Struct Expression 

pub struct Expression<T> { /* private fields */ }

A self-contained, optimized Boolean logic graph.

Expression stores logic in a deduplicated Directed Acyclic Graph (DAG). It is the immutable, optimized output of an ExpressionBuilder.

Key Features

• Interning: Every unique node (e.g., A | B) is stored exactly once.
• Flat Memory: Nodes are stored in a dense Vec, improving CPU cache locality.
• Safe: Constructed via append-only logic, ensuring no cycles exist.

Example: Boolean Evaluation

This example builds a simple logic gate (A AND NOT B) and evaluates it against a set of active keys.

use logify::{ExpressionBuilder, Expression, Evaluator};
use std::collections::HashSet;

// --- 1. Build the Logic ---
let builder = ExpressionBuilder::new();
let a = builder.leaf("A");
let b = builder.leaf("B");

// Logic: A AND (NOT B)
builder.add_root(a & !b);

let expr: Expression<&str> = builder.build();

// --- 2. Define a Solver ---
// A simple struct that holds which keys are "Active" (True).
struct TruthContext(HashSet<&'static str>);

impl Evaluator<&str, bool, ()> for TruthContext {
    // Base truths
    fn get_universal(&mut self) -> Result<bool, ()> { Ok(true) }
    fn get_empty(&mut self) -> Result<bool, ()> { Ok(false) }
     
    // Leaf lookup: True if the set contains the key
    fn eval_set(&mut self, key: &&str) -> Result<bool, ()> {
        Ok(self.0.contains(key))
    }
     
    // Boolean Logic: OR
    fn eval_union<'a, I>(&mut self, i: I) -> Result<bool, ()>
        where I: IntoIterator<Item=&'a bool>, I::IntoIter: ExactSizeIterator
    {
        Ok(i.into_iter().any(|&b| b))
    }
     
    // Boolean Logic: AND
    fn eval_intersection<'a, I>(&mut self, i: I) -> Result<bool, ()>
        where I: IntoIterator<Item=&'a bool>, I::IntoIter: ExactSizeIterator
    {
        Ok(i.into_iter().all(|&b| b))
    }
     
    // Boolean Logic: AND NOT
    fn eval_difference(&mut self, inc: &bool, exc: &bool) -> Result<bool, ()> {
        Ok(*inc && !*exc)
    }
}

// --- 3. Run Evaluation ---
// Case 1: "A" is present, "B" is missing. Result should be True.
let mut solver = TruthContext(HashSet::from(["A"]));
let results = expr.evaluate(&mut solver).unwrap();
assert_eq!(results[0], true);

// Case 2: "A" and "B" are present. Result should be False (because of NOT B).
let mut solver_2 = TruthContext(HashSet::from(["A", "B"]));
let results_2 = expr.evaluate(&mut solver_2).unwrap();
assert_eq!(results_2[0], false);

Implementations

impl<T> Expression<T>

pub fn evaluate<R, E, S>(&self, solver: &mut S) -> Result<Vec<R>, E>

where R: Clone, S: Evaluator<T, R, E>,

Evaluates the expression using a temporary cache.

This is a convenience wrapper around evaluate_with. It creates a fresh EvaluatorCache, runs the evaluation, and then drops the cache.

Performance Note

Because this allocates memory for every call, it is not recommended for tight loops. Use evaluate_with for repeated evaluations.

Examples found in repository

examples/permissions.rs (line 54)

fn print_access<'a>(name: &str, rules: &Expression<&'a str>, user: &mut BoolEval<&'a str>) {
    // Get the roots (Each representing a permission)
    let perms = rules.evaluate(user).unwrap();

    println!("Permissions for {}:", name);
    println!("  [View]:   {}", perms[0]);
    println!("  [Edit]:   {}", perms[1]);
    println!("  [Delete]: {}", perms[2]);
    println!("-----------------------------");
}

examples/product_filter.rs (line 98)

