Artifact [b06ad25c68]

Artifact b06ad25c684a1737b79e353a1b71708a4da6a773cc718e95d9f41c810a2383de:

• File internal/merge/ancestor.go — part of check-in [f5744359d3] at 2026-04-19 16:30:54 on branch trunk — Initial open source release

  libfossil is a pure-Go implementation of the Fossil SCM, reading and writing the same .fossil SQLite repository format as upstream Fossil.

  This is the first public release of code that previously lived in a private repository. The module path is github.com/danmestas/libfossil and the binary is named libfossil to avoid $PATH collisions with upstream fossil.

  Included: - Repo lifecycle (create, clone), checkout/checkin, timeline, merge, diff, annotate, shun, tag, branch, bisect, stash, undo/redo - Sync-over-HTTP protocol (client and handler) - Two SQLite drivers: modernc (pure Go, default) and ncruces (wasm-capable) - Observer interfaces (SyncObserver, CheckoutObserver) with an optional OpenTelemetry implementation in observer/otel (separate submodule) - Deterministic simulation testing harness with BUGGIFY fault injection - Kong-based embeddable CLI under cli/ and a standalone binary under cmd/libfossil/ (user: [email protected], size: 2147) [annotate] [blame] [check-ins using]

package merge

import (
	"fmt"

	libfossil "github.com/danmestas/libfossil/internal/fsltype"
	"github.com/danmestas/libfossil/internal/repo"
)

// FindCommonAncestor walks the plink DAG backwards from two checkin rids
// to find their most recent common ancestor via bidirectional BFS.
func FindCommonAncestor(r *repo.Repo, ridA, ridB libfossil.FslID) (libfossil.FslID, error) {
	if r == nil {
		panic("merge.FindCommonAncestor: r must not be nil")
	}
	if ridA <= 0 {
		panic("merge.FindCommonAncestor: ridA must be positive")
	}
	if ridB <= 0 {
		panic("merge.FindCommonAncestor: ridB must be positive")
	}
	if ridA == ridB {
		return ridA, nil
	}

	visitedA := map[libfossil.FslID]bool{ridA: true}
	visitedB := map[libfossil.FslID]bool{ridB: true}
	queueA := []libfossil.FslID{ridA}
	queueB := []libfossil.FslID{ridB}

	for len(queueA) > 0 || len(queueB) > 0 {
		if len(queueA) > 0 {
			current := queueA[0]
			queueA = queueA[1:]
			if visitedB[current] {
				return current, nil
			}
			parents, err := getParents(r, current)
			if err != nil {
				return 0, err
			}
			for _, pid := range parents {
				if !visitedA[pid] {
					visitedA[pid] = true
					if visitedB[pid] {
						return pid, nil
					}
					queueA = append(queueA, pid)
				}
			}
		}

		if len(queueB) > 0 {
			current := queueB[0]
			queueB = queueB[1:]
			if visitedA[current] {
				return current, nil
			}
			parents, err := getParents(r, current)
			if err != nil {
				return 0, err
			}
			for _, pid := range parents {
				if !visitedB[pid] {
					visitedB[pid] = true
					if visitedA[pid] {
						return pid, nil
					}
					queueB = append(queueB, pid)
				}
			}
		}
	}

	return 0, fmt.Errorf("no common ancestor for rid %d and %d", ridA, ridB)
}

func getParents(r *repo.Repo, rid libfossil.FslID) ([]libfossil.FslID, error) {
	rows, err := r.DB().Query("SELECT pid FROM plink WHERE cid=?", rid)
	if err != nil {
		return nil, err
	}
	defer rows.Close()
	var parents []libfossil.FslID
	for rows.Next() {
		var pid int64
		if err := rows.Scan(&pid); err != nil {
			continue
		}
		parents = append(parents, libfossil.FslID(pid))
	}
	return parents, rows.Err()
}