microsoft/qdk

Public

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

CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.0.33

Branches

Tags

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

Clone

HTTPS

Download ZIP

compiler/qsc_frontend/src/compile.rs

616lines · modecode

1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7pub mod preprocess;
8
9use crate::{
10 error::WithSource,
11 lower::{self, Lowerer},
12 resolve::{self, Locals, Names, Resolver},
13 typeck::{self, Checker, Table},
14};
15use bitflags::bitflags;
16use miette::{Diagnostic, Report};
17use preprocess::TrackedName;
18use qsc_ast::{
19 assigner::Assigner as AstAssigner,
20 ast::{self, TopLevelNode},
21 mut_visit::MutVisitor,
22 validate::Validator as AstValidator,
23 visit::Visitor as _,
24};
25use qsc_data_structures::{
26 index_map::{self, IndexMap},
27 span::Span,
28};
29use qsc_hir::{
30 assigner::Assigner as HirAssigner,
31 global,
32 hir::{self, PackageId},
33 validate::Validator as HirValidator,
34 visit::Visitor as _,
35};
36use std::{fmt::Debug, str::FromStr, sync::Arc};
37use thiserror::Error;
38
39bitflags! {
40 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
41 pub struct RuntimeCapabilityFlags: u32 {
42 const ConditionalForwardBranching = 0b0000_0001;
43 const IntegerComputations = 0b0000_0010;
44 const FloatingPointComputation = 0b0000_0100;
45 const BackwardsBranching = 0b0000_1000;
46 const HigherLevelConstructs = 0b0001_0000;
47 }
48}
49
50#[derive(Clone, Copy, Debug, PartialEq)]
51pub enum ConfigAttr {
52 Unrestricted,
53 Base,
54}
55
56impl ConfigAttr {
57 #[must_use]
58 pub fn to_str(&self) -> &'static str {
59 match self {
60 Self::Unrestricted => "Unrestricted",
61 Self::Base => "Base",
62 }
63 }
64
65 #[must_use]
66 pub fn is_target_str(s: &str) -> bool {
67 Self::from_str(s).is_ok()
68 }
69}
70
71impl FromStr for ConfigAttr {
72 type Err = ();
73
74 fn from_str(s: &str) -> Result<Self, Self::Err> {
75 match s {
76 "Unrestricted" => Ok(ConfigAttr::Unrestricted),
77 "Base" => Ok(ConfigAttr::Base),
78 _ => Err(()),
79 }
80 }
81}
82
83impl From<ConfigAttr> for RuntimeCapabilityFlags {
84 fn from(value: ConfigAttr) -> Self {
85 match value {
86 ConfigAttr::Unrestricted => Self::all(),
87 ConfigAttr::Base => Self::empty(),
88 }
89 }
90}
91
92#[allow(clippy::module_name_repetitions)]
93#[derive(Debug, Default)]
94pub struct CompileUnit {
95 pub package: hir::Package,
96 pub ast: AstPackage,
97 pub assigner: HirAssigner,
98 pub sources: SourceMap,
99 pub errors: Vec<Error>,
100 pub dropped_names: Vec<TrackedName>,
101}
102
103#[derive(Debug, Default)]
104pub struct AstPackage {
105 pub package: ast::Package,
106 pub tys: Table,
107 pub names: Names,
108 pub locals: Locals,
109}
110
111#[derive(Debug, Default)]
112pub struct SourceMap {
113 sources: Vec<Source>,
114 entry: Option<Source>,
115}
116
117impl SourceMap {
118 pub fn new(
119 sources: impl IntoIterator<Item = (SourceName, SourceContents)>,
120 entry: Option<Arc<str>>,
121 ) -> Self {
122 let mut offset_sources = Vec::new();
123
124 let entry_source = entry.map(|contents| Source {
125 name: "<entry>".into(),
126 contents,
127 offset: 0,
128 });
129
130 let mut offset = next_offset(entry_source.as_ref());
131 for (name, contents) in sources {
132 let source = Source {
133 name,
134 contents,
135 offset,
136 };
137 offset = next_offset(Some(&source));
138 offset_sources.push(source);
139 }
140
141 Self {
142 sources: offset_sources,
143 entry: entry_source,
144 }
145 }
146
147 pub fn push(&mut self, name: SourceName, contents: SourceContents) -> u32 {
148 let offset = next_offset(self.sources.last());
149
150 self.sources.push(Source {
151 name,
152 contents,
153 offset,
154 });
155
156 offset
157 }
158
159 #[must_use]
160 pub fn find_by_offset(&self, offset: u32) -> Option<&Source> {
161 self.sources
162 .iter()
163 .rev()
164 .chain(&self.entry)
165 .find(|source| offset >= source.offset)
166 }
167
168 #[must_use]
169 pub fn find_by_name(&self, name: &str) -> Option<&Source> {
170 self.sources.iter().find(|s| s.name.as_ref() == name)
171 }
172
173 pub fn iter(&self) -> impl Iterator<Item = &Source> {
174 self.sources.iter()
175 }
176}
177
178#[derive(Clone, Debug)]
179pub struct Source {
180 pub name: SourceName,
181 pub contents: SourceContents,
182 pub offset: u32,
183}
184
185pub type SourceName = Arc<str>;
186
187pub type SourceContents = Arc<str>;
188
189#[derive(Clone, Debug, Diagnostic, Error)]
190#[diagnostic(transparent)]
191#[error(transparent)]
192pub struct Error(pub(super) ErrorKind);
193
194#[derive(Clone, Debug, Diagnostic, Error)]
195#[diagnostic(transparent)]
196pub(super) enum ErrorKind {
197 #[error("syntax error")]
198 Parse(#[from] qsc_parse::Error),
199 #[error("name error")]
200 Resolve(#[from] resolve::Error),
201 #[error("type error")]
202 Type(#[from] typeck::Error),
203 #[error(transparent)]
204 Lower(#[from] lower::Error),
205}
206
207pub struct PackageStore {
208 core: global::Table,
209 units: IndexMap<PackageId, CompileUnit>,
210 next_id: PackageId,
211}
212
213impl Debug for PackageStore {
214 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
215 write!(f, "package store with {} units", self.units.iter().count())
216 }
217}
218
219impl PackageStore {
220 #[must_use]
221 pub fn new(core: CompileUnit) -> Self {
222 let table = global::iter_package(Some(PackageId::CORE), &core.package).collect();
223 let mut units = IndexMap::new();
224 units.insert(PackageId::CORE, core);
225 Self {
226 core: table,
227 units,
228 next_id: PackageId::CORE.successor(),
229 }
230 }
231
232 #[must_use]
233 pub fn core(&self) -> &global::Table {
234 &self.core
235 }
236
237 pub fn insert(&mut self, unit: CompileUnit) -> PackageId {
238 let id = self.next_id;
239 self.next_id = id.successor();
240 self.units.insert(id, unit);
241 id
242 }
243
244 #[must_use]
245 pub fn get(&self, id: PackageId) -> Option<&CompileUnit> {
246 self.units.get(id)
247 }
248
249 #[must_use]
250 pub fn iter(&self) -> Iter {
251 Iter(self.units.iter())
252 }
253
254 /// "Opens" the package store. This inserts an empty
255 /// package into the store, which will be considered
256 /// the open package and which can be incrementally updated.
257 #[must_use]
258 pub fn open(mut self) -> OpenPackageStore {
259 let id = self.next_id;
260 self.next_id = id.successor();
261 self.units.insert(id, CompileUnit::default());
262
263 OpenPackageStore {
264 store: self,
265 open: id,
266 }
267 }
268}
269impl<'a> IntoIterator for &'a PackageStore {
270 type IntoIter = Iter<'a>;
271 type Item = (qsc_hir::hir::PackageId, &'a CompileUnit);
272 fn into_iter(self) -> Self::IntoIter {
273 self.iter()
274 }
275}
276
277/// A package store that contains one mutable `CompileUnit`.
278pub struct OpenPackageStore {
279 store: PackageStore,
280 open: PackageId,
281}
282
283impl OpenPackageStore {
284 /// Returns a reference to the underlying, immutable,
285 /// package store.
286 #[must_use]
287 pub fn package_store(&self) -> &PackageStore {
288 &self.store
289 }
290
291 /// Returns the ID of the open package.
292 #[must_use]
293 pub fn open_package_id(&self) -> PackageId {
294 self.open
295 }
296
297 /// Returns a mutable reference to the open package,
298 /// along with a reference to the core library that can be used
299 /// to perform passes.
300 #[must_use]
301 pub fn get_open_mut(&mut self) -> (&global::Table, &mut CompileUnit) {
302 let id = self.open;
303
304 (
305 &self.store.core,
306 self.store
307 .units
308 .get_mut(id)
309 .expect("open package id should exist in store"),
310 )
311 }
312
313 /// Consumes the `OpenPackageStore` and returns a `PackageStore`
314 /// along with the id of the formerly open package.
315 #[must_use]
316 pub fn into_package_store(self) -> (PackageStore, PackageId) {
317 (self.store, self.open)
318 }
319}
320
321pub struct Iter<'a>(index_map::Iter<'a, PackageId, CompileUnit>);
322
323impl<'a> Iterator for Iter<'a> {
324 type Item = (PackageId, &'a CompileUnit);
325
326 fn next(&mut self) -> Option<Self::Item> {
327 self.0.next()
328 }
329}
330
331pub(super) struct Offsetter(pub(super) u32);
332
333impl MutVisitor for Offsetter {
334 fn visit_span(&mut self, span: &mut Span) {
335 span.lo += self.0;
336 span.hi += self.0;
337 }
338}
339
340pub fn compile(
341 store: &PackageStore,
342 dependencies: &[PackageId],
343 sources: SourceMap,
344 capabilities: RuntimeCapabilityFlags,
345) -> CompileUnit {
346 let (mut ast_package, parse_errors) = parse_all(&sources);
347
348 let mut cond_compile = preprocess::Conditional::new(capabilities);
349 cond_compile.visit_package(&mut ast_package);
350 let dropped_names = cond_compile.into_names();
351
352 let mut ast_assigner = AstAssigner::new();
353 ast_assigner.visit_package(&mut ast_package);
354 AstValidator::default().visit_package(&ast_package);
355 let mut hir_assigner = HirAssigner::new();
356 let (names, locals, name_errors) = resolve_all(
357 store,
358 dependencies,
359 &mut hir_assigner,
360 &ast_package,
361 dropped_names.clone(),
362 );
363 let (tys, ty_errors) = typeck_all(store, dependencies, &ast_package, &names);
364 let mut lowerer = Lowerer::new();
365 let package = lowerer
366 .with(&mut hir_assigner, &names, &tys)
367 .lower_package(&ast_package);
368 HirValidator::default().visit_package(&package);
369 let lower_errors = lowerer.drain_errors();
370
371 let errors = parse_errors
372 .into_iter()
373 .map(Into::into)
374 .chain(name_errors.into_iter().map(Into::into))
375 .chain(ty_errors.into_iter().map(Into::into))
376 .chain(lower_errors.into_iter().map(Into::into))
377 .map(Error)
378 .collect();
379
380 CompileUnit {
381 package,
382 ast: AstPackage {
383 package: ast_package,
384 tys,
385 names,
386 locals,
387 },
388 assigner: hir_assigner,
389 sources,
390 errors,
391 dropped_names,
392 }
393}
394
395/// Compiles the core library.
396///
397/// # Panics
398///
399/// Panics if the core library does not compile without errors.
400#[must_use]
401pub fn core() -> CompileUnit {
402 let store = PackageStore {
403 core: global::Table::default(),
404 units: IndexMap::new(),
405 next_id: PackageId::CORE,
406 };
407
408 let sources = SourceMap::new(
409 [
410 (
411 "core/core.qs".into(),
412 include_str!("../../../library/core/core.qs").into(),
413 ),
414 (
415 "core/qir.qs".into(),
416 include_str!("../../../library/core/qir.qs").into(),
417 ),
418 ],
419 None,
420 );
421
422 let mut unit = compile(&store, &[], sources, RuntimeCapabilityFlags::empty());
423 assert_no_errors(&unit.sources, &mut unit.errors);
424 unit
425}
426
427/// Compiles the standard library.
428///
429/// # Panics
430///
431/// Panics if the standard library does not compile without errors.
432#[must_use]
433pub fn std(store: &PackageStore, capabilities: RuntimeCapabilityFlags) -> CompileUnit {
434 let sources = SourceMap::new(
435 [
436 (
437 "arrays.qs".into(),
438 include_str!("../../../library/std/arrays.qs").into(),
439 ),
440 (
441 "canon.qs".into(),
442 include_str!("../../../library/std/canon.qs").into(),
443 ),
444 (
445 "convert.qs".into(),
446 include_str!("../../../library/std/convert.qs").into(),
447 ),
448 (
449 "core.qs".into(),
450 include_str!("../../../library/std/core.qs").into(),
451 ),
452 (
453 "diagnostics.qs".into(),
454 include_str!("../../../library/std/diagnostics.qs").into(),
455 ),
456 (
457 "internal.qs".into(),
458 include_str!("../../../library/std/internal.qs").into(),
459 ),
460 (
461 "intrinsic.qs".into(),
462 include_str!("../../../library/std/intrinsic.qs").into(),
463 ),
464 (
465 "math.qs".into(),
466 include_str!("../../../library/std/math.qs").into(),
467 ),
468 (
469 "measurement.qs".into(),
470 include_str!("../../../library/std/measurement.qs").into(),
471 ),
472 (
473 "qir.qs".into(),
474 include_str!("../../../library/std/qir.qs").into(),
475 ),
476 (
477 "random.qs".into(),
478 include_str!("../../../library/std/random.qs").into(),
479 ),
480 (
481 "unstable_arithmetic.qs".into(),
482 include_str!("../../../library/std/unstable_arithmetic.qs").into(),
483 ),
484 (
485 "unstable_arithmetic_internal.qs".into(),
486 include_str!("../../../library/std/unstable_arithmetic_internal.qs").into(),
487 ),
488 (
489 "unstable_table_lookup.qs".into(),
490 include_str!("../../../library/std/unstable_table_lookup.qs").into(),
491 ),
492 (
493 "re.qs".into(),
494 include_str!("../../../library/std/re.qs").into(),
495 ),
496 ],
497 None,
498 );
499
500 let mut unit = compile(store, &[PackageId::CORE], sources, capabilities);
501 assert_no_errors(&unit.sources, &mut unit.errors);
502 unit
503}
504
505fn parse_all(sources: &SourceMap) -> (ast::Package, Vec<qsc_parse::Error>) {
506 let mut namespaces = Vec::new();
507 let mut errors = Vec::new();
508 for source in &sources.sources {
509 let (source_namespaces, source_errors) = qsc_parse::namespaces(&source.contents);
510 for mut namespace in source_namespaces {
511 Offsetter(source.offset).visit_namespace(&mut namespace);
512 namespaces.push(TopLevelNode::Namespace(namespace));
513 }
514
515 append_parse_errors(&mut errors, source.offset, source_errors);
516 }
517
518 let entry = sources
519 .entry
520 .as_ref()
521 .filter(|source| !source.contents.is_empty())
522 .map(|source| {
523 let (mut entry, entry_errors) = qsc_parse::expr(&source.contents);
524 Offsetter(source.offset).visit_expr(&mut entry);
525 append_parse_errors(&mut errors, source.offset, entry_errors);
526 entry
527 });
528
529 let package = ast::Package {
530 id: ast::NodeId::default(),
531 nodes: namespaces.into_boxed_slice(),
532 entry,
533 };
534
535 (package, errors)
536}
537
538fn resolve_all(
539 store: &PackageStore,
540 dependencies: &[PackageId],
541 assigner: &mut HirAssigner,
542 package: &ast::Package,
543 mut dropped_names: Vec<TrackedName>,
544) -> (Names, Locals, Vec<resolve::Error>) {
545 let mut globals = resolve::GlobalTable::new();
546 if let Some(unit) = store.get(PackageId::CORE) {
547 globals.add_external_package(PackageId::CORE, &unit.package);
548 dropped_names.extend(unit.dropped_names.iter().cloned());
549 }
550
551 for &id in dependencies {
552 let unit = store
553 .get(id)
554 .expect("dependency should be in package store before compilation");
555 globals.add_external_package(id, &unit.package);
556 dropped_names.extend(unit.dropped_names.iter().cloned());
557 }
558
559 let mut errors = globals.add_local_package(assigner, package);
560 let mut resolver = Resolver::new(globals, dropped_names);
561 resolver.with(assigner).visit_package(package);
562 let (names, locals, mut resolver_errors) = resolver.into_result();
563 errors.append(&mut resolver_errors);
564 (names, locals, errors)
565}
566
567fn typeck_all(
568 store: &PackageStore,
569 dependencies: &[PackageId],
570 package: &ast::Package,
571 names: &Names,
572) -> (typeck::Table, Vec<typeck::Error>) {
573 let mut globals = typeck::GlobalTable::new();
574 if let Some(unit) = store.get(PackageId::CORE) {
575 globals.add_external_package(PackageId::CORE, &unit.package);
576 }
577
578 for &id in dependencies {
579 let unit = store
580 .get(id)
581 .expect("dependency should be added to package store before compilation");
582 globals.add_external_package(id, &unit.package);
583 }
584
585 let mut checker = Checker::new(globals);
586 checker.check_package(names, package);
587 checker.into_table()
588}
589
590fn append_parse_errors(
591 errors: &mut Vec<qsc_parse::Error>,
592 offset: u32,
593 other: Vec<qsc_parse::Error>,
594) {
595 for error in other {
596 errors.push(error.with_offset(offset));
597 }
598}
599
600fn next_offset(last_source: Option<&Source>) -> u32 {
601 // Leave a gap of 1 between each source so that offsets at EOF
602 // get mapped to the correct source
603 last_source.map_or(0, |s| {
604 1 + s.offset + u32::try_from(s.contents.len()).expect("contents length should fit into u32")
605 })
606}
607
608fn assert_no_errors(sources: &SourceMap, errors: &mut Vec<Error>) {
609 if !errors.is_empty() {
610 for error in errors.drain(..) {
611 eprintln!("{:?}", Report::new(WithSource::from_map(sources, error)));
612 }
613
614 panic!("could not compile package");
615 }
616}
617