Bagaimana Anda menguji kode unit menggunakan struktur grafik?

Saya menulis kode (rekursif) yang menavigasi grafik dependensi mencari siklus atau kontradiksi dalam dependensi. Namun, saya tidak yakin bagaimana cara mendekati unit testing ini. Masalahnya adalah bahwa salah satu perhatian utama kami adalah apakah kode akan menangani semua struktur grafik yang menarik yang dapat muncul dan memastikan bahwa semua node akan ditangani dengan tepat.

Meskipun biasanya 100% cakupan baris atau cabang sudah cukup untuk yakin bahwa beberapa kode berfungsi, rasanya bahkan dengan cakupan 100% Anda masih akan ragu.

Jadi, bagaimana cara memilih struktur grafik untuk kasus uji untuk memiliki keyakinan bahwa kode mereka dapat menangani semua permutasi yang mungkin Anda akan temukan dalam data dunia nyata.

PS- Jika itu penting, semua tepi dalam grafik saya diberi label "harus memiliki" xor "tidak dapat memiliki" dan tidak ada siklus sepele, dan hanya ada satu sisi antara dua node.

PPS- Pernyataan masalah tambahan ini pada awalnya diposting oleh penulis pertanyaan dalam komentar di bawah:

For all vertices N in forest F, for all vertices M, in F, such that if there are any walks between N and M they all must either use only edges labelled 'conflict' or 'requires'.

Kami terus berpikir bahwa kami memiliki semua yang rumit yang dibahas dan kemudian kami menyadari bahwa struktur tertentu menyebabkan masalah yang tidak kami pertimbangkan sebelumnya. Menguji setiap trik yang dapat kita pikirkan adalah apa yang kita lakukan.

Itu terdengar seperti awal yang baik. Saya kira Anda sudah mencoba menerapkan beberapa teknik klasik seperti analisis nilai batas atau partisi kesetaraan , seperti yang telah Anda sebutkan pengujian berbasis cakupan. Setelah Anda menginvestasikan banyak waktu dalam membangun kasus uji yang baik, Anda akan sampai pada titik di mana Anda, tim Anda, dan juga penguji Anda (jika Anda memilikinya) kehabisan ide. Dan itulah titik di mana Anda harus meninggalkan jalur pengujian unit dan mulai menguji sebanyak mungkin data dunia nyata.

