GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
cesarzc/ssa-panic

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

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