rusty_systems/
system.rs

1//! Collection of tools for defining a group of [`Production`] rules on strings
2//! of symbols.
3//!
4//! # Creating systems
5//!
6//! ## Using [`System`]
7//!
8//! * TODO Talk about [`System::new`] and [`System::default`].
9//! * TODO Talk about [`System::of_family`].
10//! * TODO define a system
11//!
12//! A production that produces the empty string can be represented as so:
13//!
14//! ```
15//! # use rusty_systems::system::System;
16//! # let system = System::default();
17//! let production = system.parse_production("X -> ").unwrap();
18//! ```
19//! 
20//! Context sensitive productions.
21//! todo More detail here
22//!
23//! ```
24//! # use rusty_systems::system::System;
25//! # use rusty_systems::parser;
26//! # let system = System::default();
27//! let production = system.parse_production("G < S -> S G").unwrap();
28//! let string = parser::parse_prod_string("S G S").unwrap();
29//! assert!(!production.matches(&string, 0));       // Does not match the first S
30//! assert!( production.matches(&string, 2));       // Matches the last S
31//! ``` 
32//! 
33//! * todo discuss stochastic rules
34//!
35//! ## Collections of [`Symbol`] and [`Production`]
36//!
37//! TODO talk about collections of symbols and productions.
38//!
39//! # Families
40//!
41//! TODO talk about families
42//!
43//! # Thread safety
44//!
45//! TODO Talk about thread safety
46//!
47//! # See also
48//! * [`Symbol`]
49//! * [`Production`]
50//! * [`ProductionString`]
51//! * [`SystemFamily`]
52
53use std::collections::HashSet;
54use std::ops::Deref;
55use std::sync::RwLock;
56
57use crate::error::{Error, ErrorKind};
58use crate::prelude::*;
59use crate::productions::{Production, ProductionStore};
60use crate::system::family::TryIntoFamily;
61use crate::symbols::{get_code, SymbolStore};
62use crate::symbols::iterator::SymbolIterable;
63use super::{parser, Result, symbols};
64
65pub mod family;
66
67/// Represents an L-system. This is the base for running the
68/// production rules.
69///
70/// This struct is convenient for defining and storing symbols
71/// and productions without having to create your own collections.
72///
73/// See the [system namespace](crate::system) to for information more broadly.
74///
75/// * Productions can be parsed via strings.
76/// * Productions can be programmatically created.
77///
78/// This is thread safe, and is [`Sync`] and [`Send`].
79#[derive(Debug)]
80pub struct System {
81    symbols: RwLock<HashSet<u32>>,
82    productions: RwLock<Vec<Production>>
83}
84
85impl System {
86    pub fn new() -> Self {
87        System {
88            symbols: RwLock::new(HashSet::new()),
89            productions: RwLock::new(Vec::new())
90        }
91    }
92
93    /// Given a previously defined family, this returns a new system
94    /// using the defined symbols / alphabet / words of that family of systems.
95    ///
96    /// ```
97    /// use rusty_systems::system::{family, System};
98    /// use rusty_systems::interpretation::abop;
99    ///
100    /// family::register(abop::abop_family()).expect("Unable to register the family");
101    /// let system = System::of_family("ABOP").expect("Unable to find system");
102    /// ```
103    pub fn of_family<F: TryIntoFamily>(family: F) -> Result<Self> {
104        let family = family.into_family()?;
105        let system = System::default();
106
107        for symbol in family.symbols() {
108            system.add_symbol(symbol.name.as_str())?;
109        }
110
111        Ok(system)
112    }
113
114    /// Parse a string as a production and add it to the system.
115    /// 
116    /// This is essentially equivalent to:
117    /// ```
118    /// # use rusty_systems::system::System;
119    /// # use rusty_systems::productions::ProductionStore;
120    /// # let system = System::default();
121    /// use rusty_systems::parser::parse_production;
122    /// let production = parse_production("A -> B C").unwrap();
123    /// system.add_production(production).unwrap();
124    /// ```
125    pub fn parse_production(&self, production: &str) -> Result<Production> {
126        let prod = parser::parse_production(production)?;
127        
128        let mut map = self.symbols.write()?;
129        prod.all_symbols_iter().for_each(|s| {
130            map.insert(s.code());
131        });
132        self.add_production(prod)
133    }
134    
135
136    /// Run a single iteration of the productions on the given string.
137    /// Returns [`None`] if an empty string is produced.
138    pub fn derive_once(&self, string: ProductionString) -> Result<ProductionString> {
139        if string.is_empty() {
140            return Ok(ProductionString::empty())
141        }
142
143        if let Ok(productions) = self.productions.read() {
144            return derive_once(string, productions.deref());
145        }
146
147        Err(Error::general("Poisoned lock on production list"))
148    }
149
150    pub fn derive(&self, string: ProductionString, settings: RunSettings) -> Result<ProductionString> {
151        if string.is_empty() {
152            return Ok(ProductionString::empty())
153        }
154
155        if let Ok(productions) = self.productions.read() {
156            return derive(string, productions.deref(), settings);
157        }
158
159        Err(Error::general("Poisoned lock on production list"))
160    }
161
162    /// Returns the number of production rules in the system.
163    pub fn production_len(&self) -> usize {
164        self.productions.read().unwrap().len()
165    }
166
167    /// Returns the number of symbols registered with the system
168    pub fn symbol_len(&self) -> usize {
169        self.symbols.read().unwrap().len()
170    }
171}
172
173impl SymbolStore for System {
174    fn add_symbol(&self, name: &str) -> Result<Symbol> {
175        let code = symbols::get_code(name)?;
176        
177        let mut map = self.symbols.write()?;
178        map.insert(code);
179        
180        Ok(Symbol::from_code(code))
181    }
182    
183    /// Return the symbol that represents the given term, if it exists.
184    ///
185    /// Note that this does not create any new symbols to the system.
186    fn get_symbol(&self, name: &str) -> Option<Symbol> {
187        let code = get_code(name).ok()?;
188        let symbols = self.symbols.read().ok()?;
189        
190        symbols.get(&code)
191            .cloned()
192            .map(Symbol::from_code)
193    }
194}
195
196impl ProductionStore for System {
197    /// Adds a production to [`System`]
198    /// 
199    /// This is a thread safe operation. It registers the production and all of its
200    /// symbols with the [`System`] instance.
201    /// 
202    /// The only error this returns is a poison error.
203    fn add_production(&self, production: Production) -> Result<Production> {
204        let lock = self.productions.write();
205        if let Ok(mut productions) = lock {
206            let head = production.head().clone();
207
208            match productions.iter_mut().find(|p| (*p.head()).eq(&head)) {
209                None => productions.push(production),
210                Some(found) => {
211                    found.merge(production);
212                }
213            }
214
215            return Ok(productions.iter().find(|p| (*p.head()).eq(&head)).unwrap().clone())
216        }
217
218        Err(Error::new(ErrorKind::Locking, "production lock is poisoned"))
219    }
220}
221
222
223impl Default for System {
224    fn default() -> Self {
225        System::new()
226    }
227}
228
229/// Defines constraints on deriving strings from an [`System`].
230#[derive(Debug, Clone)]
231pub struct RunSettings {
232    /// The maximum number of iterations allowed for a derivation.
233    pub max_iterations: usize
234}
235
236impl RunSettings {
237    pub fn for_max_iterations(max_iterations: usize) -> Self {
238        RunSettings { max_iterations }
239    }
240}
241
242
243impl From<usize> for RunSettings {
244    fn from(value: usize) -> Self {
245        RunSettings::for_max_iterations(value)
246    }
247}
248
249const DEFAULT_MAX_ITERATIONS : usize = 10;
250
251impl Default for RunSettings {
252    fn default() -> Self {
253        RunSettings {
254            max_iterations: DEFAULT_MAX_ITERATIONS
255        }
256    }
257}
258
259/// Given a vector of productions, this returns a reference to a
260/// production that matches the string at the given location.
261pub fn find_matching<'a>(productions: &'a [Production],
262                     string: &ProductionString, index: usize) -> Option<&'a Production> {
263    for production in productions {
264        if production.matches(string, index) {
265            return Some(production)
266        }
267    }
268
269    None
270}
271
272/// Runs one step of an iteration, using the given production rules.
273///
274/// Most of the time you will want to make use of [`System::derive_once`]
275/// instead of trying to call this function directly.  
276pub fn derive_once(string: ProductionString, productions: &[Production]) -> Result<ProductionString> {
277    if string.is_empty() {
278        return Ok(ProductionString::empty())
279    }
280
281    let mut result = ProductionString::default();
282
283    for (index, symbol) in string.symbols().iter().enumerate() {
284        if let Some(production) = find_matching(productions, &string, index) {
285            let body = production.body()?;
286
287            // println!("body match: {index}: {:?}", body.string().iter().map(|t| t.code()).collect::<Vec<_>>());
288
289            body.string()
290                .symbols()
291                .iter()
292                .cloned()
293                .for_each(|symbol| result.push_symbol(symbol));
294            continue;
295        } else {
296            result.push_symbol(*symbol);
297        }
298
299
300    }
301
302    match result.len() {
303        0 => Ok(ProductionString::empty()),
304        _ => Ok(result)
305    }
306}
307
308pub fn derive(string: ProductionString, productions: &[Production], settings: RunSettings) -> Result<ProductionString> {
309    if string.is_empty() {
310        return Ok(ProductionString::empty())
311    }
312
313    let mut current = string;
314    for _ in 0..settings.max_iterations {
315        current = derive_once(current, productions)?;
316    }
317
318    Ok(current)
319}
320
321
322
323
324
325#[cfg(test)]
326mod tests {
327    use std::thread;
328    use crate::parser::parse_prod_string;
329    use super::*;
330
331    #[test]
332    fn handles_empty_production() {
333        let system = System::new();
334        assert!(system.parse_production("").is_err());
335    }
336
337    #[test]
338    fn handles_no_head() {
339        let system = System::new();
340        assert!(system.parse_production("-> surname surname").is_err());
341    }
342
343    #[test]
344    fn handles_no_body() {
345        let system = System::new();
346        assert!(system.parse_production("Company ->").is_ok());
347    }
348
349    #[test]
350    fn handles_correct() {
351        let system = System::new();
352        assert!(system.parse_production("Company -> surname surname").is_ok());
353    }
354
355    #[test]
356    fn increments_for_distinct_names() {
357        let system = System::new();
358        let symbol1 = system.add_symbol("one").unwrap();
359        let symbol2 = system.add_symbol("two").unwrap();
360
361        assert_ne!(symbol1.code(), symbol2.code());
362    }
363
364    #[test]
365    fn no_increments_for_equal_names() {
366        let system = System::new();
367        let symbol1 = system.add_symbol("one").unwrap();
368        let symbol2 = system.add_symbol("one").unwrap();
369
370        assert_eq!(symbol1.code(), symbol2.code());
371    }
372
373    #[test]
374    fn sync_and_send() {
375        let mut symbol1 : Option<Symbol> = None;
376        let mut symbol2: Option<Symbol> = None;
377
378        let system = System::new();
379
380        thread::scope(|s| {
381            s.spawn(|| {
382                symbol1 = Some(system.add_symbol("one").unwrap());
383            });
384
385            s.spawn(|| {
386                symbol2 = Some(system.add_symbol("two").unwrap());
387            });
388        });
389
390        let symbol1 = symbol1.unwrap();
391        let symbol2 = symbol2.unwrap();
392
393        assert_ne!(symbol1.code(), symbol2.code());
394    }
395
396    #[test]
397    fn can_derive_once() {
398        let system = System::new();
399        system.parse_production("Company -> surname Company").expect("Unable to add production");
400        let string = parse_prod_string("Company").expect("Unable to create string");
401        let result = system.derive_once(string).unwrap();
402
403        assert_eq!(result. len(), 2);
404    }
405
406    #[test]
407    fn can_derive_multiple_times() {
408        let system = System::new();
409        system.parse_production("Company -> surname Company").expect("Unable to add production");
410        let string = parse_prod_string("Company").expect("Unable to create string");
411        let result = system.derive(string, RunSettings::for_max_iterations(2)).expect("Unable to derive");
412
413        assert_eq!(result.len(), 3);
414    }
415
416    #[test]
417    fn test_format() {
418        let system = System::default();
419
420        let symbol = system.add_symbol("a").unwrap();
421        assert_eq!(symbol.to_string(), "a");
422
423        let string = parse_prod_string("a b c").unwrap();
424        assert_eq!(string.to_string(), "a b c");
425    }
426    
427    #[test]
428    fn test_counting_symbols() {
429        let system = System::default();
430        assert_eq!(system.symbol_len(), 0);
431        
432        system.add_symbol("a").unwrap();
433        assert_eq!(system.symbol_len(), 1);
434        assert_eq!(system.production_len(), 0);
435
436        // Nothing should change
437        system.add_symbol("a").unwrap();
438        assert_eq!(system.symbol_len(), 1);
439
440        system.add_symbol("b").unwrap();
441        assert_eq!(system.symbol_len(), 2);
442
443        system.add_symbol("c").unwrap();
444        assert_eq!(system.symbol_len(), 3);
445        assert_eq!(system.production_len(), 0);
446    }
447
448    #[test]
449    fn test_counting_productions() {
450        let system = System::default();
451        assert_eq!(system.symbol_len(), 0);
452        assert_eq!(system.production_len(), 0);
453
454        system.parse_production("F -> F F").unwrap();
455        assert_eq!(system.symbol_len(), 1);
456        assert_eq!(system.production_len(), 1);
457    }
458
459
460    #[test]
461    fn testing_context_sensitive() {
462        let system = System::default();
463        let string = parse_prod_string("G S S S X").unwrap();
464        system.parse_production("G > S -> ").unwrap();
465        system.parse_production("G < S -> S G").unwrap();
466        let string = system.derive_once(string).unwrap();
467
468        assert_eq!(string, parse_prod_string("S G S S X").unwrap());
469
470        let string = system.derive_once(string).unwrap();
471        assert_eq!(string, parse_prod_string("S S G S X").unwrap());
472
473        let string = system.derive_once(string).unwrap();
474        assert_eq!(string, parse_prod_string("S S S G X").unwrap());
475    }
476
477}
rusty_systems/system.rs

rusty_systems/
system.rs
