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
17package 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 */
24public 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