2 Description: history graph computation
4 Author: Marco Costalba (C) 2005-2007
5 Copyright (C) 2008-2015 - TortoiseGit
7 Copyright: See COPYING file that comes with this distribution
13 #define IS_NODE(x) (x == NODE || x == NODE_R || x == NODE_L)
16 void Lanes::init(const CGitHash
& expectedSha
) {
20 bool wasEmptyCross
= false;
21 add(BRANCH
, expectedSha
, activeLane
, wasEmptyCross
);
29 void Lanes::setBoundary(bool b
) {
30 // changes the state so must be called as first one
32 NODE
= b
? BOUNDARY_C
: MERGE_FORK
;
33 NODE_R
= b
? BOUNDARY_R
: MERGE_FORK_R
;
34 NODE_L
= b
? BOUNDARY_L
: MERGE_FORK_L
;
38 typeVec
[activeLane
] = BOUNDARY
;
41 bool Lanes::isFork(const CGitHash
& sha
, bool& isDiscontinuity
) {
42 int pos
= findNextSha(sha
, 0);
43 isDiscontinuity
= (activeLane
!= pos
);
44 if (pos
== -1) // new branch case
47 return (findNextSha(sha
, pos
+ 1) != -1);
52 pos = findNextSha(sha, pos + 1);
53 // if (isDiscontinuity)
54 // isDiscontinuity = (activeLane != pos);
60 void Lanes::setFork(const CGitHash
& sha
) {
61 int rangeStart
, rangeEnd
, idx
;
62 rangeStart
= rangeEnd
= idx
= findNextSha(sha
, 0);
67 idx
= findNextSha(sha
, idx
+ 1);
69 typeVec
[activeLane
] = NODE
;
71 int& startT
= typeVec
[rangeStart
];
72 int& endT
= typeVec
[rangeEnd
];
86 for (int i
= rangeStart
+ 1; i
< rangeEnd
; ++i
) {
97 void Lanes::setMerge(const CGitHashList
& parents
) {
98 // setFork() must be called before setMerge()
101 return; // handle as a simple active line
103 int& t
= typeVec
[activeLane
];
104 bool wasFork
= (t
== NODE
);
105 bool wasFork_L
= (t
== NODE_L
);
106 bool wasFork_R
= (t
== NODE_R
);
107 bool startJoinWasACross
= false, endJoinWasACross
= false;
108 bool endWasEmptyCross
= false;
112 int rangeStart
= activeLane
, rangeEnd
= activeLane
;
113 CGitHashList::const_iterator
it(parents
.cbegin());
114 for (++it
; it
!= parents
.cend(); ++it
) { // skip first parent
116 int idx
= findNextSha(*it
, 0);
118 if (idx
> rangeEnd
) {
120 endJoinWasACross
= typeVec
[idx
] == CROSS
;
123 if (idx
< rangeStart
) {
125 startJoinWasACross
= typeVec
[idx
] == CROSS
;
131 rangeEnd
= add(HEAD
, *it
, rangeEnd
+ 1, endWasEmptyCross
);
133 int& startT
= typeVec
[rangeStart
];
134 int& endT
= typeVec
[rangeEnd
];
136 if (startT
== NODE
&& !wasFork
&& !wasFork_R
)
139 if (endT
== NODE
&& !wasFork
&& !wasFork_L
)
142 if (startT
== JOIN
&& !startJoinWasACross
)
145 if (endT
== JOIN
&& !endJoinWasACross
)
151 if (endT
== HEAD
&& !endWasEmptyCross
)
154 for (int i
= rangeStart
+ 1; i
< rangeEnd
; ++i
) {
155 int& t2
= typeVec
[i
];
157 if (t2
== NOT_ACTIVE
)
160 else if (t2
== EMPTY
)
163 else if (t2
== TAIL_R
|| t2
== TAIL_L
)
168 void Lanes::setInitial() {
169 int& t
= typeVec
[activeLane
];
170 if (!IS_NODE(t
) && t
!= APPLIED
)
171 t
= (boundary
? BOUNDARY
: INITIAL
);
174 void Lanes::setApplied() {
175 // applied patches are not merges, nor forks
176 typeVec
[activeLane
] = APPLIED
; // TODO test with boundaries
179 void Lanes::changeActiveLane(const CGitHash
& sha
) {
180 int& t
= typeVec
[activeLane
];
181 if (t
== INITIAL
|| isBoundary(t
))
186 int idx
= findNextSha(sha
, 0); // find first sha
188 typeVec
[idx
] = ACTIVE
; // called before setBoundary()
190 bool wasEmptyCross
= false;
191 idx
= add(BRANCH
, sha
, activeLane
, wasEmptyCross
); // new branch
197 void Lanes::afterMerge() {
199 return; // will be reset by changeActiveLane()
201 for (unsigned int i
= 0; i
< typeVec
.size(); ++i
) {
204 if (isHead(t
) || isJoin(t
) || t
== CROSS
)
207 else if (t
== CROSS_EMPTY
)
215 void Lanes::afterFork() {
216 for (unsigned int i
= 0; i
< typeVec
.size(); ++i
) {
222 else if (isTail(t
) || t
== CROSS_EMPTY
)
225 if (!boundary
&& IS_NODE(t
))
226 t
= ACTIVE
; // boundary will be reset by changeActiveLane()
228 while (typeVec
.back() == EMPTY
) {
230 nextShaVec
.pop_back();
234 bool Lanes::isBranch() {
235 return (typeVec
[activeLane
] == BRANCH
);
238 void Lanes::afterBranch() {
239 typeVec
[activeLane
] = ACTIVE
; // TODO test with boundaries
242 void Lanes::afterApplied() {
243 typeVec
[activeLane
] = ACTIVE
; // TODO test with boundaries
246 void Lanes::nextParent(const CGitHash
& sha
) {
248 nextShaVec
[activeLane
].Empty();
250 nextShaVec
[activeLane
] = sha
;
253 int Lanes::findNextSha(const CGitHash
& next
, int pos
) {
254 for (unsigned int i
= pos
; i
< nextShaVec
.size(); ++i
)
255 if (nextShaVec
[i
] == next
)
260 int Lanes::findType(int type
, int pos
) {
261 for (unsigned int i
= pos
; i
< typeVec
.size(); ++i
)
262 if (typeVec
[i
] == type
)
267 int Lanes::add(int type
, const CGitHash
& next
, int pos
, bool& wasEmptyCross
) {
268 wasEmptyCross
= false;
269 // first check empty lanes starting from pos
270 if (pos
< (int)typeVec
.size()) {
271 int posEmpty
= findType(EMPTY
, pos
);
272 int posCrossEmpty
= findType(CROSS_EMPTY
, pos
);
273 // Use first "empty" position.
274 if (posEmpty
!= -1 && posCrossEmpty
!= -1)
275 pos
= min(posEmpty
, posCrossEmpty
);
276 else if (posEmpty
!= -1)
278 else if (posCrossEmpty
!= -1)
284 wasEmptyCross
= (pos
== posCrossEmpty
);
287 nextShaVec
[pos
] = next
;
291 // if all lanes are occupied add a new lane
292 typeVec
.push_back(type
);
293 nextShaVec
.push_back(next
);
294 return (int)typeVec
.size() - 1;