[Feature Request] Lazy variable/dependency evaluation

[Volker-Weissmann]

Hello,

lets say your project includes building a lot of libraries, and the dependency graph of these libraries is given by this acyclic graph. You might solve this by writing

libEvar = library('mylibE', 'fileE.cpp', link_with : [])
libDvar = library('mylibD', 'fileD.cpp', link_with : [libEvar])
libCvar = library('mylibC', 'fileC.cpp', link_with : [libDvar, libEvar])
libBvar = library('mylibB', 'fileB.cpp', link_with : [libDvar])
libAvar = library('mylibA', 'fileA.cpp', link_with : [libBvar, libCvar, libEvar])

This works, but there is one major problem: It breaks once you change the order of those lines. If all of these lines are in the same meson.build file, then putting them into the correct order is easy. But if these lines are scattered across multiple meson.build files in nested subdirectories, then it might no longer be possible (Imagine if libEvar and libCvar are in a subdirectory of libDvar's directory).

One solution would be to write this:

libs = []
# The order of the following 5 lines is irrelevant
libs += [['mylibA', 'fileA.cpp', ['mylibB', 'mylibC', 'mylibE']]]
libs += [['mylibB', 'fileB.cpp', ['mylibD']]]
libs += [['mylibC', 'fileC.cpp', ['mylibD', 'mylibE']]]
libs += [['mylibD', 'fileD.cpp', ['mylibE']]]
libs += [['mylibE', 'fileE.cpp', []]]

lookup = {}
foreach step : [1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]
        foreach lib : libs
            flag = true
            deps = []
            foreach dep : lib[2]
                if dep not in lookup
                     flag = false
                else
                     deps += lookup[dep]
                endif
            endforeach
            assert(step == 1 or flag, 'error building the dependency graph')
            if flag and lib[0] not in lookup
                lookup += {lib[0] : library(lib[0], lib[1], link_with : deps)}
            endif   
        endforeach
endforeach

This basically does what I want/need, but it feels like very bad style. Meson should have some functionality to build these acyclic graphs itself.

This lazy function would also solve similar problems that arise if you try to use an executable to generate sources, before building that executable.

I thought of using subprojects instead of subdirs, but that would result in sandbox violations if some libraries share source files with other libraries.

[mensinda]

First of all, I do understand your issue (and I also ran into this problem myself when I accidentally changed the order of my subdirs) and I get that this is an annoyance, however, implementing lazy evaluation would have massive implications for the meson project:

• it makes everything more complex, which means more logic and code and thus a higher maintenance burden (which is not inherently bad if the feature is worth it)
• it would be a fundamental shift from our current design where we evaluate everything line by line. Changing this makes the core more difficult to reason about (both for humans and other software).
• it also effectively makes libraries, etc. mutable while one of the core features/design decisions of meson is that all libraries/etc. are immutable after creation.
• it is currently impossible to generate cyclic dependencies with build objects in meson. So new logic would need algorithms for detecting cycles basically everywhere to ensure that we end up with a DAG since we get this feature currently for free with our more restrictive syntax.

And finally, implementing this correctly would be a huge effort, since it would require some major changes to the interpreter to allow correct general lazy evaluation or some hacky and error-prone mess after the interpreter ran to fix all the references...

[Volker-Weissmann]

Since I never read the meson source code, I cannot say how easy or hard the implementation will be.

it also effectively makes libraries, etc. mutable while one of the core features/design decisions of meson is that all libraries/etc. are immutable after creation.

Libraries can still be immutable if they are created late enough.

My proposal: Add a function called e.g. "order_and_eval":

my_array = []
my_array += [['libDvar', 'library(\'mylibD\', \'fileD.cpp\', link_with : [libEvar])']]
my_array += [['libEvar', 'library(\'mylibE\', \'fileE.cpp\')']]
order_and_eval(my_array)

Notice how 'libDvar' and 'library(\'mylibD\', \'fileD.cpp\', link_with : [libEvar])' are just definitions of strings.
The order_and_eval first parses the 'libary...' strings to mesons AST. order_and_eval then makes a list of all undefined variable references in the AST, in this case [libEvar] for the first line and [] for the second line. order_and_eval now knows which line depends on which other line. order_and_eval can then check if the graph is connected and acylic and exit with a meaningful error message otherwise. order_and_eval can then put the lines in the correct order and evaluate them.

Graphlib can do topological sorts, which is exactly what order_and_eval needs to do.

What I wrote is basically what order_and_eval should do, but python is better suited for such cases than the meson dsl.

Maybe there could also be some syntax sugar for

my_array += [['libDvar', 'library(\'mylibD\', \'fileD.cpp\', link_with : [libEvar])']]

Maybe something like

my_array.lazy( libDvar = library('mylibD', 'fileD.cpp', link_with : [libEvar])  )

If the AST parsing to find all undefined variable references, is too complicated one could also write

my_array += [['libDvar', ['libEvar'], 'library(\'mylibD\', \'fileD.cpp\', link_with : [libEvar])']]

The following should abort:

my_array = []
my_array += [['libDvar', '...']]
my_array += [['libDvar', '...']]
order_and_eval(my_array)

[mensinda]

Ok, this proposal could work, however, there are some problems.

my_array.lazy( libDvar = library('mylibD', 'fileD.cpp', link_with : [libEvar])  )

If the AST parsing to find all undefined variable references, is too complicated one could also write

Yes, this is way too complicated, since we would have to do a special case in the parser (not even the interpreter) for one object + method call combination...

Secondly, I don't know the official 100% correct stance regarding eval(), however, I am 99.9% certain that any form of eval() will never be accepted.

What could work is a new object type for defining dependency graphs for user-defined objects (maybe even as a new experimental module). Essentially something like this could work:

dag = import('graph')


// Syntax:
// dag.insert('<provides>', depends: ['<optional>', '<list>', '<of>', '<deps>'], data: <opaque object>}
dag.insert('mylibA', depends: ['mylibB', 'mylibC', 'mylibE'], data: {'src': ['fileA.cpp']})
dag.insert('mylibB', depends: ['mylibD'],                     data: {'src': ['fileB.cpp']})
dag.insert('mylibC', depends: ['mylibD', 'mylibE'],           data: {'src': ['fileC.cpp']})
dag.insert('mylibD', depends: ['mylibE'],                     data: {'src': ['fileD.cpp']})
dag.insert('mylibE', data: {'src': ['fileE.cpp']})

dag.insert('mylibX', depends: ['mylibY'], data: {'src': ['fileX.cpp']})
dag.insert('mylibY', depends: ['mylibZ'], data: {'src': ['fileY.cpp']})
dag.insert('mylibZ', depends: ['mylibX'], data: {'src': ['fileZ.cpp']}) // Generates a cycle error

foreach i : dag.as_list()
  // Your code that just adds the libs
  // Guaranteed to have all dependencies resolved
endforeach

Also, thanks for telling me about graphlib, however, we only recently bumped our min. python version requirement to 3.6, so requiring 3.9 features is a few years away :)

