Method dichotomy_changelist

atomic-remote/src/sync.rs:512–616

Find the divergence point between our cached view and the remote's actual state using binary search on Merkle states. Returns the sequence number at which divergence begins. All entries before this point are identical between cache and remote. # Algorithm 1. Check if the last cached state matches the remote's current state. If yes, we're already in sync — return `last + 1`. 2. Otherwise, binar

(&mut self, view: &str)

    /// Each round-trip is a single `GET ?view={s}&state=` request that
    /// returns three values: `(position, merkle, tag_merkle)`.
    async fn dichotomy_changelist(&mut self, view: &str) -> RemoteResult<u64> {
        // If cache is empty, divergence is at the beginning
        let last_seq = match self.cache.last_sequence() {
            Some(seq) => seq,
            None => {
                debug!("dichotomy: cache is empty, starting from 0");
                return Ok(0);
            }
        };

        let last_state = match self.cache.last_merkle_state() {
            Some(s) => s.to_string(),
            None => return Ok(0),
        };

        debug!(
            "dichotomy: cache has {} entries, last_seq={}, last_state={}",
            self.cache.len(),
            last_seq,
            &last_state[..8.min(last_state.len())]
        );

        // Check if we're already in sync by comparing the last state
        let remote_state = self.remote.get_state(view).await?;
        self.stats.dichotomy_comparisons += 1;

        match &remote_state {
            StateResponse::State { merkle, .. } if *merkle == last_state => {
                debug!("dichotomy: already in sync at seq {}", last_seq);
                return Ok(last_seq + 1);
            }
            StateResponse::Empty => {
                debug!("dichotomy: remote view is empty");
                return Ok(0);
            }
            _ => {
                debug!("dichotomy: states differ, starting binary search");
            }
        }

        // Binary search for the divergence point
        let mut lo: u64 = 0;
        let mut hi: u64 = last_seq;

        while lo < hi {
            let mid = (lo + hi) / 2;

            // Get the Merkle state at the midpoint from our cache
            let cached_state = match self.cache.get_state(mid) {
                Some(s) => s.to_string(),
                None => {
                    // Gap in cache — we can't compare, assume divergence is here or earlier
                    debug!(
                        "dichotomy: gap in cache at {}, narrowing to [{}, {}]",
                        mid, lo, mid
                    );
                    hi = mid;
                    continue;