GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
5e957374e300916bbbc028c807583fcd5e112661

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

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