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         if(!ruleset.extensible)
  18             for(CHRRule rule : ruleset.rules)
  19                 determinePassiveLiterals(rule);
  20         //printPriorities(ruleset);
  21     }
  22     /*
  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;
  30         }
  31         for(CHRRule rule : ruleset.rules)
  32             calculateFirstPriority(headConstraintMap, rule);
  33     }
  34
  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)
  42                     return;
  43                 result = Math.max(result, constraintPriority);
  44             }
  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;
  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                         // We know here that previous call to lowerPriorityRule "failed",
  64                         // because constraint.firstPriorityAdded was previously Integer.MAX_VALUE
  65                         calculateFirstPriority(headConstraintMap, lowerPriorityRule);
  66             }
  67     }
  68     */
  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;
  76         }
  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);
  81         }
  82     }
  83
  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;
  92             }
  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)
  97                     continue;
  98                 constraint.lastPriorityAdded = priority;
  99                 ArrayList<CHRRule> list = headConstraintMap.get(constraint);
 100                 if(list == null)
 101                     continue;
 102                 for(CHRRule lowerPriorityRule : list)
 103                     if(lowerPriorityRule.lastPriorityExecuted == Integer.MIN_VALUE)
 104                         calculateLastPriority(headConstraintMap, lowerPriorityRule, priority);
 105             }
 106     }
 107
 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);
 114                     if(list == null) {
 115                         list = new ArrayList<CHRRule>();
 116                         map.put((CHRConstraint)literal.relation, list);
 117                         list.add(rule);
 118                     }
 119                     else if(list.get(list.size()-1) != rule)
 120                         list.add(rule);
 121                 }
 122         return map;
 123     }
 124
 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);
 133         }
 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);
 138         }
 139     }*/
 140
 141     private static void determinePassiveLiterals(CHRRule rule) {
 142         for(CHRLiteral literal : rule.head.literals) {
 143             if(literal.passive)
 144                 continue;
 145             CHRConstraint constraint = (CHRConstraint)literal.relation;
 146             if(constraint.lastPriorityAdded < rule.priority)
 147                 literal.passive = true;
 148         }
 149     }
 150 }