1 package org.simantics.scl.compiler.elaboration.chr.analysis;
3 import java.util.ArrayList;
5 import org.simantics.scl.compiler.elaboration.chr.CHRLiteral;
6 import org.simantics.scl.compiler.elaboration.chr.CHRRule;
7 import org.simantics.scl.compiler.elaboration.chr.CHRRuleset;
8 import org.simantics.scl.compiler.elaboration.chr.relations.CHRConstraint;
10 import gnu.trove.map.hash.THashMap;
12 public class UsageAnalysis {
13 public static void analyzeUsage(CHRRuleset ruleset) {
14 THashMap<CHRConstraint,ArrayList<CHRRule>> headConstraintMap = createHeadConstraintMap(ruleset);
15 //calculateFirstPriorities(ruleset, headConstraintMap);
16 calculateLastPriorities(ruleset, headConstraintMap);
17 if(!ruleset.extensible)
18 for(CHRRule rule : ruleset.rules)
19 determinePassiveLiterals(rule);
20 //printPriorities(ruleset);
23 private static void calculateFirstPriorities(CHRRuleset ruleset,
24 THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {
25 for(CHRRule rule : ruleset.rules)
26 rule.firstPriorityExecuted = Integer.MAX_VALUE;
27 for(CHRConstraint constraint : ruleset.constraints) {
28 constraint.firstPriorityAdded = Integer.MAX_VALUE;
29 constraint.firstPriorityRemoved = Integer.MAX_VALUE;
31 for(CHRRule rule : ruleset.rules)
32 calculateFirstPriority(headConstraintMap, rule);
35 private static void calculateFirstPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap, CHRRule rule) {
36 int result = rule.priority;
37 for(CHRLiteral literal : rule.head.literals)
38 if(literal.relation instanceof CHRConstraint) {
39 CHRConstraint constraint = (CHRConstraint)literal.relation;
40 int constraintPriority = constraint.firstPriorityAdded;
41 if(constraintPriority == Integer.MAX_VALUE)
43 result = Math.max(result, constraintPriority);
45 rule.firstPriorityExecuted = result;
46 for(CHRLiteral literal : rule.head.literals)
47 if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {
48 CHRConstraint constraint = (CHRConstraint)literal.relation;
49 if(constraint.firstPriorityRemoved == Integer.MAX_VALUE)
50 constraint.firstPriorityRemoved = result;
52 for(CHRLiteral literal : rule.body.literals)
53 if(literal.relation instanceof CHRConstraint) {
54 CHRConstraint constraint = (CHRConstraint)literal.relation;
55 if(constraint.firstPriorityAdded != Integer.MAX_VALUE)
57 constraint.firstPriorityAdded = result;
58 ArrayList<CHRRule> list = headConstraintMap.get(constraint);
61 for(CHRRule lowerPriorityRule : list)
62 if(lowerPriorityRule.priority < rule.priority)
63 // We know here that previous call to lowerPriorityRule "failed",
64 // because constraint.firstPriorityAdded was previously Integer.MAX_VALUE
65 calculateFirstPriority(headConstraintMap, lowerPriorityRule);
69 private static void calculateLastPriorities(CHRRuleset ruleset,
70 THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {
71 for(CHRRule rule : ruleset.rules)
72 rule.lastPriorityExecuted = Integer.MIN_VALUE;
73 for(CHRConstraint constraint : headConstraintMap.keySet()) {
74 constraint.lastPriorityAdded = Integer.MIN_VALUE;
75 constraint.lastPriorityRemoved = Integer.MIN_VALUE;
77 for(int i=ruleset.rules.size()-1;i>=0;--i) {
78 CHRRule rule = ruleset.rules.get(i);
79 if(rule.lastPriorityExecuted == Integer.MIN_VALUE)
80 calculateLastPriority(headConstraintMap, rule, rule.priority);
84 private static void calculateLastPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap,
85 CHRRule rule, int priority) {
86 rule.lastPriorityExecuted = priority;
87 for(CHRLiteral literal : rule.head.literals)
88 if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {
89 CHRConstraint constraint = (CHRConstraint)literal.relation;
90 if(constraint.lastPriorityRemoved == Integer.MIN_VALUE)
91 constraint.lastPriorityRemoved = priority;
93 for(CHRLiteral literal : rule.body.literals)
94 if(literal.relation instanceof CHRConstraint) {
95 CHRConstraint constraint = (CHRConstraint)literal.relation;
96 if(constraint.lastPriorityAdded != Integer.MIN_VALUE)
98 constraint.lastPriorityAdded = priority;
99 ArrayList<CHRRule> list = headConstraintMap.get(constraint);
102 for(CHRRule lowerPriorityRule : list)
103 if(lowerPriorityRule.lastPriorityExecuted == Integer.MIN_VALUE)
104 calculateLastPriority(headConstraintMap, lowerPriorityRule, priority);
108 private static THashMap<CHRConstraint, ArrayList<CHRRule>> createHeadConstraintMap(CHRRuleset ruleset) {
109 THashMap<CHRConstraint, ArrayList<CHRRule>> map = new THashMap<CHRConstraint, ArrayList<CHRRule>>();
110 for(CHRRule rule : ruleset.rules)
111 for(CHRLiteral literal : rule.head.literals)
112 if(literal.relation instanceof CHRConstraint) {
113 ArrayList<CHRRule> list = map.get(literal.relation);
115 list = new ArrayList<CHRRule>();
116 map.put((CHRConstraint)literal.relation, list);
119 else if(list.get(list.size()-1) != rule)
125 /*private static void printPriorities(CHRRuleset ruleset) {
126 System.out.println("-------------------------------");
127 for(CHRConstraint constraint : ruleset.constraints) {
128 System.out.print(" [" + constraint.firstPriorityAdded + ".." + constraint.lastPriorityAdded + "]");
129 if(constraint.firstPriorityRemoved != Integer.MAX_VALUE)
130 System.out.print("R[" + constraint.firstPriorityRemoved + ".." + constraint.lastPriorityRemoved + "]");
131 System.out.print(" ");
132 System.out.println(constraint);
134 for(CHRRule rule : ruleset.rules) {
135 System.out.print(rule.priority);
136 System.out.print(" [" + rule.firstPriorityExecuted + ".." + rule.lastPriorityExecuted + "] ");
137 System.out.println(rule);
141 private static void determinePassiveLiterals(CHRRule rule) {
142 for(CHRLiteral literal : rule.head.literals) {
145 CHRConstraint constraint = (CHRConstraint)literal.relation;
146 if(constraint.lastPriorityAdded < rule.priority)
147 literal.passive = true;