src/graph.c

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