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.19.0

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/ty.rs

715lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use indenter::{Indented, indented};
5use qsc_data_structures::span::Span;
6use rustc_hash::FxHashMap;
7
8use crate::fir::{CallableKind, FieldPath, Functor, ItemId, Res};
9use std::{
10 fmt::{self, Debug, Display, Formatter, Write},
11 rc::Rc,
12};
13
14fn set_indentation<'a, 'b>(
15 indent: Indented<'a, Formatter<'b>>,
16 level: usize,
17) -> Indented<'a, Formatter<'b>> {
18 match level {
19 0 => indent.with_str(""),
20 1 => indent.with_str(" "),
21 2 => indent.with_str(" "),
22 _ => unimplemented!("intentation level not supported"),
23 }
24}
25
26/// A type.
27#[derive(Clone, Debug, Default, Eq, PartialEq)]
28pub enum Ty {
29 /// An array type.
30 Array(Box<Ty>),
31 /// An arrow type: `->` for a function or `=>` for an operation.
32 Arrow(Box<Arrow>),
33 /// A placeholder type variable used during type inference.
34 Infer(InferTyId),
35 /// A type parameter.
36 Param(ParamId),
37 /// A primitive type.
38 Prim(Prim),
39 /// A tuple type.
40 Tuple(Vec<Ty>),
41 /// A user-defined type.
42 Udt(Res),
43 /// An invalid type.
44 #[default]
45 Err,
46}
47
48impl Ty {
49 /// The unit type.
50 pub const UNIT: Self = Self::Tuple(Vec::new());
51}
52
53impl Display for Ty {
54 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
55 match self {
56 Ty::Array(item) => write!(f, "({item})[]"),
57 Ty::Arrow(arrow) => Display::fmt(arrow, f),
58 Ty::Infer(infer) => Display::fmt(infer, f),
59 Ty::Param(param_id) => write!(f, "Param<{param_id}>"),
60 Ty::Prim(prim) => Debug::fmt(prim, f),
61 Ty::Tuple(items) => {
62 if items.is_empty() {
63 f.write_str("Unit")
64 } else {
65 f.write_str("(")?;
66 if let Some((first, rest)) = items.split_first() {
67 Display::fmt(first, f)?;
68 if rest.is_empty() {
69 f.write_str(",")?;
70 } else {
71 for item in rest {
72 f.write_str(", ")?;
73 Display::fmt(item, f)?;
74 }
75 }
76 }
77 f.write_str(")")
78 }
79 }
80 Ty::Udt(res) => write!(f, "UDT<{res}>"),
81 Ty::Err => f.write_str("?"),
82 }
83 }
84}
85
86/// A type scheme.
87pub struct Scheme {
88 params: Vec<TypeParameter>,
89 ty: Box<Arrow>,
90}
91
92impl Scheme {
93 /// Creates a new type scheme.
94 #[must_use]
95 pub fn new(params: Vec<TypeParameter>, ty: Box<Arrow>) -> Self {
96 Self { params, ty }
97 }
98
99 /// The generic parameters to the type.
100 #[must_use]
101 pub fn params(&self) -> &[TypeParameter] {
102 &self.params
103 }
104
105 /// Instantiates this type scheme with the given arguments.
106 ///
107 /// # Errors
108 ///
109 /// Returns an error if the given arguments do not match the scheme parameters.
110 pub fn instantiate(&self, args: &[GenericArg]) -> Result<Arrow, InstantiationError> {
111 if args.len() == self.params.len() {
112 let args: FxHashMap<_, _> = self
113 .params
114 .iter()
115 .enumerate()
116 .map(|(ix, _)| ParamId::from(ix))
117 .zip(args)
118 .collect();
119 instantiate_arrow_ty(|name| args.get(name).copied(), &self.ty)
120 } else {
121 Err(InstantiationError::Arity)
122 }
123 }
124}
125
126/// A type scheme instantiation error.
127#[derive(Debug)]
128pub enum InstantiationError {
129 /// The number of generic arguments does not match the number of generic parameters.
130 Arity,
131 /// A generic argument does not match the kind of its corresponding generic parameter.
132 Kind(ParamId),
133}
134
135fn instantiate_ty<'a>(
136 arg: impl Fn(&ParamId) -> Option<&'a GenericArg> + Copy,
137 ty: &Ty,
138) -> Result<Ty, InstantiationError> {
139 match ty {
140 Ty::Err | Ty::Infer(_) | Ty::Prim(_) | Ty::Udt(_) => Ok(ty.clone()),
141 Ty::Array(item) => Ok(Ty::Array(Box::new(instantiate_ty(arg, item)?))),
142 Ty::Arrow(arrow) => Ok(Ty::Arrow(Box::new(instantiate_arrow_ty(arg, arrow)?))),
143 Ty::Param(param) => match arg(param) {
144 Some(GenericArg::Ty(ty_arg)) => Ok(ty_arg.clone()),
145 Some(_) => Err(InstantiationError::Kind(*param)),
146 None => Ok(ty.clone()),
147 },
148 Ty::Tuple(items) => Ok(Ty::Tuple(
149 items
150 .iter()
151 .map(|item| instantiate_ty(arg, item))
152 .collect::<Result<_, _>>()?,
153 )),
154 }
155}
156
157fn instantiate_arrow_ty<'a>(
158 arg: impl Fn(&ParamId) -> Option<&'a GenericArg> + Copy,
159 arrow: &Arrow,
160) -> Result<Arrow, InstantiationError> {
161 let input = instantiate_ty(arg, &arrow.input)?;
162 let output = instantiate_ty(arg, &arrow.output)?;
163 let functors = if let FunctorSet::Param(param) = arrow.functors {
164 match arg(&param) {
165 Some(GenericArg::Functor(functor_arg)) => *functor_arg,
166 Some(_) => return Err(InstantiationError::Kind(param)),
167 None => arrow.functors,
168 }
169 } else {
170 arrow.functors
171 };
172
173 Ok(Arrow {
174 kind: arrow.kind,
175 input: Box::new(input),
176 output: Box::new(output),
177 functors,
178 })
179}
180
181impl Display for TypeParameter {
182 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
183 match self {
184 TypeParameter::Ty { name, bounds } => {
185 write!(f, "type ({name}){bounds}")
186 }
187 TypeParameter::Functor(min) => write!(f, "functor ({min})"),
188 }
189 }
190}
191#[derive(Clone, Debug, Default, Eq, PartialEq)]
192pub struct ClassConstraints(pub Box<[ClassConstraint]>);
193
194impl std::fmt::Display for ClassConstraints {
195 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
196 if self.0.is_empty() {
197 Ok(())
198 } else {
199 let bounds = self
200 .0
201 .iter()
202 .map(std::string::ToString::to_string)
203 .collect::<Vec<_>>()
204 .join(", ");
205 write!(f, "{bounds}")
206 }
207 }
208}
209
210#[derive(Clone, Debug, Eq, PartialEq)]
211pub enum ClassConstraint {
212 /// Whether or not 'T can be compared via Eq to values of the same domain.
213 Eq,
214 /// Whether or not 'T can be added to values of the same domain via the + operator.
215 Add,
216 Exp {
217 // `base` is inferred to be the self type
218 power: Ty,
219 },
220 /// If 'T is iterable, then it can be iterated over and the items inside are yielded (of type `item`).
221 Iterable { item: Ty },
222 /// Whether or not 'T can be divided by values of the same domain via the / operator.
223 Div,
224 /// Whether or not 'T can be subtracted from values of the same domain via the - operator.
225 Sub,
226 /// Whether or not 'T can be multiplied by values of the same domain via the * operator.
227 Mul,
228 /// Whether or not 'T can be taken modulo values of the same domain via the % operator.
229 Mod,
230 /// Whether or not 'T can be compared via Ord to values of the same domain.
231 Ord,
232 /// Whether or not 'T can be signed.
233 Signed,
234 /// Whether or not 'T is an integral type (can be used in bit shifting operators).
235 Integral,
236 /// Whether or not 'T can be displayed as a string (converted to a string).
237 Show,
238 /// A class that is not built-in to the compiler.
239 NonNativeClass(Rc<str>),
240}
241
242impl std::fmt::Display for ClassConstraint {
243 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
244 match self {
245 ClassConstraint::Eq => write!(f, "Eq"),
246 ClassConstraint::NonNativeClass(name) => write!(f, "{name}"),
247 ClassConstraint::Exp { power } => write!(f, "Exp<{power}>"),
248 ClassConstraint::Iterable { item } => write!(f, "Iterable<{item}>"),
249 ClassConstraint::Add => write!(f, "Add"),
250 ClassConstraint::Integral => write!(f, "Integral"),
251 ClassConstraint::Show => write!(f, "Show"),
252 ClassConstraint::Div => write!(f, "Div"),
253 ClassConstraint::Sub => write!(f, "Sub"),
254 ClassConstraint::Mul => write!(f, "Mul"),
255 ClassConstraint::Mod => write!(f, "Mod"),
256 ClassConstraint::Ord => write!(f, "Ord"),
257 ClassConstraint::Signed => write!(f, "Signed"),
258 }
259 }
260}
261
262/// The kind of a generic parameter.
263#[derive(Clone, Debug, PartialEq)]
264pub enum TypeParameter {
265 /// A type parameter.
266 Ty {
267 name: Rc<str>,
268 bounds: ClassConstraints,
269 },
270 /// A functor parameter with a lower bound.
271 Functor(FunctorSetValue),
272}
273
274/// A generic parameter ID.
275#[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
276pub struct ParamId(u32);
277
278impl ParamId {
279 /// The successor of this ID.
280 #[must_use]
281 pub fn successor(self) -> Self {
282 Self(self.0 + 1)
283 }
284}
285
286impl From<usize> for ParamId {
287 fn from(value: usize) -> Self {
288 ParamId(
289 value
290 .try_into()
291 .expect("Type Parameter ID does not fit into u32"),
292 )
293 }
294}
295
296impl Display for ParamId {
297 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
298 Display::fmt(&self.0, f)
299 }
300}
301
302/// An argument to a generic parameter.
303#[derive(Clone, Debug, Eq, PartialEq)]
304pub enum GenericArg {
305 /// A type argument.
306 Ty(Ty),
307 /// A functor argument.
308 Functor(FunctorSet),
309}
310
311impl Display for GenericArg {
312 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
313 match self {
314 GenericArg::Ty(ty) => Display::fmt(ty, f),
315 GenericArg::Functor(functors) => Display::fmt(functors, f),
316 }
317 }
318}
319
320/// An arrow type: `->` for a function or `=>` for an operation.
321#[derive(Clone, Debug, Eq, PartialEq)]
322pub struct Arrow {
323 /// Whether the callable is a function or an operation.
324 pub kind: CallableKind,
325 /// The input type to the callable.
326 pub input: Box<Ty>,
327 /// The output type from the callable.
328 pub output: Box<Ty>,
329 /// The functors supported by the callable.
330 pub functors: FunctorSet,
331}
332
333impl Display for Arrow {
334 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
335 let arrow = match self.kind {
336 CallableKind::Function => "->",
337 CallableKind::Operation => "=>",
338 };
339 write!(f, "({} {arrow} {}", self.input, self.output)?;
340 if self.functors != FunctorSet::Value(FunctorSetValue::Empty) {
341 f.write_str(" is ")?;
342 Display::fmt(&self.functors, f)?;
343 }
344 f.write_char(')')
345 }
346}
347
348/// A primitive type.
349#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
350pub enum Prim {
351 /// The big integer type.
352 BigInt,
353 /// The boolean type.
354 Bool,
355 /// The floating-point type.
356 Double,
357 /// The integer type.
358 Int,
359 /// The Pauli operator type.
360 Pauli,
361 /// The qubit type.
362 Qubit,
363 /// The range type.
364 Range,
365 /// The range type without a lower bound.
366 RangeTo,
367 /// The range type without an upper bound.
368 RangeFrom,
369 /// The range type without lower and upper bounds.
370 RangeFull,
371 /// The measurement result type.
372 Result,
373 /// The string type.
374 String,
375}
376
377/// A set of functors.
378#[derive(Clone, Copy, Debug, Eq, PartialEq)]
379pub enum FunctorSet {
380 /// An evaluated set.
381 Value(FunctorSetValue),
382 /// A functor parameter.
383 Param(ParamId),
384 /// A placeholder functor variable used during type inference.
385 Infer(InferFunctorId),
386}
387
388impl FunctorSet {
389 /// Returns the contained value.
390 ///
391 /// # Panics
392 ///
393 /// Panics if this set is not a value.
394 #[must_use]
395 pub fn expect_value(self, msg: &str) -> FunctorSetValue {
396 match self {
397 Self::Value(value) => value,
398 Self::Param(_) | Self::Infer(_) => panic!("{msg}"),
399 }
400 }
401}
402
403impl Display for FunctorSet {
404 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
405 match self {
406 Self::Value(value) => Display::fmt(value, f),
407 Self::Param(param) => Display::fmt(param, f),
408 Self::Infer(infer) => Display::fmt(infer, f),
409 }
410 }
411}
412
413/// The value of a functor set.
414#[derive(Clone, Copy, Debug, Default, Hash, Eq, PartialEq)]
415pub enum FunctorSetValue {
416 /// The empty set.
417 #[default]
418 Empty,
419 /// The singleton adjoint set.
420 Adj,
421 /// The singleton controlled set.
422 Ctl,
423 /// The set of controlled and adjoint.
424 CtlAdj,
425}
426
427impl FunctorSetValue {
428 /// True if this set contains the functor.
429 #[must_use]
430 pub fn contains(&self, functor: &Functor) -> bool {
431 match self {
432 Self::Empty => false,
433 Self::Adj => matches!(functor, Functor::Adj),
434 Self::Ctl => matches!(functor, Functor::Ctl),
435 Self::CtlAdj => matches!(functor, Functor::Adj | Functor::Ctl),
436 }
437 }
438
439 /// The intersection of this set and another set.
440 #[must_use]
441 pub fn intersect(&self, other: &Self) -> Self {
442 match (self, other) {
443 (Self::Empty, _)
444 | (_, Self::Empty)
445 | (Self::Adj, Self::Ctl)
446 | (Self::Ctl, Self::Adj) => Self::Empty,
447 (Self::Adj, Self::Adj) => Self::Adj,
448 (Self::Ctl, Self::Ctl) => Self::Ctl,
449 (Self::CtlAdj, &set) | (&set, Self::CtlAdj) => set,
450 }
451 }
452
453 /// The union of this set and another set.
454 #[must_use]
455 pub fn union(&self, other: &Self) -> Self {
456 match (self, other) {
457 (Self::Empty, &set) | (&set, Self::Empty) => set,
458 (Self::Adj, Self::Adj) => Self::Adj,
459 (Self::Ctl, Self::Ctl) => Self::Ctl,
460 (Self::CtlAdj, _)
461 | (_, Self::CtlAdj)
462 | (Self::Adj, Self::Ctl)
463 | (Self::Ctl, Self::Adj) => Self::CtlAdj,
464 }
465 }
466}
467
468impl Display for FunctorSetValue {
469 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
470 match self {
471 Self::Empty => f.write_str("empty set"),
472 Self::Adj => f.write_str("Adj"),
473 Self::Ctl => f.write_str("Ctl"),
474 Self::CtlAdj => f.write_str("Adj + Ctl"),
475 }
476 }
477}
478
479/// A user-defined type.
480#[derive(Clone, Debug, PartialEq)]
481pub struct Udt {
482 /// The span.
483 pub span: Span,
484 /// The name.
485 pub name: Rc<str>,
486 // The definition.
487 pub definition: UdtDef,
488}
489
490impl Udt {
491 #[must_use]
492 pub fn get_pure_ty(&self) -> Ty {
493 fn get_pure_ty(def: &UdtDef) -> Ty {
494 match &def.kind {
495 UdtDefKind::Field(field) => field.ty.clone(),
496 UdtDefKind::Tuple(tup) => Ty::Tuple(tup.iter().map(get_pure_ty).collect()),
497 }
498 }
499 get_pure_ty(&self.definition)
500 }
501
502 /// The type scheme of the constructor for this type definition.
503 ///
504 /// # Arguments
505 ///
506 /// * `id` - The ID of the constructed type.
507 #[must_use]
508 pub fn cons_scheme(&self, id: ItemId) -> Scheme {
509 Scheme {
510 params: Vec::new(),
511 ty: Box::new(Arrow {
512 kind: CallableKind::Function,
513 input: Box::new(self.get_pure_ty()),
514 output: Box::new(Ty::Udt(Res::Item(id))),
515 functors: FunctorSet::Value(FunctorSetValue::Empty),
516 }),
517 }
518 }
519
520 /// The path to the field with the given name. Returns [None] if this user-defined type does not
521 /// have a field with the given name.
522 #[must_use]
523 pub fn field_path(&self, name: &str) -> Option<FieldPath> {
524 Self::find_field_path(&self.definition, name)
525 }
526
527 fn find_field_path(def: &UdtDef, name: &str) -> Option<FieldPath> {
528 match &def.kind {
529 UdtDefKind::Field(field) => field.name.as_ref().and_then(|field_name| {
530 if field_name.as_ref() == name {
531 Some(FieldPath::default())
532 } else {
533 None
534 }
535 }),
536 UdtDefKind::Tuple(defs) => defs.iter().enumerate().find_map(|(i, def)| {
537 Self::find_field_path(def, name).map(|mut path| {
538 path.indices.insert(0, i);
539 path
540 })
541 }),
542 }
543 }
544
545 fn find_field(&self, path: &FieldPath) -> Option<&UdtField> {
546 let mut udt_def = &self.definition;
547 for &index in &path.indices {
548 let UdtDefKind::Tuple(items) = &udt_def.kind else {
549 return None;
550 };
551 udt_def = &items[index];
552 }
553 let UdtDefKind::Field(field) = &udt_def.kind else {
554 return None;
555 };
556 Some(field)
557 }
558
559 /// The type of the field at the given path. Returns [None] if the path is not valid for this
560 /// user-defined type.
561 #[must_use]
562 pub fn field_ty(&self, path: &FieldPath) -> Option<&Ty> {
563 self.find_field(path).map(|field| &field.ty)
564 }
565
566 /// The type of the field with the given name. Returns [None] if this user-defined type does not
567 /// have a field with the given name.
568 #[must_use]
569 pub fn field_ty_by_name(&self, name: &str) -> Option<&Ty> {
570 let path = self.field_path(name)?;
571 self.field_ty(&path)
572 }
573}
574
575impl Display for Udt {
576 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
577 let mut indent = set_indentation(indented(f), 0);
578 write!(indent, "UDT {}:", self.span)?;
579 indent = set_indentation(indent, 1);
580 write!(indent, "\n{}", self.definition)?;
581 Ok(())
582 }
583}
584
585/// A UDT type definition.
586#[derive(Clone, Debug, PartialEq)]
587pub struct UdtDef {
588 /// The span.
589 pub span: Span,
590 /// The type definition kind.
591 pub kind: UdtDefKind,
592}
593
594impl Display for UdtDef {
595 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
596 write!(f, "TyDef {}: {}", self.span, self.kind)
597 }
598}
599
600/// A UDT type definition kind.
601#[derive(Clone, Debug, PartialEq)]
602pub enum UdtDefKind {
603 /// A field definition with an optional name but required type.
604 Field(UdtField),
605 /// A tuple.
606 Tuple(Vec<UdtDef>),
607}
608
609impl Display for UdtDefKind {
610 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
611 let mut indent = set_indentation(indented(f), 0);
612 match &self {
613 UdtDefKind::Field(field) => {
614 write!(indent, "Field:")?;
615 indent = set_indentation(indent, 1);
616 write!(indent, "{field}")?;
617 }
618 UdtDefKind::Tuple(ts) => {
619 if ts.is_empty() {
620 write!(indent, "Unit")?;
621 } else {
622 write!(indent, "Tuple:")?;
623 indent = set_indentation(indent, 1);
624 for t in ts {
625 write!(indent, "\n{t}")?;
626 }
627 }
628 }
629 }
630 Ok(())
631 }
632}
633
634/// A user-defined type.
635#[derive(Clone, Debug, PartialEq)]
636pub struct UdtField {
637 /// The span of the field name.
638 pub name_span: Option<Span>,
639 /// The field name.
640 pub name: Option<Rc<str>>,
641 // The field type.
642 pub ty: Ty,
643}
644
645impl Display for UdtField {
646 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
647 if let Some(n) = &self.name {
648 if let Some(s) = &self.name_span {
649 write!(f, "\nname: {n} {s}")?;
650 }
651 }
652 write!(f, "\ntype: {}", self.ty)?;
653 Ok(())
654 }
655}
656
657/// A placeholder type variable used during type inference.
658#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
659pub struct InferTyId(usize);
660
661impl InferTyId {
662 /// The successor of this ID.
663 #[must_use]
664 pub fn successor(self) -> Self {
665 Self(self.0 + 1)
666 }
667}
668
669impl Display for InferTyId {
670 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
671 write!(f, "?{}", self.0)
672 }
673}
674
675impl From<usize> for InferTyId {
676 fn from(value: usize) -> Self {
677 Self(value)
678 }
679}
680
681impl From<InferTyId> for usize {
682 fn from(value: InferTyId) -> Self {
683 value.0
684 }
685}
686
687/// A placeholder functor variable used during type inference.
688#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
689pub struct InferFunctorId(usize);
690
691impl InferFunctorId {
692 /// The successor of this ID.
693 #[must_use]
694 pub fn successor(self) -> Self {
695 Self(self.0 + 1)
696 }
697}
698
699impl Display for InferFunctorId {
700 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
701 write!(f, "f?{}", self.0)
702 }
703}
704
705impl From<InferFunctorId> for usize {
706 fn from(value: InferFunctorId) -> Self {
707 value.0
708 }
709}
710
711impl From<usize> for InferFunctorId {
712 fn from(value: usize) -> Self {
713 InferFunctorId(value)
714 }
715}
716