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 "lanes.h" |
10 | |
11 | #include <QStringList> |
12 | |
13 | void Lanes::init(const QString &expectedSha) |
14 | { |
15 | clear(); |
16 | activeLane = 0; |
17 | add(LaneType::BRANCH, expectedSha, activeLane); |
18 | } |
19 | |
20 | void Lanes::clear() |
21 | { |
22 | typeVec.clear(); |
23 | typeVec.squeeze(); |
24 | nextShaVec.clear(); |
25 | nextShaVec.squeeze(); |
26 | } |
27 | |
28 | bool Lanes::isFork(const QString &sha, bool &isDiscontinuity) |
29 | { |
30 | int pos = findNextSha(sha, 0); |
31 | isDiscontinuity = activeLane != pos; |
32 | |
33 | return pos == -1 ? false : findNextSha(sha, pos + 1) != -1; |
34 | } |
35 | |
36 | void Lanes::setFork(const QString &sha) |
37 | { |
38 | auto rangeEnd = 0; |
39 | auto idx = 0; |
40 | auto rangeStart = rangeEnd = idx = findNextSha(sha, 0); |
41 | |
42 | while (idx != -1) |
43 | { |
44 | rangeEnd = idx; |
45 | typeVec[idx].setType(LaneType::TAIL); |
46 | idx = findNextSha(sha, idx + 1); |
47 | } |
48 | |
49 | typeVec[activeLane].setType(NODE); |
50 | |
51 | auto &startT = typeVec[rangeStart]; |
52 | auto &endT = typeVec[rangeEnd]; |
53 | |
54 | if (startT.equals(NODE)) |
55 | startT.setType(NODE_L); |
56 | |
57 | if (endT.equals(NODE)) |
58 | endT.setType(NODE_R); |
59 | |
60 | if (startT.equals(LaneType::TAIL)) |
61 | startT.setType(LaneType::TAIL_L); |
62 | |
63 | if (endT.equals(LaneType::TAIL)) |
64 | endT.setType(LaneType::TAIL_R); |
65 | |
66 | for (int i = rangeStart + 1; i < rangeEnd; ++i) |
67 | { |
68 | switch (auto &t = typeVec[i]; t.getType()) |
69 | { |
70 | case LaneType::NOT_ACTIVE: |
71 | t.setType(LaneType::CROSS); |
72 | break; |
73 | case LaneType::EMPTY: |
74 | t.setType(LaneType::CROSS_EMPTY); |
75 | break; |
76 | default: |
77 | break; |
78 | } |
79 | } |
80 | } |
81 | |
82 | void Lanes::setMerge(const QStringList &parents) |
83 | { |
84 | auto &t = typeVec[activeLane]; |
85 | auto wasFork = t.equals(NODE); |
86 | auto wasFork_L = t.equals(NODE_L); |
87 | auto wasFork_R = t.equals(NODE_R); |
88 | auto startJoinWasACross = false; |
89 | auto endJoinWasACross = false; |
90 | |
91 | t.setType(NODE); |
92 | |
93 | auto rangeStart = activeLane; |
94 | auto rangeEnd = activeLane; |
95 | QStringList::const_iterator it(parents.constBegin()); |
96 | |
97 | for (++it; it != parents.constEnd(); ++it) |
98 | { // skip first parent |
99 | int idx = findNextSha(*it, 0); |
100 | |
101 | if (idx != -1) |
102 | { |
103 | if (idx > rangeEnd) |
104 | { |
105 | rangeEnd = idx; |
106 | endJoinWasACross = typeVec[idx].equals(LaneType::CROSS); |
107 | } |
108 | |
109 | if (idx < rangeStart) |
110 | { |
111 | rangeStart = idx; |
112 | startJoinWasACross = typeVec[idx].equals(LaneType::CROSS); |
113 | } |
114 | |
115 | typeVec[idx].setType(LaneType::JOIN); |
116 | } |
117 | else |
118 | rangeEnd = add(LaneType::HEAD, *it, rangeEnd + 1); |
119 | } |
120 | |
121 | auto &startT = typeVec[rangeStart]; |
122 | auto &endT = typeVec[rangeEnd]; |
123 | |
124 | if (startT.equals(NODE) && !wasFork && !wasFork_R) |
125 | startT.setType(NODE_L); |
126 | |
127 | if (endT.equals(NODE) && !wasFork && !wasFork_L) |
128 | endT.setType(NODE_R); |
129 | |
130 | if (startT.equals(LaneType::JOIN) && !startJoinWasACross) |
131 | startT.setType(LaneType::JOIN_L); |
132 | |
133 | if (endT.equals(LaneType::JOIN) && !endJoinWasACross) |
134 | endT.setType(LaneType::JOIN_R); |
135 | |
136 | if (startT.equals(LaneType::HEAD)) |
137 | startT.setType(LaneType::HEAD_L); |
138 | |
139 | if (endT.equals(LaneType::HEAD)) |
140 | endT.setType(LaneType::HEAD_R); |
141 | |
142 | for (int i = rangeStart + 1; i < rangeEnd; i++) |
143 | { |
144 | auto &t = typeVec[i]; |
145 | |
146 | if (t.equals(LaneType::NOT_ACTIVE)) |
147 | t.setType(LaneType::CROSS); |
148 | else if (t.equals(LaneType::EMPTY)) |
149 | t.setType(LaneType::CROSS_EMPTY); |
150 | else if (t.equals(LaneType::TAIL_R) || t.equals(LaneType::TAIL_L)) |
151 | t.setType(LaneType::TAIL); |
152 | } |
153 | } |
154 | |
155 | void Lanes::setInitial() |
156 | { |
157 | auto &t = typeVec[activeLane]; |
158 | |
159 | if (!isNode(t)) |
160 | t.setType(LaneType::INITIAL); |
161 | } |
162 | |
163 | void Lanes::changeActiveLane(const QString &sha) |
164 | { |
165 | auto &t = typeVec[activeLane]; |
166 | |
167 | if (t.equals(LaneType::INITIAL)) |
168 | t.setType(LaneType::EMPTY); |
169 | else |
170 | t.setType(LaneType::NOT_ACTIVE); |
171 | |
172 | int idx = findNextSha(sha, 0); |
173 | if (idx != -1) |
174 | typeVec[idx].setType(LaneType::ACTIVE); |
175 | else |
176 | idx = add(LaneType::BRANCH, sha, activeLane); |
177 | |
178 | activeLane = idx; |
179 | } |
180 | |
181 | void Lanes::afterMerge() |
182 | { |
183 | for (int i = 0; i < typeVec.count(); i++) |
184 | { |
185 | auto &t = typeVec[i]; |
186 | |
187 | if (t.isHead() || t.isJoin() || t.equals(LaneType::CROSS)) |
188 | t.setType(LaneType::NOT_ACTIVE); |
189 | else if (t.equals(LaneType::CROSS_EMPTY)) |
190 | t.setType(LaneType::EMPTY); |
191 | else if (isNode(t)) |
192 | t.setType(LaneType::ACTIVE); |
193 | } |
194 | } |
195 | |
196 | void Lanes::afterFork() |
197 | { |
198 | for (int i = 0; i < typeVec.count(); i++) |
199 | { |
200 | auto &t = typeVec[i]; |
201 | |
202 | if (t.equals(LaneType::CROSS)) |
203 | t.setType(LaneType::NOT_ACTIVE); |
204 | else if (t.isTail() || t.equals(LaneType::CROSS_EMPTY)) |
205 | t.setType(LaneType::EMPTY); |
206 | |
207 | if (isNode(t)) |
208 | t.setType(LaneType::ACTIVE); |
209 | } |
210 | |
211 | while (typeVec.last().equals(LaneType::EMPTY)) |
212 | { |
213 | typeVec.pop_back(); |
214 | nextShaVec.pop_back(); |
215 | } |
216 | } |
217 | |
218 | bool Lanes::isBranch() |
219 | { |
220 | if (typeVec.count() > activeLane) |
221 | return typeVec.at(activeLane).equals(LaneType::BRANCH); |
222 | |
223 | return false; |
224 | } |
225 | |
226 | void Lanes::afterBranch() |
227 | { |
228 | typeVec[activeLane].setType(LaneType::ACTIVE); |
229 | } |
230 | |
231 | void Lanes::nextParent(const QString &sha) |
232 | { |
233 | nextShaVec[activeLane] = sha; |
234 | } |
235 | |
236 | int Lanes::findNextSha(const QString &next, int pos) |
237 | { |
238 | for (int i = pos; i < nextShaVec.count(); i++) |
239 | { |
240 | if (nextShaVec[i] == next) |
241 | return i; |
242 | } |
243 | |
244 | return -1; |
245 | } |
246 | |
247 | int Lanes::findType(const LaneType type, int pos) |
248 | { |
249 | const auto typeVecCount = typeVec.count(); |
250 | |
251 | for (int i = pos; i < typeVecCount; i++) |
252 | { |
253 | if (typeVec[i].equals(type)) |
254 | return i; |
255 | } |
256 | |
257 | return -1; |
258 | } |
259 | |
260 | int Lanes::add(const LaneType type, const QString &next, int pos) |
261 | { |
262 | if (pos < typeVec.count()) |
263 | { |
264 | pos = findType(LaneType::EMPTY, pos); |
265 | if (pos != -1) |
266 | { |
267 | typeVec[pos].setType(type); |
268 | nextShaVec[pos] = next; |
269 | return pos; |
270 | } |
271 | } |
272 | |
273 | typeVec.append(type); |
274 | nextShaVec.append(next); |
275 | return typeVec.count() - 1; |
276 | } |
277 | |
278 | bool Lanes::isNode(Lane lane) const |
279 | { |
280 | return lane.equals(NODE) || lane.equals(NODE_R) || lane.equals(NODE_L); |
281 | } |
282 | |