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	}