Superficial Reflections ⟶ java

Exponential backtracking

The post's title already spoils it: the change is related to backtracking. OpenJDK's Pattern implements quantifiers in regular expressions by trying out the different possibilities and it then backtracks in case there was no match. So for example, to see if a matches the pattern a?a, first the pattern aa is tried and because it doesn't match (not enough as in the input), the matching backtracks to the beginning and tries the pattern a next, which then succeeds.

Now let's see what happens if the input 1111a is matched against the pattern (1*)* in OpenJDK 8, like in the following code: Pattern.compile("(1*)*").matcher("1111a").matches()). In words: in a group, match zero or more 1s and repeat that group zero or more times.

In the beginning, the 1* inside the group matches greedily all characters 1 in the input until the a. Then the remaining input (the a) is used as input for the remaining part of the regex, which is the group repetition. The group is repeated again, but 1* still doesn't match the a and the matching fails because not all input is used. Note that the implementation is smart enough to not try to repeat the group forever with a zero-width match for 1*.

The implementation then remembers that in the beginning, it consumed all the 1s greedily. The question is: would the regex probably match the input if the first greedy matching doesn't consume all the 1s, but all except the last one? So the implementation backtracks to the point where it consumed all but the last 1 and then tries to match the remaining regex against the input 1a. This approach still doesn't result in a match. That means another backtrack and 11a is tried next. The big problem is now: that input 11a will be again first matched greedily by 1*, because remaining regex means the group repetition. And as there is still no match due to the trailing a, this matching as part of the backtracking will backtrack as well.

In other words, for every character 1 in the input, there are two choices: match and consume the character as part of the sub-expression 1* or don't match and continue with the remaining expression (the group repetition). That results in 2ⁿ different combinations that need to be tested, with n being the number of leading 1s in the input. There will never be a match, but that will only be known after every combination has been tested. So, exponential runtime.

This is not exactly big news. The phenomena of catastrophic backtracking is well understood and there are various ways how either the regular expression can be changed to avoid the backtracking (see for example The Explosive Quantifier Trap ) or how regexes can be implemented without backtracking (see for example Regular Expression Matching Can Be Simple And Fast). It is even known as an attack under the name ReDoS and has its own OWASP entry.

The change in OpenJDK 9

In OpenJDK, an optimization was added to avoid the exponential backtracking. Whenever a greedy repetition (*, +, curly braces, etc) doesn't match some input, the input's cursor position is memoized. Then, when the repetition is executed again during backtracking, it's checked whether it already failed to match for this cursor position and if so, the repetition isn't tested at all (as it will fail no match).

How does that help against exponential backtracking? Let's have a look again at the previous regex (\d*) that should match the input 1111a. First the greedy match of the 1s, then the failed attempt to match a and then the backtracking of the first greedy match. The first backtracking attempt is with the remaining input 1a. It doesn't match and it's memoized that this input failed. Then 11a is tried next. It also fails to match, but it also backtracks itself due to the first greedy match on the leading 11. During that backtracking, the inputs 1a and 11a need to be tested, but only the former is actually tested, due to the latter being memoized to have failed. Hence the backtracking is now linear instead of exponential.

Note that this optimization only works if the pattern doesn't use any backreferences.

More questions? Then study the source of OpenJDK's Pattern implementation!

Prior Art

Da Links erzeugen ein Recht häufiges Problem ist, gibt es natürlich so einiges an Prior Art. Wahrscheinlich in so ziemlich jedem Webrahmenwerk, in den unterschiedlichsten Ausprägungen. Ich habe stellvertretend einmal drei herausgegriffen:

• Pyramids route_url

  Zeigt schon mal die grobe Idee, wenn auch in Python und nicht in Java. Gewisse Fehler werden abgefangen (falsche Anzahl an Argumenten zum Beispiel). Allerdings passiert alles zur Laufzeit. Man braucht also eine recht gut ausgeprägte Test-Suite, um Fehler beim Linken zu erkennen.

• Declarative Hyperlinking in Jersey

  Mit Annotationen umgesetzt und dadurch stringly typed. Fehler werden erst zur Laufzeit erkannt.

• Spring HATEOAS

  Kommt schon recht nahe dran. Insbesondere Building links pointing to methods geht stark in die Richtung:

  Method method = PersonController.class.getMethod("show", Long.class);
  Link link = linkTo(method, 2L);
  

  Allerdings funktioniert die Methoden-Auflösung zur Laufzeit und via Name als String. Die Parametertypen müssen explizit angegeben werden und die Typüberprüfung passiert ebenfalls erst zur Laufzeit.

Warum nicht Methodenreferenzen?

Da Java 8 endlich Methodenreferenzen eingeführt hat, liegt natürlich die Idee nahe, es damit irgendwie zu versuchen.

Stellen wir uns vor, dass wir den folgenden Controller hätten:

@Path("/hello")
class HelloWorldController {

    @GET
    public String hello() {
        return "Hello, world!";
    }
}

Als erstes erstellen wir ein FunctionalInterface. Das Interface soll eine Referenz auf eine Methode der Klasse H darstellen, die keine Parameter entgegen nimmt und ein R als Ergebnis zurück gibt. Dementsprechend sieht das Interface wie folgt aus:

