001/** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.activemq.filter; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.HashMap; 022import java.util.Iterator; 023import java.util.List; 024import java.util.Map; 025 026import javax.jms.JMSException; 027 028/** 029 * A MultiExpressionEvaluator is used to evaluate multiple expressions in single 030 * method call. <p/> Multiple Expression/ExpressionListener pairs can be added 031 * to a MultiExpressionEvaluator object. When the MultiExpressionEvaluator 032 * object is evaluated, all the registed Expressions are evaluated and then the 033 * associated ExpressionListener is invoked to inform it of the evaluation 034 * result. <p/> By evaluating multiple expressions at one time, some 035 * optimizations can be made to reduce the number of computations normally 036 * required to evaluate all the expressions. <p/> When this class adds an 037 * Expression it wrapps each node in the Expression's AST with a CacheExpression 038 * object. Then each CacheExpression object (one for each node) is placed in the 039 * cachedExpressions map. The cachedExpressions map allows us to find the sub 040 * expressions that are common across two different expressions. When adding an 041 * Expression in, if a sub Expression of the Expression is allready in the 042 * cachedExpressions map, then instead of wrapping the sub expression in a new 043 * CacheExpression object, we reuse the CacheExpression allready int the map. 044 * <p/> To help illustrate what going on, lets try to give an exmample: If we 045 * denote the AST of a Expression as follows: 046 * [AST-Node-Type,Left-Node,Right-Node], then A expression like: "3*5+6" would 047 * result in "[*,3,[+,5,6]]" <p/> If the [*,3,[+,5,6]] expression is added to 048 * the MultiExpressionEvaluator, it would really be converted to: 049 * [c0,[*,3,[c1,[+,5,6]]]] where c0 and c1 represent the CacheExpression 050 * expression objects that cache the results of the * and the + operation. 051 * Constants and Property nodes are not cached. <p/> If later on we add the 052 * following expression [=,11,[+,5,6]] ("11=5+6") to the 053 * MultiExpressionEvaluator it would be converted to: [c2,[=,11,[c1,[+,5,6]]]], 054 * where c2 is a new CacheExpression object but c1 is the same CacheExpression 055 * used in the previous expression. <p/> When the expressions are evaluated, the 056 * c1 CacheExpression object will only evaluate the [+,5,6] expression once and 057 * cache the resulting value. Hence evauating the second expression costs less 058 * because that [+,5,6] is not done 2 times. <p/> Problems: - cacheing the 059 * values introduces overhead. It may be possible to be smarter about WHICH 060 * nodes in the AST are cached and which are not. - Current implementation is 061 * not thread safe. This is because you need a way to invalidate all the cached 062 * values so that the next evaluation re-evaluates the nodes. By going single 063 * threaded, chache invalidation is done quickly by incrementing a 'view' 064 * counter. When a CacheExpressionnotices it's last cached value was generated 065 * in an old 'view', it invalidates its cached value. 066 * 067 * $Date: 2005/08/27 03:52:36 $ 068 */ 069public class MultiExpressionEvaluator { 070 071 Map<String, ExpressionListenerSet> rootExpressions = new HashMap<String, ExpressionListenerSet>(); 072 Map<Expression, CacheExpression> cachedExpressions = new HashMap<Expression, CacheExpression>(); 073 074 int view; 075 076 /** 077 * A UnaryExpression that caches the result of the nested expression. The 078 * cached value is valid if the 079 * CacheExpression.cview==MultiExpressionEvaluator.view 080 */ 081 public class CacheExpression extends UnaryExpression { 082 short refCount; 083 int cview = view - 1; 084 Object cachedValue; 085 int cachedHashCode; 086 087 public CacheExpression(Expression realExpression) { 088 super(realExpression); 089 cachedHashCode = realExpression.hashCode(); 090 } 091 092 /** 093 * @see org.apache.activemq.filter.Expression#evaluate(MessageEvaluationContext) 094 */ 095 public Object evaluate(MessageEvaluationContext message) throws JMSException { 096 if (view == cview) { 097 return cachedValue; 098 } 099 cachedValue = right.evaluate(message); 100 cview = view; 101 return cachedValue; 102 } 103 104 public int hashCode() { 105 return cachedHashCode; 106 } 107 108 public boolean equals(Object o) { 109 if (o == null) { 110 return false; 111 } 112 return ((CacheExpression)o).right.equals(right); 113 } 114 115 public String getExpressionSymbol() { 116 return null; 117 } 118 119 public String toString() { 120 return right.toString(); 121 } 122 123 } 124 125 /** 126 * Multiple listeners my be interested in the results of a single 127 * expression. 128 */ 129 static class ExpressionListenerSet { 130 Expression expression; 131 List<ExpressionListener> listeners = new ArrayList<ExpressionListener>(); 132 } 133 134 /** 135 * Objects that are interested in the results of an expression should 136 * implement this interface. 137 */ 138 static interface ExpressionListener { 139 void evaluateResultEvent(Expression selector, MessageEvaluationContext message, Object result); 140 } 141 142 /** 143 * Adds an ExpressionListener to a given expression. When evaluate is 144 * called, the ExpressionListener will be provided the results of the 145 * Expression applied to the evaluated message. 146 */ 147 public void addExpressionListner(Expression selector, ExpressionListener c) { 148 ExpressionListenerSet data = rootExpressions.get(selector.toString()); 149 if (data == null) { 150 data = new ExpressionListenerSet(); 151 data.expression = addToCache(selector); 152 rootExpressions.put(selector.toString(), data); 153 } 154 data.listeners.add(c); 155 } 156 157 /** 158 * Removes an ExpressionListener from receiving the results of a given 159 * evaluation. 160 */ 161 public boolean removeEventListner(String selector, ExpressionListener c) { 162 String expKey = selector; 163 ExpressionListenerSet d = rootExpressions.get(expKey); 164 // that selector had not been added. 165 if (d == null) { 166 return false; 167 } 168 // that selector did not have that listeners.. 169 if (!d.listeners.remove(c)) { 170 return false; 171 } 172 173 // If there are no more listeners for this expression.... 174 if (d.listeners.size() == 0) { 175 // Un-cache it... 176 removeFromCache((CacheExpression)d.expression); 177 rootExpressions.remove(expKey); 178 } 179 return true; 180 } 181 182 /** 183 * Finds the CacheExpression that has been associated with an expression. If 184 * it is the first time the Expression is being added to the Cache, a new 185 * CacheExpression is created and associated with the expression. <p/> This 186 * method updates the reference counters on the CacheExpression to know when 187 * it is no longer needed. 188 */ 189 private CacheExpression addToCache(Expression expr) { 190 191 CacheExpression n = cachedExpressions.get(expr); 192 if (n == null) { 193 n = new CacheExpression(expr); 194 cachedExpressions.put(expr, n); 195 if (expr instanceof UnaryExpression) { 196 197 // Cache the sub expressions too 198 UnaryExpression un = (UnaryExpression)expr; 199 un.setRight(addToCache(un.getRight())); 200 201 } else if (expr instanceof BinaryExpression) { 202 203 // Cache the sub expressions too. 204 BinaryExpression bn = (BinaryExpression)expr; 205 bn.setRight(addToCache(bn.getRight())); 206 bn.setLeft(addToCache(bn.getLeft())); 207 208 } 209 } 210 n.refCount++; 211 return n; 212 } 213 214 /** 215 * Removes an expression from the cache. Updates the reference counters on 216 * the CacheExpression object. When the refernce counter goes to zero, the 217 * entry int the Expression to CacheExpression map is removed. 218 * 219 * @param cn 220 */ 221 private void removeFromCache(CacheExpression cn) { 222 cn.refCount--; 223 Expression realExpr = cn.getRight(); 224 if (cn.refCount == 0) { 225 cachedExpressions.remove(realExpr); 226 } 227 if (realExpr instanceof UnaryExpression) { 228 UnaryExpression un = (UnaryExpression)realExpr; 229 removeFromCache((CacheExpression)un.getRight()); 230 } 231 if (realExpr instanceof BinaryExpression) { 232 BinaryExpression bn = (BinaryExpression)realExpr; 233 removeFromCache((CacheExpression)bn.getRight()); 234 } 235 } 236 237 /** 238 * Evaluates the message against all the Expressions added to this object. 239 * The added ExpressionListeners are notified of the result of the 240 * evaluation. 241 * 242 * @param message 243 */ 244 public void evaluate(MessageEvaluationContext message) { 245 Collection<ExpressionListenerSet> expressionListeners = rootExpressions.values(); 246 for (Iterator<ExpressionListenerSet> iter = expressionListeners.iterator(); iter.hasNext();) { 247 ExpressionListenerSet els = iter.next(); 248 try { 249 Object result = els.expression.evaluate(message); 250 for (Iterator<ExpressionListener> iterator = els.listeners.iterator(); iterator.hasNext();) { 251 ExpressionListener l = iterator.next(); 252 l.evaluateResultEvent(els.expression, message, result); 253 } 254 } catch (Throwable e) { 255 e.printStackTrace(); 256 } 257 } 258 } 259}