332 let mut missing: Vec<Revision> = Vec::new(); |
332 let mut missing: Vec<Revision> = Vec::new(); |
333 for curr in (0..=start).rev() { |
333 for curr in (0..=start).rev() { |
334 if revs_visit.is_empty() { |
334 if revs_visit.is_empty() { |
335 break; |
335 break; |
336 } |
336 } |
337 if both_visit.contains(&curr) { |
337 if both_visit.remove(&curr) { |
338 // curr's parents might have made it into revs_visit through |
338 // curr's parents might have made it into revs_visit through |
339 // another path |
339 // another path |
340 // TODO optim: Rust's HashSet.remove returns a boolean telling |
|
341 // if it happened. This will spare us one set lookup |
|
342 both_visit.remove(&curr); |
|
343 for p in self.graph.parents(curr)?.iter().cloned() { |
340 for p in self.graph.parents(curr)?.iter().cloned() { |
344 if p == NULL_REVISION { |
341 if p == NULL_REVISION { |
345 continue; |
342 continue; |
346 } |
343 } |
347 revs_visit.remove(&p); |
344 revs_visit.remove(&p); |
352 missing.push(curr); |
349 missing.push(curr); |
353 for p in self.graph.parents(curr)?.iter().cloned() { |
350 for p in self.graph.parents(curr)?.iter().cloned() { |
354 if p == NULL_REVISION { |
351 if p == NULL_REVISION { |
355 continue; |
352 continue; |
356 } |
353 } |
357 if bases_visit.contains(&p) || both_visit.contains(&p) { |
354 if bases_visit.contains(&p) { |
358 // p is an ancestor of revs_visit, and is implicitly |
355 // p is already known to be an ancestor of revs_visit |
359 // in bases_visit, which means p is ::revs & ::bases. |
356 revs_visit.remove(&p); |
360 // TODO optim: hence if bothvisit, we look up twice |
357 both_visit.insert(p); |
|
358 } else if both_visit.contains(&p) { |
|
359 // p should have been in bases_visit |
361 revs_visit.remove(&p); |
360 revs_visit.remove(&p); |
362 bases_visit.insert(p); |
361 bases_visit.insert(p); |
363 both_visit.insert(p); |
|
364 } else { |
362 } else { |
365 // visit later |
363 // visit later |
366 revs_visit.insert(p); |
364 revs_visit.insert(p); |
367 } |
365 } |
368 } |
366 } |
369 } else if bases_visit.contains(&curr) { |
367 } else if bases_visit.contains(&curr) { |
370 for p in self.graph.parents(curr)?.iter().cloned() { |
368 for p in self.graph.parents(curr)?.iter().cloned() { |
371 if p == NULL_REVISION { |
369 if p == NULL_REVISION { |
372 continue; |
370 continue; |
373 } |
371 } |
374 if revs_visit.contains(&p) || both_visit.contains(&p) { |
372 if revs_visit.remove(&p) || both_visit.contains(&p) { |
375 // p is an ancestor of bases_visit, and is implicitly |
373 // p is an ancestor of bases_visit, and is implicitly |
376 // in revs_visit, which means p is ::revs & ::bases. |
374 // in revs_visit, which means p is ::revs & ::bases. |
377 // TODO optim: hence if bothvisit, we look up twice |
|
378 revs_visit.remove(&p); |
|
379 bases_visit.insert(p); |
375 bases_visit.insert(p); |
380 both_visit.insert(p); |
376 both_visit.insert(p); |
381 } else { |
377 } else { |
382 bases_visit.insert(p); |
378 bases_visit.insert(p); |
383 } |
379 } |