invariants.tex

   1 \section{Invariants}
   2
   3 We maintain these each time we construct a new commit. \\
   4 \[ \eqn{No Replay:}{
   5   C \has D \implies C \ge D
   6 }\]
   7 \[\eqn{Unique Base:}{
   8  \bigforall_{C \in \py} \pendsof{C}{\pn} = \{ B \}
   9 }\]
  10 \[\eqn{Tip Contents:}{
  11   \bigforall_{C \in \py} D \isin C \equiv
  12     { D \isin \baseof{C} \lor \atop
  13       (D \in \py \land D \le C) }
  14 }\]
  15 \[\eqn{Base Acyclic:}{
  16   \bigforall_{C \in \pn} D \isin C \implies D \notin \py
  17 }\]
  18 \[\eqn{Coherence:}{
  19   \bigforall_{C,\p} C \haspatch \p \lor C \nothaspatch \p
  20 }\]
  21 \[\eqn{Foreign Inclusion:}{
  22   \bigforall_{D \text{ s.t. } \patchof{D} = \bot} D \isin C \equiv D \leq C
  23 }\]
  24 \[\eqn{Foreign Contents:}{
  25   \bigforall_{C \text{ s.t. } \patchof{C} = \bot}
  26     D \le C \implies \patchof{D} = \bot
  27 }\]
  28
  29 A commit $C$ which satisfies all of the above is said to be
  30 ``conformant''.
  31
  32 For each operation we will perform which generates a new commit, we
  33 will assume the conformance of the existing history and prove the
  34 conformance of the new commit.