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

   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.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 }