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 import org.slf4j.Logger;
  20 import org.slf4j.LoggerFactory;
  21
  22 import gnu.trove.map.hash.THashMap;
  23 import gnu.trove.set.hash.THashSet;
  24
  25 public class ConstraintSolver {
  26
  27     private static final Logger LOGGER = LoggerFactory.getLogger(ConstraintSolver.class);
  28
  29     public static THashSet<TCon> DEFAULTS_IGNORE = new THashSet<TCon>();
  30     public static THashMap<List<TCon>, Type> DEFAULTS = new THashMap<List<TCon>, Type>();
  31
  32     static {
  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"));
  40
  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);
  46
  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);
  56         }
  57     }
  58
  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) {
  67             LOGGER.info("");
  68             LOGGER.info("GIVEN:");
  69             for(TPred g : given)
  70                 LOGGER.info("    " + g.toString(tuc));
  71             LOGGER.info("DEMANDS:");
  72             for(EVariable demand : demands)
  73                 LOGGER.info("    " + demand.getType().toString(tuc));
  74             LOGGER.info("==>");
  75         }
  76
  77         ConstraintSet cs = new ConstraintSet(environment);
  78         ArrayList<Constraint> givenConstraints =
  79                 new ArrayList<Constraint>(given.size());
  80
  81         for(TPred g : given)
  82             givenConstraints.add(cs.addGiven(g));
  83
  84         for(EVariable d : demands)
  85             cs.addDemand(d);
  86
  87         cs.reduce();
  88
  89         ArrayList<Constraint> unsolvedConstraints = new ArrayList<Constraint>();
  90         ArrayList<Constraint> solvedConstraints = new ArrayList<Constraint>();
  91         cs.collect(unsolvedConstraints, solvedConstraints);
  92
  93         // Apply defaults
  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));
 102                     LOGGER.info("    --");
 103                 }
 104             }
 105
 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) {
 113                         try {
 114                             ((TMetaVar)parameter).setRef(Types.INTEGER);
 115                         } catch (UnificationException e) {
 116                             throw new InternalCompilerError(e);
 117                         }
 118
 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);
 126                     }
 127                     continue;
 128                 }*/
 129
 130                 // Standard rule
 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);
 136
 137                 Type defaultType = DEFAULTS.get(cons);
 138                 if(defaultType != null) {
 139                     TMetaVar var = null;
 140                     for(Constraint constraint : group) {
 141                         if(constraint.constraint.parameters.length != 1) {
 142                             var = null;
 143                             break;
 144                         }
 145                         Type parameter = Types.canonical(constraint.constraint.parameters[0]);
 146                         if(!(parameter instanceof TMetaVar)) {
 147                             var = null;
 148                             break;
 149                         }
 150                         if(var == null)
 151                             var = (TMetaVar)parameter;
 152                     }
 153                     if(var != null) {
 154                         try {
 155                             var.setRef(defaultType);
 156                         } catch (UnificationException e) {
 157                             throw new InternalCompilerError();
 158                         }
 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);
 166                         }
 167                         continue;
 168                     }
 169                 }
 170                 unsolvedConstraints.addAll(group);
 171             }
 172
 173             Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE);
 174
 175             newSolvedConstraints.addAll(solvedConstraints);
 176             solvedConstraints = newSolvedConstraints;
 177         }
 178
 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);
 187         }
 188
 189         return new ReducedConstraints(givenConstraints,
 190                 solvedConstraints,
 191                 unsolvedConstraints);
 192     }
 193
 194     private static <K,V> void add(
 195             THashMap<K, ArrayList<V>> map,
 196             K k, V v) {
 197         ArrayList<V> list = map.get(k);
 198         if(list == null) {
 199             list = new ArrayList<V>(2);
 200             map.put(k, list);
 201         }
 202         list.add(v);
 203     }
 204
 205     private static TMetaVar canonical(
 206             THashMap<TMetaVar, TMetaVar> cMap,
 207             TMetaVar v) {
 208         while(true) {
 209             TMetaVar temp = cMap.get(v);
 210             if(temp == null)
 211                 return v;
 212             else
 213                 v = temp;
 214         }
 215     }
 216
 217     private static void merge(
 218             THashMap<TMetaVar, TMetaVar> cMap,
 219             THashMap<TMetaVar, ArrayList<Constraint>> groups,
 220             TMetaVar a,
 221             TMetaVar b) {
 222         if(a != b) {
 223             cMap.put(b, a);
 224             ArrayList<Constraint> listB = groups.remove(b);
 225             if(listB != null) {
 226                 ArrayList<Constraint> listA = groups.get(a);
 227                 if(listA == null)
 228                     groups.put(a, listB);
 229                 else
 230                     listA.addAll(listB);
 231             }
 232         }
 233     }
 234
 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>();
 240
 241         ArrayList<TMetaVar> vars = new ArrayList<TMetaVar>();
 242         for(Constraint constraint : constraints) {
 243             constraint.constraint.collectMetaVars(vars);
 244             if(vars.isEmpty()) {
 245                 add(groups, null, constraint);
 246             }
 247             else {
 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)));
 251                 vars.clear();
 252                 add(groups, first, constraint);
 253             }
 254         }
 255
 256         return new ArrayList<ArrayList<Constraint>>(groups.values());
 257     }
 258
 259 }