Seharusnya jelas bahwa Anda harus mencoba untuk memilih beragam grafik dari data produksi Anda. Mungkin Anda harus menulis beberapa alat atau program tambahan hanya untuk bagian proses itu. Bagian yang sulit di sini mungkin untuk memverifikasi kebenaran dari output program Anda, ketika Anda memasukkan sepuluh ribu grafik dunia nyata ke dalam program Anda, bagaimana Anda akan tahu jika program Anda selalu menghasilkan output yang benar? Jelas Anda tidak dapat memeriksa selain secara manual. Jadi, jika Anda beruntung, Anda mungkin bisa melakukan implementasi kedua, pemeriksaan dependensi Anda yang sangat sederhana, yang mungkin tidak memenuhi harapan kinerja Anda, tetapi lebih mudah untuk diverifikasi daripada algoritma asli Anda. Anda juga harus mencoba untuk mengintegrasikan banyak pemeriksaan masuk akal langsung ke program Anda (misalnya,

Akhirnya, pelajari untuk menerima bahwa setiap tes hanya dapat membuktikan keberadaan bug, tetapi tidak adanya bug.

1. Pembuatan uji acak

Tulis sebuah algoritma yang menghasilkan grafik, buat grafik beberapa ratus (atau lebih) grafik acak dan lemparkan masing-masing ke algoritma Anda.

Simpan benih acak dari grafik yang menyebabkan kegagalan yang menarik dan tambahkan itu sebagai unit test.

2. Hard-code bagian sulit

Beberapa struktur grafik yang Anda tahu rumit, dapat Anda kode langsung, atau menulis beberapa kode yang menggabungkannya dan mendorongnya ke algoritme Anda.

3. Hasilkan daftar lengkap

Tetapi, jika Anda ingin memastikan "kode tersebut dapat menangani semua permutasi yang mungkin Anda temukan dalam data dunia nyata.", Anda perlu membuat data ini bukan dari seed acak, tetapi dengan berjalan melalui semua permutasi. (Ini dilakukan saat menguji sistem sinyal kereta bawah tanah, dan memberi Anda banyak sekali kasus yang perlu waktu lama untuk diuji. Untuk kereta bawah tanah metro, sistem dibatasi, jadi ada batas atas jumlah permutasi. Tidak yakin bagaimana kasus Anda berlaku)

Tidak ada pengujian apa pun yang akan mampu mencukupi dalam kasus ini, bahkan tidak banyak data dunia nyata atau fuzzing. Cakupan kode 100%, atau bahkan cakupan 100% tidak cukup untuk menguji fungsi rekursif.

Entah fungsi rekursif berdiri untuk bukti formal (seharusnya tidak terlalu sulit dalam kasus ini), atau tidak. Jika kode terlalu terkait dengan kode khusus aplikasi untuk mengesampingkan efek samping, di situlah untuk memulai.

Algoritme itu sendiri terdengar seperti algoritma flooding sederhana, mirip dengan pencarian pertama yang luas dan sederhana, dengan penambahan daftar hitam yang tidak boleh bersinggungan dengan daftar node yang dikunjungi, dijalankan dari semua node.

foreach nodes as node
    foreach nodes as tmp
        tmp.status = unmarked

    tovisit = []
    tovisit.push(node)
    node.status = required

    while |tovisit| > 0 do
        next = tovisit.pop()
        foreach next.requires as requirement
            if requirement.status = unmarked
                tovisit.push(requirement)
                requirement.status = required
            else if requirement.status = blacklisted
                return false
        foreach next.collides as collision
            if collision.status = unmarked
                requirement.status = blacklisted
            else if requirement.status = required
                return false
return true

Algoritma iteratif ini memenuhi syarat bahwa tidak ada ketergantungan yang diperlukan dan masuk daftar hitam pada saat yang sama, untuk grafik struktur arbitrer, dimulai dari artefak arbitrer dimana artefak awal selalu diperlukan.

Meskipun mungkin atau mungkin tidak secepat implementasi Anda sendiri, dapat dibuktikan bahwa itu berakhir untuk semua kasus (seperti untuk setiap iterasi dari loop luar setiap elemen hanya dapat didorong sekali ke tovisitantrian), itu membanjiri seluruh yang dapat dijangkau grafik (bukti induktif), dan mendeteksi semua kasus di mana artifak diperlukan untuk diminta dan masuk daftar hitam secara bersamaan, mulai dari setiap node.

Jika Anda dapat menunjukkan bahwa implementasi Anda sendiri memiliki karakteristik yang sama, Anda dapat membuktikan kebenaran tanpa menghasilkan pengujian unit. Hanya metode dasar untuk mendorong dan muncul dari antrian, menghitung panjang antrian, iterasi properti dan sama-sama perlu diuji dan terbukti bebas dari efek samping.

EDIT: Apa yang tidak dibuktikan oleh algoritma ini, apakah grafik Anda bebas dari siklus. Grafik asiklik terarah adalah topik yang diteliti dengan baik, jadi mencari algoritma yang sudah jadi untuk membuktikan properti ini juga harus mudah.

Seperti yang Anda lihat, sama sekali tidak perlu menemukan kembali roda.

Anda menggunakan frasa seperti "semua struktur grafik yang menarik" dan "ditangani dengan tepat". Kecuali jika Anda memiliki cara untuk menguji kode Anda terhadap semua struktur itu dan menentukan apakah kode tersebut menangani grafik dengan tepat, Anda hanya dapat menggunakan alat seperti analisis cakupan pengujian.

Saya sarankan Anda mulai dengan mencari dan menguji dengan sejumlah struktur grafik yang menarik dan menentukan penanganan yang sesuai dan melihat bahwa kode melakukan itu. Kemudian, Anda dapat mulai mengganggu grafik itu menjadi a) grafik rusak yang melanggar aturan atau b) grafik tidak terlalu menarik yang memiliki masalah; lihat apakah kode Anda gagal menanganinya.

Anda dapat mencoba melakukan semacam topologi dan melihat apakah itu berhasil. Jika tidak, maka Anda memiliki setidaknya satu siklus.

Ketika datang ke semacam ini sulit untuk menguji algoritma, saya akan pergi untuk TDD, di mana Anda membangun algoritma berdasarkan tes,

Singkatnya TDD,

• tulis ujiannya
• lihat itu gagal
• modifikasi kodenya
• pastikan semua tes lulus
• refactor

dan ulangi siklus,

Dalam situasi khusus ini,

1. Tes pertama adalah, grafik simpul tunggal di mana algoritma seharusnya tidak mengembalikan siklus apa pun
2. Yang kedua adalah tiga simpul grafik tanpa siklus di mana algoritma seharusnya tidak mengembalikan siklus apa pun
3. Berikutnya adalah menggunakan tiga simpul grafik dengan siklus di mana algoritma seharusnya tidak mengembalikan siklus apa pun
4. Sekarang Anda bisa mengujinya terhadap siklus yang sedikit lebih kompleks tergantung pada kemungkinan

Salah satu aspek penting dalam metode ini adalah Anda harus selalu menambahkan tes untuk langkah yang mungkin (di mana Anda membagi skenario yang mungkin menjadi tes sederhana), dan ketika Anda membahas semua skenario yang mungkin biasanya algoritma akan berevolusi secara otomatis.

Akhirnya Anda perlu menambahkan satu atau lebih tes Integrasi yang rumit untuk melihat apakah ada masalah yang tidak terduga (seperti kesalahan stack-overflow / kesalahan kinerja ketika grafik Anda sangat besar dan ketika Anda menggunakan rekursi)

