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 */
017 package org.apache.activemq.filter;
018
019 import java.util.ArrayList;
020 import java.util.Collection;
021 import java.util.HashMap;
022 import java.util.Iterator;
023 import java.util.List;
024 import java.util.Map;
025
026 import 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 */
069 public 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 }