#include "diff.h"
#include "revision.h"
+/* Internal API */
+
+/*
+ * Output the next line for a graph.
+ * This formats the next graph line into the specified strbuf. It is not
+ * terminated with a newline.
+ *
+ * Returns 1 if the line includes the current commit, and 0 otherwise.
+ * graph_next_line() will return 1 exactly once for each time
+ * graph_update() is called.
+ */
+static int graph_next_line(struct git_graph *graph, struct strbuf *sb);
+
+/*
+ * Output a padding line in the graph.
+ * This is similar to graph_next_line(). However, it is guaranteed to
+ * never print the current commit line. Instead, if the commit line is
+ * next, it will simply output a line of vertical padding, extending the
+ * branch lines downwards, but leaving them otherwise unchanged.
+ */
+static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
+
+/*
+ * Print a strbuf to stdout. If the graph is non-NULL, all lines but the
+ * first will be prefixed with the graph output.
+ *
+ * If the strbuf ends with a newline, the output will end after this
+ * newline. A new graph line will not be printed after the final newline.
+ * If the strbuf is empty, no output will be printed.
+ *
+ * Since the first line will not include the graph ouput, the caller is
+ * responsible for printing this line's graph (perhaps via
+ * graph_show_commit() or graph_show_oneline()) before calling
+ * graph_show_strbuf().
+ */
+static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
+
/*
* TODO:
* - Add colors to the graph.
* The commit currently being processed
*/
struct commit *commit;
+ /* The rev-info used for the current traversal */
+ struct rev_info *revs;
/*
- * The number of parents this commit has.
- * (Stored so we don't have to walk over them each time we need
- * this number)
+ * The number of interesting parents that this commit has.
+ *
+ * Note that this is not the same as the actual number of parents.
+ * This count excludes parents that won't be printed in the graph
+ * output, as determined by graph_is_interesting().
*/
int num_parents;
/*
* This tells us what kind of line graph_next_line() should output.
*/
enum graph_state state;
+ /*
+ * The output state for the previous line of output.
+ * This is primarily used to determine how the first merge line
+ * should appear, based on the last line of the previous commit.
+ */
+ enum graph_state prev_state;
+ /*
+ * The index of the column that refers to this commit.
+ *
+ * If none of the incoming columns refer to this commit,
+ * this will be equal to num_columns.
+ */
+ int commit_index;
+ /*
+ * The commit_index for the previously displayed commit.
+ *
+ * This is used to determine how the first line of a merge
+ * graph output should appear, based on the last line of the
+ * previous commit.
+ */
+ int prev_commit_index;
/*
* The maximum number of columns that can be stored in the columns
* and new_columns arrays. This is also half the number of entries
int *new_mapping;
};
-struct git_graph *graph_init(void)
+struct git_graph *graph_init(struct rev_info *opt)
{
struct git_graph *graph = xmalloc(sizeof(struct git_graph));
graph->commit = NULL;
+ graph->revs = opt;
graph->num_parents = 0;
graph->expansion_row = 0;
graph->state = GRAPH_PADDING;
+ graph->prev_state = GRAPH_PADDING;
+ graph->commit_index = 0;
+ graph->prev_commit_index = 0;
graph->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 0;
return graph;
}
-void graph_release(struct git_graph *graph)
+static void graph_update_state(struct git_graph *graph, enum graph_state s)
{
- free(graph->columns);
- free(graph->new_columns);
- free(graph->mapping);
- free(graph);
+ graph->prev_state = graph->state;
+ graph->state = s;
}
static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
sizeof(int) * 2 * graph->column_capacity);
}
+/*
+ * Returns 1 if the commit will be printed in the graph output,
+ * and 0 otherwise.
+ */
+static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
+{
+ /*
+ * If revs->boundary is set, commits whose children have
+ * been shown are always interesting, even if they have the
+ * UNINTERESTING or TREESAME flags set.
+ */
+ if (graph->revs && graph->revs->boundary) {
+ if (commit->object.flags & CHILD_SHOWN)
+ return 1;
+ }
+
+ /*
+ * Uninteresting and pruned commits won't be printed
+ */
+ return (commit->object.flags & (UNINTERESTING | TREESAME)) ? 0 : 1;
+}
+
+static struct commit_list *next_interesting_parent(struct git_graph *graph,
+ struct commit_list *orig)
+{
+ struct commit_list *list;
+
+ /*
+ * If revs->first_parent_only is set, only the first
+ * parent is interesting. None of the others are.
+ */
+ if (graph->revs->first_parent_only)
+ return NULL;
+
+ /*
+ * Return the next interesting commit after orig
+ */
+ for (list = orig->next; list; list = list->next) {
+ if (graph_is_interesting(graph, list->item))
+ return list;
+ }
+
+ return NULL;
+}
+
+static struct commit_list *first_interesting_parent(struct git_graph *graph)
+{
+ struct commit_list *parents = graph->commit->parents;
+
+ /*
+ * If this commit has no parents, ignore it
+ */
+ if (!parents)
+ return NULL;
+
+ /*
+ * If the first parent is interesting, return it
+ */
+ if (graph_is_interesting(graph, parents->item))
+ return parents;
+
+ /*
+ * Otherwise, call next_interesting_parent() to get
+ * the next interesting parent
+ */
+ return next_interesting_parent(graph, parents);
+}
+
static void graph_insert_into_new_columns(struct git_graph *graph,
struct commit *commit,
int *mapping_index)
{
int i;
- /*
- * Ignore uinteresting and pruned commits
- */
- if (commit->object.flags & (UNINTERESTING | TREESAME))
- return;
-
/*
* If the commit is already in the new_columns list, we don't need to
* add it. Just update the mapping correctly.
int max_cols = graph->num_columns + graph->num_parents;
/*
- * Even if the current commit has no parents, it still takes up a
- * column for itself.
+ * Even if the current commit has no parents to be printed, it
+ * still takes up a column for itself.
*/
if (graph->num_parents < 1)
max_cols++;
}
if (col_commit == graph->commit) {
+ int old_mapping_idx = mapping_idx;
seen_this = 1;
- for (parent = graph->commit->parents;
+ graph->commit_index = i;
+ for (parent = first_interesting_parent(graph);
parent;
- parent = parent->next) {
+ parent = next_interesting_parent(graph, parent)) {
graph_insert_into_new_columns(graph,
parent->item,
&mapping_idx);
}
+ /*
+ * We always need to increment mapping_idx by at
+ * least 2, even if it has no interesting parents.
+ * The current commit always takes up at least 2
+ * spaces.
+ */
+ if (mapping_idx == old_mapping_idx)
+ mapping_idx += 2;
} else {
graph_insert_into_new_columns(graph, col_commit,
&mapping_idx);
graph->commit = commit;
/*
- * Count how many parents this commit has
+ * Count how many interesting parents this commit has
*/
graph->num_parents = 0;
- for (parent = commit->parents; parent; parent = parent->next)
+ for (parent = first_interesting_parent(graph);
+ parent;
+ parent = next_interesting_parent(graph, parent))
+ {
graph->num_parents++;
+ }
+
+ /*
+ * Store the old commit_index in prev_commit_index.
+ * graph_update_columns() will update graph->commit_index for this
+ * commit.
+ */
+ graph->prev_commit_index = graph->commit_index;
/*
* Call graph_update_columns() to update
/*
* Update graph->state.
+ * Note that we don't call graph_update_state() here, since
+ * we don't want to update graph->prev_state. No line for
+ * graph->state was ever printed.
*
* If the previous commit didn't get to the GRAPH_PADDING state,
* it never finished its output. Goto GRAPH_SKIP, to print out
* a line to indicate that portion of the graph is missing.
*
- * Otherwise, if there are 3 or more parents, we need to print
- * extra rows before the commit, to expand the branch lines around
- * it and make room for it.
+ * If there are 3 or more parents, we may need to print extra rows
+ * before the commit, to expand the branch lines around it and make
+ * room for it. We need to do this only if there is a branch row
+ * (or more) to the right of this commit.
*
* If there are less than 3 parents, we can immediately print the
* commit line.
*/
if (graph->state != GRAPH_PADDING)
graph->state = GRAPH_SKIP;
- else if (graph->num_parents >= 3)
+ else if (graph->num_parents >= 3 &&
+ graph->commit_index < (graph->num_columns - 1))
graph->state = GRAPH_PRE_COMMIT;
else
graph->state = GRAPH_COMMIT;
strbuf_addstr(sb, "...");
graph_pad_horizontally(graph, sb);
- if (graph->num_parents >= 3)
- graph->state = GRAPH_PRE_COMMIT;
+ if (graph->num_parents >= 3 &&
+ graph->commit_index < (graph->num_columns - 1))
+ graph_update_state(graph, GRAPH_PRE_COMMIT);
else
- graph->state = GRAPH_COMMIT;
+ graph_update_state(graph, GRAPH_COMMIT);
}
static void graph_output_pre_commit_line(struct git_graph *graph,
if (col->commit == graph->commit) {
seen_this = 1;
strbuf_addf(sb, "| %*s", graph->expansion_row, "");
- } else if (seen_this) {
+ } else if (seen_this && (graph->expansion_row == 0)) {
+ /*
+ * This is the first line of the pre-commit output.
+ * If the previous commit was a merge commit and
+ * ended in the GRAPH_POST_MERGE state, all branch
+ * lines after graph->prev_commit_index were
+ * printed as "\" on the previous line. Continue
+ * to print them as "\" on this line. Otherwise,
+ * print the branch lines as "|".
+ */
+ if (graph->prev_state == GRAPH_POST_MERGE &&
+ graph->prev_commit_index < i)
+ strbuf_addstr(sb, "\\ ");
+ else
+ strbuf_addstr(sb, "| ");
+ } else if (seen_this && (graph->expansion_row > 0)) {
strbuf_addstr(sb, "\\ ");
} else {
strbuf_addstr(sb, "| ");
*/
graph->expansion_row++;
if (graph->expansion_row >= num_expansion_rows)
- graph->state = GRAPH_COMMIT;
+ graph_update_state(graph, GRAPH_COMMIT);
+}
+
+static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
+{
+ /*
+ * For boundary commits, print 'o'
+ * (We should only see boundary commits when revs->boundary is set.)
+ */
+ if (graph->commit->object.flags & BOUNDARY) {
+ assert(graph->revs->boundary);
+ strbuf_addch(sb, 'o');
+ return;
+ }
+
+ /*
+ * If revs->left_right is set, print '<' for commits that
+ * come from the left side, and '>' for commits from the right
+ * side.
+ */
+ if (graph->revs && graph->revs->left_right) {
+ if (graph->commit->object.flags & SYMMETRIC_LEFT)
+ strbuf_addch(sb, '<');
+ else
+ strbuf_addch(sb, '>');
+ return;
+ }
+
+ /*
+ * Print '*' in all other cases
+ */
+ strbuf_addch(sb, '*');
}
-void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
{
int seen_this = 0;
int i, j;
if (col_commit == graph->commit) {
seen_this = 1;
- if (graph->num_parents > 1)
- strbuf_addch(sb, 'M');
- else
- strbuf_addch(sb, '*');
+ graph_output_commit_char(graph, sb);
- if (graph->num_parents < 2)
+ if (graph->num_parents < 3)
strbuf_addch(sb, ' ');
- else if (graph->num_parents == 2)
- strbuf_addstr(sb, " ");
else {
int num_dashes =
((graph->num_parents - 2) * 2) - 1;
strbuf_addch(sb, '-');
strbuf_addstr(sb, ". ");
}
- } else if (seen_this && (graph->num_parents > 1)) {
+ } else if (seen_this && (graph->num_parents > 2)) {
strbuf_addstr(sb, "\\ ");
+ } else if (seen_this && (graph->num_parents == 2)) {
+ /*
+ * This is a 2-way merge commit.
+ * There is no GRAPH_PRE_COMMIT stage for 2-way
+ * merges, so this is the first line of output
+ * for this commit. Check to see what the previous
+ * line of output was.
+ *
+ * If it was GRAPH_POST_MERGE, the branch line
+ * coming into this commit may have been '\',
+ * and not '|' or '/'. If so, output the branch
+ * line as '\' on this line, instead of '|'. This
+ * makes the output look nicer.
+ */
+ if (graph->prev_state == GRAPH_POST_MERGE &&
+ graph->prev_commit_index < i)
+ strbuf_addstr(sb, "\\ ");
+ else
+ strbuf_addstr(sb, "| ");
} else {
strbuf_addstr(sb, "| ");
}
* Update graph->state
*/
if (graph->num_parents > 1)
- graph->state = GRAPH_POST_MERGE;
+ graph_update_state(graph, GRAPH_POST_MERGE);
else if (graph_is_mapping_correct(graph))
- graph->state = GRAPH_PADDING;
+ graph_update_state(graph, GRAPH_PADDING);
else
- graph->state = GRAPH_COLLAPSING;
+ graph_update_state(graph, GRAPH_COLLAPSING);
}
-void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
{
int seen_this = 0;
int i, j;
strbuf_addch(sb, '|');
for (j = 0; j < graph->num_parents - 1; j++)
strbuf_addstr(sb, "\\ ");
- if (graph->num_parents == 2)
- strbuf_addch(sb, ' ');
- } else if (seen_this && (graph->num_parents > 2)) {
+ } else if (seen_this) {
strbuf_addstr(sb, "\\ ");
} else {
strbuf_addstr(sb, "| ");
* Update graph->state
*/
if (graph_is_mapping_correct(graph))
- graph->state = GRAPH_PADDING;
+ graph_update_state(graph, GRAPH_PADDING);
else
- graph->state = GRAPH_COLLAPSING;
+ graph_update_state(graph, GRAPH_COLLAPSING);
}
-void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
{
int i;
int *tmp_mapping;
* Otherwise, we need to collapse some branch lines together.
*/
if (graph_is_mapping_correct(graph))
- graph->state = GRAPH_PADDING;
+ graph_update_state(graph, GRAPH_PADDING);
}
-int graph_next_line(struct git_graph *graph, struct strbuf *sb)
+static int graph_next_line(struct git_graph *graph, struct strbuf *sb)
{
switch (graph->state) {
case GRAPH_PADDING:
return 0;
}
-void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
{
int i, j;
}
graph_pad_horizontally(graph, sb);
+
+ /*
+ * Update graph->prev_state since we have output a padding line
+ */
+ graph->prev_state = GRAPH_PADDING;
}
int graph_is_commit_finished(struct git_graph const *graph)
}
-void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
+static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
{
char *p;