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 static size_t get_free_graph_color(struct graph *graph)
  21 {
  22         size_t i, free_color;
  23
  24         for (free_color = i = 0; i < ARRAY_SIZE(graph->colors); i++) {
  25                 if (graph->colors[i] < graph->colors[free_color])
  26                         free_color = i;
  27         }
  28
  29         graph->colors[free_color]++;
  30         return free_color;
  31 }
  32
  33 void
  34 done_graph(struct graph *graph)
  35 {
  36         free(graph->row.columns);
  37         free(graph->parents.columns);
  38         memset(graph, 0, sizeof(*graph));
  39 }
  40
  41 #define graph_column_has_commit(col) ((col)->id[0])
  42
  43 static size_t
  44 graph_find_column_by_id(struct graph_row *row, const char *id)
  45 {
  46         size_t free_column = row->size;
  47         size_t i;
  48
  49         for (i = 0; i < row->size; i++) {
  50                 if (!graph_column_has_commit(&row->columns[i]))
  51                         free_column = i;
  52                 else if (!strcmp(row->columns[i].id, id))
  53                         return i;
  54         }
  55
  56         return free_column;
  57 }
  58
  59 static struct graph_column *
  60 graph_insert_column(struct graph *graph, struct graph_row *row, size_t pos, const char *id)
  61 {
  62         struct graph_column *column;
  63
  64         if (!realloc_graph_columns(&row->columns, row->size, 1))
  65                 return NULL;
  66
  67         column = &row->columns[pos];
  68         if (pos < row->size) {
  69                 memmove(column + 1, column, sizeof(*column) * (row->size - pos));
  70         }
  71
  72         row->size++;
  73         memset(column, 0, sizeof(*column));
  74         string_copy_rev(column->id, id);
  75         column->symbol.boundary = !!graph->is_boundary;
  76
  77         return column;
  78 }
  79
  80 struct graph_column *
  81 graph_add_parent(struct graph *graph, const char *parent)
  82 {
  83         return graph_insert_column(graph, &graph->parents, graph->parents.size, parent);
  84 }
  85
  86 static bool
  87 graph_needs_expansion(struct graph *graph)
  88 {
  89         return graph->position + graph->parents.size > graph->row.size;
  90 #if 0
  91         return graph->parents.size > 1
  92             && graph->expanded < graph->parents.size;
  93 #endif
  94 }
  95
  96 static bool
  97 graph_expand(struct graph *graph)
  98 {
  99         while (graph_needs_expansion(graph)) {
 100                 if (!graph_insert_column(graph, &graph->row, graph->position + graph->expanded, ""))
 101                         return FALSE;
 102                 graph->expanded++;
 103         }
 104
 105         return TRUE;
 106 }
 107
 108 static bool
 109 graph_needs_collapsing(struct graph *graph)
 110 {
 111         return graph->row.size > 1
 112             && !graph_column_has_commit(&graph->row.columns[graph->row.size - 1]);
 113 }
 114
 115 static bool
 116 graph_collapse(struct graph *graph)
 117 {
 118         while (graph_needs_collapsing(graph)) {
 119                 graph->row.size--;
 120         }
 121
 122         return TRUE;
 123 }
 124
 125 static void
 126 graph_reorder_parents(struct graph *graph)
 127 {
 128         struct graph_row *row = &graph->row;
 129         struct graph_row *parents = &graph->parents;
 130         int i;
 131
 132         if (parents->size == 1)
 133                 return;
 134
 135         for (i = 0; i < parents->size; i++) {
 136                 struct graph_column *column = &parents->columns[i];
 137                 size_t match = graph_find_column_by_id(row, column->id);
 138
 139                 if (match < graph->position && graph_column_has_commit(&row->columns[match])) {
 140                         //die("Reorder: %s -> %s", graph->commit->id, column->id);
 141 //                      row->columns[match].symbol.initial = 1;
 142                 }
 143         }
 144 }
 145
 146 static void
 147 graph_canvas_append_symbol(struct graph *graph, struct graph_symbol *symbol)
 148 {
 149         struct graph_canvas *canvas = graph->canvas;
 150
 151         if (realloc_graph_symbols(&canvas->symbols, canvas->size, 1))
 152                 canvas->symbols[canvas->size++] = *symbol;
 153 }
 154
 155 static bool
 156 graph_insert_parents(struct graph *graph)
 157 {
 158         struct graph_row *row = &graph->row;
 159         struct graph_row *parents = &graph->parents;
 160         size_t orig_size = row->size;
 161         bool branched = FALSE;
 162         bool merge = parents->size > 1;
 163         int pos;
 164
 165         assert(!graph_needs_expansion(graph));
 166
 167         for (pos = 0; pos < graph->position; pos++) {
 168                 struct graph_column *column = &row->columns[pos];
 169                 struct graph_symbol symbol = column->symbol;
 170
 171                 if (graph_column_has_commit(column)) {
 172                         size_t match = graph_find_column_by_id(parents, column->id);
 173
 174                         if (match < parents->size) {
 175                                 column->symbol.initial = 1;
 176                         }
 177
 178                         symbol.branch = 1;
 179                 }
 180                 symbol.vbranch = !!branched;
 181                 if (!strcmp(column->id, graph->id)) {
 182                         branched = TRUE;
 183                         column->id[0] = 0;
 184                 }
 185
 186                 graph_canvas_append_symbol(graph, &symbol);
 187         }
 188
 189         for (; pos < graph->position + parents->size; pos++) {
 190                 struct graph_column *old = &row->columns[pos];
 191                 struct graph_column *new = &parents->columns[pos - graph->position];
 192                 struct graph_symbol symbol = old->symbol;
 193
 194                 symbol.merge = !!merge;
 195
 196                 if (pos == graph->position) {
 197                         symbol.commit = 1;
 198                         if (new->symbol.boundary) {
 199                                 symbol.boundary = 1;
 200                         } else if (!graph_column_has_commit(new)) {
 201                                 symbol.initial = 1;
 202                         }
 203
 204                 } else if (!strcmp(old->id, new->id) && orig_size == row->size) {
 205                         symbol.vbranch = 1;
 206                         symbol.branch = 1;
 207                         //symbol.merge = 1;
 208
 209                 } else if (parents->size > 1) {
 210                         symbol.merge = 1;
 211                         symbol.vbranch = !(pos == graph->position + parents->size - 1);
 212
 213                 } else if (graph_column_has_commit(old)) {
 214                         symbol.branch = 1;
 215                 }
 216
 217                 graph_canvas_append_symbol(graph, &symbol);
 218                 if (!graph_column_has_commit(old))
 219                         new->symbol.color = get_free_graph_color(graph);
 220                 *old = *new;
 221         }
 222
 223         for (; pos < row->size; pos++) {
 224                 bool too = !strcmp(row->columns[row->size - 1].id, graph->id);
 225                 struct graph_symbol symbol = row->columns[pos].symbol;
 226
 227                 symbol.vbranch = !!too;
 228                 if (row->columns[pos].id[0]) {
 229                         symbol.branch = 1;
 230                         if (!strcmp(row->columns[pos].id, graph->id)) {
 231                                 symbol.branched = 1;
 232                                 if (too && pos != row->size - 1) {
 233                                         symbol.vbranch = 1;
 234                                 } else {
 235                                         symbol.vbranch = 0;
 236                                 }
 237                                 row->columns[pos].id[0] = 0;
 238                         }
 239                 }
 240                 graph_canvas_append_symbol(graph, &symbol);
 241         }
 242
 243         graph->parents.size = graph->expanded = graph->position = 0;
 244
 245         return TRUE;
 246 }
 247
 248 bool
 249 graph_render_parents(struct graph *graph)
 250 {
 251         if (!graph_expand(graph))
 252                 return FALSE;
 253         graph_reorder_parents(graph);
 254         graph_insert_parents(graph);
 255         if (!graph_collapse(graph))
 256                 return FALSE;
 257
 258         return TRUE;
 259 }
 260
 261 bool
 262 graph_add_commit(struct graph *graph, struct graph_canvas *canvas,
 263                  const char *id, const char *parents, bool is_boundary)
 264 {
 265         graph->position = graph_find_column_by_id(&graph->row, id);
 266         graph->id = id;
 267         graph->canvas = canvas;
 268         graph->is_boundary = is_boundary;
 269
 270         while ((parents = strchr(parents, ' '))) {
 271                 parents++;
 272                 if (!graph_add_parent(graph, parents))
 273                         return FALSE;
 274                 graph->has_parents = TRUE;
 275         }
 276
 277         if (graph->parents.size == 0 &&
 278             !graph_add_parent(graph, ""))
 279                 return FALSE;
 280
 281         return TRUE;
 282 }
 283
 284 const char *
 285 graph_symbol_to_utf8(struct graph_symbol *symbol)
 286 {
 287         if (symbol->commit) {
 288                 if (symbol->boundary)
 289                         return " ◯";
 290                 else if (symbol->initial)
 291                         return " ◎";
 292                 else if (symbol->merge)
 293                         return " ●";
 294                 return " ●";
 295         }
 296
 297         if (symbol->merge) {
 298                 if (symbol->branch) {
 299                         return "━┪";
 300                 }
 301                 if (symbol->vbranch)
 302                         return "━┯";
 303                 return "━┑";
 304         }
 305
 306         if (symbol->branch) {
 307                 if (symbol->branched) {
 308                         if (symbol->vbranch)
 309                                 return "─┴";
 310                         return "─┘";
 311                 }
 312                 if (symbol->vbranch)
 313                         return "─│";
 314                 return " │";
 315         }
 316
 317         if (symbol->vbranch)
 318                 return "──";
 319
 320         return "  ";
 321 }
 322
 323 const chtype *
 324 graph_symbol_to_chtype(struct graph_symbol *symbol)
 325 {
 326         static chtype graphics[2];
 327
 328         if (symbol->commit) {
 329                 graphics[0] = ' ';
 330                 if (symbol->boundary)
 331                         graphics[1] = 'o';
 332                 else if (symbol->initial)
 333                         graphics[1] = 'I';
 334                 else if (symbol->merge)
 335                         graphics[1] = 'M';
 336                 else
 337                         graphics[1] = 'o'; //ACS_DIAMOND; //'*';
 338                 return graphics;
 339         }
 340
 341         if (symbol->merge) {
 342                 graphics[0] = ACS_HLINE;
 343                 if (symbol->branch)
 344                         graphics[1] = ACS_RTEE;
 345                 else
 346                         graphics[1] = ACS_URCORNER;
 347                 return graphics;
 348         }
 349
 350         if (symbol->branch) {
 351                 graphics[0] = ACS_HLINE;
 352                 if (symbol->branched) {
 353                         if (symbol->vbranch)
 354                                 graphics[1] = ACS_BTEE;
 355                         else
 356                                 graphics[1] = ACS_LRCORNER;
 357                         return graphics;
 358                 }
 359
 360                 if (!symbol->vbranch)
 361                         graphics[0] = ' ';
 362                 graphics[1] = ACS_VLINE;
 363                 return graphics;
 364         }
 365
 366         if (symbol->vbranch) {
 367                 graphics[0] = graphics[1] = ACS_HLINE;
 368         } else
 369                 graphics[0] = graphics[1] = ' ';
 370
 371         return graphics;
 372 }
 373
 374 const char *
 375 graph_symbol_to_ascii(struct graph_symbol *symbol)
 376 {
 377         if (symbol->commit) {
 378                 if (symbol->boundary)
 379                         return " o";
 380                 else if (symbol->initial)
 381                         return " I";
 382                 else if (symbol->merge)
 383                         return " M";
 384                 return " *";
 385         }
 386
 387         if (symbol->merge) {
 388                 if (symbol->branch)
 389                         return "-+";
 390                 return "-.";
 391         }
 392
 393         if (symbol->branch) {
 394                 if (symbol->branched) {
 395                         if (symbol->vbranch)
 396                                 return "-+";
 397                         return "-'";
 398                 }
 399                 if (symbol->vbranch)
 400                         return "-|";
 401                 return " |";
 402         }
 403
 404         if (symbol->vbranch)
 405                 return "--";
 406
 407         return "  ";
 408 }
 409
 410 /* vim: set ts=8 sw=8 noexpandtab: */