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_frontend/src

source/compiler/qsc_frontend/src/compile.rs

676lines · modecode

RawDownload
Latest commit unavailable.
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};
15
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 language_features::LanguageFeatures,
28 span::Span,
29 target::TargetCapabilityFlags,
30};
31use qsc_hir::{
32 assigner::Assigner as HirAssigner,
33 global::{self},
34 hir::{self, PackageId},
35 validate::Validator as HirValidator,
36 visit::Visitor as _,
37};
38use std::{fmt::Debug, sync::Arc};
39use thiserror::Error;
40
41#[derive(Debug, Default)]
42pub struct CompileUnit {
43 pub package: hir::Package,
44 pub ast: AstPackage,
45 pub assigner: HirAssigner,
46 pub sources: SourceMap,
47 pub errors: Vec<Error>,
48 pub dropped_names: Vec<TrackedName>,
49}
50
51impl CompileUnit {
52 pub fn expose(&mut self) {
53 for (_item_id, item) in self.package.items.iter_mut() {
54 item.visibility = hir::Visibility::Public;
55 }
56 }
57}
58
59#[derive(Debug, Default)]
60pub struct AstPackage {
61 pub package: ast::Package,
62 pub tys: Table,
63 pub names: Names,
64 pub locals: Locals,
65}
66
67#[derive(Clone, Debug, Default)]
68pub struct SourceMap {
69 sources: Vec<Source>,
70 /// The common prefix of the sources
71 /// e.g. if the sources all start with `/Users/microsoft/code/qsharp/src`, then this value is
72 /// `/Users/microsoft/code/qsharp/src`.
73 common_prefix: Option<Arc<str>>,
74 entry: Option<Source>,
75}
76
77impl SourceMap {
78 pub fn new(
79 sources: impl IntoIterator<Item = (SourceName, SourceContents)>,
80 entry: Option<Arc<str>>,
81 ) -> Self {
82 let mut offset_sources = Vec::new();
83
84 let entry_source = entry.map(|contents| Source {
85 name: "<entry>".into(),
86 contents,
87 offset: 0,
88 });
89
90 let mut offset = next_offset(entry_source.as_ref());
91 for (name, contents) in sources {
92 let source = Source {
93 name,
94 contents,
95 offset,
96 };
97 offset = next_offset(Some(&source));
98 offset_sources.push(source);
99 }
100
101 // Each source has a name, which is a string. The project root dir is calculated as the
102 // common prefix of all of the sources.
103 // Calculate the common prefix.
104 let common_prefix: String = longest_common_prefix(
105 &offset_sources
106 .iter()
107 .map(|source| source.name.as_ref())
108 .collect::<Vec<_>>(),
109 )
110 .to_string();
111
112 let common_prefix: Arc<str> = Arc::from(common_prefix);
113
114 Self {
115 sources: offset_sources,
116 common_prefix: if common_prefix.is_empty() {
117 None
118 } else {
119 Some(common_prefix)
120 },
121 entry: entry_source,
122 }
123 }
124
125 pub fn push(&mut self, name: SourceName, contents: SourceContents) -> u32 {
126 let offset = next_offset(self.sources.last());
127
128 self.sources.push(Source {
129 name,
130 contents,
131 offset,
132 });
133
134 offset
135 }
136
137 #[must_use]
138 pub fn find_by_offset(&self, offset: u32) -> Option<&Source> {
139 self.sources
140 .iter()
141 .rev()
142 .chain(&self.entry)
143 .find(|source| offset >= source.offset)
144 }
145
146 #[must_use]
147 pub fn find_by_name(&self, name: &str) -> Option<&Source> {
148 self.sources.iter().find(|s| s.name.as_ref() == name)
149 }
150
151 pub fn iter(&self) -> impl Iterator<Item = &Source> {
152 self.sources.iter()
153 }
154
155 /// Returns the sources as an iter, but with the project root directory subtracted
156 /// from the individual source names.
157 pub(crate) fn relative_sources(&self) -> impl Iterator<Item = Source> + '_ {
158 self.sources.iter().map(move |source| {
159 let name = source.name.as_ref();
160 let relative_name = self.relative_name(name);
161
162 Source {
163 name: relative_name.into(),
164 contents: source.contents.clone(),
165 offset: source.offset,
166 }
167 })
168 }
169
170 #[must_use]
171 pub fn relative_name<'a>(&'a self, name: &'a str) -> &'a str {
172 if let Some(common_prefix) = &self.common_prefix {
173 name.strip_prefix(common_prefix.as_ref()).unwrap_or(name)
174 } else {
175 name
176 }
177 }
178}
179
180#[derive(Clone, Debug)]
181pub struct Source {
182 pub name: SourceName,
183 pub contents: SourceContents,
184 pub offset: u32,
185}
186
187pub type SourceName = Arc<str>;
188
189pub type SourceContents = Arc<str>;
190
191// the arc<str> is only `None` for the legacy stdlib, core, and an interpreter special case
192pub type Dependencies = [(PackageId, Option<Arc<str>>)];
193
194#[derive(Clone, Debug, Diagnostic, Error)]
195#[diagnostic(transparent)]
196#[error(transparent)]
197pub struct Error(pub(super) ErrorKind);
198
199#[derive(Clone, Debug, Diagnostic, Error)]
200#[diagnostic(transparent)]
201pub(super) enum ErrorKind {
202 #[error("syntax error")]
203 Parse(#[from] qsc_parse::Error),
204 #[error("name error")]
205 Resolve(#[from] resolve::Error),
206 #[error("type error")]
207 Type(#[from] typeck::Error),
208 #[error(transparent)]
209 Lower(#[from] lower::Error),
210}
211
212pub struct PackageStore {
213 core: global::Table,
214 units: IndexMap<PackageId, CompileUnit>,
215 next_id: PackageId,
216}
217
218impl Debug for PackageStore {
219 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
220 write!(f, "package store with {} units", self.units.iter().count())
221 }
222}
223
224impl PackageStore {
225 #[must_use]
226 pub fn new(core: CompileUnit) -> Self {
227 let table = global::iter_package(Some(PackageId::CORE), &core.package).collect();
228 let mut units = IndexMap::new();
229 units.insert(PackageId::CORE, core);
230 Self {
231 core: table,
232 units,
233 next_id: PackageId::CORE.successor(),
234 }
235 }
236
237 #[must_use]
238 pub fn core(&self) -> &global::Table {
239 &self.core
240 }
241
242 pub fn insert(&mut self, unit: CompileUnit) -> PackageId {
243 let id = self.next_id;
244 self.next_id = id.successor();
245 self.units.insert(id, unit);
246 id
247 }
248
249 #[must_use]
250 pub fn get(&self, id: PackageId) -> Option<&CompileUnit> {
251 self.units.get(id)
252 }
253
254 #[must_use]
255 pub fn iter(&self) -> Iter {
256 Iter(self.units.iter())
257 }
258
259 /// "Opens" the package store. This inserts an empty
260 /// package into the store, which will be considered
261 /// the open package and which can be incrementally updated.
262 #[must_use]
263 pub fn open(mut self) -> OpenPackageStore {
264 let id = self.next_id;
265 self.next_id = id.successor();
266 self.units.insert(id, CompileUnit::default());
267
268 OpenPackageStore {
269 store: self,
270 open: id,
271 }
272 }
273
274 #[must_use]
275 pub fn is_empty(&self) -> bool {
276 self.units.is_empty()
277 }
278}
279
280impl<'a> IntoIterator for &'a PackageStore {
281 type IntoIter = Iter<'a>;
282 type Item = (qsc_hir::hir::PackageId, &'a CompileUnit);
283 fn into_iter(self) -> Self::IntoIter {
284 self.iter()
285 }
286}
287
288/// A package store that contains one mutable `CompileUnit`.
289pub struct OpenPackageStore {
290 store: PackageStore,
291 open: PackageId,
292}
293
294impl OpenPackageStore {
295 /// Returns a reference to the underlying, immutable,
296 /// package store.
297 #[must_use]
298 pub fn package_store(&self) -> &PackageStore {
299 &self.store
300 }
301
302 /// Returns the ID of the open package.
303 #[must_use]
304 pub fn open_package_id(&self) -> PackageId {
305 self.open
306 }
307
308 /// Returns a mutable reference to the open package,
309 /// along with a reference to the core library that can be used
310 /// to perform passes.
311 #[must_use]
312 pub fn get_open_mut(&mut self) -> (&global::Table, &mut CompileUnit) {
313 let id = self.open;
314
315 (
316 &self.store.core,
317 self.store
318 .units
319 .get_mut(id)
320 .expect("open package id should exist in store"),
321 )
322 }
323
324 /// Consumes the `OpenPackageStore` and returns a `PackageStore`
325 /// along with the id of the formerly open package.
326 #[must_use]
327 pub fn into_package_store(self) -> (PackageStore, PackageId) {
328 (self.store, self.open)
329 }
330}
331
332pub struct Iter<'a>(index_map::Iter<'a, PackageId, CompileUnit>);
333
334impl<'a> Iterator for Iter<'a> {
335 type Item = (PackageId, &'a CompileUnit);
336
337 fn next(&mut self) -> Option<Self::Item> {
338 self.0.next()
339 }
340}
341
342impl DoubleEndedIterator for Iter<'_> {
343 fn next_back(&mut self) -> Option<Self::Item> {
344 self.0.next_back()
345 }
346}
347
348pub(super) struct Offsetter(pub(super) u32);
349
350impl MutVisitor for Offsetter {
351 fn visit_span(&mut self, span: &mut Span) {
352 span.lo += self.0;
353 span.hi += self.0;
354 }
355}
356
357#[must_use]
358pub fn compile(
359 store: &PackageStore,
360 dependencies: &Dependencies,
361 sources: SourceMap,
362 capabilities: TargetCapabilityFlags,
363 language_features: LanguageFeatures,
364) -> CompileUnit {
365 let (ast_package, parse_errors) = parse_all(&sources, language_features);
366
367 compile_ast(
368 store,
369 dependencies,
370 ast_package,
371 sources,
372 capabilities,
373 parse_errors,
374 )
375}
376
377#[allow(clippy::module_name_repetitions)]
378pub fn compile_ast(
379 store: &PackageStore,
380 dependencies: &Dependencies,
381 mut ast_package: ast::Package,
382 sources: SourceMap,
383 capabilities: TargetCapabilityFlags,
384 parse_errors: Vec<qsc_parse::Error>,
385) -> CompileUnit {
386 let mut cond_compile = preprocess::Conditional::new(capabilities);
387 cond_compile.visit_package(&mut ast_package);
388 let dropped_names = cond_compile.into_names();
389
390 let mut remove_spans = preprocess::RemoveCircuitSpans::new(&sources);
391 remove_spans.visit_package(&mut ast_package);
392
393 let mut ast_assigner = AstAssigner::new();
394 ast_assigner.visit_package(&mut ast_package);
395 AstValidator::default().visit_package(&ast_package);
396 let mut hir_assigner = HirAssigner::new();
397 let ResolveResult {
398 names,
399 locals,
400 errors: name_errors,
401 namespaces,
402 } = resolve_all(
403 store,
404 dependencies,
405 &mut hir_assigner,
406 &ast_package,
407 dropped_names.clone(),
408 );
409 let (tys, ty_errors) = typeck_all(store, dependencies, &ast_package, &names);
410 let mut lowerer = Lowerer::new();
411 let package = lowerer
412 .with(&mut hir_assigner, &names, &tys)
413 .lower_package(&ast_package, namespaces);
414 HirValidator::default().visit_package(&package);
415 let lower_errors = lowerer.drain_errors();
416
417 let errors = parse_errors
418 .into_iter()
419 .map(Into::into)
420 .chain(name_errors.into_iter().map(Into::into))
421 .chain(ty_errors.into_iter().map(Into::into))
422 .chain(lower_errors.into_iter().map(Into::into))
423 .map(Error)
424 .collect();
425
426 CompileUnit {
427 package,
428 ast: AstPackage {
429 package: ast_package,
430 tys,
431 names,
432 locals,
433 },
434 assigner: hir_assigner,
435 sources,
436 errors,
437 dropped_names,
438 }
439}
440
441/// Compiles the core library.
442///
443/// # Panics
444///
445/// Panics if the core library does not compile without errors.
446#[must_use]
447pub fn core() -> CompileUnit {
448 let store = PackageStore {
449 core: global::Table::default(),
450 units: IndexMap::new(),
451 next_id: PackageId::CORE,
452 };
453
454 let core: Vec<(SourceName, SourceContents)> = library::CORE_LIB
455 .iter()
456 .map(|(name, contents)| ((*name).into(), (*contents).into()))
457 .collect();
458 let sources = SourceMap::new(core, None);
459
460 let mut unit = compile(
461 &store,
462 &[],
463 sources,
464 TargetCapabilityFlags::empty(),
465 LanguageFeatures::default(),
466 );
467 assert_no_errors(&unit.sources, &mut unit.errors);
468 unit
469}
470
471/// Compiles the standard library.
472///
473/// # Panics
474///
475/// Panics if the standard library does not compile without errors.
476#[must_use]
477pub fn std(store: &PackageStore, capabilities: TargetCapabilityFlags) -> CompileUnit {
478 let std: Vec<(SourceName, SourceContents)> = library::STD_LIB
479 .iter()
480 .map(|(name, contents)| ((*name).into(), (*contents).into()))
481 .collect();
482 let sources = SourceMap::new(std, None);
483
484 let mut unit = compile(
485 store,
486 &[(PackageId::CORE, None)],
487 sources,
488 capabilities,
489 LanguageFeatures::default(),
490 );
491 assert_no_errors(&unit.sources, &mut unit.errors);
492 unit
493}
494
495#[must_use]
496pub fn parse_all(
497 sources: &SourceMap,
498 features: LanguageFeatures,
499) -> (ast::Package, Vec<qsc_parse::Error>) {
500 let mut namespaces = Vec::new();
501 let mut errors = Vec::new();
502 for source in sources.relative_sources() {
503 let (source_namespaces, source_errors) =
504 qsc_parse::namespaces(&source.contents, Some(&source.name), features);
505 for mut namespace in source_namespaces {
506 Offsetter(source.offset).visit_namespace(&mut namespace);
507 namespaces.push(TopLevelNode::Namespace(namespace));
508 }
509
510 append_parse_errors(&mut errors, source.offset, source_errors);
511 }
512
513 let entry = sources
514 .entry
515 .as_ref()
516 .filter(|source| !source.contents.is_empty())
517 .map(|source| {
518 let (mut entry, entry_errors) = qsc_parse::expr(&source.contents, features);
519 Offsetter(source.offset).visit_expr(&mut entry);
520 append_parse_errors(&mut errors, source.offset, entry_errors);
521 entry
522 });
523
524 let package = ast::Package {
525 id: ast::NodeId::default(),
526 nodes: namespaces.into_boxed_slice(),
527 entry,
528 };
529
530 (package, errors)
531}
532
533pub(crate) struct ResolveResult {
534 pub names: Names,
535 pub locals: Locals,
536 pub namespaces: qsc_data_structures::namespaces::NamespaceTreeRoot,
537 pub errors: Vec<resolve::Error>,
538}
539
540fn resolve_all(
541 store: &PackageStore,
542 dependencies: &Dependencies,
543 assigner: &mut HirAssigner,
544 package: &ast::Package,
545 mut dropped_names: Vec<TrackedName>,
546) -> ResolveResult {
547 let mut globals = resolve::GlobalTable::new();
548 let mut errors = Vec::new();
549 if let Some(unit) = store.get(PackageId::CORE) {
550 if let Err(errs) = globals.add_external_package(PackageId::CORE, &unit.package, store, None)
551 {
552 errors.extend(errs);
553 }
554 dropped_names.extend(unit.dropped_names.iter().cloned());
555 }
556
557 for (id, alias) in dependencies {
558 let unit = store
559 .get(*id)
560 .expect("dependency should be in package store before compilation");
561 if let Err(errs) = globals.add_external_package(*id, &unit.package, store, alias.as_deref())
562 {
563 errors.extend(errs);
564 }
565 dropped_names.extend(unit.dropped_names.iter().cloned());
566 }
567
568 // bind all symbols in `add_local_package`
569 errors.extend(globals.add_local_package(assigner, package));
570 let mut resolver = Resolver::new(globals, dropped_names);
571
572 // bind all exported symbols in a follow-on step
573 resolver.bind_and_resolve_imports_and_exports(package);
574
575 // resolve all symbols
576 resolver.with(assigner).visit_package(package);
577 let (names, locals, mut resolver_errors, namespaces) = resolver.into_result();
578 errors.append(&mut resolver_errors);
579
580 ResolveResult {
581 names,
582 locals,
583 namespaces,
584 errors,
585 }
586}
587
588fn typeck_all(
589 store: &PackageStore,
590 dependencies: &Dependencies,
591 package: &ast::Package,
592 names: &Names,
593) -> (typeck::Table, Vec<typeck::Error>) {
594 let mut globals = typeck::GlobalTable::new();
595 if let Some(unit) = store.get(PackageId::CORE) {
596 globals.add_external_package(PackageId::CORE, &unit.package, store);
597 }
598
599 for (id, _alias) in dependencies {
600 let unit = store
601 .get(*id)
602 .expect("dependency should be added to package store before compilation");
603 // we can ignore the dependency alias here, because the
604 // typechecker doesn't do any name resolution -- it only operates on item ids.
605 // because of this, the typechecker doesn't actually need to care about visibility
606 // or the names of items at all.
607 globals.add_external_package(*id, &unit.package, store);
608 }
609
610 let mut checker = Checker::new(globals);
611 checker.check_package(names, package);
612 checker.into_table()
613}
614
615fn append_parse_errors(
616 errors: &mut Vec<qsc_parse::Error>,
617 offset: u32,
618 other: Vec<qsc_parse::Error>,
619) {
620 for error in other {
621 errors.push(error.with_offset(offset));
622 }
623}
624
625fn next_offset(last_source: Option<&Source>) -> u32 {
626 // Leave a gap of 1 between each source so that offsets at EOF
627 // get mapped to the correct source
628 last_source.map_or(0, |s| {
629 1 + s.offset + u32::try_from(s.contents.len()).expect("contents length should fit into u32")
630 })
631}
632
633fn assert_no_errors(sources: &SourceMap, errors: &mut Vec<Error>) {
634 if !errors.is_empty() {
635 for error in errors.drain(..) {
636 eprintln!("{:?}", Report::new(WithSource::from_map(sources, error)));
637 }
638
639 panic!("could not compile package");
640 }
641}
642
643#[must_use]
644pub fn longest_common_prefix<'a>(strs: &'a [&'a str]) -> &'a str {
645 if strs.len() == 1 {
646 return truncate_to_path_separator(strs[0]);
647 }
648
649 let Some(common_prefix_so_far) = strs.first() else {
650 return "";
651 };
652
653 for (i, character) in common_prefix_so_far.char_indices() {
654 for string in strs {
655 if string.chars().nth(i) != Some(character) {
656 let prefix = &common_prefix_so_far[0..i];
657 // Find the last occurrence of the path separator in the prefix
658 return truncate_to_path_separator(prefix);
659 }
660 }
661 }
662 common_prefix_so_far
663}
664
665fn truncate_to_path_separator(prefix: &str) -> &str {
666 let last_separator_index = prefix
667 .rfind('/')
668 .or_else(|| prefix.rfind('\\'))
669 .or_else(|| prefix.rfind(':'));
670 if let Some(last_separator_index) = last_separator_index {
671 // Return the prefix up to and including the last path separator
672 return &prefix[0..=last_separator_index];
673 }
674 // If there's no path separator in the prefix, return an empty string
675 ""
676}
677