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    }