fn main() -> Result<(), ()> {
    // 1. Build logic
    let builder = ExpressionBuilder::new();
    let red = builder.leaf("Red");
    let blue = builder.leaf("Blue");
    let expensive = builder.leaf("Expensive");

    let filter = (red | blue) & !expensive;
    builder.add_root(filter);

    let expr = builder.build();

    // 2. Setup Evaluator
    let mut db = ProductDb::new();
    db.add_tag("Red", &[1, 2]);
    db.add_tag("Blue", &[3, 4]);
    db.add_tag("Expensive", &[1, 4]);

    // 5. Evaluate
    let results = expr.evaluate(&mut db)?;

    let mut matching_products: Vec<i32> = results[0].iter().copied().collect();
    matching_products.sort();

    println!("Matching Products: {:?}", matching_products);
    assert_eq!(matching_products, vec![2, 3]);

    Ok(())
}

pub fn evaluate_with<R, E, S>( &self, solver: &mut S, cache: &mut EvaluatorCache<R>, ) -> Result<Vec<R>, E>

where R: Clone, S: Evaluator<T, R, E>,

Evaluates the expression using a persistent, external cache.

This is the most efficient way to evaluate an expression multiple times.

How it works

1. Validation: Checks if the cache matches the current expression’s UUID. If not, it clears the cache.
2. Execution: Iterates through the node graph. Intermediate results are stored in the cache.
3. Reuse: If called again, the internal vectors (Vec<Option<R>>) are reused, preventing heap allocation overhead.

Cache Invalidation

The cache is tied to the structure of the expression. Modifying the expression (e.g., via compress(), prune(), or optimize()) changes the UUID, causing the cache to reset on the next call.

pub fn evaluate_with_pruning<R, E, S>( &self, solver: &mut S, ) -> Result<Vec<R>, E>

where R: Clone, S: Evaluator<T, R, E>,

Evaluates the expression while aggressively freeing memory.

Unlike standard evaluation, which keeps all intermediate results until the end, this method calculates reference counts for every node. As soon as a node’s result is consumed by all its parents, the memory is dropped.

Trade-offs

• Pros: Significantly lower peak memory usage. Ideal for very large result types (e.g., Bitmaps, Images).
• Cons: Slower execution speed due to the overhead of calculating reference counts and dropping values during iteration.

impl<T> Expression<T>

pub fn new() -> Self

Creates a new, empty Expression.

pub fn add_root(&mut self, root: NodeId)

registers a node as a “Root” of the expression.

Roots are the entry points for evaluation and dependency iteration. Nodes not reachable from a root are considered dead code.

Panics

Panics if root is not a valid ID belonging to this expression.

Example

let mut expr = logify::Expression::new();
let a = expr.set("A");
expr.add_root(a);

pub fn build_root(&mut self, root: impl FnOnce(&mut Self) -> NodeId)

A helper to build logic and add it as a root in one closure.

This pattern is often more ergonomic than manually creating variables and passing them to add_root.

Example

let mut expr = logify::Expression::new();

// Build (A & B) and add it as a root immediately
expr.build_root(|e| {
    let a = e.set("A");
    let b = e.set("B");
    e.intersection([a, b])
});

pub fn roots(&self) -> Iter<'_, NodeId>

Iterate over the registered root IDs.

Examples found in repository

examples/optimizer.rs (line 71)

