← 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/regexp.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/regexp.go
 
1
// Copyright 2011 The Go Authors.  All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
// Package syntax parses regular expressions into syntax trees.
 
6
// WORK IN PROGRESS.
 
7
package syntax
 
8
 
 
9
// Note to implementers:
 
10
// In this package, re is always a *Regexp and r is always a rune.
 
11
 
 
12
import (
 
13
        "bytes"
 
14
        "strconv"
 
15
        "strings"
 
16
        "unicode"
 
17
)
 
18
 
 
19
// A Regexp is a node in a regular expression syntax tree.
 
20
type Regexp struct {
 
21
        Op       Op // operator
 
22
        Flags    Flags
 
23
        Sub      []*Regexp  // subexpressions, if any
 
24
        Sub0     [1]*Regexp // storage for short Sub
 
25
        Rune     []int      // matched runes, for OpLiteral, OpCharClass
 
26
        Rune0    [2]int     // storage for short Rune
 
27
        Min, Max int        // min, max for OpRepeat
 
28
        Cap      int        // capturing index, for OpCapture
 
29
        Name     string     // capturing name, for OpCapture
 
30
}
 
31
 
 
32
// An Op is a single regular expression operator.
 
33
type Op uint8
 
34
 
 
35
// Operators are listed in precedence order, tightest binding to weakest.
 
36
// Character class operators are listed simplest to most complex
 
37
// (OpLiteral, OpCharClass, OpAnyCharNotNL, OpAnyChar).
 
38
 
 
39
const (
 
40
        OpNoMatch        Op = 1 + iota // matches no strings
 
41
        OpEmptyMatch                   // matches empty string
 
42
        OpLiteral                      // matches Runes sequence
 
43
        OpCharClass                    // matches Runes interpreted as range pair list
 
44
        OpAnyCharNotNL                 // matches any character
 
45
        OpAnyChar                      // matches any character
 
46
        OpBeginLine                    // matches empty string at beginning of line
 
47
        OpEndLine                      // matches empty string at end of line
 
48
        OpBeginText                    // matches empty string at beginning of text
 
49
        OpEndText                      // matches empty string at end of text
 
50
        OpWordBoundary                 // matches word boundary `\b`
 
51
        OpNoWordBoundary               // matches word non-boundary `\B`
 
52
        OpCapture                      // capturing subexpression with index Cap, optional name Name
 
53
        OpStar                         // matches Sub[0] zero or more times
 
54
        OpPlus                         // matches Sub[0] one or more times
 
55
        OpQuest                        // matches Sub[0] zero or one times
 
56
        OpRepeat                       // matches Sub[0] at least Min times, at most Max (Max == -1 is no limit)
 
57
        OpConcat                       // matches concatenation of Subs
 
58
        OpAlternate                    // matches alternation of Subs
 
59
)
 
60
 
 
61
const opPseudo Op = 128 // where pseudo-ops start
 
62
 
 
63
// Equal returns true if x and y have identical structure.
 
64
func (x *Regexp) Equal(y *Regexp) bool {
 
65
        if x == nil || y == nil {
 
66
                return x == y
 
67
        }
 
68
        if x.Op != y.Op {
 
69
                return false
 
70
        }
 
71
        switch x.Op {
 
72
        case OpEndText:
 
73
                // The parse flags remember whether this is \z or \Z.
 
74
                if x.Flags&WasDollar != y.Flags&WasDollar {
 
75
                        return false
 
76
                }
 
77
 
 
78
        case OpLiteral, OpCharClass:
 
79
                if len(x.Rune) != len(y.Rune) {
 
80
                        return false
 
81
                }
 
82
                for i, r := range x.Rune {
 
83
                        if r != y.Rune[i] {
 
84
                                return false
 
85
                        }
 
86
                }
 
87
 
 
88
        case OpAlternate, OpConcat:
 
89
                if len(x.Sub) != len(y.Sub) {
 
90
                        return false
 
91
                }
 
92
                for i, sub := range x.Sub {
 
93
                        if !sub.Equal(y.Sub[i]) {
 
94
                                return false
 
95
                        }
 
96
                }
 
97
 
 
98
        case OpStar, OpPlus, OpQuest:
 
99
                if x.Flags&NonGreedy != y.Flags&NonGreedy || !x.Sub[0].Equal(y.Sub[0]) {
 
100
                        return false
 
101
                }
 
102
 
 
103
        case OpRepeat:
 
104
                if x.Flags&NonGreedy != y.Flags&NonGreedy || x.Min != y.Min || x.Max != y.Max || !x.Sub[0].Equal(y.Sub[0]) {
 
105
                        return false
 
106
                }
 
107
 
 
108
        case OpCapture:
 
109
                if x.Cap != y.Cap || x.Name != y.Name || !x.Sub[0].Equal(y.Sub[0]) {
 
110
                        return false
 
111
                }
 
112
        }
 
113
        return true
 
114
}
 
