Documentation

Mathlib.Lean.Meta.RefinedDiscrTree.Basic

Basic Definitions for RefinedDiscrTree #

We define

Discrimination tree key.

  • star : Key

    A metavariable. This key matches with anything.

  • labelledStar (id : Nat) : Key

    A metavariable. This key matches with anything. It stores an identifier.

  • opaque : Key

    An opaque variable. This key only matches with Key.star.

  • const (declName : Name) (nargs : Nat) : Key

    A constant. It stores the name and the arity.

  • fvar (fvarId : FVarId) (nargs : Nat) : Key

    A free variable. It stores the FVarId and the arity.

  • bvar (deBruijnIndex nargs : Nat) : Key

    A bound variable, from a lambda or forall binder. It stores the De Bruijn index and the arity.

  • lit (v : Literal) : Key

    A literal.

  • sort : Key

    A sort. Universe levels are ignored.

  • lam : Key

    A lambda function.

  • forall : Key

    A dependent arrow.

  • proj (typeName : Name) (idx nargs : Nat) : Key

    A projection. It stores the structure name, the projection index and the arity.

Instances For
    Equations
    Instances For

      Converts an entry (i.e., List Key) to the discrimination tree into MessageData that is more user-friendly.

      This is a copy of Lean.Meta.DiscrTree.keysAsPattern

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For

        Get the next key.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For

          Format the application f args.

          Format the next expression.

          Add parentheses if paren == true.

          Equations
          Instances For

            Return the number of arguments that the Key takes.

            Equations
            Instances For

              The information for computing the keys of a subexpression.

              • expr : Expr

                The expression

              • bvars : List FVarId

                Variables that come from a lambda or forall binder. The list index gives the De Bruijn index.

              • The local context, which contains the introduced bound variables.

              • localInsts : LocalInstances

                The local instances, which may contain the introduced bound variables.

              • cfg : Config

                The Meta.Config used by this entry.

              Instances For

                Creates an ExprInfo using the current context.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For

                  The possible values that can appear in the stack

                  Instances For

                    A LazyEntry represents a snapshot of the computation of encoding an Expr as Array Key. This is used for computing the keys one by one.

                    • previous : Option ExprInfo

                      If an expression creates more entries in the stack, for example because it is an application, then instead of pushing to the stack greedily, we only extend the stack once we need to. So, the field previous is used to extend the stack before looking in the stack.

                      For example in 10.add (20.add 30), after computing the key ⟨Nat.add, 2⟩, the stack is still empty, and previous will be 10.add (20.add 30).

                    • The stack, used to emulate recursion. It contains the list of all expressions for which the keys still need to be computed, in that order.

                      For example in 10.add (20.add 30), after computing the keys ⟨Nat.add, 2⟩ and 10, the stack will be a list of length 1 containing the expression 20.add 30.

                    • The metavariable context, which may contain variables appearing in this entry.

                    • labelledStars? : Option (Array MVarId)

                      MVarIds corresponding to the .labelledStar labels. The index in the array is the label. It is none if we use .star instead of labelledStar, for example when encoding the lookup expression.

                    • computedKeys : List Key

                      The Keys that have already been computed.

                      Sometimes, more than one Key ends up being computed in one go. This happens when there are lambda binders (because it depends on the body whether the lambda key should be indexed or not). In that case the remaining Keys are stored in results.

                    Instances For

                      Creates a LazyEntry using the current metavariable context.

                      Equations
                      Instances For
                        @[reducible, inline]

                        Array index of a Trie α in the tries of a RefinedDiscrTree.

                        Equations
                        Instances For

                          Discrimination tree trie. See RefinedDiscrTree.

                          A Trie will normally have exactly one of the following

                          • nonempty values
                          • nonempty stars, labelledStars and/or children
                          • nonempty pending But defining it as a structure that can have all at the same time turns out to be easier.
                          Instances For
                            Equations

                            Lazy refined discrimination tree. It is an index from expressions to values of type α.

                            We store all of the nodes in one Array, tries, instead of using a 'normal' inductive type. This is so that we can modify the tree globally, which is very useful when evaluating lazy entries and saving the result globally.

                            Instances For