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                 } else
 135                         rangeEnd = add(HEAD, *it, rangeEnd + 1);
 136         }
 137         int& startT = typeVec[rangeStart];
 138         int& endT = typeVec[rangeEnd];
 139
 140         if (startT == NODE && !wasFork && !wasFork_R)
 141                 startT = NODE_L;
 142
 143         if (endT == NODE && !wasFork && !wasFork_L)
 144                 endT = NODE_R;
 145
 146         if (startT == JOIN && !startJoinWasACross)
 147                 startT = JOIN_L;
 148
 149         if (endT == JOIN && !endJoinWasACross)
 150                 endT = JOIN_R;
 151
 152         if (startT == HEAD)
 153                 startT = HEAD_L;
 154
 155         if (endT == HEAD)
 156                 endT = HEAD_R;
 157
 158         for (int i = rangeStart + 1; i < rangeEnd; i++) {
 159
 160                 int& t = typeVec[i];
 161
 162                 if (t == NOT_ACTIVE)
 163                         t = CROSS;
 164
 165                 else if (t == EMPTY)
 166                         t = CROSS_EMPTY;
 167
 168                 else if (t == TAIL_R || t == TAIL_L)
 169                         t = TAIL;
 170         }
 171 }
 172
 173 void Lanes::setInitial() {
 174
 175         int& t = typeVec[activeLane];
 176         if (!IS_NODE(t) && t != APPLIED)
 177                 t = (boundary ? BOUNDARY : INITIAL);
 178 }
 179
 180 void Lanes::setApplied() {
 181
 182         // applied patches are not merges, nor forks
 183         typeVec[activeLane] = APPLIED; // TODO test with boundaries
 184 }
 185
 186 void Lanes::changeActiveLane(const CGitHash& sha) {
 187
 188         int& t = typeVec[activeLane];
 189         if (t == INITIAL || isBoundary(t))
 190                 t = EMPTY;
 191         else
 192                 t = NOT_ACTIVE;
 193
 194         int idx = findNextSha(sha, 0); // find first sha
 195         if (idx != -1)
 196                 typeVec[idx] = ACTIVE; // called before setBoundary()
 197         else
 198                 idx = add(BRANCH, sha, activeLane); // new branch
 199
 200         activeLane = idx;
 201 }
 202
 203 void Lanes::afterMerge() {
 204
 205         if (boundary)
 206                 return; // will be reset by changeActiveLane()
 207
 208         for (unsigned int i = 0; i < typeVec.size(); i++) {
 209
 210                 int& t = typeVec[i];
 211
 212                 if (isHead(t) || isJoin(t) || t == CROSS)
 213                         t = NOT_ACTIVE;
 214
 215                 else if (t == CROSS_EMPTY)
 216                         t = EMPTY;
 217
 218                 else if (IS_NODE(t))
 219                         t = ACTIVE;
 220         }
 221 }
 222
 223 void Lanes::afterFork() {
 224
 225         for (unsigned int i = 0; i < typeVec.size(); i++) {
 226
 227                 int& t = typeVec[i];
 228
 229                 if (t == CROSS)
 230                         t = NOT_ACTIVE;
 231
 232                 else if (isTail(t) || t == CROSS_EMPTY)
 233                         t = EMPTY;
 234
 235                 if (!boundary && IS_NODE(t))
 236                         t = ACTIVE; // boundary will be reset by changeActiveLane()
 237         }
 238         while (typeVec.back() == EMPTY) {
 239                 typeVec.pop_back();
 240                 nextShaVec.pop_back();
 241         }
 242 }
 243
 244 bool Lanes::isBranch() {
 245
 246         return (typeVec[activeLane] == BRANCH);
 247 }
 248
 249 void Lanes::afterBranch() {
 250
 251         typeVec[activeLane] = ACTIVE; // TODO test with boundaries
 252 }
 253
 254 void Lanes::afterApplied() {
 255
 256         typeVec[activeLane] = ACTIVE; // TODO test with boundaries
 257 }
 258
 259 void Lanes::nextParent(const CGitHash& sha) {
 260
 261         if(boundary)
 262                 nextShaVec[activeLane].Empty();
 263         else
 264                 nextShaVec[activeLane] = sha;
 265 }
 266
 267 int Lanes::findNextSha(const CGitHash& next, int pos) {
 268
 269         for (unsigned int i = pos; i < nextShaVec.size(); i++)
 270                 if (nextShaVec[i] == next)
 271                         return i;
 272         return -1;
 273 }
 274
 275 int Lanes::findType(int type, int pos) {
 276
 277         for (unsigned int i = pos; i < typeVec.size(); i++)
 278                 if (typeVec[i] == type)
 279                         return i;
 280         return -1;
 281 }
 282
 283 int Lanes::add(int type, const CGitHash& next, int pos) {
 284
 285         // first check empty lanes starting from pos
 286         if (pos < (int)typeVec.size()) {
 287                 pos = findType(EMPTY, pos);
 288                 if (pos != -1) {
 289                         typeVec[pos] = type;
 290                         nextShaVec[pos] = next;
 291                         return pos;
 292                 }
 293         }
 294         // if all lanes are occupied add a new lane
 295         typeVec.push_back(type);
 296         nextShaVec.push_back(next);
 297         return typeVec.size() - 1;
 298 }