GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
2b583dda267f5bb3df16fbf6251d9bbb86b42b49

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

1647lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#![warn(clippy::mod_module_files, clippy::pedantic, clippy::unwrap_used)]
5
6#[cfg(test)]
7mod tests;
8
9pub mod backend;
10pub mod debug;
11mod intrinsic;
12pub mod lower;
13pub mod output;
14pub mod val;
15
16use crate::val::{FunctorApp, Value};
17use backend::Backend;
18use debug::{CallStack, Frame};
19use miette::Diagnostic;
20use num_bigint::BigInt;
21use output::Receiver;
22use qsc_data_structures::span::Span;
23use qsc_fir::fir::{
24 self, BinOp, CallableDecl, ExprKind, Field, Functor, Lit, LocalItemId, Mutability, NodeId,
25 PackageId, PatKind, PrimField, Res, SpecBody, SpecGen, StmtKind, StringComponent, UnOp,
26};
27use qsc_fir::fir::{BlockId, ExprId, PatId, StmtId};
28use std::{
29 collections::{hash_map::Entry, HashMap},
30 fmt::{self, Display, Formatter, Write},
31 iter,
32 ops::Neg,
33 rc::Rc,
34};
35use thiserror::Error;
36use val::GlobalId;
37
38#[derive(Clone, Debug, Diagnostic, Error)]
39pub enum Error {
40 #[error("array too large")]
41 #[diagnostic(code("Qsc.Eval.ArrayTooLarge"))]
42 ArrayTooLarge(#[label("this array has too many items")] Span),
43
44 #[error("invalid array length: {0}")]
45 #[diagnostic(code("Qsc.Eval.InvalidArrayLength"))]
46 InvalidArrayLength(i64, #[label("cannot be used as a length")] Span),
47
48 #[error("division by zero")]
49 #[diagnostic(code("Qsc.Eval.DivZero"))]
50 DivZero(#[label("cannot divide by zero")] Span),
51
52 #[error("empty range")]
53 #[diagnostic(code("Qsc.Eval.EmptyRange"))]
54 EmptyRange(#[label("the range cannot be empty")] Span),
55
56 #[error("value cannot be used as an index: {0}")]
57 #[diagnostic(code("Qsc.Eval.InvalidIndex"))]
58 InvalidIndex(i64, #[label("invalid index")] Span),
59
60 #[error("integer too large for operation")]
61 #[diagnostic(code("Qsc.Eval.IntTooLarge"))]
62 IntTooLarge(i64, #[label("this value is too large")] Span),
63
64 #[error("missing specialization: {0}")]
65 #[diagnostic(code("Qsc.Eval.MissingSpec"))]
66 MissingSpec(String, #[label("callable has no {0} specialization")] Span),
67
68 #[error("index out of range: {0}")]
69 #[diagnostic(code("Qsc.Eval.IndexOutOfRange"))]
70 IndexOutOfRange(i64, #[label("out of range")] Span),
71
72 #[error("negative integers cannot be used here: {0}")]
73 #[diagnostic(code("Qsc.Eval.InvalidNegativeInt"))]
74 InvalidNegativeInt(i64, #[label("invalid negative integer")] Span),
75
76 #[error("output failure")]
77 #[diagnostic(code("Qsc.Eval.OutputFail"))]
78 OutputFail(#[label("failed to generate output")] Span),
79
80 #[error("qubits in gate invocation are not unique")]
81 #[diagnostic(code("Qsc.Eval.QubitUniqueness"))]
82 QubitUniqueness(#[label] Span),
83
84 #[error("range with step size of zero")]
85 #[diagnostic(code("Qsc.Eval.RangeStepZero"))]
86 RangeStepZero(#[label("invalid range")] Span),
87
88 #[error("Qubit{0} released while not in |0⟩ state")]
89 #[diagnostic(code("Qsc.Eval.ReleasedQubitNotZero"))]
90 ReleasedQubitNotZero(usize),
91
92 #[error("name is not bound")]
93 #[diagnostic(code("Qsc.Eval.UnboundName"))]
94 UnboundName(#[label] Span),
95
96 #[error("unknown intrinsic `{0}`")]
97 #[diagnostic(code("Qsc.Eval.UnknownIntrinsic"))]
98 UnknownIntrinsic(String, #[label("callable has no implementation")] Span),
99
100 #[error("program failed: {0}")]
101 #[diagnostic(code("Qsc.Eval.UserFail"))]
102 UserFail(String, #[label("explicit fail")] Span),
103}
104
105/// A specialization that may be implemented for an operation.
106enum Spec {
107 /// The default specialization.
108 Body,
109 /// The adjoint specialization.
110 Adj,
111 /// The controlled specialization.
112 Ctl,
113 /// The controlled adjoint specialization.
114 CtlAdj,
115}
116
117impl Display for Spec {
118 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
119 match self {
120 Spec::Body => f.write_str("body"),
121 Spec::Adj => f.write_str("adjoint"),
122 Spec::Ctl => f.write_str("controlled"),
123 Spec::CtlAdj => f.write_str("controlled adjoint"),
124 }
125 }
126}
127
128/// Evaluates the given stmt with the given context.
129/// # Errors
130/// Returns the first error encountered during execution.
131pub fn eval_stmt(
132 stmt: StmtId,
133 globals: &impl NodeLookup,
134 env: &mut Env,
135 sim: &mut impl Backend,
136 package: PackageId,
137 receiver: &mut impl Receiver,
138) -> Result<Value, (Error, Vec<Frame>)> {
139 let mut state = State::new(package);
140 state.push_stmt(stmt);
141 state.resume(globals, env, sim, receiver, &[])?;
142 Ok(state.pop_val())
143}
144
145/// Evaluates the given expr with the given context.
146/// # Errors
147/// Returns the first error encountered during execution.
148pub fn eval_expr(
149 state: &mut State,
150 expr: ExprId,
151 globals: &impl NodeLookup,
152 env: &mut Env,
153 sim: &mut impl Backend,
154 out: &mut impl Receiver,
155) -> Result<Value, (Error, Vec<Frame>)> {
156 state.push_expr(expr);
157 state.resume(globals, env, sim, out, &[])?;
158 Ok(state.pop_val())
159}
160
161pub fn eval_push_expr(state: &mut State, expr: ExprId) {
162 state.push_expr(expr);
163}
164
165/// Continues evaluation given current state with the given context.
166/// # Errors
167/// Returns the first error encountered during execution.
168pub fn eval_resume(
169 state: &mut State,
170 globals: &impl NodeLookup,
171 env: &mut Env,
172 sim: &mut impl Backend,
173 out: &mut impl Receiver,
174 breakpoints: &[StmtId],
175) -> Result<Option<StmtId>, (Error, Vec<Frame>)> {
176 state.resume(globals, env, sim, out, breakpoints)
177}
178
179trait AsIndex {
180 type Output;
181
182 fn as_index(&self, span: Span) -> Self::Output;
183}
184
185impl AsIndex for i64 {
186 type Output = Result<usize, Error>;
187
188 fn as_index(&self, span: Span) -> Self::Output {
189 match (*self).try_into() {
190 Ok(index) => Ok(index),
191 Err(_) => Err(Error::InvalidIndex(*self, span)),
192 }
193 }
194}
195
196#[derive(Debug)]
197struct Variable {
198 value: Value,
199 mutability: Mutability,
200}
201
202impl Variable {
203 fn is_mutable(&self) -> bool {
204 self.mutability == Mutability::Mutable
205 }
206}
207
208struct Range {
209 step: i64,
210 end: i64,
211 curr: i64,
212}
213
214impl Iterator for Range {
215 type Item = i64;
216
217 fn next(&mut self) -> Option<Self::Item> {
218 let curr = self.curr;
219 self.curr += self.step;
220 if (self.step > 0 && curr <= self.end) || (self.step < 0 && curr >= self.end) {
221 Some(curr)
222 } else {
223 None
224 }
225 }
226}
227
228impl Range {
229 fn new(start: i64, step: i64, end: i64) -> Self {
230 Range {
231 step,
232 end,
233 curr: start,
234 }
235 }
236}
237
238pub enum Global<'a> {
239 Callable(&'a CallableDecl),
240 Udt,
241}
242
243pub trait NodeLookup {
244 fn get(&self, id: GlobalId) -> Option<Global>;
245 fn get_block(&self, package: PackageId, id: BlockId) -> &qsc_fir::fir::Block;
246 fn get_expr(&self, package: PackageId, id: ExprId) -> &qsc_fir::fir::Expr;
247 fn get_pat(&self, package: PackageId, id: PatId) -> &qsc_fir::fir::Pat;
248 fn get_stmt(&self, package: PackageId, id: StmtId) -> &qsc_fir::fir::Stmt;
249}
250
251#[derive(Default)]
252pub struct Env(Vec<Scope>);
253
254impl Env {
255 #[must_use]
256 fn get(&self, id: NodeId) -> Option<&Variable> {
257 self.0
258 .iter()
259 .rev()
260 .find_map(|scope| scope.bindings.get(&id))
261 }
262
263 fn get_mut(&mut self, id: NodeId) -> Option<&mut Variable> {
264 self.0
265 .iter_mut()
266 .rev()
267 .find_map(|scope| scope.bindings.get_mut(&id))
268 }
269
270 fn push_scope(&mut self) {
271 self.0.push(Scope::default());
272 }
273
274 fn leave_scope(&mut self) {
275 self.0
276 .pop()
277 .expect("scope should be entered first before leaving");
278 }
279}
280
281#[derive(Default)]
282struct Scope {
283 bindings: HashMap<NodeId, Variable>,
284}
285
286impl Env {
287 #[must_use]
288 pub fn with_empty_scope() -> Self {
289 Self(vec![Scope::default()])
290 }
291}
292
293enum Cont {
294 Action(Action),
295 Expr(ExprId),
296 Frame(usize),
297 Scope,
298 Stmt(StmtId),
299}
300
301#[derive(Clone)]
302enum Action {
303 Array(usize),
304 ArrayRepeat(Span),
305 Assign(ExprId),
306 Bind(PatId, Mutability),
307 BinOp(BinOp, Span, Option<ExprId>),
308 Call(Span, Span),
309 Consume,
310 Fail(Span),
311 Field(Field),
312 If(ExprId, Option<ExprId>),
313 Index(Span),
314 Range(bool, bool, bool),
315 Return,
316 StringConcat(usize),
317 StringLit(Rc<str>),
318 UpdateIndex(Span),
319 Tuple(usize),
320 UnOp(UnOp),
321 UpdateField(Field),
322 While(ExprId, BlockId),
323}
324
325pub struct State {
326 stack: Vec<Cont>,
327 vals: Vec<Value>,
328 package: PackageId,
329 call_stack: CallStack,
330 current_span: Span,
331}
332
333impl State {
334 #[must_use]
335 pub fn new(package: PackageId) -> Self {
336 Self {
337 stack: Vec::new(),
338 vals: Vec::new(),
339 package,
340 call_stack: CallStack::default(),
341 current_span: Span::default(),
342 }
343 }
344
345 fn pop_cont(&mut self) -> Option<Cont> {
346 self.stack.pop()
347 }
348
349 fn push_action(&mut self, action: Action) {
350 self.stack.push(Cont::Action(action));
351 }
352
353 fn push_expr(&mut self, expr: ExprId) {
354 self.stack.push(Cont::Expr(expr));
355 }
356
357 fn push_frame(&mut self, id: GlobalId, functor: FunctorApp) {
358 self.call_stack.push_frame(Frame {
359 span: self.current_span,
360 id,
361 caller: self.package,
362 functor,
363 });
364 self.stack.push(Cont::Frame(self.vals.len()));
365 self.package = id.package;
366 }
367
368 fn leave_frame(&mut self, len: usize) {
369 let frame = self
370 .call_stack
371 .pop_frame()
372 .expect("frame should be present");
373 self.package = frame.caller;
374 let frame_val = self.pop_val();
375 self.vals.drain(len..);
376 self.push_val(frame_val);
377 }
378
379 fn push_scope(&mut self, env: &mut Env) {
380 env.push_scope();
381 self.stack.push(Cont::Scope);
382 }
383
384 fn push_stmt(&mut self, stmt: StmtId) {
385 self.stack.push(Cont::Stmt(stmt));
386 }
387
388 fn push_block(&mut self, env: &mut Env, globals: &impl NodeLookup, block: BlockId) {
389 let block = globals.get_block(self.package, block);
390 self.push_scope(env);
391 for stmt in block.stmts.iter().rev() {
392 self.push_stmt(*stmt);
393 self.push_action(Action::Consume);
394 }
395 if block.stmts.is_empty() {
396 self.push_val(Value::unit());
397 } else {
398 self.pop_cont();
399 }
400 }
401
402 fn pop_val(&mut self) -> Value {
403 self.vals.pop().expect("value should be present")
404 }
405
406 fn pop_vals(&mut self, len: usize) -> Vec<Value> {
407 self.vals.drain(self.vals.len() - len..).collect()
408 }
409
410 fn push_val(&mut self, val: Value) {
411 self.vals.push(val);
412 }
413
414 #[must_use]
415 pub fn get_stack_frames(&self) -> Vec<Frame> {
416 let mut frames = self.call_stack.clone().into_frames();
417
418 let mut span = self.current_span;
419 for frame in frames.iter_mut().rev() {
420 std::mem::swap(&mut frame.span, &mut span);
421 }
422 frames
423 }
424
425 /// # Errors
426 /// Returns the first error encountered during execution.
427 pub fn resume(
428 &mut self,
429 globals: &impl NodeLookup,
430 env: &mut Env,
431 sim: &mut impl Backend,
432 out: &mut impl Receiver,
433 breakpoints: &[StmtId],
434 ) -> Result<Option<StmtId>, (Error, Vec<Frame>)> {
435 while let Some(cont) = self.pop_cont() {
436 let res = match cont {
437 Cont::Action(action) => self
438 .cont_action(env, sim, globals, action, out)
439 .map(|_| None),
440 Cont::Expr(expr) => self.cont_expr(env, globals, expr).map(|_| None),
441 Cont::Frame(len) => {
442 self.leave_frame(len);
443 Ok(None)
444 }
445 Cont::Scope => {
446 env.leave_scope();
447 Ok(None)
448 }
449 Cont::Stmt(stmt) => {
450 self.cont_stmt(globals, stmt);
451 match breakpoints.iter().find(|&bp| *bp == stmt) {
452 Some(bp) => Ok(Some(bp)),
453 None => Ok(None),
454 }
455 }
456 };
457 match res {
458 Ok(Some(bp)) => return Ok(Some(*bp)),
459 Ok(None) => {}
460 Err(e) => return Err((e, self.get_stack_frames())),
461 }
462 }
463
464 Ok(None)
465 }
466
467 pub fn get_result(&mut self) -> Value {
468 self.pop_val()
469 }
470
471 #[allow(clippy::similar_names)]
472 fn cont_expr(
473 &mut self,
474 env: &mut Env,
475 globals: &impl NodeLookup,
476 expr: ExprId,
477 ) -> Result<(), Error> {
478 let expr = globals.get_expr(self.package, expr);
479 self.current_span = expr.span;
480
481 match &expr.kind {
482 ExprKind::Array(arr) => self.cont_arr(arr),
483 ExprKind::ArrayRepeat(item, size) => self.cont_arr_repeat(globals, *item, *size),
484 ExprKind::Assign(lhs, rhs) => self.cont_assign(*lhs, *rhs),
485 ExprKind::AssignOp(op, lhs, rhs) => self.cont_assign_op(globals, *op, *lhs, *rhs),
486 ExprKind::AssignField(record, field, replace) => {
487 self.cont_assign_field(*record, field, *replace);
488 }
489 ExprKind::AssignIndex(lhs, mid, rhs) => {
490 self.cont_assign_index(globals, *lhs, *mid, *rhs);
491 }
492 ExprKind::BinOp(op, lhs, rhs) => self.cont_binop(globals, *op, *rhs, *lhs),
493 ExprKind::Block(block) => self.push_block(env, globals, *block),
494 ExprKind::Call(callee_expr, args_expr) => {
495 self.cont_call(globals, *callee_expr, *args_expr);
496 }
497 ExprKind::Closure(args, callable) => {
498 let closure = resolve_closure(env, self.package, expr.span, args, *callable)?;
499 self.push_val(closure);
500 }
501 ExprKind::Fail(fail_expr) => self.cont_fail(expr.span, *fail_expr),
502 ExprKind::Field(expr, field) => self.cont_field(*expr, field),
503 ExprKind::Hole => panic!("hole expr should be disallowed by passes"),
504 ExprKind::If(cond_expr, then_expr, else_expr) => {
505 self.cont_if(*cond_expr, *then_expr, *else_expr);
506 }
507 ExprKind::Index(arr, index) => self.cont_index(globals, *arr, *index),
508 ExprKind::Lit(lit) => self.push_val(lit_to_val(lit)),
509 ExprKind::Range(start, step, end) => self.cont_range(*start, *step, *end),
510 ExprKind::Return(expr) => self.cont_ret(*expr),
511 ExprKind::String(components) => self.cont_string(components),
512 ExprKind::UpdateIndex(lhs, mid, rhs) => self.update_index(globals, *lhs, *mid, *rhs),
513 ExprKind::Tuple(tup) => self.cont_tup(tup),
514 ExprKind::UnOp(op, expr) => self.cont_unop(*op, *expr),
515 ExprKind::UpdateField(record, field, replace) => {
516 self.cont_update_field(*record, field, *replace);
517 }
518 ExprKind::Var(res, _) => {
519 self.push_val(resolve_binding(env, self.package, *res, expr.span)?);
520 }
521 ExprKind::While(cond_expr, block) => self.cont_while(*cond_expr, *block),
522 }
523
524 Ok(())
525 }
526
527 fn cont_tup(&mut self, tup: &Vec<ExprId>) {
528 self.push_action(Action::Tuple(tup.len()));
529 for tup_expr in tup.iter().rev() {
530 self.push_expr(*tup_expr);
531 }
532 }
533
534 fn cont_arr(&mut self, arr: &Vec<ExprId>) {
535 self.push_action(Action::Array(arr.len()));
536 for entry in arr.iter().rev() {
537 self.push_expr(*entry);
538 }
539 }
540
541 fn cont_arr_repeat(&mut self, globals: &impl NodeLookup, item: ExprId, size: ExprId) {
542 let size_expr = globals.get_expr(self.package, size);
543 self.push_action(Action::ArrayRepeat(size_expr.span));
544 self.push_expr(size);
545 self.push_expr(item);
546 }
547
548 fn cont_ret(&mut self, expr: ExprId) {
549 self.push_action(Action::Return);
550 self.push_expr(expr);
551 }
552
553 fn cont_if(&mut self, cond_expr: ExprId, then_expr: ExprId, else_expr: Option<ExprId>) {
554 self.push_action(Action::If(then_expr, else_expr));
555 self.push_expr(cond_expr);
556 }
557
558 fn cont_fail(&mut self, span: Span, fail_expr: ExprId) {
559 self.push_action(Action::Fail(span));
560 self.push_expr(fail_expr);
561 }
562
563 fn cont_assign(&mut self, lhs: ExprId, rhs: ExprId) {
564 self.push_action(Action::Assign(lhs));
565 self.push_expr(rhs);
566 self.push_val(Value::unit());
567 }
568
569 fn cont_assign_op(&mut self, globals: &impl NodeLookup, op: BinOp, lhs: ExprId, rhs: ExprId) {
570 self.push_action(Action::Assign(lhs));
571 self.cont_binop(globals, op, rhs, lhs);
572 self.push_val(Value::unit());
573 }
574
575 fn cont_assign_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
576 self.push_action(Action::Assign(record));
577 self.cont_update_field(record, field, replace);
578 self.push_val(Value::unit());
579 }
580
581 fn cont_assign_index(
582 &mut self,
583 globals: &impl NodeLookup,
584 lhs: ExprId,
585 mid: ExprId,
586 rhs: ExprId,
587 ) {
588 self.push_action(Action::Assign(lhs));
589 self.update_index(globals, lhs, mid, rhs);
590 self.push_val(Value::unit());
591 }
592
593 fn cont_field(&mut self, expr: ExprId, field: &Field) {
594 self.push_action(Action::Field(field.clone()));
595 self.push_expr(expr);
596 }
597
598 fn cont_index(&mut self, globals: &impl NodeLookup, arr: ExprId, index: ExprId) {
599 let index_expr = globals.get_expr(self.package, index);
600 self.push_action(Action::Index(index_expr.span));
601 self.push_expr(index);
602 self.push_expr(arr);
603 }
604
605 fn cont_range(&mut self, start: Option<ExprId>, step: Option<ExprId>, end: Option<ExprId>) {
606 self.push_action(Action::Range(
607 start.is_some(),
608 step.is_some(),
609 end.is_some(),
610 ));
611 if let Some(end) = end {
612 self.push_expr(end);
613 }
614 if let Some(step) = step {
615 self.push_expr(step);
616 }
617 if let Some(start) = start {
618 self.push_expr(start);
619 }
620 }
621
622 fn cont_string(&mut self, components: &[StringComponent]) {
623 if let [StringComponent::Lit(str)] = components {
624 self.push_val(Value::String(Rc::clone(str)));
625 return;
626 }
627
628 self.push_action(Action::StringConcat(components.len()));
629 for component in components.iter().rev() {
630 match component {
631 StringComponent::Expr(expr) => self.push_expr(*expr),
632 StringComponent::Lit(lit) => self.push_action(Action::StringLit(lit.clone())),
633 }
634 }
635 }
636
637 fn cont_while(&mut self, cond_expr: ExprId, block: BlockId) {
638 self.push_action(Action::While(cond_expr, block));
639 self.push_expr(cond_expr);
640 }
641
642 fn cont_call(&mut self, globals: &impl NodeLookup, callee: ExprId, args: ExprId) {
643 let callee_expr = globals.get_expr(self.package, callee);
644 let args_expr = globals.get_expr(self.package, args);
645 self.push_action(Action::Call(callee_expr.span, args_expr.span));
646 self.push_expr(args);
647 self.push_expr(callee);
648 }
649
650 fn cont_binop(&mut self, globals: &impl NodeLookup, op: BinOp, rhs: ExprId, lhs: ExprId) {
651 let rhs_expr = globals.get_expr(self.package, rhs);
652 match op {
653 BinOp::Add
654 | BinOp::AndB
655 | BinOp::Div
656 | BinOp::Eq
657 | BinOp::Exp
658 | BinOp::Gt
659 | BinOp::Gte
660 | BinOp::Lt
661 | BinOp::Lte
662 | BinOp::Mod
663 | BinOp::Mul
664 | BinOp::Neq
665 | BinOp::OrB
666 | BinOp::Shl
667 | BinOp::Shr
668 | BinOp::Sub
669 | BinOp::XorB => {
670 self.push_action(Action::BinOp(op, rhs_expr.span, None));
671 self.push_expr(rhs);
672 self.push_expr(lhs);
673 }
674 BinOp::AndL | BinOp::OrL => {
675 self.push_action(Action::BinOp(op, rhs_expr.span, Some(rhs)));
676 self.push_expr(lhs);
677 }
678 }
679 }
680
681 fn update_index(&mut self, globals: &impl NodeLookup, lhs: ExprId, mid: ExprId, rhs: ExprId) {
682 let mid_expr = globals.get_expr(self.package, mid);
683 self.push_action(Action::UpdateIndex(mid_expr.span));
684 self.push_expr(lhs);
685 self.push_expr(rhs);
686 self.push_expr(mid);
687 }
688
689 fn cont_unop(&mut self, op: UnOp, expr: ExprId) {
690 self.push_action(Action::UnOp(op));
691 self.push_expr(expr);
692 }
693
694 fn cont_update_field(&mut self, record: ExprId, field: &Field, replace: ExprId) {
695 self.push_action(Action::UpdateField(field.clone()));
696 self.push_expr(replace);
697 self.push_expr(record);
698 }
699
700 fn cont_stmt(&mut self, globals: &impl NodeLookup, stmt: StmtId) {
701 let stmt = globals.get_stmt(self.package, stmt);
702 self.current_span = stmt.span;
703
704 match &stmt.kind {
705 StmtKind::Expr(expr) => self.push_expr(*expr),
706 StmtKind::Item(..) => self.push_val(Value::unit()),
707 StmtKind::Local(mutability, pat, expr) => {
708 self.push_action(Action::Bind(*pat, *mutability));
709 self.push_expr(*expr);
710 self.push_val(Value::unit());
711 }
712 StmtKind::Qubit(..) => panic!("qubit use-stmt should be eliminated by passes"),
713 StmtKind::Semi(expr) => {
714 self.push_action(Action::Consume);
715 self.push_expr(*expr);
716 self.push_val(Value::unit());
717 }
718 }
719 }
720
721 fn cont_action(
722 &mut self,
723 env: &mut Env,
724 sim: &mut impl Backend,
725 globals: &impl NodeLookup,
726 action: Action,
727 out: &mut impl Receiver,
728 ) -> Result<(), Error> {
729 match action {
730 Action::Array(len) => self.eval_arr(len),
731 Action::ArrayRepeat(span) => self.eval_arr_repeat(span)?,
732 Action::Assign(lhs) => self.eval_assign(env, globals, lhs)?,
733 Action::BinOp(op, span, rhs) => self.eval_binop(op, span, rhs)?,
734 Action::Bind(pat, mutability) => self.eval_bind(env, globals, pat, mutability),
735 Action::Call(callee_span, args_span) => {
736 self.eval_call(env, sim, globals, callee_span, args_span, out)?;
737 }
738 Action::Consume => {
739 self.pop_val();
740 }
741 Action::Fail(span) => {
742 return Err(Error::UserFail(
743 self.pop_val().unwrap_string().to_string(),
744 span,
745 ));
746 }
747 Action::Field(field) => self.eval_field(field),
748 Action::If(then_expr, else_expr) => self.eval_if(then_expr, else_expr),
749 Action::Index(span) => self.eval_index(span)?,
750 Action::Range(has_start, has_step, has_end) => {
751 self.eval_range(has_start, has_step, has_end);
752 }
753 Action::Return => self.eval_ret(env),
754 Action::StringConcat(len) => self.eval_string_concat(len),
755 Action::StringLit(str) => self.push_val(Value::String(str)),
756 Action::UpdateIndex(span) => self.eval_update_index(span)?,
757 Action::Tuple(len) => self.eval_tup(len),
758 Action::UnOp(op) => self.eval_unop(op),
759 Action::UpdateField(field) => self.eval_update_field(field),
760 Action::While(cond_expr, block) => self.eval_while(env, globals, cond_expr, block),
761 }
762 Ok(())
763 }
764
765 fn eval_arr(&mut self, len: usize) {
766 let arr = self.pop_vals(len);
767 self.push_val(Value::Array(arr.into()));
768 }
769
770 fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> {
771 let size_val = self.pop_val().unwrap_int();
772 let item_val = self.pop_val();
773 let s = match size_val.try_into() {
774 Ok(i) => Ok(i),
775 Err(_) => Err(Error::InvalidArrayLength(size_val, span)),
776 }?;
777 self.push_val(Value::Array(vec![item_val; s].into()));
778 Ok(())
779 }
780
781 fn eval_assign(
782 &mut self,
783 env: &mut Env,
784 globals: &impl NodeLookup,
785 lhs: ExprId,
786 ) -> Result<(), Error> {
787 let rhs = self.pop_val();
788 self.update_binding(env, globals, lhs, rhs)
789 }
790
791 fn eval_bind(
792 &mut self,
793 env: &mut Env,
794 globals: &impl NodeLookup,
795 pat: PatId,
796 mutability: Mutability,
797 ) {
798 let val = self.pop_val();
799 self.bind_value(env, globals, pat, val, mutability);
800 }
801
802 fn eval_binop(&mut self, op: BinOp, span: Span, rhs: Option<ExprId>) -> Result<(), Error> {
803 match op {
804 BinOp::Add => self.eval_binop_simple(eval_binop_add),
805 BinOp::AndB => self.eval_binop_simple(eval_binop_andb),
806 BinOp::AndL => {
807 if self.pop_val().unwrap_bool() {
808 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
809 } else {
810 self.push_val(Value::Bool(false));
811 }
812 }
813 BinOp::Div => self.eval_binop_with_error(span, eval_binop_div)?,
814 BinOp::Eq => {
815 let rhs_val = self.pop_val();
816 let lhs_val = self.pop_val();
817 self.push_val(Value::Bool(lhs_val == rhs_val));
818 }
819 BinOp::Exp => self.eval_binop_with_error(span, eval_binop_exp)?,
820 BinOp::Gt => self.eval_binop_simple(eval_binop_gt),
821 BinOp::Gte => self.eval_binop_simple(eval_binop_gte),
822 BinOp::Lt => self.eval_binop_simple(eval_binop_lt),
823 BinOp::Lte => self.eval_binop_simple(eval_binop_lte),
824 BinOp::Mod => self.eval_binop_simple(eval_binop_mod),
825 BinOp::Mul => self.eval_binop_simple(eval_binop_mul),
826 BinOp::Neq => {
827 let rhs_val = self.pop_val();
828 let lhs_val = self.pop_val();
829 self.push_val(Value::Bool(lhs_val != rhs_val));
830 }
831 BinOp::OrB => self.eval_binop_simple(eval_binop_orb),
832 BinOp::OrL => {
833 if self.pop_val().unwrap_bool() {
834 self.push_val(Value::Bool(true));
835 } else {
836 self.push_expr(rhs.expect("rhs should be provided with binop andl"));
837 }
838 }
839 BinOp::Shl => self.eval_binop_simple(eval_binop_shl),
840 BinOp::Shr => self.eval_binop_simple(eval_binop_shr),
841 BinOp::Sub => self.eval_binop_simple(eval_binop_sub),
842 BinOp::XorB => self.eval_binop_simple(eval_binop_xorb),
843 }
844 Ok(())
845 }
846
847 fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) {
848 let rhs_val = self.pop_val();
849 let lhs_val = self.pop_val();
850 self.push_val(binop_func(lhs_val, rhs_val));
851 }
852
853 fn eval_binop_with_error(
854 &mut self,
855 span: Span,
856 binop_func: impl FnOnce(Value, Value, Span) -> Result<Value, Error>,
857 ) -> Result<(), Error> {
858 let rhs_val = self.pop_val();
859 let lhs_val = self.pop_val();
860 self.push_val(binop_func(lhs_val, rhs_val, span)?);
861 Ok(())
862 }
863
864 fn eval_call(
865 &mut self,
866 env: &mut Env,
867 sim: &mut impl Backend,
868 globals: &impl NodeLookup,
869 callee_span: Span,
870 arg_span: Span,
871 out: &mut impl Receiver,
872 ) -> Result<(), Error> {
873 let arg = self.pop_val();
874 let (callee_id, functor, fixed_args) = match self.pop_val() {
875 Value::Closure(fixed_args, id, functor) => (id, functor, Some(fixed_args)),
876 Value::Global(id, functor) => (id, functor, None),
877 _ => panic!("value is not callable"),
878 };
879
880 let callee = match globals.get(callee_id) {
881 Some(Global::Callable(callable)) => callable,
882 Some(Global::Udt) => {
883 self.push_val(arg);
884 return Ok(());
885 }
886 None => return Err(Error::UnboundName(callee_span)),
887 };
888
889 let spec = spec_from_functor_app(functor);
890 self.push_frame(callee_id, functor);
891 self.push_scope(env);
892 let block_body = &match spec {
893 Spec::Body => Some(&callee.body),
894 Spec::Adj => callee.adj.as_ref(),
895 Spec::Ctl => callee.ctl.as_ref(),
896 Spec::CtlAdj => callee.ctl_adj.as_ref(),
897 }
898 .ok_or(Error::MissingSpec(spec.to_string(), callee_span))?
899 .body;
900 match block_body {
901 SpecBody::Impl(input, body_block) => {
902 self.bind_args_for_spec(
903 env,
904 globals,
905 callee.input,
906 *input,
907 arg,
908 functor.controlled,
909 fixed_args,
910 );
911 self.push_block(env, globals, *body_block);
912 Ok(())
913 }
914 SpecBody::Gen(SpecGen::Intrinsic) => {
915 let name = &callee.name.name;
916 let val = intrinsic::call(name, callee_span, arg, arg_span, sim, out)?;
917 self.push_val(val);
918 Ok(())
919 }
920 SpecBody::Gen(_) => Err(Error::MissingSpec(spec.to_string(), callee_span)),
921 }
922 }
923
924 fn eval_field(&mut self, field: Field) {
925 let record = self.pop_val();
926 let val = match (record, field) {
927 (Value::Range(Some(start), _, _), Field::Prim(PrimField::Start)) => Value::Int(start),
928 (Value::Range(_, step, _), Field::Prim(PrimField::Step)) => Value::Int(step),
929 (Value::Range(_, _, Some(end)), Field::Prim(PrimField::End)) => Value::Int(end),
930 (record, Field::Path(path)) => {
931 follow_field_path(record, &path.indices).expect("field path should be valid")
932 }
933 _ => panic!("invalid field access"),
934 };
935 self.push_val(val);
936 }
937
938 fn eval_if(&mut self, then_expr: ExprId, else_expr: Option<ExprId>) {
939 if self.pop_val().unwrap_bool() {
940 self.push_expr(then_expr);
941 } else if let Some(else_expr) = else_expr {
942 self.push_expr(else_expr);
943 } else {
944 self.push_val(Value::unit());
945 }
946 }
947
948 fn eval_index(&mut self, span: Span) -> Result<(), Error> {
949 let index_val = self.pop_val();
950 let arr = self.pop_val().unwrap_array();
951 match &index_val {
952 Value::Int(i) => self.push_val(index_array(&arr, *i, span)?),
953 &Value::Range(start, step, end) => {
954 self.push_val(slice_array(&arr, start, step, end, span)?);
955 }
956 _ => panic!("array should only be indexed by Int or Range"),
957 }
958 Ok(())
959 }
960
961 fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) {
962 let end = if has_end {
963 Some(self.pop_val().unwrap_int())
964 } else {
965 None
966 };
967 let step = if has_step {
968 self.pop_val().unwrap_int()
969 } else {
970 val::DEFAULT_RANGE_STEP
971 };
972 let start = if has_start {
973 Some(self.pop_val().unwrap_int())
974 } else {
975 None
976 };
977 self.push_val(Value::Range(start, step, end));
978 }
979
980 fn eval_ret(&mut self, env: &mut Env) {
981 while let Some(cont) = self.pop_cont() {
982 match cont {
983 Cont::Frame(len) => {
984 self.leave_frame(len);
985 break;
986 }
987 Cont::Scope => env.leave_scope(),
988 _ => {}
989 }
990 }
991 }
992
993 fn eval_string_concat(&mut self, len: usize) {
994 let mut string = String::new();
995 for component in self.pop_vals(len) {
996 write!(string, "{component}").expect("string should be writable");
997 }
998 self.push_val(Value::String(string.into()));
999 }
1000
1001 fn eval_update_index(&mut self, span: Span) -> Result<(), Error> {
1002 let values = self.pop_val().unwrap_array();
1003 let update = self.pop_val();
1004 let index = self.pop_val().unwrap_int();
1005 if index < 0 {
1006 return Err(Error::InvalidNegativeInt(index, span));
1007 }
1008 let i = index.as_index(span)?;
1009 let mut values = values.iter().cloned().collect::<Vec<_>>();
1010 match values.get_mut(i) {
1011 Some(value) => {
1012 *value = update;
1013 }
1014 None => return Err(Error::IndexOutOfRange(index, span)),
1015 }
1016 self.push_val(Value::Array(values.into()));
1017 Ok(())
1018 }
1019
1020 fn eval_tup(&mut self, len: usize) {
1021 let tup = self.pop_vals(len);
1022 self.push_val(Value::Tuple(tup.into()));
1023 }
1024
1025 fn eval_unop(&mut self, op: UnOp) {
1026 let val = self.pop_val();
1027 match op {
1028 UnOp::Functor(functor) => match val {
1029 Value::Closure(args, id, app) => {
1030 self.push_val(Value::Closure(args, id, update_functor_app(functor, app)));
1031 }
1032 Value::Global(id, app) => {
1033 self.push_val(Value::Global(id, update_functor_app(functor, app)));
1034 }
1035 _ => panic!("value should be callable"),
1036 },
1037 UnOp::Neg => match val {
1038 Value::BigInt(v) => self.push_val(Value::BigInt(v.neg())),
1039 Value::Double(v) => self.push_val(Value::Double(v.neg())),
1040 Value::Int(v) => self.push_val(Value::Int(v.wrapping_neg())),
1041 _ => panic!("value should be number"),
1042 },
1043 UnOp::NotB => match val {
1044 Value::Int(v) => self.push_val(Value::Int(!v)),
1045 Value::BigInt(v) => self.push_val(Value::BigInt(!v)),
1046 _ => panic!("value should be Int or BigInt"),
1047 },
1048 UnOp::NotL => match val {
1049 Value::Bool(b) => self.push_val(Value::Bool(!b)),
1050 _ => panic!("value should be bool"),
1051 },
1052 UnOp::Pos => match val {
1053 Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.push_val(val),
1054 _ => panic!("value should be number"),
1055 },
1056 UnOp::Unwrap => self.push_val(val),
1057 }
1058 }
1059
1060 fn eval_update_field(&mut self, field: Field) {
1061 let value = self.pop_val();
1062 let record = self.pop_val();
1063 let update = match (record, field) {
1064 (Value::Range(_, step, end), Field::Prim(PrimField::Start)) => {
1065 Value::Range(Some(value.unwrap_int()), step, end)
1066 }
1067 (Value::Range(start, _, end), Field::Prim(PrimField::Step)) => {
1068 Value::Range(start, value.unwrap_int(), end)
1069 }
1070 (Value::Range(start, step, _), Field::Prim(PrimField::End)) => {
1071 Value::Range(start, step, Some(value.unwrap_int()))
1072 }
1073 (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value)
1074 .expect("field path should be valid"),
1075 _ => panic!("invalid field access"),
1076 };
1077 self.push_val(update);
1078 }
1079
1080 fn eval_while(
1081 &mut self,
1082 env: &mut Env,
1083 globals: &impl NodeLookup,
1084 cond_expr: ExprId,
1085 block: BlockId,
1086 ) {
1087 if self.pop_val().unwrap_bool() {
1088 self.cont_while(cond_expr, block);
1089 self.push_action(Action::Consume);
1090 self.push_val(Value::unit());
1091 self.push_block(env, globals, block);
1092 } else {
1093 self.push_val(Value::unit());
1094 }
1095 }
1096
1097 fn bind_value(
1098 &self,
1099 env: &mut Env,
1100 globals: &impl NodeLookup,
1101 pat: PatId,
1102 val: Value,
1103 mutability: Mutability,
1104 ) {
1105 let pat = globals.get_pat(self.package, pat);
1106 match &pat.kind {
1107 PatKind::Bind(variable) => {
1108 let scope = env.0.last_mut().expect("binding should have a scope");
1109 match scope.bindings.entry(variable.id) {
1110 Entry::Vacant(entry) => entry.insert(Variable {
1111 value: val,
1112 mutability,
1113 }),
1114 Entry::Occupied(_) => panic!("duplicate binding"),
1115 };
1116 }
1117 PatKind::Discard => {}
1118 PatKind::Tuple(tup) => {
1119 let val_tup = val.unwrap_tuple();
1120 for (pat, val) in tup.iter().zip(val_tup.iter()) {
1121 self.bind_value(env, globals, *pat, val.clone(), mutability);
1122 }
1123 }
1124 }
1125 }
1126
1127 #[allow(clippy::similar_names)]
1128 fn update_binding(
1129 &self,
1130 env: &mut Env,
1131 globals: &impl NodeLookup,
1132 lhs: ExprId,
1133 rhs: Value,
1134 ) -> Result<(), Error> {
1135 let lhs = globals.get_expr(self.package, lhs);
1136 match (&lhs.kind, rhs) {
1137 (ExprKind::Hole, _) => {}
1138 (&ExprKind::Var(Res::Local(node), _), rhs) => match env.get_mut(node) {
1139 Some(var) if var.is_mutable() => {
1140 var.value = rhs;
1141 }
1142 Some(_) => panic!("update of mutable variable should be disallowed by compiler"),
1143 None => return Err(Error::UnboundName(lhs.span)),
1144 },
1145 (ExprKind::Tuple(var_tup), Value::Tuple(tup)) => {
1146 for (expr, val) in var_tup.iter().zip(tup.iter()) {
1147 self.update_binding(env, globals, *expr, val.clone())?;
1148 }
1149 }
1150 _ => panic!("unassignable pattern should be disallowed by compiler"),
1151 }
1152 Ok(())
1153 }
1154
1155 #[allow(clippy::too_many_arguments)]
1156 fn bind_args_for_spec(
1157 &self,
1158 env: &mut Env,
1159 globals: &impl NodeLookup,
1160 decl_pat: PatId,
1161 spec_pat: Option<PatId>,
1162 args_val: Value,
1163 ctl_count: u8,
1164 fixed_args: Option<Rc<[Value]>>,
1165 ) {
1166 match spec_pat {
1167 Some(spec_pat) => {
1168 assert!(
1169 ctl_count > 0,
1170 "spec pattern tuple used without controlled functor"
1171 );
1172
1173 let mut tup = args_val;
1174 let mut ctls = vec![];
1175 for _ in 0..ctl_count {
1176 let [c, rest] = &*tup.unwrap_tuple() else {
1177 panic!("tuple should be arity 2");
1178 };
1179 ctls.extend_from_slice(&c.clone().unwrap_array());
1180 tup = rest.clone();
1181 }
1182
1183 self.bind_value(
1184 env,
1185 globals,
1186 spec_pat,
1187 Value::Array(ctls.into()),
1188 Mutability::Immutable,
1189 );
1190 self.bind_value(
1191 env,
1192 globals,
1193 decl_pat,
1194 merge_fixed_args(fixed_args, tup),
1195 Mutability::Immutable,
1196 );
1197 }
1198 None => self.bind_value(
1199 env,
1200 globals,
1201 decl_pat,
1202 merge_fixed_args(fixed_args, args_val),
1203 Mutability::Immutable,
1204 ),
1205 }
1206 }
1207}
1208
1209fn merge_fixed_args(fixed_args: Option<Rc<[Value]>>, arg: Value) -> Value {
1210 if let Some(fixed_args) = fixed_args {
1211 Value::Tuple(fixed_args.iter().cloned().chain(iter::once(arg)).collect())
1212 } else {
1213 arg
1214 }
1215}
1216
1217fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result<Value, Error> {
1218 Ok(match res {
1219 Res::Err => panic!("resolution error"),
1220 Res::Item(item) => Value::Global(
1221 GlobalId {
1222 package: item.package.unwrap_or(package),
1223 item: item.item,
1224 },
1225 FunctorApp::default(),
1226 ),
1227 Res::Local(node) => env.get(node).ok_or(Error::UnboundName(span))?.value.clone(),
1228 })
1229}
1230
1231fn spec_from_functor_app(functor: FunctorApp) -> Spec {
1232 match (functor.adjoint, functor.controlled) {
1233 (false, 0) => Spec::Body,
1234 (true, 0) => Spec::Adj,
1235 (false, _) => Spec::Ctl,
1236 (true, _) => Spec::CtlAdj,
1237 }
1238}
1239
1240fn resolve_closure(
1241 env: &Env,
1242 package: PackageId,
1243 span: Span,
1244 args: &[NodeId],
1245 callable: LocalItemId,
1246) -> Result<Value, Error> {
1247 let args: Option<_> = args
1248 .iter()
1249 .map(|&arg| Some(env.get(arg)?.value.clone()))
1250 .collect();
1251 let args: Vec<_> = args.ok_or(Error::UnboundName(span))?;
1252 let callable = GlobalId {
1253 package,
1254 item: callable,
1255 };
1256 Ok(Value::Closure(args.into(), callable, FunctorApp::default()))
1257}
1258
1259fn lit_to_val(lit: &Lit) -> Value {
1260 match lit {
1261 Lit::BigInt(v) => Value::BigInt(v.clone()),
1262 Lit::Bool(v) => Value::Bool(*v),
1263 Lit::Double(v) => Value::Double(*v),
1264 Lit::Int(v) => Value::Int(*v),
1265 Lit::Pauli(v) => Value::Pauli(*v),
1266 Lit::Result(fir::Result::Zero) => Value::Result(false),
1267 Lit::Result(fir::Result::One) => Value::Result(true),
1268 }
1269}
1270
1271fn index_array(arr: &[Value], index: i64, span: Span) -> Result<Value, Error> {
1272 let i = index.as_index(span)?;
1273 match arr.get(i) {
1274 Some(v) => Ok(v.clone()),
1275 None => Err(Error::IndexOutOfRange(index, span)),
1276 }
1277}
1278
1279fn slice_array(
1280 arr: &[Value],
1281 start: Option<i64>,
1282 step: i64,
1283 end: Option<i64>,
1284 span: Span,
1285) -> Result<Value, Error> {
1286 if step == 0 {
1287 Err(Error::RangeStepZero(span))
1288 } else {
1289 let len: i64 = match arr.len().try_into() {
1290 Ok(len) => Ok(len),
1291 Err(_) => Err(Error::ArrayTooLarge(span)),
1292 }?;
1293 let (start, end) = if step > 0 {
1294 (start.unwrap_or(0), end.unwrap_or(len - 1))
1295 } else {
1296 (start.unwrap_or(len - 1), end.unwrap_or(0))
1297 };
1298
1299 let range = Range::new(start, step, end);
1300 let mut slice = vec![];
1301 for i in range {
1302 slice.push(index_array(arr, i, span)?);
1303 }
1304
1305 Ok(Value::Array(slice.into()))
1306 }
1307}
1308
1309fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value {
1310 match lhs_val {
1311 Value::Array(arr) => {
1312 let rhs_arr = rhs_val.unwrap_array();
1313 let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect();
1314 Value::Array(items.into())
1315 }
1316 Value::BigInt(val) => {
1317 let rhs = rhs_val.unwrap_big_int();
1318 Value::BigInt(val + rhs)
1319 }
1320 Value::Double(val) => {
1321 let rhs = rhs_val.unwrap_double();
1322 Value::Double(val + rhs)
1323 }
1324 Value::Int(val) => {
1325 let rhs = rhs_val.unwrap_int();
1326 Value::Int(val + rhs)
1327 }
1328 Value::String(val) => {
1329 let rhs = rhs_val.unwrap_string();
1330 Value::String((val.to_string() + &rhs).into())
1331 }
1332 _ => panic!("value is not addable"),
1333 }
1334}
1335
1336fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value {
1337 match lhs_val {
1338 Value::BigInt(val) => {
1339 let rhs = rhs_val.unwrap_big_int();
1340 Value::BigInt(val & rhs)
1341 }
1342 Value::Int(val) => {
1343 let rhs = rhs_val.unwrap_int();
1344 Value::Int(val & rhs)
1345 }
1346 _ => panic!("value type does not support andb"),
1347 }
1348}
1349
1350fn eval_binop_div(lhs_val: Value, rhs_val: Value, rhs_span: Span) -> Result<Value, Error> {
1351 match lhs_val {
1352 Value::BigInt(val) => {
1353 let rhs = rhs_val.unwrap_big_int();
1354 if rhs == BigInt::from(0) {
1355 Err(Error::DivZero(rhs_span))
1356 } else {
1357 Ok(Value::BigInt(val / rhs))
1358 }
1359 }
1360 Value::Int(val) => {
1361 let rhs = rhs_val.unwrap_int();
1362 if rhs == 0 {
1363 Err(Error::DivZero(rhs_span))
1364 } else {
1365 Ok(Value::Int(val / rhs))
1366 }
1367 }
1368 Value::Double(val) => {
1369 let rhs = rhs_val.unwrap_double();
1370 if rhs == 0.0 {
1371 Err(Error::DivZero(rhs_span))
1372 } else {
1373 Ok(Value::Double(val / rhs))
1374 }
1375 }
1376 _ => panic!("value should support div"),
1377 }
1378}
1379
1380fn eval_binop_exp(lhs_val: Value, rhs_val: Value, rhs_span: Span) -> Result<Value, Error> {
1381 match lhs_val {
1382 Value::BigInt(val) => {
1383 let rhs_val = rhs_val.unwrap_int();
1384 if rhs_val < 0 {
1385 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1386 } else {
1387 let rhs_val: u32 = match rhs_val.try_into() {
1388 Ok(v) => Ok(v),
1389 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1390 }?;
1391 Ok(Value::BigInt(val.pow(rhs_val)))
1392 }
1393 }
1394 Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))),
1395 Value::Int(val) => {
1396 let rhs_val = rhs_val.unwrap_int();
1397 if rhs_val < 0 {
1398 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
1399 } else {
1400 let rhs_val: u32 = match rhs_val.try_into() {
1401 Ok(v) => Ok(v),
1402 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
1403 }?;
1404 Ok(Value::Int(val.pow(rhs_val)))
1405 }
1406 }
1407 _ => panic!("value should support exp"),
1408 }
1409}
1410
1411fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value {
1412 match lhs_val {
1413 Value::BigInt(val) => {
1414 let rhs = rhs_val.unwrap_big_int();
1415 Value::Bool(val > rhs)
1416 }
1417 Value::Int(val) => {
1418 let rhs = rhs_val.unwrap_int();
1419 Value::Bool(val > rhs)
1420 }
1421 Value::Double(val) => {
1422 let rhs = rhs_val.unwrap_double();
1423 Value::Bool(val > rhs)
1424 }
1425 _ => panic!("value doesn't support binop gt"),
1426 }
1427}
1428
1429fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value {
1430 match lhs_val {
1431 Value::BigInt(val) => {
1432 let rhs = rhs_val.unwrap_big_int();
1433 Value::Bool(val >= rhs)
1434 }
1435 Value::Int(val) => {
1436 let rhs = rhs_val.unwrap_int();
1437 Value::Bool(val >= rhs)
1438 }
1439 Value::Double(val) => {
1440 let rhs = rhs_val.unwrap_double();
1441 Value::Bool(val >= rhs)
1442 }
1443 _ => panic!("value doesn't support binop gte"),
1444 }
1445}
1446
1447fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value {
1448 match lhs_val {
1449 Value::BigInt(val) => {
1450 let rhs = rhs_val.unwrap_big_int();
1451 Value::Bool(val < rhs)
1452 }
1453 Value::Int(val) => {
1454 let rhs = rhs_val.unwrap_int();
1455 Value::Bool(val < rhs)
1456 }
1457 Value::Double(val) => {
1458 let rhs = rhs_val.unwrap_double();
1459 Value::Bool(val < rhs)
1460 }
1461 _ => panic!("value doesn't support binop lt"),
1462 }
1463}
1464
1465fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value {
1466 match lhs_val {
1467 Value::BigInt(val) => {
1468 let rhs = rhs_val.unwrap_big_int();
1469 Value::Bool(val <= rhs)
1470 }
1471 Value::Int(val) => {
1472 let rhs = rhs_val.unwrap_int();
1473 Value::Bool(val <= rhs)
1474 }
1475 Value::Double(val) => {
1476 let rhs = rhs_val.unwrap_double();
1477 Value::Bool(val <= rhs)
1478 }
1479 _ => panic!("value doesn't support binop lte"),
1480 }
1481}
1482
1483fn eval_binop_mod(lhs_val: Value, rhs_val: Value) -> Value {
1484 match lhs_val {
1485 Value::BigInt(val) => {
1486 let rhs = rhs_val.unwrap_big_int();
1487 Value::BigInt(val % rhs)
1488 }
1489 Value::Int(val) => {
1490 let rhs = rhs_val.unwrap_int();
1491 Value::Int(val % rhs)
1492 }
1493 Value::Double(val) => {
1494 let rhs = rhs_val.unwrap_double();
1495 Value::Double(val % rhs)
1496 }
1497 _ => panic!("value should support mod"),
1498 }
1499}
1500
1501fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value {
1502 match lhs_val {
1503 Value::BigInt(val) => {
1504 let rhs = rhs_val.unwrap_big_int();
1505 Value::BigInt(val * rhs)
1506 }
1507 Value::Int(val) => {
1508 let rhs = rhs_val.unwrap_int();
1509 Value::Int(val * rhs)
1510 }
1511 Value::Double(val) => {
1512 let rhs = rhs_val.unwrap_double();
1513 Value::Double(val * rhs)
1514 }
1515 _ => panic!("value should support mul"),
1516 }
1517}
1518
1519fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value {
1520 match lhs_val {
1521 Value::BigInt(val) => {
1522 let rhs = rhs_val.unwrap_big_int();
1523 Value::BigInt(val | rhs)
1524 }
1525 Value::Int(val) => {
1526 let rhs = rhs_val.unwrap_int();
1527 Value::Int(val | rhs)
1528 }
1529 _ => panic!("value type does not support orb"),
1530 }
1531}
1532
1533fn eval_binop_shl(lhs_val: Value, rhs_val: Value) -> Value {
1534 match lhs_val {
1535 Value::BigInt(val) => {
1536 let rhs = rhs_val.unwrap_int();
1537 if rhs > 0 {
1538 Value::BigInt(val << rhs)
1539 } else {
1540 Value::BigInt(val >> rhs.abs())
1541 }
1542 }
1543 Value::Int(val) => {
1544 let rhs = rhs_val.unwrap_int();
1545 if rhs > 0 {
1546 Value::Int(val << rhs)
1547 } else {
1548 Value::Int(val >> rhs.abs())
1549 }
1550 }
1551 _ => panic!("value should support shl"),
1552 }
1553}
1554
1555fn eval_binop_shr(lhs_val: Value, rhs_val: Value) -> Value {
1556 match lhs_val {
1557 Value::BigInt(val) => {
1558 let rhs = rhs_val.unwrap_int();
1559 if rhs > 0 {
1560 Value::BigInt(val >> rhs)
1561 } else {
1562 Value::BigInt(val << rhs.abs())
1563 }
1564 }
1565 Value::Int(val) => {
1566 let rhs = rhs_val.unwrap_int();
1567 if rhs > 0 {
1568 Value::Int(val >> rhs)
1569 } else {
1570 Value::Int(val << rhs.abs())
1571 }
1572 }
1573 _ => panic!("value should support shr"),
1574 }
1575}
1576
1577fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value {
1578 match lhs_val {
1579 Value::BigInt(val) => {
1580 let rhs = rhs_val.unwrap_big_int();
1581 Value::BigInt(val - rhs)
1582 }
1583 Value::Double(val) => {
1584 let rhs = rhs_val.unwrap_double();
1585 Value::Double(val - rhs)
1586 }
1587 Value::Int(val) => {
1588 let rhs = rhs_val.unwrap_int();
1589 Value::Int(val - rhs)
1590 }
1591 _ => panic!("value is not subtractable"),
1592 }
1593}
1594
1595fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value {
1596 match lhs_val {
1597 Value::BigInt(val) => {
1598 let rhs = rhs_val.unwrap_big_int();
1599 Value::BigInt(val ^ rhs)
1600 }
1601 Value::Int(val) => {
1602 let rhs = rhs_val.unwrap_int();
1603 Value::Int(val ^ rhs)
1604 }
1605 _ => panic!("value type does not support xorb"),
1606 }
1607}
1608
1609fn update_functor_app(functor: Functor, app: FunctorApp) -> FunctorApp {
1610 match functor {
1611 Functor::Adj => FunctorApp {
1612 adjoint: !app.adjoint,
1613 controlled: app.controlled,
1614 },
1615 Functor::Ctl => FunctorApp {
1616 adjoint: app.adjoint,
1617 controlled: app.controlled + 1,
1618 },
1619 }
1620}
1621
1622fn follow_field_path(mut value: Value, path: &[usize]) -> Option<Value> {
1623 for &index in path {
1624 let Value::Tuple(items) = value else { return None; };
1625 value = items[index].clone();
1626 }
1627 Some(value)
1628}
1629
1630fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option<Value> {
1631 match (record, path) {
1632 (_, []) => Some(replace.clone()),
1633 (Value::Tuple(items), &[next_index, ..]) if next_index < items.len() => {
1634 let update = |(index, item)| {
1635 if index == next_index {
1636 update_field_path(item, &path[1..], replace)
1637 } else {
1638 Some(item.clone())
1639 }
1640 };
1641
1642 let items: Option<_> = items.iter().enumerate().map(update).collect();
1643 Some(Value::Tuple(items?))
1644 }
1645 _ => None,
1646 }
1647}
1648