github-actions[bot] commented on code in PR #64941: URL: https://github.com/apache/doris/pull/64941#discussion_r3492471556
########## fe/fe-filesystem/fe-filesystem-spi/src/main/java/org/apache/doris/filesystem/spi/ObjectStorageGlob.java: ########## @@ -0,0 +1,695 @@ +// 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.math.BigInteger; +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.Matcher; +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 static final Pattern NUMERIC_RANGE_ALTERNATIVE = 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); Review Comment: Sorting expanded prefixes in UTF-8 byte order needs the same ordering everywhere that consumes the resulting cursor. The new `globListWithLimit_paginatesExpandedPrefixesInUtf8BinaryOrder` case demonstrates a first page where `data/<U+E000>/file.csv` is returned and `data/<U+1F600>/file.csv` becomes `maxFile`. `S3SourceOffsetProvider` stores the returned file as `currentOffset.endFile`, stores this `maxFile` as `maxEndFile`, and then uses Java UTF-16 `String.compareTo` in `hasMoreDataToConsume()`. For that pair, Java orders `<U+E000>` after `<U+1F600>`, so the provider returns false and never schedules the remaining object. Please make the glob cursor contract consistent end to end, for example by using the same UTF-8 binary comparator in the offset/provider cursor checks (and Azure's client-side `startAfter` filter if it is meant to share this order), or by avoiding an expanded-prefix order that downstream cursors cannot compare. -- 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]
