1 /* Copyright (c) 2006-2015 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 struct graph_symbol {
19 unsigned int color:8;
20 unsigned int bold:1;
21
22 unsigned int commit:1;
23 unsigned int branch:1;
24
25 unsigned int boundary:1;
26 unsigned int initial:1;
27 unsigned int merge:1;
28
29 unsigned int vbranch:1;
30 unsigned int branched:1;
31 };
32
33 struct graph_column {
34 struct graph_symbol symbol;
35 char id[SIZEOF_REV]; /* Parent SHA1 ID. */
36 };
37
38 struct graph_row {
39 size_t size;
40 struct graph_column *columns;
41 };
42
43 struct graph_v1 {
44 struct graph api;
45 struct graph_row row;
46 struct graph_row parents;
47 size_t position;
48 size_t expanded;
49 const char *id;
50 struct graph_canvas *canvas;
51 size_t colors[GRAPH_COLORS];
52 bool has_parents;
53 bool is_boundary;
54 };
55
56 DEFINE_ALLOCATOR(realloc_graph_columns, struct graph_column, 32)
57 DEFINE_ALLOCATOR(realloc_graph_symbols, struct graph_symbol, 1)
58
get_free_graph_color(struct graph_v1 * graph)59 static size_t get_free_graph_color(struct graph_v1 *graph)
60 {
61 size_t i, free_color;
62
63 for (free_color = i = 0; i < ARRAY_SIZE(graph->colors); i++) {
64 if (graph->colors[i] < graph->colors[free_color])
65 free_color = i;
66 }
67
68 graph->colors[free_color]++;
69 return free_color;
70 }
71
72 static void
done_graph(struct graph * graph_)73 done_graph(struct graph *graph_)
74 {
75 struct graph_v1 *graph = graph_->private;
76
77 free(graph);
78 }
79
80 static void
done_graph_rendering(struct graph * graph_)81 done_graph_rendering(struct graph *graph_)
82 {
83 struct graph_v1 *graph = graph_->private;
84
85 free(graph->row.columns);
86 free(graph->parents.columns);
87 }
88
89 #define graph_column_has_commit(col) ((col)->id[0])
90
91 static size_t
graph_find_column_by_id(struct graph_row * row,const char * id)92 graph_find_column_by_id(struct graph_row *row, const char *id)
93 {
94 size_t free_column = row->size;
95 size_t i;
96
97 for (i = 0; i < row->size; i++) {
98 if (!graph_column_has_commit(&row->columns[i]))
99 free_column = i;
100 else if (!strcmp(row->columns[i].id, id))
101 return i;
102 }
103
104 return free_column;
105 }
106
107 static struct graph_column *
graph_insert_column(struct graph_v1 * graph,struct graph_row * row,size_t pos,const char * id)108 graph_insert_column(struct graph_v1 *graph, struct graph_row *row, size_t pos, const char *id)
109 {
110 struct graph_column *column;
111
112 if (!realloc_graph_columns(&row->columns, row->size, 1))
113 return NULL;
114
115 column = &row->columns[pos];
116 if (pos < row->size) {
117 memmove(column + 1, column, sizeof(*column) * (row->size - pos));
118 }
119
120 row->size++;
121 memset(column, 0, sizeof(*column));
122 string_copy_rev(column->id, id);
123 column->symbol.boundary = !!graph->is_boundary;
124
125 return column;
126 }
127
128 static bool
graph_add_parent(struct graph * graph_,const char * parent)129 graph_add_parent(struct graph *graph_, const char *parent)
130 {
131 struct graph_v1 *graph = graph_->private;
132
133 if (graph->has_parents)
134 return true;
135 return graph_insert_column(graph, &graph->parents, graph->parents.size, parent) != NULL;
136 }
137
138 static bool
graph_needs_expansion(struct graph_v1 * graph)139 graph_needs_expansion(struct graph_v1 *graph)
140 {
141 return graph->position + graph->parents.size > graph->row.size;
142 #if 0
143 return graph->parents.size > 1
144 && graph->expanded < graph->parents.size;
145 #endif
146 }
147
148 static bool
graph_expand(struct graph_v1 * graph)149 graph_expand(struct graph_v1 *graph)
150 {
151 while (graph_needs_expansion(graph)) {
152 if (!graph_insert_column(graph, &graph->row, graph->position + graph->expanded, ""))
153 return false;
154 graph->expanded++;
155 }
156
157 return true;
158 }
159
160 static bool
graph_needs_collapsing(struct graph_v1 * graph)161 graph_needs_collapsing(struct graph_v1 *graph)
162 {
163 return graph->row.size > 1
164 && !graph_column_has_commit(&graph->row.columns[graph->row.size - 1]);
165 }
166
167 static bool
graph_collapse(struct graph_v1 * graph)168 graph_collapse(struct graph_v1 *graph)
169 {
170 while (graph_needs_collapsing(graph)) {
171 graph->row.size--;
172 }
173
174 return true;
175 }
176
177 static void
graph_reorder_parents(struct graph_v1 * graph)178 graph_reorder_parents(struct graph_v1 *graph)
179 {
180 struct graph_row *row = &graph->row;
181 struct graph_row *parents = &graph->parents;
182 int i;
183
184 if (parents->size == 1)
185 return;
186
187 for (i = 0; i < parents->size; i++) {
188 struct graph_column *column = &parents->columns[i];
189 size_t match = graph_find_column_by_id(row, column->id);
190
191 if (match < graph->position && graph_column_has_commit(&row->columns[match])) {
192 //die("Reorder: %s -> %s", graph->commit->id, column->id);
193 // row->columns[match].symbol.initial = 1;
194 }
195 }
196 }
197
198 static void
graph_canvas_append_symbol(struct graph_v1 * graph,struct graph_symbol * symbol)199 graph_canvas_append_symbol(struct graph_v1 *graph, struct graph_symbol *symbol)
200 {
201 struct graph_canvas *canvas = graph->canvas;
202
203 if (realloc_graph_symbols(&canvas->symbols, canvas->size, 1))
204 canvas->symbols[canvas->size++] = *symbol;
205 }
206
207 static bool
graph_insert_parents(struct graph_v1 * graph)208 graph_insert_parents(struct graph_v1 *graph)
209 {
210 struct graph_row *row = &graph->row;
211 struct graph_row *parents = &graph->parents;
212 size_t orig_size = row->size;
213 bool branched = false;
214 bool merge = parents->size > 1;
215 int pos;
216
217 assert(!graph_needs_expansion(graph));
218
219 for (pos = 0; pos < graph->position; pos++) {
220 struct graph_column *column = &row->columns[pos];
221 struct graph_symbol symbol = column->symbol;
222
223 if (graph_column_has_commit(column)) {
224 size_t match = graph_find_column_by_id(parents, column->id);
225
226 if (match < parents->size) {
227 column->symbol.initial = 1;
228 }
229
230 symbol.branch = 1;
231 }
232 symbol.vbranch = !!branched;
233 if (!strcmp(column->id, graph->id)) {
234 branched = true;
235 column->id[0] = 0;
236 }
237
238 graph_canvas_append_symbol(graph, &symbol);
239 }
240
241 for (; pos < graph->position + parents->size; pos++) {
242 struct graph_column *old = &row->columns[pos];
243 struct graph_column *new = &parents->columns[pos - graph->position];
244 struct graph_symbol symbol = old->symbol;
245
246 symbol.merge = !!merge;
247
248 if (pos == graph->position) {
249 symbol.commit = 1;
250 if (new->symbol.boundary) {
251 symbol.boundary = 1;
252 } else if (!graph_column_has_commit(new)) {
253 symbol.initial = 1;
254 }
255
256 } else if (!strcmp(old->id, new->id) && orig_size == row->size) {
257 symbol.vbranch = 1;
258 symbol.branch = 1;
259 //symbol.merge = 1;
260
261 } else if (parents->size > 1) {
262 symbol.merge = 1;
263 symbol.vbranch = !(pos == graph->position + parents->size - 1);
264
265 } else if (graph_column_has_commit(old)) {
266 symbol.branch = 1;
267 }
268
269 graph_canvas_append_symbol(graph, &symbol);
270 if (!graph_column_has_commit(old))
271 new->symbol.color = get_free_graph_color(graph);
272 *old = *new;
273 }
274
275 for (; pos < row->size; pos++) {
276 bool too = !strcmp(row->columns[row->size - 1].id, graph->id);
277 struct graph_symbol symbol = row->columns[pos].symbol;
278
279 symbol.vbranch = !!too;
280 if (row->columns[pos].id[0]) {
281 symbol.branch = 1;
282 if (!strcmp(row->columns[pos].id, graph->id)) {
283 symbol.branched = 1;
284 if (too && pos != row->size - 1) {
285 symbol.vbranch = 1;
286 } else {
287 symbol.vbranch = 0;
288 }
289 row->columns[pos].id[0] = 0;
290 }
291 }
292 graph_canvas_append_symbol(graph, &symbol);
293 }
294
295 graph->parents.size = graph->expanded = graph->position = 0;
296
297 return true;
298 }
299
300 static bool
graph_render_parents(struct graph * graph_,struct graph_canvas * canvas)301 graph_render_parents(struct graph *graph_, struct graph_canvas *canvas)
302 {
303 struct graph_v1 *graph = graph_->private;
304
305 if (!graph_expand(graph))
306 return false;
307 graph_reorder_parents(graph);
308 graph_insert_parents(graph);
309 if (!graph_collapse(graph))
310 return false;
311
312 return true;
313 }
314
315 static bool
graph_is_merge(struct graph_canvas * canvas)316 graph_is_merge(struct graph_canvas *canvas)
317 {
318 return !!canvas->symbols->merge;
319 }
320
321 static bool
graph_add_commit(struct graph * graph_,struct graph_canvas * canvas,const char * id,const char * parents,bool is_boundary)322 graph_add_commit(struct graph *graph_, struct graph_canvas *canvas,
323 const char *id, const char *parents, bool is_boundary)
324 {
325 struct graph_v1 *graph = graph_->private;
326 int has_parents = 0;
327
328 graph->position = graph_find_column_by_id(&graph->row, id);
329 graph->id = id;
330 graph->canvas = canvas;
331 graph->is_boundary = is_boundary;
332 graph->has_parents = false;
333
334 while ((parents = strchr(parents, ' '))) {
335 parents++;
336 if (!graph_add_parent(graph_, parents))
337 return false;
338 has_parents++;
339 }
340
341 if (graph->parents.size == 0 &&
342 !graph_add_parent(graph_, ""))
343 return false;
344
345 graph->has_parents = has_parents > 0;
346
347 return true;
348 }
349
350 static const char *
graph_symbol_to_utf8(const struct graph_symbol * symbol)351 graph_symbol_to_utf8(const struct graph_symbol *symbol)
352 {
353 if (symbol->commit) {
354 if (symbol->boundary)
355 return " ◯";
356 else if (symbol->initial)
357 return " ◎";
358 else if (symbol->merge)
359 return " ●";
360 return " ∙";
361 }
362
363 if (symbol->merge) {
364 if (symbol->branch) {
365 return "━┪";
366 }
367 if (symbol->vbranch)
368 return "━┯";
369 return "━┑";
370 }
371
372 if (symbol->branch) {
373 if (symbol->branched) {
374 if (symbol->vbranch)
375 return "─┴";
376 return "─┘";
377 }
378 if (symbol->vbranch)
379 return "─│";
380 return " │";
381 }
382
383 if (symbol->vbranch)
384 return "──";
385
386 return " ";
387 }
388
389 static const chtype *
graph_symbol_to_chtype(const struct graph_symbol * symbol)390 graph_symbol_to_chtype(const struct graph_symbol *symbol)
391 {
392 static chtype graphics[2];
393
394 if (symbol->commit) {
395 graphics[0] = ' ';
396 if (symbol->boundary)
397 graphics[1] = 'o';
398 else if (symbol->initial)
399 graphics[1] = 'I';
400 else if (symbol->merge)
401 graphics[1] = 'M';
402 else
403 graphics[1] = 'o'; //ACS_DIAMOND; //'*';
404 return graphics;
405 }
406
407 if (symbol->merge) {
408 graphics[0] = ACS_HLINE;
409 if (symbol->branch)
410 graphics[1] = ACS_RTEE;
411 else
412 graphics[1] = ACS_URCORNER;
413 return graphics;
414 }
415
416 if (symbol->branch) {
417 graphics[0] = ACS_HLINE;
418 if (symbol->branched) {
419 if (symbol->vbranch)
420 graphics[1] = ACS_BTEE;
421 else
422 graphics[1] = ACS_LRCORNER;
423 return graphics;
424 }
425
426 if (!symbol->vbranch)
427 graphics[0] = ' ';
428 graphics[1] = ACS_VLINE;
429 return graphics;
430 }
431
432 if (symbol->vbranch) {
433 graphics[0] = graphics[1] = ACS_HLINE;
434 } else
435 graphics[0] = graphics[1] = ' ';
436
437 return graphics;
438 }
439
440 static const char *
graph_symbol_to_ascii(const struct graph_symbol * symbol)441 graph_symbol_to_ascii(const struct graph_symbol *symbol)
442 {
443 if (symbol->commit) {
444 if (symbol->boundary)
445 return " o";
446 else if (symbol->initial)
447 return " I";
448 else if (symbol->merge)
449 return " M";
450 return " *";
451 }
452
453 if (symbol->merge) {
454 if (symbol->branch)
455 return "-+";
456 return "-.";
457 }
458
459 if (symbol->branch) {
460 if (symbol->branched) {
461 if (symbol->vbranch)
462 return "-+";
463 return "-'";
464 }
465 if (symbol->vbranch)
466 return "-|";
467 return " |";
468 }
469
470 if (symbol->vbranch)
471 return "--";
472
473 return " ";
474 }
475
476 static void
graph_foreach_symbol(const struct graph * graph,const struct graph_canvas * canvas,graph_symbol_iterator_fn fn,void * data)477 graph_foreach_symbol(const struct graph *graph, const struct graph_canvas *canvas, graph_symbol_iterator_fn fn, void *data)
478 {
479 int i;
480
481 for (i = 0; i < canvas->size; i++) {
482 struct graph_symbol *symbol = &canvas->symbols[i];
483 int color_id = symbol->commit ? GRAPH_COMMIT_COLOR : symbol->color;
484
485 if (fn(data, graph, symbol, color_id, i == 0))
486 break;
487 }
488 }
489
490 struct graph *
init_graph_v1(void)491 init_graph_v1(void)
492 {
493 struct graph_v1 *graph = calloc(1, sizeof(*graph));
494 struct graph *api = &graph->api;
495
496 api->private = graph;
497 api->done = done_graph;
498 api->done_rendering = done_graph_rendering;
499 api->add_commit = graph_add_commit;
500 api->add_parent = graph_add_parent;
501 api->render_parents = graph_render_parents;
502 api->is_merge = graph_is_merge;
503 api->foreach_symbol = graph_foreach_symbol;
504 api->symbol_to_ascii = graph_symbol_to_ascii;
505 api->symbol_to_utf8 = graph_symbol_to_utf8;
506 api->symbol_to_chtype = graph_symbol_to_chtype;
507
508 return api;
509 }
510
511 /* vim: set ts=8 sw=8 noexpandtab: */
512