src/TortoiseProc/lanes.cpp

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