← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/exp/regexp/syntax/compile.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-08-03 17:04:59 UTC
  • mfrom: (14.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20110803170459-wzd99m3567y80ila
Tags: 1:59-1
http://bugs.debian.org/634270
* Imported Upstream version 59
* Refresh patches to a new release
* Fix FTBFS on ARM (Closes: #634270)
* Update version.bash to work with Debian packaging and not hg
  repository

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/exp/regexp/syntax/compile.go
 
1
package syntax
 
2
 
 
3
import (
 
4
        "os"
 
5
        "unicode"
 
6
)
 
7
 
 
8
// A patchList is a list of instruction pointers that need to be filled in (patched).
 
9
// Because the pointers haven't been filled in yet, we can reuse their storage
 
10
// to hold the list.  It's kind of sleazy, but works well in practice.
 
11
// See http://swtch.com/~rsc/regexp/regexp1.html for inspiration.
 
12
// 
 
13
// These aren't really pointers: they're integers, so we can reinterpret them
 
14
// this way without using package unsafe.  A value l denotes
 
15
// p.inst[l>>1].Out (l&1==0) or .Arg (l&1==1). 
 
16
// l == 0 denotes the empty list, okay because we start every program
 
17
// with a fail instruction, so we'll never want to point at its output link.
 
18
type patchList uint32
 
19
 
 
20
func (l patchList) next(p *Prog) patchList {
 
21
        i := &p.Inst[l>>1]
 
22
        if l&1 == 0 {
 
23
                return patchList(i.Out)
 
24
        }
 
25
        return patchList(i.Arg)
 
26
}
 
27
 
 
28
func (l patchList) patch(p *Prog, val uint32) {
 
29
        for l != 0 {
 
30
                i := &p.Inst[l>>1]
 
31
                if l&1 == 0 {
 
32
                        l = patchList(i.Out)
 
33
                        i.Out = val
 
34
                } else {
 
35
                        l = patchList(i.Arg)
 
36
                        i.Arg = val
 
37
                }
 
38
        }
 
39
}
 
40
 
 
41
func (l1 patchList) append(p *Prog, l2 patchList) patchList {
 
42
        if l1 == 0 {
 
43
                return l2
 
44
        }
 
45
        if l2 == 0 {
 
46
                return l1
 
47
        }
 
48
 
 
49
        last := l1
 
50
        for {
 
51
                next := last.next(p)
 
52
                if next == 0 {
 
53
                        break
 
54
                }
 
55
                last = next
 
56
        }
 
57
 
 
58
        i := &p.Inst[last>>1]
 
59
        if last&1 == 0 {
 
60
                i.Out = uint32(l2)
 
61
        } else {
 
62
                i.Arg = uint32(l2)
 
63
        }
 
64
        return l1
 
65
}
 
66
 
 
67
// A frag represents a compiled program fragment.
 
68
type frag struct {
 
69
        i   uint32    // index of first instruction
 
70
        out patchList // where to record end instruction
 
71
}
 
72
 
 
73
type compiler struct {
 
74
        p *Prog
 
75
}
 
76
 
 
77
// Compile compiles the regexp into a program to be executed.
 
78
func Compile(re *Regexp) (*Prog, os.Error) {
 
79
        var c compiler
 
80
        c.init()
 
81
        f := c.compile(re)
 
82
        f.out.patch(c.p, c.inst(InstMatch).i)
 
83
        c.p.Start = int(f.i)
 
84
        return c.p, nil
 
85
}
 
86
 
 
87
func (c *compiler) init() {
 
88
        c.p = new(Prog)
 
89
        c.inst(InstFail)
 
90
}
 
91
 
 
92
var anyRuneNotNL = []int{0, '\n' - 1, '\n' - 1, unicode.MaxRune}
 
93
var anyRune = []int{0, unicode.MaxRune}
 
94
 
 
95
func (c *compiler) compile(re *Regexp) frag {
 
96
        switch re.Op {
 
97
        case OpNoMatch:
 
98
                return c.fail()
 
99
        case OpEmptyMatch:
 
100
                return c.nop()
 
101
        case OpLiteral:
 
102
                if len(re.Rune) == 0 {
 
103
                        return c.nop()
 
104
                }
 
105
                var f frag
 
106
                for j := range re.Rune {
 
107
                        f1 := c.rune(re.Rune[j : j+1])
 
108
                        if j == 0 {
 
109
                                f = f1
 
110
                        } else {
 
111
                                f = c.cat(f, f1)
 
112
                        }
 
113
                }
 
114
                return f
 
115
        case OpCharClass:
 
116
                return c.rune(re.Rune)
 
117
        case OpAnyCharNotNL:
 
118
                return c.rune(anyRuneNotNL)
 
119
        case OpAnyChar:
 
120
                return c.rune(anyRune)
 
121
        case OpBeginLine:
 
122
                return c.empty(EmptyBeginLine)
 
123
        case OpEndLine:
 
124
                return c.empty(EmptyEndLine)
 
125
        case OpBeginText:
 
126
                return c.empty(EmptyBeginText)
 
127
        case OpEndText:
 
128
                return c.empty(EmptyEndText)
 
129
        case OpWordBoundary:
 
130
                return c.empty(EmptyWordBoundary)
 
131
        case OpNoWordBoundary:
 
132
                return c.empty(EmptyNoWordBoundary)
 
133
        case OpCapture:
 
134
                bra := c.cap(uint32(re.Cap << 1))
 
135
                sub := c.compile(re.Sub[0])
 
136
                ket := c.cap(uint32(re.Cap<<1 | 1))
 
137
                return c.cat(c.cat(bra, sub), ket)
 
138
        case OpStar:
 
139
                return c.star(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 
140
        case OpPlus:
 
141
                return c.plus(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 
142
        case OpQuest:
 
143
                return c.quest(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 
144
        case OpConcat:
 
145
                if len(re.Sub) == 0 {
 
146
                        return c.nop()
 
147
                }
 
148
                var f frag
 
149
                for i, sub := range re.Sub {
 
150
                        if i == 0 {
 
151
                                f = c.compile(sub)
 
152
                        } else {
 
153
                                f = c.cat(f, c.compile(sub))
 
154
                        }
 
155
                }
 
156
                return f
 
157
        case OpAlternate:
 
158
                var f frag
 
159
                for _, sub := range re.Sub {
 
160
                        f = c.alt(f, c.compile(sub))
 
161
                }
 
162
                return f
 
163
        }
 
164
        panic("regexp: unhandled case in compile")
 
165
}
 
166
 
 
167
func (c *compiler) inst(op InstOp) frag {
 
168
        // TODO: impose length limit
 
169
        f := frag{i: uint32(len(c.p.Inst))}
 
170
        c.p.Inst = append(c.p.Inst, Inst{Op: op})
 
171
        return f
 
172
}
 
173
 
 
174
func (c *compiler) nop() frag {
 
175
        f := c.inst(InstNop)
 
176
        f.out = patchList(f.i << 1)
 
177
        return f
 
178
}
 
179
 
 
180
func (c *compiler) fail() frag {
 
181
        return frag{}
 
182
}
 
183
 
 
184
func (c *compiler) cap(arg uint32) frag {
 
185
        f := c.inst(InstCapture)
 
186
        f.out = patchList(f.i << 1)
 
187
        c.p.Inst[f.i].Arg = arg
 
188
        return f
 
189
}
 
190
 
 
191
func (c *compiler) cat(f1, f2 frag) frag {
 
192
        // concat of failure is failure
 
193
        if f1.i == 0 || f2.i == 0 {
 
194
                return frag{}
 
195
        }
 
196
 
 
197
        // TODO: elide nop
 
198
 
 
199
        f1.out.patch(c.p, f2.i)
 
200
        return frag{f1.i, f2.out}
 
201
}
 
202
 
 
203
func (c *compiler) alt(f1, f2 frag) frag {
 
204
        // alt of failure is other
 
205
        if f1.i == 0 {
 
206
                return f2
 
207
        }
 
208
        if f2.i == 0 {
 
209
                return f1
 
210
        }
 
211
 
 
212
        f := c.inst(InstAlt)
 
213
        i := &c.p.Inst[f.i]
 
214
        i.Out = f1.i
 
215
        i.Arg = f2.i
 
216
        f.out = f1.out.append(c.p, f2.out)
 
217
        return f
 
218
}
 
219
 
 
220
func (c *compiler) quest(f1 frag, nongreedy bool) frag {
 
221
        f := c.inst(InstAlt)
 
222
        i := &c.p.Inst[f.i]
 
223
        if nongreedy {
 
224
                i.Arg = f1.i
 
225
                f.out = patchList(f.i << 1)
 
226
        } else {
 
227
                i.Out = f1.i
 
228
                f.out = patchList(f.i<<1 | 1)
 
229
        }
 
230
        f.out = f.out.append(c.p, f1.out)
 
231
        return f
 
232
}
 
233
 
 
234
func (c *compiler) star(f1 frag, nongreedy bool) frag {
 
235
        f := c.inst(InstAlt)
 
236
        i := &c.p.Inst[f.i]
 
237
        if nongreedy {
 
238
                i.Arg = f1.i
 
239
                f.out = patchList(f.i << 1)
 
240
        } else {
 
241
                i.Out = f1.i
 
242
                f.out = patchList(f.i<<1 | 1)
 
243
        }
 
244
        f1.out.patch(c.p, f.i)
 
245
        return f
 
246
}
 
247
 
 
248
func (c *compiler) plus(f1 frag, nongreedy bool) frag {
 
249
        return frag{f1.i, c.star(f1, nongreedy).out}
 
250
}
 
251
 
 
252
func (c *compiler) empty(op EmptyOp) frag {
 
253
        f := c.inst(InstEmptyWidth)
 
254
        c.p.Inst[f.i].Arg = uint32(op)
 
255
        f.out = patchList(f.i << 1)
 
256
        return f
 
257
}
 
258
 
 
259
func (c *compiler) rune(rune []int) frag {
 
260
        f := c.inst(InstRune)
 
261
        c.p.Inst[f.i].Rune = rune
 
262
        f.out = patchList(f.i << 1)
 
263
        return f
 
264
}