test_that/matchers/containers/container_contains/

unordered_matcher.rs

// Copyright 2022 Google LLC
// Copyright 2026 Bradford Hovinen <bradford@hovinen.me>
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// There are no visible documentation elements in this module; the declarative
// macro is documented in the matchers module.
#![doc(hidden)]

/// Module for use only by the macros in this module.
///
/// **For internal use only. API stablility is not guaranteed!**
#[doc(hidden)]
pub mod __internal {
    use crate::{
        description::Description,
        matcher::{Describable, Matcher, MatcherResult},
        matcher_support::count_elements::count_elements,
        matchers::__internal::ContainerContainsOrderedMatcher,
        matchers::containers::{
            OwnedItems, RefItems,
            container_contains::{PairBorrow, Requirements},
        },
    };
    use alloc::{boxed::Box, collections::BTreeSet, vec::Vec};
    use core::{borrow::Borrow, fmt::Debug, marker::PhantomData};

    /// Matches elements of an iterable collection with a sequence of matchers,
    /// in any order.
    ///
    /// This struct is meant to be used only through the
    /// `contains_exactly![...]` macro.
    pub struct ContainerContainsUnorderedMatcher<'matchers, ContainerT: ?Sized, T: Debug, ModeT> {
        elements: Vec<Box<dyn Matcher<T> + 'matchers>>,
        requirements: Requirements,
        _phantom: PhantomData<(*const ContainerT, ModeT)>,
    }

    impl<'matchers, ContainerT: ?Sized, T: Debug, ModeT>
        ContainerContainsUnorderedMatcher<'matchers, ContainerT, T, ModeT>
    {
        /// Constructs a [ContainerContainsUnorderedMatcher] with the given
        /// matchers.
        ///
        /// This is not intended to be invoked directly, but rather through the
        /// macros [contains_exactly], [contains_each] and
        /// [is_contained_in].
        #[doc(hidden)]
        pub fn new(
            elements: Vec<Box<dyn Matcher<T> + 'matchers>>,
            requirements: Requirements,
        ) -> Self {
            Self { elements, requirements, _phantom: PhantomData }
        }

        /// Asserts that the matchers must match the elements of the collection
        /// in the same order as they appear when iterating.
        pub fn in_order(self) -> ContainerContainsOrderedMatcher<'matchers, ContainerT, T, ModeT> {
            ContainerContainsOrderedMatcher::new(self.elements, self.requirements)
        }

        fn matches_with_iter<ItemT: Borrow<T>>(
            &self,
            n: usize,
            actual: impl Iterator<Item = ItemT>,
        ) -> MatcherResult {
            let match_matrix = MatchMatrix::generate(actual, n, &self.elements);
            match_matrix.is_match_for(self.requirements).into()
        }

        // This performs the checks in three different steps. This is useful for
        // performance but also to produce an actionable error message.
        // 1. Verifies that both collections have the same size (via size_mismatch
        //    param)
        // 2. Verifies that each actual element matches at least one expected element
        //    and vice versa.
        // 3. Verifies that a perfect matching exists using Ford-Fulkerson.
        fn explain_match_with_iters<ItemT1: Borrow<T>, ItemT2: Borrow<T>>(
            &self,
            size_mismatch: Option<Description>,
            n: usize,
            iter_for_generate: impl Iterator<Item = ItemT1>,
            iter_for_explain: impl Iterator<Item = ItemT2>,
        ) -> Description {
            if let Some(explanation) = size_mismatch {
                return explanation;
            }
            let match_matrix = MatchMatrix::generate(iter_for_generate, n, &self.elements);
            if let Some(unmatchable) = match_matrix.explain_unmatchable(self.requirements) {
                return unmatchable;
            }
            let best_match = match_matrix.find_best_match();
            best_match
                .get_explanation(iter_for_explain, &self.elements, self.requirements)
                .unwrap_or("whose elements all match".into())
        }
    }

    impl<'matchers, T: Debug, ContainerT: Debug + ?Sized> Matcher<ContainerT>
        for ContainerContainsUnorderedMatcher<'matchers, ContainerT, T, RefItems>
    where
        for<'b> &'b ContainerT: IntoIterator<Item = &'b T>,
    {
        fn matches(&self, actual: &ContainerT) -> MatcherResult {
            self.matches_with_iter(count_elements(actual), actual.into_iter())
        }

        fn explain_match(&self, actual: &ContainerT) -> Description {
            self.explain_match_with_iters(
                self.requirements.explain_size_mismatch(actual, self.elements.len()),
                count_elements(actual),
                actual.into_iter(),
                actual.into_iter(),
            )
        }
    }

    impl<'matchers, T: Debug, ContainerT: Debug + ?Sized> Matcher<ContainerT>
        for ContainerContainsUnorderedMatcher<'matchers, ContainerT, T, OwnedItems>
    where
        for<'b> &'b ContainerT: IntoIterator<Item = T>,
    {
        fn matches(&self, actual: &ContainerT) -> MatcherResult {
            self.matches_with_iter(count_elements(actual), actual.into_iter())
        }

        fn explain_match(&self, actual: &ContainerT) -> Description {
            self.explain_match_with_iters(
                self.requirements.explain_size_mismatch(actual, self.elements.len()),
                count_elements(actual),
                actual.into_iter(),
                actual.into_iter(),
            )
        }
    }

    impl<'matchers, T: Debug, ContainerT: ?Sized, ModeT> Describable
        for ContainerContainsUnorderedMatcher<'matchers, ContainerT, T, ModeT>
    {
        fn describe(&self, matcher_result: MatcherResult) -> Description {
            format!(
                "{} elements matching in any order:\n{}",
                if matcher_result.into() { "contains" } else { "doesn't contain" },
                self.elements
                    .iter()
                    .map(|matcher| matcher.describe(MatcherResult::Match))
                    .collect::<Description>()
                    .enumerate()
                    .indent()
            )
            .into()
        }
    }

    type KeyValueMatcher<'a, KeyT, ValueT> =
        (Box<dyn Matcher<KeyT> + 'a>, Box<dyn Matcher<ValueT> + 'a>);

    /// This is the analogue to [ContainerContainsUnorderedMatcher] for maps and
    /// map-like collections.
    ///
    /// **For internal use only. API stablility is not guaranteed!**
    #[doc(hidden)]
    pub struct MapContainsMatcher<'matchers, ContainerT, KeyT, ValueT, ModeT, const N: usize>
    where
        ContainerT: ?Sized,
        KeyT: Debug,
        ValueT: Debug,
    {
        elements: [KeyValueMatcher<'matchers, KeyT, ValueT>; N],
        requirements: Requirements,
        phantom: PhantomData<(ModeT, ContainerT)>,
    }

    impl<'matchers, ContainerT: ?Sized, KeyT: Debug, ValueT: Debug, ModeT, const N: usize>
        MapContainsMatcher<'matchers, ContainerT, KeyT, ValueT, ModeT, N>
    {
        pub fn new(
            elements: [KeyValueMatcher<'matchers, KeyT, ValueT>; N],
            requirements: Requirements,
        ) -> Self {
            Self { elements, requirements, phantom: PhantomData }
        }

        fn matches_with_iter<ItemT: PairBorrow<KeyT, ValueT>>(
            &self,
            n: usize,
            actual: impl Iterator<Item = ItemT>,
        ) -> MatcherResult {
            let match_matrix = MatchMatrix::generate_for_map(actual, n, &self.elements);
            match_matrix.is_match_for(self.requirements).into()
        }

        fn explain_match_with_iters<
            ItemT1: PairBorrow<KeyT, ValueT>,
            ItemT2: PairBorrow<KeyT, ValueT>,
        >(
            &self,
            size_mismatch: Option<Description>,
            n: usize,
            iter_for_generate: impl Iterator<Item = ItemT1>,
            iter_for_explain: impl Iterator<Item = ItemT2>,
        ) -> Description {
            if let Some(explanation) = size_mismatch {
                return explanation;
            }
            let match_matrix = MatchMatrix::generate_for_map(iter_for_generate, n, &self.elements);
            if let Some(unmatchable) = match_matrix.explain_unmatchable(self.requirements) {
                return unmatchable;
            }
            let best_match = match_matrix.find_best_match();
            best_match
                .get_explanation_for_map(iter_for_explain, &self.elements, self.requirements)
                .unwrap_or("whose elements all match".into())
        }
    }

    impl<'matchers, KeyT: Debug, ValueT: Debug, ContainerT: Debug + ?Sized, const N: usize>
        Matcher<ContainerT> for MapContainsMatcher<'matchers, ContainerT, KeyT, ValueT, RefItems, N>
    where
        for<'b> &'b ContainerT: IntoIterator<Item = (&'b KeyT, &'b ValueT)>,
    {
        fn matches(&self, actual: &ContainerT) -> MatcherResult {
            self.matches_with_iter(count_elements(actual), actual.into_iter())
        }

        fn explain_match(&self, actual: &ContainerT) -> Description {
            self.explain_match_with_iters(
                self.requirements.explain_size_mismatch(actual, N),
                count_elements(actual),
                actual.into_iter(),
                actual.into_iter(),
            )
        }
    }

    impl<'matchers, KeyT: Debug, ValueT: Debug, ContainerT: Debug + ?Sized, const N: usize>
        Matcher<ContainerT>
        for MapContainsMatcher<'matchers, ContainerT, KeyT, ValueT, OwnedItems, N>
    where
        for<'b> &'b ContainerT: IntoIterator<Item = (KeyT, ValueT)>,
    {
        fn matches(&self, actual: &ContainerT) -> MatcherResult {
            self.matches_with_iter(count_elements(actual), actual.into_iter())
        }

        fn explain_match(&self, actual: &ContainerT) -> Description {
            self.explain_match_with_iters(
                self.requirements.explain_size_mismatch(actual, N),
                count_elements(actual),
                actual.into_iter(),
                actual.into_iter(),
            )
        }
    }

    impl<'matchers, KeyT: Debug, ValueT: Debug, ContainerT: ?Sized, ModeT, const N: usize>
        Describable for MapContainsMatcher<'matchers, ContainerT, KeyT, ValueT, ModeT, N>
    {
        fn describe(&self, matcher_result: MatcherResult) -> Description {
            format!(
                "{} elements matching in any order:\n{}",
                if matcher_result.into() { "contains" } else { "doesn't contain" },
                self.elements
                    .iter()
                    .map(|(key_matcher, value_matcher)| format!(
                        "{} => {}",
                        key_matcher.describe(MatcherResult::Match),
                        value_matcher.describe(MatcherResult::Match)
                    ))
                    .collect::<Description>()
                    .indent()
            )
            .into()
        }
    }

    /// The bipartite matching graph between actual and expected elements.
    pub(crate) struct MatchMatrix(Vec<Vec<MatcherResult>>, usize);

    impl MatchMatrix {
        fn generate<'matchers, ActualT: Debug + ?Sized + 'matchers, ItemT: Borrow<ActualT>>(
            actual_items: impl Iterator<Item = ItemT>,
            n_actual: usize,
            expected: &[Box<dyn Matcher<ActualT> + 'matchers>],
        ) -> Self {
            let mut matrix = MatchMatrix(
                vec![vec![MatcherResult::NoMatch; expected.len()]; n_actual],
                expected.len(),
            );
            for (actual_idx, actual_item) in actual_items.enumerate() {
                for (expected_idx, expected) in expected.iter().enumerate() {
                    matrix.0[actual_idx][expected_idx] = expected.matches(actual_item.borrow());
                }
            }
            matrix
        }

        pub(crate) fn generate_for_fixed_matcher<
            'matchers,
            MatcherT: Matcher<ActualT> + 'matchers,
            ActualT: Debug + ?Sized + 'matchers,
            ItemT: Borrow<ActualT>,
        >(
            actual_items: impl Iterator<Item = ItemT>,
            n_actual: usize,
            expected: &[MatcherT],
        ) -> Self {
            let mut matrix = MatchMatrix(
                vec![vec![MatcherResult::NoMatch; expected.len()]; n_actual],
                expected.len(),
            );
            for (actual_idx, actual_item) in actual_items.enumerate() {
                for (expected_idx, expected) in expected.iter().enumerate() {
                    matrix.0[actual_idx][expected_idx] = expected.matches(actual_item.borrow());
                }
            }
            matrix
        }

        fn generate_for_map<
            'matchers,
            KeyT: Debug,
            ValueT: Debug,
            ItemT: PairBorrow<KeyT, ValueT>,
        >(
            actual_items: impl Iterator<Item = ItemT>,
            n_actual: usize,
            expected: &[KeyValueMatcher<'matchers, KeyT, ValueT>],
        ) -> Self {
            let mut matrix = MatchMatrix(
                vec![vec![MatcherResult::NoMatch; expected.len()]; n_actual],
                expected.len(),
            );
            for (actual_idx, actual_item) in actual_items.enumerate() {
                for (expected_idx, (expected_key, expected_value)) in expected.iter().enumerate() {
                    matrix.0[actual_idx][expected_idx] =
                        (expected_key.matches(actual_item.borrow_key()).into()
                            && expected_value.matches(actual_item.borrow_value()).into())
                        .into();
                }
            }
            matrix
        }

        pub(crate) fn is_match_for(&self, requirements: Requirements) -> bool {
            match requirements {
                Requirements::PerfectMatch => {
                    !self.find_unmatchable_elements().has_unmatchable_elements()
                        && self.find_best_match().is_full_match()
                }
                Requirements::Superset => {
                    !self.find_unmatched_expected().has_unmatchable_elements()
                        && self.find_best_match().is_superset_match()
                }
                Requirements::Subset => {
                    !self.find_unmatched_actual().has_unmatchable_elements()
                        && self.find_best_match().is_subset_match()
                }
            }
        }

        fn explain_unmatchable(&self, requirements: Requirements) -> Option<Description> {
            let unmatchable_elements = match requirements {
                Requirements::PerfectMatch => self.find_unmatchable_elements(),
                Requirements::Superset => self.find_unmatched_expected(),
                Requirements::Subset => self.find_unmatched_actual(),
            };
            unmatchable_elements.get_explanation()
        }

        // Verifies that each actual matches at least one expected and that
        // each expected matches at least one actual.
        // This is a necessary condition but not sufficient. But it is faster
        // than `find_best_match()`.
        fn find_unmatchable_elements(&self) -> UnmatchableElements {
            let unmatchable_actual =
                self.0.iter().map(|row| row.iter().all(|&e| e.is_no_match())).collect();
            let mut unmatchable_expected = vec![false; self.1];
            for (col_idx, expected) in unmatchable_expected.iter_mut().enumerate() {
                *expected = self.0.iter().map(|row| row[col_idx]).all(|e| e.is_no_match());
            }
            UnmatchableElements { unmatchable_actual, unmatchable_expected }
        }

        fn find_unmatched_expected(&self) -> UnmatchableElements {
            let mut unmatchable_expected = vec![false; self.1];
            for (col_idx, expected) in unmatchable_expected.iter_mut().enumerate() {
                *expected = self.0.iter().map(|row| row[col_idx]).all(|e| e.is_no_match());
            }
            UnmatchableElements {
                unmatchable_actual: vec![false; self.0.len()],
                unmatchable_expected,
            }
        }

        fn find_unmatched_actual(&self) -> UnmatchableElements {
            let unmatchable_actual =
                self.0.iter().map(|row| row.iter().all(|e| e.is_no_match())).collect();
            UnmatchableElements {
                unmatchable_actual,
                unmatchable_expected: vec![false; self.0.len()],
            }
        }

        // Verifies that a full match exists.
        //
        // Uses the well-known Ford-Fulkerson max flow method to find a maximum
        // bipartite matching. Flow is considered to be from actual to expected.
        // There is an implicit source node that is connected to all of the actual
        // nodes, and an implicit sink node that is connected to all of the
        // expected nodes. All edges have unit capacity.
        //
        // Neither the flow graph nor the residual flow graph are represented
        // explicitly. Instead, they are implied by the information in `self.0` and
        // the local `actual_match : [Option<usize>; N]` whose elements are initialized
        // to `None`. This represents the initial state of the algorithm,
        // where the flow graph is empty, and the residual flow graph has the
        // following edges:
        //   - An edge from source to each actual element node
        //   - An edge from each expected element node to sink
        //   - An edge from each actual element node to each expected element node, if
        //     the actual element matches the expected element, i.e.
        //     `matches!(self.0[actual_id][expected_id], Matches)`
        //
        // When the `try_augment(...)` method adds a flow, it sets `actual_match[l] =
        // Some(r)` for some nodes l and r. This induces the following changes:
        //   - The edges (source, l), (l, r), and (r, sink) are added to the flow graph.
        //   - The same three edges are removed from the residual flow graph.
        //   - The reverse edges (l, source), (r, l), and (sink, r) are added to the
        //     residual flow graph, which is a directional graph representing unused
        //     flow capacity.
        //
        // When the method augments a flow (changing `actual_match[l]` from `Some(r1)`
        // to `Some(r2)`), this can be thought of as "undoing" the above steps
        // with respect to r1 and "redoing" them with respect to r2.
        //
        // It bears repeating that the flow graph and residual flow graph are
        // never represented explicitly, but can be derived by looking at the
        // information in 'self.0' and in `actual_match`.
        //
        // As an optimization, there is a second local `expected_match: [Option<usize>;
        // N]` which does not provide any new information. Instead, it enables
        // more efficient queries about edges entering or leaving the expected elements
        // nodes of the flow or residual flow graphs. The following invariants
        // are maintained:
        //
        // actual_match[a] == None or expected_match[actual_match[a].unwrap()] ==
        // Some(a)
        // expected_match[r] == None or actual_match[expected_match[e].unwrap()] ==
        // Some(e)
        //
        // | [ source ]                                                              |
        // |   |||                                                                   |
        // |   |||                                                                   |
        // |   ||\-> actual_match[0]=Some(1) -\   expected_match[0]=None    ---\     |
        // |   ||                             |                                |     |
        // |   |\--> actual_match[1]=None     \-> expected_match[1]=Some(0) --\|     |
        // |   |                                                              ||     |
        // |   \---> actual_match[2]=Some(2)  --> expected_match[2]=Some(2) -\||     |
        // |                                                                 |||     |
        // |         elements                     matchers                   vvv     |
        // |                                                               [ sink ]  |
        //
        // See Also:
        //   [1] Cormen, et al (2001). "Section 26.2: The Ford-Fulkerson method".
        //       "Introduction to Algorithms (Second ed.)", pp. 651-664.
        //   [2] "Ford-Fulkerson algorithm", Wikipedia,
        //       'http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm'
        fn find_best_match(&self) -> BestMatch {
            let mut actual_match = vec![None; self.0.len()];
            let mut expected_match: Vec<Option<usize>> = vec![None; self.1];
            // Searches the residual flow graph for a path from each actual node to
            // the sink in the residual flow graph, and if one is found, add this path
            // to the graph.
            // It's okay to search through the actual nodes once. The
            // edge from the implicit source node to each previously-visited actual
            // node will have flow if that actual node has any path to the sink
            // whatsoever. Subsequent augmentations can only add flow to the
            // network, and cannot take away that previous flow unit from the source.
            // Since the source-to-actual edge can only carry one flow unit (or,
            // each actual element can be matched to only one expected element), there is no
            // need to visit the actual nodes more than once looking for
            // augmented paths. The flow is known to be possible or impossible
            // by looking at the node once.
            for actual_idx in 0..self.0.len() {
                assert!(actual_match[actual_idx].is_none());
                let mut seen = vec![false; self.1];
                self.try_augment(actual_idx, &mut seen, &mut actual_match, &mut expected_match);
            }
            BestMatch(actual_match, self.1)
        }

        // Perform a depth-first search from actual node `actual_idx` to the sink by
        // searching for an unassigned expected node. If a path is found, flow
        // is added to the network by linking the actual and expected vector elements
        // corresponding each segment of the path. Returns true if a path to
        // sink was found, which means that a unit of flow was added to the
        // network. The 'seen' array elements correspond to expected nodes and are
        // marked to eliminate cycles from the search.
        //
        // Actual nodes will only be explored at most once because they
        // are accessible from at most one expected node in the residual flow
        // graph.
        //
        // Note that `actual_match[actual_idx]` is the only element of `actual_match`
        // that `try_augment(...)` will potentially transition from `None` to
        // `Some(...)`. Any other `actual_match` element holding `None` before
        // `try_augment(...)` will be holding it when `try_augment(...)`
        // returns.
        //
        fn try_augment(
            &self,
            actual_idx: usize,
            seen: &mut [bool],
            actual_match: &mut [Option<usize>],
            expected_match: &mut [Option<usize>],
        ) -> bool {
            for expected_idx in 0..expected_match.len() {
                if seen[expected_idx] {
                    continue;
                }
                if self.0[actual_idx][expected_idx].is_no_match() {
                    continue;
                }
                // There is an edge between `actual_idx` and `expected_idx`.
                seen[expected_idx] = true;
                // Next a search is performed to determine whether
                // this edge is a dead end or leads to the sink.
                //
                // `expected_match[expected_idx].is_none()` means that there is residual flow
                // from expected node at index expected_idx to the sink, so we
                // can use that to finish this flow path and return success.
                //
                // Otherwise, we look for a residual flow starting from
                // `expected_match[expected_idx].unwrap()` by calling
                // ourselves recursively to see if this ultimately leads to
                // sink.
                if expected_match[expected_idx].is_none()
                    || self.try_augment(
                        expected_match[expected_idx].unwrap(),
                        seen,
                        actual_match,
                        expected_match,
                    )
                {
                    // We found a residual flow from source to sink. We thus need to add the new
                    // edge to the current flow.
                    // Note: this also remove the potential flow that existed by overwriting the
                    // value in the `expected_match` and `actual_match`.
                    expected_match[expected_idx] = Some(actual_idx);
                    actual_match[actual_idx] = Some(expected_idx);
                    return true;
                }
            }
            false
        }
    }

    /// The list of elements that do not match any element in the corresponding
    /// set.
    /// These lists are represented as fixed sized bit set to avoid
    /// allocation.
    /// TODO(bjacotg) Use BitArr!(for N) once generic_const_exprs is stable.
    struct UnmatchableElements {
        unmatchable_actual: Vec<bool>,
        unmatchable_expected: Vec<bool>,
    }

    impl UnmatchableElements {
        fn has_unmatchable_elements(&self) -> bool {
            self.unmatchable_actual.iter().any(|b| *b)
                || self.unmatchable_expected.iter().any(|b| *b)
        }

        fn get_explanation(&self) -> Option<Description> {
            let unmatchable_actual = self.unmatchable_actual();
            let actual_idx = unmatchable_actual
                .iter()
                .map(|idx| format!("#{}", idx))
                .collect::<Vec<_>>()
                .join(", ");
            let unmatchable_expected = self.unmatchable_expected();
            let expected_idx = unmatchable_expected
                .iter()
                .map(|idx| format!("#{}", idx))
                .collect::<Vec<_>>()
                .join(", ");
            match (unmatchable_actual.len(), unmatchable_expected.len()) {
                (0, 0) => None,
                (1, 0) => {
                    Some(format!("whose element {actual_idx} does not match any expected elements").into())
                }
                (_, 0) => {
                    Some(format!("whose elements {actual_idx} do not match any expected elements",).into())
                }
                (0, 1) => Some(format!(
                    "which has no element matching the expected element {expected_idx}"
                ).into()),
                (0, _) => Some(format!(
                    "which has no elements matching the expected elements {expected_idx}"
                ).into()),
                (1, 1) => Some(format!(
                    "whose element {actual_idx} does not match any expected elements and no elements match the expected element {expected_idx}"
                ).into()),
                (_, 1) => Some(format!(
                    "whose elements {actual_idx} do not match any expected elements and no elements match the expected element {expected_idx}"
                ).into()),
                (1, _) => Some(format!(
                    "whose element {actual_idx} does not match any expected elements and no elements match the expected elements {expected_idx}"
                ).into()),
                (_, _) => Some(format!(
                    "whose elements {actual_idx} do not match any expected elements and no elements match the expected elements {expected_idx}"
                ).into()),
            }
        }

        fn unmatchable_actual(&self) -> Vec<usize> {
            self.unmatchable_actual
                .iter()
                .enumerate()
                .filter_map(|(idx, b)| if *b { Some(idx) } else { None })
                .collect()
        }

        fn unmatchable_expected(&self) -> Vec<usize> {
            self.unmatchable_expected
                .iter()
                .enumerate()
                .filter_map(|(idx, b)| if *b { Some(idx) } else { None })
                .collect()
        }
    }

    /// The representation of a match between actual and expected.
    /// The value at idx represents to which expected the actual at idx is
    /// matched with. For example, `BestMatch([Some(0), None, Some(1)])`
    /// means:
    ///  * The 0th element in actual matches the 0th element in expected.
    ///  * The 1st element in actual does not match.
    ///  * The 2nd element in actual matches the 1st element in expected.
    struct BestMatch(Vec<Option<usize>>, usize);

    impl BestMatch {
        fn is_full_match(&self) -> bool {
            self.0.iter().all(|o| o.is_some())
        }

        fn is_subset_match(&self) -> bool {
            self.is_full_match()
        }

        fn is_superset_match(&self) -> bool {
            self.get_unmatched_expected().is_empty()
        }

        fn get_matches(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
            self.0.iter().enumerate().filter_map(|(actual_idx, maybe_expected_idx)| {
                maybe_expected_idx.map(|expected_idx| (actual_idx, expected_idx))
            })
        }

        fn get_unmatched_actual(&self) -> impl Iterator<Item = usize> + '_ {
            self.0
                .iter()
                .enumerate()
                .filter(|&(_, o)| o.is_none())
                .map(|(actual_idx, _)| actual_idx)
        }

        fn get_unmatched_expected(&self) -> Vec<usize> {
            let matched_expected: BTreeSet<_> = self.0.iter().flatten().collect();
            (0..self.1).filter(|expected_idx| !matched_expected.contains(expected_idx)).collect()
        }

        fn get_explanation<'matchers, T: Debug, ItemT: Borrow<T>>(
            &self,
            actual_items: impl Iterator<Item = ItemT>,
            expected: &[Box<dyn Matcher<T> + 'matchers>],
            requirements: Requirements,
        ) -> Option<Description> {
            let actual: Vec<ItemT> = actual_items.collect();
            if self.is_full_match() {
                return None;
            }

            let matches = self.get_matches().map(|(actual_idx, expected_idx)| {
                format!(
                    "Actual element {:?} at index {actual_idx} matched expected element `{}` at index {expected_idx}.",
                    actual[actual_idx].borrow(),
                    expected[expected_idx].describe(MatcherResult::Match),
                )
            });

            let unmatched_actual = self.get_unmatched_actual().map(|actual_idx| {
                format!(
                    "Actual element {:#?} at index {actual_idx} did not match any remaining expected element.",
                    actual[actual_idx].borrow()
                )
            });

            let unmatched_expected =
                self.get_unmatched_expected().into_iter().map(|expected_idx| {
                    format!(
                        "Expected element `{}` at index {expected_idx} did not match any remaining actual element.",
                        expected[expected_idx].describe(MatcherResult::Match)
                    )
                });

            let best_match = matches
                .chain(unmatched_actual)
                .chain(unmatched_expected)
                .collect::<Description>()
                .indent();
            Some(
                format!(
                    "which does not have a {requirements} match with the expected elements. The best match found was:\n{best_match}"
                )
                .into(),
            )
        }

        fn get_explanation_for_map<
            'matchers,
            KeyT: Debug,
            ValueT: Debug,
            ItemT: PairBorrow<KeyT, ValueT>,
        >(
            &self,
            actual_items: impl Iterator<Item = ItemT>,
            expected: &[KeyValueMatcher<'matchers, KeyT, ValueT>],
            requirements: Requirements,
        ) -> Option<Description> {
            let actual: Vec<ItemT> = actual_items.collect();
            if self.is_full_match() {
                return None;
            }

            let matches = self.get_matches().map(|(actual_idx, expected_idx)| {
                format!(
                    "Actual element {:?} => {:?} at index {actual_idx} matched expected element `{}` => `{}` at index {expected_idx}.",
                    actual[actual_idx].borrow_key(),
                    actual[actual_idx].borrow_value(),
                    expected[expected_idx].0.describe(MatcherResult::Match),
                    expected[expected_idx].1.describe(MatcherResult::Match),
                )
            });

            let unmatched_actual = self.get_unmatched_actual().map(|actual_idx| {
                format!(
                    "Actual element {:#?} => {:#?} at index {actual_idx} did not match any remaining expected element.",
                    actual[actual_idx].borrow_key(),
                    actual[actual_idx].borrow_value(),
                )
            });

            let unmatched_expected =
                self.get_unmatched_expected().into_iter().map(|expected_idx| {
                    format!(
                        "Expected element `{}` => `{}` at index {expected_idx} did not match any remaining actual element.",
                        expected[expected_idx].0.describe(MatcherResult::Match),
                        expected[expected_idx].1.describe(MatcherResult::Match),
                    )
                });

            let best_match = matches
                .chain(unmatched_actual)
                .chain(unmatched_expected)
                .collect::<Description>()
                .indent();
            Some(
                format!(
                    "which does not have a {requirements} match with the expected elements. The best match found was:\n{best_match}"
                )
                .into(),
            )
        }
    }
}

#[cfg(all(test, feature = "std"))]
mod tests {
    use super::__internal::MapContainsMatcher;
    use crate::matcher::Matcher;
    use crate::matchers::containers::RefItems;
    use crate::prelude::*;
    use indoc::indoc;
    use std::collections::HashMap;

    #[test]
    fn has_correct_description_for_map() -> TestResult<()> {
        // ContainerContainsUnorderedMatcher maintains references to the matchers, so
        // the constituent matchers must live longer. Inside a verify_that!
        // macro, the compiler takes care of that, but when the matcher is
        // created separately, we must create the constitute matchers separately
        // so that they aren't dropped too early.
        let matchers = ((eq(2), eq("Two")), (eq(1), eq("One")), (eq(3), eq("Three")));
        let result = verify_that!(
            HashMap::from([(1, "one")]),
            contains_exactly![
                matchers.0.0 => matchers.0.1,
                matchers.1.0 => matchers.1.1,
                matchers.2.0 => matchers.2.1
            ]
        );
        verify_that!(
            result,
            err(displays_as(contains_substring(indoc!(
                "
                contains elements matching in any order:
                  is equal to 2 => is equal to \"Two\"
                  is equal to 1 => is equal to \"One\"
                  is equal to 3 => is equal to \"Three\""
            ))))
        )
    }

    #[cfg(feature = "regex")]
    #[test]
    fn contains_exactly_description_no_full_match_with_map() -> TestResult<()> {
        // ContainerContainsUnorderedMatcher maintains references to the matchers, so
        // the constituent matchers must live longer. Inside a verify_that!
        // macro, the compiler takes care of that, but when the matcher is
        // created separately, we must create the constitute matchers separately
        // so that they aren't dropped too early.
        let matchers = ((anything(), eq(1)), (anything(), eq(2)), (anything(), eq(2)));
        let matcher: MapContainsMatcher<HashMap<u32, u32>, _, _, RefItems, 3> = contains_exactly![
            matchers.0.0 => matchers.0.1,
            matchers.1.0 => matchers.1.1,
            matchers.2.0 => matchers.2.1,
        ];
        let value: HashMap<u32, u32> = HashMap::from_iter([(0, 1), (1, 1), (2, 2)]);
        verify_that!(
            matcher.explain_match(&value),
                displays_as(
                    contains_regex(
                        "Actual element 2 => 2 at index [0-2] matched expected element `is anything` => `is equal to 2` at index [0-2]."
                    )
                )
                .and(
                    displays_as(
                        contains_regex(
                            "Actual element [0-1] => [0-1] at index [0-2] did not match any remaining expected element."
                        )
                    )
                )
                .and(
                    displays_as(
                        contains_substring(
                            "Expected element `is anything` => `is equal to 2` at index 2 did not match any remaining actual element."
                        )
                    )
                )
        )
    }
}