001 package org.apache.qpid.server.exchange.headers;
002
003 import org.apache.qpid.framing.*;
004
005 import java.util.*;
006
007 /*
008 *
009 * Licensed to the Apache Software Foundation (ASF) under one
010 * or more contributor license agreements. See the NOTICE file
011 * distributed with this work for additional information
012 * regarding copyright ownership. The ASF licenses this file
013 * to you under the Apache License, Version 2.0 (the
014 * "License"); you may not use this file except in compliance
015 * with the License. You may obtain a copy of the License at
016 *
017 * http://www.apache.org/licenses/LICENSE-2.0
018 *
019 * Unless required by applicable law or agreed to in writing,
020 * software distributed under the License is distributed on an
021 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
022 * KIND, either express or implied. See the License for the
023 * specific language governing permissions and limitations
024 * under the License.
025 *
026 */
027 public class HeadersParser
028 {
029
030 private final HeaderKeyDictionary _dictionary = new HeaderKeyDictionary();
031 private static final AMQShortString MATCHING_TYPE_KEY = new AMQShortString("x-match");
032 private static final String ANY_MATCHING = "any";
033 private static final AMQShortString RESERVED_KEY_PREFIX = new AMQShortString("x-");
034
035
036 HeadersMatcherDFAState createStateMachine(FieldTable bindingArguments, HeaderMatcherResult result)
037 {
038 String matchingType = bindingArguments.getString(MATCHING_TYPE_KEY);
039 boolean matchAny = matchingType.equalsIgnoreCase(ANY_MATCHING);
040 if(matchAny)
041 {
042 return createStateMachineForAnyMatch(bindingArguments, result);
043 }
044 else
045 {
046 return createStateMachineForAllMatch(bindingArguments, result);
047 }
048
049
050 }
051
052
053 private HeadersMatcherDFAState createStateMachineForAnyMatch(final FieldTable bindingArguments,
054 final HeaderMatcherResult result)
055 {
056
057 // DFAs for "any" matches have only two states, "not-matched" and "matched"... they start in the former
058 // and upon meeting any of the criteria they move to the latter
059
060 //noinspection unchecked
061 final HeadersMatcherDFAState successState =
062 new HeadersMatcherDFAState(Collections.EMPTY_MAP,Collections.singleton(result),_dictionary);
063
064 Map<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>> nextStateMap =
065 new HashMap<HeaderKey, Map<AMQTypedValue, HeadersMatcherDFAState>>();
066
067 Set<AMQShortString> seenKeys = new HashSet<AMQShortString>();
068
069 Iterator<Map.Entry<AMQShortString, AMQTypedValue>> tableIterator = bindingArguments.iterator();
070
071 while(tableIterator.hasNext())
072 {
073 final Map.Entry<AMQShortString, AMQTypedValue> entry = tableIterator.next();
074 final AMQShortString key = entry.getKey();
075 final AMQTypedValue value = entry.getValue();
076
077
078 if(seenKeys.add(key) && !key.startsWith(RESERVED_KEY_PREFIX))
079 {
080 final AMQType type = value.getType();
081
082 final HeaderKey headerKey = _dictionary.getOrCreate(key);
083 final Map<AMQTypedValue, HeadersMatcherDFAState> valueMap;
084
085 if(type == AMQType.VOID ||
086 ((type == AMQType.ASCII_STRING || type == AMQType.WIDE_STRING) && ((CharSequence)value.getValue()).length() == 0))
087 {
088 valueMap = Collections.singletonMap(null,successState);
089
090 }
091 else
092 {
093 valueMap = Collections.singletonMap(value,successState);
094 }
095 nextStateMap.put(headerKey,valueMap);
096
097 }
098
099 }
100
101 if(seenKeys.size() == 0)
102 {
103 return successState;
104 }
105 else
106 {
107 return new HeadersMatcherDFAState(nextStateMap,Collections.EMPTY_SET,_dictionary);
108 }
109
110
111 }
112
113
114 private HeadersMatcherDFAState createStateMachineForAllMatch(final FieldTable bindingArguments,
115 final HeaderMatcherResult result)
116 {
117 // DFAs for "all" matches have a "success" state, a "fail" state, and states for every subset of
118 // matches which are possible, starting with the empty subset. For example if we have a binding
119 // { x-match="all"
120 // a=1
121 // b=1
122 // c=1
123 // d=1 }
124 // Then we would have the following states
125 // (1) Seen none of a, b, c, or d
126 // (2) Seen a=1 ; none of b,c, or d
127 // (3) Seen b=1 ; none of a,c, or d
128 // (4) Seen c=1 ; none of a,b, or d
129 // (5) Seen d=1 ; none of a,b, or c
130 // (6) Seen a=1,b=1 ; none of c,d
131 // (7) Seen a=1,c=1 ; none of b,d
132 // (8) Seen a=1,d=1 ; none of b,c
133 // (9) Seen b=1,c=1 ; none of a,d
134 //(10) Seen b=1,d=1 ; none of c,d
135 //(11) Seen c=1,d=1 ; none of a,b
136 //(12) Seen a=1,b=1,c=1 ; not d
137 //(13) Seen a=1,b=1,d=1 ; not c
138 //(14) Seen a=1,c=1,d=1 ; not b
139 //(15) Seen b=1,c=1,d=1 ; not a
140 //(16) success
141 //(17) fail
142 //
143 // All states but (16) can transition to (17); additionally:
144 // (1) can transition to (2),(3),(4),(5)
145 // (2) can transition to (6),(7),(8)
146 // (3) can transition to (6),(9),(10)
147 // (4) can transition to (7),(9),(11)
148 // (5) can transition to (8),(10),(11)
149 // (6) can transition to (12),(13)
150 // (7) can transition to (12),(14)
151 // (8) can transition to (13),(14)
152 // (9) can transition to (12),(15)
153 //(10) can transition to (13),(15)
154 //(11) can transition to (14),(15)
155 //(12)-(15) can transition to (16)
156
157 Set<AMQShortString> seenKeys = new HashSet<AMQShortString>();
158 List<KeyValuePair> requiredTerms = new ArrayList<KeyValuePair>(bindingArguments.size());
159
160 Iterator<Map.Entry<AMQShortString, AMQTypedValue>> tableIterator = bindingArguments.iterator();
161
162
163
164 while(tableIterator.hasNext())
165 {
166 final Map.Entry<AMQShortString, AMQTypedValue> entry = tableIterator.next();
167 final AMQShortString key = entry.getKey();
168 final AMQTypedValue value = entry.getValue();
169
170
171 if(seenKeys.add(key) && !key.startsWith(RESERVED_KEY_PREFIX))
172 {
173 final AMQType type = value.getType();
174
175 if(type == AMQType.VOID ||
176 ((type == AMQType.ASCII_STRING || type == AMQType.WIDE_STRING) && ((CharSequence)value.getValue()).length() == 0))
177 {
178 requiredTerms.add(new KeyValuePair(_dictionary.getOrCreate(key),null));
179 }
180 else
181 {
182 requiredTerms.add(new KeyValuePair(_dictionary.getOrCreate(key),value));
183 }
184 }
185
186 }
187
188 final HeadersMatcherDFAState successState =
189 new HeadersMatcherDFAState(Collections.EMPTY_MAP,Collections.singleton(result),_dictionary);
190
191 final HeadersMatcherDFAState failState =
192 new HeadersMatcherDFAState(Collections.EMPTY_MAP,Collections.EMPTY_SET,_dictionary);
193
194 Map<Set<KeyValuePair>, HeadersMatcherDFAState> notSeenTermsToStateMap =
195 new HashMap<Set<KeyValuePair>, HeadersMatcherDFAState>();
196
197 notSeenTermsToStateMap.put(Collections.EMPTY_SET, successState);
198
199
200 final int numberOfTerms = requiredTerms.size();
201
202 for(int numMissingTerms = 1; numMissingTerms <= numberOfTerms; numMissingTerms++)
203 {
204 int[] pos = new int[numMissingTerms];
205 for(int i = 0; i < numMissingTerms; i++)
206 {
207 pos[i] = i;
208 }
209
210 final int maxTermValue = (numberOfTerms - (numMissingTerms - 1));
211
212 while(pos[0] < maxTermValue)
213 {
214
215 Set<KeyValuePair> stateSet = new HashSet<KeyValuePair>();
216 for(int posIndex = 0; posIndex < pos.length; posIndex++)
217 {
218 stateSet.add(requiredTerms.get(pos[posIndex]));
219 }
220
221 final Map<HeaderKey, Map<AMQTypedValue,HeadersMatcherDFAState>> nextStateMap =
222 new HashMap<HeaderKey, Map<AMQTypedValue,HeadersMatcherDFAState>>();
223
224
225 for(int posIndex = 0; posIndex < pos.length; posIndex++)
226 {
227 KeyValuePair nextTerm = requiredTerms.get(pos[posIndex]);
228 HashSet<KeyValuePair> nextStateSet =
229 new HashSet<KeyValuePair>(stateSet);
230 nextStateSet.remove(nextTerm);
231
232 Map<AMQTypedValue, HeadersMatcherDFAState> valueToStateMap =
233 new HashMap<AMQTypedValue, HeadersMatcherDFAState>();
234 nextStateMap.put(nextTerm._key, valueToStateMap);
235
236 valueToStateMap.put( nextTerm._value,notSeenTermsToStateMap.get(nextStateSet));
237 if(nextTerm._value != null)
238 {
239 valueToStateMap.put(null, failState);
240 }
241
242
243 }
244
245
246 HeadersMatcherDFAState newState = new HeadersMatcherDFAState(nextStateMap, Collections.EMPTY_SET, _dictionary);
247
248 notSeenTermsToStateMap.put(stateSet, newState);
249
250 int i = numMissingTerms;
251 while(i-- != 0)
252 {
253 if(++pos[i] <= numberOfTerms -(numMissingTerms-i))
254 {
255 int k = pos[i];
256 for(int j = i+1; j < numMissingTerms; j++)
257 {
258 pos[j] = ++k;
259 }
260 break;
261 }
262 }
263 }
264
265
266
267
268 }
269
270
271 return notSeenTermsToStateMap.get(new HashSet<KeyValuePair>(requiredTerms));
272
273
274
275 }
276
277 public static void main(String[] args) throws AMQFrameDecodingException
278 {
279
280 FieldTable bindingTable = new FieldTable();
281
282 bindingTable.setString(new AMQShortString("x-match"),"all");
283 bindingTable.setInteger("a",1);
284 bindingTable.setVoid(new AMQShortString("b"));
285 bindingTable.setString("c","");
286 bindingTable.setInteger("d",4);
287 bindingTable.setInteger("e",1);
288
289
290
291 FieldTable bindingTable2 = new FieldTable();
292 bindingTable2.setString(new AMQShortString("x-match"),"all");
293 bindingTable2.setInteger("a",1);
294 bindingTable2.setVoid(new AMQShortString("b"));
295 bindingTable2.setString("c","");
296 bindingTable2.setInteger("d",4);
297 bindingTable2.setInteger("e",1);
298 bindingTable2.setInteger("f",1);
299
300
301 FieldTable table = new FieldTable();
302 table.setInteger("a",1);
303 table.setInteger("b",2);
304 table.setString("c","");
305 table.setInteger("d",4);
306 table.setInteger("e",1);
307 table.setInteger("f",1);
308 table.setInteger("h",1);
309 table.setInteger("i",1);
310 table.setInteger("j",1);
311 table.setInteger("k",1);
312 table.setInteger("l",1);
313
314 org.apache.mina.common.ByteBuffer buffer = org.apache.mina.common.ByteBuffer.allocate( (int) table.getEncodedSize());
315 EncodingUtils.writeFieldTableBytes(buffer, table);
316 buffer.flip();
317
318 FieldTable table2 = EncodingUtils.readFieldTable(buffer);
319
320
321
322 FieldTable bindingTable3 = new FieldTable();
323 bindingTable3.setString(new AMQShortString("x-match"),"any");
324 bindingTable3.setInteger("a",1);
325 bindingTable3.setInteger("b",3);
326
327
328 FieldTable bindingTable4 = new FieldTable();
329 bindingTable4.setString(new AMQShortString("x-match"),"any");
330 bindingTable4.setVoid(new AMQShortString("a"));
331
332
333 FieldTable bindingTable5 = new FieldTable();
334 bindingTable5.setString(new AMQShortString("x-match"),"all");
335 bindingTable5.setString(new AMQShortString("h"),"hello");
336
337 for(int i = 0; i < 100; i++)
338 {
339 printMatches(new FieldTable[] {bindingTable5} , table2);
340 }
341
342
343
344 }
345
346
347
348 private static void printMatches(final FieldTable[] bindingKeys, final FieldTable routingKey)
349 {
350 HeadersMatcherDFAState sm = null;
351 Map<HeaderMatcherResult, String> resultMap = new HashMap<HeaderMatcherResult, String>();
352
353 HeadersParser parser = new HeadersParser();
354
355 for(int i = 0; i < bindingKeys.length; i++)
356 {
357 HeaderMatcherResult r = new HeaderMatcherResult();
358 resultMap.put(r, bindingKeys[i].toString());
359
360
361 if(i==0)
362 {
363 sm = parser.createStateMachine(bindingKeys[i], r);
364 }
365 else
366 {
367 sm = sm.mergeStateMachines(parser.createStateMachine(bindingKeys[i], r));
368 }
369 }
370
371 Collection<HeaderMatcherResult> results = null;
372 long beforeTime = System.currentTimeMillis();
373 for(int i = 0; i < 1000000; i++)
374 {
375 routingKey.size();
376
377 assert sm != null;
378 results = sm.match(routingKey);
379
380 }
381 long elapsed = System.currentTimeMillis() - beforeTime;
382 System.out.println("1000000 Iterations took: " + elapsed);
383 Collection<String> resultStrings = new ArrayList<String>();
384
385 assert results != null;
386 for(HeaderMatcherResult result : results)
387 {
388 resultStrings.add(resultMap.get(result));
389 }
390
391 final ArrayList<String> nonMatches = new ArrayList<String>();
392 for(FieldTable key : bindingKeys)
393 {
394 nonMatches.add(key.toString());
395 }
396 nonMatches.removeAll(resultStrings);
397 System.out.println("\""+routingKey+"\" matched with " + resultStrings + " DID NOT MATCH with " + nonMatches);
398
399
400 }
401
402
403 public final static class KeyValuePair
404 {
405 public final HeaderKey _key;
406 public final AMQTypedValue _value;
407 private final int _hashCode;
408
409 public KeyValuePair(final HeaderKey key, final AMQTypedValue value)
410 {
411 _key = key;
412 _value = value;
413 int hash = (1 + 31 * _key.hashCode());
414 if(_value != null)
415 {
416 hash+=_value.hashCode();
417 }
418 _hashCode = hash;
419 }
420
421 public int hashCode()
422 {
423 return _hashCode;
424 }
425
426 public boolean equals(Object o)
427 {
428 KeyValuePair other = (KeyValuePair)o;
429 return (_key == other._key) && (_value == null ? other._value == null : _value.equals(other._value));
430 }
431
432
433 public String toString()
434 {
435 return "{" + _key + " -> " + _value + "}";
436 }
437
438 }
439 }
|