Fuzzing implementation that doesn't require libraries

[EmmanuelMess]

I propose a function that generates syntactically correct strings, to test the interpreter:

enum Simbol {
    SIGMA, DECLARATION, VAR_NAME, NUMBER,
    assign, end,
    letterA, letterB,
    number1, number2
};

const std::set<Simbol> terminalSimbols {
    assign, end, letterA, letterB, number1, number2
};

const std::unordered_map<Simbol, std::string> finalReplacement {
    {assign,  " := " },
    {end,     ";" },
    {letterA, "a"},
    {letterB, "b"},
    {number1, "1"},
    {number2, "2"},
};

const std::unordered_map<Simbol, std::vector<std::vector<Simbol>>> intermidiateReplacement {
    {SIGMA,          { { DECLARATION } } },
    {DECLARATION,   { { end }, { VAR_NAME, assign, NUMBER, end }, { DECLARATION, DECLARATION } } },
    {VAR_NAME,      { { letterA }, { letterB }, { VAR_NAME, VAR_NAME } } },
    {NUMBER,        { { number1} , { number2 }, { NUMBER, NUMBER } } }
};

const std::unordered_map<Simbol,  std::discrete_distribution<int>> intermidiateReplacementDist {
    {SIGMA,          { 1 } },
    {DECLARATION,   { 0.5, 1, 0.5} },
    {VAR_NAME,       { 1, 1, 1 } },
    {NUMBER,        { 1, 1, 0.5 } }
};

std::list<Simbol> generate() {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::list<Simbol> list;
    list.push_back(SIGMA);

    int terminalsInList = 0;

    auto i = list.begin();
    while (terminalsInList < list.size()) {
        if(i == list.begin()) {
            terminalsInList = 0;
        }

        bool terminal = terminalSimbols.find(*i) != terminalSimbols.end();

        if (!terminal) {
            auto replacementDistribution = intermidiateReplacementDist.at(*i);
            std::vector<std::vector<Simbol>> currentReplacementPossibilities = intermidiateReplacement.at(*i);
            assert(currentReplacementPossibilities.size() == replacementDistribution.probabilities().size());

            auto replacement = currentReplacementPossibilities[replacementDistribution(rd)];

            list.insert(i, replacement.begin(), replacement.end());
            i = list.erase(i);
        } else {
            terminalsInList++;
            ++i;
        }

        if(i == list.end()) {
            i = list.begin();
        }
    }

    return list;
}

int main() {

    for (int i = 0; i < 100; ++i) {
        for (auto v : generate()) {
            assert(terminalSimbols.find(v) != terminalSimbols.end());
            std::cout << finalReplacement.at(v);
        }
        std::cout << std::endl;
    }

    return 0;
}

Output:

/home/emmanuel/Documentos/temp/testregularthing/cmake-build-debug/testregularthing
a := 1;b := 2;
;
a := 1;
bbab := 2;b := 1;
a := 2;
;
bab := 12;
b := 1;
b := 2;
a := 12;
;
;
;b := 1;
b := 1;
a := 1;
baa := 1;
a := 2;
bbaab := 1;
;
b := 2;
aba := 2;
;
a := 2;
a := 1;
bb := 2;
a := 2;
b := 111;
a := 1;
baab := 21;a := 2;bb := 121;bbbabaabab := 1;;b := 2;;
;
;
bb := 1;aa := 2;;
;
bbaa := 2;a := 1;
ba := 1;
baababaaababaabaaabaaba := 2;
aabbaabaabaaaaaabb := 12;
a := 1;
;;
;
ab := 2;
b := 2;
;
;;
a := 1;;;
bbb := 211;;;
;
aa := 1;
a := 1;
ba := 1;
;
abb := 1;
b := 1;
b := 2;b := 12;;b := 2;;a := 2;b := 2;;b := 111112;
b := 12;
;bba := 1;ab := 2;;
a := 1;
b := 1;
ba := 2;
a := 2;
ababb := 12;
aba := 1;
;
abaa := 1;
;a := 1;;
a := 2;
;
a := 1;
;
abaabb := 1;b := 1;a := 1;
b := 2;
;
;
a := 1;
;;
b := 1;
;
;
b := 12;
;
a := 2;
;a := 2;
;
;
;
;
b := 2;
bb := 1;b := 11122;
;
a := 1;
aabbb := 122;
b := 2121;
ba := 1;;
bb := 2;
ba := 2;
;
b := 1;
;
;
a := 11;

[SebastianMestre]

That's pretty cool. I had tried something similar a while back, but I never actually filled out the tables according to Jasper's syntax. Is that something you could do?

We don't have a full BNF for Jasper's syntax, but I could try to write it up, if that'd help.

[EmmanuelMess]

I can try to make production rules that fit the language.

[EmmanuelMess]

How should redefinitions of the same variable be handled? like: a:= 10; a:=1;

[SebastianMestre]

I can try to make production rules that fit the language.

Would having a BNF help?

How should redefinitions of the same variable be handled? like: a:= 10; a:=1;

It shouldn't be allowed.

That is not what actually happens in the compiler, which could be considered a bug. (EDIT: addressed in #188)

[EmmanuelMess]

Would having a BNF help?

Reading about BNF, it seems it constructs a context free language, the issue right now for me would be dealing with (variable) names and how to not repeat them.

[SebastianMestre]

the issue right now for me would be dealing with (variable) names and how to not repeat them.

The way we handle variables in the compiler is with a stack of hash tables.

Whenever a new scope is introduced (either by a for-statement, a block-statement, or a function-expression), we push a new table onto the stack, and pop it when the scope ends.

When producing a new name, one could generate random (valid) strings until one that is not "in the current scope" is generated.