src/TortoiseProc/lanes.cpp

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