Pemahaman saya tentang masalah, seperti yang dinyatakan sebelumnya dan kemudian diperbarui oleh komentar di bawah jawaban Macke, meliputi yang berikut: 1) kedua jenis tepi (dependensi dan konflik) diarahkan; 2) jika dua node dihubungkan oleh satu sisi, mereka tidak boleh dihubungkan oleh yang lain, bahkan jika itu dari tipe yang lain atau terbalik; 3) jika jalur antara dua node dapat dibangun dengan mencampurkan tepi dari tipe yang berbeda, maka itu adalah kesalahan, bukan keadaan yang diabaikan; 4) Jika ada jalur antara dua node menggunakan tepi dari satu jenis, maka mungkin tidak ada jalur lain di antara mereka menggunakan tepi dari jenis lainnya; 5) siklus jenis tepi tunggal atau jenis tepi campuran tidak diizinkan (dari tebakan di aplikasi, saya tidak yakin bahwa siklus konflik saja merupakan kesalahan, tetapi kondisi ini dapat dihapus, jika tidak.)

Lebih jauh, saya akan mengasumsikan struktur data yang digunakan tidak mencegah pelanggaran terhadap persyaratan yang dinyatakan (misalnya, grafik yang melanggar kondisi 2 tidak dapat diekspresikan dalam peta dari pasangan-simpul ke (tipe, arah) jika pasangan-pasangan selalu memiliki simpul bernomor paling rendah terlebih dahulu.) Jika kesalahan tertentu tidak dapat diungkapkan, ini mengurangi jumlah kasus yang harus dipertimbangkan.

Sebenarnya ada tiga grafik yang dapat dipertimbangkan di sini: dua secara eksklusif satu jenis tepi, dan grafik campuran dibentuk oleh penyatuan satu dari masing-masing dua jenis. Anda dapat menggunakan ini untuk secara sistematis menghasilkan semua grafik hingga sejumlah node. Pertama-tama buat semua grafik yang mungkin dari simpul N yang tidak memiliki lebih dari satu tepi antara dua pasang simpul yang dipesan (pasangan yang dipesan karena ini adalah grafik yang diarahkan.) Sekarang ambil semua pasangan yang memungkinkan dari grafik ini, yang satu mewakili dependensi dan yang lainnya mewakili konflik, dan membentuk persatuan masing-masing pasangan.

Jika struktur data Anda tidak dapat mengungkapkan pelanggaran kondisi 2, Anda dapat secara signifikan mengurangi kasus yang harus dipertimbangkan dengan hanya membuat semua grafik konflik yang sesuai dengan ruang grafik ketergantungan, atau sebaliknya. Jika tidak, Anda dapat mendeteksi pelanggaran kondisi 2 saat membentuk serikat pekerja.

Pada lintasan pertama dari grafik gabungan dari simpul pertama, Anda bisa membangun set semua lintasan ke setiap simpul yang dapat dijangkau, dan saat melakukannya, Anda bisa memeriksa pelanggaran semua kondisi (untuk deteksi siklus, Anda bisa gunakan algoritma Tarjan .)

Anda hanya perlu mempertimbangkan jalur dari simpul pertama, bahkan jika grafik terputus, karena jalur dari simpul lain akan muncul sebagai jalur dari simpul pertama dalam beberapa kasus lain.

Jika jalur campuran dapat diabaikan, alih-alih menjadi kesalahan (kondisi 3), cukup untuk mempertimbangkan grafik dependensi dan konflik secara independen, dan memeriksa bahwa jika sebuah node dapat dijangkau di satu, itu tidak di yang lain.

Jika Anda ingat jalur yang ditemukan dalam memeriksa grafik N-1 node, Anda dapat menggunakannya sebagai titik awal untuk menghasilkan dan mengevaluasi grafik N node.

Ini tidak menghasilkan banyak sisi dengan tipe yang sama antar node, tetapi bisa diperluas untuk melakukannya. Ini akan sangat meningkatkan jumlah kasus, jadi akan lebih baik jika kode yang diuji membuat ini tidak mungkin untuk mewakili, atau gagal itu, menyaring semua kasus tersebut sebelumnya.

Kunci untuk menulis oracle seperti ini adalah menjaganya sesederhana mungkin, meskipun itu berarti tidak efisien, sehingga Anda dapat membangun kepercayaan di dalamnya (idealnya melalui argumen untuk kebenarannya, didukung oleh pengujian.)

Setelah Anda memiliki sarana untuk menghasilkan kasus uji, dan Anda percaya pada oracle yang telah Anda buat untuk secara akurat memisahkan yang baik dari yang buruk, Anda mungkin menggunakan ini untuk mendorong pengujian otomatis kode target. Jika itu tidak layak, pilihan terbaik Anda berikutnya adalah menyisir hasil untuk kasus yang berbeda. Oracle dapat mengklasifikasikan kesalahan yang ditemukannya, dan memberi Anda beberapa informasi tentang kasus yang diterima, seperti jumlah dan panjang jalur dari setiap jenis, dan apakah ada node yang ada di awal kedua jenis jalur, dan ini dapat membantu Anda mencari kasus yang belum Anda lihat sebelumnya.