Appearance
| 1 | namespace Syntax.Parsers.Expressions is | |
| 2 | use System.Exception | |
| 3 | ||
| 4 | use IO.Std | |
| 5 | ||
| 6 | use Logging | |
| 7 | use Source | |
| 8 | ||
| 9 | enum PRECEDENCE is | |
| 10 | NONE = 0, | |
| 11 | MIN = 10, | |
| 12 | YIELD = 20, // reserved for `||` generator yield infix | |
| 13 | UNDEFINED = 30, | |
| 14 | USER_1 = 40, | |
| 15 | BOOLEAN = 50, | |
| 16 | USER_2 = 60, | |
| 17 | RELATIONAL = 70, | |
| 18 | THREAD_FIRST = 75, // `|>` and `~>` | |
| 19 | USER_3 = 80, | |
| 20 | RANGE = 90, | |
| 21 | USER_4 = 100, | |
| 22 | SHIFT = 110, | |
| 23 | USER_5 = 120, | |
| 24 | BITWISE = 130, | |
| 25 | USER_6 = 140, | |
| 26 | ADDITION = 150, | |
| 27 | USER_7 = 160, | |
| 28 | MULTIPLICATION = 170, | |
| 29 | USER_8 = 180, | |
| 30 | MEMBER = 190, | |
| 31 | PRIMARY = 200 | |
| 32 | si | |
| 33 | ||
| 34 | enum ASSOCIATIVITY is | |
| 35 | LEFT, | |
| 36 | RIGHT | |
| 37 | si | |
| 38 | ||
| 39 | class EXPRESSION( | |
| 40 | expression_tertiary_parser: Parser[Trees.Expressions.Expression], | |
| 41 | expression_secondary_parser: LAZY_PARSER[Trees.Expressions.Expression], | |
| 42 | precedence: Collections.MutableMap[string,PRECEDENCE] | |
| 43 | ): Base[Trees.Expressions.Expression] is | |
| 44 | _precedence: Collections.MutableMap[string,PRECEDENCE] | |
| 45 | _real_operation: Collections.MAP[string,string] | |
| 46 | _expression_secondary_parser: LAZY_PARSER[Trees.Expressions.Expression] | |
| 47 | ||
| 48 | // The right side of `|>` and `~>` is parsed by the secondary parser, | |
| 49 | // which owns the trailer grammar a call is built from. | |
| 50 | _thread_first: SECONDARY => cast SECONDARY(_expression_secondary_parser.value()) | |
| 51 | ||
| 52 | super() | |
| 53 | ||
| 54 | init(..) is | |
| 55 | _precedence = precedence | |
| 56 | _expression_secondary_parser = expression_secondary_parser | |
| 57 | ||
| 58 | _precedence["*"] = PRECEDENCE.MULTIPLICATION | |
| 59 | _precedence["✕"] = PRECEDENCE.MULTIPLICATION | |
| 60 | _precedence["×"] = PRECEDENCE.MULTIPLICATION | |
| 61 | _precedence["/"] = PRECEDENCE.MULTIPLICATION | |
| 62 | _precedence["%"] = PRECEDENCE.MULTIPLICATION | |
| 63 | _precedence["÷"] = PRECEDENCE.MULTIPLICATION | |
| 64 | _precedence["+"] = PRECEDENCE.ADDITION | |
| 65 | _precedence["-"] = PRECEDENCE.ADDITION | |
| 66 | _precedence["&"] = PRECEDENCE.BITWISE | |
| 67 | _precedence["|"] = PRECEDENCE.BITWISE | |
| 68 | _precedence["¦"] = PRECEDENCE.BITWISE | |
| 69 | _precedence["^"] = PRECEDENCE.BITWISE | |
| 70 | _precedence["∩"] = PRECEDENCE.BITWISE | |
| 71 | _precedence["∪"] = PRECEDENCE.BITWISE | |
| 72 | _precedence[".."] = PRECEDENCE.RANGE | |
| 73 | _precedence["::"] = PRECEDENCE.RANGE | |
| 74 | _precedence["<<"] = PRECEDENCE.SHIFT | |
| 75 | _precedence[">>"] = PRECEDENCE.SHIFT | |
| 76 | _precedence["≈"] = PRECEDENCE.RELATIONAL | |
| 77 | _precedence["≡"] = PRECEDENCE.RELATIONAL | |
| 78 | _precedence["=="] = PRECEDENCE.RELATIONAL | |
| 79 | _precedence["!="] = PRECEDENCE.RELATIONAL | |
| 80 | _precedence["=~"] = PRECEDENCE.RELATIONAL | |
| 81 | _precedence["!~"] = PRECEDENCE.RELATIONAL | |
| 82 | _precedence["<"] = PRECEDENCE.RELATIONAL | |
| 83 | _precedence[">"] = PRECEDENCE.RELATIONAL | |
| 84 | _precedence[">="] = PRECEDENCE.RELATIONAL | |
| 85 | _precedence["<="] = PRECEDENCE.RELATIONAL | |
| 86 | _precedence["/\\"] = PRECEDENCE.BOOLEAN | |
| 87 | _precedence["\\/"] = PRECEDENCE.BOOLEAN | |
| 88 | _precedence["∧"] = PRECEDENCE.BOOLEAN | |
| 89 | _precedence["∨"] = PRECEDENCE.BOOLEAN | |
| 90 | _precedence["||"] = PRECEDENCE.YIELD | |
| 91 | _precedence["??"] = PRECEDENCE.USER_1 | |
| 92 | ||
| 93 | _real_operation = Collections.MAP[string,string]() | |
| 94 | ||
| 95 | _real_operation["!~"] = "=~" | |
| 96 | _real_operation["=~"] = "=~" | |
| 97 | _real_operation["!="] = "==" | |
| 98 | _real_operation["=="] = "==" | |
| 99 | _real_operation["<"] = "<>" | |
| 100 | _real_operation["<="] = "<>" | |
| 101 | _real_operation[">"] = "<>" | |
| 102 | _real_operation[">="] = "<>" | |
| 103 | si | |
| 104 | ||
| 105 | description: string => "expression" | |
| 106 | ||
| 107 | precedence(context: CONTEXT) -> PRECEDENCE is | |
| 108 | // A line-start `|>` or `~>` continues the chain above it: a | |
| 109 | // wrapped chain puts the operator first on each line. | |
| 110 | if _is_thread_first(context) then | |
| 111 | return PRECEDENCE.THREAD_FIRST | |
| 112 | fi | |
| 113 | ||
| 114 | if context.current.token != Lexical.TOKEN.OPERATOR then | |
| 115 | return PRECEDENCE.NONE | |
| 116 | fi | |
| 117 | ||
| 118 | // A binary operator never continues an expression from the | |
| 119 | // start of a new line: operators sit at end of line. A | |
| 120 | // line-start operator belongs to what follows - the next | |
| 121 | // member (an operator declaration), a prefix `!` opening a | |
| 122 | // statement - and gluing it as an infix operand would | |
| 123 | // silently misread those. | |
| 124 | if context.current.first_on_line then | |
| 125 | return PRECEDENCE.NONE | |
| 126 | fi | |
| 127 | ||
| 128 | ||
| 129 | let op = context.current.value_string | |
| 130 | ||
| 131 | let known: PRECEDENCE mut = _ | |
| 132 | if _precedence.try_get_value(op, known ref) then | |
| 133 | return known | |
| 134 | fi | |
| 135 | ||
| 136 | let auto = auto_precedence_for(op) | |
| 137 | _precedence[op] = auto | |
| 138 | ||
| 139 | return auto | |
| 140 | si | |
| 141 | ||
| 142 | _is_thread_first(context: CONTEXT) -> bool static => | |
| 143 | context.current.token == Lexical.TOKEN.BAR_ARROW \/ | |
| 144 | context.current.token == Lexical.TOKEN.TILDE_ARROW | |
| 145 | ||
| 146 | // First-character-based precedence heuristic for user-defined | |
| 147 | // operators. Modelled on OCaml/F#. Every built-in operator in the | |
| 148 | // _precedence table matches what this would compute, so the table | |
| 149 | // is purely an optimisation and a hook point for explicit overrides | |
| 150 | // via @precedence. | |
| 151 | auto_precedence_for(op: string) -> PRECEDENCE static is | |
| 152 | if op =~ "/\\" \/ op =~ "\\/" then | |
| 153 | return PRECEDENCE.BOOLEAN | |
| 154 | fi | |
| 155 | // Any operator opening with `..` or `::` is a range operator, so | |
| 156 | // the from-the-end forms (`..<`, `::<`, `..<<`, `::<<`) sit with | |
| 157 | // the plain ones rather than falling through to the | |
| 158 | // first-character chain. | |
| 159 | if op.starts_with("..") \/ op.starts_with("::") then | |
| 160 | return PRECEDENCE.RANGE | |
| 161 | fi | |
| 162 | ||
| 163 | let first = op[0] | |
| 164 | ||
| 165 | if first == '*' \/ first == '/' \/ first == '%' \/ | |
| 166 | first == '×' \/ first == '÷' \/ first == '✕' \/ | |
| 167 | first == '⊗' \/ first == '⊘' \/ first == '⊙' \/ | |
| 168 | first == '⋅' \/ first == '∗' | |
| 169 | then | |
| 170 | return PRECEDENCE.MULTIPLICATION | |
| 171 | fi | |
| 172 | if first == '+' \/ first == '-' \/ | |
| 173 | first == '⊕' \/ first == '⊖' \/ | |
| 174 | first == '±' \/ first == '∓' | |
| 175 | then | |
| 176 | return PRECEDENCE.ADDITION | |
| 177 | fi | |
| 178 | if first == '<' \/ first == '>' then | |
| 179 | if op.length >= 2 /\ op[1] == first then | |
| 180 | return PRECEDENCE.SHIFT | |
| 181 | else | |
| 182 | return PRECEDENCE.RELATIONAL | |
| 183 | fi | |
| 184 | fi | |
| 185 | if first == '=' \/ first == '!' \/ first == '~' \/ | |
| 186 | first == '≈' \/ first == '≉' \/ | |
| 187 | first == '≡' \/ first == '≢' \/ | |
| 188 | first == '≠' \/ first == '≤' \/ first == '≥' \/ | |
| 189 | first == '∈' \/ first == '∉' \/ first == '∋' \/ | |
| 190 | first == '⊂' \/ first == '⊃' \/ | |
| 191 | first == '⊆' \/ first == '⊇' | |
| 192 | then | |
| 193 | return PRECEDENCE.RELATIONAL | |
| 194 | fi | |
| 195 | if first == '&' \/ first == '∩' then | |
| 196 | return PRECEDENCE.BITWISE | |
| 197 | fi | |
| 198 | if first == '|' \/ first == '¦' \/ first == '∪' then | |
| 199 | return PRECEDENCE.BITWISE | |
| 200 | fi | |
| 201 | if first == '^' \/ | |
| 202 | first == '⊻' \/ first == '⊼' \/ first == '⊽' | |
| 203 | then | |
| 204 | return PRECEDENCE.BITWISE | |
| 205 | fi | |
| 206 | if first == '∧' \/ first == '∨' then | |
| 207 | return PRECEDENCE.BOOLEAN | |
| 208 | fi | |
| 209 | if first == '?' then | |
| 210 | return PRECEDENCE.USER_1 | |
| 211 | fi | |
| 212 | ||
| 213 | return PRECEDENCE.USER_5 | |
| 214 | si | |
| 215 | ||
| 216 | // First-character associativity heuristic. Default is left; | |
| 217 | // `?`-prefixed operators are right-associative so that `a ?? b ?? c` | |
| 218 | // parses as `a ?? (b ?? c)` — each intermediate result stays | |
| 219 | // optional rather than being closed off by the inner operator. | |
| 220 | auto_associativity_for(op: string) -> ASSOCIATIVITY static is | |
| 221 | if op[0] == '?' then | |
| 222 | return ASSOCIATIVITY.RIGHT | |
| 223 | fi | |
| 224 | return ASSOCIATIVITY.LEFT | |
| 225 | si | |
| 226 | ||
| 227 | parse(context: CONTEXT) -> Trees.Expressions.Expression is | |
| 228 | try | |
| 229 | return parse(context, expression_tertiary_parser.parse(context)!, PRECEDENCE.MIN) | |
| 230 | catch ue: UnwindException | |
| 231 | throw ue | |
| 232 | ||
| 233 | catch e: Exception | |
| 234 | IoC.CONTAINER.instance.logger.exception(context.current.location, e, "parse exception: {e.message}") | |
| 235 | ||
| 236 | return Trees.Expressions.Literals.NONE(context.location) | |
| 237 | yrt | |
| 238 | si | |
| 239 | ||
| 240 | // precedence climbing expression parser: | |
| 241 | parse(context: CONTEXT, left: Trees.Expressions.Expression mut, min_precedence: PRECEDENCE) -> Trees.Expressions.Expression is | |
| 242 | let last_was_yield_infix mut = false | |
| 243 | ||
| 244 | do | |
| 245 | let left_precedence = precedence(context) | |
| 246 | ||
| 247 | if cast int(left_precedence) < cast int(min_precedence) then | |
| 248 | break | |
| 249 | fi | |
| 250 | ||
| 251 | // The right side of a thread-first operator is one call | |
| 252 | // rather than an operand, so nothing on it competes for | |
| 253 | // precedence: an operator written after the call applies | |
| 254 | // to the result of the whole chain. | |
| 255 | if _is_thread_first(context) then | |
| 256 | let propagating = context.current.token == Lexical.TOKEN.TILDE_ARROW | |
| 257 | ||
| 258 | left = | |
| 259 | _thread_first.parse_thread_first( | |
| 260 | context, | |
| 261 | left, | |
| 262 | propagating, | |
| 263 | if propagating then "~>" else "|>" fi | |
| 264 | ) | |
| 265 | ||
| 266 | last_was_yield_infix = false | |
| 267 | ||
| 268 | continue | |
| 269 | fi | |
| 270 | ||
| 271 | let apparent_op = context.current.value_string | |
| 272 | ||
| 273 | let real_op mut = apparent_op | |
| 274 | ||
| 275 | if _real_operation.contains_key(apparent_op) then | |
| 276 | real_op = _real_operation[apparent_op] | |
| 277 | fi | |
| 278 | ||
| 279 | let op = Trees.Identifiers.Identifier(context.location, real_op) | |
| 280 | ||
| 281 | let op_location = context.location | |
| 282 | ||
| 283 | let associativity = auto_associativity_for(apparent_op) | |
| 284 | ||
| 285 | context.next_token() | |
| 286 | ||
| 287 | let right: Trees.Expressions.Expression mut = expression_tertiary_parser.parse(context)! | |
| 288 | ||
| 289 | assert right? else "parse right failed" | |
| 290 | ||
| 291 | do | |
| 292 | let right_precedence = precedence(context) | |
| 293 | ||
| 294 | if associativity == ASSOCIATIVITY.RIGHT then | |
| 295 | if cast int(right_precedence) < cast int(left_precedence) then | |
| 296 | break | |
| 297 | fi | |
| 298 | else | |
| 299 | if cast int(right_precedence) <= cast int(left_precedence) then | |
| 300 | break | |
| 301 | fi | |
| 302 | fi | |
| 303 | ||
| 304 | right = parse(context, right, right_precedence) | |
| 305 | od | |
| 306 | ||
| 307 | if apparent_op =~ "||" then | |
| 308 | if last_was_yield_infix then | |
| 309 | IoC.CONTAINER.instance.logger.error( | |
| 310 | op_location, | |
| 311 | "yield infix '||' does not chain" | |
| 312 | ) | |
| 313 | fi | |
| 314 | left = lower_yield_infix(left, right) | |
| 315 | last_was_yield_infix = true | |
| 316 | else | |
| 317 | left = Trees.Expressions.BINARY(left.location::right.location, op, apparent_op, left, right) | |
| 318 | last_was_yield_infix = false | |
| 319 | fi | |
| 320 | od | |
| 321 | ||
| 322 | return left | |
| 323 | si | |
| 324 | ||
| 325 | // Desugar `value || next_state` into a call to the stream-step | |
| 326 | // YIELD variant: `Ghul.Pipes.STREAM.YIELD(value, next_state)`. | |
| 327 | // The right operand is the next state for the consuming | |
| 328 | // `STREAM_PIPE` to feed into the next `advance(state)` call — | |
| 329 | // not a deferred thunk, since laziness comes from the consumer | |
| 330 | // invoking `advance` once per `move_next`. | |
| 331 | lower_yield_infix( | |
| 332 | left: Trees.Expressions.Expression, | |
| 333 | right: Trees.Expressions.Expression | |
| 334 | ) -> Trees.Expressions.Expression static is | |
| 335 | let location = left.location::right.location | |
| 336 | ||
| 337 | let ghul = Trees.Identifiers.Identifier(location, "Ghul") | |
| 338 | let pipes = Trees.Identifiers.QUALIFIED(location, ghul, "Pipes", location, location) | |
| 339 | let stream = Trees.Identifiers.QUALIFIED(location, pipes, "STREAM", location, location) | |
| 340 | let yield_member = Trees.Identifiers.QUALIFIED(location, stream, "YIELD", location, location) | |
| 341 | ||
| 342 | let yield_function = Trees.Expressions.IDENTIFIER(location, yield_member) | |
| 343 | ||
| 344 | let call_arguments = Trees.Expressions.LIST( | |
| 345 | location, | |
| 346 | [left, right]: Trees.Expressions.Expression | |
| 347 | ) | |
| 348 | ||
| 349 | return Trees.Expressions.CALL(location, yield_function, call_arguments) | |
| 350 | si | |
| 351 | si | |
| 352 | si |