1// Copyright (C) 2016 Kohei YOSHIDA. All rights reserved.
2//
3// This program is free software; you can redistribute it and/or
4// modify it under the terms of The BSD 3-Clause License
5// that can be found in the LICENSE file.
6
7package uritemplate
8
9import (
10 "bytes"
11 "unicode"
12 "unicode/utf8"
13)
14
15type matcher struct {
16 prog *prog
17
18 list1 threadList
19 list2 threadList
20 matched bool
21 cap map[string][]int
22
23 input string
24}
25
26func (m *matcher) at(pos int) (rune, int, bool) {
27 if l := len(m.input); pos < l {
28 c := m.input[pos]
29 if c < utf8.RuneSelf {
30 return rune(c), 1, pos+1 < l
31 }
32 r, size := utf8.DecodeRuneInString(m.input[pos:])
33 return r, size, pos+size < l
34 }
35 return -1, 0, false
36}
37
38func (m *matcher) add(list *threadList, pc uint32, pos int, next bool, cap map[string][]int) {
39 if i := list.sparse[pc]; i < uint32(len(list.dense)) && list.dense[i].pc == pc {
40 return
41 }
42
43 n := len(list.dense)
44 list.dense = list.dense[:n+1]
45 list.sparse[pc] = uint32(n)
46
47 e := &list.dense[n]
48 e.pc = pc
49 e.t = nil
50
51 op := &m.prog.op[pc]
52 switch op.code {
53 default:
54 panic("unhandled opcode")
55 case opRune, opRuneClass, opEnd:
56 e.t = &thread{
57 op: &m.prog.op[pc],
58 cap: make(map[string][]int, len(m.cap)),
59 }
60 for k, v := range cap {
61 e.t.cap[k] = make([]int, len(v))
62 copy(e.t.cap[k], v)
63 }
64 case opLineBegin:
65 if pos == 0 {
66 m.add(list, pc+1, pos, next, cap)
67 }
68 case opLineEnd:
69 if !next {
70 m.add(list, pc+1, pos, next, cap)
71 }
72 case opCapStart, opCapEnd:
73 ocap := make(map[string][]int, len(m.cap))
74 for k, v := range cap {
75 ocap[k] = make([]int, len(v))
76 copy(ocap[k], v)
77 }
78 ocap[op.name] = append(ocap[op.name], pos)
79 m.add(list, pc+1, pos, next, ocap)
80 case opSplit:
81 m.add(list, pc+1, pos, next, cap)
82 m.add(list, op.i, pos, next, cap)
83 case opJmp:
84 m.add(list, op.i, pos, next, cap)
85 case opJmpIfNotDefined:
86 m.add(list, pc+1, pos, next, cap)
87 m.add(list, op.i, pos, next, cap)
88 case opJmpIfNotFirst:
89 m.add(list, pc+1, pos, next, cap)
90 m.add(list, op.i, pos, next, cap)
91 case opJmpIfNotEmpty:
92 m.add(list, op.i, pos, next, cap)
93 m.add(list, pc+1, pos, next, cap)
94 case opNoop:
95 m.add(list, pc+1, pos, next, cap)
96 }
97}
98
99func (m *matcher) step(clist *threadList, nlist *threadList, r rune, pos int, nextPos int, next bool) {
100 debug.Printf("===== %q =====", string(r))
101 for i := 0; i < len(clist.dense); i++ {
102 e := clist.dense[i]
103 if debug {
104 var buf bytes.Buffer
105 dumpProg(&buf, m.prog, e.pc)
106 debug.Printf("\n%s", buf.String())
107 }
108 if e.t == nil {
109 continue
110 }
111
112 t := e.t
113 op := t.op
114 switch op.code {
115 default:
116 panic("unhandled opcode")
117 case opRune:
118 if op.r == r {
119 m.add(nlist, e.pc+1, nextPos, next, t.cap)
120 }
121 case opRuneClass:
122 ret := false
123 if !ret && op.rc&runeClassU == runeClassU {
124 ret = ret || unicode.Is(rangeUnreserved, r)
125 }
126 if !ret && op.rc&runeClassR == runeClassR {
127 ret = ret || unicode.Is(rangeReserved, r)
128 }
129 if !ret && op.rc&runeClassPctE == runeClassPctE {
130 ret = ret || unicode.Is(unicode.ASCII_Hex_Digit, r)
131 }
132 if ret {
133 m.add(nlist, e.pc+1, nextPos, next, t.cap)
134 }
135 case opEnd:
136 m.matched = true
137 for k, v := range t.cap {
138 m.cap[k] = make([]int, len(v))
139 copy(m.cap[k], v)
140 }
141 clist.dense = clist.dense[:0]
142 }
143 }
144 clist.dense = clist.dense[:0]
145}
146
147func (m *matcher) match() bool {
148 pos := 0
149 clist, nlist := &m.list1, &m.list2
150 for {
151 if len(clist.dense) == 0 && m.matched {
152 break
153 }
154 r, width, next := m.at(pos)
155 if !m.matched {
156 m.add(clist, 0, pos, next, m.cap)
157 }
158 m.step(clist, nlist, r, pos, pos+width, next)
159
160 if width < 1 {
161 break
162 }
163 pos += width
164
165 clist, nlist = nlist, clist
166 }
167 return m.matched
168}
169
170func (tmpl *Template) Match(expansion string) Values {
171 tmpl.mu.Lock()
172 if tmpl.prog == nil {
173 c := compiler{}
174 c.init()
175 c.compile(tmpl)
176 tmpl.prog = c.prog
177 }
178 prog := tmpl.prog
179 tmpl.mu.Unlock()
180
181 n := len(prog.op)
182 m := matcher{
183 prog: prog,
184 list1: threadList{
185 dense: make([]threadEntry, 0, n),
186 sparse: make([]uint32, n),
187 },
188 list2: threadList{
189 dense: make([]threadEntry, 0, n),
190 sparse: make([]uint32, n),
191 },
192 cap: make(map[string][]int, prog.numCap),
193 input: expansion,
194 }
195 if !m.match() {
196 return nil
197 }
198
199 match := make(Values, len(m.cap))
200 for name, indices := range m.cap {
201 v := Value{V: make([]string, len(indices)/2)}
202 for i := range v.V {
203 v.V[i] = pctDecode(expansion[indices[2*i]:indices[2*i+1]])
204 }
205 if len(v.V) == 1 {
206 v.T = ValueTypeString
207 } else {
208 v.T = ValueTypeList
209 }
210 match[name] = v
211 }
212 return match
213}