Skip to content

pattern-data-structure.md

Latest commit

 

History

History
546 lines (386 loc) · 11.3 KB

pattern-data-structure.md

File metadata and controls

546 lines (386 loc) · 11.3 KB

Pattern Data Structure

Source: ../gram-rs/crates/pattern-core/src/pattern.rs
Created: 2026-01-08
Purpose: Reference documentation for the core Pattern<V> data structure used in gram-rs

Overview

Pattern<V> is a recursive, nested structure (s-expression-like) that is generic over value type V. It's the fundamental data structure for representing graph patterns in the gram ecosystem.

Key Characteristics

  • Generic over value type: Pattern<V> can hold any type V
  • Recursive structure: Elements are themselves Pattern<V>, creating nested hierarchies
  • S-expression-like: Not strictly a tree, but accepts tree-like operations
  • Intimate pairing: The value provides "information about the elements"

Type Definition

pub struct Pattern<V> {
    /// The value component, which provides information about the elements
    pub value: V,
    
    /// The nested collection of patterns that form the recursive structure
    pub elements: Vec<Pattern<V>>,
}

Fields

Field Type Description
value V The value component that provides information about the elements
elements Vec<Pattern<V>> Nested collection of patterns (recursive structure)

Common Usage: Pattern

The most common use case is Pattern<Subject>, where patterns contain Subject values representing graph elements (nodes, edges, paths).

Example: Simple Pattern

use pattern_core::{Pattern, Subject, Symbol};
use std::collections::{HashSet, HashMap};

let subject = Subject {
    identity: Symbol("n".to_string()),
    labels: HashSet::new(),
    properties: HashMap::new(),
};

let pattern: Pattern<Subject> = Pattern {
    value: subject,
    elements: vec![],
};

Example: Nested Pattern

use pattern_core::{Pattern, Subject, Symbol};

// Create a pattern with nested elements
let pattern = Pattern {
    value: Subject {
        identity: Symbol("root".to_string()),
        labels: HashSet::new(),
        properties: HashMap::new(),
    },
    elements: vec![
        Pattern {
            value: Subject {
                identity: Symbol("child1".to_string()),
                labels: HashSet::new(),
                properties: HashMap::new(),
            },
            elements: vec![],
        },
        Pattern {
            value: Subject {
                identity: Symbol("child2".to_string()),
                labels: HashSet::new(),
                properties: HashMap::new(),
            },
            elements: vec![],
        },
    ],
};

Pattern Types by Element Count

Patterns can be classified by the number of elements they contain:

Atomic Pattern (0 elements)

Represents a single, indivisible unit.

In gram notation: A node pattern like (alice)

Pattern {
    value: subject,
    elements: vec![],  // Empty = atomic
}

Relationship Pattern (2 elements)

Represents a connection between two patterns.

In gram notation: A relationship like (alice)-[:KNOWS]->(bob)

Pattern {
    value: edge_subject,    // Edge/relationship information
    elements: vec![
        left_pattern,       // Left node
        right_pattern,      // Right node
    ],
}

Subject Pattern (N elements)

Represents a collection or grouping of patterns.

In gram notation: A subject pattern like [team | alice, bob, charlie]

Pattern {
    value: container_subject,  // Container information
    elements: vec![
        member1,
        member2,
        member3,
        // ... more members
    ],
}

Annotated Pattern (1 element)

Represents a pattern with metadata annotations.

In gram notation: An annotated pattern like @type(node) (alice)

Pattern {
    value: annotation_subject,  // Annotation metadata
    elements: vec![
        annotated_pattern,      // The annotated pattern
    ],
}

Construction Functions

Pattern::point

Creates an atomic pattern from a value (0 elements).

let pattern = Pattern::point("hello".to_string());
// Equivalent to: Pattern { value: "hello".to_string(), elements: vec![] }

Pattern::pattern

Creates a pattern with elements (primary constructor).

let pattern = Pattern::pattern(
    "root".to_string(),
    vec![
        Pattern::point("child1".to_string()),
        Pattern::point("child2".to_string()),
    ],
);

Pattern::from_list

Creates a pattern from a list of values.

let values = vec!["a", "b", "c"];
let pattern = Pattern::from_list(values);

Accessor Methods

value()

Returns a reference to the pattern's value.

let pattern = Pattern::point("hello".to_string());
assert_eq!(pattern.value(), "hello");

elements()

Returns a slice of the pattern's elements.

let pattern = Pattern::pattern("root", vec![
    Pattern::point("child1"),
    Pattern::point("child2"),
]);
assert_eq!(pattern.elements().len(), 2);

Inspection Methods

is_atomic()

Checks if a pattern has no elements (atomic).

let atomic = Pattern::point("hello");
assert!(atomic.is_atomic());

let compound = Pattern::pattern("root", vec![atomic]);
assert!(!compound.is_atomic());

length()

Returns the number of direct elements.

let pattern = Pattern::pattern("root", vec![
    Pattern::point("child1"),
    Pattern::point("child2"),
]);
assert_eq!(pattern.length(), 2);

size()

Returns the total number of nodes (including nested).

let pattern = Pattern::pattern("root", vec![
    Pattern::pattern("branch", vec![
        Pattern::point("leaf1"),
        Pattern::point("leaf2"),
    ]),
]);
// Size = 1 (root) + 1 (branch) + 2 (leaves) = 4
assert_eq!(pattern.size(), 4);

