Obsolescence Markers exchange

List of case and expected behavior when exchanging obsolesence marker

This page is intended for developer

Current strategy idea

Current idea

1. You want all markers relevant changeset common between source and destination to be exchanged 2. Marker relevant to a changeset are:

• marker that use this changeset as successors
• prune marker of direct children on this changeset.
• recursive application of the two rules on precursors store in those marker

?. What shall we do on partial split push…

recent idea

One of the big issue it the necessity to know actual changeset graph to perform the "prune marker of direct children on this changeset".

A radical idea is to store parent information of the precursors in all marker. But his mean a significant inflation of the size of marker. Matt Mackall does not like the idea (because of the extra size).

Pierre-Yves David suspect we could make all necessary computation by just storing parent information in prune marker only:

According to above definition we only care marker from a changeset if:

1) the successors is in the pushed set (actualy pushed or already common) 2) the successors is in a precursors of a marker we care about 3) this is prune marker and we care about the parent of the prune

This me we never need parent information elsewhere than one prune marker.

Graph Outline

    ○ ← a changeset,
    ◔ ← changeset being pushed
    ● ← changeset that exist remotly before the push.
    ◕ ← changeset that exist remotly but is not selected by the push
    ⊗ ← pruned changeset
    ø ← obsolete changeset with a precursors
    ◌ ← changeset that does not exist locally but are present in marker history
    ✕ ← changeset that does not exist locally but are pruned in marker history
    ⇠ ← obsolescence marker from that point (if not poiting to anything this mean we do not care about what is point to)

A. Simple Case

A.1 pushing a single heads

A.1.1 pushing a single head

    ⇠◔ A
     |
     ●  O

Marker exist from:

• A

Command run:

• hg push -r A
• hg push

Expected exchange:

• chain from A

A.1.2 pushing a multiple changeset into a single head

     ◔ B
     |
    ⇠◔ A
     |
     ● O

Marker exist from:

• A

Command run:

• hg push -r B
• hg push

Expected exchange:

• chain from A

A.2 Two heads

    ⇠○ B
  ⇠◔ | A
   |/
   ● O

Marker exist from:

• A
• B

Command run:

• hg push -r A

Expected exchange:

• chain from A

Expected Exclude:

• chain from B

A.3 new branch created

  B' ○⇢ø B
     | |
     \Aø⇠◔ A'
      \|/
       ● O

Marker exist from:

• Aø⇠○ A'

• Bø⇠○ B'

Command run:

• hg push -r A

Expected exchange:

• chain from A

Expected Exclude:

• chain from B

If A and B are remontly known, we should expect:

• hg push will complain about the new head

• hg push should complain about unstable history creation

A.4 Push in the middle of the obsolescence chain

(Where we show that we should not push the marker without the successors)

  B ◔
    |
  A⇠ø⇠○ A'
    |/
    ● O

Marker exist from:

• Aø⇠○ A'

• chain from A

Command run:

• hg push -r B

Expected exchange:

• Chain from A

Expected Exclude:

• Aø⇠○ A'

A.5 partial reordering

  B ø⇠⇠
    | ⇡
  A ø⇠⇠⇠○ A'
    | ⇡/
    | ○ B'
    |/
    ● O

Marker exist from:

• Aø⇠○ A'

• Bø⇠○ B'

Command run:

• hg push -r B

Expected exchange:

• Bø⇠○ B'

Expected Exclude:

• Aø⇠○ A'

A.6 between existing changeset

  A ◕⇠● B
    |/
    ● O

Marker exist from:

• A◕⇠● B

Command run:

• hg push -r B
• hg push

Expected exchange:

• A◕⇠● B

A.7 Non targeted common changeset

   ⇠◕ A
    |
    ● O

Marker exist from:

• Chain from A

Command run:

• hg push -r O

Expected exchange:

• ø

Expected exclude:

• Chain from A

B. Deletion Case

Most B case can be read with

B.1 Pruned changeset atop the pushed set

    ⊗ B
    |
    ◔ A
    |
    ● O

Marker exist from:

• B (prune)

Command run:

• hg push -r A
• hg push

Expected exchange:

• prune marker for B

B.2 Pruned changeset on head. nothing pushed

    ⊗ A
    |
    ● O

Marker exist from:

• A (prune)

Command run:

• hg push -r O
• hg push

Expected exchange:

• prune marker for A

B.3 Pruned changeset on non-pushed part of the history

  ⊗ C
  |
  ○ B
  | ◔ A
  |/
  ● O

Marker exist from:

• C (prune)

Command run:

• hg push -r A
• hg push

Expected exchange:

• ø

Expected Exclude:

• chain from B

