From patchwork Mon Jan 4 23:49:50 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997787 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C53B7C43381 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9AC282253D for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727839AbhADXvM (ORCPT ); Mon, 4 Jan 2021 18:51:12 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33630 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvL (ORCPT ); Mon, 4 Jan 2021 18:51:11 -0500 Received: from mail-ot1-x32b.google.com (mail-ot1-x32b.google.com [IPv6:2607:f8b0:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 37058C061793 for ; Mon, 4 Jan 2021 15:50:31 -0800 (PST) Received: by mail-ot1-x32b.google.com with SMTP id 11so27690635oty.9 for ; Mon, 04 Jan 2021 15:50:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=3ExD4NwtEea+vxCJJBfFXlp09hukXUB83Uc8F7axU4U=; b=ER5dBaExHo4x0oDbU3nhs6Mp/h4UHyDprNHCiBjVpOB+E198S6nCFHjH4FBZNh4SFs eCjPwOKouJUsGd0wV+RZfaYyv4lPKA2iWaBdykr06udJ9UDWqV1KMycsT3VO/DEgniem 2IcVLnIXLJWYf4xIpCAkrjZotkt5ywudSRTUMTd5t1PlZ5ZBD8/vsW5eqGBSEmIoxSkx 9H/ihugh34/RxlpcRBhuX25JtdQgqWVRyj6or2JeiiutnoDOmR3juN9w4l0hcLHFElky BhFM/AZanoPVehfGD9/PHSHygVswTS3xGU8I+jDgRVZFUcb6faZiu3qcV6BcQiBApglv RPbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=3ExD4NwtEea+vxCJJBfFXlp09hukXUB83Uc8F7axU4U=; b=R/ClI53XaX7nmPzVjy28mI8YeNVyl8IQu+4RvFpwfkVuj0/kjb7Fm+QICHnDhHEes4 Yex8dKsM1kps0HLLJrhNLNVMdDceJ4K9osl7+IPO6PZtZLao9x/X6zsqB7cWd/4GqWu6 ExUEhCihIGx2IVsW2VVSelLbtA1A1enmn2/hjwq9FQwS47YeBWfM66OGvs4jmBfG//O8 oA0FFToNSZqWI5nPpOlr6WDq7R0Fn1oiKuDzWRzMSb9MQDw/8LvkgL9QWWGJgX5Aqydk 9FH3yTj7s53528RUNqO2HNTsW10VJk3oHqY6RWf22VuNQkTBrej2wegQ2slIid1nXJf7 3ZbQ== X-Gm-Message-State: AOAM533hOT9+w88xd9ENZXMjYPKA08wNrgDqeLHsXax2kA4Vy5cQG1pF xKlH/PaDVREBEAAa2g0Le+zBmou9rRM= X-Google-Smtp-Source: ABdhPJxK/5Bv3OTG0q2b5vUTurbOp/DsMmTG4+wQLGc5WvN/Crh3S7TtEt4BIGksS9CAelchWX7mlw== X-Received: by 2002:a05:6830:15c1:: with SMTP id j1mr54224907otr.211.1609804230513; Mon, 04 Jan 2021 15:50:30 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:30 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 01/17] merge-ort: add new data structures for directory rename detection Date: Mon, 4 Jan 2021 15:49:50 -0800 Message-Id: <20210104235006.2867404-2-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- merge-ort.c | 34 +++++++++++++++++++++++++++++++--- 1 file changed, 31 insertions(+), 3 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 6900ab9e7f..719cc1c582 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -52,14 +52,42 @@ enum merge_side { }; struct rename_info { + /* + * All variables that are arrays of size 3 correspond to data tracked + * for the sides in enum merge_side. Index 0 is almost always unused + * because we often only need to track information for MERGE_SIDE1 and + * MERGE_SIDE2 (MERGE_BASE can't have rename information since renames + * are determined relative to what changed since the MERGE_BASE). + */ + /* * pairs: pairing of filenames from diffcore_rename() - * - * Index 1 and 2 correspond to sides 1 & 2 as used in - * conflict_info.stages. Index 0 unused. */ struct diff_queue_struct pairs[3]; + /* + * dirs_removed: directories removed on a given side of history. + */ + struct strset dirs_removed[3]; + + /* + * dir_rename_count: tracking where parts of a directory were renamed to + * + * When files in a directory are renamed, they may not all go to the + * same location. Each strmap here tracks: + * old_dir => {new_dir => int} + * That is, dir_rename_count[side] is a strmap to a strintmap. + */ + struct strmap dir_rename_count[3]; + + /* + * dir_renames: computed directory renames + * + * This is a map of old_dir => new_dir and is derived in part from + * dir_rename_count. + */ + struct strmap dir_renames[3]; + /* * needed_limit: value needed for inexact rename detection to run * From patchwork Mon Jan 4 23:49:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997783 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6BEC2C433E0 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3AD9D22519 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727700AbhADXur (ORCPT ); Mon, 4 Jan 2021 18:50:47 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33524 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726168AbhADXur (ORCPT ); Mon, 4 Jan 2021 18:50:47 -0500 Received: from mail-ot1-x32a.google.com (mail-ot1-x32a.google.com [IPv6:2607:f8b0:4864:20::32a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 567CFC061794 for ; Mon, 4 Jan 2021 15:50:32 -0800 (PST) Received: by mail-ot1-x32a.google.com with SMTP id a109so27741796otc.1 for ; Mon, 04 Jan 2021 15:50:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=2D27MOZCWKJcR+qftRGZM+KbS3IqNa6FfwwOpSLCd/M=; b=s1Lr7IwrltqgOGAQZnLhc8FL0rfeQPg5zpC5lT6FF+SN2AOLiuURpWbuUBwL12a5cz NvQc6mTnACqoAAcSYAeDnKO2D7RS3aNCuixQlpJ4H339eUEeFMbu1VGgoAWim+0GIRCo 3m68QK9JaAZh3vrKheB2sOj6sg4K07bFEosWtIqpg/PLh12wHuamEc/T0lmPHP4ONwKd 40t52BpllbnP7IsHKSNP+5um7KInc03YKJAPygam3loCeLdE12PFV5B7aqJB6DLtm2Xm qsb2RN+iv/0biReQEY4Km27qR9Cx+CsUp/qU96Yn6QMUZCjKNMbhjvEVZWkbpR9TEWSU M9yQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=2D27MOZCWKJcR+qftRGZM+KbS3IqNa6FfwwOpSLCd/M=; b=tL6KjZZAwuz4fjbTlDFXBJevBxnsNwwuaS9wqBizd64LyWBQrHNvJcRsEADKs9ou8F ZvQewilQfEDK58bpWj+WkYuVuiQIaZL0iD1p4HRDNc15/QHabGcZsDTC1LBoXwHDLxB2 ef7U0KrAPT1D7UNi7/8YmGB/n1mkU5pfLDTI9sF08aYLcC6MRRL4cp2kJ3BWK+ak31PA u/lsDQAB1a4mHlgz1Q321GRxV1cxLD/TmJrX4oPT/2eurivISqsvm/IE9duTFVtUiCN8 LgwRRGlb5ApFn4gmr2udFlm4XjBfuxFSRnFmrIWXYfv2+sg9KNVdaHvIB6cU4K9rii/a BHdw== X-Gm-Message-State: AOAM530QpATQIm8GqRBMh1CvJ/4Mxjbqvw5R22f4ld8Ezh7gVQpUrX/c U9fPPe/Nh/vFJetWhxNn5Qcgg5hR8H4= X-Google-Smtp-Source: ABdhPJxD0dbNGe6ID799sxlNPPNSpMV71oxPYwvel2YwcFpTeSbEW5Aim/EqIqzDLtaPvjGTtYZKIw== X-Received: by 2002:a9d:a61:: with SMTP id 88mr52266393otg.18.1609804231536; Mon, 04 Jan 2021 15:50:31 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:31 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 02/17] merge-ort: initialize and free new directory rename data structures Date: Mon, 4 Jan 2021 15:49:51 -0800 Message-Id: <20210104235006.2867404-3-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- merge-ort.c | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 719cc1c582..8b190b0ea5 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -311,8 +311,12 @@ static void free_strmap_strings(struct strmap *map) static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, int reinitialize) { + struct rename_info *renames = &opti->renames; + int i; void (*strmap_func)(struct strmap *, int) = reinitialize ? strmap_partial_clear : strmap_clear; + void (*strset_func)(struct strset *) = + reinitialize ? strset_partial_clear : strset_clear; /* * We marked opti->paths with strdup_strings = 0, so that we @@ -342,6 +346,23 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, string_list_clear(&opti->paths_to_free, 0); opti->paths_to_free.strdup_strings = 0; + /* Free memory used by various renames maps */ + for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) { + struct hashmap_iter iter; + struct strmap_entry *entry; + + strset_func(&renames->dirs_removed[i]); + + strmap_for_each_entry(&renames->dir_rename_count[i], + &iter, entry) { + struct strintmap *counts = entry->value; + strintmap_clear(counts); + } + strmap_func(&renames->dir_rename_count[i], 1); + + strmap_func(&renames->dir_renames[i], 0); + } + if (!reinitialize) { struct hashmap_iter iter; struct strmap_entry *e; @@ -2447,6 +2468,9 @@ static struct commit *make_virtual_commit(struct repository *repo, static void merge_start(struct merge_options *opt, struct merge_result *result) { + struct rename_info *renames; + int i; + /* Sanity checks on opt */ assert(opt->repo); @@ -2481,6 +2505,17 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) /* Initialization of opt->priv, our internal merge data */ opt->priv = xcalloc(1, sizeof(*opt->priv)); + /* Initialization of various renames fields */ + renames = &opt->priv->renames; + for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) { + strset_init_with_options(&renames->dirs_removed[i], + NULL, 0); + strmap_init_with_options(&renames->dir_rename_count[i], + NULL, 1); + strmap_init_with_options(&renames->dir_renames[i], + NULL, 0); + } + /* * Although we initialize opt->priv->paths with strdup_strings=0, * that's just to avoid making yet another copy of an allocated From patchwork Mon Jan 4 23:49:52 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997791 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E4B3BC4332D for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C4B9722519 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727844AbhADXvO (ORCPT ); Mon, 4 Jan 2021 18:51:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33636 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvN (ORCPT ); Mon, 4 Jan 2021 18:51:13 -0500 Received: from mail-oi1-x22a.google.com (mail-oi1-x22a.google.com [IPv6:2607:f8b0:4864:20::22a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 31687C061795 for ; Mon, 4 Jan 2021 15:50:33 -0800 (PST) Received: by mail-oi1-x22a.google.com with SMTP id p5so34094864oif.7 for ; Mon, 04 Jan 2021 15:50:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=X6qDFKHYv2+CPcQFqk/39OmXiYJ8Imm+KW7HA6oTQ+E=; b=fisqyIcbBu5uO88l9n6gyryRVM3W4x4dH+ftcPBRj6M9kkkpDk3cyj9lA5okgfm4Rd eIt0LmEeeWKqFiD/qliEYMC+DgLYaRhLvA7SJKVC/UfifigGtX9/4aNFHw4s24BxHSLC Mw8lSySW/41DiwQNDsjs7hydrQ6+vLy8pNVEq77+f0Un2wAd0eA1n2pUH1pCReog8FKy 6aWoV1ORj2ecXZGlFS6AD/ucE0D9mmPuYp20T7xASjK+ZRZ+1BEkV7WpzHc3XHOtHeS/ FJ61fRwL14/x9AU30cedMUd7Rl7OQM8LAXi7P5AjP0F30BB7lwRsI1ZY1mB4erjyC/MD bWrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=X6qDFKHYv2+CPcQFqk/39OmXiYJ8Imm+KW7HA6oTQ+E=; b=fgkXDmuot8jg6Vfo8twaKzV4kaDKwEOoOlPKm4PcTaqKMkZCMsDYuUvQgIQMwqZ5O1 d+SmqNHOgTuX15gpWfHTI5So+9Yq5nH4cr6Nw7WjSoW0iEmvvK5U1/sVv3MytUP6k/Bo Qu85l0Enb+CeFtyY715aaRugpv4Ow5Eqm0XonjAGIBvDtKarxC26EFktP2fFlPIjoZ/S FBXCCtGUwSlUDtomaciDdiMJrtMnIXzDjNj2Mb9PBcAhr5XfYmDKy/Q5pxWKE0I0EYOB yLkmlrlA0XnHRC9LcbyR6nN6hwCFEu8QEWaGzR9wHhBXR1l6sYvJTKoP5kzEHciptgq0 bQXQ== X-Gm-Message-State: AOAM531kqOV15pQ0tMWY/Qv18ZospdGj0MQgdsezPY8vtq/Cb4qyfIup 9VydpV0FZsM7T1WFXObfqGNvXRy2bJg= X-Google-Smtp-Source: ABdhPJxULeXwUZBMmge6DxRbN5gFb+g+oreTQuGqDiTZoP/lXUbRezVwUrFfGcKvIkdzuj9uzXIs4Q== X-Received: by 2002:a05:6808:199:: with SMTP id w25mr932374oic.151.1609804232526; Mon, 04 Jan 2021 15:50:32 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:32 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 03/17] merge-ort: collect which directories are removed in dirs_removed Date: Mon, 4 Jan 2021 15:49:52 -0800 Message-Id: <20210104235006.2867404-4-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- merge-ort.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 8b190b0ea5..f67ecdd171 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -532,6 +532,27 @@ static void setup_path_info(struct merge_options *opt, result->util = mi; } +static void collect_rename_info(struct merge_options *opt, + struct name_entry *names, + const char *dirname, + const char *fullname, + unsigned filemask, + unsigned dirmask, + unsigned match_mask) +{ + struct rename_info *renames = &opt->priv->renames; + + /* Update dirs_removed, as needed */ + if (dirmask == 1 || dirmask == 3 || dirmask == 5) { + /* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */ + unsigned sides = (0x07 - dirmask)/2; + if (sides & 1) + strset_add(&renames->dirs_removed[1], fullname); + if (sides & 2) + strset_add(&renames->dirs_removed[2], fullname); + } +} + static int collect_merge_info_callback(int n, unsigned long mask, unsigned long dirmask, @@ -632,6 +653,12 @@ static int collect_merge_info_callback(int n, return mask; } + /* + * Gather additional information used in rename detection. + */ + collect_rename_info(opt, names, dirname, fullpath, + filemask, dirmask, match_mask); + /* * Record information about the path so we can resolve later in * process_entries. From patchwork Mon Jan 4 23:49:53 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997795 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0D79DC433E0 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D498822519 for ; Mon, 4 Jan 2021 23:51:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727867AbhADXvQ (ORCPT ); Mon, 4 Jan 2021 18:51:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33644 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvP (ORCPT ); Mon, 4 Jan 2021 18:51:15 -0500 Received: from mail-ot1-x331.google.com (mail-ot1-x331.google.com [IPv6:2607:f8b0:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 35180C061796 for ; Mon, 4 Jan 2021 15:50:34 -0800 (PST) Received: by mail-ot1-x331.google.com with SMTP id j12so27703338ota.7 for ; Mon, 04 Jan 2021 15:50:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=NY/QvUSxgLx3VRAo5824Vs664wHz4pGpKBxjHUNrye4=; b=iECkFFnE/dO7Y2RgFY9Vw9Icgf4g+qOvWEkoa+X6eeUY2PbQePx0kxXF605j6IZdkK aqumTsb0QzeTv0C/IMbP0Yw0+QQBr0GGCwiWqueZfRCE+cYF/FZtblIzQfzhZaYHbYaN UL0n6IXveef+unE+7/3nyviFR3ylnPwRYz2pweAZM7MbTLh7TN0+yAi2HQf2lT/iaXU3 byfRXHamEhME3+wmghUxNgVndHVHW/DkEbw1Iowp4fNreYrMPEJz5iSWqZkrRNcL1gIx APugOcVsLMcuL4+BzeJVJoZz1rvAr0l0LKlGrxqbpI1c3KCu+nJGJY2rvWOYJoxLGE8M yWtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NY/QvUSxgLx3VRAo5824Vs664wHz4pGpKBxjHUNrye4=; b=iwOhO7XHNeqI/sJeYb3wDmRrUYeo4q08dm9kxY52ElkBXlwksGCmLrGg66NFBTLEdr BUIrYw8W7hvSCyyrRg5NatcXhJK41JF11x07x7P+0wAsad/+8CZdX/7opN0qaAxQghaq lbjO5GQvxInTbLaax5GOdAD9GHevNZU6aVo7Bff18hwMlPUlWd02TgAA/AfV3DS0ayPL cXI2l67ndzeg1dZSFX9QVrAw8mQWkKpQ1b50K5RoDgA++1Lsh5nxxLSw1eg+GapJl1ab TBSlN3Ws+mvetszgoI9xMfax6FfgT+KpKWZ9f+QqOTmCng5cAj4XEdgzhikICnOg5OjT 0ddg== X-Gm-Message-State: AOAM531uTvnXZXurotJ68/OBawd3q3u2HgXyBIg8stbXlVOifJYL7lnA QcxGoXGAgX2j7PRZHo+JIBr1+ZtPGkM= X-Google-Smtp-Source: ABdhPJza6IHyswiTMA83ZWwjWX5hxt5zohP8IaJSgD2NPJhvEpaz09SDDTrmW47/Yb/cjkS1CXaZdA== X-Received: by 2002:a9d:4e84:: with SMTP id v4mr55344353otk.45.1609804233497; Mon, 04 Jan 2021 15:50:33 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:33 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 04/17] merge-ort: add outline for computing directory renames Date: Mon, 4 Jan 2021 15:49:53 -0800 Message-Id: <20210104235006.2867404-5-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Port some directory rename handling changes from merge-recursive.c's detect_and_process_renames() to the same-named function of merge-ort.c. This does not yet add any use or handling of directory renames, just the outline for where we start to compute them. Thus, a future patch will add port additional changes to merge-ort's detect_and_process_renames(). Signed-off-by: Elijah Newren --- merge-ort.c | 25 ++++++++++++++++++++++++- 1 file changed, 24 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index f67ecdd171..0bd0ab1e8b 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1139,6 +1139,18 @@ static int handle_content_merge(struct merge_options *opt, /*** Function Grouping: functions related to directory rename detection ***/ +static void get_provisional_directory_renames(struct merge_options *opt, + unsigned side, + int *clean) +{ + die("Not yet implemented!"); +} + +static void handle_directory_level_conflicts(struct merge_options *opt) +{ + die("Not yet implemented!"); +} + /*** Function Grouping: functions related to regular rename detection ***/ static int process_renames(struct merge_options *opt, @@ -1504,13 +1516,24 @@ static int detect_and_process_renames(struct merge_options *opt, { struct diff_queue_struct combined; struct rename_info *renames = &opt->priv->renames; - int s, clean = 1; + int need_dir_renames, s, clean = 1; memset(&combined, 0, sizeof(combined)); detect_regular_renames(opt, merge_base, side1, MERGE_SIDE1); detect_regular_renames(opt, merge_base, side2, MERGE_SIDE2); + need_dir_renames = + !opt->priv->call_depth && + (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE || + opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_CONFLICT); + + if (need_dir_renames) { + for (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) + get_provisional_directory_renames(opt, s, &clean); + handle_directory_level_conflicts(opt); + } + ALLOC_GROW(combined.queue, renames->pairs[1].nr + renames->pairs[2].nr, combined.alloc); From patchwork Mon Jan 4 23:49:54 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997801 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5461BC433E6 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1938022519 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727860AbhADXvP (ORCPT ); Mon, 4 Jan 2021 18:51:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33646 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727850AbhADXvP (ORCPT ); Mon, 4 Jan 2021 18:51:15 -0500 Received: from mail-ot1-x333.google.com (mail-ot1-x333.google.com [IPv6:2607:f8b0:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 28D5EC061798 for ; Mon, 4 Jan 2021 15:50:35 -0800 (PST) Received: by mail-ot1-x333.google.com with SMTP id j12so27703368ota.7 for ; Mon, 04 Jan 2021 15:50:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=gske+Yavvz+ocnpd1TmNj2kn5OMntlBdi/x6/WJqZdg=; b=uRE66ULjJgy37M7cy7pcbCm0EdLSdZF/cr+2nqbbTnCMHeXTebuLJ9RjcXo83XPDKL /mTfFtAJzEigY3pYj4ZvlcLp3wwEu1WkDQonCAHeGGKbzSXj9HKHSH2Tfg5aLfr24dn4 xcpDxTpUU5os8mMgKpLryUfDhdckN74VfZsDSF9rirOaaS0vE9eU9ABMBSHhppvaoZR3 wpdrS2WjfVk6jKHkbwV6T+q7UjkY8r0n0hI+deVAslP5JuHqj/bgRq5Lx9YLgttXGMZ3 EOZaOZlkyNjkmgz0cz1+E9nwGrLsOBDQPkYDpmPristjUnIN7xAkURcUPuQiDuwF4zpI uzyQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=gske+Yavvz+ocnpd1TmNj2kn5OMntlBdi/x6/WJqZdg=; b=XX3O79UvqSWZC+SH5qj8avHqRvn7iOoiyJZ/Er0L7SR7pS0wk2bVNogcho3mAGetSU Ek5VbcjfTCefqTvJu8BIgWJxY7EuS/+0A2Tsc8KZXh3cqFliRCagwMnYVEGb+cwUNHcS 7n4gj6J8QnBRmtkEse7ghLVadMPO3/yR4u8BlhH35l5J1WZN/ViV15dVyX3jwsZxsE3t EpPJAza0GrDSiWC8UAYPMFEQjQfToyY+9KCn3F+0HqU3Z1wtnqL3qFjMw8MkPeewA0ff m3X8pmtTE1LCS7hV7AHA2yUmogHSC2Y++X/3woCIXMwFvDv1p+iYDyPjW6E3kHD9mlPq G9tA== X-Gm-Message-State: AOAM532KATmR5Tn3bwEnmwqj2il1RrLjBrrrvChi0pYZGhhhBqNyRNbW iCCwQ102F+OdU2z+F15V81amRESlMxA= X-Google-Smtp-Source: ABdhPJw0QEsoSBbt5mig9GTPe5M5IegYSFCREI8M28nvSQJ6iWVYN9x9Tii6nqkjRkmBrzl4GuCarg== X-Received: by 2002:a05:6830:1352:: with SMTP id r18mr52465158otq.73.1609804234449; Mon, 04 Jan 2021 15:50:34 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:34 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 05/17] merge-ort: add outline of get_provisional_directory_renames() Date: Mon, 4 Jan 2021 15:49:54 -0800 Message-Id: <20210104235006.2867404-6-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This function is based on merge-recursive.c's get_directory_renames(), except that the first half has been split out into a not-yet-implemented compute_rename_counts(). The primary difference here is our lack of the non_unique_new_dir boolean in our strmap. The lack of that field will at first cause us to fail testcase 2b of t6423; however, future optimizations will obviate the need for that ugly field so we have just left it out. Signed-off-by: Elijah Newren --- merge-ort.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 59 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 0bd0ab1e8b..6ccc7a1a45 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1139,11 +1139,69 @@ static int handle_content_merge(struct merge_options *opt, /*** Function Grouping: functions related to directory rename detection ***/ +static void compute_rename_counts(struct diff_queue_struct *pairs, + struct strmap *dir_rename_count, + struct strset *dirs_removed) +{ + die("Not yet implemented!"); +} + static void get_provisional_directory_renames(struct merge_options *opt, unsigned side, int *clean) { - die("Not yet implemented!"); + struct hashmap_iter iter; + struct strmap_entry *entry; + struct rename_info *renames = &opt->priv->renames; + + compute_rename_counts(&renames->pairs[side], + &renames->dir_rename_count[side], + &renames->dirs_removed[side]); + /* + * Collapse + * dir_rename_count: old_directory -> {new_directory -> count} + * down to + * dir_renames: old_directory -> best_new_directory + * where best_new_directory is the one with the unique highest count. + */ + strmap_for_each_entry(&renames->dir_rename_count[side], &iter, entry) { + const char *source_dir = entry->key; + struct strintmap *counts = entry->value; + struct hashmap_iter count_iter; + struct strmap_entry *count_entry; + int max = 0; + int bad_max = 0; + const char *best = NULL; + + strintmap_for_each_entry(counts, &count_iter, count_entry) { + const char *target_dir = count_entry->key; + intptr_t count = (intptr_t)count_entry->value; + + if (count == max) + bad_max = max; + else if (count > max) { + max = count; + best = target_dir; + } + } + + if (max == 0) + continue; + + if (bad_max == max) { + path_msg(opt, source_dir, 0, + _("CONFLICT (directory rename split): " + "Unclear where to rename %s to; it was " + "renamed to multiple other directories, with " + "no destination getting a majority of the " + "files."), + source_dir); + *clean &= 0; + } else { + strmap_put(&renames->dir_renames[side], + source_dir, (void*)best); + } + } } static void handle_directory_level_conflicts(struct merge_options *opt) From patchwork Mon Jan 4 23:49:55 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997797 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2D98EC433DB for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 02CC22253D for ; Mon, 4 Jan 2021 23:51:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727878AbhADXvQ (ORCPT ); Mon, 4 Jan 2021 18:51:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33648 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvQ (ORCPT ); Mon, 4 Jan 2021 18:51:16 -0500 Received: from mail-ot1-x32b.google.com (mail-ot1-x32b.google.com [IPv6:2607:f8b0:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2BDBCC06179A for ; Mon, 4 Jan 2021 15:50:36 -0800 (PST) Received: by mail-ot1-x32b.google.com with SMTP id j20so27739443otq.5 for ; Mon, 04 Jan 2021 15:50:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=D3/K76RpxK95m/dgFzqFg6bo0ITTMqrb4v0r2gO+Kok=; b=fkYeQI6Cd+3tCaGuu5vsBvLgA6HX2A8fJBNIuW4kHAqefrw0ZOXiR22IEcmC/WZ9Va ZVAHZr0XM/7iurzVjWQgZ+2vD894GZV0xtOO0kU1CJsnot7VGPjn3o2LNxiVSwBqWkYO 77ddt0aK5yYpvLcmh6qt0Zr9cQiuOFelsn2ubooMYxJCen5iXUtU19zB9a5Iotp58p4Z bB9ITIHdbX7pYsjn9KVVSSxaGYEbRLhV3cgvUlGX8UkmRAzEvuBek9CCpA1JIMyiww/W U/8lqq237K3o0kQ73mYGZhespsrP15IsCPEtJ8cNJ9TIqTneTpKSgrF9YQAjPwb6i6V1 tWkQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=D3/K76RpxK95m/dgFzqFg6bo0ITTMqrb4v0r2gO+Kok=; b=SZ+pcLN/VaQ/o9zMXP8AE/26lyyzZTM3FNtLvWxHppxPqNKtWeAmgxn2qdYCliZSWT VfbmZ3Cumsn00pVWsBSma9tjn/88M5yH3JNwNTsl9d2/3JBJcYaeOgBHnH/wtpKCsNxF lSygVnLL3tS2niRCnRNKkJJrZspYZICYDcoPbzVEon2Okrv37rDpBYqKZ1Unzydm622J 2k2R51b1w6b5yXwMqLz+gtzYGYWILTCREmv6x4XGybgq83O6usbs7RBkJnCkjzJBEYve +Pc506mAwmjX3VfjknscbtLdCjgpDxVHWaVeuD6l9yU2XIJ/d7koYDcvBQvBx8o51Aj/ 8voA== X-Gm-Message-State: AOAM532PA27op5HvrNozRDRcduFUpY0P36POiksiv7ztSqGYVbo+KAwm zALpOilj5wLommonCIr7lpb6fmxP/zs= X-Google-Smtp-Source: ABdhPJxTMeoyxnKPAX2NQ2M0bSBFZ+qnVG0UpjQGff7tlTlMVU8n33huBt5oxVxtgd3duEVS/cdXcg== X-Received: by 2002:a9d:508:: with SMTP id 8mr54538827otw.338.1609804235419; Mon, 04 Jan 2021 15:50:35 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:35 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 06/17] merge-ort: copy get_renamed_dir_portion() from merge-recursive.c Date: Mon, 4 Jan 2021 15:49:55 -0800 Message-Id: <20210104235006.2867404-7-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- merge-ort.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 104 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 6ccc7a1a45..19c3f8d41d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1139,6 +1139,110 @@ static int handle_content_merge(struct merge_options *opt, /*** Function Grouping: functions related to directory rename detection ***/ +MAYBE_UNUSED +static void get_renamed_dir_portion(const char *old_path, const char *new_path, + char **old_dir, char **new_dir) +{ + char *end_of_old, *end_of_new; + + /* Default return values: NULL, meaning no rename */ + *old_dir = NULL; + *new_dir = NULL; + + /* + * For + * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c" + * the "e/foo.c" part is the same, we just want to know that + * "a/b/c/d" was renamed to "a/b/some/thing/else" + * so, for this example, this function returns "a/b/c/d" in + * *old_dir and "a/b/some/thing/else" in *new_dir. + */ + + /* + * If the basename of the file changed, we don't care. We want + * to know which portion of the directory, if any, changed. + */ + end_of_old = strrchr(old_path, '/'); + end_of_new = strrchr(new_path, '/'); + + /* + * If end_of_old is NULL, old_path wasn't in a directory, so there + * could not be a directory rename (our rule elsewhere that a + * directory which still exists is not considered to have been + * renamed means the root directory can never be renamed -- because + * the root directory always exists). + */ + if (end_of_old == NULL) + return; /* Note: *old_dir and *new_dir are still NULL */ + + /* + * If new_path contains no directory (end_of_new is NULL), then we + * have a rename of old_path's directory to the root directory. + */ + if (end_of_new == NULL) { + *old_dir = xstrndup(old_path, end_of_old - old_path); + *new_dir = xstrdup(""); + return; + } + + /* Find the first non-matching character traversing backwards */ + while (*--end_of_new == *--end_of_old && + end_of_old != old_path && + end_of_new != new_path) + ; /* Do nothing; all in the while loop */ + + /* + * If both got back to the beginning of their strings, then the + * directory didn't change at all, only the basename did. + */ + if (end_of_old == old_path && end_of_new == new_path && + *end_of_old == *end_of_new) + return; /* Note: *old_dir and *new_dir are still NULL */ + + /* + * If end_of_new got back to the beginning of its string, and + * end_of_old got back to the beginning of some subdirectory, then + * we have a rename/merge of a subdirectory into the root, which + * needs slightly special handling. + * + * Note: There is no need to consider the opposite case, with a + * rename/merge of the root directory into some subdirectory + * because as noted above the root directory always exists so it + * cannot be considered to be renamed. + */ + if (end_of_new == new_path && + end_of_old != old_path && end_of_old[-1] == '/') { + *old_dir = xstrndup(old_path, --end_of_old - old_path); + *new_dir = xstrdup(""); + return; + } + + /* + * We've found the first non-matching character in the directory + * paths. That means the current characters we were looking at + * were part of the first non-matching subdir name going back from + * the end of the strings. Get the whole name by advancing both + * end_of_old and end_of_new to the NEXT '/' character. That will + * represent the entire directory rename. + * + * The reason for the increment is cases like + * a/b/star/foo/whatever.c -> a/b/tar/foo/random.c + * After dropping the basename and going back to the first + * non-matching character, we're now comparing: + * a/b/s and a/b/ + * and we want to be comparing: + * a/b/star/ and a/b/tar/ + * but without the pre-increment, the one on the right would stay + * a/b/. + */ + end_of_old = strchr(++end_of_old, '/'); + end_of_new = strchr(++end_of_new, '/'); + + /* Copy the old and new directories into *old_dir and *new_dir. */ + *old_dir = xstrndup(old_path, end_of_old - old_path); + *new_dir = xstrndup(new_path, end_of_new - new_path); +} + static void compute_rename_counts(struct diff_queue_struct *pairs, struct strmap *dir_rename_count, struct strset *dirs_removed) From patchwork Mon Jan 4 23:49:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997805 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8ADBBC4332B for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 64B6522519 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727882AbhADXvT (ORCPT ); Mon, 4 Jan 2021 18:51:19 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33654 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727879AbhADXvR (ORCPT ); Mon, 4 Jan 2021 18:51:17 -0500 Received: from mail-ot1-x32f.google.com (mail-ot1-x32f.google.com [IPv6:2607:f8b0:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 380DCC06179F for ; Mon, 4 Jan 2021 15:50:37 -0800 (PST) Received: by mail-ot1-x32f.google.com with SMTP id q25so27699869otn.10 for ; Mon, 04 Jan 2021 15:50:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=QSa86NgttJOKxMMPzERywp7Xg2m01EcqQ8oR72Q8BZo=; b=ptCvtjrW80vWG3ECa+3QV4WGC+UJbNKFeuc1/VvCToRRt9cgeOSLAJcMUrWFje9p0u 44zxKB8P1aRhIoIDm1p4/lOeA3JoMy02jxAWclHmHTX2P2OMGuAoM7JLugQfh0DDgfmP Mi1Qj1daA7Yd+AL/lYy7hihzKOfzOldc5VjVkwpwnOzS6eMlohurK07fmhBMqstkjZ1p hr+EkKgRMIY+A0DmtROREFwHcxs6DIEf49Uh8hRl1RtssVsrbDGtL7Ko84bG2gD3x7D+ qTNviYjw0dCBQMCyJQtmJVj1soufgyQ9uEN/QtkaQxp7hsGAycNfm+CHRiMKv6dgstiX UWaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=QSa86NgttJOKxMMPzERywp7Xg2m01EcqQ8oR72Q8BZo=; b=AvKKUOVkI9BA2/fK74Dj2fj2R1IaI2Xwfz2ZucE4sJF7HxgQDQk8yJOa4WTaqvebhG 92gZPi8T84Oz9dRVC8ot5d5EhcWb2Jw8JGglDvvF6iauUfXCNbwVCAUBPTQZXSDUW8P+ oW/L1f6l5aIkvJDWGgxujjthRKJaSZxHUsLTrqNZHeIh7gCRVw0SHeD9z8+sfvnbFvR8 qF0NOOGcCI2xKHMCI1lwGz1NB5hAGxT1Owxklksc/o9wk7AnZntvs621XcbPWo1sl6S7 4QYh3WMzU8mB5MgXetYcdgphwzDe4w67sB4PpOaBWb3jFF+WSc6m8m6o2GCRBEzqFFXm qhtQ== X-Gm-Message-State: AOAM53382uTMCt0lYbzl3v795y3vDmSaYLpsJ1FTHORXCitIRe5svvf7 RKlI6YCmBl5U4olIY6wDjpLw0xdmdWs= X-Google-Smtp-Source: ABdhPJyRPFnVkCwE+D3O6Bjo1qmRbGySCG7FuANqkyhDpisSnfr/uFqQfcUTwpRqlCO8OCGqS4PbqQ== X-Received: by 2002:a05:6830:1411:: with SMTP id v17mr55789593otp.352.1609804236387; Mon, 04 Jan 2021 15:50:36 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:35 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 07/17] merge-ort: implement compute_rename_counts() Date: Mon, 4 Jan 2021 15:49:56 -0800 Message-Id: <20210104235006.2867404-8-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This function is based on the first half of get_directory_renames() from merge-recursive.c Signed-off-by: Elijah Newren --- merge-ort.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 51 insertions(+), 2 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 19c3f8d41d..05bac9c5bd 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1139,7 +1139,6 @@ static int handle_content_merge(struct merge_options *opt, /*** Function Grouping: functions related to directory rename detection ***/ -MAYBE_UNUSED static void get_renamed_dir_portion(const char *old_path, const char *new_path, char **old_dir, char **new_dir) { @@ -1243,11 +1242,61 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path, *new_dir = xstrndup(new_path, end_of_new - new_path); } +static void increment_count(struct strmap *dir_rename_count, + char *old_dir, + char *new_dir) +{ + struct strintmap *counts; + struct strmap_entry *e; + + /* Get the {new_dirs -> counts} mapping using old_dir */ + e = strmap_get_entry(dir_rename_count, old_dir); + if (e) { + counts = e->value; + } else { + counts = xmalloc(sizeof(*counts)); + strintmap_init_with_options(counts, 0, NULL, 1); + strmap_put(dir_rename_count, old_dir, counts); + } + + /* Increment the count for new_dir */ + strintmap_incr(counts, new_dir, 1); +} + static void compute_rename_counts(struct diff_queue_struct *pairs, struct strmap *dir_rename_count, struct strset *dirs_removed) { - die("Not yet implemented!"); + int i; + + for (i = 0; i < pairs->nr; ++i) { + char *old_dir, *new_dir; + struct diff_filepair *pair = pairs->queue[i]; + + if (pair->status != 'R') + continue; + + /* Get the old and new directory names */ + get_renamed_dir_portion(pair->one->path, pair->two->path, + &old_dir, &new_dir); + if (!old_dir) + /* Directory didn't change at all; ignore this one. */ + continue; + + /* + * Make dir_rename_count contain a map of a map: + * old_directory -> {new_directory -> count} + * In other words, for every pair look at the directories for + * the old filename and the new filename and count how many + * times that pairing occurs. + */ + if (strset_contains(dirs_removed, old_dir)) + increment_count(dir_rename_count, old_dir, new_dir); + + /* Free resources we don't need anymore */ + free(old_dir); + free(new_dir); + } } static void get_provisional_directory_renames(struct merge_options *opt, From patchwork Mon Jan 4 23:49:57 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997781 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 81988C433DB for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 532442253D for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727811AbhADXuz (ORCPT ); Mon, 4 Jan 2021 18:50:55 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726749AbhADXuy (ORCPT ); Mon, 4 Jan 2021 18:50:54 -0500 Received: from mail-ot1-x334.google.com (mail-ot1-x334.google.com [IPv6:2607:f8b0:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2703BC0617A0 for ; Mon, 4 Jan 2021 15:50:38 -0800 (PST) Received: by mail-ot1-x334.google.com with SMTP id 11so27690835oty.9 for ; Mon, 04 Jan 2021 15:50:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=+ZIxZE7OXOiV/nMspJY3IPbpEz60W3Z7PXDTFbpft1U=; b=nhTQ5/m5qBxNJk9u9vjJhtoJ7e19iSgNjhu6arAfWxq6fmolZVNWrfWj3ZtlZTNeY2 MSHPB9CJgCwaZSQ4Qb48dgKcLBB8gdK5l2x15MVZlN9U7oN84BiIVEtwX9GE9RoJpHXu kdR7jZFQnL4G9f/KcZwIDdgWZRla3moABIvrQhn6lorb7DrrLIdBfJLMtE7t0AqJbt85 vLquXFGeGLFgv0zkrsX78ctg+pf99E/mfJFCr54u9Wq87pyewKjIKj6+RcEtENIeZqUm oWE5/Qif1nTaP2QN5ua5YGsPdmAz5gq3bDVZKuO6zsqTKsCPi9zrDx6g6ZLEk0p/Hytv KsNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=+ZIxZE7OXOiV/nMspJY3IPbpEz60W3Z7PXDTFbpft1U=; b=OfVIfAQFImV2FMPb8f2o0t7fIX4NW4YojIObyrDiYeyMx5Djnram8GJH214SlAoa6j FdKQMN6MyOZtALO0VzgE4OmupEUEnt4+T81/Lo/uNXlUPJKYBtqMdYVeT/E/9kjtQ7ZG 15FxxL6wmcuDYgZ6SbOZz1TJTc10rRGxefCq2AM+X9x5w6xebdhyvZUvGGxnOJOvBl06 Xg37qtHroMSFUFFzUWQEjdLNnwYz8Pc2b3fTuvJp3UTNjqJxp1JR/AhAI1jndEe7tsoB oXRD3s/kfevigquQWVkwV+d30DIq6EmcY4vilgTyHXzDk3u459kNuG/DXVbrJwhXSyFp S9tw== X-Gm-Message-State: AOAM533evVLRgE43gHOdmA52oBEA/pvKNsPN2dNr3hYOECAytCS55SP7 iVkfWbFhHLQl1ZpYp6Fpdq8d5pcGB/o= X-Google-Smtp-Source: ABdhPJy4V2t8gZdvcDgzVew/xM4h5rw/9eVh5hMwFlkiNlu7qZ1Q0jeE4WUai2GBd9/Ely6xYCfb2Q== X-Received: by 2002:a05:6830:114a:: with SMTP id x10mr54517091otq.350.1609804237452; Mon, 04 Jan 2021 15:50:37 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:37 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 08/17] merge-ort: implement handle_directory_level_conflicts() Date: Mon, 4 Jan 2021 15:49:57 -0800 Message-Id: <20210104235006.2867404-9-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This is modelled on the version of handle_directory_level_conflicts() from merge-recursive.c, but is massively simplified due to the following factors: * strmap API provides simplifications over using direct hashamp * we have a dirs_removed field in struct rename_info that we have an easy way to populate from collect_merge_info(); this was already used in compute_rename_counts() and thus we do not need to check for condition #2. * The removal of condition #2 by handling it earlier in the code also obviates the need to check for condition #3 -- if both sides renamed a directory, meaning that the directory no longer exists on either side, then neither side could have added any new files to that directory, and thus there are no files whose locations we need to move due to such a directory rename. In fact, the same logic that makes condition #3 irrelevant means condition #1 is also irrelevant so we could drop this function. However, it is cheap to check if both sides rename the same directory, and doing so can save future computation. So, simply remove any directories that both sides renamed from the list of directory renames. Signed-off-by: Elijah Newren --- merge-ort.c | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 05bac9c5bd..c4f437d4c0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1359,7 +1359,23 @@ static void get_provisional_directory_renames(struct merge_options *opt, static void handle_directory_level_conflicts(struct merge_options *opt) { - die("Not yet implemented!"); + struct hashmap_iter iter; + struct strmap_entry *entry; + struct string_list duplicated = STRING_LIST_INIT_NODUP; + struct strmap *side1_dir_renames = &opt->priv->renames.dir_renames[1]; + struct strmap *side2_dir_renames = &opt->priv->renames.dir_renames[2]; + int i; + + strmap_for_each_entry(side1_dir_renames, &iter, entry) { + if (strmap_contains(side2_dir_renames, entry->key)) + string_list_append(&duplicated, entry->key); + } + + for (i=0; i X-Patchwork-Id: 11997803 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 70B44C43381 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4FBD82255F for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727902AbhADXvV (ORCPT ); Mon, 4 Jan 2021 18:51:21 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33662 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvU (ORCPT ); Mon, 4 Jan 2021 18:51:20 -0500 Received: from mail-oo1-xc2d.google.com (mail-oo1-xc2d.google.com [IPv6:2607:f8b0:4864:20::c2d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 77F8FC0617A2 for ; Mon, 4 Jan 2021 15:50:39 -0800 (PST) Received: by mail-oo1-xc2d.google.com with SMTP id 9so6688018ooy.7 for ; Mon, 04 Jan 2021 15:50:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=2NDkgdwIZLhIA+8d2WTIMJr3YqBZJibNdEHzP4jnCck=; b=upg2qBTTQOPDsF1YuYk8+94EbFNC/fZxxRN/2r1XzmcbOeo5N/SlUNpeL8KILFUK82 /aAUvVPDxO9ioCoQXaQ9tv+mupFko47WGzg9g9Xz3Z9qXpu+VX1DzE2tnZO737k+w3Pm 5v8aTk58MVxrlJXWfLweNwbbGeLn2O1XrZWsPLPKm8MGh19ru5QQ+q5sr/g5WASv27vD ZSBfsTZlOkmW806Yt872SIEgvmi2NeCRi7iMeu3R40iJPfun6EofKcT49Ph2Rs1s+B4e 6s6Uq5zZ6e6fBSLMcZiDjleNJeI9nbyDdU12UJ2WEmAIvG5hwQMvQPox3m+5wupdJzNZ bnOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=2NDkgdwIZLhIA+8d2WTIMJr3YqBZJibNdEHzP4jnCck=; b=eGnXQde6lSNoFpbxU8okZ0nVg5qNSXbhDrCShK9f0Ez2gNrmajkjTJK7u1qRwl2vbY zdBp2K8q8mIy1ZnDdyeeQKqBQFF74njR+TJSnqB3xw8sP2bMrPeUBAlvedJ/kM+ISP5Y dwiIFWqv2d3L3OIdOLNev9b2Tpwm5FHRbf3N6KgjeMlJ82mfQEaI8r2RUgvZGrRy7IWd S8xRPYkI3y6SiRbvIjnsTP+xMUXXCyKBV2l8Hm1V3MuIBlUAH0He/A2FJhhjNjPJeTBx yyMyuHPAqho2ZCO/mehysQ3Ch2Ngkqs7sJiIo+hNU/RyqOXDAGP9VmDOzGWX9KMUi+Bi /rZg== X-Gm-Message-State: AOAM532pZCP10/ePFxUpr9cjjmGkcC6HNCyCwBvkHm1I+huPKEMBfQpu gkMFPQZgd0gJm+hUiCIauk0TIIWCroU= X-Google-Smtp-Source: ABdhPJz0qh4J1MBxy9ZiH81as6CynhDKkX47jKMfzYU8wqnIipXBOd0ZuJO1TKZcogCnv4Bnyg1EaA== X-Received: by 2002:a4a:901a:: with SMTP id i26mr50894069oog.42.1609804238698; Mon, 04 Jan 2021 15:50:38 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:38 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 09/17] merge-ort: modify collect_renames() for directory rename handling Date: Mon, 4 Jan 2021 15:49:58 -0800 Message-Id: <20210104235006.2867404-10-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org collect_renames() is similar to merge-recursive.c's get_renames(), but lacks the directory rename handling found in the latter. Port that code structure over to merge-ort. This introduces three new die-not-yet-implemented functions that will be defined in future commits. Signed-off-by: Elijah Newren --- merge-ort.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 74 insertions(+), 4 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index c4f437d4c0..a52905c4ee 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1139,6 +1139,11 @@ static int handle_content_merge(struct merge_options *opt, /*** Function Grouping: functions related to directory rename detection ***/ +struct collision_info { + struct string_list source_files; + unsigned reported_already:1; +}; + static void get_renamed_dir_portion(const char *old_path, const char *new_path, char **old_dir, char **new_dir) { @@ -1378,6 +1383,31 @@ static void handle_directory_level_conflicts(struct merge_options *opt) string_list_clear(&duplicated, 0); } +static void compute_collisions(struct strmap *collisions, + struct strmap *dir_renames, + struct diff_queue_struct *pairs) +{ + die("Not yet implemented."); +} + +static char *check_for_directory_rename(struct merge_options *opt, + const char *path, + unsigned side_index, + struct strmap *dir_renames, + struct strmap *dir_rename_exclusions, + struct strmap *collisions, + int *clean_merge) +{ + die("Not yet implemented."); +} + +static void apply_directory_rename_modifications(struct merge_options *opt, + struct diff_filepair *pair, + char *new_path) +{ + die("Not yet implemented."); +} + /*** Function Grouping: functions related to regular rename detection ***/ static int process_renames(struct merge_options *opt, @@ -1703,22 +1733,44 @@ static void detect_regular_renames(struct merge_options *opt, */ static int collect_renames(struct merge_options *opt, struct diff_queue_struct *result, - unsigned side_index) + unsigned side_index, + struct strmap *dir_renames_for_side, + struct strmap *rename_exclusions) { int i, clean = 1; + struct strmap collisions; struct diff_queue_struct *side_pairs; + struct hashmap_iter iter; + struct strmap_entry *entry; struct rename_info *renames = &opt->priv->renames; side_pairs = &renames->pairs[side_index]; + compute_collisions(&collisions, dir_renames_for_side, side_pairs); for (i = 0; i < side_pairs->nr; ++i) { struct diff_filepair *p = side_pairs->queue[i]; + char *new_path; /* non-NULL only with directory renames */ - if (p->status != 'R') { + if (p->status != 'A' && p->status != 'R') { diff_free_filepair(p); continue; } + new_path = check_for_directory_rename(opt, p->two->path, + side_index, + dir_renames_for_side, + rename_exclusions, + &collisions, + &clean); + + if (p->status != 'R' && !new_path) { + diff_free_filepair(p); + continue; + } + + if (new_path) + apply_directory_rename_modifications(opt, p, new_path); + /* * p->score comes back from diffcore_rename_extended() with * the similarity of the renamed file. The similarity is @@ -1733,6 +1785,20 @@ static int collect_renames(struct merge_options *opt, result->queue[result->nr++] = p; } + /* Free each value in the collisions map */ + strmap_for_each_entry(&collisions, &iter, entry) { + struct collision_info *info = entry->value; + string_list_clear(&info->source_files, 0); + } + /* + * In compute_collisions(), we set collisions.strdup_strings to 0 + * so that we wouldn't have to make another copy of the new_path + * allocated by apply_dir_rename(). But now that we've used them + * and have no other references to these strings, it is time to + * deallocate them. + */ + free_strmap_strings(&collisions); + strmap_clear(&collisions, 1); return clean; } @@ -1764,8 +1830,12 @@ static int detect_and_process_renames(struct merge_options *opt, ALLOC_GROW(combined.queue, renames->pairs[1].nr + renames->pairs[2].nr, combined.alloc); - clean &= collect_renames(opt, &combined, MERGE_SIDE1); - clean &= collect_renames(opt, &combined, MERGE_SIDE2); + clean &= collect_renames(opt, &combined, MERGE_SIDE1, + &renames->dir_renames[2], + &renames->dir_renames[1]); + clean &= collect_renames(opt, &combined, MERGE_SIDE2, + &renames->dir_renames[1], + &renames->dir_renames[2]); QSORT(combined.queue, combined.nr, compare_pairs); clean &= process_renames(opt, &combined); From patchwork Mon Jan 4 23:49:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997785 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 97A49C433E6 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 685F42255F for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727815AbhADXvD (ORCPT ); Mon, 4 Jan 2021 18:51:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33524 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727199AbhADXvC (ORCPT ); Mon, 4 Jan 2021 18:51:02 -0500 Received: from mail-ot1-x333.google.com (mail-ot1-x333.google.com [IPv6:2607:f8b0:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 76641C06179E for ; Mon, 4 Jan 2021 15:50:40 -0800 (PST) Received: by mail-ot1-x333.google.com with SMTP id q25so27699989otn.10 for ; Mon, 04 Jan 2021 15:50:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=/bMKGIkWjChas4gmQd1Tpi1mi8PGOvDQ31SZeYXakCw=; b=FB6wuj1VDLdVOAhjiu4gd68xaWtV9+ZfH1b0/MlCZ+cI7cNT6dHYrhwSPZ27xJ+i0n UVFxiTwnL+VEHM39vksF4i0RJAzm/nfVKd5cgJDuvXcseGzVo4CIozswN8s9Elevr8vI 0J3SKFfV1yEwnUYXWWDSQXwFWduy2FOR8hAVCJZSeB/XzetOYL9mOXpDTiLNwa6qb7/I ii6coNqfxXPhrFv7zlJYwvehSdI+0wK/xO1EPFOINLlaQ9yh4OswiInLBML6FKEtyuSt UST9kzYCnfUP4LSkk5cxCiFFS9ZAGYyMsykAv6XHruVHRCIialre5xO+48++L6Jo7Gqi VNYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=/bMKGIkWjChas4gmQd1Tpi1mi8PGOvDQ31SZeYXakCw=; b=RSdx2ZhrQb3C06yHHMtgz/Ww9RopFhQ17SCdVo7sJqq+1eNSn2QvwTeGZBmCK51yFM PAfpVeQ7d48ZXqh7Eu5GJKP6VeHSJLmHoAdcndW1eNPQ0HY0Dc+IKR0g5WxfqWobcedf bW69uSdmK73w3izrjybraAAQ8twTmQUPp860CCeQsuvGBYWFTdu1K32dkCBzZ+Ab/ZHH HMhqbDb52oNXC6a6YnAzxr95HA93zZ3D3RRqccsa0WqvGLvL9wU8Rs+03BlJnmxuHvk2 +CtSY7MyU3lQpCSWH2DrNBr6cV5cizTXRYEP2S4DcZQErxfAd5Ynf0UtT9j03E7Wq15/ 4Lxw== X-Gm-Message-State: AOAM533dsdDSRmZiAlZRCpzKPbr0nfZSkl9LbDF4Yu5lV0U8uVwpchPC Lo56kLCZvaC9jgHYwYSsyIElIWvXBAw= X-Google-Smtp-Source: ABdhPJyuX6h3KRt0JBsoN/7p0SZUr8FXVu7jPiIr4INUvpywbpMl2b/6f6XlKfnwni4UvyYvDjBdqg== X-Received: by 2002:a9d:2035:: with SMTP id n50mr52430625ota.44.1609804239699; Mon, 04 Jan 2021 15:50:39 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:39 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 10/17] merge-ort: implement compute_collisions() Date: Mon, 4 Jan 2021 15:49:59 -0800 Message-Id: <20210104235006.2867404-11-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This is nearly a wholesale copy of compute_collisions() from merge-recursive.c, and the logic remains the same, but it has been tweaked slightly due to: * using strmap.h API (instead of direct hashmaps) * allocation/freeing of data structures were done separately in merge_start() and clear_or_reinit_internal_opts() in an earlier patch in this series * there is no non_unique_new_dir data field in merge-ort; that will be handled a different way It does depend on two new functions, apply_dir_rename() and check_dir_renamed() which were introduced with simple die-not-yet-implemented shells and will be implemented in subsequent patches. Signed-off-by: Elijah Newren --- merge-ort.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 67 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index a52905c4ee..9c9be645ea 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1144,6 +1144,19 @@ struct collision_info { unsigned reported_already:1; }; +/* + * Return a new string that replaces the beginning portion (which matches + * rename_info->key), with rename_info->util.new_dir. In perl-speak: + * new_path_name = (old_path =~ s/rename_info->key/rename_info->value/); + * NOTE: + * Caller must ensure that old_path starts with rename_info->key + '/'. + */ +static char *apply_dir_rename(struct strmap_entry *rename_info, + const char *old_path) +{ + die("Not yet implemented!"); +} + static void get_renamed_dir_portion(const char *old_path, const char *new_path, char **old_dir, char **new_dir) { @@ -1383,11 +1396,64 @@ static void handle_directory_level_conflicts(struct merge_options *opt) string_list_clear(&duplicated, 0); } +static struct strmap_entry *check_dir_renamed(const char *path, + struct strmap *dir_renames) +{ + die("Not yet implemented!"); +} + static void compute_collisions(struct strmap *collisions, struct strmap *dir_renames, struct diff_queue_struct *pairs) { - die("Not yet implemented."); + int i; + + strmap_init_with_options(collisions, NULL, 0); + if (strmap_empty(dir_renames)) + return; + + /* + * Multiple files can be mapped to the same path due to directory + * renames done by the other side of history. Since that other + * side of history could have merged multiple directories into one, + * if our side of history added the same file basename to each of + * those directories, then all N of them would get implicitly + * renamed by the directory rename detection into the same path, + * and we'd get an add/add/.../add conflict, and all those adds + * from *this* side of history. This is not representable in the + * index, and users aren't going to easily be able to make sense of + * it. So we need to provide a good warning about what's + * happening, and fall back to no-directory-rename detection + * behavior for those paths. + * + * See testcases 9e and all of section 5 from t6043 for examples. + */ + for (i = 0; i < pairs->nr; ++i) { + struct strmap_entry *rename_info; + struct collision_info *collision_info; + char *new_path; + struct diff_filepair *pair = pairs->queue[i]; + + if (pair->status != 'A' && pair->status != 'R') + continue; + rename_info = check_dir_renamed(pair->two->path, dir_renames); + if (!rename_info) + continue; + + new_path = apply_dir_rename(rename_info, pair->two->path); + assert(new_path); + collision_info = strmap_get(collisions, new_path); + if (collision_info) { + free(new_path); + } else { + collision_info = xcalloc(1, + sizeof(struct collision_info)); + string_list_init(&collision_info->source_files, 0); + strmap_put(collisions, new_path, collision_info); + } + string_list_insert(&collision_info->source_files, + pair->two->path); + } } static char *check_for_directory_rename(struct merge_options *opt, From patchwork Mon Jan 4 23:50:00 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997811 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D4614C4332E for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B02812253D for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727925AbhADXv2 (ORCPT ); Mon, 4 Jan 2021 18:51:28 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33684 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXv1 (ORCPT ); Mon, 4 Jan 2021 18:51:27 -0500 Received: from mail-ot1-x32b.google.com (mail-ot1-x32b.google.com [IPv6:2607:f8b0:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 70E6AC0617A3 for ; Mon, 4 Jan 2021 15:50:41 -0800 (PST) Received: by mail-ot1-x32b.google.com with SMTP id j12so27703568ota.7 for ; Mon, 04 Jan 2021 15:50:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=IhFkzsBZ+eashqkkejacoo3lS8AN2lYp5V5hCqaa9DE=; b=GmxZyC7H1WO+8suE0OO5DxL/+Al6JgNqb3OJuJ9xh0JaETnEZG6UzpJe8b76/LR2o7 44PJOt9VkSCbw2YhMa8L36qdUafxxx+14mzIGizI5QMxudOzCEsAzd6qmKigAEqrM7cF B0LUff3HriBed8+NyHjDeFxl3OHDxkRNQxQXuh6h3M05/8gi8M0L24ic7m2d3+4mLpaJ xcrlrSZhelTa+285v/6b2Q4Gx2fbOePp45iS7xwqdGEmy1jQNP7g0YTpZZ4X4odRDWF4 4FUs1r/RULS9xgI1V4IDQ5AlBDWTut5I+yUIB7SsjD9jMdg7uTbT81T4renp1M2i3xOE YD2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=IhFkzsBZ+eashqkkejacoo3lS8AN2lYp5V5hCqaa9DE=; b=m5OTy26j3KusuuE7U2FgoJQRQJ51tmnBRCh9bBfMMVFerwCdttbp//To7qZUM4AwYY CpKbYjQIouZBareGpmNhDKxVebiZHsuH4Tk+MFDdJ+adfn1B8Brb+/E814gwDt+8vNzS UOzArox4PA8lIDTW7KMk2oJ56OqGKD5J6FpHNm33AE5yQSKUUKP/ylt4kGVUXK7QWPr4 aHnYgokAKLMvJSIyPNUCLoBeY3iIewZmtX5NFc7WUakCVHeGtWN/asO4c/O3wnz89Bby 6oNUWEquEmqI/J1aPQqIYgvBEqaD1edHo4DBHVV0ri/VXPNo9WEVb6diDAVQgmbPrmWP kN3g== X-Gm-Message-State: AOAM533j+aquTOqRa/jkuWyLGxwG+KGw1IgWcYx55TvLxCoTUEaNsaMc +AiZrpc/oOOxYOpkPx1JDKN8Yo8w/8o= X-Google-Smtp-Source: ABdhPJyets1aX6uMlQKUIVFCx904UBYSPkgZNkEJqRjkwXIubtYLRCyCdkbQ41BdrRlAzL09KLrqiA== X-Received: by 2002:a9d:2aaa:: with SMTP id e39mr51641199otb.10.1609804240679; Mon, 04 Jan 2021 15:50:40 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:40 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 11/17] merge-ort: implement apply_dir_rename() and check_dir_renamed() Date: Mon, 4 Jan 2021 15:50:00 -0800 Message-Id: <20210104235006.2867404-12-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Both of these are copied from merge-recursive.c, with just minor tweaks due to using strmap API and not having a non_unique_new_dir field. Signed-off-by: Elijah Newren --- merge-ort.c | 37 +++++++++++++++++++++++++++++++++++-- 1 file changed, 35 insertions(+), 2 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 9c9be645ea..f7f2470c96 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1154,7 +1154,29 @@ struct collision_info { static char *apply_dir_rename(struct strmap_entry *rename_info, const char *old_path) { - die("Not yet implemented!"); + struct strbuf new_path = STRBUF_INIT; + const char *old_dir = rename_info->key; + const char *new_dir = rename_info->value; + int oldlen, newlen, new_dir_len; + + oldlen = strlen(old_dir); + if (*new_dir == '\0') + /* + * If someone renamed/merged a subdirectory into the root + * directory (e.g. 'some/subdir' -> ''), then we want to + * avoid returning + * '' + '/filename' + * as the rename; we need to make old_path + oldlen advance + * past the '/' character. + */ + oldlen++; + new_dir_len = strlen(new_dir); + newlen = new_dir_len + (strlen(old_path) - oldlen) + 1; + strbuf_grow(&new_path, newlen); + strbuf_add(&new_path, new_dir, new_dir_len); + strbuf_addstr(&new_path, &old_path[oldlen]); + + return strbuf_detach(&new_path, NULL); } static void get_renamed_dir_portion(const char *old_path, const char *new_path, @@ -1399,7 +1421,18 @@ static void handle_directory_level_conflicts(struct merge_options *opt) static struct strmap_entry *check_dir_renamed(const char *path, struct strmap *dir_renames) { - die("Not yet implemented!"); + char *temp = xstrdup(path); + char *end; + struct strmap_entry *e = NULL; + + while ((end = strrchr(temp, '/'))) { + *end = '\0'; + e = strmap_get_entry(dir_renames, temp); + if (e) + break; + } + free(temp); + return e; } static void compute_collisions(struct strmap *collisions, From patchwork Mon Jan 4 23:50:01 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997789 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id AD701C433E9 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 813AE22519 for ; Mon, 4 Jan 2021 23:51:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727821AbhADXvK (ORCPT ); Mon, 4 Jan 2021 18:51:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727816AbhADXvJ (ORCPT ); Mon, 4 Jan 2021 18:51:09 -0500 Received: from mail-oi1-x22b.google.com (mail-oi1-x22b.google.com [IPv6:2607:f8b0:4864:20::22b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7821BC0617A4 for ; Mon, 4 Jan 2021 15:50:42 -0800 (PST) Received: by mail-oi1-x22b.google.com with SMTP id s2so34143169oij.2 for ; Mon, 04 Jan 2021 15:50:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=GieFQOSS2/WeB9FLiTOdNLbGs/riDswR5m//gi3jabY=; b=WIvOcZIbsxaGf4T65njEq1do+YISVu7wNEIL2c0vMFfzUSGJp0/H28LfQTIgNOLh8w d/R+d5+4XHSoivGliS9Mt8v2Pxzm40rpdYuW5I+YEB1bXt+LijZUnuGhYdkMSWJEs7W/ u/fJPNj7uOhnc3FknarLjJzyQwZxtFL5L7ieFpyXYgxZvf0ekztdTs4/3YpA+AHosf/x T34ghcI0ov+q5y2/XdMBFq1sE8GEmniBIgx/VlEFr3h+S1ASxl7DfzB4KWMJ704eewns jYIkN58DJyiIYV7kYFwc+gWip9v2u60u2NcVP/4pthOT4oeFuTK8OIDJdbNOwPd3zZwJ RLTw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=GieFQOSS2/WeB9FLiTOdNLbGs/riDswR5m//gi3jabY=; b=MwKgr07Dufc5YxmWyVduOiM0xTlSAebH/wPyso+MT6aE6rrj9aSNVT709mtFWXfZKK CLE7y5bQBa33rop3VtQsVijnUzSM6p7Chspjhi2xtHV5Hmj5pzRbhJqxcfsW/ResVhTG cpud9k5OLHh8UT8B7NXAKbljD1rEIlYoWFphyHY8WfsSwatNBuZI9O/+XQXEUAa6xj29 2X/zl3T3ps0pgS1zlC/kAb0PbwqZS7F1/XBYhhEUNcybRqXskj2MpUKlG19HLoemPl9U Gx0C8D2l4npVraUGj5vvehSEzlFVNuvKJJRuUwR0gDT9mDxrZuhSAyy0bYfhpxynMhSG 17JQ== X-Gm-Message-State: AOAM530zC+Jw5EFaBdGTT4C+xIMbJyhTrMkTJq8FeYBtiUxZQZ25pnft dNY7v+gjw1rDLQAdPYhlRSK5ruhz0LM= X-Google-Smtp-Source: ABdhPJywZtRCVc0dYX8qRn+0kpjTzfhWN6/3pWWgTVWFpoIoeE2f+NqmsWa7M7yd1anoB8dXe5UC6Q== X-Received: by 2002:aca:4257:: with SMTP id p84mr967572oia.176.1609804241699; Mon, 04 Jan 2021 15:50:41 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:41 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 12/17] merge-ort: implement check_for_directory_rename() Date: Mon, 4 Jan 2021 15:50:01 -0800 Message-Id: <20210104235006.2867404-13-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This is copied from merge-recursive.c, with minor tweaks due to using strmap API and the fact that it can use opt->priv->paths to get all pathnames that exist instead of taking a tree object. This depends on a new function, handle_path_level_conflicts(), which just has a placeholder die-not-yet-implemented implementation for now; a subsequent patch will implement it. Signed-off-by: Elijah Newren --- merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 66 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index f7f2470c96..84f4f4776b 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1282,6 +1282,21 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path, *new_dir = xstrndup(new_path, end_of_new - new_path); } +/* + * See if there is a directory rename for path, and if there are any file + * level conflicts on the given side for the renamed location. If there is + * a rename and there are no conflicts, return the new name. Otherwise, + * return NULL. + */ +static char *handle_path_level_conflicts(struct merge_options *opt, + const char *path, + unsigned side_index, + struct strmap_entry *rename_info, + struct strmap *collisions) +{ + die("Not yet implemented"); +} + static void increment_count(struct strmap *dir_rename_count, char *old_dir, char *new_dir) @@ -1497,7 +1512,57 @@ static char *check_for_directory_rename(struct merge_options *opt, struct strmap *collisions, int *clean_merge) { - die("Not yet implemented."); + char *new_path = NULL; + struct strmap_entry *rename_info; + struct strmap_entry *otherinfo = NULL; + const char *new_dir; + + if (strmap_empty(dir_renames)) + return new_path; + rename_info = check_dir_renamed(path, dir_renames); + if (!rename_info) + return new_path; + /* old_dir = rename_info->key; */ + new_dir = rename_info->value; + + /* + * This next part is a little weird. We do not want to do an + * implicit rename into a directory we renamed on our side, because + * that will result in a spurious rename/rename(1to2) conflict. An + * example: + * Base commit: dumbdir/afile, otherdir/bfile + * Side 1: smrtdir/afile, otherdir/bfile + * Side 2: dumbdir/afile, dumbdir/bfile + * Here, while working on Side 1, we could notice that otherdir was + * renamed/merged to dumbdir, and change the diff_filepair for + * otherdir/bfile into a rename into dumbdir/bfile. However, Side + * 2 will notice the rename from dumbdir to smrtdir, and do the + * transitive rename to move it from dumbdir/bfile to + * smrtdir/bfile. That gives us bfile in dumbdir vs being in + * smrtdir, a rename/rename(1to2) conflict. We really just want + * the file to end up in smrtdir. And the way to achieve that is + * to not let Side1 do the rename to dumbdir, since we know that is + * the source of one of our directory renames. + * + * That's why otherinfo and dir_rename_exclusions is here. + * + * As it turns out, this also prevents N-way transient rename + * confusion; See testcases 9c and 9d of t6043. + */ + otherinfo = strmap_get_entry(dir_rename_exclusions, new_dir); + if (otherinfo) { + path_msg(opt, rename_info->key, 1, + _("WARNING: Avoiding applying %s -> %s rename " + "to %s, because %s itself was renamed."), + rename_info->key, new_dir, path, new_dir); + return NULL; + } + + new_path = handle_path_level_conflicts(opt, path, side_index, + rename_info, collisions); + *clean_merge &= (new_path != NULL); + + return new_path; } static void apply_directory_rename_modifications(struct merge_options *opt, From patchwork Mon Jan 4 23:50:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997813 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4AB4DC43333 for ; Mon, 4 Jan 2021 23:51:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0E91B2253D for ; Mon, 4 Jan 2021 23:51:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727927AbhADXvf (ORCPT ); Mon, 4 Jan 2021 18:51:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33702 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727646AbhADXvf (ORCPT ); Mon, 4 Jan 2021 18:51:35 -0500 Received: from mail-ot1-x329.google.com (mail-ot1-x329.google.com [IPv6:2607:f8b0:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 834B0C0617A5 for ; Mon, 4 Jan 2021 15:50:43 -0800 (PST) Received: by mail-ot1-x329.google.com with SMTP id 11so27691010oty.9 for ; Mon, 04 Jan 2021 15:50:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=NhdC5dcT9zDMpbgcjdf8rubywHfnE+fEellrIf/R7UM=; b=IKX1yWnrGGoypxgrKV++tW6FhRaOxngWTbLq835sCigRKSElXWw6RdAOoxGVyUfnVa ZYxxYcoEwjbPhwrRU/FkB8q2G/sH9MtL9z77H2SKtrJUf4zHBNtqT3TZ7mmTIOw3Mugv LSLNsXobxppo4SHQ0KVgM4hJlyuYDcQx5iyY+qYOlXW1ouNPfIg/01VFEf7oMCKMqBBo Cqb1G/+mjMiQtQqfbVE+LXPf1/ElIZKvGl1J0Bw4egGhDnwBB/WROZx2lWVZxsv0DNpK TFsM9EwisYFqx/XzhAo+9PArtNjBNRTDutt/2KDO68FnerUpCkEX5SUfqTs7g2BH6OAu Nn6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NhdC5dcT9zDMpbgcjdf8rubywHfnE+fEellrIf/R7UM=; b=O0cqPOD3Amrpjy00atooI6juqAkOx+W5GNtp1gv/2VF52dqrwg08CFxr+cHbw34faT 1di2kJeTYe1k8qfI9L1URe9oMbc3zki2F+iBYbQHzNraaIPBdf8Gas4NBgHwDmSjyBYu ruSHWGpfA42zCRKnrPsjSbtp/wYOTYtodpmeyFVCiwqTz4eHcw6A0YNlpifM3DGHR2PA /Hwv2HxZIVL4h4/lWhAw2HLYFhYNCkHpiu3LmHSpgcdAZfFP2Z8msFcacbEfYR4UgO1U bYEyLysZURtm1kXrL6NpZIi8aiwdMjRMYGnP2GJv4yuXoGIErBt0Te+bAWWuh8Ztenu3 3wWg== X-Gm-Message-State: AOAM532foYlJy96Pi34b2jlazmVXvnyBdkLraqSdKX8s1qkmyWTF6ot/ UuaF+lPMjmUHXJqhSttxdFU90cnPjhs= X-Google-Smtp-Source: ABdhPJyXOumsd6BayAOsH4DKkWNdSogvKUuMPnKyQg9DfyZKW3OizW6BM7Rc0GEmM5YVIeOar/PScg== X-Received: by 2002:a9d:3a26:: with SMTP id j35mr29014114otc.64.1609804242793; Mon, 04 Jan 2021 15:50:42 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:42 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 13/17] merge-ort: implement handle_path_level_conflicts() Date: Mon, 4 Jan 2021 15:50:02 -0800 Message-Id: <20210104235006.2867404-14-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This is copied from merge-recursive.c, with minor tweaks due to: * using strmap API * merge-ort not using the non_unique_new_dir field, since it'll obviate its need entirely later with performance improvements * adding a new path_in_way() function that uses opt->priv->paths instead of doing an expensive tree_has_path() lookup to see if a tree has a given path. Signed-off-by: Elijah Newren --- merge-ort.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 71 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 84f4f4776b..d0fb8f4282 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1282,6 +1282,16 @@ static void get_renamed_dir_portion(const char *old_path, const char *new_path, *new_dir = xstrndup(new_path, end_of_new - new_path); } +static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask) +{ + struct merged_info *mi = strmap_get(paths, path); + struct conflict_info *ci; + if (!mi) + return 0; + INITIALIZE_CI(ci, mi); + return mi->clean || (side_mask & (ci->filemask | ci->dirmask)); +} + /* * See if there is a directory rename for path, and if there are any file * level conflicts on the given side for the renamed location. If there is @@ -1294,7 +1304,67 @@ static char *handle_path_level_conflicts(struct merge_options *opt, struct strmap_entry *rename_info, struct strmap *collisions) { - die("Not yet implemented"); + char *new_path = NULL; + struct collision_info *c_info; + int clean = 1; + struct strbuf collision_paths = STRBUF_INIT; + + /* + * entry has the mapping of old directory name to new directory name + * that we want to apply to path. + */ + new_path = apply_dir_rename(rename_info, path); + if (!new_path) + BUG("Failed to apply directory rename!"); + + /* + * The caller needs to have ensured that it has pre-populated + * collisions with all paths that map to new_path. Do a quick check + * to ensure that's the case. + */ + c_info = strmap_get(collisions, new_path); + if (c_info == NULL) + BUG("c_info is NULL"); + + /* + * Check for one-sided add/add/.../add conflicts, i.e. + * where implicit renames from the other side doing + * directory rename(s) can affect this side of history + * to put multiple paths into the same location. Warn + * and bail on directory renames for such paths. + */ + if (c_info->reported_already) { + clean = 0; + } else if (path_in_way(&opt->priv->paths, new_path, 1 << side_index)) { + c_info->reported_already = 1; + strbuf_add_separated_string_list(&collision_paths, ", ", + &c_info->source_files); + path_msg(opt, new_path, 0, + _("CONFLICT (implicit dir rename): Existing file/dir " + "at %s in the way of implicit directory rename(s) " + "putting the following path(s) there: %s."), + new_path, collision_paths.buf); + clean = 0; + } else if (c_info->source_files.nr > 1) { + c_info->reported_already = 1; + strbuf_add_separated_string_list(&collision_paths, ", ", + &c_info->source_files); + path_msg(opt, new_path, 0, + _("CONFLICT (implicit dir rename): Cannot map more " + "than one path to %s; implicit directory renames " + "tried to put these paths there: %s"), + new_path, collision_paths.buf); + clean = 0; + } + + /* Free memory we no longer need */ + strbuf_release(&collision_paths); + if (!clean && new_path) { + free(new_path); + return NULL; + } + + return new_path; } static void increment_count(struct strmap *dir_rename_count, From patchwork Mon Jan 4 23:50:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997799 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 61A66C433E9 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3864E2253D for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727890AbhADXvT (ORCPT ); Mon, 4 Jan 2021 18:51:19 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33524 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvR (ORCPT ); Mon, 4 Jan 2021 18:51:17 -0500 Received: from mail-ot1-x334.google.com (mail-ot1-x334.google.com [IPv6:2607:f8b0:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 78E20C0617A6 for ; Mon, 4 Jan 2021 15:50:44 -0800 (PST) Received: by mail-ot1-x334.google.com with SMTP id r9so27681280otk.11 for ; Mon, 04 Jan 2021 15:50:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=aHVe7bKOa7rO3CZHK14AowessT5lSzkarRPSP2gmUMc=; b=Ls0jDlIJKxaAkasjgTZ5sXd/j1q0ge+4OMujNH98cwfFwVcEBklQ5z/vviLpmvlyXB 3FmU88a19q68pCQDB2VrjamwSx9w/JZ7LvRGqVSlmbM3oXCswxfLHiucol/s1LDt2+l1 dFP8t0eFIHPB5br+RBzawCSy0bXXm5y97qJYpcJ/2gCfmyLmPnEpdpo7QW3TyjT9endK sZ6+uagFvrlkHFBOP96RqCdkg/enWNN6MSa5yGDDyn6ugTUpf2voklue6D1t7XKA3l+e wMqfrzDfXpnGKgMq13JcbHzByMUaMfVt6PkghUToPtIqpQPg5A3w6YVzjJOf/6UDZF65 w9LQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=aHVe7bKOa7rO3CZHK14AowessT5lSzkarRPSP2gmUMc=; b=MKIn0JVrIR7qeNRbxbjGIkb49P/F9kkWSwA3zUZMgf6olvDIs2o+8Xp+O2LuR07nd/ cIagfts99AZs92DUufDr90ovvOj3yOJKb/oLVf0rBJY3dISp2SB8gJjzQmu6sdnUq2EF YS4u1Uw+EdGnvfVpNAZYsChd4nPPTcwfFcY+HJfjMrkaJUYTnDb+rgw//yWrHVkGWFLW UOsbXT6S38FrF9iEm/8+f1ksHKDsAeD/RykF/QqeeegxWHZlni7xTLeZcgmIlhEoh6oC wblW1PDl4RlS3aPk2LXghrDI3NM/RmRTua5mgDs/Xq57lMP5d2cpGENXl0KZMOMoCGQU Bxrw== X-Gm-Message-State: AOAM531cRVNok1zrPiNn7O1n0nMtYkmzH/LoGT+xlcAM0Usoz1Qggzih Kx3c/HeN1gHCVAizSbORBzhE9ZdjPPQ= X-Google-Smtp-Source: ABdhPJyHusW8VxnQWLJuyREKhoaSF9sLuyGsPb1pjU8F8+QO5SGB19j4gFTLei2ka1eTmHyIVNOpNg== X-Received: by 2002:a05:6830:916:: with SMTP id v22mr55765770ott.257.1609804243777; Mon, 04 Jan 2021 15:50:43 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:43 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 14/17] merge-ort: add a new toplevel_dir field Date: Mon, 4 Jan 2021 15:50:03 -0800 Message-Id: <20210104235006.2867404-15-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Due to the string-equality-iff-pointer-equality requirements placed on merged_info.directory_name, apply_directory_rename_modifications() will need to have access to the exact toplevel directory name string pointer and can't just use a new empty string. Store it in a field that we can use. Signed-off-by: Elijah Newren --- merge-ort.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index d0fb8f4282..230224e680 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -171,12 +171,15 @@ struct merge_options_internal { struct rename_info renames; /* - * current_dir_name: temporary var used in collect_merge_info_callback() + * current_dir_name, toplevel_dir: temporary vars * - * Used to set merged_info.directory_name; see documentation for that - * variable and the requirements placed on that field. + * These are used in collect_merge_info_callback(), and will set the + * various merged_info.directory_name for the various paths we get; + * see documentation for that variable and the requirements placed on + * that field. */ const char *current_dir_name; + const char *toplevel_dir; /* call_depth: recursion level counter for merging merge bases */ int call_depth; @@ -734,10 +737,10 @@ static int collect_merge_info(struct merge_options *opt, int ret; struct tree_desc t[3]; struct traverse_info info; - const char *toplevel_dir_placeholder = ""; - opt->priv->current_dir_name = toplevel_dir_placeholder; - setup_traverse_info(&info, toplevel_dir_placeholder); + opt->priv->toplevel_dir = ""; + opt->priv->current_dir_name = opt->priv->toplevel_dir; + setup_traverse_info(&info, opt->priv->toplevel_dir); info.fn = collect_merge_info_callback; info.data = opt; info.show_all_errors = 1; From patchwork Mon Jan 4 23:50:04 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997807 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A446DC4332D for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 830942253D for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727911AbhADXvZ (ORCPT ); Mon, 4 Jan 2021 18:51:25 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXvZ (ORCPT ); Mon, 4 Jan 2021 18:51:25 -0500 Received: from mail-ot1-x32d.google.com (mail-ot1-x32d.google.com [IPv6:2607:f8b0:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 96881C0617A9 for ; Mon, 4 Jan 2021 15:50:45 -0800 (PST) Received: by mail-ot1-x32d.google.com with SMTP id q25so27700131otn.10 for ; Mon, 04 Jan 2021 15:50:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=zJcxNGID72K8wTTj1W0BEoPSOqxlJMImdcW59TSS8IA=; b=GV3abgngcV/mjp9MhcO7OkfX/iNTdou5x2CWRlmMksGeXyXDGXeN6L6WeCEA8adP5/ va2Vmo6BxmXgDBKWJypDOeimI8yAsFw3qn3VwqNd0v9OiLhaILa9Rp4g4+GTIrAbvyWp 80GQhXufaRr8heh6wmPsA7INAsWe9hEuaRjwgmWLo4ncWu5leLCzUAhyODQfOoOnD6i5 VvxUBO/96ENza85qhw9GN5Qve4Dj6GhP+W31xY4dupFuFho8GhnhfbqJHGD+L/9A75tN XzQ4bK2pg768q2CEJ/PmJa5fPMqu4d1xaPJLws0jhGGaUQclqCrNiEeiSsERqTHg1nTz wh9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=zJcxNGID72K8wTTj1W0BEoPSOqxlJMImdcW59TSS8IA=; b=Y+kF30aCoRj8W5NN3/kEIpK8DgZvX6CBAXP05KgmDjH02y3s9rZOAAMZU7JT/IXS85 5wNBe9U+qZfrluT2kyviD3NF/bMNLoBJJ8mRb6yqqLVTkanI+8Cm9UEFxekL5lXrZU5g byTXVn3ef52ijyc1UVny/wKSgCj+gUvTeifFR+3QlxNAnBImNO0iwbAxz6kUkuuWu9tW QQes4ZLRQ18y/ppNsgG+YQGtB3r1rojjTJXYj6prENwe4kVnx4E1IO4B7xq4WOLqfSm3 i7KtwDvDGTeLcj8mMOY1DWriIzeMfoVmABpJ4iMy28xX8ashd4xKybBp+XI0BktuBwUy hO6Q== X-Gm-Message-State: AOAM530e0rZ+fLfaE2V8XR2lwRcgJoqca23ry40ULmOpUW5V78tVG2Ag jPR1CesbzYJIgfXdh1X0EC9kP37NHac= X-Google-Smtp-Source: ABdhPJyIBx0KfFsvB0Gabe6ltvQ+l1b3lgejwn8iwKc0cklIk1d1EMhYRPF/o4QHJasEV2Z04N37+A== X-Received: by 2002:a05:6830:1ad4:: with SMTP id r20mr53262492otc.354.1609804244736; Mon, 04 Jan 2021 15:50:44 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:44 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 15/17] merge-ort: implement apply_directory_rename_modifications() Date: Mon, 4 Jan 2021 15:50:04 -0800 Message-Id: <20210104235006.2867404-16-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This function roughly follows the same outline as the function of the same name from merge-recursive.c, but the code diverges in multiple ways due to some special considerations: * merge-ort's version needs to update opt->priv->paths with any new paths (and opt->priv->paths points to struct conflict_infos which track quite a bit of metadata for each path); merge-recursive's version would directly update the index * merge-ort requires that opt->priv->paths has any leading directories of any relevant files also be included in the set of paths. And due to pointer equality requirements on merged_info.directory_name, we have to be careful how we compute and insert these. * due to the above requirements on opt->priv->paths, merge-ort's version starts with a long comment to explain all the special considerations that need to be handled * merge-ort can use the full data stored in opt->priv->paths to avoid making expensive get_tree_entry() calls to regather the necessary data. * due to messages being deferred automatically in merge-ort, this is the best place to handle conflict messages whereas in merge-recursive.c they are deferred manually so that processing of entries does all the printing Signed-off-by: Elijah Newren --- merge-ort.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 167 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 230224e680..115ff6d2d5 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1642,7 +1642,173 @@ static void apply_directory_rename_modifications(struct merge_options *opt, struct diff_filepair *pair, char *new_path) { - die("Not yet implemented."); + /* + * The basic idea is to get the conflict_info from opt->priv->paths + * at old path, and insert it into new_path; basically just this: + * ci = strmap_get(&opt->priv->paths, old_path); + * strmap_remove(&opt->priv->paths, old_path, 0); + * strmap_put(&opt->priv->paths, new_path, ci); + * However, there are some factors complicating this: + * - opt->priv->paths may already have an entry at new_path + * - Each ci tracks its containing directory, so we need to + * update that + * - If another ci has the same containing directory, then + * the two char*'s MUST point to the same location. See the + * comment in struct merged_info. strcmp equality is not + * enough; we need pointer equality. + * - opt->priv->paths must hold the parent directories of any + * entries that are added. So, if this directory rename + * causes entirely new directories, we must recursively add + * parent directories. + * - For each parent directory added to opt->priv->paths, we + * also need to get its parent directory stored in its + * conflict_info->merged.directory_name with all the same + * requirements about pointer equality. + */ + struct string_list dirs_to_insert = STRING_LIST_INIT_NODUP; + struct conflict_info *ci, *new_ci; + struct strmap_entry *entry; + const char *branch_with_new_path, *branch_with_dir_rename; + const char *old_path = pair->two->path; + const char *parent_name; + const char *cur_path; + int i, len; + + entry = strmap_get_entry(&opt->priv->paths, old_path); + old_path = entry->key; + ci = entry->value; + VERIFY_CI(ci); + + /* Find parent directories missing from opt->priv->paths */ + cur_path = new_path; + while (1) { + /* Find the parent directory of cur_path */ + char *last_slash = strrchr(cur_path, '/'); + if (last_slash) { + parent_name = xstrndup(cur_path, last_slash - cur_path); + } else { + parent_name = opt->priv->toplevel_dir; + break; + } + + /* Look it up in opt->priv->paths */ + entry = strmap_get_entry(&opt->priv->paths, parent_name); + if (entry) { + free((char*)parent_name); + parent_name = entry->key; /* reuse known pointer */ + break; + } + + /* Record this is one of the directories we need to insert */ + string_list_append(&dirs_to_insert, parent_name); + cur_path = parent_name; + } + + /* Traverse dirs_to_insert and insert them into opt->priv->paths */ + for (i = dirs_to_insert.nr-1; i >= 0; --i) { + struct conflict_info *dir_ci; + char *cur_dir = dirs_to_insert.items[i].string; + + dir_ci = xcalloc(1, sizeof(*dir_ci)); + + dir_ci->merged.directory_name = parent_name; + len = strlen(parent_name); + /* len+1 because of trailing '/' character */ + dir_ci->merged.basename_offset = (len > 0 ? len+1 : len); + dir_ci->dirmask = ci->filemask; + strmap_put(&opt->priv->paths, cur_dir, dir_ci); + + parent_name = cur_dir; + } + + /* + * We are removing old_path from opt->priv->paths. old_path also will + * eventually need to be freed, but it may still be used by e.g. + * ci->pathnames. So, store it in another string-list for now. + */ + string_list_append(&opt->priv->paths_to_free, old_path); + + assert(ci->filemask == 2 || ci->filemask == 4); + assert(ci->dirmask == 0); + strmap_remove(&opt->priv->paths, old_path, 0); + + branch_with_new_path = (ci->filemask == 2) ? opt->branch1 : opt->branch2; + branch_with_dir_rename = (ci->filemask == 2) ? opt->branch2 : opt->branch1; + + /* Now, finally update ci and stick it into opt->priv->paths */ + ci->merged.directory_name = parent_name; + len = strlen(parent_name); + ci->merged.basename_offset = (len > 0 ? len+1 : len); + new_ci = strmap_get(&opt->priv->paths, new_path); + if (!new_ci) { + /* Place ci back into opt->priv->paths, but at new_path */ + strmap_put(&opt->priv->paths, new_path, ci); + } else { + int index; + + /* A few sanity checks */ + VERIFY_CI(new_ci); + assert(ci->filemask == 2 || ci->filemask == 4); + assert((new_ci->filemask & ci->filemask) == 0); + assert(!new_ci->merged.clean); + + /* Copy stuff from ci into new_ci */ + new_ci->filemask |= ci->filemask; + if (new_ci->dirmask) + new_ci->df_conflict = 1; + index = (ci->filemask >> 1); + new_ci->pathnames[index] = ci->pathnames[index]; + new_ci->stages[index].mode = ci->stages[index].mode; + oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid); + + free(ci); + ci = new_ci; + } + + if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE) { + /* Notify user of updated path */ + if (pair->status == 'A') + path_msg(opt, new_path, 1, + _("Path updated: %s added in %s inside a " + "directory that was renamed in %s; moving " + "it to %s."), + old_path, branch_with_new_path, + branch_with_dir_rename, new_path); + else + path_msg(opt, new_path, 1, + _("Path updated: %s renamed to %s in %s, " + "inside a directory that was renamed in %s; " + "moving it to %s."), + pair->one->path, old_path, branch_with_new_path, + branch_with_dir_rename, new_path); + } else { + /* + * opt->detect_directory_renames has the value + * MERGE_DIRECTORY_RENAMES_CONFLICT, so mark these as conflicts. + */ + ci->path_conflict = 1; + if (pair->status == 'A') + path_msg(opt, new_path, 0, + _("CONFLICT (file location): %s added in %s " + "inside a directory that was renamed in %s, " + "suggesting it should perhaps be moved to " + "%s."), + old_path, branch_with_new_path, + branch_with_dir_rename, new_path); + else + path_msg(opt, new_path, 0, + _("CONFLICT (file location): %s renamed to %s " + "in %s, inside a directory that was renamed " + "in %s, suggesting it should perhaps be " + "moved to %s."), + pair->one->path, old_path, branch_with_new_path, + branch_with_dir_rename, new_path); + } + + /* + * Finally, record the new location. + */ + pair->two->path = new_path; } /*** Function Grouping: functions related to regular rename detection ***/ From patchwork Mon Jan 4 23:50:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997815 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 31AB3C433E0 for ; Mon, 4 Jan 2021 23:51:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F31222253D for ; Mon, 4 Jan 2021 23:51:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727772AbhADXvu (ORCPT ); Mon, 4 Jan 2021 18:51:50 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33748 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727570AbhADXvu (ORCPT ); Mon, 4 Jan 2021 18:51:50 -0500 Received: from mail-ot1-x32e.google.com (mail-ot1-x32e.google.com [IPv6:2607:f8b0:4864:20::32e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CEFB9C0617AA for ; Mon, 4 Jan 2021 15:50:46 -0800 (PST) Received: by mail-ot1-x32e.google.com with SMTP id 11so27691107oty.9 for ; Mon, 04 Jan 2021 15:50:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=SslbAurq9E10mVdLdx4PqWNtIyOJeDsTI2O8op1OF+4=; b=FbnpNugogDpPWXUs9zbx9FqTOldWRbI2AQjVpnUTnwaquZkON+SCDIFUxSx0y3rKuo 5afMPP+sR4abI+OJa6XO7DGwvcf9kXOPj/QZEyNw9W1kgikFNOD2YNqVQ22qCRrjCgnD vBOd943/1p0js4ragnXuZ9yGEusFBM76T+1JDzm3rZM+NJiaZGNQppCTWSMo5dQ0NIkg MJwwFJtID/GDHptbvtfG5ww/UHuiAsCzaNPVNMGzL0cwhhsaEucmjpoO8cbQ3yG1ntTb dq84D511We0ZfxYPynQ3ZFGIno2G2CUSXHh5X6TrylnaFJ1Kl5MyCHvnx4NqqyiBa4UR VOyQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=SslbAurq9E10mVdLdx4PqWNtIyOJeDsTI2O8op1OF+4=; b=q5xk+AM0TLhcR0CmFdZpT4pcZiXWgXQH3YJbYroLT6HMfxUsr0uqJJFI+h1B6q9f4O tt3MoNjgFlwoSYjn4i4bM7A+hkfdI9l3Fhh4O4WPkWUQBOqDBhpY82n7t55fXYHQF9P7 QvRcDsy2lOM0AyTiwZKXaFHpTw6W+Ki6cGsJr0NjHjsFQOehB8XpPQTr8Uxgg4BvMXtw Q61UNqbKggpTyJ9p/6VANypVrniW9dIUpFV4pUcEHkmj76hoslpyxoKAZ0hOmaaSMQdv Pe8vVh8Atrv3jzQZm9COnis+e+hy9gecn1VqErky1C5w5BkTGT/cD8rMzqM3RhtSOfh5 IbNA== X-Gm-Message-State: AOAM530/kiHo7epD5sGE20fVdeEoQEhf6dUO55E/vinMchdJ4xrEPdxp RF5+RU+mL7FTu7z7DEzIbxpho2e/bUI= X-Google-Smtp-Source: ABdhPJyknDr4hXu4G05M8C6rPVwGbg0vZVfgC77f9jlWAVG/SrAwQWudmgrjgN35/hpRoxZ9PbG2sw== X-Received: by 2002:a9d:7f15:: with SMTP id j21mr54937585otq.76.1609804245962; Mon, 04 Jan 2021 15:50:45 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:45 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 16/17] merge-ort: process_renames() now needs more defensiveness Date: Mon, 4 Jan 2021 15:50:05 -0800 Message-Id: <20210104235006.2867404-17-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Since directory rename detection adds new paths to opt->priv->paths and removes old ones, process_renames() needs to now check whether pair->one->path actually exists in opt->priv->paths instead of just assuming it does. Signed-off-by: Elijah Newren --- merge-ort.c | 26 +++++++++++++++++++++----- 1 file changed, 21 insertions(+), 5 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 115ff6d2d5..480f212cff 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1829,12 +1829,28 @@ static int process_renames(struct merge_options *opt, const char *rename_branch = NULL, *delete_branch = NULL; old_ent = strmap_get_entry(&opt->priv->paths, pair->one->path); - oldpath = old_ent->key; - oldinfo = old_ent->value; - new_ent = strmap_get_entry(&opt->priv->paths, pair->two->path); - newpath = new_ent->key; - newinfo = new_ent->value; + if (old_ent) { + oldpath = old_ent->key; + oldinfo = old_ent->value; + } + newpath = pair->two->path; + if (new_ent) { + newpath = new_ent->key; + newinfo = new_ent->value; + } + + /* + * If pair->one->path isn't in opt->priv->paths, that means + * that either directory rename detection removed that + * path, or a parent directory of oldpath was resolved and + * we don't even need the rename; in either case, we can + * skip it. If oldinfo->merged.clean, then the other side + * of history had no changes to oldpath and we don't need + * the rename and can skip it. + */ + if (!oldinfo || oldinfo->merged.clean) + continue; /* * diff_filepairs have copies of pathnames, thus we have to From patchwork Mon Jan 4 23:50:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11997809 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id BD340C43331 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9A1DD22519 for ; Mon, 4 Jan 2021 23:51:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727915AbhADXv1 (ORCPT ); Mon, 4 Jan 2021 18:51:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33628 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727826AbhADXv0 (ORCPT ); Mon, 4 Jan 2021 18:51:26 -0500 Received: from mail-ot1-x32d.google.com (mail-ot1-x32d.google.com [IPv6:2607:f8b0:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E9BEAC061794 for ; Mon, 4 Jan 2021 15:50:47 -0800 (PST) Received: by mail-ot1-x32d.google.com with SMTP id x13so27700267oto.8 for ; Mon, 04 Jan 2021 15:50:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=sxcelU7KFx1SjLKVAvfCWMiY5H/moK3W+j2QgFzzW1A=; b=bqBiMWpdYf0O/7sFAwNBsDp2hhueZkX3Lx7K1P/OGFmgR2JdeVZua/BbL14Nguh9th s0OOy6RsbZzAUbaQgF8MdAYYJXxPD8JEn0eAw/P/uhXVv80NYXTpMo4aoXfkG31mb12F ZDrsYNFCAM9PRpjjTnl4zS673vLaCB3LYFssljAmG7H1xc20HJPGm9T7F4iSpIYxGI1O LdubLlwz6TST8U5zFYMvs5OTXRPZS7ouXdoOpoVnhSCZUWHNRm9UVVLrcExUR5q5ZbLn 7bBn49wIoliO5wrhwSNCXwsci0ye5CWPY6qAyTVk4+6EeGq+0zfPEjeRUbDPWPFevnh1 Quqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=sxcelU7KFx1SjLKVAvfCWMiY5H/moK3W+j2QgFzzW1A=; b=bq7l5VFcVWhow6F81HOf7ESPWuhCyYD7OKuUhTRwv0Gpht4Cg4Dv2BWabHdcLV/ddZ 8FTb/KrkBx6n9aIWLVVonod7R8TaPqOPIC4ALj/hOsE1KIZezGfyqRDtMgYZPEyeB3Ix +I+Ir6YRcxTq4onM7RI246tpibU+S9HrXqKbRS1z9STb0Cqx+0HR6rMPD9B3xMYb0qli rcyAVO+CJMEaMC8YL+oUsqOVrIxvi8IrHhQlw/34D3ogW62L2d7DTiCCbe1CysTxVguC 8PAO+xrhZ/V9f7hEDCpxUQZRA0eof3p0+tJd/sxEpLbp388ilti1/sFch2Dgcb6iIDva F5VA== X-Gm-Message-State: AOAM530+vYfX+gBac+nTI0ic/8oIpVy+1hNdMFtXCnL1cKsnVeGArwQS PNLLfOymB09XpKsUbUteytYVk+toPt8= X-Google-Smtp-Source: ABdhPJyP6oIPVEkmWq/jNeGgNozLBrW8j4NqVDhYFv3APVCki+SgSDg9teeRLrgNF8JwhUN59rJMsA== X-Received: by 2002:a9d:744a:: with SMTP id p10mr54487116otk.203.1609804247048; Mon, 04 Jan 2021 15:50:47 -0800 (PST) Received: from tiger.attlocal.net ([2600:1700:bae0:2de0::26]) by smtp.gmail.com with ESMTPSA id o135sm13359600ooo.38.2021.01.04.15.50.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Jan 2021 15:50:46 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: gitster@pobox.com, Elijah Newren Subject: [PATCH 17/17] merge-ort: fix a directory rename detection bug Date: Mon, 4 Jan 2021 15:50:06 -0800 Message-Id: <20210104235006.2867404-18-newren@gmail.com> X-Mailer: git-send-email 2.29.1.106.g3ff750dc32.dirty In-Reply-To: <20210104235006.2867404-1-newren@gmail.com> References: <20210104235006.2867404-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org As noted in commit 902c521a35 ("t6423: more involved directory rename test", 2020-10-15), when we have a case where * dir/subdir/ has several files * almost all files in dir/subdir/ are renamed to folder/subdir/ * one of the files in dir/subdir/ is renamed to folder/subdir/newsubdir/ * the other side of history (that doesn't do the renames) adds a new file to dir/subdir/ Then for the majority of the file renames, the directory rename of dir/subdir/ -> folder/subdir/ is actually not represented that way but as dir/ -> folder/ We also had one rename that was represented as dir/subdir/ -> folder/subdir/newsubdir/ Now, since there's a new file in dir/subdir/, where does it go? Well, there's only one rule for dir/subdir/, so the code previously noted that this rule had the "majority" of the one "relevant" rename and thus erroneously used it to place the file in folder/subdir/newsubdir/. We really want the heavy weight associated with dir/ -> folder/ to also be treated as dir/subdir/ -> folder/subdir/, so that we correctly place the file in folder/subdir/. Add a bunch of logic to make sure that we use all relevant renamings in directory rename detection. Note that testcase 12f of t6423 still fails after this, but it gets further than merge-recursive does. There are some performance related bits in that testcase (the region_enter messages) that do not yet succeed, but the rest of the testcase works after this patch. Subsequent patch series will fix up the performance side. Signed-off-by: Elijah Newren --- merge-ort.c | 198 +++++++++++++++++++++------------------------------- 1 file changed, 81 insertions(+), 117 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 480f212cff..8f4ca4fe83 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1182,109 +1182,6 @@ static char *apply_dir_rename(struct strmap_entry *rename_info, return strbuf_detach(&new_path, NULL); } -static void get_renamed_dir_portion(const char *old_path, const char *new_path, - char **old_dir, char **new_dir) -{ - char *end_of_old, *end_of_new; - - /* Default return values: NULL, meaning no rename */ - *old_dir = NULL; - *new_dir = NULL; - - /* - * For - * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c" - * the "e/foo.c" part is the same, we just want to know that - * "a/b/c/d" was renamed to "a/b/some/thing/else" - * so, for this example, this function returns "a/b/c/d" in - * *old_dir and "a/b/some/thing/else" in *new_dir. - */ - - /* - * If the basename of the file changed, we don't care. We want - * to know which portion of the directory, if any, changed. - */ - end_of_old = strrchr(old_path, '/'); - end_of_new = strrchr(new_path, '/'); - - /* - * If end_of_old is NULL, old_path wasn't in a directory, so there - * could not be a directory rename (our rule elsewhere that a - * directory which still exists is not considered to have been - * renamed means the root directory can never be renamed -- because - * the root directory always exists). - */ - if (end_of_old == NULL) - return; /* Note: *old_dir and *new_dir are still NULL */ - - /* - * If new_path contains no directory (end_of_new is NULL), then we - * have a rename of old_path's directory to the root directory. - */ - if (end_of_new == NULL) { - *old_dir = xstrndup(old_path, end_of_old - old_path); - *new_dir = xstrdup(""); - return; - } - - /* Find the first non-matching character traversing backwards */ - while (*--end_of_new == *--end_of_old && - end_of_old != old_path && - end_of_new != new_path) - ; /* Do nothing; all in the while loop */ - - /* - * If both got back to the beginning of their strings, then the - * directory didn't change at all, only the basename did. - */ - if (end_of_old == old_path && end_of_new == new_path && - *end_of_old == *end_of_new) - return; /* Note: *old_dir and *new_dir are still NULL */ - - /* - * If end_of_new got back to the beginning of its string, and - * end_of_old got back to the beginning of some subdirectory, then - * we have a rename/merge of a subdirectory into the root, which - * needs slightly special handling. - * - * Note: There is no need to consider the opposite case, with a - * rename/merge of the root directory into some subdirectory - * because as noted above the root directory always exists so it - * cannot be considered to be renamed. - */ - if (end_of_new == new_path && - end_of_old != old_path && end_of_old[-1] == '/') { - *old_dir = xstrndup(old_path, --end_of_old - old_path); - *new_dir = xstrdup(""); - return; - } - - /* - * We've found the first non-matching character in the directory - * paths. That means the current characters we were looking at - * were part of the first non-matching subdir name going back from - * the end of the strings. Get the whole name by advancing both - * end_of_old and end_of_new to the NEXT '/' character. That will - * represent the entire directory rename. - * - * The reason for the increment is cases like - * a/b/star/foo/whatever.c -> a/b/tar/foo/random.c - * After dropping the basename and going back to the first - * non-matching character, we're now comparing: - * a/b/s and a/b/ - * and we want to be comparing: - * a/b/star/ and a/b/tar/ - * but without the pre-increment, the one on the right would stay - * a/b/. - */ - end_of_old = strchr(++end_of_old, '/'); - end_of_new = strchr(++end_of_new, '/'); - - /* Copy the old and new directories into *old_dir and *new_dir. */ - *old_dir = xstrndup(old_path, end_of_old - old_path); - *new_dir = xstrndup(new_path, end_of_new - new_path); -} - static int path_in_way(struct strmap *paths, const char *path, unsigned side_mask) { struct merged_info *mi = strmap_get(paths, path); @@ -1370,6 +1267,14 @@ static char *handle_path_level_conflicts(struct merge_options *opt, return new_path; } +static void dirname_munge(char *filename) +{ + char *slash = strrchr(filename, '/'); + if (!slash) + slash = filename; + *slash = '\0'; +} + static void increment_count(struct strmap *dir_rename_count, char *old_dir, char *new_dir) @@ -1391,6 +1296,76 @@ static void increment_count(struct strmap *dir_rename_count, strintmap_incr(counts, new_dir, 1); } +static void update_dir_rename_counts(struct strmap *dir_rename_count, + struct strset *dirs_removed, + const char *oldname, + const char *newname) +{ + char *old_dir = xstrdup(oldname); + char *new_dir = xstrdup(newname); + char new_dir_first_char = new_dir[0]; + int first_time_in_loop = 1; + + while (1) { + dirname_munge(old_dir); + dirname_munge(new_dir); + + /* + * When renaming + * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c" + * then this suggests that both + * a/b/c/d/e/ => a/b/some/thing/else/e/ + * a/b/c/d/ => a/b/some/thing/else/ + * so we want to increment counters for both. We do NOT, + * however, also want to suggest that there was the following + * rename: + * a/b/c/ => a/b/some/thing/ + * so we need to quit at that point. + * + * Note the when first_time_in_loop, we only strip off the + * basename, and we don't care if that's different. + */ + if (!first_time_in_loop) { + char *old_sub_dir = strchr(old_dir, '\0')+1; + char *new_sub_dir = strchr(new_dir, '\0')+1; + if (!*new_dir) { + /* + * Special case when renaming to root directory, + * i.e. when new_dir == "". In this case, we had + * something like + * a/b/subdir => subdir + * and so dirname_munge() sets things up so that + * old_dir = "a/b\0subdir\0" + * new_dir = "\0ubdir\0" + * We didn't have a '/' to overwrite a '\0' onto + * in new_dir, so we have to compare differently. + */ + if (new_dir_first_char != old_sub_dir[0] || + strcmp(old_sub_dir+1, new_sub_dir)) + break; + } else { + if (strcmp(old_sub_dir, new_sub_dir)) + break; + } + } + + if (strset_contains(dirs_removed, old_dir)) + increment_count(dir_rename_count, old_dir, new_dir); + else + break; + + /* If we hit toplevel directory ("") for old or new dir, quit */ + if (!*old_dir || !*new_dir) + break; + + first_time_in_loop = 0; + } + + /* Free resources we don't need anymore */ + free(old_dir); + free(new_dir); +} + static void compute_rename_counts(struct diff_queue_struct *pairs, struct strmap *dir_rename_count, struct strset *dirs_removed) @@ -1398,19 +1373,11 @@ static void compute_rename_counts(struct diff_queue_struct *pairs, int i; for (i = 0; i < pairs->nr; ++i) { - char *old_dir, *new_dir; struct diff_filepair *pair = pairs->queue[i]; if (pair->status != 'R') continue; - /* Get the old and new directory names */ - get_renamed_dir_portion(pair->one->path, pair->two->path, - &old_dir, &new_dir); - if (!old_dir) - /* Directory didn't change at all; ignore this one. */ - continue; - /* * Make dir_rename_count contain a map of a map: * old_directory -> {new_directory -> count} @@ -1418,12 +1385,9 @@ static void compute_rename_counts(struct diff_queue_struct *pairs, * the old filename and the new filename and count how many * times that pairing occurs. */ - if (strset_contains(dirs_removed, old_dir)) - increment_count(dir_rename_count, old_dir, new_dir); - - /* Free resources we don't need anymore */ - free(old_dir); - free(new_dir); + update_dir_rename_counts(dir_rename_count, dirs_removed, + pair->one->path, + pair->two->path); } }