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