bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/analysis/UsageAnalysis.java

   1 package org.simantics.scl.compiler.elaboration.chr.analysis;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 \r
   5 import org.simantics.scl.compiler.elaboration.chr.CHRLiteral;\r
   6 import org.simantics.scl.compiler.elaboration.chr.CHRRule;\r
   7 import org.simantics.scl.compiler.elaboration.chr.CHRRuleset;\r
   8 import org.simantics.scl.compiler.elaboration.chr.relations.CHRConstraint;\r
   9 \r
  10 import gnu.trove.map.hash.THashMap;\r
  11 \r
  12 public class UsageAnalysis {\r
  13     public static void analyzeUsage(CHRRuleset ruleset) {\r
  14         THashMap<CHRConstraint,ArrayList<CHRRule>> headConstraintMap = createHeadConstraintMap(ruleset);\r
  15         calculateFirstPriorities(ruleset, headConstraintMap);\r
  16         calculateLastPriorities(ruleset, headConstraintMap);\r
  17         for(CHRRule rule : ruleset.rules)\r
  18             determinePassiveLiterals(rule);\r
  19         //printPriorities(ruleset);\r
  20     }\r
  21 \r
  22     private static void calculateFirstPriorities(CHRRuleset ruleset,\r
  23             THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {\r
  24         for(CHRRule rule : ruleset.rules)\r
  25             rule.firstPriorityExecuted = Integer.MAX_VALUE;\r
  26         for(CHRConstraint constraint : ruleset.constraints) {\r
  27             constraint.firstPriorityAdded = Integer.MAX_VALUE;\r
  28             constraint.firstPriorityRemoved = Integer.MAX_VALUE;\r
  29         }\r
  30         for(CHRRule rule : ruleset.rules)\r
  31             calculateFirstPriority(headConstraintMap, rule);\r
  32     }\r
  33 \r
  34     private static void calculateFirstPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap, CHRRule rule) {\r
  35         int result = rule.priority;\r
  36         for(CHRLiteral literal : rule.head.literals)\r
  37             if(literal.relation instanceof CHRConstraint) {\r
  38                 CHRConstraint constraint = (CHRConstraint)literal.relation;\r
  39                 int constraintPriority = constraint.firstPriorityAdded;\r
  40                 if(constraintPriority == Integer.MAX_VALUE)\r
  41                     return;\r
  42                 result = Math.max(result, constraint.firstPriorityAdded);\r
  43             }\r
  44         rule.firstPriorityExecuted = result;\r
  45         for(CHRLiteral literal : rule.head.literals)\r
  46             if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {\r
  47                 CHRConstraint constraint = (CHRConstraint)literal.relation;\r
  48                 if(constraint.firstPriorityRemoved != Integer.MAX_VALUE)\r
  49                     continue;\r
  50                 constraint.firstPriorityRemoved = result;\r
  51             }\r
  52         for(CHRLiteral literal : rule.body.literals)\r
  53             if(literal.relation instanceof CHRConstraint) {\r
  54                 CHRConstraint constraint = (CHRConstraint)literal.relation;\r
  55                 if(constraint.firstPriorityAdded != Integer.MAX_VALUE)\r
  56                     continue;\r
  57                 constraint.firstPriorityAdded = result;\r
  58                 ArrayList<CHRRule> list = headConstraintMap.get(constraint);\r
  59                 if(list == null)\r
  60                     continue;\r
  61                 for(CHRRule lowerPriorityRule : list)\r
  62                     if(lowerPriorityRule.priority < rule.priority)\r
  63                         calculateFirstPriority(headConstraintMap, lowerPriorityRule);\r
  64             }\r
  65     }\r
  66 \r
  67     private static void calculateLastPriorities(CHRRuleset ruleset,\r
  68             THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap) {\r
  69         for(CHRRule rule : ruleset.rules)\r
  70             rule.lastPriorityExecuted = Integer.MIN_VALUE;\r
  71         for(CHRConstraint constraint : ruleset.constraints) {\r
  72             constraint.lastPriorityAdded = Integer.MIN_VALUE;\r
  73             constraint.lastPriorityRemoved = Integer.MIN_VALUE;\r
  74         }\r
  75         for(int i=ruleset.rules.size()-1;i>=0;--i) {\r
  76             CHRRule rule = ruleset.rules.get(i);\r
  77             if(rule.lastPriorityExecuted == Integer.MIN_VALUE)\r
  78                 calculateLastPriority(headConstraintMap, rule, rule.priority);\r
  79         }\r
  80     }\r
  81 \r
  82     private static void calculateLastPriority(THashMap<CHRConstraint, ArrayList<CHRRule>> headConstraintMap,\r
  83             CHRRule rule, int priority) {\r
  84         rule.lastPriorityExecuted = priority;\r
  85         for(CHRLiteral literal : rule.head.literals)\r
  86             if(literal.killAfterMatch && literal.relation instanceof CHRConstraint) {\r
  87                 CHRConstraint constraint = (CHRConstraint)literal.relation;\r
  88                 if(constraint.lastPriorityRemoved != Integer.MIN_VALUE)\r
  89                     continue;\r
  90                 constraint.lastPriorityRemoved = priority;\r
  91             }\r
  92         for(CHRLiteral literal : rule.body.literals)\r
  93             if(literal.relation instanceof CHRConstraint) {\r
  94                 CHRConstraint constraint = (CHRConstraint)literal.relation;\r
  95                 if(constraint.lastPriorityAdded != Integer.MIN_VALUE)\r
  96                     continue;\r
  97                 constraint.lastPriorityAdded = priority;\r
  98                 ArrayList<CHRRule> list = headConstraintMap.get(constraint);\r
  99                 if(list == null)\r
 100                     continue;\r
 101                 for(CHRRule lowerPriorityRule : list)\r
 102                     if(lowerPriorityRule.lastPriorityExecuted == Integer.MIN_VALUE)\r
 103                         calculateLastPriority(headConstraintMap, lowerPriorityRule, priority);\r
 104             }\r
 105     }\r
 106 \r
 107     private static THashMap<CHRConstraint, ArrayList<CHRRule>> createHeadConstraintMap(CHRRuleset ruleset) {\r
 108         THashMap<CHRConstraint, ArrayList<CHRRule>> map = new THashMap<CHRConstraint, ArrayList<CHRRule>>(); \r
 109         for(CHRRule rule : ruleset.rules)\r
 110             for(CHRLiteral literal : rule.head.literals)\r
 111                 if(literal.relation instanceof CHRConstraint) {\r
 112                     ArrayList<CHRRule> list = map.get(literal.relation);\r
 113                     if(list == null) {\r
 114                         list = new ArrayList<CHRRule>();\r
 115                         map.put((CHRConstraint)literal.relation, list);\r
 116                         list.add(rule);\r
 117                     }\r
 118                     else if(list.get(list.size()-1) != rule)\r
 119                         list.add(rule);\r
 120                 }\r
 121         return map;\r
 122     }\r
 123     \r
 124     private static void printPriorities(CHRRuleset ruleset) {\r
 125         System.out.println("-------------------------------");\r
 126         for(CHRConstraint constraint : ruleset.constraints) {\r
 127             System.out.print(" [" + constraint.firstPriorityAdded + ".." + constraint.lastPriorityAdded + "]");\r
 128             if(constraint.firstPriorityRemoved != Integer.MAX_VALUE)\r
 129                 System.out.print("R[" + constraint.firstPriorityRemoved + ".." + constraint.lastPriorityRemoved + "]");\r
 130             System.out.print(" ");\r
 131             System.out.println(constraint);\r
 132         }\r
 133         for(CHRRule rule : ruleset.rules) {\r
 134             System.out.print(rule.priority);\r
 135             System.out.print(" [" + rule.firstPriorityExecuted + ".." + rule.lastPriorityExecuted + "] ");\r
 136             System.out.println(rule);\r
 137         }\r
 138     }\r
 139 \r
 140     private static void determinePassiveLiterals(CHRRule rule) {\r
 141         for(CHRLiteral literal : rule.head.literals) {\r
 142             if(literal.passive)\r
 143                 continue;\r
 144             CHRConstraint constraint = (CHRConstraint)literal.relation;\r
 145             if(constraint.lastPriorityAdded < rule.priority)\r
 146                 literal.passive = true;\r
 147         }\r
 148     }\r
 149 }\r