re.bend

yaml-for-bend@0.1.1.0 · 140 lines · 19 definitions

1# A small regular-expression matcher, for the scalar forms schemas name as
2# regexes. A pattern is data: a list of items, each a character class, an
3# optional or repeated item, or a choice of sequences. Matching is anchored
4# at both ends and backtracks. Each step eats a character or moves along the
5# pattern, so fuel of the text's length times a constant bounds the work.
6
7import Base
8
9type Cls is Data:
10  Digit{}
11  Hex{}
12  Range{lo: Char, hi: Char}
13  Lit{c: Char}
14  OneOf{chars: String}
15  NoneOf{chars: String}
16  Alpha{}
17  Space{}
18  Anything{}
19
20type Pat is Data:
21  One{cls: Cls}
22  Opt{p: Pat}
23  Star{p: Pat}
24  Plus{p: Pat}
25  Alt{alts: List<&2, List<&2, Pat>>}
26
27def code(c: Char) -> U32:
28  match c:
29    case Chr{x}:
30      x
31
32def between(+x: U32, lo: U32, hi: U32) -> Bool:
33  Bool.and(U32.is_ge(x, lo), U32.is_le(x, hi))
34
35def in(c: Char, s: String) -> Bool:
36  String.contains(s, SCon{c, SNil{}})
37
38# [[:alpha:]] as Onigmo reads it: ASCII letters, and letters past ASCII.
39def is_alpha(+x: U32) -> Bool:
40  Bool.or(Bool.or(between(x, 65, 90), between(x, 97, 122)),
41    Bool.or(between(x, 170, 170), Bool.or(between(x, 181, 181), Bool.or(between(x, 186, 186),
42      Bool.and(U32.is_ge(x, 192), Bool.and(Bool.not(U32.is_eq(x, 215)), Bool.not(U32.is_eq(x, 247))))))))
43
44def test(cls: Cls, +c: Char) -> Bool:
45  match cls:
46    case Digit{}:
47      Char.is_digit(c)
48    case Hex{}:
49      Bool.or(Char.is_digit(c), Bool.or(between(code(c), 65, 70), between(code(c), 97, 102)))
50    case Range{lo, hi}:
51      between(code(c), code(lo), code(hi))
52    case Lit{x}:
53      Char.is_eq(c, x)
54    case OneOf{chars}:
55      in(c, chars)
56    case NoneOf{chars}:
57      Bool.not(in(c, chars))
58    case Alpha{}:
59      is_alpha(code(c))
60    case Space{}:
61      Char.is_space(c)
62    case Anything{}:
63      True{}
64
65def or.else(hit: Bool, rest: Unit -> Bool) -> Bool:
66  match hit:
67    case True{}:
68      True{}
69    case False{}:
70      rest(Unit{})
71
72def and.then(hit: Bool, rest: Unit -> Bool) -> Bool:
73  match hit:
74    case True{}:
75      rest(Unit{})
76    case False{}:
77      False{}
78
79def run(fuel: Nat, ps: List<&2, Pat>, +s: String) -> Bool:
80  match fuel:
81    case 0n:
82      False{}
83    case 1n+(+k):
84      match ps:
85        case Nil{}:
86          String.is_empty(s)
87        case Con{p, +rest}:
88          match p:
89            case One{cls}:
90              match s:
91                case SNil{}:
92                  False{}
93                case SCon{+c, t}:
94                  and.then(test(cls, c), u => run(k, rest, t))
95            case Opt{+q}:
96              or.else(run(k, q <> rest, s), u => run(k, rest, s))
97            case Star{+q}:
98              or.else(run(k, q <> Star{q} <> rest, s), u => run(k, rest, s))
99            case Plus{+q}:
100              run(k, q <> Star{q} <> rest, s)
101            case Alt{alts}:
102              match alts:
103                case Nil{}:
104                  False{}
105                case Con{a, others}:
106                  or.else(run(k, List.append(&2, Pat, a, rest), s), u => run(k, Alt{others} <> rest, s))
107
108# Whether all of +s+ matches +ps+.
109def matches(ps: List<&2, Pat>, +s: String) -> Bool:
110  run(Nat.mul(Nat.add(String.length(s), 2n), 64n), ps, s)
111
112# Whether +s+ starts with a match of +ps+.
113def starts(ps: List<&2, Pat>, +s: String) -> Bool:
114  matches(List.append(&2, Pat, ps, [Star{One{Anything{}}}]), s)
115
116# Builders, so a pattern reads close to the regex it comes from.
117def c(x: Char) -> Pat:
118  One{Lit{x}}
119
120def digit() -> Pat:
121  One{Digit{}}
122
123def digits() -> Pat:
124  Plus{One{Digit{}}}
125
126def sign() -> Pat:
127  Opt{One{OneOf{"-+"}}}
128
129def of(chars: String) -> Pat:
130  One{OneOf{chars}}
131
132def seq(ps: List<&2, Pat>) -> Pat:
133  Alt{[ps]}
134
135def word(s: String) -> List<&2, Pat>:
136  match s:
137    case SNil{}:
138      []
139    case SCon{x, t}:
140      c(x) <> word(t)