ref: 37707aada0157f255dbad920b917efb601184e12
parent: 41f07c00cefc4561493a8e1ef91550adc4c544f5
author: Runxi Yu <runxiyu@umich.edu>
date: Sun Mar 29 09:38:19 EDT 2026
commitquery: Reorganize
--- a/commitquery/bits.go
+++ /dev/null
@@ -1,14 +1,0 @@
-package commitquery
-
-type markBits uint8
-
-const (
- markLeft markBits = 1 << iota
- markRight
- markStale
- markResult
-)
-
-const (
- allMarks = markLeft | markRight | markStale | markResult
-)
--- a/commitquery/compare.go
+++ /dev/null
@@ -1,25 +1,0 @@
-package commitquery
-
-import objectid "codeberg.org/lindenii/furgit/object/id"
-
-// Compare compares two internal nodes using merge-base queue ordering.
-func (query *query) compare(left, right nodeIndex) int {- leftGeneration := query.effectiveGeneration(left)
- rightGeneration := query.effectiveGeneration(right)
-
- switch {- case leftGeneration < rightGeneration:
- return -1
- case leftGeneration > rightGeneration:
- return 1
- }
-
- switch {- case query.nodes[left].commitTime < query.nodes[right].commitTime:
- return -1
- case query.nodes[left].commitTime > query.nodes[right].commitTime:
- return 1
- }
-
- return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
-}
--- a/commitquery/generation.go
+++ /dev/null
@@ -1,43 +1,0 @@
-package commitquery
-
-import (
- "math"
-
- objectid "codeberg.org/lindenii/furgit/object/id"
-)
-
-// EffectiveGeneration returns one node's generation value.
-func (query *query) effectiveGeneration(idx nodeIndex) uint64 {- if !query.nodes[idx].hasGeneration {- return generationInfinity
- }
-
- return query.nodes[idx].generation
-}
-
-const (
- generationInfinity = uint64(math.MaxUint64)
-)
-
-func compareByGeneration(query *query) func(nodeIndex, nodeIndex) int {- return func(left, right nodeIndex) int {- leftGeneration := query.effectiveGeneration(left)
- rightGeneration := query.effectiveGeneration(right)
-
- switch {- case leftGeneration < rightGeneration:
- return -1
- case leftGeneration > rightGeneration:
- return 1
- }
-
- switch {- case query.nodes[left].commitTime < query.nodes[right].commitTime:
- return -1
- case query.nodes[left].commitTime > query.nodes[right].commitTime:
- return 1
- }
-
- return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
- }
-}
--- a/commitquery/load.go
+++ b/commitquery/load.go
@@ -1,5 +1,15 @@
package commitquery
+import (
+ stderrors "errors"
+
+ giterrors "codeberg.org/lindenii/furgit/errors"
+ commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+ objectcommit "codeberg.org/lindenii/furgit/object/commit"
+ objectstore "codeberg.org/lindenii/furgit/object/store"
+ objecttype "codeberg.org/lindenii/furgit/object/type"
+)
+
// ensureLoaded completes one node's metadata load if it has not been loaded yet.
func (query *query) ensureLoaded(idx nodeIndex) error { if query.nodes[idx].loaded {@@ -11,4 +21,51 @@
}
return query.loadByOID(idx)
+}
+
+// loadByOID populates one node from an object ID.
+func (query *query) loadByOID(idx nodeIndex) error {+ id := query.nodes[idx].id
+
+ if query.graph != nil {+ pos, err := query.graph.Lookup(id)
+ if err != nil {+ if _, ok := stderrors.AsType[*commitgraphread.NotFoundError](err); !ok {+ return err
+ }
+ } else {+ return query.loadCommitAtGraphPos(idx, pos)
+ }
+ }
+
+ ty, content, err := query.store.ReadBytesContent(id)
+ if err != nil {+ if stderrors.Is(err, objectstore.ErrObjectNotFound) {+ return &giterrors.ObjectMissingError{OID: id}+ }
+
+ return err
+ }
+
+ if ty != objecttype.TypeCommit {+ return &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit}+ }
+
+ commitObj, err := objectcommit.Parse(content, id.Algorithm())
+ if err != nil {+ return err
+ }
+
+ parents := make([]parentRef, 0, len(commitObj.Parents))
+ for _, parentID := range commitObj.Parents {+ parents = append(parents, parentRef{ID: parentID})+ }
+
+ commit := commitData{+ ID: id,
+ Parents: parents,
+ CommitTime: commitObj.Committer.WhenUnix,
+ }
+
+ return query.populateNode(idx, commit)
}
--- a/commitquery/marks.go
+++ b/commitquery/marks.go
@@ -87,3 +87,16 @@
return out
}
+
+type markBits uint8
+
+const (
+ markLeft markBits = 1 << iota
+ markRight
+ markStale
+ markResult
+)
+
+const (
+ allMarks = markLeft | markRight | markStale | markResult
+)
--- a/commitquery/node.go
+++ b/commitquery/node.go
@@ -5,9 +5,6 @@
objectid "codeberg.org/lindenii/furgit/object/id"
)
-// nodeIndex identifies one internal query node.
-type nodeIndex int
-
// node stores one mutable commit traversal node.
type node struct {id objectid.ObjectID
@@ -25,15 +22,4 @@
marks markBits
touchedPhase uint32
-}
-
-// newNode allocates one empty internal node.
-func (query *query) newNode(id objectid.ObjectID) nodeIndex {- count := len(query.nodes)
-
- idx := nodeIndex(count)
-
- query.nodes = append(query.nodes, node{id: id})-
- return idx
}
--- /dev/null
+++ b/commitquery/node_commit_time.go
@@ -1,0 +1,5 @@
+package commitquery
+
+func (query *query) commitTime(idx nodeIndex) int64 {+ return query.nodes[idx].commitTime
+}
--- /dev/null
+++ b/commitquery/node_compare.go
@@ -1,0 +1,25 @@
+package commitquery
+
+import objectid "codeberg.org/lindenii/furgit/object/id"
+
+// Compare compares two internal nodes using merge-base queue ordering.
+func (query *query) compare(left, right nodeIndex) int {+ leftGeneration := query.effectiveGeneration(left)
+ rightGeneration := query.effectiveGeneration(right)
+
+ switch {+ case leftGeneration < rightGeneration:
+ return -1
+ case leftGeneration > rightGeneration:
+ return 1
+ }
+
+ switch {+ case query.nodes[left].commitTime < query.nodes[right].commitTime:
+ return -1
+ case query.nodes[left].commitTime > query.nodes[right].commitTime:
+ return 1
+ }
+
+ return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
+}
--- /dev/null
+++ b/commitquery/node_generation.go
@@ -1,0 +1,43 @@
+package commitquery
+
+import (
+ "math"
+
+ objectid "codeberg.org/lindenii/furgit/object/id"
+)
+
+// EffectiveGeneration returns one node's generation value.
+func (query *query) effectiveGeneration(idx nodeIndex) uint64 {+ if !query.nodes[idx].hasGeneration {+ return generationInfinity
+ }
+
+ return query.nodes[idx].generation
+}
+
+const (
+ generationInfinity = uint64(math.MaxUint64)
+)
+
+func (query *query) compareByGeneration() func(nodeIndex, nodeIndex) int {+ return func(left, right nodeIndex) int {+ leftGeneration := query.effectiveGeneration(left)
+ rightGeneration := query.effectiveGeneration(right)
+
+ switch {+ case leftGeneration < rightGeneration:
+ return -1
+ case leftGeneration > rightGeneration:
+ return 1
+ }
+
+ switch {+ case query.nodes[left].commitTime < query.nodes[right].commitTime:
+ return -1
+ case query.nodes[left].commitTime > query.nodes[right].commitTime:
+ return 1
+ }
+
+ return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
+ }
+}
--- /dev/null
+++ b/commitquery/node_id.go
@@ -1,0 +1,7 @@
+package commitquery
+
+import objectid "codeberg.org/lindenii/furgit/object/id"
+
+func (query *query) id(idx nodeIndex) objectid.ObjectID {+ return query.nodes[idx].id
+}
--- /dev/null
+++ b/commitquery/node_index.go
@@ -1,0 +1,4 @@
+package commitquery
+
+// nodeIndex identifies one internal query node.
+type nodeIndex int
--- /dev/null
+++ b/commitquery/node_new.go
@@ -1,0 +1,14 @@
+package commitquery
+
+import objectid "codeberg.org/lindenii/furgit/object/id"
+
+// newNode allocates one empty internal node.
+func (query *query) newNode(id objectid.ObjectID) nodeIndex {+ count := len(query.nodes)
+
+ idx := nodeIndex(count)
+
+ query.nodes = append(query.nodes, node{id: id})+
+ return idx
+}
--- /dev/null
+++ b/commitquery/node_paint_down_to_common.go
@@ -1,0 +1,55 @@
+package commitquery
+
+func (query *query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGeneration uint64) error {+ query.beginMarkPhase()
+
+ query.setMarks(left, markLeft)
+
+ if len(rights) == 0 {+ query.setMarks(left, markResult)
+
+ return nil
+ }
+
+ queue := newPriorityQueue(query)
+ queue.PushNode(left)
+
+ for _, right := range rights {+ query.setMarks(right, markRight)
+ queue.PushNode(right)
+ }
+
+ lastGeneration := generationInfinity
+
+ for query.queueHasNonStale(queue) {+ idx := queue.PopNode()
+
+ generation := query.effectiveGeneration(idx)
+ if generation > lastGeneration {+ return errBadGenerationOrder
+ }
+
+ lastGeneration = generation
+ if generation < minGeneration {+ break
+ }
+
+ flags := query.marks(idx) & (markLeft | markRight | markStale)
+ if flags == (markLeft | markRight) {+ query.setMarks(idx, markResult)
+
+ flags |= markStale
+ }
+
+ for _, parent := range query.parents(idx) {+ if query.hasAllMarks(parent, flags) {+ continue
+ }
+
+ query.setMarks(parent, flags)
+ queue.PushNode(parent)
+ }
+ }
+
+ return nil
+}
--- /dev/null
+++ b/commitquery/node_parent.go
@@ -1,0 +1,27 @@
+package commitquery
+
+import (
+ commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+ objectid "codeberg.org/lindenii/furgit/object/id"
+)
+
+// Parents returns resolved parent node indices for one internal node.
+func (query *query) parents(idx nodeIndex) []nodeIndex {+ return query.nodes[idx].parents
+}
+
+// parentRef references one commit parent.
+type parentRef struct {+ ID objectid.ObjectID
+ GraphPos commitgraphread.Position
+ HasGraphPos bool
+}
+
+// resolveParent resolves one parent descriptor to one internal node.
+func (query *query) resolveParent(parent parentRef) (nodeIndex, error) {+ if parent.HasGraphPos {+ return query.resolveGraphPos(parent.GraphPos)
+ }
+
+ return query.resolveOID(parent.ID)
+}
--- /dev/null
+++ b/commitquery/node_populate.go
@@ -1,0 +1,42 @@
+package commitquery
+
+import "fmt"
+
+// populateNode fills one node's metadata and resolves its parents.
+func (query *query) populateNode(idx nodeIndex, commit commitData) error {+ if query.nodes[idx].loaded {+ if query.nodes[idx].id != commit.ID {+ return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", query.nodes[idx].id, commit.ID)+ }
+
+ return nil
+ }
+
+ query.nodes[idx].id = commit.ID
+ query.nodes[idx].commitTime = commit.CommitTime
+ query.nodes[idx].generation = commit.Generation
+ query.nodes[idx].hasGeneration = commit.HasGeneration
+
+ if commit.HasGraphPos {+ query.nodes[idx].graphPos = commit.GraphPos
+ query.nodes[idx].hasGraphPos = true
+ query.byGraphPos[commit.GraphPos] = idx
+ }
+
+ query.nodes[idx].loaded = true
+ query.nodes[idx].parents = query.nodes[idx].parents[:0]
+
+ for _, parent := range commit.Parents {+ parentIdx, err := query.resolveParent(parent)
+ if err != nil {+ query.nodes[idx].loaded = false
+ query.nodes[idx].parents = nil
+
+ return err
+ }
+
+ query.nodes[idx].parents = append(query.nodes[idx].parents, parentIdx)
+ }
+
+ return nil
+}
--- a/commitquery/oid.go
+++ /dev/null
@@ -1,101 +1,0 @@
-package commitquery
-
-import (
- stderrors "errors"
-
- giterrors "codeberg.org/lindenii/furgit/errors"
- commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
- "codeberg.org/lindenii/furgit/internal/peel"
- objectcommit "codeberg.org/lindenii/furgit/object/commit"
- objectid "codeberg.org/lindenii/furgit/object/id"
- objectstore "codeberg.org/lindenii/furgit/object/store"
- objecttype "codeberg.org/lindenii/furgit/object/type"
-)
-
-func (query *query) id(idx nodeIndex) objectid.ObjectID {- return query.nodes[idx].id
-}
-
-func (query *query) commitTime(idx nodeIndex) int64 {- return query.nodes[idx].commitTime
-}
-
-func (query *query) resolveOID(id objectid.ObjectID) (nodeIndex, error) {- idx, ok := query.byOID[id]
- if ok {- err := query.ensureLoaded(idx)
- if err != nil {- return 0, err
- }
-
- return idx, nil
- }
-
- idx = query.newNode(id)
- query.byOID[id] = idx
-
- err := query.loadByOID(idx)
- if err != nil {- delete(query.byOID, id)
-
- return 0, err
- }
-
- return idx, nil
-}
-
-func (query *query) resolveCommitish(id objectid.ObjectID) (nodeIndex, error) {- commitID, err := peel.ToCommit(query.store, id)
- if err != nil {- return 0, err
- }
-
- return query.resolveOID(commitID)
-}
-
-// loadByOID populates one node from an object ID.
-func (query *query) loadByOID(idx nodeIndex) error {- id := query.nodes[idx].id
-
- if query.graph != nil {- pos, err := query.graph.Lookup(id)
- if err != nil {- if _, ok := stderrors.AsType[*commitgraphread.NotFoundError](err); !ok {- return err
- }
- } else {- return query.loadCommitAtGraphPos(idx, pos)
- }
- }
-
- ty, content, err := query.store.ReadBytesContent(id)
- if err != nil {- if stderrors.Is(err, objectstore.ErrObjectNotFound) {- return &giterrors.ObjectMissingError{OID: id}- }
-
- return err
- }
-
- if ty != objecttype.TypeCommit {- return &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit}- }
-
- commitObj, err := objectcommit.Parse(content, id.Algorithm())
- if err != nil {- return err
- }
-
- parents := make([]parentRef, 0, len(commitObj.Parents))
- for _, parentID := range commitObj.Parents {- parents = append(parents, parentRef{ID: parentID})- }
-
- commit := commitData{- ID: id,
- Parents: parents,
- CommitTime: commitObj.Committer.WhenUnix,
- }
-
- return query.populateNode(idx, commit)
-}
--- a/commitquery/paint.go
+++ /dev/null
@@ -1,55 +1,0 @@
-package commitquery
-
-func (query *query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGeneration uint64) error {- query.beginMarkPhase()
-
- query.setMarks(left, markLeft)
-
- if len(rights) == 0 {- query.setMarks(left, markResult)
-
- return nil
- }
-
- queue := newPriorityQueue(query)
- queue.PushNode(left)
-
- for _, right := range rights {- query.setMarks(right, markRight)
- queue.PushNode(right)
- }
-
- lastGeneration := generationInfinity
-
- for query.queueHasNonStale(queue) {- idx := queue.PopNode()
-
- generation := query.effectiveGeneration(idx)
- if generation > lastGeneration {- return errBadGenerationOrder
- }
-
- lastGeneration = generation
- if generation < minGeneration {- break
- }
-
- flags := query.marks(idx) & (markLeft | markRight | markStale)
- if flags == (markLeft | markRight) {- query.setMarks(idx, markResult)
-
- flags |= markStale
- }
-
- for _, parent := range query.parents(idx) {- if query.hasAllMarks(parent, flags) {- continue
- }
-
- query.setMarks(parent, flags)
- queue.PushNode(parent)
- }
- }
-
- return nil
-}
--- a/commitquery/parent.go
+++ /dev/null
@@ -1,27 +1,0 @@
-package commitquery
-
-import (
- commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
- objectid "codeberg.org/lindenii/furgit/object/id"
-)
-
-// parentRef references one commit parent.
-type parentRef struct {- ID objectid.ObjectID
- GraphPos commitgraphread.Position
- HasGraphPos bool
-}
-
-// Parents returns resolved parent node indices for one internal node.
-func (query *query) parents(idx nodeIndex) []nodeIndex {- return query.nodes[idx].parents
-}
-
-// resolveParent resolves one parent descriptor to one internal node.
-func (query *query) resolveParent(parent parentRef) (nodeIndex, error) {- if parent.HasGraphPos {- return query.resolveGraphPos(parent.GraphPos)
- }
-
- return query.resolveOID(parent.ID)
-}
--- a/commitquery/populate.go
+++ /dev/null
@@ -1,42 +1,0 @@
-package commitquery
-
-import "fmt"
-
-// populateNode fills one node's metadata and resolves its parents.
-func (query *query) populateNode(idx nodeIndex, commit commitData) error {- if query.nodes[idx].loaded {- if query.nodes[idx].id != commit.ID {- return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", query.nodes[idx].id, commit.ID)- }
-
- return nil
- }
-
- query.nodes[idx].id = commit.ID
- query.nodes[idx].commitTime = commit.CommitTime
- query.nodes[idx].generation = commit.Generation
- query.nodes[idx].hasGeneration = commit.HasGeneration
-
- if commit.HasGraphPos {- query.nodes[idx].graphPos = commit.GraphPos
- query.nodes[idx].hasGraphPos = true
- query.byGraphPos[commit.GraphPos] = idx
- }
-
- query.nodes[idx].loaded = true
- query.nodes[idx].parents = query.nodes[idx].parents[:0]
-
- for _, parent := range commit.Parents {- parentIdx, err := query.resolveParent(parent)
- if err != nil {- query.nodes[idx].loaded = false
- query.nodes[idx].parents = nil
-
- return err
- }
-
- query.nodes[idx].parents = append(query.nodes[idx].parents, parentIdx)
- }
-
- return nil
-}
--- a/commitquery/reduce.go
+++ b/commitquery/reduce.go
@@ -74,7 +74,7 @@
func removeRedundantWithGen(query *query, candidates []nodeIndex) []nodeIndex {sorted := append([]nodeIndex(nil), candidates...)
- slices.SortFunc(sorted, compareByGeneration(query))
+ slices.SortFunc(sorted, query.compareByGeneration())
minGeneration := query.effectiveGeneration(sorted[0])
minGenPos := 0
@@ -97,7 +97,7 @@
}
}
- slices.SortFunc(walkStart, compareByGeneration(query))
+ slices.SortFunc(walkStart, query.compareByGeneration())
for _, idx := range walkStart {query.clearMarks(idx, markStale)
--- /dev/null
+++ b/commitquery/resolve.go
@@ -1,0 +1,39 @@
+package commitquery
+
+import (
+ "codeberg.org/lindenii/furgit/internal/peel"
+ objectid "codeberg.org/lindenii/furgit/object/id"
+)
+
+func (query *query) resolveOID(id objectid.ObjectID) (nodeIndex, error) {+ idx, ok := query.byOID[id]
+ if ok {+ err := query.ensureLoaded(idx)
+ if err != nil {+ return 0, err
+ }
+
+ return idx, nil
+ }
+
+ idx = query.newNode(id)
+ query.byOID[id] = idx
+
+ err := query.loadByOID(idx)
+ if err != nil {+ delete(query.byOID, id)
+
+ return 0, err
+ }
+
+ return idx, nil
+}
+
+func (query *query) resolveCommitish(id objectid.ObjectID) (nodeIndex, error) {+ commitID, err := peel.ToCommit(query.store, id)
+ if err != nil {+ return 0, err
+ }
+
+ return query.resolveOID(commitID)
+}
--
⑨