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