From patchwork Thu Nov 18 16:49:14 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627375 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5B263C433F5 for ; Thu, 18 Nov 2021 16:49:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 390C261B29 for ; Thu, 18 Nov 2021 16:49:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233811AbhKRQwx (ORCPT ); Thu, 18 Nov 2021 11:52:53 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52780 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233742AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 48262218B8 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ivlBUFy6KLRqxRf+OtPU/FcocZMZLDnmlNbcKj3V+UQ=; b=Xc+A4o1YqkwTuMfIe8Y+D4d+1I7I/kmNTlTzj0teVAYRVzrRUDqVgsZSuU+T1pT/7X4QHh vsGzym3B05xSxZYli5Gl/9LsAjnVyP3ueNBpa7+Z4NhcshmZG4u17BPAGda68LqpqYQDxH m3aNa5v9tSKgKyrpQ02LlBD+pHWYgsM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ivlBUFy6KLRqxRf+OtPU/FcocZMZLDnmlNbcKj3V+UQ=; b=fJVRzrxfYxr/Vp3eupT6X1BVSBNe/gm+zH8rIyfLATkYcEewgDs8ERFckuPo2AFin5vxQw IOrz3GH8BVUPa5DQ== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 1E7EDA3B8A; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 743E91E0679; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 01/27] bisect: Fixup test rev-list-bisect/02 Date: Thu, 18 Nov 2021 17:49:14 +0100 Message-Id: <20211118164940.8818-2-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 2 from t6002-rev-list-bisect.sh expects 'c2' as the bisection point but b2 is an equivalent choice. Improve the test to accept both. Signed-off-by: Jan Kara --- t/t6002-rev-list-bisect.sh | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh index b95a0212adff..48db52447fd3 100755 --- a/t/t6002-rev-list-bisect.sh +++ b/t/t6002-rev-list-bisect.sh @@ -247,8 +247,9 @@ test_expect_success 'set up fake --bisect refs' ' test_expect_success 'rev-list --bisect can default to good/bad refs' ' # the only thing between c3 and c1 is c2 git rev-parse c2 >expect && - git rev-list --bisect >actual && - test_cmp expect actual + git rev-parse b2 >>expect && + actual=$(git rev-list --bisect) && + grep &>/dev/null $actual expect ' test_expect_success 'rev-parse --bisect can default to good/bad refs' ' From patchwork Thu Nov 18 16:49:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627371 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3A22BC433EF for ; Thu, 18 Nov 2021 16:49:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 112CB61A8A for ; Thu, 18 Nov 2021 16:49:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233797AbhKRQwv (ORCPT ); Thu, 18 Nov 2021 11:52:51 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52772 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233734AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 4376C218B0 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=R24rzMp4bXbzycTMsB26icFWttDt9+TzzbC2PvKxCN0=; b=KJMH9o9zei+xF4S+uJosoQJC5TwpQxIc9dIbEYvHG0CRyM5ABE9tJ+qMWi7DlQpNQOQ76m 4oo5Nqc+ekYAzq6k5Pevqc+Lsr29J3MngGct6C2TFpKT4ZeEieLFnpJyCM7m+1ZHoRYQHc YXLO1SV/Q53QO4LQvzfygtPkTE4Zd5M= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=R24rzMp4bXbzycTMsB26icFWttDt9+TzzbC2PvKxCN0=; b=27JRLk4IvJizX/u9FmkIqihmZ7SYgTpIzm9tklbgOoVqUbIrCLCPWH1n7wqq6M4PB5oy5C vl5UeU0T6bp6ltBQ== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 1E6D5A3B89; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 762501F2C9D; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 02/27] bisect: Fixup bisect-porcelain/17 Date: Thu, 18 Nov 2021 17:49:15 +0100 Message-Id: <20211118164940.8818-3-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 17 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests first HASH3 where HASH2 and HASH3 are equivalent choices. Make sure test correctly handles both choices, add test variant to properly test commit skipping in the second case. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 1be85d064e76..f8cfdd3c36d2 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -197,11 +197,27 @@ test_expect_success 'bisect skip: successful result' ' test_when_finished git bisect reset && git bisect reset && git bisect start $HASH4 $HASH1 && - git bisect skip && + if [ $(git rev-parse HEAD) == $HASH3 ]; then + git bisect skip + fi && git bisect bad > my_bisect_log.txt && grep "$HASH2 is the first bad commit" my_bisect_log.txt ' +# $HASH1 is good, $HASH4 is bad, we skip $HASH2 +# but $HASH3 is good, +# so we should find $HASH4 as the first bad commit +test_expect_success 'bisect skip: successful result' ' + test_when_finished git bisect reset && + git bisect reset && + git bisect start $HASH4 $HASH1 && + if [ $(git rev-parse HEAD) == $HASH2 ]; then + git bisect skip + fi && + git bisect good > my_bisect_log.txt && + grep "$HASH4 is the first bad commit" my_bisect_log.txt +' + # $HASH1 is good, $HASH4 is bad, we skip $HASH3 and $HASH2 # so we should not be able to tell the first bad commit # among $HASH2, $HASH3 and $HASH4 From patchwork Thu Nov 18 16:49:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627373 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 144A9C433FE for ; Thu, 18 Nov 2021 16:49:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id ECA0961B39 for ; Thu, 18 Nov 2021 16:49:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233805AbhKRQww (ORCPT ); Thu, 18 Nov 2021 11:52:52 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57588 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233746AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 524C41FD39 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Wlen4cf+aEJt/FgD27jOu/Drnv8TKfRrfQK+828Eh2c=; b=0bhV8VS63IlO6C0MY4/QHc8qIfvyGVgWZyCY0XqQKbY0+ey0LyWbLy+RYqei/BjdwDRZNL Pa8rabsLpm4rfogI3WRurqqCNI3aDqDzhEkH3CxwNPfnIeVzlXqILV5oh+0V9f9i5PMkeG mj5LFRZCqiPLT+gkiVlik1R5cEWUTBg= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Wlen4cf+aEJt/FgD27jOu/Drnv8TKfRrfQK+828Eh2c=; b=fBeexZmBfGF+z8/0luaBiU3TdC/OqseIIDy7Wn8nLucqHXjazWT4MUWgy/O6+66fAkirXW te7FNYdnanwW+rDw== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 2D6D2A3B8C; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 795541F2C9F; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 03/27] bisect: Fixup test bisect-porcelain/20 Date: Thu, 18 Nov 2021 17:49:16 +0100 Message-Id: <20211118164940.8818-4-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 20 from t6030-bisect-porcelain.sh fails if the bisection algorithm picks HASH2 instead of HASH3 as the first step although these are equivalent. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index f8cfdd3c36d2..13f7deea4d81 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -240,8 +240,13 @@ test_expect_success 'bisect skip: cannot tell between 3 commits' ' test_expect_success 'bisect skip: cannot tell between 2 commits' ' test_when_finished git bisect reset && git bisect start $HASH4 $HASH1 && - git bisect skip && - test_expect_code 2 git bisect good >my_bisect_log.txt && + if [ $(git rev-parse HEAD) == $HASH2 ]; then + results=('good' 'skip') + else + results=('skip' 'good') + fi && + git bisect ${results[0]} && + test_expect_code 2 git bisect ${results[1]} >my_bisect_log.txt && grep "first bad commit could be any of" my_bisect_log.txt && ! grep $HASH1 my_bisect_log.txt && ! grep $HASH2 my_bisect_log.txt && From patchwork Thu Nov 18 16:49:17 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627369 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 92A7EC433F5 for ; Thu, 18 Nov 2021 16:49:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7154061A8A for ; Thu, 18 Nov 2021 16:49:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233790AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57582 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233741AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 49B7D1FD38 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=S1a/czSZhfUnhLXVMqptQNShNNknPs7qQBVC0h/JUvM=; b=keOsc7lVsvjwfYzD/A+smoaeFSJr3tGa99njXvOpXJ8SmoYqYbJOvSrpqasuiYM4A6sNqK Z725sYcJAFjc4dos5NneKyJkrgdFKk4uI+vBHiSpUh0lc2miMnbAYxZb0lpdgdF4U37j+v Y3apxVcb6eJjSR2XIepVIzH+FF5sX5M= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=S1a/czSZhfUnhLXVMqptQNShNNknPs7qQBVC0h/JUvM=; b=7inL6WwR+6We7hnMh3U0k3oIt8FWZ4oL7l05zw/kpYsosdafvoQNAbHPQmr19Jvg1TunOE 7SmSml1CdgUInqCA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 2A724A3B8B; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 7D40A1F2CA2; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 04/27] bisect: Fixup bisect-porcelain/32 Date: Thu, 18 Nov 2021 17:49:17 +0100 Message-Id: <20211118164940.8818-5-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 32 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests HASH6 after HASH4 when HASH5 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 13f7deea4d81..d693c0002098 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -395,9 +395,13 @@ test_expect_success 'bisect does not create a "bisect" branch' ' test "$rev_hash4" = "$HASH4" && git branch -D bisect && git bisect good && + rev_hash=$(git rev-parse --verify HEAD) && + if [ $rev_hash == "$HASH5" ]; then + git bisect good && + rev_hash=$(git rev-parse --verify HEAD) + fi && git branch bisect && - rev_hash6=$(git rev-parse --verify HEAD) && - test "$rev_hash6" = "$HASH6" && + test "$rev_hash" = "$HASH6" && git bisect good > my_bisect_log.txt && grep "$HASH7 is the first bad commit" my_bisect_log.txt && git bisect reset && From patchwork Thu Nov 18 16:49:18 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627379 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0ECA8C433EF for ; Thu, 18 Nov 2021 16:49:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E67166138D for ; Thu, 18 Nov 2021 16:49:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233832AbhKRQw4 (ORCPT ); Thu, 18 Nov 2021 11:52:56 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57600 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233752AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 751271FD3A for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=diWe5KBRJnS5BEgTzQ7aWOywkai+rWrsV6GF881RCPI=; b=IupUE92ig1STvICd7E4qecCwgkXGFu9SS5zXolCp9Z+btLxjL40CF/CYtjkimWxCb1cajf 8qR5GlmCeoyT/vqY/mN7ahUm6Wl27SlCVVhyZYnTeI0cIcSChQa8mNRsMrr+tpXBH75UdS W8HuvI/HcHTCuxEWoYhPXWH4fkFcqXc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=diWe5KBRJnS5BEgTzQ7aWOywkai+rWrsV6GF881RCPI=; b=G8jD0VXW2VopDAIlbkQUtvco+2+vTVGxSaBpSXnnQKEFJ0tOxetdVapqKHN/9AJ6Wz6ru1 9XQxUc/R+2PwEHAA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 678BBA3B93; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 811731F2CA3; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 05/27] bisect: Fixup bisect-porcelain/34 Date: Thu, 18 Nov 2021 17:49:18 +0100 Message-Id: <20211118164940.8818-6-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 34 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests HASH6 after merge base when HASH5 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index d693c0002098..ed81a6403b63 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -433,7 +433,7 @@ test_expect_success 'good merge base when good and bad are siblings' ' grep $HASH4 my_bisect_log.txt && git bisect good > my_bisect_log.txt && ! grep "merge base must be tested" my_bisect_log.txt && - grep $HASH6 my_bisect_log.txt && + grep -E "$HASH5|$HASH6" my_bisect_log.txt && git bisect reset ' test_expect_success 'skipped merge base when good and bad are siblings' ' From patchwork Thu Nov 18 16:49:19 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627385 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5113AC433EF for ; Thu, 18 Nov 2021 16:50:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2CB7E61A8A for ; Thu, 18 Nov 2021 16:50:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233854AbhKRQw7 (ORCPT ); Thu, 18 Nov 2021 11:52:59 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52794 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233747AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 6F966218D5 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=CtoMAbsYeDByBMa/BABCjE5/QXzQy4aCbXxjaicEYnA=; b=LK3/X9mglyS6XJou1vpUbQmbMjI4RraQpo8U9mX+dJnf61x88psspNoA282u8y2UCku4Dp fYIuul1hYihmQ2XhvaZ5hXfBWF+5awqfUbML8P4gTB9iwjv4m7ibUqb+jogZUVH8Ypmx8v KcL3BLm7SgJCfeCZxtksQUjytzdp0EE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=CtoMAbsYeDByBMa/BABCjE5/QXzQy4aCbXxjaicEYnA=; b=t+IB3ilG5gJdBxOFNO/JLIpYA6zcUlDBTqnIHReoHlXqOLt95eyXgDUlDw/nOkyiNMn0lQ HN94+jcfD3b/sCBQ== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 63A2DA3B91; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 856EE1F2CA4; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 06/27] bisect: Fixup bisect-porcelain/40 Date: Thu, 18 Nov 2021 17:49:19 +0100 Message-Id: <20211118164940.8818-7-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 40 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests HASH6 after merge base when HASH5 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index ed81a6403b63..0f2a91996393 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -524,8 +524,9 @@ test_expect_success 'optimized merge base checks' ' grep "$HASH4" my_bisect_log.txt && git bisect good > my_bisect_log2.txt && test -f ".git/BISECT_ANCESTORS_OK" && - test "$HASH6" = $(git rev-parse --verify HEAD) && - git bisect bad && + rev_hash=$(git rev-parse --verify HEAD) && + test "$HASH5" = "$rev_hash" -o "$HASH6" = "$rev_hash" && + git bisect bad "$HASH6" && git bisect good "$A_HASH" > my_bisect_log4.txt && test_i18ngrep "merge base must be tested" my_bisect_log4.txt && test_path_is_missing ".git/BISECT_ANCESTORS_OK" From patchwork Thu Nov 18 16:49:20 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627401 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 38C28C433EF for ; Thu, 18 Nov 2021 16:50:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 267016138D for ; Thu, 18 Nov 2021 16:50:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233907AbhKRQxK (ORCPT ); Thu, 18 Nov 2021 11:53:10 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57646 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233773AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 7CBF71FD3E for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=1pyOw1MAjgaQTX2QSTF+ebbWNKx+ZrqnpMJuQb6wcHQ=; b=rCp6INoRpB6CdjaM1lQPwjTw4NBk94kwmPdaVc10akR5hzX/TPFJN2QckNjJUnvBRRE2fF w2G1ecOmsQ3EbUPOQ8CubqSJb8OZG5NLwh82ja3hvwd4VsPOj5BPtUMCZPgmXXBSjGoNFR F/zsJQzIiv7UtYyiTCfzQV40EgRUd3M= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=1pyOw1MAjgaQTX2QSTF+ebbWNKx+ZrqnpMJuQb6wcHQ=; b=flkMddKO7W1LI6tTJmRTgFFhAcmPjIKm67SKPWXiJd/QkMyiMjRgXRfLTcumwtO7zc3n27 IfPrwHPKgQjbntDg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 62110A3B90; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 8852E1F2CA5; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 07/27] bisect: Remove duplicated bisect-porcelain/48 Date: Thu, 18 Nov 2021 17:49:20 +0100 Message-Id: <20211118164940.8818-8-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 48 from t6030-bisect-porcelain.sh claims it tests whether bisection fails if tree is broken on start commit. However that actually does not happen because the bisection really only fails because the first trial point we choose happens to be broken. Furthermore there is another equivalent trial point which is not broken so the test is not reliable. Remove it as test 49 tests the same behavior is a more reliable setting. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 6 ------ 1 file changed, 6 deletions(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 0f2a91996393..4ec7b5b5a72e 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -675,12 +675,6 @@ cat > expected.missing-tree.default <error.txt && - test_cmp expected.missing-tree.default error.txt -' - test_expect_success 'bisect fails if tree is broken on trial commit' ' git bisect reset && test_must_fail git bisect start BROKEN_HASH9 BROKEN_HASH4 2>error.txt && From patchwork Thu Nov 18 16:49:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627381 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id AAF60C4332F for ; Thu, 18 Nov 2021 16:49:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8EF846138D for ; Thu, 18 Nov 2021 16:49:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233830AbhKRQwz (ORCPT ); Thu, 18 Nov 2021 11:52:55 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57606 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233753AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 776C11FD3C for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=iGwuiCS51dh/1BotnKaVyj381ZiDx17kLZxreKVQl0M=; b=F9ejmCO3oyihNCqgOtmLHRFweF5zm3pYzWNtmT8n24UFEOeN47Hz0F0HU+v+lVTUPOJ5Z4 R9ca2aV9FPBoiZ3GGx97o3+tJlknyLr9xskQ/k4Skpn9yea43ZcSKIdTbit8FkbV1esyS6 UULHpejaJGTEY0zrdHw81HblbULXwBs= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=iGwuiCS51dh/1BotnKaVyj381ZiDx17kLZxreKVQl0M=; b=hCV1jO4/sGCAvAu8Wzz9iTVhcDAQnzDYxJde4MEmjH2bQuK2ZpMoV9s9Q6UgV5CBrNUGjt QSWKovjRY1IShwDg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 60378A3B8E; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 8B8DF1F2CA6; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 08/27] bisect: Fixup bisect-porcelain/50 Date: Thu, 18 Nov 2021 17:49:21 +0100 Message-Id: <20211118164940.8818-9-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 50 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests BROKEN_HASH6 when BROKEN_HASH5 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 4ec7b5b5a72e..79f253f01b00 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -689,10 +689,23 @@ check_same() test_cmp_rev "$1" "$2" } +check_oneof() +{ + base="$1" + shift + echo "Checking $base is among $@" && + for rev in "$@"; do + if test_cmp_rev "$base" "$rev"; then + return 0 + fi + done + return 1 +} + test_expect_success 'bisect: --no-checkout - start commit bad' ' git bisect reset && git bisect start BROKEN_HASH7 BROKEN_HASH4 --no-checkout && - check_same BROKEN_HASH6 BISECT_HEAD && + check_oneof BISECT_HEAD BROKEN_HASH5 BROKEN_HASH6 && git bisect reset ' From patchwork Thu Nov 18 16:49:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627383 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id F2547C433F5 for ; Thu, 18 Nov 2021 16:49:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DA50A6138D for ; Thu, 18 Nov 2021 16:49:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233761AbhKRQw5 (ORCPT ); Thu, 18 Nov 2021 11:52:57 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52792 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233750AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 6FE70218E0 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=axs7WhdHHsiDyTEbW534DheU46cT8sLHfTiC7IkGEQQ=; b=EU5WoHg9wsiaXHCtzgEld6VPz2eNKNsYSyHuo9xYsfxD5PeNhLpzo8VroqV2ULWwr/lUer +7hblE2pQLznAh8QCzb/PkK68rVweO3UP2/WMZ2qE/65c/muwb7PNcqwIn6ia4vVB8qcC9 AgraGdpRn7si/tBVRehVqAJ+8VFy4gE= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=axs7WhdHHsiDyTEbW534DheU46cT8sLHfTiC7IkGEQQ=; b=paAx3ytsphJ0xIN7Cmk7rCyqPsbGTF42dKxdWE3oUnwIMThYjP0w+srNHyDBuH35ppQQdL Hq9q2FBJScEjfeBA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 604B6A3B8F; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 8E78A1F2CA8; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 09/27] bisect: Fixup bisect-porcelain/54 Date: Thu, 18 Nov 2021 17:49:22 +0100 Message-Id: <20211118164940.8818-10-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 54 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests BROKEN_HASH8 as the second bisection point when BROKEN_HASH7 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 79f253f01b00..46d67929e1e5 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -743,7 +743,11 @@ test_expect_success 'bisect: --no-checkout - target after breakage' ' git bisect start broken BROKEN_HASH4 --no-checkout && check_same BROKEN_HASH6 BISECT_HEAD && git bisect good BISECT_HEAD && - check_same BROKEN_HASH8 BISECT_HEAD && + check_oneof BISECT_HEAD BROKEN_HASH7 BROKEN_HASH8 && + if check_same BROKEN_HASH7 BISECT_HEAD; then + git bisect good BISECT_HEAD && + check_same BROKEN_HASH8 BISECT_HEAD + fi && test_must_fail git bisect good BISECT_HEAD && check_same BROKEN_HASH9 bisect/bad && git bisect reset From patchwork Thu Nov 18 16:49:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627377 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B4B95C433FE for ; Thu, 18 Nov 2021 16:49:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9F6256138D for ; Thu, 18 Nov 2021 16:49:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233827AbhKRQwz (ORCPT ); Thu, 18 Nov 2021 11:52:55 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57598 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233751AbhKRQwt (ORCPT ); Thu, 18 Nov 2021 11:52:49 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 7556B1FD3B for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=5u0gR8S2YhsGDhIzIgdL+6Z5zuuzGq1jMQ8S4UfHUaE=; b=BzAJ9/w0011BdChO7sf3e2/h7WXiNLTHcL8lkW7CyB0r5g76IykFHABfZf4DQUnk9NGCyz YwRq4ZBJsi294oZTdUcsiIa/BR6yY8CfiQQ57byZ9QnkRzhMdjRM2NBm+JtokRB2986Tha tCLfO8k6UFNlFTdMY7qLK5u8SFvYak4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=5u0gR8S2YhsGDhIzIgdL+6Z5zuuzGq1jMQ8S4UfHUaE=; b=aLdFhNkTlea4HbxHyOcuO+BYLiRiAqFzD5CN49IsHr/qQBlSLQ7dxcP96kG+85xVMOJMSP I2+TRV1r6Trz/ECA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 69C22A3B94; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 9260C1F2CA9; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 10/27] bisect: Fixup bisect-porcelain/58 Date: Thu, 18 Nov 2021 17:49:23 +0100 Message-Id: <20211118164940.8818-11-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Test 58 from t6030-bisect-porcelain.sh assumes that bisection algorithm suggests HASH6 as the last bisection step when HASH5 is an equivalent choice. Fix the test to work in both cases. Signed-off-by: Jan Kara --- t/t6030-bisect-porcelain.sh | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 46d67929e1e5..3363dc765b9d 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -811,7 +811,8 @@ test_expect_success '"git bisect bad HEAD" behaves as "git bisect bad"' ' git bisect start HEAD $HASH1 && git bisect good HEAD && git bisect bad HEAD && - test "$HASH6" = $(git rev-parse --verify HEAD) && + rev=$(git rev-parse --verify HEAD) && + test "$HASH5" = "$rev" -o "$HASH6" = "$rev" && git bisect reset ' From patchwork Thu Nov 18 16:49:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627393 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 73A0FC433FE for ; Thu, 18 Nov 2021 16:50:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5DDA961A8A for ; Thu, 18 Nov 2021 16:50:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233896AbhKRQxF (ORCPT ); Thu, 18 Nov 2021 11:53:05 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57642 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233771AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 7C1911FD3D for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=N0xoVlPsVNNDIwvOw/PW3D9wabAqSlx7T7hqMqsMcyQ=; b=H2764KhGu/8HGUyXi0HkOeZwbqMVAHHS1R6oQAp/x+k4nDzrCiQ8twd6EXedpfjrcP8gq7 dHEUShG/69eZT2sQlBG3pHRDTdsOpZKltm7vITKTaDBR21Bi8Yidj132wPp2xcHHiJ/t0t Z2BCUNrSxvf2Uu/CztCmuZJz3Bwkzzk= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=N0xoVlPsVNNDIwvOw/PW3D9wabAqSlx7T7hqMqsMcyQ=; b=itoawXYHSUfsYcnefNVy53jJn4S6tDp2QE74Dx0umXskk9/GBUf5ua6NICY8fNefAMjQFd 0TCe+DPBtB2dMdBg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 63C6FA3B92; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 963591F2CAA; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 11/27] bisect: Fix bisection debugging Date: Thu, 18 Nov 2021 17:49:24 +0100 Message-Id: <20211118164940.8818-12-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org show_list() dumps commit weights associated with each commit. Thus it needs commit_weight slab already initialized. Move initialization of commit_weight slab before the first show_list() call. Signed-off-by: Jan Kara --- bisect.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/bisect.c b/bisect.c index 888949fba6b5..ab264b8ca879 100644 --- a/bisect.c +++ b/bisect.c @@ -395,8 +395,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches, struct commit_list *list, *p, *best, *next, *last; int *weights; - show_list("bisection 2 entry", 0, 0, *commit_list); init_commit_weight(&commit_weight); + show_list("bisection 2 entry", 0, 0, *commit_list); /* * Count the number of total and tree-changing items on the From patchwork Thu Nov 18 16:49:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627413 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6BED1C43217 for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5408861B3B for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233971AbhKRQxQ (ORCPT ); Thu, 18 Nov 2021 11:53:16 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57648 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233777AbhKRQwv (ORCPT ); Thu, 18 Nov 2021 11:52:51 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 814AD1FD41 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=uaYKDs8+9+ozm+tdGvsQ+qbV3Ysqldseial9pSanCWs=; b=awg9NBFbRAZPojr9oyhueBvnqxVgNtCXMPI++4zPDlbiJXWj6UkrUJJ5sKd9FWhqkWrrPC jbTPhbi97D6N4Cji1H0eQ7f/t5zVMla5pJkIhInr2KBTC7QDKTfrLFUAXRP74Qh5ftINay q82TlulMZsJoPhst+bdTiTm4zZZi8Cw= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=uaYKDs8+9+ozm+tdGvsQ+qbV3Ysqldseial9pSanCWs=; b=NFPJ2cS60v7Uf/pNbSckoRsuLvAaBJTVWT8gxt9qJiS4ckhOv7wHMNkFjhMdVm0mRRgf9S 74IFjhkcodkahVDw== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 6BC0DA3B95; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 99D9F1F2CAB; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 12/27] bisect: Accept and store confidence with each decision Date: Thu, 18 Nov 2021 17:49:25 +0100 Message-Id: <20211118164940.8818-13-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org With each decision whether a commit is good or bad, accept an optional confidence argument and store it in bisect log and special file with probabilities a test is recording a 'bad' result. We will later use these probabilities to alter decisions about the next bisection point. Signed-off-by: Jan Kara --- bisect.c | 51 ++++++++++++++++ builtin/bisect--helper.c | 129 ++++++++++++++++++++++++++++++++------- fixedpoint.h | 29 +++++++++ 3 files changed, 186 insertions(+), 23 deletions(-) create mode 100644 fixedpoint.h diff --git a/bisect.c b/bisect.c index ab264b8ca879..0773a872c82b 100644 --- a/bisect.c +++ b/bisect.c @@ -16,8 +16,10 @@ #include "commit-reach.h" #include "object-store.h" #include "dir.h" +#include "fixedpoint.h" static struct oid_array good_revs; +static struct oid_array ptest_revs; static struct oid_array skipped_revs; static struct object_id *current_bad_oid; @@ -444,12 +446,17 @@ static int register_ref(const char *refname, const struct object_id *oid, int flags, void *cb_data) { struct strbuf good_prefix = STRBUF_INIT; + struct strbuf ptest_prefix = STRBUF_INIT; + strbuf_addstr(&good_prefix, term_good); strbuf_addstr(&good_prefix, "-"); + strbuf_addstr(&ptest_prefix, "ptest-"); if (!strcmp(refname, term_bad)) { current_bad_oid = xmalloc(sizeof(*current_bad_oid)); oidcpy(current_bad_oid, oid); + } else if (starts_with(refname, ptest_prefix.buf)) { + oid_array_append(&ptest_revs, oid); } else if (starts_with(refname, good_prefix.buf)) { oid_array_append(&good_revs, oid); } else if (starts_with(refname, "skip-")) { @@ -474,8 +481,46 @@ static GIT_PATH_FUNC(git_path_bisect_start, "BISECT_START") static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG") static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS") static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT") +static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES") static GIT_PATH_FUNC(git_path_head_name, "head-name") +static void read_bisect_confidences(void) +{ + struct strbuf str = STRBUF_INIT; + const char *filename = git_path_bisect_confidences(); + FILE *fp = fopen(filename, "r"); + + /* Just a regular bisection? */ + if (!fp) + return; + + while (strbuf_getline_lf(&str, fp) != EOF) { + fpnum_t prob; + char *spc; + char state; + struct object_id oid; + + strbuf_trim(&str); + spc = strchr(str.buf, ' '); + if (!spc) + die(_("Badly formatted content in file '%s': %s"), + filename, str.buf); + *spc = 0; + if (sscanf(spc + 1, "%c %" FPNUM_FMT, &state, &prob) != 2) + die(_("Cannot parse confidence in file '%s': %s"), + filename, spc+1); + if (state != 'g' && state != 'b') + die(_("Unknown test state in file '%s': '%c'"), + filename, state); + if (get_oid(str.buf, &oid)) + die(_("Cannot get oid of rev '%s' from file '%s'"), + str.buf, filename); + /* We'll use parsed data later */ + } + strbuf_release(&str); + fclose(fp); +} + static void read_bisect_paths(struct strvec *array) { struct strbuf str = STRBUF_INIT; @@ -661,6 +706,10 @@ static void bisect_rev_setup(struct repository *r, struct rev_info *revs, /* rev_argv.argv[0] will be ignored by setup_revisions */ strvec_push(&rev_argv, "bisect_rev_setup"); + /* + * We use only revision certainly known to be good or bad for limiting + * a search. + */ strvec_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid)); for (i = 0; i < good_revs.nr; i++) strvec_pushf(&rev_argv, good_format, @@ -1023,6 +1072,7 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix) read_bisect_terms(&term_bad, &term_good); if (read_bisect_refs()) die(_("reading bisect refs failed")); + read_bisect_confidences(); if (file_exists(git_path_bisect_first_parent())) bisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY; @@ -1172,6 +1222,7 @@ int bisect_clean_state(void) unlink_or_warn(git_path_bisect_run()); unlink_or_warn(git_path_bisect_terms()); unlink_or_warn(git_path_bisect_first_parent()); + unlink_or_warn(git_path_bisect_confidences()); /* Cleanup head-name if it got left by an old version of git-bisect */ unlink_or_warn(git_path_head_name()); /* diff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c index 28a2e6a5750b..f88feb8da949 100644 --- a/builtin/bisect--helper.c +++ b/builtin/bisect--helper.c @@ -9,6 +9,7 @@ #include "prompt.h" #include "quote.h" #include "revision.h" +#include "fixedpoint.h" static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS") static GIT_PATH_FUNC(git_path_bisect_expected_rev, "BISECT_EXPECTED_REV") @@ -19,6 +20,7 @@ static GIT_PATH_FUNC(git_path_head_name, "head-name") static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES") static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT") static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN") +static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES") static const char * const git_bisect_helper_usage[] = { N_("git bisect--helper --bisect-reset []"), @@ -26,8 +28,8 @@ static const char * const git_bisect_helper_usage[] = { N_("git bisect--helper --bisect-start [--term-{new,bad}= --term-{old,good}=]" " [--no-checkout] [--first-parent] [ [...]] [--] [...]"), N_("git bisect--helper --bisect-next"), - N_("git bisect--helper --bisect-state (bad|new) []"), - N_("git bisect--helper --bisect-state (good|old) [...]"), + N_("git bisect--helper --bisect-state (bad|new) [--confidence ] []"), + N_("git bisect--helper --bisect-state (good|old) [--confidence ] [...]"), N_("git bisect--helper --bisect-replay "), N_("git bisect--helper --bisect-skip [(|)...]"), N_("git bisect--helper --bisect-visualize"), @@ -254,18 +256,24 @@ static void log_commit(FILE *fp, char *fmt, const char *state, free(label); } -static int bisect_write(const char *state, const char *rev, +static int bisect_write(const char *state, const char *rev, fpnum_t confidence, const struct bisect_terms *terms, int nolog) { + const char *logstate = state; struct strbuf tag = STRBUF_INIT; struct object_id oid; struct commit *commit; FILE *fp = NULL; int res = 0; + /* Uncertain result? */ + if (one_of(state, terms->term_bad, terms->term_good, NULL) && + confidence != FP_ONE) + state = "ptest"; + if (!strcmp(state, terms->term_bad)) { strbuf_addf(&tag, "refs/bisect/%s", state); - } else if (one_of(state, terms->term_good, "skip", NULL)) { + } else if (one_of(state, terms->term_good, "skip", "ptest", NULL)) { strbuf_addf(&tag, "refs/bisect/%s-%s", state, rev); } else { res = error(_("Bad bisect_write argument: %s"), state); @@ -283,6 +291,24 @@ static int bisect_write(const char *state, const char *rev, goto finish; } + /* Store confidence if it is non-trivial */ + if (!strcmp(state, "ptest")) { + char cstate; + + fp = fopen(git_path_bisect_confidences(), "a"); + if (!fp) { + res = error_errno(_("couldn't open the file '%s'"), + git_path_bisect_confidences()); + goto finish; + } + if (!strcmp(logstate, terms->term_bad)) + cstate = 'b'; + else + cstate = 'g'; + fprintf(fp, "%s %c %" FPNUM_FMT "\n", rev, cstate, confidence); + fclose(fp); + } + fp = fopen(git_path_bisect_log(), "a"); if (!fp) { res = error_errno(_("couldn't open the file '%s'"), git_path_bisect_log()); @@ -290,10 +316,16 @@ static int bisect_write(const char *state, const char *rev, } commit = lookup_commit_reference(the_repository, &oid); - log_commit(fp, "%s", state, commit); + log_commit(fp, "%s", logstate, commit); - if (!nolog) - fprintf(fp, "git bisect %s %s\n", state, rev); + if (!nolog) { + if (!strcmp(state, "ptest")) { + fprintf(fp, "git bisect %s --confidence %lf %s\n", + logstate, fp_to_double(confidence), rev); + } else { + fprintf(fp, "git bisect %s %s\n", logstate, rev); + } + } finish: if (fp) @@ -612,6 +644,16 @@ static enum bisect_error bisect_auto_next(struct bisect_terms *terms, const char return bisect_next(terms, prefix); } +static int parse_confidence(const char *str, fpnum_t *confidence) +{ + double confd; + + if (sscanf(str, "%lf", &confd) != 1 || confd < 0 || confd > 1) + return error(_("invalid confidence '%s'"), str); + *confidence = double_to_fp(confd); + return 0; +} + static enum bisect_error bisect_start(struct bisect_terms *terms, const char **argv, int argc) { int no_checkout = 0; @@ -784,8 +826,8 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a write_file(git_path_bisect_names(), "%s\n", bisect_names.buf); for (i = 0; i < states.nr; i++) - if (bisect_write(states.items[i].string, - revs.items[i].string, terms, 1)) { + if (bisect_write(states.items[i].string, revs.items[i].string, + FP_ONE, terms, 1)) { res = BISECT_FAILED; goto finish; } @@ -854,6 +896,7 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a struct object_id oid, expected; struct strbuf buf = STRBUF_INIT; struct oid_array revs = OID_ARRAY_INIT; + fpnum_t confidence = FP_ONE; if (!argc) return error(_("Please call `--bisect-state` with at least one argument")); @@ -868,6 +911,15 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a argv++; argc--; + + if (argc > 0 && !strcmp(argv[0], "--confidence")) { + if (argc < 2) + return error(_("missing confidence argument")); + if (parse_confidence(argv[1], &confidence)) + return -1; + argv += 2; + argc -= 2; + } if (argc > 1 && !strcmp(state, terms->term_bad)) return error(_("'git bisect %s' can take only one argument."), terms->term_bad); @@ -912,7 +964,8 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a strbuf_release(&buf); for (i = 0; i < revs.nr; i++) { - if (bisect_write(state, oid_to_hex(&revs.oid[i]), terms, 0)) { + if (bisect_write(state, oid_to_hex(&revs.oid[i]), confidence, + terms, 0)) { oid_array_clear(&revs); return BISECT_FAILED; } @@ -946,39 +999,69 @@ static enum bisect_error bisect_log(void) static int process_replay_line(struct bisect_terms *terms, struct strbuf *line) { - const char *p = line->buf + strspn(line->buf, " \t"); - char *word_end, *rev; + char *p = line->buf + strspn(line->buf, " \t"); + char *word_end, *cmd; - if ((!skip_prefix(p, "git bisect", &p) && - !skip_prefix(p, "git-bisect", &p)) || !isspace(*p)) + if ((!skip_prefix(p, "git bisect", (const char **)&p) && + !skip_prefix(p, "git-bisect", (const char **)&p)) || !isspace(*p)) return 0; p += strspn(p, " \t"); + cmd = p; word_end = (char *)p + strcspn(p, " \t"); - rev = word_end + strspn(word_end, " \t"); + p = word_end + strspn(word_end, " \t"); *word_end = '\0'; /* NUL-terminate the word */ get_terms(terms); - if (check_and_set_terms(terms, p)) + if (check_and_set_terms(terms, cmd)) return -1; - if (!strcmp(p, "start")) { + if (!strcmp(cmd, "start")) { struct strvec argv = STRVEC_INIT; int res; - sq_dequote_to_strvec(rev, &argv); + sq_dequote_to_strvec(p, &argv); res = bisect_start(terms, argv.v, argv.nr); strvec_clear(&argv); return res; } - if (one_of(p, terms->term_good, - terms->term_bad, "skip", NULL)) - return bisect_write(p, rev, terms, 0); + if (one_of(cmd, terms->term_good, + terms->term_bad, "skip", NULL)) { + fpnum_t confidence = FP_ONE; + char *arg; + + arg = p; + word_end = (char *)p + strcspn(p, " \t"); + p = word_end + strspn(word_end, " \t"); + *word_end = '\0'; + if (!strcmp(arg, "--confidence")) { + if (!strcmp(cmd, "skip")) { + error(_("skipping does not take confidence")); + return -1; + } + if (!*p) { + error(_("missing bisect confidence argument")); + return -1; + } + arg = p; + word_end = (char *)p + strcspn(p, " \t"); + p = word_end + strspn(word_end, " \t"); + *word_end = '\0'; + if (parse_confidence(arg, &confidence)) + return -1; + arg = p; + } + if (!*arg) { + error(_("missing bisect revision")); + return -1; + } + return bisect_write(cmd, arg, confidence, terms, 0); + } - if (!strcmp(p, "terms")) { + if (!strcmp(cmd, "terms")) { struct strvec argv = STRVEC_INIT; int res; - sq_dequote_to_strvec(rev, &argv); + sq_dequote_to_strvec(p, &argv); res = bisect_terms(terms, argv.nr == 1 ? argv.v[0] : NULL); strvec_clear(&argv); return res; diff --git a/fixedpoint.h b/fixedpoint.h new file mode 100644 index 000000000000..addef223be2b --- /dev/null +++ b/fixedpoint.h @@ -0,0 +1,29 @@ +#ifndef FIXEDPOINT_H +#define FIXEDPOINT_H + +#include + +#define FIXEDPOINT_SHIFT 32 + +typedef uint64_t fpnum_t; + +#define FPNUM_FMT PRIu64 + +static inline const fpnum_t frac_to_fp(unsigned int n, unsigned int d) +{ + return (((fpnum_t)n) << FIXEDPOINT_SHIFT) / d; +} + +static inline const fpnum_t double_to_fp(double n) +{ + return (n * (1ULL << FIXEDPOINT_SHIFT)); +} + +static inline const double fp_to_double(fpnum_t n) +{ + return ((double)n) / (1ULL << FIXEDPOINT_SHIFT); +} + +#define FP_ONE frac_to_fp(1, 1) + +#endif From patchwork Thu Nov 18 16:49:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627395 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4321DC433EF for ; Thu, 18 Nov 2021 16:50:08 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2B1E461B2B for ; Thu, 18 Nov 2021 16:50:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233751AbhKRQxH (ORCPT ); Thu, 18 Nov 2021 11:53:07 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57644 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233769AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 80DD01FD40 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=JNck9KdNOF5Q1sHo+uYStEzLaVAX6KCJVKKc5Ex23hk=; b=AXwrQldK5RvA4Am0kC9xmkDKb/Df6VPJfIubkJeYX+vw/taZfjYD5LxHqnXyzt+YIKc6w+ DZLd3g/nY8qRWYibgQRkHqeRUqedDALKVWAkDmipHeXZ6RwUAK+ojEg8USr9xYcGDyU/7S 5x/Ycui8rkewbrXoTx2nCWVjopDtLcs= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=JNck9KdNOF5Q1sHo+uYStEzLaVAX6KCJVKKc5Ex23hk=; b=/tnENvhfbO4uNdFokMtEhJyotWXwXqjy2R42p/VI3odSGPy7Lz9MwC3YcD5bWyk8sg5ArW 7wBRwk1Uw4J4KOAA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 72B01A3B96; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id 9CF931F2CAC; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 13/27] bisect: Allow specifying desired result confidence Date: Thu, 18 Nov 2021 17:49:26 +0100 Message-Id: <20211118164940.8818-14-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Allow specifying desired result confidence for stochastic bisection when starting bisection. Store it and load it when doing bisection steps. Signed-off-by: Jan Kara --- bisect.c | 15 ++++++++++++++- builtin/bisect--helper.c | 22 +++++++++++++++++++++- fixedpoint.h | 1 + 3 files changed, 36 insertions(+), 2 deletions(-) diff --git a/bisect.c b/bisect.c index 0773a872c82b..f87753d0c67c 100644 --- a/bisect.c +++ b/bisect.c @@ -22,6 +22,8 @@ static struct oid_array good_revs; static struct oid_array ptest_revs; static struct oid_array skipped_revs; +static fpnum_t result_confidence; + static struct object_id *current_bad_oid; static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL}; @@ -482,15 +484,25 @@ static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG") static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS") static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT") static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES") +static GIT_PATH_FUNC(git_path_bisect_result_confidence, "BISECT_RESULT_CONFIDENCE") static GIT_PATH_FUNC(git_path_head_name, "head-name") static void read_bisect_confidences(void) { struct strbuf str = STRBUF_INIT; - const char *filename = git_path_bisect_confidences(); + const char *filename = git_path_bisect_result_confidence(); FILE *fp = fopen(filename, "r"); /* Just a regular bisection? */ + if (!fp) + return; + if (fscanf(fp, "%"FPNUM_FMT, &result_confidence) != 1) + die(_("Cannot parse result confidence in file '%s'"), filename); + fclose(fp); + + /* No uncertain bisection steps yet? */ + filename = git_path_bisect_confidences(); + fp = fopen(filename, "r"); if (!fp) return; @@ -1223,6 +1235,7 @@ int bisect_clean_state(void) unlink_or_warn(git_path_bisect_terms()); unlink_or_warn(git_path_bisect_first_parent()); unlink_or_warn(git_path_bisect_confidences()); + unlink_or_warn(git_path_bisect_result_confidence()); /* Cleanup head-name if it got left by an old version of git-bisect */ unlink_or_warn(git_path_head_name()); /* diff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c index f88feb8da949..5b46a8ca3fd9 100644 --- a/builtin/bisect--helper.c +++ b/builtin/bisect--helper.c @@ -21,12 +21,14 @@ static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES") static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT") static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN") static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES") +static GIT_PATH_FUNC(git_path_bisect_result_confidence, "BISECT_RESULT_CONFIDENCE") static const char * const git_bisect_helper_usage[] = { N_("git bisect--helper --bisect-reset []"), N_("git bisect--helper --bisect-terms [--term-good | --term-old | --term-bad | --term-new]"), N_("git bisect--helper --bisect-start [--term-{new,bad}= --term-{old,good}=]" - " [--no-checkout] [--first-parent] [ [...]] [--] [...]"), + " [--no-checkout] [--first-parent] [--confidence ]" + " [ [...]] [--] [...]"), N_("git bisect--helper --bisect-next"), N_("git bisect--helper --bisect-state (bad|new) [--confidence ] []"), N_("git bisect--helper --bisect-state (good|old) [--confidence ] [...]"), @@ -668,6 +670,7 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a struct object_id head_oid; struct object_id oid; const char *head; + fpnum_t confidence = FP_ONE; if (is_bare_repository()) no_checkout = 1; @@ -690,6 +693,16 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a no_checkout = 1; } else if (!strcmp(arg, "--first-parent")) { first_parent_only = 1; + } else if (!strcmp(arg, "--confidence")) { + i++; + if (argc <= i) + return error(_("missing confidence argument")); + if (parse_confidence(argv[i], &confidence)) + return -1; + if (confidence == FP_ONE) + return error(_("Absolute confidence not possible with stochastic bisection")); + if (confidence < FP_HALF) + return error(_("Target confidence of at least 0.5 needed for stochastic bisection")); } else if (!strcmp(arg, "--term-good") || !strcmp(arg, "--term-old")) { i++; @@ -809,6 +822,10 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a if (first_parent_only) write_file(git_path_bisect_first_parent(), "\n"); + if (confidence != FP_ONE) + write_file(git_path_bisect_result_confidence(), + "%" FPNUM_FMT "\n", confidence); + if (no_checkout) { if (get_oid(start_head.buf, &oid) < 0) { res = error(_("invalid ref: '%s'"), start_head.buf); @@ -917,6 +934,9 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a return error(_("missing confidence argument")); if (parse_confidence(argv[1], &confidence)) return -1; + if (is_empty_or_missing_file(git_path_bisect_result_confidence())) + return error(_("Stochastic bisection not started. Pass " + "desired target confidence to git bisect start.")); argv += 2; argc -= 2; } diff --git a/fixedpoint.h b/fixedpoint.h index addef223be2b..3f6234c6530a 100644 --- a/fixedpoint.h +++ b/fixedpoint.h @@ -25,5 +25,6 @@ static inline const double fp_to_double(fpnum_t n) } #define FP_ONE frac_to_fp(1, 1) +#define FP_HALF frac_to_fp(1, 2) #endif From patchwork Thu Nov 18 16:49:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627405 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 29A2CC433EF for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1536961A8A for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233929AbhKRQxN (ORCPT ); Thu, 18 Nov 2021 11:53:13 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57652 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233779AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 859551FD45 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=W65rbHW4EMr3ZKytxyCaIqMLh0Jl147sHGJcLmPSvfo=; b=wwQuDisOo+5KHL3CIRMMWTXTQOqDGdsrWGIxl6/cwC1ZWktjxYOVVa9Xr+G9yve6Z80Jm8 Eain+4Vx9YNirYPMiVtGwhfsRVODPlGO5flIEVHaEglpc1t0hu6U6xVDEhqcDhtx9NWDiV 7/+VfjRTEeM8QHOU8s8PxlpQULDbALw= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=W65rbHW4EMr3ZKytxyCaIqMLh0Jl147sHGJcLmPSvfo=; b=uCeBJGeLzLmtsYCHuR/UJmVASFtlO9SjfNA1HWG0oFfqO5btDjGiEC8EjCcHTsfrrNgCHF drsUSt+ABYJtQPAg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 78348A3B97; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id A004D1F2CAE; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 14/27] bisect: Use void * for commit_weight Date: Thu, 18 Nov 2021 17:49:27 +0100 Message-Id: <20211118164940.8818-15-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org For stochastic bisection we will need to store more information per commit. Make commit_weight slab store void * instead of int * so that we can reuse it for stochastic bisection as well. Signed-off-by: Jan Kara --- bisect.c | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/bisect.c b/bisect.c index f87753d0c67c..7416a57db4e3 100644 --- a/bisect.c +++ b/bisect.c @@ -77,19 +77,25 @@ static void clear_distance(struct commit_list *list) } } -define_commit_slab(commit_weight, int *); +define_commit_slab(commit_weight, void *); static struct commit_weight commit_weight; #define DEBUG_BISECT 0 +static inline int has_weight(struct commit_list *elem) +{ + return commit_weight.slab_size > 0 && + *commit_weight_at(&commit_weight, elem->item) != NULL; +} + static inline int weight(struct commit_list *elem) { - return **commit_weight_at(&commit_weight, elem->item); + return *(int *)*commit_weight_at(&commit_weight, elem->item); } static inline void weight_set(struct commit_list *elem, int weight) { - **commit_weight_at(&commit_weight, elem->item) = weight; + *(int *)*commit_weight_at(&commit_weight, elem->item) = weight; } static int count_interesting_parents(struct commit *commit, unsigned bisect_flags) @@ -163,7 +169,7 @@ static void show_list(const char *debug, int counted, int nr, (commit_flags & TREESAME) ? ' ' : 'T', (commit_flags & UNINTERESTING) ? 'U' : ' ', (commit_flags & COUNTED) ? 'C' : ' '); - if (*commit_weight_at(&commit_weight, p->item)) + if (has_weight(p)) fprintf(stderr, "%3d", weight(p)); else fprintf(stderr, "---"); From patchwork Thu Nov 18 16:49:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627387 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1BCFCC433EF for ; Thu, 18 Nov 2021 16:50:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0109761A8A for ; Thu, 18 Nov 2021 16:50:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233864AbhKRQxA (ORCPT ); Thu, 18 Nov 2021 11:53:00 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52818 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233766AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 84E98218F0 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=WXELKBo8uDsU1cFv5GK5dy25OPf51KgwTnrazDfAPbg=; b=SX8cLGbQkqLeE40j+H3pkKQKJzSf+VHq5cNYszKDbro9HMwKlWC3u3wdJOHE2R0mB3bG/j 359WIWkmfaB8ftQem1VuI9xRuU/7LJQMqHnLqM9MPVpW4Zq/zwSqKF21G1mNV7BhJkcCW5 cXs0gQiU1Y2H9fQ1FkO8+oXR3s+BVuU= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=WXELKBo8uDsU1cFv5GK5dy25OPf51KgwTnrazDfAPbg=; b=yDX8uK/5K43lZ4J7VnAVEbEP8uPjD3gwklXkFguqttx3I4oudjIJcN95GwilYjyLR8GQ88 WRGWxtx9yubgWkBw== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 79EC0A3B99; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id A46CE1F2CB1; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 15/27] bisect: Rename clear_distance() to clear_counted_flag() Date: Thu, 18 Nov 2021 17:49:28 +0100 Message-Id: <20211118164940.8818-16-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org clear_distance() only clears COUNTED flag. Rename the function to match what it does. No code changes. Signed-off-by: Jan Kara --- bisect.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bisect.c b/bisect.c index 7416a57db4e3..675e8d433760 100644 --- a/bisect.c +++ b/bisect.c @@ -68,7 +68,7 @@ static int count_distance(struct commit_list *entry) return nr; } -static void clear_distance(struct commit_list *list) +static void clear_counted_flag(struct commit_list *list) { while (list) { struct commit *commit = list->item; @@ -339,7 +339,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY) BUG("shouldn't be calling count-distance in fp mode"); weight_set(p, count_distance(p)); - clear_distance(list); + clear_counted_flag(list); /* Does it happen to be at half-way? */ if (!(bisect_flags & FIND_BISECTION_ALL) && From patchwork Thu Nov 18 16:49:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627403 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 06687C433F5 for ; Thu, 18 Nov 2021 16:50:22 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E337C6138D for ; Thu, 18 Nov 2021 16:50:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233872AbhKRQxL (ORCPT ); Thu, 18 Nov 2021 11:53:11 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57650 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233774AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 84EA61FD42 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=0l7Hqf9Tv6e3Szo71Wu9BxNjeHulm4d9oBijOO6mBR8=; b=zOeyqKOo2kpqzS0/eo9ofa05R+BhMtT9jBt7AD0UcDXAqkPtKl9gzAyKqItzGdosD9ymwJ juY8rwNjt3qe0FJZ4GH9r7zXZLWeFTOUj2+yTJnPbIIzjyyLFYt5KoEqBAmVQjn8to49IC HzxkS4t8/YvsUnawlVCOFlMU38y+EqY= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=0l7Hqf9Tv6e3Szo71Wu9BxNjeHulm4d9oBijOO6mBR8=; b=zCwtoCHlbE7onffFvG6eZ/3susGflw964GTYPRlf0ye9YpG8G9YEv3IDPCi4a2uoFC1VQR EsVnqro+2MDCHcBg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 79D30A3B98; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id A882D1F2CB3; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 16/27] bisect: Separate commit list reversal Date: Thu, 18 Nov 2021 17:49:29 +0100 Message-Id: <20211118164940.8818-17-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Item list reversal is part of code counting number of list items changing tree. Move it into the separate function and do the reversal after counting. The stochastic bisection will need to do more operations after the counting but before reversing the list. Signed-off-by: Jan Kara --- bisect.c | 29 +++++++++++++++++++++-------- 1 file changed, 21 insertions(+), 8 deletions(-) diff --git a/bisect.c b/bisect.c index 675e8d433760..8dc1eb7f9d82 100644 --- a/bisect.c +++ b/bisect.c @@ -398,11 +398,24 @@ static struct commit_list *do_find_bisection(struct commit_list *list, return best_bisection_sorted(list, nr); } + +static struct commit_list *reverse_list(struct commit_list *list) +{ + struct commit_list *p, *next, *last = NULL; + + for (p = list; p; p = next) { + next = p->next; + p->next = last; + last = p; + } + return last; +} + void find_bisection(struct commit_list **commit_list, int *reaches, int *all, unsigned bisect_flags) { int nr, on_list; - struct commit_list *list, *p, *best, *next, *last; + struct commit_list *list, *p, *best, *next, **pnext; int *weights; init_commit_weight(&commit_weight); @@ -410,25 +423,25 @@ void find_bisection(struct commit_list **commit_list, int *reaches, /* * Count the number of total and tree-changing items on the - * list, while reversing the list. + * list and trim uninteresting items from the list. */ - for (nr = on_list = 0, last = NULL, p = *commit_list; - p; - p = next) { + list = *commit_list; + pnext = &list; + for (nr = on_list = 0, p = list; p; p = next) { unsigned commit_flags = p->item->object.flags; next = p->next; if (commit_flags & UNINTERESTING) { + *pnext = next; free(p); continue; } - p->next = last; - last = p; + pnext = &p->next; if (!(commit_flags & TREESAME)) nr++; on_list++; } - list = last; + list = reverse_list(list); show_list("bisection 2 sorted", 0, nr, list); *all = nr; From patchwork Thu Nov 18 16:49:30 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627407 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4ABF7C4332F for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 318C761B3E for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233951AbhKRQxP (ORCPT ); Thu, 18 Nov 2021 11:53:15 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57654 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233760AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 895DD1FD48 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Sw4ZcsUC4u3YijjcSItb1VeXU9oNyBhEvya1p7Z44Lw=; b=IdpIRG8Q/I9FrWqgSC28VMccvU4cB9Ub0T/LIOmZAO3mzpGxaPmMTxcNpIytbCwIlM3WuX pCn/I/AQhV6Y8FR2qgzCH05tvZTclgx1K0tnvgVXAYgraNf8z0XpEvyaM136Mv+K0GDlw3 +xbAIxbNZps/Sedti4wo2k5IXd/2kZk= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Sw4ZcsUC4u3YijjcSItb1VeXU9oNyBhEvya1p7Z44Lw=; b=TGE7cyrqWkktC8zGv8WkajDub12OYNUoGk3ez4TLF2w8tuoMzv3L9yRAR98EfAgzRBe+q8 Yyu5dOJ1RWBzGcDA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 7E93FA3B9A; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id AC95A1F2CB4; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 17/27] bisect: Allow more complex commit weights Date: Thu, 18 Nov 2021 17:49:30 +0100 Message-Id: <20211118164940.8818-18-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org For stochastic bisection we will need to keep more information for each commit than plain int. Factor out initialization of commit weight storage into a separate function so that stochastic bisection can more easily alter it. Signed-off-by: Jan Kara --- bisect.c | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-) diff --git a/bisect.c b/bisect.c index 8dc1eb7f9d82..dd2f6b68ae3d 100644 --- a/bisect.c +++ b/bisect.c @@ -280,19 +280,17 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n * or positive distance. */ static struct commit_list *do_find_bisection(struct commit_list *list, - int nr, int *weights, - unsigned bisect_flags) + int nr, unsigned bisect_flags) { - int n, counted; + int counted; struct commit_list *p; counted = 0; - for (n = 0, p = list; p; p = p->next) { + for (p = list; p; p = p->next) { struct commit *commit = p->item; unsigned commit_flags = commit->object.flags; - *commit_weight_at(&commit_weight, p->item) = &weights[n++]; switch (count_interesting_parents(commit, bisect_flags)) { case 0: if (!(commit_flags & TREESAME)) { @@ -398,6 +396,20 @@ static struct commit_list *do_find_bisection(struct commit_list *list, return best_bisection_sorted(list, nr); } +static void *setup_commit_weight_array(struct commit_list *list, int nodes) +{ + int entry_size = sizeof(int); + void *array; + struct commit_list *p; + int n; + + array = xcalloc(nodes, entry_size); + for (n = 0, p = list; p; p = p->next, n++) { + *commit_weight_at(&commit_weight, p->item) = + array + n * entry_size; + } + return array; +} static struct commit_list *reverse_list(struct commit_list *list) { @@ -416,7 +428,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches, { int nr, on_list; struct commit_list *list, *p, *best, *next, **pnext; - int *weights; + void *weights; init_commit_weight(&commit_weight); show_list("bisection 2 entry", 0, 0, *commit_list); @@ -441,14 +453,14 @@ void find_bisection(struct commit_list **commit_list, int *reaches, nr++; on_list++; } + weights = setup_commit_weight_array(list, on_list); list = reverse_list(list); show_list("bisection 2 sorted", 0, nr, list); *all = nr; - CALLOC_ARRAY(weights, on_list); /* Do the real work of finding bisection commit. */ - best = do_find_bisection(list, nr, weights, bisect_flags); + best = do_find_bisection(list, nr, bisect_flags); if (best) { if (!(bisect_flags & FIND_BISECTION_ALL)) { list->item = best->item; From patchwork Thu Nov 18 16:49:31 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627409 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3E71AC433FE for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 27D676138D for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233937AbhKRQxO (ORCPT ); Thu, 18 Nov 2021 11:53:14 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57658 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233783AbhKRQwv (ORCPT ); Thu, 18 Nov 2021 11:52:51 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 892A21FD47 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=4CmTeXKzEcBZ8PzGmGR3A4u4FUjCs0iU+tEspYPRBzk=; b=hmjOp1BarurO5N2iahXFVve7utCqRrAE35YHh4hiYzLYquHqKh9nrEFyubrZjex++fYyTK 5jhtnkX4PA6QRJ1JjffJ2ic676+Za6ck3+RqkKAXD74euC2V49NXZnl9GmlWGYG4XuKZnz 0el/rlbRkI7vpACF/Dl/PdKcrYVwA/U= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=4CmTeXKzEcBZ8PzGmGR3A4u4FUjCs0iU+tEspYPRBzk=; b=9dq6pNbBr/hYMQyiEzFdPG/ycgyXnEMgLXFFXv4LXQGSEqEFa6Nu8UaRIhK5eMqqYMr2+O oRCcQqHf6ZkMxlBA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 7E975A3B9B; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id AF8C51F2CB5; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 18/27] bisect: Terminate early if there are no eligible commits Date: Thu, 18 Nov 2021 17:49:31 +0100 Message-Id: <20211118164940.8818-19-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org If there are no commits that can be valid bisection point, just terminate search for bisection point early. Firstly, it just wastes time, secondly with more complex computations for stochastic bisection we would have to deal with this special corner-case unnecessarily. Signed-off-by: Jan Kara --- bisect.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/bisect.c b/bisect.c index dd2f6b68ae3d..3a26255e8650 100644 --- a/bisect.c +++ b/bisect.c @@ -453,12 +453,15 @@ void find_bisection(struct commit_list **commit_list, int *reaches, nr++; on_list++; } + *all = nr; + if (!nr) { + *reaches = 0; + goto out_weights; + } weights = setup_commit_weight_array(list, on_list); list = reverse_list(list); show_list("bisection 2 sorted", 0, nr, list); - *all = nr; - /* Do the real work of finding bisection commit. */ best = do_find_bisection(list, nr, bisect_flags); if (best) { @@ -472,6 +475,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches, } free(weights); *commit_list = best; +out_weights: clear_commit_weight(&commit_weight); } From patchwork Thu Nov 18 16:49:32 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627399 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 74564C433FE for ; Thu, 18 Nov 2021 16:50:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5C89461B2B for ; Thu, 18 Nov 2021 16:50:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233877AbhKRQxJ (ORCPT ); Thu, 18 Nov 2021 11:53:09 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57656 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233781AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 9085C1FD4A for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=mVVdUrxRugPiJiyu7oHu4NRyFbiOJg4sEexX4E3yPws=; b=ZsJJ0VeiSuvaIUer0M7TPVa/7BRRrMd1RLaAH5s/ItRXmvzxq2dc9uOuAF/8aMIPIZD0Yh W5Vnlv5vKAy3gEyaEy2+Eod/IPI/e0ahAYH4eZYrONaEOmUnj6jlnBDrGA2RbVPDP2Bdo+ ORcNrH6ffmMhLPQIl78ip4FEiKDOF6w= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=mVVdUrxRugPiJiyu7oHu4NRyFbiOJg4sEexX4E3yPws=; b=6ZjuSNA+g91WLSnprN0ugndbpAFVuRaSQBQYpt1ScFoFCOzvPg7TQ8vEH8ajem3Vqlk6i0 7ov/q+FPptxgF0Cg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 80C7FA3B9C; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id B2CBE1F2CB6; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 19/27] bisect: Compute reachability of tested revs Date: Thu, 18 Nov 2021 17:49:32 +0100 Message-Id: <20211118164940.8818-20-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Compute for each rev a bitmap of revs that can reach it and that were tested during stochastic bisection run. Signed-off-by: Jan Kara --- bisect.c | 199 ++++++++++++++++++++++++++++++++++++++++++++++++++- fixedpoint.h | 18 +++++ 2 files changed, 215 insertions(+), 2 deletions(-) diff --git a/bisect.c b/bisect.c index 3a26255e8650..cf11926d6f4e 100644 --- a/bisect.c +++ b/bisect.c @@ -17,6 +17,7 @@ #include "object-store.h" #include "dir.h" #include "fixedpoint.h" +#include "hashmap.h" static struct oid_array good_revs; static struct oid_array ptest_revs; @@ -24,6 +25,16 @@ static struct oid_array skipped_revs; static fpnum_t result_confidence; +struct tested_rev { + struct hashmap_entry entry; + struct object_id *oid; + int index; /* Index in ptest_revs array */ + fpnum_t confidence; /* Total confidence the rev is good computed + * from of all tests on this rev */ +}; + +static struct hashmap tested_revs_map; + static struct object_id *current_bad_oid; static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL}; @@ -80,8 +91,26 @@ static void clear_counted_flag(struct commit_list *list) define_commit_slab(commit_weight, void *); static struct commit_weight commit_weight; +/* + * Information associated with each commit when computing stochastic bisection + * weights. + */ +struct st_weight { + fpnum_t weight; /* Total weight of all reachable commits */ + fpnum_t node_weight; /* Weight of this particular commit */ + unsigned long rev_bitmap[]; /* Bitmap of tested commits reaching + * this commit */ +}; +int sw_rev_bmp_longs; + #define DEBUG_BISECT 0 +#if DEBUG_BISECT > 0 +#define debug_bisect(fmt...) fprintf(stderr, fmt) +#else +#define debug_bisect(fmt...) do { } while (0) +#endif + static inline int has_weight(struct commit_list *elem) { return commit_weight.slab_size > 0 && @@ -98,6 +127,37 @@ static inline void weight_set(struct commit_list *elem, int weight) *(int *)*commit_weight_at(&commit_weight, elem->item) = weight; } +#define BITS_PER_LONG (sizeof(long) * 8) + +/* + * Add bits in 'from' reachability bitmap to 'to'. Returns 1 if any bit in 'to' + * was set. + */ +static int sw_rev_bmp_or(struct st_weight *to, struct st_weight *from) +{ + int i; + int set = 0; + + for (i = 0; i < sw_rev_bmp_longs; i++) { + unsigned long prev = to->rev_bitmap[i]; + + to->rev_bitmap[i] |= from->rev_bitmap[i]; + set |= (to->rev_bitmap[i] != prev); + } + return set; +} + +static void sw_rev_bmp_set(struct st_weight *to, int idx) +{ + to->rev_bitmap[idx / BITS_PER_LONG] |= 1UL << (idx % BITS_PER_LONG); +} + +static unsigned long sw_rev_bmp_test(struct st_weight *to, int idx) +{ + return to->rev_bitmap[idx / BITS_PER_LONG] & + (1UL << (idx % BITS_PER_LONG)); +} + static int count_interesting_parents(struct commit *commit, unsigned bisect_flags) { struct commit_list *p; @@ -403,6 +463,14 @@ static void *setup_commit_weight_array(struct commit_list *list, int nodes) struct commit_list *p; int n; + /* Stochastic bisection? */ + if (result_confidence) { + int revs = ptest_revs.nr + 1; + + sw_rev_bmp_longs = (revs + BITS_PER_LONG - 1) / BITS_PER_LONG; + entry_size = sizeof(struct st_weight) + + sw_rev_bmp_longs * sizeof(long); + } array = xcalloc(nodes, entry_size); for (n = 0, p = list; p; p = p->next, n++) { *commit_weight_at(&commit_weight, p->item) = @@ -411,6 +479,91 @@ static void *setup_commit_weight_array(struct commit_list *list, int nodes) return array; } +static struct tested_rev *lookup_tested_oid(struct object_id *oid) +{ + struct tested_rev key; + + hashmap_entry_init(&key.entry, oidhash(oid)); + key.oid = oid; + return hashmap_get_entry(&tested_revs_map, &key, entry, NULL); +} + +static int sw_rev_test_idx(struct commit *commit) +{ + struct tested_rev *tr; + + tr = lookup_tested_oid(&commit->object.oid); + if (!tr) + return -1; + return tr->index; +} + +static int propagate_to_ancestors(struct commit *commit) +{ + struct commit_list *q; + int out_of_order = 0, set; + struct st_weight *cw; + + cw = *commit_weight_at(&commit_weight, commit); + for (q = commit->parents; q; q = q->next) { + if (q->item->object.flags & UNINTERESTING) + continue; + set = sw_rev_bmp_or(*commit_weight_at(&commit_weight, q->item), + cw); + if (set && q->item->object.flags & COUNTED) { + debug_bisect("descendants_bitmap: Recursion for %s\n", + oid_to_hex(&q->item->object.oid)); + /* + * If the commit is already processed, we need to + * propagate bitmap update to all already processed + * ancestors. The 'list' should be close to inverse + * topological order so this should be rare. + */ + out_of_order = 1; + } + } + return out_of_order; +} + +/* + * For each commit in the 'list' compute bitmap of tested revisions that can + * reach it. Note for our purposes each commit can reach itself. + */ +static void compute_tested_descendants(struct commit_list *list) +{ + struct commit_list *p; + int retry = 0, tried = 1; + + for (p = list; p; p = p->next) { + struct commit *commit = p->item; + struct st_weight *cw; + int idx; + + cw = *commit_weight_at(&commit_weight, commit); + idx = sw_rev_test_idx(commit); + if (idx >= 0) + sw_rev_bmp_set(cw, idx); + retry = propagate_to_ancestors(commit); + commit->object.flags |= COUNTED; + } + clear_counted_flag(list); + /* + * We expect the 'list' to be close to reverse topological order. If + * it is not exactly in reverse topological order, we need to repeat + * descendant bit propagation until bitmaps are stable. + */ + while (retry) { + tried++; + retry = 0; + for (p = list; p; p = p->next) { + retry = propagate_to_ancestors(p->item); + p->item->object.flags |= COUNTED; + } + clear_counted_flag(list); + } + debug_bisect("%s: Took %d iterations to stabilize.\n", __func__, tried); +} + static struct commit_list *reverse_list(struct commit_list *list) { struct commit_list *p, *next, *last = NULL; @@ -459,6 +612,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches, goto out_weights; } weights = setup_commit_weight_array(list, on_list); + if (result_confidence) + compute_tested_descendants(list); list = reverse_list(list); show_list("bisection 2 sorted", 0, nr, list); @@ -522,11 +677,39 @@ static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES") static GIT_PATH_FUNC(git_path_bisect_result_confidence, "BISECT_RESULT_CONFIDENCE") static GIT_PATH_FUNC(git_path_head_name, "head-name") +static int tested_rev_cmp(const void *data, const struct hashmap_entry *ap, + const struct hashmap_entry *bp, const void *keydata) +{ + const struct tested_rev *a, *b; + + a = container_of(ap, const struct tested_rev, entry); + b = container_of(bp, const struct tested_rev, entry); + + return oidcmp(a->oid, b->oid); +} + +static void setup_tested_revs_map(void) +{ + int i; + struct tested_rev *tr; + + hashmap_init(&tested_revs_map, tested_rev_cmp, NULL, ptest_revs.nr + 1); + for (i = 0; i < ptest_revs.nr; i++) { + tr = xmalloc(sizeof(struct tested_rev)); + hashmap_entry_init(&tr->entry, oidhash(ptest_revs.oid + i)); + tr->oid = ptest_revs.oid + i; + tr->index = i; + tr->confidence = FP_HALF; + hashmap_add(&tested_revs_map, &tr->entry); + } +} + static void read_bisect_confidences(void) { struct strbuf str = STRBUF_INIT; const char *filename = git_path_bisect_result_confidence(); FILE *fp = fopen(filename, "r"); + struct tested_rev *trev; /* Just a regular bisection? */ if (!fp) @@ -535,6 +718,8 @@ static void read_bisect_confidences(void) die(_("Cannot parse result confidence in file '%s'"), filename); fclose(fp); + setup_tested_revs_map(); + /* No uncertain bisection steps yet? */ filename = git_path_bisect_confidences(); fp = fopen(filename, "r"); @@ -542,7 +727,7 @@ static void read_bisect_confidences(void) return; while (strbuf_getline_lf(&str, fp) != EOF) { - fpnum_t prob; + fpnum_t prob, pos_prob, neg_prob; char *spc; char state; struct object_id oid; @@ -562,7 +747,17 @@ static void read_bisect_confidences(void) if (get_oid(str.buf, &oid)) die(_("Cannot get oid of rev '%s' from file '%s'"), str.buf, filename); - /* We'll use parsed data later */ + trev = lookup_tested_oid(&oid); + if (!trev) + die(_("Rev '%s' not tracked as ptest rev."), str.buf); + if (state == 'b') + prob = FP_ONE - prob; + pos_prob = fp_mul(trev->confidence, prob); + neg_prob = fp_mul(FP_ONE - trev->confidence, FP_ONE - prob); + trev->confidence = fp_div(pos_prob, pos_prob + neg_prob); + debug_bisect("read confidence %s: %"FPNUM_FMT + " (total %"FPNUM_FMT")\n", + str.buf, prob, trev->confidence); } strbuf_release(&str); fclose(fp); diff --git a/fixedpoint.h b/fixedpoint.h index 3f6234c6530a..159bb6ef4358 100644 --- a/fixedpoint.h +++ b/fixedpoint.h @@ -27,4 +27,22 @@ static inline const double fp_to_double(fpnum_t n) #define FP_ONE frac_to_fp(1, 1) #define FP_HALF frac_to_fp(1, 2) +/* Multiplication for numbers <= 1 */ +static inline const fpnum_t fp_mul(fpnum_t n, fpnum_t m) +{ + if (m == FP_ONE) + return n; + if (n == FP_ONE) + return m; + assert(m < FP_ONE && n < FP_ONE); + return (m * n) >> FIXEDPOINT_SHIFT; +} + +/* Division for number <= 1 */ +static inline const fpnum_t fp_div(fpnum_t n, fpnum_t d) +{ + assert(n <= FP_ONE); + return (n << (FIXEDPOINT_SHIFT - 1)) / (d >> 1); +} + #endif From patchwork Thu Nov 18 16:49:33 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627389 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id BE885C433F5 for ; Thu, 18 Nov 2021 16:50:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9FF5D6138D for ; Thu, 18 Nov 2021 16:50:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233743AbhKRQxC (ORCPT ); Thu, 18 Nov 2021 11:53:02 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52812 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233759AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id A344B218F6 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=X9+2KidoEbEnpkSJZ+evZwd27d2QrbOsZwz5F+6w0G0=; b=TKmxJHf/tYgA1OpNWqoFfKnrmLT88lx3B2wnFq+x0g80cZ9AARqZxk3bfgEUt8iheyC2MS rLfP3p1I5hlg02XgMf1BSOrJoadvl/PPFsa/j0ioR2FFlFqrOXVCaiXLXWh2MoTeO9MFKR vacLzhWlRPwp41TV5v8HRvwExk5ERvA= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=X9+2KidoEbEnpkSJZ+evZwd27d2QrbOsZwz5F+6w0G0=; b=MBKrzXMwDKsQ3Kk+nlmfMR/BLBsn4qMQt15yM1dvgjQoPYRLeefZugMg7p3tCGagipTzDz oCaq5XH/A/DTCVAg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 9795EA3B8A; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id B6C821F2CB8; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 20/27] bisect: Compute probability a particular commit is bad Date: Thu, 18 Nov 2021 17:49:33 +0100 Message-Id: <20211118164940.8818-21-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Compute conditional probability a commit is bad given results of tests performed so far, for each commit in commit list. Signed-off-by: Jan Kara --- bisect.c | 124 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 124 insertions(+) diff --git a/bisect.c b/bisect.c index cf11926d6f4e..680b96654fd4 100644 --- a/bisect.c +++ b/bisect.c @@ -576,6 +576,128 @@ static struct commit_list *reverse_list(struct commit_list *list) return last; } +struct sw_rev_bmp_hash_entry { + struct hashmap_entry entry; + struct st_weight *commit_weight; + fpnum_t cluster_p_bad; + unsigned int count; +}; + +static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap, + const struct hashmap_entry *bp, const void *keydata) +{ + int i; + const struct sw_rev_bmp_hash_entry *a, *b; + + a = container_of(ap, const struct sw_rev_bmp_hash_entry, entry); + b = container_of(bp, const struct sw_rev_bmp_hash_entry, entry); + + for (i = 0; i < sw_rev_bmp_longs; i++) + if (a->commit_weight->rev_bitmap[i] != + b->commit_weight->rev_bitmap[i]) + return 1; + return 0; +} + +/* + * Compute for each commit a probability it is the bad one given tests + * performed so far. + */ +static void compute_commit_weights(struct commit_list *list) +{ + struct commit_list *p; + struct hashmap reach_map; + struct sw_rev_bmp_hash_entry *found_entry, entry; + struct hashmap_iter reach_iter, trev_iter; + fpnum_t cluster_prob_sum = 0; + + /* + * We call a "cluster" a set of commits which have identical set of + * tested revisions that can reach to it. We compute the size of each + * cluster here - we count only tree-changing nodes as only those can + * be the bad ones. + */ + hashmap_init(&reach_map, sw_rev_bmp_cmp, NULL, ptest_revs.nr + 1); + for (p = list; p; p = p->next) { + struct st_weight *pweight; + unsigned int hashval; + + if (p->item->object.flags & TREESAME) + continue; + + pweight = *commit_weight_at(&commit_weight, p->item); + hashval = memhash(pweight->rev_bitmap, + sw_rev_bmp_longs * sizeof(unsigned long)); + hashmap_entry_init(&entry.entry, hashval); + entry.commit_weight = pweight; + found_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL); + if (!found_entry) { + found_entry = xmalloc( + sizeof(struct sw_rev_bmp_hash_entry)); + hashmap_entry_init(&found_entry->entry, hashval); + found_entry->commit_weight = pweight; + found_entry->count = 0; + hashmap_add(&reach_map, &found_entry->entry); + } + found_entry->count++; + } + + /* + * Compute probability bad commit is in a particular cluster. The + * probability is: + * P(error in cluster C) = + * \Pi_{i\in 'tested rev not reaching C'} P(test at i good) * + * \Pi_{i\in 'tested rev reaching C'} P(test at i bad) + */ + hashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) { + fpnum_t cluster_prob = FP_ONE; + struct tested_rev *trev; + + hashmap_for_each_entry(&tested_revs_map, &trev_iter, trev, + entry) { + if (sw_rev_bmp_test(found_entry->commit_weight, + trev->index)) { + cluster_prob = fp_mul(cluster_prob, + FP_ONE - trev->confidence); + } else { + cluster_prob = fp_mul(cluster_prob, + trev->confidence); + } + } + found_entry->cluster_p_bad = cluster_prob; + cluster_prob_sum += cluster_prob; + } + /* + * Normalize the probabilities to sum to 1 - we need this normalization + * because in fact we compute conditional probability of bad commit + * being in a particular cluster given test results we already + * obtained. + */ + hashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) { + found_entry->cluster_p_bad = fp_div(found_entry->cluster_p_bad, + cluster_prob_sum); + } + + /* Uniformly distribute the probability among all nodes of a cluster */ + for (p = list; p; p = p->next) { + struct st_weight *pweight; + + if (p->item->object.flags & TREESAME) + continue; + + pweight = *commit_weight_at(&commit_weight, p->item); + hashmap_entry_init(&entry.entry, + memhash(pweight->rev_bitmap, + sw_rev_bmp_longs * sizeof(unsigned long))); + entry.commit_weight = pweight; + found_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL); + pweight->node_weight = + found_entry->cluster_p_bad / found_entry->count; + } + + hashmap_clear_and_free(&reach_map, struct sw_rev_bmp_hash_entry, entry); +} + void find_bisection(struct commit_list **commit_list, int *reaches, int *all, unsigned bisect_flags) { @@ -615,6 +737,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches, if (result_confidence) compute_tested_descendants(list); list = reverse_list(list); + if (result_confidence) + compute_commit_weights(list); show_list("bisection 2 sorted", 0, nr, list); /* Do the real work of finding bisection commit. */ From patchwork Thu Nov 18 16:49:34 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627411 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8C47CC43219 for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 753966138D for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234007AbhKRQxR (ORCPT ); Thu, 18 Nov 2021 11:53:17 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57644 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233795AbhKRQwv (ORCPT ); Thu, 18 Nov 2021 11:52:51 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id AE3921FD54 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=tGJ3Y0RXvgjFuBOyhXbLOG2S0U9AxTOAy6AZJjmJcuA=; b=R+menAgysdkF18DM+BQFJEqW2VIJbhXfgyaGugEZ17d4wCZWQ9fX7oCxX/YO/hpKgoJSeO z0z3XkTLmW9iP2aALdRVASYSeqbwQBEFQ9GSSewPEVxGC5YDEHz3ns0dzgLTwBeVGQwQEl N/cfr1Uf2MW+rL2Tv5iMPhJn4J+jiAM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=tGJ3Y0RXvgjFuBOyhXbLOG2S0U9AxTOAy6AZJjmJcuA=; b=RzVuTOwKPopgNgkXfv7wl6QGjMKTtvL7uMZLkhZNn3IY8UPrYSmtKJdv6rst0SfBmBVS2T 64fXAJRdcQWCD3DA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id A05B0A3BA0; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id BB4CF1F2CBC; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 21/27] bisect: Reorganize commit weight computation Date: Thu, 18 Nov 2021 17:49:34 +0100 Message-Id: <20211118164940.8818-22-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Reorganize commit weight computation a bit so that it is easier to generalize for stochastic bisection. There's no real need for two special values (-1 and -2). Also we can set weight of leaf nodes while computing weight of nodes with one parent. Overall the code becomes a bit simpler. Signed-off-by: Jan Kara --- bisect.c | 93 +++++++++++++++++++++----------------------------------- 1 file changed, 34 insertions(+), 59 deletions(-) diff --git a/bisect.c b/bisect.c index 680b96654fd4..4107161c086c 100644 --- a/bisect.c +++ b/bisect.c @@ -158,17 +158,14 @@ static unsigned long sw_rev_bmp_test(struct st_weight *to, int idx) (1UL << (idx % BITS_PER_LONG)); } -static int count_interesting_parents(struct commit *commit, unsigned bisect_flags) +static int count_interesting_parents(struct commit *commit) { struct commit_list *p; int count; - for (count = 0, p = commit->parents; p; p = p->next) { + for (count = 0, p = commit->parents; p; p = p->next) if (!(p->item->object.flags & UNINTERESTING)) count++; - if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY) - break; - } return count; } @@ -326,18 +323,14 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n return list; } +#define WEIGHT_UNSET -1 + /* - * zero or positive weight is the number of interesting commits it can + * Zero or positive weight is the number of interesting commits it can * reach, including itself. Especially, weight = 0 means it does not * reach any tree-changing commits (e.g. just above uninteresting one - * but traversal is with pathspec). - * - * weight = -1 means it has one parent and its distance is yet to - * be computed. - * - * weight = -2 means it has more than one parent and its distance is - * unknown. After running count_distance() first, they will get zero - * or positive distance. + * but traversal is with pathspec). We initialize weights to a special value + * WEIGHT_UNSET to identify commits for which we didn't compute weight yet. */ static struct commit_list *do_find_bisection(struct commit_list *list, int nr, unsigned bisect_flags) @@ -346,32 +339,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list, struct commit_list *p; counted = 0; - - for (p = list; p; p = p->next) { - struct commit *commit = p->item; - unsigned commit_flags = commit->object.flags; - - switch (count_interesting_parents(commit, bisect_flags)) { - case 0: - if (!(commit_flags & TREESAME)) { - weight_set(p, 1); - counted++; - show_list("bisection 2 count one", - counted, nr, list); - } - /* - * otherwise, it is known not to reach any - * tree-changing commit and gets weight 0. - */ - break; - case 1: - weight_set(p, -1); - break; - default: - weight_set(p, -2); - break; - } - } + for (p = list; p; p = p->next) + weight_set(p, WEIGHT_UNSET); show_list("bisection 2 initialize", counted, nr, list); @@ -389,21 +358,21 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * So we will first count distance of merges the usual * way, and then fill the blanks using cheaper algorithm. */ - for (p = list; p; p = p->next) { - if (p->item->object.flags & UNINTERESTING) - continue; - if (weight(p) != -2) - continue; - if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY) - BUG("shouldn't be calling count-distance in fp mode"); - weight_set(p, count_distance(p)); - clear_counted_flag(list); + if (!(bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)) { + for (p = list; p; p = p->next) { + if (p->item->object.flags & UNINTERESTING) + continue; + if (count_interesting_parents(p->item) <= 1) + continue; + weight_set(p, count_distance(p)); + clear_counted_flag(list); - /* Does it happen to be at half-way? */ - if (!(bisect_flags & FIND_BISECTION_ALL) && - approx_halfway(p, nr)) - return p; - counted++; + /* Does it happen to be at half-way? */ + if (!(bisect_flags & FIND_BISECTION_ALL) && + approx_halfway(p, nr)) + return p; + counted++; + } } show_list("bisection 2 count_distance", counted, nr, list); @@ -412,8 +381,9 @@ static struct commit_list *do_find_bisection(struct commit_list *list, for (p = list; p; p = p->next) { struct commit_list *q; unsigned commit_flags = p->item->object.flags; + int parent_weight = 0; - if (0 <= weight(p)) + if (weight(p) != WEIGHT_UNSET) continue; for (q = p->item->parents; @@ -421,10 +391,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list, q = bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY ? NULL : q->next) { if (q->item->object.flags & UNINTERESTING) continue; - if (0 <= weight(q)) + parent_weight = weight(q); + if (parent_weight != WEIGHT_UNSET) break; } - if (!q) + /* + * Only parent with unset weight? We need to compute + * other weights first. + */ + if (parent_weight == WEIGHT_UNSET) continue; /* @@ -433,13 +408,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * otherwise inherit it from q directly. */ if (!(commit_flags & TREESAME)) { - weight_set(p, weight(q)+1); + weight_set(p, parent_weight + 1); counted++; show_list("bisection 2 count one", counted, nr, list); } else - weight_set(p, weight(q)); + weight_set(p, parent_weight); /* Does it happen to be at half-way? */ if (!(bisect_flags & FIND_BISECTION_ALL) && From patchwork Thu Nov 18 16:49:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627397 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5CE42C433F5 for ; Thu, 18 Nov 2021 16:50:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 449A261B2B for ; Thu, 18 Nov 2021 16:50:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233815AbhKRQxI (ORCPT ); Thu, 18 Nov 2021 11:53:08 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52814 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233767AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id AE5012190C for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=HsKLjsAUt13nezPJ4q8AKg2AgiIXfDiTolWNPplO1q8=; b=PElFBjX0ueFWWK0WPBGpt3VlYghXeS07m+7D87ZE23xi+xM49O8+L/3rJLDl35XbYGp9A/ cUA/PZ0U3DEhpAK+L3xwEvSy1V97x4oKnic0v8uQwXG/XjIqLmS59EAUUorFmYuFyHCOvn xbTXPeDIDHjBFz9UL5tc5T+Qy89ixOI= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=HsKLjsAUt13nezPJ4q8AKg2AgiIXfDiTolWNPplO1q8=; b=vB7YKDcbPnhKr3+/4wyg2wrODYqDa6+08Eg6OMivquaDl/+I3JraXZERRKDMrIVKAnLTm0 0/LPxO7pYsZNuCDw== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 9E300A3B9F; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id BF5DD1F2CBD; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 22/27] bisect: Move count_distance() Date: Thu, 18 Nov 2021 17:49:35 +0100 Message-Id: <20211118164940.8818-23-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Move count_distance() function as stochastic bisection will need to call weight() from it and the move avoids forward declaration. No code changes. Signed-off-by: Jan Kara --- bisect.c | 92 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 46 insertions(+), 46 deletions(-) diff --git a/bisect.c b/bisect.c index 4107161c086c..8e47c3fb4b9e 100644 --- a/bisect.c +++ b/bisect.c @@ -42,52 +42,6 @@ static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL}; static const char *term_bad; static const char *term_good; -/* Remember to update object flag allocation in object.h */ -#define COUNTED (1u<<16) - -/* - * This is a truly stupid algorithm, but it's only - * used for bisection, and we just don't care enough. - * - * We care just barely enough to avoid recursing for - * non-merge entries. - */ -static int count_distance(struct commit_list *entry) -{ - int nr = 0; - - while (entry) { - struct commit *commit = entry->item; - struct commit_list *p; - - if (commit->object.flags & (UNINTERESTING | COUNTED)) - break; - if (!(commit->object.flags & TREESAME)) - nr++; - commit->object.flags |= COUNTED; - p = commit->parents; - entry = p; - if (p) { - p = p->next; - while (p) { - nr += count_distance(p); - p = p->next; - } - } - } - - return nr; -} - -static void clear_counted_flag(struct commit_list *list) -{ - while (list) { - struct commit *commit = list->item; - commit->object.flags &= ~COUNTED; - list = list->next; - } -} - define_commit_slab(commit_weight, void *); static struct commit_weight commit_weight; @@ -169,6 +123,52 @@ static int count_interesting_parents(struct commit *commit) return count; } +/* Remember to update object flag allocation in object.h */ +#define COUNTED (1u<<16) + +/* + * This is a truly stupid algorithm, but it's only + * used for bisection, and we just don't care enough. + * + * We care just barely enough to avoid recursing for + * non-merge entries. + */ +static int count_distance(struct commit_list *entry) +{ + int nr = 0; + + while (entry) { + struct commit *commit = entry->item; + struct commit_list *p; + + if (commit->object.flags & (UNINTERESTING | COUNTED)) + break; + if (!(commit->object.flags & TREESAME)) + nr++; + commit->object.flags |= COUNTED; + p = commit->parents; + entry = p; + if (p) { + p = p->next; + while (p) { + nr += count_distance(p); + p = p->next; + } + } + } + + return nr; +} + +static void clear_counted_flag(struct commit_list *list) +{ + while (list) { + struct commit *commit = list->item; + commit->object.flags &= ~COUNTED; + list = list->next; + } +} + static inline int approx_halfway(struct commit_list *p, int nr) { int diff; From patchwork Thu Nov 18 16:49:36 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627391 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C44D1C433EF for ; Thu, 18 Nov 2021 16:50:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B2B3061A8A for ; Thu, 18 Nov 2021 16:50:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233891AbhKRQxF (ORCPT ); Thu, 18 Nov 2021 11:53:05 -0500 Received: from smtp-out1.suse.de ([195.135.220.28]:52816 "EHLO smtp-out1.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233763AbhKRQwu (ORCPT ); Thu, 18 Nov 2021 11:52:50 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id B2DEA21910 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=In/LXxyrRhidOT26/GDN+I3ayXT0ctYPZUiGPy8Qls8=; b=WRgvULrK395g4Agi+NeOx8iZXyGlNXZH+eoJ3F9uxnJG08+5PfpVwL+vssXH47ZXlRr86U 1cKiJEu1Mz0mEYdNSkrsYFZUfZRIxmPuL2yHbHZGyxgPRh4LYoEJSqwskyhMpGL4sa9QPa 2w8u4Fltp47qa1sezyOatzToaHI6u5g= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=In/LXxyrRhidOT26/GDN+I3ayXT0ctYPZUiGPy8Qls8=; b=zqpvn3fB1uWgfkujGxXd4gj1jSKrfMKogTqjR1pnPLz9brRATBJKijyqWHWTsbT2jgU90E hsAspj5AYF1KEoAQ== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id A3F78A3BA1; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id C2BBE1F2CC1; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 23/27] bisect: Find bisection point for stochastic weights Date: Thu, 18 Nov 2021 17:49:36 +0100 Message-Id: <20211118164940.8818-24-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The algorithm for finding the next bisection point for stochastic bisection is the same as for normal bisection. Just instead of uniform node weight 1 we use the weights derived from computed fault probabilities. To allow reusing as much code as possible we change normal bisection to use fixedpoint number type (uint64_t) for computations instead of int. It wastes 4 bytes per commit but is probably worth the avoided duplication. We change the functions deciding about bisection point to work on weights in [0,1] range and scale normal bisection weights to be in this range. Signed-off-by: Jan Kara --- bisect.c | 138 ++++++++++++++++++++++++++++++++++----------------- fixedpoint.h | 10 ++++ 2 files changed, 102 insertions(+), 46 deletions(-) diff --git a/bisect.c b/bisect.c index 8e47c3fb4b9e..12b027b86e75 100644 --- a/bisect.c +++ b/bisect.c @@ -42,6 +42,12 @@ static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL}; static const char *term_bad; static const char *term_good; +/* + * Slab for keeping weight information associated with each commit. For normal + * bisection we keep just weight of each commit (fpnum_t - fraction of + * reachable commits), for stochastic bisection we keep struct st_weight which + * contains more information. + */ define_commit_slab(commit_weight, void *); static struct commit_weight commit_weight; @@ -50,7 +56,9 @@ static struct commit_weight commit_weight; * weights. */ struct st_weight { - fpnum_t weight; /* Total weight of all reachable commits */ + fpnum_t weight; /* Total weight of all reachable commits. This + * has to be first in this struct for weight() + * and weight_set() to work correctly. */ fpnum_t node_weight; /* Weight of this particular commit */ unsigned long rev_bitmap[]; /* Bitmap of tested commits reaching * this commit */ @@ -71,14 +79,26 @@ static inline int has_weight(struct commit_list *elem) *commit_weight_at(&commit_weight, elem->item) != NULL; } -static inline int weight(struct commit_list *elem) +static inline fpnum_t weight(struct commit_list *elem) +{ + return *(fpnum_t *)*commit_weight_at(&commit_weight, elem->item); +} + +static inline void weight_set(struct commit_list *elem, fpnum_t weight) { - return *(int *)*commit_weight_at(&commit_weight, elem->item); + *(fpnum_t *)*commit_weight_at(&commit_weight, elem->item) = weight; } -static inline void weight_set(struct commit_list *elem, int weight) +static inline fpnum_t node_weight(struct commit_list *elem) { - *(int *)*commit_weight_at(&commit_weight, elem->item) = weight; + /* + * For normal bisection weight of each node is 1. For stochastic + * bisection we use the weight computed based on test results. + */ + if (result_confidence) + return ((struct st_weight *)*commit_weight_at(&commit_weight, + elem->item))->node_weight; + return FP_ONE; } #define BITS_PER_LONG (sizeof(long) * 8) @@ -133,9 +153,9 @@ static int count_interesting_parents(struct commit *commit) * We care just barely enough to avoid recursing for * non-merge entries. */ -static int count_distance(struct commit_list *entry) +static fpnum_t count_distance(struct commit_list *entry) { - int nr = 0; + fpnum_t weight = 0; while (entry) { struct commit *commit = entry->item; @@ -144,20 +164,20 @@ static int count_distance(struct commit_list *entry) if (commit->object.flags & (UNINTERESTING | COUNTED)) break; if (!(commit->object.flags & TREESAME)) - nr++; + weight += node_weight(entry); commit->object.flags |= COUNTED; p = commit->parents; entry = p; if (p) { p = p->next; while (p) { - nr += count_distance(p); + weight += count_distance(p); p = p->next; } } } - return nr; + return weight; } static void clear_counted_flag(struct commit_list *list) @@ -169,9 +189,18 @@ static void clear_counted_flag(struct commit_list *list) } } +/* Return scale of weights in commit_weight() array */ +static int weight_scale(int nr) +{ + if (result_confidence) + return 1; + return nr; +} + static inline int approx_halfway(struct commit_list *p, int nr) { - int diff; + fpnum_t diff; + int scale = weight_scale(nr); /* * Don't short-cut something we are not going to return! @@ -180,25 +209,30 @@ static inline int approx_halfway(struct commit_list *p, int nr) return 0; if (DEBUG_BISECT) return 0; - /* - * For small number of commits 2 and 3 are halfway of 5, and - * 3 is halfway of 6 but 2 and 4 are not. - */ - diff = 2 * weight(p) - nr; - switch (diff) { - case -1: case 0: case 1: - return 1; - default: + + if (!result_confidence) { + scale = nr; /* - * For large number of commits we are not so strict, it's - * good enough if it's within ~0.1% of the halfway point, - * e.g. 5000 is exactly halfway of 10000, but we consider - * the values [4996, 5004] as halfway as well. + * For small number of commits 2 and 3 are halfway of 5, and 3 + * is halfway of 6 but 2 and 4 are not. For large number of + * commits we are not so strict, it's good enough if it's + * within ~0.1% of the halfway point, e.g. 5000 is exactly + * halfway of 10000, but we consider the values [4996, 5004] as + * halfway as well. */ - if (abs(diff) < nr / 1024) - return 1; - return 0; + diff = frac_to_fp((nr + 1023) / 1024, nr); + } else { + /* + * For stochastic we accept any node whose weight is within + * 1/16 from the middle. In the worst case this may result in + * ~20% more tests which is not too bad. + */ + diff = frac_to_fp(1, 16); } + if (weight(p) > (FP_HALF - diff) * scale && + weight(p) < (FP_HALF + diff) * scale) + return 1; + return 0; } static void show_list(const char *debug, int counted, int nr, @@ -227,7 +261,7 @@ static void show_list(const char *debug, int counted, int nr, (commit_flags & UNINTERESTING) ? 'U' : ' ', (commit_flags & COUNTED) ? 'C' : ' '); if (has_weight(p)) - fprintf(stderr, "%3d", weight(p)); + fprintf(stderr, "%lf", fp_to_double(weight(p))); else fprintf(stderr, "---"); fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid)); @@ -245,19 +279,20 @@ static void show_list(const char *debug, int counted, int nr, static struct commit_list *best_bisection(struct commit_list *list, int nr) { struct commit_list *p, *best; - int best_distance = -1; + fpnum_t best_distance = -1; + int scale = weight_scale(nr); best = list; for (p = list; p; p = p->next) { - int distance; + fpnum_t distance; unsigned commit_flags = p->item->object.flags; if (commit_flags & TREESAME) continue; distance = weight(p); - if (nr - distance < distance) - distance = nr - distance; - if (distance > best_distance) { + if (distance > FP_HALF * scale) + distance = FP_ONE * scale - distance; + if (best_distance == -1 || distance > best_distance) { best = p; best_distance = distance; } @@ -268,7 +303,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr) struct commit_dist { struct commit *commit; - int distance; + fpnum_t distance; }; static int compare_commit_dist(const void *a_, const void *b_) @@ -277,27 +312,32 @@ static int compare_commit_dist(const void *a_, const void *b_) a = (struct commit_dist *)a_; b = (struct commit_dist *)b_; - if (a->distance != b->distance) - return b->distance - a->distance; /* desc sort */ + if (a->distance != b->distance) { + if (a->distance > b->distance) + return -1; + return 1; + } return oidcmp(&a->commit->object.oid, &b->commit->object.oid); } -static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr) +static struct commit_list *best_bisection_sorted(struct commit_list *list, + int nr) { struct commit_list *p; struct commit_dist *array = xcalloc(nr, sizeof(*array)); struct strbuf buf = STRBUF_INIT; int cnt, i; + int scale = weight_scale(nr); for (p = list, cnt = 0; p; p = p->next) { - int distance; + fpnum_t distance; unsigned commit_flags = p->item->object.flags; if (commit_flags & TREESAME) continue; distance = weight(p); - if (nr - distance < distance) - distance = nr - distance; + if (distance > FP_HALF * scale) + distance = FP_ONE * scale - distance; array[cnt].commit = p->item; array[cnt].distance = distance; cnt++; @@ -307,7 +347,13 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n struct object *obj = &(array[i].commit->object); strbuf_reset(&buf); - strbuf_addf(&buf, "dist=%d", array[i].distance); + if (!result_confidence) { + strbuf_addf(&buf, "dist=%u", + fp_to_int(array[i].distance)); + } else { + strbuf_addf(&buf, "dist=%lf", + fp_to_double(array[i].distance)); + } add_name_decoration(DECORATION_NONE, buf.buf, obj); p->item = array[i].commit; @@ -323,7 +369,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n return list; } -#define WEIGHT_UNSET -1 +#define WEIGHT_UNSET ((fpnum_t)-1) /* * Zero or positive weight is the number of interesting commits it can @@ -381,7 +427,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, for (p = list; p; p = p->next) { struct commit_list *q; unsigned commit_flags = p->item->object.flags; - int parent_weight = 0; + fpnum_t parent_weight = 0; if (weight(p) != WEIGHT_UNSET) continue; @@ -408,7 +454,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, * otherwise inherit it from q directly. */ if (!(commit_flags & TREESAME)) { - weight_set(p, parent_weight + 1); + weight_set(p, parent_weight + node_weight(p)); counted++; show_list("bisection 2 count one", counted, nr, list); @@ -433,7 +479,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list, static void *setup_commit_weight_array(struct commit_list *list, int nodes) { - int entry_size = sizeof(int); + int entry_size = sizeof(fpnum_t); void *array; struct commit_list *p; int n; @@ -725,7 +771,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches, best = list; best->next = NULL; } - *reaches = weight(best); + *reaches = fp_to_int(weight(best) * (nr / weight_scale(nr))); } free(weights); *commit_list = best; diff --git a/fixedpoint.h b/fixedpoint.h index 159bb6ef4358..6d03a5e010ee 100644 --- a/fixedpoint.h +++ b/fixedpoint.h @@ -14,6 +14,16 @@ static inline const fpnum_t frac_to_fp(unsigned int n, unsigned int d) return (((fpnum_t)n) << FIXEDPOINT_SHIFT) / d; } +static inline const fpnum_t int_to_fp(unsigned int n) +{ + return ((fpnum_t)n) << FIXEDPOINT_SHIFT; +} + +static inline unsigned int fp_to_int(fpnum_t n) +{ + return (n + (1ULL << (FIXEDPOINT_SHIFT - 1))) >> FIXEDPOINT_SHIFT; +} + static inline const fpnum_t double_to_fp(double n) { return (n * (1ULL << FIXEDPOINT_SHIFT)); From patchwork Thu Nov 18 16:49:37 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627415 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 970CBC4321E for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7FB5C61B3B for ; Thu, 18 Nov 2021 16:50:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234061AbhKRQxT (ORCPT ); Thu, 18 Nov 2021 11:53:19 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57660 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233799AbhKRQww (ORCPT ); Thu, 18 Nov 2021 11:52:52 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 9031D1FD49 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=WIqWaPCbKytzaGTVJNjidUkwwHYS84r6kQkbTNQcunk=; b=oNmRhFvvV/H83bDIZVDP/9K8RSu2C2v2RNtep3boyjJbVj4GGu4IxineU6HOy9oNPmg+gx f8HZU3N2zUfHQ1R1dQTDYiTHaXGaUW8DC1yryyQ8Drx8r3OrKZOaZeDrwpgTAuWUUF9c23 JwCyhMStOzAaMFMRWymHZZx2QNcA0pg= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=WIqWaPCbKytzaGTVJNjidUkwwHYS84r6kQkbTNQcunk=; b=1bVhhqge//3KfGc2TGYK3ePA1QXALtz8OvkoNiy33hNwBoCJZkHOjxA2uGEeT5DtcWVwH4 1AgoOIwDLk62wRCw== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 81535A3B9D; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id C5ADE1F2CC4; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 24/27] bisect: Stop bisection when we are confident about bad commit Date: Thu, 18 Nov 2021 17:49:37 +0100 Message-Id: <20211118164940.8818-25-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org When we found a commit that has high enough probability of being bad, stop bisection and report it. Signed-off-by: Jan Kara --- bisect.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/bisect.c b/bisect.c index 12b027b86e75..7da74778d780 100644 --- a/bisect.c +++ b/bisect.c @@ -624,7 +624,7 @@ static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap, * Compute for each commit a probability it is the bad one given tests * performed so far. */ -static void compute_commit_weights(struct commit_list *list) +static struct commit_list *compute_commit_weights(struct commit_list *list) { struct commit_list *p; struct hashmap reach_map; @@ -714,9 +714,14 @@ static void compute_commit_weights(struct commit_list *list) found_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL); pweight->node_weight = found_entry->cluster_p_bad / found_entry->count; + /* Found node we are confident enough is bad? */ + if (pweight->node_weight >= result_confidence) + break; } hashmap_clear_and_free(&reach_map, struct sw_rev_bmp_hash_entry, entry); + + return p; } void find_bisection(struct commit_list **commit_list, int *reaches, @@ -758,14 +763,21 @@ void find_bisection(struct commit_list **commit_list, int *reaches, if (result_confidence) compute_tested_descendants(list); list = reverse_list(list); - if (result_confidence) - compute_commit_weights(list); + if (result_confidence) { + best = compute_commit_weights(list); + /* Found commit we are confident is bad? Stop bisection... */ + if (best) { + oidcpy(current_bad_oid, &best->item->object.oid); + goto found_best; + } + } show_list("bisection 2 sorted", 0, nr, list); /* Do the real work of finding bisection commit. */ best = do_find_bisection(list, nr, bisect_flags); if (best) { if (!(bisect_flags & FIND_BISECTION_ALL)) { +found_best: list->item = best->item; free_commit_list(list->next); best = list; From patchwork Thu Nov 18 16:49:38 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627419 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 860A6C433F5 for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 64F0861391 for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233997AbhKRQxR (ORCPT ); Thu, 18 Nov 2021 11:53:17 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57642 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233793AbhKRQwv (ORCPT ); Thu, 18 Nov 2021 11:52:51 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 930C61FD4D for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=09c+ekA3hGnIdR0LKBMZyVTqnxiznpUf73U5DAnWRHg=; b=knl3yL72Ub7eSTEMrgfp7fnGpS6IzO3K7uu+nX295R41cmse3BkA5GDXQW9c0n+l9op61B hUwXGWRVFGxC4yCdkYddT/bBgQfB1cbZIjc33GTh6GIxBWqXoHTSGURooRnM8VDSnDOHTO V25SeS2LxLZJIZMKiTrGByxX4VAJBqM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=09c+ekA3hGnIdR0LKBMZyVTqnxiznpUf73U5DAnWRHg=; b=Y8JCOUULlpvrx7r/X0gGhEeO6Qxjo/4sQg7JKWHBOiP+lcISyCWcrXzs0RJrzgG+KddwP3 QLeT4dFhhKWYs4AA== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id 83B16A3B9E; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id CA1B51F2CC8; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 25/27] bisect: Report commit with the highest probability Date: Thu, 18 Nov 2021 17:49:38 +0100 Message-Id: <20211118164940.8818-26-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org For stochastic bisection it does not make sense to report number of commits to investigate (since we always consider all). What we can do though is to report the highest probability some commit has of being bad. That also indicates how far we are from the end of bisection as once the probability reaches desired result confidence bisection stops. Signed-off-by: Jan Kara --- bisect.c | 56 +++++++++++++++++++++++++++++++++------------- bisect.h | 4 +++- builtin/rev-list.c | 6 +++-- 3 files changed, 48 insertions(+), 18 deletions(-) diff --git a/bisect.c b/bisect.c index 7da74778d780..6ed740106795 100644 --- a/bisect.c +++ b/bisect.c @@ -724,7 +724,25 @@ static struct commit_list *compute_commit_weights(struct commit_list *list) return p; } -void find_bisection(struct commit_list **commit_list, int *reaches, +static fpnum_t heaviest_commit(struct commit_list *list) +{ + fpnum_t best_weight = 0; + struct commit_list *p; + + for (p = list; p; p = p->next) { + struct st_weight *pweight; + + if (p->item->object.flags & TREESAME) + continue; + + pweight = *commit_weight_at(&commit_weight, p->item); + if (pweight->node_weight > best_weight) + best_weight = pweight->node_weight; + } + return best_weight; +} + +void find_bisection(struct commit_list **commit_list, fpnum_t *reaches, int *all, unsigned bisect_flags) { int nr, on_list; @@ -770,6 +788,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches, oidcpy(current_bad_oid, &best->item->object.oid); goto found_best; } + *reaches = heaviest_commit(list); } show_list("bisection 2 sorted", 0, nr, list); @@ -783,7 +802,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches, best = list; best->next = NULL; } - *reaches = fp_to_int(weight(best) * (nr / weight_scale(nr))); + if (!result_confidence) + *reaches = weight(best) / nr; } free(weights); *commit_list = best; @@ -1457,7 +1477,8 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix) { struct rev_info revs; struct commit_list *tried; - int reaches = 0, all = 0, nr, steps; + int all = 0, nr, steps; + fpnum_t reaches = 0; enum bisect_error res = BISECT_OK; struct object_id *bisect_rev; char *steps_msg; @@ -1536,19 +1557,24 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix) return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND; } - nr = all - reaches - 1; - steps = estimate_bisect_steps(all); + if (!result_confidence) { + nr = all - fp_to_int(reaches * all) - 1; + steps = estimate_bisect_steps(all); - steps_msg = xstrfmt(Q_("(roughly %d step)", "(roughly %d steps)", - steps), steps); - /* - * TRANSLATORS: the last %s will be replaced with "(roughly %d - * steps)" translation. - */ - printf(Q_("Bisecting: %d revision left to test after this %s\n", - "Bisecting: %d revisions left to test after this %s\n", - nr), nr, steps_msg); - free(steps_msg); + steps_msg = xstrfmt(Q_("(roughly %d step)", "(roughly %d steps)", + steps), steps); + /* + * TRANSLATORS: the last %s will be replaced with "(roughly %d + * steps)" translation. + */ + printf(Q_("Bisecting: %d revision left to test after this %s\n", + "Bisecting: %d revisions left to test after this %s\n", + nr), nr, steps_msg); + free(steps_msg); + } else { + printf(_("Bisecting: most probable commit has probability %lf\n"), + fp_to_double(reaches)); + } /* Clean up objects used, as they will be reused. */ repo_clear_commit_marks(r, ALL_REV_FLAGS); diff --git a/bisect.h b/bisect.h index ec24ac2d7ee9..d0a805b05041 100644 --- a/bisect.h +++ b/bisect.h @@ -1,6 +1,8 @@ #ifndef BISECT_H #define BISECT_H +#include "fixedpoint.h" + struct commit_list; struct repository; @@ -11,7 +13,7 @@ struct repository; * Otherwise, it will be either all non-SAMETREE commits or the single * best commit, as chosen by `find_all`. */ -void find_bisection(struct commit_list **list, int *reaches, int *all, +void find_bisection(struct commit_list **list, fpnum_t *reaches, int *all, unsigned bisect_flags); struct commit_list *filter_skipped(struct commit_list *list, diff --git a/builtin/rev-list.c b/builtin/rev-list.c index 36cb909ebaa5..c98ac9e91688 100644 --- a/builtin/rev-list.c +++ b/builtin/rev-list.c @@ -702,7 +702,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix) mark_edges_uninteresting(&revs, show_edge, 0); if (bisect_list) { - int reaches, all; + int all; + fpnum_t reaches; unsigned bisect_flags = 0; if (bisect_find_all) @@ -714,7 +715,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix) find_bisection(&revs.commits, &reaches, &all, bisect_flags); if (bisect_show_vars) - return show_bisect_vars(&info, reaches, all); + return show_bisect_vars(&info, fp_to_int(reaches * all), + all); } if (filter_provided_objects) { From patchwork Thu Nov 18 16:49:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627417 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8B5B9C433FE for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7900E61B31 for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234029AbhKRQxS (ORCPT ); Thu, 18 Nov 2021 11:53:18 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57646 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233798AbhKRQww (ORCPT ); Thu, 18 Nov 2021 11:52:52 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id B99C11FD57 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=fhny/z4JRByPragM5njdv8TFYMb262mT72nZ5Crjcj4=; b=nuNu0o//O7HN1pH70Iltzital/zfraykHkbMDjh4BvYimIZzgjeevYOJrE66RZPHXWz3EL G1onKrxNso/UsSOHwyxuAbJLANSgy8m7VRJy6TZeOBLXmxwIAw8LRisI/1EnnjE6mlYmB0 G3dghGifEThCK659ozL1Nbj64JSo5Xo= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=fhny/z4JRByPragM5njdv8TFYMb262mT72nZ5Crjcj4=; b=DTuNKswOXscZogNbYRzwK0j/Ldqo4/ZoQYm7NkpAGBYwL1VGOmtFmyOIigXbrP8+nT/hF6 ziKyKT+bxUZwtlBQ== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id ADBDDA3BA2; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id CE0A61F2CCB; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 26/27] bisect: Debug stochastic bisection Date: Thu, 18 Nov 2021 17:49:39 +0100 Message-Id: <20211118164940.8818-27-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add debug prints for debugging stochastic bisection. Signed-off-by: Jan Kara --- bisect.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) diff --git a/bisect.c b/bisect.c index 6ed740106795..4d2ba5dbd77e 100644 --- a/bisect.c +++ b/bisect.c @@ -620,6 +620,21 @@ static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap, return 0; } +static void show_cluster(struct sw_rev_bmp_hash_entry *entry) +{ + int i; + + if (!DEBUG_BISECT) + return; + + fprintf(stderr, "cluster prob %"FPNUM_FMT" members %u reaching revs ", + entry->cluster_p_bad, entry->count); + for (i = 0; i < ptest_revs.nr; i++) + if (sw_rev_bmp_test(entry->commit_weight, i)) + fprintf(stderr, "%.8s ", oid_to_hex(ptest_revs.oid + i)); + fprintf(stderr, "\n"); +} + /* * Compute for each commit a probability it is the bad one given tests * performed so far. @@ -697,6 +712,7 @@ static struct commit_list *compute_commit_weights(struct commit_list *list) hashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) { found_entry->cluster_p_bad = fp_div(found_entry->cluster_p_bad, cluster_prob_sum); + show_cluster(found_entry); } /* Uniformly distribute the probability among all nodes of a cluster */ @@ -1111,6 +1127,30 @@ static struct commit_list *managed_skipped(struct commit_list *list, return skip_away(list, count); } +static void print_object(struct object *obj) +{ + unsigned flags = obj->flags; + + fprintf(stderr, "%c%c%c%c ", + (flags & TREESAME) ? ' ' : 'T', + (flags & UNINTERESTING) ? 'U' : ' ', + (flags & SEEN) ? 'S' : ' ', + (flags & COUNTED) ? 'C' : ' '); + fprintf(stderr, "%.8s\n", oid_to_hex(&obj->oid)); +} + +static void show_object_array(const char *str, struct object_array *array) +{ + int i; + + if (!DEBUG_BISECT) + return; + + fprintf(stderr, "%s\n", str); + for (i = 0; i < array->nr; i++) + print_object(array->objects[i].item); +} + static void bisect_rev_setup(struct repository *r, struct rev_info *revs, const char *prefix, const char *bad_format, const char *good_format, @@ -1139,12 +1179,16 @@ static void bisect_rev_setup(struct repository *r, struct rev_info *revs, setup_revisions(rev_argv.nr, rev_argv.v, revs, NULL); /* XXX leak rev_argv, as "revs" may still be pointing to it */ + show_list("setup_revisions commits", 0, 0, revs->commits); + show_object_array("setup_revisions pending", &revs->pending); } static void bisect_common(struct rev_info *revs) { if (prepare_revision_walk(revs)) die("revision walk setup failed"); + show_list("bisect_common commits", 0, 0, revs->commits); + show_object_array("bisect_common pending", &revs->pending); if (revs->tree_objects) mark_edges_uninteresting(revs, NULL, 0); } @@ -1462,6 +1506,12 @@ void read_bisect_terms(const char **read_bad, const char **read_good) fclose(fp); } +static int debug_print_oid(const struct object_id *oid, void *data) +{ + fprintf(stderr, "%s\n", oid_to_hex(oid)); + return 0; +} + /* * We use the convention that return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10) means * the bisection process finished successfully. @@ -1493,6 +1543,12 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix) if (read_bisect_refs()) die(_("reading bisect refs failed")); read_bisect_confidences(); + if (DEBUG_BISECT) { + debug_bisect("good revs:\n"); + oid_array_for_each(&good_revs, debug_print_oid, NULL); + debug_bisect("p-test revs:\n"); + oid_array_for_each(&ptest_revs, debug_print_oid, NULL); + } if (file_exists(git_path_bisect_first_parent())) bisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY; From patchwork Thu Nov 18 16:49:40 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Kara X-Patchwork-Id: 12627421 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A7962C433EF for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9360B61391 for ; Thu, 18 Nov 2021 16:52:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234079AbhKRQxU (ORCPT ); Thu, 18 Nov 2021 11:53:20 -0500 Received: from smtp-out2.suse.de ([195.135.220.29]:57662 "EHLO smtp-out2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233734AbhKRQww (ORCPT ); Thu, 18 Nov 2021 11:52:52 -0500 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id B8FB21FD56 for ; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=NT9sGEPBqM6vPhi/cHT8+cK9Bk+W5K3bs+clikvUBlU=; b=crafe2tKMZ4xmQfiHP9UD5/TwH5+MZeBrDpLDNjHBQOXtA/MyZvALAvMh4VsAKFIs1VAJF 9rKU3L4NpJBNAvjCx3aMryM4IuCGQpYj7d+0tMRkfK8CSaHem/voR4EfiWfv+WvjaA94Fg jpnOKwQlvw0vBowquLYrmJ8vh+RrJow= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1637254188; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=NT9sGEPBqM6vPhi/cHT8+cK9Bk+W5K3bs+clikvUBlU=; b=tA88GC9bqRYsSneCk7YFLNa8MhbFu/AafqRo7GqNoKWA4yGu+QBS4wLpdfdUNx68rUM/Mm XylVjWwjf3EGh6Cg== Received: from quack2.suse.cz (unknown [10.100.200.198]) by relay2.suse.de (Postfix) with ESMTP id AF1A5A3BA3; Thu, 18 Nov 2021 16:49:48 +0000 (UTC) Received: by quack2.suse.cz (Postfix, from userid 1000) id D20FA1F2CD0; Thu, 18 Nov 2021 17:49:47 +0100 (CET) From: Jan Kara To: git@vger.kernel.org Cc: Jan Kara Subject: [PATCH 27/27] bisect: Allow bisection debugging of approx_halfway() Date: Thu, 18 Nov 2021 17:49:40 +0100 Message-Id: <20211118164940.8818-28-jack@suse.cz> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20211118164940.8818-1-jack@suse.cz> References: <20211118164940.8818-1-jack@suse.cz> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Currently approx_halfway() is shortcircuited when bisection debugging is turned on. Allow possibility of printing all debug messages while keeping approx_halfway() working by setting DEBUG_BISECT to 1. Disable approx_halfway() only when BISECT_DEBUG is larger than 1. Also add a debug message to approx_halfway() to dump info about commit it is selecting. Signed-off-by: Jan Kara --- bisect.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/bisect.c b/bisect.c index 4d2ba5dbd77e..60e8c32056ac 100644 --- a/bisect.c +++ b/bisect.c @@ -207,7 +207,7 @@ static inline int approx_halfway(struct commit_list *p, int nr) */ if (p->item->object.flags & TREESAME) return 0; - if (DEBUG_BISECT) + if (DEBUG_BISECT > 1) return 0; if (!result_confidence) { @@ -230,8 +230,11 @@ static inline int approx_halfway(struct commit_list *p, int nr) diff = frac_to_fp(1, 16); } if (weight(p) > (FP_HALF - diff) * scale && - weight(p) < (FP_HALF + diff) * scale) + weight(p) < (FP_HALF + diff) * scale) { + debug_bisect("found approx half: %lf diff %lf\n", + fp_to_double(weight(p)), fp_to_double(diff)); return 1; + } return 0; }