GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
dmitryv/select-updated

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_fir/src

compiler/qsc_fir/src/fir.rs

1426lines · 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, GenericParam, Scheme, Ty, Udt};
12use indenter::{indented, Indented};
13use num_bigint::BigInt;
14use qsc_data_structures::{index_map::IndexMap, span::Span};
15use std::{
16 cmp::Ordering,
17 fmt::{self, Debug, Display, Formatter, Write},
18 hash::{Hash, Hasher},
19 rc::Rc,
20 result,
21 str::FromStr,
22};
23
24fn set_indentation<'a, 'b>(
25 indent: Indented<'a, Formatter<'b>>,
26 level: usize,
27) -> Indented<'a, Formatter<'b>> {
28 match level {
29 0 => indent.with_str(""),
30 1 => indent.with_str(" "),
31 2 => indent.with_str(" "),
32 _ => unimplemented!("intentation level not supported"),
33 }
34}
35
36/// A unique identifier for an FIR node.
37#[derive(Clone, Copy, Debug)]
38pub struct NodeId(u32);
39
40impl NodeId {
41 /// The ID of the first node.
42 pub const FIRST: Self = Self(0);
43
44 /// The successor of this ID.
45 #[must_use]
46 pub fn successor(self) -> Self {
47 Self(self.0 + 1)
48 }
49}
50
51impl Display for NodeId {
52 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
53 Display::fmt(&self.0, f)
54 }
55}
56
57impl From<NodeId> for usize {
58 fn from(value: NodeId) -> Self {
59 value.0 as usize
60 }
61}
62
63impl From<usize> for NodeId {
64 fn from(value: usize) -> Self {
65 NodeId(
66 value
67 .try_into()
68 .expect("Type Node ID does not fit into u32"),
69 )
70 }
71}
72
73impl From<NodeId> for u32 {
74 fn from(value: NodeId) -> Self {
75 value.0
76 }
77}
78
79impl From<u32> for NodeId {
80 fn from(value: u32) -> Self {
81 NodeId(value)
82 }
83}
84
85impl PartialEq for NodeId {
86 fn eq(&self, other: &Self) -> bool {
87 self.0 == other.0
88 }
89}
90
91impl Eq for NodeId {}
92
93impl PartialOrd for NodeId {
94 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
95 Some(self.cmp(other))
96 }
97}
98
99impl Ord for NodeId {
100 fn cmp(&self, other: &Self) -> Ordering {
101 self.0.cmp(&other.0)
102 }
103}
104
105impl Hash for NodeId {
106 fn hash<H: Hasher>(&self, state: &mut H) {
107 self.0.hash(state);
108 }
109}
110
111macro_rules! fir_id {
112 ($id:ident) => {
113 /// A unique identifier for an FIR node.
114 #[derive(Debug, Clone, Copy)]
115 pub struct $id(pub u32);
116
117 impl $id {
118 /// The successor of this ID.
119 #[must_use]
120 pub fn successor(self) -> Self {
121 Self(self.0 + 1)
122 }
123 }
124
125 impl Default for $id {
126 fn default() -> Self {
127 Self(0)
128 }
129 }
130
131 impl From<NodeId> for $id {
132 fn from(val: NodeId) -> Self {
133 $id(val.into())
134 }
135 }
136
137 impl From<$id> for NodeId {
138 fn from(val: $id) -> Self {
139 NodeId(val.into())
140 }
141 }
142
143 impl From<u32> for $id {
144 fn from(val: u32) -> Self {
145 $id(val)
146 }
147 }
148
149 impl From<$id> for u32 {
150 fn from(id: $id) -> Self {
151 id.0
152 }
153 }
154
155 impl From<$id> for usize {
156 fn from(value: $id) -> Self {
157 value.0 as usize
158 }
159 }
160
161 impl From<usize> for $id {
162 fn from(value: usize) -> Self {
163 $id(value.try_into().expect(&format!(
164 "Value, {}, does not fit into {}",
165 value,
166 stringify!($id)
167 )))
168 }
169 }
170
171 impl PartialEq for $id {
172 fn eq(&self, other: &Self) -> bool {
173 self.0 == other.0
174 }
175 }
176
177 impl Eq for $id {}
178
179 impl PartialOrd for $id {
180 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
181 Some(self.cmp(other))
182 }
183 }
184
185 impl Ord for $id {
186 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
187 self.0.cmp(&other.0)
188 }
189 }
190
191 impl std::hash::Hash for $id {
192 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
193 self.0.hash(state);
194 }
195 }
196
197 impl Display for $id {
198 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
199 Display::fmt(&self.0, f)
200 }
201 }
202 };
203}
204
205fir_id!(BlockId);
206fir_id!(ExprId);
207fir_id!(PatId);
208fir_id!(StmtId);
209
210/// A unique identifier for a package within a package store.
211#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
212pub struct PackageId(usize);
213
214impl PackageId {
215 /// The package ID of the core library.
216 pub const CORE: Self = Self(0);
217
218 /// The successor of this ID.
219 #[must_use]
220 pub fn successor(self) -> Self {
221 Self(self.0 + 1)
222 }
223}
224
225impl Display for PackageId {
226 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
227 Display::fmt(&self.0, f)
228 }
229}
230
231impl From<PackageId> for usize {
232 fn from(value: PackageId) -> Self {
233 value.0
234 }
235}
236
237impl From<usize> for PackageId {
238 fn from(value: usize) -> Self {
239 PackageId(value)
240 }
241}
242
243/// A unique identifier for an item within a package.
244#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
245pub struct LocalItemId(usize);
246
247impl LocalItemId {
248 /// The successor of this ID.
249 #[must_use]
250 pub fn successor(self) -> Self {
251 Self(self.0 + 1)
252 }
253}
254
255impl Display for LocalItemId {
256 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
257 Display::fmt(&self.0, f)
258 }
259}
260
261impl From<usize> for LocalItemId {
262 fn from(value: usize) -> Self {
263 Self(value)
264 }
265}
266
267impl From<LocalItemId> for usize {
268 fn from(value: LocalItemId) -> Self {
269 value.0
270 }
271}
272
273/// A unique identifier for an item within a package store.
274#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
275pub struct ItemId {
276 /// The package ID or `None` for the local package.
277 pub package: Option<PackageId>,
278 /// The item ID.
279 pub item: LocalItemId,
280}
281
282impl Display for ItemId {
283 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
284 match self.package {
285 None => write!(f, "Item {}", self.item),
286 Some(package) => write!(f, "Item {} (Package {package})", self.item),
287 }
288 }
289}
290
291/// A resolution. This connects a usage of a name with the declaration of that name by uniquely
292/// identifying the node that declared it.
293#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
294pub enum Res {
295 /// An invalid resolution.
296 Err,
297 /// A global item.
298 Item(ItemId),
299 /// A local variable.
300 Local(NodeId),
301}
302
303impl Display for Res {
304 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
305 match self {
306 Res::Err => f.write_str("Err"),
307 Res::Item(item) => Display::fmt(item, f),
308 Res::Local(node) => write!(f, "Local {node}"),
309 }
310 }
311}
312
313/// The root node of the FIR.
314/// ### Notes
315/// We maintain a dense map of ids within the package.
316/// `BlockId`, `ExprId`, `PatId`, `StmtId`, and `NodeId`s are all assigned
317/// from a type specific counter in the assigner.
318///
319/// `BlockId`, `ExprId`, `PatId`, `StmtId` ids don't leak and are only used
320/// within the containing node. Node ids are used to identify nodes within
321/// the package and require mapping from the HIR node id to the new FIR node id.
322/// `PackageId`s and `LocalItemId`s are 1:1 from the HIR and are not remapped.
323#[derive(Clone, Debug, Default)]
324pub struct Package {
325 /// The items in the package.
326 pub items: IndexMap<LocalItemId, Item>,
327 /// The entry expression for an executable package.
328 pub entry: Option<ExprId>,
329 /// The blocks in the package.
330 pub blocks: IndexMap<BlockId, Block>,
331 /// The expressions in the package.
332 pub exprs: IndexMap<ExprId, Expr>,
333 /// The patterns in the package.
334 pub pats: IndexMap<PatId, Pat>,
335 /// The statements in the package.
336 pub stmts: IndexMap<StmtId, Stmt>,
337}
338
339impl Display for Package {
340 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
341 let mut indent = set_indentation(indented(f), 0);
342 write!(indent, "Package:")?;
343 indent = set_indentation(indent, 1);
344 if let Some(e) = &self.entry {
345 write!(indent, "\nentry expression: {e}")?;
346 }
347 for item in self.items.values() {
348 write!(indent, "\n{item}")?;
349 }
350 Ok(())
351 }
352}
353
354/// An item.
355#[derive(Clone, Debug, PartialEq)]
356pub struct Item {
357 /// The ID.
358 pub id: LocalItemId,
359 /// The span.
360 pub span: Span,
361 /// The parent item.
362 pub parent: Option<LocalItemId>,
363 /// The documentation.
364 pub doc: Rc<str>,
365 /// The attributes.
366 pub attrs: Vec<Attr>,
367 /// The visibility.
368 pub visibility: Visibility,
369 /// The item kind.
370 pub kind: ItemKind,
371}
372
373impl Display for Item {
374 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
375 let mut indent = set_indentation(indented(f), 0);
376 write!(
377 indent,
378 "Item {} {} ({:?}):",
379 self.id, self.span, self.visibility
380 )?;
381
382 indent = set_indentation(indent, 1);
383 if let Some(parent) = self.parent {
384 write!(indent, "\nParent: {parent}")?;
385 }
386
387 if !self.doc.is_empty() {
388 write!(indent, "\nDoc:")?;
389 indent = set_indentation(indent, 2);
390 write!(indent, "\n{}", self.doc)?;
391 indent = set_indentation(indent, 1);
392 }
393
394 for attr in &self.attrs {
395 write!(indent, "\n{attr:?}")?;
396 }
397
398 write!(indent, "\n{}", self.kind)?;
399 Ok(())
400 }
401}
402
403/// An item kind.
404#[derive(Clone, Debug, PartialEq)]
405pub enum ItemKind {
406 /// A `function` or `operation` declaration.
407 Callable(CallableDecl),
408 /// A `namespace` declaration.
409 Namespace(Ident, Vec<LocalItemId>),
410 /// A `newtype` declaration.
411 Ty(Ident, Udt),
412}
413
414impl Display for ItemKind {
415 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
416 match self {
417 ItemKind::Callable(decl) => write!(f, "{decl}"),
418 ItemKind::Namespace(name, items) => {
419 write!(f, "Namespace ({name}):")?;
420 let mut items = items.iter();
421 if let Some(item) = items.next() {
422 write!(f, " Item {item}")?;
423 for item in items {
424 write!(f, ", Item {item}")?;
425 }
426 Ok(())
427 } else {
428 write!(f, " <empty>")
429 }
430 }
431 ItemKind::Ty(name, udt) => write!(f, "Type ({name}): {udt}"),
432 }
433 }
434}
435
436/// A callable declaration header.
437#[derive(Clone, Debug, PartialEq)]
438pub struct CallableDecl {
439 /// The node ID.
440 pub id: NodeId,
441 /// The span.
442 pub span: Span,
443 /// The callable kind.
444 pub kind: CallableKind,
445 /// The name of the callable.
446 pub name: Ident,
447 /// The generic parameters to the callable.
448 pub generics: Vec<GenericParam>,
449 /// The input to the callable.
450 pub input: PatId,
451 /// The return type of the callable.
452 pub output: Ty,
453 /// The functors supported by the callable.
454 pub functors: FunctorSetValue,
455 /// The callable body.
456 pub body: SpecDecl,
457 /// The adjoint specialization.
458 pub adj: Option<SpecDecl>,
459 /// The controlled specialization.
460 pub ctl: Option<SpecDecl>,
461 /// The controlled adjoint specialization.
462 pub ctl_adj: Option<SpecDecl>,
463}
464
465impl CallableDecl {
466 /// The type scheme of the callable.
467 #[must_use]
468 pub fn scheme<'a>(&self, f: impl Fn(PatId) -> &'a Pat) -> Scheme {
469 Scheme::new(
470 self.generics.clone(),
471 Box::new(Arrow {
472 kind: self.kind,
473 input: Box::new(f(self.input).ty.clone()),
474 output: Box::new(self.output.clone()),
475 functors: FunctorSet::Value(self.functors),
476 }),
477 )
478 }
479}
480
481impl Display for CallableDecl {
482 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
483 let mut indent = set_indentation(indented(f), 0);
484 write!(
485 indent,
486 "Callable {} {} ({}):",
487 self.id, self.span, self.kind
488 )?;
489 indent = set_indentation(indent, 1);
490 write!(indent, "\nname: {}", self.name)?;
491 if !self.generics.is_empty() {
492 write!(indent, "\ngenerics:")?;
493 indent = set_indentation(indent, 2);
494 for (ix, param) in self.generics.iter().enumerate() {
495 write!(indent, "\n{ix}: {param}")?;
496 }
497 indent = set_indentation(indent, 1);
498 }
499 write!(indent, "\ninput: {}", self.input)?;
500 write!(indent, "\noutput: {}", self.output)?;
501 write!(indent, "\nfunctors: {}", self.functors)?;
502 write!(indent, "\nbody: {}", self.body)?;
503 match &self.adj {
504 Some(spec) => write!(indent, "\nadj: {spec}")?,
505 None => write!(indent, "\nadj: <none>")?,
506 }
507 match &self.ctl {
508 Some(spec) => write!(indent, "\nctl: {spec}")?,
509 None => write!(indent, "\nctl: <none>")?,
510 }
511 match &self.ctl_adj {
512 Some(spec) => write!(indent, "\nctl-adj: {spec}")?,
513 None => write!(indent, "\nctl-adj: <none>")?,
514 }
515 Ok(())
516 }
517}
518
519/// A specialization declaration.
520#[derive(Clone, Debug, PartialEq)]
521pub struct SpecDecl {
522 /// The node ID.
523 pub id: NodeId,
524 /// The span.
525 pub span: Span,
526 /// The body of the specialization.
527 pub body: SpecBody,
528}
529
530impl Display for SpecDecl {
531 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
532 write!(f, "SpecDecl {} {}: {}", self.id, self.span, self.body)
533 }
534}
535
536/// The body of a specialization.
537#[derive(Clone, Debug, PartialEq)]
538pub enum SpecBody {
539 /// The strategy to use to automatically generate the specialization.
540 Gen(SpecGen),
541 /// A manual implementation of the specialization.
542 Impl(Option<PatId>, BlockId),
543}
544
545impl Display for SpecBody {
546 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
547 let mut indent = set_indentation(indented(f), 0);
548 match self {
549 SpecBody::Gen(sg) => write!(indent, "Gen: {sg:?}")?,
550 SpecBody::Impl(p, b) => {
551 write!(indent, "Impl:")?;
552 indent = set_indentation(indent, 1);
553 if let Some(p) = p {
554 write!(indent, "\n{p}")?;
555 }
556 write!(indent, "\n{b}")?;
557 }
558 }
559 Ok(())
560 }
561}
562
563/// A sequenced block of statements.
564#[derive(Clone, Debug, PartialEq)]
565pub struct Block {
566 /// The node ID.
567 pub id: BlockId,
568 /// The span.
569 pub span: Span,
570 /// The block type.
571 pub ty: Ty,
572 /// The statements in the block.
573 pub stmts: Vec<StmtId>,
574}
575
576impl Display for Block {
577 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
578 if self.stmts.is_empty() {
579 write!(f, "Block {} {}: <empty>", self.id, self.span)?;
580 } else {
581 let mut indent = set_indentation(indented(f), 0);
582 write!(
583 indent,
584 "Block {} {} [Type {}]:",
585 self.id, self.span, self.ty
586 )?;
587 indent = set_indentation(indent, 1);
588 for s in &self.stmts {
589 write!(indent, "\n{s}")?;
590 }
591 }
592 Ok(())
593 }
594}
595
596/// A statement.
597#[derive(Clone, Debug, PartialEq)]
598pub struct Stmt {
599 /// The stmt ID.
600 pub id: StmtId,
601 /// The span.
602 pub span: Span,
603 /// The statement kind.
604 pub kind: StmtKind,
605}
606
607impl Display for Stmt {
608 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
609 write!(f, "Stmt {} {}: {}", self.id, self.span, self.kind)
610 }
611}
612
613/// A statement kind.
614#[derive(Clone, Debug, PartialEq)]
615pub enum StmtKind {
616 /// An expression without a trailing semicolon.
617 Expr(ExprId),
618 /// An item.
619 Item(LocalItemId),
620 /// A let or mutable binding: `let a = b;` or `mutable x = b;`.
621 Local(Mutability, PatId, ExprId),
622 /// A use or borrow qubit allocation: `use a = b;` or `borrow a = b;`.
623 Qubit(QubitSource, PatId, QubitInit, Option<BlockId>),
624 /// An expression with a trailing semicolon.
625 Semi(ExprId),
626}
627
628impl Display for StmtKind {
629 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
630 let mut indent = set_indentation(indented(f), 0);
631 match self {
632 StmtKind::Expr(e) => write!(indent, "Expr: {e}")?,
633 StmtKind::Item(item) => write!(indent, "Item: {item}")?,
634 StmtKind::Local(m, lhs, rhs) => {
635 write!(indent, "Local ({m:?}):")?;
636 indent = set_indentation(indent, 1);
637 write!(indent, "\n{lhs}")?;
638 write!(indent, "\n{rhs}")?;
639 }
640 StmtKind::Qubit(s, lhs, rhs, block) => {
641 write!(indent, "Qubit ({s:?})")?;
642 indent = set_indentation(indent, 1);
643 write!(indent, "\n{lhs}")?;
644 write!(indent, "\n{rhs}")?;
645 if let Some(b) = block {
646 write!(indent, "\n{b}")?;
647 }
648 }
649 StmtKind::Semi(e) => write!(indent, "Semi: {e}")?,
650 }
651 Ok(())
652 }
653}
654
655/// An expression.
656#[derive(Clone, Debug, PartialEq)]
657pub struct Expr {
658 /// The expr ID.
659 pub id: ExprId,
660 /// The span.
661 pub span: Span,
662 /// The expression type.
663 pub ty: Ty,
664 /// The expression kind.
665 pub kind: ExprKind,
666}
667
668impl Display for Expr {
669 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
670 write!(
671 f,
672 "Expr {} {} [Type {}]: {}",
673 self.id, self.span, self.ty, self.kind
674 )
675 }
676}
677
678/// An expression kind.
679#[derive(Clone, Debug, PartialEq)]
680pub enum ExprKind {
681 /// An array: `[a, b, c]`.
682 Array(Vec<ExprId>),
683 /// An array constructed by repeating a value: `[a, size = b]`.
684 ArrayRepeat(ExprId, ExprId),
685 /// An assignment: `set a = b`.
686 Assign(ExprId, ExprId),
687 /// An assignment with a compound operator. For example: `set a += b`.
688 AssignOp(BinOp, ExprId, ExprId),
689 /// An assignment with a compound field update operator: `set a w/= B <- c`.
690 AssignField(ExprId, Field, ExprId),
691 /// An assignment with a compound index update operator: `set a w/= b <- c`.
692 AssignIndex(ExprId, ExprId, ExprId),
693 /// A binary operator.
694 BinOp(BinOp, ExprId, ExprId),
695 /// A block: `{ ... }`.
696 Block(BlockId),
697 /// A call: `a(b)`.
698 Call(ExprId, ExprId),
699 /// A closure that fixes the vector of local variables as arguments to the callable item.
700 Closure(Vec<NodeId>, LocalItemId),
701 /// A failure: `fail "message"`.
702 Fail(ExprId),
703 /// A field accessor: `a::F`.
704 Field(ExprId, Field),
705 /// An unspecified expression, _, which may indicate partial application or discards
706 Hole,
707 /// An if expression with an optional else block: `if a { ... } else { ... }`.
708 ///
709 /// Note that, as a special case, `elif ...` is effectively parsed as `else if ...`, without a
710 /// block wrapping the `if`. This distinguishes `elif ...` from `else { if ... }`, which does
711 /// have a block.
712 If(ExprId, ExprId, Option<ExprId>),
713 /// An index accessor: `a[b]`.
714 Index(ExprId, ExprId),
715 /// A literal.
716 Lit(Lit),
717 /// A range: `start..step..end`, `start..end`, `start...`, `...end`, or `...`.
718 Range(Option<ExprId>, Option<ExprId>, Option<ExprId>),
719 /// A return: `return a`.
720 Return(ExprId),
721 /// A string.
722 String(Vec<StringComponent>),
723 /// Update array index: `a w/ b <- c`.
724 UpdateIndex(ExprId, ExprId, ExprId),
725 /// A tuple: `(a, b, c)`.
726 Tuple(Vec<ExprId>),
727 /// A unary operator.
728 UnOp(UnOp, ExprId),
729 /// A record field update: `a w/ B <- c`.
730 UpdateField(ExprId, Field, ExprId),
731 /// A variable and its generic arguments.
732 Var(Res, Vec<GenericArg>),
733 /// A while loop: `while a { ... }`.
734 While(ExprId, BlockId),
735}
736
737impl Display for ExprKind {
738 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
739 let mut indent = set_indentation(indented(f), 0);
740 match self {
741 ExprKind::Array(exprs) => display_array(indent, exprs)?,
742 ExprKind::ArrayRepeat(val, size) => display_array_repeat(indent, *val, *size)?,
743 ExprKind::Assign(lhs, rhs) => display_assign(indent, *lhs, *rhs)?,
744 ExprKind::AssignOp(op, lhs, rhs) => display_assign_op(indent, *op, *lhs, *rhs)?,
745 ExprKind::AssignField(record, field, replace) => {
746 display_assign_field(indent, *record, field, *replace)?;
747 }
748 ExprKind::AssignIndex(container, item, replace) => {
749 display_assign_index(indent, *container, *item, *replace)?;
750 }
751 ExprKind::BinOp(op, lhs, rhs) => display_bin_op(indent, *op, *lhs, *rhs)?,
752 ExprKind::Block(block) => write!(indent, "Expr Block: {block}")?,
753 ExprKind::Call(callable, arg) => display_call(indent, *callable, *arg)?,
754 ExprKind::Closure(args, callable) => display_closure(indent, args, *callable)?,
755 ExprKind::Fail(e) => write!(indent, "Fail: {e}")?,
756 ExprKind::Field(expr, field) => display_field(indent, *expr, field)?,
757 ExprKind::Hole => write!(indent, "Hole")?,
758 ExprKind::If(cond, body, els) => display_if(indent, *cond, *body, *els)?,
759 ExprKind::Index(array, index) => display_index(indent, *array, *index)?,
760 ExprKind::Lit(lit) => write!(indent, "Lit: {lit}")?,
761 ExprKind::Range(start, step, end) => display_range(indent, *start, *step, *end)?,
762 ExprKind::Return(e) => write!(indent, "Return: {e}")?,
763 ExprKind::String(components) => display_string(indent, components)?,
764 ExprKind::UpdateIndex(expr1, expr2, expr3) => {
765 display_update_index(indent, *expr1, *expr2, *expr3)?;
766 }
767 ExprKind::Tuple(exprs) => display_tuple(indent, exprs)?,
768 ExprKind::UnOp(op, expr) => display_un_op(indent, *op, *expr)?,
769 ExprKind::UpdateField(record, field, replace) => {
770 display_update_field(indent, *record, field, *replace)?;
771 }
772 ExprKind::Var(res, args) => display_var(indent, *res, args)?,
773 ExprKind::While(cond, block) => display_while(indent, *cond, *block)?,
774 }
775 Ok(())
776 }
777}
778
779fn display_array(mut indent: Indented<Formatter>, exprs: &Vec<ExprId>) -> fmt::Result {
780 write!(indent, "Array:")?;
781 indent = set_indentation(indent, 1);
782 for e in exprs {
783 write!(indent, "\n{e}")?;
784 }
785 Ok(())
786}
787
788fn display_array_repeat(mut indent: Indented<Formatter>, val: ExprId, size: ExprId) -> fmt::Result {
789 write!(indent, "ArrayRepeat:")?;
790 indent = set_indentation(indent, 1);
791 write!(indent, "\n{val}")?;
792 write!(indent, "\n{size}")?;
793 Ok(())
794}
795
796fn display_assign(mut indent: Indented<Formatter>, lhs: ExprId, rhs: ExprId) -> fmt::Result {
797 write!(indent, "Assign:")?;
798 indent = set_indentation(indent, 1);
799 write!(indent, "\n{lhs}")?;
800 write!(indent, "\n{rhs}")?;
801 Ok(())
802}
803
804fn display_assign_op(
805 mut indent: Indented<Formatter>,
806 op: BinOp,
807 lhs: ExprId,
808 rhs: ExprId,
809) -> fmt::Result {
810 write!(indent, "AssignOp ({op:?}):")?;
811 indent = set_indentation(indent, 1);
812 write!(indent, "\n{lhs}")?;
813 write!(indent, "\n{rhs}")?;
814 Ok(())
815}
816
817fn display_assign_field(
818 mut indent: Indented<Formatter>,
819 record: ExprId,
820 field: &Field,
821 replace: ExprId,
822) -> fmt::Result {
823 write!(indent, "AssignField:")?;
824 indent = set_indentation(indent, 1);
825 write!(indent, "\n{record}")?;
826 write!(indent, "\n{field}")?;
827 write!(indent, "\n{replace}")?;
828 Ok(())
829}
830
831fn display_assign_index(
832 mut indent: Indented<Formatter>,
833 array: ExprId,
834 index: ExprId,
835 replace: ExprId,
836) -> fmt::Result {
837 write!(indent, "AssignIndex:")?;
838 indent = set_indentation(indent, 1);
839 write!(indent, "\n{array}")?;
840 write!(indent, "\n{index}")?;
841 write!(indent, "\n{replace}")?;
842 Ok(())
843}
844
845fn display_bin_op(
846 mut indent: Indented<Formatter>,
847 op: BinOp,
848 lhs: ExprId,
849 rhs: ExprId,
850) -> fmt::Result {
851 write!(indent, "BinOp ({op:?}):")?;
852 indent = set_indentation(indent, 1);
853 write!(indent, "\n{lhs}")?;
854 write!(indent, "\n{rhs}")?;
855 Ok(())
856}
857
858fn display_call(mut indent: Indented<Formatter>, callable: ExprId, arg: ExprId) -> fmt::Result {
859 write!(indent, "Call:")?;
860 indent = set_indentation(indent, 1);
861 write!(indent, "\n{callable}")?;
862 write!(indent, "\n{arg}")?;
863 Ok(())
864}
865
866fn display_closure(
867 mut f: Indented<Formatter>,
868 args: &[NodeId],
869 callable: LocalItemId,
870) -> fmt::Result {
871 f.write_str("Closure([")?;
872 let mut args = args.iter();
873 if let Some(arg) = args.next() {
874 write!(f, "{arg}")?;
875 }
876 for arg in args {
877 write!(f, ", {arg}")?;
878 }
879 write!(f, "], {callable})")
880}
881
882fn display_field(mut indent: Indented<Formatter>, expr: ExprId, field: &Field) -> fmt::Result {
883 write!(indent, "Field:")?;
884 indent = set_indentation(indent, 1);
885 write!(indent, "\n{expr}")?;
886 write!(indent, "\n{field:?}")?;
887 Ok(())
888}
889
890fn display_if(
891 mut indent: Indented<Formatter>,
892 cond: ExprId,
893 body: ExprId,
894 els: Option<ExprId>,
895) -> fmt::Result {
896 write!(indent, "If:")?;
897 indent = set_indentation(indent, 1);
898 write!(indent, "\n{cond}")?;
899 write!(indent, "\n{body}")?;
900 if let Some(e) = els {
901 write!(indent, "\n{e}")?;
902 }
903 Ok(())
904}
905
906fn display_index(mut indent: Indented<Formatter>, array: ExprId, index: ExprId) -> fmt::Result {
907 write!(indent, "Index:")?;
908 indent = set_indentation(indent, 1);
909 write!(indent, "\n{array}")?;
910 write!(indent, "\n{index}")?;
911 Ok(())
912}
913
914fn display_range(
915 mut indent: Indented<Formatter>,
916 start: Option<ExprId>,
917 step: Option<ExprId>,
918 end: Option<ExprId>,
919) -> fmt::Result {
920 write!(indent, "Range:")?;
921 indent = set_indentation(indent, 1);
922 match start {
923 Some(e) => write!(indent, "\n{e}")?,
924 None => write!(indent, "\n<no start>")?,
925 }
926 match step {
927 Some(e) => write!(indent, "\n{e}")?,
928 None => write!(indent, "\n<no step>")?,
929 }
930 match end {
931 Some(e) => write!(indent, "\n{e}")?,
932 None => write!(indent, "\n<no end>")?,
933 }
934 Ok(())
935}
936
937fn display_string(mut indent: Indented<Formatter>, components: &[StringComponent]) -> fmt::Result {
938 write!(indent, "String:")?;
939 indent = set_indentation(indent, 1);
940 for component in components {
941 match component {
942 StringComponent::Expr(expr) => write!(indent, "\nExpr: {expr}")?,
943 StringComponent::Lit(str) => write!(indent, "\nLit: {str:?}")?,
944 }
945 }
946
947 Ok(())
948}
949
950fn display_update_index(
951 mut indent: Indented<Formatter>,
952 expr1: ExprId,
953 expr2: ExprId,
954 expr3: ExprId,
955) -> fmt::Result {
956 write!(indent, "UpdateIndex:")?;
957 indent = set_indentation(indent, 1);
958 write!(indent, "\n{expr1}")?;
959 write!(indent, "\n{expr2}")?;
960 write!(indent, "\n{expr3}")?;
961 Ok(())
962}
963
964fn display_tuple(mut indent: Indented<Formatter>, exprs: &Vec<ExprId>) -> fmt::Result {
965 if exprs.is_empty() {
966 write!(indent, "Unit")?;
967 } else {
968 write!(indent, "Tuple:")?;
969 indent = set_indentation(indent, 1);
970 for e in exprs {
971 write!(indent, "\n{e}")?;
972 }
973 }
974 Ok(())
975}
976
977fn display_un_op(mut indent: Indented<Formatter>, op: UnOp, expr: ExprId) -> fmt::Result {
978 write!(indent, "UnOp ({op}):")?;
979 indent = set_indentation(indent, 1);
980 write!(indent, "\n{expr}")?;
981 Ok(())
982}
983
984fn display_update_field(
985 mut indent: Indented<Formatter>,
986 record: ExprId,
987 field: &Field,
988 replace: ExprId,
989) -> fmt::Result {
990 write!(indent, "UpdateField:")?;
991 indent = set_indentation(indent, 1);
992 write!(indent, "\n{record}")?;
993 write!(indent, "\n{field}")?;
994 write!(indent, "\n{replace}")?;
995 Ok(())
996}
997
998fn display_var(mut f: Indented<Formatter>, res: Res, args: &[GenericArg]) -> fmt::Result {
999 if args.is_empty() {
1000 write!(f, "Var: {res}")
1001 } else {
1002 write!(f, "Var:")?;
1003 f = set_indentation(f, 1);
1004 write!(f, "\nres: {res}")?;
1005 write!(f, "\ngenerics:")?;
1006 f = set_indentation(f, 2);
1007 for arg in args {
1008 write!(f, "\n{arg}")?;
1009 }
1010 Ok(())
1011 }
1012}
1013
1014fn display_while(mut indent: Indented<Formatter>, cond: ExprId, block: BlockId) -> fmt::Result {
1015 write!(indent, "While:")?;
1016 indent = set_indentation(indent, 1);
1017 write!(indent, "\n{cond}")?;
1018 write!(indent, "\n{block}")?;
1019 Ok(())
1020}
1021
1022/// A string component.
1023#[derive(Clone, Debug, PartialEq)]
1024pub enum StringComponent {
1025 /// An expression.
1026 Expr(ExprId),
1027 /// A string literal.
1028 Lit(Rc<str>),
1029}
1030
1031/// A pattern.
1032#[derive(Clone, Debug, Eq, PartialEq)]
1033pub struct Pat {
1034 /// The node ID.
1035 pub id: PatId,
1036 /// The span.
1037 pub span: Span,
1038 /// The pattern type.
1039 pub ty: Ty,
1040 /// The pattern kind.
1041 pub kind: PatKind,
1042}
1043
1044impl Display for Pat {
1045 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1046 write!(
1047 f,
1048 "Pat {} {} [Type {}]: {}",
1049 self.id, self.span, self.ty, self.kind
1050 )
1051 }
1052}
1053
1054/// A pattern kind.
1055#[derive(Clone, Debug, Eq, PartialEq)]
1056pub enum PatKind {
1057 /// A binding.
1058 Bind(Ident),
1059 /// A discarded binding, `_`.
1060 Discard,
1061 /// A tuple: `(a, b, c)`.
1062 Tuple(Vec<PatId>),
1063}
1064
1065impl Display for PatKind {
1066 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1067 let mut indent = set_indentation(indented(f), 0);
1068 match self {
1069 PatKind::Bind(id) => {
1070 write!(indent, "Bind: {id}")?;
1071 }
1072 PatKind::Discard => write!(indent, "Discard")?,
1073 PatKind::Tuple(ps) => {
1074 if ps.is_empty() {
1075 write!(indent, "Unit")?;
1076 } else {
1077 write!(indent, "Tuple:")?;
1078 indent = set_indentation(indent, 1);
1079 for p in ps {
1080 write!(indent, "\n{p}")?;
1081 }
1082 }
1083 }
1084 }
1085 Ok(())
1086 }
1087}
1088
1089/// A qubit initializer.
1090#[derive(Clone, Debug, PartialEq)]
1091pub struct QubitInit {
1092 /// The node ID.
1093 pub id: NodeId,
1094 /// The span.
1095 pub span: Span,
1096 /// The qubit initializer type.
1097 pub ty: Ty,
1098 /// The qubit initializer kind.
1099 pub kind: QubitInitKind,
1100}
1101
1102impl Display for QubitInit {
1103 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1104 write!(
1105 f,
1106 "QubitInit {} {} [Type {}]: {}",
1107 self.id, self.span, self.ty, self.kind
1108 )
1109 }
1110}
1111
1112/// A qubit initializer kind.
1113#[derive(Clone, Debug, PartialEq)]
1114pub enum QubitInitKind {
1115 /// An array of qubits: `Qubit[a]`.
1116 Array(ExprId),
1117 /// A single qubit: `Qubit()`.
1118 Single,
1119 /// A tuple: `(a, b, c)`.
1120 Tuple(Vec<QubitInit>),
1121}
1122
1123impl Display for QubitInitKind {
1124 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1125 let mut indent = set_indentation(indented(f), 0);
1126 match self {
1127 QubitInitKind::Array(e) => {
1128 write!(indent, "Array:")?;
1129 indent = set_indentation(indent, 1);
1130 write!(indent, "\n{e}")?;
1131 }
1132 QubitInitKind::Single => write!(indent, "Single")?,
1133 QubitInitKind::Tuple(qis) => {
1134 if qis.is_empty() {
1135 write!(indent, "Unit")?;
1136 } else {
1137 write!(indent, "Tuple:")?;
1138 indent = set_indentation(indent, 1);
1139 for qi in qis {
1140 write!(indent, "\n{qi}")?;
1141 }
1142 }
1143 }
1144 }
1145 Ok(())
1146 }
1147}
1148
1149/// An identifier.
1150#[derive(Clone, Debug, Eq, Hash, PartialEq)]
1151pub struct Ident {
1152 /// The node ID.
1153 pub id: NodeId,
1154 /// The span.
1155 pub span: Span,
1156 /// The identifier name.
1157 pub name: Rc<str>,
1158}
1159
1160impl Display for Ident {
1161 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1162 write!(f, "Ident {} {} \"{}\"", self.id, self.span, self.name)
1163 }
1164}
1165
1166/// An attribute.
1167#[derive(Clone, Debug, PartialEq)]
1168pub enum Attr {
1169 /// Indicates that a callable is an entry point to a program.
1170 EntryPoint,
1171}
1172
1173/// A field.
1174#[derive(Clone, Debug, Eq, PartialEq)]
1175pub enum Field {
1176 /// A field path.
1177 Path(FieldPath),
1178 /// A primitive field for a built-in type.
1179 Prim(PrimField),
1180 /// An invalid field.
1181 Err,
1182}
1183
1184impl Display for Field {
1185 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1186 match self {
1187 Field::Path(path) => write!(f, "Path({:?})", path.indices),
1188 Field::Prim(prim) => write!(f, "Prim({prim:?}"),
1189 Field::Err => f.write_str("Err"),
1190 }
1191 }
1192}
1193
1194/// A path to a field in a tuple or user-defined type.
1195#[derive(Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
1196pub struct FieldPath {
1197 /// The tuple item indices to follow in order from top to bottom.
1198 pub indices: Vec<usize>,
1199}
1200
1201/// A primitive field for a built-in type.
1202#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
1203pub enum PrimField {
1204 /// The start of a range.
1205 Start,
1206 /// The step of a range.
1207 Step,
1208 /// The end of a range.
1209 End,
1210}
1211
1212impl FromStr for PrimField {
1213 type Err = ();
1214
1215 fn from_str(s: &str) -> result::Result<Self, <Self as FromStr>::Err> {
1216 match s {
1217 "Start" => Ok(Self::Start),
1218 "Step" => Ok(Self::Step),
1219 "End" => Ok(Self::End),
1220 _ => Err(()),
1221 }
1222 }
1223}
1224
1225/// The visibility of a declaration.
1226#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1227pub enum Visibility {
1228 /// Visible everywhere.
1229 Public,
1230 /// Visible within a package.
1231 Internal,
1232}
1233
1234/// A callable kind.
1235#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1236pub enum CallableKind {
1237 /// A function.
1238 Function,
1239 /// An operation.
1240 Operation,
1241}
1242
1243impl Display for CallableKind {
1244 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1245 match self {
1246 CallableKind::Function => f.write_str("function"),
1247 CallableKind::Operation => f.write_str("operation"),
1248 }
1249 }
1250}
1251
1252/// The mutability of a binding.
1253#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1254pub enum Mutability {
1255 /// An immutable binding.
1256 Immutable,
1257 /// A mutable binding.
1258 Mutable,
1259}
1260
1261/// The source of an allocated qubit.
1262#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1263pub enum QubitSource {
1264 /// A qubit initialized to the zero state.
1265 Fresh,
1266 /// A qubit borrowed from another part of the program that may be in any state, and is expected
1267 /// to be returned to that state before being released.
1268 Dirty,
1269}
1270
1271/// A literal.
1272#[derive(Clone, Debug, PartialEq)]
1273pub enum Lit {
1274 /// A big integer literal.
1275 BigInt(BigInt),
1276 /// A boolean literal.
1277 Bool(bool),
1278 /// A floating-point literal.
1279 Double(f64),
1280 /// An integer literal.
1281 Int(i64),
1282 /// A Pauli operator literal.
1283 Pauli(Pauli),
1284 /// A measurement result literal.
1285 Result(Result),
1286}
1287
1288impl Display for Lit {
1289 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1290 match self {
1291 Lit::BigInt(val) => write!(f, "BigInt({val})")?,
1292 Lit::Bool(val) => write!(f, "Bool({val})")?,
1293 Lit::Double(val) => write!(f, "Double({val})")?,
1294 Lit::Int(val) => write!(f, "Int({val})")?,
1295 Lit::Pauli(val) => write!(f, "Pauli({val:?})")?,
1296 Lit::Result(val) => write!(f, "Result({val:?})")?,
1297 }
1298 Ok(())
1299 }
1300}
1301
1302/// A measurement result.
1303#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1304pub enum Result {
1305 /// The zero eigenvalue.
1306 Zero,
1307 /// The one eigenvalue.
1308 One,
1309}
1310
1311/// A Pauli operator.
1312#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1313pub enum Pauli {
1314 /// The Pauli I operator.
1315 I,
1316 /// The Pauli X operator.
1317 X,
1318 /// The Pauli Y operator.
1319 Y,
1320 /// The Pauli Z operator.
1321 Z,
1322}
1323
1324/// A functor that may be applied to an operation.
1325#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1326pub enum Functor {
1327 /// The adjoint functor.
1328 Adj,
1329 /// The controlled functor.
1330 Ctl,
1331}
1332
1333impl Display for Functor {
1334 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1335 match self {
1336 Functor::Adj => f.write_str("Adj"),
1337 Functor::Ctl => f.write_str("Ctl"),
1338 }
1339 }
1340}
1341
1342/// A strategy for generating a specialization.
1343#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1344pub enum SpecGen {
1345 /// Choose a strategy automatically.
1346 Auto,
1347 /// Distributes controlled qubits.
1348 Distribute,
1349 /// A specialization implementation is not generated, but is instead left as an opaque
1350 /// declaration.
1351 Intrinsic,
1352 /// Inverts the order of operations.
1353 Invert,
1354 /// Uses the body specialization without modification.
1355 Slf,
1356}
1357
1358/// A unary operator.
1359#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1360pub enum UnOp {
1361 /// A functor application.
1362 Functor(Functor),
1363 /// Negation: `-`.
1364 Neg,
1365 /// Bitwise NOT: `~~~`.
1366 NotB,
1367 /// Logical NOT: `not`.
1368 NotL,
1369 /// A leading `+`.
1370 Pos,
1371 /// Unwrap a user-defined type: `!`.
1372 Unwrap,
1373}
1374
1375impl Display for UnOp {
1376 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1377 match self {
1378 UnOp::Functor(func) => write!(f, "Functor {func:?}")?,
1379 _ => fmt::Debug::fmt(self, f)?,
1380 }
1381 Ok(())
1382 }
1383}
1384
1385/// A binary operator.
1386#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1387pub enum BinOp {
1388 /// Addition: `+`.
1389 Add,
1390 /// Bitwise AND: `&&&`.
1391 AndB,
1392 /// Logical AND: `and`.
1393 AndL,
1394 /// Division: `/`.
1395 Div,
1396 /// Equality: `==`.
1397 Eq,
1398 /// Exponentiation: `^`.
1399 Exp,
1400 /// Greater than: `>`.
1401 Gt,
1402 /// Greater than or equal: `>=`.
1403 Gte,
1404 /// Less than: `<`.
1405 Lt,
1406 /// Less than or equal: `<=`.
1407 Lte,
1408 /// Modulus: `%`.
1409 Mod,
1410 /// Multiplication: `*`.
1411 Mul,
1412 /// Inequality: `!=`.
1413 Neq,
1414 /// Bitwise OR: `|||`.
1415 OrB,
1416 /// Logical OR: `or`.
1417 OrL,
1418 /// Shift left: `<<<`.
1419 Shl,
1420 /// Shift right: `>>>`.
1421 Shr,
1422 /// Subtraction: `-`.
1423 Sub,
1424 /// Bitwise XOR: `^^^`.
1425 XorB,
1426}
1427