X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Felaboration%2Fconstraints%2FConstraintSolver.java;h=69b8e7e647f2a393e988204d4092fa7306d4aa51;hb=b4c720aaf27b84a479d800ed8a1e130f924213ef;hp=35f916ec0ed6290ee0c06ad1c97d96f95414efb6;hpb=ca40974f87c9db00eb77aaf1acc1e9937b37261b;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/ConstraintSolver.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/ConstraintSolver.java index 35f916ec0..69b8e7e64 100644 --- a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/ConstraintSolver.java +++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/ConstraintSolver.java @@ -1,255 +1,255 @@ -package org.simantics.scl.compiler.internal.elaboration.constraints; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.List; - -import org.simantics.scl.compiler.common.exceptions.InternalCompilerError; -import org.simantics.scl.compiler.elaboration.expressions.EVariable; -import org.simantics.scl.compiler.top.SCLCompilerConfiguration; -import org.simantics.scl.compiler.types.TCon; -import org.simantics.scl.compiler.types.TMetaVar; -import org.simantics.scl.compiler.types.TPred; -import org.simantics.scl.compiler.types.Type; -import org.simantics.scl.compiler.types.Types; -import org.simantics.scl.compiler.types.exceptions.UnificationException; -import org.simantics.scl.compiler.types.util.TConComparator; -import org.simantics.scl.compiler.types.util.TypeUnparsingContext; - -import gnu.trove.map.hash.THashMap; -import gnu.trove.set.hash.THashSet; - -public class ConstraintSolver { - - public static THashSet DEFAULTS_IGNORE = new THashSet(); - public static THashMap, Type> DEFAULTS = new THashMap, Type>(); - - static { - DEFAULTS_IGNORE.add(Types.SHOW); - DEFAULTS_IGNORE.add(Types.con("Json2", "JSON")); - DEFAULTS_IGNORE.add(Types.VEC_COMP); - DEFAULTS_IGNORE.add(Types.ORD); - DEFAULTS_IGNORE.add(Types.TYPEABLE); - DEFAULTS_IGNORE.add(Types.SERIALIZABLE); - DEFAULTS_IGNORE.add(Types.con("Formatting", "FormatArgument")); - - DEFAULTS.put(Arrays.asList(Types.ADDITIVE), Types.INTEGER); - DEFAULTS.put(Arrays.asList(Types.RING), Types.INTEGER); - DEFAULTS.put(Arrays.asList(Types.ORDERED_RING), Types.INTEGER); - DEFAULTS.put(Arrays.asList(Types.INTEGRAL), Types.INTEGER); - DEFAULTS.put(Arrays.asList(Types.REAL), Types.DOUBLE); - - { // Some R -module specific hacks - TCon RCOMPATIBLE = Types.con("R/RExp", "RCompatible"); - TCon REXP = Types.con("R/RExp", "RExp"); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE), REXP); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ADDITIVE), Types.DOUBLE); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.RING), Types.DOUBLE); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ORDERED_RING), Types.DOUBLE); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.INTEGRAL), Types.DOUBLE); - DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.REAL), Types.DOUBLE); - } - } - - public static ReducedConstraints solve( - ConstraintEnvironment environment, - ArrayList given, - ArrayList demands, - boolean applyDefaults) { - TypeUnparsingContext tuc = SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER ? - new TypeUnparsingContext() : null; - if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { - System.out.println(); - System.out.println("GIVEN:"); - for(TPred g : given) - System.out.println(" " + g.toString(tuc)); - System.out.println("DEMANDS:"); - for(EVariable demand : demands) - System.out.println(" " + demand.getType().toString(tuc)); - System.out.println("==>"); - } - - ConstraintSet cs = new ConstraintSet(environment); - ArrayList givenConstraints = - new ArrayList(given.size()); - - for(TPred g : given) - givenConstraints.add(cs.addGiven(g)); - - for(EVariable d : demands) - cs.addDemand(d); - - cs.reduce(); - - ArrayList unsolvedConstraints = new ArrayList(); - ArrayList solvedConstraints = new ArrayList(); - cs.collect(unsolvedConstraints, solvedConstraints); - - // Apply defaults - if(applyDefaults && !unsolvedConstraints.isEmpty()) { - ArrayList> groups = - groupConstraintsByCommonMetavars(unsolvedConstraints); - if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { - System.out.println("DEFAULT GROUPS:"); - for(ArrayList group : groups) { - for(Constraint c : group) - System.out.println(" " + c.constraint.toString(tuc)); - System.out.println(" --"); - } - } - - unsolvedConstraints.clear(); - ArrayList newSolvedConstraints = new ArrayList(unsolvedConstraints.size() + solvedConstraints.size()); - for(ArrayList group : groups) { - // Special rule for Typeable - /*if(group.size() == 1 && group.get(0).constraint.typeFunction == Types.TYPEABLE) { - Type parameter = Types.canonical(group.get(0).constraint.parameters[0]); - if(parameter instanceof TMetaVar) { - try { - ((TMetaVar)parameter).setRef(Types.INTEGER); - } catch (UnificationException e) { - throw new InternalCompilerError(e); - } - - Constraint constraint = group.get(0); - Reduction reduction = environment.reduce(constraint.constraint); - if(reduction.parameters.length > 0) - throw new InternalCompilerError(); - constraint.setGenerator(Constraint.STATE_HAS_INSTANCE, - reduction.generator, reduction.parameters); - newSolvedConstraints.add(constraint); - } - continue; - }*/ - - // Standard rule - ArrayList cons = new ArrayList(group.size()); - for(Constraint constraint : group) - if(!DEFAULTS_IGNORE.contains(constraint.constraint.typeClass)) - cons.add(constraint.constraint.typeClass); - Collections.sort(cons, TConComparator.INSTANCE); - - Type defaultType = DEFAULTS.get(cons); - if(defaultType != null) { - TMetaVar var = null; - for(Constraint constraint : group) { - if(constraint.constraint.parameters.length != 1) { - var = null; - break; - } - Type parameter = Types.canonical(constraint.constraint.parameters[0]); - if(!(parameter instanceof TMetaVar)) { - var = null; - break; - } - if(var == null) - var = (TMetaVar)parameter; - } - if(var != null) { - try { - var.setRef(defaultType); - } catch (UnificationException e) { - throw new InternalCompilerError(); - } - for(Constraint constraint : group) { - Reduction reduction = environment.reduce(constraint.constraint); - if(reduction.demands.length > 0) - throw new InternalCompilerError(); - constraint.setGenerator(Constraint.STATE_HAS_INSTANCE, - reduction.generator, reduction.parameters); - newSolvedConstraints.add(constraint); - } - continue; - } - } - unsolvedConstraints.addAll(group); - } - - Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE); - - newSolvedConstraints.addAll(solvedConstraints); - solvedConstraints = newSolvedConstraints; - } - - if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { - System.out.println("UNSOLVED:"); - for(Constraint c : unsolvedConstraints) - System.out.println(" " + c.constraint.toString(tuc)); - System.out.println("SOLVED:"); - for(Constraint c : solvedConstraints) - System.out.println(" " + c.constraint.toString(tuc) + " <= " + c.generator); - //System.out.println("APPLY DEFAULTS: " + applyDefaults); - } - - return new ReducedConstraints(givenConstraints, - solvedConstraints, - unsolvedConstraints); - } - - private static void add( - THashMap> map, - K k, V v) { - ArrayList list = map.get(k); - if(list == null) { - list = new ArrayList(2); - map.put(k, list); - } - list.add(v); - } - - private static TMetaVar canonical( - THashMap cMap, - TMetaVar v) { - while(true) { - TMetaVar temp = cMap.get(v); - if(temp == null) - return v; - else - v = temp; - } - } - - private static void merge( - THashMap cMap, - THashMap> groups, - TMetaVar a, - TMetaVar b) { - if(a != b) { - cMap.put(b, a); - ArrayList listB = groups.remove(b); - if(listB != null) { - ArrayList listA = groups.get(a); - if(listA == null) - groups.put(a, listB); - else - listA.addAll(listB); - } - } - } - - private static ArrayList> groupConstraintsByCommonMetavars( - ArrayList constraints) { - THashMap> groups = - new THashMap>(); - THashMap cMap = new THashMap(); - - ArrayList vars = new ArrayList(); - for(Constraint constraint : constraints) { - constraint.constraint.collectMetaVars(vars); - if(vars.isEmpty()) { - add(groups, null, constraint); - } - else { - TMetaVar first = canonical(cMap, vars.get(0)); - for(int i=1;i>(groups.values()); - } - -} +package org.simantics.scl.compiler.internal.elaboration.constraints; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import org.simantics.scl.compiler.common.exceptions.InternalCompilerError; +import org.simantics.scl.compiler.elaboration.expressions.EVariable; +import org.simantics.scl.compiler.top.SCLCompilerConfiguration; +import org.simantics.scl.compiler.types.TCon; +import org.simantics.scl.compiler.types.TMetaVar; +import org.simantics.scl.compiler.types.TPred; +import org.simantics.scl.compiler.types.Type; +import org.simantics.scl.compiler.types.Types; +import org.simantics.scl.compiler.types.exceptions.UnificationException; +import org.simantics.scl.compiler.types.util.TConComparator; +import org.simantics.scl.compiler.types.util.TypeUnparsingContext; + +import gnu.trove.map.hash.THashMap; +import gnu.trove.set.hash.THashSet; + +public class ConstraintSolver { + + public static THashSet DEFAULTS_IGNORE = new THashSet(); + public static THashMap, Type> DEFAULTS = new THashMap, Type>(); + + static { + DEFAULTS_IGNORE.add(Types.SHOW); + DEFAULTS_IGNORE.add(Types.con("Json2", "JSON")); + DEFAULTS_IGNORE.add(Types.VEC_COMP); + DEFAULTS_IGNORE.add(Types.ORD); + DEFAULTS_IGNORE.add(Types.TYPEABLE); + DEFAULTS_IGNORE.add(Types.SERIALIZABLE); + DEFAULTS_IGNORE.add(Types.con("Formatting", "FormatArgument")); + + DEFAULTS.put(Arrays.asList(Types.ADDITIVE), Types.INTEGER); + DEFAULTS.put(Arrays.asList(Types.RING), Types.INTEGER); + DEFAULTS.put(Arrays.asList(Types.ORDERED_RING), Types.INTEGER); + DEFAULTS.put(Arrays.asList(Types.INTEGRAL), Types.INTEGER); + DEFAULTS.put(Arrays.asList(Types.REAL), Types.DOUBLE); + + { // Some R -module specific hacks + TCon RCOMPATIBLE = Types.con("R/RExp", "RCompatible"); + TCon REXP = Types.con("R/RExp", "RExp"); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE), REXP); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ADDITIVE), Types.DOUBLE); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.RING), Types.DOUBLE); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.ORDERED_RING), Types.DOUBLE); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.INTEGRAL), Types.DOUBLE); + DEFAULTS.put(Arrays.asList(RCOMPATIBLE, Types.REAL), Types.DOUBLE); + } + } + + public static ReducedConstraints solve( + ConstraintEnvironment environment, + ArrayList given, + ArrayList demands, + boolean applyDefaults) { + TypeUnparsingContext tuc = SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER ? + new TypeUnparsingContext() : null; + if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { + System.out.println(); + System.out.println("GIVEN:"); + for(TPred g : given) + System.out.println(" " + g.toString(tuc)); + System.out.println("DEMANDS:"); + for(EVariable demand : demands) + System.out.println(" " + demand.getType().toString(tuc)); + System.out.println("==>"); + } + + ConstraintSet cs = new ConstraintSet(environment); + ArrayList givenConstraints = + new ArrayList(given.size()); + + for(TPred g : given) + givenConstraints.add(cs.addGiven(g)); + + for(EVariable d : demands) + cs.addDemand(d); + + cs.reduce(); + + ArrayList unsolvedConstraints = new ArrayList(); + ArrayList solvedConstraints = new ArrayList(); + cs.collect(unsolvedConstraints, solvedConstraints); + + // Apply defaults + if(applyDefaults && !unsolvedConstraints.isEmpty()) { + ArrayList> groups = + groupConstraintsByCommonMetavars(unsolvedConstraints); + if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { + System.out.println("DEFAULT GROUPS:"); + for(ArrayList group : groups) { + for(Constraint c : group) + System.out.println(" " + c.constraint.toString(tuc)); + System.out.println(" --"); + } + } + + unsolvedConstraints.clear(); + ArrayList newSolvedConstraints = new ArrayList(unsolvedConstraints.size() + solvedConstraints.size()); + for(ArrayList group : groups) { + // Special rule for Typeable + /*if(group.size() == 1 && group.get(0).constraint.typeFunction == Types.TYPEABLE) { + Type parameter = Types.canonical(group.get(0).constraint.parameters[0]); + if(parameter instanceof TMetaVar) { + try { + ((TMetaVar)parameter).setRef(Types.INTEGER); + } catch (UnificationException e) { + throw new InternalCompilerError(e); + } + + Constraint constraint = group.get(0); + Reduction reduction = environment.reduce(constraint.constraint); + if(reduction.parameters.length > 0) + throw new InternalCompilerError(); + constraint.setGenerator(Constraint.STATE_HAS_INSTANCE, + reduction.generator, reduction.parameters); + newSolvedConstraints.add(constraint); + } + continue; + }*/ + + // Standard rule + ArrayList cons = new ArrayList(group.size()); + for(Constraint constraint : group) + if(!DEFAULTS_IGNORE.contains(constraint.constraint.typeClass)) + cons.add(constraint.constraint.typeClass); + Collections.sort(cons, TConComparator.INSTANCE); + + Type defaultType = DEFAULTS.get(cons); + if(defaultType != null) { + TMetaVar var = null; + for(Constraint constraint : group) { + if(constraint.constraint.parameters.length != 1) { + var = null; + break; + } + Type parameter = Types.canonical(constraint.constraint.parameters[0]); + if(!(parameter instanceof TMetaVar)) { + var = null; + break; + } + if(var == null) + var = (TMetaVar)parameter; + } + if(var != null) { + try { + var.setRef(defaultType); + } catch (UnificationException e) { + throw new InternalCompilerError(); + } + for(Constraint constraint : group) { + Reduction reduction = environment.reduce(constraint.demandLocation, constraint.constraint); + if(reduction.demands.length > 0) + throw new InternalCompilerError(); + constraint.setGenerator(Constraint.STATE_HAS_INSTANCE, + reduction.generator, reduction.parameters); + newSolvedConstraints.add(constraint); + } + continue; + } + } + unsolvedConstraints.addAll(group); + } + + Collections.sort(unsolvedConstraints, ConstraintComparator.INSTANCE); + + newSolvedConstraints.addAll(solvedConstraints); + solvedConstraints = newSolvedConstraints; + } + + if(SCLCompilerConfiguration.TRACE_CONSTRAINT_SOLVER) { + System.out.println("UNSOLVED:"); + for(Constraint c : unsolvedConstraints) + System.out.println(" " + c.constraint.toString(tuc)); + System.out.println("SOLVED:"); + for(Constraint c : solvedConstraints) + System.out.println(" " + c.constraint.toString(tuc) + " <= " + c.generator); + //System.out.println("APPLY DEFAULTS: " + applyDefaults); + } + + return new ReducedConstraints(givenConstraints, + solvedConstraints, + unsolvedConstraints); + } + + private static void add( + THashMap> map, + K k, V v) { + ArrayList list = map.get(k); + if(list == null) { + list = new ArrayList(2); + map.put(k, list); + } + list.add(v); + } + + private static TMetaVar canonical( + THashMap cMap, + TMetaVar v) { + while(true) { + TMetaVar temp = cMap.get(v); + if(temp == null) + return v; + else + v = temp; + } + } + + private static void merge( + THashMap cMap, + THashMap> groups, + TMetaVar a, + TMetaVar b) { + if(a != b) { + cMap.put(b, a); + ArrayList listB = groups.remove(b); + if(listB != null) { + ArrayList listA = groups.get(a); + if(listA == null) + groups.put(a, listB); + else + listA.addAll(listB); + } + } + } + + private static ArrayList> groupConstraintsByCommonMetavars( + ArrayList constraints) { + THashMap> groups = + new THashMap>(); + THashMap cMap = new THashMap(); + + ArrayList vars = new ArrayList(); + for(Constraint constraint : constraints) { + constraint.constraint.collectMetaVars(vars); + if(vars.isEmpty()) { + add(groups, null, constraint); + } + else { + TMetaVar first = canonical(cMap, vars.get(0)); + for(int i=1;i>(groups.values()); + } + +}