fn main() {
    let mut config = OptimizerConfig {
        merger: GeoMerger,
        merger_depth: 2,
        max_iterations: 0,
    };

    // Example 1. California is inside of USA, so it will be redacted
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            any![{ Geo::California }, { Geo::USA }, { Geo::Paris }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("1. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("1. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 2. Texas and France are disjoint, so the result is EMPTY
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(builder, all![{ Geo::Texas }, { Geo::France }]);
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("2. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("2. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 3. California and Texas are both within the USA, so USA is redundant
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            all![any![{ Geo::California }, { Geo::Texas }], { Geo::USA }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("3. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("3. After:  {}", expr.to_string(new_root));
    }
}

pub fn root_count(&self) -> usize

Returns the number of roots.

pub fn nodes(&self) -> Iter<'_, Node<T>>

Iterate linearly over the raw internal nodes.

Note: This iterates the storage vector directly. It includes dead nodes and does not respect topological order.

pub fn node_count(&self) -> usize

Returns the total number of nodes (active and dead) in memory.

pub fn iter_dependencies(&self) -> ExpressionDependencyIter<'_, T>

Returns an iterator that visits nodes in topological order.

This is useful for evaluation or compilation, as it guarantees that a node’s dependencies (children) are yielded before the node itself.

• Post-Order: Children before Parents.
• Pruned: Only visits nodes reachable from the roots.
• Unique: Visits each reachable node exactly once.

impl<T: Hash + PartialEq> Expression<T>

pub fn set(&mut self, value: T) -> NodeId

Creates a leaf node representing a specific value A.

If an identical set A already exists, the existing ID is returned.

Example

let mut expr = logify::Expression::new();
let a1 = expr.set("TagA");
let a2 = expr.set("TagA");

assert_eq!(a1, a2); // Deduplication happens automatically

pub fn union(&mut self, children: impl IntoIterator<Item = NodeId>) -> NodeId

Creates a logical Union (A OR B).

This method acts as a Smart Constructor. It performs immediate on-the-fly simplifications to keep the graph small.

Simplifications Performed

• Commutativity: B | A -> A | B (sorted).
• Idempotence: A | A -> A.
• Identity: A | Empty -> A.
• Annihilation: A | Universal -> Universal.
• Complements: A | !A -> Universal.
• Singleton: Union([A]) -> A.

Example

let mut expr = Expression::new();
let a = expr.set("A");
let b = expr.set("B");

// Standard Union
let a_or_b = expr.union([a, b]);

// Simplification: A | A == A
let a_or_a = expr.union([a, a]);
assert_eq!(a_or_a, a);

pub fn intersection( &mut self, children: impl IntoIterator<Item = NodeId>, ) -> NodeId

Creates a logical Intersection (A AND B).

This method acts as a Smart Constructor. It performs immediate on-the-fly simplifications to keep the graph small.

Simplifications Performed

• Commutativity: B & A -> A & B (sorted).
• Idempotence: A & A -> A.
• Identity: A & Universal -> A.
• Annihilation: A & Empty -> Empty.
• Complements: A & !A -> Empty.
• Singleton: Intersection([A]) -> A.

Example

let mut expr = Expression::new();
let a = expr.set("A");
let not_a = expr.complement(a);

// Simplification: A & !A == Empty
let impossible = expr.intersection([a, not_a]);
assert_eq!(impossible, logify::NodeId::EMPTY);

pub fn complement(&self, child: NodeId) -> NodeId

Returns the complement A => A’.

impl<T: Display> Expression<T>

pub fn to_string(&self, root: &NodeId) -> String

Recursively formats the expression starting from the given root.

Example

let mut expr = Expression::new();
let a = expr.set("A");
let b = expr.set("B");
let root = expr.intersection([a, b]);

assert_eq!(expr.to_string(&root), "([A] & [B])");

Examples found in repository

examples/optimizer.rs (line 72)

fn main() {
    let mut config = OptimizerConfig {
        merger: GeoMerger,
        merger_depth: 2,
        max_iterations: 0,
    };

    // Example 1. California is inside of USA, so it will be redacted
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            any![{ Geo::California }, { Geo::USA }, { Geo::Paris }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("1. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("1. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 2. Texas and France are disjoint, so the result is EMPTY
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(builder, all![{ Geo::Texas }, { Geo::France }]);
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("2. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("2. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 3. California and Texas are both within the USA, so USA is redundant
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            all![any![{ Geo::California }, { Geo::Texas }], { Geo::USA }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("3. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("3. After:  {}", expr.to_string(new_root));
    }
}

impl<T: Hash + PartialEq> Expression<T>

pub fn prune<R>(self) -> Self

Removes unreachable nodes (Garbage Collection).

When you modify an expression (e.g., via build_into or manual logic), nodes that are no longer connected to any root may be left behind. This method rebuilds the expression, keeping only the live nodes.

Important

• Invalidation: All existing NodeIds are invalidated. Do not use old IDs after calling this.
• Cache Reset: This invalidates any attached EvaluatorCache (resetting its UUID).
• Reordering: Nodes may be re-ordered in memory.

pub fn prune_with_cache<R>(self, cache: Option<&mut EvaluatorCache<R>>) -> Self

Removes unreachable nodes while preserving an external cache.

Identical to prune, but attempts to remap the values inside cache so that expensive computations don’t need to be redone.

Arguments

• cache - The cache to update. If provided, its internal mapping is updated to match the new node layout.

pub fn absorb_raw<I>(&mut self, exprs: I)

where T: Clone, I: IntoIterator<Item = Expression<T>>,

Moves the logic from other expressions into this one.

This consumes the source expressions.

Performance

• Fast: Operates directly on internal storage without traversing the graph.
• Dirty: Includes dead nodes from the source. If the source expression contains garbage (nodes not connected to roots), that garbage is copied into self. Call prune afterwards if this is a concern.

pub fn merge_raw<'a, I>(&mut self, exprs: I)

where T: 'a + Clone, I: IntoIterator<Item = &'a Expression<T>>,

Clones the logic from multiple expressions into this one.

Useful if you need to keep the original expressions intact.

Performance

• Fast: Linear copy of internal storage. May be slower than absorb_raw because it clones every term.
• Dirty: Includes dead nodes from the source.

pub fn compress<R>(self, cache: Option<&mut EvaluatorCache<R>>) -> Self

Globally deduplicates logic patterns (Common Subexpression Elimination).

While the builder deduplicates nodes (e.g., A & B is only stored once), it does not automatically refactor deeply nested structures. compress finds repeated patterns across the entire graph and factors them out.

Example

• Before: (A & B & C) and (A & B & D) are separate nodes.
• After: (A & B) becomes a shared node, referenced by both parents.

Use Case

Recommended to run after optimize, as optimization often exposes new structural similarities.

impl<T: Hash + PartialEq> Expression<T>

pub fn optimize<M: Mergeable<T>>(&mut self, config: &mut OptimizerConfig<M>)

Applies logic reduction and domain-specific simplification to the expression.

This method performs operations such as:

• Flattening: Union(A, Union(B, C)) becomes Union(A, B, C).
• De Morgan’s Laws: Distributes negations to minimize depth.
• Absorption: A & (A | B) simplifies to A.
• Custom Merging: Uses the provided Mergeable implementation to combine sets.

Dead Nodes

Optimization rewrites connections between nodes. This often leaves behind “dead” nodes (nodes that are no longer connected to any root). While this does not affect evaluation correctness, you may wish to call Expression::clean afterwards if memory footprint is a concern.

Examples found in repository

examples/optimizer.rs (line 74)

fn main() {
    let mut config = OptimizerConfig {
        merger: GeoMerger,
        merger_depth: 2,
        max_iterations: 0,
    };

    // Example 1. California is inside of USA, so it will be redacted
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            any![{ Geo::California }, { Geo::USA }, { Geo::Paris }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("1. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("1. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 2. Texas and France are disjoint, so the result is EMPTY
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(builder, all![{ Geo::Texas }, { Geo::France }]);
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("2. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("2. After:  {}", expr.to_string(new_root));
    }
    println!();

    // Example 3. California and Texas are both within the USA, so USA is redundant
    {
        let builder = ExpressionBuilder::new();
        let rule = logic!(
            builder,
            all![any![{ Geo::California }, { Geo::Texas }], { Geo::USA }]
        );
        builder.add_root(rule);

        let mut expr = builder.build();

        let root = expr.roots().next().unwrap();
        println!("3. Before: {}", expr.to_string(root));

        expr.optimize(&mut config);

        let new_root = expr.roots().next().unwrap();
        println!("3. After:  {}", expr.to_string(new_root));
    }
}

Trait Implementations

impl<T: Clone + Hash + PartialEq> Clone for Expression<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Default for Expression<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T> Deserialize<'de> for Expression<T>

where T: Serialize + for<'a> Deserialize<'a> + Hash + PartialEq,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, T: Clone + Hash + PartialEq> Extend<&'a Expression<T>> for Expression<T>

fn extend<I: IntoIterator<Item = &'a Expression<T>>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T: Hash + PartialEq + Clone> Extend<&'a ExpressionBuilder<T>> for Expression<T>

fn extend<I: IntoIterator<Item = &'a ExpressionBuilder<T>>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Hash + PartialEq> Extend<Expression<T>> for Expression<T>

fn extend<I: IntoIterator<Item = Expression<T>>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Hash + PartialEq> Extend<ExpressionBuilder<T>> for Expression<T>

fn extend<I: IntoIterator<Item = ExpressionBuilder<T>>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> IntoIterator for &Expression<T>

type Item = &Expression<T>

The type of the elements being iterated over.

type IntoIter = Once<&Expression<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for Expression<T>

type Item = Expression<T>

The type of the elements being iterated over.

type IntoIter = Once<Expression<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Serialize for Expression<T>

where T: Serialize + for<'a> Deserialize<'a> + Hash + PartialEq,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.