GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.25.1

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/compiler/qsc_fir/src

source/compiler/qsc_fir/src/fir.rs

1899lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! The flattened intermediate representation for Q#. FIR is lowered from the HIR.
5//! The blocks, exprs, pats, and stmts from HIR are replaced with IDs that index into
6//! the corresponding lookups in the package. This allows for traversal without
7//! leaking references to the FIR nodes.
8
9#![warn(missing_docs)]
10
11use crate::ty::{Arrow, FunctorSet, FunctorSetValue, GenericArg, Scheme, Ty, TypeParameter, Udt};
12use indenter::{Indented, indented};
13use num_bigint::BigInt;
14use qsc_data_structures::{
15 index_map::{IndexMap, Iter},
16 span::Span,
17};
18use std::{
19 cmp::Ordering,
20 fmt::{self, Debug, Display, Formatter, Write},
21 hash::{Hash, Hasher},
22 ops,
23 rc::Rc,
24 result,
25 str::FromStr,
26};
27
28fn set_indentation<'a, 'b>(
29 indent: Indented<'a, Formatter<'b>>,
30 level: usize,
31) -> Indented<'a, Formatter<'b>> {
32 match level {
33 0 => indent.with_str(""),
34 1 => indent.with_str(" "),
35 2 => indent.with_str(" "),
36 _ => unimplemented!("indentation level not supported"),
37 }
38}
39
40/// A unique identifier for an FIR node.
41#[derive(Clone, Copy, Debug)]
42pub struct NodeId(u32);
43
44impl NodeId {
45 /// The ID of the first node.
46 pub const FIRST: Self = Self(0);
47
48 /// The successor of this ID.
49 #[must_use]
50 pub fn successor(self) -> Self {
51 Self(self.0 + 1)
52 }
53}
54
55impl Display for NodeId {
56 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
57 Display::fmt(&self.0, f)
58 }
59}
60
61impl From<NodeId> for usize {
62 fn from(value: NodeId) -> Self {
63 value.0 as usize
64 }
65}
66
67impl From<usize> for NodeId {
68 fn from(value: usize) -> Self {
69 NodeId(
70 value
71 .try_into()
72 .expect("Type Node ID does not fit into u32"),
73 )
74 }
75}
76
77impl From<NodeId> for u32 {
78 fn from(value: NodeId) -> Self {
79 value.0
80 }
81}
82
83impl From<u32> for NodeId {
84 fn from(value: u32) -> Self {
85 NodeId(value)
86 }
87}
88
89impl PartialEq for NodeId {
90 fn eq(&self, other: &Self) -> bool {
91 self.0 == other.0
92 }
93}
94
95impl Eq for NodeId {}
96
97impl PartialOrd for NodeId {
98 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
99 Some(self.cmp(other))
100 }
101}
102
103impl Ord for NodeId {
104 fn cmp(&self, other: &Self) -> Ordering {
105 self.0.cmp(&other.0)
106 }
107}
108
109impl Hash for NodeId {
110 fn hash<H: Hasher>(&self, state: &mut H) {
111 self.0.hash(state);
112 }
113}
114
115macro_rules! fir_id {
116 ($id:ident) => {
117 /// A unique identifier for an FIR node.
118 #[derive(Debug, Clone, Copy)]
119 pub struct $id(pub u32);
120
121 impl $id {
122 /// The successor of this ID.
123 #[must_use]
124 pub fn successor(self) -> Self {
125 Self(self.0 + 1)
126 }
127 }
128
129 impl Default for $id {
130 fn default() -> Self {
131 Self(0)
132 }
133 }
134
135 impl From<NodeId> for $id {
136 fn from(val: NodeId) -> Self {
137 $id(val.into())
138 }
139 }
140
141 impl From<$id> for NodeId {
142 fn from(val: $id) -> Self {
143 NodeId(val.into())
144 }
145 }
146
147 impl From<u32> for $id {
148 fn from(val: u32) -> Self {
149 $id(val)
150 }
151 }
152
153 impl From<$id> for u32 {
154 fn from(id: $id) -> Self {
155 id.0
156 }
157 }
158
159 impl From<$id> for usize {
160 fn from(value: $id) -> Self {
161 value.0 as usize
162 }
163 }
164
165 impl From<usize> for $id {
166 fn from(value: usize) -> Self {
167 $id(value.try_into().expect(&format!(
168 "Value, {}, does not fit into {}",
169 value,
170 stringify!($id)
171 )))
172 }
173 }
174
175 impl PartialEq for $id {
176 fn eq(&self, other: &Self) -> bool {
177 self.0 == other.0
178 }
179 }
180
181 impl Eq for $id {}
182
183 impl PartialOrd for $id {
184 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
185 Some(self.cmp(other))
186 }
187 }
188
189 impl Ord for $id {
190 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
191 self.0.cmp(&other.0)
192 }
193 }
194
195 impl std::hash::Hash for $id {
196 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
197 self.0.hash(state);
198 }
199 }
200
201 impl Display for $id {
202 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
203 Display::fmt(&self.0, f)
204 }
205 }
206 };
207}
208
209fir_id!(BlockId);
210fir_id!(ExprId);
211fir_id!(PatId);
212fir_id!(StmtId);
213fir_id!(LocalVarId);
214
215/// A unique identifier for a package within a package store.
216#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
217pub struct PackageId(usize);
218
219impl PackageId {
220 /// The package ID of the core library.
221 pub const CORE: Self = Self(0);
222
223 /// The successor of this ID.
224 #[must_use]
225 pub fn successor(self) -> Self {
226 Self(self.0 + 1)
227 }
228}
229
230impl Display for PackageId {
231 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
232 Display::fmt(&self.0, f)
233 }
234}
235
236impl From<PackageId> for usize {
237 fn from(value: PackageId) -> Self {
238 value.0
239 }
240}
241
242impl From<usize> for PackageId {
243 fn from(value: usize) -> Self {
244 PackageId(value)
245 }
246}
247
248/// A unique identifier for an item within a package.
249#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
250pub struct LocalItemId(usize);
251
252impl LocalItemId {
253 /// The successor of this ID.
254 #[must_use]
255 pub fn successor(self) -> Self {
256 Self(self.0 + 1)
257 }
258}
259
260impl Display for LocalItemId {
261 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
262 Display::fmt(&self.0, f)
263 }
264}
265
266impl From<usize> for LocalItemId {
267 fn from(value: usize) -> Self {
268 Self(value)
269 }
270}
271
272impl From<LocalItemId> for usize {
273 fn from(value: LocalItemId) -> Self {
274 value.0
275 }
276}
277
278/// A unique identifier for an item within a package store.
279#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
280pub struct ItemId {
281 /// The package ID or `None` for the local package.
282 pub package: PackageId,
283 /// The item ID.
284 pub item: LocalItemId,
285}
286
287impl Display for ItemId {
288 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
289 write!(f, "Item {} (Package {})", self.item, self.package)
290 }
291}
292
293/// A resolution. This connects a usage of a name with the declaration of that name by uniquely
294/// identifying the node that declared it.
295#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
296pub enum Res {
297 /// An invalid resolution.
298 Err,
299 /// A global item.
300 Item(ItemId),
301 /// A local variable.
302 Local(LocalVarId),
303}
304
305impl Display for Res {
306 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
307 match self {
308 Res::Err => f.write_str("Err"),
309 Res::Item(item) => Display::fmt(item, f),
310 Res::Local(node) => write!(f, "Local {node}"),
311 }
312 }
313}
314
315/// A global item.
316pub enum Global<'a> {
317 /// A global callable.
318 Callable(&'a CallableDecl),
319 /// A global user-defined type.
320 Udt,
321}
322
323/// A unique identifier for an item within a package store.
324#[derive(Clone, Copy, Debug, PartialEq, Hash, Eq)]
325pub struct StoreItemId {
326 /// The package ID.
327 pub package: PackageId,
328 /// The item ID.
329 pub item: LocalItemId,
330}
331
332impl StoreItemId {
333 /// The item ID for the Complex type in the core library.
334 #[must_use]
335 pub fn complex() -> Self {
336 Self {
337 package: PackageId::CORE,
338 item: LocalItemId(3),
339 }
340 }
341}
342
343impl Display for StoreItemId {
344 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
345 write!(f, "<item {} in package {}>", self.item, self.package)
346 }
347}
348
349impl From<(PackageId, LocalItemId)> for StoreItemId {
350 fn from(tuple: (PackageId, LocalItemId)) -> Self {
351 Self {
352 package: tuple.0,
353 item: tuple.1,
354 }
355 }
356}
357
358/// A unique identifier for a block within a package store.
359#[derive(Clone, Copy, Debug, PartialEq)]
360pub struct StoreBlockId {
361 /// The package ID.
362 pub package: PackageId,
363 /// The item ID.
364 pub block: BlockId,
365}
366
367impl Display for StoreBlockId {
368 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
369 write!(f, "<block {} in package {}>", self.block, self.package)
370 }
371}
372
373impl From<(PackageId, BlockId)> for StoreBlockId {
374 fn from(tuple: (PackageId, BlockId)) -> Self {
375 Self {
376 package: tuple.0,
377 block: tuple.1,
378 }
379 }
380}
381
382/// A unique identifier for an expression within a package store.
383#[derive(Clone, Copy, Debug, PartialEq)]
384pub struct StoreExprId {
385 /// The package ID.
386 pub package: PackageId,
387 /// The expression ID.
388 pub expr: ExprId,
389}
390
391impl Display for StoreExprId {
392 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
393 write!(f, "<expression {} in package {}>", self.expr, self.package)
394 }
395}
396
397impl From<(PackageId, ExprId)> for StoreExprId {
398 fn from(tuple: (PackageId, ExprId)) -> Self {
399 Self {
400 package: tuple.0,
401 expr: tuple.1,
402 }
403 }
404}
405
406/// A unique identifier for a pattern within a package store.
407#[derive(Clone, Copy, Debug, PartialEq)]
408pub struct StorePatId {
409 /// The package ID.
410 pub package: PackageId,
411 /// The pat ID.
412 pub pat: PatId,
413}
414
415impl Display for StorePatId {
416 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
417 write!(f, "<pattern {} in package {}>", self.pat, self.package)
418 }
419}
420
421impl From<(PackageId, PatId)> for StorePatId {
422 fn from(tuple: (PackageId, PatId)) -> Self {
423 Self {
424 package: tuple.0,
425 pat: tuple.1,
426 }
427 }
428}
429
430/// A unique identifier for a statement within a package store.
431#[derive(Clone, Copy, Debug, PartialEq)]
432pub struct StoreStmtId {
433 /// The package ID.
434 pub package: PackageId,
435 /// The statement ID.
436 pub stmt: StmtId,
437}
438
439impl Display for StoreStmtId {
440 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
441 write!(f, "<pattern {} in package {}>", self.stmt, self.package)
442 }
443}
444
445impl From<(PackageId, StmtId)> for StoreStmtId {
446 fn from(tuple: (PackageId, StmtId)) -> Self {
447 Self {
448 package: tuple.0,
449 stmt: tuple.1,
450 }
451 }
452}
453
454/// A trait to find elements in a package store.
455pub trait PackageStoreLookup {
456 /// Gets a block.
457 fn get_block(&self, id: StoreBlockId) -> &Block;
458 /// Gets an expression.
459 fn get_expr(&self, id: StoreExprId) -> &Expr;
460 /// Gets a global.
461 fn get_global(&self, id: StoreItemId) -> Option<Global<'_>>;
462 /// Gets a pat.
463 fn get_pat(&self, id: StorePatId) -> &Pat;
464 /// Gets a statement.
465 fn get_stmt(&self, id: StoreStmtId) -> &Stmt;
466 /// Gets an item.
467 fn get_item(&self, id: StoreItemId) -> &Item;
468}
469
470/// A FIR package store.
471#[derive(Debug, Default)]
472pub struct PackageStore(IndexMap<PackageId, Package>);
473
474impl PackageStoreLookup for PackageStore {
475 fn get_block(&self, id: StoreBlockId) -> &Block {
476 self.get(id.package).get_block(id.block)
477 }
478
479 fn get_expr(&self, id: StoreExprId) -> &Expr {
480 self.get(id.package).get_expr(id.expr)
481 }
482
483 fn get_global(&self, id: StoreItemId) -> Option<Global<'_>> {
484 self.get(id.package).get_global(id.item)
485 }
486
487 fn get_pat(&self, id: StorePatId) -> &Pat {
488 self.get(id.package).get_pat(id.pat)
489 }
490
491 fn get_stmt(&self, id: StoreStmtId) -> &Stmt {
492 self.get(id.package).get_stmt(id.stmt)
493 }
494
495 fn get_item(&self, id: StoreItemId) -> &Item {
496 self.get(id.package).get_item(id.item)
497 }
498}
499
500impl PackageStore {
501 /// Gets a package from the store.
502 #[must_use]
503 pub fn get(&self, id: PackageId) -> &Package {
504 self.0.get(id).expect("store should have package")
505 }
506
507 /// Gets a mutable package from the store.
508 #[must_use]
509 pub fn get_mut(&mut self, id: PackageId) -> &mut Package {
510 self.0.get_mut(id).expect("store should have package")
511 }
512
513 /// Inserts a package to the store.
514 pub fn insert(&mut self, id: PackageId, package: Package) {
515 self.0.insert(id, package);
516 }
517
518 /// Gets a package store iterator.
519 #[must_use]
520 pub fn iter(&self) -> Iter<'_, PackageId, Package> {
521 self.0.iter()
522 }
523
524 /// Creates a package store.
525 #[must_use]
526 pub fn new() -> Self {
527 Self::default()
528 }
529}
530
531impl<'a> IntoIterator for &'a PackageStore {
532 type IntoIter = qsc_data_structures::index_map::Iter<'a, PackageId, Package>;
533 type Item = (PackageId, &'a Package);
534
535 fn into_iter(self) -> Self::IntoIter {
536 self.iter()
537 }
538}
539
540/// A trait to find elements in a package.
541pub trait PackageLookup {
542 /// Gets a block.
543 fn get_block(&self, id: BlockId) -> &Block;
544 /// Gets an expression.
545 fn get_expr(&self, id: ExprId) -> &Expr;
546 /// Gets a global.
547 fn get_global(&self, id: LocalItemId) -> Option<Global<'_>>;
548 /// Gets an item.
549 fn get_item(&self, id: LocalItemId) -> &Item;
550 /// Gets a pat.
551 fn get_pat(&self, id: PatId) -> &Pat;
552 /// Gets a statement.
553 fn get_stmt(&self, id: StmtId) -> &Stmt;
554}
555
556/// The root node of the FIR.
557/// ### Notes
558/// We maintain a dense map of ids within the package.
559/// `BlockId`, `ExprId`, `PatId`, `StmtId`, and `NodeId`s are all assigned
560/// from a type specific counter in the assigner.
561///
562/// `BlockId`, `ExprId`, `PatId`, `StmtId` ids don't leak and are only used
563/// within the containing node. Node ids are used to identify nodes within
564/// the package and require mapping from the HIR node id to the new FIR node id.
565/// `PackageId`s and `LocalItemId`s are 1:1 from the HIR and are not remapped.
566#[derive(Debug)]
567pub struct Package {
568 /// The items in the package.
569 pub items: IndexMap<LocalItemId, Item>,
570 /// The entry expression for an executable package.
571 pub entry: Option<ExprId>,
572 /// The control flow graph for the entry expression in the package.
573 pub entry_exec_graph: ExecGraph,
574 /// The blocks in the package.
575 pub blocks: IndexMap<BlockId, Block>,
576 /// The expressions in the package.
577 pub exprs: IndexMap<ExprId, Expr>,
578 /// The patterns in the package.
579 pub pats: IndexMap<PatId, Pat>,
580 /// The statements in the package.
581 pub stmts: IndexMap<StmtId, Stmt>,
582}
583
584impl Display for Package {
585 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
586 let mut indent = set_indentation(indented(f), 0);
587 write!(indent, "Package:")?;
588 indent = set_indentation(indent, 1);
589 if let Some(e) = &self.entry {
590 write!(indent, "\nEntry Expression: {e}")?;
591 }
592
593 write!(indent, "\nItems:")?;
594 indent = set_indentation(indent, 2);
595 for item in self.items.values() {
596 write!(indent, "\n{item}")?;
597 }
598
599 indent = set_indentation(indent, 1);
600 write!(indent, "\nBlocks:")?;
601 indent = set_indentation(indent, 2);
602 for block in self.blocks.values() {
603 write!(indent, "\n{block}")?;
604 }
605
606 indent = set_indentation(indent, 1);
607 write!(indent, "\nStmts:")?;
608 indent = set_indentation(indent, 2);
609 for stmt in self.stmts.values() {
610 write!(indent, "\n{stmt}")?;
611 }
612
613 indent = set_indentation(indent, 1);
614 write!(indent, "\nExprs:")?;
615 indent = set_indentation(indent, 2);
616 for expr in self.exprs.values() {
617 write!(indent, "\n{expr}")?;
618 }
619
620 indent = set_indentation(indent, 1);
621 write!(indent, "\nPats:")?;
622 indent = set_indentation(indent, 2);
623 for pat in self.pats.values() {
624 write!(indent, "\n{pat}")?;
625 }
626 Ok(())
627 }
628}
629
630impl PackageLookup for Package {
631 fn get_block(&self, id: BlockId) -> &Block {
632 self.blocks.get(id).expect("Block not found")
633 }
634
635 fn get_expr(&self, id: ExprId) -> &Expr {
636 self.exprs.get(id).expect("Expression not found")
637 }
638
639 fn get_global(&self, id: LocalItemId) -> Option<Global<'_>> {
640 match &self.items.get(id)?.kind {
641 ItemKind::Callable(callable) => Some(Global::Callable(callable)),
642 ItemKind::Namespace(..) => None,
643 ItemKind::Ty(..) => Some(Global::Udt),
644 ItemKind::Export(_name, _id) => None,
645 }
646 }
647
648 fn get_item(&self, id: LocalItemId) -> &Item {
649 self.items.get(id).expect("Item not found")
650 }
651
652 fn get_pat(&self, id: PatId) -> &Pat {
653 self.pats.get(id).expect("Pattern not found")
654 }
655
656 fn get_stmt(&self, id: StmtId) -> &Stmt {
657 self.stmts.get(id).expect("Statement not found")
658 }
659}
660
661/// An item.
662#[derive(Clone, Debug, PartialEq)]
663pub struct Item {
664 /// The ID.
665 pub id: LocalItemId,
666 /// The span.
667 pub span: Span,
668 /// The parent item.
669 pub parent: Option<LocalItemId>,
670 /// The documentation.
671 pub doc: Rc<str>,
672 /// The attributes.
673 pub attrs: Vec<Attr>,
674 /// The visibility.
675 pub visibility: Visibility,
676 /// The item kind.
677 pub kind: ItemKind,
678}
679
680impl Display for Item {
681 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
682 let mut indent = set_indentation(indented(f), 0);
683 write!(
684 indent,
685 "Item {} {} ({:?}):",
686 self.id, self.span, self.visibility
687 )?;
688
689 indent = set_indentation(indent, 1);
690 if let Some(parent) = self.parent {
691 write!(indent, "\nParent: {parent}")?;
692 }
693
694 if !self.doc.is_empty() {
695 write!(indent, "\nDoc:")?;
696 indent = set_indentation(indent, 2);
697 write!(indent, "\n{}", self.doc)?;
698 indent = set_indentation(indent, 1);
699 }
700
701 for attr in &self.attrs {
702 write!(indent, "\n{attr:?}")?;
703 }
704
705 write!(indent, "\n{}", self.kind)?;
706 Ok(())
707 }
708}
709
710/// An item kind.
711#[derive(Clone, Debug, PartialEq)]
712pub enum ItemKind {
713 /// A `function` or `operation` declaration.
714 Callable(Box<CallableDecl>),
715 /// A `namespace` declaration.
716 Namespace(Ident, Vec<LocalItemId>),
717 /// A `newtype` declaration.
718 Ty(Ident, Udt),
719 /// An export referring to another item
720 Export(Ident, Res),
721}
722
723impl Display for ItemKind {
724 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
725 match self {
726 ItemKind::Callable(decl) => write!(f, "{decl}"),
727 ItemKind::Namespace(name, items) => {
728 write!(f, "Namespace ({name}):")?;
729 let mut items = items.iter();
730 if let Some(item) = items.next() {
731 write!(f, " Item {item}")?;
732 for item in items {
733 write!(f, ", Item {item}")?;
734 }
735 Ok(())
736 } else {
737 write!(f, " <empty>")
738 }
739 }
740 ItemKind::Ty(name, udt) => write!(f, "Type ({name}): {udt}"),
741 ItemKind::Export(name, item) => write!(f, "Export ({name}): {item}"),
742 }
743 }
744}
745
746/// A callable declaration header.
747#[derive(Clone, Debug, PartialEq)]
748pub struct CallableDecl {
749 /// The node ID.
750 pub id: NodeId,
751 /// The span.
752 pub span: Span,
753 /// The callable kind.
754 pub kind: CallableKind,
755 /// The name of the callable.
756 pub name: Ident,
757 /// The generic parameters to the callable.
758 pub generics: Vec<TypeParameter>,
759 /// The input to the callable.
760 pub input: PatId,
761 /// The return type of the callable.
762 pub output: Ty,
763 /// The functors supported by the callable.
764 pub functors: FunctorSetValue,
765 /// The callable implementation.
766 pub implementation: CallableImpl,
767 /// The attributes of the callable, (e.g.: Measurement or Reset).
768 pub attrs: Vec<Attr>,
769}
770
771impl CallableDecl {
772 /// The type scheme of the callable.
773 #[must_use]
774 pub fn scheme<'a>(&self, f: impl Fn(PatId) -> &'a Pat) -> Scheme {
775 Scheme::new(
776 self.generics.clone(),
777 Box::new(Arrow {
778 kind: self.kind,
779 input: Box::new(f(self.input).ty.clone()),
780 output: Box::new(self.output.clone()),
781 functors: FunctorSet::Value(self.functors),
782 }),
783 )
784 }
785}
786
787impl Display for CallableDecl {
788 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
789 let mut indent = set_indentation(indented(f), 0);
790 write!(
791 indent,
792 "Callable {} {} ({}):",
793 self.id, self.span, self.kind
794 )?;
795 indent = set_indentation(indent, 1);
796 write!(indent, "\nname: {}", self.name)?;
797 if !self.generics.is_empty() {
798 write!(indent, "\ngenerics:")?;
799 indent = set_indentation(indent, 2);
800 for (ix, param) in self.generics.iter().enumerate() {
801 write!(indent, "\n{ix}: {param}")?;
802 }
803 indent = set_indentation(indent, 1);
804 }
805 write!(indent, "\ninput: {}", self.input)?;
806 write!(indent, "\noutput: {}", self.output)?;
807 write!(indent, "\nfunctors: {}", self.functors)?;
808 write!(indent, "\nimplementation: {}", self.implementation)?;
809 Ok(())
810 }
811}
812
813/// A callable implementations.
814#[derive(Clone, Debug, PartialEq)]
815pub enum CallableImpl {
816 /// An intrinsic callable implementation.
817 Intrinsic,
818 /// A specialized callable implementation.
819 Spec(SpecImpl),
820 /// An intrinsic with a simulation override.
821 SimulatableIntrinsic(SpecDecl),
822}
823
824impl Display for CallableImpl {
825 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
826 let mut indent = set_indentation(indented(f), 0);
827 match self {
828 CallableImpl::Intrinsic => {
829 write!(indent, "Instrinsic")?;
830 }
831 CallableImpl::Spec(spec_impl) => {
832 write!(indent, "Spec:")?;
833 indent = set_indentation(indent, 1);
834 write!(indent, "\n{spec_impl}")?;
835 }
836 CallableImpl::SimulatableIntrinsic(spec_decl) => {
837 write!(indent, "SimulatableIntrinsic:")?;
838 indent = set_indentation(indent, 1);
839 write!(indent, "\n{spec_decl}")?;
840 }
841 }
842
843 Ok(())
844 }
845}
846
847/// A specialized implementation.
848#[derive(Clone, Debug, PartialEq)]
849pub struct SpecImpl {
850 /// The body implementation.
851 pub body: SpecDecl,
852 /// The adjoint specialization.
853 pub adj: Option<SpecDecl>,
854 /// The controlled specialization.
855 pub ctl: Option<SpecDecl>,
856 /// The controlled adjoint specialization.
857 pub ctl_adj: Option<SpecDecl>,
858}
859
860impl Display for SpecImpl {
861 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
862 let mut indent = set_indentation(indented(f), 0);
863 write!(indent, "SpecImpl:")?;
864 indent = set_indentation(indent, 1);
865 write!(indent, "\nbody: {}", self.body)?;
866 match &self.adj {
867 Some(spec) => write!(indent, "\nadj: {spec}")?,
868 None => write!(indent, "\nadj: <none>")?,
869 }
870 match &self.ctl {
871 Some(spec) => write!(indent, "\nctl: {spec}")?,
872 None => write!(indent, "\nctl: <none>")?,
873 }
874 match &self.ctl_adj {
875 Some(spec) => write!(indent, "\nctl-adj: {spec}")?,
876 None => write!(indent, "\nctl-adj: <none>")?,
877 }
878 Ok(())
879 }
880}
881
882/// A specialization declaration.
883#[derive(Clone, Debug, PartialEq)]
884pub struct SpecDecl {
885 /// The node ID.
886 pub id: NodeId,
887 /// The span.
888 pub span: Span,
889 /// The block that implements the specialization.
890 pub block: BlockId,
891 /// The input of the specialization.
892 pub input: Option<PatId>,
893 /// The flattened control flow graph for the execution of the specialization.
894 pub exec_graph: ExecGraph,
895}
896
897impl Display for SpecDecl {
898 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
899 write!(
900 f,
901 "SpecDecl {} {}: {:?} {}",
902 self.id, self.span, self.input, self.block
903 )
904 }
905}
906
907#[derive(Clone, PartialEq, Debug, Default)]
908/// A multi-configuration execution graph, containing both a debug and no-debug version.
909pub struct ExecGraph {
910 /// Execution graph without any debug nodes.
911 no_debug: ConfiguredExecGraph,
912 /// Execution graph with debug nodes.
913 debug: ConfiguredExecGraph,
914}
915
916impl ExecGraph {
917 #[must_use]
918 /// Creates a new multi-configuration execution graph.
919 pub fn new(
920 no_debug_exec_graph: ConfiguredExecGraph,
921 debug_exec_graph: ConfiguredExecGraph,
922 ) -> Self {
923 Self {
924 no_debug: no_debug_exec_graph,
925 debug: debug_exec_graph,
926 }
927 }
928
929 #[must_use]
930 /// Selects the execution graph based on the configuration.
931 pub fn select(self, exec_graph_config: ExecGraphConfig) -> ConfiguredExecGraph {
932 match exec_graph_config {
933 ExecGraphConfig::Debug => self.debug,
934 ExecGraphConfig::NoDebug => self.no_debug,
935 }
936 }
937
938 #[must_use]
939 /// Selects the execution graph based on the configuration.
940 fn select_ref(&self, exec_graph_config: ExecGraphConfig) -> &ConfiguredExecGraph {
941 match exec_graph_config {
942 ExecGraphConfig::Debug => &self.debug,
943 ExecGraphConfig::NoDebug => &self.no_debug,
944 }
945 }
946
947 /// Utility function to identify a subset of a control flow graph corresponding to a given
948 /// range.
949 #[must_use]
950 pub fn get_range(&self, range: &ops::Range<ExecGraphIdx>) -> ExecGraph {
951 let get = |config: ExecGraphConfig| -> ConfiguredExecGraph {
952 let start: u32 = range
953 .start
954 .select(config)
955 .try_into()
956 .expect("exec graph ranges should fit into u32");
957 self.select_ref(config)[range.start.select(config)..range.end.select(config)]
958 .iter()
959 .map(|node| match node {
960 ExecGraphNode::Jump(idx) => ExecGraphNode::Jump(idx - start),
961 ExecGraphNode::JumpIf(idx) => ExecGraphNode::JumpIf(idx - start),
962 ExecGraphNode::JumpIfNot(idx) => ExecGraphNode::JumpIfNot(idx - start),
963 _ => *node,
964 })
965 .collect::<Vec<_>>()
966 .into()
967 };
968
969 ExecGraph {
970 no_debug: get(ExecGraphConfig::NoDebug),
971 debug: get(ExecGraphConfig::Debug),
972 }
973 }
974}
975
976#[derive(Clone, Copy)]
977/// The execution graph configuration.
978pub enum ExecGraphConfig {
979 /// Execution graph with debug nodes.
980 Debug,
981 /// Execution graph without debug nodes.
982 NoDebug,
983}
984
985#[derive(Clone, Copy, Debug, PartialEq)]
986/// An index into a multi-configuration execution graph.
987pub struct ExecGraphIdx {
988 /// The index into the no-debug execution graph.
989 pub no_debug_idx: usize,
990 /// The index into the debug execution graph.
991 pub debug_idx: usize,
992}
993
994impl ExecGraphIdx {
995 /// Selects the index based on the configuration.
996 fn select(self, exec_graph_config: ExecGraphConfig) -> usize {
997 match exec_graph_config {
998 ExecGraphConfig::Debug => self.debug_idx,
999 ExecGraphConfig::NoDebug => self.no_debug_idx,
1000 }
1001 }
1002}
1003
1004impl std::ops::Add<usize> for ExecGraphIdx {
1005 type Output = Self;
1006
1007 fn add(self, rhs: usize) -> Self::Output {
1008 Self {
1009 no_debug_idx: self.no_debug_idx + rhs,
1010 debug_idx: self.debug_idx + rhs,
1011 }
1012 }
1013}
1014
1015/// An execution graph represented by a reference counted vector of nodes.
1016pub type ConfiguredExecGraph = Rc<[ExecGraphNode]>;
1017
1018#[derive(Copy, Clone, Debug, PartialEq)]
1019/// A node within the control flow graph.
1020pub enum ExecGraphNode {
1021 /// A binding of a value to a variable.
1022 Bind(PatId),
1023 /// An expression to execute.
1024 Expr(ExprId),
1025 /// An unconditional jump with to given location.
1026 Jump(u32),
1027 /// A conditional jump with to given location, where the jump is only taken if the condition is
1028 /// true.
1029 JumpIf(u32),
1030 /// A conditional jump with to given location, where the jump is only taken if the condition is
1031 /// false.
1032 JumpIfNot(u32),
1033 /// An indication that the current accumulated result value should be stored into the value stack.
1034 Store,
1035 /// A no-op Unit node that tells execution to insert a unit value into the current accumulated result.
1036 Unit,
1037 /// The end of the control flow graph.
1038 Ret,
1039 /// A node only to be executed in debug mode.
1040 Debug(ExecGraphDebugNode),
1041}
1042
1043#[derive(Copy, Clone, Debug, PartialEq)]
1044/// A debug-only node within the control flow graph.
1045pub enum ExecGraphDebugNode {
1046 /// A statement to track for debugging.
1047 Stmt(StmtId),
1048 /// A push of a new scope.
1049 PushScope,
1050 /// A push of a new loop scope. The `ExprId` is the condition or iterable expression.
1051 PushLoopScope(ExprId),
1052 /// A pop of the current scope. Loop scopes are also popped with this node.
1053 PopScope,
1054 /// The end of a block, used in debugging to have a step point after all statements in a block have been executed,
1055 /// but before the block is exited.
1056 BlockEnd(BlockId),
1057 /// The end of the control flow graph plus a pop of the current debug frame. Used instead of `Ret`
1058 /// when debugging.
1059 RetFrame,
1060 /// The beginning of a loop iteration.
1061 LoopIteration,
1062}
1063
1064/// A sequenced block of statements.
1065#[derive(Clone, Debug, PartialEq)]
1066pub struct Block {
1067 /// The node ID.
1068 pub id: BlockId,
1069 /// The span.
1070 pub span: Span,
1071 /// The block type.
1072 pub ty: Ty,
1073 /// The statements in the block.
1074 pub stmts: Vec<StmtId>,
1075}
1076
1077impl Display for Block {
1078 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1079 if self.stmts.is_empty() {
1080 write!(f, "Block {} {}: <empty>", self.id, self.span)?;
1081 } else {
1082 let mut indent = set_indentation(indented(f), 0);
1083 write!(
1084 indent,
1085 "Block {} {} [Type {}]:",
1086 self.id, self.span, self.ty
1087 )?;
1088 indent = set_indentation(indent, 1);
1089 for s in &self.stmts {
1090 write!(indent, "\n{s}")?;
1091 }
1092 }
1093 Ok(())
1094 }
1095}
1096
1097/// A statement.
1098#[derive(Clone, Debug, PartialEq)]
1099pub struct Stmt {
1100 /// The stmt ID.
1101 pub id: StmtId,
1102 /// The span.
1103 pub span: Span,
1104 /// The statement kind.
1105 pub kind: StmtKind,
1106 /// The locations within the containing control flow graph for the current statement.
1107 pub exec_graph_range: ops::Range<ExecGraphIdx>,
1108}
1109
1110impl Display for Stmt {
1111 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1112 write!(f, "Stmt {} {}: {}", self.id, self.span, self.kind)
1113 }
1114}
1115
1116/// A statement kind.
1117#[derive(Clone, Debug, PartialEq)]
1118pub enum StmtKind {
1119 /// An expression without a trailing semicolon.
1120 Expr(ExprId),
1121 /// An item.
1122 Item(LocalItemId),
1123 /// A let or mutable binding: `let a = b;` or `mutable x = b;`.
1124 Local(Mutability, PatId, ExprId),
1125 /// An expression with a trailing semicolon.
1126 Semi(ExprId),
1127}
1128
1129impl Display for StmtKind {
1130 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1131 let mut indent = set_indentation(indented(f), 0);
1132 match self {
1133 StmtKind::Expr(e) => write!(indent, "Expr: {e}")?,
1134 StmtKind::Item(item) => write!(indent, "Item: {item}")?,
1135 StmtKind::Local(m, lhs, rhs) => {
1136 write!(indent, "Local ({m:?}):")?;
1137 indent = set_indentation(indent, 1);
1138 write!(indent, "\n{lhs}")?;
1139 write!(indent, "\n{rhs}")?;
1140 }
1141 StmtKind::Semi(e) => write!(indent, "Semi: {e}")?,
1142 }
1143 Ok(())
1144 }
1145}
1146
1147/// An expression.
1148#[derive(Clone, Debug, PartialEq)]
1149pub struct Expr {
1150 /// The expr ID.
1151 pub id: ExprId,
1152 /// The span.
1153 pub span: Span,
1154 /// The expression type.
1155 pub ty: Ty,
1156 /// The expression kind.
1157 pub kind: ExprKind,
1158 /// The locations within the containing control flow graph for the current expression.
1159 pub exec_graph_range: ops::Range<ExecGraphIdx>,
1160}
1161
1162impl Display for Expr {
1163 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1164 write!(
1165 f,
1166 "Expr {} {} [Type {}]: {}",
1167 self.id, self.span, self.ty, self.kind
1168 )
1169 }
1170}
1171
1172/// An expression kind.
1173#[derive(Clone, Debug, PartialEq)]
1174pub enum ExprKind {
1175 /// An array: `[a, b, c]`.
1176 Array(Vec<ExprId>),
1177 /// An array of literal values, ie: `[1, 2, 3]`.
1178 ArrayLit(Vec<ExprId>),
1179 /// An array constructed by repeating a value: `[a, size = b]`.
1180 ArrayRepeat(ExprId, ExprId),
1181 /// An assignment: `set a = b`.
1182 Assign(ExprId, ExprId),
1183 /// An assignment with a compound operator. For example: `set a += b`.
1184 AssignOp(BinOp, ExprId, ExprId),
1185 /// An assignment with a compound field update operator: `set a w/= B <- c`.
1186 AssignField(ExprId, Field, ExprId),
1187 /// An assignment with a compound index update operator: `set a w/= b <- c`.
1188 AssignIndex(ExprId, ExprId, ExprId),
1189 /// A binary operator.
1190 BinOp(BinOp, ExprId, ExprId),
1191 /// A block: `{ ... }`.
1192 Block(BlockId),
1193 /// A call: `a(b)`.
1194 Call(ExprId, ExprId),
1195 /// A closure that fixes the vector of local variables as arguments to the callable item.
1196 Closure(Vec<LocalVarId>, LocalItemId),
1197 /// A failure: `fail "message"`.
1198 Fail(ExprId),
1199 /// A field accessor: `a::F` or `a.F`.
1200 Field(ExprId, Field),
1201 /// An unspecified expression, _, which may indicate partial application or discards
1202 Hole,
1203 /// An if expression with an optional else block: `if a { ... } else { ... }`.
1204 ///
1205 /// Note that, as a special case, `elif ...` is effectively parsed as `else if ...`, without a
1206 /// block wrapping the `if`. This distinguishes `elif ...` from `else { if ... }`, which does
1207 /// have a block.
1208 If(ExprId, ExprId, Option<ExprId>),
1209 /// An index accessor: `a[b]`.
1210 Index(ExprId, ExprId),
1211 /// A literal.
1212 Lit(Lit),
1213 /// A range: `start..step..end`, `start..end`, `start...`, `...end`, or `...`.
1214 Range(Option<ExprId>, Option<ExprId>, Option<ExprId>),
1215 /// A return: `return a`.
1216 Return(ExprId),
1217 /// A struct constructor.
1218 Struct(Res, Option<ExprId>, Vec<FieldAssign>),
1219 /// A string.
1220 String(Vec<StringComponent>),
1221 /// Update array index: `a w/ b <- c`.
1222 UpdateIndex(ExprId, ExprId, ExprId),
1223 /// A tuple: `(a, b, c)`.
1224 Tuple(Vec<ExprId>),
1225 /// A unary operator.
1226 UnOp(UnOp, ExprId),
1227 /// A record field update: `a w/ B <- c`.
1228 UpdateField(ExprId, Field, ExprId),
1229 /// A variable and its generic arguments.
1230 Var(Res, Vec<GenericArg>),
1231 /// A while loop: `while a { ... }`.
1232 While(ExprId, BlockId),
1233}
1234
1235impl Display for ExprKind {
1236 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1237 let mut indent = set_indentation(indented(f), 0);
1238 match self {
1239 ExprKind::Array(exprs) | ExprKind::ArrayLit(exprs) => display_array(indent, exprs)?,
1240 ExprKind::ArrayRepeat(val, size) => display_array_repeat(indent, *val, *size)?,
1241 ExprKind::Assign(lhs, rhs) => display_assign(indent, *lhs, *rhs)?,
1242 ExprKind::AssignOp(op, lhs, rhs) => display_assign_op(indent, *op, *lhs, *rhs)?,
1243 ExprKind::AssignField(record, field, replace) => {
1244 display_assign_field(indent, *record, field, *replace)?;
1245 }
1246 ExprKind::AssignIndex(container, item, replace) => {
1247 display_assign_index(indent, *container, *item, *replace)?;
1248 }
1249 ExprKind::BinOp(op, lhs, rhs) => display_bin_op(indent, *op, *lhs, *rhs)?,
1250 ExprKind::Block(block) => write!(indent, "Expr Block: {block}")?,
1251 ExprKind::Call(callable, arg) => display_call(indent, *callable, *arg)?,
1252 ExprKind::Closure(args, callable) => display_closure(indent, args, *callable)?,
1253 ExprKind::Fail(e) => write!(indent, "Fail: {e}")?,
1254 ExprKind::Field(expr, field) => display_field(indent, *expr, field)?,
1255 ExprKind::Hole => write!(indent, "Hole")?,
1256 ExprKind::If(cond, body, els) => display_if(indent, *cond, *body, *els)?,
1257 ExprKind::Index(array, index) => display_index(indent, *array, *index)?,
1258 ExprKind::Lit(lit) => write!(indent, "Lit: {lit}")?,
1259 ExprKind::Range(start, step, end) => display_range(indent, *start, *step, *end)?,
1260 ExprKind::Return(e) => write!(indent, "Return: {e}")?,
1261 ExprKind::Struct(name, copy, fields) => display_struct(indent, name, *copy, fields)?,
1262 ExprKind::String(components) => display_string(indent, components)?,
1263 ExprKind::UpdateIndex(expr1, expr2, expr3) => {
1264 display_update_index(indent, *expr1, *expr2, *expr3)?;
1265 }
1266 ExprKind::Tuple(exprs) => display_tuple(indent, exprs)?,
1267 ExprKind::UnOp(op, expr) => display_un_op(indent, *op, *expr)?,
1268 ExprKind::UpdateField(record, field, replace) => {
1269 display_update_field(indent, *record, field, *replace)?;
1270 }
1271 ExprKind::Var(res, args) => display_var(indent, *res, args)?,
1272 ExprKind::While(cond, block) => display_while(indent, *cond, *block)?,
1273 }
1274 Ok(())
1275 }
1276}
1277
1278fn display_array(mut indent: Indented<Formatter>, exprs: &Vec<ExprId>) -> fmt::Result {
1279 write!(indent, "Array:")?;
1280 indent = set_indentation(indent, 1);
1281 for e in exprs {
1282 write!(indent, "\n{e}")?;
1283 }
1284 Ok(())
1285}
1286
1287fn display_array_repeat(mut indent: Indented<Formatter>, val: ExprId, size: ExprId) -> fmt::Result {
1288 write!(indent, "ArrayRepeat:")?;
1289 indent = set_indentation(indent, 1);
1290 write!(indent, "\n{val}")?;
1291 write!(indent, "\n{size}")?;
1292 Ok(())
1293}
1294
1295fn display_assign(mut indent: Indented<Formatter>, lhs: ExprId, rhs: ExprId) -> fmt::Result {
1296 write!(indent, "Assign:")?;
1297 indent = set_indentation(indent, 1);
1298 write!(indent, "\n{lhs}")?;
1299 write!(indent, "\n{rhs}")?;
1300 Ok(())
1301}
1302
1303fn display_assign_op(
1304 mut indent: Indented<Formatter>,
1305 op: BinOp,
1306 lhs: ExprId,
1307 rhs: ExprId,
1308) -> fmt::Result {
1309 write!(indent, "AssignOp ({op:?}):")?;
1310 indent = set_indentation(indent, 1);
1311 write!(indent, "\n{lhs}")?;
1312 write!(indent, "\n{rhs}")?;
1313 Ok(())
1314}
1315
1316fn display_assign_field(
1317 mut indent: Indented<Formatter>,
1318 record: ExprId,
1319 field: &Field,
1320 replace: ExprId,
1321) -> fmt::Result {
1322 write!(indent, "AssignField:")?;
1323 indent = set_indentation(indent, 1);
1324 write!(indent, "\n{record}")?;
1325 write!(indent, "\n{field}")?;
1326 write!(indent, "\n{replace}")?;
1327 Ok(())
1328}
1329
1330fn display_assign_index(
1331 mut indent: Indented<Formatter>,
1332 array: ExprId,
1333 index: ExprId,
1334 replace: ExprId,
1335) -> fmt::Result {
1336 write!(indent, "AssignIndex:")?;
1337 indent = set_indentation(indent, 1);
1338 write!(indent, "\n{array}")?;
1339 write!(indent, "\n{index}")?;
1340 write!(indent, "\n{replace}")?;
1341 Ok(())
1342}
1343
1344fn display_bin_op(
1345 mut indent: Indented<Formatter>,
1346 op: BinOp,
1347 lhs: ExprId,
1348 rhs: ExprId,
1349) -> fmt::Result {
1350 write!(indent, "BinOp ({op:?}):")?;
1351 indent = set_indentation(indent, 1);
1352 write!(indent, "\n{lhs}")?;
1353 write!(indent, "\n{rhs}")?;
1354 Ok(())
1355}
1356
1357fn display_call(mut indent: Indented<Formatter>, callable: ExprId, arg: ExprId) -> fmt::Result {
1358 write!(indent, "Call:")?;
1359 indent = set_indentation(indent, 1);
1360 write!(indent, "\n{callable}")?;
1361 write!(indent, "\n{arg}")?;
1362 Ok(())
1363}
1364
1365fn display_closure(
1366 mut f: Indented<Formatter>,
1367 args: &[LocalVarId],
1368 callable: LocalItemId,
1369) -> fmt::Result {
1370 f.write_str("Closure([")?;
1371 let mut args = args.iter();
1372 if let Some(arg) = args.next() {
1373 write!(f, "{arg}")?;
1374 }
1375 for arg in args {
1376 write!(f, ", {arg}")?;
1377 }
1378 write!(f, "], {callable})")
1379}
1380
1381fn display_field(mut indent: Indented<Formatter>, expr: ExprId, field: &Field) -> fmt::Result {
1382 write!(indent, "Field:")?;
1383 indent = set_indentation(indent, 1);
1384 write!(indent, "\n{expr}")?;
1385 write!(indent, "\n{field:?}")?;
1386 Ok(())
1387}
1388
1389fn display_if(
1390 mut indent: Indented<Formatter>,
1391 cond: ExprId,
1392 body: ExprId,
1393 els: Option<ExprId>,
1394) -> fmt::Result {
1395 write!(indent, "If:")?;
1396 indent = set_indentation(indent, 1);
1397 write!(indent, "\n{cond}")?;
1398 write!(indent, "\n{body}")?;
1399 if let Some(e) = els {
1400 write!(indent, "\n{e}")?;
1401 }
1402 Ok(())
1403}
1404
1405fn display_index(mut indent: Indented<Formatter>, array: ExprId, index: ExprId) -> fmt::Result {
1406 write!(indent, "Index:")?;
1407 indent = set_indentation(indent, 1);
1408 write!(indent, "\n{array}")?;
1409 write!(indent, "\n{index}")?;
1410 Ok(())
1411}
1412
1413fn display_range(
1414 mut indent: Indented<Formatter>,
1415 start: Option<ExprId>,
1416 step: Option<ExprId>,
1417 end: Option<ExprId>,
1418) -> fmt::Result {
1419 write!(indent, "Range:")?;
1420 indent = set_indentation(indent, 1);
1421 match start {
1422 Some(e) => write!(indent, "\n{e}")?,
1423 None => write!(indent, "\n<no start>")?,
1424 }
1425 match step {
1426 Some(e) => write!(indent, "\n{e}")?,
1427 None => write!(indent, "\n<no step>")?,
1428 }
1429 match end {
1430 Some(e) => write!(indent, "\n{e}")?,
1431 None => write!(indent, "\n<no end>")?,
1432 }
1433 Ok(())
1434}
1435
1436fn display_struct(
1437 mut indent: Indented<Formatter>,
1438 name: &Res,
1439 copy: Option<ExprId>,
1440 fields: &Vec<FieldAssign>,
1441) -> fmt::Result {
1442 write!(indent, "Struct ({name}):")?;
1443 if copy.is_none() && fields.is_empty() {
1444 write!(indent, " <empty>")?;
1445 return Ok(());
1446 }
1447 indent = set_indentation(indent, 1);
1448 if let Some(copy) = copy {
1449 write!(indent, "\nCopy: {copy}")?;
1450 }
1451 for field in fields {
1452 write!(indent, "\n{field}")?;
1453 }
1454 Ok(())
1455}
1456
1457fn display_string(mut indent: Indented<Formatter>, components: &[StringComponent]) -> fmt::Result {
1458 write!(indent, "String:")?;
1459 indent = set_indentation(indent, 1);
1460 for component in components {
1461 match component {
1462 StringComponent::Expr(expr) => write!(indent, "\nExpr: {expr}")?,
1463 StringComponent::Lit(str) => write!(indent, "\nLit: {str:?}")?,
1464 }
1465 }
1466
1467 Ok(())
1468}
1469
1470fn display_update_index(
1471 mut indent: Indented<Formatter>,
1472 expr1: ExprId,
1473 expr2: ExprId,
1474 expr3: ExprId,
1475) -> fmt::Result {
1476 write!(indent, "UpdateIndex:")?;
1477 indent = set_indentation(indent, 1);
1478 write!(indent, "\n{expr1}")?;
1479 write!(indent, "\n{expr2}")?;
1480 write!(indent, "\n{expr3}")?;
1481 Ok(())
1482}
1483
1484fn display_tuple(mut indent: Indented<Formatter>, exprs: &Vec<ExprId>) -> fmt::Result {
1485 if exprs.is_empty() {
1486 write!(indent, "Unit")?;
1487 } else {
1488 write!(indent, "Tuple:")?;
1489 indent = set_indentation(indent, 1);
1490 for e in exprs {
1491 write!(indent, "\n{e}")?;
1492 }
1493 }
1494 Ok(())
1495}
1496
1497fn display_un_op(mut indent: Indented<Formatter>, op: UnOp, expr: ExprId) -> fmt::Result {
1498 write!(indent, "UnOp ({op}):")?;
1499 indent = set_indentation(indent, 1);
1500 write!(indent, "\n{expr}")?;
1501 Ok(())
1502}
1503
1504fn display_update_field(
1505 mut indent: Indented<Formatter>,
1506 record: ExprId,
1507 field: &Field,
1508 replace: ExprId,
1509) -> fmt::Result {
1510 write!(indent, "UpdateField:")?;
1511 indent = set_indentation(indent, 1);
1512 write!(indent, "\n{record}")?;
1513 write!(indent, "\n{field}")?;
1514 write!(indent, "\n{replace}")?;
1515 Ok(())
1516}
1517
1518fn display_var(mut f: Indented<Formatter>, res: Res, args: &[GenericArg]) -> fmt::Result {
1519 if args.is_empty() {
1520 write!(f, "Var: {res}")
1521 } else {
1522 write!(f, "Var:")?;
1523 f = set_indentation(f, 1);
1524 write!(f, "\nres: {res}")?;
1525 write!(f, "\ngenerics:")?;
1526 f = set_indentation(f, 2);
1527 for arg in args {
1528 write!(f, "\n{arg}")?;
1529 }
1530 Ok(())
1531 }
1532}
1533
1534fn display_while(mut indent: Indented<Formatter>, cond: ExprId, block: BlockId) -> fmt::Result {
1535 write!(indent, "While:")?;
1536 indent = set_indentation(indent, 1);
1537 write!(indent, "\n{cond}")?;
1538 write!(indent, "\n{block}")?;
1539 Ok(())
1540}
1541
1542/// A field assignment in a struct constructor expression.
1543#[derive(Clone, Debug, PartialEq)]
1544pub struct FieldAssign {
1545 /// The node ID.
1546 pub id: NodeId,
1547 /// The span.
1548 pub span: Span,
1549 /// The field to assign.
1550 pub field: Field,
1551 /// The value to assign to the field.
1552 pub value: ExprId,
1553}
1554
1555impl Display for FieldAssign {
1556 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1557 write!(
1558 f,
1559 "FieldsAssign {} {}: ({}) {}",
1560 self.id, self.span, self.field, self.value
1561 )
1562 }
1563}
1564
1565/// A string component.
1566#[derive(Clone, Debug, PartialEq)]
1567pub enum StringComponent {
1568 /// An expression.
1569 Expr(ExprId),
1570 /// A string literal.
1571 Lit(Rc<str>),
1572}
1573
1574/// A pattern.
1575#[derive(Clone, Debug, Eq, PartialEq)]
1576pub struct Pat {
1577 /// The node ID.
1578 pub id: PatId,
1579 /// The span.
1580 pub span: Span,
1581 /// The pattern type.
1582 pub ty: Ty,
1583 /// The pattern kind.
1584 pub kind: PatKind,
1585}
1586
1587impl Display for Pat {
1588 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1589 write!(
1590 f,
1591 "Pat {} {} [Type {}]: {}",
1592 self.id, self.span, self.ty, self.kind
1593 )
1594 }
1595}
1596
1597/// A pattern kind.
1598#[derive(Clone, Debug, Eq, PartialEq)]
1599pub enum PatKind {
1600 /// A binding.
1601 Bind(Ident),
1602 /// A discarded binding, `_`.
1603 Discard,
1604 /// A tuple: `(a, b, c)`.
1605 Tuple(Vec<PatId>),
1606}
1607
1608impl Display for PatKind {
1609 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1610 let mut indent = set_indentation(indented(f), 0);
1611 match self {
1612 PatKind::Bind(id) => {
1613 write!(indent, "Bind: {id}")?;
1614 }
1615 PatKind::Discard => write!(indent, "Discard")?,
1616 PatKind::Tuple(ps) => {
1617 if ps.is_empty() {
1618 write!(indent, "Unit")?;
1619 } else {
1620 write!(indent, "Tuple:")?;
1621 indent = set_indentation(indent, 1);
1622 for p in ps {
1623 write!(indent, "\n{p}")?;
1624 }
1625 }
1626 }
1627 }
1628 Ok(())
1629 }
1630}
1631
1632/// An identifier.
1633#[derive(Clone, Debug, Eq, Hash, PartialEq)]
1634pub struct Ident {
1635 /// The node ID.
1636 pub id: LocalVarId,
1637 /// The span.
1638 pub span: Span,
1639 /// The identifier name.
1640 pub name: Rc<str>,
1641}
1642
1643impl Display for Ident {
1644 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1645 write!(f, "Ident {} {} \"{}\"", self.id, self.span, self.name)
1646 }
1647}
1648
1649/// An attribute.
1650#[derive(Clone, Debug, PartialEq)]
1651pub enum Attr {
1652 /// Indicates that a callable is an entry point to a program.
1653 EntryPoint,
1654 /// Indicates that a callable is a measurement.
1655 Measurement,
1656 /// Indicates that a callable is a reset.
1657 Reset,
1658 /// Indicates that a callable is used for unit testing.
1659 Test,
1660}
1661
1662/// A field.
1663#[derive(Clone, Debug, Eq, PartialEq)]
1664pub enum Field {
1665 /// A field path.
1666 Path(FieldPath),
1667 /// A primitive field for a built-in type.
1668 Prim(PrimField),
1669 /// An invalid field.
1670 Err,
1671}
1672
1673impl Display for Field {
1674 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1675 match self {
1676 Field::Path(path) => write!(f, "Path({:?})", path.indices),
1677 Field::Prim(prim) => write!(f, "Prim({prim:?}"),
1678 Field::Err => f.write_str("Err"),
1679 }
1680 }
1681}
1682
1683/// A path to a field in a tuple or user-defined type.
1684#[derive(Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
1685pub struct FieldPath {
1686 /// The tuple item indices to follow in order from top to bottom.
1687 pub indices: Vec<usize>,
1688}
1689
1690/// A primitive field for a built-in type.
1691#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
1692pub enum PrimField {
1693 /// The start of a range.
1694 Start,
1695 /// The step of a range.
1696 Step,
1697 /// The end of a range.
1698 End,
1699}
1700
1701impl FromStr for PrimField {
1702 type Err = ();
1703
1704 fn from_str(s: &str) -> result::Result<Self, <Self as FromStr>::Err> {
1705 match s {
1706 "Start" => Ok(Self::Start),
1707 "Step" => Ok(Self::Step),
1708 "End" => Ok(Self::End),
1709 _ => Err(()),
1710 }
1711 }
1712}
1713
1714/// The visibility of a declaration.
1715#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1716pub enum Visibility {
1717 /// Visible everywhere.
1718 Public,
1719 /// Visible within a package.
1720 Internal,
1721}
1722
1723/// A callable kind.
1724#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
1725pub enum CallableKind {
1726 /// A function.
1727 Function,
1728 /// An operation.
1729 Operation,
1730}
1731
1732impl Display for CallableKind {
1733 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1734 match self {
1735 CallableKind::Function => f.write_str("function"),
1736 CallableKind::Operation => f.write_str("operation"),
1737 }
1738 }
1739}
1740
1741/// The mutability of a binding.
1742#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1743pub enum Mutability {
1744 /// An immutable binding.
1745 Immutable,
1746 /// A mutable binding.
1747 Mutable,
1748}
1749
1750/// The source of an allocated qubit.
1751#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1752pub enum QubitSource {
1753 /// A qubit initialized to the zero state.
1754 Fresh,
1755 /// A qubit borrowed from another part of the program that may be in any state, and is expected
1756 /// to be returned to that state before being released.
1757 Dirty,
1758}
1759
1760/// A literal.
1761#[derive(Clone, Debug, PartialEq)]
1762pub enum Lit {
1763 /// A big integer literal.
1764 BigInt(BigInt),
1765 /// A boolean literal.
1766 Bool(bool),
1767 /// A floating-point literal.
1768 Double(f64),
1769 /// An integer literal.
1770 Int(i64),
1771 /// A Pauli operator literal.
1772 Pauli(Pauli),
1773 /// A measurement result literal.
1774 Result(Result),
1775}
1776
1777impl Display for Lit {
1778 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1779 match self {
1780 Lit::BigInt(val) => write!(f, "BigInt({val})")?,
1781 Lit::Bool(val) => write!(f, "Bool({val})")?,
1782 Lit::Double(val) => write!(f, "Double({val})")?,
1783 Lit::Int(val) => write!(f, "Int({val})")?,
1784 Lit::Pauli(val) => write!(f, "Pauli({val:?})")?,
1785 Lit::Result(val) => write!(f, "Result({val:?})")?,
1786 }
1787 Ok(())
1788 }
1789}
1790
1791/// A measurement result.
1792#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1793pub enum Result {
1794 /// The zero eigenvalue.
1795 Zero,
1796 /// The one eigenvalue.
1797 One,
1798}
1799
1800/// A Pauli operator.
1801#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1802pub enum Pauli {
1803 /// The Pauli I operator.
1804 I,
1805 /// The Pauli X operator.
1806 X,
1807 /// The Pauli Y operator.
1808 Y,
1809 /// The Pauli Z operator.
1810 Z,
1811}
1812
1813/// A functor that may be applied to an operation.
1814#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1815pub enum Functor {
1816 /// The adjoint functor.
1817 Adj,
1818 /// The controlled functor.
1819 Ctl,
1820}
1821
1822impl Display for Functor {
1823 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1824 match self {
1825 Functor::Adj => f.write_str("Adj"),
1826 Functor::Ctl => f.write_str("Ctl"),
1827 }
1828 }
1829}
1830
1831/// A unary operator.
1832#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1833pub enum UnOp {
1834 /// A functor application.
1835 Functor(Functor),
1836 /// Negation: `-`.
1837 Neg,
1838 /// Bitwise NOT: `~~~`.
1839 NotB,
1840 /// Logical NOT: `not`.
1841 NotL,
1842 /// A leading `+`.
1843 Pos,
1844 /// Unwrap a user-defined type: `!`.
1845 Unwrap,
1846}
1847
1848impl Display for UnOp {
1849 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1850 match self {
1851 UnOp::Functor(func) => write!(f, "Functor {func:?}")?,
1852 _ => fmt::Debug::fmt(self, f)?,
1853 }
1854 Ok(())
1855 }
1856}
1857
1858/// A binary operator.
1859#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1860pub enum BinOp {
1861 /// Addition: `+`.
1862 Add,
1863 /// Bitwise AND: `&&&`.
1864 AndB,
1865 /// Logical AND: `and`.
1866 AndL,
1867 /// Division: `/`.
1868 Div,
1869 /// Equality: `==`.
1870 Eq,
1871 /// Exponentiation: `^`.
1872 Exp,
1873 /// Greater than: `>`.
1874 Gt,
1875 /// Greater than or equal: `>=`.
1876 Gte,
1877 /// Less than: `<`.
1878 Lt,
1879 /// Less than or equal: `<=`.
1880 Lte,
1881 /// Modulus: `%`.
1882 Mod,
1883 /// Multiplication: `*`.
1884 Mul,
1885 /// Inequality: `!=`.
1886 Neq,
1887 /// Bitwise OR: `|||`.
1888 OrB,
1889 /// Logical OR: `or`.
1890 OrL,
1891 /// Shift left: `<<<`.
1892 Shl,
1893 /// Shift right: `>>>`.
1894 Shr,
1895 /// Subtraction: `-`.
1896 Sub,
1897 /// Bitwise XOR: `^^^`.
1898 XorB,
1899}
1900