src/TortoiseProc/lanes.cpp

   1 /*
   2         Description: history graph computation
   3
   4         Author: Marco Costalba (C) 2005-2007
   5         Copyright (C) 2008-2015 - TortoiseGit
   6
   7         Copyright: See COPYING file that comes with this distribution
   8
   9 */
  10 #include "stdafx.h"
  11 #include "lanes.h"
  12
  13 #define IS_NODE(x) (x == NODE || x == NODE_R || x == NODE_L)
  14
  15
  16 void Lanes::init(const CGitHash& expectedSha) {
  17
  18         clear();
  19         activeLane = 0;
  20         setBoundary(false);
  21         bool wasEmptyCross = false;
  22         add(BRANCH, expectedSha, activeLane, wasEmptyCross);
  23 }
  24
  25 void Lanes::clear() {
  26
  27         typeVec.clear();
  28         nextShaVec.clear();
  29 }
  30
  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
  43 bool Lanes::isFork(const CGitHash& 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
  63 void Lanes::setFork(const CGitHash& 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
 102 void Lanes::setMerge(const CGitHashList& 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         bool endWasEmptyCross = false;
 114
 115         t = NODE;
 116
 117         int rangeStart = activeLane, rangeEnd = activeLane;
 118         CGitHashList::const_iterator it(parents.begin());
 119         for (++it; it != parents.end(); ++it) { // skip first parent
 120
 121                 int idx = findNextSha(*it, 0);
 122                 if (idx != -1) {
 123
 124                         if (idx > rangeEnd) {
 125
 126                                 rangeEnd = idx;
 127                                 endJoinWasACross = typeVec[idx] == CROSS;
 128                         }
 129
 130                         if (idx < rangeStart) {
 131
 132                                 rangeStart = idx;
 133                                 startJoinWasACross = typeVec[idx] == CROSS;
 134                         }
 135
 136                         typeVec[idx] = JOIN;
 137                 }
 138                 else
 139                         rangeEnd = add(HEAD, *it, rangeEnd + 1, endWasEmptyCross);
 140         }
 141         int& startT = typeVec[rangeStart];
 142         int& endT = typeVec[rangeEnd];
 143
 144         if (startT == NODE && !wasFork && !wasFork_R)
 145                 startT = NODE_L;
 146
 147         if (endT == NODE && !wasFork && !wasFork_L)
 148                 endT = NODE_R;
 149
 150         if (startT == JOIN && !startJoinWasACross)
 151                 startT = JOIN_L;
 152
 153         if (endT == JOIN && !endJoinWasACross)
 154                 endT = JOIN_R;
 155
 156         if (startT == HEAD)
 157                 startT = HEAD_L;
 158
 159         if (endT == HEAD && !endWasEmptyCross)
 160                 endT = HEAD_R;
 161
 162         for (int i = rangeStart + 1; i < rangeEnd; ++i) {
 163
 164                 int& t2 = typeVec[i];
 165
 166                 if (t2 == NOT_ACTIVE)
 167                         t2 = CROSS;
 168
 169                 else if (t2 == EMPTY)
 170                         t2 = CROSS_EMPTY;
 171
 172                 else if (t2 == TAIL_R || t2 == TAIL_L)
 173                         t2 = TAIL;
 174         }
 175 }
 176
 177 void Lanes::setInitial() {
 178
 179         int& t = typeVec[activeLane];
 180         if (!IS_NODE(t) && t != APPLIED)
 181                 t = (boundary ? BOUNDARY : INITIAL);
 182 }
 183
 184 void Lanes::setApplied() {
 185
 186         // applied patches are not merges, nor forks
 187         typeVec[activeLane] = APPLIED; // TODO test with boundaries
 188 }
 189
 190 void Lanes::changeActiveLane(const CGitHash& sha) {
 191
 192         int& t = typeVec[activeLane];
 193         if (t == INITIAL || isBoundary(t))
 194                 t = EMPTY;
 195         else
 196                 t = NOT_ACTIVE;
 197
 198         int idx = findNextSha(sha, 0); // find first sha
 199         if (idx != -1)
 200                 typeVec[idx] = ACTIVE; // called before setBoundary()
 201         else {
 202                 bool wasEmptyCross = false;
 203                 idx = add(BRANCH, sha, activeLane, wasEmptyCross); // new branch
 204         }
 205
 206         activeLane = idx;
 207 }
 208
 209 void Lanes::afterMerge() {
 210
 211         if (boundary)
 212                 return; // will be reset by changeActiveLane()
 213
 214         for (unsigned int i = 0; i < typeVec.size(); ++i) {
 215
 216                 int& t = typeVec[i];
 217
 218                 if (isHead(t) || isJoin(t) || t == CROSS)
 219                         t = NOT_ACTIVE;
 220
 221                 else if (t == CROSS_EMPTY)
 222                         t = EMPTY;
 223
 224                 else if (IS_NODE(t))
 225                         t = ACTIVE;
 226         }
 227 }
 228
 229 void Lanes::afterFork() {
 230
 231         for (unsigned int i = 0; i < typeVec.size(); ++i) {
 232
 233                 int& t = typeVec[i];
 234
 235                 if (t == CROSS)
 236                         t = NOT_ACTIVE;
 237
 238                 else if (isTail(t) || t == CROSS_EMPTY)
 239                         t = EMPTY;
 240
 241                 if (!boundary && IS_NODE(t))
 242                         t = ACTIVE; // boundary will be reset by changeActiveLane()
 243         }
 244         while (typeVec.back() == EMPTY) {
 245                 typeVec.pop_back();
 246                 nextShaVec.pop_back();
 247         }
 248 }
 249
 250 bool Lanes::isBranch() {
 251
 252         return (typeVec[activeLane] == BRANCH);
 253 }
 254
 255 void Lanes::afterBranch() {
 256
 257         typeVec[activeLane] = ACTIVE; // TODO test with boundaries
 258 }
 259
 260 void Lanes::afterApplied() {
 261
 262         typeVec[activeLane] = ACTIVE; // TODO test with boundaries
 263 }
 264
 265 void Lanes::nextParent(const CGitHash& sha) {
 266
 267         if(boundary)
 268                 nextShaVec[activeLane].Empty();
 269         else
 270                 nextShaVec[activeLane] = sha;
 271 }
 272
 273 int Lanes::findNextSha(const CGitHash& next, int pos) {
 274
 275         for (unsigned int i = pos; i < nextShaVec.size(); ++i)
 276                 if (nextShaVec[i] == next)
 277                         return i;
 278         return -1;
 279 }
 280
 281 int Lanes::findType(int type, int pos) {
 282
 283         for (unsigned int i = pos; i < typeVec.size(); ++i)
 284                 if (typeVec[i] == type)
 285                         return i;
 286         return -1;
 287 }
 288
 289 int Lanes::add(int type, const CGitHash& next, int pos, bool& wasEmptyCross) {
 290
 291         wasEmptyCross = false;
 292         // first check empty lanes starting from pos
 293         if (pos < (int)typeVec.size()) {
 294                 int posEmpty = findType(EMPTY, pos);
 295                 int posCrossEmpty = findType(CROSS_EMPTY, pos);
 296                 // Use first "empty" position.
 297                 if (posEmpty != -1 && posCrossEmpty != -1)
 298                         pos = min(posEmpty, posCrossEmpty);
 299                 else if (posEmpty != -1)
 300                         pos = posEmpty;
 301                 else if (posCrossEmpty != -1)
 302                         pos = posCrossEmpty;
 303                 else
 304                         pos = -1;
 305
 306                 if (pos != -1) {
 307                         wasEmptyCross = (pos == posCrossEmpty);
 308
 309                         typeVec[pos] = type;
 310                         nextShaVec[pos] = next;
 311                         return pos;
 312                 }
 313         }
 314         // if all lanes are occupied add a new lane
 315         typeVec.push_back(type);
 316         nextShaVec.push_back(next);
 317         return (int)typeVec.size() - 1;
 318 }