JsonPath.java

  1. /***************************************************************************
  2.    Copyright 2014 Emily Estes

  4.    Licensed under the Apache License, Version 2.0 (the "License") { return this; }
  5.    you may not use this file except in compliance with the License.
  6.    You may obtain a copy of the License at

  8.        http://www.apache.org/licenses/LICENSE-2.0

  10.    Unless required by applicable law or agreed to in writing, software
  11.    distributed under the License is distributed on an "AS IS" BASIS,
  12.    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.    See the License for the specific language governing permissions and
  14.    limitations under the License.
  15. ***************************************************************************/
  16. package net.metanotion.json;


  19. import java.util.ArrayList;
  20. import java.util.List;

  22. import org.apache.commons.lang3.StringEscapeUtils;

  24. import net.metanotion.functor.Block;
  25. import net.metanotion.util.Pair;

  27. /** This class is meant to solve a similar problem to "XPath". The idea is to provide a handler implementation for a
  28. streaming parser that matches JS "expressions" to nodes in the JSON object being parsed, and then switches to a user
  29. provided handler for processing that subtree. For instance: "foo.bar[5]" would look for a key called "foo" whose value
  30. was an object, and then the key "bar" in inside foo's value, and assume bar's value was an array, and find the 5th
  31. element of that array, at which point it would pass control to the handler provided with that path expression.

  33. JsonPath "grammar":
  34.     <path> = <element> [ <subelement> ]*
  35.     <element> = <id> | '*' | <array> | '{}'
  36.     <subelement> = '.' ( <id> | '*') | <array>
  37.     <id> = [a-zA-Z_][anything]*
  38.     <array> = '[' [<int> | <string>] ']'

  40.     @param <T> The type parameter for the handler. This class always returns null from finish().
  41. */
  42. public final class JsonPath<T> implements Handler<T> {
  43.     private enum Token { ID, STAR, L_BRACE, R_BRACE, DOT, INT, STRING, L_CURLY, R_CURLY, EOF }
  44.     private static final class Lexeme {
  45.         public final Token type;
  46.         public final Object value;
  47.         public Lexeme(final Token type, final Object value) {
  48.             this.type = type;
  49.             this.value = value;
  50.         }
  51.         @Override public String toString() { return type.toString() + " - " + value; }
  52.     }
  53.     private static final Lexeme STAR = new Lexeme(Token.STAR, null);
  54.     private static final Lexeme L_BRACE = new Lexeme(Token.L_BRACE, null);
  55.     private static final Lexeme R_BRACE = new Lexeme(Token.R_BRACE, null);
  56.     private static final Lexeme L_CURLY = new Lexeme(Token.L_CURLY, null);
  57.     private static final Lexeme R_CURLY = new Lexeme(Token.R_CURLY, null);
  58.     private static final Lexeme DOT = new Lexeme(Token.DOT, null);
  59.     private static final Lexeme EOF = new Lexeme(Token.EOF, null);

  61.     private static Lexeme lexToken(final String cs, final int[] position) {
  62.         final int c = skipWhitespace(cs, position);
  63.         switch(c) {
  64.             case -1:
  65.                 return EOF;
  66.             case '[':
  67.                 return L_BRACE;
  68.             case ']':
  69.                 return R_BRACE;
  70.             case '{':
  71.                 return L_CURLY;
  72.             case '}':
  73.                 return R_CURLY;
  74.             case '*':
  75.                 return STAR;
  76.             case '.':
  77.                 return DOT;
  78.             case '\'':
  79.                 return lexString(cs, position);
  80.             default:
  81.                 if(Character.isDigit(c) || (c == (int) '-')) {
  82.                     // Lex integer
  83.                     final StringBuilder sb = new StringBuilder(new String(Character.toChars(c)));
  84.                     int digits = Character.isDigit(c) ? 1 : 0;
  85.                     while(true) {
  86.                         final int i = read(cs, position);
  87.                         if(Character.isDigit(i)) {
  88.                             digits++;
  89.                             sb.append(Character.toChars(i));
  90.                         } else {
  91.                             position[0]--;
  92.                             if(digits == 0) { throw new IllegalArgumentException("Expected at least one digit [0-9]"); }
  93.                             return new Lexeme(Token.INT, Long.valueOf(sb.toString()));
  94.                         }
  95.                     }
  96.                 } else {
  97.                     // Lex identifier
  98.                     position[0]--;
  99.                     final StringBuilder sb = new StringBuilder();
  100.                     while(true) {
  101.                         final int i = read(cs, position);
  102.                         if(i == -1) { return new Lexeme(Token.ID, sb.toString()); }
  103.                         if(Character.isLetter(i) || (i == (int) '_') || Character.isDigit(i)) {
  104.                             sb.append(Character.toChars(i));
  105.                         } else {
  106.                             position[0]--;
  107.                             return new Lexeme(Token.ID, sb.toString());
  108.                         }
  109.                     }
  110.                 }
  111.         }
  112.     }

  114.     private static int read(final String cs, final int[] position) {
  115.         try {
  116.             final int c = cs.codePointAt(position[0]);
  117.             position[0]++;
  118.             return c;
  119.         } catch (IndexOutOfBoundsException ioobe) {
  120.             return -1;
  121.         }
  122.     }

  124.     private static int skipWhitespace(final String cs, final int[] position) {
  125.         int c;
  126.         do {
  127.             c = read(cs, position);
  128.         } while(Character.isWhitespace((char) c));
  129.         return c;
  130.     }

  132.     private static Lexeme lexString(final String cs, final int[] position) {
  133.         final StringBuilder sb = new StringBuilder();
  134.         boolean escape = false;
  135.         while(true) {
  136.             final int c = read(cs, position);
  137.             if(c == -1) { throw new IllegalArgumentException("unexpected end of expression in string"); }
  138.             final String cbuf = new String(Character.toChars(c));
  139.             if(("\'".equals(cbuf)) && !escape) {
  140.                 return new Lexeme(Token.STRING, StringEscapeUtils.unescapeJson(sb.toString()));
  141.             } else if ("\\".equals(cbuf)) {
  142.                 escape = true;
  143.                 sb.append(cbuf);
  144.             } else {
  145.                 escape = false;
  146.                 sb.append(cbuf);
  147.             }
  148.         }
  149.     }



  153.     private enum Type { STAR, KEY, LIST, OBJ }
  154.     private static final class Path {
  155.         public final Type type;
  156.         public Object value;
  157.         public Path(final Type type, final Object value) {
  158.             this.type = type;
  159.             this.value = value;
  160.         }
  161.     }
  162.     private static final Path P_STAR = new Path(Type.STAR, null);
  163.     private static final Path P_OBJ = new Path(Type.OBJ, null);
  164.     private static final Path P_KEY = new Path(Type.KEY, null);

  166.     private static List<Path> parseElement(final String expression, final int[] pos, final List<Path> list) {
  167.         Lexeme lex = lexToken(expression, pos);
  168.         switch(lex.type) {
  169.             case EOF:
  170.                 return list;
  171.             case DOT:
  172.                 lex = lexToken(expression, pos);
  173.                 if(lex.type != Token.ID) {
  174.                     throw new IllegalArgumentException("Expected identifier after the '.', instead found: "
  175.                         + lex);
  176.                 }
  177.                 list.add(P_OBJ);
  178.                 list.add(new Path(Type.KEY, lex.value));
  179.                 return parseElement(expression, pos, list);
  180.             case L_BRACE:
  181.                 return parseIndex(expression, pos, list);
  182.             case L_CURLY:
  183.                 return parseCurly(expression, pos, list);
  184.             default:
  185.                 throw new IllegalArgumentException("Expression is not a valid JSON path, expected ID, '[', or eof, found: "
  186.                     + lex.toString());
  187.         }
  188.     }

  190.     private static List<Path> parseIndex(final String expression, final int[] pos, final List<Path> list) {
  191.         Lexeme lex = lexToken(expression, pos);
  192.         switch(lex.type) {
  193.             case STRING:
  194.                 list.add(P_OBJ);
  195.                 list.add(new Path(Type.KEY, lex.value));
  196.                 break;
  197.             case INT:
  198.                 list.add(new Path(Type.LIST, lex.value));
  199.                 break;
  200.             case R_BRACE:
  201.                 list.add(new Path(Type.LIST, null));
  202.                 return parseElement(expression, pos, list);
  203.             default:
  204.                 throw new IllegalArgumentException("Expression is not a valid JSON path, "
  205.                     + "expected a string or integer index in [], found: " + lex.toString());
  206.         }
  207.         lex = lexToken(expression, pos);
  208.         if(lex.type != Token.R_BRACE) {
  209.             throw new IllegalArgumentException("Expression is not a valid JSON path, expected a ']', found: " + lex.toString());
  210.         }
  211.         return parseElement(expression, pos, list);
  212.     }

  214.     private static List<Path> parseCurly(final String expression, final int[] pos, final List<Path> list) {
  215.         final Lexeme lex = lexToken(expression, pos);
  216.         if(lex.type != Token.R_CURLY) { throw new IllegalArgumentException("Expression is not a valid JSON Path, "
  217.             + "expected }, found:" + lex.toString());
  218.         }
  219.         list.add(P_OBJ);
  220.         list.add(P_KEY);
  221.         return parseElement(expression, pos, list);
  222.     }

  224.     private static List<Path> parse(final String expression) {
  225.         final ArrayList<Path> list = new ArrayList<>();
  226.         final int[] pos = { 0 };
  227.         final Lexeme lex = lexToken(expression, pos);
  228.         switch(lex.type) {
  229.             case STAR:
  230.                 list.add(P_STAR);
  231.                 return parseElement(expression, pos, list);
  232.             case ID:
  233.                 list.add(P_OBJ);
  234.                 list.add(new Path(Type.KEY, lex.value));
  235.                 return parseElement(expression, pos, list);
  236.             case L_BRACE:
  237.                 return parseIndex(expression, pos, list);
  238.             case L_CURLY:
  239.                 return parseCurly(expression, pos, list);
  240.             default:
  241.                 throw new IllegalArgumentException("Expression is not a valid JSON Path.");
  242.         }
  243.     }


  246.     private final List<Pair<List<Path>,Block<Object,? extends Object>>> matches = new ArrayList<>();
  247.     private final ArrayList<Path> current = new ArrayList<>();
  248.     private final List<Handler<T>> accumulators = new ArrayList<>();
  249.     private final ArrayList<String> currentKey = new ArrayList<>();

  251.     // compare the path to current.
  252.     private boolean compare(final List<Path> path) {
  253.         int index = 0;
  254.         final int len = path.size();
  255.         for(final Path c: current) {
  256.             if(index >= len) { return false; }
  257.             final Path p = path.get(index);
  258.             index++;
  259.             if(p.type != c.type) { return false; }
  260.             switch(p.type) {
  261.                 case LIST:
  262.                     if((p.value != null) && (!c.value.equals(p.value))) { return false; }
  263.                     break;
  264.                 case KEY:
  265.                     if((p.value != null) && (!c.value.equals(p.value))) { return false; }
  266.                     break;
  267.                 default:
  268.                     break;
  269.             }
  270.         }
  271.         return index == len;
  272.     }

  274.     private static final class Accumulator<T> implements Handler<T>, Continuation<Object,T> {
  275.         private final List<Handler<T>> accumulators;
  276.         private final List<String> currentKey;
  277.         private final List<Path> match;
  278.         private final Block<Object, ? extends Object> block;

  280.         public Accumulator(final List<String> currentKey,
  281.                 final List<Handler<T>> accumulators,
  282.                 final List<Path> match,
  283.                 final Block<Object, ? extends Object> block) {
  284.             this.currentKey = currentKey;
  285.             this.accumulators = accumulators;
  286.             this.match = match;
  287.             this.block = block;
  288.         }

  290.         @Override public Handler<T> resume(Object val) {
  291.             try {
  292.                 final Path p = match.get(match.size() - 1);
  293.                 if ((p.type == Type.KEY) && (p.value == null)) {
  294.                     final String k = currentKey.get(currentKey.size() - 1);
  295.                     val = new Pair<String,Object>(k, val);
  296.                 }
  297.                 block.eval(val);
  298.             } catch (final Exception e) { throw new RuntimeException(e); }
  299.             accumulators.remove(this);
  300.             return null;
  301.         }

  303.         @Override public Handler<T> start() { return this; }
  304.         @Override public T finish() { return null; }
  305.         @Override public Handler<T> startObject() { return new ObjectReader<T>(this); }
  306.         @Override public Handler<T> key(final String key) {
  307.             throw new RuntimeException("Unexpected Json token, was expecting a value, got a key.");
  308.         }
  309.         @Override public Handler<T> endObject() { return null; }
  310.         @Override public Handler<T> startList() { return new ListReader<T>(this); }
  311.         @Override public Handler<T> endList() { return null; }
  312.         @Override public Handler<T> integer(final Long value) { return this.resume(value); }
  313.         @Override public Handler<T> decimal(final Double value) { return this.resume(value); }
  314.         @Override public Handler<T> string(final String value) { return this.resume(value); }
  315.         @Override public Handler<T> bool(final boolean value) { return this.resume(value); }
  316.         @Override public Handler<T> jsonNull() { return this.resume(null); }
  317.     }

  319.     private void findMatch() {
  320.         for(final Pair<List<Path>,Block<Object,? extends Object>> candidate: matches) {
  321.             final List<Path> path = candidate.getKey();
  322.             if(compare(path)) {
  323.                 accumulators.add(new Accumulator<T>(currentKey, accumulators, path, candidate.getValue()));
  324.             }
  325.         }
  326.     }

  328.     /** Add a Path expression to this instance. Every time the path is matched, the iterator will be evaluated with the
  329.     accumulated value of the nodes beneath the match. Only one match can be active at a time, so given two expressions
  330.     that would match, the one added first "wins".
  331.         @param expression A valid JSON path expression to match.
  332.         @param iterator Block to evaluate against the accumulated child nodes(this must not be null).
  333.         @return This instance of JsonPath.
  334.         @throws IllegalArgumentException if the expression is not well formed.
  335.         @throws NullPointerException if iterator is null.
  336.     */
  337.     public JsonPath<T> add(final String expression, final Block<Object, ? extends Object> iterator) {
  338.         if(iterator == null) { throw new NullPointerException("block must not be null."); }
  339.         final List<Path> expr = parse(expression);
  340.         matches.add(new Pair<List<Path>,Block<Object,? extends Object>>(expr, iterator));
  341.         return this;
  342.     }

  344.     @Override public Handler<T> start() {
  345.         current.clear();
  346.         currentKey.clear();
  347.         accumulators.clear();
  348.         return this;
  349.     }

  351.     @Override public T finish() {
  352.         if(current.size() > 0) { throw new RuntimeException("JSON not well formed."); }
  353.         return null;
  354.     }

  356.     @Override public Handler<T> startObject() {
  357.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  358.         for(int i=0; i < accs.length; i++) {
  359.             accs[i] = accs[i].startObject();
  360.         }
  361.         accumulators.clear();
  362.         for(final Handler a: accs) {
  363.             if(a != null) { accumulators.add(a); }
  364.         }
  365.         currentKey.add(null);
  366.         current.add(new Path(Type.OBJ, null));
  367.         return this;
  368.     }

  370.     @Override public Handler<T> key(final String key) {
  371.         currentKey.set(currentKey.size() - 1, key);
  372.         current.add(new Path(Type.KEY, key));
  373.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  374.         for(int i=0; i < accs.length; i++) {
  375.             accs[i] = accs[i].key(key);
  376.         }
  377.         accumulators.clear();
  378.         for(final Handler a: accs) {
  379.             if(a != null) { accumulators.add(a); }
  380.         }
  381.         findMatch();
  382.         return this;
  383.     }

  385.     private Path pop() { return current.remove(current.size() - 1); }

  387.     private void closeValue() {
  388.         final int len = current.size();
  389.         if(len > 0) {
  390.             final Path p = current.get(len - 1);
  391.             if(p.type == Type.KEY) {
  392.                 pop();
  393.             } else if(p.type == Type.LIST) {
  394.                 p.value = ((Long) p.value).longValue() + 1;
  395.             }
  396.         }
  397.     }

  399.     @Override public Handler<T> endObject() {
  400.         currentKey.remove(currentKey.size() - 1);
  401.         final Path p = pop();
  402.         if(p.type != Type.OBJ) { throw new RuntimeException("Invalid end of object"); }
  403.         closeValue();
  404.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  405.         for(int i=0; i < accs.length; i++) {
  406.             accs[i] = accs[i].endObject();
  407.         }
  408.         accumulators.clear();
  409.         for(final Handler a: accs) {
  410.             if(a != null) { accumulators.add(a); }
  411.         }
  412.         findMatch();
  413.         return this;
  414.     }

  416.     @Override public Handler<T> startList() {
  417.         current.add(new Path(Type.LIST, Long.valueOf(0)));
  418.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  419.         for(int i=0; i < accs.length; i++) {
  420.             accs[i] = accs[i].startList();
  421.         }
  422.         accumulators.clear();
  423.         for(final Handler a: accs) {
  424.             if(a != null) { accumulators.add(a); }
  425.         }
  426.         findMatch();
  427.         return this;
  428.     }

  430.     @Override public Handler<T> endList() {
  431.         final Path p = pop();
  432.         if(p.type != Type.LIST) { throw new RuntimeException("Invalid end of list"); }
  433.         closeValue();
  434.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  435.         for(int i=0; i < accs.length; i++) {
  436.             accs[i] = accs[i].endList();
  437.         }
  438.         accumulators.clear();
  439.         for(final Handler a: accs) {
  440.             if(a != null) { accumulators.add(a); }
  441.         }
  442.         findMatch();
  443.         return this;
  444.     }

  446.     @Override public Handler<T> integer(final Long val) {
  447.         closeValue();
  448.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  449.         for(int i=0; i < accs.length; i++) {
  450.             accs[i] = accs[i].integer(val);
  451.         }
  452.         accumulators.clear();
  453.         for(final Handler a: accs) {
  454.             if(a != null) { accumulators.add(a); }
  455.         }
  456.         findMatch();
  457.         return this;
  458.     }

  460.     @Override public Handler<T> decimal(final Double val) {
  461.         closeValue();
  462.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  463.         for(int i=0; i < accs.length; i++) {
  464.             accs[i] = accs[i].decimal(val);
  465.         }
  466.         accumulators.clear();
  467.         for(final Handler a: accs) {
  468.             if(a != null) { accumulators.add(a); }
  469.         }
  470.         findMatch();
  471.         return this;
  472.     }

  474.     @Override public Handler<T> string(final String val) {
  475.         closeValue();
  476.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  477.         for(int i=0; i < accs.length; i++) {
  478.             accs[i] = accs[i].string(val);
  479.         }
  480.         accumulators.clear();
  481.         for(final Handler a: accs) {
  482.             if(a != null) { accumulators.add(a); }
  483.         }
  484.         findMatch();
  485.         return this;
  486.     }

  488.     @Override public Handler<T> bool(final boolean val) {
  489.         closeValue();
  490.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  491.         for(int i=0; i < accs.length; i++) {
  492.             accs[i] = accs[i].bool(val);
  493.         }
  494.         accumulators.clear();
  495.         for(final Handler a: accs) {
  496.             if(a != null) { accumulators.add(a); }
  497.         }
  498.         findMatch();
  499.         return this;
  500.     }

  502.     @Override public Handler<T> jsonNull() {
  503.         closeValue();
  504.         final Handler[] accs = accumulators.toArray(new Handler[accumulators.size()]);
  505.         for(int i=0; i < accs.length; i++) {
  506.             accs[i] = accs[i].jsonNull();
  507.         }
  508.         accumulators.clear();
  509.         for(final Handler a: accs) {
  510.             if(a != null) { accumulators.add(a); }
  511.         }
  512.         findMatch();
  513.         return this;
  514.     }
  515. }
Created with JaCoCo 0.7.5.201505241946