GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.1.3

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

2070lines · 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,
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 cont_stack: Vec<Cont>,
432 action_stack: Vec<Action>,
433 vals: Vec<Value>,
434 package: PackageId,
435 call_stack: CallStack,
436 current_span: Span,
437 rng: RefCell<StdRng>,
438}
439
440impl State {
441 #[must_use]
442 pub fn new(package: PackageId, classical_seed: Option<u64>) -> Self {
443 let rng = match classical_seed {
444 Some(seed) => RefCell::new(StdRng::seed_from_u64(seed)),
445 None => RefCell::new(StdRng::from_entropy()),
446 };
447 Self {
448 cont_stack: Vec::new(),
449 action_stack: Vec::new(),
450 vals: Vec::new(),
451 package,
452 call_stack: CallStack::default(),
453 current_span: Span::default(),
454 rng,
455 }
456 }
457
458 fn pop_cont(&mut self) -> Option<Cont> {
459 self.cont_stack.pop()
460 }
461
462 fn push_action(&mut self, action: Action) {
463 self.cont_stack.push(Cont::Action);
464 self.action_stack.push(action);
465 }
466
467 fn push_expr(&mut self, expr: ExprId) {
468 self.cont_stack.push(Cont::Expr(expr));
469 }
470
471 fn push_exprs(&mut self, exprs: &[ExprId]) {
472 self.cont_stack
473 .extend(exprs.iter().rev().map(|expr| Cont::Expr(*expr)));
474 }
475
476 fn push_frame(&mut self, id: StoreItemId, functor: FunctorApp) {
477 self.call_stack.push_frame(Frame {
478 span: self.current_span,
479 id,
480 caller: self.package,
481 functor,
482 });
483 self.cont_stack.push(Cont::Frame(self.vals.len()));
484 self.package = id.package;
485 }
486
487 fn leave_frame(&mut self, len: usize) {
488 let frame = self
489 .call_stack
490 .pop_frame()
491 .expect("frame should be present");
492 self.package = frame.caller;
493 let frame_val = self.pop_val();
494 self.vals.drain(len..);
495 self.push_val(frame_val);
496 }
497
498 fn push_scope(&mut self, env: &mut Env) {
499 env.push_scope(self.call_stack.len());
500 self.cont_stack.push(Cont::Scope);
501 }
502
503 fn push_stmt(&mut self, stmt: StmtId) {
504 self.cont_stack.push(Cont::Stmt(stmt));
505 }
506
507 fn push_block(&mut self, env: &mut Env, globals: &impl PackageStoreLookup, block: BlockId) {
508 let block = globals.get_block((self.package, block).into());
509 self.push_scope(env);
510 for stmt in block.stmts.iter().rev() {
511 self.push_stmt(*stmt);
512 self.push_action(Action::Consume);
513 }
514 if block.stmts.is_empty() {
515 self.push_val(Value::unit());
516 } else if let Some(Cont::Action) = self.pop_cont() {
517 self.action_stack.pop();
518 }
519 }
520
521 fn pop_val(&mut self) -> Value {
522 self.vals.pop().expect("value should be present")
523 }
524
525 fn pop_vals(&mut self, len: usize) -> Vec<Value> {
526 self.vals.drain(self.vals.len() - len..).collect()
527 }
528
529 fn push_val(&mut self, val: Value) {
530 self.vals.push(val);
531 }
532
533 #[must_use]
534 pub fn get_stack_frames(&self) -> Vec<Frame> {
535 let mut frames = self.call_stack.clone().into_frames();
536
537 let mut span = self.current_span;
538 for frame in frames.iter_mut().rev() {
539 std::mem::swap(&mut frame.span, &mut span);
540 }
541 frames
542 }
543
544 /// # Errors
545 /// Returns the first error encountered during execution.
546 /// # Panics
547 /// When returning a value in the middle of execution.
548 pub fn eval(
549 &mut self,
550 globals: &impl PackageStoreLookup,
551 env: &mut Env,
552 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
553 out: &mut impl Receiver,
554 breakpoints: &[StmtId],
555 step: StepAction,
556 ) -> Result<StepResult, (Error, Vec<Frame>)> {
557 let current_frame = self.call_stack.len();
558
559 while let Some(cont) = self.pop_cont() {
560 let res = match cont {
561 Cont::Action => {
562 let action = self.action_stack.pop().expect("action should be present");
563 self.cont_action(env, sim, globals, action, out)
564 .map_err(|e| (e, self.get_stack_frames()))?;
565 continue;
566 }
567 Cont::Expr(expr) => {
568 self.cont_expr(env, globals, expr)
569 .map_err(|e| (e, self.get_stack_frames()))?;
570 continue;
571 }
572 Cont::Frame(len) => {
573 self.leave_frame(len);
574 continue;
575 }
576 Cont::Scope => {
577 env.leave_scope();
578 continue;
579 }
580 Cont::Stmt(stmt) => {
581 self.cont_stmt(globals, stmt);
582 if let Some(bp) = breakpoints.iter().find(|&bp| *bp == stmt) {
583 StepResult::BreakpointHit(*bp)
584 } else {
585 if self.current_span == Span::default() {
586 // if there is no span, we are in generated code, so we should skip
587 continue;
588 }
589 // no breakpoint, but we may stop here
590 if step == StepAction::In {
591 StepResult::StepIn
592 } else if step == StepAction::Next && current_frame >= self.call_stack.len()
593 {
594 StepResult::Next
595 } else if step == StepAction::Out && current_frame > self.call_stack.len() {
596 StepResult::StepOut
597 } else {
598 continue;
599 }
600 }
601 }
602 };
603
604 if let StepResult::Return(_) = res {
605 panic!("unexpected return");
606 }
607
608 return Ok(res);
609 }
610
611 Ok(StepResult::Return(self.get_result()))
612 }
613
614 pub fn get_result(&mut self) -> Value {
615 self.pop_val()
616 }
617
618 #[allow(clippy::similar_names)]
619 fn cont_expr(
620 &mut self,
621 env: &mut Env,
622 globals: &impl PackageStoreLookup,
623 expr: ExprId,
624 ) -> Result<(), Error> {
625 let expr = globals.get_expr((self.package, expr).into());
626 self.current_span = expr.span;
627
628 match &expr.kind {
629 ExprKind::Array(arr) => self.cont_arr(arr),
630 ExprKind::ArrayRepeat(item, size) => self.cont_arr_repeat(globals, *item, *size),
631 ExprKind::Assign(lhs, rhs) => self.cont_assign(*lhs, *rhs),
632 ExprKind::AssignOp(op, lhs, rhs) => self.cont_assign_op(globals, *op, *lhs, *rhs),
633 ExprKind::AssignField(record, field, replace) => {
634 self.cont_assign_field(*record, field, *replace);
635 }
636 ExprKind::AssignIndex(lhs, mid, rhs) => {
637 self.cont_assign_index(globals, *lhs, *mid, *rhs);
638 }
639 ExprKind::BinOp(op, lhs, rhs) => self.cont_binop(globals, *op, *rhs, *lhs),
640 ExprKind::Block(block) => self.push_block(env, globals, *block),
641 ExprKind::Call(callee_expr, args_expr) => {
642 self.cont_call(globals, *callee_expr, *args_expr);
643 }
644 ExprKind::Closure(args, callable) => {
645 let closure = resolve_closure(env, self.package, expr.span, args, *callable)?;
646 self.push_val(closure);
647 }
648 ExprKind::Fail(fail_expr) => self.cont_fail(expr.span, *fail_expr),
649 ExprKind::Field(expr, field) => self.cont_field(*expr, field),
650 ExprKind::Hole => panic!("hole expr should be disallowed by passes"),
651 ExprKind::If(cond_expr, then_expr, else_expr) => {
652 self.cont_if(*cond_expr, *then_expr, *else_expr);
653 }
654 ExprKind::Index(arr, index) => self.cont_index(globals, *arr, *index),
655 ExprKind::Lit(lit) => self.push_val(lit_to_val(lit)),
656 ExprKind::Range(start, step, end) => self.cont_range(*start, *step, *end),
657 ExprKind::Return(expr) => self.cont_ret(*expr),
658 ExprKind::String(components) => self.cont_string(components),
659 ExprKind::UpdateIndex(lhs, mid, rhs) => self.update_index(globals, *lhs, *mid, *rhs),
660 ExprKind::Tuple(tup) => self.cont_tup(tup),
661 ExprKind::UnOp(op, expr) => self.cont_unop(*op, *expr),
662 ExprKind::UpdateField(record, field, replace) => {
663 self.cont_update_field(*record, field, *replace);
664 }
665 ExprKind::Var(res, _) => {
666 self.push_val(resolve_binding(env, self.package, *res, expr.span)?);
667 }
668 ExprKind::While(cond_expr, block) => self.cont_while(*cond_expr, *block),
669 }
670
671 Ok(())
672 }
673
674 fn cont_tup(&mut self, tup: &Vec<ExprId>) {
675 self.push_action(Action::Tuple(tup.len()));
676 self.push_exprs(tup);
677 }
678
679 fn cont_arr(&mut self, arr: &Vec<ExprId>) {
680 self.push_action(Action::Array(arr.len()));
681 self.push_exprs(arr);
682 }
683
684 fn cont_arr_repeat(&mut self, globals: &impl PackageStoreLookup, item: ExprId, size: ExprId) {
685 let size_expr = globals.get_expr((self.package, size).into());
686 self.push_action(Action::ArrayRepeat(size_expr.span));
687 self.push_expr(size);
688 self.push_expr(item);
689 }
690
691 fn cont_ret(&mut self, expr: ExprId) {
692 self.push_action(Action::Return);
693 self.push_expr(expr);
694 }
695
696 fn cont_if(&mut self, cond_expr: ExprId, then_expr: ExprId, else_expr: Option<ExprId>) {
697 self.push_action(Action::If(then_expr, else_expr));
698 self.push_expr(cond_expr);
699 }
700
701 fn cont_fail(&mut self, span: Span, fail_expr: ExprId) {
702 self.push_action(Action::Fail(span));
703 self.push_expr(fail_expr);
704 }
705
706 fn cont_assign(&mut self, lhs: ExprId, rhs: ExprId) {
707 self.push_action(Action::Assign(lhs));
708 self.push_expr(rhs);
709 self.push_val(Value::unit());
710 }
711
712 fn cont_assign_op(
713 &mut self,
714 globals: &impl PackageStoreLookup,
715 op: BinOp,
716 lhs: ExprId,
717 rhs: ExprId,
718 ) {
719 // If we know the assign op is an array append, as in `set arr += other;`, we should perform it in-place.
720 if op == BinOp::Add
721 && matches!(
722 globals.get_expr((self.package, lhs).into()).ty,
723 Ty::Array(_)
724 )
725 {
726 self.push_action(Action::ArrayAppendInPlace(lhs));
727 self.push_expr(rhs);
728 self.push_val(Value::unit());
729 return;
730 }
731
732 self.push_action(Action::Assign(lhs));
733 self.cont_binop(globals, op, rhs, lhs);
734 self.push_val(Value::unit());
735 }
736
737 fn cont_assign_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
738 self.push_action(Action::Assign(record));
739 self.cont_update_field(record, field, replace);
740 self.push_val(Value::unit());
741 }
742
743 fn cont_assign_index(
744 &mut self,
745 globals: &impl PackageStoreLookup,
746 lhs: ExprId,
747 mid: ExprId,
748 rhs: ExprId,
749 ) {
750 let span = globals.get_expr((self.package, mid).into()).span;
751 self.push_action(Action::UpdateIndexInPlace(lhs, span));
752 self.push_expr(rhs);
753 self.push_expr(mid);
754 self.push_val(Value::unit());
755 }
756
757 fn cont_field(&mut self, expr: ExprId, field: &Field) {
758 self.push_action(Action::Field(field.clone()));
759 self.push_expr(expr);
760 }
761
762 fn cont_index(&mut self, globals: &impl PackageStoreLookup, arr: ExprId, index: ExprId) {
763 let index_expr = globals.get_expr((self.package, index).into());
764 self.push_action(Action::Index(index_expr.span));
765 self.push_expr(index);
766 self.push_expr(arr);
767 }
768
769 fn cont_range(&mut self, start: Option<ExprId>, step: Option<ExprId>, end: Option<ExprId>) {
770 self.push_action(Action::Range(
771 start.is_some(),
772 step.is_some(),
773 end.is_some(),
774 ));
775 if let Some(end) = end {
776 self.push_expr(end);
777 }
778 if let Some(step) = step {
779 self.push_expr(step);
780 }
781 if let Some(start) = start {
782 self.push_expr(start);
783 }
784 }
785
786 fn cont_string(&mut self, components: &[StringComponent]) {
787 if let [StringComponent::Lit(str)] = components {
788 self.push_val(Value::String(Rc::clone(str)));
789 return;
790 }
791
792 self.push_action(Action::StringConcat(components.len()));
793 for component in components.iter().rev() {
794 match component {
795 StringComponent::Expr(expr) => self.push_expr(*expr),
796 StringComponent::Lit(lit) => self.push_action(Action::StringLit(lit.clone())),
797 }
798 }
799 }
800
801 fn cont_while(&mut self, cond_expr: ExprId, block: BlockId) {
802 self.push_action(Action::While(cond_expr, block));
803 self.push_expr(cond_expr);
804 }
805
806 fn cont_call(&mut self, globals: &impl PackageStoreLookup, callee: ExprId, args: ExprId) {
807 let callee_expr = globals.get_expr((self.package, callee).into());
808 let args_expr = globals.get_expr((self.package, args).into());
809 self.push_action(Action::Call(callee_expr.span, args_expr.span));
810 self.push_expr(args);
811 self.push_expr(callee);
812 }
813
814 fn cont_binop(
815 &mut self,
816 globals: &impl PackageStoreLookup,
817 op: BinOp,
818 rhs: ExprId,
819 lhs: ExprId,
820 ) {
821 let rhs_expr = globals.get_expr((self.package, rhs).into());
822 match op {
823 BinOp::Add
824 | BinOp::AndB
825 | BinOp::Div
826 | BinOp::Eq
827 | BinOp::Exp
828 | BinOp::Gt
829 | BinOp::Gte
830 | BinOp::Lt
831 | BinOp::Lte
832 | BinOp::Mod
833 | BinOp::Mul
834 | BinOp::Neq
835 | BinOp::OrB
836 | BinOp::Shl
837 | BinOp::Shr
838 | BinOp::Sub
839 | BinOp::XorB => {
840 self.push_action(Action::BinOp(op, rhs_expr.span, None));
841 self.push_expr(rhs);
842 self.push_expr(lhs);
843 }
844 BinOp::AndL | BinOp::OrL => {
845 self.push_action(Action::BinOp(op, rhs_expr.span, Some(rhs)));
846 self.push_expr(lhs);
847 }
848 }
849 }
850
851 fn update_index(
852 &mut self,
853 globals: &impl PackageStoreLookup,
854 lhs: ExprId,
855 mid: ExprId,
856 rhs: ExprId,
857 ) {
858 let span = globals.get_expr((self.package, mid).into()).span;
859 self.push_action(Action::UpdateIndex(span));
860 self.push_expr(lhs);
861 self.push_expr(rhs);
862 self.push_expr(mid);
863 }
864
865 fn cont_unop(&mut self, op: UnOp, expr: ExprId) {
866 self.push_action(Action::UnOp(op));
867 self.push_expr(expr);
868 }
869
870 fn cont_update_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
871 self.push_action(Action::UpdateField(field.clone()));
872 self.push_expr(replace);
873 self.push_expr(record);
874 }
875
876 fn cont_stmt(&mut self, globals: &impl PackageStoreLookup, stmt: StmtId) {
877 let stmt = globals.get_stmt((self.package, stmt).into());
878 self.current_span = stmt.span;
879
880 match &stmt.kind {
881 StmtKind::Expr(expr) => self.push_expr(*expr),
882 StmtKind::Item(..) => self.push_val(Value::unit()),
883 StmtKind::Local(mutability, pat, expr) => {
884 self.push_action(Action::Bind(*pat, *mutability));
885 self.push_expr(*expr);
886 self.push_val(Value::unit());
887 }
888 StmtKind::Semi(expr) => {
889 self.push_action(Action::Consume);
890 self.push_expr(*expr);
891 self.push_val(Value::unit());
892 }
893 }
894 }
895
896 fn cont_action(
897 &mut self,
898 env: &mut Env,
899 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
900 globals: &impl PackageStoreLookup,
901 action: Action,
902 out: &mut impl Receiver,
903 ) -> Result<(), Error> {
904 match action {
905 Action::Array(len) => self.eval_arr(len),
906 Action::ArrayAppendInPlace(lhs) => {
907 self.eval_array_append_in_place(env, globals, lhs)?;
908 }
909 Action::ArrayRepeat(span) => self.eval_arr_repeat(span)?,
910 Action::Assign(lhs) => self.eval_assign(env, globals, lhs)?,
911 Action::BinOp(op, span, rhs) => self.eval_binop(op, span, rhs)?,
912 Action::Bind(pat, mutability) => self.eval_bind(env, globals, pat, mutability),
913 Action::Call(callee_span, args_span) => {
914 self.eval_call(env, sim, globals, callee_span, args_span, out)?;
915 }
916 Action::Consume => {
917 self.pop_val();
918 }
919 Action::Fail(span) => {
920 return Err(Error::UserFail(
921 self.pop_val().unwrap_string().to_string(),
922 self.to_global_span(span),
923 ));
924 }
925 Action::Field(field) => self.eval_field(field),
926 Action::If(then_expr, else_expr) => self.eval_if(then_expr, else_expr),
927 Action::Index(span) => self.eval_index(span)?,
928 Action::Range(has_start, has_step, has_end) => {
929 self.eval_range(has_start, has_step, has_end);
930 }
931 Action::Return => self.eval_ret(env),
932 Action::StringConcat(len) => self.eval_string_concat(len),
933 Action::StringLit(str) => self.push_val(Value::String(str)),
934 Action::UpdateIndex(span) => self.eval_update_index(span)?,
935 Action::UpdateIndexInPlace(lhs, span) => {
936 self.eval_update_index_in_place(env, globals, lhs, span)?;
937 }
938 Action::Tuple(len) => self.eval_tup(len),
939 Action::UnOp(op) => self.eval_unop(op),
940 Action::UpdateField(field) => self.eval_update_field(field),
941 Action::While(cond_expr, block) => self.eval_while(env, globals, cond_expr, block),
942 }
943 Ok(())
944 }
945
946 fn eval_arr(&mut self, len: usize) {
947 let arr = self.pop_vals(len);
948 self.push_val(Value::Array(arr.into()));
949 }
950
951 fn eval_array_append_in_place(
952 &mut self,
953 env: &mut Env,
954 globals: &impl PackageStoreLookup,
955 lhs: ExprId,
956 ) -> Result<(), Error> {
957 let lhs = globals.get_expr((self.package, lhs).into());
958 let rhs = self.pop_val();
959 match (&lhs.kind, rhs) {
960 (&ExprKind::Var(Res::Local(node), _), rhs) => match env.get_mut(node) {
961 Some(var) if var.is_mutable() => {
962 var.value.append_array(rhs);
963 }
964 Some(_) => {
965 unreachable!("update of mutable variable should be disallowed by compiler")
966 }
967 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
968 },
969 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
970 }
971 Ok(())
972 }
973
974 fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> {
975 let size_val = self.pop_val().unwrap_int();
976 let item_val = self.pop_val();
977 let s = match size_val.try_into() {
978 Ok(i) => Ok(i),
979 Err(_) => Err(Error::InvalidArrayLength(
980 size_val,
981 self.to_global_span(span),
982 )),
983 }?;
984 self.push_val(Value::Array(vec![item_val; s].into()));
985 Ok(())
986 }
987
988 fn eval_assign(
989 &mut self,
990 env: &mut Env,
991 globals: &impl PackageStoreLookup,
992 lhs: ExprId,
993 ) -> Result<(), Error> {
994 let rhs = self.pop_val();
995 self.update_binding(env, globals, lhs, rhs)
996 }
997
998 fn eval_bind(
999 &mut self,
1000 env: &mut Env,
1001 globals: &impl PackageStoreLookup,
1002 pat: PatId,
1003 mutability: Mutability,
1004 ) {
1005 let val = self.pop_val();
1006 self.bind_value(env, globals, pat, val, mutability);
1007 }
1008
1009 fn eval_binop(&mut self, op: BinOp, span: Span, rhs: Option<ExprId>) -> Result<(), Error> {
1010 match op {
1011 BinOp::Add => self.eval_binop_simple(eval_binop_add),
1012 BinOp::AndB => self.eval_binop_simple(eval_binop_andb),
1013 BinOp::AndL => {
1014 if self.pop_val().unwrap_bool() {
1015 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
1016 } else {
1017 self.push_val(Value::Bool(false));
1018 }
1019 }
1020 BinOp::Div => self.eval_binop_with_error(span, eval_binop_div)?,
1021 BinOp::Eq => {
1022 let rhs_val = self.pop_val();
1023 let lhs_val = self.pop_val();
1024 self.push_val(Value::Bool(lhs_val == rhs_val));
1025 }
1026 BinOp::Exp => self.eval_binop_with_error(span, eval_binop_exp)?,
1027 BinOp::Gt => self.eval_binop_simple(eval_binop_gt),
1028 BinOp::Gte => self.eval_binop_simple(eval_binop_gte),
1029 BinOp::Lt => self.eval_binop_simple(eval_binop_lt),
1030 BinOp::Lte => self.eval_binop_simple(eval_binop_lte),
1031 BinOp::Mod => self.eval_binop_with_error(span, eval_binop_mod)?,
1032 BinOp::Mul => self.eval_binop_simple(eval_binop_mul),
1033 BinOp::Neq => {
1034 let rhs_val = self.pop_val();
1035 let lhs_val = self.pop_val();
1036 self.push_val(Value::Bool(lhs_val != rhs_val));
1037 }
1038 BinOp::OrB => self.eval_binop_simple(eval_binop_orb),
1039 BinOp::OrL => {
1040 if self.pop_val().unwrap_bool() {
1041 self.push_val(Value::Bool(true));
1042 } else {
1043 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
1044 }
1045 }
1046 BinOp::Shl => self.eval_binop_with_error(span, eval_binop_shl)?,
1047 BinOp::Shr => self.eval_binop_with_error(span, eval_binop_shr)?,
1048 BinOp::Sub => self.eval_binop_simple(eval_binop_sub),
1049 BinOp::XorB => self.eval_binop_simple(eval_binop_xorb),
1050 }
1051 Ok(())
1052 }
1053
1054 fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) {
1055 let rhs_val = self.pop_val();
1056 let lhs_val = self.pop_val();
1057 self.push_val(binop_func(lhs_val, rhs_val));
1058 }
1059
1060 fn eval_binop_with_error(
1061 &mut self,
1062 span: Span,
1063 binop_func: impl FnOnce(Value, Value, PackageSpan) -> Result<Value, Error>,
1064 ) -> Result<(), Error> {
1065 let span = self.to_global_span(span);
1066 let rhs_val = self.pop_val();
1067 let lhs_val = self.pop_val();
1068 self.push_val(binop_func(lhs_val, rhs_val, span)?);
1069 Ok(())
1070 }
1071
1072 fn eval_call(
1073 &mut self,
1074 env: &mut Env,
1075 sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
1076 globals: &impl PackageStoreLookup,
1077 callee_span: Span,
1078 arg_span: Span,
1079 out: &mut impl Receiver,
1080 ) -> Result<(), Error> {
1081 let arg = self.pop_val();
1082 let (callee_id, functor, fixed_args) = match self.pop_val() {
1083 Value::Closure(fixed_args, id, functor) => (id, functor, Some(fixed_args)),
1084 Value::Global(id, functor) => (id, functor, None),
1085 _ => panic!("value is not callable"),
1086 };
1087
1088 let callee_span = self.to_global_span(callee_span);
1089 let arg_span = self.to_global_span(arg_span);
1090
1091 let callee = match globals.get_global(callee_id) {
1092 Some(Global::Callable(callable)) => callable,
1093 Some(Global::Udt) => {
1094 self.push_val(arg);
1095 return Ok(());
1096 }
1097 None => return Err(Error::UnboundName(callee_span)),
1098 };
1099
1100 let spec = spec_from_functor_app(functor);
1101 self.push_frame(callee_id, functor);
1102 self.push_scope(env);
1103 match &callee.implementation {
1104 CallableImpl::Intrinsic => {
1105 let name = &callee.name.name;
1106 let val = intrinsic::call(
1107 name,
1108 callee_span,
1109 arg,
1110 arg_span,
1111 sim,
1112 &mut self.rng.borrow_mut(),
1113 out,
1114 )?;
1115 self.push_val(val);
1116 Ok(())
1117 }
1118 CallableImpl::Spec(specialized_implementation) => {
1119 let spec_decl = match spec {
1120 Spec::Body => Some(&specialized_implementation.body),
1121 Spec::Adj => specialized_implementation.adj.as_ref(),
1122 Spec::Ctl => specialized_implementation.ctl.as_ref(),
1123 Spec::CtlAdj => specialized_implementation.ctl_adj.as_ref(),
1124 }
1125 .ok_or(Error::MissingSpec(spec.to_string(), callee_span))?;
1126 self.bind_args_for_spec(
1127 env,
1128 globals,
1129 callee.input,
1130 spec_decl.input,
1131 arg,
1132 functor.controlled,
1133 fixed_args,
1134 );
1135 self.push_block(env, globals, spec_decl.block);
1136 Ok(())
1137 }
1138 }
1139 }
1140
1141 fn eval_field(&mut self, field: Field) {
1142 let record = self.pop_val();
1143 let val = match (record, field) {
1144 (Value::Range(Some(start), _, _), Field::Prim(PrimField::Start)) => Value::Int(start),
1145 (Value::Range(_, step, _), Field::Prim(PrimField::Step)) => Value::Int(step),
1146 (Value::Range(_, _, Some(end)), Field::Prim(PrimField::End)) => Value::Int(end),
1147 (record, Field::Path(path)) => {
1148 follow_field_path(record, &path.indices).expect("field path should be valid")
1149 }
1150 _ => panic!("invalid field access"),
1151 };
1152 self.push_val(val);
1153 }
1154
1155 fn eval_if(&mut self, then_expr: ExprId, else_expr: Option<ExprId>) {
1156 if self.pop_val().unwrap_bool() {
1157 self.push_expr(then_expr);
1158 } else if let Some(else_expr) = else_expr {
1159 self.push_expr(else_expr);
1160 } else {
1161 self.push_val(Value::unit());
1162 }
1163 }
1164
1165 fn eval_index(&mut self, span: Span) -> Result<(), Error> {
1166 let index_val = self.pop_val();
1167 let arr = self.pop_val().unwrap_array();
1168 match &index_val {
1169 Value::Int(i) => self.push_val(index_array(&arr, *i, self.to_global_span(span))?),
1170 &Value::Range(start, step, end) => {
1171 self.push_val(slice_array(
1172 &arr,
1173 start,
1174 step,
1175 end,
1176 self.to_global_span(span),
1177 )?);
1178 }
1179 _ => panic!("array should only be indexed by Int or Range"),
1180 }
1181 Ok(())
1182 }
1183
1184 fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) {
1185 let end = if has_end {
1186 Some(self.pop_val().unwrap_int())
1187 } else {
1188 None
1189 };
1190 let step = if has_step {
1191 self.pop_val().unwrap_int()
1192 } else {
1193 val::DEFAULT_RANGE_STEP
1194 };
1195 let start = if has_start {
1196 Some(self.pop_val().unwrap_int())
1197 } else {
1198 None
1199 };
1200 self.push_val(Value::Range(start, step, end));
1201 }
1202
1203 fn eval_ret(&mut self, env: &mut Env) {
1204 while let Some(cont) = self.pop_cont() {
1205 match cont {
1206 Cont::Frame(len) => {
1207 self.leave_frame(len);
1208 break;
1209 }
1210 Cont::Scope => env.leave_scope(),
1211 Cont::Action => {
1212 self.action_stack.pop();
1213 }
1214 _ => {}
1215 }
1216 }
1217 }
1218
1219 fn eval_string_concat(&mut self, len: usize) {
1220 let mut string = String::new();
1221 for component in self.pop_vals(len) {
1222 write!(string, "{component}").expect("string should be writable");
1223 }
1224 self.push_val(Value::String(string.into()));
1225 }
1226
1227 fn eval_update_index(&mut self, span: Span) -> Result<(), Error> {
1228 let values = self.pop_val().unwrap_array();
1229 let update = self.pop_val();
1230 let index = self.pop_val();
1231 let span = self.to_global_span(span);
1232 match index {
1233 Value::Int(index) => self.eval_update_index_single(&values, index, update, span),
1234 Value::Range(start, step, end) => {
1235 self.eval_update_index_range(&values, start, step, end, update, span)
1236 }
1237 _ => unreachable!("array should only be indexed by Int or Range"),
1238 }
1239 }
1240
1241 fn eval_update_index_single(
1242 &mut self,
1243 values: &[Value],
1244 index: i64,
1245 update: Value,
1246 span: PackageSpan,
1247 ) -> Result<(), Error> {
1248 if index < 0 {
1249 return Err(Error::InvalidNegativeInt(index, span));
1250 }
1251 let i = index.as_index(span)?;
1252 let mut values = values.to_vec();
1253 match values.get_mut(i) {
1254 Some(value) => {
1255 *value = update;
1256 }
1257 None => return Err(Error::IndexOutOfRange(index, span)),
1258 }
1259 self.push_val(Value::Array(values.into()));
1260 Ok(())
1261 }
1262
1263 fn eval_update_index_range(
1264 &mut self,
1265 values: &[Value],
1266 start: Option<i64>,
1267 step: i64,
1268 end: Option<i64>,
1269 update: Value,
1270 span: PackageSpan,
1271 ) -> Result<(), Error> {
1272 let range = make_range(values, start, step, end, span)?;
1273 let mut values = values.to_vec();
1274 let update = update.unwrap_array();
1275 for (idx, update) in range.into_iter().zip(update.iter()) {
1276 let i = idx.as_index(span)?;
1277 match values.get_mut(i) {
1278 Some(value) => {
1279 *value = update.clone();
1280 }
1281 None => return Err(Error::IndexOutOfRange(idx, span)),
1282 }
1283 }
1284 self.push_val(Value::Array(values.into()));
1285 Ok(())
1286 }
1287
1288 fn eval_update_index_in_place(
1289 &mut self,
1290 env: &mut Env,
1291 globals: &impl PackageStoreLookup,
1292 lhs: ExprId,
1293 span: Span,
1294 ) -> Result<(), Error> {
1295 let update = self.pop_val();
1296 let index = self.pop_val();
1297 let span = self.to_global_span(span);
1298 match index {
1299 Value::Int(index) => {
1300 if index < 0 {
1301 return Err(Error::InvalidNegativeInt(index, span));
1302 }
1303 let i = index.as_index(span)?;
1304 self.update_array_index_single(env, globals, lhs, span, i, update)
1305 }
1306 range @ Value::Range(..) => {
1307 self.update_array_index_range(env, globals, lhs, span, &range, update)
1308 }
1309 _ => unreachable!("array should only be indexed by Int or Range"),
1310 }
1311 }
1312
1313 fn eval_tup(&mut self, len: usize) {
1314 let tup = self.pop_vals(len);
1315 self.push_val(Value::Tuple(tup.into()));
1316 }
1317
1318 fn eval_unop(&mut self, op: UnOp) {
1319 let val = self.pop_val();
1320 match op {
1321 UnOp::Functor(functor) => match val {
1322 Value::Closure(args, id, app) => {
1323 self.push_val(Value::Closure(args, id, update_functor_app(functor, app)));
1324 }
1325 Value::Global(id, app) => {
1326 self.push_val(Value::Global(id, update_functor_app(functor, app)));
1327 }
1328 _ => panic!("value should be callable"),
1329 },
1330 UnOp::Neg => match val {
1331 Value::BigInt(v) => self.push_val(Value::BigInt(v.neg())),
1332 Value::Double(v) => self.push_val(Value::Double(v.neg())),
1333 Value::Int(v) => self.push_val(Value::Int(v.wrapping_neg())),
1334 _ => panic!("value should be number"),
1335 },
1336 UnOp::NotB => match val {
1337 Value::Int(v) => self.push_val(Value::Int(!v)),
1338 Value::BigInt(v) => self.push_val(Value::BigInt(!v)),
1339 _ => panic!("value should be Int or BigInt"),
1340 },
1341 UnOp::NotL => match val {
1342 Value::Bool(b) => self.push_val(Value::Bool(!b)),
1343 _ => panic!("value should be bool"),
1344 },
1345 UnOp::Pos => match val {
1346 Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.push_val(val),
1347 _ => panic!("value should be number"),
1348 },
1349 UnOp::Unwrap => self.push_val(val),
1350 }
1351 }
1352
1353 fn eval_update_field(&mut self, field: Field) {
1354 let value = self.pop_val();
1355 let record = self.pop_val();
1356 let update = match (record, field) {
1357 (Value::Range(_, step, end), Field::Prim(PrimField::Start)) => {
1358 Value::Range(Some(value.unwrap_int()), step, end)
1359 }
1360 (Value::Range(start, _, end), Field::Prim(PrimField::Step)) => {
1361 Value::Range(start, value.unwrap_int(), end)
1362 }
1363 (Value::Range(start, step, _), Field::Prim(PrimField::End)) => {
1364 Value::Range(start, step, Some(value.unwrap_int()))
1365 }
1366 (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value)
1367 .expect("field path should be valid"),
1368 _ => panic!("invalid field access"),
1369 };
1370 self.push_val(update);
1371 }
1372
1373 fn eval_while(
1374 &mut self,
1375 env: &mut Env,
1376 globals: &impl PackageStoreLookup,
1377 cond_expr: ExprId,
1378 block: BlockId,
1379 ) {
1380 if self.pop_val().unwrap_bool() {
1381 self.cont_while(cond_expr, block);
1382 self.push_action(Action::Consume);
1383 self.push_val(Value::unit());
1384 self.push_block(env, globals, block);
1385 } else {
1386 self.push_val(Value::unit());
1387 }
1388 }
1389
1390 fn bind_value(
1391 &self,
1392 env: &mut Env,
1393 globals: &impl PackageStoreLookup,
1394 pat: PatId,
1395 val: Value,
1396 mutability: Mutability,
1397 ) {
1398 let pat = globals.get_pat((self.package, pat).into());
1399 match &pat.kind {
1400 PatKind::Bind(variable) => {
1401 let scope = env.0.last_mut().expect("binding should have a scope");
1402 match scope.bindings.entry(variable.id) {
1403 Entry::Vacant(entry) => entry.insert(Variable {
1404 name: variable.name.clone(),
1405 value: val,
1406 mutability,
1407 span: variable.span,
1408 }),
1409 Entry::Occupied(_) => panic!("duplicate binding"),
1410 };
1411 }
1412 PatKind::Discard => {}
1413 PatKind::Tuple(tup) => {
1414 let val_tup = val.unwrap_tuple();
1415 for (pat, val) in tup.iter().zip(val_tup.iter()) {
1416 self.bind_value(env, globals, *pat, val.clone(), mutability);
1417 }
1418 }
1419 }
1420 }
1421
1422 #[allow(clippy::similar_names)]
1423 fn update_binding(
1424 &self,
1425 env: &mut Env,
1426 globals: &impl PackageStoreLookup,
1427 lhs: ExprId,
1428 rhs: Value,
1429 ) -> Result<(), Error> {
1430 let lhs = globals.get_expr((self.package, lhs).into());
1431 match (&lhs.kind, rhs) {
1432 (ExprKind::Hole, _) => {}
1433 (&ExprKind::Var(Res::Local(node), _), rhs) => match env.get_mut(node) {
1434 Some(var) if var.is_mutable() => {
1435 var.value = rhs;
1436 }
1437 Some(_) => {
1438 unreachable!("update of mutable variable should be disallowed by compiler")
1439 }
1440 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1441 },
1442 (ExprKind::Tuple(var_tup), Value::Tuple(tup)) => {
1443 for (expr, val) in var_tup.iter().zip(tup.iter()) {
1444 self.update_binding(env, globals, *expr, val.clone())?;
1445 }
1446 }
1447 _ => unreachable!("unassignable pattern should be disallowed by compiler"),
1448 }
1449 Ok(())
1450 }
1451
1452 fn update_array_index_single(
1453 &self,
1454 env: &mut Env,
1455 globals: &impl PackageStoreLookup,
1456 lhs: ExprId,
1457 span: PackageSpan,
1458 index: usize,
1459 rhs: Value,
1460 ) -> Result<(), Error> {
1461 let lhs = globals.get_expr((self.package, lhs).into());
1462 match &lhs.kind {
1463 &ExprKind::Var(Res::Local(node), _) => match env.get_mut(node) {
1464 Some(var) if var.is_mutable() => {
1465 var.value.update_array(index, rhs).map_err(|idx| {
1466 Error::IndexOutOfRange(idx.try_into().expect("index should be valid"), span)
1467 })?;
1468 }
1469 Some(_) => {
1470 unreachable!("update of immutable variable should be disallowed by compiler")
1471 }
1472 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1473 },
1474 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1475 }
1476 Ok(())
1477 }
1478
1479 #[allow(clippy::similar_names)] // `env` and `end` are similar but distinct
1480 fn update_array_index_range(
1481 &self,
1482 env: &mut Env,
1483 globals: &impl PackageStoreLookup,
1484 lhs: ExprId,
1485 range_span: PackageSpan,
1486 range: &Value,
1487 update: Value,
1488 ) -> Result<(), Error> {
1489 let lhs = globals.get_expr((self.package, lhs).into());
1490 match &lhs.kind {
1491 &ExprKind::Var(Res::Local(node), _) => match env.get_mut(node) {
1492 Some(var) if var.is_mutable() => {
1493 let rhs = update.unwrap_array();
1494 let Value::Array(arr) = &mut var.value else {
1495 panic!("variable should be an array");
1496 };
1497 let Value::Range(start, step, end) = range else {
1498 unreachable!("range should be a Value::Range");
1499 };
1500 let range = make_range(arr, *start, *step, *end, range_span)?;
1501 for (idx, rhs) in range.into_iter().zip(rhs.iter()) {
1502 if idx < 0 {
1503 return Err(Error::InvalidNegativeInt(idx, range_span));
1504 }
1505 let i = idx.as_index(range_span)?;
1506 var.value.update_array(i, rhs.clone()).map_err(|idx| {
1507 Error::IndexOutOfRange(
1508 idx.try_into().expect("index should be valid"),
1509 range_span,
1510 )
1511 })?;
1512 }
1513 }
1514 Some(_) => {
1515 unreachable!("update of mutable variable should be disallowed by compiler")
1516 }
1517 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1518 },
1519 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1520 }
1521 Ok(())
1522 }
1523
1524 #[allow(clippy::too_many_arguments)]
1525 fn bind_args_for_spec(
1526 &self,
1527 env: &mut Env,
1528 globals: &impl PackageStoreLookup,
1529 decl_pat: PatId,
1530 spec_pat: Option<PatId>,
1531 args_val: Value,
1532 ctl_count: u8,
1533 fixed_args: Option<Rc<[Value]>>,
1534 ) {
1535 match spec_pat {
1536 Some(spec_pat) => {
1537 assert!(
1538 ctl_count > 0,
1539 "spec pattern tuple used without controlled functor"
1540 );
1541
1542 let mut tup = args_val;
1543 let mut ctls = vec![];
1544 for _ in 0..ctl_count {
1545 let [c, rest] = &*tup.unwrap_tuple() else {
1546 panic!("tuple should be arity 2");
1547 };
1548 ctls.extend_from_slice(&c.clone().unwrap_array());
1549 tup = rest.clone();
1550 }
1551
1552 self.bind_value(
1553 env,
1554 globals,
1555 spec_pat,
1556 Value::Array(ctls.into()),
1557 Mutability::Immutable,
1558 );
1559 self.bind_value(
1560 env,
1561 globals,
1562 decl_pat,
1563 merge_fixed_args(fixed_args, tup),
1564 Mutability::Immutable,
1565 );
1566 }
1567 None => self.bind_value(
1568 env,
1569 globals,
1570 decl_pat,
1571 merge_fixed_args(fixed_args, args_val),
1572 Mutability::Immutable,
1573 ),
1574 }
1575 }
1576
1577 fn to_global_span(&self, span: Span) -> PackageSpan {
1578 PackageSpan {
1579 package: map_fir_package_to_hir(self.package),
1580 span,
1581 }
1582 }
1583}
1584
1585fn merge_fixed_args(fixed_args: Option<Rc<[Value]>>, arg: Value) -> Value {
1586 if let Some(fixed_args) = fixed_args {
1587 Value::Tuple(fixed_args.iter().cloned().chain(iter::once(arg)).collect())
1588 } else {
1589 arg
1590 }
1591}
1592
1593fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result<Value, Error> {
1594 Ok(match res {
1595 Res::Err => panic!("resolution error"),
1596 Res::Item(item) => Value::Global(
1597 StoreItemId {
1598 package: item.package.unwrap_or(package),
1599 item: item.item,
1600 },
1601 FunctorApp::default(),
1602 ),
1603 Res::Local(node) => env
1604 .get(node)
1605 .ok_or(Error::UnboundName(PackageSpan {
1606 package: map_fir_package_to_hir(package),
1607 span,
1608 }))?
1609 .value
1610 .clone(),
1611 })
1612}
1613
1614fn spec_from_functor_app(functor: FunctorApp) -> Spec {
1615 match (functor.adjoint, functor.controlled) {
1616 (false, 0) => Spec::Body,
1617 (true, 0) => Spec::Adj,
1618 (false, _) => Spec::Ctl,
1619 (true, _) => Spec::CtlAdj,
1620 }
1621}
1622
1623fn resolve_closure(
1624 env: &Env,
1625 package: PackageId,
1626 span: Span,
1627 args: &[NodeId],
1628 callable: LocalItemId,
1629) -> Result<Value, Error> {
1630 let args: Option<_> = args
1631 .iter()
1632 .map(|&arg| Some(env.get(arg)?.value.clone()))
1633 .collect();
1634 let args: Vec<_> = args.ok_or(Error::UnboundName(PackageSpan {
1635 package: map_fir_package_to_hir(package),
1636 span,
1637 }))?;
1638 let callable = StoreItemId {
1639 package,
1640 item: callable,
1641 };
1642 Ok(Value::Closure(args.into(), callable, FunctorApp::default()))
1643}
1644
1645fn lit_to_val(lit: &Lit) -> Value {
1646 match lit {
1647 Lit::BigInt(v) => Value::BigInt(v.clone()),
1648 Lit::Bool(v) => Value::Bool(*v),
1649 Lit::Double(v) => Value::Double(*v),
1650 Lit::Int(v) => Value::Int(*v),
1651 Lit::Pauli(v) => Value::Pauli(*v),
1652 Lit::Result(fir::Result::Zero) => Value::RESULT_ZERO,
1653 Lit::Result(fir::Result::One) => Value::RESULT_ONE,
1654 }
1655}
1656
1657fn index_array(arr: &[Value], index: i64, span: PackageSpan) -> Result<Value, Error> {
1658 let i = index.as_index(span)?;
1659 match arr.get(i) {
1660 Some(v) => Ok(v.clone()),
1661 None => Err(Error::IndexOutOfRange(index, span)),
1662 }
1663}
1664
1665fn slice_array(
1666 arr: &[Value],
1667 start: Option<i64>,
1668 step: i64,
1669 end: Option<i64>,
1670 span: PackageSpan,
1671) -> Result<Value, Error> {
1672 let range = make_range(arr, start, step, end, span)?;
1673 let mut slice = vec![];
1674 for i in range {
1675 slice.push(index_array(arr, i, span)?);
1676 }
1677
1678 Ok(Value::Array(slice.into()))
1679}
1680
1681fn make_range(
1682 arr: &[Value],
1683 start: Option<i64>,
1684 step: i64,
1685 end: Option<i64>,
1686 span: PackageSpan,
1687) -> Result<Range, Error> {
1688 if step == 0 {
1689 Err(Error::RangeStepZero(span))
1690 } else {
1691 let len: i64 = match arr.len().try_into() {
1692 Ok(len) => Ok(len),
1693 Err(_) => Err(Error::ArrayTooLarge(span)),
1694 }?;
1695 let (start, end) = if step > 0 {
1696 (start.unwrap_or(0), end.unwrap_or(len - 1))
1697 } else {
1698 (start.unwrap_or(len - 1), end.unwrap_or(0))
1699 };
1700 Ok(Range::new(start, step, end))
1701 }
1702}
1703
1704fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value {
1705 match lhs_val {
1706 Value::Array(arr) => {
1707 let rhs_arr = rhs_val.unwrap_array();
1708 let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect();
1709 Value::Array(items.into())
1710 }
1711 Value::BigInt(val) => {
1712 let rhs = rhs_val.unwrap_big_int();
1713 Value::BigInt(val + rhs)
1714 }
1715 Value::Double(val) => {
1716 let rhs = rhs_val.unwrap_double();
1717 Value::Double(val + rhs)
1718 }
1719 Value::Int(val) => {
1720 let rhs = rhs_val.unwrap_int();
1721 Value::Int(val.wrapping_add(rhs))
1722 }
1723 Value::String(val) => {
1724 let rhs = rhs_val.unwrap_string();
1725 Value::String((val.to_string() + &rhs).into())
1726 }
1727 _ => panic!("value is not addable"),
1728 }
1729}
1730
1731fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value {
1732 match lhs_val {
1733 Value::BigInt(val) => {
1734 let rhs = rhs_val.unwrap_big_int();
1735 Value::BigInt(val & rhs)
1736 }
1737 Value::Int(val) => {
1738 let rhs = rhs_val.unwrap_int();
1739 Value::Int(val & rhs)
1740 }
1741 _ => panic!("value type does not support andb"),
1742 }
1743}
1744
1745fn eval_binop_div(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1746 match lhs_val {
1747 Value::BigInt(val) => {
1748 let rhs = rhs_val.unwrap_big_int();
1749 if rhs == BigInt::from(0) {
1750 Err(Error::DivZero(rhs_span))
1751 } else {
1752 Ok(Value::BigInt(val / rhs))
1753 }
1754 }
1755 Value::Int(val) => {
1756 let rhs = rhs_val.unwrap_int();
1757 if rhs == 0 {
1758 Err(Error::DivZero(rhs_span))
1759 } else {
1760 Ok(Value::Int(val.wrapping_div(rhs)))
1761 }
1762 }
1763 Value::Double(val) => {
1764 let rhs = rhs_val.unwrap_double();
1765 Ok(Value::Double(val / rhs))
1766 }
1767 _ => panic!("value should support div"),
1768 }
1769}
1770
1771fn eval_binop_exp(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1772 match lhs_val {
1773 Value::BigInt(val) => {
1774 let rhs_val = rhs_val.unwrap_int();
1775 if rhs_val < 0 {
1776 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1777 } else {
1778 let rhs_val: u32 = match rhs_val.try_into() {
1779 Ok(v) => Ok(v),
1780 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1781 }?;
1782 Ok(Value::BigInt(val.pow(rhs_val)))
1783 }
1784 }
1785 Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))),
1786 Value::Int(val) => {
1787 let rhs_val = rhs_val.unwrap_int();
1788 if rhs_val < 0 {
1789 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1790 } else {
1791 let result: i64 = match rhs_val.try_into() {
1792 Ok(v) => val
1793 .checked_pow(v)
1794 .ok_or(Error::IntTooLarge(rhs_val, rhs_span)),
1795 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1796 }?;
1797 Ok(Value::Int(result))
1798 }
1799 }
1800 _ => panic!("value should support exp"),
1801 }
1802}
1803
1804fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value {
1805 match lhs_val {
1806 Value::BigInt(val) => {
1807 let rhs = rhs_val.unwrap_big_int();
1808 Value::Bool(val > rhs)
1809 }
1810 Value::Int(val) => {
1811 let rhs = rhs_val.unwrap_int();
1812 Value::Bool(val > rhs)
1813 }
1814 Value::Double(val) => {
1815 let rhs = rhs_val.unwrap_double();
1816 Value::Bool(val > rhs)
1817 }
1818 _ => panic!("value doesn't support binop gt"),
1819 }
1820}
1821
1822fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value {
1823 match lhs_val {
1824 Value::BigInt(val) => {
1825 let rhs = rhs_val.unwrap_big_int();
1826 Value::Bool(val >= rhs)
1827 }
1828 Value::Int(val) => {
1829 let rhs = rhs_val.unwrap_int();
1830 Value::Bool(val >= rhs)
1831 }
1832 Value::Double(val) => {
1833 let rhs = rhs_val.unwrap_double();
1834 Value::Bool(val >= rhs)
1835 }
1836 _ => panic!("value doesn't support binop gte"),
1837 }
1838}
1839
1840fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value {
1841 match lhs_val {
1842 Value::BigInt(val) => {
1843 let rhs = rhs_val.unwrap_big_int();
1844 Value::Bool(val < rhs)
1845 }
1846 Value::Int(val) => {
1847 let rhs = rhs_val.unwrap_int();
1848 Value::Bool(val < rhs)
1849 }
1850 Value::Double(val) => {
1851 let rhs = rhs_val.unwrap_double();
1852 Value::Bool(val < rhs)
1853 }
1854 _ => panic!("value doesn't support binop lt"),
1855 }
1856}
1857
1858fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value {
1859 match lhs_val {
1860 Value::BigInt(val) => {
1861 let rhs = rhs_val.unwrap_big_int();
1862 Value::Bool(val <= rhs)
1863 }
1864 Value::Int(val) => {
1865 let rhs = rhs_val.unwrap_int();
1866 Value::Bool(val <= rhs)
1867 }
1868 Value::Double(val) => {
1869 let rhs = rhs_val.unwrap_double();
1870 Value::Bool(val <= rhs)
1871 }
1872 _ => panic!("value doesn't support binop lte"),
1873 }
1874}
1875
1876fn eval_binop_mod(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1877 match lhs_val {
1878 Value::BigInt(val) => {
1879 let rhs = rhs_val.unwrap_big_int();
1880 if rhs == BigInt::from(0) {
1881 Err(Error::DivZero(rhs_span))
1882 } else {
1883 Ok(Value::BigInt(val % rhs))
1884 }
1885 }
1886 Value::Int(val) => {
1887 let rhs = rhs_val.unwrap_int();
1888 if rhs == 0 {
1889 Err(Error::DivZero(rhs_span))
1890 } else {
1891 Ok(Value::Int(val.wrapping_rem(rhs)))
1892 }
1893 }
1894 Value::Double(val) => {
1895 let rhs = rhs_val.unwrap_double();
1896 if rhs == 0.0 {
1897 Err(Error::DivZero(rhs_span))
1898 } else {
1899 Ok(Value::Double(val % rhs))
1900 }
1901 }
1902 _ => panic!("value should support mod"),
1903 }
1904}
1905
1906fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value {
1907 match lhs_val {
1908 Value::BigInt(val) => {
1909 let rhs = rhs_val.unwrap_big_int();
1910 Value::BigInt(val * rhs)
1911 }
1912 Value::Int(val) => {
1913 let rhs = rhs_val.unwrap_int();
1914 Value::Int(val.wrapping_mul(rhs))
1915 }
1916 Value::Double(val) => {
1917 let rhs = rhs_val.unwrap_double();
1918 Value::Double(val * rhs)
1919 }
1920 _ => panic!("value should support mul"),
1921 }
1922}
1923
1924fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value {
1925 match lhs_val {
1926 Value::BigInt(val) => {
1927 let rhs = rhs_val.unwrap_big_int();
1928 Value::BigInt(val | rhs)
1929 }
1930 Value::Int(val) => {
1931 let rhs = rhs_val.unwrap_int();
1932 Value::Int(val | rhs)
1933 }
1934 _ => panic!("value type does not support orb"),
1935 }
1936}
1937
1938fn eval_binop_shl(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1939 Ok(match lhs_val {
1940 Value::BigInt(val) => {
1941 let rhs = rhs_val.unwrap_int();
1942 if rhs > 0 {
1943 Value::BigInt(val << rhs)
1944 } else {
1945 Value::BigInt(val >> rhs.abs())
1946 }
1947 }
1948 Value::Int(val) => {
1949 let rhs = rhs_val.unwrap_int();
1950 Value::Int(if rhs > 0 {
1951 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1952 val.checked_shl(shift)
1953 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1954 } else {
1955 let shift: u32 = rhs
1956 .checked_neg()
1957 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1958 .try_into()
1959 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1960 val.checked_shr(shift)
1961 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1962 })
1963 }
1964 _ => panic!("value should support shl"),
1965 })
1966}
1967
1968fn eval_binop_shr(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
1969 Ok(match lhs_val {
1970 Value::BigInt(val) => {
1971 let rhs = rhs_val.unwrap_int();
1972 if rhs > 0 {
1973 Value::BigInt(val >> rhs)
1974 } else {
1975 Value::BigInt(val << rhs.abs())
1976 }
1977 }
1978 Value::Int(val) => {
1979 let rhs = rhs_val.unwrap_int();
1980 Value::Int(if rhs > 0 {
1981 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1982 val.checked_shr(shift)
1983 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1984 } else {
1985 let shift: u32 = rhs
1986 .checked_neg()
1987 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1988 .try_into()
1989 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
1990 val.checked_shl(shift)
1991 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
1992 })
1993 }
1994 _ => panic!("value should support shr"),
1995 })
1996}
1997
1998fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value {
1999 match lhs_val {
2000 Value::BigInt(val) => {
2001 let rhs = rhs_val.unwrap_big_int();
2002 Value::BigInt(val - rhs)
2003 }
2004 Value::Double(val) => {
2005 let rhs = rhs_val.unwrap_double();
2006 Value::Double(val - rhs)
2007 }
2008 Value::Int(val) => {
2009 let rhs = rhs_val.unwrap_int();
2010 Value::Int(val.wrapping_sub(rhs))
2011 }
2012 _ => panic!("value is not subtractable"),
2013 }
2014}
2015
2016fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value {
2017 match lhs_val {
2018 Value::BigInt(val) => {
2019 let rhs = rhs_val.unwrap_big_int();
2020 Value::BigInt(val ^ rhs)
2021 }
2022 Value::Int(val) => {
2023 let rhs = rhs_val.unwrap_int();
2024 Value::Int(val ^ rhs)
2025 }
2026 _ => panic!("value type does not support xorb"),
2027 }
2028}
2029
2030fn update_functor_app(functor: Functor, app: FunctorApp) -> FunctorApp {
2031 match functor {
2032 Functor::Adj => FunctorApp {
2033 adjoint: !app.adjoint,
2034 controlled: app.controlled,
2035 },
2036 Functor::Ctl => FunctorApp {
2037 adjoint: app.adjoint,
2038 controlled: app.controlled + 1,
2039 },
2040 }
2041}
2042
2043fn follow_field_path(mut value: Value, path: &[usize]) -> Option<Value> {
2044 for &index in path {
2045 let Value::Tuple(items) = value else {
2046 return None;
2047 };
2048 value = items[index].clone();
2049 }
2050 Some(value)
2051}
2052
2053fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option<Value> {
2054 match (record, path) {
2055 (_, []) => Some(replace.clone()),
2056 (Value::Tuple(items), &[next_index, ..]) if next_index < items.len() => {
2057 let update = |(index, item)| {
2058 if index == next_index {
2059 update_field_path(item, &path[1..], replace)
2060 } else {
2061 Some(item.clone())
2062 }
2063 };
2064
2065 let items: Option<_> = items.iter().enumerate().map(update).collect();
2066 Some(Value::Tuple(items?))
2067 }
2068 _ => None,
2069 }
2070}
2071