4 ms·
> > 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 c
by 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.)