internal/commitquery: paintDown only paints, don't collect

3 files changed, 30 insertions, 19 deletions

diff --git a/internal/commitquery/ancestor.go b/internal/commitquery/ancestor.go
index 78149c6a..d050ce08 100644
--- a/internal/commitquery/ancestor.go
+++ b/internal/commitquery/ancestor.go
@@ -21,7 +21,7 @@ func IsAncestor(ctx *Context, ancestor, descendant NodeIndex) (bool, error) {
 		minGeneration = ancestorGeneration
 	}
 
-	_, err := paintDownToCommon(ctx, ancestor, []NodeIndex{descendant}, minGeneration)
+	err := paintDownToCommon(ctx, ancestor, []NodeIndex{descendant}, minGeneration)
 	if err != nil {
 		return false, err
 	}
diff --git a/internal/commitquery/merge_bases.go b/internal/commitquery/merge_bases.go
index b0171f5e..c4b942f6 100644
--- a/internal/commitquery/merge_bases.go
+++ b/internal/commitquery/merge_bases.go
@@ -8,11 +8,13 @@ func MergeBases(ctx *Context, left, right NodeIndex) ([]NodeIndex, error) {
 		return []NodeIndex{left}, nil
 	}
 
-	candidates, err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0)
+	err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0)
 	if err != nil {
 		return nil, err
 	}
 
+	candidates := collectMarkedResults(ctx)
+
 	if len(candidates) <= 1 {
 		slices.SortFunc(candidates, ctx.Compare)
 
@@ -31,13 +33,15 @@ func MergeBases(ctx *Context, left, right NodeIndex) ([]NodeIndex, error) {
 	return reduced, nil
 }
 
-func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGeneration uint64) ([]NodeIndex, error) {
+func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGeneration uint64) error {
 	ctx.BeginMarkPhase()
 
 	ctx.SetMarks(left, markLeft)
 
 	if len(rights) == 0 {
-		return []NodeIndex{left}, nil
+		ctx.SetMarks(left, markResult)
+
+		return nil
 	}
 
 	queue := NewPriorityQueue(ctx)
@@ -49,14 +53,13 @@ func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGene
 	}
 
 	lastGeneration := generationInfinity
-	results := make([]NodeIndex, 0, 4)
 
 	for queueHasNonStale(ctx, queue) {
 		idx := queue.PopNode()
 
 		generation := ctx.EffectiveGeneration(idx)
 		if generation > lastGeneration {
-			return nil, errBadGenerationOrder
+			return errBadGenerationOrder
 		}
 
 		lastGeneration = generation
@@ -66,10 +69,7 @@ func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGene
 
 		flags := ctx.Marks(idx) & (markLeft | markRight | markStale)
 		if flags == (markLeft | markRight) {
-			if !ctx.HasAnyMarks(idx, markResult) {
-				ctx.SetMarks(idx, markResult)
-				results = append(results, idx)
-			}
+			ctx.SetMarks(idx, markResult)
 
 			flags |= markStale
 		}
@@ -84,14 +84,7 @@ func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGene
 		}
 	}
 
-	out := results[:0]
-	for _, idx := range results {
-		if !ctx.HasAnyMarks(idx, markStale) {
-			out = append(out, idx)
-		}
-	}
-
-	return out, nil
+	return nil
 }
 
 func queueHasNonStale(ctx *Context, queue *PriorityQueue) bool {
@@ -103,3 +96,21 @@ func queueHasNonStale(ctx *Context, queue *PriorityQueue) bool {
 
 	return false
 }
+
+func collectMarkedResults(ctx *Context) []NodeIndex {
+	out := make([]NodeIndex, 0, 4)
+
+	for _, idx := range ctx.touched {
+		if !ctx.HasAnyMarks(idx, markResult) {
+			continue
+		}
+
+		if ctx.HasAnyMarks(idx, markStale) {
+			continue
+		}
+
+		out = append(out, idx)
+	}
+
+	return out
+}
diff --git a/internal/commitquery/reduce.go b/internal/commitquery/reduce.go
index 497ff443..917f2fa2 100644
--- a/internal/commitquery/reduce.go
+++ b/internal/commitquery/reduce.go
@@ -44,7 +44,7 @@ func removeRedundantNoGen(ctx *Context, candidates []NodeIndex) ([]NodeIndex, er
 			}
 		}
 
-		_, err := paintDownToCommon(ctx, candidate, work, minGeneration)
+		err := paintDownToCommon(ctx, candidate, work, minGeneration)
 		if err != nil {
 			return nil, err
 		}