URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [regexp/] [syntax/] [regexp.go] - Blame information for rev 747

Details | Compare with Previous | View Log


// Copyright 2011 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
// Package syntax parses regular expressions into syntax trees.
// WORK IN PROGRESS.
package syntax
 
// Note to implementers:
// In this package, re is always a *Regexp and r is always a rune.
 
import (
        "bytes"
        "strconv"
        "strings"
        "unicode"
)
 
// A Regexp is a node in a regular expression syntax tree.
type Regexp struct {
        Op       Op // operator
        Flags    Flags
        Sub      []*Regexp  // subexpressions, if any
        Sub0     [1]*Regexp // storage for short Sub
        Rune     []rune     // matched runes, for OpLiteral, OpCharClass
        Rune0    [2]rune    // storage for short Rune
        Min, Max int        // min, max for OpRepeat
        Cap      int        // capturing index, for OpCapture
        Name     string     // capturing name, for OpCapture
}
 
// An Op is a single regular expression operator.
type Op uint8
 
// Operators are listed in precedence order, tightest binding to weakest.
// Character class operators are listed simplest to most complex
// (OpLiteral, OpCharClass, OpAnyCharNotNL, OpAnyChar).
 
const (
        OpNoMatch        Op = 1 + iota // matches no strings
        OpEmptyMatch                   // matches empty string
        OpLiteral                      // matches Runes sequence
        OpCharClass                    // matches Runes interpreted as range pair list
        OpAnyCharNotNL                 // matches any character
        OpAnyChar                      // matches any character
        OpBeginLine                    // matches empty string at beginning of line
        OpEndLine                      // matches empty string at end of line
        OpBeginText                    // matches empty string at beginning of text
        OpEndText                      // matches empty string at end of text
        OpWordBoundary                 // matches word boundary `\b`
        OpNoWordBoundary               // matches word non-boundary `\B`
        OpCapture                      // capturing subexpression with index Cap, optional name Name
        OpStar                         // matches Sub[0] zero or more times
        OpPlus                         // matches Sub[0] one or more times
        OpQuest                        // matches Sub[0] zero or one times
        OpRepeat                       // matches Sub[0] at least Min times, at most Max (Max == -1 is no limit)
        OpConcat                       // matches concatenation of Subs
        OpAlternate                    // matches alternation of Subs
)
 
const opPseudo Op = 128 // where pseudo-ops start
 
// Equal returns true if x and y have identical structure.
func (x *Regexp) Equal(y *Regexp) bool {
        if x == nil || y == nil {
                return x == y
        }
        if x.Op != y.Op {
                return false
        }
        switch x.Op {
        case OpEndText:
                // The parse flags remember whether this is \z or \Z.
                if x.Flags&WasDollar != y.Flags&WasDollar {
                        return false
                }
 
        case OpLiteral, OpCharClass:
                if len(x.Rune) != len(y.Rune) {
                        return false
                }
                for i, r := range x.Rune {
                        if r != y.Rune[i] {
                                return false
                        }
                }
 
        case OpAlternate, OpConcat:
                if len(x.Sub) != len(y.Sub) {
                        return false
                }
                for i, sub := range x.Sub {
                        if !sub.Equal(y.Sub[i]) {
                                return false
                        }
                }
 
        case OpStar, OpPlus, OpQuest:
                if x.Flags&NonGreedy != y.Flags&NonGreedy || !x.Sub[0].Equal(y.Sub[0]) {
                        return false
                }
 
        case OpRepeat:
                if x.Flags&NonGreedy != y.Flags&NonGreedy || x.Min != y.Min || x.Max != y.Max || !x.Sub[0].Equal(y.Sub[0]) {
                        return false
                }
 
        case OpCapture:
                if x.Cap != y.Cap || x.Name != y.Name || !x.Sub[0].Equal(y.Sub[0]) {
                        return false
                }
        }
        return true
}
 
