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