1use super::*;
5use crate::json::{self, Value};
6use std::cell::RefCell;
7use std::cmp::Ordering;
8use std::collections::{HashMap, HashSet, VecDeque};
9use std::rc::Rc;
10
11pub fn generate_with_overlay(
15 stream: NodeStream,
16 overlay: Change,
17 schema: Rc<SourceSchema>,
18) -> NodeStream {
19 Box::new(OrderedOverlay {
20 stream,
21 overlay,
22 schema,
23 applied: false,
24 edit_old_applied: false,
25 edit_new_applied: false,
26 queue: VecDeque::new(),
27 finished: false,
28 })
29}
30
31struct OrderedOverlay {
32 stream: NodeStream,
33 overlay: Change,
34 schema: Rc<SourceSchema>,
35 applied: bool,
36 edit_old_applied: bool,
37 edit_new_applied: bool,
38 queue: VecDeque<Node>,
39 finished: bool,
40}
41
42impl Iterator for OrderedOverlay {
43 type Item = Node;
44
45 fn next(&mut self) -> Option<Node> {
46 let compare = self.schema.compare_rows.clone();
47 loop {
48 if let Some(n) = self.queue.pop_front() {
49 return Some(n);
50 }
51 if self.finished {
52 return None;
53 }
54 let Some(node) = self.stream.next() else {
55 self.finished = true;
56 if !self.applied {
57 match &self.overlay {
58 Change::Remove(n) => {
59 self.applied = true;
60 return Some(n.clone());
61 }
62 Change::Edit { old_node, .. } => {
63 assert!(
64 self.edit_new_applied,
65 "edit overlay: new node must be applied before old node"
66 );
67 self.edit_old_applied = true;
68 self.applied = true;
69 return Some(old_node.clone());
70 }
71 _ => {}
72 }
73 }
74 assert!(
75 self.applied,
76 "overlayGenerator: overlay was never applied to any fetched node"
77 );
78 return None;
79 };
80 let mut yield_node = true;
81 if !self.applied {
82 match &self.overlay {
83 Change::Add(n) => {
84 if compare(&n.row, &node.row) == Ordering::Equal {
85 self.applied = true;
86 yield_node = false;
87 }
88 }
89 Change::Remove(n) => {
90 if compare(&n.row, &node.row) == Ordering::Less {
91 self.applied = true;
92 self.queue.push_back(n.clone());
93 }
94 }
95 Change::Edit { node: n, old_node } => {
96 if !self.edit_old_applied
97 && compare(&old_node.row, &node.row) == Ordering::Less
98 {
99 self.edit_old_applied = true;
100 if self.edit_new_applied {
101 self.applied = true;
102 }
103 self.queue.push_back(old_node.clone());
104 }
105 if !self.edit_new_applied && compare(&n.row, &node.row) == Ordering::Equal {
106 self.edit_new_applied = true;
107 if self.edit_old_applied {
108 self.applied = true;
109 }
110 yield_node = false;
111 }
112 }
113 Change::Child(n, child) => {
114 if compare(&n.row, &node.row) == Ordering::Equal {
115 self.applied = true;
116 self.queue
117 .push_back(overlay_child(&node, child, &self.schema));
118 yield_node = false;
119 }
120 }
121 }
122 }
123 if yield_node {
124 self.queue.push_back(node);
125 }
126 }
127 }
128}
129
130fn overlay_child(node: &Node, child: &ChildChange, schema: &SourceSchema) -> Node {
132 let name = child.relationship_name.as_str();
133 let original = node
134 .relationships
135 .get(name)
136 .expect("overlay: relationship on node")
137 .clone();
138 let child_schema = schema
139 .relationship(name)
140 .expect("overlay: relationship in schema")
141 .clone();
142 let change = child.change.clone();
143 node.clone().with(
144 name,
145 Rc::new(move || generate_with_overlay(original(), change.clone(), child_schema.clone())),
146 )
147}
148
149pub fn generate_with_overlay_unordered(
152 stream: NodeStream,
153 overlay: Change,
154 schema: Rc<SourceSchema>,
155) -> NodeStream {
156 Box::new(UnorderedOverlay {
157 stream,
158 overlay,
159 schema,
160 injected: false,
161 suppressed: false,
162 })
163}
164
165struct UnorderedOverlay {
166 stream: NodeStream,
167 overlay: Change,
168 schema: Rc<SourceSchema>,
169 injected: bool,
170 suppressed: bool,
171}
172
173impl Iterator for UnorderedOverlay {
174 type Item = Node;
175
176 fn next(&mut self) -> Option<Node> {
177 if !self.injected {
178 self.injected = true;
179 match &self.overlay {
180 Change::Remove(n) => return Some(n.clone()),
181 Change::Edit { old_node, .. } => return Some(old_node.clone()),
182 _ => {}
183 }
184 }
185 let pk = &self.schema.primary_key;
186 for node in self.stream.by_ref() {
187 if !self.suppressed {
188 match &self.overlay {
189 Change::Add(n) | Change::Edit { node: n, .. } => {
190 if row_equals_for_compound_key(&n.row, &node.row, pk) {
191 self.suppressed = true;
192 continue;
193 }
194 }
195 Change::Child(n, child) => {
196 if row_equals_for_compound_key(&n.row, &node.row, pk) {
197 self.suppressed = true;
198 return Some(overlay_child(&node, child, &self.schema));
199 }
200 }
201 Change::Remove(_) => {}
202 }
203 }
204 return Some(node);
205 }
206 assert!(
207 self.suppressed || self.overlay.change_type() == ChangeType::Remove,
208 "overlayGenerator: overlay was never applied to any fetched node"
209 );
210 None
211 }
212}
213
214pub fn row_equals_for_compound_key(a: &Row, b: &Row, key: &[String]) -> bool {
215 key.iter()
216 .all(|k| compare_values(a.get(k), b.get(k)) == Ordering::Equal)
217}
218
219pub fn is_join_match(
220 parent: &Row,
221 parent_key: &[String],
222 child: &Row,
223 child_key: &[String],
224) -> bool {
225 parent_key
226 .iter()
227 .zip(child_key)
228 .all(|(p, c)| values_equal(parent.get(p), child.get(c)))
229}
230
231pub fn build_join_constraint(
234 source_row: &Row,
235 source_key: &[String],
236 target_key: &[String],
237) -> Option<Constraint> {
238 let mut c = Constraint::default();
239 for (s, t) in source_key.iter().zip(target_key) {
240 let value = source_row.get(s);
241 if matches!(value, Some(Value::Null)) {
242 return None;
243 }
244 c.set(t, value.cloned());
245 }
246 Some(c)
247}
248
249pub fn canonical_key(row: &Row, keys: &[String]) -> String {
252 canonical_key_with(keys, |k| row.get(k))
253}
254
255pub fn canonical_key_of_constraint(constraint: &Constraint, keys: &[String]) -> String {
257 canonical_key_with(keys, |k| constraint.get(k))
258}
259
260fn canonical_key_with<'a>(keys: &[String], get: impl Fn(&str) -> Option<&'a Value>) -> String {
261 let mut s = String::new();
262 for (i, k) in keys.iter().enumerate() {
263 if i > 0 {
264 s.push('\0');
265 }
266 match get(k) {
267 None | Some(Value::Null) => s.push('n'),
268 Some(Value::String(v)) => {
269 s.push('s');
270 s.push_str(v);
271 }
272 Some(Value::Number(n)) => {
273 s.push('d');
274 s.push_str(&json::number::format(*n));
275 }
276 Some(Value::Bool(b)) => s.push(if *b { 't' } else { 'f' }),
277 Some(v) => {
278 s.push('j');
279 s.push_str(&json::stringify(v));
280 }
281 }
282 }
283 s
284}
285
286pub type ParentPartitions = Vec<Option<Constraint>>;
289
290struct Partition {
291 constraint: Constraint,
292 pks: HashSet<String>,
293}
294
295#[derive(Default)]
296struct JoinIndexState {
297 unpartitioned: HashMap<String, HashSet<String>>,
298 partitioned: HashMap<String, (Vec<String>, HashMap<String, Partition>)>,
300 size: usize,
301}
302
303pub struct JoinIndex {
307 parent_key: Vec<String>,
308 primary_key: Vec<String>,
309 join_key_is_pk: bool,
310 partition_key: Option<Vec<String>>,
311 state: RefCell<JoinIndexState>,
312}
313
314impl JoinIndex {
315 pub fn new(
316 parent_key: Vec<String>,
317 primary_key: Vec<String>,
318 partition_key: Option<Vec<String>>,
319 ) -> Rc<Self> {
320 Rc::new(JoinIndex {
321 join_key_is_pk: parent_key == primary_key,
322 parent_key,
323 primary_key,
324 partition_key,
325 state: RefCell::default(),
326 })
327 }
328
329 pub fn size(&self) -> usize {
331 self.state.borrow().size
332 }
333
334 fn pk_of(&self, row: &Row, join_key: &str) -> String {
335 if self.join_key_is_pk {
336 join_key.to_owned()
337 } else {
338 canonical_key(row, &self.primary_key)
339 }
340 }
341
342 pub fn add(&self, row: &Row) {
343 let Some(join_key) = join_key_of(row, &self.parent_key) else {
344 return;
345 };
346 let pk = self.pk_of(row, &join_key);
347 let mut state = self.state.borrow_mut();
348 let state = &mut *state;
349 let Some(partition_key) = &self.partition_key else {
350 if state.unpartitioned.entry(join_key).or_default().insert(pk) {
351 state.size += 1;
352 }
353 return;
354 };
355 let part_key = canonical_key(row, partition_key);
356 let (order, partitions) = state.partitioned.entry(join_key).or_default();
357 let partition = partitions.entry(part_key.clone()).or_insert_with(|| {
358 order.push(part_key);
359 Partition {
360 constraint: Constraint::from_row(row, partition_key),
361 pks: HashSet::new(),
362 }
363 });
364 if partition.pks.insert(pk) {
365 state.size += 1;
366 }
367 }
368
369 pub fn remove(&self, row: &Row) {
370 let Some(join_key) = join_key_of(row, &self.parent_key) else {
371 return;
372 };
373 let pk = self.pk_of(row, &join_key);
374 let mut state = self.state.borrow_mut();
375 let state = &mut *state;
376 let Some(partition_key) = &self.partition_key else {
377 if let Some(pks) = state.unpartitioned.get_mut(&join_key)
378 && pks.remove(&pk)
379 {
380 state.size -= 1;
381 if pks.is_empty() {
382 state.unpartitioned.remove(&join_key);
383 }
384 }
385 return;
386 };
387 let Some((order, partitions)) = state.partitioned.get_mut(&join_key) else {
388 return;
389 };
390 let part_key = canonical_key(row, partition_key);
391 let Some(partition) = partitions.get_mut(&part_key) else {
392 return;
393 };
394 if partition.pks.remove(&pk) {
395 state.size -= 1;
396 if partition.pks.is_empty() {
397 partitions.remove(&part_key);
398 order.retain(|k| *k != part_key);
399 if partitions.is_empty() {
400 state.partitioned.remove(&join_key);
401 }
402 }
403 }
404 }
405
406 pub fn lookup(&self, child_row: &Row, child_key: &[String]) -> Option<ParentPartitions> {
409 let join_key = join_key_of(child_row, child_key)?;
410 let state = self.state.borrow();
411 if self.partition_key.is_none() {
412 return state
413 .unpartitioned
414 .contains_key(&join_key)
415 .then(|| vec![None]);
416 }
417 let (order, partitions) = state.partitioned.get(&join_key)?;
418 Some(
419 order
420 .iter()
421 .map(|k| Some(partitions[k].constraint.clone()))
422 .collect(),
423 )
424 }
425}
426
427fn join_key_of(row: &Row, key: &[String]) -> Option<String> {
429 if key.iter().any(|k| matches!(row.get(k), Some(Value::Null))) {
430 return None;
431 }
432 Some(canonical_key(row, key))
433}