GENERAL C >= D C is descendant of D, partial order C \haspatch D C contains changes from D, partial order Patch P has two sets P+, P- Ancestors A(C,P) = { Ca \elem C | Ca \elem P } Ends E(C,P) = maximal elements of A(C,P) Patch inclusion C \haspatch P <=> [ \forall D \elem P+: D \isin C <=> D <= C ] C \nothaspatch P <=> [ \forall D \elem P+: D \notisin C ] COMMIT ANNOTATIONS Commit C is annotated with: P(C) Either P s.t. C \elem P or _|_ meaning \notexists_{P} C \elem P. { Pi | C \haspatch Pi } ie the set of included patches For every Px, E(C,Px+) Implicitly for C \elem Pc+, E(C,Pc+) = { C } and this is not annotated explicitly. Also implicitly for P(C) = _|_, \forall_{Px} E(C,Px+) = { } and this is also not annotated explicitly. B(C) For C \elem P+: B s.t. E(C,P-) = { B } P(C) = P- or _|_: _|_ Of these in principle all except P(C) can be recalculated from the commit history, but that would involve a complete history scan and in the case of \haspatch is clearly impractical. At some point we may provide a checker/sanitiser that recalculates E(C,Px+) and B(C) from the commit history. SIMPLE COMMIT make C >1 { A } from A with contents D \isin C <=> D \isin A v D = C results P(C) = P(A) A \haspatch P <=> C \haspatch P For A \notelem Px+: E(C,Px+) = E(A,Px+) A \elem Px+: E(C,Px+) = { C } -- not annotated ANTICOMMIT make C >1 { L } from L, R+, R- with contents D \isin C <=> D \notelement Pr+ ^ D \isin L where P(R+) = Pr+, P(R-) = Pr- E(L,Pr+) = { R+ } -- nontrivial, may need R+' = merge of E(L,Pr+) B(R+) = R- L \haspatch Pr results P(C) = P(L) = Pl- If C \elem P+, B(C) = B(L); otherwise B(C) n/a For P = Pr: C \nothaspatch Pr E(C,Pr+) = E(L,Pr+) = { R+ } P != Pr: C \haspatch P <=> L \haspatch P E(C,P+) = E(L,P+) MERGE make C >1 { L, R } from L, R, M with contents D \isin C <=> [ (D \isin L ^ D \isin R) v D = C : T ] [ D \notisin L ^ D \notisin R ^ D != C : F ] [ otherwise : D \notisin M ] where M < L, M < R If L \elem P+: R \elem P+ ^ B(R) = B(L) -- only merge tips with same base v R \elem P- ^ R >= B(L) ^ M = B(L) -- base when merging into tip If L \elem P-: R \nothaspatch P If L \haspatch P <=/=> R \haspatch P: \forall Ce \elem E(R,P+): Ce <= L -- may need to merge E(R,P+) into L results P(C) = P(L) B(C) = For C \notelem P+: n/a C \elem P+, R \elem P+: B(L) = B(R) C \elem P+, R \notelem P+: R >= B(L) C \haspatch P = For L \nothaspatch P, R \nothaspatch P: F L \haspatch P, R \haspatch P: T otherwise: M \nothaspatch P E(C,P+) = maximal elements of E(L,P+) \union E(R,P+) = { Cl | \notexist Cr \elem E(R,P+): Cr >= Cl } \union { Cr | \notexist Cl \elem E(L,P+): Cl >= Cr } -- to reintroduce a dep, set P(C)=P(L)=Pl-, P(R)=Pr+, M=B(R) where L \notelem Pr obv. CREATE BASE make B >1 { L } from L, P where P(L) = Pl+ v P(L) = _|_ P(L) != P(B) E(B,P+) = { } with contents D \isin B <=> D \isin L v D = B results P(B) = Pb- B(C) n/a E(B,Px+) = E(L,Px+) B \haspatch P <=> L \haspatch P CREATE TIP make C >1 { B} from B where B \elem Pb- E(B,P+) = { } with contents D \isin C <=> D \isin B v D = C results P(C) = Pb+ B(C) = B C \haspatch P = For P != Pb: B \haspatch P P = Pb: T