Struct ReBuilder 

pub struct ReBuilder { /* private fields */ }

A builder for constructing regular expressions in the SMT-LIB string theory.

This is the only way to create Regex instances. The ReBuilder ensures structural sharing by deduplicates identical sub-expressions and assigns globally unique identifiers to each node. An instance of ReBuilder is obtained by calling ReBuilder::default() or ReBuilder::non_optimizing().

Internally, the builder maintains a registry of expressions: if the same regular expression is constructed multiple times, it will return a shared, reference-counted pointer to the same ReNode instance. The builder automatically performs garbage collection on unused expressions to keep memory usage low.

For each SMT-LIB regex operation (e.g., re.*, re.union, re.++, re.comp, etc.), the builder provides a corresponding method to create the appropriate Regex node.

Optimization

By default, the builder performs lightweight optimizations during construction. For instance, it may simplify expressions like (re.++ ε r) to just r. This behavior can be disabled by constructing a builder using ReBuilder::non_optimizing(), which suppresses all such optimizations.

Using multiple builders

Mixing regular expressions from different builders results in logical errors. It is recommended to use a single builder instance to construct all regular expressions in a program.

Example

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

let mut builder1 = ReBuilder::default();
let mut builder2 = ReBuilder::default();

// Construct a regex using the first builder
let r1 = builder1.to_re("a".into());

// Construct a regex using the second builder
let r2 = builder2.to_re("b".into());

// The regexes are structurally different but the following assertion will hold
assert_eq!(r1, r2);

// Construct compound regexes using regexes from different builder will also result in unexpected behavior
let r3 = builder1.union(smallvec![r1.clone(), r2.clone()]);

// The following assertion will hold, although we wanted r3 to accept "a" and "b"
assert!(!r3.accepts(&"b".into()), "Expected {} to accept 'b'", r3);

Implementations

impl ReBuilder

pub fn non_optimizing() -> Self

Creates a new RegexBuilder with on-the-fly optimization disabled.

pub fn manages(&self, regex: &Regex) -> bool

Checks if the builder manages the given regex. Returns true if the regex was constructed by this builder. Returns false otherwise.

Example

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

let mut builder1 = ReBuilder::default();
let mut builder2 = ReBuilder::default();

// Construct a regex using the first builder
let r1 = builder1.to_re("a".into());

// Construct a regex using the second builder
let r2 = builder2.to_re("b".into());


assert!(builder1.manages(&r1));
assert!(!builder1.manages(&r2));
assert!(builder2.manages(&r2));
assert!(!builder2.manages(&r1));

pub fn regex(&mut self, regex: &Regex) -> Regex

Re-create a structurally identical regex as the given one using this builder.

/// # Example

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

let mut builder1 = ReBuilder::default();
let mut builder2 = ReBuilder::default();


// Construct a regex using the second builder
let r = builder2.to_re("b".into());

assert!(!builder1.manages(&r));

let rr = builder1.regex(&r);
assert!(builder1.manages(&rr));

pub fn to_re(&mut self, w: SmtString) -> Regex

Constructor for str.to_re. Returns a regular expression of a constant word.

Example

use smt_str::re::*;
use smt_str::SmtString;

let mut builder = ReBuilder::default();
let string = SmtString::from("abc");
let r = builder.to_re(string.clone());
assert!(r.accepts(&string));

pub fn epsilon(&self) -> Regex

Constructs a regular expression denoting the empty word. This is exactly the regular expression (str.to_re "").

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.epsilon();
assert!(r.accepts(&"".into()));

pub fn none(&self) -> Regex

Constructor for re.none. Returns a regular expression denoting the empty set.

Example

use smt_str::re::*;


let mut builder = ReBuilder::default();
let r = builder.none();
assert!(!r.accepts(&"a".into()));
assert!(!r.accepts(&"".into()));
assert_eq!(r.none(), Some(true));

pub fn all(&self) -> Regex

Constructor for re.all. Returns a regular expression denoting the set of all strings.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.all();
assert!(r.accepts(&"a".into()));
assert!(r.accepts(&"".into()));
assert_eq!(r.universal(), Some(true));

pub fn allchar(&self) -> Regex

Constructor for re.allchar. Returns a regular expression accepting any character in the SMT-LIB alphabet (0 - 0x2FFFF).

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.allchar();
assert!(r.accepts(&"a".into()));
assert!(r.accepts(&"🦀".into()));
assert!(!r.accepts(&"".into()));

pub fn range(&mut self, r: CharRange) -> Regex

Constructor for re.range. Returns a regular expression denoting the set of characters in the given range.

Example

use smt_str::re::*;
use smt_str::alphabet::CharRange;

let mut builder = ReBuilder::default();
let r = builder.range(CharRange::new('a', 'z'));
assert!(r.accepts(&"a".into()));
assert!(r.accepts(&"c".into()));
assert!(r.accepts(&"a".into()));
assert!(r.accepts(&"b".into()));
assert!(!r.accepts(&"A".into()));

pub fn range_from_to( &mut self, l: impl Into<SmtChar>, u: impl Into<SmtChar>, ) -> Regex

Wrapper for ReBuilder::range that creates a range from the given characters.

