github-actions[bot] commented on code in PR #64941: URL: https://github.com/apache/doris/pull/64941#discussion_r3490446348
########## fe/fe-filesystem/fe-filesystem-spi/src/main/java/org/apache/doris/filesystem/spi/ObjectStorageGlob.java: ########## @@ -0,0 +1,519 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +package org.apache.doris.filesystem.spi; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; +import java.util.regex.Pattern; + +/** + * Provider-neutral glob helpers for object-storage keys. + */ +public final class ObjectStorageGlob { + + private static final int MAX_EXPANDED_GLOB_LIST_PREFIXES = 256; + private static final Comparator<String> UTF8_BINARY_ORDER = ObjectStorageGlob::compareUtf8Binary; + private static final Pattern NUMERIC_RANGE_PATTERN = Pattern.compile("-?\\d+\\.\\.-?\\d+"); + + private ObjectStorageGlob() { + } + + /** + * Returns the longest key prefix that contains no glob metacharacters. + */ + public static String longestNonGlobPrefix(String globPattern) { + int earliest = globPattern.length(); + for (char c : new char[]{'*', '?', '[', '{', '\\'}) { + int idx = globPattern.indexOf(c); + if (idx >= 0 && idx < earliest) { + earliest = idx; + } + } + return globPattern.substring(0, earliest); + } + + /** + * Returns object-store list prefixes that are safe to push down for a glob pattern. + * + * <p>Unlike {@link #longestNonGlobPrefix(String)}, this expands bounded glob constructs + * ({@code {...}} alternation and positive {@code [...]} character classes) before the first + * unbounded wildcard. For example, + * {@code date=2025-{0[3-9],1[0-2]}-01/mp_id=8/*} becomes concrete date prefixes instead + * of one broad {@code date=2025-} scan. If expansion would be too large or unsafe, it + * falls back to the conservative longest static prefix. + */ + public static List<String> expandedGlobListPrefixes(String globPattern) { + List<String> prefixes = expandGlobListPrefixes(globPattern, true); + return prefixes == null ? List.of(longestNonGlobPrefix(globPattern)) : prefixes; + } + + private static List<String> expandGlobListPrefixes(String globPattern, boolean allowPartialPrefix) { + List<String> prefixes = new ArrayList<>(); + prefixes.add(""); + int i = 0; + while (i < globPattern.length()) { + char c = globPattern.charAt(i); + if (c == '*' || c == '?') { + return allowPartialPrefix ? compactPrefixes(prefixes) : null; + } + if (c == '\\') { + if (i + 1 < globPattern.length()) { + appendLiteral(prefixes, globPattern.charAt(i + 1)); + i += 2; + } else { + appendLiteral(prefixes, c); + i++; + } + continue; + } + if (c == '[') { + PrefixExpansion charClass = expandCharacterClass(globPattern, i); + if (charClass == null) { + return allowPartialPrefix ? compactPrefixes(prefixes) : null; + } + prefixes = appendAlternatives(prefixes, charClass.values); + if (prefixes == null) { + return null; + } + i = charClass.nextIndex; + continue; + } + if (c == '{') { + PrefixExpansion brace = expandBraceGroup(globPattern, i); + if (brace == null) { + return allowPartialPrefix ? compactPrefixes(prefixes) : null; + } + prefixes = appendAlternatives(prefixes, brace.values); + if (prefixes == null) { + return null; + } + i = brace.nextIndex; + continue; + } + appendLiteral(prefixes, c); + i++; + } + return compactPrefixes(prefixes); + } + + private static void appendLiteral(List<String> prefixes, char c) { + for (int i = 0; i < prefixes.size(); i++) { + prefixes.set(i, prefixes.get(i) + c); + } + } + + private static List<String> appendAlternatives(List<String> prefixes, List<String> alternatives) { + long expandedSize = (long) prefixes.size() * alternatives.size(); + if (expandedSize > MAX_EXPANDED_GLOB_LIST_PREFIXES) { + return null; + } + List<String> expanded = new ArrayList<>((int) expandedSize); + for (String prefix : prefixes) { + for (String alternative : alternatives) { + expanded.add(prefix + alternative); + } + } + return expanded; + } + + private static PrefixExpansion expandCharacterClass(String globPattern, int openIndex) { + int closeIndex = findClosingBracket(globPattern, openIndex); + if (closeIndex < 0 || closeIndex == openIndex + 1) { + return null; + } + int i = openIndex + 1; + char first = globPattern.charAt(i); + if (first == '!' || first == '^') { + return null; + } + if (containsSurrogate(globPattern, i, closeIndex)) { + return null; + } + List<String> values = new ArrayList<>(); + while (i < closeIndex) { + char current = globPattern.charAt(i); + if (current == '\\') { + if (i + 1 >= closeIndex) { + return null; + } + values.add(String.valueOf(globPattern.charAt(i + 1))); + i += 2; + continue; + } + if (i + 2 < closeIndex && globPattern.charAt(i + 1) == '-') { + char rangeEnd = globPattern.charAt(i + 2); + int step = current <= rangeEnd ? 1 : -1; + for (char ch = current; step > 0 ? ch <= rangeEnd : ch >= rangeEnd; ch += step) { + values.add(String.valueOf(ch)); + if (values.size() > MAX_EXPANDED_GLOB_LIST_PREFIXES) { + return null; + } + } + i += 3; + continue; + } + values.add(String.valueOf(current)); + i++; + } + return new PrefixExpansion(values, closeIndex + 1); + } + + private static int findClosingBracket(String globPattern, int openIndex) { + for (int i = openIndex + 1; i < globPattern.length(); i++) { + char c = globPattern.charAt(i); + if (c == '\\') { + i++; + continue; + } + if (c == ']') { + return i; + } + } + return -1; + } + + private static boolean containsSurrogate(String text, int start, int end) { + for (int i = start; i < end; i++) { + if (Character.isSurrogate(text.charAt(i))) { + return true; + } + } + return false; + } + + private static PrefixExpansion expandBraceGroup(String globPattern, int openIndex) { + int closeIndex = findClosingBrace(globPattern, openIndex); + if (closeIndex < 0) { + return null; + } + List<String> alternatives = splitBraceAlternatives( + globPattern.substring(openIndex + 1, closeIndex)); + if (alternatives.isEmpty()) { + return null; + } + List<String> values = new ArrayList<>(); + for (String alternative : alternatives) { + if (containsNumericRange(alternative)) { + return null; + } + List<String> expandedAlternative = expandGlobListPrefixes(alternative, false); + if (expandedAlternative == null) { + return null; + } + values.addAll(expandedAlternative); + if (values.size() > MAX_EXPANDED_GLOB_LIST_PREFIXES) { + return null; + } + } + return new PrefixExpansion(values, closeIndex + 1); + } + + private static int findClosingBrace(String globPattern, int openIndex) { + int depth = 0; + for (int i = openIndex; i < globPattern.length(); i++) { + char c = globPattern.charAt(i); + if (c == '\\') { + i++; + continue; + } + if (c == '{') { + depth++; + } else if (c == '}') { + depth--; + if (depth == 0) { + return i; + } + } + } + return -1; + } + + private static List<String> splitBraceAlternatives(String content) { + List<String> alternatives = new ArrayList<>(); + int depth = 0; + int start = 0; + for (int i = 0; i < content.length(); i++) { + char c = content.charAt(i); + if (c == '\\') { + i++; + continue; + } + if (c == '{') { + depth++; + } else if (c == '}') { + if (depth == 0) { + return Collections.emptyList(); + } + depth--; + } else if (c == ',' && depth == 0) { + alternatives.add(content.substring(start, i)); + start = i + 1; + } + } + if (depth != 0) { + return Collections.emptyList(); + } + alternatives.add(content.substring(start)); + return alternatives; + } + + private static List<String> compactPrefixes(List<String> prefixes) { + List<String> sorted = new ArrayList<>(prefixes); + sorted.sort(UTF8_BINARY_ORDER); + List<String> compact = new ArrayList<>(); + for (String prefix : sorted) { + if (prefix.isEmpty()) { + return List.of(""); + } + boolean covered = false; + for (String existing : compact) { + if (prefix.startsWith(existing)) { + covered = true; + break; + } + } + if (!covered) { + compact.add(prefix); + } + } + return compact; + } + + private static int compareUtf8Binary(String left, String right) { + byte[] leftBytes = left.getBytes(StandardCharsets.UTF_8); + byte[] rightBytes = right.getBytes(StandardCharsets.UTF_8); + int commonLength = Math.min(leftBytes.length, rightBytes.length); + for (int i = 0; i < commonLength; i++) { + int result = Integer.compare( + Byte.toUnsignedInt(leftBytes[i]), Byte.toUnsignedInt(rightBytes[i])); + if (result != 0) { + return result; + } + } + return Integer.compare(leftBytes.length, rightBytes.length); + } + + /** + * Expands bounded {N..M} numeric ranges inside brace groups into comma-separated alternatives. + */ + public static String expandNumericRanges(String pattern) { + java.util.regex.Pattern rangeSegment = java.util.regex.Pattern.compile( + "(-?\\d+)\\.\\.(-?\\d+)"); + java.util.regex.Pattern simpleRange = java.util.regex.Pattern.compile( + "\\{(\\d+)\\.\\.(\\d+)\\}"); + java.util.regex.Pattern braceGroup = java.util.regex.Pattern.compile( + "\\{([^}]*\\d+\\.\\.\\d+[^}]*)\\}"); + java.util.regex.Matcher m = braceGroup.matcher(pattern); + StringBuffer sb = new StringBuffer(); + while (m.find()) { + String content = m.group(1); + boolean isMixed = content.contains(","); + if (!isMixed) { + java.util.regex.Matcher sm = simpleRange.matcher(m.group(0)); + if (!sm.matches()) { + continue; + } + } + String[] segments = content.split(",", -1); + java.util.LinkedHashSet<String> values = new java.util.LinkedHashSet<>(); + boolean canExpand = true; + for (String seg : segments) { + java.util.regex.Matcher rm = rangeSegment.matcher(seg.trim()); + if (rm.matches()) { + long from; + long to; + try { + from = Long.parseLong(rm.group(1)); + to = Long.parseLong(rm.group(2)); + } catch (NumberFormatException e) { + canExpand = false; + break; + } + long cardinality = numericRangeCardinality(from, to); + if (cardinality < 0 + || cardinality > MAX_EXPANDED_GLOB_LIST_PREFIXES - values.size()) { + canExpand = false; + break; + } + long step = from <= to ? 1L : -1L; + boolean zeroPad = hasLeadingZero(rm.group(1)) || hasLeadingZero(rm.group(2)); + int width = Math.max(digitWidth(rm.group(1)), digitWidth(rm.group(2))); + for (long offset = 0; offset < cardinality; offset++) { + long value = step > 0 ? from + offset : from - offset; + values.add(formatRangeValue(value, width, zeroPad)); + } + } else { + values.add(seg.trim()); + if (values.size() > MAX_EXPANDED_GLOB_LIST_PREFIXES) { + canExpand = false; + break; + } + } + } + if (!canExpand) { Review Comment: When expansion is skipped for an oversized numeric range, the pattern still has to preserve range semantics. Right now `continue` leaves the original `{N..M}` group in `expandedKeyPattern`; Azure/S3 then build the matcher with `globToRegex(expandedKeyPattern)`, and `globToRegex` treats braces only as comma alternation while escaping the dots. For example, `date={1..10000000}/*` falls back to the broad `date=` list prefix, but the regex becomes `^date=(?:1\\.\\.10000000)/[^/]*$`, so a real key like `date=123/file.csv` is listed and then filtered out. Please either keep numeric-range matching semantics without materializing all alternatives, or fail/diagnose unsupported oversized ranges instead of silently returning no valid matches; an end-to-end Azure/S3 glob test with a >256 range and a matching object would catch this. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
