SAST sempurna. Parser

Serangkaian artikel dikhususkan untuk menggambarkan pendekatan optimal untuk mengimplementasikan alat analisis kode statis, yang dirancang untuk spesialis. Tujuan dari pekerjaan ini adalah pendekatan, model, dan teknik untuk mendapatkan kinerja alat yang maksimal sambil meminimalkan kerumitan dalam mengembangkan dan mendukung / mengubah alat tersebut. Artikel ini membahas cara untuk mempercepat pengurai dan mengurangi konsumsi memori. Artikel ini disusun sehingga pembaca membaca manual yang ditulis oleh Terrence Parr.

Menggunakan ANTLR secara maksimal


ANTLR berfungsi dengan baik antara 1 kb dan 10 kb, file yang lebih besar tidak akan diuraikan oleh pustaka ini dengan kecepatan maksimum. Juga pekerjaan debug pada file besar menjadi hampir tidak mungkin. Alasan utama mengapa Anda perlu menyimpan data input untuk parser dalam batas yang ditentukan adalah bahwa algoritma prediksi cabang untuk ANTLR secara aktif menggunakan stack, jadi dengan cara apa pun Anda perlu menyingkirkan loop dalam tata bahasa ketika satu aturan menyebut dirinya sendiri melalui banyak aturan lain, termasuk tertentu kondisi aktivasi untuk koneksi seperti itu, pertimbangkan sebuah contoh:

var f = fun a(b) { b = 10; return b; }

Kode ini dapat dijelaskan dengan tata bahasa berikut:

start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'

Sangat mudah untuk melihat bahwa stmt disebut di dalam aturan funDecl, yang membentuk sebuah loop yang dalam aplikasi nyata dapat menyebabkan file 100 kb memerlukan tumpukan RAM 4 GB untuk kinerja maksimum, atau bahkan kemampuan untuk bekerja, yang merupakan situasi yang sama sekali tidak dapat diterima .

Salah satu cara untuk mengatasi kelemahan ini adalah dengan menambahkan modifikasi khusus dalam proses pembuatan token, yaitu, konvolusi blok {} menjadi token, dengan pemrosesan token ini nanti dalam parser baru, ke input yang token yang diciutkan akan ditransmisikan.

Untuk melakukan ini, di ANTLR Anda dapat mengganti metode org.antlr.v4.runtime.Lexer # nextToken dari lexer, di mana Anda dapat mengimplementasikan fungsi konvolusi:

  override def nextToken(): Token = super.nextToken() match {
      case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
      case x: Token => x
  }

  def buildFoldToken(start: RScanToken): RScanToken = {
    val (token, list) = createFoldBlockBody(
      mutable.MutableList[RScanToken]()
        ++ List(start.asInstanceOf[RScanToken])
    )
    val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
    result.setLine(start.getLine)
    result.setCharPositionInLine(start.getCharPositionInLine)
    result.setFoldedTokens(list)
    result
  }

  private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
    var current: RScanToken = null
    while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
      current = nextToken().asInstanceOf[RScanToken]
      list += current
    }
    if (current.getType == Token.EOF)
      throw new IllegalStateException()
    (current, list)
  }

Tata bahasa harus dilengkapi dengan:

startJavaScript 
    :   HashBangLine? jsFileBody? EOF
    ;

startFoldBlock
   :   block EOF
   ;

block
    :   LBRACE stmtList? RBRACE
    |   FoldBlock 
//     ,
//     startFoldBlock
    ;

Dengan pendekatan ini, isi konvolusi tidak akan diproses sekali lagi, karena algoritma rekursif akan menyerap token dan menyimpannya.

Kecepatan pemrosesan tumbuh dari 2 menjadi 10 kali, perbedaannya menjadi sangat nyata pada file js yang diperkecil.

Dampak pada operasi ANTLR dari optimasi yang diusulkan menggunakan beberapa file javascript sebagai contoh:
MengajukanUkuran kbSebelum optimasi, msSetelah optimasi, ms
menormalkan-dan-memuat-metadata.js1018391372
rewrite-live-Reference.js8899528
dom.umd.min.js130438526607
react.pure.umd.min.js139516686495
tsserver.js8151362857117787

