Come si esegue il test del codice unitario utilizzando le strutture del grafico?

We keep thinking that we have all the tricky ones covered and then we realise that a certain structure causes problems we hadn't considered before. Testing every tricky that we can think of is what we are doing.

Sembra un buon inizio. Immagino che tu abbia già provato ad applicare alcune tecniche classiche come analisi del valore al contorno o partizionamento equivalenza , come hai già detto test basato sulla copertura. Dopo aver investito un sacco di tempo nella costruzione di buoni casi di test, arriverai ad un punto in cui tu, il tuo team e anche i vostri tester (se ne avete uno) finiscono le idee. E questo è il punto in cui dovresti lasciare il percorso del test dell'unità e iniziare a testare con quanti più dati del mondo reale puoi.

Dovrebbe essere ovvio che dovresti provare a scegliere una grande varietà di grafici dai tuoi dati di produzione. Forse devi scrivere alcuni strumenti o programmi aggiuntivi solo per quella parte del processo. La parte difficile qui è probabilmente quella di verificare la correttezza dell'output del tuo programma, quando metti nel tuo programma diecimila diversi grafici del mondo reale, come saprai se il tuo programma produce sempre l'output corretto? Ovviamente non è possibile controllare che manualmente. Quindi, se sei fortunato, potresti essere in grado di realizzare una seconda implementazione molto semplice del tuo controllo delle dipendenze, che potrebbe non soddisfare le tue aspettative sulle prestazioni, ma è più facile da verificare rispetto all'algoritmo originale. Dovresti anche provare ad integrare molti controlli di plausibilità direttamente nel tuo programma (ad esempio, fai un po 'di contabilità se la ricerca del tuo grafico colpisce tutti i nodi e ogni lato del grafico).

Infine, impara ad accettare che ogni test può solo provare l'esistenza di bug, ma non l'assenza di bug.

In questo caso, nessun test potrà essere sufficiente, nemmeno tonnellate di dati del mondo reale o fuzzing. Una copertura del 100% del codice o addirittura una copertura del 100% del percorso non è sufficiente per testare le funzioni ricorsive.

O la funzione ricorsiva resiste ad una dimostrazione formale (non dovrebbe essere così difficile in questo caso), oppure no. Se il codice è troppo intrecciato con il codice specifico dell'applicazione per escludere effetti collaterali, è da lì che iniziare.

L'algoritmo stesso sembra un semplice algoritmo di flooding, simile a una semplice prima ricerca ampia, con l'aggiunta di una blacklist che non deve intersecarsi con l'elenco dei nodi visitati, eseguito da tutti i nodi.

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

Questo algoritmo iterativo soddisfa la condizione che nessuna dipendenza possa essere richiesta e inserita nella blacklist contemporaneamente, per i grafici di una struttura arbitraria, a partire da qualsiasi artefatto arbitrario in base al quale l'artefatto di partenza è sempre richiesto.

Sebbene possa essere o meno veloce come la tua implementazione, può essere provato che termina per tutti i casi (come per ogni iterazione del ciclo esterno ogni elemento può essere spinto una volta sola sulla coda tovisit ) , riempie l'intero grafico raggiungibile (prova induttiva) e rileva tutti i casi in cui è richiesto un artefatto e la lista nera contemporaneamente, a partire da ciascun nodo.

Se puoi dimostrare che la tua implementazione ha le stesse caratteristiche, puoi provare la correttezza senza che ciò si traduca in test delle unità. Solo i metodi di base per spingere e scoppiare da code, contare la lunghezza della coda, iterare su proprietà e simili devono essere testati e dimostrati privi di effetti collaterali.

EDIT: ciò che questo algoritmo non dimostra è che il tuo grafico è privo di cicli. I grafici aciclici diretti sono un argomento ben studiato, quindi trovare un algoritmo già pronto per dimostrare questa proprietà dovrebbe essere facile.

Come puoi vedere, non c'è bisogno di reinventare la ruota, per niente.

1. Generazione di test randomizzati

Scrivi un algoritmo che genera grafici, fai generare qualche centinaio (o più) grafici casuali e getta ognuno all'algoritmo.

Conserva i semi casuali dei grafici che causano errori interessanti e li aggiungi come test unitari.

2. Parti ingannevoli hard-code

Alcune strutture di grafici che conosci sono difficili da codificare subito, oppure scrivi del codice che le combini e le spinge al tuo algoritmo.

3. Genera elenco completo

Ma, se vuoi essere sicuro che "il codice potrebbe gestire tutte le possibili permutazioni che troverai nei dati del mondo reale.", devi generare questi dati non da seme casuale, ma camminando nonostante tutte le permutazioni. (Questo viene fatto quando si testano i sistemi di segnale della metropolitana, e ci sono enormi quantità di casi che impiegano anni per testare. Per le metropolitane della metropolitana, il sistema è limitato, quindi c'è un limite massimo al numero di permutazioni. si applica)

Stai usando frasi come "tutte le strutture del grafico interessanti" e "gestite in modo appropriato". A meno che tu non abbia modi per testare il tuo codice contro tutte quelle strutture e determinare se il codice gestisce il grafico in modo appropriato, puoi utilizzare solo strumenti come l'analisi della copertura del test.

Ti suggerisco di iniziare a cercare e provare con un numero di strutture di grafici interessanti e determinare quale sarebbe la gestione appropriata e vedere che il codice lo fa. Quindi, puoi iniziare a perturbare quei grafici in a) grafici spezzati che violano le regole o b) grafici non molto interessanti che hanno problemi; controlla se il tuo codice non riesce a gestirli correttamente.

Potresti provare a fare un ordinamento topologico e vedere se ci riesce. In caso contrario, hai almeno un ciclo.

