src/graph-v2.c

   1 /* Copyright (c) 2006-2015 Jonas Fonseca <jonas.fonseca@gmail.com>
   2  *
   3  * This program is free software; you can redistribute it and/or
   4  * modify it under the terms of the GNU General Public License as
   5  * published by the Free Software Foundation; either version 2 of
   6  * the License, or (at your option) any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  */
  13
  14 #include "tig/tig.h"
  15 #include "tig/util.h"
  16 #include "tig/graph.h"
  17 #include "compat/hashtab.h"
  18
  19 struct graph_symbol {
  20         unsigned int color:8;
  21
  22         unsigned int commit:1;
  23         unsigned int boundary:1;
  24         unsigned int initial:1;
  25         unsigned int merge:1;
  26
  27         unsigned int continued_down:1;
  28         unsigned int continued_up:1;
  29         unsigned int continued_right:1;
  30         unsigned int continued_left:1;
  31         unsigned int continued_up_left:1;
  32
  33         unsigned int parent_down:1;
  34         unsigned int parent_right:1;
  35
  36         unsigned int below_commit:1;
  37         unsigned int flanked:1;
  38         unsigned int next_right:1;
  39         unsigned int matches_commit:1;
  40
  41         unsigned int shift_left:1;
  42         unsigned int continue_shift:1;
  43         unsigned int below_shift:1;
  44
  45         unsigned int new_column:1;
  46         unsigned int empty:1;
  47 };
  48
  49 struct graph_column {
  50         struct graph_symbol symbol;
  51         char id[SIZEOF_REV];            /* Parent SHA1 ID. */
  52 };
  53
  54 struct graph_row {
  55         size_t size;
  56         struct graph_column *columns;
  57 };
  58
  59 struct colors {
  60         htab_t id_map;
  61         size_t count[GRAPH_COLORS];
  62 };
  63
  64 struct graph_v2 {
  65         struct graph api;
  66         struct graph_row row;
  67         struct graph_row parents;
  68         struct graph_row prev_row;
  69         struct graph_row next_row;
  70         size_t position;
  71         size_t prev_position;
  72         size_t expanded;
  73         char id[SIZEOF_REV];
  74         struct colors colors;
  75         bool has_parents;
  76         bool is_boundary;
  77 };
  78
  79 DEFINE_ALLOCATOR(realloc_graph_columns, struct graph_column, 32)
  80 DEFINE_ALLOCATOR(realloc_graph_symbols, struct graph_symbol, 1)
  81
  82 struct id_color {
  83         char *id;
  84         size_t color;
  85 };
  86
  87 struct id_color *
  88 id_color_new(const char *id, size_t color)
  89 {
  90         struct id_color *node = malloc(sizeof(struct id_color));
  91
  92         node->id = (char *) malloc(strlen(id) + 1);
  93         strcpy(node->id, id);
  94         node->color = color;
  95
  96         return node;
  97 }
  98
  99 static void
 100 id_color_delete(struct id_color *node)
 101 {
 102         free(node->id);
 103         free(node);
 104 }
 105
 106 static int
 107 id_color_eq(const void *entry, const void *element)
 108 {
 109         return strcmp(((const struct id_color *) entry)->id, ((const struct id_color *) element)->id) == 0;
 110 }
 111
 112 static void
 113 key_del(void *key)
 114 {
 115         id_color_delete((struct id_color *) key);
 116 }
 117
 118 static hashval_t
 119 id_color_hash(const void *node)
 120 {
 121         return htab_hash_string(((const struct id_color*) node)->id);
 122 }
 123
 124 static void
 125 colors_add_id(struct colors *colors, const char *id, const size_t color)
 126 {
 127         struct id_color *node = id_color_new(id, color);
 128         void **slot = htab_find_slot(colors->id_map, node, INSERT);
 129
 130         if (slot != NULL && *slot == NULL) {
 131                 *slot = node;
 132                 colors->count[color]++;
 133         } else {
 134                 id_color_delete(node);
 135         }
 136 }
 137
 138 static void
 139 colors_remove_id(struct colors *colors, const char *id)
 140 {
 141         struct id_color *node = id_color_new(id, 0);
 142         void **slot = htab_find_slot(colors->id_map, node, NO_INSERT);
 143
 144         if (slot != NULL && *slot != NULL) {
 145                 colors->count[((struct id_color *) *slot)->color]--;
 146                 htab_clear_slot(colors->id_map, slot);
 147         }
 148
 149         id_color_delete(node);
 150 }
 151
 152 static size_t
 153 colors_get_color(struct colors *colors, const char *id)
 154 {
 155         struct id_color *key = id_color_new(id, 0);
 156         struct id_color *node = (struct id_color *) htab_find(colors->id_map, key);
 157
 158         id_color_delete(key);
 159
 160         if (node == NULL) {
 161                 return (size_t) -1; // Max value of size_t. ID not found.
 162         }
 163         return node->color;
 164 }
 165
 166 static size_t
 167 colors_get_free_color(struct colors *colors)
 168 {
 169         size_t free_color = 0;
 170         size_t lowest = (size_t) -1; // Max value of size_t
 171         int i;
 172
 173         for (i = 0; i < ARRAY_SIZE(colors->count); i++) {
 174                 if (colors->count[i] < lowest) {
 175                         lowest = colors->count[i];
 176                         free_color = i;
 177                 }
 178         }
 179         return free_color;
 180 }
 181
 182 static void
 183 colors_init(struct colors *colors)
 184 {
 185         if (colors->id_map == NULL) {
 186                 uint size = 500;
 187
 188                 colors->id_map = htab_create_alloc(size, id_color_hash, id_color_eq, key_del, calloc, free);
 189         }
 190 }
 191
 192 static size_t
 193 get_color(struct graph_v2 *graph, char *new_id)
 194 {
 195         size_t color;
 196
 197         colors_init(&graph->colors);
 198         color = colors_get_color(&graph->colors, new_id);
 199
 200         if (color < (size_t) -1) {
 201                 return color;
 202         }
 203
 204         color = colors_get_free_color(&graph->colors);
 205         colors_add_id(&graph->colors, new_id, color);
 206
 207         return color;
 208 }
 209
 210 static void
 211 done_graph_rendering(struct graph *graph_ref)
 212 {
 213         struct graph_v2 *graph = graph_ref->private;
 214
 215         free(graph->prev_row.columns);
 216         free(graph->row.columns);
 217         free(graph->next_row.columns);
 218         free(graph->parents.columns);
 219 }
 220
 221 static void
 222 done_graph(struct graph *graph_ref)
 223 {
 224         struct graph_v2 *graph = graph_ref->private;
 225
 226         free(graph);
 227 }
 228
 229 #define graph_column_has_commit(col) ((col)->id[0])
 230
 231 static size_t
 232 graph_find_column_by_id(struct graph_row *row, const char *id)
 233 {
 234         size_t free_column = row->size;
 235         size_t i;
 236
 237         for (i = 0; i < row->size; i++) {
 238                 if (!graph_column_has_commit(&row->columns[i]) && free_column == row->size)
 239                         free_column = i;
 240                 else if (!strcmp(row->columns[i].id, id))
 241                         return i;
 242         }
 243
 244         return free_column;
 245 }
 246
 247 static size_t
 248 graph_find_free_column(struct graph_row *row)
 249 {
 250         size_t i;
 251
 252         for (i = 0; i < row->size; i++) {
 253                 if (!graph_column_has_commit(&row->columns[i]))
 254                         return i;
 255         }
 256
 257         return row->size;
 258 }
 259
 260 static struct graph_column *
 261 graph_insert_column(struct graph_v2 *graph, struct graph_row *row, size_t pos, const char *id)
 262 {
 263         struct graph_column *column;
 264
 265         if (!realloc_graph_columns(&row->columns, row->size, 1))
 266                 return NULL;
 267
 268         column = &row->columns[pos];
 269         if (pos < row->size) {
 270                 memmove(column + 1, column, sizeof(*column) * (row->size - pos));
 271         }
 272
 273         row->size++;
 274         memset(column, 0, sizeof(*column));
 275         string_copy_rev(column->id, id);
 276         column->symbol.boundary = !!graph->is_boundary;
 277
 278         return column;
 279 }
 280
 281 static bool
 282 graph_add_parent(struct graph *graph_ref, const char *parent)
 283 {
 284         struct graph_v2 *graph = graph_ref->private;
 285
 286         if (graph->has_parents)
 287                 return true;
 288         return graph_insert_column(graph, &graph->parents, graph->parents.size, parent) != NULL;
 289 }
 290
 291 static bool
 292 graph_needs_expansion(struct graph_v2 *graph)
 293 {
 294         return graph->position + graph->parents.size > graph->row.size;
 295 }
 296
 297 static bool
 298 graph_expand(struct graph_v2 *graph)
 299 {
 300         while (graph_needs_expansion(graph)) {
 301                 if (!graph_insert_column(graph, &graph->prev_row, graph->prev_row.size, ""))
 302                         return false;
 303
 304                 if (!graph_insert_column(graph, &graph->row, graph->row.size, ""))
 305                         return false;
 306
 307                 if (!graph_insert_column(graph, &graph->next_row, graph->next_row.size, ""))
 308                         return false;
 309         }
 310
 311         return true;
 312 }
 313
 314 static bool
 315 graph_needs_collapsing(struct graph_v2 *graph)
 316 {
 317         return graph->row.size > 1
 318             && !graph_column_has_commit(&graph->row.columns[graph->row.size - 1]);
 319 }
 320
 321 static bool
 322 graph_collapse(struct graph_v2 *graph)
 323 {
 324         while (graph_needs_collapsing(graph)) {
 325                 graph->prev_row.size--;
 326                 graph->row.size--;
 327                 graph->next_row.size--;
 328         }
 329
 330         return true;
 331 }
 332
 333 static void
 334 graph_canvas_append_symbol(struct graph_v2 *graph, struct graph_canvas *canvas, struct graph_symbol *symbol)
 335 {
 336         if (realloc_graph_symbols(&canvas->symbols, canvas->size, 1))
 337                 canvas->symbols[canvas->size++] = *symbol;
 338 }
 339
 340 static void
 341 graph_row_clear_commit(struct graph_row *row, const char *id)
 342 {
 343         int i;
 344
 345         for (i = 0; i < row->size; i++) {
 346                 if (strcmp(row->columns[i].id, id) == 0) {
 347                         row->columns[i].id[0] = 0;
 348                 }
 349         }
 350 }
 351
 352 static void
 353 graph_insert_parents(struct graph_v2 *graph)
 354 {
 355         struct graph_row *prev_row = &graph->prev_row;
 356         struct graph_row *row = &graph->row;
 357         struct graph_row *next_row = &graph->next_row;
 358         struct graph_row *parents = &graph->parents;
 359         int i;
 360
 361         for (i = 0; i < parents->size; i++) {
 362                 struct graph_column *new = &parents->columns[i];
 363
 364                 if (graph_column_has_commit(new)) {
 365                         size_t match = graph_find_free_column(next_row);
 366
 367                         if (match == next_row->size && *next_row->columns[next_row->size - 1].id) {
 368                                 graph_insert_column(graph, next_row, next_row->size, new->id);
 369                                 graph_insert_column(graph, row, row->size, "");
 370                                 graph_insert_column(graph, prev_row, prev_row->size, "");
 371                         } else {
 372                                 next_row->columns[match] = *new;
 373                         }
 374                 }
 375         }
 376 }
 377
 378 static bool
 379 commit_is_in_row(const char *id, struct graph_row *row)
 380 {
 381         int i;
 382
 383         for (i = 0; i < row->size; i++) {
 384                 if (!graph_column_has_commit(&row->columns[i]))
 385                         continue;
 386
 387                 if (strcmp(id, row->columns[i].id) == 0)
 388                         return true;
 389         }
 390         return false;
 391 }
 392
 393 static void
 394 graph_remove_collapsed_columns(struct graph_v2 *graph)
 395 {
 396         struct graph_row *row = &graph->next_row;
 397         int i;
 398
 399         for (i = row->size - 1; i > 0; i--) {
 400                 if (i == graph->position)
 401                         continue;
 402
 403                 if (i == graph->position + 1)
 404                         continue;
 405
 406                 if (strcmp(row->columns[i].id, graph->id) == 0)
 407                         continue;
 408
 409                 if (strcmp(row->columns[i].id, row->columns[i - 1].id) != 0)
 410                         continue;
 411
 412                 if (commit_is_in_row(row->columns[i].id, &graph->parents) && !graph_column_has_commit(&graph->prev_row.columns[i]))
 413                         continue;
 414
 415                 if (strcmp(row->columns[i - 1].id, graph->prev_row.columns[i - 1].id) != 0 || graph->prev_row.columns[i - 1].symbol.shift_left) {
 416                         if (i + 1 >= row->size)
 417                                 memset(&row->columns[i], 0, sizeof(row->columns[i]));
 418                         else
 419                                 row->columns[i] = row->columns[i + 1];
 420                 }
 421         }
 422 }
 423
 424 static void
 425 graph_fill_empty_columns(struct graph_v2 *graph)
 426 {
 427         struct graph_row *row = &graph->next_row;
 428         int i;
 429
 430         for (i = row->size - 2; i >= 0; i--) {
 431                 if (!graph_column_has_commit(&row->columns[i])) {
 432                         row->columns[i] = row->columns[i + 1];
 433                 }
 434         }
 435 }
 436
 437 static void
 438 graph_generate_next_row(struct graph_v2 *graph)
 439 {
 440         graph_row_clear_commit(&graph->next_row, graph->id);
 441         graph_insert_parents(graph);
 442         graph_remove_collapsed_columns(graph);
 443         graph_fill_empty_columns(graph);
 444 }
 445
 446 static int
 447 commits_in_row(struct graph_row *row)
 448 {
 449         int count = 0;
 450         int i;
 451
 452         for (i = 0; i < row->size;i++) {
 453                 if (graph_column_has_commit(&row->columns[i]))
 454                         count++;
 455         }
 456
 457         return count;
 458 }
 459
 460 static void
 461 graph_commit_next_row(struct graph_v2 *graph)
 462 {
 463         int i;
 464
 465         for (i = 0; i < graph->row.size; i++) {
 466                 graph->prev_row.columns[i] = graph->row.columns[i];
 467
 468                 if (i == graph->position && commits_in_row(&graph->parents) > 0)
 469                         graph->prev_row.columns[i] = graph->next_row.columns[i];
 470
 471                 if (!graph_column_has_commit(&graph->prev_row.columns[i]))
 472                         graph->prev_row.columns[i] = graph->next_row.columns[i];
 473
 474                 graph->row.columns[i] = graph->next_row.columns[i];
 475         }
 476
 477         graph->prev_position = graph->position;
 478 }
 479
 480 static bool
 481 continued_down(struct graph_row *row, struct graph_row *next_row, int pos)
 482 {
 483         if (strcmp(row->columns[pos].id, next_row->columns[pos].id) != 0)
 484                 return false;
 485
 486         if (row->columns[pos].symbol.shift_left)
 487                 return false;
 488
 489         return true;
 490 }
 491
 492 static bool
 493 shift_left(struct graph_row *row, struct graph_row *prev_row, int pos)
 494 {
 495         int i;
 496
 497         if (!graph_column_has_commit(&row->columns[pos]))
 498                 return false;
 499
 500         for (i = pos - 1; i >= 0; i--) {
 501                 if (!graph_column_has_commit(&row->columns[i]))
 502                         continue;
 503
 504                 if (strcmp(row->columns[i].id, row->columns[pos].id) != 0)
 505                         continue;
 506
 507                 if (!continued_down(prev_row, row, i))
 508                         return true;
 509
 510                 break;
 511         }
 512
 513         return false;
 514 }
 515
 516 static bool
 517 new_column(struct graph_row *row, struct graph_row *prev_row, int pos)
 518 {
 519         int i;
 520
 521         if (!graph_column_has_commit(&prev_row->columns[pos]))
 522                 return true;
 523
 524         for (i = pos; i < row->size; i++) {
 525                 if (strcmp(row->columns[pos].id, prev_row->columns[i].id) == 0)
 526                         return false;
 527         }
 528
 529         return true;
 530 }
 531
 532 static bool
 533 continued_right(struct graph_row *row, int pos, int commit_pos)
 534 {
 535         int i, end;
 536
 537         if (pos < commit_pos)
 538                 end = commit_pos;
 539         else
 540                 end = row->size;
 541
 542         for (i = pos + 1; i < end; i++) {
 543                 if (strcmp(row->columns[pos].id, row->columns[i].id) == 0)
 544                         return true;
 545         }
 546
 547         return false;
 548 }
 549
 550 static bool
 551 continued_left(struct graph_row *row, int pos, int commit_pos)
 552 {
 553         int i, start;
 554
 555         if (pos < commit_pos)
 556                 start = 0;
 557         else
 558                 start = commit_pos;
 559
 560         for (i = start; i < pos; i++) {
 561                 if (!graph_column_has_commit(&row->columns[i]))
 562                         continue;
 563
 564                 if (strcmp(row->columns[pos].id, row->columns[i].id) == 0)
 565                         return true;
 566         }
 567
 568         return false;
 569 }
 570
 571 static bool
 572 parent_down(struct graph_row *parents, struct graph_row *next_row, int pos)
 573 {
 574         int parent;
 575
 576         for (parent = 0; parent < parents->size; parent++) {
 577                 if (!graph_column_has_commit(&parents->columns[parent]))
 578                         continue;
 579
 580                 if (strcmp(parents->columns[parent].id, next_row->columns[pos].id) == 0)
 581                         return true;
 582         }
 583
 584         return false;
 585 }
 586
 587 static bool
 588 parent_right(struct graph_row *parents, struct graph_row *row, struct graph_row *next_row, int pos)
 589 {
 590         int parent, i;
 591
 592         for (parent = 0; parent < parents->size; parent++) {
 593                 if (!graph_column_has_commit(&parents->columns[parent]))
 594                         continue;
 595
 596                 for (i = pos + 1; i < next_row->size; i++) {
 597                         if (strcmp(parents->columns[parent].id, next_row->columns[i].id) != 0)
 598                                 continue;
 599
 600                         if (strcmp(parents->columns[parent].id, row->columns[i].id) != 0)
 601                                 return true;
 602                 }
 603         }
 604
 605         return false;
 606 }
 607
 608 static bool
 609 flanked(struct graph_row *row, int pos, int commit_pos, const char *commit_id)
 610 {
 611         int i, start, end;
 612
 613         if (pos < commit_pos) {
 614                 start = 0;
 615                 end = pos;
 616         } else {
 617                 start = pos + 1;
 618                 end = row->size;
 619         }
 620
 621         for (i = start; i < end; i++) {
 622                 if (strcmp(row->columns[i].id, commit_id) == 0)
 623                         return true;
 624         }
 625
 626         return false;
 627 }
 628
 629 static bool
 630 below_commit(int pos, struct graph_v2 *graph)
 631 {
 632         if (pos != graph->prev_position)
 633                 return false;
 634
 635         if (strcmp(graph->row.columns[pos].id, graph->prev_row.columns[pos].id))
 636                 return false;
 637
 638         return true;
 639 }
 640
 641 static void
 642 graph_generate_symbols(struct graph_v2 *graph, struct graph_canvas *canvas)
 643 {
 644         struct graph_row *prev_row = &graph->prev_row;
 645         struct graph_row *row = &graph->row;
 646         struct graph_row *next_row = &graph->next_row;
 647         struct graph_row *parents = &graph->parents;
 648         int pos;
 649
 650         for (pos = 0; pos < row->size; pos++) {
 651                 struct graph_column *column = &row->columns[pos];
 652                 struct graph_symbol *symbol = &column->symbol;
 653                 char *id = next_row->columns[pos].id;
 654
 655                 symbol->commit            = (pos == graph->position);
 656                 symbol->boundary          = (pos == graph->position && next_row->columns[pos].symbol.boundary);
 657                 symbol->initial           = (commits_in_row(parents) < 1);
 658                 symbol->merge             = (commits_in_row(parents) > 1);
 659
 660                 symbol->continued_down    = continued_down(row, next_row, pos);
 661                 symbol->continued_up      = continued_down(prev_row, row, pos);
 662                 symbol->continued_right   = continued_right(row, pos, graph->position);
 663                 symbol->continued_left    = continued_left(row, pos, graph->position);
 664                 symbol->continued_up_left = continued_left(prev_row, pos, prev_row->size);
 665
 666                 symbol->parent_down       = parent_down(parents, next_row, pos);
 667                 symbol->parent_right      = (pos > graph->position && parent_right(parents, row, next_row, pos));
 668
 669                 symbol->below_commit      = below_commit(pos, graph);
 670                 symbol->flanked           = flanked(row, pos, graph->position, graph->id);
 671                 symbol->next_right        = continued_right(next_row, pos, 0);
 672                 symbol->matches_commit    = (strcmp(column->id, graph->id) == 0);
 673
 674                 symbol->shift_left        = shift_left(row, prev_row, pos);
 675                 symbol->continue_shift    = (pos + 1 < row->size) ? shift_left(row, prev_row, pos + 1) : 0;
 676                 symbol->below_shift       = prev_row->columns[pos].symbol.shift_left;
 677
 678                 symbol->new_column        = new_column(row, prev_row, pos);
 679                 symbol->empty             = (!graph_column_has_commit(&row->columns[pos]));
 680
 681                 if (graph_column_has_commit(column)) {
 682                         id = column->id;
 683                 }
 684                 symbol->color = get_color(graph, id);
 685
 686                 graph_canvas_append_symbol(graph, canvas, symbol);
 687         }
 688
 689         colors_remove_id(&graph->colors, graph->id);
 690 }
 691
 692 static bool
 693 graph_render_parents(struct graph *graph_ref, struct graph_canvas *canvas)
 694 {
 695         struct graph_v2 *graph = graph_ref->private;
 696
 697         if (graph->parents.size == 0 &&
 698             !graph_add_parent(graph_ref, ""))
 699                 return false;
 700
 701         if (!graph_expand(graph))
 702                 return false;
 703
 704         graph_generate_next_row(graph);
 705         graph_generate_symbols(graph, canvas);
 706         graph_commit_next_row(graph);
 707
 708         graph->parents.size = graph->position = 0;
 709
 710         if (!graph_collapse(graph))
 711                 return false;
 712
 713         return true;
 714 }
 715
 716 static bool
 717 graph_add_commit(struct graph *graph_ref, struct graph_canvas *canvas,
 718                  const char *id, const char *parents, bool is_boundary)
 719 {
 720         struct graph_v2 *graph = graph_ref->private;
 721         int has_parents = 0;
 722
 723         graph->position = graph_find_column_by_id(&graph->row, id);
 724         string_copy_rev(graph->id, id);
 725         graph->is_boundary = is_boundary;
 726         graph->has_parents = false;
 727
 728         while ((parents = strchr(parents, ' '))) {
 729                 parents++;
 730                 if (!graph_add_parent(graph_ref, parents))
 731                         return false;
 732                 has_parents++;
 733         }
 734
 735         graph->has_parents = has_parents > 0;
 736
 737         return true;
 738 }
 739
 740 static const bool
 741 graph_symbol_forks(const struct graph_symbol *symbol)
 742 {
 743         if (!symbol->continued_down)
 744                 return false;
 745
 746         if (!symbol->continued_right)
 747                 return false;
 748
 749         if (!symbol->continued_up)
 750                 return false;
 751
 752         return true;
 753 }
 754
 755 static const bool
 756 graph_symbol_cross_over(const struct graph_symbol *symbol)
 757 {
 758         if (symbol->empty)
 759                 return false;
 760
 761         if (!symbol->continued_down)
 762                 return false;
 763
 764         if (!symbol->continued_up && !symbol->new_column && !symbol->below_commit)
 765                 return false;
 766
 767         if (symbol->shift_left)
 768                 return false;
 769
 770         if (symbol->parent_right && symbol->merge)
 771                 return true;
 772
 773         if (symbol->flanked)
 774                 return true;
 775
 776         return false;
 777 }
 778
 779 static const bool
 780 graph_symbol_turn_left(const struct graph_symbol *symbol)
 781 {
 782         if (symbol->matches_commit && symbol->continued_right && !symbol->continued_down)
 783                 return false;
 784
 785         if (symbol->continue_shift)
 786                 return false;
 787
 788         if (symbol->continued_up || symbol->new_column || symbol->below_commit) {
 789                 if (symbol->matches_commit)
 790                         return true;
 791
 792                 if (symbol->shift_left)
 793                         return true;
 794         }
 795
 796         return false;
 797 }
 798
 799 static const bool
 800 graph_symbol_turn_down_cross_over(const struct graph_symbol *symbol)
 801 {
 802         if (!symbol->continued_down)
 803                 return false;
 804
 805         if (!symbol->continued_right)
 806                 return false;
 807
 808         if (symbol->flanked)
 809                 return true;
 810
 811         if (symbol->merge)
 812                 return true;
 813
 814         return false;
 815 }
 816
 817 static const bool
 818 graph_symbol_turn_down(const struct graph_symbol *symbol)
 819 {
 820         if (!symbol->continued_down)
 821                 return false;
 822
 823         if (!symbol->continued_right)
 824                 return false;
 825
 826         return true;
 827 }
 828
 829 static const bool
 830 graph_symbol_merge(const struct graph_symbol *symbol)
 831 {
 832         if (symbol->continued_down)
 833                 return false;
 834
 835         if (!symbol->parent_down)
 836                 return false;
 837
 838         if (symbol->parent_right)
 839                 return false;
 840
 841         return true;
 842 }
 843
 844 static const bool
 845 graph_symbol_multi_merge(const struct graph_symbol *symbol)
 846 {
 847         if (!symbol->parent_down)
 848                 return false;
 849
 850         if (!symbol->parent_right)
 851                 return false;
 852
 853         return true;
 854 }
 855
 856 static const bool
 857 graph_symbol_vertical_bar(const struct graph_symbol *symbol)
 858 {
 859         if (symbol->empty)
 860                 return false;
 861
 862         if (symbol->shift_left)
 863                 return false;
 864
 865         if (!symbol->continued_down)
 866                 return false;
 867
 868         if (symbol->continued_up)
 869                 return true;
 870
 871         if (symbol->parent_right)
 872                 return false;
 873
 874         if (symbol->flanked)
 875                 return false;
 876
 877         if (symbol->continued_right)
 878                 return false;
 879
 880         return true;
 881 }
 882
 883 static const bool
 884 graph_symbol_horizontal_bar(const struct graph_symbol *symbol)
 885 {
 886         if (symbol->shift_left)
 887                 return true;
 888
 889         if (symbol->continued_down)
 890                 return false;
 891
 892         if (!symbol->parent_right && !symbol->continued_right)
 893                 return false;
 894
 895         if ((symbol->continued_up && !symbol->continued_up_left))
 896                 return false;
 897
 898         if (!symbol->below_commit)
 899                 return true;
 900
 901         return false;
 902 }
 903
 904 static const bool
 905 graph_symbol_multi_branch(const struct graph_symbol *symbol)
 906 {
 907         if (symbol->continued_down)
 908                 return false;
 909
 910         if (!symbol->continued_right)
 911                 return false;
 912
 913         if (symbol->below_shift)
 914                 return false;
 915
 916         if (symbol->continued_up || symbol->new_column || symbol->below_commit) {
 917                 if (symbol->matches_commit)
 918                         return true;
 919
 920                 if (symbol->shift_left)
 921                         return true;
 922         }
 923
 924         return false;
 925 }
 926
 927 static const char *
 928 graph_symbol_to_utf8(const struct graph_symbol *symbol)
 929 {
 930         if (symbol->commit) {
 931                 if (symbol->boundary)
 932                         return " ◯";
 933                 else if (symbol->initial)
 934                         return " ◎";
 935                 else if (symbol->merge)
 936                         return " ●";
 937                 return " ●";
 938         }
 939
 940         if (graph_symbol_cross_over(symbol))
 941                 return "─│";
 942
 943         if (graph_symbol_vertical_bar(symbol))
 944                 return " │";
 945
 946         if (graph_symbol_turn_left(symbol))
 947                 return "─╯";
 948
 949         if (graph_symbol_multi_branch(symbol))
 950                 return "─┴";
 951
 952         if (graph_symbol_horizontal_bar(symbol))
 953                 return "──";
 954
 955         if (graph_symbol_forks(symbol))
 956                 return " ├";
 957
 958         if (graph_symbol_turn_down_cross_over(symbol))
 959                 return "─╭";
 960
 961         if (graph_symbol_turn_down(symbol))
 962                 return " ╭";
 963
 964         if (graph_symbol_merge(symbol))
 965                 return "─╮";
 966
 967         if (graph_symbol_multi_merge(symbol))
 968                 return "─┬";
 969
 970         return "  ";
 971 }
 972
 973 static const chtype *
 974 graph_symbol_to_chtype(const struct graph_symbol *symbol)
 975 {
 976         static chtype graphics[2];
 977
 978         if (symbol->commit) {
 979                 graphics[0] = ' ';
 980                 if (symbol->boundary)
 981                         graphics[1] = 'o';
 982                 else if (symbol->initial)
 983                         graphics[1] = 'I';
 984                 else if (symbol->merge)
 985                         graphics[1] = 'M';
 986                 else
 987                         graphics[1] = 'o'; //ACS_DIAMOND; //'*';
 988                 return graphics;
 989
 990         } else if (graph_symbol_cross_over(symbol)) {
 991                 graphics[0] = ACS_HLINE;
 992                 graphics[1] = ACS_VLINE;
 993
 994         } else if (graph_symbol_vertical_bar(symbol)) {
 995                 graphics[0] = ' ';
 996                 graphics[1] = ACS_VLINE;
 997
 998         } else if (graph_symbol_turn_left(symbol)) {
 999                 graphics[0] = ACS_HLINE;
1000                 graphics[1] = ACS_LRCORNER;
1001
1002         } else if (graph_symbol_multi_branch(symbol)) {
1003                 graphics[0] = ACS_HLINE;
1004                 graphics[1] = ACS_BTEE;
1005
1006         } else if (graph_symbol_horizontal_bar(symbol)) {
1007                 graphics[0] = graphics[1] = ACS_HLINE;
1008
1009         } else if (graph_symbol_forks(symbol)) {
1010                 graphics[0] = ' ';
1011                 graphics[1] = ACS_LTEE;
1012
1013         } else if (graph_symbol_turn_down_cross_over(symbol)) {
1014                 graphics[0] = ACS_HLINE;
1015                 graphics[1] = ACS_ULCORNER;
1016
1017         } else if (graph_symbol_turn_down(symbol)) {
1018                 graphics[0] = ' ';
1019                 graphics[1] = ACS_ULCORNER;
1020
1021         } else if (graph_symbol_merge(symbol)) {
1022                 graphics[0] = ACS_HLINE;
1023                 graphics[1] = ACS_URCORNER;
1024
1025         } else if (graph_symbol_multi_merge(symbol)) {
1026                 graphics[0] = ACS_HLINE;
1027                 graphics[1] = ACS_TTEE;
1028
1029         } else {
1030                 graphics[0] = graphics[1] = ' ';
1031         }
1032
1033         return graphics;
1034 }
1035
1036 static const char *
1037 graph_symbol_to_ascii(const struct graph_symbol *symbol)
1038 {
1039         if (symbol->commit) {
1040                 if (symbol->boundary)
1041                         return " o";
1042                 else if (symbol->initial)
1043                         return " I";
1044                 else if (symbol->merge)
1045                         return " M";
1046                 return " *";
1047         }
1048
1049         if (graph_symbol_cross_over(symbol))
1050                 return "-|";
1051
1052         if (graph_symbol_vertical_bar(symbol))
1053                 return " |";
1054
1055         if (graph_symbol_turn_left(symbol))
1056                 return "-'";
1057
1058         if (graph_symbol_multi_branch(symbol))
1059                 return "-+";
1060
1061         if (graph_symbol_horizontal_bar(symbol))
1062                 return "--";
1063
1064         if (graph_symbol_forks(symbol))
1065                 return " +";
1066
1067         if (graph_symbol_turn_down_cross_over(symbol))
1068                 return "-.";
1069
1070         if (graph_symbol_turn_down(symbol))
1071                 return " .";
1072
1073         if (graph_symbol_merge(symbol))
1074                 return "-.";
1075
1076         if (graph_symbol_multi_merge(symbol))
1077                 return "-+";
1078
1079         return "  ";
1080 }
1081
1082 static void
1083 graph_foreach_symbol(const struct graph *graph, const struct graph_canvas *canvas,
1084                      graph_symbol_iterator_fn fn, void *data)
1085 {
1086         int i;
1087
1088         for (i = 0; i < canvas->size; i++) {
1089                 struct graph_symbol *symbol = &canvas->symbols[i];
1090                 int color_id = symbol->commit ? GRAPH_COMMIT_COLOR : symbol->color;
1091
1092                 if (fn(data, graph, symbol, color_id, i == 0))
1093                         break;
1094         }
1095 }
1096
1097 struct graph *
1098 init_graph_v2(void)
1099 {
1100         struct graph_v2 *graph = calloc(1, sizeof(*graph));
1101         struct graph *api;
1102
1103         if (!graph)
1104                 return NULL;
1105
1106         api = &graph->api;
1107         api->private = graph;
1108         api->done = done_graph;
1109         api->done_rendering = done_graph_rendering;
1110         api->add_commit = graph_add_commit;
1111         api->add_parent = graph_add_parent;
1112         api->render_parents = graph_render_parents;
1113         api->foreach_symbol = graph_foreach_symbol;
1114         api->symbol_to_ascii = graph_symbol_to_ascii;
1115         api->symbol_to_utf8 = graph_symbol_to_utf8;
1116         api->symbol_to_chtype = graph_symbol_to_chtype;
1117
1118         return api;
1119 }
1120
1121 /* vim: set ts=8 sw=8 noexpandtab: */