GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billt/revert-mimalloc

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

1848lines · modecode

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