def Lean.Meta.Grind.Arith.Cutsat.getBestLower? (x : Var) : GoalM (Option (Rat × LeCnstr))

Assuming all variables smaller than x have already been assigned, returns the best lower bound for x using the given partial assignment and inequality constraints where x is the maximal variable.

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.getBestUpper? (x : Var) : GoalM (Option (Rat × LeCnstr))

Assuming all variables smaller than x have already been assigned, returns the best upper bound for x using the given partial assignment and inequality constraints where x is the maximal variable.

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.getDiseqValues (x : Var) : SearchM (Array (Rat × DiseqCnstr))

Returns values we cannot assign x because of disequality constraints.

Equations

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

structure Lean.Meta.Grind.Arith.Cutsat.DvdSolution : Type

Solution space for a divisibility constraint of the form d ∣ a*x + b See DvdCnstr.getSolutions? to understand how it is computed.

• d : Int
• b : Int

def Lean.Meta.Grind.Arith.Cutsat.DvdCnstr.getSolutions? (c : DvdCnstr) : SearchM (Option DvdSolution)

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveDvdConflict (c : DvdCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.DvdSolution.ge (s : DvdSolution) (v : Int) : Int

Given a divisibility constraint solution space s := { b, d }, and a candidate assignment v, we want to find an assignment w such that w ≥ v such that exists k, w = k*d + b Thus,

• k*d + b ≥ v
• k ≥ cdiv (v - b) d So, we take w = (cdiv (v - b) d)*d + b

Equations

• s.ge v = Int.Linear.cdiv (v - s.b) s.d * s.d + s.b

def Lean.Meta.Grind.Arith.Cutsat.DvdSolution.le (s : DvdSolution) (v : Int) : Int

Given a divisibility constraint solution space s := { b, d }, and a candidate assignment v, we want to find an assignment w such that w ≤ v such that exists k, w = k*d + b Thus,

• k*d + b ≤ v
• k ≤ (v - b) / d So, we take w = ((v - b) / d)*d + b

Equations

• s.le v = (v - s.b) / s.d * s.d + s.b

def Lean.Meta.Grind.Arith.Cutsat.findDiseq? (v : Int) (dvals : Array (Rat × DiseqCnstr)) : Option DiseqCnstr

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.inDiseqValues (v : Int) (dvals : Array (Rat × DiseqCnstr)) : Bool

Equations

• Lean.Meta.Grind.Arith.Cutsat.inDiseqValues v dvals = (Lean.Meta.Grind.Arith.Cutsat.findDiseq? v dvals).isSome

def Lean.Meta.Grind.Arith.Cutsat.findRatDiseq? (v : Rat) (dvals : Array (Rat × DiseqCnstr)) : Option DiseqCnstr

Equations

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

partial def Lean.Meta.Grind.Arith.Cutsat.DvdSolution.geAvoiding (s : DvdSolution) (v : Int) (dvals : Array (Rat × DiseqCnstr)) : Int

def Lean.Meta.Grind.Arith.Cutsat.DvdSolution.leAvoiding (s : DvdSolution) (v : Int) (dvals : Array (Rat × DiseqCnstr)) : Int

Equations

• s.leAvoiding v dvals = if Lean.Meta.Grind.Arith.Cutsat.inDiseqValues (s.le v) dvals = true then s.geAvoiding (s.le v - 1) dvals else s.le v

inductive Lean.Meta.Grind.Arith.Cutsat.FindIntValResult : Type

• found (val : Int) : FindIntValResult
• diseq (c : DiseqCnstr) : FindIntValResult
• dvd : FindIntValResult

instance Lean.Meta.Grind.Arith.Cutsat.instInhabitedFindIntValResult : Inhabited FindIntValResult

Equations

• Lean.Meta.Grind.Arith.Cutsat.instInhabitedFindIntValResult = { default := Lean.Meta.Grind.Arith.Cutsat.FindIntValResult.found default }

def Lean.Meta.Grind.Arith.Cutsat.findIntVal (s : DvdSolution) (lower upper : Int) (dvals : Array (Rat × DiseqCnstr)) : FindIntValResult

Tries to find an integer v s.t. lower ≤ v ≤ upper, v ∉ dvals, and v ∈ s. Returns .found v if result was found, .dvd if it failed because of the divisibility constraint, and .diseq c because of the disequality constraint c.

Equations

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

partial def Lean.Meta.Grind.Arith.Cutsat.findIntVal.go (s : DvdSolution) (upper : Int) (dvals : Array (Rat × DiseqCnstr)) (v : Int) : FindIntValResult

partial def Lean.Meta.Grind.Arith.Cutsat.findRatVal (lower upper : Rat) (diseqVals : Array (Rat × DiseqCnstr)) : Rat

def Lean.Meta.Grind.Arith.Cutsat.resolveRealLowerUpperConflict (c₁ c₂ : LeCnstr) : GoalM Bool

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperLeft (c₁ c₂ : LeCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperRight (c₁ c₂ : LeCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooper (c₁ c₂ : LeCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperDvdLeft (c₁ c₂ : LeCnstr) (c : DvdCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperDvdRight (c₁ c₂ : LeCnstr) (c : DvdCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperDvd (c₁ c₂ : LeCnstr) (c : DvdCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveCooperDiseq (c₁ : DiseqCnstr) (c₂ : LeCnstr) (_c? : Option DvdCnstr) : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveRatDiseq (c₁ : LeCnstr) (c : DiseqCnstr) : SearchM Unit

Given c₁ of the form -a₁*x + p₁ ≤ 0, and c of the form b*x + p ≠ 0, splits c and resolve with c₁. Recall that a disequality

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.processVar (x : Var) : SearchM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.hasAssignment : GoalM Bool

Returns true if we already have a complete assignment / model.

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.resolveConflict (h : UnsatProof) : SearchM Bool

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.searchAssigmentMain : SearchM Unit

Search for an assignment/model for the linear constraints.

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.traceModel : GoalM Unit

Equations

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

def Lean.Meta.Grind.Arith.Cutsat.searchAssigment : GoalM Unit

Equations

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