115
 
 
116
// writeRegexp writes the Perl syntax for the regular expression re to b.
 
117
func writeRegexp(b *bytes.Buffer, re *Regexp) {
 
118
        switch re.Op {
 
119
        default:
 
120
                b.WriteString("<invalid op" + strconv.Itoa(int(re.Op)) + ">")
 
121
        case OpNoMatch:
 
122
                b.WriteString(`[^\x00-\x{10FFFF}]`)
 
123
        case OpEmptyMatch:
 
124
                b.WriteString(`(?:)`)
 
125
        case OpLiteral:
 
126
                if re.Flags&FoldCase != 0 {
 
127
                        b.WriteString(`(?i:`)
 
128
                }
 
129
                for _, r := range re.Rune {
 
130
                        escape(b, r, false)
 
131
                }
 
132
                if re.Flags&FoldCase != 0 {
 
133
                        b.WriteString(`)`)
 
134
                }
 
135
        case OpCharClass:
 
136
                if len(re.Rune)%2 != 0 {
 
137
                        b.WriteString(`[invalid char class]`)
 
138
                        break
 
139
                }
 
140
                b.WriteRune('[')
 
141
                if len(re.Rune) == 0 {
 
142
                        b.WriteString(`^\x00-\x{10FFFF}`)
 
143
                } else if re.Rune[0] == 0 && re.Rune[len(re.Rune)-1] == unicode.MaxRune {
 
144
                        // Contains 0 and MaxRune.  Probably a negated class.
 
145
                        // Print the gaps.
 
146
                        b.WriteRune('^')
 
147
                        for i := 1; i < len(re.Rune)-1; i += 2 {
 
148
                                lo, hi := re.Rune[i]+1, re.Rune[i+1]-1
 
149
                                escape(b, lo, lo == '-')
 
150
                                if lo != hi {
 
151
                                        b.WriteRune('-')
 
152
                                        escape(b, hi, hi == '-')
 
153
                                }
 
154
                        }
 
155
                } else {
 
156
                        for i := 0; i < len(re.Rune); i += 2 {
 
157
                                lo, hi := re.Rune[i], re.Rune[i+1]
 
158
                                escape(b, lo, lo == '-')
 
159
                                if lo != hi {
 
160
                                        b.WriteRune('-')
 
161
                                        escape(b, hi, hi == '-')
 
162
                                }
 
163
                        }
 
164
                }
 
165
                b.WriteRune(']')
 
166
        case OpAnyCharNotNL:
 
167
                b.WriteString(`[^\n]`)
 
168
        case OpAnyChar:
 
169
                b.WriteRune('.')
 
170
        case OpBeginLine:
 
171
                b.WriteRune('^')
 
172
        case OpEndLine:
 
173
                b.WriteRune('$')
 
174
        case OpBeginText:
 
175
                b.WriteString(`\A`)
 
176
        case OpEndText:
 
177
                b.WriteString(`\z`)
 
178
        case OpWordBoundary:
 
179
                b.WriteString(`\b`)
 
180
        case OpNoWordBoundary:
 
181
                b.WriteString(`\B`)
 
182
        case OpCapture:
 
183
                if re.Name != "" {
 
184
                        b.WriteString(`(?P<`)
 
185
                        b.WriteString(re.Name)
 
186
                        b.WriteRune('>')
 
187
                } else {
 
188
                        b.WriteRune('(')
 
189
                }
 
190
                if re.Sub[0].Op != OpEmptyMatch {
 
191
                        writeRegexp(b, re.Sub[0])
 
192
                }
 
193
                b.WriteRune(')')
 
194
        case OpStar, OpPlus, OpQuest, OpRepeat:
 
195
                if sub := re.Sub[0]; sub.Op > OpCapture {
 
196
                        b.WriteString(`(?:`)
 
197
                        writeRegexp(b, sub)
 
198
                        b.WriteString(`)`)
 
199
                } else {
 
200
                        writeRegexp(b, sub)
 
201
                }
 
202
                switch re.Op {
 
203
                case OpStar:
 
204
                        b.WriteRune('*')
 
205
                case OpPlus:
 
206
                        b.WriteRune('+')
 
207
                case OpQuest:
 
208
                        b.WriteRune('?')
 
209
                case OpRepeat:
 
210
                        b.WriteRune('{')
 
211
                        b.WriteString(strconv.Itoa(re.Min))
 
212
                        if re.Max != re.Min {
 
213
                                b.WriteRune(',')
 
214
                                if re.Max >= 0 {
 
215
                                        b.WriteString(strconv.Itoa(re.Max))
 
216
                                }
 
217
                        }
 
218
                        b.WriteRune('}')
 
219
                }
 
220
        case OpConcat:
 
221
                for _, sub := range re.Sub {
 
222
                        if sub.Op == OpAlternate {
 
223
                                b.WriteString(`(?:`)
 
224
                                writeRegexp(b, sub)
 
225
                                b.WriteString(`)`)
 
226
                        } else {
 
227
                                writeRegexp(b, sub)
 
228
                        }
 
229
                }
 
230
        case OpAlternate:
 
231
                for i, sub := range re.Sub {
 
232
                        if i > 0 {
 
233
                                b.WriteRune('|')
 
234
                        }
 
235
                        writeRegexp(b, sub)
 
236
                }
 
237
        }
 
238
}
 
