GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
92f542e70a6ca4eadffcee9e2e42c59c8f02df49

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

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