Whitespace Handling in FreshMarker (2)

„It is not the language that makes programs appear simple. It is the programmer that make the language appear simple!“

Robert C. Martin

Im ersten Beitrag zum Whitespace Handling wurde eine einfache Implementierung vorgestellt, die überflüssige Whitespaces entfernt. In diesem Beitrag soll die Implementierung verbessert werden.

Das Herzstück der bisherigen Implementierung war die Methode cleanUpWhitespaces. Diese bekam das Wurzelelement des geparste FreshMarker Template übergeben und entfernt unnötigen Whitespace.

private void cleanUpWhitespaces(Root root) {
  root.getAllTokens(false).stream().filter(t -> t.getType() == TokenType.WHITESPACE)
      .forEach(this::normalizeWhitespaces);
  List<Token> currentLine = new ArrayList<>();
  root.getAllTokens(false).forEach(token -> cleanUpLine(currentLine, token));
}

Die Methode erfüllt ihren Zweck, könnte aber sicherlich verbessert werden. Offensichtlich ruft sie zweimal die teure Methode root.getAllTokens(false) auf, die alle Token aus dem Parse-Tree einsammelt. Die erste Liste wird für die Methode normalizeWhitespaces aufgerufen und die zweite für die Methode cleanUpLine.

Der Hintergrund für das zweimalige Abfragen ist in der Methode normalizeWhitespaces zu finden. Sie modifiziert den Parse-Tree, in dem sie Whitespace Token durch eine Liste neuer Whitespace Token ersetzt. wenn sie Zeilenumbrüche vor dem letzten Zeichen enthalten. Dadurch entstehen Whitespace Token, die keinen Zeilenumbruch enthalten oder einen einzelnen Zeilenumbruch am Ende.

Nicht ganz so offensichtlich verbesserungswürdig ist die Verwendung der Liste currentLine. In dieser Liste werden von der Methode cleanUpLine alle Token gesammelt, die zur aktuellen Zeile gehören.

Wie im letzten Beitrag beschrieben, soll Whitespace aus der aktuellen Zeile gelöscht werden, wenn außer Whitespace am Anfang und Ende, nur Token für FreshMarker Befehle in der Zeile zu finden sind. wurde ein Whitespace mit Zeilenumbruch entdeckt, dann wurde die Liste geprüft, ggf. Token aus dem Parse-Tree gelöscht und die Zeile geleert.

Für diese Evaluierung wird aber keine Liste benötigt, es reichen zwei Attribute. Es muss nur bekannt sein, ob die Zeile Token vom Typ INTERPOLATE, PRINTABLE_CHAR oder WHITESPACE enthält und das erste Token der Zeile, falls es gelöscht werden soll. Das Attribut containNonTag wird auf true gesetzt, sobald eines der Token vom Typ INTERPOLATE, PRINTABLE_CHAR oder WHITESPACE ist. Das Attribut first wird mit dem ersten Token belegt, dass bei einer neuen Zeile angetroffen wird.

private void addNonWhitespaceTokenToLine(Token token) {
  containNonTag = containNonTag || NON_TAG_TOKEN_TYPES.contains(token.getType());
  first = first == null ? token : first;
}

In der Hilfsmethode addNonWhitespaceTokenToLine wird containNonTag auf true gesetzt, wenn das aktuelle Token vom Type INTERPOLATE oder PRINTABLE_CHAR ist. Vom Typ WHITESPACE kann das Token nicht sein, das die Methode nicht für diesen Typ gedacht ist. Das Attribut first wird nur gesetzt, falls es vorher null war.

private void addWhitespaceTokenToLine(Token token) {
  containNonTag = first != null;
  first = first == null ? token : first;
}

In der Methode addWhitespaceTokenToLine wird containNonTag auf true gesetzt, falls das aktuelle Whitespace nicht das erste Whitespace der Zeile ist. Diese Methode wird innerhalb der cleanUpLine Methode verwendet, wenn das übergebene Whitespace Token keinen Zeilenumbruch enthält. Die Verwendung der Methode cleanUpLine hat sich leicht verändert, sie wird nur noch für Whitespace Token aufgerufen.

private void cleanUpLine(Token whitespaceToken) {
  if (!whitespaceToken.getImage().endsWith("\n")) {
    addWhitespaceTokenToLine(whitespaceToken);
    return;
  }
  if (first == null || containNonTag) {
    clearLine();
    return;
  }
  getFirstAsWhitespace().ifPresent(f -> f.getParent().removeChild(f));
  whitespaceToken.getParent().removeChild(whitespaceToken);
  clearLine();
}

Für ein Whitespace Token mit Zeilenumbruch wird die Methode beendet, wenn das Attribute first und somit die Zeile leer ist oder das Attribute containNonTag den Wert true enthält und damit Token enthält, die das Löschen von Whitespace verbieten. Ansonsten werden in den letzten beiden Zeilen die Whitespace Token entfernt.

Die Methode normalizeWhitespaces hat sich auch verändert. Im Gegensatz zur ersten Implementierung wird sie nicht getrennt von der cleanUpLine Methode aufgerufen, sondern mit ihr verschränkt. Die cleanUpLine Methode wird innerhalb der normalizeWhitespaces aufgerufen, wenn es sich um Whitespace Token handelt.

private void normalizeWhitespaces(Token token) {
  if (token.getType() != TokenType.WHITESPACE) {
    addNonWhitespaceTokenToLine(token);
    return;
  }
  String image = token.getImage();
  int index = image.indexOf("\n");
  if (index == -1 || index == image.length() - 1) {
    cleanUpLine(token);
    return;
  }
  int beginOffset = token.getBeginOffset();
  int endOffset = token.getEndOffset();
  Node parent = token.getParent();
  int tokenIndex = parent.indexOf(token);
  parent.removeChild(token);
  int start = beginOffset;
  List<Token> list = new ArrayList<>();
  for (int i = 0; i < image.length(); i++) {
    char c = image.charAt(i);
    if (c == '\n') {
      Token newToken = newToken(token, start, beginOffset + i + 1);
      list.add(newToken);
      parent.addChild(tokenIndex, newToken);
      tokenIndex++;
      start = beginOffset + i + 1;
    }
  }
  if (start <= endOffset) {
    Token newToken = newToken(token, start, endOffset);
    list.add(newToken);
    parent.addChild(tokenIndex, newToken);
  }
  list.forEach(this::cleanUpLine);
}

Auf diese Weise wird nur noch ein Durchlauf durch den Parse-Tree benötig. Die cleanUpWhitespaces Methode vereinfacht sich dadurch auf den folgenden Einzeiler.

public void cleanUpWhitespaces(Root root) {
  root.getAllTokens(false).forEach(this::normalizeWhitespaces);
}

Die Veränderungen im Sourcecode haben die Verarbeitung der Whitespace Token beschleunigt. Dabei hat sich in diesem Fall nicht der algorithmische Ansatz als Hebel der Verbesserung angeboten, sondern die Datenstrukturen, mit denen das Problem beschrieben wurde.

Auch die neue Version der FreshMarker Template-Engine ist auf Maven Central zu finden. Viel Spaß!

<dependency>
  <groupId>de.schegge</groupId>
  <artifactId>freshmarker</artifactId>
  <version>0.2.2</version>
</dependency>

Schreibe einen Kommentar