C'è qualche motivo per scrivere un tester casuale per il codice che si occupa di strutture di dati induttivi?

Question

C'è qualche motivo per scrivere un tester casuale per il codice che si occupa di strutture di dati induttivi?

#1 da (1 voti)
#2 da (1 voti)
#3 da (0 voti)

2

Diciamo che stiamo scrivendo un semplice parser JSON e abbiamo coperto completamente il codice con i test unitari:

può analizzare primitive "0", "123", "-456", '""', '"asd"', true, false
può analizzare le matrici "[]", "[1, 2, 3]"
può analizzare le matrici annidate "[[]]"
può analizzare gli oggetti "{}", '{ "a": 1, "b": 2 }'
può analizzare oggetti nidificati '{ "a": {} }'

Ogni possibile JSON può essere o una primitiva o un array / oggetto che contiene altre primitive / matrici / oggetti - questo è ciò che intendo per struttura dati induttiva (è 'ricorsivo' un termine migliore?). Mi sembra che qualsiasi analisi JSON possa essere ridotta a questi pochi casi e se il parser supera questi test, allora è completamente corretto (a meno che non sia stato esplicitamente cablato per interrompere quando si tenta di analizzare numeri speciali).

C'è ancora qualche punto nella creazione di un tester casuale che generi JSON con stringhe casuali nella speranza che uno di loro possa interrompere questo parser? Questo tester casuale troverà qualcosa di interessante?

P.S. Ho scelto JSON solo come esempio di una struttura dati induttiva; Non mi interessa scrivere un parser JSON.

testing recursion

posta adrianton3 23.05.2014 - 07:38

fonte

3 risposte

1

La domanda a cui intendo rispondere è una sul valore dei test casuali in generale, e delle strutture dati induttive / ricorsive in particolare, non su JSON.

I test casuali hanno valore in diverse impostazioni. Lo scopo principale del test casuale è quello di affrontare i casi in cui lo spazio del test è immensamente grande in modo che non possa essere testato in modo esaustivo. Posso pensare a 3 di questi spazi.

sopravvivenza. Il sistema sottoposto a test sopravvive nutrendo grandi quantità di dati di input bizzarri? Sì, dovresti testarlo.
Limiti. Il SUT si comporta correttamente quando l'input dell'alimentatore supera i suoi limiti, come lunghezza del token, profondità di ricorsione, backtracking o qualsiasi altra cosa, da solo o in combinazione? Puoi fare la maggior parte con test pianificati, ma potrebbe essere utile un po 'di casual.
Verificare i difetti. C'è sempre il rischio che i tuoi altri test abbiano perso qualcosa di interessante, e che l'alimentazione di una quantità sufficiente di dati intorno ai margini (che saprai dall'ispezione della scatola bianca) la trovi. Vale la pena considerare.

Il problema con i test casuali è (a) come esplorare in modo adeguato uno spazio di input quasi infinito (b) come prevedere il risultato del test per ogni caso di input.

Se hai delle soluzioni per questo, allora vale la pena prendere in considerazione le prove casuali per questi tre motivi.

risposta data 24.05.2014 - 03:03

fonte

0

Una cosa che faccio quando si analizzano i parser è scrivere test separati per il solo il lexer. Ciò significa che ci sono molti nuovi casi che dovranno essere testati dallo stage del parser.

Molti dei test per il lexer potrebbero non essere nemmeno validi per il parser. Ad esempio, l'input "]: [" dovrebbe riportarlo con successo a [EndArray, KeyValueSeparator, StartArray, ElementSeparator, EOF], mentre "" \ "" non riuscirebbe a lesseggiare con Error ("preventivo di chiusura previsto").

Non userei un tester casuale, ma io vorrei generare ogni sequenza di token validi e verificare se il parser è d'accordo con me sul fatto che debba essere analizzabile. Garantire che il parser fallisca quando appropriato è tanto importante quanto assicurarne il successo.

Json ha 8 tipi di token (String, Number, BeginList, EndList, BeginObject, EndObject, KeyValueSeparator, ElementSeparator), oltre a EOF (e occasionalmente Error, se non si utilizzano eccezioni). 4 di questi errori nella prima posizione, quindi non avranno bisogno di test con stringhe con più di un token. Altri due (numero e stringa) non possono essere seguiti legalmente da altro, quindi non hanno bisogno di test con stringhe con più di due token. Se il primo token è BeginList o BeginObject, 3 dei token preveranno immediatamente errori.

Ripeti con sequenze di token più lunghe, finché ogni una di esse non è più valida o ripete un testcase precedente solo con un elenco più lungo o qualcosa del genere. Ma ogni testcase positivo deve essere un prefisso di almeno 8 testcases negativi.

risposta data 24.05.2014 - 01:13

fonte

Leggi altre domande sui tag testing recursion

sviluppo basato su test di accettazione in c ++ Test di composizioni complesse

score 1 · Accepted Answer

(I termini "ricorsivo" e "induttivo" significano praticamente la stessa cosa, matematicamente parlando, anche se "ricorsivo" è più comune tra la folla di elaboratori. Ancora più comune per le strutture dati è "dinamico", che si riduce a la stessa cosa, dal momento che le possibili forme di strutture dati dinamiche sono invariabilmente definite da condizioni come "... e puoi annidare un altro nodo proprio come questo alle due estremità.")

Hai ragione che è improbabile che un parser ricorsivamente definito che analizzi l'input ricorsivo abbia bug che richiedono un input molto complicato da esporre - etere il caso base e il caso ricorsivo sono gestiti correttamente, altrimenti non lo sono. C'è sempre il problema dei limiti delle risorse, ovviamente, ma anche quello di solito richiede solo molto grande input da verificare, non necessariamente molto complesso input.

Nella mia esperienza, i difetti insidiosi dei parser si verificano attraverso la combinazione di funzionalità che sono, di per sé, ben supportate: stringhe contenenti citazioni incorporate e caratteri di escape incorporati simultaneamente, i token che secondo uno standard sono letterali ma in pratica sono spesso scritti con virgolette comunque perché i browser attuali si aspettano in questo modo, ecc. Quindi dovresti mirare a configurazioni nuove per testare, non così tanto per più .