Skip to main content

Name Resolution Cheatsheet

The Name Resolution stage is not that difficult stage of compilation, anyway tricky one. Here I tried to collect workflows for different resolution cases and connections between them.

Okay, what classes do we have:

  • ModuleTreeBuilder - by the name you can see that this one builds a module tree.
  • Importer - this one resolves use declarations and imports new items to the module tree.
  • NameResolver - resolves names, that is, binds each usage to the definition.
  • PathResolver - helper class that unifies path resolution logic for all name resolution sub-stages.
  • DefTable - common definitions info storage

Basic structures

Symbol

Identifies interned string, read more about symbols here

Namespace

An enumeration of namespaces. Each namespace is a separate storage for definitions, thus type names do not collide with value names, etc. There is one special variant - Namespace::Any, it is not used in definition storages and mappings, by the way, is used in methods, e.g. to collect definitions with the same name from all namespaces. Never store Namespace::Any in DefTable, only use it as a helper.

Def

Definition structure, holds DefKind and DefId. You can access particular definition via DefTable::getDef or get all, defined, using DefTable::getDefinitions

DefId & DefIndex

DefIndex is a simple index type, i.e. integer wrapper to create a distinct integer type (C++ does not support it). DefId is a unique definition identifier, currently, it only holds DefIndex but might be extended in the future.

DefId::index is the index of vector from DefTable::defs. You can get particular definition by DefId or DefIndex from DefTable via getDef.

ROOT_DEF_ID

The constant for root module definition, used in many places for validations and logic checks.

DefKind

Enumeration of definitions kinds. Each kind has some properties, e.g. namespace where it will be defined. You can get DefKind from Def structure if you have one on hand.

To find out in which namespace specific DefKind must be defined call Def::getDefKindNS.

Vis

Visibility enumeration, for now only Vis::Unset and Vis::Pub exist.

PerNS<T>

A helper template structure that stores a value of some type for each namespace.

PrimTypeSet

Bits-optimized collection of primitive types flags. It can be used to mark specific primitive types used/shadowed, etc. Used by the module to save shadowed primitive types.

Module

The Module is a single node of the Module Tree. Fields:

  • kind - Kind of module, i.e. Def (named module bound to some definition) or Block (anonymous module). Type is the ModuleKind enumeration.
  • id - Identifier of module - either DefId (for ModuleKind::Def) or NodeId (for ModuleKind::Block).
  • parent - Optional parent that is another module (only root module does not have a parent).
  • nearestModDef - Nearest definition of a kind DefKind::Mod, always present. For modules which are DefKind::Mod by themselves nearestModDef point to the same modules (root module is also of a kind DefKind, thus nearestModDef of root module is the same as ROOT_DEF_ID).
  • perNS - PerNS<map<Symbol, [NameBinding](#namebinding)>>. A per-namespace collection of mappings Symbol (some name) -> DefId (some definition).
  • shadowedPrimTypes - module PrimTypeSet, i.e. flags showing which primitive types (e.g. int, f32) are shadowed in the module.

NameBinding

The Module binds names either to FOS or to some definition. This is why NameBinding exists, it is an ADT for FOS and DefId.

FOSId

FOS stands for "Function Overload Set". In Jacy you can overload functions via different label names, i.e. not by types but func foo(from: int) and func foo(to: int) can exist together.

FOSId is a unique identifier for one FOS -- a collection of functions with the same name, defined in the same module.

For example, in:

mod m {
    func foo(from: int) {}

    func foo(to: int) {}
}

mod m only holds NameBinding with name foo (base name of FOS) which points to FOSId of FOS foo in DefTable. To access a specific function, at first, you need to get FOSId from the module and then go to the DefTable to search for a suffix.

Function suffix is an interned string such as (from:) or (to:), i.e. function label list.

DefTable

DefTable holds all data, we need, about definitions and relations between them.

Fields, Storages

Direct storage mark means that this field is the final storage, i.e. it is not a mapping and other items map to it, Indirect storage is an opposite.

  • defs - vector<Def> - Direct storage - Definition collection, DefIndex points to index in defs.
  • modules - DefMap<Module::Ptr> - Direct storage - Maps definitions to modules -- Named modules. Used everywhere, filled in the ModuleTreeBuilder.
  • blocks - NodeMap<Module::Ptr> - Direct storage - Maps block nodes to modules -- Anonymous modules. Used everywhere, filled in the ModuleTreeBuilder.
  • useDeclModules - NodeMap<Module::Ptr> - Indirect storage - Maps node id of use item to module it defined it. Used by Importer, filled in the ModuleTreeBuilder.
  • defVisMap - DefMap<Vis> - Maps definition to its visibility.
  • nodeIdDefIdMap - - Maps definition node id to its DefId.
  • defIdNodeIdMap - Maps DefId to definition node id.
  • importAliases - Maps DefId of import alias, i.e. definition appeared from use declaration to another definition (that also might be an import alias).

Basic API

This API is almost a list of helpers to retrieve items from the fields described above.

  • Working with definitions:

    • getDef(DefId/DefIndex) -> Def - get definition by DefId or DefIndex.
    • getDefUnwind(DefId) -> Def - get definition unwinding aliases (if definition is an ImportAlias).
    • getDefVis(DefId) -> Vis - get definition visibility.
    • getNodeIdByDefId(DefId) -> NodeId - get node id of definition node by definition id.
    • getDefIdByNodeId(NodeId) -> DefId - get definition id by node id.
    • getDefNameSpan(DefId) -> Span - get span of definition identifier (e.g. in func foo() {} it returns span for foo).

  • Working with modules:

    • getModule(DefId) -> Module::Ptr - get module by definition id.
    • getBlock(NodeId) -> Module::Ptr - get block (anonymous module) by node id.
    • getFuncModule(FOSId, Symbol) -> Module::Ptr - get function module by FOSId and specific suffix, together they non-ambiguously specify some function.
    • addModule(DefId, Module::Ptr) - Add named module, binding it by DefId.
    • addBlock(NodeId, Module::Ptr) - Add block (anonymous module), binding it by NodeId.