regexp.go

Documentation: regexp/syntax

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