(refs #7365) Fixed the bug in the test CHR11.scl
[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / elaboration / chr / planning / QueryPlanningContext.java
1 package org.simantics.scl.compiler.elaboration.chr.planning;
2
3 import java.util.ArrayList;
4
5 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
6 import org.simantics.scl.compiler.compilation.CompilationContext;
7 import org.simantics.scl.compiler.elaboration.chr.CHRLiteral;
8 import org.simantics.scl.compiler.elaboration.chr.plan.AccessFactOp;
9 import org.simantics.scl.compiler.elaboration.chr.plan.ClaimOp;
10 import org.simantics.scl.compiler.elaboration.chr.plan.ExecuteOp;
11 import org.simantics.scl.compiler.elaboration.chr.plan.PlanOp;
12 import org.simantics.scl.compiler.elaboration.chr.planning.items.CheckPrePlanItem;
13 import org.simantics.scl.compiler.elaboration.chr.planning.items.EqualsPrePlanItem;
14 import org.simantics.scl.compiler.elaboration.chr.planning.items.GenericPrePlanItem;
15 import org.simantics.scl.compiler.elaboration.chr.planning.items.MemberPrePlanItem;
16 import org.simantics.scl.compiler.elaboration.chr.relations.CHRConstraint;
17 import org.simantics.scl.compiler.elaboration.chr.relations.SpecialCHRRelation;
18 import org.simantics.scl.compiler.elaboration.expressions.EApplyType;
19 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
20 import org.simantics.scl.compiler.elaboration.expressions.EExternalConstant;
21 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
22 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
23 import org.simantics.scl.compiler.elaboration.expressions.Expression;
24 import org.simantics.scl.compiler.elaboration.expressions.Variable;
25 import org.simantics.scl.compiler.errors.Locations;
26
27 import gnu.trove.impl.Constants;
28 import gnu.trove.map.hash.TObjectIntHashMap;
29 import gnu.trove.procedure.TIntProcedure;
30 import gnu.trove.set.hash.TIntHashSet;
31
32 public class QueryPlanningContext {
33     CompilationContext compilationContext;
34     public PlanPriorityQueue priorityQueue = new PlanPriorityQueue();
35     ArrayList<Variable> variables;
36     TObjectIntHashMap<Variable> variableMap;
37     ArrayList<ArrayList<PrePlanItem>> itemsContainingVariable;
38     ArrayList<PlanOp> planOps = new ArrayList<PlanOp>(); 
39     
40     public QueryPlanningContext(CompilationContext compilationContext, Variable[] variables) {
41         this.compilationContext = compilationContext;
42         this.variables = new ArrayList<Variable>(variables.length*2);
43         this.variableMap = new TObjectIntHashMap<Variable>(variables.length, Constants.DEFAULT_LOAD_FACTOR, -1);
44         itemsContainingVariable = new ArrayList<ArrayList<PrePlanItem>>(variables.length*2);
45         for(Variable variable : variables)
46             addVariable(variable);
47     }
48     
49     private void addVariable(Variable variable) {
50         int id = variables.size();
51         variables.add(variable);
52         variableMap.put(variable, id);
53         itemsContainingVariable.add(new ArrayList<PrePlanItem>(2));
54     }
55
56     public void add(CHRLiteral literal, int secondaryPriority) {
57         if(literal.relation instanceof SpecialCHRRelation) {
58             switch((SpecialCHRRelation)literal.relation) {
59             case CHECK:
60                 addCheck(literal.location, literal.parameters[0], secondaryPriority);
61                 return;
62             case EQUALS:
63                 addGenericEquals(literal.location, literal.parameters[0], literal.parameters[1], secondaryPriority);
64                 return;
65             case MEMBER:
66                 addMember(literal.location, literal.parameters[0], literal.parameters[1], secondaryPriority);
67                 return;
68             case EXECUTE:
69                 throw new InternalCompilerError(literal.location, "EXECUTE constraint is not allowed in query compilation.");
70             }
71         }
72         
73         addGenericConstraint(literal, secondaryPriority);
74     }
75     
76     private TIntHashSet getVars(Expression expression, int initialCapacity) {
77         TIntHashSet variableSet = new TIntHashSet(initialCapacity);
78         expression.collectVars(variableMap, variableSet);
79         return variableSet;
80     }
81     
82     private TIntHashSet[] getVars(Expression[] expressions, int initialCapacity) {
83         TIntHashSet[] variableSets = new TIntHashSet[expressions.length];
84         for(int i=0;i<expressions.length;++i)
85             variableSets[i] = getVars(expressions[i], initialCapacity);
86         return variableSets;
87     }
88     
89     /**
90      * Returns true, if the expression is so simple, it does not involve any computation.
91      */
92     private static boolean isSimpleExpression(Expression expression) {
93         while(expression instanceof EApplyType)
94             expression = ((EApplyType)expression).getExpression();
95         return expression instanceof EVariable 
96                 || expression instanceof EConstant
97                 || expression instanceof ELiteral
98                 || expression instanceof EExternalConstant;
99     }
100     
101     private Expression toSimpleExpression(Expression expression, int secondaryPriority) {
102         if(isSimpleExpression(expression))        
103             return expression;
104         else {
105             Variable temp = new Variable("temp", expression.getType());
106             addVariable(temp);
107             addOneSidedEquals(expression.location, new EVariable(temp), expression, secondaryPriority);
108             return new EVariable(temp);
109         }
110     }
111     
112     private Expression[] toSimpleExpressions(Expression[] expressions, int secondaryPriority) {
113         Expression[] result = new Expression[expressions.length];
114         for(int i=0;i<expressions.length;++i)
115             result[i] = toSimpleExpression(expressions[i], secondaryPriority);
116         return result;
117     }
118
119     private void addGenericConstraint(CHRLiteral literal, int secondaryPriority) {
120         if(literal.killAfterMatch)
121             ((CHRConstraint)literal.relation).setMayBeRemoved();
122         Expression[] parameters = toSimpleExpressions(literal.parameters, secondaryPriority);
123         add(literal.location, new GenericPrePlanItem(literal, literal.relation, parameters, getVars(parameters, 1), secondaryPriority));
124     }
125
126     private void addMember(long location, Expression p1, Expression p2, int secondaryPriority) {
127         Expression expression1 = toSimpleExpression(p1, secondaryPriority);
128         Expression expression2 = toSimpleExpression(p2, secondaryPriority);
129         add(location, new MemberPrePlanItem(expression1, expression2,
130                 getVars(expression1, 1), getVars(expression2, 1), secondaryPriority));
131     }
132     
133     private void addOneSidedEquals(long location, Expression expression1, Expression expression2, int secondaryPriority) {
134         add(location, new EqualsPrePlanItem(expression1, expression2,
135                 getVars(expression1, 1), getVars(expression2, 4), secondaryPriority));
136     }
137
138     private void addGenericEquals(long location, Expression p1, Expression p2, int secondaryPriority) {
139         if(isSimpleExpression(p1))
140             addOneSidedEquals(location, p1, p2, secondaryPriority);
141         else if(isSimpleExpression(p2))
142             addOneSidedEquals(location, p2, p1, secondaryPriority);
143         else {
144             Variable temp = new Variable("temp", p1.getType());
145             addVariable(temp);
146             addOneSidedEquals(p1.location, new EVariable(temp), p1, secondaryPriority);
147             addOneSidedEquals(p2.location, new EVariable(temp), p2, secondaryPriority);
148         }
149     }
150
151     private void addCheck(long location, Expression condition, int secondaryPriority) {
152         TIntHashSet variableSet = new TIntHashSet(4);
153         condition.collectVars(variableMap, variableSet);
154         add(location, new CheckPrePlanItem(condition, variableSet, secondaryPriority));
155     }
156
157     private void add(long location, PrePlanItem item) {
158         priorityQueue.add(item);
159         item.initializeListeners(this);
160         item.location = location;
161     }
162
163     public void listen(TIntHashSet variableSet, PrePlanItem item) {
164         variableSet.forEach(new TIntProcedure() {
165             @Override
166             public boolean execute(int variableId) {
167                 listen(variableId, item);
168                 return true;
169             }
170         });
171     }
172
173     public void listen(int variableId, PrePlanItem item) {
174         itemsContainingVariable.get(variableId).add(item);
175     }
176
177     public boolean createQueryPlan() {
178         while(!priorityQueue.isEmpty()) {
179             PrePlanItem head = priorityQueue.head();
180             if(head.primaryPriority == Double.POSITIVE_INFINITY) {
181                 compilationContext.errorLog.log(head.location, "Cannot solve the query.");
182                 return false;
183             }
184             priorityQueue.pop();
185             head.generate(this);
186         }
187         return true;
188     }
189     
190     public ArrayList<PlanOp> getPlanOps() {
191         return planOps;
192     }
193     
194     private final TIntProcedure BIND_PROCEDURE = new TIntProcedure() {
195         @Override
196         public boolean execute(int variableId) {
197             ArrayList<PrePlanItem> l = itemsContainingVariable.get(variableId);
198             for(PrePlanItem item : l)
199                 item.variableSolved(QueryPlanningContext.this, variableId);
200             l.clear();
201             return true;
202         }
203     };
204
205     public void bind(TIntHashSet variableSet) {
206         variableSet.forEach(BIND_PROCEDURE);
207     }
208
209     public void addPlanOp(PlanOp planOp) {
210         planOps.add(planOp);
211     }
212
213     public CompilationContext getCompilationContext() {
214         return compilationContext;
215     }
216
217     public void activate(CHRLiteral literal, Expression inputFact, int secondaryPriority) {
218         Variable[] variables = new Variable[literal.parameters.length];
219         for(int i=0;i<literal.parameters.length;++i)
220             variables[i] = new Variable("activeFactComponent" + i, literal.parameters[i].getType());
221         if(literal.killAfterMatch)
222             ((CHRConstraint)literal.relation).setMayBeRemoved();
223         planOps.add(new AccessFactOp(literal.location, inputFact, (CHRConstraint)literal.relation, variables, literal.killAfterMatch));
224         for(int i=0;i<literal.parameters.length;++i)
225             addOneSidedEquals(literal.parameters[i].location, new EVariable(variables[i]), literal.parameters[i], secondaryPriority);
226     }
227     
228     public void addInitFact(CHRConstraint initConstraint, Expression inputFact) {
229         planOps.add(new AccessFactOp(Locations.NO_LOCATION, inputFact, initConstraint, Variable.EMPTY_ARRAY, false));
230     }
231
232     public void claim(QueryPlanningContext context, CHRLiteral literal) {
233         if(literal.relation instanceof CHRConstraint) {
234             CHRConstraint constraint = (CHRConstraint)literal.relation;
235             addPlanOp(new ClaimOp(literal.location, constraint, literal.parameters));
236         }
237         else if(literal.relation instanceof SpecialCHRRelation) {
238             switch((SpecialCHRRelation)literal.relation) {
239             case EXECUTE:
240                 addPlanOp(new ExecuteOp(literal.location, literal.parameters[0]));
241                 break;
242             default:
243                 context.getCompilationContext().errorLog.log(
244                         literal.location,
245                         "Cannot enforce this constraint.");
246             }
247         }
248     }
249
250 }