gerrit.simantics Code Review - simantics/platform.git/blob

   1 package org.simantics.scl.compiler.elaboration.query;
   2
   3 import gnu.trove.map.hash.THashMap;
   4 import gnu.trove.map.hash.TLongObjectHashMap;
   5 import gnu.trove.set.hash.TIntHashSet;
   6
   7 import java.util.ArrayList;
   8 import java.util.Set;
   9
  10 import org.simantics.scl.compiler.elaboration.contexts.ReplaceContext;
  11 import org.simantics.scl.compiler.elaboration.expressions.EApply;
  12 import org.simantics.scl.compiler.elaboration.expressions.ESimpleLambda;
  13 import org.simantics.scl.compiler.elaboration.expressions.ESimpleLet;
  14 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  15 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  16 import org.simantics.scl.compiler.elaboration.expressions.QueryTransformer;
  17 import org.simantics.scl.compiler.elaboration.expressions.Variable;
  18 import org.simantics.scl.compiler.elaboration.query.compilation.ConstraintCollectionContext;
  19 import org.simantics.scl.compiler.elaboration.query.compilation.DerivateException;
  20 import org.simantics.scl.compiler.elaboration.query.compilation.QueryCompilationContext;
  21 import org.simantics.scl.compiler.elaboration.query.compilation.QueryConstraint;
  22 import org.simantics.scl.compiler.elaboration.query.compilation.UnsolvableQueryException;
  23 import org.simantics.scl.compiler.elaboration.relations.LocalRelation;
  24 import org.simantics.scl.compiler.elaboration.relations.SCLRelation;
  25 import org.simantics.scl.compiler.errors.Locations;
  26 import org.simantics.scl.compiler.types.Types;
  27
  28
  29 public class QDisjunction extends QAbstractCombiner {
  30
  31     public QDisjunction(Query ... queries) {
  32         super(queries);
  33     }
  34
  35     private static class CachedPlan {
  36         Variable[] variables;
  37         QueryCompilationContext[] subplans;
  38         double totalBranching;
  39         double totalCost;
  40
  41         public CachedPlan(Variable[] variables, QueryCompilationContext[] subplans,
  42                 double totalBranching, double totalCost) {
  43             this.variables = variables;
  44             this.subplans = subplans;
  45             this.totalBranching = totalBranching;
  46             this.totalCost = totalCost;
  47         }
  48     }
  49
  50     @Override
  51     public void collectConstraints(final ConstraintCollectionContext context) {
  52         TIntHashSet vars = new TIntHashSet();
  53         collectVars(context.getVariableMap(), vars);
  54
  55         final Variable continuationFunction = new Variable("continuation");
  56         int[] variables = vars.toArray();
  57         long variableMask_ = 0L;
  58         for(int v : variables)
  59             variableMask_ |= 1L << v;
  60         final long variableMask = variableMask_;
  61
  62         context.addConstraint(new QueryConstraint(variables) {
  63
  64             TLongObjectHashMap<CachedPlan> cache = new TLongObjectHashMap<CachedPlan>();
  65
  66             private CachedPlan create(long boundVariables) {
  67                 QueryCompilationContext[] subplans = new QueryCompilationContext[queries.length];
  68                 double totalBranching = 1.0;
  69                 double totalCost = 0.0;
  70                 ArrayList<Variable> solvedVariablesList = new ArrayList<Variable>();
  71                 for(int v : variables)
  72                     if( ((boundVariables >> v)&1) == 0 )
  73                         solvedVariablesList.add(context.getVariable(v));
  74                 Variable[] solvedVariables = solvedVariablesList.toArray(new Variable[solvedVariablesList.size()]);
  75                 for(int i=0;i<queries.length;++i) {
  76                     Expression[] parameters = new Expression[solvedVariables.length];
  77                     for(int j=0;j<solvedVariables.length;++j)
  78                         parameters[j] = new EVariable(solvedVariables[j]);
  79                     EApply cont = new EApply(Locations.NO_LOCATION, Types.PROC,
  80                             new EVariable(continuationFunction), parameters);
  81                     cont.setType(context.getQueryCompilationContext().getContinuation().getType());
  82                     subplans[i] = context.getQueryCompilationContext().createSubcontext(cont);
  83                     try {
  84                         new QExists(solvedVariables, queries[i]).generate(subplans[i]);
  85                     } catch (UnsolvableQueryException e) {
  86                         return new CachedPlan(null, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
  87                     }
  88                     totalBranching += subplans[i].getBranching();
  89                     totalCost += subplans[i].getCost();
  90                 }
  91                 return new CachedPlan(solvedVariables, subplans, totalBranching, totalCost);
  92             }
  93
  94             private CachedPlan get(long boundVariables) {
  95                 boundVariables &= variableMask;
  96                 CachedPlan plan = cache.get(boundVariables);
  97                 if(plan == null) {
  98                     plan = create(boundVariables);
  99                     cache.put(boundVariables, plan);
 100                 }
 101                 return plan;
 102             }
 103
 104             @Override
 105             public double getSolutionCost(long boundVariables) {
 106                 return get(boundVariables).totalCost;
 107             }
 108
 109             @Override
 110             public double getSolutionBranching(long boundVariables) {
 111                 return get(boundVariables).totalBranching;
 112             }
 113
 114             @Override
 115             public boolean canBeSolvedFrom(long boundVariables) {
 116                 return get(boundVariables).totalCost != Double.POSITIVE_INFINITY;
 117             }
 118
 119             @Override
 120             public void generate(QueryCompilationContext context) {
 121                 CachedPlan plan = get(finalBoundVariables);
 122
 123                 Expression[] disjuncts = new Expression[plan.subplans.length];
 124                 for(int i=0;i<plan.subplans.length;++i)
 125                     disjuncts[i] = plan.subplans[i].getContinuation().copy(context.getTypingContext());
 126                 Expression result = context.disjunction(disjuncts);
 127
 128                 ReplaceContext replaceContext = new ReplaceContext(context.getTypingContext());
 129                 Variable[] newVariables = new Variable[plan.variables.length];
 130                 for(int i=0;i<newVariables.length;++i) {
 131                     Variable oldVariable = plan.variables[i];
 132                     Variable newVariable = new Variable(oldVariable.getName(), oldVariable.getType());
 133                     newVariables[i] = newVariable;
 134                     oldVariable.setName(oldVariable.getName() + "_temp");
 135                     replaceContext.varMap.put(oldVariable, new EVariable(newVariable));
 136                 }
 137
 138                 Expression functionDefinition = context.getContinuation().replace(replaceContext);
 139                 boolean first = true;
 140                 for(int i=plan.variables.length-1;i>=0;--i) {
 141                     functionDefinition = new ESimpleLambda(
 142                             first ? Types.PROC /* FIXME */ : Types.NO_EFFECTS,
 143                             newVariables[i], functionDefinition);
 144                     first = false;
 145                 }
 146                 continuationFunction.setType(functionDefinition.getType());
 147
 148                 context.setContinuation(new ESimpleLet(
 149                         continuationFunction,
 150                         functionDefinition,
 151                         result));
 152             }
 153         });
 154     }
 155
 156     @Override
 157     public Diff[] derivate(THashMap<LocalRelation, Diffable> diffables) throws DerivateException {
 158         Diff[][] diffs = new Diff[queries.length][];
 159         int totalDiffCount = 0;
 160         for(int i=0;i<queries.length;++i) {
 161             Diff[] ds = queries[i].derivate(diffables);
 162             diffs[i] = ds;
 163             totalDiffCount += ds.length;
 164         }
 165         if(totalDiffCount == 0)
 166             return NO_DIFF;
 167         else {
 168             Diff[] result = new Diff[totalDiffCount];
 169             int i=0;
 170             for(Diff[] ds : diffs)
 171                 for(Diff diff : ds)
 172                     result[i++] = diff;
 173             return result;
 174         }
 175     }
 176
 177     @Override
 178     public Query replace(ReplaceContext context) {
 179         Query[] newQueries = new Query[queries.length];
 180         for(int i=0;i<queries.length;++i)
 181             newQueries[i] = queries[i].replace(context);
 182         return new QDisjunction(newQueries);
 183     }
 184
 185     @Override
 186     public Query removeRelations(Set<SCLRelation> relations) {
 187         for(int i=0;i<queries.length;++i) {
 188             Query query = queries[i];
 189             Query newQuery = query.removeRelations(relations);
 190             if(query != newQuery) {
 191                 ArrayList<Query> newQueries = new ArrayList<Query>(queries.length);
 192                 for(int j=0;j<i;++j)
 193                     newQueries.add(queries[j]);
 194                 if(newQuery != EMPTY_QUERY)
 195                     newQueries.add(newQuery);
 196                 for(++i;i<queries.length;++i) {
 197                     query = queries[i];
 198                     newQuery = query.removeRelations(relations);
 199                     if(newQuery != EMPTY_QUERY)
 200                         newQueries.add(newQuery);
 201                 }
 202                 if(newQueries.isEmpty())
 203                     return EMPTY_QUERY;
 204                 else if(newQueries.size()==1)
 205                     return newQueries.get(0);
 206                 else
 207                     return new QDisjunction(newQueries.toArray(new Query[newQueries.size()]));
 208             }
 209         }
 210         return this;
 211     }
 212
 213     @Override
 214     public void accept(QueryVisitor visitor) {
 215         visitor.visit(this);
 216     }
 217
 218     @Override
 219     public Query accept(QueryTransformer transformer) {
 220         return transformer.transform(this);
 221     }
 222
 223 }