git.iko.soy/j
on master help sign in
j/src/parse.rs
1115 lines 41 kB history raw
1//! Parser for the j language (§3.2–3.4), including the two layout rules.
3use crate::ast::{Expr, Item, Pattern, Source, TypeExpr};
4use crate::lex::{lex, LexError, SpTok, Tok};
5use num_bigint::BigInt;
6use std::collections::{BTreeSet, HashMap, HashSet};
7use std::rc::Rc;
9#[derive(Debug)]
10pub struct ParseError {
11 pub msg: String,
12 pub line: usize,
15impl ParseError {
16 fn new(msg: impl Into<String>, line: usize) -> Self {
17 ParseError {
18 msg: msg.into(),
19 line,
20 }
21 }
24impl From<LexError> for ParseError {
25 fn from(e: LexError) -> Self {
26 ParseError {
27 msg: e.msg,
28 line: e.line,
29 }
30 }
33pub struct Parser {
34 /// the text being parsed, of which each lambda keeps its span (§5.2)
35 src: Rc<str>,
36 toks: Vec<SpTok>,
37 pos: usize,
38 /// Names in scope (top-level + builtins) for the no-shadowing rule;
39 /// in config.j the builtins alone (§4.2).
40 outer_names: Rc<BTreeSet<String>>,
41 /// Names bound by the lambdas and `let` blocks around the current
42 /// position, for the same rule (§4.2). Since shadowing is refused, no
43 /// name is in here twice, and a construct removes the names it added
44 /// when its scope ends.
45 locals: HashSet<String>,
46 /// How many local binders have been parsed, and for each name the
47 /// ordinal and line of the latest one: the `let` check that `locals`
48 /// cannot make (see `parse_let`).
49 binders: usize,
50 last_binder: HashMap<String, (usize, usize)>,
51 /// set when an operator expression ends with a trailing operator before
52 /// `)`, i.e. a left section
53 section_op: Option<&'static str>,
54 /// levels of recursive descent currently open, bounded by `MAX_DEPTH`
55 depth: usize,
56 /// how many levels high (see `MAX_DEPTH`) the expression the last parse
57 /// function returned is, which each leaves here for its caller
58 height: usize,
61/// How many levels deep an expression may be (§3.4): a leaf is one level, and
62/// any other node one more than its highest part, or two more for a
63/// parenthesis (or section) and for the braces of a record or update. Deeper
64/// input is a parse error (§1.4) instead of an overflow of the worker
65/// thread's stack (main.rs). The recursive descent opens at most one level of
66/// its own (`nested`) per level of the expression around the point it has
67/// reached, each taking up to about 6 KB of stack in a debug build (a
68/// parenthesis takes two) and 1.3 KB in a release build, so the deepest parse
69/// takes under half of the worker's 512 MB. The passes over the tree after the
70/// parse, and dropping it, recurse on its height at about 1.2 KB a level.
71const MAX_DEPTH: usize = 40_000;
73/// fixity table (§3.2): (precedence, right-assoc)
74fn fixity(op: &str) -> Option<(u8, bool)> {
75 Some(match op {
76 "." => (9, true),
77 "*" => (7, false),
78 "+" | "-" => (6, false),
79 "++" | "::" => (5, true),
80 "==" | "/=" | "<" | "<=" | ">" | ">=" => (4, false), // non-assoc
81 "&&" => (3, true),
82 "||" => (2, true),
83 _ => return None,
84 })
87/// non-associative operators cannot be chained
88fn is_nonassoc(op: &str) -> bool {
89 matches!(op, "==" | "/=" | "<" | "<=" | ">" | ">=")
92impl Parser {
93 pub fn new(src: &str, outer_names: Rc<BTreeSet<String>>) -> Result<Self, ParseError> {
94 Ok(Parser {
95 src: Rc::from(src),
96 toks: lex(src)?,
97 pos: 0,
98 outer_names,
99 locals: HashSet::new(),
100 binders: 0,
101 last_binder: HashMap::new(),
102 section_op: None,
103 depth: 0,
104 height: 0,
105 })
106 }
108 /// Run `f` one level deeper in the recursive descent. Every cycle of
109 /// mutually recursive parse functions passes through a call made here,
110 /// which is what bounds the parser's stack use. Each call is matched by a
111 /// level of the expression around what `f` parses, so on input that
112 /// parses, this bound is reached no sooner than `within`'s: it is what
113 /// stops input that never closes, like `((((…`.
114 fn nested<T>(
115 &mut self,
116 f: impl FnOnce(&mut Self) -> Result<T, ParseError>,
117 ) -> Result<T, ParseError> {
118 if self.depth >= MAX_DEPTH {
119 return Err(ParseError::new("nested too deeply", self.line()));
120 }
121 self.depth += 1;
122 let r = f(self);
123 self.depth -= 1;
124 r
125 }
127 /// `h`, the height of an expression just built, while it is within
128 /// `MAX_DEPTH`. Every node is checked here as it is built, since a loop
129 /// builds a left-associative chain (`a + b + …`, `f x y …`, `r.a.b …`,
130 /// `r { … } { … }`) as tall as it is long without recursing, and the
131 /// passes over the tree after the parse, and dropping it, recurse on its
132 /// height.
133 fn within(&self, h: usize) -> Result<usize, ParseError> {
134 if h > MAX_DEPTH {
135 return Err(ParseError::new("nested too deeply", self.line()));
136 }
137 Ok(h)
138 }
140 fn peek(&self) -> &Tok {
141 &self.toks[self.pos].tok
142 }
143 fn line(&self) -> usize {
144 self.toks[self.pos].line
145 }
146 fn col(&self) -> usize {
147 self.toks[self.pos].col
148 }
149 fn bump(&mut self) -> Tok {
150 let t = self.toks[self.pos].tok.clone();
151 if self.pos < self.toks.len() - 1 {
152 self.pos += 1;
153 }
154 t
155 }
156 fn skip_newlines(&mut self) {
157 while matches!(self.peek(), Tok::Newline) {
158 self.bump();
159 }
160 }
161 fn expect(&mut self, t: &Tok) -> Result<(), ParseError> {
162 if self.peek() == t {
163 self.bump();
164 Ok(())
165 } else {
166 Err(ParseError::new(
167 format!("expected {}, found {}", t.describe(), self.peek().describe()),
168 self.line(),
169 ))
170 }
171 }
173 // ------------------------------------------------------------------
174 // top-level: config := item* (layout rule 1)
175 // ------------------------------------------------------------------
176 pub fn parse_config(&mut self) -> Result<Vec<Item>, ParseError> {
177 let mut items = Vec::new();
178 self.skip_newlines();
179 while !matches!(self.peek(), Tok::Eof) {
180 if self.col() != 1 {
181 return Err(ParseError::new(
182 "top-level items must begin in column 1",
183 self.line(),
184 ));
185 }
186 let item = self.parse_item()?;
187 items.push(item);
188 // after an item, expect newline(s) or eof
189 self.skip_newlines();
190 }
191 Ok(items)
192 }
194 /// One item. Under rule 1 (§3.3) a line starting past column 1 continues
195 /// it, so a line break before its `=` or `:` is skipped when the next
196 /// line starts past column 1, like one inside its type or expression.
197 fn parse_item(&mut self) -> Result<Item, ParseError> {
198 match self.peek().clone() {
199 Tok::TypeName(name) => {
200 // typedecl: TYPENAME '=' type
201 self.bump();
202 self.skip_layout_newlines(1);
203 self.expect(&Tok::Equals)?;
204 let ty = self.parse_type()?;
205 Ok(Item::TypeDecl(name, ty))
206 }
207 Tok::Ident(name) => {
208 let line = self.line();
209 self.bump();
210 self.skip_layout_newlines(1);
211 match self.peek().clone() {
212 Tok::Colon => {
213 self.bump();
214 let ty = self.parse_type()?;
215 Ok(Item::Signature(name, ty, line))
216 }
217 Tok::Equals => {
218 self.bump();
219 // inside nothing, so it opens no level (see `nested`)
220 let e = self.parse_expr_inner(1)?;
221 Ok(Item::Definition(name, Rc::new(e), line))
222 }
223 other => Err(ParseError::new(
224 format!("expected `:` or `=` after `{}`, found {}", name, other.describe()),
225 self.line(),
226 )),
227 }
228 }
229 Tok::LParen => {
230 // operator signature: (op) : type
231 let line = self.line();
232 self.bump();
233 let op = match self.bump() {
234 Tok::Op(o) => o,
235 other => {
236 return Err(ParseError::new(
237 format!("expected operator, found {}", other.describe()),
238 self.line(),
239 ))
240 }
241 };
242 self.expect(&Tok::RParen)?;
243 self.skip_layout_newlines(1);
244 self.expect(&Tok::Colon)?;
245 let ty = self.parse_type()?;
246 Ok(Item::Signature(op.to_string(), ty, line))
247 }
248 other => Err(ParseError::new(
249 format!("unexpected {} at top level", other.describe()),
250 self.line(),
251 )),
252 }
253 }
255 // ------------------------------------------------------------------
256 // types
257 // ------------------------------------------------------------------
258 fn parse_type(&mut self) -> Result<TypeExpr, ParseError> {
259 self.nested(Self::parse_type_inner)
260 }
262 /// Types occur only in top-level items, so their layout limit is always
263 /// rule 1's column 1 (§3.3): a line break may fall anywhere in a type,
264 /// before or after `->` alike, when the next line starts past column 1.
265 fn parse_type_inner(&mut self) -> Result<TypeExpr, ParseError> {
266 self.skip_layout_newlines(1);
267 let lhs = self.parse_atype()?;
268 self.skip_layout_newlines(1);
269 if matches!(self.peek(), Tok::Arrow) {
270 self.bump();
271 let rhs = self.parse_type()?;
272 Ok(TypeExpr::Fun(Rc::new(lhs), Rc::new(rhs)))
273 } else {
274 Ok(lhs)
275 }
276 }
278 fn parse_atype(&mut self) -> Result<TypeExpr, ParseError> {
279 match self.peek().clone() {
280 Tok::TypeName(n) => {
281 self.bump();
282 Ok(TypeExpr::Con(n))
283 }
284 Tok::Ident(n) => {
285 self.bump();
286 Ok(TypeExpr::Con(n))
287 }
288 Tok::LBracket => {
289 self.bump();
290 let t = self.parse_type()?;
291 self.expect(&Tok::RBracket)?;
292 Ok(TypeExpr::List(Rc::new(t)))
293 }
294 Tok::LBrace => {
295 self.bump();
296 let mut fields = Vec::new();
297 loop {
298 self.skip_layout_newlines(1);
299 if matches!(self.peek(), Tok::RBrace) {
300 self.bump();
301 break;
302 }
303 let name = match self.bump() {
304 Tok::Ident(n) => n,
305 other => {
306 return Err(ParseError::new(
307 format!("expected field name, found {}", other.describe()),
308 self.line(),
309 ))
310 }
311 };
312 self.skip_layout_newlines(1);
313 self.expect(&Tok::Colon)?;
314 let t = self.parse_type()?;
315 fields.push((name, Rc::new(t)));
316 self.skip_layout_newlines(1);
317 match self.peek() {
318 Tok::Comma => {
319 self.bump();
320 }
321 Tok::RBrace => {
322 self.bump();
323 break;
324 }
325 other => {
326 return Err(ParseError::new(
327 format!("expected `,` or `}}`, found {}", other.describe()),
328 self.line(),
329 ))
330 }
331 }
332 }
333 Ok(TypeExpr::Record(fields))
334 }
335 Tok::LParen => {
336 self.bump();
337 let t = self.parse_type()?;
338 self.expect(&Tok::RParen)?;
339 Ok(t)
340 }
341 other => Err(ParseError::new(
342 format!("expected a type, found {}", other.describe()),
343 self.line(),
344 )),
345 }
346 }
348 // ------------------------------------------------------------------
349 // expressions
350 // ------------------------------------------------------------------
352 /// Parse a full expression. `min_col` is the layout column limit: the
353 /// expression stops at a Newline whose following token is in a column
354 /// <= min_col (it belongs to an outer construct).
355 pub fn parse_expr(&mut self, min_col: usize) -> Result<Expr, ParseError> {
356 self.nested(|p| p.parse_expr_inner(min_col))
357 }
359 /// Each construct here and in `parse_atom_inner` is parsed by a function
360 /// of its own: nested input stacks a frame of every function on its path
361 /// for each level (see `MAX_DEPTH`), and in a debug build a function's
362 /// frame holds the temporaries of all its arms.
363 fn parse_expr_inner(&mut self, min_col: usize) -> Result<Expr, ParseError> {
364 self.skip_layout_newlines(min_col);
365 match self.peek().clone() {
366 Tok::Backslash => self.parse_lambda(min_col),
367 Tok::If => self.parse_if(min_col),
368 Tok::Let => self.parse_let(min_col),
369 _ => self.parse_or(min_col),
370 }
371 }
373 fn parse_lambda(&mut self, min_col: usize) -> Result<Expr, ParseError> {
374 let src_start = self.toks[self.pos].clone();
375 self.bump();
376 let mut params = Vec::new();
377 loop {
378 match self.peek().clone() {
379 Tok::Ident(n) => {
380 // in scope from here on, so a later parameter
381 // may not reuse it either
382 self.check_shadow(&n)?;
383 self.locals.insert(n.clone());
384 self.note_binder(&n, self.line());
385 params.push(Pattern::Var(n));
386 self.bump();
387 }
388 Tok::Underscore => {
389 params.push(Pattern::Wildcard);
390 self.bump();
391 }
392 Tok::Arrow => {
393 self.bump();
394 break;
395 }
396 other => {
397 return Err(ParseError::new(
398 format!(
399 "expected a parameter or `->`, found {}",
400 other.describe()
401 ),
402 self.line(),
403 ))
404 }
405 }
406 }
407 if params.is_empty() {
408 return Err(ParseError::new("lambda needs at least one parameter", self.line()));
409 }
410 let body = self.parse_expr(min_col)?;
411 self.height = self.within(self.height + 1)?;
412 for p in &params {
413 if let Pattern::Var(n) = p {
414 self.locals.remove(n);
415 }
416 }
417 let src = self.source_slice(&src_start);
418 Ok(Expr::Lambda(params, Rc::new(body), src))
419 }
421 fn parse_if(&mut self, min_col: usize) -> Result<Expr, ParseError> {
422 self.bump();
423 let c = self.parse_expr(min_col)?;
424 let mut h = self.height;
425 self.skip_layout_newlines(min_col);
426 self.expect(&Tok::Then)?;
427 let t = self.parse_expr(min_col)?;
428 h = h.max(self.height);
429 self.skip_layout_newlines(min_col);
430 self.expect(&Tok::Else)?;
431 let e = self.parse_expr(min_col)?;
432 self.height = self.within(h.max(self.height) + 1)?;
433 Ok(Expr::If(Rc::new(c), Rc::new(t), Rc::new(e)))
434 }
436 /// skip Newlines whose next real token is in a column > min_col
437 fn skip_layout_newlines(&mut self, min_col: usize) {
438 loop {
439 if !matches!(self.peek(), Tok::Newline) {
440 return;
441 }
442 // lookahead past consecutive newlines
443 let mut p = self.pos;
444 while matches!(self.toks[p].tok, Tok::Newline) {
445 p += 1;
446 }
447 if matches!(self.toks[p].tok, Tok::Eof) {
448 return;
449 }
450 if self.toks[p].col > min_col {
451 self.pos = p;
452 } else {
453 return;
454 }
455 }
456 }
458 fn parse_let(&mut self, min_col: usize) -> Result<Expr, ParseError> {
459 self.bump(); // let
460 // skip newlines to find the block column
461 let mut p = self.pos;
462 while matches!(self.toks[p].tok, Tok::Newline) {
463 p += 1;
464 }
465 let block_col = self.toks[p].col;
466 self.pos = p;
467 if block_col <= min_col {
468 return Err(ParseError::new(
469 "let bindings must be indented",
470 self.line(),
471 ));
472 }
473 let mut bindings: Vec<(String, Rc<Expr>)> = Vec::new();
474 let mut names: Vec<(String, usize)> = Vec::new();
475 let first_binder = self.binders;
476 let mut h = 0;
477 loop {
478 // binding: ident '=' expr, expr limited to block_col
479 let name = match self.peek().clone() {
480 Tok::Ident(n) => n,
481 other => {
482 return Err(ParseError::new(
483 format!("expected a binding name, found {}", other.describe()),
484 self.line(),
485 ))
486 }
487 };
488 if names.iter().any(|(n, _)| *n == name) {
489 return Err(ParseError::new(
490 format!("`{}` is bound twice in this let", name),
491 self.line(),
492 ));
493 }
494 self.check_shadow(&name)?;
495 // in scope from here on: in its own expression, the later ones
496 // and the body (§4.1)
497 self.locals.insert(name.clone());
498 names.push((name.clone(), self.line()));
499 self.bump();
500 self.expect(&Tok::Equals)?;
501 let e = self.parse_expr(block_col)?;
502 h = h.max(self.height);
503 bindings.push((name, Rc::new(e)));
504 // separator: `;` or newline at exactly block_col, then `in` ends
505 match self.peek().clone() {
506 Tok::Semi => {
507 self.bump();
508 self.skip_layout_newlines(block_col - 1); // any continuation
509 if matches!(self.peek(), Tok::In) {
510 self.bump();
511 break;
512 }
513 continue;
514 }
515 Tok::In => {
516 self.bump();
517 break;
518 }
519 Tok::Newline => {
520 // find next real token
521 let mut q = self.pos;
522 while matches!(self.toks[q].tok, Tok::Newline) {
523 q += 1;
524 }
525 let next_col = self.toks[q].col;
526 if matches!(self.toks[q].tok, Tok::In) {
527 // like any token that begins a line, an `in` at or
528 // left of the limit belongs to an outer construct
529 // (§3.3): a new top-level item or an outer let's
530 // binding line, never this let
531 if next_col <= min_col {
532 return Err(ParseError::new(
533 format!("`in` must be indented past column {}", min_col),
534 self.toks[q].line,
535 ));
536 }
537 self.pos = q;
538 self.bump();
539 break;
540 }
541 if next_col == block_col {
542 self.pos = q;
543 continue;
544 }
545 if next_col < block_col {
546 // block ends without `in`? `in` must appear on an
547 // outer line; treat as error unless next is In handled above
548 if matches!(self.toks[q].tok, Tok::In) {
549 self.pos = q;
550 self.bump();
551 break;
552 }
553 // The `in` could be at a smaller column: look for it
554 return Err(ParseError::new(
555 "expected `in` or another binding",
556 self.toks[q].line,
557 ));
558 }
559 // deeper indentation continues the expression; but the
560 // expression parser should have consumed it. Error.
561 return Err(ParseError::new(
562 "unexpected indentation in let block",
563 self.toks[q].line,
564 ));
565 }
566 other => {
567 return Err(ParseError::new(
568 format!("expected `;`, newline, or `in`, found {}", other.describe()),
569 self.line(),
570 ))
571 }
572 }
573 }
574 // A binding is in scope in the expressions before it too (§4.1), but
575 // it was not yet in `locals` while they were parsed: a binder in one
576 // of them that reuses its name is caught here instead.
577 for (n, _) in &names {
578 if let Some(&(k, line)) = self.last_binder.get(n) {
579 if k >= first_binder {
580 return Err(shadowed(n, line));
581 }
582 }
583 }
584 for (n, line) in &names {
585 self.note_binder(n, *line);
586 }
587 let body = self.parse_expr(min_col)?;
588 self.height = self.within(h.max(self.height) + 1)?;
589 for (n, _) in &names {
590 self.locals.remove(n);
591 }
592 Ok(Expr::Let(bindings, Rc::new(body)))
593 }
595 /// §4.2: a binder may not reuse a top-level or builtin name, nor one
596 /// bound by an enclosing lambda or `let`.
597 fn check_shadow(&self, name: &str) -> Result<(), ParseError> {
598 if self.outer_names.contains(name) || self.locals.contains(name) {
599 return Err(shadowed(name, self.line()));
600 }
601 Ok(())
602 }
604 /// Record a local binder for the check at the end of each enclosing
605 /// `let` block's bindings.
606 fn note_binder(&mut self, name: &str, line: usize) {
607 self.last_binder.insert(name.to_string(), (self.binders, line));
608 self.binders += 1;
609 }
611 fn parse_or(&mut self, min_col: usize) -> Result<Expr, ParseError> {
612 // `or` is infixl 0 and extends as far right as possible
613 let mut lhs = self.parse_opexpr(1, min_col)?;
614 let mut h = self.height;
615 loop {
616 self.skip_layout_newlines(min_col);
617 if matches!(self.peek(), Tok::Or) {
618 self.bump();
619 let rhs = self.nested(|p| p.parse_or(min_col))?;
620 h = self.within(h.max(self.height) + 1)?;
621 lhs = Expr::Or(Rc::new(lhs), Rc::new(rhs));
622 } else {
623 break;
624 }
625 }
626 self.height = h;
627 Ok(lhs)
628 }
630 /// precedence-climbing over the fixity table
631 fn parse_opexpr(&mut self, min_prec: u8, min_col: usize) -> Result<Expr, ParseError> {
632 let mut lhs = self.parse_app(min_col)?;
633 let mut h = self.height;
634 loop {
635 self.skip_op_newline(min_col);
636 let op: &'static str = match self.peek() {
637 Tok::Op(o) => o,
638 _ => break,
639 };
640 let (prec, right) = match fixity(op) {
641 Some(f) => f,
642 None => break,
643 };
644 if prec < min_prec {
645 break;
646 }
647 self.bump();
648 // left section: `(e op)` — a trailing operator before `)`
649 if matches!(self.peek(), Tok::RParen) {
650 self.section_op = Some(op);
651 self.height = h;
652 return Ok(lhs);
653 }
654 let next_min = if right { prec } else { prec + 1 };
655 let rhs = self.nested(|p| p.parse_opexpr(next_min, min_col))?;
656 // non-assoc check: if lhs is the same operator, reject chaining
657 if is_nonassoc(op) {
658 // a non-associative operator cannot be chained; explicit
659 // parentheses break the chain
660 if let Expr::BinOp(o2, _, _) = &lhs {
661 if is_nonassoc(o2) {
662 return Err(ParseError::new(
663 format!("`{}` is non-associative and cannot be chained", op),
664 self.line(),
665 ));
666 }
667 }
668 if let Expr::BinOp(o2, _, _) = &rhs {
669 if is_nonassoc(o2) && *o2 == op {
670 return Err(ParseError::new(
671 format!("`{}` is non-associative and cannot be chained", op),
672 self.line(),
673 ));
674 }
675 }
676 }
677 h = self.within(h.max(self.height) + 1)?;
678 lhs = Expr::BinOp(op, Rc::new(lhs), Rc::new(rhs));
679 }
680 self.height = h;
681 Ok(lhs)
682 }
684 /// allow an operator at the start of a continuation line (column > min_col)
685 fn skip_op_newline(&mut self, min_col: usize) {
686 if !matches!(self.peek(), Tok::Newline) {
687 return;
688 }
689 let mut p = self.pos;
690 while matches!(self.toks[p].tok, Tok::Newline) {
691 p += 1;
692 }
693 if matches!(self.toks[p].tok, Tok::Op(_)) && self.toks[p].col > min_col {
694 self.pos = p;
695 }
696 }
698 fn starts_atom(t: &Tok) -> bool {
699 matches!(
700 t,
701 Tok::Ident(_)
702 | Tok::TypeName(_)
703 | Tok::Int(_)
704 | Tok::Text(_)
705 | Tok::IdLit(_)
706 | Tok::NewId
707 | Tok::LabelLit(_)
708 | Tok::PathLit(_)
709 | Tok::True
710 | Tok::False
711 | Tok::LParen
712 | Tok::LBracket
713 | Tok::LBrace
714 | Tok::Selector(_)
715 )
716 }
718 fn parse_app(&mut self, min_col: usize) -> Result<Expr, ParseError> {
719 let mut e = self.parse_postfix(min_col)?;
720 let mut h = self.height;
721 loop {
722 // application across a newline requires deeper indentation
723 if matches!(self.peek(), Tok::Newline) {
724 let mut p = self.pos;
725 while matches!(self.toks[p].tok, Tok::Newline) {
726 p += 1;
727 }
728 if Self::starts_atom(&self.toks[p].tok) && self.toks[p].col > min_col {
729 self.pos = p;
730 } else {
731 break;
732 }
733 }
734 if Self::starts_atom(self.peek()) {
735 let arg = self.parse_postfix(min_col)?;
736 h = self.within(h.max(self.height) + 1)?;
737 e = Expr::App(Rc::new(e), Rc::new(arg));
738 } else {
739 break;
740 }
741 }
742 self.height = h;
743 Ok(e)
744 }
746 fn parse_postfix(&mut self, min_col: usize) -> Result<Expr, ParseError> {
747 let mut e = self.parse_atom(min_col)?;
748 let mut h = self.height;
749 loop {
750 match self.peek().clone() {
751 Tok::Selector(f) => {
752 self.bump();
753 h = self.within(h + 1)?;
754 e = Expr::Select(Rc::new(e), f);
755 }
756 Tok::LBrace => {
757 // record update (or a record literal argument? no —
758 // postfix binds tighter than application, so `{` after an
759 // atom is an update)
760 self.bump();
761 // two levels, like a record literal's braces, so a second
762 // level of the descent to match (see `MAX_DEPTH`)
763 let fields = self.nested(|p| p.parse_fields(min_col, true))?;
764 h = self.within(h.max(self.height) + 2)?;
765 e = Expr::Update(Rc::new(e), fields);
766 }
767 // a Newline ends the chain too: a selector or `{` that
768 // begins a line is the next postfix, not this one's (§3.3)
769 _ => break,
770 }
771 }
772 self.height = h;
773 Ok(e)
774 }
776 /// parse `ident = expr, ...` inside braces. `update` controls the error message.
777 fn parse_fields(
778 &mut self,
779 min_col: usize,
780 _update: bool,
781 ) -> Result<Vec<(String, Rc<Expr>)>, ParseError> {
782 let mut fields: Vec<(String, Rc<Expr>)> = Vec::new();
783 self.skip_layout_newlines(min_col);
784 if matches!(self.peek(), Tok::RBrace) {
785 self.bump();
786 // nothing inside the braces
787 self.height = 0;
788 return Ok(fields);
789 }
790 // the height of the highest field
791 let mut h = 0;
792 loop {
793 let name = match self.bump() {
794 Tok::Ident(n) => n,
795 other => {
796 return Err(ParseError::new(
797 format!("expected a field name, found {}", other.describe()),
798 self.line(),
799 ))
800 }
801 };
802 if fields.iter().any(|(n, _)| *n == name) {
803 return Err(ParseError::new(
804 format!("duplicate field `{}`", name),
805 self.line(),
806 ));
807 }
808 self.expect(&Tok::Equals)?;
809 let v = self.parse_expr(min_col)?;
810 h = h.max(self.height);
811 fields.push((name, Rc::new(v)));
812 self.skip_layout_newlines(min_col);
813 match self.peek() {
814 Tok::Comma => {
815 self.bump();
816 self.skip_layout_newlines(min_col);
817 }
818 Tok::RBrace => {
819 self.bump();
820 break;
821 }
822 other => {
823 return Err(ParseError::new(
824 format!("expected `,` or `}}`, found {}", other.describe()),
825 self.line(),
826 ))
827 }
828 }
829 }
830 self.height = h;
831 Ok(fields)
832 }
834 fn parse_atom(&mut self, min_col: usize) -> Result<Expr, ParseError> {
835 self.nested(|p| p.parse_atom_inner(min_col))
836 }
838 fn parse_atom_inner(&mut self, min_col: usize) -> Result<Expr, ParseError> {
839 // one level, unless an arm below builds more around what it parses
840 self.height = 1;
841 match self.peek().clone() {
842 Tok::Ident(n) => {
843 self.bump();
844 Ok(Expr::Var(n))
845 }
846 Tok::TypeName(n) => {
847 self.bump();
848 Ok(Expr::TypeName(n))
849 }
850 Tok::Int(n) => {
851 self.bump();
852 Ok(Expr::Int(n))
853 }
854 Tok::Text(s) => {
855 self.bump();
856 Ok(Expr::Text(s))
857 }
858 Tok::IdLit(s) => {
859 self.bump();
860 Ok(Expr::IdLit(s))
861 }
862 Tok::NewId => {
863 self.bump();
864 Ok(Expr::NewId)
865 }
866 Tok::LabelLit(s) => {
867 self.bump();
868 Ok(Expr::LabelLit(s))
869 }
870 Tok::PathLit(p) => {
871 self.bump();
872 Ok(Expr::PathLit(p))
873 }
874 Tok::True => {
875 self.bump();
876 Ok(Expr::Bool(true))
877 }
878 Tok::False => {
879 self.bump();
880 Ok(Expr::Bool(false))
881 }
882 Tok::Selector(f) => {
883 self.bump();
884 Ok(Expr::SelectorFun(f))
885 }
886 Tok::LBracket => self.parse_list(min_col),
887 Tok::LBrace => {
888 self.bump();
889 let fields = self.parse_fields(min_col, false)?;
890 // the braces are two levels, as they open two of the
891 // descent: this atom and the field (see `MAX_DEPTH`)
892 self.height = self.within(self.height + 2)?;
893 Ok(Expr::Record(fields))
894 }
895 Tok::LParen => self.parse_paren(min_col),
896 other => Err(ParseError::new(
897 format!("unexpected {}", other.describe()),
898 self.line(),
899 )),
900 }
901 }
903 fn parse_list(&mut self, min_col: usize) -> Result<Expr, ParseError> {
904 self.bump();
905 let mut elems = Vec::new();
906 let mut h = 0;
907 loop {
908 self.skip_layout_newlines(min_col);
909 if matches!(self.peek(), Tok::RBracket) {
910 self.bump();
911 break;
912 }
913 let e = self.parse_postfix(min_col)?;
914 h = h.max(self.height);
915 elems.push(Rc::new(e));
916 }
917 self.height = self.within(h + 1)?;
918 Ok(Expr::List(elems))
919 }
921 fn parse_paren(&mut self, min_col: usize) -> Result<Expr, ParseError> {
922 let open = self.toks[self.pos].clone();
923 self.bump();
924 // (op) | (op expr) | (expr op) | (expr)
925 if let Tok::Op(o) = self.peek().clone() {
926 self.bump();
927 self.skip_layout_newlines(min_col);
928 if matches!(self.peek(), Tok::RParen) {
929 self.bump();
930 return Ok(Expr::Var(o.to_string()));
931 }
932 // right section: (op e) = \x -> x op e
933 let e = self.parse_expr(min_col)?;
934 // `(op e op)` is no production (§3.4); unchecked, the
935 // trailing operator would be dropped here and left set
936 // for the next `(e)` to take as a left section
937 if let Some(o2) = self.section_op.take() {
938 return Err(ParseError::new(
939 format!(
940 "a section cannot have operators on both sides (`{}` and `{}`)",
941 o, o2
942 ),
943 self.line(),
944 ));
945 }
946 self.expect(&Tok::RParen)?;
947 // a lambda around an operator: two levels
948 self.height = self.within(self.height + 2)?;
949 let var = fresh_var();
950 let body = Expr::BinOp(
951 o,
952 Rc::new(Expr::Var(var.clone())),
953 Rc::new(e),
954 );
955 return Ok(Expr::Lambda(
956 vec![Pattern::Var(var)],
957 Rc::new(body),
958 self.source_slice(&open),
959 ));
960 }
961 let first = self.parse_expr(min_col)?;
962 // a parenthesis is two levels, as is a section's lambda
963 // around its operator
964 self.height = self.within(self.height + 2)?;
965 self.skip_layout_newlines(min_col);
966 if let Some(o) = self.section_op.take() {
967 // left section: (e op) = \x -> e op x
968 self.expect(&Tok::RParen)?;
969 let var = fresh_var();
970 let body = Expr::BinOp(
971 o,
972 Rc::new(first),
973 Rc::new(Expr::Var(var.clone())),
974 );
975 return Ok(Expr::Lambda(
976 vec![Pattern::Var(var)],
977 Rc::new(body),
978 self.source_slice(&open),
979 ));
980 }
981 self.expect(&Tok::RParen)?;
982 Ok(Expr::Paren(Rc::new(first)))
983 }
985 /// The source of a lambda or section, from its first token `start` to
986 /// the last token consumed, for its rendering (§5.2: exactly as
987 /// written). Line breaks the layout rules skipped looking for more of it
988 /// are not part of it, nor is a comment after its last token.
989 fn source_slice(&self, start: &SpTok) -> Source {
990 let mut last = self.pos - 1;
991 while matches!(self.toks[last].tok, Tok::Newline) {
992 last -= 1;
993 }
994 Source::new(self.src.clone(), start.start, self.toks[last].end)
995 }
997 /// Parse a single command-line expression. Layout rule 1 does not apply.
998 pub fn parse_cli_expr(&mut self) -> Result<Expr, ParseError> {
999 self.skip_newlines();
1000 // inside nothing, so it opens no level (see `nested`)
1001 let e = self.parse_expr_inner(0)?;
1002 self.skip_newlines();
1003 if !matches!(self.peek(), Tok::Eof) {
1004 return Err(ParseError::new(
1005 format!("unexpected {} after the expression", self.peek().describe()),
1006 self.line(),
1007 ));
1009 Ok(e)
1013fn shadowed(name: &str, line: usize) -> ParseError {
1014 ParseError::new(format!("`{}` is already bound and may not be shadowed", name), line)
1017use std::sync::atomic::{AtomicUsize, Ordering};
1018static FRESH: AtomicUsize = AtomicUsize::new(0);
1019fn fresh_var() -> String {
1020 format!("$sec{}", FRESH.fetch_add(1, Ordering::Relaxed))
1023pub fn parse_config(src: &str, outer_names: Rc<BTreeSet<String>>) -> Result<Vec<Item>, ParseError> {
1024 let mut p = Parser::new(src, outer_names)?;
1025 p.parse_config()
1028pub fn parse_expr(src: &str, outer_names: Rc<BTreeSet<String>>) -> Result<Expr, ParseError> {
1029 let mut p = Parser::new(src, outer_names)?;
1030 p.parse_cli_expr()
1033/// Re-render a lambda as source text (used for display of closures).
1034pub fn render_lambda(params: &[Pattern], body: &Expr) -> String {
1035 let ps: Vec<String> = params
1036 .iter()
1037 .map(|p| match p {
1038 Pattern::Var(n) => n.clone(),
1039 Pattern::Wildcard => "_".into(),
1040 })
1041 .collect();
1042 format!("\\{} -> {}", ps.join(" "), render_expr(body))
1045pub fn render_expr(e: &Expr) -> String {
1046 match e {
1047 Expr::Var(n) => n.clone(),
1048 Expr::TypeName(n) => n.clone(),
1049 Expr::Int(n) => n.to_string(),
1050 Expr::Text(s) => format!("{:?}", s),
1051 Expr::IdLit(s) => format!("@{}", s),
1052 Expr::Id(s) => format!("@{}", s),
1053 Expr::NewId => "@".into(),
1054 Expr::LabelLit(s) => format!("%{}", s),
1055 Expr::PathLit(p) => {
1056 if p.is_empty() {
1057 "./".into()
1058 } else {
1059 format!("./{}", p.join("/"))
1062 Expr::Bool(b) => b.to_string(),
1063 Expr::Lambda(ps, b, _) => render_lambda(ps, b),
1064 Expr::If(c, t, f) => format!(
1065 "if {} then {} else {}",
1066 render_expr(c),
1067 render_expr(t),
1068 render_expr(f)
1069 ),
1070 Expr::Let(bs, b) => {
1071 let parts: Vec<String> = bs
1072 .iter()
1073 .map(|(n, e)| format!("{} = {}", n, render_expr(e)))
1074 .collect();
1075 format!("let {} in {}", parts.join("; "), render_expr(b))
1077 Expr::App(f, x) => {
1078 let fs = match f.as_ref() {
1079 Expr::App(_, _) => format!("({})", render_expr(f)),
1080 Expr::Paren(_) => render_expr(f),
1081 _ => render_expr(f),
1082 };
1083 format!("{} ({})", fs, render_expr(x))
1085 Expr::BinOp(o, a, b) => format!("({} {} {})", render_expr(a), o, render_expr(b)),
1086 Expr::Or(a, b) => format!("({} or {})", render_expr(a), render_expr(b)),
1087 Expr::Select(e, f) => format!("{}.{}", render_expr(e), f),
1088 Expr::Update(e, fs) => {
1089 let parts: Vec<String> = fs
1090 .iter()
1091 .map(|(n, v)| format!("{} = {}", n, render_expr(v)))
1092 .collect();
1093 format!("{} {{ {} }}", render_expr(e), parts.join(", "))
1095 Expr::Record(fs) => {
1096 let parts: Vec<String> = fs
1097 .iter()
1098 .map(|(n, v)| format!("{} = {}", n, render_expr(v)))
1099 .collect();
1100 format!("{{ {} }}", parts.join(", "))
1102 Expr::List(es) => {
1103 let parts: Vec<String> = es.iter().map(|e| render_expr(e)).collect();
1104 format!("[{}]", parts.join(" "))
1106 Expr::SelectorFun(f) => format!(".{}", f),
1107 Expr::Paren(e) => render_expr(e),
1108 Expr::Crash => "crash".into(),
1112/// helper used by tests
1113pub fn int(n: i64) -> Expr {
1114 Expr::Int(BigInt::from(n))