--- /dev/null
+package org.simantics.scl.compiler.elaboration.chr.analysis;\r
+\r
+import java.util.ArrayList;\r
+\r
+import org.simantics.scl.compiler.elaboration.chr.CHRLiteral;\r
+import org.simantics.scl.compiler.elaboration.chr.CHRRule;\r
+import org.simantics.scl.compiler.elaboration.chr.CHRRuleset;\r
+import org.simantics.scl.compiler.elaboration.chr.relations.CHRConstraint;\r
+\r
+import gnu.trove.map.hash.THashMap;\r
+\r
+public class UsageAnalysis {\r
+ public static void analyzeUsage(CHRRuleset ruleset) {\r
+ THashMap<CHRConstraint,ArrayList<CHRRule>> headConstraintMap = createHeadConstraintMap(ruleset);\r
+ calculateFirstPriorities(ruleset, headConstraintMap);\r
+ calculateLastPriorities(ruleset, headConstraintMap);\r
+ for(CHRRule rule : ruleset.rules)\r
+ determinePassiveLiterals(rule);\r
+ //printPriorities(ruleset);\r
+ }\r
+\r
+ private static void calculateFirstPriorities(CHRRuleset ruleset,\r
+ THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {\r
+ for(CHRRule rule : ruleset.rules)\r
+ rule.firstPriorityExecuted = Integer.MAX_VALUE;\r
+ for(CHRConstraint constraint : ruleset.constraints) {\r
+ constraint.firstPriorityAdded = Integer.MAX_VALUE;\r
+ constraint.firstPriorityRemoved = Integer.MAX_VALUE;\r
+ }\r
+ for(CHRRule rule : ruleset.rules)\r
+ calculateFirstPriority(headConstraintMap, rule);\r
+ }\r
+\r
+ private static void calculateFirstPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap, CHRRule rule) {\r
+ int result = rule.priority;\r
+ for(CHRLiteral literal : rule.head.literals)\r
+ if(literal.relation instanceof CHRConstraint) {\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ int constraintPriority = constraint.firstPriorityAdded;\r
+ if(constraintPriority == Integer.MAX_VALUE)\r
+ return;\r
+ result = Math.max(result, constraint.firstPriorityAdded);\r
+ }\r
+ rule.firstPriorityExecuted = result;\r
+ for(CHRLiteral literal : rule.head.literals)\r
+ if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ if(constraint.firstPriorityRemoved != Integer.MAX_VALUE)\r
+ continue;\r
+ constraint.firstPriorityRemoved = result;\r
+ }\r
+ for(CHRLiteral literal : rule.body.literals)\r
+ if(literal.relation instanceof CHRConstraint) {\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ if(constraint.firstPriorityAdded != Integer.MAX_VALUE)\r
+ continue;\r
+ constraint.firstPriorityAdded = result;\r
+ ArrayList<CHRRule> list = headConstraintMap.get(constraint);\r
+ if(list == null)\r
+ continue;\r
+ for(CHRRule lowerPriorityRule : list)\r
+ if(lowerPriorityRule.priority < rule.priority)\r
+ calculateFirstPriority(headConstraintMap, lowerPriorityRule);\r
+ }\r
+ }\r
+\r
+ private static void calculateLastPriorities(CHRRuleset ruleset,\r
+ THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {\r
+ for(CHRRule rule : ruleset.rules)\r
+ rule.lastPriorityExecuted = Integer.MIN_VALUE;\r
+ for(CHRConstraint constraint : ruleset.constraints) {\r
+ constraint.lastPriorityAdded = Integer.MIN_VALUE;\r
+ constraint.lastPriorityRemoved = Integer.MIN_VALUE;\r
+ }\r
+ for(int i=ruleset.rules.size()-1;i>=0;--i) {\r
+ CHRRule rule = ruleset.rules.get(i);\r
+ if(rule.lastPriorityExecuted == Integer.MIN_VALUE)\r
+ calculateLastPriority(headConstraintMap, rule, rule.priority);\r
+ }\r
+ }\r
+\r
+ private static void calculateLastPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap,\r
+ CHRRule rule, int priority) {\r
+ rule.lastPriorityExecuted = priority;\r
+ for(CHRLiteral literal : rule.head.literals)\r
+ if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ if(constraint.lastPriorityRemoved != Integer.MIN_VALUE)\r
+ continue;\r
+ constraint.lastPriorityRemoved = priority;\r
+ }\r
+ for(CHRLiteral literal : rule.body.literals)\r
+ if(literal.relation instanceof CHRConstraint) {\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ if(constraint.lastPriorityAdded != Integer.MIN_VALUE)\r
+ continue;\r
+ constraint.lastPriorityAdded = priority;\r
+ ArrayList<CHRRule> list = headConstraintMap.get(constraint);\r
+ if(list == null)\r
+ continue;\r
+ for(CHRRule lowerPriorityRule : list)\r
+ if(lowerPriorityRule.lastPriorityExecuted == Integer.MIN_VALUE)\r
+ calculateLastPriority(headConstraintMap, lowerPriorityRule, priority);\r
+ }\r
+ }\r
+\r
+ private static THashMap<CHRConstraint, ArrayList<CHRRule>> createHeadConstraintMap(CHRRuleset ruleset) {\r
+ THashMap<CHRConstraint, ArrayList<CHRRule>> map = new THashMap<CHRConstraint, ArrayList<CHRRule>>(); \r
+ for(CHRRule rule : ruleset.rules)\r
+ for(CHRLiteral literal : rule.head.literals)\r
+ if(literal.relation instanceof CHRConstraint) {\r
+ ArrayList<CHRRule> list = map.get(literal.relation);\r
+ if(list == null) {\r
+ list = new ArrayList<CHRRule>();\r
+ map.put((CHRConstraint)literal.relation, list);\r
+ list.add(rule);\r
+ }\r
+ else if(list.get(list.size()-1) != rule)\r
+ list.add(rule);\r
+ }\r
+ return map;\r
+ }\r
+ \r
+ private static void printPriorities(CHRRuleset ruleset) {\r
+ System.out.println("-------------------------------");\r
+ for(CHRConstraint constraint : ruleset.constraints) {\r
+ System.out.print(" [" + constraint.firstPriorityAdded + ".." + constraint.lastPriorityAdded + "]");\r
+ if(constraint.firstPriorityRemoved != Integer.MAX_VALUE)\r
+ System.out.print("R[" + constraint.firstPriorityRemoved + ".." + constraint.lastPriorityRemoved + "]");\r
+ System.out.print(" ");\r
+ System.out.println(constraint);\r
+ }\r
+ for(CHRRule rule : ruleset.rules) {\r
+ System.out.print(rule.priority);\r
+ System.out.print(" [" + rule.firstPriorityExecuted + ".." + rule.lastPriorityExecuted + "] ");\r
+ System.out.println(rule);\r
+ }\r
+ }\r
+\r
+ private static void determinePassiveLiterals(CHRRule rule) {\r
+ for(CHRLiteral literal : rule.head.literals) {\r
+ if(literal.passive)\r
+ continue;\r
+ CHRConstraint constraint = (CHRConstraint)literal.relation;\r
+ if(constraint.lastPriorityAdded < rule.priority)\r
+ literal.passive = true;\r
+ }\r
+ }\r
+}\r