Идеальный SAST. Тестируем парсеры

Пока индексируется github (спасибо лимиту в 5000 запросов в час), который нужен для получения данных для статьи, поговорим пока о тестировании лексеров и парсеров. Обсудим пожелания к процессу разработки грамматик, их тестирования и контроля качества так, что бы не превращаться в существо на картинке.

Основной проблемой разработки парсеров является высокая вариативность входных данных, комбинации элементов языка могут и с ума свести, особенно если это какой-нибудь С++. Разумеется можно брать большие массивы исходных кодов и ждать сутками, пока все проанализиуется и вы получите отчет об ошибках. Но проблема в том, что нужно TDD, причем такое, что бы максимум за 15 секунд можно было получить хотя бы 100% покрытие всех вариантов грамматики (включая комбинации). Особо следует упомянуть лексер, так как часто даже с токенами бывают проблемы.

Для покрытия такого большого количества вариантов грамматик в столь короткое время придется рассчитывать только на малые примеры, демонстрирующие конкретную работу парсера, например:

class Example {
    boolean flag;
}

Разумеется читатель может подумать, в чем смысл таких тестов, если они столь просты? Так и сам парсер является простым, но после него начинается такая жесть, которую без гарантии, что парсер точно работает как надо, отладить может оказаться очень трудно, потому что будете тратить время на лишние кейсы, которые надо проверить. В итоге время теряется на пустяки.

Очевидным преимуществом малых примеров, корректных с точки зрения парсера (или синтаксически правильных, семантику не нужно трогать), является возможность задавать таких вариантов тысячи, гарантируя, что отработают все за крайне малое время, позволяя разработчику в любой момент скомпилировать проект и запустить тесты, что бы проверить работу. Разработка парсера превращается в TDD, когда ты в начале пишешь пример для разбора, а затем пишешь правила.

Так же к достоинству можно отнести тот факт, что если что-то сломается, то человеку проще будет искать в десятке файлов нужную информацию, чем в огромном файле десяток участков, это не говоря о том, что находить дельты больших файлов - та еще проблема.

Однако есть недостаток, нужно уметь видеть какие варианты для грамматик являются уникальными наборами, вы же не будете говорить, что поменяв имя переменной в примере вы добавили новый кейс? Идентификаторы вы можете протестировать в отдельной папке, не вдаваясь в подробности этой фичи в другом месте.

Предлагаю рассмотреть следующий вариант: у нас есть язык C# и тернарный оператор, вопрос, сколько уникальных вариантов использования можно выбрать? (Можете написать в комментарии) Пока что вот вам несколько важных вариантов:

1. ID ? ID : ID

2. ID ? LITERAL : LITERAL

3. ID? ? ANY : ANY

И это только малая часть! При разработке грамматики для C# смог получить именно проблему, что парсер не справлялся с вариантом value is MyType ? var1 : var2, потому что он пытался парсить, используя знак ? не как тернарный оператор. Antlr просто не хватало глубины поиска в правилах и он не мог поймать тернарку. При этом это мелкая проблема, которую вытаскивать анализируя большие массивы информации совершенно неприемлимо. В то же время, даже если вы обнаружили такой баг на большом коде, это не помешает вытащить из него достаточно малый участок, что бы воспроизвести баг и отладить его, не заморачивась лишними данными вокруг. Что лучше, 1 раз отладится на 100 мб проекте целый час или хоть 1000 раз запустить тест на 0.001 секунду ?

Тестируем лексер

Для того, что бы точно быть уверенным в иммутабельности вывода лексера и дать гарантию следующим этапам обработки, следует закрепить вывод токенов. Этап токенизации берет на себя лексер, так же именно в этом этапе выгодно добавлять препроцессирование, так что бы на выходе можно было получить сразу готовый поток токенов. Для таких языков как С++ лексер просто необходимо запускать отдельно от парсера, что бы получать корректный вывод - иначе вы все макросы не раскроете. Соответственно для него нужно в начале все файлы прогнать через лексер, а только потом парсер.

