The Root of the Dependency Tree

submited by
Style Pass
2023-09-18 08:00:02

My personal blog about problems I find intriguing. I would love to hear from you! Feel free to reach out through my about page.

The hobby debugger I am working on, Spray, features custom syntax highlighting of C source code. To implement this, I had to recursively parse all the type definitions in the current source file and in its dependencies.

C is not a context-free language, which leads to the so-called typedef-name problem 1. The problem is that typedef can be used to make types look like regular identifiers. This creates some situations where context is needed to determine whether the given identifier is a type. Since types and identifiers should be highlighted with different colors, I had to get that context.

While slowly iterating on the logic required to solve this problem, I got to a point where I could inspect the entire public dependency tree of all the header files included in a single source file. Header files are all I need to worry about here, since that is where all public type definitions live.

This revealed some pretty interesting patterns, some of which I have already shared on Twitter/X. What I found most interesting is that basically every program you will every write2 will somehow include the bits/wordsize.h header file. Here is what it looks like on my machine:

Leave a Comment