From patchwork Mon Nov 2 20:43:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875263 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 14D4DC388F9 for ; Mon, 2 Nov 2020 20:46:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A2F75206E5 for ; Mon, 2 Nov 2020 20:46:17 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dXl6UQtl" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727308AbgKBUoe (ORCPT ); Mon, 2 Nov 2020 15:44:34 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51318 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726711AbgKBUnw (ORCPT ); Mon, 2 Nov 2020 15:43:52 -0500 Received: from mail-ot1-x341.google.com (mail-ot1-x341.google.com [IPv6:2607:f8b0:4864:20::341]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 11F63C0617A6 for ; Mon, 2 Nov 2020 12:43:52 -0800 (PST) Received: by mail-ot1-x341.google.com with SMTP id h62so13889113oth.9 for ; Mon, 02 Nov 2020 12:43:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=iDmmdb1yMbAVf8rdFEjA/Su1MuMpaeeULyOhTaFe/Yc=; b=dXl6UQtlQ2sDQyri5OFPjbt6NhtlmuyK3t4lNbh2C+nV20ApevilPETWQo7qddU2E+ vFZtGnKdNDt3+bBflnO85CULK9v5aSZeeAciq3jLF+VL5toY3txZ6Z5xTXi1wtosFP4N zozfLVrSB7hnD3txzYZKlEGQt6h75Lt7wJaCk1Z4QlKgoRYXH39wufw6Ov+oSjJCaEzx ZiwtlBcoy8MmnLvjnIRx3eycqhp00XROvX0DZRKcck21y6TMQ2f+10WYBngIQoemOfE0 l6xSMvnEodwk+CXGAz+otFGfR2NBEG9ombvzia9dsBAqC2lYjE4R3K3BgPpYu9+lc44i Auvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=iDmmdb1yMbAVf8rdFEjA/Su1MuMpaeeULyOhTaFe/Yc=; b=Qm5bcVy5AF64/PhjPsy1Q4c60Tpb/kwouOsgXVML1FMVCzFZEnpg7oxf+tAEKBDG+U B107rxeOTkM75OjaaCe38ICVPpLxQKxczpyKWiUbATPRQZxYJXLS8yFqZxvZl6Wsm8xW MWjno+ddQ/+rLL2qie5CJSYYysYJJ5qhB4x2e+8ce2KjtLxgzHCYocoJGL7KV/gbou34 iq0EwPjPDK89TyJFugz2VWlkJTRlqD/bopIEVQxLh4YJjwSgxQsQbf3SGU/nUK7V19pt FkS8utSIlXT1+llCIkQJE4zvIEnOkgcrYQFmmN2la9vUoEBlGdl0eVK/CtVWBGQNFASP BjLw== X-Gm-Message-State: AOAM530MCy3maKWGWfj3P3xLZDJMB31OJ/4H5x+zz1jumSBmqQzuVDki 9CkR5gu8nEs3kK6xiOoCB+kEyPXxMwF64A== X-Google-Smtp-Source: ABdhPJzBSC6xzlyv+QVRiquoyCuk8CNc3Xk5DWqRgYe4HCMO80+gxcKAeiuFOMRo8HN2J+tEruf85A== X-Received: by 2002:a05:6830:2143:: with SMTP id r3mr4388680otd.189.1604349830746; Mon, 02 Nov 2020 12:43:50 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:50 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 01/20] merge-ort: setup basic internal data structures Date: Mon, 2 Nov 2020 12:43:25 -0800 Message-Id: <20201102204344.342633-2-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Set up some basic internal data structures. The only carry-over from merge-recursive.c is call_depth, though needed_rename_limit will be added later. The central piece of data will definitely be the strmap "paths", which will map every relevant pathname under consideration to either a merged_info or a conflict_info. ("unmerged" is a strmap that is a subset of "paths".) merged_info contains all relevant information for a non-conflicted entry. conflict_info contains a merged_info, plus any additional information about a conflict such as the higher orders stages involved and the names of the paths those came from (handy once renames get involved). If an entry remains conflicted, the merged_info portion of a conflict_info will later be filled with whatever version of the file should be placed in the working directory (e.g. an as-merged-as-possible variation that contains conflict markers). Signed-off-by: Elijah Newren --- merge-ort.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index b487901d3e..9d5ea0930d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -17,6 +17,46 @@ #include "cache.h" #include "merge-ort.h" +#include "strmap.h" + +struct merge_options_internal { + struct strmap paths; /* maps path -> (merged|conflict)_info */ + struct strmap unmerged; /* maps path -> conflict_info */ + const char *current_dir_name; + int call_depth; +}; + +struct version_info { + struct object_id oid; + unsigned short mode; +}; + +struct merged_info { + struct version_info result; + unsigned is_null:1; + unsigned clean:1; + size_t basename_offset; + /* + * Containing directory name. Note that we assume directory_name is + * constructed such that + * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name, + * i.e. string equality is equivalent to pointer equality. For this + * to hold, we have to be careful setting directory_name. + */ + const char *directory_name; +}; + +struct conflict_info { + struct merged_info merged; + struct version_info stages[3]; + const char *pathnames[3]; + unsigned df_conflict:1; + unsigned path_conflict:1; + unsigned filemask:3; + unsigned dirmask:3; + unsigned match_mask:3; +}; + void merge_switch_to_result(struct merge_options *opt, struct tree *head, struct merge_result *result, From patchwork Mon Nov 2 20:43:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875261 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3EFA6C2D0A3 for ; Mon, 2 Nov 2020 20:46:35 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EB031206E5 for ; Mon, 2 Nov 2020 20:46:34 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="pyzTSyqf" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727301AbgKBUod (ORCPT ); Mon, 2 Nov 2020 15:44:33 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51320 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726878AbgKBUnw (ORCPT ); Mon, 2 Nov 2020 15:43:52 -0500 Received: from mail-ot1-x341.google.com (mail-ot1-x341.google.com [IPv6:2607:f8b0:4864:20::341]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 91FC1C0617A6 for ; Mon, 2 Nov 2020 12:43:52 -0800 (PST) Received: by mail-ot1-x341.google.com with SMTP id y22so3416772oti.10 for ; Mon, 02 Nov 2020 12:43:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=T+XG60ElO52BdiW2lH9zi9v/2gK1c0M/S/IJh6MzwkQ=; b=pyzTSyqfA4y4WnxqA4N4lUkj4Uh85XqOM5BJkpjUbo213T+Slq0G1vR5jvxIINTox1 zjzWFhnij4eCg6n96sGcAuZ71Si0twANTLgnDpHHIu755lveC58FSKIjcnNVfAKoPMEw YuGZN7kCSnUu3ZoRAsQ2HwGvauWrMm3VCrW/ChESSW8hq3Jtownh7k82IaG20ZV4V45v bN4ue994Jd7IS2mf/Ob0xMUFJY+XrzJbPQStqmfcf/9ev2Ih0rUmMJ3G1kIXmcQVKdAi n1JXTfc4Do/JqSJUHbGupMfuTOw/qD7bnmVYeqwtmqYFLrmIjOLHrZtdHSuC7v71/gWp FpBA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=T+XG60ElO52BdiW2lH9zi9v/2gK1c0M/S/IJh6MzwkQ=; b=VMe9H3L+kiJOYAh8rIvXpQJJgUFNPaHUAqkF6W1SGOKqFWesx8Q34GXK/qn7x3aI6y 00v84NJcjd1Pq/EwmnUdeRc0Rd+d568u+LromClxJO6gNEz1mcbBFgF7r35G0oQvfhH7 3LhgcsvJdyc8AI4vnf8lj0PmRxfWx8fYOD6E2D6V5gC4Im1F2GQy+QdZFBq4gbrl3qnD g7VkFt+wSz0bm7j/UeFX/YIY0TAuOt0q5IBLZPPOiWbBM1L6sDqs1YQLsohXu9k4JZY9 AojImlBA0ZMTbPftmx2m8iCPHUHk0uyf/ubmX19JlB8/U9SGoUU5fY3HRQzimL1xGu6T sfnw== X-Gm-Message-State: AOAM530OwM52qykpeIAtxgpiegDxJFwqFn6i41tZWyk69LaHOWB2Ii9L alqhFMXeihsE3PIub6eoaureBozM/sykBg== X-Google-Smtp-Source: ABdhPJxmvORgzYkvjhGWh2J4hty0vQScpF0lHO1nPrb8wj2DVypvIDdnMpgDo/kS3zfVn0UvtvEr4w== X-Received: by 2002:a05:6830:18e6:: with SMTP id d6mr13051547otf.60.1604349831779; Mon, 02 Nov 2020 12:43:51 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:51 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 02/20] merge-ort: add some high-level algorithm structure Date: Mon, 2 Nov 2020 12:43:26 -0800 Message-Id: <20201102204344.342633-3-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org merge_ort_nonrecursive_internal() will be used by both merge_inmemory_nonrecursive() and merge_inmemory_recursive(); let's focus on it for now. It involves some setup -- merge_start() -- followed by the following chain of functions: collect_merge_info() This function will populate merge_options_internal's paths field, via a call to traverse_trees() and a new callback that will be added later. detect_and_process_renames() This function will detect renames, and then adjust entries in paths to move conflict stages from old pathnames into those for new pathnames, so that the next step doesn't have to think about renames and just can do three-way content merging and such. process_entries() This function determines how to take the various stages (versions of a file from the three different sides) and merge them, and whether to mark the result as conflicted or cleanly merged. It also writes out these merged file versions as it goes to create a tree. 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 9d5ea0930d..b53cd80104 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -18,6 +18,7 @@ #include "merge-ort.h" #include "strmap.h" +#include "tree.h" struct merge_options_internal { struct strmap paths; /* maps path -> (merged|conflict)_info */ @@ -57,6 +58,37 @@ struct conflict_info { unsigned match_mask:3; }; +static int collect_merge_info(struct merge_options *opt, + struct tree *merge_base, + struct tree *side1, + struct tree *side2) +{ + die("Not yet implemented."); +} + +static int detect_and_process_renames(struct merge_options *opt, + struct tree *merge_base, + struct tree *side1, + struct tree *side2) +{ + int clean = 1; + + /* + * Rename detection works by detecting file similarity. Here we use + * a really easy-to-implement scheme: files are similar IFF they have + * the same filename. Therefore, by this scheme, there are no renames. + * + * TODO: Actually implement a real rename detection scheme. + */ + return clean; +} + +static void process_entries(struct merge_options *opt, + struct object_id *result_oid) +{ + die("Not yet implemented."); +} + void merge_switch_to_result(struct merge_options *opt, struct tree *head, struct merge_result *result, @@ -73,13 +105,46 @@ void merge_finalize(struct merge_options *opt, die("Not yet implemented"); } +static void merge_start(struct merge_options *opt, struct merge_result *result) +{ + die("Not yet implemented."); +} + +/* + * Originally from merge_trees_internal(); heavily adapted, though. + */ +static void merge_ort_nonrecursive_internal(struct merge_options *opt, + struct tree *merge_base, + struct tree *side1, + struct tree *side2, + struct merge_result *result) +{ + struct object_id working_tree_oid; + + collect_merge_info(opt, merge_base, side1, side2); + result->clean = detect_and_process_renames(opt, merge_base, + side1, side2); + process_entries(opt, &working_tree_oid); + + /* Set return values */ + result->tree = parse_tree_indirect(&working_tree_oid); + /* existence of unmerged entries implies unclean */ + result->clean &= strmap_empty(&opt->priv->unmerged); + if (!opt->priv->call_depth) { + result->priv = opt->priv; + opt->priv = NULL; + } +} + void merge_incore_nonrecursive(struct merge_options *opt, struct tree *merge_base, struct tree *side1, struct tree *side2, struct merge_result *result) { - die("Not yet implemented"); + assert(opt->ancestor != NULL); + merge_start(opt, result); + merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result); } void merge_incore_recursive(struct merge_options *opt, From patchwork Mon Nov 2 20:43:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875259 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3684FC388F9 for ; Mon, 2 Nov 2020 20:46:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DA81F22226 for ; Mon, 2 Nov 2020 20:46:35 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="R5Su15nH" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727298AbgKBUod (ORCPT ); Mon, 2 Nov 2020 15:44:33 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51324 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726889AbgKBUnx (ORCPT ); Mon, 2 Nov 2020 15:43:53 -0500 Received: from mail-ot1-x343.google.com (mail-ot1-x343.google.com [IPv6:2607:f8b0:4864:20::343]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8E000C0617A6 for ; Mon, 2 Nov 2020 12:43:53 -0800 (PST) Received: by mail-ot1-x343.google.com with SMTP id m26so13886739otk.11 for ; Mon, 02 Nov 2020 12:43:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=gHp7pGdtJLpf4WZA/d366+a7XIvMZibD4On6OHEyQ+U=; b=R5Su15nHYCRUXTIywYCEJnFVLogdiqlJHw3lUeUBgs/fujaHtfPh9QcbnDhA5pJBP7 EmJxTZMhfhMceYuJiqUGEPT4lSTGfwN/KP3TTcK26GtskWE5aL4JQaIg4dtW0EaehrHt Dl8YEk3Ceq1mHqY9G4HY75aw62ryEUH0FQqsUqlD0oJtmAr5OMrq/Y8EBMzF8QYUiL/9 8PD1H8UMgmqdNJws5G29l5CdSX5cR5XDeIJOry3NdxCAkTK4C1RdZf+Cz3M3d4CNbT8R /dxX53SbkNWCnZNgvYQbW8R47GXnoTJQrZAXBUQWupqMubRAEy93kwtTQjyiNagtcKp0 wzbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=gHp7pGdtJLpf4WZA/d366+a7XIvMZibD4On6OHEyQ+U=; b=CdA/U58NoyxIKqiURIzKA+1n3QKODyGnzDZQVwRUOF30pOMSpbhmjFKuH260sJVEcM 77WldJz8WcQ0QHUGG4dPvODHoqMyfJC4MQY/AAsEgBLpk2tzxRJyy2w2feefYYhwkTWK 1oajcRTY0e3bWgrURb4gq5oN6EzIfDVsY/U7ama9+fZgje7yO9cz7WNVbTB0dgeJuR2y 20Kzpr6pmLgyWfAfTDu/9ltwgm43Ig2HC0aSVz42EatuS9i53a2tsanSNdTutFsNX3e1 +a9gJa/ibNmK+7Fdb+F2G6NINWVq3zx8k/INcrYroIoZK1PdkrJCAOo/F5fmrARijasu qIWg== X-Gm-Message-State: AOAM530FGEvLHOty6BdTH8P+h/xpx3thJu5jHrxQnOZes00q+tBXW4iR 47jdnt/zcXFmSm5n/vVk9bugAwqa8YRU9g== X-Google-Smtp-Source: ABdhPJyxhadgFaQXawpWYgoqyT4oM9QP2BH/nLmD/lJ9ax9TNKKdMLwgjJDgNfJ50B3LczOueDhsQA== X-Received: by 2002:a9d:3ef7:: with SMTP id b110mr13021263otc.333.1604349832799; Mon, 02 Nov 2020 12:43:52 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:52 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 03/20] merge-ort: port merge_start() from merge-recursive Date: Mon, 2 Nov 2020 12:43:27 -0800 Message-Id: <20201102204344.342633-4-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org merge_start() basically does a bunch of sanity checks, then allocates and initializes opt->priv -- a struct merge_options_internal. Most the sanity checks are usable as-is. The allocation/intialization is a bit different since merge-ort has a very different merge_options_internal than merge-recursive, but the idea is the same. The weirdest part here is that merge-ort and merge-recursive use the same struct merge_options, even though merge_options has a number of fields that are oddly specific to merge-recursive's internal implementation and don't even make sense with merge-ort's high-level design (e.g. buffer_output, which merge-ort has to always do). I reused the same data structure because: * most the fields made sense to both merge algorithms * making a new struct would have required making new enums or somehow externalizing them, and that was getting messy. * it simplifies converting the existing callers by not having to have different code paths for merge_options setup. I also marked detect_renames as ignored. We can revisit that later, but in short: merge-recursive allowed turning off rename detection because it was sometimes glacially slow. When you speed something up by a few orders of magnitude, it's worth revisiting whether that justification is still relevant. Besides, if folks find it's still too slow, perhaps they have a better scaling case than I could find and maybe it turns up some more optimizations we can add. If it still is needed as an option, it is easy to add later. Signed-off-by: Elijah Newren --- merge-ort.c | 44 +++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index b53cd80104..f5460a8a52 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -17,6 +17,8 @@ #include "cache.h" #include "merge-ort.h" +#include "diff.h" +#include "diffcore.h" #include "strmap.h" #include "tree.h" @@ -107,7 +109,47 @@ void merge_finalize(struct merge_options *opt, static void merge_start(struct merge_options *opt, struct merge_result *result) { - die("Not yet implemented."); + /* Sanity checks on opt */ + assert(opt->repo); + + assert(opt->branch1 && opt->branch2); + + assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE && + opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE); + assert(opt->rename_limit >= -1); + assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE); + assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1); + + assert(opt->xdl_opts >= 0); + assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL && + opt->recursive_variant <= MERGE_VARIANT_THEIRS); + + /* + * detect_renames, verbosity, buffer_output, and obuf are ignored + * fields that were used by "recursive" rather than "ort" -- but + * sanity check them anyway. + */ + assert(opt->detect_renames >= -1 && + opt->detect_renames <= DIFF_DETECT_COPY); + assert(opt->verbosity >= 0 && opt->verbosity <= 5); + assert(opt->buffer_output <= 2); + assert(opt->obuf.len == 0); + + assert(opt->priv == NULL); + + /* Initialization of opt->priv, our internal merge data */ + opt->priv = xcalloc(1, sizeof(*opt->priv)); + /* + * Although we initialize opt->priv->paths with strdup_strings=0, + * that's just to avoid making yet another copy of an allocated + * string. Putting the entry into paths means we are taking + * ownership, so we will later free it. + * + * In contrast, unmerged just has a subset of keys from paths, so + * we don't want to free those (it'd be a duplicate free). + */ + strmap_init_with_options(&opt->priv->paths, NULL, 0); + strmap_init_with_options(&opt->priv->unmerged, NULL, 0); } /* From patchwork Mon Nov 2 20:43:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875257 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 47504C00A89 for ; Mon, 2 Nov 2020 20:46:37 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F25C822226 for ; Mon, 2 Nov 2020 20:46:36 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="J42FBMUF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727289AbgKBUoc (ORCPT ); Mon, 2 Nov 2020 15:44:32 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51332 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726928AbgKBUny (ORCPT ); Mon, 2 Nov 2020 15:43:54 -0500 Received: from mail-oi1-x241.google.com (mail-oi1-x241.google.com [IPv6:2607:f8b0:4864:20::241]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7E29CC0617A6 for ; Mon, 2 Nov 2020 12:43:54 -0800 (PST) Received: by mail-oi1-x241.google.com with SMTP id s21so16084331oij.0 for ; Mon, 02 Nov 2020 12:43:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=R3C39cbVAfVBp4LfrVFtVfvoxVJX09siz6Mw9R93DkU=; b=J42FBMUFUWYyZ9jju4EO3GsBZOwDvv0vBllJe6cAfM28tAql+6v1kgmjW/6F0W8Zn+ /CS2OvDPaI9ur+YYOcPokJgQvitRaZpFP3a5bRr/uWvVRwR9yiFuXUuIXdrkideo46Tk YAidCp432YyWD44UmVShmvIpsqbVtQIgevGtgvYEMPnU7jl3rKURTgt/a24gWpnpHurj x5TrVQXrBuJP/ti0pxuaj+x1pWNxrqoX0D1v8tGOUiAJVURD1otHv3BgRY+oAr9uHXVt Yte48TBFsIlcUJ9QCT/6/AhoYF9CeXtmu/IA39jin+o4XvynAbcOZJ5ZNU55VMEfWmaS Ypkg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=R3C39cbVAfVBp4LfrVFtVfvoxVJX09siz6Mw9R93DkU=; b=U/iSChqz+7kWMfAnBqS8XW781cPBtkUA3aPyTBglwz526PMABVhnVuK1+1j3bxsWJj m+ESqzUla3PNfVwOXpMvhqBzH974a0C8s1aDF6p/y+3JirtCo7LJ5Jjgylx9OuMAP/uj pjwhWcOxzG9wFpE8CUVtQBKUC4OSMRwNNRnNX8It9kn5XCe8Pkx6fzUp0D5EaHIE6Lfw aM5AtOaceecCP0nOyqtx/eBV9XzOdDhU9wBtfL7OF5Zr5+iLaCtutoYTsZFF6pDjQHYf Xw9VG7vdiD+4pRorsyy90n56XqEpHBmWtdXu4QCwaBsnRkRVwDABoM0q3/oIIWENM/Xs 3k6A== X-Gm-Message-State: AOAM533pIdOF13OmWdr6p+gAM6FqU0lAQcp5qr1KnJIIIEuLlr1yBRke VgGJHjbHafNyizB32x5mvCInUrMjRmdDYg== X-Google-Smtp-Source: ABdhPJz6aRLuP73XScjIc1mI6Wrlr760pBIY+It4XDlSsc+bok8zI20zRpuL7VtBtTtYkspd73LuXQ== X-Received: by 2002:aca:3b0a:: with SMTP id i10mr11821429oia.167.1604349833781; Mon, 02 Nov 2020 12:43:53 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:53 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 04/20] merge-ort: use histogram diff Date: Mon, 2 Nov 2020 12:43:28 -0800 Message-Id: <20201102204344.342633-5-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org I have some ideas for using a histogram diff to improve content merges, which fundamentally relies on the idea of a histogram. Since the diffs are never displayed to the user but just used internally for merging, the typical user preference shouldn't matter anyway, and I want to make sure that all my testing works with this algorithm. Granted, I don't yet know if those ideas will pan out and I haven't even tried any of them out yet, but it's easy to change the diff algorithm in the future if needed or wanted. For now, just set it to histogram. Signed-off-by: Elijah Newren --- merge-ort.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index f5460a8a52..df97a54773 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -21,6 +21,7 @@ #include "diffcore.h" #include "strmap.h" #include "tree.h" +#include "xdiff-interface.h" struct merge_options_internal { struct strmap paths; /* maps path -> (merged|conflict)_info */ @@ -137,6 +138,9 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) assert(opt->priv == NULL); + /* Default to histogram diff. Actually, just hardcode it...for now. */ + opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF); + /* Initialization of opt->priv, our internal merge data */ opt->priv = xcalloc(1, sizeof(*opt->priv)); /* From patchwork Mon Nov 2 20:43:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875255 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5F949C388F9 for ; Mon, 2 Nov 2020 20:44:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 19F892071A for ; Mon, 2 Nov 2020 20:44:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ku9NgP+W" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727265AbgKBUo0 (ORCPT ); Mon, 2 Nov 2020 15:44:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51336 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726938AbgKBUn5 (ORCPT ); Mon, 2 Nov 2020 15:43:57 -0500 Received: from mail-ot1-x343.google.com (mail-ot1-x343.google.com [IPv6:2607:f8b0:4864:20::343]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8E83BC0617A6 for ; Mon, 2 Nov 2020 12:43:55 -0800 (PST) Received: by mail-ot1-x343.google.com with SMTP id b2so13899309ots.5 for ; Mon, 02 Nov 2020 12:43:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=+kCVfyu3obAf7EB+v3Qn0Io5JqSinEA44RPCaVFdqPE=; b=ku9NgP+WfAigpa2tmCo4xgp3Y5qAvdoMhG4O3e3LNfLguWcYR24BFAlJE+ed9ZQOxp XvqaAvXUTKcuuZLURUoyyzLi9eHp+x8o+oKvouhxEmhVSXULv2L/T5/aCEN01PPAo7KK kB4A+x9Af/BSkQFoJLONN/csR4yQ1vCJVOvGXlzk7uFKafTOeIJUaRBPA3JzyX8/1JvP Lwy8k/7rRsfO7kDzkVmDEPwXOlgEKD8M/6+zsgJ938nQrDeEsdtwKUKXQKDF0cqh/ZU8 KEk/TFMK3dZVnJ4n8oiBi3uHBJNhJFVNhpkGbgz/6Ad1t46Xh5DxINiqPWrpUAcdRXo/ KnYQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=+kCVfyu3obAf7EB+v3Qn0Io5JqSinEA44RPCaVFdqPE=; b=YKM5sGGQVmL4rNn6JWu6UO89SzohlW1KIWRDEQmtO0Z72DOZMphkfp6YAEF28Y4b6+ fbPVXQFvZ8rjvoUCIK0WB9qC9OXnXpb+16/s0en0M/s3H/ASB+9CYMYl09VpQFEKw1M/ EBEdmktpEZoF01/ldjd7dhND+jMCspsAegudQuHpeZJXjFZEKtPt6drQpanEP4pCUBet ubCUVkHaV/lbfTZDiW2U43AN9hSswm1Nn2yBvC/N8SYBc0za2Crl0gxAyvx3Ipv5/iry VibBnC3LMhU/GGeuaTUOtwO9op2mR6UGFCINyR1VvlyfFa2I3iDdmxWRcNeQorA/pmQS zMXQ== X-Gm-Message-State: AOAM530cx/CqVqCMdER+MTLcBXRTOTbB5PsDI9i3j0bGSMEW8xqTsPDI hyzDTDf6qyxwBeIbT+c1anPlmmE/iOOtPA== X-Google-Smtp-Source: ABdhPJwGHeIYv62NKoDnzoGFgxW8REs8u7J7YMaYzaHjRTCViz45YTyQ/aRUveCnSo6jl2CTpeKztA== X-Received: by 2002:a9d:6f96:: with SMTP id h22mr12647598otq.344.1604349834741; Mon, 02 Nov 2020 12:43:54 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:54 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 05/20] merge-ort: add an err() function similar to one from merge-recursive Date: Mon, 2 Nov 2020 12:43:29 -0800 Message-Id: <20201102204344.342633-6-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Various places in merge-recursive used an err() function when it hit some kind of unrecoverable error. That code was from the reusable bits of merge-recursive.c that we liked, such as merge_3way, writing object files to the object store, reading blobs from the object store, etc. So create a similar function to allow us to port that code over, and use it for when we detect problems returned from collect_merge_info()'s traverse_trees() call, which we will be adding next. Signed-off-by: Elijah Newren --- merge-ort.c | 27 ++++++++++++++++++++++++++- 1 file changed, 26 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index df97a54773..537da9f6df 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -61,11 +61,28 @@ struct conflict_info { unsigned match_mask:3; }; +static int err(struct merge_options *opt, const char *err, ...) +{ + va_list params; + struct strbuf sb = STRBUF_INIT; + + strbuf_addstr(&sb, "error: "); + va_start(params, err); + strbuf_vaddf(&sb, err, params); + va_end(params); + + error("%s", sb.buf); + strbuf_release(&sb); + + return -1; +} + static int collect_merge_info(struct merge_options *opt, struct tree *merge_base, struct tree *side1, struct tree *side2) { + /* TODO: Implement this using traverse_trees() */ die("Not yet implemented."); } @@ -167,7 +184,15 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt, { struct object_id working_tree_oid; - collect_merge_info(opt, merge_base, side1, side2); + if (collect_merge_info(opt, merge_base, side1, side2) != 0) { + err(opt, _("collecting merge info failed for trees %s, %s, %s"), + oid_to_hex(&merge_base->object.oid), + oid_to_hex(&side1->object.oid), + oid_to_hex(&side2->object.oid)); + result->clean = -1; + return; + } + result->clean = detect_and_process_renames(opt, merge_base, side1, side2); process_entries(opt, &working_tree_oid); From patchwork Mon Nov 2 20:43:30 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875265 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2A563C00A89 for ; Mon, 2 Nov 2020 20:50:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id ACA2E20657 for ; Mon, 2 Nov 2020 20:50:08 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="uHb8Nm3o" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727273AbgKBUoc (ORCPT ); Mon, 2 Nov 2020 15:44:32 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51340 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726891AbgKBUn4 (ORCPT ); Mon, 2 Nov 2020 15:43:56 -0500 Received: from mail-ot1-x344.google.com (mail-ot1-x344.google.com [IPv6:2607:f8b0:4864:20::344]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9DB47C061A04 for ; Mon, 2 Nov 2020 12:43:56 -0800 (PST) Received: by mail-ot1-x344.google.com with SMTP id m26so13886876otk.11 for ; Mon, 02 Nov 2020 12:43:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=rUMDrTyhb8V1OQJgYcoUPDmGl3I7A/HB3XR5aMuKYDU=; b=uHb8Nm3o82JtEsuJNG4+6oNZh68XLmWlmTW5cU4UuitEqPsPbnt8UuH6NIfBgxjq0G BYEGfV5VnNmfOBzd7csl5IpHe0EYbR/tuJk0ZbCIJxDA+w7hDNiokxY9DSTPLZLaJ5r0 vIn1P3FuuqiKirNqhxyHQ7q3c1hdw16bNij+npf+1BYvAZiQRBEvLaIXJNBGatU4/VF+ teBbLkRXbPX7zwXxpmmf2IuVms01d9Wq9A7BbyIlFXD+bWyNSOSgmJQBWdq/w0ju/1n/ 5g6En+YHGhnOkXjtL5TMvm9zxF3gYzAneI62ilL6RB0F7u4TtNUpESpeMloQega/Vw9c yuHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=rUMDrTyhb8V1OQJgYcoUPDmGl3I7A/HB3XR5aMuKYDU=; b=XxYfNFuGT/XDDE52rqs0j35ssgQfcMJAEKkbeJT1sFwFeUtZvifDYtLkmT4pWPsx7a 7/7D4oFxwzOwGL+gT7pIPsKXbL3Sgxc8zcEEp5JEpNrKhQCvIjt/wVe6z+YumXcT+Qqg q/Zn7kOaW1iZGFj7+HMwRYCMrxQ3XiWKUVuQoOqkMGdO2MO7woBG9MQhdQwoGnQPx2Kf MMYYWNe9Gn0DmXwvN2BP8bvyKcTO8ri2qDzzxvJaF1g5wVfUKm1KltH6+AsGNPEYKnpq BNQpunNJApoPKwnCqXCF5zx+pw6mJ23L+PS1AM5PR68ypvvATNaGIIcvMWVqrAQo5lCj QUXQ== X-Gm-Message-State: AOAM532XC4tfGlMyjf78NMKoLJ5eVLapDX5qlp4298oBoScQWchIDBFX 2SJHowDuoBdw4/rjUkccGXy36qWhVOjZtw== X-Google-Smtp-Source: ABdhPJzhbFw/kca6fYrc9tEmg5JGX0axm23xdhX0iOlNP87PyZnOSB2ZYNCPVW6XWT2If6KEbDRPOg== X-Received: by 2002:a05:6830:154e:: with SMTP id l14mr12721242otp.291.1604349835816; Mon, 02 Nov 2020 12:43:55 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:55 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 06/20] merge-ort: implement a very basic collect_merge_info() Date: Mon, 2 Nov 2020 12:43:30 -0800 Message-Id: <20201102204344.342633-7-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This does not actually collect any necessary info other than the pathnames involved, since it just allocates an all-zero conflict_info and stuffs that into paths. However, it invokes the traverse_trees() machinery to walk over all the paths and sets up the basic infrastructure we need. I have left out a few obvious optimizations to try to make this patch as short and obvious as possible. A subsequent patch will add some of those back in with some more useful data fields before we introduce a patch that actually sets up the conflict_info fields. Signed-off-by: Elijah Newren --- merge-ort.c | 121 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 119 insertions(+), 2 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 537da9f6df..626eb9713e 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -77,13 +77,130 @@ static int err(struct merge_options *opt, const char *err, ...) return -1; } +static int collect_merge_info_callback(int n, + unsigned long mask, + unsigned long dirmask, + struct name_entry *names, + struct traverse_info *info) +{ + /* + * n is 3. Always. + * common ancestor (mbase) has mask 1, and stored in index 0 of names + * head of side 1 (side1) has mask 2, and stored in index 1 of names + * head of side 2 (side2) has mask 4, and stored in index 2 of names + */ + struct merge_options *opt = info->data; + struct merge_options_internal *opti = opt->priv; + struct conflict_info *ci; + struct name_entry *p; + size_t len; + char *fullpath; + unsigned filemask = mask & ~dirmask; + unsigned mbase_null = !(mask & 1); + unsigned side1_null = !(mask & 2); + unsigned side2_null = !(mask & 4); + + /* n = 3 is a fundamental assumption. */ + if (n != 3) + BUG("Called collect_merge_info_callback wrong"); + + /* + * A bunch of sanity checks verifying that traverse_trees() calls + * us the way I expect. Could just remove these at some point, + * though maybe they are helpful to future code readers. + */ + assert(mbase_null == is_null_oid(&names[0].oid)); + assert(side1_null == is_null_oid(&names[1].oid)); + assert(side2_null == is_null_oid(&names[2].oid)); + assert(!mbase_null || !side1_null || !side2_null); + assert(mask > 0 && mask < 8); + + /* Other invariant checks, mostly for documentation purposes. */ + assert(mask == (dirmask | filemask)); + + /* + * Get the name of the relevant filepath, which we'll pass to + * setup_path_info() for tracking. + */ + p = names; + while (!p->mode) + p++; + len = traverse_path_len(info, p->pathlen); + + /* +1 in both of the following lines to include the NUL byte */ + fullpath = xmalloc(len+1); + make_traverse_path(fullpath, len+1, info, p->path, p->pathlen); + + /* + * TODO: record information about the path other than all zeros, + * so we can resolve later in process_entries. + */ + ci = xcalloc(1, sizeof(struct conflict_info)); + strmap_put(&opti->paths, fullpath, ci); + + /* If dirmask, recurse into subdirectories */ + if (dirmask) { + struct traverse_info newinfo; + struct tree_desc t[3]; + void *buf[3] = {NULL,}; + const char *original_dir_name; + int i, ret; + + ci->match_mask &= filemask; + newinfo = *info; + newinfo.prev = info; + newinfo.name = p->path; + newinfo.namelen = p->pathlen; + newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1); + + for (i = 0; i < 3; i++, dirmask >>= 1) { + const struct object_id *oid = NULL; + if (dirmask & 1) + oid = &names[i].oid; + buf[i] = fill_tree_descriptor(opt->repo, t + i, oid); + } + + original_dir_name = opti->current_dir_name; + opti->current_dir_name = fullpath; + ret = traverse_trees(NULL, 3, t, &newinfo); + opti->current_dir_name = original_dir_name; + + for (i = 0; i < 3; i++) + free(buf[i]); + + if (ret < 0) + return -1; + } + + return mask; +} + static int collect_merge_info(struct merge_options *opt, struct tree *merge_base, struct tree *side1, struct tree *side2) { - /* TODO: Implement this using traverse_trees() */ - die("Not yet implemented."); + int ret; + struct tree_desc t[3]; + struct traverse_info info; + char *toplevel_dir_placeholder = ""; + + opt->priv->current_dir_name = toplevel_dir_placeholder; + setup_traverse_info(&info, toplevel_dir_placeholder); + info.fn = collect_merge_info_callback; + info.data = opt; + info.show_all_errors = 1; + + parse_tree(merge_base); + parse_tree(side1); + parse_tree(side2); + init_tree_desc(t+0, merge_base->buffer, merge_base->size); + init_tree_desc(t+1, side1->buffer, side1->size); + init_tree_desc(t+2, side2->buffer, side2->size); + + ret = traverse_trees(NULL, 3, t, &info); + + return ret; } static int detect_and_process_renames(struct merge_options *opt, From patchwork Mon Nov 2 20:43:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875251 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A5FD2C2D0A3 for ; Mon, 2 Nov 2020 20:44:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5048B2071A for ; Mon, 2 Nov 2020 20:44:27 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lyFL0hfG" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727261AbgKBUoZ (ORCPT ); Mon, 2 Nov 2020 15:44:25 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51346 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726949AbgKBUn5 (ORCPT ); Mon, 2 Nov 2020 15:43:57 -0500 Received: from mail-oi1-x244.google.com (mail-oi1-x244.google.com [IPv6:2607:f8b0:4864:20::244]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8FE6CC0617A6 for ; Mon, 2 Nov 2020 12:43:57 -0800 (PST) Received: by mail-oi1-x244.google.com with SMTP id s21so16084483oij.0 for ; Mon, 02 Nov 2020 12:43:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=NY614d/h/vzCYSbEDOYPGjZwRMoxV7s7hSmK9PfVhQY=; b=lyFL0hfG7pqZJVac9VkgHGFNGzDyAD1BtTozor7unOWTuxZbC/Lq18zC9FZV+uhSeW fhT1eZgbOIMSX8mj2KevAw47t5h1joFH791vA92VWReloE/NLQMyMUjiVZC4pdxDczem ko2JHExeTVZudhE7mHMz/oMRbmJ/M5sVxKvgmCwOqP7E7e8RDP1Z+KYKQdmGlfx9xctO kZiAX2Z6sJTSUedvp92gl8fvTFrchiXrCqwhiKqNOhUKP58EzM2GL15S/U96AWDzL/G7 wUKNwcoL7Xo8w3MIin5N+2UEm9og4whQR7kY87CGAOD8DrgpknYRnLjuZYh498bPkHpL yfXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NY614d/h/vzCYSbEDOYPGjZwRMoxV7s7hSmK9PfVhQY=; b=f/arW0wRbMJ/tmNbDx6jA2nrQujbmn4c1clFuil1QOJxEFBz4f7gA03ZTdpTOqYGxG F2R8TbgvVBurD9F3maefgY1WnRw1AejofSNii9CPBqZ+E1s2qLZdYrtgSJ8A6nwkaWOh 5B41OFCFtCBAwaL/DRTUfAqdpMHFHDlKtKi/x8jAW2+SRJgDPSwYs8ZJs8LnO7TiFeBy NgHomP2miOjf3AXattr5tjep+XxdLQVqEPf9kWqxQeFNcbyTHCfmh7MQYZBuzeEtYo2P lgSAqJCPypUmG1ddMImzZaljjrjwA5q2cWdmsHVOVBygeuwOYu5zSLYX4laR1MJBD1S/ ZOTQ== X-Gm-Message-State: AOAM532tt5D3L4diUwAIiVWWTZxxbN5NfaV/WtbR170WDakp+cPnKSXY tSUpd4il58/dROx8MMqIdMuLC8GlkgeNgw== X-Google-Smtp-Source: ABdhPJygYJEnylgh4UxXeR2jB3AuXxDIGqm36i+XLgLmaRYofpiTX730I7dKbMa5eF7cDTuoGB7eBQ== X-Received: by 2002:aca:3343:: with SMTP id z64mr11670817oiz.45.1604349836851; Mon, 02 Nov 2020 12:43:56 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:56 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree Date: Mon, 2 Nov 2020 12:43:31 -0800 Message-Id: <20201102204344.342633-8-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Three-way merges, by their nature, are going to often have two or more trees match at a given subdirectory. We can avoid calling fill_tree_descriptor() on the same tree by checking when these trees match. Noting when various oids match will also be useful in other calculations and optimizations as well. Signed-off-by: Elijah Newren --- merge-ort.c | 26 ++++++++++++++++++++++---- 1 file changed, 22 insertions(+), 4 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 626eb9713e..d3c1d00fc6 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -99,6 +99,15 @@ static int collect_merge_info_callback(int n, unsigned mbase_null = !(mask & 1); unsigned side1_null = !(mask & 2); unsigned side2_null = !(mask & 4); + unsigned side1_matches_mbase = (!side1_null && !mbase_null && + names[0].mode == names[1].mode && + oideq(&names[0].oid, &names[1].oid)); + unsigned side2_matches_mbase = (!side2_null && !mbase_null && + names[0].mode == names[2].mode && + oideq(&names[0].oid, &names[2].oid)); + unsigned sides_match = (!side1_null && !side2_null && + names[1].mode == names[2].mode && + oideq(&names[1].oid, &names[2].oid)); /* n = 3 is a fundamental assumption. */ if (n != 3) @@ -154,10 +163,19 @@ static int collect_merge_info_callback(int n, newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1); for (i = 0; i < 3; i++, dirmask >>= 1) { - const struct object_id *oid = NULL; - if (dirmask & 1) - oid = &names[i].oid; - buf[i] = fill_tree_descriptor(opt->repo, t + i, oid); + if (i == 1 && side1_matches_mbase) + t[1] = t[0]; + else if (i == 2 && side2_matches_mbase) + t[2] = t[0]; + else if (i == 2 && sides_match) + t[2] = t[1]; + else { + const struct object_id *oid = NULL; + if (dirmask & 1) + oid = &names[i].oid; + buf[i] = fill_tree_descriptor(opt->repo, + t + i, oid); + } } original_dir_name = opti->current_dir_name; From patchwork Mon Nov 2 20:43:33 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875231 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E39F4C2D0A3 for ; Mon, 2 Nov 2020 20:44:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 862B622245 for ; Mon, 2 Nov 2020 20:44:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nGTKZYZW" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727145AbgKBUoL (ORCPT ); Mon, 2 Nov 2020 15:44:11 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51358 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726959AbgKBUn7 (ORCPT ); Mon, 2 Nov 2020 15:43:59 -0500 Received: from mail-oi1-x244.google.com (mail-oi1-x244.google.com [IPv6:2607:f8b0:4864:20::244]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BB710C061A04 for ; Mon, 2 Nov 2020 12:43:59 -0800 (PST) Received: by mail-oi1-x244.google.com with SMTP id u127so16032470oib.6 for ; Mon, 02 Nov 2020 12:43:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=llZ/sYfVCTbOwTTD+7xVMPnkot9bZxKUdVwXEV8C+tY=; b=nGTKZYZWugCu6ZXce2+hMQupvtdQ3ut3YdN45g7JxeyGaA0SiDA2OXKp1dvZaw9RqG TqISG1Ul6TgvTOCxF5n4rGSlIUdx9k0+zS0QEZsn3hajYdmQzpuArQ22dC2ii/4H4sBz P1RUlJ0uL9BERMbR7tuxiZBMWeRXsCLnq5DIzKyXcuzHr9cx6RajG3zBj00ZAzGPbm5P E/eEg2uDWwDAKSveODDLrHMdZMiDDe7/Ed/6VLTiEEyW8nIPmYveNZg5c+YcJVTESlnM evCumiYc70KOgIkcTDN4FxbUn3Zd1B/GDAe8TnWwEmdoFD8bQgvtWRRYUQVrCsSRYJ96 cpOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=llZ/sYfVCTbOwTTD+7xVMPnkot9bZxKUdVwXEV8C+tY=; b=EzzXsJ/ca47+oIapDSkI6QRbT8ebVX25WyByZCi69mht2kInuS9TL0JhTF36nzQS1c zrs+NmeoXBr90w3dBJxUH4FROd+VSQ00DgwHQXgz/STF+UsGMJyi8tOJ2hkWEfL3YVRM IYf9Omuk3wSdBr1K41qeVDROSOrUN4/nxMAvZhOlT/g52EWuuFlA+Ib0psd5wwMyuyw6 3E7kGhxqt9Ru+t+8CF1IvFhua2f+NDzYyIqhsFbS19SvDmXV9rEilQTse5/iqDw9Fp0M kHkQFKt3IFoUuv/l0Ctd4sYLwz2cyvgB+TELuMHTqKX3iKeGcatPiCO1KFOuie12oDng xpcA== X-Gm-Message-State: AOAM533IPlj02vvNJ4mFEGHwp6S6yfYF7OYSdeXCCfBeF2l3oB075gVc iVvIlz1rrBLtnU/0vy1a/KxvQi/luw2spg== X-Google-Smtp-Source: ABdhPJybBTiGRTl1nuA7+7n0P/izuqr8POkj8l3ouxNIvW2LTT6XKwbCJmpMQidGQbwSSxUOGUZNeA== X-Received: by 2002:aca:ab91:: with SMTP id u139mr6513oie.28.1604349838816; Mon, 02 Nov 2020 12:43:58 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:58 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 09/20] merge-ort: record stage and auxiliary info for every path Date: Mon, 2 Nov 2020 12:43:33 -0800 Message-Id: <20201102204344.342633-10-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Create a helper function, setup_path_info(), which can be used to record all the information we want in a merged_info or conflict_info. While there is currently only one caller of this new function, and some of its particular parameters are fixed, future callers of this function will be added later. Signed-off-by: Elijah Newren --- merge-ort.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 54 insertions(+), 7 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 0ff90981cf..bef3c648a0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -77,6 +77,51 @@ static int err(struct merge_options *opt, const char *err, ...) return -1; } +static void setup_path_info(struct merge_options *opt, + struct string_list_item *result, + const char *current_dir_name, + int current_dir_name_len, + char *fullpath, /* we'll take over ownership */ + struct name_entry *names, + struct name_entry *merged_version, + unsigned is_null, /* boolean */ + unsigned df_conflict, /* boolean */ + unsigned filemask, + unsigned dirmask, + int resolved /* boolean */) +{ + struct conflict_info *path_info; + + assert(!is_null || resolved); + assert(!df_conflict || !resolved); /* df_conflict implies !resolved */ + assert(resolved == (merged_version != NULL)); + + path_info = xcalloc(1, resolved ? sizeof(struct merged_info) : + sizeof(struct conflict_info)); + path_info->merged.directory_name = current_dir_name; + path_info->merged.basename_offset = current_dir_name_len; + path_info->merged.clean = !!resolved; + if (resolved) { + path_info->merged.result.mode = merged_version->mode; + oidcpy(&path_info->merged.result.oid, &merged_version->oid); + path_info->merged.is_null = !!is_null; + } else { + int i; + + for (i = 0; i < 3; i++) { + path_info->pathnames[i] = fullpath; + path_info->stages[i].mode = names[i].mode; + oidcpy(&path_info->stages[i].oid, &names[i].oid); + } + path_info->filemask = filemask; + path_info->dirmask = dirmask; + path_info->df_conflict = !!df_conflict; + } + strmap_put(&opt->priv->paths, fullpath, path_info); + result->string = fullpath; + result->util = path_info; +} + static int collect_merge_info_callback(int n, unsigned long mask, unsigned long dirmask, @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n, */ struct merge_options *opt = info->data; struct merge_options_internal *opti = opt->priv; - struct conflict_info *ci; + struct string_list_item pi; /* Path Info */ + struct conflict_info *ci; /* pi.util when there's a conflict */ struct name_entry *p; size_t len; char *fullpath; + const char *dirname = opti->current_dir_name; unsigned filemask = mask & ~dirmask; unsigned match_mask = 0; /* will be updated below */ unsigned mbase_null = !(mask & 1); @@ -157,13 +204,13 @@ static int collect_merge_info_callback(int n, make_traverse_path(fullpath, len+1, info, p->path, p->pathlen); /* - * TODO: record information about the path other than all zeros, - * so we can resolve later in process_entries. + * Record information about the path so we can resolve later in + * process_entries. */ - ci = xcalloc(1, sizeof(struct conflict_info)); - ci->df_conflict = df_conflict; + setup_path_info(opt, &pi, dirname, info->pathlen, fullpath, + names, NULL, 0, df_conflict, filemask, dirmask, 0); + ci = pi.util; ci->match_mask = match_mask; - strmap_put(&opti->paths, fullpath, ci); /* If dirmask, recurse into subdirectories */ if (dirmask) { @@ -204,7 +251,7 @@ static int collect_merge_info_callback(int n, } original_dir_name = opti->current_dir_name; - opti->current_dir_name = fullpath; + opti->current_dir_name = pi.string; ret = traverse_trees(NULL, 3, t, &newinfo); opti->current_dir_name = original_dir_name; From patchwork Mon Nov 2 20:43:34 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875241 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D42B6C00A89 for ; Mon, 2 Nov 2020 20:44:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6C254206E5 for ; Mon, 2 Nov 2020 20:44:09 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="VThpurWw" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727065AbgKBUoI (ORCPT ); Mon, 2 Nov 2020 15:44:08 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51360 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726988AbgKBUoC (ORCPT ); Mon, 2 Nov 2020 15:44:02 -0500 Received: from mail-oi1-x244.google.com (mail-oi1-x244.google.com [IPv6:2607:f8b0:4864:20::244]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 80CBFC0617A6 for ; Mon, 2 Nov 2020 12:44:00 -0800 (PST) Received: by mail-oi1-x244.google.com with SMTP id 9so16034132oir.5 for ; Mon, 02 Nov 2020 12:44:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=8o3sAg1zpz+tjQUlz9e4oByVDbFxIiaVgYiFPH3mUzE=; b=VThpurWw1efvpu3RmBccfY+dDl465zIhfpsu7TRKGETsDQXnGT0DyLjEY5dM3Bj7/8 Z3M5MV78B8aRIYsjrXfvVM9ZbJruIgFP0uTlRWfJOaV4UYnCtCX+lTMo1XITHgq5e13B lWYOHcor376WyjFiXDHM01WsfsB1LlZgIpayLiXjupjHqZ85XFxmnbxsx4exXsjKCBGX FxRkwYpBRYqJJdkpXKNKoBK7aSU0VQ8stnhYmiHq2ttolu67H3Wsdb08Pm+siEhYfN8f rR5q2FZybmMg0XwHvLye89pBCRJTZknS+qfSRUX3KlQ0Kk4elAoUwQbfV8mh3JkEBl7A i37w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=8o3sAg1zpz+tjQUlz9e4oByVDbFxIiaVgYiFPH3mUzE=; b=Ui9XJxRAT3urpSRby7iVwloZtHDr4qivujOBI02m6ivq8bEWII7pW00k+3eYROr3u3 u66wOC+mrrohEMPyvl/ROLC7SaaG8gh6uZHdhr0Ds4Fp8yjQxn0z395doOF7z9fU3qR3 OW36PSREsLJvJWebUMwM6tfClx1potB1RK3hy0VHzE1DSreN/AU8fpgRRxpHuE2bOdMW DKWmsW1d14lEhftonlNL1MHd29tUxj1vz6KN3NB3TaySzAKt90gjc3xKphdhlF/wJNiS yknlpuSyCGWcKqfcLvajLSlnoffS3n0k0M0zKHXj+SYWiizH9bPjYcCnSE8yCbwh1ZCD cwmA== X-Gm-Message-State: AOAM532KPuK2Mg/LjcwTKqluD48jT7k4wollQ/HE4ZSyKAA7RpgNnbs1 G/O9wE5ahe7N8q+h1iuPWiXRddhanC+Seg== X-Google-Smtp-Source: ABdhPJyQixbM9t1z9+F7WlPdX2VPyQfJS2irQmhfTOMBoiTYh8BmdTSnCc8xiRKJtj4BXPSw3tf+XQ== X-Received: by 2002:aca:bad4:: with SMTP id k203mr6334oif.16.1604349839791; Mon, 02 Nov 2020 12:43:59 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:43:59 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 10/20] merge-ort: avoid recursing into identical trees Date: Mon, 2 Nov 2020 12:43:34 -0800 Message-Id: <20201102204344.342633-11-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org When all three trees have the same oid, there is no need to recurse into these trees to find that all files within them happen to match. We can just record any one of the trees as the resolution of merging that particular path. Immediately resolving trees for other types of trivial tree merges (such as one side matches the merge base, or the two sides match each other) would prevent us from detecting renames for some paths, and thus prevent us from doing three-way content merges for those paths whose renames we did not detect. Signed-off-by: Elijah Newren --- merge-ort.c | 13 +++++++++++++ 1 file changed, 13 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index bef3c648a0..9900fa1bf8 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -203,6 +203,19 @@ static int collect_merge_info_callback(int n, fullpath = xmalloc(len+1); make_traverse_path(fullpath, len+1, info, p->path, p->pathlen); + /* + * If mbase, side1, and side2 all match, we can resolve early. Even + * if these are trees, there will be no renames or anything + * underneath. + */ + if (side1_matches_mbase && side2_matches_mbase) { + /* mbase, side1, & side2 all match; use mbase as resolution */ + setup_path_info(opt, &pi, dirname, info->pathlen, fullpath, + names, names+0, mbase_null, 0, + filemask, dirmask, 1); + return mask; + } + /* * Record information about the path so we can resolve later in * process_entries. From patchwork Mon Nov 2 20:43:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875239 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 95177C4742C for ; Mon, 2 Nov 2020 20:44:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2E1B12071A for ; Mon, 2 Nov 2020 20:44:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="WJ4ChSdX" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727140AbgKBUoK (ORCPT ); Mon, 2 Nov 2020 15:44:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51364 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726881AbgKBUoB (ORCPT ); Mon, 2 Nov 2020 15:44:01 -0500 Received: from mail-oi1-x243.google.com (mail-oi1-x243.google.com [IPv6:2607:f8b0:4864:20::243]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A83C3C061A04 for ; Mon, 2 Nov 2020 12:44:01 -0800 (PST) Received: by mail-oi1-x243.google.com with SMTP id c21so1038687oic.1 for ; Mon, 02 Nov 2020 12:44:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=IR2/n85Xwj+gaLo7lHLgG8yfkiGkvuF41MAa2z6PnYA=; b=WJ4ChSdXJSSfLYFBCZ98VWNY+m6iGkeLx2Udzk0s/eEmXHDoIThJSCsxOm457glurj vkM5DpGdqwYo2u0q97YW0oLldpjfS5TZ8Y3zvIVO1JJ/ghcJQ54HLXkM1qufCHvNP3Ni YbdfWLDP0oM8V7YqwR/ns23mr2xxysa8j/UkK64iDQOriDtgKP9/w+Z6fJXMMshcKwwU c3/OHQecJhAPCIaTfm3+jL57dyomnuHmCmUoBooX33lBsBPjVUBVn3eyu7VEfdsOjEKS B2oDNtJVFLEYB6a0EAxyPi7oNIgL84WYLEpUMiGqIYSxm/HdP2U/yz3deIZSnYdt3OwB HsNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=IR2/n85Xwj+gaLo7lHLgG8yfkiGkvuF41MAa2z6PnYA=; b=gjIMAK2EVhKHZatsTWVi8fSdYGkFL5vQeaDlioBulOuWJQ+7PxVB+LgpQ0W6NlxEX/ 0fw5B/NoRgfS7srJBuDbYScFdodZQemBI8VMkZuTLjshOnG4eokK9mAIEWcpOCTBx06V e2vN/i+He0tbYERoxVMBzDGW0iSPxrIZZ4Ym74N/1aUnPyt33/YXfSkk5IYPm0xyyZtF G6BrhedCzHhgXdAopOp66mkDq1fMGtldrcj5cWRRh+Or+0JKuS3EGHS1HlTBl5qCtmCe 89u/wvWIbIiSluAx6916yrcGYRFuMmo7Akeepg6ZFreCEkzuIXkIS3FErxjGR3LqaXK7 E8ZQ== X-Gm-Message-State: AOAM530R/V5cOSPdvIr9pFzx8xmthy5AKJ6O56F0ZzH6Vc1EA4FpY8sm 3/pMzM9szhCR37B0ALLTa6bV7YyexAHeAA== X-Google-Smtp-Source: ABdhPJy7J9WmEFihu+Z+toPoRky8Kbps2Nc/lH4uGm0xwicpvNx1PsXP0p0YDdr0WQpmytcFddsMQQ== X-Received: by 2002:aca:5dc5:: with SMTP id r188mr11603504oib.120.1604349840780; Mon, 02 Nov 2020 12:44:00 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.43.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:00 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 11/20] merge-ort: add a preliminary simple process_entries() implementation Date: Mon, 2 Nov 2020 12:43:35 -0800 Message-Id: <20201102204344.342633-12-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add a process_entries() implementation that just loops over the paths and processes each one individually with an auxiliary process_entry() call. Add a basic process_entry() as well, which handles several cases but leaves a few of the more involved ones with die-not-implemented messages. Also, although process_entries() is supposed to create a tree, it does not yet have code to do so -- except in the special case of merging completely empty trees. Signed-off-by: Elijah Newren --- merge-ort.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 105 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 9900fa1bf8..92bbdc7255 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -323,10 +323,114 @@ static int detect_and_process_renames(struct merge_options *opt, return clean; } +/* Per entry merge function */ +static void process_entry(struct merge_options *opt, + const char *path, + struct conflict_info *ci) +{ + assert(!ci->merged.clean); + assert(ci->filemask >= 0 && ci->filemask <= 7); + + if (ci->filemask == 0) { + /* + * This is a placeholder for directories that were recursed + * into; nothing to do in this case. + */ + return; + } + + if (ci->df_conflict) { + die("Not yet implemented."); + } + + /* + * NOTE: Below there is a long switch-like if-elseif-elseif... block + * which the code goes through even for the df_conflict cases + * above. Well, it will once we don't die-not-implemented above. + */ + if (ci->match_mask) { + ci->merged.clean = 1; + if (ci->match_mask == 6) { + /* stages[1] == stages[2] */ + ci->merged.result.mode = ci->stages[1].mode; + oidcpy(&ci->merged.result.oid, &ci->stages[1].oid); + } else { + /* determine the mask of the side that didn't match */ + unsigned int othermask = 7 & ~ci->match_mask; + int side = (othermask == 4) ? 2 : 1; + + ci->merged.is_null = (ci->filemask == ci->match_mask); + ci->merged.result.mode = ci->stages[side].mode; + oidcpy(&ci->merged.result.oid, &ci->stages[side].oid); + + assert(othermask == 2 || othermask == 4); + assert(ci->merged.is_null == !ci->merged.result.mode); + } + } else if (ci->filemask >= 6 && + (S_IFMT & ci->stages[1].mode) != + (S_IFMT & ci->stages[2].mode)) { + /* + * Two different items from (file/submodule/symlink) + */ + die("Not yet implemented."); + } else if (ci->filemask >= 6) { + /* + * TODO: Needs a two-way or three-way content merge, but we're + * just being lazy and copying the version from HEAD and + * leaving it as conflicted. + */ + ci->merged.clean = 0; + ci->merged.result.mode = ci->stages[1].mode; + oidcpy(&ci->merged.result.oid, &ci->stages[1].oid); + } else if (ci->filemask == 3 || ci->filemask == 5) { + /* Modify/delete */ + die("Not yet implemented."); + } else if (ci->filemask == 2 || ci->filemask == 4) { + /* Added on one side */ + int side = (ci->filemask == 4) ? 2 : 1; + ci->merged.result.mode = ci->stages[side].mode; + oidcpy(&ci->merged.result.oid, &ci->stages[side].oid); + ci->merged.clean = !ci->df_conflict && !ci->path_conflict; + } else if (ci->filemask == 1) { + /* Deleted on both sides */ + ci->merged.is_null = 1; + ci->merged.result.mode = 0; + oidcpy(&ci->merged.result.oid, &null_oid); + ci->merged.clean = !ci->path_conflict; + } + + /* + * If still unmerged, record it separately. This allows us to later + * iterate over just unmerged entries when updating the index instead + * of iterating over all entries. + */ + if (!ci->merged.clean) + strmap_put(&opt->priv->unmerged, path, ci); +} + static void process_entries(struct merge_options *opt, struct object_id *result_oid) { - die("Not yet implemented."); + struct hashmap_iter iter; + struct strmap_entry *e; + + if (strmap_empty(&opt->priv->paths)) { + oidcpy(result_oid, opt->repo->hash_algo->empty_tree); + return; + } + + strmap_for_each_entry(&opt->priv->paths, &iter, e) { + /* + * WARNING: If ci->merged.clean is true, then ci does not + * actually point to a conflict_info but a struct merge_info. + */ + struct conflict_info *ci = e->value; + + if (!ci->merged.clean) + process_entry(opt, e->key, e->value); + } + + die("Tree creation not yet implemented"); } void merge_switch_to_result(struct merge_options *opt, From patchwork Mon Nov 2 20:43:36 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875253 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1628EC00A89 for ; Mon, 2 Nov 2020 20:44:24 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C3F532071A for ; Mon, 2 Nov 2020 20:44:23 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="B61dvNg5" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727045AbgKBUoI (ORCPT ); Mon, 2 Nov 2020 15:44:08 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51372 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726998AbgKBUoD (ORCPT ); Mon, 2 Nov 2020 15:44:03 -0500 Received: from mail-oi1-x242.google.com (mail-oi1-x242.google.com [IPv6:2607:f8b0:4864:20::242]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BE75EC0617A6 for ; Mon, 2 Nov 2020 12:44:02 -0800 (PST) Received: by mail-oi1-x242.google.com with SMTP id c80so4536540oib.2 for ; Mon, 02 Nov 2020 12:44:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=EU5eR3cWvBGUmKiDUkbd1kHFSAPGBQBdRmerAY3P0ho=; b=B61dvNg5FeIYQEpR+0Ow6zHd09AxgZpEJyw0C+1DhCCSt92Dk/dBt66JGORcY/9RJs n9+XAJhM5VjSiXlVF+mpokLKbeOPKNHrNy4hD/CozLgvXldwEZHLmOMZH9tGYUUahGo9 zU39OLf59FbvgNc1roBhLlTs2GcgHb4QzDaeC2Z4nDyDs58X/gkUveqtRD5y5OBdUnpm Q9KbcSy9cnoqFT8MgGf1b6pC3/xzBQ167c6kT4qM5WXTHht2LvZvVwWtr6ZsykIeHiLS vgkSu4bXDaS408sobKIE92gpLkXacyxvUZsBAIu1fnh/YbJkUDdcMzfeu9Y/+ncCIiWi Hd/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=EU5eR3cWvBGUmKiDUkbd1kHFSAPGBQBdRmerAY3P0ho=; b=DiocX3yy8cFNd16pZgx2yxuHz87qZgEwV8OapkWBAxyqwsWvuEHiWDo26hSI6cfYZ1 3kt8fvWhtM/egh0jva/4UHPcYSl7c7E3wZfdHdHnD5g4Dx6H9GgKnmm8M/xwFvXakUHs DYpiPylRNKKlPizhm/g/TAKr27TUWMkD8pC2jbL5v+J18xa8s6ip62Js89LWTCB4J0AO L8VD8LZYsyuQXfUky7u4pr0ElUMj11So6/isPrXW9d1kLZVevHAPJiY3mfQJ4G3py3Je mdBGteits8IGZ9r8T7i02aa77ci44yBQAL9ip7p1ylgkjPrdAeBX87jc3KHV1CLpTl8R qKpg== X-Gm-Message-State: AOAM530r14UbCtQeV28y9nj9vXVJRS0Q6g4tIvtEmYlBVDidAhl7TTO1 eOrMTFJTOppj3bA19iyfjNu0mslUJy8egg== X-Google-Smtp-Source: ABdhPJy0Q8NfUaRAeOrzr9P0FdHrbPXX2JUI3o3pr3oYNi7HmdSkP6JvFycGi7mG+5URe+B9Hzexpg== X-Received: by 2002:aca:d502:: with SMTP id m2mr3923148oig.105.1604349841993; Mon, 02 Nov 2020 12:44:01 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:01 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 12/20] merge-ort: have process_entries operate in a defined order Date: Mon, 2 Nov 2020 12:43:36 -0800 Message-Id: <20201102204344.342633-13-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org We want to handle paths below a directory before needing to handle the directory itself. Also, we want to handle the directory immediately after the paths below it, so we can't use simple lexicographic ordering from strcmp (which would insert foo.txt between foo and foo/file.c). Copy string_list_df_name_compare() from merge-recursive.c, and set up a string list of paths sorted by that function so that we can iterate in the desired order. Signed-off-by: Elijah Newren --- merge-ort.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 47 insertions(+), 2 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 92bbdc7255..3d46d62ed3 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -323,6 +323,33 @@ static int detect_and_process_renames(struct merge_options *opt, return clean; } +static int string_list_df_name_compare(const char *one, const char *two) +{ + int onelen = strlen(one); + int twolen = strlen(two); + /* + * Here we only care that entries for D/F conflicts are + * adjacent, in particular with the file of the D/F conflict + * appearing before files below the corresponding directory. + * The order of the rest of the list is irrelevant for us. + * + * To achieve this, we sort with df_name_compare and provide + * the mode S_IFDIR so that D/F conflicts will sort correctly. + * We use the mode S_IFDIR for everything else for simplicity, + * since in other cases any changes in their order due to + * sorting cause no problems for us. + */ + int cmp = df_name_compare(one, onelen, S_IFDIR, + two, twolen, S_IFDIR); + /* + * Now that 'foo' and 'foo/bar' compare equal, we have to make sure + * that 'foo' comes before 'foo/bar'. + */ + if (cmp) + return cmp; + return onelen - twolen; +} + /* Per entry merge function */ static void process_entry(struct merge_options *opt, const char *path, @@ -413,23 +440,41 @@ static void process_entries(struct merge_options *opt, { struct hashmap_iter iter; struct strmap_entry *e; + struct string_list plist = STRING_LIST_INIT_NODUP; + struct string_list_item *entry; if (strmap_empty(&opt->priv->paths)) { oidcpy(result_oid, opt->repo->hash_algo->empty_tree); return; } + /* Hack to pre-allocate plist to the desired size */ + ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc); + + /* Put every entry from paths into plist, then sort */ strmap_for_each_entry(&opt->priv->paths, &iter, e) { + string_list_append(&plist, e->key)->util = e->value; + } + plist.cmp = string_list_df_name_compare; + string_list_sort(&plist); + + /* + * Iterate over the items in reverse order, so we can handle paths + * below a directory before needing to handle the directory itself. + */ + for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) { + char *path = entry->string; /* * WARNING: If ci->merged.clean is true, then ci does not * actually point to a conflict_info but a struct merge_info. */ - struct conflict_info *ci = e->value; + struct conflict_info *ci = entry->util; if (!ci->merged.clean) - process_entry(opt, e->key, e->value); + process_entry(opt, path, ci); } + string_list_clear(&plist, 0); die("Tree creation not yet implemented"); } From patchwork Mon Nov 2 20:43:37 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875237 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A7F96C2D0A3 for ; Mon, 2 Nov 2020 20:44:25 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4D83F2071A for ; Mon, 2 Nov 2020 20:44:25 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Uf6rzEJQ" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727035AbgKBUoI (ORCPT ); Mon, 2 Nov 2020 15:44:08 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51376 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727002AbgKBUoD (ORCPT ); Mon, 2 Nov 2020 15:44:03 -0500 Received: from mail-ot1-x343.google.com (mail-ot1-x343.google.com [IPv6:2607:f8b0:4864:20::343]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C9CBEC0617A6 for ; Mon, 2 Nov 2020 12:44:03 -0800 (PST) Received: by mail-ot1-x343.google.com with SMTP id i18so9190336ots.0 for ; Mon, 02 Nov 2020 12:44:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=pkcPoDrRjJoW13tugZ4uXzSNmaonzfe2NBzDHxj/ryo=; b=Uf6rzEJQZrECSFyoWu6ROCij+MMx96ox7F8fIQ1/FXrGOjYqA7ytKYQmHpCRxepF85 HgYGVY9SIeAcI5s/FxZvqv7iNbifv0yVFstGdrYAvpA02SGNjlJume2lBYce1vSFh2uQ ALr/zE/qq2ZbpOS2SGVZwJOpjZtPE2bdWyuwlQ29ZwIlcPVgZF3HVzBDh7OEeb3GXcgs Tn8G5n+Il4J7aZVClG6qGiT+RKnRSO6dVvOEbKiQap45WpMwavKxLC0zH3spJYM+W3SC AyEJo0leAyDrdx57RvxeVgO2ZQriC6LMVPBthCf9xk9MGrQHLERcaS6npc1UMTwX7piE s8wA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=pkcPoDrRjJoW13tugZ4uXzSNmaonzfe2NBzDHxj/ryo=; b=JLNcuFsOQbxfDxYNVB09NJgTU6Vm39jQAddpvpneS9Nzxy/Sk8KMQMXxQc9AES9PA5 WL9WRCMln7p7WsqBTxtO2INj0EZ9HUbh2TNwdIPSK83Wpq0e5FJLvNo+kUxJ0UJsMELn LNFjILwMFUl9Ldzn9ltGxFUXa07/Pv8m62eZ1MBi1EqjgNmvR+2TXxSzV4bljOiKyMVk xUhBARprwrAJsr20GLufXZSH5JUGb0QixPnJ4JZFcT3uLAJgtEvJNTO81w/dO9Ji8HIF K9YsGWYCBK0rFtuJRp/RHQdk0uiXL18EsZP3imypwtUI3V2URhbttsLh5PpRYog7Dq+Z kHMA== X-Gm-Message-State: AOAM532bKDFdclKxZu7WrgzZTy/WfnSP3h+iyfVmSx9AhIAQj0MWo+eE OcVujw89Qr/HHdgO+Dimz2ymDt933MWyjg== X-Google-Smtp-Source: ABdhPJx56K4CGiMEtWb+KcYpzQ6hrpZzPu+n92OR32vpcVPBoVjgfqquy3Dxk1MwB0v3uqxi/r/1xg== X-Received: by 2002:a05:6830:17d6:: with SMTP id p22mr14286538ota.154.1604349843021; Mon, 02 Nov 2020 12:44:03 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:02 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids Date: Mon, 2 Nov 2020 12:43:37 -0800 Message-Id: <20201102204344.342633-14-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org As a step towards transforming the processed path->conflict_info entries into an actual tree object, start recording basenames, modes, and oids in a dir_metadata structure. Subsequent commits will make use of this to actually write a tree. Signed-off-by: Elijah Newren --- merge-ort.c | 35 ++++++++++++++++++++++++++++++++--- 1 file changed, 32 insertions(+), 3 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 3d46d62ed3..ff4d455dce 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -350,10 +350,31 @@ static int string_list_df_name_compare(const char *one, const char *two) return onelen - twolen; } +struct directory_versions { + struct string_list versions; +}; + +static void record_entry_for_tree(struct directory_versions *dir_metadata, + const char *path, + struct conflict_info *ci) +{ + const char *basename; + + if (ci->merged.is_null) + /* nothing to record */ + return; + + basename = path + ci->merged.basename_offset; + assert(strchr(basename, '/') == NULL); + string_list_append(&dir_metadata->versions, + basename)->util = &ci->merged.result; +} + /* Per entry merge function */ static void process_entry(struct merge_options *opt, const char *path, - struct conflict_info *ci) + struct conflict_info *ci, + struct directory_versions *dir_metadata) { assert(!ci->merged.clean); assert(ci->filemask >= 0 && ci->filemask <= 7); @@ -433,6 +454,7 @@ static void process_entry(struct merge_options *opt, */ if (!ci->merged.clean) strmap_put(&opt->priv->unmerged, path, ci); + record_entry_for_tree(dir_metadata, path, ci); } static void process_entries(struct merge_options *opt, @@ -442,6 +464,7 @@ static void process_entries(struct merge_options *opt, struct strmap_entry *e; struct string_list plist = STRING_LIST_INIT_NODUP; struct string_list_item *entry; + struct directory_versions dir_metadata; if (strmap_empty(&opt->priv->paths)) { oidcpy(result_oid, opt->repo->hash_algo->empty_tree); @@ -458,6 +481,9 @@ static void process_entries(struct merge_options *opt, plist.cmp = string_list_df_name_compare; string_list_sort(&plist); + /* other setup */ + string_list_init(&dir_metadata.versions, 0); + /* * Iterate over the items in reverse order, so we can handle paths * below a directory before needing to handle the directory itself. @@ -470,11 +496,14 @@ static void process_entries(struct merge_options *opt, */ struct conflict_info *ci = entry->util; - if (!ci->merged.clean) - process_entry(opt, path, ci); + if (ci->merged.clean) + record_entry_for_tree(&dir_metadata, path, ci); + else + process_entry(opt, path, ci, &dir_metadata); } string_list_clear(&plist, 0); + string_list_clear(&dir_metadata.versions, 0); die("Tree creation not yet implemented"); } From patchwork Mon Nov 2 20:43:38 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875243 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2723FC00A89 for ; Mon, 2 Nov 2020 20:44:19 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D42332071A for ; Mon, 2 Nov 2020 20:44:18 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="mGhm+zME" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727238AbgKBUoQ (ORCPT ); Mon, 2 Nov 2020 15:44:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51390 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726963AbgKBUoJ (ORCPT ); Mon, 2 Nov 2020 15:44:09 -0500 Received: from mail-oi1-x241.google.com (mail-oi1-x241.google.com [IPv6:2607:f8b0:4864:20::241]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A5B13C0617A6 for ; Mon, 2 Nov 2020 12:44:09 -0800 (PST) Received: by mail-oi1-x241.google.com with SMTP id m13so6964373oih.8 for ; Mon, 02 Nov 2020 12:44:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=F38hhNw/G8Gyp0GH8i2VeT5MijQbGXIg+WonHnkcw0s=; b=mGhm+zMEiJSwcKQAyD31ddLjwXocjOpSxb+nt8pR+A4rzHa923tPeQ2mQNYAvhkMkI TJxOf2wGGAcTiGRYeCnKIYYGNUon4cwjQlJsH3isA+8f1SZoqOz4FND6xXaHS4igg6BC Etudu5YUSCN0O5F/zrlq/VABYFdQDbmDN7fkUMvy67/yH1ewkh9gXOd7RJuckaJ+8Uqr m+9M3ebDSV5dbdVumJwtb2taRbzcZiW3LPgsVHovKz30KuXXupfXwLRScuc/Cj208pjs hwQHOxVoR3CKSQEmvQ10VaCLiv2JkIEJAtGeku+SrkVp5oeRYuQ/2D1V/R5Oi94v6WAZ q5mQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=F38hhNw/G8Gyp0GH8i2VeT5MijQbGXIg+WonHnkcw0s=; b=MRA00GjpJYNVpiAJJAA1wCJmGazLDFdzUazunXpsv4ZOO+naKqphSdDDabQ/mY/e4V QcnfFyUPACGKsJDqqJLDc8C0lzDQf8jDnNwkway6DBDJmI2IcAl8XYcjNp49SdBtd45A wr3fYnFQPp0B/me/PAM9S9uV4yA8+Q4tyu6WSk9gcnUoAsDmb4lhbn8fNbLLr040dS00 GaLGum+N5H44dfBaa01lP6EIEgSS25kGBfHEOJ579y4TCXlWYJfWEnQ9n1Bvyo8plCLw vTy8kG7dj2JQSIRwYTfl4WUn0i24I5AW+rxki02uBiP70ekFTL2QXFNzJ4fuL+n4N1Nb REIQ== X-Gm-Message-State: AOAM532WlK7Kx0gLDPNskeGa7KQUGLquzDOktkPcnSejnkJcuC3iRs7p jLBySOOXTvR/Mi9WLsb1kGJwdWitJbzMMA== X-Google-Smtp-Source: ABdhPJy6HeLK5eKvBuW4MKug7cz2pzvGpi6/kAaN/DcRG21fobrPWOhUYZXplYY3qijnKqqDVo7q9Q== X-Received: by 2002:aca:c188:: with SMTP id r130mr139765oif.99.1604349848933; Mon, 02 Nov 2020 12:44:08 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:03 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 14/20] merge-ort: step 2 of tree writing -- function to create tree object Date: Mon, 2 Nov 2020 12:43:38 -0800 Message-Id: <20201102204344.342633-15-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Create a new function, write_tree(), which will take a list of basenames, modes, and oids for a single directory and create a tree object in the object-store. We do not yet have just basenames, modes, and oids for just a single directory (we have a mixture of entries from all directory levels in the hierarchy) so we still die() before the current call to write_tree(), but the next patch will rectify that. Signed-off-by: Elijah Newren --- merge-ort.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 53 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index ff4d455dce..c560dd1634 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -19,6 +19,7 @@ #include "diff.h" #include "diffcore.h" +#include "object-store.h" #include "strmap.h" #include "tree.h" #include "xdiff-interface.h" @@ -354,6 +355,50 @@ struct directory_versions { struct string_list versions; }; +static void write_tree(struct object_id *result_oid, + struct string_list *versions, + unsigned int offset) +{ + size_t maxlen = 0; + unsigned int nr = versions->nr - offset; + struct strbuf buf = STRBUF_INIT; + struct string_list relevant_entries = STRING_LIST_INIT_NODUP; + int i; + + /* + * We want to sort the last (versions->nr-offset) entries in versions. + * Do so by abusing the string_list API a bit: make another string_list + * that contains just those entries and then sort them. + * + * We won't use relevant_entries again and will let it just pop off the + * stack, so there won't be allocation worries or anything. + */ + relevant_entries.items = versions->items + offset; + relevant_entries.nr = versions->nr - offset; + string_list_sort(&relevant_entries); + + /* Pre-allocate some space in buf */ + for (i = 0; i < nr; i++) { + maxlen += strlen(versions->items[offset+i].string) + 34; + } + strbuf_reset(&buf); + strbuf_grow(&buf, maxlen); + + /* Write each entry out to buf */ + for (i = 0; i < nr; i++) { + struct merged_info *mi = versions->items[offset+i].util; + struct version_info *ri = &mi->result; + strbuf_addf(&buf, "%o %s%c", + ri->mode, + versions->items[offset+i].string, '\0'); + strbuf_add(&buf, ri->oid.hash, the_hash_algo->rawsz); + } + + /* Write this object file out, and record in result_oid */ + write_object_file(buf.buf, buf.len, tree_type, result_oid); + strbuf_release(&buf); +} + static void record_entry_for_tree(struct directory_versions *dir_metadata, const char *path, struct conflict_info *ci) @@ -502,9 +547,16 @@ static void process_entries(struct merge_options *opt, process_entry(opt, path, ci, &dir_metadata); } + /* + * TODO: We can't actually write a tree yet, because dir_metadata just + * contains all basenames of all files throughout the tree with their + * mode and hash. Not only is that a nonsensical tree, it will have + * lots of duplicates for paths such as "Makefile" or ".gitignore". + */ + die("Not yet implemented; need to process subtrees separately"); + write_tree(result_oid, &dir_metadata.versions, 0); string_list_clear(&plist, 0); string_list_clear(&dir_metadata.versions, 0); - die("Tree creation not yet implemented"); } void merge_switch_to_result(struct merge_options *opt, From patchwork Mon Nov 2 20:43:39 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875233 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 37756C388F9 for ; Mon, 2 Nov 2020 20:44:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D4D1222226 for ; Mon, 2 Nov 2020 20:44:13 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="f2qUlyQ3" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727160AbgKBUoM (ORCPT ); Mon, 2 Nov 2020 15:44:12 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51398 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726635AbgKBUoL (ORCPT ); Mon, 2 Nov 2020 15:44:11 -0500 Received: from mail-oi1-x242.google.com (mail-oi1-x242.google.com [IPv6:2607:f8b0:4864:20::242]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D56AEC0617A6 for ; Mon, 2 Nov 2020 12:44:10 -0800 (PST) Received: by mail-oi1-x242.google.com with SMTP id t143so4466705oif.10 for ; Mon, 02 Nov 2020 12:44:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=P26CaB+rlL/P8c0N/tACqXuNUFzNe7fXIG2qiTPrY7w=; b=f2qUlyQ3FSOGGghRvSw+Y1I4fRz76ZR04LbxPzyoDT2fO1jD0a8SyEef0hdcIWtFWc x6c/Xj5F+PG9wlKxD9I04ECZ5rJxGimpmhLe6/ej+7a2Uc4CefbokhM/39/wviQ+XV/5 smi9tyYbXmLd+7SwgxUSxqSij/D8VlrgcOo9Y/aOMqVUpukqzJqcnHO37jAOxHjsmKp2 ScUIB4PSLyLtebzEd1fkd+F+IrGwVICMDZvDvzWbm2iQ43C6ntuV+aJULvnYBZ6lpFUS ns8Rb/3B/c8KNlzbU7DLIMBFVGyBfNPR8EJo8E8lqTF2ifZ0kogiRSmzTI4tvoVU02IL AQFA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=P26CaB+rlL/P8c0N/tACqXuNUFzNe7fXIG2qiTPrY7w=; b=Vz/qpuGwKTufSzNfXKfkQcLVgC/1XBMSjFDdLoRMlW/zEmxadTRSj4rni3P26Mc/GM PitUaGR/72OLhFawtK0ttkmaVZ2c2ux5kv8bnqbzKRfe0SUipt2E8tk2fG+3jgOjW5Tq pQmYGVMm1FIb/ax8uM3qy3YNZtHWT9pW+D+ofJLvxM0o8PfUo4Bls2QPNFTADXBDn9qV Kvk581gBOvA5i1TypHWin5tJyK4o8VX3Zz418ApKj5/Td8ZCVxAcm4qrTVnFirFtQ9TB x3fLRnq5vnv07rsxYDfeRYuJi7xKYWxWfV3ZeOj9rp7/iP0Y1lxFJlJoi0DBSN41H9yf EGvg== X-Gm-Message-State: AOAM530piB0Qiqi7ihjgwJylUQHxVSpbVp1//qZGBXZw7LGiiIJd086a BKyJLDeb9asksUc6ax+umiRVyWoDZUESfQ== X-Google-Smtp-Source: ABdhPJwSleS747w7CwtnKmLydmAvw/NFWNiF9Q4m0GvF1jgzUrX1yHDYmnQUKFFd7Dwx1XtR6FeGAw== X-Received: by 2002:a05:6808:8cc:: with SMTP id k12mr11525776oij.179.1604349849888; Mon, 02 Nov 2020 12:44:09 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:09 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go Date: Mon, 2 Nov 2020 12:43:39 -0800 Message-Id: <20201102204344.342633-16-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Our order for processing of entries means that if we have a tree of files that looks like Makefile src/moduleA/foo.c src/moduleA/bar.c src/moduleB/baz.c src/moduleB/umm.c tokens.txt Then we will process paths in the order of the leftmost column below. I have added two additional columns that help explain the algorithm that follows; the 2nd column is there to remind us we have oid & mode info we are tracking for each of these paths (which differs between the paths which I'm not representing well here), and the third column annotates the parent directory of the entry: tokens.txt "" src/moduleB/umm.c src/moduleB src/moduleB/baz.c src/moduleB src/moduleB src src/moduleA/foo.c src/moduleA src/moduleA/bar.c src/moduleA src/moduleA src src "" Makefile "" When the parent directory changes, if it's a subdirectory of the previous parent directory (e.g. "" -> src/moduleB) then we can just keep appending. If the parent directory differs from the previous parent directory and is not a subdirectory, then we should process that directory. So, for example, when we get to this point: tokens.txt "" src/moduleB/umm.c src/moduleB src/moduleB/baz.c src/moduleB and note that the next entry (src/moduleB) has a different parent than the last one that isn't a subdirectory, we should write out a tree for it 100644 blob umm.c 100644 blob baz.c then pop all the entries under that directory while recording the new hash for that directory, leaving us with tokens.txt "" src/moduleB src This process repeats until at the end we get to tokens.txt "" src "" Makefile "" and then we can write out the toplevel tree. Since we potentially have entries in our string_list corresponding to multiple different toplevel directories, e.g. a slightly different repository might have: whizbang.txt "" tokens.txt "" src/moduleD src src/moduleC src src/moduleB src src/moduleA/foo.c src/moduleA src/moduleA/bar.c src/moduleA When src/moduleA is popped off, we need to know that the "last directory" reverts back to src, and how many entries in our string_list are associated with that parent directory. So I use an auxiliary offsets string_list which would have (parent_directory,offset) information of the form "" 0 src 2 src/moduleA 5 Whenever I write out a tree for a subdirectory, I set versions.nr to the final offset value and then decrement offsets.nr...and then add an entry to versions with a hash for the new directory. The idea is relatively simple, there's just a lot of accounting to implement this. Signed-off-by: Elijah Newren --- merge-ort.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 106 insertions(+), 7 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index c560dd1634..20b7c0d8b0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -353,6 +353,9 @@ static int string_list_df_name_compare(const char *one, const char *two) struct directory_versions { struct string_list versions; + struct string_list offsets; + const char *last_directory; + unsigned last_directory_len; }; static void write_tree(struct object_id *result_oid, @@ -409,12 +412,100 @@ static void record_entry_for_tree(struct directory_versions *dir_metadata, /* nothing to record */ return; + /* + * Note: write_completed_directories() already added + * entries for directories to dir_metadata->versions, + * so no need to handle ci->filemask == 0 again. + */ + if (!ci->merged.clean && !ci->filemask) + return; + basename = path + ci->merged.basename_offset; assert(strchr(basename, '/') == NULL); string_list_append(&dir_metadata->versions, basename)->util = &ci->merged.result; } +static void write_completed_directories(struct merge_options *opt, + const char *new_directory_name, + struct directory_versions *info) +{ + const char *prev_dir; + struct merged_info *dir_info = NULL; + unsigned int offset; + int wrote_a_new_tree = 0; + + if (new_directory_name == info->last_directory) + return; + + /* + * If we are just starting (last_directory is NULL), or last_directory + * is a prefix of the current directory, then we can just update + * last_directory and record the offset where we started this directory. + */ + if (info->last_directory == NULL || + !strncmp(new_directory_name, info->last_directory, + info->last_directory_len)) { + uintptr_t offset = info->versions.nr; + + info->last_directory = new_directory_name; + info->last_directory_len = strlen(info->last_directory); + string_list_append(&info->offsets, + info->last_directory)->util = (void*)offset; + return; + } + + /* + * At this point, ne (next entry) is within a different directory + * than the last entry, so we need to create a tree object for all + * the entries in info->versions that are under info->last_directory. + */ + dir_info = strmap_get(&opt->priv->paths, info->last_directory); + assert(dir_info); + offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util; + if (offset == info->versions.nr) { + dir_info->is_null = 1; + } else { + dir_info->result.mode = S_IFDIR; + write_tree(&dir_info->result.oid, &info->versions, offset); + wrote_a_new_tree = 1; + } + + /* + * We've now used several entries from info->versions and one entry + * from info->offsets, so we get rid of those values. + */ + info->offsets.nr--; + info->versions.nr = offset; + + /* + * Now we've got an OID for last_directory in dir_info. We need to + * add it to info->versions for it to be part of the computation of + * its parent directories' OID. But first, we have to find out what + * its' parent name was and whether that matches the previous + * info->offsets or we need to set up a new one. + */ + prev_dir = info->offsets.nr == 0 ? NULL : + info->offsets.items[info->offsets.nr-1].string; + if (new_directory_name != prev_dir) { + uintptr_t c = info->versions.nr; + string_list_append(&info->offsets, + new_directory_name)->util = (void*)c; + } + + /* + * Okay, finally record OID for last_directory in info->versions, + * and update last_directory. + */ + if (wrote_a_new_tree) { + const char *dir_name = strrchr(info->last_directory, '/'); + dir_name = dir_name ? dir_name+1 : info->last_directory; + string_list_append(&info->versions, dir_name)->util = dir_info; + } + info->last_directory = new_directory_name; + info->last_directory_len = strlen(info->last_directory); +} + /* Per entry merge function */ static void process_entry(struct merge_options *opt, const char *path, @@ -528,6 +619,9 @@ static void process_entries(struct merge_options *opt, /* other setup */ string_list_init(&dir_metadata.versions, 0); + string_list_init(&dir_metadata.offsets, 0); + dir_metadata.last_directory = NULL; + dir_metadata.last_directory_len = 0; /* * Iterate over the items in reverse order, so we can handle paths @@ -541,22 +635,27 @@ static void process_entries(struct merge_options *opt, */ struct conflict_info *ci = entry->util; + write_completed_directories(opt, ci->merged.directory_name, + &dir_metadata); if (ci->merged.clean) record_entry_for_tree(&dir_metadata, path, ci); else process_entry(opt, path, ci, &dir_metadata); } - /* - * TODO: We can't actually write a tree yet, because dir_metadata just - * contains all basenames of all files throughout the tree with their - * mode and hash. Not only is that a nonsensical tree, it will have - * lots of duplicates for paths such as "Makefile" or ".gitignore". - */ - die("Not yet implemented; need to process subtrees separately"); + if (dir_metadata.offsets.nr != 1 || + (uintptr_t)dir_metadata.offsets.items[0].util != 0) { + printf("dir_metadata.offsets.nr = %d (should be 1)\n", + dir_metadata.offsets.nr); + printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n", + (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util); + fflush(stdout); + BUG("dir_metadata accounting completely off; shouldn't happen"); + } write_tree(result_oid, &dir_metadata.versions, 0); string_list_clear(&plist, 0); string_list_clear(&dir_metadata.versions, 0); + string_list_clear(&dir_metadata.offsets, 0); } void merge_switch_to_result(struct merge_options *opt, From patchwork Mon Nov 2 20:43:40 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875247 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5E524C2D0A3 for ; Mon, 2 Nov 2020 20:44:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0632B2071A for ; Mon, 2 Nov 2020 20:44:22 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="b0QQbyA2" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727200AbgKBUoO (ORCPT ); Mon, 2 Nov 2020 15:44:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51400 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726635AbgKBUoN (ORCPT ); Mon, 2 Nov 2020 15:44:13 -0500 Received: from mail-oi1-x241.google.com (mail-oi1-x241.google.com [IPv6:2607:f8b0:4864:20::241]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AC801C0617A6 for ; Mon, 2 Nov 2020 12:44:11 -0800 (PST) Received: by mail-oi1-x241.google.com with SMTP id w145so10383710oie.9 for ; Mon, 02 Nov 2020 12:44:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=/91y2IShTUxlFRJSwGZM1L55xZd3TS9RORFe+3DBDT0=; b=b0QQbyA2zJxFjY/TH5rwh6wMzOQZ6/qlwvSrogWAw01vogrIY7jNp8PZ4BuswtQWLG TWtK1b71gDuv6kdmnPx7PtiNxqj1cLTeFEsF8OIxEeGltHD/lYmxaAzHl3Z73n7XO3xY rJ2fHN7Ly4hviuuOfYUTpY0YMsFGE0sdn+oGSfOFGLVJdypCbPhENnoz3VUnapB0sWd7 FUCQFxUkS7KFZjuCtX219AgZsil8MS+g8LyY3AlpEzTG9okzh9ZK+XrsPY5dSxS78LJy qwsTbeBVB5DO4WbIhpGQwy02WBdpizC+EGB3z3LxpG9UD5JIFYkc+zNLvBkw92BlQEjd wf+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=/91y2IShTUxlFRJSwGZM1L55xZd3TS9RORFe+3DBDT0=; b=i2vZNMUaKuO3y9nescHFUo+Kgpj4zL55PgzYYMenxKhLD7W898KVWOpgTLG0gGyn11 Cad/3/HFbynE8bJXNg2UcmrkJqm9P5RX++2x+TbcKBj1K2k13pvUtn7b55Y9bEjPIZ+P zrzU6Xx0cxXPuGLrAXxXsogYJRpt6RFMGiXa5Hv3vA49+5Odp/khPQL5kqR+eokMHACm qqRaUAD3idHnJLwsmwf0zUKVYh1CIgmdJ8UdpyGCNXx3W2BZyabtkrlndFbd23ZLtqWh 49A0nOTF98uGTTx0EezBv2W7lH8SDkqEoIH0V1SwBS9WE55jlJkBZSXWHT9n0CL5CWHp /4fg== X-Gm-Message-State: AOAM533Gqu+oCxteDYlRdgu+POCiafNiCs0aRqzs8LEbzWMJeIQw5Ega oxyC6ycSog2WcB8R5tPqQZ2PBzlI1p6M/g== X-Google-Smtp-Source: ABdhPJxSj51rA2hHhSSnVu+uCQlnEz9++Tchtxgq0slpe3mXbIk72LjrvXyRxP7v7RmR+7MsTx5aag== X-Received: by 2002:aca:ddc2:: with SMTP id u185mr11574795oig.81.1604349850964; Mon, 02 Nov 2020 12:44:10 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:10 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 16/20] merge-ort: basic outline for merge_switch_to_result() Date: Mon, 2 Nov 2020 12:43:40 -0800 Message-Id: <20201102204344.342633-17-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org This adds a basic implementation for merge_switch_to_result(), though just in terms of a few new empty functions that will be defined in subsequent commits. Signed-off-by: Elijah Newren --- merge-ort.c | 42 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 41 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 20b7c0d8b0..2a60d84f1d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -658,13 +658,53 @@ static void process_entries(struct merge_options *opt, string_list_clear(&dir_metadata.offsets, 0); } +static int checkout(struct merge_options *opt, + struct tree *prev, + struct tree *next) +{ + die("Not yet implemented."); +} + +static int record_unmerged_index_entries(struct merge_options *opt, + struct index_state *index, + struct strmap *paths, + struct strmap *unmerged) +{ + if (strmap_empty(unmerged)) + return 0; + + die("Not yet implemented."); +} + void merge_switch_to_result(struct merge_options *opt, struct tree *head, struct merge_result *result, int update_worktree_and_index, int display_update_msgs) { - die("Not yet implemented"); + assert(opt->priv == NULL); + if (result->clean >= 0 && update_worktree_and_index) { + struct merge_options_internal *opti = result->priv; + + if (checkout(opt, head, result->tree)) { + /* failure to function */ + result->clean = -1; + return; + } + + if (record_unmerged_index_entries(opt, opt->repo->index, + &opti->paths, + &opti->unmerged)) { + /* failure to function */ + result->clean = -1; + return; + } + } + + if (display_update_msgs) { + /* TODO: print out CONFLICT and other informational messages. */ + } + merge_finalize(opt, result); } From patchwork Mon Nov 2 20:43:41 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875227 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D00FBC388F9 for ; Mon, 2 Nov 2020 20:44:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 79DAB2071A for ; Mon, 2 Nov 2020 20:44:16 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="W8Q3tTE2" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727175AbgKBUoP (ORCPT ); Mon, 2 Nov 2020 15:44:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51406 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727180AbgKBUoO (ORCPT ); Mon, 2 Nov 2020 15:44:14 -0500 Received: from mail-oi1-x241.google.com (mail-oi1-x241.google.com [IPv6:2607:f8b0:4864:20::241]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C00F1C061A04 for ; Mon, 2 Nov 2020 12:44:12 -0800 (PST) Received: by mail-oi1-x241.google.com with SMTP id c80so4536965oib.2 for ; Mon, 02 Nov 2020 12:44:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=3NP2EgG/8B70Vbco8KEBwKH7RCWHLR+ikPArhSK0X9M=; b=W8Q3tTE2I7QNEwoBI320NxiBgg3rlUSURKlqmZIl9hhdTTds585VbLfMaH1z1xYBpK 8iOpb4uYHnSF8gNu7hOO7sj/ZbUdvFoXeqUjJKjsmI6dqTaYmPm+yynHQoV2AZOdoRC1 JFiZy9JWliflFqBooACgbvtETRpsb/PT7tNR2ElqK5nHwVsy+LIFpOhcsU91Qy113Cwb Xj4bDbMC6i5j4t2kxqCymQtyrBhz7nWU8DixIWf7ZXiZ8ZSav4iCmHfAC05SXn5vENSi S0UGpc7yYiCOWvugWPbATZAbOKRRJV60jbFJr4JL+WupG9TlNYy6k9zBSo8ghj/r7uxE Mnkg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=3NP2EgG/8B70Vbco8KEBwKH7RCWHLR+ikPArhSK0X9M=; b=Z6S41hfzofN/utjM1X4e+VaqDfNXSTmZ2kd9ftdopuiGjAGH15qEvul+j8s6zn5gu7 C08x+W4b1W4VOO5qgSk8q5VrkpCjv8eyJ0/4iO9SNBJrFHMYUDv3oRWS+x+PN7nOHray AGFCfM1LqakvkOBql2brpp/fgFf5llUrBqc9meNt2dUrKnVbyxJ/kSKh6dwZk0rHzeGP KudHmZh3EbOL4y1aNzIN8goCdRdo7bOez9MnzPCZU5Mciu2dyzMmRnDgpvuYMJWrKA18 MtuSpLkwmdPLyFO5msyBcuLAiFsKfy0yh/KbuXkY8n18ZL5oabMRmkq2OtdYCJm3Ddsr 5N7g== X-Gm-Message-State: AOAM531RAGeN7lvHUg5FN1pREQGHQp/mZ8X1FoAVlzT7EOw/HiTJbp4S iC/dYR/8lcOgLbjlHE2+Qp4p0zlzjvUKRA== X-Google-Smtp-Source: ABdhPJwR8yl+Z7CJCgcrccRTLrNtiuOrzkMdJKz9hSV9KvoPL5FCUG1i0BeMzgKNYQFgGLh9wL+sRA== X-Received: by 2002:aca:e0d7:: with SMTP id x206mr11667457oig.67.1604349852012; Mon, 02 Nov 2020 12:44:12 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:11 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 17/20] merge-ort: add implementation of checkout() Date: Mon, 2 Nov 2020 12:43:41 -0800 Message-Id: <20201102204344.342633-18-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Since merge-ort creates a tree for its output, when there are no conflicts, updating the working tree and index is as simple as using the unpack_trees() machinery with a twoway_merge (i.e. doing the equivalent of a "checkout" operation). If there were conflicts in the merge, then since the tree we created included all the conflict markers, then using the unpack_trees machinery in this manner will still update the working tree correctly. Further, all index entries corresponding to cleanly merged files will also be updated correctly by this procedure. Index entries corresponding to unmerged entries will appear as though the user had run "git add -u" after the merge to accept all files as-is with conflict markers. Thus, after running unpack_trees(), there needs to be a separate step for updating the entries in the index corresponding to unmerged files. This will be the job for the function record_unmerged_index_entries(), which will be implemented in a subsequent commit. Signed-off-by: Elijah Newren --- merge-ort.c | 45 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 44 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 2a60d84f1d..b7c5973d4d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -19,9 +19,11 @@ #include "diff.h" #include "diffcore.h" +#include "dir.h" #include "object-store.h" #include "strmap.h" #include "tree.h" +#include "unpack-trees.h" #include "xdiff-interface.h" struct merge_options_internal { @@ -662,7 +664,48 @@ static int checkout(struct merge_options *opt, struct tree *prev, struct tree *next) { - die("Not yet implemented."); + /* Switch the index/working copy from old to new */ + int ret; + struct tree_desc trees[2]; + struct unpack_trees_options unpack_opts; + + memset(&unpack_opts, 0, sizeof(unpack_opts)); + unpack_opts.head_idx = -1; + unpack_opts.src_index = opt->repo->index; + unpack_opts.dst_index = opt->repo->index; + + setup_unpack_trees_porcelain(&unpack_opts, "merge"); + + /* + * NOTE: if this were just "git checkout" code, we would probably + * read or refresh the cache and check for an unmerged index, but + * builtin/merge.c or sequencer.c really needs to read the index + * and check for unmerged entries before starting merging for a + * good user experience (no sense waiting for merges/rebases before + * erroring out), so there's no reason to duplicate that work here. + */ + + /* 2-way merge to the new branch */ + unpack_opts.update = 1; + unpack_opts.merge = 1; + unpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */ + unpack_opts.verbose_update = (opt->verbosity > 2); + unpack_opts.fn = twoway_merge; + if (1/* FIXME: opts->overwrite_ignore*/) { + unpack_opts.dir = xcalloc(1, sizeof(*unpack_opts.dir)); + unpack_opts.dir->flags |= DIR_SHOW_IGNORED; + setup_standard_excludes(unpack_opts.dir); + } + parse_tree(prev); + init_tree_desc(&trees[0], prev->buffer, prev->size); + parse_tree(next); + init_tree_desc(&trees[1], next->buffer, next->size); + + ret = unpack_trees(2, trees, &unpack_opts); + clear_unpack_trees_porcelain(&unpack_opts); + dir_clear(unpack_opts.dir); + FREE_AND_NULL(unpack_opts.dir); + return ret; } static int record_unmerged_index_entries(struct merge_options *opt, From patchwork Mon Nov 2 20:43:42 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875245 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_NONE,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4E15DC2D0A3 for ; Mon, 2 Nov 2020 20:44:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EC1C3206E5 for ; Mon, 2 Nov 2020 20:44:15 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Y/6aYLLo" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727217AbgKBUoP (ORCPT ); Mon, 2 Nov 2020 15:44:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51414 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727177AbgKBUoN (ORCPT ); Mon, 2 Nov 2020 15:44:13 -0500 Received: from mail-oi1-x244.google.com (mail-oi1-x244.google.com [IPv6:2607:f8b0:4864:20::244]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C8381C0617A6 for ; Mon, 2 Nov 2020 12:44:13 -0800 (PST) Received: by mail-oi1-x244.google.com with SMTP id j7so16006883oie.12 for ; Mon, 02 Nov 2020 12:44:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=YFCb51uRTTPCO8hIEsQWsOIa2UB9F539kDz6RVguH8Y=; b=Y/6aYLLoXypoj01S1ayNSZG74C8rTFWsZn4rJcvkghGe8jItfk1N9Ks/4w8pImeP7W HeLsR5+HIkOo9YA9tCLVlMa3jHNkchsuATZmkfeF8MTOO8UsRs7Ktu4QznIguNVZQ+6m xMW5qx9hdEcPE/cLBFOkEIiHdQ//ep/B9zg/ktHE7xs+8tJvPINSHfBqfDg3nuwP8cXU jcpTXzkgC2ZAehbwmepROkR4dnRJRsDD0bv9SIyxm8QPa8e0ad5KfnDVPiIqqAyj5kwe sfXu2auiSwPk6PdNQK1bCocy7cJ1Jq99F2LcXF8zeeCwy1EP/uDwtXQXjKz+rhbQb6B3 U19w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=YFCb51uRTTPCO8hIEsQWsOIa2UB9F539kDz6RVguH8Y=; b=opZMkrNpk5FcaHyuwYirABqJ7mVdXNdR803DJqs84z08hTGqmOS/WDme74q8O2cDDq FaB8mTAkP9Gdg2rUXlTFffwvZSrNAL7Wi9YFwrwR2GMPrkUlfqlp2CwhQWt89PMJqLZy wehB0tghP4Aq50QgsSrtybxifvGmmq5q+wSlx9W58cjU6DQBo3pWFdIorfNK/7LbrVth 4izpe919AC3VEjhMOXh5UDf/IMkHmI0f6axe3EKsjwEBt6ucu7LzR715PJLyDrISkQrE 66CacPSwHYq/Fbg48OvpcZ+CnWQGhWBgkTqUnItkvR4BSAmb0w9G7R8Nt+60Wct0D6AL csHg== X-Gm-Message-State: AOAM532a40umotB8OS68LJRM1q3gDGzTg6BVKJmvR/yAbhDzxxamhSyg 9ZEuicBp6AveU/R2aRjtHrU20Pw8xAYJug== X-Google-Smtp-Source: ABdhPJzGmcLfYVM12EZcxJrvIjEQUVOOPtx4vP/unnDYenfT2wir90FTnxTD5kvnl6SJZkW9e6aajQ== X-Received: by 2002:a05:6808:696:: with SMTP id k22mr11611462oig.107.1604349853071; Mon, 02 Nov 2020 12:44:13 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:12 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere Date: Mon, 2 Nov 2020 12:43:42 -0800 Message-Id: <20201102204344.342633-19-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- tree.c | 2 +- tree.h | 2 ++ 2 files changed, 3 insertions(+), 1 deletion(-) diff --git a/tree.c b/tree.c index e76517f6b1..a52479812c 100644 --- a/tree.c +++ b/tree.c @@ -144,7 +144,7 @@ int read_tree_recursive(struct repository *r, return ret; } -static int cmp_cache_name_compare(const void *a_, const void *b_) +int cmp_cache_name_compare(const void *a_, const void *b_) { const struct cache_entry *ce1, *ce2; diff --git a/tree.h b/tree.h index 9383745073..3eb0484cbf 100644 --- a/tree.h +++ b/tree.h @@ -28,6 +28,8 @@ void free_tree_buffer(struct tree *tree); /* Parses and returns the tree in the given ent, chasing tags and commits. */ struct tree *parse_tree_indirect(const struct object_id *oid); +int cmp_cache_name_compare(const void *a_, const void *b_); + #define READ_TREE_RECURSIVE 1 typedef int (*read_tree_fn_t)(const struct object_id *, struct strbuf *, const char *, unsigned int, int, void *); From patchwork Mon Nov 2 20:43:43 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875235 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C89A1C388F9 for ; Mon, 2 Nov 2020 20:44:19 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7F65D2071A for ; Mon, 2 Nov 2020 20:44:19 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="E4aGhk2J" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727255AbgKBUoS (ORCPT ); Mon, 2 Nov 2020 15:44:18 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51418 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726635AbgKBUoP (ORCPT ); Mon, 2 Nov 2020 15:44:15 -0500 Received: from mail-oi1-x242.google.com (mail-oi1-x242.google.com [IPv6:2607:f8b0:4864:20::242]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E8B44C0617A6 for ; Mon, 2 Nov 2020 12:44:14 -0800 (PST) Received: by mail-oi1-x242.google.com with SMTP id m143so6707887oig.7 for ; Mon, 02 Nov 2020 12:44:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=E5N0LIVZr2Sf5o6RBc3AWQq3yrNEzWIeZxdNHMsH9Vg=; b=E4aGhk2JLki2mNTIqlCbCaTXpBX+IqRuys22pCMfAHW+I/5DbrQAlXfB4TwKKGEAjJ 5bZWpjI4cMbqWy+R+MgZ436gyakT1xsm/AMwouMfLgO7ekcgs2myJ5qZc53aCo0QFqjH HbnznKegJwh+Ppc/BApkCFm2Lf3EtL9dnfwjl3QiZfAsbY/ppHRZxy5cWbDy7uX0Jb9o losqLF2xRkho0DoRojgGYpo19dWXWIPaBVNY/lksb4sSOYtJCW5j0hxFUJNOzoIbhIAx 4FWwJd7x7B06mpGyP16ZstFakVGHcYFLIZSLXNDFSM/8GRbSsOKJTSqRhtbEofsbeiJL NePw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=E5N0LIVZr2Sf5o6RBc3AWQq3yrNEzWIeZxdNHMsH9Vg=; b=Fe0Q+aejlDTDhBWE6HOKRfiaHrgDBVj/QLfYMf2spR4w0NQsU+gsp4wy1izU8cf3GB 2fdcIl9JqtDlfyq6SdmEZ0lfVyoDo06mOCezdUlsaIByI1glk3WpI7JCBPJxhFyY3hd0 VodDJwWuwoGABdIfLORb9ni3bUBmdjXwVQFpu4e4UlZHYuS+6gcTIVwnb6G6XzQ+QORu jQIDjldMtvUV6eQFQAO1BkP1MnNBCI6akxf3kXnxyqOg+FJiIZGfdozKKb2fTM54SsPK 95DIHnCvdqAvZ//IWAgKcQcBrI5npYhlqnu1/sW0n6VHiEBnMUQLS6QAeQh5Lw8CRU9J cqrA== X-Gm-Message-State: AOAM533EOkFkiRmeW0kh4C0jm3lj8Oa3G8lpVfhVOtlLGfj9PsyEYj/W epu9jiCXXBREI/JFO82ZQNAHORqnrkLtbQ== X-Google-Smtp-Source: ABdhPJx3b/lPDgzUTlfFB8SuybOmGOkHo7KcMdKjIXJMYpB/hUvHrjrkDZOeFQqBAIjWbg1cFU/zNA== X-Received: by 2002:a05:6808:5d7:: with SMTP id d23mr1890oij.56.1604349854131; Mon, 02 Nov 2020 12:44:14 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:13 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 19/20] merge-ort: add implementation of record_unmerged_index_entries() Date: Mon, 2 Nov 2020 12:43:43 -0800 Message-Id: <20201102204344.342633-20-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org After checkout(), the working tree has the appropriate contents, and the index matches the working copy. That means that all unmodified and cleanly merged files have correct index entries, but unmerged entries need to be updated. We do this by looping over the unmerged entries, marking the existing index entry for the path with CE_REMOVE, adding new higher order staged for the path at the end of the index (ignoring normal index sort order), and then at the end of the loop removing the CE_REMOVED-marked cache entries and sorting the index. Signed-off-by: Elijah Newren --- merge-ort.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 86 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index b7c5973d4d..19c30117b0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -17,6 +17,7 @@ #include "cache.h" #include "merge-ort.h" +#include "cache-tree.h" #include "diff.h" #include "diffcore.h" #include "dir.h" @@ -713,10 +714,94 @@ static int record_unmerged_index_entries(struct merge_options *opt, struct strmap *paths, struct strmap *unmerged) { + struct hashmap_iter iter; + struct strmap_entry *e; + int errs = 0; + int original_cache_nr; + if (strmap_empty(unmerged)) return 0; - die("Not yet implemented."); + original_cache_nr = index->cache_nr; + + /* Put every entry from paths into plist, then sort */ + strmap_for_each_entry(unmerged, &iter, e) { + const char *path = e->key; + struct conflict_info *ci = e->value; + int pos; + struct cache_entry *ce; + int i; + + /* + * The index will already have a stage=0 entry for this path, + * because we created an as-merged-as-possible version of the + * file and checkout() moved the working copy and index over + * to that version. + * + * However, previous iterations through this loop will have + * added unstaged entries to the end of the cache which + * ignore the standard alphabetical ordering of cache + * entries and break invariants needed for index_name_pos() + * to work. However, we know the entry we want is before + * those appended cache entries, so do a temporary swap on + * cache_nr to only look through entries of interest. + */ + SWAP(index->cache_nr, original_cache_nr); + pos = index_name_pos(index, path, strlen(path)); + SWAP(index->cache_nr, original_cache_nr); + if (pos < 0) { + if (ci->filemask == 1) + cache_tree_invalidate_path(index, path); + else + BUG("Unmerged %s but nothing in basic working tree or index; this shouldn't happen", path); + } else { + ce = index->cache[pos]; + + /* + * Clean paths with CE_SKIP_WORKTREE set will not be + * written to the working tree by the unpack_trees() + * call in checkout(). Our unmerged entries would + * have appeared clean to that code since we ignored + * the higher order stages. Thus, we need override + * the CE_SKIP_WORKTREE bit and manually write those + * files to the working disk here. + * + * TODO: Implement this CE_SKIP_WORKTREE fixup. + */ + + /* + * Mark this cache entry for removal and instead add + * new stage>0 entries corresponding to the + * conflicts. If there are many unmerged entries, we + * want to avoid memmove'ing O(NM) entries by + * inserting the new entries one at a time. So, + * instead, we just add the new cache entries to the + * end (ignoring normal index requirements on sort + * order) and sort the index once we're all done. + */ + ce->ce_flags |= CE_REMOVE; + } + + for (i = 0; i < 3; i++) { + struct version_info *vi; + if (!(ci->filemask & (1ul << i))) + continue; + vi = &ci->stages[i]; + ce = make_cache_entry(index, vi->mode, &vi->oid, + path, i+1, 0); + add_index_entry(index, ce, ADD_CACHE_JUST_APPEND); + } + } + + /* + * Remove the unused cache entries (and invalidate the relevant + * cache-trees), then sort the index entries to get the unmerged + * entries we added to the end into their right locations. + */ + remove_marked_cache_entries(index, 1); + QSORT(index->cache, index->cache_nr, cmp_cache_name_compare); + + return errs; } void merge_switch_to_result(struct merge_options *opt, From patchwork Mon Nov 2 20:43:44 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11875249 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.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E3031C2D0A3 for ; Mon, 2 Nov 2020 20:44:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 900022071A for ; Mon, 2 Nov 2020 20:44:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="j7gbQNFF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727258AbgKBUoT (ORCPT ); Mon, 2 Nov 2020 15:44:19 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51422 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727251AbgKBUoR (ORCPT ); Mon, 2 Nov 2020 15:44:17 -0500 Received: from mail-ot1-x342.google.com (mail-ot1-x342.google.com [IPv6:2607:f8b0:4864:20::342]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1F0BCC0617A6 for ; Mon, 2 Nov 2020 12:44:16 -0800 (PST) Received: by mail-ot1-x342.google.com with SMTP id z16so8739488otq.6 for ; Mon, 02 Nov 2020 12:44:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=u2dMW9aAW7YlJ0Fi5Y6EY+FlpKwA9bNCoxkmnmeWy5s=; b=j7gbQNFFph/3eGH3j4M+CNZZsxGwR8+k+8s45STQjOqODq3uJrC2f9BxTr8+HiCfke Aip9qE6884QbZHBtDYzY2E9jAssoP3QNBJz8U+ZuonNvhCrohA/zzbrNIqX+n4sDXbWu Udisz2NRy/kESHyzRFzLNp5c/waEppf09nSbeXnTA6ARlptrNNLL7+PaGzGHv1w7lW2p CKhAYEuOjCMpPVgUMetYHy5m6q1O/HRvLB4NnJH8wr0mpjTuK1W8LY8APcILjqc3rOXC N3Y8Nb57c2duuORZft2zYgHIFwrkCy08PYjNhl2PEnP95sP39mT/nRAh4t+7UA1Pu6NX NY9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=u2dMW9aAW7YlJ0Fi5Y6EY+FlpKwA9bNCoxkmnmeWy5s=; b=UiSUjRvn4bt4fTpZbB6v2aUpuB5T+mmaU78l+AG+fJZIiQ8F762kZDIOJXFnz2c09j ly9IfwPaAJTqHqCDEuT5mt8uCerrxY0+YzW8PoJhx7QqnMuYijRUHl0yNK7QepxiOqad XjDdjv2LtmX6NZ/v/iDM9NDzeNyI0WOSqo/rDOIx+j//f41yy1tfNI+6T+oFXIFLgLFt j+Ywwju1CiC+FJzzhB4DaR0l3bPk+mHB5kLqyX//PrsYpeaflB2TZ03XHXh9JLAPudEI Gc09CScecUDVAe919RzhdGK3sC1T9NG47GTNOeuFSiJRFmnvfUSiHVjpRDYjpeUWmLmV GJCg== X-Gm-Message-State: AOAM533CLbBE5WgjI3Xy5whIKTyJf0cHIrK/ltbQtZLI9Dh+zERn8t5x qlA4+hAYrtC7hq9Fx+VSwbqc23JjOaes7A== X-Google-Smtp-Source: ABdhPJyzx1pT4sEPZrZeUalqKxrxZlS3UYcXHk+02+jyCz5BOzE2I5zex4IFjvdTCj/JRb0oe0oSfA== X-Received: by 2002:a05:6830:1dab:: with SMTP id z11mr5455319oti.247.1604349855286; Mon, 02 Nov 2020 12:44:15 -0800 (PST) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id t27sm3848512otc.14.2020.11.02.12.44.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Nov 2020 12:44:14 -0800 (PST) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH v2 20/20] merge-ort: free data structures in merge_finalize() Date: Mon, 2 Nov 2020 12:43:44 -0800 Message-Id: <20201102204344.342633-21-newren@gmail.com> X-Mailer: git-send-email 2.29.0.471.ga4f56089c0 In-Reply-To: <20201102204344.342633-1-newren@gmail.com> References: <20201102204344.342633-1-newren@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Elijah Newren --- merge-ort.c | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 19c30117b0..c6a0fc388f 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -81,6 +81,16 @@ static int err(struct merge_options *opt, const char *err, ...) return -1; } +static void free_strmap_strings(struct strmap *map) +{ + struct hashmap_iter iter; + struct strmap_entry *entry; + + strmap_for_each_entry(map, &iter, entry) { + free((char*)entry->key); + } +} + static void setup_path_info(struct merge_options *opt, struct string_list_item *result, const char *current_dir_name, @@ -839,7 +849,27 @@ void merge_switch_to_result(struct merge_options *opt, void merge_finalize(struct merge_options *opt, struct merge_result *result) { - die("Not yet implemented"); + struct merge_options_internal *opti = result->priv; + + assert(opt->priv == NULL); + + /* + * We marked opti->paths with strdup_strings = 0, so that we + * wouldn't have to make another copy of the fullpath created by + * make_traverse_path from setup_path_info(). But, now that we've + * used it and have no other references to these strings, it is time + * to deallocate them. + */ + free_strmap_strings(&opti->paths); + strmap_clear(&opti->paths, 1); + + /* + * All strings and util fields in opti->unmerged are a subset of + * those in opti->paths. We don't want to deallocate anything + * twice, so we don't free the strings we pass 0 for free_util. + */ + strmap_clear(&opti->unmerged, 0); + FREE_AND_NULL(opti); } static void merge_start(struct merge_options *opt, struct merge_result *result)