TopicMatcherDFAState.java
001 package org.apache.qpid.server.exchange.topic;
002 
003 import org.apache.qpid.framing.AMQShortString;
004 import org.apache.qpid.framing.AMQShortStringTokenizer;
005 
006 import java.util.*;
007 import java.util.concurrent.atomic.AtomicInteger;
008 
009 /*
010 *
011 * Licensed to the Apache Software Foundation (ASF) under one
012 * or more contributor license agreements.  See the NOTICE file
013 * distributed with this work for additional information
014 * regarding copyright ownership.  The ASF licenses this file
015 * to you under the Apache License, Version 2.0 (the
016 * "License"); you may not use this file except in compliance
017 * with the License.  You may obtain a copy of the License at
018 *
019 *   http://www.apache.org/licenses/LICENSE-2.0
020 *
021 * Unless required by applicable law or agreed to in writing,
022 * software distributed under the License is distributed on an
023 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
024 * KIND, either express or implied.  See the License for the
025 * specific language governing permissions and limitations
026 * under the License.
027 *
028 */
029 public class TopicMatcherDFAState
030 {
031     private static final AtomicInteger stateId = new AtomicInteger();
032 
033     private final int _id = stateId.incrementAndGet();
034 
035     private final Collection<TopicMatcherResult> _results;
036     private final Map<TopicWord, TopicMatcherDFAState> _nextStateMap;
037     private static final byte TOPIC_DELIMITTER = (byte)'.';
038 
039 
040     public TopicMatcherDFAState(Map<TopicWord, TopicMatcherDFAState> nextStateMap,
041                                 Collection<TopicMatcherResult> results )
042     {
043         _nextStateMap = nextStateMap;
044         _results = results;
045     }
046 
047 
048     public TopicMatcherDFAState nextState(TopicWord word)
049     {
050         final TopicMatcherDFAState nextState = _nextStateMap.get(word);
051         return nextState == null ? _nextStateMap.get(TopicWord.ANY_WORD: nextState;
052     }
053 
054     public Collection<TopicMatcherResult> terminate()
055     {
056         return _results;
057     }
058 
059 
060     public Collection<TopicMatcherResult> parse(TopicWordDictionary dictionary, AMQShortString routingKey)
061     {
062         return parse(dictionary, routingKey.tokenize(TOPIC_DELIMITTER));
063     }
064 
065     private Collection<TopicMatcherResult> parse(final TopicWordDictionary dictionary,
066                                                  final AMQShortStringTokenizer tokens)
067     {
068         if(!tokens.hasMoreTokens())
069         {
070             return _results;
071         }
072         TopicWord word = dictionary.getWord(tokens.nextToken());
073         TopicMatcherDFAState nextState = _nextStateMap.get(word);
074         if(nextState == null && word != TopicWord.ANY_WORD)
075         {
076             nextState = _nextStateMap.get(TopicWord.ANY_WORD);
077         }
078         if(nextState == null)
079         {
080             return Collections.EMPTY_SET;
081         }
082         // Shortcut if we are at a looping terminal state
083         if((nextState == this&& (_nextStateMap.size() == 1&& _nextStateMap.containsKey(TopicWord.ANY_WORD))
084         {
085             return _results;
086         }
087 
088         return nextState.parse(dictionary, tokens);
089         
090     }
091 
092 
093     public TopicMatcherDFAState  mergeStateMachines(TopicMatcherDFAState otherStateMachine)
094     {
095         Map<Set<TopicMatcherDFAState>, TopicMatcherDFAState> newStateMap= new HashMap<Set<TopicMatcherDFAState>, TopicMatcherDFAState>();
096 
097         Collection<TopicMatcherResult> results;
098 
099         if(_results.isEmpty())
100         {
101             results = otherStateMachine._results;
102         }
103         else if(otherStateMachine._results.isEmpty())
104         {
105             results = _results;
106         }
107         else
108         {
109             results = new HashSet<TopicMatcherResult>(_results);
110             results.addAll(otherStateMachine._results);
111         }
112 
113 
114         final Map<TopicWord, TopicMatcherDFAState> newNextStateMap = new HashMap<TopicWord, TopicMatcherDFAState>();
115 
116         TopicMatcherDFAState newState = new TopicMatcherDFAState(newNextStateMap, results);
117 
118 
119         Set<TopicMatcherDFAState> oldStates = new HashSet<TopicMatcherDFAState>();
120         oldStates.add(this);
121         oldStates.add(otherStateMachine);
122 
123         newStateMap.put(oldStates, newState);
124 
125         mergeStateMachines(oldStates, newNextStateMap, newStateMap);
126 
127         return newState;
128 
129     }
130 
131     private static void mergeStateMachines(
132             final Set<TopicMatcherDFAState> oldStates,
133             final Map<TopicWord, TopicMatcherDFAState> newNextStateMap,
134             final Map<Set<TopicMatcherDFAState>, TopicMatcherDFAState> newStateMap)
135     {
136         Map<TopicWord, Set<TopicMatcherDFAState>> nfaMap = new HashMap<TopicWord, Set<TopicMatcherDFAState>>();
137 
138         for(TopicMatcherDFAState state : oldStates)
139         {
140             Map<TopicWord, TopicMatcherDFAState> map = state._nextStateMap;
141             for(Map.Entry<TopicWord, TopicMatcherDFAState> entry : map.entrySet())
142             {
143                 Set<TopicMatcherDFAState> states = nfaMap.get(entry.getKey());
144                 if(states == null)
145                 {
146                     states = new HashSet<TopicMatcherDFAState>();
147                     nfaMap.put(entry.getKey(), states);
148                 }
149                 states.add(entry.getValue());
150             }
151         }
152 
153         Set<TopicMatcherDFAState> anyWordStates = nfaMap.get(TopicWord.ANY_WORD);
154 
155         for(Map.Entry<TopicWord, Set<TopicMatcherDFAState>> transition : nfaMap.entrySet())
156         {
157             Set<TopicMatcherDFAState> destinations = transition.getValue();
158 
159             if(anyWordStates != null)
160             {
161                 destinations.addAll(anyWordStates);
162             }
163 
164             TopicMatcherDFAState nextState = newStateMap.get(destinations);
165             if(nextState == null)
166             {
167 
168                 if(destinations.size() == 1)
169                 {
170                     nextState = destinations.iterator().next();
171                     newStateMap.put(destinations, nextState);
172                 }
173                 else
174                 {
175                     Collection<TopicMatcherResult> results;
176 
177                     Set<Collection<TopicMatcherResult>> resultSets = new HashSet<Collection<TopicMatcherResult>>();
178                     for(TopicMatcherDFAState destination : destinations)
179                     {
180                         resultSets.add(destination._results);
181                     }
182                     resultSets.remove(Collections.EMPTY_SET);
183                     if(resultSets.size() == 0)
184                     {
185                         results = Collections.EMPTY_SET;
186                     }
187                     else if(resultSets.size() == 1)
188                     {
189                         results = resultSets.iterator().next();
190                     }
191                     else
192                     {
193                         results = new HashSet<TopicMatcherResult>();
194                         for(Collection<TopicMatcherResult> oldResult : resultSets)
195                         {
196                             results.addAll(oldResult);
197                         }
198                     }
199 
200                     final Map<TopicWord, TopicMatcherDFAState> nextStateMap = new HashMap<TopicWord, TopicMatcherDFAState>();
201 
202                     nextState = new TopicMatcherDFAState(nextStateMap, results);
203                     newStateMap.put(destinations, nextState);
204 
205                     mergeStateMachines(
206                             destinations,
207                                        nextStateMap,
208                                        newStateMap);
209 
210 
211                 }
212 
213 
214             }
215             newNextStateMap.put(transition.getKey(),nextState);
216         }
217 
218         // Remove redundant transitions where defined tokenWord has same action as ANY_WORD
219         TopicMatcherDFAState anyWordState = newNextStateMap.get(TopicWord.ANY_WORD);
220         if(anyWordState != null)
221         {
222             List<TopicWord> removeList = new ArrayList<TopicWord>();
223             for(Map.Entry<TopicWord,TopicMatcherDFAState> entry : newNextStateMap.entrySet())
224             {
225                 if(entry.getValue() == anyWordState && entry.getKey() != TopicWord.ANY_WORD)
226                 {
227                     removeList.add(entry.getKey());
228                 }
229             }
230             for(TopicWord removeKey : removeList)
231             {
232                 newNextStateMap.remove(removeKey);
233             }
234         }
235 
236 
237 
238     }
239 
240 
241     public String toString()
242     {
243         StringBuilder transitions = new StringBuilder();
244         for(Map.Entry<TopicWord, TopicMatcherDFAState> entry : _nextStateMap.entrySet())
245         {
246             transitions.append("[ ");
247             transitions.append(entry.getKey());
248             transitions.append("\t ->\t ");
249             transitions.append(entry.getValue()._id);
250             transitions.append(" ]\n");
251         }
252 
253 
254         return "[ State " + _id + " ]\n" + transitions + "\n";
255 
256     }
257 
258     public String reachableStates()
259     {
260         StringBuilder result = new StringBuilder("Start state: " + _id + "\n");
261 
262         SortedSet<TopicMatcherDFAState> reachableStates =
263                 new TreeSet<TopicMatcherDFAState>(new Comparator<TopicMatcherDFAState>()
264                                                         {
265                                                             public int compare(final TopicMatcherDFAState o1, final TopicMatcherDFAState o2)
266                                                             {
267                                                                 return o1._id - o2._id;
268                                                             }
269                                                         });
270         reachableStates.add(this);
271 
272         int count;
273 
274         do
275         {
276             count = reachableStates.size();
277             Collection<TopicMatcherDFAState> originalStates = new ArrayList<TopicMatcherDFAState>(reachableStates);
278             for(TopicMatcherDFAState state : originalStates)
279             {
280                 reachableStates.addAll(state._nextStateMap.values());
281             }
282         }
283         while(reachableStates.size() != count);
284 
285 
286 
287         for(TopicMatcherDFAState state : reachableStates)
288         {
289             result.append(state.toString());
290         }
291 
292         return result.toString();
293     }
294 
295 }