GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/callable-generic

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

718lines · 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 /// Whether 'T is callable with specific arguments and for specific outputs.
239 Callable { input: Ty, output: Ty },
240 /// A class that is not built-in to the compiler.
241 NonNativeClass(Rc<str>),
242}
243
244impl std::fmt::Display for ClassConstraint {
245 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
246 match self {
247 ClassConstraint::Eq => write!(f, "Eq"),
248 ClassConstraint::NonNativeClass(name) => write!(f, "{name}"),
249 ClassConstraint::Exp { power } => write!(f, "Exp<{power}>"),
250 ClassConstraint::Iterable { item } => write!(f, "Iterable<{item}>"),
251 ClassConstraint::Add => write!(f, "Add"),
252 ClassConstraint::Integral => write!(f, "Integral"),
253 ClassConstraint::Show => write!(f, "Show"),
254 ClassConstraint::Div => write!(f, "Div"),
255 ClassConstraint::Sub => write!(f, "Sub"),
256 ClassConstraint::Mul => write!(f, "Mul"),
257 ClassConstraint::Mod => write!(f, "Mod"),
258 ClassConstraint::Ord => write!(f, "Ord"),
259 ClassConstraint::Signed => write!(f, "Signed"),
260 ClassConstraint::Callable { input, output } => write!(f, "Callable<{input} -> {output}>"),
261 }
262 }
263}
264
265/// The kind of a generic parameter.
266#[derive(Clone, Debug, PartialEq)]
267pub enum TypeParameter {
268 /// A type parameter.
269 Ty {
270 name: Rc<str>,
271 bounds: ClassConstraints,
272 },
273 /// A functor parameter with a lower bound.
274 Functor(FunctorSetValue),
275}
276
277/// A generic parameter ID.
278#[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
279pub struct ParamId(u32);
280
281impl ParamId {
282 /// The successor of this ID.
283 #[must_use]
284 pub fn successor(self) -> Self {
285 Self(self.0 + 1)
286 }
287}
288
289impl From<usize> for ParamId {
290 fn from(value: usize) -> Self {
291 ParamId(
292 value
293 .try_into()
294 .expect("Type Parameter ID does not fit into u32"),
295 )
296 }
297}
298
299impl Display for ParamId {
300 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
301 Display::fmt(&self.0, f)
302 }
303}
304
305/// An argument to a generic parameter.
306#[derive(Clone, Debug, Eq, PartialEq)]
307pub enum GenericArg {
308 /// A type argument.
309 Ty(Ty),
310 /// A functor argument.
311 Functor(FunctorSet),
312}
313
314impl Display for GenericArg {
315 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
316 match self {
317 GenericArg::Ty(ty) => Display::fmt(ty, f),
318 GenericArg::Functor(functors) => Display::fmt(functors, f),
319 }
320 }
321}
322
323/// An arrow type: `->` for a function or `=>` for an operation.
324#[derive(Clone, Debug, Eq, PartialEq)]
325pub struct Arrow {
326 /// Whether the callable is a function or an operation.
327 pub kind: CallableKind,
328 /// The input type to the callable.
329 pub input: Box<Ty>,
330 /// The output type from the callable.
331 pub output: Box<Ty>,
332 /// The functors supported by the callable.
333 pub functors: FunctorSet,
334}
335
336impl Display for Arrow {
337 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
338 let arrow = match self.kind {
339 CallableKind::Function => "->",
340 CallableKind::Operation => "=>",
341 };
342 write!(f, "({} {arrow} {}", self.input, self.output)?;
343 if self.functors != FunctorSet::Value(FunctorSetValue::Empty) {
344 f.write_str(" is ")?;
345 Display::fmt(&self.functors, f)?;
346 }
347 f.write_char(')')
348 }
349}
350
351/// A primitive type.
352#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
353pub enum Prim {
354 /// The big integer type.
355 BigInt,
356 /// The boolean type.
357 Bool,
358 /// The floating-point type.
359 Double,
360 /// The integer type.
361 Int,
362 /// The Pauli operator type.
363 Pauli,
364 /// The qubit type.
365 Qubit,
366 /// The range type.
367 Range,
368 /// The range type without a lower bound.
369 RangeTo,
370 /// The range type without an upper bound.
371 RangeFrom,
372 /// The range type without lower and upper bounds.
373 RangeFull,
374 /// The measurement result type.
375 Result,
376 /// The string type.
377 String,
378}
379
380/// A set of functors.
381#[derive(Clone, Copy, Debug, Eq, PartialEq)]
382pub enum FunctorSet {
383 /// An evaluated set.
384 Value(FunctorSetValue),
385 /// A functor parameter.
386 Param(ParamId),
387 /// A placeholder functor variable used during type inference.
388 Infer(InferFunctorId),
389}
390
391impl FunctorSet {
392 /// Returns the contained value.
393 ///
394 /// # Panics
395 ///
396 /// Panics if this set is not a value.
397 #[must_use]
398 pub fn expect_value(self, msg: &str) -> FunctorSetValue {
399 match self {
400 Self::Value(value) => value,
401 Self::Param(_) | Self::Infer(_) => panic!("{msg}"),
402 }
403 }
404}
405
406impl Display for FunctorSet {
407 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
408 match self {
409 Self::Value(value) => Display::fmt(value, f),
410 Self::Param(param) => Display::fmt(param, f),
411 Self::Infer(infer) => Display::fmt(infer, f),
412 }
413 }
414}
415
416/// The value of a functor set.
417#[derive(Clone, Copy, Debug, Default, Hash, Eq, PartialEq)]
418pub enum FunctorSetValue {
419 /// The empty set.
420 #[default]
421 Empty,
422 /// The singleton adjoint set.
423 Adj,
424 /// The singleton controlled set.
425 Ctl,
426 /// The set of controlled and adjoint.
427 CtlAdj,
428}
429
430impl FunctorSetValue {
431 /// True if this set contains the functor.
432 #[must_use]
433 pub fn contains(&self, functor: &Functor) -> bool {
434 match self {
435 Self::Empty => false,
436 Self::Adj => matches!(functor, Functor::Adj),
437 Self::Ctl => matches!(functor, Functor::Ctl),
438 Self::CtlAdj => matches!(functor, Functor::Adj | Functor::Ctl),
439 }
440 }
441
442 /// The intersection of this set and another set.
443 #[must_use]
444 pub fn intersect(&self, other: &Self) -> Self {
445 match (self, other) {
446 (Self::Empty, _)
447 | (_, Self::Empty)
448 | (Self::Adj, Self::Ctl)
449 | (Self::Ctl, Self::Adj) => Self::Empty,
450 (Self::Adj, Self::Adj) => Self::Adj,
451 (Self::Ctl, Self::Ctl) => Self::Ctl,
452 (Self::CtlAdj, &set) | (&set, Self::CtlAdj) => set,
453 }
454 }
455
456 /// The union of this set and another set.
457 #[must_use]
458 pub fn union(&self, other: &Self) -> Self {
459 match (self, other) {
460 (Self::Empty, &set) | (&set, Self::Empty) => set,
461 (Self::Adj, Self::Adj) => Self::Adj,
462 (Self::Ctl, Self::Ctl) => Self::Ctl,
463 (Self::CtlAdj, _)
464 | (_, Self::CtlAdj)
465 | (Self::Adj, Self::Ctl)
466 | (Self::Ctl, Self::Adj) => Self::CtlAdj,
467 }
468 }
469}
470
471impl Display for FunctorSetValue {
472 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
473 match self {
474 Self::Empty => f.write_str("empty set"),
475 Self::Adj => f.write_str("Adj"),
476 Self::Ctl => f.write_str("Ctl"),
477 Self::CtlAdj => f.write_str("Adj + Ctl"),
478 }
479 }
480}
481
482/// A user-defined type.
483#[derive(Clone, Debug, PartialEq)]
484pub struct Udt {
485 /// The span.
486 pub span: Span,
487 /// The name.
488 pub name: Rc<str>,
489 // The definition.
490 pub definition: UdtDef,
491}
492
493impl Udt {
494 #[must_use]
495 pub fn get_pure_ty(&self) -> Ty {
496 fn get_pure_ty(def: &UdtDef) -> Ty {
497 match &def.kind {
498 UdtDefKind::Field(field) => field.ty.clone(),
499 UdtDefKind::Tuple(tup) => Ty::Tuple(tup.iter().map(get_pure_ty).collect()),
500 }
501 }
502 get_pure_ty(&self.definition)
503 }
504
505 /// The type scheme of the constructor for this type definition.
506 ///
507 /// # Arguments
508 ///
509 /// * `id` - The ID of the constructed type.
510 #[must_use]
511 pub fn cons_scheme(&self, id: ItemId) -> Scheme {
512 Scheme {
513 params: Vec::new(),
514 ty: Box::new(Arrow {
515 kind: CallableKind::Function,
516 input: Box::new(self.get_pure_ty()),
517 output: Box::new(Ty::Udt(Res::Item(id))),
518 functors: FunctorSet::Value(FunctorSetValue::Empty),
519 }),
520 }
521 }
522
523 /// The path to the field with the given name. Returns [None] if this user-defined type does not
524 /// have a field with the given name.
525 #[must_use]
526 pub fn field_path(&self, name: &str) -> Option<FieldPath> {
527 Self::find_field_path(&self.definition, name)
528 }
529
530 fn find_field_path(def: &UdtDef, name: &str) -> Option<FieldPath> {
531 match &def.kind {
532 UdtDefKind::Field(field) => field.name.as_ref().and_then(|field_name| {
533 if field_name.as_ref() == name {
534 Some(FieldPath::default())
535 } else {
536 None
537 }
538 }),
539 UdtDefKind::Tuple(defs) => defs.iter().enumerate().find_map(|(i, def)| {
540 Self::find_field_path(def, name).map(|mut path| {
541 path.indices.insert(0, i);
542 path
543 })
544 }),
545 }
546 }
547
548 fn find_field(&self, path: &FieldPath) -> Option<&UdtField> {
549 let mut udt_def = &self.definition;
550 for &index in &path.indices {
551 let UdtDefKind::Tuple(items) = &udt_def.kind else {
552 return None;
553 };
554 udt_def = &items[index];
555 }
556 let UdtDefKind::Field(field) = &udt_def.kind else {
557 return None;
558 };
559 Some(field)
560 }
561
562 /// The type of the field at the given path. Returns [None] if the path is not valid for this
563 /// user-defined type.
564 #[must_use]
565 pub fn field_ty(&self, path: &FieldPath) -> Option<&Ty> {
566 self.find_field(path).map(|field| &field.ty)
567 }
568
569 /// The type of the field with the given name. Returns [None] if this user-defined type does not
570 /// have a field with the given name.
571 #[must_use]
572 pub fn field_ty_by_name(&self, name: &str) -> Option<&Ty> {
573 let path = self.field_path(name)?;
574 self.field_ty(&path)
575 }
576}
577
578impl Display for Udt {
579 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
580 let mut indent = set_indentation(indented(f), 0);
581 write!(indent, "UDT {}:", self.span)?;
582 indent = set_indentation(indent, 1);
583 write!(indent, "\n{}", self.definition)?;
584 Ok(())
585 }
586}
587
588/// A UDT type definition.
589#[derive(Clone, Debug, PartialEq)]
590pub struct UdtDef {
591 /// The span.
592 pub span: Span,
593 /// The type definition kind.
594 pub kind: UdtDefKind,
595}
596
597impl Display for UdtDef {
598 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
599 write!(f, "TyDef {}: {}", self.span, self.kind)
600 }
601}
602
603/// A UDT type definition kind.
604#[derive(Clone, Debug, PartialEq)]
605pub enum UdtDefKind {
606 /// A field definition with an optional name but required type.
607 Field(UdtField),
608 /// A tuple.
609 Tuple(Vec<UdtDef>),
610}
611
612impl Display for UdtDefKind {
613 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
614 let mut indent = set_indentation(indented(f), 0);
615 match &self {
616 UdtDefKind::Field(field) => {
617 write!(indent, "Field:")?;
618 indent = set_indentation(indent, 1);
619 write!(indent, "{field}")?;
620 }
621 UdtDefKind::Tuple(ts) => {
622 if ts.is_empty() {
623 write!(indent, "Unit")?;
624 } else {
625 write!(indent, "Tuple:")?;
626 indent = set_indentation(indent, 1);
627 for t in ts {
628 write!(indent, "\n{t}")?;
629 }
630 }
631 }
632 }
633 Ok(())
634 }
635}
636
637/// A user-defined type.
638#[derive(Clone, Debug, PartialEq)]
639pub struct UdtField {
640 /// The span of the field name.
641 pub name_span: Option<Span>,
642 /// The field name.
643 pub name: Option<Rc<str>>,
644 // The field type.
645 pub ty: Ty,
646}
647
648impl Display for UdtField {
649 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
650 if let Some(n) = &self.name {
651 if let Some(s) = &self.name_span {
652 write!(f, "\nname: {n} {s}")?;
653 }
654 }
655 write!(f, "\ntype: {}", self.ty)?;
656 Ok(())
657 }
658}
659
660/// A placeholder type variable used during type inference.
661#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
662pub struct InferTyId(usize);
663
664impl InferTyId {
665 /// The successor of this ID.
666 #[must_use]
667 pub fn successor(self) -> Self {
668 Self(self.0 + 1)
669 }
670}
671
672impl Display for InferTyId {
673 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
674 write!(f, "?{}", self.0)
675 }
676}
677
678impl From<usize> for InferTyId {
679 fn from(value: usize) -> Self {
680 Self(value)
681 }
682}
683
684impl From<InferTyId> for usize {
685 fn from(value: InferTyId) -> Self {
686 value.0
687 }
688}
689
690/// A placeholder functor variable used during type inference.
691#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
692pub struct InferFunctorId(usize);
693
694impl InferFunctorId {
695 /// The successor of this ID.
696 #[must_use]
697 pub fn successor(self) -> Self {
698 Self(self.0 + 1)
699 }
700}
701
702impl Display for InferFunctorId {
703 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
704 write!(f, "f?{}", self.0)
705 }
706}
707
708impl From<InferFunctorId> for usize {
709 fn from(value: InferFunctorId) -> Self {
710 value.0
711 }
712}
713
714impl From<usize> for InferFunctorId {
715 fn from(value: usize) -> Self {
716 InferFunctorId(value)
717 }
718}
719