Documentation

Lean.Elab.Tactic.BVDecide.LRAT.Trim

This module implements the LRAT trimming algorithm described in section 4 of "Faster LRAT Checking Than Solving with CaDiCaL" (https://drops.dagstuhl.de/storage/00lipics/lipics-vol271-sat2023/LIPIcs.SAT.2023.21/LIPIcs.SAT.2023.21.pdf).

source
structure Lean.Elab.Tactic.BVDecide.LRAT.trim.Context :
Type

The context used for trimming LRAT proofs.

Instances For
    source
    structure Lean.Elab.Tactic.BVDecide.LRAT.trim.State :
    Type
    • used : Lean.RBMap Nat Unit compare

      The set of used proof step ids.

    • mapped : Std.HashMap Nat Nat

      A mapping from old proof step ids to new ones. Used such that the proof remains a sequence without gaps.

    Instances For
      source
      @[reducible, inline]
      abbrev Lean.Elab.Tactic.BVDecide.LRAT.trim.M :
      Type → Type
      Instances For
        source
        partial def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.findInitialId (proof : Array Std.Tactic.BVDecide.LRAT.IntAction) (curr : Nat := 0) :
        Except String Nat
        source
        def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.findEmptyId (proof : Array Std.Tactic.BVDecide.LRAT.IntAction) :
        Except String Nat
        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          source
          def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.run {α : Type} (proof : Array Std.Tactic.BVDecide.LRAT.IntAction) (x : Lean.Elab.Tactic.BVDecide.LRAT.trim.M α) :
          Except String α
          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            source
            @[inline]
            def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.getInitialId :
            Lean.Elab.Tactic.BVDecide.LRAT.trim.M Nat
            Equations
            Instances For
              source
              @[inline]
              def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.getEmptyId :
              Lean.Elab.Tactic.BVDecide.LRAT.trim.M Nat
              Instances For
                source
                @[inline]
                def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.getProofStep (id : Nat) :
                Lean.Elab.Tactic.BVDecide.LRAT.trim.M (Option Std.Tactic.BVDecide.LRAT.IntAction)
                Instances For
                  source
                  @[inline]
                  def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.isUsed (id : Nat) :
                  Lean.Elab.Tactic.BVDecide.LRAT.trim.M Bool
                  Instances For
                    source
                    @[inline]
                    def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.markUsed (id : Nat) :
                    Lean.Elab.Tactic.BVDecide.LRAT.trim.M Unit
                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      source
                      @[inline]
                      def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.getUsedSet :
                      Lean.Elab.Tactic.BVDecide.LRAT.trim.M (Lean.RBMap Nat Unit compare)
                      Equations
                      Instances For
                        source
                        def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.registerIdMap (oldId newId : Nat) :
                        Lean.Elab.Tactic.BVDecide.LRAT.trim.M Unit
                        Instances For
                          source
                          def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.mapStep (step : Std.Tactic.BVDecide.LRAT.IntAction) :
                          Lean.Elab.Tactic.BVDecide.LRAT.trim.M Std.Tactic.BVDecide.LRAT.IntAction
                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            source
                            @[inline]
                            def Lean.Elab.Tactic.BVDecide.LRAT.trim.M.mapStep.mapIdent (ident : Nat) :
                            Lean.Elab.Tactic.BVDecide.LRAT.trim.M Nat
                            Equations
                            Instances For
                              source
                              def Lean.Elab.Tactic.BVDecide.LRAT.trim.useAnalysis :
                              Lean.Elab.Tactic.BVDecide.LRAT.trim.M Unit

                              Perform a use-def analysis of LRAT proof steps, starting at the empty clause and working its way up with DFS.

                              Equations
                              Instances For
                                source
                                partial def Lean.Elab.Tactic.BVDecide.LRAT.trim.useAnalysis.go (workList : List Nat) :
                                Lean.Elab.Tactic.BVDecide.LRAT.trim.M Unit
                                source
                                def Lean.Elab.Tactic.BVDecide.LRAT.trim.mapping :
                                Lean.Elab.Tactic.BVDecide.LRAT.trim.M (Array Std.Tactic.BVDecide.LRAT.IntAction)

                                Map the set of used proof steps to a new LRAT proof that has no holes in the sequence of proof identifiers.

                                Instances For
                                  source
                                  def Lean.Elab.Tactic.BVDecide.LRAT.trim.go :
                                  Lean.Elab.Tactic.BVDecide.LRAT.trim.M (Array Std.Tactic.BVDecide.LRAT.IntAction)
                                  Instances For
                                    source
                                    def Lean.Elab.Tactic.BVDecide.LRAT.trim (proof : Array Std.Tactic.BVDecide.LRAT.IntAction) :
                                    Except String (Array Std.Tactic.BVDecide.LRAT.IntAction)

                                    Trim the LRAT proof by removing all steps that are not used in reaching the empty clause conclusion.

                                    Equations
                                    Instances For