From patchwork Thu Dec 9 10:29:55 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666311 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id D0C03C433EF for ; Thu, 9 Dec 2021 10:30:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234556AbhLIKdw (ORCPT ); Thu, 9 Dec 2021 05:33:52 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34342 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232317AbhLIKdr (ORCPT ); Thu, 9 Dec 2021 05:33:47 -0500 Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com [IPv6:2a00:1450:4864:20::32a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D977EC061746 for ; Thu, 9 Dec 2021 02:30:13 -0800 (PST) Received: by mail-wm1-x32a.google.com with SMTP id p3-20020a05600c1d8300b003334fab53afso6161649wms.3 for ; Thu, 09 Dec 2021 02:30:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=196Fzi9pWJNNoy0fcJITLBwaY4nVQto3zq+DfxxjTpI=; b=Pt3ikzE9/30zKgUQTJSETzNPc8HN2gMYb2xbfL5tNZPVK1ZYxP5YcPQpPdejG2Kqiz 0bvqlmQ8qgLEx4IqqxGTC9gyiALWEyuS2/QM25m7QgZBGOrrxrEyeifp4EguMOQg0bsY v1+pQLcfAQ98YARdCEqjjWz9B4+3/uRPWmrxdrpLDURCSlIhF1aL9efsH3PPmfvPXk4z wGBANI+z9KiQd7uiTqq3csbxUyk1ATLJxISDJWMDXwfL+nPw3cdmQ/8C6ngBHyeVQDP7 bt22X154kfIGI+R52zMQXWp6W23NcmBDIRNfm1uRaA39dIWoL3r0tredy7g1r4Vp5tVN 5Z4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=196Fzi9pWJNNoy0fcJITLBwaY4nVQto3zq+DfxxjTpI=; b=bRq1KUarF4GGA5m3RJb6wrTx4QtBaaE2O3tcGWziLV1PC+0CD5hCwgaR2aFnWm796E 7Rwcjtf0jRbDwgp+c8JbQRhkzMn46x+5XeyH0HtNBLfCr7+p5KRrr5rUU7z6Kxmx49jJ dNMln9hHw8uiWpUNrDs4d6EB8nBrmtfdsUgBygAXMCPFZtzDASf2oaPHQa0BKE9m0Mvp EoOTZKLrI8HoMcMYAgmm6HmwQN1IBzWqWb/UQdzEBtzQmUuQxTqI1BhN5PlnjPJ5XI9x LjclWJ9S7XkMzF2rtcdRim0Ey0E56N+4dR23H3G9ggsrUj6QEzgplV95Obe2QF6KwG+e 1KRw== X-Gm-Message-State: AOAM53121O9sfmJ+NaXXxFbtCdOqNvZdhdwviKg6Jmw5VmuA/cxxXD90 n/+rxM7ialPnV0csyfZzT4HJNGWOT8w= X-Google-Smtp-Source: ABdhPJwAGnn4QWbeMDOwFsQ2CI/YloNREoMOIpaIdS9+aBPdAKUyavRdfFsqiFJQtFFNp0fX9axX7A== X-Received: by 2002:a1c:ed0a:: with SMTP id l10mr5975870wmh.104.1639045812312; Thu, 09 Dec 2021 02:30:12 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id d9sm5293406wre.52.2021.12.09.02.30.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:11 -0800 (PST) Message-Id: <48ee03cf52a619d22d7ee7b1958dd59872bf721f.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:29:55 +0000 Subject: [PATCH v5 01/15] diff --color-moved: add perf tests Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Add some tests so we can monitor changes to the performance of the move detection code. The tests record the performance --color-moved and --color-moved-ws=allow-indentation-change for a large diff and a sequence of smaller diffs. The range of commits used for the large diff can be customized by exporting TEST_REV_A and TEST_REV_B when running the test. Signed-off-by: Phillip Wood --- t/perf/p4002-diff-color-moved.sh | 57 ++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100755 t/perf/p4002-diff-color-moved.sh diff --git a/t/perf/p4002-diff-color-moved.sh b/t/perf/p4002-diff-color-moved.sh new file mode 100755 index 00000000000..ab2af931c04 --- /dev/null +++ b/t/perf/p4002-diff-color-moved.sh @@ -0,0 +1,57 @@ +#!/bin/sh + +test_description='Tests diff --color-moved performance' +. ./perf-lib.sh + +test_perf_default_repo + +# The endpoints of the diff can be customized by setting TEST_REV_A +# and TEST_REV_B in the environment when running this test. + +rev="${TEST_REV_A:-v2.28.0}" +if ! rev_a="$(git rev-parse --quiet --verify "$rev")" +then + skip_all="skipping because '$rev' was not found. \ + Use TEST_REV_A and TEST_REV_B to set the revs to use" + test_done +fi +rev="${TEST_REV_B:-v2.29.0}" +if ! rev_b="$(git rev-parse --quiet --verify "$rev")" +then + skip_all="skipping because '$rev' was not found. \ + Use TEST_REV_A and TEST_REV_B to set the revs to use" + test_done +fi + +GIT_PAGER_IN_USE=1 +test_export GIT_PAGER_IN_USE rev_a rev_b + +test_perf 'diff --no-color-moved --no-color-moved-ws large change' ' + git diff --no-color-moved --no-color-moved-ws $rev_a $rev_b +' + +test_perf 'diff --color-moved --no-color-moved-ws large change' ' + git diff --color-moved=zebra --no-color-moved-ws $rev_a $rev_b +' + +test_perf 'diff --color-moved-ws=allow-indentation-change large change' ' + git diff --color-moved=zebra --color-moved-ws=allow-indentation-change \ + $rev_a $rev_b +' + +test_perf 'log --no-color-moved --no-color-moved-ws' ' + git log --no-color-moved --no-color-moved-ws --no-merges --patch \ + -n1000 $rev_b +' + +test_perf 'log --color-moved --no-color-moved-ws' ' + git log --color-moved=zebra --no-color-moved-ws --no-merges --patch \ + -n1000 $rev_b +' + +test_perf 'log --color-moved-ws=allow-indentation-change' ' + git log --color-moved=zebra --color-moved-ws=allow-indentation-change \ + --no-merges --patch -n1000 $rev_b +' + +test_done From patchwork Thu Dec 9 10:29:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666313 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2E9BAC433FE for ; Thu, 9 Dec 2021 10:30:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234459AbhLIKdz (ORCPT ); Thu, 9 Dec 2021 05:33:55 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34352 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234450AbhLIKds (ORCPT ); Thu, 9 Dec 2021 05:33:48 -0500 Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C6788C0617A1 for ; Thu, 9 Dec 2021 02:30:14 -0800 (PST) Received: by mail-wm1-x332.google.com with SMTP id y196so3782854wmc.3 for ; Thu, 09 Dec 2021 02:30:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=8PooKE+ZmACiLnvvFNaC9GMC6c2B/Iz1nlWdS4LuFUY=; b=h8rioBTutx19lpS3B1gDa5AwOpWfnD2vssAB40de+aV5SDdfXHPHikjfwrQVZKyts0 BEzY9SpCe+nUE2dVtjupf8mVRYADilT7Ai/Mp2M6vPfoBPFK2H2D6p1dciMGL7W11lqN /6IO0eLmraG++s9C24aw7mwpPiCo8iSaOUdR57fIMq0ELIDGMmV8tOf6/i4ZUftUXETd IPD2f9v8zVFPJ2TQacRskHLWYoFkOGue1j4r8zUYat5U0BUVfR2jdRds3DwH0/DAI1kw twgrsyJnX8DHqPTpQvWZ0EuIOvYaX+NhqW5vzNkqt+Gp2bS2bQNe2I4qICkiBoK3feiK mXvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=8PooKE+ZmACiLnvvFNaC9GMC6c2B/Iz1nlWdS4LuFUY=; b=BDqU4JLEu6PMCBRCBfX/fg1jrPr7fmsdk7NvNgzeY4o8T7GslrSSUHsXAZUBkpSBI5 KW+draK/n2kh5IT/JMEkDifdqMlxUYUYuq1EkWI7FWCSuz8mwocUXAIfzmeG6cOnVzxP M5/bG1tiWR7RR2y/709SqM95c8WkKLZ4KnJgijbWG2ov385N1wTfygK0PbwwrATHNhdg RAfvBXARzM5JdXn1SqH2UKEZUPz1Q5jM6j4yLzZ8p7aTaB+YQyR8SdU4EohXjTypjN5p 60/kmrcfq38/OLqRM3lF7HFa24wKVwyyAxWK6qLUKH5H+fZLbdSBU0SwG9Oa7CAs8VBL M7Yw== X-Gm-Message-State: AOAM530pcNavaCpiqblkYogD/kvYPgCqSTTplqVsVmOT734wMsf0iJft 0bygwc0MZkN+HM267sjaVxZUWUOlFgU= X-Google-Smtp-Source: ABdhPJx79+ar2+MnEQxxGO77epsJd4r4CS69OtthMniisKQA+mptA7hHe9A0CYp0+pIlyaidvayXrw== X-Received: by 2002:a05:600c:19d1:: with SMTP id u17mr6110709wmq.148.1639045813127; Thu, 09 Dec 2021 02:30:13 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id n1sm5557598wmq.6.2021.12.09.02.30.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:12 -0800 (PST) Message-Id: <47c652716e88af7199c44a555780eafb643a1f9e.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:29:56 +0000 Subject: [PATCH v5 02/15] diff --color-moved: clear all flags on blocks that are too short Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood If a block of potentially moved lines is not long enough then the DIFF_SYMBOL_MOVED_LINE flag is cleared on the matching lines so they are not marked as moved. To avoid problems when we start rewinding after an unsuccessful match in a couple of commits time make sure all the move related flags are cleared, not just DIFF_SYMBOL_MOVED_LINE. Signed-off-by: Phillip Wood --- diff.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/diff.c b/diff.c index 52c791574b7..bd8e4ec9757 100644 --- a/diff.c +++ b/diff.c @@ -1114,6 +1114,8 @@ static int shrink_potential_moved_blocks(struct moved_block *pmb, * NEEDSWORK: This uses the same heuristic as blame_entry_score() in blame.c. * Think of a way to unify them. */ +#define DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK \ + (DIFF_SYMBOL_MOVED_LINE | DIFF_SYMBOL_MOVED_LINE_ALT) static int adjust_last_block(struct diff_options *o, int n, int block_length) { int i, alnum_count = 0; @@ -1130,7 +1132,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length) } } for (i = 1; i < block_length + 1; i++) - o->emitted_symbols->buf[n - i].flags &= ~DIFF_SYMBOL_MOVED_LINE; + o->emitted_symbols->buf[n - i].flags &= ~DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK; return 0; } @@ -1237,8 +1239,6 @@ static void mark_color_as_moved(struct diff_options *o, free(pmb); } -#define DIFF_SYMBOL_MOVED_LINE_ZEBRA_MASK \ - (DIFF_SYMBOL_MOVED_LINE | DIFF_SYMBOL_MOVED_LINE_ALT) static void dim_moved_lines(struct diff_options *o) { int n; From patchwork Thu Dec 9 10:29:57 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666317 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7E7ADC433EF for ; Thu, 9 Dec 2021 10:30:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234595AbhLIKd4 (ORCPT ); Thu, 9 Dec 2021 05:33:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34358 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234469AbhLIKdt (ORCPT ); Thu, 9 Dec 2021 05:33:49 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ACE0DC061353 for ; Thu, 9 Dec 2021 02:30:15 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id a9so8825779wrr.8 for ; Thu, 09 Dec 2021 02:30:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=I1OjuyEdvS7pDHXy+edm6Y3GA0g7nFkP4MZfeMkkBBA=; b=m+RkgsLQhTOMxZVHi6sQyIT5+DfmrpCF0WeXlFh9vrbs2ndZWrJdZzHT6E/5ta06MY syrOrVXDybsyeh+jCbM+lmXqDWB9KiD9Vi5lOK3rlCAfydejC10lM7Wp8IG1MQXpgXHB AtitPN6G/H04anTSe2T4R7Hk0p2aNO+nWoFeT7pJfdTyLxOxojJs3J3bKJgwbtK24LYl BBoNLsOTnWM6lnpoJChsrv0a1n42JwvjLZy8O5MoVlwTBLfCQ7RtfYOzoqAWGKwObB5P vbvalZVxkuSwtyZ4FM0ad9oVhJn3zNE1OhmXyj2IPJPPIBl7iyhIsG7lIiXLPfXIhREc 6OvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=I1OjuyEdvS7pDHXy+edm6Y3GA0g7nFkP4MZfeMkkBBA=; b=sAMtDHvhRtFOtqf9gJbB4uSLmC+LjzGYT43HnSgk31tvx7TXoEUVFTHmYWJrbaXfI1 a6nzV0RsPo4hGKLBgDaJ4McVQKuEl42kUrdYIKpvJXV9Bxrqs/f0Q5270ku3uqHmvl77 0T8h1eqjfLmxVIEVfW3p++T0Ki3rV/4DfwdjMqCoX09atbds1j8Y+567iyFcl3CjJbZ5 9bDnS+igNeynmMveFcsLxLJRGrvdIhX9keyIgcbxy+4LcbpWmCVQP0d3FHYghStkZlzv z1I3CbRl18/w6m+TfAd4y6N/QdW6Faa0Ig3VmxPI7hEwMu/zu1L+diOCNDCSmJRp1JKW pCdw== X-Gm-Message-State: AOAM530/sFKZpskV7Nf7umhqcvGRIK2Aj7DVBEPFmVDXjL+bzgNL6Kei yG1zT8ne2fs97ao1134w67/CnR7hiLE= X-Google-Smtp-Source: ABdhPJygZVnVGSj55ysFQ8wRC6c3V06J51sGzou7ckZWRAhLITpEAQqBytiwJevjyigy1qbYoE1mUA== X-Received: by 2002:a5d:4889:: with SMTP id g9mr5439933wrq.455.1639045814009; Thu, 09 Dec 2021 02:30:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s24sm4832817wmj.26.2021.12.09.02.30.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:13 -0800 (PST) Message-Id: <99e38ba9de9bcd7b767908ec218937ae8c2ccf36.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:29:57 +0000 Subject: [PATCH v5 03/15] diff --color-moved: factor out function Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood This code is quite heavily indented and having it in its own function simplifies an upcoming change. Signed-off-by: Phillip Wood --- diff.c | 51 ++++++++++++++++++++++++++++++++++----------------- 1 file changed, 34 insertions(+), 17 deletions(-) diff --git a/diff.c b/diff.c index bd8e4ec9757..09af94e018c 100644 --- a/diff.c +++ b/diff.c @@ -1098,6 +1098,38 @@ static int shrink_potential_moved_blocks(struct moved_block *pmb, return rp + 1; } +static void fill_potential_moved_blocks(struct diff_options *o, + struct hashmap *hm, + struct moved_entry *match, + struct emitted_diff_symbol *l, + struct moved_block **pmb_p, + int *pmb_alloc_p, int *pmb_nr_p) + +{ + struct moved_block *pmb = *pmb_p; + int pmb_alloc = *pmb_alloc_p, pmb_nr = *pmb_nr_p; + + /* + * The current line is the start of a new block. + * Setup the set of potential blocks. + */ + hashmap_for_each_entry_from(hm, match, ent) { + ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); + if (o->color_moved_ws_handling & + COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { + if (compute_ws_delta(l, match->es, &(pmb[pmb_nr]).wsd)) + pmb[pmb_nr++].match = match; + } else { + pmb[pmb_nr].wsd = 0; + pmb[pmb_nr++].match = match; + } + } + + *pmb_p = pmb; + *pmb_alloc_p = pmb_alloc; + *pmb_nr_p = pmb_nr; +} + /* * If o->color_moved is COLOR_MOVED_PLAIN, this function does nothing. * @@ -1198,23 +1230,8 @@ static void mark_color_as_moved(struct diff_options *o, pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr); if (pmb_nr == 0) { - /* - * The current line is the start of a new block. - * Setup the set of potential blocks. - */ - hashmap_for_each_entry_from(hm, match, ent) { - ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); - if (o->color_moved_ws_handling & - COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { - if (compute_ws_delta(l, match->es, - &pmb[pmb_nr].wsd)) - pmb[pmb_nr++].match = match; - } else { - pmb[pmb_nr].wsd = 0; - pmb[pmb_nr++].match = match; - } - } - + fill_potential_moved_blocks( + o, hm, match, l, &pmb, &pmb_alloc, &pmb_nr); if (adjust_last_block(o, n, block_length) && pmb_nr && last_symbol != l->s) flipped_block = (flipped_block + 1) % 2; From patchwork Thu Dec 9 10:29:58 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666323 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 78B79C433F5 for ; Thu, 9 Dec 2021 10:30:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234661AbhLIKeA (ORCPT ); Thu, 9 Dec 2021 05:34:00 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34370 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234492AbhLIKdv (ORCPT ); Thu, 9 Dec 2021 05:33:51 -0500 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 97F40C061D5E for ; Thu, 9 Dec 2021 02:30:16 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id a18so8844828wrn.6 for ; Thu, 09 Dec 2021 02:30:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=4TWTb1oFbv2Cyih2NY/IJNJz+zwyZHn49m5PcWSyTQM=; b=Bh18PUttEHi9bjfq1I8thUzh5asahfsfWyyVP7q8b7tevdJT5dqPhIi4McUKC1FV1i /B+n5g7+Qx/aPolL1ufEQBIkabigvAaHFodOtCvYrkkU2Tx7K1WVFLEQTTUCX859KVIV 52zeRHnw/mHXK/bGXFx/gXJg1MNsxNHJc/NVzussdPuOqLesbaGJUyJh7V5IXK6y6Ox+ ig/BZNaxDLKwXEIpfgT/Qb1svXsPaXS81SUsxFKOGfLf7R7HLXNYg8rSlAcf3f2rCA0t t+Y7ceb/mM0h8wtBflNTSXY+VlFluJdxZGoqRrwRmQh9jou6jbCM9PRpXvS4VB70QJB3 fhSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=4TWTb1oFbv2Cyih2NY/IJNJz+zwyZHn49m5PcWSyTQM=; b=PVaFGdbeDJcdlDjUwcO1CfKfM7NrzCownRYOJdy1SgfxZRUJLDVz8b7GehZkWb138X BTXBxSjCBQaUYA7IHR/tymg1hE4ANiNBRTEPjlpGG0UBl+kRjTO1PAE6Hw+ru9tLZMBb hzitfSv6BhTzoyHL7sPjaJ4io5+0qRyt0ngkXTGAGlqztjb+z7Xv/eiJ+fEUEMzUvgM0 KW5O3y0hhqEJcbfYNQS6dXc7YBzZZmj72JCb9lw3642epRJlS2JYFVU3ObXcA2n1CjNl 29xa1HWEbMdChAldlGgKuF1Xke8utrU/prtEtCNwRLG/VQm42wZjaCRa34PqHepOJhWE HgBw== X-Gm-Message-State: AOAM531LFJejIBakAIIyp9aThn/rIqMpWYFCZb2DAVCpAI2XILF11FZ4 gtpzq8ecM/Me0rD+6xkMI+YR6k+BbtA= X-Google-Smtp-Source: ABdhPJx/hcp/bo5Vnlnzca6jAjqlwnIMPhdiGvCZW77evix/u0ZddK7VFrl1xJrFkOtOsWNseP2ycQ== X-Received: by 2002:a05:6000:184e:: with SMTP id c14mr5362075wri.241.1639045814837; Thu, 09 Dec 2021 02:30:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l8sm9979517wmc.40.2021.12.09.02.30.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:14 -0800 (PST) Message-Id: <9ca71db61ae92d99fceba112593999596b65cd4c.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:29:58 +0000 Subject: [PATCH v5 04/15] diff --color-moved: rewind when discarding pmb Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood diff --color-moved colors the two sides of the diff separately. It walks through the diff and tries to find matches on the other side of the diff for the current line. When it finds one or more matches it starts a "potential moved block" (pmb) and marks the current line as moved. Then as it walks through the diff it only looks for matches for the current line in the lines following those in the pmb. When none of the lines in the pmb match it checks how long the match is and if it is too short it unmarks the lines as matched and goes back to finding all the lines that match the current line. As the process of finding matching lines restarts from the end of the block that was too short it is possible to miss the start of a matching block on on side but not the other. In the test added here "-two" would not be colored as moved but "+two" would be. Fix this by rewinding the current line when we reach the end of a block that is too short. This is quadratic in the length of the discarded block. While the discarded blocks are quite short on a large diff this still has a significant impact on the performance of --color-moved-ws=allow-indentation-change. The following commits optimize the performance of the --color-moved machinery which mitigates the performance impact of this commit. After the optimization this commit has a negligible impact on performance. Test HEAD^ HEAD ----------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.39 (0.34+0.04) +2.6% 4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.76+0.03) 0.86 (0.82+0.04) +7.5% 4002.3: diff --color-moved-ws=allow-indentation-change large change 14.22(14.17+0.04) 19.01(18.93+0.05) +33.7% 4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.16 (1.07+0.07) +0.0% 4002.5: log --color-moved --no-color-moved-ws 1.31 (1.22+0.09) 1.32 (1.22+0.09) +0.8% 4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.61+0.09) 1.72 (1.63+0.08) +0.6% Signed-off-by: Phillip Wood --- diff.c | 28 ++++++++++++++++++----- t/t4015-diff-whitespace.sh | 46 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 69 insertions(+), 5 deletions(-) diff --git a/diff.c b/diff.c index 09af94e018c..1e1b5127d15 100644 --- a/diff.c +++ b/diff.c @@ -1205,7 +1205,15 @@ static void mark_color_as_moved(struct diff_options *o, if (!match) { int i; - adjust_last_block(o, n, block_length); + if (!adjust_last_block(o, n, block_length) && + block_length > 1) { + /* + * Rewind in case there is another match + * starting at the second line of the block + */ + match = NULL; + n -= block_length; + } for(i = 0; i < pmb_nr; i++) moved_block_clear(&pmb[i]); pmb_nr = 0; @@ -1230,10 +1238,20 @@ static void mark_color_as_moved(struct diff_options *o, pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr); if (pmb_nr == 0) { - fill_potential_moved_blocks( - o, hm, match, l, &pmb, &pmb_alloc, &pmb_nr); - if (adjust_last_block(o, n, block_length) && - pmb_nr && last_symbol != l->s) + int contiguous = adjust_last_block(o, n, block_length); + + if (!contiguous && block_length > 1) + /* + * Rewind in case there is another match + * starting at the second line of the block + */ + n -= block_length; + else + fill_potential_moved_blocks(o, hm, match, l, + &pmb, &pmb_alloc, + &pmb_nr); + + if (contiguous && pmb_nr && last_symbol != l->s) flipped_block = (flipped_block + 1) % 2; else flipped_block = 0; diff --git a/t/t4015-diff-whitespace.sh b/t/t4015-diff-whitespace.sh index 2c13b62d3c6..308dc136596 100755 --- a/t/t4015-diff-whitespace.sh +++ b/t/t4015-diff-whitespace.sh @@ -1833,6 +1833,52 @@ test_expect_success '--color-moved treats adjacent blocks as separate for MIN_AL test_cmp expected actual ' +test_expect_success '--color-moved rewinds for MIN_ALNUM_COUNT' ' + git reset --hard && + test_write_lines >file \ + A B C one two three four five six seven D E F G H I J && + git add file && + test_write_lines >file \ + one two A B C D E F G H I J two three four five six seven && + git diff --color-moved=zebra -- file && + + git diff --color-moved=zebra --color -- file >actual.raw && + grep -v "index" actual.raw | test_decode_color >actual && + cat >expected <<-\EOF && + diff --git a/file b/file + --- a/file + +++ b/file + @@ -1,13 +1,8 @@ + +one + +two + A + B + C + -one + -two + -three + -four + -five + -six + -seven + D + E + F + @@ -15,3 +10,9 @@ G + H + I + J + +two + +three + +four + +five + +six + +seven + EOF + + test_cmp expected actual +' + test_expect_success 'move detection with submodules' ' test_create_repo bananas && echo ripe >bananas/recipe && From patchwork Thu Dec 9 10:29:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666315 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C11ADC433F5 for ; Thu, 9 Dec 2021 10:30:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234485AbhLIKd4 (ORCPT ); Thu, 9 Dec 2021 05:33:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34372 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234510AbhLIKdv (ORCPT ); Thu, 9 Dec 2021 05:33:51 -0500 Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 771BAC061D5F for ; Thu, 9 Dec 2021 02:30:17 -0800 (PST) Received: by mail-wr1-x42d.google.com with SMTP id c4so8813825wrd.9 for ; Thu, 09 Dec 2021 02:30:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=r/21tYvfclPNJep2HNK27H7vRi4XW03mypSl62mMt2g=; b=pq4dmQ4k5cyB56ULn6T6R3UXO3iQsB9s+6BZyYNycW80AsaJ+dy6dqnogq47dmkxCa d4zcxYCUe75f+GS7lXVNx8+VTU6F3KvCDIMg4u0/BdrV6oTpwtoY4MCeOClBVFzwI0sI 0BD8nPvOM/ashdpSj3tOWiYsCmtrdYKp20FNLA55eEN4n2b2k8fHfbQjTyI6274N+Xnj yx2Dv67ql/uqqLZ4uDw4qV1eQCWAguGCODYh4zkFm2LWIwggt4KESD9sVIhEtFoOobcP +/avNZLGIjSGgqixOlX76DTzpL3VgWgkWQw2L7/UTenDNMZIjLBKUyhBpHJ6d93fd1iW BPRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=r/21tYvfclPNJep2HNK27H7vRi4XW03mypSl62mMt2g=; b=cqudpZTk/eCDpeaA9xPBgfdse8niTypxRIh8EyM2HRuWK/xdaMPPZkawKSXB+iuZcb fRvZr/GEMtcFP2AOVgGtk4m8tUQ5NLGhRnaM4Ag3J1RYvgc14Jg+bM4EiHnb7j2usfGy noVmJnxY0TXokqT+EkZe3j+W0J1p6ZWpWbeFNb6vjhaXjtPCisoFU4jK+TVjGdNwLGVa UhMVrjsI8JLEVVemmg+p9fB6GW8iWvy+JaMGPLRSeI0n0Q/e/oeUS6S9KzDlmOO80q7w 2VyteyIAsJLhXL5Jh4yb3GQzGjHvNItMqWDu1p7BpPRWeuFbuJism8PjYhlYGV/vvlY1 D9PA== X-Gm-Message-State: AOAM533Ptmw8203lEHJBxrGh/r9pW4xHNdjPsoohoPbuVrahEcLJhUrq EVwd03ioNbMOKjXBfXxuSus3u+KhT30= X-Google-Smtp-Source: ABdhPJyKaXYgAh0bi0RvkcudASq5ue8Rma4cM+rn2wQ/db+OjCNO7viThTSnlKmZz6Qi7T50bw7hWQ== X-Received: by 2002:adf:e8c1:: with SMTP id k1mr5577901wrn.257.1639045815717; Thu, 09 Dec 2021 02:30:15 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p62sm5297069wmp.10.2021.12.09.02.30.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:15 -0800 (PST) Message-Id: <56bb69af36e5e3180d53586d30048d5033a01d14.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:29:59 +0000 Subject: [PATCH v5 05/15] diff --color-moved=zebra: fix alternate coloring Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood b0a2ba4776 ("diff --color-moved=zebra: be stricter with color alternation", 2018-11-23) sought to avoid using the alternate colors unless there are two adjacent moved blocks of the same sign. Unfortunately it contains two bugs that prevented it from fixing the problem properly. Firstly `last_symbol` is reset at the start of each iteration of the loop losing the symbol of the last line and secondly when deciding whether to use the alternate color it should be checking if the current line is the same sign of the last line, not a different sign. The combination of the two errors means that we still use the alternate color when we should do but we also use it when we shouldn't. This is most noticable when using --color-moved-ws=allow-indentation-change with hunks like -this line gets indented + this line gets indented where the post image is colored with newMovedAlternate rather than newMoved. While this does not matter much, the next commit will change the coloring to be correct in this case, so lets fix the bug here to make it clear why the output is changing and add a regression test. Signed-off-by: Phillip Wood --- diff.c | 4 +-- t/t4015-diff-whitespace.sh | 72 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 74 insertions(+), 2 deletions(-) diff --git a/diff.c b/diff.c index 1e1b5127d15..53f0df75329 100644 --- a/diff.c +++ b/diff.c @@ -1176,6 +1176,7 @@ static void mark_color_as_moved(struct diff_options *o, struct moved_block *pmb = NULL; /* potentially moved blocks */ int pmb_nr = 0, pmb_alloc = 0; int n, flipped_block = 0, block_length = 0; + enum diff_symbol last_symbol = 0; for (n = 0; n < o->emitted_symbols->nr; n++) { @@ -1183,7 +1184,6 @@ static void mark_color_as_moved(struct diff_options *o, struct moved_entry *key; struct moved_entry *match = NULL; struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; - enum diff_symbol last_symbol = 0; switch (l->s) { case DIFF_SYMBOL_PLUS: @@ -1251,7 +1251,7 @@ static void mark_color_as_moved(struct diff_options *o, &pmb, &pmb_alloc, &pmb_nr); - if (contiguous && pmb_nr && last_symbol != l->s) + if (contiguous && pmb_nr && last_symbol == l->s) flipped_block = (flipped_block + 1) % 2; else flipped_block = 0; diff --git a/t/t4015-diff-whitespace.sh b/t/t4015-diff-whitespace.sh index 308dc136596..4e0fd76c6c5 100755 --- a/t/t4015-diff-whitespace.sh +++ b/t/t4015-diff-whitespace.sh @@ -1442,6 +1442,78 @@ test_expect_success 'detect permutations inside moved code -- dimmed-zebra' ' test_cmp expected actual ' +test_expect_success 'zebra alternate color is only used when necessary' ' + cat >old.txt <<-\EOF && + line 1A should be marked as oldMoved newMovedAlternate + line 1B should be marked as oldMoved newMovedAlternate + unchanged + line 2A should be marked as oldMoved newMovedAlternate + line 2B should be marked as oldMoved newMovedAlternate + line 3A should be marked as oldMovedAlternate newMoved + line 3B should be marked as oldMovedAlternate newMoved + unchanged + line 4A should be marked as oldMoved newMovedAlternate + line 4B should be marked as oldMoved newMovedAlternate + line 5A should be marked as oldMovedAlternate newMoved + line 5B should be marked as oldMovedAlternate newMoved + line 6A should be marked as oldMoved newMoved + line 6B should be marked as oldMoved newMoved + EOF + cat >new.txt <<-\EOF && + line 1A should be marked as oldMoved newMovedAlternate + line 1B should be marked as oldMoved newMovedAlternate + unchanged + line 3A should be marked as oldMovedAlternate newMoved + line 3B should be marked as oldMovedAlternate newMoved + line 2A should be marked as oldMoved newMovedAlternate + line 2B should be marked as oldMoved newMovedAlternate + unchanged + line 6A should be marked as oldMoved newMoved + line 6B should be marked as oldMoved newMoved + line 4A should be marked as oldMoved newMovedAlternate + line 4B should be marked as oldMoved newMovedAlternate + line 5A should be marked as oldMovedAlternate newMoved + line 5B should be marked as oldMovedAlternate newMoved + EOF + test_expect_code 1 git diff --no-index --color --color-moved=zebra \ + --color-moved-ws=allow-indentation-change \ + old.txt new.txt >output && + grep -v index output | test_decode_color >actual && + cat >expected <<-\EOF && + diff --git a/old.txt b/new.txt + --- a/old.txt + +++ b/new.txt + @@ -1,14 +1,14 @@ + -line 1A should be marked as oldMoved newMovedAlternate + -line 1B should be marked as oldMoved newMovedAlternate + + line 1A should be marked as oldMoved newMovedAlternate + + line 1B should be marked as oldMoved newMovedAlternate + unchanged + -line 2A should be marked as oldMoved newMovedAlternate + -line 2B should be marked as oldMoved newMovedAlternate + -line 3A should be marked as oldMovedAlternate newMoved + -line 3B should be marked as oldMovedAlternate newMoved + + line 3A should be marked as oldMovedAlternate newMoved + + line 3B should be marked as oldMovedAlternate newMoved + + line 2A should be marked as oldMoved newMovedAlternate + + line 2B should be marked as oldMoved newMovedAlternate + unchanged + -line 4A should be marked as oldMoved newMovedAlternate + -line 4B should be marked as oldMoved newMovedAlternate + -line 5A should be marked as oldMovedAlternate newMoved + -line 5B should be marked as oldMovedAlternate newMoved + -line 6A should be marked as oldMoved newMoved + -line 6B should be marked as oldMoved newMoved + + line 6A should be marked as oldMoved newMoved + + line 6B should be marked as oldMoved newMoved + + line 4A should be marked as oldMoved newMovedAlternate + + line 4B should be marked as oldMoved newMovedAlternate + + line 5A should be marked as oldMovedAlternate newMoved + + line 5B should be marked as oldMovedAlternate newMoved + EOF + test_cmp expected actual +' + test_expect_success 'cmd option assumes configured colored-moved' ' test_config color.diff.oldMoved "magenta" && test_config color.diff.newMoved "cyan" && From patchwork Thu Dec 9 10:30:00 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666319 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 965CDC433F5 for ; Thu, 9 Dec 2021 10:30:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234640AbhLIKd7 (ORCPT ); Thu, 9 Dec 2021 05:33:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34374 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234518AbhLIKdv (ORCPT ); Thu, 9 Dec 2021 05:33:51 -0500 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 36CACC061746 for ; Thu, 9 Dec 2021 02:30:18 -0800 (PST) Received: by mail-wr1-x42b.google.com with SMTP id a9so8826000wrr.8 for ; Thu, 09 Dec 2021 02:30:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=63o3P4q1ZFH6Z3d6V3ABrwdZeiLXPkyAw8esWLYB2Wc=; b=fs7SpRqQugB6VIZB6kwTc80kj22sXs2eWDvIqj1QCTaCQC3bLHHGSrvcPbx0NZZgQl xsJNhgmq0H3wC0+tjXMtQzfzzw6orjBNuHuSVs1KJVWqrhJXvZ3zxyt3OHB91VmolQN1 Pm5F1h8Y8CcDPrRVbiZZ7uvA3xoPdbjaCZMeJtrva3bqz1HuiBQI8UoriRtFApF00kn9 aSIpDwZjtHA+YwkJFMIfe5HTMNkh5KG2NOboDya7oWTiX1N5zX3UuRSDGGrn9h4kbGq8 OCdgw5TwXscUinQKfqGPYpvfRzsEc0WJDgMioykf073tkB3Rmc86mDIsuGCZQOFvjID+ Z58g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=63o3P4q1ZFH6Z3d6V3ABrwdZeiLXPkyAw8esWLYB2Wc=; b=pQxhoHSsyr0GwwZi+WVORl6EX7yCkcAzBygTAhW0TnymuIeRebarXSY3e+HZ5a980C bTDS3A+UFq6MIOAv4yPhd3+kzpC+K4yazJgB2hRsrH8/vCvaOj8cvD7hzprD8NqJynPM NVlM09f9CnsUx2WgAwzuw/gZUf8bxRq3NsfLqAl99fWI4Pjrht4zZh13GjvkfwL4IaMU Q4uLUbKs5FdNS1y55HpgQYQNb4AJFPiWEpgtZp4Z2dB8fX7xsDiL/Sj+mNdhQWelxsqC uSl+6JzFfIjlNtTjQqsf2GyGCVAbJGGaJ7VTpqnoLqe+klcJopqQs2zMDGLugq0r2sIK nl5g== X-Gm-Message-State: AOAM530CPfjjFCAljtcMvAGEkshDdfyJlecyiE6yrm8F3wysHR651kMr oHOCHfawCphhGgUzE9FbZEMiX/7jJYc= X-Google-Smtp-Source: ABdhPJxLxqYEMCmKj8nKsSoWFZkjW0hjY5uhxeflMlzt6jAj+eqBeeFO454gv0KZI8nn70jja8VH0w== X-Received: by 2002:a05:6000:252:: with SMTP id m18mr5362591wrz.117.1639045816529; Thu, 09 Dec 2021 02:30:16 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 10sm7222277wrb.75.2021.12.09.02.30.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:16 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:00 +0000 Subject: [PATCH v5 06/15] diff --color-moved: avoid false short line matches and bad zebra coloring Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood When marking moved lines it is possible for a block of potential matched lines to extend past a change in sign when there is a sequence of added lines whose text matches the text of a sequence of deleted and added lines. Most of the time either `match` will be NULL or `pmb_advance_or_null()` will fail when the loop encounters a change of sign but there are corner cases where `match` is non-NULL and `pmb_advance_or_null()` successfully advances the moved block despite the change in sign. One consequence of this is highlighting a short line as moved when it should not be. For example -moved line # Correctly highlighted as moved +short line # Wrongly highlighted as moved context +moved line # Correctly highlighted as moved +short line context -short line The other consequence is coloring a moved addition following a moved deletion in the wrong color. In the example below the first "+moved line 3" should be highlighted as newMoved not newMovedAlternate. -moved line 1 # Correctly highlighted as oldMoved -moved line 2 # Correctly highlighted as oldMovedAlternate +moved line 3 # Wrongly highlighted as newMovedAlternate context # Everything else is highlighted correctly +moved line 2 +moved line 3 context +moved line 1 -moved line 3 These false matches are more likely when using --color-moved-ws with the exception of --color-moved-ws=allow-indentation-change which ties the sign of the current whitespace delta to the sign of the line to avoid this problem. The fix is to check that the sign of the new line being matched is the same as the sign of the line that started the block of potential matches. Signed-off-by: Phillip Wood --- diff.c | 17 ++++++---- t/t4015-diff-whitespace.sh | 65 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 76 insertions(+), 6 deletions(-) diff --git a/diff.c b/diff.c index 53f0df75329..efba2789354 100644 --- a/diff.c +++ b/diff.c @@ -1176,7 +1176,7 @@ static void mark_color_as_moved(struct diff_options *o, struct moved_block *pmb = NULL; /* potentially moved blocks */ int pmb_nr = 0, pmb_alloc = 0; int n, flipped_block = 0, block_length = 0; - enum diff_symbol last_symbol = 0; + enum diff_symbol moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER; for (n = 0; n < o->emitted_symbols->nr; n++) { @@ -1202,7 +1202,7 @@ static void mark_color_as_moved(struct diff_options *o, flipped_block = 0; } - if (!match) { + if (pmb_nr && (!match || l->s != moved_symbol)) { int i; if (!adjust_last_block(o, n, block_length) && @@ -1219,12 +1219,13 @@ static void mark_color_as_moved(struct diff_options *o, pmb_nr = 0; block_length = 0; flipped_block = 0; - last_symbol = l->s; + } + if (!match) { + moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER; continue; } if (o->color_moved == COLOR_MOVED_PLAIN) { - last_symbol = l->s; l->flags |= DIFF_SYMBOL_MOVED_LINE; continue; } @@ -1251,11 +1252,16 @@ static void mark_color_as_moved(struct diff_options *o, &pmb, &pmb_alloc, &pmb_nr); - if (contiguous && pmb_nr && last_symbol == l->s) + if (contiguous && pmb_nr && moved_symbol == l->s) flipped_block = (flipped_block + 1) % 2; else flipped_block = 0; + if (pmb_nr) + moved_symbol = l->s; + else + moved_symbol = DIFF_SYMBOL_BINARY_DIFF_HEADER; + block_length = 0; } @@ -1265,7 +1271,6 @@ static void mark_color_as_moved(struct diff_options *o, if (flipped_block && o->color_moved != COLOR_MOVED_BLOCKS) l->flags |= DIFF_SYMBOL_MOVED_LINE_ALT; } - last_symbol = l->s; } adjust_last_block(o, n, block_length); diff --git a/t/t4015-diff-whitespace.sh b/t/t4015-diff-whitespace.sh index 4e0fd76c6c5..15782c879d2 100755 --- a/t/t4015-diff-whitespace.sh +++ b/t/t4015-diff-whitespace.sh @@ -1514,6 +1514,71 @@ test_expect_success 'zebra alternate color is only used when necessary' ' test_cmp expected actual ' +test_expect_success 'short lines of opposite sign do not get marked as moved' ' + cat >old.txt <<-\EOF && + this line should be marked as moved + unchanged + unchanged + unchanged + unchanged + too short + this line should be marked as oldMoved newMoved + this line should be marked as oldMovedAlternate newMoved + unchanged 1 + unchanged 2 + unchanged 3 + unchanged 4 + this line should be marked as oldMoved newMoved/newMovedAlternate + EOF + cat >new.txt <<-\EOF && + too short + unchanged + unchanged + this line should be marked as moved + too short + unchanged + unchanged + this line should be marked as oldMoved newMoved/newMovedAlternate + unchanged 1 + unchanged 2 + this line should be marked as oldMovedAlternate newMoved + this line should be marked as oldMoved newMoved/newMovedAlternate + unchanged 3 + this line should be marked as oldMoved newMoved + unchanged 4 + EOF + test_expect_code 1 git diff --no-index --color --color-moved=zebra \ + old.txt new.txt >output && cat output && + grep -v index output | test_decode_color >actual && + cat >expect <<-\EOF && + diff --git a/old.txt b/new.txt + --- a/old.txt + +++ b/new.txt + @@ -1,13 +1,15 @@ + -this line should be marked as moved + +too short + unchanged + unchanged + +this line should be marked as moved + +too short + unchanged + unchanged + -too short + -this line should be marked as oldMoved newMoved + -this line should be marked as oldMovedAlternate newMoved + +this line should be marked as oldMoved newMoved/newMovedAlternate + unchanged 1 + unchanged 2 + +this line should be marked as oldMovedAlternate newMoved + +this line should be marked as oldMoved newMoved/newMovedAlternate + unchanged 3 + +this line should be marked as oldMoved newMoved + unchanged 4 + -this line should be marked as oldMoved newMoved/newMovedAlternate + EOF + test_cmp expect actual +' + test_expect_success 'cmd option assumes configured colored-moved' ' test_config color.diff.oldMoved "magenta" && test_config color.diff.newMoved "cyan" && From patchwork Thu Dec 9 10:30:01 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666321 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 71B23C433EF for ; Thu, 9 Dec 2021 10:30:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234560AbhLIKd7 (ORCPT ); Thu, 9 Dec 2021 05:33:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34368 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234549AbhLIKdw (ORCPT ); Thu, 9 Dec 2021 05:33:52 -0500 Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E7B68C0617A1 for ; Thu, 9 Dec 2021 02:30:18 -0800 (PST) Received: by mail-wr1-x433.google.com with SMTP id i5so8868772wrb.2 for ; Thu, 09 Dec 2021 02:30:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=QMoWx+vto78ZYKdHTzHFdPgdOaprERVbNGfNe2DRDPg=; b=qKEZjmRp66CBiIC7f135+4JrHAc43c3p2OtllsnUXWMZvgSBugDlEkcuhqw4ARjaRH WOTRa4grOkttxyJ7Z+lFUWsBHCYT//sn0NRXTyviagz1E4r3CwBUqXef7QnxFlo2aZkJ xnKIDIZWmkxMg818XbesKpzNarQLRMF3bn7XtCJRamPZ61e9wvyLvwBASwZ33ZiSHeiB q7+mUgswSvebsrFpYVmi2FluUwRtkLehOpHZcVcgNS/wsJk5PgoqiGC7CduA/6UqBSnG r6Zt3eYVgGtpdESHR67RlASwC9/X1omow/zxYscIA6+zKOlxPX4uRepTdclGtbzSU/SB fpjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=QMoWx+vto78ZYKdHTzHFdPgdOaprERVbNGfNe2DRDPg=; b=KDgtY5SaN1zvuFzZR2USczcxCsWiJkSaEa7yhDQdKrb23gYb9roq8jsK0rAUEFXjqu /86rfURINKpu04t7yBiy2V7Wrw3efO2v8hP7Iz9oLrEblOL3PU2eG0GBsX8OwnyVcjjs LVR8NcWiKAPBZj9uI99fl/X1D+oqWrmd2TDql2a9FETEEjBiKAeuMiouFFpu0WARBoRP 5+Mka3MEsl0l6zDoqwjpCu2G2fHn2RM1PbwpljyqKPj0SJaPlm4uJBsS8uc+TDBlUKpG tGAIWfC0SqmuCQYZ59o3d4tcS6KsYkKDA5zsKPj6iAfu3uSWUL4C6+qICoL8l4r+rFL4 u9YA== X-Gm-Message-State: AOAM53305ZwiKXnh/yf1WiY3g5qiCyNcaI7F9ZUAiBoc0DNRIEm90fft nqW16IdK3bk+4ytrLKUc3EYN9dI7040= X-Google-Smtp-Source: ABdhPJx30WOP6JgBvi9NGIZyrv+3G2n182WFXQalLC21bCouaK1mogGFLj3Mzi/x4zLT8TcIGh830w== X-Received: by 2002:a5d:404d:: with SMTP id w13mr5135858wrp.293.1639045817394; Thu, 09 Dec 2021 02:30:17 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id q8sm5424795wrx.71.2021.12.09.02.30.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:17 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:01 +0000 Subject: [PATCH v5 07/15] diff: simplify allow-indentation-change delta calculation Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Now that we reliably end a block when the sign changes we don't need the whitespace delta calculation to rely on the sign. Signed-off-by: Phillip Wood --- diff.c | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-) diff --git a/diff.c b/diff.c index efba2789354..9aff167be27 100644 --- a/diff.c +++ b/diff.c @@ -864,23 +864,17 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a, a_width = a->indent_width, b_off = b->indent_off, b_width = b->indent_width; - int delta; if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE) { *out = INDENT_BLANKLINE; return 1; } - if (a->s == DIFF_SYMBOL_PLUS) - delta = a_width - b_width; - else - delta = b_width - a_width; - if (a_len - a_off != b_len - b_off || memcmp(a->line + a_off, b->line + b_off, a_len - a_off)) return 0; - *out = delta; + *out = a_width - b_width; return 1; } @@ -924,10 +918,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, * match those of the current block and that the text of 'l' and 'cur' * after the indentation match. */ - if (cur->es->s == DIFF_SYMBOL_PLUS) - delta = a_width - c_width; - else - delta = c_width - a_width; + delta = c_width - a_width; /* * If the previous lines of this block were all blank then set its From patchwork Thu Dec 9 10:30:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666325 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 70439C433F5 for ; Thu, 9 Dec 2021 10:30:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234469AbhLIKeB (ORCPT ); Thu, 9 Dec 2021 05:34:01 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34388 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232317AbhLIKdx (ORCPT ); Thu, 9 Dec 2021 05:33:53 -0500 Received: from mail-wm1-x331.google.com (mail-wm1-x331.google.com [IPv6:2a00:1450:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0DC52C0617A1 for ; Thu, 9 Dec 2021 02:30:20 -0800 (PST) Received: by mail-wm1-x331.google.com with SMTP id i8-20020a7bc948000000b0030db7b70b6bso6182374wml.1 for ; Thu, 09 Dec 2021 02:30:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=+/NY0FSLLgoOM2WL1cJXCz+GAAkWsSqC7KSVILVwygw=; b=IZZi2DNwcoOaogFj0riIh8SiH1i5CR3Qi9v8Zzs6bl4dv9VsFY4bNfZUsSWnihL8C3 mbptttCGU/8MKCPv5MhZzK6XYlReVpINzOX3V6GD/6onCrGyH59N2aywiXz/Jdfh2lRh TB6QtH5Q71F2X+ASgx692JchnX/R1FqxP9Koc9RZNPFdC18drY0Mt+QabT58wFXDT5+D AsU7ca32fo6in3W+PGj6O7PX6ZmNaDdZjU92rVPg92kP3XTnRqlrUhjKFCoxwlRbjTLE 5XaZa94y7hYTSvCroXglGo+s31HtrTTwh6YdcG3c4IgAVFHAKvD/8MWYRZmo+NhTsH5s tAPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=+/NY0FSLLgoOM2WL1cJXCz+GAAkWsSqC7KSVILVwygw=; b=mKuZX+JAZFmluwl1rGD29ERKxM40vfp8DiFJSqKQqj8HMXrvjTQ8det8PC0Y981gVH fsyKPhAPfXwxDltJbV3El0nGHqcu1US8lLpndPsNz1BC9ZP57OeAq1vnFqCOQcxNGyvy jliuHlOuKePZzf35NEVRHwOqeEnY3Go6GDAUdFPEHpXTq0IP0aPlgZhFQNHBdXAyIdcv PFzVEM1eVSqkqVHP4vTnVEeLHrQ5d7BHBtIwgeHW3LkrSkQFBsQxpiH1JeyB9Tt2JGmX cMZ4NYJExQ1QJCHtt9NfjEtgNuxV6hd2wm+w3I7W7ue/QHM17MHpTO7mHZeM3ekjVZF4 X3Sw== X-Gm-Message-State: AOAM5334h//rJo/x67+2UrlPAmWeSwkhQxu6HqcgMUV35JvizQ6IQWpc 26oEnTG6psywC5z73aY+qs517i9jhrk= X-Google-Smtp-Source: ABdhPJzVRR885HEErq3/F2kaOwGLNWmlNnPOhHYPrxe2GA+YrVLdxOJ+LOCifOO9lMwb6sdepAaCnw== X-Received: by 2002:a1c:447:: with SMTP id 68mr6119040wme.69.1639045818246; Thu, 09 Dec 2021 02:30:18 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z6sm5334302wrm.93.2021.12.09.02.30.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:17 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:02 +0000 Subject: [PATCH v5 08/15] diff --color-moved-ws=allow-indentation-change: simplify and optimize Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood If we already have a block of potentially moved lines then as we move down the diff we need to check if the next line of each potentially moved line matches the current line of the diff. The implementation of --color-moved-ws=allow-indentation-change was needlessly performing this check on all the lines in the diff that matched the current line rather than just the current line. To exacerbate the problem finding all the other lines in the diff that match the current line involves a fuzzy lookup so we were wasting even more time performing a second comparison to filter out the non-matching lines. Fixing this reduces time to run git diff --color-moved-ws=allow-indentation-change v2.28.0 v2.29.0 by 93% compared to master and simplifies the code. Test HEAD^ HEAD --------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.35+0.03) 0.38(0.35+0.03) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.86 (0.80+0.06) 0.87(0.83+0.04) +1.2% 4002.3: diff --color-moved-ws=allow-indentation-change large change 19.01(18.93+0.06) 0.97(0.92+0.04) -94.9% 4002.4: log --no-color-moved --no-color-moved-ws 1.16 (1.06+0.09) 1.17(1.06+0.10) +0.9% 4002.5: log --color-moved --no-color-moved-ws 1.32 (1.25+0.07) 1.32(1.24+0.08) +0.0% 4002.6: log --color-moved-ws=allow-indentation-change 1.71 (1.64+0.06) 1.36(1.25+0.10) -20.5% Test master HEAD --------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.35+0.03) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.87(0.83+0.04) +8.7% 4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.97(0.92+0.04) -93.2% 4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.17(1.06+0.10) +1.7% 4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.32(1.24+0.08) +1.5% 4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.36(1.25+0.10) -20.0% Helped-by: Jeff King Signed-off-by: Phillip Wood --- diff.c | 70 +++++++++++++++++----------------------------------------- 1 file changed, 20 insertions(+), 50 deletions(-) diff --git a/diff.c b/diff.c index 9aff167be27..78a486021ab 100644 --- a/diff.c +++ b/diff.c @@ -879,37 +879,21 @@ static int compute_ws_delta(const struct emitted_diff_symbol *a, return 1; } -static int cmp_in_block_with_wsd(const struct diff_options *o, - const struct moved_entry *cur, - const struct moved_entry *match, - struct moved_block *pmb, - int n) -{ - struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; - int al = cur->es->len, bl = match->es->len, cl = l->len; +static int cmp_in_block_with_wsd(const struct moved_entry *cur, + const struct emitted_diff_symbol *l, + struct moved_block *pmb) +{ + int al = cur->es->len, bl = l->len; const char *a = cur->es->line, - *b = match->es->line, - *c = l->line; + *b = l->line; int a_off = cur->es->indent_off, a_width = cur->es->indent_width, - c_off = l->indent_off, - c_width = l->indent_width; + b_off = l->indent_off, + b_width = l->indent_width; int delta; - /* - * We need to check if 'cur' is equal to 'match'. As those - * are from the same (+/-) side, we do not need to adjust for - * indent changes. However these were found using fuzzy - * matching so we do have to check if they are equal. Here we - * just check the lengths. We delay calling memcmp() to check - * the contents until later as if the length comparison for a - * and c fails we can avoid the call all together. - */ - if (al != bl) - return 1; - /* If 'l' and 'cur' are both blank then they match. */ - if (a_width == INDENT_BLANKLINE && c_width == INDENT_BLANKLINE) + if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE) return 0; /* @@ -918,7 +902,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, * match those of the current block and that the text of 'l' and 'cur' * after the indentation match. */ - delta = c_width - a_width; + delta = b_width - a_width; /* * If the previous lines of this block were all blank then set its @@ -927,9 +911,8 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, if (pmb->wsd == INDENT_BLANKLINE) pmb->wsd = delta; - return !(delta == pmb->wsd && al - a_off == cl - c_off && - !memcmp(a, b, al) && ! - memcmp(a + a_off, c + c_off, al - a_off)); + return !(delta == pmb->wsd && al - a_off == bl - b_off && + !memcmp(a + a_off, b + b_off, al - a_off)); } static int moved_entry_cmp(const void *hashmap_cmp_fn_data, @@ -1030,36 +1013,23 @@ static void pmb_advance_or_null(struct diff_options *o, } static void pmb_advance_or_null_multi_match(struct diff_options *o, - struct moved_entry *match, - struct hashmap *hm, + struct emitted_diff_symbol *l, struct moved_block *pmb, - int pmb_nr, int n) + int pmb_nr) { int i; - char *got_match = xcalloc(1, pmb_nr); - - hashmap_for_each_entry_from(hm, match, ent) { - for (i = 0; i < pmb_nr; i++) { - struct moved_entry *prev = pmb[i].match; - struct moved_entry *cur = (prev && prev->next_line) ? - prev->next_line : NULL; - if (!cur) - continue; - if (!cmp_in_block_with_wsd(o, cur, match, &pmb[i], n)) - got_match[i] |= 1; - } - } for (i = 0; i < pmb_nr; i++) { - if (got_match[i]) { + struct moved_entry *prev = pmb[i].match; + struct moved_entry *cur = (prev && prev->next_line) ? + prev->next_line : NULL; + if (cur && !cmp_in_block_with_wsd(cur, l, &pmb[i])) { /* Advance to the next line */ - pmb[i].match = pmb[i].match->next_line; + pmb[i].match = cur; } else { moved_block_clear(&pmb[i]); } } - - free(got_match); } static int shrink_potential_moved_blocks(struct moved_block *pmb, @@ -1223,7 +1193,7 @@ static void mark_color_as_moved(struct diff_options *o, if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) - pmb_advance_or_null_multi_match(o, match, hm, pmb, pmb_nr, n); + pmb_advance_or_null_multi_match(o, l, pmb, pmb_nr); else pmb_advance_or_null(o, match, hm, pmb, pmb_nr); From patchwork Thu Dec 9 10:30:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666327 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CED75C433EF for ; Thu, 9 Dec 2021 10:30:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234635AbhLIKeD (ORCPT ); Thu, 9 Dec 2021 05:34:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34396 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234470AbhLIKdy (ORCPT ); Thu, 9 Dec 2021 05:33:54 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BCCB2C061353 for ; Thu, 9 Dec 2021 02:30:20 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id 77-20020a1c0450000000b0033123de3425so6219760wme.0 for ; Thu, 09 Dec 2021 02:30:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=nXlUzK0eG1nytfPPrkrw0gtj2yvs5u/jSO3jH2X9/oQ=; b=owjJK6X4p+JTjFnWr/mNHTlciPp+YQc/xgS2Gf0wHNOgLqWFGB6jCBuLVYK5ulC7ez OMrpTyf+bpx+niTGE+B6Xa7/pLeGQWanuNH89sb3vGf5fifc3P4Uj4PTAD48Tp74SUyf WDAjcQspiKWMtrCCwHBmUFLloBrRX1SFs9BYToWKZvI75gIcjbZ1b9LFDV+Ap+WMB6fT wHbRYKQoxO1msHrRekra8yY8Q9/1KccvyUc4MYjBQo8zyJRoIblIKjc98hpCJWXQ0MJP 0D+jjHLUTJSRH8X/U3BHVqvWUaHavQSGzRqRjV4i3F3hdjog1ayxLnwUH39Yq+TTq1BJ gT9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=nXlUzK0eG1nytfPPrkrw0gtj2yvs5u/jSO3jH2X9/oQ=; b=zhg1gg19ryNyD9sOhNJBn9qqYBE8YFAASm+z/K42rDMnLUPKA7kHCG+lNQy4vvm30b isXGhvtpZH+MbQz+Gnb+ugEIQbk2rxFPeuDi2dfWjrijiEv8OBTPvl1xttYJgN3a4Bqm JPm2EGyWWv9T5k3j7o522qF42GBasuTuY340SEzdUc4wj0sit+u2X6VXKy7rjVnKydjJ REGwRWcZbIV56mGVvujUGYexdDs04ThfGyxShWOcVKhzys7W3ExVXm7RYuqSJ/baq37v elg2x+SweT56QvfkSYkqaLCUjpTSy1+jKnMe/+yjITf/zBQaAE76fJhqVJfsLPag5d05 vb0A== X-Gm-Message-State: AOAM530iWJbJT7EanQuc9LjpVj1urEO4XMFTNuMZlGsO06HjY879ruzd yemrhhXyOH7e9PvHFSxgKUHkag0xyRY= X-Google-Smtp-Source: ABdhPJyYHOR75EQHbkx7F7uXGwckHvhaXzIbwFhEAxVgKCXOGOBJKkrGSBKDf76cPTGVQ7PQ57FLMg== X-Received: by 2002:a05:600c:378b:: with SMTP id o11mr6120168wmr.157.1639045819123; Thu, 09 Dec 2021 02:30:19 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id x13sm5559894wrr.47.2021.12.09.02.30.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:18 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:03 +0000 Subject: [PATCH v5 09/15] diff --color-moved: call comparison function directly Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood This change will allow us to easily combine pmb_advance_or_null() and pmb_advance_or_null_multi_match() in the next commit. Calling xdiff_compare_lines() directly rather than using a function pointer from the hash map has little effect on the run time. Test HEAD^ HEAD ------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.35+0.03) 0.38(0.32+0.06) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.87(0.83+0.04) 0.87(0.80+0.06) +0.0% 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.92+0.04) 0.97(0.93+0.04) +0.0% 4002.4: log --no-color-moved --no-color-moved-ws 1.17(1.06+0.10) 1.16(1.10+0.05) -0.9% 4002.5: log --color-moved --no-color-moved-ws 1.32(1.24+0.08) 1.31(1.22+0.09) -0.8% 4002.6: log --color-moved-ws=allow-indentation-change 1.36(1.25+0.10) 1.35(1.25+0.10) -0.7% Signed-off-by: Phillip Wood --- diff.c | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/diff.c b/diff.c index 78a486021ab..22e0edac173 100644 --- a/diff.c +++ b/diff.c @@ -994,17 +994,20 @@ static void add_lines_to_move_detection(struct diff_options *o, } static void pmb_advance_or_null(struct diff_options *o, - struct moved_entry *match, - struct hashmap *hm, + struct emitted_diff_symbol *l, struct moved_block *pmb, int pmb_nr) { int i; + unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; + for (i = 0; i < pmb_nr; i++) { struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? prev->next_line : NULL; - if (cur && !hm->cmpfn(o, &cur->ent, &match->ent, NULL)) { + if (cur && xdiff_compare_lines(cur->es->line, cur->es->len, + l->line, l->len, + flags)) { pmb[i].match = cur; } else { pmb[i].match = NULL; @@ -1195,7 +1198,7 @@ static void mark_color_as_moved(struct diff_options *o, COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) pmb_advance_or_null_multi_match(o, l, pmb, pmb_nr); else - pmb_advance_or_null(o, match, hm, pmb, pmb_nr); + pmb_advance_or_null(o, l, pmb, pmb_nr); pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr); From patchwork Thu Dec 9 10:30:04 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666329 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 317E4C433F5 for ; Thu, 9 Dec 2021 10:30:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234734AbhLIKeF (ORCPT ); Thu, 9 Dec 2021 05:34:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34396 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234561AbhLIKdz (ORCPT ); Thu, 9 Dec 2021 05:33:55 -0500 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A79C0C0617A1 for ; Thu, 9 Dec 2021 02:30:21 -0800 (PST) Received: by mail-wr1-x42b.google.com with SMTP id t9so8838882wrx.7 for ; Thu, 09 Dec 2021 02:30:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=p2vb6cLuLTkHSnEEqr1bN8UrIqfnfxxTwYxWo4ujnVY=; b=iEpMVoyQuNBlRU6HVUT0N61kcCV9OUht70bqyNHtxnvSV/6mEzVMFffrYaAQNJkNQA sHDtIQOwHGLqWn1ZqtcVHTm/64tKhkTM6ibd1NSpXzqgwbMwsCYPD1ZfrW9w4eQBCgdz b/IlEyR0Ee0+YALojHJYzNLOFrE8cSgIq2FP2dJAg5SbNUKSqDzsRvifNl4gVgPEJIzl pZObeOkh9WoCpUixMAIA/ailfHhQm6U2iuqOQaTVTj4dqfD8wr7Yr2Ab/ofVDO5LHfeZ iXYPlcLpy4ZaeqNAjDxZu5dEEid2HsEz+GrIwpGKqtQ/jqI2cnuljQM/RQaHRf70J2ce byRQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=p2vb6cLuLTkHSnEEqr1bN8UrIqfnfxxTwYxWo4ujnVY=; b=BFFRgUtmHgMHpwmQJFLUVVMYa7PPs6YaAW5SMPr3H0cnGcbmM/BDlxYYTPx8XWLuFD GOSKqTK0AkhS76wXwqQbIbbKxqnHhcve4lN6eAr6/dyIV3PrmL0pXdllDLIZbU/skuUp QR5Vn3uMhjZx4k5NHfOoiqUyHmbYTvawGVU35thEiJ4W7p0/AxqsnE/NXQXyisI9vcEH Q9SiiSp4agxubyEBSQUO/yFas5chXVDHIcKHUPo/6UrzrtvVME6mPTUr0pqlwHEEZh7L WMK1wd04uW3tjGZLOjQar8M47ADF1jhQP4Fv7oERbpUo2kjMfI5z60S6rno17TLDgCfP 2VLQ== X-Gm-Message-State: AOAM532b0ml/mMnrH2Ce4klca1dSDqwtOSVN8+WJ6yRVCcE4pOA5gLem 0uyL3u1MRM2VhROnYktBWwW7AO/2qFo= X-Google-Smtp-Source: ABdhPJy6FJD/OFGbV/1/KpZwWTp7SKU5yvVXLl9pi/3mHjYPSsA1rPMmj2fi1bnI3bkdwB4v87dRtg== X-Received: by 2002:a5d:5251:: with SMTP id k17mr5409540wrc.482.1639045819978; Thu, 09 Dec 2021 02:30:19 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j8sm5122500wrh.16.2021.12.09.02.30.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:19 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:04 +0000 Subject: [PATCH v5 10/15] diff --color-moved: unify moved block growth functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood After the last two commits pmb_advance_or_null() and pmb_advance_or_null_multi_match() differ only in the comparison they perform. Lets simplify the code by combining them into a single function. Signed-off-by: Phillip Wood --- diff.c | 41 ++++++++++++----------------------------- 1 file changed, 12 insertions(+), 29 deletions(-) diff --git a/diff.c b/diff.c index 22e0edac173..51f092e724e 100644 --- a/diff.c +++ b/diff.c @@ -1002,36 +1002,23 @@ static void pmb_advance_or_null(struct diff_options *o, unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; for (i = 0; i < pmb_nr; i++) { + int match; struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? prev->next_line : NULL; - if (cur && xdiff_compare_lines(cur->es->line, cur->es->len, - l->line, l->len, - flags)) { - pmb[i].match = cur; - } else { - pmb[i].match = NULL; - } - } -} -static void pmb_advance_or_null_multi_match(struct diff_options *o, - struct emitted_diff_symbol *l, - struct moved_block *pmb, - int pmb_nr) -{ - int i; - - for (i = 0; i < pmb_nr; i++) { - struct moved_entry *prev = pmb[i].match; - struct moved_entry *cur = (prev && prev->next_line) ? - prev->next_line : NULL; - if (cur && !cmp_in_block_with_wsd(cur, l, &pmb[i])) { - /* Advance to the next line */ + if (o->color_moved_ws_handling & + COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) + match = cur && + !cmp_in_block_with_wsd(cur, l, &pmb[i]); + else + match = cur && + xdiff_compare_lines(cur->es->line, cur->es->len, + l->line, l->len, flags); + if (match) pmb[i].match = cur; - } else { + else moved_block_clear(&pmb[i]); - } } } @@ -1194,11 +1181,7 @@ static void mark_color_as_moved(struct diff_options *o, continue; } - if (o->color_moved_ws_handling & - COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) - pmb_advance_or_null_multi_match(o, l, pmb, pmb_nr); - else - pmb_advance_or_null(o, l, pmb, pmb_nr); + pmb_advance_or_null(o, l, pmb, pmb_nr); pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr); From patchwork Thu Dec 9 10:30:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666331 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 201A7C433EF for ; Thu, 9 Dec 2021 10:30:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234811AbhLIKeG (ORCPT ); Thu, 9 Dec 2021 05:34:06 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34402 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234450AbhLIKdz (ORCPT ); Thu, 9 Dec 2021 05:33:55 -0500 Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 71755C061746 for ; Thu, 9 Dec 2021 02:30:22 -0800 (PST) Received: by mail-wr1-x42a.google.com with SMTP id a18so8845347wrn.6 for ; Thu, 09 Dec 2021 02:30:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=PvZWtTB+saRNvbTicS6KSTgR/AzyDN0INgP6F8z97h4=; b=SEB/DiHrirc+e7c7hrV3yqiHDmR3ufTsWgfhfDzUADwr8VEnSNd+4u6vI5KOb76Ciq 3JDCuVz9AYAMoBtgJRHHWPWJIxcmUpBGxYfSmQ7a/BbBBEffr3MRVm9PB2UQIcF6k3Y1 U110676/2QHe80bOTwuvHt8P26qspgZ7A+uA9jdM9EqirFecXEcl5Bcwmq6uKedX4EWb QaqTPFacAc8xgsm7cvX5EMrlQ8FZSA1mhoy7JA1jZfuvQS/X8w6OvYPTAUc55P42ql+b Q26qiYzDDGObo1W9Sk0lkhyjegL0WE3CFM2aqVqHRTPMEKoosUdM4o9ZsfV6bpM4l21/ wsTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=PvZWtTB+saRNvbTicS6KSTgR/AzyDN0INgP6F8z97h4=; b=QF56s+fYJbPWddI9Qp+03DEFqVWcquIA8opdHHMNtw0OicPKJbD+vzNMevWr3xzBNo emPqmrsDS13f4Wia9ufJwz0XMU3uyS8Bwo37fa46wRv99cmLmZJ8qUKs6UcCrK2yJZ5e FlYqiA1KrYybAbnA2Ltn8HNr18ferhjV4I4Rjs2GH2IA9QFbi4KbXQwEdso07Lpd7e+q 87mp0jLAy4qSSOOvYfmQSnTMZy0ZdonB6lM2DneOaObrdDd0GIAmha4fnJaGJFsfswNV as0gUtsytzlJrAe5yVywlbEufkZny3HmtZyE/cIGo7rnDHaGo+hKDZr8F2f3xRXyG7LN RooA== X-Gm-Message-State: AOAM531BKJX2DgbNn3x8THOD+KjARBRp72mEyhilbKLBDPsXM2CsR5se IziCBeB+nYq//3aseiR3+UgT0uc0TXQ= X-Google-Smtp-Source: ABdhPJz0OeEY4dcJAePa7r3GuL/jTXM1TU6wrAd4YTcmyXg07qBsFMfRLxAjDa9rnUZup3z6zFP3hw== X-Received: by 2002:adf:cf11:: with SMTP id o17mr5205329wrj.554.1639045820854; Thu, 09 Dec 2021 02:30:20 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id d1sm5175640wrz.92.2021.12.09.02.30.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:20 -0800 (PST) Message-Id: <6199a01454710f23bb96be9c73564365b77b40e5.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:05 +0000 Subject: [PATCH v5 11/15] diff --color-moved: shrink potential moved blocks as we go Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Rather than setting `match` to NULL and then looping over the list of potential matched blocks for a second time to remove blocks with no matches just filter out the blocks with no matches as we go. Signed-off-by: Phillip Wood --- diff.c | 44 ++++++++------------------------------------ 1 file changed, 8 insertions(+), 36 deletions(-) diff --git a/diff.c b/diff.c index 51f092e724e..626fd47aa0e 100644 --- a/diff.c +++ b/diff.c @@ -996,12 +996,12 @@ static void add_lines_to_move_detection(struct diff_options *o, static void pmb_advance_or_null(struct diff_options *o, struct emitted_diff_symbol *l, struct moved_block *pmb, - int pmb_nr) + int *pmb_nr) { - int i; + int i, j; unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; - for (i = 0; i < pmb_nr; i++) { + for (i = 0, j = 0; i < *pmb_nr; i++) { int match; struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? @@ -1015,38 +1015,12 @@ static void pmb_advance_or_null(struct diff_options *o, match = cur && xdiff_compare_lines(cur->es->line, cur->es->len, l->line, l->len, flags); - if (match) - pmb[i].match = cur; - else - moved_block_clear(&pmb[i]); - } -} - -static int shrink_potential_moved_blocks(struct moved_block *pmb, - int pmb_nr) -{ - int lp, rp; - - /* Shrink the set of potential block to the remaining running */ - for (lp = 0, rp = pmb_nr - 1; lp <= rp;) { - while (lp < pmb_nr && pmb[lp].match) - lp++; - /* lp points at the first NULL now */ - - while (rp > -1 && !pmb[rp].match) - rp--; - /* rp points at the last non-NULL */ - - if (lp < pmb_nr && rp > -1 && lp < rp) { - pmb[lp] = pmb[rp]; - memset(&pmb[rp], 0, sizeof(pmb[rp])); - rp--; - lp++; + if (match) { + pmb[j] = pmb[i]; + pmb[j++].match = cur; } } - - /* Remember the number of running sets */ - return rp + 1; + *pmb_nr = j; } static void fill_potential_moved_blocks(struct diff_options *o, @@ -1181,9 +1155,7 @@ static void mark_color_as_moved(struct diff_options *o, continue; } - pmb_advance_or_null(o, l, pmb, pmb_nr); - - pmb_nr = shrink_potential_moved_blocks(pmb, pmb_nr); + pmb_advance_or_null(o, l, pmb, &pmb_nr); if (pmb_nr == 0) { int contiguous = adjust_last_block(o, n, block_length); From patchwork Thu Dec 9 10:30:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666333 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B0944C433EF for ; Thu, 9 Dec 2021 10:30:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234915AbhLIKeH (ORCPT ); Thu, 9 Dec 2021 05:34:07 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34412 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234554AbhLIKd4 (ORCPT ); Thu, 9 Dec 2021 05:33:56 -0500 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5F7D0C061746 for ; Thu, 9 Dec 2021 02:30:23 -0800 (PST) Received: by mail-wm1-x32f.google.com with SMTP id k37-20020a05600c1ca500b00330cb84834fso6183673wms.2 for ; Thu, 09 Dec 2021 02:30:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=hbX6ChgF1/7zCe8TRq2mAwsHjDZd1Mp8/GA16/PwtSw=; b=i+Pz3PR1ojL43V8shzQXD3V3fDTLvX2rs07xdIu1/MvNjV4EwdhqckLAhRzUW5XWae hGFg5F+zRZZJVQLstrGWs6qsJXumq8REEv0P85FI/KT+4vtxpbOxVgYnaNGHvTGMzHsO gpTKvBIOBXr5yJyEQhvc7vZdeUByZY6c8WlCvI+GyJqdgm1JdOgMtybQ2bGyI0dgpdKm kViOYdmwMcIitiota1fWBApct93TNRZQHPxqH7Mqqng1zuHu/x0NTMSXOokFFOm5aLK7 e4cmPjjNy9tCzX5YNKlsaK4S2Rb5u9AgVSHe2v0zGY33iU7awPNwkwRxKZRtSXspVHE/ s/Fw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=hbX6ChgF1/7zCe8TRq2mAwsHjDZd1Mp8/GA16/PwtSw=; b=nNOJbYkrgpycsu9qnundG13I4J2Am+/wfUHTr2OZeuLYsd04+p7M+89z4mkOzYfCIN 54w2ecIdn/6UBL0CbpA2g7I9OPkZN039qVOmrSPMHaufSbUeMwj/cTYmsI+BuuX/ZnXO bSpAm4NbTyDV6fRUdEw6R4BTY05oWBOudZRiktNFFJEX7LXc2TZlLtUCqqSdcKfjKJvU HgwMVB/UTPcT7H81+Kjuq8/JfzANa2nksJIPtjaRlGRTVPnigVPKR6a9Icf4hz0jngQm vV5ZMH1FuOJ+WfVTc95cHMgoCfFs1nxxz0ZU0FoPsLINPTPdDYmCvhac7X0UHYcXWY/B yZSQ== X-Gm-Message-State: AOAM533lKUadGCSq0xzwSeO4xZYudHd1OgdbWEOgJHca2N1yRI5fKhcB bwaudQt5KRN0ZqJJLO5XZlqYr2ppvok= X-Google-Smtp-Source: ABdhPJwoPhjoMjz9gKVDfA5exetBM6IJfKR3O+A+0kZCyWpfomYszE70v77dD7QuDfO2vd7YeQbeIg== X-Received: by 2002:a05:600c:6024:: with SMTP id az36mr4130933wmb.11.1639045821643; Thu, 09 Dec 2021 02:30:21 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id r83sm8482093wma.22.2021.12.09.02.30.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:21 -0800 (PST) Message-Id: <1db84490ee42bf8ad681d217de00a902ce9734c2.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:06 +0000 Subject: [PATCH v5 12/15] diff --color-moved: stop clearing potential moved blocks Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood moved_block_clear() was introduced in 74d156f4a1 ("diff --color-moved-ws: fix double free crash", 2018-10-04) to free the memory that was allocated when initializing a potential moved block. However since 21536d077f ("diff --color-moved-ws: modify allow-indentation-change", 2018-11-23) initializing a potential moved block no longer allocates any memory. Up until the last commit we were relying on moved_block_clear() to set the `match` pointer to NULL when a block stopped matching, but since that commit we do not clear a moved block that does not match so it does not make sense to clear them elsewhere. Signed-off-by: Phillip Wood --- diff.c | 11 ----------- 1 file changed, 11 deletions(-) diff --git a/diff.c b/diff.c index 626fd47aa0e..ffbe09937bc 100644 --- a/diff.c +++ b/diff.c @@ -807,11 +807,6 @@ struct moved_block { int wsd; /* The whitespace delta of this block */ }; -static void moved_block_clear(struct moved_block *b) -{ - memset(b, 0, sizeof(*b)); -} - #define INDENT_BLANKLINE INT_MIN static void fill_es_indent_data(struct emitted_diff_symbol *es) @@ -1128,8 +1123,6 @@ static void mark_color_as_moved(struct diff_options *o, } if (pmb_nr && (!match || l->s != moved_symbol)) { - int i; - if (!adjust_last_block(o, n, block_length) && block_length > 1) { /* @@ -1139,8 +1132,6 @@ static void mark_color_as_moved(struct diff_options *o, match = NULL; n -= block_length; } - for(i = 0; i < pmb_nr; i++) - moved_block_clear(&pmb[i]); pmb_nr = 0; block_length = 0; flipped_block = 0; @@ -1193,8 +1184,6 @@ static void mark_color_as_moved(struct diff_options *o, } adjust_last_block(o, n, block_length); - for(n = 0; n < pmb_nr; n++) - moved_block_clear(&pmb[n]); free(pmb); } From patchwork Thu Dec 9 10:30:07 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666335 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id E705BC433F5 for ; Thu, 9 Dec 2021 10:30:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234803AbhLIKeM (ORCPT ); Thu, 9 Dec 2021 05:34:12 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34428 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234628AbhLIKd6 (ORCPT ); Thu, 9 Dec 2021 05:33:58 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4EFD2C061A32 for ; Thu, 9 Dec 2021 02:30:24 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id t18so8796944wrg.11 for ; Thu, 09 Dec 2021 02:30:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=IQqFcygNNGO8TgTlsU7pdOOW17PYUaCsqLVpjC9Nw7w=; b=Q3A8AGMtAjEwLa6j0KXpth+PizSggT5CKX6FoR/XeCKhyp7gp8hgjoeZLadkF4lmAu bQQti262MDGo/ZnXvLydQtsAw1oUVw+Uaxupe7e8Pylx8jpKxWL9xTu3xCq7LOOfm9Ut YdMAs//xVbd5kslgF2vXvb7hpRJfKldMpkeL6vIeXr27fQjrkzSFJ1SRz+1kO2VyahVy HHZwrQbsFzJR3knrn9lPhaCQM67AF8g+Fs7y8Q+2NLp+veXMhjlEZiximOJsul2JJx/O 3b1FXUlbPjocIFW7lMDjWauOPos++A0mDGf7EY2DxZZapkeX4sU769vB8E65FxEck/w4 hluw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=IQqFcygNNGO8TgTlsU7pdOOW17PYUaCsqLVpjC9Nw7w=; b=aBpERic3oaX7eawtg9uz90fOKUOv+DEeFTmt8T+wzlox1IJt2SqlHHe5hryOlb2zMy Y0KRoo27KdA+KLxc0/JFaNwfLjbqiiv1dETDyykMMZjxMsmuSUwryGLw9K1JSCaFR5MN ZBv8groMSu+vQeRMUb7g0847OFLIvPCxy/3bb4Q6SqPf251ONfwZt6zoiIxV17Tjjzhn oBGgzRoqemSzZLwHQ/TBv974ecrMs+BCJsq5qy9B8kqNDN3MPyB6oC3T3gxBc7Mj8JIF +wExpKiSCMbRkaeSYVGbgiNt1h0GhMKIe5oibx5YN4EHNtF5/AQlO/ye2++D0gvrx6zB MIsg== X-Gm-Message-State: AOAM532kBnBmeq2XyfAMO7PgMAhNq/eiQ69WEdW3B2Ol/AB4G42ZIx2s PgdiECf7N9tDe4LeOH9+swIBCw0JFpI= X-Google-Smtp-Source: ABdhPJxx+al7+3DaoGy5Pb/pOn5oK8hDgMuYZb44Cp0jmJlQKPzPsGkSsIgvZv0Asfk6tbgL3K5HKA== X-Received: by 2002:adf:8165:: with SMTP id 92mr5779994wrm.199.1639045822620; Thu, 09 Dec 2021 02:30:22 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id g16sm6436261wmq.20.2021.12.09.02.30.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:22 -0800 (PST) Message-Id: <3e769bab78cdef61be4b3e06dbe15445f1983a1f.1639045809.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:07 +0000 Subject: [PATCH v5 13/15] diff --color-moved-ws=allow-indentation-change: improve hash lookups Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood As libxdiff does not have a whitespace flag to ignore the indentation the code for --color-moved-ws=allow-indentation-change uses XDF_IGNORE_WHITESPACE and then filters out any hash lookups where there are non-indentation changes. This filtering is inefficient as we have to perform another string comparison. By using the offset data that we have already computed to skip the indentation we can avoid using XDF_IGNORE_WHITESPACE and safely remove the extra checks which improves the performance by 11% and paves the way for the elimination of string comparisons in the next commit. This change slightly increases the run time of other --color-moved modes. This could be avoided by using different comparison functions for the different modes but after the next two commits there is no measurable benefit in doing so. There is a change in behavior for lines that begin with a form-feed or vertical-tab character. Since b46054b374 ("xdiff: use git-compat-util", 2019-04-11) xdiff does not treat '\f' or '\v' as whitespace characters. This means that lines starting with those characters are never considered to be blank and never match a line that does not start with the same character. After this patch a line matching "^[\f\v\r]*[ \t]*$" is considered to be blank by --color-moved-ws=allow-indentation-change and lines beginning "^[\f\v\r]*[ \t]*" can match another line if the suffixes match. This changes the output of git show for d18f76dccf ("compat/regex: use the regex engine from gawk for compat", 2010-08-17) as some lines in the pre-image before a moved block that contain '\f' are now considered moved as well as they match a blank line before the moved lines in the post-image. This commit updates one of the tests to reflect this change. Test HEAD^ HEAD -------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.86(0.82+0.04) 0.88(0.84+0.04) +2.3% 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.97(0.94+0.03) 0.86(0.81+0.05) -11.3% 4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.09) 1.16(1.06+0.09) +0.0% 4002.5: log --color-moved --no-color-moved-ws 1.32(1.26+0.06) 1.33(1.27+0.05) +0.8% 4002.6: log --color-moved-ws=allow-indentation-change 1.35(1.29+0.06) 1.33(1.24+0.08) -1.5% Signed-off-by: Phillip Wood --- diff.c | 65 +++++++++++--------------------------- t/t4015-diff-whitespace.sh | 22 ++++++------- 2 files changed, 30 insertions(+), 57 deletions(-) diff --git a/diff.c b/diff.c index ffbe09937bc..2085c063675 100644 --- a/diff.c +++ b/diff.c @@ -850,28 +850,15 @@ static void fill_es_indent_data(struct emitted_diff_symbol *es) } static int compute_ws_delta(const struct emitted_diff_symbol *a, - const struct emitted_diff_symbol *b, - int *out) -{ - int a_len = a->len, - b_len = b->len, - a_off = a->indent_off, - a_width = a->indent_width, - b_off = b->indent_off, + const struct emitted_diff_symbol *b) +{ + int a_width = a->indent_width, b_width = b->indent_width; - if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE) { - *out = INDENT_BLANKLINE; - return 1; - } - - if (a_len - a_off != b_len - b_off || - memcmp(a->line + a_off, b->line + b_off, a_len - a_off)) - return 0; - - *out = a_width - b_width; + if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE) + return INDENT_BLANKLINE; - return 1; + return a_width - b_width; } static int cmp_in_block_with_wsd(const struct moved_entry *cur, @@ -916,26 +903,17 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data, const void *keydata) { const struct diff_options *diffopt = hashmap_cmp_fn_data; - const struct moved_entry *a, *b; + const struct emitted_diff_symbol *a, *b; unsigned flags = diffopt->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; - a = container_of(eptr, const struct moved_entry, ent); - b = container_of(entry_or_key, const struct moved_entry, ent); + a = container_of(eptr, const struct moved_entry, ent)->es; + b = container_of(entry_or_key, const struct moved_entry, ent)->es; - if (diffopt->color_moved_ws_handling & - COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) - /* - * As there is not specific white space config given, - * we'd need to check for a new block, so ignore all - * white space. The setup of the white space - * configuration for the next block is done else where - */ - flags |= XDF_IGNORE_WHITESPACE; - - return !xdiff_compare_lines(a->es->line, a->es->len, - b->es->line, b->es->len, - flags); + return !xdiff_compare_lines(a->line + a->indent_off, + a->len - a->indent_off, + b->line + b->indent_off, + b->len - b->indent_off, flags); } static struct moved_entry *prepare_entry(struct diff_options *o, @@ -944,7 +922,8 @@ static struct moved_entry *prepare_entry(struct diff_options *o, struct moved_entry *ret = xmalloc(sizeof(*ret)); struct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no]; unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; - unsigned int hash = xdiff_hash_string(l->line, l->len, flags); + unsigned int hash = xdiff_hash_string(l->line + l->indent_off, + l->len - l->indent_off, flags); hashmap_entry_init(&ret->ent, hash); ret->es = l; @@ -1036,13 +1015,11 @@ static void fill_potential_moved_blocks(struct diff_options *o, hashmap_for_each_entry_from(hm, match, ent) { ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & - COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { - if (compute_ws_delta(l, match->es, &(pmb[pmb_nr]).wsd)) - pmb[pmb_nr++].match = match; - } else { + COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) + pmb[pmb_nr].wsd = compute_ws_delta(l, match->es); + else pmb[pmb_nr].wsd = 0; - pmb[pmb_nr++].match = match; - } + pmb[pmb_nr++].match = match; } *pmb_p = pmb; @@ -6276,10 +6253,6 @@ static void diff_flush_patch_all_file_pairs(struct diff_options *o) if (o->color_moved) { struct hashmap add_lines, del_lines; - if (o->color_moved_ws_handling & - COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) - o->color_moved_ws_handling |= XDF_IGNORE_WHITESPACE; - hashmap_init(&del_lines, moved_entry_cmp, o, 0); hashmap_init(&add_lines, moved_entry_cmp, o, 0); diff --git a/t/t4015-diff-whitespace.sh b/t/t4015-diff-whitespace.sh index 15782c879d2..50d0cf486be 100755 --- a/t/t4015-diff-whitespace.sh +++ b/t/t4015-diff-whitespace.sh @@ -2206,10 +2206,10 @@ EMPTY='' test_expect_success 'compare mixed whitespace delta across moved blocks' ' git reset --hard && - tr Q_ "\t " <<-EOF >text.txt && - ${EMPTY} - ____too short without - ${EMPTY} + tr "^|Q_" "\f\v\t " <<-EOF >text.txt && + ^__ + |____too short without + ^ ___being grouped across blank line ${EMPTY} context @@ -2228,7 +2228,7 @@ test_expect_success 'compare mixed whitespace delta across moved blocks' ' git add text.txt && git commit -m "add text.txt" && - tr Q_ "\t " <<-EOF >text.txt && + tr "^|Q_" "\f\v\t " <<-EOF >text.txt && context lines to @@ -2239,7 +2239,7 @@ test_expect_success 'compare mixed whitespace delta across moved blocks' ' ${EMPTY} QQtoo short without ${EMPTY} - Q_______being grouped across blank line + ^Q_______being grouped across blank line ${EMPTY} Q_QThese two lines have had their indentation reduced by four spaces @@ -2251,16 +2251,16 @@ test_expect_success 'compare mixed whitespace delta across moved blocks' ' -c core.whitespace=space-before-tab \ diff --color --color-moved --ws-error-highlight=all \ --color-moved-ws=allow-indentation-change >actual.raw && - grep -v "index" actual.raw | test_decode_color >actual && + grep -v "index" actual.raw | tr "\f\v" "^|" | test_decode_color >actual && cat <<-\EOF >expected && diff --git a/text.txt b/text.txt --- a/text.txt +++ b/text.txt @@ -1,16 +1,16 @@ - - - - too short without - - + -^ + -| too short without + -^ - being grouped across blank line - context @@ -2280,7 +2280,7 @@ test_expect_success 'compare mixed whitespace delta across moved blocks' ' + + too short without + - + being grouped across blank line + +^ being grouped across blank line + + These two lines have had their +indentation reduced by four spaces From patchwork Thu Dec 9 10:30:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666337 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 25C1FC433FE for ; Thu, 9 Dec 2021 10:30:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235011AbhLIKeP (ORCPT ); Thu, 9 Dec 2021 05:34:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34446 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234692AbhLIKeB (ORCPT ); Thu, 9 Dec 2021 05:34:01 -0500 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 41A2FC061D60 for ; Thu, 9 Dec 2021 02:30:25 -0800 (PST) Received: by mail-wm1-x329.google.com with SMTP id p27-20020a05600c1d9b00b0033bf8532855so3689954wms.3 for ; Thu, 09 Dec 2021 02:30:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=B2qNreqxPbVLHXZVbNIw1FNvHSOsXYeU20/GeFvd7zY=; b=bCK7/r1XwQKR72lDYzGsc22lfie21i6xbZt0aKfxLBianeNYQdQsoZp9SWm+jJwAcK kpb7JI3StoqU19A6VXI9AH/OzvRjF1YhS2t/obpilY2YPOWuU9oO5dtJSPbMBqwJaYrV ieTaOUiZ/0CkkrxeM5lHl0+1C3QbTQ2RDDXgrd1uT7ZgTKKiNb3Lu92+yGv6DmwGo6Dh FzBDNErBAbYG0Vr8YmPFxKfyhddQAsXHQOReEnDBe0Eb67iJG7tipLeTeQC0xXVWy9Pg Lt+b/C4NGDp4S5MT8f/Df0VjaQY5E7l3B9FFIjR/xIKidMXrO+qGm1WEyzlThYa0cBxX wi6A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=B2qNreqxPbVLHXZVbNIw1FNvHSOsXYeU20/GeFvd7zY=; b=EWfFqxDYOtdw9Q9SlzxtvIIuGE9JEXeK4NlVj/w0NOV4egUkUPKKHpeD6GtbU24D7b Bm5ttdHlKLMgyzHtsKzY4rndwPyZZl8iJOF638HDbcFAyl9nx2JLr2q9gK8EevXuHyKO lgoy6/4ZjgqWBI+fee08rphFUWRLyz+U4PdeWeBU4T3N6El7aig25a9YrY2Nfebj8AgB GFUvImhCh6lZsQ4gyuUTMKqvaupzFMmX2r8FkmkSM/rARO5upLASKbZFKY6rz6Lrc5P+ v5Zyy5UUufVkhFLuXsKcDz7TYcjKMiTz7kIPN9rPin00+9Z5af5cY95W5lre/IIZAf+M UKXA== X-Gm-Message-State: AOAM532AMGEfEXjSBWbkAKzzFsGINo35tgPj41s+nr/y06N0JxoFxUDm 4lzQWTEvIMCDeW2X1qxtu3qSl2BgWBo= X-Google-Smtp-Source: ABdhPJz7MexfkYiIMJMDX+gySDoyBBfenS62X6NEIzKYUGYztufpuojC2Q/z9kIx1AN4VoUrZ5VuUw== X-Received: by 2002:a1c:4d13:: with SMTP id o19mr5911779wmh.164.1639045823520; Thu, 09 Dec 2021 02:30:23 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j11sm5439064wrt.3.2021.12.09.02.30.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:23 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:08 +0000 Subject: [PATCH v5 14/15] diff: use designated initializers for emitted_diff_symbol Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood This makes it clearer which fields are being explicitly initialized and will simplify the next commit where we add a new field to the struct. Signed-off-by: Phillip Wood --- diff.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/diff.c b/diff.c index 2085c063675..9ef88d7665a 100644 --- a/diff.c +++ b/diff.c @@ -1497,7 +1497,9 @@ static void emit_diff_symbol_from_struct(struct diff_options *o, static void emit_diff_symbol(struct diff_options *o, enum diff_symbol s, const char *line, int len, unsigned flags) { - struct emitted_diff_symbol e = {line, len, flags, 0, 0, s}; + struct emitted_diff_symbol e = { + .line = line, .len = len, .flags = flags, .s = s + }; if (o->emitted_symbols) append_emitted_diff_symbol(o, &e); From patchwork Thu Dec 9 10:30:09 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phillip Wood X-Patchwork-Id: 12666339 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 49923C433F5 for ; Thu, 9 Dec 2021 10:30:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234986AbhLIKeN (ORCPT ); Thu, 9 Dec 2021 05:34:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34450 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234694AbhLIKeB (ORCPT ); Thu, 9 Dec 2021 05:34:01 -0500 Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3E715C061D76 for ; Thu, 9 Dec 2021 02:30:26 -0800 (PST) Received: by mail-wm1-x32d.google.com with SMTP id p27-20020a05600c1d9b00b0033bf8532855so3689980wms.3 for ; Thu, 09 Dec 2021 02:30:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=p5cnPMQKbgHXVyVGUj+cefY7DiWcqcJMbT+NkgNsm8c=; b=CG4Zy+soFpCevMahk2DcIx2BpN/38fzKT8MJcvFm4dhrdmKmbDvC+nkg37fjNKHcDM kbeRHZJijkr6o/KtuMzhatbCslRRLTSLQ6j2vwhBiP9KdXjOiYGFyhtfhza9e6EI0yb4 MHkLyU5E8GSu5lde6vWk2aT20dNjEX9i2m8EXoXoSEYzP23w3ezVXAKdPBfRXwumtCDE SWdKPRjCbDsDM0awTvYz3CjegPuiPdCNsedWtYKu+ifnY839hlO/URIyBzRewoJuMT/b CHidEVT0SlJyknTPNRETBmAxwgW2fPW7XffKxE6j8JaYrHIOj4SrBFR7fTmBnhTgEJqR GyaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=p5cnPMQKbgHXVyVGUj+cefY7DiWcqcJMbT+NkgNsm8c=; b=Jq+xN6NvnVXK0eAf9IOS2q9TUHoScYG/xLNoYZi3/CBK91TaO86wcEj8tOnAM1PqbD 2Kg/baFT8ry0I/Zmxoq7v7S78wcWXxsN8d6Ee3/wvtgeZYhVy9J61O9l96DLbs3svnRI KIIuIgUN56Ma83r1XCTubgjZhpuqEZnXuWhhP1YhpD46YSRUNuSc0dbmjMqrvBe4w5wV ssZRZfcBSdRIzhcg4QRUj1xa35FMCZyI3iuWJ3J3E5gTp+OkfQh0Hd/+tAkPWarRuR3U YcrHg2XleCBOBXAaEIrOL01wSLkYbQE82KYVd6Zd1yxd0JDC+RHUz/snJ3xuTt7XN4r5 KBVw== X-Gm-Message-State: AOAM533PVZ7ldZUx8eGCK5MYDO6Itwkjd/Pv/1sabyjw+pmp5OstfmoW lh2bXcOHn+kaMMSYVr7575LqpnpEln8= X-Google-Smtp-Source: ABdhPJxnBpKHYEQjAqbD0lQUFD71KTARUTKwAEFE6t25Jih+2zkd3+vaspa+zOfND6LNK4QzxHfTgQ== X-Received: by 2002:a1c:7e41:: with SMTP id z62mr6284852wmc.62.1639045824482; Thu, 09 Dec 2021 02:30:24 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id q123sm8034027wma.30.2021.12.09.02.30.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Dec 2021 02:30:24 -0800 (PST) Message-Id: <350fa55ce5eaf92f000f52668dfa7c2485b8660a.1639045810.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 09 Dec 2021 10:30:09 +0000 Subject: [PATCH v5 15/15] diff --color-moved: intern strings Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Phillip Wood , =?utf-8?b?w4Z2YXIgQXJuZmo=?= =?utf-8?b?w7Zyw7A=?= Bjarmason , Elijah Newren , Phillip Wood , Johannes Schindelin , Phillip Wood , Phillip Wood Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Phillip Wood From: Phillip Wood Taking inspiration from xdl_classify_record() assign an id to each addition and deletion such that lines that match for the current --color-moved-ws mode share the same unique id. This reduces the number of hash lookups a little (calculating the ids still involves one hash lookup per line) but the main benefit is that when growing blocks of potentially moved lines we can replace string comparisons which involve chasing a pointer with a simple integer comparison. On a large diff this commit reduces the time to run 'diff --color-moved' by 37% compared to the previous commit and 31% compared to master, for 'diff --color-moved-ws=allow-indentation-change' the reduction is 28% compared to the previous commit and 96% compared to master. There is little change in the performance of 'git log --patch' as the diffs are smaller. Test HEAD^ HEAD --------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38(0.33+0.05) 0.38(0.33+0.05) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.88(0.81+0.06) 0.55(0.50+0.04) -37.5% 4002.3: diff --color-moved-ws=allow-indentation-change large change 0.85(0.79+0.06) 0.61(0.54+0.06) -28.2% 4002.4: log --no-color-moved --no-color-moved-ws 1.16(1.07+0.08) 1.15(1.09+0.05) -0.9% 4002.5: log --color-moved --no-color-moved-ws 1.31(1.22+0.08) 1.29(1.19+0.09) -1.5% 4002.6: log --color-moved-ws=allow-indentation-change 1.32(1.24+0.08) 1.31(1.18+0.13) -0.8% Test master HEAD --------------------------------------------------------------------------------------------------------------- 4002.1: diff --no-color-moved --no-color-moved-ws large change 0.38 (0.33+0.05) 0.38(0.33+0.05) +0.0% 4002.2: diff --color-moved --no-color-moved-ws large change 0.80 (0.75+0.04) 0.55(0.50+0.04) -31.2% 4002.3: diff --color-moved-ws=allow-indentation-change large change 14.20(14.15+0.05) 0.61(0.54+0.06) -95.7% 4002.4: log --no-color-moved --no-color-moved-ws 1.15 (1.05+0.09) 1.15(1.09+0.05) +0.0% 4002.5: log --color-moved --no-color-moved-ws 1.30 (1.19+0.11) 1.29(1.19+0.09) -0.8% 4002.6: log --color-moved-ws=allow-indentation-change 1.70 (1.63+0.06) 1.31(1.18+0.13) -22.9% Signed-off-by: Phillip Wood --- diff.c | 174 +++++++++++++++++++++++++++++++-------------------------- 1 file changed, 96 insertions(+), 78 deletions(-) diff --git a/diff.c b/diff.c index 9ef88d7665a..c28c56c1283 100644 --- a/diff.c +++ b/diff.c @@ -18,6 +18,7 @@ #include "submodule-config.h" #include "submodule.h" #include "hashmap.h" +#include "mem-pool.h" #include "ll-merge.h" #include "string-list.h" #include "strvec.h" @@ -772,6 +773,7 @@ struct emitted_diff_symbol { int flags; int indent_off; /* Offset to first non-whitespace character */ int indent_width; /* The visual width of the indentation */ + unsigned id; enum diff_symbol s; }; #define EMITTED_DIFF_SYMBOL_INIT {NULL} @@ -797,9 +799,9 @@ static void append_emitted_diff_symbol(struct diff_options *o, } struct moved_entry { - struct hashmap_entry ent; const struct emitted_diff_symbol *es; struct moved_entry *next_line; + struct moved_entry *next_match; }; struct moved_block { @@ -865,24 +867,24 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur, const struct emitted_diff_symbol *l, struct moved_block *pmb) { - int al = cur->es->len, bl = l->len; - const char *a = cur->es->line, - *b = l->line; - int a_off = cur->es->indent_off, - a_width = cur->es->indent_width, - b_off = l->indent_off, - b_width = l->indent_width; + int a_width = cur->es->indent_width, b_width = l->indent_width; int delta; - /* If 'l' and 'cur' are both blank then they match. */ - if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE) + /* The text of each line must match */ + if (cur->es->id != l->id) + return 1; + + /* + * If 'l' and 'cur' are both blank then we don't need to check the + * indent. We only need to check cur as we know the strings match. + * */ + if (a_width == INDENT_BLANKLINE) return 0; /* * The indent changes of the block are known and stored in pmb->wsd; * however we need to check if the indent changes of the current line - * match those of the current block and that the text of 'l' and 'cur' - * after the indentation match. + * match those of the current block. */ delta = b_width - a_width; @@ -893,22 +895,26 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur, if (pmb->wsd == INDENT_BLANKLINE) pmb->wsd = delta; - return !(delta == pmb->wsd && al - a_off == bl - b_off && - !memcmp(a + a_off, b + b_off, al - a_off)); + return delta != pmb->wsd; } -static int moved_entry_cmp(const void *hashmap_cmp_fn_data, - const struct hashmap_entry *eptr, - const struct hashmap_entry *entry_or_key, - const void *keydata) +struct interned_diff_symbol { + struct hashmap_entry ent; + struct emitted_diff_symbol *es; +}; + +static int interned_diff_symbol_cmp(const void *hashmap_cmp_fn_data, + const struct hashmap_entry *eptr, + const struct hashmap_entry *entry_or_key, + const void *keydata) { const struct diff_options *diffopt = hashmap_cmp_fn_data; const struct emitted_diff_symbol *a, *b; unsigned flags = diffopt->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; - a = container_of(eptr, const struct moved_entry, ent)->es; - b = container_of(entry_or_key, const struct moved_entry, ent)->es; + a = container_of(eptr, const struct interned_diff_symbol, ent)->es; + b = container_of(entry_or_key, const struct interned_diff_symbol, ent)->es; return !xdiff_compare_lines(a->line + a->indent_off, a->len - a->indent_off, @@ -916,55 +922,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data, b->len - b->indent_off, flags); } -static struct moved_entry *prepare_entry(struct diff_options *o, - int line_no) +static void prepare_entry(struct diff_options *o, struct emitted_diff_symbol *l, + struct interned_diff_symbol *s) { - struct moved_entry *ret = xmalloc(sizeof(*ret)); - struct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no]; unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; unsigned int hash = xdiff_hash_string(l->line + l->indent_off, l->len - l->indent_off, flags); - hashmap_entry_init(&ret->ent, hash); - ret->es = l; - ret->next_line = NULL; - - return ret; + hashmap_entry_init(&s->ent, hash); + s->es = l; } -static void add_lines_to_move_detection(struct diff_options *o, - struct hashmap *add_lines, - struct hashmap *del_lines) +struct moved_entry_list { + struct moved_entry *add, *del; +}; + +static struct moved_entry_list *add_lines_to_move_detection(struct diff_options *o, + struct mem_pool *entry_mem_pool) { struct moved_entry *prev_line = NULL; - + struct mem_pool interned_pool; + struct hashmap interned_map; + struct moved_entry_list *entry_list = NULL; + size_t entry_list_alloc = 0; + unsigned id = 0; int n; + + hashmap_init(&interned_map, interned_diff_symbol_cmp, o, 8096); + mem_pool_init(&interned_pool, 1024 * 1024); + for (n = 0; n < o->emitted_symbols->nr; n++) { - struct hashmap *hm; - struct moved_entry *key; + struct interned_diff_symbol key; + struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; + struct interned_diff_symbol *s; + struct moved_entry *entry; - switch (o->emitted_symbols->buf[n].s) { - case DIFF_SYMBOL_PLUS: - hm = add_lines; - break; - case DIFF_SYMBOL_MINUS: - hm = del_lines; - break; - default: + if (l->s != DIFF_SYMBOL_PLUS && l->s != DIFF_SYMBOL_MINUS) { prev_line = NULL; continue; } if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) - fill_es_indent_data(&o->emitted_symbols->buf[n]); - key = prepare_entry(o, n); - if (prev_line && prev_line->es->s == o->emitted_symbols->buf[n].s) - prev_line->next_line = key; + fill_es_indent_data(l); - hashmap_add(hm, &key->ent); - prev_line = key; + prepare_entry(o, l, &key); + s = hashmap_get_entry(&interned_map, &key, ent, &key.ent); + if (s) { + l->id = s->es->id; + } else { + l->id = id; + ALLOC_GROW_BY(entry_list, id, 1, entry_list_alloc); + hashmap_add(&interned_map, + memcpy(mem_pool_alloc(&interned_pool, + sizeof(key)), + &key, sizeof(key))); + } + entry = mem_pool_alloc(entry_mem_pool, sizeof(*entry)); + entry->es = l; + entry->next_line = NULL; + if (prev_line && prev_line->es->s == l->s) + prev_line->next_line = entry; + prev_line = entry; + if (l->s == DIFF_SYMBOL_PLUS) { + entry->next_match = entry_list[l->id].add; + entry_list[l->id].add = entry; + } else { + entry->next_match = entry_list[l->id].del; + entry_list[l->id].del = entry; + } } + + hashmap_clear(&interned_map); + mem_pool_discard(&interned_pool, 0); + + return entry_list; } static void pmb_advance_or_null(struct diff_options *o, @@ -973,7 +1005,6 @@ static void pmb_advance_or_null(struct diff_options *o, int *pmb_nr) { int i, j; - unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; for (i = 0, j = 0; i < *pmb_nr; i++) { int match; @@ -986,9 +1017,8 @@ static void pmb_advance_or_null(struct diff_options *o, match = cur && !cmp_in_block_with_wsd(cur, l, &pmb[i]); else - match = cur && - xdiff_compare_lines(cur->es->line, cur->es->len, - l->line, l->len, flags); + match = cur && cur->es->id == l->id; + if (match) { pmb[j] = pmb[i]; pmb[j++].match = cur; @@ -998,7 +1028,6 @@ static void pmb_advance_or_null(struct diff_options *o, } static void fill_potential_moved_blocks(struct diff_options *o, - struct hashmap *hm, struct moved_entry *match, struct emitted_diff_symbol *l, struct moved_block **pmb_p, @@ -1012,7 +1041,7 @@ static void fill_potential_moved_blocks(struct diff_options *o, * The current line is the start of a new block. * Setup the set of potential blocks. */ - hashmap_for_each_entry_from(hm, match, ent) { + for (; match; match = match->next_match) { ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) @@ -1067,8 +1096,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length) /* Find blocks of moved code, delegate actual coloring decision to helper */ static void mark_color_as_moved(struct diff_options *o, - struct hashmap *add_lines, - struct hashmap *del_lines) + struct moved_entry_list *entry_list) { struct moved_block *pmb = NULL; /* potentially moved blocks */ int pmb_nr = 0, pmb_alloc = 0; @@ -1077,23 +1105,15 @@ static void mark_color_as_moved(struct diff_options *o, for (n = 0; n < o->emitted_symbols->nr; n++) { - struct hashmap *hm = NULL; - struct moved_entry *key; struct moved_entry *match = NULL; struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; switch (l->s) { case DIFF_SYMBOL_PLUS: - hm = del_lines; - key = prepare_entry(o, n); - match = hashmap_get_entry(hm, key, ent, NULL); - free(key); + match = entry_list[l->id].del; break; case DIFF_SYMBOL_MINUS: - hm = add_lines; - key = prepare_entry(o, n); - match = hashmap_get_entry(hm, key, ent, NULL); - free(key); + match = entry_list[l->id].add; break; default: flipped_block = 0; @@ -1135,7 +1155,7 @@ static void mark_color_as_moved(struct diff_options *o, */ n -= block_length; else - fill_potential_moved_blocks(o, hm, match, l, + fill_potential_moved_blocks(o, match, l, &pmb, &pmb_alloc, &pmb_nr); @@ -6253,20 +6273,18 @@ static void diff_flush_patch_all_file_pairs(struct diff_options *o) if (o->emitted_symbols) { if (o->color_moved) { - struct hashmap add_lines, del_lines; - - hashmap_init(&del_lines, moved_entry_cmp, o, 0); - hashmap_init(&add_lines, moved_entry_cmp, o, 0); + struct mem_pool entry_pool; + struct moved_entry_list *entry_list; - add_lines_to_move_detection(o, &add_lines, &del_lines); - mark_color_as_moved(o, &add_lines, &del_lines); + mem_pool_init(&entry_pool, 1024 * 1024); + entry_list = add_lines_to_move_detection(o, + &entry_pool); + mark_color_as_moved(o, entry_list); if (o->color_moved == COLOR_MOVED_ZEBRA_DIM) dim_moved_lines(o); - hashmap_clear_and_free(&add_lines, struct moved_entry, - ent); - hashmap_clear_and_free(&del_lines, struct moved_entry, - ent); + mem_pool_discard(&entry_pool, 0); + free(entry_list); } for (i = 0; i < esm.nr; i++)