muse-dev[bot] commented on a change in pull request #6894: URL: https://github.com/apache/skywalking/pull/6894#discussion_r626261538
########## File path: apm-sniffer/optional-plugins/optional-spring-plugins/spring-mvc-annotation-naming-plugin/src/main/java/org/apache/skywalking/apm/plugin/spring/mvc/naming/AntPathMatcher.java ########## @@ -0,0 +1,699 @@ +/* + * 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.skywalking.apm.plugin.spring.mvc.naming; + +import java.util.Comparator; +import java.util.LinkedHashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.concurrent.ConcurrentHashMap; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +public class AntPathMatcher implements PathMatcher { + + /** + * Default path separator: "/". + */ + public static final String DEFAULT_PATH_SEPARATOR = "/"; + + private static final int CACHE_TURNOFF_THRESHOLD = 65536; + + private static final Pattern VARIABLE_PATTERN = Pattern.compile("\\{[^/]+?}"); + + private static final char[] WILDCARD_CHARS = {'*', '?', '{'}; + + private String pathSeparator; + + private PathSeparatorPatternCache pathSeparatorPatternCache; + + private boolean caseSensitive = true; + + private boolean trimTokens = false; + + private volatile Boolean cachePatterns; + + private final Map<String, String[]> tokenizedPatternCache = new ConcurrentHashMap<>(256); + + final Map<String, AntPathStringMatcher> stringMatcherCache = new ConcurrentHashMap<>(256); + + public AntPathMatcher() { + this.pathSeparator = DEFAULT_PATH_SEPARATOR; + this.pathSeparatorPatternCache = new PathSeparatorPatternCache(DEFAULT_PATH_SEPARATOR); + } + + public AntPathMatcher(String pathSeparator) { + this.pathSeparator = pathSeparator; + this.pathSeparatorPatternCache = new PathSeparatorPatternCache(pathSeparator); + } + + public void setPathSeparator(String pathSeparator) { + this.pathSeparator = pathSeparator != null ? pathSeparator : DEFAULT_PATH_SEPARATOR; + this.pathSeparatorPatternCache = new PathSeparatorPatternCache(this.pathSeparator); + } + + public void setCaseSensitive(boolean caseSensitive) { + this.caseSensitive = caseSensitive; + } + + public void setTrimTokens(boolean trimTokens) { + this.trimTokens = trimTokens; + } + + public void setCachePatterns(boolean cachePatterns) { + this.cachePatterns = cachePatterns; + } + + private void deactivatePatternCache() { + this.cachePatterns = false; + this.tokenizedPatternCache.clear(); + this.stringMatcherCache.clear(); + } + + @Override + public boolean isPattern(String path) { + if (path == null) { + return false; + } + boolean uriVar = false; + for (int i = 0; i < path.length(); i++) { + char c = path.charAt(i); + if (c == '*' || c == '?') { + return true; + } + if (c == '{') { + uriVar = true; + continue; + } + if (c == '}' && uriVar) { + return true; + } + } + return false; + } + + @Override + public boolean match(String pattern, String path) { + return doMatch(pattern, path, true, null); + } + + @Override + public boolean matchStart(String pattern, String path) { + return doMatch(pattern, path, false, null); + } + + protected boolean doMatch(String pattern, String path, boolean fullMatch, + Map<String, String> uriTemplateVariables) { + + if (path == null || path.startsWith(this.pathSeparator) != pattern.startsWith(this.pathSeparator)) { + return false; + } + + String[] pattDirs = tokenizePattern(pattern); + if (fullMatch && this.caseSensitive && !isPotentialMatch(path, pattDirs)) { + return false; + } + + String[] pathDirs = tokenizePath(path); + int pattIdxStart = 0; + int pattIdxEnd = pattDirs.length - 1; + int pathIdxStart = 0; + int pathIdxEnd = pathDirs.length - 1; + + // Match all elements up to the first ** + while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { + String pattDir = pattDirs[pattIdxStart]; + if ("**".equals(pattDir)) { + break; + } + if (!matchStrings(pattDir, pathDirs[pathIdxStart], uriTemplateVariables)) { + return false; + } + pattIdxStart++; + pathIdxStart++; + } + + if (pathIdxStart > pathIdxEnd) { + // Path is exhausted, only match if rest of pattern is * or **'s + if (pattIdxStart > pattIdxEnd) { + return pattern.endsWith(this.pathSeparator) == path.endsWith(this.pathSeparator); + } + if (!fullMatch) { + return true; + } + if (pattIdxStart == pattIdxEnd && pattDirs[pattIdxStart].equals("*") && path.endsWith(this.pathSeparator)) { + return true; + } + for (int i = pattIdxStart; i <= pattIdxEnd; i++) { + if (!pattDirs[i].equals("**")) { + return false; + } + } + return true; + } else if (pattIdxStart > pattIdxEnd) { + // String not exhausted, but pattern is. Failure. + return false; + } else if (!fullMatch && "**".equals(pattDirs[pattIdxStart])) { + // Path start definitely matches due to "**" part in pattern. + return true; + } + + // up to last '**' + while (pattIdxStart <= pattIdxEnd && pathIdxStart <= pathIdxEnd) { + String pattDir = pattDirs[pattIdxEnd]; + if (pattDir.equals("**")) { + break; + } + if (!matchStrings(pattDir, pathDirs[pathIdxEnd], uriTemplateVariables)) { + return false; + } + pattIdxEnd--; + pathIdxEnd--; + } + if (pathIdxStart > pathIdxEnd) { + // String is exhausted + for (int i = pattIdxStart; i <= pattIdxEnd; i++) { + if (!pattDirs[i].equals("**")) { + return false; + } + } + return true; + } + + while (pattIdxStart != pattIdxEnd && pathIdxStart <= pathIdxEnd) { + int patIdxTmp = -1; + for (int i = pattIdxStart + 1; i <= pattIdxEnd; i++) { + if (pattDirs[i].equals("**")) { + patIdxTmp = i; + break; + } + } + if (patIdxTmp == pattIdxStart + 1) { + // '**/**' situation, so skip one + pattIdxStart++; + continue; + } + // Find the pattern between padIdxStart & padIdxTmp in str between + // strIdxStart & strIdxEnd + int patLength = patIdxTmp - pattIdxStart - 1; + int strLength = pathIdxEnd - pathIdxStart + 1; + int foundIdx = -1; + + strLoop: + for (int i = 0; i <= strLength - patLength; i++) { + for (int j = 0; j < patLength; j++) { + String subPat = pattDirs[pattIdxStart + j + 1]; + String subStr = pathDirs[pathIdxStart + i + j]; + if (!matchStrings(subPat, subStr, uriTemplateVariables)) { + continue strLoop; + } + } + foundIdx = pathIdxStart + i; + break; + } + + if (foundIdx == -1) { + return false; + } + + pattIdxStart = patIdxTmp; + pathIdxStart = foundIdx + patLength; + } + + for (int i = pattIdxStart; i <= pattIdxEnd; i++) { + if (!pattDirs[i].equals("**")) { + return false; + } + } + + return true; + } + + private boolean isPotentialMatch(String path, String[] pattDirs) { + if (!this.trimTokens) { + int pos = 0; + for (String pattDir : pattDirs) { + int skipped = skipSeparator(path, pos, this.pathSeparator); + pos += skipped; + skipped = skipSegment(path, pos, pattDir); + if (skipped < pattDir.length()) { + return skipped > 0 || (pattDir.length() > 0 && isWildcardChar(pattDir.charAt(0))); + } + pos += skipped; + } + } + return true; + } + + private int skipSegment(String path, int pos, String prefix) { + int skipped = 0; + for (int i = 0; i < prefix.length(); i++) { + char c = prefix.charAt(i); + if (isWildcardChar(c)) { + return skipped; + } + int currPos = pos + skipped; + if (currPos >= path.length()) { + return 0; + } + if (c == path.charAt(currPos)) { + skipped++; + } + } + return skipped; + } + + private int skipSeparator(String path, int pos, String separator) { + int skipped = 0; + while (path.startsWith(separator, pos + skipped)) { + skipped += separator.length(); + } + return skipped; + } + + private boolean isWildcardChar(char c) { + for (char candidate : WILDCARD_CHARS) { + if (c == candidate) { + return true; + } + } + return false; + } + + protected String[] tokenizePattern(String pattern) { + String[] tokenized = null; + Boolean cachePatterns = this.cachePatterns; + if (cachePatterns == null || cachePatterns.booleanValue()) { + tokenized = this.tokenizedPatternCache.get(pattern); + } + if (tokenized == null) { + tokenized = tokenizePath(pattern); + if (cachePatterns == null && this.tokenizedPatternCache.size() >= CACHE_TURNOFF_THRESHOLD) { + // Try to adapt to the runtime situation that we're encountering: + // There are obviously too many different patterns coming in here... + // So let's turn off the cache since the patterns are unlikely to be reoccurring. + deactivatePatternCache(); + return tokenized; + } + if (cachePatterns == null || cachePatterns.booleanValue()) { + this.tokenizedPatternCache.put(pattern, tokenized); + } + } + return tokenized; + } + + protected String[] tokenizePath(String path) { + return StringUtils.tokenizeToStringArray(path, this.pathSeparator, this.trimTokens, true); + } + + private boolean matchStrings(String pattern, String str, Map<String, String> uriTemplateVariables) { + + return getStringMatcher(pattern).matchStrings(str, uriTemplateVariables); + } + + protected AntPathStringMatcher getStringMatcher(String pattern) { + AntPathStringMatcher matcher = null; + Boolean cachePatterns = this.cachePatterns; + if (cachePatterns == null || cachePatterns.booleanValue()) { + matcher = this.stringMatcherCache.get(pattern); + } + if (matcher == null) { + matcher = new AntPathStringMatcher(pattern, this.caseSensitive); + if (cachePatterns == null && this.stringMatcherCache.size() >= CACHE_TURNOFF_THRESHOLD) { + // Try to adapt to the runtime situation that we're encountering: + // There are obviously too many different patterns coming in here... + // So let's turn off the cache since the patterns are unlikely to be reoccurring. + deactivatePatternCache(); + return matcher; + } + if (cachePatterns == null || cachePatterns.booleanValue()) { + this.stringMatcherCache.put(pattern, matcher); + } + } + return matcher; + } + + @Override + public String extractPathWithinPattern(String pattern, String path) { + String[] patternParts = StringUtils.tokenizeToStringArray(pattern, this.pathSeparator, this.trimTokens, true); + String[] pathParts = StringUtils.tokenizeToStringArray(path, this.pathSeparator, this.trimTokens, true); + StringBuilder builder = new StringBuilder(); + boolean pathStarted = false; + + for (int segment = 0; segment < patternParts.length; segment++) { + String patternPart = patternParts[segment]; + if (patternPart.indexOf('*') > -1 || patternPart.indexOf('?') > -1) { + for (; segment < pathParts.length; segment++) { + if (pathStarted || (segment == 0 && !pattern.startsWith(this.pathSeparator))) { + builder.append(this.pathSeparator); + } + builder.append(pathParts[segment]); + pathStarted = true; + } + } + } + + return builder.toString(); + } + + @Override + public Map<String, String> extractUriTemplateVariables(String pattern, String path) { + Map<String, String> variables = new LinkedHashMap<>(); + boolean result = doMatch(pattern, path, true, variables); + if (!result) { + throw new IllegalStateException("Pattern \"" + pattern + "\" is not a match for \"" + path + "\""); + } + return variables; + } + + @Override + public String combine(String pattern1, String pattern2) { + if (!StringUtils.hasText(pattern1) && !StringUtils.hasText(pattern2)) { + return ""; + } + if (!StringUtils.hasText(pattern1)) { + return pattern2; + } + if (!StringUtils.hasText(pattern2)) { + return pattern1; + } + + boolean pattern1ContainsUriVar = pattern1.indexOf('{') != -1; + if (!pattern1.equals(pattern2) && !pattern1ContainsUriVar && match(pattern1, pattern2)) { + // /* + /hotel -> /hotel ; "/*.*" + "/*.html" -> /*.html + // However /user + /user -> /usr/user ; /{foo} + /bar -> /{foo}/bar + return pattern2; + } + + // /hotels/* + /booking -> /hotels/booking + // /hotels/* + booking -> /hotels/booking + if (pattern1.endsWith(this.pathSeparatorPatternCache.getEndsOnWildCard())) { + return concat(pattern1.substring(0, pattern1.length() - 2), pattern2); + } + + // /hotels/** + /booking -> /hotels/**/booking + // /hotels/** + booking -> /hotels/**/booking + if (pattern1.endsWith(this.pathSeparatorPatternCache.getEndsOnDoubleWildCard())) { + return concat(pattern1, pattern2); + } + + int starDotPos1 = pattern1.indexOf("*."); + if (pattern1ContainsUriVar || starDotPos1 == -1 || this.pathSeparator.equals(".")) { + // simply concatenate the two patterns + return concat(pattern1, pattern2); + } + + String ext1 = pattern1.substring(starDotPos1 + 1); + int dotPos2 = pattern2.indexOf('.'); + String file2 = dotPos2 == -1 ? pattern2 : pattern2.substring(0, dotPos2); + String ext2 = dotPos2 == -1 ? "" : pattern2.substring(dotPos2); + boolean ext1All = ext1.equals(".*") || ext1.isEmpty(); + boolean ext2All = ext2.equals(".*") || ext2.isEmpty(); + if (!ext1All && !ext2All) { + throw new IllegalArgumentException("Cannot combine patterns: " + pattern1 + " vs " + pattern2); + } + String ext = ext1All ? ext2 : ext1; + return file2 + ext; + } + + private String concat(String path1, String path2) { + boolean path1EndsWithSeparator = path1.endsWith(this.pathSeparator); + boolean path2StartsWithSeparator = path2.startsWith(this.pathSeparator); + + if (path1EndsWithSeparator && path2StartsWithSeparator) { + return path1 + path2.substring(1); + } else if (path1EndsWithSeparator || path2StartsWithSeparator) { + return path1 + path2; + } else { + return path1 + this.pathSeparator + path2; + } + } + + @Override + public Comparator<String> getPatternComparator(String path) { + return new AntPatternComparator(path); + } + + protected static class AntPathStringMatcher { + + private static final Pattern GLOB_PATTERN = Pattern.compile("\\?|\\*|\\{((?:\\{[^/]+?}|[^/{}]|\\\\[{}])+?)}"); Review comment: *REDOS:* The regular expression "\\?|\\*|\\{((?:\\{[^/]+?}|[^/{}]|\\\\[{}])+?)}" is vulnerable to a denial of service attack (ReDOS) [(details)](https://find-sec-bugs.github.io/bugs.htm#REDOS) (at-me [in a reply](https://docs.muse.dev/docs/talk-to-muse/) with `help` or `ignore`) -- 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. For queries about this service, please contact Infrastructure at: [email protected]
