...
Run Format

Source file src/regexp/syntax/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  	"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 except newline
    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.WriteString(`(?m:^)`)
   170  	case OpEndLine:
   171  		b.WriteString(`(?m:$)`)
   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.ContainsRune(meta, r) || 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  }
   320  

View as plain text