GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/merge-mines-changes

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

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