From patchwork Thu Jan 7 20:01:10 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004709 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 688ACC433DB for ; Thu, 7 Jan 2021 20:02:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1F42423444 for ; Thu, 7 Jan 2021 20:02:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727269AbhAGUCN (ORCPT ); Thu, 7 Jan 2021 15:02:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51860 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727198AbhAGUCM (ORCPT ); Thu, 7 Jan 2021 15:02:12 -0500 Received: from mail-wm1-x331.google.com (mail-wm1-x331.google.com [IPv6:2a00:1450:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9ABDBC0612F6 for ; Thu, 7 Jan 2021 12:01:31 -0800 (PST) Received: by mail-wm1-x331.google.com with SMTP id g25so5542145wmh.1 for ; Thu, 07 Jan 2021 12:01:31 -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=IUIoipE+o/j8OjTFQCpddRh8GIYxlJ1GpvvmsTzdnkQGeNnfkGuSWbWESIh3OYFTOc De2GfJs+j4EDcrfwRucmZHupZcA6bIp+mQuFm3nzMFP+eJppxsS1DON88bnGAZmW7q4l fyEMXkjAK7Cf204hrnRgurq2jbnxTRylxbek7k0ekDC4lf8LSuDcOA0gLqW/UqqCgq2a aPKmxYWJ94W2EgpufkF8ZpTA5Gnt5qGJAgLpftXweNqjUp4Ei1jGh0lEUP2JDPTrSxpq 9U1XIeaBRwnHmHvWUer2ttIVNgpYS2Fv6g5LWPKEBWVSh8X4EYxiqAsQ67jGmWLtzlcv eDLQ== 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=XFUqMPhnhaGd+1cZ852oVybkESvpJUiV+BD4r/BaNtI0wA4LxuP9H81WO3OJ5VepDa qPKqIqMAkDVkBogL6PtqDbg8gNQtzFRc/Y8YUA9n3kV0kBldEljSkHXeeSq4FzWWYn5F hJYBLO6SdBohpBx/DFW+nYDDd/0QgZB5gCBC9oiR1pwUXnPUMS91UrjeTXcoaV6JoANO TrZ1Huuh2zcgzri5Y7W3OMPxxVkIZu7/TD1kp1T6X90hpgZXPgzUvIz89hGYQSZYEgkC vJOGn1P1j6ht2wBq9NGfjv8Ci1tc3/PyJqYUl0Zu5HMA1xQ8qqjxJ4oA0M1wlkZs2WUm GmHw== X-Gm-Message-State: AOAM531n++40wluS+iQ/isg3Z7H+q2RPOOyNjcLv20VV2/x+AYFKqM2U itld+Ech2rR11sbvFLeExI/9EKCcKPE= X-Google-Smtp-Source: ABdhPJyXG+UfG9vlKSBuX+Wrji65hbzlPTPJY5i5ths2/bZf6B4PsJRIRNgSLuBI0jUp0k2pOnWCOA== X-Received: by 2002:a1c:e246:: with SMTP id z67mr166812wmg.166.1610049689978; Thu, 07 Jan 2021 12:01:29 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h9sm9339020wme.11.2021.01.07.12.01.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:29 -0800 (PST) Message-Id: <41a99640cc55d71659116dd66db6048cfb436e34.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:10 +0000 Subject: [PATCH 01/18] 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 20:01:11 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004707 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 1E49AC433DB for ; Thu, 7 Jan 2021 20:02:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D900923447 for ; Thu, 7 Jan 2021 20:02:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727438AbhAGUCO (ORCPT ); Thu, 7 Jan 2021 15:02:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51862 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727199AbhAGUCN (ORCPT ); Thu, 7 Jan 2021 15:02:13 -0500 Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 81A13C0612F8 for ; Thu, 7 Jan 2021 12:01:32 -0800 (PST) Received: by mail-wr1-x42d.google.com with SMTP id q18so6861138wrn.1 for ; Thu, 07 Jan 2021 12:01:32 -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=f/MTUUxEWVyrtnzPt97vtD+FPPhkdjmxXQEska/VTS3zn5GH96BhrCAa0+wShhoeZW ILDHk1ux4MDyE6UcYxYWLPY/kIGz1Z2zIv2dzqRlSr/+H1Z2F7bEEBibVAaDCfLzQTP/ AQJYfK4Ag3Bk6PuVauUvNQKIdAx4QvwBZYQwdYbcHngXbL8TKPJGz3qr5T4qzKrOQ4xx Kkh3S+oTbczKPJEH9oZuIeVEXfnKj8T6Aha+As/n4d9OgiWRskMY9YIEHdW/VpXLiLnI WrnlDk4RIsDzm9hrQpY+c+OzICxSqRRAOvpbQO7iKBTFGdYmppJSOniS0qCBGVUDM+om t+ow== 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=t+1yumuK07wO7rycU3RjFVlofkdIL+QdUmNOVioPpyTm5pGyUKw3F7GzT3rLZRhf+r zZWmFowz42Cxj0NSRJ/sYiaZCmTLOslpxxDGjYIzEASNu6QMkv8knKy1pZI89AKQNn2P A019yZaGKtQyYm5BJ4l2PlKIds0svGVqoy/N5yDmGou2e9JPDhwzhK6lgbyKufiret/J q6vqoCbcbY/7w2DPXmdmcCnO+I81h5nWL714/Xltxk3TL9XjYN+U3Gi+EGDm0Ib1lHCv DT0eyp/g63huHYdZrIYws1RgmfijiRCtDNVRUwIJEMaG/OvR/PEyTX3idNemJGdp1QvU U5Fg== X-Gm-Message-State: AOAM530qqy/cuTD0l5aWuvDeQ8J76RIzesmI8XLpjQOS/yz6uCmF8czU X5+tHcl7Fq0lfkW3yaOS+0mILQq018g= X-Google-Smtp-Source: ABdhPJzOFxtjDXDdUbYawbx/ZX9rxcz8ZVXAcNaX5kNIwovVprjAk5kx/UrUcQwSG3QA2Un3tTu1bg== X-Received: by 2002:adf:a1d5:: with SMTP id v21mr304155wrv.24.1610049691093; Thu, 07 Jan 2021 12:01:31 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c20sm9013447wmb.38.2021.01.07.12.01.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:30 -0800 (PST) Message-Id: <762151802be53fbe0269bad721bb93ed84fd8f8b.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:11 +0000 Subject: [PATCH 02/18] 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 20:01:12 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004719 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 15433C433E0 for ; Thu, 7 Jan 2021 20:02:22 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CC3F523447 for ; Thu, 7 Jan 2021 20:02:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728099AbhAGUCV (ORCPT ); Thu, 7 Jan 2021 15:02:21 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51870 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727199AbhAGUCO (ORCPT ); Thu, 7 Jan 2021 15:02:14 -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 81138C0612F9 for ; Thu, 7 Jan 2021 12:01:33 -0800 (PST) Received: by mail-wr1-x435.google.com with SMTP id d26so6792135wrb.12 for ; Thu, 07 Jan 2021 12:01:33 -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=SJpXqdmmErnp+cIrwLR3rYxff21X2vDCEewZigQ5n03ao+yrZegRDfe/a++2mJO0oP BZoczeQP99VAg037BObNhp9EwFE1X4A84fgZAUn0I0/F1J2dFWAo78rRCYJlY1fJb/jD /BGKPWoauPFeGsarob2eymB4RbTMMA94sAmaxy2CC1s71lGxAJW+aNQcW54QB4asTk3O Gm2tSqK5SL+GSACRTaQ0QXeGv78MaQ1uz8tPvVK3jYKKPJ7V9da33WSXVZsumwHK3mHS Mhrpe0mKNgHocI2AyF+KAqF/V2qsIxlYXjZgLERP6x8TS98TUshheYiqIRn+BoOdTbG+ lUAA== 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=mM54ZoQ14OBOz7r2vMcqTsQ1Oeo6YIHM8kvuZs/jUO+kvHU8Fc9TvhAQul0YVAaATU YXwOJ5Anq3vGXpw6FFHb0GxkP9zXFH/BlyihLdGYH/dAULQJSSP1tAjCCqxSLUjJT1tU /KzrOrgdfAj/aKOnYgM3pAj9FBZyp4YHEPcjSIDukI+a1NO3dyjZx6jjuQN0JbYtCTGT eWt6N+7FvICMBtI+KfMj1TsinBGfNg1DYis0VmN10cMbU/xvZYq5h/FB3A7R0KobTg97 TmbgqwFjTM3GWAjQ/SsM2vlVCyKQx022yMK7YsBgYZdeR6mqtX3zaawgga/9i2vHNj+T BUYQ== X-Gm-Message-State: AOAM531O2hr2BgFlMui7lw4jQvuZw/wIk5wjVx344H8gBfLtVuRvlDlz Ib/pN+zSIsuKRyaZsrfoYjB6ipvTFEc= X-Google-Smtp-Source: ABdhPJwflP+2aTVisFlU7CGnFfRc0+iKZP9vpjsBRrtiymBO6MB4thd85E6F0a3UDSHrNUp7e1q7vw== X-Received: by 2002:adf:eec7:: with SMTP id a7mr272489wrp.45.1610049691999; Thu, 07 Jan 2021 12:01:31 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z63sm9501090wme.8.2021.01.07.12.01.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:31 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:12 +0000 Subject: [PATCH 03/18] 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 20:01:13 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004729 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 B01F8C433E6 for ; Thu, 7 Jan 2021 20:02:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 80EAE23444 for ; Thu, 7 Jan 2021 20:02:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727962AbhAGUCS (ORCPT ); Thu, 7 Jan 2021 15:02:18 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51872 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727665AbhAGUCO (ORCPT ); Thu, 7 Jan 2021 15:02:14 -0500 Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 499BDC0612FA for ; Thu, 7 Jan 2021 12:01:34 -0800 (PST) Received: by mail-wr1-x42f.google.com with SMTP id 91so6832105wrj.7 for ; Thu, 07 Jan 2021 12:01:34 -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=sENvxkAB0BOdVB+t2BnGOAVxStMQLTkt6MP5GMRSBpNSVrgN0mJJEIpxGuBHQbKE7U WaCwbiUIIxdNd3HojiLiiRSj60XhSb6O0m5YxwE8fmJah3sEz7677RIPF8pS+oNSF0mB eWOaDD+nndVCIBr9uOE1Yt0izy4ZRi/6kIBXb1aovkRs22x6ObGqp878bbBk4E22J5Gn iR8OB7g8/ku3HH67GyyOdBEZB9mmV83bCW+nktR3R/TSvUKeeRNCJYVeNQuA61M5vhgU iOgDmL/eurnHe/cKe3jTcNjGL58knv4nLIrMU7zSZwWRIeG2EvA6G+3Qt/LEn10AtaM8 +ALA== 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=HmZEOHt0+jt6foH/Ew6ZenaGCBDB2E5FeGt6qiXTIETjaTPHHXhvDHSAeNyJ4/ZBaJ 2MeUdRAMLTUVYuyacO9k1bke6pEZg44X3kGahCE8GNwGZIwUy+wMDm9/bWGKDmXdNJpe MPJzldemIAjoJOQ4BzVMCJNPTelyMmpcBu054u4N5GuybrytRD64G1NiXMILlHP/H/LH rY4pyBtrJEK/H0K9bgAcd2QzTpy+jekshuC7lxch8eXj5HOZ0vICGaBU8sByyV3AkYPB EycBMvhXCJlBWQgaT0QE1Dw0yIdkPjVjz/pvo5eD0CXFmdp+Zurl9TWPO2zrWEoTpXVe 9x8g== X-Gm-Message-State: AOAM530PHsKLIZiK87N63X5HoMa9QzC+edGU/UQt7W61qtGITE8ldNG4 0zJKvhVKi4/UkJITZAH3OsQDLvLTQus= X-Google-Smtp-Source: ABdhPJzjk2Ym/bsmsW1sqq7MCmYHaiVW0ofT26kIPcj0PV4dr6PsZiD0KPohRW2Z4Mq222JmlCGSNg== X-Received: by 2002:adf:fccb:: with SMTP id f11mr273362wrs.3.1610049692903; Thu, 07 Jan 2021 12:01:32 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id u10sm8892913wmd.43.2021.01.07.12.01.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:32 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:13 +0000 Subject: [PATCH 04/18] 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 20:01:14 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004721 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 63A2EC433DB for ; Thu, 7 Jan 2021 20:02:22 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3C7AD235E4 for ; Thu, 7 Jan 2021 20:02:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728080AbhAGUCU (ORCPT ); Thu, 7 Jan 2021 15:02:20 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51874 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727693AbhAGUCP (ORCPT ); Thu, 7 Jan 2021 15:02:15 -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 39A39C0612FB for ; Thu, 7 Jan 2021 12:01:35 -0800 (PST) Received: by mail-wr1-x433.google.com with SMTP id r7so6824613wrc.5 for ; Thu, 07 Jan 2021 12:01:35 -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=MM9il2W9kHJqw10TYgdenggIMtapdgVN4F3WpUNzKslcaGKW7iJX9ffb9NYfnFG6TA 9IRIgu1w50DxkyH2LH9IW7EObEdv8xMr3roLd8clOrGwZdlX/JMPdMNR/K40ylQEoipZ F96L6Iqe3rxa2b6Y2qrK1A5Nm4fCSJe5paStwmRL1BgYdPp1yGmVQRqzkTp7/ST4fA75 S5g30RmgQxaML8lENEEZ+WOhaA0tuoaLdhS7vR3/2oOFA9XFFUEzOolB+0ch9padWfvN hgpAyEYD/TKmBSeyJfbm+pZ5Des0X1F63GpgJ3jaqq6LTE3va3J9+kkS1DgxmvTg+hj9 Uy3g== 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=cqlLLPgbwRw2g/9iXPfFhR9M+RfVb71IknPqgyOuue+3GKk8wELOjVbFoPqSE8HWUz PWdsC5qaQXQ4H51oyTgsMA5KfTpZd3GEkjgKlaYcKxLNrpRZFKnlYQsNedG1aIyfxr1I SCU+bmWGAMq+onZvC/SBWQILc5mgTdzGZVmq0xeQaN7ajqgEmQRXYtGla1wWltx19NuW VCORWHZtXsn7WSUxk669YEUmJrnkBjpkGIw0ydI/pKZgw0BB3wUuUvM1wCsirb0IxQrn pjGzCgzrVgAmBD3LmeNUnZR8Jia8XsC/CQUe762sg8oT/9tORw3DtJjk2Nlbjho+HRGm U3Yw== X-Gm-Message-State: AOAM533yMjw34XT5MNTJ5wXAiUDiajLiurcxGEqjTliuj6Ydl0mnkfGu rR5yT9d4O5Bac/kat7pkC7zd+h7sZoM= X-Google-Smtp-Source: ABdhPJwS/iJur4r3cfRO/M/fZZjGn92rwJ6oWn0CNpk60E8eTzaBwMQ2+tol+D3Sb9kW1s3TkZT0bQ== X-Received: by 2002:a5d:4242:: with SMTP id s2mr256449wrr.187.1610049693798; Thu, 07 Jan 2021 12:01:33 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h16sm9043083wmb.41.2021.01.07.12.01.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:33 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:14 +0000 Subject: [PATCH 05/18] 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 20:01:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004723 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 36EADC433E6 for ; Thu, 7 Jan 2021 20:02:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0915F235F7 for ; Thu, 7 Jan 2021 20:02:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728058AbhAGUCU (ORCPT ); Thu, 7 Jan 2021 15:02:20 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51880 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727790AbhAGUCR (ORCPT ); Thu, 7 Jan 2021 15:02:17 -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 24B69C0612FC for ; Thu, 7 Jan 2021 12:01:36 -0800 (PST) Received: by mail-wr1-x433.google.com with SMTP id i9so6846954wrc.4 for ; Thu, 07 Jan 2021 12:01:36 -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=h+Fuxh2ae9BeqMB3M5CUyzQ6cpHp1yzs05olkmm6JOPfYbmvxFrYylSfZ43Tgqi093 yzAJZUemvzbwGVwsgUVONsPIGTAeoMBOMR8UWkwh2H+FSIqNYCQHrjHJ92vsd7dzP1ES Da3KeQJrdNESMvsM9GM3jNU1DzMX1hnzocRTptZNBCzYgDBbf88VLrnV35Pi1k/DRMgM czj32rABOAaHTG0VPUQa2jNgXQ6HEplJPJVnUatiSs0pdrFMpr/otqWNnvRahi8VFrHZ VoCNNAuopSmJltT9IFq2Am5h+MWj17CjKSnfbnr6uGs8i8Aa3WAT6OJSR5xc3r8kLZ60 21Uw== 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=UT93CZe7WvBOt8oNCZ4omG4BsSmsOtSNTGQ3+eL9gjjuwxOqCV9EXeD0nJLegcBBY1 rzpV2/drKUCGBQgJzJDEGRIhdD9cjb74wh8r0ET7ZViIlnUola6qdxNSiFlGl8f/Nwvy iwPtfjJ2vYzNZGmIA9OGM/ebEKmUVVF4rRGzH2HwLPsbBXWPLy/Vf570Ybm8rKMKzOvc Q9lj/hNdlonfCRqLWhWigTvCd0YxtNLfMw1NKx4XEQxzWgiiIkTJefg0qdnj2xxUzvjf +C3gAvxp1FqxF7tiSpt+T5jzMO3EaH5ofjHtpjs7Me84JSQtYkvsAFbie/uOG1/4TMYS Ou4Q== X-Gm-Message-State: AOAM532Kc4KFIhxH0vu+2STbz9CMrFWnz1aqTvr9MP95YuSUv8tJaUiQ L/88dNnzVoUWKN0/t8G6ERXd5HjC/Bg= X-Google-Smtp-Source: ABdhPJzr20+gXauGxmF4qfLVVM+ydk8LTz1a2gDl1/LzL4xqcX8MgRhm+1T6nl9tEw6VP+TkYT+rYA== X-Received: by 2002:adf:fdcc:: with SMTP id i12mr249673wrs.317.1610049694708; Thu, 07 Jan 2021 12:01:34 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s25sm10088932wrs.49.2021.01.07.12.01.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:34 -0800 (PST) Message-Id: <4e79a96ba1cd5635e5f4cd6e57f5d6055ff37804.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:15 +0000 Subject: [PATCH 06/18] 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 20:01:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004711 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 F0DB2C433E0 for ; Thu, 7 Jan 2021 20:02:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C656823444 for ; Thu, 7 Jan 2021 20:02:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727999AbhAGUCS (ORCPT ); Thu, 7 Jan 2021 15:02:18 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51884 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727903AbhAGUCR (ORCPT ); Thu, 7 Jan 2021 15:02:17 -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 2A3F8C0612FD for ; Thu, 7 Jan 2021 12:01:37 -0800 (PST) Received: by mail-wm1-x335.google.com with SMTP id c124so6104182wma.5 for ; Thu, 07 Jan 2021 12:01:37 -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=Nd7qC/DYENxcM3UNuUSUkwQ3y6nepmk4E09I6PB0Qlo4nNy5rmGULuH6kImopn9wQn 2Wt6vNswPlGflLkkFHNhzJUY2IL2c6LzrgyWLnEiPE/PbHel8bchCHdoUC657riecK7B cgqgM/PPgb/6KX/qAdDhpY8a8LkIN8H/bBDTFW7+539XW44xrJY2Jh900/oFEsS7NAyM evA07W5+w+ENYB0xX3UeVKugH25avdl3jwt+PXxFZ0VCHk+HhT0KoScrMs8p8wzrZ6Hn R4stSvf/1HCkDc9QkdhmSPpA8B1C7RAMdKAERqDTh9yebEPcxScXvamcW6c95JGa2EOk IZhw== 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=ROIyfswAjUrjfDK4YiHdYDbknRavqrXu0Xfa612yCgLDnKM6NOczTc18UhvVRV9Ced 0pa3SQH9mRmNMutvczm4e13t+8m2mjpBuZZETsxULi3RLowGm/ywBaVwasc54gt8NcPc nSDqIbikH3vbvc3Rj9NXyE0ZjJ5Vpxahqas5VK0HOUzOKW6oaLFK1hHZrylYDwPQ+ErV bRIHjhO2tCuQALGfro7qLm9aBggdq0tk1MD/xtjCRgQuEFUUdA7otN8a2HJ594YCcmwT WcVt/9pWS3iuASmg5sutNQ0tCCscChpqGKE2wIM/VkmdGXVlG2Za0rIzjXAt0v4LogTt oyNA== X-Gm-Message-State: AOAM532g0igpoxr8LtbK1t7t4rvzjjTCl8YXu8VspR561Ul/4P8+3lPo f5mCNOVEnhlJw4288eZQCkUva2XmRWY= X-Google-Smtp-Source: ABdhPJxLJB3g8beJ7dIBz61F4Nr8/EY2SVu56Ea/r4Fj6x+rxeOkQf+v5zPnlRHrB7rqVu/lIlvdTQ== X-Received: by 2002:a05:600c:2042:: with SMTP id p2mr173251wmg.152.1610049695674; Thu, 07 Jan 2021 12:01:35 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l5sm10006218wrv.44.2021.01.07.12.01.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:35 -0800 (PST) Message-Id: <1e48cde01b9e2fe24eeda063e0298db8421b13a7.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:16 +0000 Subject: [PATCH 07/18] 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 20:01:17 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004725 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 B6329C433DB for ; Thu, 7 Jan 2021 20:02:24 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8B95623444 for ; Thu, 7 Jan 2021 20:02:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728104AbhAGUCY (ORCPT ); Thu, 7 Jan 2021 15:02:24 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51890 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727903AbhAGUCS (ORCPT ); Thu, 7 Jan 2021 15:02:18 -0500 Received: from mail-wm1-x32b.google.com (mail-wm1-x32b.google.com [IPv6:2a00:1450:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 10258C0612FE for ; Thu, 7 Jan 2021 12:01:38 -0800 (PST) Received: by mail-wm1-x32b.google.com with SMTP id e25so6594490wme.0 for ; Thu, 07 Jan 2021 12:01:37 -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=muBC3zn1iuIYNWCMRX49W5yvQYEd4Mr914GzMofcwCL2Rav6oQYlaA2E9/JUr8AyGk +ihE7wMHRUJuyGZa8StuzASdvA9QNz6QqsiD9MFASGBaisXKHUoondFSDbnys3Owkigd 7eoumoYcYaNCBZGTIG3/AzSDxDr4x6JIqQQskRyUO7dIwyHFBDa5O4GLP6X5bbHsxmRf WLl48h82oR7J9VO0bMj9S4V7eD5cC2G/OkPEeU2ZWxKGwZPg0ZqCr5eBdsOGfJVi2D0A /Cie4TpzACyjvCOnMmxVk0r2p5OYRu5zc9+UaiQq+0GpaKr4FNnQpXqawkfXZltv4njP Oiww== 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=Z9n9X0KnS9oKnzgbZhqOjU3UQX7R3O+8HTJI83BYEmgVOVbumSQfvU0PYZ4+heK3VK Jg7AtiI7gdpMflp/4DANgqpHkdiLW3RWJ2I6wEeBwt159X8Aclqo1LxBg9XejdaRWaCY +uZc74SxLcCe4TgnbN20VNz2IwZICNyfghh8hRRzrT6ck9MidmnWYmLvA/ugE4o7fNaG nlVGvvZbGmdiH+bA8GMltqCvol5uZ65I7zW1iu0Z8NTuRFUE1Io8E/St3P9q9pMFcfgb O9hB95JqNugeXl4/0lt0tsGn7VvDkYI1M8UsQ/OUELySkhmXsrdqpNd7AC01A4VQBopm j7mA== X-Gm-Message-State: AOAM531UMazx5+BsZZLX0XKj3idlGdH2j4WsUArAca5CI9nTAByM+5Q2 KMRmgE3fx9EGpOSv9pETMHIkMDoYnoA= X-Google-Smtp-Source: ABdhPJyhjGaOuqkyM7/BH1v/J+tMrqriDO+Iz2E6ujnR7I+gNmfuzPpBH0rWYDIveS8291DL+cJ9sg== X-Received: by 2002:a05:600c:2903:: with SMTP id i3mr158416wmd.41.1610049696587; Thu, 07 Jan 2021 12:01:36 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t188sm8812140wmf.9.2021.01.07.12.01.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:36 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:17 +0000 Subject: [PATCH 08/18] 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: 12004727 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 E51A1C433E0 for ; Thu, 7 Jan 2021 20:02:25 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B2F9123444 for ; Thu, 7 Jan 2021 20:02:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727875AbhAGUCX (ORCPT ); Thu, 7 Jan 2021 15:02:23 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51892 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728030AbhAGUCT (ORCPT ); Thu, 7 Jan 2021 15:02:19 -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 F07ADC0612FF for ; Thu, 7 Jan 2021 12:01:38 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id a12so6805112wrv.8 for ; Thu, 07 Jan 2021 12:01:38 -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=JRA7yteWnlVxyuDgI2O8qXhqt/APGkbbObax/5e0egnfokICAOBJudvyGV70c+BhO6 6agFVq+m0e/dewsI4kIwK+O6kvyjhBWfAaluiX7e4RvuTvS7s8XT0yAbXPjsDqYKP4Xg 2yr1TeY5Gsrvuk8brjtc/NWLs5geMFcuO3HtG1lku26Ysx/9iJRCV9WYj/pvZzZS1wV+ FLwKkvQPxa8zU2321A3K5rWxZ/G1qu3Jv80QZTPkA+A5CRFWkKJIOGRHwJYEAi2SJG8n Eb0jQkQtmsAz3tIP6J3L+1LnCsC7XHDGH0oDBP8nSV2u7L9v0843xuae4O5kCOll9kBo k/KA== 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=nv0zZHo1Laapl2SOZClWWNTb1DC0fW5B0hq94uJs3rh9Nxee0luRTFmCwcfWzm98W3 mY1fzrSop3Mna18U4AsTfgMtJpZ9l4lR1DNbPan8gMONDwTGHyEbMEnlqmAyDTtAu/d/ uLttOll4YV9yuftTDx6Qk9ZZQYsPZZN2uC7UoR2S3cs+iZyu25jkFa2nXb5Ru3aTRHH+ cb5hYk27JKMpbB7FpCoTO2TVtIeq/pj+zm6mF0FDkcRdLUTWWdrqTcxJiWgbnmMsh5Th +hO0LxUWhpWC8YIXXJG10dCAcczOuYvy0qzs4MayMnkhFQ/P3+ND/2ilTgb76cQ26uTC wFTA== X-Gm-Message-State: AOAM5324vJp92xJnHwDqiU1wEttd0QOh9HY39e+nJ8Guow7CLSgy5Gf+ 8yjkhMkVDvQdkdR7jAiQ/i6pFi0wSds= X-Google-Smtp-Source: ABdhPJwD1OCVKT1roLbHFzj0Uxr9BeEDwOsbHK0PDl00kSQH5HE2bIuPtqzK/El8Cgzk6aKU0of+lg== X-Received: by 2002:a5d:4f8a:: with SMTP id d10mr252000wru.219.1610049697548; Thu, 07 Jan 2021 12:01:37 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z3sm10610777wrn.59.2021.01.07.12.01.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:37 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:18 +0000 Subject: [PATCH 09/18] 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 20:01:19 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004701 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 0A7F6C433E6 for ; Thu, 7 Jan 2021 20:02:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D1A2423447 for ; Thu, 7 Jan 2021 20:02:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727004AbhAGUCB (ORCPT ); Thu, 7 Jan 2021 15:02:01 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51750 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726064AbhAGUCB (ORCPT ); Thu, 7 Jan 2021 15:02:01 -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 D7F28C061282 for ; Thu, 7 Jan 2021 12:01:39 -0800 (PST) Received: by mail-wr1-x42c.google.com with SMTP id r3so6848363wrt.2 for ; Thu, 07 Jan 2021 12:01:39 -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=NcGbF/Teqc16f+dDkiUXnywawOTCa8LMa92cFHacyB5KXmhfACxUBGjqngLviEEIQW Db3/tCsE2nepoTXI9RnSbiEt9xXRci0JM5ozkErphIO1MFm1/90UHbVkt27BqBrqPgSn cjVfYMQ3Gf9WqT3GUFmixNKfySlSh2vK0SPAmrQhmidvUf2PuFXMMAH3ojYjHlQF605O iRFBHKpiusak97yqr28BYEz1bPDsNOtIicVYWph6fEuUI4DZyp+Ijqky4QU+Q/Lp3Izq Y5GHDcaBn6kC2Sv4zdl4uFmLJP1SiAhM0GfzpvlPfWSc0EPvAHOqD3Gifs3rVojbmrxG Ifvg== 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=KopSlqHE4bgg2+tkOjEj1g0aqydhoQHhAKG6O7tFCBZhvdm3rgESAILB5aPNxUSsC+ +gVc2dzj3aO6z7rmSLXEQiRgL8RlED8wGDCZa9kvdQcEnVyUj2RkISVaB9fAdh6jJBIE 05PB77bkuCGIHelQhqGtlCRZiTs0XMPnTLfBTqgTWWRQprOJXNYoYiC/8CMOuAJQMo3h beqDqmupZTqVnjjAM1GKHxvYkQh/OKAd4jEwEQAn1aJ6PmvUFZQZdDMfpA3MFklVvM8F 9TVgX+Gsrcy8gO0EE60hep4lONlK5x3LNDQox7P6DU+KDV+JBjaJv1Iuns12ut2KMeSH XmDg== X-Gm-Message-State: AOAM530Zu0FyOtsUwmn6mM5bU239J3tnMJLKmruvzzsrlbAtcXa9qhvo werU9XFteCTFNiF68EiBX3leE3+k6Y8= X-Google-Smtp-Source: ABdhPJwgG/iAaWKSh2iaRz6VYgoV/XxBfu8MRAteS9fBrhB8TdsuZ1QBf+COvIFSDucqN3BfvAUeaw== X-Received: by 2002:adf:fb85:: with SMTP id a5mr249460wrr.331.1610049698415; Thu, 07 Jan 2021 12:01:38 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id u66sm9171233wmg.30.2021.01.07.12.01.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:37 -0800 (PST) Message-Id: <9a06c698857d4067ea34f9ae9dd610b999b907b8.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:19 +0000 Subject: [PATCH 10/18] 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 20:01:20 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004733 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 ED646C433E9 for ; Thu, 7 Jan 2021 20:02:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C6F9823444 for ; Thu, 7 Jan 2021 20:02:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728131AbhAGUC1 (ORCPT ); Thu, 7 Jan 2021 15:02:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51914 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727903AbhAGUC0 (ORCPT ); Thu, 7 Jan 2021 15:02:26 -0500 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B548BC061285 for ; Thu, 7 Jan 2021 12:01:40 -0800 (PST) Received: by mail-wr1-x429.google.com with SMTP id d26so6792430wrb.12 for ; Thu, 07 Jan 2021 12:01:40 -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=PnmUtrZ7W67oKK9aEmou2nLoZuNXc6Eu2XC85R9QeUHI9f6vg/PtlBNaMsGIyKlFZY Uahl5v8BaLxLCbddinTQi2uT+tSmjoxgu3I2q3ei8aixkDylqTEf+S38fpvZ1n48B5C6 3CWCAmTljwqDLf+wA7uZRGie9LMKAybMYEjlaBJ0keoifZuZvktxL4r2KfVFnMjB4vUk 9SQtR3Kubx2eTEDw73/Ua2BLEfEe8n4YE2zxc+bH4U61JCs/B2zzX8Y0q0srVvIv8S2g SyFkW4fk5QlwReei7M+DlfFpW8wQi6Gl8cF28zsZ5Y2NuuI903Fv250or+RTFQGVuTfW 8TKg== 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=WTLwLkc9JD3nLEXrsqZT8lBKrl2WO8DFWwV4CslWhKCB0/zzujfQybwxYLaTXRHOMa JP9h6Xd8Q6X27teawRw7BdIgHkaR4r0CfGJAbEiakKagW4CDC/LKF2QUac52IE0uLv5d lGo43+XkaipJAu5Bgxf92wm8RtZG74dS0Rf84foVc5Ls7wgijdFGcVJ+hqAptXyXSDRZ ImJiSck4bmmkXsIF5/rEY5nrpDtHPhZT5hKEcNlDoxqIP8Of0eB4kskHbPAP+7IC+3b7 UlV8RZVZi9UoYSRISRsKSDxQRJ7t6pmOCQGxsJbyyYDPgVnhftBmWYT/y7Nd67v1iXCY iu8w== X-Gm-Message-State: AOAM531aHlo87tXwu8x+25GWrA1GP+W+0dYCjQaRMETm2cUiam/Z2vTE z+hq/2GJXHv3C9BbzH7kB0Sh3SByHeQ= X-Google-Smtp-Source: ABdhPJwc5FBX90jkVwJYgAwVtutuFl6P32uhxQ/iCq23HCr4p83MYw5Db//ojxkm0spnpD+T1LswNg== X-Received: by 2002:adf:fd0c:: with SMTP id e12mr269906wrr.61.1610049699351; Thu, 07 Jan 2021 12:01:39 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id b127sm10674216wmc.45.2021.01.07.12.01.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:38 -0800 (PST) Message-Id: <2ffb93c37ac7e9ca8697a43c41d618d987db4f47.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:20 +0000 Subject: [PATCH 11/18] 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 20:01:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004705 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 E66D2C433E0 for ; Thu, 7 Jan 2021 20:02:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A633223447 for ; Thu, 7 Jan 2021 20:02:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727164AbhAGUCJ (ORCPT ); Thu, 7 Jan 2021 15:02:09 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51848 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726064AbhAGUCJ (ORCPT ); Thu, 7 Jan 2021 15:02:09 -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 CF54BC061290 for ; Thu, 7 Jan 2021 12:01:41 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id 91so6832419wrj.7 for ; Thu, 07 Jan 2021 12:01:41 -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=YxL2XM8hYzrPB7Sg9jKT477f3lblKLZK2vDEz9W9Y4Fk6O+NFqKjC9QjUv4kS0Qm6t oU9xq/AhlI+uKRTCbX4IZ8wLTCAPdfwfDiIyEtqwqR7zBlZRDl9FDOX/aJIg0FKLC6mj wEmf0mpSfo8xiozkUFa7y8mi2XvwAO0kzXFEOxMbI4fiVeCutCRHO/19wGttcyyRCK/b v0WKkMYnNnRp0icMkKFL9BOtlGOwkOyzt86NqUf5dtuHVqXiU3zdf9k3POSbTJ5S3ejJ rgMvRnqv0WNuYuGPfjcLB+/VwqNZ4NJROfAKDiZdGI6tDLnPgkmoVEgMtNL5m5NmCGxq Babg== 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=Z4vCGP7skNDC+Hfrr/XxXUySqbc+NpqebAl43QY+/WPZ/M2lp7kH0KNCy2suFZGZHs eLJ6fK7MajjEW24u3lcICHNhQJCchuXGGhc7BT7T2YjEXpkX6EGaqbwTSCMP+kp8ieKr j34saySB7kUiyuF+d2VPdV5TOHMgpdltXGd99I2JKI2eC8Qt9mL1sEZvfoUhDmUiiVe1 J8/ORf59RB3lyNJl4TLn/zoQTXQ1buK4wsRgpeR6UQ88Io9iaT3mTERlF/VYj30CUHzK OBlfEc+U1ZFCXBwbA+ODpRCMxsjdxLilY8svoZJyBt6PwILNEWAbT2GNiEopji06ESmc rWtw== X-Gm-Message-State: AOAM532n1Ap4ObJidGK5qkrl0fmE1J41O4aBvz9IP7wvXXofId/8IdMk 63k16nx1Ku3lBfkjI5DPEtWTmrqqHJQ= X-Google-Smtp-Source: ABdhPJz8YM0q6/4VA4xH1dQYfM7lZKSTuwADABYQb4PO8EkM1J1q9wP6OZT36pa17V57huzk35Z7Xw== X-Received: by 2002:adf:bb0e:: with SMTP id r14mr271826wrg.159.1610049700379; Thu, 07 Jan 2021 12:01:40 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l7sm8952840wme.4.2021.01.07.12.01.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:39 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:21 +0000 Subject: [PATCH 12/18] 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 20:01:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004737 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,URIBL_BLOCKED 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 29634C433E6 for ; Thu, 7 Jan 2021 20:02:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E92C323444 for ; Thu, 7 Jan 2021 20:02:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728163AbhAGUCf (ORCPT ); Thu, 7 Jan 2021 15:02:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51936 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727217AbhAGUCe (ORCPT ); Thu, 7 Jan 2021 15:02:34 -0500 Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B40AEC0612A0 for ; Thu, 7 Jan 2021 12:01:42 -0800 (PST) Received: by mail-wm1-x330.google.com with SMTP id e25so6594670wme.0 for ; Thu, 07 Jan 2021 12:01:42 -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=ubNtddEjK2pswsc3+eg/OxjO+Zr5V80dfMG4rzuKMwOGuwciGMECjljZyq/NLZyHRy snD/NTY4ZI0P6ZLJxCPZ3WuGKKZL9qgta92VjyjoA6dbSSLqpURWE96diHUzpUtxluLw 9fRlR7NACpxarneB0S+9x1s+Kuq0XkKEJppVdpySlljo45H5iyrzAddBW5lGGoKQMnD8 K2wT9zWJgo/ZMgwp5JF3Pr1DQtY0eNa/obeWhNnFYabERFkv/25AFTub8BnO9MJLhtn6 xiELr0vF6AjSp9Kz/U3dplkgQoWI3ZOepR2R20l+RBr9boRimWoCkSHPqciSn5KUSWzp WFyw== 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=r7pQ5pbsbKISUBHW1ZWcoUlRLAOzhxpvBt60fPb1uP81sehgywbYWz7PoSzGD7iaJ5 2dMxvSujF4EdpEFi/69DafNAspMLjhIuDa4SUDa8Thytl4tXfuTrgBFGirPp300kmB4Y sEN4890PGQE1GIBh5JzRmPLrTQmTpqk5wbL3fAeIJsczSQN2up14fOp21j156M3m4KvQ SVs8e7iYpJWLvqAsAaUA3RZbQFTRc7Xe95N2hD2lhhr0C0WOPUtYBusFAmhUMzTVTccc AXIVCOG5AiUNQO+/ASqiw9pmNiihiWO+zU/KuX2b3cRFCf2HKxyLDvIS9b6bwmV0/cDi c40g== X-Gm-Message-State: AOAM533JEzyNArcBfhYjQy/Uu+oZCx1BNBVR6kAuTMsF7gOggeBmZvA9 kz536PgwmvZSu0p7wOoIWlw7M/Vvh+w= X-Google-Smtp-Source: ABdhPJzx3AX8AhGbUgMJdHoy7qk776TVlujIYW0gk+uEtq7lNkwzal28NJRsKMWmSzafCaA3+zO+BQ== X-Received: by 2002:a1c:ac86:: with SMTP id v128mr177763wme.76.1610049701269; Thu, 07 Jan 2021 12:01:41 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id v65sm4747483wme.23.2021.01.07.12.01.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:40 -0800 (PST) Message-Id: <734891cb3153f9e1982721257b766ed9c10b9676.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:22 +0000 Subject: [PATCH 13/18] 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 20:01:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004713 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 39271C433E6 for ; Thu, 7 Jan 2021 20:02:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EF9EB23444 for ; Thu, 7 Jan 2021 20:02:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726961AbhAGUCT (ORCPT ); Thu, 7 Jan 2021 15:02:19 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51750 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727833AbhAGUCR (ORCPT ); Thu, 7 Jan 2021 15:02:17 -0500 Received: from mail-wm1-x32e.google.com (mail-wm1-x32e.google.com [IPv6:2a00:1450:4864:20::32e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 99BBAC0612A1 for ; Thu, 7 Jan 2021 12:01:43 -0800 (PST) Received: by mail-wm1-x32e.google.com with SMTP id y23so6579099wmi.1 for ; Thu, 07 Jan 2021 12:01:43 -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=jhYRmY/syqj36Z6Pg3EPgp87yIVQ7A+nOezf0PPq/2EriFTAfk61aNPA2A/kHq8JS1 wyvlMYv56p//Te3N4Zpy/cTcIvdh1kCrNyPVDnUfnKSiQ5TfH8tfIkNnx0Myy/wFVH2+ 9FvTA+msihX2E8S0gNlYx7eT/HOqyruUw+YWiWit15PMriQfK6er9U3sxMU1Btu6WLqx Y7nbyEts8+lEtd+4PS0KCklAPsw9eA64IrTbJq+jNOf0XNL12MlprV3Fpx4h5BLh6JPW iSeW0aeXT0YgZ1ZpuwCG++y0XwKYJrtZDbOVRdiILk7TzQ0Zknm1BKgC/f7NFPTBE5oY RpsA== 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=aYTcw2JmP8Oso8Es2kl6Wj8v58PhESjG3U1S273EbMqkSXV2ZYDLtzbgL13Vca2bqh Sy61N0IprAVkzjoU0ProrwzgkiExrurJGCJlTRfuufHxuK3qJKOry5TyvlY6/tFY4VD9 9lz6yWVLX7xxKEgkhP7W7dq+og40/RuyMoFnNLimCSrkEafhdN5fuVRHz373SZ8YQJWT /2jMbCHbQLxtONxHuz+utMfTLB7EWOmX632OnOJls3LqOlqNiScIH4Et/BZlB1HiQaH0 1mJc5XzY7MaaPujiJzbrf6kzWuItJWfk30zCM7958JI45RktQMLt2Bzmswqj8wrIc1Q4 6MRQ== X-Gm-Message-State: AOAM533kgMneIiREioIQE8jMxvhxHSaI+Lht01mr5+iZchMOJzAuxZyD lQPSeaf/zyZCJ6+VNjRYT+EDMLH3XQ0= X-Google-Smtp-Source: ABdhPJy2t+ZwJmXiXtIQi0LVpLgPtf3IjFe6d6k0Q6zSdtD4j38xTRT/QeF38EqJzelF+8OrqrZCbA== X-Received: by 2002:a1c:24c4:: with SMTP id k187mr193858wmk.14.1610049702199; Thu, 07 Jan 2021 12:01:42 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l1sm10008383wrq.64.2021.01.07.12.01.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:41 -0800 (PST) Message-Id: <4b912f2c0251b7d19ba74f0af5563605f6ad9667.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:23 +0000 Subject: [PATCH 14/18] 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 20:01:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004739 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 8DA86C433DB for ; Thu, 7 Jan 2021 20:02:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 592CB233EA for ; Thu, 7 Jan 2021 20:02:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727263AbhAGUCm (ORCPT ); Thu, 7 Jan 2021 15:02:42 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51954 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726805AbhAGUCl (ORCPT ); Thu, 7 Jan 2021 15:02:41 -0500 Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com [IPv6:2a00:1450:4864:20::32a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 942A0C0612A2 for ; Thu, 7 Jan 2021 12:01:44 -0800 (PST) Received: by mail-wm1-x32a.google.com with SMTP id a6so6119038wmc.2 for ; Thu, 07 Jan 2021 12:01:44 -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=B2wpXdsItMJkalfd8XfJWwcVWq1IiMNwh4S8taP6mShe1+wCq/B19vNBgNn3+ZNVLd 7m4EKvX45R3sRchfs8Bh2oxnJ4lGSpdB84/UOSfX7BWI3kzv7+nxK388F9zkcCWYfZvr Xq3x9+VCbnpfrtTITCX+p6ifcAYDlqQ6LyNhrfXnInZx4u0wOlwQPe35wZaz2BxM+/8N sOT7yQS2s0qXTKAx/4CKJbX1XnBz8B3SFSFWue+0rZkw/Q7Lvy6F4HXI8jHICaMdIVMp epJSOOHfD9oAPIACFuR1QAvXutj4SnFAtPqnOu10ovX69gS0YRoAH7Tv/T2v7EkTDcN1 I5TQ== 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=USnx/biW19bj9A4Uy/6G09IFwbnPErjkDFvrFxdLKRYPmGBf10jLeqFMK64JN7F0Cc 4wREbRfCoWbflYfB2kmFtydGrsPoImRrHrT7FK8GOz9loZ1YdneTlPiVkqclmnXayxZq JnA7rSsF7mE7EDa3wOoLSv6uKUpmTKuLw4Z3DoCKanCCJUUzSd8/lcsVTlClHMXdXZIl 8xwmiMYWI2TOn7uLnN+lR/taUu7lRS966CIEg5qujn1liFXAI+1LrC/AU628BCfyDHlq xfS2SIcxaUMYabBMjizd9qFg7kFGs/kVUb67modktob8dAtpLaXO9lTH00L0S3Gm3n/F X3oA== X-Gm-Message-State: AOAM530KlWL4wkL7mgrYc8BOKxycVeFVBweRfTHd31KkR9DXH/J6eNf7 9UTwQQmK0Al38EnXTzjlZzMp6eU6dSY= X-Google-Smtp-Source: ABdhPJwaWny1UaJYiGKGQlk2J/bFHi1nO6/XG1w6PkUxcnvLWJ3nUl50oLQ8DRA3e0xSSqPmREMJOQ== X-Received: by 2002:a1c:b657:: with SMTP id g84mr141167wmf.181.1610049703036; Thu, 07 Jan 2021 12:01:43 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id n16sm9814164wrj.26.2021.01.07.12.01.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:42 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:24 +0000 Subject: [PATCH 15/18] 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 20:01:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004731 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 4AB34C433DB for ; Thu, 7 Jan 2021 20:02:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2007723444 for ; Thu, 7 Jan 2021 20:02:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728113AbhAGUC0 (ORCPT ); Thu, 7 Jan 2021 15:02:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51848 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727183AbhAGUCY (ORCPT ); Thu, 7 Jan 2021 15:02:24 -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 63FC8C0612A3 for ; Thu, 7 Jan 2021 12:01:45 -0800 (PST) Received: by mail-wr1-x431.google.com with SMTP id d13so6773670wrc.13 for ; Thu, 07 Jan 2021 12:01:45 -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=KSauYskfzhP6kXK24rjwbyL78H3L6b1k+XwF/YmwKMMo4oVrgSxalGQziehupIubaL WrOTJJ3lz/ZidtApwjm1PeD+c7VCFZFsC0AM5z80adTkaZQEHlKIPcjHiVNFrgCL7ypn tgJnkBiNQpqb1MQTPdPNp+CVU9LYhdNVjDM7C8NRuRvpyzTJ+ZIuVFx++ViacV56ZTW/ oe36GvxR0QhTmDjLLumGmvoYLOBdlwAzsuvpXwo+heZfhbJodrsNdBYcDRkJGIa2EJZK +At97cff9VQziBr5Oqhrzuf7FeIrIPJS+foDX0XGEeTwfW4hVFkObSupL85lhO0atkWY wvhA== 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=UclN2TTlTjyM1WkCU4/iqSfZedkg9Q9ody84vjEJ61D1DzqnNDy72reEUPglVOBZmD 6V+og76wNt3Q2yLKmPavzlg1dfbsiKQLHYehGvCiRQGUvvETHxjjpAy4GIYRPk8cVC0z Lb7eZjjW1OLnT7HTX7ogHZSU416yV8lleTkRzSuFlGMAtr4BVZyPXQVH64RTE9GTj1Vp XEu6kFfXr61q4g87mu02bb1etVqjNScZkOtv6D4mahI2nC89/hlQ3AP1e2BSONZABqtW KoLPHdHXUtzDpBJ5Cuq69r0Yo0RwJr4m3ViyuueQlmII+bPQoYXFlHQhyq2scL0WyCnR bGDg== X-Gm-Message-State: AOAM531AGg8c8K72v3uwgbgpekgXPJIiiDBno5d7GBlDHaaWopAfgZuP r8OHZZqq9MB51M/svL5idaBuobC0V7I= X-Google-Smtp-Source: ABdhPJwgX+P13QglD785DNlpDICXzWeRf71iUdoyrsmBfRsWcaFWBpOfldpRqI9m9yq9YQWx2ZQ5Pw== X-Received: by 2002:a5d:4e86:: with SMTP id e6mr277624wru.33.1610049704012; Thu, 07 Jan 2021 12:01:44 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j59sm10544787wrj.13.2021.01.07.12.01.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:43 -0800 (PST) Message-Id: <11e45af831d14296c6a78441e423aba315c8f76b.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:25 +0000 Subject: [PATCH 16/18] 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 20:01:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004741 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 CCB26C433E6 for ; Thu, 7 Jan 2021 20:02:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9EA96233EE for ; Thu, 7 Jan 2021 20:02:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725835AbhAGUCu (ORCPT ); Thu, 7 Jan 2021 15:02:50 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51976 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726805AbhAGUCt (ORCPT ); Thu, 7 Jan 2021 15:02:49 -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 805A3C0612F5 for ; Thu, 7 Jan 2021 12:01:46 -0800 (PST) Received: by mail-wr1-x42b.google.com with SMTP id w5so6791523wrm.11 for ; Thu, 07 Jan 2021 12:01:46 -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=dPGFxvgaWi9iD2ards8gb7YZWc75e109esj98jNPdkjPdzlbYw7X8YcXfM/QB09qdG R/fjStVN40dQoD+SSArDehQNLnleRPkHlTkhmIUTUW8B2bYyRoQW7Pi8xa1+kufKBwcf LCgMm4pF8Ao77IEvazIMnlIXwcuxkORB1RvXRBbmuoKqR4vIy1DkKnT6H1rWCaxma6vn shFDwxpIikavg8dU1SxBPazS4dSZJnaaDN+oWdL1fdhDkP87AAev3NKgdriFdlSe/aBb Hu3adXMWQZp7ZAq5cLI2eHJjB6CuCxN5e/D1JyPz9wBbqLFxh1Kqjj3EnE/Rwv+nsdWP P0Sg== 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=aCAuclasVBnLycUIw+D9aGF+5vgO1xA5dboyBY2i7aXkyGrxbqQ1t99R5x6QRfVZ8L DlX2AN1RMMyG75kKqSEkyUBeqFiX62PXjFk/NrlwwoXyZ+9Tc2U9NR5a5tQhVmMH+LLn qoHJcBK2rDGADyNsO61dgesDoUll3IFaYd4lZWr6fDNhLMTClryZHGRuy4WxbUM7gdka p9V9djw1zFezsweoHTGDovXM+5D9Co07+wAJ8owmA8LEdBNApS8pm1xby0VkplK5tokd vFTuU6DSx22R5bieSAS0i96gqnsPvUFzC8JysQGs7Qbgxm1b5DI+Bj9yVpzVMr3Xsbd2 AQBA== X-Gm-Message-State: AOAM530rLZQYj16RU0zBFHpjPaboHQAQFqbeWRSx8weK4XaZyz1hrPVf Cib/gW+/lHWQKjx6shUPI4dblSDKavc= X-Google-Smtp-Source: ABdhPJxSBU/NyK0eKROWxu+KNKVy664dph3nDiRMJoG9Uw5pAHSUyT2qZ8CxbWJoKeeL8X/QmBWc7A== X-Received: by 2002:a5d:54cc:: with SMTP id x12mr302626wrv.132.1610049704942; Thu, 07 Jan 2021 12:01:44 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l8sm10578903wrb.73.2021.01.07.12.01.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:44 -0800 (PST) Message-Id: <551878bd84da895e0899eba620553f6efe60e100.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:26 +0000 Subject: [PATCH 17/18] 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); } } From patchwork Thu Jan 7 20:01:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12004735 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 4D8A0C433E0 for ; Thu, 7 Jan 2021 20:02:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0DAAF23444 for ; Thu, 7 Jan 2021 20:02:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728144AbhAGUC3 (ORCPT ); Thu, 7 Jan 2021 15:02:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51862 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727903AbhAGUC2 (ORCPT ); Thu, 7 Jan 2021 15:02:28 -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 59C76C0612A4 for ; Thu, 7 Jan 2021 12:01:47 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id q75so6581185wme.2 for ; Thu, 07 Jan 2021 12:01:47 -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=nAuK0icYeCv6YS0QrluSPaIZD6FjfdByI7t/kR1s2e0=; b=O7RL340E+h2QThQPBG0Him3tp0CXHTktL3+aB5WoKL6UKf2l2m4MFEhdhY9t2wpEQY PrpOHs/iiuvqJAXtKpfcEA3tEuDi4BplIyXvbzVBclu0rn4kkwhmsxo6lVK5DmIbPdKS cXwdLwlv/5ljVk43gYRCWD7yIJPuFqMTl7yWtQbMXA1lxzIwW4X8I/HVbK6QSdyJaN6A ZSLBJyGkzIZIacJSBcUME82jntLsd0GSD1Zw2uFrlag4tDrb3LHJ+FPN46dVC4T8QawY vnKUV7U1C+oPrjOtbhi0xRzL8+YRXXPz+mIxfV6RLjL49961WyZJBWzfFrjGLp/U8eb3 0q2w== 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=nAuK0icYeCv6YS0QrluSPaIZD6FjfdByI7t/kR1s2e0=; b=sV33vO22Drb5fQHmGO/4BQvK4dvfbit8Vv7w9dHpw5BVuHDgo3QAsSGCUOX3Q+fzAB 5YV5RlWiFPX7j6qu/CmiAuoDbQM1/lf+hWusje1qWU89X3BhOAnezTXGuw5t/Kvu12QQ W3K7YAR+z/QBCgyOB+hzjuvD71XoEVwN23w6EysqlWApP6lWHxKwvrjpa85e1F6pRFLt fK1BU93M51E4Ml8DC39Gd8rCimK/iNjOAyY4O7AqqbMzZr5Ea1zMLWI8WBUumGNiTdYY eBOLPQA8HfLMWLUuMeJhlxdSQ3smHnyPFo906U5B9mIKK0mfnv8LTT9svA36mfTaAz5K jWPQ== X-Gm-Message-State: AOAM5335xUf/zJsBNqwLwfhy7U1paEVCrMlEkgWL2aenobJiWbzwzWyQ z2GuZnxjBJFOiPndjeYAy/DqKk3sUDQ= X-Google-Smtp-Source: ABdhPJyYKD/+jaNC8xy7ZX+7RIEZuqBjEWMKcO8owRteh5k1hVc/7r1kfh0XnrlwS5h4cWA9KzB4XQ== X-Received: by 2002:a1c:3c09:: with SMTP id j9mr166579wma.180.1610049705962; Thu, 07 Jan 2021 12:01:45 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s13sm10181608wra.53.2021.01.07.12.01.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 12:01:45 -0800 (PST) Message-Id: <786dc8f0c449958174a4cf5e98704d36f3ae4076.1610049687.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 20:01:27 +0000 Subject: [PATCH 18/18] DO NOT SUBMIT: directory rename stuff for redo_after_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 I believe the ci->dirmask & sidemask stuff was leftovers from before I added dirs_removed. I think it's dead, useless code; just need to check. Also, the !mi || mi->clean portions should only be triggerable once I do the redo_after_renames stuff. Signed-off-by: Elijah Newren --- merge-ort.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 55a835f8b97..1eb3a2e0fbb 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1031,6 +1031,48 @@ static void get_provisional_directory_renames(struct merge_options *opt, } } +static void remove_invalid_dir_renames(struct merge_options *opt, + struct strmap *side_dir_renames, + unsigned side_mask) +{ + struct hashmap_iter iter; + struct strmap_entry *entry; + struct string_list removable = STRING_LIST_INIT_NODUP; + int i; + + strmap_for_each_entry(side_dir_renames, &iter, entry) { + struct merged_info *mi; + struct conflict_info *ci; + + mi = strmap_get(&opt->priv->paths, entry->key); + INITIALIZE_CI(ci, mi); + if (!mi || + mi->clean || + (ci->dirmask & side_mask)) { + /* + * !mi: This rename came from a directory that was + * unchanged on the other side of history, and NULL on + * our side. No directory rename detection needed. + * + * mi->clean: Due to redo_after_renames, on the second + * run, collect_merge_info_callback was able to + * cleanly resolve the trivial directory merge without + * recursing. As such, we know we don't need + * directory rename detection for it. + * + * ci->dirmask & side_mask: this directory "rename" + * isn't valid because the source directory name still + * exists on the destination side. + */ + string_list_append(&removable, entry->key); + } + } + + for (i=0; i