Documentation

Lean.ConstTrie

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.

inductive Lean.ConstTrie (α : Type) :

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.

Instances For
    @[inline]
    Equations
    Instances For
      @[inline]
      Equations
      Instances For
        @[inline]
        Equations
        Instances For
          def Lean.ConstTrie.mk {α : Type} (key : Name) (val? : Option α) (children : Array (ConstTrie α)) :

          Creates a node of the appropriate shape; children must be sorted by key hash.

          Equations
          Instances For
            def Lean.ConstTrie.find? {α : Type} (t : ConstTrie α) (n : Name) :
            Equations
            Instances For
              @[irreducible]
              def Lean.ConstTrie.foldlM {m : Type u_1 → Type u_2} {α : Type} {σ : Type u_1} [Monad m] (t : ConstTrie α) (f : σ → Name → α → m σ) (init : σ) :
              m σ
              Equations
              Instances For
                def Lean.ConstTrie.ofArrays {α : Type} (names : Array Name) (vals : Array α) :

                Creates a trie mapping names[i] to vals[i]; of duplicate names, the last occurrence wins.

                Equations
                Instances For

                  Creates a trie containing names as keys.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  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
                      @[extern lean_imported_consts_cache_new]
                      inductive Lean.ImportedTree (α : Type) :

                      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.

                      Instances For
                        structure Lean.ImportedConsts (α : Type) :

                        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.

                        Instances For
                          @[instance_reducible]
                          Equations

                          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
                            Instances For
                              @[inline]

                              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
                                @[inline]

                                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
                                  Equations
                                  Instances For

                                    A constant name declared by more than one module; see collectDuplicates.

                                    • name : Name
                                    • entries : Array (α × Nat)

                                      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
                                      Instances For
                                        def Lean.ImportedConsts.mergeModuleTreesLazy {α : Type} (trees : Array (Nat × ConstTrie α)) (resolve : Array (α × Nat) → Option (α × Nat) := fun (x : Array (α × Nat)) => x[0]?) :

                                        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
                                        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.

                                          Equations
                                          Instances For
                                            def Lean.ImportedConsts.foldlM {m : Type u_1 → Type u_2} {α : Type} {σ : Type u_1} [Monad m] (t : ImportedConsts α) (f : σ → Name → α → m σ) (init : σ) :
                                            m σ
                                            Equations
                                            Instances For
                                              def Lean.ImportedConsts.foldl {α : Type} {σ : Type u_1} (t : ImportedConsts α) (f : σ → Name → α → σ) (init : σ) :
                                              σ
                                              Equations
                                              Instances For
                                                def Lean.ImportedConsts.foldlEntriesM {m : Type u_1 → Type u_2} {α : Type} {σ : Type u_1} [Monad m] (t : ImportedConsts α) (f : σ → Name → α × Nat → m σ) (init : σ) :
                                                m σ

                                                Like foldlM, but also passing the index of the first module declaring each name.

                                                Equations
                                                Instances For
                                                  def Lean.ImportedConsts.forM {m : Type u_1 → Type u_2} {α : Type} [Monad m] (t : ImportedConsts α) (f : Name → α → m PUnit) :
                                                  Equations
                                                  Instances For
                                                    Equations
                                                    Instances For
                                                      def Lean.ImportedConsts.fold {α : Type} {σ : Type u_1} (t : ImportedConsts α) (f : σ → Name → α → σ) (init : σ) :
                                                      σ
                                                      Equations
                                                      Instances For
                                                        def Lean.ImportedConsts.foldM {m : Type u_1 → Type u_2} {α : Type} {σ : Type u_1} [Monad m] (t : ImportedConsts α) (f : σ → Name → α → m σ) (init : σ) :
                                                        m σ
                                                        Equations
                                                        Instances For
                                                          Equations
                                                          Instances For
                                                            Equations
                                                            Instances For
                                                              @[instance_reducible]
                                                              Equations
                                                              • One or more equations did not get rendered due to their size.
                                                              @[instance_reducible]
                                                              instance Lean.ImportedConsts.instForMProdNameOfMonad {m : Type u_1 → Type u_2} {α : Type} [Monad m] :
                                                              Equations
                                                              @[instance_reducible]
                                                              instance Lean.ImportedConsts.instForInProdNameOfMonad {m : Type u_1 → Type u_2} {α : Type} [Monad m] :
                                                              Equations