From patchwork Thu Nov 1 13:46:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663971 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 9ACEF13B5 for ; Thu, 1 Nov 2018 13:46:31 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 90A122BBC3 for ; Thu, 1 Nov 2018 13:46:31 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 84A5F2BC69; Thu, 1 Nov 2018 13:46:31 +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 E29BD2BC7B for ; Thu, 1 Nov 2018 13:46:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728606AbeKAWta (ORCPT ); Thu, 1 Nov 2018 18:49:30 -0400 Received: from mail-qk1-f193.google.com ([209.85.222.193]:45024 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728520AbeKAWta (ORCPT ); Thu, 1 Nov 2018 18:49:30 -0400 Received: by mail-qk1-f193.google.com with SMTP id n12so12252101qkh.11 for ; Thu, 01 Nov 2018 06:46:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=51vf9rmyUST7LXKwNKxANNRDC7ro8zDKgJwS3AqXweg=; b=RhLPgp6BvneNOpak6OVeths1yX4t5PuYVOniv34MNd2Fs5hImyVGNg+cdWR2aSTJg6 BpvA1WRrQKDzEtnRukg5KhS74VLJ8E0HHnyliX8Zoz2DIGkMfItabpDaXoOu5xkuhfM5 sN8x8mB3wwWYAKgH982BBy2lz2PuhpeOppo2U5zIgE7eFCgJe+rsGPcVkI4oCjhDCazC suDINoG9RKM9KIFl7OK+Qu8tRLpKdQomxpy6HdrPj+4x+otKd22W6suUnJi5g6UmQIIz Vxaq3BRIXeIlD3tzEUxev/MILGKekojz1fQ2X7Exi4npB4l0Rw605ftQGWrKQxh1t8Kd eg/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=51vf9rmyUST7LXKwNKxANNRDC7ro8zDKgJwS3AqXweg=; b=QyU4W8mF1CAYNnEuGwy7Vb5p20zv43Wfpsfj4oWyJEjsCmo1W70Dzti74lqy2iHenL jqLoHfFrQaXdjlEUAts5gIQyZYFgSYTAAf+AE84KafkPeVWd+m75oDvBkO5GKFgvFqMl M9uvqsUVrIUtpn7i3t/aa8hyd1QXNfA+mDNZj71Jy0dAk6Iu9endx5urqGys3QLNdRSo jMHnrDbdKvUSGRfeIlLzGooXZulaf6N5peznQZ3lgAEnFNLBzNRysfWE2kY5vG6MhPJS ZLnj+AX4A3Pvs8QzgnKjhN1fezHUAQxSkyXTe1ofZNJMNXwuprmRuLgNYBPcLeJNE9bv 5Fog== X-Gm-Message-State: AGRZ1gJOWH1+WKSG8j+fEdPJTwO6qSXAkSDBRv8SHFkI7qIJnO//bnHR EnDtPMKuJ5fjq/G4pVjDuX4YvnrU X-Google-Smtp-Source: AJdET5f0yMnSjXKTo4T1KJKt3RE64WQ0YqsD/tHVrfIC5rT0xz0yyrRZSQ2bMDZY0Qj7xbkeXA2BwQ== X-Received: by 2002:a37:7484:: with SMTP id p126-v6mr6328258qkc.153.1541079987624; Thu, 01 Nov 2018 06:46:27 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.26 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:27 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 1/7] prio-queue: add 'peek' operation Date: Thu, 1 Nov 2018 13:46:17 +0000 Message-Id: <20181101134623.84055-2-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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(-) base-commit: 2d3b1c576c85b7f5db1f418907af00ab88e0c303 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 Thu Nov 1 13:46:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663973 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 186933E9D for ; Thu, 1 Nov 2018 13:46:32 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0E6BC2BBC3 for ; Thu, 1 Nov 2018 13:46:32 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 02C5B2BC7B; Thu, 1 Nov 2018 13:46:31 +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 A2B9A2BC69 for ; Thu, 1 Nov 2018 13:46:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728623AbeKAWtb (ORCPT ); Thu, 1 Nov 2018 18:49:31 -0400 Received: from mail-qt1-f193.google.com ([209.85.160.193]:42510 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728520AbeKAWtb (ORCPT ); Thu, 1 Nov 2018 18:49:31 -0400 Received: by mail-qt1-f193.google.com with SMTP id z20-v6so21060027qti.9 for ; Thu, 01 Nov 2018 06:46:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=6nnlYnor2jca28BytU8+iX6lJi/U1iwWUVEVAahWFOA=; b=bJhwPRoMYXsLZrNNL0EJb01MIt0rt1bjosakIJE/f8/rA8R7BMa1j619xtr3JHgtTk fNnUfJ/0TF1qJiSY2aa6aQhHE6qO94EsuJRD+R5Qhl6hsodDnydVRG3YwN7vh19Ijwjg SrXuXYsAnpQpeEc6Us+dy2CzwafuIqRQkyG96ajtVSpdHcUJYw7xg+q8mULT7KCZCb1d pcCONmuEd4spe9kZEPJEGZV9oJiDT/gtURSyLjiZmcPs39jMxVOZRXu6CX2Akeh6Z4GS HG/vMV5BuuJHikRuY3UT1zNOilKPRvMw037oIRTwJLsGKdoWf3Dt+UYph9UTY6qfQ6y8 zCZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=6nnlYnor2jca28BytU8+iX6lJi/U1iwWUVEVAahWFOA=; b=Pc5pIp+Ehh0Mez9vXLbI9SaWaz8C32vjaH+Z0RVlRh39hzHhdpn0j0IjJwZBNUoKT9 gzX2N0VH+X781Hn15oGX5di7SFZPIbYNXC44HcdlsR6g5Nt4jbjuMTQT7w7RBjW8j3dh DqioFvnOw9RJjiVqhSlM3/khRLlDKmES97LFFHVXt+8wrd7wxur2/83oPv3CdZRekOVh baizKnj2MlucO5OHbq8Er/tcl9tVIo6IBQc2QtiMgbx33vElNeTvwsfFP0B83RR2oWFG NaXZYdiPiaaDOGegwpuYi8kgMNgomOsnpJRCmhVtMU81Hb1mSbZmNE9bRX1Z6EmA78AA 9++w== X-Gm-Message-State: AGRZ1gIo9Cy64FbYg/XuVi+ihuEJOezsVOM//VxUQR+JOnTDoOHAP5xC dDZLw5x4ZjbRDi7UoxMlWz1kYSFh X-Google-Smtp-Source: AJdET5f9fPRiQ1B92ikv9PAizFFTN20WJiXkZsZLhR5Ttmu1GZ5kvzHpW0IjCdI2NQr71xzuB0Ziug== X-Received: by 2002:a0c:98d1:: with SMTP id g17-v6mr6770449qvd.13.1541079988862; Thu, 01 Nov 2018 06:46:28 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:28 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 2/7] test-reach: add run_three_modes method Date: Thu, 1 Nov 2018 13:46:18 +0000 Message-Id: <20181101134623.84055-3-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 Thu Nov 1 13:46:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663977 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 8E328109C for ; Thu, 1 Nov 2018 13:46:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 81EA02BBC3 for ; Thu, 1 Nov 2018 13:46:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 75D5B2BC7B; Thu, 1 Nov 2018 13:46: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 052D92BBC3 for ; Thu, 1 Nov 2018 13:46:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728654AbeKAWte (ORCPT ); Thu, 1 Nov 2018 18:49:34 -0400 Received: from mail-qk1-f196.google.com ([209.85.222.196]:43413 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727963AbeKAWtd (ORCPT ); Thu, 1 Nov 2018 18:49:33 -0400 Received: by mail-qk1-f196.google.com with SMTP id r71so12265356qkr.10 for ; Thu, 01 Nov 2018 06:46:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=4XHtyEd7Lj8CK8zT8JQIjck/3o2ljdc8qaO6uLQfdCE=; b=YOiuBBqM0rWSONsq5Xl1hh2Gzw3MucQkAVU24W+Vqfs5lwacACO7JKlliznunNEVNW awN+PdyVj+COKAqN1Ikneq4DsFRzkM5Dhyz7Ei9ZSSvcFYnmfRbvtArfRWRx2Y9+Mp7K GF4WXW8lEipKLm4EJhaHqr7mUfzh5kHF44F3qzE4oBC5hY0igWVpXItBcvBUMgUc77ul T5B62ernajy2kxhFWguu93nU15Y3ov0QgMTXzasCUUzrg/zzGSEC+7hDStEv3rQmeZFK jpmFrUDfKh1HqcaH+eXWo9HlKlpHjxFDKlGXQHFuNHcLVlZ0xOnURjmmK79icfCE+Bjy Prew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=4XHtyEd7Lj8CK8zT8JQIjck/3o2ljdc8qaO6uLQfdCE=; b=hhyqOjqrWcneTNNdDtLA+QUuYA3sqSvJI1ItndtCqMhLR5ln3lpsvHiZRfOUUib2iY f6fkaxoEwGuJRzDikTK22z1rOCqCs1WL//pmOpHtAVs2Z8i+NM27BKR6vJOKK9zVJASa 87rbtts0iVYgSEt1rlf+Iu3Vjdw4T6bYs6xeehoy+kMmlsuaclMsWaKtkiiraFLxLyUU p9ZDqz8/q2Y+ScJhvoikHIWEPFiAHiIGS1UG9kE7gAJJuaR9Y0T2gpDVe0mtLUKaIseo zFGwefhHXQc7B07icqksE+y9jD/EBeH7/ZthrbiqY86Q4WAM448DG5l51dGYYjr8VjXb FXIg== X-Gm-Message-State: AGRZ1gI1b93GQdyK9YvSPCzSNIr4gQm4f3yQEGR5/nwP4cVF/MVZ847K 1v5DiuTYwtMOEOk4jEkFz1KWnsNR X-Google-Smtp-Source: AJdET5fk9G434J+xUh4suyLpMGx0IrPSVteGShZ56CXQNZk2isG3fKAODhcjvtjVqlE9DNcx1iWyww== X-Received: by 2002:a37:e20b:: with SMTP id g11mr6313633qki.21.1541079990055; Thu, 01 Nov 2018 06:46:30 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:29 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 3/7] test-reach: add rev-list tests Date: Thu, 1 Nov 2018 13:46:19 +0000 Message-Id: <20181101134623.84055-4-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 Thu Nov 1 13:46:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663979 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 3628317D5 for ; Thu, 1 Nov 2018 13:46:35 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2BFDF2BBC3 for ; Thu, 1 Nov 2018 13:46:35 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 200EF2BC69; Thu, 1 Nov 2018 13:46:35 +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 84AD12BCA0 for ; Thu, 1 Nov 2018 13:46:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728676AbeKAWtf (ORCPT ); Thu, 1 Nov 2018 18:49:35 -0400 Received: from mail-qk1-f195.google.com ([209.85.222.195]:37806 "EHLO mail-qk1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728520AbeKAWte (ORCPT ); Thu, 1 Nov 2018 18:49:34 -0400 Received: by mail-qk1-f195.google.com with SMTP id 131so12273472qkd.4 for ; Thu, 01 Nov 2018 06:46:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=bNWMo2rE6LEt7eMpPhweIKa8rWyxVykawgFSDTBrghA=; b=XHjNQXCpf4bZ2dzS4THsML0lhS0DD/AQlSurFLqkGMVW4L+B4NIEUptALLkRIkzrGL ZXTn6H9wS6uekN4DnPC8jhzWE4EH0caxcmzoeBl8CbbsX2nFNTpP4p1iP+skNIEWGTK8 XnJqZTAUxfX4Jkjem/14U2ukx5bC/W3DsT6nIfyYJR2TQoJggHqA0WIkbvZxWMg8SctC WqPGbSdLSfA3qZ8Fn8soX8c+xmwZ/NNAiwvP5gFFutciz8N+vMTTh3iWGb0+9E5LeiXd +pTNedEHnWr8GekORCeZxKCa6KuGALG9xg44BcgIoq5zrNoOY0K1a3ejnvKLws5s6VWo U6FQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=bNWMo2rE6LEt7eMpPhweIKa8rWyxVykawgFSDTBrghA=; b=R+R8MrLhVNGKhBjbTIxaAmIjiL4TevAZ60C0kJ0Hik1l8+3cLS6hhdMTg9s6GDe1es Lz3xDKJyDwMmKPds0i/DxokbaQSSHDR5Dk1z80iAOPW9drmCpIrPu8EeA9TCyZCEWLmB 231MbnZWhAWMH0EGm1mMdY9kwwzisAUkP0ZfB+PnmhEEWah2wEY/ocER44b4AP3bY634 lVNqDxh3kvwRSrP7/9uHTvyNinbVc6SvETzyYAdQ1yZnZRdLTiwQPltMrTkBLOZwMN0N OmhruVxUaZbo0ks3otKvuJLi2yusdn2ER2aVfRhlM/oLwz8ONiPgW66fQBPedcMkFeND Wn4A== X-Gm-Message-State: AGRZ1gIMOZI4Hm40a/wzwzgSM8/4g33AXPzNwgVz41lXdw6xlm3V+/9r TYTSJp+rB53dUADYlyh+sAYPVzcK X-Google-Smtp-Source: AJdET5cow79h4AiZ7qqWtz7JIQeVu45C8S9lSWUB1BB1cSFeW/LwGKghdHBcN4RKQlLfKbnzWDnl8w== X-Received: by 2002:a37:a5d1:: with SMTP id o200mr6434591qke.328.1541079991130; Thu, 01 Nov 2018 06:46:31 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.30 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:30 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 4/7] revision.c: begin refactoring --topo-order logic Date: Thu, 1 Nov 2018 13:46:20 +0000 Message-Id: <20181101134623.84055-5-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 Thu Nov 1 13:46:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663981 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 E675713B5 for ; Thu, 1 Nov 2018 13:46:36 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DC8D22BBC3 for ; Thu, 1 Nov 2018 13:46:36 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D09152BC7B; Thu, 1 Nov 2018 13:46: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 3D7FC2BBC3 for ; Thu, 1 Nov 2018 13:46:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728703AbeKAWtg (ORCPT ); Thu, 1 Nov 2018 18:49:36 -0400 Received: from mail-qk1-f196.google.com ([209.85.222.196]:43417 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727963AbeKAWtf (ORCPT ); Thu, 1 Nov 2018 18:49:35 -0400 Received: by mail-qk1-f196.google.com with SMTP id r71so12265429qkr.10 for ; Thu, 01 Nov 2018 06:46:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=e+Ow6algqNOpaxltSKYqvDdeKyRr7gCkMuSUNcd3kVg=; b=UZgI/bteDtSSaIW4jCwA+je6G9zyfnGkHZLOO5t+/bDqVZbWmPpWcvtHwOJNzLgnfZ J/NhZMs+HUZWc0kbW+GPFDL5piXB1hdonQFKACPnN4ztqQOXaFLu2aG9YvJ2i15hAvIl Q6sj+oUNb5bqCfKBnRz01/2tkbwaDZfrUcdo3Pqnv4E2A0aWTmQXet1jYUs1XQs1pQEr p9oUF2bnoQyc04ytgrPeb9+4JDHZxQSW9GvCfWLpVrQv1rZ7zZ5Rq+g28O4FP/vSbgRu fGTVuqGkfs25umpKBv9XYOkrdQ7DAnMAeE1JCe6RwJ47/725TqdE6KuWERuImuWNJ+4r 6oZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=e+Ow6algqNOpaxltSKYqvDdeKyRr7gCkMuSUNcd3kVg=; b=TQQ9hw9KPJhs3ZUU+elStqaEaNYREc7gUHfkY98ovbkTSvKmmsZXfnQuL7EPtNWtBa 65uEuQFbD6YrkM/ipb/X7RG1uFIiJ2wFigFGF2a3gyP7ug0j7q/dA8y6rlib6wU8wAGg Sob2H7PRrQk6DEvFV0AbMCKTNaCQCFRRCsqJPqXLHuUrHgr96wjZ2h0STGmjd9TArhlm XUejUsjFHKVzEazR5iXXKqr2k1MLAXvAw4I6YFG3ptrK+mqwak9GVxXJVu85+u+A2rDT VixyIE+0f+E5zFbsuZaPlfqlcvZYXR9LC3zsa7YCjV3pDMeCF2nFk37EhqI9w6YgUnkp FclQ== X-Gm-Message-State: AGRZ1gJcAh5IKmxC664+w1wB7jmok5OmhWCDsZ3uDQ9TfHpo0NlhnmoP wlanx04+e3wisjXNjO5VwWMt5sKk X-Google-Smtp-Source: AJdET5f3dVrhXNtJonhhLfiOXnkQ4kik3BjEc1UsmDEnRebn60CjU/QSpHWLDv3tNFs5+zoWwoFQVA== X-Received: by 2002:a37:34f:: with SMTP id 76mr6480126qkd.347.1541079992307; Thu, 01 Nov 2018 06:46:32 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:31 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 5/7] commit/revisions: bookkeeping before refactoring Date: Thu, 1 Nov 2018 13:46:21 +0000 Message-Id: <20181101134623.84055-6-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 an author_date_slab declaration to commit.h. Consumers will need their own implementation. 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 | 9 ++++----- commit.h | 7 +++++++ revision.c | 18 ++++++++++-------- 3 files changed, 21 insertions(+), 13 deletions(-) diff --git a/commit.c b/commit.c index d0f199e122..a025a0db60 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); -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 @@ static void record_author_date(struct author_date_slab *author_date, 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..ec5b9093ad 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,12 @@ 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 */ +struct author_date_slab; +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 Thu Nov 1 13:46:22 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663983 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 E9D7B13B5 for ; Thu, 1 Nov 2018 13:46:38 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DEB522BBC3 for ; Thu, 1 Nov 2018 13:46:38 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D29012BC7B; Thu, 1 Nov 2018 13:46: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 CBAD62BBC3 for ; Thu, 1 Nov 2018 13:46:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728733AbeKAWti (ORCPT ); Thu, 1 Nov 2018 18:49:38 -0400 Received: from mail-qk1-f194.google.com ([209.85.222.194]:36066 "EHLO mail-qk1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728520AbeKAWth (ORCPT ); Thu, 1 Nov 2018 18:49:37 -0400 Received: by mail-qk1-f194.google.com with SMTP id o125so9008623qkf.3 for ; Thu, 01 Nov 2018 06:46:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=O2sygxFRdpNLh2nFaKhC0enBudJmWRhoL/D7OHWBiQE=; b=RDMmnwCayyL9Cijt34LYP4ualXiSjypFegb687fs5nmOGm7MwAW7NKjasyFTmyAEKY O9dOKAn38Y5KSKgkKluTXJrq94hrrEBqSt8p9bsW4RpJiziX2CQiaWr9Gg5SHyzzW6t9 SFLKNaMW06nrpsj5cd0NTVNiPe/ZjSVz7VvH5JAvs8aF5XF9eaKXi0hYN7fKXbTph4ma oTcGlgBy3Ot+kHn/Nm8QOe7t4uYcepyCIeg7i1gW6R22SceqLNGPOQJsCJHVizwtK8pG 9LCUgkfc7PEVG2z8uxKYd9uj98ugoXEfH4PP58RBWm9hlvM7y4jsZPHyEtJGCLDAhQ23 kbow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=O2sygxFRdpNLh2nFaKhC0enBudJmWRhoL/D7OHWBiQE=; b=LKxhu2fq7fM+3R2XQrRISNZs1W8uCV3XNs6/xWK612zBdzjLQHvUiXhMdLZ0bSDnfM WJ7M3UgVDRbD5GglFxYqA3pZGjqDHZbnj1RnyphgFHBuhXw/oIVpdzQnwcS9jZ4+UAdj uZLWMg6U8juvZeO+/jd/B1smzg/AOycg2EKfG+snFTLJ6zwa3pvhGL7WRbC644aWhTe5 OXHj6KrDurCWgoX5HbiWbeK2GA+gHsbS6UfZ2GFE/1cB77WMLP59lfaX1ZG8M6RoF3QZ 8UuPrQrnvXcQywgrSFt2n+1AwzCtQ8Wbnvz40hiFscq/Fi6Zh40DORA/WoSqASrgSRf2 7FlQ== X-Gm-Message-State: AGRZ1gJ2iEWyS4/br0D9qosY2KqNug6OurAUrbb4zMOxLVeV3kWacr9e XS92+wFZI3bY8+XW9APROuWQC/Rq X-Google-Smtp-Source: AJdET5cSDbZ3kVzw2sLgvCyNg21QcS/dH/GX4qQvYklDilbEOV66c5GaLf3Ex/xJ9bgQYsPblCrBqw== X-Received: by 2002:ae9:e414:: with SMTP id q20mr6433425qkc.205.1541079993377; Thu, 01 Nov 2018 06:46:33 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.32 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:32 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 6/7] revision.c: generation-based topo-order algorithm Date: Thu, 1 Nov 2018 13:46:22 +0000 Message-Id: <20181101134623.84055-7-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 | 195 +++++++++++++++++++++++++++++++++++++++++++++++++++-- revision.h | 2 + 3 files changed, 194 insertions(+), 7 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..4ef47d2fb4 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,31 +2896,215 @@ static int mark_uninteresting(const struct object_id *oid, return 0; } -struct topo_walk_info {}; +define_commit_slab(indegree_slab, int); +define_commit_slab(author_date_slab, timestamp_t); + +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_cutoff) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->explore_queue)) && + c->generation >= gen_cutoff) + 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); + + 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, + uint32_t gen_cutoff) +{ + struct topo_walk_info *info = revs->topo_walk_info; + struct commit *c; + while ((c = prio_queue_peek(&info->indegree_queue)) && + c->generation >= gen_cutoff) + 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; + + if (parse_commit_gently(c, 1)) + continue; + + test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED); + test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE); + + if (c->generation < info->min_generation) + info->min_generation = c->generation; + + *(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, info->min_generation); + + 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)); } + + 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, info->min_generation); + } + + pi = indegree_slab_at(&info->indegree, parent); + + (*pi)--; + if (*pi == 1) + prio_queue_put(&info->topo_queue, parent); + + if (revs->first_parent_only) + return; + } } int prepare_revision_walk(struct rev_info *revs) 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 Thu Nov 1 13:46:23 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10663985 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 9A0D9109C for ; Thu, 1 Nov 2018 13:46:39 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8FD992BBC3 for ; Thu, 1 Nov 2018 13:46:39 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 823E32BC7B; Thu, 1 Nov 2018 13:46:39 +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 11BA42BBC3 for ; Thu, 1 Nov 2018 13:46:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728716AbeKAWti (ORCPT ); Thu, 1 Nov 2018 18:49:38 -0400 Received: from mail-qk1-f196.google.com ([209.85.222.196]:43420 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727963AbeKAWth (ORCPT ); Thu, 1 Nov 2018 18:49:37 -0400 Received: by mail-qk1-f196.google.com with SMTP id r71so12265516qkr.10 for ; Thu, 01 Nov 2018 06:46:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=xfOpbrH3Foli8dcwKpuNHg3WgKDlWxb4bmL4ZzG2yiU=; b=AF14dEIS7zrIlbZIgSGt/XmoGR4jPCq+eGtC9p3LpE1eI820mY98Tf7CVH60Ku70mX CwXmDD30u3yvM3bnYvfw2WAtFJnLy4AxctZuNv8MIHuT+bWdsEIA5N4SWf7RjLeVvrOJ BW1Fm2PDT0zqUkyrLE0tfGDAGSzisW9cjYB1Y9edmLARFKSC9P7+iwc7HSkB9MA23u3i 6k35IvAZc264p8l5+9340NYKzN8Cw6Y6WUVFRbiWvo/Y0jk9bKXE6xrM9e6AmgzZEeZI V4YAHyNgLaAM4P0PAMmMezi5/EtE2+InvGzKiU9A9h6ejexsObYc64M+oMGlO+e3pr2i v+Yg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=xfOpbrH3Foli8dcwKpuNHg3WgKDlWxb4bmL4ZzG2yiU=; b=Kbzc7t55ylWb8sshSI1qJyNeAd2DyzRkItFMoCrhQK1Id7e2V8tIR1SW5kwbLyQ75F 0TN+rc3UYXLQaNguXTni5CcAP7/oAhS0N02l6etSP8UTDIwlogXL/GB9HHLmusgFuJm6 jl8fzprGZto3mQVFnlts4iHKltiSOdmVt1XDh0lKxHmPTCiXD3FVAoT9gjxNGr2UoSaS KH0GqrQd3tYCsD0XG7HQBx4TIIPtiY7yeRmjdLQzYZ+C+GLR/dqNZYG28oa5fOO6vJOU Z+qM8AyzvwKAML8dEv/VYni2eZTfe1sshEdP3rcmOrukhSFrCaBx3lPn0V8w2QISVRgG TOEg== X-Gm-Message-State: AGRZ1gIV+0jUOMFWYomkr/tF3r8vhJIxIl8330kdfxeopfpjtqNgbO1Z wSvW3BKyUTD4irjfk/Jfu/bjcN5K X-Google-Smtp-Source: AJdET5cxeTq0bi3e0cWrmntEjWgkCccs4SsP5c1FrAnq+K5pm5mVvN36pCjUL9biZNs80E6vS+G/Og== X-Received: by 2002:a37:4c41:: with SMTP id z62mr6467957qka.206.1541079994590; Thu, 01 Nov 2018 06:46:34 -0700 (PDT) Received: from stolee-linux.mshome.net ([167.220.148.125]) by smtp.gmail.com with ESMTPSA id f75sm7347357qkf.96.2018.11.01.06.46.33 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 01 Nov 2018 06:46:33 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: gitster@pobox.com, avarab@gmail.com, szeder.dev@gmail.com, peff@peff.net, jnareb@gmail.com, Derrick Stolee Subject: [PATCH v5 7/7] t6012: make rev-list tests more interesting Date: Thu, 1 Nov 2018 13:46:23 +0000 Message-Id: <20181101134623.84055-8-dstolee@microsoft.com> X-Mailer: git-send-email 2.19.1.542.gc4df23f792 In-Reply-To: <20181101134623.84055-1-dstolee@microsoft.com> References: <20181101134623.84055-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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' '