// writeRegexp writes the Perl syntax for the regular expression re to b.
func writeRegexp(b *bytes.Buffer, re *Regexp) {
        switch re.Op {
        default:
                b.WriteString("")
        case OpNoMatch:
                b.WriteString(`[^\x00-\x{10FFFF}]`)
        case OpEmptyMatch:
                b.WriteString(`(?:)`)
        case OpLiteral:
                if re.Flags&FoldCase != 0 {
                        b.WriteString(`(?i:`)
                }
                for _, r := range re.Rune {
                        escape(b, r, false)
                }
                if re.Flags&FoldCase != 0 {
                        b.WriteString(`)`)
                }
        case OpCharClass:
                if len(re.Rune)%2 != 0 {
                        b.WriteString(`[invalid char class]`)
                        break
                }
                b.WriteRune('[')
                if len(re.Rune) == 0 {
                        b.WriteString(`^\x00-\x{10FFFF}`)
                } else if re.Rune[0] == 0 && re.Rune[len(re.Rune)-1] == unicode.MaxRune {
                        // Contains 0 and MaxRune.  Probably a negated class.
                        // Print the gaps.
                        b.WriteRune('^')
                        for i := 1; i < len(re.Rune)-1; i += 2 {
                                lo, hi := re.Rune[i]+1, re.Rune[i+1]-1
                                escape(b, lo, lo == '-')
                                if lo != hi {
                                        b.WriteRune('-')
                                        escape(b, hi, hi == '-')
                                }
                        }
                } else {
                        for i := 0; i < len(re.Rune); i += 2 {
                                lo, hi := re.Rune[i], re.Rune[i+1]
                                escape(b, lo, lo == '-')
                                if lo != hi {
                                        b.WriteRune('-')
                                        escape(b, hi, hi == '-')
                                }
                        }
                }
                b.WriteRune(']')
        case OpAnyCharNotNL:
                b.WriteString(`(?-s:.)`)
        case OpAnyChar:
                b.WriteString(`(?s:.)`)
        case OpBeginLine:
                b.WriteRune('^')
        case OpEndLine:
                b.WriteRune('$')
        case OpBeginText:
                b.WriteString(`\A`)
        case OpEndText:
                if re.Flags&WasDollar != 0 {
                        b.WriteString(`(?-m:$)`)
                } else {
                        b.WriteString(`\z`)
                }
        case OpWordBoundary:
                b.WriteString(`\b`)
        case OpNoWordBoundary:
                b.WriteString(`\B`)
        case OpCapture:
                if re.Name != "" {
                        b.WriteString(`(?P<`)
                        b.WriteString(re.Name)
                        b.WriteRune('>')
                } else {
                        b.WriteRune('(')
                }
                if re.Sub[0].Op != OpEmptyMatch {
                        writeRegexp(b, re.Sub[0])
                }
                b.WriteRune(')')
        case OpStar, OpPlus, OpQuest, OpRepeat:
                if sub := re.Sub[0]; sub.Op > OpCapture || sub.Op == OpLiteral && len(sub.Rune) > 1 {
                        b.WriteString(`(?:`)
                        writeRegexp(b, sub)
                        b.WriteString(`)`)
                } else {
                        writeRegexp(b, sub)
                }
                switch re.Op {
                case OpStar:
                        b.WriteRune('*')
                case OpPlus:
                        b.WriteRune('+')
                case OpQuest:
                        b.WriteRune('?')
                case OpRepeat:
                        b.WriteRune('{')
                        b.WriteString(strconv.Itoa(re.Min))
                        if re.Max != re.Min {
                                b.WriteRune(',')
                                if re.Max >= 0 {
                                        b.WriteString(strconv.Itoa(re.Max))
                                }
                        }
                        b.WriteRune('}')
                }
                if re.Flags&NonGreedy != 0 {
                        b.WriteRune('?')
                }
        case OpConcat:
                for _, sub := range re.Sub {
                        if sub.Op == OpAlternate {
                                b.WriteString(`(?:`)
                                writeRegexp(b, sub)
                                b.WriteString(`)`)
                        } else {
                                writeRegexp(b, sub)
                        }
                }
        case OpAlternate:
                for i, sub := range re.Sub {
                        if i > 0 {
                                b.WriteRune('|')
                        }
                        writeRegexp(b, sub)
                }
        }
}
 
