1  (function(exports) {
   2    "use strict";
   3  
   4    function isArray(obj) {
   5      if (obj !== null) {
   6        return Object.prototype.toString.call(obj) === "[object Array]";
   7      } else {
   8        return false;
   9      }
  10    }
  11  
  12    function isObject(obj) {
  13      if (obj !== null) {
  14        return Object.prototype.toString.call(obj) === "[object Object]";
  15      } else {
  16        return false;
  17      }
  18    }
  19  
  20    function strictDeepEqual(first, second) {
  21      // Check the scalar case first.
  22      if (first === second) {
  23        return true;
  24      }
  25  
  26      // Check if they are the same type.
  27      var firstType = Object.prototype.toString.call(first);
  28      if (firstType !== Object.prototype.toString.call(second)) {
  29        return false;
  30      }
  31      // We know that first and second have the same type so we can just check the
  32      // first type from now on.
  33      if (isArray(first) === true) {
  34        // Short circuit if they're not the same length;
  35        if (first.length !== second.length) {
  36          return false;
  37        }
  38        for (var i = 0; i < first.length; i++) {
  39          if (strictDeepEqual(first[i], second[i]) === false) {
  40            return false;
  41          }
  42        }
  43        return true;
  44      }
  45      if (isObject(first) === true) {
  46        // An object is equal if it has the same key/value pairs.
  47        var keysSeen = {};
  48        for (var key in first) {
  49          if (hasOwnProperty.call(first, key)) {
  50            if (strictDeepEqual(first[key], second[key]) === false) {
  51              return false;
  52            }
  53            keysSeen[key] = true;
  54          }
  55        }
  56        // Now check that there aren't any keys in second that weren't
  57        // in first.
  58        for (var key2 in second) {
  59          if (hasOwnProperty.call(second, key2)) {
  60            if (keysSeen[key2] !== true) {
  61              return false;
  62            }
  63          }
  64        }
  65        return true;
  66      }
  67      return false;
  68    }
  69  
  70    function isFalse(obj) {
  71      // From the spec:
  72      // A false value corresponds to the following values:
  73      // Empty list
  74      // Empty object
  75      // Empty string
  76      // False boolean
  77      // null value
  78  
  79      // First check the scalar values.
  80      if (obj === "" || obj === false || obj === null) {
  81          return true;
  82      } else if (isArray(obj) && obj.length === 0) {
  83          // Check for an empty array.
  84          return true;
  85      } else if (isObject(obj)) {
  86          // Check for an empty object.
  87          for (var key in obj) {
  88              // If there are any keys, then
  89              // the object is not empty so the object
  90              // is not false.
  91              if (obj.hasOwnProperty(key)) {
  92                return false;
  93              }
  94          }
  95          return true;
  96      } else {
  97          return false;
  98      }
  99    }
 100  
 101    function objValues(obj) {
 102      var keys = Object.keys(obj);
 103      var values = [];
 104      for (var i = 0; i < keys.length; i++) {
 105        values.push(obj[keys[i]]);
 106      }
 107      return values;
 108    }
 109  
 110    function merge(a, b) {
 111        var merged = {};
 112        for (var key in a) {
 113            merged[key] = a[key];
 114        }
 115        for (var key2 in b) {
 116            merged[key2] = b[key2];
 117        }
 118        return merged;
 119    }
 120  
 121    var trimLeft;
 122    if (typeof String.prototype.trimLeft === "function") {
 123      trimLeft = function(str) {
 124        return str.trimLeft();
 125      };
 126    } else {
 127      trimLeft = function(str) {
 128        return str.match(/^\s*(.*)/)[1];
 129      };
 130    }
 131  
 132    // Type constants used to define functions.
 133    var TYPE_NUMBER = 0;
 134    var TYPE_ANY = 1;
 135    var TYPE_STRING = 2;
 136    var TYPE_ARRAY = 3;
 137    var TYPE_OBJECT = 4;
 138    var TYPE_BOOLEAN = 5;
 139    var TYPE_EXPREF = 6;
 140    var TYPE_NULL = 7;
 141    var TYPE_ARRAY_NUMBER = 8;
 142    var TYPE_ARRAY_STRING = 9;
 143  
 144    var TOK_EOF = "EOF";
 145    var TOK_UNQUOTEDIDENTIFIER = "UnquotedIdentifier";
 146    var TOK_QUOTEDIDENTIFIER = "QuotedIdentifier";
 147    var TOK_RBRACKET = "Rbracket";
 148    var TOK_RPAREN = "Rparen";
 149    var TOK_COMMA = "Comma";
 150    var TOK_COLON = "Colon";
 151    var TOK_RBRACE = "Rbrace";
 152    var TOK_NUMBER = "Number";
 153    var TOK_CURRENT = "Current";
 154    var TOK_EXPREF = "Expref";
 155    var TOK_PIPE = "Pipe";
 156    var TOK_OR = "Or";
 157    var TOK_AND = "And";
 158    var TOK_EQ = "EQ";
 159    var TOK_GT = "GT";
 160    var TOK_LT = "LT";
 161    var TOK_GTE = "GTE";
 162    var TOK_LTE = "LTE";
 163    var TOK_NE = "NE";
 164    var TOK_FLATTEN = "Flatten";
 165    var TOK_STAR = "Star";
 166    var TOK_FILTER = "Filter";
 167    var TOK_DOT = "Dot";
 168    var TOK_NOT = "Not";
 169    var TOK_LBRACE = "Lbrace";
 170    var TOK_LBRACKET = "Lbracket";
 171    var TOK_LPAREN= "Lparen";
 172    var TOK_LITERAL= "Literal";
 173  
 174    // The "&", "[", "<", ">" tokens
 175    // are not in basicToken because
 176    // there are two token variants
 177    // ("&&", "[?", "<=", ">=").  This is specially handled
 178    // below.
 179  
 180    var basicTokens = {
 181      ".": TOK_DOT,
 182      "*": TOK_STAR,
 183      ",": TOK_COMMA,
 184      ":": TOK_COLON,
 185      "{": TOK_LBRACE,
 186      "}": TOK_RBRACE,
 187      "]": TOK_RBRACKET,
 188      "(": TOK_LPAREN,
 189      ")": TOK_RPAREN,
 190      "@": TOK_CURRENT
 191    };
 192  
 193    var operatorStartToken = {
 194        "<": true,
 195        ">": true,
 196        "=": true,
 197        "!": true
 198    };
 199  
 200    var skipChars = {
 201        " ": true,
 202        "\t": true,
 203        "\n": true
 204    };
 205  
 206  
 207    function isAlpha(ch) {
 208        return (ch >= "a" && ch <= "z") ||
 209               (ch >= "A" && ch <= "Z") ||
 210               ch === "_";
 211    }
 212  
 213    function isNum(ch) {
 214        return (ch >= "0" && ch <= "9") ||
 215               ch === "-";
 216    }
 217    function isAlphaNum(ch) {
 218        return (ch >= "a" && ch <= "z") ||
 219               (ch >= "A" && ch <= "Z") ||
 220               (ch >= "0" && ch <= "9") ||
 221               ch === "_";
 222    }
 223  
 224    function Lexer() {
 225    }
 226    Lexer.prototype = {
 227        tokenize: function(stream) {
 228            var tokens = [];
 229            this._current = 0;
 230            var start;
 231            var identifier;
 232            var token;
 233            while (this._current < stream.length) {
 234                if (isAlpha(stream[this._current])) {
 235                    start = this._current;
 236                    identifier = this._consumeUnquotedIdentifier(stream);
 237                    tokens.push({type: TOK_UNQUOTEDIDENTIFIER,
 238                                 value: identifier,
 239                                 start: start});
 240                } else if (basicTokens[stream[this._current]] !== undefined) {
 241                    tokens.push({type: basicTokens[stream[this._current]],
 242                                value: stream[this._current],
 243                                start: this._current});
 244                    this._current++;
 245                } else if (isNum(stream[this._current])) {
 246                    token = this._consumeNumber(stream);
 247                    tokens.push(token);
 248                } else if (stream[this._current] === "[") {
 249                    // No need to increment this._current.  This happens
 250                    // in _consumeLBracket
 251                    token = this._consumeLBracket(stream);
 252                    tokens.push(token);
 253                } else if (stream[this._current] === "\"") {
 254                    start = this._current;
 255                    identifier = this._consumeQuotedIdentifier(stream);
 256                    tokens.push({type: TOK_QUOTEDIDENTIFIER,
 257                                 value: identifier,
 258                                 start: start});
 259                } else if (stream[this._current] === "'") {
 260                    start = this._current;
 261                    identifier = this._consumeRawStringLiteral(stream);
 262                    tokens.push({type: TOK_LITERAL,
 263                                 value: identifier,
 264                                 start: start});
 265                } else if (stream[this._current] === "`") {
 266                    start = this._current;
 267                    var literal = this._consumeLiteral(stream);
 268                    tokens.push({type: TOK_LITERAL,
 269                                 value: literal,
 270                                 start: start});
 271                } else if (operatorStartToken[stream[this._current]] !== undefined) {
 272                    tokens.push(this._consumeOperator(stream));
 273                } else if (skipChars[stream[this._current]] !== undefined) {
 274                    // Ignore whitespace.
 275                    this._current++;
 276                } else if (stream[this._current] === "&") {
 277                    start = this._current;
 278                    this._current++;
 279                    if (stream[this._current] === "&") {
 280                        this._current++;
 281                        tokens.push({type: TOK_AND, value: "&&", start: start});
 282                    } else {
 283                        tokens.push({type: TOK_EXPREF, value: "&", start: start});
 284                    }
 285                } else if (stream[this._current] === "|") {
 286                    start = this._current;
 287                    this._current++;
 288                    if (stream[this._current] === "|") {
 289                        this._current++;
 290                        tokens.push({type: TOK_OR, value: "||", start: start});
 291                    } else {
 292                        tokens.push({type: TOK_PIPE, value: "|", start: start});
 293                    }
 294                } else {
 295                    var error = new Error("Unknown character:" + stream[this._current]);
 296                    error.name = "LexerError";
 297                    throw error;
 298                }
 299            }
 300            return tokens;
 301        },
 302  
 303        _consumeUnquotedIdentifier: function(stream) {
 304            var start = this._current;
 305            this._current++;
 306            while (this._current < stream.length && isAlphaNum(stream[this._current])) {
 307                this._current++;
 308            }
 309            return stream.slice(start, this._current);
 310        },
 311  
 312        _consumeQuotedIdentifier: function(stream) {
 313            var start = this._current;
 314            this._current++;
 315            var maxLength = stream.length;
 316            while (stream[this._current] !== "\"" && this._current < maxLength) {
 317                // You can escape a double quote and you can escape an escape.
 318                var current = this._current;
 319                if (stream[current] === "\\" && (stream[current + 1] === "\\" ||
 320                                                 stream[current + 1] === "\"")) {
 321                    current += 2;
 322                } else {
 323                    current++;
 324                }
 325                this._current = current;
 326            }
 327            this._current++;
 328            return JSON.parse(stream.slice(start, this._current));
 329        },
 330  
 331        _consumeRawStringLiteral: function(stream) {
 332            var start = this._current;
 333            this._current++;
 334            var maxLength = stream.length;
 335            while (stream[this._current] !== "'" && this._current < maxLength) {
 336                // You can escape a single quote and you can escape an escape.
 337                var current = this._current;
 338                if (stream[current] === "\\" && (stream[current + 1] === "\\" ||
 339                                                 stream[current + 1] === "'")) {
 340                    current += 2;
 341                } else {
 342                    current++;
 343                }
 344                this._current = current;
 345            }
 346            this._current++;
 347            var literal = stream.slice(start + 1, this._current - 1);
 348            return literal.replace("\\'", "'");
 349        },
 350  
 351        _consumeNumber: function(stream) {
 352            var start = this._current;
 353            this._current++;
 354            var maxLength = stream.length;
 355            while (isNum(stream[this._current]) && this._current < maxLength) {
 356                this._current++;
 357            }
 358            var value = parseInt(stream.slice(start, this._current));
 359            return {type: TOK_NUMBER, value: value, start: start};
 360        },
 361  
 362        _consumeLBracket: function(stream) {
 363            var start = this._current;
 364            this._current++;
 365            if (stream[this._current] === "?") {
 366                this._current++;
 367                return {type: TOK_FILTER, value: "[?", start: start};
 368            } else if (stream[this._current] === "]") {
 369                this._current++;
 370                return {type: TOK_FLATTEN, value: "[]", start: start};
 371            } else {
 372                return {type: TOK_LBRACKET, value: "[", start: start};
 373            }
 374        },
 375  
 376        _consumeOperator: function(stream) {
 377            var start = this._current;
 378            var startingChar = stream[start];
 379            this._current++;
 380            if (startingChar === "!") {
 381                if (stream[this._current] === "=") {
 382                    this._current++;
 383                    return {type: TOK_NE, value: "!=", start: start};
 384                } else {
 385                  return {type: TOK_NOT, value: "!", start: start};
 386                }
 387            } else if (startingChar === "<") {
 388                if (stream[this._current] === "=") {
 389                    this._current++;
 390                    return {type: TOK_LTE, value: "<=", start: start};
 391                } else {
 392                    return {type: TOK_LT, value: "<", start: start};
 393                }
 394            } else if (startingChar === ">") {
 395                if (stream[this._current] === "=") {
 396                    this._current++;
 397                    return {type: TOK_GTE, value: ">=", start: start};
 398                } else {
 399                    return {type: TOK_GT, value: ">", start: start};
 400                }
 401            } else if (startingChar === "=") {
 402                if (stream[this._current] === "=") {
 403                    this._current++;
 404                    return {type: TOK_EQ, value: "==", start: start};
 405                }
 406            }
 407        },
 408  
 409        _consumeLiteral: function(stream) {
 410            this._current++;
 411            var start = this._current;
 412            var maxLength = stream.length;
 413            var literal;
 414            while(stream[this._current] !== "`" && this._current < maxLength) {
 415                // You can escape a literal char or you can escape the escape.
 416                var current = this._current;
 417                if (stream[current] === "\\" && (stream[current + 1] === "\\" ||
 418                                                 stream[current + 1] === "`")) {
 419                    current += 2;
 420                } else {
 421                    current++;
 422                }
 423                this._current = current;
 424            }
 425            var literalString = trimLeft(stream.slice(start, this._current));
 426            literalString = literalString.replace("\\`", "`");
 427            if (this._looksLikeJSON(literalString)) {
 428                literal = JSON.parse(literalString);
 429            } else {
 430                // Try to JSON parse it as "<literal>"
 431                literal = JSON.parse("\"" + literalString + "\"");
 432            }
 433            // +1 gets us to the ending "`", +1 to move on to the next char.
 434            this._current++;
 435            return literal;
 436        },
 437  
 438        _looksLikeJSON: function(literalString) {
 439            var startingChars = "[{\"";
 440            var jsonLiterals = ["true", "false", "null"];
 441            var numberLooking = "-0123456789";
 442  
 443            if (literalString === "") {
 444                return false;
 445            } else if (startingChars.indexOf(literalString[0]) >= 0) {
 446                return true;
 447            } else if (jsonLiterals.indexOf(literalString) >= 0) {
 448                return true;
 449            } else if (numberLooking.indexOf(literalString[0]) >= 0) {
 450                try {
 451                    JSON.parse(literalString);
 452                    return true;
 453                } catch (ex) {
 454                    return false;
 455                }
 456            } else {
 457                return false;
 458            }
 459        }
 460    };
 461  
 462        var bindingPower = {};
 463        bindingPower[TOK_EOF] = 0;
 464        bindingPower[TOK_UNQUOTEDIDENTIFIER] = 0;
 465        bindingPower[TOK_QUOTEDIDENTIFIER] = 0;
 466        bindingPower[TOK_RBRACKET] = 0;
 467        bindingPower[TOK_RPAREN] = 0;
 468        bindingPower[TOK_COMMA] = 0;
 469        bindingPower[TOK_RBRACE] = 0;
 470        bindingPower[TOK_NUMBER] = 0;
 471        bindingPower[TOK_CURRENT] = 0;
 472        bindingPower[TOK_EXPREF] = 0;
 473        bindingPower[TOK_PIPE] = 1;
 474        bindingPower[TOK_OR] = 2;
 475        bindingPower[TOK_AND] = 3;
 476        bindingPower[TOK_EQ] = 5;
 477        bindingPower[TOK_GT] = 5;
 478        bindingPower[TOK_LT] = 5;
 479        bindingPower[TOK_GTE] = 5;
 480        bindingPower[TOK_LTE] = 5;
 481        bindingPower[TOK_NE] = 5;
 482        bindingPower[TOK_FLATTEN] = 9;
 483        bindingPower[TOK_STAR] = 20;
 484        bindingPower[TOK_FILTER] = 21;
 485        bindingPower[TOK_DOT] = 40;
 486        bindingPower[TOK_NOT] = 45;
 487        bindingPower[TOK_LBRACE] = 50;
 488        bindingPower[TOK_LBRACKET] = 55;
 489        bindingPower[TOK_LPAREN] = 60;
 490  
 491    function Parser() {
 492    }
 493  
 494    Parser.prototype = {
 495        parse: function(expression) {
 496            this._loadTokens(expression);
 497            this.index = 0;
 498            var ast = this.expression(0);
 499            if (this._lookahead(0) !== TOK_EOF) {
 500                var t = this._lookaheadToken(0);
 501                var error = new Error(
 502                    "Unexpected token type: " + t.type + ", value: " + t.value);
 503                error.name = "ParserError";
 504                throw error;
 505            }
 506            return ast;
 507        },
 508  
 509        _loadTokens: function(expression) {
 510            var lexer = new Lexer();
 511            var tokens = lexer.tokenize(expression);
 512            tokens.push({type: TOK_EOF, value: "", start: expression.length});
 513            this.tokens = tokens;
 514        },
 515  
 516        expression: function(rbp) {
 517            var leftToken = this._lookaheadToken(0);
 518            this._advance();
 519            var left = this.nud(leftToken);
 520            var currentToken = this._lookahead(0);
 521            while (rbp < bindingPower[currentToken]) {
 522                this._advance();
 523                left = this.led(currentToken, left);
 524                currentToken = this._lookahead(0);
 525            }
 526            return left;
 527        },
 528  
 529        _lookahead: function(number) {
 530            return this.tokens[this.index + number].type;
 531        },
 532  
 533        _lookaheadToken: function(number) {
 534            return this.tokens[this.index + number];
 535        },
 536  
 537        _advance: function() {
 538            this.index++;
 539        },
 540  
 541        nud: function(token) {
 542          var left;
 543          var right;
 544          var expression;
 545          switch (token.type) {
 546            case TOK_LITERAL:
 547              return {type: "Literal", value: token.value};
 548            case TOK_UNQUOTEDIDENTIFIER:
 549              return {type: "Field", name: token.value};
 550            case TOK_QUOTEDIDENTIFIER:
 551              var node = {type: "Field", name: token.value};
 552              if (this._lookahead(0) === TOK_LPAREN) {
 553                  throw new Error("Quoted identifier not allowed for function names.");
 554              } else {
 555                  return node;
 556              }
 557              break;
 558            case TOK_NOT:
 559              right = this.expression(bindingPower.Not);
 560              return {type: "NotExpression", children: [right]};
 561            case TOK_STAR:
 562              left = {type: "Identity"};
 563              right = null;
 564              if (this._lookahead(0) === TOK_RBRACKET) {
 565                  // This can happen in a multiselect,
 566                  // [a, b, *]
 567                  right = {type: "Identity"};
 568              } else {
 569                  right = this._parseProjectionRHS(bindingPower.Star);
 570              }
 571              return {type: "ValueProjection", children: [left, right]};
 572            case TOK_FILTER:
 573              return this.led(token.type, {type: "Identity"});
 574            case TOK_LBRACE:
 575              return this._parseMultiselectHash();
 576            case TOK_FLATTEN:
 577              left = {type: TOK_FLATTEN, children: [{type: "Identity"}]};
 578              right = this._parseProjectionRHS(bindingPower.Flatten);
 579              return {type: "Projection", children: [left, right]};
 580            case TOK_LBRACKET:
 581              if (this._lookahead(0) === TOK_NUMBER || this._lookahead(0) === TOK_COLON) {
 582                  right = this._parseIndexExpression();
 583                  return this._projectIfSlice({type: "Identity"}, right);
 584              } else if (this._lookahead(0) === TOK_STAR &&
 585                         this._lookahead(1) === TOK_RBRACKET) {
 586                  this._advance();
 587                  this._advance();
 588                  right = this._parseProjectionRHS(bindingPower.Star);
 589                  return {type: "Projection",
 590                          children: [{type: "Identity"}, right]};
 591              } else {
 592                  return this._parseMultiselectList();
 593              }
 594              break;
 595            case TOK_CURRENT:
 596              return {type: TOK_CURRENT};
 597            case TOK_EXPREF:
 598              expression = this.expression(bindingPower.Expref);
 599              return {type: "ExpressionReference", children: [expression]};
 600            case TOK_LPAREN:
 601              var args = [];
 602              while (this._lookahead(0) !== TOK_RPAREN) {
 603                if (this._lookahead(0) === TOK_CURRENT) {
 604                  expression = {type: TOK_CURRENT};
 605                  this._advance();
 606                } else {
 607                  expression = this.expression(0);
 608                }
 609                args.push(expression);
 610              }
 611              this._match(TOK_RPAREN);
 612              return args[0];
 613            default:
 614              this._errorToken(token);
 615          }
 616        },
 617  
 618        led: function(tokenName, left) {
 619          var right;
 620          switch(tokenName) {
 621            case TOK_DOT:
 622              var rbp = bindingPower.Dot;
 623              if (this._lookahead(0) !== TOK_STAR) {
 624                  right = this._parseDotRHS(rbp);
 625                  return {type: "Subexpression", children: [left, right]};
 626              } else {
 627                  // Creating a projection.
 628                  this._advance();
 629                  right = this._parseProjectionRHS(rbp);
 630                  return {type: "ValueProjection", children: [left, right]};
 631              }
 632              break;
 633            case TOK_PIPE:
 634              right = this.expression(bindingPower.Pipe);
 635              return {type: TOK_PIPE, children: [left, right]};
 636            case TOK_OR:
 637              right = this.expression(bindingPower.Or);
 638              return {type: "OrExpression", children: [left, right]};
 639            case TOK_AND:
 640              right = this.expression(bindingPower.And);
 641              return {type: "AndExpression", children: [left, right]};
 642            case TOK_LPAREN:
 643              var name = left.name;
 644              var args = [];
 645              var expression, node;
 646              while (this._lookahead(0) !== TOK_RPAREN) {
 647                if (this._lookahead(0) === TOK_CURRENT) {
 648                  expression = {type: TOK_CURRENT};
 649                  this._advance();
 650                } else {
 651                  expression = this.expression(0);
 652                }
 653                if (this._lookahead(0) === TOK_COMMA) {
 654                  this._match(TOK_COMMA);
 655                }
 656                args.push(expression);
 657              }
 658              this._match(TOK_RPAREN);
 659              node = {type: "Function", name: name, children: args};
 660              return node;
 661            case TOK_FILTER:
 662              var condition = this.expression(0);
 663              this._match(TOK_RBRACKET);
 664              if (this._lookahead(0) === TOK_FLATTEN) {
 665                right = {type: "Identity"};
 666              } else {
 667                right = this._parseProjectionRHS(bindingPower.Filter);
 668              }
 669              return {type: "FilterProjection", children: [left, right, condition]};
 670            case TOK_FLATTEN:
 671              var leftNode = {type: TOK_FLATTEN, children: [left]};
 672              var rightNode = this._parseProjectionRHS(bindingPower.Flatten);
 673              return {type: "Projection", children: [leftNode, rightNode]};
 674            case TOK_EQ:
 675            case TOK_NE:
 676            case TOK_GT:
 677            case TOK_GTE:
 678            case TOK_LT:
 679            case TOK_LTE:
 680              return this._parseComparator(left, tokenName);
 681            case TOK_LBRACKET:
 682              var token = this._lookaheadToken(0);
 683              if (token.type === TOK_NUMBER || token.type === TOK_COLON) {
 684                  right = this._parseIndexExpression();
 685                  return this._projectIfSlice(left, right);
 686              } else {
 687                  this._match(TOK_STAR);
 688                  this._match(TOK_RBRACKET);
 689                  right = this._parseProjectionRHS(bindingPower.Star);
 690                  return {type: "Projection", children: [left, right]};
 691              }
 692              break;
 693            default:
 694              this._errorToken(this._lookaheadToken(0));
 695          }
 696        },
 697  
 698        _match: function(tokenType) {
 699            if (this._lookahead(0) === tokenType) {
 700                this._advance();
 701            } else {
 702                var t = this._lookaheadToken(0);
 703                var error = new Error("Expected " + tokenType + ", got: " + t.type);
 704                error.name = "ParserError";
 705                throw error;
 706            }
 707        },
 708  
 709        _errorToken: function(token) {
 710            var error = new Error("Invalid token (" +
 711                                  token.type + "): \"" +
 712                                  token.value + "\"");
 713            error.name = "ParserError";
 714            throw error;
 715        },
 716  
 717  
 718        _parseIndexExpression: function() {
 719            if (this._lookahead(0) === TOK_COLON || this._lookahead(1) === TOK_COLON) {
 720                return this._parseSliceExpression();
 721            } else {
 722                var node = {
 723                    type: "Index",
 724                    value: this._lookaheadToken(0).value};
 725                this._advance();
 726                this._match(TOK_RBRACKET);
 727                return node;
 728            }
 729        },
 730  
 731        _projectIfSlice: function(left, right) {
 732            var indexExpr = {type: "IndexExpression", children: [left, right]};
 733            if (right.type === "Slice") {
 734                return {
 735                    type: "Projection",
 736                    children: [indexExpr, this._parseProjectionRHS(bindingPower.Star)]
 737                };
 738            } else {
 739                return indexExpr;
 740            }
 741        },
 742  
 743        _parseSliceExpression: function() {
 744            // [start:end:step] where each part is optional, as well as the last
 745            // colon.
 746            var parts = [null, null, null];
 747            var index = 0;
 748            var currentToken = this._lookahead(0);
 749            while (currentToken !== TOK_RBRACKET && index < 3) {
 750                if (currentToken === TOK_COLON) {
 751                    index++;
 752                    this._advance();
 753                } else if (currentToken === TOK_NUMBER) {
 754                    parts[index] = this._lookaheadToken(0).value;
 755                    this._advance();
 756                } else {
 757                    var t = this._lookahead(0);
 758                    var error = new Error("Syntax error, unexpected token: " +
 759                                          t.value + "(" + t.type + ")");
 760                    error.name = "Parsererror";
 761                    throw error;
 762                }
 763                currentToken = this._lookahead(0);
 764            }
 765            this._match(TOK_RBRACKET);
 766            return {
 767                type: "Slice",
 768                children: parts
 769            };
 770        },
 771  
 772        _parseComparator: function(left, comparator) {
 773          var right = this.expression(bindingPower[comparator]);
 774          return {type: "Comparator", name: comparator, children: [left, right]};
 775        },
 776  
 777        _parseDotRHS: function(rbp) {
 778            var lookahead = this._lookahead(0);
 779            var exprTokens = [TOK_UNQUOTEDIDENTIFIER, TOK_QUOTEDIDENTIFIER, TOK_STAR];
 780            if (exprTokens.indexOf(lookahead) >= 0) {
 781                return this.expression(rbp);
 782            } else if (lookahead === TOK_LBRACKET) {
 783                this._match(TOK_LBRACKET);
 784                return this._parseMultiselectList();
 785            } else if (lookahead === TOK_LBRACE) {
 786                this._match(TOK_LBRACE);
 787                return this._parseMultiselectHash();
 788            }
 789        },
 790  
 791        _parseProjectionRHS: function(rbp) {
 792            var right;
 793            if (bindingPower[this._lookahead(0)] < 10) {
 794                right = {type: "Identity"};
 795            } else if (this._lookahead(0) === TOK_LBRACKET) {
 796                right = this.expression(rbp);
 797            } else if (this._lookahead(0) === TOK_FILTER) {
 798                right = this.expression(rbp);
 799            } else if (this._lookahead(0) === TOK_DOT) {
 800                this._match(TOK_DOT);
 801                right = this._parseDotRHS(rbp);
 802            } else {
 803                var t = this._lookaheadToken(0);
 804                var error = new Error("Sytanx error, unexpected token: " +
 805                                      t.value + "(" + t.type + ")");
 806                error.name = "ParserError";
 807                throw error;
 808            }
 809            return right;
 810        },
 811  
 812        _parseMultiselectList: function() {
 813            var expressions = [];
 814            while (this._lookahead(0) !== TOK_RBRACKET) {
 815                var expression = this.expression(0);
 816                expressions.push(expression);
 817                if (this._lookahead(0) === TOK_COMMA) {
 818                    this._match(TOK_COMMA);
 819                    if (this._lookahead(0) === TOK_RBRACKET) {
 820                      throw new Error("Unexpected token Rbracket");
 821                    }
 822                }
 823            }
 824            this._match(TOK_RBRACKET);
 825            return {type: "MultiSelectList", children: expressions};
 826        },
 827  
 828        _parseMultiselectHash: function() {
 829          var pairs = [];
 830          var identifierTypes = [TOK_UNQUOTEDIDENTIFIER, TOK_QUOTEDIDENTIFIER];
 831          var keyToken, keyName, value, node;
 832          for (;;) {
 833            keyToken = this._lookaheadToken(0);
 834            if (identifierTypes.indexOf(keyToken.type) < 0) {
 835              throw new Error("Expecting an identifier token, got: " +
 836                              keyToken.type);
 837            }
 838            keyName = keyToken.value;
 839            this._advance();
 840            this._match(TOK_COLON);
 841            value = this.expression(0);
 842            node = {type: "KeyValuePair", name: keyName, value: value};
 843            pairs.push(node);
 844            if (this._lookahead(0) === TOK_COMMA) {
 845              this._match(TOK_COMMA);
 846            } else if (this._lookahead(0) === TOK_RBRACE) {
 847              this._match(TOK_RBRACE);
 848              break;
 849            }
 850          }
 851          return {type: "MultiSelectHash", children: pairs};
 852        }
 853    };
 854  
 855  
 856    function TreeInterpreter(runtime) {
 857      this.runtime = runtime;
 858    }
 859  
 860    TreeInterpreter.prototype = {
 861        search: function(node, value) {
 862            return this.visit(node, value);
 863        },
 864  
 865        visit: function(node, value) {
 866            var matched, current, result, first, second, field, left, right, collected, i;
 867            switch (node.type) {
 868              case "Field":
 869                if (value === null ) {
 870                    return null;
 871                } else if (isObject(value)) {
 872                    field = value[node.name];
 873                    if (field === undefined) {
 874                        return null;
 875                    } else {
 876                        return field;
 877                    }
 878                } else {
 879                  return null;
 880                }
 881                break;
 882              case "Subexpression":
 883                result = this.visit(node.children[0], value);
 884                for (i = 1; i < node.children.length; i++) {
 885                    result = this.visit(node.children[1], result);
 886                    if (result === null) {
 887                        return null;
 888                    }
 889                }
 890                return result;
 891              case "IndexExpression":
 892                left = this.visit(node.children[0], value);
 893                right = this.visit(node.children[1], left);
 894                return right;
 895              case "Index":
 896                if (!isArray(value)) {
 897                  return null;
 898                }
 899                var index = node.value;
 900                if (index < 0) {
 901                  index = value.length + index;
 902                }
 903                result = value[index];
 904                if (result === undefined) {
 905                  result = null;
 906                }
 907                return result;
 908              case "Slice":
 909                if (!isArray(value)) {
 910                  return null;
 911                }
 912                var sliceParams = node.children.slice(0);
 913                var computed = this.computeSliceParams(value.length, sliceParams);
 914                var start = computed[0];
 915                var stop = computed[1];
 916                var step = computed[2];
 917                result = [];
 918                if (step > 0) {
 919                    for (i = start; i < stop; i += step) {
 920                        result.push(value[i]);
 921                    }
 922                } else {
 923                    for (i = start; i > stop; i += step) {
 924                        result.push(value[i]);
 925                    }
 926                }
 927                return result;
 928              case "Projection":
 929                // Evaluate left child.
 930                var base = this.visit(node.children[0], value);
 931                if (!isArray(base)) {
 932                  return null;
 933                }
 934                collected = [];
 935                for (i = 0; i < base.length; i++) {
 936                  current = this.visit(node.children[1], base[i]);
 937                  if (current !== null) {
 938                    collected.push(current);
 939                  }
 940                }
 941                return collected;
 942              case "ValueProjection":
 943                // Evaluate left child.
 944                base = this.visit(node.children[0], value);
 945                if (!isObject(base)) {
 946                  return null;
 947                }
 948                collected = [];
 949                var values = objValues(base);
 950                for (i = 0; i < values.length; i++) {
 951                  current = this.visit(node.children[1], values[i]);
 952                  if (current !== null) {
 953                    collected.push(current);
 954                  }
 955                }
 956                return collected;
 957              case "FilterProjection":
 958                base = this.visit(node.children[0], value);
 959                if (!isArray(base)) {
 960                  return null;
 961                }
 962                var filtered = [];
 963                var finalResults = [];
 964                for (i = 0; i < base.length; i++) {
 965                  matched = this.visit(node.children[2], base[i]);
 966                  if (!isFalse(matched)) {
 967                    filtered.push(base[i]);
 968                  }
 969                }
 970                for (var j = 0; j < filtered.length; j++) {
 971                  current = this.visit(node.children[1], filtered[j]);
 972                  if (current !== null) {
 973                    finalResults.push(current);
 974                  }
 975                }
 976                return finalResults;
 977              case "Comparator":
 978                first = this.visit(node.children[0], value);
 979                second = this.visit(node.children[1], value);
 980                switch(node.name) {
 981                  case TOK_EQ:
 982                    result = strictDeepEqual(first, second);
 983                    break;
 984                  case TOK_NE:
 985                    result = !strictDeepEqual(first, second);
 986                    break;
 987                  case TOK_GT:
 988                    result = first > second;
 989                    break;
 990                  case TOK_GTE:
 991                    result = first >= second;
 992                    break;
 993                  case TOK_LT:
 994                    result = first < second;
 995                    break;
 996                  case TOK_LTE:
 997                    result = first <= second;
 998                    break;
 999                  default:
1000                    throw new Error("Unknown comparator: " + node.name);
1001                }
1002                return result;
1003              case TOK_FLATTEN:
1004                var original = this.visit(node.children[0], value);
1005                if (!isArray(original)) {
1006                  return null;
1007                }
1008                var merged = [];
1009                for (i = 0; i < original.length; i++) {
1010                  current = original[i];
1011                  if (isArray(current)) {
1012                    merged.push.apply(merged, current);
1013                  } else {
1014                    merged.push(current);
1015                  }
1016                }
1017                return merged;
1018              case "Identity":
1019                return value;
1020              case "MultiSelectList":
1021                if (value === null) {
1022                  return null;
1023                }
1024                collected = [];
1025                for (i = 0; i < node.children.length; i++) {
1026                    collected.push(this.visit(node.children[i], value));
1027                }
1028                return collected;
1029              case "MultiSelectHash":
1030                if (value === null) {
1031                  return null;
1032                }
1033                collected = {};
1034                var child;
1035                for (i = 0; i < node.children.length; i++) {
1036                  child = node.children[i];
1037                  collected[child.name] = this.visit(child.value, value);
1038                }
1039                return collected;
1040              case "OrExpression":
1041                matched = this.visit(node.children[0], value);
1042                if (isFalse(matched)) {
1043                    matched = this.visit(node.children[1], value);
1044                }
1045                return matched;
1046              case "AndExpression":
1047                first = this.visit(node.children[0], value);
1048  
1049                if (isFalse(first) === true) {
1050                  return first;
1051                }
1052                return this.visit(node.children[1], value);
1053              case "NotExpression":
1054                first = this.visit(node.children[0], value);
1055                return isFalse(first);
1056              case "Literal":
1057                return node.value;
1058              case TOK_PIPE:
1059                left = this.visit(node.children[0], value);
1060                return this.visit(node.children[1], left);
1061              case TOK_CURRENT:
1062                return value;
1063              case "Function":
1064                var resolvedArgs = [];
1065                for (i = 0; i < node.children.length; i++) {
1066                    resolvedArgs.push(this.visit(node.children[i], value));
1067                }
1068                return this.runtime.callFunction(node.name, resolvedArgs);
1069              case "ExpressionReference":
1070                var refNode = node.children[0];
1071                // Tag the node with a specific attribute so the type
1072                // checker verify the type.
1073                refNode.jmespathType = TOK_EXPREF;
1074                return refNode;
1075              default:
1076                throw new Error("Unknown node type: " + node.type);
1077            }
1078        },
1079  
1080        computeSliceParams: function(arrayLength, sliceParams) {
1081          var start = sliceParams[0];
1082          var stop = sliceParams[1];
1083          var step = sliceParams[2];
1084          var computed = [null, null, null];
1085          if (step === null) {
1086            step = 1;
1087          } else if (step === 0) {
1088            var error = new Error("Invalid slice, step cannot be 0");
1089            error.name = "RuntimeError";
1090            throw error;
1091          }
1092          var stepValueNegative = step < 0 ? true : false;
1093  
1094          if (start === null) {
1095              start = stepValueNegative ? arrayLength - 1 : 0;
1096          } else {
1097              start = this.capSliceRange(arrayLength, start, step);
1098          }
1099  
1100          if (stop === null) {
1101              stop = stepValueNegative ? -1 : arrayLength;
1102          } else {
1103              stop = this.capSliceRange(arrayLength, stop, step);
1104          }
1105          computed[0] = start;
1106          computed[1] = stop;
1107          computed[2] = step;
1108          return computed;
1109        },
1110  
1111        capSliceRange: function(arrayLength, actualValue, step) {
1112            if (actualValue < 0) {
1113                actualValue += arrayLength;
1114                if (actualValue < 0) {
1115                    actualValue = step < 0 ? -1 : 0;
1116                }
1117            } else if (actualValue >= arrayLength) {
1118                actualValue = step < 0 ? arrayLength - 1 : arrayLength;
1119            }
1120            return actualValue;
1121        }
1122  
1123    };
1124  
1125    function Runtime(interpreter) {
1126      this._interpreter = interpreter;
1127      this.functionTable = {
1128          // name: [function, <signature>]
1129          // The <signature> can be:
1130          //
1131          // {
1132          //   args: [[type1, type2], [type1, type2]],
1133          //   variadic: true|false
1134          // }
1135          //
1136          // Each arg in the arg list is a list of valid types
1137          // (if the function is overloaded and supports multiple
1138          // types.  If the type is "any" then no type checking
1139          // occurs on the argument.  Variadic is optional
1140          // and if not provided is assumed to be false.
1141          abs: {_func: this._functionAbs, _signature: [{types: [TYPE_NUMBER]}]},
1142          avg: {_func: this._functionAvg, _signature: [{types: [TYPE_ARRAY_NUMBER]}]},
1143          ceil: {_func: this._functionCeil, _signature: [{types: [TYPE_NUMBER]}]},
1144          contains: {
1145              _func: this._functionContains,
1146              _signature: [{types: [TYPE_STRING, TYPE_ARRAY]},
1147                          {types: [TYPE_ANY]}]},
1148          "ends_with": {
1149              _func: this._functionEndsWith,
1150              _signature: [{types: [TYPE_STRING]}, {types: [TYPE_STRING]}]},
1151          floor: {_func: this._functionFloor, _signature: [{types: [TYPE_NUMBER]}]},
1152          length: {
1153              _func: this._functionLength,
1154              _signature: [{types: [TYPE_STRING, TYPE_ARRAY, TYPE_OBJECT]}]},
1155          map: {
1156              _func: this._functionMap,
1157              _signature: [{types: [TYPE_EXPREF]}, {types: [TYPE_ARRAY]}]},
1158          max: {
1159              _func: this._functionMax,
1160              _signature: [{types: [TYPE_ARRAY_NUMBER, TYPE_ARRAY_STRING]}]},
1161          "merge": {
1162              _func: this._functionMerge,
1163              _signature: [{types: [TYPE_OBJECT], variadic: true}]
1164          },
1165          "max_by": {
1166            _func: this._functionMaxBy,
1167            _signature: [{types: [TYPE_ARRAY]}, {types: [TYPE_EXPREF]}]
1168          },
1169          sum: {_func: this._functionSum, _signature: [{types: [TYPE_ARRAY_NUMBER]}]},
1170          "starts_with": {
1171              _func: this._functionStartsWith,
1172              _signature: [{types: [TYPE_STRING]}, {types: [TYPE_STRING]}]},
1173          min: {
1174              _func: this._functionMin,
1175              _signature: [{types: [TYPE_ARRAY_NUMBER, TYPE_ARRAY_STRING]}]},
1176          "min_by": {
1177            _func: this._functionMinBy,
1178            _signature: [{types: [TYPE_ARRAY]}, {types: [TYPE_EXPREF]}]
1179          },
1180          type: {_func: this._functionType, _signature: [{types: [TYPE_ANY]}]},
1181          keys: {_func: this._functionKeys, _signature: [{types: [TYPE_OBJECT]}]},
1182          values: {_func: this._functionValues, _signature: [{types: [TYPE_OBJECT]}]},
1183          sort: {_func: this._functionSort, _signature: [{types: [TYPE_ARRAY_STRING, TYPE_ARRAY_NUMBER]}]},
1184          "sort_by": {
1185            _func: this._functionSortBy,
1186            _signature: [{types: [TYPE_ARRAY]}, {types: [TYPE_EXPREF]}]
1187          },
1188          join: {
1189              _func: this._functionJoin,
1190              _signature: [
1191                  {types: [TYPE_STRING]},
1192                  {types: [TYPE_ARRAY_STRING]}
1193              ]
1194          },
1195          reverse: {
1196              _func: this._functionReverse,
1197              _signature: [{types: [TYPE_STRING, TYPE_ARRAY]}]},
1198          "to_array": {_func: this._functionToArray, _signature: [{types: [TYPE_ANY]}]},
1199          "to_string": {_func: this._functionToString, _signature: [{types: [TYPE_ANY]}]},
1200          "to_number": {_func: this._functionToNumber, _signature: [{types: [TYPE_ANY]}]},
1201          "not_null": {
1202              _func: this._functionNotNull,
1203              _signature: [{types: [TYPE_ANY], variadic: true}]
1204          }
1205      };
1206    }
1207  
1208    Runtime.prototype = {
1209      callFunction: function(name, resolvedArgs) {
1210        var functionEntry = this.functionTable[name];
1211        if (functionEntry === undefined) {
1212            throw new Error("Unknown function: " + name + "()");
1213        }
1214        this._validateArgs(name, resolvedArgs, functionEntry._signature);
1215        return functionEntry._func.call(this, resolvedArgs);
1216      },
1217  
1218      _validateArgs: function(name, args, signature) {
1219          // Validating the args requires validating
1220          // the correct arity and the correct type of each arg.
1221          // If the last argument is declared as variadic, then we need
1222          // a minimum number of args to be required.  Otherwise it has to
1223          // be an exact amount.
1224          var pluralized;
1225          if (signature[signature.length - 1].variadic) {
1226              if (args.length < signature.length) {
1227                  pluralized = signature.length === 1 ? " argument" : " arguments";
1228                  throw new Error("ArgumentError: " + name + "() " +
1229                                  "takes at least" + signature.length + pluralized +
1230                                  " but received " + args.length);
1231              }
1232          } else if (args.length !== signature.length) {
1233              pluralized = signature.length === 1 ? " argument" : " arguments";
1234              throw new Error("ArgumentError: " + name + "() " +
1235                              "takes " + signature.length + pluralized +
1236                              " but received " + args.length);
1237          }
1238          var currentSpec;
1239          var actualType;
1240          var typeMatched;
1241          for (var i = 0; i < signature.length; i++) {
1242              typeMatched = false;
1243              currentSpec = signature[i].types;
1244              actualType = this._getTypeName(args[i]);
1245              for (var j = 0; j < currentSpec.length; j++) {
1246                  if (this._typeMatches(actualType, currentSpec[j], args[i])) {
1247                      typeMatched = true;
1248                      break;
1249                  }
1250              }
1251              if (!typeMatched) {
1252                  throw new Error("TypeError: " + name + "() " +
1253                                  "expected argument " + (i + 1) +
1254                                  " to be type " + currentSpec +
1255                                  " but received type " + actualType +
1256                                  " instead.");
1257              }
1258          }
1259      },
1260  
1261      _typeMatches: function(actual, expected, argValue) {
1262          if (expected === TYPE_ANY) {
1263              return true;
1264          }
1265          if (expected === TYPE_ARRAY_STRING ||
1266              expected === TYPE_ARRAY_NUMBER ||
1267              expected === TYPE_ARRAY) {
1268              // The expected type can either just be array,
1269              // or it can require a specific subtype (array of numbers).
1270              //
1271              // The simplest case is if "array" with no subtype is specified.
1272              if (expected === TYPE_ARRAY) {
1273                  return actual === TYPE_ARRAY;
1274              } else if (actual === TYPE_ARRAY) {
1275                  // Otherwise we need to check subtypes.
1276                  // I think this has potential to be improved.
1277                  var subtype;
1278                  if (expected === TYPE_ARRAY_NUMBER) {
1279                    subtype = TYPE_NUMBER;
1280                  } else if (expected === TYPE_ARRAY_STRING) {
1281                    subtype = TYPE_STRING;
1282                  }
1283                  for (var i = 0; i < argValue.length; i++) {
1284                      if (!this._typeMatches(
1285                              this._getTypeName(argValue[i]), subtype,
1286                                               argValue[i])) {
1287                          return false;
1288                      }
1289                  }
1290                  return true;
1291              }
1292          } else {
1293              return actual === expected;
1294          }
1295      },
1296      _getTypeName: function(obj) {
1297          switch (Object.prototype.toString.call(obj)) {
1298              case "[object String]":
1299                return TYPE_STRING;
1300              case "[object Number]":
1301                return TYPE_NUMBER;
1302              case "[object Array]":
1303                return TYPE_ARRAY;
1304              case "[object Boolean]":
1305                return TYPE_BOOLEAN;
1306              case "[object Null]":
1307                return TYPE_NULL;
1308              case "[object Object]":
1309                // Check if it's an expref.  If it has, it's been
1310                // tagged with a jmespathType attr of 'Expref';
1311                if (obj.jmespathType === TOK_EXPREF) {
1312                  return TYPE_EXPREF;
1313                } else {
1314                  return TYPE_OBJECT;
1315                }
1316          }
1317      },
1318  
1319      _functionStartsWith: function(resolvedArgs) {
1320          return resolvedArgs[0].lastIndexOf(resolvedArgs[1]) === 0;
1321      },
1322  
1323      _functionEndsWith: function(resolvedArgs) {
1324          var searchStr = resolvedArgs[0];
1325          var suffix = resolvedArgs[1];
1326          return searchStr.indexOf(suffix, searchStr.length - suffix.length) !== -1;
1327      },
1328  
1329      _functionReverse: function(resolvedArgs) {
1330          var typeName = this._getTypeName(resolvedArgs[0]);
1331          if (typeName === TYPE_STRING) {
1332            var originalStr = resolvedArgs[0];
1333            var reversedStr = "";
1334            for (var i = originalStr.length - 1; i >= 0; i--) {
1335                reversedStr += originalStr[i];
1336            }
1337            return reversedStr;
1338          } else {
1339            var reversedArray = resolvedArgs[0].slice(0);
1340            reversedArray.reverse();
1341            return reversedArray;
1342          }
1343      },
1344  
1345      _functionAbs: function(resolvedArgs) {
1346        return Math.abs(resolvedArgs[0]);
1347      },
1348  
1349      _functionCeil: function(resolvedArgs) {
1350          return Math.ceil(resolvedArgs[0]);
1351      },
1352  
1353      _functionAvg: function(resolvedArgs) {
1354          var sum = 0;
1355          var inputArray = resolvedArgs[0];
1356          for (var i = 0; i < inputArray.length; i++) {
1357              sum += inputArray[i];
1358          }
1359          return sum / inputArray.length;
1360      },
1361  
1362      _functionContains: function(resolvedArgs) {
1363          return resolvedArgs[0].indexOf(resolvedArgs[1]) >= 0;
1364      },
1365  
1366      _functionFloor: function(resolvedArgs) {
1367          return Math.floor(resolvedArgs[0]);
1368      },
1369  
1370      _functionLength: function(resolvedArgs) {
1371         if (!isObject(resolvedArgs[0])) {
1372           return resolvedArgs[0].length;
1373         } else {
1374           // As far as I can tell, there's no way to get the length
1375           // of an object without O(n) iteration through the object.
1376           return Object.keys(resolvedArgs[0]).length;
1377         }
1378      },
1379  
1380      _functionMap: function(resolvedArgs) {
1381        var mapped = [];
1382        var interpreter = this._interpreter;
1383        var exprefNode = resolvedArgs[0];
1384        var elements = resolvedArgs[1];
1385        for (var i = 0; i < elements.length; i++) {
1386            mapped.push(interpreter.visit(exprefNode, elements[i]));
1387        }
1388        return mapped;
1389      },
1390  
1391      _functionMerge: function(resolvedArgs) {
1392        var merged = {};
1393        for (var i = 0; i < resolvedArgs.length; i++) {
1394          var current = resolvedArgs[i];
1395          for (var key in current) {
1396            merged[key] = current[key];
1397          }
1398        }
1399        return merged;
1400      },
1401  
1402      _functionMax: function(resolvedArgs) {
1403        if (resolvedArgs[0].length > 0) {
1404          var typeName = this._getTypeName(resolvedArgs[0][0]);
1405          if (typeName === TYPE_NUMBER) {
1406            return Math.max.apply(Math, resolvedArgs[0]);
1407          } else {
1408            var elements = resolvedArgs[0];
1409            var maxElement = elements[0];
1410            for (var i = 1; i < elements.length; i++) {
1411                if (maxElement.localeCompare(elements[i]) < 0) {
1412                    maxElement = elements[i];
1413                }
1414            }
1415            return maxElement;
1416          }
1417        } else {
1418            return null;
1419        }
1420      },
1421  
1422      _functionMin: function(resolvedArgs) {
1423        if (resolvedArgs[0].length > 0) {
1424          var typeName = this._getTypeName(resolvedArgs[0][0]);
1425          if (typeName === TYPE_NUMBER) {
1426            return Math.min.apply(Math, resolvedArgs[0]);
1427          } else {
1428            var elements = resolvedArgs[0];
1429            var minElement = elements[0];
1430            for (var i = 1; i < elements.length; i++) {
1431                if (elements[i].localeCompare(minElement) < 0) {
1432                    minElement = elements[i];
1433                }
1434            }
1435            return minElement;
1436          }
1437        } else {
1438          return null;
1439        }
1440      },
1441  
1442      _functionSum: function(resolvedArgs) {
1443        var sum = 0;
1444        var listToSum = resolvedArgs[0];
1445        for (var i = 0; i < listToSum.length; i++) {
1446          sum += listToSum[i];
1447        }
1448        return sum;
1449      },
1450  
1451      _functionType: function(resolvedArgs) {
1452          switch (this._getTypeName(resolvedArgs[0])) {
1453            case TYPE_NUMBER:
1454              return "number";
1455            case TYPE_STRING:
1456              return "string";
1457            case TYPE_ARRAY:
1458              return "array";
1459            case TYPE_OBJECT:
1460              return "object";
1461            case TYPE_BOOLEAN:
1462              return "boolean";
1463            case TYPE_EXPREF:
1464              return "expref";
1465            case TYPE_NULL:
1466              return "null";
1467          }
1468      },
1469  
1470      _functionKeys: function(resolvedArgs) {
1471          return Object.keys(resolvedArgs[0]);
1472      },
1473  
1474      _functionValues: function(resolvedArgs) {
1475          var obj = resolvedArgs[0];
1476          var keys = Object.keys(obj);
1477          var values = [];
1478          for (var i = 0; i < keys.length; i++) {
1479              values.push(obj[keys[i]]);
1480          }
1481          return values;
1482      },
1483  
1484      _functionJoin: function(resolvedArgs) {
1485          var joinChar = resolvedArgs[0];
1486          var listJoin = resolvedArgs[1];
1487          return listJoin.join(joinChar);
1488      },
1489  
1490      _functionToArray: function(resolvedArgs) {
1491          if (this._getTypeName(resolvedArgs[0]) === TYPE_ARRAY) {
1492              return resolvedArgs[0];
1493          } else {
1494              return [resolvedArgs[0]];
1495          }
1496      },
1497  
1498      _functionToString: function(resolvedArgs) {
1499          if (this._getTypeName(resolvedArgs[0]) === TYPE_STRING) {
1500              return resolvedArgs[0];
1501          } else {
1502              return JSON.stringify(resolvedArgs[0]);
1503          }
1504      },
1505  
1506      _functionToNumber: function(resolvedArgs) {
1507          var typeName = this._getTypeName(resolvedArgs[0]);
1508          var convertedValue;
1509          if (typeName === TYPE_NUMBER) {
1510              return resolvedArgs[0];
1511          } else if (typeName === TYPE_STRING) {
1512              convertedValue = +resolvedArgs[0];
1513              if (!isNaN(convertedValue)) {
1514                  return convertedValue;
1515              }
1516          }
1517          return null;
1518      },
1519  
1520      _functionNotNull: function(resolvedArgs) {
1521          for (var i = 0; i < resolvedArgs.length; i++) {
1522              if (this._getTypeName(resolvedArgs[i]) !== TYPE_NULL) {
1523                  return resolvedArgs[i];
1524              }
1525          }
1526          return null;
1527      },
1528  
1529      _functionSort: function(resolvedArgs) {
1530          var sortedArray = resolvedArgs[0].slice(0);
1531          sortedArray.sort();
1532          return sortedArray;
1533      },
1534  
1535      _functionSortBy: function(resolvedArgs) {
1536          var sortedArray = resolvedArgs[0].slice(0);
1537          if (sortedArray.length === 0) {
1538              return sortedArray;
1539          }
1540          var interpreter = this._interpreter;
1541          var exprefNode = resolvedArgs[1];
1542          var requiredType = this._getTypeName(
1543              interpreter.visit(exprefNode, sortedArray[0]));
1544          if ([TYPE_NUMBER, TYPE_STRING].indexOf(requiredType) < 0) {
1545              throw new Error("TypeError");
1546          }
1547          var that = this;
1548          // In order to get a stable sort out of an unstable
1549          // sort algorithm, we decorate/sort/undecorate (DSU)
1550          // by creating a new list of [index, element] pairs.
1551          // In the cmp function, if the evaluated elements are
1552          // equal, then the index will be used as the tiebreaker.
1553          // After the decorated list has been sorted, it will be
1554          // undecorated to extract the original elements.
1555          var decorated = [];
1556          for (var i = 0; i < sortedArray.length; i++) {
1557            decorated.push([i, sortedArray[i]]);
1558          }
1559          decorated.sort(function(a, b) {
1560            var exprA = interpreter.visit(exprefNode, a[1]);
1561            var exprB = interpreter.visit(exprefNode, b[1]);
1562            if (that._getTypeName(exprA) !== requiredType) {
1563                throw new Error(
1564                    "TypeError: expected " + requiredType + ", received " +
1565                    that._getTypeName(exprA));
1566            } else if (that._getTypeName(exprB) !== requiredType) {
1567                throw new Error(
1568                    "TypeError: expected " + requiredType + ", received " +
1569                    that._getTypeName(exprB));
1570            }
1571            if (exprA > exprB) {
1572              return 1;
1573            } else if (exprA < exprB) {
1574              return -1;
1575            } else {
1576              // If they're equal compare the items by their
1577              // order to maintain relative order of equal keys
1578              // (i.e. to get a stable sort).
1579              return a[0] - b[0];
1580            }
1581          });
1582          // Undecorate: extract out the original list elements.
1583          for (var j = 0; j < decorated.length; j++) {
1584            sortedArray[j] = decorated[j][1];
1585          }
1586          return sortedArray;
1587      },
1588  
1589      _functionMaxBy: function(resolvedArgs) {
1590        var exprefNode = resolvedArgs[1];
1591        var resolvedArray = resolvedArgs[0];
1592        var keyFunction = this.createKeyFunction(exprefNode, [TYPE_NUMBER, TYPE_STRING]);
1593        var maxNumber = -Infinity;
1594        var maxRecord;
1595        var current;
1596        for (var i = 0; i < resolvedArray.length; i++) {
1597          current = keyFunction(resolvedArray[i]);
1598          if (current > maxNumber) {
1599            maxNumber = current;
1600            maxRecord = resolvedArray[i];
1601          }
1602        }
1603        return maxRecord;
1604      },
1605  
1606      _functionMinBy: function(resolvedArgs) {
1607        var exprefNode = resolvedArgs[1];
1608        var resolvedArray = resolvedArgs[0];
1609        var keyFunction = this.createKeyFunction(exprefNode, [TYPE_NUMBER, TYPE_STRING]);
1610        var minNumber = Infinity;
1611        var minRecord;
1612        var current;
1613        for (var i = 0; i < resolvedArray.length; i++) {
1614          current = keyFunction(resolvedArray[i]);
1615          if (current < minNumber) {
1616            minNumber = current;
1617            minRecord = resolvedArray[i];
1618          }
1619        }
1620        return minRecord;
1621      },
1622  
1623      createKeyFunction: function(exprefNode, allowedTypes) {
1624        var that = this;
1625        var interpreter = this._interpreter;
1626        var keyFunc = function(x) {
1627          var current = interpreter.visit(exprefNode, x);
1628          if (allowedTypes.indexOf(that._getTypeName(current)) < 0) {
1629            var msg = "TypeError: expected one of " + allowedTypes +
1630                      ", received " + that._getTypeName(current);
1631            throw new Error(msg);
1632          }
1633          return current;
1634        };
1635        return keyFunc;
1636      }
1637  
1638    };
1639  
1640    function compile(stream) {
1641      var parser = new Parser();
1642      var ast = parser.parse(stream);
1643      return ast;
1644    }
1645  
1646    function tokenize(stream) {
1647        var lexer = new Lexer();
1648        return lexer.tokenize(stream);
1649    }
1650  
1651    function search(data, expression) {
1652        var parser = new Parser();
1653        // This needs to be improved.  Both the interpreter and runtime depend on
1654        // each other.  The runtime needs the interpreter to support exprefs.
1655        // There's likely a clean way to avoid the cyclic dependency.
1656        var runtime = new Runtime();
1657        var interpreter = new TreeInterpreter(runtime);
1658        runtime._interpreter = interpreter;
1659        var node = parser.parse(expression);
1660        return interpreter.search(node, data);
1661    }
1662  
1663    exports.tokenize = tokenize;
1664    exports.compile = compile;
1665    exports.search = search;
1666    exports.strictDeepEqual = strictDeepEqual;
1667  })(typeof exports === "undefined" ? this.jmespath = {} : exports);