##// END OF EJS Templates
upstream » mercurial-mirror
RSS

Clone from https://www.mercurial-scm.org/repo/hg-all

copies: iterate over children directly (instead of parents)...
marmoute -
r46764:294d5aca default
parent child Browse files
Show More
Show file before | Show file after | Hide comments
@@ -288,40 +288,92 def _changesetforwardcopies(a, b, match)
288
288
289 cl = repo.changelog
289 cl = repo.changelog
290 isancestor = cl.isancestorrev
290 isancestor = cl.isancestorrev
291 missingrevs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])
291
292 mrset = set(missingrevs)
292 # To track rename from "A" to B, we need to gather all parent → children
293 # edges that are contains in `::B` but not in `::A`.
294 #
295 #
296 # To do so, we need to gather all revisions exclusive¹ to "B" (ie¹: `::b -
297 # ::a`) and also all the "roots point", ie the parents of the exclusive set
298 # that belong to ::a. These are exactly all the revisions needed to express
299 # the parent → children we need to combine.
300 #
301 # [1] actually, we need to gather all the edges within `(::a)::b`, ie:
302 # excluding paths that leads to roots that are not ancestors of `a`. We
303 # keep this out of the explanation because it is hard enough without this special case..
304
305 parents = cl._uncheckedparentrevs
306 graph_roots = (nullrev, nullrev)
307
308 ancestors = cl.ancestors([a.rev()], inclusive=True)
309 revs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])
293 roots = set()
310 roots = set()
294 for r in missingrevs:
311 has_graph_roots = False
295 for p in cl.parentrevs(r):
312
296 if p == nullrev:
313 # iterate over `only(B, A)`
297 continue
314 for r in revs:
298 if p not in children:
315 ps = parents(r)
299 children[p] = [r]
316 if ps == graph_roots:
317 has_graph_roots = True
300 else:
318 else:
301 children[p].append(r)
319 p1, p2 = ps
302 if p not in mrset:
320
303 roots.add(p)
321 # find all the "root points" (see larger comment above)
322 if p1 != nullrev and p1 in ancestors:
323 roots.add(p1)
324 if p2 != nullrev and p2 in ancestors:
325 roots.add(p2)
304 if not roots:
326 if not roots:
305 # no common revision to track copies from
327 # no common revision to track copies from
306 return {}
328 return {}
307 min_root = min(roots)
329 if has_graph_roots:
308
330 # this deal with the special case mentionned in the [1] footnotes. We
309 from_head = set(
331 # must filter out revisions that leads to non-common graphroots.
310 cl.reachableroots(min_root, [b.rev()], list(roots), includepath=True)
332 roots = list(roots)
311 )
333 m = min(roots)
312
334 h = [b.rev()]
313 iterrevs = set(from_head)
335 roots_to_head = cl.reachableroots(m, h, roots, includepath=True)
314 iterrevs &= mrset
336 roots_to_head = set(roots_to_head)
315 iterrevs.update(roots)
337 revs = [r for r in revs if r in roots_to_head]
316 iterrevs.remove(b.rev())
317 revs = sorted(iterrevs)
318
338
319 if repo.filecopiesmode == b'changeset-sidedata':
339 if repo.filecopiesmode == b'changeset-sidedata':
340 # When using side-data, we will process the edges "from" the children.
341 # We iterate over the childre, gathering previous collected data for
342 # the parents. Do know when the parents data is no longer necessary, we
343 # keep a counter of how many children each revision has.
344 #
345 # An interresting property of `children_count` is that it only contains
346 # revision that will be relevant for a edge of the graph. So if a
347 # children has parent not in `children_count`, that edges should not be
348 # processed.
349 children_count = dict((r, 0) for r in roots)
350 for r in revs:
351 for p in cl.parentrevs(r):
352 if p == nullrev:
353 continue
354 children_count[r] = 0
355 if p in children_count:
356 children_count[p] += 1
320 revinfo = _revinfo_getter(repo, match)
357 revinfo = _revinfo_getter(repo, match)
321 return _combine_changeset_copies(
358 return _combine_changeset_copies(
322 revs, children, b.rev(), revinfo, match, isancestor
359 revs, children_count, b.rev(), revinfo, match, isancestor
323 )
360 )
324 else:
361 else:
362 # When not using side-data, we will process the edges "from" the parent.
363 # so we need a full mapping of the parent -> children relation.
364 children = dict((r, []) for r in roots)
365 for r in revs:
366 for p in cl.parentrevs(r):
367 if p == nullrev:
368 continue
369 children[r] = []
370 if p in children:
371 children[p].append(r)
372 x = revs.pop()
373 assert x == b.rev()
374 revs.extend(roots)
375 revs.sort()
376
325 revinfo = _revinfo_getter_extra(repo)
377 revinfo = _revinfo_getter_extra(repo)
326 return _combine_changeset_copies_extra(
378 return _combine_changeset_copies_extra(
327 revs, children, b.rev(), revinfo, match, isancestor
379 revs, children, b.rev(), revinfo, match, isancestor
@@ -329,12 +381,12 def _changesetforwardcopies(a, b, match)
329
381
330
382
331 def _combine_changeset_copies(
383 def _combine_changeset_copies(
332 revs, children, targetrev, revinfo, match, isancestor
384 revs, children_count, targetrev, revinfo, match, isancestor
333 ):
385 ):
334 """combine the copies information for each item of iterrevs
386 """combine the copies information for each item of iterrevs
335
387
336 revs: sorted iterable of revision to visit
388 revs: sorted iterable of revision to visit
337 children: a {parent: [children]} mapping.
389 children_count: a {parent: <number-of-relevant-children>} mapping.
338 targetrev: the final copies destination revision (not in iterrevs)
390 targetrev: the final copies destination revision (not in iterrevs)
339 revinfo(rev): a function that return (p1, p2, p1copies, p2copies, removed)
391 revinfo(rev): a function that return (p1, p2, p1copies, p2copies, removed)
340 match: a matcher
392 match: a matcher
@@ -346,52 +398,60 def _combine_changeset_copies(
346
398
347 if rustmod is not None and alwaysmatch:
399 if rustmod is not None and alwaysmatch:
348 return rustmod.combine_changeset_copies(
400 return rustmod.combine_changeset_copies(
349 list(revs), children, targetrev, revinfo, isancestor
401 list(revs), children_count, targetrev, revinfo, isancestor
350 )
402 )
351
403
352 isancestor = cached_is_ancestor(isancestor)
404 isancestor = cached_is_ancestor(isancestor)
353
405
354 all_copies = {}
406 all_copies = {}
355 # iterate over all the "parent" side of copy tracing "edge"
407 # iterate over all the "children" side of copy tracing "edge"
356 for r in revs:
408 for current_rev in revs:
357 # fetch potential previously computed data for that parent
409 p1, p2, changes = revinfo(current_rev)
358 copies = all_copies.pop(r, None)
410 current_copies = None
411
412 # iterate over all parents to chain the existing data with the
413 # data from the parent → child edge.
414 for parent, parent_rev in ((1, p1), (2, p2)):
415 if parent_rev == nullrev:
416 continue
417 remaining_children = children_count.get(parent_rev)
418 if remaining_children is None:
419 continue
420 remaining_children -= 1
421 children_count[parent_rev] = remaining_children
422 if remaining_children:
423 copies = all_copies.get(parent_rev, None)
424 else:
425 copies = all_copies.pop(parent_rev, None)
426
359 if copies is None:
427 if copies is None:
360 # this is a root
428 # this is a root
361 copies = {}
429 copies = {}
362
430
363 # iterate over all known children to chain the existing data with the
431 newcopies = copies
364 # data from the parent → child edge.
432 # chain the data in the edge with the existing data
365 for i, c in enumerate(children[r]):
433 if changes is not None:
366 p1, p2, changes = revinfo(c)
367 childcopies = {}
434 childcopies = {}
435 if parent == 1:
436 childcopies = changes.copied_from_p1
437 elif parent == 2:
438 childcopies = changes.copied_from_p2
368
439
369 # select the right parent → child edge
370 if r == p1:
371 parent = 1
372 if changes is not None:
373 childcopies = changes.copied_from_p1
374 else:
375 assert r == p2
376 parent = 2
377 if changes is not None:
378 childcopies = changes.copied_from_p2
379 if not alwaysmatch:
440 if not alwaysmatch:
380 childcopies = {
441 childcopies = {
381 dst: src for dst, src in childcopies.items() if match(dst)
442 dst: src
443 for dst, src in childcopies.items()
444 if match(dst)
382 }
445 }
383
384 # chain the data in the edge with the existing data
385 newcopies = copies
386 if childcopies:
446 if childcopies:
387 newcopies = copies.copy()
447 newcopies = copies.copy()
388 for dest, source in pycompat.iteritems(childcopies):
448 for dest, source in pycompat.iteritems(childcopies):
389 prev = copies.get(source)
449 prev = copies.get(source)
390 if prev is not None and prev[1] is not None:
450 if prev is not None and prev[1] is not None:
391 source = prev[1]
451 source = prev[1]
392 newcopies[dest] = (c, source)
452 newcopies[dest] = (current_rev, source)
393 assert newcopies is not copies
453 assert newcopies is not copies
394 if changes is not None and changes.removed:
454 if changes.removed:
395 if newcopies is copies:
455 if newcopies is copies:
396 newcopies = copies.copy()
456 newcopies = copies.copy()
397 for f in changes.removed:
457 for f in changes.removed:
@@ -401,14 +461,13 def _combine_changeset_copies(
401 # branches. when there are no other branches, this
461 # branches. when there are no other branches, this
402 # could be avoided.
462 # could be avoided.
403 newcopies = copies.copy()
463 newcopies = copies.copy()
404 newcopies[f] = (c, None)
464 newcopies[f] = (current_rev, None)
405
465
406 # check potential need to combine the data from another parent (for
466 # check potential need to combine the data from another parent (for
407 # that child). See comment below for details.
467 # that child). See comment below for details.
408 othercopies = all_copies.get(c)
468 if current_copies is None:
409 if othercopies is None:
469 current_copies = newcopies
410 all_copies[c] = newcopies
470 elif current_copies is newcopies:
411 elif newcopies is othercopies:
412 # nothing to merge:
471 # nothing to merge:
413 pass
472 pass
414 else:
473 else:
@@ -419,17 +478,11 def _combine_changeset_copies(
419 # This is an arbitrary choice made anew when implementing
478 # This is an arbitrary choice made anew when implementing
420 # changeset based copies. It was made without regards with
479 # changeset based copies. It was made without regards with
421 # potential filelog related behavior.
480 # potential filelog related behavior.
422 if parent == 1:
481 assert parent == 2
423 if newcopies is copies:
482 current_copies = _merge_copies_dict(
424 newcopies = copies.copy()
483 newcopies, current_copies, isancestor, changes
425 minor, major = othercopies, newcopies
484 )
426 else:
485 all_copies[current_rev] = current_copies
427 # we do not know if the other dict is a copy or not, so we
428 # need to blindly copy it. Future change should make this
429 # unnecessary.
430 minor, major = newcopies, othercopies.copy()
431 copies = _merge_copies_dict(minor, major, isancestor, changes)
432 all_copies[c] = copies
433
486
434 # filter out internal details and return a {dest: source mapping}
487 # filter out internal details and return a {dest: source mapping}
435 final_copies = {}
488 final_copies = {}
Show file before | Show file after | Hide comments
@@ -1,6 +1,7
1 use crate::utils::hg_path::HgPath;
1 use crate::utils::hg_path::HgPath;
2 use crate::utils::hg_path::HgPathBuf;
2 use crate::utils::hg_path::HgPathBuf;
3 use crate::Revision;
3 use crate::Revision;
4 use crate::NULL_REVISION;
4
5
5 use im_rc::ordmap::DiffItem;
6 use im_rc::ordmap::DiffItem;
6 use im_rc::ordmap::OrdMap;
7 use im_rc::ordmap::OrdMap;
@@ -328,7 +329,7 enum Parent {
328 /// ancestor of another
329 /// ancestor of another
329 pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool, D>(
330 pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool, D>(
330 revs: Vec<Revision>,
331 revs: Vec<Revision>,
331 children: HashMap<Revision, Vec<Revision>>,
332 mut children_count: HashMap<Revision, usize>,
332 target_rev: Revision,
333 target_rev: Revision,
333 rev_info: RevInfoMaker<D>,
334 rev_info: RevInfoMaker<D>,
334 is_ancestor: &A,
335 is_ancestor: &A,
@@ -337,57 +338,69 pub fn combine_changeset_copies<A: Fn(Re
337 let mut oracle = AncestorOracle::new(is_ancestor);
338 let mut oracle = AncestorOracle::new(is_ancestor);
338
339
339 for rev in revs {
340 for rev in revs {
340 // Retrieve data computed in a previous iteration
341 let mut d: DataHolder<D> = DataHolder { data: None };
341 let copies = all_copies.remove(&rev);
342 let (p1, p2, changes) = rev_info(rev, &mut d);
342 let copies = match copies {
343 Some(c) => c,
344 None => TimeStampedPathCopies::default(), // root of the walked set
345 };
346
347 let current_children = match children.get(&rev) {
348 Some(c) => c,
349 None => panic!("inconsistent `revs` and `children`"),
350 };
351
343
352 for child in current_children {
344 // We will chain the copies information accumulated for the parent with
353 // We will chain the copies information accumulated for `rev` with
345 // the individual copies information the curent revision. Creating a
354 // the individual copies information for each of its children.
346 // new TimeStampedPath for each `rev` → `children` vertex.
355 // Creating a new PathCopies for each `rev` → `children` vertex.
347 let mut copies: Option<TimeStampedPathCopies> = None;
356 let mut d: DataHolder<D> = DataHolder { data: None };
348 if p1 != NULL_REVISION {
357 let (p1, p2, changes) = rev_info(*child, &mut d);
349 // Retrieve data computed in a previous iteration
350 let parent_copies = get_and_clean_parent_copies(
351 &mut all_copies,
352 &mut children_count,
353 p1,
354 );
355 if let Some(parent_copies) = parent_copies {
356 // combine it with data for that revision
357 let vertex_copies = add_from_changes(
358 &parent_copies,
359 &changes,
360 Parent::FirstParent,
361 rev,
362 );
363 // keep that data around for potential later combination
364 copies = Some(vertex_copies);
365 }
366 }
367 if p2 != NULL_REVISION {
368 // Retrieve data computed in a previous iteration
369 let parent_copies = get_and_clean_parent_copies(
370 &mut all_copies,
371 &mut children_count,
372 p2,
373 );
374 if let Some(parent_copies) = parent_copies {
375 // combine it with data for that revision
376 let vertex_copies = add_from_changes(
377 &parent_copies,
378 &changes,
379 Parent::SecondParent,
380 rev,
381 );
358
382
359 let parent = if rev == p1 {
383 copies = match copies {
360 Parent::FirstParent
384 None => Some(vertex_copies),
361 } else {
385 // Merge has two parents needs to combines their copy
362 assert_eq!(rev, p2);
386 // information.
363 Parent::SecondParent
387 //
388 // If we got data from both parents, We need to combine
389 // them.
390 Some(copies) => Some(merge_copies_dict(
391 vertex_copies,
392 copies,
393 &changes,
394 &mut oracle,
395 )),
364 };
396 };
365 let new_copies =
397 }
366 add_from_changes(&copies, &changes, parent, *child);
367
368 // Merge has two parents needs to combines their copy information.
369 //
370 // If the vertex from the other parent was already processed, we
371 // will have a value for the child ready to be used. We need to
372 // grab it and combine it with the one we already
373 // computed. If not we can simply store the newly
374 // computed data. The processing happening at
375 // the time of the second parent will take care of combining the
376 // two TimeStampedPathCopies instance.
377 match all_copies.remove(child) {
378 None => {
379 all_copies.insert(child, new_copies);
380 }
398 }
381 Some(other_copies) => {
399 match copies {
382 let (minor, major) = match parent {
400 Some(copies) => {
383 Parent::FirstParent => (other_copies, new_copies),
401 all_copies.insert(rev, copies);
384 Parent::SecondParent => (new_copies, other_copies),
385 };
386 let merged_copies =
387 merge_copies_dict(minor, major, &changes, &mut oracle);
388 all_copies.insert(child, merged_copies);
389 }
402 }
390 };
403 _ => {}
391 }
404 }
392 }
405 }
393
406
@@ -405,6 +418,32 pub fn combine_changeset_copies<A: Fn(Re
405 result
418 result
406 }
419 }
407
420
421 /// fetch previous computed information
422 ///
423 /// If no other children are expected to need this information, we drop it from
424 /// the cache.
425 ///
426 /// If parent is not part of the set we are expected to walk, return None.
427 fn get_and_clean_parent_copies(
428 all_copies: &mut HashMap<Revision, TimeStampedPathCopies>,
429 children_count: &mut HashMap<Revision, usize>,
430 parent_rev: Revision,
431 ) -> Option<TimeStampedPathCopies> {
432 let count = children_count.get_mut(&parent_rev)?;
433 *count -= 1;
434 if *count == 0 {
435 match all_copies.remove(&parent_rev) {
436 Some(c) => Some(c),
437 None => Some(TimeStampedPathCopies::default()),
438 }
439 } else {
440 match all_copies.get(&parent_rev) {
441 Some(c) => Some(c.clone()),
442 None => Some(TimeStampedPathCopies::default()),
443 }
444 }
445 }
446
408 /// Combine ChangedFiles with some existing PathCopies information and return
447 /// Combine ChangedFiles with some existing PathCopies information and return
409 /// the result
448 /// the result
410 fn add_from_changes(
449 fn add_from_changes(
Show file before | Show file after | Hide comments
@@ -23,7 +23,7 use hg::Revision;
23 pub fn combine_changeset_copies_wrapper(
23 pub fn combine_changeset_copies_wrapper(
24 py: Python,
24 py: Python,
25 revs: PyList,
25 revs: PyList,
26 children: PyDict,
26 children_count: PyDict,
27 target_rev: Revision,
27 target_rev: Revision,
28 rev_info: PyObject,
28 rev_info: PyObject,
29 is_ancestor: PyObject,
29 is_ancestor: PyObject,
@@ -93,20 +93,15 pub fn combine_changeset_copies_wrapper(
93
93
94 (p1, p2, files)
94 (p1, p2, files)
95 });
95 });
96 let children: PyResult<_> = children
96 let children_count: PyResult<_> = children_count
97 .items(py)
97 .items(py)
98 .iter()
98 .iter()
99 .map(|(k, v)| {
99 .map(|(k, v)| Ok((k.extract(py)?, v.extract(py)?)))
100 let v: &PyList = v.cast_as(py)?;
101 let v: PyResult<_> =
102 v.iter(py).map(|child| Ok(child.extract(py)?)).collect();
103 Ok((k.extract(py)?, v?))
104 })
105 .collect();
100 .collect();
106
101
107 let res = combine_changeset_copies(
102 let res = combine_changeset_copies(
108 revs?,
103 revs?,
109 children?,
104 children_count?,
110 target_rev,
105 target_rev,
111 rev_info_maker,
106 rev_info_maker,
112 &is_ancestor_wrap,
107 &is_ancestor_wrap,
General Comments 0
You need to be logged in to leave comments. Login now