X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Felaboration%2Fchr%2Fanalysis%2FUsageAnalysis.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Felaboration%2Fchr%2Fanalysis%2FUsageAnalysis.java;h=3e13e0f3f8feb32c77dda1fbf9eddc0690e2763b;hb=a8758de5bc19e5adb3f618d3038743a164f09912;hp=0000000000000000000000000000000000000000;hpb=12d9af17384d960b75d58c3935d2b7b46d93e87b;p=simantics%2Fplatform.git

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