|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object jif.types.AbstractSolver
public abstract class AbstractSolver
A solver of Jif constraints. Finds solution to constraints essentially by propagating upper bounds backwards.
Nested Class Summary | |
---|---|
protected static class |
AbstractSolver.EquationQueue
A queue for equations. |
protected class |
AbstractSolver.Frame
|
Field Summary | |
---|---|
protected VarMap |
bounds
|
protected polyglot.frontend.Compiler |
compiler
|
protected static int |
constraint_counter
Counter of the number of constraints added to the system. |
protected java.util.Set |
currentSCC
|
protected java.util.Collection |
equations
|
protected java.util.Set |
fixedValueVars
Set of Variables that had their initial value fixed when the constraint was added. |
protected AbstractSolver.EquationQueue |
Q
|
protected java.util.LinkedList |
scc
|
protected static int |
solverCounter
Number of solvers instantiated, for debugging purposes |
protected java.util.Set |
staticFailedConstraints
Constraints that were added to the solver, and failed statically. |
protected int |
status
|
protected static int |
STATUS_NO_SOLUTION
|
protected static int |
STATUS_NOT_SOLVED
|
protected static int |
STATUS_SOLVED
|
protected static int |
STATUS_SOLVING
|
protected static boolean |
THROW_STATIC_FAILED_CONSTRAINTS
|
protected static java.util.Collection |
topics
|
protected java.util.Map |
traces
|
protected JifTypeSystem |
ts
|
protected boolean |
useSCC
This boolean is used to turn on or off whether the strongly connected components optimization is used. |
Constructor Summary | |
---|---|
protected |
AbstractSolver(AbstractSolver js)
Constructor |
protected |
AbstractSolver(JifTypeSystem ts,
polyglot.frontend.Compiler compiler,
java.lang.String solverName)
Constructor |
protected |
AbstractSolver(JifTypeSystem ts,
polyglot.frontend.Compiler compiler,
java.lang.String solverName,
boolean useSCC)
Constructor |
Method Summary | |
---|---|
void |
addConstraint(Constraint c)
Add the constraint c to the system |
protected void |
addConstraintEquations(Constraint c)
Go through each equation in the constraint, add the equation if needed, and register dependencies for the equation. |
protected abstract void |
addDependencies(Equation eqn)
This abstract method must add the correct dependencies from Equation eqn to variables occurring in eqn, and dependencies in the other direction (that is, from variables occurring in eqn to eqn). |
protected void |
addDependency(Equation eqn,
Variable var)
This method records a dependency from Equation eqn to variable var. |
protected void |
addDependency(Variable var,
Equation eqn)
This method records a dependency from variable var to Equation eqn. |
protected void |
addEquationToQueue(Equation eqn)
|
protected void |
addEquationToQueueHead(Equation eqn)
|
protected void |
addTrace(VarLabel v,
Equation eqn,
Label lb)
Record the fact that label variable v, in the constraint eqn had its bound set to the label lb. |
Label |
applyBoundsTo(Label L)
Substitute variables in L with the solution for the variables. |
VarMap |
bounds()
Get the bounds for this Solver. |
protected void |
checkCandidateSolution()
Check the candidate solution |
protected void |
checkEquationSatisfied(LabelEquation eqn)
|
protected void |
considerEquation(Equation eqn)
|
protected void |
considerEquation(LabelEquation eqn)
|
protected void |
considerEquation(PrincipalEquation eqn)
|
protected java.util.Set |
eqnEqnDependencies(Equation eqn)
Returns the equations that are dependent on the equation eqn by finding the variables that eqn may alter if it is solved (useing the map eqnVarDependencies), and then finds the equations that depend on those variables (using the map varEqnDependencies) |
protected java.util.Set |
eqnEqnReverseDependencies(Equation eqn)
Returns the equations that are reverse dependent on the equation eqn by finding the variables that may invalidate eqn (using the map eqnVarReverseDependencies), and then finding the equations that may alter those variables (using the map varEqnReverseDependencies) |
protected java.lang.String |
errorMsg(Constraint c)
Produce an error message for the constraint c, which cannot be satisfied. |
protected boolean |
errorShowConstraint()
|
protected boolean |
errorShowDefns()
|
protected boolean |
errorShowDetailMsg()
|
protected boolean |
errorShowTechnicalMsg()
|
protected java.lang.String |
errorStringConstraint(Constraint c)
Produce a string appropriate for an error message that displays the unsatisfiable constraint c . |
protected java.lang.String |
errorStringDefns(LabelConstraint c)
Produce a string appropriate for an error message that displays the definitions needed by the unsatisfiable constraint c . |
protected Equation |
findContradictiveEqn(Constraint c)
|
protected abstract Equation |
findContradictiveEqn(LabelConstraint c)
|
protected java.util.LinkedList |
findSCCs()
Returns the linked list [by_scc, scc_head] where by_scc is an array in which SCCs occur in topologically order. |
protected Equation |
findTrace(VarLabel var,
Label threshold,
boolean lowerThreshold)
|
protected abstract Label |
getDefaultLabelBound()
This method must return a constant label, which is the default bound of label variables. |
protected abstract Principal |
getDefaultPrincipalBound()
This method must return a constant principal, which is the default bound of principal variables. |
protected java.util.List |
getQueue()
|
protected void |
inc_counter()
Increase the count of the number of constraints added (not just to this system, but to all instances of the Solver). |
protected boolean |
isFixedValueVar(Variable v)
|
protected void |
processConstraint(Constraint c)
Perform any special processing for the label constraint |
static void |
report(int level,
java.lang.String s)
Convenience method to report messages for the appropriate topics |
protected void |
reportError(Constraint c,
java.util.Collection variables)
Throws a SemanticException with the appropriate error message. |
protected void |
reportTraces(java.util.Collection variables)
Report the traces for each variables in the collection Variables |
void |
setBound(VarLabel v,
Label newBound,
LabelConstraint responsible)
|
void |
setBound(VarPrincipal v,
Principal newBound,
PrincipalConstraint responsible)
|
void |
setBounds(VarMap bnds)
Set the bounds for this Solver. |
protected void |
setStatus(int status)
|
static boolean |
shouldReport(int obscurity)
Convenience method to determine if messages of the given obscurity should be reported. |
protected VarMap |
solve_bounds()
Solve the system of constraints, by finding upper bounds for the label variables. |
protected abstract void |
solve_eqn(LabelEquation eqn)
This method changes the bounds of variables in the Equation eqn, to make the equation satisfied. |
protected abstract void |
solve_eqn(PrincipalEquation eqn)
This method changes the bounds of variables in the Equation eqn, to make the equation satisfied. |
VarMap |
solve()
Solve the system of constraints. |
java.lang.String |
solverName()
|
protected Label |
triggerTransforms(Label label,
LabelEnv env)
|
protected void |
wakeUp(Variable v)
Awakens all equations in the system that depend on the variable v, ensuring that they are in the queue of active equations. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected AbstractSolver.EquationQueue Q
protected java.util.LinkedList scc
protected java.util.Set currentSCC
protected java.util.Collection equations
protected java.util.Set fixedValueVars
protected static final int STATUS_NOT_SOLVED
protected static final int STATUS_SOLVING
protected static final int STATUS_SOLVED
protected static final int STATUS_NO_SOLUTION
protected int status
protected VarMap bounds
protected JifTypeSystem ts
protected java.util.Set staticFailedConstraints
protected static final boolean THROW_STATIC_FAILED_CONSTRAINTS
protected final polyglot.frontend.Compiler compiler
protected java.util.Map traces
protected static java.util.Collection topics
protected final boolean useSCC
protected static int solverCounter
protected static int constraint_counter
Constructor Detail |
---|
protected AbstractSolver(JifTypeSystem ts, polyglot.frontend.Compiler compiler, java.lang.String solverName)
protected AbstractSolver(JifTypeSystem ts, polyglot.frontend.Compiler compiler, java.lang.String solverName, boolean useSCC)
protected AbstractSolver(AbstractSolver js)
Method Detail |
---|
public static final void report(int level, java.lang.String s)
public static final boolean shouldReport(int obscurity)
public Label applyBoundsTo(Label L)
Solver
applyBoundsTo
in interface Solver
protected Label triggerTransforms(Label label, LabelEnv env)
protected java.util.List getQueue()
protected void addEquationToQueue(Equation eqn)
protected void addEquationToQueueHead(Equation eqn)
public VarMap bounds()
public void setBounds(VarMap bnds)
public void setBound(VarLabel v, Label newBound, LabelConstraint responsible) throws polyglot.types.SemanticException
v
- the VarLabel to set the bound fornewBound
- the new bound for vresponsible
- the constraint that was responsible for modifying the
bound.
polyglot.types.SemanticException
- if the new bound violates an equality
constraint.public void setBound(VarPrincipal v, Principal newBound, PrincipalConstraint responsible) throws polyglot.types.SemanticException
polyglot.types.SemanticException
public VarMap solve() throws polyglot.types.SemanticException
solve
in interface Solver
polyglot.types.SemanticException
- if the Solver cannot find a solution to the
system of contraints.protected void setStatus(int status)
protected abstract Label getDefaultLabelBound()
protected abstract Principal getDefaultPrincipalBound()
protected VarMap solve_bounds() throws polyglot.types.SemanticException
polyglot.types.SemanticException
- if the Solver cannot find a solution to the
system of constraints.protected void considerEquation(Equation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected void considerEquation(LabelEquation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected abstract void solve_eqn(LabelEquation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected void considerEquation(PrincipalEquation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected abstract void solve_eqn(PrincipalEquation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected final void checkCandidateSolution() throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected void checkEquationSatisfied(LabelEquation eqn) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected final void wakeUp(Variable v)
public java.lang.String solverName()
protected final void inc_counter()
protected boolean isFixedValueVar(Variable v)
public void addConstraint(Constraint c) throws polyglot.types.SemanticException
addConstraint
in interface Solver
polyglot.types.SemanticException
protected void processConstraint(Constraint c) throws polyglot.types.SemanticException
polyglot.types.SemanticException
protected void addConstraintEquations(Constraint c) throws polyglot.types.SemanticException
c
-
polyglot.types.SemanticException
protected abstract void addDependencies(Equation eqn)
protected void addDependency(Variable var, Equation eqn)
protected void addDependency(Equation eqn, Variable var)
protected java.util.Set eqnEqnDependencies(Equation eqn)
protected java.util.Set eqnEqnReverseDependencies(Equation eqn)
protected final void addTrace(VarLabel v, Equation eqn, Label lb)
protected final Equation findTrace(VarLabel var, Label threshold, boolean lowerThreshold)
protected void reportTraces(java.util.Collection variables)
Variables
protected boolean errorShowConstraint()
protected boolean errorShowTechnicalMsg()
protected boolean errorShowDetailMsg()
protected boolean errorShowDefns()
protected final java.lang.String errorMsg(Constraint c)
protected java.lang.String errorStringConstraint(Constraint c)
c
.
protected java.lang.String errorStringDefns(LabelConstraint c)
c
.
protected void reportError(Constraint c, java.util.Collection variables) throws polyglot.types.SemanticException
c
- The constraint that cannot be satisfied.
polyglot.types.SemanticException
- always.protected Equation findContradictiveEqn(Constraint c)
protected abstract Equation findContradictiveEqn(LabelConstraint c)
protected java.util.LinkedList findSCCs()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |