From patchwork Fri Oct 30 03:41:12 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868361 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 C558AC5517A for ; Fri, 30 Oct 2020 03:42:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 59CB520796 for ; Fri, 30 Oct 2020 03:42:40 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="WshNP+dY" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726306AbgJ3Dmi (ORCPT ); Thu, 29 Oct 2020 23:42:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47190 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725800AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 45933C0613D2 for ; Thu, 29 Oct 2020 20:41:44 -0700 (PDT) Received: by mail-oi1-x241.google.com with SMTP id 9so5384849oir.5 for ; Thu, 29 Oct 2020 20:41:44 -0700 (PDT) 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=OjCL1x/UCD1jtyn3E5ybdEdjSXu+u08PNMRbOq34jhU=; b=WshNP+dYm9sYhIANqVCrKK6uMArPmXkPklYfsIsVDLsUGs2WRMJM50wEsmcR4nxpoo eJHnqbbBqZhl/FXPBP6/HlQVoJcH+Q6CAO5CntVbTxfituwGnIy8DvHHgICngz7D8Xss KNAtKi8PS1h3WtHhl+ge/cZVH9StjvyZe5X8QJU0800gcNwrkcW0FTCxBzmct+pSANC1 jlAvrnXWn67jou66yPzrryTko5tfnrnCPyk/nFNMobJMSZX12a2n0SNPVxZK2Rj/M500 zs2gPMF3DpbubIRHQJPSkoGW3TOm8YLVagSBybPu3F4aCWC0PIC+2+MjDXxw+Qu82kgK UALA== 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=OjCL1x/UCD1jtyn3E5ybdEdjSXu+u08PNMRbOq34jhU=; b=nmrnL1yLJF35HrU35n5C3KBaT7qRKjCm2VbrSVsCDKHpfCu4SaMvE2lgsR5yUUyoHc pW6U5Ybzu32rmHMLTRYVPCFt94PzQ/q0uQD/ZbmV43fUqMozjIICVYNC+Hx7Sr1z8xM7 GN4bf0v7UP63P7eV61dYwczXVE95SeqT2CBzxw/7zRbahASlxRVxAg+Ng892U5+ehuuV J+eTOcWlzi90dD08WHF7QpioYXLO9ToW9NSzHCG4HI0I/N7snfDscBAqjRWyQXEwNgGV lPRzJ69P/K2gFhJKDKVOJTDxjZihDvDDkj3kBFd0PzrMtO1R1XAxnD/IIltStCwi3jNr 9ixA== X-Gm-Message-State: AOAM533DTzALU87Fp/iyZdCsLedpI9RHvGwQLjBEmT80ztzjCWKowNSZ jlfisY6bFsVeee4Li665LfCnLqJllEAUYw== X-Google-Smtp-Source: ABdhPJwjdbd9J1/Upjo0EviQqPdjZ3CJzjO5E231qjkGokxo6fYNWXvm/eYMBV3ZodmXadV76MIBnQ== X-Received: by 2002:aca:5515:: with SMTP id j21mr272363oib.150.1604029303112; Thu, 29 Oct 2020 20:41:43 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:42 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 01/20] merge-ort: setup basic internal data structures Date: Thu, 29 Oct 2020 20:41:12 -0700 Message-Id: <20201030034131.1479968-2-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 Fri Oct 30 03:41:13 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868365 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 2BE1AC388F9 for ; Fri, 30 Oct 2020 03:42:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id ADAD12098B for ; Fri, 30 Oct 2020 03:42:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Th4ZU/tT" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726261AbgJ3Dmh (ORCPT ); Thu, 29 Oct 2020 23:42:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47194 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725815AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 E66EFC0613D3 for ; Thu, 29 Oct 2020 20:41:44 -0700 (PDT) Received: by mail-ot1-x342.google.com with SMTP id 32so4474566otm.3 for ; Thu, 29 Oct 2020 20:41:44 -0700 (PDT) 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=tSMS3p7w30guZJLBhcOnk/FlnusbE8UmdUxhNbx8iRs=; b=Th4ZU/tTBUSBPv+9GBPZd56cgOBbS7BOM5kI8/yyNrN/0HvqHEX2N602xJym9XAKkE 6gcrZ2+3wu43KcBy4/3bwGNDYziBGtYDfilChRnjDe1lEDSuCddx1RokRmPgEkn2SWzM 0GZ/OW0iJBOtBmXWpTiInoIQ2S7QvV6IoI5x2Aq/RUiG6YX7l1+c1ZTh9gwRNIdchEkF UOmQJcr04lqxx+nUxrxoFj/BsE+EkcoozC0UPoxt842cSqb4t6m/UTSchSe7jBwq8CF6 RcrSSVXicaGZieRkEYrKHnqvSS4pkLFaTaT/buxNLCQ7pUyc87RA3jR7FBpSRrMdXYQ7 x1FQ== 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=tSMS3p7w30guZJLBhcOnk/FlnusbE8UmdUxhNbx8iRs=; b=PY/dCpX2+5uzis68Kh0PWoLI0aI6Ll9R4Jm/1quIIDoHPFP3gdGEBo+jqHzanOpX9F e94pwnoAgIgTPvkwJExzmAT1ISWluL5V9UiTT/DCSx0Gp73YkH2/zWaC/8tgnAxe2m6b Jk1IhUjAkhpDpb2up+AE6gozdblw1fPzECd4pT7nB+ngoXM04DqtHvrOoYNlFjS7XhvP xyJWg37d6w//4DYh6UjLdFYf3OAw2U4evuZxorrDtkFibB7zFZo6hC1odL2xhaFJYuQ6 5hbhOlrAc+Umrldn7SisMz0vl5IGzxZSYdjZr5BKxYxcVooiqV547Plu/eiTtR4EL8PA o9Lw== X-Gm-Message-State: AOAM530hUN/RFx9lqxb1IKmxxDmp+rlowqabkUon1z98OzEPzIljTGgD t3ipBCCkjqGhPoQCKjdwIqWhh8B/6g86qg== X-Google-Smtp-Source: ABdhPJwCYvqbtvlt3CDBkheTLf+sMRO0CGRF2MgD7GJ7JE98x4iDyr+mwK2yCBwHA4t88f2Vzu2Ynw== X-Received: by 2002:a9d:3662:: with SMTP id w89mr184437otb.277.1604029304114; Thu, 29 Oct 2020 20:41:44 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:43 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 02/20] merge-ort: add some high-level algorithm structure Date: Thu, 29 Oct 2020 20:41:13 -0700 Message-Id: <20201030034131.1479968-3-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 Fri Oct 30 03:41:14 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868399 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 66AC4C388F9 for ; Fri, 30 Oct 2020 03:43:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1188821534 for ; Fri, 30 Oct 2020 03:43:01 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="FjHirYOE" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725943AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47198 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725806AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 0721FC0613D4 for ; Thu, 29 Oct 2020 20:41:46 -0700 (PDT) Received: by mail-ot1-x344.google.com with SMTP id b2so4454373ots.5 for ; Thu, 29 Oct 2020 20:41:46 -0700 (PDT) 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=MX5gbFs9WmJ5onWHsU9fnxyaMe1kENiKiYIypZLfQh8=; b=FjHirYOEHcChC/tfHwSBN/ZDcIo76WaUBJuxxAkDoRtDzJhAr4OyhaF1N5YczONRJT tlxml4t7bkfjt7vkDr+vY2FC313MoQ1VtKGB/KARETcZ3NVi2ChjF6F74+p6BumKzQbP mYnF6q8MZ73KgeQ0XEYArN9ISZvdI9NqM3+Dd7xsJH7ZqlUy5XW3ZbghdTqOxjZgUuSP N5PVOnsDZs6aCeo8Q0wnV5VpGOucV328VUT9shKxSs8RUjzzg10aaKBgTlLlQycccXXt goWFXJSGG9Q+7OtcfDQi0kBH4FaNzfiP1uOPs0Sw2jdekyoAi3QuBsp6PFQFroYsavjc WWVQ== 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=MX5gbFs9WmJ5onWHsU9fnxyaMe1kENiKiYIypZLfQh8=; b=Ii8kJvpOn+7lI+wk+0oTPR+saGBjOLtdBYEXn0wjyq6zeo0Mb2yQiKQToUYWr3bwBL wbXr0d+aqbriSrLDS1unGJlS73LOINtZYLRVXS5DmQqiDosc2nw7q86e5Vrppj3Kbk3c kCl+hklJ5UEnAGyarM/bxvet443tHQDWi8PONvqmaYF30PyKnm6WIVYe1I/Xu2GVa8lL dEVvHyoMT4mQcHaoKnUX4jmBQTWtg9NDcpzWJFqsa9RCSjHDckR442a/uAlqkwctSU4v 5YV4JfpJpPcjOEwWoGx6+rJhK69i0ZAJIXEAXEuQDJUoXIA1kjJI6bLmSfnP9La0eJWt /law== X-Gm-Message-State: AOAM530/B0c6PAMISVfMRFBiVssL+6ogpOKKzRR6bbBezcuLRPZ2K1tW thoRRLjF7FyMVANXUC2kKfrtEAVjyyQ07g== X-Google-Smtp-Source: ABdhPJyxjICFMSiaf2TsIfBDu8OISbi0cPSnC3a+N2w/B6bCtH6kuhb8dmixFYdLJJs28jJ6aGUaKw== X-Received: by 2002:a9d:67c8:: with SMTP id c8mr171426otn.211.1604029305195; Thu, 29 Oct 2020 20:41:45 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:44 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 03/20] merge-ort: port merge_start() from merge-recursive Date: Thu, 29 Oct 2020 20:41:14 -0700 Message-Id: <20201030034131.1479968-4-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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..bee9507319 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_ocd_init(&opt->priv->paths, NULL, 0); + strmap_ocd_init(&opt->priv->unmerged, NULL, 0); } /* From patchwork Fri Oct 30 03:41:15 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868371 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 5B64DC4742C for ; Fri, 30 Oct 2020 03:42:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 04FEA20738 for ; Fri, 30 Oct 2020 03:42:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BR/2QlOn" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726279AbgJ3Dmi (ORCPT ); Thu, 29 Oct 2020 23:42:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47202 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725853AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 633E8C0613D5 for ; Thu, 29 Oct 2020 20:41:47 -0700 (PDT) Received: by mail-ot1-x342.google.com with SMTP id n11so4473674ota.2 for ; Thu, 29 Oct 2020 20:41:47 -0700 (PDT) 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=yK+JG9hRuWwbWaDVifd7XcrTPIdCvS6YG9pr3fsEa0g=; b=BR/2QlOnHF9nre+tlaMxpg2z/DjmRS9McQkYexbFmVQCNUC2EYUIwzphX0E6hrN0ry z+iz1K9Pfku+IF83+sCZjUCZVmh2W1Oy/EHqgqPgaTaGn2qlGr33L+a4v9SvBTzVVSYJ 3U4/0Zvuc9gVaAdfaTH67/rx8QOHt37Ra10ad5/NfYNNau7RIEKhl1A9ei5nr20kWx+W 3JSCBIsRmxZLO2pGaVVvsDymVQsWMvP6aJQeNmnnVarlY/IYeRUEKXLPRZJIHa+pC+Dj RDFYof7DSmdzrMmWuusC5wlH2ucP0AVOPCl28zsyZbYz3kMB53LvTlhAGEVFGxLG+UJ4 grKg== 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=yK+JG9hRuWwbWaDVifd7XcrTPIdCvS6YG9pr3fsEa0g=; b=dMfzeJEKMyW5ZCTqEbq/MG/BWTcSxadPd0NSQNtRS+b/Xowl4UBxr/aaTrRZ8SYEKn Hm35/itIfp6KNCX6g7jCr+a4NbjiPpQ4EDm67NS4lhBYcDrAA6QlK0x8kj4Pd5k2efw/ FwIJf8YqTmgCk23f4yle5Nx+H7PS3bpjEKdIDovBppgpCHCp5RTCqwNdf35HmQuX4WUd 0yEEI2Oa/kvVgBsRIhZKwf+SS8v/cWy3xUYr3lRK8g2UcVNwErZSYMTYhlcDYcSpsL4n 10mAGP/0R3JKkFEOoqC3O51vzqgBDkapG0frn6JEfpDnmSATA6zrNq13zxbfxGRlX2nK sG+A== X-Gm-Message-State: AOAM530JWu6GN8jXbwf09wl5NEt2fqKghHtfBlAAglgQlO7DKl3PqitI y+7uZwIv2UWCAw9EaBos0JpXvWX5OikOCA== X-Google-Smtp-Source: ABdhPJyVh/BZVYaLmxYk5eEd5NPVlfjk87U5unF13344xOH8dcSetOuaePcJWgpWxegcLdLkOGDeGQ== X-Received: by 2002:a9d:7848:: with SMTP id c8mr214937otm.120.1604029306631; Thu, 29 Oct 2020 20:41:46 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:46 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 04/20] merge-ort: use histogram diff Date: Thu, 29 Oct 2020 20:41:15 -0700 Message-Id: <20201030034131.1479968-5-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 bee9507319..e629d7b62c 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 Fri Oct 30 03:41:16 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868401 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 D8ABDC4742C for ; Fri, 30 Oct 2020 03:42:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7BDD9214DB for ; Fri, 30 Oct 2020 03:42:59 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="H0emmo8V" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726364AbgJ3Dm5 (ORCPT ); Thu, 29 Oct 2020 23:42:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47322 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726122AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 758FDC0613D6 for ; Thu, 29 Oct 2020 20:41:48 -0700 (PDT) Received: by mail-ot1-x343.google.com with SMTP id n11so4473692ota.2 for ; Thu, 29 Oct 2020 20:41:48 -0700 (PDT) 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=q/AWh+RiIpndKYGuUwBn+oiGcyXdhD2Jq8CniHYSjMc=; b=H0emmo8VMK5ZUTRCQwVWemfEBn60loR4dvYghImjHC0zzoiAzUyIvaQIhDfR3kOEWQ 6Z+iPMpviRvCFWqvTqgXrMyM0SJ6LtRQCu2ST0QDsijfnpitJJULv1u45iqrrOF/J9eA BM3NnmHS08688iprl+arVw55HZmTeHruYBM/Sp+BP65/id4zmODNHz925yK+b9RM0iSr 0vdxcGzj+9HqpdKcVkz1W1jdxpshOai2ztHAZYYDZ+mfkBFsbEVN2fVIYqFyowMnY9EK KAXbk+cwJNARMGTFK98x6/JqwpH5ryVn/KshKa24KLc4y5ijKUQ8utZd6GaunH2vXJIF g1Yg== 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=q/AWh+RiIpndKYGuUwBn+oiGcyXdhD2Jq8CniHYSjMc=; b=R2d9ehb84penfcTWAtUZobAAPm7hxLyboLVr4u/JEfaXOR5d/00T2Bcg2XlTJQkM6s cLsb74iQEPJ5PZ2CYmhRNScP819CRs4oaulx3XYOlKKJlJLipzj5AB9GtBs0mZ5VLk9F NP7nh+27BHYFCUz8V871theOdBxb2I5Nsde6G3ONbDQ52kVAnkpWuEauSV0umb8GEe9c vr54/GWfq2iWgMp/2pDR/73iFLIXbpOxCx7lMVb4SzKigb16axAfZDnKqStlewgN+t2S 3yXlW+QvBSRMtwt48gP3bnL8zjv+qXu6Mkld8WrG8bcA83VLojllStqGpP9vIPhBpLjE ssAA== X-Gm-Message-State: AOAM533nt4CLKYRiTLr/WdzH+K6HEJyf6OKsfFkWX59fTZCi4v4wcG3n vy+ztbn4elBo4ninG1/g0ERn3AYE4WsOAQ== X-Google-Smtp-Source: ABdhPJzjfR2auZEn4UQ4CCUL9npN9hv0jJCfiBTs3D05XdGyVFkYD/Wui9R2UylL4Yq6lkjCiYG4yg== X-Received: by 2002:a9d:7cc8:: with SMTP id r8mr225325otn.30.1604029307671; Thu, 29 Oct 2020 20:41:47 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:47 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 05/20] merge-ort: add an err() function similar to one from merge-recursive Date: Thu, 29 Oct 2020 20:41:16 -0700 Message-Id: <20201030034131.1479968-6-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 e629d7b62c..ffea7ac8ea 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 Fri Oct 30 03:41:17 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868377 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 17EF5C4363A for ; Fri, 30 Oct 2020 03:42:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A2AD420796 for ; Fri, 30 Oct 2020 03:42:43 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nFfdp9lV" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726238AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47326 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725790AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 9E4D7C0613D7 for ; Thu, 29 Oct 2020 20:41:49 -0700 (PDT) Received: by mail-oi1-x243.google.com with SMTP id 9so5385004oir.5 for ; Thu, 29 Oct 2020 20:41:49 -0700 (PDT) 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=O+deo6nN5TuwCDIySNiBUkKPdHa3hRownvy8mhficaM=; b=nFfdp9lV8hEJTt/YT4rkeiXQrap2OAfeLowLgbyjZ0Ni1bW0E0ME6MWUd5lfHzE5Tc +NNW0I4DBmAZOyNghiYGGtpjbdIxLSZqNxe+nvkHO9H6xa0766lcoph/6oROzva7fiBc A2EJ9M/tKyrjH1RKR04bmGISxm6P+W7fSZfIzrjS27r244jSyhjXM6rO9GazbhMz7Pcz ZR8oBPud6mmTWIGsFQ/aS8heEu4SJYGLQWxZCuBUXjuJVK2WK75zp5QByVLnw0hjqe6X dsD8TT8DKGfeKOMRqM1mCfQo/Flthl9cdGWNGddYaWixb02yvXCQJHIvaQjp5mUc3vhC UUgA== 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=O+deo6nN5TuwCDIySNiBUkKPdHa3hRownvy8mhficaM=; b=rGC9SykvE+3VKMjNjpyQRnIh185IeFlhqTbd/MSm71gm+a+p6lXuxO1g1DgViU1nmk CrT4yQUTQmjcoXm50Enazc7gVbaCHPtAojiI7oVdTXZJ4Te1oRkzwgoZ1W6ZsVI8Yp0e nxy8pXqbTIcmR3acB7qWcduo01c8JTM7Hq92QF//dxn3dBQeO/mGoEZeHD0zThUub9Eh ZuPlCvuIpoAeYGz9KeNB8W3p9ao35pj/5efef2yBvFEXE+hi+aIF1DczZ3357JKkNHN3 fxy+ZjSsR9B9mwjEEuTGn4HJdW3AfNXNpeX1ROYo5HZ7gzc5L2S9+WZlD/TPpkmti3+Y 069g== X-Gm-Message-State: AOAM530YzPAhX3Q/EfDHyFHP32VwxkgBUp43l9iDLpDrix47XLBoQ0of 5fzBV77oN5icwXRLziPeWFAsAsUwo1Iwkg== X-Google-Smtp-Source: ABdhPJyFVe9XwXt/SlM/CQKdoBTdDkDXFhZta54P8q+pBqZRsCzSXfkWUKhStuhLmiPvo+qZKEOD1g== X-Received: by 2002:a54:4194:: with SMTP id 20mr271586oiy.137.1604029308779; Thu, 29 Oct 2020 20:41:48 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:48 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 06/20] merge-ort: implement a very basic collect_merge_info() Date: Thu, 29 Oct 2020 20:41:17 -0700 Message-Id: <20201030034131.1479968-7-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 ffea7ac8ea..d652f1f062 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 Fri Oct 30 03:41:18 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868375 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 D79EAC4741F for ; Fri, 30 Oct 2020 03:42:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6D1A720738 for ; Fri, 30 Oct 2020 03:42:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="g023wwbF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726253AbgJ3Dmh (ORCPT ); Thu, 29 Oct 2020 23:42:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47328 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725831AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 B2A7BC0613D8 for ; Thu, 29 Oct 2020 20:41:50 -0700 (PDT) Received: by mail-oi1-x244.google.com with SMTP id z23so5411845oic.1 for ; Thu, 29 Oct 2020 20:41:50 -0700 (PDT) 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=oQ3dGlZGxZVT3M098u1YqkVcMHlVyY9FmXORDjr2ygk=; b=g023wwbFKFlGCpSNe/GP2WXHloR3InzR6EiM4JGSQq+gPGr49xCdIsKD4ill0EM0Vl 2sZsnxQfy1vARzNV91MyBGejeug5V2yOajbAvpUOGxun4HSV40xrV/Sn6OuijWFGTBfO L7Xv6sLPcrNPmOZXg3edb1vgxuSAjzbX4AQ88uKmkKH7V7beWG9vfX8qTK74A24RjR+P 5DrOCqaVeG85JbQ0syotLyxQUZ3biJ4ZmNVgaD+xxrGsmQrPlbhHd51gc44dAfRILhfJ K8h0T3ZI+Abrwc5Ileeb3zaxSeYDH8yJDqNfV7JiAUsn2pFIK2/G7FcXOxJVG8P8ibAc ermw== 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=oQ3dGlZGxZVT3M098u1YqkVcMHlVyY9FmXORDjr2ygk=; b=LolllxYnUnh0gU7LIp0wOSZq1lBQu3UgfKBvK6R01xljNFBJSIUbESsc1ZlUnntN4n LhwuTHJapbrTQbIkKn4yDkHp2JRb/XN7Hdriw0s2X8BMI/4JFXrC145o0DefgmNiiZgi VoeXXdGB+XaA9lJqBjQSeohrImKqAfLc3oiVytd49db3oJoZ76FrzfnYCOzpqWuhnHe2 VJTuxihqsf8WfFEf18T7jttF2vwwmoladQqAf+/MzRc1M2X9t3qESyzpmtX/OQ0WGMgk OCsYolK4BeaEoz9O7Zmfr7XIKFBaoKMdMECm7ACERORzD3bGcTnaMDGWe4AmQPS0mArC 9l6w== X-Gm-Message-State: AOAM530ybKjUk6QBh80WcTYjLGK9qLZGU2LRXZXnzDNEfU2s6SIMqoR0 pKpDDEsSnq+WDf3zYbU5l3z+mnV+L2RM9w== X-Google-Smtp-Source: ABdhPJwKcJ2a8c0oPH5Yh7sPgY1YWheGHB6PqWys2FCmRHY/O1bfelKjahd/7dyWUKnqUS1ydz2L5Q== X-Received: by 2002:aca:7592:: with SMTP id q140mr279044oic.87.1604029309845; Thu, 29 Oct 2020 20:41:49 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:49 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree Date: Thu, 29 Oct 2020 20:41:18 -0700 Message-Id: <20201030034131.1479968-8-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 d652f1f062..7083388a47 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 Fri Oct 30 03:41:19 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868397 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 E1AD1C4363A for ; Fri, 30 Oct 2020 03:43:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7ED1E21582 for ; Fri, 30 Oct 2020 03:43:02 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="gDMOI/RK" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726392AbgJ3DnA (ORCPT ); Thu, 29 Oct 2020 23:43:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47330 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725909AbgJ3Dme (ORCPT ); Thu, 29 Oct 2020 23:42:34 -0400 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 C8CB7C0613D9 for ; Thu, 29 Oct 2020 20:41:51 -0700 (PDT) Received: by mail-oi1-x241.google.com with SMTP id f7so5396780oib.4 for ; Thu, 29 Oct 2020 20:41:51 -0700 (PDT) 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=/lyLUi9f36c5DAcnWpd3TGmdiXq/99VXer78xLZtz3w=; b=gDMOI/RKrfEJRqsk1yWmR8ziZ4nDSRKTOR93pIdBQIqo2+y56QK/ExO2ns0whftDjC bLWKt/Yk5UXxfEpkdBRq3RsCDX3mx9C81iBnhZqYZb47FWx9D5hz9kXnNj4WeJ+VumKj fYQFOPWdb6/QdVa07xDvnGeRFvDfo46gqTNG5zPIbOCvQ8XxjnhFb4oG28Hrf/cS8reM 88hCR5JB9L6XaK2MYoHd3iAMfWtSTR+l2BzbdT1qn0Op9UjzJ/7/jY6g3NghTPHJhpM5 cXyxANii/eZANyVfJCDuFqqraU5G5wIuDKGvLQlGWPR15CpenpgVdfy+zjFe7TPY6xe/ 5lxA== 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=/lyLUi9f36c5DAcnWpd3TGmdiXq/99VXer78xLZtz3w=; b=lbrTqPNwn7NQowON9waxFCYhZtvT5cYtR9BcMhfQQumVimr6xxZK1vYJaY0DJ00EUo HRqF8AA1C3Qj8ruiE36iIWlq63zaQ0CgWE3QYlew2puzwWiYGC3m/8Qgd/oPzjeISj4x TwJjckl+JsTR+uJpsKtSWA020OQ4PgRzkVzVNciY8+HE+sm2dwNVf9fxeSrQAXmBYSxI 8ZZJtyJQY2CqSRTswkYQ1IFk+KaqaUB0ChXbjfF5f1j+fNaM+CApxijxBGmoK8P+e/Ua WAaY2mP5U5tEE61hiKqvMNAmZG1iIixDwTPDq7sZMqggX7dKqEWEzJv4CtAArYrSrWDe dlUg== X-Gm-Message-State: AOAM533Nb6QJ0HgkzDjidiPkiIM0Ppy4KokD997p31Ow/FTpZJMUOztp Fe/wAFcUkmaHwxYPymECkUl6JaF5DMkThQ== X-Google-Smtp-Source: ABdhPJxJRGvB6kE15fsiKEUtmDR1KYXpKvY7gEnj3XjQsJwMYSLVbGyK0aX44QicfRpJezEVTT9Ncw== X-Received: by 2002:aca:1803:: with SMTP id h3mr271785oih.148.1604029311004; Thu, 29 Oct 2020 20:41:51 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:50 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 08/20] merge-ort: compute a few more useful fields for collect_merge_info Date: Thu, 29 Oct 2020 20:41:19 -0700 Message-Id: <20201030034131.1479968-9-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 7083388a47..86d9b87cb9 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -96,6 +96,7 @@ static int collect_merge_info_callback(int n, size_t len; char *fullpath; unsigned filemask = mask & ~dirmask; + unsigned match_mask = 0; /* will be updated below */ unsigned mbase_null = !(mask & 1); unsigned side1_null = !(mask & 2); unsigned side2_null = !(mask & 4); @@ -108,6 +109,13 @@ static int collect_merge_info_callback(int n, unsigned sides_match = (!side1_null && !side2_null && names[1].mode == names[2].mode && oideq(&names[1].oid, &names[2].oid)); + /* + * Note: We only label files with df_conflict, not directories. + * Since directories stay where they are, and files move out of the + * way to make room for a directory, we don't care if there was a + * directory/file conflict for a parent directory of the current path. + */ + unsigned df_conflict = (filemask != 0) && (dirmask != 0); /* n = 3 is a fundamental assumption. */ if (n != 3) @@ -127,6 +135,14 @@ static int collect_merge_info_callback(int n, /* Other invariant checks, mostly for documentation purposes. */ assert(mask == (dirmask | filemask)); + /* Determine match_mask */ + if (side1_matches_mbase) + match_mask = (side2_matches_mbase ? 7 : 3); + else if (side2_matches_mbase) + match_mask = 5; + else if (sides_match) + match_mask = 6; + /* * Get the name of the relevant filepath, which we'll pass to * setup_path_info() for tracking. @@ -145,6 +161,8 @@ static int collect_merge_info_callback(int n, * so we can resolve later in process_entries. */ ci = xcalloc(1, sizeof(struct conflict_info)); + ci->df_conflict = df_conflict; + ci->match_mask = match_mask; strmap_put(&opti->paths, fullpath, ci); /* If dirmask, recurse into subdirectories */ @@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n, newinfo.name = p->path; newinfo.namelen = p->pathlen; newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1); + /* + * If we did care about parent directories having a D/F + * conflict, then we'd include + * newinfo.df_conflicts |= (mask & ~dirmask); + * here. But we don't. (See comment near setting of local + * df_conflict variable near the beginning of this function). + */ for (i = 0; i < 3; i++, dirmask >>= 1) { if (i == 1 && side1_matches_mbase) From patchwork Fri Oct 30 03:41:20 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868393 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 219FFC4363A for ; Fri, 30 Oct 2020 03:43:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BC09521582 for ; Fri, 30 Oct 2020 03:42:59 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="li9KhdcW" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726384AbgJ3Dm6 (ORCPT ); Thu, 29 Oct 2020 23:42:58 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47332 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725996AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 E2565C0613DA for ; Thu, 29 Oct 2020 20:41:52 -0700 (PDT) Received: by mail-oi1-x241.google.com with SMTP id j7so5348917oie.12 for ; Thu, 29 Oct 2020 20:41:52 -0700 (PDT) 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=8EAdQR7/bcDpixXRS/pkUWch9ufWkYYXtudDe5isTK0=; b=li9KhdcWqdRuuL8RKR1swxRrzlMqCIpWMguuw9XO1XGUIUaw2mjxj5k5UMk2yStEbk 0clkdxDzH5VNSxJer7rq2xC//WmfWLcklHan6hOF91ji5gJ2NM5v2ENdWOEyXZk1uqK9 XKRtsKLoRnlHxKXVttSDFpGvEhuMCGmyiE1NQw8UeTORjwhSdSz7giVu9YvKEwUZ0LzH xQ85V4LtX5YGuDKw6qMMMSWfBzEEJoWBz4bQhTkypRqLqJP1FpARcdrmV41mQA/cEsJB VUeJ24DRLvg3nxhoPx8iY5lhSz6WCuDgl4r4GaZmKYWmyB0vzSXtYxVA1Ml+KM/27MWP WU/g== 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=8EAdQR7/bcDpixXRS/pkUWch9ufWkYYXtudDe5isTK0=; b=ZePnsd+Sd534POHPDqemSmnSC7Pdh9S4INjg3fNrFmf3LMk86NWANRvOz/GPdirbYT KYpsAULkMx6Fa72feZb43RBdcPOSmWdsBprfy8KPyQlYAY3tZmi407W7OkCNJEX63DTb 8WGZoc0GfHkhkT620qkK7dYzMPCoX+bcCT8WAELgtckOTqzQbHnsgGcrrYZLY0VvzYrH ySGPTbJr5ZoDAejiEd7EXVxj4k9b8zn75Htf6sf7vszUdxXnd4SoZs1KhdSti5XO6H0z uD5vZyfuAD1Qr3G5J2UtuMQHyHnU4CZorrakn0VO8fyzOfDr81RvHpERYGOHJoHokeHt dycA== X-Gm-Message-State: AOAM530MfXLNILcRiHKzJM7yyg9uM7wEpN5zMOOaGhjvNagcS76KD8ed iU92R3DL0oyefik2PzfyzeLmyy6cmDhOKA== X-Google-Smtp-Source: ABdhPJwuFqB3UY376d873pM4yOeM75f+8nVIEBwfd+jAiZ3znbhwiu0Vm3rDzDtMiPAjI9py3ZpgVw== X-Received: by 2002:a05:6808:8cc:: with SMTP id k12mr267091oij.179.1604029312115; Thu, 29 Oct 2020 20:41:52 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:51 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 09/20] merge-ort: record stage and auxiliary info for every path Date: Thu, 29 Oct 2020 20:41:20 -0700 Message-Id: <20201030034131.1479968-10-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 86d9b87cb9..60e2b78e2d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -77,6 +77,50 @@ 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; + } + result->string = fullpath; + result->util = path_info; +} + static int collect_merge_info_callback(int n, unsigned long mask, unsigned long dirmask, @@ -91,10 +135,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 +203,14 @@ 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); + strmap_put(&opti->paths, pi.string, pi.util); /* 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 Fri Oct 30 03:41:21 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868379 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 0B7BAC56201 for ; Fri, 30 Oct 2020 03:42:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9A3F42098B for ; Fri, 30 Oct 2020 03:42:47 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="URlyQxEx" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726325AbgJ3Dmq (ORCPT ); Thu, 29 Oct 2020 23:42:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47334 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725806AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 D33E0C0613DB for ; Thu, 29 Oct 2020 20:41:53 -0700 (PDT) Received: by mail-oi1-x243.google.com with SMTP id z23so5411923oic.1 for ; Thu, 29 Oct 2020 20:41:53 -0700 (PDT) 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=qYf/QaTh48jEgR1wqxr56L7b2jjhLlekH2WhA065ZxM=; b=URlyQxExhWxgyKJ/xFQLdCEWB1kcQLyRxGj7aQaap8f3+0Pt5cdjPkbFfTTYp9aF79 34eZ2xuL/x/dIyzWN6JRii8Qpj9vV3ReSNwaaWJrfNT8g/JS6upRvyPl8ZXMGu1R6NZk TzPudKenU2TTp8mPMwXI0tEuCHuXIgEeS/qi6B6o0wrDlzV4vRGP+VhPTKm1oNa1Hhcu S3UlqQlFz2BvtjuCyiTHvj/CbSzytXqrJDlAz5uJzkYVDmD9LzhyrlRmu3xVFTV2WklG spINgb/hyqYYTzhKs25fG2/aeQJ7U0RrgmRNnrZogBYEYV485E6pRLAPb4A7EmF+fMHj 4dfA== 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=qYf/QaTh48jEgR1wqxr56L7b2jjhLlekH2WhA065ZxM=; b=XjIiinWVXTLXYJi9FDw4IMuoIZlaLa0TBQevb26wkPxrA6jfacjT7NIEYBwUQAiRSG b15ZJv1uciu4bwl5mjF0/ss9muQcFQZvoBn44qY47RZBAp0YAMCW0ijCpRSoJwaEdIaJ ICRoiGilS7RJfXEI3MxO6/EC0RKEnVHUopwYLghdYxB6ShFIGh5Oq6j/lVbvdKiNEy4S cRB8LUiccxDODZUS6FYd18nZirGVuHgSDAf9gcHd/uK8PJVElzODTNOWvBUUPQU2lLV/ ZM6AZQinyQyhFf12APnPuzEqi9eCmtQZEsjrIKAkSiXj0cUwMsjhR/6qixN2w6kl05OF w4Gw== X-Gm-Message-State: AOAM53268N3KaYdlsqj0st7aEMwk2UdfKKr5oV3ZJHaJunSu9MHEfagr IeiMwTtnbe/0P9EPYZidwKktrkKvP+siuQ== X-Google-Smtp-Source: ABdhPJwS7/b/yma7/64yHyBVw/bXAd97KqMqUoIBOm2aFk3bcyHCi+dYBj6vyIVrSiEPdxWdXDmKIg== X-Received: by 2002:aca:d6d5:: with SMTP id n204mr306856oig.2.1604029313131; Thu, 29 Oct 2020 20:41:53 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:52 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 10/20] merge-ort: avoid recursing into identical trees Date: Thu, 29 Oct 2020 20:41:21 -0700 Message-Id: <20201030034131.1479968-11-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 | 14 ++++++++++++++ 1 file changed, 14 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 60e2b78e2d..2a402e18ed 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -202,6 +202,20 @@ 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); + strmap_put(&opti->paths, pi.string, pi.util); + return mask; + } + /* * Record information about the path so we can resolve later in * process_entries. From patchwork Fri Oct 30 03:41:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868373 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 9D159C4741F for ; Fri, 30 Oct 2020 03:42:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2CD3B20796 for ; Fri, 30 Oct 2020 03:42:44 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="I3N9XHTu" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726314AbgJ3Dmn (ORCPT ); Thu, 29 Oct 2020 23:42:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47336 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726096AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 07777C0613DC for ; Thu, 29 Oct 2020 20:41:55 -0700 (PDT) Received: by mail-ot1-x343.google.com with SMTP id 32so4474772otm.3 for ; Thu, 29 Oct 2020 20:41:55 -0700 (PDT) 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=TAmOxGVitKXhlYrJ/4fHaJEH2uvTcyZqXkfEp5oYRWA=; b=I3N9XHTuQn1lQ9yRiX7t5O0751iKiCUDZvHRV/dWNnu1/bdnyka5WVMfkSlLNcXmxo SNynM+Xk73gofoUsUl/Z3CxYVLsgiolNKTp6i0Zw0pKhcYTpBLb4EHgeDhHZdKXXCRBx ZVHRiQI8uqiiVWk6j1W19M8NfcXQ9yK7SNwO+pVCs1XFXTHr0FadXtoCSmheWwz7ZNwE PWy9n/yku3d8B42TeEBw3S4C2dA2gRb9YDQ3bfV1GQ/viMlXDzbn31xoX2iWv5rDuA/y 4sMMMbqrOjpZNmm2bi2hhkCrxUfidhXr472zAZ2cJruTMjYSjVQRmhwgv7wTrpQIL9lX JIKg== 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=TAmOxGVitKXhlYrJ/4fHaJEH2uvTcyZqXkfEp5oYRWA=; b=Ok8bwsjfc9Su8VC9iKYVshR+KfWzLKRDz6avSmBHKVbRccIorz7xtX2anUd1Oev684 fXLJAChj8DmMFXFphGtfvp+BE+ICZI7ecf1R6qhPVgNzNyhXc0MyFaN+VQT4DgRbDeHx mER4K6hcimumJt/d5uH/yAWC0vlfimgi0OTK02KQhJVSQO4Lkyox1Gs/TG2u+qSb1Gl5 BmSfzUpYqXaNYpxHxo6r7rNJXvzJKiQXqH9eXZFB7L4WpdH0ISaLjFMQB5XzJozzsVFI 2UCevF+JKmG2W9kB+YwMVdoGaTWP72unNsw4AjDA3v8QZKr20lvkcTv0YQOEwriw5PVl v6jw== X-Gm-Message-State: AOAM530+8Me+cWA3jAbOXcSrnHlsnHlt+Wpfft4Rn+4PWX/Znkn7wssb sViExIZOsWa35mUbVYtfRGISsdlh8MbNCw== X-Google-Smtp-Source: ABdhPJy1zt60hdFrlMzrUZXUmIMWrP6BXod4Nv0xCkWsRF3XGHXqBXB8oQWRI2HfybHTfObm2oymsw== X-Received: by 2002:a9d:7f09:: with SMTP id j9mr192328otq.184.1604029314104; Thu, 29 Oct 2020 20:41:54 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:53 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 11/20] merge-ort: add a preliminary simple process_entries() implementation Date: Thu, 29 Oct 2020 20:41:22 -0700 Message-Id: <20201030034131.1479968-12-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 2a402e18ed..f4bf1baf78 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -324,10 +324,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 Fri Oct 30 03:41:23 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868367 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 B9621C388F9 for ; Fri, 30 Oct 2020 03:42:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 59F1820796 for ; Fri, 30 Oct 2020 03:42:47 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="sDhVsjPS" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726323AbgJ3Dmo (ORCPT ); Thu, 29 Oct 2020 23:42:44 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47338 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726111AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 1FE78C0613DD for ; Thu, 29 Oct 2020 20:41:56 -0700 (PDT) Received: by mail-oi1-x244.google.com with SMTP id k27so5356122oij.11 for ; Thu, 29 Oct 2020 20:41:56 -0700 (PDT) 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=qOJxQ7Gp9vO6NQOwsHIkhlAXSJ9DFR4iru5x8tMjHYs=; b=sDhVsjPS42SzsUZh5C0RsnOjqrXIIJirnjRk5ycA+Pf7MDM5Zf69wEWjnFo7v4MPtI nZR6SgxSDL1flAlXg7EPv9+1n0rpMC5fAjai3mWX3XgCSLrls701fwOAG7Etwn8CdqPr fUxFnLYVqWa0A4TVVO5mBQWRQGm6vCS7Ikn9HyvjC0Zow4pgcyMx72/0V/bsHVZGlfPu Oy/pbRFxJpYVUlQfoDJ0bV+xkVF1f9UOm+hWHA684oG/b8lBZF5RN0x1E6u9/Qg68FUs KvfmfcUGUaSmezxufmzjJ6dpPpMD+Eung28st4Rn36Dsi8ccEjk6Wu6CqQlW6ZwQjb+B r9dg== 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=qOJxQ7Gp9vO6NQOwsHIkhlAXSJ9DFR4iru5x8tMjHYs=; b=rKxk8S6Cok04Xo8CwaR4hxJB8ETULclMoFzTmlNsntPkeC9ow+cG6G2Au/NtF5oMlz x+MWfzY97Wz5xfs1/NlaQMTOra5qzjkT47daul6wwGPeFZBWHldtXjGPZdLwX4mj+3yo qbZxCrEsp/0z2GxNPstkulf040ZoYutquWvbFGdglx2pMc3IeLkGyXkzsOQUuacbdnq5 HGKGeQbvqo4NuNE9N4lN6QOIovNkjoTn3BAzc/4Qb94OuiFQlK2JeAovAIrMU7eAkaiO 52JuXgNeaxqu2mf4KFSRW2w0Abj5uWQ5woLXncJixItcoUf4gvGmAND+qhDXSsEA/FJI u6WQ== X-Gm-Message-State: AOAM532MdLu5vmZSOQEKXOBjLe16IHwkLhqme8KSU9GfQ7Nx1GFOOW7O 6YhuOrvTj5a5wKwylKICAS7EdDkZa/HNgw== X-Google-Smtp-Source: ABdhPJyH1WjV9BnSNOsQCLSBGPaO9+aTipT2BolIjLYwsURSMtd9qMdpNCvHGrCWG2p3O2exIn5V3A== X-Received: by 2002:aca:df0a:: with SMTP id w10mr263084oig.118.1604029315324; Thu, 29 Oct 2020 20:41:55 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:54 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 12/20] merge-ort: have process_entries operate in a defined order Date: Thu, 29 Oct 2020 20:41:23 -0700 Message-Id: <20201030034131.1479968-13-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 f4bf1baf78..31c16edd3d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -324,6 +324,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, @@ -414,23 +441,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 Fri Oct 30 03:41:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11868369 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 5353EC4742C for ; Fri, 30 Oct 2020 03:42:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E0F102098B for ; Fri, 30 Oct 2020 03:42:43 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="FjOL6ZrT" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726309AbgJ3Dml (ORCPT ); Thu, 29 Oct 2020 23:42:41 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47344 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725780AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 73281C0613DE for ; Thu, 29 Oct 2020 20:41:57 -0700 (PDT) Received: by mail-oi1-x242.google.com with SMTP id x203so5353472oia.10 for ; Thu, 29 Oct 2020 20:41:57 -0700 (PDT) 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=uSLjR+mw4410C/7AntQ68xJsxwFe3uCoyAyu8gQ9huU=; b=FjOL6ZrTxpnxD92uIQlmFxa2BPNA1LvOG/2iyldRlhe8e3GzVQrX16X/MCihIPzjww uhzcq3K30UuCBVIdB8PBAaAr8C0SOzTiAtrXgyCPZy1ndgXeIOQcOfGgOKGd29whVZRF ec0DK2OHjgIOYLpfberEL5Nmjh9LQtId75sU0IGSNWsbmXXmSmzcvqnpz3/4BGB4D85v qKQYX9Ouc/NtoKVnvgVXQ7vbpLjNJBUr3CNMy8pIyblCPHKLHwykgZ0XQI7YTaCNHMGF UWfC7EOSz64sx2KaUFdYd6sWvDVTyvzWjfA+HwRKU/h/UzTAJMMxoW6dmtmxSfNczcpk /BWA== 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=uSLjR+mw4410C/7AntQ68xJsxwFe3uCoyAyu8gQ9huU=; b=gY35EPik/av2rMKWX5fiY2vLR3UACWVuO4Up37YROdAt8kHd0sCt3laz5hF3BUo28H +OcKbn50zlO/OeDu3FJYRnD/JRtyrkvSCbBj6u7V5L3jH4P9VhpnajOvUM6dt3WqNlEH uTIl6R3JFjT4sk/yUY/do2ZrwZ65mUEJaI4W2DhaMVO/oc/ZxOBGtV869LjZilEnBd/V /WNG7sdN7joJBHYLVuDbhiqRTMmd+cII6TUzxhCApqafjv7MclPYgmNxA08WbWmJrVAe y0ED6DPw2VDjn7mb+mB9K0O/a6vsWOK+OQqGDBaeZI3j1ozacCP5/CSVw3sALWj0jH7A RKqQ== X-Gm-Message-State: AOAM531JRzrsrYsfDbXu/3ouKWDichAyPsDphR8nbUo7BurUpCgbVReg brN/stYpVReAiYVd7+YH1Tv+mGnxk60e6w== X-Google-Smtp-Source: ABdhPJxtryXmHnJ2ipWG77vUK3chVa4LfW6oYbl3Mb2jol4UDD68i7rieTC53wt2zsC72nuHphePew== X-Received: by 2002:aca:383:: with SMTP id 125mr240744oid.171.1604029316653; Thu, 29 Oct 2020 20:41:56 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:56 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids Date: Thu, 29 Oct 2020 20:41:24 -0700 Message-Id: <20201030034131.1479968-14-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 31c16edd3d..17159df5db 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -351,10 +351,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); @@ -434,6 +455,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, @@ -443,6 +465,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); @@ -459,6 +482,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. @@ -471,11 +497,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 Fri Oct 30 03:41: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: 11868389 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 4E3C0C4363A for ; Fri, 30 Oct 2020 03:42:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DBC9C2098B for ; Fri, 30 Oct 2020 03:42:48 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="c4UYHYyH" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726329AbgJ3Dmr (ORCPT ); Thu, 29 Oct 2020 23:42:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47346 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726117AbgJ3Dmf (ORCPT ); Thu, 29 Oct 2020 23:42:35 -0400 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 6830DC0613DF for ; Thu, 29 Oct 2020 20:41:58 -0700 (PDT) Received: by mail-ot1-x344.google.com with SMTP id m26so4422072otk.11 for ; Thu, 29 Oct 2020 20:41:58 -0700 (PDT) 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=KF594PqkhmRWa/EpXPObNxlZdQnyFkhPVXCNbZ3jA4Q=; b=c4UYHYyHrSHFm/2bcEEfpckTmeniKzhBwJWRPYT9f3+oV9ERQHq9QW9GgjnO1AZH7X +FzUReLEsCYrulEk4V77Xh26cutSEDMLPb5O8qQQQeXXrW+56vkUsdteuiNg3dE5dWrg o07eiKYc2VpUrqyuaubOpS8qcERqXfYjefNKDTRIpPkorOSK+xuYHhdgBAPYsbDAJl54 i07MTNTr7Vi0x3HJNc7kmUVzu2aIwj6QOqebc8I09Olum6KDVvO7A/pcqTnAeHQrQVCy RuF/OJk2RXFrL/NpC5ktVNIPIBuUgTcfZ2W7qRoAFXy/L5qWIQNGR90QeC4/chehHyZz ay4g== 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=KF594PqkhmRWa/EpXPObNxlZdQnyFkhPVXCNbZ3jA4Q=; b=OwQ1HjWeMWWW9awQFFWI2gMV996h8+eM2g6DRuW/e+qctZRz4az2ZLD+CO0V5tlGe2 VH05t9BZUzR1fI4bw4NfP8qeDVd/8/Ld7FEFjqa3F5wMdCSxuJJ8/W8x2gSqhAzKh2u+ qcoaiimthSE23ZBEEo6ojCXB5Hy/tIG5mHelou+QpMoYL7mHiXkBJfBQzFyjjQLG1pRz 7yPIzrKwVHxTqMHBVkew9ISP76qBYZk7e7YMSRthrnM6Qe9HlJVrrNHinBPHmizAIAUB Ss1dzg967yifhT4THore6NCi2AKOSm90chMpdEW5Lf9a+N2XskooJiLMG5CS/5HTTm+P Y+Aw== X-Gm-Message-State: AOAM531NLaTIKB7eZlieBj8kSISNzmwR3mZrytKxZFtoEZnjYid7Y1fr sO+XWijq2obmZjKtoP2qUQCgW100ZtDo3g== X-Google-Smtp-Source: ABdhPJzVab6h8zLm2vZT538cJnsuKO3klhZAezJ8U6LpEeJ7py56TYS6/kdnrj1ncsvIfNB6l5njzA== X-Received: by 2002:a9d:828:: with SMTP id 37mr169691oty.147.1604029317644; Thu, 29 Oct 2020 20:41:57 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:57 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 14/20] merge-ort: step 2 of tree writing -- function to create tree object Date: Thu, 29 Oct 2020 20:41:25 -0700 Message-Id: <20201030034131.1479968-15-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 17159df5db..ad34800705 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" @@ -355,6 +356,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) @@ -503,9 +548,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 Fri Oct 30 03:41: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: 11868381 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 82066C4742C for ; Fri, 30 Oct 2020 03:42:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2178F20C09 for ; Fri, 30 Oct 2020 03:42:51 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="EjPXlaHd" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726336AbgJ3Dmt (ORCPT ); Thu, 29 Oct 2020 23:42:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47326 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726152AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 A18D3C0613E0 for ; Thu, 29 Oct 2020 20:41:59 -0700 (PDT) Received: by mail-ot1-x344.google.com with SMTP id h62so4441929oth.9 for ; Thu, 29 Oct 2020 20:41:59 -0700 (PDT) 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=tLW3nDz6OxzlWDmz3MiImCCTFf58Op/P3wqn4AqZ5yU=; b=EjPXlaHdIoS0Elxw3yJNckxqmB0iX/3jXhA5DGv0bBvdHfjGUREiS9E7zjk4lyGyXT slqfOQd8nI1YHsFvHf7Efax5+zoe4GQM87nUHodjQDzGPfD14Lpp/J0tu/nkvwDI+bP2 txV6e4nQNuEZkO8YlsS3w3CBRNogTbRYVzhkrfHPHRebR/r/eLQyIUbX+03ONcn+wQPY nGP5Js5r6l5si8WfBONbedTDXLfBaalim+S9iW1muqXM1blQqzd4dPhdTO1L+MUvsJR/ Jsp/OT5c1XitwZzD1JW2binWo1U/6wP4rvqwVBwj61k0ehbV53IP+I9mA2ujUuwRCoht gkXQ== 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=tLW3nDz6OxzlWDmz3MiImCCTFf58Op/P3wqn4AqZ5yU=; b=jop7dtrZL4bXUdLr1Do01ZQd2SuZ+OYZoc0p5SDxJ6xWlqOimbNyWjkRPozFHsJSp2 rilxHG51pViGlcokR89dEGTs4Lfo45W3sWy2BKofNlzZ+VXpnXy4Bz0buWAtvAsLMNUS d9UVr0ecepDKjLZ21tvku7p6ufE8m/cVU9cAXyUwELGAP48dh6fGr5IpMFRdwoF7t4KA WM36aGeqJ/Dtsox2sY9fV9wNm2khsU6nFN859DY+5Tl3nWJ3MuwkJly8K8vRWnXHOcym 6n5ufNyEJ9tudNOYBHnD7aocneHv/wHjyzwMi/UxWlIYrtL4FY3TEp2IBtATwrvNDv6X BUaA== X-Gm-Message-State: AOAM531q7k01lFk5yoXzBgzsIdkd9qWy8CBMBjJzHinh4jhCdpZOaY4v Ljnerw7wfTe5Z082SVLXsGtxUPn18/3ORQ== X-Google-Smtp-Source: ABdhPJyRsjaanj2bDoekFYPbjDQB10LaV+m9vRa5OA3blsUhcowH2J9SNV+pD/MGOjsAR5KFrAgYeA== X-Received: by 2002:a9d:68da:: with SMTP id i26mr203289oto.200.1604029318677; Thu, 29 Oct 2020 20:41:58 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:58 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go Date: Thu, 29 Oct 2020 20:41:26 -0700 Message-Id: <20201030034131.1479968-16-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 ad34800705..ac58fa6f04 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -354,6 +354,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, @@ -410,12 +413,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 entires 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, @@ -529,6 +620,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 @@ -542,22 +636,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 Fri Oct 30 03:41: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: 11868395 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 2B67DC4741F for ; Fri, 30 Oct 2020 03:42:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CAA74214DB for ; Fri, 30 Oct 2020 03:42:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="RzNYBrdW" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726358AbgJ3Dm4 (ORCPT ); Thu, 29 Oct 2020 23:42:56 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47348 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726184AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 68479C0613E1 for ; Thu, 29 Oct 2020 20:42:00 -0700 (PDT) Received: by mail-oi1-x243.google.com with SMTP id j7so5349137oie.12 for ; Thu, 29 Oct 2020 20:42:00 -0700 (PDT) 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=XRq3ceItSoCNIEoFX+x4KRX7d9hx7jei8MnJe9/TxCY=; b=RzNYBrdWRe94C7gkM34NsiB26VhqZ4vNt8SPpgKeyrtaagPRfcXHxB9v/PZac8czEJ 1pgJhHVLyCUh1fN2JVGEsxFHNajovI46SGSWDQrFgitelo00n6aCCRJAmoVSl6xdK7KE 6rD+yrg+rqQGRVcvoW2wYw0r86DpF1XcTiUDhEkJQbWVBBDs6/020NVH8/Dq1jWi1ZUI A8RHN52FkiMXQ8EqhbOsOy1lJ3TkI1tXuT6+DHA41Z5NdmjlIrnG/Q1PUaTammFIukdT qPNcQB/NAmNP6EPJhyxgO2d+rl/v49ZK3u3pBe4AZtx7/PqrxwGvJYHP7uVukT1z7P44 B7tw== 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=XRq3ceItSoCNIEoFX+x4KRX7d9hx7jei8MnJe9/TxCY=; b=J0a+OgwoVX4/RiLHkCYt0DocvMCtYYs7Z3srTaL1BFgvv/9koVhS/sWI3rBpeRS71m uf6rCZw1T5ZzIiooL9z0HeKQr64QxjTfxDR/nIJiFLUBqfRATOHLhvNZqsGTQQh88eOI FUfAlb8k3es24nXDAgC5aON0/dLk7n6Yn78zrXtuGkYaWp7HkkJoSlbSUR8ItA6GQtwk cdB1WTvE+Sxb1+oA6eM6UMa62O00lZuU2gNaR58qX3/Lg64Db+DFYnXa3/cxo4VJ8qGQ KYv2B+s9Uj3DE7D6EitaO7Ctaxuv/lKrDkU9FVrD19RXHizh7lZ02swV+2YcQF+CSwOB 9NgA== X-Gm-Message-State: AOAM5327IiVtUv0BDKDgU40fVrksSZzba70Af+R3cF07rM0MabJIbunK CJd8GXsDbveZSaa5Aoe69hfIZ3fLt1sVAg== X-Google-Smtp-Source: ABdhPJzbB09lOL7t7qN1Rlu3pOBY6TZlC02RZmDTBofhBXLDN7GQAUd/IdvO0a2QVRGY40wYluDW7w== X-Received: by 2002:aca:b1c2:: with SMTP id a185mr271402oif.83.1604029319681; Thu, 29 Oct 2020 20:41:59 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:41:59 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 16/20] merge-ort: basic outline for merge_switch_to_result() Date: Thu, 29 Oct 2020 20:41:27 -0700 Message-Id: <20201030034131.1479968-17-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 ac58fa6f04..a5b97adfc4 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -659,13 +659,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 Fri Oct 30 03:41: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: 11868385 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 BFDA6C388F9 for ; Fri, 30 Oct 2020 03:42:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5CF1C214DB for ; Fri, 30 Oct 2020 03:42:56 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="eXvefOQh" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726355AbgJ3Dmy (ORCPT ); Thu, 29 Oct 2020 23:42:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47328 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726204AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 82856C0613E2 for ; Thu, 29 Oct 2020 20:42:01 -0700 (PDT) Received: by mail-ot1-x342.google.com with SMTP id k3so4469959otp.1 for ; Thu, 29 Oct 2020 20:42:01 -0700 (PDT) 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=hRM/UyOupsJLfM+8brweFn3i2Segwa0PDcUC6ikit7I=; b=eXvefOQhcPguNaAhXJl6ktEnwBbpyDvqmliTSuTuzPJXWYqoHL/jTk/MJYwxf3RMu0 aRw3zH9PWdExig1VxbifCuMysE2zdTiF2bXooSQo9rm/YSpZjCbEm1rtoJIQxYKGruCH Q7g7i/pfEaObxBz6gnTRZkgs4OtQFk5y3B3WS4Of3In5ih1vBHWoiMDbIvkTIgexZ8t9 ylUXFBqjiqW1qz8LsQnQ4CVa/t/Db1FkY2C3rA3xyPcMOzv7qRrdW4MIpLw9fvew9rxh uDMHqhwCNsJabkXo8A1hH9ShA1UDMk4+0YdwmKsJwBqboH7ndWGqTzZs5Vl/2ii7IkNL ZaxA== 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=hRM/UyOupsJLfM+8brweFn3i2Segwa0PDcUC6ikit7I=; b=cIpjuPeza/YQ/Qd7PiY5zYpc9Zi+f45a/WYL4RMD4KuklFedlFAnm7a7zBewwQkz6P Mi+rS9JcTg6H1r212YJVUqY8ao1fwvWz3TnYA+SaYGo8A/DaYGjgUPYQwXXhxXAbGjmW isizWtL0s2mgctkj4+Xy8HtziftN/g9uDl9paqU2hO+QfxaDzsngSvrrWQPZaIK5m9iL JwjX+nNGKzg+tWgGFbINoBUseyZko4JaZBnZzaDmykEg8OQNhP/p//FD75XLXC98w5cH E3AzUYripqlkgoNBElxssMXMvibB3wa+jV12kCxUzXIUmBMQgVs4R3Gf2YgXKKq45ksJ upeA== X-Gm-Message-State: AOAM5320k26P2EsS5dCD/2xrD0S/AEKdnPy5CT4DqO7gNTPCzHt/ppO5 QUOOtIaCcfr+jtwEYlQhFwKbiLVfj+ELVg== X-Google-Smtp-Source: ABdhPJyeEGsMKKE7XokWeYb6j211wsSesM6T/LdxLum1CRYXlIFZ7T7A1HS5PsEWav3WXsQVqusZ4A== X-Received: by 2002:a9d:6c1a:: with SMTP id f26mr177457otq.1.1604029320722; Thu, 29 Oct 2020 20:42:00 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.41.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:42:00 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 17/20] merge-ort: add implementation of checkout() Date: Thu, 29 Oct 2020 20:41:28 -0700 Message-Id: <20201030034131.1479968-18-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 a5b97adfc4..4da671d647 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 { @@ -663,7 +665,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 Fri Oct 30 03:41: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: 11868387 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 55E9AC5517A for ; Fri, 30 Oct 2020 03:42:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E69B121534 for ; Fri, 30 Oct 2020 03:42:54 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="A0Pd5M6o" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726353AbgJ3Dmx (ORCPT ); Thu, 29 Oct 2020 23:42:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47350 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726211AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 906FCC0613E3 for ; Thu, 29 Oct 2020 20:42:02 -0700 (PDT) Received: by mail-ot1-x341.google.com with SMTP id h62so4441979oth.9 for ; Thu, 29 Oct 2020 20:42:02 -0700 (PDT) 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=to/66f58ggxvN3D3hJjafigrplV2/UGbU/lYsScmKjM=; b=A0Pd5M6okvTNXywz7ougvLJbPBIuR2SCrrKA4XGm/TOZOiok6mYVuJvDM8dOB33Q7S XYwgGUJqVo4ZdpDayUh68NP8sf32SkY+l9gnWaK0W5A6XT/HXgcXpq3FJ2nscavczOdq COXKmd7o2AMNezqMaGihgWaASxrZRJzqLX6e6DTNVzAxJQLoHDZclfe2h/C/g/iS8snc Ln/RPybTBrrKuG7M0lxnQ+Rutm90iabU/PypKRZ1YIaFQo0FoxAOR2gzZLwDrttMurJD 2nPx06DAGdVBsY49u+/k2w7ajeItyiYf3tCT5zF/i3wEtuYh2jHsQWqbeqrNOyAtAEFs aCQw== 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=to/66f58ggxvN3D3hJjafigrplV2/UGbU/lYsScmKjM=; b=m8Y6t+8CC0GuxGVOHo1rU/q356agqmsrM96O1m1F6VZak5K8QW1SoD75tOaS4gW0cr EoLtX4cT/xbtSObTLDWg9wMIBC+P268fGXLWOEw2WQ+WN1yAyqmizBCnR+4BUYG0Sv+B s+/rJbtp2Fcpjsl1lvGALcPK+xUOffNKgMOlzKBzL7/Uk8KcMUGQleGcdamKhFcJiLaZ 0MJ1xYEWXxvnDw4y5xfFnNx2IOCdQLSkoQEYP9FFykYEONakejMhbuV8syLks5VVxKJ2 byQd6hD4SeO6+VVtx7I9xSgWB8EFVukUffpeTlS/W7Kf6W7o/MDDqOuMWCjsu/3PhTQh TB6A== X-Gm-Message-State: AOAM531uGt9wxkMkYss05QbyhGpy/l8tw2/aP1kUgDzlFffhQ1zUvLc4 vwYaKtxcSZOy5dPaPqoDhdTilKdqf0n+Kw== X-Google-Smtp-Source: ABdhPJz3hpfry77lY+PcvD9b0MLeR+LOfVaWKhqGzckWb4YMrwYtEo/uXxNqNY+ylNN9XRrPEFnbUw== X-Received: by 2002:a9d:2182:: with SMTP id s2mr199273otb.328.1604029321810; Thu, 29 Oct 2020 20:42:01 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.42.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:42:01 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere Date: Thu, 29 Oct 2020 20:41:29 -0700 Message-Id: <20201030034131.1479968-19-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 Fri Oct 30 03:41: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: 11868383 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 30469C4363A for ; Fri, 30 Oct 2020 03:42:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C5EA2215A4 for ; Fri, 30 Oct 2020 03:42:53 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jYI89NzP" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726345AbgJ3Dmw (ORCPT ); Thu, 29 Oct 2020 23:42:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47330 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726245AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 93D7AC0613E4 for ; Thu, 29 Oct 2020 20:42:03 -0700 (PDT) Received: by mail-oi1-x244.google.com with SMTP id 9so5385402oir.5 for ; Thu, 29 Oct 2020 20:42:03 -0700 (PDT) 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=1VZpHTdzpL/PlKMflmLf8gPE63e8+wDxFMIr98axago=; b=jYI89NzPXXOmaOQzBw/8r4HsVB/Ew5A8euTFTcsYvyyixm4R6N+sgEuemUf6C+iZh9 5dgz3KIgrFvrWy/HEN9Irvho6A1Cwcw/hkG2eiePT1ghHYgx7SEYkZsWDnkI2BssbJoW LCjJSrg2i+yXbjT0q8tvpjjtTherWGlLzwsuTry8QbqVdzUMI576xy8XL5wbIVYXckyh 6WYOIw/x9kutMV+eEbLeFsNg0yBnHuXqGKt1+jrJRo+ddZX6iFyx30yzxZQyWAisa8D3 OjEtT6AUtUC4jvT8kE/qHts64YOU9lfn5HCDpvlSd5Pn15HZdXHA0aHsh4ePxQMGxTKN BwrQ== 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=1VZpHTdzpL/PlKMflmLf8gPE63e8+wDxFMIr98axago=; b=c2xPPlex9ggOkM3DAUoNK8GfvpHh1tpq7o9UgPZQpByCvTZ0eH3cY9eMpLie5XTjvv OEde6ykNqczLo8Be/P3fwQbkwIcd4uOucTL1c3jPI6ZtETMy0F3YCVo4ux8s2NJtyVyJ GESIV+mshd7V2TX3gxJ5yEQMdQgW2jDb5kuOmv7GiicoBOfb8n8CN2FUcrAhlNFi+bLv PBDjdV8XqWCR73PFdF8o20cBtwO1JoCSC8ejMSww9uNcj2d6k9oYRNE4m8paq56vluiO d0yC5i/C5JZMuKWngmVdfXxH6/OViqv8gmwm7RIIQYeggwfclMdFVt2sWuzmw9MO5X8S 6wWA== X-Gm-Message-State: AOAM533rJHnT8DsqiNJILeTqLjVbynJJvN4Hjlrq7otFzGy6Ng8G6Wc1 BqFlRHTJ4E31LMQtCXtNDe29HuB0I0OWVQ== X-Google-Smtp-Source: ABdhPJwdWbz5RcOZXLhc6sCBH35BveBGPrUbfXGVpjw830KZZXZuqN9lBGhCklh0myc/SL4HHznAsA== X-Received: by 2002:aca:ecca:: with SMTP id k193mr273723oih.96.1604029322787; Thu, 29 Oct 2020 20:42:02 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.42.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:42:02 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 19/20] merge-ort: add implementation of record_unmerged_index_entries() Date: Thu, 29 Oct 2020 20:41:30 -0700 Message-Id: <20201030034131.1479968-20-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 4da671d647..0b091c86eb 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" @@ -714,10 +715,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 Fri Oct 30 03:41: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: 11868391 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 AA56DC4741F for ; Fri, 30 Oct 2020 03:42:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 45BFA21582 for ; Fri, 30 Oct 2020 03:42:52 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="CDt0aDTa" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726340AbgJ3Dmv (ORCPT ); Thu, 29 Oct 2020 23:42:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47354 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726250AbgJ3Dmg (ORCPT ); Thu, 29 Oct 2020 23:42:36 -0400 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 922DCC0613E5 for ; Thu, 29 Oct 2020 20:42:04 -0700 (PDT) Received: by mail-ot1-x344.google.com with SMTP id j21so4417755ota.13 for ; Thu, 29 Oct 2020 20:42:04 -0700 (PDT) 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=sVz3L0N1RYV+ebIGzq6lJCdFUN9PJKLCVgG1iuddNDw=; b=CDt0aDTaaA9MDSQCc+F+CBVrXviBvYZJ1KzbIGRO5B94fzxBseg+R6V3wz5ah/UGi6 /LeJeTvUthRJKscDz8NQsUfypNZ1q52l3hhXa5UIbzojmNHoA8ObgEO/V6TIpastkBMJ ueqh3S70Vo9LK5nXUK8XjqOf+ajYFS4XwqcEoOSgeA+uz1XhBKnAkuJyM86z4IoY+Qq5 7eEIpMjW5JZ9laW9whjpIqlMyjbGDOa2vkk9C7N7s4nn0AeveahrJZt78IhWcJDR0CFB FkYEikuizUu73Q2Jo9T8c2hwYYGPTmXCbp+ObX7I1eCLZR9ObPxSb/+GtPZIPH+/8qRE hfoA== 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=sVz3L0N1RYV+ebIGzq6lJCdFUN9PJKLCVgG1iuddNDw=; b=LLsdCTpBnsERKIyU0/kHOSQQ5QukfKz8BBvCuCRwNkus/5eQFXOCk+59q2ON8yraOW 3nXW+H/sPwUl1psSJTFw64FIVt+aLrpUvmD4atm83hmJYQxhU970EAMupHqssXvQ2zzZ 47u4mE3Hin0CfHvL/WM4tLj3USxlE87kocDCPs63LGeuaQghDQ4/i+f0FXGrhWB/RO/6 fS0MyjCpoxxQjez6sE8IeQYQFlK53XzGOt+BBDb0DHyLINtucQRMY93jZTNewWHkRHan +L9CuDASc7asatLxbZB5grCEoqUMF5VsJBP6X114+H5o/y2M2yk8GbvZvIaijvY0ZKpp MHdA== X-Gm-Message-State: AOAM531oKdTKOiUti3BphRrzW5zuxY7KC3ARkiWC9EPK8O3E1usU8kw8 dUSkwVW9aPHc4/qz8Gccbozz10K0jUMgYw== X-Google-Smtp-Source: ABdhPJyWTMM7P3piDCIu1RxNxyxLoy4YvqF2Y4qO81etzuoKIsGc+DReFZPG9YLjQfr4K45DtqLCUA== X-Received: by 2002:a9d:7586:: with SMTP id s6mr211195otk.46.1604029323811; Thu, 29 Oct 2020 20:42:03 -0700 (PDT) Received: from tiger.attlocal.net ([2602:30a:2c28:20f0:7c1a:85e3:2ea9:5d7e]) by smtp.gmail.com with ESMTPSA id x13sm1047063otg.66.2020.10.29.20.42.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Oct 2020 20:42:03 -0700 (PDT) From: Elijah Newren To: git@vger.kernel.org Cc: Elijah Newren Subject: [PATCH 20/20] merge-ort: free data structures in merge_finalize() Date: Thu, 29 Oct 2020 20:41:31 -0700 Message-Id: <20201030034131.1479968-21-newren@gmail.com> X-Mailer: git-send-email 2.29.1.56.ga287c268e6.dirty In-Reply-To: <20201030034131.1479968-1-newren@gmail.com> References: <20201030034131.1479968-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 | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) diff --git a/merge-ort.c b/merge-ort.c index 0b091c86eb..9cd1845c37 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -840,7 +840,29 @@ 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, which we do by just setting strdup_string = 1 + * before the strmaps are cleared. + */ + opti->paths.strdup_strings = 1; + 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 set strdup_strings and 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)