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

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