Java > Open Source Codes > org > cojen > util > PatternMatcher


1 /*
2  * Copyright 2004 Brian S O'Neill
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.cojen.util;
18
19 import java.io.PrintStream ;
20 import java.lang.reflect.Constructor ;
21 import java.lang.reflect.InvocationTargetException ;
22 import java.util.AbstractList ;
23 import java.util.ArrayList ;
24 import java.util.Arrays ;
25 import java.util.Comparator ;
26 import java.util.List ;
27 import java.util.Map ;
28 import java.util.Stack ;
29 import org.cojen.classfile.ClassFile;
30 import org.cojen.classfile.CodeBuilder;
31 import org.cojen.classfile.Label;
32 import org.cojen.classfile.LocalVariable;
33 import org.cojen.classfile.MethodInfo;
34 import org.cojen.classfile.Modifiers;
35 import org.cojen.classfile.Opcode;
36 import org.cojen.classfile.TypeDesc;
37
38 /**
39  * Provides fast matching of strings against patterns containing wildcards.
40  * An ordinary map must be supplied in order to create a PatternMatcher. The
41  * map keys must be strings. Asterisks (*) are treated as wildcard characters.
42  *
43  * @author Brian S O'Neill
44  */
45 public abstract class PatternMatcher {
46     private static final int[] NO_POSITIONS = new int[0];
47
48     // Maps pattern sets to auto-generated classes.
49 private static Map cPatternMatcherClasses = new SoftValuedHashMap();
50
51     public static synchronized PatternMatcher forPatterns(Map patternMap) {
52         Maker maker = new Maker(patternMap);
53         Class clazz = (Class )cPatternMatcherClasses.get(maker.getKey());
54
55         if (clazz == null) {
56             Class patternMatcherClass = PatternMatcher.class;
57
58             ClassInjector ci = ClassInjector.create
59                 (patternMatcherClass.getName(),
60                  patternMatcherClass.getClassLoader());
61             
62             ClassFile cf = maker.createClassFile(ci.getClassName());
63             clazz = ci.defineClass(cf);
64
65             cPatternMatcherClasses.put(maker.getKey(), clazz);
66         }
67
68         try {
69             Constructor ctor =
70                 clazz.getConstructor(new Class []{Object [].class});
71             return (PatternMatcher)ctor.newInstance
72                 (new Object []{maker.getMappedValues()});
73         } catch (NoSuchMethodException e) {
74             throw new InternalError (e.toString());
75         } catch (InstantiationException e) {
76             throw new InternalError (e.toString());
77         } catch (IllegalAccessException e) {
78             throw new InternalError (e.toString());
79         } catch (InvocationTargetException e) {
80             throw new InternalError (e.toString());
81         }
82     }
83
84     protected final Object [] mValues;
85
86     protected PatternMatcher(Object [] values) {
87         mValues = values;
88     }
89
90     /**
91      * Returns null if no match.
92      */
93     public Result getMatch(String lookup) {
94         int strLen = lookup.length();
95         char[] chars = new char[strLen + 1];
96         lookup.getChars(0, strLen, chars, 0);
97         chars[strLen] = '\uffff';
98         
99         TinyList resultList = new TinyList();
100         fillMatchResults(chars, 1, resultList);
101
102         return (Result)resultList.mElement;
103     }
104
105     /**
106      * Returns an empty array if no matches.
107      *
108      * @param limit maximum number of results to return
109      */
110     public Result[] getMatches(String lookup, int limit) {
111         int strLen = lookup.length();
112         char[] chars = new char[strLen + 1];
113         lookup.getChars(0, strLen, chars, 0);
114         chars[strLen] = '\uffff';
115         
116         List resultList = new ArrayList ();
117         fillMatchResults(chars, limit, resultList);
118
119         return (Result[])resultList.toArray(new Result[resultList.size()]);
120     }
121
122     protected abstract void fillMatchResults(char[] lookup,
123                                              int limit, List results);
124
125     // Returns false if no more results should be added.
126 protected static boolean addMatchResult(int limit,
127                                             List results,
128                                             String pattern,
129                                             Object value,
130                                             int[] positions,
131                                             int len)
132     {
133         int size = results.size();
134         if (size < limit) {
135             if (positions == null || len == 0) {
136                 positions = NO_POSITIONS;
137             } else {
138                 int[] original = positions;
139                 positions = new int[len];
140                 for (int i=0; i<len; i++) {
141                     positions[i] = original[i];
142                 }
143             }
144             results.add(new Result(pattern, value, positions));
145             return size + 1 < limit;
146         } else {
147             return false;
148         }
149     }
150
151     public static class Result {
152         private final String mPattern;
153         private final Object mValue;
154         private final int[] mPositions;
155
156         Result(String pattern, Object value, int[] positions) {
157             mPattern = pattern;
158             mValue = value;
159             mPositions = positions;
160         }
161
162         public String getPattern() {
163             return mPattern;
164         }
165
166         /**
167          * Returns the value associated with the matched pattern.
168          */
169         public Object getValue() {
170             return mValue;
171         }
172
173         /**
174          * Returns the indexes used to parse the lookup string at wildcard
175          * positions in order for it to match the pattern. Array length is
176          * always double the number of wildcards in the pattern. Every even
177          * element is the start index (inclusive) of a wildcard match, and
178          * every odd element is the end index (exclusive) of a wildcard match.
179          */
180         public int[] getWildcardPositions() {
181             return mPositions;
182         }
183     }
184
185     private static class Maker {
186         private PatternNode mPatternRoot;
187         private Object mKey;
188         private Object [] mMappedValues;
189         private int mMaxWildPerKey;
190
191         private TypeDesc mIntType;
192         private TypeDesc mBooleanType;
193         private TypeDesc mListType;
194         private TypeDesc mStringType;
195         private TypeDesc mObjectType;
196         private TypeDesc mIntArrayType;
197
198         private CodeBuilder mBuilder;
199         private LocalVariable mLookupLocal;
200         private LocalVariable mLimitLocal;
201         private LocalVariable mResultsLocal;
202         private LocalVariable mPositionsLocal;
203         private LocalVariable mIndexLocal;
204         private Stack mTempLocals;
205         private Label mReturnLabel;
206
207         private int mReferenceLine;
208
209         Maker(Map patternMap) {
210             String [] keys = (String [])patternMap.keySet().toArray(new String [0]);
211
212             for (int i=0; i<keys.length; i++) {
213                 String key = keys[i];
214                 // Ensure terminating patterns end in the special
215 // terminator char.
216 if (!key.endsWith("*")) {
217                     keys[i] = key.concat("\uffff");
218                 }
219             }
220
221             // Sort the keys in a special order that ensures correct
222 // "closest match" semantics.
223 Arrays.sort(keys, new PatternComparator());
224
225             mMappedValues = new Object [keys.length];
226             for (int i=0; i<keys.length; i++) {
227                 String key = keys[i];
228                 if (key.endsWith("\uffff")) {
229                     key = key.substring(0, key.length() - 1);
230                 }
231                 mMappedValues[i] = patternMap.get(key);
232             }
233             
234             // Build tree structure for managing pattern matching.
235 mPatternRoot = new PatternNode();
236             for (int i=0; i<keys.length; i++) {
237                 String key = keys[i];
238                 mPatternRoot.buildPathTo(key, i);
239             }
240
241             mMaxWildPerKey = mPatternRoot.getMaxWildcardCount();
242
243             mKey = KeyFactory.createKey(keys);
244         }
245
246         public Object getKey() {
247             return mKey;
248         }
249
250         public Object getMappedValues() {
251             return mMappedValues;
252         }
253
254         public ClassFile createClassFile(String className) {
255             ClassFile cf = new ClassFile(className, PatternMatcher.class);
256             cf.markSynthetic();
257             cf.setSourceFile(PatternMatcher.class.getName());
258             
259             // constructor
260 TypeDesc objectArrayType = TypeDesc.OBJECT.toArrayType();
261             TypeDesc[] params = {objectArrayType};
262             MethodInfo mi = cf.addConstructor(Modifiers.PUBLIC, params);
263             mBuilder = new CodeBuilder(mi);
264             mBuilder.loadThis();
265             mBuilder.loadLocal(mBuilder.getParameter(0));
266             mBuilder.invokeSuperConstructor(params);
267             mBuilder.returnVoid();
268
269             mIntType = TypeDesc.INT;
270             mBooleanType = TypeDesc.BOOLEAN;
271             mListType = TypeDesc.forClass(List .class);
272             mStringType = TypeDesc.STRING;
273             mObjectType = TypeDesc.OBJECT;
274             mIntArrayType = TypeDesc.INT.toArrayType();
275
276             // fillMatchResults method
277 TypeDesc charArrayType = TypeDesc.CHAR.toArrayType();
278             params = new TypeDesc[]{charArrayType, mIntType, mListType};
279             mi = cf.addMethod(Modifiers.PUBLIC, "fillMatchResults", null, params);
280             mBuilder = new CodeBuilder(mi);
281
282             mLookupLocal = mBuilder.getParameter(0);
283             mLimitLocal = mBuilder.getParameter(1);
284             mResultsLocal = mBuilder.getParameter(2);
285             mPositionsLocal = mBuilder.createLocalVariable("positions", mIntArrayType);
286             mIndexLocal = mBuilder.createLocalVariable("index", mIntType);
287
288             mBuilder.mapLineNumber(++mReferenceLine);
289
290             mBuilder.loadConstant(mMaxWildPerKey * 2);
291             mBuilder.newObject(mIntArrayType);
292             mBuilder.storeLocal(mPositionsLocal);
293
294             mBuilder.loadConstant(0);
295             mBuilder.storeLocal(mIndexLocal);
296             mTempLocals = new Stack ();
297             mReturnLabel = mBuilder.createLabel();
298
299             generateBranches(mPatternRoot, -1, 0);
300
301             mReturnLabel.setLocation();
302             mBuilder.returnVoid();
303
304             return cf;
305         }
306
307         private void generateBranches(PatternNode node, int depth,
308                                       int posIndex) {
309             generateBranches(node, depth, posIndex, null);
310         }
311
312         private void generateBranches(PatternNode node, int depth,
313                                       int posIndex,
314                                       LocalVariable tempChar) {
315             int c = node.mChar;
316             List subNodes = node.mSubNodes;
317
318             mBuilder.mapLineNumber(++mReferenceLine);
319
320             if (c == '*') {
321                 LocalVariable savedIndex;
322                 
323                 if (mTempLocals.isEmpty()) {
324                     savedIndex =
325                         mBuilder.createLocalVariable("temp", mIntType);
326                 } else {
327                     savedIndex = (LocalVariable)mTempLocals.pop();
328                 }
329                 
330                 mBuilder.loadLocal(mIndexLocal);
331                 mBuilder.storeLocal(savedIndex);
332                 
333                 // Save position of wildcard start.
334 mBuilder.loadLocal(mPositionsLocal);
335                 mBuilder.loadConstant(posIndex);
336                 mBuilder.loadLocal(mIndexLocal);
337                 if (depth > 0) {
338                     mBuilder.loadConstant(depth);
339                     mBuilder.math(Opcode.IADD);
340                 }
341                 mBuilder.storeToArray(TypeDesc.INT);
342                 
343                 if (subNodes == null) {
344                     generateWildcard(null, depth, posIndex + 2);
345                 } else {
346                     int size = subNodes.size();
347                     for (int i=0; i<size; i++) {
348                         generateWildcard((PatternNode)subNodes.get(i),
349                                          depth, posIndex + 2);
350                         mBuilder.loadLocal(savedIndex);
351                         mBuilder.storeLocal(mIndexLocal);
352                     }
353                 }
354                 
355                 mTempLocals.push(savedIndex);
356
357                 if (node.mPattern != null) {
358                     generateAddMatchResult(node);
359                 }
360
361                 return;
362             }
363
364             Label noMatch = mBuilder.createLabel();
365
366             if (c >= 0) {
367                 if (tempChar != null) {
368                     mBuilder.loadLocal(tempChar);
369                     mTempLocals.push(tempChar);
370                 } else {
371                     mBuilder.loadLocal(mLookupLocal);
372                     mBuilder.loadLocal(mIndexLocal);
373                     if (depth > 0) {
374                         mBuilder.loadConstant(depth);
375                         mBuilder.math(Opcode.IADD);
376                     }
377                     mBuilder.loadFromArray(TypeDesc.CHAR);
378                 }
379                 
380                 mBuilder.loadConstant((char)c);
381                 mBuilder.ifComparisonBranch(noMatch, "!=");
382             }
383             
384             if (subNodes != null) {
385                 int size = subNodes.size();
386                 for (int i=0; i<size; i++) {
387                     generateBranches
388                         ((PatternNode)subNodes.get(i), depth + 1, posIndex);
389                 }
390             }
391             
392             if (node.mPattern != null) {
393                 // Matched pattern; save results.
394 generateAddMatchResult(node);
395             }
396
397             noMatch.setLocation();
398         }
399         
400         private void generateWildcard(PatternNode node, int depth,
401                                       int posIndex) {
402             Label loopStart = mBuilder.createLabel().setLocation();
403             Label loopEnd = mBuilder.createLabel();
404             Label loopContinue = mBuilder.createLabel();
405
406             // Save position of wildcard end.
407 mBuilder.loadLocal(mPositionsLocal);
408             mBuilder.loadConstant(posIndex - 1);
409             mBuilder.loadLocal(mIndexLocal);
410             if (depth > 0) {
411                 mBuilder.loadConstant(depth);
412                 mBuilder.math(Opcode.IADD);
413             }
414             mBuilder.storeToArray(TypeDesc.INT);
415
416             mBuilder.loadLocal(mLookupLocal);
417             mBuilder.loadLocal(mIndexLocal);
418             if (depth > 0) {
419                 mBuilder.loadConstant(depth);
420                 mBuilder.math(Opcode.IADD);
421             }
422             mBuilder.loadFromArray(TypeDesc.CHAR);
423
424             if (node == null) {
425                 mBuilder.loadConstant('\uffff');
426                 mBuilder.ifComparisonBranch(loopEnd, "==");
427             } else {
428                 LocalVariable tempChar;
429                 if (mTempLocals.isEmpty()) {
430                     tempChar =
431                         mBuilder.createLocalVariable("temp", mIntType);
432                 } else {
433                     tempChar = (LocalVariable)mTempLocals.pop();
434                 }
435                 mBuilder.storeLocal(tempChar);
436                 mBuilder.loadLocal(tempChar);
437
438                 mBuilder.loadConstant('\uffff');
439                 mBuilder.ifComparisonBranch(loopEnd, "==");
440
441                 generateBranches(node, depth, posIndex, tempChar);
442             }
443
444             loopContinue.setLocation();
445             mBuilder.integerIncrement(mIndexLocal, 1);
446             mBuilder.branch(loopStart);
447             loopEnd.setLocation();
448         }
449
450         private void generateAddMatchResult(PatternNode node) {
451             mBuilder.mapLineNumber(++mReferenceLine);
452
453             mBuilder.loadLocal(mLimitLocal);
454             mBuilder.loadLocal(mResultsLocal);
455             mBuilder.loadConstant(node.mPattern);
456             mBuilder.loadThis();
457             mBuilder.loadField("mValues", TypeDesc.OBJECT.toArrayType());
458             mBuilder.loadConstant(node.mOrder);
459             mBuilder.loadFromArray(TypeDesc.OBJECT);
460             mBuilder.loadLocal(mPositionsLocal);
461             mBuilder.loadConstant(node.getWildcardCount() * 2);
462
463             TypeDesc[] params = {
464                 mIntType,
465                 mListType,
466                 mStringType,
467                 mObjectType,
468                 mIntArrayType,
469                 mIntType
470             };
471             
472             mBuilder.invokeStatic(PatternMatcher.class.getName(),
473                                   "addMatchResult", mBooleanType, params);
474             mBuilder.ifZeroComparisonBranch(mReturnLabel, "==");
475         }
476     }
477
478     private static class PatternNode {
479         public final int mChar;
480         public String mPattern;
481         public int mOrder;
482         public List mSubNodes;
483
484         public PatternNode() {
485             mChar = -1;
486         }
487
488         public PatternNode(char c) {
489             mChar = c;
490         }
491
492         public void buildPathTo(String pattern, int order) {
493             buildPathTo(pattern, order, 0);
494         }
495
496         public int getHeight() {
497             int height = 1;
498             if (mSubNodes != null) {
499                 int size = mSubNodes.size();
500                 for (int i=0; i<size; i++) {
501                     int subH = ((PatternNode)mSubNodes.get(i)).getHeight();
502                     if (subH > height) {
503                         height = subH;
504                     }
505                 }
506             }
507             return height;
508         }
509
510         public int getWildcardCount() {
511             int wildCount = 0;
512             String pattern = mPattern;
513             if (pattern != null) {
514                 int len = pattern.length();
515                 for (int i=0; i<len; i++) {
516                     if (pattern.charAt(i) == '*') {
517                         wildCount++;
518                     }
519                 }
520             }
521             return wildCount;
522         }
523
524         public int getMaxWildcardCount() {
525             int wildCount = getWildcardCount();
526             
527             if (mSubNodes != null) {
528                 for (int i=0; i<mSubNodes.size(); i++) {
529                     int count =
530                         ((PatternNode)mSubNodes.get(i)).getMaxWildcardCount();
531                     if (count > wildCount) {
532                         wildCount = count;
533                     }
534                 }
535             }
536
537             return wildCount;
538         }
539
540         private void buildPathTo(String pattern, int order, int index) {
541             if (index >= pattern.length()) {
542                 if (pattern.endsWith("\uffff")) {
543                     // Trim off the '\uffff'.
544 pattern = pattern.substring(0, pattern.length() - 1);
545                 }
546                 mPattern = pattern;
547                 mOrder = order;
548                 return;
549             }
550
551             char c = pattern.charAt(index);
552
553             if (mSubNodes == null) {
554                 mSubNodes = new ArrayList (10);
555             }
556
557             int size = mSubNodes.size();
558             for (int i=0; i<size; i++) {
559                 PatternNode node = (PatternNode)mSubNodes.get(i);
560                 if (node.mChar == c) {
561                     node.buildPathTo(pattern, order, index + 1);
562                     return;
563                 }
564             }
565
566             PatternNode node = new PatternNode(c);
567             mSubNodes.add(node);
568             node.buildPathTo(pattern, order, index + 1);
569
570             return;
571         }
572
573         public void dump(PrintStream out, String indent) {
574             if (mSubNodes != null) {
575                 String subIndent = indent.concat(" ");
576                 for (int i=0; i<mSubNodes.size(); i++) {
577                     ((PatternNode)mSubNodes.get(i)).dump(out, subIndent);
578                 }
579             }
580             out.print(indent);
581             out.print('\'');
582             out.print((char)mChar);
583             out.print('\'');
584             if (mPattern != null) {
585                 out.print(" -> ");
586                 out.print(mPattern);
587             }
588             out.println();
589         }
590     }
591
592     private static class PatternComparator implements Comparator {
593         public int compare(Object a, Object b) {
594             String sa = (String )a;
595             String sb = (String )b;
596             
597             int alen = sa.length();
598             int blen = sb.length();
599             int mlen = Math.min(alen, blen);
600             
601             for (int i=0; i<mlen; i++) {
602                 char ca = sa.charAt(i);
603                 char cb = sb.charAt(i);
604                 if (ca == '*') {
605                     if (cb != '*') {
606                         // Wildcard sorted high.
607 return 1;
608                     }
609                 } else if (cb == '*') {
610                     // Wildcard sorted high.
611 return -1;
612                 } else if (ca < cb) {
613                     return -1;
614                 } else if (ca > cb) {
615                     return 1;
616                 }
617             }
618             
619             // The shorter string is sorted high.
620 if (alen < blen) {
621                 return 1;
622             } else if (alen > blen) {
623                 return -1;
624             }
625             
626             return 0;
627         }
628     }
629
630     private static class TinyList extends AbstractList {
631         public Object mElement;
632
633         public int size() {
634             return mElement == null ? 0 : 1;
635         }
636
637         public boolean add(Object obj) {
638             if (mElement == null) {
639                 mElement = obj;
640                 return true;
641             } else {
642                 throw new UnsupportedOperationException ();
643             }
644         }
645
646         public Object get(int index) {
647             if (index == 0 && mElement != null) {
648                 return mElement;
649             } else {
650                 throw new IndexOutOfBoundsException ();
651             }
652         }
653     }
654
655     /* Sample auto-generated method.
656     protected void fillMatchResults(char[] lookup, int limit, List results) {
657         int[] positions = new int[2]; // At least as large as number of wildcards, times 2.
658         int i = 0;
659         if (lookup[i + 0] == '/') {
660             if (lookup[i + 1] == 'a') {
661                 if (lookup[i + 2] == 'd') {
662                     if (lookup[i + 3] == 'm') {
663                         if (lookup[i + 4] == 'i') {
664                             if (lookup[i + 5] == 'n') {
665                                 if (lookup[i + 6] == '2') {
666                                     if (lookup[i + 7] == '?') {
667                                         addMatchResult(limit, results, "/admin2", mValues[0], null, 0);
668                                     }
669                                 } else if (lookup[i + 6] == '?') {
670                                     addMatchResult(limit, results, "/admin", mValues[1], null, 0);
671                                 }
672                             }
673                         }
674                     }
675                 }
676             } else if (lookup[i + 1] == 't') {
677                 if (lookup[i + 2] == 'e') {
678                     if (lookup[i + 3] == 'a') {
679                         if (lookup[i + 4] == '/') {
680                             // Wildcard pattern. Consume characters until match found.
681                             int saved_i = i;
682                             positions[0] = i + 5;
683                             while (true) {
684                                 positions[1] = i + 5;
685                                 char c = lookup[i + 5];
686                                 if (c == '?') {
687                                     break;
688                                 } else if (c == '.') {
689                                     if (lookup[i + 6] == 'h') {
690                                         if (lookup[i + 7] == 't') {
691                                             if (lookup[i + 8] == 'm') {
692                                                 if (lookup[i + 9] == 'l') {
693                                                     if (lookup[i + 10] == '?') {
694                                                         addMatchResult(limit, results, "/tea/*.html", mValues[2], positions, 2);
695                                                     }
696                                                 }
697                                             }
698                                         }
699                                     }
700                                 }
701                                 i++;
702                             }
703                             i = saved_i;
704                             addMatchResult(limit, results, "/tea/*", mValues[3], positions, 2);
705                         }
706                     }
707                 }
708             }
709         }
710         // Wildcard pattern. Consume characters until match found.
711         int saved_i = i;
712         positions[0] = i;
713         while (true) {
714             positions[1] = i;
715             char c = lookup[i];
716             if (c == '?') {
717                 break;
718             } else if (c == '.') {
719                 if (lookup[i + 1] == 'h') {
720                     if (lookup[i + 2] == 't') {
721                         if (lookup[i + 3] == 'm') {
722                             if (lookup[i + 4] == 'l') {
723                                 if (lookup[i + 5] == '?') {
724                                     addMatchResult(limit, results, "*.html", mValues[4], positions, 2);
725                                 }
726                             }
727                         }
728                     }
729                 }
730             }
731             i++;
732         }
733         i = saved_i;
734         addMatchResult(limit, results, "*", mValues[5], positions, 2);
735     }
736     */
737 }
738

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags