1 package org.simantics.scl.compiler.internal.elaboration.constraints;
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Collections;
8 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
9 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
10 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
11 import org.simantics.scl.compiler.types.TCon;
12 import org.simantics.scl.compiler.types.TMetaVar;
13 import org.simantics.scl.compiler.types.TPred;
14 import org.simantics.scl.compiler.types.Type;
15 import org.simantics.scl.compiler.types.Types;
16 import org.simantics.scl.compiler.types.exceptions.UnificationException;
17 import org.simantics.scl.compiler.types.util.TConComparator;
18 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;
19 import org.slf4j.Logger;
20 import org.slf4j.LoggerFactory;
22 import gnu.trove.map.hash.THashMap;
23 import gnu.trove.set.hash.THashSet;
25 public class ConstraintSolver {
27 private static final Logger LOGGER = LoggerFactory.getLogger(ConstraintSolver.class);
29 public static THashSet<TCon> DEFAULTS_IGNORE = new THashSet<TCon>();
30 public static THashMap<List<TCon>, Type> DEFAULTS = new THashMap<List<TCon>, Type>();
33 DEFAULTS_IGNORE.add(Types.SHOW);
34 DEFAULTS_IGNORE.add(Types.con("Json2", "JSON"));
35 DEFAULTS_IGNORE.add(Types.VEC_COMP);
36 DEFAULTS_IGNORE.add(Types.ORD);
37 DEFAULTS_IGNORE.add(Types.TYPEABLE);
38 DEFAULTS_IGNORE.add(Types.SERIALIZABLE);
39 DEFAULTS_IGNORE.add(Types.con("Formatting", "FormatArgument"));
41 DEFAULTS.put(Arrays.asList(Types.ADDITIVE), Types.INTEGER);
42 DEFAULTS.put(Arrays.asList(Types.RING), Types.INTEGER);
43 DEFAULTS.put(Arrays.asList(Types.ORDERED_RING), Types.INTEGER);
44 DEFAULTS.put(Arrays.asList(Types.INTEGRAL), Types.INTEGER);
45 DEFAULTS.put(Arrays.asList(Types.REAL), Types.DOUBLE);
47 { // Some R -module specific hacks
48 TCon RCOMPATIBLE = Types.con("R/RExp", "RCompatible");
49 TCon REXP = Types.con("R/RExp", "RExp");
50 DEFAULTS.put(Arrays.asList(RCOMPATIBLE), REXP);
51 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ADDITIVE), Types.DOUBLE);
52 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.RING), Types.DOUBLE);
53 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ORDERED_RING), Types.DOUBLE);
54 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.INTEGRAL), Types.DOUBLE);
55 DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.REAL), Types.DOUBLE);
59 public static ReducedConstraints solve(
60 ConstraintEnvironment environment,
61 ArrayList<TPred> given,
62 ArrayList<EVariable> demands,
63 boolean applyDefaults) {
64 TypeUnparsingContext tuc = SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER ?
65 new TypeUnparsingContext() : null;
66 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
68 LOGGER.info("GIVEN:");
70 LOGGER.info(" " + g.toString(tuc));
71 LOGGER.info("DEMANDS:");
72 for(EVariable demand : demands)
73 LOGGER.info(" " + demand.getType().toString(tuc));
77 ConstraintSet cs = new ConstraintSet(environment);
78 ArrayList<Constraint> givenConstraints =
79 new ArrayList<Constraint>(given.size());
82 givenConstraints.add(cs.addGiven(g));
84 for(EVariable d : demands)
89 ArrayList<Constraint> unsolvedConstraints = new ArrayList<Constraint>();
90 ArrayList<Constraint> solvedConstraints = new ArrayList<Constraint>();
91 cs.collect(unsolvedConstraints, solvedConstraints);
94 if(applyDefaults && !unsolvedConstraints.isEmpty()) {
95 ArrayList<ArrayList<Constraint>> groups =
96 groupConstraintsByCommonMetavars(unsolvedConstraints);
97 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
98 LOGGER.info("DEFAULT GROUPS:");
99 for(ArrayList<Constraint> group : groups) {
100 for(Constraint c : group)
101 LOGGER.info(" " + c.constraint.toString(tuc));
106 unsolvedConstraints.clear();
107 ArrayList<Constraint> newSolvedConstraints = new ArrayList<Constraint>(unsolvedConstraints.size() + solvedConstraints.size());
108 for(ArrayList<Constraint> group : groups) {
109 // Special rule for Typeable
110 /*if(group.size() == 1 && group.get(0).constraint.typeFunction == Types.TYPEABLE) {
111 Type parameter = Types.canonical(group.get(0).constraint.parameters[0]);
112 if(parameter instanceof TMetaVar) {
114 ((TMetaVar)parameter).setRef(Types.INTEGER);
115 } catch (UnificationException e) {
116 throw new InternalCompilerError(e);
119 Constraint constraint = group.get(0);
120 Reduction reduction = environment.reduce(constraint.constraint);
121 if(reduction.parameters.length > 0)
122 throw new InternalCompilerError();
123 constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
124 reduction.generator, reduction.parameters);
125 newSolvedConstraints.add(constraint);
131 ArrayList<TCon> cons = new ArrayList<TCon>(group.size());
132 for(Constraint constraint : group)
133 if(!DEFAULTS_IGNORE.contains(constraint.constraint.typeClass))
134 cons.add(constraint.constraint.typeClass);
135 Collections.sort(cons, TConComparator.INSTANCE);
137 Type defaultType = DEFAULTS.get(cons);
138 if(defaultType != null) {
140 for(Constraint constraint : group) {
141 if(constraint.constraint.parameters.length != 1) {
145 Type parameter = Types.canonical(constraint.constraint.parameters[0]);
146 if(!(parameter instanceof TMetaVar)) {
151 var = (TMetaVar)parameter;
155 var.setRef(defaultType);
156 } catch (UnificationException e) {
157 throw new InternalCompilerError();
159 for(Constraint constraint : group) {
160 Reduction reduction = environment.reduce(constraint.demandLocation, constraint.constraint);
161 if(reduction.demands.length > 0)
162 throw new InternalCompilerError();
163 constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
164 reduction.generator, reduction.parameters);
165 newSolvedConstraints.add(constraint);
170 unsolvedConstraints.addAll(group);
173 Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE);
175 newSolvedConstraints.addAll(solvedConstraints);
176 solvedConstraints = newSolvedConstraints;
179 if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
180 LOGGER.info("UNSOLVED:");
181 for(Constraint c : unsolvedConstraints)
182 LOGGER.info(" " + c.constraint.toString(tuc));
183 LOGGER.info("SOLVED:");
184 for(Constraint c : solvedConstraints)
185 LOGGER.info(" " + c.constraint.toString(tuc) + " <= " + c.generator);
186 //LOGGER.info("APPLY DEFAULTS: " + applyDefaults);
189 return new ReducedConstraints(givenConstraints,
191 unsolvedConstraints);
194 private static <K,V> void add(
195 THashMap<K, ArrayList<V>> map,
197 ArrayList<V> list = map.get(k);
199 list = new ArrayList<V>(2);
205 private static TMetaVar canonical(
206 THashMap<TMetaVar, TMetaVar> cMap,
209 TMetaVar temp = cMap.get(v);
217 private static void merge(
218 THashMap<TMetaVar, TMetaVar> cMap,
219 THashMap<TMetaVar, ArrayList<Constraint>> groups,
224 ArrayList<Constraint> listB = groups.remove(b);
226 ArrayList<Constraint> listA = groups.get(a);
228 groups.put(a, listB);
235 private static ArrayList<ArrayList<Constraint>> groupConstraintsByCommonMetavars(
236 ArrayList<Constraint> constraints) {
237 THashMap<TMetaVar, ArrayList<Constraint>> groups =
238 new THashMap<TMetaVar, ArrayList<Constraint>>();
239 THashMap<TMetaVar, TMetaVar> cMap = new THashMap<TMetaVar, TMetaVar>();
241 ArrayList<TMetaVar> vars = new ArrayList<TMetaVar>();
242 for(Constraint constraint : constraints) {
243 constraint.constraint.collectMetaVars(vars);
245 add(groups, null, constraint);
248 TMetaVar first = canonical(cMap, vars.get(0));
249 for(int i=1;i<vars.size();++i)
250 merge(cMap, groups, first, canonical(cMap, vars.get(i)));
252 add(groups, first, constraint);
256 return new ArrayList<ArrayList<Constraint>>(groups.values());