Efficient data-driven finite state machine

Nice work.

1. On findWeekdayDate() return, I'd expect a value that is enumerated like fWD_SUCCESS, fWD_FAIL, fWD_SUCCESS_for_foo_reason, fWD_FAIL_for_bar_reason, etc. Rather than magic numbers -1,0,3,.... It could end up being a simple bool.

2. As fsm[] is const struct fsmNode, I see no value in making a field const like const char target. char target is simpler and sufficient. OTOH, if there is some value, then next should also be const as in const struct fsmNode * const next.

3. Delay/remove #includes.

   #include <string.h>  // Needed?
   #include <stdlib.h>  // OK, for NULL
   #include <ctype.h>   // Needed?
   

4. Style inconsistency. Recommend empty for body to match other indentations.

   // for ( ; state->target && *curr != state->target; ++state) 
   //{ /* do nothing */ }
   for ( ; state->target && *curr != state->target; ++state) {
     /* do nothing */
   }
   

5. Use an auto formatter. The extra space betrays manual formatting as it is inconsistent with the rest of code. Life is too short for manual formatting.

   //             v
   for (curr = str ; *curr; ++curr) {
   

Suggest adding link to software used to create FSM.

This was quite fun to read and to figure out how it works.

It took me a while to understand the control flow, which is my main point of critisism. I rearranged it a bit so that, at least in my opinion, the logic is easier to follow.

for ( ; state->target && *curr != state->target; ++state)
{ /* do nothing */ }

Here, instead of having to use a comment to "excuse" the empty body of the for loop, I would use a while loop and add a real comment explaining its purpose.

if (state->next == NULL) {
    if (state->target) {
        // found a valid string
        return curr-str-4;  
    } else {
        state = fsm;
    }
} else {
    state = state->next;
}

For this part, I would apply the following changes:

• Consistently use implicit boolean evaluation (i.e. use !p instead of p == NULL).
• Use continue, in order to
  • reduce nesting,
  • group each condition with its corresponding action,
  • sort the cases by increasing success (no match → partial match → full match).
• Add comments explaining each case.

This is what comes out:

int findWeekdayDate(const char *str) {
    const struct fsmNode *state = fsm;
    const char *curr;
    for (curr = str; *curr; ++curr) {
        // try to find a match
        while (state->target && *curr != state->target) {
            ++state;
        }
        if (!state->target) {
            // no match, go back to start
            state = fsm;
            continue;
        }
        if (state->next) {
            // current character matched, but the pattern goes on
            state = state->next;
            continue;
        }
        // found a valid string
        return curr - str - 4;
    }
    return -1;
}

I hope this is still correct, at least all the provided test cases are passed.

Other remarks are:

• I'm afraid this is quite an inflexible solution. Adding, removing or changing the patterns would probably require updating most of the next indexes (and the "line number" comments).

• Assuming it was somewhat convenient to generate the fsm structure, it would make sense to make it a parameter of the matching function so that the function can be reused for different FSMs.

• The magic number 4 (in curr-str-4) should be a named constant.

  • Its value should actually by 5 (because it is the length of the WWWDD pattern),
  • the result of the function should then be calculated as (curr - PATTERN_LENGTH + 1) - str in order to (1) make the awareness of the "fence post problem" apparent and (2) highlight the fact that the offset into str is calculated.
  • Hard-coding it into the function makes it also impossible to support patterns where not all matches have the same length, e.g. the full weekday names (which would already be supported by the given FSM data structure).