func (re *Regexp) String() string {
        var b bytes.Buffer
        writeRegexp(&b, re)
        return b.String()
}
 
const meta = `\.+*?()|[]{}^$`
 
func escape(b *bytes.Buffer, r rune, force bool) {
        if unicode.IsPrint(r) {
                if strings.IndexRune(meta, r) >= 0 || force {
                        b.WriteRune('\\')
                }
                b.WriteRune(r)
                return
        }
 
        switch r {
        case '\a':
                b.WriteString(`\a`)
        case '\f':
                b.WriteString(`\f`)
        case '\n':
                b.WriteString(`\n`)
        case '\r':
                b.WriteString(`\r`)
        case '\t':
                b.WriteString(`\t`)
        case '\v':
                b.WriteString(`\v`)
        default:
                if r < 0x100 {
                        b.WriteString(`\x`)
                        s := strconv.FormatInt(int64(r), 16)
                        if len(s) == 1 {
                                b.WriteRune('0')
                        }
                        b.WriteString(s)
                        break
                }
                b.WriteString(`\x{`)
                b.WriteString(strconv.FormatInt(int64(r), 16))
                b.WriteString(`}`)
        }
}
 
// MaxCap walks the regexp to find the maximum capture index.
func (re *Regexp) MaxCap() int {
        m := 0
        if re.Op == OpCapture {
                m = re.Cap
        }
        for _, sub := range re.Sub {
                if n := sub.MaxCap(); m < n {
                        m = n
                }
        }
        return m
}
 
// CapNames walks the regexp to find the names of capturing groups.
func (re *Regexp) CapNames() []string {
        names := make([]string, re.MaxCap()+1)
        re.capNames(names)
        return names
}
 
