19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.os; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * A simple pattern matcher, which is safe to use on untrusted data: it does 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * not provide full reg-exp support, only simple globbing that can not be 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * used maliciously. 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic class PatternMatcher implements Parcelable { 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Pattern type: the given pattern must exactly match the string it is 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * tested against. 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static final int PATTERN_LITERAL = 0; 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Pattern type: the given pattern must match the 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * beginning of the string it is tested against. 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static final int PATTERN_PREFIX = 1; 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Pattern type: the given pattern is interpreted with a 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * simple glob syntax for matching against the string it is tested against. 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * In this syntax, you can use the '*' character to match against zero or 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * more occurrences of the character immediately before. If the 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * character before it is '.' it will match any character. The character 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * '\' can be used as an escape. This essentially provides only the '*' 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * wildcard part of a normal regexp. 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static final int PATTERN_SIMPLE_GLOB = 2; 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private final String mPattern; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private final int mType; 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public PatternMatcher(String pattern, int type) { 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mPattern = pattern; 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mType = type; 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public final String getPath() { 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mPattern; 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public final int getType() { 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mType; 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public boolean match(String str) { 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return matchPattern(mPattern, str, mType); 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public String toString() { 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String type = "? "; 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project switch (mType) { 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PATTERN_LITERAL: 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project type = "LITERAL: "; 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PATTERN_PREFIX: 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project type = "PREFIX: "; 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project case PATTERN_SIMPLE_GLOB: 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project type = "GLOB: "; 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return "PatternMatcher{" + type + mPattern + "}"; 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int describeContents() { 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void writeToParcel(Parcel dest, int flags) { 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dest.writeString(mPattern); 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dest.writeInt(mType); 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public PatternMatcher(Parcel src) { 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mPattern = src.readString(); 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mType = src.readInt(); 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public static final Parcelable.Creator<PatternMatcher> CREATOR 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project = new Parcelable.Creator<PatternMatcher>() { 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public PatternMatcher createFromParcel(Parcel source) { 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return new PatternMatcher(source); 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public PatternMatcher[] newArray(int size) { 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return new PatternMatcher[size]; 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project }; 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static boolean matchPattern(String pattern, String match, int type) { 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (match == null) return false; 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (type == PATTERN_LITERAL) { 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return pattern.equals(match); 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } if (type == PATTERN_PREFIX) { 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return match.startsWith(pattern); 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else if (type != PATTERN_SIMPLE_GLOB) { 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final int NP = pattern.length(); 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (NP <= 0) { 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return match.length() <= 0; 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final int NM = match.length(); 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int ip = 0, im = 0; 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char nextChar = pattern.charAt(0); 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while ((ip<NP) && (im<NM)) { 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char c = nextChar; 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = ip < NP ? pattern.charAt(ip) : 0; 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final boolean escaped = (c == '\\'); 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (escaped) { 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project c = nextChar; 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = ip < NP ? pattern.charAt(ip) : 0; 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (nextChar == '*') { 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!escaped && c == '.') { 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip >= (NP-1)) { 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // at the end with a pattern match, so 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // all is good without checking! 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = pattern.charAt(ip); 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Consume everything until the next character in the 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // pattern is found. 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (nextChar == '\\') { 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = ip < NP ? pattern.charAt(ip) : 0; 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project do { 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (match.charAt(im) == nextChar) { 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project im++; 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } while (im < NM); 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (im == NM) { 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Whoops, the next character in the pattern didn't 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // exist in the match. 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = ip < NP ? pattern.charAt(ip) : 0; 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project im++; 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Consume only characters matching the one before '*'. 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project do { 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (match.charAt(im) != c) { 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project im++; 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } while (im < NM); 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ip++; 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project nextChar = ip < NP ? pattern.charAt(ip) : 0; 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (c != '.' && match.charAt(im) != c) return false; 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project im++; 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip >= NP && im >= NM) { 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Reached the end of both strings, all is good! 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // One last check: we may have finished the match string, but still 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // have a '.*' at the end of the pattern, which should still count 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // as a match. 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (ip == NP-2 && pattern.charAt(ip) == '.' 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && pattern.charAt(ip+1) == '*') { 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 198