Одним из вариантов является сохранение как есть потока результата работы лексера - токенов в файл, вот только бинарные файлы люди пока читать не научились, поэтому предлагаю использовать json, это поможет не только видеть изменения через дельты с минимальными шумами, но так же позволит автоматизировать поиск разницы.

{
  "tokens" : [ {
    "tokenType" : "PACKAGE",
    "statement" : "1:0[7]"
  }, {
    "tokenType" : "Identifier",
    "statement" : "1:8[7]",
    "text" : "example"
  }, {
    "tokenType" : "SEMI",
    "statement" : "1:15[1]"
  }, {
    "tokenType" : "CLASS",
    "statement" : "3:0[5]"
  }, {
    "tokenType" : "Identifier",
    "statement" : "3:6[7]",
    "text" : "Example"
  }, {
    "tokenType" : "FoldBlock",
    "statement" : "3:14[21]",
    "children" : {
      "tokens" : [ {
        "tokenType" : "LBRACE",
        "statement" : "3:14[1]"
      }, {
        "tokenType" : "BOOLEAN",
        "statement" : "4:4[7]"
      }, {
        "tokenType" : "Identifier",
        "statement" : "4:12[4]",
        "text" : "flag"
      }, {
        "tokenType" : "SEMI",
        "statement" : "4:16[1]"
      }, {
        "tokenType" : "RBRACE",
        "statement" : "5:0[1]"
      }, {
        "tokenType" : "EOF",
        "statement" : "5:1[3]"
      } ]
    }
  }, {
    "tokenType" : "EOF",
    "statement" : "6:0[5]"
  } ]
}

Уверен, что вам не составит труда обнаружить разницу, если в файле что-то поменяется или вы измените обработку токенов.

Следует отметить, что токены характеризуются не только типом, но и текстом, при это для каких-то токенов нам текст не важен, поэтому где-то необходимо хранить список типов токенов, для которых текст нужно хранить. В моем примере для этого используется ParserService, но у вас может быть даже статик, если одного языка для вас достаточно, либо вовсе вшить эти данные в тест, что отчасти не самый лучший вариант (причина будет позже).

Имея на руках такой дамп представления файла, довольно легко написать юнит-тест:

  def testLexer(suite: Suite): Unit = {
    implicit val ps: ParserService = ParserService(suite.language)
    for (fi <- suite.fileInfos) {
      assertFile(fi.file)
      val lexerOutput: LexerOutput = readFromFile[LexerOutput](testConfig(LexerSuiteDir, suite, fi.file))
      val lexer = ps.newLexer(asVirtualFile(fi))
      val stream = new CommonTokenStream(lexer)
      stream.fill()
      val tokens = CollectionConverters.asScala(stream.getTokens)
      assertTokens(lexer, lexerOutput, tokens)
    }
  }
  
  private def assertTokens(lexer: AbstractRScanLexer, lexerOutput: LexerOutput, tokens: mutable.Buffer[Token]): Unit = {
    val queue = new mutable.Queue[LexerOutputToken]()
    queue ++= lexerOutput.tokens
    for (t <- tokens) {
      assertTrue(queue.nonEmpty, "Queue should not be empty")
      val lot = queue.dequeue()
      val tokenType = lexer.getVocabulary.getSymbolicName(t.getType)
      assertEquals(lot.tokenType, tokenType, "Token types are not equal")
      assertEquals(lot.statement, tokenStatement(t), "Token types are not equal")
      if (lot.text != null) {
        assertEquals(lot.text, t.getText, "Texts are not equal")
      }
      if (lot.children != null) {
        assertTrue(t.isInstanceOf[RScanToken], "Must be RScanToken")
        val rt = t.asInstanceOf[RScanToken]
        assertTrue(rt.foldedTokens().nonEmpty, "Must have fold tokens")
        assertTokens(lexer, lot.children, rt.foldedTokens().toBuffer)
      } else {
        assertFalse(t.isInstanceOf[RScanToken] && t.asInstanceOf[RScanToken].foldedTokens().nonEmpty, "No fold tokens allowed")
      }
    }
    if (queue.nonEmpty && queue.head.tokenType.equals("EOF")) queue.dequeue()
    assertTrue(queue.isEmpty, "Queue must be empty")
  }

