Topological sort for alltex

[lambdaTotoro]

Qoth Michael:

Es gibt "lmh make alltex", das macht eine Datei all.tex (all.*.tex wenn multilingual) die alle Dateien eines directory includiert.

Es wäre toll, wenn diese topologisch nach der dependency relation sortiert würden (nicht alphabetisch nach file-namen).

Für die problem repositories wird das nicht direkt funktionieren; aber vielleicht kann man anhand der dependencies auch sortieren.

[lambdaTotoro]

Okay, I think the current state (i.e. commit 43f3d780d5d6b3e98c83ae4359f9626c9a7c0ab9 and after) is workable. The files are now sorted primarily topologically and secondarily by size of dependency closure (ignoring the sms parts, because cycles).

Could you test if this fits your use cases, @kohlhase ?

[kohlhase]

I have tested, and topological sort does not seem to work yet. I go to ../MathHub/MiKoMH/KRMT/source/categories/en/ and do a mmt make alltex there and I get

\begin{center} \LARGE File: \url{categories-krmt.tex} \end{center}
\input{categories-krmt} \newpage

\begin{center} \LARGE File: \url{common-categories.tex} \end{center}
\input{common-categories} \newpage

\begin{center} \LARGE File: \url{NNO-unique.tex} \end{center}
\input{NNO-unique} \newpage

the first two are OK, but the last one depends on Lawvere-NN.tex, which is last in all.tex

[lambdaTotoro]

Okay, could you try again with a recent devel (i.e. commit e2410d5a67cd3b9b2d63237efc64483afedecf6f and newer)?

I tested it locally with folders from MiKoMH/AI, MiKoMH/IWGS and the above from MiKoMH/KRMT and it works fine for me. But I'd like you to verify that before I close the ticket.

Edit: oh, also, I didn't test this on problem repositories yet, I'll have a look sometime soon.

[kohlhase]

I have tested this non-exhaustively, and it seems to work. A very nice side effect of this topological sort is that I get a much better sense of what imports are missing. Thanks a lot.

[kohlhase]

I am afraid, there is still something wrong: when I run mmt make alltex with the newest devel build on MathHub/MiKoMH/AI/source/csp/en, then I get

\begin{center} \LARGE File: \url{encode-hypergraph.tex} \end{center}
\input{encode-hypergraph} \newpage

\begin{center} \LARGE File: \url{csp-complexity.tex} \end{center}
\input{csp-complexity} \newpage

\begin{center} \LARGE File: \url{ac-motivation.tex} \end{center}
\input{ac-motivation} \newpage

\begin{center} \LARGE File: \url{cutset-conditioning-algo.tex} \end{center}
\input{cutset-conditioning-algo} \newpage

\begin{center} \LARGE File: \url{csp-questionnaire.tex} \end{center}
\input{csp-questionnaire} \newpage

\begin{center} \LARGE File: \url{constraint-graph.tex} \end{center}
\input{constraint-graph} \newpage

\begin{center} \LARGE File: \url{csp-intro.tex} \end{center}
\input{csp-intro} \newpage

even though encode-hypergraph.tex contains

\importmhmodule[dir=csp/en]{csp-intro}

could it be that the dir-variant of \importmhmodule is not taken into account yet? \importmhmodule[dir=csp/en]{csp-intro} is an abbreviation for \importmhmodule[path=csp/en/csp-intro]{csp-intro}

[lambdaTotoro]

Annoying. 😒 encode-hypergraph.tex is indeed listed as not depending on anything, even though it clearly does. I'll follow up with your hunch, although this should have been done with #499 (and the dependency is included in encode-hypergraph.sms when I generate that manually). Maybe I missed something then. Or it might somehow drop some dependencies off alltex BuildTasks.

Thanks for finding this! I'll take another look.

[lambdaTotoro]

Okay, I think I know what's going on, now. Take a look at (this part of) the dependency graph I generated for MiKoMH/AI/source/csp/en:

This cannot be topologically sorted, because it contains cycles (in this case between problem-solving-intro.tex and problem-formulation.tex at the very bottom). Such cycles between sms files are common. And since we're not actually putting these sms files down the dependency tree into all.tex, I previously just filtered them out.

But! As you can also see from the above graph, the dependency from encode-hypergraph.tex to csp-intro.tex goes to the sms-dependency, not the alltex-dependency. Hence, it will be forgotten, encode-hypergraph.tex will have no dependencies and be wrongly sorted in the topsort.

I'm fairly certain this is the culprit, I'll let you know when I have a new version to test, should be soon.

[kohlhase]

I think that this is another instance of the \importmodule, \usemodule problem. We need to understand/solve this once and for all.

[lambdaTotoro]

Okay, leaving the general case of sms worries alone (because sms might be gone soon), I simply corrected the dependency map so that alltex targets depend on alltex targets and not on sms targets. This allows us to throw away the part of the dependency tree that has (faulty) sms cycles and still keep a correct dependency relation between the nodes that are left.

As a result, as of commit 05ed04b390337c5782e458bb5086877a8103c28e, the topological sorting should work fine. I tested it in the above directory manually and it works fine there, but please let me know if it also does for you.