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