239
 
 
240
func (re *Regexp) String() string {
 
241
        var b bytes.Buffer
 
242
        writeRegexp(&b, re)
 
243
        return b.String()
 
244
}
 
245
 
 
246
const meta = `\.+*?()|[]{}^$`
 
247
 
 
248
func escape(b *bytes.Buffer, r int, force bool) {
 
249
        if unicode.IsPrint(r) {
 
250
                if strings.IndexRune(meta, r) >= 0 || force {
 
251
                        b.WriteRune('\\')
 
252
                }
 
253
                b.WriteRune(r)
 
254
                return
 
255
        }
 
256
 
 
257
        switch r {
 
258
        case '\a':
 
259
                b.WriteString(`\a`)
 
260
        case '\f':
 
261
                b.WriteString(`\f`)
 
262
        case '\n':
 
263
                b.WriteString(`\n`)
 
264
        case '\r':
 
265
                b.WriteString(`\r`)
 
266
        case '\t':
 
267
                b.WriteString(`\t`)
 
268
        case '\v':
 
269
                b.WriteString(`\v`)
 
270
        default:
 
271
                if r < 0x100 {
 
272
                        b.WriteString(`\x`)
 
273
                        s := strconv.Itob(r, 16)
 
274
                        if len(s) == 1 {
 
275
                                b.WriteRune('0')
 
276
                        }
 
277
                        b.WriteString(s)
 
278
                        break
 
279
                }
 
280
                b.WriteString(`\x{`)
 
281
                b.WriteString(strconv.Itob(r, 16))
 
282
                b.WriteString(`}`)
 
283
        }
 
284
}