1/* 2 * This file is part of gitg 3 * 4 * Copyright (C) 2012 - Jesse van den Kieboom 5 * 6 * gitg is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * gitg is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with gitg. If not, see <http://www.gnu.org/licenses/>. 18 */ 19 20namespace Gitg 21{ 22 23public class Lanes : Object 24{ 25 public int inactive_max { get; set; default = 30; } 26 public int inactive_collapse { get; set; default = 10; } 27 public int inactive_gap { get; set; default = 10; } 28 public bool inactive_enabled { get; set; default = true; } 29 public Gee.LinkedList<Commit> miss_commits {get; set; } 30 31 private SList<weak Commit> d_previous; 32 private Gee.LinkedList<LaneContainer> d_lanes; 33 private HashTable<Ggit.OId, CollapsedLane> d_collapsed; 34 private Gee.HashSet<Ggit.OId>? d_roots; 35 36 class LaneContainer 37 { 38 public Lane lane; 39 public int inactive; 40 public Ggit.OId? from; 41 public Ggit.OId? to; 42 43 public LaneContainer.with_color(Ggit.OId? from, 44 Ggit.OId? to, 45 Color? color) 46 { 47 this.from = from; 48 this.to = to; 49 this.lane = new Lane.with_color(color); 50 this.inactive = 0; 51 } 52 53 public LaneContainer(Ggit.OId? from, 54 Ggit.OId? to) 55 { 56 this.with_color(from, to, null); 57 } 58 59 public void next(int index) 60 { 61 var hidden = is_hidden; 62 lane = lane.copy(); 63 64 lane.tag = LaneTag.NONE; 65 lane.from = new SList<int>(); 66 67 if (!hidden) 68 { 69 lane.from.prepend(index); 70 } 71 72 is_hidden = hidden; 73 74 if (to != null && inactive >= 0) 75 { 76 ++inactive; 77 } 78 } 79 80 public bool is_hidden 81 { 82 get { return (lane.tag & LaneTag.HIDDEN) != 0; } 83 set 84 { 85 if (value) 86 { 87 lane.tag |= LaneTag.HIDDEN; 88 } 89 else 90 { 91 lane.tag &= ~LaneTag.HIDDEN; 92 } 93 } 94 } 95 } 96 97 [Compact] 98 class CollapsedLane 99 { 100 public Color color; 101 public uint index; 102 public Ggit.OId? from; 103 public Ggit.OId? to; 104 105 public CollapsedLane(LaneContainer container) 106 { 107 color = container.lane.color; 108 from = container.from; 109 to = container.to; 110 } 111 } 112 113 public Lanes() 114 { 115 d_collapsed = new HashTable<Ggit.OId, CollapsedLane>(Ggit.OId.hash, 116 Ggit.OId.equal); 117 118 var settings = new Settings(Gitg.Config.APPLICATION_ID + ".preferences.history"); 119 120 settings.bind("collapse-inactive-lanes-enabled", 121 this, 122 "inactive-enabled", 123 SettingsBindFlags.GET | SettingsBindFlags.SET); 124 125 settings.bind("collapse-inactive-lanes", 126 this, 127 "inactive-collapse", 128 SettingsBindFlags.GET | SettingsBindFlags.SET); 129 130 reset(); 131 } 132 133 public void reset(Ggit.OId[]? reserved = null, 134 Gee.HashSet<Ggit.OId>? roots = null) 135 { 136 d_lanes = new Gee.LinkedList<LaneContainer>(); 137 miss_commits = new Gee.LinkedList<Commit>(); 138 d_roots = roots; 139 140 Color.reset(); 141 142 if (reserved != null) 143 { 144 foreach (var r in reserved) 145 { 146 var ct = new LaneContainer(null, r); 147 ct.inactive = -1; 148 ct.is_hidden = true; 149 150 d_lanes.add(ct); 151 } 152 } 153 154 d_collapsed.remove_all(); 155 d_previous = new SList<weak Commit>(); 156 } 157 158 public bool next(Commit next, 159 out SList<Lane> lanes, 160 out int nextpos, 161 bool save_miss = false) 162 { 163 var myoid = next.get_id(); 164 165 if (inactive_enabled) 166 { 167 collapse_lanes(); 168 expand_lanes(next); 169 } 170 171 debug("commit: %s %s", next.get_subject(), next.get_id().to_string()); 172 LaneContainer? mylane = find_lane_by_oid(myoid, out nextpos); 173 if (mylane == null && d_roots != null && !d_roots.contains(myoid)) 174 { 175 lanes = null; 176 if (save_miss) { 177 debug ("saving miss %s %s", next.get_id().to_string(), next.get_id().to_string()); 178 miss_commits.add(next); 179 } 180 181 return false; 182 } 183 184 if (mylane == null) 185 { 186 // there is no lane reserved for this commit, add a new lane 187 mylane = new LaneContainer(myoid, null); 188 189 d_lanes.add(mylane); 190 nextpos = (int)d_lanes.size - 1; 191 } 192 else 193 { 194 // copy the color here because the commit is a new stop 195 mylane.lane.color = mylane.lane.color.copy(); 196 197 mylane.to = null; 198 mylane.from = next.get_id(); 199 200 if (mylane.is_hidden && d_roots != null && d_roots.contains(myoid)) 201 { 202 mylane.is_hidden = false; 203 mylane.lane.from = new SList<int>(); 204 } 205 206 if (mylane.inactive >= 0) 207 { 208 mylane.inactive = 0; 209 } 210 } 211 212 var hidden = mylane.is_hidden; 213 214 lanes = lanes_list(); 215 prepare_lanes(next, nextpos, hidden); 216 217 return !hidden; 218 } 219 220 private void prepare_lanes(Commit next, int pos, bool hidden) 221 { 222 var parents = next.get_parents(); 223 var myoid = next.get_id(); 224 225 if (!hidden) 226 { 227 init_next_layer(); 228 } 229 230 var mylane = d_lanes[pos]; 231 232 for (uint i = 0; i < parents.size; ++i) 233 { 234 int lnpos; 235 var poid = parents.get_id(i); 236 237 var container = find_lane_by_oid(poid, out lnpos); 238 239 if (container != null) 240 { 241 // there is already a lane for this parent. This means that 242 // we add pos as a merge for the lane. 243 if (i == 0 && pos < lnpos) 244 { 245 // we are at the mainline of a merge, and this parent has 246 // already been assigned to an existing lane, if our 247 // lane's pos is smaller, then the this parent should be in 248 // our lane instead. 249 mylane.to = poid; 250 mylane.from = myoid; 251 252 if (!container.is_hidden) 253 { 254 mylane.lane.from.append(lnpos); 255 mylane.is_hidden = false; 256 } 257 258 mylane.lane.color = mylane.lane.color.copy(); 259 260 if (mylane.inactive >= 0) 261 { 262 mylane.inactive = 0; 263 } 264 265 d_lanes.remove(container); 266 } 267 else 268 { 269 container.from = myoid; 270 271 if (!hidden) 272 { 273 container.lane.from.append(pos); 274 } 275 276 container.lane.color = container.lane.color.copy(); 277 278 if (!hidden) 279 { 280 container.is_hidden = false; 281 } 282 283 if (container.inactive >= 0) 284 { 285 container.inactive = 0; 286 } 287 } 288 289 continue; 290 } 291 else if (mylane != null && mylane.to == null) 292 { 293 // there is no parent yet which can proceed on the current 294 // commit lane, so set it now 295 mylane.to = poid; 296 297 mylane.lane.color = mylane.lane.color.copy(); 298 } 299 else if (!hidden) 300 { 301 // generate a new lane for this parent 302 var newlane = new LaneContainer(myoid, poid); 303 304 newlane.lane.from.prepend(pos); 305 d_lanes.add(newlane); 306 } 307 } 308 309 if (mylane != null && mylane.to == null) 310 { 311 // remove current lane if no longer needed (i.e. merged) 312 d_lanes.remove(mylane); 313 } 314 315 // store new commit in track list 316 if (d_previous.length() == inactive_collapse + inactive_gap + 1) 317 { 318 d_previous.delete_link(d_previous.last()); 319 } 320 321 d_previous.prepend(next); 322 } 323 324 private void add_collapsed(LaneContainer container, 325 int index) 326 { 327 var collapsed = new CollapsedLane(container); 328 collapsed.index = index; 329 330 d_collapsed.insert(container.to, (owned)collapsed); 331 } 332 333 private void collapse_lane(LaneContainer container, 334 int index) 335 { 336 add_collapsed(container, index); 337 338 unowned SList<weak Commit> item = d_previous; 339 340 while (item != null) 341 { 342 var commit = item.data; 343 unowned SList<Lane> lns = commit.get_lanes(); 344 345 if (lns != null && index <= lns.length()) 346 { 347 unowned Lane lane = lns.nth_data(index); 348 349 if (item.next != null) 350 { 351 var newindex = lane.from.data; 352 353 lns = commit.remove_lane(lane); 354 355 if (item.next.next != null) 356 { 357 update_merge_indices(lns, newindex, -1); 358 } 359 360 var mylane = commit.mylane; 361 362 if (mylane > index) 363 { 364 --commit.mylane; 365 } 366 367 index = newindex; 368 } 369 else 370 { 371 lane.tag |= LaneTag.END; 372 lane.boundary_id = container.to; 373 } 374 } 375 376 item = item.next; 377 } 378 } 379 380 private void collapse_lanes() 381 { 382 int index = 0; 383 384 var iter = d_lanes.iterator(); 385 386 while (iter.next()) 387 { 388 var container = iter.get(); 389 390 if (container.inactive != inactive_max + inactive_gap) 391 { 392 ++index; 393 continue; 394 } 395 396 collapse_lane(container, container.lane.from.data); 397 update_current_lane_merge_indices(index, -1); 398 399 iter.remove(); 400 } 401 } 402 403 private int ensure_correct_index(Commit commit, 404 int index) 405 { 406 var len = commit.get_lanes().length(); 407 408 if (index > len) 409 { 410 return (int)len; 411 } 412 else 413 { 414 return index; 415 } 416 } 417 418 private void update_lane_merge_indices(SList<int> from, 419 int index, 420 int direction) 421 { 422 while (from != null) 423 { 424 int idx = from.data; 425 426 if (idx > index || (direction > 0 && idx == index)) 427 { 428 from.data = idx + direction; 429 } 430 431 from = from.next; 432 } 433 } 434 435 private void update_merge_indices(SList<Lane> lanes, 436 int index, 437 int direction) 438 { 439 foreach (unowned Lane lane in lanes) 440 { 441 update_lane_merge_indices(lane.from, index, direction); 442 } 443 } 444 private void update_current_lane_merge_indices(int index, 445 int direction) 446 { 447 foreach (var container in d_lanes) 448 { 449 update_lane_merge_indices(container.lane.from, 450 index, 451 direction); 452 } 453 } 454 455 private void expand_lane(CollapsedLane lane) 456 { 457 var index = lane.index; 458 var ln = new Lane.with_color(lane.color); 459 var len = d_lanes.size; 460 461 if (index > len) 462 { 463 index = len; 464 } 465 466 var next = ensure_correct_index(d_previous.data, (int)index); 467 468 var container = new LaneContainer.with_color(lane.from, 469 lane.to, 470 lane.color); 471 472 update_current_lane_merge_indices((int)index, 1); 473 474 container.lane.from.prepend(next); 475 d_lanes.insert((int)index, container); 476 477 index = next; 478 uint cnt = 0; 479 480 unowned SList<weak Commit> ptr = d_previous; 481 482 while (ptr != null) 483 { 484 var commit = ptr.data; 485 486 if (cnt == inactive_collapse) 487 { 488 break; 489 } 490 491 // Insert new lane at the index 492 Lane copy = ln.copy(); 493 unowned SList<Lane> lns = commit.get_lanes(); 494 495 if (ptr.next == null || cnt + 1 == inactive_collapse) 496 { 497 copy.boundary_id = lane.from; 498 copy.tag |= LaneTag.START; 499 } 500 else 501 { 502 next = ensure_correct_index(ptr.next.data, (int)index); 503 copy.from.prepend(next); 504 505 update_merge_indices(lns, (int)index, 1); 506 } 507 508 commit.insert_lane(copy, (int)index); 509 510 var mylane = commit.mylane; 511 512 if (mylane >= index) 513 { 514 ++commit.mylane; 515 } 516 517 index = next; 518 ++cnt; 519 520 ptr = ptr.next; 521 } 522 } 523 524 private void expand_lane_from_oid(Ggit.OId id) 525 { 526 unowned CollapsedLane? collapsed = d_collapsed.lookup(id); 527 528 if (collapsed != null) 529 { 530 expand_lane(collapsed); 531 d_collapsed.remove(id); 532 } 533 } 534 535 private void expand_lanes(Commit commit) 536 { 537 expand_lane_from_oid(commit.get_id()); 538 539 var parents = commit.get_parents(); 540 541 for (uint i = 0; i < parents.size; ++i) 542 { 543 expand_lane_from_oid(parents.get_id(i)); 544 } 545 } 546 547 private void init_next_layer() 548 { 549 int index = 0; 550 551 foreach (var container in d_lanes) 552 { 553 container.next(index++); 554 } 555 } 556 557 private LaneContainer? find_lane_by_oid(Ggit.OId id, 558 out int pos) 559 { 560 int p = 0; 561 562 foreach (var container in d_lanes) 563 { 564 if (container != null && 565 id.equal(container.to)) 566 { 567 pos = p; 568 return container; 569 } 570 571 ++p; 572 } 573 574 pos = -1; 575 return null; 576 } 577 578 private SList<Lane> lanes_list() 579 { 580 var ret = new SList<Lane>(); 581 582 foreach (var container in d_lanes) 583 { 584 ret.prepend(container.lane.copy()); 585 } 586 587 ret.reverse(); 588 return ret; 589 } 590} 591 592} 593 594// ex:set ts=4 noet 595