Struct ReNode 

pub struct ReNode { /* private fields */ }

A node in the abstract syntax tree (AST) of a regular expression.

Each ReNode stores a single operation (ReOp) and a set of lazily computed properties, such as:

• Whether the expression is nullable (i.e., accepts the empty word)
• Whether it is universal (i.e., accepts all words)
• Whether it denotes the empty set or the empty word
• Whether it has a constant prefix, suffix, or word
• The first-character partition and alphabet
• Whether it contains a complement or difference operation

All these properties are cached and evaluated on demand to improve performance.

Every ReNode has a unique identifier assigned by ReBuilder. This is unique across all regular expressions created by the same builder, which enables fast (i.e., O(1)) equality checking and hashing. Instances of this type are also superficially order by their ID.

Note: ReNode is not meant to be used directly. Use the Regex alias, which wraps it in a reference-counted pointer.

Cheap Cloning

The subexpressions of a regular expression are stored as reference-counted pointers (Regex) in the ReOp variant that defines the operation. All derived properties are lazily computed and cached using interior mutability. As a result, cloning a regular expression is inexpensive: it only increments the reference count to shared subexpressions and cached data. This makes it efficient to clone and pass around regular expressions, even when they are large.

Caching and Interior Mutability

This structure uses interior mutability (RefCell) to cache the derived properties. These caches do not affect the Hash, Ord, or Eq implementations, which rely solely on the unique id.

Therefore, it is safe to use ReNode (via Regex) as a key in hash maps or sets, even though Clippy may issue warnings about interior mutability. The warning clippy::mutable_key_type can be safely suppressed for this type using #[allow(clippy::mutable_key_type)]

Implementations

impl ReNode

pub fn id(&self) -> ReId

Returns the unique identifier of the regular expression. The ID assigned by the ReBuilder and unique across all regular expressions created by the same builder.

pub fn op(&self) -> &ReOp

Returns the operation defining the regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let re = builder.to_re("a".into());
assert_eq!(re.op(), &ReOp::Literal("a".into()));

let re_star = builder.star(re.clone());
assert_eq!(re_star.op(), &ReOp::Star(re));

pub fn nullable(&self) -> bool

Returns whether the regular expression is nullable. A regular expression is nullable if it accepts the empty word.

Example

use smt_str::re::*;
let mut builder = ReBuilder::default();
let re = builder.to_re("a".into());
let re_star = builder.star(re.clone());
assert!(!re.nullable());
assert!(re_star.nullable());

pub fn simple(&self) -> bool

Returns whether the regular expression is simple. A regular expression is simple if it does not contain complement, difference, or intersection.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();
let re_a = builder.to_re("a".into());
let re_star = builder.star(re_a.clone());
assert!(re_a.simple());
assert!(re_star.simple());

// Complement, difference, and intersection are not simple.

let re_comp = builder.comp(re_a.clone());
let re_diff = builder.diff(re_star.clone(), re_a.clone());
let re_inter = builder.inter(smallvec![re_star.clone(), re_a.clone()]);
assert!(!re_comp.simple());
assert!(!re_diff.simple());
assert!(!re_inter.simple());

pub fn universal(&self) -> Option<bool>

Returns whether the regular expression is universal. A regular expression is universal if it accepts every word. This is determined heuristically based on the structure of the regular expression. As such, this operation may return None if the universality cannot be determined.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();

assert_eq!(builder.all().universal(), Some(true));
assert_eq!(builder.none().universal(), Some(false));

// Universally can not always be determined.
let re_a = builder.to_re("a".into());
let diff = builder.diff(builder.all(), re_a.clone());
let union = builder.union(smallvec![diff, re_a.clone()]);

assert_eq!(union.universal(), None);

pub fn none(&self) -> Option<bool>

Returns whether the regular expression is the empty set. A regular expression is the empty set if it does not accept any word. This operation may return None if the emptiness cannot be determined.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();
assert_eq!(builder.none().none(), Some(true));
assert_eq!(builder.all().none(), Some(false));

let re_a = builder.to_re("a".into());
let re_comp = builder.comp(re_a.clone());
let inter = builder.inter(smallvec![re_a.clone(), re_comp.clone()]);

assert_eq!(re_a.none(), Some(false));
assert_eq!(re_comp.none(), Some(false));
assert_eq!(inter.none(), None);

pub fn epsilon(&self) -> Option<bool>

Returns whether the regular expression denotes the empty word. A regular expression denotes the empty word if it only accepts the empty word. This operation may return None if the property cannot be determined.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();

assert_eq!(builder.epsilon().epsilon(), Some(true));

let re_a = builder.to_re("a".into());
let re_b = builder.to_re("b".into());
let re_a_star = builder.star(re_a.clone());
let re_b_star = builder.opt(re_a.clone());
// The intersection contains only the empty word but we can't determine it.
let re_inter = builder.inter(smallvec![re_a_star.clone(), re_b_star.clone()]);
assert_eq!(re_inter.epsilon(), None);

pub fn first(&self) -> Rc<AlphabetPartition>

Returns the set of characters that can be first in a word accepted by the regular expression. The set of first characters is partitioned into disjoint subsets of the alphabet, such that for each two characters a and b in the same subset, the left quotient of the regular expression w.r.t. a is equal to the left quotient of the regular expression w.r.t. b. In other words, if a and b are in the same subset, then for all words u, the regular expression accepts a \cdot u iff it accepts b \cdot u.

pub fn alphabet(&self) -> Rc<Alphabet>

The alphabet of the regular expression. The alphabet is the set of characters that occur in the regular expression. This is not the alphabet of words that the regular expression can accept. For example, the alphabet of [^a] is {'a'}, but the alphabet of [^a] is every character except 'a'.

