Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

411 lines (341 sloc) 8.901 kb
/* Copyright (c) 2006-2010 Jonas Fonseca <fonseca@diku.dk>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2 of
* the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*/
#include "tig.h"
#include "graph.h"
DEFINE_ALLOCATOR(realloc_graph_columns, struct graph_column, 32)
DEFINE_ALLOCATOR(realloc_graph_symbols, struct graph_symbol, 1)
static size_t get_free_graph_color(struct graph *graph)
{
size_t i, free_color;
for (free_color = i = 0; i < ARRAY_SIZE(graph->colors); i++) {
if (graph->colors[i] < graph->colors[free_color])
free_color = i;
}
graph->colors[free_color]++;
return free_color;
}
void
done_graph(struct graph *graph)
{
free(graph->row.columns);
free(graph->parents.columns);
memset(graph, 0, sizeof(*graph));
}
#define graph_column_has_commit(col) ((col)->id[0])
static size_t
graph_find_column_by_id(struct graph_row *row, const char *id)
{
size_t free_column = row->size;
size_t i;
for (i = 0; i < row->size; i++) {
if (!graph_column_has_commit(&row->columns[i]))
free_column = i;
else if (!strcmp(row->columns[i].id, id))
return i;
}
return free_column;
}
static struct graph_column *
graph_insert_column(struct graph *graph, struct graph_row *row, size_t pos, const char *id)
{
struct graph_column *column;
if (!realloc_graph_columns(&row->columns, row->size, 1))
return NULL;
column = &row->columns[pos];
if (pos < row->size) {
memmove(column + 1, column, sizeof(*column) * (row->size - pos));
}
row->size++;
memset(column, 0, sizeof(*column));
string_copy_rev(column->id, id);
column->symbol.boundary = !!graph->is_boundary;
return column;
}
struct graph_column *
graph_add_parent(struct graph *graph, const char *parent)
{
return graph_insert_column(graph, &graph->parents, graph->parents.size, parent);
}
static bool
graph_needs_expansion(struct graph *graph)
{
if (graph->position + graph->parents.size > graph->row.size)
return TRUE;
return graph->parents.size > 1
&& graph->position < 0
&& graph->expanded < graph->parents.size;
}
static bool
graph_expand(struct graph *graph)
{
while (graph_needs_expansion(graph)) {
if (!graph_insert_column(graph, &graph->row, graph->position + graph->expanded, ""))
return FALSE;
graph->expanded++;
}
return TRUE;
}
static bool
graph_needs_collapsing(struct graph *graph)
{
return graph->row.size > 1
&& !graph_column_has_commit(&graph->row.columns[graph->row.size - 1]);
}
static bool
graph_collapse(struct graph *graph)
{
while (graph_needs_collapsing(graph)) {
graph->row.size--;
}
return TRUE;
}
static void
graph_reorder_parents(struct graph *graph)
{
struct graph_row *row = &graph->row;
struct graph_row *parents = &graph->parents;
int i;
if (parents->size == 1)
return;
for (i = 0; i < parents->size; i++) {
struct graph_column *column = &parents->columns[i];
size_t match = graph_find_column_by_id(row, column->id);
if (match < graph->position && graph_column_has_commit(&row->columns[match])) {
//die("Reorder: %s -> %s", graph->commit->id, column->id);
// row->columns[match].symbol.initial = 1;
}
}
}
static void
graph_canvas_append_symbol(struct graph *graph, struct graph_symbol *symbol)
{
struct graph_canvas *canvas = graph->canvas;
if (realloc_graph_symbols(&canvas->symbols, canvas->size, 1))
canvas->symbols[canvas->size++] = *symbol;
}
static bool
graph_insert_parents(struct graph *graph)
{
struct graph_row *row = &graph->row;
struct graph_row *parents = &graph->parents;
size_t orig_size = row->size;
bool branched = FALSE;
bool merge = parents->size > 1;
int pos;
assert(!graph_needs_expansion(graph));
for (pos = 0; pos < graph->position; pos++) {
struct graph_column *column = &row->columns[pos];
struct graph_symbol symbol = column->symbol;
if (graph_column_has_commit(column)) {
size_t match = graph_find_column_by_id(parents, column->id);
if (match < parents->size) {
column->symbol.initial = 1;
}
symbol.branch = 1;
}
symbol.vbranch = !!branched;
if (!strcmp(column->id, graph->id)) {
branched = TRUE;
column->id[0] = 0;
}
graph_canvas_append_symbol(graph, &symbol);
}
for (; pos < graph->position + parents->size; pos++) {
struct graph_column *old = &row->columns[pos];
struct graph_column *new = &parents->columns[pos - graph->position];
struct graph_symbol symbol = old->symbol;
symbol.merge = !!merge;
if (pos == graph->position) {
symbol.commit = 1;
/*
if (new->symbol->boundary) {
symbol.boundary = 1;
} else*/
if (!graph_column_has_commit(new)) {
symbol.initial = 1;
}
} else if (!strcmp(old->id, new->id) && orig_size == row->size) {
symbol.vbranch = 1;
symbol.branch = 1;
//symbol.merge = 1;
} else if (parents->size > 1) {
symbol.merge = 1;
symbol.vbranch = !(pos == graph->position + parents->size - 1);
} else if (graph_column_has_commit(old)) {
symbol.branch = 1;
}
graph_canvas_append_symbol(graph, &symbol);
if (!graph_column_has_commit(old))
new->symbol.color = get_free_graph_color(graph);
*old = *new;
}
for (; pos < row->size; pos++) {
bool too = !strcmp(row->columns[row->size - 1].id, graph->id);
struct graph_symbol symbol = row->columns[pos].symbol;
symbol.vbranch = !!too;
if (row->columns[pos].id[0]) {
symbol.branch = 1;
if (!strcmp(row->columns[pos].id, graph->id)) {
symbol.branched = 1;
if (too && pos != row->size - 1) {
symbol.vbranch = 1;
} else {
symbol.vbranch = 0;
}
row->columns[pos].id[0] = 0;
}
}
graph_canvas_append_symbol(graph, &symbol);
}
graph->parents.size = graph->expanded = graph->position = 0;
return TRUE;
}
bool
graph_render_parents(struct graph *graph)
{
if (!graph_expand(graph))
return FALSE;
graph_reorder_parents(graph);
graph_insert_parents(graph);
if (!graph_collapse(graph))
return FALSE;
return TRUE;
}
bool
graph_add_commit(struct graph *graph, struct graph_canvas *canvas,
const char *id, const char *parents, bool is_boundary)
{
graph->position = graph_find_column_by_id(&graph->row, id);
graph->id = id;
graph->canvas = canvas;
graph->is_boundary = is_boundary;
while ((parents = strchr(parents, ' '))) {
parents++;
if (!graph_add_parent(graph, parents))
return FALSE;
graph->has_parents = TRUE;
}
if (graph->parents.size == 0 &&
!graph_add_parent(graph, ""))
return FALSE;
return TRUE;
}
const char *
graph_symbol_to_utf8(struct graph_symbol *symbol)
{
if (symbol->commit) {
if (symbol->boundary)
return "";
else if (symbol->initial)
return "";
else if (symbol->merge)
return "";
return "";
}
if (symbol->merge) {
if (symbol->branch) {
return "━┪";
}
if (symbol->vbranch)
return "━┯";
return "━┑";
}
if (symbol->branch) {
if (symbol->branched) {
if (symbol->vbranch)
return "─┴";
return "─┘";
}
if (symbol->vbranch)
return "─│";
return "";
}
if (symbol->vbranch)
return "──";
return " ";
}
const chtype *
graph_symbol_to_chtype(struct graph_symbol *symbol)
{
static chtype graphics[2];
if (symbol->commit) {
graphics[0] = ' ';
if (symbol->boundary)
graphics[1] = 'o';
else if (symbol->initial)
graphics[1] = 'I';
else if (symbol->merge)
graphics[1] = 'M';
else
graphics[1] = 'o'; //ACS_DIAMOND; //'*';
return graphics;
}
if (symbol->merge) {
graphics[0] = ACS_HLINE;
if (symbol->branch)
graphics[1] = ACS_RTEE;
else
graphics[1] = ACS_URCORNER;
return graphics;
}
if (symbol->branch) {
graphics[0] = ACS_HLINE;
if (symbol->branched) {
if (symbol->vbranch)
graphics[1] = ACS_BTEE;
else
graphics[1] = ACS_LRCORNER;
return graphics;
}
if (!symbol->vbranch)
graphics[0] = ' ';
graphics[1] = ACS_VLINE;
return graphics;
}
if (symbol->vbranch) {
graphics[0] = graphics[1] = ACS_HLINE;
} else
graphics[0] = graphics[1] = ' ';
return graphics;
}
const char *
graph_symbol_to_ascii(struct graph_symbol *symbol)
{
if (symbol->commit) {
if (symbol->boundary)
return " o";
else if (symbol->initial)
return " I";
else if (symbol->merge)
return " M";
return " *";
}
if (symbol->merge) {
if (symbol->branch)
return "-+";
return "-.";
}
if (symbol->branch) {
if (symbol->branched) {
if (symbol->vbranch)
return "-+";
return "-'";
}
if (symbol->vbranch)
return "-|";
return " |";
}
if (symbol->vbranch)
return "--";
return " ";
}
Jump to Line
Something went wrong with that request. Please try again.