match.go•4.56 kB
// Copyright (C) 2016 Kohei YOSHIDA. All rights reserved.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of The BSD 3-Clause License
// that can be found in the LICENSE file.
package uritemplate
import (
"bytes"
"unicode"
"unicode/utf8"
)
type matcher struct {
prog *prog
list1 threadList
list2 threadList
matched bool
cap map[string][]int
input string
}
func (m *matcher) at(pos int) (rune, int, bool) {
if l := len(m.input); pos < l {
c := m.input[pos]
if c < utf8.RuneSelf {
return rune(c), 1, pos+1 < l
}
r, size := utf8.DecodeRuneInString(m.input[pos:])
return r, size, pos+size < l
}
return -1, 0, false
}
func (m *matcher) add(list *threadList, pc uint32, pos int, next bool, cap map[string][]int) {
if i := list.sparse[pc]; i < uint32(len(list.dense)) && list.dense[i].pc == pc {
return
}
n := len(list.dense)
list.dense = list.dense[:n+1]
list.sparse[pc] = uint32(n)
e := &list.dense[n]
e.pc = pc
e.t = nil
op := &m.prog.op[pc]
switch op.code {
default:
panic("unhandled opcode")
case opRune, opRuneClass, opEnd:
e.t = &thread{
op: &m.prog.op[pc],
cap: make(map[string][]int, len(m.cap)),
}
for k, v := range cap {
e.t.cap[k] = make([]int, len(v))
copy(e.t.cap[k], v)
}
case opLineBegin:
if pos == 0 {
m.add(list, pc+1, pos, next, cap)
}
case opLineEnd:
if !next {
m.add(list, pc+1, pos, next, cap)
}
case opCapStart, opCapEnd:
ocap := make(map[string][]int, len(m.cap))
for k, v := range cap {
ocap[k] = make([]int, len(v))
copy(ocap[k], v)
}
ocap[op.name] = append(ocap[op.name], pos)
m.add(list, pc+1, pos, next, ocap)
case opSplit:
m.add(list, pc+1, pos, next, cap)
m.add(list, op.i, pos, next, cap)
case opJmp:
m.add(list, op.i, pos, next, cap)
case opJmpIfNotDefined:
m.add(list, pc+1, pos, next, cap)
m.add(list, op.i, pos, next, cap)
case opJmpIfNotFirst:
m.add(list, pc+1, pos, next, cap)
m.add(list, op.i, pos, next, cap)
case opJmpIfNotEmpty:
m.add(list, op.i, pos, next, cap)
m.add(list, pc+1, pos, next, cap)
case opNoop:
m.add(list, pc+1, pos, next, cap)
}
}
func (m *matcher) step(clist *threadList, nlist *threadList, r rune, pos int, nextPos int, next bool) {
debug.Printf("===== %q =====", string(r))
for i := 0; i < len(clist.dense); i++ {
e := clist.dense[i]
if debug {
var buf bytes.Buffer
dumpProg(&buf, m.prog, e.pc)
debug.Printf("\n%s", buf.String())
}
if e.t == nil {
continue
}
t := e.t
op := t.op
switch op.code {
default:
panic("unhandled opcode")
case opRune:
if op.r == r {
m.add(nlist, e.pc+1, nextPos, next, t.cap)
}
case opRuneClass:
ret := false
if !ret && op.rc&runeClassU == runeClassU {
ret = ret || unicode.Is(rangeUnreserved, r)
}
if !ret && op.rc&runeClassR == runeClassR {
ret = ret || unicode.Is(rangeReserved, r)
}
if !ret && op.rc&runeClassPctE == runeClassPctE {
ret = ret || unicode.Is(unicode.ASCII_Hex_Digit, r)
}
if ret {
m.add(nlist, e.pc+1, nextPos, next, t.cap)
}
case opEnd:
m.matched = true
for k, v := range t.cap {
m.cap[k] = make([]int, len(v))
copy(m.cap[k], v)
}
clist.dense = clist.dense[:0]
}
}
clist.dense = clist.dense[:0]
}
func (m *matcher) match() bool {
pos := 0
clist, nlist := &m.list1, &m.list2
for {
if len(clist.dense) == 0 && m.matched {
break
}
r, width, next := m.at(pos)
if !m.matched {
m.add(clist, 0, pos, next, m.cap)
}
m.step(clist, nlist, r, pos, pos+width, next)
if width < 1 {
break
}
pos += width
clist, nlist = nlist, clist
}
return m.matched
}
func (tmpl *Template) Match(expansion string) Values {
tmpl.mu.Lock()
if tmpl.prog == nil {
c := compiler{}
c.init()
c.compile(tmpl)
tmpl.prog = c.prog
}
prog := tmpl.prog
tmpl.mu.Unlock()
n := len(prog.op)
m := matcher{
prog: prog,
list1: threadList{
dense: make([]threadEntry, 0, n),
sparse: make([]uint32, n),
},
list2: threadList{
dense: make([]threadEntry, 0, n),
sparse: make([]uint32, n),
},
cap: make(map[string][]int, prog.numCap),
input: expansion,
}
if !m.match() {
return nil
}
match := make(Values, len(m.cap))
for name, indices := range m.cap {
v := Value{V: make([]string, len(indices)/2)}
for i := range v.V {
v.V[i] = pctDecode(expansion[indices[2*i]:indices[2*i+1]])
}
if len(v.V) == 1 {
v.T = ValueTypeString
} else {
v.T = ValueTypeList
}
match[name] = v
}
return match
}