This repository has been archived by the owner on Nov 24, 2022. It is now read-only.
/
spah-grammar.html
200 lines (145 loc) · 9.28 KB
/
spah-grammar.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
<!DOCTYPE html>
<html>
<head>
<title>Appendix: SpahQL Grammar and execution spec</title>
<link rel="stylesheet" href="css/normalize.css" type="text/css" media="screen" />
<link rel="stylesheet" href="css/nav.css" type="text/css" media="screen" />
<link rel="stylesheet" href="css/ir_black.css" type="text/css" media="screen" />
<link rel="stylesheet" href="css/repl.css" type="text/css" media="screen" />
<script type="text/javascript" src="js/highlight.pack.js"></script>
<script type="text/javascript" src="js/jquery.1.5.2.min.js"></script>
<script type="text/javascript" src="js/jquery.scrollTo-1.4.2-min.js"></script>
<script type="text/javascript" src="js/spahql-min.js"></script>
<script type="text/javascript" src="js/spahql-repl.js"></script>
<script type="text/javascript" src="js/nav.js"></script>
<script type="text/javascript">
$(document).ready(function() {
hljs.initHighlighting();
Nav.init(function(overview) {
$("nav .current").first().after(overview);
});
});
</script>
</head>
<body>
<a href="https://github.com/danski/spahql"><img style="position: fixed; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_white_ffffff.png" alt="Fork me on GitHub"></a>
<div class="nav-wrapper">
<nav id="nav-overview" class="overview">
<h3>SpahQL</h3>
<h4><a href="repl.html">Try SpahQL</a></h4>
<h4><a href="index.html">SpahQL Manual</a></h4>
<h4><a href="src/index.html">API</a></h4>
</nav>
</div>
<article>
<h1 id='appendix_spahql_grammar_and_execution_spec'>Appendix: SpahQL Grammar and execution spec</h1>
<h1 id='ebnf_grammar'>EBNF Grammar</h1>
<pre><code>PathDelimiter ::= "/";
PathWildcard ::= "*";
ArrayDelimiter ::= ",";
RangeDelimiter ::= "..";
SingleQuote ::= "'";
DoubleQuote ::= "\"";
Negative ::= "-";
DecimalPoint ::= ".";
PropertyIdentifier ::= ".";
RootScopeFlag ::= "$";
SetStart ::= "{";
SetEnd ::= "}";
FilterStart ::= "[";
FilterEnd ::= "]";
BooleanTrue ::= "true";
BooleanFalse ::= "false";
StrictEquality ::= "==";
RoughEquality ::= "=~";
Inequality ::= "!=";
GT ::= ">";
LT ::= "<";
LTE ::= LT, "=";
GTE ::= GT, "=";
SetEquality ::= "}={";
DisjointSet ::= "}!{";
JointSet ::= "}~{";
Superset ::= "}>{";
Subset ::= "}<{";
(* Tokens *)
ComparisonOperator ::= StrictEquality | RoughEquality
| Inequality | GT | LT | GTE | LTE
| SetEquality | DisjointSet
| JointSet | Superset | Subset;
Digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
AlphaChar ::= "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
| "c" | "d" | "e" | "f" | "g" | "h" | "i"
| "j" | "k" | "l" | "m" | "n" | "o" | "p"
| "q" | "r" | "s" | "t" | "u" | "v" | "w"
| "x" | "y" | "z";
AlphaNumChar ::= AlphaChar | Digit;
NumericLiteral ::= [Negative], Digit, {Digit}, [DecimalPoint, Digit, {Digit}];
SingleQuoteString ::= SingleQuote, {all characters - SingleQuote}, SingleQuote;
DoubleQuoteString ::= DoubleQuote, {all characters - DoubleQuote}, DoubleQuote;
StringLiteral ::= SingleQuoteString | DoubleQuoteString;
BooleanLiteral ::= BooleanTrue | BooleanFalse;
PrimitiveLiteral ::= NumericLiteral | StringLiteral | BooleanLiteral;
SetMember ::= PrimitiveLiteral | SelectionQuery;
SetArrayLiteral ::= SetStart, ( SetEnd | {SetMember, ArrayDelimiter}, SetMember, SetEnd );
SetRangeLiteral ::= SetStart, SetMember, RangeDelimiter, SetMember, SetEnd;
SetLiteral ::= SetArrayLiteral | SetRangeLiteral;
SelectionQuery ::= [RootScopeFlag], PathComponent, {PathComponent};
PathComponent ::= PathDelimiter, [PathWildcard | (PropertyIdentifier, KeyName) | KeyName], {FilterQuery};
KeyName ::= AlphaNumChar, {AlphaNumChar};
FilterQuery ::= FilterStart, RunnableAssertion, FilterEnd;
RunnableSelection ::= SetLiteral | SelectionQuery;
RunnableAssertion ::= RunnableSelection, [ComparisonOperator, RunnableSelection];
SpahQL ::= RunnableAssertion;</code></pre>
<h1 id='spahql_query_execution_spec'>SpahQL query execution spec</h1>
<p>SpahQL selection queries are, fundamentally, reductive. At the start of execution, a selection query is given the root data context against which it will run. As the execution moves between the path segments, the data is reduced (and possibly forked) before being passed to the next path segment:</p>
<pre><code>data = {foo: {bar: {baz: "str"}}}
query = "/foo/bar/baz"</code></pre>
<p>At each point in the above query:</p>
<ol>
<li>The root <code>data</code> object is handed to the first path component, which selects the key <code>foo</code>.</li>
<li>The resulting data <code>{bar: {baz: "str"}}</code> is handed to the next path component which selects the key <code>bar</code></li>
<li>The resulting data <code>{baz: "str"}</code> is handed to the final path segment, which selects the key <code>baz</code></li>
<li>The key “baz” is a string with value “str”. This is returned as a result set with one item.</li>
</ol>
<p>If at any point a query runs out of data, the execution is aborted and an empty result set is returned:</p>
<pre><code>data = {foo: {bar: {baz: "str"}}}
query = "/foo/NOTBAR/baz"</code></pre>
<p>In this case, the query exits and returns <code>[]</code> when it is unable to find any matching data for the <code>NOTBAR</code> portion of the query.</p>
<p>Recursive paths force the query runner to fork the execution:</p>
<pre><code>data = {foo: {bar: {baz: "str", bar: "inner-bar"}}}
query = "/foo//bar/baz"</code></pre>
<p>In this instance:</p>
<ol>
<li>The root <code>data</code> object is handed to the first path component, which selects the key <code>foo</code>.</li>
<li>The remaining data <code>{bar: {baz: "str", bar: "inner-bar"}}</code> is handed to the next path query, which <strong>recursively</strong> searches for the key <code>bar</code>.</li>
<li>The recursive search returns results from two paths: <code>/foo/bar</code>, which contains a hash, and <code>/foo/bar/bar</code> which is a value within a sub-hash.</li>
<li>The two result sets are handed down to the <code>baz</code> portion of the query.</li>
<li>The <code>baz</code> key appears in only one of the previous data constructs, and this result is added to the final result set.</li>
</ol>
<p>And so we can see that the overall progression is:</p>
<pre><code>data -> reduce -> array of result sets -> reduce -> array of result sets -> reduce -> finalise</code></pre>
<p>The finalisation step flattens the returned resultsets as a set of <code>QueryResult</code> objects. The final result set is a union of each of the final result sets made unique by result path.</p>
<p>In the case of <strong>filters</strong>, an additional reduce step is introduced into the path segment specifying the filter:</p>
<pre><code>data = {foo: {bar: {baz: "str", bar: "inner-bar"}}}
query = "/foo/[//baz == 'str']"</code></pre>
<p>In this case:</p>
<ol>
<li>The root <code>data</code> object is handed to the first path segment, which retrieves the key <code>foo</code>.</li>
<li>The resulting data is handed to the next path segment, which specifies no key - therefore all keys are acceptable.</li>
<li>All keys in the resulting data have the filter query <code>//baz =='str'</code> run against their values. Those keys for which the filter query returns <code>true</code> are added to the result set for this path segment.</li>
<li>The query ends - the results (all values defined directly on <code>/foo</code> that may be recursed to find a key <code>baz</code> with value <code>str</code>) are flattened and returned as the query result.</li>
</ol>
<p>Example execution flow:</p>
<img src='https://img.skitch.com/20110511-f6t1iwt3jq4gxyd2hnk7fyfjdd.jpg' />
<p><strong>Properties</strong> act like special keys on paths:</p>
<pre><code>data = {foo: {bar: {baz: "str", bar: "inner-bar"}}}
query = "/.size" // returns the number of keys on the root object
query = "//baz/.size" // returns the sizes of all keys named "baz"</code></pre>
<p>There is no other special behaviour for properties - they simply act like key names.</p>
</article>
</body>
</html>