[Volker-Weissmann]

I think the following syntax would make more sense:

dag.insert('mylibB', depends: ['mylibD'],  cmd: 'library(\'mylibB\', \'fileB.cpp\', link_with : [libDvar])')

[mensinda]

The problem with cmd: 'library(\'mylibB\', \'fileB.cpp\', link_with : [libDvar])' is that we are not adding any string eval() functionality. This also includes any runtime AST analysis of random strings. This would be a huge pain to get right in the first place and also a huge maintenance burden going forward.

My idea was a general dependency graph data structure where you can define some provides and depends strings and attach to each entry a user-defined object that meson does not care about and will completely ignore for all internal operations. It is then up to the user to iterate over this object (which is guaranteed to be topologically sorted) in a foreach loop and interpreter the user data.

This approach has the advantage that you can maintain any kind of dependency tree and the impact for the meson codebase is minimal since no changes to the interpreter are required.

[Volker-Weissmann]

Ok. I'm a bit disappointed, but if everything else would be too much of a writing and maintenance burden, then that's ok.

[Volker-Weissmann]

Do you want to implement this Feature Request or should I do it?

[mensinda]

Patches are always welcome and I currently have limited time to work on meson. However, here are some (hopefully helpful) pointers for getting started:

First of all, this feature should be in a new module, since

• it is arguably not a core feature because you can do the sort manually (this module just makes things easier)
• this makes the algorithm more logically contained.
• this increases the likelihood of getting the PR merged.

---

These are only recommendations and by no means hard requirements:

• Try to avoid changes in the core interpreter and work with new objects when required.
• A good starting point would probably be to look at the external_project module and the cmake module for a setup with custom InterpreterObjects.
• Modules themself are stateless, so you will likely need a new InterpreterObject

In meson code this would mean:

dag_mod = import('graph')    # dag_mod is stateles
dag     = dag_mod.gen_dag()  # generate the object that does all the actual work

dag.insert(...)   # do the actual work

---

Some important points from our contributing docs:

• new features need a release snippet
• the module needs documentation
• some form of tests are required (in this case including tests that are expected to fail (dependency cycles, etc.))

We are also in the (admittedly slow) process of type annotating the meson source code, so new code should also be fully type annotated and the new module should be added to our run_mypy.py script.

Feel free to ask if you have any questions.

[jpakkane]

Notice how 'libDvar' and 'library('mylibD', 'fileD.cpp', link_with : [libEvar])' are just definitions of strings.

One of the core design points of Meson was that things are actually objects and not strings to things that might get defined later. Make, CMake, Bazel and possibly others do that and it always leads to incredibly convoluted and unmaintainable messes. For example you might look at the build definitions of Google's Abseil C++ libraries and try to work out how the dependencies go.

