boto/jmespath — pull request #55 by jamesls (2014-04-09 01:11:36+00:00)
Title: Implement JEP 4: Pipe Expressions

Switch to hand written lexer/parser

This commit removes the dependency of PLY in favor of
a hand written lexer and parser.

The motivation for this was to fully support the new pipe syntax
(JEP 4). In order to do this we needed the high level feature of
being able to stop projections when a '|' symbol was encountered.

This proved difficult because when a projection is needed in the
previous implemention, we'd create a `_Projection` node which contained
the specific semantics for handling projections. It knew that when
we looked up a specific key that it internally needed to map that
key lookup onto each element in the projection.

This meant that in order to stop a projection we needed to find
every `_Projection` instance and convert it so a normal `list` type.
The only way to do this was to recursively crawl through the matched
structure and look for `_Projection` instances.

A better way to do this is to restructure the AST nodes to represent
a projection via a `Projection` AST node. This idea is shamelessly
stolen from the PHP jmespath implementation. For example, given the
expression `foo[*].bar.baz`, the previous AST matched the reference
grammar rule exactly and gave the AST of:

```
SubExpression(
SubExpression(
SubExpression(
Field(foo),
Index(*)),
Field(bar)),
Field(baz))
```

The new AST is:

```
Projection(
Field(foo),
SubExpression(
Field(bar),
Field(baz)))
```

This makes the AST for a pipe straightforward:

```
Pipe(
Projection(
Field(foo),
SubExpression(
Field(bar),
Field(baz))),
IndexExpression(
Identity(),
Index(0)))
```

In terms of implementation, the lexer is a regex based lexer.
We compile the list of regexes of each of the respective tokens
into a single master regex and use that for the lexing process.

The parser is a Pratt parser (top down operator precedence parser),
and follows the original paper's semantics fairly closely. While the
parse module has more info on the algorithm there's a few points of
interest:

* The new grammar that includes projection AST nodes cannot be parsed
with a single token of lookahead. We need LL(2) in order to
distinguish multi-select-list and projections. Specifically given a
`[` token, if we then see `*`, we don't know if we should parse that
as a multi-select list or as a projection (`[*]`).

* Interestingly enough, the fastest implementation was to create a fixed
list of tokens and track the current index. This also makes additional
tokens of lookahead really simple. The previous implementation used
an iterator to look for the next token only when asked. Even though
this new approach requires two passes through the input (one to create
the list of tokens, and through the tokens to create the AST), this
actually turns out to be the fastest implementation.

Performance is drastically improved switching to a handwritten lexer
and parser.

Previously (@7480643df8ad0c99269b1fa6b9e793582bcb7efe):

```
$ python perf/perftest.py
lex_time: 1.10602379, parse_time: 1.45006180ms, search_time: 0.00190735ms description: Basic minimal case name: single_expression
lex_time: 1.11699104, parse_time: 1.37901306ms, search_time: 0.00190735ms description: Basic minimal case name: single_dot_expression
lex_time: 1.04880333, parse_time: 1.40404701ms, search_time: 0.00286102ms description: Basic minimal case name: double_dot_expression
lex_time: 1.05977058, parse_time: 1.42598152ms, search_time: 0.00405312ms description: Basic minimal case name: dot_no_match
lex_time: 1.11579895, parse_time: 1.56807899ms, search_time: 0.00977516ms description: Deeply nested dict name: deep_nesting_10
lex_time: 1.52611732, parse_time: 2.52008438ms, search_time: 0.05292892ms description: Deeply nested dict name: deep_nesting_50
lex_time: 1.07789040, parse_time: 1.47080421ms, search_time: 0.01692772ms description: Multiple wildcards in an expression name: multi_wildcard_field
lex_time: 1.08003616, parse_time: 1.47199631ms, search_time: 0.01382828ms description: Multiple wildcards in an expression name: wildcard_with_index
lex_time: 1.05094910, parse_time: 1.41000748ms, search_time: 0.00691414ms description: Multiple wildcards name: wildcard_with_field_match
lex_time: 1.04999542, parse_time: 1.41096115ms, search_time: 0.00500679ms description: Multiple wildcards name: wildcard_with_field_match2
```

Hand written lexer and parser:

```
$ python perf/perftest.py
lex_time: 0.00882149, parse_time: 0.01788139ms, search_time: 0.00190735ms description: Basic minimal case name: single_expression
lex_time: 0.02598763, parse_time: 0.04196167ms, search_time: 0.00286102ms description: Basic minimal case name: single_dot_expression
lex_time: 0.02384186, parse_time: 0.04792213ms, search_time: 0.00286102ms description: Basic minimal case name: double_dot_expression
lex_time: 0.03099442, parse_time: 0.06079674ms, search_time: 0.00500679ms description: Basic minimal case name: dot_no_match
lex_time: 0.07581711, parse_time: 0.14400482ms, search_time: 0.01287460ms description: Deeply nested dict name: deep_nesting_10
lex_time: 0.37312508, parse_time: 0.69999695ms, search_time: 0.06580353ms description: Deeply nested dict name: deep_nesting_50
lex_time: 0.04816055, parse_time: 0.08702278ms, search_time: 0.01192093ms description: Multiple wildcards in an expression name: multi_wildcard_field
lex_time: 0.04887581, parse_time: 0.08988380ms, search_time: 0.01192093ms description: Multiple wildcards in an expression name: wildcard_with_index
lex_time: 0.02884865, parse_time: 0.05292892ms, search_time: 0.00691414ms description: Multiple wildcards name: wildcard_with_field_match
lex_time: 0.02789497, parse_time: 0.05388260ms, search_time: 0.00691414ms description: Multiple wildcards name: wildcard_with_field_match2
```