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    }