From patchwork Tue Sep 18 04:08:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603709 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4791E913 for ; Tue, 18 Sep 2018 04:08:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 35E2C2A1E8 for ; Tue, 18 Sep 2018 04:08:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2983A2A20F; Tue, 18 Sep 2018 04:08:47 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A7BDF2A1B5 for ; Tue, 18 Sep 2018 04:08:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727140AbeIRJjY (ORCPT ); Tue, 18 Sep 2018 05:39:24 -0400 Received: from mail-pf1-f196.google.com ([209.85.210.196]:42771 "EHLO mail-pf1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJjY (ORCPT ); Tue, 18 Sep 2018 05:39:24 -0400 Received: by mail-pf1-f196.google.com with SMTP id l9-v6so325165pff.9 for ; Mon, 17 Sep 2018 21:08:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=zhzyC86jamcIAKUp1vhGlOa+f9+2z11kBeOkNS8kz2Q=; b=uW8M+kFZncwBQ6PpY/sihv1KwQ8RE2LkfFkYV3r5Pwur0a1ieM67jQRZFmUiYOJORX kMN8PycqkbBdbSE2bA37J3IOqJDin9W4IbhNutN0Xsq5UBVHL2CNQYmI8/wiX89zCVW/ MfzjV8apAhxsOTQq5A7fMHGVfHHUPu3CI4IlQ2Ufl3coPixPNy7nkFhh7sSHWlFwNOhV mmCxMEbCOyIvqXpBzFuzE5g+Clc2kp9362VI/cdPpcrCAvmNzP7saQbRsaqytbcKY5/9 JTxR7boEr/kfbMBwEs/5lQU2QOhaU7q9kaYeyR9XL7jQd3W0jvHpnM7RkPNNL0p6ElZJ 6bNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=zhzyC86jamcIAKUp1vhGlOa+f9+2z11kBeOkNS8kz2Q=; b=Wfpq0/OV3yu3iw/rfmp2Ps/v5KpwEJ7uviUhJ6b4h2R8tjfF0XYK5yiOgHJ/FWWRtO fo3NPmKpuLBX6C14/j9kN3GuziN8MzMXpugu/1FiNpRYy9Tv/yewzfzVLWnoO/G4Ltn1 sypGThItcj+XYMGZusKDavEnIVL1jsnmiOTpbw+14gU0CtVw7u6p+iP0qvRJcD7EQo0p eBgF2Z9EnJUGygiuoMG74SqoPIoNSjyuuA1uM0POIn4YCnEoW1VxhvJw5Bd2RCmrNPoH y+U4bpq1ydmmml4OpNAEanIzaRcjvX0EztOfrPa6VWnpbB6W1e4ZuZVqkohNIMIEldBI IJ/g== X-Gm-Message-State: APzg51A4i4joxs5NUsZ2SAbYue3pUCZTCY9DZWmggK5VBvhl1slsjGV8 xD0j0Z/JBFeoFmd+/rdehnfX6kLu X-Google-Smtp-Source: ANB0VdbMQMRkQB0uv5TzNqcM7iHqGOhPJuvESmBC2JAEJdeRnq9VTeOufA6O1QqryqDDjtcYH5Q4UQ== X-Received: by 2002:a63:91:: with SMTP id 139-v6mr25979167pga.389.1537243724160; Mon, 17 Sep 2018 21:08:44 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id s27-v6sm35491271pfk.133.2018.09.17.21.08.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:43 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:43 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:34 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 1/6] prio-queue: add 'peek' operation Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek(). Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh. Signed-off-by: Derrick Stolee --- prio-queue.c | 9 +++++++++ prio-queue.h | 6 ++++++ t/helper/test-prio-queue.c | 10 +++++++--- 3 files changed, 22 insertions(+), 3 deletions(-) diff --git a/prio-queue.c b/prio-queue.c index a078451872..d3f488cb05 100644 --- a/prio-queue.c +++ b/prio-queue.c @@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue) } return result; } + +void *prio_queue_peek(struct prio_queue *queue) +{ + if (!queue->nr) + return NULL; + if (!queue->compare) + return queue->array[queue->nr - 1].data; + return queue->array[0].data; +} diff --git a/prio-queue.h b/prio-queue.h index d030ec9dd6..682e51867a 100644 --- a/prio-queue.h +++ b/prio-queue.h @@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing); */ extern void *prio_queue_get(struct prio_queue *); +/* + * Gain access to the "thing" that would be returned by + * prio_queue_get, but do not remove it from the queue. + */ +extern void *prio_queue_peek(struct prio_queue *); + extern void clear_prio_queue(struct prio_queue *); /* Reverse the LIFO elements */ diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c index 9807b649b1..e817bbf464 100644 --- a/t/helper/test-prio-queue.c +++ b/t/helper/test-prio-queue.c @@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv) struct prio_queue pq = { intcmp }; while (*++argv) { - if (!strcmp(*argv, "get")) - show(prio_queue_get(&pq)); - else if (!strcmp(*argv, "dump")) { + if (!strcmp(*argv, "get")) { + void *peek = prio_queue_peek(&pq); + void *get = prio_queue_get(&pq); + if (peek != get) + BUG("peek and get results do not match"); + show(get); + } else if (!strcmp(*argv, "dump")) { int *v; while ((v = prio_queue_get(&pq))) show(v); From patchwork Tue Sep 18 04:08:44 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603713 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D4CD9913 for ; Tue, 18 Sep 2018 04:08:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id C48EC2A1B4 for ; Tue, 18 Sep 2018 04:08:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id B8DD92A1E8; Tue, 18 Sep 2018 04:08:48 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 65F742A1B4 for ; Tue, 18 Sep 2018 04:08:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727471AbeIRJj0 (ORCPT ); Tue, 18 Sep 2018 05:39:26 -0400 Received: from mail-pf1-f193.google.com ([209.85.210.193]:36683 "EHLO mail-pf1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJj0 (ORCPT ); Tue, 18 Sep 2018 05:39:26 -0400 Received: by mail-pf1-f193.google.com with SMTP id b11-v6so338347pfo.3 for ; Mon, 17 Sep 2018 21:08:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=QcshJYbErKPtRZt/cFP+z4bKvfLxODsQO0mhl0dPlSA=; b=qXFEg5M3w5kS4hYWqvC6IjoVtAPIbVDT6Ii0KvBvTZgJcyZ8c06hjZeLLavR/kgELH TmJWJGpcbTkpV4fSCQewCiq5IOgzWEtPP6YBNg0Gcz8rGEfLktlJ5Ar/eynga9TWk38/ 0Jk9A6JUsNhgrudRA9pN7D1zwEkt89ntx7MIw8/zrEd053AHFVa4JMkLfHmlWKFV5dgl sWCA+rI0Ey15rANplinumAGl1FlIYfXMYdCv3n8kb0dVfb4PoR4dbT+AUZE29+kK5aNw /y8mON5Hd5WFernYR+xGXNDsSM6OhKWnFVel4z8WVa4ljFLOXtAhxxFUDs1XtZ3Ay8N/ 61Cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=QcshJYbErKPtRZt/cFP+z4bKvfLxODsQO0mhl0dPlSA=; b=AcBioB30YmV8+3fsisFhmz1tcxW0YrIlJygXZ7ZzsOo5CyV7ZNwqpTMrizvXUiN4PT kSAVGNMuUEY/CCrHYlLJd0f7gsa8HOLoPiZgOEi0afNcr9KyxdArKd5sLInuIiJgp5RQ r/L57nNIJx8IyH5iI9v+T9puUpJI2jOqKd72wnEla49gpC6T8J9z4hIeJ+25RvdSMj33 6Z83KHKJs8AEZgDuU/2SIhyIG1+wTGNN7/DcnVMYpwNqoXe7HH/Fu+ZzPzZTByFw3zzp rYQyROv2sKtLWQERRraYHW8/y+IbN59ALBM5Ghkn910ReALJ8QnARyfcRYlyLj5NZT6I rdcA== X-Gm-Message-State: APzg51CGIpZM8nH77lLhuhx7hgZjMR6isuOcOjDFVMDTrtYXtwqFYcXv Z1ZEz0NsaM453dWjMhI/sDTuDdc+ X-Google-Smtp-Source: ANB0VdZ53x+BbUb48BvakhjOPOYGABj2AK/cQTaDynFoJzPE+DHd10Xs5scFgsqaxmmIIS2TQKZX+Q== X-Received: by 2002:a62:b0e:: with SMTP id t14-v6mr28382124pfi.36.1537243725574; Mon, 17 Sep 2018 21:08:45 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id k126-v6sm23460415pgk.26.2018.09.17.21.08.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:44 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:44 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:35 GMT Message-Id: <404c9186080ecee6c1cc39a6dcd17deaaa7a620a.1537243720.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 2/6] test-reach: add run_three_modes method Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee The 'test_three_modes' method assumes we are using the 'test-tool reach' command for our test. However, we may want to use the data shape of our commit graph and the three modes (no commit-graph, full commit-graph, partial commit-graph) for other git commands. Split test_three_modes to be a simple translation on a more general run_three_modes method that executes the given command and tests the actual output to the expected output. While inspecting this code, I realized that the final test for 'commit_contains --tag' is silently dropping the '--tag' argument. It should be quoted to include both. Signed-off-by: Derrick Stolee --- t/t6600-test-reach.sh | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..1b18e12a4e 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -53,18 +53,22 @@ test_expect_success 'setup' ' git config core.commitGraph true ' -test_three_modes () { +run_three_modes () { test_when_finished rm -rf .git/objects/info/commit-graph && - test-tool reach $1 actual && + $1 actual && test_cmp expect actual && cp commit-graph-full .git/objects/info/commit-graph && - test-tool reach $1 actual && + $1 actual && test_cmp expect actual && cp commit-graph-half .git/objects/info/commit-graph && - test-tool reach $1 actual && + $1 actual && test_cmp expect actual } +test_three_modes () { + run_three_modes "test-tool reach $1" +} + test_expect_success 'ref_newer:miss' ' cat >input <<-\EOF && A:commit-5-7 @@ -219,7 +223,7 @@ test_expect_success 'commit_contains:hit' ' EOF echo "commit_contains(_,A,X,_):1" >expect && test_three_modes commit_contains && - test_three_modes commit_contains --tag + test_three_modes "commit_contains --tag" ' test_expect_success 'commit_contains:miss' ' From patchwork Tue Sep 18 04:08:46 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603715 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 118A0112B for ; Tue, 18 Sep 2018 04:08:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 023942A1B4 for ; Tue, 18 Sep 2018 04:08:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id EAB332A1E8; Tue, 18 Sep 2018 04:08:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 75B422A1B4 for ; Tue, 18 Sep 2018 04:08:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728895AbeIRJj1 (ORCPT ); Tue, 18 Sep 2018 05:39:27 -0400 Received: from mail-pl1-f195.google.com ([209.85.214.195]:44565 "EHLO mail-pl1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJj1 (ORCPT ); Tue, 18 Sep 2018 05:39:27 -0400 Received: by mail-pl1-f195.google.com with SMTP id ba4-v6so303474plb.11 for ; Mon, 17 Sep 2018 21:08:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=K65VwEnoM18mn4v7KlCl+CxtPYHXpgqjKxIDTT0LP/A=; b=CspUjKrWDON21EUJBkUY583v1nntis+JCqQTouo8M1o59c6rkE1c/RWCPhuTiO+Nz0 B/j/S9GnTDlD58Fl9pdvStwYIrVc3F/p95CFeqJFC4bDRt6XSMaAv7JfyrzMzZEJUYE5 nxrGYEImqa+cs1WrDFOjJHWlne1cstcJ4wgiAgWOiC/QME9dOC3POJf81innsD7It6Ov KHm7VeSKC8YXs2aiNdn/FXQAmvyZKUc7FReRo1ZdgqK3A4Js5+G9BJjM4cvEH949joFF qRjUdMegHQJh3isReLQPbr8R7e6s4MeC1Lr9i36DteQFDcpKN9nxGtIN4ORJ2JZQvSgR ilHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=K65VwEnoM18mn4v7KlCl+CxtPYHXpgqjKxIDTT0LP/A=; b=HN00idR5hLnI4xbTw7BzXiQ38ttprVQ4FpprMBFWy7R2SzQBwXA1RC8UOE8AfF7lrI CJ4HAM4/ALVd+K/FMwXdoKzbNEHqNOIcaP+I9/1q1k3Kov160H0y/H/SFA6lQFtMH+FR XzGDrCOwc5mj/D4i7buSQBcAwxocxulYvhPSVS3QZCWQUyJoUDzwu0wbTB5CQBwjnE7/ mFK7L9BliElDXB1dzEPJpBDF6qqqnA7vcFPwQqLl1bCyCKdKKhgHoR4rWMeYEyMTBEhK Yxfji6tr3To0VPFbOSr2hj3wD6EDVFdWSZRHgVo88zM0mHQ0DKviGzciCxO97ePtFwxG jupw== X-Gm-Message-State: APzg51AOqx4f7Q6qLcvajP9vhGynIa3+yBD00oGijrGf8CS3lXLloQo8 4cK9EBT6b/BCidtVFpwYYW307++d X-Google-Smtp-Source: ANB0VdYpJliLvRDomtt/z9aLG0kuDlO1Sjm7IdTojF/pY6GNBDsTp35+MT9MQjzN0RXNIZQ+/rpkCQ== X-Received: by 2002:a17:902:7246:: with SMTP id c6-v6mr27596610pll.28.1537243726931; Mon, 17 Sep 2018 21:08:46 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id y128-v6sm22779629pfb.56.2018.09.17.21.08.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:46 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:46 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:36 GMT Message-Id: <30dee58c615701c8810d055008a687fca278888a.1537243720.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 3/6] test-reach: add rev-list tests Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee The rev-list command is critical to Git's functionality. Ensure it works in the three commit-graph environments constructed in t6600-test-reach.sh. Here are a few important types of rev-list operations: * Basic: git rev-list --topo-order HEAD * Range: git rev-list --topo-order compare..HEAD * Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD * Symmetric Difference: git rev-list --topo-order compare...HEAD Signed-off-by: Derrick Stolee --- t/t6600-test-reach.sh | 84 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index 1b18e12a4e..2fcaa39077 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -243,4 +243,88 @@ test_expect_success 'commit_contains:miss' ' test_three_modes commit_contains --tag ' +test_expect_success 'rev-list: basic topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \ + commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \ + commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \ + commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \ + >expect && + run_three_modes "git rev-list --topo-order commit-6-6" +' + +test_expect_success 'rev-list: first-parent topo-order' ' + git rev-parse \ + commit-6-6 \ + commit-6-5 \ + commit-6-4 \ + commit-6-3 \ + commit-6-2 \ + commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \ + >expect && + run_three_modes "git rev-list --first-parent --topo-order commit-6-6" +' + +test_expect_success 'rev-list: range topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes "git rev-list --topo-order commit-3-3..commit-6-6" +' + +test_expect_success 'rev-list: range topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 \ + commit-6-5 commit-5-5 commit-4-5 \ + commit-6-4 commit-5-4 commit-4-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes "git rev-list --topo-order commit-3-8..commit-6-6" +' + +test_expect_success 'rev-list: first-parent range topo-order' ' + git rev-parse \ + commit-6-6 \ + commit-6-5 \ + commit-6-4 \ + commit-6-3 \ + commit-6-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + >expect && + run_three_modes "git rev-list --first-parent --topo-order commit-3-8..commit-6-6" +' + +test_expect_success 'rev-list: ancestry-path topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 commit-3-6 \ + commit-6-5 commit-5-5 commit-4-5 commit-3-5 \ + commit-6-4 commit-5-4 commit-4-4 commit-3-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + >expect && + run_three_modes "git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6" +' + +test_expect_success 'rev-list: symmetric difference topo-order' ' + git rev-parse \ + commit-6-6 commit-5-6 commit-4-6 \ + commit-6-5 commit-5-5 commit-4-5 \ + commit-6-4 commit-5-4 commit-4-4 \ + commit-6-3 commit-5-3 commit-4-3 \ + commit-6-2 commit-5-2 commit-4-2 \ + commit-6-1 commit-5-1 commit-4-1 \ + commit-3-8 commit-2-8 commit-1-8 \ + commit-3-7 commit-2-7 commit-1-7 \ + >expect && + run_three_modes "git rev-list --topo-order commit-3-8...commit-6-6" +' + test_done From patchwork Tue Sep 18 04:08:47 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603717 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1395F112B for ; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 003F82A1B4 for ; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E900A2A1E8; Tue, 18 Sep 2018 04:08:51 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B9A2D2A1B4 for ; Tue, 18 Sep 2018 04:08:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728944AbeIRJj3 (ORCPT ); Tue, 18 Sep 2018 05:39:29 -0400 Received: from mail-pl1-f193.google.com ([209.85.214.193]:39044 "EHLO mail-pl1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJj2 (ORCPT ); Tue, 18 Sep 2018 05:39:28 -0400 Received: by mail-pl1-f193.google.com with SMTP id w14-v6so313764plp.6 for ; Mon, 17 Sep 2018 21:08:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=kxsxfuatUGnB3bzwSX68mZcKrbJkiLhKQcgRuUNHX/w=; b=kgzSRxofw1pvLhxLIqUh/mBIQiSTi0zL1S9jpzxsmPJYlQSvQeZRafubNZ1jmspSYM fDEUGlY3TGUe6saf/1AwcesKENFvv6DLRZQy2klhyzBRTeKZcazbcSH9WbWH45fMTKky uM31TAiGi0o9uV9ISoYy8wYiQc28Pwghtlo5Uwtlbi7voaJA0eVvBzg2EM5wLr0PDJXH 5Zq5bVPNZrXYkjPqn6Azu2Bzpzsi5Pt+/0RxfGmykzQv3PnyUJTJRfz1C9BFOBtqvExm FiGA94ayUcvfkf3EoXBqZsg9yTDd2bAyjxbTDKoi8QeL9sveOcUZhAYuUerbBd8Ig0Kx VaIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=kxsxfuatUGnB3bzwSX68mZcKrbJkiLhKQcgRuUNHX/w=; b=I//FGiJYyJoBKJ/w/UqVgYzrb5bsuhLBkeypGVrqG+bbe/S3sA1LeOQi0a9XS9A+zU eTr8HL6PrGjOsilAhohohi4epHdWxeLGx66wNtm1XMffqTo5/XByHVYChpQW8Yhy9BiT L/Cb5jW+hLImZlSiiZ2kvX9U6/k5CtJNvz51pruKnxE9M32vdFftwtPcmGmKVCT2akkQ fD6uK6kOWfa4dBnwKMQrdDytkAeYO3C6dgLWd497F7aD79U1fv7DugQXrn3xduVbT4bq M1Rcah0+LE5ZiQbd6wui0is/VIROQqvQ+c2fdYRITFQiY1E9m891X9VlHo8kqQnoe0m4 CIUw== X-Gm-Message-State: APzg51DMFsQeCVDh4pDM4oO1ogBClljhc2SY6mz2e5KyrfaeaDqcokQI bU2JpYG9TY3Z64qD+GG/Nq2wC2r6 X-Google-Smtp-Source: ANB0VdaPC8Ee69QgCClZDknLojhfw0Eslc6A/Ftbc0WE6XpjKgB+QyiGw/hEBKP8qZUCT4ynibM/Aw== X-Received: by 2002:a17:902:9696:: with SMTP id n22-v6mr27867930plp.212.1537243728314; Mon, 17 Sep 2018 21:08:48 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id q6-v6sm19928166pgq.19.2018.09.17.21.08.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:47 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:47 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:37 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 4/6] revision.c: begin refactoring --topo-order logic Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee When running 'git rev-list --topo-order' and its kin, the topo_order setting in struct rev_info implies the limited setting. This means that the following things happen during prepare_revision_walk(): * revs->limited implies we run limit_list() to walk the entire reachable set. There are some short-cuts here, such as if we perform a range query like 'git rev-list COMPARE..HEAD' and we can stop limit_list() when all queued commits are uninteresting. * revs->topo_order implies we run sort_in_topological_order(). See the implementation of that method in commit.c. It implies that the full set of commits to order is in the given commit_list. These two methods imply that a 'git rev-list --topo-order HEAD' command must walk the entire reachable set of commits _twice_ before returning a single result. If we have a commit-graph file with generation numbers computed, then there is a better way. This patch introduces some necessary logic redirection when we are in this situation. In v2.18.0, the commit-graph file contains zero-valued bytes in the positions where the generation number is stored in v2.19.0 and later. Thus, we use generation_numbers_enabled() to check if the commit-graph is available and has non-zero generation numbers. When setting revs->limited only because revs->topo_order is true, only do so if generation numbers are not available. There is no reason to use the new logic as it will behave similarly when all generation numbers are INFINITY or ZERO. In prepare_revision_walk(), if we have revs->topo_order but not revs->limited, then we trigger the new logic. It breaks the logic into three pieces, to fit with the existing framework: 1. init_topo_walk() fills a new struct topo_walk_info in the rev_info struct. We use the presence of this struct as a signal to use the new methods during our walk. In this patch, this method simply calls limit_list() and sort_in_topological_order(). In the future, this method will set up a new data structure to perform that logic in-line. 2. next_topo_commit() provides get_revision_1() with the next topo- ordered commit in the list. Currently, this simply pops the commit from revs->commits. 3. expand_topo_walk() provides get_revision_1() with a way to signal walking beyond the latest commit. Currently, this calls add_parents_to_list() exactly like the old logic. While this commit presents method redirection for performing the exact same logic as before, it allows the next commit to focus only on the new logic. Signed-off-by: Derrick Stolee --- revision.c | 42 ++++++++++++++++++++++++++++++++++++++---- revision.h | 4 ++++ 2 files changed, 42 insertions(+), 4 deletions(-) diff --git a/revision.c b/revision.c index e18bd530e4..2dcde8a8ac 100644 --- a/revision.c +++ b/revision.c @@ -25,6 +25,7 @@ #include "worktree.h" #include "argv-array.h" #include "commit-reach.h" +#include "commit-graph.h" volatile show_early_output_fn_t show_early_output; @@ -2454,7 +2455,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s if (revs->diffopt.objfind) revs->simplify_history = 0; - if (revs->topo_order) + if (revs->topo_order && !generation_numbers_enabled(the_repository)) revs->limited = 1; if (revs->prune_data.nr) { @@ -2892,6 +2893,33 @@ static int mark_uninteresting(const struct object_id *oid, return 0; } +struct topo_walk_info {}; + +static void init_topo_walk(struct rev_info *revs) +{ + struct topo_walk_info *info; + revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info)); + info = revs->topo_walk_info; + memset(info, 0, sizeof(struct topo_walk_info)); + + limit_list(revs); + sort_in_topological_order(&revs->commits, revs->sort_order); +} + +static struct commit *next_topo_commit(struct rev_info *revs) +{ + return pop_commit(&revs->commits); +} + +static void expand_topo_walk(struct rev_info *revs, struct commit *commit) +{ + if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) { + if (!revs->ignore_missing_links) + die("Failed to traverse parents of commit %s", + oid_to_hex(&commit->object.oid)); + } +} + int prepare_revision_walk(struct rev_info *revs) { int i; @@ -2928,11 +2956,13 @@ int prepare_revision_walk(struct rev_info *revs) commit_list_sort_by_date(&revs->commits); if (revs->no_walk) return 0; - if (revs->limited) + if (revs->limited) { if (limit_list(revs) < 0) return -1; - if (revs->topo_order) - sort_in_topological_order(&revs->commits, revs->sort_order); + if (revs->topo_order) + sort_in_topological_order(&revs->commits, revs->sort_order); + } else if (revs->topo_order) + init_topo_walk(revs); if (revs->line_level_traverse) line_log_filter(revs); if (revs->simplify_merges) @@ -3257,6 +3287,8 @@ static struct commit *get_revision_1(struct rev_info *revs) if (revs->reflog_info) commit = next_reflog_entry(revs->reflog_info); + else if (revs->topo_walk_info) + commit = next_topo_commit(revs); else commit = pop_commit(&revs->commits); @@ -3278,6 +3310,8 @@ static struct commit *get_revision_1(struct rev_info *revs) if (revs->reflog_info) try_to_simplify_commit(revs, commit); + else if (revs->topo_walk_info) + expand_topo_walk(revs, commit); else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) { if (!revs->ignore_missing_links) die("Failed to traverse parents of commit %s", diff --git a/revision.h b/revision.h index 2b30ac270d..fd4154ff75 100644 --- a/revision.h +++ b/revision.h @@ -56,6 +56,8 @@ struct rev_cmdline_info { #define REVISION_WALK_NO_WALK_SORTED 1 #define REVISION_WALK_NO_WALK_UNSORTED 2 +struct topo_walk_info; + struct rev_info { /* Starting list */ struct commit_list *commits; @@ -245,6 +247,8 @@ struct rev_info { const char *break_bar; struct revision_sources *sources; + + struct topo_walk_info *topo_walk_info; }; int ref_excluded(struct string_list *, const char *path); From patchwork Tue Sep 18 04:08:48 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603719 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id AC827913 for ; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 975942A1B5 for ; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 8BB9D2A1B4; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1FB1E2A1B4 for ; Tue, 18 Sep 2018 04:08:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729089AbeIRJja (ORCPT ); Tue, 18 Sep 2018 05:39:30 -0400 Received: from mail-pg1-f193.google.com ([209.85.215.193]:40816 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJja (ORCPT ); Tue, 18 Sep 2018 05:39:30 -0400 Received: by mail-pg1-f193.google.com with SMTP id l63-v6so330214pga.7 for ; Mon, 17 Sep 2018 21:08:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=L2kxBlA6o09grlg+pOFzgAWNVQtJaXzO8PzA/6R4CRI=; b=DksIvY9twLcidMw6iBw5vtKbDE6LG+2LpHpfBbJm2uPlOiwNHDh0WvvWdgB8n2YAuI yNjThWUc9T+DR8p/AGAUSOH4ldyAPiJYFuZ2GmLMDPpoAi0KPtaT3fCjUEIN+20hi4+f DJ1AY7uvtL5bhUVx2h56bQCKb7Jp0mb1uJtKSK5oBVSZkEkfuY3BC6advicC+UXCV38c Uu8prROaiaANV8baVtbc52gQSJNOX9yOxhF3TfRYHE9fpvgVgTqto7qz+74LYOaa/NBq UlP9uu47OCZarrjAAvjp4PhGQYNZgJNNVWu9DOssOJNKh+1dSNS23Hkm/ObUY8tYrZ0p Fi6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=L2kxBlA6o09grlg+pOFzgAWNVQtJaXzO8PzA/6R4CRI=; b=BYdHCTeY7JRYl1kui+ivq2rMhJjSk32fMl5/N8GTrpXjX65dsmmDa4rUMuPPJ7c56t tgJPeKHaKbx9W8B8UcBkK/Q+dEARXVJIOztK/fHN4VaemJZc+Xf+AgqaK+jJ4Gs6KP+J iljocgrlW3XpauE53C4vvoAzI2IVyHswQ7gvyQQvaYaxubI0fdS/1xTpohv2z0LbhLHS X2mSVqTfjgExpJ/3GjWcQBBeK1NHJRtaUMv89LP3zrKViteSoOxoIMTU2k5MNU8nylyY Xl35OoQ8Cn5FU0UHuJmBi/yOSH80c9uPNOF/ijiIym+mYzpBJNkUuTkfv8iWlXfv9ROq 4j/A== X-Gm-Message-State: APzg51D/FSnO4eisUz3BjVghKVHsb600+vT7ztdsW8c0ftS8RXkPToQ1 a3dt+TY9XcEyoMSye+XupV2LBJ1a X-Google-Smtp-Source: ANB0VdZS85XJCBkrlup9vR7P3KPRP77pghvdJdgmFRlcUjytHIBS0BaJwyPzoUdVP00V9rgGHVPOJA== X-Received: by 2002:a63:2043:: with SMTP id r3-v6mr25841227pgm.105.1537243729656; Mon, 17 Sep 2018 21:08:49 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id b73-v6sm25984691pfj.93.2018.09.17.21.08.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:48 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:48 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:38 GMT Message-Id: <0e64fc144cf4eb8b15c9e8453cf8af83330930e2.1537243720.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 5/6] commit/revisions: bookkeeping before refactoring Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee There are a few things that need to move around a little before making a big refactoring in the topo-order logic: 1. We need access to record_author_date() and compare_commits_by_author_date() in revision.c. These are used currently by sort_in_topological_order() in commit.c. 2. Moving these methods to commit.h requires adding the author_slab definition to commit.h. 3. The add_parents_to_list() method in revision.c performs logic around the UNINTERESTING flag and other special cases depending on the struct rev_info. Allow this method to ignore a NULL 'list' parameter, as we will not be populating the list for our walk. Signed-off-by: Derrick Stolee --- commit.c | 11 ++++------- commit.h | 8 ++++++++ revision.c | 6 ++++-- 3 files changed, 16 insertions(+), 9 deletions(-) diff --git a/commit.c b/commit.c index d0f199e122..f68e04b2f1 100644 --- a/commit.c +++ b/commit.c @@ -655,11 +655,8 @@ struct commit *pop_commit(struct commit_list **stack) /* count number of children that have not been emitted */ define_commit_slab(indegree_slab, int); -/* record author-date for each commit object */ -define_commit_slab(author_date_slab, timestamp_t); - -static void record_author_date(struct author_date_slab *author_date, - struct commit *commit) +void record_author_date(struct author_date_slab *author_date, + struct commit *commit) { const char *buffer = get_commit_buffer(commit, NULL); struct ident_split ident; @@ -684,8 +681,8 @@ fail_exit: unuse_commit_buffer(commit, buffer); } -static int compare_commits_by_author_date(const void *a_, const void *b_, - void *cb_data) +int compare_commits_by_author_date(const void *a_, const void *b_, + void *cb_data) { const struct commit *a = a_, *b = b_; struct author_date_slab *author_date = cb_data; diff --git a/commit.h b/commit.h index 2b1a734388..ff0eb5f8ef 100644 --- a/commit.h +++ b/commit.h @@ -8,6 +8,7 @@ #include "gpg-interface.h" #include "string-list.h" #include "pretty.h" +#include "commit-slab.h" #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF @@ -328,6 +329,13 @@ extern int remove_signature(struct strbuf *buf); */ extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc); +/* record author-date for each commit object */ +define_commit_slab(author_date_slab, timestamp_t); + +void record_author_date(struct author_date_slab *author_date, + struct commit *commit); + +int compare_commits_by_author_date(const void *a_, const void *b_, void *unused); int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused); int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused); diff --git a/revision.c b/revision.c index 2dcde8a8ac..92012d5f45 100644 --- a/revision.c +++ b/revision.c @@ -808,7 +808,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, if (p->object.flags & SEEN) continue; p->object.flags |= SEEN; - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + if (list) + commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); } return 0; } @@ -847,7 +848,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, p->object.flags |= left_flag; if (!(p->object.flags & SEEN)) { p->object.flags |= SEEN; - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + if (list) + commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); } if (revs->first_parent_only) break; From patchwork Tue Sep 18 04:08:50 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10603721 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 3CCAD913 for ; Tue, 18 Sep 2018 04:08:55 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2BA5F2A1B4 for ; Tue, 18 Sep 2018 04:08:55 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2045E2A1E8; Tue, 18 Sep 2018 04:08:55 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 220EF2A1B4 for ; Tue, 18 Sep 2018 04:08:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729127AbeIRJjc (ORCPT ); Tue, 18 Sep 2018 05:39:32 -0400 Received: from mail-pl1-f194.google.com ([209.85.214.194]:42495 "EHLO mail-pl1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726414AbeIRJjb (ORCPT ); Tue, 18 Sep 2018 05:39:31 -0400 Received: by mail-pl1-f194.google.com with SMTP id g23-v6so308117plq.9 for ; Mon, 17 Sep 2018 21:08:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=NVgdOCip1TxgsnZsyNZgcKy42zKeMl++TNUikvP0gLk=; b=kxdvnLPl7Jtaw+4r/ExJh9mQl5fgrM+cEUmSqDRnuNjGa2TA4GzuRAS61GU+C7ZsrW 58PA4uY37kLmoJwP7Cu29XzzRSrVLORaXi2dSwJG+LB6tuHY/5YWXu4Sbhm9mPoGXa3v 2aucV1YVXrCp9+yG1MnU6Lg426SB7WHHp79CdlGk4wVaFRiYQAMNLaHC/Q1T8Gt+qBRu wrdN3bT4XG4MA5JS7Fg2ElYqMZiu1nDSzJDH8YzK9fjJPZ5nPUnM0Z7Ipk2xpYr5Wqb0 VgHZ7xylwwfjzJqMsrRqO9Cu674/jS/Wyjj/2vUjAW3PhHDlG9ajHyPcPYzG6/t+2GPg PBiw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=NVgdOCip1TxgsnZsyNZgcKy42zKeMl++TNUikvP0gLk=; b=VpAiFdxsNPRAKMexqZzXTJqyDhmzGgbXNIQcpoQECrvZIIbiq/+KQmcV/mhQ96U05Q M2qPRzQ5/jbnLOO1JqMcsYm1Nfi+/t/UK7X/iVCNCZjDGsrxDanucJ5TMR8B1hv4sNF0 dGE6pDlqDzLmj9kS+uHPweDYK0gnr8FxGiuofJX97/Tbsw0jnOA3DBwOFaZHWoKwjUbo jEhwjCvxvmB/RifqzdEbNUwp3iQOAOxjRXf1tVDp+LnCXgOvcrCH5BMxzE83YH/VAjTU bPXv7PHe42vNT35RqCZnXLS1lxjg/Uhi+jFwJPjIjzCTPpbYH2iTZOi8QGub7xMnQzlR 5kTQ== X-Gm-Message-State: APzg51BJQg3g5Hs0shct3vFlF7NF+0aJfW6DknhmJm5l1SEMvCanBlbl UtcSvvkfcZqF8y65UvwJzBOfqf93 X-Google-Smtp-Source: ANB0VdakSPUO438wuJ8T8JX0XKsaz7UwUJq87dbXihGoGoAeFf7GJeC8RnJGyKeFlA2M2FZ7pNJGCg== X-Received: by 2002:a17:902:4201:: with SMTP id g1-v6mr27726206pld.203.1537243731136; Mon, 17 Sep 2018 21:08:51 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id q6-v6sm19928278pgq.19.2018.09.17.21.08.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Sep 2018 21:08:50 -0700 (PDT) Date: Mon, 17 Sep 2018 21:08:50 -0700 (PDT) X-Google-Original-Date: Tue, 18 Sep 2018 04:08:39 GMT Message-Id: <3b185ac3b1cd54e0ffee8e5b42cc0ea3d1fac3c7.1537243720.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 6/6] revision.c: refactor basic topo-order logic Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee When running a command like 'git rev-list --topo-order HEAD', Git performed the following steps: 1. Run limit_list(), which parses all reachable commits, adds them to a linked list, and distributes UNINTERESTING flags. If all unprocessed commits are UNINTERESTING, then it may terminate without walking all reachable commits. This does not occur if we do not specify UNINTERESTING commits. 2. Run sort_in_topological_order(), which is an implementation of Kahn's algorithm. It first iterates through the entire set of important commits and computes the in-degree of each (plus one, as we use 'zero' as a special value here). Then, we walk the commits in priority order, adding them to the priority queue if and only if their in-degree is one. As we remove commits from this priority queue, we decrement the in-degree of their parents. 3. While we are peeling commits for output, get_revision_1() uses pop_commit on the full list of commits computed by sort_in_topological_order(). In the new algorithm, these three steps correspond to three different commit walks. We run these walks simultaneously, and advance each only as far as necessary to satisfy the requirements of the 'higher order' walk. We know when we can pause each walk by using generation numbers from the commit- graph feature. Recall that the generation number of a commit satisfies: * If the commit has at least one parent, then the generation number is one more than the maximum generation number among its parents. * If the commit has no parent, then the generation number is one. There are two special generation numbers: * GENERATION_NUMBER_INFINITY: this value is 0xffffffff and indicates that the commit is not stored in the commit-graph and the generation number was not previously calculated. * GENERATION_NUMBER_ZERO: this value (0) is a special indicator to say that the commit-graph was generated by a version of Git that does not compute generation numbers (such as v2.18.0). Since we use generation_numbers_enabled() before using the new algorithm, we do not need to worry about GENERATION_NUMBER_ZERO. However, the existence of GENERATION_NUMBER_INFINITY implies the following weaker statement than the usual we expect from generation numbers: If A and B are commits with generation numbers gen(A) and gen(B) and gen(A) < gen(B), then A cannot reach B. Thus, we will walk in each of our stages until the "maximum unexpanded generation number" is strictly lower than the generation number of a commit we are about to use. The walks are as follows: 1. EXPLORE: using the explore_queue priority queue (ordered by maximizing the generation number), parse each reachable commit until all commits in the queue have generation number strictly lower than needed. During this walk, update the UNINTERESTING flags as necessary. 2. INDEGREE: using the indegree_queue priority queue (ordered by maximizing the generation number), add one to the in- degree of each parent for each commit that is walked. Since we walk in order of decreasing generation number, we know that discovering an in-degree value of 0 means the value for that commit was not initialized, so should be initialized to two. (Recall that in-degree value "1" is what we use to say a commit is ready for output.) As we iterate the parents of a commit during this walk, ensure the EXPLORE walk has walked beyond their generation numbers. 3. TOPO: using the topo_queue priority queue (ordered based on the sort_order given, which could be commit-date, author- date, or typical topo-order which treats the queue as a LIFO stack), remove a commit from the queue and decrement the in-degree of each parent. If a parent has an in-degree of one, then we add it to the topo_queue. Before we decrement the in-degree, however, ensure the INDEGREE walk has walked beyond that generation number. The implementations of these walks are in the following methods: * explore_walk_step and explore_to_depth * indegree_walk_step and compute_indegrees_to_depth * next_topo_commit and expand_topo_walk These methods have some patterns that may seem strange at first, but they are probably carry-overs from their equivalents in limit_list and sort_in_topological_order. One thing that is missing from this implementation is a proper way to stop walking when the entire queue is UNINTERESTING, so this implementation is not enabled by comparisions, such as in 'git rev-list --topo-order A..B'. This can be updated in the future. In my local testing, I used the following Git commands on the Linux repository in three modes: HEAD~1 with no commit-graph, HEAD~1 with a commit-graph, and HEAD with a commit-graph. This allows comparing the benefits we get from parsing commits from the commit-graph and then again the benefits we get by restricting the set of commits we walk. Test: git rev-list --topo-order -100 HEAD HEAD~1, no commit-graph: 6.80 s HEAD~1, w/ commit-graph: 0.77 s HEAD, w/ commit-graph: 0.02 s Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s HEAD~1, w/ commit-graph: 6.06 s HEAD, w/ commit-graph: 0.06 s This speedup is due to a few things. First, the new generation- number-enabled algorithm walks commits on order of the number of results output (subject to some branching structure expectations). Since we limit to 100 results, we are running a query similar to filling a single page of results. Second, when specifying a path, we must parse the root tree object for each commit we walk. The previous benefits from the commit-graph are entirely from reading the commit-graph instead of parsing commits. Since we need to parse trees for the same number of commits as before, we slow down significantly from the non-path-based query. For the test above, I specifically selected a path that is changed frequently, including by merge commits. A less-frequently-changed path (such as 'README') has similar end-to-end time since we need to walk the same number of commits (before determining we do not have 100 hits). However, get get the benefit that the output is presented to the user as it is discovered, much the same as a normal 'git log' command (no '--topo-order'). This is an improved user experience, even if the command has the same runtime. Signed-off-by: Derrick Stolee --- object.h | 4 +- revision.c | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++-- revision.h | 2 + 3 files changed, 194 insertions(+), 8 deletions(-) diff --git a/object.h b/object.h index 0feb90ae61..796792cb32 100644 --- a/object.h +++ b/object.h @@ -59,7 +59,7 @@ struct object_array { /* * object flag allocation: - * revision.h: 0---------10 2526 + * revision.h: 0---------10 25----28 * fetch-pack.c: 01 * negotiator/default.c: 2--5 * walker.c: 0-2 @@ -78,7 +78,7 @@ struct object_array { * builtin/show-branch.c: 0-------------------------------------------26 * builtin/unpack-objects.c: 2021 */ -#define FLAG_BITS 27 +#define FLAG_BITS 29 /* * The object type is stored in 3 bits. diff --git a/revision.c b/revision.c index 92012d5f45..c5d0cb6599 100644 --- a/revision.c +++ b/revision.c @@ -26,6 +26,7 @@ #include "argv-array.h" #include "commit-reach.h" #include "commit-graph.h" +#include "prio-queue.h" volatile show_early_output_fn_t show_early_output; @@ -2895,30 +2896,213 @@ static int mark_uninteresting(const struct object_id *oid, return 0; } -struct topo_walk_info {}; +define_commit_slab(indegree_slab, int); + +struct topo_walk_info { + uint32_t min_generation; + struct prio_queue explore_queue; + struct prio_queue indegree_queue; + struct prio_queue topo_queue; + struct indegree_slab indegree; + struct author_date_slab author_date; +}; + +static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag) +{ + if (c->object.flags & flag) + return; + + c->object.flags |= flag; + prio_queue_put(q, c); +} + +static void explore_walk_step(struct rev_info *revs) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit_list *p; + struct commit *c = prio_queue_get(&info->explore_queue); + + if (!c) + return; + + if (parse_commit_gently(c, 1) < 0) + return; + + if (revs->max_age != -1 && (c->date < revs->max_age)) + c->object.flags |= UNINTERESTING; + + if (add_parents_to_list(revs, c, NULL, NULL) < 0) + return; + + if (c->object.flags & UNINTERESTING) + mark_parents_uninteresting(c); + + for (p = c->parents; p; p = p->next) + test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED); +} + +static void explore_to_depth(struct rev_info *revs, + uint32_t gen) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->explore_queue)) && + c->generation >= gen) + explore_walk_step(revs); +} + +static void indegree_walk_step(struct rev_info *revs) +{ + struct commit_list *p; + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c = prio_queue_get(&info->indegree_queue); + + if (!c) + return; + + if (parse_commit_gently(c, 1) < 0) + return; + + explore_to_depth(revs, c->generation); + + if (parse_commit_gently(c, 1) < 0) + return; + + for (p = c->parents; p; p = p->next) { + struct commit *parent = p->item; + int *pi = indegree_slab_at(&info->indegree, parent); + + if (*pi) + (*pi)++; + else + *pi = 2; + + test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE); + + if (revs->first_parent_only) + return; + } +} + +static void compute_indegrees_to_depth(struct rev_info *revs) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->indegree_queue)) && + c->generation >= info->min_generation) + indegree_walk_step(revs); +} static void init_topo_walk(struct rev_info *revs) { struct topo_walk_info *info; + struct commit_list *list; revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info)); info = revs->topo_walk_info; memset(info, 0, sizeof(struct topo_walk_info)); - limit_list(revs); - sort_in_topological_order(&revs->commits, revs->sort_order); + init_indegree_slab(&info->indegree); + memset(&info->explore_queue, '\0', sizeof(info->explore_queue)); + memset(&info->indegree_queue, '\0', sizeof(info->indegree_queue)); + memset(&info->topo_queue, '\0', sizeof(info->topo_queue)); + + switch (revs->sort_order) { + default: /* REV_SORT_IN_GRAPH_ORDER */ + info->topo_queue.compare = NULL; + break; + case REV_SORT_BY_COMMIT_DATE: + info->topo_queue.compare = compare_commits_by_commit_date; + break; + case REV_SORT_BY_AUTHOR_DATE: + init_author_date_slab(&info->author_date); + info->topo_queue.compare = compare_commits_by_author_date; + info->topo_queue.cb_data = &info->author_date; + break; + } + + info->explore_queue.compare = compare_commits_by_gen_then_commit_date; + info->indegree_queue.compare = compare_commits_by_gen_then_commit_date; + + info->min_generation = GENERATION_NUMBER_INFINITY; + for (list = revs->commits; list; list = list->next) { + struct commit *c = list->item; + test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED); + test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE); + + if (parse_commit_gently(c, 1)) + continue; + if (c->generation < info->min_generation) + info->min_generation = c->generation; + } + + for (list = revs->commits; list; list = list->next) { + struct commit *c = list->item; + *(indegree_slab_at(&info->indegree, c)) = 1; + + if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE) + record_author_date(&info->author_date, c); + } + compute_indegrees_to_depth(revs); + + for (list = revs->commits; list; list = list->next) { + struct commit *c = list->item; + + if (*(indegree_slab_at(&info->indegree, c)) == 1) + prio_queue_put(&info->topo_queue, c); + } + + /* + * This is unfortunate; the initial tips need to be shown + * in the order given from the revision traversal machinery. + */ + if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER) + prio_queue_reverse(&info->topo_queue); } static struct commit *next_topo_commit(struct rev_info *revs) { - return pop_commit(&revs->commits); + struct commit *c; + struct topo_walk_info *info = revs->topo_walk_info; + + /* pop next off of topo_queue */ + c = prio_queue_get(&info->topo_queue); + + if (c) + *(indegree_slab_at(&info->indegree, c)) = 0; + + return c; } static void expand_topo_walk(struct rev_info *revs, struct commit *commit) { - if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) { + struct commit_list *p; + struct topo_walk_info *info = revs->topo_walk_info; + if (add_parents_to_list(revs, commit, NULL, NULL) < 0) { if (!revs->ignore_missing_links) die("Failed to traverse parents of commit %s", - oid_to_hex(&commit->object.oid)); + oid_to_hex(&commit->object.oid)); + } + + for (p = commit->parents; p; p = p->next) { + struct commit *parent = p->item; + int *pi; + + if (parse_commit_gently(parent, 1) < 0) + continue; + + if (parent->generation < info->min_generation) { + info->min_generation = parent->generation; + compute_indegrees_to_depth(revs); + } + + pi = indegree_slab_at(&info->indegree, parent); + + (*pi)--; + if (*pi == 1) + prio_queue_put(&info->topo_queue, parent); + + if (revs->first_parent_only) + return; } } diff --git a/revision.h b/revision.h index fd4154ff75..b20c16c0e0 100644 --- a/revision.h +++ b/revision.h @@ -24,6 +24,8 @@ #define USER_GIVEN (1u<<25) /* given directly by the user */ #define TRACK_LINEAR (1u<<26) #define ALL_REV_FLAGS (((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR) +#define TOPO_WALK_EXPLORED (1u<<27) +#define TOPO_WALK_INDEGREE (1u<<28) #define DECORATE_SHORT_REFS 1 #define DECORATE_FULL_REFS 2