THEORY

   1 GENERAL
   2
   3  C >= D                 C is descendant of D, partial order
   4  D \isin C              C contains changes from D, partial order
   5  Patch P has two sets P+, P-
   6  Ancestors A(C,P) = { Ca \elem P | Ca <= C }
   7  Ends E(C,P) = <=-maximal elements of A(C,P)
   8  Patch inclusion
   9    C \haspatch P    <=> [ \forall D \elem P+: D \isin C <=> D <= C ]
  10    C \nothaspatch P <=> [ \forall D \elem P+: D \notisin C ]
  11    and we maintain C \haspatch P v C \nothaspatch P
  12
  13 COMMIT ANNOTATIONS
  14
  15  Commit C is annotated with:
  16
  17  P(C)
  18    Either P s.t. C \elem P
  19    or _|_ meaning \notexists_{P} C \elem P.
  20
  21  { Pi | C \haspatch Pi }
  22    ie the set of included patches
  23
  24  For every Px, E(C,Px+)
  25    Implicitly for C \elem Pc+, E(C,Pc+) = { C }
  26    and this is not annotated explicitly.
  27    Also implicitly for P(C) = _|_, \forall_{Px} E(C,Px+) = { }
  28    and this is also not annotated explicitly.
  29
  30  B(C)
  31    For C \elem P+:       B s.t. E(C,P-) = { B }
  32        P(C) = P- or _|_: _|_
  33
  34  Of these in principle all except P(C) can be recalculated from the
  35  commit history, but that would involve a complete history scan and in
  36  the case of \haspatch is clearly impractical.  At some point we may
  37  provide a checker/sanitiser that recalculates E(C,Px+) and B(C) from
  38  the commit history.
  39
  40 SIMPLE COMMIT
  41
  42  make C >1 { A }
  43  from A
  44
  45  with contents
  46   D \isin C <=> D \isin A v D = C
  47
  48  results
  49   P(C) = P(A)
  50   A \haspatch P <=> C \haspatch P
  51   For A \notelem Px+: E(C,Px+) = E(A,Px+)
  52       A \elem Px+: E(C,Px+) = { C } -- not annotated
  53
  54 ANTICOMMIT
  55
  56  make C >1 { L }
  57  from L, R+, R-
  58
  59  with contents
  60   D \isin C <=> D \notelement Pr+ ^ D \isin L
  61
  62  where
  63   P(R+) = Pr+, P(R-) = Pr-
  64   E(L,Pr+) = { R+ }    -- nontrivial, may need R+' = merge of E(L,Pr+)
  65   B(R+) = R-
  66   L \haspatch Pr
  67
  68  results
  69   P(C) = P(L) = Pl-
  70   If C \elem P+, B(C) = B(L); otherwise B(C) n/a
  71   For P = Pr:  C \nothaspatch Pr
  72                E(C,Pr+) = E(L,Pr+) = { R+ }
  73       P != Pr: C \haspatch P <=> L \haspatch P
  74                E(C,P+) = E(L,P+)
  75
  76 MERGE
  77
  78  make C >1 { L, R }
  79  from L, R, M
  80
  81  with contents
  82   D \isin C <=> [ (D \isin    L ^ D \isin    R) v D =  C : T            ]
  83                 [  D \notisin L ^ D \notisin R  ^ D != C : F            ]
  84                 [  otherwise                             : D \notisin M ]
  85
  86  where
  87   M < L, M < R
  88   If L \elem P+:
  89       R \elem P+ ^ B(R) = B(L)            -- only merge tips with same base
  90     v R \elem P- ^ R >= B(L) ^ M = B(L)   -- base when merging into tip
  91   If L \elem P-:
  92       R \nothaspatch P
  93   If L \haspatch P <=/=> R \haspatch P:
  94       \forall Ce \elem E(R,P+): Ce <= L   -- may need to merge E(R,P+) into L
  95
  96  results
  97   P(C) = P(L)
  98   B(C) =
  99     For C \notelem P+:             n/a
 100         C \elem P+, R \elem P+:    B(L) = B(R)
 101         C \elem P+, R \notelem P+: R >= B(L)
 102
 103   C \haspatch P =
 104     For L \nothaspatch P, R \nothaspatch P: F
 105         L \haspatch P,    R \haspatch P:    T
 106         otherwise:                          M \nothaspatch P
 107   E(C,P+) = maximal elements of E(L,P+) \union E(R,P+)
 108           = { Cl | \notexist Cr \elem E(R,P+): Cr >= Cl } \union
 109             { Cr | \notexist Cl \elem E(L,P+): Cl >= Cr }
 110
 111  -- to reintroduce a dep, set P(C)=P(L)=Pl-, P(R)=Pr+, M=B(R)
 112     where L \notelem Pr obv.
 113
 114
 115 CREATE BASE
 116
 117  make B >1 { L }
 118  from L, P
 119
 120  where
 121   P(L) = Pl+ v P(L) = _|_
 122   P(L) != P(B)
 123   E(B,P+) = { }
 124
 125  with contents
 126   D \isin B <=> D \isin L v D = B
 127
 128  results
 129   P(B) = Pb-
 130   B(C) n/a
 131   E(B,Px+) = E(L,Px+)
 132   B \haspatch P <=> L \haspatch P
 133
 134
 135 CREATE TIP
 136
 137  make C >1 { B}
 138  from B
 139
 140  where
 141   B \elem Pb-
 142   E(B,P+) = { }
 143
 144  with contents
 145   D \isin C <=> D \isin B v D = C
 146
 147  results
 148   P(C) = Pb+
 149   B(C) = B
 150   C \haspatch P =
 151     For P != Pb: B \haspatch P
 152         P = Pb:  T