Unit test di un compilatore

Question

Qual è l'approccio migliore per il test dell'unità di un'unità complessa come un compilatore?

Ho scritto un paio di compilatori e interpreti nel corso degli anni, e lo faccio trovare questo tipo di codice molto difficile da testare in un buon modo.

Se prendiamo qualcosa come la generazione di Abstract Syntax Tree. come metteresti alla prova questo usando TDD?

I piccoli costrutti possono essere facili da testare. ad es. qualcosa del tipo:

string code = @"public class Foo {}"; 
AST ast = compiler.Parse(code); 

Dal momento che non genererà un sacco di nodi.

Ma se in realtà voglio provare che il compilatore in grado di generare un AST per qualcosa di simile a un metodo:

[TestMethod] 
public void Can_parse_integer_instance_method_in_class() 
{ 
    string code = @"public class Foo { public int method(){ return 0;}}"; 
    AST ast = compiler.Parse(code); 

Cosa vorresti valere su? Definire manualmente un AST che rappresenta il codice dato e fare un'affermazione secondo cui l'AST generato è conforme all'AST definito manualmente sembra orribilmente combiante e potrebbe persino essere soggetto a errori.

Quindi quali sono le migliori tattiche per TDD'ing scenari complessi come questo?

Answer 1

Prima di tutto l'analisi è in genere una parte banale del progetto del compilatore. Dalla mia esperienza non ci vuole mai più del 10% delle volte (a meno che non stiamo parlando di C++, ma non ci porrei domande qui se lo stavate progettando) quindi preferireste non investire molto del vostro tempo nei test del parser.

Eppure, TDD (o comunque si voglia chiamare) ha la sua parte nello sviluppo del mezzo-end in cui spesso si desidera verificare che per esempio le ottimizzazioni appena aggiunte hanno effettivamente comportato la trasformazione del codice prevista. Dalla mia esperienza, i test di questo tipo vengono solitamente implementati fornendo al compilatore programmi di test appositamente predisposti e l'assemblaggio di output di grepping per i pattern previsti (questo ciclo è stato srotolato quattro volte? Abbiamo evitato di scrivere in memoria questa funzione? Ecc.). L'assemblaggio di grepping non è buono come analizzare la rappresentazione strutturata (S-exprs o XML) ma è economico e funziona bene nella maggior parte dei casi. Tuttavia è incredibilmente difficile da supportare man mano che il tuo compilatore cresce.

Answer 2

In primo luogo, se si prova un compilatore, non è possibile ottenere abbastanza prove! Gli utenti fanno davvero affidamento sull'output generato dal compilatore come se fosse uno standard sempre d'oro, quindi sii davvero consapevole della qualità. Quindi se puoi, prova con ogni prova che riesci a trovare!

secondo luogo, utilizzare tutti i metodi di prova disponibili, tuttavia usarli all'occorrenza. In effetti, potresti essere in grado di provare matematicamente che una certa trasformazione è corretta. Se sei in grado di farlo, dovresti.

Ma ogni compilatore che ho visto alcuni interni di euristiche e coinvolge un sacco di ottimizzazione, il codice artigianale nelle sue parti interne; in tal modo i metodi di dimostrazione assistita di solito non sono più applicabili. Qui, i test vengono a posto, e intendo molto!

Quando si raccolgono le prove, perche casi diversi:

1. positivo standard-Conformità: il vostro frontend dovrebbe accettare certi modelli di codice e il compilatore deve produrre un programma di corretta esecuzione della stessa.I test in questa categoria richiedono un compilatore o un generatore di riferimento dorato che produca l'output corretto del programma di test; o coinvolge programmi scritti a mano che includono un controllo contro valori forniti dal ragionamento umano.
2. Test negativi: ogni compilatore deve rifiutare il codice errato, come errori di sintassi, tipo mancate corrispondenze e così via. Deve produrre determinati tipi di messaggi di errore e di avviso. Non conosco alcun metodo per generare automaticamente tali test. Quindi anche questi devono essere scritti da umani.
3. Test di trasformazione: ogni volta che si ottiene un'ottimizzazione dell'ottimizzazione all'interno del compilatore (middle-end), probabilmente si ha a mente un codice di esempio che dimostra l'ottimizzazione. Essere consapevoli delle trasformazioni prima e dopo tale modulo, potrebbero richiedere opzioni speciali per il compilatore o un compilatore bare-bone con solo quel modulo collegato. Prova anche un ragionevole insieme di combinazioni di moduli circostanti. Di solito eseguivo i test di regressione sulla rappresentazione intermedia prima e dopo la trasformazione specifica, definendo un riferimento mediante ragionamento intensivo con i colleghi. Prova a scrivere il codice su entrambi i lati della trasformazione, ad esempio frammenti di codice che desideri trasformare e leggermente diversi che non devono essere.

Ora, questo sembra un sacco di lavoro! Sì, ma c'è un aiuto: ci sono diverse test-suite commerciali per i compilatori (C) nel mondo ed esperti che potrebbero aiutarti ad applicarle. Ecco un piccolo elenco di quelli noti a me:

• ACE: SuperTest Compiler Test and Validation Suite
• perenne C Compiler di convalida Suite
• Bugseng: ECLAIR
• Test nel GCC e LLVM ambiente
• è il nome! O google "Compiler Test Suite"