acir/parser/
mod.rs

1use std::{collections::BTreeSet, str::FromStr};
2
3use acir_field::{AcirField, FieldElement};
4
5use lexer::{Lexer, LexerError};
6use noirc_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;
21#[cfg(test)]
22mod tests;
23mod token;
24
25pub struct AcirParserErrorWithSource {
26    src: String,
27    error: ParserError,
28}
29
30impl AcirParserErrorWithSource {
31    fn parse_error(error: ParserError, src: &str) -> Self {
32        Self { src: src.to_string(), error }
33    }
34
35    #[cfg(test)]
36    pub(super) fn get_error(self) -> ParserError {
37        self.error
38    }
39}
40
41impl std::fmt::Debug for AcirParserErrorWithSource {
42    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
43        let span = self.error.span();
44
45        let mut byte: usize = 0;
46        for line in self.src.lines() {
47            let has_error =
48                byte <= span.start() as usize && span.end() as usize <= byte + line.len();
49            if has_error {
50                writeln!(f)?;
51            }
52
53            writeln!(f, "{line}")?;
54
55            if has_error {
56                let offset = span.start() as usize - byte;
57                write!(f, "{}", " ".repeat(offset))?;
58                writeln!(f, "{}", "^".repeat((span.end() - span.start()) as usize))?;
59                write!(f, "{}", " ".repeat(offset))?;
60                writeln!(f, "{}", self.error)?;
61                writeln!(f)?;
62            }
63
64            byte += line.len() + 1; // "+ 1" for the newline
65        }
66        Ok(())
67    }
68}
69
70impl FromStr for Program<FieldElement> {
71    type Err = AcirParserErrorWithSource;
72
73    fn from_str(src: &str) -> Result<Self, Self::Err> {
74        Self::from_str_impl(src)
75    }
76}
77
78impl Program<FieldElement> {
79    /// Creates a [Program] object from the given string.
80    #[allow(clippy::should_implement_trait)]
81    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
82        FromStr::from_str(src)
83    }
84
85    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
86        let mut parser =
87            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
88        parser.parse_program().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
89    }
90}
91
92impl FromStr for Circuit<FieldElement> {
93    type Err = AcirParserErrorWithSource;
94
95    fn from_str(src: &str) -> Result<Self, Self::Err> {
96        Self::from_str_impl(src)
97    }
98}
99
100impl Circuit<FieldElement> {
101    /// Creates a [Circuit] object from the given string.
102    #[allow(clippy::should_implement_trait)]
103    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
104        FromStr::from_str(src)
105    }
106
107    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
108        let mut parser =
109            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
110        parser.parse_circuit().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
111    }
112}
113
114impl FromStr for Expression<FieldElement> {
115    type Err = AcirParserErrorWithSource;
116
117    fn from_str(src: &str) -> Result<Self, Self::Err> {
118        Self::from_str_impl(src)
119    }
120}
121
122impl Expression<FieldElement> {
123    /// Creates a [Expression] object from the given string.
124    #[allow(clippy::should_implement_trait)]
125    pub fn from_str(src: &str) -> Result<Self, AcirParserErrorWithSource> {
126        FromStr::from_str(src)
127    }
128
129    pub fn from_str_impl(src: &str) -> Result<Self, AcirParserErrorWithSource> {
130        let mut parser =
131            Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
132        parser
133            .parse_arithmetic_expression()
134            .map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
135    }
136}
137
138pub fn parse_opcodes(src: &str) -> Result<Vec<Opcode<FieldElement>>, AcirParserErrorWithSource> {
139    let mut parser =
140        Parser::new(src).map_err(|err| AcirParserErrorWithSource::parse_error(err, src))?;
141    parser.parse_opcodes().map_err(|err| AcirParserErrorWithSource::parse_error(err, src))
142}
143
144struct Parser<'a> {
145    lexer: Lexer<'a>,
146    token: SpannedToken,
147    max_witness_index: u32,
148}
149
150impl<'a> Parser<'a> {
151    fn new(source: &'a str) -> ParseResult<Self> {
152        let lexer = Lexer::new(source);
153        let mut parser = Self { lexer, token: eof_spanned_token(), max_witness_index: 0 };
154        parser.token = parser.read_token_internal()?;
155        Ok(parser)
156    }
157
158    /// Parse multiple [Circuit] blocks and return a [Program].
159    fn parse_program(&mut self) -> ParseResult<Program<FieldElement>> {
160        let mut functions: Vec<Circuit<FieldElement>> = Vec::new();
161
162        // We expect top-level "func" keywords for each circuit
163        while self.eat_keyword(Keyword::Function)? {
164            let func_id = self.eat_u32_or_error()?;
165            let expected_id = functions.len() as u32;
166            if func_id != expected_id {
167                return Err(ParserError::UnexpectedFunctionId {
168                    expected: expected_id,
169                    found: func_id,
170                    span: self.token.span(),
171                });
172            }
173
174            let circuit = self.parse_circuit()?;
175
176            functions.push(circuit);
177        }
178
179        // We don't support parsing unconstrained Brillig bytecode blocks
180        let unconstrained_functions = Vec::new();
181        Ok(Program { functions, unconstrained_functions })
182    }
183
184    pub(crate) fn parse_circuit(&mut self) -> ParseResult<Circuit<FieldElement>> {
185        self.max_witness_index = 0;
186
187        let private_parameters = self.parse_private_parameters()?;
188        let public_parameters = PublicInputs(self.parse_public_parameters()?);
189        let return_values = PublicInputs(self.parse_return_values()?);
190
191        let opcodes = self.parse_opcodes()?;
192
193        Ok(Circuit {
194            current_witness_index: self.max_witness_index,
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.parse_arithmetic_expression()?;
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.parse_arithmetic_expression()?;
682        self.eat_or_error(Token::RightBracket)?;
683
684        let operation = Expression::zero();
685
686        Ok(Opcode::MemoryOp { block_id, op: MemOp { index, value, operation } })
687    }
688
689    fn parse_memory_write(&mut self) -> ParseResult<Opcode<FieldElement>> {
690        self.eat_keyword_or_error(Keyword::MemoryWrite)?;
691
692        // blockId[index] = value
693        let block_id = self.eat_block_id_or_error()?;
694        self.eat_or_error(Token::LeftBracket)?;
695        let index = self.parse_arithmetic_expression()?;
696        self.eat_or_error(Token::RightBracket)?;
697        self.eat_or_error(Token::Equal)?;
698        let value = self.parse_arithmetic_expression()?;
699
700        let operation = Expression::one();
701
702        Ok(Opcode::MemoryOp { block_id, op: MemOp { index, value, operation } })
703    }
704
705    fn parse_brillig_call(&mut self) -> ParseResult<Opcode<FieldElement>> {
706        self.eat_keyword_or_error(Keyword::Brillig)?;
707        self.eat_keyword_or_error(Keyword::Call)?;
708        self.eat_keyword_or_error(Keyword::Function)?;
709        self.eat_or_error(Token::Colon)?;
710        let func_id = self.eat_u32_or_error()?;
711        self.eat_or_error(Token::Comma)?;
712
713        let predicate = self.eat_predicate()?;
714
715        // Parse inputs
716        self.eat_keyword_or_error(Keyword::Inputs)?;
717        self.eat_or_error(Token::Colon)?;
718        let inputs = self.parse_brillig_inputs()?;
719
720        self.eat_or_error(Token::Comma)?; // between inputs and outputs
721
722        // Parse outputs
723        self.eat_keyword_or_error(Keyword::Outputs)?;
724        self.eat_or_error(Token::Colon)?;
725        let outputs = self.parse_brillig_outputs()?;
726
727        Ok(Opcode::BrilligCall { id: BrilligFunctionId(func_id), inputs, outputs, predicate })
728    }
729
730    fn parse_brillig_inputs(&mut self) -> ParseResult<Vec<BrilligInputs<FieldElement>>> {
731        self.parse_bracketed_list(|parser| parser.parse_brillig_input())
732    }
733
734    fn parse_brillig_input(&mut self) -> Result<BrilligInputs<FieldElement>, ParserError> {
735        if self.at(Token::LeftBracket) {
736            // It's an array of expressions
737            let exprs = self.parse_bracketed_list(|parser| parser.parse_arithmetic_expression())?;
738            Ok(BrilligInputs::Array(exprs))
739        } else if let Some(block_id) = self.eat_block_id()? {
740            Ok(BrilligInputs::MemoryArray(block_id))
741        } else {
742            let expr = self.parse_arithmetic_expression()?;
743            Ok(BrilligInputs::Single(expr))
744        }
745    }
746
747    fn parse_brillig_outputs(&mut self) -> ParseResult<Vec<BrilligOutputs>> {
748        self.parse_bracketed_list(|parser| parser.parse_brillig_output())
749    }
750
751    fn parse_brillig_output(&mut self) -> Result<BrilligOutputs, ParserError> {
752        if self.at(Token::LeftBracket) {
753            let witnesses = self.parse_witness_vector()?;
754            Ok(BrilligOutputs::Array(witnesses))
755        } else if let Some(witness) = self.eat_witness()? {
756            Ok(BrilligOutputs::Simple(witness))
757        } else {
758            self.expected_one_of_tokens(&[Token::LeftBracket, Token::Witness(0)])
759        }
760    }
761
762    fn parse_call(&mut self) -> ParseResult<Opcode<FieldElement>> {
763        self.eat_keyword_or_error(Keyword::Call)?;
764        self.eat_keyword_or_error(Keyword::Function)?;
765        self.eat_or_error(Token::Colon)?;
766        let id = self.eat_u32_or_error()?;
767        self.eat_or_error(Token::Comma)?;
768        let predicate = self.eat_predicate()?;
769
770        self.eat_keyword_or_error(Keyword::Inputs)?;
771        self.eat_or_error(Token::Colon)?;
772        let inputs = self.parse_witness_vector()?;
773
774        self.eat_or_error(Token::Comma)?;
775        self.eat_keyword_or_error(Keyword::Outputs)?;
776        self.eat_or_error(Token::Colon)?;
777        let outputs = self.parse_witness_vector()?;
778
779        Ok(Opcode::Call { id: AcirFunctionId(id), inputs, outputs, predicate })
780    }
781
782    fn eat_predicate(&mut self) -> ParseResult<Expression<FieldElement>> {
783        self.eat_keyword_or_error(Keyword::Predicate)?;
784        self.eat_or_error(Token::Colon)?;
785        let expr = self.parse_arithmetic_expression()?;
786        self.eat_or_error(Token::Comma)?;
787        Ok(expr)
788    }
789
790    fn parse_bracketed_list<T, F>(&mut self, parser: F) -> ParseResult<Vec<T>>
791    where
792        F: Fn(&mut Parser<'a>) -> ParseResult<T>,
793    {
794        self.eat_or_error(Token::LeftBracket)?;
795
796        let mut values = Vec::new();
797
798        while !self.eat(Token::RightBracket)? {
799            let value = parser(self)?;
800            values.push(value);
801
802            // Eat optional comma
803            if self.eat(Token::Comma)? {
804                continue;
805            }
806
807            // If no comma, expect closing bracket next
808            self.eat_or_error(Token::RightBracket)?;
809            break;
810        }
811
812        Ok(values)
813    }
814
815    fn eat_ident_or_error(&mut self) -> ParseResult<String> {
816        if let Some(identifier) = self.eat_ident()? {
817            Ok(identifier)
818        } else {
819            self.expected_identifier()
820        }
821    }
822
823    fn eat_ident(&mut self) -> ParseResult<Option<String>> {
824        if !matches!(self.token.token(), Token::Ident(..)) {
825            return Ok(None);
826        }
827
828        let token = self.bump()?;
829        match token.into_token() {
830            Token::Ident(ident) => Ok(Some(ident)),
831            _ => unreachable!(),
832        }
833    }
834
835    fn eat_field_element(&mut self) -> ParseResult<Option<FieldElement>> {
836        if let Token::Int(_) = self.token.token() {
837            let token = self.bump()?;
838            if let Token::Int(int) = token.into_token() { Ok(Some(int)) } else { unreachable!() }
839        } else {
840            Ok(None)
841        }
842    }
843
844    fn eat_field_or_error(&mut self) -> ParseResult<FieldElement> {
845        if let Some(int) = self.eat_field_element()? {
846            Ok(int)
847        } else {
848            self.expected_field_element()
849        }
850    }
851
852    fn eat_u32_or_error(&mut self) -> ParseResult<u32> {
853        // u32s will cause issues if we have fields smaller than u32.
854        // For the parser's simplicity we treat all integers as field elements.
855        // It may be worth adding an integer type to the ACIR format as to distinguish between integer types and the native field.
856        let number = self.eat_field_or_error()?;
857        number
858            .try_to_u32()
859            .ok_or(ParserError::IntegerLargerThanU32 { number, span: self.token.span() })
860    }
861
862    fn bump(&mut self) -> ParseResult<SpannedToken> {
863        let token = self.read_token_internal()?;
864        Ok(std::mem::replace(&mut self.token, token))
865    }
866
867    fn read_token_internal(&mut self) -> ParseResult<SpannedToken> {
868        self.lexer.next_token().map_err(ParserError::LexerError)
869    }
870
871    fn eat_keyword(&mut self, keyword: Keyword) -> ParseResult<bool> {
872        if let Token::Keyword(kw) = self.token.token() {
873            if *kw == keyword {
874                self.bump()?;
875                Ok(true)
876            } else {
877                Ok(false)
878            }
879        } else {
880            Ok(false)
881        }
882    }
883
884    fn eat_keyword_or_error(&mut self, keyword: Keyword) -> ParseResult<()> {
885        if !self.eat_keyword(keyword)? {
886            return self.expected_token(Token::Keyword(keyword));
887        }
888        Ok(())
889    }
890
891    fn peek_keyword(&self) -> Option<Keyword> {
892        match self.token.token() {
893            Token::Keyword(kw) => Some(*kw),
894            _ => None,
895        }
896    }
897
898    fn eat_witness(&mut self) -> ParseResult<Option<Witness>> {
899        let is_witness_type = matches!(self.token.token(), Token::Witness(_));
900        if is_witness_type {
901            let token = self.bump()?;
902            match token.into_token() {
903                Token::Witness(witness) => {
904                    if witness > self.max_witness_index {
905                        self.max_witness_index = witness;
906                    }
907                    Ok(Some(Witness(witness)))
908                }
909                _ => unreachable!(),
910            }
911        } else {
912            Ok(None)
913        }
914    }
915
916    fn eat_witness_or_error(&mut self) -> ParseResult<Witness> {
917        if let Some(int) = self.eat_witness()? { Ok(int) } else { self.expected_witness() }
918    }
919
920    fn eat_block_id(&mut self) -> ParseResult<Option<BlockId>> {
921        let is_block_type = matches!(self.token.token(), Token::Block(_));
922        if is_block_type {
923            let token = self.bump()?;
924            match token.into_token() {
925                Token::Block(block) => Ok(Some(BlockId(block))),
926                _ => unreachable!(),
927            }
928        } else {
929            Ok(None)
930        }
931    }
932
933    fn eat_block_id_or_error(&mut self) -> ParseResult<BlockId> {
934        if let Some(int) = self.eat_block_id()? { Ok(int) } else { self.expected_block_id() }
935    }
936
937    fn eat_comma_or_error(&mut self) -> ParseResult<()> {
938        self.eat_or_error(Token::Comma)
939    }
940
941    fn eat_or_error(&mut self, token: Token) -> ParseResult<()> {
942        if self.eat(token.clone())? { Ok(()) } else { self.expected_token(token) }
943    }
944
945    fn at(&self, token: Token) -> bool {
946        self.token.token() == &token
947    }
948
949    /// Returns true if the token is eaten and bumps to the next token.
950    /// Otherwise will return false and no bump will occur.
951    fn eat(&mut self, token: Token) -> ParseResult<bool> {
952        if self.token.token() == &token {
953            self.bump()?;
954            Ok(true)
955        } else {
956            Ok(false)
957        }
958    }
959
960    fn try_vec_to_array<const N: usize, T: Clone>(
961        &self,
962        vec: Vec<T>,
963        keyword: Keyword,
964    ) -> Result<Box<[T; N]>, ParserError> {
965        let len = vec.len();
966        vec.try_into().map_err(|_| ParserError::IncorrectValuesLength {
967            expected: N,
968            found: len,
969            name: keyword.to_string(),
970            span: self.token.span(),
971        })
972    }
973
974    fn expected_identifier<T>(&self) -> ParseResult<T> {
975        Err(ParserError::ExpectedIdentifier {
976            found: self.token.token().clone(),
977            span: self.token.span(),
978        })
979    }
980
981    fn expected_field_element<T>(&self) -> ParseResult<T> {
982        Err(ParserError::ExpectedFieldElement {
983            found: self.token.token().clone(),
984            span: self.token.span(),
985        })
986    }
987
988    fn expected_witness<T>(&self) -> ParseResult<T> {
989        Err(ParserError::ExpectedWitness {
990            found: self.token.token().clone(),
991            span: self.token.span(),
992        })
993    }
994
995    fn expected_block_id<T>(&self) -> ParseResult<T> {
996        Err(ParserError::ExpectedBlockId {
997            found: self.token.token().clone(),
998            span: self.token.span(),
999        })
1000    }
1001
1002    fn expected_term<T>(&self) -> ParseResult<T> {
1003        Err(ParserError::ExpectedTerm {
1004            found: self.token.token().clone(),
1005            span: self.token.span(),
1006        })
1007    }
1008
1009    fn expected_token<T>(&self, token: Token) -> ParseResult<T> {
1010        Err(ParserError::ExpectedToken {
1011            token,
1012            found: self.token.token().clone(),
1013            span: self.token.span(),
1014        })
1015    }
1016
1017    fn expected_one_of_tokens<T>(&self, tokens: &[Token]) -> ParseResult<T> {
1018        Err(ParserError::ExpectedOneOfTokens {
1019            tokens: tokens.to_vec(),
1020            found: self.token.token().clone(),
1021            span: self.token.span(),
1022        })
1023    }
1024}
1025
1026fn build_expression_from_terms(terms: impl Iterator<Item = Term>) -> Expression<FieldElement> {
1027    // Gather all terms, summing the constants
1028    let mut q_c = FieldElement::zero();
1029    let mut linear_combinations = Vec::new();
1030    let mut mul_terms = Vec::new();
1031
1032    for term in terms {
1033        match term {
1034            Term::Constant(c) => q_c += c,
1035            Term::Linear(c, w) => linear_combinations.push((c, w)),
1036            Term::Multiplication(c, w1, w2) => mul_terms.push((c, w1, w2)),
1037        }
1038    }
1039
1040    Expression { mul_terms, linear_combinations, q_c }
1041}
1042
1043fn is_zero_term(terms: &[Term]) -> bool {
1044    terms.len() == 1 && matches!(terms[0], Term::Constant(c) if c.is_zero())
1045}
1046
1047fn eof_spanned_token() -> SpannedToken {
1048    SpannedToken::new(Token::Eof, Default::default())
1049}
1050
1051#[derive(Debug, Clone, Copy)]
1052enum Term {
1053    Constant(FieldElement),
1054    Linear(FieldElement, Witness),
1055    Multiplication(FieldElement, Witness, Witness),
1056}
1057
1058impl Term {
1059    fn negate(self) -> Self {
1060        match self {
1061            Term::Constant(c) => Term::Constant(-c),
1062            Term::Linear(c, w) => Term::Linear(-c, w),
1063            Term::Multiplication(c, w1, w2) => Term::Multiplication(-c, w1, w2),
1064        }
1065    }
1066}
1067
1068type ParseResult<T> = Result<T, ParserError>;
1069
1070#[derive(Debug, Error)]
1071pub(crate) enum ParserError {
1072    #[error("{0}")]
1073    LexerError(LexerError),
1074    #[error("Expected '{token}', found '{found}'")]
1075    ExpectedToken { token: Token, found: Token, span: Span },
1076    #[error("Expected one of {tokens:?}, found {found}")]
1077    ExpectedOneOfTokens { tokens: Vec<Token>, found: Token, span: Span },
1078    #[error("Expected an identifier, found '{found}'")]
1079    ExpectedIdentifier { found: Token, span: Span },
1080    #[error("Expected a field element, found '{found}'")]
1081    ExpectedFieldElement { found: Token, span: Span },
1082    #[error("Expected a witness index, found '{found}'")]
1083    ExpectedWitness { found: Token, span: Span },
1084    #[error("Expected a block ID, found '{found}'")]
1085    ExpectedBlockId { found: Token, span: Span },
1086    #[error("Expected a term, found '{found}'")]
1087    ExpectedTerm { found: Token, span: Span },
1088    #[error("Expected valid black box function name, found '{found}'")]
1089    ExpectedBlackBoxFuncName { found: Token, span: Span },
1090    #[error("Number does not fit in u32, got: '{number}'")]
1091    IntegerLargerThanU32 { number: FieldElement, span: Span },
1092    #[error("Expected {expected} values for {name}, found {found}")]
1093    IncorrectValuesLength { expected: usize, found: usize, name: String, span: Span },
1094    #[error("Expected function id {expected}, found {found}")]
1095    UnexpectedFunctionId { expected: u32, found: u32, span: Span },
1096}
1097
1098impl ParserError {
1099    fn span(&self) -> Span {
1100        use ParserError::*;
1101        match self {
1102            LexerError(e) => e.span(),
1103            ExpectedToken { span, .. }
1104            | ExpectedOneOfTokens { span, .. }
1105            | ExpectedIdentifier { span, .. }
1106            | ExpectedFieldElement { span, .. }
1107            | ExpectedWitness { span, .. }
1108            | ExpectedBlockId { span, .. }
1109            | ExpectedTerm { span, .. }
1110            | ExpectedBlackBoxFuncName { span, .. }
1111            | IntegerLargerThanU32 { span, .. }
1112            | IncorrectValuesLength { span, .. }
1113            | UnexpectedFunctionId { span, .. } => *span,
1114        }
1115    }
1116}
acir/parser/mod.rs

acir/parser/
mod.rs
