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}