bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/ConstraintSolver.java

   1 package org.simantics.scl.compiler.internal.elaboration.constraints;\r
   2 \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
   7 \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
  19 \r
  20 import gnu.trove.map.hash.THashMap;\r
  21 import gnu.trove.set.hash.THashSet;\r
  22 \r
  23 public class ConstraintSolver {\r
  24 \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
  27     \r
  28     static {\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
  36         \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
  42         \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
  52         }\r
  53     }\r
  54     \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
  71         }\r
  72         \r
  73         ConstraintSet cs = new ConstraintSet(environment);\r
  74         ArrayList<Constraint> givenConstraints =\r
  75                 new ArrayList<Constraint>(given.size());\r
  76         \r
  77         for(TPred g : given)\r
  78             givenConstraints.add(cs.addGiven(g));\r
  79         \r
  80         for(EVariable d : demands)\r
  81             cs.addDemand(d);\r
  82         \r
  83         cs.reduce();\r
  84         \r
  85         ArrayList<Constraint> unsolvedConstraints = new ArrayList<Constraint>();\r
  86         ArrayList<Constraint> solvedConstraints = new ArrayList<Constraint>();\r
  87         cs.collect(unsolvedConstraints, solvedConstraints);\r
  88         \r
  89         // Apply defaults\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
  99                 }\r
 100             }\r
 101             \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
 109                         try {\r
 110                             ((TMetaVar)parameter).setRef(Types.INTEGER);\r
 111                         } catch (UnificationException e) {\r
 112                             throw new InternalCompilerError(e);\r
 113                         }\r
 114 \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
 122                     }\r
 123                     continue;\r
 124                 }*/\r
 125                 \r
 126                 // Standard rule\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
 132                 \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
 138                             var = null;\r
 139                             break;\r
 140                         }\r
 141                         Type parameter = Types.canonical(constraint.constraint.parameters[0]);\r
 142                         if(!(parameter instanceof TMetaVar)) {\r
 143                             var = null;\r
 144                             break;\r
 145                         }\r
 146                         if(var == null)\r
 147                             var = (TMetaVar)parameter;\r
 148                     }\r
 149                     if(var != null) {\r
 150                         try {\r
 151                             var.setRef(defaultType);\r
 152                         } catch (UnificationException e) {\r
 153                             throw new InternalCompilerError();\r
 154                         }\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
 162                         }  \r
 163                         continue;\r
 164                     }                                          \r
 165                 }\r
 166                 unsolvedConstraints.addAll(group);\r
 167             }\r
 168             \r
 169             Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE);\r
 170             \r
 171             newSolvedConstraints.addAll(solvedConstraints);\r
 172             solvedConstraints = newSolvedConstraints;                    \r
 173         }\r
 174 \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
 183         }\r
 184         \r
 185         return new ReducedConstraints(givenConstraints, \r
 186                 solvedConstraints,\r
 187                 unsolvedConstraints);\r
 188     }\r
 189 \r
 190     private static <K,V> void add(\r
 191             THashMap<K, ArrayList<V>> map, \r
 192             K k, V v) {\r
 193         ArrayList<V> list = map.get(k);\r
 194         if(list == null) {\r
 195             list = new ArrayList<V>(2);\r
 196             map.put(k, list);\r
 197         }\r
 198         list.add(v);\r
 199     }\r
 200     \r
 201     private static TMetaVar canonical(\r
 202             THashMap<TMetaVar, TMetaVar> cMap,\r
 203             TMetaVar v) {\r
 204         while(true) {\r
 205             TMetaVar temp = cMap.get(v);\r
 206             if(temp == null)\r
 207                 return v;\r
 208             else\r
 209                 v = temp;\r
 210         }\r
 211     }       \r
 212     \r
 213     private static void merge(\r
 214             THashMap<TMetaVar, TMetaVar> cMap,\r
 215             THashMap<TMetaVar, ArrayList<Constraint>> groups,\r
 216             TMetaVar a,\r
 217             TMetaVar b) {\r
 218         if(a != b) {\r
 219             cMap.put(b, a);\r
 220             ArrayList<Constraint> listB = groups.remove(b);\r
 221             if(listB != null) {\r
 222                 ArrayList<Constraint> listA = groups.get(a);\r
 223                 if(listA == null)\r
 224                     groups.put(a, listB);\r
 225                 else\r
 226                     listA.addAll(listB);\r
 227             }\r
 228         }\r
 229     }\r
 230     \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
 236         \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
 242             } \r
 243             else {\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
 247                 vars.clear();\r
 248                 add(groups, first, constraint);                \r
 249             }\r
 250         }\r
 251         \r
 252         return new ArrayList<ArrayList<Constraint>>(groups.values());\r
 253     }\r
 254     \r
 255 }\r