Все что мы делаем - это проверяем, что бы в потоке токенов совпадал ключ и специальный текст, если же у нас токен содержит свертку, то всего лишь рекурсивно продолжаем проверку токенов.

Выделив код в библиотеку можно добавить тестирование лексера, всего лишь написав конфигурацию для теста:

class JavaParserTest extends AbstractJUnitAntlr4Test {

  @ParameterizedTest(name = "[{index}] {0}")
  @MethodSource(Array("testFiles"))
  override def testLexer(suite: Suite): Unit = {
    super.testLexer(suite)
  }

  @ParameterizedTest(name = "[{index}] {0}")
  @MethodSource(Array("testFiles"))
  override def testParser(suite: Suite): Unit = {
    super.testParser(suite)
  }
}


object JavaParserTest {
  private val TestDataDirectory = "/test/java/unit"

  def testFiles: java.util.stream.Stream[Arguments] = Antlr4TestUtils.filesFromResourceDirectory(JavaLanguage.ref, TestDataDirectory, getClass, Seq("java"))
}

Данный тест создаст из ресурсной папки /test/java/unit коллекцию тестовых наборов данных (suite), а уже junit создаст все необходимые тесты и передаст каждый из них в качестве параметра нашему методу testLexer, вызываем затем родительский метод и вуаля - наша грамматика тестируется, и так для любого языка. Генерируем дампы и запускаем тест!

java -Xmx128m -Dfile.encoding=UTF-8 -classpath $CLASSPATH \
  org.lastrix.rscan.test.ParserTestSuiteGenerator \
  -l Java -d $TEST_PATH -e .java

./gradlew clean test

Тестируем парсер

Тестировать лексер - задача простая и тривиальная. Но основной сложностью при тестировании парсера является то, каким образом вы работаете с AST. Идеальным вариантом было бы работать не с сырым AST, а обогащенным, уже снабженным данными, которые позволят сократить объем выходных данных, например вот так:

{
  "languageName" : "Java",
  "items" : [ {
    "keyText" : "RAW_DECL_PACKAGE at field000.java[1:0-5:1]",
    "children" : [ {
      "keyText" : "NAME at field000.java[1:8-1:15]",
      "children" : [ {
        "keyText" : "UNRESOLVED_ID at field000.java[1:8-1:15]",
        "specText" : "example"
      } ]
    }, {
      "keyText" : "RAW_DECL_CLASS at field000.java[3:0-5:1]",
      "children" : [ {
        "keyText" : "NAME at field000.java[3:6-3:13]",
        "children" : [ {
          "keyText" : "UNRESOLVED_ID at field000.java[3:6-3:13]",
          "specText" : "Example"
        } ]
      }, {
        "keyText" : "MEMBERS at field000.java[3:14-5:1]",
        "children" : [ {
          "keyText" : "RAW_DECL_FIELD at field000.java[4:4-4:16]",
          "children" : [ {
            "keyText" : "RAW_TYPE at field000.java[4:4-4:11]",
            "children" : [ {
              "keyText" : "UNRESOLVED_ID at field000.java[4:4-4:11]",
              "specText" : "boolean"
            } ]
          }, {
            "keyText" : "RAW_DECL_VARIABLE at field000.java[4:12-4:16]",
            "children" : [ {
              "keyText" : "NAME at field000.java[4:12-4:16]",
              "children" : [ {
                "keyText" : "UNRESOLVED_ID at field000.java[4:12-4:16]",
                "specText" : "flag"
              } ]
            } ]
          } ]
        } ]
      } ]
    } ]
  } ]
}

При этом любое изменение в представлении или изменении в исходном коде выльется в изменение структуры выходных данных так, что дельта изменений будет минимальной и затронет только измененные участки.

