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