4 ms·
This article gave me a fair bit of nostalgic feelings. So much so, that I had to go and dig out one of my first university assignments from seven years ago[!],
by jdsalaro 6y ago
This article gave me a fair bit of nostalgic feelings. So much so, that I had to go and dig out one of my first university assignments from seven years ago[!], writing a simple Linux Shell, where I actually had to use "decision tables". In my case I remember thinking about using an automata for a grammar to prevent my code from becoming an unmaintainable, unexplainable, SEGFAULT-y mess.
Most important of all, I remember the lecture assistant telling us that we "won't pass the assignment as long as I can bring your program to SEGFAULT."
Many of us struggled, SEGFAULT after SEGFAULT, with uneven quotes, pipes inside or outside quotes, double bars, double ampersands, etc. As the days progressed, many code-bases became more complex and more fragile as we tried to deal with the pesky inputs of the lecture assistant. When our turn came up, we all grinned while the lecture assistant tried in frustration to bring our shell to SEGFAULT. I remember pointing out "those inputs are not supported by the grammar, and walking him through the bits I list below". Those were the days, oh man :)
---
struct listNode {
char *token;
int type;
struct listNode *next;
};
...
#define M_BEGIN 0
#define T_WORD 1
#define T_QUOTE 2
#define T_BAR 3
#define T_AMP 4
#define T_NL 5
...
int validateInput(struct listNode * head) {
unsigned char smpshGrammar[6][6] = {
{0,1,0,0,0,1}, // M_BEGIN
{0,1,1,1,1,1}, // T_WORD
{0,1,1,1,1,1}, // T_QUOTE
{0,1,0,0,0,0}, // T_BAR
{0,0,0,0,0,1}, // T_AMP
{0,0,0,0,0,0}}; // T_NL
struct listNode * iterator = head;
int validInput = 1;
int previousState = 0;
while(iterator && validInput){
if(DEBUG) printf(" Debug Information > Validating transition from Q%d to Q%d ... Possible:%d\n",
previousState,
iterator->type,
smpshGrammar[previousState][iterator->type]);
if(smpshGrammar[previousState][iterator->type])
{
previousState = iterator->type;
iterator = iterator->next;
}
else { validInput = 0; }
}
if(previousState!=5){ validInput = 0; }
return validInput;
}
- chubot 6y agoInteresting that you did this as part of a course! It makes a lot of sense, as I agree shell has a lot of conditionals to handle. I would say that the segfaults are an instance of the "else-idgaf anti-pattern" where the corner cases are undefined/broken. This seems to happen a lot in bash. I use regular languages a lot in the Oil shell precisely because it forces every state and transition to be defined: https://lobste.rs/s/jyyuhn/decision_table_patterns#c_o49q52 https://lobste.rs/s/jyyuhn/decision_table_patterns#c_o49q52 Related: How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html http://www.oilshell.org/blog/2019/02/07.html also related: https://lobste.rs/s/jyyuhn/decision_table_patterns#c_yukvlr https://lobste.rs/s/jyyuhn/decision_table_patterns#c_yukvlr
- hansvm 6y agoIt looks like "else-idgaf" is meant to describe not considering all cases. What do you think about pushing input validation to the caller; you write code that explicitly considers some subset of all possible inputs and thoroughly document that subset -- behavior for other inputs is not guaranteed.
- chubot 6y agoI think if you have an assert() for the invalid input, that makes sense. I don't think documentation is enough in practice. In my experience, you can write "don't call this with 0" in the comments, or you can write it in the documentation -- it doesn't matter. Someone will call it in an unexpected way. They will make it work for the happy path and not consider the other cases, because that takes time. (And that includes myself in many instances.) So the only way to be sure is to blow up and make it a hard bug. ---- I'll also note that very few functions are public APIs with documentation. I'm thinking about the bash codebase, which has 140K lines of C written over 30 years. There are a lot of informal internal APIs, and few documented APIs. They are kinda stable but also subject to change. So I think assert() is the best way of "documenting" the expected invariants in these cases, which comprise the vast majority of coding situations.
- andreareina 6y agoIt's really a wonderful thing when once you understand the data the rest of the code becomes obvious.