Skip to main content

cozo/runtime/
temp_store.rs

1/*
2 * Copyright 2022, The Cozo Project Authors.
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
5 * If a copy of the MPL was not distributed with this file,
6 * You can obtain one at https://mozilla.org/MPL/2.0/.
7 */
8
9use std::cmp::Ordering;
10use std::collections::btree_map::Entry;
11use std::collections::BTreeMap;
12use std::collections::Bound::Included;
13use std::mem;
14use std::ops::Bound::Excluded;
15
16use either::{Left, Right};
17use itertools::Itertools;
18use miette::Result;
19
20use crate::data::aggr::Aggregation;
21use crate::data::tuple::Tuple;
22use crate::data::value::DataValue;
23
24/// A store holding temp data during evaluation of queries.
25/// The public interface is used in custom implementations of algorithms/utilities.
26#[derive(Default, Debug)]
27pub struct RegularTempStore {
28    inner: BTreeMap<Tuple, bool>,
29}
30
31const EMPTY_TUPLE_REF: &Tuple = &vec![];
32
33impl RegularTempStore {
34    pub(crate) fn wrap(self) -> TempStore {
35        TempStore::Normal(self)
36    }
37    /// Tests if a key already exists in the store.
38    pub fn exists(&self, key: &Tuple) -> bool {
39        self.inner.contains_key(key)
40    }
41
42    fn range_iter<'a>(
43        &'a self,
44        lower: &Tuple,
45        upper: &Tuple,
46        upper_inclusive: bool,
47    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
48        let lower_bound = Included(lower.to_vec());
49        let upper_bound = if upper_inclusive {
50            Included(upper.to_vec())
51        } else {
52            Excluded(upper.to_vec())
53        };
54        self.inner
55            .range((lower_bound, upper_bound))
56            .map(|(t, skip)| TupleInIter(t, EMPTY_TUPLE_REF, *skip))
57    }
58    /// Add a tuple to the store
59    pub fn put(&mut self, tuple: Tuple) {
60        self.inner.insert(tuple, false);
61    }
62    pub(crate) fn put_with_skip(&mut self, tuple: Tuple) {
63        self.inner.insert(tuple, true);
64    }
65    // returns true if prev is guaranteed to be the same as self after this function call,
66    // false if we are not sure.
67    pub(crate) fn merge_in(&mut self, prev: &mut Self, mut new: Self) -> bool {
68        prev.inner.clear();
69        if new.inner.is_empty() {
70            return false;
71        }
72        if self.inner.is_empty() {
73            mem::swap(&mut new, self);
74            return true;
75        }
76        for (k, v) in new.inner {
77            match self.inner.entry(k) {
78                Entry::Vacant(ent) => {
79                    prev.inner.insert(ent.key().clone(), v);
80                    ent.insert(v);
81                }
82                Entry::Occupied(mut ent) => {
83                    ent.insert(v);
84                }
85            }
86        }
87        false
88    }
89}
90
91#[derive(Debug)]
92pub(crate) struct MeetAggrStore {
93    inner: BTreeMap<Tuple, Tuple>,
94    aggregations: Vec<(Aggregation, Vec<DataValue>)>,
95    grouping_len: usize,
96}
97
98impl MeetAggrStore {
99    pub(crate) fn wrap(self) -> TempStore {
100        TempStore::MeetAggr(self)
101    }
102    pub(crate) fn exists(&self, key: &Tuple) -> bool {
103        let truncated = &key[0..self.grouping_len];
104        self.inner.contains_key(truncated)
105    }
106    pub(crate) fn is_empty(&self) -> bool {
107        self.inner.is_empty()
108    }
109    pub(crate) fn new(aggrs: Vec<Option<(Aggregation, Vec<DataValue>)>>) -> Result<Self> {
110        let total_key_len = aggrs.len();
111        let mut aggregations = aggrs.into_iter().flatten().collect_vec();
112        for (aggr, args) in aggregations.iter_mut() {
113            aggr.meet_init(args)?;
114        }
115        let grouping_len = total_key_len - aggregations.len();
116        Ok(Self {
117            inner: Default::default(),
118            aggregations,
119            grouping_len,
120        })
121    }
122    // also need to check if value exists beforehand! use the idempotency!
123    // need to think this through more carefully.
124    pub(crate) fn meet_put(&mut self, tuple: Tuple) -> Result<bool> {
125        let (key_part, val_part) = tuple.split_at(self.grouping_len);
126        match self.inner.get_mut(key_part) {
127            Some(prev_aggr) => {
128                let mut changed = false;
129                for (i, (aggr_op, _)) in self.aggregations.iter().enumerate() {
130                    let op = aggr_op.meet_op.as_ref().unwrap();
131                    changed |= op.update(&mut prev_aggr[i], &val_part[i])?;
132                }
133                Ok(changed)
134            }
135            None => {
136                self.inner.insert(key_part.to_vec(), val_part.to_vec());
137                Ok(true)
138            }
139        }
140    }
141    fn range_iter<'a>(
142        &'a self,
143        lower: &Tuple,
144        upper: &Tuple,
145        upper_inclusive: bool,
146    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
147        let lower_key = if lower.len() > self.grouping_len {
148            lower[0..self.grouping_len].to_vec()
149        } else {
150            lower.to_vec()
151        };
152        let upper_key = if upper.len() > self.grouping_len {
153            upper[0..self.grouping_len].to_vec()
154        } else {
155            upper.to_vec()
156        };
157        let lower = lower.to_vec();
158        let upper = upper.to_vec();
159        self.inner
160            .range(lower_key..=upper_key)
161            .filter_map(move |(k, v)| {
162                let ret = TupleInIter(k, v, false);
163                if ret.partial_cmp(&lower as &[DataValue]) == Some(Ordering::Less) {
164                    None
165                } else {
166                    match ret.partial_cmp(&upper as &[DataValue]).unwrap() {
167                        Ordering::Less => Some(ret),
168                        Ordering::Equal => {
169                            if upper_inclusive {
170                                Some(ret)
171                            } else {
172                                None
173                            }
174                        }
175                        Ordering::Greater => None,
176                    }
177                }
178            })
179    }
180    /// returns true if prev is guaranteed to be the same as self after this function call,
181    /// false if we are not sure.
182    pub(crate) fn merge_in(&mut self, prev: &mut Self, mut new: Self) -> Result<bool> {
183        prev.inner.clear();
184        if new.inner.is_empty() {
185            return Ok(false);
186        }
187        if self.inner.is_empty() {
188            mem::swap(self, &mut new);
189            return Ok(true);
190        }
191        for (k, v) in new.inner {
192            match self.inner.entry(k) {
193                Entry::Vacant(ent) => {
194                    prev.inner.insert(ent.key().clone(), v.clone());
195                    ent.insert(v);
196                }
197                Entry::Occupied(mut ent) => {
198                    let mut changed = false;
199                    {
200                        let target = ent.get_mut();
201                        for (i, (aggr_op, _)) in self.aggregations.iter().enumerate() {
202                            let op = aggr_op.meet_op.as_ref().unwrap();
203                            changed |= op.update(&mut target[i], &v[i])?;
204                        }
205                    }
206                    if changed {
207                        prev.inner.insert(ent.key().clone(), ent.get().clone());
208                    }
209                }
210            }
211        }
212        Ok(false)
213    }
214}
215
216#[derive(Debug)]
217pub(crate) enum TempStore {
218    Normal(RegularTempStore),
219    MeetAggr(MeetAggrStore),
220}
221
222impl TempStore {
223    fn exists(&self, key: &Tuple) -> bool {
224        match self {
225            TempStore::Normal(n) => n.exists(key),
226            TempStore::MeetAggr(m) => m.exists(key),
227        }
228    }
229    fn range_iter<'a>(
230        &'a self,
231        lower: &Tuple,
232        upper: &Tuple,
233        upper_inclusive: bool,
234    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
235        match self {
236            TempStore::Normal(n) => Left(n.range_iter(lower, upper, upper_inclusive)),
237            TempStore::MeetAggr(m) => Right(m.range_iter(lower, upper, upper_inclusive)),
238        }
239    }
240    fn is_empty(&self) -> bool {
241        match self {
242            TempStore::Normal(n) => n.inner.is_empty(),
243            TempStore::MeetAggr(m) => m.inner.is_empty(),
244        }
245    }
246}
247
248#[derive(Debug)]
249pub(crate) struct EpochStore {
250    total: TempStore,
251    delta: TempStore,
252    use_total_for_delta: bool,
253    pub(crate) arity: usize,
254}
255
256impl EpochStore {
257    pub(crate) fn exists(&self, key: &Tuple) -> bool {
258        self.total.exists(key)
259    }
260    pub(crate) fn new_normal(arity: usize) -> Self {
261        Self {
262            total: TempStore::Normal(RegularTempStore::default()),
263            delta: TempStore::Normal(RegularTempStore::default()),
264            use_total_for_delta: true,
265            arity,
266        }
267    }
268    pub(crate) fn new_meet(aggrs: &[Option<(Aggregation, Vec<DataValue>)>]) -> Result<Self> {
269        Ok(Self {
270            total: TempStore::MeetAggr(MeetAggrStore::new(aggrs.to_vec())?),
271            delta: TempStore::MeetAggr(MeetAggrStore::new(aggrs.to_vec())?),
272            use_total_for_delta: true,
273            arity: aggrs.len(),
274        })
275    }
276    pub(crate) fn merge_in(&mut self, new: TempStore) -> Result<()> {
277        match (&mut self.total, &mut self.delta, new) {
278            (TempStore::Normal(total), TempStore::Normal(prev), TempStore::Normal(new)) => {
279                self.use_total_for_delta = total.merge_in(prev, new);
280            }
281            (TempStore::MeetAggr(total), TempStore::MeetAggr(prev), TempStore::MeetAggr(new)) => {
282                self.use_total_for_delta = total.merge_in(prev, new)?;
283            }
284            _ => unreachable!(),
285        }
286        Ok(())
287    }
288    pub(crate) fn has_delta(&self) -> bool {
289        if self.use_total_for_delta {
290            !self.total.is_empty()
291        } else {
292            !self.delta.is_empty()
293        }
294    }
295    pub(crate) fn range_iter<'a>(
296        &'a self,
297        lower: &Tuple,
298        upper: &Tuple,
299        upper_inclusive: bool,
300    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
301        self.total.range_iter(lower, upper, upper_inclusive)
302    }
303    pub(crate) fn delta_range_iter<'a>(
304        &'a self,
305        lower: &Tuple,
306        upper: &Tuple,
307        upper_inclusive: bool,
308    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
309        if self.use_total_for_delta {
310            self.total.range_iter(lower, upper, upper_inclusive)
311        } else {
312            self.delta.range_iter(lower, upper, upper_inclusive)
313        }
314    }
315    pub(crate) fn prefix_iter<'a>(&'a self, prefix: &Tuple) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
316        let mut upper = prefix.to_vec();
317        upper.push(DataValue::Bot);
318        self.range_iter(prefix, &upper, true)
319    }
320    pub(crate) fn delta_prefix_iter<'a>(
321        &'a self,
322        prefix: &Tuple,
323    ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
324        let mut upper = prefix.to_vec();
325        upper.push(DataValue::Bot);
326        self.delta_range_iter(prefix, &upper, true)
327    }
328    pub(crate) fn all_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
329        self.prefix_iter(&vec![])
330    }
331    pub(crate) fn delta_all_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
332        self.delta_prefix_iter(&vec![])
333    }
334    pub(crate) fn early_returned_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
335        self.all_iter().filter(|t| !t.should_skip())
336    }
337}
338
339#[derive(Copy, Clone)]
340pub(crate) struct TupleInIter<'a>(&'a Tuple, &'a Tuple, bool);
341
342impl<'a> TupleInIter<'a> {
343    pub(crate) fn get(self, idx: usize) -> &'a DataValue {
344        self.0
345            .get(idx)
346            .unwrap_or_else(|| self.1.get(idx - self.0.len()).unwrap())
347    }
348    fn should_skip(&self) -> bool {
349        self.2
350    }
351    pub(crate) fn into_tuple(self) -> Tuple {
352        self.into_iter().cloned().collect_vec()
353    }
354}
355
356impl<'a> IntoIterator for TupleInIter<'a> {
357    type Item = &'a DataValue;
358    type IntoIter = TupleInIterIterator<'a>;
359
360    fn into_iter(self) -> Self::IntoIter {
361        TupleInIterIterator {
362            inner: self,
363            idx: 0,
364        }
365    }
366}
367
368pub(crate) struct TupleInIterIterator<'a> {
369    inner: TupleInIter<'a>,
370    idx: usize,
371}
372
373impl PartialEq for TupleInIter<'_> {
374    fn eq(&self, other: &Self) -> bool {
375        self.into_iter().eq(other.into_iter())
376    }
377}
378
379impl Eq for TupleInIter<'_> {}
380
381impl Ord for TupleInIter<'_> {
382    fn cmp(&self, other: &Self) -> Ordering {
383        self.into_iter().cmp(other.into_iter())
384    }
385}
386
387impl PartialOrd for TupleInIter<'_> {
388    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
389        Some(self.cmp(other))
390    }
391}
392
393impl PartialEq<[DataValue]> for TupleInIter<'_> {
394    fn eq(&self, other: &'_ [DataValue]) -> bool {
395        self.into_iter().eq(other.iter())
396    }
397}
398
399impl PartialOrd<[DataValue]> for TupleInIter<'_> {
400    fn partial_cmp(&self, other: &'_ [DataValue]) -> Option<Ordering> {
401        self.into_iter().partial_cmp(other.iter())
402    }
403}
404
405impl<'a> Iterator for TupleInIterIterator<'a> {
406    type Item = &'a DataValue;
407
408    fn next(&mut self) -> Option<Self::Item> {
409        let ret = match self.inner.0.get(self.idx) {
410            Some(d) => d,
411            None => match self.inner.1.get(self.idx - self.inner.0.len()) {
412                None => return None,
413                Some(d) => d,
414            },
415        };
416        self.idx += 1;
417        Some(ret)
418    }
419}