Example

use smt_str::re::*;
use smt_str::alphabet::{Alphabet, CharRange};

use smallvec::smallvec;
let mut builder = ReBuilder::default();
let re_a = builder.to_re("a".into()); // 'a'
let re_b = builder.to_re("b".into()); // 'b'
let re_a_comp = builder.star(re_a.clone()); // comp('a')
let re_union = builder.union(smallvec![re_a_comp.clone(), re_b.clone()]); // comp('a') | 'b'

assert_eq!(re_a.alphabet().as_ref(), &Alphabet::from(CharRange::singleton('a')));
// even though `comp('a')` accepts words with any character from the SMT-LIB alphabet, the alphabet of the regex is still `{'a'}`.
assert_eq!(re_a_comp.alphabet().as_ref(), &Alphabet::from(CharRange::singleton('a')));
assert_eq!(
    re_union.alphabet().as_ref(),
    &Alphabet::from_iter(vec![CharRange::singleton('a'), CharRange::singleton('b')])
);

pub fn is_constant(&self) -> Option<SmtString>

Returns Some(word) if the regular expression accepts only the given constant word, None otherwise or if it cannot be determined.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();

let re_foo = builder.to_re("foo".into());
assert_eq!(re_foo.is_constant(), Some("foo".into()));

// Not a constant word
let re_opt = builder.opt(re_foo.clone());
assert_eq!(re_opt.is_constant(), None);

// Cannot be determined
let re_bar = builder.to_re("bar".into());
let re_foo_or_bar = builder.union(smallvec![re_foo.clone(), re_bar.clone()]);
let inter = builder.inter(smallvec![re_foo.clone(), re_foo_or_bar.clone()]); // foo & (foo | bar) <--> foo
assert_eq!(inter.is_constant(), None);

pub fn prefix(&self) -> Option<SmtString>

Returns the prefix of all words accepted by the regular expression. Makes a best effort to obtain the longest prefix, but does not guarantee it. Is None if the prefix cannot be determined.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();
let re_foo = builder.to_re("foo".into());

assert_eq!(re_foo.prefix(), Some("foo".into()));

let re_bar = builder.to_re("bar".into());
let re_foobar = builder.concat(smallvec![re_foo.clone(), re_bar.clone()]);

let union = builder.union(smallvec![re_foo.clone(), re_foobar.clone()]);
assert_eq!(union.prefix(), Some("foo".into()));

pub fn suffix(&self) -> Option<SmtString>

Returns the suffix of all words accepted by the regular expression. Makes a best effort to obtain the longest suffix, but does not guarantee it. Is None if the suffix cannot be determined, which is the case for some extended regexes.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();
let re_bar = builder.to_re("bar".into());

assert_eq!(re_bar.suffix(), Some("bar".into()));

let re_foo = builder.to_re("foo".into());
let re_foobar = builder.concat(smallvec![re_foo.clone(), re_bar.clone()]);

let union = builder.union(smallvec![re_bar.clone(), re_foobar.clone()]);
assert_eq!(union.suffix(), Some("bar".into()));

pub fn contains_complement(&self) -> bool

Returns whether the regular expression contains a complement operation.

Example

use smt_str::re::*;
use smallvec::smallvec;
let mut builder = ReBuilder::default();
let re_a = builder.to_re("a".into());
let re_b = builder.to_re("b".into());
let re_a_comp = builder.comp(re_a.clone());

assert!(!re_a.contains_complement());
assert!(re_a_comp.contains_complement());

// Difference is equivalent to complement
let diff = builder.diff(re_a.clone(), re_b.clone());
assert!(diff.contains_complement());

pub fn accepts(&self, w: &SmtString) -> bool

Return whether the regular expression accepts a given word.

Example

use smt_str::re::*;
let mut builder = ReBuilder::default();
let re_a = builder.to_re("a".into());
let re_star = builder.star(re_a.clone());
assert!(re_star.accepts(&"a".into()));
assert!(re_star.accepts(&"aaaa".into()));
assert!(re_star.accepts(&"".into()));

pub fn subexpr(&self) -> SubExpressions<'_>

Returns an iterator over the subexpressions of the regular expression.

The subexpressions of a regular expression are the direct children of the operation defining the regex. If the regex is a base case (literal, range, none, any, all), it has no subexpressions.

Example

use smt_str::re::*;
use smallvec::smallvec;

let mut builder = ReBuilder::default();
let re_a = builder.to_re("a".into());
let re_star = builder.star(re_a.clone());
let re_b = builder.to_re("b".into());
let re_union = builder.union(smallvec![re_star.clone(), re_b.clone()]);

let mut subexprs = re_union.subexpr();
assert_eq!(subexprs.next(), Some(&re_star));
assert_eq!(subexprs.next(), Some(&re_b));
assert_eq!(subexprs.next(), None);

Trait Implementations

impl Arbitrary for ReNode

fn arbitrary(g: &mut Gen) -> Self

Return an arbitrary value.

fn shrink(&self) -> Box<dyn Iterator<Item = Self>>

Return an iterator of values that are smaller than itself.

impl Clone for ReNode

fn clone(&self) -> ReNode

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ReNode

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for ReNode

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for ReNode

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Index<usize> for ReNode

fn index(&self, index: usize) -> &Self::Output

Returns the subexpression at the given index. If the index is out of bounds, this function panics. This function always panics on regular expressions that have no subexpressions, i.e., literals, ranges, none, any, and all.

type Output = Rc<ReNode>

The returned type after indexing.

impl Ord for ReNode

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for ReNode

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for ReNode

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for ReNode