jsonpath.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569
  1. // Package jsonpath implements Stefan Goener's JSONPath http://goessner.net/articles/JsonPath/
  2. //
  3. // A jsonpath applies to any JSON decoded data using interface{} when
  4. // decoded with encoding/json (http://golang.org/pkg/encoding/json/) :
  5. //
  6. // var bookstore interface{}
  7. // err := json.Unmarshal(data, &bookstore)
  8. // authors, err := jsonpath.Read(bookstore, "$..authors")
  9. //
  10. // A jsonpath expression can be prepared to be reused multiple times :
  11. //
  12. // allAuthors, err := jsonpath.Prepare("$..authors")
  13. // ...
  14. // var bookstore interface{}
  15. // err = json.Unmarshal(data, &bookstore)
  16. // authors, err := allAuthors(bookstore)
  17. //
  18. // The type of the values returned by the `Read` method or `Prepare`
  19. // functions depends on the jsonpath expression.
  20. //
  21. // Limitations
  22. //
  23. // No support for subexpressions and filters.
  24. // Strings in brackets must use double quotes.
  25. // It cannot operate on JSON decoded struct fields.
  26. //
  27. package jsonpath
  28. import (
  29. "errors"
  30. "fmt"
  31. "sort"
  32. "strconv"
  33. "strings"
  34. "text/scanner"
  35. )
  36. // Read a path from a decoded JSON array or object ([]interface{} or map[string]interface{})
  37. // and returns the corresponding value or an error.
  38. //
  39. // The returned value type depends on the requested path and the JSON value.
  40. func Read(value interface{}, path string) (interface{}, error) {
  41. filter, err := Prepare(path)
  42. if err != nil {
  43. return nil, err
  44. }
  45. return filter(value)
  46. }
  47. // Prepare will parse the path and return a filter function that can then be applied to decoded JSON values.
  48. func Prepare(path string) (FilterFunc, error) {
  49. p := newScanner(path)
  50. if err := p.parse(); err != nil {
  51. return nil, err
  52. }
  53. return p.prepareFilterFunc(), nil
  54. }
  55. // FilterFunc applies a prepared json path to a JSON decoded value
  56. type FilterFunc func(value interface{}) (interface{}, error)
  57. // short variables
  58. // p: the parser context
  59. // r: root node => @
  60. // c: current node => $
  61. // a: the list of actions to apply next
  62. // v: value
  63. // actionFunc applies a transformation to current value (possibility using root)
  64. // then applies the next action from actions (using next()) to the output of the transformation
  65. type actionFunc func(r, c interface{}, a actions) (interface{}, error)
  66. // a list of action functions to apply one after the other
  67. type actions []actionFunc
  68. // next applies the next action function
  69. func (a actions) next(r, c interface{}) (interface{}, error) {
  70. return a[0](r, c, a[1:])
  71. }
  72. // call applies the next action function without taking it out
  73. func (a actions) call(r, c interface{}) (interface{}, error) {
  74. return a[0](r, c, a)
  75. }
  76. type exprFunc func(r, c interface{}) (interface{}, error)
  77. type searchResults []interface{}
  78. func (sr searchResults) append(v interface{}) searchResults {
  79. if vsr, ok := v.(searchResults); ok {
  80. return append(sr, vsr...)
  81. }
  82. return append(sr, v)
  83. }
  84. type parser struct {
  85. scanner scanner.Scanner
  86. path string
  87. actions actions
  88. }
  89. func (p *parser) prepareFilterFunc() FilterFunc {
  90. actions := p.actions
  91. return func(value interface{}) (interface{}, error) {
  92. result, err := actions.next(value, value)
  93. if err == nil {
  94. if sr, ok := result.(searchResults); ok {
  95. result = ([]interface{})(sr)
  96. }
  97. }
  98. return result, err
  99. }
  100. }
  101. func newScanner(path string) *parser {
  102. return &parser{path: path}
  103. }
  104. func (p *parser) scan() rune {
  105. return p.scanner.Scan()
  106. }
  107. func (p *parser) text() string {
  108. return p.scanner.TokenText()
  109. }
  110. func (p *parser) column() int {
  111. return p.scanner.Position.Column
  112. }
  113. func (p *parser) peek() rune {
  114. return p.scanner.Peek()
  115. }
  116. func (p *parser) add(action actionFunc) {
  117. p.actions = append(p.actions, action)
  118. }
  119. func (p *parser) parse() error {
  120. p.scanner.Init(strings.NewReader(p.path))
  121. if p.scan() != '$' {
  122. return errors.New("path must start with a '$'")
  123. }
  124. return p.parsePath()
  125. }
  126. func (p *parser) parsePath() (err error) {
  127. for err == nil {
  128. switch p.scan() {
  129. case '.':
  130. p.scanner.Mode = scanner.ScanIdents
  131. switch p.scan() {
  132. case scanner.Ident:
  133. err = p.parseObjAccess()
  134. case '*':
  135. err = p.prepareWildcard()
  136. case '.':
  137. err = p.parseDeep()
  138. default:
  139. err = fmt.Errorf("expected JSON child identifier after '.' at %d", p.column())
  140. }
  141. case '[':
  142. err = p.parseBracket()
  143. case scanner.EOF:
  144. // the end, add a last func that just return current node
  145. p.add(func(r, c interface{}, a actions) (interface{}, error) { return c, nil })
  146. return nil
  147. default:
  148. err = fmt.Errorf("unexpected token %s at %d", p.text(), p.column())
  149. }
  150. }
  151. return
  152. }
  153. func (p *parser) parseObjAccess() error {
  154. ident := p.text()
  155. column := p.scanner.Position.Column
  156. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  157. obj, ok := c.(map[string]interface{})
  158. if !ok {
  159. return nil, fmt.Errorf("expected JSON object to access child '%s' at %d", ident, column)
  160. }
  161. if c, ok = obj[ident]; !ok {
  162. return nil, fmt.Errorf("child '%s' not found in JSON object at %d", ident, column)
  163. }
  164. return a.next(r, c)
  165. })
  166. return nil
  167. }
  168. func (p *parser) prepareWildcard() error {
  169. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  170. values := searchResults{}
  171. if obj, ok := c.(map[string]interface{}); ok {
  172. for _, v := range valuesSortedByKey(obj) {
  173. v, err := a.next(r, v)
  174. if err != nil {
  175. continue
  176. }
  177. values = values.append(v)
  178. }
  179. } else if array, ok := c.([]interface{}); ok {
  180. for _, v := range array {
  181. v, err := a.next(r, v)
  182. if err != nil {
  183. continue
  184. }
  185. values = values.append(v)
  186. }
  187. }
  188. return values, nil
  189. })
  190. return nil
  191. }
  192. func (p *parser) parseDeep() (err error) {
  193. p.scanner.Mode = scanner.ScanIdents
  194. switch p.scan() {
  195. case scanner.Ident:
  196. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  197. return recSearchParent(r, c, a, searchResults{}), nil
  198. })
  199. return p.parseObjAccess()
  200. case '[':
  201. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  202. return recSearchParent(r, c, a, searchResults{}), nil
  203. })
  204. return p.parseBracket()
  205. case '*':
  206. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  207. return recSearchChildren(r, c, a, searchResults{}), nil
  208. })
  209. p.add(func(r, c interface{}, a actions) (interface{}, error) {
  210. return a.next(r, c)
  211. })
  212. return nil
  213. case scanner.EOF:
  214. return fmt.Errorf("cannot end with a scan '..' at %d", p.column())
  215. default:
  216. return fmt.Errorf("unexpected token '%s' after deep search '..' at %d",
  217. p.text(), p.column())
  218. }
  219. }
  220. // bracket contains filter, wildcard or array access
  221. func (p *parser) parseBracket() error {
  222. if p.peek() == '?' {
  223. return p.parseFilter()
  224. } else if p.peek() == '*' {
  225. p.scan() // eat *
  226. if p.scan() != ']' {
  227. return fmt.Errorf("expected closing bracket after [* at %d", p.column())
  228. }
  229. return p.prepareWildcard()
  230. }
  231. return p.parseArray()
  232. }
  233. // array contains either a union [,,,], a slice [::] or a single element.
  234. // Each element can be an int, a string or an expression.
  235. // TODO optimize map/array access (by detecting the type of indexes)
  236. func (p *parser) parseArray() error {
  237. var indexes []interface{} // string, int or exprFunc
  238. var mode string // slice or union
  239. p.scanner.Mode = scanner.ScanIdents | scanner.ScanStrings | scanner.ScanInts
  240. parse:
  241. for {
  242. // parse value
  243. switch p.scan() {
  244. case scanner.Int:
  245. index, err := strconv.Atoi(p.text())
  246. if err != nil {
  247. return fmt.Errorf("%s at %d", err.Error(), p.column())
  248. }
  249. indexes = append(indexes, index)
  250. case '-':
  251. if p.scan() != scanner.Int {
  252. return fmt.Errorf("expect an int after the minus '-' sign at %d", p.column())
  253. }
  254. index, err := strconv.Atoi(p.text())
  255. if err != nil {
  256. return fmt.Errorf("%s at %d", err.Error(), p.column())
  257. }
  258. indexes = append(indexes, -index)
  259. case scanner.Ident:
  260. indexes = append(indexes, p.text())
  261. case scanner.String:
  262. s, err := strconv.Unquote(p.text())
  263. if err != nil {
  264. return fmt.Errorf("bad string %s at %d", err, p.column())
  265. }
  266. indexes = append(indexes, s)
  267. case '(':
  268. filter, err := p.parseExpression()
  269. if err != nil {
  270. return err
  271. }
  272. indexes = append(indexes, filter)
  273. case ':': // when slice value is omitted
  274. if mode == "" {
  275. mode = "slice"
  276. indexes = append(indexes, 0)
  277. } else if mode == "slice" {
  278. indexes = append(indexes, 0)
  279. } else {
  280. return fmt.Errorf("unexpected ':' after %s at %d", mode, p.column())
  281. }
  282. continue // skip separator parsing, it's done
  283. case ']': // when slice value is omitted
  284. if mode == "slice" {
  285. indexes = append(indexes, 0)
  286. } else if len(indexes) == 0 {
  287. return fmt.Errorf("expected at least one key, index or expression at %d", p.column())
  288. }
  289. break parse
  290. case scanner.EOF:
  291. return fmt.Errorf("unexpected end of path at %d", p.column())
  292. default:
  293. return fmt.Errorf("unexpected token '%s' at %d", p.text(), p.column())
  294. }
  295. // parse separator
  296. switch p.scan() {
  297. case ',':
  298. if mode == "" {
  299. mode = "union"
  300. } else if mode != "union" {
  301. return fmt.Errorf("unexpeted ',' in %s at %d", mode, p.column())
  302. }
  303. case ':':
  304. if mode == "" {
  305. mode = "slice"
  306. } else if mode != "slice" {
  307. return fmt.Errorf("unexpected ':' in %s at %d", mode, p.column())
  308. }
  309. case ']':
  310. break parse
  311. case scanner.EOF:
  312. return fmt.Errorf("unexpected end of path at %d", p.column())
  313. default:
  314. return fmt.Errorf("unexpected token '%s' at %d", p.text(), p.column())
  315. }
  316. }
  317. if mode == "slice" {
  318. if len(indexes) > 3 {
  319. return fmt.Errorf("bad range syntax [start:end:step] at %d", p.column())
  320. }
  321. p.add(prepareSlice(indexes, p.column()))
  322. } else if len(indexes) == 1 {
  323. p.add(prepareIndex(indexes[0], p.column()))
  324. } else {
  325. p.add(prepareUnion(indexes, p.column()))
  326. }
  327. return nil
  328. }
  329. func (p *parser) parseFilter() error {
  330. return errors.New("Filters are not (yet) implemented")
  331. }
  332. func (p *parser) parseExpression() (exprFunc, error) {
  333. return nil, errors.New("Expression are not (yet) implemented")
  334. }
  335. func recSearchParent(r, c interface{}, a actions, acc searchResults) searchResults {
  336. if v, err := a.next(r, c); err == nil {
  337. acc = acc.append(v)
  338. }
  339. return recSearchChildren(r, c, a, acc)
  340. }
  341. func recSearchChildren(r, c interface{}, a actions, acc searchResults) searchResults {
  342. if obj, ok := c.(map[string]interface{}); ok {
  343. for _, c := range valuesSortedByKey(obj) {
  344. acc = recSearchParent(r, c, a, acc)
  345. }
  346. } else if array, ok := c.([]interface{}); ok {
  347. for _, c := range array {
  348. acc = recSearchParent(r, c, a, acc)
  349. }
  350. }
  351. return acc
  352. }
  353. func prepareIndex(index interface{}, column int) actionFunc {
  354. return func(r, c interface{}, a actions) (interface{}, error) {
  355. if obj, ok := c.(map[string]interface{}); ok {
  356. key, err := indexAsString(index, r, c)
  357. if err != nil {
  358. return nil, err
  359. }
  360. if c, ok = obj[key]; !ok {
  361. return nil, fmt.Errorf("no key '%s' for object at %d", key, column)
  362. }
  363. return a.next(r, c)
  364. } else if array, ok := c.([]interface{}); ok {
  365. index, err := indexAsInt(index, r, c)
  366. if err != nil {
  367. return nil, err
  368. }
  369. if index < 0 || index >= len(array) {
  370. return nil, fmt.Errorf("out of bound array access at %d", column)
  371. }
  372. return a.next(r, array[index])
  373. }
  374. return nil, fmt.Errorf("expected array or object at %d", column)
  375. }
  376. }
  377. func prepareSlice(indexes []interface{}, column int) actionFunc {
  378. return func(r, c interface{}, a actions) (interface{}, error) {
  379. array, ok := c.([]interface{})
  380. if !ok {
  381. return nil, fmt.Errorf("expected JSON array at %d", column)
  382. }
  383. var err error
  384. var start, end, step int
  385. if start, err = indexAsInt(indexes[0], r, c); err != nil {
  386. return nil, err
  387. }
  388. if end, err = indexAsInt(indexes[1], r, c); err != nil {
  389. return nil, err
  390. }
  391. if len(indexes) > 2 {
  392. if step, err = indexAsInt(indexes[2], r, c); err != nil {
  393. return nil, err
  394. }
  395. }
  396. max := len(array)
  397. start = negmax(start, max)
  398. if end == 0 {
  399. end = max
  400. } else {
  401. end = negmax(end, max)
  402. }
  403. if start > end {
  404. return nil, fmt.Errorf("cannot start range at %d and end at %d", start, end)
  405. }
  406. if step == 0 {
  407. step = 1
  408. }
  409. var values searchResults
  410. if step > 0 {
  411. for i := start; i < end; i += step {
  412. v, err := a.next(r, array[i])
  413. if err != nil {
  414. continue
  415. }
  416. values = values.append(v)
  417. }
  418. } else { // reverse order on negative step
  419. for i := end - 1; i >= start; i += step {
  420. v, err := a.next(r, array[i])
  421. if err != nil {
  422. continue
  423. }
  424. values = values.append(v)
  425. }
  426. }
  427. return values, nil
  428. }
  429. }
  430. func prepareUnion(indexes []interface{}, column int) actionFunc {
  431. return func(r, c interface{}, a actions) (interface{}, error) {
  432. if obj, ok := c.(map[string]interface{}); ok {
  433. var values searchResults
  434. for _, index := range indexes {
  435. key, err := indexAsString(index, r, c)
  436. if err != nil {
  437. return nil, err
  438. }
  439. if c, ok = obj[key]; !ok {
  440. return nil, fmt.Errorf("no key '%s' for object at %d", key, column)
  441. }
  442. if c, err = a.next(r, c); err != nil {
  443. return nil, err
  444. }
  445. values = values.append(c)
  446. }
  447. return values, nil
  448. } else if array, ok := c.([]interface{}); ok {
  449. var values searchResults
  450. for _, index := range indexes {
  451. index, err := indexAsInt(index, r, c)
  452. if err != nil {
  453. return nil, err
  454. }
  455. if index < 0 || index >= len(array) {
  456. return nil, fmt.Errorf("out of bound array access at %d", column)
  457. }
  458. if c, err = a.next(r, array[index]); err != nil {
  459. return nil, err
  460. }
  461. values = values.append(c)
  462. }
  463. return values, nil
  464. }
  465. return nil, fmt.Errorf("expected array or object at %d", column)
  466. }
  467. }
  468. func negmax(n, max int) int {
  469. if n < 0 {
  470. n = max + n
  471. if n < 0 {
  472. n = 0
  473. }
  474. } else if n > max {
  475. return max
  476. }
  477. return n
  478. }
  479. func indexAsInt(index, r, c interface{}) (int, error) {
  480. switch i := index.(type) {
  481. case int:
  482. return i, nil
  483. case exprFunc:
  484. index, err := i(r, c)
  485. if err != nil {
  486. return 0, err
  487. }
  488. switch i := index.(type) {
  489. case int:
  490. return i, nil
  491. default:
  492. return 0, fmt.Errorf("expected expression to return an index for array access")
  493. }
  494. default:
  495. return 0, fmt.Errorf("expected index value (integer or expression returning an integer) for array access")
  496. }
  497. }
  498. func indexAsString(key, r, c interface{}) (string, error) {
  499. switch s := key.(type) {
  500. case string:
  501. return s, nil
  502. case exprFunc:
  503. key, err := s(r, c)
  504. if err != nil {
  505. return "", err
  506. }
  507. switch s := key.(type) {
  508. case string:
  509. return s, nil
  510. default:
  511. return "", fmt.Errorf("expected expression to return a key for object access")
  512. }
  513. default:
  514. return "", fmt.Errorf("expected key value (string or expression returning a string) for object access")
  515. }
  516. }
  517. func valuesSortedByKey(m map[string]interface{}) []interface{} {
  518. if len(m) == 0 {
  519. return nil
  520. }
  521. keys := make([]string, 0, len(m))
  522. for k := range m {
  523. keys = append(keys, k)
  524. }
  525. sort.Strings(keys)
  526. values := make([]interface{}, 0, len(m))
  527. for _, k := range keys {
  528. values = append(values, m[k])
  529. }
  530. return values
  531. }