depth()

Returns the maximum nesting depth.

let pattern = Pattern::pattern("root", vec![
    Pattern::pattern("branch", vec![
        Pattern::point("leaf"),
    ]),
]);
// Depth: root=1, branch=2, leaf=3
assert_eq!(pattern.depth(), 3);

values()

Extracts all values as a flat list (pre-order traversal).

let pattern = Pattern::pattern("root", vec![
    Pattern::point("child1"),
    Pattern::point("child2"),
]);
let values = pattern.values();
// Returns: ["root", "child1", "child2"]

Query Functions

any_value()

Checks if at least one value satisfies a predicate (short-circuits).

let pattern = Pattern::pattern("root", vec![
    Pattern::point("hello"),
    Pattern::point("world"),
]);

let has_hello = pattern.any_value(|v| v == &"hello");
assert!(has_hello);

all_values()

Checks if all values satisfy a predicate (short-circuits).

let pattern = Pattern::pattern("hello", vec![
    Pattern::point("hello"),
    Pattern::point("hello"),
]);

let all_hello = pattern.all_values(|v| v == &"hello");
assert!(all_hello);

filter()

Extracts subpatterns that satisfy a predicate.

let pattern = Pattern::pattern("root", vec![
    Pattern::point("keep"),
    Pattern::point("drop"),
    Pattern::point("keep"),
]);

let filtered = pattern.filter(|p| p.value() == &"keep");
// Returns patterns with value "keep"

find_first()

Finds the first subpattern that satisfies a predicate (short-circuits).

let pattern = Pattern::pattern("root", vec![
    Pattern::point("first"),
    Pattern::point("second"),
]);

let found = pattern.find_first(|p| p.value() == &"second");
assert!(found.is_some());

matches()

Checks if two patterns have identical structure (ignoring values).

let p1 = Pattern::pattern("a", vec![Pattern::point("b")]);
let p2 = Pattern::pattern("x", vec![Pattern::point("y")]);

assert!(p1.matches(&p2));  // Same structure, different values

contains()

Checks if a pattern contains another as a subpattern.

let inner = Pattern::point("target");
let outer = Pattern::pattern("root", vec![inner.clone()]);

assert!(outer.contains(&inner));

Transformation (Functor)

map()

Transforms pattern values while preserving structure.

let pattern = Pattern::pattern("root", vec![
    Pattern::point("child1"),
    Pattern::point("child2"),
]);

let upper = pattern.map(|s| s.to_uppercase());
// Result: Pattern { value: "ROOT", elements: [...] }

Combination (Combinable)

combine()

Combines two patterns associatively (value combination + element concatenation).

let p1 = Pattern::point("hello".to_string());
let p2 = Pattern::point(" world".to_string());

let combined = p1.combine(p2);
assert_eq!(combined.value(), "hello world");

For types with + operator: Values are combined with +, elements are concatenated.

let p1 = Pattern::pattern("a".to_string(), vec![child1]);
let p2 = Pattern::pattern("b".to_string(), vec![child2]);

let combined = p1.combine(p2);
// Result: Pattern {
//     value: "ab",
//     elements: vec![child1, child2],
// }

Trait Implementations

Clone

Available when V: Clone.

let p1 = Pattern::point("hello".to_string());
let p2 = p1.clone();

PartialEq, Eq

Available when V: PartialEq (or Eq).

let p1 = Pattern::point("hello");
let p2 = Pattern::point("hello");
assert_eq!(p1, p2);

Note: Pattern<Subject> only implements PartialEq (not Eq) because Subject contains f64 values.

PartialOrd, Ord

Available when V: PartialOrd (or Ord). Uses value-first lexicographic ordering.

let p1 = Pattern::point("a");
let p2 = Pattern::point("b");
assert!(p1 < p2);

Hash

Available when V: Hash. Enables use in HashMap/HashSet.

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert(Pattern::point("hello"));

Note: Pattern<Subject> is NOT hashable (Subject contains f64).

Debug, Display

All patterns implement Debug (for debugging) and Display (for human-readable output).

let pattern = Pattern::point("hello");
println!("{:?}", pattern);  // Debug output
println!("{}", pattern);    // Display output

Validation

Patterns can be validated against configurable rules.

ValidationRules

use pattern_core::ValidationRules;

let rules = ValidationRules {
    max_depth: Some(10),
    max_elements: Some(100),
    required_fields: vec![],
};

validate()

let pattern = create_deep_pattern();
match pattern.validate(&rules) {
    Ok(_) => println!("Valid"),
    Err(e) => println!("Invalid: {}", e.message),
}

Structure Analysis

StructureAnalysis

Provides detailed information about pattern structure.

let analysis = pattern.analyze();
println!("Max depth: {}", analysis.max_depth);
println!("Total nodes: {}", analysis.total_nodes);
println!("Leaf nodes: {}", analysis.leaf_count);

Performance Characteristics

  • Deep nesting: Supports at least 100 nesting levels without stack overflow
  • Large patterns: Handles at least 10,000 elements efficiently
  • WASM compatible: All types compile successfully for wasm32-unknown-unknown target

Related Documentation

Last Updated: 2026-01-08