GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
3c5b548ae50c8ba069b8197d5a17b36d4a5f5848

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_parse/src

compiler/qsc_parse/src/expr.rs

812lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! Expression parsing makes use of Pratt parsing (or “top-down operator-precedence parsing”) to handle
5//! relative precedence of operators.
6
7#[cfg(test)]
8mod tests;
9
10use crate::{
11 completion::WordKinds,
12 keyword::Keyword,
13 lex::{
14 ClosedBinOp, Delim, InterpolatedEnding, InterpolatedStart, Radix, StringToken, Token,
15 TokenKind,
16 },
17 prim::{ident, opt, pat, recovering_path, recovering_token, seq, shorten, token},
18 scan::ParserContext,
19 stmt, Error, ErrorKind, Result,
20};
21use num_bigint::BigInt;
22use num_traits::Num;
23use qsc_ast::ast::{
24 self, BinOp, CallableKind, Expr, ExprKind, FieldAssign, Functor, Lit, NodeId, Pat, PatKind,
25 PathKind, Pauli, StringComponent, TernOp, UnOp,
26};
27use qsc_data_structures::span::Span;
28use std::{result, str::FromStr};
29
30struct PrefixOp {
31 kind: UnOp,
32 precedence: u8,
33}
34
35struct MixfixOp {
36 kind: OpKind,
37 precedence: u8,
38}
39
40enum OpKind {
41 Postfix(UnOp),
42 Binary(BinOp, Assoc),
43 Ternary(TernOp, TokenKind, Assoc),
44 Rich(fn(&mut ParserContext, Box<Expr>) -> Result<Box<ExprKind>>),
45}
46
47#[derive(Clone, Copy)]
48enum OpName {
49 Token(TokenKind),
50 Keyword(Keyword),
51}
52
53#[derive(Clone, Copy)]
54enum OpContext {
55 Precedence(u8),
56 Stmt,
57}
58
59#[derive(Clone, Copy)]
60enum Assoc {
61 Left,
62 Right,
63}
64
65const LAMBDA_PRECEDENCE: u8 = 1;
66
67const RANGE_PRECEDENCE: u8 = 1;
68
69pub(super) fn expr(s: &mut ParserContext) -> Result<Box<Expr>> {
70 expr_op(s, OpContext::Precedence(0))
71}
72
73pub(super) fn expr_eof(s: &mut ParserContext) -> Result<Box<Expr>> {
74 let expr = expr(s)?;
75 token(s, TokenKind::Eof)?;
76 Ok(expr)
77}
78
79pub(super) fn expr_stmt(s: &mut ParserContext) -> Result<Box<Expr>> {
80 expr_op(s, OpContext::Stmt)
81}
82
83/// Returns true if the expression kind is statement-final. When a statement-final expression occurs
84/// at the top level of an expression statement, it indicates the end of the statement, and any
85/// operators following it will not be parsed as part of the expression. Statement-final expressions
86/// in a top level position also do not require a semicolon when they are followed by another
87/// statement.
88pub(super) fn is_stmt_final(kind: &ExprKind) -> bool {
89 matches!(
90 kind,
91 ExprKind::Block(..)
92 | ExprKind::Conjugate(..)
93 | ExprKind::For(..)
94 | ExprKind::If(..)
95 | ExprKind::Repeat(..)
96 | ExprKind::While(..)
97 )
98}
99
100fn expr_op(s: &mut ParserContext, context: OpContext) -> Result<Box<Expr>> {
101 let lo = s.peek().span.lo;
102
103 s.expect(WordKinds::AdjointUpper | WordKinds::ControlledUpper | WordKinds::Not);
104 let mut lhs = if let Some(op) = prefix_op(op_name(s)) {
105 s.advance();
106 let rhs = expr_op(s, OpContext::Precedence(op.precedence))?;
107 Box::new(Expr {
108 id: NodeId::default(),
109 span: s.span(lo),
110 kind: Box::new(ExprKind::UnOp(op.kind, rhs)),
111 })
112 } else {
113 expr_base(s)?
114 };
115
116 let min_precedence = match context {
117 OpContext::Precedence(p) => p,
118 OpContext::Stmt if is_stmt_final(&lhs.kind) => return Ok(lhs),
119 OpContext::Stmt => 0,
120 };
121
122 s.expect(WordKinds::And | WordKinds::Or);
123 while let Some(op) = mixfix_op(op_name(s)) {
124 if op.precedence < min_precedence {
125 break;
126 }
127
128 s.advance();
129 let kind = match op.kind {
130 OpKind::Postfix(kind) => Box::new(ExprKind::UnOp(kind, lhs)),
131 OpKind::Binary(kind, assoc) => {
132 let precedence = next_precedence(op.precedence, assoc);
133 let rhs = expr_op(s, OpContext::Precedence(precedence))?;
134 Box::new(ExprKind::BinOp(kind, lhs, rhs))
135 }
136 OpKind::Ternary(kind, delim, assoc) => {
137 let mid = expr(s)?;
138 token(s, delim)?;
139 let precedence = next_precedence(op.precedence, assoc);
140 let rhs = expr_op(s, OpContext::Precedence(precedence))?;
141 Box::new(ExprKind::TernOp(kind, lhs, mid, rhs))
142 }
143 OpKind::Rich(f) => f(s, lhs)?,
144 };
145
146 lhs = Box::new(Expr {
147 id: NodeId::default(),
148 span: s.span(lo),
149 kind,
150 });
151 }
152
153 Ok(lhs)
154}
155
156fn expr_base(s: &mut ParserContext) -> Result<Box<Expr>> {
157 let lo = s.peek().span.lo;
158 let kind = if token(s, TokenKind::Open(Delim::Paren)).is_ok() {
159 let (exprs, final_sep) = seq(s, expr)?;
160 token(s, TokenKind::Close(Delim::Paren))?;
161 Ok(Box::new(final_sep.reify(
162 exprs,
163 ExprKind::Paren,
164 ExprKind::Tuple,
165 )))
166 } else if token(s, TokenKind::DotDotDot).is_ok() {
167 expr_range_prefix(s)
168 } else if token(s, TokenKind::Keyword(Keyword::Underscore)).is_ok() {
169 Ok(Box::new(ExprKind::Hole))
170 } else if token(s, TokenKind::Keyword(Keyword::Fail)).is_ok() {
171 Ok(Box::new(ExprKind::Fail(expr(s)?)))
172 } else if token(s, TokenKind::Keyword(Keyword::For)).is_ok() {
173 let peeked = s.peek();
174 let vars = match pat(s) {
175 Ok(o) => o,
176 Err(e) => {
177 if let (
178 TokenKind::Open(Delim::Paren),
179 ErrorKind::Token(_, TokenKind::Keyword(Keyword::In), _),
180 ) = (peeked.kind, &e.0)
181 {
182 return Err(
183 e.with_help("parenthesis are not permitted around for-loop iterations")
184 );
185 }
186 return Err(e);
187 }
188 };
189 token(s, TokenKind::Keyword(Keyword::In))?;
190 let iter = expr(s)?;
191 let body = stmt::parse_block(s)?;
192 Ok(Box::new(ExprKind::For(vars, iter, body)))
193 } else if token(s, TokenKind::Keyword(Keyword::If)).is_ok() {
194 expr_if(s)
195 } else if let Some(components) = opt(s, expr_interpolate)? {
196 Ok(Box::new(ExprKind::Interpolate(
197 components.into_boxed_slice(),
198 )))
199 } else if token(s, TokenKind::Keyword(Keyword::Repeat)).is_ok() {
200 let body = stmt::parse_block(s)?;
201 token(s, TokenKind::Keyword(Keyword::Until))?;
202 let cond = expr(s)?;
203 let fixup = if token(s, TokenKind::Keyword(Keyword::Fixup)).is_ok() {
204 Some(stmt::parse_block(s)?)
205 } else {
206 None
207 };
208 Ok(Box::new(ExprKind::Repeat(body, cond, fixup)))
209 } else if token(s, TokenKind::Keyword(Keyword::Return)).is_ok() {
210 Ok(Box::new(ExprKind::Return(expr(s)?)))
211 } else if token(s, TokenKind::Keyword(Keyword::Set)).is_ok() {
212 expr_set(s)
213 } else if token(s, TokenKind::Keyword(Keyword::While)).is_ok() {
214 Ok(Box::new(ExprKind::While(expr(s)?, stmt::parse_block(s)?)))
215 } else if token(s, TokenKind::Keyword(Keyword::Within)).is_ok() {
216 let outer = stmt::parse_block(s)?;
217 token(s, TokenKind::Keyword(Keyword::Apply))?;
218 let inner = stmt::parse_block(s)?;
219 Ok(Box::new(ExprKind::Conjugate(outer, inner)))
220 } else if token(s, TokenKind::Keyword(Keyword::New)).is_ok() {
221 recovering_struct(s)
222 } else if let Some(a) = opt(s, expr_array)? {
223 Ok(a)
224 } else if let Some(b) = opt(s, stmt::parse_block)? {
225 Ok(Box::new(ExprKind::Block(b)))
226 } else if let Some(l) = lit(s)? {
227 Ok(Box::new(ExprKind::Lit(Box::new(l))))
228 } else if let Some(p) = opt(s, |s| recovering_path(s, WordKinds::PathExpr))? {
229 Ok(Box::new(ExprKind::Path(p)))
230 } else {
231 Err(Error::new(ErrorKind::Rule(
232 "expression",
233 s.peek().kind,
234 s.peek().span,
235 )))
236 }?;
237
238 Ok(Box::new(Expr {
239 id: NodeId::default(),
240 span: s.span(lo),
241 kind,
242 }))
243}
244
245/// A struct expression excluding the `new` keyword,
246/// e.g. `A { a = b, c = d }`
247fn recovering_struct(s: &mut ParserContext) -> Result<Box<ExprKind>> {
248 let name = recovering_path(s, WordKinds::PathStruct)?;
249
250 if let Err(e) = token(s, TokenKind::Open(Delim::Brace)) {
251 s.push_error(e);
252 return Ok(Box::new(ExprKind::Struct(name, None, Box::new([]))));
253 }
254
255 let (copy, fields) = struct_fields(s)?;
256 recovering_token(s, TokenKind::Close(Delim::Brace));
257 Ok(Box::new(ExprKind::Struct(name, copy, fields)))
258}
259
260/// A sequence of field assignments and an optional base expression,
261/// e.g. `...a, b = c, d = e`
262#[allow(clippy::type_complexity)]
263fn struct_fields(
264 s: &mut ParserContext<'_>,
265) -> Result<(Option<Box<Expr>>, Box<[Box<FieldAssign>]>)> {
266 let copy: Option<Box<Expr>> = opt(s, |s| {
267 token(s, TokenKind::DotDotDot)?;
268 expr(s)
269 })?;
270 let mut fields = vec![];
271 if copy.is_none() || copy.is_some() && token(s, TokenKind::Comma).is_ok() {
272 (fields, _) = seq(s, parse_field_assign)?;
273 }
274 Ok((copy, fields.into_boxed_slice()))
275}
276
277fn parse_field_assign(s: &mut ParserContext) -> Result<Box<FieldAssign>> {
278 let lo = s.peek().span.lo;
279 let field = ident(s)?;
280 token(s, TokenKind::Eq)?;
281 let value = expr(s)?;
282 Ok(Box::new(FieldAssign {
283 id: NodeId::default(),
284 span: s.span(lo),
285 field,
286 value,
287 }))
288}
289
290fn expr_if(s: &mut ParserContext) -> Result<Box<ExprKind>> {
291 let cond = expr(s)?;
292 let body = stmt::parse_block(s)?;
293 let lo = s.peek().span.lo;
294
295 let otherwise = if token(s, TokenKind::Keyword(Keyword::Elif)).is_ok() {
296 Some(expr_if(s)?)
297 } else if token(s, TokenKind::Keyword(Keyword::Else)).is_ok() {
298 Some(Box::new(ExprKind::Block(stmt::parse_block(s)?)))
299 } else {
300 None
301 }
302 .map(|kind| {
303 Box::new(Expr {
304 id: NodeId::default(),
305 span: s.span(lo),
306 kind,
307 })
308 });
309
310 Ok(Box::new(ExprKind::If(cond, body, otherwise)))
311}
312
313fn expr_set(s: &mut ParserContext) -> Result<Box<ExprKind>> {
314 let lhs = expr(s)?;
315 if token(s, TokenKind::Eq).is_ok() {
316 let rhs = expr(s)?;
317 Ok(Box::new(ExprKind::Assign(lhs, rhs)))
318 } else if token(s, TokenKind::WSlashEq).is_ok() {
319 let index = expr(s)?;
320 token(s, TokenKind::LArrow)?;
321 let rhs = expr(s)?;
322 Ok(Box::new(ExprKind::AssignUpdate(lhs, index, rhs)))
323 } else if let TokenKind::BinOpEq(op) = s.peek().kind {
324 s.advance();
325 let rhs = expr(s)?;
326 Ok(Box::new(ExprKind::AssignOp(closed_bin_op(op), lhs, rhs)))
327 } else {
328 Err(Error::new(ErrorKind::Rule(
329 "assignment operator",
330 s.peek().kind,
331 s.peek().span,
332 )))
333 }
334}
335
336fn expr_array(s: &mut ParserContext) -> Result<Box<ExprKind>> {
337 token(s, TokenKind::Open(Delim::Bracket))?;
338 let kind = expr_array_core(s)?;
339 token(s, TokenKind::Close(Delim::Bracket))?;
340 Ok(kind)
341}
342
343fn expr_array_core(s: &mut ParserContext) -> Result<Box<ExprKind>> {
344 let Some(first) = opt(s, expr)? else {
345 return Ok(Box::new(ExprKind::Array(Vec::new().into_boxed_slice())));
346 };
347
348 if token(s, TokenKind::Comma).is_err() {
349 return Ok(Box::new(ExprKind::Array(vec![first].into_boxed_slice())));
350 }
351
352 s.expect(WordKinds::Size);
353 let second = expr(s)?;
354 if is_ident("size", &second.kind) && token(s, TokenKind::Eq).is_ok() {
355 let size = expr(s)?;
356 return Ok(Box::new(ExprKind::ArrayRepeat(first, size)));
357 }
358
359 let mut items = vec![first, second];
360 if token(s, TokenKind::Comma).is_ok() {
361 items.append(&mut seq(s, expr)?.0);
362 }
363 Ok(Box::new(ExprKind::Array(items.into_boxed_slice())))
364}
365
366fn is_ident(name: &str, kind: &ExprKind) -> bool {
367 matches!(kind, ExprKind::Path(PathKind::Ok(path)) if path.segments.is_none() && path.name.name.as_ref() == name)
368}
369
370fn expr_range_prefix(s: &mut ParserContext) -> Result<Box<ExprKind>> {
371 let e = opt(s, |s| {
372 expr_op(s, OpContext::Precedence(RANGE_PRECEDENCE + 1))
373 })?;
374
375 Ok(Box::new(if token(s, TokenKind::DotDotDot).is_ok() {
376 ExprKind::Range(None, e, None)
377 } else if token(s, TokenKind::DotDot).is_ok() {
378 let end = expr_op(s, OpContext::Precedence(RANGE_PRECEDENCE + 1))?;
379 ExprKind::Range(None, e, Some(end))
380 } else {
381 ExprKind::Range(None, None, e)
382 }))
383}
384
385fn expr_interpolate(s: &mut ParserContext) -> Result<Vec<StringComponent>> {
386 let token = s.peek();
387 let TokenKind::String(StringToken::Interpolated(InterpolatedStart::DollarQuote, mut end)) =
388 token.kind
389 else {
390 return Err(Error::new(ErrorKind::Rule(
391 "interpolated string",
392 token.kind,
393 token.span,
394 )));
395 };
396
397 let mut components = Vec::new();
398 let lit = shorten(2, 1, s.read());
399 if !lit.is_empty() {
400 components.push(StringComponent::Lit(lit.into()));
401 }
402
403 s.advance();
404 while end == InterpolatedEnding::LBrace {
405 components.push(StringComponent::Expr(expr(s)?));
406
407 let token = s.peek();
408 let TokenKind::String(StringToken::Interpolated(InterpolatedStart::RBrace, next_end)) =
409 token.kind
410 else {
411 return Err(Error::new(ErrorKind::Rule(
412 "interpolated string",
413 token.kind,
414 token.span,
415 )));
416 };
417
418 let lit = shorten(1, 1, s.read());
419 if !lit.is_empty() {
420 components.push(StringComponent::Lit(lit.into()));
421 }
422
423 s.advance();
424 end = next_end;
425 }
426
427 Ok(components)
428}
429
430fn lit(s: &mut ParserContext) -> Result<Option<Lit>> {
431 let lexeme = s.read();
432
433 s.expect(
434 WordKinds::True
435 | WordKinds::False
436 | WordKinds::Zero
437 | WordKinds::One
438 | WordKinds::PauliX
439 | WordKinds::PauliY
440 | WordKinds::PauliZ
441 | WordKinds::PauliI,
442 );
443
444 let token = s.peek();
445 match lit_token(lexeme, token) {
446 Ok(Some(lit)) => {
447 s.advance();
448 Ok(Some(lit))
449 }
450 Ok(None) => Ok(None),
451 Err(err) => {
452 s.advance();
453 Err(err)
454 }
455 }
456}
457
458#[allow(clippy::inline_always)]
459#[inline(always)]
460fn lit_token(lexeme: &str, token: Token) -> Result<Option<Lit>> {
461 match token.kind {
462 TokenKind::BigInt(radix) => {
463 let offset = if radix == Radix::Decimal { 0 } else { 2 };
464 let lexeme = &lexeme[offset..lexeme.len() - 1]; // Slice off prefix and suffix.
465 let value = BigInt::from_str_radix(lexeme, radix.into())
466 .map_err(|_| Error::new(ErrorKind::Lit("big-integer", token.span)))?;
467 Ok(Some(Lit::BigInt(Box::new(value))))
468 }
469 TokenKind::Float => {
470 let lexeme = lexeme.replace('_', "");
471 let value = lexeme
472 .parse()
473 .map_err(|_| Error::new(ErrorKind::Lit("floating-point", token.span)))?;
474 Ok(Some(Lit::Double(value)))
475 }
476 TokenKind::Int(radix) => {
477 let offset = if radix == Radix::Decimal { 0 } else { 2 };
478 let value = lit_int(&lexeme[offset..], radix.into())
479 .ok_or(Error::new(ErrorKind::Lit("integer", token.span)))?;
480 Ok(Some(Lit::Int(value)))
481 }
482 TokenKind::String(StringToken::Normal) => {
483 let lexeme = shorten(1, 1, lexeme);
484 let string = unescape(lexeme).map_err(|index| {
485 let ch = lexeme[index + 1..]
486 .chars()
487 .next()
488 .expect("character should be found at index");
489 let index: u32 = index.try_into().expect("index should fit into u32");
490 let lo = token.span.lo + index + 2;
491 let span = Span { lo, hi: lo + 1 };
492 Error::new(ErrorKind::Escape(ch, span))
493 })?;
494 Ok(Some(Lit::String(string.into())))
495 }
496 TokenKind::Keyword(Keyword::True) => Ok(Some(Lit::Bool(true))),
497 TokenKind::Keyword(Keyword::Zero) => Ok(Some(Lit::Result(ast::Result::Zero))),
498 TokenKind::Keyword(Keyword::One) => Ok(Some(Lit::Result(ast::Result::One))),
499 TokenKind::Keyword(Keyword::PauliZ) => Ok(Some(Lit::Pauli(Pauli::Z))),
500 TokenKind::Keyword(Keyword::False) => Ok(Some(Lit::Bool(false))),
501 TokenKind::Keyword(Keyword::PauliX) => Ok(Some(Lit::Pauli(Pauli::X))),
502 TokenKind::Keyword(Keyword::PauliI) => Ok(Some(Lit::Pauli(Pauli::I))),
503 TokenKind::Keyword(Keyword::PauliY) => Ok(Some(Lit::Pauli(Pauli::Y))),
504 _ => Ok(None),
505 }
506}
507
508fn lit_int(lexeme: &str, radix: u32) -> Option<i64> {
509 let multiplier = i64::from(radix);
510 lexeme
511 .chars()
512 .filter(|&c| c != '_')
513 .try_rfold((0i64, 1i64, false), |(value, place, mut overflow), c| {
514 let (increment, over) = i64::from(c.to_digit(radix)?).overflowing_mul(place);
515 overflow |= over;
516
517 let (new_value, over) = value.overflowing_add(increment);
518 overflow |= over;
519
520 // Only treat as overflow if the value is not i64::MIN, since we need to allow once special
521 // case of overflow to allow for minimum value literals.
522 if overflow && new_value != i64::MIN {
523 return None;
524 }
525
526 let (new_place, over) = place.overflowing_mul(multiplier);
527 overflow |= over;
528
529 // If the place overflows, we can still accept the value as long as it's the last digit.
530 // Pass the overflow forward so that it fails if there are more digits.
531 Some((new_value, new_place, overflow))
532 })
533 .map(|(value, _, _)| value)
534}
535
536fn prefix_op(name: OpName) -> Option<PrefixOp> {
537 match name {
538 OpName::Keyword(Keyword::Not) => Some(PrefixOp {
539 kind: UnOp::NotL,
540 precedence: 11,
541 }),
542 OpName::Token(TokenKind::TildeTildeTilde) => Some(PrefixOp {
543 kind: UnOp::NotB,
544 precedence: 11,
545 }),
546 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Plus)) => Some(PrefixOp {
547 kind: UnOp::Pos,
548 precedence: 11,
549 }),
550 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Minus)) => Some(PrefixOp {
551 kind: UnOp::Neg,
552 precedence: 11,
553 }),
554 OpName::Keyword(Keyword::AdjointUpper) => Some(PrefixOp {
555 kind: UnOp::Functor(Functor::Adj),
556 precedence: 14,
557 }),
558 OpName::Keyword(Keyword::ControlledUpper) => Some(PrefixOp {
559 kind: UnOp::Functor(Functor::Ctl),
560 precedence: 14,
561 }),
562 _ => None,
563 }
564}
565
566#[allow(clippy::too_many_lines)]
567fn mixfix_op(name: OpName) -> Option<MixfixOp> {
568 match name {
569 OpName::Token(TokenKind::RArrow) => Some(MixfixOp {
570 kind: OpKind::Rich(|s, input| lambda_op(s, *input, CallableKind::Function)),
571 precedence: LAMBDA_PRECEDENCE,
572 }),
573 OpName::Token(TokenKind::FatArrow) => Some(MixfixOp {
574 kind: OpKind::Rich(|s, input| lambda_op(s, *input, CallableKind::Operation)),
575 precedence: LAMBDA_PRECEDENCE,
576 }),
577 OpName::Token(TokenKind::DotDot) => Some(MixfixOp {
578 kind: OpKind::Rich(range_op),
579 precedence: RANGE_PRECEDENCE,
580 }),
581 OpName::Token(TokenKind::DotDotDot) => Some(MixfixOp {
582 kind: OpKind::Rich(|_, start| Ok(Box::new(ExprKind::Range(Some(start), None, None)))),
583 precedence: RANGE_PRECEDENCE,
584 }),
585 OpName::Token(TokenKind::WSlash) => Some(MixfixOp {
586 kind: OpKind::Ternary(TernOp::Update, TokenKind::LArrow, Assoc::Left),
587 precedence: 1,
588 }),
589 OpName::Token(TokenKind::Question) => Some(MixfixOp {
590 kind: OpKind::Ternary(TernOp::Cond, TokenKind::Bar, Assoc::Right),
591 precedence: 1,
592 }),
593 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Or)) => Some(MixfixOp {
594 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Or), Assoc::Left),
595 precedence: 2,
596 }),
597 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::And)) => Some(MixfixOp {
598 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::And), Assoc::Left),
599 precedence: 3,
600 }),
601 OpName::Token(TokenKind::EqEq) => Some(MixfixOp {
602 kind: OpKind::Binary(BinOp::Eq, Assoc::Left),
603 precedence: 4,
604 }),
605 OpName::Token(TokenKind::Ne) => Some(MixfixOp {
606 kind: OpKind::Binary(BinOp::Neq, Assoc::Left),
607 precedence: 4,
608 }),
609 OpName::Token(TokenKind::Gt) => Some(MixfixOp {
610 kind: OpKind::Binary(BinOp::Gt, Assoc::Left),
611 precedence: 4,
612 }),
613 OpName::Token(TokenKind::Gte) => Some(MixfixOp {
614 kind: OpKind::Binary(BinOp::Gte, Assoc::Left),
615 precedence: 4,
616 }),
617 OpName::Token(TokenKind::Lt) => Some(MixfixOp {
618 kind: OpKind::Binary(BinOp::Lt, Assoc::Left),
619 precedence: 4,
620 }),
621 OpName::Token(TokenKind::Lte) => Some(MixfixOp {
622 kind: OpKind::Binary(BinOp::Lte, Assoc::Left),
623 precedence: 4,
624 }),
625 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::BarBarBar)) => Some(MixfixOp {
626 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::BarBarBar), Assoc::Left),
627 precedence: 5,
628 }),
629 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::CaretCaretCaret)) => Some(MixfixOp {
630 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::CaretCaretCaret), Assoc::Left),
631 precedence: 6,
632 }),
633 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::AmpAmpAmp)) => Some(MixfixOp {
634 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::AmpAmpAmp), Assoc::Left),
635 precedence: 7,
636 }),
637 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::LtLtLt)) => Some(MixfixOp {
638 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::LtLtLt), Assoc::Left),
639 precedence: 8,
640 }),
641 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::GtGtGt)) => Some(MixfixOp {
642 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::GtGtGt), Assoc::Left),
643 precedence: 8,
644 }),
645 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Plus)) => Some(MixfixOp {
646 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Plus), Assoc::Left),
647 precedence: 9,
648 }),
649 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Minus)) => Some(MixfixOp {
650 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Minus), Assoc::Left),
651 precedence: 9,
652 }),
653 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Star)) => Some(MixfixOp {
654 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Star), Assoc::Left),
655 precedence: 10,
656 }),
657 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Slash)) => Some(MixfixOp {
658 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Slash), Assoc::Left),
659 precedence: 10,
660 }),
661 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Percent)) => Some(MixfixOp {
662 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Percent), Assoc::Left),
663 precedence: 10,
664 }),
665 OpName::Token(TokenKind::ClosedBinOp(ClosedBinOp::Caret)) => Some(MixfixOp {
666 kind: OpKind::Binary(closed_bin_op(ClosedBinOp::Caret), Assoc::Right),
667 precedence: 12,
668 }),
669 OpName::Token(TokenKind::Open(Delim::Paren)) => Some(MixfixOp {
670 kind: OpKind::Rich(call_op),
671 precedence: 13,
672 }),
673 OpName::Token(TokenKind::Bang) => Some(MixfixOp {
674 kind: OpKind::Postfix(UnOp::Unwrap),
675 precedence: 15,
676 }),
677 OpName::Token(TokenKind::ColonColon | TokenKind::Dot) => Some(MixfixOp {
678 kind: OpKind::Rich(field_op),
679 precedence: 15,
680 }),
681 OpName::Token(TokenKind::Open(Delim::Bracket)) => Some(MixfixOp {
682 kind: OpKind::Rich(index_op),
683 precedence: 15,
684 }),
685 _ => None,
686 }
687}
688
689fn closed_bin_op(op: ClosedBinOp) -> BinOp {
690 match op {
691 ClosedBinOp::AmpAmpAmp => BinOp::AndB,
692 ClosedBinOp::And => BinOp::AndL,
693 ClosedBinOp::BarBarBar => BinOp::OrB,
694 ClosedBinOp::Caret => BinOp::Exp,
695 ClosedBinOp::CaretCaretCaret => BinOp::XorB,
696 ClosedBinOp::GtGtGt => BinOp::Shr,
697 ClosedBinOp::LtLtLt => BinOp::Shl,
698 ClosedBinOp::Minus => BinOp::Sub,
699 ClosedBinOp::Or => BinOp::OrL,
700 ClosedBinOp::Percent => BinOp::Mod,
701 ClosedBinOp::Plus => BinOp::Add,
702 ClosedBinOp::Slash => BinOp::Div,
703 ClosedBinOp::Star => BinOp::Mul,
704 }
705}
706
707fn lambda_op(s: &mut ParserContext, input: Expr, kind: CallableKind) -> Result<Box<ExprKind>> {
708 let input = expr_as_pat(input)?;
709 let output = expr_op(s, OpContext::Precedence(LAMBDA_PRECEDENCE))?;
710 Ok(Box::new(ExprKind::Lambda(kind, input, output)))
711}
712
713fn field_op(s: &mut ParserContext, lhs: Box<Expr>) -> Result<Box<ExprKind>> {
714 s.expect(WordKinds::Field);
715 Ok(Box::new(ExprKind::Field(lhs, ident(s)?)))
716}
717
718fn index_op(s: &mut ParserContext, lhs: Box<Expr>) -> Result<Box<ExprKind>> {
719 let index = expr(s)?;
720 token(s, TokenKind::Close(Delim::Bracket))?;
721 Ok(Box::new(ExprKind::Index(lhs, index)))
722}
723
724fn call_op(s: &mut ParserContext, lhs: Box<Expr>) -> Result<Box<ExprKind>> {
725 let lo = s.span(0).hi - 1;
726 let (args, final_sep) = seq(s, expr)?;
727 token(s, TokenKind::Close(Delim::Paren))?;
728 let rhs = Box::new(Expr {
729 id: NodeId::default(),
730 span: s.span(lo),
731 kind: Box::new(final_sep.reify(args, ExprKind::Paren, ExprKind::Tuple)),
732 });
733 Ok(Box::new(ExprKind::Call(lhs, rhs)))
734}
735
736fn range_op(s: &mut ParserContext, start: Box<Expr>) -> Result<Box<ExprKind>> {
737 let rhs = expr_op(s, OpContext::Precedence(RANGE_PRECEDENCE + 1))?;
738 Ok(Box::new(if token(s, TokenKind::DotDot).is_ok() {
739 let end = expr_op(s, OpContext::Precedence(RANGE_PRECEDENCE + 1))?;
740 ExprKind::Range(Some(start), Some(rhs), Some(end))
741 } else if token(s, TokenKind::DotDotDot).is_ok() {
742 ExprKind::Range(Some(start), Some(rhs), None)
743 } else {
744 ExprKind::Range(Some(start), None, Some(rhs))
745 }))
746}
747
748fn op_name(s: &ParserContext) -> OpName {
749 match Keyword::from_str(s.read()) {
750 Ok(Keyword::And | Keyword::Or) | Err(()) => OpName::Token(s.peek().kind),
751 Ok(keyword) => OpName::Keyword(keyword),
752 }
753}
754
755fn next_precedence(precedence: u8, assoc: Assoc) -> u8 {
756 match assoc {
757 Assoc::Left => precedence + 1,
758 Assoc::Right => precedence,
759 }
760}
761
762fn expr_as_pat(expr: Expr) -> Result<Box<Pat>> {
763 let kind = Box::new(match *expr.kind {
764 ExprKind::Path(PathKind::Ok(path)) if path.segments.is_none() => {
765 Ok(PatKind::Bind(path.name, None))
766 }
767 ExprKind::Hole => Ok(PatKind::Discard(None)),
768 ExprKind::Range(None, None, None) => Ok(PatKind::Elided),
769 ExprKind::Paren(expr) => Ok(PatKind::Paren(expr_as_pat(*expr)?)),
770 ExprKind::Tuple(exprs) => {
771 let pats = exprs
772 .into_vec()
773 .into_iter()
774 .map(|e| expr_as_pat(*e))
775 .collect::<Result<_>>()?;
776 Ok(PatKind::Tuple(pats))
777 }
778 _ => Err(Error::new(ErrorKind::Convert(
779 "pattern",
780 "expression",
781 expr.span,
782 ))),
783 }?);
784
785 Ok(Box::new(Pat {
786 id: NodeId::default(),
787 span: expr.span,
788 kind,
789 }))
790}
791
792fn unescape(s: &str) -> result::Result<String, usize> {
793 let mut chars = s.char_indices();
794 let mut buf = String::with_capacity(s.len());
795 while let Some((index, ch)) = chars.next() {
796 buf.push(if ch == '\\' {
797 let escape = chars.next().expect("escape should not be empty").1;
798 match escape {
799 '\\' => '\\',
800 '"' => '"',
801 'n' => '\n',
802 'r' => '\r',
803 't' => '\t',
804 _ => return Err(index),
805 }
806 } else {
807 ch
808 });
809 }
810
811 Ok(buf)
812}
813