From patchwork Fri Sep 21 17:39:27 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: 10610771 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 65EA6157B for ; Fri, 21 Sep 2018 17:39:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4DE052DF44 for ; Fri, 21 Sep 2018 17:39:33 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 424652DF7C; Fri, 21 Sep 2018 17:39:33 +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 8D3822DF57 for ; Fri, 21 Sep 2018 17:39:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390951AbeIUX3Y (ORCPT ); Fri, 21 Sep 2018 19:29:24 -0400 Received: from mail-pf1-f195.google.com ([209.85.210.195]:42866 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX3Y (ORCPT ); Fri, 21 Sep 2018 19:29:24 -0400 Received: by mail-pf1-f195.google.com with SMTP id l9-v6so6279835pff.9 for ; Fri, 21 Sep 2018 10:39:29 -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=fffD5Qzw0WxT3iO60Dd0heV4oNYmEuOHYETqwtREmTcGZSSs4QypkoDynMqhstUNvV qERWgDhUWtW7nHx3wRYx1karMNmAfFMB7u+Cf7ekI8JdSU2TiMp1apmU9TFO2pKJ6fnm w8VQU8vzoW0XNY8xcEv5utxqeDBnmopfKPEknvus8P+EdiyydTimmd0Xn5/rvxFI9GgC ioZ15fC6xyVgdyuzWEpz5qF5f2tMUUjF5VqaGgFexYVVK6onxxDaehORx6UnAgzfCI1Q 6E2ce5FtbYi/PW8JHPoZuOHQN4icTm/JCTZZz4COPAf4qcAFp65/dZlBf41FD6YoSzj7 EhIQ== 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=knwgQ3OiDYVYhCiPxYhU6MTtCTktfNmIXWhTCqPCHjPVD0HmzDsvJYL7MEfCBlmg2L y0QykueCYPo+s0l2lE6wnvUKtgGfqy+SnlcBUOOtsbQEfaIp4IMUfnMDuSLu2pF+XjJ2 pwEwJqNYFj2Ys2q5niWflu8Gc70BpL//55X+EN7IerSxYksu+CsqWOjv78RwWABzUU6X 1XlaTn5KiOGASfYEpX7r7ykirbJwNXPR2fziMvm05us45cBim8/nBnKFvmAzlXVpi21u 2/N3ft6kAimxp89XEgVVbqXkqT9vL2rAM2JKf21FyOMNW/MkIo/E41n+IjppuBhUadUH h3WQ== X-Gm-Message-State: APzg51AGe+2ApUpGctnfuzwTqjNvCgVkmRY1lFE8/hNwB8dDOJd2/Tm0 f3Own9/4BwkAfc6nvRAGYwOenl/j X-Google-Smtp-Source: ANB0VdaYA8+sczhnNalFT8klLNMaxe4/QOtqEEWKVfMt7gFy5xqIRlXax3Ld5l9ZLAP2/qADHOTJpg== X-Received: by 2002:a63:ef4f:: with SMTP id c15-v6mr41828645pgk.368.1537551568667; Fri, 21 Sep 2018 10:39:28 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id h85-v6sm43338668pfk.71.2018.09.21.10.39.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:27 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:27 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:17 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 1/7] prio-queue: add 'peek' operation Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 Fri Sep 21 17:39:29 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: 10610769 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 2E6931709 for ; Fri, 21 Sep 2018 17:39:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 16B5F2DF44 for ; Fri, 21 Sep 2018 17:39:33 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0A1572E36B; Fri, 21 Sep 2018 17:39:33 +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 A77092DF44 for ; Fri, 21 Sep 2018 17:39:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390960AbeIUX30 (ORCPT ); Fri, 21 Sep 2018 19:29:26 -0400 Received: from mail-pl1-f196.google.com ([209.85.214.196]:34947 "EHLO mail-pl1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX3Z (ORCPT ); Fri, 21 Sep 2018 19:29:25 -0400 Received: by mail-pl1-f196.google.com with SMTP id g2-v6so6267192plo.2 for ; Fri, 21 Sep 2018 10:39:30 -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=DIlKSMnygAmhqJbkFGN9kloLOOTraPA2YoTYIEIHZic=; b=T7BOP77yxqbO8IkY+mOJ6GHHYKLzDDzVPq+m32rV7I+PzaPCjXaSLi+K8CWOGIevz+ 03uWNACCyccis8HcFMvpp3fPpzwQ/lr026o0rZqKfaxbAAxkipromp6qC0eN6zsMRXdE /HIemhuOefb/E0bs9ze1/tCvrhFWu8U5W53VBG2c/Qn0BzS9hCmVg+psTexKCLRTZKeH PUJorGtrJ+SpG2QfddODDIO+P8AcU+kgXiR8VhHFz7VXH6BieV1J+0/q6DpbeUuhVv1l eC6RAPXYR/zkvF4zNjRg5FDYPbnUYV3yVnMGt2CtBiUbpsdF3IS5TUELKbPF/m5t3ks9 ELgg== 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=DIlKSMnygAmhqJbkFGN9kloLOOTraPA2YoTYIEIHZic=; b=GUr5oyYgvyNwcYWiiJZLIjMCEDCMzA58/CfqN3mkPqV5hggJ23SER8UJl+0+N/5H6e A9LZYwBTAfqTJlR5BqLmlpxF4BhsJTqkxhkf3FOcNmSZgp5L0uKVyzO6AcnTMyEZfXf7 7bUd4SQ6qWsHmBtZY0VOleI4y/BTRpfZiD4j19iQ2DYHNQx314c2rpYynI9eGMYefeHM 3uI51pBxhfYXqAD2dJwpz8QNyYB9CrFH6WxZJ2zfpZemCwmFT4chg5gCgeUYyyW1/1E7 XVF/NqaPtcR4yz9tBVdEIfLSInGG/gMmIWnwYQVe3hExTu+Hgnqk6F0+Y3Tb2D9w1R9D WWpA== X-Gm-Message-State: APzg51AfASyHMT8aSWUZR2mTnAeK4XexPpIVLAN7vyBqa+ijd34cuYZt 9PS7Rffr5SJiwiHZaIenoGCJAdWe X-Google-Smtp-Source: ANB0VdY+0nYv3ENjir2PlAVH4rsBMWqemMrzRL960ltsIRncVLFdWnQ6rmSsO/aOQL2L4iP6w0ARrA== X-Received: by 2002:a17:902:ac86:: with SMTP id h6-v6mr8209308plr.103.1537551570061; Fri, 21 Sep 2018 10:39:30 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id j15-v6sm33175540pfn.52.2018.09.21.10.39.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:29 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:29 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:18 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 2/7] test-reach: add run_three_modes method Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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. Signed-off-by: Derrick Stolee --- t/t6600-test-reach.sh | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index d139a00d1d..9d65b8b946 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 && + "$@" actual && test_cmp expect actual && cp commit-graph-full .git/objects/info/commit-graph && - test-tool reach $1 actual && + "$@" actual && test_cmp expect actual && cp commit-graph-half .git/objects/info/commit-graph && - test-tool reach $1 actual && + "$@" actual && test_cmp expect actual } +test_three_modes () { + run_three_modes test-tool reach "$@" +} + test_expect_success 'ref_newer:miss' ' cat >input <<-\EOF && A:commit-5-7 From patchwork Fri Sep 21 17:39:30 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: 10610773 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 A7689157B for ; Fri, 21 Sep 2018 17:39:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8AAC12DF44 for ; Fri, 21 Sep 2018 17:39:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7F4DB2DF7C; Fri, 21 Sep 2018 17:39:34 +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 0FF1A2DF44 for ; Fri, 21 Sep 2018 17:39:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390996AbeIUX31 (ORCPT ); Fri, 21 Sep 2018 19:29:27 -0400 Received: from mail-pf1-f193.google.com ([209.85.210.193]:33854 "EHLO mail-pf1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX31 (ORCPT ); Fri, 21 Sep 2018 19:29:27 -0400 Received: by mail-pf1-f193.google.com with SMTP id k19-v6so6296125pfi.1 for ; Fri, 21 Sep 2018 10:39:32 -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=y1zQlUARm7GbYNl3NtJpUgMhk/cSFyvMqeULyUEQfWc=; b=QS/a03rovOdifrL/63HAdJlWFIHn50te8ZSNWBDKkc8DY09nB38NRcjo4NRQC//STG x+f4Y6yQVn3KkwxSAXXRp5/Nb78ws/QSZkwEcyImSQ4HVrlL/TUk8z96sNf+GKrgVcu9 itOk5h/+QuL9uw0ZmTrE2OBRitEImRZrV/+H0yELpoMs9ItC+R0NC4blK2IaZ5DM5aND W0LuclJ+Q5kykgnYlzXRNcA45cnNGfqt58E0HXRF+9hoWI97vFsxC89e27USGLTkRFPx 5c1ORDIbwt0MQCp4bAiJGQGfXInPxYyu2qWkLDi7EJY8DarQYt54ADiOxyIFMlblsFyn 2XqA== 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=y1zQlUARm7GbYNl3NtJpUgMhk/cSFyvMqeULyUEQfWc=; b=WFAwQD8ch1OhBLAk0JABzx8ubEQ9ZHHvuypU8WcZ2t3yTlb3H0jYR8rrnRs+esonf8 yDm5fXOIRtILTtO5AKQ7vAgcGbi3c6bflgHcG2LnG6MhNX4R/8s/WP0rF/9f+5k6q/ZK 0fAEjsQgOdzSdDKnpl1Guf/3koe6zXv2bJIgr7/xONOD/pseLnW7M4yhSVKPuQmirCGJ h87Tv4lgPzyr3E9stR5BJRJn5KAS52WSGtM6VqOWe11LnTYetwGnsg8DByB70usGj0Nz QXT56sJq6BBlajhvfG5TQjNUjuYe+hLv1Mwyp2iVHSpgp1yXOJEvBeqKzZDbdqSVBMP/ DXgw== X-Gm-Message-State: APzg51CKwazS7urTrzMvgQdI6qAH2KAH+0dMenvJUNPGSKQ8WhcD/U2m p3HbvA+94jF0icmO8n6wtdoOqSeH X-Google-Smtp-Source: ANB0VdYMott/62hhsee27mcSJ2Ja9r0gLRLdrCYCb6sYxsvSUnWGX4eIga30MOZlFEp808scLzo1XA== X-Received: by 2002:a63:4f64:: with SMTP id p36-v6mr41222686pgl.210.1537551571490; Fri, 21 Sep 2018 10:39:31 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id e73-v6sm54878514pfb.153.2018.09.21.10.39.30 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:30 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:30 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:19 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 3/7] test-reach: add rev-list tests Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 9d65b8b946..288f703b7b 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 Fri Sep 21 17:39:32 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: 10610775 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 B8FAF157B for ; Fri, 21 Sep 2018 17:39:36 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9FA782DF57 for ; Fri, 21 Sep 2018 17:39:36 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 941892DF7C; Fri, 21 Sep 2018 17:39:36 +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 02D832DF44 for ; Fri, 21 Sep 2018 17:39:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391010AbeIUX32 (ORCPT ); Fri, 21 Sep 2018 19:29:28 -0400 Received: from mail-pg1-f194.google.com ([209.85.215.194]:35211 "EHLO mail-pg1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX32 (ORCPT ); Fri, 21 Sep 2018 19:29:28 -0400 Received: by mail-pg1-f194.google.com with SMTP id 205-v6so5423122pgd.2 for ; Fri, 21 Sep 2018 10:39:33 -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=L4qmnI1hA11rtu7I8rno84o5UJKl+YVKqLoli9C7ErUQMuZq/7VqlnMPSE2iCSHNtQ CX2R683gc/cCq6VR4g29paWv9m2LTyM4bi3IcU3PE0jn41xmcQFhmlloXOwErtGBIMgT kicmQBhiylFL5SOm9jzlbbIw/HiS8HHEkVL8xSdWzLLnMDsJS8hPBIcJtsWb5zeZe6Qv Txgo0C35jwj8zkKTeM7Tu3G2DAIJMHZr70scQ1OoCqs2amDMs9dF6K/A4GlbW9FvJ+XP C/h58SYAf2ACXEnXt9bFkHjC6TA2PPjQVBJuMqynoy3W7nqq4UZCbNsEoDqlKJWwA2aD xq7w== 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=Cs+g+hKtNDyWskG4MjEqvy8itathXUheMaR9A9sv4I7E4vVaOkeGqLi6NEYBi4AnaW Xv2YckrsciC7WHr/1Y/fgvsCTi88i5MjWDmOfQ4motQY/eHSHF1x/7D6lNz5/Bx0aXBw H0hUomuGKDIGFimOHIcE8ZywP3I7G/mSUk7FnpgocaC5PtLqd/hsgvY/i5L8WZ8ZWcaW rxObxFTrFaGXG2gox5RojwS626nL326nvyYxLoGzINxiNPlpUTrOw67kuTSDcYflnV4c 7mUfV9EPj5XsWBW5qCEFVoWKvYI2aouEfLRZaqSH5Pi5gyp6TFx2v7OPVJPG99NqCKdy 3oEA== X-Gm-Message-State: APzg51AO6FmT265/g8i5V7/1qR2s8QMbs95P3pYaz6egtp7Cy6eMdf7Y l+RGkxRoyPD+xxruEqYFKNR3l8F4 X-Google-Smtp-Source: ANB0Vda6bdKYN+GiPilTDM0rcrrjXRgqD6Jw+tdVDkAwpt2xyWvSBD6DmOvPXZ1uRfoZR9vKeF39Qw== X-Received: by 2002:a63:68c7:: with SMTP id d190-v6mr9540223pgc.135.1537551572924; Fri, 21 Sep 2018 10:39:32 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id r17-v6sm44809823pff.50.2018.09.21.10.39.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:32 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:32 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:20 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 4/7] revision.c: begin refactoring --topo-order logic Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 Fri Sep 21 17:39:33 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: 10610777 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 357531709 for ; Fri, 21 Sep 2018 17:39:37 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1D4C22DF44 for ; Fri, 21 Sep 2018 17:39:37 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 11B462DF7C; Fri, 21 Sep 2018 17:39:37 +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 9A5942DF44 for ; Fri, 21 Sep 2018 17:39:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391024AbeIUX33 (ORCPT ); Fri, 21 Sep 2018 19:29:29 -0400 Received: from mail-pf1-f196.google.com ([209.85.210.196]:43479 "EHLO mail-pf1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX33 (ORCPT ); Fri, 21 Sep 2018 19:29:29 -0400 Received: by mail-pf1-f196.google.com with SMTP id j26-v6so6277206pfi.10 for ; Fri, 21 Sep 2018 10:39:35 -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=UrPhzdRE1FAbBlh/RWIyAHF0klCBbvz/dTajPqF5Y2sD037bWGzr1go6ZdFt/j4fBK SNs1v0J/UMv2G4zcVcOGqh+P1be8Hw8Awj3ZFMURSCbXOspmb7diLu9KqYRFO0YZAiBM yZIKHUx1rEJRneS1NLslQaf5ozWRU+NTtauuG4aAgf/FNGOxBSLLmiqoAXsUjWPInFLf XkjCpkemRhqfJZixhA3Y1+b/rQ/2awELGRhEURJpNNJeCTD4N8tRdjTRQuWa/5chuK/1 A0EmxDsB+ieWZDsu8GPkGomWTC/RtDokDgZeOyW7iW22EoAuhYwnQzCWYyuVspZUNp0e MlnQ== 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=oKGt7by6gwS6tXAkSQB1XXaGShbQVgAx2u3HvRyEgjTosu9ZeURrlNWyTvNctATufZ P2RUdr3a1TZZ7RgLJbV5efKjOpA01c1osgz6rZXJBtakpCUqmQlnLdIpxL/LHvLYU5qN qa4cTOw/gn/YiiHOinAzVqgBnXbyUFX0JasR2JozxozCrXFsdnBfeCKElthUw/+Ca19S ynN9RntuYy+sZs15DJnBjrqoDyZZ/+DDu0jMA2ecOxBfHyNqtl/yRj72LZhYlsf+S2zG 72M4Uk536/aYYhCYNXWNCAjRL19Dc/gQCq5in6ThUJf1BKZNBJMNpwP13rmzejq/14U5 TKyA== X-Gm-Message-State: APzg51Db9Bus9lEt+tIXqW/UfexbzF7g9VF/AOXaB++UpUIDi0QRLJem GSgVUsqldeNSRDKX8R7hrMhyLDkN X-Google-Smtp-Source: ANB0VdbQf2ApF1aCgUMQ6SOz2ifVf7bZ/GQ39RuFvp1zBqvPaC8MJr6Fbgno9W6WAaWVHtMRZlu4UQ== X-Received: by 2002:a63:5558:: with SMTP id f24-v6mr13917234pgm.37.1537551574451; Fri, 21 Sep 2018 10:39:34 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id l85-v6sm48035392pfk.34.2018.09.21.10.39.33 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:33 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:33 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:21 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 5/7] commit/revisions: bookkeeping before refactoring Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 Fri Sep 21 17:39:35 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: 10610779 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 58124157B for ; Fri, 21 Sep 2018 17:39:38 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 40F4C2DF44 for ; Fri, 21 Sep 2018 17:39:38 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 358BC2DF7C; Fri, 21 Sep 2018 17:39:38 +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 CF1222DF44 for ; Fri, 21 Sep 2018 17:39:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391030AbeIUX3b (ORCPT ); Fri, 21 Sep 2018 19:29:31 -0400 Received: from mail-pf1-f175.google.com ([209.85.210.175]:39221 "EHLO mail-pf1-f175.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2391025AbeIUX3b (ORCPT ); Fri, 21 Sep 2018 19:29:31 -0400 Received: by mail-pf1-f175.google.com with SMTP id j8-v6so6284839pff.6 for ; Fri, 21 Sep 2018 10:39:36 -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=BZOhhE9AML81OMes14sxjPPAo+VYQQgTwCbQcYv1DFI=; b=OJD4MUc7VVdNxYEAdsDU3IBjVWK36TFUu6OqXMVNugiTvcT/uaEdGLfd9aZLhQBIlN 9aPKnDJ/7tRpnomSzO9RGgX9WJRJwGQmVGYi+5FYogAkq8qjlGWdyVorGJvYa9E2ra0B kRVqnMbW3dJJq4QoiiA4xFfhDw+hPzUMDjzgA49nqr+Qoxv0xUQKCW5mTGuGF0U0Tfma WrfeSfh0NWHBKjhL2j0CKtJP4PETICmRzAm03c9qGddwXEuFGz/SXzKOUJeRUwYRvulU eqcIZiIz0J2GD64bw466jQci0bDabBbGwcx055GkUU/qGrHc0J67TO2oOoB3+sSzsLoV Eb6w== 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=BZOhhE9AML81OMes14sxjPPAo+VYQQgTwCbQcYv1DFI=; b=GhPZgGZFsM/RgqvS5Y5Mej1DLp92kKbRBt21bwbS+IRfmATSqswe/o7nbZ1qxyV2NP Ch1dDnfoYlpmr4sooLN8TiDZh1C6DNIemDUEKmySp9otaijKDnUsHp8xUjvNM87EqlK4 KtsCnXRjqpw6mCgJtamW6tQ9KejIMm6rd6hHVorBdb0x2QfTyPnhAGq2LM4KD7M+EuC5 dcBD7b+Ih73Vd7vMom/7EPIPVt9Y1DDkMb7jC6XIwgIxEhtuZmSsSLg2tn8NBdLz2WPB Bm0w5WqY9fWBfLfH/0118dG3N0WZgAWAthhc5GGnmfqyHQ8DMTPfVjPNXMIlUmKloCts dOCA== X-Gm-Message-State: APzg51D6HbRr9gQwuMjRqqSEnlCkDFtTTFfAbVnIJ7l5eyyYahs3h2yj tArB5jYJimoshobFTtQU6JjEYXgX X-Google-Smtp-Source: ANB0VdZPWjWOE1c/8D8GjxzqGWUnkFk+XlZv7h834Vi5RQ64Kvp5v2FzMah03nns8eepu9hIkFZUOw== X-Received: by 2002:a62:1544:: with SMTP id 65-v6mr47162672pfv.178.1537551575981; Fri, 21 Sep 2018 10:39:35 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id p4-v6sm38384838pfb.180.2018.09.21.10.39.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:35 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:35 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:22 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 6/7] revision.h: add whitespace in flag definitions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 In anticipation of adding longer flag names in the next change, add an extra tab to each flag definition in revision.h. Signed-off-by: Derrick Stolee --- revision.h | 28 ++++++++++++++-------------- 1 file changed, 14 insertions(+), 14 deletions(-) diff --git a/revision.h b/revision.h index fd4154ff75..e7bd059d80 100644 --- a/revision.h +++ b/revision.h @@ -10,20 +10,20 @@ #include "commit-slab-decl.h" /* Remember to update object flag allocation in object.h */ -#define SEEN (1u<<0) -#define UNINTERESTING (1u<<1) -#define TREESAME (1u<<2) -#define SHOWN (1u<<3) -#define TMP_MARK (1u<<4) /* for isolated cases; clean after use */ -#define BOUNDARY (1u<<5) -#define CHILD_SHOWN (1u<<6) -#define ADDED (1u<<7) /* Parents already parsed and added? */ -#define SYMMETRIC_LEFT (1u<<8) -#define PATCHSAME (1u<<9) -#define BOTTOM (1u<<10) -#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 SEEN (1u<<0) +#define UNINTERESTING (1u<<1) +#define TREESAME (1u<<2) +#define SHOWN (1u<<3) +#define TMP_MARK (1u<<4) /* for isolated cases; clean after use */ +#define BOUNDARY (1u<<5) +#define CHILD_SHOWN (1u<<6) +#define ADDED (1u<<7) /* Parents already parsed and added? */ +#define SYMMETRIC_LEFT (1u<<8) +#define PATCHSAME (1u<<9) +#define BOTTOM (1u<<10) +#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 DECORATE_SHORT_REFS 1 #define DECORATE_FULL_REFS 2 From patchwork Fri Sep 21 17:39:36 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: 10610781 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 CFF551709 for ; Fri, 21 Sep 2018 17:39:42 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B4E772DF44 for ; Fri, 21 Sep 2018 17:39:42 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A9BFA2DF7C; Fri, 21 Sep 2018 17:39:42 +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 9FF422DF44 for ; Fri, 21 Sep 2018 17:39:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391036AbeIUX3e (ORCPT ); Fri, 21 Sep 2018 19:29:34 -0400 Received: from mail-pg1-f195.google.com ([209.85.215.195]:41428 "EHLO mail-pg1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2389545AbeIUX3e (ORCPT ); Fri, 21 Sep 2018 19:29:34 -0400 Received: by mail-pg1-f195.google.com with SMTP id z3-v6so1396831pgv.8 for ; Fri, 21 Sep 2018 10:39:38 -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=GzbRe1o65QFkhy0oJ9wrkH2k6Fmm4QvLDYlydFe+pmw=; b=qjBhfVpyeaaxCpZdk2gk2jbvHanUNFjHsPv1jfvLpNQwcwmz1RdPTw14Dj0EOWBFTu EhaLHx2pEnujwXb1lWpdQvI1ilPRjNUDQYu5Z9nXU7V2RW8JQywRf0dGe/9T8kFs5wRC ulSCXDeGPGg7GhKJJo9bhjbUiS2zhvQfUnu/KOU9yN7nkhUUwI7v5hvc8Dn+A+vKM6Lr PGppRkIL5rsqfw5FKpYb379Oc+sPHaacH0qnTM3OS7vFrLf7AiUEP0/AWMW9zLiEQXix G7M57X8OuSGbnxgPgYik5gOP/IVTnQJm27KUpiLE5pZim5qtt1S6/YN3YrFsUlngRQBH dbDQ== 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=GzbRe1o65QFkhy0oJ9wrkH2k6Fmm4QvLDYlydFe+pmw=; b=Lh6bKqnUAcsU9gno57JTxbNNFPJro4PKvRRNHDLEpo3w9jvczhzchh1DKPxKD4GNcn qg+SImBYylazFdrvCVPbmPxanqBnZN8ts0U6IH909QpJo5oy3C1SMj9HmZxCtFmqENYb pJY1AwZSKssz6usdUE1JJHnDiBqpy05upzbV6BM0WWh5+hXsmb1U6wdYhc4Yt2CULkkh uhJw2N2fVXcUrbS956iPE7SxaE1mt4S6FTXXQchVcjv9H+B6vtC5IDAaEFtD+F3/Tvz3 iLCmp8paF8Nw0IplV3OCi+r8xHr0fGEa/drVjehmscuw38cuAZFRZX3YVsQ7N0k7ClpF YKmg== X-Gm-Message-State: APzg51CRTLrY5QB5RYDn/DTS8XSB4dfuuDKAxJGmeD8nLbblGcEpypso w51HFvsojEOXANpcW+1zMl3o1doU X-Google-Smtp-Source: ANB0VdZKzqodizoNjp3+0ZJiPo2EqjA1IFmzG4iIRmtgZcrvpR0QaUDYWz3Jl0CrrpdOIwoJwznZQA== X-Received: by 2002:a62:7590:: with SMTP id q138-v6mr48105061pfc.148.1537551577473; Fri, 21 Sep 2018 10:39:37 -0700 (PDT) Received: from [127.0.0.1] ([40.112.142.204]) by smtp.gmail.com with ESMTPSA id t23-v6sm7317294pfl.109.2018.09.21.10.39.36 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 10:39:36 -0700 (PDT) Date: Fri, 21 Sep 2018 10:39:36 -0700 (PDT) X-Google-Original-Date: Fri, 21 Sep 2018 17:39:23 GMT Message-Id: <020b2f50c5703e8291577b008fdfa567093c6eab.1537551564.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v3 7/7] revision.c: refactor basic topo-order logic Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, 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 e7bd059d80..7cc3bf5fc0 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