Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Pre-solve equality constraints to reduce number of constraint variables hitting back end solvers #205

Open
jyluo opened this issue Jan 21, 2019 · 0 comments

Comments

@jyluo
Copy link

jyluo commented Jan 21, 2019

Across all of the type systems supported, we typically have equality constraints expressed between constant slots and variable slots, which can be pre-solved to reduced the number of constraint variables and constraints in the system, and which are then encoded into SAT or SMT formulas.

Enabling this requires slots in constraints to be replaceable (always from a variable slot to a constant slot) in this pre-solving phase, eg:

original constraints

@9 == @Top
@8 <: @9

slot solution after solving equalities:

@9 := @Top 

constraints after solving equalities:

@8 <: @Top

Rough algo:

For eqc in equality constraints
   if eqc is between a constant slot CS and a variable slot V
      update V's solution  V := CS
      delete eqc from constraint set
      for c in all constraints
         if c is expressed over V, replace V in c with CS
         check to see if updated c is unsat, if so, generate error warning
         check to see if updated c is always sat, if so, delete c from constraint set
until fixpoint

Should be O(n^2) relative to number of constraints.

Details:

  1. if unsat, a minimal unsat core needs to be generated (by back-propagating from the unsat constraint and looking up all involved slots)

  2. Constraints are currently hashed on their component slots, this may need to change to ensure that a constraint with an updated slot does not collide with another constraint already present in the constraint set.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant