1 /*
2 Description: history graph computation
3
4 Author: Marco Costalba (C) 2005-2007
5
6 Copyright: See COPYING file that comes with this distribution
7
8 */
9 #include <QStringList>
10 #include "common.h"
11 #include "lanes.h"
12
13 #define IS_NODE(x) (x == NODE || x == NODE_R || x == NODE_L)
14
15 using namespace QGit;
16
init(const QString & expectedSha)17 void Lanes::init(const QString& expectedSha) {
18
19 clear();
20 activeLane = 0;
21 setBoundary(false);
22 add(BRANCH, expectedSha, activeLane);
23 }
24
clear()25 void Lanes::clear() {
26
27 typeVec.clear();
28 nextShaVec.clear();
29 }
30
setBoundary(bool b)31 void Lanes::setBoundary(bool b) {
32 // changes the state so must be called as first one
33
34 NODE = b ? BOUNDARY_C : MERGE_FORK;
35 NODE_R = b ? BOUNDARY_R : MERGE_FORK_R;
36 NODE_L = b ? BOUNDARY_L : MERGE_FORK_L;
37 boundary = b;
38
39 if (boundary)
40 typeVec[activeLane] = BOUNDARY;
41 }
42
isFork(const QString & sha,bool & isDiscontinuity)43 bool Lanes::isFork(const QString& sha, bool& isDiscontinuity) {
44
45 int pos = findNextSha(sha, 0);
46 isDiscontinuity = (activeLane != pos);
47 if (pos == -1) // new branch case
48 return false;
49
50 return (findNextSha(sha, pos + 1) != -1);
51 /*
52 int cnt = 0;
53 while (pos != -1) {
54 cnt++;
55 pos = findNextSha(sha, pos + 1);
56 // if (isDiscontinuity)
57 // isDiscontinuity = (activeLane != pos);
58 }
59 return (cnt > 1);
60 */
61 }
62
setFork(const QString & sha)63 void Lanes::setFork(const QString& sha) {
64
65 int rangeStart, rangeEnd, idx;
66 rangeStart = rangeEnd = idx = findNextSha(sha, 0);
67
68 while (idx != -1) {
69 rangeEnd = idx;
70 typeVec[idx] = TAIL;
71 idx = findNextSha(sha, idx + 1);
72 }
73 typeVec[activeLane] = NODE;
74
75 int& startT = typeVec[rangeStart];
76 int& endT = typeVec[rangeEnd];
77
78 if (startT == NODE)
79 startT = NODE_L;
80
81 if (endT == NODE)
82 endT = NODE_R;
83
84 if (startT == TAIL)
85 startT = TAIL_L;
86
87 if (endT == TAIL)
88 endT = TAIL_R;
89
90 for (int i = rangeStart + 1; i < rangeEnd; i++) {
91
92 int& t = typeVec[i];
93
94 if (t == NOT_ACTIVE)
95 t = CROSS;
96
97 else if (t == EMPTY)
98 t = CROSS_EMPTY;
99 }
100 }
101
setMerge(const QStringList & parents)102 void Lanes::setMerge(const QStringList& parents) {
103 // setFork() must be called before setMerge()
104
105 if (boundary)
106 return; // handle as a simple active line
107
108 int& t = typeVec[activeLane];
109 bool wasFork = (t == NODE);
110 bool wasFork_L = (t == NODE_L);
111 bool wasFork_R = (t == NODE_R);
112 bool startJoinWasACross = false, endJoinWasACross = false;
113
114 t = NODE;
115
116 int rangeStart = activeLane, rangeEnd = activeLane;
117 QStringList::const_iterator it(parents.constBegin());
118 for (++it; it != parents.constEnd(); ++it) { // skip first parent
119
120 int idx = findNextSha(*it, 0);
121 if (idx != -1) {
122
123 if (idx > rangeEnd) {
124
125 rangeEnd = idx;
126 endJoinWasACross = typeVec[idx] == CROSS;
127 }
128
129 if (idx < rangeStart) {
130
131 rangeStart = idx;
132 startJoinWasACross = typeVec[idx] == CROSS;
133 }
134
135 typeVec[idx] = JOIN;
136 } else
137 rangeEnd = add(HEAD, *it, rangeEnd + 1);
138 }
139 int& startT = typeVec[rangeStart];
140 int& endT = typeVec[rangeEnd];
141
142 if (startT == NODE && !wasFork && !wasFork_R)
143 startT = NODE_L;
144
145 if (endT == NODE && !wasFork && !wasFork_L)
146 endT = NODE_R;
147
148 if (startT == JOIN && !startJoinWasACross)
149 startT = JOIN_L;
150
151 if (endT == JOIN && !endJoinWasACross)
152 endT = JOIN_R;
153
154 if (startT == HEAD)
155 startT = HEAD_L;
156
157 if (endT == HEAD)
158 endT = HEAD_R;
159
160 for (int i = rangeStart + 1; i < rangeEnd; i++) {
161
162 int& t = typeVec[i];
163
164 if (t == NOT_ACTIVE)
165 t = CROSS;
166
167 else if (t == EMPTY)
168 t = CROSS_EMPTY;
169
170 else if (t == TAIL_R || t == TAIL_L)
171 t = TAIL;
172 }
173 }
174
setInitial()175 void Lanes::setInitial() {
176
177 int& t = typeVec[activeLane];
178 if (!IS_NODE(t) && t != APPLIED)
179 t = (boundary ? BOUNDARY : INITIAL);
180 }
181
setApplied()182 void Lanes::setApplied() {
183
184 // applied patches are not merges, nor forks
185 typeVec[activeLane] = APPLIED; // TODO test with boundaries
186 }
187
changeActiveLane(const QString & sha)188 void Lanes::changeActiveLane(const QString& sha) {
189
190 int& t = typeVec[activeLane];
191 if (t == INITIAL || isBoundary(t))
192 t = EMPTY;
193 else
194 t = NOT_ACTIVE;
195
196 int idx = findNextSha(sha, 0); // find first sha
197 if (idx != -1)
198 typeVec[idx] = ACTIVE; // called before setBoundary()
199 else
200 idx = add(BRANCH, sha, activeLane); // new branch
201
202 activeLane = idx;
203 }
204
afterMerge()205 void Lanes::afterMerge() {
206
207 if (boundary)
208 return; // will be reset by changeActiveLane()
209
210 for (int i = 0; i < typeVec.count(); i++) {
211
212 int& t = typeVec[i];
213
214 if (isHead(t) || isJoin(t) || t == CROSS)
215 t = NOT_ACTIVE;
216
217 else if (t == CROSS_EMPTY)
218 t = EMPTY;
219
220 else if (IS_NODE(t))
221 t = ACTIVE;
222 }
223 }
224
afterFork()225 void Lanes::afterFork() {
226
227 for (int i = 0; i < typeVec.count(); i++) {
228
229 int& t = typeVec[i];
230
231 if (t == CROSS)
232 t = NOT_ACTIVE;
233
234 else if (isTail(t) || t == CROSS_EMPTY)
235 t = EMPTY;
236
237 if (!boundary && IS_NODE(t))
238 t = ACTIVE; // boundary will be reset by changeActiveLane()
239 }
240 while (typeVec.last() == EMPTY) {
241 typeVec.pop_back();
242 nextShaVec.pop_back();
243 }
244 }
245
isBranch()246 bool Lanes::isBranch() {
247
248 return (typeVec[activeLane] == BRANCH);
249 }
250
afterBranch()251 void Lanes::afterBranch() {
252
253 typeVec[activeLane] = ACTIVE; // TODO test with boundaries
254 }
255
afterApplied()256 void Lanes::afterApplied() {
257
258 typeVec[activeLane] = ACTIVE; // TODO test with boundaries
259 }
260
nextParent(const QString & sha)261 void Lanes::nextParent(const QString& sha) {
262
263 nextShaVec[activeLane] = (boundary ? "" : sha);
264 }
265
findNextSha(const QString & next,int pos)266 int Lanes::findNextSha(const QString& next, int pos) {
267
268 for (int i = pos; i < nextShaVec.count(); i++)
269 if (nextShaVec[i] == next)
270 return i;
271 return -1;
272 }
273
findType(int type,int pos)274 int Lanes::findType(int type, int pos) {
275
276 for (int i = pos; i < typeVec.count(); i++)
277 if (typeVec[i] == type)
278 return i;
279 return -1;
280 }
281
add(int type,const QString & next,int pos)282 int Lanes::add(int type, const QString& next, int pos) {
283
284 // first check empty lanes starting from pos
285 if (pos < (int)typeVec.count()) {
286 pos = findType(EMPTY, pos);
287 if (pos != -1) {
288 typeVec[pos] = type;
289 nextShaVec[pos] = next;
290 return pos;
291 }
292 }
293 // if all lanes are occupied add a new lane
294 typeVec.append(type);
295 nextShaVec.append(next);
296 return typeVec.count() - 1;
297 }
298