bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/transformations/UnifiableFactory.java

   1 package org.simantics.scl.compiler.internal.elaboration.transformations;
   2
   3 import java.util.ArrayList;
   4
   5 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   6 import org.simantics.scl.compiler.common.names.Name;
   7 import org.simantics.scl.compiler.constants.Constant;
   8 import org.simantics.scl.compiler.constants.StringConstant;
   9 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
  10 import org.simantics.scl.compiler.elaboration.expressions.EApply;
  11 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
  12 import org.simantics.scl.compiler.elaboration.expressions.ELambda;
  13 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
  14 import org.simantics.scl.compiler.elaboration.expressions.ESimpleLet;
  15 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  16 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  17 import org.simantics.scl.compiler.elaboration.expressions.Expressions;
  18 import org.simantics.scl.compiler.elaboration.expressions.Variable;
  19 import org.simantics.scl.compiler.elaboration.expressions.VariableProcedure;
  20 import org.simantics.scl.compiler.elaboration.expressions.block.LetStatement;
  21 import org.simantics.scl.compiler.elaboration.expressions.block.Statement;
  22 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
  23 import org.simantics.scl.compiler.errors.Locations;
  24 import org.simantics.scl.compiler.internal.codegen.references.IVal;
  25 import org.simantics.scl.compiler.internal.types.HashCodeUtils;
  26 import org.simantics.scl.compiler.types.TCon;
  27 import org.simantics.scl.compiler.types.Type;
  28 import org.simantics.scl.compiler.types.Types;
  29 import org.simantics.scl.compiler.types.exceptions.MatchException;
  30 import org.simantics.scl.compiler.types.util.MultiApply;
  31 import org.simantics.scl.compiler.types.util.MultiFunction;
  32
  33 import gnu.trove.map.hash.THashMap;
  34 import gnu.trove.set.hash.THashSet;
  35
  36 public class UnifiableFactory {
  37     private static final TCon Unifiable = Types.con("Unification", "Unifiable");
  38     private static final Name uVar = Name.create("Unification", "uVar");
  39     private static final Name uCons = Name.create("Unification", "uCons");
  40     private static final Name uId = Name.create("Unification", "uId");
  41     private static final Name uPending = Name.create("Unification", "uPending");
  42     private static final TCon UTag = Types.con("Unification", "UTag");
  43     private static final Name uTag = Name.create("Unification", "uTag");
  44     private static final Name extractWithDefault = Name.create("Unification", "extractWithDefault");
  45
  46     private static final Name putUMap = Name.create("Unification", "putUMap");
  47     private static final Name putUMapC = Name.create("Unification", "putUMapC");
  48     private static final Name getUMapWithDefault = Name.create("Unification", "getUMapWithDefault");
  49
  50     private static final Name fail = Name.create("Builtin", "fail");
  51     private static final Name unsafeCoerce = Name.create("JavaBuiltin", "unsafeCoerce");
  52     private static final Name newResource = Name.create("Simantics/DB", "newResource");
  53     private static final Name createElement = Name.create("Data/XML", "createElement");
  54
  55     private static final Type XML_ELEMENT = Types.con("Data/XML", "Element");
  56
  57     private final TypingContext context;
  58     /**
  59      * The factory generates here the statements initializing the variables needed in unification.
  60      */
  61     private final ArrayList<Statement> mappingStatements;
  62     private THashMap<Type, Variable> defaultGenerators =
  63             new THashMap<Type, Variable>();
  64
  65     public UnifiableFactory(TypingContext context, ArrayList<Statement> phase2Statements) {
  66         this.context = context;
  67         this.mappingStatements = phase2Statements;
  68     }
  69
  70     /**
  71      * Converts an expression of type {@code T} to an expression of type {@code Unifiable T}
  72      * @param variableSet The unifiable variables
  73      * @param uniVariableMap A map from ordinary variables to unifiables
  74      * @param expression The expression that is converted
  75      * @return
  76      */
  77     private Expression toUnifiable(
  78             THashSet<Variable> variableSet,
  79             THashMap<Variable, Variable> uniVariableMap,
  80             Expression expression) {
  81         UnifiableRep rep = toUnifiableRep(variableSet, uniVariableMap, expression);
  82         return rep.toExpression();
  83     }
  84
  85     static interface UnifiableRep {
  86         Expression toExpression();
  87     }
  88
  89     class ConstantRep implements UnifiableRep {
  90         final Expression constant;
  91         public ConstantRep(Expression constant) {
  92             this.constant = constant;
  93         }
  94         @Override
  95         public Expression toExpression() {
  96             return Expressions.apply(context, Types.NO_EFFECTS, uId,
  97                     constant.getType(), constant);
  98         }
  99     }
 100
 101     class PendingRep implements UnifiableRep {
 102         final THashSet<Variable> dependences;
 103         final THashMap<Variable, Variable> uniVariableMap;
 104         final Expression value;
 105         public PendingRep(THashSet<Variable> dependences, THashMap<Variable, Variable> uniVariableMap,
 106                 Expression value) {
 107             this.dependences = dependences;
 108             this.uniVariableMap = uniVariableMap;
 109             this.value = value;
 110         }
 111         @Override
 112         public Expression toExpression() {
 113             Expression expression = value;
 114             for(Variable variable : dependences)
 115                 expression = new ESimpleLet(
 116                         variable,
 117                         extract(variable.getType(), Expressions.var(uniVariableMap.get(variable))),
 118                         expression);
 119             return Expressions.apply(context, Types.NO_EFFECTS, uPending,
 120                     value.getType(), Expressions.computation(Types.PROC, expression));
 121         }
 122     }
 123
 124     static class UniRep implements UnifiableRep {
 125         final Expression uni;
 126         public UniRep(Expression uni) {
 127             this.uni = uni;
 128         }
 129         @Override
 130         public Expression toExpression() {
 131             return uni;
 132         }
 133     }
 134
 135     /**
 136      * Returns null, if does not contain variables from variableSet
 137      */
 138     private UnifiableRep toUnifiableRep(
 139             final THashSet<Variable> variableSet,
 140             final THashMap<Variable, Variable> uniVariableMap,
 141             Expression expression) {
 142         if(expression instanceof EVariable) {
 143             Variable variable = ((EVariable)expression).getVariable();
 144             if(!variableSet.contains(variable))
 145                 return new ConstantRep(expression);
 146
 147             Variable uniVariable = uniVariableMap.get(variable);
 148             if(uniVariable != null)
 149                 return new UniRep(new EVariable(uniVariable));
 150             else
 151                 return new UniRep(Expressions.apply(context, Types.PROC, uVar, variable.getType(), Expressions.punit()));
 152         }
 153         apply:
 154         if(expression instanceof EApply) {
 155             EApply apply = (EApply)expression;
 156
 157             if(!(apply.getFunction() instanceof EConstant))
 158                 break apply;
 159             EConstant function = (EConstant)apply.getFunction();
 160
 161             IVal val = function.getValue().getValue();
 162             if(!(val instanceof Constant))
 163                 break apply;
 164             Constant constant = (Constant)val;
 165
 166             int constructorTag = constant.constructorTag();
 167             if(constructorTag < 0)
 168                 break apply;
 169
 170             int arity = constant.getArity();
 171             Expression[] parameters = apply.getParameters();
 172             if(arity != parameters.length)
 173                 break apply;
 174
 175             boolean hasUnifiableParameter = false;
 176             boolean hasPendingParameter = false;
 177             UnifiableRep[] uniParameters = new UnifiableRep[arity];
 178             for(int i=0;i<arity;++i) {
 179                 UnifiableRep uRep = toUnifiableRep(variableSet, uniVariableMap, parameters[i]);
 180                 uniParameters[i] = uRep;
 181                 if(uRep instanceof UniRep)
 182                     hasUnifiableParameter = true;
 183                 else if(uRep instanceof PendingRep)
 184                     hasPendingParameter = true;
 185             }
 186
 187             if(hasUnifiableParameter) {
 188                 Expression[] tupleParameters = new Expression[arity];
 189                 for(int i=0;i<arity;++i)
 190                     tupleParameters[i] = uniParameters[i].toExpression();
 191                 Expression tuple = Expressions.tuple(tupleParameters);
 192                 return new UniRep(Expressions.apply(context, Types.NO_EFFECTS, uCons,
 193                         expression.getType(), tuple.getType(),
 194                         getTag(function), tuple));
 195             }
 196             else if(hasPendingParameter) {
 197                 THashSet<Variable> dependences = new THashSet<Variable>();
 198                 for(UnifiableRep uRep : uniParameters)
 199                     if(uRep instanceof PendingRep)
 200                         dependences.addAll(((PendingRep)uRep).dependences);
 201                 return new PendingRep(dependences, uniVariableMap, expression);
 202             }
 203             else
 204                 return new ConstantRep(expression);
 205         }
 206
 207         // Default action
 208         final THashSet<Variable> dependences = new THashSet<Variable>();
 209         expression.forVariables(new VariableProcedure() {
 210
 211             @Override
 212             public void execute(long location, Variable variable) {
 213                 if(variableSet.contains(variable))
 214                     dependences.add(variable);
 215             }
 216         });
 217         if(dependences.isEmpty())
 218             return new ConstantRep(expression);
 219         else
 220             return new PendingRep(dependences, uniVariableMap, expression);
 221     }
 222
 223     private static class Constructor {
 224         final SCLValue function;
 225         final Type[] typeParameters;
 226         private int hashCode;
 227
 228         public Constructor(SCLValue function, Type[] typeParameters) {
 229             this.function = function;
 230             this.typeParameters = typeParameters;
 231         }
 232
 233         @Override
 234         public boolean equals(Object obj) {
 235             if(obj == this)
 236                 return true;
 237             if(obj == null || obj.getClass() != Constructor.class)
 238                 return false;
 239             Constructor other = (Constructor)obj;
 240             if(function != other.function)
 241                 return false;
 242             return Types.equals(typeParameters, other.typeParameters);
 243         }
 244
 245         @Override
 246         public int hashCode() {
 247             if(hashCode == 0) {
 248                 int hash = HashCodeUtils.SEED;
 249                 hash = HashCodeUtils.update(hash, function.hashCode());
 250                 for(Type typeParameter : typeParameters)
 251                     hash = typeParameter.hashCode(hash);
 252                 hashCode = hash;
 253             }
 254             return hashCode;
 255         }
 256     }
 257
 258     private THashMap<Constructor, Variable> constructorTags =
 259             new THashMap<Constructor, Variable>();
 260
 261     private Expression getTag(EConstant constructorExpr) {
 262         Constructor key = new Constructor(constructorExpr.getValue(),
 263                 constructorExpr.getTypeParameters());
 264         Variable tag = constructorTags.get(key);
 265         if(tag == null) {
 266             SCLValue sclValue = constructorExpr.getValue();
 267             Constant constant = (Constant)sclValue.getValue();
 268             int arity = constant.getArity();
 269             int constructorTag = constant.constructorTag();
 270             MultiFunction mfun;
 271             try {
 272                 mfun = Types.matchFunction(constructorExpr.getType(), arity);
 273             } catch (MatchException e) {
 274                 throw new InternalCompilerError(e);
 275             }
 276
 277             Type[] uniParameterTypes = new Type[arity];
 278             for(int i=0;i<arity;++i)
 279                 uniParameterTypes[i] = Types.apply(Unifiable, mfun.parameterTypes[i]);
 280             Type tupleType = Types.tuple(uniParameterTypes);
 281
 282             // Destructor
 283             Expression destructor;
 284             if(sclValue.getName().module.equals("Builtin") && sclValue.getName().name.charAt(0)=='(') {
 285                 // Tuple constructor is a special case, where we can just cast the value
 286                 destructor = Expressions.constant(context, unsafeCoerce, mfun.returnType, tupleType);
 287             }
 288             else {
 289                 Variable[] parameters = new Variable[arity];
 290                 for(int i=0;i<arity;++i)
 291                     parameters[i] = new Variable("p" + i, mfun.parameterTypes[i]);
 292                 Expression pattern = new EApply(constructorExpr.copy(context), Expressions.vars(parameters));
 293                 Expression[] tupleParameters = new Expression[arity];
 294                 for(int i=0;i<arity;++i)
 295                     tupleParameters[i] = Expressions.apply(context, Types.NO_EFFECTS, uId,
 296                             parameters[i].getType(), Expressions.var(parameters[i]));
 297                 Expression value = Expressions.tuple(tupleParameters);
 298                 destructor = new ELambda(Locations.NO_LOCATION, pattern, value);
 299             }
 300
 301             // Constructor
 302             Expression constructor;
 303             {
 304                 Variable[] parameters = new Variable[arity];
 305                 for(int i=0;i<arity;++i)
 306                     parameters[i] = new Variable("p" + i, uniParameterTypes[i]);
 307                 Expression pattern = Expressions.tuple(Expressions.vars(parameters));
 308                 Expression[] constructorParameters = new Expression[arity];
 309                 for(int i=0;i<arity;++i)
 310                     constructorParameters[i] = extract(mfun.parameterTypes[i], Expressions.var(parameters[i]));
 311                 Expression value = new EApply(constructorExpr.copy(context), constructorParameters);
 312                 constructor = new ELambda(Locations.NO_LOCATION, pattern, value);
 313             }
 314
 315             tag = new Variable("tag", Types.apply(UTag, mfun.returnType, tupleType));
 316             mappingStatements.add(new LetStatement(new EVariable(tag),
 317                     Expressions.apply(context, Types.NO_EFFECTS, uTag, tupleType, mfun.returnType,
 318                             Expressions.integer(constructorTag), constructor, destructor)));
 319             constructorTags.put(key, tag);
 320         }
 321         return new EVariable(tag);
 322     }
 323
 324     private Expression extract(Type type, Expression uni) {
 325         return Expressions.apply(context, Types.PROC, extractWithDefault,
 326                 type, getDefaultGenerator(type), uni);
 327     }
 328
 329     /**
 330      * Returns for the given type {@code T} a generator
 331      * of type {@code <Proc> T} that generates the values of the type.
 332      */
 333     private Expression getDefaultGenerator(Type type) {
 334         Variable generator = defaultGenerators.get(type);
 335         if(generator == null) {
 336             generator = new Variable("defGen", Types.functionE(Types.PUNIT, Types.PROC, type));
 337             mappingStatements.add(new LetStatement(new EVariable(generator),
 338                     Expressions.computation(Types.PROC, createGenerationExpression(type))
 339                     ));
 340             defaultGenerators.put(type, generator);
 341         }
 342         return new EVariable(generator);
 343     }
 344
 345     private Expression createGenerationExpression(Type type) {
 346         MultiApply apply = Types.matchApply(type);
 347         //System.out.println("createGenerationExpression(" + type.toString(tuc) + ")");
 348         if(apply.constructor instanceof TCon) {
 349             if(apply.constructor.equals(Types.RESOURCE))
 350                 return Expressions.apply(context, Types.PROC, newResource, Expressions.tuple());
 351
 352             if(apply.constructor.equals(Types.STRING))
 353                 return new ELiteral(new StringConstant("")); // FIXME
 354
 355             if(apply.constructor.equals(XML_ELEMENT))
 356                 return Expressions.apply(context, Types.PROC, createElement, Expressions.string("NO-NAME"));
 357
 358             TCon con = (TCon)apply.constructor;
 359             if(con.name.charAt(0) == '(') { // (), (,), (,,),...
 360                 int arity = con.name.length()-1;
 361                 if(arity == 1)
 362                     arity = 0;
 363                 if(arity != apply.parameters.length)
 364                     throw new InternalCompilerError();
 365                 Expression[] parameters = new Expression[arity];
 366                 for(int i=0;i<arity;++i)
 367                     parameters[i] = new EApply(Locations.NO_LOCATION, Types.PROC,
 368                             getDefaultGenerator(apply.parameters[i]), Expressions.punit());
 369                 return Expressions.tuple(parameters);
 370             }
 371         }
 372         return Expressions.apply(context, Types.NO_EFFECTS, fail,
 373                 new ELiteral(new StringConstant("Cannot generated default instance for type " + type + ".")));
 374     }
 375
 376     public Expression generateDefaultValue(Type type) {
 377         return Expressions.apply(Types.PROC, getDefaultGenerator(type), Expressions.punit());
 378     }
 379
 380     public Expression getFromUMap(Expression umap, Expression key, Type valueType) {
 381         return Expressions.apply(context, Types.PROC,
 382                 getUMapWithDefault,
 383                 valueType,
 384                 key.getType(),
 385                 getDefaultGenerator(valueType),
 386                 umap,
 387                 key);
 388     }
 389
 390     public Expression putToUMapUnifiable(
 391             THashSet<Variable> variableSet, THashMap<Variable, Variable> uniVariableMap,
 392             Expression umap, Expression key, Expression value) {
 393         return Expressions.apply(context, Types.PROC,
 394                 putUMap,
 395                 key.getType(),
 396                 value.getType(),
 397                 umap,
 398                 key,
 399                 toUnifiable(variableSet, uniVariableMap, value));
 400     }
 401
 402     public Expression putToUMapConstant(Variable umap, Expression key, Expression value) {
 403         return Expressions.apply(context, Types.PROC,
 404                 putUMapC,
 405                 key.getType(), value.getType(),
 406                 Expressions.var(umap),
 407                 key, value);
 408     }
 409 }