This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/iceberg-go.git
The following commit(s) were added to refs/heads/main by this push:
new 84c6fd693 refactor(table): unify cycle-safe snapshot ancestry walks
(#2285)
84c6fd693 is described below
commit 84c6fd693fe25bc9f6e3c9d99ef733930a6bc30f
Author: Minh Vu <[email protected]>
AuthorDate: Fri Oct 23 20:26:03 2026 +0200
refactor(table): unify cycle-safe snapshot ancestry walks (#2285)
* refactor(table): unify cycle-safe snapshot ancestry walks
Signed-off-by: Minh Vu <[email protected]>
* test(table): guard self-referencing snapshot ancestry
* style(table): satisfy nlreturn in ancestry test
---------
Signed-off-by: Minh Vu <[email protected]>
---
table/snapshot_ancestry.go | 121 ++++++++++++++++------------------------
table/snapshot_ancestry_test.go | 66 ++++++++++++++++++++++
2 files changed, 115 insertions(+), 72 deletions(-)
diff --git a/table/snapshot_ancestry.go b/table/snapshot_ancestry.go
index 7fe95c653..bb233f7f3 100644
--- a/table/snapshot_ancestry.go
+++ b/table/snapshot_ancestry.go
@@ -64,6 +64,51 @@ func (s *snapshotVisitSet) seenOrAdd(id int64) bool {
return false
}
+// ancestryWalkMode selects how a snapshot ancestry walk ends.
+// An expired base ID can end a conflict-detection walk, but checking whether
+// an ID is an ancestor requires resolving that snapshot.
+type ancestryWalkMode uint8
+
+const (
+ ancestryToRoot ancestryWalkMode = iota
+ ancestryBeforeBase
+ ancestryToResolvedAncestor
+)
+
+// walkSnapshotAncestry shares parent traversal, missing-snapshot handling and
+// cycle detection. Only the first two modes accumulate snapshot values.
+func walkSnapshotAncestry(startID, boundaryID int64, lookup SnapshotLookup,
mode ancestryWalkMode) ([]Snapshot, bool) {
+ var history []Snapshot
+ var visited snapshotVisitSet
+
+ id := startID
+ for {
+ // A base may have expired, so stop before resolving it.
+ if mode == ancestryBeforeBase && id == boundaryID {
+ return history, true
+ }
+ if visited.seenOrAdd(id) {
+ return history, false
+ }
+ snap := lookup(id)
+ if snap == nil {
+ return history, false
+ }
+
+ // Membership requires the candidate ancestor to resolve.
+ if mode == ancestryToResolvedAncestor && id == boundaryID {
+ return nil, true
+ }
+ if mode != ancestryToResolvedAncestor {
+ history = append(history, *snap)
+ }
+ if snap.ParentSnapshotID == nil {
+ return history, mode == ancestryToRoot
+ }
+ id = *snap.ParentSnapshotID
+ }
+}
+
// AncestorsOf walks the parent chain starting from snapshotID and yields
// every snapshot reachable via ParentSnapshotID, including the starting
// snapshot itself. Iteration stops when a snapshot has no parent, the
@@ -99,27 +144,7 @@ func AncestorsOf(snapshotID int64, lookup SnapshotLookup)
[]Snapshot {
// Snapshots are returned by value in reverse-chronological order.
// Returns an empty slice and false when snapshotID cannot be resolved.
func AncestorsOfChecked(snapshotID int64, lookup SnapshotLookup) ([]Snapshot,
bool) {
- var ancestors []Snapshot
- var visited snapshotVisitSet
-
- id := snapshotID
- for {
- if visited.seenOrAdd(id) {
- return ancestors, false
- }
-
- snap := lookup(id)
- if snap == nil {
- return ancestors, false
- }
-
- ancestors = append(ancestors, *snap)
-
- if snap.ParentSnapshotID == nil {
- return ancestors, true
- }
- id = *snap.ParentSnapshotID
- }
+ return walkSnapshotAncestry(snapshotID, 0, lookup, ancestryToRoot)
}
// AncestorsBetween returns the snapshots from latestID (inclusive) down
@@ -147,33 +172,7 @@ func AncestorsBetween(latestID, baseID int64, lookup
SnapshotLookup) ([]Snapshot
return nil, true
}
- var between []Snapshot
- var visited snapshotVisitSet
-
- id := latestID
- for {
- if id == baseID {
- return between, true
- }
- if visited.seenOrAdd(id) {
- // Cycle detected before reaching baseID.
- break
- }
-
- snap := lookup(id)
- if snap == nil {
- break
- }
-
- between = append(between, *snap)
-
- if snap.ParentSnapshotID == nil {
- break
- }
- id = *snap.ParentSnapshotID
- }
-
- return between, false
+ return walkSnapshotAncestry(latestID, baseID, lookup,
ancestryBeforeBase)
}
// IsAncestorOf returns true if ancestorID is in the parent chain of
@@ -189,29 +188,7 @@ func AncestorsBetween(latestID, baseID int64, lookup
SnapshotLookup) ([]Snapshot
// semantics are stricter (conservative) — broken chains return false
// rather than matching an unreachable ancestor id.
func IsAncestorOf(snapshotID, ancestorID int64, lookup SnapshotLookup) bool {
- var visited snapshotVisitSet
-
- id := snapshotID
- for {
- if visited.seenOrAdd(id) {
- return false
- }
-
- snap := lookup(id)
- if snap == nil {
- return false
- }
-
- // Resolve before matching, so an absent ancestor ID does not
- // count as reachable. An ID inside a cycle succeeds on its
first
- // visit, before cycle detection can reject a repeated ID.
- if id == ancestorID {
- return true
- }
+ _, found := walkSnapshotAncestry(snapshotID, ancestorID, lookup,
ancestryToResolvedAncestor)
- if snap.ParentSnapshotID == nil {
- return false
- }
- id = *snap.ParentSnapshotID
- }
+ return found
}
diff --git a/table/snapshot_ancestry_test.go b/table/snapshot_ancestry_test.go
index fa1c75842..65aac0d4e 100644
--- a/table/snapshot_ancestry_test.go
+++ b/table/snapshot_ancestry_test.go
@@ -94,6 +94,29 @@ func TestAncestorsOf_BrokenChain(t *testing.T) {
assert.Equal(t, []int64{3}, snapshotIDs(got))
}
+func TestSnapshotAncestrySelfCycleTerminates(t *testing.T) {
+ id := int64(17)
+ snapshot := Snapshot{SnapshotID: id, ParentSnapshotID: &id}
+ lookup := func(candidate int64) *Snapshot {
+ if candidate == id {
+ return &snapshot
+ }
+
+ return nil
+ }
+
+ ancestors, complete := AncestorsOfChecked(id, lookup)
+ assert.False(t, complete)
+ assert.Equal(t, []int64{id}, snapshotIDs(ancestors))
+
+ between, found := AncestorsBetween(id, 999, lookup)
+ assert.False(t, found)
+ assert.Equal(t, []int64{id}, snapshotIDs(between))
+
+ assert.True(t, IsAncestorOf(id, id, lookup))
+ assert.False(t, IsAncestorOf(id, 999, lookup))
+}
+
func TestAncestorsOf_CycleDefense(t *testing.T) {
got := AncestorsOf(1, buildCycle())
@@ -289,3 +312,46 @@ func snapshotIDs(snaps []Snapshot) []int64 {
return ids
}
+
+func TestSnapshotAncestryWalkBoundarySemantics(t *testing.T) {
+ // The parent has expired, but its ID remains recorded on the child.
+ // Conflict checks may use it as an exclusive base while membership must
+ // resolve the requested ancestor.
+ parentID := int64(7)
+ childID := int64(8)
+ child := Snapshot{SnapshotID: childID, ParentSnapshotID: &parentID}
+
+ var lookedUp []int64
+ lookup := func(id int64) *Snapshot {
+ lookedUp = append(lookedUp, id)
+ if id == childID {
+ return &child
+ }
+
+ return nil
+ }
+
+ between, found := AncestorsBetween(childID, parentID, lookup)
+ assert.True(t, found)
+ assert.Equal(t, []int64{childID}, snapshotIDs(between))
+ assert.Equal(t, []int64{childID}, lookedUp, "exclusive base should not
be resolved")
+
+ lookedUp = nil
+ assert.False(t, IsAncestorOf(childID, parentID, lookup))
+ assert.Equal(t, []int64{childID, parentID}, lookedUp, "ancestor must
resolve")
+
+ lookedUp = nil
+ ancestors, complete := AncestorsOfChecked(childID, lookup)
+ assert.False(t, complete)
+ assert.Equal(t, []int64{childID}, snapshotIDs(ancestors))
+ assert.Equal(t, []int64{childID, parentID}, lookedUp)
+
+ lookedUp = nil
+ between, found = AncestorsBetween(parentID, parentID, lookup)
+ assert.True(t, found)
+ assert.Empty(t, between)
+ assert.Empty(t, lookedUp, "equal base and latest must not be resolved")
+
+ assert.False(t, IsAncestorOf(parentID, parentID, lookup))
+ assert.Equal(t, []int64{parentID}, lookedUp, "equal ancestor and
snapshot must resolve")
+}
