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 <jack@xxxxxxx>
---
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) &&
--
2.26.2
