AST

Active contributors: DougGregor, slavapestov, hamishknight

Purpose

lib/AST/ holds the in-memory program representation: declarations (StructDecl, FuncDecl, ...), types (StructType, FunctionType, ...), expressions, statements, patterns, and the request evaluator that drives lazy queries over them. The AST is shared by every later stage; SILGen, Sema, IRGen, ClangImporter, and the IDE all read AST nodes.

Directory layout

lib/AST/                       (172 files)
├── Decl.cpp                   # 13,602 lines — declaration node implementations
├── Type.cpp
├── Expr.cpp
├── Stmt.cpp
├── Pattern.cpp
├── Module.cpp                  # ModuleDecl, FileUnit
├── ASTContext.cpp              # the context that owns everything
├── ASTPrinter.cpp              # canonical printing of AST as Swift
├── Evaluator.cpp               # the request evaluator core
├── DiagnosticEngine.cpp
├── GenericSignature.cpp
├── ConformanceLookup.cpp
├── ProtocolConformance.cpp
├── SubstitutionMap.cpp
├── TypeJoinMeet.cpp
└── RequirementMachine/         # Knuth-Bendix machinery for generic signatures

Key abstractions

Type	File	Description
swift::ASTContext	include/swift/AST/ASTContext.h	Owns all AST allocations (bump allocator), the type cache, and the request evaluator. Every AST query takes an ASTContext &.
swift::Decl	include/swift/AST/Decl.h (10,399 lines)	Base of the declaration hierarchy.
swift::Type / CanType	include/swift/AST/Types.h (8,707 lines)	Type handles. Type wraps a TypeBase *; CanType adds canonicalization.
swift::Expr, Stmt, Pattern	include/swift/AST/Expr.h, etc.	Statement/expression hierarchies.
swift::ModuleDecl	include/swift/AST/Module.h	A loaded Swift module (built or imported).
swift::FileUnit	include/swift/AST/FileUnit.h	A single file inside a module (source or serialized).
swift::Evaluator	include/swift/AST/Evaluator.h	Memoizing request graph.
swift::GenericSignature	include/swift/AST/GenericSignature.h	Reduced where-clause for a generic context.
swift::ProtocolConformance	include/swift/AST/ProtocolConformance.h	A type's witness for a protocol.
swift::SubstitutionMap	include/swift/AST/SubstitutionMap.h	Mapping from generic params to concrete types.

How it works

Allocation and identity

ASTContext uses a bump allocator. AST nodes are typically immutable after construction, so identity-via-pointer is safe. Types are uniqued: requesting IntType.getCanonicalType() returns the same TypeBase * across the whole compilation.

The request evaluator

Many lazy facts about a Decl (its interface type, its overridden methods, its attributes) are computed on demand. Each fact is a request with a key (the input) and a value (the output). The evaluator memoizes each request and tracks dependencies for incremental builds (docs/RequestEvaluator.md).

graph LR
    Caller["someDecl.getInterfaceType()"]
    Caller --> Evaluator
    Evaluator --> Cache{cached?}
    Cache -->|yes| Return[return cached]
    Cache -->|no| Request[InterfaceTypeRequest]
    Request --> Compute[evaluate]
    Compute --> Cache2[store]
    Cache2 --> Return

Requests are defined throughout lib/AST/ and lib/Sema/ via the *Requests.h headers (e.g., include/swift/AST/TypeCheckRequests.h).

Generic signatures and the requirement machine

A generic signature collects the conformances and same-type constraints on a generic context. Building a signature -- e.g., reducing <T: Sequence, T.Element == Int, U: Hashable> to a canonical form -- is the job of the requirement machine in lib/AST/RequirementMachine/. It is a Knuth-Bendix-style completion procedure derived from the Compiling Swift Generics book.

The Requirement Machine replaced the older GenericSignatureBuilder and is the live system today.

AST mutation

Most AST nodes are constructed once. A few exceptions:

• Sema attaches Type to expressions during constraint solving (Expr::setType).
• The request evaluator may evict cached results when source files are mutated (incremental builds).
• SourceFile can have decls added during macro expansion.

Integration points

• Parser populates the AST (see Parser).
• Sema type-checks the AST in place, attaching types to Exprs and resolving TypeRepr to Type.
• SILGen walks the type-checked AST to emit SIL.
• Serialization writes AST nodes to .swiftmodule and reconstructs them on load.
• PrintAsClang consumes the AST to emit a C/Objective-C/C++ header.
• SymbolGraphGen consumes the AST to emit a symbol-graph JSON.
• IDE / SourceKit queries the AST for completions, jump-to-definition, refactorings.

Entry points for modification

• Adding a new declaration kind: extend the Decl hierarchy (include/swift/AST/Decl.h, lib/AST/Decl.cpp), add to DeclNodes.def, teach the parser, Sema, SILGen, serialization.
• Adding a new type kind: extend the Type hierarchy (include/swift/AST/Types.h), add to TypeNodes.def. Many places dispatch by visiting type nodes -- expect to touch ~15 files.
• Adding a new request: define it in the appropriate *Requests.h and *Requests.def, register the cache, implement the evaluator function.

Related pages

• Parser -- where AST nodes come from.
• Sema -- the largest consumer / mutator.
• Serialization -- writing and reading AST.
• SwiftCompilerSources -- has its own AST module wrapping these types.