From 37707aada0157f255dbad920b917efb601184e12 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Sun, 29 Mar 2026 13:38:19 +0000 Subject: commitquery: Reorganize --- commitquery/bits.go | 14 ----- commitquery/compare.go | 25 -------- commitquery/generation.go | 43 ------------- commitquery/load.go | 57 +++++++++++++++++ commitquery/marks.go | 13 ++++ commitquery/node.go | 14 ----- commitquery/node_commit_time.go | 5 ++ commitquery/node_compare.go | 25 ++++++++ commitquery/node_generation.go | 43 +++++++++++++ commitquery/node_id.go | 7 +++ commitquery/node_index.go | 4 ++ commitquery/node_new.go | 14 +++++ commitquery/node_paint_down_to_common.go | 55 +++++++++++++++++ commitquery/node_parent.go | 27 +++++++++ commitquery/node_populate.go | 42 +++++++++++++ commitquery/oid.go | 101 ------------------------------- commitquery/paint.go | 55 ----------------- commitquery/parent.go | 27 --------- commitquery/populate.go | 42 ------------- commitquery/reduce.go | 4 +- commitquery/resolve.go | 39 ++++++++++++ 21 files changed, 333 insertions(+), 323 deletions(-) delete mode 100644 commitquery/bits.go delete mode 100644 commitquery/compare.go delete mode 100644 commitquery/generation.go create mode 100644 commitquery/node_commit_time.go create mode 100644 commitquery/node_compare.go create mode 100644 commitquery/node_generation.go create mode 100644 commitquery/node_id.go create mode 100644 commitquery/node_index.go create mode 100644 commitquery/node_new.go create mode 100644 commitquery/node_paint_down_to_common.go create mode 100644 commitquery/node_parent.go create mode 100644 commitquery/node_populate.go delete mode 100644 commitquery/oid.go delete mode 100644 commitquery/paint.go delete mode 100644 commitquery/parent.go delete mode 100644 commitquery/populate.go create mode 100644 commitquery/resolve.go diff --git a/commitquery/bits.go b/commitquery/bits.go deleted file mode 100644 index 36ffff29..00000000 --- a/commitquery/bits.go +++ /dev/null @@ -1,14 +0,0 @@ -package commitquery - -type markBits uint8 - -const ( - markLeft markBits = 1 << iota - markRight - markStale - markResult -) - -const ( - allMarks = markLeft | markRight | markStale | markResult -) diff --git a/commitquery/compare.go b/commitquery/compare.go deleted file mode 100644 index 7ae984dc..00000000 --- a/commitquery/compare.go +++ /dev/null @@ -1,25 +0,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) -} diff --git a/commitquery/generation.go b/commitquery/generation.go deleted file mode 100644 index 935da104..00000000 --- a/commitquery/generation.go +++ /dev/null @@ -1,43 +0,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) - } -} diff --git a/commitquery/load.go b/commitquery/load.go index be39c7d9..076f3000 100644 --- 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 { @@ -12,3 +22,50 @@ func (query *query) ensureLoaded(idx nodeIndex) error { 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) +} diff --git a/commitquery/marks.go b/commitquery/marks.go index 43ca9f44..2d0b013f 100644 --- a/commitquery/marks.go +++ b/commitquery/marks.go @@ -87,3 +87,16 @@ func (query *query) collectMarkedResults() []nodeIndex { return out } + +type markBits uint8 + +const ( + markLeft markBits = 1 << iota + markRight + markStale + markResult +) + +const ( + allMarks = markLeft | markRight | markStale | markResult +) diff --git a/commitquery/node.go b/commitquery/node.go index d5f1d3cd..7432a719 100644 --- a/commitquery/node.go +++ b/commitquery/node.go @@ -5,9 +5,6 @@ import ( 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 @@ -26,14 +23,3 @@ type node struct { 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 -} diff --git a/commitquery/node_commit_time.go b/commitquery/node_commit_time.go new file mode 100644 index 00000000..3c42673d --- /dev/null +++ b/commitquery/node_commit_time.go @@ -0,0 +1,5 @@ +package commitquery + +func (query *query) commitTime(idx nodeIndex) int64 { + return query.nodes[idx].commitTime +} diff --git a/commitquery/node_compare.go b/commitquery/node_compare.go new file mode 100644 index 00000000..7ae984dc --- /dev/null +++ b/commitquery/node_compare.go @@ -0,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) +} diff --git a/commitquery/node_generation.go b/commitquery/node_generation.go new file mode 100644 index 00000000..b04f3762 --- /dev/null +++ b/commitquery/node_generation.go @@ -0,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) + } +} diff --git a/commitquery/node_id.go b/commitquery/node_id.go new file mode 100644 index 00000000..c1d82f38 --- /dev/null +++ b/commitquery/node_id.go @@ -0,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 +} diff --git a/commitquery/node_index.go b/commitquery/node_index.go new file mode 100644 index 00000000..06122d62 --- /dev/null +++ b/commitquery/node_index.go @@ -0,0 +1,4 @@ +package commitquery + +// nodeIndex identifies one internal query node. +type nodeIndex int diff --git a/commitquery/node_new.go b/commitquery/node_new.go new file mode 100644 index 00000000..14a35262 --- /dev/null +++ b/commitquery/node_new.go @@ -0,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 +} diff --git a/commitquery/node_paint_down_to_common.go b/commitquery/node_paint_down_to_common.go new file mode 100644 index 00000000..6bb1f489 --- /dev/null +++ b/commitquery/node_paint_down_to_common.go @@ -0,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 +} diff --git a/commitquery/node_parent.go b/commitquery/node_parent.go new file mode 100644 index 00000000..17224701 --- /dev/null +++ b/commitquery/node_parent.go @@ -0,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) +} diff --git a/commitquery/node_populate.go b/commitquery/node_populate.go new file mode 100644 index 00000000..26fb5629 --- /dev/null +++ b/commitquery/node_populate.go @@ -0,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 +} diff --git a/commitquery/oid.go b/commitquery/oid.go deleted file mode 100644 index fd524dfb..00000000 --- a/commitquery/oid.go +++ /dev/null @@ -1,101 +0,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) -} diff --git a/commitquery/paint.go b/commitquery/paint.go deleted file mode 100644 index 6bb1f489..00000000 --- a/commitquery/paint.go +++ /dev/null @@ -1,55 +0,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 -} diff --git a/commitquery/parent.go b/commitquery/parent.go deleted file mode 100644 index fe0f4fba..00000000 --- a/commitquery/parent.go +++ /dev/null @@ -1,27 +0,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) -} diff --git a/commitquery/populate.go b/commitquery/populate.go deleted file mode 100644 index 26fb5629..00000000 --- a/commitquery/populate.go +++ /dev/null @@ -1,42 +0,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 -} diff --git a/commitquery/reduce.go b/commitquery/reduce.go index f8a86f69..46c3bf39 100644 --- a/commitquery/reduce.go +++ b/commitquery/reduce.go @@ -74,7 +74,7 @@ func removeRedundantNoGen(query *query, candidates []nodeIndex) ([]nodeIndex, er 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 @@ func removeRedundantWithGen(query *query, candidates []nodeIndex) []nodeIndex { } } - slices.SortFunc(walkStart, compareByGeneration(query)) + slices.SortFunc(walkStart, query.compareByGeneration()) for _, idx := range walkStart { query.clearMarks(idx, markStale) diff --git a/commitquery/resolve.go b/commitquery/resolve.go new file mode 100644 index 00000000..cd6c3650 --- /dev/null +++ b/commitquery/resolve.go @@ -0,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) +} -- cgit v1.3.1-10-gc9f91