GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
fddddcf80bb87464a67b10ff2ca79c7048d4372b

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

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