vendredi 27 mars 2020

Go DFA implementation best practice

Suppose I need to write a simple DFA in Go (dfa.go below is counting whether number of occurrence of "A" is odd)

However, when writing tests (dfa_test.go), I cannot reach 100% coverage (using go test -cover) because line 33 cannot be covered. Removing this line definitely solves the problem, but I still want the code to panic when the DFA is incorrectly implemented (e.g. If I am changing it to counting number of A modulo 3, it is easy to make a mistake)

So what is a good programming practice when writing DFAs in Go?

dfa.go:

package dfa

func DFA(input string) int {
    /*
        Transitions:
            (0, 'A') -> 1
            (0, 'B') -> 0
            (1, 'A') -> 0
            (1, 'B') -> 1
    */
    state := 0 // start state
    for _, i := range input {
        switch {
        case state == 0:
            switch i {
            case 'A':
                state = 1
            case 'B':
                state = 0
            default:
                panic("Invalid input")
            }
        case state == 1:
            switch i {
            case 'A':
                state = 0
            case 'B':
                state = 1
            default:
                panic("Invalid input")
            }
        default:
            panic("Invalid state")      // line 33
        }
    }
    return state
}

dfa_test.go:

package dfa

import (
    "testing"
)

func TestDFA(t *testing.T) {
    if DFA("AABBAABBABA") != 0 {
        t.Errorf("error")
    }
    func() {
        defer func() {
            if recover() == nil {
                t.Errorf("error")
            }
        }()
        DFA("AC")
    }()
    func() {
        defer func() {
            if recover() == nil {
                t.Errorf("error")
            }
        }()
        DFA("C")
    }()
}

Aucun commentaire:

Enregistrer un commentaire