Struct datafrog::Variable

pub struct Variable<Tuple: Ord> {
    pub stable: Rc<RefCell<Vec<Relation<Tuple>>>>,
    pub recent: Rc<RefCell<Relation<Tuple>>>,
    /* private fields */
}

An monotonically increasing set of Tuples.

There are three stages in the lifecycle of a tuple:

1. A tuple is added to self.to_add, but is not yet visible externally.
2. Newly added tuples are then promoted to self.recent for one iteration.
3. After one iteration, recent tuples are moved to self.tuples for posterity.

Each time self.changed() is called, the recent relation is folded into tuples, and the to_add relations are merged, potentially deduplicated against tuples, and then made recent. This way, across calls to changed() all added tuples are in recent at least once and eventually all are in tuples.

A Variable may optionally be instructed not to de-duplicate its tuples, for reasons of performance. Such a variable cannot be relied on to terminate iterative computation, and it is important that any cycle of derivations have at least one de-duplicating variable on it.

Fields

stable: Rc<RefCell<Vec<Relation<Tuple>>>>

A list of relations whose union are the accepted tuples.

recent: Rc<RefCell<Relation<Tuple>>>

A list of recent tuples, still to be processed.

Implementations

impl<Tuple: Ord> Variable<Tuple>

pub fn from_join<K: Ord, V1: Ord, V2: Ord>(
    &self,
    input1: &Variable<(K, V1)>,
    input2: &Variable<(K, V2)>,
    logic: impl FnMut(&K, &V1, &V2) -> Tuple
)

Adds tuples that result from joining input1 and input2.

Examples

This example starts a collection with the pairs (x, x+1) and (x+1, x) for x in 0 .. 10. It then adds pairs (y, z) for which (x, y) and (x, z) are present. Because the initial pairs are symmetric, this should result in all pairs (x, y) for x and y in 0 .. 11.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x + 1))));
variable.insert(Relation::from((0 .. 10).map(|x| (x + 1, x))));

while iteration.changed() {
    variable.from_join(&variable, &variable, |&key, &val1, &val2| (val1, val2));
}

let result = variable.complete();
assert_eq!(result.len(), 121);

pub fn from_antijoin<K: Ord, V: Ord>(
    &self,
    input1: &Variable<(K, V)>,
    input2: &Relation<K>,
    logic: impl FnMut(&K, &V) -> Tuple
)

Adds tuples from input1 whose key is not present in input2.

Examples

This example starts a collection with the pairs (x, x+1) for x in 0 .. 10. It then adds any pairs (x+1,x) for which x is not a multiple of three. That excludes four pairs (for 0, 3, 6, and 9) which should leave us with 16 total pairs.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x + 1))));

let relation = Relation::from((0 .. 10).filter(|x| x % 3 == 0));

while iteration.changed() {
    variable.from_antijoin(&variable, &relation, |&key, &val| (val, key));
}

let result = variable.complete();
assert_eq!(result.len(), 16);

pub fn from_map<T2: Ord>(
    &self,
    input: &Variable<T2>,
    logic: impl FnMut(&T2) -> Tuple
)

Adds tuples that result from mapping input.

Examples

This example starts a collection with the pairs (x, x) for x in 0 .. 10. It then repeatedly adds any pairs (x, z) for (x, y) in the collection, where z is the Collatz step for y: it is y/2 if y is even, and 3*y + 1 if y is odd. This produces all of the pairs (x, y) where x visits y as part of its Collatz journey.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x))));

while iteration.changed() {
    variable.from_map(&variable, |&(key, val)|
        if val % 2 == 0 {
            (key, val/2)
        }
        else {
            (key, 3*val + 1)
        });
}

let result = variable.complete();
assert_eq!(result.len(), 74);

pub fn from_leapjoin<'a, SourceTuple: Ord, Val: Ord + 'a>(
    &self,
    source: &Variable<SourceTuple>,
    leapers: &mut [&mut dyn Leaper<'a, SourceTuple, Val>],
    logic: impl FnMut(&SourceTuple, &Val) -> Tuple
)

Adds tuples that result from combining source with the relations given in leapers. This operation is very flexible and can be used to do a combination of joins and anti-joins. The main limitation is that the things being combined must consist of one dynamic variable (source) and then several fixed relations (leapers).

The idea is as follows:

• You will be inserting new tuples that result from joining (and anti-joining) some dynamic variable source of source tuples (SourceTuple) with some set of values (of type Val).
• You provide these values by combining source with a set of leapers leapers, each of which is derived from a fixed relation. You can create a leaper in one of two ways:
  • Extension: In this case, you have a relation of type (K, Val) for some type K. You provide a closure that maps from SourceTuple to the key K. If you use relation.extend_with, then any Val values the relation provides will be added to the set of values; if you use extend_anti, then the Val values will be removed.
  • Filtering: In this case, you have a relation of type K for some type K and you provide a closure that maps from SourceTuple to the key K. Filters don’t provide values but they remove source tuples.
• Finally, you get a callback logic that accepts each (SourceTuple, Val) that was successfully joined (and not filtered) and which maps to the type of this variable.

impl<Tuple: Ord> Variable<Tuple>

pub fn insert(&self, relation: Relation<Tuple>)

Inserts a relation into the variable.

This is most commonly used to load initial values into a variable. it is not obvious that it should be commonly used otherwise, but it should not be harmful.

pub fn complete(self) -> Relation<Tuple>

Consumes the variable and returns a relation.

This method removes the ability for the variable to develop, and flattens all internal tuples down to one relation. The method asserts that iteration has completed, in that self.recent and self.to_add should both be empty.

Trait Implementations

impl<Tuple: Ord> Clone for Variable<Tuple>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.