B.4 Pruned changeset on common part of history

  ⊗ C
  | ● B
  | |
  | ● A
  |/
  ● O

Marker exist from:

• C (prune)

Command run:

• hg push -r B
• hg push

Expected exchange:

• prune for C

B.5 Push of a children of changeset which successors is pruned

This case Mirror A.4, with pruned changeset successors.

  B ◔
    |
  A⇠ø⇠⊗ A'
    |/
    ● O

Marker exist from:

• Aø⇠○ A'

• chain from A

• A'

Command run:

• hg push -r B

Expected exchange:

• Aø⇠○ A'

• chain from A

• A'

Extra Note:

• I'm not totally happy about this case and I believe some more complicated graph can result in behavior wuite confusing for the user (if some tool create prune maker in a the middle of a valid chain)

B.6 Pruned changeset with ancestors not in pushed set

  B ø⇠⊗ B'
    | |
  A ○ |
    |/
    ● O

Marker exist from:

• Bø⇠⊗ B'

• B' prune

Command run:

• hg push -r O

Expected exchange:

• Bø⇠⊗ B'

• B' prune

B.7 Prune on non targeted common changeset

    ⊗ B
    |
    ◕ A
    |
    ● O

Marker exist from:

• B (prune)

Command run:

• hg push -r O

Expected exchange:

• ø

C. Advance Case

C.1 Multiple pruned changeset atop each other

  ⊗ B
  |
  ⊗ A
  |
  ● O

Marker exist from:

• A (prune)
• B (prune)

Command run:

• hg push -r O
• hg push

Expected exchange:

• A (prune)
• B (prune)

C.2 Pruned changeset on precursors

  B ⊗
    |
  A ø⇠◔ A'
    |/
    ● O

Marker exist from:

• A' succeed to A
• B (prune)

Command run:

• hg push -r A'
• hg push

Expected exchange:

• A ø⇠o A'

• B (prune)

C.3 Pruned changeset on precursors of another pruned one

  B ⊗
    |
  A ø⇠⊗ A'
    |/
    ● O

Marker exist from:

• A' succeed to A
• A' (prune
• B (prune)

Command run:

• hg push -r A'
• hg push

Expected exchange:

• A ø⇠⊗ A'

• A (prune)
• B (prune)

C.4 multiple successors, one is pruned

Another case were prune are confusing? (A is killed without its successors being pushed)

(could split of divergence, if split see the Z section)

       A
   B ○⇢ø⇠⊗ C
      \|/
       ● O

Marker exist from:

• A ø⇠○ B

• A ø⇠○ C

• C (prune)

Command run:

• hg push -r O

Expected exchange:

• A ø⇠○ C

• C (prune)

Expected exclude:

• A ø⇠○ B

D. Partial Information Case

From then we have changeset missing from the repo but still referenced in obsolescence marker. This has an impact on the knowledge we have from the graph topology.

About any of the above Case could be used too, just drop local knownledge of some/all obsolete changeset.

D.1 Pruned changeset based on a missing precursors of something we push

  B ⊗
    |
  A ◌⇠◔ A'
     /
    ● O

Marker exist from:

• A' succeed to A
• B (prune)

Command run:

• hg push -r A'
• hg push

Expected exchange:

• A ø⇠o A'

• B (prune)

D.2 missing prune target (prune in "pushed set")

  A ø⇠✕ A'
    |/
    ● O

Marker exist from:

• A' succeed to A
• A' (prune)

Command run:

• hg push

Expected exchange:

• A ø⇠o A'

• A' (prune)

D.3 missing prune target (prune Not in "pushed set")

(this is one of the case were is will be hard to be non-confusing)

  A ø⇠✕ A'
    | |
    | ○ B
    |/
    ● O

Marker exist from:

• A' succeed to A
• A' (prune)

Command run:

• hg push -r O

(shall we account for a secret B?

Expected exchange:

• nothing?

D.4 Unknown changeset in between known one

Mostly a clarification case

    ø⇠◌⇠○
    | |/
    | ◔
    |/
    ● O

Should be treated as A.3 case:

    ø⇠○
    | |
    | ◔
    |/
    ● O

D.5 Unknown changeset in between known one

Z. Crazy case

When I'm note very sure about what we should do

Z.1 partial push of split

   D'○⇢ø D
     | | A
   B ○⇢ø⇠◔ C
      \|/
       ● O

Marker exist from:

• A ø⇠⚭ (B,C) (split)

• D ø⇠○ D'

Command run:

• hg push -r C

Expected exchange:

• We should probably send the whole marker anyway. But what about things related to B children

• A ø⇠⚭ (B,C) (split)

Expected exclude:

• D ø⇠○ D'