##// 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 b' def _changesetforwardcopies(a, b, match)'
288 288
289 289 cl = repo.changelog
290 290 isancestor = cl.isancestorrev
291 missingrevs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])
292 mrset = set(missingrevs)
291
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 310 roots = set()
294 for r in missingrevs:
295 for p in cl.parentrevs(r):
296 if p == nullrev:
297 continue
298 if p not in children:
299 children[p] = [r]
300 else:
301 children[p].append(r)
302 if p not in mrset:
303 roots.add(p)
311 has_graph_roots = False
312
313 # iterate over `only(B, A)`
314 for r in revs:
315 ps = parents(r)
316 if ps == graph_roots:
317 has_graph_roots = True
318 else:
319 p1, p2 = ps
320
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 326 if not roots:
305 327 # no common revision to track copies from
306 328 return {}
307 min_root = min(roots)
308
309 from_head = set(
310 cl.reachableroots(min_root, [b.rev()], list(roots), includepath=True)
311 )
312
313 iterrevs = set(from_head)
314 iterrevs &= mrset
315 iterrevs.update(roots)
316 iterrevs.remove(b.rev())
317 revs = sorted(iterrevs)
329 if has_graph_roots:
330 # this deal with the special case mentionned in the [1] footnotes. We
331 # must filter out revisions that leads to non-common graphroots.
332 roots = list(roots)
333 m = min(roots)
334 h = [b.rev()]
335 roots_to_head = cl.reachableroots(m, h, roots, includepath=True)
336 roots_to_head = set(roots_to_head)
337 revs = [r for r in revs if r in roots_to_head]
318 338
319 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 357 revinfo = _revinfo_getter(repo, match)
321 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 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 377 revinfo = _revinfo_getter_extra(repo)
326 378 return _combine_changeset_copies_extra(
327 379 revs, children, b.rev(), revinfo, match, isancestor
@@ -329,12 +381,12 b' def _changesetforwardcopies(a, b, match)'
329 381
330 382
331 383 def _combine_changeset_copies(
332 revs, children, targetrev, revinfo, match, isancestor
384 revs, children_count, targetrev, revinfo, match, isancestor
333 385 ):
334 386 """combine the copies information for each item of iterrevs
335 387
336 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 390 targetrev: the final copies destination revision (not in iterrevs)
339 391 revinfo(rev): a function that return (p1, p2, p1copies, p2copies, removed)
340 392 match: a matcher
@@ -346,69 +398,76 b' def _combine_changeset_copies('
346 398
347 399 if rustmod is not None and alwaysmatch:
348 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 404 isancestor = cached_is_ancestor(isancestor)
353 405
354 406 all_copies = {}
355 # iterate over all the "parent" side of copy tracing "edge"
356 for r in revs:
357 # fetch potential previously computed data for that parent
358 copies = all_copies.pop(r, None)
359 if copies is None:
360 # this is a root
361 copies = {}
407 # iterate over all the "children" side of copy tracing "edge"
408 for current_rev in revs:
409 p1, p2, changes = revinfo(current_rev)
410 current_copies = None
362 411
363 # iterate over all known children to chain the existing data with the
412 # iterate over all parents to chain the existing data with the
364 413 # data from the parent → child edge.
365 for i, c in enumerate(children[r]):
366 p1, p2, changes = revinfo(c)
367 childcopies = {}
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)
368 426
369 # select the right parent → child edge
370 if r == p1:
371 parent = 1
372 if changes is not None:
427 if copies is None:
428 # this is a root
429 copies = {}
430
431 newcopies = copies
432 # chain the data in the edge with the existing data
433 if changes is not None:
434 childcopies = {}
435 if parent == 1:
373 436 childcopies = changes.copied_from_p1
374 else:
375 assert r == p2
376 parent = 2
377 if changes is not None:
437 elif parent == 2:
378 438 childcopies = changes.copied_from_p2
379 if not alwaysmatch:
380 childcopies = {
381 dst: src for dst, src in childcopies.items() if match(dst)
382 }
383 439
384 # chain the data in the edge with the existing data
385 newcopies = copies
386 if childcopies:
387 newcopies = copies.copy()
388 for dest, source in pycompat.iteritems(childcopies):
389 prev = copies.get(source)
390 if prev is not None and prev[1] is not None:
391 source = prev[1]
392 newcopies[dest] = (c, source)
393 assert newcopies is not copies
394 if changes is not None and changes.removed:
395 if newcopies is copies:
440 if not alwaysmatch:
441 childcopies = {
442 dst: src
443 for dst, src in childcopies.items()
444 if match(dst)
445 }
446 if childcopies:
396 447 newcopies = copies.copy()
397 for f in changes.removed:
398 if f in newcopies:
399 if newcopies is copies:
400 # copy on write to avoid affecting potential other
401 # branches. when there are no other branches, this
402 # could be avoided.
403 newcopies = copies.copy()
404 newcopies[f] = (c, None)
448 for dest, source in pycompat.iteritems(childcopies):
449 prev = copies.get(source)
450 if prev is not None and prev[1] is not None:
451 source = prev[1]
452 newcopies[dest] = (current_rev, source)
453 assert newcopies is not copies
454 if changes.removed:
455 if newcopies is copies:
456 newcopies = copies.copy()
457 for f in changes.removed:
458 if f in newcopies:
459 if newcopies is copies:
460 # copy on write to avoid affecting potential other
461 # branches. when there are no other branches, this
462 # could be avoided.
463 newcopies = copies.copy()
464 newcopies[f] = (current_rev, None)
405 465
406 466 # check potential need to combine the data from another parent (for
407 467 # that child). See comment below for details.
408 othercopies = all_copies.get(c)
409 if othercopies is None:
410 all_copies[c] = newcopies
411 elif newcopies is othercopies:
468 if current_copies is None:
469 current_copies = newcopies
470 elif current_copies is newcopies:
412 471 # nothing to merge:
413 472 pass
414 473 else:
@@ -419,17 +478,11 b' def _combine_changeset_copies('
419 478 # This is an arbitrary choice made anew when implementing
420 479 # changeset based copies. It was made without regards with
421 480 # potential filelog related behavior.
422 if parent == 1:
423 if newcopies is copies:
424 newcopies = copies.copy()
425 minor, major = othercopies, newcopies
426 else:
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
481 assert parent == 2
482 current_copies = _merge_copies_dict(
483 newcopies, current_copies, isancestor, changes
484 )
485 all_copies[current_rev] = current_copies
433 486
434 487 # filter out internal details and return a {dest: source mapping}
435 488 final_copies = {}
Show file before | Show file after | Hide comments
@@ -1,6 +1,7 b''
1 1 use crate::utils::hg_path::HgPath;
2 2 use crate::utils::hg_path::HgPathBuf;
3 3 use crate::Revision;
4 use crate::NULL_REVISION;
4 5
5 6 use im_rc::ordmap::DiffItem;
6 7 use im_rc::ordmap::OrdMap;
@@ -328,7 +329,7 b' enum Parent {'
328 329 /// ancestor of another
329 330 pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool, D>(
330 331 revs: Vec<Revision>,
331 children: HashMap<Revision, Vec<Revision>>,
332 mut children_count: HashMap<Revision, usize>,
332 333 target_rev: Revision,
333 334 rev_info: RevInfoMaker<D>,
334 335 is_ancestor: &A,
@@ -337,57 +338,69 b' pub fn combine_changeset_copies<A: Fn(Re'
337 338 let mut oracle = AncestorOracle::new(is_ancestor);
338 339
339 340 for rev in revs {
340 // Retrieve data computed in a previous iteration
341 let copies = all_copies.remove(&rev);
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
352 for child in current_children {
353 // We will chain the copies information accumulated for `rev` with
354 // the individual copies information for each of its children.
355 // Creating a new PathCopies for each `rev` → `children` vertex.
356 let mut d: DataHolder<D> = DataHolder { data: None };
357 let (p1, p2, changes) = rev_info(*child, &mut d);
341 let mut d: DataHolder<D> = DataHolder { data: None };
342 let (p1, p2, changes) = rev_info(rev, &mut d);
358 343
359 let parent = if rev == p1 {
360 Parent::FirstParent
361 } else {
362 assert_eq!(rev, p2);
363 Parent::SecondParent
364 };
365 let new_copies =
366 add_from_changes(&copies, &changes, parent, *child);
344 // We will chain the copies information accumulated for the parent with
345 // the individual copies information the curent revision. Creating a
346 // new TimeStampedPath for each `rev` → `children` vertex.
347 let mut copies: Option<TimeStampedPathCopies> = None;
348 if p1 != NULL_REVISION {
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 );
367 382
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 }
381 Some(other_copies) => {
382 let (minor, major) = match parent {
383 Parent::FirstParent => (other_copies, new_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 }
390 };
383 copies = match copies {
384 None => Some(vertex_copies),
385 // Merge has two parents needs to combines their copy
386 // information.
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 )),
396 };
397 }
398 }
399 match copies {
400 Some(copies) => {
401 all_copies.insert(rev, copies);
402 }
403 _ => {}
391 404 }
392 405 }
393 406
@@ -405,6 +418,32 b' pub fn combine_changeset_copies<A: Fn(Re'
405 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 447 /// Combine ChangedFiles with some existing PathCopies information and return
409 448 /// the result
410 449 fn add_from_changes(
Show file before | Show file after | Hide comments
@@ -23,7 +23,7 b' use hg::Revision;'
23 23 pub fn combine_changeset_copies_wrapper(
24 24 py: Python,
25 25 revs: PyList,
26 children: PyDict,
26 children_count: PyDict,
27 27 target_rev: Revision,
28 28 rev_info: PyObject,
29 29 is_ancestor: PyObject,
@@ -93,20 +93,15 b' pub fn combine_changeset_copies_wrapper('
93 93
94 94 (p1, p2, files)
95 95 });
96 let children: PyResult<_> = children
96 let children_count: PyResult<_> = children_count
97 97 .items(py)
98 98 .iter()
99 .map(|(k, v)| {
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 })
99 .map(|(k, v)| Ok((k.extract(py)?, v.extract(py)?)))
105 100 .collect();
106 101
107 102 let res = combine_changeset_copies(
108 103 revs?,
109 children?,
104 children_count?,
110 105 target_rev,
111 106 rev_info_maker,
112 107 &is_ancestor_wrap,
General Comments 0
You need to be logged in to leave comments. Login now