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		"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