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                         row->columns[i] = row->columns[i + 1];
 417         }
 418 }
 419
 420 static void
 421 graph_fill_empty_columns(struct graph_v2 *graph)
 422 {
 423         struct graph_row *row = &graph->next_row;
 424         int i;
 425
 426         for (i = row->size - 2; i >= 0; i--) {
 427                 if (!graph_column_has_commit(&row->columns[i])) {
 428                         row->columns[i] = row->columns[i + 1];
 429                 }
 430         }
 431 }
 432
 433 static void
 434 graph_generate_next_row(struct graph_v2 *graph)
 435 {
 436         graph_row_clear_commit(&graph->next_row, graph->id);
 437         graph_insert_parents(graph);
 438         graph_remove_collapsed_columns(graph);
 439         graph_fill_empty_columns(graph);
 440 }
 441
 442 static int
 443 commits_in_row(struct graph_row *row)
 444 {
 445         int count = 0;
 446         int i;
 447
 448         for (i = 0; i < row->size;i++) {
 449                 if (graph_column_has_commit(&row->columns[i]))
 450                         count++;
 451         }
 452
 453         return count;
 454 }
 455
 456 static void
 457 graph_commit_next_row(struct graph_v2 *graph)
 458 {
 459         int i;
 460
 461         for (i = 0; i < graph->row.size; i++) {
 462                 graph->prev_row.columns[i] = graph->row.columns[i];
 463
 464                 if (i == graph->position && commits_in_row(&graph->parents) > 0)
 465                         graph->prev_row.columns[i] = graph->next_row.columns[i];
 466
 467                 if (!graph_column_has_commit(&graph->prev_row.columns[i]))
 468                         graph->prev_row.columns[i] = graph->next_row.columns[i];
 469
 470                 graph->row.columns[i] = graph->next_row.columns[i];
 471         }
 472
 473         graph->prev_position = graph->position;
 474 }
 475
 476 static bool
 477 continued_down(struct graph_row *row, struct graph_row *next_row, int pos)
 478 {
 479         if (strcmp(row->columns[pos].id, next_row->columns[pos].id) != 0)
 480                 return false;
 481
 482         if (row->columns[pos].symbol.shift_left)
 483                 return false;
 484
 485         return true;
 486 }
 487
 488 static bool
 489 shift_left(struct graph_row *row, struct graph_row *prev_row, int pos)
 490 {
 491         int i;
 492
 493         if (!graph_column_has_commit(&row->columns[pos]))
 494                 return false;
 495
 496         for (i = pos - 1; i >= 0; i--) {
 497                 if (!graph_column_has_commit(&row->columns[i]))
 498                         continue;
 499
 500                 if (strcmp(row->columns[i].id, row->columns[pos].id) != 0)
 501                         continue;
 502
 503                 if (!continued_down(prev_row, row, i))
 504                         return true;
 505
 506                 break;
 507         }
 508
 509         return false;
 510 }
 511
 512 static bool
 513 new_column(struct graph_row *row, struct graph_row *prev_row, int pos)
 514 {
 515         int i;
 516
 517         if (!graph_column_has_commit(&prev_row->columns[pos]))
 518                 return true;
 519
 520         for (i = pos; i < row->size; i++) {
 521                 if (strcmp(row->columns[pos].id, prev_row->columns[i].id) == 0)
 522                         return false;
 523         }
 524
 525         return true;
 526 }
 527
 528 static bool
 529 continued_right(struct graph_row *row, int pos, int commit_pos)
 530 {
 531         int i, end;
 532
 533         if (pos < commit_pos)
 534                 end = commit_pos;
 535         else
 536                 end = row->size;
 537
 538         for (i = pos + 1; i < end; i++) {
 539                 if (strcmp(row->columns[pos].id, row->columns[i].id) == 0)
 540                         return true;
 541         }
 542
 543         return false;
 544 }
 545
 546 static bool
 547 continued_left(struct graph_row *row, int pos, int commit_pos)
 548 {
 549         int i, start;
 550
 551         if (pos < commit_pos)
 552                 start = 0;
 553         else
 554                 start = commit_pos;
 555
 556         for (i = start; i < pos; i++) {
 557                 if (!graph_column_has_commit(&row->columns[i]))
 558                         continue;
 559
 560                 if (strcmp(row->columns[pos].id, row->columns[i].id) == 0)
 561                         return true;
 562         }
 563
 564         return false;
 565 }
 566
 567 static bool
 568 parent_down(struct graph_row *parents, struct graph_row *next_row, int pos)
 569 {
 570         int parent;
 571
 572         for (parent = 0; parent < parents->size; parent++) {
 573                 if (!graph_column_has_commit(&parents->columns[parent]))
 574                         continue;
 575
 576                 if (strcmp(parents->columns[parent].id, next_row->columns[pos].id) == 0)
 577                         return true;
 578         }
 579
 580         return false;
 581 }
 582
 583 static bool
 584 parent_right(struct graph_row *parents, struct graph_row *row, struct graph_row *next_row, int pos)
 585 {
 586         int parent, i;
 587
 588         for (parent = 0; parent < parents->size; parent++) {
 589                 if (!graph_column_has_commit(&parents->columns[parent]))
 590                         continue;
 591
 592                 for (i = pos + 1; i < next_row->size; i++) {
 593                         if (strcmp(parents->columns[parent].id, next_row->columns[i].id) != 0)
 594                                 continue;
 595
 596                         if (strcmp(parents->columns[parent].id, row->columns[i].id) != 0)
 597                                 return true;
 598                 }
 599         }
 600
 601         return false;
 602 }
 603
 604 static bool
 605 flanked(struct graph_row *row, int pos, int commit_pos, const char *commit_id)
 606 {
 607         int i, start, end;
 608
 609         if (pos < commit_pos) {
 610                 start = 0;
 611                 end = pos;
 612         } else {
 613                 start = pos + 1;
 614                 end = row->size;
 615         }
 616
 617         for (i = start; i < end; i++) {
 618                 if (strcmp(row->columns[i].id, commit_id) == 0)
 619                         return true;
 620         }
 621
 622         return false;
 623 }
 624
 625 static bool
 626 below_commit(int pos, struct graph_v2 *graph)
 627 {
 628         if (!pos == graph->prev_position)
 629                 return false;
 630
 631         if (!strcmp(graph->row.columns[pos].id, graph->prev_row.columns[pos].id) == 0)
 632                 return false;
 633
 634         return true;
 635 }
 636
 637 static void
 638 graph_generate_symbols(struct graph_v2 *graph, struct graph_canvas *canvas)
 639 {
 640         struct graph_row *prev_row = &graph->prev_row;
 641         struct graph_row *row = &graph->row;
 642         struct graph_row *next_row = &graph->next_row;
 643         struct graph_row *parents = &graph->parents;
 644         int pos;
 645
 646         for (pos = 0; pos < row->size; pos++) {
 647                 struct graph_column *column = &row->columns[pos];
 648                 struct graph_symbol *symbol = &column->symbol;
 649                 char *id = next_row->columns[pos].id;
 650
 651                 symbol->commit            = (pos == graph->position);
 652                 symbol->boundary          = (pos == graph->position && next_row->columns[pos].symbol.boundary);
 653                 symbol->initial           = (commits_in_row(parents) < 1);
 654                 symbol->merge             = (commits_in_row(parents) > 1);
 655
 656                 symbol->continued_down    = continued_down(row, next_row, pos);
 657                 symbol->continued_up      = continued_down(prev_row, row, pos);
 658                 symbol->continued_right   = continued_right(row, pos, graph->position);
 659                 symbol->continued_left    = continued_left(row, pos, graph->position);
 660                 symbol->continued_up_left = continued_left(prev_row, pos, prev_row->size);
 661
 662                 symbol->parent_down       = parent_down(parents, next_row, pos);
 663                 symbol->parent_right      = (pos > graph->position && parent_right(parents, row, next_row, pos));
 664
 665                 symbol->below_commit      = below_commit(pos, graph);
 666                 symbol->flanked           = flanked(row, pos, graph->position, graph->id);
 667                 symbol->next_right        = continued_right(next_row, pos, 0);
 668                 symbol->matches_commit    = (strcmp(column->id, graph->id) == 0);
 669
 670                 symbol->shift_left        = shift_left(row, prev_row, pos);
 671                 symbol->continue_shift    = shift_left(row, prev_row, pos + 1);
 672                 symbol->below_shift       = prev_row->columns[pos].symbol.shift_left;
 673
 674                 symbol->new_column        = new_column(row, prev_row, pos);
 675                 symbol->empty             = (!graph_column_has_commit(&row->columns[pos]));
 676
 677                 if (graph_column_has_commit(column)) {
 678                         id = column->id;
 679                 }
 680                 symbol->color = get_color(graph, id);
 681
 682                 graph_canvas_append_symbol(graph, canvas, symbol);
 683         }
 684
 685         colors_remove_id(&graph->colors, graph->id);
 686 }
 687
 688 static bool
 689 graph_render_parents(struct graph *graph_ref, struct graph_canvas *canvas)
 690 {
 691         struct graph_v2 *graph = graph_ref->private;
 692
 693         if (graph->parents.size == 0 &&
 694             !graph_add_parent(graph_ref, ""))
 695                 return FALSE;
 696
 697         if (!graph_expand(graph))
 698                 return FALSE;
 699
 700         graph_generate_next_row(graph);
 701         graph_generate_symbols(graph, canvas);
 702         graph_commit_next_row(graph);
 703
 704         graph->parents.size = graph->position = 0;
 705
 706         if (!graph_collapse(graph))
 707                 return FALSE;
 708
 709         return TRUE;
 710 }
 711
 712 static bool
 713 graph_add_commit(struct graph *graph_ref, struct graph_canvas *canvas,
 714                  const char *id, const char *parents, bool is_boundary)
 715 {
 716         struct graph_v2 *graph = graph_ref->private;
 717         int has_parents = 0;
 718
 719         graph->position = graph_find_column_by_id(&graph->row, id);
 720         string_copy_rev(graph->id, id);
 721         graph->is_boundary = is_boundary;
 722         graph->has_parents = FALSE;
 723
 724         while ((parents = strchr(parents, ' '))) {
 725                 parents++;
 726                 if (!graph_add_parent(graph_ref, parents))
 727                         return FALSE;
 728                 has_parents++;
 729         }
 730
 731         graph->has_parents = has_parents > 0;
 732
 733         return TRUE;
 734 }
 735
 736 static const bool
 737 graph_symbol_forks(const struct graph_symbol *symbol)
 738 {
 739         if (!symbol->continued_down)
 740                 return false;
 741
 742         if (!symbol->continued_right)
 743                 return false;
 744
 745         if (!symbol->continued_up)
 746                 return false;
 747
 748         return true;
 749 }
 750
 751 static const bool
 752 graph_symbol_cross_over(const struct graph_symbol *symbol)
 753 {
 754         if (symbol->empty)
 755                 return false;
 756
 757         if (!symbol->continued_down)
 758                 return false;
 759
 760         if (!symbol->continued_up && !symbol->new_column && !symbol->below_commit)
 761                 return false;
 762
 763         if (symbol->shift_left)
 764                 return false;
 765
 766         if (symbol->parent_right && symbol->merge)
 767                 return true;
 768
 769         if (symbol->flanked)
 770                 return true;
 771
 772         return false;
 773 }
 774
 775 static const bool
 776 graph_symbol_turn_left(const struct graph_symbol *symbol)
 777 {
 778         if (symbol->matches_commit && symbol->continued_right && !symbol->continued_down)
 779                 return false;
 780
 781         if (symbol->continue_shift)
 782                 return false;
 783
 784         if (symbol->continued_up || symbol->new_column || symbol->below_commit) {
 785                 if (symbol->matches_commit)
 786                         return true;
 787
 788                 if (symbol->shift_left)
 789                         return true;
 790         }
 791
 792         return false;
 793 }
 794
 795 static const bool
 796 graph_symbol_turn_down_cross_over(const struct graph_symbol *symbol)
 797 {
 798         if (!symbol->continued_down)
 799                 return false;
 800
 801         if (!symbol->continued_right)
 802                 return false;
 803
 804         if (symbol->flanked)
 805                 return true;
 806
 807         if (symbol->merge)
 808                 return true;
 809
 810         return false;
 811 }
 812
 813 static const bool
 814 graph_symbol_turn_down(const struct graph_symbol *symbol)
 815 {
 816         if (!symbol->continued_down)
 817                 return false;
 818
 819         if (!symbol->continued_right)
 820                 return false;
 821
 822         return true;
 823 }
 824
 825 static const bool
 826 graph_symbol_merge(const struct graph_symbol *symbol)
 827 {
 828         if (symbol->continued_down)
 829                 return false;
 830
 831         if (!symbol->parent_down)
 832                 return false;
 833
 834         if (symbol->parent_right)
 835                 return false;
 836
 837         return true;
 838 }
 839
 840 static const bool
 841 graph_symbol_multi_merge(const struct graph_symbol *symbol)
 842 {
 843         if (!symbol->parent_down)
 844                 return false;
 845
 846         if (!symbol->parent_right)
 847                 return false;
 848
 849         return true;
 850 }
 851
 852 static const bool
 853 graph_symbol_vertical_bar(const struct graph_symbol *symbol)
 854 {
 855         if (symbol->empty)
 856                 return false;
 857
 858         if (symbol->shift_left)
 859                 return false;
 860
 861         if (!symbol->continued_down)
 862                 return false;
 863
 864         if (symbol->continued_up)
 865                 return true;
 866
 867         if (symbol->parent_right)
 868                 return false;
 869
 870         if (symbol->flanked)
 871                 return false;
 872
 873         if (symbol->continued_right)
 874                 return false;
 875
 876         return true;
 877 }
 878
 879 static const bool
 880 graph_symbol_horizontal_bar(const struct graph_symbol *symbol)
 881 {
 882         if (symbol->shift_left)
 883                 return true;
 884
 885         if (symbol->continued_down)
 886                 return false;
 887
 888         if (!symbol->parent_right && !symbol->continued_right)
 889                 return false;
 890
 891         if ((symbol->continued_up && !symbol->continued_up_left))
 892                 return false;
 893
 894         if (!symbol->below_commit)
 895                 return true;
 896
 897         return false;
 898 }
 899
 900 static const bool
 901 graph_symbol_multi_branch(const struct graph_symbol *symbol)
 902 {
 903         if (symbol->continued_down)
 904                 return false;
 905
 906         if (!symbol->continued_right)
 907                 return false;
 908
 909         if (symbol->below_shift)
 910                 return false;
 911
 912         if (symbol->continued_up || symbol->new_column || symbol->below_commit) {
 913                 if (symbol->matches_commit)
 914                         return true;
 915
 916                 if (symbol->shift_left)
 917                         return true;
 918         }
 919
 920         return false;
 921 }
 922
 923 static const char *
 924 graph_symbol_to_utf8(const struct graph_symbol *symbol)
 925 {
 926         if (symbol->commit) {
 927                 if (symbol->boundary)
 928                         return " ◯";
 929                 else if (symbol->initial)
 930                         return " ◎";
 931                 else if (symbol->merge)
 932                         return " ●";
 933                 return " ●";
 934         }
 935
 936         if (graph_symbol_cross_over(symbol))
 937                 return "─│";
 938
 939         if (graph_symbol_vertical_bar(symbol))
 940                 return " │";
 941
 942         if (graph_symbol_turn_left(symbol))
 943                 return "─╯";
 944
 945         if (graph_symbol_multi_branch(symbol))
 946                 return "─┴";
 947
 948         if (graph_symbol_horizontal_bar(symbol))
 949                 return "──";
 950
 951         if (graph_symbol_forks(symbol))
 952                 return " ├";
 953
 954         if (graph_symbol_turn_down_cross_over(symbol))
 955                 return "─╭";
 956
 957         if (graph_symbol_turn_down(symbol))
 958                 return " ╭";
 959
 960         if (graph_symbol_merge(symbol))
 961                 return "─╮";
 962
 963         if (graph_symbol_multi_merge(symbol))
 964                 return "─┬";
 965
 966         return "  ";
 967 }
 968
 969 static const chtype *
 970 graph_symbol_to_chtype(const struct graph_symbol *symbol)
 971 {
 972         static chtype graphics[2];
 973
 974         if (symbol->commit) {
 975                 graphics[0] = ' ';
 976                 if (symbol->boundary)
 977                         graphics[1] = 'o';
 978                 else if (symbol->initial)
 979                         graphics[1] = 'I';
 980                 else if (symbol->merge)
 981                         graphics[1] = 'M';
 982                 else
 983                         graphics[1] = 'o'; //ACS_DIAMOND; //'*';
 984                 return graphics;
 985
 986         } else if (graph_symbol_cross_over(symbol)) {
 987                 graphics[0] = ACS_HLINE;
 988                 graphics[1] = ACS_VLINE;
 989
 990         } else if (graph_symbol_vertical_bar(symbol)) {
 991                 graphics[0] = ' ';
 992                 graphics[1] = ACS_VLINE;
 993
 994         } else if (graph_symbol_turn_left(symbol)) {
 995                 graphics[0] = ACS_HLINE;
 996                 graphics[1] = ACS_LRCORNER;
 997
 998         } else if (graph_symbol_multi_branch(symbol)) {
 999                 graphics[0] = ACS_HLINE;
1000                 graphics[1] = ACS_BTEE;
1001
1002         } else if (graph_symbol_horizontal_bar(symbol)) {
1003                 graphics[0] = graphics[1] = ACS_HLINE;
1004
1005         } else if (graph_symbol_forks(symbol)) {
1006                 graphics[0] = ' ';
1007                 graphics[1] = ACS_LTEE;
1008
1009         } else if (graph_symbol_turn_down_cross_over(symbol)) {
1010                 graphics[0] = ACS_HLINE;
1011                 graphics[1] = ACS_ULCORNER;
1012
1013         } else if (graph_symbol_turn_down(symbol)) {
1014                 graphics[0] = ' ';
1015                 graphics[1] = ACS_ULCORNER;
1016
1017         } else if (graph_symbol_merge(symbol)) {
1018                 graphics[0] = ACS_HLINE;
1019                 graphics[1] = ACS_URCORNER;
1020
1021         } else if (graph_symbol_multi_merge(symbol)) {
1022                 graphics[0] = ACS_HLINE;
1023                 graphics[1] = ACS_TTEE;
1024
1025         } else {
1026                 graphics[0] = graphics[1] = ' ';
1027         }
1028
1029         return graphics;
1030 }
1031
1032 static const char *
1033 graph_symbol_to_ascii(const struct graph_symbol *symbol)
1034 {
1035         if (symbol->commit) {
1036                 if (symbol->boundary)
1037                         return " o";
1038                 else if (symbol->initial)
1039                         return " I";
1040                 else if (symbol->merge)
1041                         return " M";
1042                 return " *";
1043         }
1044
1045         if (graph_symbol_cross_over(symbol))
1046                 return "-|";
1047
1048         if (graph_symbol_vertical_bar(symbol))
1049                 return " |";
1050
1051         if (graph_symbol_turn_left(symbol))
1052                 return "-'";
1053
1054         if (graph_symbol_multi_branch(symbol))
1055                 return "-+";
1056
1057         if (graph_symbol_horizontal_bar(symbol))
1058                 return "--";
1059
1060         if (graph_symbol_forks(symbol))
1061                 return " +";
1062
1063         if (graph_symbol_turn_down_cross_over(symbol))
1064                 return "-.";
1065
1066         if (graph_symbol_turn_down(symbol))
1067                 return " .";
1068
1069         if (graph_symbol_merge(symbol))
1070                 return "-.";
1071
1072         if (graph_symbol_multi_merge(symbol))
1073                 return "-+";
1074
1075         return "  ";
1076 }
1077
1078 static void
1079 graph_foreach_symbol(const struct graph *graph, const struct graph_canvas *canvas,
1080                      graph_symbol_iterator_fn fn, void *data)
1081 {
1082         int i;
1083
1084         for (i = 0; i < canvas->size; i++) {
1085                 struct graph_symbol *symbol = &canvas->symbols[i];
1086                 int color_id = symbol->commit ? GRAPH_COMMIT_COLOR : symbol->color;
1087
1088                 if (fn(data, graph, symbol, color_id, i == 0))
1089                         break;
1090         }
1091 }
1092
1093 struct graph *
1094 init_graph_v2(void)
1095 {
1096         struct graph_v2 *graph = calloc(1, sizeof(*graph));
1097         struct graph *api;
1098
1099         if (!graph)
1100                 return NULL;
1101
1102         api = &graph->api;
1103         api->private = graph;
1104         api->done = done_graph;
1105         api->done_rendering = done_graph_rendering;
1106         api->add_commit = graph_add_commit;
1107         api->add_parent = graph_add_parent;
1108         api->render_parents = graph_render_parents;
1109         api->foreach_symbol = graph_foreach_symbol;
1110         api->symbol_to_ascii = graph_symbol_to_ascii;
1111         api->symbol_to_utf8 = graph_symbol_to_utf8;
1112         api->symbol_to_chtype = graph_symbol_to_chtype;
1113
1114         return api;
1115 }
1116
1117 /* vim: set ts=8 sw=8 noexpandtab: */