asdi/idb/query/
mod.rs

1/*!
2This module provides the [Query] type that represents a query goal as well as the [View] and [Row].
3types used to return query results.
4
5![module UML](https://raw.githubusercontent.com/johnstonskj/rust-asdi/main/book/src/model/idb_query.svg)
6
7 */
8
9use self::relational::{FactOps, Projection, RelationOps, Selection};
10use crate::edb::{Attribute, AttributeIndex, AttributeKind, Constant, Fact, Schema};
11use crate::error::Result;
12use crate::idb::{Atom, Term, Variable};
13use crate::syntax::{CHAR_PERIOD, QUERY_ASCII_PREFIX};
14use crate::{Collection, IndexedCollection, PredicateRef};
15use std::collections::HashSet;
16use std::fmt::{Debug, Display, Formatter};
17use std::hash::Hash;
18use tracing::{error, trace};
19
20// ------------------------------------------------------------------------------------------------
21// Public Types & Constants
22// ------------------------------------------------------------------------------------------------
23
24///
25/// A query, or goal, is an atom to be matched against [relations](../edb/struct.Relation.html)
26/// known to the program.
27///
28/// # Examples
29///
30/// ```datalog
31/// .assert car(make: string, model: string, year: integer).
32///
33/// ## Is there a car model Fiesta, from Ford, with a model year 2010?
34/// car(ford, focus, 2010)?
35///
36/// ## Return all the models Ford made with a model year 2010.
37/// car(ford, X, 2010)?
38///
39/// ## Return all the model years for Ford Fiesta.
40/// car(ford, focus, X)?
41/// ```
42///
43#[derive(Clone, Debug, PartialEq, Eq, Hash)]
44pub struct Query(Atom);
45
46#[derive(Clone, Debug, Default, PartialEq, Eq)]
47pub struct QuerySet(HashSet<Query>);
48
49///
50/// A view is an intermediate structure, a selection/projection of a [relation](../edb/struct.Relation.html),
51/// or the join of two or more views.
52///
53#[derive(Clone, Debug, PartialEq, Eq)]
54pub struct View {
55    schema: Schema<Variable>,
56    facts: HashSet<Row>,
57}
58
59///
60/// A row within a view corresponds to a [`Fact`] within a [`Relation`](../edb/struct.Relation.html),
61/// except that it is not labeled.
62///
63#[derive(Clone, Debug, PartialEq, Eq, Hash)]
64pub struct Row(Vec<Constant>);
65
66pub trait Queryable {
67    fn query(&self, query: &Query) -> Result<Option<View>> {
68        self.query_atom(query.as_ref())
69    }
70
71    fn query_atom(&self, query: &Atom) -> Result<Option<View>>;
72}
73
74// ------------------------------------------------------------------------------------------------
75// Implementations
76// ------------------------------------------------------------------------------------------------
77
78impl Display for Query {
79    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
80        write!(f, "{} {}{}", QUERY_ASCII_PREFIX, self.0, CHAR_PERIOD)
81    }
82}
83
84impl From<Atom> for Query {
85    fn from(v: Atom) -> Self {
86        Self(v)
87    }
88}
89
90impl AsRef<Atom> for Query {
91    fn as_ref(&self) -> &Atom {
92        &self.0
93    }
94}
95
96impl Query {
97    pub fn new<T: Into<Vec<Term>>>(predicate: PredicateRef, terms: T) -> Self {
98        Self(Atom::new(predicate, terms))
99    }
100}
101
102// ------------------------------------------------------------------------------------------------
103
104impl Display for QuerySet {
105    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
106        for query in self.iter() {
107            writeln!(f, "{}", query)?;
108        }
109        Ok(())
110    }
111}
112
113impl Collection<Query> for QuerySet {
114    delegate!(is_empty -> bool);
115
116    delegate!(len -> usize);
117
118    fn iter(&self) -> Box<dyn Iterator<Item = &'_ Query> + '_> {
119        Box::new(self.0.iter())
120    }
121
122    fn contains(&self, value: &Query) -> bool {
123        self.0.contains(value)
124    }
125}
126
127impl QuerySet {
128    pub fn add(&mut self, rule: Query) -> bool {
129        self.0.insert(rule)
130    }
131}
132
133// ------------------------------------------------------------------------------------------------
134
135#[cfg(feature = "tabular")]
136impl Display for View {
137    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
138        use prettytable::format::Alignment;
139        use prettytable::Table;
140        use prettytable::{Attr, Cell};
141
142        let mut table = Table::new();
143
144        table.set_titles(
145            self.schema
146                .iter()
147                .map(|c| {
148                    Cell::new_align(&c.to_column_decl(false), Alignment::CENTER)
149                        .with_style(Attr::Bold)
150                })
151                .collect(),
152        );
153
154        for row in self.iter() {
155            table.add_row(row.iter().map(|c| Cell::new(&c.to_string())).collect());
156        }
157
158        write!(f, "{}", table)
159    }
160}
161
162#[cfg(not(feature = "tabular"))]
163impl Display for View {
164    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
165        writeln!(
166            f,
167            "| {} |",
168            self.schema
169                .iter()
170                .map(|a| a.to_string())
171                .collect::<Vec<String>>()
172                .join(" | ")
173        )?;
174
175        for row in self.iter() {
176            writeln!(
177                f,
178                "| {} |",
179                row.iter()
180                    .map(|a| a.to_string())
181                    .collect::<Vec<String>>()
182                    .join(" | ")
183            )?;
184        }
185        Ok(())
186    }
187}
188
189impl Collection<Row> for View {
190    delegate!(is_empty, facts -> bool);
191
192    delegate!(len, facts -> usize);
193
194    fn iter(&self) -> Box<dyn Iterator<Item = &'_ Row> + '_> {
195        Box::new(self.facts.iter())
196    }
197
198    fn contains(&self, value: &Row) -> bool {
199        self.facts.contains(value)
200    }
201}
202
203impl RelationOps for View {
204    fn union(self, _other: Self) -> Result<View>
205    where
206        Self: Sized,
207    {
208        todo!()
209    }
210
211    fn intersection(self, _other: Self) -> Result<View>
212    where
213        Self: Sized,
214    {
215        todo!()
216    }
217
218    fn difference(self, _other: Self) -> Result<View>
219    where
220        Self: Sized,
221    {
222        todo!()
223    }
224
225    fn cartesian_product(self, _other: Self) -> Result<View>
226    where
227        Self: Sized,
228    {
229        todo!()
230    }
231
232    fn select(self, selection: &Selection) -> Result<View> {
233        Ok(if selection.is_all() {
234            self
235        } else {
236            let results: Result<Vec<Row>> = self
237                .facts
238                .into_iter()
239                .filter_map(|row| row.select(selection).transpose())
240                .collect();
241            Self::new_with_facts(self.schema, results?)
242        })
243    }
244
245    fn project(self, projection: &Projection) -> Result<View> {
246        Ok(if projection.is_all() {
247            self
248        } else {
249            let results: Result<Vec<Row>> = self
250                .facts
251                .into_iter()
252                .map(|row| row.project(projection))
253                .collect();
254            Self::new_with_facts(self.schema, results?)
255        })
256    }
257
258    fn natural_join(self, other: Self) -> Result<Self>
259    where
260        Self: Sized,
261    {
262        let mut new_table: Self = Self::new(
263            self.schema()
264                .label_union(other.schema())
265                .into_iter()
266                .map(Attribute::from)
267                .collect::<Vec<Attribute<Variable>>>(),
268        );
269        let common_variables = self.schema().label_intersection(other.schema());
270
271        // TODO: (ISSUE/rust-asdi/5) infer attribute types for new results!
272        for left_row in self.iter() {
273            for right_row in other.filter(
274                common_variables
275                    .iter()
276                    .map(|(_, left_i, right_i)| (left_row.get(left_i).unwrap().clone(), *right_i))
277                    .collect(),
278            ) {
279                let mut new_row: Vec<Constant> = Vec::with_capacity(new_table.schema().len());
280                for (i, column) in new_table.schema().iter().enumerate() {
281                    if let Some(index) = self.schema().label_to_index(column.label().unwrap()) {
282                        new_row.insert(i, left_row.get(&index).unwrap().clone())
283                    } else if let Some(index) =
284                        other.schema().label_to_index(column.label().unwrap())
285                    {
286                        new_row.insert(i, right_row.get(&index).unwrap().clone())
287                    } else {
288                        error!(
289                            "The column {:?} ({}) was found in neither table.",
290                            column, i
291                        );
292                        unreachable!()
293                    }
294                }
295                new_table.add(new_row.into())?;
296            }
297        }
298        Ok(new_table)
299    }
300
301    fn exists(self, criteria: &Selection) -> Result<bool> {
302        for row in self.facts.into_iter() {
303            if criteria.is_all() || criteria.matches(row.values())? {
304                return Ok(true);
305            }
306        }
307        Ok(false)
308    }
309}
310
311impl View {
312    pub fn empty() -> Self {
313        Self {
314            schema: Schema::empty(),
315            facts: Default::default(),
316        }
317    }
318
319    pub fn new<V: Into<Schema<Variable>>>(schema: V) -> Self {
320        Self {
321            schema: schema.into(),
322            facts: Default::default(),
323        }
324    }
325
326    pub fn new_with_facts<V: Into<Schema<Variable>>, C: Into<Vec<Row>>>(
327        schema: V,
328        facts: C,
329    ) -> Self {
330        Self {
331            schema: schema.into(),
332            facts: HashSet::from_iter(facts.into()),
333        }
334    }
335
336    pub fn new_true() -> Self {
337        Self::new_with_facts(
338            vec![Attribute::from(AttributeKind::Boolean)],
339            vec![Row::from(Constant::new_true())],
340        )
341    }
342
343    pub fn new_false() -> Self {
344        Self::new_with_facts(
345            vec![Attribute::from(AttributeKind::Boolean)],
346            vec![Row::from(Constant::new_false())],
347        )
348    }
349
350    // --------------------------------------------------------------------------------------------
351
352    get!(pub schema -> Schema<Variable>);
353
354    pub fn attribute_index(&self, index: AttributeIndex<Variable>) -> Option<usize> {
355        let index = match &index {
356            AttributeIndex::Label(n) => self.schema.label_to_index(n),
357            AttributeIndex::Index(i) => Some(*i),
358        };
359        index.map(|index| {
360            assert!(index < self.schema.len());
361            index
362        })
363    }
364
365    // --------------------------------------------------------------------------------------------
366
367    pub fn add(&mut self, row: Row) -> Result<()> {
368        self.facts.insert(row);
369        Ok(())
370    }
371
372    pub fn extend(&mut self, other: Self) -> Result<()> {
373        trace!("extend > schema {:?} == {:?}", self.schema, other.schema);
374        assert_eq!(self.schema, other.schema);
375        for fact in other.facts.into_iter() {
376            self.add(fact)?;
377        }
378        Ok(())
379    }
380
381    // --------------------------------------------------------------------------------------------
382    // --------------------------------------------------------------------------------------------
383
384    pub fn join_all<V: Into<Vec<View>>>(views: V) -> Result<Self> {
385        let mut views = views.into();
386        assert!(!views.is_empty());
387        if views.len() == 1 {
388            Ok(views.remove(0))
389        } else {
390            let mut views = views.into_iter();
391            let mut result = views.next().unwrap();
392            for next in views {
393                result = result.natural_join(next)?;
394            }
395            Ok(result)
396        }
397    }
398
399    fn filter(&self, values: Vec<(Constant, usize)>) -> impl Iterator<Item = &Row> {
400        self.iter()
401            .filter(move |row| values.iter().all(|(v, i)| row.get(i).unwrap() == v))
402    }
403}
404
405// ------------------------------------------------------------------------------------------------
406
407impl From<Vec<Constant>> for Row {
408    fn from(v: Vec<Constant>) -> Self {
409        Self(v)
410    }
411}
412
413impl From<Constant> for Row {
414    fn from(v: Constant) -> Self {
415        Self(vec![v])
416    }
417}
418
419impl From<Row> for Vec<Constant> {
420    fn from(v: Row) -> Self {
421        v.0
422    }
423}
424
425impl From<Fact> for Row {
426    fn from(v: Fact) -> Self {
427        Self(v.into())
428    }
429}
430
431impl Collection<Constant> for Row {
432    delegate!(is_empty -> bool);
433
434    delegate!(len -> usize);
435
436    fn iter(&self) -> Box<dyn Iterator<Item = &'_ Constant> + '_> {
437        Box::new(self.0.iter())
438    }
439
440    fn contains(&self, value: &Constant) -> bool {
441        self.0.contains(value)
442    }
443}
444
445impl IndexedCollection<usize, Constant> for Row {
446    fn get(&self, index: &usize) -> Option<&Constant> {
447        self.0.get(*index)
448    }
449
450    fn contains_index(&self, index: &usize) -> bool {
451        *index < self.len()
452    }
453}
454
455impl FactOps for Row {
456    fn project(self, projection: &Projection) -> Result<Row> {
457        Ok(if projection.is_all() {
458            self
459        } else {
460            Self::from(
461                self.0
462                    .into_iter()
463                    .enumerate()
464                    .filter_map(|(i, c)| {
465                        if projection.contains_index(&i) {
466                            Some(c)
467                        } else {
468                            None
469                        }
470                    })
471                    .collect::<Vec<Constant>>(),
472            )
473        })
474    }
475
476    fn select(self, criteria: &Selection) -> Result<Option<Row>> {
477        Ok(if criteria.is_all() || criteria.matches(self.values())? {
478            Some(self)
479        } else {
480            None
481        })
482    }
483}
484
485impl Row {
486    pub fn values(&self) -> &Vec<Constant> {
487        &self.0
488    }
489}
490
491// ------------------------------------------------------------------------------------------------
492// Modules
493// ------------------------------------------------------------------------------------------------
494
495pub mod relational;
asdi/idb/query/mod.rs

asdi/idb/query/
mod.rs
