[BUG] Filter path parsing implementation is inefficient

[jainankitk]

Describe the bug

The current implementation for filter path evaluation 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" + "." * 4000, json={"query": {"match_all" : {}}}

+ private static FilterPath parse(final String filter, final String segment) {
    int end = segment.length();

    for (int i = 0; i < end;) {
        char c = segment.charAt(i);

        if (c == '.') {
            String current = segment.substring(0, i).replaceAll("\\\\.", ".");
+            return new FilterPath(filter, current, parse(filter, segment.substring(i + 1)));
        }
        ++i;
        if ((c == '\\') && (i < end) && (segment.charAt(i) == '.')) {
            ++i;
        }
    }
    return new FilterPath(filter, segment.replaceAll("\\\\.", "."), EMPTY);
}

Extract from FilterPath.java

Solution

Can be written more efficiently by:

• not using recursion, OR
• using existing more efficient libraries for matching the pattern against string (cons: additional dependency)

Related component

Search:Resiliency

To Reproduce

opensearch-node1       | java.lang.StackOverflowError
opensearch-node1       |    at java.base/java.lang.RuntimeException.<init>(RuntimeException.java:52)
opensearch-node1       |    at java.base/java.lang.IllegalArgumentException.<init>(IllegalArgumentException.java:40)
opensearch-node1       |    at java.base/java.util.regex.PatternSyntaxException.<init>(PatternSyntaxException.java:58)
opensearch-node1       |    at java.base/java.util.regex.Pattern.error(Pattern.java:2028)
opensearch-node1       |    at java.base/java.util.regex.Pattern.<init>(Pattern.java:1432)
opensearch-node1       |    at java.base/java.util.regex.Pattern.compile(Pattern.java:1069)
opensearch-node1       |    at java.base/java.lang.String.replaceAll(String.java:2944)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:119)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:120)
opensearch-node1       |    at org.opensearch.core.xcontent.filtering.FilterPath.parse(FilterPath.java:12

Expected behavior

There should not be any stack overflow error

Related component

Search:Resiliency

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 this issue. @robinf95 Look forward to seeing a pull request.

[reta]

Closing this one as duplicate of #12067