1 package org.simantics.scl.compiler.internal.elaboration.constraints;
\r
3 import java.util.ArrayList;
\r
4 import java.util.Arrays;
\r
5 import java.util.Collections;
\r
6 import java.util.List;
\r
8 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
\r
9 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
\r
10 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
\r
11 import org.simantics.scl.compiler.types.TCon;
\r
12 import org.simantics.scl.compiler.types.TMetaVar;
\r
13 import org.simantics.scl.compiler.types.TPred;
\r
14 import org.simantics.scl.compiler.types.Type;
\r
15 import org.simantics.scl.compiler.types.Types;
\r
16 import org.simantics.scl.compiler.types.exceptions.UnificationException;
\r
17 import org.simantics.scl.compiler.types.util.TConComparator;
\r
18 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;
\r
20 import gnu.trove.map.hash.THashMap;
\r
21 import gnu.trove.set.hash.THashSet;
\r
23 public class ConstraintSolver {
\r
25 public static THashSet<TCon> DEFAULTS_IGNORE = new THashSet<TCon>();
\r
26 public static THashMap<List<TCon>, Type> DEFAULTS = new THashMap<List<TCon>, Type>();
\r
29 DEFAULTS_IGNORE.add(Types.SHOW);
\r
30 DEFAULTS_IGNORE.add(Types.con("Json2", "JSON"));
\r
31 DEFAULTS_IGNORE.add(Types.VEC_COMP);
\r
32 DEFAULTS_IGNORE.add(Types.ORD);
\r
33 DEFAULTS_IGNORE.add(Types.TYPEABLE);
\r
34 DEFAULTS_IGNORE.add(Types.SERIALIZABLE);
\r
35 DEFAULTS_IGNORE.add(Types.con("Formatting", "FormatArgument"));
\r
37 DEFAULTS.put(Arrays.asList(Types.ADDITIVE), Types.INTEGER);
\r
38 DEFAULTS.put(Arrays.asList(Types.RING), Types.INTEGER);
\r
39 DEFAULTS.put(Arrays.asList(Types.ORDERED_RING), Types.INTEGER);
\r
40 DEFAULTS.put(Arrays.asList(Types.INTEGRAL), Types.INTEGER);
\r
41 DEFAULTS.put(Arrays.asList(Types.REAL), Types.DOUBLE);
\r
43 { // Some R -module specific hacks
\r
44 TCon RCOMPATIBLE = Types.con("R/RExp", "RCompatible");
\r
45 TCon REXP = Types.con("R/RExp", "RExp");
\r
46 DEFAULTS.put(Arrays.asList(RCOMPATIBLE), REXP);
\r
47 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ADDITIVE), Types.DOUBLE);
\r
48 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.RING), Types.DOUBLE);
\r
49 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ORDERED_RING), Types.DOUBLE);
\r
50 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.INTEGRAL), Types.DOUBLE);
\r
51 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.REAL), Types.DOUBLE);
\r
55 public static ReducedConstraints solve(
\r
56 ConstraintEnvironment environment,
\r
57 ArrayList<TPred> given,
\r
58 ArrayList<EVariable> demands,
\r
59 boolean applyDefaults) {
\r
60 TypeUnparsingContext tuc = SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER ?
\r
61 new TypeUnparsingContext() : null;
\r
62 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
\r
63 System.out.println();
\r
64 System.out.println("GIVEN:");
\r
65 for(TPred g : given)
\r
66 System.out.println(" " + g.toString(tuc));
\r
67 System.out.println("DEMANDS:");
\r
68 for(EVariable demand : demands)
\r
69 System.out.println(" " + demand.getType().toString(tuc));
\r
70 System.out.println("==>");
\r
73 ConstraintSet cs = new ConstraintSet(environment);
\r
74 ArrayList<Constraint> givenConstraints =
\r
75 new ArrayList<Constraint>(given.size());
\r
77 for(TPred g : given)
\r
78 givenConstraints.add(cs.addGiven(g));
\r
80 for(EVariable d : demands)
\r
85 ArrayList<Constraint> unsolvedConstraints = new ArrayList<Constraint>();
\r
86 ArrayList<Constraint> solvedConstraints = new ArrayList<Constraint>();
\r
87 cs.collect(unsolvedConstraints, solvedConstraints);
\r
90 if(applyDefaults && !unsolvedConstraints.isEmpty()) {
\r
91 ArrayList<ArrayList<Constraint>> groups =
\r
92 groupConstraintsByCommonMetavars(unsolvedConstraints);
\r
93 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
\r
94 System.out.println("DEFAULT GROUPS:");
\r
95 for(ArrayList<Constraint> group : groups) {
\r
96 for(Constraint c : group)
\r
97 System.out.println(" " + c.constraint.toString(tuc));
\r
98 System.out.println(" --");
\r
102 unsolvedConstraints.clear();
\r
103 ArrayList<Constraint> newSolvedConstraints = new ArrayList<Constraint>(unsolvedConstraints.size() + solvedConstraints.size());
\r
104 for(ArrayList<Constraint> group : groups) {
\r
105 // Special rule for Typeable
\r
106 /*if(group.size() == 1 && group.get(0).constraint.typeFunction == Types.TYPEABLE) {
\r
107 Type parameter = Types.canonical(group.get(0).constraint.parameters[0]);
\r
108 if(parameter instanceof TMetaVar) {
\r
110 ((TMetaVar)parameter).setRef(Types.INTEGER);
\r
111 } catch (UnificationException e) {
\r
112 throw new InternalCompilerError(e);
\r
115 Constraint constraint = group.get(0);
\r
116 Reduction reduction = environment.reduce(constraint.constraint);
\r
117 if(reduction.parameters.length > 0)
\r
118 throw new InternalCompilerError();
\r
119 constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
\r
120 reduction.generator, reduction.parameters);
\r
121 newSolvedConstraints.add(constraint);
\r
127 ArrayList<TCon> cons = new ArrayList<TCon>(group.size());
\r
128 for(Constraint constraint : group)
\r
129 if(!DEFAULTS_IGNORE.contains(constraint.constraint.typeClass))
\r
130 cons.add(constraint.constraint.typeClass);
\r
131 Collections.sort(cons, TConComparator.INSTANCE);
\r
133 Type defaultType = DEFAULTS.get(cons);
\r
134 if(defaultType != null) {
\r
135 TMetaVar var = null;
\r
136 for(Constraint constraint : group) {
\r
137 if(constraint.constraint.parameters.length != 1) {
\r
141 Type parameter = Types.canonical(constraint.constraint.parameters[0]);
\r
142 if(!(parameter instanceof TMetaVar)) {
\r
147 var = (TMetaVar)parameter;
\r
151 var.setRef(defaultType);
\r
152 } catch (UnificationException e) {
\r
153 throw new InternalCompilerError();
\r
155 for(Constraint constraint : group) {
\r
156 Reduction reduction = environment.reduce(constraint.constraint);
\r
157 if(reduction.demands.length > 0)
\r
158 throw new InternalCompilerError();
\r
159 constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
\r
160 reduction.generator, reduction.parameters);
\r
161 newSolvedConstraints.add(constraint);
\r
166 unsolvedConstraints.addAll(group);
\r
169 Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE);
\r
171 newSolvedConstraints.addAll(solvedConstraints);
\r
172 solvedConstraints = newSolvedConstraints;
\r
175 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
\r
176 System.out.println("UNSOLVED:");
\r
177 for(Constraint c : unsolvedConstraints)
\r
178 System.out.println(" " + c.constraint.toString(tuc));
\r
179 System.out.println("SOLVED:");
\r
180 for(Constraint c : solvedConstraints)
\r
181 System.out.println(" " + c.constraint.toString(tuc) + " <= " + c.generator);
\r
182 //System.out.println("APPLY DEFAULTS: " + applyDefaults);
\r
185 return new ReducedConstraints(givenConstraints,
\r
187 unsolvedConstraints);
\r
190 private static <K,V> void add(
\r
191 THashMap<K, ArrayList<V>> map,
\r
193 ArrayList<V> list = map.get(k);
\r
195 list = new ArrayList<V>(2);
\r
201 private static TMetaVar canonical(
\r
202 THashMap<TMetaVar, TMetaVar> cMap,
\r
205 TMetaVar temp = cMap.get(v);
\r
213 private static void merge(
\r
214 THashMap<TMetaVar, TMetaVar> cMap,
\r
215 THashMap<TMetaVar, ArrayList<Constraint>> groups,
\r
220 ArrayList<Constraint> listB = groups.remove(b);
\r
221 if(listB != null) {
\r
222 ArrayList<Constraint> listA = groups.get(a);
\r
224 groups.put(a, listB);
\r
226 listA.addAll(listB);
\r
231 private static ArrayList<ArrayList<Constraint>> groupConstraintsByCommonMetavars(
\r
232 ArrayList<Constraint> constraints) {
\r
233 THashMap<TMetaVar, ArrayList<Constraint>> groups =
\r
234 new THashMap<TMetaVar, ArrayList<Constraint>>();
\r
235 THashMap<TMetaVar, TMetaVar> cMap = new THashMap<TMetaVar, TMetaVar>();
\r
237 ArrayList<TMetaVar> vars = new ArrayList<TMetaVar>();
\r
238 for(Constraint constraint : constraints) {
\r
239 constraint.constraint.collectMetaVars(vars);
\r
240 if(vars.isEmpty()) {
\r
241 add(groups, null, constraint);
\r
244 TMetaVar first = canonical(cMap, vars.get(0));
\r
245 for(int i=1;i<vars.size();++i)
\r
246 merge(cMap, groups, first, canonical(cMap, vars.get(i)));
\r
248 add(groups, first, constraint);
\r
252 return new ArrayList<ArrayList<Constraint>>(groups.values());
\r