THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1431 lines
37KB

  1. #include "cache.h"
  2. #include "config.h"
  3. #include "commit.h"
  4. #include "color.h"
  5. #include "graph.h"
  6. #include "revision.h"
  7. #include "argv-array.h"
  8. /* Internal API */
  9. /*
  10. * Output a padding line in the graph.
  11. * This is similar to graph_next_line(). However, it is guaranteed to
  12. * never print the current commit line. Instead, if the commit line is
  13. * next, it will simply output a line of vertical padding, extending the
  14. * branch lines downwards, but leaving them otherwise unchanged.
  15. */
  16. static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
  17. /*
  18. * Print a strbuf. If the graph is non-NULL, all lines but the first will be
  19. * prefixed with the graph output.
  20. *
  21. * If the strbuf ends with a newline, the output will end after this
  22. * newline. A new graph line will not be printed after the final newline.
  23. * If the strbuf is empty, no output will be printed.
  24. *
  25. * Since the first line will not include the graph output, the caller is
  26. * responsible for printing this line's graph (perhaps via
  27. * graph_show_commit() or graph_show_oneline()) before calling
  28. * graph_show_strbuf().
  29. *
  30. * Note that unlike some other graph display functions, you must pass the file
  31. * handle directly. It is assumed that this is the same file handle as the
  32. * file specified by the graph diff options. This is necessary so that
  33. * graph_show_strbuf can be called even with a NULL graph.
  34. */
  35. static void graph_show_strbuf(struct git_graph *graph,
  36. FILE *file,
  37. struct strbuf const *sb);
  38. /*
  39. * TODO:
  40. * - Limit the number of columns, similar to the way gitk does.
  41. * If we reach more than a specified number of columns, omit
  42. * sections of some columns.
  43. */
  44. struct column {
  45. /*
  46. * The parent commit of this column.
  47. */
  48. struct commit *commit;
  49. /*
  50. * The color to (optionally) print this column in. This is an
  51. * index into column_colors.
  52. */
  53. unsigned short color;
  54. };
  55. enum graph_state {
  56. GRAPH_PADDING,
  57. GRAPH_SKIP,
  58. GRAPH_PRE_COMMIT,
  59. GRAPH_COMMIT,
  60. GRAPH_POST_MERGE,
  61. GRAPH_COLLAPSING
  62. };
  63. static void graph_show_line_prefix(const struct diff_options *diffopt)
  64. {
  65. if (!diffopt || !diffopt->line_prefix)
  66. return;
  67. fwrite(diffopt->line_prefix,
  68. sizeof(char),
  69. diffopt->line_prefix_length,
  70. diffopt->file);
  71. }
  72. static const char **column_colors;
  73. static unsigned short column_colors_max;
  74. static void parse_graph_colors_config(struct argv_array *colors, const char *string)
  75. {
  76. const char *end, *start;
  77. start = string;
  78. end = string + strlen(string);
  79. while (start < end) {
  80. const char *comma = strchrnul(start, ',');
  81. char color[COLOR_MAXLEN];
  82. if (!color_parse_mem(start, comma - start, color))
  83. argv_array_push(colors, color);
  84. else
  85. warning(_("ignore invalid color '%.*s' in log.graphColors"),
  86. (int)(comma - start), start);
  87. start = comma + 1;
  88. }
  89. argv_array_push(colors, GIT_COLOR_RESET);
  90. }
  91. void graph_set_column_colors(const char **colors, unsigned short colors_max)
  92. {
  93. column_colors = colors;
  94. column_colors_max = colors_max;
  95. }
  96. static const char *column_get_color_code(unsigned short color)
  97. {
  98. return column_colors[color];
  99. }
  100. static void strbuf_write_column(struct strbuf *sb, const struct column *c,
  101. char col_char)
  102. {
  103. if (c->color < column_colors_max)
  104. strbuf_addstr(sb, column_get_color_code(c->color));
  105. strbuf_addch(sb, col_char);
  106. if (c->color < column_colors_max)
  107. strbuf_addstr(sb, column_get_color_code(column_colors_max));
  108. }
  109. struct git_graph {
  110. /*
  111. * The commit currently being processed
  112. */
  113. struct commit *commit;
  114. /* The rev-info used for the current traversal */
  115. struct rev_info *revs;
  116. /*
  117. * The number of interesting parents that this commit has.
  118. *
  119. * Note that this is not the same as the actual number of parents.
  120. * This count excludes parents that won't be printed in the graph
  121. * output, as determined by graph_is_interesting().
  122. */
  123. int num_parents;
  124. /*
  125. * The width of the graph output for this commit.
  126. * All rows for this commit are padded to this width, so that
  127. * messages printed after the graph output are aligned.
  128. */
  129. int width;
  130. /*
  131. * The next expansion row to print
  132. * when state is GRAPH_PRE_COMMIT
  133. */
  134. int expansion_row;
  135. /*
  136. * The current output state.
  137. * This tells us what kind of line graph_next_line() should output.
  138. */
  139. enum graph_state state;
  140. /*
  141. * The output state for the previous line of output.
  142. * This is primarily used to determine how the first merge line
  143. * should appear, based on the last line of the previous commit.
  144. */
  145. enum graph_state prev_state;
  146. /*
  147. * The index of the column that refers to this commit.
  148. *
  149. * If none of the incoming columns refer to this commit,
  150. * this will be equal to num_columns.
  151. */
  152. int commit_index;
  153. /*
  154. * The commit_index for the previously displayed commit.
  155. *
  156. * This is used to determine how the first line of a merge
  157. * graph output should appear, based on the last line of the
  158. * previous commit.
  159. */
  160. int prev_commit_index;
  161. /*
  162. * The maximum number of columns that can be stored in the columns
  163. * and new_columns arrays. This is also half the number of entries
  164. * that can be stored in the mapping and new_mapping arrays.
  165. */
  166. int column_capacity;
  167. /*
  168. * The number of columns (also called "branch lines" in some places)
  169. */
  170. int num_columns;
  171. /*
  172. * The number of columns in the new_columns array
  173. */
  174. int num_new_columns;
  175. /*
  176. * The number of entries in the mapping array
  177. */
  178. int mapping_size;
  179. /*
  180. * The column state before we output the current commit.
  181. */
  182. struct column *columns;
  183. /*
  184. * The new column state after we output the current commit.
  185. * Only valid when state is GRAPH_COLLAPSING.
  186. */
  187. struct column *new_columns;
  188. /*
  189. * An array that tracks the current state of each
  190. * character in the output line during state GRAPH_COLLAPSING.
  191. * Each entry is -1 if this character is empty, or a non-negative
  192. * integer if the character contains a branch line. The value of
  193. * the integer indicates the target position for this branch line.
  194. * (I.e., this array maps the current column positions to their
  195. * desired positions.)
  196. *
  197. * The maximum capacity of this array is always
  198. * sizeof(int) * 2 * column_capacity.
  199. */
  200. int *mapping;
  201. /*
  202. * A temporary array for computing the next mapping state
  203. * while we are outputting a mapping line. This is stored as part
  204. * of the git_graph simply so we don't have to allocate a new
  205. * temporary array each time we have to output a collapsing line.
  206. */
  207. int *new_mapping;
  208. /*
  209. * The current default column color being used. This is
  210. * stored as an index into the array column_colors.
  211. */
  212. unsigned short default_column_color;
  213. };
  214. static struct strbuf *diff_output_prefix_callback(struct diff_options *opt, void *data)
  215. {
  216. struct git_graph *graph = data;
  217. static struct strbuf msgbuf = STRBUF_INIT;
  218. assert(opt);
  219. strbuf_reset(&msgbuf);
  220. if (opt->line_prefix)
  221. strbuf_add(&msgbuf, opt->line_prefix,
  222. opt->line_prefix_length);
  223. if (graph)
  224. graph_padding_line(graph, &msgbuf);
  225. return &msgbuf;
  226. }
  227. static const struct diff_options *default_diffopt;
  228. void graph_setup_line_prefix(struct diff_options *diffopt)
  229. {
  230. default_diffopt = diffopt;
  231. /* setup an output prefix callback if necessary */
  232. if (diffopt && !diffopt->output_prefix)
  233. diffopt->output_prefix = diff_output_prefix_callback;
  234. }
  235. struct git_graph *graph_init(struct rev_info *opt)
  236. {
  237. struct git_graph *graph = xmalloc(sizeof(struct git_graph));
  238. if (!column_colors) {
  239. char *string;
  240. if (git_config_get_string("log.graphcolors", &string)) {
  241. /* not configured -- use default */
  242. graph_set_column_colors(column_colors_ansi,
  243. column_colors_ansi_max);
  244. } else {
  245. static struct argv_array custom_colors = ARGV_ARRAY_INIT;
  246. argv_array_clear(&custom_colors);
  247. parse_graph_colors_config(&custom_colors, string);
  248. free(string);
  249. /* graph_set_column_colors takes a max-index, not a count */
  250. graph_set_column_colors(custom_colors.argv,
  251. custom_colors.argc - 1);
  252. }
  253. }
  254. graph->commit = NULL;
  255. graph->revs = opt;
  256. graph->num_parents = 0;
  257. graph->expansion_row = 0;
  258. graph->state = GRAPH_PADDING;
  259. graph->prev_state = GRAPH_PADDING;
  260. graph->commit_index = 0;
  261. graph->prev_commit_index = 0;
  262. graph->num_columns = 0;
  263. graph->num_new_columns = 0;
  264. graph->mapping_size = 0;
  265. /*
  266. * Start the column color at the maximum value, since we'll
  267. * always increment it for the first commit we output.
  268. * This way we start at 0 for the first commit.
  269. */
  270. graph->default_column_color = column_colors_max - 1;
  271. /*
  272. * Allocate a reasonably large default number of columns
  273. * We'll automatically grow columns later if we need more room.
  274. */
  275. graph->column_capacity = 30;
  276. ALLOC_ARRAY(graph->columns, graph->column_capacity);
  277. ALLOC_ARRAY(graph->new_columns, graph->column_capacity);
  278. ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity);
  279. ALLOC_ARRAY(graph->new_mapping, 2 * graph->column_capacity);
  280. /*
  281. * The diff output prefix callback, with this we can make
  282. * all the diff output to align with the graph lines.
  283. */
  284. opt->diffopt.output_prefix = diff_output_prefix_callback;
  285. opt->diffopt.output_prefix_data = graph;
  286. return graph;
  287. }
  288. static void graph_update_state(struct git_graph *graph, enum graph_state s)
  289. {
  290. graph->prev_state = graph->state;
  291. graph->state = s;
  292. }
  293. static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
  294. {
  295. if (graph->column_capacity >= num_columns)
  296. return;
  297. do {
  298. graph->column_capacity *= 2;
  299. } while (graph->column_capacity < num_columns);
  300. REALLOC_ARRAY(graph->columns, graph->column_capacity);
  301. REALLOC_ARRAY(graph->new_columns, graph->column_capacity);
  302. REALLOC_ARRAY(graph->mapping, graph->column_capacity * 2);
  303. REALLOC_ARRAY(graph->new_mapping, graph->column_capacity * 2);
  304. }
  305. /*
  306. * Returns 1 if the commit will be printed in the graph output,
  307. * and 0 otherwise.
  308. */
  309. static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
  310. {
  311. /*
  312. * If revs->boundary is set, commits whose children have
  313. * been shown are always interesting, even if they have the
  314. * UNINTERESTING or TREESAME flags set.
  315. */
  316. if (graph->revs && graph->revs->boundary) {
  317. if (commit->object.flags & CHILD_SHOWN)
  318. return 1;
  319. }
  320. /*
  321. * Otherwise, use get_commit_action() to see if this commit is
  322. * interesting
  323. */
  324. return get_commit_action(graph->revs, commit) == commit_show;
  325. }
  326. static struct commit_list *next_interesting_parent(struct git_graph *graph,
  327. struct commit_list *orig)
  328. {
  329. struct commit_list *list;
  330. /*
  331. * If revs->first_parent_only is set, only the first
  332. * parent is interesting. None of the others are.
  333. */
  334. if (graph->revs->first_parent_only)
  335. return NULL;
  336. /*
  337. * Return the next interesting commit after orig
  338. */
  339. for (list = orig->next; list; list = list->next) {
  340. if (graph_is_interesting(graph, list->item))
  341. return list;
  342. }
  343. return NULL;
  344. }
  345. static struct commit_list *first_interesting_parent(struct git_graph *graph)
  346. {
  347. struct commit_list *parents = graph->commit->parents;
  348. /*
  349. * If this commit has no parents, ignore it
  350. */
  351. if (!parents)
  352. return NULL;
  353. /*
  354. * If the first parent is interesting, return it
  355. */
  356. if (graph_is_interesting(graph, parents->item))
  357. return parents;
  358. /*
  359. * Otherwise, call next_interesting_parent() to get
  360. * the next interesting parent
  361. */
  362. return next_interesting_parent(graph, parents);
  363. }
  364. static unsigned short graph_get_current_column_color(const struct git_graph *graph)
  365. {
  366. if (!want_color(graph->revs->diffopt.use_color))
  367. return column_colors_max;
  368. return graph->default_column_color;
  369. }
  370. /*
  371. * Update the graph's default column color.
  372. */
  373. static void graph_increment_column_color(struct git_graph *graph)
  374. {
  375. graph->default_column_color = (graph->default_column_color + 1) %
  376. column_colors_max;
  377. }
  378. static unsigned short graph_find_commit_color(const struct git_graph *graph,
  379. const struct commit *commit)
  380. {
  381. int i;
  382. for (i = 0; i < graph->num_columns; i++) {
  383. if (graph->columns[i].commit == commit)
  384. return graph->columns[i].color;
  385. }
  386. return graph_get_current_column_color(graph);
  387. }
  388. static void graph_insert_into_new_columns(struct git_graph *graph,
  389. struct commit *commit,
  390. int *mapping_index)
  391. {
  392. int i;
  393. /*
  394. * If the commit is already in the new_columns list, we don't need to
  395. * add it. Just update the mapping correctly.
  396. */
  397. for (i = 0; i < graph->num_new_columns; i++) {
  398. if (graph->new_columns[i].commit == commit) {
  399. graph->mapping[*mapping_index] = i;
  400. *mapping_index += 2;
  401. return;
  402. }
  403. }
  404. /*
  405. * This commit isn't already in new_columns. Add it.
  406. */
  407. graph->new_columns[graph->num_new_columns].commit = commit;
  408. graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
  409. graph->mapping[*mapping_index] = graph->num_new_columns;
  410. *mapping_index += 2;
  411. graph->num_new_columns++;
  412. }
  413. static void graph_update_width(struct git_graph *graph,
  414. int is_commit_in_existing_columns)
  415. {
  416. /*
  417. * Compute the width needed to display the graph for this commit.
  418. * This is the maximum width needed for any row. All other rows
  419. * will be padded to this width.
  420. *
  421. * Compute the number of columns in the widest row:
  422. * Count each existing column (graph->num_columns), and each new
  423. * column added by this commit.
  424. */
  425. int max_cols = graph->num_columns + graph->num_parents;
  426. /*
  427. * Even if the current commit has no parents to be printed, it
  428. * still takes up a column for itself.
  429. */
  430. if (graph->num_parents < 1)
  431. max_cols++;
  432. /*
  433. * We added a column for the current commit as part of
  434. * graph->num_parents. If the current commit was already in
  435. * graph->columns, then we have double counted it.
  436. */
  437. if (is_commit_in_existing_columns)
  438. max_cols--;
  439. /*
  440. * Each column takes up 2 spaces
  441. */
  442. graph->width = max_cols * 2;
  443. }
  444. static void graph_update_columns(struct git_graph *graph)
  445. {
  446. struct commit_list *parent;
  447. int max_new_columns;
  448. int mapping_idx;
  449. int i, seen_this, is_commit_in_columns;
  450. /*
  451. * Swap graph->columns with graph->new_columns
  452. * graph->columns contains the state for the previous commit,
  453. * and new_columns now contains the state for our commit.
  454. *
  455. * We'll re-use the old columns array as storage to compute the new
  456. * columns list for the commit after this one.
  457. */
  458. SWAP(graph->columns, graph->new_columns);
  459. graph->num_columns = graph->num_new_columns;
  460. graph->num_new_columns = 0;
  461. /*
  462. * Now update new_columns and mapping with the information for the
  463. * commit after this one.
  464. *
  465. * First, make sure we have enough room. At most, there will
  466. * be graph->num_columns + graph->num_parents columns for the next
  467. * commit.
  468. */
  469. max_new_columns = graph->num_columns + graph->num_parents;
  470. graph_ensure_capacity(graph, max_new_columns);
  471. /*
  472. * Clear out graph->mapping
  473. */
  474. graph->mapping_size = 2 * max_new_columns;
  475. for (i = 0; i < graph->mapping_size; i++)
  476. graph->mapping[i] = -1;
  477. /*
  478. * Populate graph->new_columns and graph->mapping
  479. *
  480. * Some of the parents of this commit may already be in
  481. * graph->columns. If so, graph->new_columns should only contain a
  482. * single entry for each such commit. graph->mapping should
  483. * contain information about where each current branch line is
  484. * supposed to end up after the collapsing is performed.
  485. */
  486. seen_this = 0;
  487. mapping_idx = 0;
  488. is_commit_in_columns = 1;
  489. for (i = 0; i <= graph->num_columns; i++) {
  490. struct commit *col_commit;
  491. if (i == graph->num_columns) {
  492. if (seen_this)
  493. break;
  494. is_commit_in_columns = 0;
  495. col_commit = graph->commit;
  496. } else {
  497. col_commit = graph->columns[i].commit;
  498. }
  499. if (col_commit == graph->commit) {
  500. int old_mapping_idx = mapping_idx;
  501. seen_this = 1;
  502. graph->commit_index = i;
  503. for (parent = first_interesting_parent(graph);
  504. parent;
  505. parent = next_interesting_parent(graph, parent)) {
  506. /*
  507. * If this is a merge, or the start of a new
  508. * childless column, increment the current
  509. * color.
  510. */
  511. if (graph->num_parents > 1 ||
  512. !is_commit_in_columns) {
  513. graph_increment_column_color(graph);
  514. }
  515. graph_insert_into_new_columns(graph,
  516. parent->item,
  517. &mapping_idx);
  518. }
  519. /*
  520. * We always need to increment mapping_idx by at
  521. * least 2, even if it has no interesting parents.
  522. * The current commit always takes up at least 2
  523. * spaces.
  524. */
  525. if (mapping_idx == old_mapping_idx)
  526. mapping_idx += 2;
  527. } else {
  528. graph_insert_into_new_columns(graph, col_commit,
  529. &mapping_idx);
  530. }
  531. }
  532. /*
  533. * Shrink mapping_size to be the minimum necessary
  534. */
  535. while (graph->mapping_size > 1 &&
  536. graph->mapping[graph->mapping_size - 1] < 0)
  537. graph->mapping_size--;
  538. /*
  539. * Compute graph->width for this commit
  540. */
  541. graph_update_width(graph, is_commit_in_columns);
  542. }
  543. void graph_update(struct git_graph *graph, struct commit *commit)
  544. {
  545. struct commit_list *parent;
  546. /*
  547. * Set the new commit
  548. */
  549. graph->commit = commit;
  550. /*
  551. * Count how many interesting parents this commit has
  552. */
  553. graph->num_parents = 0;
  554. for (parent = first_interesting_parent(graph);
  555. parent;
  556. parent = next_interesting_parent(graph, parent))
  557. {
  558. graph->num_parents++;
  559. }
  560. /*
  561. * Store the old commit_index in prev_commit_index.
  562. * graph_update_columns() will update graph->commit_index for this
  563. * commit.
  564. */
  565. graph->prev_commit_index = graph->commit_index;
  566. /*
  567. * Call graph_update_columns() to update
  568. * columns, new_columns, and mapping.
  569. */
  570. graph_update_columns(graph);
  571. graph->expansion_row = 0;
  572. /*
  573. * Update graph->state.
  574. * Note that we don't call graph_update_state() here, since
  575. * we don't want to update graph->prev_state. No line for
  576. * graph->state was ever printed.
  577. *
  578. * If the previous commit didn't get to the GRAPH_PADDING state,
  579. * it never finished its output. Goto GRAPH_SKIP, to print out
  580. * a line to indicate that portion of the graph is missing.
  581. *
  582. * If there are 3 or more parents, we may need to print extra rows
  583. * before the commit, to expand the branch lines around it and make
  584. * room for it. We need to do this only if there is a branch row
  585. * (or more) to the right of this commit.
  586. *
  587. * If there are less than 3 parents, we can immediately print the
  588. * commit line.
  589. */
  590. if (graph->state != GRAPH_PADDING)
  591. graph->state = GRAPH_SKIP;
  592. else if (graph->num_parents >= 3 &&
  593. graph->commit_index < (graph->num_columns - 1))
  594. graph->state = GRAPH_PRE_COMMIT;
  595. else
  596. graph->state = GRAPH_COMMIT;
  597. }
  598. static int graph_is_mapping_correct(struct git_graph *graph)
  599. {
  600. int i;
  601. /*
  602. * The mapping is up to date if each entry is at its target,
  603. * or is 1 greater than its target.
  604. * (If it is 1 greater than the target, '/' will be printed, so it
  605. * will look correct on the next row.)
  606. */
  607. for (i = 0; i < graph->mapping_size; i++) {
  608. int target = graph->mapping[i];
  609. if (target < 0)
  610. continue;
  611. if (target == (i / 2))
  612. continue;
  613. return 0;
  614. }
  615. return 1;
  616. }
  617. static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
  618. int chars_written)
  619. {
  620. /*
  621. * Add additional spaces to the end of the strbuf, so that all
  622. * lines for a particular commit have the same width.
  623. *
  624. * This way, fields printed to the right of the graph will remain
  625. * aligned for the entire commit.
  626. */
  627. if (chars_written < graph->width)
  628. strbuf_addchars(sb, ' ', graph->width - chars_written);
  629. }
  630. static void graph_output_padding_line(struct git_graph *graph,
  631. struct strbuf *sb)
  632. {
  633. int i;
  634. /*
  635. * We could conceivable be called with a NULL commit
  636. * if our caller has a bug, and invokes graph_next_line()
  637. * immediately after graph_init(), without first calling
  638. * graph_update(). Return without outputting anything in this
  639. * case.
  640. */
  641. if (!graph->commit)
  642. return;
  643. /*
  644. * Output a padding row, that leaves all branch lines unchanged
  645. */
  646. for (i = 0; i < graph->num_new_columns; i++) {
  647. strbuf_write_column(sb, &graph->new_columns[i], '|');
  648. strbuf_addch(sb, ' ');
  649. }
  650. graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
  651. }
  652. int graph_width(struct git_graph *graph)
  653. {
  654. return graph->width;
  655. }
  656. static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
  657. {
  658. /*
  659. * Output an ellipsis to indicate that a portion
  660. * of the graph is missing.
  661. */
  662. strbuf_addstr(sb, "...");
  663. graph_pad_horizontally(graph, sb, 3);
  664. if (graph->num_parents >= 3 &&
  665. graph->commit_index < (graph->num_columns - 1))
  666. graph_update_state(graph, GRAPH_PRE_COMMIT);
  667. else
  668. graph_update_state(graph, GRAPH_COMMIT);
  669. }
  670. static void graph_output_pre_commit_line(struct git_graph *graph,
  671. struct strbuf *sb)
  672. {
  673. int num_expansion_rows;
  674. int i, seen_this;
  675. int chars_written;
  676. /*
  677. * This function formats a row that increases the space around a commit
  678. * with multiple parents, to make room for it. It should only be
  679. * called when there are 3 or more parents.
  680. *
  681. * We need 2 extra rows for every parent over 2.
  682. */
  683. assert(graph->num_parents >= 3);
  684. num_expansion_rows = (graph->num_parents - 2) * 2;
  685. /*
  686. * graph->expansion_row tracks the current expansion row we are on.
  687. * It should be in the range [0, num_expansion_rows - 1]
  688. */
  689. assert(0 <= graph->expansion_row &&
  690. graph->expansion_row < num_expansion_rows);
  691. /*
  692. * Output the row
  693. */
  694. seen_this = 0;
  695. chars_written = 0;
  696. for (i = 0; i < graph->num_columns; i++) {
  697. struct column *col = &graph->columns[i];
  698. if (col->commit == graph->commit) {
  699. seen_this = 1;
  700. strbuf_write_column(sb, col, '|');
  701. strbuf_addchars(sb, ' ', graph->expansion_row);
  702. chars_written += 1 + graph->expansion_row;
  703. } else if (seen_this && (graph->expansion_row == 0)) {
  704. /*
  705. * This is the first line of the pre-commit output.
  706. * If the previous commit was a merge commit and
  707. * ended in the GRAPH_POST_MERGE state, all branch
  708. * lines after graph->prev_commit_index were
  709. * printed as "\" on the previous line. Continue
  710. * to print them as "\" on this line. Otherwise,
  711. * print the branch lines as "|".
  712. */
  713. if (graph->prev_state == GRAPH_POST_MERGE &&
  714. graph->prev_commit_index < i)
  715. strbuf_write_column(sb, col, '\\');
  716. else
  717. strbuf_write_column(sb, col, '|');
  718. chars_written++;
  719. } else if (seen_this && (graph->expansion_row > 0)) {
  720. strbuf_write_column(sb, col, '\\');
  721. chars_written++;
  722. } else {
  723. strbuf_write_column(sb, col, '|');
  724. chars_written++;
  725. }
  726. strbuf_addch(sb, ' ');
  727. chars_written++;
  728. }
  729. graph_pad_horizontally(graph, sb, chars_written);
  730. /*
  731. * Increment graph->expansion_row,
  732. * and move to state GRAPH_COMMIT if necessary
  733. */
  734. graph->expansion_row++;
  735. if (graph->expansion_row >= num_expansion_rows)
  736. graph_update_state(graph, GRAPH_COMMIT);
  737. }
  738. static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
  739. {
  740. /*
  741. * For boundary commits, print 'o'
  742. * (We should only see boundary commits when revs->boundary is set.)
  743. */
  744. if (graph->commit->object.flags & BOUNDARY) {
  745. assert(graph->revs->boundary);
  746. strbuf_addch(sb, 'o');
  747. return;
  748. }
  749. /*
  750. * get_revision_mark() handles all other cases without assert()
  751. */
  752. strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
  753. }
  754. /*
  755. * Draw the horizontal dashes of an octopus merge and return the number of
  756. * characters written.
  757. */
  758. static int graph_draw_octopus_merge(struct git_graph *graph,
  759. struct strbuf *sb)
  760. {
  761. /*
  762. * Here dashless_parents represents the number of parents which don't
  763. * need to have dashes (the edges labeled "0" and "1"). And
  764. * dashful_parents are the remaining ones.
  765. *
  766. * | *---.
  767. * | |\ \ \
  768. * | | | | |
  769. * x 0 1 2 3
  770. *
  771. */
  772. const int dashless_parents = 2;
  773. int dashful_parents = graph->num_parents - dashless_parents;
  774. /*
  775. * Usually, we add one new column for each parent (like the diagram
  776. * above) but sometimes the first parent goes into an existing column,
  777. * like this:
  778. *
  779. * | *---.
  780. * | |\ \ \
  781. * |/ / / /
  782. * x 0 1 2
  783. *
  784. * In which case the number of parents will be one greater than the
  785. * number of added columns.
  786. */
  787. int added_cols = (graph->num_new_columns - graph->num_columns);
  788. int parent_in_old_cols = graph->num_parents - added_cols;
  789. /*
  790. * In both cases, commit_index corresponds to the edge labeled "0".
  791. */
  792. int first_col = graph->commit_index + dashless_parents
  793. - parent_in_old_cols;
  794. int i;
  795. for (i = 0; i < dashful_parents; i++) {
  796. strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
  797. strbuf_write_column(sb, &graph->new_columns[i+first_col],
  798. i == dashful_parents-1 ? '.' : '-');
  799. }
  800. return 2 * dashful_parents;
  801. }
  802. static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
  803. {
  804. int seen_this = 0;
  805. int i, chars_written;
  806. /*
  807. * Output the row containing this commit
  808. * Iterate up to and including graph->num_columns,
  809. * since the current commit may not be in any of the existing
  810. * columns. (This happens when the current commit doesn't have any
  811. * children that we have already processed.)
  812. */
  813. seen_this = 0;
  814. chars_written = 0;
  815. for (i = 0; i <= graph->num_columns; i++) {
  816. struct column *col = &graph->columns[i];
  817. struct commit *col_commit;
  818. if (i == graph->num_columns) {
  819. if (seen_this)
  820. break;
  821. col_commit = graph->commit;
  822. } else {
  823. col_commit = graph->columns[i].commit;
  824. }
  825. if (col_commit == graph->commit) {
  826. seen_this = 1;
  827. graph_output_commit_char(graph, sb);
  828. chars_written++;
  829. if (graph->num_parents > 2)
  830. chars_written += graph_draw_octopus_merge(graph,
  831. sb);
  832. } else if (seen_this && (graph->num_parents > 2)) {
  833. strbuf_write_column(sb, col, '\\');
  834. chars_written++;
  835. } else if (seen_this && (graph->num_parents == 2)) {
  836. /*
  837. * This is a 2-way merge commit.
  838. * There is no GRAPH_PRE_COMMIT stage for 2-way
  839. * merges, so this is the first line of output
  840. * for this commit. Check to see what the previous
  841. * line of output was.
  842. *
  843. * If it was GRAPH_POST_MERGE, the branch line
  844. * coming into this commit may have been '\',
  845. * and not '|' or '/'. If so, output the branch
  846. * line as '\' on this line, instead of '|'. This
  847. * makes the output look nicer.
  848. */
  849. if (graph->prev_state == GRAPH_POST_MERGE &&
  850. graph->prev_commit_index < i)
  851. strbuf_write_column(sb, col, '\\');
  852. else
  853. strbuf_write_column(sb, col, '|');
  854. chars_written++;
  855. } else {
  856. strbuf_write_column(sb, col, '|');
  857. chars_written++;
  858. }
  859. strbuf_addch(sb, ' ');
  860. chars_written++;
  861. }
  862. graph_pad_horizontally(graph, sb, chars_written);
  863. /*
  864. * Update graph->state
  865. */
  866. if (graph->num_parents > 1)
  867. graph_update_state(graph, GRAPH_POST_MERGE);
  868. else if (graph_is_mapping_correct(graph))
  869. graph_update_state(graph, GRAPH_PADDING);
  870. else
  871. graph_update_state(graph, GRAPH_COLLAPSING);
  872. }
  873. static struct column *find_new_column_by_commit(struct git_graph *graph,
  874. struct commit *commit)
  875. {
  876. int i;
  877. for (i = 0; i < graph->num_new_columns; i++) {
  878. if (graph->new_columns[i].commit == commit)
  879. return &graph->new_columns[i];
  880. }
  881. return NULL;
  882. }
  883. static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
  884. {
  885. int seen_this = 0;
  886. int i, j, chars_written;
  887. /*
  888. * Output the post-merge row
  889. */
  890. chars_written = 0;
  891. for (i = 0; i <= graph->num_columns; i++) {
  892. struct column *col = &graph->columns[i];
  893. struct commit *col_commit;
  894. if (i == graph->num_columns) {
  895. if (seen_this)
  896. break;
  897. col_commit = graph->commit;
  898. } else {
  899. col_commit = col->commit;
  900. }
  901. if (col_commit == graph->commit) {
  902. /*
  903. * Since the current commit is a merge find
  904. * the columns for the parent commits in
  905. * new_columns and use those to format the
  906. * edges.
  907. */
  908. struct commit_list *parents = NULL;
  909. struct column *par_column;
  910. seen_this = 1;
  911. parents = first_interesting_parent(graph);
  912. assert(parents);
  913. par_column = find_new_column_by_commit(graph, parents->item);
  914. assert(par_column);
  915. strbuf_write_column(sb, par_column, '|');
  916. chars_written++;
  917. for (j = 0; j < graph->num_parents - 1; j++) {
  918. parents = next_interesting_parent(graph, parents);
  919. assert(parents);
  920. par_column = find_new_column_by_commit(graph, parents->item);
  921. assert(par_column);
  922. strbuf_write_column(sb, par_column, '\\');
  923. strbuf_addch(sb, ' ');
  924. }
  925. chars_written += j * 2;
  926. } else if (seen_this) {
  927. strbuf_write_column(sb, col, '\\');
  928. strbuf_addch(sb, ' ');
  929. chars_written += 2;
  930. } else {
  931. strbuf_write_column(sb, col, '|');
  932. strbuf_addch(sb, ' ');
  933. chars_written += 2;
  934. }
  935. }
  936. graph_pad_horizontally(graph, sb, chars_written);
  937. /*
  938. * Update graph->state
  939. */
  940. if (graph_is_mapping_correct(graph))
  941. graph_update_state(graph, GRAPH_PADDING);
  942. else
  943. graph_update_state(graph, GRAPH_COLLAPSING);
  944. }
  945. static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
  946. {
  947. int i;
  948. short used_horizontal = 0;
  949. int horizontal_edge = -1;
  950. int horizontal_edge_target = -1;
  951. /*
  952. * Clear out the new_mapping array
  953. */
  954. for (i = 0; i < graph->mapping_size; i++)
  955. graph->new_mapping[i] = -1;
  956. for (i = 0; i < graph->mapping_size; i++) {
  957. int target = graph->mapping[i];
  958. if (target < 0)
  959. continue;
  960. /*
  961. * Since update_columns() always inserts the leftmost
  962. * column first, each branch's target location should
  963. * always be either its current location or to the left of
  964. * its current location.
  965. *
  966. * We never have to move branches to the right. This makes
  967. * the graph much more legible, since whenever branches
  968. * cross, only one is moving directions.
  969. */
  970. assert(target * 2 <= i);
  971. if (target * 2 == i) {
  972. /*
  973. * This column is already in the
  974. * correct place
  975. */
  976. assert(graph->new_mapping[i] == -1);
  977. graph->new_mapping[i] = target;
  978. } else if (graph->new_mapping[i - 1] < 0) {
  979. /*
  980. * Nothing is to the left.
  981. * Move to the left by one
  982. */
  983. graph->new_mapping[i - 1] = target;
  984. /*
  985. * If there isn't already an edge moving horizontally
  986. * select this one.
  987. */
  988. if (horizontal_edge == -1) {
  989. int j;
  990. horizontal_edge = i;
  991. horizontal_edge_target = target;
  992. /*
  993. * The variable target is the index of the graph
  994. * column, and therefore target*2+3 is the
  995. * actual screen column of the first horizontal
  996. * line.
  997. */
  998. for (j = (target * 2)+3; j < (i - 2); j += 2)
  999. graph->new_mapping[j] = target;
  1000. }
  1001. } else if (graph->new_mapping[i - 1] == target) {
  1002. /*
  1003. * There is a branch line to our left
  1004. * already, and it is our target. We
  1005. * combine with this line, since we share
  1006. * the same parent commit.
  1007. *
  1008. * We don't have to add anything to the
  1009. * output or new_mapping, since the
  1010. * existing branch line has already taken
  1011. * care of it.
  1012. */
  1013. } else {
  1014. /*
  1015. * There is a branch line to our left,
  1016. * but it isn't our target. We need to
  1017. * cross over it.
  1018. *
  1019. * The space just to the left of this
  1020. * branch should always be empty.
  1021. *
  1022. * The branch to the left of that space
  1023. * should be our eventual target.
  1024. */
  1025. assert(graph->new_mapping[i - 1] > target);
  1026. assert(graph->new_mapping[i - 2] < 0);
  1027. assert(graph->new_mapping[i - 3] == target);
  1028. graph->new_mapping[i - 2] = target;
  1029. /*
  1030. * Mark this branch as the horizontal edge to
  1031. * prevent any other edges from moving
  1032. * horizontally.
  1033. */
  1034. if (horizontal_edge == -1)
  1035. horizontal_edge = i;
  1036. }
  1037. }
  1038. /*
  1039. * The new mapping may be 1 smaller than the old mapping
  1040. */
  1041. if (graph->new_mapping[graph->mapping_size - 1] < 0)
  1042. graph->mapping_size--;
  1043. /*
  1044. * Output out a line based on the new mapping info
  1045. */
  1046. for (i = 0; i < graph->mapping_size; i++) {
  1047. int target = graph->new_mapping[i];
  1048. if (target < 0)
  1049. strbuf_addch(sb, ' ');
  1050. else if (target * 2 == i)
  1051. strbuf_write_column(sb, &graph->new_columns[target], '|');
  1052. else if (target == horizontal_edge_target &&
  1053. i != horizontal_edge - 1) {
  1054. /*
  1055. * Set the mappings for all but the
  1056. * first segment to -1 so that they
  1057. * won't continue into the next line.
  1058. */
  1059. if (i != (target * 2)+3)
  1060. graph->new_mapping[i] = -1;
  1061. used_horizontal = 1;
  1062. strbuf_write_column(sb, &graph->new_columns[target], '_');
  1063. } else {
  1064. if (used_horizontal && i < horizontal_edge)
  1065. graph->new_mapping[i] = -1;
  1066. strbuf_write_column(sb, &graph->new_columns[target], '/');
  1067. }
  1068. }
  1069. graph_pad_horizontally(graph, sb, graph->mapping_size);
  1070. /*
  1071. * Swap mapping and new_mapping
  1072. */
  1073. SWAP(graph->mapping, graph->new_mapping);
  1074. /*
  1075. * If graph->mapping indicates that all of the branch lines
  1076. * are already in the correct positions, we are done.
  1077. * Otherwise, we need to collapse some branch lines together.
  1078. */
  1079. if (graph_is_mapping_correct(graph))
  1080. graph_update_state(graph, GRAPH_PADDING);
  1081. }
  1082. int graph_next_line(struct git_graph *graph, struct strbuf *sb)
  1083. {
  1084. switch (graph->state) {
  1085. case GRAPH_PADDING:
  1086. graph_output_padding_line(graph, sb);
  1087. return 0;
  1088. case GRAPH_SKIP:
  1089. graph_output_skip_line(graph, sb);
  1090. return 0;
  1091. case GRAPH_PRE_COMMIT:
  1092. graph_output_pre_commit_line(graph, sb);
  1093. return 0;
  1094. case GRAPH_COMMIT:
  1095. graph_output_commit_line(graph, sb);
  1096. return 1;
  1097. case GRAPH_POST_MERGE:
  1098. graph_output_post_merge_line(graph, sb);
  1099. return 0;
  1100. case GRAPH_COLLAPSING:
  1101. graph_output_collapsing_line(graph, sb);
  1102. return 0;
  1103. }
  1104. assert(0);
  1105. return 0;
  1106. }
  1107. static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
  1108. {
  1109. int i;
  1110. int chars_written = 0;
  1111. if (graph->state != GRAPH_COMMIT) {
  1112. graph_next_line(graph, sb);
  1113. return;
  1114. }
  1115. /*
  1116. * Output the row containing this commit
  1117. * Iterate up to and including graph->num_columns,
  1118. * since the current commit may not be in any of the existing
  1119. * columns. (This happens when the current commit doesn't have any
  1120. * children that we have already processed.)
  1121. */
  1122. for (i = 0; i < graph->num_columns; i++) {
  1123. struct column *col = &graph->columns[i];
  1124. strbuf_write_column(sb, col, '|');
  1125. chars_written++;
  1126. if (col->commit == graph->commit && graph->num_parents > 2) {
  1127. int len = (graph->num_parents - 2) * 2;
  1128. strbuf_addchars(sb, ' ', len);
  1129. chars_written += len;
  1130. } else {
  1131. strbuf_addch(sb, ' ');
  1132. chars_written++;
  1133. }
  1134. }
  1135. graph_pad_horizontally(graph, sb, chars_written);
  1136. /*
  1137. * Update graph->prev_state since we have output a padding line
  1138. */
  1139. graph->prev_state = GRAPH_PADDING;
  1140. }
  1141. int graph_is_commit_finished(struct git_graph const *graph)
  1142. {
  1143. return (graph->state == GRAPH_PADDING);
  1144. }
  1145. void graph_show_commit(struct git_graph *graph)
  1146. {
  1147. struct strbuf msgbuf = STRBUF_INIT;
  1148. int shown_commit_line = 0;
  1149. graph_show_line_prefix(default_diffopt);
  1150. if (!graph)
  1151. return;
  1152. /*
  1153. * When showing a diff of a merge against each of its parents, we
  1154. * are called once for each parent without graph_update having been
  1155. * called. In this case, simply output a single padding line.
  1156. */
  1157. if (graph_is_commit_finished(graph)) {
  1158. graph_show_padding(graph);
  1159. shown_commit_line = 1;
  1160. }
  1161. while (!shown_commit_line && !graph_is_commit_finished(graph)) {
  1162. shown_commit_line = graph_next_line(graph, &msgbuf);
  1163. fwrite(msgbuf.buf, sizeof(char), msgbuf.len,
  1164. graph->revs->diffopt.file);
  1165. if (!shown_commit_line) {
  1166. putc('\n', graph->revs->diffopt.file);
  1167. graph_show_line_prefix(&graph->revs->diffopt);
  1168. }
  1169. strbuf_setlen(&msgbuf, 0);
  1170. }
  1171. strbuf_release(&msgbuf);
  1172. }
  1173. void graph_show_oneline(struct git_graph *graph)
  1174. {
  1175. struct strbuf msgbuf = STRBUF_INIT;
  1176. graph_show_line_prefix(default_diffopt);
  1177. if (!graph)
  1178. return;
  1179. graph_next_line(graph, &msgbuf);
  1180. fwrite(msgbuf.buf, sizeof(char), msgbuf.len, graph->revs->diffopt.file);
  1181. strbuf_release(&msgbuf);
  1182. }
  1183. void graph_show_padding(struct git_graph *graph)
  1184. {
  1185. struct strbuf msgbuf = STRBUF_INIT;
  1186. graph_show_line_prefix(default_diffopt);
  1187. if (!graph)
  1188. return;
  1189. graph_padding_line(graph, &msgbuf);
  1190. fwrite(msgbuf.buf, sizeof(char), msgbuf.len, graph->revs->diffopt.file);
  1191. strbuf_release(&msgbuf);
  1192. }
  1193. int graph_show_remainder(struct git_graph *graph)
  1194. {
  1195. struct strbuf msgbuf = STRBUF_INIT;
  1196. int shown = 0;
  1197. graph_show_line_prefix(default_diffopt);
  1198. if (!graph)
  1199. return 0;
  1200. if (graph_is_commit_finished(graph))
  1201. return 0;
  1202. for (;;) {
  1203. graph_next_line(graph, &msgbuf);
  1204. fwrite(msgbuf.buf, sizeof(char), msgbuf.len,
  1205. graph->revs->diffopt.file);
  1206. strbuf_setlen(&msgbuf, 0);
  1207. shown = 1;
  1208. if (!graph_is_commit_finished(graph)) {
  1209. putc('\n', graph->revs->diffopt.file);
  1210. graph_show_line_prefix(&graph->revs->diffopt);
  1211. } else {
  1212. break;
  1213. }
  1214. }
  1215. strbuf_release(&msgbuf);
  1216. return shown;
  1217. }
  1218. static void graph_show_strbuf(struct git_graph *graph,
  1219. FILE *file,
  1220. struct strbuf const *sb)
  1221. {
  1222. char *p;
  1223. /*
  1224. * Print the strbuf line by line,
  1225. * and display the graph info before each line but the first.
  1226. */
  1227. p = sb->buf;
  1228. while (p) {
  1229. size_t len;
  1230. char *next_p = strchr(p, '\n');
  1231. if (next_p) {
  1232. next_p++;
  1233. len = next_p - p;
  1234. } else {
  1235. len = (sb->buf + sb->len) - p;
  1236. }
  1237. fwrite(p, sizeof(char), len, file);
  1238. if (next_p && *next_p != '\0')
  1239. graph_show_oneline(graph);
  1240. p = next_p;
  1241. }
  1242. }
  1243. void graph_show_commit_msg(struct git_graph *graph,
  1244. FILE *file,
  1245. struct strbuf const *sb)
  1246. {
  1247. int newline_terminated;
  1248. /*
  1249. * Show the commit message
  1250. */
  1251. graph_show_strbuf(graph, file, sb);
  1252. if (!graph)
  1253. return;
  1254. newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\n');
  1255. /*
  1256. * If there is more output needed for this commit, show it now
  1257. */
  1258. if (!graph_is_commit_finished(graph)) {
  1259. /*
  1260. * If sb doesn't have a terminating newline, print one now,
  1261. * so we can start the remainder of the graph output on a
  1262. * new line.
  1263. */
  1264. if (!newline_terminated)
  1265. putc('\n', file);
  1266. graph_show_remainder(graph);
  1267. /*
  1268. * If sb ends with a newline, our output should too.
  1269. */
  1270. if (newline_terminated)
  1271. putc('\n', file);
  1272. }
  1273. }