1 // Copyright 2022 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // There are no visible documentation elements in this module; the declarative 16 // macro is documented in the matchers module. 17 #![doc(hidden)] 18 19 /// Matches a container whose elements in any order have a 1:1 correspondence 20 /// with the provided element matchers. 21 /// 22 /// ``` 23 /// # use googletest::prelude::*; 24 /// # fn should_pass() -> Result<()> { 25 /// verify_that!(vec![3, 2, 1], unordered_elements_are![eq(&1), ge(&2), anything()])?; // Passes 26 /// # Ok(()) 27 /// # } 28 /// # fn should_fail_1() -> Result<()> { 29 /// verify_that!(vec![1], unordered_elements_are![eq(&1), ge(&2)])?; // Fails: container has wrong size 30 /// # Ok(()) 31 /// # } 32 /// # fn should_fail_2() -> Result<()> { 33 /// verify_that!(vec![3, 2, 1], unordered_elements_are![eq(&1), ge(&4), eq(&2)])?; // Fails: second matcher not matched 34 /// # Ok(()) 35 /// # } 36 /// # fn should_fail_3() -> Result<()> { 37 /// verify_that!(vec![3, 2, 1], unordered_elements_are![ge(&3), ge(&3), ge(&3)])?; // Fails: no 1:1 correspondence 38 /// # Ok(()) 39 /// # } 40 /// # should_pass().unwrap(); 41 /// # should_fail_1().unwrap_err(); 42 /// # should_fail_2().unwrap_err(); 43 /// # should_fail_3().unwrap_err(); 44 /// ``` 45 /// 46 /// The actual value must be a container such as a `&Vec`, an array, or a 47 /// slice. More precisely, the actual value must implement [`IntoIterator`]. 48 /// 49 /// This can also be omitted in [`verify_that!`] macros and replaced with curly 50 /// brackets. 51 /// 52 /// ``` 53 /// # use googletest::prelude::*; 54 /// verify_that!(vec![1, 2], {eq(&2), eq(&1)}) 55 /// # .unwrap(); 56 /// ``` 57 /// 58 /// Note: This behavior is only possible in [`verify_that!`] macros. In any 59 /// other cases, it is still necessary to use the 60 /// [`unordered_elements_are!`][crate::matchers::unordered_elements_are] macro. 61 /// 62 /// ```compile_fail 63 /// # use googletest::prelude::*; 64 /// verify_that!(vec![vec![1,2], vec![3]], {{eq(2), eq(1)}, {eq(3)}}) 65 /// # .unwrap(); 66 /// ``` 67 /// 68 /// Use this instead: 69 /// ``` 70 /// # use googletest::prelude::*; 71 /// verify_that!(vec![vec![1,2], vec![3]], 72 /// {unordered_elements_are![eq(&2), eq(&1)], unordered_elements_are![eq(&3)]}) 73 /// # .unwrap(); 74 /// ``` 75 /// 76 /// If an inner matcher is `eq(...)`, it can be omitted: 77 /// 78 /// ``` 79 /// # use googletest::prelude::*; 80 /// 81 /// verify_that!(vec![1,2,3], unordered_elements_are![lt(&2), gt(&1), &3]) 82 /// # .unwrap(); 83 /// ``` 84 /// 85 /// The matcher proceeds in three stages: 86 /// 87 /// 1. It first checks whether the actual value is of the right size to possibly 88 /// be matched by each of the given matchers. If not, then it immediately 89 /// fails explaining that the size is incorrect. 90 /// 91 /// 2. It then checks whether each matcher matches at least one corresponding 92 /// element in the actual container and each element in the actual container 93 /// is matched by at least one matcher. If not, it fails with a message 94 /// indicating which matcher respectively container elements had no 95 /// counterparts. 96 /// 97 /// 3. Finally, it checks whether the mapping of matchers to corresponding 98 /// actual elements is a 1-1 correspondence and fails if that is not the 99 /// case. The failure message then shows the best matching it could find, 100 /// including which matchers did not have corresponding unique elements in 101 /// the container and which container elements had no corresponding matchers. 102 /// 103 /// [`IntoIterator`]: std::iter::IntoIterator 104 /// [`Iterator`]: std::iter::Iterator 105 /// [`Iterator::collect`]: std::iter::Iterator::collect 106 /// [`Vec`]: std::vec::Vec 107 #[macro_export] 108 #[doc(hidden)] 109 macro_rules! __unordered_elements_are { 110 ($(,)?) => {{ 111 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 112 UnorderedElementsAreMatcher::new( 113 [], 114 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 115 Requirements::PerfectMatch) 116 }}; 117 118 ($($matcher:expr),* $(,)?) => {{ 119 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 120 UnorderedElementsAreMatcher::new( 121 [$(Box::new( 122 $crate::matcher_support::__internal_unstable_do_not_depend_on_these::auto_eq!( 123 $matcher 124 ) 125 )),*], 126 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 127 Requirements::PerfectMatch) 128 }}; 129 } 130 131 /// Matches a container containing elements matched by the given matchers. 132 /// 133 /// To match, each given matcher must have a corresponding element in the 134 /// container which it matches. There must be a mapping uniquely matching each 135 /// matcher to a container element. The container can, however, contain 136 /// additional elements that don't correspond to any matcher. 137 /// 138 /// Put another way, `contains_each!` matches if there is a subset of the actual 139 /// container which 140 /// [`unordered_elements_are`][crate::matchers::unordered_elements_are] would 141 /// match. 142 /// 143 /// ``` 144 /// # use googletest::prelude::*; 145 /// # fn should_pass() -> Result<()> { 146 /// verify_that!(vec![3, 2, 1], contains_each![eq(&2), ge(&3)])?; // Passes 147 /// verify_that!(vec![3, 2, 1], contains_each![ge(&2), ge(&2)])?; // Passes 148 /// # Ok(()) 149 /// # } 150 /// # fn should_fail_1() -> Result<()> { 151 /// verify_that!(vec![1], contains_each![eq(&1), ge(&2)])?; // Fails: container too small 152 /// # Ok(()) 153 /// # } 154 /// # fn should_fail_2() -> Result<()> { 155 /// verify_that!(vec![3, 2, 1], contains_each![eq(&1), ge(&4)])?; // Fails: second matcher unmatched 156 /// # Ok(()) 157 /// # } 158 /// # fn should_fail_3() -> Result<()> { 159 /// verify_that!(vec![3, 2, 1], contains_each![ge(&3), ge(&3), ge(&3)])?; // Fails: no matching 160 /// # Ok(()) 161 /// # } 162 /// # should_pass().unwrap(); 163 /// # should_fail_1().unwrap_err(); 164 /// # should_fail_2().unwrap_err(); 165 /// # should_fail_3().unwrap_err(); 166 /// ``` 167 /// 168 /// The actual value must be a container such as a `&Vec`, an array, or a 169 /// slice. More precisely, the actual value must implement [`IntoIterator`]. 170 /// 171 /// If an inner matcher is `eq(...)`, it can be omitted: 172 /// 173 /// ``` 174 /// # use googletest::prelude::*; 175 /// 176 /// verify_that!(vec![1,2,3], contains_each![lt(&2), &3]) 177 /// # .unwrap(); 178 /// ``` 179 /// 180 /// The matcher proceeds in three stages: 181 /// 182 /// 1. It first checks whether the actual value is large enough to possibly be 183 /// matched by each of the given matchers. If not, then it immediately fails 184 /// explaining that the size is too small. 185 /// 186 /// 2. It then checks whether each matcher matches at least one corresponding 187 /// element in the actual container and fails if that is not the case. The 188 /// failure message indicates which matcher had no corresponding element. 189 /// 190 /// 3. Finally, it checks whether the mapping of matchers to corresponding 191 /// actual elements is 1-1 and fails if that is not the case. The failure 192 /// message then shows the best matching it could find, including which 193 /// matchers did not have corresponding unique elements in the container. 194 /// 195 /// [`IntoIterator`]: std::iter::IntoIterator 196 /// [`Iterator`]: std::iter::Iterator 197 /// [`Iterator::collect`]: std::iter::Iterator::collect 198 /// [`Vec`]: std::vec::Vec 199 #[macro_export] 200 #[doc(hidden)] 201 macro_rules! __contains_each { 202 ($(,)?) => {{ 203 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 204 UnorderedElementsAreMatcher::new( 205 [], 206 $crate::matchers::__internal_unstable_do_not_depend_on_these::Requirements::Superset) 207 }}; 208 209 ($($matcher:expr),* $(,)?) => {{ 210 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 211 UnorderedElementsAreMatcher::new( 212 [$(Box::new( 213 $crate::matcher_support::__internal_unstable_do_not_depend_on_these::auto_eq!( 214 $matcher 215 ) 216 )),*], 217 $crate::matchers::__internal_unstable_do_not_depend_on_these::Requirements::Superset) 218 }} 219 } 220 221 /// Matches a container all of whose elements are matched by the given matchers. 222 /// 223 /// To match, each element in the container must have a corresponding matcher 224 /// which matches it. There must be a 1-1 mapping from container elements to 225 /// matchers, so that no matcher has more than one corresponding element. 226 /// 227 /// There may, however, be matchers not corresponding to any elements in the 228 /// container. 229 /// 230 /// Put another way, `is_contained_in!` matches if there is a subset of the 231 /// matchers which would match with 232 /// [`unordered_elements_are`][crate::matchers::unordered_elements_are]. 233 /// 234 /// ``` 235 /// # use googletest::prelude::*; 236 /// # fn should_pass() -> Result<()> { 237 /// verify_that!(vec![2, 1], is_contained_in![eq(&1), ge(&2)])?; // Passes 238 /// verify_that!(vec![2, 1], is_contained_in![ge(&1), ge(&1)])?; // Passes 239 /// # Ok(()) 240 /// # } 241 /// # fn should_fail_1() -> Result<()> { 242 /// verify_that!(vec![1, 2, 3], is_contained_in![eq(&1), ge(&2)])?; // Fails: container too large 243 /// # Ok(()) 244 /// # } 245 /// # fn should_fail_2() -> Result<()> { 246 /// verify_that!(vec![2, 1], is_contained_in![eq(&1), ge(&4)])?; // Fails: second matcher unmatched 247 /// # Ok(()) 248 /// # } 249 /// # fn should_fail_3() -> Result<()> { 250 /// verify_that!(vec![3, 1], is_contained_in![ge(&3), ge(&3), ge(&3)])?; // Fails: no matching 251 /// # Ok(()) 252 /// # } 253 /// # should_pass().unwrap(); 254 /// # should_fail_1().unwrap_err(); 255 /// # should_fail_2().unwrap_err(); 256 /// # should_fail_3().unwrap_err(); 257 /// ``` 258 /// 259 /// The actual value must be a container such as a `&Vec`, an array, or a slice. 260 /// More precisely, the actual value must implement [`IntoIterator`]. 261 /// 262 /// If an inner matcher is `eq(...)`, it can be omitted: 263 /// 264 /// ``` 265 /// # use googletest::prelude::*; 266 /// 267 /// verify_that!(vec![1,2,3], is_contained_in![lt(&2), &3, &4, gt(&0)]) 268 /// # .unwrap(); 269 /// ``` 270 /// 271 /// The matcher proceeds in three stages: 272 /// 273 /// 1. It first checks whether the actual value is too large to possibly be 274 /// matched by each of the given matchers. If so, it immediately fails 275 /// explaining that the size is too large. 276 /// 277 /// 2. It then checks whether each actual container element is matched by at 278 /// least one matcher and fails if that is not the case. The failure message 279 /// indicates which element had no corresponding matcher. 280 /// 281 /// 3. Finally, it checks whether the mapping of elements to corresponding 282 /// matchers is 1-1 and fails if that is not the case. The failure message 283 /// then shows the best matching it could find, including which container 284 /// elements did not have corresponding matchers. 285 /// 286 /// [`IntoIterator`]: std::iter::IntoIterator 287 /// [`Iterator`]: std::iter::Iterator 288 /// [`Iterator::collect`]: std::iter::Iterator::collect 289 /// [`Vec`]: std::vec::Vec 290 #[macro_export] 291 #[doc(hidden)] 292 macro_rules! __is_contained_in { 293 ($(,)?) => {{ 294 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 295 UnorderedElementsAreMatcher::new( 296 [], $crate::matchers::__internal_unstable_do_not_depend_on_these::Requirements::Subset) 297 }}; 298 299 ($($matcher:expr),* $(,)?) => {{ 300 $crate::matchers::__internal_unstable_do_not_depend_on_these:: 301 UnorderedElementsAreMatcher::new( 302 [$(Box::new( 303 $crate::matcher_support::__internal_unstable_do_not_depend_on_these::auto_eq!( 304 $matcher 305 ) 306 )),*], 307 $crate::matchers::__internal_unstable_do_not_depend_on_these::Requirements::Subset) 308 }} 309 } 310 311 /// Module for use only by the macros in this module. 312 /// 313 /// **For internal use only. API stablility is not guaranteed!** 314 #[doc(hidden)] 315 pub mod internal { 316 use crate::description::Description; 317 use crate::matcher::{Matcher, MatcherBase, MatcherResult}; 318 use crate::matcher_support::count_elements::count_elements; 319 use std::collections::HashSet; 320 use std::fmt::{Debug, Display}; 321 322 /// This struct is meant to be used only through the 323 /// `unordered_elements_are![...]` macro. 324 /// 325 /// **For internal use only. API stablility is not guaranteed!** 326 #[doc(hidden)] 327 #[derive(MatcherBase)] 328 pub struct UnorderedElementsAreMatcher<'a, T: Debug + Copy, const N: usize> { 329 elements: [Box<dyn Matcher<T> + 'a>; N], 330 requirements: Requirements, 331 } 332 333 impl<'a, T: Debug + Copy, const N: usize> UnorderedElementsAreMatcher<'a, T, N> { new(elements: [Box<dyn Matcher<T> + 'a>; N], requirements: Requirements) -> Self334 pub fn new(elements: [Box<dyn Matcher<T> + 'a>; N], requirements: Requirements) -> Self { 335 Self { elements, requirements } 336 } 337 } 338 339 // This matcher performs the checks in three different steps in both `matches` 340 // and `explain_match`. This is useful for performance but also to produce 341 // an actionable error message. 342 // 1. `UnorderedElementsAreMatcher` verifies that both collections have the same 343 // size 344 // 2. `UnorderedElementsAreMatcher` verifies that each actual element matches at 345 // least one expected element and vice versa. 346 // 3. `UnorderedElementsAreMatcher` verifies that a perfect matching exists 347 // using Ford-Fulkerson. 348 impl<'a, T: Debug + Copy, ContainerT: Debug + Copy, const N: usize> Matcher<ContainerT> 349 for UnorderedElementsAreMatcher<'a, T, N> 350 where 351 ContainerT: IntoIterator<Item = T>, 352 { matches(&self, actual: ContainerT) -> MatcherResult353 fn matches(&self, actual: ContainerT) -> MatcherResult { 354 let match_matrix = MatchMatrix::generate(actual, &self.elements); 355 match_matrix.is_match_for(self.requirements).into() 356 } 357 explain_match(&self, actual: ContainerT) -> Description358 fn explain_match(&self, actual: ContainerT) -> Description { 359 if let Some(size_mismatch_explanation) = 360 self.requirements.explain_size_mismatch(actual, N) 361 { 362 return size_mismatch_explanation; 363 } 364 365 let match_matrix = MatchMatrix::generate(actual, &self.elements); 366 if let Some(unmatchable_explanation) = 367 match_matrix.explain_unmatchable(self.requirements) 368 { 369 return unmatchable_explanation; 370 } 371 372 let best_match = match_matrix.find_best_match(); 373 best_match 374 .get_explanation(actual, &self.elements, self.requirements) 375 .unwrap_or("whose elements all match".into()) 376 } 377 describe(&self, matcher_result: MatcherResult) -> Description378 fn describe(&self, matcher_result: MatcherResult) -> Description { 379 format!( 380 "{} elements matching in any order:\n{}", 381 if matcher_result.into() { "contains" } else { "doesn't contain" }, 382 self.elements 383 .iter() 384 .map(|matcher| matcher.describe(MatcherResult::Match)) 385 .collect::<Description>() 386 .enumerate() 387 .indent() 388 ) 389 .into() 390 } 391 } 392 393 /// The requirements of the mapping between matchers and actual values by 394 /// which [`UnorderedElementsAre`] is deemed to match its input. 395 /// 396 /// **For internal use only. API stablility is not guaranteed!** 397 #[doc(hidden)] 398 #[derive(Clone, Copy)] 399 pub enum Requirements { 400 /// There must be a 1:1 correspondence between the actual values and the 401 /// matchers. 402 PerfectMatch, 403 404 /// The mapping from matched actual values to their corresponding 405 /// matchers must be surjective. 406 Superset, 407 408 /// The mapping from matchers to matched actual values must be 409 /// surjective. 410 Subset, 411 } 412 413 impl Requirements { explain_size_mismatch<ContainerT: IntoIterator + Copy>( &self, actual: ContainerT, expected_size: usize, ) -> Option<Description>414 fn explain_size_mismatch<ContainerT: IntoIterator + Copy>( 415 &self, 416 actual: ContainerT, 417 expected_size: usize, 418 ) -> Option<Description> { 419 let actual_size = count_elements(actual); 420 match self { 421 Requirements::PerfectMatch if actual_size != expected_size => Some( 422 format!("which has size {} (expected {})", actual_size, expected_size).into(), 423 ), 424 425 Requirements::Superset if actual_size < expected_size => Some( 426 format!("which has size {} (expected at least {})", actual_size, expected_size) 427 .into(), 428 ), 429 430 Requirements::Subset if actual_size > expected_size => Some( 431 format!("which has size {} (expected at most {})", actual_size, expected_size) 432 .into(), 433 ), 434 435 _ => None, 436 } 437 } 438 } 439 440 impl Display for Requirements { fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result441 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 442 match self { 443 Requirements::PerfectMatch => { 444 write!(f, "perfect") 445 } 446 Requirements::Superset => { 447 write!(f, "superset") 448 } 449 Requirements::Subset => { 450 write!(f, "subset") 451 } 452 } 453 } 454 } 455 456 /// The bipartite matching graph between actual and expected elements. 457 struct MatchMatrix<const N: usize>(Vec<[MatcherResult; N]>); 458 459 impl<const N: usize> MatchMatrix<N> { generate<'a, T: Debug + Copy + 'a, ContainerT: Debug + Copy + IntoIterator<Item = T>>( actual: ContainerT, expected: &[Box<dyn Matcher<T> + 'a>; N], ) -> Self460 fn generate<'a, T: Debug + Copy + 'a, ContainerT: Debug + Copy + IntoIterator<Item = T>>( 461 actual: ContainerT, 462 expected: &[Box<dyn Matcher<T> + 'a>; N], 463 ) -> Self { 464 let mut matrix = MatchMatrix(vec![[MatcherResult::NoMatch; N]; count_elements(actual)]); 465 for (actual_idx, actual) in actual.into_iter().enumerate() { 466 for (expected_idx, expected) in expected.iter().enumerate() { 467 matrix.0[actual_idx][expected_idx] = expected.matches(actual); 468 } 469 } 470 matrix 471 } 472 is_match_for(&self, requirements: Requirements) -> bool473 fn is_match_for(&self, requirements: Requirements) -> bool { 474 match requirements { 475 Requirements::PerfectMatch => { 476 !self.find_unmatchable_elements().has_unmatchable_elements() 477 && self.find_best_match().is_full_match() 478 } 479 Requirements::Superset => { 480 !self.find_unmatched_expected().has_unmatchable_elements() 481 && self.find_best_match().is_superset_match() 482 } 483 Requirements::Subset => { 484 !self.find_unmatched_actual().has_unmatchable_elements() 485 && self.find_best_match().is_subset_match() 486 } 487 } 488 } 489 explain_unmatchable(&self, requirements: Requirements) -> Option<Description>490 fn explain_unmatchable(&self, requirements: Requirements) -> Option<Description> { 491 let unmatchable_elements = match requirements { 492 Requirements::PerfectMatch => self.find_unmatchable_elements(), 493 Requirements::Superset => self.find_unmatched_expected(), 494 Requirements::Subset => self.find_unmatched_actual(), 495 }; 496 unmatchable_elements.get_explanation() 497 } 498 499 // Verifies that each actual matches at least one expected and that 500 // each expected matches at least one actual. 501 // This is a necessary condition but not sufficient. But it is faster 502 // than `find_best_match()`. find_unmatchable_elements(&self) -> UnmatchableElements<N>503 fn find_unmatchable_elements(&self) -> UnmatchableElements<N> { 504 let unmatchable_actual = 505 self.0.iter().map(|row| row.iter().all(|&e| e.is_no_match())).collect(); 506 let mut unmatchable_expected = [false; N]; 507 for (col_idx, expected) in unmatchable_expected.iter_mut().enumerate() { 508 *expected = self.0.iter().map(|row| row[col_idx]).all(|e| e.is_no_match()); 509 } 510 UnmatchableElements { unmatchable_actual, unmatchable_expected } 511 } 512 find_unmatched_expected(&self) -> UnmatchableElements<N>513 fn find_unmatched_expected(&self) -> UnmatchableElements<N> { 514 let mut unmatchable_expected = [false; N]; 515 for (col_idx, expected) in unmatchable_expected.iter_mut().enumerate() { 516 *expected = self.0.iter().map(|row| row[col_idx]).all(|e| e.is_no_match()); 517 } 518 UnmatchableElements { unmatchable_actual: vec![false; N], unmatchable_expected } 519 } 520 find_unmatched_actual(&self) -> UnmatchableElements<N>521 fn find_unmatched_actual(&self) -> UnmatchableElements<N> { 522 let unmatchable_actual = 523 self.0.iter().map(|row| row.iter().all(|e| e.is_no_match())).collect(); 524 UnmatchableElements { unmatchable_actual, unmatchable_expected: [false; N] } 525 } 526 527 // Verifies that a full match exists. 528 // 529 // Uses the well-known Ford-Fulkerson max flow method to find a maximum 530 // bipartite matching. Flow is considered to be from actual to expected. 531 // There is an implicit source node that is connected to all of the actual 532 // nodes, and an implicit sink node that is connected to all of the 533 // expected nodes. All edges have unit capacity. 534 // 535 // Neither the flow graph nor the residual flow graph are represented 536 // explicitly. Instead, they are implied by the information in `self.0` and 537 // the local `actual_match : [Option<usize>; N]` whose elements are initialized 538 // to `None`. This represents the initial state of the algorithm, 539 // where the flow graph is empty, and the residual flow graph has the 540 // following edges: 541 // - An edge from source to each actual element node 542 // - An edge from each expected element node to sink 543 // - An edge from each actual element node to each expected element node, if 544 // the actual element matches the expected element, i.e. 545 // `matches!(self.0[actual_id][expected_id], Matches)` 546 // 547 // When the `try_augment(...)` method adds a flow, it sets `actual_match[l] = 548 // Some(r)` for some nodes l and r. This induces the following changes: 549 // - The edges (source, l), (l, r), and (r, sink) are added to the flow graph. 550 // - The same three edges are removed from the residual flow graph. 551 // - The reverse edges (l, source), (r, l), and (sink, r) are added to the 552 // residual flow graph, which is a directional graph representing unused 553 // flow capacity. 554 // 555 // When the method augments a flow (changing `actual_match[l]` from `Some(r1)` 556 // to `Some(r2)`), this can be thought of as "undoing" the above steps 557 // with respect to r1 and "redoing" them with respect to r2. 558 // 559 // It bears repeating that the flow graph and residual flow graph are 560 // never represented explicitly, but can be derived by looking at the 561 // information in 'self.0' and in `actual_match`. 562 // 563 // As an optimization, there is a second local `expected_match: [Option<usize>; 564 // N]` which does not provide any new information. Instead, it enables 565 // more efficient queries about edges entering or leaving the expected elements 566 // nodes of the flow or residual flow graphs. The following invariants 567 // are maintained: 568 // 569 // actual_match[a] == None or expected_match[actual_match[a].unwrap()] == 570 // Some(a) 571 // expected_match[r] == None or actual_match[expected_match[e].unwrap()] == 572 // Some(e) 573 // 574 // | [ source ] | 575 // | ||| | 576 // | ||| | 577 // | ||\-> actual_match[0]=Some(1) -\ expected_match[0]=None ---\ | 578 // | || | | | 579 // | |\--> actual_match[1]=None \-> expected_match[1]=Some(0) --\| | 580 // | | || | 581 // | \---> actual_match[2]=Some(2) --> expected_match[2]=Some(2) -\|| | 582 // | ||| | 583 // | elements matchers vvv | 584 // | [ sink ] | 585 // 586 // See Also: 587 // [1] Cormen, et al (2001). "Section 26.2: The Ford-Fulkerson method". 588 // "Introduction to Algorithms (Second ed.)", pp. 651-664. 589 // [2] "Ford-Fulkerson algorithm", Wikipedia, 590 // 'http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm' find_best_match(&self) -> BestMatch<N>591 fn find_best_match(&self) -> BestMatch<N> { 592 let mut actual_match = vec![None; self.0.len()]; 593 let mut expected_match: [Option<usize>; N] = [None; N]; 594 // Searches the residual flow graph for a path from each actual node to 595 // the sink in the residual flow graph, and if one is found, add this path 596 // to the graph. 597 // It's okay to search through the actual nodes once. The 598 // edge from the implicit source node to each previously-visited actual 599 // node will have flow if that actual node has any path to the sink 600 // whatsoever. Subsequent augmentations can only add flow to the 601 // network, and cannot take away that previous flow unit from the source. 602 // Since the source-to-actual edge can only carry one flow unit (or, 603 // each actual element can be matched to only one expected element), there is no 604 // need to visit the actual nodes more than once looking for 605 // augmented paths. The flow is known to be possible or impossible 606 // by looking at the node once. 607 for actual_idx in 0..self.0.len() { 608 assert!(actual_match[actual_idx].is_none()); 609 let mut seen = [false; N]; 610 self.try_augment(actual_idx, &mut seen, &mut actual_match, &mut expected_match); 611 } 612 BestMatch(actual_match) 613 } 614 615 // Perform a depth-first search from actual node `actual_idx` to the sink by 616 // searching for an unassigned expected node. If a path is found, flow 617 // is added to the network by linking the actual and expected vector elements 618 // corresponding each segment of the path. Returns true if a path to 619 // sink was found, which means that a unit of flow was added to the 620 // network. The 'seen' array elements correspond to expected nodes and are 621 // marked to eliminate cycles from the search. 622 // 623 // Actual nodes will only be explored at most once because they 624 // are accessible from at most one expected node in the residual flow 625 // graph. 626 // 627 // Note that `actual_match[actual_idx]` is the only element of `actual_match` 628 // that `try_augment(...)` will potentially transition from `None` to 629 // `Some(...)`. Any other `actual_match` element holding `None` before 630 // `try_augment(...)` will be holding it when `try_augment(...)` 631 // returns. 632 // try_augment( &self, actual_idx: usize, seen: &mut [bool; N], actual_match: &mut [Option<usize>], expected_match: &mut [Option<usize>; N], ) -> bool633 fn try_augment( 634 &self, 635 actual_idx: usize, 636 seen: &mut [bool; N], 637 actual_match: &mut [Option<usize>], 638 expected_match: &mut [Option<usize>; N], 639 ) -> bool { 640 for expected_idx in 0..N { 641 if seen[expected_idx] { 642 continue; 643 } 644 if self.0[actual_idx][expected_idx].is_no_match() { 645 continue; 646 } 647 // There is an edge between `actual_idx` and `expected_idx`. 648 seen[expected_idx] = true; 649 // Next a search is performed to determine whether 650 // this edge is a dead end or leads to the sink. 651 // 652 // `expected_match[expected_idx].is_none()` means that there is residual flow 653 // from expected node at index expected_idx to the sink, so we 654 // can use that to finish this flow path and return success. 655 // 656 // Otherwise, we look for a residual flow starting from 657 // `expected_match[expected_idx].unwrap()` by calling 658 // ourselves recursively to see if this ultimately leads to 659 // sink. 660 if expected_match[expected_idx].is_none() 661 || self.try_augment( 662 expected_match[expected_idx].unwrap(), 663 seen, 664 actual_match, 665 expected_match, 666 ) 667 { 668 // We found a residual flow from source to sink. We thus need to add the new 669 // edge to the current flow. 670 // Note: this also remove the potential flow that existed by overwriting the 671 // value in the `expected_match` and `actual_match`. 672 expected_match[expected_idx] = Some(actual_idx); 673 actual_match[actual_idx] = Some(expected_idx); 674 return true; 675 } 676 } 677 false 678 } 679 } 680 681 /// The list of elements that do not match any element in the corresponding 682 /// set. 683 /// These lists are represented as fixed sized bit set to avoid 684 /// allocation. 685 /// TODO(bjacotg) Use BitArr!(for N) once generic_const_exprs is stable. 686 struct UnmatchableElements<const N: usize> { 687 unmatchable_actual: Vec<bool>, 688 unmatchable_expected: [bool; N], 689 } 690 691 impl<const N: usize> UnmatchableElements<N> { has_unmatchable_elements(&self) -> bool692 fn has_unmatchable_elements(&self) -> bool { 693 self.unmatchable_actual.iter().any(|b| *b) 694 || self.unmatchable_expected.iter().any(|b| *b) 695 } 696 get_explanation(&self) -> Option<Description>697 fn get_explanation(&self) -> Option<Description> { 698 let unmatchable_actual = self.unmatchable_actual(); 699 let actual_idx = unmatchable_actual 700 .iter() 701 .map(|idx| format!("#{}", idx)) 702 .collect::<Vec<_>>() 703 .join(", "); 704 let unmatchable_expected = self.unmatchable_expected(); 705 let expected_idx = unmatchable_expected 706 .iter() 707 .map(|idx| format!("#{}", idx)) 708 .collect::<Vec<_>>() 709 .join(", "); 710 match (unmatchable_actual.len(), unmatchable_expected.len()) { 711 (0, 0) => None, 712 (1, 0) => { 713 Some(format!("whose element {actual_idx} does not match any expected elements").into()) 714 } 715 (_, 0) => { 716 Some(format!("whose elements {actual_idx} do not match any expected elements",).into()) 717 } 718 (0, 1) => Some(format!( 719 "which has no element matching the expected element {expected_idx}" 720 ).into()), 721 (0, _) => Some(format!( 722 "which has no elements matching the expected elements {expected_idx}" 723 ).into()), 724 (1, 1) => Some(format!( 725 "whose element {actual_idx} does not match any expected elements and no elements match the expected element {expected_idx}" 726 ).into()), 727 (_, 1) => Some(format!( 728 "whose elements {actual_idx} do not match any expected elements and no elements match the expected element {expected_idx}" 729 ).into()), 730 (1, _) => Some(format!( 731 "whose element {actual_idx} does not match any expected elements and no elements match the expected elements {expected_idx}" 732 ).into()), 733 (_, _) => Some(format!( 734 "whose elements {actual_idx} do not match any expected elements and no elements match the expected elements {expected_idx}" 735 ).into()), 736 } 737 } 738 unmatchable_actual(&self) -> Vec<usize>739 fn unmatchable_actual(&self) -> Vec<usize> { 740 self.unmatchable_actual 741 .iter() 742 .enumerate() 743 .filter_map(|(idx, b)| if *b { Some(idx) } else { None }) 744 .collect() 745 } 746 unmatchable_expected(&self) -> Vec<usize>747 fn unmatchable_expected(&self) -> Vec<usize> { 748 self.unmatchable_expected 749 .iter() 750 .enumerate() 751 .filter_map(|(idx, b)| if *b { Some(idx) } else { None }) 752 .collect() 753 } 754 } 755 756 /// The representation of a match between actual and expected. 757 /// The value at idx represents to which expected the actual at idx is 758 /// matched with. For example, `BestMatch([Some(0), None, Some(1)])` 759 /// means: 760 /// * The 0th element in actual matches the 0th element in expected. 761 /// * The 1st element in actual does not match. 762 /// * The 2nd element in actual matches the 1st element in expected. 763 struct BestMatch<const N: usize>(Vec<Option<usize>>); 764 765 impl<const N: usize> BestMatch<N> { is_full_match(&self) -> bool766 fn is_full_match(&self) -> bool { 767 self.0.iter().all(|o| o.is_some()) 768 } 769 is_subset_match(&self) -> bool770 fn is_subset_match(&self) -> bool { 771 self.is_full_match() 772 } 773 is_superset_match(&self) -> bool774 fn is_superset_match(&self) -> bool { 775 self.get_unmatched_expected().is_empty() 776 } 777 get_matches(&self) -> impl Iterator<Item = (usize, usize)> + '_778 fn get_matches(&self) -> impl Iterator<Item = (usize, usize)> + '_ { 779 self.0.iter().enumerate().filter_map(|(actual_idx, maybe_expected_idx)| { 780 maybe_expected_idx.map(|expected_idx| (actual_idx, expected_idx)) 781 }) 782 } 783 get_unmatched_actual(&self) -> impl Iterator<Item = usize> + '_784 fn get_unmatched_actual(&self) -> impl Iterator<Item = usize> + '_ { 785 self.0 786 .iter() 787 .enumerate() 788 .filter(|&(_, o)| o.is_none()) 789 .map(|(actual_idx, _)| actual_idx) 790 } 791 get_unmatched_expected(&self) -> Vec<usize>792 fn get_unmatched_expected(&self) -> Vec<usize> { 793 let matched_expected: HashSet<_> = self.0.iter().flatten().collect(); 794 (0..N).filter(|expected_idx| !matched_expected.contains(expected_idx)).collect() 795 } 796 get_explanation< 'a, T: Debug + Copy, ContainerT: Debug + Copy + IntoIterator<Item = T>, >( &self, actual: ContainerT, expected: &[Box<dyn Matcher<T> + 'a>; N], requirements: Requirements, ) -> Option<Description>797 fn get_explanation< 798 'a, 799 T: Debug + Copy, 800 ContainerT: Debug + Copy + IntoIterator<Item = T>, 801 >( 802 &self, 803 actual: ContainerT, 804 expected: &[Box<dyn Matcher<T> + 'a>; N], 805 requirements: Requirements, 806 ) -> Option<Description> { 807 let actual: Vec<_> = actual.into_iter().collect(); 808 if self.is_full_match() { 809 return None; 810 } 811 let mut error_message = 812 format!("which does not have a {requirements} match with the expected elements."); 813 814 error_message.push_str("\n The best match found was: "); 815 816 let matches = self.get_matches().map(|(actual_idx, expected_idx)|{ 817 format!( 818 "Actual element {:?} at index {actual_idx} matched expected element `{}` at index {expected_idx}.", 819 actual[actual_idx], 820 expected[expected_idx].describe(MatcherResult::Match), 821 )}); 822 823 let unmatched_actual = self.get_unmatched_actual().map(|actual_idx| { 824 format!( 825 "Actual element {:#?} at index {actual_idx} did not match any remaining expected element.", 826 actual[actual_idx] 827 ) 828 }); 829 830 let unmatched_expected = self.get_unmatched_expected().into_iter().map(|expected_idx|{format!( 831 "Expected element `{}` at index {expected_idx} did not match any remaining actual element.", 832 expected[expected_idx].describe(MatcherResult::Match) 833 )}); 834 835 let best_match = matches 836 .chain(unmatched_actual) 837 .chain(unmatched_expected) 838 .collect::<Description>() 839 .indent(); 840 Some(format!( 841 "which does not have a {requirements} match with the expected elements. The best match found was:\n{best_match}" 842 ).into()) 843 } 844 } 845 } 846 847 #[cfg(test)] 848 mod tests { 849 use crate::matcher::MatcherResult; 850 use crate::prelude::*; 851 use indoc::indoc; 852 use std::collections::HashMap; 853 854 #[test] has_correct_description_for_map() -> Result<()>855 fn has_correct_description_for_map() -> Result<()> { 856 // UnorderedElementsAreMatcher maintains references to the matchers, so the 857 // constituent matchers must live longer. Inside a verify_that! macro, the 858 // compiler takes care of that, but when the matcher is created separately, 859 // we must create the constitute matchers separately so that they 860 // aren't dropped too early. 861 let matchers = ((eq(&2), eq(&"Two")), (eq(&1), eq(&"One")), (eq(&3), eq(&"Three"))); 862 let matcher = unordered_elements_are![ 863 (matchers.0 .0, matchers.0 .1), 864 (matchers.1 .0, matchers.1 .1), 865 (matchers.2 .0, matchers.2 .1) 866 ]; 867 verify_that!( 868 Matcher::<&HashMap<i32, String>>::describe(&matcher, MatcherResult::Match), 869 displays_as(eq(indoc!( 870 " 871 contains elements matching in any order: 872 0. is a tuple whose values respectively match: 873 is equal to 2 874 is equal to \"Two\" 875 1. is a tuple whose values respectively match: 876 is equal to 1 877 is equal to \"One\" 878 2. is a tuple whose values respectively match: 879 is equal to 3 880 is equal to \"Three\"" 881 ))) 882 ) 883 } 884 885 #[test] unordered_elements_are_description_no_full_match_with_map() -> Result<()>886 fn unordered_elements_are_description_no_full_match_with_map() -> Result<()> { 887 // UnorderedElementsAreMatcher maintains references to the matchers, so the 888 // constituent matchers must live longer. Inside a verify_that! macro, the 889 // compiler takes care of that, but when the matcher is created separately, 890 // we must create the constitute matchers separately so that they 891 // aren't dropped too early. 892 let value: HashMap<u32, u32> = HashMap::from_iter([(0, 1), (1, 1), (2, 2)]); 893 let matchers = ((anything(), eq(&1)), (anything(), eq(&2)), (anything(), eq(&2))); 894 let matcher = unordered_elements_are![ 895 (matchers.0 .0, matchers.0 .1), 896 (matchers.1 .0, matchers.1 .1), 897 (matchers.2 .0, matchers.2 .1), 898 ]; 899 verify_that!( 900 matcher.explain_match(&value), 901 all![ 902 displays_as(contains_regex( 903 "Actual element \\(2, 2\\) at index [0-2] matched expected element `is a tuple whose values respectively match:\n is anything\n is equal to 2` at index [0-2]." 904 )), 905 displays_as(contains_regex( 906 "Actual element \\(\n [0-1],\n [0-1],\n \\) at index [0-2] did not match any remaining expected element." 907 )), 908 displays_as(contains_substring( 909 "Expected element `is a tuple whose values respectively match:\n is anything\n is equal to 2` at index 2 did not match any remaining actual element." 910 )) 911 ] 912 ) 913 } 914 } 915