Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / WSL / SpecWork / source / index.rst
1 .. WSL documentation master file, created by
2    sphinx-quickstart on Thu Jun  7 15:53:54 2018.
3    You can adapt this file completely to your liking, but it should at least
4    contain the root `toctree` directive.
5
6 WSL Specification
7 #################
8
9 Grammar
10 =======
11
12 Lexical analysis
13 ----------------
14
15 Before parsing, the text of a WSL program is first turned into a list of tokens, removing comments and whitespace along the way.
16 Tokens are built greedily, in other words each token is as long as possible.
17 If the program cannot be transformed into a list of tokens by following these rules, the program is invalid and must be rejected.
18
19 A token can be either of:
20
21 - An integer literal
22 - A float literal
23 - Punctuation
24 - A keyword
25 - A normal identifier
26 - An operator name
27
28 Literals
29 """"""""
30
31 An integer literal can either be decimal or hexadecimal, and either signed or unsigned, giving 4 possibilities.
32
33 - A signed decimal integer literal starts with an optional ``-``, then a number without leading 0.
34 - An unsigned decimal integer literal starts with a number without leading 0, then ``u``.
35 - A signed hexadecimal integer literal starts with an optional ``-``, then the string ``0x``, then a non-empty sequence of elements of [0-9a-fA-F] (non-case sensitive, leading 0s are allowed).
36 - An unsigned hexadecimal inter literal starts with the string ``0x``, then a non-empty sequence of elements of [0-9a-fA-F] (non-case sensitive, leading 0s are allowed), and finally the character ``u``.
37
38 .. todo:: I chose rather arbitrarily to allow leading 0s in hexadecimal, but not in decimal integer literals. This can obviously be changed either way.
39
40 A float literal is made of the following elements in sequence:
41
42 - an optional ``-`` character
43 - a sequence of 0 or more digits (in [0-9])
44 - a ``.`` character
45 - a sequence of 0 or more digits (in [0-9]). This sequence must instead have 1 or more elements, if the last sequence was empty.
46 - optionally a ``f`` or ``d`` character
47
48 In regexp form: '-'? ([0-9]+ '.' [0-9]* | [0-9]* '.' [0-9]+) [fd]?
49
50 Keywords and punctuation
51 """"""""""""""""""""""""
52
53 The following strings are reserved keywords of the language:
54
55 +-------------------------------+---------------------------------------------------------------------------------+
56 | Top level                     | struct typedef enum operator vertex fragment native restricted                  |
57 +-------------------------------+---------------------------------------------------------------------------------+
58 | Control flow                  | if else switch case default while do for break continue fallthrough return trap |
59 +-------------------------------+---------------------------------------------------------------------------------+
60 | Literals                      | null true false                                                                 |
61 +-------------------------------+---------------------------------------------------------------------------------+
62 | Address space                 | constant device threadgroup thread                                              |
63 +-------------------------------+---------------------------------------------------------------------------------+
64 | Reserved for future extension | protocol auto                                                                   |
65 +-------------------------------+---------------------------------------------------------------------------------+
66
67 Similarily, the following elements of punctuation are valid tokens:
68
69 +----------------------+-----------------------------------------------------------------------------------------------+
70 | Relational operators | ``==`` ``!=`` ``<=`` ``=>`` ``<`` ``>``                                                       |
71 +----------------------+-----------------------------------------------------------------------------------------------+
72 | Assignment operators | ``=`` ``++`` ``--`` ``+=`` ``-=`` ``*=`` ``/=`` ``%=`` ``^=`` ``&=``  ``|=`` ``>>=``  ``<<=`` |
73 +----------------------+-----------------------------------------------------------------------------------------------+
74 | Arithmetic operators | ``+``  ``-`` ``*`` ``/`` ``%``                                                                |
75 +----------------------+-----------------------------------------------------------------------------------------------+
76 | Logic operators      | ``&&`` ``||`` ``&``  ``|``  ``^`` ``>>`` ``<<`` ``!`` ``~``                                   |
77 +----------------------+-----------------------------------------------------------------------------------------------+
78 | Memory operators     | ``->`` ``.`` ``&`` ``@``                                                                      |
79 +----------------------+-----------------------------------------------------------------------------------------------+
80 | Other                | ``?`` ``:`` ``;`` ``,`` ``[`` ``]`` ``{`` ``}`` ``(`` ``)``                                   |
81 +----------------------+-----------------------------------------------------------------------------------------------+
82
83 Identifiers and operator names
84 """"""""""""""""""""""""""""""
85
86 An identifier is any sequence of alphanumeric characters or underscores, that does not start by a digit, that is not a single underscore (the single underscore is reserved for future extension), and that is not a reserved keyword.
87 TODO: decide if we only accept [_a-zA-Z][_a-zA-Z0-9], or whether we also accept unicode characters.
88
89 Operator names can be either of the 4 following possibilities:
90
91 - the string ``operator``, followed immediately with one of the following strings: ``>>``, ``<<``, ``+``, ``-``, ``*``, ``/``, ``%``, ``&&``, ``||``, ``&``, ``|``, ``^``, ``>=``, ``<=``, ``>``, ``<``, ``++``, ``--``, ``!``, ``~``, ``[]``, ``[]=``, ``&[]``.
92 - the string ``operator.`` followed immediately with what would be a valid identifier x. We call this token a 'getter for x'.
93 - the string ``operator.`` followed immediately with what would be a valid identifier x, followed immediately with the character ``=``. We call this token 'a setter for x'.
94 - the string ``operator&.`` followed immediately with what would be a valid identifier x. We call this token an 'address taker for x'.
95
96 .. note:: Thanks to the rule that token are read greedily, the string "operator.foo" is a single token (a getter for foo), and not the keyword "operator" followed by the punctuation "." followed by the identifier "foo".
97
98 Whitespace and comments
99 """""""""""""""""""""""
100
101 Any of the following characters are considered whitespace, and ignored after this phase: space, tabulation (``\t``), carriage return (``\r``), new line(``\n``).
102
103 .. todo:: do we want to also allow other unicode whitespace characters?
104
105 We also allow two kinds of comments, that are treated like whitespace (i.e. ignored during parsing).
106 The first kind is a line comment, that starts with the string ``//`` and continues until the next end of line character.
107 The second kind is a multi-line comment, that starts with the string ``/*`` and ends as soon as the string ``*/`` is read.
108
109 .. note:: Multi-line comments cannot be nested, as the first ``*/`` closes the outermost ``/*``
110
111 Parsing
112 -------
113
114 .. todo:: add here a quick explanation of BNF syntax and our conventions.
115
116 Top-level declarations
117 """"""""""""""""""""""
118
119 A valid file is made of a sequence of 0 or more top-level declarations, followed by the special End-Of-File token.
120
121 .. productionlist::
122     topLevelDecl: ";" | `typedef` | `structDef` | `enumDef` | `funcDef`
123
124 .. todo:: We may want to also allow variable declarations at the top-level if it can easily be supported by all of our targets.
125 .. todo:: Decide whether we put native/restricted in the spec or not.
126
127 .. productionlist::
128     typedef: "typedef" `Identifier` "=" `type` ";"
129
130 .. productionlist::
131     structDef: "struct" `Identifier` "{" `structElement`* "}"
132     structElement: `type` `Identifier` ";"
133
134 .. productionlist::
135     enumDef: "enum" `Identifier` (":" `type`)? "{" `enumElement` ("," `enumElement`)* "}"
136     enumElement: `Identifier` ("=" `constexpr`)?
137
138 .. productionlist::
139     funcDef: `funcDecl` "{" `stmt`* "}"
140     funcDecl: `entryPointDecl` | `normalFuncDecl` | `castOperatorDecl`
141     entryPointDecl: ("vertex" | "fragment") `type` `Identifier` `parameters`
142     normalFuncDecl: `type` (`Identifier` | `OperatorName`) `parameters`
143     castOperatorDecl: "operator" `type` `parameters`
144     parameters: "(" ")" | "(" `parameter` ("," `parameter`)* ")"
145     parameter: `type` `Identifier`
146
147 .. note:: the return type is put after the "operator" keyword when declaring a cast operator, mostly because it is also the name of the created function. 
148
149 Statements
150 """"""""""
151
152 .. productionlist::
153     stmt: "{" `stmt`* "}"
154         : | `compoundStmt` 
155         : | `terminatorStmt` ";" 
156         : | `variableDecls` ";" 
157         : | `maybeEffectfulExpr` ";"
158     compoundStmt: `ifStmt` | `ifElseStmt` | `whileStmt` | `doWhileStmt` | `forStmt` | `switchStmt`
159     terminatorStmt: "break" | "continue" | "fallthrough" | "return" `expr`? | "trap"
160
161 .. productionlist::
162     ifStmt: "if" "(" `expr` ")" `stmt`
163     ifElseStmt: "if" "(" `expr` ")" `stmt` "else" `stmt`
164
165 .. todo:: should I forbid assignments (without parentheses) inside the conditions of if/while to avoid the common mistaking of "=" for "==" ? 
166
167 The first of these two productions is merely syntactic sugar for the second:
168
169 .. math:: \textbf{if}(e) \,s \leadsto \textbf{if}(e) \,s\, \textbf{else} \,\{\}
170
171 .. productionlist::
172     whileStmt: "while" "(" `expr` ")" `stmt`
173     forStmt: "for" "(" (`maybeEffectfulExpr` | `variableDecls`) ";" `expr`? ";" `expr`? ")" `stmt`
174     doWhileStmt: "do" `stmt` "while" "(" `expr` ")" ";"
175
176 Similarily, we desugar first for loops into while loops, and then all while loops into do while loops.
177 First, if the second element of the for is empty we replace it by "true".
178 Then, we apply the following two rules:
179
180 .. math::
181     \textbf{for} (X_{pre} ; e_{cond} ; e_{iter}) \, s \leadsto \{ X_{pre} ; \textbf{while} (e_{cond}) \{ s \, e_{iter} ; \} \}
182
183 .. math::
184     \textbf{while} (e)\, s \leadsto \textbf{if} (e) \textbf{do}\, s\, \textbf{while}(e)
185
186 .. productionlist::
187     switchStmt: "switch" "(" `expr` ")" "{" `switchCase`* "}"
188     switchCase: ("case" `constexpr` | "default") ":" `stmt`*
189
190 .. productionlist::
191     variableDecls: `type` `variableDecl` ("," `variableDecl`)*
192     variableDecl: `Identifier` ("=" `expr`)?
193
194 Complex variable declarations are also mere syntactic sugar.
195 Several variable declarations separated by commas are the same as separating them with semicolons and repeating the type for each one.
196 And a variable declaration with an initializer is the same as an uninitialized declaration, followed by an assignment of the corresponding value to this variable.
197 These two transformations can always be done because variable declarations are only allowed inside blocks (and for loops, but these get desugared into a block, see above).
198
199 .. todo:: should I make the requirement that variableDecls only appear in blocks be part of the syntax, or should it just be part of the validation rules?
200
201 Types
202 """""
203
204 .. productionlist::
205     type: `addressSpace` `Identifier` `typeArguments` `typeSuffixAbbreviated`+
206         : | `Identifier` `typeArguments` `typeSuffixNonAbbreviated`*
207     addressSpace: "constant" | "device" | "threadgroup" | "thread"
208     typeSuffixAbbreviated: "*" | "[" "]" | "[" `IntLiteral` "]"
209     typeSuffixNonAbbreviated: "*" `addressSpace` | "[" "]" `addressSpace` | "[" `IntLiteral` "]"
210
211
212 Putting the address space before the identifier is just syntactic sugar for having that same address space applied to all type suffixes.
213 ``thread int *[]*[42]`` is for example the same as ``int *thread []thread *thread [42]``.
214
215 .. productionlist::
216     typeArguments: "<" (`typeArgument` ",")* `addressSpace`? `Identifier` "<" 
217                  : (`typeArgument` ("," `typeArgument`)*)? ">>"
218                  : | "<" (`typeArgument` ("," `typeArgument`)* ">"
219                  : | ("<" ">")?
220     typeArgument: `constepxr` | `type`
221
222 The first production rule for typeArguments is a way to say that `>>` can be parsed as two `>` closing delimiters, in the case of nested typeArguments.
223
224 Expressions
225 """""""""""
226
227 We accept three different kinds of expressions, in different places in the grammar.
228
229 - ``expr`` is the most generic, and includes all expressions.
230 - ``maybeEffectfulExpr`` is used in places where a variable declaration would also be allowed. It forbids some expressions that are clearly effect-free, such as ``x*y`` or ``x < y``.
231   As the name indicates, it may be empty. In that case it is equivalent to "null" (any other effect-free expression would be fine, as the result of such an expression is always discarded).
232 - ``constexpr`` is limited to literals and the elements of an enum. It is used in switch cases, and in type arguments.
233
234 .. productionlist::
235     expr: (`expr` ",")? `ternaryConditional`
236     ternaryConditional: `exprLogicalOr` "?" `expr` ":" `ternaryConditional`
237                       : | `exprPrefix` `assignOperator` `ternaryConditional`
238                       : | `exprLogicalOr`
239     assignOperator: "=" | "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "|=" | "^=" | ">>=" | "<<="
240     exprLogicalOr: (`exprLogicalOr` "||")? `exprLogicalAnd`
241     exprLogicalAnd: (`exprLogicalAnd` "&&")? `exprBitwiseOr`
242     exprBitwiseOr: (`exprBitwiseOr` "|")? `exprBitwiseXor`
243     exprBitwiseXor: (`exprBitwiseXor` "^")? `exprBitwiseAnd`
244     exprBitwiseAnd: (`exprBitwiseAnd` "&")? `exprRelational`
245     exprRelational: `exprShift` (`relationalBinop` `exprShift`)?
246     relationalBinop: "<" | ">" | "<=" | ">=" | "==" | "!="
247     exprShift: (`exprShift` ("<<" | ">>"))? `exprAdd`
248     exprAdd: (`exprMult` ("*" | "/" | "%"))? `exprPrefix`
249     exprPrefix: `prefixOp` `exprPrefix` | `exprSuffix`
250     prefixOp: "++" | "--" | "+" | "-" | "~" | "!" | "*" | "&" | "@"
251     exprSuffix: `callExpression` `limitedSuffixOp`*
252               : | `term` (`limitedSuffixOp` | "++" | "--")*
253     limitedSuffixOp: "." `Identifier` | "->" `Identifier` | "[" `expr` "]"
254     callExpression: `Identifier` "(" (`ternaryConditional` ("," `ternaryConditional`)*)? ")"
255     term: `Literal` | `Identifier` | "(" `expr` ")"
256
257 We match the precedence and associativity of operators from C++, with one exception: we made relational operators non-associative,
258 so that they cannot be chained. Chaining them has sufficiently surprising results that it is not a clear reduction in usability, and it should make it a lot easier to extend the syntax in the future to accept generics.
259
260 There is exactly one piece of syntactic sugar in the above rules: the ``!=`` operator.
261 ``e0 != e1`` is equivalent with ``! (e0 == e1)``.
262
263 .. productionlist::
264     maybeEffectfulExpr: (`effAssignment` ("," `effAssignment`)*)?
265     effAssignment: `exprPrefix` `assignOperator` `expr` | `effPrefix`
266     effPrefix: ("++" | "--") `exprPrefix` | `effSuffix`
267     effSuffix: `exprSuffix` ("++" | "--") | `callExpression` | "(" `expr` ")"
268
269 The structure of maybeEffectfulExpr roughly match the structure of normal expressions, just with normally effect-free operators left off.
270
271 If the programmer still wants to use them in such a position (for example due to having overloaded an operator with an effectful operation),
272 it can be done just by wrapping the expression in parentheses (see the last alternative for effSuffix).
273
274 .. productionlist::
275     constexpr: `Literal` | `Identifier` "." `Identifier`
276
277 Static rules
278 ============
279
280 Phase 1: Gathering declarations
281 -------------------------------
282
283 the goal is to build the global typing environment, as well as the global execution environment.
284 I am afraid it may require several steps.
285 The first step would do most of the work, gathering all function signatures, as well as typedefs, etc..
286 The second step would go through the resulting environment, resolving all types, in particular all typedefs (as well as connecting function parameters to the corresponding type variables, etc..)
287
288 Phase 2: Local typing and early validation
289 ------------------------------------------
290
291 Notations and definitions
292 """""""""""""""""""""""""
293
294 - Definition of the typing environment
295 - Definition of the type hierarchy
296 - Definition of the type evaluation judgement
297
298 Validating top-level declarations
299 """""""""""""""""""""""""""""""""
300
301 Typedefs and structs:
302
303 - checking no recursive types (both structs and typedefs.. maybe as part of the computation of the size of each type)
304   No, the computation of the size of each type will necessarily happen during monomorphisation
305   And we cannot defer this check until then, because we will need to eliminate all typedefs during the local typing phase.
306
307 Structs:
308
309 - checking that structs have distinct names for different fields, and that the type of their fields are well-defined
310
311 Enums:
312
313 - check that enums do not have duplicate values, and have one zero-valued element.
314 - check that enums have an integer base type (not another enum in particular).
315 - check that every value given to an enum element fits in the base type.
316
317 Protocols:
318
319 - check that each signature inside a protocol refers to the protocol name (aka type variable).
320 - check that the extension relation on protocols is sane (at the very least acyclic, maybe also no incompatible signatures for the same function name).
321
322 Functions:
323
324 - check that operator.field, operator.field=, operator[] and operator[]= are not defined for pointer types, nor declared for pointer types in a protocol.
325 - check that operator.field= is only defined if operator.field is as well, and that they agree on their return type in that case.
326 - check that operator[]= is only defined if operator[] is as well, and that they agree on their return type in that case.
327 - check that all of the type parameters of each operator declaration/definition are inferrable from their arguments (and from its return type in the case of cast operators).
328 - finally, check that the function body can only end with a return of the right type, or with Nothing if it is a void function
329
330 Typing statements
331 """""""""""""""""
332
333 Typing expressions
334 """"""""""""""""""
335
336 - typing rules (this and everything that follows can be managed by just a pair of judgements that type stmts/exprs)
337 - checking returns
338 - check that every variable declaration is in a block or at the top-level
339 - check that no variable declaration shadows another one at the same scope
340 - check that switch statements treat all cases
341 - check that every case in a switch statement ends in a terminator (fallthrough/break/return/continue/trap)
342 - check that literals fit into the type they are stored into (optional?)
343
344 Phase 3: Monomorphisation and late validation
345 ---------------------------------------------
346
347 - monomorphisation itself
348 - resolving function calls (probably done as part of monomorphisation)
349 - checking no recursive functions (seems very hard to do before that step, as it requires resolving overloaded functions)
350 - allocating a unique store identifier to each function parameter and variable declaration
351 - annotating each array access with the stride used by that array type? If we do it here and not at runtime, then each assignment would also need a size annotation..
352 - checks of proper use of address spaces
353
354 Dynamic rules
355 =============
356
357 Definitions
358 -----------
359
360 Execution of statements
361 -----------------------
362
363 Execution of expressions
364 ------------------------
365
366 Memory model
367 ------------
368
369 Standard library
370 ================
371
372 Interface with JavaScript
373 =========================
374
375 Indices and tables
376 ##################
377
378 * :ref:`genindex`
379 * :ref:`modindex`
380 * :ref:`search`