iceberg/util/
snapshot.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use crate::spec::{SnapshotRef, TableMetadataRef};
19
20struct Ancestors {
21    next: Option<SnapshotRef>,
22    get_snapshot: Box<dyn Fn(i64) -> Option<SnapshotRef> + Send>,
23}
24
25impl Iterator for Ancestors {
26    type Item = SnapshotRef;
27
28    fn next(&mut self) -> Option<Self::Item> {
29        let snapshot = self.next.take()?;
30        self.next = snapshot
31            .parent_snapshot_id()
32            .and_then(|id| (self.get_snapshot)(id));
33        Some(snapshot)
34    }
35}
36
37/// Iterate starting from `snapshot_id` (inclusive) to the root snapshot.
38pub fn ancestors_of(
39    table_metadata: &TableMetadataRef,
40    snapshot_id: i64,
41) -> impl Iterator<Item = SnapshotRef> + Send {
42    let initial = table_metadata.snapshot_by_id(snapshot_id).cloned();
43    let table_metadata = table_metadata.clone();
44    Ancestors {
45        next: initial,
46        get_snapshot: Box::new(move |id| table_metadata.snapshot_by_id(id).cloned()),
47    }
48}
49
50/// Iterate starting from `latest_snapshot_id` (inclusive) to `oldest_snapshot_id` (exclusive).
51///
52/// Note: if `oldest_snapshot_id` is `Some(id)` but `id` is not actually an
53/// ancestor of `latest_snapshot_id`, the walk is never stopped and this yields
54/// *all* ancestors of `latest_snapshot_id` down to the root. Callers that treat
55/// `oldest_snapshot_id` as a lower bound must validate the lineage themselves.
56pub fn ancestors_between(
57    table_metadata: &TableMetadataRef,
58    latest_snapshot_id: i64,
59    oldest_snapshot_id: Option<i64>,
60) -> impl Iterator<Item = SnapshotRef> + Send {
61    ancestors_of(table_metadata, latest_snapshot_id).take_while(move |snapshot| {
62        oldest_snapshot_id
63            .map(|id| snapshot.snapshot_id() != id)
64            .unwrap_or(true)
65    })
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use crate::scan::tests::TableTestFixture;
72
73    // Five snapshots chained as: S1 (root) -> S2 -> S3 -> S4 -> S5 (current)
74    const S1: i64 = 3051729675574597004;
75    const S2: i64 = 3055729675574597004;
76    const S3: i64 = 3056729675574597004;
77    const S4: i64 = 3057729675574597004;
78    const S5: i64 = 3059729675574597004;
79
80    fn metadata() -> TableMetadataRef {
81        let fixture = TableTestFixture::new_with_deep_history();
82        std::sync::Arc::new(fixture.table.metadata().clone())
83    }
84
85    // --- ancestors_of ---
86
87    #[test]
88    fn test_ancestors_of_nonexistent_snapshot_returns_empty() {
89        let meta = metadata();
90        let ids: Vec<i64> = ancestors_of(&meta, 999).map(|s| s.snapshot_id()).collect();
91        assert!(ids.is_empty());
92    }
93
94    #[test]
95    fn test_ancestors_of_root_returns_only_root() {
96        let meta = metadata();
97        let ids: Vec<i64> = ancestors_of(&meta, S1).map(|s| s.snapshot_id()).collect();
98        assert_eq!(ids, vec![S1]);
99    }
100
101    #[test]
102    fn test_ancestors_of_leaf_returns_full_chain() {
103        let meta = metadata();
104        let ids: Vec<i64> = ancestors_of(&meta, S5).map(|s| s.snapshot_id()).collect();
105        assert_eq!(ids, vec![S5, S4, S3, S2, S1]);
106    }
107
108    #[test]
109    fn test_ancestors_of_mid_chain_returns_partial_chain() {
110        let meta = metadata();
111        let ids: Vec<i64> = ancestors_of(&meta, S3).map(|s| s.snapshot_id()).collect();
112        assert_eq!(ids, vec![S3, S2, S1]);
113    }
114
115    #[test]
116    fn test_ancestors_of_second_snapshot() {
117        let meta = metadata();
118        let ids: Vec<i64> = ancestors_of(&meta, S2).map(|s| s.snapshot_id()).collect();
119        assert_eq!(ids, vec![S2, S1]);
120    }
121
122    // --- ancestors_between ---
123
124    #[test]
125    fn test_ancestors_between_same_id_returns_empty() {
126        let meta = metadata();
127        let ids: Vec<i64> = ancestors_between(&meta, S3, Some(S3))
128            .map(|s| s.snapshot_id())
129            .collect();
130        assert!(ids.is_empty());
131    }
132
133    #[test]
134    fn test_ancestors_between_no_oldest_returns_all_ancestors() {
135        let meta = metadata();
136        let ids: Vec<i64> = ancestors_between(&meta, S5, None)
137            .map(|s| s.snapshot_id())
138            .collect();
139        assert_eq!(ids, vec![S5, S4, S3, S2, S1]);
140    }
141
142    #[test]
143    fn test_ancestors_between_excludes_oldest_snapshot() {
144        let meta = metadata();
145        // S5 down to (but not including) S2
146        let ids: Vec<i64> = ancestors_between(&meta, S5, Some(S2))
147            .map(|s| s.snapshot_id())
148            .collect();
149        assert_eq!(ids, vec![S5, S4, S3]);
150    }
151
152    #[test]
153    fn test_ancestors_between_adjacent_snapshots() {
154        let meta = metadata();
155        // S3 down to (but not including) S2 — only S3 itself
156        let ids: Vec<i64> = ancestors_between(&meta, S3, Some(S2))
157            .map(|s| s.snapshot_id())
158            .collect();
159        assert_eq!(ids, vec![S3]);
160    }
161
162    #[test]
163    fn test_ancestors_between_leaf_and_root() {
164        let meta = metadata();
165        // S5 down to (but not including) S1
166        let ids: Vec<i64> = ancestors_between(&meta, S5, Some(S1))
167            .map(|s| s.snapshot_id())
168            .collect();
169        assert_eq!(ids, vec![S5, S4, S3, S2]);
170    }
171
172    #[test]
173    fn test_ancestors_between_nonexistent_oldest_returns_full_chain() {
174        let meta = metadata();
175        // oldest_snapshot_id doesn't exist in the chain, so take_while never stops
176        let ids: Vec<i64> = ancestors_between(&meta, S5, Some(999))
177            .map(|s| s.snapshot_id())
178            .collect();
179        assert_eq!(ids, vec![S5, S4, S3, S2, S1]);
180    }
181
182    #[test]
183    fn test_ancestors_between_nonexistent_latest_returns_empty() {
184        let meta = metadata();
185        let ids: Vec<i64> = ancestors_between(&meta, 999, Some(S1))
186            .map(|s| s.snapshot_id())
187            .collect();
188        assert!(ids.is_empty());
189    }
190}
iceberg/util/snapshot.rs

iceberg/util/
snapshot.rs
