1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.jdisc.application;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* @author Simon Thoresen Hult
*/
class GlobPattern implements Comparable<GlobPattern> {
private static final GlobPattern WILDCARD = new WildcardPattern();
protected final String[] parts;
private GlobPattern(String... parts) {
this.parts = parts;
}
public final Match match(String text) {
return match(text, 0);
}
public Match match(String text, int offset) {
int[] pos = new int[parts.length - 1 << 1];
if (!matches(text, offset, 0, pos)) {
return null;
}
return new Match(text, pos);
}
private boolean matches(String text, int textIdx, int partIdx, int[] out) {
String part = parts[partIdx];
if (partIdx == parts.length - 1 && part.isEmpty()) {
out[partIdx - 1 << 1 | 1] = text.length();
return true; // optimize trailing wildcard
}
int partEnd = textIdx + part.length();
if (partEnd > text.length()|| !text.startsWith(part, textIdx)) {
return false;
}
if (partIdx == parts.length - 1) {
return partEnd == text.length();
}
out[partIdx << 1] = partEnd;
for (int i = partEnd; i <= text.length(); ++i) {
out[partIdx << 1 | 1] = i;
if (matches(text, i, partIdx + 1, out)) {
return true;
}
}
return false;
}
@Override
public int compareTo(GlobPattern rhs) {
// wildcard pattern always orders last
if (parts.length == 0 || rhs.parts.length == 0) {
return rhs.parts.length - parts.length;
}
// next is trailing wildcard
int cmp = compare(parts[parts.length - 1], rhs.parts[rhs.parts.length - 1], false);
if (cmp != 0) {
return cmp;
}
// then comes part comparison
for (int i = 0; i < parts.length && i < rhs.parts.length; ++i) {
cmp = compare(parts[i], rhs.parts[i], true);
if (cmp != 0) {
return cmp;
}
}
// one starts with the other, sort longest first
return rhs.parts.length - parts.length;
}
private static int compare(String lhs, String rhs, boolean compareNonEmpty) {
if ((lhs.isEmpty() || rhs.isEmpty()) && !lhs.equals(rhs)) {
return rhs.length() - lhs.length();
}
if (!compareNonEmpty) {
return 0;
}
return rhs.compareTo(lhs);
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof GlobPattern)) {
return false;
}
GlobPattern rhs = (GlobPattern)obj;
if (!Arrays.equals(parts, rhs.parts)) {
return false;
}
return true;
}
@Override
public int hashCode() {
return Arrays.hashCode(parts);
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
for (int i = 0; i < parts.length; ++i) {
ret.append(parts[i]);
if (i < parts.length - 1) {
ret.append("*");
}
}
return ret.toString();
}
public static Match match(String glob, String text) {
return compile(glob).match(text);
}
public static GlobPattern compile(String pattern) {
if (pattern.equals("*")) {
return WILDCARD;
}
if (pattern.indexOf('*') < 0) {
return new VerbatimPattern(pattern);
}
List<String> arr = new LinkedList<>();
for (int prev = 0, next = 0; next <= pattern.length(); ++next) {
if (next == pattern.length() || pattern.charAt(next) == '*') {
arr.add(pattern.substring(prev, next));
prev = next + 1;
}
}
return new GlobPattern(arr.toArray(new String[arr.size()]));
}
public static class Match {
private final String str;
private final int[] pos;
private Match(String str, int[] pos) {
this.str = str;
this.pos = pos;
}
public int groupCount() {
return pos.length >> 1;
}
public String group(int idx) {
return str.substring(pos[idx << 1], pos[idx << 1 | 1]);
}
}
private static class VerbatimPattern extends GlobPattern {
VerbatimPattern(String value) {
super(value);
}
@Override
public Match match(String text, int offset) {
int len = text.length() - offset;
if (len != parts[0].length()) {
return null;
}
if (!parts[0].regionMatches(0, text, offset, len)) {
return null;
}
return new Match(parts[0], new int[0]);
}
}
private static class WildcardPattern extends GlobPattern {
@Override
public Match match(String text, int offset) {
int len = text.length();
if (len <= offset) {
return new Match(text, new int[] { 0, 0 });
}
return new Match(text, new int[] { offset, len });
}
@Override
public String toString() {
return "*";
}
}
}
|
