|
1 .. Copyright 2014 Greg Ward <greg@gerg.ca> |
|
2 |
|
3 ---------------- |
|
4 Evolve: Concepts |
|
5 ---------------- |
|
6 |
|
7 Getting the most out of software requires an accurate understanding of |
|
8 the concepts underlying it. For example, you cannot use Mercurial to |
|
9 its full potential without understanding the DAG (directed acyclic |
|
10 graph) of changesets and the meaning of parent/child relationships |
|
11 between nodes in that graph. Mercurial with changeset evolution adds |
|
12 some additional concepts to the graph of changesets. Understanding |
|
13 those concepts will make you an informed and empowered user of |
|
14 ``evolve``. |
|
15 |
|
16 .. note:: This document contains math! If you have a pathological fear |
|
17 of set theory and the associated notation, you might be |
|
18 better off just reading the `user guide`_. But if you |
|
19 appreciate the theoretical rigour underlying core Mercurial, |
|
20 you will be happy to know that it continues right into |
|
21 changeset evolution. |
|
22 |
|
23 .. note:: This document is incomplete! (The formatting of the math |
|
24 isn't quite right yet, and the diagrams are missing for |
|
25 malformatted.) |
|
26 |
|
27 This document follows standard set theory notation: |
|
28 |
|
29 x ∈ A: x is a member of A |
|
30 |
|
31 A ∪ B: union of A and B: { x | x ∈ A or x ∈ B } |
|
32 |
|
33 A ∖ B: set difference: { x | x ∈ A and x ∉ B } |
|
34 |
|
35 A ⊇ B: superset: if x ∈ B, then x ∈ A |
|
36 |
|
37 .. _`user guide`: user-guide.html |
|
38 |
|
39 Phases |
|
40 ------ |
|
41 |
|
42 First, every changeset in a Mercurial repository (since 2.3) has a |
|
43 *phase*. Phases are independent of ``evolve`` and they affect |
|
44 Mercurial usage with or without changeset evolution. However, they |
|
45 were implemented in order to support evolution, and are a critical |
|
46 foundation of ``evolve``. |
|
47 |
|
48 Phases are strictly ordered: |
|
49 |
|
50 secret > draft > public |
|
51 |
|
52 Changesets generally only move from a higher phase to a lower phase. |
|
53 Typically, changesets start life in *draft* phase, and move to |
|
54 *public* phase when they are pushed to a public repository. (You can |
|
55 set the default phase of new commits in Mercurial configuration.) |
|
56 |
|
57 The purpose of phases is to prevent modifying published history. |
|
58 ``evolve`` will therefore only let you rewrite changesets in one of |
|
59 the two *mutable* phases (secret or draft). |
|
60 |
|
61 Run ``hg help phases`` for more information on phases. |
|
62 |
|
63 Obsolete changesets |
|
64 ------------------- |
|
65 |
|
66 *Obsolescence* is they key concept at the heart of changeset |
|
67 evolution. Everything else in this document depends on understanding |
|
68 obsolescence. So: what does it mean for a changeset to be obsolete? |
|
69 |
|
70 In implementation terms, there is an *obsolescence marker* associated |
|
71 with changesets: every changeset is either obsolete or not. |
|
72 |
|
73 The simplest way that a changeset becomes obsolete is by *pruning* it. |
|
74 The ``hg prune`` command simply marks the specified changesets |
|
75 obsolete, as long as they are mutable. |
|
76 |
|
77 More commonly, a changeset *A* becomes obsolete by *amending* it. |
|
78 Amendment creates a new changeset *A'* that replaces *A*, which is now |
|
79 obsolete. *A'* is the successor of *A*, and *A* the predecessor of *A'*: |
|
80 |
|
81 [diagram: A and A' with pred/succ edge] |
|
82 |
|
83 The predecessor/successor relationship forms an additional |
|
84 *obsolescence graph* overlaid on top of the traditional DAG formed by |
|
85 changesets and their parent/child relationships. In fact, the |
|
86 obsolescence graph is second-order version control. Where the |
|
87 traditional parent/child DAG tracks changes to your source code, the |
|
88 obsolescence graph tracks changes to your changesets. It tracks the |
|
89 evolution of your changesets. |
|
90 |
|
91 (If you prefer a calculus metaphor to set theory, it might help to |
|
92 think of the traditional parent/child DAG as the first derivative of |
|
93 your source code, and the obsolescence DAG as the second derivative.) |
|
94 |
|
95 Troubled changesets (unstable, bumped, divergent) |
|
96 ------------------------------------------------- |
|
97 |
|
98 Evolving history can introduce problems that need to be solved. For |
|
99 example, if you prune a changeset *P* but not its descendants, those |
|
100 descendants are now on thin ice. To push a changeset to another |
|
101 repository *R*, all of its ancestors must be present in *R* or pushed |
|
102 at the same time. But Mercurial does not push obsolete changesets like |
|
103 *P*, so it cannot push the descendants of *P*. Any non-obsolete |
|
104 changeset that is a descendant of an obsolete changeset is said to be |
|
105 *unstable*. |
|
106 |
|
107 [diagram: obsolete cset with non-obsolete descendant] |
|
108 |
|
109 Another sort of trouble occurs when two developers, Alice and Bob, |
|
110 collaborate via a shared non-publishing repository. (This is how |
|
111 developers can safely `share mutable history`_.) Say Alice and Bob |
|
112 both start the day with changeset *C* in *draft* phase. If Alice |
|
113 pushes *C* to their public repository, then it is now published and |
|
114 therefore immutable. But Bob is working from a desert island and |
|
115 cannot pull this change in *C*'s phase. For Bob, *C* is still in draft |
|
116 phase and therefore mutable. So Bob amends *C*, which marks it |
|
117 obsolete and replaces it with *C'*. When he is back online and pulls |
|
118 from the public repository, Mercurial learns that *C* is public, which |
|
119 means it cannot be obsolete. We say that *C'* is *bumped*, since it is |
|
120 the successor of a public changeset. |
|
121 |
|
122 .. _`share mutable history`: sharing.html |
|
123 |
|
124 (Incidentally, the terminology here comes from airline overbooking: if |
|
125 two people have bought tickets for the same seat on a plane and they |
|
126 both show up at the airport, only one of them gets on the plane. The |
|
127 passenger who is left behind in the airport terminal has been |
|
128 "bumped".) |
|
129 |
|
130 The third sort of trouble is when Alice and Bob both amend the same |
|
131 changeset *C* to have different successors. When this happens, the |
|
132 successors are both called *divergent* (unless one of them is in |
|
133 public phase; only mutable changesets are divergent). |
|
134 |
|
135 The collective term for unstable, bumped, and divergent changeset is |
|
136 *troubled*: |
|
137 |
|
138 troubled = unstable ∪ bumped ∪ divergent |
|
139 |
|
140 It is possible for a changeset to be in any of the troubled categories |
|
141 at the same time: it might be unstable and divergent, or bumped and |
|
142 divergent, or whatever. |
|
143 |
|
144 [diagram: Venn diagram of troubled changesets, showing overlap] |
|
145 |
|
146 The presence of troubled changesets indicates the need to run ``hg |
|
147 evolve``. |
|
148 |
|
149 Hidden (and visible) changesets |
|
150 ------------------------------- |
|
151 |
|
152 Some obsolete changesets are *hidden*: deliberately suppressed by |
|
153 Mercurial and usually not visible through the UI. (As of Mercurial |
|
154 2.9, there are still some commands that inadvertently reveal hidden |
|
155 changesets; these are bugs and will be fixed in due course.) |
|
156 |
|
157 All hidden changesets are obsolete, and all obsolete changesets are |
|
158 part of your repository. Mathematically speaking: |
|
159 |
|
160 repo ⊇ obsolete ⊇ hidden |
|
161 |
|
162 Or, putting it visually: |
|
163 |
|
164 [diagram: Venn diagram showing nested strict subsets] |
|
165 |
|
166 However, the presence of obsolete but not hidden changesets should be |
|
167 temporary. The desired end state for any history mutation operation is |
|
168 that all obsolete changesets are hidden, i.e.: |
|
169 |
|
170 repo ⊇ obsolete, obsolete = hidden |
|
171 |
|
172 Visually: |
|
173 |
|
174 [diagram: Venn diagram showing obsolete = hidden, subset of repo] |
|
175 |
|
176 |
|
177 Why is this changeset visible? |
|
178 ------------------------------ |
|
179 |
|
180 Any changeset which is not hidden is *visible*. That is, |
|
181 |
|
182 visible = repo ∖ hidden |
|
183 |
|
184 (Recall that ∖ means set difference: *visible* is the set of |
|
185 changesets that are in *repo* but not in *hidden*.) |
|
186 |
|
187 After amending or pruning a changeset, you might expect it to be |
|
188 hidden. It doesn't always work out that way. The precise rules are: |
|
189 |
|
190 hideable = obsolete |
|
191 blockers = bookmarks ∪ parents(workingcopy) ∪ localtags |
|
192 hidden = hideable ∖ ancestors((repo ∖ hideable) ∪ blockers) |
|
193 |
|
194 This will probably be clearer with a worked example. First, here's a |
|
195 repository with some obsolete changesets, some troubled changesets, |
|
196 one bookmark, a working copy, and some hidden changesets: |
|
197 |
|
198 x-x |
|
199 / |
|
200 -o-o-o-o |
|
201 \ |
|
202 x-x-o |
|
203 |
|
204 Here's the computation required to determine which changesets are |
|
205 hidden: |
|
206 |
|
207 repo = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } |
|
208 |
|
209 hideable = obsolete = { 2, 4, 5, 8 } |
|
210 |
|
211 blockers = { 6 } ∪ { 4 } ∪ {} |
|
212 |
|
213 blockers = { 4, 6 } |
|
214 |
|
215 hidden = hideable ∖ ancestors((repo ∖ { 2, 4, 5, 8 }) ∪ { 4, 6 }) |
|
216 |
|
217 hidden = hideable ∖ ancestors({ 0, 1, 3, 6, 7 } ∪ { 4, 6 }) |
|
218 |
|
219 hidden = hideable ∖ ancestors({ 0, 1, 3, 4, 6, 7 }) |
|
220 |
|
221 hidden = { 2, 4, 5, 8 } ∖ { 0, 1, 2, 3, 4, 5, 6, 7 } |
|
222 |
|
223 hidden = { 8 } |