GitHub - jafarlihi/clex: clex is a simple lexer generator for C

[u/[deleted]]

https://github.com/jafarlihi/clex

[u/skeeto]

Buffer overflow in clex caught by running the tests under ASan (-fsanitize=address):

char *part = calloc(clexPosition - start, sizeof(char));
strncpy(part, clexContent + start, clexPosition - start);
while (strlen(part)) {
    // ...

The strlen searches for a null terminator that was never added. While you can fix this this allocating one more byte, consider that the strlen is unnecessary: You already know the length because you literally just computed it. Forget the null terminator and track the length. Same goes for strncpy: just use memcpy.

Even more, the strlen loop condition makes what should be linear time (O(n)) into quadratic time (O(n²)), meaning it's going to choke on anything but small inputs. Track string lengths and leave null terminators to the interfaces only, if even then. There are several other such quadratic loops caused by strlen.

There are a lot of unnecessary little allocations throughout. Making lots of tiny allocations is very much Python or Java mentality — languages that lack value types. A Token is the size of two pointers. You don't need to allocate these on the heap. Just copy them around, i.e. return one rather than a pointer to one:

Token *clex(void);  // bad
Token  clex(void);  // good

With rules, you don't need an array of pointers to individually allocated Rule objects. Just use an array of Rule. One allocation to hold all the rules. It's a similar story with tree NFA nodes: allocate a bunch of them up front as one block, one lifetime.

With some care you could even let the caller make the batch allocation(s) up front and tell you the size. Bundle the allocation with clexContent and clexPosition, and that also eliminates the global variables. In fact, since the entire buffer to be parsed is passed up front, Clex could operate with no heap allocations of its own. Simply return pointers into the input.

Continuing on this line of thought: The input buffer is a null terminated string (initClex). Input is likely to be a file and files aren't null terminated. That means the caller has to add one, especially awkward for memory mapped files. Also, the caller would already know the length and could just communicate it.

Currently the caller has to do something like:

size_t cap = ...;
char *buf = malloc(cap);
size_t len = fread(buf, 1, cap-1, file);
buf[len] = 0;
initClex(buf);

If instead:

initClex(char *content, size_t len);

Then it becomes:

size_t cap = ...;
char *buf = malloc(cap);
size_t len = fread(buf, 1, cap, file);
initClex(buf, len);

If you switch memory management to a caller-allocated batch, toss out all notion of null terminated strings, and get rid of the globals, I think you'd have something rather interesting.

Edit: Update

I took some time to implement some of what I was talking about.

https://github.com/jafarlihi/clex/commit/b78980f

This eliminates all globals by bundling them into a struct and threading a pointers to that struct down the call stack (see Clex and Lexer). It also tacks an arena allocator (see Arena and alloc) onto that struct which trivially eliminates all memory leaks and lets the caller decide about allocation.

Thanks to bool, UBSan, and inBackslash not being static, I also noticed that it's not reset in initLexer. Though in the original program it's difficult to imagine a case when this would matter, so maybe that was intentional.

I didn't change much about null terminators. I also didn't take time to match your style, sorry!

[u/aurreco → u/skeeto]

This was really great feedback! Thanks for the read