| 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 |
} |