nanore 0.2.0

Tiny regular expression matcher for arbitrary data types.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

= nanore

image:https://travis-ci.org/y-fujii/nanore.svg?branch=master["Build Status", link="https://travis-ci.org/y-fujii/nanore"]
image:https://docs.rs/nanore/badge.svg["Documentation", link="https://docs.rs/nanore/"]

nanore is a tiny (≃ 0.2K SLOC) regular expression matcher for arbitrary data
types written in Rust.

* O(|regexp||sequence|) time and O(|regexp|) space.  No exponential blowup.
* Support online matching.
* Matching states can be copied at any time.
* Support regex weighting.
* Support path marking.

== Example

=== Basics

[source, rust]
----
use nanore::*;

let re = RegExRoot::<_, ()>::new(
    atom(|_, e| *e % 2 != 0) * atom(|_, e| *e % 2 == 0) + rep(atom(|_, e| *e > 0))
);
let mut m = Matcher::new(&re);

assert!(m.is_match());
m.feed(&1);
assert!(m.is_match());
m.feed(&2);
assert!(m.is_match());
m.feed(&3);
assert!(m.is_match());
m.feed(&0);
assert!(!m.is_match());
----

Constructs: `*` (concatenation), `+` (alternation), `rep()`, `opt()`, `eps()`,
`atom()`, `any()`, `val()`, `weight()`, `mark()`.

=== Mark & Path

[source, rust]
----
#[derive(Clone, Copy, PartialEq, Eq)]
enum Marker { Foo, Bar }

let re = RegExRoot::new(
    rep(mark(Marker::Foo) * val('a') + mark(Marker::Bar) * val('b'))
);
let mut m = Matcher::new(&re);

m.feed(&'a');
m.feed(&'b');
m.feed(&'a');
m.feed(&'b');
assert!(m.is_match());
assert!(m.path() == [(0, Marker::Foo), (1, Marker::Bar), (2, Marker::Foo), (3, Marker::Bar)]);
----

=== Weight

[source, rust]
----
let re = RegExRoot::new(
    rep(mark(Marker::Foo) * val('a')) * rep(weight(-1) * mark(Marker::Bar) * val('a'))
);
let mut m = Matcher::new(&re);

m.feed(&'a');
m.feed(&'a');
m.feed(&'a');
m.feed(&'a');
assert!(m.is_match());
assert!(m.path() == [(0, Marker::Bar), (1, Marker::Bar), (2, Marker::Bar), (3, Marker::Bar)]);
----

=== Application: Find longest fibonacci sequence

[source, rust]
----
#[derive(Clone, Copy, PartialEq, Eq)]
enum Marker { Bgn, End }

let xs = [1, 1, 2, 3, 5, 3, 2, 3, 5, 8, 13, 21, 34];
//        ^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^

let re = RegExRoot::new(
    rep(weight(1) * any()) * mark(Marker::Bgn) *
    any() * any() * rep(atom(|i, x| *x == xs[i - 2] + xs[i - 1])) *
    mark(Marker::End) * rep(weight(1) * any())
);
let mut m = Matcher::new(&re);
m.feed_iter(&xs);

assert!(m.path() == [(6, Marker::Bgn), (13, Marker::End)]);
----

== Reference

http://sebfisch.github.io/haskell-regexp/[Weighted RegExp Matching]::
	nanore uses (the subset of) the method in this paper.  Note that the idea
	is simple and elegant, but there are some non-trivial parts due to
	ε-transitions in implicitly generated ε-NFA (see `empty`, `final` and
	`shift`).  nanore handles normal transitions and ε-transitions separately,
	which seems a bit different from this paper (see `shift()` and
	`propagate()` in nanore).
http://research.preferred.jp/2010/11/regexp-play/[関数型的正規表現マッチ]::
	The excellent article about the paper above, in Japanese.