tinymist_analysis/syntax/
def.rs

1//! Definitions of syntax structures.
2
3use core::fmt;
4use std::{
5    collections::BTreeMap,
6    ops::{Deref, Range},
7    sync::Arc,
8};
9
10use rustc_hash::FxHashMap;
11use serde::{Deserialize, Serialize};
12use tinymist_derive::DeclEnum;
13use tinymist_std::DefId;
14use tinymist_world::package::PackageSpec;
15use typst::{
16    foundations::{Element, Func, Module, Type, Value},
17    syntax::{Span, SyntaxNode},
18    utils::LazyHash,
19};
20
21use crate::{
22    adt::interner::impl_internable,
23    docs::DocString,
24    prelude::*,
25    ty::{InsTy, Interned, SelectTy, Ty, TypeVar},
26};
27
28use super::{ExprDescriber, ExprPrinter};
29
30/// Information about expressions in a source file.
31///
32/// This structure wraps expression analysis data and provides access to
33/// expression resolution, documentation, and scoping information.
34#[derive(Debug, Clone, Hash)]
35pub struct ExprInfo(Arc<LazyHash<ExprInfoRepr>>);
36
37impl ExprInfo {
38    /// Creates a new [`ExprInfo`] instance from expression information
39    /// representation.
40    ///
41    /// Wraps the provided representation in an Arc and LazyHash for efficient
42    /// sharing and hashing.
43    pub fn new(repr: ExprInfoRepr) -> Self {
44        Self(Arc::new(LazyHash::new(repr)))
45    }
46}
47
48impl Deref for ExprInfo {
49    type Target = Arc<LazyHash<ExprInfoRepr>>;
50
51    fn deref(&self) -> &Self::Target {
52        &self.0
53    }
54}
55
56/// Representation of [`ExprInfo`] for a specific file.
57///
58/// Contains all the analyzed information including resolution maps,
59/// documentation strings, imports, and exports.
60#[derive(Debug)]
61pub struct ExprInfoRepr {
62    /// The file ID this expression information belongs to.
63    pub fid: TypstFileId,
64    /// Revision number for tracking changes to the file.
65    pub revision: usize,
66    /// The source code content.
67    pub source: Source,
68    /// The root expression of the file.
69    pub root: Expr,
70    /// Documentation string for the module.
71    pub module_docstring: Arc<DocString>,
72    /// The lexical scope of exported symbols from this file.
73    pub exports: Arc<LazyHash<LexicalScope>>,
74    /// Map from file IDs to imported lexical scopes.
75    pub imports: FxHashMap<TypstFileId, Arc<LazyHash<LexicalScope>>>,
76    /// Map from spans to expressions for scope analysis.
77    pub exprs: FxHashMap<Span, Expr>,
78    /// Map from spans to resolved reference expressions.
79    pub resolves: FxHashMap<Span, Interned<RefExpr>>,
80    /// Map from declarations to their documentation strings.
81    pub docstrings: FxHashMap<DeclExpr, Arc<DocString>>,
82}
83
84impl std::hash::Hash for ExprInfoRepr {
85    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
86        // already contained in the source.
87        // self.fid.hash(state);
88        self.revision.hash(state);
89        self.source.hash(state);
90        self.root.hash(state);
91        self.exports.hash(state);
92        let mut resolves = self.resolves.iter().collect::<Vec<_>>();
93        resolves.sort_by_key(|(fid, _)| fid.into_raw());
94        resolves.hash(state);
95        let mut imports = self.imports.iter().collect::<Vec<_>>();
96        imports.sort_by_key(|(fid, _)| *fid);
97        imports.hash(state);
98    }
99}
100
101impl ExprInfoRepr {
102    /// Gets the definition expression for a given declaration.
103    pub fn get_def(&self, decl: &Interned<Decl>) -> Option<Expr> {
104        if decl.is_def() {
105            return Some(Expr::Decl(decl.clone()));
106        }
107        let resolved = self.resolves.get(&decl.span())?;
108        Some(Expr::Ref(resolved.clone()))
109    }
110
111    /// Gets all references to a given declaration.
112    pub fn get_refs(
113        &self,
114        decl: Interned<Decl>,
115    ) -> impl Iterator<Item = (&Span, &Interned<RefExpr>)> {
116        let of = Some(Expr::Decl(decl.clone()));
117        self.resolves
118            .iter()
119            .filter(move |(_, r)| match (decl.as_ref(), r.decl.as_ref()) {
120                (Decl::Label(..), Decl::Label(..)) => r.decl == decl,
121                (Decl::Label(..), Decl::ContentRef(..)) => r.decl.name() == decl.name(),
122                (Decl::Label(..), _) => false,
123                _ => r.decl == decl || r.root == of,
124            })
125    }
126
127    /// Checks if a declaration is exported from this module.
128    pub fn is_exported(&self, decl: &Interned<Decl>) -> bool {
129        let of = Expr::Decl(decl.clone());
130        self.exports
131            .get(decl.name())
132            .is_some_and(|export| match export {
133                Expr::Ref(ref_expr) => ref_expr.root == Some(of),
134                exprt => *exprt == of,
135            })
136    }
137
138    /// Shows the expression information.
139    #[allow(dead_code)]
140    fn show(&self) {
141        use std::io::Write;
142        let vpath = self
143            .fid
144            .vpath()
145            .resolve(Path::new("target/exprs/"))
146            .unwrap();
147        let root = vpath.with_extension("root.expr");
148        std::fs::create_dir_all(root.parent().unwrap()).unwrap();
149        std::fs::write(root, format!("{}", self.root)).unwrap();
150        let scopes = vpath.with_extension("scopes.expr");
151        std::fs::create_dir_all(scopes.parent().unwrap()).unwrap();
152        {
153            let mut scopes = std::fs::File::create(scopes).unwrap();
154            for (span, expr) in self.exprs.iter() {
155                writeln!(scopes, "{span:?} -> {expr}").unwrap();
156            }
157        }
158        let imports = vpath.with_extension("imports.expr");
159        std::fs::create_dir_all(imports.parent().unwrap()).unwrap();
160        std::fs::write(imports, format!("{:#?}", self.imports)).unwrap();
161        let exports = vpath.with_extension("exports.expr");
162        std::fs::create_dir_all(exports.parent().unwrap()).unwrap();
163        std::fs::write(exports, format!("{:#?}", self.exports)).unwrap();
164    }
165}
166
167/// Represents different kinds of expressions in the language.
168///
169/// This enum covers all possible expression types that can appear in Typst
170/// source code, from basic literals to complex control flow constructs.
171#[derive(Debug, Clone, PartialEq, Eq, Hash)]
172pub enum Expr {
173    /// A sequence of expressions: `{ x; y; z }`
174    Block(Interned<Vec<Expr>>),
175    /// An array literal: `(1, 2, 3)`
176    Array(Interned<ArgsExpr>),
177    /// A dict literal: `(a: 1, b: 2)`
178    Dict(Interned<ArgsExpr>),
179    /// An args literal: `(1, 2, 3)`
180    Args(Interned<ArgsExpr>),
181    /// A pattern: `(x, y, ..z)`
182    Pattern(Interned<Pattern>),
183    /// An element literal: `[*Hi* there!]`
184    Element(Interned<ElementExpr>),
185    /// An unary operation: `-x`
186    Unary(Interned<UnExpr>),
187    /// A binary operation: `x + y`
188    Binary(Interned<BinExpr>),
189    /// A function call: `f(x, y)`
190    Apply(Interned<ApplyExpr>),
191    /// A function: `(x, y) => x + y`
192    Func(Interned<FuncExpr>),
193    /// A let: `let x = 1`
194    Let(Interned<LetExpr>),
195    /// A show: `show heading: it => emph(it.body)`
196    Show(Interned<ShowExpr>),
197    /// A set: `set text(...)`
198    Set(Interned<SetExpr>),
199    /// A reference: `#x`
200    Ref(Interned<RefExpr>),
201    /// A content reference: `@x`
202    ContentRef(Interned<ContentRefExpr>),
203    /// A select: `x.y`
204    Select(Interned<SelectExpr>),
205    /// An import expression: `import "path.typ": x`
206    Import(Interned<ImportExpr>),
207    /// An include expression: `include "path.typ"`
208    Include(Interned<IncludeExpr>),
209    /// A contextual expression: `context text.lang`
210    Contextual(Interned<Expr>),
211    /// A conditional expression: `if x { y } else { z }`
212    Conditional(Interned<IfExpr>),
213    /// A while loop: `while x { y }`
214    WhileLoop(Interned<WhileExpr>),
215    /// A for loop: `for x in y { z }`
216    ForLoop(Interned<ForExpr>),
217    /// A type: `str`
218    Type(Ty),
219    /// A declaration: `x`
220    Decl(DeclExpr),
221    /// A star import: `*`
222    Star,
223}
224
225impl Expr {
226    /// Returns a string representation of the expression.
227    pub fn repr(&self) -> EcoString {
228        let mut s = EcoString::new();
229        let _ = ExprDescriber::new(&mut s).write_expr(self);
230        s
231    }
232
233    /// Returns the span location of the expression.
234    pub fn span(&self) -> Span {
235        match self {
236            Expr::Decl(decl) => decl.span(),
237            Expr::Select(select) => select.span,
238            Expr::Apply(apply) => apply.span,
239            _ => Span::detached(),
240        }
241    }
242
243    /// Returns the file ID associated with this expression, if any.
244    pub fn file_id(&self) -> Option<TypstFileId> {
245        match self {
246            Expr::Decl(decl) => decl.file_id(),
247            _ => self.span().id(),
248        }
249    }
250
251    /// Returns whether the expression is definitely defined.
252    pub fn is_defined(&self) -> bool {
253        match self {
254            Expr::Ref(refs) => refs.root.is_some() || refs.term.is_some(),
255            Expr::Decl(decl) => decl.is_def(),
256            // There are unsure cases, like `x.y`, which may be defined or not.
257            _ => false,
258        }
259    }
260}
261
262impl fmt::Display for Expr {
263    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
264        ExprPrinter::new(f).write_expr(self)
265    }
266}
267
268/// Type alias for lexical scopes.
269///
270/// Represents a lexical scope as a persistent map from names to expressions.
271pub type LexicalScope = rpds::RedBlackTreeMapSync<Interned<str>, Expr>;
272
273/// Different types of scopes for expression evaluation.
274///
275/// Represents the various kinds of scopes that can contain variable bindings,
276/// including lexical scopes, modules, functions, and types.
277#[derive(Debug, Clone)]
278pub enum ExprScope {
279    /// A lexical scope extracted from a source file.
280    Lexical(LexicalScope),
281    /// A module instance which is either built-in or evaluated during analysis.
282    Module(Module),
283    /// A scope bound to a function.
284    Func(Func),
285    /// A scope bound to a type.
286    Type(Type),
287}
288
289impl ExprScope {
290    /// Creates an empty lexical scope.
291    pub fn empty() -> Self {
292        ExprScope::Lexical(LexicalScope::default())
293    }
294
295    /// Checks if the scope contains no bindings.
296    pub fn is_empty(&self) -> bool {
297        match self {
298            ExprScope::Lexical(scope) => scope.is_empty(),
299            ExprScope::Module(module) => is_empty_scope(module.scope()),
300            ExprScope::Func(func) => func.scope().is_none_or(is_empty_scope),
301            ExprScope::Type(ty) => is_empty_scope(ty.scope()),
302        }
303    }
304
305    /// Looks up a name in the scope and returns both expression and type
306    /// information.
307    pub fn get(&self, name: &Interned<str>) -> (Option<Expr>, Option<Ty>) {
308        let (of, val) = match self {
309            ExprScope::Lexical(scope) => {
310                crate::log_debug_ct!("evaluating: {name:?} in {scope:?}");
311                (scope.get(name).cloned(), None)
312            }
313            ExprScope::Module(module) => {
314                let v = module.scope().get(name);
315                // let decl =
316                //     v.and_then(|_| Some(Decl::external(module.file_id()?,
317                // name.clone()).into()));
318                (None, v)
319            }
320            ExprScope::Func(func) => (None, func.scope().unwrap().get(name)),
321            ExprScope::Type(ty) => (None, ty.scope().get(name)),
322        };
323
324        // ref_expr.of = of.clone();
325        // ref_expr.val = val.map(|v| Ty::Value(InsTy::new(v.clone())));
326        // return ref_expr;
327        (
328            of,
329            val.cloned()
330                .map(|val| Ty::Value(InsTy::new(val.read().to_owned()))),
331        )
332    }
333
334    /// Merges all bindings from this scope into the provided export map.
335    pub fn merge_into(&self, exports: &mut LexicalScope) {
336        match self {
337            ExprScope::Lexical(scope) => {
338                for (name, expr) in scope.iter() {
339                    exports.insert_mut(name.clone(), expr.clone());
340                }
341            }
342            ExprScope::Module(module) => {
343                crate::log_debug_ct!("imported: {module:?}");
344                let v = Interned::new(Ty::Value(InsTy::new(Value::Module(module.clone()))));
345                for (name, _) in module.scope().iter() {
346                    let name: Interned<str> = name.into();
347                    exports.insert_mut(name.clone(), select_of(v.clone(), name));
348                }
349            }
350            ExprScope::Func(func) => {
351                if let Some(scope) = func.scope() {
352                    let v = Interned::new(Ty::Value(InsTy::new(Value::Func(func.clone()))));
353                    for (name, _) in scope.iter() {
354                        let name: Interned<str> = name.into();
355                        exports.insert_mut(name.clone(), select_of(v.clone(), name));
356                    }
357                }
358            }
359            ExprScope::Type(ty) => {
360                let v = Interned::new(Ty::Value(InsTy::new(Value::Type(*ty))));
361                for (name, _) in ty.scope().iter() {
362                    let name: Interned<str> = name.into();
363                    exports.insert_mut(name.clone(), select_of(v.clone(), name));
364                }
365            }
366        }
367    }
368}
369
370fn select_of(source: Interned<Ty>, name: Interned<str>) -> Expr {
371    Expr::Type(Ty::Select(SelectTy::new(source, name)))
372}
373
374/// Kind of a definition.
375#[derive(Debug, Default, Clone, Copy, Hash, Serialize, Deserialize)]
376#[serde(rename_all = "camelCase")]
377pub enum DefKind {
378    /// A definition for some constant: `let x = 1`
379    #[default]
380    Constant,
381    /// A definition for some function: `(x, y) => x + y`
382    Function,
383    /// A definition for some variable: `let x = (x, y) => x + y`
384    Variable,
385    /// A definition for some module.
386    Module,
387    /// A definition for some struct (type).
388    Struct,
389    /// A definition for some reference: `<label>`
390    Reference,
391}
392
393impl fmt::Display for DefKind {
394    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
395        match self {
396            Self::Constant => write!(f, "constant"),
397            Self::Function => write!(f, "function"),
398            Self::Variable => write!(f, "variable"),
399            Self::Module => write!(f, "module"),
400            Self::Struct => write!(f, "struct"),
401            Self::Reference => write!(f, "reference"),
402        }
403    }
404}
405
406/// Type alias for declaration expressions.
407pub type DeclExpr = Interned<Decl>;
408
409/// Represents different kinds of declarations in the language.
410#[derive(Clone, PartialEq, Eq, Hash, DeclEnum)]
411pub enum Decl {
412    /// A function declaration: `(x, y) => x + y`
413    Func(SpannedDecl),
414    /// An import alias declaration: `import "path.typ": x`
415    ImportAlias(SpannedDecl),
416    /// A variable declaration: `let x = 1`
417    Var(SpannedDecl),
418    /// An identifier reference declaration: `x`
419    IdentRef(SpannedDecl),
420    /// A module declaration: `import calc`
421    Module(ModuleDecl),
422    /// A module alias declaration: `import "path.typ" as x`
423    ModuleAlias(SpannedDecl),
424    /// A path stem declaration: `path.typ`
425    PathStem(SpannedDecl),
426    /// An import path declaration: `import "path.typ"`
427    ImportPath(SpannedDecl),
428    /// An include path declaration: `include "path.typ"`
429    IncludePath(SpannedDecl),
430    /// An import declaration: `import "path.typ"`
431    Import(SpannedDecl),
432    /// A content reference declaration: `@x`
433    ContentRef(SpannedDecl),
434    /// A label declaration: `label`
435    Label(SpannedDecl),
436    /// A string name declaration: `"x"`
437    StrName(SpannedDecl),
438    /// A module import declaration: `import "path.typ": *`
439    ModuleImport(SpanDecl),
440    /// A closure declaration: `(x, y) => x + y`
441    Closure(SpanDecl),
442    /// A pattern declaration: `let (x, y, ..z) = 1`
443    Pattern(SpanDecl),
444    /// A spread declaration: `..z`
445    Spread(SpanDecl),
446    /// A content declaration: `#[text]`
447    Content(SpanDecl),
448    /// A constant declaration: `let x = 1`
449    Constant(SpanDecl),
450    /// A bib entry declaration: `@entry`
451    BibEntry(NameRangeDecl),
452    /// A docs declaration created by the compiler.
453    Docs(DocsDecl),
454    /// A generated declaration created by the compiler.
455    Generated(GeneratedDecl),
456}
457
458impl Decl {
459    /// Creates a function declaration from an identifier.
460    pub fn func(ident: ast::Ident) -> Self {
461        Self::Func(SpannedDecl {
462            name: ident.get().into(),
463            at: ident.span(),
464        })
465    }
466
467    /// Creates a variable declaration from a string literal.
468    pub fn lit(name: &str) -> Self {
469        Self::Var(SpannedDecl {
470            name: name.into(),
471            at: Span::detached(),
472        })
473    }
474
475    /// Creates a variable declaration from an interned string.
476    pub fn lit_(name: Interned<str>) -> Self {
477        Self::Var(SpannedDecl {
478            name,
479            at: Span::detached(),
480        })
481    }
482
483    /// Creates a variable declaration from an identifier.
484    pub fn var(ident: ast::Ident) -> Self {
485        Self::Var(SpannedDecl {
486            name: ident.get().into(),
487            at: ident.span(),
488        })
489    }
490
491    /// Creates an import alias declaration from an identifier.
492    pub fn import_alias(ident: ast::Ident) -> Self {
493        Self::ImportAlias(SpannedDecl {
494            name: ident.get().into(),
495            at: ident.span(),
496        })
497    }
498
499    /// Creates an identifier reference declaration from an identifier.
500    pub fn ident_ref(ident: ast::Ident) -> Self {
501        Self::IdentRef(SpannedDecl {
502            name: ident.get().into(),
503            at: ident.span(),
504        })
505    }
506
507    /// Creates an identifier reference declaration from a math identifier.
508    pub fn math_ident_ref(ident: ast::MathIdent) -> Self {
509        Self::IdentRef(SpannedDecl {
510            name: ident.get().into(),
511            at: ident.span(),
512        })
513    }
514
515    /// Creates a module declaration with a file ID.
516    pub fn module(fid: TypstFileId) -> Self {
517        let name = {
518            let stem = fid.vpath().as_rooted_path().file_stem();
519            stem.and_then(|s| Some(Interned::new_str(s.to_str()?)))
520                .unwrap_or_default()
521        };
522        Self::Module(ModuleDecl { name, fid })
523    }
524
525    /// Creates a module declaration with a name and a file ID.
526    pub fn module_with_name(name: Interned<str>, fid: TypstFileId) -> Self {
527        Self::Module(ModuleDecl { name, fid })
528    }
529
530    /// Creates a module alias declaration from an identifier.
531    pub fn module_alias(ident: ast::Ident) -> Self {
532        Self::ModuleAlias(SpannedDecl {
533            name: ident.get().into(),
534            at: ident.span(),
535        })
536    }
537
538    /// Creates an import declaration from an identifier.
539    pub fn import(ident: ast::Ident) -> Self {
540        Self::Import(SpannedDecl {
541            name: ident.get().into(),
542            at: ident.span(),
543        })
544    }
545
546    /// Creates a label declaration with a name and span.
547    pub fn label(name: &str, at: Span) -> Self {
548        Self::Label(SpannedDecl {
549            name: name.into(),
550            at,
551        })
552    }
553
554    /// Creates a content reference declaration from a reference AST node.
555    pub fn ref_(ident: ast::Ref) -> Self {
556        Self::ContentRef(SpannedDecl {
557            name: ident.target().into(),
558            at: ident.span(),
559        })
560    }
561
562    /// Creates a string name declaration from a syntax node and name.
563    pub fn str_name(s: SyntaxNode, name: &str) -> Decl {
564        Self::StrName(SpannedDecl {
565            name: name.into(),
566            at: s.span(),
567        })
568    }
569
570    /// Calculates the path stem from a string path or package specification.
571    ///
572    /// For package specs (starting with '@'), extracts the package name.
573    /// For file paths, extracts the file stem. Returns empty string if
574    /// extraction fails.
575    pub fn calc_path_stem(s: &str) -> Interned<str> {
576        use std::str::FromStr;
577        let name = if s.starts_with('@') {
578            let spec = PackageSpec::from_str(s).ok();
579            spec.map(|spec| Interned::new_str(spec.name.as_str()))
580        } else {
581            let stem = Path::new(s).file_stem();
582            stem.and_then(|stem| Some(Interned::new_str(stem.to_str()?)))
583        };
584        name.unwrap_or_default()
585    }
586
587    /// Creates a path stem declaration from a syntax node and name.
588    pub fn path_stem(s: SyntaxNode, name: Interned<str>) -> Self {
589        Self::PathStem(SpannedDecl { name, at: s.span() })
590    }
591
592    /// Creates an import path declaration with a span and name.
593    pub fn import_path(s: Span, name: Interned<str>) -> Self {
594        Self::ImportPath(SpannedDecl { name, at: s })
595    }
596
597    /// Creates an include path declaration with a span and name.
598    pub fn include_path(s: Span, name: Interned<str>) -> Self {
599        Self::IncludePath(SpannedDecl { name, at: s })
600    }
601
602    /// Creates a module import declaration with just a span.
603    pub fn module_import(s: Span) -> Self {
604        Self::ModuleImport(SpanDecl(s))
605    }
606
607    /// Creates a closure declaration with just a span.
608    pub fn closure(s: Span) -> Self {
609        Self::Closure(SpanDecl(s))
610    }
611
612    /// Creates a pattern declaration with just a span.
613    pub fn pattern(s: Span) -> Self {
614        Self::Pattern(SpanDecl(s))
615    }
616
617    /// Creates a spread declaration with just a span.
618    pub fn spread(s: Span) -> Self {
619        Self::Spread(SpanDecl(s))
620    }
621
622    /// Creates a content declaration with just a span.
623    pub fn content(s: Span) -> Self {
624        Self::Content(SpanDecl(s))
625    }
626
627    /// Creates a constant declaration with just a span.
628    pub fn constant(s: Span) -> Self {
629        Self::Constant(SpanDecl(s))
630    }
631
632    /// Creates a documentation declaration linking a base declaration with a
633    /// type variable.
634    pub fn docs(base: Interned<Decl>, var: Interned<TypeVar>) -> Self {
635        Self::Docs(DocsDecl { base, var })
636    }
637
638    /// Creates a generated declaration with a definition ID.
639    pub fn generated(def_id: DefId) -> Self {
640        Self::Generated(GeneratedDecl(def_id))
641    }
642
643    /// Creates a bibliography entry declaration.
644    pub fn bib_entry(
645        name: Interned<str>,
646        fid: TypstFileId,
647        name_range: Range<usize>,
648        range: Option<Range<usize>>,
649    ) -> Self {
650        Self::BibEntry(NameRangeDecl {
651            name,
652            at: Box::new((fid, name_range, range)),
653        })
654    }
655
656    /// Checks if this declaration represents a definition rather than a
657    /// reference (usage of a definition).
658    pub fn is_def(&self) -> bool {
659        matches!(
660            self,
661            Self::Func(..)
662                | Self::BibEntry(..)
663                | Self::Closure(..)
664                | Self::Var(..)
665                | Self::Label(..)
666                | Self::StrName(..)
667                | Self::Module(..)
668                | Self::ModuleImport(..)
669                | Self::PathStem(..)
670                | Self::ImportPath(..)
671                | Self::IncludePath(..)
672                | Self::Spread(..)
673                | Self::Generated(..)
674        )
675    }
676
677    /// Returns the kind of definition this declaration represents.
678    pub fn kind(&self) -> DefKind {
679        use Decl::*;
680        match self {
681            ModuleAlias(..) | Module(..) | PathStem(..) | ImportPath(..) | IncludePath(..) => {
682                DefKind::Module
683            }
684            // Type(_) => DocStringKind::Struct,
685            Func(..) | Closure(..) => DefKind::Function,
686            Label(..) | BibEntry(..) | ContentRef(..) => DefKind::Reference,
687            IdentRef(..) | ImportAlias(..) | Import(..) | Var(..) => DefKind::Variable,
688            Pattern(..) | Docs(..) | Generated(..) | Constant(..) | StrName(..)
689            | ModuleImport(..) | Content(..) | Spread(..) => DefKind::Constant,
690        }
691    }
692
693    /// Gets file location of the declaration.
694    pub fn file_id(&self) -> Option<TypstFileId> {
695        match self {
696            Self::Module(ModuleDecl { fid, .. }) => Some(*fid),
697            Self::BibEntry(NameRangeDecl { at, .. }) => Some(at.0),
698            that => that.span().id(),
699        }
700    }
701
702    /// Gets full range of the declaration.
703    pub fn full_range(&self) -> Option<Range<usize>> {
704        if let Decl::BibEntry(decl) = self {
705            return decl.at.2.clone();
706        }
707
708        None
709    }
710
711    /// Creates a reference expression that points to this declaration.
712    pub fn as_def(this: &Interned<Self>, val: Option<Ty>) -> Interned<RefExpr> {
713        let def: Expr = this.clone().into();
714        Interned::new(RefExpr {
715            decl: this.clone(),
716            step: Some(def.clone()),
717            root: Some(def),
718            term: val,
719        })
720    }
721}
722
723impl Ord for Decl {
724    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
725        let base = match (self, other) {
726            (Self::Generated(l), Self::Generated(r)) => l.0.0.cmp(&r.0.0),
727            (Self::Module(l), Self::Module(r)) => l.fid.cmp(&r.fid),
728            (Self::Docs(l), Self::Docs(r)) => l.var.cmp(&r.var).then_with(|| l.base.cmp(&r.base)),
729            _ => self.span().into_raw().cmp(&other.span().into_raw()),
730        };
731
732        base.then_with(|| self.name().cmp(other.name()))
733    }
734}
735
736trait StrictCmp {
737    /// Low-performance comparison but it is free from the concurrency issue.
738    /// This is only used for making stable test snapshots.
739    fn strict_cmp(&self, other: &Self) -> std::cmp::Ordering;
740}
741
742impl Decl {
743    /// Low-performance comparison that is free from concurrency issues.
744    pub fn strict_cmp(&self, other: &Self) -> std::cmp::Ordering {
745        let base = match (self, other) {
746            (Self::Generated(l), Self::Generated(r)) => l.0.0.cmp(&r.0.0),
747            (Self::Module(l), Self::Module(r)) => l.fid.strict_cmp(&r.fid),
748            (Self::Docs(l), Self::Docs(r)) => l
749                .var
750                .strict_cmp(&r.var)
751                .then_with(|| l.base.strict_cmp(&r.base)),
752            _ => self.span().strict_cmp(&other.span()),
753        };
754
755        base.then_with(|| self.name().cmp(other.name()))
756    }
757}
758
759impl StrictCmp for TypstFileId {
760    fn strict_cmp(&self, other: &Self) -> std::cmp::Ordering {
761        self.package()
762            .map(ToString::to_string)
763            .cmp(&other.package().map(ToString::to_string))
764            .then_with(|| self.vpath().cmp(other.vpath()))
765    }
766}
767impl<T: StrictCmp> StrictCmp for Option<T> {
768    fn strict_cmp(&self, other: &Self) -> std::cmp::Ordering {
769        match (self, other) {
770            (Some(l), Some(r)) => l.strict_cmp(r),
771            (Some(_), None) => std::cmp::Ordering::Greater,
772            (None, Some(_)) => std::cmp::Ordering::Less,
773            (None, None) => std::cmp::Ordering::Equal,
774        }
775    }
776}
777
778impl StrictCmp for Span {
779    fn strict_cmp(&self, other: &Self) -> std::cmp::Ordering {
780        self.id()
781            .strict_cmp(&other.id())
782            .then_with(|| self.into_raw().cmp(&other.into_raw()))
783    }
784}
785
786impl PartialOrd for Decl {
787    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
788        Some(self.cmp(other))
789    }
790}
791
792impl From<Decl> for Expr {
793    fn from(decl: Decl) -> Self {
794        Expr::Decl(decl.into())
795    }
796}
797
798impl From<DeclExpr> for Expr {
799    fn from(decl: DeclExpr) -> Self {
800        Expr::Decl(decl)
801    }
802}
803
804/// A declaration with an associated name and span location.
805#[derive(Clone, PartialEq, Eq, Hash)]
806pub struct SpannedDecl {
807    /// The name of the declaration.
808    name: Interned<str>,
809    /// The span location of the declaration.
810    at: Span,
811}
812
813impl SpannedDecl {
814    /// Gets the name of the declaration.
815    fn name(&self) -> &Interned<str> {
816        &self.name
817    }
818
819    /// Gets the span location of the declaration.
820    fn span(&self) -> Span {
821        self.at
822    }
823}
824
825impl fmt::Debug for SpannedDecl {
826    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
827        f.write_str(self.name.as_ref())
828    }
829}
830
831/// A declaration with a name and range information.
832#[derive(Clone, PartialEq, Eq, Hash)]
833pub struct NameRangeDecl {
834    /// The name of the declaration.
835    pub name: Interned<str>,
836    /// Boxed tuple containing (file_id, name_range, full_range).
837    pub at: Box<(TypstFileId, Range<usize>, Option<Range<usize>>)>,
838}
839
840impl NameRangeDecl {
841    /// Gets the name of the declaration.
842    fn name(&self) -> &Interned<str> {
843        &self.name
844    }
845
846    /// Gets the span location of the declaration.
847    fn span(&self) -> Span {
848        Span::detached()
849    }
850}
851
852impl fmt::Debug for NameRangeDecl {
853    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
854        f.write_str(self.name.as_ref())
855    }
856}
857
858/// A module declaration with name and file ID.
859#[derive(Clone, PartialEq, Eq, Hash)]
860pub struct ModuleDecl {
861    /// The name of the module.
862    pub name: Interned<str>,
863    /// The file ID where the module is defined.
864    pub fid: TypstFileId,
865}
866
867impl ModuleDecl {
868    /// Gets the name of the declaration.
869    fn name(&self) -> &Interned<str> {
870        &self.name
871    }
872
873    /// Gets the span location of the declaration.
874    fn span(&self) -> Span {
875        Span::detached()
876    }
877}
878
879impl fmt::Debug for ModuleDecl {
880    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
881        f.write_str(self.name.as_ref())
882    }
883}
884
885/// A documentation declaration linking a base declaration with type variables.
886#[derive(Clone, PartialEq, Eq, Hash)]
887pub struct DocsDecl {
888    base: Interned<Decl>,
889    var: Interned<TypeVar>,
890}
891
892impl DocsDecl {
893    /// Gets the name of the declaration.
894    fn name(&self) -> &Interned<str> {
895        Interned::empty()
896    }
897
898    /// Gets the span location of the declaration.
899    fn span(&self) -> Span {
900        Span::detached()
901    }
902}
903
904impl fmt::Debug for DocsDecl {
905    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
906        write!(f, "{:?}, {:?}", self.base, self.var)
907    }
908}
909
910/// A span-only declaration for anonymous constructs.
911#[derive(Clone, PartialEq, Eq, Hash)]
912pub struct SpanDecl(Span);
913
914impl SpanDecl {
915    /// Gets the name of the declaration.
916    fn name(&self) -> &Interned<str> {
917        Interned::empty()
918    }
919
920    /// Gets the span location of the declaration.
921    fn span(&self) -> Span {
922        self.0
923    }
924}
925
926impl fmt::Debug for SpanDecl {
927    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
928        write!(f, "..")
929    }
930}
931
932/// A generated declaration with a unique definition ID.
933#[derive(Clone, PartialEq, Eq, Hash)]
934pub struct GeneratedDecl(DefId);
935
936impl GeneratedDecl {
937    /// Gets the name of the declaration.
938    fn name(&self) -> &Interned<str> {
939        Interned::empty()
940    }
941
942    /// Gets the span location of the declaration.
943    fn span(&self) -> Span {
944        Span::detached()
945    }
946}
947
948impl fmt::Debug for GeneratedDecl {
949    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
950        self.0.fmt(f)
951    }
952}
953
954/// Type alias for unary expressions.
955pub type UnExpr = UnInst<Expr>;
956/// Type alias for binary expressions.
957pub type BinExpr = BinInst<Expr>;
958
959/// Type alias for export maps.
960///
961/// Maps exported names to their corresponding expressions.
962pub type ExportMap = BTreeMap<Interned<str>, Expr>;
963
964/// Represents different kinds of function arguments.
965///
966/// Covers positional arguments, named arguments, and spread arguments.
967#[derive(Debug, Clone, PartialEq, Eq, Hash)]
968pub enum ArgExpr {
969    /// A positional argument: `x`
970    Pos(Expr),
971    /// A named argument: `a: x`
972    Named(Box<(DeclExpr, Expr)>),
973    /// A named argument with a default value: `((a): x)`
974    NamedRt(Box<(Expr, Expr)>),
975    /// A spread argument: `..x`
976    Spread(Expr),
977}
978
979/// Represents different kinds of patterns for destructuring.
980#[derive(Debug, Clone, PartialEq, Eq, Hash)]
981pub enum Pattern {
982    /// A general pattern expression can occur in right-hand side of a
983    /// function signature.
984    Expr(Expr),
985    /// A simple pattern: `x`
986    Simple(Interned<Decl>),
987    /// A pattern signature: `(x, y: val, ..z)`
988    Sig(Box<PatternSig>),
989}
990
991impl fmt::Display for Pattern {
992    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
993        ExprPrinter::new(f).write_pattern(self)
994    }
995}
996
997impl Pattern {
998    /// Returns a string representation of the pattern.
999    pub fn repr(&self) -> EcoString {
1000        let mut s = EcoString::new();
1001        let _ = ExprDescriber::new(&mut s).write_pattern(self);
1002        s
1003    }
1004}
1005
1006/// Signature pattern for function parameters.
1007///
1008/// Describes the structure of function parameters including positional,
1009/// named, and spread parameters.
1010#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1011pub struct PatternSig {
1012    /// Positional parameters in order.
1013    pub pos: EcoVec<Interned<Pattern>>,
1014    /// Named parameters with their default patterns.
1015    pub named: EcoVec<(DeclExpr, Interned<Pattern>)>,
1016    /// Left spread parameter (collects extra positional arguments).
1017    pub spread_left: Option<(DeclExpr, Interned<Pattern>)>,
1018    /// Right spread parameter (collects remaining arguments).
1019    pub spread_right: Option<(DeclExpr, Interned<Pattern>)>,
1020}
1021
1022impl Pattern {}
1023
1024impl_internable!(Decl,);
1025
1026/// Represents a content sequence expression.
1027///
1028/// Used for sequences of content elements with associated type information.
1029#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1030pub struct ContentSeqExpr {
1031    /// The type of the content sequence
1032    pub ty: Ty,
1033}
1034
1035/// Represents a reference expression.
1036///
1037/// A reference expression tracks how an identifier resolves through the lexical
1038/// scope, imports, and field accesses. It maintains a chain of resolution steps
1039/// to support features like go-to-definition, go-to-reference, and type
1040/// inference.
1041///
1042/// # Resolution Chain
1043///
1044/// The fields form a resolution chain: `root` -> `step` -> `decl`, where:
1045/// - `root` is the original source of the value
1046/// - `step` is any intermediate transformation
1047/// - `decl` is the final identifier being referenced
1048/// - `term` is the resolved type (if known)
1049///   - Hint: A value `1`'s typst type is `int`, but here we keep the type as
1050///     `1` to improve the type inference.
1051///
1052/// # Examples
1053///
1054/// ## Simple identifier reference
1055/// ```rust,ignore
1056/// // For: let x = value; let y = x;
1057/// RefExpr {
1058///     decl: y,           // The identifier 'y'
1059///     root: Some(x),     // Points back to 'x'
1060///     step: Some(x),     // Same as root for simple refs
1061///     term: None,        // Type may not be known yet
1062/// }
1063/// ```
1064///
1065/// ## Import with rename
1066/// ```rust,ignore
1067/// // For: import "mod.typ": old as new
1068/// // First creates ref for 'old':
1069/// RefExpr { decl: old, root: Some(mod.old), step: Some(field), term: Some(Func(() -> dict)) }
1070/// // Then creates ref for 'new':
1071/// RefExpr { decl: new, root: Some(mod.old), step: Some(old), term: Some(Func(() -> dict)) }
1072/// ```
1073///
1074/// ## Builtin definitions
1075/// ```rust,ignore
1076/// // For: std.length
1077/// RefExpr { decl: length, root: None, step: None, term: Some(Type(length)) }
1078/// ```
1079#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1080pub struct RefExpr {
1081    /// The declaration being referenced (the final identifier in the chain).
1082    ///
1083    /// This is always set and represents the identifier at the current point
1084    /// of reference (e.g., the variable name, import alias, or field name).
1085    pub decl: DeclExpr,
1086
1087    /// The intermediate expression in the resolution chain.
1088    ///
1089    /// Set in the following cases:
1090    /// - **Import/include**: The module expression being imported
1091    /// - **Field access**: The selected field's expression
1092    /// - **Scope resolution**: The scope expression being resolved
1093    /// - **Renamed imports**: The original name before renaming
1094    ///
1095    /// `None` when the identifier is an undefined reference.
1096    pub step: Option<Expr>,
1097
1098    /// The root expression at the start of the reference chain.
1099    ///
1100    /// A root definition never references another root definition.
1101    pub root: Option<Expr>,
1102
1103    /// The final resolved type of the referenced value.
1104    ///
1105    /// Set whenever a type is known for the referenced value.
1106    ///
1107    /// Some reference doesn't have a root definition, but has a term. For
1108    /// example, `std.length` is termed as `Type(length)` while has no a
1109    /// definition.
1110    pub term: Option<Ty>,
1111}
1112
1113/// Represents a content reference expression.
1114#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1115pub struct ContentRefExpr {
1116    /// The identifier being referenced.
1117    pub ident: DeclExpr,
1118    /// The declaration this reference points to (if resolved).
1119    pub of: Option<DeclExpr>,
1120    /// The body content associated with the reference.
1121    pub body: Option<Expr>,
1122}
1123
1124/// Represents a field selection expression.
1125#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1126pub struct SelectExpr {
1127    /// The left-hand side expression being selected from.
1128    pub lhs: Expr,
1129    /// The key or field name being selected.
1130    pub key: DeclExpr,
1131    /// The span location of this selection.
1132    pub span: Span,
1133}
1134
1135impl SelectExpr {
1136    /// Creates a new SelectExpr with the given key and left-hand side.
1137    pub fn new(key: DeclExpr, lhs: Expr) -> Interned<Self> {
1138        Interned::new(Self {
1139            key,
1140            lhs,
1141            span: Span::detached(),
1142        })
1143    }
1144}
1145
1146/// Represents an arguments expression.
1147#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1148pub struct ArgsExpr {
1149    /// The list of arguments.
1150    pub args: Vec<ArgExpr>,
1151    /// The span location of the argument list.
1152    pub span: Span,
1153}
1154
1155impl ArgsExpr {
1156    /// Creates a new ArgsExpr with the given span and arguments.
1157    pub fn new(span: Span, args: Vec<ArgExpr>) -> Interned<Self> {
1158        Interned::new(Self { args, span })
1159    }
1160}
1161
1162/// Represents an element expression.
1163#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1164pub struct ElementExpr {
1165    /// The Typst element type.
1166    pub elem: Element,
1167    /// The content expressions within this element.
1168    pub content: EcoVec<Expr>,
1169}
1170
1171/// Represents a function application expression.
1172#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1173pub struct ApplyExpr {
1174    /// The function expression being called.
1175    pub callee: Expr,
1176    /// The arguments passed to the function.
1177    pub args: Expr,
1178    /// The span location of the function call.
1179    pub span: Span,
1180}
1181
1182/// Represents a function expression.
1183#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1184pub struct FuncExpr {
1185    /// The declaration for this function.
1186    pub decl: DeclExpr,
1187    /// The parameter signature defining function inputs.
1188    pub params: PatternSig,
1189    /// The function body expression.
1190    pub body: Expr,
1191}
1192
1193/// Represents a let binding expression.
1194#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1195pub struct LetExpr {
1196    /// Span of the pattern.
1197    pub span: Span,
1198    /// The pattern being bound (left side of assignment).
1199    pub pattern: Interned<Pattern>,
1200    /// The optional body expression (right side of assignment).
1201    pub body: Option<Expr>,
1202}
1203
1204/// Represents a show rule expression.
1205#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1206pub struct ShowExpr {
1207    /// Optional selector expression to determine what to show.
1208    pub selector: Option<Expr>,
1209    /// The edit function to apply to selected elements.
1210    pub edit: Expr,
1211}
1212
1213/// Represents a set rule expression.
1214#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1215pub struct SetExpr {
1216    /// The target element or function to set.
1217    pub target: Expr,
1218    /// The arguments to apply to the target.
1219    pub args: Expr,
1220    /// Optional condition for when to apply the set rule.
1221    pub cond: Option<Expr>,
1222}
1223
1224/// Represents an import expression.
1225#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1226pub struct ImportExpr {
1227    /// The reference expression for what is being imported.
1228    pub decl: Interned<RefExpr>,
1229}
1230
1231/// Represents an include expression.
1232#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1233pub struct IncludeExpr {
1234    /// The source expression indicating what file or content to include.
1235    pub source: Expr,
1236}
1237
1238/// Represents a conditional (if) expression.
1239#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1240pub struct IfExpr {
1241    /// The condition expression to evaluate.
1242    pub cond: Expr,
1243    /// The expression to evaluate if condition is true.
1244    pub then: Expr,
1245    /// The expression to evaluate if condition is false.
1246    pub else_: Expr,
1247}
1248
1249/// Represents a while loop expression.
1250#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1251pub struct WhileExpr {
1252    /// The condition expression evaluated each iteration.
1253    pub cond: Expr,
1254    /// The body expression executed while condition is true.
1255    pub body: Expr,
1256}
1257
1258/// Represents a for loop expression.
1259#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1260pub struct ForExpr {
1261    /// The pattern to match each iteration value against.
1262    pub pattern: Interned<Pattern>,
1263    /// The expression that produces values to iterate over.
1264    pub iter: Expr,
1265    /// The body expression executed for each iteration.
1266    pub body: Expr,
1267}
1268
1269/// The kind of unary operation.
1270#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
1271pub enum UnaryOp {
1272    /// The (arithmetic) positive operation.
1273    /// `+t`
1274    Pos,
1275    /// The (arithmetic) negate operation.
1276    /// `-t`
1277    Neg,
1278    /// The (logical) not operation.
1279    /// `not t`
1280    Not,
1281    /// The return operation.
1282    /// `return t`
1283    Return,
1284    /// The typst context operation.
1285    /// `context t`
1286    Context,
1287    /// The spreading operation.
1288    /// `..t`
1289    Spread,
1290    /// The not element of operation.
1291    /// `not in t`
1292    NotElementOf,
1293    /// The element of operation.
1294    /// `in t`
1295    ElementOf,
1296    /// The type of operation.
1297    /// `type(t)`
1298    TypeOf,
1299}
1300
1301/// A unary operation type.
1302#[derive(Debug, Hash, Clone, PartialEq, Eq)]
1303pub struct UnInst<T> {
1304    /// The operand of the unary operation.
1305    pub lhs: T,
1306    /// The kind of the unary operation.
1307    pub op: UnaryOp,
1308}
1309
1310impl<T: Ord> PartialOrd for UnInst<T> {
1311    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
1312        Some(self.cmp(other))
1313    }
1314}
1315
1316impl<T: Ord> Ord for UnInst<T> {
1317    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
1318        let op_as_int = self.op as u8;
1319        let other_op_as_int = other.op as u8;
1320        op_as_int
1321            .cmp(&other_op_as_int)
1322            .then_with(|| self.lhs.cmp(&other.lhs))
1323    }
1324}
1325
1326impl UnInst<Expr> {
1327    /// Creates a unary operation type with the given operator and operand.
1328    pub fn new(op: UnaryOp, lhs: Expr) -> Interned<Self> {
1329        Interned::new(Self { lhs, op })
1330    }
1331}
1332
1333impl<T> UnInst<T> {
1334    /// Gets the operands of the unary operation.
1335    pub fn operands(&self) -> [&T; 1] {
1336        [&self.lhs]
1337    }
1338}
1339
1340/// Type alias for binary operation types.
1341pub type BinaryOp = ast::BinOp;
1342
1343/// A binary operation type.
1344#[derive(Debug, Hash, Clone, PartialEq, Eq)]
1345pub struct BinInst<T> {
1346    /// The operands of the binary operation (left, right).
1347    pub operands: (T, T),
1348    /// The kind of the binary operation.
1349    pub op: BinaryOp,
1350}
1351
1352impl<T: Ord> PartialOrd for BinInst<T> {
1353    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
1354        Some(self.cmp(other))
1355    }
1356}
1357
1358impl<T: Ord> Ord for BinInst<T> {
1359    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
1360        let op_as_int = self.op as u8;
1361        let other_op_as_int = other.op as u8;
1362        op_as_int
1363            .cmp(&other_op_as_int)
1364            .then_with(|| self.operands.cmp(&other.operands))
1365    }
1366}
1367
1368impl BinInst<Expr> {
1369    /// Creates a binary operation type with the given operator and operands.
1370    pub fn new(op: BinaryOp, lhs: Expr, rhs: Expr) -> Interned<Self> {
1371        Interned::new(Self {
1372            operands: (lhs, rhs),
1373            op,
1374        })
1375    }
1376}
1377
1378impl<T> BinInst<T> {
1379    /// Gets the operands of the binary operation.
1380    pub fn operands(&self) -> [&T; 2] {
1381        [&self.operands.0, &self.operands.1]
1382    }
1383}
1384
1385/// Checks if a scope is empty.
1386fn is_empty_scope(scope: &typst::foundations::Scope) -> bool {
1387    scope.iter().next().is_none()
1388}
1389
1390impl_internable!(
1391    Expr,
1392    ArgsExpr,
1393    ElementExpr,
1394    ContentSeqExpr,
1395    RefExpr,
1396    ContentRefExpr,
1397    SelectExpr,
1398    ImportExpr,
1399    IncludeExpr,
1400    IfExpr,
1401    WhileExpr,
1402    ForExpr,
1403    FuncExpr,
1404    LetExpr,
1405    ShowExpr,
1406    SetExpr,
1407    Pattern,
1408    EcoVec<(Decl, Expr)>,
1409    Vec<ArgExpr>,
1410    Vec<Expr>,
1411    UnInst<Expr>,
1412    BinInst<Expr>,
1413    ApplyExpr,
1414);