Source file src/pkg/regexp/syntax/compile.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	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 http://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	}