1 // ancestors.rs 2 // 3 // Copyright 2018 Georges Racinet <gracinet@anybox.fr> 4 // 5 // This software may be used and distributed according to the terms of the 6 // GNU General Public License version 2 or any later version. 7 8 //! Rust versions of generic DAG ancestors algorithms for Mercurial 9 10 use super::{Graph, GraphError, Revision, NULL_REVISION}; 11 use crate::dagops; 12 use std::cmp::max; 13 use std::collections::{BinaryHeap, HashSet}; 14 15 /// Iterator over the ancestors of a given list of revisions 16 /// This is a generic type, defined and implemented for any Graph, so that 17 /// it's easy to 18 /// 19 /// - unit test in pure Rust 20 /// - bind to main Mercurial code, potentially in several ways and have these 21 /// bindings evolve over time 22 pub struct AncestorsIterator<G: Graph> { 23 graph: G, 24 visit: BinaryHeap<Revision>, 25 seen: HashSet<Revision>, 26 stoprev: Revision, 27 } 28 29 /// Lazy ancestors set, backed by AncestorsIterator 30 pub struct LazyAncestors<G: Graph + Clone> { 31 graph: G, 32 containsiter: AncestorsIterator<G>, 33 initrevs: Vec<Revision>, 34 stoprev: Revision, 35 inclusive: bool, 36 } 37 38 pub struct MissingAncestors<G: Graph> { 39 graph: G, 40 bases: HashSet<Revision>, 41 max_base: Revision, 42 } 43 44 impl<G: Graph> AncestorsIterator<G> { 45 /// Constructor. 46 /// 47 /// if `inclusive` is true, then the init revisions are emitted in 48 /// particular, otherwise iteration starts from their parents. new( graph: G, initrevs: impl IntoIterator<Item = Revision>, stoprev: Revision, inclusive: bool, ) -> Result<Self, GraphError>49 pub fn new( 50 graph: G, 51 initrevs: impl IntoIterator<Item = Revision>, 52 stoprev: Revision, 53 inclusive: bool, 54 ) -> Result<Self, GraphError> { 55 let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); 56 if inclusive { 57 let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); 58 let seen = visit.iter().cloned().collect(); 59 return Ok(AncestorsIterator { 60 visit, 61 seen, 62 stoprev, 63 graph, 64 }); 65 } 66 let mut this = AncestorsIterator { 67 visit: BinaryHeap::new(), 68 seen: HashSet::new(), 69 stoprev, 70 graph, 71 }; 72 this.seen.insert(NULL_REVISION); 73 for rev in filtered_initrevs { 74 for parent in this.graph.parents(rev)?.iter().cloned() { 75 this.conditionally_push_rev(parent); 76 } 77 } 78 Ok(this) 79 } 80 81 #[inline] conditionally_push_rev(&mut self, rev: Revision)82 fn conditionally_push_rev(&mut self, rev: Revision) { 83 if self.stoprev <= rev && self.seen.insert(rev) { 84 self.visit.push(rev); 85 } 86 } 87 88 /// Consumes partially the iterator to tell if the given target 89 /// revision 90 /// is in the ancestors it emits. 91 /// This is meant for iterators actually dedicated to that kind of 92 /// purpose contains(&mut self, target: Revision) -> Result<bool, GraphError>93 pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { 94 if self.seen.contains(&target) && target != NULL_REVISION { 95 return Ok(true); 96 } 97 for item in self { 98 let rev = item?; 99 if rev == target { 100 return Ok(true); 101 } 102 if rev < target { 103 return Ok(false); 104 } 105 } 106 Ok(false) 107 } 108 peek(&self) -> Option<Revision>109 pub fn peek(&self) -> Option<Revision> { 110 self.visit.peek().cloned() 111 } 112 113 /// Tell if the iterator is about an empty set 114 /// 115 /// The result does not depend whether the iterator has been consumed 116 /// or not. 117 /// This is mostly meant for iterators backing a lazy ancestors set is_empty(&self) -> bool118 pub fn is_empty(&self) -> bool { 119 if self.visit.len() > 0 { 120 return false; 121 } 122 if self.seen.len() > 1 { 123 return false; 124 } 125 // at this point, the seen set is at most a singleton. 126 // If not `self.inclusive`, it's still possible that it has only 127 // the null revision 128 self.seen.is_empty() || self.seen.contains(&NULL_REVISION) 129 } 130 } 131 132 /// Main implementation for the iterator 133 /// 134 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` 135 /// with a few non crucial differences: 136 /// 137 /// - there's no filtering of invalid parent revisions. Actually, it should be 138 /// consistent and more efficient to filter them from the end caller. 139 /// - we don't have the optimization for adjacent revisions (i.e., the case 140 /// where `p1 == rev - 1`), because it amounts to update the first element of 141 /// the heap without sifting, which Rust's BinaryHeap doesn't let us do. 142 /// - we save a few pushes by comparing with `stoprev` before pushing 143 impl<G: Graph> Iterator for AncestorsIterator<G> { 144 type Item = Result<Revision, GraphError>; 145 next(&mut self) -> Option<Self::Item>146 fn next(&mut self) -> Option<Self::Item> { 147 let current = match self.visit.peek() { 148 None => { 149 return None; 150 } 151 Some(c) => *c, 152 }; 153 let [p1, p2] = match self.graph.parents(current) { 154 Ok(ps) => ps, 155 Err(e) => return Some(Err(e)), 156 }; 157 if p1 < self.stoprev || !self.seen.insert(p1) { 158 self.visit.pop(); 159 } else { 160 *(self.visit.peek_mut().unwrap()) = p1; 161 }; 162 163 self.conditionally_push_rev(p2); 164 Some(Ok(current)) 165 } 166 } 167 168 impl<G: Graph + Clone> LazyAncestors<G> { new( graph: G, initrevs: impl IntoIterator<Item = Revision>, stoprev: Revision, inclusive: bool, ) -> Result<Self, GraphError>169 pub fn new( 170 graph: G, 171 initrevs: impl IntoIterator<Item = Revision>, 172 stoprev: Revision, 173 inclusive: bool, 174 ) -> Result<Self, GraphError> { 175 let v: Vec<Revision> = initrevs.into_iter().collect(); 176 Ok(LazyAncestors { 177 graph: graph.clone(), 178 containsiter: AncestorsIterator::new( 179 graph, 180 v.iter().cloned(), 181 stoprev, 182 inclusive, 183 )?, 184 initrevs: v, 185 stoprev, 186 inclusive, 187 }) 188 } 189 contains(&mut self, rev: Revision) -> Result<bool, GraphError>190 pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> { 191 self.containsiter.contains(rev) 192 } 193 is_empty(&self) -> bool194 pub fn is_empty(&self) -> bool { 195 self.containsiter.is_empty() 196 } 197 iter(&self) -> AncestorsIterator<G>198 pub fn iter(&self) -> AncestorsIterator<G> { 199 // the arguments being the same as for self.containsiter, we know 200 // for sure that AncestorsIterator constructor can't fail 201 AncestorsIterator::new( 202 self.graph.clone(), 203 self.initrevs.iter().cloned(), 204 self.stoprev, 205 self.inclusive, 206 ) 207 .unwrap() 208 } 209 } 210 211 impl<G: Graph> MissingAncestors<G> { new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self212 pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { 213 let mut created = MissingAncestors { 214 graph, 215 bases: HashSet::new(), 216 max_base: NULL_REVISION, 217 }; 218 created.add_bases(bases); 219 created 220 } 221 has_bases(&self) -> bool222 pub fn has_bases(&self) -> bool { 223 !self.bases.is_empty() 224 } 225 226 /// Return a reference to current bases. 227 /// 228 /// This is useful in unit tests, but also setdiscovery.py does 229 /// read the bases attribute of a ancestor.missingancestors instance. get_bases<'a>(&'a self) -> &'a HashSet<Revision>230 pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> { 231 &self.bases 232 } 233 234 /// Computes the relative heads of current bases. 235 /// 236 /// The object is still usable after this. bases_heads(&self) -> Result<HashSet<Revision>, GraphError>237 pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> { 238 dagops::heads(&self.graph, self.bases.iter()) 239 } 240 241 /// Consumes the object and returns the relative heads of its bases. into_bases_heads( mut self, ) -> Result<HashSet<Revision>, GraphError>242 pub fn into_bases_heads( 243 mut self, 244 ) -> Result<HashSet<Revision>, GraphError> { 245 dagops::retain_heads(&self.graph, &mut self.bases)?; 246 Ok(self.bases) 247 } 248 249 /// Add some revisions to `self.bases` 250 /// 251 /// Takes care of keeping `self.max_base` up to date. add_bases( &mut self, new_bases: impl IntoIterator<Item = Revision>, )252 pub fn add_bases( 253 &mut self, 254 new_bases: impl IntoIterator<Item = Revision>, 255 ) { 256 let mut max_base = self.max_base; 257 self.bases.extend( 258 new_bases 259 .into_iter() 260 .filter(|&rev| rev != NULL_REVISION) 261 .map(|r| { 262 if r > max_base { 263 max_base = r; 264 } 265 r 266 }), 267 ); 268 self.max_base = max_base; 269 } 270 271 /// Remove all ancestors of self.bases from the revs set (in place) remove_ancestors_from( &mut self, revs: &mut HashSet<Revision>, ) -> Result<(), GraphError>272 pub fn remove_ancestors_from( 273 &mut self, 274 revs: &mut HashSet<Revision>, 275 ) -> Result<(), GraphError> { 276 revs.retain(|r| !self.bases.contains(r)); 277 // the null revision is always an ancestor. Logically speaking 278 // it's debatable in case bases is empty, but the Python 279 // implementation always adds NULL_REVISION to bases, making it 280 // unconditionnally true. 281 revs.remove(&NULL_REVISION); 282 if revs.is_empty() { 283 return Ok(()); 284 } 285 // anything in revs > start is definitely not an ancestor of bases 286 // revs <= start need to be investigated 287 if self.max_base == NULL_REVISION { 288 return Ok(()); 289 } 290 291 // whatever happens, we'll keep at least keepcount of them 292 // knowing this gives us a earlier stop condition than 293 // going all the way to the root 294 let keepcount = revs.iter().filter(|r| **r > self.max_base).count(); 295 296 let mut curr = self.max_base; 297 while curr != NULL_REVISION && revs.len() > keepcount { 298 if self.bases.contains(&curr) { 299 revs.remove(&curr); 300 self.add_parents(curr)?; 301 } 302 curr -= 1; 303 } 304 Ok(()) 305 } 306 307 /// Add the parents of `rev` to `self.bases` 308 /// 309 /// This has no effect on `self.max_base` 310 #[inline] add_parents(&mut self, rev: Revision) -> Result<(), GraphError>311 fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> { 312 if rev == NULL_REVISION { 313 return Ok(()); 314 } 315 for p in self.graph.parents(rev)?.iter().cloned() { 316 // No need to bother the set with inserting NULL_REVISION over and 317 // over 318 if p != NULL_REVISION { 319 self.bases.insert(p); 320 } 321 } 322 Ok(()) 323 } 324 325 /// Return all the ancestors of revs that are not ancestors of self.bases 326 /// 327 /// This may include elements from revs. 328 /// 329 /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in 330 /// revision number order, which is a topological order. missing_ancestors( &mut self, revs: impl IntoIterator<Item = Revision>, ) -> Result<Vec<Revision>, GraphError>331 pub fn missing_ancestors( 332 &mut self, 333 revs: impl IntoIterator<Item = Revision>, 334 ) -> Result<Vec<Revision>, GraphError> { 335 // just for convenience and comparison with Python version 336 let bases_visit = &mut self.bases; 337 let mut revs: HashSet<Revision> = revs 338 .into_iter() 339 .filter(|r| !bases_visit.contains(r)) 340 .collect(); 341 let revs_visit = &mut revs; 342 let mut both_visit: HashSet<Revision> = 343 revs_visit.intersection(&bases_visit).cloned().collect(); 344 if revs_visit.is_empty() { 345 return Ok(Vec::new()); 346 } 347 let max_revs = revs_visit.iter().cloned().max().unwrap(); 348 let start = max(self.max_base, max_revs); 349 350 // TODO heuristics for with_capacity()? 351 let mut missing: Vec<Revision> = Vec::new(); 352 for curr in (0..=start).rev() { 353 if revs_visit.is_empty() { 354 break; 355 } 356 if both_visit.remove(&curr) { 357 // curr's parents might have made it into revs_visit through 358 // another path 359 for p in self.graph.parents(curr)?.iter().cloned() { 360 if p == NULL_REVISION { 361 continue; 362 } 363 revs_visit.remove(&p); 364 bases_visit.insert(p); 365 both_visit.insert(p); 366 } 367 } else if revs_visit.remove(&curr) { 368 missing.push(curr); 369 for p in self.graph.parents(curr)?.iter().cloned() { 370 if p == NULL_REVISION { 371 continue; 372 } 373 if bases_visit.contains(&p) { 374 // p is already known to be an ancestor of revs_visit 375 revs_visit.remove(&p); 376 both_visit.insert(p); 377 } else if both_visit.contains(&p) { 378 // p should have been in bases_visit 379 revs_visit.remove(&p); 380 bases_visit.insert(p); 381 } else { 382 // visit later 383 revs_visit.insert(p); 384 } 385 } 386 } else if bases_visit.contains(&curr) { 387 for p in self.graph.parents(curr)?.iter().cloned() { 388 if p == NULL_REVISION { 389 continue; 390 } 391 if revs_visit.remove(&p) || both_visit.contains(&p) { 392 // p is an ancestor of bases_visit, and is implicitly 393 // in revs_visit, which means p is ::revs & ::bases. 394 bases_visit.insert(p); 395 both_visit.insert(p); 396 } else { 397 bases_visit.insert(p); 398 } 399 } 400 } 401 } 402 missing.reverse(); 403 Ok(missing) 404 } 405 } 406 407 #[cfg(test)] 408 mod tests { 409 410 use super::*; 411 use crate::testing::{SampleGraph, VecGraph}; 412 use std::iter::FromIterator; 413 list_ancestors<G: Graph>( graph: G, initrevs: Vec<Revision>, stoprev: Revision, inclusive: bool, ) -> Vec<Revision>414 fn list_ancestors<G: Graph>( 415 graph: G, 416 initrevs: Vec<Revision>, 417 stoprev: Revision, 418 inclusive: bool, 419 ) -> Vec<Revision> { 420 AncestorsIterator::new(graph, initrevs, stoprev, inclusive) 421 .unwrap() 422 .map(|res| res.unwrap()) 423 .collect() 424 } 425 426 #[test] 427 /// Same tests as test-ancestor.py, without membership 428 /// (see also test-ancestor.py.out) test_list_ancestor()429 fn test_list_ancestor() { 430 assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]); 431 assert_eq!( 432 list_ancestors(SampleGraph, vec![11, 13], 0, false), 433 vec![8, 7, 4, 3, 2, 1, 0] 434 ); 435 assert_eq!( 436 list_ancestors(SampleGraph, vec![1, 3], 0, false), 437 vec![1, 0] 438 ); 439 assert_eq!( 440 list_ancestors(SampleGraph, vec![11, 13], 0, true), 441 vec![13, 11, 8, 7, 4, 3, 2, 1, 0] 442 ); 443 assert_eq!( 444 list_ancestors(SampleGraph, vec![11, 13], 6, false), 445 vec![8, 7] 446 ); 447 assert_eq!( 448 list_ancestors(SampleGraph, vec![11, 13], 6, true), 449 vec![13, 11, 8, 7] 450 ); 451 assert_eq!( 452 list_ancestors(SampleGraph, vec![11, 13], 11, true), 453 vec![13, 11] 454 ); 455 assert_eq!( 456 list_ancestors(SampleGraph, vec![11, 13], 12, true), 457 vec![13] 458 ); 459 assert_eq!( 460 list_ancestors(SampleGraph, vec![10, 1], 0, true), 461 vec![10, 5, 4, 2, 1, 0] 462 ); 463 } 464 465 #[test] 466 /// Corner case that's not directly in test-ancestors.py, but 467 /// that happens quite often, as demonstrated by running the whole 468 /// suite. 469 /// For instance, run tests/test-obsolete-checkheads.t test_nullrev_input()470 fn test_nullrev_input() { 471 let mut iter = 472 AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap(); 473 assert_eq!(iter.next(), None) 474 } 475 476 #[test] test_contains()477 fn test_contains() { 478 let mut lazy = 479 AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap(); 480 assert!(lazy.contains(1).unwrap()); 481 assert!(!lazy.contains(3).unwrap()); 482 483 let mut lazy = 484 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap(); 485 assert!(!lazy.contains(NULL_REVISION).unwrap()); 486 } 487 488 #[test] test_peek()489 fn test_peek() { 490 let mut iter = 491 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap(); 492 // peek() gives us the next value 493 assert_eq!(iter.peek(), Some(10)); 494 // but it's not been consumed 495 assert_eq!(iter.next(), Some(Ok(10))); 496 // and iteration resumes normally 497 assert_eq!(iter.next(), Some(Ok(5))); 498 499 // let's drain the iterator to test peek() at the end 500 while iter.next().is_some() {} 501 assert_eq!(iter.peek(), None); 502 } 503 504 #[test] test_empty()505 fn test_empty() { 506 let mut iter = 507 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap(); 508 assert!(!iter.is_empty()); 509 while iter.next().is_some() {} 510 assert!(!iter.is_empty()); 511 512 let iter = 513 AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap(); 514 assert!(iter.is_empty()); 515 516 // case where iter.seen == {NULL_REVISION} 517 let iter = 518 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap(); 519 assert!(iter.is_empty()); 520 } 521 522 /// A corrupted Graph, supporting error handling tests 523 #[derive(Clone, Debug)] 524 struct Corrupted; 525 526 impl Graph for Corrupted { parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>527 fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { 528 match rev { 529 1 => Ok([0, -1]), 530 r => Err(GraphError::ParentOutOfRange(r)), 531 } 532 } 533 } 534 535 #[test] test_initrev_out_of_range()536 fn test_initrev_out_of_range() { 537 // inclusive=false looks up initrev's parents right away 538 match AncestorsIterator::new(SampleGraph, vec![25], 0, false) { 539 Ok(_) => panic!("Should have been ParentOutOfRange"), 540 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), 541 } 542 } 543 544 #[test] test_next_out_of_range()545 fn test_next_out_of_range() { 546 // inclusive=false looks up initrev's parents right away 547 let mut iter = 548 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); 549 assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); 550 } 551 552 #[test] test_lazy_iter_contains()553 fn test_lazy_iter_contains() { 554 let mut lazy = 555 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); 556 557 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); 558 // compare with iterator tests on the same initial revisions 559 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); 560 561 // contains() results are correct, unaffected by the fact that 562 // we consumed entirely an iterator out of lazy 563 assert_eq!(lazy.contains(2), Ok(true)); 564 assert_eq!(lazy.contains(9), Ok(false)); 565 } 566 567 #[test] test_lazy_contains_iter()568 fn test_lazy_contains_iter() { 569 let mut lazy = 570 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0] 571 572 assert_eq!(lazy.contains(2), Ok(true)); 573 assert_eq!(lazy.contains(6), Ok(false)); 574 575 // after consumption of 2 by the inner iterator, results stay 576 // consistent 577 assert_eq!(lazy.contains(2), Ok(true)); 578 assert_eq!(lazy.contains(5), Ok(false)); 579 580 // iter() still gives us a fresh iterator 581 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); 582 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); 583 } 584 585 #[test] 586 /// Test constructor, add/get bases and heads test_missing_bases() -> Result<(), GraphError>587 fn test_missing_bases() -> Result<(), GraphError> { 588 let mut missing_ancestors = 589 MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); 590 let mut as_vec: Vec<Revision> = 591 missing_ancestors.get_bases().iter().cloned().collect(); 592 as_vec.sort(); 593 assert_eq!(as_vec, [1, 3, 5]); 594 assert_eq!(missing_ancestors.max_base, 5); 595 596 missing_ancestors.add_bases([3, 7, 8].iter().cloned()); 597 as_vec = missing_ancestors.get_bases().iter().cloned().collect(); 598 as_vec.sort(); 599 assert_eq!(as_vec, [1, 3, 5, 7, 8]); 600 assert_eq!(missing_ancestors.max_base, 8); 601 602 as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect(); 603 as_vec.sort(); 604 assert_eq!(as_vec, [3, 5, 7, 8]); 605 Ok(()) 606 } 607 assert_missing_remove( bases: &[Revision], revs: &[Revision], expected: &[Revision], )608 fn assert_missing_remove( 609 bases: &[Revision], 610 revs: &[Revision], 611 expected: &[Revision], 612 ) { 613 let mut missing_ancestors = 614 MissingAncestors::new(SampleGraph, bases.iter().cloned()); 615 let mut revset: HashSet<Revision> = revs.iter().cloned().collect(); 616 missing_ancestors 617 .remove_ancestors_from(&mut revset) 618 .unwrap(); 619 let mut as_vec: Vec<Revision> = revset.into_iter().collect(); 620 as_vec.sort(); 621 assert_eq!(as_vec.as_slice(), expected); 622 } 623 624 #[test] test_missing_remove()625 fn test_missing_remove() { 626 assert_missing_remove( 627 &[1, 2, 3, 4, 7], 628 Vec::from_iter(1..10).as_slice(), 629 &[5, 6, 8, 9], 630 ); 631 assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]); 632 assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]); 633 } 634 assert_missing_ancestors( bases: &[Revision], revs: &[Revision], expected: &[Revision], )635 fn assert_missing_ancestors( 636 bases: &[Revision], 637 revs: &[Revision], 638 expected: &[Revision], 639 ) { 640 let mut missing_ancestors = 641 MissingAncestors::new(SampleGraph, bases.iter().cloned()); 642 let missing = missing_ancestors 643 .missing_ancestors(revs.iter().cloned()) 644 .unwrap(); 645 assert_eq!(missing.as_slice(), expected); 646 } 647 648 #[test] test_missing_ancestors()649 fn test_missing_ancestors() { 650 // examples taken from test-ancestors.py by having it run 651 // on the same graph (both naive and fast Python algs) 652 assert_missing_ancestors(&[10], &[11], &[3, 7, 11]); 653 assert_missing_ancestors(&[11], &[10], &[5, 10]); 654 assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]); 655 } 656 657 /// An interesting case found by a random generator similar to 658 /// the one in test-ancestor.py. An early version of Rust MissingAncestors 659 /// failed this, yet none of the integration tests of the whole suite 660 /// catched it. 661 #[test] test_remove_ancestors_from_case1()662 fn test_remove_ancestors_from_case1() { 663 let graph: VecGraph = vec![ 664 [NULL_REVISION, NULL_REVISION], 665 [0, NULL_REVISION], 666 [1, 0], 667 [2, 1], 668 [3, NULL_REVISION], 669 [4, NULL_REVISION], 670 [5, 1], 671 [2, NULL_REVISION], 672 [7, NULL_REVISION], 673 [8, NULL_REVISION], 674 [9, NULL_REVISION], 675 [10, 1], 676 [3, NULL_REVISION], 677 [12, NULL_REVISION], 678 [13, NULL_REVISION], 679 [14, NULL_REVISION], 680 [4, NULL_REVISION], 681 [16, NULL_REVISION], 682 [17, NULL_REVISION], 683 [18, NULL_REVISION], 684 [19, 11], 685 [20, NULL_REVISION], 686 [21, NULL_REVISION], 687 [22, NULL_REVISION], 688 [23, NULL_REVISION], 689 [2, NULL_REVISION], 690 [3, NULL_REVISION], 691 [26, 24], 692 [27, NULL_REVISION], 693 [28, NULL_REVISION], 694 [12, NULL_REVISION], 695 [1, NULL_REVISION], 696 [1, 9], 697 [32, NULL_REVISION], 698 [33, NULL_REVISION], 699 [34, 31], 700 [35, NULL_REVISION], 701 [36, 26], 702 [37, NULL_REVISION], 703 [38, NULL_REVISION], 704 [39, NULL_REVISION], 705 [40, NULL_REVISION], 706 [41, NULL_REVISION], 707 [42, 26], 708 [0, NULL_REVISION], 709 [44, NULL_REVISION], 710 [45, 4], 711 [40, NULL_REVISION], 712 [47, NULL_REVISION], 713 [36, 0], 714 [49, NULL_REVISION], 715 [NULL_REVISION, NULL_REVISION], 716 [51, NULL_REVISION], 717 [52, NULL_REVISION], 718 [53, NULL_REVISION], 719 [14, NULL_REVISION], 720 [55, NULL_REVISION], 721 [15, NULL_REVISION], 722 [23, NULL_REVISION], 723 [58, NULL_REVISION], 724 [59, NULL_REVISION], 725 [2, NULL_REVISION], 726 [61, 59], 727 [62, NULL_REVISION], 728 [63, NULL_REVISION], 729 [NULL_REVISION, NULL_REVISION], 730 [65, NULL_REVISION], 731 [66, NULL_REVISION], 732 [67, NULL_REVISION], 733 [68, NULL_REVISION], 734 [37, 28], 735 [69, 25], 736 [71, NULL_REVISION], 737 [72, NULL_REVISION], 738 [50, 2], 739 [74, NULL_REVISION], 740 [12, NULL_REVISION], 741 [18, NULL_REVISION], 742 [77, NULL_REVISION], 743 [78, NULL_REVISION], 744 [79, NULL_REVISION], 745 [43, 33], 746 [81, NULL_REVISION], 747 [82, NULL_REVISION], 748 [83, NULL_REVISION], 749 [84, 45], 750 [85, NULL_REVISION], 751 [86, NULL_REVISION], 752 [NULL_REVISION, NULL_REVISION], 753 [88, NULL_REVISION], 754 [NULL_REVISION, NULL_REVISION], 755 [76, 83], 756 [44, NULL_REVISION], 757 [92, NULL_REVISION], 758 [93, NULL_REVISION], 759 [9, NULL_REVISION], 760 [95, 67], 761 [96, NULL_REVISION], 762 [97, NULL_REVISION], 763 [NULL_REVISION, NULL_REVISION], 764 ]; 765 let problem_rev = 28 as Revision; 766 let problem_base = 70 as Revision; 767 // making the problem obvious: problem_rev is a parent of problem_base 768 assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev); 769 770 let mut missing_ancestors: MissingAncestors<VecGraph> = 771 MissingAncestors::new( 772 graph, 773 [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6] 774 .iter() 775 .cloned(), 776 ); 777 assert!(missing_ancestors.bases.contains(&problem_base)); 778 779 let mut revs: HashSet<Revision> = 780 [4, 12, 41, 28, 68, 38, 1, 30, 56, 44] 781 .iter() 782 .cloned() 783 .collect(); 784 missing_ancestors.remove_ancestors_from(&mut revs).unwrap(); 785 assert!(!revs.contains(&problem_rev)); 786 } 787 } 788