[BUG] Glob matching implementation is inefficient

[jainankitk]

Describe the bug

The current implementation for glob matching is really inefficient, recursively invoking method for every * pattern, when many of those can be skipped altogether. For example, it breaks for simple match all request with 4k * appended together (assuming small size JVM like 512k):

_search?filter_path=hits" + "*" * 4030, json={"query": {"match_all" : {}}}

+    public static boolean globMatch(String pattern, String str) {
        
        /* code */
        
        if (firstIndex == 0) {
            if (pattern.length() == 1) {
                return true;
            }
            int nextIndex = pattern.indexOf('*', firstIndex + 1);
            if (nextIndex == -1) {
                return str.endsWith(pattern.substring(1));
            } else if (nextIndex == 1) {
                // Double wildcard "**" - skipping the first "*"
+                return globMatch(pattern.substring(1), str);
            }
        /* code */
    }

Extract from Glob.java

Solution
Can be written more efficiently by:

• not using recursion, OR
• converting glob to regex pattern and using existing more efficient libraries for matching the pattern against string, OR
• using more efficient library for glob matching (cons: additional dependency)

Related component

Search:Resiliency

To Reproduce

opensearch-node1       | java.lang.StackOverflowError: null
opensearch-node1       |    at java.lang.String.indexOf(String.java:2423) ~[?:?]
opensearch-node1       |    at java.lang.String.indexOf(String.java:2380) ~[?:?]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:55) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]
opensearch-node1       |    at org.opensearch.common.Glob.globMatch(Glob.java:68) ~[opensearch-common-2.11.1.jar:2.11.1]

Expected behavior

There should not be any stack overflow error

[robinf95]

Would take this issue.

[peternied]

[Triage - attendees 1 2 3 4 5 6 7 8]
@jainankitk Thanks for filing, @robinf95 Look forward to a PR - thanks for volunteering.

[reta]

Closing as duplicate of #12065