From patchwork Tue Oct 16 22:36:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644283 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 D4F2715E2 for ; Tue, 16 Oct 2018 22:36:43 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id C6096286DC for ; Tue, 16 Oct 2018 22:36:43 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id BA9012A5AD; Tue, 16 Oct 2018 22:36:43 +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 54709286DC for ; Tue, 16 Oct 2018 22:36:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727282AbeJQG3O (ORCPT ); Wed, 17 Oct 2018 02:29:14 -0400 Received: from mail-pf1-f194.google.com ([209.85.210.194]:42745 "EHLO mail-pf1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727247AbeJQG3M (ORCPT ); Wed, 17 Oct 2018 02:29:12 -0400 Received: by mail-pf1-f194.google.com with SMTP id f26-v6so12144371pfn.9 for ; Tue, 16 Oct 2018 15:36:39 -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=SJ+lmcE+SHOiaT/fYfkqaXMRwOhfW/HXswdUqQ9heU4=; b=Wcud3eGpYhhNRMnGjvMP348dedvLSubESDbTXa3No4qXriflzszpnJgiPRt/FidzOj LHUHPzTmpXsogxWM8CW1NJuZjAada4jxvjVgphY/m2oPigaSOup6AG0LKxM5LrRjTiPZ mj8fArpB1AV0AiduWOLUxn8FY5p6ZL6lpQ6SUV34OHXJRa8imKmy+OD4qK9Mi3TSooUk EGcgv2sSPtiK/OFt6tV2n7nO6pOZwWn04id9DUgVhAlunxfTyhpyF+Q6Em8/4Yu3RSVL z7Trl+3XJy33YSrnf+tfpW60DgrTfNKvrJnbI/1nP1/RD1O83QX0TsEYV7QB+eDWzpRb Y5cw== 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=SJ+lmcE+SHOiaT/fYfkqaXMRwOhfW/HXswdUqQ9heU4=; b=GWzei/ofUkbNE6h2oVd8XdpxchiFmrUiFpks121IVCLyknvVB0n3+SOoeiI4/GVVYo luLQLrJlfRmuTfa1Jjwu7yX6mFCkEcILK548NzhORiRCXB9yYd7x4Bc/1AMiP4aHjTR4 gl1EwBhmTvECCU7YzKHiqk6v1+R0XbbNPgbb/x9wgWPGj6vHizKQVKl8WwkfA8+VLU0N Oig/WgJ/d8hMouQcOkabi36xgBB7oMPejH+1rJsElXk+ZVFEQsMWoVQQbpVxJE4lAaPG eZzdtmwUtGGcIeDiZ5Ln/sGI3UINuD5Tj0U8sWCEEKg9DW96ygyVxRX6g2BSk9UJM7Lu Ps4w== X-Gm-Message-State: ABuFfogJ5fIdTdRt0tpabVaWSdxevwMBVgScJOzrMnAk8PYRswN5a22M kYhIeumpgzgL445JLvIkTVr8JNf7 X-Google-Smtp-Source: ACcGV60ciWKdNPyNhnGAdiuF5yBtYd6qkIaL5LaJY9r3jLbm++Tu2PTMb2w2qxyKHIyalfxxiWHZhQ== X-Received: by 2002:a62:c252:: with SMTP id l79-v6mr23759939pfg.141.1539729399028; Tue, 16 Oct 2018 15:36:39 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id h32-v6sm7017961pgb.94.2018.10.16.15.36.37 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:37 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:37 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:26 GMT Message-Id: <2358cfd5edde4f749ee237f6b9f643444c62b900.1539729393.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 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. Further, add a test that checks the behavior when the compare function is NULL (i.e. the queue becomes a stack). Signed-off-by: Derrick Stolee --- prio-queue.c | 9 +++++++++ prio-queue.h | 6 ++++++ t/helper/test-prio-queue.c | 26 ++++++++++++++++++-------- t/t0009-prio-queue.sh | 14 ++++++++++++++ 4 files changed, 47 insertions(+), 8 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..5bc9c46ea5 100644 --- a/t/helper/test-prio-queue.c +++ b/t/helper/test-prio-queue.c @@ -22,14 +22,24 @@ 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")) { - int *v; - while ((v = prio_queue_get(&pq))) - show(v); - } - else { + 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")) { + void *peek; + void *get; + while ((peek = prio_queue_peek(&pq))) { + get = prio_queue_get(&pq); + if (peek != get) + BUG("peek and get results do not match"); + show(get); + } + } else if (!strcmp(*argv, "stack")) { + pq.compare = NULL; + } else { int *v = malloc(sizeof(*v)); *v = atoi(*argv); prio_queue_put(&pq, v); diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh index e56dfce668..3941ad2528 100755 --- a/t/t0009-prio-queue.sh +++ b/t/t0009-prio-queue.sh @@ -47,4 +47,18 @@ test_expect_success 'notice empty queue' ' test_cmp expect actual ' +cat >expect <<'EOF' +3 +2 +6 +4 +5 +1 +8 +EOF +test_expect_success 'stack order' ' + test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual && + test_cmp expect actual +' + test_done From patchwork Tue Oct 16 22:36:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644289 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 B7CF713AD for ; Tue, 16 Oct 2018 22:36:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A69D7286DC for ; Tue, 16 Oct 2018 22:36:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 97E942A5AD; Tue, 16 Oct 2018 22:36: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 215C7286DC for ; Tue, 16 Oct 2018 22:36:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727265AbeJQG3O (ORCPT ); Wed, 17 Oct 2018 02:29:14 -0400 Received: from mail-pf1-f195.google.com ([209.85.210.195]:42747 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726663AbeJQG3N (ORCPT ); Wed, 17 Oct 2018 02:29:13 -0400 Received: by mail-pf1-f195.google.com with SMTP id f26-v6so12144392pfn.9 for ; Tue, 16 Oct 2018 15:36:41 -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=ZpAYruApCQqyqrhNj0SzoYDRVjgyRcqkhmRl9/Cjo2QvUwxhSqFomHgwqdiIWxWSqx OmKwhiF85Hb+XGPEDB71ujhJlDqeUbJTEYNyZTvtwGCwSGWiYJ387LWQvdkOm5SGbLqR apbgvFWLJ5aP8t9bQgNF4S3SCyFWhkpH14bsflSKKz5tENuti/fqmeARhicGB7UuGSPd 6LklvmZClGLvsC4LhTlI3g7MTmudj8JGYz2E1fbUwd8k06vuJsG29T0EWqyAqnn6hVV0 hE7nECn5EmUQ6BQmdEDRAXYZBIhxzJ0iUDd4mGOxhZsgRtfozhzp1V2/bA/HeIsWw7SK US1g== 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=QsBDS+XIw2X3t4y+tUkOOWwmHQmCXUElllGvGAfHwMO9ExPfaNA+IvSwUrp2tMEmaB U17fGCXmcOOc+SJ/wLmQ++sC9lKBROTNLjM1LTD2sLrpwTLq1rwCa4b2/OtHKCROdb3J SNbroyP08cE/XQQVJ211AgIfT3AF0aFOKzwtgTO56pDSDNfJ5gpewcN2/nUUpPGSSuY5 KcaEtUYveaRpppmqUdv2XB0IfYfOG866oV88zWv47YX2E6gdXLDy1NttKQeYnL87GKRG bUsDOEDKNJkrWJ8HzkzLVD3AmjVrNmUYo4OJS55vGQdeaN6nQjO8QfslSh6ZRcNWpz5n 7AwA== X-Gm-Message-State: ABuFfoggfkCrVuYbnDODr2NR9mFatSBvwzP0m6ikyV424JDrzPOliUPV y3h845Rco36HDiGz/sbmpkQ0yGNI X-Google-Smtp-Source: ACcGV63kQx0W/yxvKBnJgLlK2/VMOT5iLUWv6edLsnP/RQdGLXSctzSSPdSyPX4EFfqsxWSuAQUGKg== X-Received: by 2002:a62:5441:: with SMTP id i62-v6mr24108494pfb.155.1539729400453; Tue, 16 Oct 2018 15:36:40 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id l10-v6sm22691578pgs.45.2018.10.16.15.36.39 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:39 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:39 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:27 GMT Message-Id: <3a4b68e479aa6c270ef1af3aae3222c3310c2935.1539729393.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 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 Tue Oct 16 22:36:41 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644285 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 C504C15E2 for ; Tue, 16 Oct 2018 22:36:45 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B581A286DC for ; Tue, 16 Oct 2018 22:36:45 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A9F092A5AD; Tue, 16 Oct 2018 22:36:45 +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 95650286DC for ; Tue, 16 Oct 2018 22:36:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727292AbeJQG3Q (ORCPT ); Wed, 17 Oct 2018 02:29:16 -0400 Received: from mail-pl1-f196.google.com ([209.85.214.196]:37830 "EHLO mail-pl1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727247AbeJQG3P (ORCPT ); Wed, 17 Oct 2018 02:29:15 -0400 Received: by mail-pl1-f196.google.com with SMTP id u6-v6so8947677plz.4 for ; Tue, 16 Oct 2018 15:36:42 -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=ZteN7PdkYCdvEjIyHvZpKLhrjLaq58/JYjdfbo2/kKblujho7XQxI7DNmIutwVZP5V 3Z43qLL1lGgpltrrPwhKpYHeiV6CRCYMANIPUcRYQoH2U7aZvWk9HrYRtFZSIgx30PEC h7ZROZ9KjLmqb4l0nWZqtv/Ryt8Z6A7/YaaTtiK0G2hhE2PmHU5OV3pFxb7Ti8gAZbRA u3sfb3LrSLCy4PCXTllH0+N9dxrKssCmndRm/pzHK36Zq+Gu1fs0e56niEuPAVltTHph Uq7wEjiSV4/1BXfkhZDFSjNcG+RvOlbkwSbdaTUZtWjm6xxWffpdJYC4EDUPK+ieeg/E 9aSA== 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=qWHhFBiOhvYEmkrd2XFmfdV9YUafyxy2w+3nOYfggmmEYDLQoLXLkYGtf0lPou+WK/ QoCSgK+35wI6rpRz6jV3OIjBurkDACZW7O6mom38mXRuPbcp++fRh3Gv/sVIDVwAPLzd 4WNNJOzAGpbeeyyXC97stt9xpnitah1UaBn8lyIR94t1nsKoPGi7WsIvuTHwCaKDfiyN Eu5G8xpZbdM4HB4jGgW3BfiW9cGt3XwL8AjHblHAyVNF5T32X8lNOPj+A2uBdHh3QJtP r6uH7cJNprvohcPzA2MYcRLsoDnlawPTrF41WNv08AuX0Heyj39k3R3rpGOezL5uaWSf RWYw== X-Gm-Message-State: ABuFfogGaSP73n6dtgnvFcw2r4B9mB8gndPZ5moelOTaHTHM2e6akwjT iDwDin5rqIczN/nwaUbyHQIv+wnK X-Google-Smtp-Source: ACcGV630ifs+YMp4ceyiKr0qf6QuEpWgnPeXo5zSotp6WvZRM1qBg8fB0aHFzf318QIzPI2+nJP/5A== X-Received: by 2002:a17:902:4103:: with SMTP id e3-v6mr23219979pld.236.1539729401903; Tue, 16 Oct 2018 15:36:41 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id i184-v6sm21263524pfg.88.2018.10.16.15.36.40 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:41 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:41 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:28 GMT Message-Id: <12a3f6d3670834f19b38f5e23ef83cdf80a58c33.1539729393.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 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 Tue Oct 16 22:36:42 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644287 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 816DF13AD for ; Tue, 16 Oct 2018 22:36:46 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 71546286DC for ; Tue, 16 Oct 2018 22:36:46 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 65B182A5A8; Tue, 16 Oct 2018 22:36:46 +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 B67672A6AB for ; Tue, 16 Oct 2018 22:36:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727303AbeJQG3R (ORCPT ); Wed, 17 Oct 2018 02:29:17 -0400 Received: from mail-pl1-f195.google.com ([209.85.214.195]:39436 "EHLO mail-pl1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727247AbeJQG3Q (ORCPT ); Wed, 17 Oct 2018 02:29:16 -0400 Received: by mail-pl1-f195.google.com with SMTP id e67-v6so2699057plb.6 for ; Tue, 16 Oct 2018 15:36: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=kxsxfuatUGnB3bzwSX68mZcKrbJkiLhKQcgRuUNHX/w=; b=uu5NqKlbDTFEBwUCY96nW273ELyakiol5JJQf8xPfFBocsW0DSg9J3CMcHI9umKtzb 1gkvVd8Un3Utcmo528HutO5hilhc+4bk0YQVHiU2UpuqAhdHfmOsmc8yfQodHKzi3ut4 U/eifHbQ9FNFBG0VFA5voSjVII8dOg8lvokc+u1WVs0ndNhupH57RY8bmbu4BOUhpfeV XwyxDM49m/45BTMD0uRfKzk9a4f1MaA86THQeexn09U0LcJrmIFcQA5T6HdF3YkzzBgm bPaGUFnx4/Dq4rZgj6Y5cD9XqQ7cgYeuftI84gOm9P1j5thltTt0iC6UPtdRVP1sTHIl Zdvw== 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=iSLl0svTXWTmGNaj63Q8GB/V9OPONfHhU/GnX7RKt0GIYgwZvp3vVsM07b8K/LeFIk cyWld+u1djddXvrgnS4hiw61CFVXjsV6Jd2/FzhttfnUToE+kOwTF41JE/7gdAY7wyLc iTG7tSXA+BIPOwdEcwu58k1wNXV8FHINpkTr6CFiqMHLH5geIcv4gOtzl4C9BK0Zb+6J WZKhmXAKI59wJjG+OkjVS231k9guMgFxZi4LjyiIUqV33dyFkqrF6QxkNcFmINrcguu/ 1Y7X6bKXfYBxaXW1v+x0VO+B44UN3ELLvUaL/j+KAp4a0eHF8Sh/ZNbtKFVgFL/v6zKV jqqQ== X-Gm-Message-State: ABuFfohd8WVlyPyZK7emPb3ZHs4qMNz60v4HS0WdbTwMn+5g59M/81mf yOW8OpljnHTM5vQ0GZCX2SIgsbA5 X-Google-Smtp-Source: ACcGV60HyYPvCfcZjK8ffwnqBkOGvJ3aqKaa54Vm0toUI2mZxAZKiVw/Xwc9DNGh8kugZ7eZE8D8Gw== X-Received: by 2002:a17:902:848f:: with SMTP id c15-v6mr22718778plo.119.1539729403345; Tue, 16 Oct 2018 15:36:43 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id o131-v6sm24468079pgo.53.2018.10.16.15.36.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:42 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:42 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:29 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 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 Tue Oct 16 22:36:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644291 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 C521D13AD for ; Tue, 16 Oct 2018 22:36:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B624B286DC for ; Tue, 16 Oct 2018 22:36:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id AA3D62A5AD; Tue, 16 Oct 2018 22:36: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 1C1A8286DC for ; Tue, 16 Oct 2018 22:36:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727323AbeJQG3T (ORCPT ); Wed, 17 Oct 2018 02:29:19 -0400 Received: from mail-pg1-f194.google.com ([209.85.215.194]:46513 "EHLO mail-pg1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727247AbeJQG3S (ORCPT ); Wed, 17 Oct 2018 02:29:18 -0400 Received: by mail-pg1-f194.google.com with SMTP id a5-v6so11509405pgv.13 for ; Tue, 16 Oct 2018 15:36:45 -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=NU/Iu8Ji8N1MpF5ITTmj/BX7u15ZcGZShg5sidDyG0g=; b=YeZeqJZEPBm6YgjlBkt23DPQt/AYKq7tpuYi5ExuIvEd9KhZMgi0LDACuEWI1GAn9a HE0phWRDrPlEZnyGNSqwfXQ7EtFFGjbwgxhBmMTLEBr3o6jIndkV4VUAiIVU1GK4yX4q iD6ony3H69o8FJRYWyki5HoyJ6qT4EY78+he0MoEzyNvkeaM4pVJfifKJCSnVwnCFn09 cRmdfrbr9JPDgPebDHUnvd6K5inmCwjrtX8SZqVH+seYz0hq4/QabriWCnWUozFQaW45 C/wGdK6GkkRYbw8/L9II1c4kiyMFU38399e560brSVDWM9Tpybs7YOVd/2VjETiZwH7d 4o4A== 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=NU/Iu8Ji8N1MpF5ITTmj/BX7u15ZcGZShg5sidDyG0g=; b=T544mOIFhSTm22LiBWnIvG/2DHdodF3hE6UX4ryJjmFnph4ysaK2/GbGYRQ3jAYQ1M SsOOBx+T9BTZemUtjeztNmPTOgt60Si0yjsadUzveLOVgWNrI+vE6FOXl7uAsaV8rHEK 8K1H/A5GF+ePj1YuhVKHJyaL6FaWK0JGtiR29q1lQbbNDkOH0ctEK6FcvSIcraBga7EF jugSgMjfOIyxLCfx51FIp/CShiBR9et5ncDxvHEcZBQiHJ9f2usbThJcGd63tOH9/kv1 i+tfI66ooqZHCBMqCN+wcwpRpRjiFb/ZegcD7zg61OXpcNBp81QvSIi3qNn9zX2elFqy i4Yg== X-Gm-Message-State: ABuFfoiHYrN3ZtsskfhTleFVv4QI1Of3iLFaH8csexV4MZm/OZzzVws5 nlpEbZ3nYDmbK92ai1QidIBlrwY9 X-Google-Smtp-Source: ACcGV62kAZCwP0c+yomoS1syYVWa9FVRBry1CY49qoAi3WDll6H1dPY7zarKiuJKgR6LV1L+XbBWnw== X-Received: by 2002:a65:4103:: with SMTP id w3-v6mr22389833pgp.284.1539729404792; Tue, 16 Oct 2018 15:36:44 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id e2-v6sm16496554pgv.25.2018.10.16.15.36.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:43 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:43 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:30 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 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. Also rename the method to the slightly more generic name process_parents() to make clear that this method does more than add to a list (and no list is required anymore). Helped-by: Jeff King Signed-off-by: Derrick Stolee --- commit.c | 11 +++++------ commit.h | 8 ++++++++ revision.c | 18 ++++++++++-------- 3 files changed, 23 insertions(+), 14 deletions(-) diff --git a/commit.c b/commit.c index d0f199e122..861a485e93 100644 --- a/commit.c +++ b/commit.c @@ -655,11 +655,10 @@ 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); +implement_shared_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 +683,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..977d397356 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_shared_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..36458265a0 100644 --- a/revision.c +++ b/revision.c @@ -768,8 +768,8 @@ static void commit_list_insert_by_date_cached(struct commit *p, struct commit_li *cache = new_entry; } -static int add_parents_to_list(struct rev_info *revs, struct commit *commit, - struct commit_list **list, struct commit_list **cache_ptr) +static int process_parents(struct rev_info *revs, struct commit *commit, + struct commit_list **list, struct commit_list **cache_ptr) { struct commit_list *parent = commit->parents; unsigned left_flag; @@ -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; @@ -1091,7 +1093,7 @@ static int limit_list(struct rev_info *revs) if (revs->max_age != -1 && (commit->date < revs->max_age)) obj->flags |= UNINTERESTING; - if (add_parents_to_list(revs, commit, &list, NULL) < 0) + if (process_parents(revs, commit, &list, NULL) < 0) return -1; if (obj->flags & UNINTERESTING) { mark_parents_uninteresting(commit); @@ -2913,7 +2915,7 @@ static struct commit *next_topo_commit(struct rev_info *revs) static void expand_topo_walk(struct rev_info *revs, struct commit *commit) { - if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) { + if (process_parents(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)); @@ -2979,7 +2981,7 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp for (;;) { struct commit *p = *pp; if (!revs->limited) - if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0) + if (process_parents(revs, p, &revs->commits, &cache) < 0) return rewrite_one_error; if (p->object.flags & UNINTERESTING) return rewrite_one_ok; @@ -3312,7 +3314,7 @@ static struct commit *get_revision_1(struct rev_info *revs) 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) { + else if (process_parents(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)); From patchwork Tue Oct 16 22:36:45 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644293 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 7D9F815E2 for ; Tue, 16 Oct 2018 22:36:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6D9D6286DC for ; Tue, 16 Oct 2018 22:36:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 61B3E2A5AD; Tue, 16 Oct 2018 22:36:50 +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 68A93286DC for ; Tue, 16 Oct 2018 22:36:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727331AbeJQG3V (ORCPT ); Wed, 17 Oct 2018 02:29:21 -0400 Received: from mail-pl1-f176.google.com ([209.85.214.176]:33357 "EHLO mail-pl1-f176.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727247AbeJQG3U (ORCPT ); Wed, 17 Oct 2018 02:29:20 -0400 Received: by mail-pl1-f176.google.com with SMTP id s4-v6so11697776plp.0 for ; Tue, 16 Oct 2018 15:36: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=wM7VNQFtyRUO6BJxq2Kb7OC33S5o+1V8iH5nMhfmTL4=; b=vdgT4+pYJbdRWft/t5xZD3CdJBZ1ihy3N9cMbqiqmLDYPEzFqzEeU9noVcy0ZflCca mJV1WMK/aal6kjUKHKVIdZxde5eclijZcb0f/alvlzblPwVk7uDulcb3AvX+h9nPQBiY 8gSTbUfbzLYl4jI0Vi9vd4ngFoaxwddBpVhjglSVp2NPOz8+XUSEr7zoxp0nNn+D4ThK 7yI/zpDRnydkZs01bKjnGgEbVFaXCRYsFhL26hFU0f7hghIzRR/OCNdaiBXTpMp5P7vj LRM364m1CFSdGZsHPcXszqYX4+Dp7Xzaq5Qbo7OnuZ5f0Qn8imgCr0cfTCA+D8+xpS26 r3iQ== 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=wM7VNQFtyRUO6BJxq2Kb7OC33S5o+1V8iH5nMhfmTL4=; b=eXsd+BVdu/2SeYjKYib/8s/nlsYV83b+NvODgtvqxq9Th5qclTEdsRJd3okJ6fUHIY 3FbPt5ssYNfa0jBR116xs8e9HvIfGo1uHs9Rx+5f4JyacFhNyRhgMKy4BbJCDHFHSip/ 25v7dYCl37m3VYbU98HN9EpG3ziGELFeoBR/SEDgvdRgtvOe/KIBvLo918BNSjg7OgFo DW6ZS3yvXz+Ulp4TOK8SsRKTbqTtUY2ANz8GPcB/0pNGhcZKpQsZNsZ/Iw2rNL9LCaos KUDc/kiPXM+3k55EzicF1guGRLkAObW0C/mCEPL0AMTajfrvvaowVwcck4zI+tV+emYD SSZw== X-Gm-Message-State: ABuFfoiWDgyQbGW4P0XoHbSiBxdaeQCbxIeGLVidGpqDmV88rlwy32af myKZxV08TofG3VwjASpNtgOlyMeC X-Google-Smtp-Source: ACcGV62ny/P/3BltMeUh/M+4h4Ku4NtmzfUV3iXGouBf3CEWfwn/yL1h2Eq0aTpUVZGUyPxuxtX1Ww== X-Received: by 2002:a17:902:a5cc:: with SMTP id t12-v6mr23951868plq.229.1539729406281; Tue, 16 Oct 2018 15:36:46 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id s23-v6sm19073658pgg.67.2018.10.16.15.36.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:45 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:45 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:31 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 6/7] revision.c: generation-based topo-order algorithm 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 current --topo-order algorithm requires walking all reachable commits up front, topo-sorting them, all before outputting the first value. This patch introduces a new algorithm which uses stored generation numbers to incrementally walk in topo-order, outputting commits as we go. This can dramatically reduce the computation time to write a fixed number of commits, such as when limiting with "-n " or filling the first page of a pager. 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 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. Helped-by: Jeff King Signed-off-by: Derrick Stolee --- object.h | 4 +- revision.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++++++-- revision.h | 2 + 3 files changed, 197 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 36458265a0..472f3994e3 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,216 @@ 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->sort_order == REV_SORT_BY_AUTHOR_DATE) + record_author_date(&info->author_date, c); + + if (revs->max_age != -1 && (c->date < revs->max_age)) + c->object.flags |= UNINTERESTING; + + if (process_parents(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 (process_parents(revs, commit, &revs->commits, NULL) < 0) { + struct commit_list *p; + struct topo_walk_info *info = revs->topo_walk_info; + if (process_parents(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..b0b3bb8025 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 From patchwork Tue Oct 16 22:36:46 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Schindelin via GitGitGadget X-Patchwork-Id: 10644295 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 38CA415E2 for ; Tue, 16 Oct 2018 22:36:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 28C7D286DC for ; Tue, 16 Oct 2018 22:36:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1CA0F2A5AD; Tue, 16 Oct 2018 22:36: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 A13F1286DC for ; Tue, 16 Oct 2018 22:36:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727333AbeJQG3W (ORCPT ); Wed, 17 Oct 2018 02:29:22 -0400 Received: from mail-pg1-f193.google.com ([209.85.215.193]:45330 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727304AbeJQG3V (ORCPT ); Wed, 17 Oct 2018 02:29:21 -0400 Received: by mail-pg1-f193.google.com with SMTP id t70-v6so11514499pgd.12 for ; Tue, 16 Oct 2018 15:36: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=9dub4UGRgjLu0zkHm8JWsQaxviQeUr5UMnvk5A7Kz7Q=; b=S7fz5WUmqNWjbSSPG0hwVGXflJU8qoFAqCJ3NXAlg+PlTKX9+LOoTnMzZo30MU2Sbz pYDvabKHnzFSe/meA6L6P2KaR8q32eNWf3aBU8oDAZQi/jScDZbKgD6J8hjtIIvFVMV/ yvvDwKlLy6fnnjuoRxNtV56VL8y65NAZ7JyzGKvF02jezDixxbdZVwq2q38zStmTFNRN Dsi3rPUXh2gVkUM5474dez5uBQSdDsztGQJ0pLeKhl/3KEGpxVN6qGWRtxN8+rRZUBI5 e/byHz4qLgrhM6suifbT5gguZx+LdmYZvir7/BKeDDfwVGzhcGFpu/hZlsKLsz037/wP WN7w== 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=9dub4UGRgjLu0zkHm8JWsQaxviQeUr5UMnvk5A7Kz7Q=; b=WuszB3ldLVIveFiU6LwYKQ81SgPIsKxGN/q6YHF3skjuH7D9FY4SxNBFMMFQDcJoy8 qYLaIzFf/zrUXg0zwtRDfb2TEFFD7ZDs0UTvTo58+Umzpi1lYVViiIT/+MNVJwR5CzrB u9GdVBJqhyEZXQPJLXfX3yt2LhAgzP05ecNm26csCU03OFLOKy27G8wnehr6lCscvDlk N9yWEY4yuM5yKMm5r4vGjOTwTjZhDqgdxLytlSBq9bThoi6rF5zgY5AJasV0+Bm64e8N fMEGu6N/KuLemj3dfUIEM/3jfA1kVL0NhRfulV0cnuDL9ha0Gp1O+atb2yuJyIOclryT AqQQ== X-Gm-Message-State: ABuFfogXngefg+73r4Kg3HO/FmO9O+nvccIehGWxRe8lcjBtak9LTJev bz1NEyrRGivXLBqGSh2vyh6m7Zmb X-Google-Smtp-Source: ACcGV61sU6jR8RN479MiLmElno2FzsUTExVuDAaS7euq4v6Nb4jOHpd0nuR4YPXmpP7eyeIP6WcEnQ== X-Received: by 2002:a63:df4f:: with SMTP id h15-v6mr21138304pgj.94.1539729407700; Tue, 16 Oct 2018 15:36:47 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id q25-v6sm23054959pfk.154.2018.10.16.15.36.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 16 Oct 2018 15:36:46 -0700 (PDT) Date: Tue, 16 Oct 2018 15:36:46 -0700 (PDT) X-Google-Original-Date: Tue, 16 Oct 2018 22:36:32 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 7/7] t6012: make rev-list tests more interesting 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 As we are working to rewrite some of the revision-walk machinery, there could easily be some interesting interactions between the options that force topological constraints (--topo-order, --date-order, and --author-date-order) along with specifying a path. Add extra tests to t6012-rev-list-simplify.sh to add coverage of these interactions. To ensure interesting things occur, alter the repo data shape to have different orders depending on topo-, date-, or author-date-order. When testing using GIT_TEST_COMMIT_GRAPH, this assists in covering the new logic for topo-order walks using generation numbers. The extra tests can be added indepently. Signed-off-by: Derrick Stolee --- t/t6012-rev-list-simplify.sh | 45 ++++++++++++++++++++++++++++-------- 1 file changed, 36 insertions(+), 9 deletions(-) diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh index b5a1190ffe..a10f0df02b 100755 --- a/t/t6012-rev-list-simplify.sh +++ b/t/t6012-rev-list-simplify.sh @@ -12,6 +12,22 @@ unnote () { git name-rev --tags --stdin | sed -e "s|$OID_REGEX (tags/\([^)]*\)) |\1 |g" } +# +# Create a test repo with interesting commit graph: +# +# A--B----------G--H--I--K--L +# \ \ / / +# \ \ / / +# C------E---F J +# \_/ +# +# The commits are laid out from left-to-right starting with +# the root commit A and terminating at the tip commit L. +# +# There are a few places where we adjust the commit date or +# author date to make the --topo-order, --date-order, and +# --author-date-order flags produce different output. + test_expect_success setup ' echo "Hi there" >file && echo "initial" >lost && @@ -21,10 +37,18 @@ test_expect_success setup ' git branch other-branch && + git symbolic-ref HEAD refs/heads/unrelated && + git rm -f "*" && + echo "Unrelated branch" >side && + git add side && + test_tick && git commit -m "Side root" && + note J && + git checkout master && + echo "Hello" >file && echo "second" >lost && git add file lost && - test_tick && git commit -m "Modified file and lost" && + test_tick && GIT_AUTHOR_DATE=$(($test_tick + 120)) git commit -m "Modified file and lost" && note B && git checkout other-branch && @@ -63,13 +87,6 @@ test_expect_success setup ' test_tick && git commit -a -m "Final change" && note I && - git symbolic-ref HEAD refs/heads/unrelated && - git rm -f "*" && - echo "Unrelated branch" >side && - git add side && - test_tick && git commit -m "Side root" && - note J && - git checkout master && test_tick && git merge --allow-unrelated-histories -m "Coolest" unrelated && note K && @@ -103,14 +120,24 @@ check_result () { check_outcome success "$@" } -check_result 'L K J I H G F E D C B A' --full-history +check_result 'L K J I H F E D C G B A' --full-history --topo-order +check_result 'L K I H G F E D C B J A' --full-history +check_result 'L K I H G F E D C B J A' --full-history --date-order +check_result 'L K I H G F E D B C J A' --full-history --author-date-order check_result 'K I H E C B A' --full-history -- file check_result 'K I H E C B A' --full-history --topo-order -- file check_result 'K I H E C B A' --full-history --date-order -- file +check_result 'K I H E B C A' --full-history --author-date-order -- file check_result 'I E C B A' --simplify-merges -- file +check_result 'I E C B A' --simplify-merges --topo-order -- file +check_result 'I E C B A' --simplify-merges --date-order -- file +check_result 'I E B C A' --simplify-merges --author-date-order -- file check_result 'I B A' -- file check_result 'I B A' --topo-order -- file +check_result 'I B A' --date-order -- file +check_result 'I B A' --author-date-order -- file check_result 'H' --first-parent -- another-file +check_result 'H' --first-parent --topo-order -- another-file check_result 'E C B A' --full-history E -- lost test_expect_success 'full history simplification without parent' '