compile.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  import "unicode"
     8  
     9  // A patchList is a list of instruction pointers that need to be filled in (patched).
    10  // Because the pointers haven't been filled in yet, we can reuse their storage
    11  // to hold the list. It's kind of sleazy, but works well in practice.
    12  // See https://swtch.com/~rsc/regexp/regexp1.html for inspiration.
    13  //
    14  // These aren't really pointers: they're integers, so we can reinterpret them
    15  // this way without using package unsafe. A value l denotes
    16  // p.inst[l>>1].Out (l&1==0) or .Arg (l&1==1).
    17  // l == 0 denotes the empty list, okay because we start every program
    18  // with a fail instruction, so we'll never want to point at its output link.
    19  type patchList uint32
    20  
    21  func (l patchList) next(p *Prog) patchList {
    22  	i := &p.Inst[l>>1]
    23  	if l&1 == 0 {
    24  		return patchList(i.Out)
    25  	}
    26  	return patchList(i.Arg)
    27  }
    28  
    29  func (l patchList) patch(p *Prog, val uint32) {
    30  	for l != 0 {
    31  		i := &p.Inst[l>>1]
    32  		if l&1 == 0 {
    33  			l = patchList(i.Out)
    34  			i.Out = val
    35  		} else {
    36  			l = patchList(i.Arg)
    37  			i.Arg = val
    38  		}
    39  	}
    40  }
    41  
    42  func (l1 patchList) append(p *Prog, l2 patchList) patchList {
    43  	if l1 == 0 {
    44  		return l2
    45  	}
    46  	if l2 == 0 {
    47  		return l1
    48  	}
    49  
    50  	last := l1
    51  	for {
    52  		next := last.next(p)
    53  		if next == 0 {
    54  			break
    55  		}
    56  		last = next
    57  	}
    58  
    59  	i := &p.Inst[last>>1]
    60  	if last&1 == 0 {
    61  		i.Out = uint32(l2)
    62  	} else {
    63  		i.Arg = uint32(l2)
    64  	}
    65  	return l1
    66  }
    67  
    68  // A frag represents a compiled program fragment.
    69  type frag struct {
    70  	i   uint32    // index of first instruction
    71  	out patchList // where to record end instruction
    72  }
    73  
    74  type compiler struct {
    75  	p *Prog
    76  }
    77  
    78  // Compile compiles the regexp into a program to be executed.
    79  // The regexp should have been simplified already (returned from re.Simplify).
    80  func Compile(re *Regexp) (*Prog, error) {
    81  	var c compiler
    82  	c.init()
    83  	f := c.compile(re)
    84  	f.out.patch(c.p, c.inst(InstMatch).i)
    85  	c.p.Start = int(f.i)
    86  	return c.p, nil
    87  }
    88  
    89  func (c *compiler) init() {
    90  	c.p = new(Prog)
    91  	c.p.NumCap = 2 // implicit ( and ) for whole match $0
    92  	c.inst(InstFail)
    93  }
    94  
    95  var anyRuneNotNL = []rune{0, '\n' - 1, '\n' + 1, unicode.MaxRune}
    96  var anyRune = []rune{0, unicode.MaxRune}
    97  
    98  func (c *compiler) compile(re *Regexp) frag {
    99  	switch re.Op {
   100  	case OpNoMatch:
   101  		return c.fail()
   102  	case OpEmptyMatch:
   103  		return c.nop()
   104  	case OpLiteral:
   105  		if len(re.Rune) == 0 {
   106  			return c.nop()
   107  		}
   108  		var f frag
   109  		for j := range re.Rune {
   110  			f1 := c.rune(re.Rune[j:j+1], re.Flags)
   111  			if j == 0 {
   112  				f = f1
   113  			} else {
   114  				f = c.cat(f, f1)
   115  			}
   116  		}
   117  		return f
   118  	case OpCharClass:
   119  		return c.rune(re.Rune, re.Flags)
   120  	case OpAnyCharNotNL:
   121  		return c.rune(anyRuneNotNL, 0)
   122  	case OpAnyChar:
   123  		return c.rune(anyRune, 0)
   124  	case OpBeginLine:
   125  		return c.empty(EmptyBeginLine)
   126  	case OpEndLine:
   127  		return c.empty(EmptyEndLine)
   128  	case OpBeginText:
   129  		return c.empty(EmptyBeginText)
   130  	case OpEndText:
   131  		return c.empty(EmptyEndText)
   132  	case OpWordBoundary:
   133  		return c.empty(EmptyWordBoundary)
   134  	case OpNoWordBoundary:
   135  		return c.empty(EmptyNoWordBoundary)
   136  	case OpCapture:
   137  		bra := c.cap(uint32(re.Cap << 1))
   138  		sub := c.compile(re.Sub[0])
   139  		ket := c.cap(uint32(re.Cap<<1 | 1))
   140  		return c.cat(c.cat(bra, sub), ket)
   141  	case OpStar:
   142  		return c.star(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
   143  	case OpPlus:
   144  		return c.plus(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
   145  	case OpQuest:
   146  		return c.quest(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
   147  	case OpConcat:
   148  		if len(re.Sub) == 0 {
   149  			return c.nop()
   150  		}
   151  		var f frag
   152  		for i, sub := range re.Sub {
   153  			if i == 0 {
   154  				f = c.compile(sub)
   155  			} else {
   156  				f = c.cat(f, c.compile(sub))
   157  			}
   158  		}
   159  		return f
   160  	case OpAlternate:
   161  		var f frag
   162  		for _, sub := range re.Sub {
   163  			f = c.alt(f, c.compile(sub))
   164  		}
   165  		return f
   166  	}
   167  	panic("regexp: unhandled case in compile")
   168  }
   169  
   170  func (c *compiler) inst(op InstOp) frag {
   171  	// TODO: impose length limit
   172  	f := frag{i: uint32(len(c.p.Inst))}
   173  	c.p.Inst = append(c.p.Inst, Inst{Op: op})
   174  	return f
   175  }
   176  
   177  func (c *compiler) nop() frag {
   178  	f := c.inst(InstNop)
   179  	f.out = patchList(f.i << 1)
   180  	return f
   181  }
   182  
   183  func (c *compiler) fail() frag {
   184  	return frag{}
   185  }
   186  
   187  func (c *compiler) cap(arg uint32) frag {
   188  	f := c.inst(InstCapture)
   189  	f.out = patchList(f.i << 1)
   190  	c.p.Inst[f.i].Arg = arg
   191  
   192  	if c.p.NumCap < int(arg)+1 {
   193  		c.p.NumCap = int(arg) + 1
   194  	}
   195  	return f
   196  }
   197  
   198  func (c *compiler) cat(f1, f2 frag) frag {
   199  	// concat of failure is failure
   200  	if f1.i == 0 || f2.i == 0 {
   201  		return frag{}
   202  	}
   203  
   204  	// TODO: elide nop
   205  
   206  	f1.out.patch(c.p, f2.i)
   207  	return frag{f1.i, f2.out}
   208  }
   209  
   210  func (c *compiler) alt(f1, f2 frag) frag {
   211  	// alt of failure is other
   212  	if f1.i == 0 {
   213  		return f2
   214  	}
   215  	if f2.i == 0 {
   216  		return f1
   217  	}
   218  
   219  	f := c.inst(InstAlt)
   220  	i := &c.p.Inst[f.i]
   221  	i.Out = f1.i
   222  	i.Arg = f2.i
   223  	f.out = f1.out.append(c.p, f2.out)
   224  	return f
   225  }
   226  
   227  func (c *compiler) quest(f1 frag, nongreedy bool) frag {
   228  	f := c.inst(InstAlt)
   229  	i := &c.p.Inst[f.i]
   230  	if nongreedy {
   231  		i.Arg = f1.i
   232  		f.out = patchList(f.i << 1)
   233  	} else {
   234  		i.Out = f1.i
   235  		f.out = patchList(f.i<<1 | 1)
   236  	}
   237  	f.out = f.out.append(c.p, f1.out)
   238  	return f
   239  }
   240  
   241  func (c *compiler) star(f1 frag, nongreedy bool) frag {
   242  	f := c.inst(InstAlt)
   243  	i := &c.p.Inst[f.i]
   244  	if nongreedy {
   245  		i.Arg = f1.i
   246  		f.out = patchList(f.i << 1)
   247  	} else {
   248  		i.Out = f1.i
   249  		f.out = patchList(f.i<<1 | 1)
   250  	}
   251  	f1.out.patch(c.p, f.i)
   252  	return f
   253  }
   254  
   255  func (c *compiler) plus(f1 frag, nongreedy bool) frag {
   256  	return frag{f1.i, c.star(f1, nongreedy).out}
   257  }
   258  
   259  func (c *compiler) empty(op EmptyOp) frag {
   260  	f := c.inst(InstEmptyWidth)
   261  	c.p.Inst[f.i].Arg = uint32(op)
   262  	f.out = patchList(f.i << 1)
   263  	return f
   264  }
   265  
   266  func (c *compiler) rune(r []rune, flags Flags) frag {
   267  	f := c.inst(InstRune)
   268  	i := &c.p.Inst[f.i]
   269  	i.Rune = r
   270  	flags &= FoldCase // only relevant flag is FoldCase
   271  	if len(r) != 1 || unicode.SimpleFold(r[0]) == r[0] {
   272  		// and sometimes not even that
   273  		flags &^= FoldCase
   274  	}
   275  	i.Arg = uint32(flags)
   276  	f.out = patchList(f.i << 1)
   277  
   278  	// Special cases for exec machine.
   279  	switch {
   280  	case flags&FoldCase == 0 && (len(r) == 1 || len(r) == 2 && r[0] == r[1]):
   281  		i.Op = InstRune1
   282  	case len(r) == 2 && r[0] == 0 && r[1] == unicode.MaxRune:
   283  		i.Op = InstRuneAny
   284  	case len(r) == 4 && r[0] == 0 && r[1] == '\n'-1 && r[2] == '\n'+1 && r[3] == unicode.MaxRune:
   285  		i.Op = InstRuneAnyNotNL
   286  	}
   287  
   288  	return f
   289  }
   290
View as plain text