5 ms·
> Build graphs are acyclic. While yes, this is a falsehood... in practice, you generally want to figure out a way to break cycles and remove them from the buil
by klodolph 6y ago
> Build graphs are acyclic.
While yes, this is a falsehood... in practice, you generally want to figure out a way to break cycles and remove them from the build system. In general, make the user responsible for breaking cycles in the build system.
The only major use case for cycles that I can think of is self-hosting compilers.
I would add some additional falsehoods:
- It is always the right thing to rebuild files when the inputs have changed.
- The host and target systems are the same (you are never cross-compiling).
- The host and target systems are different (you are always cross-compiling).
- You can reliably figure out the version number of whatever you are building.
- The build steps always produce the correct outputs if they do not fail.
- You always want to build third-party dependencies from source.
- You never want to build third-party dependencies from source.
- The input files do not change while the build is running.
- All of the inputs are files (and not, say, the current timestamp).
- The entire build should use the same build settings (optimization / debug), you don't want to do a partial-debug, partial-optimized build.
- You don't want to rebuild when e.g. files in /usr/include change.
- You always want to rebuild when e.g. files in /usr/include change.
- Installing additional software will not break the build.
- Running the same build twice will result in the same output.
- Build products do not contain absolute paths.
- You can move an executable from one path to another and it will still work.
- You can delete object files and everything will still work.
- jnxx 6y ago> > Build graphs are acyclic. Normal C code, not that I can think of. But it is not difficult to give a real-world example: A LaTeX document with a table of contents and an index has a cyclic dependency: The final document, including its pagination, depends on the table of contents, and the table of contents depends on the final document.
- amelius 6y ago> A LaTeX document with a table of contents and an index has a cyclic dependency One of the uglier problems of LaTeX, which people of the likes of Leslie Lamport and Donald Knuth should have been able to solve, one might think.
- CJefferson 6y agoI think this is an impossible problem to fix -- inserting page numbers into a document can change formatting enough to cause things to move to a different page. There are LaTeX documents which never reach a fixed point (I've made one by accident exactly once), and need slight adjustment.
- amelius 6y agoThen "iteratively computing a fixed point by simply rerunning the formatter from scratch" is not a solution to the problem. Actually I think you can do it iteratively by never decreasing the space occupied by an element between iterations. Of course this might yield ugly results but at least it halts with a solution.
- yongjik 6y agoWhen Knuth was writing TeX, computer systems had really small memories - I'm sure it strongly affected TeX's architecture, because TeX reads the source document and generates output pages one by one, like some kind of online streaming processor. It never holds the entire document in memory, because old computers couldn't do it.
- pantaloony 6y agoSeems reasonable to me. One of the first things I’d reach for if I wanted to build a flexible tool that’d perform well, last, and be broadly useful is the ability to chop up the workload, ideally into a fixed size, but into some practically-by-convention-probably-not-too-big size as a (riskier) fallback if fixed size wasn’t practical. IME any time you need performance & stability with unknown input, it’s gonna end up looking like streaming.
- klodolph 6y agoThis is pretty easy to encapsulate into an individual build step. Rerun LaTeX until the TOC doesn’t change. Fail if this takes too many iterations or repeats. I have written LaTeX rules for Bazel.
- zzo38computer 6y agoI use Plain TeX instead of LaTeX, although whichever system you use, these would be the same problems, and there are some possibilities: - Use separate page numbering for the table of contents. - Since the number of table of contents entries will not change, just use two passes; you don't need a separate page numbering for the table of contents. - Never reference page numbers within the main text; use section numbers instead. This avoids problems with their size changed. Anyways, when I need to do this, I do it purely in TeX rather than using a separate build system. (There is a way to use insertions containing alternating marks and penalties to extract the information needed without shipping out the page.)
- bjourne 6y ago> The only major use case for cycles that I can think of is self-hosting compilers. Yup. In the build system for a self-hosting compiler I wrote I solved it using an optional target. If the compiler is present, generate the boot code using it, else download the boot code from a site on the internet, do md5sum checking and bootstrap from that. In a good build system, modeling this is a piece of cake.