graph.c

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