bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/relations/TransitiveClosureRelation.java

   1 package org.simantics.scl.compiler.elaboration.relations;
   2
   3 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.apply;
   4 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.if_;
   5 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.lambda;
   6 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.let;
   7 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.letRec;
   8 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.tuple;
   9 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.var;
  10
  11 import org.simantics.scl.compiler.common.names.Name;
  12 import org.simantics.scl.compiler.elaboration.expressions.EApply;
  13 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  14 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  15 import org.simantics.scl.compiler.elaboration.expressions.Variable;
  16 import org.simantics.scl.compiler.elaboration.query.compilation.QueryCompilationContext;
  17 import org.simantics.scl.compiler.types.TVar;
  18 import org.simantics.scl.compiler.types.Type;
  19 import org.simantics.scl.compiler.types.Types;
  20
  21 public class TransitiveClosureRelation extends AbstractRelation implements CompositeRelation {
  22
  23     SCLRelation baseRelation;
  24
  25     public TransitiveClosureRelation(SCLRelation baseRelation) {
  26         this.baseRelation = baseRelation;
  27     }
  28
  29     @Override
  30     public TVar[] getTypeVariables() {
  31         return baseRelation.getTypeVariables();
  32     }
  33
  34     @Override
  35     public Type[] getParameterTypes() {
  36         return baseRelation.getParameterTypes();
  37     }
  38
  39     @Override
  40     public double getSelectivity(int boundVariabes) {
  41         return baseRelation.getSelectivity(boundVariabes)*5.0;
  42     }
  43
  44     @Override
  45     public int getRequiredVariablesMask() {
  46         return baseRelation.getRequiredVariablesMask();
  47     }
  48
  49     @Override
  50     public void generate(long location,
  51             QueryCompilationContext context,
  52             Type[] typeParameters, Variable[] parameters, int boundVariables) {
  53         Variable bound, solved;
  54         if(boundVariables == (1<<(parameters.length-1))-1) {
  55             bound = parameters[0];
  56             solved = parameters[parameters.length-1];
  57         }
  58         else if(boundVariables == (1<<(parameters.length))-2) {
  59             bound = parameters[parameters.length-1];
  60             solved = parameters[0];
  61         }
  62         else //if(boundVariables == 3 || boundVariables == 0)
  63             throw new UnsupportedOperationException("boundVariables = " + boundVariables);
  64
  65         Type type = baseRelation.getParameterTypes()[0];
  66         if(typeParameters.length > 0)
  67             type = type.replace(getTypeVariables(), typeParameters);
  68
  69         Expression continuation = context.getContinuation();
  70         Variable set = new Variable("set", Types.apply(Types.con("MSet", "T"), type));
  71         Variable f = new Variable("f", Types.functionE(type, Types.PROC, continuation.getType()));
  72         Variable innerSolved = new Variable("tcTemp", solved.getType());
  73
  74         QueryCompilationContext newContext = context.createSubcontext(new EApply(
  75                 new EVariable(f), new EVariable(innerSolved)
  76                 ));
  77         Variable[] innerParameters = new Variable[parameters.length];
  78         if(boundVariables == (1<<(parameters.length-1))-1) {
  79             innerParameters[0] = solved;
  80             innerParameters[parameters.length-1] = innerSolved;
  81         }
  82         else {
  83             innerParameters[0] = innerSolved;
  84             innerParameters[parameters.length-1] = solved;
  85         }
  86         for(int i=1;i<parameters.length-1;++i)
  87             innerParameters[i] = parameters[i];
  88         baseRelation.generate(location,
  89                 newContext,
  90                 typeParameters,
  91                 innerParameters, boundVariables);
  92
  93         continuation = context.disjunction(continuation, newContext.getContinuation());
  94         continuation = if_(apply(context, Types.PROC, Name.create("MSet", "add"), type,
  95                 var(set), var(solved)),
  96                 continuation,
  97                 context.failure());
  98         continuation = lambda(Types.PROC, solved, continuation);
  99         continuation = letRec(f, continuation, apply(var(f), var(bound)));
 100         continuation = let(set,
 101                 apply(context, Types.PROC, Name.create("MSet", "create"), type, tuple()),
 102                 continuation);
 103         context.setContinuation(continuation);
 104
 105         // TODO Auto-generated method stub
 106         // base :: (a -> <Proc> ()) -> a -> <Proc> ()
 107         // initial :: a
 108         // cont :: a -> <Proc> ()
 109         /* s = MSet.create ()
 110          * f cur = if MSet.add s cur
 111          *         then do
 112          *             cont cur
 113          *             base f cur
 114          *         else ()
 115          * f cur = MSet.add s cur && (cont cur || base f cur)
 116          * f cur = if MSet.add s cur
 117          *         then match cont cur with
 118          *             result @ (Just _) -> result
 119          *             _ -> base f cur
 120          *         else Nothing
 121          */
 122
 123         /* let s = MSet.new ()
 124                f = \r -> if MSet.add s r
 125                          then do
 126                              g r
 127                              rel
 128                          else ()
 129            in  f init
 130          */
 131     }
 132
 133     @Override
 134     public SCLRelation[] getSubrelations() {
 135         return new SCLRelation[] { baseRelation };
 136     }
 137
 138 }