aboutsummaryrefslogtreecommitdiff
path: root/internal/commitquery/merge_bases.go
diff options
context:
space:
mode:
Diffstat (limited to 'internal/commitquery/merge_bases.go')
-rw-r--r--internal/commitquery/merge_bases.go116
1 files changed, 0 insertions, 116 deletions
diff --git a/internal/commitquery/merge_bases.go b/internal/commitquery/merge_bases.go
deleted file mode 100644
index 62ab9bd6..00000000
--- a/internal/commitquery/merge_bases.go
+++ /dev/null
@@ -1,116 +0,0 @@
-package commitquery
-
-import "slices"
-
-// MergeBases computes fully reduced merge bases using one query context.
-func MergeBases(ctx *Context, left, right NodeIndex) ([]NodeIndex, error) {
- if left == right {
- return []NodeIndex{left}, nil
- }
-
- 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)
-
- return candidates, nil
- }
-
- ctx.ClearTouchedMarks(allMarks)
-
- reduced, err := removeRedundant(ctx, candidates)
- if err != nil {
- return nil, err
- }
-
- slices.SortFunc(reduced, ctx.Compare)
-
- return reduced, nil
-}
-
-func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGeneration uint64) error {
- ctx.BeginMarkPhase()
-
- ctx.SetMarks(left, markLeft)
-
- if len(rights) == 0 {
- ctx.SetMarks(left, markResult)
-
- return nil
- }
-
- queue := newPriorityQueue(ctx)
- queue.PushNode(left)
-
- for _, right := range rights {
- ctx.SetMarks(right, markRight)
- queue.PushNode(right)
- }
-
- lastGeneration := generationInfinity
-
- for queueHasNonStale(ctx, queue) {
- idx := queue.PopNode()
-
- generation := ctx.EffectiveGeneration(idx)
- if generation > lastGeneration {
- return errBadGenerationOrder
- }
-
- lastGeneration = generation
- if generation < minGeneration {
- break
- }
-
- flags := ctx.Marks(idx) & (markLeft | markRight | markStale)
- if flags == (markLeft | markRight) {
- ctx.SetMarks(idx, markResult)
-
- flags |= markStale
- }
-
- for _, parent := range ctx.Parents(idx) {
- if ctx.HasAllMarks(parent, flags) {
- continue
- }
-
- ctx.SetMarks(parent, flags)
- queue.PushNode(parent)
- }
- }
-
- return nil
-}
-
-func queueHasNonStale(ctx *Context, queue *priorityQueue) bool {
- for _, idx := range queue.items {
- if !ctx.HasAnyMarks(idx, markStale) {
- return true
- }
- }
-
- 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
-}