From patchwork Thu Jan 7 21:35:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004921 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=-12.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 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 8B83AC433E0 for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5461D235FC for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727366AbhAGVg6 (ORCPT ); Thu, 7 Jan 2021 16:36:58 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38608 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726646AbhAGVg5 (ORCPT ); Thu, 7 Jan 2021 16:36:57 -0500 Received: from mail-wr1-x435.google.com (mail-wr1-x435.google.com [IPv6:2a00:1450:4864:20::435]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0DF10C0612FA for ; Thu, 7 Jan 2021 13:36:12 -0800 (PST) Received: by mail-wr1-x435.google.com with SMTP id d13so6976034wrc.13 for ; Thu, 07 Jan 2021 13:36:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=hDyryaov45i5VpCMwMfYmGC3XG+kMJuhszeqQ9Ks0RE=; b=aIBdKHpBAAyndq0dpz7RYzitk4B2NgdV1EAFdCvof1SuaZRKE0Yzwt2UpPMuVQKjJp j+iACPc2KtQaLwhWoR8tmWNnExCep+7xjEW9rj5/sTHHFbpfX8l9xGcsJPxF7ry6Yvha U982qQPyFDIaw5H+XY/LG1TVcXFUS6WZdwkrVFfsRzMBBXYjfjmK+OhWJ118owhYM7LU Uo2YrOCDG71fKtU8KXYEz3p+n0ejrG1zkAcNKkBfF187/gtQMGinGJA28GkGZwTw5JgC TRP5JwnA0eTXiUou0ewbsZDOov/0gPTXy6lvueseLhzqouwks8p48zX+4VJ8ETAMhB/g QUQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=hDyryaov45i5VpCMwMfYmGC3XG+kMJuhszeqQ9Ks0RE=; b=eOdEkAK2a2rChtFC4EGmJ3k1kp97+ZutF9Pg3TMrOwRwwzsBrbBbGsjbEFRM6XEfC3 1ZcAIBI4DFljZT8F3mlKPjyqx+MErnXHetefy+deNTrdpdOU38lXVxLrZ1TYkzeIvXQk HA00zZUhhBtM+zj4LrwddHPRCLSrM7CbEDAO1ScDDjPBPmhcnfIr60Gis6Vz/0tMjTVj TGGY/aS4IFK1N2llqozqbNHQOHgJONvP8w/Q9XOCBYNwsSGe7t2/bEzZVq48Gnwyy6Yq MAC3e4mnP3218MS6QhnTqnvAYbPTQT0bNmxzrkKebQzL2Ozbg7cAuTX+8udlMef39P3g VkrA== X-Gm-Message-State: AOAM530jaiFhU/W8L1i8tzcqHVmcWRmrnqLEFRVsqxmhh0u7ipobYPC4 7u3bc2+ta8oxlhPy/HuVBSPGXBac7dI= X-Google-Smtp-Source: ABdhPJxo/vSQvJAFJ0INA53wCBb82uoM6IPAqlKUBC+Dy0xB7InEVj6uKTqGlrfmiWBnT7ZnQfrXzw== X-Received: by 2002:adf:aa83:: with SMTP id h3mr576071wrc.108.1610055369682; Thu, 07 Jan 2021 13:36:09 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z3sm10996766wrn.59.2021.01.07.13.36.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:07 -0800 (PST) Message-Id: <41a99640cc55d71659116dd66db6048cfb436e34.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:49 +0000 Subject: [PATCH v2 01/17] merge-ort: add new data structures for directory rename detection Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 d36a92b59b7..652ff730afa 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -49,14 +49,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 Thu Jan 7 21:35: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: 12004919 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=-12.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 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 96975C433E9 for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 71BCA23718 for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726541AbhAGVg5 (ORCPT ); Thu, 7 Jan 2021 16:36:57 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38610 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726666AbhAGVg5 (ORCPT ); Thu, 7 Jan 2021 16:36:57 -0500 Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 19C59C0612FB for ; Thu, 7 Jan 2021 13:36:12 -0800 (PST) Received: by mail-wr1-x433.google.com with SMTP id i9so7048221wrc.4 for ; Thu, 07 Jan 2021 13:36:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=MX2aW2g13Yn3qC4kR0lcJp3Y9xbONhy3MIMIOrlLn+A=; b=sG1XMtZKQJVjpSoi2EL8vR5XbNq4v/X146lQDziOFja3c3ngDSP6LoF9lB6hSkRD8E DbdTWdl3HjF9Cq6ZciCro4J4KlPGB/u9fIEK1/GrCpUo04utzEb67vkEJ56GpvISFiJb Lzg60p+YNxAxd99NDizrl1wO42Jw7bMu5RpCGz3LPjlBqxCmM+HAOCh37zij7jCXS8lT b2MPWS3Cyroh0bi4LJXqH+o17qozHWzxvHIDPIbLXoV57Xxv6tqdQ4FE1xOyfUBwkoJZ 9wirGVBxsBqC0dTiOP/Hz9FbvOcefK/J2D6oVGLSTDQsClWI3LyFgi0mdtcvWLJSTq0t HdOw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=MX2aW2g13Yn3qC4kR0lcJp3Y9xbONhy3MIMIOrlLn+A=; b=cjI/zzsMoB86NGRzEpNQ+0iyXIBHb2oFgiBMiTcBhz23KNDQoSxSbUkovK/DHLgOKK Bf/iK9E/GONNC3OC4i2YDO1N+eGOuAlqh5qYhIQ76FGDCAu9wUpjTxFLblJUI7eFpcc8 mm1TB5WMt7VLPH1axHdxlotqOSFZXqK2LHgSLXMYePLVUWyIYeo2/3baYiiyJOwl0qFb jyw0UZI+Y24WgWY4UlS9MqfwhOTfXXWpum4b26fTjU/L5mmM4Bnp0b8ZMtSKMnYrZg0v rh2oMBbta2a6H6eeOVX02j0Foh7xCf1mOrJNmGt/qBvGp8SX89BrnT7Hfyhr/UAoetrO tGeQ== X-Gm-Message-State: AOAM530tUAAALAWcSbe9mNoN6mbJKLCm7yVU/CXvQhIUwIe70IWsFPdx e6rnpbEtcrws96/kJ6ORSo7wl2Dadl4= X-Google-Smtp-Source: ABdhPJzc8dsGbR0tXUSlJMd5VP1bpL2ntX3elwdL9xZwiqMxU3FcBHzpDkyGMHBCaUmHnhamo20WrQ== X-Received: by 2002:adf:fc48:: with SMTP id e8mr528310wrs.11.1610055370656; Thu, 07 Jan 2021 13:36:10 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id x7sm8905150wmi.11.2021.01.07.13.36.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:10 -0800 (PST) Message-Id: <762151802be53fbe0269bad721bb93ed84fd8f8b.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:50 +0000 Subject: [PATCH v2 02/17] merge-ort: initialize and free new directory rename data structures Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 652ff730afa..2e6d41b0a0f 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -308,8 +308,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 @@ -339,6 +343,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; @@ -1812,6 +1833,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); @@ -1846,6 +1870,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 Thu Jan 7 21:35: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: 12004931 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=-12.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 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 C6834C433E9 for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9BF45235FD for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727693AbhAGVha (ORCPT ); Thu, 7 Jan 2021 16:37:30 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38700 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727610AbhAGVha (ORCPT ); Thu, 7 Jan 2021 16:37:30 -0500 Received: from mail-wr1-x434.google.com (mail-wr1-x434.google.com [IPv6:2a00:1450:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E0A00C0612FC for ; Thu, 7 Jan 2021 13:36:12 -0800 (PST) Received: by mail-wr1-x434.google.com with SMTP id y17so7002918wrr.10 for ; Thu, 07 Jan 2021 13:36:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=jZK3pNu61wrQ/V04IYnePto8PDBrZpemvXpBnPivOPU=; b=rEJeKFYlQfVUsce4C7u9hvswJoIGDonw3EV5y+VqncEpNLiSvkszzJG3JpFsIQDu5k zNhcjLgmcHux0h/WikFpylwS3PwK6qIfEuRgeQHsyDFz8kB+0lKnn3jeY2TmOQ/GBie8 7RX1kyMvT0cRHtoDPcWz24ADc/FBaagfuc/Xnm6DWPPrBrv40j3qVLnSiRX/Qn41H+RL 6ZDX+SzoPoY+VNezZYMIcIZGhkylTEM5fjr45OetYIJZ4Xx9fwRTpSNJ68CGFY2P/CMs 4NJz4miWlRN8nn3Uwd7RbHjwnQFPjiOkcI0MSvcHllp+u9y02Mjr4hwop8cFeG62iX+k qIMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=jZK3pNu61wrQ/V04IYnePto8PDBrZpemvXpBnPivOPU=; b=DDJwMVCE1PKRRdipyWTTS9cW5A+NWbbdLA5tVSlDQ7SqHZ2zViepCobC/0Wq0MTBxw 8JCFYW5gy4ZRdTVs6foCfZ684cnpV5laY2+hzRaqExz7S8izSBACfAqVCYNhLR+qzlGb aPCYpwg452Z3UiEVX9Fn4SYk9absypguRLOzgiEFXKRHg/LSFnVxhuNgqZr++R6AR+8L paPeP+MsYIVPYDWv4cEt1huNw1Wo0B0GsUawFxSCzTkWIqyUqWL0ZJ/21t9JvBnxZMaS F6lxDtrXxvfI/ZtfvYsqI5dIxaDRu9Nx72uIpMJaCQcZcTuZmxGdTcHplveZJuqrala8 RWew== X-Gm-Message-State: AOAM5325TYtFvW0pU6/zpVkwzV2joQd8122Ze1SrZ6sGKbnlI/lEAuZN m9fZZpElOMlHqjnwyaGwG+3U2p4RRto= X-Google-Smtp-Source: ABdhPJxuBFk5tOHugZiitXES5YGdXuYKhnakOqdW6V2VpVtteoQPdoOeDP9Zr0h6a80uvpMGY63twA== X-Received: by 2002:a5d:68ce:: with SMTP id p14mr539630wrw.386.1610055371487; Thu, 07 Jan 2021 13:36:11 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h14sm10275085wrx.37.2021.01.07.13.36.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:11 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:51 +0000 Subject: [PATCH v2 03/17] merge-ort: collect which directories are removed in dirs_removed Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 2e6d41b0a0f..999a7c91c52 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -480,6 +480,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, @@ -580,6 +601,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 Thu Jan 7 21:35: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: 12004935 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=-12.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 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 DDB1AC43381 for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B3AD7235FF for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727674AbhAGVha (ORCPT ); Thu, 7 Jan 2021 16:37:30 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38702 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727652AbhAGVha (ORCPT ); Thu, 7 Jan 2021 16:37:30 -0500 Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D37B7C0612FD for ; Thu, 7 Jan 2021 13:36:13 -0800 (PST) Received: by mail-wr1-x42c.google.com with SMTP id w5so6994045wrm.11 for ; Thu, 07 Jan 2021 13:36:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=9Per0sGB/F/TcHB64BoKVIyLbqwPA6indn6vys9rSI0=; b=OEJJaGBK82tXe2TKfDIcTiZ7ZoBQDlA/3fyFD36TPwM8C1fkKcsZMOE4vQE5KXbZOl /aZbFmtFqFVjkuS/Kp+RPvus63bD6+UyWy4gqqA1Q8agC3DuYAdT426fKmmxQW95GkgG v7ZdBraFXyLfYa3gsxjWQZGtKRojrIoGB72dCv4OlIOhE31LfUwV7Z4QAX1zcWz6zzUi 4+snPYk8rFpUtKz7OHg8I8vnxTf3HRLUUPquyp7WfcuCmhlb1d/YAb+eRQsf42fkOH3q y79x0w66N/UflCAoUnJC/s4gDLtPb7hxpaSTzGgzh0fMuvDu0dekhs7AB6uM7b24aycN z4BQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=9Per0sGB/F/TcHB64BoKVIyLbqwPA6indn6vys9rSI0=; b=jbuTGFzpWD1FueNY4gWsr3Op2LzkmEIg3hfocqDuRKsILS1DDyVN8StfZ2mb+Ct3Zq SUm+iSut7l5nBiJhxGibOgm3t2s9loaHEqa7psLEm8g6AmbSzOG7SSRdVWlRQpuW75xk LOkjTbfHWb3Zv6Q/hgXdyAEYX3oqs2zhNmPJbRCOy/dO50/4GptrVYCncFXNuk4XndUK HbQDMZ3mfoUyDhecCFJ7YTCTFKA59ED5gFYmbwreRD8nIsNnWsEQsGOze80wlGWlVLkt C78Q+n4LtgQY0S62hLigx2WEORdlj7wYLiLbDSJDWYcVYeYDwnLHvM73MS2w0kj8QMEw WPYQ== X-Gm-Message-State: AOAM530dRCrT6LYM/wgdDH2C14pThutOgF2eNngI4beoghsjJckhFyzP +y0bvFdoLXjspKeqlRHEefbdlXn/qtA= X-Google-Smtp-Source: ABdhPJx9/CljpuVWd2/W7Jq3ZuF18HKOHj2Iq5wHgWpYw2LTFlkBo3l1jyrN/FB26ZQ5GB8TcODDjA== X-Received: by 2002:adf:f3c8:: with SMTP id g8mr507304wrp.405.1610055372423; Thu, 07 Jan 2021 13:36:12 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id y13sm11058164wrl.63.2021.01.07.13.36.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:11 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:52 +0000 Subject: [PATCH v2 04/17] merge-ort: add outline for computing directory renames Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 999a7c91c52..378ac495d09 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,6 +721,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, @@ -1086,13 +1098,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 Thu Jan 7 21:35: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: 12004923 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=-12.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 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 D0E0AC4332B for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A17DB23718 for ; Thu, 7 Jan 2021 21:37:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727558AbhAGVhN (ORCPT ); Thu, 7 Jan 2021 16:37:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38610 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727189AbhAGVhM (ORCPT ); Thu, 7 Jan 2021 16:37:12 -0500 Received: from mail-wr1-x436.google.com (mail-wr1-x436.google.com [IPv6:2a00:1450:4864:20::436]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C06EEC0612FE for ; Thu, 7 Jan 2021 13:36:14 -0800 (PST) Received: by mail-wr1-x436.google.com with SMTP id q18so7062528wrn.1 for ; Thu, 07 Jan 2021 13:36:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=b2Tke+PYbrPjdh/VepLSu52qSdEUam57Tg136FE7V/g=; b=A//8T4IUJtSAYCTRVKMBNp1Dzq9b6PLivsC3MR+1c7T7QAOz8Xp0qe8pB4jGQQqcbM YlKFN99EWsmn3Oimvsnr6HJQ64rdlNTZBq/3bkcViiLusUpxqiANYSO9fodEHLcKE4R0 Sr8uWFRBSNXYpa8N0x4fC9HwJ9UF/HKTMVvhJa+JwFX9ggwSKRB7/4nau0VkfyRpHlKs 4kl85Ur16tQt6LyIzFgRVtSN2/gBFOAcdJ5wzm8C9KB+fhBlY6sNdiQlFCje+IGe10SZ tZygoXpiTrSxsLowrW+HSGdXIMp0gT+n/Q+z59qCtbzpagnsfx7IhJL8sYGVQ85qgNjU 3jjw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=b2Tke+PYbrPjdh/VepLSu52qSdEUam57Tg136FE7V/g=; b=eY+MbOvK42KCU18UGzYmFhkQzaemb38rzy6jaLo1gAMQREGYfQNER4o0VKkmCYLzG9 42FE3pOk2Y6YNHrNiWKAHFhT9ZFwsrq79ogjoeO4sgkYf8t/wBVDDBexfz2tZO9O8flY XmuW1w463hvy/fG/hhCtU+Fg4FhwWYS2kKxMO+i9z3vehT7bhRqN7gG4DSEwjShTXS05 FGdo0uesCW5v/k42Pa+MHqbCw6IndbuEkOUFcdPJ7sNJ2Lzr4mm7ZeMvaO89O9O/+pWe NVpJMVR9VwZHxIHdYaCwaLqKvmSMM69M+yB9e3aFaeOjpz4RvfCqJOfWMSBp0SJ/I/2v wmBA== X-Gm-Message-State: AOAM531T/xw25uFM+y6fBxEsgoA0J2FDAwrmhs/2AmAgT+d1H+HOViCh Qn8IubRbjfONXRVxQuC2f3HO06fIQug= X-Google-Smtp-Source: ABdhPJycHXQoNrYlGTsZFixYXW4q8kQL47T3GEEaTb7gy2dEWhxs+3nPnX54wRrqx2dJdkf/1qMkzA== X-Received: by 2002:adf:dd11:: with SMTP id a17mr545044wrm.360.1610055373320; Thu, 07 Jan 2021 13:36:13 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id v1sm9785101wrr.48.2021.01.07.13.36.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:12 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:53 +0000 Subject: [PATCH v2 05/17] merge-ort: add outline of get_provisional_directory_renames() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 378ac495d09..73d3ff97f52 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,11 +721,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 Thu Jan 7 21:35: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: 12004945 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=-12.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 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 76A17C432C3 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5B3E0235FF for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727823AbhAGVhk (ORCPT ); Thu, 7 Jan 2021 16:37:40 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38720 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727711AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D79D8C0612FF for ; Thu, 7 Jan 2021 13:36:15 -0800 (PST) Received: by mail-wr1-x42a.google.com with SMTP id q18so7062562wrn.1 for ; Thu, 07 Jan 2021 13:36:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=OkMBD9Rttf0qJ4vQ0leKiHKLBZbrHW77od2y0g+9RaA=; b=c6YP5wjXVFa6fRe/J1o0Cf6zM5g8HmBlNTk7zY5YNZ16SAnkwGVRFvx6FqBPb69Kfn JoRdkuwSwrTmTJmdet90rjnWThdflugkx3CSgQYgsabC+HEwHvpJ+kSfgKltfrIO+FlR 3RAgHaORjsHtjIoQElHvMiFDcJoY4C26kqXvAC71JpdMTfmnj4gTFdDCa3bj28o/y+4f rssDFhrhy4LcfDh0hYh4DwUku1+Kl2dwG4/Z8whdRhV6R2Pe4tT5OpytNtj5Tp9ZWafq 0ORJiUB4dF/c5t/fw7hKhxSRhZWoTjec+sEMRrr9qLyUfQG/3RTjbQkXymnAY5VGSD/K IW9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=OkMBD9Rttf0qJ4vQ0leKiHKLBZbrHW77od2y0g+9RaA=; b=TIM1X6uvpMn9X8jR1XRVIfqHCkIvsu0/OYH6XKTU3oSxMRm7enpom3oZikOCAXw9sZ js+4iApEvrZ24oexzwSuCCbVlcJ6icINxOGqYRyVjJXB4aS8ZWz1HLYc7dcNCWIyQOaR onQyNDq2ai310QXdSel8z6Mft+h6TBzbQMBDyhRSRPTKuDm0A16i3AaW61+HWLYc/4Vm XJYiTOtryltMzZQwLmjYQ1vFOJPUiUmUEUx9Dhlj+1bC3YTZKdlhzEEO2GX8PkZD9IZx CTVolOsTouXfdrO8WiuWHbhazmEAsAWHMwqHlWFF6rugtXtw8Zyj/IAyrtY8xXLsfdMw wGHQ== X-Gm-Message-State: AOAM530Uz3HtrwJ2P9BlmOwAEage/cmwgWG9aECB5qJTcv9YZl+ShwSS nekqO+tBU93d30BbS+8rXifzQpqng+w= X-Google-Smtp-Source: ABdhPJwvK/oX2xq8Y5RhVhtMU2WOIbQ0m1sgeQgdFzJlRD7gOtwYhKle+2SJ835T9mSfZvKUwST4ZQ== X-Received: by 2002:adf:9d48:: with SMTP id o8mr546226wre.408.1610055374364; Thu, 07 Jan 2021 13:36:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id v11sm10120932wrt.25.2021.01.07.13.36.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:13 -0800 (PST) Message-Id: <4e79a96ba1cd5635e5f4cd6e57f5d6055ff37804.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:54 +0000 Subject: [PATCH v2 06/17] merge-ort: copy get_renamed_dir_portion() from merge-recursive.c Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 73d3ff97f52..7e0cc597055 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,6 +721,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 Thu Jan 7 21:35: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: 12004951 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=-12.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 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 C5D2EC4321A for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A0F2123601 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727732AbhAGVhi (ORCPT ); Thu, 7 Jan 2021 16:37:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38722 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727699AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AEE85C0612F4 for ; Thu, 7 Jan 2021 13:36:16 -0800 (PST) Received: by mail-wr1-x42b.google.com with SMTP id i9so7048390wrc.4 for ; Thu, 07 Jan 2021 13:36:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=4JP1HOJAF5tmslgBv1jJeKDuRrchYeWGkW2hGbQECY0=; b=KpzXtijUG5e8jVetzFBxh8rpaUVVRYBsRed22YwC3a7oolo+y/GO7cXsNu++d7q6+Q Hr5w1JTrgGK7SJQ5/WRY3Eoggq7D5j86pn2fXqMoZDvhPsGnDjWh9oF8C1lpkahp8j/+ uAyx35bzFgUSeZXNblG5EYiDQRbh+p+nYdXFJ0BHXedzeQfPnbGQhukztpsparCXLH8v vrbL9jD/RihvWAIypMt1fx1CxRPIeHEmEGiUe9manLhGz7W6oqSrDySq9b4WlGEb87S9 LusqPpufGsDKip9xPFK0ADKlPFsbe9lUrQsnHVymvz6et3/Zh5KpTfX5n94pBf0gYc3w q9xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=4JP1HOJAF5tmslgBv1jJeKDuRrchYeWGkW2hGbQECY0=; b=B58CnTeR7RtVtWM3tcomKm0l8mQ61qMMdEdf+q4WE/JyV0jAncCpNFmbyuEbe3Fh0d G7+HW6TZoRBlE/GAmmiOw+dxFb+xaFVxo0AQZKhsbZMDoOQfI96q5Igo7b0vRs/CPfKG 4d5TW2ZtuE02rBcdEH8FkAqGNo6oGRx6+nmaiYZkxPQM9VeXNQnHohKo62ym2vMbWAHI ZtdTny20rOvA+NrX1VrfauNLESmfjoMg6W6kNppg01OqvxRvOriANjvzwpRIO8axK8t0 5sN4PfQf4g7bXbEKnkt7mZnEJcOhBzP2xwkqyk1PO26Xdgk1ocbhsWGxMWOLPXm4LjIT hp0Q== X-Gm-Message-State: AOAM531iWj+YkxOcjfpQ9CgTxIB8tt6MlpweMX4e31CsJ4Pnz1dXlssD 3YB3Gm5Tz52siuym/7gbcq3JVxQZiTs= X-Google-Smtp-Source: ABdhPJzB+dJLUafIIizABEHMejyHjaFb9kQ8p6BhfBuuwlR3uxUIj/mJIfbPD4ngEmS6c9LgPUFq5A== X-Received: by 2002:adf:902a:: with SMTP id h39mr524180wrh.147.1610055375332; Thu, 07 Jan 2021 13:36:15 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id r16sm11346580wrx.36.2021.01.07.13.36.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:14 -0800 (PST) Message-Id: <1e48cde01b9e2fe24eeda063e0298db8421b13a7.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:55 +0000 Subject: [PATCH v2 07/17] merge-ort: implement compute_rename_counts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 7e0cc597055..a8fcc026031 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,7 +721,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) { @@ -825,11 +824,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 Thu Jan 7 21:35: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: 12004943 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=-12.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 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 54541C4332E for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 21E9C235FF for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727807AbhAGVhj (ORCPT ); Thu, 7 Jan 2021 16:37:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38724 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727694AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 95BD1C061282 for ; Thu, 7 Jan 2021 13:36:17 -0800 (PST) Received: by mail-wr1-x42e.google.com with SMTP id q18so7062625wrn.1 for ; Thu, 07 Jan 2021 13:36:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=HFooLETrm6cM084s80tGP8huAtkbI3KV88B3jfO86ys=; b=na4tZmFV8e3MRtUxI90KO/1Yh9gsKD93iSFniOYPuKXOG/qmT0CcbjCg5hxe/Ai26e NrlgyE67Q0ZY+2UPEz7qHCVutDWFLYJuSeiZ1A5n8jVUqhiMuQZU77wHjTTT6y2AeHzP NvQ2h2a2IQ64D0cteAhnd/e9M4lReQAZwkbHLA271GvGvOkOB01Ba4qvtGqNyDsS/KYp KkWNrfl9lfy2H4yjmfl0MyVC7MnPjvJRCTiyjyoGFS2c0E1VSyjKjqIspR4v3jnhb3wm 3x8Kb2SJRVEEE7EBx0xQiOwV7mceaPkO4bojpMn52ka/4exsnhR9BbiVFaWL10wWZFEC 2gRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=HFooLETrm6cM084s80tGP8huAtkbI3KV88B3jfO86ys=; b=HSugy8P53neWeYBS88EDu8EMjLPw8Ht7B+mKCf6qhaoFlVR5N7M3Zoz/px6C4N2aIr IbnIlboXnJN28P1H8qqR/YHgNdbNpiJgMt3MW9Gog5CQvbLoZRihTpsCaU6Igkbzoi+6 W0EZVrzLi9/DiHNWREvOJXSaCKpbBAMO3+cwPLG2+skyYog+Yx7qX5yVOq2nfvO8rVGo +nbDZvYooUVu0ZQuSufXYgXyergD2+EplJM9JSq7Lq+7cYAxnfb0+Nqu8cCH4Xgpo/uY hggRREyfM0cuWHbwbV0hEHPV1P4lD/lsw4phTDNv9PqRlHO1rUFp+25yOTovycNbVeBB SdPg== X-Gm-Message-State: AOAM530TgSHk8r+Xzm0iRasaAvfXWjdvzUA3KOTd2Uc0zRvKMZEgtW5R TGQdd3S3izVQQOPtRD48+iM7yYCd1ig= X-Google-Smtp-Source: ABdhPJz//97CkrsUacyC32hrxUK8Q88bAcpbda+B56tGihuLgwL8+WVY1vlABh2x7XN0V2iAwhLxog== X-Received: by 2002:a5d:4ece:: with SMTP id s14mr499293wrv.427.1610055376215; Thu, 07 Jan 2021 13:36:16 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j10sm10208267wmj.7.2021.01.07.13.36.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:15 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:56 +0000 Subject: [PATCH v2 08/17] merge-ort: implement handle_directory_level_conflicts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 a8fcc026031..feeb838231a 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -941,7 +941,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: 12004927 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=-12.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 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 907B3C433DB for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 59581235FD for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727480AbhAGVhM (ORCPT ); Thu, 7 Jan 2021 16:37:12 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38608 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726989AbhAGVhM (ORCPT ); Thu, 7 Jan 2021 16:37:12 -0500 Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [IPv6:2a00:1450:4864:20::431]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8B288C061285 for ; Thu, 7 Jan 2021 13:36:18 -0800 (PST) Received: by mail-wr1-x431.google.com with SMTP id i9so7048453wrc.4 for ; Thu, 07 Jan 2021 13:36:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=IM9iUgvIbWyIXf1PCkOZI86FcaiMwFm5yW5FJzWa8Ao=; b=nBNhDb9RwoQkNgDxxga9T6dm1S4YkB6t37oJpYzF8RNfxZ2srq2rO5y/lHm6509Ytp fP84foCIOBdhHmSfeSIkQ7cjjggsInONb9EtQriCNkDnGS526D8sPjvCdylPJqMLp8TO l6pyxIQpAf1aQ2LZK6ttfn5pdNspcy+7ogJrnUicxEugZzyjO2luaWVRvCTUTojBQAVk cZ5xndqnnK0uLo0Gn8tlpdvd8Lm++KTkfSIsNmjAZFJ9gJQXNCmUHKxKg3Ivs+EXFj8W +zIzBNCmojh9YUbzDPKaXsUaIkH+2aI1UtQIzA+C7cHYN2JFVR1DCPvzqesQnPEZLkCF bvvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=IM9iUgvIbWyIXf1PCkOZI86FcaiMwFm5yW5FJzWa8Ao=; b=ppWBVxs1K6cr2O40vU7tGaOhn0nYMaYobL1rNrVAZGYSQXV5oAVrHZJ8xwWnuSj8rX OHZUA/CLBlQ04ILkgC8Zb0IEhrq050uKmdARDs3gj69m4lpRIefzeJaG/wCqFhIRDkGd zZRTbR3a6KPs7BEMy3HXSAZ/Cgb9gT+um7jjl3xfGoKLPtxgeIVdWS5eLiIjTbvJHDaX SA67hzQw7bYabQwLoUdLwnABKbdPjgVZoz7oNdrP7tp1lI57DCVSKX9LKjCYR1+Yx6xJ bj/ZX8V5jo3UiAiXMUzEvXSZkMNHJOFXw60hYjhQy2/J8MOWz5iXYD+Cy7/RbkR+N4pv /1UA== X-Gm-Message-State: AOAM530b4cyPZhylia+nThiF7HBhKDTlN4g73r48eNcMIXWSY+hCCFE2 o0vynKD0Sw+mDowaJvpfXX6cqg4HRI0= X-Google-Smtp-Source: ABdhPJwkFGN6qDwOCj1EIOWTngMgk+orci1LC7PxyzySpF4XlnnF2tWYQh3kv7my7U/pRm+yLlkijg== X-Received: by 2002:adf:fdcc:: with SMTP id i12mr515669wrs.317.1610055377079; Thu, 07 Jan 2021 13:36:17 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h4sm9717296wrt.65.2021.01.07.13.36.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:16 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:57 +0000 Subject: [PATCH v2 09/17] merge-ort: modify collect_renames() for directory rename handling Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 feeb838231a..f7ecd76c479 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,6 +721,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) { @@ -960,6 +965,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, @@ -1285,22 +1315,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 @@ -1315,6 +1367,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; } @@ -1346,8 +1412,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 Thu Jan 7 21:35:58 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004947 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=-12.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 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 F1B0CC4332B for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D4D17235FD for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727750AbhAGVhi (ORCPT ); Thu, 7 Jan 2021 16:37:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38730 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727713AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9A293C061290 for ; Thu, 7 Jan 2021 13:36:19 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id c133so6278187wme.4 for ; Thu, 07 Jan 2021 13:36:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=xk6I5P6DqHm/qwpFbAbA7RHflfrmgcuc6HeGgd6g7G4=; b=cYYc9ChdTdgrWEZeVyfEeqpjivI3n0HG7Mnh3P5we6vXTucYtErmve2bGeNiGBYBIX RxGVcy64QVNUYBy0wgkSEsPaWwVLtdgLt1QkwG9NvV0o0zQc5l8MUFEvQ8fv3Ug8tkFE iA9q7YB7X+DqAtLJA9xvaz6Z1vYwkSfAUuk9jQz8+z+pAPmyPKMb9BMSfUaHb4ErqUz3 NqofY4OBfwSwqxHy38OWBPssH+YlkwUv5LR2FJLpXWnw6RRKzg1Cn6TKFcud1IFDo9t0 7y7pmI3FZyEeuLYAgKZ4Z8OpWGL8UM1dWSVTNPJhLM4aL3Ek4fyfMyl/2YnqMYEPeH1C Iv2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=xk6I5P6DqHm/qwpFbAbA7RHflfrmgcuc6HeGgd6g7G4=; b=kv3u1MWlgS9pBzPSRE5PpshopWxsG7vDaNzaKLUFZdXkB7n72z0GOmeMLAoWm6MFmp fluQrE7VBEPDpCW6jScJpiAUwmNGzWZQEfI1Z1khWU05g0zgscAvJVkjq3ZgCEAewP/l FX3SfjpJfAPS8e0DA3nfTdTd4WDxthHVF3uj8F+yvLrQwbskdog/I9zC0nAaissc0PvL 7xEgm+s5XmFuQsGA88CwktN2xXA4ZLFeWtDbNe+ZjeQrzBhERbtSNi64wH8gtKDjaauB F/47HA+XuTRWPd9jsCfzUODDBhll56rUhQCJrJLM4FtPggMKIJnQTdzzLXz+N51h/W0s xWPA== X-Gm-Message-State: AOAM533gS/k5kc2LQiUNbzIhnEbcdA7gjZdNSlPP5AYwewisfjJmTPGq mD18UfRwbxLUmEP0kveKMDnpI1y70NY= X-Google-Smtp-Source: ABdhPJxU4MQGnIL4vawRBrh4QgnOADU5o4bcT68DNlG6rpjjyCPxj7EkSJJhBxAlm+rvjUD+nNJ3gg== X-Received: by 2002:a1c:7213:: with SMTP id n19mr423411wmc.14.1610055378066; Thu, 07 Jan 2021 13:36:18 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c7sm11316142wro.16.2021.01.07.13.36.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:17 -0800 (PST) Message-Id: <9a06c698857d4067ea34f9ae9dd610b999b907b8.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:58 +0000 Subject: [PATCH v2 10/17] merge-ort: implement compute_collisions() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 f7ecd76c479..e436418d0d2 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -726,6 +726,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) { @@ -965,11 +978,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 Thu Jan 7 21:35: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: 12004939 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=-12.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 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 2D942C43331 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0ACB4235FD for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727800AbhAGVhj (ORCPT ); Thu, 7 Jan 2021 16:37:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38732 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727719AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ED490C0612A0 for ; Thu, 7 Jan 2021 13:36:20 -0800 (PST) Received: by mail-wm1-x32d.google.com with SMTP id 3so6740750wmg.4 for ; Thu, 07 Jan 2021 13:36:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=7SNw9eu+RPlhHL8eL3KhfrVAuFokhSKjmDIaKN5ygSU=; b=Sx+ts0oajqHkOaVNaBKEJHDPHr1dvXX3sjbx80Igz7wFN4Mov33zijTlCmm1xwTUEa E+O97UKOivOp8imgypx/I8nPSeswrWXmYbMOmbXxiHieynATA2/DS2OxiJV5TzyObGJt 9zx9TMs9qs8ljorUKI4SKPPkUrBlg4pruYYEPkymDJAMmK1yMn5MJeTVOg1S4zM3Ahxg LFS2falksAZYwJLv8ihAW62XGNJQ0ZNXtIA2kLwd8N7nswVTithuaWPKj0xMWY+B5Y6F 8L60Q/D3iBGMT0CyQgbczFKtygErGwBfrMjwmRHzQ3YROsUlliDQTzgrEVlinWY5HisA Jg7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=7SNw9eu+RPlhHL8eL3KhfrVAuFokhSKjmDIaKN5ygSU=; b=QWl1NXxst1j1ClYytinplyB3P8QdAaKIuByrbAfNeThq252g6GnMO5H5ZVvLozLETP bkONLy7tEY5Oqpos7HzjWrfVwAJYvzyGVTbzN4z5LshBq7BxVc5ANQVVjLzZTEVK7em+ solKXS1YOW7+K2PnM5K8HEaV28ebFZwtxSu/gbQ4y3CHRIK/2zUWWBcxWLQUnfp49dbY AyOar7BCBmPDGHvWvgKQ22D+nTQfrA92pZPN6Epv8ww1p2ELfWIET6e7xzzGOgrelVQq /XJTwkkhQw6q08l34xxYrxvxjUzNBkIkX74nUU5QynaWWTElMdJlnE9CDM3kgSuBiDPr Lmug== X-Gm-Message-State: AOAM532K9n2QG7OadK/+A+WTMIUIeAd9pEGg9yTUMhw6yzsY+FW1gcOT eiyLpCNDndg69FzphKw+F0ZttEt2+e4= X-Google-Smtp-Source: ABdhPJzh529WEg+zv1yqtI2EaxRU3GBVBwoIL7uqGIDO1YNcL09An1AEpJsl5ZjmpPs7E/27TD2hcw== X-Received: by 2002:a05:600c:2219:: with SMTP id z25mr403560wml.27.1610055379489; Thu, 07 Jan 2021 13:36:19 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id u6sm11154933wrm.90.2021.01.07.13.36.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:18 -0800 (PST) Message-Id: <2ffb93c37ac7e9ca8697a43c41d618d987db4f47.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:35:59 +0000 Subject: [PATCH v2 11/17] merge-ort: implement apply_dir_rename() and check_dir_renamed() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 e436418d0d2..8ee9c685c7b 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -736,7 +736,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, @@ -981,7 +1003,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 Thu Jan 7 21:36: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: 12004949 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=-12.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 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 AF9B5C43217 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 89622235FF for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727766AbhAGVhi (ORCPT ); Thu, 7 Jan 2021 16:37:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38734 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727720AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E4A5CC0612A1 for ; Thu, 7 Jan 2021 13:36:21 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id 190so6306453wmz.0 for ; Thu, 07 Jan 2021 13:36:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=NHnapn2YaP8WvGrSYN719MNz1Vbq/U0fN5T5UuDmtNM=; b=LlhtWRdpTgb/2UbUiI02iNX39O62K/GjcvXYmSxZBm+NAbXQDronE1i/fY271r8+26 ypaDfB1jdhabqeoQX1rv6N4J8J5OS3iiukCte3e9xdnUA6eBQHe463NknZ0no8c/8+25 lKVYjKgSKdv2yrlo1c4akTDsv2iX4OhX4RS2DDILu/8ro6sPEo7fc/798LjHg76EVTTx TIZ7taYDfVxXBU7A1bAkfyHNKu6hHqBX59mNR9H2bmLXdQKahuASE72KgfuWGZtjFK/b +WxAEfVY0qBoPlOYXj/BfDiW1NNwCbVmUBu3ulefyk9DLeQz7VNu6m2cCnJZp45rbDN1 MUPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=NHnapn2YaP8WvGrSYN719MNz1Vbq/U0fN5T5UuDmtNM=; b=fWUBR8WVLM3nqSh3H/UU4EJ5QXx4foarBUx3Yt8XaSLYgAymVL4hfhzNs4c4MWCP+K nh+TMNrNQyAeOdIv2riehftMMxT0guCEZVhqX7OY3RfGHn5xuW3M5nhN+RnSlIy/nbnd bPLBhkFW48SnNLw3ZqWMTSCrWqQ8l5e8Z4oFlchydaw/DzBzpHtKmex9bqymjGCAYFdO ue5jFeNowUY/Wi25ECEG3fiYFYcnw0c9NE1YhHef7mfnovyvGukx6jvkmsrctn8B2CjC CIjTrf1ioYNj9spxyawlc0nvwSRaIX2JnaGgN/TtstPbRuEL9pwjmpLRQwecpsq8PfWN KW1A== X-Gm-Message-State: AOAM530kMELgSGhWgjawezCuPf6eRg6ZBJAMAovqblmcw30er7rBW4q3 +gJ43HYASZYuk7uAFbOEO8jnPrAbdRQ= X-Google-Smtp-Source: ABdhPJzeqrcJDLKYFIbr6a9umyRMqnXFkb9j8qlZyrinobaEOBFQN/87hWmh3Wdr2oB6Qz5AbYZ0DQ== X-Received: by 2002:a7b:c5d6:: with SMTP id n22mr400839wmk.70.1610055380417; Thu, 07 Jan 2021 13:36:20 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id y7sm9714861wmb.37.2021.01.07.13.36.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:19 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:00 +0000 Subject: [PATCH v2 12/17] merge-ort: implement check_for_directory_rename() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 8ee9c685c7b..6823f812c28 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -864,6 +864,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) @@ -1079,7 +1094,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 Thu Jan 7 21:36: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: 12004937 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=-12.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 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 1A013C4332D for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E8BD8235FF for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727771AbhAGVhi (ORCPT ); Thu, 7 Jan 2021 16:37:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38736 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727722AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C8023C0612A2 for ; Thu, 7 Jan 2021 13:36:22 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id t30so7059130wrb.0 for ; Thu, 07 Jan 2021 13:36:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=uJLyoB/uoq2MmvnDWAoRFFOhn647HBz0bQTBAePKgmM=; b=J6SzizH8natltzYvVhrI1zqdwfYCTOOksIerHM5qbgauVPQiciPmtc3goESVIT7cg1 dC7ovqf+DyNDAwtUrRijXayNlmnvkF1jL+JPVlbAHgYTV2NY5Q1pe7nxJhrvl5cpWI6V V3HXg009VHSb+58gDRfB+EwAMF9K2cZk4LqAhTACt5n1H0FbK0i1McKzivG/dZRNqnnt Y6+G1xk0UDYoHfnkelrjZpsxq1DJAR9eP1euTnSgzLUmve2VnClsELoEk+D359Zyb+ff 0plp6543HcoB/bpH/g0pSnHglwM3Cp+rCGfEbh0TO8/QStodweD1fjjhmuyOrn/Gwl8i 68fw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=uJLyoB/uoq2MmvnDWAoRFFOhn647HBz0bQTBAePKgmM=; b=PB+I7PU6sGogx8I5cIYCY4WXirsOvhJ9hy8O58IByK0uuN+8UbyX15gIIwgnpZ0sVQ +rFLCbhtnsV7OOyz4QfNNJLkDO9brOcOKKySTq/tco+nAUWbhXwr2quFDCcB94Ix0LR1 s3WsmtkqoahP9ZMLvx2mm7z4lRN0jgnUYWSseLhGosw75xwqcgMrrMsGUH5GPPh60QDq cW7LdN/6/GTNQc4cv1o3SKC6f8Ve1btAuaOdS5enymVg9IOlX2JGrUnSOobZ8i5SL4Os w3W2heOFn2JF7Ydpr/nOxY/ffPNSmPsXZOi31h5Hv8jW4XkJPavX7G1afeVSi0Z4wQSo zl3g== X-Gm-Message-State: AOAM532CnEQ/GYB6jQPdgMBAvpv0hwkY+AfGu83LLCOkouggRQG6V70h reHwyPNQCz9WIoCXKh3dZurGE6tscRc= X-Google-Smtp-Source: ABdhPJz4NXWo8sj7bvVQJEOfsn/MftuKuIcdwd1XXVWsLRex29UpS8MTe6KIDnLhbqE6YKscHqPnig== X-Received: by 2002:adf:828b:: with SMTP id 11mr541063wrc.180.1610055381398; Thu, 07 Jan 2021 13:36:21 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id v4sm11064736wrw.42.2021.01.07.13.36.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:20 -0800 (PST) Message-Id: <734891cb3153f9e1982721257b766ed9c10b9676.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:01 +0000 Subject: [PATCH v2 13/17] merge-ort: implement handle_path_level_conflicts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 6823f812c28..43cfee29bd0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -864,6 +864,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 @@ -876,7 +886,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 Thu Jan 7 21:36: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: 12004941 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=-12.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 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 6D327C43332 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 46018235FD for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727788AbhAGVhj (ORCPT ); Thu, 7 Jan 2021 16:37:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38738 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727725AbhAGVhh (ORCPT ); Thu, 7 Jan 2021 16:37:37 -0500 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 25DE5C0612A3 for ; Thu, 7 Jan 2021 13:36:24 -0800 (PST) Received: by mail-wr1-x42b.google.com with SMTP id t16so7051092wra.3 for ; Thu, 07 Jan 2021 13:36:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=VsDDCUfuM3/U0xqHj0cutD4REsVRsW0DC2i4mKl9dK0=; b=jcq4s1hIR7I/rmuUKJPyjl1QtZM5egrNNDfx+WeKU3770ZGi8DzQGuolLvLTTlLNBc FLzJYqJCePx2Q4IxCkEx+YIK0OJwRgrPs9t1WUMvC6PLc1MTbcYJPE7jIDy0xkFx2DAy +520ggMEEt6jgNWHzFN0ApfdemJfeCKZawpNFtGzj8dU4miGqzWnjZPTzEZskocNFbPi APy2MRryDXD6QZZB80y8vT1QUPNRmlplB2yDxgQ9E9B+B+7GWkmGyccCteHp7eCJYRMi hAPLd3KkauZh7lPBAeGzlQJYu7bI9gZ/0nyUfGUlB3jbO/uI19ABD8hR95jGxLBbj2C0 d82Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=VsDDCUfuM3/U0xqHj0cutD4REsVRsW0DC2i4mKl9dK0=; b=R89ktbBw1a3OpE/ht7KhBK06tkXSG20jLSSDK+M4nCxehPri827F2JOgmpSKLkFCaB 7DO32gQAfbN4WTn+0gUmnzAjZQViEDxg01Qr/f6GO0VAJvN/WJLZ990369tezhxSWJA2 q/Zo0ZcXc5I+QD2hV3BMIC0dy+cI11vwhFD8AWEJNUTllhCc6oQuj/nwPBXETfAfsNXy NOrO1ET4Dt8zwl9WfHf2+g+i8yVEdA8sifiAzlAZ2Vy0CQ6zSHA0bjh7u5saLSF1TxkA dGSO7I0iS5U2EjgUF9xYAK5nLJh21cpTCx8YPS3xXTHC43NmLpz9iV77N0aRIU6c6ZS3 y9nA== X-Gm-Message-State: AOAM5336wrI0zi7mqh+b2ogXpLAyDgdJ5/t8q7VUpf97XVSeEp7AWDlg FVDlakGe9lh2qxOpTWNdJrO0mhOc+dA= X-Google-Smtp-Source: ABdhPJybvP0H8L0gNxz/DEZh1LCBpZJ6uLCDTJFIS6xtk8v/ctAUef5LSkN0A9sGAseiFdSsx8VYJw== X-Received: by 2002:a5d:504d:: with SMTP id h13mr558774wrt.246.1610055382759; Thu, 07 Jan 2021 13:36:22 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c16sm10556349wrx.51.2021.01.07.13.36.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:21 -0800 (PST) Message-Id: <4b912f2c0251b7d19ba74f0af5563605f6ad9667.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:02 +0000 Subject: [PATCH v2 14/17] merge-ort: add a new toplevel_dir field Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 43cfee29bd0..19850ffc0ab 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -168,12 +168,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; @@ -682,10 +685,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 Thu Jan 7 21:36: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: 12004929 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=-12.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 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 9B246C433E6 for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6F772235FF for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727645AbhAGVh2 (ORCPT ); Thu, 7 Jan 2021 16:37:28 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38610 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727610AbhAGVh1 (ORCPT ); Thu, 7 Jan 2021 16:37:27 -0500 Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3D5BFC0612A4 for ; Thu, 7 Jan 2021 13:36:25 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id c124so6260967wma.5 for ; Thu, 07 Jan 2021 13:36:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=x+DF9E4DRBiUqWwG/Jbo7vmizhmBZ9RLlQ3C2U2KsZ8=; b=QtaMovPJAQ8frFZm1wQ/UHoBs8I0D9hFlRBZUCoWMe1oyONgMt2tvKkhOf63ZSHtWy H3fuzAJCSguDy5euQN3X0oABunTygYQMVjHriZq0cPp/pkb+mEKy4Dj0XuYeNJeu8Kl8 J/Y/tL0Z+KMQMuOhUrUb4zLCMyff4i8O1obaa0G00X214NSjhBYS5e1hmnGI61nty4iV VxD4HFll9p66CUljWTDAgbRzk25g+aI4KUbj2VULuuB70UgP86wGZ+DNBl+eM3aNxqNL ClQeY+PlTmqPHviNu9n2sY1hh7n3x17KKshebvkTLCtsbfnSK+H45+OF8OqczFITGZjq lWqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=x+DF9E4DRBiUqWwG/Jbo7vmizhmBZ9RLlQ3C2U2KsZ8=; b=C4vd1H38ACYj89PO4qF6pexJ5OdrS+v/5gzHNDOnRxct7OQ8Ajx1k4Tzb6o3etnrn9 CKVu2nVHmt7SkG5EoV1x5+qJcBPhos1slmuDo9yzCLBSFgFyQnwOy3X3EE6+PEOyxnck mZ24FlONT6kiEVE/K17IEPf+yoo9U37APlSfb4twhKxJXL8ue719ii6CiO6ZO15qVyql LaJFbVD3nyJgCtQFgzZwZnJuAvnJxARVe0t9+MckOcGSZBi8GEbEc2PjbIUSyrgm7mWh xByoJbets+9/d43liTPEc3fGrE+g8BO9OYWRTNSOPVS5lGM1v/lGj7vI8NLMLnLR3Y6Y 6upQ== X-Gm-Message-State: AOAM532izOyhSa3Y0EEvAnjPcXdNKlxYlhz23sJFOBxx5cRslcy0yU/5 BrdHeI/P5ySV0blaov1OSIe+0ry5/eg= X-Google-Smtp-Source: ABdhPJy4am/2hJFYOz7MTN3Ej+EYnwvU+K4007l+9fkHGO5PYdyjXBvIY75gBLGDgK41e7JfHi+sFA== X-Received: by 2002:a1c:cc19:: with SMTP id h25mr418689wmb.124.1610055383686; Thu, 07 Jan 2021 13:36:23 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z6sm10495467wrw.58.2021.01.07.13.36.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:23 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:03 +0000 Subject: [PATCH v2 15/17] merge-ort: implement apply_directory_rename_modifications() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 19850ffc0ab..ea6a08e23e2 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1224,7 +1224,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 Thu Jan 7 21:36: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: 12004933 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=-12.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 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 AD831C433E0 for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 86C0123600 for ; Thu, 7 Jan 2021 21:38:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727633AbhAGVh2 (ORCPT ); Thu, 7 Jan 2021 16:37:28 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38608 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727612AbhAGVh1 (ORCPT ); Thu, 7 Jan 2021 16:37:27 -0500 Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 134BBC0612A5 for ; Thu, 7 Jan 2021 13:36:26 -0800 (PST) Received: by mail-wm1-x335.google.com with SMTP id g25so5643464wmh.1 for ; Thu, 07 Jan 2021 13:36:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=zuhaytbslpiiTsJARPXCZhteNOT9TskDEFoa6C7OWHg=; b=LgpJGbWt73DP7z4zGn+8hj0FuAHx3LliWSlr6tUM6rCGhLsgWnjnlYa6YPew2KRZcG ds23p9TFYmziTTBVufDi78aAqVS0HG8Rlr6PNqvDK3M4iqut52nOmMiLd4poev500H/v wm2kGksq5TB+UKPt2OIS4667OtAXKx72/ZClOW75hmPq6tqCM6I+rC10Lb4ZZ+GWCzfC rtQUvGLjk92dQv1coQaVN4ECghMjOxIggkEsF2J4tzWc9ONUuwjzkPDSbR6OI8B8lFtQ KMugEKFEbgulTr7lGsSUHmPWZBcuQqr0KCR2/jsgakNRWWAbdnHSvlzyiOeHV852ZPBg XD7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=zuhaytbslpiiTsJARPXCZhteNOT9TskDEFoa6C7OWHg=; b=W8oWirxmh9Iaz5RjMC/stBDA9lJB2HK0QfhUeVMiHgca8VNvlpj6sZMt89bIltHWAM 7J63qmXkvRVQn0hzJrlKsteWY4Es6vOBRIjI2jkIQ578x2Ef0xtcaKdima723OyWoXUL +4ZL7IQyUowcIIizJ5mcRjAd2AHYWeAO6xS8/eOvlAqy8bSwpazlDvsPqw71KrnMQTkm xXKzcYv/yipTESyZCP+7PtzAOUpUa41iuUMWyuRC1CsUh0wgCShwRzPOR7sq0xK/1K6U Py+PviycBlRomRlFCoJtvoNXBAcBzNCdH6ehk9k0ISYGaOkk9rQtK834vdGxwRauCXXm Nqxg== X-Gm-Message-State: AOAM5300szbKp/ACwCMz0tCn6tTEXBwkHm4+NhDV+YnM3NiMLY2Q8zBj OEAM2iwWBq3gL10PkfZj8/oNOh7pBmc= X-Google-Smtp-Source: ABdhPJz3AcHLulUdmPnBGjnO1vjruw7pInpawbYPr5WL0dwzMaxSZFhUqDjaL5QKSOn6UNdtkAHbOQ== X-Received: by 2002:a1c:dfd7:: with SMTP id w206mr434673wmg.48.1610055384587; Thu, 07 Jan 2021 13:36:24 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id q15sm9737637wrw.75.2021.01.07.13.36.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:23 -0800 (PST) Message-Id: <11e45af831d14296c6a78441e423aba315c8f76b.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:04 +0000 Subject: [PATCH v2 16/17] merge-ort: process_renames() now needs more defensiveness Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 ea6a08e23e2..9e4ebd9c4d6 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1411,12 +1411,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 Thu Jan 7 21:36: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: 12004953 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=-12.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 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 D5F18C43219 for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B6014235FF for ; Thu, 7 Jan 2021 21:38:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727871AbhAGVhx (ORCPT ); Thu, 7 Jan 2021 16:37:53 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38776 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727858AbhAGVhw (ORCPT ); Thu, 7 Jan 2021 16:37:52 -0500 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 55FB0C0612A6 for ; Thu, 7 Jan 2021 13:36:27 -0800 (PST) Received: by mail-wm1-x329.google.com with SMTP id g25so5643480wmh.1 for ; Thu, 07 Jan 2021 13:36:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=gO75Y2ITWHlP9keipCaly8dIgYl7zS22kQ7bUpxDDyE=; b=ngIcU4ZSf2kWMPc3QVpiY7nA9Zh3hKk9DEpO9lixDkH+Va2L7yTv1ALfq27euTifp4 WbKByQZhQmLfamuwdQcyon6+/+DQwejn5YqczzYW9AFLL3Gu8iOfpMvPm409loiqZhk1 35z9RPU8Z1EJpecBk2JtWuxDB6zl13SMcI/2GTiMNHK29o+VXnugNC9qhRs+mfTwaAf4 NUuxwRUMp40dQz6L4BLaMK0R3lbBBY+6OMdfpyQVne40Vh+mb7CutCvum3wtxhaPvzZG qVz5OzI1GJiaG0NP/XTSGqv5ZYenxbJvE3oUmYfAk7izsa0TXIzYNEcrP10j5kCGiSDN tgtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=gO75Y2ITWHlP9keipCaly8dIgYl7zS22kQ7bUpxDDyE=; b=GctVbIsDTH5yZ7n5xt086V51wmTO1BwnhNYRaSDws92XHUIpqqbXLGk7YL2YPjDT7D hgkMbKaGUpkzc6qf7sOg7vmvDLziewexrSz4ObK40OmB3RfTX9+XrKUK9RMfYoSjoZ6z u+9owGom7Ciue4cGNX2wcv6FG0nBb38YGVi9LkGc6YB0mhQjkXaYnClXTRCgq6TlsR6y BX/b0kU3cmX90KG5klcVhQZ8dggA6gnjG3UN8WDeNxFWOb7sSJXNZC5VqqLF2xNa0Qi+ iTsnYu23BcZk2qHk91mepIGEX+y5brEawjlL4Gmzzi2TKnUB4laqSZxWKVwaLP6+oFoO JHmw== X-Gm-Message-State: AOAM5315CcLmXpCqsRGRmDIA4bdqP3QLBxUMTV199qt3YdFI82pYAZsq ukdJ3/0ridqfll2lwBCt4Gbv4yX41Ds= X-Google-Smtp-Source: ABdhPJxOksZ5taxwghHhhbrRwQ3S341QCRoX5Vrht0yWRXDSb/PbboXx1I7l2HE8wvXEF2oUu4tRWw== X-Received: by 2002:a1c:c204:: with SMTP id s4mr384751wmf.73.1610055385680; Thu, 07 Jan 2021 13:36:25 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o23sm10735170wro.57.2021.01.07.13.36.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 13:36:25 -0800 (PST) Message-Id: <551878bd84da895e0899eba620553f6efe60e100.1610055365.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 21:36:05 +0000 Subject: [PATCH v2 17/17] merge-ort: fix a directory rename detection bug Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren 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 9e4ebd9c4d6..55a835f8b97 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -764,109 +764,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); @@ -952,6 +849,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) @@ -973,6 +878,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) @@ -980,19 +955,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} @@ -1000,12 +967,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); } }