vlsi commented on code in PR #5375:
URL: https://github.com/apache/calcite/pull/5375#discussion_r4417698178
##########
core/src/main/java/org/apache/calcite/schema/lookup/LikePattern.java:
##########
@@ -56,43 +60,56 @@ public static Predicate1<String> matcher(String
likePattern) {
if (likePattern == null || likePattern.equals(ANY)) {
return v1 -> true;
}
- final Pattern regex = likeToRegex(likePattern);
- return v1 -> regex.matcher(v1).matches();
+ final List<String> segments = segments(likePattern);
+ return v1 -> matches(segments, v1);
}
- /**
- * Converts a LIKE-style pattern (where '%' represents a wild-card, escaped
- * using '\') to a Java regex. It's always case sensitive.
- */
- public static Pattern likeToRegex(String pattern) {
- StringBuilder buf = new StringBuilder("^");
- char[] charArray = pattern.toCharArray();
- int slash = -2;
- for (int i = 0; i < charArray.length; i++) {
- char c = charArray[i];
- if (slash == i - 1) {
- buf.append('[').append(c).append(']');
- } else {
- switch (c) {
- case '\\':
- slash = i;
- break;
- case '%':
- buf.append(".*");
- break;
- case '[':
- buf.append("\\[");
- break;
- case ']':
- buf.append("\\]");
- break;
- default:
- buf.append('[').append(c).append(']');
+ /** Splits a LIKE-style pattern into the literal segments between its
+ * '%' wild-cards, resolving '\' escapes. A pattern with n wild-cards has
+ * n + 1 segments, some of which may be empty. */
+ private static List<String> segments(String pattern) {
+ final List<String> segments = new ArrayList<>();
+ final StringBuilder buf = new StringBuilder();
+ for (int i = 0; i < pattern.length(); i++) {
+ final char c = pattern.charAt(i);
+ if (c == '\\') {
+ if (++i < pattern.length()) {
+ buf.append(pattern.charAt(i));
}
+ } else if (c == '%') {
+ segments.add(buf.toString());
+ buf.setLength(0);
+ } else {
+ buf.append(c);
+ }
+ }
+ segments.add(buf.toString());
+ return segments;
+ }
+
+ /** Returns whether a string matches a pattern split by
+ * {@link #segments}. Each middle segment is matched at its leftmost
+ * occurrence, which leaves the most room for the segments after it. */
+ private static boolean matches(List<String> segments, String s) {
+ final String first = segments.get(0);
+ if (segments.size() == 1) {
+ return s.equals(first);
+ }
+ final String last = segments.get(segments.size() - 1);
+ if (s.length() < first.length() + last.length()
+ || !s.startsWith(first) || !s.endsWith(last)) {
+ return false;
+ }
+ final int end = s.length() - last.length();
+ int pos = first.length();
+ for (String segment : segments.subList(1, segments.size() - 1)) {
+ final int i = s.indexOf(segment, pos);
Review Comment:
This can cause `O(n*m)` complexity because `Stirng.indexOf` can repeatedly
compare long literal segments. WDYT of going for linear time with KMP?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