Самое простое теперь, это написать юнит-тест, что бы проверить, что парсер выдает именно то, что от него ожидают:

  def testParser(suite: Suite): Unit = {
    implicit val ps: ParserService = ParserService(suite.language)
    for (fi <- suite.fileInfos) {
      assertFile(fi.file)
      val parserOutput: ParserOutput = readFromFile[ParserOutput](testConfig(ParserSuiteDir, suite, fi.file))
      val op = antlr4.parseFile(asVirtualFile(fi))
      assertTrue(op.isInstanceOf[RLangOp], "Must be RLangOp")
      assertEquals(parserOutput.languageName, op.asInstanceOf[RLangOp].language.name, "Languages are not equal")
      assertOperations(op.key, op.children, parserOutput.items)
    }
  }

  private def assertOperations(ownerKey: ROpKey, children: Seq[ROp], items: Seq[ParserOutputItem]): Unit = {
    if (children.isEmpty) {
      assertTrue(items == null || items.isEmpty, s"No items in operation: $ownerKey")
      return
    } else if (items == null) {
      Assertions.fail(s"Missing child operations: $ownerKey")
    }
    val queue = new mutable.Queue[ParserOutputItem]()
    queue ++= items
    for (child <- children) {
      assertTrue(queue.nonEmpty, s"Must not be empty at: ${child.key}")
      val poi = queue.dequeue()
      assertEquals(poi.keyText, child.key.toString, "Key text is not equal")
      assertEquals(poi.specText, child.specText, "SpecText is not equal")
      assertOperations(child.key, child.children, poi.children)
    }
    assertTrue(queue.isEmpty, s"Queue must be empty for: $ownerKey")
  }

Теперь парсер будет гарантированно выдавать одно и тоже, проверка работы парсера может быть включена в CI/CD и гарантировать хотя бы формально, что парсер действительно работает в соответствии со спецификацией языка (разумеется если примеры подобраны корректные и разработчик не спал на работе). Имея на руках такую базу коротких примеров, в случае обнаружения ошибки, даже если половина файлов потребует изменений (что вряд ли), все равно не нужно будет смотреть все подряд - потому что все фичи во всех ЯП обладают иерархичностью из-за чего вы можете называть папки не просто по названию, но и добавив порядковый номер. При таком подходе может вовсе и не потребоваться смотреть все. Исправил первые две, а остальные 100 сами решились. Правильно выстраивая иерархию в ваших тестовых данных вы сможете сократить время на разработку и отладку на порядки.

Но самым важным преимуществом такого подхода к тестированию парсера является увеличение скорости разработки парсеров без потери качества, снижение трудозатрат, а ваши разработчики не будут превращаться в существ на обложке статьи, повторяющих одно и то же "тестируем". Зачем тратить недели рабочего времени, если то же самое можно сделать за пару секунд?

Для генерации тестовых дампов используется специальный класс org.lastrix.rscan.test.ParserTestSuiteGenerator, причем по сути система тестирования обладает двумя режимами. В первом режиме (основном), она верифицирует, что все работает как нужно, во втором, она помогает разработчику видеть наглядно, как его правки в грамматику влияют на изменение вывода (вы же не забыли, что все тестовые дампы у нас в репозиторий добавляются?), соответственно сделали правку, запустили генератор дампов и сразу увидели разницу, тем более что Intellij IDEA позволяет спокойно работать с тысячами измененных файлов - хуже, если файлы больше 4 кб. А имея на руках большую библиотеку вход-выход, можно и с внутренней документацией работу упростить, отчасти ее генерируя из тестовых данных. После парсера же еще этапы есть, не так ли?

Полный исходный код проекта для тестирования парсера языка Java, можно найти тут . В пример включено небольшое множество тестовых данных (478 примеров), на моей машине (intel i7 9700k) обработка занимает всего 1s 45ms, при этом 65% строк кода парсера покрывается этими тестами.

Заключение

В статье предложен подход к тестированию лексеров и парсеров, позволяющий ускорить разработку и отказаться от дедовского подхода, когда для проверки работы грамматики вам требовалось анализировать тысячи огромных проектов, что бы выцепить маленький баг. Писать руками огромное количество кода по проверке результата работы - все это можно автоматизировать, кроме пожалуй проверки результата генерации. Несмотря на то, что полностью отказаться от варианта тестирования тестирования большим кодом нельзя, можно сократить необходимость прибегать к такому подходу. Обнаруженный баг на большом коде можно легко воспроизвести на малом и в дальнейшем уже контролировать эту проблему.