1 /*
2  * Copyright (C) 2008 The Android Open Source Project
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 android.os;
18 
19 /**
20  * A simple pattern matcher, which is safe to use on untrusted data: it does
21  * not provide full reg-exp support, only simple globbing that can not be
22  * used maliciously.
23  */
24 public class PatternMatcher implements Parcelable {
25     /**
26      * Pattern type: the given pattern must exactly match the string it is
27      * tested against.
28      */
29     public static final int PATTERN_LITERAL = 0;
30 
31     /**
32      * Pattern type: the given pattern must match the
33      * beginning of the string it is tested against.
34      */
35     public static final int PATTERN_PREFIX = 1;
36 
37     /**
38      * Pattern type: the given pattern is interpreted with a
39      * simple glob syntax for matching against the string it is tested against.
40      * In this syntax, you can use the '*' character to match against zero or
41      * more occurrences of the character immediately before.  If the
42      * character before it is '.' it will match any character.  The character
43      * '\' can be used as an escape.  This essentially provides only the '*'
44      * wildcard part of a normal regexp.
45      */
46     public static final int PATTERN_SIMPLE_GLOB = 2;
47 
48     private final String mPattern;
49     private final int mType;
50 
PatternMatcher(String pattern, int type)51     public PatternMatcher(String pattern, int type) {
52         mPattern = pattern;
53         mType = type;
54     }
55 
getPath()56     public final String getPath() {
57         return mPattern;
58     }
59 
getType()60     public final int getType() {
61         return mType;
62     }
63 
match(String str)64     public boolean match(String str) {
65         return matchPattern(mPattern, str, mType);
66     }
67 
toString()68     public String toString() {
69         String type = "? ";
70         switch (mType) {
71             case PATTERN_LITERAL:
72                 type = "LITERAL: ";
73                 break;
74             case PATTERN_PREFIX:
75                 type = "PREFIX: ";
76                 break;
77             case PATTERN_SIMPLE_GLOB:
78                 type = "GLOB: ";
79                 break;
80         }
81         return "PatternMatcher{" + type + mPattern + "}";
82     }
83 
describeContents()84     public int describeContents() {
85         return 0;
86     }
87 
writeToParcel(Parcel dest, int flags)88     public void writeToParcel(Parcel dest, int flags) {
89         dest.writeString(mPattern);
90         dest.writeInt(mType);
91     }
92 
PatternMatcher(Parcel src)93     public PatternMatcher(Parcel src) {
94         mPattern = src.readString();
95         mType = src.readInt();
96     }
97 
98     public static final Parcelable.Creator<PatternMatcher> CREATOR
99             = new Parcelable.Creator<PatternMatcher>() {
100         public PatternMatcher createFromParcel(Parcel source) {
101             return new PatternMatcher(source);
102         }
103 
104         public PatternMatcher[] newArray(int size) {
105             return new PatternMatcher[size];
106         }
107     };
108 
matchPattern(String pattern, String match, int type)109     static boolean matchPattern(String pattern, String match, int type) {
110         if (match == null) return false;
111         if (type == PATTERN_LITERAL) {
112             return pattern.equals(match);
113         } if (type == PATTERN_PREFIX) {
114             return match.startsWith(pattern);
115         } else if (type != PATTERN_SIMPLE_GLOB) {
116             return false;
117         }
118 
119         final int NP = pattern.length();
120         if (NP <= 0) {
121             return match.length() <= 0;
122         }
123         final int NM = match.length();
124         int ip = 0, im = 0;
125         char nextChar = pattern.charAt(0);
126         while ((ip<NP) && (im<NM)) {
127             char c = nextChar;
128             ip++;
129             nextChar = ip < NP ? pattern.charAt(ip) : 0;
130             final boolean escaped = (c == '\\');
131             if (escaped) {
132                 c = nextChar;
133                 ip++;
134                 nextChar = ip < NP ? pattern.charAt(ip) : 0;
135             }
136             if (nextChar == '*') {
137                 if (!escaped && c == '.') {
138                     if (ip >= (NP-1)) {
139                         // at the end with a pattern match, so
140                         // all is good without checking!
141                         return true;
142                     }
143                     ip++;
144                     nextChar = pattern.charAt(ip);
145                     // Consume everything until the next character in the
146                     // pattern is found.
147                     if (nextChar == '\\') {
148                         ip++;
149                         nextChar = ip < NP ? pattern.charAt(ip) : 0;
150                     }
151                     do {
152                         if (match.charAt(im) == nextChar) {
153                             break;
154                         }
155                         im++;
156                     } while (im < NM);
157                     if (im == NM) {
158                         // Whoops, the next character in the pattern didn't
159                         // exist in the match.
160                         return false;
161                     }
162                     ip++;
163                     nextChar = ip < NP ? pattern.charAt(ip) : 0;
164                     im++;
165                 } else {
166                     // Consume only characters matching the one before '*'.
167                     do {
168                         if (match.charAt(im) != c) {
169                             break;
170                         }
171                         im++;
172                     } while (im < NM);
173                     ip++;
174                     nextChar = ip < NP ? pattern.charAt(ip) : 0;
175                 }
176             } else {
177                 if (c != '.' && match.charAt(im) != c) return false;
178                 im++;
179             }
180         }
181 
182         if (ip >= NP && im >= NM) {
183             // Reached the end of both strings, all is good!
184             return true;
185         }
186 
187         // One last check: we may have finished the match string, but still
188         // have a '.*' at the end of the pattern, which should still count
189         // as a match.
190         if (ip == NP-2 && pattern.charAt(ip) == '.'
191             && pattern.charAt(ip+1) == '*') {
192             return true;
193         }
194 
195         return false;
196     }
197 }
198