Quando si tratta di questo tipo di algoritmo difficile da testare, sceglierei il TDD, in cui si costruisce l'algoritmo basato sui test,

TDD in breve,

• scrivi il test
• vedi che non funziona
• modifica il codice
• assicurati che tutti i test stiano passando
• refactoring

e ripeti il ciclo,

In questa particolare situazione,

1. Il primo test sarebbe, grafico a nodo singolo dove l'algoritmo non dovrebbe restituire alcun ciclo
2. Il secondo sarebbe un grafico a tre nodi senza ciclo in cui l'algoritmo non dovrebbe restituire alcun ciclo
3. Il prossimo sarebbe utilizzare un grafico a tre nodi con un ciclo in cui l'algoritmo non dovrebbe restituire alcun ciclo
4. Ora potresti testarlo contro un ciclo un po 'più complesso a seconda delle possibilità

Un aspetto importante in questo metodo è che devi sempre aggiungere un test per il possibile passo (dove dividi i possibili scenari in semplici test) e quando copri tutti i possibili scenari solitamente l'algoritmo si evolve automaticamente.

Infine, devi aggiungere uno o più test di integrazione complicati per vedere se ci sono problemi imprevisti (come errori di overflow dello stack / errori di prestazioni quando il tuo grafico è molto grande e quando usi ricorsione)

La mia comprensione del problema, come inizialmente dichiarato e poi aggiornato dai commenti sotto la risposta di Macke, include quanto segue: 1) entrambi i tipi di bordo (dipendenze e conflitti) sono diretti; 2) se due nodi sono collegati da un lato, non devono essere collegati da un altro, anche se è dell'altro tipo o al contrario; 3) se un percorso tra due nodi può essere costruito mescolando i bordi di tipi diversi, allora questo è un errore, piuttosto che una circostanza che viene ignorata; 4) Se c'è un percorso tra due nodi usando i bordi di un tipo, allora potrebbe non esserci un altro percorso tra loro usando i bordi dell'altro tipo; 5) i cicli di tipo single edge o mixed edge non sono consentiti (da un'ipotesi dell'applicazione, non sono sicuro che i cicli di soli conflitti siano un errore, ma questa condizione può essere rimossa, in caso contrario.)

Inoltre, assumerò che la struttura dei dati utilizzata non impedisca di esprimere le violazioni di questi requisiti (ad esempio, un grafico che viola la condizione 2 non potrebbe essere espresso in una mappa dalla coppia di nodi a (tipo, direzione) se il nodo -pair ha sempre il nodo con il numero minimo.) Se alcuni errori non possono essere espressi, riduce il numero di casi da considerare.

Ci sono in realtà tre grafici che possono essere considerati qui: i due di un solo tipo di bordo e il grafico misto formato dall'unione di uno dei due tipi. È possibile utilizzare questo per generare sistematicamente tutti i grafici fino ad un certo numero di nodi. Prima genera tutti i possibili grafici di N nodi che non hanno più di un bordo tra due coppie di nodi ordinati (coppie ordinate perché questi sono grafici diretti). Prendi ora tutte le possibili coppie di questi grafici, uno che rappresenta le dipendenze e l'altro che rappresenta i conflitti, e formare l'unione di ogni coppia.

Se la struttura dei dati non può esprimere violazioni della condizione 2, è possibile ridurre significativamente i casi da considerare costruendo tutti i possibili grafici di conflitto che si adattano agli spazi dei grafici delle dipendenze o viceversa. Altrimenti, è possibile rilevare le violazioni della condizione 2 durante la formazione dell'unione.

Durante una traversata in ampiezza del grafico combinato dal primo nodo, puoi creare l'insieme di tutti i percorsi per ogni nodo raggiungibile e, mentre lo fai, puoi controllare le violazioni di tutte le condizioni (per il rilevamento del ciclo , puoi utilizzare l'algoritmo di Tarjan .)

Devi solo considerare i percorsi dal primo nodo, anche se il grafico è disconnesso, perché i percorsi di qualsiasi altro nodo appariranno come percorsi dal primo nodo in qualche altro caso.

Se i percorsi a bordo misto possono semplicemente essere ignorati, piuttosto che essere errori (condizione 3), è sufficiente considerare indipendentemente i grafici di dipendenza e conflitto e verificare che se un nodo è raggiungibile in uno, non è nel altro.

Se ricordi i percorsi trovati nell'esaminare i grafici dei nodi N-1, puoi usarli come punto di partenza per generare e valutare grafici di N nodi.

Questo non genera più spigoli dello stesso tipo tra i nodi, ma potrebbe essere esteso per farlo. Ciò tuttavia aumenterebbe notevolmente il numero di casi, quindi sarebbe meglio se il codice da testare rendesse impossibile rappresentarlo o, in caso contrario, filtrasse tutti questi casi in anticipo.

La chiave per scrivere un oracolo come questo è di mantenerlo il più semplice possibile, anche se ciò significa essere inefficienti, in modo da poter stabilire fiducia in esso (idealmente attraverso argomenti per la sua correttezza, supportati da test).

Una volta che hai i mezzi per generare casi di test, e ti fidi dell'oracolo che hai creato per separare accuratamente il bene dal male, puoi usare questo per guidare il test automatico del codice di destinazione. Se ciò non è fattibile, la tua prossima migliore opzione è quella di analizzare i risultati per casi distintivi. L'oracolo può classificare gli errori che trova e fornire alcune informazioni sui casi accettati, come il numero e la lunghezza dei percorsi di ciascun tipo e se ci sono nodi all'inizio di entrambi i tipi di percorso e questo potrebbe aiutarti a cercare casi che non hai mai visto prima.