Home | History | Annotate | Download | only in os 
      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 
     51     public PatternMatcher(String pattern, int type) {
     52         mPattern = pattern;
     53         mType = type;
     54     }
     55 
     56     public final String getPath() {
     57         return mPattern;
     58     }
     59 
     60     public final int getType() {
     61         return mType;
     62     }
     63 
     64     public boolean match(String str) {
     65         return matchPattern(mPattern, str, mType);
     66     }
     67 
     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 
     84     public int describeContents() {
     85         return 0;
     86     }
     87 
     88     public void writeToParcel(Parcel dest, int flags) {
     89         dest.writeString(mPattern);
     90         dest.writeInt(mType);
     91     }
     92 
     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 
    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