graph.c

   1 /* Copyright (c) 2006-2010 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         if (graph->position + graph->parents.size > graph->row.size)
  90                 return TRUE;
  91         return graph->parents.size > 1
  92             && graph->position < 0
  93             && graph->expanded < graph->parents.size;
  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                         /*
 199                         if (new->symbol->boundary) {
 200                                 symbol.boundary = 1;
 201                         } else*/
 202                         if (!graph_column_has_commit(new)) {
 203                                 symbol.initial = 1;
 204                         }
 205
 206                 } else if (!strcmp(old->id, new->id) && orig_size == row->size) {
 207                         symbol.vbranch = 1;
 208                         symbol.branch = 1;
 209                         //symbol.merge = 1;
 210
 211                 } else if (parents->size > 1) {
 212                         symbol.merge = 1;
 213                         symbol.vbranch = !(pos == graph->position + parents->size - 1);
 214
 215                 } else if (graph_column_has_commit(old)) {
 216                         symbol.branch = 1;
 217                 }
 218
 219                 graph_canvas_append_symbol(graph, &symbol);
 220                 if (!graph_column_has_commit(old))
 221                         new->symbol.color = get_free_graph_color(graph);
 222                 *old = *new;
 223         }
 224
 225         for (; pos < row->size; pos++) {
 226                 bool too = !strcmp(row->columns[row->size - 1].id, graph->id);
 227                 struct graph_symbol symbol = row->columns[pos].symbol;
 228
 229                 symbol.vbranch = !!too;
 230                 if (row->columns[pos].id[0]) {
 231                         symbol.branch = 1;
 232                         if (!strcmp(row->columns[pos].id, graph->id)) {
 233                                 symbol.branched = 1;
 234                                 if (too && pos != row->size - 1) {
 235                                         symbol.vbranch = 1;
 236                                 } else {
 237                                         symbol.vbranch = 0;
 238                                 }
 239                                 row->columns[pos].id[0] = 0;
 240                         }
 241                 }
 242                 graph_canvas_append_symbol(graph, &symbol);
 243         }
 244
 245         graph->parents.size = graph->expanded = graph->position = 0;
 246
 247         return TRUE;
 248 }
 249
 250 bool
 251 graph_render_parents(struct graph *graph)
 252 {
 253         if (!graph_expand(graph))
 254                 return FALSE;
 255         graph_reorder_parents(graph);
 256         graph_insert_parents(graph);
 257         if (!graph_collapse(graph))
 258                 return FALSE;
 259
 260         return TRUE;
 261 }
 262
 263 bool
 264 graph_add_commit(struct graph *graph, struct graph_canvas *canvas,
 265                  const char *id, const char *parents, bool is_boundary)
 266 {
 267         graph->position = graph_find_column_by_id(&graph->row, id);
 268         graph->id = id;
 269         graph->canvas = canvas;
 270         graph->is_boundary = is_boundary;
 271
 272         while ((parents = strchr(parents, ' '))) {
 273                 parents++;
 274                 if (!graph_add_parent(graph, parents))
 275                         return FALSE;
 276                 graph->has_parents = TRUE;
 277         }
 278
 279         if (graph->parents.size == 0 &&
 280             !graph_add_parent(graph, ""))
 281                 return FALSE;
 282
 283         return TRUE;
 284 }
 285
 286 const char *
 287 graph_symbol_to_utf8(struct graph_symbol *symbol)
 288 {
 289         if (symbol->commit) {
 290                 if (symbol->boundary)
 291                         return " ◯";
 292                 else if (symbol->initial)
 293                         return " ◎";
 294                 else if (symbol->merge)
 295                         return " ●";
 296                 return " ●";
 297         }
 298
 299         if (symbol->merge) {
 300                 if (symbol->branch) {
 301                         return "━┪";
 302                 }
 303                 if (symbol->vbranch)
 304                         return "━┯";
 305                 return "━┑";
 306         }
 307
 308         if (symbol->branch) {
 309                 if (symbol->branched) {
 310                         if (symbol->vbranch)
 311                                 return "─┴";
 312                         return "─┘";
 313                 }
 314                 if (symbol->vbranch)
 315                         return "─│";
 316                 return " │";
 317         }
 318
 319         if (symbol->vbranch)
 320                 return "──";
 321
 322         return "  ";
 323 }
 324
 325 const chtype *
 326 graph_symbol_to_chtype(struct graph_symbol *symbol)
 327 {
 328         static chtype graphics[2];
 329
 330         if (symbol->commit) {
 331                 graphics[0] = ' ';
 332                 if (symbol->boundary)
 333                         graphics[1] = 'o';
 334                 else if (symbol->initial)
 335                         graphics[1] = 'I';
 336                 else if (symbol->merge)
 337                         graphics[1] = 'M';
 338                 else
 339                         graphics[1] = 'o'; //ACS_DIAMOND; //'*';
 340                 return graphics;
 341         }
 342
 343         if (symbol->merge) {
 344                 graphics[0] = ACS_HLINE;
 345                 if (symbol->branch)
 346                         graphics[1] = ACS_RTEE;
 347                 else
 348                         graphics[1] = ACS_URCORNER;
 349                 return graphics;
 350         }
 351
 352         if (symbol->branch) {
 353                 graphics[0] = ACS_HLINE;
 354                 if (symbol->branched) {
 355                         if (symbol->vbranch)
 356                                 graphics[1] = ACS_BTEE;
 357                         else
 358                                 graphics[1] = ACS_LRCORNER;
 359                         return graphics;
 360                 }
 361
 362                 if (!symbol->vbranch)
 363                         graphics[0] = ' ';
 364                 graphics[1] = ACS_VLINE;
 365                 return graphics;
 366         }
 367
 368         if (symbol->vbranch) {
 369                 graphics[0] = graphics[1] = ACS_HLINE;
 370         } else
 371                 graphics[0] = graphics[1] = ' ';
 372
 373         return graphics;
 374 }
 375
 376 const char *
 377 graph_symbol_to_ascii(struct graph_symbol *symbol)
 378 {
 379         if (symbol->commit) {
 380                 if (symbol->boundary)
 381                         return " o";
 382                 else if (symbol->initial)
 383                         return " I";
 384                 else if (symbol->merge)
 385                         return " M";
 386                 return " *";
 387         }
 388
 389         if (symbol->merge) {
 390                 if (symbol->branch)
 391                         return "-+";
 392                 return "-.";
 393         }
 394
 395         if (symbol->branch) {
 396                 if (symbol->branched) {
 397                         if (symbol->vbranch)
 398                                 return "-+";
 399                         return "-'";
 400                 }
 401                 if (symbol->vbranch)
 402                         return "-|";
 403                 return " |";
 404         }
 405
 406         if (symbol->vbranch)
 407                 return "--";
 408
 409         return "  ";
 410 }