1use crate::storage::page::TupleMeta;
2use crate::transaction::{CommandId, TransactionId, INVALID_COMMAND_ID};
3
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub enum TransactionStatus {
6 InProgress,
7 Committed,
8 Aborted,
9 Unknown,
10}
11
12impl TransactionStatus {
13 fn is_committed(self) -> bool {
14 matches!(self, TransactionStatus::Committed)
15 }
16
17 fn is_aborted(self) -> bool {
18 matches!(self, TransactionStatus::Aborted)
19 }
20}
21
22#[derive(Debug, Clone)]
23pub struct TransactionSnapshot {
24 txn_id: TransactionId,
25 xmin: TransactionId,
26 xmax: TransactionId,
27 active_txns: Vec<TransactionId>,
28}
29
30impl TransactionSnapshot {
31 pub fn new(
32 txn_id: TransactionId,
33 xmin: TransactionId,
34 xmax: TransactionId,
35 mut active_txns: Vec<TransactionId>,
36 ) -> Self {
37 active_txns.sort_unstable();
38 Self {
39 txn_id,
40 xmin,
41 xmax,
42 active_txns,
43 }
44 }
45
46 pub fn txn_id(&self) -> TransactionId {
47 self.txn_id
48 }
49
50 pub fn xmin(&self) -> TransactionId {
51 self.xmin
52 }
53
54 pub fn xmax(&self) -> TransactionId {
55 self.xmax
56 }
57
58 pub fn active_txns(&self) -> &[TransactionId] {
59 &self.active_txns
60 }
61
62 fn active_contains(&self, txn_id: TransactionId) -> bool {
63 self.active_txns.binary_search(&txn_id).is_ok()
64 }
65
66 pub fn is_visible<F>(&self, meta: &TupleMeta, command_id: CommandId, mut status_of: F) -> bool
67 where
68 F: FnMut(TransactionId) -> TransactionStatus,
69 {
70 let inserter = meta.insert_txn_id;
71 if inserter == 0 {
72 return self.other_txn_delete_invisible(meta, command_id, &mut status_of);
73 }
74
75 if inserter == self.txn_id {
76 if meta.insert_cid > command_id {
77 return false;
78 }
79 return self.visible_after_local_delete(meta, command_id, &mut status_of);
80 }
81
82 if !self.other_txn_insert_visible(inserter, &mut status_of) {
83 return false;
84 }
85
86 if !meta.is_deleted {
87 return true;
88 }
89
90 self.other_txn_delete_invisible(meta, command_id, &mut status_of)
91 }
92
93 fn visible_after_local_delete<F>(
94 &self,
95 meta: &TupleMeta,
96 command_id: CommandId,
97 status_of: &mut F,
98 ) -> bool
99 where
100 F: FnMut(TransactionId) -> TransactionStatus,
101 {
102 if !meta.is_deleted {
103 return true;
104 }
105 let deleter = meta.delete_txn_id;
106 if deleter == self.txn_id {
107 if meta.delete_cid == INVALID_COMMAND_ID {
108 return true;
109 }
110 return meta.delete_cid > command_id;
111 }
112 self.other_txn_delete_invisible(meta, command_id, status_of)
113 }
114
115 fn other_txn_insert_visible<F>(&self, inserter: TransactionId, status_of: &mut F) -> bool
116 where
117 F: FnMut(TransactionId) -> TransactionStatus,
118 {
119 if inserter >= self.xmax {
120 return false;
121 }
122
123 let status = status_of(inserter);
124 if status.is_aborted() {
125 return false;
126 }
127
128 if inserter < self.xmin {
129 return status.is_committed() || matches!(status, TransactionStatus::Unknown);
130 }
131
132 if self.active_contains(inserter) {
133 return false;
134 }
135
136 matches!(
137 status,
138 TransactionStatus::Committed | TransactionStatus::Unknown
139 )
140 }
141
142 fn other_txn_delete_invisible<F>(
143 &self,
144 meta: &TupleMeta,
145 command_id: CommandId,
146 status_of: &mut F,
147 ) -> bool
148 where
149 F: FnMut(TransactionId) -> TransactionStatus,
150 {
151 if !meta.is_deleted {
152 return true;
153 }
154
155 let deleter = meta.delete_txn_id;
156 if deleter == 0 {
157 return true;
158 }
159
160 if deleter == self.txn_id {
161 if meta.delete_cid == INVALID_COMMAND_ID {
162 return true;
163 }
164 return meta.delete_cid > command_id;
165 }
166
167 if deleter >= self.xmax {
168 return true;
169 }
170
171 let status = status_of(deleter);
172 if deleter < self.xmin {
173 return !status.is_committed();
174 }
175
176 if self.active_contains(deleter) {
177 return true;
178 }
179
180 match status {
181 TransactionStatus::Committed => false,
182 TransactionStatus::Aborted => true,
183 TransactionStatus::InProgress => true,
184 TransactionStatus::Unknown => false,
185 }
186 }
187}
188
189#[cfg(test)]
190mod tests {
191 use super::*;
192 use crate::storage::page::TupleMeta;
193
194 #[test]
195 fn snapshot_filters_uncommitted() {
196 let snapshot = TransactionSnapshot::new(2, 1, 5, vec![1, 3]);
197 let meta = TupleMeta {
198 insert_txn_id: 1,
199 insert_cid: 0,
200 delete_txn_id: 0,
201 delete_cid: INVALID_COMMAND_ID,
202 is_deleted: false,
203 next_version: None,
204 prev_version: None,
205 };
206 assert!(!snapshot.is_visible(&meta, 0, |_| TransactionStatus::InProgress));
207 }
208
209 #[test]
210 fn snapshot_allows_committed_visible() {
211 let snapshot = TransactionSnapshot::new(3, 2, 10, vec![4, 6]);
212 let meta = TupleMeta {
213 insert_txn_id: 1,
214 insert_cid: 0,
215 delete_txn_id: 0,
216 delete_cid: INVALID_COMMAND_ID,
217 is_deleted: false,
218 next_version: None,
219 prev_version: None,
220 };
221 assert!(snapshot.is_visible(&meta, 0, |_| TransactionStatus::Committed));
222 }
223
224 #[test]
225 fn snapshot_hides_committed_delete() {
226 let snapshot = TransactionSnapshot::new(3, 2, 10, vec![4, 6]);
227 let meta = TupleMeta {
228 insert_txn_id: 1,
229 insert_cid: 0,
230 delete_txn_id: 5,
231 delete_cid: 0,
232 is_deleted: true,
233 next_version: None,
234 prev_version: None,
235 };
236 assert!(!snapshot.is_visible(&meta, 0, |txn| {
237 if txn == 5 {
238 TransactionStatus::Committed
239 } else {
240 TransactionStatus::Committed
241 }
242 }));
243 }
244
245 #[test]
246 fn snapshot_retains_tuple_when_delete_aborted() {
247 let snapshot = TransactionSnapshot::new(3, 2, 10, vec![4, 6]);
248 let meta = TupleMeta {
249 insert_txn_id: 1,
250 insert_cid: 0,
251 delete_txn_id: 5,
252 delete_cid: 0,
253 is_deleted: true,
254 next_version: None,
255 prev_version: None,
256 };
257 assert!(snapshot.is_visible(&meta, 0, |txn| {
258 if txn == 5 {
259 TransactionStatus::Aborted
260 } else {
261 TransactionStatus::Committed
262 }
263 }));
264 }
265}