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