GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billti/bloch

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

640lines · 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<GenericParam>,
89 ty: Box<Arrow>,
90}
91
92impl Scheme {
93 /// Creates a new type scheme.
94 #[must_use]
95 pub fn new(params: Vec<GenericParam>, 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) -> &[GenericParam] {
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 GenericParam {
182 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
183 match self {
184 GenericParam::Ty => write!(f, "type"),
185 GenericParam::Functor(min) => write!(f, "functor ({min})"),
186 }
187 }
188}
189
190/// The kind of a generic parameter.
191#[derive(Clone, Debug, PartialEq)]
192pub enum GenericParam {
193 /// A type parameter.
194 Ty,
195 /// A functor parameter with a lower bound.
196 Functor(FunctorSetValue),
197}
198
199/// A generic parameter ID.
200#[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
201pub struct ParamId(u32);
202
203impl ParamId {
204 /// The successor of this ID.
205 #[must_use]
206 pub fn successor(self) -> Self {
207 Self(self.0 + 1)
208 }
209}
210
211impl From<usize> for ParamId {
212 fn from(value: usize) -> Self {
213 ParamId(
214 value
215 .try_into()
216 .expect("Type Parameter ID does not fit into u32"),
217 )
218 }
219}
220
221impl Display for ParamId {
222 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
223 Display::fmt(&self.0, f)
224 }
225}
226
227/// An argument to a generic parameter.
228#[derive(Clone, Debug, Eq, PartialEq)]
229pub enum GenericArg {
230 /// A type argument.
231 Ty(Ty),
232 /// A functor argument.
233 Functor(FunctorSet),
234}
235
236impl Display for GenericArg {
237 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
238 match self {
239 GenericArg::Ty(ty) => Display::fmt(ty, f),
240 GenericArg::Functor(functors) => Display::fmt(functors, f),
241 }
242 }
243}
244
245/// An arrow type: `->` for a function or `=>` for an operation.
246#[derive(Clone, Debug, Eq, PartialEq)]
247pub struct Arrow {
248 /// Whether the callable is a function or an operation.
249 pub kind: CallableKind,
250 /// The input type to the callable.
251 pub input: Box<Ty>,
252 /// The output type from the callable.
253 pub output: Box<Ty>,
254 /// The functors supported by the callable.
255 pub functors: FunctorSet,
256}
257
258impl Display for Arrow {
259 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
260 let arrow = match self.kind {
261 CallableKind::Function => "->",
262 CallableKind::Operation => "=>",
263 };
264 write!(f, "({} {arrow} {}", self.input, self.output)?;
265 if self.functors != FunctorSet::Value(FunctorSetValue::Empty) {
266 f.write_str(" is ")?;
267 Display::fmt(&self.functors, f)?;
268 }
269 f.write_char(')')
270 }
271}
272
273/// A primitive type.
274#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
275pub enum Prim {
276 /// The big integer type.
277 BigInt,
278 /// The boolean type.
279 Bool,
280 /// The floating-point type.
281 Double,
282 /// The integer type.
283 Int,
284 /// The Pauli operator type.
285 Pauli,
286 /// The qubit type.
287 Qubit,
288 /// The range type.
289 Range,
290 /// The range type without a lower bound.
291 RangeTo,
292 /// The range type without an upper bound.
293 RangeFrom,
294 /// The range type without lower and upper bounds.
295 RangeFull,
296 /// The measurement result type.
297 Result,
298 /// The string type.
299 String,
300}
301
302/// A set of functors.
303#[derive(Clone, Copy, Debug, Eq, PartialEq)]
304pub enum FunctorSet {
305 /// An evaluated set.
306 Value(FunctorSetValue),
307 /// A functor parameter.
308 Param(ParamId),
309 /// A placeholder functor variable used during type inference.
310 Infer(InferFunctorId),
311}
312
313impl FunctorSet {
314 /// Returns the contained value.
315 ///
316 /// # Panics
317 ///
318 /// Panics if this set is not a value.
319 #[must_use]
320 pub fn expect_value(self, msg: &str) -> FunctorSetValue {
321 match self {
322 Self::Value(value) => value,
323 Self::Param(_) | Self::Infer(_) => panic!("{msg}"),
324 }
325 }
326}
327
328impl Display for FunctorSet {
329 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
330 match self {
331 Self::Value(value) => Display::fmt(value, f),
332 Self::Param(param) => Display::fmt(param, f),
333 Self::Infer(infer) => Display::fmt(infer, f),
334 }
335 }
336}
337
338/// The value of a functor set.
339#[derive(Clone, Copy, Debug, Default, Hash, Eq, PartialEq)]
340pub enum FunctorSetValue {
341 /// The empty set.
342 #[default]
343 Empty,
344 /// The singleton adjoint set.
345 Adj,
346 /// The singleton controlled set.
347 Ctl,
348 /// The set of controlled and adjoint.
349 CtlAdj,
350}
351
352impl FunctorSetValue {
353 /// True if this set contains the functor.
354 #[must_use]
355 pub fn contains(&self, functor: &Functor) -> bool {
356 match self {
357 Self::Empty => false,
358 Self::Adj => matches!(functor, Functor::Adj),
359 Self::Ctl => matches!(functor, Functor::Ctl),
360 Self::CtlAdj => matches!(functor, Functor::Adj | Functor::Ctl),
361 }
362 }
363
364 /// The intersection of this set and another set.
365 #[must_use]
366 pub fn intersect(&self, other: &Self) -> Self {
367 match (self, other) {
368 (Self::Empty, _)
369 | (_, Self::Empty)
370 | (Self::Adj, Self::Ctl)
371 | (Self::Ctl, Self::Adj) => Self::Empty,
372 (Self::Adj, Self::Adj) => Self::Adj,
373 (Self::Ctl, Self::Ctl) => Self::Ctl,
374 (Self::CtlAdj, &set) | (&set, Self::CtlAdj) => set,
375 }
376 }
377
378 /// The union of this set and another set.
379 #[must_use]
380 pub fn union(&self, other: &Self) -> Self {
381 match (self, other) {
382 (Self::Empty, &set) | (&set, Self::Empty) => set,
383 (Self::Adj, Self::Adj) => Self::Adj,
384 (Self::Ctl, Self::Ctl) => Self::Ctl,
385 (Self::CtlAdj, _)
386 | (_, Self::CtlAdj)
387 | (Self::Adj, Self::Ctl)
388 | (Self::Ctl, Self::Adj) => Self::CtlAdj,
389 }
390 }
391}
392
393impl Display for FunctorSetValue {
394 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
395 match self {
396 Self::Empty => f.write_str("empty set"),
397 Self::Adj => f.write_str("Adj"),
398 Self::Ctl => f.write_str("Ctl"),
399 Self::CtlAdj => f.write_str("Adj + Ctl"),
400 }
401 }
402}
403
404/// A user-defined type.
405#[derive(Clone, Debug, PartialEq)]
406pub struct Udt {
407 /// The span.
408 pub span: Span,
409 /// The name.
410 pub name: Rc<str>,
411 // The definition.
412 pub definition: UdtDef,
413}
414
415impl Udt {
416 #[must_use]
417 pub fn get_pure_ty(&self) -> Ty {
418 fn get_pure_ty(def: &UdtDef) -> Ty {
419 match &def.kind {
420 UdtDefKind::Field(field) => field.ty.clone(),
421 UdtDefKind::Tuple(tup) => Ty::Tuple(tup.iter().map(get_pure_ty).collect()),
422 }
423 }
424 get_pure_ty(&self.definition)
425 }
426
427 /// The type scheme of the constructor for this type definition.
428 ///
429 /// # Arguments
430 ///
431 /// * `id` - The ID of the constructed type.
432 #[must_use]
433 pub fn cons_scheme(&self, id: ItemId) -> Scheme {
434 Scheme {
435 params: Vec::new(),
436 ty: Box::new(Arrow {
437 kind: CallableKind::Function,
438 input: Box::new(self.get_pure_ty()),
439 output: Box::new(Ty::Udt(Res::Item(id))),
440 functors: FunctorSet::Value(FunctorSetValue::Empty),
441 }),
442 }
443 }
444
445 /// The path to the field with the given name. Returns [None] if this user-defined type does not
446 /// have a field with the given name.
447 #[must_use]
448 pub fn field_path(&self, name: &str) -> Option<FieldPath> {
449 Self::find_field_path(&self.definition, name)
450 }
451
452 fn find_field_path(def: &UdtDef, name: &str) -> Option<FieldPath> {
453 match &def.kind {
454 UdtDefKind::Field(field) => field.name.as_ref().and_then(|field_name| {
455 if field_name.as_ref() == name {
456 Some(FieldPath::default())
457 } else {
458 None
459 }
460 }),
461 UdtDefKind::Tuple(defs) => defs.iter().enumerate().find_map(|(i, def)| {
462 Self::find_field_path(def, name).map(|mut path| {
463 path.indices.insert(0, i);
464 path
465 })
466 }),
467 }
468 }
469
470 fn find_field(&self, path: &FieldPath) -> Option<&UdtField> {
471 let mut udt_def = &self.definition;
472 for &index in &path.indices {
473 let UdtDefKind::Tuple(items) = &udt_def.kind else {
474 return None;
475 };
476 udt_def = &items[index];
477 }
478 let UdtDefKind::Field(field) = &udt_def.kind else {
479 return None;
480 };
481 Some(field)
482 }
483
484 /// The type of the field at the given path. Returns [None] if the path is not valid for this
485 /// user-defined type.
486 #[must_use]
487 pub fn field_ty(&self, path: &FieldPath) -> Option<&Ty> {
488 self.find_field(path).map(|field| &field.ty)
489 }
490
491 /// The type of the field with the given name. Returns [None] if this user-defined type does not
492 /// have a field with the given name.
493 #[must_use]
494 pub fn field_ty_by_name(&self, name: &str) -> Option<&Ty> {
495 let path = self.field_path(name)?;
496 self.field_ty(&path)
497 }
498}
499
500impl Display for Udt {
501 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
502 let mut indent = set_indentation(indented(f), 0);
503 write!(indent, "UDT {}:", self.span)?;
504 indent = set_indentation(indent, 1);
505 write!(indent, "\n{}", self.definition)?;
506 Ok(())
507 }
508}
509
510/// A UDT type definition.
511#[derive(Clone, Debug, PartialEq)]
512pub struct UdtDef {
513 /// The span.
514 pub span: Span,
515 /// The type definition kind.
516 pub kind: UdtDefKind,
517}
518
519impl Display for UdtDef {
520 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
521 write!(f, "TyDef {}: {}", self.span, self.kind)
522 }
523}
524
525/// A UDT type definition kind.
526#[derive(Clone, Debug, PartialEq)]
527pub enum UdtDefKind {
528 /// A field definition with an optional name but required type.
529 Field(UdtField),
530 /// A tuple.
531 Tuple(Vec<UdtDef>),
532}
533
534impl Display for UdtDefKind {
535 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
536 let mut indent = set_indentation(indented(f), 0);
537 match &self {
538 UdtDefKind::Field(field) => {
539 write!(indent, "Field:")?;
540 indent = set_indentation(indent, 1);
541 write!(indent, "{field}")?;
542 }
543 UdtDefKind::Tuple(ts) => {
544 if ts.is_empty() {
545 write!(indent, "Unit")?;
546 } else {
547 write!(indent, "Tuple:")?;
548 indent = set_indentation(indent, 1);
549 for t in ts {
550 write!(indent, "\n{t}")?;
551 }
552 }
553 }
554 }
555 Ok(())
556 }
557}
558
559/// A user-defined type.
560#[derive(Clone, Debug, PartialEq)]
561pub struct UdtField {
562 /// The span of the field name.
563 pub name_span: Option<Span>,
564 /// The field name.
565 pub name: Option<Rc<str>>,
566 // The field type.
567 pub ty: Ty,
568}
569
570impl Display for UdtField {
571 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
572 if let Some(n) = &self.name {
573 if let Some(s) = &self.name_span {
574 write!(f, "\nname: {n} {s}")?;
575 }
576 }
577 write!(f, "\ntype: {}", self.ty)?;
578 Ok(())
579 }
580}
581
582/// A placeholder type variable used during type inference.
583#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
584pub struct InferTyId(usize);
585
586impl InferTyId {
587 /// The successor of this ID.
588 #[must_use]
589 pub fn successor(self) -> Self {
590 Self(self.0 + 1)
591 }
592}
593
594impl Display for InferTyId {
595 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
596 write!(f, "?{}", self.0)
597 }
598}
599
600impl From<usize> for InferTyId {
601 fn from(value: usize) -> Self {
602 Self(value)
603 }
604}
605
606impl From<InferTyId> for usize {
607 fn from(value: InferTyId) -> Self {
608 value.0
609 }
610}
611
612/// A placeholder functor variable used during type inference.
613#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
614pub struct InferFunctorId(usize);
615
616impl InferFunctorId {
617 /// The successor of this ID.
618 #[must_use]
619 pub fn successor(self) -> Self {
620 Self(self.0 + 1)
621 }
622}
623
624impl Display for InferFunctorId {
625 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
626 write!(f, "f?{}", self.0)
627 }
628}
629
630impl From<InferFunctorId> for usize {
631 fn from(value: InferFunctorId) -> Self {
632 value.0
633 }
634}
635
636impl From<usize> for InferFunctorId {
637 fn from(value: usize) -> Self {
638 InferFunctorId(value)
639 }
640}