acir/parser/
mod.rs

1use std::{collections::BTreeSet, str::FromStr};
2
3use acir_field::{AcirField, FieldElement};
4
5use lexer::{Lexer, LexerError};
6use span::Span;
7use thiserror::Error;
8use token::{Keyword, SpannedToken, Token};
9
10use crate::{
11    BlackBoxFunc,
12    circuit::{
13        Circuit, Opcode, Program, PublicInputs,
14        brillig::{BrilligFunctionId, BrilligInputs, BrilligOutputs},
15        opcodes::{AcirFunctionId, BlackBoxFuncCall, BlockId, BlockType, FunctionInput, MemOp},
16    },
17    native_types::{Expression, Witness},
18};
19
20mod lexer;
21mod span;
22#[cfg(test)]
23mod tests;
24mod token;
25
26pub struct AcirParserErrorWithSource {
27    src: String,
28    error: ParserError,
29}
30
31impl AcirParserErrorWithSource {
32    fn parse_error(error: ParserError, src: &str) -> Self {
33        Self { src: src.to_string(), error }
34    }
35
36    #[cfg(test)]
37    pub(super) fn get_error(self) -> ParserError {
38        self.error
39    }
40}
41
42impl std::fmt::Debug for AcirParserErrorWithSource {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        let span = self.error.span();
45
46        let mut byte: usize = 0;
47        for line in self.src.lines() {
48            let has_error =
49                byte <= span.start() as usize && span.end() as usize <= byte + line.len();
50            if has_error {
51                writeln!(f)?;
52            }
53
54            writeln!(f, "{line}")?;
55
56            if has_error {
57                let offset = span.start() as usize - byte;
58                write!(f, "{}", " ".repeat(offset))?;
59                writeln!(f, "{}", "^".repeat((span.end() - span.start()) as usize))?;
60                write!(f, "{}", " ".repeat(offset))?;
61                writeln!(f, "{}", self.error)?;
62                writeln!(f)?;
63            }
64
65            byte += line.len() + 1; // "+ 1" for the newline
66        }
67        Ok(())
68    }
69}
70
71impl FromStr for Program<FieldElement> {
72    type Err = AcirParserErrorWithSource;
73
74    fn from_str(src: &str) -> Result<Self, Self::Err> {
75        Self::from_str_impl(src)
76    }
77}
78
79impl Program<FieldElement> {
80    /// Creates a [Program] object from the given string.
81    #[allow(clippy::should_implement_trait)]
82    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
83        FromStr::from_str(src)
84    }
85
86    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
87        let mut parser =
88            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
89        parser.parse_program().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
90    }
91}
92
93impl FromStr for Circuit<FieldElement> {
94    type Err = AcirParserErrorWithSource;
95
96    fn from_str(src: &str) -> Result<Self, Self::Err> {
97        Self::from_str_impl(src)
98    }
99}
100
101impl Circuit<FieldElement> {
102    /// Creates a [Circuit] object from the given string.
103    #[allow(clippy::should_implement_trait)]
104    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
105        FromStr::from_str(src)
106    }
107
108    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
109        let mut parser =
110            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
111        parser.parse_circuit().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
112    }
113}
114
115impl FromStr for Expression<FieldElement> {
116    type Err = AcirParserErrorWithSource;
117
118    fn from_str(src: &str) -> Result<Self, Self::Err> {
119        Self::from_str_impl(src)
120    }
121}
122
123impl Expression<FieldElement> {
124    /// Creates a [Expression] object from the given string.
125    #[allow(clippy::should_implement_trait)]
126    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
127        FromStr::from_str(src)
128    }
129
130    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
131        let mut parser =
132            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
133        parser
134            .parse_arithmetic_expression()
135            .map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
136    }
137}
138
139pub fn parse_opcodes(src: &str) -> Result<Vec<Opcode<FieldElement>>, AcirParserErrorWithSource> {
140    let mut parser =
141        Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
142    parser.parse_opcodes().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
143}
144
145struct Parser<'a> {
146    lexer: Lexer<'a>,
147    token: SpannedToken,
148    max_witness_index: u32,
149}
150
151impl<'a> Parser<'a> {
152    fn new(source: &'a str) -> ParseResult<Self> {
153        let lexer = Lexer::new(source);
154        let mut parser = Self { lexer, token: eof_spanned_token(), max_witness_index: 0 };
155        parser.token = parser.read_token_internal()?;
156        Ok(parser)
157    }
158
159    /// Parse multiple [Circuit] blocks and return a [Program].
160    fn parse_program(&mut self) -> ParseResult<Program<FieldElement>> {
161        let mut functions: Vec<Circuit<FieldElement>> = Vec::new();
162
163        // We expect top-level "func" keywords for each circuit
164        while self.eat_keyword(Keyword::Function)? {
165            let func_id = self.eat_u32_or_error()?;
166            let expected_id = functions.len() as u32;
167            if func_id != expected_id {
168                return Err(ParserError::UnexpectedFunctionId {
169                    expected: expected_id,
170                    found: func_id,
171                    span: self.token.span(),
172                });
173            }
174
175            let circuit = self.parse_circuit()?;
176
177            functions.push(circuit);
178        }
179
180        // We don't support parsing unconstrained Brillig bytecode blocks
181        let unconstrained_functions = Vec::new();
182        Ok(Program { functions, unconstrained_functions })
183    }
184
185    pub(crate) fn parse_circuit(&mut self) -> ParseResult<Circuit<FieldElement>> {
186        self.max_witness_index = 0;
187
188        let private_parameters = self.parse_private_parameters()?;
189        let public_parameters = PublicInputs(self.parse_public_parameters()?);
190        let return_values = PublicInputs(self.parse_return_values()?);
191
192        let opcodes = self.parse_opcodes()?;
193
194        Ok(Circuit {
195            opcodes,
196            private_parameters,
197            public_parameters,
198            return_values,
199            ..Default::default()
200        })
201    }
202
203    fn parse_private_parameters(&mut self) -> ParseResult<BTreeSet<Witness>> {
204        self.eat_keyword_or_error(Keyword::Private)?;
205        self.eat_keyword_or_error(Keyword::Parameters)?;
206        self.eat_or_error(Token::Colon)?;
207
208        self.parse_witness_ordered_set()
209    }
210
211    fn parse_public_parameters(&mut self) -> ParseResult<BTreeSet<Witness>> {
212        self.eat_keyword_or_error(Keyword::Public)?;
213        self.eat_keyword_or_error(Keyword::Parameters)?;
214        self.eat_or_error(Token::Colon)?;
215
216        self.parse_witness_ordered_set()
217    }
218
219    fn parse_return_values(&mut self) -> ParseResult<BTreeSet<Witness>> {
220        self.eat_keyword_or_error(Keyword::Return)?;
221        self.eat_keyword_or_error(Keyword::Values)?;
222        self.eat_or_error(Token::Colon)?;
223
224        self.parse_witness_ordered_set()
225    }
226
227    fn parse_witness_vector(&mut self) -> ParseResult<Vec<Witness>> {
228        self.parse_bracketed_list(|parser| parser.eat_witness_or_error())
229    }
230
231    fn parse_witness_ordered_set(&mut self) -> ParseResult<BTreeSet<Witness>> {
232        self.parse_witness_vector().map(|vec| vec.into_iter().collect::<BTreeSet<_>>())
233    }
234
235    fn parse_opcodes(&mut self) -> ParseResult<Vec<Opcode<FieldElement>>> {
236        let mut opcodes = Vec::new();
237
238        while let Some(keyword) = self.peek_keyword() {
239            match keyword {
240                Keyword::Assert => {
241                    let expr = self.parse_assert_zero_expression()?;
242                    opcodes.push(Opcode::AssertZero(expr));
243                }
244                Keyword::BlackBoxFuncCall => {
245                    opcodes.push(Opcode::BlackBoxFuncCall(self.parse_blackbox_func_call()?));
246                }
247                Keyword::MemoryInit => {
248                    opcodes.push(self.parse_memory_init()?);
249                }
250                Keyword::MemoryRead => {
251                    opcodes.push(self.parse_memory_read()?);
252                }
253                Keyword::MemoryWrite => {
254                    opcodes.push(self.parse_memory_write()?);
255                }
256                Keyword::Brillig => {
257                    opcodes.push(self.parse_brillig_call()?);
258                }
259                Keyword::Call => {
260                    opcodes.push(self.parse_call()?);
261                }
262                _ => break,
263            }
264        }
265
266        Ok(opcodes)
267    }
268
269    fn parse_assert_zero_expression(&mut self) -> ParseResult<Expression<FieldElement>> {
270        // 'ASSERT'
271        self.eat_keyword_or_error(Keyword::Assert)?;
272
273        // Parse the left-hand side terms
274        let lhs_terms = self.parse_terms_or_error()?;
275
276        // '='
277        self.eat_or_error(Token::Equal)?;
278
279        // Parse the right-hand side terms
280        let rhs_terms = self.parse_terms_or_error()?;
281
282        // If we have something like `0 = ...` or `... = 0`, just consider the expressions
283        // on the non-zero side. Otherwise we could be "moving" terms to the other side and
284        // negating them, which won't accurately reflect the original expression.
285        let expression = if is_zero_term(&lhs_terms) {
286            build_expression_from_terms(rhs_terms.into_iter())
287        } else if is_zero_term(&rhs_terms) {
288            build_expression_from_terms(lhs_terms.into_iter())
289        } else {
290            // "Move" the terms to the left by negating them
291            let rhs_terms = rhs_terms.into_iter().map(|term| term.negate()).collect::<Vec<_>>();
292            build_expression_from_terms(lhs_terms.into_iter().chain(rhs_terms))
293        };
294
295        Ok(expression)
296    }
297
298    fn parse_terms_or_error(&mut self) -> ParseResult<Vec<Term>> {
299        let mut terms = Vec::new();
300        let mut negative = self.eat(Token::Minus)?;
301        loop {
302            let term = self.parse_term_or_error()?;
303            let term = if negative { term.negate() } else { term };
304            terms.push(term);
305
306            if self.eat(Token::Plus)? {
307                negative = false;
308                continue;
309            }
310
311            if self.eat(Token::Minus)? {
312                negative = true;
313                continue;
314            }
315
316            break;
317        }
318        Ok(terms)
319    }
320
321    fn parse_term_or_error(&mut self) -> ParseResult<Term> {
322        if let Some(coefficient) = self.eat_field_element()? {
323            if self.eat(Token::Star)? {
324                let w1 = self.eat_witness_or_error()?;
325                self.parse_linear_or_multiplication_term(coefficient, w1)
326            } else {
327                Ok(Term::Constant(coefficient))
328            }
329        } else if let Some(w1) = self.eat_witness()? {
330            self.parse_linear_or_multiplication_term(FieldElement::one(), w1)
331        } else {
332            self.expected_term()
333        }
334    }
335
336    fn parse_linear_or_multiplication_term(
337        &mut self,
338        coefficient: FieldElement,
339        w1: Witness,
340    ) -> Result<Term, ParserError> {
341        if self.eat(Token::Star)? {
342            let w2 = self.eat_witness_or_error()?;
343            Ok(Term::Multiplication(coefficient, w1, w2))
344        } else {
345            Ok(Term::Linear(coefficient, w1))
346        }
347    }
348
349    fn parse_arithmetic_expression(&mut self) -> ParseResult<Expression<FieldElement>> {
350        let terms = self.parse_terms_or_error()?;
351        let expression = build_expression_from_terms(terms.into_iter());
352        Ok(expression)
353    }
354
355    fn parse_blackbox_func_call(&mut self) -> ParseResult<BlackBoxFuncCall<FieldElement>> {
356        self.eat_keyword(Keyword::BlackBoxFuncCall)?;
357        self.eat_or_error(Token::Colon)?;
358        self.eat_or_error(Token::Colon)?;
359
360        // Expect an identifier like "RANGE", "AND", "XOR", etc.
361        let name_ident = self.eat_ident_or_error()?;
362
363        let Some(func_name) = BlackBoxFunc::lookup(&name_ident.to_lowercase()) else {
364            return Err(ParserError::ExpectedBlackBoxFuncName {
365                found: self.token.token().clone(),
366                span: self.token.span(),
367            });
368        };
369
370        let func = match func_name {
371            BlackBoxFunc::AES128Encrypt => {
372                let inputs = self.parse_blackbox_inputs(Keyword::Inputs)?;
373                self.eat_comma_or_error()?;
374                assert!(inputs.len() % 16 == 0, "input length must be a multiple of 16");
375
376                let iv = self.parse_blackbox_inputs_array::<16>(Keyword::Iv)?;
377                self.eat_comma_or_error()?;
378
379                let key = self.parse_blackbox_inputs_array::<16>(Keyword::Key)?;
380                self.eat_comma_or_error()?;
381
382                let outputs = self.parse_blackbox_outputs()?;
383
384                BlackBoxFuncCall::AES128Encrypt { inputs, iv, key, outputs }
385            }
386            BlackBoxFunc::AND => {
387                let lhs = self.parse_blackbox_input(Keyword::Lhs)?;
388                self.eat_comma_or_error()?;
389
390                let rhs = self.parse_blackbox_input(Keyword::Rhs)?;
391                self.eat_comma_or_error()?;
392
393                let output = self.parse_blackbox_output()?;
394                self.eat_comma_or_error()?;
395
396                let num_bits = self.parse_blackbox_u32(Keyword::Bits)?;
397
398                BlackBoxFuncCall::AND { lhs, rhs, num_bits, output }
399            }
400            BlackBoxFunc::XOR => {
401                let lhs = self.parse_blackbox_input(Keyword::Lhs)?;
402                self.eat_comma_or_error()?;
403
404                let rhs = self.parse_blackbox_input(Keyword::Rhs)?;
405                self.eat_comma_or_error()?;
406
407                let output = self.parse_blackbox_output()?;
408                self.eat_comma_or_error()?;
409
410                let num_bits = self.parse_blackbox_u32(Keyword::Bits)?;
411
412                BlackBoxFuncCall::XOR { lhs, rhs, num_bits, output }
413            }
414            BlackBoxFunc::RANGE => {
415                let input = self.parse_blackbox_input(Keyword::Input)?;
416                self.eat_comma_or_error()?;
417
418                let num_bits = self.parse_blackbox_u32(Keyword::Bits)?;
419
420                BlackBoxFuncCall::RANGE { input, num_bits }
421            }
422            BlackBoxFunc::Blake2s => {
423                let inputs = self.parse_blackbox_inputs(Keyword::Inputs)?;
424                self.eat_comma_or_error()?;
425
426                let outputs = self.parse_blackbox_outputs_array::<32>()?;
427
428                BlackBoxFuncCall::Blake2s { inputs, outputs }
429            }
430            BlackBoxFunc::Blake3 => {
431                let inputs = self.parse_blackbox_inputs(Keyword::Inputs)?;
432                self.eat_comma_or_error()?;
433
434                let outputs = self.parse_blackbox_outputs_array::<32>()?;
435
436                BlackBoxFuncCall::Blake3 { inputs, outputs }
437            }
438            BlackBoxFunc::EcdsaSecp256k1 => {
439                let public_key_x = self.parse_blackbox_inputs_array::<32>(Keyword::PublicKeyX)?;
440                self.eat_comma_or_error()?;
441
442                let public_key_y = self.parse_blackbox_inputs_array::<32>(Keyword::PublicKeyY)?;
443                self.eat_comma_or_error()?;
444
445                let signature = self.parse_blackbox_inputs_array::<64>(Keyword::Signature)?;
446                self.eat_comma_or_error()?;
447
448                let hashed_message =
449                    self.parse_blackbox_inputs_array::<32>(Keyword::HashedMessage)?;
450                self.eat_comma_or_error()?;
451
452                let predicate = self.parse_blackbox_input(Keyword::Predicate)?;
453                self.eat_comma_or_error()?;
454
455                let output = self.parse_blackbox_output()?;
456
457                BlackBoxFuncCall::EcdsaSecp256k1 {
458                    public_key_x,
459                    public_key_y,
460                    signature,
461                    hashed_message,
462                    output,
463                    predicate,
464                }
465            }
466            BlackBoxFunc::EcdsaSecp256r1 => {
467                let public_key_x = self.parse_blackbox_inputs_array::<32>(Keyword::PublicKeyX)?;
468                self.eat_comma_or_error()?;
469
470                let public_key_y = self.parse_blackbox_inputs_array::<32>(Keyword::PublicKeyY)?;
471                self.eat_comma_or_error()?;
472
473                let signature = self.parse_blackbox_inputs_array::<64>(Keyword::Signature)?;
474                self.eat_comma_or_error()?;
475
476                let hashed_message =
477                    self.parse_blackbox_inputs_array::<32>(Keyword::HashedMessage)?;
478                self.eat_comma_or_error()?;
479
480                let predicate = self.parse_blackbox_input(Keyword::Predicate)?;
481                self.eat_comma_or_error()?;
482
483                let output = self.parse_blackbox_output()?;
484
485                BlackBoxFuncCall::EcdsaSecp256r1 {
486                    public_key_x,
487                    public_key_y,
488                    signature,
489                    hashed_message,
490                    output,
491                    predicate,
492                }
493            }
494            BlackBoxFunc::MultiScalarMul => {
495                let points = self.parse_blackbox_inputs(Keyword::Points)?;
496                self.eat_comma_or_error()?;
497
498                let scalars = self.parse_blackbox_inputs(Keyword::Scalars)?;
499                self.eat_comma_or_error()?;
500
501                let predicate = self.parse_blackbox_input(Keyword::Predicate)?;
502                self.eat_comma_or_error()?;
503
504                let outputs = self.parse_blackbox_outputs_array::<3>()?;
505                let outputs = (outputs[0], outputs[1], outputs[2]);
506
507                BlackBoxFuncCall::MultiScalarMul { points, scalars, predicate, outputs }
508            }
509            BlackBoxFunc::Keccakf1600 => {
510                let inputs = self.parse_blackbox_inputs_array::<25>(Keyword::Inputs)?;
511                self.eat_comma_or_error()?;
512
513                let outputs = self.parse_blackbox_outputs_array::<25>()?;
514
515                BlackBoxFuncCall::Keccakf1600 { inputs, outputs }
516            }
517            BlackBoxFunc::RecursiveAggregation => {
518                let verification_key = self.parse_blackbox_inputs(Keyword::VerificationKey)?;
519                self.eat_comma_or_error()?;
520
521                let proof = self.parse_blackbox_inputs(Keyword::Proof)?;
522                self.eat_comma_or_error()?;
523
524                let public_inputs = self.parse_blackbox_inputs(Keyword::PublicInputs)?;
525                self.eat_comma_or_error()?;
526
527                let key_hash = self.parse_blackbox_input(Keyword::KeyHash)?;
528                self.eat_comma_or_error()?;
529
530                let proof_type = self.parse_blackbox_u32(Keyword::ProofType)?;
531                self.eat_comma_or_error()?;
532
533                let predicate = self.parse_blackbox_input(Keyword::Predicate)?;
534
535                BlackBoxFuncCall::RecursiveAggregation {
536                    verification_key,
537                    proof,
538                    public_inputs,
539                    key_hash,
540                    proof_type,
541                    predicate,
542                }
543            }
544            BlackBoxFunc::EmbeddedCurveAdd => {
545                let input1 = self.parse_blackbox_inputs_array::<3>(Keyword::Input1)?;
546                self.eat_comma_or_error()?;
547
548                let input2 = self.parse_blackbox_inputs_array::<3>(Keyword::Input2)?;
549                self.eat_comma_or_error()?;
550
551                let predicate = self.parse_blackbox_input(Keyword::Predicate)?;
552                self.eat_comma_or_error()?;
553
554                let outputs = self.parse_blackbox_outputs_array::<3>()?;
555                let outputs = (outputs[0], outputs[1], outputs[2]);
556
557                BlackBoxFuncCall::EmbeddedCurveAdd { input1, input2, predicate, outputs }
558            }
559            BlackBoxFunc::Poseidon2Permutation => {
560                let inputs = self.parse_blackbox_inputs(Keyword::Inputs)?;
561                self.eat_comma_or_error()?;
562
563                let outputs = self.parse_blackbox_outputs()?;
564
565                BlackBoxFuncCall::Poseidon2Permutation { inputs, outputs }
566            }
567            BlackBoxFunc::Sha256Compression => {
568                let inputs = self.parse_blackbox_inputs_array::<16>(Keyword::Inputs)?;
569                self.eat_comma_or_error()?;
570
571                let hash_values = self.parse_blackbox_inputs_array::<8>(Keyword::HashValues)?;
572                self.eat_comma_or_error()?;
573
574                let outputs = self.parse_blackbox_outputs_array::<8>()?;
575
576                BlackBoxFuncCall::Sha256Compression { inputs, hash_values, outputs }
577            }
578        };
579        Ok(func)
580    }
581
582    fn parse_blackbox_inputs_array<const N: usize>(
583        &mut self,
584        keyword: Keyword,
585    ) -> Result<Box<[FunctionInput<FieldElement>; N]>, ParserError> {
586        let inputs = self.parse_blackbox_inputs(keyword)?;
587        self.try_vec_to_array::<N, _>(inputs, keyword)
588    }
589
590    fn parse_blackbox_inputs(
591        &mut self,
592        keyword: Keyword,
593    ) -> ParseResult<Vec<FunctionInput<FieldElement>>> {
594        self.eat_keyword_or_error(keyword)?;
595        self.eat_or_error(Token::Colon)?;
596        self.parse_bracketed_list(|parser| parser.parse_blackbox_input_no_keyword())
597    }
598
599    fn parse_blackbox_input(
600        &mut self,
601        keyword: Keyword,
602    ) -> Result<FunctionInput<FieldElement>, ParserError> {
603        self.eat_keyword_or_error(keyword)?;
604        self.eat_or_error(Token::Colon)?;
605        self.parse_blackbox_input_no_keyword()
606    }
607
608    fn parse_blackbox_input_no_keyword(
609        &mut self,
610    ) -> Result<FunctionInput<FieldElement>, ParserError> {
611        if let Some(value) = self.eat_field_element()? {
612            Ok(FunctionInput::Constant(value))
613        } else if let Some(witness) = self.eat_witness()? {
614            Ok(FunctionInput::Witness(witness))
615        } else {
616            Err(ParserError::ExpectedOneOfTokens {
617                tokens: vec![Token::Int(FieldElement::zero()), Token::Witness(0)],
618                found: self.token.token().clone(),
619                span: self.token.span(),
620            })
621        }
622    }
623
624    fn parse_blackbox_output(&mut self) -> ParseResult<Witness> {
625        self.eat_keyword_or_error(Keyword::Output)?;
626        self.eat_or_error(Token::Colon)?;
627        let witness = self.eat_witness_or_error()?;
628        Ok(witness)
629    }
630
631    fn parse_blackbox_outputs_array<const N: usize>(&mut self) -> ParseResult<Box<[Witness; N]>> {
632        let outputs = self.parse_blackbox_outputs()?;
633        self.try_vec_to_array::<N, _>(outputs, Keyword::Outputs)
634    }
635
636    fn parse_blackbox_outputs(&mut self) -> ParseResult<Vec<Witness>> {
637        self.eat_keyword_or_error(Keyword::Outputs)?;
638        self.eat_or_error(Token::Colon)?;
639        self.parse_witness_vector()
640    }
641
642    fn parse_blackbox_u32(&mut self, keyword: Keyword) -> ParseResult<u32> {
643        self.eat_keyword_or_error(keyword)?;
644        self.eat_or_error(Token::Colon)?;
645        let num_bits = self.eat_u32_or_error()?;
646
647        Ok(num_bits)
648    }
649
650    fn parse_memory_init(&mut self) -> ParseResult<Opcode<FieldElement>> {
651        self.eat_keyword_or_error(Keyword::MemoryInit)?;
652
653        let block_type = self.parse_block_type()?;
654
655        // blockId = [witness1, witness2, ...]
656        let block_id = self.eat_block_id_or_error()?;
657        self.eat_or_error(Token::Equal)?;
658        let init = self.parse_witness_vector()?;
659
660        Ok(Opcode::MemoryInit { block_id, init, block_type })
661    }
662
663    fn parse_block_type(&mut self) -> Result<BlockType, ParserError> {
664        if self.eat_keyword(Keyword::CallData)? {
665            Ok(BlockType::CallData(self.eat_u32_or_error()?))
666        } else if self.eat_keyword(Keyword::ReturnData)? {
667            Ok(BlockType::ReturnData)
668        } else {
669            Ok(BlockType::Memory)
670        }
671    }
672
673    fn parse_memory_read(&mut self) -> ParseResult<Opcode<FieldElement>> {
674        self.eat_keyword_or_error(Keyword::MemoryRead)?;
675
676        // value = blockId[index]
677        let value = self.eat_witness_or_error()?;
678        self.eat_or_error(Token::Equal)?;
679        let block_id = self.eat_block_id_or_error()?;
680        self.eat_or_error(Token::LeftBracket)?;
681        let index = self.eat_witness_or_error()?;
682        self.eat_or_error(Token::RightBracket)?;
683
684        Ok(Opcode::MemoryOp { block_id, op: MemOp::read_at_mem_index(index, value) })
685    }
686
687    fn parse_memory_write(&mut self) -> ParseResult<Opcode<FieldElement>> {
688        self.eat_keyword_or_error(Keyword::MemoryWrite)?;
689
690        // blockId[index] = value
691        let block_id = self.eat_block_id_or_error()?;
692        self.eat_or_error(Token::LeftBracket)?;
693        let index = self.eat_witness_or_error()?;
694        self.eat_or_error(Token::RightBracket)?;
695        self.eat_or_error(Token::Equal)?;
696        let value = self.eat_witness_or_error()?;
697
698        Ok(Opcode::MemoryOp { block_id, op: MemOp::write_to_mem_index(index, value) })
699    }
700
701    fn parse_brillig_call(&mut self) -> ParseResult<Opcode<FieldElement>> {
702        self.eat_keyword_or_error(Keyword::Brillig)?;
703        self.eat_keyword_or_error(Keyword::Call)?;
704        self.eat_keyword_or_error(Keyword::Function)?;
705        self.eat_or_error(Token::Colon)?;
706        let func_id = self.eat_u32_or_error()?;
707        self.eat_or_error(Token::Comma)?;
708
709        let predicate = self.eat_predicate()?;
710
711        // Parse inputs
712        self.eat_keyword_or_error(Keyword::Inputs)?;
713        self.eat_or_error(Token::Colon)?;
714        let inputs = self.parse_brillig_inputs()?;
715
716        self.eat_or_error(Token::Comma)?; // between inputs and outputs
717
718        // Parse outputs
719        self.eat_keyword_or_error(Keyword::Outputs)?;
720        self.eat_or_error(Token::Colon)?;
721        let outputs = self.parse_brillig_outputs()?;
722
723        Ok(Opcode::BrilligCall { id: BrilligFunctionId(func_id), inputs, outputs, predicate })
724    }
725
726    fn parse_brillig_inputs(&mut self) -> ParseResult<Vec<BrilligInputs<FieldElement>>> {
727        self.parse_bracketed_list(|parser| parser.parse_brillig_input())
728    }
729
730    fn parse_brillig_input(&mut self) -> Result<BrilligInputs<FieldElement>, ParserError> {
731        if self.at(Token::LeftBracket) {
732            // It's an array of expressions
733            let exprs = self.parse_bracketed_list(|parser| parser.parse_arithmetic_expression())?;
734            Ok(BrilligInputs::Array(exprs))
735        } else if let Some(block_id) = self.eat_block_id()? {
736            Ok(BrilligInputs::MemoryArray(block_id))
737        } else {
738            let expr = self.parse_arithmetic_expression()?;
739            Ok(BrilligInputs::Single(expr))
740        }
741    }
742
743    fn parse_brillig_outputs(&mut self) -> ParseResult<Vec<BrilligOutputs>> {
744        self.parse_bracketed_list(|parser| parser.parse_brillig_output())
745    }
746
747    fn parse_brillig_output(&mut self) -> Result<BrilligOutputs, ParserError> {
748        if self.at(Token::LeftBracket) {
749            let witnesses = self.parse_witness_vector()?;
750            Ok(BrilligOutputs::Array(witnesses))
751        } else if let Some(witness) = self.eat_witness()? {
752            Ok(BrilligOutputs::Simple(witness))
753        } else {
754            self.expected_one_of_tokens(&[Token::LeftBracket, Token::Witness(0)])
755        }
756    }
757
758    fn parse_call(&mut self) -> ParseResult<Opcode<FieldElement>> {
759        self.eat_keyword_or_error(Keyword::Call)?;
760        self.eat_keyword_or_error(Keyword::Function)?;
761        self.eat_or_error(Token::Colon)?;
762        let id = self.eat_u32_or_error()?;
763        self.eat_or_error(Token::Comma)?;
764        let predicate = self.eat_predicate()?;
765
766        self.eat_keyword_or_error(Keyword::Inputs)?;
767        self.eat_or_error(Token::Colon)?;
768        let inputs = self.parse_witness_vector()?;
769
770        self.eat_or_error(Token::Comma)?;
771        self.eat_keyword_or_error(Keyword::Outputs)?;
772        self.eat_or_error(Token::Colon)?;
773        let outputs = self.parse_witness_vector()?;
774
775        Ok(Opcode::Call { id: AcirFunctionId(id), inputs, outputs, predicate })
776    }
777
778    fn eat_predicate(&mut self) -> ParseResult<Expression<FieldElement>> {
779        self.eat_keyword_or_error(Keyword::Predicate)?;
780        self.eat_or_error(Token::Colon)?;
781        let expr = self.parse_arithmetic_expression()?;
782        self.eat_or_error(Token::Comma)?;
783        Ok(expr)
784    }
785
786    fn parse_bracketed_list<T, F>(&mut self, parser: F) -> ParseResult<Vec<T>>
787    where
788        F: Fn(&mut Parser<'a>) -> ParseResult<T>,
789    {
790        self.eat_or_error(Token::LeftBracket)?;
791
792        let mut values = Vec::new();
793
794        while !self.eat(Token::RightBracket)? {
795            let value = parser(self)?;
796            values.push(value);
797
798            // Eat optional comma
799            if self.eat(Token::Comma)? {
800                continue;
801            }
802
803            // If no comma, expect closing bracket next
804            self.eat_or_error(Token::RightBracket)?;
805            break;
806        }
807
808        Ok(values)
809    }
810
811    fn eat_ident_or_error(&mut self) -> ParseResult<String> {
812        if let Some(identifier) = self.eat_ident()? {
813            Ok(identifier)
814        } else {
815            self.expected_identifier()
816        }
817    }
818
819    fn eat_ident(&mut self) -> ParseResult<Option<String>> {
820        if !matches!(self.token.token(), Token::Ident(..)) {
821            return Ok(None);
822        }
823
824        let token = self.bump()?;
825        match token.into_token() {
826            Token::Ident(ident) => Ok(Some(ident)),
827            _ => unreachable!(),
828        }
829    }
830
831    fn eat_field_element(&mut self) -> ParseResult<Option<FieldElement>> {
832        if let Token::Int(_) = self.token.token() {
833            let token = self.bump()?;
834            if let Token::Int(int) = token.into_token() { Ok(Some(int)) } else { unreachable!() }
835        } else {
836            Ok(None)
837        }
838    }
839
840    fn eat_field_or_error(&mut self) -> ParseResult<FieldElement> {
841        if let Some(int) = self.eat_field_element()? {
842            Ok(int)
843        } else {
844            self.expected_field_element()
845        }
846    }
847
848    fn eat_u32_or_error(&mut self) -> ParseResult<u32> {
849        // u32s will cause issues if we have fields smaller than u32.
850        // For the parser's simplicity we treat all integers as field elements.
851        // It may be worth adding an integer type to the ACIR format as to distinguish between integer types and the native field.
852        let number = self.eat_field_or_error()?;
853        number
854            .try_to_u32()
855            .ok_or(ParserError::IntegerLargerThanU32 { number, span: self.token.span() })
856    }
857
858    fn bump(&mut self) -> ParseResult<SpannedToken> {
859        let token = self.read_token_internal()?;
860        Ok(std::mem::replace(&mut self.token, token))
861    }
862
863    fn read_token_internal(&mut self) -> ParseResult<SpannedToken> {
864        self.lexer.next_token().map_err(ParserError::LexerError)
865    }
866
867    fn eat_keyword(&mut self, keyword: Keyword) -> ParseResult<bool> {
868        if let Token::Keyword(kw) = self.token.token() {
869            if *kw == keyword {
870                self.bump()?;
871                Ok(true)
872            } else {
873                Ok(false)
874            }
875        } else {
876            Ok(false)
877        }
878    }
879
880    fn eat_keyword_or_error(&mut self, keyword: Keyword) -> ParseResult<()> {
881        if !self.eat_keyword(keyword)? {
882            return self.expected_token(Token::Keyword(keyword));
883        }
884        Ok(())
885    }
886
887    fn peek_keyword(&self) -> Option<Keyword> {
888        match self.token.token() {
889            Token::Keyword(kw) => Some(*kw),
890            _ => None,
891        }
892    }
893
894    fn eat_witness(&mut self) -> ParseResult<Option<Witness>> {
895        let is_witness_type = matches!(self.token.token(), Token::Witness(_));
896        if is_witness_type {
897            let token = self.bump()?;
898            match token.into_token() {
899                Token::Witness(witness) => {
900                    if witness > self.max_witness_index {
901                        self.max_witness_index = witness;
902                    }
903                    Ok(Some(Witness(witness)))
904                }
905                _ => unreachable!(),
906            }
907        } else {
908            Ok(None)
909        }
910    }
911
912    fn eat_witness_or_error(&mut self) -> ParseResult<Witness> {
913        if let Some(int) = self.eat_witness()? { Ok(int) } else { self.expected_witness() }
914    }
915
916    fn eat_block_id(&mut self) -> ParseResult<Option<BlockId>> {
917        let is_block_type = matches!(self.token.token(), Token::Block(_));
918        if is_block_type {
919            let token = self.bump()?;
920            match token.into_token() {
921                Token::Block(block) => Ok(Some(BlockId(block))),
922                _ => unreachable!(),
923            }
924        } else {
925            Ok(None)
926        }
927    }
928
929    fn eat_block_id_or_error(&mut self) -> ParseResult<BlockId> {
930        if let Some(int) = self.eat_block_id()? { Ok(int) } else { self.expected_block_id() }
931    }
932
933    fn eat_comma_or_error(&mut self) -> ParseResult<()> {
934        self.eat_or_error(Token::Comma)
935    }
936
937    fn eat_or_error(&mut self, token: Token) -> ParseResult<()> {
938        if self.eat(token.clone())? { Ok(()) } else { self.expected_token(token) }
939    }
940
941    fn at(&self, token: Token) -> bool {
942        self.token.token() == &token
943    }
944
945    /// Returns true if the token is eaten and bumps to the next token.
946    /// Otherwise will return false and no bump will occur.
947    fn eat(&mut self, token: Token) -> ParseResult<bool> {
948        if self.token.token() == &token {
949            self.bump()?;
950            Ok(true)
951        } else {
952            Ok(false)
953        }
954    }
955
956    fn try_vec_to_array<const N: usize, T: Clone>(
957        &self,
958        vec: Vec<T>,
959        keyword: Keyword,
960    ) -> Result<Box<[T; N]>, ParserError> {
961        let len = vec.len();
962        vec.try_into().map_err(|_| ParserError::IncorrectValuesLength {
963            expected: N,
964            found: len,
965            name: keyword.to_string(),
966            span: self.token.span(),
967        })
968    }
969
970    fn expected_identifier<T>(&self) -> ParseResult<T> {
971        Err(ParserError::ExpectedIdentifier {
972            found: self.token.token().clone(),
973            span: self.token.span(),
974        })
975    }
976
977    fn expected_field_element<T>(&self) -> ParseResult<T> {
978        Err(ParserError::ExpectedFieldElement {
979            found: self.token.token().clone(),
980            span: self.token.span(),
981        })
982    }
983
984    fn expected_witness<T>(&self) -> ParseResult<T> {
985        Err(ParserError::ExpectedWitness {
986            found: self.token.token().clone(),
987            span: self.token.span(),
988        })
989    }
990
991    fn expected_block_id<T>(&self) -> ParseResult<T> {
992        Err(ParserError::ExpectedBlockId {
993            found: self.token.token().clone(),
994            span: self.token.span(),
995        })
996    }
997
998    fn expected_term<T>(&self) -> ParseResult<T> {
999        Err(ParserError::ExpectedTerm {
1000            found: self.token.token().clone(),
1001            span: self.token.span(),
1002        })
1003    }
1004
1005    fn expected_token<T>(&self, token: Token) -> ParseResult<T> {
1006        Err(ParserError::ExpectedToken {
1007            token,
1008            found: self.token.token().clone(),
1009            span: self.token.span(),
1010        })
1011    }
1012
1013    fn expected_one_of_tokens<T>(&self, tokens: &[Token]) -> ParseResult<T> {
1014        Err(ParserError::ExpectedOneOfTokens {
1015            tokens: tokens.to_vec(),
1016            found: self.token.token().clone(),
1017            span: self.token.span(),
1018        })
1019    }
1020}
1021
1022fn build_expression_from_terms(terms: impl Iterator<Item = Term>) -> Expression<FieldElement> {
1023    // Gather all terms, summing the constants
1024    let mut q_c = FieldElement::zero();
1025    let mut linear_combinations = Vec::new();
1026    let mut mul_terms = Vec::new();
1027
1028    for term in terms {
1029        match term {
1030            Term::Constant(c) => q_c += c,
1031            Term::Linear(c, w) => linear_combinations.push((c, w)),
1032            Term::Multiplication(c, w1, w2) => mul_terms.push((c, w1, w2)),
1033        }
1034    }
1035
1036    Expression { mul_terms, linear_combinations, q_c }
1037}
1038
1039fn is_zero_term(terms: &[Term]) -> bool {
1040    terms.len() == 1 && matches!(terms[0], Term::Constant(c) if c.is_zero())
1041}
1042
1043fn eof_spanned_token() -> SpannedToken {
1044    SpannedToken::new(Token::Eof, Default::default())
1045}
1046
1047#[derive(Debug, Clone, Copy)]
1048enum Term {
1049    Constant(FieldElement),
1050    Linear(FieldElement, Witness),
1051    Multiplication(FieldElement, Witness, Witness),
1052}
1053
1054impl Term {
1055    fn negate(self) -> Self {
1056        match self {
1057            Term::Constant(c) => Term::Constant(-c),
1058            Term::Linear(c, w) => Term::Linear(-c, w),
1059            Term::Multiplication(c, w1, w2) => Term::Multiplication(-c, w1, w2),
1060        }
1061    }
1062}
1063
1064type ParseResult<T> = Result<T, ParserError>;
1065
1066#[derive(Debug, Error)]
1067pub(crate) enum ParserError {
1068    #[error("{0}")]
1069    LexerError(LexerError),
1070    #[error("Expected '{token}', found '{found}'")]
1071    ExpectedToken { token: Token, found: Token, span: Span },
1072    #[error("Expected one of {tokens:?}, found {found}")]
1073    ExpectedOneOfTokens { tokens: Vec<Token>, found: Token, span: Span },
1074    #[error("Expected an identifier, found '{found}'")]
1075    ExpectedIdentifier { found: Token, span: Span },
1076    #[error("Expected a field element, found '{found}'")]
1077    ExpectedFieldElement { found: Token, span: Span },
1078    #[error("Expected a witness index, found '{found}'")]
1079    ExpectedWitness { found: Token, span: Span },
1080    #[error("Expected a block ID, found '{found}'")]
1081    ExpectedBlockId { found: Token, span: Span },
1082    #[error("Expected a term, found '{found}'")]
1083    ExpectedTerm { found: Token, span: Span },
1084    #[error("Expected valid black box function name, found '{found}'")]
1085    ExpectedBlackBoxFuncName { found: Token, span: Span },
1086    #[error("Number does not fit in u32, got: '{number}'")]
1087    IntegerLargerThanU32 { number: FieldElement, span: Span },
1088    #[error("Expected {expected} values for {name}, found {found}")]
1089    IncorrectValuesLength { expected: usize, found: usize, name: String, span: Span },
1090    #[error("Expected function id {expected}, found {found}")]
1091    UnexpectedFunctionId { expected: u32, found: u32, span: Span },
1092}
1093
1094impl ParserError {
1095    fn span(&self) -> Span {
1096        use ParserError::*;
1097        match self {
1098            LexerError(e) => e.span(),
1099            ExpectedToken { span, .. }
1100            | ExpectedOneOfTokens { span, .. }
1101            | ExpectedIdentifier { span, .. }
1102            | ExpectedFieldElement { span, .. }
1103            | ExpectedWitness { span, .. }
1104            | ExpectedBlockId { span, .. }
1105            | ExpectedTerm { span, .. }
1106            | ExpectedBlackBoxFuncName { span, .. }
1107            | IntegerLargerThanU32 { span, .. }
1108            | IncorrectValuesLength { span, .. }
1109            | UnexpectedFunctionId { span, .. } => *span,
1110        }
1111    }
1112}
acir/parser/mod.rs

acir/parser/
mod.rs
