Debian Codegraph @

bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/SimplePattern.java

raw
1 /*******************************************************************************
2 * Copyright (c) 2009, 2017 Cloudsmith Inc. and others.
3 *
4 * This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License 2.0
6 * which accompanies this distribution, and is available at
7 * https://www.eclipse.org/legal/epl-2.0/
8 *
9 * SPDX-License-Identifier: EPL-2.0
10 *
11 * Contributors:
12 * Cloudsmith Inc. - initial API and implementation
13 *******************************************************************************/
14 package org.eclipse.equinox.p2.metadata.expression;
15
16 import java.io.Serializable;
17
18 /**
19 * A simple compiled pattern. It supports two kinds of wildcards. The '*' (any character zero to many times)
20 * and the '?' (any character exactly one time).
21 * @since 2.0
22 */
23 public class SimplePattern implements Serializable, Comparable<SimplePattern> {
24 private static final long serialVersionUID = -2477990705739062410L;
25
26 /**
27 * Matches the <code>value</code> with the compiled expression. The value
28 * is considered matching if all characters are matched by the expression. A
29 * partial match is not enough.
30 * @param value The value to match
31 * @return <code>true</code> if the value was a match.
32 */
33 public boolean isMatch(CharSequence value) {
34 if (node == null)
35 node = parse(pattern, 0);
36 return node.match(value, 0);
37 }
38
39 @Override
40 public String toString() {
41 return pattern;
42 }
43
44 @Override
45 public int compareTo(SimplePattern o) {
46 return pattern.compareTo(o.pattern);
47 }
48
49 @Override
50 public boolean equals(Object o) {
51 return o == this || (o instanceof SimplePattern && ((SimplePattern) o).pattern.equals(pattern));
52 }
53
54 @Override
55 public int hashCode() {
56 return 3 * pattern.hashCode();
57 }
58
59 private final String pattern;
60 private transient Node node;
61
62 private SimplePattern(String pattern) {
63 this.pattern = pattern;
64 }
65
66 static class AllNode extends Node {
67 @Override
68 boolean match(CharSequence value, int pos) {
69 return true;
70 }
71 }
72
73 static class RubberBandNode extends Node {
74 final Node next;
75
76 RubberBandNode(Node next) {
77 this.next = next;
78 }
79
80 @Override
81 boolean match(CharSequence value, int pos) {
82 int top = value.length();
83 String ending = next.getEndingConstant();
84 if (ending != null) {
85 // value must end with this constant. It will be faster
86 // to scan backwards from the end.
87 int clen = ending.length();
88 if (clen > top - pos)
89 return false;
90 while (clen > 0)
91 if (ending.charAt(--clen) != value.charAt(--top))
92 return false;
93 return true;
94 }
95
96 while (pos < top) {
97 if (next.match(value, pos++))
98 return true;
99 }
100 return false;
101 }
102 }
103
104 static class AnyCharacterNode extends Node {
105 final Node next;
106
107 AnyCharacterNode(Node next) {
108 this.next = next;
109 }
110
111 @Override
112 boolean match(CharSequence value, int pos) {
113 int top = value.length();
114 return next == null ? pos + 1 == top : next.match(value, pos + 1);
115 }
116 }
117
118 static class EndConstantNode extends Node {
119 final String constant;
120
121 EndConstantNode(String constant) {
122 this.constant = constant;
123 }
124
125 @Override
126 boolean match(CharSequence value, int pos) {
127 int max = constant.length() + pos;
128 int top = value.length();
129 if (top != max)
130 return false;
131
132 int idx = 0;
133 while (pos < max)
134 if (value.charAt(pos++) != constant.charAt(idx++))
135 return false;
136 return true;
137 }
138
139 @Override
140 String getEndingConstant() {
141 return constant;
142 }
143 }
144
145 static class ConstantNode extends Node {
146 final Node next;
147 final String constant;
148
149 ConstantNode(Node next, String constant) {
150 this.next = next;
151 this.constant = constant;
152 }
153
154 @Override
155 boolean match(CharSequence value, int pos) {
156 int max = constant.length() + pos;
157 int top = value.length();
158 if (top < max)
159 return false;
160
161 int idx = 0;
162 while (pos < max)
163 if (value.charAt(pos++) != constant.charAt(idx++))
164 return false;
165 return next == null ? (pos == top) : next.match(value, pos);
166 }
167 }
168
169 static abstract class Node {
170 abstract boolean match(CharSequence value, int pos);
171
172 String getEndingConstant() {
173 return null;
174 }
175 }
176
177 public static SimplePattern compile(String pattern) {
178 if (pattern == null)
179 throw new IllegalArgumentException("Pattern can not be null"); //$NON-NLS-1$
180 return new SimplePattern(pattern);
181 }
182
183 private static Node parse(String pattern, int pos) {
184 int top = pattern.length();
185 StringBuilder bld = null;
186 Node parsedNode = null;
187 while (pos < top) {
188 char c = pattern.charAt(pos);
189 switch (c) {
190 case '*' :
191 ++pos;
192 parsedNode = pos == top ? new AllNode() : new RubberBandNode(parse(pattern, pos));
193 break;
194 case '?' :
195 parsedNode = new AnyCharacterNode(parse(pattern, pos + 1));
196 break;
197 case '\\' :
198 if (++pos == top)
199 throw new IllegalArgumentException("Pattern ends with escape"); //$NON-NLS-1$
200 c = pattern.charAt(pos);
201 // fall through
202 default :
203 if (bld == null)
204 bld = new StringBuilder();
205 bld.append(c);
206 ++pos;
207 continue;
208 }
209 break;
210 }
211
212 if (bld != null) {
213 String constant = bld.toString();
214 parsedNode = parsedNode == null ? new EndConstantNode(constant) : new ConstantNode(parsedNode, constant);
215 }
216 return parsedNode;
217 }
218 }