GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billti/copilot

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

660lines · 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(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 = if let Some(common_prefix) = &self.common_prefix {
161 name.strip_prefix(common_prefix.as_ref()).unwrap_or(name)
162 } else {
163 name
164 };
165
166 Source {
167 name: relative_name.into(),
168 contents: source.contents.clone(),
169 offset: source.offset,
170 }
171 })
172 }
173}
174
175#[derive(Clone, Debug)]
176pub struct Source {
177 pub name: SourceName,
178 pub contents: SourceContents,
179 pub offset: u32,
180}
181
182pub type SourceName = Arc<str>;
183
184pub type SourceContents = Arc<str>;
185
186// the arc<str> is only `None` for the legacy stdlib, core, and an interpreter special case
187pub type Dependencies = [(PackageId, Option<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
269 #[must_use]
270 pub fn is_empty(&self) -> bool {
271 self.units.is_empty()
272 }
273}
274
275impl<'a> IntoIterator for &'a PackageStore {
276 type IntoIter = Iter<'a>;
277 type Item = (qsc_hir::hir::PackageId, &'a CompileUnit);
278 fn into_iter(self) -> Self::IntoIter {
279 self.iter()
280 }
281}
282
283/// A package store that contains one mutable `CompileUnit`.
284pub struct OpenPackageStore {
285 store: PackageStore,
286 open: PackageId,
287}
288
289impl OpenPackageStore {
290 /// Returns a reference to the underlying, immutable,
291 /// package store.
292 #[must_use]
293 pub fn package_store(&self) -> &PackageStore {
294 &self.store
295 }
296
297 /// Returns the ID of the open package.
298 #[must_use]
299 pub fn open_package_id(&self) -> PackageId {
300 self.open
301 }
302
303 /// Returns a mutable reference to the open package,
304 /// along with a reference to the core library that can be used
305 /// to perform passes.
306 #[must_use]
307 pub fn get_open_mut(&mut self) -> (&global::Table, &mut CompileUnit) {
308 let id = self.open;
309
310 (
311 &self.store.core,
312 self.store
313 .units
314 .get_mut(id)
315 .expect("open package id should exist in store"),
316 )
317 }
318
319 /// Consumes the `OpenPackageStore` and returns a `PackageStore`
320 /// along with the id of the formerly open package.
321 #[must_use]
322 pub fn into_package_store(self) -> (PackageStore, PackageId) {
323 (self.store, self.open)
324 }
325}
326
327pub struct Iter<'a>(index_map::Iter<'a, PackageId, CompileUnit>);
328
329impl<'a> Iterator for Iter<'a> {
330 type Item = (PackageId, &'a CompileUnit);
331
332 fn next(&mut self) -> Option<Self::Item> {
333 self.0.next()
334 }
335}
336
337impl DoubleEndedIterator for Iter<'_> {
338 fn next_back(&mut self) -> Option<Self::Item> {
339 self.0.next_back()
340 }
341}
342
343pub(super) struct Offsetter(pub(super) u32);
344
345impl MutVisitor for Offsetter {
346 fn visit_span(&mut self, span: &mut Span) {
347 span.lo += self.0;
348 span.hi += self.0;
349 }
350}
351
352#[must_use]
353pub fn compile(
354 store: &PackageStore,
355 dependencies: &Dependencies,
356 sources: SourceMap,
357 capabilities: TargetCapabilityFlags,
358 language_features: LanguageFeatures,
359) -> CompileUnit {
360 let (ast_package, parse_errors) = parse_all(&sources, language_features);
361
362 compile_ast(
363 store,
364 dependencies,
365 ast_package,
366 sources,
367 capabilities,
368 parse_errors,
369 )
370}
371
372#[allow(clippy::module_name_repetitions)]
373pub fn compile_ast(
374 store: &PackageStore,
375 dependencies: &Dependencies,
376 mut ast_package: ast::Package,
377 sources: SourceMap,
378 capabilities: TargetCapabilityFlags,
379 parse_errors: Vec<qsc_parse::Error>,
380) -> CompileUnit {
381 let mut cond_compile = preprocess::Conditional::new(capabilities);
382 cond_compile.visit_package(&mut ast_package);
383 let dropped_names = cond_compile.into_names();
384
385 let mut ast_assigner = AstAssigner::new();
386 ast_assigner.visit_package(&mut ast_package);
387 AstValidator::default().visit_package(&ast_package);
388 let mut hir_assigner = HirAssigner::new();
389 let ResolveResult {
390 names,
391 locals,
392 errors: name_errors,
393 namespaces,
394 } = resolve_all(
395 store,
396 dependencies,
397 &mut hir_assigner,
398 &ast_package,
399 dropped_names.clone(),
400 );
401 let (tys, ty_errors) = typeck_all(store, dependencies, &ast_package, &names);
402 let mut lowerer = Lowerer::new();
403 let package = lowerer
404 .with(&mut hir_assigner, &names, &tys)
405 .lower_package(&ast_package, namespaces);
406 HirValidator::default().visit_package(&package);
407 let lower_errors = lowerer.drain_errors();
408
409 let errors = parse_errors
410 .into_iter()
411 .map(Into::into)
412 .chain(name_errors.into_iter().map(Into::into))
413 .chain(ty_errors.into_iter().map(Into::into))
414 .chain(lower_errors.into_iter().map(Into::into))
415 .map(Error)
416 .collect();
417
418 CompileUnit {
419 package,
420 ast: AstPackage {
421 package: ast_package,
422 tys,
423 names,
424 locals,
425 },
426 assigner: hir_assigner,
427 sources,
428 errors,
429 dropped_names,
430 }
431}
432
433/// Compiles the core library.
434///
435/// # Panics
436///
437/// Panics if the core library does not compile without errors.
438#[must_use]
439pub fn core() -> CompileUnit {
440 let store = PackageStore {
441 core: global::Table::default(),
442 units: IndexMap::new(),
443 next_id: PackageId::CORE,
444 };
445
446 let core: Vec<(SourceName, SourceContents)> = library::CORE_LIB
447 .iter()
448 .map(|(name, contents)| ((*name).into(), (*contents).into()))
449 .collect();
450 let sources = SourceMap::new(core, None);
451
452 let mut unit = compile(
453 &store,
454 &[],
455 sources,
456 TargetCapabilityFlags::empty(),
457 LanguageFeatures::default(),
458 );
459 assert_no_errors(&unit.sources, &mut unit.errors);
460 unit
461}
462
463/// Compiles the standard library.
464///
465/// # Panics
466///
467/// Panics if the standard library does not compile without errors.
468#[must_use]
469pub fn std(store: &PackageStore, capabilities: TargetCapabilityFlags) -> CompileUnit {
470 let std: Vec<(SourceName, SourceContents)> = library::STD_LIB
471 .iter()
472 .map(|(name, contents)| ((*name).into(), (*contents).into()))
473 .collect();
474 let sources = SourceMap::new(std, None);
475
476 let mut unit = compile(
477 store,
478 &[(PackageId::CORE, None)],
479 sources,
480 capabilities,
481 LanguageFeatures::default(),
482 );
483 assert_no_errors(&unit.sources, &mut unit.errors);
484 unit
485}
486
487fn parse_all(
488 sources: &SourceMap,
489 features: LanguageFeatures,
490) -> (ast::Package, Vec<qsc_parse::Error>) {
491 let mut namespaces = Vec::new();
492 let mut errors = Vec::new();
493 for source in sources.relative_sources() {
494 let (source_namespaces, source_errors) =
495 qsc_parse::namespaces(&source.contents, Some(&source.name), features);
496 for mut namespace in source_namespaces {
497 Offsetter(source.offset).visit_namespace(&mut namespace);
498 namespaces.push(TopLevelNode::Namespace(namespace));
499 }
500
501 append_parse_errors(&mut errors, source.offset, source_errors);
502 }
503
504 let entry = sources
505 .entry
506 .as_ref()
507 .filter(|source| !source.contents.is_empty())
508 .map(|source| {
509 let (mut entry, entry_errors) = qsc_parse::expr(&source.contents, features);
510 Offsetter(source.offset).visit_expr(&mut entry);
511 append_parse_errors(&mut errors, source.offset, entry_errors);
512 entry
513 });
514
515 let package = ast::Package {
516 id: ast::NodeId::default(),
517 nodes: namespaces.into_boxed_slice(),
518 entry,
519 };
520
521 (package, errors)
522}
523
524pub(crate) struct ResolveResult {
525 pub names: Names,
526 pub locals: Locals,
527 pub namespaces: qsc_data_structures::namespaces::NamespaceTreeRoot,
528 pub errors: Vec<resolve::Error>,
529}
530
531fn resolve_all(
532 store: &PackageStore,
533 dependencies: &Dependencies,
534 assigner: &mut HirAssigner,
535 package: &ast::Package,
536 mut dropped_names: Vec<TrackedName>,
537) -> ResolveResult {
538 let mut globals = resolve::GlobalTable::new();
539 if let Some(unit) = store.get(PackageId::CORE) {
540 globals.add_external_package(PackageId::CORE, &unit.package, store, &None);
541 dropped_names.extend(unit.dropped_names.iter().cloned());
542 }
543
544 for (ref id, alias) in dependencies {
545 let unit = store
546 .get(*id)
547 .expect("dependency should be in package store before compilation");
548 globals.add_external_package(*id, &unit.package, store, alias);
549 dropped_names.extend(unit.dropped_names.iter().cloned());
550 }
551
552 // bind all symbols in `add_local_package`
553 let mut errors = globals.add_local_package(assigner, package);
554 let mut resolver = Resolver::new(globals, dropped_names);
555
556 // bind all exported symbols in a follow-on step
557 resolver.bind_and_resolve_imports_and_exports(package);
558
559 // resolve all symbols
560 resolver.with(assigner).visit_package(package);
561 let (names, locals, mut resolver_errors, namespaces) = resolver.into_result();
562 errors.append(&mut resolver_errors);
563
564 ResolveResult {
565 names,
566 locals,
567 namespaces,
568 errors,
569 }
570}
571
572fn typeck_all(
573 store: &PackageStore,
574 dependencies: &Dependencies,
575 package: &ast::Package,
576 names: &Names,
577) -> (typeck::Table, Vec<typeck::Error>) {
578 let mut globals = typeck::GlobalTable::new();
579 if let Some(unit) = store.get(PackageId::CORE) {
580 globals.add_external_package(PackageId::CORE, &unit.package, store);
581 }
582
583 for (id, _alias) in dependencies {
584 let unit = store
585 .get(*id)
586 .expect("dependency should be added to package store before compilation");
587 // we can ignore the dependency alias here, because the
588 // typechecker doesn't do any name resolution -- it only operates on item ids.
589 // because of this, the typechecker doesn't actually need to care about visibility
590 // or the names of items at all.
591 globals.add_external_package(*id, &unit.package, store);
592 }
593
594 let mut checker = Checker::new(globals);
595 checker.check_package(names, package);
596 checker.into_table()
597}
598
599fn append_parse_errors(
600 errors: &mut Vec<qsc_parse::Error>,
601 offset: u32,
602 other: Vec<qsc_parse::Error>,
603) {
604 for error in other {
605 errors.push(error.with_offset(offset));
606 }
607}
608
609fn next_offset(last_source: Option<&Source>) -> u32 {
610 // Leave a gap of 1 between each source so that offsets at EOF
611 // get mapped to the correct source
612 last_source.map_or(0, |s| {
613 1 + s.offset + u32::try_from(s.contents.len()).expect("contents length should fit into u32")
614 })
615}
616
617fn assert_no_errors(sources: &SourceMap, errors: &mut Vec<Error>) {
618 if !errors.is_empty() {
619 for error in errors.drain(..) {
620 eprintln!("{:?}", Report::new(WithSource::from_map(sources, error)));
621 }
622
623 panic!("could not compile package");
624 }
625}
626
627#[must_use]
628pub fn longest_common_prefix<'a>(strs: &'a [&'a str]) -> &'a str {
629 if strs.len() == 1 {
630 return truncate_to_path_separator(strs[0]);
631 }
632
633 let Some(common_prefix_so_far) = strs.first() else {
634 return "";
635 };
636
637 for (i, character) in common_prefix_so_far.chars().enumerate() {
638 for string in strs {
639 if string.chars().nth(i) != Some(character) {
640 let prefix = &common_prefix_so_far[0..i];
641 // Find the last occurrence of the path separator in the prefix
642 return truncate_to_path_separator(prefix);
643 }
644 }
645 }
646 common_prefix_so_far
647}
648
649fn truncate_to_path_separator(prefix: &str) -> &str {
650 let last_separator_index = prefix
651 .rfind('/')
652 .or_else(|| prefix.rfind('\\'))
653 .or_else(|| prefix.rfind(':'));
654 if let Some(last_separator_index) = last_separator_index {
655 // Return the prefix up to and including the last path separator
656 return &prefix[0..=last_separator_index];
657 }
658 // If there's no path separator in the prefix, return an empty string
659 ""
660}
661