🌐 AI搜索 & 代理 主页
Google Git
Sign in
chromium / external / github.com / git / git / refs/tags/v2.52.0-rc1 / . / graph.c
blob: 26f6fbf000aef5ef1fa46aeed5851a8fbb2d8fe3 [file] [log] [blame]
Patrick Steinhardt41f43b82024-12-06 10:27:19[diff] [blame]1#define DISABLE_SIGN_COMPARE_WARNINGS
Patrick Steinhardt219de842024-08-13 09:14:21[diff] [blame]2
Elijah Newrenfc7bd512023-02-24 00:09:34[diff] [blame]3#include "git-compat-util.h"
4#include "gettext.h"
Brandon Williamsb2141fc2017-06-14 18:07:36[diff] [blame]5#include "config.h"
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]6#include "commit.h"
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]7#include "color.h"
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]8#include "graph.h"
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]9#include "revision.h"
Jeff Kingdbbcd442020-07-28 20:23:39[diff] [blame]10#include "strvec.h"
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]11
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]12/* Internal API */
13
14/*
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]15 * Output a padding line in the graph.
16 * This is similar to graph_next_line(). However, it is guaranteed to
17 * never print the current commit line. Instead, if the commit line is
18 * next, it will simply output a line of vertical padding, extending the
19 * branch lines downwards, but leaving them otherwise unchanged.
20 */
21static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
22
23/*
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]24 * Print a strbuf. If the graph is non-NULL, all lines but the first will be
25 * prefixed with the graph output.
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]26 *
27 * If the strbuf ends with a newline, the output will end after this
28 * newline. A new graph line will not be printed after the final newline.
29 * If the strbuf is empty, no output will be printed.
30 *
Mike Ralphson3ea3c212009-04-17 18:13:30[diff] [blame]31 * Since the first line will not include the graph output, the caller is
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]32 * responsible for printing this line's graph (perhaps via
33 * graph_show_commit() or graph_show_oneline()) before calling
34 * graph_show_strbuf().
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]35 *
36 * Note that unlike some other graph display functions, you must pass the file
37 * handle directly. It is assumed that this is the same file handle as the
38 * file specified by the graph diff options. This is necessary so that
39 * graph_show_strbuf can be called even with a NULL graph.
Heba Waly3f1480b2019-11-17 21:04:42[diff] [blame]40 * If a NULL graph is supplied, the strbuf is printed as-is.
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]41 */
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]42static void graph_show_strbuf(struct git_graph *graph,
43 FILE *file,
44 struct strbuf const *sb);
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]45
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]46/*
47 * TODO:
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]48 * - Limit the number of columns, similar to the way gitk does.
49 * If we reach more than a specified number of columns, omit
50 * sections of some columns.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]51 */
52
53struct column {
54 /*
55 * The parent commit of this column.
56 */
57 struct commit *commit;
58 /*
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]59 * The color to (optionally) print this column in. This is an
60 * index into column_colors.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]61 */
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]62 unsigned short color;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]63};
64
65enum graph_state {
66 GRAPH_PADDING,
67 GRAPH_SKIP,
68 GRAPH_PRE_COMMIT,
69 GRAPH_COMMIT,
70 GRAPH_POST_MERGE,
71 GRAPH_COLLAPSING
72};
73
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]74static void graph_show_line_prefix(const struct diff_options *diffopt)
75{
76 if (!diffopt || !diffopt->line_prefix)
77 return;
78
Jeff King2011bb42024-10-03 21:06:54[diff] [blame]79 fputs(diffopt->line_prefix, diffopt->file);
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]80}
81
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]82static const char **column_colors;
83static unsigned short column_colors_max;
84
Jeff Kingef8d7ac2020-07-28 20:24:53[diff] [blame]85static void parse_graph_colors_config(struct strvec *colors, const char *string)
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]86{
87 const char *end, *start;
88
89 start = string;
90 end = string + strlen(string);
91 while (start < end) {
92 const char *comma = strchrnul(start, ',');
93 char color[COLOR_MAXLEN];
94
95 if (!color_parse_mem(start, comma - start, color))
Jeff Kingef8d7ac2020-07-28 20:24:53[diff] [blame]96 strvec_push(colors, color);
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]97 else
Alex Henrie98538302021-06-12 18:41:44[diff] [blame]98 warning(_("ignored invalid color '%.*s' in log.graphColors"),
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]99 (int)(comma - start), start);
100 start = comma + 1;
101 }
Jeff Kingef8d7ac2020-07-28 20:24:53[diff] [blame]102 strvec_push(colors, GIT_COLOR_RESET);
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]103}
104
John Keepingac751a02013-03-04 00:03:37[diff] [blame]105void graph_set_column_colors(const char **colors, unsigned short colors_max)
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]106{
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]107 column_colors = colors;
108 column_colors_max = colors_max;
109}
110
111static const char *column_get_color_code(unsigned short color)
112{
113 return column_colors[color];
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]114}
115
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]116struct graph_line {
117 struct strbuf *buf;
118 size_t width;
119};
120
121static inline void graph_line_addch(struct graph_line *line, int c)
122{
123 strbuf_addch(line->buf, c);
124 line->width++;
125}
126
127static inline void graph_line_addchars(struct graph_line *line, int c, size_t n)
128{
129 strbuf_addchars(line->buf, c, n);
130 line->width += n;
131}
132
133static inline void graph_line_addstr(struct graph_line *line, const char *s)
134{
135 strbuf_addstr(line->buf, s);
136 line->width += strlen(s);
137}
138
139static inline void graph_line_addcolor(struct graph_line *line, unsigned short color)
140{
141 strbuf_addstr(line->buf, column_get_color_code(color));
142}
143
144static void graph_line_write_column(struct graph_line *line, const struct column *c,
145 char col_char)
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]146{
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]147 if (c->color < column_colors_max)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]148 graph_line_addcolor(line, c->color);
149 graph_line_addch(line, col_char);
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]150 if (c->color < column_colors_max)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]151 graph_line_addcolor(line, column_colors_max);
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]152}
153
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]154struct git_graph {
155 /*
156 * The commit currently being processed
157 */
158 struct commit *commit;
Adam Simpkins7528f272008-05-25 07:07:21[diff] [blame]159 /* The rev-info used for the current traversal */
160 struct rev_info *revs;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]161 /*
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]162 * The number of interesting parents that this commit has.
163 *
164 * Note that this is not the same as the actual number of parents.
165 * This count excludes parents that won't be printed in the graph
166 * output, as determined by graph_is_interesting().
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]167 */
168 int num_parents;
169 /*
Adam Simpkins0724cb82008-05-05 07:57:03[diff] [blame]170 * The width of the graph output for this commit.
171 * All rows for this commit are padded to this width, so that
172 * messages printed after the graph output are aligned.
173 */
174 int width;
175 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]176 * The next expansion row to print
177 * when state is GRAPH_PRE_COMMIT
178 */
179 int expansion_row;
180 /*
181 * The current output state.
182 * This tells us what kind of line graph_next_line() should output.
183 */
184 enum graph_state state;
185 /*
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]186 * The output state for the previous line of output.
187 * This is primarily used to determine how the first merge line
188 * should appear, based on the last line of the previous commit.
189 */
190 enum graph_state prev_state;
191 /*
192 * The index of the column that refers to this commit.
193 *
194 * If none of the incoming columns refer to this commit,
195 * this will be equal to num_columns.
196 */
197 int commit_index;
198 /*
199 * The commit_index for the previously displayed commit.
200 *
201 * This is used to determine how the first line of a merge
202 * graph output should appear, based on the last line of the
203 * previous commit.
204 */
205 int prev_commit_index;
206 /*
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]207 * Which layout variant to use to display merge commits. If the
208 * commit's first parent is known to be in a column to the left of the
209 * merge, then this value is 0 and we use the layout on the left.
210 * Otherwise, the value is 1 and the layout on the right is used. This
211 * field tells us how many columns the first parent occupies.
212 *
213 * 0) 1)
214 *
215 * | | | *-. | | *---.
216 * | |_|/|\ \ | | |\ \ \
217 * |/| | | | | | | | | | *
218 */
219 int merge_layout;
220 /*
James Cogland62893e2019-10-15 23:47:55[diff] [blame]221 * The number of columns added to the graph by the current commit. For
ryenus571fb962019-12-15 15:12:24[diff] [blame]222 * 2-way and octopus merges, this is usually one less than the
James Cogland62893e2019-10-15 23:47:55[diff] [blame]223 * number of parents:
224 *
225 * | | | | | \
226 * | * | | *---. \
227 * | |\ \ | |\ \ \ \
228 * | | | | | | | | | |
229 *
230 * num_parents: 2 num_parents: 4
231 * edges_added: 1 edges_added: 3
232 *
233 * For left-skewed merges, the first parent fuses with its neighbor and
234 * so one less column is added:
235 *
236 * | | | | | \
237 * | * | | *-. \
238 * |/| | |/|\ \ \
239 * | | | | | | | |
240 *
241 * num_parents: 2 num_parents: 4
242 * edges_added: 0 edges_added: 2
243 *
244 * This number determines how edges to the right of the merge are
245 * displayed in commit and post-merge lines; if no columns have been
246 * added then a vertical line should be used where a right-tracking
247 * line would otherwise be used.
248 *
249 * | * \ | * |
250 * | |\ \ |/| |
251 * | | * \ | * |
252 */
253 int edges_added;
254 /*
255 * The number of columns added by the previous commit, which is used to
256 * smooth edges appearing to the right of a commit in a commit line
257 * following a post-merge line.
258 */
259 int prev_edges_added;
260 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]261 * The maximum number of columns that can be stored in the columns
262 * and new_columns arrays. This is also half the number of entries
James Coglan01952852019-10-15 23:47:56[diff] [blame]263 * that can be stored in the mapping and old_mapping arrays.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]264 */
265 int column_capacity;
266 /*
267 * The number of columns (also called "branch lines" in some places)
268 */
269 int num_columns;
270 /*
271 * The number of columns in the new_columns array
272 */
273 int num_new_columns;
274 /*
275 * The number of entries in the mapping array
276 */
277 int mapping_size;
278 /*
279 * The column state before we output the current commit.
280 */
281 struct column *columns;
282 /*
283 * The new column state after we output the current commit.
284 * Only valid when state is GRAPH_COLLAPSING.
285 */
286 struct column *new_columns;
287 /*
288 * An array that tracks the current state of each
289 * character in the output line during state GRAPH_COLLAPSING.
290 * Each entry is -1 if this character is empty, or a non-negative
291 * integer if the character contains a branch line. The value of
292 * the integer indicates the target position for this branch line.
293 * (I.e., this array maps the current column positions to their
294 * desired positions.)
295 *
296 * The maximum capacity of this array is always
297 * sizeof(int) * 2 * column_capacity.
298 */
299 int *mapping;
300 /*
James Coglan479db182019-10-15 23:47:57[diff] [blame]301 * A copy of the contents of the mapping array from the last commit,
302 * which we use to improve the display of columns that are tracking
303 * from right to left through a commit line. We also use this to
304 * avoid allocating a fresh array when we compute the next mapping.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]305 */
James Coglan01952852019-10-15 23:47:56[diff] [blame]306 int *old_mapping;
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]307 /*
308 * The current default column color being used. This is
309 * stored as an index into the array column_colors.
310 */
311 unsigned short default_column_color;
Jeff King1164e272024-10-03 21:13:17[diff] [blame]312
313 /*
314 * Scratch buffer for generating prefixes to be used with
315 * diff_output_prefix_callback().
316 */
317 struct strbuf prefix_buf;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]318};
319
Jeff King436728f2024-10-03 21:09:24[diff] [blame]320static const char *diff_output_prefix_callback(struct diff_options *opt, void *data)
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]321{
322 struct git_graph *graph = data;
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]323
Lucian Poston5e71a842012-04-16 10:44:50[diff] [blame]324 assert(opt);
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]325
Jeff King19752d92024-10-03 21:11:31[diff] [blame]326 if (!graph)
327 return opt->line_prefix;
328
Jeff King1164e272024-10-03 21:13:17[diff] [blame]329 strbuf_reset(&graph->prefix_buf);
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]330 if (opt->line_prefix)
Jeff King1164e272024-10-03 21:13:17[diff] [blame]331 strbuf_addstr(&graph->prefix_buf, opt->line_prefix);
332 graph_padding_line(graph, &graph->prefix_buf);
333 return graph->prefix_buf.buf;
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]334}
335
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]336static const struct diff_options *default_diffopt;
337
338void graph_setup_line_prefix(struct diff_options *diffopt)
339{
340 default_diffopt = diffopt;
341
342 /* setup an output prefix callback if necessary */
343 if (diffopt && !diffopt->output_prefix)
344 diffopt->output_prefix = diff_output_prefix_callback;
345}
346
Adam Simpkins7528f272008-05-25 07:07:21[diff] [blame]347struct git_graph *graph_init(struct rev_info *opt)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]348{
349 struct git_graph *graph = xmalloc(sizeof(struct git_graph));
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]350
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]351 if (!column_colors) {
352 char *string;
Patrick Steinhardte1335a92024-12-17 06:44:00[diff] [blame]353 if (repo_config_get_string(opt->repo, "log.graphcolors", &string)) {
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]354 /* not configured -- use default */
355 graph_set_column_colors(column_colors_ansi,
356 column_colors_ansi_max);
357 } else {
Jeff Kingef8d7ac2020-07-28 20:24:53[diff] [blame]358 static struct strvec custom_colors = STRVEC_INIT;
359 strvec_clear(&custom_colors);
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]360 parse_graph_colors_config(&custom_colors, string);
361 free(string);
362 /* graph_set_column_colors takes a max-index, not a count */
Jeff Kingd70a9eb2020-07-29 00:37:20[diff] [blame]363 graph_set_column_colors(custom_colors.v,
364 custom_colors.nr - 1);
Nguyễn Thái Ngọc Duy73c727d2017-01-19 11:41:23[diff] [blame]365 }
366 }
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]367
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]368 graph->commit = NULL;
Adam Simpkins7528f272008-05-25 07:07:21[diff] [blame]369 graph->revs = opt;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]370 graph->num_parents = 0;
371 graph->expansion_row = 0;
372 graph->state = GRAPH_PADDING;
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]373 graph->prev_state = GRAPH_PADDING;
374 graph->commit_index = 0;
375 graph->prev_commit_index = 0;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]376 graph->merge_layout = 0;
James Cogland62893e2019-10-15 23:47:55[diff] [blame]377 graph->edges_added = 0;
378 graph->prev_edges_added = 0;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]379 graph->num_columns = 0;
380 graph->num_new_columns = 0;
381 graph->mapping_size = 0;
Adam Simpkins91e50b22009-08-18 21:41:12[diff] [blame]382 /*
383 * Start the column color at the maximum value, since we'll
384 * always increment it for the first commit we output.
385 * This way we start at 0 for the first commit.
386 */
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]387 graph->default_column_color = column_colors_max - 1;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]388
389 /*
390 * Allocate a reasonably large default number of columns
391 * We'll automatically grow columns later if we need more room.
392 */
393 graph->column_capacity = 30;
Jeff Kingb32fa952016-02-22 22:44:25[diff] [blame]394 ALLOC_ARRAY(graph->columns, graph->column_capacity);
395 ALLOC_ARRAY(graph->new_columns, graph->column_capacity);
396 ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity);
James Coglan01952852019-10-15 23:47:56[diff] [blame]397 ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]398
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]399 /*
400 * The diff output prefix callback, with this we can make
401 * all the diff output to align with the graph lines.
402 */
Jeff King1164e272024-10-03 21:13:17[diff] [blame]403 strbuf_init(&graph->prefix_buf, 0);
Bo Yangb5a4de92010-05-26 07:23:56[diff] [blame]404 opt->diffopt.output_prefix = diff_output_prefix_callback;
405 opt->diffopt.output_prefix_data = graph;
406
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]407 return graph;
408}
409
Alex Henriedccf6c12022-02-11 16:36:24[diff] [blame]410void graph_clear(struct git_graph *graph)
411{
412 if (!graph)
413 return;
414
415 free(graph->columns);
416 free(graph->new_columns);
417 free(graph->mapping);
418 free(graph->old_mapping);
Jeff King1164e272024-10-03 21:13:17[diff] [blame]419 strbuf_release(&graph->prefix_buf);
Alex Henriedccf6c12022-02-11 16:36:24[diff] [blame]420 free(graph);
421}
422
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]423static void graph_update_state(struct git_graph *graph, enum graph_state s)
424{
425 graph->prev_state = graph->state;
426 graph->state = s;
427}
428
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]429static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
430{
431 if (graph->column_capacity >= num_columns)
432 return;
433
434 do {
435 graph->column_capacity *= 2;
436 } while (graph->column_capacity < num_columns);
437
René Scharfe2756ca42014-09-16 18:56:57[diff] [blame]438 REALLOC_ARRAY(graph->columns, graph->column_capacity);
439 REALLOC_ARRAY(graph->new_columns, graph->column_capacity);
440 REALLOC_ARRAY(graph->mapping, graph->column_capacity * 2);
James Coglan01952852019-10-15 23:47:56[diff] [blame]441 REALLOC_ARRAY(graph->old_mapping, graph->column_capacity * 2);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]442}
443
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]444/*
445 * Returns 1 if the commit will be printed in the graph output,
446 * and 0 otherwise.
447 */
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]448static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]449{
450 /*
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]451 * If revs->boundary is set, commits whose children have
452 * been shown are always interesting, even if they have the
453 * UNINTERESTING or TREESAME flags set.
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]454 */
455 if (graph->revs && graph->revs->boundary) {
Adam Simpkins4603ec02008-05-24 23:02:05[diff] [blame]456 if (commit->object.flags & CHILD_SHOWN)
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]457 return 1;
458 }
459
460 /*
Adam Simpkinsbeb5af42009-08-19 02:34:33[diff] [blame]461 * Otherwise, use get_commit_action() to see if this commit is
462 * interesting
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]463 */
Adam Simpkinsbeb5af42009-08-19 02:34:33[diff] [blame]464 return get_commit_action(graph->revs, commit) == commit_show;
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]465}
466
Adam Simpkinsa0ebe572008-06-05 08:56:19[diff] [blame]467static struct commit_list *next_interesting_parent(struct git_graph *graph,
468 struct commit_list *orig)
469{
470 struct commit_list *list;
471
472 /*
473 * If revs->first_parent_only is set, only the first
474 * parent is interesting. None of the others are.
475 */
476 if (graph->revs->first_parent_only)
477 return NULL;
478
479 /*
480 * Return the next interesting commit after orig
481 */
482 for (list = orig->next; list; list = list->next) {
483 if (graph_is_interesting(graph, list->item))
484 return list;
485 }
486
487 return NULL;
488}
489
490static struct commit_list *first_interesting_parent(struct git_graph *graph)
491{
492 struct commit_list *parents = graph->commit->parents;
493
494 /*
495 * If this commit has no parents, ignore it
496 */
497 if (!parents)
498 return NULL;
499
500 /*
501 * If the first parent is interesting, return it
502 */
503 if (graph_is_interesting(graph, parents->item))
504 return parents;
505
506 /*
507 * Otherwise, call next_interesting_parent() to get
508 * the next interesting parent
509 */
510 return next_interesting_parent(graph, parents);
511}
512
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]513static unsigned short graph_get_current_column_color(const struct git_graph *graph)
514{
Jeff Kingdaa0c3d2011-08-18 05:04:23[diff] [blame]515 if (!want_color(graph->revs->diffopt.use_color))
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]516 return column_colors_max;
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]517 return graph->default_column_color;
518}
519
520/*
521 * Update the graph's default column color.
522 */
523static void graph_increment_column_color(struct git_graph *graph)
524{
525 graph->default_column_color = (graph->default_column_color + 1) %
Johan Herland1e3d4112010-07-13 21:23:39[diff] [blame]526 column_colors_max;
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]527}
528
529static unsigned short graph_find_commit_color(const struct git_graph *graph,
530 const struct commit *commit)
531{
532 int i;
533 for (i = 0; i < graph->num_columns; i++) {
534 if (graph->columns[i].commit == commit)
535 return graph->columns[i].color;
536 }
537 return graph_get_current_column_color(graph);
538}
539
James Coglan9157a2a2019-10-15 23:47:49[diff] [blame]540static int graph_find_new_column_by_commit(struct git_graph *graph,
541 struct commit *commit)
542{
543 int i;
544 for (i = 0; i < graph->num_new_columns; i++) {
545 if (graph->new_columns[i].commit == commit)
546 return i;
547 }
548 return -1;
549}
550
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]551static void graph_insert_into_new_columns(struct git_graph *graph,
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]552 struct commit *commit,
553 int idx)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]554{
James Coglan9157a2a2019-10-15 23:47:49[diff] [blame]555 int i = graph_find_new_column_by_commit(graph, commit);
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]556 int mapping_idx;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]557
558 /*
James Coglana551fd52019-10-15 23:47:50[diff] [blame]559 * If the commit is not already in the new_columns array, then add it
560 * and record it as being in the final column.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]561 */
James Coglana551fd52019-10-15 23:47:50[diff] [blame]562 if (i < 0) {
563 i = graph->num_new_columns++;
564 graph->new_columns[i].commit = commit;
565 graph->new_columns[i].color = graph_find_commit_color(graph, commit);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]566 }
567
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]568 if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
569 /*
570 * If this is the first parent of a merge, choose a layout for
571 * the merge line based on whether the parent appears in a
572 * column to the left of the merge
573 */
574 int dist, shift;
575
576 dist = idx - i;
577 shift = (dist > 1) ? 2 * dist - 3 : 1;
578
579 graph->merge_layout = (dist > 0) ? 0 : 1;
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]580 graph->edges_added = graph->num_parents + graph->merge_layout - 2;
581
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]582 mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
583 graph->width += 2 * graph->merge_layout;
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]584
585 } else if (graph->edges_added > 0 && i == graph->mapping[graph->width - 2]) {
586 /*
587 * If some columns have been added by a merge, but this commit
588 * was found in the last existing column, then adjust the
589 * numbers so that the two edges immediately join, i.e.:
590 *
591 * * | * |
592 * |\ \ => |\|
593 * | |/ | *
594 * | *
595 */
596 mapping_idx = graph->width - 2;
597 graph->edges_added = -1;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]598 } else {
599 mapping_idx = graph->width;
600 graph->width += 2;
601 }
602
603 graph->mapping[mapping_idx] = i;
Adam Simpkins0724cb82008-05-05 07:57:03[diff] [blame]604}
605
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]606static void graph_update_columns(struct git_graph *graph)
607{
608 struct commit_list *parent;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]609 int max_new_columns;
Adam Simpkins0724cb82008-05-05 07:57:03[diff] [blame]610 int i, seen_this, is_commit_in_columns;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]611
612 /*
613 * Swap graph->columns with graph->new_columns
614 * graph->columns contains the state for the previous commit,
615 * and new_columns now contains the state for our commit.
616 *
617 * We'll re-use the old columns array as storage to compute the new
618 * columns list for the commit after this one.
619 */
René Scharfe9e2edd62017-01-28 21:42:15[diff] [blame]620 SWAP(graph->columns, graph->new_columns);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]621 graph->num_columns = graph->num_new_columns;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]622 graph->num_new_columns = 0;
623
624 /*
625 * Now update new_columns and mapping with the information for the
626 * commit after this one.
627 *
628 * First, make sure we have enough room. At most, there will
629 * be graph->num_columns + graph->num_parents columns for the next
630 * commit.
631 */
632 max_new_columns = graph->num_columns + graph->num_parents;
633 graph_ensure_capacity(graph, max_new_columns);
634
635 /*
636 * Clear out graph->mapping
637 */
638 graph->mapping_size = 2 * max_new_columns;
639 for (i = 0; i < graph->mapping_size; i++)
640 graph->mapping[i] = -1;
641
James Coglan46ba2ab2019-10-15 23:47:51[diff] [blame]642 graph->width = 0;
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]643 graph->prev_edges_added = graph->edges_added;
644 graph->edges_added = 0;
James Coglan46ba2ab2019-10-15 23:47:51[diff] [blame]645
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]646 /*
647 * Populate graph->new_columns and graph->mapping
648 *
649 * Some of the parents of this commit may already be in
650 * graph->columns. If so, graph->new_columns should only contain a
651 * single entry for each such commit. graph->mapping should
652 * contain information about where each current branch line is
653 * supposed to end up after the collapsing is performed.
654 */
655 seen_this = 0;
Adam Simpkins0724cb82008-05-05 07:57:03[diff] [blame]656 is_commit_in_columns = 1;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]657 for (i = 0; i <= graph->num_columns; i++) {
658 struct commit *col_commit;
659 if (i == graph->num_columns) {
660 if (seen_this)
661 break;
Adam Simpkins0724cb82008-05-05 07:57:03[diff] [blame]662 is_commit_in_columns = 0;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]663 col_commit = graph->commit;
664 } else {
665 col_commit = graph->columns[i].commit;
666 }
667
668 if (col_commit == graph->commit) {
669 seen_this = 1;
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]670 graph->commit_index = i;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]671 graph->merge_layout = -1;
Adam Simpkinsa0ebe572008-06-05 08:56:19[diff] [blame]672 for (parent = first_interesting_parent(graph);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]673 parent;
Adam Simpkinsa0ebe572008-06-05 08:56:19[diff] [blame]674 parent = next_interesting_parent(graph, parent)) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]675 /*
Adam Simpkins91e50b22009-08-18 21:41:12[diff] [blame]676 * If this is a merge, or the start of a new
677 * childless column, increment the current
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]678 * color.
679 */
Adam Simpkins91e50b22009-08-18 21:41:12[diff] [blame]680 if (graph->num_parents > 1 ||
681 !is_commit_in_columns) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]682 graph_increment_column_color(graph);
Adam Simpkins91e50b22009-08-18 21:41:12[diff] [blame]683 }
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]684 graph_insert_into_new_columns(graph, parent->item, i);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]685 }
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]686 /*
James Coglan46ba2ab2019-10-15 23:47:51[diff] [blame]687 * We always need to increment graph->width by at
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]688 * least 2, even if it has no interesting parents.
689 * The current commit always takes up at least 2
690 * spaces.
691 */
James Coglan46ba2ab2019-10-15 23:47:51[diff] [blame]692 if (graph->num_parents == 0)
693 graph->width += 2;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]694 } else {
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]695 graph_insert_into_new_columns(graph, col_commit, -1);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]696 }
697 }
698
699 /*
700 * Shrink mapping_size to be the minimum necessary
701 */
702 while (graph->mapping_size > 1 &&
703 graph->mapping[graph->mapping_size - 1] < 0)
704 graph->mapping_size--;
705}
706
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]707static int graph_num_dashed_parents(struct git_graph *graph)
708{
709 return graph->num_parents + graph->merge_layout - 3;
710}
711
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]712static int graph_num_expansion_rows(struct git_graph *graph)
713{
714 /*
715 * Normally, we need two expansion rows for each dashed parent line from
716 * an octopus merge:
717 *
718 * | *
719 * | |\
720 * | | \
721 * | | \
722 * | *-. \
723 * | |\ \ \
724 *
725 * If the merge is skewed to the left, then its parents occupy one less
726 * column, and we don't need as many expansion rows to route around it;
727 * in some cases that means we don't need any expansion rows at all:
728 *
729 * | *
730 * | |\
731 * | * \
732 * |/|\ \
733 */
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]734 return graph_num_dashed_parents(graph) * 2;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]735}
736
James Coglanee7abb52019-10-15 23:47:52[diff] [blame]737static int graph_needs_pre_commit_line(struct git_graph *graph)
738{
739 return graph->num_parents >= 3 &&
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]740 graph->commit_index < (graph->num_columns - 1) &&
741 graph->expansion_row < graph_num_expansion_rows(graph);
James Coglanee7abb52019-10-15 23:47:52[diff] [blame]742}
743
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]744void graph_update(struct git_graph *graph, struct commit *commit)
745{
746 struct commit_list *parent;
747
748 /*
749 * Set the new commit
750 */
751 graph->commit = commit;
752
753 /*
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]754 * Count how many interesting parents this commit has
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]755 */
756 graph->num_parents = 0;
Adam Simpkinsa0ebe572008-06-05 08:56:19[diff] [blame]757 for (parent = first_interesting_parent(graph);
758 parent;
759 parent = next_interesting_parent(graph, parent))
760 {
761 graph->num_parents++;
Adam Simpkins37a75ab2008-05-24 02:24:11[diff] [blame]762 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]763
764 /*
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]765 * Store the old commit_index in prev_commit_index.
766 * graph_update_columns() will update graph->commit_index for this
767 * commit.
768 */
769 graph->prev_commit_index = graph->commit_index;
770
771 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]772 * Call graph_update_columns() to update
773 * columns, new_columns, and mapping.
774 */
775 graph_update_columns(graph);
776
777 graph->expansion_row = 0;
778
779 /*
780 * Update graph->state.
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]781 * Note that we don't call graph_update_state() here, since
782 * we don't want to update graph->prev_state. No line for
783 * graph->state was ever printed.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]784 *
785 * If the previous commit didn't get to the GRAPH_PADDING state,
786 * it never finished its output. Goto GRAPH_SKIP, to print out
787 * a line to indicate that portion of the graph is missing.
788 *
Adam Simpkinsf1979d62008-06-01 20:56:58[diff] [blame]789 * If there are 3 or more parents, we may need to print extra rows
790 * before the commit, to expand the branch lines around it and make
791 * room for it. We need to do this only if there is a branch row
792 * (or more) to the right of this commit.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]793 *
794 * If there are less than 3 parents, we can immediately print the
795 * commit line.
796 */
797 if (graph->state != GRAPH_PADDING)
798 graph->state = GRAPH_SKIP;
James Coglanee7abb52019-10-15 23:47:52[diff] [blame]799 else if (graph_needs_pre_commit_line(graph))
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]800 graph->state = GRAPH_PRE_COMMIT;
801 else
802 graph->state = GRAPH_COMMIT;
803}
804
805static int graph_is_mapping_correct(struct git_graph *graph)
806{
807 int i;
808
809 /*
810 * The mapping is up to date if each entry is at its target,
811 * or is 1 greater than its target.
812 * (If it is 1 greater than the target, '/' will be printed, so it
813 * will look correct on the next row.)
814 */
815 for (i = 0; i < graph->mapping_size; i++) {
816 int target = graph->mapping[i];
817 if (target < 0)
818 continue;
819 if (target == (i / 2))
820 continue;
821 return 0;
822 }
823
824 return 1;
825}
826
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]827static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]828{
829 /*
830 * Add additional spaces to the end of the strbuf, so that all
831 * lines for a particular commit have the same width.
832 *
833 * This way, fields printed to the right of the graph will remain
834 * aligned for the entire commit.
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]835 */
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]836 if (line->width < graph->width)
837 graph_line_addchars(line, ' ', graph->width - line->width);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]838}
839
840static void graph_output_padding_line(struct git_graph *graph,
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]841 struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]842{
843 int i;
844
845 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]846 * Output a padding row, that leaves all branch lines unchanged
847 */
848 for (i = 0; i < graph->num_new_columns; i++) {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]849 graph_line_write_column(line, &graph->new_columns[i], '|');
850 graph_line_addch(line, ' ');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]851 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]852}
853
Josef Kufner3ad87c82016-06-16 13:18:37[diff] [blame]854
855int graph_width(struct git_graph *graph)
856{
857 return graph->width;
858}
859
860
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]861static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]862{
863 /*
864 * Output an ellipsis to indicate that a portion
865 * of the graph is missing.
866 */
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]867 graph_line_addstr(line, "...");
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]868
James Coglanee7abb52019-10-15 23:47:52[diff] [blame]869 if (graph_needs_pre_commit_line(graph))
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]870 graph_update_state(graph, GRAPH_PRE_COMMIT);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]871 else
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]872 graph_update_state(graph, GRAPH_COMMIT);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]873}
874
875static void graph_output_pre_commit_line(struct git_graph *graph,
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]876 struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]877{
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]878 int i, seen_this;
879
880 /*
881 * This function formats a row that increases the space around a commit
882 * with multiple parents, to make room for it. It should only be
883 * called when there are 3 or more parents.
884 *
885 * We need 2 extra rows for every parent over 2.
886 */
887 assert(graph->num_parents >= 3);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]888
889 /*
890 * graph->expansion_row tracks the current expansion row we are on.
891 * It should be in the range [0, num_expansion_rows - 1]
892 */
893 assert(0 <= graph->expansion_row &&
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]894 graph->expansion_row < graph_num_expansion_rows(graph));
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]895
896 /*
897 * Output the row
898 */
899 seen_this = 0;
900 for (i = 0; i < graph->num_columns; i++) {
901 struct column *col = &graph->columns[i];
902 if (col->commit == graph->commit) {
903 seen_this = 1;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]904 graph_line_write_column(line, col, '|');
905 graph_line_addchars(line, ' ', graph->expansion_row);
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]906 } else if (seen_this && (graph->expansion_row == 0)) {
907 /*
908 * This is the first line of the pre-commit output.
909 * If the previous commit was a merge commit and
910 * ended in the GRAPH_POST_MERGE state, all branch
911 * lines after graph->prev_commit_index were
912 * printed as "\" on the previous line. Continue
913 * to print them as "\" on this line. Otherwise,
914 * print the branch lines as "|".
915 */
916 if (graph->prev_state == GRAPH_POST_MERGE &&
917 graph->prev_commit_index < i)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]918 graph_line_write_column(line, col, '\\');
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]919 else
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]920 graph_line_write_column(line, col, '|');
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]921 } else if (seen_this && (graph->expansion_row > 0)) {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]922 graph_line_write_column(line, col, '\\');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]923 } else {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]924 graph_line_write_column(line, col, '|');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]925 }
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]926 graph_line_addch(line, ' ');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]927 }
928
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]929 /*
930 * Increment graph->expansion_row,
931 * and move to state GRAPH_COMMIT if necessary
932 */
933 graph->expansion_row++;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]934 if (!graph_needs_pre_commit_line(graph))
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]935 graph_update_state(graph, GRAPH_COMMIT);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]936}
937
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]938static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line)
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]939{
940 /*
941 * For boundary commits, print 'o'
942 * (We should only see boundary commits when revs->boundary is set.)
943 */
944 if (graph->commit->object.flags & BOUNDARY) {
945 assert(graph->revs->boundary);
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]946 graph_line_addch(line, 'o');
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]947 return;
948 }
949
950 /*
Michael J Gruber1df2d652011-03-07 12:31:39[diff] [blame]951 * get_revision_mark() handles all other cases without assert()
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]952 */
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]953 graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
Adam Simpkins3c68d672008-05-24 23:02:04[diff] [blame]954}
955
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]956/*
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]957 * Draw the horizontal dashes of an octopus merge.
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]958 */
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]959static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]960{
961 /*
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]962 * The parents of a merge commit can be arbitrarily reordered as they
963 * are mapped onto display columns, for example this is a valid merge:
Noam Postavsky04005832018-09-02 00:07:16[diff] [blame]964 *
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]965 * | | *---.
966 * | | |\ \ \
967 * | | |/ / /
968 * | |/| | /
969 * | |_|_|/
970 * |/| | |
971 * 3 1 0 2
Noam Postavsky04005832018-09-02 00:07:16[diff] [blame]972 *
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]973 * The numbers denote which parent of the merge each visual column
974 * corresponds to; we can't assume that the parents will initially
975 * display in the order given by new_columns.
976 *
977 * To find the right color for each dash, we need to consult the
978 * mapping array, starting from the column 2 places to the right of the
979 * merge commit, and use that to find out which logical column each
980 * edge will collapse to.
981 *
982 * Commits are rendered once all edges have collapsed to their correct
983 * logcial column, so commit_index gives us the right visual offset for
984 * the merge commit.
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]985 */
Noam Postavsky04005832018-09-02 00:07:16[diff] [blame]986
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]987 int i, j;
988 struct column *col;
Noam Postavsky04005832018-09-02 00:07:16[diff] [blame]989
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]990 int dashed_parents = graph_num_dashed_parents(graph);
Noam Postavsky04005832018-09-02 00:07:16[diff] [blame]991
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]992 for (i = 0; i < dashed_parents; i++) {
993 j = graph->mapping[(graph->commit_index + i + 2) * 2];
994 col = &graph->new_columns[j];
995
996 graph_line_write_column(line, col, '-');
997 graph_line_write_column(line, col, (i == dashed_parents - 1) ? '.' : '-');
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]998 }
James Coglanbbb13e82019-10-15 23:47:59[diff] [blame]999
1000 return;
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1001}
1002
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1003static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1004{
1005 int seen_this = 0;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1006 int i;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1007
1008 /*
1009 * Output the row containing this commit
1010 * Iterate up to and including graph->num_columns,
1011 * since the current commit may not be in any of the existing
1012 * columns. (This happens when the current commit doesn't have any
1013 * children that we have already processed.)
1014 */
1015 seen_this = 0;
1016 for (i = 0; i <= graph->num_columns; i++) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1017 struct column *col = &graph->columns[i];
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1018 struct commit *col_commit;
1019 if (i == graph->num_columns) {
1020 if (seen_this)
1021 break;
1022 col_commit = graph->commit;
1023 } else {
1024 col_commit = graph->columns[i].commit;
1025 }
1026
1027 if (col_commit == graph->commit) {
1028 seen_this = 1;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1029 graph_output_commit_char(graph, line);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1030
Allan Caffeea6c1a382009-04-22 21:27:59[diff] [blame]1031 if (graph->num_parents > 2)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1032 graph_draw_octopus_merge(graph, line);
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1033 } else if (seen_this && (graph->edges_added > 1)) {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1034 graph_line_write_column(line, col, '\\');
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1035 } else if (seen_this && (graph->edges_added == 1)) {
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1036 /*
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1037 * This is either a right-skewed 2-way merge
1038 * commit, or a left-skewed 3-way merge.
1039 * There is no GRAPH_PRE_COMMIT stage for such
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1040 * merges, so this is the first line of output
1041 * for this commit. Check to see what the previous
1042 * line of output was.
1043 *
1044 * If it was GRAPH_POST_MERGE, the branch line
1045 * coming into this commit may have been '\',
1046 * and not '|' or '/'. If so, output the branch
1047 * line as '\' on this line, instead of '|'. This
1048 * makes the output look nicer.
1049 */
1050 if (graph->prev_state == GRAPH_POST_MERGE &&
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1051 graph->prev_edges_added > 0 &&
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1052 graph->prev_commit_index < i)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1053 graph_line_write_column(line, col, '\\');
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1054 else
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1055 graph_line_write_column(line, col, '|');
James Coglan479db182019-10-15 23:47:57[diff] [blame]1056 } else if (graph->prev_state == GRAPH_COLLAPSING &&
1057 graph->old_mapping[2 * i + 1] == i &&
1058 graph->mapping[2 * i] < i) {
1059 graph_line_write_column(line, col, '/');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1060 } else {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1061 graph_line_write_column(line, col, '|');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1062 }
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1063 graph_line_addch(line, ' ');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1064 }
1065
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1066 /*
1067 * Update graph->state
1068 */
1069 if (graph->num_parents > 1)
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1070 graph_update_state(graph, GRAPH_POST_MERGE);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1071 else if (graph_is_mapping_correct(graph))
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1072 graph_update_state(graph, GRAPH_PADDING);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1073 else
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1074 graph_update_state(graph, GRAPH_COLLAPSING);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1075}
1076
Đoàn Trần Công Danh9d2152d2020-04-27 14:22:36[diff] [blame]1077static const char merge_chars[] = {'/', '|', '\\'};
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1078
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1079static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1080{
1081 int seen_this = 0;
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]1082 int i, j;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1083
1084 struct commit_list *first_parent = first_interesting_parent(graph);
Derrick Stoleea1087c92020-01-07 21:27:02[diff] [blame]1085 struct column *parent_col = NULL;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1086
1087 /*
1088 * Output the post-merge row
1089 */
1090 for (i = 0; i <= graph->num_columns; i++) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1091 struct column *col = &graph->columns[i];
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1092 struct commit *col_commit;
1093 if (i == graph->num_columns) {
1094 if (seen_this)
1095 break;
1096 col_commit = graph->commit;
1097 } else {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1098 col_commit = col->commit;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1099 }
1100
1101 if (col_commit == graph->commit) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1102 /*
1103 * Since the current commit is a merge find
1104 * the columns for the parent commits in
1105 * new_columns and use those to format the
1106 * edges.
1107 */
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1108 struct commit_list *parents = first_parent;
James Coglan9157a2a2019-10-15 23:47:49[diff] [blame]1109 int par_column;
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1110 int idx = graph->merge_layout;
1111 char c;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1112 seen_this = 1;
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1113
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]1114 for (j = 0; j < graph->num_parents; j++) {
James Coglan9157a2a2019-10-15 23:47:49[diff] [blame]1115 par_column = graph_find_new_column_by_commit(graph, parents->item);
1116 assert(par_column >= 0);
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1117
1118 c = merge_chars[idx];
1119 graph_line_write_column(line, &graph->new_columns[par_column], c);
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]1120 if (idx == 2) {
1121 if (graph->edges_added > 0 || j < graph->num_parents - 1)
1122 graph_line_addch(line, ' ');
1123 } else {
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1124 idx++;
James Coglan92beecc2019-10-15 23:47:58[diff] [blame]1125 }
1126 parents = next_interesting_parent(graph, parents);
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1127 }
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1128 if (graph->edges_added == 0)
1129 graph_line_addch(line, ' ');
1130
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1131 } else if (seen_this) {
James Cogland62893e2019-10-15 23:47:55[diff] [blame]1132 if (graph->edges_added > 0)
1133 graph_line_write_column(line, col, '\\');
1134 else
1135 graph_line_write_column(line, col, '|');
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1136 graph_line_addch(line, ' ');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1137 } else {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1138 graph_line_write_column(line, col, '|');
Derrick Stoleea1087c92020-01-07 21:27:02[diff] [blame]1139 if (graph->merge_layout != 0 || i != graph->commit_index - 1) {
1140 if (parent_col)
1141 graph_line_write_column(
1142 line, parent_col, '_');
1143 else
1144 graph_line_addch(line, ' ');
1145 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1146 }
James Coglan0f0f3892019-10-15 23:47:54[diff] [blame]1147
1148 if (col_commit == first_parent->item)
Derrick Stoleea1087c92020-01-07 21:27:02[diff] [blame]1149 parent_col = col;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1150 }
1151
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1152 /*
1153 * Update graph->state
1154 */
1155 if (graph_is_mapping_correct(graph))
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1156 graph_update_state(graph, GRAPH_PADDING);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1157 else
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1158 graph_update_state(graph, GRAPH_COLLAPSING);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1159}
1160
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1161static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1162{
1163 int i;
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1164 short used_horizontal = 0;
1165 int horizontal_edge = -1;
1166 int horizontal_edge_target = -1;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1167
1168 /*
James Coglan01952852019-10-15 23:47:56[diff] [blame]1169 * Swap the mapping and old_mapping arrays
1170 */
1171 SWAP(graph->mapping, graph->old_mapping);
1172
1173 /*
1174 * Clear out the mapping array
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1175 */
1176 for (i = 0; i < graph->mapping_size; i++)
James Coglan01952852019-10-15 23:47:56[diff] [blame]1177 graph->mapping[i] = -1;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1178
1179 for (i = 0; i < graph->mapping_size; i++) {
James Coglan01952852019-10-15 23:47:56[diff] [blame]1180 int target = graph->old_mapping[i];
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1181 if (target < 0)
1182 continue;
1183
1184 /*
1185 * Since update_columns() always inserts the leftmost
1186 * column first, each branch's target location should
1187 * always be either its current location or to the left of
1188 * its current location.
1189 *
1190 * We never have to move branches to the right. This makes
1191 * the graph much more legible, since whenever branches
1192 * cross, only one is moving directions.
1193 */
1194 assert(target * 2 <= i);
1195
1196 if (target * 2 == i) {
1197 /*
1198 * This column is already in the
1199 * correct place
1200 */
James Coglan01952852019-10-15 23:47:56[diff] [blame]1201 assert(graph->mapping[i] == -1);
1202 graph->mapping[i] = target;
1203 } else if (graph->mapping[i - 1] < 0) {
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1204 /*
1205 * Nothing is to the left.
1206 * Move to the left by one
1207 */
James Coglan01952852019-10-15 23:47:56[diff] [blame]1208 graph->mapping[i - 1] = target;
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1209 /*
1210 * If there isn't already an edge moving horizontally
1211 * select this one.
1212 */
1213 if (horizontal_edge == -1) {
1214 int j;
1215 horizontal_edge = i;
1216 horizontal_edge_target = target;
1217 /*
1218 * The variable target is the index of the graph
1219 * column, and therefore target*2+3 is the
1220 * actual screen column of the first horizontal
1221 * line.
1222 */
1223 for (j = (target * 2)+3; j < (i - 2); j += 2)
James Coglan01952852019-10-15 23:47:56[diff] [blame]1224 graph->mapping[j] = target;
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1225 }
James Coglan01952852019-10-15 23:47:56[diff] [blame]1226 } else if (graph->mapping[i - 1] == target) {
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1227 /*
1228 * There is a branch line to our left
1229 * already, and it is our target. We
1230 * combine with this line, since we share
1231 * the same parent commit.
1232 *
1233 * We don't have to add anything to the
James Coglan01952852019-10-15 23:47:56[diff] [blame]1234 * output or mapping, since the
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1235 * existing branch line has already taken
1236 * care of it.
1237 */
1238 } else {
1239 /*
1240 * There is a branch line to our left,
1241 * but it isn't our target. We need to
1242 * cross over it.
1243 *
1244 * The space just to the left of this
1245 * branch should always be empty.
1246 */
James Coglan01952852019-10-15 23:47:56[diff] [blame]1247 assert(graph->mapping[i - 1] > target);
1248 assert(graph->mapping[i - 2] < 0);
James Coglan01952852019-10-15 23:47:56[diff] [blame]1249 graph->mapping[i - 2] = target;
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1250 /*
1251 * Mark this branch as the horizontal edge to
1252 * prevent any other edges from moving
1253 * horizontally.
1254 */
Derrick Stoleec958d3b2020-01-08 04:27:55[diff] [blame]1255 if (horizontal_edge == -1) {
1256 int j;
1257 horizontal_edge_target = target;
1258 horizontal_edge = i - 1;
1259
1260 for (j = (target * 2) + 3; j < (i - 2); j += 2)
1261 graph->mapping[j] = target;
1262 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1263 }
1264 }
1265
1266 /*
James Coglan479db182019-10-15 23:47:57[diff] [blame]1267 * Copy the current mapping array into old_mapping
1268 */
1269 COPY_ARRAY(graph->old_mapping, graph->mapping, graph->mapping_size);
1270
1271 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1272 * The new mapping may be 1 smaller than the old mapping
1273 */
James Coglan01952852019-10-15 23:47:56[diff] [blame]1274 if (graph->mapping[graph->mapping_size - 1] < 0)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1275 graph->mapping_size--;
1276
1277 /*
1278 * Output out a line based on the new mapping info
1279 */
1280 for (i = 0; i < graph->mapping_size; i++) {
James Coglan01952852019-10-15 23:47:56[diff] [blame]1281 int target = graph->mapping[i];
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1282 if (target < 0)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1283 graph_line_addch(line, ' ');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1284 else if (target * 2 == i)
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1285 graph_line_write_column(line, &graph->new_columns[target], '|');
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1286 else if (target == horizontal_edge_target &&
1287 i != horizontal_edge - 1) {
1288 /*
1289 * Set the mappings for all but the
1290 * first segment to -1 so that they
1291 * won't continue into the next line.
1292 */
1293 if (i != (target * 2)+3)
James Coglan01952852019-10-15 23:47:56[diff] [blame]1294 graph->mapping[i] = -1;
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1295 used_horizontal = 1;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1296 graph_line_write_column(line, &graph->new_columns[target], '_');
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1297 } else {
1298 if (used_horizontal && i < horizontal_edge)
James Coglan01952852019-10-15 23:47:56[diff] [blame]1299 graph->mapping[i] = -1;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1300 graph_line_write_column(line, &graph->new_columns[target], '/');
Allan Caffeeeaf158f2009-04-21 12:47:01[diff] [blame]1301
1302 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1303 }
1304
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1305 /*
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1306 * If graph->mapping indicates that all of the branch lines
1307 * are already in the correct positions, we are done.
1308 * Otherwise, we need to collapse some branch lines together.
1309 */
1310 if (graph_is_mapping_correct(graph))
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1311 graph_update_state(graph, GRAPH_PADDING);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1312}
1313
John Keepingac751a02013-03-04 00:03:37[diff] [blame]1314int graph_next_line(struct git_graph *graph, struct strbuf *sb)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1315{
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1316 int shown_commit_line = 0;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1317 struct graph_line line = { .buf = sb, .width = 0 };
1318
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1319 /*
1320 * We could conceivable be called with a NULL commit
1321 * if our caller has a bug, and invokes graph_next_line()
1322 * immediately after graph_init(), without first calling
1323 * graph_update(). Return without outputting anything in this
1324 * case.
1325 */
1326 if (!graph->commit)
1327 return -1;
1328
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1329 switch (graph->state) {
1330 case GRAPH_PADDING:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1331 graph_output_padding_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1332 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1333 case GRAPH_SKIP:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1334 graph_output_skip_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1335 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1336 case GRAPH_PRE_COMMIT:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1337 graph_output_pre_commit_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1338 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1339 case GRAPH_COMMIT:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1340 graph_output_commit_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1341 shown_commit_line = 1;
1342 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1343 case GRAPH_POST_MERGE:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1344 graph_output_post_merge_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1345 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1346 case GRAPH_COLLAPSING:
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1347 graph_output_collapsing_line(graph, &line);
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1348 break;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1349 }
1350
James Coglan210179a2019-10-15 23:47:48[diff] [blame]1351 graph_pad_horizontally(graph, &line);
1352 return shown_commit_line;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1353}
1354
Nanako Shiraishi064bfbd2008-09-25 09:41:08[diff] [blame]1355static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1356{
René Scharfe415792e2014-09-07 07:06:42[diff] [blame]1357 int i;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1358 struct graph_line line = { .buf = sb, .width = 0 };
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1359
1360 if (graph->state != GRAPH_COMMIT) {
1361 graph_next_line(graph, sb);
1362 return;
1363 }
1364
1365 /*
1366 * Output the row containing this commit
1367 * Iterate up to and including graph->num_columns,
1368 * since the current commit may not be in any of the existing
1369 * columns. (This happens when the current commit doesn't have any
1370 * children that we have already processed.)
1371 */
1372 for (i = 0; i < graph->num_columns; i++) {
Allan Caffee427fc5b2009-04-13 19:53:41[diff] [blame]1373 struct column *col = &graph->columns[i];
Jeff King16477932016-09-29 08:37:51[diff] [blame]1374
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1375 graph_line_write_column(&line, col, '|');
Jeff King16477932016-09-29 08:37:51[diff] [blame]1376
1377 if (col->commit == graph->commit && graph->num_parents > 2) {
1378 int len = (graph->num_parents - 2) * 2;
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1379 graph_line_addchars(&line, ' ', len);
Jeff King16477932016-09-29 08:37:51[diff] [blame]1380 } else {
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1381 graph_line_addch(&line, ' ');
Jeff King16477932016-09-29 08:37:51[diff] [blame]1382 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1383 }
1384
James Coglanfbccf252019-10-15 23:47:47[diff] [blame]1385 graph_pad_horizontally(graph, &line);
Adam Simpkins33959082008-06-01 20:56:57[diff] [blame]1386
1387 /*
1388 * Update graph->prev_state since we have output a padding line
1389 */
1390 graph->prev_state = GRAPH_PADDING;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1391}
1392
1393int graph_is_commit_finished(struct git_graph const *graph)
1394{
1395 return (graph->state == GRAPH_PADDING);
1396}
1397
1398void graph_show_commit(struct git_graph *graph)
1399{
Brandon Caseyf285a2d2008-10-09 19:12:12[diff] [blame]1400 struct strbuf msgbuf = STRBUF_INIT;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1401 int shown_commit_line = 0;
1402
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1403 graph_show_line_prefix(default_diffopt);
1404
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1405 if (!graph)
1406 return;
1407
John Keepinga48ec242013-02-07 20:15:23[diff] [blame]1408 /*
1409 * When showing a diff of a merge against each of its parents, we
1410 * are called once for each parent without graph_update having been
1411 * called. In this case, simply output a single padding line.
1412 */
1413 if (graph_is_commit_finished(graph)) {
1414 graph_show_padding(graph);
1415 shown_commit_line = 1;
1416 }
1417
Michał Kiedrowicz656197a2009-07-24 23:45:00[diff] [blame]1418 while (!shown_commit_line && !graph_is_commit_finished(graph)) {
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1419 shown_commit_line = graph_next_line(graph, &msgbuf);
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1420 fwrite(msgbuf.buf, sizeof(char), msgbuf.len,
1421 graph->revs->diffopt.file);
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1422 if (!shown_commit_line) {
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1423 putc('\n', graph->revs->diffopt.file);
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1424 graph_show_line_prefix(&graph->revs->diffopt);
1425 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1426 strbuf_setlen(&msgbuf, 0);
1427 }
1428
1429 strbuf_release(&msgbuf);
1430}
1431
1432void graph_show_oneline(struct git_graph *graph)
1433{
Brandon Caseyf285a2d2008-10-09 19:12:12[diff] [blame]1434 struct strbuf msgbuf = STRBUF_INIT;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1435
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1436 graph_show_line_prefix(default_diffopt);
1437
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1438 if (!graph)
1439 return;
1440
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1441 graph_next_line(graph, &msgbuf);
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1442 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, graph->revs->diffopt.file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1443 strbuf_release(&msgbuf);
1444}
1445
1446void graph_show_padding(struct git_graph *graph)
1447{
Brandon Caseyf285a2d2008-10-09 19:12:12[diff] [blame]1448 struct strbuf msgbuf = STRBUF_INIT;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1449
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1450 graph_show_line_prefix(default_diffopt);
1451
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1452 if (!graph)
1453 return;
1454
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1455 graph_padding_line(graph, &msgbuf);
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1456 fwrite(msgbuf.buf, sizeof(char), msgbuf.len, graph->revs->diffopt.file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1457 strbuf_release(&msgbuf);
1458}
1459
1460int graph_show_remainder(struct git_graph *graph)
1461{
Brandon Caseyf285a2d2008-10-09 19:12:12[diff] [blame]1462 struct strbuf msgbuf = STRBUF_INIT;
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1463 int shown = 0;
1464
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1465 graph_show_line_prefix(default_diffopt);
1466
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1467 if (!graph)
1468 return 0;
1469
1470 if (graph_is_commit_finished(graph))
1471 return 0;
1472
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1473 for (;;) {
1474 graph_next_line(graph, &msgbuf);
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1475 fwrite(msgbuf.buf, sizeof(char), msgbuf.len,
1476 graph->revs->diffopt.file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1477 strbuf_setlen(&msgbuf, 0);
1478 shown = 1;
1479
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1480 if (!graph_is_commit_finished(graph)) {
Johannes Schindelinc61008f2016-06-22 15:01:44[diff] [blame]1481 putc('\n', graph->revs->diffopt.file);
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1482 graph_show_line_prefix(&graph->revs->diffopt);
1483 } else {
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1484 break;
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1485 }
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1486 }
1487 strbuf_release(&msgbuf);
1488
1489 return shown;
1490}
1491
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1492static void graph_show_strbuf(struct git_graph *graph,
1493 FILE *file,
1494 struct strbuf const *sb)
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1495{
1496 char *p;
1497
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1498 /*
1499 * Print the strbuf line by line,
1500 * and display the graph info before each line but the first.
1501 */
1502 p = sb->buf;
1503 while (p) {
1504 size_t len;
1505 char *next_p = strchr(p, '\n');
1506 if (next_p) {
1507 next_p++;
1508 len = next_p - p;
1509 } else {
1510 len = (sb->buf + sb->len) - p;
1511 }
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1512 fwrite(p, sizeof(char), len, file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1513 if (next_p && *next_p != '\0')
1514 graph_show_oneline(graph);
1515 p = next_p;
1516 }
1517}
1518
1519void graph_show_commit_msg(struct git_graph *graph,
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1520 FILE *file,
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1521 struct strbuf const *sb)
1522{
1523 int newline_terminated;
1524
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1525 /*
1526 * Show the commit message
1527 */
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1528 graph_show_strbuf(graph, file, sb);
1529
1530 if (!graph)
1531 return;
1532
1533 newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1534
1535 /*
1536 * If there is more output needed for this commit, show it now
1537 */
1538 if (!graph_is_commit_finished(graph)) {
1539 /*
1540 * If sb doesn't have a terminating newline, print one now,
1541 * so we can start the remainder of the graph output on a
1542 * new line.
1543 */
1544 if (!newline_terminated)
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1545 putc('\n', file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1546
1547 graph_show_remainder(graph);
1548
1549 /*
1550 * If sb ends with a newline, our output should too.
1551 */
1552 if (newline_terminated)
Jacob Keller660e1132016-08-31 23:27:20[diff] [blame]1553 putc('\n', file);
Adam Simpkinsc12172d2008-05-04 10:36:53[diff] [blame]1554 }
1555}