Snapshot: whole-tree passes as merge joins (refs #41) d616faf5d136

        let pick = crate::timing::phase("snapshot:   of which picking the changed");

        let changed: BTreeMap<String, FsEntry> = join(fs_entries, &base_snapshot.files)

            .filter_map(|(p, e, f)| {

                let e = e?;

                (!e.unchanged || f.is_none_or(|f| f.kind != e.kind || f.mode.exec != e.exec))

                    .then(|| (p.clone(), e.clone()))

        // Paths the base has and the disk does not.

        let gone = join(&base_snapshot.files, fs_entries)

            .filter_map(|(p, f, e)| (e.is_none()).then_some((p, f?)));

        for (p, f) in gone {

            if f.kind == NodeKind::Dir {

        drop(pick);

        let _build = crate::timing::phase("snapshot:   of which building the change");

                let sets = crate::timing::phase("snapshot:   of which choosing graphs");

                // Every file but those on disk known unchanged.

                let need: Vec<(&str, NodeId)> = join(&view.entries, &fs_entries)

                    .filter_map(|(p, v, f)| {

                        let v = v?;

                        (v.kind == NodeKind::File && !f.is_some_and(|f| f.unchanged))

                            .then_some((p.as_str(), v.node))

                    })

                let render: std::collections::HashSet<&str> =

                    need.iter().map(|(p, _)| *p).collect();

                let need: Vec<NodeId> = need.iter().map(|(_, n)| *n).collect();

                drop(sets);

                base.materialize_only(&render)

}

/// Two maps side by side in key order: each key of either, with its value

/// in each. Linear, with no lookups, for maps of a whole tree.

fn join<'a, A, B>(

    a: &'a BTreeMap<String, A>,

    b: &'a BTreeMap<String, B>,

) -> impl Iterator<Item = (&'a String, Option<&'a A>, Option<&'a B>)> {

    let (mut a, mut b) = (a.iter().peekable(), b.iter().peekable());

    std::iter::from_fn(move || match (a.peek(), b.peek()) {

        (None, None) => None,

        (Some(_), None) => a.next().map(|(k, v)| (k, Some(v), None)),

        (None, Some(_)) => b.next().map(|(k, v)| (k, None, Some(v))),

        (Some((ka, _)), Some((kb, _))) => match ka.cmp(kb) {

            std::cmp::Ordering::Less => a.next().map(|(k, v)| (k, Some(v), None)),

            std::cmp::Ordering::Greater => b.next().map(|(k, v)| (k, None, Some(v))),

            std::cmp::Ordering::Equal => {

                let (k, va) = a.next()?;

                let (_, vb) = b.next()?;

                Some((k, Some(va), Some(vb)))

            }

        },

    })

}

#[cfg(test)]

mod join_tests {

    use super::*;

    #[test]

    fn join_pairs_every_key_in_order() {

        let a: BTreeMap<String, u8> = [("a", 1), ("b/c", 2), ("d", 3)]

            .into_iter()

            .map(|(k, v)| (k.to_string(), v))

            .collect();

        let b: BTreeMap<String, char> = [("b", 'x'), ("b/c", 'y'), ("e", 'z')]

            .into_iter()

            .map(|(k, v)| (k.to_string(), v))

            .collect();

        let got: Vec<(String, Option<u8>, Option<char>)> = join(&a, &b)

            .map(|(k, x, y)| (k.clone(), x.copied(), y.copied()))

            .collect();

        let want = vec![

            ("a".to_string(), Some(1), None),

            ("b".to_string(), None, Some('x')),

            ("b/c".to_string(), Some(2), Some('y')),

            ("d".to_string(), Some(3), None),

            ("e".to_string(), None, Some('z')),

        ];

        assert_eq!(got, want);

    }

        self.materialize_leaving(|_, e| skip.contains(&e.node))

    }

    /// As [`State::materialize_except`], rendering only the text files at

    /// `render` (a few, where the caller knows the rest unchanged).

    pub fn materialize_only(&self, render: &std::collections::HashSet<&str>) -> Snapshot {

        self.materialize_leaving(|p, _| !render.contains(p))

    }

    fn materialize_leaving(

        &self,

        leave: impl Fn(&str, &crate::tree::TreeEntry) -> bool + Sync,

    ) -> Snapshot {

                if e.kind == NodeKind::File && !e.mode.opaque && leave(path, e) {