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 }
|