Prefix trees over constant names, stored per module in its olean parts and merged at import time.
Each olean part carries a prefix tree over its constant names whose nodes live in the memory-mapped
compacted region. finalizeImport merges the per-module trees into an ImportedConsts on
demand, allocating fresh nodes only for name prefixes that occur in more than one module and
sharing all single-module subtrees directly with the olean regions.
A prefix tree over the constant names of a single module, keyed on name components. key is the
full name prefix represented by a node. children is sorted by the (cached) hash of the child keys
and searched by binary search; as all children extend key by one component, comparing that final
component suffices to disambiguate equal hashes. Nodes are split by shape so that leaves and
value-less nodes store no unused fields.
- leaf {α : Type} (key : Name) (val : α) : ConstTrie α
- inner {α : Type} (key : Name) (children : Array (ConstTrie α)) : ConstTrie α
- node {α : Type} (key : Name) (val : α) (children : Array (ConstTrie α)) : ConstTrie α
Instances For
Equations
Equations
- (Lean.ConstTrie.leaf k val).key = k
- (Lean.ConstTrie.inner k children).key = k
- (Lean.ConstTrie.node k val children).key = k
Instances For
Equations
- (Lean.ConstTrie.leaf key v).val? = some v
- (Lean.ConstTrie.node key v children).val? = some v
- (Lean.ConstTrie.inner key children).val? = none
Instances For
Equations
- (Lean.ConstTrie.leaf k val).children = #[]
- (Lean.ConstTrie.inner k children).children = children
- (Lean.ConstTrie.node k val children).children = children
Instances For
Creates a node of the appropriate shape; children must be sorted by key hash.
Equations
- Lean.ConstTrie.mk key (some v) children = Lean.ConstTrie.leaf key v
- Lean.ConstTrie.mk key (some v) children = Lean.ConstTrie.node key v children
- Lean.ConstTrie.mk key none children = Lean.ConstTrie.inner key children
Instances For
Equations
- t.find? n = have path := Lean.prefixesOf✝ n; Lean.ConstTrie.findAux✝ t path path.size
Instances For
Equations
- (Lean.ConstTrie.leaf k val).foldlM f init = f init k val
- (Lean.ConstTrie.inner k children).foldlM f init = Array.foldlM (fun (s : σ) (c : Lean.ConstTrie α) => c.foldlM f s) init children
- (Lean.ConstTrie.node k val children).foldlM f init = do let __do_lift ← f init k val Array.foldlM (fun (s : σ) (c : Lean.ConstTrie α) => c.foldlM f s) __do_lift children
Instances For
Creates a trie mapping names[i] to vals[i]; of duplicate names, the last occurrence wins.
Equations
- Lean.ConstTrie.ofArrays names vals = Lean.ConstTrie.Builder.toTrie✝ (Lean.ConstTrie.ofArrays.go✝ names vals 0 { }) Lean.Name.anonymous (Lean.ConstTrie.depthBound✝ names)
Instances For
A lock-free cache for lookups in one ImportedConsts, implemented in C++
(src/library/const_cache.cpp) and freed together with it.
Equations
Instances For
Merged per-module constant prefix trees of all imported modules. Node keys and lookup work like in
ConstTrie; subtrees whose prefix occurs in only a single module are borrowed directly from that
module's (usually region-resident) tree.
- mod {α : Type} (modIdx : Nat) (tree : ConstTrie α) : ImportedTree α
A subtree containing entries of only a single module: the module's own tree.
- merged {α : Type} (key : Name) (entry? : Option (α × Nat)) (children : Array (ImportedTree α)) : ImportedTree α
A node whose prefix occurs in several modules, allocated at import time.
entry?holds the value together with the index of the first module declaring it. - lazy {α : Type} (key : Name) (entry? : Option (α × Nat)) (children : Thunk (Array (ImportedTree α))) : ImportedTree α
Like
merged, but with the children computed on first access from the candidate subtrees sharing the prefix, one level at a time (seeImportedConsts.mergeModuleTreesLazy).
Instances For
Equations
The merged constants of all imported modules, owning the cache used by findConstEntryCached?
and findExtraEntryCached? (see withCache). Lookups in an ImportedConsts without a cache
are cached in a process-global table instead, which keeps it alive.
- cache? : Option LookupCache
- tree : ImportedTree α
Instances For
Equations
Instances For
Gives t a fresh lookup cache, freed together with the result. The cache is an external object, so
the result cannot be compacted, e.g. into an incremental snapshot.
Equations
Instances For
Finds the value for n together with the index of the first module declaring it.
Equations
- t.findEntry? n = have path := Lean.prefixesOf✝ n; Lean.ImportedTree.findEntryAux✝ t.tree path path.size
Instances For
findEntry? for importedExtraConsts, memoized in a lock-free cache: the one owned by t, or
else a process-global one; sound because t is immutable per import set.
Equations
Instances For
findEntry? for importedExtraConsts, memoized in a lock-free cache: the one owned by t, or
else a process-global one; sound because t is immutable per import set.
Equations
- t.findExtraModIdxCached? n = match Lean.ImportedConsts.findExtraModIdxCachedImpl✝ t.cache? t n with | 0 => none | i.succ => some i
Instances For
Equations
- t.find? n = have path := Lean.prefixesOf✝ n; Lean.ImportedTree.findValAux✝ t.tree path path.size
Instances For
A constant name declared by more than one module; see collectDuplicates.
- name : Name
The declared values with their module indices, in module order.
Instances For
Collects the names declared by more than one of the given modules, with their declarations in module
order, without building an ImportedConsts: only name prefixes occurring in several modules are
walked. covered optionally gives each module a bitmask of covering direct imports; subtrees whose
modules share a mask bit are skipped, as their pairs are conflict-checked already (see
checkImportConflicts).
Equations
- Lean.ImportedConsts.collectDuplicates trees covered = if trees.size < 2 then #[] else Lean.ImportedConsts.collectDupsAux✝ covered Lean.Name.anonymous trees #[]
Instances For
Merges per-module trees, given in module order, into a single tree, merging each node's entry and
children on first access. Only name prefixes occurring in more than one module get fresh nodes;
single-module subtrees are shared with the given trees. resolve picks the entry stored for a name
declared by several modules from the candidate entries, given in module order. Conflicting
declarations must have been ruled out beforehand, e.g. using collectDuplicates.
Equations
- Lean.ImportedConsts.mergeModuleTreesLazy trees resolve = { tree := Lean.ImportedConsts.mergeLazy✝ resolve Lean.Name.anonymous trees }
Instances For
Replaces the node for n using f. n must be a prefix shared by several modules, such as a
Duplicate name; single-module subtrees are never modified. The result has no cache of its own.
Instances For
Equations
- t.foldlM f init = Lean.ImportedTree.foldlM✝ t.tree f init
Instances For
Instances For
Like foldlM, but also passing the index of the first module declaring each name.
Equations
- t.foldlEntriesM f init = Lean.ImportedTree.foldlEntriesM✝ t.tree f init
Instances For
Instances For
Equations
- One or more equations did not get rendered due to their size.
Equations
- Lean.ImportedConsts.instForInProdNameOfMonad = { forIn := fun {β : Type ?u.2} => ForM.forIn }