path_template_parser.go 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. // Copyright 2016, Google Inc.
  2. // All rights reserved.
  3. //
  4. // Redistribution and use in source and binary forms, with or without
  5. // modification, are permitted provided that the following conditions are
  6. // met:
  7. //
  8. // * Redistributions of source code must retain the above copyright
  9. // notice, this list of conditions and the following disclaimer.
  10. // * Redistributions in binary form must reproduce the above
  11. // copyright notice, this list of conditions and the following disclaimer
  12. // in the documentation and/or other materials provided with the
  13. // distribution.
  14. // * Neither the name of Google Inc. nor the names of its
  15. // contributors may be used to endorse or promote products derived from
  16. // this software without specific prior written permission.
  17. //
  18. // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21. // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22. // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23. // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24. // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25. // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26. // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27. // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28. // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29. package gax
  30. import (
  31. "fmt"
  32. "io"
  33. "strings"
  34. )
  35. // This parser follows the syntax of path templates, from
  36. // https://github.com/googleapis/googleapis/blob/master/google/api/http.proto.
  37. // The differences are that there is no custom verb, we allow the initial slash
  38. // to be absent, and that we are not strict as
  39. // https://tools.ietf.org/html/rfc6570 about the characters in identifiers and
  40. // literals.
  41. type pathTemplateParser struct {
  42. r *strings.Reader
  43. runeCount int // the number of the current rune in the original string
  44. nextVar int // the number to use for the next unnamed variable
  45. seenName map[string]bool // names we've seen already
  46. seenPathWildcard bool // have we seen "**" already?
  47. }
  48. func parsePathTemplate(template string) (pt *PathTemplate, err error) {
  49. p := &pathTemplateParser{
  50. r: strings.NewReader(template),
  51. seenName: map[string]bool{},
  52. }
  53. // Handle panics with strings like errors.
  54. // See pathTemplateParser.error, below.
  55. defer func() {
  56. if x := recover(); x != nil {
  57. errmsg, ok := x.(errString)
  58. if !ok {
  59. panic(x)
  60. }
  61. pt = nil
  62. err = ParseError{p.runeCount, template, string(errmsg)}
  63. }
  64. }()
  65. segs := p.template()
  66. // If there is a path wildcard, set its length. We can't do this
  67. // until we know how many segments we've got all together.
  68. for i, seg := range segs {
  69. if _, ok := seg.matcher.(pathWildcardMatcher); ok {
  70. segs[i].matcher = pathWildcardMatcher(len(segs) - i - 1)
  71. break
  72. }
  73. }
  74. return &PathTemplate{segments: segs}, nil
  75. }
  76. // Used to indicate errors "thrown" by this parser. We don't use string because
  77. // many parts of the standard library panic with strings.
  78. type errString string
  79. // Terminates parsing immediately with an error.
  80. func (p *pathTemplateParser) error(msg string) {
  81. panic(errString(msg))
  82. }
  83. // Template = [ "/" ] Segments
  84. func (p *pathTemplateParser) template() []segment {
  85. var segs []segment
  86. if p.consume('/') {
  87. // Initial '/' needs an initial empty matcher.
  88. segs = append(segs, segment{matcher: labelMatcher("")})
  89. }
  90. return append(segs, p.segments("")...)
  91. }
  92. // Segments = Segment { "/" Segment }
  93. func (p *pathTemplateParser) segments(name string) []segment {
  94. var segs []segment
  95. for {
  96. subsegs := p.segment(name)
  97. segs = append(segs, subsegs...)
  98. if !p.consume('/') {
  99. break
  100. }
  101. }
  102. return segs
  103. }
  104. // Segment = "*" | "**" | LITERAL | Variable
  105. func (p *pathTemplateParser) segment(name string) []segment {
  106. if p.consume('*') {
  107. if name == "" {
  108. name = fmt.Sprintf("$%d", p.nextVar)
  109. p.nextVar++
  110. }
  111. if p.consume('*') {
  112. if p.seenPathWildcard {
  113. p.error("multiple '**' disallowed")
  114. }
  115. p.seenPathWildcard = true
  116. // We'll change 0 to the right number at the end.
  117. return []segment{{name: name, matcher: pathWildcardMatcher(0)}}
  118. }
  119. return []segment{{name: name, matcher: wildcardMatcher(0)}}
  120. }
  121. if p.consume('{') {
  122. if name != "" {
  123. p.error("recursive named bindings are not allowed")
  124. }
  125. return p.variable()
  126. }
  127. return []segment{{name: name, matcher: labelMatcher(p.literal())}}
  128. }
  129. // Variable = "{" FieldPath [ "=" Segments ] "}"
  130. // "{" is already consumed.
  131. func (p *pathTemplateParser) variable() []segment {
  132. // Simplification: treat FieldPath as LITERAL, instead of IDENT { '.' IDENT }
  133. name := p.literal()
  134. if p.seenName[name] {
  135. p.error(name + " appears multiple times")
  136. }
  137. p.seenName[name] = true
  138. var segs []segment
  139. if p.consume('=') {
  140. segs = p.segments(name)
  141. } else {
  142. // "{var}" is equivalent to "{var=*}"
  143. segs = []segment{{name: name, matcher: wildcardMatcher(0)}}
  144. }
  145. if !p.consume('}') {
  146. p.error("expected '}'")
  147. }
  148. return segs
  149. }
  150. // A literal is any sequence of characters other than a few special ones.
  151. // The list of stop characters is not quite the same as in the template RFC.
  152. func (p *pathTemplateParser) literal() string {
  153. lit := p.consumeUntil("/*}{=")
  154. if lit == "" {
  155. p.error("empty literal")
  156. }
  157. return lit
  158. }
  159. // Read runes until EOF or one of the runes in stopRunes is encountered.
  160. // If the latter, unread the stop rune. Return the accumulated runes as a string.
  161. func (p *pathTemplateParser) consumeUntil(stopRunes string) string {
  162. var runes []rune
  163. for {
  164. r, ok := p.readRune()
  165. if !ok {
  166. break
  167. }
  168. if strings.IndexRune(stopRunes, r) >= 0 {
  169. p.unreadRune()
  170. break
  171. }
  172. runes = append(runes, r)
  173. }
  174. return string(runes)
  175. }
  176. // If the next rune is r, consume it and return true.
  177. // Otherwise, leave the input unchanged and return false.
  178. func (p *pathTemplateParser) consume(r rune) bool {
  179. rr, ok := p.readRune()
  180. if !ok {
  181. return false
  182. }
  183. if r == rr {
  184. return true
  185. }
  186. p.unreadRune()
  187. return false
  188. }
  189. // Read the next rune from the input. Return it.
  190. // The second return value is false at EOF.
  191. func (p *pathTemplateParser) readRune() (rune, bool) {
  192. r, _, err := p.r.ReadRune()
  193. if err == io.EOF {
  194. return r, false
  195. }
  196. if err != nil {
  197. p.error(err.Error())
  198. }
  199. p.runeCount++
  200. return r, true
  201. }
  202. // Put the last rune that was read back on the input.
  203. func (p *pathTemplateParser) unreadRune() {
  204. if err := p.r.UnreadRune(); err != nil {
  205. p.error(err.Error())
  206. }
  207. p.runeCount--
  208. }