Meson does not do that by design. It requires you to be very clear, direct and upfront about your build structure. It proceeds through source directories in specific and unsurprising ways. Enter one dir. Process it. Never return to it. Proceed to the next one. Never return to it. And so on. This means that people writing their build definitions can rely on this behaviour. It reduces the mental burden of working out what is happening when bugs occur.

We are very, very, very unlikely to add functionality to add lazy evaluation like this. That is not to say we could not add other primitives to improve things, but a general lazy evaluation thing is exceedingly unlikely to be accepted.

[mensinda]

@jpakkane jus to be clear, do you then have any objections to a new general graph module, as described in #8178 (comment)?

[jpakkane]

Yes I have. For mostly the same reasons. I am strongly of the opinion that if your build definition is so bizarrely complicated that it requires a DAG dependency solver, then the bettersolution is to make your build setup simpler rather than adding this functionality to the build system.

[Volker-Weissmann]

Notice how 'libDvar' and 'library('mylibD', 'fileD.cpp', link_with : [libEvar])' are just definitions of strings.

One of the core design points of Meson was that things are actually objects and not strings to things that might get defined later. Make, CMake, Bazel and possibly others do that and it always leads to incredibly convoluted and unmaintainable messes. For example you might look at the build definitions of Google's Abseil C++ libraries and try to work out how the dependencies go.

Meson does not do that by design. It requires you to be very clear, direct and upfront about your build structure. It proceeds through source directories in specific and unsurprising ways. Enter one dir. Process it. Never return to it. Proceed to the next one. Never return to it. And so on. This means that people writing their build definitions can rely on this behaviour. It reduces the mental burden of working out what is happening when bugs occur.

Good plan, but to quote a prussian general: "no plan survives contact with the enemy", or in our case "no architecture design survives contact with legacy code".

I'm currently working on a project with roughly 10000 *.cpp files, 10000 *.hpp files that are built into 130 shared libraries and 260 binaries. It currently uses gnu make + 2500 lines of custom bash scripts.
I want to write meson.build files for it (more exactly: I want to write a python script that generates these meson.build files), but I don't want to break the old build system.
Reordering the directory structure would be a nice solution, but

1. It would be a looooot of work.
2. It would be a biiiiiiiig breaking change, leaving a lot of people very pissed that the old build system no longer works. Such a PR would certainly not be accepted by upstream.

Every solution to this problem is a bad one, but the question is what the least bad solution is.
Possible solutions:

1. Continue using the old build system and not writing meson.build files -> bad, because the old build system is bad
2. Reordering the directory structure -> lots of work and breaks the old build system
3. Using the foreach step : [1,1,1,1,1,1,1,1,1,1,1,1,1,1,0] ... endforeach code: Very hacky and it has very unreadable error messages if you have cyclic dependencies. And I cannot easily improve these error messages, because the meson dsl is not as nice and Turing complete as Python.
4. Writing the 'graph' module and submitting a PR to meson.
5. Don't use the subdir command and instead put all of the static_library(...) commands into root/meson.build. The disadvantages are that this is more messy than having it nicely sorted into subdirs, and it also requires me to write a DAG solver (this DAG solver would be in the python script that generates the meson.build files instead of in meson.)

I am strongly of the opinion that if your build definition is so bizarrely complicated

Do you seriously think that a build is bizarrely complicated, just because of the way files are organized into directories?

that it requires a DAG dependency solver,

I don't want to bash on meson, but I just want to note that ninja, make and nearly every other build system has a DAG dependency resolver.

then the bettersolution is to make your build setup simpler rather than adding this functionality to the build system.

In my case it takes an impractical amount of time to do it and it would break the old build system. Do you seriously think that in a project with 900 k lines of code, "break the old build system and start using another one" is that easy? If both build systems work on the same files, then you can have gradual adoption which is a lot easier.

Of the 5 solutions I suggested above, I think you can only seriously suggest 3., 4. or 5.
I honestly want to hear your opinion, what you would suggest me to do.

[mensinda]

I agree that it would be better to restructure the build system, but not everyone will be willing to do this (especially if you are porting a project to meson). It is already possible to build a DAG solver in meson (see the first comment), hence I would argue that meson already has the base functionality to do this.

The new module basically moves the hacky foreach step : [1,1,1,1,1,1,1,1,1,1,1,1,1,1,0] loop part from the first comment into a module. This way we don't end up with a bunch of bad copy-pasted meson code that solves this problem in a bad way.

Also, using the DAG solver is not trivial, since you have to come up with a system to pass all the kwargs and sources to the correct build type function. This would be far too much overkill for most projects where then manually resolving the dependencies is easier.

So my point is (basically the same argument why we have modules in the first place and do not allow custom functions in meson): We can't prevent people from doing (from our perspective) stupid things if they can already do some hacky loop magic in meson that is duplicated many times (like CMake functions) and will break horribly if you touch it. We can however do it once correctly in meson itself and add a big warning label that you are 99% of the time better of just doing this manually but if you really can't be bothered and would rather copy-paste some hacky meson code, then we have an official module for it.

So could you live with this functionality as a module + some warning labels in the docs?