func (re *Regexp) capNames(names []string) {
        if re.Op == OpCapture {
                names[re.Cap] = re.Name
        }
        for _, sub := range re.Sub {
                sub.capNames(names)
        }
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [regexp/] [syntax/] [regexp.go] - Blame information for rev 747

Line No.	Rev	Author	Line
1	747	jeremybenn	`// 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 []rune // matched runes, for OpLiteral, OpCharClass`
26			`Rune0 [2]rune // 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("")`
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(`(?-s:.)`)
168			`case OpAnyChar:`
169			b.WriteString(`(?s:.)`)
170			`case OpBeginLine:`
171			`b.WriteRune('^')`
172			`case OpEndLine:`
173			`b.WriteRune('$')`
174			`case OpBeginText:`
175			b.WriteString(`\A`)
176			`case OpEndText:`
177			`if re.Flags&WasDollar != 0 {`
178			b.WriteString(`(?-m:$)`)
179			`} else {`
180			b.WriteString(`\z`)
181			`}`
182			`case OpWordBoundary:`
183			b.WriteString(`\b`)
184			`case OpNoWordBoundary:`
185			b.WriteString(`\B`)
186			`case OpCapture:`
187			`if re.Name != "" {`
188			b.WriteString(`(?P<`)
189			`b.WriteString(re.Name)`
190			`b.WriteRune('>')`
191			`} else {`
192			`b.WriteRune('(')`
193			`}`
194			`if re.Sub[0].Op != OpEmptyMatch {`
195			`writeRegexp(b, re.Sub[0])`
196			`}`
197			`b.WriteRune(')')`
198			`case OpStar, OpPlus, OpQuest, OpRepeat:`
199			`if sub := re.Sub[0]; sub.Op > OpCapture \|\| sub.Op == OpLiteral && len(sub.Rune) > 1 {`
200			b.WriteString(`(?:`)
201			`writeRegexp(b, sub)`
202			b.WriteString(`)`)
203			`} else {`
204			`writeRegexp(b, sub)`
205			`}`
206			`switch re.Op {`
207			`case OpStar:`
208			`b.WriteRune('*')`
209			`case OpPlus:`
210			`b.WriteRune('+')`
211			`case OpQuest:`
212			`b.WriteRune('?')`
213			`case OpRepeat:`
214			`b.WriteRune('{')`
215			`b.WriteString(strconv.Itoa(re.Min))`
216			`if re.Max != re.Min {`
217			`b.WriteRune(',')`
218			`if re.Max >= 0 {`
219			`b.WriteString(strconv.Itoa(re.Max))`
220			`}`
221			`}`
222			`b.WriteRune('}')`
223			`}`
224			`if re.Flags&NonGreedy != 0 {`
225			`b.WriteRune('?')`
226			`}`
227			`case OpConcat:`
228			`for _, sub := range re.Sub {`
229			`if sub.Op == OpAlternate {`
230			b.WriteString(`(?:`)
231			`writeRegexp(b, sub)`
232			b.WriteString(`)`)
233			`} else {`
234			`writeRegexp(b, sub)`
235			`}`
236			`}`
237			`case OpAlternate:`
238			`for i, sub := range re.Sub {`
239			`if i > 0 {`
240			`b.WriteRune('\|')`
241			`}`
242			`writeRegexp(b, sub)`
243			`}`
244			`}`
245			`}`
246
247			`func (re *Regexp) String() string {`
248			`var b bytes.Buffer`
249			`writeRegexp(&b, re)`
250			`return b.String()`
251			`}`
252
253			const meta = `\.+*?()\|[]{}^$`
254
255			`func escape(b *bytes.Buffer, r rune, force bool) {`
256			`if unicode.IsPrint(r) {`
257			`if strings.IndexRune(meta, r) >= 0 \|\| force {`
258			`b.WriteRune('\\')`
259			`}`
260			`b.WriteRune(r)`
261			`return`
262			`}`
263
264			`switch r {`
265			`case '\a':`
266			b.WriteString(`\a`)
267			`case '\f':`
268			b.WriteString(`\f`)
269			`case '\n':`
270			b.WriteString(`\n`)
271			`case '\r':`
272			b.WriteString(`\r`)
273			`case '\t':`
274			b.WriteString(`\t`)
275			`case '\v':`
276			b.WriteString(`\v`)
277			`default:`
278			`if r < 0x100 {`
279			b.WriteString(`\x`)
280			`s := strconv.FormatInt(int64(r), 16)`
281			`if len(s) == 1 {`
282			`b.WriteRune('0')`
283			`}`
284			`b.WriteString(s)`
285			`break`
286			`}`
287			b.WriteString(`\x{`)
288			`b.WriteString(strconv.FormatInt(int64(r), 16))`
289			b.WriteString(`}`)
290			`}`
291			`}`
292
293			`// MaxCap walks the regexp to find the maximum capture index.`
294			`func (re *Regexp) MaxCap() int {`
295			`m := 0`
296			`if re.Op == OpCapture {`
297			`m = re.Cap`
298			`}`
299			`for _, sub := range re.Sub {`
300			`if n := sub.MaxCap(); m < n {`
301			`m = n`
302			`}`
303			`}`
304			`return m`
305			`}`
306
307			`// CapNames walks the regexp to find the names of capturing groups.`
308			`func (re *Regexp) CapNames() []string {`
309			`names := make([]string, re.MaxCap()+1)`
310			`re.capNames(names)`
311			`return names`
312			`}`
313
314			`func (re *Regexp) capNames(names []string) {`
315			`if re.Op == OpCapture {`
316			`names[re.Cap] = re.Name`
317			`}`
318			`for _, sub := range re.Sub {`
319			`sub.capNames(names)`
320			`}`
321			`}`