Dalam hari-hari Januari yang indah ini, kita semua, tentu saja, prihatin dengan masalah meminimalkan kode sumber sambil mempertahankan yang lain. Maksud saya, tidak peduli?!? Sia-sia ... Di sini kompiler jatuh, dan programnya raksasa - entah bagaimana merepotkan pengembang untuk mengirim hal seperti itu. Dan kemudian kesenangan dimulai: bagaimana jika Anda membuangnya? Oh, tidak jatuh - oke, kita pergi, tetapi bagaimana jika itu? - Masih crash, dan ini, dan ini, dan itu ... Oh, saya mulai kompilator pada sumber-sumber lama.
Pada saat yang sama, mengotomatiskan pencarian bug adalah sesuatu yang vital: git bisect, llvm-bugpoint, creduce, ... Dalam artikel ini saya akan menjelaskan cara lain untuk memecahkan masalah penyederhanaan test case, kurang lebih universal sehubungan dengan bahasa pemrograman, dan menunjukkan beberapa contoh penggunaan.
Universal, katakanlah ... Mungkin, tentu saja, ini telah diterapkan sepuluh kali, tetapi apakah ini akan menghentikan seorang pengendara sepeda berpengalaman. Dan ketika di tangan mikroskop, semua masalah tampak seperti paku. Dalam peran mikroskop - PMD .
Secara umum, ada bahasa seperti itu untuk model penulisan yang dijelaskan oleh persamaan diferensial - Modelica. Ini cukup canggih, ada implementasi terbuka yang sangat keren dan secara umum. Tetapi ada masalah kecil: kadang-kadang kesalahan kompiler internal terjadi di kompiler. Dalam artikel sebelumnya, saya sudah menunjukkan cara menambahkan dukungan Modela ke penganalisa statis PMD (omong-omong, beberapa kesalahan saya muncul selama proses peninjauan) di samping sepuluh modul bahasa yang ada. Jadi sekarang saya memutuskan - apa gunanya menghilang - dan mengirim alat proof-of-concept Source Code Minimizer, menggunakan kembali modul bahasa PMD yang ada. Sayangnya, saya dikirim, meskipun tidak jauh, ke repositori tetangga: menter mengatakan bahwa dia masih belum memutuskan untuk mendukung ini sampai akhir abad ini, dan itu hilang dalam basis kode umum, jadi saya segera menemukan undangan untuk berkolaborasi di inbox saya Baru dibuat pmd / pmd-scm .
Pertama, apa pernyataan masalahnya? Diperlukan untuk mengurangi ukuran kode sumber, menjaga sebagian propertinya. Lebih spesifik, saya mau
- kode yang dihasilkan dapat diprediksi
- tidak harus seminimal mungkin , "penyelesaian file" diizinkan, tetapi seharusnya tidak berubah menjadi siksaan
- kebingungan otomatis tidak dipertimbangkan
- program yang diminimalkan dapat dibagi menjadi beberapa file dengan kode sumber
- misalnya, di Jawa, setiap kelas
public harus dalam file terpisah dengan nama yang benar, dll. - Saya ingin setiap file tetap terlihat pada akhirnya
- dalam proses transformasi, invarian yang ditunjukkan harus dipertahankan
Perangkat internal
Pada bagian ini, saya akan secara kasar menggambarkan implementasinya. Untuk mulai dengan, saya perhatikan lagi bahwa ide ini, secara halus, bukanlah hal baru. Dan jika saya mengutip git bisect hanya sebagai contoh dari "mekanisme debug otomatis," maka saya menemukan kredibilitas atau sesuatu yang serupa untuk beberapa waktu (meskipun saya tidak menggunakannya). Tetapi saya harus menggunakan llvm-bugpoint - sangat mengesankan: Anda duduk, men-debug LLVM Pass Anda, dan - infeksi semacam itu - lumpuh pada beberapa sistem file. Jadi, Anda dapat mengkompilasi file ini dalam bitcode LLVM, jalankan opt pada file .bc dengan plugin Anda dan pastikan itu crash. Dan kemudian, secara kasar, saya baru saja mengganti opt dengan llvm-bugpoint , dan setelah satu menit saya mendapatkan "kerangka" yang kuat dari salah satu fungsi, yang terdiri dari awan balok dasar dan transisi di antara mereka; semuanya kecuali cabang-cabang berhasil dibuang. Ngomong-ngomong, seperti dalam pernyataan masalah saya, setelah selusin menit penyederhanaan manual, semuanya berujung pada fakta bahwa saya salah memproses jenis cabang, dan yang lainnya hanya pemandangan. Secara umum, idenya bukanlah hal baru.
Dan sekarang untuk implementasinya. Karena itu seharusnya menjadi alat yang kurang lebih universal, saya ingin membuat semacam kerangka kerja di mana kita bisa menjejalkan implementasi yang dioptimalkan untuk berbagai bahasa. Akibatnya, dua konsep yang agak ortogonal menonjol:
- invarian yang didukung
- strategi minimisasi
Invarian
Salah satu opsi untuk properti yang mungkin ingin Anda simpan, saya telah jelaskan: "kompiler mencetak frasa ke konsol" ("Kesalahan kompiler internal", misalnya). Juga, ide dapat diperoleh dari berbagai fuzzer: AFL , Killerbeez dan lainnya:
- proses berakhir dengan beberapa kode kembali (khususnya, "crash on signal" di Linux)
- prosesnya memakan waktu lebih dari T milidetik. Di sini, sayangnya, ketidakstabilan dapat terjadi karena beban mengambang sistem. Untuk lebih akurat, Anda dapat menggunakan waktu CPU, meskipun, idealnya, penghitung kinerja berguna
- kompiler dapat (tidak) menghasilkan beberapa file output
- ...
Saya sudah menerapkan beberapa dari mereka (kode pengembalian, garis tercetak), beberapa tidak, beberapa mungkin khusus untuk masing-masing bahasa. Secara umum, ini adalah bagian dari tugas yang cukup otonom, seringkali sepenuhnya independen dari bahasa tertentu.
Strategi minimalisasi
Sekilas, semuanya di sini murni tergantung pada bahasa. Di suatu tempat Anda perlu membuang variabel bersama dengan kasus penggunaan, di suatu tempat - untuk mempertahankan jumlah persamaan dan tidak diketahui yang sama. Yang lebih penting adalah mengabstraksi bagian kode ini. Tapi sesuatu yang mendasar dapat dibuat umum untuk semua orang: misalnya, dengan menggerakkan pergelangan tangan, mesin aturan XPath berubah ... ternyata ... ... oh, untuk XPath versi 1.0 tidak. Maaf, sedikit masalah teknis - menjadi alat universal untuk memangkas pohon sintaks untuk musim dingin . Secara umum, strategi minimalisasi API cukup sederhana: pada umumnya, fungsi tersebut memiliki fungsi langkah (diberikan daftar simpul akar dari pohon sintaks), yang dapat menanyakan "tetapi mencoba membuang cabang-cabang ini" melalui antarmuka operasi. Jika invarian dilanggar, fungsi mengembalikan kontrol, jika tidak, ia memutar stack dengan melemparkan pengecualian khusus, dan versi yang dihasilkan diambil sebagai perkiraan berikutnya. Suatu proses dianggap selesai jika fungsi langkah mengembalikan kontrol tidak melalui pengecualian. Anda mungkin mengatakan bahwa ini sangat tidak efektif - mungkin begitu, NYAMAN NYAMAN !! 111 , tapi apa masalahnya, jika seharusnya memulai proses kompiler eksternal secara teratur ratusan kali dalam satu siklus.
Ini menimbulkan pertanyaan: bagaimana cara mendapatkan sumber kembali dari AST yang menipis? Tentu saja, Anda dapat mencoba menulis kode khusus untuk setiap bahasa yang menghasilkan file teks. Tapi, seperti yang Anda tahu, seorang programmer harus malas. Jadi itu tidak akan berhasil - sudah jelas bukan dari seri "mengambil implementasi yang ada dan pergi." Untungnya, di simpul pohon terdapat informasi tentang awal dan akhir baris dan kolom untuk simpul ini - itu artinya, jika modul bahasa menunjukkan informasi ini dengan benar, Anda dapat mengambil teks sumber dan dengan hati-hati memotongnya (karenanya, omong-omong, dan beberapa kesulitan dengan kebingungan: tidak cukup untuk membuang sesuatu, tetapi Anda harus menggantinya: pengidentifikasi, misalnya). Ngomong-ngomong, dalam basis kode PMD, kami bahkan menemukan kelas untuk mengedit file menggunakan operasi pemotongan teks yang tidak memotong (juga menambahkan, tetapi ini tidak begitu menarik untuk tugas khusus ini).
Teori: Ringkasan
Saat ini saya telah menerapkan dua strategi. Salah satunya adalah pemangkasan XPath, yang dalam arti tertentu, merupakan kasus yang merosot, karena ia secara paksa menulis hasilnya, bahkan jika itu bukan lagi sumber yang benar secara sintaksis. Yang kedua sudah "jujur" berulang dan interaktif (dalam arti bahwa itu benar-benar berinteraksi dengan kompiler dan memeriksa yang lain): ia hanya mencoba untuk melemparkan cabang satu per satu dalam satu lingkaran. Ini sedikit tentang itu:
- pada prinsipnya, memeriksa invarian untuk sumber, yang tidak diuraikan, tidak masuk akal untuk strategi "jujur": bahkan jika kompiler bertahan ini, minimizer harus memulai ulang sumber. Oleh karena itu, masuk akal untuk membuang file "rusak" terlebih dahulu: parsing dalam proses Anda lebih cepat daripada menjalankan seluruh kompiler
- dalam kasus umum, mungkin akan lebih mudah untuk menggunakan coroutine di sini (baik, atau mengubah aliran kontrol dalam ke luar), tetapi karena ini jauh dari bagian pekerjaan yang paling sulit secara komputasi, pada setiap langkah dalam fungsi langkah saya hanya berjalan di sekitar pohon, menghitung jarak. puncak. Saya hanya ingat konter. Jadi, pada awalnya saya berpikir bahwa bagian atas lebih besar, bagian atas lebih sedikit - bedanya apa, heuristik! Ternyata kesalahan per unit dapat mengubah tingkat "konvergensi" di kali. Intinya, ini logis: membuang seluruh fungsi dari kelas agar sering menjadi strategi yang efektif. Tetapi untuk melompati sedikit, dan setiap kali masuk ke dalam fungsi, dalam kebanyakan kasus tidak ada hubungannya dengan masalah, sepertinya ide yang begitu-begitu.
- Omong-omong tentang coroutine dan penyebaran aliran kontrol: akan ada beberapa masalah dengan ini, karena setelah me-reboot teks yang diubah AST mungkin tidak berubah dengan cara yang sangat jelas (yaitu, tidak hanya cabang-cabang ini akan dibuang kembali, tetapi di suatu tempat node kosong akan menghilang, di suatu tempat umumnya parsing akan menuju ke arah lain). Belum lagi bahwa node AST baru tidak akan identik dengan merujuk ke yang lama, dan pencocokan logis dengan yang
equals - juga terlihat seperti tugas yang sulit - pada prinsipnya, Anda dapat menggunakan kemampuan PMD ke berbagai tingkat: Anda dapat menggunakan tipe terhitung, dependensi penggunaan definisi, dll. dan melakukan sesuatu yang sangat cerdas (tetapi Anda perlu mempertimbangkan API universal). Di sisi lain, untuk strategi yang dijelaskan, cukup untuk mendapatkan pohon parse. Dan di sini Anda bahkan dapat mengaitkan beberapa Kaitai Struct dan mencoba untuk mendorong afl-tmin untuk meminimalkan file biner :)
Berlatih
Untuk memulai, mari buat minimizer:
git clone https://github.com/pmd/pmd-scm.git cd pmd-scm ./mvnw clean verify unzip pmd-scm-dist/target/pmd-scm-bin-1.0.0-SNAPSHOT.zip
Sekarang Anda membutuhkan beberapa sumber. Mari kita ambil GreedyStrategy.java misalnya.
Dengan menggunakan Rule Designer, cari tahu seperti apa AST pada Java, dan jalankan
$ ./bin/run.sh scm --language java \ --input-file ../pmd-scm/src/main/java/net/sourceforge/pmd/scm/strategies/GreedyStrategy.java \ --output-file GreedyStrategy-min.java \ --strategy xpath \ --xpath-expression '//BlockStatement[count(../BlockStatement) > 1]' Original file(s): 6155 bytes, 1099 nodes. After initial white-space cleanup: size 4548 bytes (73%), 1099 nodes (100%) After pass #1: size 1984 bytes (32%), 1099 nodes (100%) After final white-space cleanup: size 1984 bytes (32%), 325 nodes (29%) After blank line clean up: size 1767 bytes (28%), 325 nodes (29%)
package net.sourceforge.pmd.scm.strategies; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; import net.sourceforge.pmd.lang.ast.Node; public class GreedyStrategy extends AbstractMinimizationStrategy { public static class Configuration extends AbstractConfiguration { @Override public MinimizationStrategy createStrategy() { return new GreedyStrategy(this); } } public static final MinimizationStrategyConfigurationFactory FACTORY = new AbstractFactory("greedy") { @Override public MinimizationStrategyConfiguration createConfiguration() { return new Configuration(); } }; private GreedyStrategy(Configuration configuration) { super(configuration); } private final Map<Node, HashSet<Node>> directlyDependingNodes = new HashMap<>(); private final Map<Node, Set<Node>> transitivelyDependingNodes = new HashMap<>(); private void fetchDirectDependentsFromSubtree(Node node) {
Artinya, kami mengosongkan semua fungsi yang secara langsung berisi lebih dari satu pernyataan . Namun, menghapus komentar, baris kosong, dll. Saya belum menentukannya - lagipula, apakah ini (sejauh ini?) Utamanya merupakan alat untuk debugging compiler , daripada membuat deskripsi antarmuka yang indah.
Mari kita lihat sesuatu yang lebih menarik sekarang: cobalah untuk meminimalkan dua file dengan umpan balik dari kompiler secara bersamaan:
orig / TestResource.java:
class TestResource { int func() { System.err.println("Hello World!"); return 123; } void unused() {
orig / Main.java:
class Main { public static void main(String[] args) { String str = new TestResource().func(); return 123; } }
Seperti yang Anda lihat, mereka tidak mengkompilasi:
$ javac orig/TestResource.java orig/Main.java orig/Main.java:3: error: incompatible types: int cannot be converted to String String str = new TestResource().func(); ^ orig/Main.java:5: error: incompatible types: unexpected return value return 123; ^ 2 errors
Mari kita bayangkan ada sesuatu yang salah dengan kesalahan pertama, dan cobalah membuat contoh minimal yang menghasilkan
error: incompatible types: int cannot be converted to String
Untuk melakukan ini, jalankan
$ bin/run.sh scm --language java \ --input-file orig/TestResource.java orig/Main.java \ --output-file TestResource.java Main.java \ --invariant message \ --printed-message "error: incompatible types: int cannot be converted to String"\ --command-line "javac TestResource.java Main.java" \ --strategy greedy Original file(s): 290 bytes, 77 nodes. After initial white-space cleanup: size 258 bytes (88%), 77 nodes (100%) After pass #1: size 255 bytes (87%), 64 nodes (83%) After pass #2: size 244 bytes (84%), 57 nodes (74%) After pass #3: size 205 bytes (70%), 51 nodes (66%) After pass #4: size 192 bytes (66%), 46 nodes (59%) After pass #5: size 181 bytes (62%), 39 nodes (50%) After pass #6: size 179 bytes (61%), 39 nodes (50%) After final white-space cleanup: size 149 bytes (51%), 39 nodes (50%) After blank line clean up: size 147 bytes (50%), 39 nodes (50%)
Hasilnya, kita dapatkan
TestResource.java:
class TestResource { int func() { } }
Main.java:
class Main { public static void main() { String str = new TestResource().func(); } }
$ javac TestResource.java Main.java TestResource.java:3: error: missing return statement } ^ Main.java:3: error: incompatible types: int cannot be converted to String String str = new TestResource().func(); ^ 2 errors
Semuanya seperti yang diperintahkan!
Ringkasan
Sejauh ini, proyek ini pada tahap yang cukup awal, tetapi sudah ada sesuatu untuk ditunjukkan. Di masa depan, ada ide untuk membuat API untuk agnostik yang mengindikasikan ketergantungan antara AST node, untuk memungkinkannya menyediakan strategi khusus bahasa. Akan lebih baik jika membuat strategi universal yang menjalankan skrip Groovy / Kotlin / sesuatu yang lain - lagipula, orang yang menggunakan Java mungkin tidak pernah melihatnya, tetapi mereka tahu benar, misalnya, Modelika, dan ada di kepala mereka cara canggih untuk memeras sumbernya.