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