GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/pythontelem

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_frontend/src

compiler/qsc_frontend/src/compile.rs

672lines · 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 ast_assigner = AstAssigner::new();
391 ast_assigner.visit_package(&mut ast_package);
392 AstValidator::default().visit_package(&ast_package);
393 let mut hir_assigner = HirAssigner::new();
394 let ResolveResult {
395 names,
396 locals,
397 errors: name_errors,
398 namespaces,
399 } = resolve_all(
400 store,
401 dependencies,
402 &mut hir_assigner,
403 &ast_package,
404 dropped_names.clone(),
405 );
406 let (tys, ty_errors) = typeck_all(store, dependencies, &ast_package, &names);
407 let mut lowerer = Lowerer::new();
408 let package = lowerer
409 .with(&mut hir_assigner, &names, &tys)
410 .lower_package(&ast_package, namespaces);
411 HirValidator::default().visit_package(&package);
412 let lower_errors = lowerer.drain_errors();
413
414 let errors = parse_errors
415 .into_iter()
416 .map(Into::into)
417 .chain(name_errors.into_iter().map(Into::into))
418 .chain(ty_errors.into_iter().map(Into::into))
419 .chain(lower_errors.into_iter().map(Into::into))
420 .map(Error)
421 .collect();
422
423 CompileUnit {
424 package,
425 ast: AstPackage {
426 package: ast_package,
427 tys,
428 names,
429 locals,
430 },
431 assigner: hir_assigner,
432 sources,
433 errors,
434 dropped_names,
435 }
436}
437
438/// Compiles the core library.
439///
440/// # Panics
441///
442/// Panics if the core library does not compile without errors.
443#[must_use]
444pub fn core() -> CompileUnit {
445 let store = PackageStore {
446 core: global::Table::default(),
447 units: IndexMap::new(),
448 next_id: PackageId::CORE,
449 };
450
451 let core: Vec<(SourceName, SourceContents)> = library::CORE_LIB
452 .iter()
453 .map(|(name, contents)| ((*name).into(), (*contents).into()))
454 .collect();
455 let sources = SourceMap::new(core, None);
456
457 let mut unit = compile(
458 &store,
459 &[],
460 sources,
461 TargetCapabilityFlags::empty(),
462 LanguageFeatures::default(),
463 );
464 assert_no_errors(&unit.sources, &mut unit.errors);
465 unit
466}
467
468/// Compiles the standard library.
469///
470/// # Panics
471///
472/// Panics if the standard library does not compile without errors.
473#[must_use]
474pub fn std(store: &PackageStore, capabilities: TargetCapabilityFlags) -> CompileUnit {
475 let std: Vec<(SourceName, SourceContents)> = library::STD_LIB
476 .iter()
477 .map(|(name, contents)| ((*name).into(), (*contents).into()))
478 .collect();
479 let sources = SourceMap::new(std, None);
480
481 let mut unit = compile(
482 store,
483 &[(PackageId::CORE, None)],
484 sources,
485 capabilities,
486 LanguageFeatures::default(),
487 );
488 assert_no_errors(&unit.sources, &mut unit.errors);
489 unit
490}
491
492fn parse_all(
493 sources: &SourceMap,
494 features: LanguageFeatures,
495) -> (ast::Package, Vec<qsc_parse::Error>) {
496 let mut namespaces = Vec::new();
497 let mut errors = Vec::new();
498 for source in sources.relative_sources() {
499 let (source_namespaces, source_errors) =
500 qsc_parse::namespaces(&source.contents, Some(&source.name), features);
501 for mut namespace in source_namespaces {
502 Offsetter(source.offset).visit_namespace(&mut namespace);
503 namespaces.push(TopLevelNode::Namespace(namespace));
504 }
505
506 append_parse_errors(&mut errors, source.offset, source_errors);
507 }
508
509 let entry = sources
510 .entry
511 .as_ref()
512 .filter(|source| !source.contents.is_empty())
513 .map(|source| {
514 let (mut entry, entry_errors) = qsc_parse::expr(&source.contents, features);
515 Offsetter(source.offset).visit_expr(&mut entry);
516 append_parse_errors(&mut errors, source.offset, entry_errors);
517 entry
518 });
519
520 let package = ast::Package {
521 id: ast::NodeId::default(),
522 nodes: namespaces.into_boxed_slice(),
523 entry,
524 };
525
526 (package, errors)
527}
528
529pub(crate) struct ResolveResult {
530 pub names: Names,
531 pub locals: Locals,
532 pub namespaces: qsc_data_structures::namespaces::NamespaceTreeRoot,
533 pub errors: Vec<resolve::Error>,
534}
535
536fn resolve_all(
537 store: &PackageStore,
538 dependencies: &Dependencies,
539 assigner: &mut HirAssigner,
540 package: &ast::Package,
541 mut dropped_names: Vec<TrackedName>,
542) -> ResolveResult {
543 let mut globals = resolve::GlobalTable::new();
544 let mut errors = Vec::new();
545 if let Some(unit) = store.get(PackageId::CORE) {
546 if let Err(errs) =
547 globals.add_external_package(PackageId::CORE, &unit.package, store, &None)
548 {
549 errors.extend(errs);
550 }
551 dropped_names.extend(unit.dropped_names.iter().cloned());
552 }
553
554 for (ref id, alias) in dependencies {
555 let unit = store
556 .get(*id)
557 .expect("dependency should be in package store before compilation");
558 if let Err(errs) = globals.add_external_package(*id, &unit.package, store, alias) {
559 errors.extend(errs);
560 };
561 dropped_names.extend(unit.dropped_names.iter().cloned());
562 }
563
564 // bind all symbols in `add_local_package`
565 errors.extend(globals.add_local_package(assigner, package));
566 let mut resolver = Resolver::new(globals, dropped_names);
567
568 // bind all exported symbols in a follow-on step
569 resolver.bind_and_resolve_imports_and_exports(package);
570
571 // resolve all symbols
572 resolver.with(assigner).visit_package(package);
573 let (names, locals, mut resolver_errors, namespaces) = resolver.into_result();
574 errors.append(&mut resolver_errors);
575
576 ResolveResult {
577 names,
578 locals,
579 namespaces,
580 errors,
581 }
582}
583
584fn typeck_all(
585 store: &PackageStore,
586 dependencies: &Dependencies,
587 package: &ast::Package,
588 names: &Names,
589) -> (typeck::Table, Vec<typeck::Error>) {
590 let mut globals = typeck::GlobalTable::new();
591 if let Some(unit) = store.get(PackageId::CORE) {
592 globals.add_external_package(PackageId::CORE, &unit.package, store);
593 }
594
595 for (id, _alias) in dependencies {
596 let unit = store
597 .get(*id)
598 .expect("dependency should be added to package store before compilation");
599 // we can ignore the dependency alias here, because the
600 // typechecker doesn't do any name resolution -- it only operates on item ids.
601 // because of this, the typechecker doesn't actually need to care about visibility
602 // or the names of items at all.
603 globals.add_external_package(*id, &unit.package, store);
604 }
605
606 let mut checker = Checker::new(globals);
607 checker.check_package(names, package);
608 checker.into_table()
609}
610
611fn append_parse_errors(
612 errors: &mut Vec<qsc_parse::Error>,
613 offset: u32,
614 other: Vec<qsc_parse::Error>,
615) {
616 for error in other {
617 errors.push(error.with_offset(offset));
618 }
619}
620
621fn next_offset(last_source: Option<&Source>) -> u32 {
622 // Leave a gap of 1 between each source so that offsets at EOF
623 // get mapped to the correct source
624 last_source.map_or(0, |s| {
625 1 + s.offset + u32::try_from(s.contents.len()).expect("contents length should fit into u32")
626 })
627}
628
629fn assert_no_errors(sources: &SourceMap, errors: &mut Vec<Error>) {
630 if !errors.is_empty() {
631 for error in errors.drain(..) {
632 eprintln!("{:?}", Report::new(WithSource::from_map(sources, error)));
633 }
634
635 panic!("could not compile package");
636 }
637}
638
639#[must_use]
640pub fn longest_common_prefix<'a>(strs: &'a [&'a str]) -> &'a str {
641 if strs.len() == 1 {
642 return truncate_to_path_separator(strs[0]);
643 }
644
645 let Some(common_prefix_so_far) = strs.first() else {
646 return "";
647 };
648
649 for (i, character) in common_prefix_so_far.chars().enumerate() {
650 for string in strs {
651 if string.chars().nth(i) != Some(character) {
652 let prefix = &common_prefix_so_far[0..i];
653 // Find the last occurrence of the path separator in the prefix
654 return truncate_to_path_separator(prefix);
655 }
656 }
657 }
658 common_prefix_so_far
659}
660
661fn truncate_to_path_separator(prefix: &str) -> &str {
662 let last_separator_index = prefix
663 .rfind('/')
664 .or_else(|| prefix.rfind('\\'))
665 .or_else(|| prefix.rfind(':'));
666 if let Some(last_separator_index) = last_separator_index {
667 // Return the prefix up to and including the last path separator
668 return &prefix[0..=last_separator_index];
669 }
670 // If there's no path separator in the prefix, return an empty string
671 ""
672}
673