match - structure.go
1 package match
2
3 import (
4 "unsafe"
5
6 "vimagination.zapto.org/parser"
7 )
8
9 type visitedSet map[uint32]struct{}
10
11 func parse[T comparable](str string, fn parser.TokenFunc) (*or[T], error) {
12 tk := parser.NewStringTokeniser(str)
13
14 tk.TokeniserState(fn)
15
16 p := parser.New(tk)
17
18 var or or[T]
19
20 if err := or.parse(&p); err != nil {
21 return nil, err
22 }
23
24 return &or, nil
25 }
26
27 type or[T comparable] struct {
28 sequences []sequence[T]
29 }
30
31 func (o *or[T]) parse(p *parser.Parser) error {
32 var s sequence[T]
33
34 if err := s.parse(p); err != nil {
35 return err
36 }
37
38 o.sequences = append(o.sequences, s)
39
40 return nil
41 }
42
43 func (o *or[T]) compile(sm *StateMachine[T], state uint32, visited visitedSet, value T) ([]*uint32, error) {
44 var ends []*uint32
45
46 for _, seq := range o.sequences {
47 seqEnds, err := seq.compile(sm, state, visited, value)
48 if err != nil {
49 return nil, err
50 }
51
52 ends = append(ends, seqEnds...)
53 }
54
55 return ends, nil
56 }
57
58 type sequence[T comparable] struct {
59 parts []part[T]
60 }
61
62 func (s *sequence[T]) parse(p *parser.Parser) error {
63 for {
64 if p.Peek().Type == parser.TokenDone {
65 break
66 }
67
68 var pt part[T]
69
70 if err := pt.parse(p); err != nil {
71 return err
72 }
73
74 if p.Accept(tokenRepeat) {
75 pt.partType = partMany
76 }
77
78 s.parts = append(s.parts, pt)
79 }
80
81 return nil
82 }
83
84 func (s *sequence[T]) compile(sm *StateMachine[T], state uint32, visited visitedSet, value T) ([]*uint32, error) {
85 var (
86 ends = []*uint32{}
87 err error
88 )
89
90 for _, pt := range s.parts {
91 if ends == nil {
92 break
93 } else if len(ends) == 1 {
94 if *ends[0] == 0 {
95 *ends[0] = uint32(len(sm.states))
96 sm.states = append(sm.states, stateValue[T]{})
97 }
98
99 state = *ends[0]
100 }
101
102 ends, err = pt.compile(sm, state, visited, value)
103 if err != nil {
104 return nil, err
105 }
106 }
107
108 return ends, nil
109 }
110
111 type partType uint8
112
113 const (
114 partOne partType = iota
115 partMany
116 partStart
117 partEnd
118 )
119
120 type part[T comparable] struct {
121 partType
122 char *char[T]
123 }
124
125 func (pt *part[T]) parse(p *parser.Parser) error {
126 if p.Accept(tokenStart) {
127 pt.partType = partStart
128 } else if p.Accept(tokenEnd) {
129 pt.partType = partEnd
130 } else {
131 pt.char = new(char[T])
132
133 if err := pt.char.parse(p); err != nil {
134 return err
135 }
136 }
137
138 return nil
139 }
140
141 func (pt *part[T]) compile(sm *StateMachine[T], state uint32, visited visitedSet, value T) ([]*uint32, error) {
142 switch pt.partType {
143 case partOne, partMany:
144 return pt.char.compile(sm, state, visited, value)
145 case partStart:
146 if len(visited) == 0 {
147 return []*uint32{}, nil
148 }
149 case partEnd:
150 var zero T
151
152 if v := sm.states[state].value; v != zero && v != value {
153 return nil, ErrAmbiguous
154 }
155
156 sm.states[state].value = value
157 }
158
159 return nil, nil
160 }
161
162 type char[T comparable] struct {
163 invert bool
164 char [256]bool
165 }
166
167 func (c *char[T]) parse(p *parser.Parser) error {
168 tk := p.Next()
169
170 if tk.Type == parser.TokenError {
171 return p.GetError()
172 } else if tk.Type == tokenAnyChar {
173 c.invert = true
174 }
175
176 for _, b := range unsafe.Slice(unsafe.StringData(tk.Data), len(tk.Data)) {
177 c.char[b] = true
178 }
179
180 return nil
181 }
182
183 func (c *char[T]) compile(sm *StateMachine[T], state uint32, visited visitedSet, value T) ([]*uint32, error) {
184 var ends []*uint32
185
186 for b, v := range c.char {
187 if v != c.invert {
188 ends = append(ends, &sm.states[state].states[b])
189 }
190 }
191
192 return ends, nil
193 }
194