Merged changes from feature/scl to master.

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / elaboration / chr / analysis / UsageAnalysis.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/analysis/UsageAnalysis.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/analysis/UsageAnalysis.java
new file mode 100644 (file)
index 0000000..3e13e0f
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/analysis/UsageAnalysis.java
@@ -0,0 +1,149 @@
+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