From patchwork Tue Jan 19 19:53:37 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030671 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 5278BC43381 for ; Tue, 19 Jan 2021 20:00:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 19EE72310B for ; Tue, 19 Jan 2021 20:00:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730064AbhASTyn (ORCPT ); Tue, 19 Jan 2021 14:54:43 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38204 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728987AbhASTyh (ORCPT ); Tue, 19 Jan 2021 14:54:37 -0500 Received: from mail-wm1-x336.google.com (mail-wm1-x336.google.com [IPv6:2a00:1450:4864:20::336]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 45B5FC061575 for ; Tue, 19 Jan 2021 11:53:57 -0800 (PST) Received: by mail-wm1-x336.google.com with SMTP id 190so890401wmz.0 for ; Tue, 19 Jan 2021 11:53:57 -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=fE8JwkdnhqtPkfMetcZosnfNX5/o4RA/xJU5IgmaJXMetjDfiHnVQfdCbMz+a2v8Gw WysbpIyiibIhBdobJ5FAtZ+Bm0ZAzhzLrlxcIWyNQJztXnv6qNpq6fXTV6An2aYJTz9C VuJW7zm54x4yX0kkNMrz/Ber8rDSbzjNI1RHj40dw4XIXlmnavVxgm0pQfxiMW+1I0wf p28mPaJcwlNXkMQXSMw007W0CtM4v/RmWUJisyjKkRZN+lWToNXBXtsKiD3WXoRcbkBQ PsVXxNykIyTArsxrL5wEgzs+rVRYva3GjpUKQStKvpz4ZUrAbUtGogxy9rs4M9HuALQA WIqA== 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=epn4fkaMf4vPD+EQUgJR5s3Jc/wUP4h6hut2HbhKioJ/pNkMYLGkpCDhKTOL0HBqpD nylz3Hl9thTcdVYhseyZq1/3NwTWRn62d7Oj8QxH0verVo16sFRKCtS4AQkqd0h/7P1V yLnTb/N3TgbDs10jczx3C9sHh93+2B0kBP96cr6KZXEHzXwmcohjUN4HVgDjkRiBQnSw IxGOpDVJnW3iVci3YTw8X4uY23nN6BLBPs7sxdx6tT4GRMWtAhtaCYvF199Wbu1zhd/9 cbZtsKiZBMxu5k8A1wiKYX1OuhF4h3kVl2phA78IKh+mAL21UtEkax78dDmi2IC15iHV CZBw== X-Gm-Message-State: AOAM533Pc9fWNbINsoKrSQiHfjUjyGhhoFz7MZBRmnwsNYH5PYPRx+Qd 7k9ZMQwTJkmn+4HY4fmWnaJUKo+me1k= X-Google-Smtp-Source: ABdhPJwu0Q534Bxgnt/GhjsKZ1WDuRhcsCKM3YlxE5305OS36D7A9j8zQvmYunHJ9JuUARvciytbBA== X-Received: by 2002:a1c:7dc4:: with SMTP id y187mr1161994wmc.42.1611086035821; Tue, 19 Jan 2021 11:53:55 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h187sm6356180wmf.30.2021.01.19.11.53.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:55 -0800 (PST) Message-Id: <3b14afd4129f19ecb581025a94cc816a5f2ff28b.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:37 +0000 Subject: [PATCH v3 01/17] merge-ort: add new data structures for directory rename detection Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 Tue Jan 19 19:53:38 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030629 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 F31F8C433DB for ; Tue, 19 Jan 2021 19:55:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9CA7C2310D for ; Tue, 19 Jan 2021 19:55:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391807AbhASTyt (ORCPT ); Tue, 19 Jan 2021 14:54:49 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38210 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729609AbhASTyi (ORCPT ); Tue, 19 Jan 2021 14:54:38 -0500 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 223F2C061757 for ; Tue, 19 Jan 2021 11:53:58 -0800 (PST) Received: by mail-wm1-x32f.google.com with SMTP id m187so884937wme.2 for ; Tue, 19 Jan 2021 11:53:58 -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=ItIQfI+f5vMNPDap+5SgJ/p+V6BIdWWnLQRv7SNecpKe9/s6ZSKqUwB1b3gcyJt1vV V0WlbSABSA5zr7oJ9P0k+yUyCXDY5cgarwIv8RAtx8dLDIm8HHP30NcHNEr1aJe9R4u9 78dJCb4NH2Nw/1f2Frl/o0zfOC5QngLd/NNqtvWEBIM+wKOuzEhVMdJga40nNY8FncY/ 9/K9eQO/0ld/5Z2SVjdqwtFUZLOS6b4GtCxhYcZ6Bz81gWbT4jAft3Lq8jiSKzJ4PKHa 48RzUYdiIiUOoVU79ti5yxoxuTTz8BTMmGgy2409ZbfgqEcq889NWQepLuIFWMB0MGCv jMPQ== 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=o1XWrQzQ5UaoBVQqHo3pO4POf0n1Qs8C+KyUZBYJ706C1rY2CL4C4fefL2z34CZyJ6 ebj4mCUuA5BicpEQNy01vhrmsZRR1ezsRBZKHXTikW7D7SfcQ51i+hzkCBqtdzvTtEEe IUbSZoQd9jdyByeMMytKAIXeJYFdiQSRCYoxtzU2iMM9tMUFEHuJOJ14WNQPYu2fjZwg oWDF1jGuLp91lTVCTi3pgcF5qU15HhcmN6b58d0d26+dj1Pp1rM8loHr5ykY4AfG3gIs FHspkNOLX8l7KgAv7iG8fdlFuU74AbeWHiTcqZtWyp9hWWso0sulCk7hkoQSkq+6lwpL 8Btw== X-Gm-Message-State: AOAM5328KbHLNI47Rgo5ACKQjiqGSIuy00Yc/vSpSPRHaIUKCKEv/1sR 07h5zHhGsjerlkGp+a60IGZUKbc1QNc= X-Google-Smtp-Source: ABdhPJzT3T1dzhqWOUV6UCKp9/ZddVA3axsikttmGtKIRizbM3McAiAupygQeF2UuAQxTRA1DpUdbw== X-Received: by 2002:a1c:9dd5:: with SMTP id g204mr1101642wme.37.1611086036717; Tue, 19 Jan 2021 11:53:56 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w4sm5491726wmc.13.2021.01.19.11.53.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:56 -0800 (PST) Message-Id: <9da04816c3b712242d111b98ddc2558c91f44f2a.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:38 +0000 Subject: [PATCH v3 02/17] merge-ort: initialize and free new directory rename data structures Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 Tue Jan 19 19:53:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030631 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 E688AC433E0 for ; Tue, 19 Jan 2021 19:55:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9E13A23119 for ; Tue, 19 Jan 2021 19:55:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728435AbhASTzS (ORCPT ); Tue, 19 Jan 2021 14:55:18 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38214 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729969AbhASTyo (ORCPT ); Tue, 19 Jan 2021 14:54:44 -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 E48B8C0613C1 for ; Tue, 19 Jan 2021 11:53:58 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id v15so17273038wrx.4 for ; Tue, 19 Jan 2021 11:53:58 -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=ZxWHcVhMy4gwXNyUJD6CvxQrvf0XvbS0jvUXAByW9NcAB3+VUL0Urd5jdSAjQ/PKgy doFSKvIJVByaZbbCPjAIUMb7Wtfwbj2R+cUq8L8LBFiIbfHy8LgGkiM0f9Q2C4jXM+3W zdRzHT1zVsdIvPTqnCFxU81omCj5XiG/R9fZ08psMcAU2oaIc6bBnmXCM7Hx/IwkZl90 Zj7tl8h/GAKy2+/X+X42GHsJD0yFXXvU603xZVwShIFVdpvje8qEUta/7UOSlb8qVRyu jV6gcTIAWvYmtFCsjmIeG8fLYzu3vRzYuu1B6PrFMfRTcXeUmGFGtO+DS55KJltPZ6Pj Sfag== 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=NQdcbNVuNjzGK95BFwi0BxFxENbdJFWRicOoMjmh57tjTwHfgFpz7bR7UbWoWZo1HM EwjbNRA9gXCzVKMKvOvurKIdDDuWqVqsOIeTy5jdU3r5czhiTROwuJBPiGfELRfOVNLw DrWqUwG/aWWmPtqfkHathBV+tGZv9amoZGSNQyCdeeAVcRf+e2xY4jdwI2heiBx0qmMo 0Bg7QI3bT5g/JMm1mtizVGn6ApHO9ARGvS9xmHpb1wR9xmcjmBYA+HR+0WKVNQjA3vH1 l7rfCdm4zVN3WpeV8MI7TDO2yFY5wKGVGrC+UGlIhrLgFnqRLw4avF2pq3Lgr9nmv3aJ Lkdg== X-Gm-Message-State: AOAM532/OmAYvBS2oS6WDR84m4yDnVeCIEGXXYRm0drBiyUEJxE6Ra6W EgB1uGyZSSKnZYLmEV+WrmTWKsawyZs= X-Google-Smtp-Source: ABdhPJyuScaxJSB2zpfuqBbyDljLjZz53i7N7OIDKX97XMRcrlDh212kz59dMG21cFHoaV7HF7eNRg== X-Received: by 2002:adf:b781:: with SMTP id s1mr5978663wre.290.1611086037534; Tue, 19 Jan 2021 11:53:57 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 62sm6493030wmd.34.2021.01.19.11.53.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:57 -0800 (PST) Message-Id: <3061a6ae69c167e2548d42de85851dd21cd1159f.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:39 +0000 Subject: [PATCH v3 03/17] merge-ort: collect which directories are removed in dirs_removed Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 Tue Jan 19 19:53:40 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030635 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 F3F04C433DB for ; Tue, 19 Jan 2021 19:55:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A9D212310D for ; Tue, 19 Jan 2021 19:55:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2392150AbhASTzf (ORCPT ); Tue, 19 Jan 2021 14:55:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38298 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2391994AbhASTzD (ORCPT ); Tue, 19 Jan 2021 14:55:03 -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 BF229C0613CF for ; Tue, 19 Jan 2021 11:53:59 -0800 (PST) Received: by mail-wm1-x331.google.com with SMTP id v184so845913wma.1 for ; Tue, 19 Jan 2021 11:53:59 -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=md58dQnFiM7rZcqPW93M53qV0XBglYVk4a3l+cpgqL4=; b=QUGT1Z2oF7HgcYgAhphQ9KNPxmVS2RkGG2dGWpRNxGmlL0vw/ohlIgazMlJTlE7mDN 2ej0Yvel0jv2lwlqbATgLc5iIwkkUJBYQW8aQnqchK2RMBAxyHmDBQtiLsMb3ikd2E1W 3ffGYs2bBxaK8RbOkEx9Zw39gluty4n6405CQs57i2HwTLafBzPJPFJXj9M4HTyYgswW /JPjTD9NgOHiff75DPecTskxAMDYdRjoAM8TcZt4JrUY1UiEjIVlfIRqwfoEryzn0YTj xiMOs5tj4PSnXHslrGQV0+4m+yuqQ2lxTaXrCnuZHOyd+wB6KBBQBMRF7heTvUh7Gfg/ Sncw== 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=md58dQnFiM7rZcqPW93M53qV0XBglYVk4a3l+cpgqL4=; b=axAH1G95Ar6kE5lVE5KJc19iPVHNWGUPoxQsNYj5ikFvifswOGAtOYigFWdJ/fQvTm PuNfYcZngWdVyJdKjQWVacmBQW3KaHXj0MkJkrlCnDAz5+f8O+nxqmNh72i+nL94S60t lRN1vSkOkvXTJUYNJL0U3RyeMwdY9eoPIYGRaDB65orblZSRIEX2FZBChZFpJq4H9e3S 58jpXdAyWZL8w6ngl7g/JpYZFH+4cj1Xk0+fq2RmQpOzbb4PMrj8Mn+TrsnJ2aoIJ262 h7wiFp4sJeK9IfJp4Llkoi+tsYQpZ/4jVPJqwSHxk+VL6ontQ7BmVX1qfbFG35dWsKJo 6uSg== X-Gm-Message-State: AOAM5302wxqarw83nqymuj6PFE5iTrGuBoS4ROkjbNhfYRK4M8DxDlPO wOqIjo9n1Z7jHUVIsiUxZiYKjYiSvaM= X-Google-Smtp-Source: ABdhPJwOA3k4Oat1x20rPauxcs3VC2jN0I8/LHVY8qQM9NifDp6EAkLgst8hIPNSQvndLAXPw3UopA== X-Received: by 2002:a05:600c:19cb:: with SMTP id u11mr1127630wmq.110.1611086038386; Tue, 19 Jan 2021 11:53:58 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id g192sm6520327wmg.18.2021.01.19.11.53.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:57 -0800 (PST) Message-Id: <0dd6e83d2b019d5663dd842405cee1b3bcfd1902.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:40 +0000 Subject: [PATCH v3 04/17] merge-ort: add outline for computing directory renames Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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..b4c1fe28a5c 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) { + get_provisional_directory_renames(opt, MERGE_SIDE1, &clean); + get_provisional_directory_renames(opt, MERGE_SIDE2, &clean); + handle_directory_level_conflicts(opt); + } + ALLOC_GROW(combined.queue, renames->pairs[1].nr + renames->pairs[2].nr, combined.alloc); From patchwork Tue Jan 19 19:53:41 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030637 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 1DC4DC433DB for ; Tue, 19 Jan 2021 19:56:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C55A623110 for ; Tue, 19 Jan 2021 19:56:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2392234AbhASTzy (ORCPT ); Tue, 19 Jan 2021 14:55:54 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38300 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392020AbhASTzD (ORCPT ); Tue, 19 Jan 2021 14:55:03 -0500 Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 90E77C0613D3 for ; Tue, 19 Jan 2021 11:54:00 -0800 (PST) Received: by mail-wr1-x42a.google.com with SMTP id w5so20899107wrm.11 for ; Tue, 19 Jan 2021 11:54:00 -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=BvTRjOzh3Pg8M4PKYrxaJ5Hkk6dQATHE8vqGsjvL+C0=; b=ZnIumjkNkgeovotm8rkHC1FxtvFY7gW/uAd7cmIAcL9WKK4ombEOomEkontBjR96xP R8A7iglIMg3aT99uPBon/UxREpt32cPFIXOarUwOVP9RssFce1fDtKk7t7n3JGIqV8Eg 9KXkyLS+IN/CLpZl20lhcgiR2sNuX2hzuigWMdB3fNz5W7LhROwQvYrKkxVuQt10grOI o+hMhYiYYw7F2SO7Pr1BceDgL+Hub4D0rr4nikPMmZUG0fOw2Q11+TA2CLim28nBNLXZ pZw1pBTE7GzWqgcyS6V8oTyxnT6wi61AxnvKagQrh7YkUXrcYZ6ISrFg3HJhjI5j8KnV YYOQ== 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=BvTRjOzh3Pg8M4PKYrxaJ5Hkk6dQATHE8vqGsjvL+C0=; b=CnBjNYgGGW/JAC/K5dS0ZbxS4iioPXJQPo4dmNikLunKB20F6EJXdoVNdp0STov4bY FqfkZrD+O1+ypHdzksK+S4pbHwqxdf5dvN+WbVJYeyrpDI2pA4DIFUJBoJaq+oMUyApU xQkgROXT+UoDW+kKHcdill7CGJ7nk85OMWKs3oezGk8EdCywXa3a2UsZf/gVqTL6AYa7 hfYy8yguDrdhPG0xDEuD8V5SXv2CY4xnv4RLxFtdGdpqAqpzwaK3jDQR7iziLu1shHKz jWwdvknGTc30JLh0ALMlLQWJ2jcuoIyiKhp8igkqblhmuO/FtEa2XhzQsdBLMmYcQbRm W5Nw== X-Gm-Message-State: AOAM532P9XKMXF+tc4NuhbkTYQK7bEzGEtKWQHmjEQyytwIULcADq7qI RPpW86ZJvfAaxzQL9Ry4No69tRgpfN4= X-Google-Smtp-Source: ABdhPJwPuIE+wcdX3x/GeVKLg9UlI+OLQW8REHj5a/Z/m5vJNodz5sBF0BUdRncUrjdD5daYsAH1Ig== X-Received: by 2002:a5d:6686:: with SMTP id l6mr5896630wru.236.1611086039187; Tue, 19 Jan 2021 11:53:59 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id n8sm37925955wrs.34.2021.01.19.11.53.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:58 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:41 +0000 Subject: [PATCH v3 05/17] merge-ort: add outline of get_provisional_directory_renames() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 56 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index b4c1fe28a5c..2a1c62c533b 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -721,11 +721,66 @@ 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 (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 Tue Jan 19 19:53:42 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030633 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 B61D7C433E0 for ; Tue, 19 Jan 2021 19:55:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 63B912310D for ; Tue, 19 Jan 2021 19:55:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2392015AbhASTzY (ORCPT ); Tue, 19 Jan 2021 14:55:24 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38358 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392087AbhASTzT (ORCPT ); Tue, 19 Jan 2021 14:55:19 -0500 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 926DBC0613D6 for ; Tue, 19 Jan 2021 11:54:01 -0800 (PST) Received: by mail-wm1-x32f.google.com with SMTP id e15so850715wme.0 for ; Tue, 19 Jan 2021 11:54:01 -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=X1K7c77iozQ7EAWOj1NdcLk4b681myE9MFxgQNb2s40=; b=Pj2Xr61WXvXZq+yjnKMLCvD5DzcpVBHxlUWMvt925IYKUUTYapxOqo6FiPypG2M/Fp NUdiutDNt2uGvfEhvrgwQdDr9Ag4MGzmCxJ5QIdGyQqRfePGvP3tAjpWEMxtlwIlWNVe tLUiLMfpRREG4J7AagsZ7pfakJX7FWjXuxzzSPvJQGf9sxFWXRF7zjTqzzMbRVrJV3Vo fkIhxiGXbvOTwNEGkyVa0oMl7LZX5ueHSvcK+Dbz5anC4vNvyWyP68HVegq7QDEwkS28 okhVI9igKiLxENJ9JSwXha2TqKzqw1BjAZlj5FyVDKabwmkPg+UFTqVqWW4ZFokZlaFv 8yhg== 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=X1K7c77iozQ7EAWOj1NdcLk4b681myE9MFxgQNb2s40=; b=YLjCTFPQ+m9Jct4uSYuusCKABRRNRSdtJOzD3sReLGjzBW2nXkCbBNAtVuk4sp9Tln rEls+h2Z6rNY7ZiWgAuNF5PElkLTPaZLI/9mrfPeb2zi7VwafumAy26sBcTjwBhvQtuR lzcKaDAFnh44Vqcay0Gu9uqwEmHwmjuiHRKcRq4gIexk2Xy3eoWrwZSUIrr3sXk13bUL bEoA3yPcIcu0bqds4xepHv8CUKlxwjoHkOjzOHjCdGkrdGVPQawOdSGJhFwDDwUN8hfN vFenwgIOQHUo53ibPJRxBBSDbZatCufCVUOuOQ0OStwOryJSt7VGY2kH7SrDJ9SWmHJ9 EZNQ== X-Gm-Message-State: AOAM5333G7ZYkzstNEqKFAQVanm5HyHgyurd1c8kYXB3Y++K36wu15O/ ws/A1iF9wIWMtICllL0JR6E6HD+Ljpk= X-Google-Smtp-Source: ABdhPJxmHT13ZGwjMqPJdgzS+ns5knBgqVEET7XKx5CCQ1j3gV8XdnEoXfwY7XMKWKKFRbPDmJSTZQ== X-Received: by 2002:a7b:ce11:: with SMTP id m17mr1094043wmc.158.1611086040110; Tue, 19 Jan 2021 11:54:00 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id d7sm5754944wmb.47.2021.01.19.11.53.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:53:59 -0800 (PST) Message-Id: <54c1850570659b4c819a06ff5c14651c8676cfa4.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:42 +0000 Subject: [PATCH v3 06/17] merge-ort: copy get_renamed_dir_portion() from merge-recursive.c Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 2a1c62c533b..eb609ab0063 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 Tue Jan 19 19:53:43 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030673 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 B6942C433DB for ; Tue, 19 Jan 2021 20:01:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6715723104 for ; Tue, 19 Jan 2021 20:01:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391760AbhASUAR (ORCPT ); Tue, 19 Jan 2021 15:00:17 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38362 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2391966AbhASTzT (ORCPT ); Tue, 19 Jan 2021 14:55:19 -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 8AD3DC0613ED for ; Tue, 19 Jan 2021 11:54:02 -0800 (PST) Received: by mail-wm1-x32a.google.com with SMTP id y187so832614wmd.3 for ; Tue, 19 Jan 2021 11:54:02 -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=O5wTBKeWiHf7mJrnNho3TBC79jlaWAJ7FeqyH8aQJ/4=; b=bHP4ZTsnItQT2MmZX7LPWb78TTIx2ZIS1DUhG5SL8qnadpCnd63O9phqPpnlwSqxau Bp1auFbyoFVhivSIr8WUsn5ThYTZ6JdC7DCCXFyM0EN2ewjIS15UksF+U/IojDxZEeNW ksfQzq0s4BaPzPO3XXoZzqjNnwrnXUP0p3zbAasWeUOebQWkVg0dhWJvIuTQKnL4RFrb 1q+/+LXICOJVV9NHiG8MHsx+YBkJjZRxN5vA4xdmyeknu9iUn8f2T/p5TwIo4TYkj9UI xZBrClDIp10AIdGpKoIzjl58lRr5DF3lgA0DmaoqGeqKSCbzTD2XRnqz6+IQLbwvqgee fMRA== 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=O5wTBKeWiHf7mJrnNho3TBC79jlaWAJ7FeqyH8aQJ/4=; b=Ra7dQXR1L4ffZYrpUpql+ASdwswgx5MV0sdidEPKhBRphNslqoRTZytweRxYvT5W4s cMYTm7TFhISQ128E3XdIyI8GmlC+x/udYpuDQazrcMO52IguAVDH0AtoYDQreQLIApe9 yalC5LicZDlO8lWK9EerMNr2xwlMuEaPCCNtjJRCcqopVukZVm/MipfwMkid1wfjhk+L Haa9TM7WZiZ3Sa0uPsa6EnNRrBiqndlLMTpYNp+l6d0zGfjqRFG5xplJwNJ5sHD2YABD sHWgRTJboz1nKB22YTZDXJGPP1khldvWX4xNVcPPMrHglAeKKnEBVmYVVnbMXazYUgYq Oirg== X-Gm-Message-State: AOAM532DHxNZMildCnryFsAfOdUTcb3i4BqrWh7wYtwfLDX1BvnwQbkw KMRQ3cEo/plyNKz5shFcFC9RGzHnOnc= X-Google-Smtp-Source: ABdhPJzrgZajrhBvJ2BrkpcB7TTkd0oyVh6/0CPm/8tSnvjk5w+00NpIFlV8nNMnAAiCIqXhUfhdvg== X-Received: by 2002:a05:600c:1986:: with SMTP id t6mr1081558wmq.93.1611086041069; Tue, 19 Jan 2021 11:54:01 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h5sm39748893wrp.56.2021.01.19.11.54.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:00 -0800 (PST) Message-Id: <5b5c8368174179272b67659d9babd251fbf07497.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:43 +0000 Subject: [PATCH v3 07/17] merge-ort: implement compute_rename_counts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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; as part of the implementation, factor out a routine, increment_count(), to update the bookkeeping to track the number of items renamed into new directories. Signed-off-by: Elijah Newren --- merge-ort.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 52 insertions(+), 2 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index eb609ab0063..8aa415c542f 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,62 @@ 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]; + + /* File not part of directory rename if it wasn't renamed */ + 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 Tue Jan 19 19:53:44 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030667 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 C2166C433DB for ; Tue, 19 Jan 2021 19:59:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7A29B23104 for ; Tue, 19 Jan 2021 19:59:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729842AbhAST7U (ORCPT ); Tue, 19 Jan 2021 14:59:20 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38364 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729969AbhASTzU (ORCPT ); Tue, 19 Jan 2021 14:55:20 -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 7BDFFC061786 for ; Tue, 19 Jan 2021 11:54:03 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id i63so870426wma.4 for ; Tue, 19 Jan 2021 11:54:03 -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=m8rNPCROge/KXdKMUmdsHImLFeBiC8U5I3xNvcm92VM=; b=aL8Gbu7YG7E34YEcnhEZ4adIN3aPQZbngzcqkvCb52rL3G3W4WaPyrJF+BOfGDYn7s /406r2QvbPyy5haiyDLoaJZXTN2BJsRrVjK6ivHHNMeFO0lmO02o7um9/ZwEDWErDz+g qYEsMcuHZ0B24ujHDLTFPaf0xoAnZb0u0svkEwJCply7nq7nzYS/S1PUy7M9Dr8o3UX/ 6xsyn82YpxRvKT97YmAxZJjMuFx6fF7+g50iycefdrLgdnl4oR4NHrXXiRKFb7kpcaFZ tiqwlxjxO0HFq9CExRXw43oDPRNMAuF/Eq9uYtO0XuM6XONCG47PZa+kgrpICtetW7w7 Hw1g== 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=m8rNPCROge/KXdKMUmdsHImLFeBiC8U5I3xNvcm92VM=; b=uB7YYc/VGBXE8qez+VprWPA31LYrnrdrPS0LGLQx9+SL4C/U8+NSotOgwBMIa3X6Ui koDf4CLyLqCVIvPaD6+STgEkiBHGjclluXwUwSyWaB9C3zrhaLk9R++tWeZ60jxBKwCi ZKmAJy75qX3BS0qlvgp6mAPBG0v70xUWMoqWSA+fdp6+9+M/4+k27UaERKTSnSzVpjxT qcVCWoR7O2k4HqlsyGT2k0UQGvuV+cFeXTbb6k6fOHFskboXk5wgO/NEIkbUOnsPSLFJ PUjO7wqHDTURnOprySeHAyDrTDEMk2ohj+b1JFRdjuhkSVYEFdi5c1lDUXSzoZLc2yrD +bOg== X-Gm-Message-State: AOAM532tQ03td/Vp2zS2PPI+DKU3iSWHHYUhEtPjsUOSTUGk0kX8zj1o Sm08rS+fA/kIRZLN4uGqeA6n+eNf7zA= X-Google-Smtp-Source: ABdhPJyqOpWwyO27nmtwsZTgxsIcx0jznNx6BxY7xYfpFAEjMR5w0qmMsisY7G/ainpBkTCENbiovQ== X-Received: by 2002:a1c:9a90:: with SMTP id c138mr1040725wme.147.1611086042111; Tue, 19 Jan 2021 11:54:02 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c2sm33016108wrt.87.2021.01.19.11.54.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:01 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:44 +0000 Subject: [PATCH v3 08/17] merge-ort: implement handle_directory_level_conflicts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 hashmap * 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 | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 8aa415c542f..6dea4206dc6 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -939,7 +939,24 @@ 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 rename_info *renames = &opt->priv->renames; + struct strmap *side1_dir_renames = &renames->dir_renames[MERGE_SIDE1]; + struct strmap *side2_dir_renames = &renames->dir_renames[MERGE_SIDE2]; + 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 < duplicated.nr; i++) { + strmap_remove(side1_dir_renames, duplicated.items[i].string, 0); + strmap_remove(side2_dir_renames, duplicated.items[i].string, 0); + } + string_list_clear(&duplicated, 0); } /*** Function Grouping: functions related to regular rename detection ***/ From patchwork Tue Jan 19 19:53:45 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030669 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 3EB07C433E9 for ; Tue, 19 Jan 2021 20:00:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E97E823104 for ; Tue, 19 Jan 2021 19:59:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728892AbhAST74 (ORCPT ); Tue, 19 Jan 2021 14:59:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38366 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392089AbhASTzU (ORCPT ); Tue, 19 Jan 2021 14:55:20 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6137EC061793 for ; Tue, 19 Jan 2021 11:54:04 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id s24so2164012wmj.0 for ; Tue, 19 Jan 2021 11:54:04 -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=N10pSBx6/l8A1GlErUbjDT3w29kUzj8xpttyDUnNgqM=; b=obJP8HwTlY4LVqa2qipHao6zHb/AUXxZ9IFnmpkbhrt5IhhKOqNHhTKzBLfMV5nYhw 8xG83PHxYxNYlEOPwpvgzK5TdJBOzwtjyXrZuo/dBXFcgq60ACStnbr4IJ2sILvLA+Lr TKGfFy0UsFZrmnUoMtvvuLjYRw/rolXPwvKO0M32jcEoyeRabMXhtsla2rel+Ljq3L3H C0oQFxaLSorgvmZ/VPfn4g1uCt1KTessEymc+GskG0Qc+AauKOTbNWOag2BdQvLVtBHw vfid9XuUrWzwK79gYf/IfkJqP6N8+Z40XHWmE9fV0TY2Svycaw/fl6M5vzkZRnuW+/s7 X3pA== 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=N10pSBx6/l8A1GlErUbjDT3w29kUzj8xpttyDUnNgqM=; b=l0jEB3A4Q8tGH2B/BOO8L0NzIawYtNW3/z0auPR0IdKL/vb8tcPS+14iizEYoHRGN6 E/K7+jUu30Rn/19z9Tce+EdMIJxvzHgqfiVUnMRAiPeDSiNZvbXn8c5cxsaG5O6fdllm WVvS1GO3wqeWt9FSBivZESGH9Kj5LPc4Wltf9qiaav3n2yMoJ5HQP7v5J6fcY6Y4kmqq EZoMBfkdQPAaNw7bk1UMwm/cHUv3R7fvaTIjl7UkAHgbx8CjP+0W7HZAPH97Ykf0vvWF /BBsfZdEVitIiv/aGdMpovp/4lPE/g2SC9I7f5yA9Y4yYaE13dgOGcjhPtiFFaeobn79 U9bA== X-Gm-Message-State: AOAM530gZbVuAKvy4A7f+9q4tZXZlXun+/r6sX2oVQyqqq5kG+Wh40PO JncFypnLEaPVEkpyN315h8keCRLq3UA= X-Google-Smtp-Source: ABdhPJwYPxs81/kawg7BBXWsnPdE5z80Qu511RC+jlprvY0woRLMIK0cf8tZpi8gDZnQgGp9P/MggA== X-Received: by 2002:a1c:1f86:: with SMTP id f128mr1115548wmf.174.1611086042927; Tue, 19 Jan 2021 11:54:02 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s2sm4702574wmc.12.2021.01.19.11.54.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:02 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:45 +0000 Subject: [PATCH v3 09/17] merge-ort: modify collect_renames() for directory rename handling Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 6dea4206dc6..c86ed85b097 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) { @@ -959,6 +964,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, @@ -1284,22 +1314,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 @@ -1314,6 +1366,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; } @@ -1345,8 +1411,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 Tue Jan 19 19:53:46 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030639 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 218DAC433E0 for ; Tue, 19 Jan 2021 19:56:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C988A2310D for ; Tue, 19 Jan 2021 19:56:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2392277AbhAST4E (ORCPT ); Tue, 19 Jan 2021 14:56:04 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38368 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392091AbhASTzU (ORCPT ); Tue, 19 Jan 2021 14:55:20 -0500 Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 53830C061794 for ; Tue, 19 Jan 2021 11:54:05 -0800 (PST) Received: by mail-wm1-x332.google.com with SMTP id 190so890700wmz.0 for ; Tue, 19 Jan 2021 11:54:05 -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=w2/HSScYSrG8aAG3GHWx2M+5Qf4iHoRWPTPJjAhD8So=; b=PHBrjhHshBa9UI7S/Jmo4b7VMf+T58cHtxHYqs2O0MqSNrYHOYrUkSIeMfYGxtfpDN bbasUb8nDSg+YFQEAhrXMs0Xaa0apvd74jBjClHqTme5E1HpjFufqTOCFQ1vZ8UzJ+EP XS3RB2+5tSxRFe+TAVBgAtWLpi3KmRGly/BcRqT0MyQ+5TsWeBSKkTmToDElpJDXiP2Z 3fG2UXdRIhy6NVmU1C4V84tGGeMIrvfFiM2+0vdL6ijdLqI+x2LZSBVRVPZozDRSwwQ6 9uVAqGzd6DVEn+8ZJf/Y44eCngDuMdSTGglCj7JW/ne5jBKVsbOvEH0p/ft2dFYP7Pa5 RJFA== 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=w2/HSScYSrG8aAG3GHWx2M+5Qf4iHoRWPTPJjAhD8So=; b=WnikWAzWxDCWiJPrihVTGd4kidvH3N8AC9A9LvQ7fYcI07hlnB5zdYoZKcUZNeNZ93 rKdBp/jqngyvSsWxMz35T0xe3wXobWr6j0fsm9ZnpJVyBOSjCCRFbGQoibtB0hIv3ZOi 7Opm+/WN3mc2DthdhGjKScyKf8uEp7pr+1KK0WhEdba9sJSK0QKUP1U4j0cWA2pZETX/ 261qjQ7Eqn3AW3Ne8g/38JStbmuyyWDXdlxvXYXzYZzkZmI427Xx60if77XKgpk2OMfz 78TqZRWayrSJXJRS7akQFDXWoabHzQU8+VvAp3bCZmI9GkOP5910KgUPjIKNNaxE7Lvk VLHg== X-Gm-Message-State: AOAM530uf5/xjPJEE/5Oq/y39cPSRYtMif9UVMwLn6eleaSn9fss41Pt 1XAWrxqDeEo/o/RRORW52b1aN3kYHiA= X-Google-Smtp-Source: ABdhPJx2ZSPrYIDI/Pyx7d83mkH+7itoRultgBzh+00Y7Y9O+dGF01CvMR93prUkpFnEgdG48OjbEw== X-Received: by 2002:a7b:cb4f:: with SMTP id v15mr1083892wmj.123.1611086043919; Tue, 19 Jan 2021 11:54:03 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s19sm35965025wrf.72.2021.01.19.11.54.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:03 -0800 (PST) Message-Id: <28ae21bcb46d2b582183db62b346f5d1998b4e52.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:46 +0000 Subject: [PATCH v3 10/17] merge-ort: implement compute_collisions() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 c86ed85b097..22028d57f3d 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) { @@ -964,11 +977,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 Tue Jan 19 19:53:47 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030645 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 47612C433E6 for ; Tue, 19 Jan 2021 19:56:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EF5D62310B for ; Tue, 19 Jan 2021 19:56:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2392173AbhAST4N (ORCPT ); Tue, 19 Jan 2021 14:56:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38370 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392094AbhASTzU (ORCPT ); Tue, 19 Jan 2021 14:55:20 -0500 Received: from mail-wr1-x436.google.com (mail-wr1-x436.google.com [IPv6:2a00:1450:4864:20::436]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 37147C061795 for ; Tue, 19 Jan 2021 11:54:06 -0800 (PST) Received: by mail-wr1-x436.google.com with SMTP id a9so17468744wrt.5 for ; Tue, 19 Jan 2021 11:54:06 -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=ygk2dHvdie6xocUMSQuhzWjXnVGU//ctbHvZdY9sPug=; b=YkXf3GN8BR6j1WD6DoEhQ/i6+bBrYkDDYOZktpHvz5O29cwrAEgCvm3e/cw59SOekh nhwnPqJ4rt1C/7ExAVNPgZZfKFQr2V3kro64A4BOV0f5s+/4tztTu+yUGMYsodd/AoVs V1GzqbofG9AQxxNSkqA7NFYZtEp9M15WiGSJlBIbH3s+QLaUS7JlPr67W+l4tU0yaRka Ewm6aPzGD1IlhbLQiAU30tZEAbsX6a0x+qVxO+PoF/50CVSZCErijvrUSc6Fnir8Z2B0 6rt2RPemUhu1wEvK7247cbmebQMxDMFFc6rEvzFPyS6uRNcTEjWiSOWpdEjNqP3qW8Me 2v3w== 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=ygk2dHvdie6xocUMSQuhzWjXnVGU//ctbHvZdY9sPug=; b=M91AbqbHYppsHy4J0CLIub4H0aMsjf2Hn4uds2WDVe0gG/RsdDS3CEkK3g/zkEbuGg zT3HmVjPkQ3LsHaQi/gpDPUvl+p1KH/04xwhWf7qYltruevh12WfSM+18EOtA2dDB5ba J4/phdcRA3JNtuErTLxC8ioqgL8wlwUCdMB3z6Mcr5yg6GwOBah/b6zxGfc8QvRitwqr qBNedun693R3xtaoJEOzAz/KXUvxhwtN+a719PYsUlyGYmib8ljLY7tVVxh7MFCXPZq8 oS12RzYglqLe59IfoneBu25dRMXCN7OHW5LVZoVEPFm7FmvrglMBZQ4fEZPp/zjukEmy dv/A== X-Gm-Message-State: AOAM532FCsVVDB7E9Bg0Er9CXjWV+4+4C/bNLa0VCJk/SQMn0bML4FJ1 yMbJTEBPwPobUjGRgmV2BmoX92+2rIE= X-Google-Smtp-Source: ABdhPJxT2phcROoy6LeaJIOnbr1jPz3zTuP2j6L5uYgSE7UyU4FOJUsygj1DtC6OoiGUEWDfzrfcIQ== X-Received: by 2002:a5d:4f0e:: with SMTP id c14mr5919544wru.84.1611086044826; Tue, 19 Jan 2021 11:54:04 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s25sm41176997wrs.49.2021.01.19.11.54.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:04 -0800 (PST) Message-Id: <95f6e11907240b1cd7772d358fb4ad580de3b506.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:47 +0000 Subject: [PATCH v3 11/17] merge-ort: implement apply_dir_rename() and check_dir_renamed() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 22028d57f3d..db922272edf 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, @@ -980,7 +1002,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 Tue Jan 19 19:53:48 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030665 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 D9A1EC433E0 for ; Tue, 19 Jan 2021 19:59:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 941432310B for ; Tue, 19 Jan 2021 19:59:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390820AbhAST7Q (ORCPT ); Tue, 19 Jan 2021 14:59:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38394 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392077AbhASTzZ (ORCPT ); Tue, 19 Jan 2021 14:55:25 -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 1845CC061796 for ; Tue, 19 Jan 2021 11:54:07 -0800 (PST) Received: by mail-wm1-x335.google.com with SMTP id u14so828412wmq.4 for ; Tue, 19 Jan 2021 11:54:07 -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=yYjdeMwcEkwlwbV0E3MXEBcoSxWoEC30fUk9SMydLaA=; b=g+KsP0cw6mTdndGJg9sBZKVtloIvLn94EK7VP47gABEasp8uWuNe1T00GPfXreAxjU ovVai7oyLv0YHcmxQ59YkcGtzbq0S6kfzLiF7bFTq9nzWdAYVy+w4k9A1cqtkfPCuOdS QEEL23l1yDK2NY7Q0VCOc3X8n5h/sN+7n4/9oJqAFuiBEEgt0JpsSEOeLcCYcsmA5RH+ sF3TuiLkAHEcYgg7vQHW0jMHJeMatv0zPzN1BY4wZLklC+DDHA8VPB+/+3wnfWvmjZdh 5fbeOCmsQLlyEtPhjyj16+XEQd6UJ3weDWKnx2r91Wepeyzc4jCn3nWEI1t3e1C3O3Eu iqCg== 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=yYjdeMwcEkwlwbV0E3MXEBcoSxWoEC30fUk9SMydLaA=; b=AmRad4nEKGXMUNiddj5wjjUUqoTb4fDhoAyVO4XnRIPsnfqbf0pfviP/XlkPVTNKem lfu/skt5Ntzr/iANAhUJLJhGo+ct+zVIeWUQ6vQ7JWHmKZWBNLZmG4yfLCLBSPM0CrD7 ko9X2zT3xayFZ0JdR6ooY8JInCAqg8bAi+uO3rSqSdSj50/EkWDpfQ/i37uI15CYf+TC ZPio1MKR4/mnl9OOz0lxSTSJXC4mWY7LdjWH28nlnrGfDIIYjgwe4GuRR0be19EIlgvB wvZQvnNzA2z5bN17oQ+PGNGDafWNlYIeTcHYkRFJrjRRucrWVpA5YtO/RCEYG5E/77UG npJA== X-Gm-Message-State: AOAM532SeTDpTgil43gwMwTlo+4szUIR6C1PbiNmocd6XPM+FhWxllE8 X/vv1lyeW3abLxOGmwGczqOcWHgn4t0= X-Google-Smtp-Source: ABdhPJx5PSn/7/UVJnSx8//NPkn81GqPgKkM0LcW0U0IKn/F59nzKQop12RhUU0lTYNEtASfGC2c4Q== X-Received: by 2002:a05:600c:4ec6:: with SMTP id g6mr1169135wmq.2.1611086045678; Tue, 19 Jan 2021 11:54:05 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id m2sm5777509wml.34.2021.01.19.11.54.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:05 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:48 +0000 Subject: [PATCH v3 12/17] merge-ort: implement check_for_directory_rename() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 db922272edf..86d2214006e 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) @@ -1078,7 +1093,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 Tue Jan 19 19:53:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030663 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 87433C433E0 for ; Tue, 19 Jan 2021 19:59:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 382692310B for ; Tue, 19 Jan 2021 19:59:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730139AbhAST7L (ORCPT ); Tue, 19 Jan 2021 14:59:11 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38396 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392086AbhASTzZ (ORCPT ); Tue, 19 Jan 2021 14:55:25 -0500 Received: from mail-wm1-x32c.google.com (mail-wm1-x32c.google.com [IPv6:2a00:1450:4864:20::32c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EF3AAC061798 for ; Tue, 19 Jan 2021 11:54:07 -0800 (PST) Received: by mail-wm1-x32c.google.com with SMTP id v184so846243wma.1 for ; Tue, 19 Jan 2021 11:54:07 -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=BHbeRbrue7+N3V7H9FmoaCX8vFmbG0wcwDK4/486DF4=; b=Mcceieorw1UQA3TKX9aM41d0MVajzvQ3UUwBzGxJa39vmwCz52MBiljiE9hRyNl/od ba+6oUvmAga9g8XX3PdKojeAHDi/nZKaDCvx5em6W2SZaCTqvJoyEVBD2Kvzrd0lPw5V dG4jG3U9k/OOIUTWjBrKrrVB/lQbaWd3XpckfwYcd2iwOHfe8BtUCQDAglu1pU7GI26M lcmdrN7v5+gETfl8q9yO5kLmg89TCXg9HZjQ8cr5emK8KQgTCpM3AfWsDqckHD44Nj2c KbvBRkJd7Xdo1FTDHNCr3//WhAFdweMuUSTGO46FB0Pj1SMcr1/Rm/02sP6/HykRR3yR QFQQ== 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=BHbeRbrue7+N3V7H9FmoaCX8vFmbG0wcwDK4/486DF4=; b=TJEfTP77mwzidMuKds2jQL3uwewJCaSnCg+1e5OLAn7Tq65W6vvz+Xz+8UqrMWKv5R siJE90MM4Vx+nKDSw5cHx66fhWogAnB5gWu3L2dJITzOCq+UCRGvZf715NThL5AY4UEI xGtU+zg3NoeM5BsNwSxD1ocWJz57NN/b0MAJDFBjpYuK48wveeDbymltn6aa2VirpHaX anc7oQQt5c7BPFAULX/O9s3LT6iG9/qppq/VY98zCZeTQfoUsb2UjuYip+Pz/Anc6zDl beTs+lAAJDeB2Iq7t3d59FP4fnhP9yZ4nzaGrEInHdpXIZJbop0s3Bucn0I0r70m1PyD 6gzQ== X-Gm-Message-State: AOAM530GdMrjE7X9HiSmp6qpIVn1hE2ONmcErmmLEVR6ODZ8CjAcUJ7B bxSNgK31E1jodaD6/8UBEdZFdYoIfM0= X-Google-Smtp-Source: ABdhPJwOcFp2rtwF6Ia5ObMtewxqDpmTblcX2HjS0nuEXg4QToqNAc79gIEsnJ0eQywtkkDX0ghxMw== X-Received: by 2002:a1c:2945:: with SMTP id p66mr1126945wmp.110.1611086046503; Tue, 19 Jan 2021 11:54:06 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f7sm5573515wmg.43.2021.01.19.11.54.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:06 -0800 (PST) Message-Id: <1bece72e37ae269c81336a7e8406db1131684383.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:49 +0000 Subject: [PATCH v3 13/17] merge-ort: implement handle_path_level_conflicts() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 86d2214006e..ad8ecb7e448 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 Tue Jan 19 19:53:50 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030661 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 DD0E1C433E6 for ; Tue, 19 Jan 2021 19:58:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 91EA22310B for ; Tue, 19 Jan 2021 19:58:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390462AbhAST6v (ORCPT ); Tue, 19 Jan 2021 14:58:51 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38298 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392144AbhASTzd (ORCPT ); Tue, 19 Jan 2021 14:55:33 -0500 Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D8E3BC061799 for ; Tue, 19 Jan 2021 11:54:08 -0800 (PST) Received: by mail-wm1-x332.google.com with SMTP id m187so885279wme.2 for ; Tue, 19 Jan 2021 11:54:08 -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=1u4V06vH6u0mHUMgN5NtHBEHiw3x/FPsLgfL+4qUsO0=; b=daomNRxBMBg9ZctLBBMtPA9nCUCG5bgq1faqRzFJkIFlEhkKGYwpksw13CdHJJzzLP DcEkWa3Wkzc9BH+vJGnczuSgrTiUDnD9MBawuhD7RJx1U0MBNNUyD+n+YHUsXFSd7Tcx YNFf2kVR1I7ouX26ksVKur7eyJme6sjE6y+AdSHG6ubhZbTKPoqPgKev+iWHX4wMUjF4 CNmlSe48VXUlrMmNAYK7YSV7YEgbmSj6JsBB33Ko3rXGNZcIHwwAIqocHodqaW7iITI1 9ehih7XCWSMk/UvriV/951P1KJnEf0C+uKwRQha+/MA94ds8jAoblXbuhp1NrxFCelK4 enlg== 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=1u4V06vH6u0mHUMgN5NtHBEHiw3x/FPsLgfL+4qUsO0=; b=rsCAqmNaPc69NZM4lb6EIV+nQ6AQXHuobxJBA5IDwyhfwd786sFLsgYGBsrrf2PLYr aRW+CxnymIyNxTDrS9Gd4R6vfyiW8ow6eNPK5K4RVnFkdDHTSFv8nEaox3IwpU4VCEUc eUbOUZ/rjAYxu8v2PJQnZdC77ZqzcGM0d7eHRcn4GEUf9qYFh1dQEaxaE0F9dns3n1GX cnG9fjc9T8J45sPfIIy6+7XT02KBAp8UOxddWCLohwS/WMkYlCfOvnmyKILJJZvYO1/d Y45I7e4CVe08HePAerkLj12x1D/iWVpsHCbEoL+fMKguQIP6PcxJxFfqJqsIaLVn3SvA Nx6A== X-Gm-Message-State: AOAM531dpxFUphxnCFcxZpYHdPFq0fSLEaInnKjOfO/gqU3oCxfJ1Tt7 9VhXvDa6UK4+mM0urbZ81Uf7Sg2UYTU= X-Google-Smtp-Source: ABdhPJxnUgja0jMlDqJShcxMqgyGL6B7dLfQNVHlw/laJ2pC8EonWzZzGinXy7XQw6j+lszVETQ9UA== X-Received: by 2002:a1c:7f94:: with SMTP id a142mr1078030wmd.145.1611086047475; Tue, 19 Jan 2021 11:54:07 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id g18sm31443908wrw.61.2021.01.19.11.54.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:06 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:50 +0000 Subject: [PATCH v3 14/17] merge-ort: add a new toplevel_dir field Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 ad8ecb7e448..5b3b56dc1cd 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 Tue Jan 19 19:53:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030641 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 9B838C433DB for ; Tue, 19 Jan 2021 19:56:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 410DA2310B for ; Tue, 19 Jan 2021 19:56:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730223AbhAST4X (ORCPT ); Tue, 19 Jan 2021 14:56:23 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38300 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392139AbhASTzd (ORCPT ); Tue, 19 Jan 2021 14:55:33 -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 C8FE5C06179A for ; Tue, 19 Jan 2021 11:54:09 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id l12so15695690wry.2 for ; Tue, 19 Jan 2021 11:54:09 -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=TnGcD99DeNIZL5OGLefJx74C+G0PZG0yK27PXs7H4K8=; b=du9jQFApxpuPQezwJuVsmd2VgK3u2gsjIFTXDb8j67/7XSEslmY/QjK34RXRcN+Vg5 Pei2eyjOhfmegLu9D6sva0PoRFSOgvUSbBvuSphXVKZVNEjtMD9C8DW7DREH/n3MCj/m AJgmW2Ru8gdqRYzvpwwPqVyD+LMFt0gyKc0Yv9v6nHSmHzV8a6fIUES0d+lZGnGWTR5k zEmaghD1nvqz2XGe8fl6g/cdC19jDVLEQ+yo+If+ngjvCDlwSDljJvPGvzs5HhKqkwRV 6E3r51elorVPrzAKjX5hJHnawuPvve5O6uSEdfTT5G+kJ87mGWX+avGhukWnPYc8n4En gWqg== 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=TnGcD99DeNIZL5OGLefJx74C+G0PZG0yK27PXs7H4K8=; b=jHqMLXSzcRNBAIjPtRWjfyetgPCW+VWB3y/AUoj0SH1UXBUtuJImGR6fsay01BgVMX XbjsoKdc7kpA7mFib6J1yIlgo5eHJJBO6OhSfHWjpBtcIRIp/XFDLF2z+Lq/15vkBL3S B4exGH+rVfYsJEf/isM88qxzbkIcVL4HLHTGEUE9mLlc3SSwXk8vKwJJ0QRBPgriuUZf JLTFqDfSlRX9hXmqUiKk/JTaiG4nlBfMr2UCctn452+UhU59a8KLFocQ0xSAXZLlfygg C/f+2ek/BYHuz+V8JtFznNhEk1ICnUeQBvXDK0TjgStA+BFzKVRbXwePAdYUk93Ud2z/ +2gQ== X-Gm-Message-State: AOAM533755w6PeoUSnOf7y55LCD6ArcjjeNsKdQIDoyTCPHaUhfQR9tF 3xdXEIXrS4kWiL44lb+p4RSPxvw+ta0= X-Google-Smtp-Source: ABdhPJwvKnAGySRI0vz9fggBvH1Dxl7epeUHpjQhjC0COu6iWOdpewSiKHHHhy2YKlLQVQ2UuJzt8g== X-Received: by 2002:a5d:58d3:: with SMTP id o19mr6097452wrf.250.1611086048318; Tue, 19 Jan 2021 11:54:08 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i7sm39308605wrv.12.2021.01.19.11.54.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:07 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:51 +0000 Subject: [PATCH v3 15/17] merge-ort: implement apply_directory_rename_modifications() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 5b3b56dc1cd..1152d0ae21e 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1223,7 +1223,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 Tue Jan 19 19:53:52 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030659 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 9D028C433E0 for ; Tue, 19 Jan 2021 19:58:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4133E23110 for ; Tue, 19 Jan 2021 19:58:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732192AbhAST60 (ORCPT ); Tue, 19 Jan 2021 14:58:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38516 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392258AbhASTz6 (ORCPT ); Tue, 19 Jan 2021 14:55:58 -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 8CB87C06179C for ; Tue, 19 Jan 2021 11:54:10 -0800 (PST) Received: by mail-wm1-x32a.google.com with SMTP id c127so821678wmf.5 for ; Tue, 19 Jan 2021 11:54:10 -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=LB6DzRWwHf8U2p9Xh6RTlRrxoQr9tHmDu0eu+IFcF/0=; b=dSn9V4bZ5ct5gZcLppuEjpWfyrvpQ0NQa/PZtNEPS9nfbP+qdvH2xxZCAAzTENgB3m EUXWZ6CswlCv3+L0gyskHsscB2NMGvYyVFZQnAcuwTL0dpXmucTEWDhfbnh8/IenDKG+ lLuq2/Reb5QLI8bC0V0ElOsP9Z04ro082nrE2S6RjCGm1lwEbVnf2uXZOa/UkpE3hC3L n/N6dnC653Ruv+5xD4tJNfnTGePls5YgceGiMGJkf0eyQf39g6Z6JLBmx9Lne41BcZn8 VuL3i52oUd33x5tZoxTR3Nkjai6W7nSB7WxvCPBTj3CgC7JZ9802RJSiCsnCKiI9tN7V ESNg== 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=LB6DzRWwHf8U2p9Xh6RTlRrxoQr9tHmDu0eu+IFcF/0=; b=LqZ5KxRjgF4iy3QJ4vbI5TAAR1avqTF5IDycCkE+DWlUG30U9xtJ91SzF2yvM1j2La 6EzoOtX8oK//3Im2oWMgqx2IrKUzZ/eDI9PE3KsUMTXvBY3B1y9ji/o0jWO9v1S6QjJn xTVX/nQXx+esL5zY8NWbo/gczQe8BHR1T3uFPg+9MH7oGqHGu15dQYtIFWd2RqZFQwns wKs9BQ1/qbk2cZE6duPJIkVsS5xD/l7jpt3EeNqTXMQardc9dNeG8gOSuNSG8ANeVXgm E+qcHWdYAcMvspUYondPwbxF9DHiQxshAnZFP/xVLrX5BX85BhAlo0wSOaNV1GJplEcO p+rA== X-Gm-Message-State: AOAM533fs98TCH8yaKjjjmCNsEC8qrgGSR6q0+XIpvTbw9fwMS+Xmno2 R9xTV50zvmKjR5N4YwM+CgQWTa38Nas= X-Google-Smtp-Source: ABdhPJy9L9oB2+/IcBEUbqg+U8Aglv2zxbTvClkzB+vHnkNVI2uNOce+RUTXcfqIvwDERINojC2Ekg== X-Received: by 2002:a1c:f706:: with SMTP id v6mr1102581wmh.85.1611086049213; Tue, 19 Jan 2021 11:54:09 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id x7sm5630083wmi.11.2021.01.19.11.54.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:08 -0800 (PST) Message-Id: In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:52 +0000 Subject: [PATCH v3 16/17] merge-ort: process_renames() now needs more defensiveness Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 1152d0ae21e..7314f9c69c2 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -1410,12 +1410,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 Tue Jan 19 19:53:53 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12030643 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 6B62FC433E0 for ; Tue, 19 Jan 2021 19:56:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 25C3A2310B for ; Tue, 19 Jan 2021 19:56:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728790AbhAST4m (ORCPT ); Tue, 19 Jan 2021 14:56:42 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38362 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2392197AbhASTzj (ORCPT ); Tue, 19 Jan 2021 14:55:39 -0500 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 831C1C0617A0 for ; Tue, 19 Jan 2021 11:54:11 -0800 (PST) Received: by mail-wm1-x32f.google.com with SMTP id e15so851152wme.0 for ; Tue, 19 Jan 2021 11:54:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=SBX50jTtSCkmvJwUfdCRNS0p7wVjBYxX2b8bzcgBC6E=; b=fuuA9MzZXsl2BzkHVlEFmNpa2ppcqODCNHAiGdtmTvffI3crqLS45xQ9ocLH6vpqwq YT2FGs38uSOT+Nw5MbRlKTyLPxmfFCoFozWRUuYPS7Gk/acY+i3OQiM0v68d8YOhpAc1 PLhT6kZAO35ZJTbjFY/KPnSWguT+2t+sU4okW+tpCq7AMtISj4gzANOSVH1uiqJxSypC kCbDFJjAAaZKl/d49l5eabKXaWbNvwUuInv4ba5A0AY16JhoiLh17bIjLdh6sbWZi5f/ S8cAtfFH0elUJPpASvvwdA0GaKwImI9AcK+sOHYNSCtFlNvY09XiMhkKYv/Wuah63yTg w5Fg== 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=SBX50jTtSCkmvJwUfdCRNS0p7wVjBYxX2b8bzcgBC6E=; b=IDK2u4a0N5r+YwEIQe40hk57hTukBTu1m//KnDdVMmEoza2zxGyrJ1ZGQvX2Fe4WA8 jdokiqW4mQzA3kpz3SHJSNzHxHSAxJXE3XN4RCvcCnXrGxa1/RqYxcFQRIIOpy6aWlkY ud4XGVuSzpQUMY1fbJoiFTVDCNgZuemOrLzFQ8LCcqqGzRfczk0Jpe9uSgadLL5/0WWa 0W2rsQUlGqcxDEnrLp93DA04Pos14nxuaCAcyW4qjUXOPBKVPaLejJ1Il0BZjXuI7nbJ PE4kvqM1vHkJdfcLhMtM/gNh9w1ZKuMpB26yLKp3WshOxBj7XLjwd7BpWfPkrETewEq0 TKbg== X-Gm-Message-State: AOAM533uAm/cmrbj78iTsVpG5Jmc6+MZDBs88ITrFwtW+sl8F+DGC44a 1BpOLla7schGr7Qv07RyGQiZMuOkXJc= X-Google-Smtp-Source: ABdhPJxSBdY6hbi//KbQe9I0lyscBFIqXh3xAe/FrtPE+RexbTCwEa6gvalWtrisbW+UpCGWMSssIw== X-Received: by 2002:a7b:c41a:: with SMTP id k26mr1114301wmi.1.1611086049988; Tue, 19 Jan 2021 11:54:09 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id r2sm39046401wrn.83.2021.01.19.11.54.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jan 2021 11:54:09 -0800 (PST) Message-Id: <7c24f9f7aedc57c08cc1d12141590d8a83f1c72e.1611086033.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 19 Jan 2021 19:53:53 +0000 Subject: [PATCH v3 17/17] merge-ort: fix a directory rename detection bug Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Taylor Blau , Elijah Newren , 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 7314f9c69c2..3192b27625e 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,20 +955,12 @@ 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]; /* File not part of directory rename if it wasn't renamed */ 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} @@ -1001,12 +968,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); } }