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