pub fn concat(&mut self, rs: SmallVec<[Regex; 2]>) -> Regex

Constructor for re.++. Constructs a regular expression denoting the concatenation of the given regular expressions.

Example

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

let mut builder = ReBuilder::default();
let r1 = builder.to_re("abc".into());
let r2 = builder.to_re("def".into());
let r = builder.concat(smallvec![r1, r2]);
assert!(r.accepts(&"abcdef".into()));
assert!(!r.accepts(&"abc".into()));

pub fn union(&mut self, rs: SmallVec<[Regex; 2]>) -> Regex

Constructor for re.union. Returns a regular expression denoting the union of the given regular expressions.

Example

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

let mut builder = ReBuilder::default();
let r1 = builder.to_re("ac".into());
let r2 = builder.to_re("ab".into());
let r = builder.union(smallvec![r1, r2]);
assert!(r.accepts(&"ac".into()));
assert!(r.accepts(&"ab".into()));
assert!(!r.accepts(&"cb".into()));

pub fn inter(&mut self, rs: SmallVec<[Regex; 2]>) -> Regex

Constructor for re.inter. Returns a regular expression denoting the intersection of the given regular expressions.

Example

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

let mut builder = ReBuilder::default();
let r1 = builder.range_from_to('a', 'z');
let r2 = builder.range_from_to('o', 'x');
let r = builder.inter(smallvec![r1, r2]);
assert!(r.accepts(&"o".into()));
assert!(r.accepts(&"q".into()));
assert!(r.accepts(&"x".into()));
assert!(!r.accepts(&"z".into()));
assert!(!r.accepts(&"1".into()));

pub fn star(&mut self, r: Regex) -> Regex

Constructor for re.*. Returns a regular expression denoting the Kleene star of the given regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let s = builder.star(r);
assert!(s.accepts(&"".into()));
assert!(s.accepts(&"a".into()));
assert!(s.accepts(&"aaaa".into()));
assert!(s.accepts(&"aaaaaaaa".into()));
assert!(!s.accepts(&"b".into()));

pub fn plus(&mut self, r: Regex) -> Regex

Constructor for re.+. Returns a regular expression denoting the positive closure of the given regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let p = builder.plus(r);
assert!(!p.accepts(&"".into()));
assert!(p.accepts(&"a".into()));
assert!(p.accepts(&"aaaa".into()));
assert!(p.accepts(&"aaaaaaaa".into()));
assert!(!p.accepts(&"b".into()));

pub fn comp(&mut self, r: Regex) -> Regex

Constructor for re.comp. Returns a regular expression denoting the complement of the given regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let c = builder.comp(r);
assert!(!c.accepts(&"a".into()));
assert!(c.accepts(&"b".into()));
assert!(c.accepts(&"".into()));
assert!(c.accepts(&"aa".into()));

pub fn diff(&mut self, r1: Regex, r2: Regex) -> Regex

Constructor for re.diff. Returns a regular expression denoting the difference of the given regular expressions.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let a = builder.to_re("a".into());
let s = builder.star(a.clone());
let eps = builder.epsilon();
let r = builder.diff(s, eps);

assert!(r.accepts(&"a".into()));
assert!(r.accepts(&"aaaa".into()));
assert!(!r.accepts(&"".into()));
assert!(!r.accepts(&"b".into()));

pub fn opt(&mut self, r: Regex) -> Regex

Constructor for re.opt. Returns a regular expression denoting the optional version of the given regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let o = builder.opt(r);
assert!(o.accepts(&"a".into()));
assert!(o.accepts(&"".into()));
assert!(!o.accepts(&"b".into()));

pub fn pow(&mut self, r: Regex, n: u32) -> Regex

Constructor for re.pow. Returns a regular expression denoting the nth power of the given regular expression.

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let p = builder.pow(r, 3);
assert!(p.accepts(&"aaa".into()));
assert!(!p.accepts(&"aaaa".into()));
assert!(!p.accepts(&"aa".into()));

pub fn loop_(&mut self, r: Regex, l: u32, u: u32) -> Regex

Constructor for re.loop. Returns a regular expression denoting the loop of the given regular expression. That is, the regular expression accepts any number of repetitions of the given regular expression between l and u times (inclusive).

Example

use smt_str::re::*;

let mut builder = ReBuilder::default();
let r = builder.to_re("a".into());
let l = 2;
let u = 4;
let looped = builder.loop_(r, l, u);
assert!(looped.accepts(&"aa".into()));
assert!(looped.accepts(&"aaa".into()));
assert!(looped.accepts(&"aaaa".into()));
assert!(!looped.accepts(&"aaaaa".into()));
assert!(!looped.accepts(&"a".into()));

pub fn reversed(&mut self, r: &Regex) -> Regex

Constructs a regular expression denoting the reverse of the given regular expression. If a word w is accepted by the given regular expression, then the reverse of w is accepted by the returned regular expression.

Trait Implementations

impl Debug for ReBuilder

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

Formats the value using the given formatter.

impl Default for ReBuilder

fn default() -> Self

Creates a new RegexBuilder with an empty internal registry. By default, on-the-fly optimization is enabled.