@FunctionalInterface
interface NoParam<H, R> {
    R apply(H h);
}

Dieses Interface kann aus einer Methodenreferenz erstellt werden:

NoParam<HelloWorldController, String> hello = HelloWorldController::hello;
// Aufrufen könnte man die Methode jetzt so (angenommen,
// someHelloWorldController ist eine Instanz von HelloWorldController):
String result = hello.apply(someHelloWorldController);
assert "Hello, world!".equals(result);

Folglich können wir damit dann die folgende Methode bauen:

<H, R> URI linkTo(NoParam<H, R> handler) {
    // Hier der Code, der die Routing-Informationen von handler ausliest und
    // daraus dann eine URI baut
}

Jetzt ist es möglich, aus einem anderen Controller heraus einen Link zu unserer gewünschten Methode HelloWorldController#hello() zu bauen:

URI helloLink = linkTo(HelloWorldController::hello);

Wenn wir ein Argument zu viel übergeben würden (zum Beispiel, weil wir denken, dass die hello-Ressource einen Namen entgegen nimmt, um einen personalisierten Gruß zu erzeugen, kompiliert der Code nicht:

java: no suitable method found for linkTo(HelloWorldController::hello)

Ziel erreicht. Um tatsächlich Pfad-Parameter zu unterstützen, müssen wir jetzt einfach (relativ mechanisch) weitere Interfaces einführen.

Erweitern wir zunächst unseren Controller um einen personalisierten Gruß:

@GET
@Path("/{name}")
public String greeting(String name) {
    return "Hello, " + name + "!";
}

Der Parameter name repräsentiert hierbei die Pfad-Variable name. Links dazu können dann folgenderweise erstellt werden:

URI link = linkTo(HelloWorldController::greeting, "Joe");

Dazu führen wir ein weiteres Interface ein:

@FunctionalInterface
interface OneParam<H, P, R> {
    R apply(H h, P p);
}

Wenig überraschend steht H hierbei für den Typ des Controllers, P für den Parameter und R für den Rückgabewert.

Desweiteren muss eine weitere Überladung von linkTo eingeführt werden:

URI linkTo(OneParam<H, P, R> handler, P param) {
    // Hier wieder Routing-Infos von handler auslesen und dann param einsetzen
}

Das ist zum Implementieren zwar ein wenig wortreich (für jede Anzahl an Pfad-Variablen ein eigenes Interface und eine entsprechende linkTo-Methode), aber das muss man zum Glück nur einmal tun und außerdem hat man ja auch nicht unendlich lange Pfade in der Praxis.

Viel gravierender ist jedoch: es funktioniert überhaupt nicht. Man kann zwar aus einer Methodenreferenz ein Lambda bauen. Allerdings geht die Information, aus welcher Methode das Lambda erzeugt wird, dabei verloren. Wir brauchen die Information, um welche Methode es sich handelt, jedoch, da wir ansonsten nicht an die Route kommen.

Proxies to the rescue

Da die Antwort auf die meisten Probleme in Java "(dynamische) Code-Generierung" ist, probieren wir es doch auch einmal damit. Genauer gesagt dynamische Proxy-Objekte. Die Idee ist dabei folgendermaßen:

• Wir erzeugen uns ein Proxy-Objekt vom gleichen Typ der Handler-Klasse.
• Wir rufen die Methode auf, die übergeben wurde (genauer gesagt, das Lambda)
• Das Proxy-Objekt ruft nicht wirklich die eigentliche Methode auf, sondern merkt sich einfach, welche Methode aufgerufen wurde.
• Wir holen uns die gemerkte Methode vom Proxy-Objekt.

Gehen wir davon aus, dass wir eine Klasse MethodResolver<T>, die die Proxy-Objekte erstellt, könnte unsere linkTo-Methode also in der Art aussehen:

URI linkto(Class<H> handlerClass, OneParam<H, P, R> handler, P param) {
    MethodResolver<H> methodResolver = MethodResolver.on(handlerClass);
    handler.apply(methodResolver, param);
    Method method = methodResolver.resolve();
    // Mit handlerClass und method kann man jetzt an die Routing-Informationen
    // kommen
}

Die meisten AOP-Rahmenwerke bieten Method-Interceptors an, mit denen man das recht einfach umsetzen kann. Für Proxetta könnte ein entsprechendes Advice zum Beispiel so aussehen:

/**
 * MethodResolver advice applied on all methods. It puts the method in a class
 * variable that can be accessed later using reflection.
 */
class MethodResolverAdvice implements ProxyAdvice {

    public Method method;

    public Object execute() {
        final Class<?> targetClass = targetClass();
        final String methodName = targetMethodName();
        final Class<?>[] argumentTypes = createArgumentsClassArray();
        try {
            method = targetClass.getMethod(methodName, argumentTypes);
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e);
        }
        return returnValue(null);
    }
}

Beispielimplementierung

Im Github-Repo java8_linking_experiments habe ich eine Beispielimplementierung für das Ratpack-Mikro-Webrahmenwerk umgesetzt.