From patchwork Thu Oct 10 16:13:43 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183893 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4B0AB14ED for ; Thu, 10 Oct 2019 16:13:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 191722190F for ; Thu, 10 Oct 2019 16:13:48 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Msi/btXU" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726131AbfJJQNr (ORCPT ); Thu, 10 Oct 2019 12:13:47 -0400 Received: from mail-wm1-f68.google.com ([209.85.128.68]:36024 "EHLO mail-wm1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725978AbfJJQNq (ORCPT ); Thu, 10 Oct 2019 12:13:46 -0400 Received: by mail-wm1-f68.google.com with SMTP id m18so7419054wmc.1 for ; Thu, 10 Oct 2019 09:13:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=NKEjr2o4e7YvpO9myfPIAFVsLL6zk9hzuoqBuKdkJkM=; b=Msi/btXUGKeoTgBFxXuNGeZDV3IJzDZp3lnUO9x80QdJusR72LKph7rhNtCvPlhFLs +F50ECx/iK4KJqVZR80nWX1ZK4VBmqmdcjFLgqwlXl9e/Eo1V38FKKaX7AQsPrx5LkUi nTbHJ8Ro5EE1yKCpcjzKUfsTwuJUn+YIqyP8jW/9EPTGHr1mGyBCBnqIZE9DOqsiOMAD X9kYjlAICRfQiAs6cLK612EuRDXHFVpaSotHh8gFSqKuW9YTOMToBJsl2ieef7zBzj1j nudamCFAwRqkDuQReUozJqm5pCcrwwQjhU+sp7u60uwetzuuARX4kIQ87Fj7q//JuDWC hxKw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=NKEjr2o4e7YvpO9myfPIAFVsLL6zk9hzuoqBuKdkJkM=; b=VXTr0ZqxRgtT7ih+BtYLPrGFXgfiX8I5b3X37emxVV0hz8+ybnsWOgqkKdYqXJlLHz 9qQDrHR4b+P4i9tAhXCoxzItG7uktN5tmGaTYNjJh/sB2WKhCvYmFLgwEzWcM6rfZ9CU Ryxm3Dgq6fKPBdzcnSTyMuMNnIi0dbE7ZfnK6y2Tu+TJi1Pj4DENmLr8eCLeaWEGQ5iM rBHGR49MwA0hWZ2IRm4hSeCqhHSCDHWwDVVJbRrneoNKI775Bx7ZT98H3nK+3vQaJo6j W0Ll0G6bsjsS5TC57uoWPmCzvUCbrfpoiDDeAPU5rgWqpkU5AjpJBK9hoeGaxgRngBs6 WDig== X-Gm-Message-State: APjAAAXWiUeRd5SdV/TSpwni/EpMk5C3wGyd8b5SIY7ShqoIWM8CI3T9 C3neW0hZiUjIQBrPyXUQCUVXg07y X-Google-Smtp-Source: APXvYqwnb1gDljATgFmCyEvtFt3agzZhi60pDhtyqJwcISyjW+y7acN5U+OGWPxL/Q2O6K5oUi8qYA== X-Received: by 2002:a1c:7e10:: with SMTP id z16mr8061543wmc.11.1570724024022; Thu, 10 Oct 2019 09:13:44 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a2sm6611956wrp.11.2019.10.10.09.13.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:43 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:43 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:30 GMT Message-Id: <4bc0a0596164212aa9d29d6dd0d7a0d8ab1b9dd0.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 01/11] graph: automatically track visible width of `strbuf` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan All the output functions in `graph.c` currently keep track of how many printable chars they've written to the buffer, before calling `graph_pad_horizontally()` to pad the line with spaces. Some functions do this by incrementing a counter whenever they write to the buffer, and others do it by encoding an assumption about how many chars are written, as in: graph_pad_horizontally(graph, sb, graph->num_columns * 2); This adds a fair amount of noise to the functions' logic and is easily broken if one forgets to increment the right counter or update the calculations used for padding. To make this easier to use, I'm adding a `width` field to `strbuf` that tracks the number of printing characters added after the line prefix. It's set to 0 at the start of `graph_next_line()`, and then various `strbuf` functions update it as follows: - `strbuf_write_column()` increments `width` by 1 - `strbuf_setlen()` changes `width` by the amount added to `len` if `len` is increased, or makes `width` and `len` the same if it's decreased - `strbuf_addch()` increments `width` by 1 This is enough to ensure that the functions used by `graph.c` update `strbuf->width` correctly, and `graph_pad_horizontally()` can then use this field instead of taking `chars_written` as a parameter. Signed-off-by: James Coglan Signed-off-by: James Coglan --- graph.c | 68 ++++++++++++++++++++++---------------------------------- strbuf.h | 8 ++++++- 2 files changed, 33 insertions(+), 43 deletions(-) diff --git a/graph.c b/graph.c index f53135485f..c56fdec1fc 100644 --- a/graph.c +++ b/graph.c @@ -115,11 +115,20 @@ static const char *column_get_color_code(unsigned short color) static void strbuf_write_column(struct strbuf *sb, const struct column *c, char col_char) { + /* + * Remember the buffer's width as we're about to add non-printing + * content to it, and we want to avoid counting the byte length + * of this content towards the buffer's visible width + */ + size_t prev_width = sb->width; + if (c->color < column_colors_max) strbuf_addstr(sb, column_get_color_code(c->color)); strbuf_addch(sb, col_char); if (c->color < column_colors_max) strbuf_addstr(sb, column_get_color_code(column_colors_max)); + + sb->width = prev_width + 1; } struct git_graph { @@ -686,8 +695,7 @@ static int graph_is_mapping_correct(struct git_graph *graph) return 1; } -static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb, - int chars_written) +static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb) { /* * Add additional spaces to the end of the strbuf, so that all @@ -696,8 +704,8 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb, * This way, fields printed to the right of the graph will remain * aligned for the entire commit. */ - if (chars_written < graph->width) - strbuf_addchars(sb, ' ', graph->width - chars_written); + if (sb->width < graph->width) + strbuf_addchars(sb, ' ', graph->width - sb->width); } static void graph_output_padding_line(struct git_graph *graph, @@ -723,7 +731,7 @@ static void graph_output_padding_line(struct git_graph *graph, strbuf_addch(sb, ' '); } - graph_pad_horizontally(graph, sb, graph->num_new_columns * 2); + graph_pad_horizontally(graph, sb); } @@ -740,7 +748,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb) * of the graph is missing. */ strbuf_addstr(sb, "..."); - graph_pad_horizontally(graph, sb, 3); + graph_pad_horizontally(graph, sb); if (graph->num_parents >= 3 && graph->commit_index < (graph->num_columns - 1)) @@ -754,7 +762,6 @@ static void graph_output_pre_commit_line(struct git_graph *graph, { int num_expansion_rows; int i, seen_this; - int chars_written; /* * This function formats a row that increases the space around a commit @@ -777,14 +784,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph, * Output the row */ seen_this = 0; - chars_written = 0; for (i = 0; i < graph->num_columns; i++) { struct column *col = &graph->columns[i]; if (col->commit == graph->commit) { seen_this = 1; strbuf_write_column(sb, col, '|'); strbuf_addchars(sb, ' ', graph->expansion_row); - chars_written += 1 + graph->expansion_row; } else if (seen_this && (graph->expansion_row == 0)) { /* * This is the first line of the pre-commit output. @@ -800,19 +805,15 @@ static void graph_output_pre_commit_line(struct git_graph *graph, strbuf_write_column(sb, col, '\\'); else strbuf_write_column(sb, col, '|'); - chars_written++; } else if (seen_this && (graph->expansion_row > 0)) { strbuf_write_column(sb, col, '\\'); - chars_written++; } else { strbuf_write_column(sb, col, '|'); - chars_written++; } strbuf_addch(sb, ' '); - chars_written++; } - graph_pad_horizontally(graph, sb, chars_written); + graph_pad_horizontally(graph, sb); /* * Increment graph->expansion_row, @@ -842,11 +843,9 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb) } /* - * Draw the horizontal dashes of an octopus merge and return the number of - * characters written. + * Draw the horizontal dashes of an octopus merge. */ -static int graph_draw_octopus_merge(struct git_graph *graph, - struct strbuf *sb) +static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb) { /* * Here dashless_parents represents the number of parents which don't @@ -890,13 +889,12 @@ static int graph_draw_octopus_merge(struct git_graph *graph, strbuf_write_column(sb, &graph->new_columns[i+first_col], i == dashful_parents-1 ? '.' : '-'); } - return 2 * dashful_parents; } static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) { int seen_this = 0; - int i, chars_written; + int i; /* * Output the row containing this commit @@ -906,7 +904,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) * children that we have already processed.) */ seen_this = 0; - chars_written = 0; for (i = 0; i <= graph->num_columns; i++) { struct column *col = &graph->columns[i]; struct commit *col_commit; @@ -921,14 +918,11 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) if (col_commit == graph->commit) { seen_this = 1; graph_output_commit_char(graph, sb); - chars_written++; if (graph->num_parents > 2) - chars_written += graph_draw_octopus_merge(graph, - sb); + graph_draw_octopus_merge(graph, sb); } else if (seen_this && (graph->num_parents > 2)) { strbuf_write_column(sb, col, '\\'); - chars_written++; } else if (seen_this && (graph->num_parents == 2)) { /* * This is a 2-way merge commit. @@ -948,16 +942,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) strbuf_write_column(sb, col, '\\'); else strbuf_write_column(sb, col, '|'); - chars_written++; } else { strbuf_write_column(sb, col, '|'); - chars_written++; } strbuf_addch(sb, ' '); - chars_written++; } - graph_pad_horizontally(graph, sb, chars_written); + graph_pad_horizontally(graph, sb); /* * Update graph->state @@ -984,12 +975,11 @@ static struct column *find_new_column_by_commit(struct git_graph *graph, static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) { int seen_this = 0; - int i, j, chars_written; + int i, j; /* * Output the post-merge row */ - chars_written = 0; for (i = 0; i <= graph->num_columns; i++) { struct column *col = &graph->columns[i]; struct commit *col_commit; @@ -1017,7 +1007,6 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf assert(par_column); strbuf_write_column(sb, par_column, '|'); - chars_written++; for (j = 0; j < graph->num_parents - 1; j++) { parents = next_interesting_parent(graph, parents); assert(parents); @@ -1026,19 +1015,16 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf strbuf_write_column(sb, par_column, '\\'); strbuf_addch(sb, ' '); } - chars_written += j * 2; } else if (seen_this) { strbuf_write_column(sb, col, '\\'); strbuf_addch(sb, ' '); - chars_written += 2; } else { strbuf_write_column(sb, col, '|'); strbuf_addch(sb, ' '); - chars_written += 2; } } - graph_pad_horizontally(graph, sb, chars_written); + graph_pad_horizontally(graph, sb); /* * Update graph->state @@ -1181,7 +1167,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf } } - graph_pad_horizontally(graph, sb, graph->mapping_size); + graph_pad_horizontally(graph, sb); /* * Swap mapping and new_mapping @@ -1199,6 +1185,8 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf int graph_next_line(struct git_graph *graph, struct strbuf *sb) { + sb->width = 0; + switch (graph->state) { case GRAPH_PADDING: graph_output_padding_line(graph, sb); @@ -1227,7 +1215,6 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb) static void graph_padding_line(struct git_graph *graph, struct strbuf *sb) { int i; - int chars_written = 0; if (graph->state != GRAPH_COMMIT) { graph_next_line(graph, sb); @@ -1245,19 +1232,16 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb) struct column *col = &graph->columns[i]; strbuf_write_column(sb, col, '|'); - chars_written++; if (col->commit == graph->commit && graph->num_parents > 2) { int len = (graph->num_parents - 2) * 2; strbuf_addchars(sb, ' ', len); - chars_written += len; } else { strbuf_addch(sb, ' '); - chars_written++; } } - graph_pad_horizontally(graph, sb, chars_written); + graph_pad_horizontally(graph, sb); /* * Update graph->prev_state since we have output a padding line diff --git a/strbuf.h b/strbuf.h index f62278a0be..3a98147321 100644 --- a/strbuf.h +++ b/strbuf.h @@ -66,11 +66,12 @@ struct string_list; struct strbuf { size_t alloc; size_t len; + size_t width; char *buf; }; extern char strbuf_slopbuf[]; -#define STRBUF_INIT { .alloc = 0, .len = 0, .buf = strbuf_slopbuf } +#define STRBUF_INIT { .alloc = 0, .len = 0, .width = 0, .buf = strbuf_slopbuf } /* * Predeclare this here, since cache.h includes this file before it defines the @@ -161,6 +162,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len) { if (len > (sb->alloc ? sb->alloc - 1 : 0)) die("BUG: strbuf_setlen() beyond buffer"); + if (len > sb->len) + sb->width += len - sb->len; + else + sb->width = len; sb->len = len; if (sb->buf != strbuf_slopbuf) sb->buf[len] = '\0'; @@ -231,6 +236,7 @@ static inline void strbuf_addch(struct strbuf *sb, int c) strbuf_grow(sb, 1); sb->buf[sb->len++] = c; sb->buf[sb->len] = '\0'; + sb->width++; } /** From patchwork Thu Oct 10 16:13:44 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183897 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 5D5EB17EE for ; Thu, 10 Oct 2019 16:13:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 3DF9120B7C for ; Thu, 10 Oct 2019 16:13:50 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Ra8/Q8ps" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726182AbfJJQNs (ORCPT ); Thu, 10 Oct 2019 12:13:48 -0400 Received: from mail-wr1-f65.google.com ([209.85.221.65]:40230 "EHLO mail-wr1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726007AbfJJQNr (ORCPT ); Thu, 10 Oct 2019 12:13:47 -0400 Received: by mail-wr1-f65.google.com with SMTP id h4so8632768wrv.7 for ; Thu, 10 Oct 2019 09:13:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=JCfRjhthfzXV4LQDK1+KzKfPOY0ZXJPV8sfl7ftyaoE=; b=Ra8/Q8psq2XkQXBWXEL97TB3jqbvalEVs+n5P0W7QDEN5FxJ/ndqGT/8Jrgsc7MRSS KY9q5MrCmnLDWTk+A98hKg0FngY9dnuDNJaEPgZBJShxCooj1nhHdsV1+p3x3tLfcWXH 94Vq8oDHQI8oT59LN6qaG3JpoG/qLAgLAa7hTagfyD0cNh4eHUTq5h9kmWXtpmwlW9tx nDULraoTaIn08gaFyV7FWC8rPFz5Q4PV4N54VldXaTbpasSs/PVAXiNshLxiQGKPTrmD RHJrE4zkkRXS8ZDzHH0d3Rc21rfJUvm0nmR+cLNeN9jMM023HgT2gwJbw1WzvmpWshYS +zDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=JCfRjhthfzXV4LQDK1+KzKfPOY0ZXJPV8sfl7ftyaoE=; b=VmjVEj/KwN90QvKf4miCTFs53MwhrXhTacPZz/y7AVRpY/Kv0VaFf+hBaEnGhMh1fo SlrSZghJfsa5FRgvbTDDS5j3c7SRTBf/1Gn8VVwCNG4TT9BYz3fQtYrEvSt3YnODHq6m t53OIoDs1pVoAOXaaLZyRMR4NUgsTdY8uCwTxgxBTuvj/oDaGmx98NP1R3/5L3TmvL26 DBwHEpMTV4UZQtooxgp13oDqlaEBnE0MBPwUzF7ZnN2UaO52QAcCZgZZKTvVATziVFZ3 WvPwjCReG+GTi4Jnllx/KISzRxICxm6BOsebi9eG+ZbMahk+p8yA6W4fYvD8oCxXquoi utBg== X-Gm-Message-State: APjAAAUjFrqn5jmCgoeGH50xyC/y6dtg0CsgYiPyy8nL3m1/osJauUfx zM3QZzQDmwE29D7+FXb+39zrG74g X-Google-Smtp-Source: APXvYqxgJpvUSySiYlMYx6cGkz3z4vwDm2gk6iUiXxMoJLhFBnU7VIfRvQtAvHYsGf3nY1vsfqo+/w== X-Received: by 2002:a5d:6592:: with SMTP id q18mr9912768wru.382.1570724024949; Thu, 10 Oct 2019 09:13:44 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a2sm9887455wrt.45.2019.10.10.09.13.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:44 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:44 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:31 GMT Message-Id: In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 02/11] graph: reuse `find_new_column_by_commit()` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan I will shortly be making some changes to `graph_insert_into_new_columns()` and so am trying to simplify it. One possible simplification is that we can extract the loop for finding the element in `new_columns` containing the given commit. `find_new_column_by_commit()` contains a very similar loop but it returns a `struct column *` rather than an `int` offset into the array. Here I'm introducing a version that returns `int` and using that in `graph_insert_into_new_columns()` and `graph_output_post_merge_line()`. Signed-off-by: James Coglan --- graph.c | 48 +++++++++++++++++++++++------------------------- 1 file changed, 23 insertions(+), 25 deletions(-) diff --git a/graph.c b/graph.c index c56fdec1fc..a890c9d8bb 100644 --- a/graph.c +++ b/graph.c @@ -441,22 +441,31 @@ static unsigned short graph_find_commit_color(const struct git_graph *graph, return graph_get_current_column_color(graph); } +static int graph_find_new_column_by_commit(struct git_graph *graph, + struct commit *commit) +{ + int i; + for (i = 0; i < graph->num_new_columns; i++) { + if (graph->new_columns[i].commit == commit) + return i; + } + return -1; +} + static void graph_insert_into_new_columns(struct git_graph *graph, struct commit *commit, int *mapping_index) { - int i; + int i = graph_find_new_column_by_commit(graph, commit); /* * If the commit is already in the new_columns list, we don't need to * add it. Just update the mapping correctly. */ - for (i = 0; i < graph->num_new_columns; i++) { - if (graph->new_columns[i].commit == commit) { - graph->mapping[*mapping_index] = i; - *mapping_index += 2; - return; - } + if (i >= 0) { + graph->mapping[*mapping_index] = i; + *mapping_index += 2; + return; } /* @@ -961,17 +970,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) graph_update_state(graph, GRAPH_COLLAPSING); } -static struct column *find_new_column_by_commit(struct git_graph *graph, - struct commit *commit) -{ - int i; - for (i = 0; i < graph->num_new_columns; i++) { - if (graph->new_columns[i].commit == commit) - return &graph->new_columns[i]; - } - return NULL; -} - static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) { int seen_this = 0; @@ -999,20 +997,20 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf * edges. */ struct commit_list *parents = NULL; - struct column *par_column; + int par_column; seen_this = 1; parents = first_interesting_parent(graph); assert(parents); - par_column = find_new_column_by_commit(graph, parents->item); - assert(par_column); + par_column = graph_find_new_column_by_commit(graph, parents->item); + assert(par_column >= 0); - strbuf_write_column(sb, par_column, '|'); + strbuf_write_column(sb, &graph->new_columns[par_column], '|'); for (j = 0; j < graph->num_parents - 1; j++) { parents = next_interesting_parent(graph, parents); assert(parents); - par_column = find_new_column_by_commit(graph, parents->item); - assert(par_column); - strbuf_write_column(sb, par_column, '\\'); + par_column = graph_find_new_column_by_commit(graph, parents->item); + assert(par_column >= 0); + strbuf_write_column(sb, &graph->new_columns[par_column], '\\'); strbuf_addch(sb, ' '); } } else if (seen_this) { From patchwork Thu Oct 10 16:13:45 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183895 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E753614ED for ; Thu, 10 Oct 2019 16:13:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C79A020B7C for ; Thu, 10 Oct 2019 16:13:49 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kxUj/Cjo" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726184AbfJJQNs (ORCPT ); Thu, 10 Oct 2019 12:13:48 -0400 Received: from mail-wm1-f68.google.com ([209.85.128.68]:39477 "EHLO mail-wm1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725909AbfJJQNr (ORCPT ); Thu, 10 Oct 2019 12:13:47 -0400 Received: by mail-wm1-f68.google.com with SMTP id v17so7402077wml.4 for ; Thu, 10 Oct 2019 09:13:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=VeHUiI42FrQp6wbepnXUQJLoVSlzgFJZk0le1Rvphbc=; b=kxUj/CjofhA5V5R+67XxgRiuMkQslykSds84USF0N6WUUl0JphpBIcE7hS7VZ3VI+O /NGjKvw6L0Q6SPNx0mHZ351EpqIjWwHWk0p2lKvx8nMz1wJ5OQ0Sh1CxL19/7+61YQVf 4qlYCnO7euXDFohpnAXkHbam1Ob1zyVcW4EX0fQe5YAOARdWLTqVCgksjnCIkuDyFLsK XOBJSFymG/l8EKwGbCNC3JreKrGbKSliqgJh2Op8fCMIE3tm8WDMc5KTMskovGwhXwIW rUsBvhiT8sgWlHiafAU/W0EZqH8BM/Aoz6qQ0rgs0Xa4nMZDdsMXtte0u6M4Pr57tkRd q7qg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=VeHUiI42FrQp6wbepnXUQJLoVSlzgFJZk0le1Rvphbc=; b=sv9O/IzhjbAmyQuEc9+1OVBbFVcqgSYgcGpn0g5MwtZWUmLfvv9w27ERQRGQ/BCJfG 50GVcnBHyKkf+yphd5kIJvAvRAUhT9DPGcA9VQXYSOHaF5NGaB40SR/JRYrQfKUbybBK m7bqzNOW2MFj7ECxmqIBw5pSNYd/62zTYE005bxwKdxP97jv5MKXOayH1PgeReJ81vCC Bp9juKItUhNn3phRk+oxkxQgt4UITbWLfCXU+fgW3ENSzI7k9t/XrlHF6/GIUxDiiPOi zoL1sRkI31OotSRY1LYJH2lRWxhg/13ZJsNIxa2TOYR3bG4c5un4IHUU/GWKXv7DJDq4 WSLw== X-Gm-Message-State: APjAAAU6Swr0zEKkeITI7tfCxaA/SKz/WcFN+8zJiDO/dCrK2qAELxUn eqWUf3XiMwyJ7cb06u4uk1hGArZE X-Google-Smtp-Source: APXvYqx62HOs4QRguNlThJhM0wjjpFwAj33wqT5BjEEFeEcqUrT4k7VwbqDuiWR/6YBcoXopPs9wqQ== X-Received: by 2002:a1c:a8c7:: with SMTP id r190mr8255794wme.162.1570724025774; Thu, 10 Oct 2019 09:13:45 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id q15sm9665137wrg.65.2019.10.10.09.13.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:45 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:45 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:32 GMT Message-Id: <21a36efd7bc405ea01be8ecfd9775ebdf68946ad.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 03/11] graph: reduce duplication in `graph_insert_into_new_columns()` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan I will shortly be making some changes to this function and so am trying to simplify it. It currently contains some duplicated logic; both branches the function can take assign the commit's column index into the `mapping` array and increment `mapping_index`. Here I change the function so that the only conditional behaviour is that it appends the commit to `new_columns` if it's not present. All manipulation of `mapping` now happens on a single code path. Signed-off-by: James Coglan --- graph.c | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) diff --git a/graph.c b/graph.c index a890c9d8bb..1cd30f80e6 100644 --- a/graph.c +++ b/graph.c @@ -459,23 +459,17 @@ static void graph_insert_into_new_columns(struct git_graph *graph, int i = graph_find_new_column_by_commit(graph, commit); /* - * If the commit is already in the new_columns list, we don't need to - * add it. Just update the mapping correctly. + * If the commit is not already in the new_columns array, then add it + * and record it as being in the final column. */ - if (i >= 0) { - graph->mapping[*mapping_index] = i; - *mapping_index += 2; - return; + if (i < 0) { + i = graph->num_new_columns++; + graph->new_columns[i].commit = commit; + graph->new_columns[i].color = graph_find_commit_color(graph, commit); } - /* - * This commit isn't already in new_columns. Add it. - */ - graph->new_columns[graph->num_new_columns].commit = commit; - graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit); - graph->mapping[*mapping_index] = graph->num_new_columns; + graph->mapping[*mapping_index] = i; *mapping_index += 2; - graph->num_new_columns++; } static void graph_update_width(struct git_graph *graph, From patchwork Thu Oct 10 16:13:46 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183899 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2648113BD for ; Thu, 10 Oct 2019 16:13:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id F0D9920B7C for ; Thu, 10 Oct 2019 16:13:51 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ouYXrz/U" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726230AbfJJQNu (ORCPT ); Thu, 10 Oct 2019 12:13:50 -0400 Received: from mail-wm1-f65.google.com ([209.85.128.65]:34881 "EHLO mail-wm1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725978AbfJJQNs (ORCPT ); Thu, 10 Oct 2019 12:13:48 -0400 Received: by mail-wm1-f65.google.com with SMTP id y21so7408495wmi.0 for ; Thu, 10 Oct 2019 09:13:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=W5QI22lTJFVbHqadkfJ+l8EwSQE3VlsI5z/yLetcA/E=; b=ouYXrz/Uf44T5PPGct3KZ/qLaqb9lmdrsNL3f7A3hzBpY54ZrN6hqvLyP31zVGXP0N 9Watf6xRashS1AXlDsKOdaIEhpJBdywAe0sBsyyy0Cil3G6hQ5QlI4M1wq5ioiX8N2CB qwfZ2fiGXQMg2hM6NfQ8BWrjVkqKSgxxda2bzrGEi2i98D1rxoNdKWkQuCrDtMO+rAs5 9HI851O3440Wtcaat0cF5qWuMZ7h35v8aLyaa/IozHwCIy6QxfxFANO5gd84ByqjnNtt ZynDHajt9Lojg13jeKSkb9wTPp9QANi37mLY+vkToD4K9SAqYm8oOQhAp3GlBSDxxjTN wagw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=W5QI22lTJFVbHqadkfJ+l8EwSQE3VlsI5z/yLetcA/E=; b=E/zyoO21zIq9mCCqhkeIS9cn6ESIXeEO0TWylDqg8buB2k3Pf7R6PfvvpCJN3ceQ2f cO2fFxU/+aZprjmuCntxE1G7HIQbOouD4KncOzYr2UxobsObuatntsztIzqZeve/DUkT 5sE6DjOUZk4FWJhJhb3Lh3Q0S0ChRFd1xefg97Tj6lMqW+X5xwOgloBHZ1SHkmDDlVNR P7oaWo3fP2o7EQ0Qaa02x0LqbP1iYGsJ/cR4JuSmBg82D5MQKncSaQQ+ovPqErv+HQn+ bzpRVmlQrYHQRCTT8Ree02El5yU+KIYITZdYEMNDJO+iqWRVPdUNTW8ydtMpkkF6bMXN bhMg== X-Gm-Message-State: APjAAAWexxmOYHHPSWoHmYUsI61YURfN/vRmqrrQw2U4trk9NhlvLghm acauO++wmRop/RzftPf4cEeYwBWQ X-Google-Smtp-Source: APXvYqwCWuHtTLBvBdcoEjO2SSpaQMcKgtQV2Q2HEXE69IZrDh/eoB1pP4/9Wv/wj4eAdlDkaqqMug== X-Received: by 2002:a1c:6a05:: with SMTP id f5mr5061593wmc.121.1570724026611; Thu, 10 Oct 2019 09:13:46 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id n1sm8759994wrg.67.2019.10.10.09.13.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:46 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:46 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:33 GMT Message-Id: <674b992371b791daa67a98aa157e5166b4e68037.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 04/11] graph: remove `mapping_idx` and `graph_update_width()` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan There's a duplication of logic between `graph_insert_into_new_columns()` and `graph_update_width()`. `graph_insert_into_new_columns()` is called repeatedly by `graph_update_columns()` with an `int *` that tracks the offset into the `mapping` array where we should write the next value. Each call to `graph_insert_into_new_columns()` effectively pushes one column index and one "null" value (-1) onto the `mapping` array and therefore increments `mapping_idx` by 2. `graph_update_width()` duplicates this process: the `width` of the graph is essentially the initial width of the `mapping` array before edges begin collapsing. The `graph_update_width()` function's logic effectively works out how many times `graph_insert_into_new_columns()` was called based on the relationship of the current commit to the rest of the graph. I'm about to make some changes that make the assignment of values into the `mapping` array more complicated. Rather than make `graph_update_width()` more complicated at the same time, we can simply remove this function and use `graph->width` to track the offset into the `mapping` array as we're building it. This removes the duplication and makes sure that `graph->width` is the same as the visual width of the `mapping` array once `graph_update_columns()` is complete. Signed-off-by: James Coglan --- graph.c | 65 +++++++++------------------------------------------------ 1 file changed, 10 insertions(+), 55 deletions(-) diff --git a/graph.c b/graph.c index 1cd30f80e6..a71ae5cd61 100644 --- a/graph.c +++ b/graph.c @@ -453,8 +453,7 @@ static int graph_find_new_column_by_commit(struct git_graph *graph, } static void graph_insert_into_new_columns(struct git_graph *graph, - struct commit *commit, - int *mapping_index) + struct commit *commit) { int i = graph_find_new_column_by_commit(graph, commit); @@ -468,50 +467,14 @@ static void graph_insert_into_new_columns(struct git_graph *graph, graph->new_columns[i].color = graph_find_commit_color(graph, commit); } - graph->mapping[*mapping_index] = i; - *mapping_index += 2; -} - -static void graph_update_width(struct git_graph *graph, - int is_commit_in_existing_columns) -{ - /* - * Compute the width needed to display the graph for this commit. - * This is the maximum width needed for any row. All other rows - * will be padded to this width. - * - * Compute the number of columns in the widest row: - * Count each existing column (graph->num_columns), and each new - * column added by this commit. - */ - int max_cols = graph->num_columns + graph->num_parents; - - /* - * Even if the current commit has no parents to be printed, it - * still takes up a column for itself. - */ - if (graph->num_parents < 1) - max_cols++; - - /* - * We added a column for the current commit as part of - * graph->num_parents. If the current commit was already in - * graph->columns, then we have double counted it. - */ - if (is_commit_in_existing_columns) - max_cols--; - - /* - * Each column takes up 2 spaces - */ - graph->width = max_cols * 2; + graph->mapping[graph->width] = i; + graph->width += 2; } static void graph_update_columns(struct git_graph *graph) { struct commit_list *parent; int max_new_columns; - int mapping_idx; int i, seen_this, is_commit_in_columns; /* @@ -544,6 +507,8 @@ static void graph_update_columns(struct git_graph *graph) for (i = 0; i < graph->mapping_size; i++) graph->mapping[i] = -1; + graph->width = 0; + /* * Populate graph->new_columns and graph->mapping * @@ -554,7 +519,6 @@ static void graph_update_columns(struct git_graph *graph) * supposed to end up after the collapsing is performed. */ seen_this = 0; - mapping_idx = 0; is_commit_in_columns = 1; for (i = 0; i <= graph->num_columns; i++) { struct commit *col_commit; @@ -568,7 +532,6 @@ static void graph_update_columns(struct git_graph *graph) } if (col_commit == graph->commit) { - int old_mapping_idx = mapping_idx; seen_this = 1; graph->commit_index = i; for (parent = first_interesting_parent(graph); @@ -583,21 +546,18 @@ static void graph_update_columns(struct git_graph *graph) !is_commit_in_columns) { graph_increment_column_color(graph); } - graph_insert_into_new_columns(graph, - parent->item, - &mapping_idx); + graph_insert_into_new_columns(graph, parent->item); } /* - * We always need to increment mapping_idx by at + * We always need to increment graph->width by at * least 2, even if it has no interesting parents. * The current commit always takes up at least 2 * spaces. */ - if (mapping_idx == old_mapping_idx) - mapping_idx += 2; + if (graph->num_parents == 0) + graph->width += 2; } else { - graph_insert_into_new_columns(graph, col_commit, - &mapping_idx); + graph_insert_into_new_columns(graph, col_commit); } } @@ -607,11 +567,6 @@ static void graph_update_columns(struct git_graph *graph) while (graph->mapping_size > 1 && graph->mapping[graph->mapping_size - 1] < 0) graph->mapping_size--; - - /* - * Compute graph->width for this commit - */ - graph_update_width(graph, is_commit_in_columns); } void graph_update(struct git_graph *graph, struct commit *commit) From patchwork Thu Oct 10 16:13:47 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183901 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 89D7814ED for ; Thu, 10 Oct 2019 16:13:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 69604208C3 for ; Thu, 10 Oct 2019 16:13:53 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="PYLaNmXP" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726268AbfJJQNv (ORCPT ); Thu, 10 Oct 2019 12:13:51 -0400 Received: from mail-wm1-f67.google.com ([209.85.128.67]:54567 "EHLO mail-wm1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726135AbfJJQNt (ORCPT ); Thu, 10 Oct 2019 12:13:49 -0400 Received: by mail-wm1-f67.google.com with SMTP id p7so7585975wmp.4 for ; Thu, 10 Oct 2019 09:13:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=i+n1jZ9IWq6XPPmNuBifZlMFmJSg+PMu0QvfLp0lz/U=; b=PYLaNmXPczryNJmMf0hSNr1C/a3aAS9V+nootvOsMdqGU0hahZI10ZiMxCXQk8zMEz Log43L1rOXqonRYFEqOopJxpZTqrOK3svACY2GykSos1JVHST4r7KakG6B1FS2dpb2Th nWK/85l7jI7d3N/QmgCyZ/ED1mDOgObcRi+ObmykZy9/1ePZEFfV50VWphpbqt33KPd5 y5DsYa5tplfZ1pApf8SSIN2WqUufk5kzrAGYAVIWRFb8gQAcMCry2xNsgoWrFHrzSPwc yiFoc9VcXcfCCm1JUCXejYQXssCbWU5LbyVpmAGnExu5meNYc1gL6XcfvA+TlVx5oAI1 6NYg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=i+n1jZ9IWq6XPPmNuBifZlMFmJSg+PMu0QvfLp0lz/U=; b=SEHLCquw15T9a9sQal4+P+hows3UjKwBGxJiq7FnaIGJkXAsy/b0spP2uM3lfkprNr NcTJ1oc04kWERLn8txroDPbqZ+P8LTjEI/qPnLFXRakvx2owzcd/CpwD/QuZlUiC6IrN BgnPjA+NdB5VPlVeyFzANqP+XqpYtpAbI0VlKg8lzNenZ9zySqrhppmZA6y1MiWeck0e T2bz2KADrFrXQMZwLGJ/wA/xjleEjt7Q180//gVAZCMNl0rbDCNDbZU2KJ80+dwYdzSo ddYG4XNQZ9+wv9aq8lfo302EylHoEE23woePAs870qwDolvYrAcDdQxg/ODhmB5qsiBA u+tQ== X-Gm-Message-State: APjAAAWAiXz6H3SYycWqImfEMNM38bUpQcIXegrc1iu7DWof1D49lvH8 XsnjPjW9kb6hrRbNlerkfmpTYDKj X-Google-Smtp-Source: APXvYqwEASdq67akpYN0eFsP9jplqBJHTEfHRwhosYQAvC1Dyq3iSLxcGHlpg9fQ+lqm6gJ9+QNnug== X-Received: by 2002:a05:600c:143:: with SMTP id w3mr7778405wmm.35.1570724027437; Thu, 10 Oct 2019 09:13:47 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i5sm4460516wmd.21.2019.10.10.09.13.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:47 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:47 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:34 GMT Message-Id: In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 05/11] graph: extract logic for moving to GRAPH_PRE_COMMIT state Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan This computation is repeated in a couple of places and I need to add another condition to it to implement a further improvement to the graph rendering, so I'm extracting this into a function. Signed-off-by: James Coglan --- graph.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/graph.c b/graph.c index a71ae5cd61..98e8777db4 100644 --- a/graph.c +++ b/graph.c @@ -569,6 +569,12 @@ static void graph_update_columns(struct git_graph *graph) graph->mapping_size--; } +static int graph_needs_pre_commit_line(struct git_graph *graph) +{ + return graph->num_parents >= 3 && + graph->commit_index < (graph->num_columns - 1); +} + void graph_update(struct git_graph *graph, struct commit *commit) { struct commit_list *parent; @@ -624,8 +630,7 @@ void graph_update(struct git_graph *graph, struct commit *commit) */ if (graph->state != GRAPH_PADDING) graph->state = GRAPH_SKIP; - else if (graph->num_parents >= 3 && - graph->commit_index < (graph->num_columns - 1)) + else if (graph_needs_pre_commit_line(graph)) graph->state = GRAPH_PRE_COMMIT; else graph->state = GRAPH_COMMIT; @@ -708,8 +713,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb) strbuf_addstr(sb, "..."); graph_pad_horizontally(graph, sb); - if (graph->num_parents >= 3 && - graph->commit_index < (graph->num_columns - 1)) + if (graph_needs_pre_commit_line(graph)) graph_update_state(graph, GRAPH_PRE_COMMIT); else graph_update_state(graph, GRAPH_COMMIT); From patchwork Thu Oct 10 16:13:47 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183911 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 73FE814ED for ; Thu, 10 Oct 2019 16:14:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 4BFBC20B7C for ; Thu, 10 Oct 2019 16:14:00 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jAsP5939" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726323AbfJJQN5 (ORCPT ); Thu, 10 Oct 2019 12:13:57 -0400 Received: from mail-wr1-f67.google.com ([209.85.221.67]:42832 "EHLO mail-wr1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726187AbfJJQNw (ORCPT ); Thu, 10 Oct 2019 12:13:52 -0400 Received: by mail-wr1-f67.google.com with SMTP id n14so8586857wrw.9 for ; Thu, 10 Oct 2019 09:13:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=CNy1xTMHVsAy6mKLaIY8F8k2guin6Fxc9R6Rg30SXgY=; b=jAsP5939VaapDUL1Q7/XNyYgi7KuFXiTJkMaVcqV4zSElplV6eBz7B5IeTPJiOYTP3 Y4sROAJaQ2J83u2p5zqlrDdz+FY839W5TYmmWRMBn4g7wU0eYVCOqKW/Fxz0hOYjcTyn cv/YIg6kenQ1vU7zu0zHIuUT9cYBVpl0I/oiQnibUB8Ecn6yKWPbfIkpSjWOZe9mNIXr 3mR5KsxBSlnMfSJJvxDEQEHJJstgjNHr7Rbny8BOiZ9OcNmvLHA2pBn3E1201iM7AvJc 0LuY4/wCpEkanbwToBEqcvvseD2//V8O43FlM0DQ2GFl/1xstbey6nTnQa0iccPZaXrn S1Ig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=CNy1xTMHVsAy6mKLaIY8F8k2guin6Fxc9R6Rg30SXgY=; b=NThwu82+qRV5hYn1UyqsndM9CZG3RXLDCHP7qiOl8+2jze+Ub7ruFsVRQ+i4pTi5lY N11MsvttDzhmv3CE7Ii+6d0mARomFr/mNE9whOrJxahchdwjnQ1ySAM318TRha58qBdw eignpGXSqB2FxW0+uHfOZj0SZbX8bvJVFjvRHvrix13d+UiOAXVclMhkMK/5IfwNk6x1 RVop2Erz1TTdxVPm2RFrYMw7GeVBicNH8V7PfoLSNszuwlL469tRl9VEu7fgyx93AErT FjLNBvP9WoGxB6J6yCsLPqF2b+gjyS+YypxGvE9FaMNn2/eDilIXO6XNBzhYC3zFBxAJ dPzA== X-Gm-Message-State: APjAAAXwWAjYrsIQqIx3CVjmO9XbYgdP8R7xE6IVN7+dDafWvErshuGG xV4V6wf0SpbUz9d27HlAO0NJ6Zqx X-Google-Smtp-Source: APXvYqxVJYrwxGF5b4d/cos34Tf+ZLdLL5pStg/KLeBUicWxRyj8l6XtoSh1n65smRw7n6zo1GQxCg== X-Received: by 2002:a5d:4b09:: with SMTP id v9mr8825530wrq.127.1570724028246; Thu, 10 Oct 2019 09:13:48 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j18sm5751016wrs.85.2019.10.10.09.13.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:47 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:47 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:35 GMT Message-Id: <12c0916cb1ef033f917dc065cc1f18c0477296b8.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 06/11] graph: tidy up display of left-skewed merges Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan Currently, when we display a merge whose first parent is already present in a column to the left of the merge commit, we display the first parent as a veritcal pipe `|` in the GRAPH_POST_MERGE line and then immediately enter the GRAPH_COLLAPSING state. The first-parent line tracks to the left and all the other parent lines follow it; this creates a "kink" in those lines: | *---. | |\ \ \ |/ / / / | | | * This change tidies the display of such commits such that if the first parent appears to the left of the merge, we render it as a `/` and the second parent as a `|`. This reduces the horizontal and vertical space needed to render the merge, and makes the resulting lines easier to read. | *-. |/|\ \ | | | * If the first parent is separated from the merge by several columns, a horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING state displays the line. | | | *-. | |_|/|\ \ |/| | | | * This effect is applied to both "normal" two-parent merges, and to octopus merges. It also reduces the vertical space needed for pre-commit lines, as the merge occupies one less column than usual. Before: After: | * | * | |\ | |\ | | \ | * \ | | \ |/|\ \ | *-. \ | |\ \ \ Signed-off-by: James Coglan --- graph.c | 125 +++++++++++++++++++++++++++-------- t/t4214-log-graph-octopus.sh | 10 ++- t/t4215-log-skewed-merges.sh | 42 ++++++++++++ 3 files changed, 143 insertions(+), 34 deletions(-) create mode 100755 t/t4215-log-skewed-merges.sh diff --git a/graph.c b/graph.c index 98e8777db4..9136173e03 100644 --- a/graph.c +++ b/graph.c @@ -183,6 +183,20 @@ struct git_graph { * previous commit. */ int prev_commit_index; + /* + * Which layout variant to use to display merge commits. If the + * commit's first parent is known to be in a column to the left of the + * merge, then this value is 0 and we use the layout on the left. + * Otherwise, the value is 1 and the layout on the right is used. This + * field tells us how many columns the first parent occupies. + * + * 0) 1) + * + * | | | *-. | | *---. + * | |_|/|\ \ | | |\ \ \ + * |/| | | | | | | | | | * + */ + int merge_layout; /* * The maximum number of columns that can be stored in the columns * and new_columns arrays. This is also half the number of entries @@ -294,6 +308,7 @@ struct git_graph *graph_init(struct rev_info *opt) graph->prev_state = GRAPH_PADDING; graph->commit_index = 0; graph->prev_commit_index = 0; + graph->merge_layout = 0; graph->num_columns = 0; graph->num_new_columns = 0; graph->mapping_size = 0; @@ -453,9 +468,11 @@ static int graph_find_new_column_by_commit(struct git_graph *graph, } static void graph_insert_into_new_columns(struct git_graph *graph, - struct commit *commit) + struct commit *commit, + int idx) { int i = graph_find_new_column_by_commit(graph, commit); + int mapping_idx; /* * If the commit is not already in the new_columns array, then add it @@ -467,8 +484,26 @@ static void graph_insert_into_new_columns(struct git_graph *graph, graph->new_columns[i].color = graph_find_commit_color(graph, commit); } - graph->mapping[graph->width] = i; - graph->width += 2; + if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) { + /* + * If this is the first parent of a merge, choose a layout for + * the merge line based on whether the parent appears in a + * column to the left of the merge + */ + int dist, shift; + + dist = idx - i; + shift = (dist > 1) ? 2 * dist - 3 : 1; + + graph->merge_layout = (dist > 0) ? 0 : 1; + mapping_idx = graph->width + (graph->merge_layout - 1) * shift; + graph->width += 2 * graph->merge_layout; + } else { + mapping_idx = graph->width; + graph->width += 2; + } + + graph->mapping[mapping_idx] = i; } static void graph_update_columns(struct git_graph *graph) @@ -534,6 +569,7 @@ static void graph_update_columns(struct git_graph *graph) if (col_commit == graph->commit) { seen_this = 1; graph->commit_index = i; + graph->merge_layout = -1; for (parent = first_interesting_parent(graph); parent; parent = next_interesting_parent(graph, parent)) { @@ -546,7 +582,7 @@ static void graph_update_columns(struct git_graph *graph) !is_commit_in_columns) { graph_increment_column_color(graph); } - graph_insert_into_new_columns(graph, parent->item); + graph_insert_into_new_columns(graph, parent->item, i); } /* * We always need to increment graph->width by at @@ -557,7 +593,7 @@ static void graph_update_columns(struct git_graph *graph) if (graph->num_parents == 0) graph->width += 2; } else { - graph_insert_into_new_columns(graph, col_commit); + graph_insert_into_new_columns(graph, col_commit, -1); } } @@ -569,10 +605,36 @@ static void graph_update_columns(struct git_graph *graph) graph->mapping_size--; } +static int graph_num_expansion_rows(struct git_graph *graph) +{ + /* + * Normally, we need two expansion rows for each dashed parent line from + * an octopus merge: + * + * | * + * | |\ + * | | \ + * | | \ + * | *-. \ + * | |\ \ \ + * + * If the merge is skewed to the left, then its parents occupy one less + * column, and we don't need as many expansion rows to route around it; + * in some cases that means we don't need any expansion rows at all: + * + * | * + * | |\ + * | * \ + * |/|\ \ + */ + return (graph->num_parents + graph->merge_layout - 3) * 2; +} + static int graph_needs_pre_commit_line(struct git_graph *graph) { return graph->num_parents >= 3 && - graph->commit_index < (graph->num_columns - 1); + graph->commit_index < (graph->num_columns - 1) && + graph->expansion_row < graph_num_expansion_rows(graph); } void graph_update(struct git_graph *graph, struct commit *commit) @@ -722,7 +784,6 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb) static void graph_output_pre_commit_line(struct git_graph *graph, struct strbuf *sb) { - int num_expansion_rows; int i, seen_this; /* @@ -733,14 +794,13 @@ static void graph_output_pre_commit_line(struct git_graph *graph, * We need 2 extra rows for every parent over 2. */ assert(graph->num_parents >= 3); - num_expansion_rows = (graph->num_parents - 2) * 2; /* * graph->expansion_row tracks the current expansion row we are on. * It should be in the range [0, num_expansion_rows - 1] */ assert(0 <= graph->expansion_row && - graph->expansion_row < num_expansion_rows); + graph->expansion_row < graph_num_expansion_rows(graph)); /* * Output the row @@ -782,7 +842,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph, * and move to state GRAPH_COMMIT if necessary */ graph->expansion_row++; - if (graph->expansion_row >= num_expansion_rows) + if (!graph_needs_pre_commit_line(graph)) graph_update_state(graph, GRAPH_COMMIT); } @@ -820,7 +880,7 @@ static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb) * x 0 1 2 3 * */ - const int dashless_parents = 2; + const int dashless_parents = 3 - graph->merge_layout; int dashful_parents = graph->num_parents - dashless_parents; /* @@ -828,9 +888,9 @@ static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb) * above) but sometimes the first parent goes into an existing column, * like this: * - * | *---. - * | |\ \ \ - * |/ / / / + * | *-. + * |/|\ \ + * | | | | * x 0 1 2 * * In which case the number of parents will be one greater than the @@ -923,10 +983,15 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) graph_update_state(graph, GRAPH_COLLAPSING); } +const char merge_chars[] = {'/', '|', '\\'}; + static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) { int seen_this = 0; - int i, j; + int i; + + struct commit_list *first_parent = first_interesting_parent(graph); + int seen_parent = 0; /* * Output the post-merge row @@ -949,30 +1014,34 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf * new_columns and use those to format the * edges. */ - struct commit_list *parents = NULL; + struct commit_list *parents = first_parent; int par_column; + int idx = graph->merge_layout; + char c; seen_this = 1; - parents = first_interesting_parent(graph); - assert(parents); - par_column = graph_find_new_column_by_commit(graph, parents->item); - assert(par_column >= 0); - - strbuf_write_column(sb, &graph->new_columns[par_column], '|'); - for (j = 0; j < graph->num_parents - 1; j++) { - parents = next_interesting_parent(graph, parents); - assert(parents); + + for (; parents; parents = next_interesting_parent(graph, parents)) { par_column = graph_find_new_column_by_commit(graph, parents->item); assert(par_column >= 0); - strbuf_write_column(sb, &graph->new_columns[par_column], '\\'); - strbuf_addch(sb, ' '); + + c = merge_chars[idx]; + strbuf_write_column(sb, &graph->new_columns[par_column], c); + if (idx == 2) + strbuf_addch(sb, ' '); + else + idx++; } } else if (seen_this) { strbuf_write_column(sb, col, '\\'); strbuf_addch(sb, ' '); } else { strbuf_write_column(sb, col, '|'); - strbuf_addch(sb, ' '); + if (graph->merge_layout != 0 || i != graph->commit_index - 1) + strbuf_addch(sb, seen_parent ? '_' : ' '); } + + if (col_commit == first_parent->item) + seen_parent = 1; } graph_pad_horizontally(graph, sb); diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh index dab96c89aa..40f420877b 100755 --- a/t/t4214-log-graph-octopus.sh +++ b/t/t4214-log-graph-octopus.sh @@ -7,9 +7,8 @@ test_description='git log --graph of skewed left octopus merge.' test_expect_success 'set up merge history' ' cat >expect.uncolored <<-\EOF && * left - | *---. octopus-merge - | |\ \ \ - |/ / / / + | *-. octopus-merge + |/|\ \ | | | * 4 | | * | 3 | | |/ @@ -21,9 +20,8 @@ test_expect_success 'set up merge history' ' EOF cat >expect.colors <<-\EOF && * left - | *---. octopus-merge - | |\ \ \ - |/ / / / + | *-. octopus-merge + |/|\ \ | | | * 4 | | * | 3 | | |/ diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh new file mode 100755 index 0000000000..cfaba40f97 --- /dev/null +++ b/t/t4215-log-skewed-merges.sh @@ -0,0 +1,42 @@ +#!/bin/sh + +test_description='git log --graph of skewed merges' + +. ./test-lib.sh + +test_expect_success 'setup left-skewed merge' ' + git checkout --orphan _a && test_commit A && + git branch _b && + git branch _c && + git branch _d && + git branch _e && + git checkout _b && test_commit B && + git checkout _c && test_commit C && + git checkout _d && test_commit D && + git checkout _e && git merge --no-ff _d -m E && + git checkout _a && git merge --no-ff _b _c _e -m F +' + +cat > expect <<\EOF +*---. F +|\ \ \ +| | | * E +| |_|/| +|/| | | +| | | * D +| |_|/ +|/| | +| | * C +| |/ +|/| +| * B +|/ +* A +EOF + +test_expect_success 'log --graph with left-skewed merge' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + +test_done From patchwork Thu Oct 10 16:13:48 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183909 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8EA8F14ED for ; Thu, 10 Oct 2019 16:13:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 66CF420B7C for ; Thu, 10 Oct 2019 16:13:59 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nv3N0eH+" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726349AbfJJQN5 (ORCPT ); Thu, 10 Oct 2019 12:13:57 -0400 Received: from mail-wr1-f47.google.com ([209.85.221.47]:45729 "EHLO mail-wr1-f47.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726208AbfJJQNw (ORCPT ); Thu, 10 Oct 2019 12:13:52 -0400 Received: by mail-wr1-f47.google.com with SMTP id r5so8581433wrm.12 for ; Thu, 10 Oct 2019 09:13:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=wEsAG2dTQLAUtykvAFnYG6m1ONvIXRaMqC/2uDselDQ=; b=nv3N0eH+sFYBcAh1tTLBdPHC30tBKENnNM6xIm59UmIwdwBWJcjHrb107C3B9xCHsF 2gEftUH1k9zSd03Y7ewHCC7bR9lCxS/GsPb6YBpM39s/hQregtIxj5aImtTPfRQ7koPi zBqyDS0gLV89K/+ulHclI759FJ1wHlVGaLsd8CeIHROQ2eVQFt14MkRKuLVCqtjnsEvO lrtrksqtuPcbp7Jnby38H623T2ewPJqIKvJK61fGAalwA7y5Sf3whShUG96ogZshzqFS HabVjGly/oCE12ngqT1sineuhB+MueXG6vmcw1Ri3AhyCyZ3PxpCICNlyhbqnRqT27HA l2+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=wEsAG2dTQLAUtykvAFnYG6m1ONvIXRaMqC/2uDselDQ=; b=gvE+GT/maCGv9FREroW/X0NmTQoJBgsoRCq7eCN8kPO6bxrwkZBmSfou4ZJ8qjsbe7 OL8IsrNzp1QE6WUtggZZXuG+/+unk9jdNBipk2fsck3Erw+q0ZyeyTLNqNvACtrVN0yW wI6xAve0/4BnmY1hy96Ro0WBB+9ij9yuiH4Sq2hQELOgpBzUmH3UhBgRy726+nZmLMRu Ol8ZGsNvC/aG+pO+ZWLg373Fx4rF+Z42JcsrUE4Yk3uAb8eE5Y39C7BCL7VmrCdqdabE kmSGaWPA6wleE9nX8wYnUUGfZEHnUOayN4ePJ5Xy0e/NkWYCnWMLr72YIxtrjBAWWFYd g0Hg== X-Gm-Message-State: APjAAAVDw6+yfgaJ9Lk9GmLpHj1JgKFNwEjyfjIILk38gB0ZYpY2ddz9 HMWDlt3mMaOw44KXyanAEWVRreX5 X-Google-Smtp-Source: APXvYqyE07UQzTk5TZPtmo/P3840A+CpFKksJrPd0e4wRbN535tTUe6OGXf6QkpKg8SCzdIhjTmB5g== X-Received: by 2002:a5d:6342:: with SMTP id b2mr500534wrw.6.1570724029437; Thu, 10 Oct 2019 09:13:49 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j26sm8947620wrd.2.2019.10.10.09.13.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:48 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:48 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:36 GMT Message-Id: <6c173663aac37f1d314db8637cf4a243066b8078.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 07/11] graph: commit and post-merge lines for left-skewed merges Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan Following the introduction of "left-skewed" merges, which are merges whose first parent fuses with another edge to its left, we have some more edge cases to deal with in the display of commit and post-merge lines. The current graph code handles the following cases for edges appearing to the right of the commit (*) on commit lines. A 2-way merge is usually followed by vertical lines: | | | | * | | |\ \ An octopus merge (more than two parents) is always followed by edges sloping to the right: | | \ | | \ | *-. \ | *---. \ | |\ \ \ | |\ \ \ \ A 2-way merge is followed by a right-sloping edge if the commit line immediately follows a post-merge line for a commit that appears in the same column as the current commit, or any column to the left of that: | * | * | | |\ | |\ \ | * \ | | * \ | |\ \ | | |\ \ This commit introduces the following new cases for commit lines. If a 2-way merge skews to the left, then the edges to its right are always vertical lines, even if the commit follows a post-merge line: | | | | |\ | * | | * | |/| | |/| | A commit with 3 parents that skews left is followed by vertical edges: | | | | * | |/|\ \ If a 3-way left-skewed merge commit appears immediately after a post-merge line, then it may be followed the right-sloping edges, just like a 2-way merge that is not skewed. | |\ | * \ |/|\ \ Octopus merges with 4 or more parents that skew to the left will always be followed by right-sloping edges, because the existing columns need to expand around the merge. | | \ | *-. \ |/|\ \ \ On post-merge lines, usually all edges following the current commit slope to the right: | * | | | |\ \ \ However, if the commit is a left-skewed 2-way merge, the edges to its right remain vertical. We also need to display a space after the vertical line descending from the commit marker, whereas this line would normally be followed by a backslash. | * | | |/| | | If a left-skewed merge has more than 2 parents, then the edges to its right are still sloped as they bend around the edges introduced by the merge. | * | | |/|\ \ \ To handle these new cases, we need to know not just how many parents each commit has, but how many new columns it adds to the display; this quantity is recorded in the `edges_added` field for the current commit, and `prev_edges_added` field for the previous commit. Here, "column" refers to visual columns, not the logical columns of the `columns` array. This is because even if all the commit's parents end up fusing with existing edges, they initially introduce distinct edges in the commit and post-merge lines before those edges collapse. For example, a 3-way merge whose 2nd and 3rd parents fuse with existing edges still introduces 2 visual columns that affect the display of edges to their right. | | | \ | | *-. \ | | |\ \ \ | |_|/ / / |/| | / / | | |/ / | |/| | | | | | This merge does not introduce any *logical* columns; there are 4 edges before and after this commit once all edges have collapsed. But it does initially introduce 2 new edges that need to be accommodated by the edges to their right. Signed-off-by: James Coglan --- graph.c | 63 +++++++++++++-- t/t4215-log-skewed-merges.sh | 151 +++++++++++++++++++++++++++++++++++ 2 files changed, 209 insertions(+), 5 deletions(-) diff --git a/graph.c b/graph.c index 9136173e03..fb2e42850f 100644 --- a/graph.c +++ b/graph.c @@ -197,6 +197,46 @@ struct git_graph { * |/| | | | | | | | | | * */ int merge_layout; + /* + * The number of columns added to the graph by the current commit. For + * 2-way and octopus merges, this is is usually one less than the + * number of parents: + * + * | | | | | \ + * | * | | *---. \ + * | |\ \ | |\ \ \ \ + * | | | | | | | | | | + * + * num_parents: 2 num_parents: 4 + * edges_added: 1 edges_added: 3 + * + * For left-skewed merges, the first parent fuses with its neighbor and + * so one less column is added: + * + * | | | | | \ + * | * | | *-. \ + * |/| | |/|\ \ \ + * | | | | | | | | + * + * num_parents: 2 num_parents: 4 + * edges_added: 0 edges_added: 2 + * + * This number determines how edges to the right of the merge are + * displayed in commit and post-merge lines; if no columns have been + * added then a vertical line should be used where a right-tracking + * line would otherwise be used. + * + * | * \ | * | + * | |\ \ |/| | + * | | * \ | * | + */ + int edges_added; + /* + * The number of columns added by the previous commit, which is used to + * smooth edges appearing to the right of a commit in a commit line + * following a post-merge line. + */ + int prev_edges_added; /* * The maximum number of columns that can be stored in the columns * and new_columns arrays. This is also half the number of entries @@ -309,6 +349,8 @@ struct git_graph *graph_init(struct rev_info *opt) graph->commit_index = 0; graph->prev_commit_index = 0; graph->merge_layout = 0; + graph->edges_added = 0; + graph->prev_edges_added = 0; graph->num_columns = 0; graph->num_new_columns = 0; graph->mapping_size = 0; @@ -670,6 +712,9 @@ void graph_update(struct git_graph *graph, struct commit *commit) */ graph_update_columns(graph); + graph->prev_edges_added = graph->edges_added; + graph->edges_added = graph->num_parents + graph->merge_layout - 2; + graph->expansion_row = 0; /* @@ -943,12 +988,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) if (graph->num_parents > 2) graph_draw_octopus_merge(graph, sb); - } else if (seen_this && (graph->num_parents > 2)) { + } else if (seen_this && (graph->edges_added > 1)) { strbuf_write_column(sb, col, '\\'); - } else if (seen_this && (graph->num_parents == 2)) { + } else if (seen_this && (graph->edges_added == 1)) { /* - * This is a 2-way merge commit. - * There is no GRAPH_PRE_COMMIT stage for 2-way + * This is either a right-skewed 2-way merge + * commit, or a left-skewed 3-way merge. + * There is no GRAPH_PRE_COMMIT stage for such * merges, so this is the first line of output * for this commit. Check to see what the previous * line of output was. @@ -960,6 +1006,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) * makes the output look nicer. */ if (graph->prev_state == GRAPH_POST_MERGE && + graph->prev_edges_added > 0 && graph->prev_commit_index < i) strbuf_write_column(sb, col, '\\'); else @@ -1031,8 +1078,14 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf else idx++; } + if (graph->edges_added == 0) + strbuf_addch(sb, ' '); + } else if (seen_this) { - strbuf_write_column(sb, col, '\\'); + if (graph->edges_added > 0) + strbuf_write_column(sb, col, '\\'); + else + strbuf_write_column(sb, col, '|'); strbuf_addch(sb, ' '); } else { strbuf_write_column(sb, col, '|'); diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh index cfaba40f97..e479d6e676 100755 --- a/t/t4215-log-skewed-merges.sh +++ b/t/t4215-log-skewed-merges.sh @@ -39,4 +39,155 @@ test_expect_success 'log --graph with left-skewed merge' ' test_cmp expect actual ' +test_expect_success 'setup nested left-skewed merge' ' + git checkout --orphan 1_p && + test_commit 1_A && + test_commit 1_B && + test_commit 1_C && + git checkout -b 1_q @^ && test_commit 1_D && + git checkout 1_p && git merge --no-ff 1_q -m 1_E && + git checkout -b 1_r @~3 && test_commit 1_F && + git checkout 1_p && git merge --no-ff 1_r -m 1_G && + git checkout @^^ && git merge --no-ff 1_p -m 1_H +' + +cat > expect <<\EOF +* 1_H +|\ +| * 1_G +| |\ +| | * 1_F +| * | 1_E +|/| | +| * | 1_D +* | | 1_C +|/ / +* | 1_B +|/ +* 1_A +EOF + +test_expect_success 'log --graph with nested left-skewed merge' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + +test_expect_success 'setup nested left-skewed merge following normal merge' ' + git checkout --orphan 2_p && + test_commit 2_A && + test_commit 2_B && + test_commit 2_C && + git checkout -b 2_q @^^ && + test_commit 2_D && + test_commit 2_E && + git checkout -b 2_r @^ && test_commit 2_F && + git checkout 2_q && + git merge --no-ff 2_r -m 2_G && + git merge --no-ff 2_p^ -m 2_H && + git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J && + git checkout 2_p && git merge --no-ff 2_s -m 2_K +' + +cat > expect <<\EOF +* 2_K +|\ +| * 2_J +| |\ +| | * 2_H +| | |\ +| | * | 2_G +| |/| | +| | * | 2_F +| * | | 2_E +| |/ / +| * | 2_D +* | | 2_C +| |/ +|/| +* | 2_B +|/ +* 2_A +EOF + +test_expect_success 'log --graph with nested left-skewed merge following normal merge' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + +test_expect_success 'setup nested right-skewed merge following left-skewed merge' ' + git checkout --orphan 3_p && + test_commit 3_A && + git checkout -b 3_q && + test_commit 3_B && + test_commit 3_C && + git checkout -b 3_r @^ && + test_commit 3_D && + git checkout 3_q && git merge --no-ff 3_r -m 3_E && + git checkout 3_p && git merge --no-ff 3_q -m 3_F && + git checkout 3_r && test_commit 3_G && + git checkout 3_p && git merge --no-ff 3_r -m 3_H && + git checkout @^^ && git merge --no-ff 3_p -m 3_J +' + +cat > expect <<\EOF +* 3_J +|\ +| * 3_H +| |\ +| | * 3_G +| * | 3_F +|/| | +| * | 3_E +| |\ \ +| | |/ +| | * 3_D +| * | 3_C +| |/ +| * 3_B +|/ +* 3_A +EOF + +test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + +test_expect_success 'setup right-skewed merge following a left-skewed one' ' + git checkout --orphan 4_p && + test_commit 4_A && + test_commit 4_B && + test_commit 4_C && + git checkout -b 4_q @^^ && test_commit 4_D && + git checkout -b 4_r 4_p^ && git merge --no-ff 4_q -m 4_E && + git checkout -b 4_s 4_p^^ && + git merge --no-ff 4_r -m 4_F && + git merge --no-ff 4_p -m 4_G && + git checkout @^^ && git merge --no-ff 4_s -m 4_H +' + +cat > expect <<\EOF +* 4_H +|\ +| * 4_G +| |\ +| * | 4_F +|/| | +| * | 4_E +| |\ \ +| | * | 4_D +| |/ / +|/| | +| | * 4_C +| |/ +| * 4_B +|/ +* 4_A +EOF + +test_expect_success 'log --graph with right-skewed merge following a left-skewed one' ' + git log --graph --date-order --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + test_done From patchwork Thu Oct 10 16:13:49 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183903 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8B34114ED for ; Thu, 10 Oct 2019 16:13:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 635DA20B7C for ; Thu, 10 Oct 2019 16:13:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="s+7tAzNg" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726317AbfJJQN4 (ORCPT ); Thu, 10 Oct 2019 12:13:56 -0400 Received: from mail-wr1-f65.google.com ([209.85.221.65]:33105 "EHLO mail-wr1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725978AbfJJQNx (ORCPT ); Thu, 10 Oct 2019 12:13:53 -0400 Received: by mail-wr1-f65.google.com with SMTP id b9so8655790wrs.0 for ; Thu, 10 Oct 2019 09:13:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=PzlKoMI1Emv7Fk2J7CVEN01D82qCeV2EyySb3bZ+Dx8=; b=s+7tAzNg/HxDeaIuyHxaB2Tdu712R+Xzq72WGQR97p1yfmdDJZ+ZUgNJ+DjXubS0oN juGNGWBNCnPuHTxeLYlHlA21A0CiYvSH+jFJuGeyAV2giyvvUokVgN29jjK09blnEddC iDeROGB4KbgBTYfIPWLiaEyzUA+pILqUiCauIFiT/tUuHcomr2Lg2DK0GjEjwW8TblMY ctpqNdRIDVFf9RoMQiUJYlAzetHBP6lX9fD0glAQ6DQBA4xQly2zXjvQV62VRNaB8sX7 H3Jtqm/oRIOyRRttk6pnHGADyLygVuXxyaZZVPbhK0JoA9FTw9gW3vaBNgWmGDPNXVxG sjMw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=PzlKoMI1Emv7Fk2J7CVEN01D82qCeV2EyySb3bZ+Dx8=; b=r8FnzYyvzR1PzuLU0LEwYvAsjpkbG+dqpvNtOWJ2crK5wW4Jm/JyhB5F3THedK1SL2 M6kAkjTwju2WvQMlQiYsPjD2cjBDhEwfUOB2AMcplc/Zabwgs5NqpURODCTI886BSEV4 9X36Pe6bd6C6E2Jq2jvMfHBXmockk8AyQ7RVQwcSX8GLuj5cUDDC3ztOvFCsRr1SWSAI exSaD01vW4J2LLxZlnfmDU518C86D3WrZ/0aaz63EzF4PhfkQ8JdHMQNp2kwtdcithdm +b/1vcUHnA5ERJY4lKstpCO112OPNCF+YJJW/oY6B1pqDfHoWBCuo8PwCq5qKNCgEA5d nvjw== X-Gm-Message-State: APjAAAV1KCTTk2voZfOPWhwXJlaU6gvzioCryDksyeJaMnU0LcM+hkwd 1sge7XJliYdOkijVlyU5lucgEw4X X-Google-Smtp-Source: APXvYqyV9lBZC5hBS8SeMNQ/qSsLHNYonIDxiWWoUwiil9wzHRF2TjoiiKkgLtIoM5qCjTx3PDfoWQ== X-Received: by 2002:a5d:5646:: with SMTP id j6mr877546wrw.396.1570724030434; Thu, 10 Oct 2019 09:13:50 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w18sm7076198wmc.9.2019.10.10.09.13.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:49 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:49 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:37 GMT Message-Id: <23f13bbefaaccde4b914813a0ab7965ab1f83c04.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 08/11] graph: rename `new_mapping` to `old_mapping` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan The change I'm about to make requires being able to inspect the mapping array that was used to render the last GRAPH_COLLAPSING line while rendering a GRAPH_COMMIT line. The `new_mapping` array currently exists as a pre-allocated space for computing the next `mapping` array during `graph_output_collapsing_line()`, but we can repurpose it to let us see the previous `mapping` state. To support this use it will make more sense if this array is named `old_mapping`, as it will contain the mapping data for the previous line we rendered, at the point we're rendering a commit line. Signed-off-by: James Coglan --- graph.c | 54 +++++++++++++++++++++++++++--------------------------- 1 file changed, 27 insertions(+), 27 deletions(-) diff --git a/graph.c b/graph.c index fb2e42850f..b0e31e23ca 100644 --- a/graph.c +++ b/graph.c @@ -240,7 +240,7 @@ struct git_graph { /* * The maximum number of columns that can be stored in the columns * and new_columns arrays. This is also half the number of entries - * that can be stored in the mapping and new_mapping arrays. + * that can be stored in the mapping and old_mapping arrays. */ int column_capacity; /* @@ -283,7 +283,7 @@ struct git_graph { * of the git_graph simply so we don't have to allocate a new * temporary array each time we have to output a collapsing line. */ - int *new_mapping; + int *old_mapping; /* * The current default column color being used. This is * stored as an index into the array column_colors. @@ -369,7 +369,7 @@ struct git_graph *graph_init(struct rev_info *opt) ALLOC_ARRAY(graph->columns, graph->column_capacity); ALLOC_ARRAY(graph->new_columns, graph->column_capacity); ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity); - ALLOC_ARRAY(graph->new_mapping, 2 * graph->column_capacity); + ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity); /* * The diff output prefix callback, with this we can make @@ -399,7 +399,7 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns) REALLOC_ARRAY(graph->columns, graph->column_capacity); REALLOC_ARRAY(graph->new_columns, graph->column_capacity); REALLOC_ARRAY(graph->mapping, graph->column_capacity * 2); - REALLOC_ARRAY(graph->new_mapping, graph->column_capacity * 2); + REALLOC_ARRAY(graph->old_mapping, graph->column_capacity * 2); } /* @@ -1116,13 +1116,18 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf int horizontal_edge_target = -1; /* - * Clear out the new_mapping array + * Swap the mapping and old_mapping arrays + */ + SWAP(graph->mapping, graph->old_mapping); + + /* + * Clear out the mapping array */ for (i = 0; i < graph->mapping_size; i++) - graph->new_mapping[i] = -1; + graph->mapping[i] = -1; for (i = 0; i < graph->mapping_size; i++) { - int target = graph->mapping[i]; + int target = graph->old_mapping[i]; if (target < 0) continue; @@ -1143,14 +1148,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * This column is already in the * correct place */ - assert(graph->new_mapping[i] == -1); - graph->new_mapping[i] = target; - } else if (graph->new_mapping[i - 1] < 0) { + assert(graph->mapping[i] == -1); + graph->mapping[i] = target; + } else if (graph->mapping[i - 1] < 0) { /* * Nothing is to the left. * Move to the left by one */ - graph->new_mapping[i - 1] = target; + graph->mapping[i - 1] = target; /* * If there isn't already an edge moving horizontally * select this one. @@ -1166,9 +1171,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * line. */ for (j = (target * 2)+3; j < (i - 2); j += 2) - graph->new_mapping[j] = target; + graph->mapping[j] = target; } - } else if (graph->new_mapping[i - 1] == target) { + } else if (graph->mapping[i - 1] == target) { /* * There is a branch line to our left * already, and it is our target. We @@ -1176,7 +1181,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * the same parent commit. * * We don't have to add anything to the - * output or new_mapping, since the + * output or mapping, since the * existing branch line has already taken * care of it. */ @@ -1192,10 +1197,10 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * The branch to the left of that space * should be our eventual target. */ - assert(graph->new_mapping[i - 1] > target); - assert(graph->new_mapping[i - 2] < 0); - assert(graph->new_mapping[i - 3] == target); - graph->new_mapping[i - 2] = target; + assert(graph->mapping[i - 1] > target); + assert(graph->mapping[i - 2] < 0); + assert(graph->mapping[i - 3] == target); + graph->mapping[i - 2] = target; /* * Mark this branch as the horizontal edge to * prevent any other edges from moving @@ -1209,14 +1214,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf /* * The new mapping may be 1 smaller than the old mapping */ - if (graph->new_mapping[graph->mapping_size - 1] < 0) + if (graph->mapping[graph->mapping_size - 1] < 0) graph->mapping_size--; /* * Output out a line based on the new mapping info */ for (i = 0; i < graph->mapping_size; i++) { - int target = graph->new_mapping[i]; + int target = graph->mapping[i]; if (target < 0) strbuf_addch(sb, ' '); else if (target * 2 == i) @@ -1229,12 +1234,12 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf * won't continue into the next line. */ if (i != (target * 2)+3) - graph->new_mapping[i] = -1; + graph->mapping[i] = -1; used_horizontal = 1; strbuf_write_column(sb, &graph->new_columns[target], '_'); } else { if (used_horizontal && i < horizontal_edge) - graph->new_mapping[i] = -1; + graph->mapping[i] = -1; strbuf_write_column(sb, &graph->new_columns[target], '/'); } @@ -1242,11 +1247,6 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf graph_pad_horizontally(graph, sb); - /* - * Swap mapping and new_mapping - */ - SWAP(graph->mapping, graph->new_mapping); - /* * If graph->mapping indicates that all of the branch lines * are already in the correct positions, we are done. From patchwork Thu Oct 10 16:13:50 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183905 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 0743D13BD for ; Thu, 10 Oct 2019 16:13:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D2B85208C3 for ; Thu, 10 Oct 2019 16:13:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="E/UFOt1C" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726345AbfJJQN5 (ORCPT ); Thu, 10 Oct 2019 12:13:57 -0400 Received: from mail-wr1-f65.google.com ([209.85.221.65]:34962 "EHLO mail-wr1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726135AbfJJQNx (ORCPT ); Thu, 10 Oct 2019 12:13:53 -0400 Received: by mail-wr1-f65.google.com with SMTP id v8so8626842wrt.2 for ; Thu, 10 Oct 2019 09:13:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=sGTR1hTEKEfjsP+HPPTapknAXdH7GJypKgy9PgR3K5w=; b=E/UFOt1C/SCNdI3nPC1wyHkw6JiKQ/FMGQXdhXb9eu1URtSmCTPKlnj3IGdDxiXii+ QIEUqMkdUry7pnVSln0wTkuJDsMTr2gDxbdr/S67oZmWbXf4EfVqmmBp6HEpNw6/3thc nXt+8s7vdUlZolz4cuVUzc6dSVgeceGFRANgVonCy3zL/pabxcA3JargbS0VFBh4KTvM havlpHZFqj2ucXMXzmmMhOFOUuJnmk4BKeSpmqTnsdaBMzzSbvUytF8EZAE7tJPpj70y +dmPSLoxviscH/c8o6itPYY8RjQpO25LlMsr4aiRzkzsdw3+uRf5DGb8+PLZbJ9HuCws Vozg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=sGTR1hTEKEfjsP+HPPTapknAXdH7GJypKgy9PgR3K5w=; b=TDzfiZqNYtPE3lOQVLhjyDtsXTjIvTW9eivpuJZYeZeioGs13oZzI1C0MQCVnVpBBa ItMXjtm4R2KWS6odClocwN66pBDvx63DlGhGpJoBNu7YViKrXEf695O+pt9wLfWLVNVs 5S3V4uaL+PUsUuSKXLbqSqxhh9G+FVTyrq84fL3lT4yA5aA9K9f1y1lgwh8yqzsXhZNE sGoyjPk4/3Lj28P+X3h9Vftz804wnpninKvUQLh83/cbA2tYUOL0uVni8LzrUprY81v6 IDv/vwk5nYBta8g3bCYFZDY46ODqZvPvujQwODuYQw/94JPF7K7hlB6kn+EWcrhRHuKM zLww== X-Gm-Message-State: APjAAAUW9OBrCPYeUYa9OQVCZSqfuLOVXIULtMRa5nCEyhTwaBNSDCQ1 0zZ0yiFI4sS2GOmKJ3s9xxjxFPO9 X-Google-Smtp-Source: APXvYqxlRaPMpfQF/eTq2Yq00ygZLuFRsKsu8EKWdxdA7vX/pf5nHNm9hSrYgRu/aYUb/SGh/HK9jw== X-Received: by 2002:adf:e688:: with SMTP id r8mr9924041wrm.342.1570724031252; Thu, 10 Oct 2019 09:13:51 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j11sm7545928wrw.86.2019.10.10.09.13.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:50 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:50 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:38 GMT Message-Id: In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 09/11] graph: smooth appearance of collapsing edges on commit lines Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan When a graph contains edges that are in the process of collapsing to the left, but those edges cross a commit line, the effect is that the edges have a jagged appearance: * |\ | * | \ *-. \ |\ \ \ | | * | | * | | | |/ / * | | |/ / * | |/ * We already takes steps to smooth edges like this when they're expanding; when an edge appears to the right of a merge commit marker on a GRAPH_COMMIT line immediately following a GRAPH_POST_MERGE line, we render it as a `\`: * \ |\ \ | * \ | |\ \ We can make a similar improvement to collapsing edges, making them easier to follow and giving the overall graph a feeling of increased symmetry: * |\ | * | \ *-. \ |\ \ \ | | * | | * | | | |/ / * / / |/ / * / |/ * To do this, we introduce a new special case for edges on GRAPH_COMMIT lines that immediately follow a GRAPH_COLLAPSING line. By retaining a copy of the `mapping` array used to render the GRAPH_COLLAPSING line in the `old_mapping` array, we can determine that an edge is collapsing through the GRAPH_COMMIT line and should be smoothed. Signed-off-by: James Coglan --- graph.c | 17 +++++++++++++---- t/t3430-rebase-merges.sh | 2 +- t/t4202-log.sh | 2 +- t/t4214-log-graph-octopus.sh | 16 ++++++++-------- t/t4215-log-skewed-merges.sh | 2 +- t/t6016-rev-list-graph-simplify-history.sh | 4 ++-- 6 files changed, 26 insertions(+), 17 deletions(-) diff --git a/graph.c b/graph.c index b0e31e23ca..6391e393ec 100644 --- a/graph.c +++ b/graph.c @@ -278,10 +278,10 @@ struct git_graph { */ int *mapping; /* - * A temporary array for computing the next mapping state - * while we are outputting a mapping line. This is stored as part - * of the git_graph simply so we don't have to allocate a new - * temporary array each time we have to output a collapsing line. + * A copy of the contents of the mapping array from the last commit, + * which we use to improve the display of columns that are tracking + * from right to left through a commit line. We also use this to + * avoid allocating a fresh array when we compute the next mapping. */ int *old_mapping; /* @@ -1011,6 +1011,10 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) strbuf_write_column(sb, col, '\\'); else strbuf_write_column(sb, col, '|'); + } else if (graph->prev_state == GRAPH_COLLAPSING && + graph->old_mapping[2 * i + 1] == i && + graph->mapping[2 * i] < i) { + strbuf_write_column(sb, col, '/'); } else { strbuf_write_column(sb, col, '|'); } @@ -1211,6 +1215,11 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf } } + /* + * Copy the current mapping array into old_mapping + */ + COPY_ARRAY(graph->old_mapping, graph->mapping, graph->mapping_size); + /* * The new mapping may be 1 smaller than the old mapping */ diff --git a/t/t3430-rebase-merges.sh b/t/t3430-rebase-merges.sh index 7b6c4847ad..051351ecdf 100755 --- a/t/t3430-rebase-merges.sh +++ b/t/t3430-rebase-merges.sh @@ -402,7 +402,7 @@ test_expect_success 'octopus merges' ' | | * three | * | two | |/ - * | one + * / one |/ o before-octopus EOF diff --git a/t/t4202-log.sh b/t/t4202-log.sh index c20209324c..c7aa0532c1 100755 --- a/t/t4202-log.sh +++ b/t/t4202-log.sh @@ -667,7 +667,7 @@ cat > expect <<\EOF * | | fifth * | | fourth |/ / -* | third +* / third |/ * second * initial diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh index 40f420877b..9ada687628 100755 --- a/t/t4214-log-graph-octopus.sh +++ b/t/t4214-log-graph-octopus.sh @@ -12,9 +12,9 @@ test_expect_success 'set up merge history' ' | | | * 4 | | * | 3 | | |/ - | * | 2 + | * / 2 | |/ - * | 1 + * / 1 |/ * initial EOF @@ -25,9 +25,9 @@ test_expect_success 'set up merge history' ' | | | * 4 | | * | 3 | | |/ - | * | 2 + | * / 2 | |/ - * | 1 + * / 1 |/ * initial EOF @@ -68,9 +68,9 @@ test_expect_success 'log --graph with normal octopus merge, no color' ' | | | * 4 | | * | 3 | | |/ - | * | 2 + | * / 2 | |/ - * | 1 + * / 1 |/ * initial EOF @@ -86,9 +86,9 @@ test_expect_success 'log --graph with normal octopus merge with colors' ' | | | * 4 | | * | 3 | | |/ - | * | 2 + | * / 2 | |/ - * | 1 + * / 1 |/ * initial EOF diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh index e479d6e676..b739268e5e 100755 --- a/t/t4215-log-skewed-merges.sh +++ b/t/t4215-log-skewed-merges.sh @@ -62,7 +62,7 @@ cat > expect <<\EOF | * | 1_D * | | 1_C |/ / -* | 1_B +* / 1_B |/ * 1_A EOF diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh index f7181d1d6a..ca1682f29b 100755 --- a/t/t6016-rev-list-graph-simplify-history.sh +++ b/t/t6016-rev-list-graph-simplify-history.sh @@ -154,7 +154,7 @@ test_expect_success '--graph --full-history -- bar.txt' ' echo "* | $A4" >> expected && echo "|\\ \\ " >> expected && echo "| |/ " >> expected && - echo "* | $A3" >> expected && + echo "* / $A3" >> expected && echo "|/ " >> expected && echo "* $A2" >> expected && git rev-list --graph --full-history --all -- bar.txt > actual && @@ -255,7 +255,7 @@ test_expect_success '--graph --boundary ^C3' ' echo "* | | | $A3" >> expected && echo "o | | | $A2" >> expected && echo "|/ / / " >> expected && - echo "o | | $A1" >> expected && + echo "o / / $A1" >> expected && echo " / / " >> expected && echo "| o $C3" >> expected && echo "|/ " >> expected && From patchwork Thu Oct 10 16:13:51 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183913 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7DBAE13BD for ; Thu, 10 Oct 2019 16:14:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 553A3208C3 for ; Thu, 10 Oct 2019 16:14:01 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="MbCW5Bbb" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726291AbfJJQN4 (ORCPT ); Thu, 10 Oct 2019 12:13:56 -0400 Received: from mail-wr1-f67.google.com ([209.85.221.67]:34966 "EHLO mail-wr1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726276AbfJJQNz (ORCPT ); Thu, 10 Oct 2019 12:13:55 -0400 Received: by mail-wr1-f67.google.com with SMTP id v8so8626915wrt.2 for ; Thu, 10 Oct 2019 09:13:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=JK2inobb5zhUsTBE/QtcNCBJfbDIsr/OGF0HFkFqJrQ=; b=MbCW5BbbBbiniMOSWUTwLORBgoF2hnSZokJKXu65wJuqNFCdmava1jlBZZlI6Pt9kr 70kGktJbYTTLqLNxIZCyZx+E5HpHrRq28ifx05ijvxj1flg0R2zlZFYxGoD86RGGR78m V/ID43iKzr3jGbLb6x8ETrkuQ46R4ZgX7vC5hvrMydjp1t5YGnzvc1BUiEx0RILkdczK 6Zoij/vEYZRFXNSRy7X8cXxRue3oxPwIUAXXv7tSqHAnzSLaR1h/zTV/UIYsqC7ROF6S XLvfk3Ey7RGUYxDB3J5QCJKF8lgeWr3F3N4M08668G5ysDv1GFrPXpt5sFIn3F0++rRZ rSaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=JK2inobb5zhUsTBE/QtcNCBJfbDIsr/OGF0HFkFqJrQ=; b=hN38H4PlYgkUDUnNrwWPUtxbLaaZsMY9ASgOG7b0ykXtrpt716ujpD0uAc6U1uosMH VjVxp/HAENvDCDOt1wFZew1kcNCoE4F+Kg59MMhHMjqnotjA0cAenObf4MOiaCsDB/qS tZA37YbkKz0pMrjIVmriYBv3J+jXjROrkSKfTdOxinqqjsHcOTwKDnXN/v5b/2bDBWKY iRdp8GLPclAVUXY3g+3WkQSXGzt0gATr/dyVf4TYYa39GTTjsaGQoW/t1V0m3T45SoG0 XhPlGZYCEnFDMYsbyk8FIFmGszITd+YdCMXB4BWAmIftZsHLJuNQ/PvYeVNlYWl0qRk7 9SlA== X-Gm-Message-State: APjAAAUJdTUoEbVrTMz6UiclUniHItQrE02ZCGtYCUgON//D2KvxBCtk mw8N+88fIOA0VrNtJkX08KDxHJCM X-Google-Smtp-Source: APXvYqznvRoFaVZAPfoGSGlPcxixRKqU955/3WePmMcI7MMEGQVMEQnB2xQzC8dXs5g3Umj5oKSyIg== X-Received: by 2002:a5d:4ed2:: with SMTP id s18mr8893093wrv.52.1570724032107; Thu, 10 Oct 2019 09:13:52 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f18sm4236692wmh.43.2019.10.10.09.13.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:51 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:51 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:39 GMT Message-Id: <50756edcf7075b27b1ac0b0fb7af8688787bcd00.1570724021.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 10/11] graph: flatten edges that join to their right neighbor Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan When a merge commit is printed and its final parent is the same commit that occupies the column to the right of the merge, this results in a kink in the displayed edges: * | |\ \ | |/ | * Graphs containing these shapes can be hard to read, as the expansion to the right followed immediately by collapsing back to the left creates a lot of zig-zagging edges, especially when many columns are present. We can improve this by eliminating the zig-zag and having the merge's final parent edge fuse immediately with its neighbor: * | |\| | * This reduces the horizontal width for the current commit by 2, and requires one less row, making the graph display more compact. Taken in combination with other graph-smoothing enhancements, it greatly compresses the space needed to display certain histories: * |\ | * * | |\ |\ | | * | * | | | | |\ | | \ | | * | *-. \ | * | | |\ \ \ => |/|\| |/ / / / | | * | | | / | * | | | |/ | |/ | | * * / | * | |/ | |/ * * | |/ * One of the test cases here cannot be correctly rendered in Git v2.23.0; it produces this output following commit E: | | *-. \ 5_E | | |\ \ \ | |/ / / / | | | / _ | |_|/ |/| | The new implementation makes sure that the rightmost edge in this history is not left dangling as above. Signed-off-by: James Coglan --- graph.c | 34 ++++++--- t/t4215-log-skewed-merges.sh | 80 +++++++++++++++++++++- t/t6016-rev-list-graph-simplify-history.sh | 30 ++++---- 3 files changed, 116 insertions(+), 28 deletions(-) diff --git a/graph.c b/graph.c index 6391e393ec..7dd2fab625 100644 --- a/graph.c +++ b/graph.c @@ -538,8 +538,24 @@ static void graph_insert_into_new_columns(struct git_graph *graph, shift = (dist > 1) ? 2 * dist - 3 : 1; graph->merge_layout = (dist > 0) ? 0 : 1; + graph->edges_added = graph->num_parents + graph->merge_layout - 2; + mapping_idx = graph->width + (graph->merge_layout - 1) * shift; graph->width += 2 * graph->merge_layout; + + } else if (graph->edges_added > 0 && i == graph->mapping[graph->width - 2]) { + /* + * If some columns have been added by a merge, but this commit + * was found in the last existing column, then adjust the + * numbers so that the two edges immediately join, i.e.: + * + * * | * | + * |\ \ => |\| + * | |/ | * + * | * + */ + mapping_idx = graph->width - 2; + graph->edges_added = -1; } else { mapping_idx = graph->width; graph->width += 2; @@ -585,6 +601,8 @@ static void graph_update_columns(struct git_graph *graph) graph->mapping[i] = -1; graph->width = 0; + graph->prev_edges_added = graph->edges_added; + graph->edges_added = 0; /* * Populate graph->new_columns and graph->mapping @@ -712,9 +730,6 @@ void graph_update(struct git_graph *graph, struct commit *commit) */ graph_update_columns(graph); - graph->prev_edges_added = graph->edges_added; - graph->edges_added = graph->num_parents + graph->merge_layout - 2; - graph->expansion_row = 0; /* @@ -1039,7 +1054,7 @@ const char merge_chars[] = {'/', '|', '\\'}; static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb) { int seen_this = 0; - int i; + int i, j; struct commit_list *first_parent = first_interesting_parent(graph); int seen_parent = 0; @@ -1071,16 +1086,19 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf char c; seen_this = 1; - for (; parents; parents = next_interesting_parent(graph, parents)) { + for (j = 0; j < graph->num_parents; j++) { par_column = graph_find_new_column_by_commit(graph, parents->item); assert(par_column >= 0); c = merge_chars[idx]; strbuf_write_column(sb, &graph->new_columns[par_column], c); - if (idx == 2) - strbuf_addch(sb, ' '); - else + if (idx == 2) { + if (graph->edges_added > 0 || j < graph->num_parents - 1) + strbuf_addch(sb, ' '); + } else { idx++; + } + parents = next_interesting_parent(graph, parents); } if (graph->edges_added == 0) strbuf_addch(sb, ' '); diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh index b739268e5e..1481e6fd80 100755 --- a/t/t4215-log-skewed-merges.sh +++ b/t/t4215-log-skewed-merges.sh @@ -137,9 +137,8 @@ cat > expect <<\EOF | | * 3_G | * | 3_F |/| | -| * | 3_E -| |\ \ -| | |/ +| * | 3_E +| |\| | | * 3_D | * | 3_C | |/ @@ -190,4 +189,79 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed test_cmp expect actual ' +test_expect_success 'setup octopus merge with column joining its penultimate parent' ' + git checkout --orphan 5_p && + test_commit 5_A && + git branch 5_q && + git branch 5_r && + test_commit 5_B && + git checkout 5_q && test_commit 5_C && + git checkout 5_r && test_commit 5_D && + git checkout 5_p && + git merge --no-ff 5_q 5_r -m 5_E && + git checkout 5_q && test_commit 5_F && + git checkout -b 5_s 5_p^ && + git merge --no-ff 5_p 5_q -m 5_G && + git checkout 5_r && + git merge --no-ff 5_s -m 5_H +' + +cat > expect <<\EOF +* 5_H +|\ +| *-. 5_G +| |\ \ +| | | * 5_F +| | * | 5_E +| |/|\ \ +| |_|/ / +|/| | / +| | |/ +* | | 5_D +| | * 5_C +| |/ +|/| +| * 5_B +|/ +* 5_A +EOF + +test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + +test_expect_success 'setup merge fusing with its left and right neighbors' ' + git checkout --orphan 6_p && + test_commit 6_A && + test_commit 6_B && + git checkout -b 6_q @^ && test_commit 6_C && + git checkout -b 6_r @^ && test_commit 6_D && + git checkout 6_p && git merge --no-ff 6_q 6_r -m 6_E && + git checkout 6_r && test_commit 6_F && + git checkout 6_p && git merge --no-ff 6_r -m 6_G && + git checkout @^^ && git merge --no-ff 6_p -m 6_H +' + +cat > expect <<\EOF +* 6_H +|\ +| * 6_G +| |\ +| | * 6_F +| * | 6_E +|/|\| +| | * 6_D +| * | 6_C +| |/ +* / 6_B +|/ +* 6_A +EOF + +test_expect_success 'log --graph with merge fusing with its left and right neighbors' ' + git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual && + test_cmp expect actual +' + test_done diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh index ca1682f29b..f5e6e92f5b 100755 --- a/t/t6016-rev-list-graph-simplify-history.sh +++ b/t/t6016-rev-list-graph-simplify-history.sh @@ -67,11 +67,10 @@ test_expect_success '--graph --all' ' echo "| * $C4" >> expected && echo "| * $C3" >> expected && echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. \\ $A4" >> expected && - echo "|\\ \\ \\ " >> expected && - echo "| | |/ " >> expected && + echo "| | " >> expected && + echo "| \\ " >> expected && + echo "*-. | $A4" >> expected && + echo "|\\ \\| " >> expected && echo "| | * $C2" >> expected && echo "| | * $C1" >> expected && echo "| * | $B2" >> expected && @@ -97,11 +96,10 @@ test_expect_success '--graph --simplify-by-decoration' ' echo "| * $C4" >> expected && echo "| * $C3" >> expected && echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. \\ $A4" >> expected && - echo "|\\ \\ \\ " >> expected && - echo "| | |/ " >> expected && + echo "| | " >> expected && + echo "| \\ " >> expected && + echo "*-. | $A4" >> expected && + echo "|\\ \\| " >> expected && echo "| | * $C2" >> expected && echo "| | * $C1" >> expected && echo "| * | $B2" >> expected && @@ -131,9 +129,8 @@ test_expect_success '--graph --simplify-by-decoration prune branch B' ' echo "| * $C4" >> expected && echo "| * $C3" >> expected && echo "* | $A5" >> expected && - echo "* | $A4" >> expected && - echo "|\\ \\ " >> expected && - echo "| |/ " >> expected && + echo "* | $A4" >> expected && + echo "|\\| " >> expected && echo "| * $C2" >> expected && echo "| * $C1" >> expected && echo "* | $A3" >> expected && @@ -151,10 +148,9 @@ test_expect_success '--graph --full-history -- bar.txt' ' echo "|\\ " >> expected && echo "| * $C4" >> expected && echo "* | $A5" >> expected && - echo "* | $A4" >> expected && - echo "|\\ \\ " >> expected && - echo "| |/ " >> expected && - echo "* / $A3" >> expected && + echo "* | $A4" >> expected && + echo "|\\| " >> expected && + echo "* | $A3" >> expected && echo "|/ " >> expected && echo "* $A2" >> expected && git rev-list --graph --full-history --all -- bar.txt > actual && From patchwork Thu Oct 10 16:13:52 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee via GitGitGadget X-Patchwork-Id: 11183907 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E1E6D13BD for ; Thu, 10 Oct 2019 16:13:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id B9F4120B7C for ; Thu, 10 Oct 2019 16:13:58 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="e7wgc1aN" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726365AbfJJQN6 (ORCPT ); Thu, 10 Oct 2019 12:13:58 -0400 Received: from mail-wm1-f48.google.com ([209.85.128.48]:35985 "EHLO mail-wm1-f48.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726284AbfJJQN4 (ORCPT ); Thu, 10 Oct 2019 12:13:56 -0400 Received: by mail-wm1-f48.google.com with SMTP id m18so7419506wmc.1 for ; Thu, 10 Oct 2019 09:13:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=IOaD5IHlIM0x+QdzkRgkgP5/vrzTBReoSyidKYaCpnk=; b=e7wgc1aNWn68kpcUeLmnnxWLlLEOSb7sOfo11KuSDLDkGWgooADm7F453hdxc0CPC9 7aFS6FgbolDz51PC5cx3z8EcBzfsFexrQwinwsDXhIgknI94oD7t49E6JsCsuBXAuiBB gNKat8kC6eYGmoOt0ySbuXWVXOBpiIPsC6fLzZ9vxh05Nx5AnxSDIZMlSbCOlBGrCLr+ FZGMsb8MtD/4M9EZY9Up/HJC64CXLtAw/C2AWHn+piQl69hBzF8JYRi3JfmQyGSIJQn7 CAb7CRPm6wiVl0Lm/YkAAZ/JGQYDoD6lm59KfDjxFKGJ8PVD/e4ywCFC9XP00ONZ4lzC suNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=IOaD5IHlIM0x+QdzkRgkgP5/vrzTBReoSyidKYaCpnk=; b=POFt7t0rTAMEoCzq451Wia9zvThlCuZar28iP2PtgpH06SuKlauQNLEqB6ICNgB6ti 97IucIAOsQn+6AR3hJwIBEMc3WBb0ZpwXWH1uUA+UXvHp3ppbmiIPPwYytdNzIx3OL5+ jpTH72lN2HolLLZmeVFUfkoXDHKyp9xfpJWlOVgEJ2DrJ03OBJj4vJL7GeKBgVhbokO1 mTerVqMaSX6/+l0H60IkXS4bdFSXvlTv6XDa0e+/47Tlm8N4z6uhRgUt/cv5VpSEO3j4 rdfyI/L4GkOC8bd+Ofpv266nEyFO3ZtBdemIWAeOETMxjGJzlDoYkEEnl7Ay3tR2PbWz FHbA== X-Gm-Message-State: APjAAAWU055nahbvq4EbSRfRRPSF4fO9Odx8TqC0SIVWuSa/STut/5Dq HA7I1X1ZWiXlIpbWfypq2F29IwJt X-Google-Smtp-Source: APXvYqwZWCPbp9sgX/OpnOYNl/C2XOJgoSmLuw5rcH8xX8+4HbZ3HY5n/X0530lLraOsfbCkWT7CGw== X-Received: by 2002:a1c:2e94:: with SMTP id u142mr8506806wmu.69.1570724033089; Thu, 10 Oct 2019 09:13:53 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id e15sm8297397wrt.94.2019.10.10.09.13.52 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Oct 2019 09:13:52 -0700 (PDT) Date: Thu, 10 Oct 2019 09:13:52 -0700 (PDT) X-Google-Original-Date: Thu, 10 Oct 2019 16:13:40 GMT Message-Id: In-Reply-To: References: From: "James Coglan via GitGitGadget" Subject: [PATCH 11/11] graph: fix coloring of octopus dashes Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , James Coglan Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: James Coglan In 04005834ed ("log: fix coloring of certain octopus merge shapes", 2018-09-01) there is a fix for the coloring of dashes following an octopus merge. It makes a distinction between the case where all parents introduce a new column, versus the case where the first parent collapses into an existing column: | *-. | *-. | |\ \ | |\ \ | | | | |/ / / The latter case means that the columns for the merge parents begin one place to the left in the `new_columns` array compared to the former case. However, the implementation only works if the commit's parents are kept in order as they map onto the visual columns, as we get the colors by iterating over `new_columns` as we print the dashes. In general, the commit's parents can arbitrarily merge with existing columns, and change their ordering in the process. For example, in the following diagram, the number of each column indicates which commit parent appears in each column. | | *---. | | |\ \ \ | | |/ / / | |/| | / | |_|_|/ |/| | | 3 1 0 2 If the columns are colored (red, green, yellow, blue), then the dashes will currently be colored yellow and blue, whereas they should be blue and red. To fix this, we need to look up each column in the `mapping` array, which before the `GRAPH_COLLAPSING` state indicates which logical column is displayed in each visual column. This implementation is simpler as it doesn't have any edge cases, and it also handles how left-skewed first parents are now displayed: | *-. |/|\ \ | | | | 0 1 2 3 The color of the first dashes is always the color found in `mapping` two columns to the right of the commit symbol. Because commits are displayed after all edges have been collapsed together and the visual columns match the logical ones, we can find the visual offset of the commit symbol using `commit_index`. Signed-off-by: James Coglan --- graph.c | 71 +++++++++++++++++++----------------- t/t4214-log-graph-octopus.sh | 59 ++++++++++++++++++++++++++++-- 2 files changed, 92 insertions(+), 38 deletions(-) diff --git a/graph.c b/graph.c index 7dd2fab625..908f257018 100644 --- a/graph.c +++ b/graph.c @@ -665,6 +665,11 @@ static void graph_update_columns(struct git_graph *graph) graph->mapping_size--; } +static int graph_num_dashed_parents(struct git_graph *graph) +{ + return graph->num_parents + graph->merge_layout - 3; +} + static int graph_num_expansion_rows(struct git_graph *graph) { /* @@ -687,7 +692,7 @@ static int graph_num_expansion_rows(struct git_graph *graph) * | * \ * |/|\ \ */ - return (graph->num_parents + graph->merge_layout - 3) * 2; + return graph_num_dashed_parents(graph) * 2; } static int graph_needs_pre_commit_line(struct git_graph *graph) @@ -930,47 +935,45 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb) static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb) { /* - * Here dashless_parents represents the number of parents which don't - * need to have dashes (the edges labeled "0" and "1"). And - * dashful_parents are the remaining ones. + * The parents of a merge commit can be arbitrarily reordered as they + * are mapped onto display columns, for example this is a valid merge: * - * | *---. - * | |\ \ \ - * | | | | | - * x 0 1 2 3 + * | | *---. + * | | |\ \ \ + * | | |/ / / + * | |/| | / + * | |_|_|/ + * |/| | | + * 3 1 0 2 * - */ - const int dashless_parents = 3 - graph->merge_layout; - int dashful_parents = graph->num_parents - dashless_parents; - - /* - * Usually, we add one new column for each parent (like the diagram - * above) but sometimes the first parent goes into an existing column, - * like this: + * The numbers denote which parent of the merge each visual column + * corresponds to; we can't assume that the parents will initially + * display in the order given by new_columns. * - * | *-. - * |/|\ \ - * | | | | - * x 0 1 2 + * To find the right color for each dash, we need to consult the + * mapping array, starting from the column 2 places to the right of the + * merge commit, and use that to find out which logical column each + * edge will collapse to. * - * In which case the number of parents will be one greater than the - * number of added columns. + * Commits are rendered once all edges have collapsed to their correct + * logcial column, so commit_index gives us the right visual offset for + * the merge commit. */ - int added_cols = (graph->num_new_columns - graph->num_columns); - int parent_in_old_cols = graph->num_parents - added_cols; - /* - * In both cases, commit_index corresponds to the edge labeled "0". - */ - int first_col = graph->commit_index + dashless_parents - - parent_in_old_cols; + int i, j; + struct column *col; - int i; - for (i = 0; i < dashful_parents; i++) { - strbuf_write_column(sb, &graph->new_columns[i+first_col], '-'); - strbuf_write_column(sb, &graph->new_columns[i+first_col], - i == dashful_parents-1 ? '.' : '-'); + int dashed_parents = graph_num_dashed_parents(graph); + + for (i = 0; i < dashed_parents; i++) { + j = graph->mapping[(graph->commit_index + i + 2) * 2]; + col = &graph->new_columns[j]; + + strbuf_write_column(sb, col, '-'); + strbuf_write_column(sb, col, (i == dashed_parents - 1) ? '.' : '-'); } + + return; } static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb) diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh index 9ada687628..fbd485d83a 100755 --- a/t/t4214-log-graph-octopus.sh +++ b/t/t4214-log-graph-octopus.sh @@ -42,23 +42,74 @@ test_expect_success 'set up merge history' ' test_tick && git merge -m octopus-merge 1 2 3 4 && git checkout 1 -b L && - test_commit left + test_commit left && + git checkout 4 -b R && + test_commit right ' test_expect_success 'log --graph with tricky octopus merge with colors' ' test_config log.graphColors red,green,yellow,blue,magenta,cyan && - git log --color=always --graph --date-order --pretty=tformat:%s --all >actual.colors.raw && + git log --color=always --graph --date-order --pretty=tformat:%s L merge >actual.colors.raw && test_decode_color actual.colors && test_cmp expect.colors actual.colors ' test_expect_success 'log --graph with tricky octopus merge, no color' ' - git log --color=never --graph --date-order --pretty=tformat:%s --all >actual.raw && + git log --color=never --graph --date-order --pretty=tformat:%s L merge >actual.raw && sed "s/ *\$//" actual.raw >actual && test_cmp expect.uncolored actual ' -# Repeat the previous two tests with "normal" octopus merge (i.e., +# Repeat the previous two tests with an octopus merge whose final parent skews left + +test_expect_success 'log --graph with left-skewed final parent, no color' ' + cat >expect.uncolored <<-\EOF && + * right + | *---. octopus-merge + | |\ \ \ + | |_|_|/ + |/| | | + * | | | 4 + | | | * 3 + | |_|/ + |/| | + | | * 2 + | |/ + |/| + | * 1 + |/ + * initial + EOF + git log --color=never --graph --date-order --pretty=tformat:%s R merge >actual.raw && + sed "s/ *\$//" actual.raw >actual && + test_cmp expect.uncolored actual +' + +test_expect_success 'log --graph with left-skewed final parent with colors' ' + cat >expect.colors <<-\EOF && + * right + | *---. octopus-merge + | |\ \ \ + | |_|_|/ + |/| | | + * | | | 4 + | | | * 3 + | |_|/ + |/| | + | | * 2 + | |/ + |/| + | * 1 + |/ + * initial + EOF + test_config log.graphColors red,green,yellow,blue,magenta,cyan && + git log --color=always --graph --date-order --pretty=tformat:%s R merge >actual.colors.raw && + test_decode_color actual.colors && + test_cmp expect.colors actual.colors +' + +# Repeat the first two tests with "normal" octopus merge (i.e., # without the first parent skewing to the "left" branch column). test_expect_success 'log --graph with normal octopus merge, no color' '