Tanpa optimasi, pekerjaan dilakukan dalam satu utas, dengan optimasi, jika mungkin, pemrosesan paralel.

Peluncuran ini dilakukan pada mesin dengan RAM 64 GB, Intel® Core (TM) i7-9700K CPU @ 3,60GHz, OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.4 + 11).

Kunci startup JVM: -Xmx4G -XX: + UseG1GC -XX: MaxHeapFreeRatio = 30 -XX: MinHeapFreeRatio = 10
Untuk file tsserver.js, kuncinya adalah -Xmx32G, sementara konsumsi memori telah mencapai 22 GB! Sementara file yang diperkecil hingga 200 kb dengan optimisasi dianalisis dengan batas tumpukan 128 mb dalam mode paralel tanpa perlu pengumpul sampah untuk memuat prosesor, maksimum 2%!

Pembuatan profil


ANTLR mendukung pembuatan profil parser / lexer dalam runtime. Untuk mengaktifkannya, Anda perlu memanggil metode: org.antlr.v4.runtime.Parser # setProfile sebelum aturan dijalankan. Maka Anda bisa mendapatkan semua informasi, misalnya dengan cara ini:

    private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {
      // do the actual parsing
      val parseInfo = parser.getParseInfo
      val atn = parser.getATN
      for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {
        val ds = atn.decisionToState.get(di.decision)
        val ruleName = parser.ruleName(ds.ruleIndex)
        log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)
        log.debug("=========================")
        log.debug(tokenStream.getText)
        log.debug("=========================")
      }
    }

Nilai tambah yang jelas dengan metode ini adalah pengurangan jumlah data yang perlu Anda analisis, karena konvolusi dapat diganti dengan {} dan selalu bekerja dalam konvolusi lokal, yang sangat mempercepat proses optimalisasi tata bahasa.

Kesimpulan


Artikel ini mengusulkan metode untuk mengoptimalkan kerja tata bahasa formal yang dilaksanakan menggunakan perpustakaan ANTLR, meskipun pendekatan itu sendiri dapat dicoba untuk diterapkan ke perpustakaan lain juga. Fitur optimasi adalah pengurangan jumlah transisi ke depan untuk memvalidasi aliran token input. Ini juga memungkinkan Anda untuk menganalisis file besar (lebih dari 1 mb) dengan biaya memori 512 mb untuk pemrosesan single-threaded, sementara kurangnya optimasi akan membutuhkan 50 kali lebih banyak memori untuk bekerja cepat menggunakan tata bahasa yang sama.

Kode sumber tersedia di github. Proyek ini dibuat untuk menunjukkan pekerjaan optimasi. Proyek ini disederhanakan sebanyak mungkin, disarankan untuk memulai studi di kelas GrammarTester, konfigurasi peluncuran telah dibuat untuk itu, Anda hanya perlu mendaftarkan jalur ke folder dengan data input. Perhatikan kunci rscan.tester.cache.dir, file sementara akan ditulis ke folder ini, analisis file yang berhasil diperbaiki dalam folder ini dan tidak akan membiarkan parser menganalisisnya untuk kedua kalinya - nyaman untuk memperbaiki kesalahan. Saat ini, tata bahasa telah diuji pada 17 ribu file dari node_modules yang dibuat untuk aplikasi reaksi inti. Hanya node_modules bersarang yang diabaikan.

Pada artikel berikutnya, kami akan mempertimbangkan opsi untuk mengatur data dan model R (Reflection) untuk representasi optimal dari sumber data sebagai objek analisis dengan konsumsi memori minimal, kemampuan untuk mengimplementasikan algoritma pencarian untuk elemen dengan kompleksitas O (1), dan dapat menyimpan ke disk dalam bentuk serial. semua objek, serta bagian unit pengujian alat.

Source: https://habr.com/ru/post/undefined/


All Articles