It's not about walking a dependency graph, but about getting the dependencies 100% right. In C, that's indeed very difficult, or at least a lot of work.
I don't know if you have tried MSBuild, but I've spent countless numbers cleaning up .vcxprojs, shifting things around, factoring into extern .props files, etc. Even on major changes I was often surprised how little rebuild was necessary. The granularity at which the system detects changes is not just per-file. It has per-file caches for the set of preprocessor variables, the set of include paths, all the little compilation and link settings, and so on.
So what it will do if you change the build file is, it will re-execute the build file processor and generate all the necessary build information for each C file. And then, it only rebuilds each file if a build dependency has actually changed in a relevant way for that file. For example, the order in which the preprocessor variables are defined does not matter (as long as they don't overwrite each other), but the ordering of include paths does. Also, if any of the files that were #include'd (transitively) in the last build changed since them, a rebuild is needed.
Compare that to the average crappy Makefile system that you are going to set up. The best thing you could achieve with Make will never be going to rebuild as little, or rebuild reliably the stale build products. I like Make for other reasons, but MSBuild is better and more robust.
I have spent large amount of time working with msbuild while migrating msbuild build into a different build system (including working on implementation of two way converter, from an to msbuild).
What you described (cache based on preprocessor flags) is really cool, in practice it does not give a huge win compared to proper modern build system like Bazel, and decent user interface (including the build language) and extensibility is much more important. Especially because it’s super hard to properly configure msbuild project with proper dependencies between modules.
I have a friend who worked at MS. He told stories how in their VS projects dependencies between modules (projects) were not configured, developers had to manually invoke compilation of dependencies. In theory it is possible to configure msbuild properly, in practice even MS employees failed to do so.
But I don’t consider msbuild a build system. For me it’s just a project format for VS which some developers commit to VCS. It’s great that MSBuild allows to have a proper C++ project definition with a custom command to actually build it (external build system), so VS sees proper project structure, but developers don’t have to deal with vcxproj files.
> He told stories how in their VS projects dependencies between modules (projects) were not configured
Yes that's still an issue at my workplace as well. When I joined, there were no dependencies - all files were compiled redundantly for each project. So there were no issues with regards to reliably rebuilding dependencies, but of course it takes a lot longer to build. And there are serious maintainability issues with de-facto internal libraries, because adding or removing files to/from each "library" means that each dependent project file has to be updated. I've started to split out a few "library projects", and now we're starting to get the rebuilding issue. I think dependencies can be configured in *.sln files, but that probably means that they have to be configured separately for each project, i.e. it probably can't be done automatically when simply importing the library's .props file into a .vcxproj.
A nice middle ground could be to make .props files that just include .c files, meaning the library's files will be part of each project, so no rebuilding issues and no maintenance issues since the list of files that belongs to a library is maintained in one isolated place (the .props file). But that again means the files are built redundantly in each project.
But the long-term solution will be to maintain the build descriptions in better-suited in-house data structures (yeah like CMake, just not that scary) and to generate the MSBuild cruft from that.
I don't know if you have tried MSBuild, but I've spent countless numbers cleaning up .vcxprojs, shifting things around, factoring into extern .props files, etc. Even on major changes I was often surprised how little rebuild was necessary. The granularity at which the system detects changes is not just per-file. It has per-file caches for the set of preprocessor variables, the set of include paths, all the little compilation and link settings, and so on.
So what it will do if you change the build file is, it will re-execute the build file processor and generate all the necessary build information for each C file. And then, it only rebuilds each file if a build dependency has actually changed in a relevant way for that file. For example, the order in which the preprocessor variables are defined does not matter (as long as they don't overwrite each other), but the ordering of include paths does. Also, if any of the files that were #include'd (transitively) in the last build changed since them, a rebuild is needed.
Compare that to the average crappy Makefile system that you are going to set up. The best thing you could achieve with Make will never be going to rebuild as little, or rebuild reliably the stale build products. I like Make for other reasons, but MSBuild is better and more robust.