uqa_execution/mutation/rules/
columns.rs1use std::collections::BTreeSet;
10
11use uqa_core::{CancellationToken, Value};
12use uqa_sql::SQLError;
13
14use crate::mutation::prepared::{decode_prepared_doc_id, encode_prepared_doc_id};
15use crate::physical::physical_exec_error;
16use crate::spill::{SharedSpill, SharedSpillReader, SpillBatchWriter, SpillBuffer, SpillRows};
17use crate::{PhysicalRow, RowSchema};
18
19mod selection;
20
21type Columns<const N: usize> = [BTreeSet<String>; N];
22
23pub struct RuleColumnSets<const N: usize> {
25 storage: Storage<N>,
26 count: usize,
27 any: bool,
28 cancellation: CancellationToken,
29}
30
31enum Storage<const N: usize> {
32 Uniform(Columns<N>),
33 Spill(SharedSpill),
34}
35
36impl<const N: usize> RuleColumnSets<N> {
37 pub(super) fn from_rows(
38 input: impl IntoIterator<Item = Result<Columns<N>, SQLError>>,
39 bytes: usize,
40 cancellation: CancellationToken,
41 ) -> Result<Self, SQLError> {
42 let mut rows = SpillBuffer::new(bytes);
43 let mut writer = SpillBatchWriter::new(schema::<N>()).map_err(physical_exec_error)?;
44 let mut pending = None::<(usize, Columns<N>)>;
45 let mut count = 0_usize;
46 let mut any = false;
47 let mut flushed = false;
48 for columns in input {
49 cancellation.check()?;
50 let columns = columns?;
51 count = count
52 .checked_add(1)
53 .ok_or_else(|| invalid("row count overflow"))?;
54 any |= columns.iter().any(|columns| !columns.is_empty());
55 if let Some((length, previous)) = &mut pending {
56 if *previous == columns {
57 *length += 1;
58 continue;
59 }
60 }
61 if let Some(run) = pending.take() {
62 writer
63 .push(&mut rows, encode(run))
64 .map_err(physical_exec_error)?;
65 flushed = true;
66 }
67 pending = Some((1, columns));
68 }
69 cancellation.check()?;
70 let storage = if flushed {
71 if let Some(run) = pending {
72 writer
73 .push(&mut rows, encode(run))
74 .map_err(physical_exec_error)?;
75 }
76 writer.finish(&mut rows).map_err(physical_exec_error)?;
77 Storage::Spill(
78 rows.into_shared(schema::<N>())
79 .map_err(physical_exec_error)?,
80 )
81 } else {
82 Storage::Uniform(pending.map_or_else(empty, |(_, columns)| columns))
83 };
84 Ok(Self {
85 storage,
86 count,
87 any,
88 cancellation,
89 })
90 }
91
92 pub fn has_required_columns(&self) -> bool {
93 self.any
94 }
95
96 pub fn reader(&self) -> Result<RuleColumnIter<N>, SQLError> {
97 self.cancellation.check()?;
98 let (pending, rows) = match &self.storage {
99 Storage::Uniform(columns) => ((self.count, columns.clone()), None),
100 Storage::Spill(rows) => (
101 (0, empty()),
102 Some(Box::new(rows.read_rows().map_err(physical_exec_error)?)),
103 ),
104 };
105 Ok(RuleColumnIter {
106 pending,
107 rows,
108 remaining: self.count,
109 cancellation: self.cancellation.clone(),
110 finished: false,
111 })
112 }
113}
114
115pub struct RuleColumnIter<const N: usize> {
117 pending: (usize, Columns<N>),
118 rows: Option<Box<SpillRows<SharedSpillReader>>>,
119 remaining: usize,
120 cancellation: CancellationToken,
121 finished: bool,
122}
123
124impl<const N: usize> RuleColumnIter<N> {
125 fn read_next(&mut self) -> Result<Option<Columns<N>>, SQLError> {
126 self.cancellation.check()?;
127 if self.pending.0 == 0 {
128 if let Some(row) = self.rows.as_mut().and_then(Iterator::next) {
129 self.pending = decode(row.map_err(physical_exec_error)?.row)?;
130 if self.pending.0 > self.remaining {
131 return Err(invalid("run exceeds the declared row count"));
132 }
133 }
134 }
135 if self.pending.0 == 0 {
136 return if self.remaining == 0 {
137 Ok(None)
138 } else {
139 Err(invalid("missing required-column rows"))
140 };
141 }
142 self.remaining = self
143 .remaining
144 .checked_sub(1)
145 .ok_or_else(|| invalid("more rows than declared"))?;
146 self.pending.0 -= 1;
147 Ok(Some(self.pending.1.clone()))
148 }
149}
150
151impl<const N: usize> Iterator for RuleColumnIter<N> {
152 type Item = Result<Columns<N>, SQLError>;
153
154 fn next(&mut self) -> Option<Self::Item> {
155 if self.finished {
156 return None;
157 }
158 match self.read_next() {
159 Ok(Some(columns)) => Some(Ok(columns)),
160 Ok(None) => {
161 self.finished = true;
162 None
163 }
164 Err(error) => {
165 self.finished = true;
166 Some(Err(error))
167 }
168 }
169 }
170}
171
172fn empty<const N: usize>() -> Columns<N> {
173 std::array::from_fn(|_| BTreeSet::new())
174}
175
176fn schema<const N: usize>() -> RowSchema {
177 RowSchema::new(
178 std::iter::once("count".into())
179 .chain((0..N).map(|side| format!("columns_{side}")))
180 .collect(),
181 )
182}
183
184fn encode<const N: usize>((count, columns): (usize, Columns<N>)) -> PhysicalRow {
185 PhysicalRow::from_values(
186 std::iter::once(encode_prepared_doc_id(count as u64))
187 .chain(
188 columns
189 .into_iter()
190 .map(|columns| Value::List(columns.into_iter().map(Value::Str).collect())),
191 )
192 .collect(),
193 )
194}
195
196fn decode<const N: usize>(row: PhysicalRow) -> Result<(usize, Columns<N>), SQLError> {
197 let mut values = row.into_physical_values().into_iter();
198 let count = usize::try_from(decode_prepared_doc_id(
199 values.next().ok_or_else(|| invalid("missing run length"))?,
200 "rewrite-rule required columns",
201 )?)
202 .map_err(|_| invalid("run exceeds the addressable row count"))?;
203 if count == 0 {
204 return Err(invalid("empty run"));
205 }
206 let mut output = empty();
207 for columns in &mut output {
208 let Some(Value::List(names)) = values.next() else {
209 return Err(invalid("invalid column set"));
210 };
211 for name in names {
212 let Value::Str(name) = name else {
213 return Err(invalid("column name is not text"));
214 };
215 if !columns.insert(name) {
216 return Err(invalid("duplicate column name"));
217 }
218 }
219 }
220 if values.next().is_some() {
221 return Err(invalid("invalid record width"));
222 }
223 Ok((count, output))
224}
225
226fn invalid(message: &str) -> SQLError {
227 SQLError::Internal(format!("rewrite-rule required columns: {message}"))
228}
229
230#[cfg(test)]
231mod tests;