]> gerrit.simantics Code Review - simantics/platform.git/blob
69b8e7e647f2a393e988204d4092fa7306d4aa51
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.elaboration.constraints;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Collections;
6 import java.util.List;
7
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
20 import gnu.trove.map.hash.THashMap;
21 import gnu.trove.set.hash.THashSet;
22
23 public class ConstraintSolver {
24
25     public static THashSet<TCon> DEFAULTS_IGNORE = new THashSet<TCon>(); 
26     public static THashMap<List<TCon>, Type> DEFAULTS = new THashMap<List<TCon>, Type>();
27     
28     static {
29         DEFAULTS_IGNORE.add(Types.SHOW);
30         DEFAULTS_IGNORE.add(Types.con("Json2", "JSON"));
31         DEFAULTS_IGNORE.add(Types.VEC_COMP);
32         DEFAULTS_IGNORE.add(Types.ORD);
33         DEFAULTS_IGNORE.add(Types.TYPEABLE);
34         DEFAULTS_IGNORE.add(Types.SERIALIZABLE);
35         DEFAULTS_IGNORE.add(Types.con("Formatting", "FormatArgument"));
36         
37         DEFAULTS.put(Arrays.asList(Types.ADDITIVE), Types.INTEGER);
38         DEFAULTS.put(Arrays.asList(Types.RING), Types.INTEGER);
39         DEFAULTS.put(Arrays.asList(Types.ORDERED_RING), Types.INTEGER);
40         DEFAULTS.put(Arrays.asList(Types.INTEGRAL), Types.INTEGER);       
41         DEFAULTS.put(Arrays.asList(Types.REAL), Types.DOUBLE);
42         
43         { // Some R -module specific hacks
44             TCon RCOMPATIBLE = Types.con("R/RExp", "RCompatible");
45             TCon REXP = Types.con("R/RExp", "RExp");
46             DEFAULTS.put(Arrays.asList(RCOMPATIBLE), REXP);
47             DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ADDITIVE), Types.DOUBLE);
48             DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.RING), Types.DOUBLE);
49             DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ORDERED_RING), Types.DOUBLE);
50             DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.INTEGRAL), Types.DOUBLE);
51             DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.REAL), Types.DOUBLE);
52         }
53     }
54     
55     public static ReducedConstraints solve(
56             ConstraintEnvironment environment,
57             ArrayList<TPred> given,
58             ArrayList<EVariable> demands,
59             boolean applyDefaults) {
60         TypeUnparsingContext tuc = SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER ? 
61                 new TypeUnparsingContext() : null;
62         if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
63             System.out.println();
64             System.out.println("GIVEN:");
65             for(TPred g : given)
66                 System.out.println("    " + g.toString(tuc));
67             System.out.println("DEMANDS:");
68             for(EVariable demand : demands)
69                 System.out.println("    " + demand.getType().toString(tuc));
70             System.out.println("==>");
71         }
72         
73         ConstraintSet cs = new ConstraintSet(environment);
74         ArrayList<Constraint> givenConstraints =
75                 new ArrayList<Constraint>(given.size());
76         
77         for(TPred g : given)
78             givenConstraints.add(cs.addGiven(g));
79         
80         for(EVariable d : demands)
81             cs.addDemand(d);
82         
83         cs.reduce();
84         
85         ArrayList<Constraint> unsolvedConstraints = new ArrayList<Constraint>();
86         ArrayList<Constraint> solvedConstraints = new ArrayList<Constraint>();
87         cs.collect(unsolvedConstraints, solvedConstraints);
88         
89         // Apply defaults
90         if(applyDefaults && !unsolvedConstraints.isEmpty()) {
91             ArrayList<ArrayList<Constraint>> groups = 
92                     groupConstraintsByCommonMetavars(unsolvedConstraints);
93             if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
94                 System.out.println("DEFAULT GROUPS:");
95                 for(ArrayList<Constraint> group : groups) {
96                     for(Constraint c : group)
97                         System.out.println("    " + c.constraint.toString(tuc));
98                     System.out.println("    --");
99                 }
100             }
101             
102             unsolvedConstraints.clear();
103             ArrayList<Constraint> newSolvedConstraints = new ArrayList<Constraint>(unsolvedConstraints.size() + solvedConstraints.size()); 
104             for(ArrayList<Constraint> group : groups) {
105                 // Special rule for Typeable
106                 /*if(group.size() == 1 && group.get(0).constraint.typeFunction == Types.TYPEABLE) {
107                     Type parameter = Types.canonical(group.get(0).constraint.parameters[0]);
108                     if(parameter instanceof TMetaVar) {
109                         try {
110                             ((TMetaVar)parameter).setRef(Types.INTEGER);
111                         } catch (UnificationException e) {
112                             throw new InternalCompilerError(e);
113                         }
114
115                         Constraint constraint = group.get(0);
116                         Reduction reduction = environment.reduce(constraint.constraint);
117                         if(reduction.parameters.length > 0)
118                             throw new InternalCompilerError();
119                         constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
120                                 reduction.generator, reduction.parameters);
121                         newSolvedConstraints.add(constraint);
122                     }
123                     continue;
124                 }*/
125                 
126                 // Standard rule
127                 ArrayList<TCon> cons = new ArrayList<TCon>(group.size());
128                 for(Constraint constraint : group)
129                     if(!DEFAULTS_IGNORE.contains(constraint.constraint.typeClass))
130                         cons.add(constraint.constraint.typeClass);
131                 Collections.sort(cons, TConComparator.INSTANCE);
132                 
133                 Type defaultType = DEFAULTS.get(cons);
134                 if(defaultType != null) {
135                     TMetaVar var = null;
136                     for(Constraint constraint : group) {
137                         if(constraint.constraint.parameters.length != 1) {
138                             var = null;
139                             break;
140                         }
141                         Type parameter = Types.canonical(constraint.constraint.parameters[0]);
142                         if(!(parameter instanceof TMetaVar)) {
143                             var = null;
144                             break;
145                         }
146                         if(var == null)
147                             var = (TMetaVar)parameter;
148                     }
149                     if(var != null) {
150                         try {
151                             var.setRef(defaultType);
152                         } catch (UnificationException e) {
153                             throw new InternalCompilerError();
154                         }
155                         for(Constraint constraint : group) {
156                             Reduction reduction = environment.reduce(constraint.demandLocation, constraint.constraint);
157                             if(reduction.demands.length > 0)
158                                 throw new InternalCompilerError();
159                             constraint.setGenerator(Constraint.STATE_HAS_INSTANCE,
160                                     reduction.generator, reduction.parameters);
161                             newSolvedConstraints.add(constraint);
162                         }  
163                         continue;
164                     }                                          
165                 }
166                 unsolvedConstraints.addAll(group);
167             }
168             
169             Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE);
170             
171             newSolvedConstraints.addAll(solvedConstraints);
172             solvedConstraints = newSolvedConstraints;                    
173         }
174
175         if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) {
176             System.out.println("UNSOLVED:");
177             for(Constraint c : unsolvedConstraints)
178                 System.out.println("    " + c.constraint.toString(tuc));  
179             System.out.println("SOLVED:");
180             for(Constraint c : solvedConstraints)
181                 System.out.println("    " + c.constraint.toString(tuc) + " <= " + c.generator);
182             //System.out.println("APPLY DEFAULTS: " + applyDefaults);
183         }
184         
185         return new ReducedConstraints(givenConstraints, 
186                 solvedConstraints,
187                 unsolvedConstraints);
188     }
189
190     private static <K,V> void add(
191             THashMap<K, ArrayList<V>> map, 
192             K k, V v) {
193         ArrayList<V> list = map.get(k);
194         if(list == null) {
195             list = new ArrayList<V>(2);
196             map.put(k, list);
197         }
198         list.add(v);
199     }
200     
201     private static TMetaVar canonical(
202             THashMap<TMetaVar, TMetaVar> cMap,
203             TMetaVar v) {
204         while(true) {
205             TMetaVar temp = cMap.get(v);
206             if(temp == null)
207                 return v;
208             else
209                 v = temp;
210         }
211     }       
212     
213     private static void merge(
214             THashMap<TMetaVar, TMetaVar> cMap,
215             THashMap<TMetaVar, ArrayList<Constraint>> groups,
216             TMetaVar a,
217             TMetaVar b) {
218         if(a != b) {
219             cMap.put(b, a);
220             ArrayList<Constraint> listB = groups.remove(b);
221             if(listB != null) {
222                 ArrayList<Constraint> listA = groups.get(a);
223                 if(listA == null)
224                     groups.put(a, listB);
225                 else
226                     listA.addAll(listB);
227             }
228         }
229     }
230     
231     private static ArrayList<ArrayList<Constraint>> groupConstraintsByCommonMetavars(
232             ArrayList<Constraint> constraints) {
233         THashMap<TMetaVar, ArrayList<Constraint>> groups =
234                 new THashMap<TMetaVar, ArrayList<Constraint>>();
235         THashMap<TMetaVar, TMetaVar> cMap = new THashMap<TMetaVar, TMetaVar>();
236         
237         ArrayList<TMetaVar> vars = new ArrayList<TMetaVar>(); 
238         for(Constraint constraint : constraints) {
239             constraint.constraint.collectMetaVars(vars);
240             if(vars.isEmpty()) {
241                 add(groups, null, constraint);
242             } 
243             else {
244                 TMetaVar first = canonical(cMap, vars.get(0));
245                 for(int i=1;i<vars.size();++i)
246                     merge(cMap, groups, first, canonical(cMap, vars.get(i)));
247                 vars.clear();
248                 add(groups, first, constraint);                
249             }
250         }
251         
252         return new ArrayList<ArrayList<Constraint>>(groups.values());
253     }
254     
255 }