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