comparison rust/hg-core/src/matchers.rs @ 51571:74230abb2504 stable

match: strengthen visit_children_set invariant, Recursive means "all files"

My previous interpretation of "Recursive" was too relaxed: I thought it
instructed the caller to do something like this:

> you can stop calling `visit_children_set` because you'll need to descend into
> every directory recursively, but you should still check every file if it
> matches or not

Whereas the real instruction seems to be:

> I guarantee that everything in this subtree matches, you can stop
> querying the matcher for all files and dirs altogether.

The evidence to support this:

- the test actually passes with the stronger invariant, revealing no
exceptions from this rule

- the implementation of `visit_children_set` for `DifferenceMatcher`
clearly relies on this requirement, so it must hold for that not to
lead to bugs.

51570:b39057b713b1

                path: &'a HgPath,
                matching: &'a Tree,
                visit_children_set: &'a VisitChildrenSet,
            }

            fn holds(matching: &Tree, vcs: &VisitChildrenSet) -> bool {
                match vcs {
                    VisitChildrenSet::Empty => matching.is_empty(),
                    VisitChildrenSet::This => {
                        // `This` does not come with any obligations.
                        true
                    }
                    VisitChildrenSet::Recursive => {
                        // `Recursive` does not come with any correctness
                        // obligations.
                        // It instructs the caller to stop calling
                        // `visit_children_set` for all
                        // descendants, so may have negative performance
                        // implications, but we're not testing against that
                        // here.
                        true
                    }
                    VisitChildrenSet::Set(allowed_children) => {
                        // `allowed_children` does not distinguish between
                        // files and directories: if it's not included, it
                        // must not be matched.

            pub fn check<M: Matcher + std::fmt::Debug>(
                matcher: &M,
                path: &HgPath,
                matching: &Tree,
                visit_children_set: &VisitChildrenSet,
            ) {
                if !holds(matching, visit_children_set) {
                    panic!(
                        "{:#?}",
                        Error {
                            matcher,
                            path,

        fn is_empty(&self) -> bool {
            self.files.is_empty() && self.dirs.is_empty()
        }

        fn filter_and_check<M: Matcher + Debug>(
            &self,
            m: &M,
            path: &HgPath,
        ) -> Self {
            let files: BTreeSet<HgPathBuf> = self
                .files
                .iter()
                .filter(|v| m.matches(&path.join(v)))
                .map(|f| f.to_owned())
                .collect();
            let dirs: BTreeMap<HgPathBuf, Tree> = self
                .dirs
                .iter()
                .filter_map(|(k, v)| {
                    let path = path.join(k);
                    let v = v.filter_and_check(m, &path);
                    if v.is_empty() {
                        None
                    } else {
                        Some((k.to_owned(), v))
                    }
                })
                .collect();
            let matching = Self { files, dirs };
            let vcs = m.visit_children_set(path);
            invariants::visit_children_set::check(m, path, &matching, &vcs);
            matching
        }

        fn check_matcher<M: Matcher + Debug>(
            &self,
            m: &M,
            expect_count: usize,
        ) {
            let res = self.filter_and_check(m, &HgPathBuf::new());
            if expect_count != res.len() {
                eprintln!(
                    "warning: expected {} matches, got {} for {:#?}",
                    expect_count,
                    res.len(),
                    m
                );
            }
        }
    }

51571:74230abb2504

                path: &'a HgPath,
                matching: &'a Tree,
                visit_children_set: &'a VisitChildrenSet,
            }

            fn holds(
                matching: &Tree,
                not_matching: &Tree,
                vcs: &VisitChildrenSet,
            ) -> bool {
                match vcs {
                    VisitChildrenSet::Empty => matching.is_empty(),
                    VisitChildrenSet::This => {
                        // `This` does not come with any obligations.
                        true
                    }
                    VisitChildrenSet::Recursive => {
                        // `Recursive` requires that *everything* in the
                        // subtree matches. This
                        // requirement is relied on for example in
                        // DifferenceMatcher implementation.
                        not_matching.is_empty()
                    }
                    VisitChildrenSet::Set(allowed_children) => {
                        // `allowed_children` does not distinguish between
                        // files and directories: if it's not included, it
                        // must not be matched.

            pub fn check<M: Matcher + std::fmt::Debug>(
                matcher: &M,
                path: &HgPath,
                matching: &Tree,
                not_matching: &Tree,
                visit_children_set: &VisitChildrenSet,
            ) {
                if !holds(matching, not_matching, visit_children_set) {
                    panic!(
                        "{:#?}",
                        Error {
                            matcher,
                            path,

        fn is_empty(&self) -> bool {
            self.files.is_empty() && self.dirs.is_empty()
        }

        fn make(
            files: BTreeSet<HgPathBuf>,
            dirs: BTreeMap<HgPathBuf, Tree>,
        ) -> Self {
            Self {
                files,
                dirs: dirs
                    .into_iter()
                    .filter(|(_k, v)| (!(v.is_empty())))
                    .collect(),
            }
        }

        fn filter_and_check<M: Matcher + Debug>(
            &self,
            m: &M,
            path: &HgPath,
        ) -> (Self, Self) {
            let (files1, files2): (BTreeSet<HgPathBuf>, BTreeSet<HgPathBuf>) =
                self.files
                    .iter()
                    .map(|v| v.to_owned())
                    .partition(|v| m.matches(&path.join(v)));
            let (dirs1, dirs2): (
                BTreeMap<HgPathBuf, Tree>,
                BTreeMap<HgPathBuf, Tree>,
            ) = self
                .dirs
                .iter()
                .map(|(k, v)| {
                    let path = path.join(k);
                    let (t1, t2) = v.filter_and_check(m, &path);
                    ((k.clone(), t1), (k.clone(), t2))
                })
                .unzip();
            let matching = Self::make(files1, dirs1);
            let not_matching = Self::make(files2, dirs2);
            let vcs = m.visit_children_set(path);
            invariants::visit_children_set::check(
                m,
                path,
                &matching,
                &not_matching,
                &vcs,
            );
            (matching, not_matching)
        }

        fn check_matcher<M: Matcher + Debug>(
            &self,
            m: &M,
            expect_count: usize,
        ) {
            let res = self.filter_and_check(m, &HgPathBuf::new());
            if expect_count != res.0.len() {
                eprintln!(
                    "warning: expected {} matches, got {} for {:#?}",
                    expect_count,
                    res.0.len(),
                    m
                );
            }
        }
    }