From patchwork Mon Mar 6 14:06:31 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161125 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A148BC6FA99 for ; Mon, 6 Mar 2023 14:07:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230420AbjCFOH0 (ORCPT ); Mon, 6 Mar 2023 09:07:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36266 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230443AbjCFOHM (ORCPT ); Mon, 6 Mar 2023 09:07:12 -0500 Received: from mail-wm1-x331.google.com (mail-wm1-x331.google.com [IPv6:2a00:1450:4864:20::331]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E1898303E4 for ; Mon, 6 Mar 2023 06:06:46 -0800 (PST) Received: by mail-wm1-x331.google.com with SMTP id k37so5762896wms.0 for ; Mon, 06 Mar 2023 06:06:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111600; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=4RqBvXxA7E+8niXoEzgIhpGjPfHyTngb6xSDCARLi3Q=; b=eil7+h0GsBZSwlQgvsI1NMUFOgaWy+rh46nyAiNqAPxirkpTcjwhQ5MhbwKtIzfUlB bRi7cpWIBjqjDEVNveMjfXUFH7tOOMAIEg3BMk9JXNaeE5D+bScLXiuDCaUiNpzsPcyc dt41R7Zj70ZmzYubXCW67d35baLjmdMPJkDsYfQP/QZTe6NgCtEBjanJnem0GNz46r7A teo6mMpQAC7fxxUZOOIe4hZ3PTdfFHYPPLC2uakmAa7lIQbjvFN8C+pgvwfxTHVhWkIJ oVgTwaj5RKTU18+mOZtajELjrakCW+u3t3I8/S6sN6rz06hDA9XoRoXrWjWqkUT00btx 56Vw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111600; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=4RqBvXxA7E+8niXoEzgIhpGjPfHyTngb6xSDCARLi3Q=; b=or8b4MvZSEeH+8J8YifxsEkSPkUunnPi9bQiiF1fYkHtYymqcLs00fNJxE3nk0ivlR 1gCOIf836ZuAXo/FYr9VJGh8SvrMzJ5lIJKFZsjm3QJRkDEq0hWjUphiPSTT1DQw/pPC Yzhe9FX0mh823HTz4LtIMipYWlvFMncfNHkkTRRBfE1pqn7nopHSBehfWK6RF7stMVpU nf88hZOJVSzEZBa6PgVRHCxLmlfQSevMhUYAEwuOyDSQYfTOekv6vxKSDJRdwRb63XCJ Evyjthvx9tS3UsnvF5R8vfkOX4V3p4saZhKDatbzzyf0H7AgQMU0Asq0kvjz9GLpIDTh XKMQ== X-Gm-Message-State: AO0yUKVC2fC5yTcpLoth4v4WsnSaOHoyJe7L3q9GfGKSp5LiT6Yodf5G x1LEDwRr8PJ+LVbUuG3o6uVgMbP5SAM= X-Google-Smtp-Source: AK7set+jAEzPptJjl9JHSWIwTgBHrn/3m9zU21cSlgfR/93Ej/p6CQhvLk5jej0uzxVt2YX1fugT7w== X-Received: by 2002:a05:600c:3548:b0:3dc:5390:6499 with SMTP id i8-20020a05600c354800b003dc53906499mr9701462wmq.1.1678111600461; Mon, 06 Mar 2023 06:06:40 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id e41-20020a05600c4ba900b003e1f2e43a1csm9960205wmp.48.2023.03.06.06.06.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:40 -0800 (PST) Message-Id: <0fd18b6d740f1e8a6f62a25947bc3ad49c2674a6.1678111599.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:31 +0000 Subject: [PATCH 1/8] ahead-behind: create empty builtin Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The 'git ahead-behind' builtin _will_ allow users to specify multiple tip revisions relative to a common base and _will_ report the number of commits on each side of the symmetric difference between each tip and the base. However, that algorithm is not implemented yet and instead this change introduces the builtin and the basic boilerplate for a new builtin. This builtin could be replaced with multiple invocations of 'git rev-list --count ..' (for ahead values) and 'git rev-list --count ..' (for behind values). However, it is important to be able to batch these calls into a single process. For example, we will be able to track all local branches relative to an upstream branch using an invocation such as git for-each-ref --format=%(refname) refs/heads/* | git ahead-behind --base=origin/main --stdin This would report each local branch and how far ahead or behind it is relative to the remote branch 'origin/main'. This could be used to signal some branches are very old and need to be updated via 'git rebase' or deleted. We will see in future changes how such commit counting can be done efficiently within a single process (and a single commit walk) instead of multiple processes. For now, only 'git ahead-behind -h' works, and the builtin reports failure and shows the usage if the '--base' option is skipped. The documentation is light. These will be updated in the coming changes. Signed-off-by: Derrick Stolee --- .gitignore | 1 + Documentation/git-ahead-behind.txt | 62 ++++++++++++++++++++++++++++++ Makefile | 1 + builtin.h | 1 + builtin/ahead-behind.c | 30 +++++++++++++++ git.c | 1 + t/t4218-ahead-behind.sh | 17 ++++++++ 7 files changed, 113 insertions(+) create mode 100644 Documentation/git-ahead-behind.txt create mode 100644 builtin/ahead-behind.c create mode 100755 t/t4218-ahead-behind.sh diff --git a/.gitignore b/.gitignore index e875c590545..cc064a4817a 100644 --- a/.gitignore +++ b/.gitignore @@ -14,6 +14,7 @@ /bin-wrappers/ /git /git-add +/git-ahead-behind /git-am /git-annotate /git-apply diff --git a/Documentation/git-ahead-behind.txt b/Documentation/git-ahead-behind.txt new file mode 100644 index 00000000000..0e2f989a1a0 --- /dev/null +++ b/Documentation/git-ahead-behind.txt @@ -0,0 +1,62 @@ +git-ahead-behind(1) +=================== + +NAME +---- +git-ahead-behind - Count the commits on each side of a revision range + +SYNOPSIS +-------- +[verse] +'git ahead-behind' --base= [ --stdin | ] + +DESCRIPTION +----------- + +Given a list of commit ranges, report the number of commits reachable from +each of the sides of the range, but not the other. Consider a commit range +specified as `...`, allowing for the following definitions: + +* The `` is *ahead* of `` by the number of commits reachable + from `` but not reachable from ``. This is the same as the + number of the commits in the range `..`. + +* The `` is *behind* `` by the number of commits reachable from + `` but not reachble from ``. This is the same as the number + of commits in the range `..`. + +The sum of the ahead and behind counts equals the number of commits in the +symmetric difference, the range `...`. + +Multiple revisions may be specified, and they are all compared against a +common base revision, as specified by the `--base` option. The values are +reported to stdout one line at a time as follows: + +--- + +--- + +There will be exactly one line per input revision, but the lines may be +in an arbitrary order. + + +OPTIONS +------- +--base=:: + Specify that `` should be used as a common base for all + provided revisions that are not specified in the form of a range. + +--stdin:: + Read revision tips and ranges from stdin instead of from the + command-line. + + +SEE ALSO +-------- +linkgit:git-branch[1] +linkgit:git-rev-list[1] +linkgit:git-tag[1] + +GIT +--- +Part of the linkgit:git[1] suite diff --git a/Makefile b/Makefile index 50ee51fde32..691f84e8d4e 100644 --- a/Makefile +++ b/Makefile @@ -1199,6 +1199,7 @@ LIB_OBJS += xdiff-interface.o LIB_OBJS += zlib.o BUILTIN_OBJS += builtin/add.o +BUILTIN_OBJS += builtin/ahead-behind.o BUILTIN_OBJS += builtin/am.o BUILTIN_OBJS += builtin/annotate.o BUILTIN_OBJS += builtin/apply.o diff --git a/builtin.h b/builtin.h index 46cc7897898..1ae168fa3e3 100644 --- a/builtin.h +++ b/builtin.h @@ -108,6 +108,7 @@ void setup_auto_pager(const char *cmd, int def); int is_builtin(const char *s); int cmd_add(int argc, const char **argv, const char *prefix); +int cmd_ahead_behind(int argc, const char **argv, const char *prefix); int cmd_am(int argc, const char **argv, const char *prefix); int cmd_annotate(int argc, const char **argv, const char *prefix); int cmd_apply(int argc, const char **argv, const char *prefix); diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c new file mode 100644 index 00000000000..a56cc565def --- /dev/null +++ b/builtin/ahead-behind.c @@ -0,0 +1,30 @@ +#include "builtin.h" +#include "parse-options.h" +#include "config.h" + +static const char * const ahead_behind_usage[] = { + N_("git ahead-behind --base= [ --stdin | ]"), + NULL +}; + +int cmd_ahead_behind(int argc, const char **argv, const char *prefix) +{ + const char *base_ref = NULL; + int from_stdin = 0; + + struct option ahead_behind_opts[] = { + OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")), + OPT_BOOL(0 , "stdin", &from_stdin, N_("read rev names from stdin")), + OPT_END() + }; + + argc = parse_options(argc, argv, NULL, ahead_behind_opts, + ahead_behind_usage, PARSE_OPT_KEEP_UNKNOWN_OPT); + + if (!base_ref) + usage_with_options(ahead_behind_usage, ahead_behind_opts); + + git_config(git_default_config, NULL); + + return 0; +} diff --git a/git.c b/git.c index 6171fd6769d..64e3d493561 100644 --- a/git.c +++ b/git.c @@ -467,6 +467,7 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv) static struct cmd_struct commands[] = { { "add", cmd_add, RUN_SETUP | NEED_WORK_TREE }, + { "ahead-behind", cmd_ahead_behind, RUN_SETUP }, { "am", cmd_am, RUN_SETUP | NEED_WORK_TREE }, { "annotate", cmd_annotate, RUN_SETUP }, { "apply", cmd_apply, RUN_SETUP_GENTLY }, diff --git a/t/t4218-ahead-behind.sh b/t/t4218-ahead-behind.sh new file mode 100755 index 00000000000..bc08f1207a0 --- /dev/null +++ b/t/t4218-ahead-behind.sh @@ -0,0 +1,17 @@ +#!/bin/sh + +test_description='git ahead-behind command-line options' + +. ./test-lib.sh + +test_expect_success 'git ahead-behind -h' ' + test_must_fail git ahead-behind -h >out && + grep "usage:" out +' + +test_expect_success 'git ahead-behind without --base' ' + test_must_fail git ahead-behind HEAD 2>err && + grep "usage:" err +' + +test_done From patchwork Mon Mar 6 14:06:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161126 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A07B2C6FD1D for ; Mon, 6 Mar 2023 14:07:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229760AbjCFOH3 (ORCPT ); Mon, 6 Mar 2023 09:07:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35972 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230212AbjCFOHM (ORCPT ); Mon, 6 Mar 2023 09:07:12 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1705C25BB0 for ; Mon, 6 Mar 2023 06:06:48 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id k37so5762921wms.0 for ; Mon, 06 Mar 2023 06:06:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111601; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=Xzhk9czL0tfPZE5t5QjBWnqeCGPryB1dJT4/B524tO8=; b=aJtyaTrRLgEN+sP7xVieUGh5sUKDCkK7oEpYA30889cdIYS+BZiC2y5kIJ16+wEPUu J+ee8uwgad4AlgRq65OdBnnc/OppYyumyV7yfwxIu6Cnx3EXuvYBYw0bKWlN9QIDsH5H ULQ+jfEO1oDmEUOTmuT4TeVIZ2BgbSTtvBgUS2Ku5+9ox8wInf9xJ9LmzJEl+Qi0+bkr hvr31GGwwtJeKUv0kDFFQRSKlAwxmSAX91jlGNF+o/quyGsuDi8y60InxTEYJMGXi9Cx tOWt4rqslcjwnG3LNQeB2nAOeG44Zk/SwZ0lx/04UGzwPBd1fwYrphJkVOa2ttTyPik/ EYoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111601; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Xzhk9czL0tfPZE5t5QjBWnqeCGPryB1dJT4/B524tO8=; b=I2Mx4kgoNfozFgqOPUJhUEbqnWda22xZ4auqr+FRAJylZDIuE1Ur3wm8AAPYCvbEUz BtWaUMFGcA/puw07tXvWv/vdCURfZf3t8WwwHBOcZzCz1qJK/eXwyzHs6uFaPcpGV6V9 apnUQyEN9ysfJ7oeQClkucMk2hOvgOG8SH/qfreBW6waRadyjImQAGJWfPmNmS4Jvrj1 yd3MEukEFRST0nIHdhhKVLZdi7TjtyC8hM8TAsAQiW99aUiL9sQVnbHY6lzmTT8quQwC mMk6sABf1f/LrG31OecotVn7rNWPVUCDRrxlKhcgrGMyWjv3Zq0LXAI03CFFfPMqNxri XV/w== X-Gm-Message-State: AO0yUKV6r8AKcCvpGwsgqlyJGUOZBKvIc5kYuw01AWa9Y530Os9gnWfb UlTqFeDLofOt1zXlF58ex0Jq0Fgggqk= X-Google-Smtp-Source: AK7set+Y0zGxXU+ph75o992IpJKB8mcV0tjAvVv0hsw3UFvnCLvQBEwwkgC570ytMPHXCd+c7wkTLw== X-Received: by 2002:a05:600c:1f0a:b0:3ea:9530:22a6 with SMTP id bd10-20020a05600c1f0a00b003ea953022a6mr10221010wmb.1.1678111601202; Mon, 06 Mar 2023 06:06:41 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o10-20020a05600c164a00b003e20cf0408esm10040567wmn.40.2023.03.06.06.06.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:41 -0800 (PST) Message-Id: <08fc0710017d4b6178a8c5772e0f15fc69c84ad6.1678111599.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:32 +0000 Subject: [PATCH 2/8] ahead-behind: parse tip references Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Before implementing the logic to compute the ahead/behind counts, parse the unknown options as commits and place them in a string_list. Be sure to error out when the reference is not found. Co-authored-by: Taylor Blau Signed-off-by: Taylor Blau Signed-off-by: Derrick Stolee --- builtin/ahead-behind.c | 39 +++++++++++++++++++++++++++++++++++++++ t/t4218-ahead-behind.sh | 10 ++++++++++ 2 files changed, 49 insertions(+) diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c index a56cc565def..c1212cc8d46 100644 --- a/builtin/ahead-behind.c +++ b/builtin/ahead-behind.c @@ -1,16 +1,31 @@ #include "builtin.h" #include "parse-options.h" #include "config.h" +#include "commit.h" static const char * const ahead_behind_usage[] = { N_("git ahead-behind --base= [ --stdin | ]"), NULL }; +static int handle_arg(struct string_list *tips, const char *arg) +{ + struct string_list_item *item; + struct commit *c = lookup_commit_reference_by_name(arg); + + if (!c) + return error(_("could not resolve '%s'"), arg); + + item = string_list_append(tips, arg); + item->util = c; + return 0; +} + int cmd_ahead_behind(int argc, const char **argv, const char *prefix) { const char *base_ref = NULL; int from_stdin = 0; + struct string_list tips = STRING_LIST_INIT_DUP; struct option ahead_behind_opts[] = { OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")), @@ -26,5 +41,29 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) git_config(git_default_config, NULL); + if (from_stdin) { + struct strbuf line = STRBUF_INIT; + + while (strbuf_getline(&line, stdin) != EOF) { + if (!line.len) + break; + + if (handle_arg(&tips, line.buf)) + return 1; + } + + strbuf_release(&line); + } else { + int i; + for (i = 0; i < argc; ++i) { + if (handle_arg(&tips, argv[i])) + return 1; + } + } + + /* Early return for no tips. */ + if (!tips.nr) + return 0; + return 0; } diff --git a/t/t4218-ahead-behind.sh b/t/t4218-ahead-behind.sh index bc08f1207a0..3b8b9dc9887 100755 --- a/t/t4218-ahead-behind.sh +++ b/t/t4218-ahead-behind.sh @@ -14,4 +14,14 @@ test_expect_success 'git ahead-behind without --base' ' grep "usage:" err ' +test_expect_success 'git ahead-behind with broken tip' ' + test_must_fail git ahead-behind --base=HEAD bogus 2>err && + grep "could not resolve '\''bogus'\''" err +' + +test_expect_success 'git ahead-behind without tips' ' + git ahead-behind --base=HEAD 2>err && + test_must_be_empty err +' + test_done From patchwork Mon Mar 6 14:06:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161128 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 70EB6C6FD1D for ; Mon, 6 Mar 2023 14:07:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230500AbjCFOHe (ORCPT ); Mon, 6 Mar 2023 09:07:34 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35978 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230301AbjCFOHQ (ORCPT ); Mon, 6 Mar 2023 09:07:16 -0500 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3FE6B25B8F for ; Mon, 6 Mar 2023 06:06:49 -0800 (PST) Received: by mail-wr1-x429.google.com with SMTP id g3so8936569wri.6 for ; Mon, 06 Mar 2023 06:06:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111602; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=vD91cJyXrD/zI1PRGWlL6b8RPw6pZbakKRIOAQ2YxEc=; b=OoGJSCX2lK56+9ARPfStcYImz+XPcmsAZ6Wjc0rjrw1oLa4jlHLFAzIKVI70+vJ6hP 80HISJQQ+dF9rdXXh2EAXv7+wr1RqwcR4FyRrUEqigcUyYRZnkJj01+DIViJkKBbrpEI a50qmzygVtYir0O1PUKnctMrl3hHNsB15MmSUNlF0RA+aeA1QAnUIGD8JmbOwX2J7Qv0 YcMDxtTbZuG5GTk2+mHPyAO5Lyoq2Un7sAcUrr3YmBzrRcHW7K0LrUnnm14OHfBglkGA /mnHfwi8a4VHfMGpdWB5hcANcO1Tg+C4ZCGiqO0kJtrv+RkN1QtUPwsT60nVxutonuwo WQ2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111602; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vD91cJyXrD/zI1PRGWlL6b8RPw6pZbakKRIOAQ2YxEc=; b=0sfiqQJrNFjuBJfGNIldYB5L9qqbgG1Il5kDge0AYs1FgzyvtK9NvAL+IoWxx+pj6M FmGN9AW0/oBIzmc+HW8CgH1KlOU49jsFuRh6eBn8vDAnzUxIJpW+x+U7atlelQzzSLub KhRnWuoRzoX/JCWuLS4q9F5o3VKO72Ewb5BWjKhtegsLLRGFahJ15FzHasEDenht2JRc qdUCSetSTgluas2YzjqrK7iUp3i/wF72pV/yR0gNnDfzuuf8DS+nNHGUMYWlE9SmlYm7 158PjY46bNTBw6Dm9N6RegKTl6/fN2PQI4IGwPlbRMw3Ey6sJXbtnpFelDoIQdeE3yre PkpQ== X-Gm-Message-State: AO0yUKUF909V5YeMaKRcScLK6alyvPHGP6oVg9b5rE36pj0oCXhXLPaB yb4EW6jm36PXJo7x/TMmh6NSmNFXVi4= X-Google-Smtp-Source: AK7set81BSlXt8Auc5/tdIIs0L0cobl9iQkX/FCfSR9Xqfdv1OC/+T9j3JcrS9yC2q7K8sqgJ86hIQ== X-Received: by 2002:adf:e6cc:0:b0:2ca:de61:b234 with SMTP id y12-20020adfe6cc000000b002cade61b234mr5158314wrm.51.1678111601700; Mon, 06 Mar 2023 06:06:41 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l8-20020a05600c4f0800b003b47b80cec3sm15914585wmq.42.2023.03.06.06.06.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:41 -0800 (PST) Message-Id: In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:33 +0000 Subject: [PATCH 3/8] ahead-behind: implement --ignore-missing option Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee When parsing the tip revisions from the ahead-behind inputs, it is important to check that those tips exist before adding them to the list for computation. The previous change caused the builtin to return with errors if the revisions could not be resolved. However, when running 'git ahead-behind' in an environment with concurrent edits, such as a Git server, then the references could be deleted from underneath the caller between reading the reference list and starting the 'git ahead-behind' process. Avoid this race by allowing the caller to specify '--ignore-missing' and continue using the information that is still available. Co-authored-by: Taylor Blau Signed-off-by: Taylor Blau Signed-off-by: Derrick Stolee --- Documentation/git-ahead-behind.txt | 6 ++++++ builtin/ahead-behind.c | 8 +++++++- t/t4218-ahead-behind.sh | 6 ++++++ 3 files changed, 19 insertions(+), 1 deletion(-) diff --git a/Documentation/git-ahead-behind.txt b/Documentation/git-ahead-behind.txt index 0e2f989a1a0..2dd5147f6b2 100644 --- a/Documentation/git-ahead-behind.txt +++ b/Documentation/git-ahead-behind.txt @@ -50,6 +50,12 @@ OPTIONS Read revision tips and ranges from stdin instead of from the command-line. +--ignore-missing:: + When parsing tip references, ignore any references that are not + found. This is useful when operating in an environment where a + reference could be deleted between reading the reference and + starting the `git ahead-behind` process. + SEE ALSO -------- diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c index c1212cc8d46..e4f65fc0548 100644 --- a/builtin/ahead-behind.c +++ b/builtin/ahead-behind.c @@ -8,13 +8,18 @@ static const char * const ahead_behind_usage[] = { NULL }; +static int ignore_missing; + static int handle_arg(struct string_list *tips, const char *arg) { struct string_list_item *item; struct commit *c = lookup_commit_reference_by_name(arg); - if (!c) + if (!c) { + if (ignore_missing) + return 0; return error(_("could not resolve '%s'"), arg); + } item = string_list_append(tips, arg); item->util = c; @@ -30,6 +35,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) struct option ahead_behind_opts[] = { OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")), OPT_BOOL(0 , "stdin", &from_stdin, N_("read rev names from stdin")), + OPT_BOOL(0 , "ignore-missing", &ignore_missing, N_("ignore missing tip references")), OPT_END() }; diff --git a/t/t4218-ahead-behind.sh b/t/t4218-ahead-behind.sh index 3b8b9dc9887..56f16515896 100755 --- a/t/t4218-ahead-behind.sh +++ b/t/t4218-ahead-behind.sh @@ -19,6 +19,12 @@ test_expect_success 'git ahead-behind with broken tip' ' grep "could not resolve '\''bogus'\''" err ' +test_expect_success 'git ahead-behind with broken tip and --ignore-missing' ' + git ahead-behind --base=HEAD --ignore-missing bogus 2>err >out && + test_must_be_empty err && + test_must_be_empty out +' + test_expect_success 'git ahead-behind without tips' ' git ahead-behind --base=HEAD 2>err && test_must_be_empty err From patchwork Mon Mar 6 14:06:34 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161129 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A6E37C6FA99 for ; Mon, 6 Mar 2023 14:07:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231126AbjCFOHh (ORCPT ); Mon, 6 Mar 2023 09:07:37 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36434 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230334AbjCFOHR (ORCPT ); Mon, 6 Mar 2023 09:07:17 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BB36020692 for ; Mon, 6 Mar 2023 06:06:50 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id t25-20020a1c7719000000b003eb052cc5ccso8255233wmi.4 for ; Mon, 06 Mar 2023 06:06:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111602; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=fV0fO6kStkffZHpmPplRcpbqu+IzTW2g86XUKU3MSkw=; b=nGiGIL1rUEUx6z34OlXw/poBM8ImO6pAwAXBM69z6aTm71CS5DrqY9RFGoIYBHBvbm eFrSqKmjr6xNB6xhcQ8Ae+VCjw1DVBQ1leFcalCBUb1Yeh8hG5d6r+8eNe6tApXv3/0Y LDzsIIP9XwOF5950W1zZGfO+x34lSWNp2DTZAKR5V1GjSlrGTxU+F+tbhCV2wtIG371T 5pPwH/ZF1fQCasuWO/t9lpvWrEyY6dPQ+QxaRWGVDRXZF5oAHygljlJqtujAg2sek1rT DihMa6bU7foPNKLbiWfUKE/XBhk4ibpfRAiEKzjhSWYxRCL0tqDZp9cDvLBN3Sw730Sn 3+Eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111602; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fV0fO6kStkffZHpmPplRcpbqu+IzTW2g86XUKU3MSkw=; b=jecx8QrKKuBpMnU8A7GMd+NI7thvCxSw9ZBMLlIj7h63tANNTziDm2KhdDlYW1gglH 87THXO2EYlZeJUQ/AAKd4wcqIJmB5M+vcOsezAQvJ9LWtAmT0iVSO5qm37l/TmqAdkbc FTD9QKpSLmkeoVwM//HKWAsc+x151D5sqKpzzT5m7QdpfA7VUbqXqBApJ061p4Nz0evl PuJmE05wGhY73Zl+RjEUnsgObSmbmeVMmLqZJWJMEs9DZUumbMDyyzfMbG/kxSymt43Z wGZe6fbU48RyxZR9hVchjRpQAHByHMCYDxyQNANO8IgIkcAImUZnASy9lud/9H2ORYBW y6OA== X-Gm-Message-State: AO0yUKW7b/2jCL6YCG09yeoCfz4f2R7p+W+hEgIVnduDoo32O3Efpyqg 1xWQMlol3amrRHuuLI9wa9blYLmY4+0= X-Google-Smtp-Source: AK7set89cE+ANu5p+od9EG3BsNN3CttySxjg3zQCr4CtbfQq7p21MMxLjY6j9VZQ7eUpkMJNhUIr9w== X-Received: by 2002:a05:600c:350f:b0:3ea:d620:57a7 with SMTP id h15-20020a05600c350f00b003ead62057a7mr9288367wmq.8.1678111602482; Mon, 06 Mar 2023 06:06:42 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id r1-20020a056000014100b002c5534db60bsm10232139wrx.71.2023.03.06.06.06.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:42 -0800 (PST) Message-Id: <853891c0b14b2a97c980a436a755f9005415ea7a.1678111599.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:34 +0000 Subject: [PATCH 4/8] commit-graph: combine generation computations Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee This patch extracts the common code used to compute topological levels and corrected committer dates into a common routine, compute_reachable_generation_numbers_1(). This new routine dispatches to call the necessary functions to get and set the generation number for a given commit through a vtable (the compute_generation_info struct). Computing the generation number itself is done in compute_generation_from_max(), which dispatches its implementation based on the generation version requested, or issuing a BUG() for unrecognized generation versions. This patch cleans up the two places that currently compute topological levels and corrected commit dates by reducing the amount of duplicated code. It also makes it possible to introduce a function which dynamically computes those values for commits that aren't stored in a commit-graph, which will be required for the forthcoming ahead-behind rewrite. Signed-off-by: Taylor Blau Signed-off-by: Derrick Stolee --- commit-graph.c | 171 +++++++++++++++++++++++++++++++------------------ 1 file changed, 107 insertions(+), 64 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index c11b59f28b3..deccf984a0d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1446,24 +1446,53 @@ static void close_reachable(struct write_commit_graph_context *ctx) stop_progress(&ctx->progress); } -static void compute_topological_levels(struct write_commit_graph_context *ctx) +struct compute_generation_info { + struct repository *r; + struct packed_commit_list *commits; + struct progress *progress; + int progress_cnt; + + timestamp_t (*get_generation)(struct commit *c, void *data); + void (*set_generation)(struct commit *c, timestamp_t gen, void *data); + void *data; +}; + +static timestamp_t compute_generation_from_max(struct commit *c, + timestamp_t max_gen, + int generation_version) +{ + switch (generation_version) { + case 1: /* topological levels */ + if (max_gen > GENERATION_NUMBER_V1_MAX - 1) + max_gen = GENERATION_NUMBER_V1_MAX - 1; + return max_gen + 1; + + case 2: /* corrected commit date */ + if (c->date && c->date > max_gen) + max_gen = c->date - 1; + return max_gen + 1; + + default: + BUG("attempting unimplemented version"); + } +} + +static void compute_reachable_generation_numbers_1( + struct compute_generation_info *info, + int generation_version) { int i; struct commit_list *list = NULL; - if (ctx->report_progress) - ctx->progress = start_delayed_progress( - _("Computing commit graph topological levels"), - ctx->commits.nr); - for (i = 0; i < ctx->commits.nr; i++) { - struct commit *c = ctx->commits.list[i]; - uint32_t level; + for (i = 0; i < info->commits->nr; i++) { + struct commit *c = info->commits->list[i]; + timestamp_t gen; + repo_parse_commit(info->r, c); + gen = info->get_generation(c, info->data); - repo_parse_commit(ctx->r, c); - level = *topo_level_slab_at(ctx->topo_levels, c); + display_progress(info->progress, info->progress_cnt + 1); - display_progress(ctx->progress, i + 1); - if (level != GENERATION_NUMBER_ZERO) + if (gen != GENERATION_NUMBER_ZERO && gen != GENERATION_NUMBER_INFINITY) continue; commit_list_insert(c, &list); @@ -1471,38 +1500,91 @@ static void compute_topological_levels(struct write_commit_graph_context *ctx) struct commit *current = list->item; struct commit_list *parent; int all_parents_computed = 1; - uint32_t max_level = 0; + uint32_t max_gen = 0; for (parent = current->parents; parent; parent = parent->next) { - repo_parse_commit(ctx->r, parent->item); - level = *topo_level_slab_at(ctx->topo_levels, parent->item); + repo_parse_commit(info->r, parent->item); + gen = info->get_generation(parent->item, info->data); - if (level == GENERATION_NUMBER_ZERO) { + if (gen == GENERATION_NUMBER_ZERO) { all_parents_computed = 0; commit_list_insert(parent->item, &list); break; } - if (level > max_level) - max_level = level; + if (gen > max_gen) + max_gen = gen; } if (all_parents_computed) { pop_commit(&list); - - if (max_level > GENERATION_NUMBER_V1_MAX - 1) - max_level = GENERATION_NUMBER_V1_MAX - 1; - *topo_level_slab_at(ctx->topo_levels, current) = max_level + 1; + gen = compute_generation_from_max( + current, max_gen, + generation_version); + info->set_generation(current, gen, info->data); } } } +} + +static timestamp_t get_topo_level(struct commit *c, void *data) +{ + struct write_commit_graph_context *ctx = data; + return *topo_level_slab_at(ctx->topo_levels, c); +} + +static void set_topo_level(struct commit *c, timestamp_t t, void *data) +{ + struct write_commit_graph_context *ctx = data; + *topo_level_slab_at(ctx->topo_levels, c) = (uint32_t)t; + display_progress(ctx->progress, ctx->progress_cnt + 1); +} + +static void compute_topological_levels(struct write_commit_graph_context *ctx) +{ + struct compute_generation_info info = { + .r = ctx->r, + .progress = ctx->progress, + .commits = &ctx->commits, + .get_generation = get_topo_level, + .set_generation = set_topo_level, + .data = ctx, + }; + + if (ctx->report_progress) + ctx->progress = start_delayed_progress( + _("Computing commit graph topological levels"), + ctx->commits.nr); + + compute_reachable_generation_numbers_1(&info, 1); + stop_progress(&ctx->progress); } +static timestamp_t get_generation_from_graph_data(struct commit *c, void *data) +{ + return commit_graph_data_at(c)->generation; +} + +static void set_generation_v2(struct commit *c, timestamp_t t, void *data) +{ + struct write_commit_graph_context *ctx = data; + struct commit_graph_data *g = commit_graph_data_at(c); + g->generation = (uint32_t)t; + display_progress(ctx->progress, ctx->progress_cnt + 1); +} + static void compute_generation_numbers(struct write_commit_graph_context *ctx) { int i; - struct commit_list *list = NULL; + struct compute_generation_info info = { + .r = ctx->r, + .progress = ctx->progress, + .commits = &ctx->commits, + .get_generation = get_generation_from_graph_data, + .set_generation = set_generation_v2, + .data = ctx, + }; if (ctx->report_progress) ctx->progress = start_delayed_progress( @@ -1517,47 +1599,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) } } - for (i = 0; i < ctx->commits.nr; i++) { - struct commit *c = ctx->commits.list[i]; - timestamp_t corrected_commit_date; - - repo_parse_commit(ctx->r, c); - corrected_commit_date = commit_graph_data_at(c)->generation; - - display_progress(ctx->progress, i + 1); - if (corrected_commit_date != GENERATION_NUMBER_ZERO) - continue; - - commit_list_insert(c, &list); - while (list) { - struct commit *current = list->item; - struct commit_list *parent; - int all_parents_computed = 1; - timestamp_t max_corrected_commit_date = 0; - - for (parent = current->parents; parent; parent = parent->next) { - repo_parse_commit(ctx->r, parent->item); - corrected_commit_date = commit_graph_data_at(parent->item)->generation; - - if (corrected_commit_date == GENERATION_NUMBER_ZERO) { - all_parents_computed = 0; - commit_list_insert(parent->item, &list); - break; - } - - if (corrected_commit_date > max_corrected_commit_date) - max_corrected_commit_date = corrected_commit_date; - } - - if (all_parents_computed) { - pop_commit(&list); - - if (current->date && current->date > max_corrected_commit_date) - max_corrected_commit_date = current->date - 1; - commit_graph_data_at(current)->generation = max_corrected_commit_date + 1; - } - } - } + compute_reachable_generation_numbers_1(&info, 2); for (i = 0; i < ctx->commits.nr; i++) { struct commit *c = ctx->commits.list[i]; @@ -1565,6 +1607,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) ctx->num_generation_data_overflows++; } + stop_progress(&ctx->progress); } From patchwork Mon Mar 6 14:06:35 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161130 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 28796C678D4 for ; Mon, 6 Mar 2023 14:07:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231139AbjCFOHj (ORCPT ); Mon, 6 Mar 2023 09:07:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36472 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230348AbjCFOHS (ORCPT ); Mon, 6 Mar 2023 09:07:18 -0500 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C201F25E38 for ; Mon, 6 Mar 2023 06:06:51 -0800 (PST) Received: by mail-wm1-x329.google.com with SMTP id l7-20020a05600c4f0700b003e79fa98ce1so5262169wmq.2 for ; Mon, 06 Mar 2023 06:06:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111603; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=Yp3Iyv77kMPOfk15oV0GgT+x6zh09VJd0pKm+NeiPD4=; b=MVvVJmNQJDb87lrRN+JmXxlmOanQOstEO6h0UW88VW4045jMRzF6QqkUE3RVIGCCT/ g+KvpAIk0T7DEQakeUzppRJxX1/oGZyuMoRCiLljFV7Bni2RjC8y0M6xvkCLcF0asm3w D81zJYshzYgj4TF1qCgm/GI0W+Dcgoi9GzbieSuWdsjGKWbLAiqTbfSOFhPpEHMgoYOR tgVXCYow4jT8hcKeh1cVWxQmSI1T7QZG2SUdnimvm89lpnEXzxC9VP/OgEnq95tq9Exw cupnNMXj+vc8nFhxqn/GoOYj/yx2y0sQwQI9jPM/4XGxf9aqxe9OkNg8HuSkGcqZ7CpP RNSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111603; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Yp3Iyv77kMPOfk15oV0GgT+x6zh09VJd0pKm+NeiPD4=; b=WGzpLDqf9SQ3MyiKZljhEh4SyQqVKYGo91Q3SfUQzblF6jACUNtrAGy+USREEgJ4lm QKi3bFtqebBdOF+HFAQGMcmmA/bykRKNWIwCp6due+M2JpcBBjUwbYFixh7qvNCu48TN iiOp8yP3KHy7nrowPirjegdnEM/tqQYQIwMFVtftGOkJ3bTa5fcn18ZaOqJ8QjM4GFmO bZwP5M8vxHfza5F1TEADqQVLY5tx+RHyIbcMVw9c82cAxpDQylzSLxuHjvrWCW2fTi4m ab+0m/xCyOfwhjBjtT7FC4xKCDBpNgmbc7exEWwkcXRqknHQbV4cma954APz8nOJzQuH ICMg== X-Gm-Message-State: AO0yUKXgWmxrDhqt60B8oeY5zEFC0+YfOXiVnvuy2RGwo3wBZp6ZJDam 1afQ4771EeN8LNdNKqvH0e8hcgXRhRk= X-Google-Smtp-Source: AK7set9GwSJq9f3Yqcf1rZ65p4lG/H/o/KsLKJmfzjWDQOXp6UvZvDpaAZ2+tFRM8kjsxEyGUtFBWg== X-Received: by 2002:a05:600c:3b16:b0:3eb:5990:aea4 with SMTP id m22-20020a05600c3b1600b003eb5990aea4mr10438336wms.12.1678111603114; Mon, 06 Mar 2023 06:06:43 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h22-20020a05600c351600b003daf6e3bc2fsm21075097wmq.1.2023.03.06.06.06.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:42 -0800 (PST) Message-Id: In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:35 +0000 Subject: [PATCH 5/8] commit-graph: return generation from memory Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The commit_graph_generation() method used to report a value of GENERATION_NUMBER_INFINITY if the commit_graph_data_slab had an instance for the given commit but the graph_pos indicated the commit was not in the commit-graph file. Instead, trust the 'generation' member if the commit has a value in the slab _and_ the 'generation' member is non-zero. Otherwise, treat it as GENERATION_NUMBER_INFINITY. This only makes a difference for a very old case for the commit-graph: the very first Git release to write commit-graph files wrote zeroes in the topological level positions. If we are parsing a commit-graph with all zeroes, those commits will now appear to have GENERATION_NUMBER_INFINITY (as if they were not parsed from the commit-graph). I attempted several variations to work around the need for providing an uninitialized 'generation' member, but this was the best one I found. It does require a change to a verification test in t5318 because it reports a different error than the one about non-zero generation numbers. Signed-off-by: Derrick Stolee --- commit-graph.c | 9 ++++----- t/t5318-commit-graph.sh | 2 +- 2 files changed, 5 insertions(+), 6 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index deccf984a0d..f04b02be1bb 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -111,17 +111,16 @@ uint32_t commit_graph_position(const struct commit *c) return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH; } + timestamp_t commit_graph_generation(const struct commit *c) { struct commit_graph_data *data = commit_graph_data_slab_peek(&commit_graph_data_slab, c); - if (!data) - return GENERATION_NUMBER_INFINITY; - else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH) - return GENERATION_NUMBER_INFINITY; + if (data && data->generation) + return data->generation; - return data->generation; + return GENERATION_NUMBER_INFINITY; } static struct commit_graph_data *commit_graph_data_at(const struct commit *c) diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh index 049c5fc8ead..b6e12115786 100755 --- a/t/t5318-commit-graph.sh +++ b/t/t5318-commit-graph.sh @@ -630,7 +630,7 @@ test_expect_success 'detect incorrect generation number' ' test_expect_success 'detect incorrect generation number' ' corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \ - "non-zero generation number" + "commit-graph generation for commit" ' test_expect_success 'detect incorrect commit date' ' From patchwork Mon Mar 6 14:06:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13161131 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id BC214C678D4 for ; Mon, 6 Mar 2023 14:07:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231182AbjCFOH4 (ORCPT ); Mon, 6 Mar 2023 09:07:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35678 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230390AbjCFOHS (ORCPT ); Mon, 6 Mar 2023 09:07:18 -0500 Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 72A9724CB9 for ; Mon, 6 Mar 2023 06:06:52 -0800 (PST) Received: by mail-wr1-x42c.google.com with SMTP id h11so8938942wrm.5 for ; Mon, 06 Mar 2023 06:06:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111603; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=HjZ+UNNJhOaqWykL3y2WkKBUiPW6gztml3WzTDYve8k=; b=Xm3ll84Y0jdvim3HLpr/u71KuDWzZ2+ArdRsa7Rapo2mm4t5i3p9Spv+eMtltGCzSW 47HdzN11KDSnZpDTvRR2nWNXzS09zLOUTdXm+EaRWfOWlSCBAaJXfFAXdoZJv2QlUhjB koLTo1nB/OJ3sSnPUgw7W+a8jeyFPGtGdLM4D6/ToN+hHnUNbu9hX9qRmchvBxduj8wS VZ5quFzWVjQMlOs+fVOjAnXsfvUWq3FFnLWNu2DC6Uz5ZOUSnNho4kG6bo5omFqPtI4L gk8l++2ChrqvSD3DvgKHy5eEyvaeNNXu2x7gJkRtQP1Yr8IZCSmW56UAIzn7a4ttjXB1 gMXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111603; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=HjZ+UNNJhOaqWykL3y2WkKBUiPW6gztml3WzTDYve8k=; b=z6PBbrqd89DgflJOkF8MSfDyU6Q+HYsCLHm04/tFMZeNaseCU5pVvoEVS8xhBzP2SN bRBh/ta+5GjiNRYUoU5XdwRhluukjLoPoa7Z3nVuUhtLbGfop4QBc/s97Eqh+eDyfkly GLUIdUScZW6IMmzrrKFVF7iWnhNUFSEuaU1FY9xr01dXzEJD4i2CWFPCoRVQceOzzxUG +sCxn5LupviTZ9915ERY/zLL00SD/tBDdAr3tnmLLL3Pcz5Htg1lDHAwyRsiM9S1kKL5 ui/olFURNgRTcnUdHp/2m8qR+AMYy1j2OM7Q/i+K0QeWSL9OiK+oMJLevnktGrdXjIZi Kr0Q== X-Gm-Message-State: AO0yUKUE6fT+HxuSdiD+Tz75JEHqss7dcYIFmdNWAWCaINKawYfm1A/t w3AuhdKVaVKwrx/gjbeYBBV/KHgo+kE= X-Google-Smtp-Source: AK7set+mhJbigqhKQSF1Krm4/o++h0pY3cw8GSB4P0wWaSmQOqIsjd1o/pgGxF34aUHgiJegx17ikg== X-Received: by 2002:adf:f14a:0:b0:2c9:97f8:2604 with SMTP id y10-20020adff14a000000b002c997f82604mr6563424wro.14.1678111603693; Mon, 06 Mar 2023 06:06:43 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a18-20020a05600c069200b003e6dcd562a6sm10053590wmn.28.2023.03.06.06.06.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:43 -0800 (PST) Message-Id: In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:36 +0000 Subject: [PATCH 6/8] commit-graph: introduce `ensure_generations_valid()` Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Taylor Blau From: Taylor Blau Use the just-introduced compute_reachable_generation_numbers_1() to implement a function which dynamically computes topological levels (or corrected commit dates) for out-of-graph commits. This will be useful for the ahead-behind algorithm we are about to introduce, which needs accurate topological levels on _all_ commits reachable from the tips in order to avoid over-counting. Co-authored-by: Derrick Stolee Signed-off-by: Taylor Blau Signed-off-by: Derrick Stolee --- commit-graph.c | 29 +++++++++++++++++++++++++++++ commit-graph.h | 7 +++++++ 2 files changed, 36 insertions(+) diff --git a/commit-graph.c b/commit-graph.c index f04b02be1bb..a573d1b89ff 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1610,6 +1610,35 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) stop_progress(&ctx->progress); } +static void set_generation_in_graph_data(struct commit *c, timestamp_t t, + void *data) +{ + commit_graph_data_at(c)->generation = t; +} + +/* + * After this method, all commits reachable from those in the given + * list will have non-zero, non-infinite generation numbers. + */ +void ensure_generations_valid(struct commit **commits, size_t nr) +{ + struct repository *r = the_repository; + int generation_version = get_configured_generation_version(r); + struct packed_commit_list list = { + .list = commits, + .alloc = nr, + .nr = nr, + }; + struct compute_generation_info info = { + .r = r, + .commits = &list, + .get_generation = get_generation_from_graph_data, + .set_generation = set_generation_in_graph_data, + }; + + compute_reachable_generation_numbers_1(&info, generation_version); +} + static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context *ctx) { trace2_data_intmax("commit-graph", ctx->r, "filter-computed", diff --git a/commit-graph.h b/commit-graph.h index 37faee6b66d..a529c62b518 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -190,4 +190,11 @@ struct commit_graph_data { */ timestamp_t commit_graph_generation(const struct commit *); uint32_t commit_graph_position(const struct commit *); + +/* + * After this method, all commits reachable from those in the given + * list will have non-zero, non-infinite generation numbers. + */ +void ensure_generations_valid(struct commit **commits, size_t nr); + #endif From patchwork Mon Mar 6 14:06:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161132 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id DDA31C61DA4 for ; Mon, 6 Mar 2023 14:08:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231185AbjCFOID (ORCPT ); Mon, 6 Mar 2023 09:08:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35598 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230463AbjCFOHT (ORCPT ); Mon, 6 Mar 2023 09:07:19 -0500 Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3EF112311E for ; Mon, 6 Mar 2023 06:06:53 -0800 (PST) Received: by mail-wm1-x335.google.com with SMTP id m25-20020a7bcb99000000b003e7842b75f2so5256396wmi.3 for ; Mon, 06 Mar 2023 06:06:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111604; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=fUZvW498oqoG37gd40FZPqaVzzvaAQQ1q00K/CTZo8I=; b=lWjix4YPbJsKll2ai0zEuVqt06OLjFvfZx8PlS6fgZSO6qDD5aYvyfnDcOYj8cP1Yr QhnE/V51Exyibgo3FXQHqN0N1CpfmWZkFl96x3sDnQzKg9fkzQUIaJe0cTrZNdLZG7jw /SynEAwBpXmInA/dtAl+fyqZEMyvZty4x0kqWyEZ2O2Tx5hXXwN03Fnd31f31uZukR0L a4ZdOdkA/UKUXuCqHApwlcDOryaHQQQ706UvMdlS1vloMJEJ6MdHMtXVzS7DZILxJvQV pYOq56CN6sRCqo+qxvSH+9JcbZEPskwbCrhRVJOOtFgHilKptlaZp2wFTUFrXMnvb2vy 5MvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111604; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fUZvW498oqoG37gd40FZPqaVzzvaAQQ1q00K/CTZo8I=; b=qFmO3jLOu+97owl62KsPipDUu3OPPxbpIT3ymd2SVPfS9MR2OiZaX6xHd/aP5uvflo asgUQUV2im02OVvBiheupuKvHBtCaVvm0pS9ALf8vTmS8QrVqw/u4UdOXux24CjoqVZT Tc9L1CYzl/8NniQ4L1/ThvXVsxPmZSrE7IPodjknb9wRKsyThb71zZkmV2i+2aj3BDcb CUQlhkYY60cBJpORo2jXhXi+A1hOQOJJKzjGbckrk8zd/HygCtfbxEqFbVIZ0MQQwrcr ypwMDCctn3fEFnwzOpUZt3w8zZ8KNdIaQfRn6phQJMPCPOI8PQM1slew1wsCaM9QKkyc taKQ== X-Gm-Message-State: AO0yUKUTvsVNfZkc8z5fub41NHFfVq8tH32xoczp0b2WYkdSAVOFCXIp rqxvDlv9urcqB9dAFuFJqtKD/0qUt9s= X-Google-Smtp-Source: AK7set9xLjWDXP3QgivLMHvG8M8THGpmdU7U2TP8y1sNJGZ5bRtu+4MrooeBeeEnQD6hcL9d3pqacQ== X-Received: by 2002:a05:600c:1d2a:b0:3e1:374:8b66 with SMTP id l42-20020a05600c1d2a00b003e103748b66mr9249306wms.40.1678111604369; Mon, 06 Mar 2023 06:06:44 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p16-20020a05600c359000b003e209b45f6bsm15589470wmq.29.2023.03.06.06.06.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:44 -0800 (PST) Message-Id: In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:37 +0000 Subject: [PATCH 7/8] ahead-behind: implement ahead_behind() logic Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Fully implement the commit-counting logic behind the ahead-behind builtin as a new ahead_behind() method in commit-reach.h. Add tests for the functionality in both t4218-ahead-behind.sh and t6600-test-reach.sh. The tests in t4218 are rather simple, but cover a simple diamond commit history completely while the tests in t6600 make use of the more complicated commit history and the test setup to check three repository states: no commit-graph, a complete commit-graph, and a half-filled commit-graph. These extra states are particularly helpful to check due to the implementation of ahead_behind() and how it relies upon ensure_generations_valid(). The interface for ahead_behind() uses two arrays. The first array of commits contains the list of all starting points for the walk. This includes all tip commits _and_ base commits. The second array, using the new ahead_behind_count struct, indicates which commits from that initial array form the base/tip pair for the ahead/behind count it will store. While the ahead-behind builtin currently only supports one base, this implementation of ahead_behind() allows multiple bases, if desired. Even with multiple bases, there is only one commit walk used for counting the ahead/behind values, saving time when the base/tip ranges overlap significantly. This interface for ahead_behind() also makes it very easy to call ensure_generations_valid() on the entire array of bases and tips. This call is necessary because it is critical that the walk that counts ahead/behind values never walks a commit more than once. Without generation numbers on every commit, there is a possibility that a commit date skew could cause the walk to revisit a commit and then double-count it. For this reason, it is strongly recommended that 'git ahead-behind' is only run in a repository with a commit-graph file that covers most of the reachable commits, storing precomputed generation numbers. If no commit-graph exists, this walk will be much slower as it must walk all reachable commits in ensure_generations_valid() before performing the counting logic. It is possible to detect if generation numbers are available at run time and redirect the implementation to another algorithm that does not require this property. However, that implementation requires a commit walk per base/tip pair _and_ can be slower due to the commit date heuristics required. Such an implementation could be considered in the future if there is a reason to include it, but most Git hosts should already be generating a commit-graph file as part of repository maintenance. Most Git clients should also be generating commit-graph files as part of background maintenance or automatic GCs. Now, let's discuss the ahead/behind counting algorithm. Each commit in the input commit list is associated with a bit position indicating "the ith commit can reach this commit". Each of these commits is associated with a bitmap with its position flipped on and then placed in a queue for walking commit history. We walk commits by popping the commit with maximum generation number out of the queue, guaranteeing that we will never walk a child of that commit in any future steps. As we walk, we load the bitmap for the current commit and perform two main steps. The _second_ step examines each parent of the current commit and adds the current commit's bitmap bits to each parent's bitmap. (We create a new bitmap for the parent if this is our first time seeing that parent.) After adding the bits to the parent's bitmap, the parent is added to the walk queue. Due to this passing of bits to parents, the current commit has a guarantee that the ith bit is enabled on its bitmap if and only if the ith commit can reach the current commit. The first step of the walk is to examine the bitmask on the current commit and decide which ranges the commit is in or not. Due to the "bit pushing" in the second step, we have a guarantee that the ith bit of the current commit's bitmap is on if and only if the ith starting commit can reach it. For each ahead_behind_count struct, check the base_index and tip_index to see if those bits are enabled on the current bitmap. If exactly one bit is enabled, then increment the corresponding 'ahead' or 'behind' count. This increment is the reason we _absolutely need_ to walk commits at most once. The only subtle thing to do with this walk is to check to see if a parent has all bits on in its bitmap, in which case it becomes "stale" and is marked with the STALE bit. This allows queue_has_nonstale() to be the terminating condition of the walk, which greatly reduces the number of commits walked if all of the commits are nearby in history. It avoids walking a large number of common commits when there is a deep history. We also use the helper method insert_no_dup() to add commits to the priority queue without adding them multiple times. This uses the PARENT2 flag. Thus, we must clear both the STALE and PARENT2 bits of all commits, in case ahead_behind() is called multiple times in the same process. There is no previous implementation of ahead-behind to compare against. A previous implementation in another fork of Git used a single process to essentially do the same walk as 'git rev-list --count ..' for every base/tip pair given as input. The single-walk implementation in this change was a significant improvement over that implementation. Another version from that fork used reachability bitmaps for the comparison, but that implementation was slower than the current commit walk implementation in almost all cases. To best present _some_ amount of evidence for this performance gain, create a new performance test, p1500-graph-walks.sh. This script could be used for other walks than just ahead-behind in the future, but let's limit to ahead-behind now. To gain some amount of a baseline, create one test that checks 'git ahead-behind' against up to 50 tips and another that uses 'git rev-list --count' in a loop. Be sure to write a commit-graph before running the performance tests. Using the Git source code as the repository, we see a pronounced improvement: Test this tree --------------------------------------------------------------- 1500.2: ahead-behind counts: git ahead-behind 0.08(0.07+0.01) 1500.3: ahead-behind counts: git rev-list 1.11(0.92+0.18) But the de-facto performance benchmark is the Linux kernel repository, which presents these values for my copy: Test this tree --------------------------------------------------------------- 1500.2: ahead-behind counts: git ahead-behind 0.27(0.25+0.02) 1500.3: ahead-behind counts: git rev-list 4.53(3.92+0.60) Signed-off-by: Derrick Stolee --- builtin/ahead-behind.c | 23 +++++++++ commit-reach.c | 95 +++++++++++++++++++++++++++++++++++++ commit-reach.h | 30 ++++++++++++ t/perf/p1500-graph-walks.sh | 25 ++++++++++ t/t4218-ahead-behind.sh | 67 ++++++++++++++++++++++++++ t/t6600-test-reach.sh | 62 ++++++++++++++++++++++++ 6 files changed, 302 insertions(+) create mode 100755 t/perf/p1500-graph-walks.sh diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c index e4f65fc0548..c06b95b5f37 100644 --- a/builtin/ahead-behind.c +++ b/builtin/ahead-behind.c @@ -2,6 +2,7 @@ #include "parse-options.h" #include "config.h" #include "commit.h" +#include "commit-reach.h" static const char * const ahead_behind_usage[] = { N_("git ahead-behind --base= [ --stdin | ]"), @@ -29,8 +30,12 @@ static int handle_arg(struct string_list *tips, const char *arg) int cmd_ahead_behind(int argc, const char **argv, const char *prefix) { const char *base_ref = NULL; + struct commit *base; int from_stdin = 0; struct string_list tips = STRING_LIST_INIT_DUP; + struct commit **commits; + struct ahead_behind_count *counts; + size_t i; struct option ahead_behind_opts[] = { OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")), @@ -71,5 +76,23 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) if (!tips.nr) return 0; + ALLOC_ARRAY(commits, tips.nr + 1); + ALLOC_ARRAY(counts, tips.nr); + + for (i = 0; i < tips.nr; i++) { + commits[i] = tips.items[i].util; + counts[i].tip_index = i; + counts[i].base_index = tips.nr; + } + commits[tips.nr] = base; + + ahead_behind(commits, tips.nr + 1, counts, tips.nr); + + for (i = 0; i < tips.nr; i++) + printf("%s %d %d\n", tips.items[i].string, + counts[i].ahead, counts[i].behind); + + free(counts); + free(commits); return 0; } diff --git a/commit-reach.c b/commit-reach.c index 2e33c599a82..87ccc2cd4f5 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -8,6 +8,7 @@ #include "revision.h" #include "tag.h" #include "commit-reach.h" +#include "ewah/ewok.h" /* Remember to update object flag allocation in object.h */ #define PARENT1 (1u<<16) @@ -941,3 +942,97 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, return found_commits; } + +define_commit_slab(bit_arrays, struct bitmap *); +static struct bit_arrays bit_arrays; + +static void insert_no_dup(struct prio_queue *queue, struct commit *c) +{ + if (c->object.flags & PARENT2) + return; + prio_queue_put(queue, c); + c->object.flags |= PARENT2; +} + +static struct bitmap *init_bit_array(struct commit *c, int width) +{ + struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c); + if (!*bitmap) + *bitmap = bitmap_word_alloc(width); + return *bitmap; +} + +static void free_bit_array(struct commit *c) +{ + struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c); + if (!*bitmap) + return; + bitmap_free(*bitmap); + *bitmap = NULL; +} + +void ahead_behind(struct commit **commits, size_t commits_nr, + struct ahead_behind_count *counts, size_t counts_nr) +{ + struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; + size_t width = (commits_nr + BITS_IN_EWORD - 1) / BITS_IN_EWORD; + size_t i; + + if (!commits_nr || !counts_nr) + return; + + for (i = 0; i < counts_nr; i++) { + counts[i].ahead = 0; + counts[i].behind = 0; + } + + ensure_generations_valid(commits, commits_nr); + + init_bit_arrays(&bit_arrays); + + for (i = 0; i < commits_nr; i++) { + struct commit *c = commits[i]; + struct bitmap *bitmap = init_bit_array(c, width); + + bitmap_set(bitmap, i); + insert_no_dup(&queue, c); + } + + while (queue_has_nonstale(&queue)) { + struct commit *c = prio_queue_get(&queue); + struct commit_list *p; + struct bitmap *bitmap_c = init_bit_array(c, width); + + for (i = 0; i < counts_nr; i++) { + int reach_from_tip = bitmap_get(bitmap_c, counts[i].tip_index); + int reach_from_base = bitmap_get(bitmap_c, counts[i].base_index); + + if (reach_from_tip ^ reach_from_base) { + if (reach_from_base) + counts[i].behind++; + else + counts[i].ahead++; + } + } + + for (p = c->parents; p; p = p->next) { + struct bitmap *bitmap_p; + + parse_commit(p->item); + + bitmap_p = init_bit_array(p->item, width); + bitmap_or(bitmap_p, bitmap_c); + + if (bitmap_popcount(bitmap_p) == commits_nr) + p->item->object.flags |= STALE; + + insert_no_dup(&queue, p->item); + } + + free_bit_array(c); + } + + repo_clear_commit_marks(the_repository, PARENT2 | STALE); + clear_bit_arrays(&bit_arrays); + clear_prio_queue(&queue); +} diff --git a/commit-reach.h b/commit-reach.h index 148b56fea50..1780f9317bf 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -104,4 +104,34 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit **to, int nr_to, unsigned int reachable_flag); +struct ahead_behind_count { + /** + * As input, the *_index members indicate which positions in + * the 'tips' array correspond to the tip and base of this + * comparison. + */ + size_t tip_index; + size_t base_index; + + /** + * These values store the computed counts for each side of the + * symmetric difference: + * + * 'ahead' stores the number of commits reachable from the tip + * and not reachable from the base. + * + * 'behind' stores the number of commits reachable from the base + * and not reachable from the tip. + */ + int ahead; + int behind; +}; + +/** + * Given an array of commits and an array of ahead_behind_count pairs, + * compute the ahead/behind counts for each pair. + */ +void ahead_behind(struct commit **commits, size_t commits_nr, + struct ahead_behind_count *counts, size_t counts_nr); + #endif diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh new file mode 100755 index 00000000000..c9ac4b7e6e2 --- /dev/null +++ b/t/perf/p1500-graph-walks.sh @@ -0,0 +1,25 @@ +#!/bin/sh + +test_description='Commit walk performance tests' +. ./perf-lib.sh + +test_perf_large_repo + +test_expect_success 'setup' ' + git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs && + sort -r allrefs | head -n 50 >refs && + git commit-graph write --reachable +' + +test_perf 'ahead-behind counts: git ahead-behind' ' + git ahead-behind --base=HEAD --stdin out && grep "usage:" out @@ -14,6 +24,11 @@ test_expect_success 'git ahead-behind without --base' ' grep "usage:" err ' +test_expect_success 'git ahead-behind with broken --base' ' + test_must_fail git ahead-behind --base=bogus HEAD 2>err && + grep "could not resolve '\''bogus'\''" err +' + test_expect_success 'git ahead-behind with broken tip' ' test_must_fail git ahead-behind --base=HEAD bogus 2>err && grep "could not resolve '\''bogus'\''" err @@ -30,4 +45,56 @@ test_expect_success 'git ahead-behind without tips' ' test_must_be_empty err ' +test_expect_success 'git ahead-behind --base=base' ' + git ahead-behind --base=base base left right merge >actual && + + cat >expect <<-EOF && + base 0 0 + left 1 0 + right 1 0 + merge 3 0 + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --base=left' ' + git ahead-behind --base=left base left right merge >actual && + + cat >expect <<-EOF && + base 0 1 + left 0 0 + right 1 1 + merge 2 0 + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --base=right' ' + git ahead-behind --base=right base left right merge >actual && + + cat >expect <<-EOF && + base 0 1 + left 1 1 + right 0 0 + merge 2 0 + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --base=merge' ' + git ahead-behind --base=merge base left right merge >actual && + + cat >expect <<-EOF && + base 0 3 + left 0 2 + right 0 2 + merge 0 0 + EOF + + test_cmp expect actual +' + test_done diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index 338a9c46a24..951e07100f6 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -443,4 +443,66 @@ test_expect_success 'get_reachable_subset:none' ' test_all_modes get_reachable_subset ' +test_expect_success 'ahead-behind:linear' ' + cat >input <<-\EOF && + commit-1-1 + commit-1-3 + commit-1-5 + commit-1-8 + EOF + cat >expect <<-\EOF && + commit-1-1 0 8 + commit-1-3 0 6 + commit-1-5 0 4 + commit-1-8 0 1 + EOF + run_all_modes git ahead-behind --base=commit-1-9 --stdin +' + +test_expect_success 'ahead-behind:all' ' + cat >input <<-\EOF && + commit-1-1 + commit-2-4 + commit-4-2 + commit-4-4 + EOF + cat >expect <<-\EOF && + commit-1-1 0 24 + commit-2-4 0 17 + commit-4-2 0 17 + commit-4-4 0 9 + EOF + run_all_modes git ahead-behind --base=commit-5-5 --stdin +' + +test_expect_success 'ahead-behind:some' ' + cat >input <<-\EOF && + commit-1-1 + commit-5-3 + commit-4-8 + commit-9-9 + EOF + cat >expect <<-\EOF && + commit-1-1 0 53 + commit-5-3 0 39 + commit-4-8 8 30 + commit-9-9 27 0 + EOF + run_all_modes git ahead-behind --base=commit-9-6 --stdin +' + +test_expect_success 'ahead-behind:none' ' + cat >input <<-\EOF && + commit-7-5 + commit-4-8 + commit-9-9 + EOF + cat >expect <<-\EOF && + commit-7-5 7 4 + commit-4-8 16 16 + commit-9-9 49 0 + EOF + run_all_modes git ahead-behind --base=commit-8-4 --stdin +' + test_done From patchwork Mon Mar 6 14:06:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13161133 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7BB3DC678D4 for ; Mon, 6 Mar 2023 14:08:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231194AbjCFOIF (ORCPT ); Mon, 6 Mar 2023 09:08:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35286 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230464AbjCFOHT (ORCPT ); Mon, 6 Mar 2023 09:07:19 -0500 Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BCF16303CC for ; Mon, 6 Mar 2023 06:06:53 -0800 (PST) Received: by mail-wr1-x42f.google.com with SMTP id e13so8908334wro.10 for ; Mon, 06 Mar 2023 06:06:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678111605; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=effbrmf4qF+w5FU0vpxjS54PIfVYnoX4SH8VIG8UrOY=; b=ONGhAMDS18ezs+wD92QJZgoq7UPTkjuUF/RUqJh8ic3XK6+gK9ppipjgTUm6q1Lv/x K535Z/t7lx1CYyvrU3D1C+YSgVcrmKK1B9LQCmC0fmYkvseJwoxKNxQHA2F8s6ijB86W W9aSxHuy8biXQQOl1dfhSLP9xpVTnQtPIbTuTTdwLZK0r6/7lJpbRnP6oiezW0uh7RPu zU8dfG7UmN/emqCDqi0soSIphg/nz2NQnw/7V04dzE9FQBgeDkfV8vYANFR6O6MfzjUk imltYioiUGOaZ0dfnF453Ls5O8nzLgZx+jRldtjTk0wxRWNxQjaXbp4XPWIaJYytRryc 7gIQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678111605; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=effbrmf4qF+w5FU0vpxjS54PIfVYnoX4SH8VIG8UrOY=; b=TMV6uXnWOint7K5YNrxlHOTrKJxilfK9ARU6wiDJ8b5k4VXsoT2+Wz9YTxeb6gFGC7 v0V57YoAI/8GiarDr3ESjs9BvyT55Hm+Ydy2xybzmBPlTzcZrzodyq8LlwP4DnsJVpXi UzNupvIOn7EJCBLHeEMjDyAAU+afTkFTz/5PvSNl/nlg6u7TGQCAf1jvvoP8Xl96BdIV 5L/A0cE0PpNgi0tKNyaJo37GQ8OjhIDlvDAa1KB/IhG10eooMntv6ku0dRNRWN9VeRkt huAUn9LByAFeykicLxQLa6alLct+Sf5g3mtKlV4Va68qE9cNAz1nBaPIr9nMQHAQwN+9 oVEQ== X-Gm-Message-State: AO0yUKVRrqI1dZC/EDfpEkSSM3JnMpL0EFidD0JJ5XNK04TAgzx1yNR1 gZUmH8qMNcwP0lZwXpRmkwnbMcaNvV8= X-Google-Smtp-Source: AK7set+fZsgdsEznFZu6aLeQAQKNzKmdmmSobRBM4Yw7CPdfnZOmzKAdO9C38Jw+MO6t/9sZ44QpNg== X-Received: by 2002:adf:e506:0:b0:2ce:3d6c:9a03 with SMTP id j6-20020adfe506000000b002ce3d6c9a03mr6013569wrm.19.1678111604881; Mon, 06 Mar 2023 06:06:44 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id e13-20020adff34d000000b002c53cc7504csm9861716wrp.78.2023.03.06.06.06.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Mar 2023 06:06:44 -0800 (PST) Message-Id: <07eb2cbb699c875e5fdca86d675c97d4d434f511.1678111599.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 06 Mar 2023 14:06:38 +0000 Subject: [PATCH 8/8] ahead-behind: add --contains mode Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The 'git ahead-behind' builtin can answer a list of questions that do not require the full ahead/behind counts. For example, instead of using 'git branch --contains=' to get the full list of branches that contain the commit at , a list of tips could be passed to 'git ahead-behind --base=' and the rows that report a "behind" value of zero show which tips can reach . By contract, the rows that report an "ahead" value of zero show which tips are reachable from the given base. This type of query does not have an existing equivalent for batching this request. While extracting the information from 'git ahead-behind' is not terribly difficult, it does more work than required to answer this query: it _counts_. Add a new '--contains' mode to 'git ahead-behind' that removes the counting behavior and focuses instead on the reachability concern. The output of the builtin changes in this mode: instead of reporting " " for every input tip, it will instead report "" for the input tips that are reachable from the specified base. The algorithm is implemented in commit-reach.c in the method tips_reachable_from_base(). This method takes a string_list of tips and assigns the 'util' for each item with the value 1 if the base commit can reach those tips. Like other reachability queries in commit-reach.c, the fastest way to search for "can A reach B?" is to do a depth-first search up to the generation number of B, preferring to explore first parents before later parents. While we must walk all reachable commits up to that generation number when the answer is "no", the depth-first search can answer "yes" much faster than other approaches in most cases. This search becomes trickier when there are multiple targets for the depth-first search. The commits with lower generation number are more likely to be within the history of the start commit, but we don't want to waste time searching commits of low generation number if the commit target with lowest generation number has already been found. The trick here is to take the input commits and sort them by generation number in ascending order. Track the index within this order as min_generation_index. When we find a commit, if its index in the list is equal to min_generation_index, then we can increase the generation number boundary of our search to the next-lowest value in the list. With this mechanism, the number of commits to search is minimized with respect to the depth-first search heuristic. We will walk all commits up to the minimum generation number of a commit that is _not_ reachable from the start, but we will walk only the necessary portion of the depth-first search for the reachable commits of lower generation. We can test this completely in the simple repo example in t4218 and more substantially in the larger repository example in t6600. We can also add a performance test to demonstrate the speedup relative to the 'git ahead-behind' builtin without the '--contains' option. For the Git source code repository, I was able to measure a speedup, even though both are quite fast. Test this tree -------------------------------------------------------------------------- 1500.2: ahead-behind counts: git ahead-behind 0.06(0.06+0.00) 1500.3: ahead-behind counts: git rev-list 1.08(0.90+0.18) 1500.4: ahead-behind counts: git ahead-behind --contains 0.02(0.02+0.00) In the Linux kernel repository, the impact is more pronounced: Test this tree -------------------------------------------------------------------------- 1500.2: ahead-behind counts: git ahead-behind 0.26(0.25+0.01) 1500.3: ahead-behind counts: git rev-list 4.58(3.92+0.66) 1500.4: ahead-behind counts: git ahead-behind --contains 0.02(0.00+0.02) Signed-off-by: Derrick Stolee --- Documentation/git-ahead-behind.txt | 12 +++- builtin/ahead-behind.c | 27 ++++++- commit-reach.c | 110 +++++++++++++++++++++++++++++ commit-reach.h | 7 ++ t/perf/p1500-graph-walks.sh | 4 ++ t/t4218-ahead-behind.sh | 62 ++++++++++++++++ t/t6600-test-reach.sh | 58 +++++++++++++++ 7 files changed, 277 insertions(+), 3 deletions(-) diff --git a/Documentation/git-ahead-behind.txt b/Documentation/git-ahead-behind.txt index 2dd5147f6b2..1652a51d719 100644 --- a/Documentation/git-ahead-behind.txt +++ b/Documentation/git-ahead-behind.txt @@ -8,7 +8,7 @@ git-ahead-behind - Count the commits on each side of a revision range SYNOPSIS -------- [verse] -'git ahead-behind' --base= [ --stdin | ] +'git ahead-behind' --base= [ --contains ] [ --stdin | ] DESCRIPTION ----------- @@ -39,6 +39,9 @@ reported to stdout one line at a time as follows: There will be exactly one line per input revision, but the lines may be in an arbitrary order. +If the `--contains` option is provided, then the output will list the +`` refs are reachable from the provided ``, one per line. + OPTIONS ------- @@ -50,6 +53,13 @@ OPTIONS Read revision tips and ranges from stdin instead of from the command-line. +--contains:: + Specify that instead of counting the ahead/behind values, only + indicate whether each tip reference is reachable from the base. In + this mode, the output format changes to include only the name of + each tip by name, one per line, and only the tips reachable from + the base are included in the output. + --ignore-missing:: When parsing tip references, ignore any references that are not found. This is useful when operating in an environment where a diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c index c06b95b5f37..4efd324d5d9 100644 --- a/builtin/ahead-behind.c +++ b/builtin/ahead-behind.c @@ -5,7 +5,7 @@ #include "commit-reach.h" static const char * const ahead_behind_usage[] = { - N_("git ahead-behind --base= [ --stdin | ]"), + N_("git ahead-behind --base= [ --contains ] [ --stdin | ]"), NULL }; @@ -31,7 +31,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) { const char *base_ref = NULL; struct commit *base; - int from_stdin = 0; + int from_stdin = 0, contains = 0; struct string_list tips = STRING_LIST_INIT_DUP; struct commit **commits; struct ahead_behind_count *counts; @@ -41,6 +41,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")), OPT_BOOL(0 , "stdin", &from_stdin, N_("read rev names from stdin")), OPT_BOOL(0 , "ignore-missing", &ignore_missing, N_("ignore missing tip references")), + OPT_BOOL(0 , "contains", &contains, N_("only check that tips are reachable from the base")), OPT_END() }; @@ -52,6 +53,10 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) git_config(git_default_config, NULL); + base = lookup_commit_reference_by_name(base_ref); + if (!base) + die(_("could not resolve '%s'"), base_ref); + if (from_stdin) { struct strbuf line = STRBUF_INIT; @@ -76,6 +81,24 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix) if (!tips.nr) return 0; + if (contains) { + struct string_list_item *item; + + /* clear out */ + for_each_string_list_item(item, &tips) + item->util = NULL; + + tips_reachable_from_base(base, &tips); + + for_each_string_list_item(item, &tips) { + if (item->util) + printf("%s\n", item->string); + } + + return 0; + } + /* else: not --contains, but normal ahead-behind counting. */ + ALLOC_ARRAY(commits, tips.nr + 1); ALLOC_ARRAY(counts, tips.nr); diff --git a/commit-reach.c b/commit-reach.c index 87ccc2cd4f5..a7a2c045551 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -1036,3 +1036,113 @@ void ahead_behind(struct commit **commits, size_t commits_nr, clear_bit_arrays(&bit_arrays); clear_prio_queue(&queue); } + +struct commit_and_index { + struct commit *commit; + unsigned int index; + timestamp_t generation; +}; + +static int compare_commit_and_index_by_generation(const void *va, const void *vb) +{ + const struct commit_and_index *a = (const struct commit_and_index *)va; + const struct commit_and_index *b = (const struct commit_and_index *)vb; + + if (a->generation > b->generation) + return 1; + if (a->generation < b->generation) + return -1; + return 0; +} + +void tips_reachable_from_base(struct commit *base, + struct string_list *tips) +{ + unsigned int i; + struct commit_and_index *commits; + unsigned int min_generation_index = 0; + timestamp_t min_generation; + struct commit_list *stack = NULL; + + if (!base || !tips || !tips->nr) + return; + + /* + * Do a depth-first search starting at 'base' to search for the + * tips. Stop at the lowest (un-found) generation number. When + * finding the lowest commit, increase the minimum generation + * number to the next lowest (un-found) generation number. + */ + + CALLOC_ARRAY(commits, tips->nr); + + for (i = 0; i < tips->nr; i++) { + commits[i].commit = lookup_commit_reference_by_name(tips->items[i].string); + commits[i].index = i; + commits[i].generation = commit_graph_generation(commits[i].commit); + } + + /* Sort with generation number ascending. */ + QSORT(commits, tips->nr, compare_commit_and_index_by_generation); + min_generation = commits[0].generation; + + parse_commit(base); + commit_list_insert(base, &stack); + + while (stack) { + unsigned int j; + int explored_all_parents = 1; + struct commit_list *p; + struct commit *c = stack->item; + timestamp_t c_gen = commit_graph_generation(c); + + /* Does it match any of our bases? */ + for (j = min_generation_index; j < tips->nr; j++) { + if (c_gen < commits[j].generation) + break; + + if (commits[j].commit == c) { + tips->items[commits[j].index].util = (void *)(uintptr_t)1; + + if (j == min_generation_index) { + unsigned int k = j + 1; + while (k < tips->nr && + tips->items[commits[k].index].util) + k++; + + /* Terminate early if all found. */ + if (k >= tips->nr) + goto done; + + min_generation_index = k; + min_generation = commits[k].generation; + } + } + } + + for (p = c->parents; p; p = p->next) { + parse_commit(p->item); + + /* Have we already explored this parent? */ + if (p->item->object.flags & SEEN) + continue; + + /* Is it below the current minimum generation? */ + if (commit_graph_generation(p->item) < min_generation) + continue; + + /* Ok, we will explore from here on. */ + p->item->object.flags |= SEEN; + explored_all_parents = 0; + commit_list_insert(p->item, &stack); + break; + } + + if (explored_all_parents) + pop_commit(&stack); + } + +done: + free(commits); + repo_clear_commit_marks(the_repository, SEEN); +} diff --git a/commit-reach.h b/commit-reach.h index 1780f9317bf..fa8994f5696 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -134,4 +134,11 @@ struct ahead_behind_count { void ahead_behind(struct commit **commits, size_t commits_nr, struct ahead_behind_count *counts, size_t counts_nr); +/* + * Populate the "util" of each string_list item with the boolean value + * corresponding to "can 'base' reach this tip?" + */ +void tips_reachable_from_base(struct commit *base, + struct string_list *tips); + #endif diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh index c9ac4b7e6e2..56de6c5b13d 100755 --- a/t/perf/p1500-graph-walks.sh +++ b/t/perf/p1500-graph-walks.sh @@ -22,4 +22,8 @@ test_perf 'ahead-behind counts: git rev-list' ' done ' +test_perf 'ahead-behind counts: git ahead-behind --contains' ' + git ahead-behind --contains --base=HEAD --stdin err && + grep "could not resolve '\''bogus'\''" err +' + +test_expect_success 'git ahead-behind --contains with broken tip and --ignore-missing' ' + git ahead-behind --base=HEAD --contains \ + --ignore-missing bogus 2>err >out && + test_must_be_empty err && + test_must_be_empty out +' + test_expect_success 'git ahead-behind without tips' ' git ahead-behind --base=HEAD 2>err && test_must_be_empty err @@ -97,4 +110,53 @@ test_expect_success 'git ahead-behind --base=merge' ' test_cmp expect actual ' +test_expect_success 'git ahead-behind --contains --base=base' ' + git ahead-behind --contains --base=base \ + base left right merge >actual && + + cat >expect <<-EOF && + base + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --contains --base=left' ' + git ahead-behind --contains --base=left \ + base left right merge >actual && + + cat >expect <<-EOF && + base + left + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --contains --base=right' ' + git ahead-behind --contains --base=right \ + base left right merge >actual && + + cat >expect <<-EOF && + base + right + EOF + + test_cmp expect actual +' + +test_expect_success 'git ahead-behind --contains --base=merge' ' + git ahead-behind --contains --base=merge \ + base left right merge >actual && + + cat >expect <<-EOF && + base + left + right + merge + EOF + + test_cmp expect actual +' + test_done diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index 951e07100f6..2fdad7b3619 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -505,4 +505,62 @@ test_expect_success 'ahead-behind:none' ' run_all_modes git ahead-behind --base=commit-8-4 --stdin ' +test_expect_success 'ahead-behind--contains:all' ' + cat >input <<-\EOF && + commit-1-1 + commit-2-4 + commit-4-2 + commit-4-4 + EOF + cat >expect <<-\EOF && + commit-1-1 + commit-2-4 + commit-4-2 + commit-4-4 + EOF + run_all_modes git ahead-behind --contains --base=commit-5-5 \ + --stdin --use-bitmap-index +' + +test_expect_success 'ahead-behind--contains:some' ' + cat >input <<-\EOF && + commit-1-1 + commit-5-3 + commit-4-8 + commit-9-9 + EOF + cat >expect <<-\EOF && + commit-1-1 + commit-5-3 + EOF + run_all_modes git ahead-behind --contains --base=commit-9-6 \ + --stdin --use-bitmap-index +' + +test_expect_success 'ahead-behind--contains:some, reordered' ' + cat >input <<-\EOF && + commit-4-8 + commit-5-3 + commit-9-9 + commit-1-1 + EOF + cat >expect <<-\EOF && + commit-5-3 + commit-1-1 + EOF + run_all_modes git ahead-behind --contains --base=commit-9-6 \ + --stdin --use-bitmap-index +' + +test_expect_success 'ahead-behind--contains:none' ' + cat >input <<-\EOF && + commit-7-5 + commit-4-8 + commit-9-9 + EOF + >expect && + run_all_modes git ahead-behind --contains --base=commit-8-4 \ + --stdin --use-bitmap-index +' + test_done