GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
fe3c4e8d81f2d65699cc8d776a55aed5a145e264

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_eval/src

compiler/qsc_eval/src/lib.rs

2062lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#![warn(clippy::mod_module_files, clippy::pedantic, clippy::unwrap_used)]
5#![allow(clippy::missing_errors_doc, clippy::missing_panics_doc)]
6
7#[cfg(test)]
8mod tests;
9
10pub mod backend;
11pub mod debug;
12mod error;
13mod intrinsic;
14pub mod lower;
15pub mod output;
16pub mod val;
17
18use crate::val::{FunctorApp, Value};
19use backend::Backend;
20use debug::{map_fir_package_to_hir, CallStack, Frame};
21use error::PackageSpan;
22use miette::Diagnostic;
23use num_bigint::BigInt;
24use output::Receiver;
25use qsc_data_structures::span::Span;
26use qsc_fir::fir::{
27 self, BinOp, BlockId, CallableImpl, ExprId, ExprKind, Field, Functor, Global, Lit, LocalItemId,
28 Mutability, NodeId, PackageId, PackageStoreLookup, PatId, PatKind, PrimField, Res, StmtId,
29 StmtKind, StoreItemId, StringComponent, UnOp,
30};
31use qsc_fir::ty::Ty;
32use rand::{rngs::StdRng, SeedableRng};
33use rustc_hash::FxHashMap;
34use std::{
35 cell::RefCell,
36 collections::hash_map::Entry,
37 fmt::{self, Display, Formatter, Write},
38 iter,
39 ops::Neg,
40 rc::Rc,
41};
42use thiserror::Error;
43
44#[derive(Clone, Debug, Diagnostic, Error)]
45pub enum Error {
46 #[error("array too large")]
47 #[diagnostic(code("Qsc.Eval.ArrayTooLarge"))]
48 ArrayTooLarge(#[label("this array has too many items")] PackageSpan),
49
50 #[error("invalid array length: {0}")]
51 #[diagnostic(code("Qsc.Eval.InvalidArrayLength"))]
52 InvalidArrayLength(i64, #[label("cannot be used as a length")] PackageSpan),
53
54 #[error("division by zero")]
55 #[diagnostic(code("Qsc.Eval.DivZero"))]
56 DivZero(#[label("cannot divide by zero")] PackageSpan),
57
58 #[error("empty range")]
59 #[diagnostic(code("Qsc.Eval.EmptyRange"))]
60 EmptyRange(#[label("the range cannot be empty")] PackageSpan),
61
62 #[error("value cannot be used as an index: {0}")]
63 #[diagnostic(code("Qsc.Eval.InvalidIndex"))]
64 InvalidIndex(i64, #[label("invalid index")] PackageSpan),
65
66 #[error("integer too large for operation")]
67 #[diagnostic(code("Qsc.Eval.IntTooLarge"))]
68 IntTooLarge(i64, #[label("this value is too large")] PackageSpan),
69
70 #[error("missing specialization: {0}")]
71 #[diagnostic(code("Qsc.Eval.MissingSpec"))]
72 MissingSpec(
73 String,
74 #[label("callable has no {0} specialization")] PackageSpan,
75 ),
76
77 #[error("index out of range: {0}")]
78 #[diagnostic(code("Qsc.Eval.IndexOutOfRange"))]
79 IndexOutOfRange(i64, #[label("out of range")] PackageSpan),
80
81 #[error("intrinsic callable `{0}` failed: {1}")]
82 #[diagnostic(code("Qsc.Eval.IntrinsicFail"))]
83 IntrinsicFail(String, String, #[label] PackageSpan),
84
85 #[error("invalid rotation angle: {0}")]
86 #[diagnostic(code("Qsc.Eval.InvalidRotationAngle"))]
87 InvalidRotationAngle(f64, #[label("invalid rotation angle")] PackageSpan),
88
89 #[error("negative integers cannot be used here: {0}")]
90 #[diagnostic(code("Qsc.Eval.InvalidNegativeInt"))]
91 InvalidNegativeInt(i64, #[label("invalid negative integer")] PackageSpan),
92
93 #[error("output failure")]
94 #[diagnostic(code("Qsc.Eval.OutputFail"))]
95 OutputFail(#[label("failed to generate output")] PackageSpan),
96
97 #[error("qubits in gate invocation are not unique")]
98 #[diagnostic(code("Qsc.Eval.QubitUniqueness"))]
99 QubitUniqueness(#[label] PackageSpan),
100
101 #[error("range with step size of zero")]
102 #[diagnostic(code("Qsc.Eval.RangeStepZero"))]
103 RangeStepZero(#[label("invalid range")] PackageSpan),
104
105 #[error("Qubit{0} released while not in |0⟩ state")]
106 #[diagnostic(help("qubits should be returned to the |0⟩ state before being released to satisfy the assumption that allocated qubits start in the |0⟩ state"))]
107 #[diagnostic(code("Qsc.Eval.ReleasedQubitNotZero"))]
108 ReleasedQubitNotZero(usize, #[label("Qubit{0}")] PackageSpan),
109
110 #[error("name is not bound")]
111 #[diagnostic(code("Qsc.Eval.UnboundName"))]
112 UnboundName(#[label] PackageSpan),
113
114 #[error("unknown intrinsic `{0}`")]
115 #[diagnostic(code("Qsc.Eval.UnknownIntrinsic"))]
116 UnknownIntrinsic(
117 String,
118 #[label("callable has no implementation")] PackageSpan,
119 ),
120
121 #[error("program failed: {0}")]
122 #[diagnostic(code("Qsc.Eval.UserFail"))]
123 UserFail(String, #[label("explicit fail")] PackageSpan),
124}
125
126impl Error {
127 #[must_use]
128 pub fn span(&self) -> &PackageSpan {
129 match self {
130 Error::ArrayTooLarge(span)
131 | Error::DivZero(span)
132 | Error::EmptyRange(span)
133 | Error::IndexOutOfRange(_, span)
134 | Error::InvalidIndex(_, span)
135 | Error::IntrinsicFail(_, _, span)
136 | Error::IntTooLarge(_, span)
137 | Error::InvalidRotationAngle(_, span)
138 | Error::InvalidNegativeInt(_, span)
139 | Error::MissingSpec(_, span)
140 | Error::OutputFail(span)
141 | Error::QubitUniqueness(span)
142 | Error::RangeStepZero(span)
143 | Error::ReleasedQubitNotZero(_, span)
144 | Error::UnboundName(span)
145 | Error::UnknownIntrinsic(_, span)
146 | Error::UserFail(_, span)
147 | Error::InvalidArrayLength(_, span) => span,
148 }
149 }
150}
151
152/// A specialization that may be implemented for an operation.
153enum Spec {
154 /// The default specialization.
155 Body,
156 /// The adjoint specialization.
157 Adj,
158 /// The controlled specialization.
159 Ctl,
160 /// The controlled adjoint specialization.
161 CtlAdj,
162}
163
164impl Display for Spec {
165 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
166 match self {
167 Spec::Body => f.write_str("body"),
168 Spec::Adj => f.write_str("adjoint"),
169 Spec::Ctl => f.write_str("controlled"),
170 Spec::CtlAdj => f.write_str("controlled adjoint"),
171 }
172 }
173}
174
175/// An id either representing a statement or an expression to be evaluated.
176#[derive(Clone, Copy)]
177pub enum EvalId {
178 Expr(ExprId),
179 Stmt(StmtId),
180}
181
182impl From<ExprId> for EvalId {
183 fn from(expr: ExprId) -> Self {
184 Self::Expr(expr)
185 }
186}
187
188impl From<StmtId> for EvalId {
189 fn from(stmt: StmtId) -> Self {
190 Self::Stmt(stmt)
191 }
192}
193
194/// Evaluates the given code with the given context.
195/// # Errors
196/// Returns the first error encountered during execution.
197/// # Panics
198/// On internal error where no result is returned.
199pub fn eval(
200 package: PackageId,
201 seed: Option<u64>,
202 id: EvalId,
203 globals: &impl PackageStoreLookup,
204 env: &mut Env,
205 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
206 receiver: &mut impl Receiver,
207) -> Result<Value, (Error, Vec<Frame>)> {
208 let mut state = State::new(package, seed);
209 match id {
210 EvalId::Expr(expr) => state.push_expr(expr),
211 EvalId::Stmt(stmt) => state.push_stmt(stmt),
212 }
213 let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?;
214 let StepResult::Return(value) = res else {
215 panic!("eval should always return a value");
216 };
217 Ok(value)
218}
219
220/// The type of step action to take during evaluation
221#[derive(Debug, Copy, Clone, Eq, PartialEq)]
222pub enum StepAction {
223 Next,
224 In,
225 Out,
226 Continue,
227}
228
229// The result of an evaluation step.
230#[derive(Clone, Debug)]
231pub enum StepResult {
232 BreakpointHit(StmtId),
233 Next,
234 StepIn,
235 StepOut,
236 Return(Value),
237}
238
239pub fn eval_push_expr(state: &mut State, expr: ExprId) {
240 state.push_expr(expr);
241}
242
243trait AsIndex {
244 type Output;
245
246 fn as_index(&self, index_source: PackageSpan) -> Self::Output;
247}
248
249impl AsIndex for i64 {
250 type Output = Result<usize, Error>;
251
252 fn as_index(&self, index_source: PackageSpan) -> Self::Output {
253 match (*self).try_into() {
254 Ok(index) => Ok(index),
255 Err(_) => Err(Error::InvalidIndex(*self, index_source)),
256 }
257 }
258}
259
260#[derive(Debug, Clone)]
261struct Variable {
262 name: Rc<str>,
263 value: Value,
264 mutability: Mutability,
265 span: Span,
266}
267
268#[derive(Debug, Clone)]
269pub struct VariableInfo {
270 pub value: Value,
271 pub name: Rc<str>,
272 pub type_name: String,
273 pub id: NodeId,
274 pub mutability: Mutability,
275 pub span: Span,
276}
277
278impl Variable {
279 fn is_mutable(&self) -> bool {
280 self.mutability == Mutability::Mutable
281 }
282}
283
284struct Range {
285 step: i64,
286 end: i64,
287 curr: i64,
288}
289
290impl Iterator for Range {
291 type Item = i64;
292
293 fn next(&mut self) -> Option<Self::Item> {
294 let curr = self.curr;
295 self.curr += self.step;
296 if (self.step > 0 && curr <= self.end) || (self.step < 0 && curr >= self.end) {
297 Some(curr)
298 } else {
299 None
300 }
301 }
302}
303
304impl Range {
305 fn new(start: i64, step: i64, end: i64) -> Self {
306 Range {
307 step,
308 end,
309 curr: start,
310 }
311 }
312}
313
314pub struct Env(Vec<Scope>);
315
316impl Env {
317 #[must_use]
318 fn get(&self, id: NodeId) -> Option<&Variable> {
319 self.0
320 .iter()
321 .rev()
322 .find_map(|scope| scope.bindings.get(&id))
323 }
324
325 fn get_mut(&mut self, id: NodeId) -> Option<&mut Variable> {
326 self.0
327 .iter_mut()
328 .rev()
329 .find_map(|scope| scope.bindings.get_mut(&id))
330 }
331
332 fn push_scope(&mut self, frame_id: usize) {
333 let scope = Scope {
334 frame_id,
335 ..Default::default()
336 };
337 self.0.push(scope);
338 }
339
340 fn leave_scope(&mut self) {
341 self.0
342 .pop()
343 .expect("scope should be entered first before leaving");
344 }
345
346 #[must_use]
347 pub fn get_variables_in_top_frame(&self) -> Vec<VariableInfo> {
348 if let Some(scope) = self.0.last() {
349 self.get_variables_in_frame(scope.frame_id)
350 } else {
351 vec![]
352 }
353 }
354
355 #[must_use]
356 pub fn get_variables_in_frame(&self, frame_id: usize) -> Vec<VariableInfo> {
357 let candidate_scopes: Vec<_> = self
358 .0
359 .iter()
360 .filter(|scope| scope.frame_id == frame_id)
361 .map(|scope| scope.bindings.iter())
362 .collect();
363
364 let variables_by_scope: Vec<Vec<VariableInfo>> = candidate_scopes
365 .into_iter()
366 .map(|bindings| {
367 bindings
368 .map(|(id, var)| VariableInfo {
369 id: *id,
370 name: var.name.clone(),
371 type_name: var.value.type_name().to_string(),
372 value: var.value.clone(),
373 mutability: var.mutability,
374 span: var.span,
375 })
376 .collect()
377 })
378 .collect();
379 variables_by_scope.into_iter().flatten().collect::<Vec<_>>()
380 }
381}
382
383#[derive(Default)]
384struct Scope {
385 bindings: FxHashMap<NodeId, Variable>,
386 frame_id: usize,
387}
388
389impl Default for Env {
390 #[must_use]
391 fn default() -> Self {
392 Self(vec![Scope::default()])
393 }
394}
395
396enum Cont {
397 Action(Action),
398 Expr(ExprId),
399 Frame(usize),
400 Scope,
401 Stmt(StmtId),
402}
403
404#[derive(Clone)]
405enum Action {
406 Array(usize),
407 ArrayRepeat(Span),
408 ArrayAppendInPlace(ExprId),
409 Assign(ExprId),
410 Bind(PatId, Mutability),
411 BinOp(BinOp, Span, Option<ExprId>),
412 Call(Span, Span),
413 Consume,
414 Fail(Span),
415 Field(Field),
416 If(ExprId, Option<ExprId>),
417 Index(Span),
418 Range(bool, bool, bool),
419 Return,
420 StringConcat(usize),
421 StringLit(Rc<str>),
422 UpdateIndex(Span),
423 UpdateIndexInPlace(ExprId, Span),
424 Tuple(usize),
425 UnOp(UnOp),
426 UpdateField(Field),
427 While(ExprId, BlockId),
428}
429
430pub struct State {
431 stack: Vec<Cont>,
432 vals: Vec<Value>,
433 package: PackageId,
434 call_stack: CallStack,
435 current_span: Span,
436 rng: RefCell<StdRng>,
437}
438
439impl State {
440 #[must_use]
441 pub fn new(package: PackageId, classical_seed: Option<u64>) -> Self {
442 let rng = match classical_seed {
443 Some(seed) => RefCell::new(StdRng::seed_from_u64(seed)),
444 None => RefCell::new(StdRng::from_entropy()),
445 };
446 Self {
447 stack: Vec::new(),
448 vals: Vec::new(),
449 package,
450 call_stack: CallStack::default(),
451 current_span: Span::default(),
452 rng,
453 }
454 }
455
456 fn pop_cont(&mut self) -> Option<Cont> {
457 self.stack.pop()
458 }
459
460 fn push_action(&mut self, action: Action) {
461 self.stack.push(Cont::Action(action));
462 }
463
464 fn push_expr(&mut self, expr: ExprId) {
465 self.stack.push(Cont::Expr(expr));
466 }
467
468 fn push_frame(&mut self, id: StoreItemId, functor: FunctorApp) {
469 self.call_stack.push_frame(Frame {
470 span: self.current_span,
471 id,
472 caller: self.package,
473 functor,
474 });
475 self.stack.push(Cont::Frame(self.vals.len()));
476 self.package = id.package;
477 }
478
479 fn leave_frame(&mut self, len: usize) {
480 let frame = self
481 .call_stack
482 .pop_frame()
483 .expect("frame should be present");
484 self.package = frame.caller;
485 let frame_val = self.pop_val();
486 self.vals.drain(len..);
487 self.push_val(frame_val);
488 }
489
490 fn push_scope(&mut self, env: &mut Env) {
491 env.push_scope(self.call_stack.len());
492 self.stack.push(Cont::Scope);
493 }
494
495 fn push_stmt(&mut self, stmt: StmtId) {
496 self.stack.push(Cont::Stmt(stmt));
497 }
498
499 fn push_block(&mut self, env: &mut Env, globals: &impl PackageStoreLookup, block: BlockId) {
500 let block = globals.get_block((self.package, block).into());
501 self.push_scope(env);
502 for stmt in block.stmts.iter().rev() {
503 self.push_stmt(*stmt);
504 self.push_action(Action::Consume);
505 }
506 if block.stmts.is_empty() {
507 self.push_val(Value::unit());
508 } else {
509 self.pop_cont();
510 }
511 }
512
513 fn pop_val(&mut self) -> Value {
514 self.vals.pop().expect("value should be present")
515 }
516
517 fn pop_vals(&mut self, len: usize) -> Vec<Value> {
518 self.vals.drain(self.vals.len() - len..).collect()
519 }
520
521 fn push_val(&mut self, val: Value) {
522 self.vals.push(val);
523 }
524
525 #[must_use]
526 pub fn get_stack_frames(&self) -> Vec<Frame> {
527 let mut frames = self.call_stack.clone().into_frames();
528
529 let mut span = self.current_span;
530 for frame in frames.iter_mut().rev() {
531 std::mem::swap(&mut frame.span, &mut span);
532 }
533 frames
534 }
535
536 /// # Errors
537 /// Returns the first error encountered during execution.
538 /// # Panics
539 /// When returning a value in the middle of execution.
540 pub fn eval(
541 &mut self,
542 globals: &impl PackageStoreLookup,
543 env: &mut Env,
544 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
545 out: &mut impl Receiver,
546 breakpoints: &[StmtId],
547 step: StepAction,
548 ) -> Result<StepResult, (Error, Vec<Frame>)> {
549 let current_frame = self.call_stack.len();
550
551 while let Some(cont) = self.pop_cont() {
552 let res = match cont {
553 Cont::Action(action) => {
554 self.cont_action(env, sim, globals, action, out)
555 .map_err(|e| (e, self.get_stack_frames()))?;
556 continue;
557 }
558 Cont::Expr(expr) => {
559 self.cont_expr(env, globals, expr)
560 .map_err(|e| (e, self.get_stack_frames()))?;
561 continue;
562 }
563 Cont::Frame(len) => {
564 self.leave_frame(len);
565 continue;
566 }
567 Cont::Scope => {
568 env.leave_scope();
569 continue;
570 }
571 Cont::Stmt(stmt) => {
572 self.cont_stmt(globals, stmt);
573 if let Some(bp) = breakpoints.iter().find(|&bp| *bp == stmt) {
574 StepResult::BreakpointHit(*bp)
575 } else {
576 if self.current_span == Span::default() {
577 // if there is no span, we are in generated code, so we should skip
578 continue;
579 }
580 // no breakpoint, but we may stop here
581 if step == StepAction::In {
582 StepResult::StepIn
583 } else if step == StepAction::Next && current_frame >= self.call_stack.len()
584 {
585 StepResult::Next
586 } else if step == StepAction::Out && current_frame > self.call_stack.len() {
587 StepResult::StepOut
588 } else {
589 continue;
590 }
591 }
592 }
593 };
594
595 if let StepResult::Return(_) = res {
596 panic!("unexpected return");
597 }
598
599 return Ok(res);
600 }
601
602 Ok(StepResult::Return(self.get_result()))
603 }
604
605 pub fn get_result(&mut self) -> Value {
606 self.pop_val()
607 }
608
609 #[allow(clippy::similar_names)]
610 fn cont_expr(
611 &mut self,
612 env: &mut Env,
613 globals: &impl PackageStoreLookup,
614 expr: ExprId,
615 ) -> Result<(), Error> {
616 let expr = globals.get_expr((self.package, expr).into());
617 self.current_span = expr.span;
618
619 match &expr.kind {
620 ExprKind::Array(arr) => self.cont_arr(arr),
621 ExprKind::ArrayRepeat(item, size) => self.cont_arr_repeat(globals, *item, *size),
622 ExprKind::Assign(lhs, rhs) => self.cont_assign(*lhs, *rhs),
623 ExprKind::AssignOp(op, lhs, rhs) => self.cont_assign_op(globals, *op, *lhs, *rhs),
624 ExprKind::AssignField(record, field, replace) => {
625 self.cont_assign_field(*record, field, *replace);
626 }
627 ExprKind::AssignIndex(lhs, mid, rhs) => {
628 self.cont_assign_index(globals, *lhs, *mid, *rhs);
629 }
630 ExprKind::BinOp(op, lhs, rhs) => self.cont_binop(globals, *op, *rhs, *lhs),
631 ExprKind::Block(block) => self.push_block(env, globals, *block),
632 ExprKind::Call(callee_expr, args_expr) => {
633 self.cont_call(globals, *callee_expr, *args_expr);
634 }
635 ExprKind::Closure(args, callable) => {
636 let closure = resolve_closure(env, self.package, expr.span, args, *callable)?;
637 self.push_val(closure);
638 }
639 ExprKind::Fail(fail_expr) => self.cont_fail(expr.span, *fail_expr),
640 ExprKind::Field(expr, field) => self.cont_field(*expr, field),
641 ExprKind::Hole => panic!("hole expr should be disallowed by passes"),
642 ExprKind::If(cond_expr, then_expr, else_expr) => {
643 self.cont_if(*cond_expr, *then_expr, *else_expr);
644 }
645 ExprKind::Index(arr, index) => self.cont_index(globals, *arr, *index),
646 ExprKind::Lit(lit) => self.push_val(lit_to_val(lit)),
647 ExprKind::Range(start, step, end) => self.cont_range(*start, *step, *end),
648 ExprKind::Return(expr) => self.cont_ret(*expr),
649 ExprKind::String(components) => self.cont_string(components),
650 ExprKind::UpdateIndex(lhs, mid, rhs) => self.update_index(globals, *lhs, *mid, *rhs),
651 ExprKind::Tuple(tup) => self.cont_tup(tup),
652 ExprKind::UnOp(op, expr) => self.cont_unop(*op, *expr),
653 ExprKind::UpdateField(record, field, replace) => {
654 self.cont_update_field(*record, field, *replace);
655 }
656 ExprKind::Var(res, _) => {
657 self.push_val(resolve_binding(env, self.package, *res, expr.span)?);
658 }
659 ExprKind::While(cond_expr, block) => self.cont_while(*cond_expr, *block),
660 }
661
662 Ok(())
663 }
664
665 fn cont_tup(&mut self, tup: &Vec<ExprId>) {
666 self.push_action(Action::Tuple(tup.len()));
667 for tup_expr in tup.iter().rev() {
668 self.push_expr(*tup_expr);
669 }
670 }
671
672 fn cont_arr(&mut self, arr: &Vec<ExprId>) {
673 self.push_action(Action::Array(arr.len()));
674 for entry in arr.iter().rev() {
675 self.push_expr(*entry);
676 }
677 }
678
679 fn cont_arr_repeat(&mut self, globals: &impl PackageStoreLookup, item: ExprId, size: ExprId) {
680 let size_expr = globals.get_expr((self.package, size).into());
681 self.push_action(Action::ArrayRepeat(size_expr.span));
682 self.push_expr(size);
683 self.push_expr(item);
684 }
685
686 fn cont_ret(&mut self, expr: ExprId) {
687 self.push_action(Action::Return);
688 self.push_expr(expr);
689 }
690
691 fn cont_if(&mut self, cond_expr: ExprId, then_expr: ExprId, else_expr: Option<ExprId>) {
692 self.push_action(Action::If(then_expr, else_expr));
693 self.push_expr(cond_expr);
694 }
695
696 fn cont_fail(&mut self, span: Span, fail_expr: ExprId) {
697 self.push_action(Action::Fail(span));
698 self.push_expr(fail_expr);
699 }
700
701 fn cont_assign(&mut self, lhs: ExprId, rhs: ExprId) {
702 self.push_action(Action::Assign(lhs));
703 self.push_expr(rhs);
704 self.push_val(Value::unit());
705 }
706
707 fn cont_assign_op(
708 &mut self,
709 globals: &impl PackageStoreLookup,
710 op: BinOp,
711 lhs: ExprId,
712 rhs: ExprId,
713 ) {
714 // If we know the assign op is an array append, as in `set arr += other;`, we should perform it in-place.
715 if op == BinOp::Add
716 && matches!(
717 globals.get_expr((self.package, lhs).into()).ty,
718 Ty::Array(_)
719 )
720 {
721 self.push_action(Action::ArrayAppendInPlace(lhs));
722 self.push_expr(rhs);
723 self.push_val(Value::unit());
724 return;
725 }
726
727 self.push_action(Action::Assign(lhs));
728 self.cont_binop(globals, op, rhs, lhs);
729 self.push_val(Value::unit());
730 }
731
732 fn cont_assign_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
733 self.push_action(Action::Assign(record));
734 self.cont_update_field(record, field, replace);
735 self.push_val(Value::unit());
736 }
737
738 fn cont_assign_index(
739 &mut self,
740 globals: &impl PackageStoreLookup,
741 lhs: ExprId,
742 mid: ExprId,
743 rhs: ExprId,
744 ) {
745 let span = globals.get_expr((self.package, mid).into()).span;
746 self.push_action(Action::UpdateIndexInPlace(lhs, span));
747 self.push_expr(rhs);
748 self.push_expr(mid);
749 self.push_val(Value::unit());
750 }
751
752 fn cont_field(&mut self, expr: ExprId, field: &Field) {
753 self.push_action(Action::Field(field.clone()));
754 self.push_expr(expr);
755 }
756
757 fn cont_index(&mut self, globals: &impl PackageStoreLookup, arr: ExprId, index: ExprId) {
758 let index_expr = globals.get_expr((self.package, index).into());
759 self.push_action(Action::Index(index_expr.span));
760 self.push_expr(index);
761 self.push_expr(arr);
762 }
763
764 fn cont_range(&mut self, start: Option<ExprId>, step: Option<ExprId>, end: Option<ExprId>) {
765 self.push_action(Action::Range(
766 start.is_some(),
767 step.is_some(),
768 end.is_some(),
769 ));
770 if let Some(end) = end {
771 self.push_expr(end);
772 }
773 if let Some(step) = step {
774 self.push_expr(step);
775 }
776 if let Some(start) = start {
777 self.push_expr(start);
778 }
779 }
780
781 fn cont_string(&mut self, components: &[StringComponent]) {
782 if let [StringComponent::Lit(str)] = components {
783 self.push_val(Value::String(Rc::clone(str)));
784 return;
785 }
786
787 self.push_action(Action::StringConcat(components.len()));
788 for component in components.iter().rev() {
789 match component {
790 StringComponent::Expr(expr) => self.push_expr(*expr),
791 StringComponent::Lit(lit) => self.push_action(Action::StringLit(lit.clone())),
792 }
793 }
794 }
795
796 fn cont_while(&mut self, cond_expr: ExprId, block: BlockId) {
797 self.push_action(Action::While(cond_expr, block));
798 self.push_expr(cond_expr);
799 }
800
801 fn cont_call(&mut self, globals: &impl PackageStoreLookup, callee: ExprId, args: ExprId) {
802 let callee_expr = globals.get_expr((self.package, callee).into());
803 let args_expr = globals.get_expr((self.package, args).into());
804 self.push_action(Action::Call(callee_expr.span, args_expr.span));
805 self.push_expr(args);
806 self.push_expr(callee);
807 }
808
809 fn cont_binop(
810 &mut self,
811 globals: &impl PackageStoreLookup,
812 op: BinOp,
813 rhs: ExprId,
814 lhs: ExprId,
815 ) {
816 let rhs_expr = globals.get_expr((self.package, rhs).into());
817 match op {
818 BinOp::Add
819 | BinOp::AndB
820 | BinOp::Div
821 | BinOp::Eq
822 | BinOp::Exp
823 | BinOp::Gt
824 | BinOp::Gte
825 | BinOp::Lt
826 | BinOp::Lte
827 | BinOp::Mod
828 | BinOp::Mul
829 | BinOp::Neq
830 | BinOp::OrB
831 | BinOp::Shl
832 | BinOp::Shr
833 | BinOp::Sub
834 | BinOp::XorB => {
835 self.push_action(Action::BinOp(op, rhs_expr.span, None));
836 self.push_expr(rhs);
837 self.push_expr(lhs);
838 }
839 BinOp::AndL | BinOp::OrL => {
840 self.push_action(Action::BinOp(op, rhs_expr.span, Some(rhs)));
841 self.push_expr(lhs);
842 }
843 }
844 }
845
846 fn update_index(
847 &mut self,
848 globals: &impl PackageStoreLookup,
849 lhs: ExprId,
850 mid: ExprId,
851 rhs: ExprId,
852 ) {
853 let span = globals.get_expr((self.package, mid).into()).span;
854 self.push_action(Action::UpdateIndex(span));
855 self.push_expr(lhs);
856 self.push_expr(rhs);
857 self.push_expr(mid);
858 }
859
860 fn cont_unop(&mut self, op: UnOp, expr: ExprId) {
861 self.push_action(Action::UnOp(op));
862 self.push_expr(expr);
863 }
864
865 fn cont_update_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
866 self.push_action(Action::UpdateField(field.clone()));
867 self.push_expr(replace);
868 self.push_expr(record);
869 }
870
871 fn cont_stmt(&mut self, globals: &impl PackageStoreLookup, stmt: StmtId) {
872 let stmt = globals.get_stmt((self.package, stmt).into());
873 self.current_span = stmt.span;
874
875 match &stmt.kind {
876 StmtKind::Expr(expr) => self.push_expr(*expr),
877 StmtKind::Item(..) => self.push_val(Value::unit()),
878 StmtKind::Local(mutability, pat, expr) => {
879 self.push_action(Action::Bind(*pat, *mutability));
880 self.push_expr(*expr);
881 self.push_val(Value::unit());
882 }
883 StmtKind::Semi(expr) => {
884 self.push_action(Action::Consume);
885 self.push_expr(*expr);
886 self.push_val(Value::unit());
887 }
888 }
889 }
890
891 fn cont_action(
892 &mut self,
893 env: &mut Env,
894 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
895 globals: &impl PackageStoreLookup,
896 action: Action,
897 out: &mut impl Receiver,
898 ) -> Result<(), Error> {
899 match action {
900 Action::Array(len) => self.eval_arr(len),
901 Action::ArrayAppendInPlace(lhs) => {
902 self.eval_array_append_in_place(env, globals, lhs)?;
903 }
904 Action::ArrayRepeat(span) => self.eval_arr_repeat(span)?,
905 Action::Assign(lhs) => self.eval_assign(env, globals, lhs)?,
906 Action::BinOp(op, span, rhs) => self.eval_binop(op, span, rhs)?,
907 Action::Bind(pat, mutability) => self.eval_bind(env, globals, pat, mutability),
908 Action::Call(callee_span, args_span) => {
909 self.eval_call(env, sim, globals, callee_span, args_span, out)?;
910 }
911 Action::Consume => {
912 self.pop_val();
913 }
914 Action::Fail(span) => {
915 return Err(Error::UserFail(
916 self.pop_val().unwrap_string().to_string(),
917 self.to_global_span(span),
918 ));
919 }
920 Action::Field(field) => self.eval_field(field),
921 Action::If(then_expr, else_expr) => self.eval_if(then_expr, else_expr),
922 Action::Index(span) => self.eval_index(span)?,
923 Action::Range(has_start, has_step, has_end) => {
924 self.eval_range(has_start, has_step, has_end);
925 }
926 Action::Return => self.eval_ret(env),
927 Action::StringConcat(len) => self.eval_string_concat(len),
928 Action::StringLit(str) => self.push_val(Value::String(str)),
929 Action::UpdateIndex(span) => self.eval_update_index(span)?,
930 Action::UpdateIndexInPlace(lhs, span) => {
931 self.eval_update_index_in_place(env, globals, lhs, span)?;
932 }
933 Action::Tuple(len) => self.eval_tup(len),
934 Action::UnOp(op) => self.eval_unop(op),
935 Action::UpdateField(field) => self.eval_update_field(field),
936 Action::While(cond_expr, block) => self.eval_while(env, globals, cond_expr, block),
937 }
938 Ok(())
939 }
940
941 fn eval_arr(&mut self, len: usize) {
942 let arr = self.pop_vals(len);
943 self.push_val(Value::Array(arr.into()));
944 }
945
946 fn eval_array_append_in_place(
947 &mut self,
948 env: &mut Env,
949 globals: &impl PackageStoreLookup,
950 lhs: ExprId,
951 ) -> Result<(), Error> {
952 let lhs = globals.get_expr((self.package, lhs).into());
953 let rhs = self.pop_val();
954 match (&lhs.kind, rhs) {
955 (&ExprKind::Var(Res::Local(node), _), rhs) => match env.get_mut(node) {
956 Some(var) if var.is_mutable() => {
957 var.value.append_array(rhs);
958 }
959 Some(_) => {
960 unreachable!("update of mutable variable should be disallowed by compiler")
961 }
962 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
963 },
964 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
965 }
966 Ok(())
967 }
968
969 fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> {
970 let size_val = self.pop_val().unwrap_int();
971 let item_val = self.pop_val();
972 let s = match size_val.try_into() {
973 Ok(i) => Ok(i),
974 Err(_) => Err(Error::InvalidArrayLength(
975 size_val,
976 self.to_global_span(span),
977 )),
978 }?;
979 self.push_val(Value::Array(vec![item_val; s].into()));
980 Ok(())
981 }
982
983 fn eval_assign(
984 &mut self,
985 env: &mut Env,
986 globals: &impl PackageStoreLookup,
987 lhs: ExprId,
988 ) -> Result<(), Error> {
989 let rhs = self.pop_val();
990 self.update_binding(env, globals, lhs, rhs)
991 }
992
993 fn eval_bind(
994 &mut self,
995 env: &mut Env,
996 globals: &impl PackageStoreLookup,
997 pat: PatId,
998 mutability: Mutability,
999 ) {
1000 let val = self.pop_val();
1001 self.bind_value(env, globals, pat, val, mutability);
1002 }
1003
1004 fn eval_binop(&mut self, op: BinOp, span: Span, rhs: Option<ExprId>) -> Result<(), Error> {
1005 match op {
1006 BinOp::Add => self.eval_binop_simple(eval_binop_add),
1007 BinOp::AndB => self.eval_binop_simple(eval_binop_andb),
1008 BinOp::AndL => {
1009 if self.pop_val().unwrap_bool() {
1010 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
1011 } else {
1012 self.push_val(Value::Bool(false));
1013 }
1014 }
1015 BinOp::Div => self.eval_binop_with_error(span, eval_binop_div)?,
1016 BinOp::Eq => {
1017 let rhs_val = self.pop_val();
1018 let lhs_val = self.pop_val();
1019 self.push_val(Value::Bool(lhs_val == rhs_val));
1020 }
1021 BinOp::Exp => self.eval_binop_with_error(span, eval_binop_exp)?,
1022 BinOp::Gt => self.eval_binop_simple(eval_binop_gt),
1023 BinOp::Gte => self.eval_binop_simple(eval_binop_gte),
1024 BinOp::Lt => self.eval_binop_simple(eval_binop_lt),
1025 BinOp::Lte => self.eval_binop_simple(eval_binop_lte),
1026 BinOp::Mod => self.eval_binop_with_error(span, eval_binop_mod)?,
1027 BinOp::Mul => self.eval_binop_simple(eval_binop_mul),
1028 BinOp::Neq => {
1029 let rhs_val = self.pop_val();
1030 let lhs_val = self.pop_val();
1031 self.push_val(Value::Bool(lhs_val != rhs_val));
1032 }
1033 BinOp::OrB => self.eval_binop_simple(eval_binop_orb),
1034 BinOp::OrL => {
1035 if self.pop_val().unwrap_bool() {
1036 self.push_val(Value::Bool(true));
1037 } else {
1038 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
1039 }
1040 }
1041 BinOp::Shl => self.eval_binop_with_error(span, eval_binop_shl)?,
1042 BinOp::Shr => self.eval_binop_with_error(span, eval_binop_shr)?,
1043 BinOp::Sub => self.eval_binop_simple(eval_binop_sub),
1044 BinOp::XorB => self.eval_binop_simple(eval_binop_xorb),
1045 }
1046 Ok(())
1047 }
1048
1049 fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) {
1050 let rhs_val = self.pop_val();
1051 let lhs_val = self.pop_val();
1052 self.push_val(binop_func(lhs_val, rhs_val));
1053 }
1054
1055 fn eval_binop_with_error(
1056 &mut self,
1057 span: Span,
1058 binop_func: impl FnOnce(Value, Value, PackageSpan) -> Result<Value, Error>,
1059 ) -> Result<(), Error> {
1060 let span = self.to_global_span(span);
1061 let rhs_val = self.pop_val();
1062 let lhs_val = self.pop_val();
1063 self.push_val(binop_func(lhs_val, rhs_val, span)?);
1064 Ok(())
1065 }
1066
1067 fn eval_call(
1068 &mut self,
1069 env: &mut Env,
1070 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
1071 globals: &impl PackageStoreLookup,
1072 callee_span: Span,
1073 arg_span: Span,
1074 out: &mut impl Receiver,
1075 ) -> Result<(), Error> {
1076 let arg = self.pop_val();
1077 let (callee_id, functor, fixed_args) = match self.pop_val() {
1078 Value::Closure(fixed_args, id, functor) => (id, functor, Some(fixed_args)),
1079 Value::Global(id, functor) => (id, functor, None),
1080 _ => panic!("value is not callable"),
1081 };
1082
1083 let callee_span = self.to_global_span(callee_span);
1084 let arg_span = self.to_global_span(arg_span);
1085
1086 let callee = match globals.get_global(callee_id) {
1087 Some(Global::Callable(callable)) => callable,
1088 Some(Global::Udt) => {
1089 self.push_val(arg);
1090 return Ok(());
1091 }
1092 None => return Err(Error::UnboundName(callee_span)),
1093 };
1094
1095 let spec = spec_from_functor_app(functor);
1096 self.push_frame(callee_id, functor);
1097 self.push_scope(env);
1098 match &callee.implementation {
1099 CallableImpl::Intrinsic => {
1100 let name = &callee.name.name;
1101 let val = intrinsic::call(
1102 name,
1103 callee_span,
1104 arg,
1105 arg_span,
1106 sim,
1107 &mut self.rng.borrow_mut(),
1108 out,
1109 )?;
1110 self.push_val(val);
1111 Ok(())
1112 }
1113 CallableImpl::Spec(specialized_implementation) => {
1114 let spec_decl = match spec {
1115 Spec::Body => Some(&specialized_implementation.body),
1116 Spec::Adj => specialized_implementation.adj.as_ref(),
1117 Spec::Ctl => specialized_implementation.ctl.as_ref(),
1118 Spec::CtlAdj => specialized_implementation.ctl_adj.as_ref(),
1119 }
1120 .ok_or(Error::MissingSpec(spec.to_string(), callee_span))?;
1121 self.bind_args_for_spec(
1122 env,
1123 globals,
1124 callee.input,
1125 spec_decl.input,
1126 arg,
1127 functor.controlled,
1128 fixed_args,
1129 );
1130 self.push_block(env, globals, spec_decl.block);
1131 Ok(())
1132 }
1133 }
1134 }
1135
1136 fn eval_field(&mut self, field: Field) {
1137 let record = self.pop_val();
1138 let val = match (record, field) {
1139 (Value::Range(Some(start), _, _), Field::Prim(PrimField::Start)) => Value::Int(start),
1140 (Value::Range(_, step, _), Field::Prim(PrimField::Step)) => Value::Int(step),
1141 (Value::Range(_, _, Some(end)), Field::Prim(PrimField::End)) => Value::Int(end),
1142 (record, Field::Path(path)) => {
1143 follow_field_path(record, &path.indices).expect("field path should be valid")
1144 }
1145 _ => panic!("invalid field access"),
1146 };
1147 self.push_val(val);
1148 }
1149
1150 fn eval_if(&mut self, then_expr: ExprId, else_expr: Option<ExprId>) {
1151 if self.pop_val().unwrap_bool() {
1152 self.push_expr(then_expr);
1153 } else if let Some(else_expr) = else_expr {
1154 self.push_expr(else_expr);
1155 } else {
1156 self.push_val(Value::unit());
1157 }
1158 }
1159
1160 fn eval_index(&mut self, span: Span) -> Result<(), Error> {
1161 let index_val = self.pop_val();
1162 let arr = self.pop_val().unwrap_array();
1163 match &index_val {
1164 Value::Int(i) => self.push_val(index_array(&arr, *i, self.to_global_span(span))?),
1165 &Value::Range(start, step, end) => {
1166 self.push_val(slice_array(
1167 &arr,
1168 start,
1169 step,
1170 end,
1171 self.to_global_span(span),
1172 )?);
1173 }
1174 _ => panic!("array should only be indexed by Int or Range"),
1175 }
1176 Ok(())
1177 }
1178
1179 fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) {
1180 let end = if has_end {
1181 Some(self.pop_val().unwrap_int())
1182 } else {
1183 None
1184 };
1185 let step = if has_step {
1186 self.pop_val().unwrap_int()
1187 } else {
1188 val::DEFAULT_RANGE_STEP
1189 };
1190 let start = if has_start {
1191 Some(self.pop_val().unwrap_int())
1192 } else {
1193 None
1194 };
1195 self.push_val(Value::Range(start, step, end));
1196 }
1197
1198 fn eval_ret(&mut self, env: &mut Env) {
1199 while let Some(cont) = self.pop_cont() {
1200 match cont {
1201 Cont::Frame(len) => {
1202 self.leave_frame(len);
1203 break;
1204 }
1205 Cont::Scope => env.leave_scope(),
1206 _ => {}
1207 }
1208 }
1209 }
1210
1211 fn eval_string_concat(&mut self, len: usize) {
1212 let mut string = String::new();
1213 for component in self.pop_vals(len) {
1214 write!(string, "{component}").expect("string should be writable");
1215 }
1216 self.push_val(Value::String(string.into()));
1217 }
1218
1219 fn eval_update_index(&mut self, span: Span) -> Result<(), Error> {
1220 let values = self.pop_val().unwrap_array();
1221 let update = self.pop_val();
1222 let index = self.pop_val();
1223 let span = self.to_global_span(span);
1224 match index {
1225 Value::Int(index) => self.eval_update_index_single(&values, index, update, span),
1226 Value::Range(start, step, end) => {
1227 self.eval_update_index_range(&values, start, step, end, update, span)
1228 }
1229 _ => unreachable!("array should only be indexed by Int or Range"),
1230 }
1231 }
1232
1233 fn eval_update_index_single(
1234 &mut self,
1235 values: &[Value],
1236 index: i64,
1237 update: Value,
1238 span: PackageSpan,
1239 ) -> Result<(), Error> {
1240 if index < 0 {
1241 return Err(Error::InvalidNegativeInt(index, span));
1242 }
1243 let i = index.as_index(span)?;
1244 let mut values = values.to_vec();
1245 match values.get_mut(i) {
1246 Some(value) => {
1247 *value = update;
1248 }
1249 None => return Err(Error::IndexOutOfRange(index, span)),
1250 }
1251 self.push_val(Value::Array(values.into()));
1252 Ok(())
1253 }
1254
1255 fn eval_update_index_range(
1256 &mut self,
1257 values: &[Value],
1258 start: Option<i64>,
1259 step: i64,
1260 end: Option<i64>,
1261 update: Value,
1262 span: PackageSpan,
1263 ) -> Result<(), Error> {
1264 let range = make_range(values, start, step, end, span)?;
1265 let mut values = values.to_vec();
1266 let update = update.unwrap_array();
1267 for (idx, update) in range.into_iter().zip(update.iter()) {
1268 let i = idx.as_index(span)?;
1269 match values.get_mut(i) {
1270 Some(value) => {
1271 *value = update.clone();
1272 }
1273 None => return Err(Error::IndexOutOfRange(idx, span)),
1274 }
1275 }
1276 self.push_val(Value::Array(values.into()));
1277 Ok(())
1278 }
1279
1280 fn eval_update_index_in_place(
1281 &mut self,
1282 env: &mut Env,
1283 globals: &impl PackageStoreLookup,
1284 lhs: ExprId,
1285 span: Span,
1286 ) -> Result<(), Error> {
1287 let update = self.pop_val();
1288 let index = self.pop_val();
1289 let span = self.to_global_span(span);
1290 match index {
1291 Value::Int(index) => {
1292 if index < 0 {
1293 return Err(Error::InvalidNegativeInt(index, span));
1294 }
1295 let i = index.as_index(span)?;
1296 self.update_array_index_single(env, globals, lhs, span, i, update)
1297 }
1298 range @ Value::Range(..) => {
1299 self.update_array_index_range(env, globals, lhs, span, &range, update)
1300 }
1301 _ => unreachable!("array should only be indexed by Int or Range"),
1302 }
1303 }
1304
1305 fn eval_tup(&mut self, len: usize) {
1306 let tup = self.pop_vals(len);
1307 self.push_val(Value::Tuple(tup.into()));
1308 }
1309
1310 fn eval_unop(&mut self, op: UnOp) {
1311 let val = self.pop_val();
1312 match op {
1313 UnOp::Functor(functor) => match val {
1314 Value::Closure(args, id, app) => {
1315 self.push_val(Value::Closure(args, id, update_functor_app(functor, app)));
1316 }
1317 Value::Global(id, app) => {
1318 self.push_val(Value::Global(id, update_functor_app(functor, app)));
1319 }
1320 _ => panic!("value should be callable"),
1321 },
1322 UnOp::Neg => match val {
1323 Value::BigInt(v) => self.push_val(Value::BigInt(v.neg())),
1324 Value::Double(v) => self.push_val(Value::Double(v.neg())),
1325 Value::Int(v) => self.push_val(Value::Int(v.wrapping_neg())),
1326 _ => panic!("value should be number"),
1327 },
1328 UnOp::NotB => match val {
1329 Value::Int(v) => self.push_val(Value::Int(!v)),
1330 Value::BigInt(v) => self.push_val(Value::BigInt(!v)),
1331 _ => panic!("value should be Int or BigInt"),
1332 },
1333 UnOp::NotL => match val {
1334 Value::Bool(b) => self.push_val(Value::Bool(!b)),
1335 _ => panic!("value should be bool"),
1336 },
1337 UnOp::Pos => match val {
1338 Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.push_val(val),
1339 _ => panic!("value should be number"),
1340 },
1341 UnOp::Unwrap => self.push_val(val),
1342 }
1343 }
1344
1345 fn eval_update_field(&mut self, field: Field) {
1346 let value = self.pop_val();
1347 let record = self.pop_val();
1348 let update = match (record, field) {
1349 (Value::Range(_, step, end), Field::Prim(PrimField::Start)) => {
1350 Value::Range(Some(value.unwrap_int()), step, end)
1351 }
1352 (Value::Range(start, _, end), Field::Prim(PrimField::Step)) => {
1353 Value::Range(start, value.unwrap_int(), end)
1354 }
1355 (Value::Range(start, step, _), Field::Prim(PrimField::End)) => {
1356 Value::Range(start, step, Some(value.unwrap_int()))
1357 }
1358 (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value)
1359 .expect("field path should be valid"),
1360 _ => panic!("invalid field access"),
1361 };
1362 self.push_val(update);
1363 }
1364
1365 fn eval_while(
1366 &mut self,
1367 env: &mut Env,
1368 globals: &impl PackageStoreLookup,
1369 cond_expr: ExprId,
1370 block: BlockId,
1371 ) {
1372 if self.pop_val().unwrap_bool() {
1373 self.cont_while(cond_expr, block);
1374 self.push_action(Action::Consume);
1375 self.push_val(Value::unit());
1376 self.push_block(env, globals, block);
1377 } else {
1378 self.push_val(Value::unit());
1379 }
1380 }
1381
1382 fn bind_value(
1383 &self,
1384 env: &mut Env,
1385 globals: &impl PackageStoreLookup,
1386 pat: PatId,
1387 val: Value,
1388 mutability: Mutability,
1389 ) {
1390 let pat = globals.get_pat((self.package, pat).into());
1391 match &pat.kind {
1392 PatKind::Bind(variable) => {
1393 let scope = env.0.last_mut().expect("binding should have a scope");
1394 match scope.bindings.entry(variable.id) {
1395 Entry::Vacant(entry) => entry.insert(Variable {
1396 name: variable.name.clone(),
1397 value: val,
1398 mutability,
1399 span: variable.span,
1400 }),
1401 Entry::Occupied(_) => panic!("duplicate binding"),
1402 };
1403 }
1404 PatKind::Discard => {}
1405 PatKind::Tuple(tup) => {
1406 let val_tup = val.unwrap_tuple();
1407 for (pat, val) in tup.iter().zip(val_tup.iter()) {
1408 self.bind_value(env, globals, *pat, val.clone(), mutability);
1409 }
1410 }
1411 }
1412 }
1413
1414 #[allow(clippy::similar_names)]
1415 fn update_binding(
1416 &self,
1417 env: &mut Env,
1418 globals: &impl PackageStoreLookup,
1419 lhs: ExprId,
1420 rhs: Value,
1421 ) -> Result<(), Error> {
1422 let lhs = globals.get_expr((self.package, lhs).into());
1423 match (&lhs.kind, rhs) {
1424 (ExprKind::Hole, _) => {}
1425 (&ExprKind::Var(Res::Local(node), _), rhs) => match env.get_mut(node) {
1426 Some(var) if var.is_mutable() => {
1427 var.value = rhs;
1428 }
1429 Some(_) => {
1430 unreachable!("update of mutable variable should be disallowed by compiler")
1431 }
1432 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1433 },
1434 (ExprKind::Tuple(var_tup), Value::Tuple(tup)) => {
1435 for (expr, val) in var_tup.iter().zip(tup.iter()) {
1436 self.update_binding(env, globals, *expr, val.clone())?;
1437 }
1438 }
1439 _ => unreachable!("unassignable pattern should be disallowed by compiler"),
1440 }
1441 Ok(())
1442 }
1443
1444 fn update_array_index_single(
1445 &self,
1446 env: &mut Env,
1447 globals: &impl PackageStoreLookup,
1448 lhs: ExprId,
1449 span: PackageSpan,
1450 index: usize,
1451 rhs: Value,
1452 ) -> Result<(), Error> {
1453 let lhs = globals.get_expr((self.package, lhs).into());
1454 match &lhs.kind {
1455 &ExprKind::Var(Res::Local(node), _) => match env.get_mut(node) {
1456 Some(var) if var.is_mutable() => {
1457 var.value.update_array(index, rhs).map_err(|idx| {
1458 Error::IndexOutOfRange(idx.try_into().expect("index should be valid"), span)
1459 })?;
1460 }
1461 Some(_) => {
1462 unreachable!("update of immutable variable should be disallowed by compiler")
1463 }
1464 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1465 },
1466 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1467 }
1468 Ok(())
1469 }
1470
1471 #[allow(clippy::similar_names)] // `env` and `end` are similar but distinct
1472 fn update_array_index_range(
1473 &self,
1474 env: &mut Env,
1475 globals: &impl PackageStoreLookup,
1476 lhs: ExprId,
1477 range_span: PackageSpan,
1478 range: &Value,
1479 update: Value,
1480 ) -> Result<(), Error> {
1481 let lhs = globals.get_expr((self.package, lhs).into());
1482 match &lhs.kind {
1483 &ExprKind::Var(Res::Local(node), _) => match env.get_mut(node) {
1484 Some(var) if var.is_mutable() => {
1485 let rhs = update.unwrap_array();
1486 let Value::Array(arr) = &mut var.value else {
1487 panic!("variable should be an array");
1488 };
1489 let Value::Range(start, step, end) = range else {
1490 unreachable!("range should be a Value::Range");
1491 };
1492 let range = make_range(arr, *start, *step, *end, range_span)?;
1493 for (idx, rhs) in range.into_iter().zip(rhs.iter()) {
1494 if idx < 0 {
1495 return Err(Error::InvalidNegativeInt(idx, range_span));
1496 }
1497 let i = idx.as_index(range_span)?;
1498 var.value.update_array(i, rhs.clone()).map_err(|idx| {
1499 Error::IndexOutOfRange(
1500 idx.try_into().expect("index should be valid"),
1501 range_span,
1502 )
1503 })?;
1504 }
1505 }
1506 Some(_) => {
1507 unreachable!("update of mutable variable should be disallowed by compiler")
1508 }
1509 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1510 },
1511 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1512 }
1513 Ok(())
1514 }
1515
1516 #[allow(clippy::too_many_arguments)]
1517 fn bind_args_for_spec(
1518 &self,
1519 env: &mut Env,
1520 globals: &impl PackageStoreLookup,
1521 decl_pat: PatId,
1522 spec_pat: Option<PatId>,
1523 args_val: Value,
1524 ctl_count: u8,
1525 fixed_args: Option<Rc<[Value]>>,
1526 ) {
1527 match spec_pat {
1528 Some(spec_pat) => {
1529 assert!(
1530 ctl_count > 0,
1531 "spec pattern tuple used without controlled functor"
1532 );
1533
1534 let mut tup = args_val;
1535 let mut ctls = vec![];
1536 for _ in 0..ctl_count {
1537 let [c, rest] = &*tup.unwrap_tuple() else {
1538 panic!("tuple should be arity 2");
1539 };
1540 ctls.extend_from_slice(&c.clone().unwrap_array());
1541 tup = rest.clone();
1542 }
1543
1544 self.bind_value(
1545 env,
1546 globals,
1547 spec_pat,
1548 Value::Array(ctls.into()),
1549 Mutability::Immutable,
1550 );
1551 self.bind_value(
1552 env,
1553 globals,
1554 decl_pat,
1555 merge_fixed_args(fixed_args, tup),
1556 Mutability::Immutable,
1557 );
1558 }
1559 None => self.bind_value(
1560 env,
1561 globals,
1562 decl_pat,
1563 merge_fixed_args(fixed_args, args_val),
1564 Mutability::Immutable,
1565 ),
1566 }
1567 }
1568
1569 fn to_global_span(&self, span: Span) -> PackageSpan {
1570 PackageSpan {
1571 package: map_fir_package_to_hir(self.package),
1572 span,
1573 }
1574 }
1575}
1576
1577fn merge_fixed_args(fixed_args: Option<Rc<[Value]>>, arg: Value) -> Value {
1578 if let Some(fixed_args) = fixed_args {
1579 Value::Tuple(fixed_args.iter().cloned().chain(iter::once(arg)).collect())
1580 } else {
1581 arg
1582 }
1583}
1584
1585fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result<Value, Error> {
1586 Ok(match res {
1587 Res::Err => panic!("resolution error"),
1588 Res::Item(item) => Value::Global(
1589 StoreItemId {
1590 package: item.package.unwrap_or(package),
1591 item: item.item,
1592 },
1593 FunctorApp::default(),
1594 ),
1595 Res::Local(node) => env
1596 .get(node)
1597 .ok_or(Error::UnboundName(PackageSpan {
1598 package: map_fir_package_to_hir(package),
1599 span,
1600 }))?
1601 .value
1602 .clone(),
1603 })
1604}
1605
1606fn spec_from_functor_app(functor: FunctorApp) -> Spec {
1607 match (functor.adjoint, functor.controlled) {
1608 (false, 0) => Spec::Body,
1609 (true, 0) => Spec::Adj,
1610 (false, _) => Spec::Ctl,
1611 (true, _) => Spec::CtlAdj,
1612 }
1613}
1614
1615fn resolve_closure(
1616 env: &Env,
1617 package: PackageId,
1618 span: Span,
1619 args: &[NodeId],
1620 callable: LocalItemId,
1621) -> Result<Value, Error> {
1622 let args: Option<_> = args
1623 .iter()
1624 .map(|&arg| Some(env.get(arg)?.value.clone()))
1625 .collect();
1626 let args: Vec<_> = args.ok_or(Error::UnboundName(PackageSpan {
1627 package: map_fir_package_to_hir(package),
1628 span,
1629 }))?;
1630 let callable = StoreItemId {
1631 package,
1632 item: callable,
1633 };
1634 Ok(Value::Closure(args.into(), callable, FunctorApp::default()))
1635}
1636
1637fn lit_to_val(lit: &Lit) -> Value {
1638 match lit {
1639 Lit::BigInt(v) => Value::BigInt(v.clone()),
1640 Lit::Bool(v) => Value::Bool(*v),
1641 Lit::Double(v) => Value::Double(*v),
1642 Lit::Int(v) => Value::Int(*v),
1643 Lit::Pauli(v) => Value::Pauli(*v),
1644 Lit::Result(fir::Result::Zero) => Value::RESULT_ZERO,
1645 Lit::Result(fir::Result::One) => Value::RESULT_ONE,
1646 }
1647}
1648
1649fn index_array(arr: &[Value], index: i64, span: PackageSpan) -> Result<Value, Error> {
1650 let i = index.as_index(span)?;
1651 match arr.get(i) {
1652 Some(v) => Ok(v.clone()),
1653 None => Err(Error::IndexOutOfRange(index, span)),
1654 }
1655}
1656
1657fn slice_array(
1658 arr: &[Value],
1659 start: Option<i64>,
1660 step: i64,
1661 end: Option<i64>,
1662 span: PackageSpan,
1663) -> Result<Value, Error> {
1664 let range = make_range(arr, start, step, end, span)?;
1665 let mut slice = vec![];
1666 for i in range {
1667 slice.push(index_array(arr, i, span)?);
1668 }
1669
1670 Ok(Value::Array(slice.into()))
1671}
1672
1673fn make_range(
1674 arr: &[Value],
1675 start: Option<i64>,
1676 step: i64,
1677 end: Option<i64>,
1678 span: PackageSpan,
1679) -> Result<Range, Error> {
1680 if step == 0 {
1681 Err(Error::RangeStepZero(span))
1682 } else {
1683 let len: i64 = match arr.len().try_into() {
1684 Ok(len) => Ok(len),
1685 Err(_) => Err(Error::ArrayTooLarge(span)),
1686 }?;
1687 let (start, end) = if step > 0 {
1688 (start.unwrap_or(0), end.unwrap_or(len - 1))
1689 } else {
1690 (start.unwrap_or(len - 1), end.unwrap_or(0))
1691 };
1692 Ok(Range::new(start, step, end))
1693 }
1694}
1695
1696fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value {
1697 match lhs_val {
1698 Value::Array(arr) => {
1699 let rhs_arr = rhs_val.unwrap_array();
1700 let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect();
1701 Value::Array(items.into())
1702 }
1703 Value::BigInt(val) => {
1704 let rhs = rhs_val.unwrap_big_int();
1705 Value::BigInt(val + rhs)
1706 }
1707 Value::Double(val) => {
1708 let rhs = rhs_val.unwrap_double();
1709 Value::Double(val + rhs)
1710 }
1711 Value::Int(val) => {
1712 let rhs = rhs_val.unwrap_int();
1713 Value::Int(val.wrapping_add(rhs))
1714 }
1715 Value::String(val) => {
1716 let rhs = rhs_val.unwrap_string();
1717 Value::String((val.to_string() + &rhs).into())
1718 }
1719 _ => panic!("value is not addable"),
1720 }
1721}
1722
1723fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value {
1724 match lhs_val {
1725 Value::BigInt(val) => {
1726 let rhs = rhs_val.unwrap_big_int();
1727 Value::BigInt(val & rhs)
1728 }
1729 Value::Int(val) => {
1730 let rhs = rhs_val.unwrap_int();
1731 Value::Int(val & rhs)
1732 }
1733 _ => panic!("value type does not support andb"),
1734 }
1735}
1736
1737fn eval_binop_div(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1738 match lhs_val {
1739 Value::BigInt(val) => {
1740 let rhs = rhs_val.unwrap_big_int();
1741 if rhs == BigInt::from(0) {
1742 Err(Error::DivZero(rhs_span))
1743 } else {
1744 Ok(Value::BigInt(val / rhs))
1745 }
1746 }
1747 Value::Int(val) => {
1748 let rhs = rhs_val.unwrap_int();
1749 if rhs == 0 {
1750 Err(Error::DivZero(rhs_span))
1751 } else {
1752 Ok(Value::Int(val.wrapping_div(rhs)))
1753 }
1754 }
1755 Value::Double(val) => {
1756 let rhs = rhs_val.unwrap_double();
1757 Ok(Value::Double(val / rhs))
1758 }
1759 _ => panic!("value should support div"),
1760 }
1761}
1762
1763fn eval_binop_exp(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1764 match lhs_val {
1765 Value::BigInt(val) => {
1766 let rhs_val = rhs_val.unwrap_int();
1767 if rhs_val < 0 {
1768 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1769 } else {
1770 let rhs_val: u32 = match rhs_val.try_into() {
1771 Ok(v) => Ok(v),
1772 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1773 }?;
1774 Ok(Value::BigInt(val.pow(rhs_val)))
1775 }
1776 }
1777 Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))),
1778 Value::Int(val) => {
1779 let rhs_val = rhs_val.unwrap_int();
1780 if rhs_val < 0 {
1781 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1782 } else {
1783 let result: i64 = match rhs_val.try_into() {
1784 Ok(v) => val
1785 .checked_pow(v)
1786 .ok_or(Error::IntTooLarge(rhs_val, rhs_span)),
1787 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1788 }?;
1789 Ok(Value::Int(result))
1790 }
1791 }
1792 _ => panic!("value should support exp"),
1793 }
1794}
1795
1796fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value {
1797 match lhs_val {
1798 Value::BigInt(val) => {
1799 let rhs = rhs_val.unwrap_big_int();
1800 Value::Bool(val > rhs)
1801 }
1802 Value::Int(val) => {
1803 let rhs = rhs_val.unwrap_int();
1804 Value::Bool(val > rhs)
1805 }
1806 Value::Double(val) => {
1807 let rhs = rhs_val.unwrap_double();
1808 Value::Bool(val > rhs)
1809 }
1810 _ => panic!("value doesn't support binop gt"),
1811 }
1812}
1813
1814fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value {
1815 match lhs_val {
1816 Value::BigInt(val) => {
1817 let rhs = rhs_val.unwrap_big_int();
1818 Value::Bool(val >= rhs)
1819 }
1820 Value::Int(val) => {
1821 let rhs = rhs_val.unwrap_int();
1822 Value::Bool(val >= rhs)
1823 }
1824 Value::Double(val) => {
1825 let rhs = rhs_val.unwrap_double();
1826 Value::Bool(val >= rhs)
1827 }
1828 _ => panic!("value doesn't support binop gte"),
1829 }
1830}
1831
1832fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value {
1833 match lhs_val {
1834 Value::BigInt(val) => {
1835 let rhs = rhs_val.unwrap_big_int();
1836 Value::Bool(val < rhs)
1837 }
1838 Value::Int(val) => {
1839 let rhs = rhs_val.unwrap_int();
1840 Value::Bool(val < rhs)
1841 }
1842 Value::Double(val) => {
1843 let rhs = rhs_val.unwrap_double();
1844 Value::Bool(val < rhs)
1845 }
1846 _ => panic!("value doesn't support binop lt"),
1847 }
1848}
1849
1850fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value {
1851 match lhs_val {
1852 Value::BigInt(val) => {
1853 let rhs = rhs_val.unwrap_big_int();
1854 Value::Bool(val <= rhs)
1855 }
1856 Value::Int(val) => {
1857 let rhs = rhs_val.unwrap_int();
1858 Value::Bool(val <= rhs)
1859 }
1860 Value::Double(val) => {
1861 let rhs = rhs_val.unwrap_double();
1862 Value::Bool(val <= rhs)
1863 }
1864 _ => panic!("value doesn't support binop lte"),
1865 }
1866}
1867
1868fn eval_binop_mod(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1869 match lhs_val {
1870 Value::BigInt(val) => {
1871 let rhs = rhs_val.unwrap_big_int();
1872 if rhs == BigInt::from(0) {
1873 Err(Error::DivZero(rhs_span))
1874 } else {
1875 Ok(Value::BigInt(val % rhs))
1876 }
1877 }
1878 Value::Int(val) => {
1879 let rhs = rhs_val.unwrap_int();
1880 if rhs == 0 {
1881 Err(Error::DivZero(rhs_span))
1882 } else {
1883 Ok(Value::Int(val.wrapping_rem(rhs)))
1884 }
1885 }
1886 Value::Double(val) => {
1887 let rhs = rhs_val.unwrap_double();
1888 if rhs == 0.0 {
1889 Err(Error::DivZero(rhs_span))
1890 } else {
1891 Ok(Value::Double(val % rhs))
1892 }
1893 }
1894 _ => panic!("value should support mod"),
1895 }
1896}
1897
1898fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value {
1899 match lhs_val {
1900 Value::BigInt(val) => {
1901 let rhs = rhs_val.unwrap_big_int();
1902 Value::BigInt(val * rhs)
1903 }
1904 Value::Int(val) => {
1905 let rhs = rhs_val.unwrap_int();
1906 Value::Int(val.wrapping_mul(rhs))
1907 }
1908 Value::Double(val) => {
1909 let rhs = rhs_val.unwrap_double();
1910 Value::Double(val * rhs)
1911 }
1912 _ => panic!("value should support mul"),
1913 }
1914}
1915
1916fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value {
1917 match lhs_val {
1918 Value::BigInt(val) => {
1919 let rhs = rhs_val.unwrap_big_int();
1920 Value::BigInt(val | rhs)
1921 }
1922 Value::Int(val) => {
1923 let rhs = rhs_val.unwrap_int();
1924 Value::Int(val | rhs)
1925 }
1926 _ => panic!("value type does not support orb"),
1927 }
1928}
1929
1930fn eval_binop_shl(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1931 Ok(match lhs_val {
1932 Value::BigInt(val) => {
1933 let rhs = rhs_val.unwrap_int();
1934 if rhs > 0 {
1935 Value::BigInt(val << rhs)
1936 } else {
1937 Value::BigInt(val >> rhs.abs())
1938 }
1939 }
1940 Value::Int(val) => {
1941 let rhs = rhs_val.unwrap_int();
1942 Value::Int(if rhs > 0 {
1943 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1944 val.checked_shl(shift)
1945 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1946 } else {
1947 let shift: u32 = rhs
1948 .checked_neg()
1949 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1950 .try_into()
1951 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1952 val.checked_shr(shift)
1953 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1954 })
1955 }
1956 _ => panic!("value should support shl"),
1957 })
1958}
1959
1960fn eval_binop_shr(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1961 Ok(match lhs_val {
1962 Value::BigInt(val) => {
1963 let rhs = rhs_val.unwrap_int();
1964 if rhs > 0 {
1965 Value::BigInt(val >> rhs)
1966 } else {
1967 Value::BigInt(val << rhs.abs())
1968 }
1969 }
1970 Value::Int(val) => {
1971 let rhs = rhs_val.unwrap_int();
1972 Value::Int(if rhs > 0 {
1973 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1974 val.checked_shr(shift)
1975 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1976 } else {
1977 let shift: u32 = rhs
1978 .checked_neg()
1979 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1980 .try_into()
1981 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1982 val.checked_shl(shift)
1983 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1984 })
1985 }
1986 _ => panic!("value should support shr"),
1987 })
1988}
1989
1990fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value {
1991 match lhs_val {
1992 Value::BigInt(val) => {
1993 let rhs = rhs_val.unwrap_big_int();
1994 Value::BigInt(val - rhs)
1995 }
1996 Value::Double(val) => {
1997 let rhs = rhs_val.unwrap_double();
1998 Value::Double(val - rhs)
1999 }
2000 Value::Int(val) => {
2001 let rhs = rhs_val.unwrap_int();
2002 Value::Int(val.wrapping_sub(rhs))
2003 }
2004 _ => panic!("value is not subtractable"),
2005 }
2006}
2007
2008fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value {
2009 match lhs_val {
2010 Value::BigInt(val) => {
2011 let rhs = rhs_val.unwrap_big_int();
2012 Value::BigInt(val ^ rhs)
2013 }
2014 Value::Int(val) => {
2015 let rhs = rhs_val.unwrap_int();
2016 Value::Int(val ^ rhs)
2017 }
2018 _ => panic!("value type does not support xorb"),
2019 }
2020}
2021
2022fn update_functor_app(functor: Functor, app: FunctorApp) -> FunctorApp {
2023 match functor {
2024 Functor::Adj => FunctorApp {
2025 adjoint: !app.adjoint,
2026 controlled: app.controlled,
2027 },
2028 Functor::Ctl => FunctorApp {
2029 adjoint: app.adjoint,
2030 controlled: app.controlled + 1,
2031 },
2032 }
2033}
2034
2035fn follow_field_path(mut value: Value, path: &[usize]) -> Option<Value> {
2036 for &index in path {
2037 let Value::Tuple(items) = value else {
2038 return None;
2039 };
2040 value = items[index].clone();
2041 }
2042 Some(value)
2043}
2044
2045fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option<Value> {
2046 match (record, path) {
2047 (_, []) => Some(replace.clone()),
2048 (Value::Tuple(items), &[next_index, ..]) if next_index < items.len() => {
2049 let update = |(index, item)| {
2050 if index == next_index {
2051 update_field_path(item, &path[1..], replace)
2052 } else {
2053 Some(item.clone())
2054 }
2055 };
2056
2057 let items: Option<_> = items.iter().enumerate().map(update).collect();
2058 Some(Value::Tuple(items?))
2059 }
2060 _ => None,
2061 }
2062}
2063