Initial distributor implementation

appengine/cmd/dm/distributor/impl/jobsim/parser/parser.go

Index: appengine/cmd/dm/distributor/impl/jobsim/parser/parser.go
diff --git a/appengine/cmd/dm/distributor/impl/jobsim/parser/parser.go b/appengine/cmd/dm/distributor/impl/jobsim/parser/parser.go
new file mode 100644
index 0000000000000000000000000000000000000000..0be6fba160d5872901b82ab83ec670e3ea366f38
--- /dev/null
+++ b/appengine/cmd/dm/distributor/impl/jobsim/parser/parser.go
@@ -0,0 +1,2025 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+package parser
+
+import (
+	"bytes"
+	"errors"
+	"fmt"
+	"io"
+	"io/ioutil"
+	"os"
+	"regexp"
+	"strconv"
+	"strings"
+	"time"
+	"unicode"
+	"unicode/utf8"
+)
+
+type retriesHolder uint64
+type identityHolder uint64
+
+var whitespaceRE = regexp.MustCompile("#[^\n]*\n|\\s+")
+
+// CleanPhrase removes all whitespace and comments from a phrase in preparation
+// for parsing it. The parsers defined in this package only operate on cleaned
+// phrases, and will fail to parse if you provide a phrase with whitespace.
+func CleanPhrase(p string) string {
+	return whitespaceRE.ReplaceAllLiteralString(p, "")
+}
+
+// ParsePhrase is a convenience function for the parser functions in this
+// package to return a typed Phrase object as the result of a string.
+func ParsePhrase(p string) (Phrase, error) {
+	ret, err := Parse("<string>", []byte(p))
+	if err != nil {
+		return nil, err
+	}
+	return ret.(Phrase), nil
+}
+
+var g = &grammar{
+	rules: []*rule{
+		{
+			name: "Overall",
+			pos:  position{line: 32, col: 1, offset: 946},
+			expr: &choiceExpr{
+				pos: position{line: 32, col: 11, offset: 956},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 32, col: 11, offset: 956},
+						run: (*parser).callonOverall2,
+						expr: &seqExpr{
+							pos: position{line: 32, col: 11, offset: 956},
+							exprs: []interface{}{
+								&labeledExpr{
+									pos:   position{line: 32, col: 11, offset: 956},
+									label: "p",
+									expr: &ruleRefExpr{
+										pos:  position{line: 32, col: 13, offset: 958},
+										name: "Phrase",
+									},
+								},
+								&notExpr{
+									pos: position{line: 32, col: 20, offset: 965},
+									expr: &anyMatcher{
+										line: 32, col: 21, offset: 966,
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 34, col: 5, offset: 990},
+						run: (*parser).callonOverall8,
+						expr: &seqExpr{
+							pos: position{line: 34, col: 5, offset: 990},
+							exprs: []interface{}{
+								&labeledExpr{
+									pos:   position{line: 34, col: 5, offset: 990},
+									label: "p",
+									expr: &ruleRefExpr{
+										pos:  position{line: 34, col: 7, offset: 992},
+										name: "Phrase",
+									},
+								},
+								&labeledExpr{
+									pos:   position{line: 34, col: 14, offset: 999},
+									label: "ext",
+									expr: &ruleRefExpr{
+										pos:  position{line: 34, col: 18, offset: 1003},
+										name: "Extra",
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 36, col: 5, offset: 1073},
+						run: (*parser).callonOverall14,
+						expr: &notExpr{
+							pos: position{line: 36, col: 5, offset: 1073},
+							expr: &anyMatcher{
+								line: 36, col: 6, offset: 1074,
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 38, col: 5, offset: 1123},
+						run: (*parser).callonOverall17,
+						expr: &labeledExpr{
+							pos:   position{line: 38, col: 5, offset: 1123},
+							label: "ext",
+							expr: &ruleRefExpr{
+								pos:  position{line: 38, col: 9, offset: 1127},
+								name: "Extra",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Extra",
+			pos:  position{line: 42, col: 1, offset: 1200},
+			expr: &actionExpr{
+				pos: position{line: 42, col: 9, offset: 1208},
+				run: (*parser).callonExtra1,
+				expr: &zeroOrMoreExpr{
+					pos: position{line: 42, col: 9, offset: 1208},
+					expr: &anyMatcher{
+						line: 42, col: 9, offset: 1208,
+					},
+				},
+			},
+		},
+		{
+			name: "Phrase",
+			pos:  position{line: 46, col: 1, offset: 1245},
+			expr: &choiceExpr{
+				pos: position{line: 46, col: 10, offset: 1254},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 46, col: 10, offset: 1254},
+						run: (*parser).callonPhrase2,
+						expr: &labeledExpr{
+							pos:   position{line: 46, col: 10, offset: 1254},
+							label: "ret",
+							expr: &ruleRefExpr{
+								pos:  position{line: 46, col: 14, offset: 1258},
+								name: "ReturnStage",
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 48, col: 5, offset: 1310},
+						run: (*parser).callonPhrase5,
+						expr: &seqExpr{
+							pos: position{line: 48, col: 5, offset: 1310},
+							exprs: []interface{}{
+								&labeledExpr{
+									pos:   position{line: 48, col: 5, offset: 1310},
+									label: "first",
+									expr: &ruleRefExpr{
+										pos:  position{line: 48, col: 11, offset: 1316},
+										name: "Stage",
+									},
+								},
+								&labeledExpr{
+									pos:   position{line: 48, col: 17, offset: 1322},
+									label: "middleI",
+									expr: &zeroOrMoreExpr{
+										pos: position{line: 48, col: 25, offset: 1330},
+										expr: &seqExpr{
+											pos: position{line: 48, col: 26, offset: 1331},
+											exprs: []interface{}{
+												&litMatcher{
+													pos:        position{line: 48, col: 26, offset: 1331},
+													val:        ",",
+													ignoreCase: false,
+												},
+												&ruleRefExpr{
+													pos:  position{line: 48, col: 30, offset: 1335},
+													name: "Stage",
+												},
+											},
+										},
+									},
+								},
+								&labeledExpr{
+									pos:   position{line: 48, col: 38, offset: 1343},
+									label: "retI",
+									expr: &zeroOrOneExpr{
+										pos: position{line: 48, col: 43, offset: 1348},
+										expr: &seqExpr{
+											pos: position{line: 48, col: 44, offset: 1349},
+											exprs: []interface{}{
+												&litMatcher{
+													pos:        position{line: 48, col: 44, offset: 1349},
+													val:        ",",
+													ignoreCase: false,
+												},
+												&ruleRefExpr{
+													pos:  position{line: 48, col: 48, offset: 1353},
+													name: "ReturnStage",
+												},
+											},
+										},
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 70, col: 5, offset: 1791},
+						run: (*parser).callonPhrase19,
+						expr: &seqExpr{
+							pos: position{line: 70, col: 5, offset: 1791},
+							exprs: []interface{}{
+								&litMatcher{
+									pos:        position{line: 70, col: 5, offset: 1791},
+									val:        ",",
+									ignoreCase: false,
+								},
+								&zeroOrMoreExpr{
+									pos: position{line: 70, col: 9, offset: 1795},
+									expr: &anyMatcher{
+										line: 70, col: 9, offset: 1795,
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Stage",
+			pos:  position{line: 74, col: 1, offset: 1868},
+			expr: &actionExpr{
+				pos: position{line: 74, col: 9, offset: 1876},
+				run: (*parser).callonStage1,
+				expr: &labeledExpr{
+					pos:   position{line: 74, col: 9, offset: 1876},
+					label: "s",
+					expr: &choiceExpr{
+						pos: position{line: 74, col: 12, offset: 1879},
+						alternatives: []interface{}{
+							&ruleRefExpr{
+								pos:  position{line: 74, col: 12, offset: 1879},
+								name: "FailureStage",
+							},
+							&ruleRefExpr{
+								pos:  position{line: 74, col: 27, offset: 1894},
+								name: "StallStage",
+							},
+							&ruleRefExpr{
+								pos:  position{line: 74, col: 40, offset: 1907},
+								name: "DepsStage",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "FailureStage",
+			pos:  position{line: 78, col: 1, offset: 1939},
+			expr: &actionExpr{
+				pos: position{line: 78, col: 16, offset: 1954},
+				run: (*parser).callonFailureStage1,
+				expr: &seqExpr{
+					pos: position{line: 78, col: 16, offset: 1954},
+					exprs: []interface{}{
+						&litMatcher{
+							pos:        position{line: 78, col: 16, offset: 1954},
+							val:        "%",
+							ignoreCase: false,
+						},
+						&labeledExpr{
+							pos:   position{line: 78, col: 20, offset: 1958},
+							label: "num",
+							expr: &ruleRefExpr{
+								pos:  position{line: 78, col: 24, offset: 1962},
+								name: "Num",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "StallStage",
+			pos:  position{line: 82, col: 1, offset: 2012},
+			expr: &actionExpr{
+				pos: position{line: 82, col: 14, offset: 2025},
+				run: (*parser).callonStallStage1,
+				expr: &seqExpr{
+					pos: position{line: 82, col: 14, offset: 2025},
+					exprs: []interface{}{
+						&litMatcher{
+							pos:        position{line: 82, col: 14, offset: 2025},
+							val:        "@",
+							ignoreCase: false,
+						},
+						&labeledExpr{
+							pos:   position{line: 82, col: 18, offset: 2029},
+							label: "amt",
+							expr: &ruleRefExpr{
+								pos:  position{line: 82, col: 22, offset: 2033},
+								name: "Duration",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "ReturnStage",
+			pos:  position{line: 86, col: 1, offset: 2093},
+			expr: &actionExpr{
+				pos: position{line: 86, col: 15, offset: 2107},
+				run: (*parser).callonReturnStage1,
+				expr: &seqExpr{
+					pos: position{line: 86, col: 15, offset: 2107},
+					exprs: []interface{}{
+						&litMatcher{
+							pos:        position{line: 86, col: 15, offset: 2107},
+							val:        "=",
+							ignoreCase: false,
+						},
+						&labeledExpr{
+							pos:   position{line: 86, col: 19, offset: 2111},
+							label: "val",
+							expr: &ruleRefExpr{
+								pos:  position{line: 86, col: 23, offset: 2115},
+								name: "Num",
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 86, col: 27, offset: 2119},
+							label: "exp",
+							expr: &zeroOrOneExpr{
+								pos: position{line: 86, col: 31, offset: 2123},
+								expr: &seqExpr{
+									pos: position{line: 86, col: 32, offset: 2124},
+									exprs: []interface{}{
+										&litMatcher{
+											pos:        position{line: 86, col: 32, offset: 2124},
+											val:        "<",
+											ignoreCase: false,
+										},
+										&ruleRefExpr{
+											pos:  position{line: 86, col: 36, offset: 2128},
+											name: "Duration",
+										},
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "DepsStage",
+			pos:  position{line: 94, col: 1, offset: 2287},
+			expr: &choiceExpr{
+				pos: position{line: 94, col: 13, offset: 2299},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 94, col: 13, offset: 2299},
+						run: (*parser).callonDepsStage2,
+						expr: &seqExpr{
+							pos: position{line: 94, col: 13, offset: 2299},
+							exprs: []interface{}{
+								&labeledExpr{
+									pos:   position{line: 94, col: 13, offset: 2299},
+									label: "first",
+									expr: &ruleRefExpr{
+										pos:  position{line: 94, col: 19, offset: 2305},
+										name: "Dependency",
+									},
+								},
+								&labeledExpr{
+									pos:   position{line: 94, col: 30, offset: 2316},
+									label: "restI",
+									expr: &zeroOrMoreExpr{
+										pos: position{line: 94, col: 36, offset: 2322},
+										expr: &seqExpr{
+											pos: position{line: 94, col: 37, offset: 2323},
+											exprs: []interface{}{
+												&litMatcher{
+													pos:        position{line: 94, col: 37, offset: 2323},
+													val:        "&",
+													ignoreCase: false,
+												},
+												&ruleRefExpr{
+													pos:  position{line: 94, col: 41, offset: 2327},
+													name: "Dependency",
+												},
+											},
+										},
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 106, col: 5, offset: 2644},
+						run: (*parser).callonDepsStage11,
+						expr: &seqExpr{
+							pos: position{line: 106, col: 5, offset: 2644},
+							exprs: []interface{}{
+								&litMatcher{
+									pos:        position{line: 106, col: 5, offset: 2644},
+									val:        "&",
+									ignoreCase: false,
+								},
+								&zeroOrMoreExpr{
+									pos: position{line: 106, col: 9, offset: 2648},
+									expr: &anyMatcher{
+										line: 106, col: 9, offset: 2648,
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Dependency",
+			pos:  position{line: 110, col: 1, offset: 2726},
+			expr: &actionExpr{
+				pos: position{line: 110, col: 14, offset: 2739},
+				run: (*parser).callonDependency1,
+				expr: &seqExpr{
+					pos: position{line: 110, col: 14, offset: 2739},
+					exprs: []interface{}{
+						&labeledExpr{
+							pos:   position{line: 110, col: 14, offset: 2739},
+							label: "shards",
+							expr: &zeroOrOneExpr{
+								pos: position{line: 110, col: 21, offset: 2746},
+								expr: &ruleRefExpr{
+									pos:  position{line: 110, col: 21, offset: 2746},
+									name: "Shards",
+								},
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 110, col: 29, offset: 2754},
+							label: "attempts",
+							expr: &zeroOrOneExpr{
+								pos: position{line: 110, col: 38, offset: 2763},
+								expr: &ruleRefExpr{
+									pos:  position{line: 110, col: 38, offset: 2763},
+									name: "Attempts",
+								},
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 110, col: 48, offset: 2773},
+							label: "id",
+							expr: &ruleRefExpr{
+								pos:  position{line: 110, col: 51, offset: 2776},
+								name: "ID",
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 110, col: 54, offset: 2779},
+							label: "options",
+							expr: &zeroOrOneExpr{
+								pos: position{line: 110, col: 62, offset: 2787},
+								expr: &ruleRefExpr{
+									pos:  position{line: 110, col: 62, offset: 2787},
+									name: "Option",
+								},
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 110, col: 70, offset: 2795},
+							label: "subI",
+							expr: &zeroOrOneExpr{
+								pos: position{line: 110, col: 75, offset: 2800},
+								expr: &seqExpr{
+									pos: position{line: 110, col: 77, offset: 2802},
+									exprs: []interface{}{
+										&litMatcher{
+											pos:        position{line: 110, col: 77, offset: 2802},
+											val:        "(",
+											ignoreCase: false,
+										},
+										&ruleRefExpr{
+											pos:  position{line: 110, col: 81, offset: 2806},
+											name: "Phrase",
+										},
+										&litMatcher{
+											pos:        position{line: 110, col: 88, offset: 2813},
+											val:        ")",
+											ignoreCase: false,
+										},
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Option",
+			pos:  position{line: 144, col: 1, offset: 3446},
+			expr: &choiceExpr{
+				pos: position{line: 144, col: 10, offset: 3455},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 144, col: 10, offset: 3455},
+						run: (*parser).callonOption2,
+						expr: &seqExpr{
+							pos: position{line: 144, col: 10, offset: 3455},
+							exprs: []interface{}{
+								&litMatcher{
+									pos:        position{line: 144, col: 10, offset: 3455},
+									val:        "+",
+									ignoreCase: false,
+								},
+								&labeledExpr{
+									pos:   position{line: 144, col: 14, offset: 3459},
+									label: "num",
+									expr: &ruleRefExpr{
+										pos:  position{line: 144, col: 18, offset: 3463},
+										name: "Num",
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 146, col: 5, offset: 3516},
+						run: (*parser).callonOption7,
+						expr: &seqExpr{
+							pos: position{line: 146, col: 5, offset: 3516},
+							exprs: []interface{}{
+								&litMatcher{
+									pos:        position{line: 146, col: 5, offset: 3516},
+									val:        "^",
+									ignoreCase: false,
+								},
+								&labeledExpr{
+									pos:   position{line: 146, col: 9, offset: 3520},
+									label: "num",
+									expr: &ruleRefExpr{
+										pos:  position{line: 146, col: 13, offset: 3524},
+										name: "Num",
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Shards",
+			pos:  position{line: 150, col: 1, offset: 3577},
+			expr: &actionExpr{
+				pos: position{line: 150, col: 10, offset: 3586},
+				run: (*parser).callonShards1,
+				expr: &seqExpr{
+					pos: position{line: 150, col: 10, offset: 3586},
+					exprs: []interface{}{
+						&litMatcher{
+							pos:        position{line: 150, col: 10, offset: 3586},
+							val:        "{",
+							ignoreCase: false,
+						},
+						&labeledExpr{
+							pos:   position{line: 150, col: 14, offset: 3590},
+							label: "num",
+							expr: &ruleRefExpr{
+								pos:  position{line: 150, col: 18, offset: 3594},
+								name: "Num",
+							},
+						},
+						&litMatcher{
+							pos:        position{line: 150, col: 22, offset: 3598},
+							val:        "}",
+							ignoreCase: false,
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Attempts",
+			pos:  position{line: 154, col: 1, offset: 3625},
+			expr: &actionExpr{
+				pos: position{line: 154, col: 12, offset: 3636},
+				run: (*parser).callonAttempts1,
+				expr: &seqExpr{
+					pos: position{line: 154, col: 12, offset: 3636},
+					exprs: []interface{}{
+						&litMatcher{
+							pos:        position{line: 154, col: 12, offset: 3636},
+							val:        "[",
+							ignoreCase: false,
+						},
+						&labeledExpr{
+							pos:   position{line: 154, col: 16, offset: 3640},
+							label: "rs",
+							expr: &ruleRefExpr{
+								pos:  position{line: 154, col: 19, offset: 3643},
+								name: "RangeSlice",
+							},
+						},
+						&litMatcher{
+							pos:        position{line: 154, col: 30, offset: 3654},
+							val:        "]",
+							ignoreCase: false,
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "RangeSlice",
+			pos:  position{line: 158, col: 1, offset: 3680},
+			expr: &actionExpr{
+				pos: position{line: 158, col: 14, offset: 3693},
+				run: (*parser).callonRangeSlice1,
+				expr: &seqExpr{
+					pos: position{line: 158, col: 14, offset: 3693},
+					exprs: []interface{}{
+						&labeledExpr{
+							pos:   position{line: 158, col: 14, offset: 3693},
+							label: "firstI",
+							expr: &ruleRefExpr{
+								pos:  position{line: 158, col: 21, offset: 3700},
+								name: "Range",
+							},
+						},
+						&labeledExpr{
+							pos:   position{line: 158, col: 27, offset: 3706},
+							label: "restI",
+							expr: &zeroOrMoreExpr{
+								pos: position{line: 158, col: 33, offset: 3712},
+								expr: &seqExpr{
+									pos: position{line: 158, col: 34, offset: 3713},
+									exprs: []interface{}{
+										&litMatcher{
+											pos:        position{line: 158, col: 34, offset: 3713},
+											val:        ",",
+											ignoreCase: false,
+										},
+										&ruleRefExpr{
+											pos:  position{line: 158, col: 38, offset: 3717},
+											name: "Range",
+										},
+									},
+								},
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Range",
+			pos:  position{line: 170, col: 1, offset: 3950},
+			expr: &choiceExpr{
+				pos: position{line: 170, col: 9, offset: 3958},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 170, col: 9, offset: 3958},
+						run: (*parser).callonRange2,
+						expr: &seqExpr{
+							pos: position{line: 170, col: 9, offset: 3958},
+							exprs: []interface{}{
+								&labeledExpr{
+									pos:   position{line: 170, col: 9, offset: 3958},
+									label: "loI",
+									expr: &ruleRefExpr{
+										pos:  position{line: 170, col: 13, offset: 3962},
+										name: "Num",
+									},
+								},
+								&litMatcher{
+									pos:        position{line: 170, col: 17, offset: 3966},
+									val:        "-",
+									ignoreCase: false,
+								},
+								&labeledExpr{
+									pos:   position{line: 170, col: 21, offset: 3970},
+									label: "hiI",
+									expr: &ruleRefExpr{
+										pos:  position{line: 170, col: 25, offset: 3974},
+										name: "Num",
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 179, col: 5, offset: 4149},
+						run: (*parser).callonRange9,
+						expr: &labeledExpr{
+							pos:   position{line: 179, col: 5, offset: 4149},
+							label: "num",
+							expr: &ruleRefExpr{
+								pos:  position{line: 179, col: 9, offset: 4153},
+								name: "Num",
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "Duration",
+			pos:  position{line: 183, col: 1, offset: 4199},
+			expr: &actionExpr{
+				pos: position{line: 183, col: 12, offset: 4210},
+				run: (*parser).callonDuration1,
+				expr: &labeledExpr{
+					pos:   position{line: 183, col: 12, offset: 4210},
+					label: "num",
+					expr: &ruleRefExpr{
+						pos:  position{line: 183, col: 16, offset: 4214},
+						name: "Num",
+					},
+				},
+			},
+		},
+		{
+			name: "Num",
+			pos:  position{line: 187, col: 1, offset: 4279},
+			expr: &choiceExpr{
+				pos: position{line: 187, col: 7, offset: 4285},
+				alternatives: []interface{}{
+					&actionExpr{
+						pos: position{line: 187, col: 7, offset: 4285},
+						run: (*parser).callonNum2,
+						expr: &litMatcher{
+							pos:        position{line: 187, col: 7, offset: 4285},
+							val:        "0",
+							ignoreCase: false,
+						},
+					},
+					&actionExpr{
+						pos: position{line: 189, col: 5, offset: 4349},
+						run: (*parser).callonNum4,
+						expr: &seqExpr{
+							pos: position{line: 189, col: 5, offset: 4349},
+							exprs: []interface{}{
+								&charClassMatcher{
+									pos:        position{line: 189, col: 5, offset: 4349},
+									val:        "[1-9]",
+									ranges:     []rune{'1', '9'},
+									ignoreCase: false,
+									inverted:   false,
+								},
+								&zeroOrMoreExpr{
+									pos: position{line: 189, col: 10, offset: 4354},
+									expr: &charClassMatcher{
+										pos:        position{line: 189, col: 10, offset: 4354},
+										val:        "[0-9]",
+										ranges:     []rune{'0', '9'},
+										ignoreCase: false,
+										inverted:   false,
+									},
+								},
+							},
+						},
+					},
+					&actionExpr{
+						pos: position{line: 191, col: 5, offset: 4418},
+						run: (*parser).callonNum9,
+						expr: &zeroOrMoreExpr{
+							pos: position{line: 191, col: 5, offset: 4418},
+							expr: &anyMatcher{
+								line: 191, col: 5, offset: 4418,
+							},
+						},
+					},
+				},
+			},
+		},
+		{
+			name: "ID",
+			pos:  position{line: 195, col: 1, offset: 4494},
+			expr: &actionExpr{
+				pos: position{line: 195, col: 6, offset: 4499},
+				run: (*parser).callonID1,
+				expr: &oneOrMoreExpr{
+					pos: position{line: 195, col: 6, offset: 4499},
+					expr: &charClassMatcher{
+						pos:        position{line: 195, col: 6, offset: 4499},
+						val:        "[a-zA-Z'_]",
+						chars:      []rune{'\'', '_'},
+						ranges:     []rune{'a', 'z', 'A', 'Z'},
+						ignoreCase: false,
+						inverted:   false,
+					},
+				},
+			},
+		},
+	},
+}
+
+func (c *current) onOverall2(p interface{}) (interface{}, error) {
+	return p, nil
+}
+
+func (p *parser) callonOverall2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOverall2(stack["p"])
+}
+
+func (c *current) onOverall8(p, ext interface{}) (interface{}, error) {
+	return nil, fmt.Errorf("found extra: %q", ext.(string))
+}
+
+func (p *parser) callonOverall8() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOverall8(stack["p"], stack["ext"])
+}
+
+func (c *current) onOverall14() (interface{}, error) {
+	return nil, fmt.Errorf("empty phrase")
+}
+
+func (p *parser) callonOverall14() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOverall14()
+}
+
+func (c *current) onOverall17(ext interface{}) (interface{}, error) {
+	return nil, fmt.Errorf("expected phrase: %q", ext.(string))
+}
+
+func (p *parser) callonOverall17() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOverall17(stack["ext"])
+}
+
+func (c *current) onExtra1() (interface{}, error) {
+	return string(c.text), nil
+}
+
+func (p *parser) callonExtra1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onExtra1()
+}
+
+func (c *current) onPhrase2(ret interface{}) (interface{}, error) {
+	return Phrase{ret.(Stage)}, nil
+}
+
+func (p *parser) callonPhrase2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onPhrase2(stack["ret"])
+}
+
+func (c *current) onPhrase5(first, middleI, retI interface{}) (interface{}, error) {
+	middle, _ := middleI.([]interface{})
+	retStage, _ := retI.([]interface{})
+
+	amt := 1
+	if middle != nil {
+		amt += len(middle)
+	}
+	if retStage != nil {
+		amt++
+	}
+
+	ret := make(Phrase, 0, amt)
+	ret = append(ret, first.(Stage))
+	for _, itm := range middle {
+		ret = append(ret, itm.([]interface{})[1].(Stage))
+	}
+	if retStage != nil {
+		ret = append(ret, retStage[1].(Stage))
+	}
+
+	return ret, nil
+}
+
+func (p *parser) callonPhrase5() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onPhrase5(stack["first"], stack["middleI"], stack["retI"])
+}
+
+func (c *current) onPhrase19() (interface{}, error) {
+	return nil, fmt.Errorf("expected stage in %q", string(c.text))
+}
+
+func (p *parser) callonPhrase19() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onPhrase19()
+}
+
+func (c *current) onStage1(s interface{}) (interface{}, error) {
+	return s, nil
+}
+
+func (p *parser) callonStage1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onStage1(stack["s"])
+}
+
+func (c *current) onFailureStage1(num interface{}) (interface{}, error) {
+	return FailureStage(num.(uint64)), nil
+}
+
+func (p *parser) callonFailureStage1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onFailureStage1(stack["num"])
+}
+
+func (c *current) onStallStage1(amt interface{}) (interface{}, error) {
+	return StallStage(amt.(time.Duration)), nil
+}
+
+func (p *parser) callonStallStage1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onStallStage1(stack["amt"])
+}
+
+func (c *current) onReturnStage1(val, exp interface{}) (interface{}, error) {
+	ret := &ReturnStage{Value: val.(uint64)}
+	if exp != nil {
+		ret.Expiration = exp.([]interface{})[1].(time.Duration)
+	}
+	return ret, nil
+}
+
+func (p *parser) callonReturnStage1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onReturnStage1(stack["val"], stack["exp"])
+}
+
+func (c *current) onDepsStage2(first, restI interface{}) (interface{}, error) {
+	rest, _ := restI.([]interface{})
+
+	if rest == nil {
+		return DepsStage{first.(*Dependency)}, nil
+	}
+	ret := make(DepsStage, 0, 1+len(rest))
+	ret = append(ret, first.(*Dependency))
+	for _, itm := range rest {
+		ret = append(ret, itm.([]interface{})[1].(*Dependency))
+	}
+	return ret, nil
+}
+
+func (p *parser) callonDepsStage2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onDepsStage2(stack["first"], stack["restI"])
+}
+
+func (c *current) onDepsStage11() (interface{}, error) {
+	return nil, fmt.Errorf("expected dependency in %q", string(c.text))
+}
+
+func (p *parser) callonDepsStage11() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onDepsStage11()
+}
+
+func (c *current) onDependency1(shards, attempts, id, options, subI interface{}) (interface{}, error) {
+	ret := &Dependency{Name: id.(string)}
+
+	if shards != nil {
+		ret.ShardCount = shards.(uint64)
+	}
+
+	if attempts != nil {
+		ret.AttemptNums = attempts.(RangeSlice)
+	}
+
+	if options != nil {
+		switch x := options.(type) {
+		case retriesHolder:
+			if attempts != nil {
+				return nil, fmt.Errorf(
+					"in %q: retries are incompatible with specified Attempts",
+					string(c.text))
+			}
+			ret.Retries = uint64(x)
+
+		case identityHolder:
+			ret.Uniq = uint64(x)
+		}
+	}
+
+	sub, _ := subI.([]interface{})
+	if sub != nil {
+		ret.Substages = sub[1].(Phrase)
+	}
+
+	return ret, nil
+}
+
+func (p *parser) callonDependency1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onDependency1(stack["shards"], stack["attempts"], stack["id"], stack["options"], stack["subI"])
+}
+
+func (c *current) onOption2(num interface{}) (interface{}, error) {
+	return retriesHolder(num.(uint64)), nil
+}
+
+func (p *parser) callonOption2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOption2(stack["num"])
+}
+
+func (c *current) onOption7(num interface{}) (interface{}, error) {
+	return identityHolder(num.(uint64)), nil
+}
+
+func (p *parser) callonOption7() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onOption7(stack["num"])
+}
+
+func (c *current) onShards1(num interface{}) (interface{}, error) {
+	return num, nil
+}
+
+func (p *parser) callonShards1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onShards1(stack["num"])
+}
+
+func (c *current) onAttempts1(rs interface{}) (interface{}, error) {
+	return rs, nil
+}
+
+func (p *parser) callonAttempts1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onAttempts1(stack["rs"])
+}
+
+func (c *current) onRangeSlice1(firstI, restI interface{}) (interface{}, error) {
+	rest, _ := restI.([]interface{})
+
+	ret := make(RangeSlice, 0, 1+len(rest))
+	ret = append(ret, firstI.(Range))
+	for _, itm := range rest {
+		ret = append(ret, itm.([]interface{})[1].(Range))
+	}
+
+	return ret, nil
+}
+
+func (p *parser) callonRangeSlice1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onRangeSlice1(stack["firstI"], stack["restI"])
+}
+
+func (c *current) onRange2(loI, hiI interface{}) (interface{}, error) {
+	lo := loI.(uint64)
+	hi := hiI.(uint64)
+
+	if lo >= hi {
+		return nil, fmt.Errorf("invalid range %q: lo >= hi", string(c.text))
+	}
+
+	return Range{lo, hi}, nil
+}
+
+func (p *parser) callonRange2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onRange2(stack["loI"], stack["hiI"])
+}
+
+func (c *current) onRange9(num interface{}) (interface{}, error) {
+	return Range{num.(uint64), 0}, nil
+}
+
+func (p *parser) callonRange9() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onRange9(stack["num"])
+}
+
+func (c *current) onDuration1(num interface{}) (interface{}, error) {
+	return time.Second * time.Duration(num.(uint64)), nil
+}
+
+func (p *parser) callonDuration1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onDuration1(stack["num"])
+}
+
+func (c *current) onNum2() (interface{}, error) {
+	return nil, fmt.Errorf("zero value not acceptable")
+}
+
+func (p *parser) callonNum2() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onNum2()
+}
+
+func (c *current) onNum4() (interface{}, error) {
+	return strconv.ParseUint(string(c.text), 10, 64)
+}
+
+func (p *parser) callonNum4() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onNum4()
+}
+
+func (c *current) onNum9() (interface{}, error) {
+	return nil, fmt.Errorf("expected number, got %q", string(c.text))
+}
+
+func (p *parser) callonNum9() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onNum9()
+}
+
+func (c *current) onID1() (interface{}, error) {
+	return string(c.text), nil
+}
+
+func (p *parser) callonID1() (interface{}, error) {
+	stack := p.vstack[len(p.vstack)-1]
+	_ = stack
+	return p.cur.onID1()
+}
+
+var (
+	// errNoRule is returned when the grammar to parse has no rule.
+	errNoRule = errors.New("grammar has no rule")
+
+	// errInvalidEncoding is returned when the source is not properly
+	// utf8-encoded.
+	errInvalidEncoding = errors.New("invalid encoding")
+
+	// errNoMatch is returned if no match could be found.
+	errNoMatch = errors.New("no match found")
+)
+
+// Option is a function that can set an option on the parser. It returns
+// the previous setting as an Option.
+type Option func(*parser) Option
+
+// Debug creates an Option to set the debug flag to b. When set to true,
+// debugging information is printed to stdout while parsing.
+//
+// The default is false.
+func Debug(b bool) Option {
+	return func(p *parser) Option {
+		old := p.debug
+		p.debug = b
+		return Debug(old)
+	}
+}
+
+// Memoize creates an Option to set the memoize flag to b. When set to true,
+// the parser will cache all results so each expression is evaluated only
+// once. This guarantees linear parsing time even for pathological cases,
+// at the expense of more memory and slower times for typical cases.
+//
+// The default is false.
+func Memoize(b bool) Option {
+	return func(p *parser) Option {
+		old := p.memoize
+		p.memoize = b
+		return Memoize(old)
+	}
+}
+
+// Recover creates an Option to set the recover flag to b. When set to
+// true, this causes the parser to recover from panics and convert it
+// to an error. Setting it to false can be useful while debugging to
+// access the full stack trace.
+//
+// The default is true.
+func Recover(b bool) Option {
+	return func(p *parser) Option {
+		old := p.recover
+		p.recover = b
+		return Recover(old)
+	}
+}
+
+// ParseFile parses the file identified by filename.
+func ParseFile(filename string, opts ...Option) (interface{}, error) {
+	f, err := os.Open(filename)
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+	return ParseReader(filename, f, opts...)
+}
+
+// ParseReader parses the data from r using filename as information in the
+// error messages.
+func ParseReader(filename string, r io.Reader, opts ...Option) (interface{}, error) {
+	b, err := ioutil.ReadAll(r)
+	if err != nil {
+		return nil, err
+	}
+
+	return Parse(filename, b, opts...)
+}
+
+// Parse parses the data from b using filename as information in the
+// error messages.
+func Parse(filename string, b []byte, opts ...Option) (interface{}, error) {
+	return newParser(filename, b, opts...).parse(g)
+}
+
+// position records a position in the text.
+type position struct {
+	line, col, offset int
+}
+
+func (p position) String() string {
+	return fmt.Sprintf("%d:%d [%d]", p.line, p.col, p.offset)
+}
+
+// savepoint stores all state required to go back to this point in the
+// parser.
+type savepoint struct {
+	position
+	rn rune
+	w  int
+}
+
+type current struct {
+	pos  position // start position of the match
+	text []byte   // raw text of the match
+}
+
+// the AST types...
+
+type grammar struct {
+	pos   position
+	rules []*rule
+}
+
+type rule struct {
+	pos         position
+	name        string
+	displayName string
+	expr        interface{}
+}
+
+type choiceExpr struct {
+	pos          position
+	alternatives []interface{}
+}
+
+type actionExpr struct {
+	pos  position
+	expr interface{}
+	run  func(*parser) (interface{}, error)
+}
+
+type seqExpr struct {
+	pos   position
+	exprs []interface{}
+}
+
+type labeledExpr struct {
+	pos   position
+	label string
+	expr  interface{}
+}
+
+type expr struct {
+	pos  position
+	expr interface{}
+}
+
+type andExpr expr
+type notExpr expr
+type zeroOrOneExpr expr
+type zeroOrMoreExpr expr
+type oneOrMoreExpr expr
+
+type ruleRefExpr struct {
+	pos  position
+	name string
+}
+
+type andCodeExpr struct {
+	pos position
+	run func(*parser) (bool, error)
+}
+
+type notCodeExpr struct {
+	pos position
+	run func(*parser) (bool, error)
+}
+
+type litMatcher struct {
+	pos        position
+	val        string
+	ignoreCase bool
+}
+
+type charClassMatcher struct {
+	pos        position
+	val        string
+	chars      []rune
+	ranges     []rune
+	classes    []*unicode.RangeTable
+	ignoreCase bool
+	inverted   bool
+}
+
+type anyMatcher position
+
+// errList cumulates the errors found by the parser.
+type errList []error
+
+func (e *errList) add(err error) {
+	*e = append(*e, err)
+}
+
+func (e errList) err() error {
+	if len(e) == 0 {
+		return nil
+	}
+	e.dedupe()
+	return e
+}
+
+func (e *errList) dedupe() {
+	var cleaned []error
+	set := make(map[string]bool)
+	for _, err := range *e {
+		if msg := err.Error(); !set[msg] {
+			set[msg] = true
+			cleaned = append(cleaned, err)
+		}
+	}
+	*e = cleaned
+}
+
+func (e errList) Error() string {
+	switch len(e) {
+	case 0:
+		return ""
+	case 1:
+		return e[0].Error()
+	default:
+		var buf bytes.Buffer
+
+		for i, err := range e {
+			if i > 0 {
+				buf.WriteRune('\n')
+			}
+			buf.WriteString(err.Error())
+		}
+		return buf.String()
+	}
+}
+
+// parserError wraps an error with a prefix indicating the rule in which
+// the error occurred. The original error is stored in the Inner field.
+type parserError struct {
+	Inner  error
+	pos    position
+	prefix string
+}
+
+// Error returns the error message.
+func (p *parserError) Error() string {
+	return p.prefix + ": " + p.Inner.Error()
+}
+
+// newParser creates a parser with the specified input source and options.
+func newParser(filename string, b []byte, opts ...Option) *parser {
+	p := &parser{
+		filename: filename,
+		errs:     new(errList),
+		data:     b,
+		pt:       savepoint{position: position{line: 1}},
+		recover:  true,
+	}
+	p.setOptions(opts)
+	return p
+}
+
+// setOptions applies the options to the parser.
+func (p *parser) setOptions(opts []Option) {
+	for _, opt := range opts {
+		opt(p)
+	}
+}
+
+type resultTuple struct {
+	v   interface{}
+	b   bool
+	end savepoint
+}
+
+type parser struct {
+	filename string
+	pt       savepoint
+	cur      current
+
+	data []byte
+	errs *errList
+
+	recover bool
+	debug   bool
+	depth   int
+
+	memoize bool
+	// memoization table for the packrat algorithm:
+	// map[offset in source] map[expression or rule] {value, match}
+	memo map[int]map[interface{}]resultTuple
+
+	// rules table, maps the rule identifier to the rule node
+	rules map[string]*rule
+	// variables stack, map of label to value
+	vstack []map[string]interface{}
+	// rule stack, allows identification of the current rule in errors
+	rstack []*rule
+
+	// stats
+	exprCnt int
+}
+
+// push a variable set on the vstack.
+func (p *parser) pushV() {
+	if cap(p.vstack) == len(p.vstack) {
+		// create new empty slot in the stack
+		p.vstack = append(p.vstack, nil)
+	} else {
+		// slice to 1 more
+		p.vstack = p.vstack[:len(p.vstack)+1]
+	}
+
+	// get the last args set
+	m := p.vstack[len(p.vstack)-1]
+	if m != nil && len(m) == 0 {
+		// empty map, all good
+		return
+	}
+
+	m = make(map[string]interface{})
+	p.vstack[len(p.vstack)-1] = m
+}
+
+// pop a variable set from the vstack.
+func (p *parser) popV() {
+	// if the map is not empty, clear it
+	m := p.vstack[len(p.vstack)-1]
+	if len(m) > 0 {
+		// GC that map
+		p.vstack[len(p.vstack)-1] = nil
+	}
+	p.vstack = p.vstack[:len(p.vstack)-1]
+}
+
+func (p *parser) print(prefix, s string) string {
+	if !p.debug {
+		return s
+	}
+
+	fmt.Printf("%s %d:%d:%d: %s [%#U]\n",
+		prefix, p.pt.line, p.pt.col, p.pt.offset, s, p.pt.rn)
+	return s
+}
+
+func (p *parser) in(s string) string {
+	p.depth++
+	return p.print(strings.Repeat(" ", p.depth)+">", s)
+}
+
+func (p *parser) out(s string) string {
+	p.depth--
+	return p.print(strings.Repeat(" ", p.depth)+"<", s)
+}
+
+func (p *parser) addErr(err error) {
+	p.addErrAt(err, p.pt.position)
+}
+
+func (p *parser) addErrAt(err error, pos position) {
+	var buf bytes.Buffer
+	if p.filename != "" {
+		buf.WriteString(p.filename)
+	}
+	if buf.Len() > 0 {
+		buf.WriteString(":")
+	}
+	buf.WriteString(fmt.Sprintf("%d:%d (%d)", pos.line, pos.col, pos.offset))
+	if len(p.rstack) > 0 {
+		if buf.Len() > 0 {
+			buf.WriteString(": ")
+		}
+		rule := p.rstack[len(p.rstack)-1]
+		if rule.displayName != "" {
+			buf.WriteString("rule " + rule.displayName)
+		} else {
+			buf.WriteString("rule " + rule.name)
+		}
+	}
+	pe := &parserError{Inner: err, prefix: buf.String()}
+	p.errs.add(pe)
+}
+
+// read advances the parser to the next rune.
+func (p *parser) read() {
+	p.pt.offset += p.pt.w
+	rn, n := utf8.DecodeRune(p.data[p.pt.offset:])
+	p.pt.rn = rn
+	p.pt.w = n
+	p.pt.col++
+	if rn == '\n' {
+		p.pt.line++
+		p.pt.col = 0
+	}
+
+	if rn == utf8.RuneError {
+		if n > 0 {
+			p.addErr(errInvalidEncoding)
+		}
+	}
+}
+
+// restore parser position to the savepoint pt.
+func (p *parser) restore(pt savepoint) {
+	if p.debug {
+		defer p.out(p.in("restore"))
+	}
+	if pt.offset == p.pt.offset {
+		return
+	}
+	p.pt = pt
+}
+
+// get the slice of bytes from the savepoint start to the current position.
+func (p *parser) sliceFrom(start savepoint) []byte {
+	return p.data[start.position.offset:p.pt.position.offset]
+}
+
+func (p *parser) getMemoized(node interface{}) (resultTuple, bool) {
+	if len(p.memo) == 0 {
+		return resultTuple{}, false
+	}
+	m := p.memo[p.pt.offset]
+	if len(m) == 0 {
+		return resultTuple{}, false
+	}
+	res, ok := m[node]
+	return res, ok
+}
+
+func (p *parser) setMemoized(pt savepoint, node interface{}, tuple resultTuple) {
+	if p.memo == nil {
+		p.memo = make(map[int]map[interface{}]resultTuple)
+	}
+	m := p.memo[pt.offset]
+	if m == nil {
+		m = make(map[interface{}]resultTuple)
+		p.memo[pt.offset] = m
+	}
+	m[node] = tuple
+}
+
+func (p *parser) buildRulesTable(g *grammar) {
+	p.rules = make(map[string]*rule, len(g.rules))
+	for _, r := range g.rules {
+		p.rules[r.name] = r
+	}
+}
+
+func (p *parser) parse(g *grammar) (val interface{}, err error) {
+	if len(g.rules) == 0 {
+		p.addErr(errNoRule)
+		return nil, p.errs.err()
+	}
+
+	// TODO : not super critical but this could be generated
+	p.buildRulesTable(g)
+
+	if p.recover {
+		// panic can be used in action code to stop parsing immediately
+		// and return the panic as an error.
+		defer func() {
+			if e := recover(); e != nil {
+				if p.debug {
+					defer p.out(p.in("panic handler"))
+				}
+				val = nil
+				switch e := e.(type) {
+				case error:
+					p.addErr(e)
+				default:
+					p.addErr(fmt.Errorf("%v", e))
+				}
+				err = p.errs.err()
+			}
+		}()
+	}
+
+	// start rule is rule [0]
+	p.read() // advance to first rune
+	val, ok := p.parseRule(g.rules[0])
+	if !ok {
+		if len(*p.errs) == 0 {
+			// make sure this doesn't go out silently
+			p.addErr(errNoMatch)
+		}
+		return nil, p.errs.err()
+	}
+	return val, p.errs.err()
+}
+
+func (p *parser) parseRule(rule *rule) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseRule " + rule.name))
+	}
+
+	if p.memoize {
+		res, ok := p.getMemoized(rule)
+		if ok {
+			p.restore(res.end)
+			return res.v, res.b
+		}
+	}
+
+	start := p.pt
+	p.rstack = append(p.rstack, rule)
+	p.pushV()
+	val, ok := p.parseExpr(rule.expr)
+	p.popV()
+	p.rstack = p.rstack[:len(p.rstack)-1]
+	if ok && p.debug {
+		p.print(strings.Repeat(" ", p.depth)+"MATCH", string(p.sliceFrom(start)))
+	}
+
+	if p.memoize {
+		p.setMemoized(start, rule, resultTuple{val, ok, p.pt})
+	}
+	return val, ok
+}
+
+func (p *parser) parseExpr(expr interface{}) (interface{}, bool) {
+	var pt savepoint
+	var ok bool
+
+	if p.memoize {
+		res, ok := p.getMemoized(expr)
+		if ok {
+			p.restore(res.end)
+			return res.v, res.b
+		}
+		pt = p.pt
+	}
+
+	p.exprCnt++
+	var val interface{}
+	switch expr := expr.(type) {
+	case *actionExpr:
+		val, ok = p.parseActionExpr(expr)
+	case *andCodeExpr:
+		val, ok = p.parseAndCodeExpr(expr)
+	case *andExpr:
+		val, ok = p.parseAndExpr(expr)
+	case *anyMatcher:
+		val, ok = p.parseAnyMatcher(expr)
+	case *charClassMatcher:
+		val, ok = p.parseCharClassMatcher(expr)
+	case *choiceExpr:
+		val, ok = p.parseChoiceExpr(expr)
+	case *labeledExpr:
+		val, ok = p.parseLabeledExpr(expr)
+	case *litMatcher:
+		val, ok = p.parseLitMatcher(expr)
+	case *notCodeExpr:
+		val, ok = p.parseNotCodeExpr(expr)
+	case *notExpr:
+		val, ok = p.parseNotExpr(expr)
+	case *oneOrMoreExpr:
+		val, ok = p.parseOneOrMoreExpr(expr)
+	case *ruleRefExpr:
+		val, ok = p.parseRuleRefExpr(expr)
+	case *seqExpr:
+		val, ok = p.parseSeqExpr(expr)
+	case *zeroOrMoreExpr:
+		val, ok = p.parseZeroOrMoreExpr(expr)
+	case *zeroOrOneExpr:
+		val, ok = p.parseZeroOrOneExpr(expr)
+	default:
+		panic(fmt.Sprintf("unknown expression type %T", expr))
+	}
+	if p.memoize {
+		p.setMemoized(pt, expr, resultTuple{val, ok, p.pt})
+	}
+	return val, ok
+}
+
+func (p *parser) parseActionExpr(act *actionExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseActionExpr"))
+	}
+
+	start := p.pt
+	val, ok := p.parseExpr(act.expr)
+	if ok {
+		p.cur.pos = start.position
+		p.cur.text = p.sliceFrom(start)
+		actVal, err := act.run(p)
+		if err != nil {
+			p.addErrAt(err, start.position)
+		}
+		val = actVal
+	}
+	if ok && p.debug {
+		p.print(strings.Repeat(" ", p.depth)+"MATCH", string(p.sliceFrom(start)))
+	}
+	return val, ok
+}
+
+func (p *parser) parseAndCodeExpr(and *andCodeExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseAndCodeExpr"))
+	}
+
+	ok, err := and.run(p)
+	if err != nil {
+		p.addErr(err)
+	}
+	return nil, ok
+}
+
+func (p *parser) parseAndExpr(and *andExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseAndExpr"))
+	}
+
+	pt := p.pt
+	p.pushV()
+	_, ok := p.parseExpr(and.expr)
+	p.popV()
+	p.restore(pt)
+	return nil, ok
+}
+
+func (p *parser) parseAnyMatcher(any *anyMatcher) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseAnyMatcher"))
+	}
+
+	if p.pt.rn != utf8.RuneError {
+		start := p.pt
+		p.read()
+		return p.sliceFrom(start), true
+	}
+	return nil, false
+}
+
+func (p *parser) parseCharClassMatcher(chr *charClassMatcher) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseCharClassMatcher"))
+	}
+
+	cur := p.pt.rn
+	// can't match EOF
+	if cur == utf8.RuneError {
+		return nil, false
+	}
+	start := p.pt
+	if chr.ignoreCase {
+		cur = unicode.ToLower(cur)
+	}
+
+	// try to match in the list of available chars
+	for _, rn := range chr.chars {
+		if rn == cur {
+			if chr.inverted {
+				return nil, false
+			}
+			p.read()
+			return p.sliceFrom(start), true
+		}
+	}
+
+	// try to match in the list of ranges
+	for i := 0; i < len(chr.ranges); i += 2 {
+		if cur >= chr.ranges[i] && cur <= chr.ranges[i+1] {
+			if chr.inverted {
+				return nil, false
+			}
+			p.read()
+			return p.sliceFrom(start), true
+		}
+	}
+
+	// try to match in the list of Unicode classes
+	for _, cl := range chr.classes {
+		if unicode.Is(cl, cur) {
+			if chr.inverted {
+				return nil, false
+			}
+			p.read()
+			return p.sliceFrom(start), true
+		}
+	}
+
+	if chr.inverted {
+		p.read()
+		return p.sliceFrom(start), true
+	}
+	return nil, false
+}
+
+func (p *parser) parseChoiceExpr(ch *choiceExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseChoiceExpr"))
+	}
+
+	for _, alt := range ch.alternatives {
+		p.pushV()
+		val, ok := p.parseExpr(alt)
+		p.popV()
+		if ok {
+			return val, ok
+		}
+	}
+	return nil, false
+}
+
+func (p *parser) parseLabeledExpr(lab *labeledExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseLabeledExpr"))
+	}
+
+	p.pushV()
+	val, ok := p.parseExpr(lab.expr)
+	p.popV()
+	if ok && lab.label != "" {
+		m := p.vstack[len(p.vstack)-1]
+		m[lab.label] = val
+	}
+	return val, ok
+}
+
+func (p *parser) parseLitMatcher(lit *litMatcher) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseLitMatcher"))
+	}
+
+	start := p.pt
+	for _, want := range lit.val {
+		cur := p.pt.rn
+		if lit.ignoreCase {
+			cur = unicode.ToLower(cur)
+		}
+		if cur != want {
+			p.restore(start)
+			return nil, false
+		}
+		p.read()
+	}
+	return p.sliceFrom(start), true
+}
+
+func (p *parser) parseNotCodeExpr(not *notCodeExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseNotCodeExpr"))
+	}
+
+	ok, err := not.run(p)
+	if err != nil {
+		p.addErr(err)
+	}
+	return nil, !ok
+}
+
+func (p *parser) parseNotExpr(not *notExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseNotExpr"))
+	}
+
+	pt := p.pt
+	p.pushV()
+	_, ok := p.parseExpr(not.expr)
+	p.popV()
+	p.restore(pt)
+	return nil, !ok
+}
+
+func (p *parser) parseOneOrMoreExpr(expr *oneOrMoreExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseOneOrMoreExpr"))
+	}
+
+	var vals []interface{}
+
+	for {
+		p.pushV()
+		val, ok := p.parseExpr(expr.expr)
+		p.popV()
+		if !ok {
+			if len(vals) == 0 {
+				// did not match once, no match
+				return nil, false
+			}
+			return vals, true
+		}
+		vals = append(vals, val)
+	}
+}
+
+func (p *parser) parseRuleRefExpr(ref *ruleRefExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseRuleRefExpr " + ref.name))
+	}
+
+	if ref.name == "" {
+		panic(fmt.Sprintf("%s: invalid rule: missing name", ref.pos))
+	}
+
+	rule := p.rules[ref.name]
+	if rule == nil {
+		p.addErr(fmt.Errorf("undefined rule: %s", ref.name))
+		return nil, false
+	}
+	return p.parseRule(rule)
+}
+
+func (p *parser) parseSeqExpr(seq *seqExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseSeqExpr"))
+	}
+
+	var vals []interface{}
+
+	pt := p.pt
+	for _, expr := range seq.exprs {
+		val, ok := p.parseExpr(expr)
+		if !ok {
+			p.restore(pt)
+			return nil, false
+		}
+		vals = append(vals, val)
+	}
+	return vals, true
+}
+
+func (p *parser) parseZeroOrMoreExpr(expr *zeroOrMoreExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseZeroOrMoreExpr"))
+	}
+
+	var vals []interface{}
+
+	for {
+		p.pushV()
+		val, ok := p.parseExpr(expr.expr)
+		p.popV()
+		if !ok {
+			return vals, true
+		}
+		vals = append(vals, val)
+	}
+}
+
+func (p *parser) parseZeroOrOneExpr(expr *zeroOrOneExpr) (interface{}, bool) {
+	if p.debug {
+		defer p.out(p.in("parseZeroOrOneExpr"))
+	}
+
+	p.pushV()
+	val, _ := p.parseExpr(expr.expr)
+	p.popV()
+	// whether it matched or not, consider it a match
+	return val, true
+}
+
+func rangeTable(class string) *unicode.RangeTable {
+	if rt, ok := unicode.Categories[class]; ok {
+		return rt
+	}
+	if rt, ok := unicode.Properties[class]; ok {
+		return rt
+	}
+	if rt, ok := unicode.Scripts[class]; ok {
+		return rt
+	}
+
+	// cannot happen
+	panic(fmt.Sprintf("invalid Unicode class: %s", class))
+}