[lit] Recursively apply substitutions

[ldionne]

Summary

This allows defining substitutions in terms of other substitutions. For
example, a %build substitution could be defined in terms of a %cxx
substitution as '%cxx %s -o %t.exe' and the script would be properly
expanded.

[dexonsmith]

This looks really cool. Can you add tests for this feature, somewhere inside llvm/utils/lit/tests?

llvm/utils/lit/lit/TestRunner.py

1179

I suggest processLineRecursively or processLineToFixedPoint instead of fullyProcessLine, since I don't think the word "fully" is clear.

[dexonsmith]

It would also be good to confirm that this isn't expensive in the normal case (one-level substitutions). Have you timed running the libc++ tests with and without this patch?

[delcypher]

While I can see the appeal of this I need convincing that this actually needed. I see too many downsides

• Possibility of non-termination being introduced that we'll have to check for which is a cost that will have to be paid every time we execute a test.
• Debugging lit substitutions becomes really difficult. Right now I can add a few print statements in the lit.site.cfg files to print out the current substitutions (or ones that interest me) to see what they expand to. With this change that doesn't work anymore because the full expansion happens much later.

The way most test suites handle achieving your end goal is to just have variables that represent the different pieces of a command line and then define the substitution appropriately. E.g.

options = { 
  'asan': '-fsanitize=address',
  'warnings': '-Wall',
  'opt':  '-O0',
  'debug': '-g',
  'cc': '/usr/bin/clang',
}

cc_asan_subst = '{cc} {warnings} {asan} {opt} {debug}'.format(**options)
print(cc_asan_subst)
cc_subst = '{cc} {warnings}  {opt} {debug}'.format(**options)
print(cc_subst)

While not quite as elegant as what this patch proposes it is so much easier to debug. Are you trying to do something that is difficult to express in the lit.site.cfg files?

llvm/utils/lit/lit/TestRunner.py

1181

If processed eventually expands to substitution already processed (e.g. a substitution expands to something containing itself) then this will never terminate. If we are going to have this feature then we should have a check for substitution cycles somewhere because this will just look like a lit hang otherwise.

[ldionne]

In D76178#1922945, @dexonsmith wrote:

This looks really cool. Can you add tests for this feature, somewhere inside llvm/utils/lit/tests?

Yes, I will, I just wanted to gauge interest first!

It would also be good to confirm that this isn't expensive in the normal case (one-level substitutions). Have you timed running the libc++ tests with and without this patch?

I can't see any noticeable difference running the Clang or the libc++ tests -- all differences appear to be noise:

# Clang with patch
real    2m43.026s
user    18m27.649s
sys 16m20.605s

# Libc++ with patch
real    18m46.297s
user    35m22.514s
sys 5m27.994s

# Clang without patch
real    3m6.585s
user    19m26.953s
sys 15m50.688s

# Libc++ without patch
real    18m47.104s
user    35m23.633s
sys 5m29.889s

In D76178#1922990, @delcypher wrote:

While I can see the appeal of this I need convincing that this actually needed. I see too many downsides

• Possibility of non-termination being introduced that we'll have to check for which is a cost that will have to be paid every time we execute a test.

I agree we should check for this, however it's not clear to me this is going to make a noticeable perf difference in practice. The tests we run involve executing processes and doing things that are a lot more expensive than the simple lit substitution, even if we check for non-terminating substitutions. I think it should be possible to make it fairly quick in the usual case where full substitution happens after exactly one substitution.

• Debugging lit substitutions becomes really difficult. Right now I can add a few print statements in the lit.site.cfg files to print out the current substitutions (or ones that interest me) to see what they expand to. With this change that doesn't work anymore because the full expansion happens much later.

I'm not sure I understand. Full expansion after this patch happens at the same point where it does before the patch. The only difference is that when you print substitutions in the lit.site.cfg, you must mentally substitute anything that would normally get re-substituted with this patch. However, if you don't have substitutions that expand into other substitutions, this is moot -- the behavior is the same as today.

The way most test suites handle achieving your end goal is to just have variables that represent the different pieces of a command line and then define the substitution appropriately. E.g.

[...]

While not quite as elegant as what this patch proposes it is so much easier to debug. Are you trying to do something that is difficult to express in the lit.site.cfg files?

Yes, that's indeed what libc++ does. It actually ends up being quite contrived in libc++, and we have a couple substitutions that would benefit from this.

The larger picture of why I got to making this change is that I'm trying to rewrite the libc++/lit integration entirely to make it simpler and more flexible. The way I've done that so far is by defining the libc++ test format right on top of executeShTest, where my test format only expects a few substitutions to be provided in the config object (%cxx, %compile_flags, and a few others), and everything else is defined on top of those substitutions. For example, a .pass.cpp test is one with a script of two steps:

• %cxx %compile_flags %link_flags -o %t.exe %s
• %exec %t.exe

The benefit of approaching it this way is that it's as flexible as what we have today, however it's incredibly easy to extend by tweaking what substitutions you provide in the lit.cfg. For example, if you want a custom executor, just define the %exec substitution to run your custom script, and you don't need to write a hundred lines of Python code that calls subprocess(...). Where recursively expanding substitutions come into the picture is that I define %build on top of %cxx (and others), and I don't have access to the actual thing that %cxx will be substituted for at the point where I define %build. In other words, I'm parameterizing substitutions on top of a set of base substitutions. I've found this to be very powerful and flexible so far.

@delcypher
Is there an interest for moving forward with this change if we check for non-termination without incurring unreasonable cost, or are you not convinced by my use case?

[delcypher]

@ldionne

In D76178#1922990, @delcypher wrote:

While I can see the appeal of this I need convincing that this actually needed. I see too many downsides

• Possibility of non-termination being introduced that we'll have to check for which is a cost that will have to be paid every time we execute a test.

I agree we should check for this, however it's not clear to me this is going to make a noticeable perf difference in practice. The tests we run involve executing processes and doing things that are a lot more expensive than the simple lit substitution, even if we check for non-terminating substitutions. I think it should be possible to make it fairly quick in the usual case where full substitution happens after exactly one substitution.

Testing only for the "usual case" isn't sufficient to cover all situations where infinite recursion might be introduced. It looks lit actually supports regex substitutions (which I didn't even know it supported). That makes checking for cycles even harder. Maybe a low default recursion depth would be the solution here?

• Debugging lit substitutions becomes really difficult. Right now I can add a few print statements in the lit.site.cfg files to print out the current substitutions (or ones that interest me) to see what they expand to. With this change that doesn't work anymore because the full expansion happens much later.

I'm not sure I understand. Full expansion after this patch happens at the same point where it does before the patch. The only difference is that when you print substitutions in the lit.site.cfg, you must mentally substitute anything that would normally get re-substituted with this patch. However, if you don't have substitutions that expand into other substitutions, this is moot -- the behavior is the same as today.

Let me give you a concrete example to illustrate the point. You can add a line like this to a lit config

import pprint
lit_config.fatal('Substitutions: {}'.format(pprint.pformat(config.substitutions)))

For ASan's x86_64 test suite for %clang you'll see something like this printed out.

('%clang ',
  '   /Volumes/data/dev/llvm/monorepo_upstream/master/builds/RelWithDebInfo/./bin/clang   -arch x86_64 -stdlib=libc++ -mmacosx-version-min=10.10 -isysroot /Volumes/data/xc/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.15.sdk  ')

Doing this is a very useful way to inspect what %clang will expand to.

Your change will break this because now people can do something like this in the their lit config.

config.substitutions.add( ('%clang', '%cc %arch %warnings %sysroot'))

and so when you try to inspect the substitution in the lit.cfg using the technique I described above we would see.

('%clang', '%cc %arch %warnings %sysroot')

Printing the above out isn't anywhere near as useful as the full expanded version that we get today. One way I see around that is providing a convenience API that can be called in lit.cfg files that can expand an arbitrary string based on the current set of substitutions.

The way most test suites handle achieving your end goal is to just have variables that represent the different pieces of a command line and then define the substitution appropriately. E.g.

[...]

While not quite as elegant as what this patch proposes it is so much easier to debug. Are you trying to do something that is difficult to express in the lit.site.cfg files?

Yes, that's indeed what libc++ does. It actually ends up being quite contrived in libc++, and we have a couple substitutions that would benefit from this.

And the full power of python isn't enough to come up with some nice syntactic sugar?

The larger picture of why I got to making this change is that I'm trying to rewrite the libc++/lit integration entirely to make it simpler and more flexible. The way I've done that so far is by defining the libc++ test format right on top of executeShTest, where my test format only expects a few substitutions to be provided in the config object (%cxx, %compile_flags, and a few others), and everything else is defined on top of those substitutions. For example, a .pass.cpp test is one with a script of two steps:

• %cxx %compile_flags %link_flags -o %t.exe %s
• %exec %t.exe

Side note: If you're rewriting the test suite now would be a good opportunity to avoid a mistake made in the past. Lit substitutions don't handle the case where a substitution is a prefix of another (e.g. %clang and %clang_asan, the resolution is dependent on the order the substitutions are defined). You could avoid this by writing your substitutions with an end delimiter (e.g. %clang% and %clang_asan%).

The benefit of approaching it this way is that it's as flexible as what we have today, however it's incredibly easy to extend by tweaking what substitutions you provide in the lit.cfg. For example, if you want a custom executor, just define the %exec substitution to run your custom script, and you don't need to write a hundred lines of Python code that calls subprocess(...). Where recursively expanding substitutions come into the picture is that I define %build on top of %cxx (and others), and I don't have access to the actual thing that %cxx will be substituted for at the point where I define %build. In other words, I'm parameterizing substitutions on top of a set of base substitutions. I've found this to be very powerful and flexible so far.

Why do you need to create your own test format to achieve your goals? Everything you've described so far is achievable with lit and a suitable lit.cfg file today.

One use case I could imagine is the case where you want to run similar variants of the same test by expanding a substitution differently (e.g. same test script except do one at -O0 and one at -O3). This is something lit is not good at and I imagine your change could be a useful stepping stone to fix this.

@delcypher
Is there an interest for moving forward with this change if we check for non-termination without incurring unreasonable cost, or are you not convinced by my use case?

I'm not entirely convinced by your use case but I do see the appeal of the feature. What I want is to make sure this feature is not added in a form where

• It's easy to shoot yourself in the foot (with infinite recursion).
• It's very difficult to debug when things go wrong.
• The feature isn't documented.

If you can fix those problems then I'm not opposed to this. My suggestions would be.

1. Have a recursion limit for substitution expansion. This could be a property of the test suite and could have a low default. If we hit the recursion limit and a further expansion would return a different string ("one more expansion check") then we should fail the test. You might need a new test failure type here. If we made the default recursion limit 0 then we could special case this by not doing the "one more expansion check". This would actually mean that only test suites that opt into recursive lit substitution expansion have to pay the cost to perform checks.
2. Introduce an api usable from lit.cfg files that can expand substitutions recursively. Include a test that actually uses it.
3. If time permits some documentation would be useful. Failing that proper tests that exercise everything you're adding will have to do.

[ldionne]

In D76178#1928073, @delcypher wrote:

@ldionne

In D76178#1922990, @delcypher wrote:

While I can see the appeal of this I need convincing that this actually needed. I see too many downsides

• Possibility of non-termination being introduced that we'll have to check for which is a cost that will have to be paid every time we execute a test.

I agree we should check for this, however it's not clear to me this is going to make a noticeable perf difference in practice. The tests we run involve executing processes and doing things that are a lot more expensive than the simple lit substitution, even if we check for non-terminating substitutions. I think it should be possible to make it fairly quick in the usual case where full substitution happens after exactly one substitution.

Testing only for the "usual case" isn't sufficient to cover all situations where infinite recursion might be introduced. It looks lit actually supports regex substitutions (which I didn't even know it supported). That makes checking for cycles even harder. Maybe a low default recursion depth would be the solution here?

Yeah, a low recursion maximum also appears like the simplest and cleanest solution to me. Concretely, I think it should rarely happen, and it's always obviously a programmer error in the lit.cfg. A max recursion depth would ensure that the programmer finds that problem quickly and simply.

Doing this is a very useful way to inspect what %clang will expand to.

Your change will break this because now people can do something like this in the their lit config.

config.substitutions.add( ('%clang', '%cc %arch %warnings %sysroot'))

[Sorry, the first shot was sent with some keyboard shortcut when I was right here]

I frankly think that this should be for the author of the lit.cfg to handle, not for lit to enforce by limiting its functionality. But as you say below, I agree lit could have a convenience API to expand substitutions to allow people to print them.

Side note: If you're rewriting the test suite now would be a good opportunity to avoid a mistake made in the past. Lit substitutions don't handle the case where a substitution is a prefix of another (e.g. %clang and %clang_asan, the resolution is dependent on the order the substitutions are defined).

Nice, I didn't know that. I don't get to redefine the substitutions, however, cause those are the ones of the existing libc++ test suite.

Why do you need to create your own test format to achieve your goals? Everything you've described so far is achievable with lit and a suitable lit.cfg file today.

I don't think it is possible to inject custom commands in front of a .sh.cpp without creating a custom test format. But regardless, a custom test format is a nice place to encapsulate that logic.

I'm not entirely convinced by your use case but I do see the appeal of the feature. What I want is to make sure this feature is not added in a form where

• It's easy to shoot yourself in the foot (with infinite recursion).

A max recursion depth will handle that.

• It's very difficult to debug when things go wrong.

I'll look into providing a convenience API to print expanded substitutions, but even then I don't believe this should be sufficient to hold off the change, since you can always avoid using the feature if for some reason you find it too complicated.

• The feature isn't documented.

Where can I document it? I'm happy to do that.

If you can fix those problems then I'm not opposed to this. My suggestions would be.

I'll look into those, thanks for the feedback!

[delcypher]

@ldionne

• The feature isn't documented.

Where can I document it? I'm happy to do that.

I would suggest here: https://llvm.org/docs/CommandGuide/lit.html

There is no documentation on lit.site.cfg files here which is very sad. I'd suggest you add a section about them but just document the functionality you're adding. We can expand on this documentation at a later date.

[ldionne]

Address review comments:

• Add tests
• Add documentation
• Make the feature opt-in
• Only expand up to some recursion limit

[delcypher]

llvm/docs/CommandGuide/lit.rst

461

Maybe mention what it can be set to (i.e. valid range?)

llvm/utils/lit/lit/LitConfig.py

30

Maybe make the default 0 so it's clearer what the type is supposed to be?

69

Maybe use an @property wrapper like for maxIndividualTestTime and do some validation in the setter so using an incorrect type or value is caught quickly.

llvm/utils/lit/lit/TestRunner.py

1189

I don't think we should raise an exception here because I think that means we'd loose the results of all other tests. We should fail the test with an appropriate message.

llvm/utils/lit/tests/unit/TestRunner.py

251

What does -1 as a limit mean? If I've read the code correctly any value <= 0 will have the same effect so why even allow negative values?

[ldionne]

Address review comments

llvm/utils/lit/lit/LitConfig.py

30

None and 0 are different -- None means no recursive substitution is attempted, and 0 means that recursive substitution is attempted up to 0 steps. But in the 0 case, it's still an error if there are unexpanded substitutions left after 0 recursive steps.

llvm/utils/lit/lit/TestRunner.py

1189

No, we don't lose the results of the other tests. Throwing an exception here results in the test being UNRESOLVED, which I believe is what we want.

llvm/utils/lit/tests/unit/TestRunner.py

251

Disallowed now!

[delcypher]

@ldionne Thanks for addressing my comments. The patch looks like its in very good shape. I have a minor nit about the documentation. Other than that LGTM.

llvm/docs/CommandGuide/lit.rst

461

Thanks. This documents what happens if recursiveExpansionLimit > 0. However we also allow recursiveExpansionLimit == 0. As you pointed out there is a difference between recursiveExpansionLimit being None and being equal to 0. Could you document that here?

llvm/utils/lit/lit/LitConfig.py

30

Ah okay. I hadn't noticed that difference. I've a left a comment elsewhere in the review that we should document this.

69

Thanks for fixing this.

llvm/utils/lit/lit/TestRunner.py

1189

Ah I didn't realise that. Now that I've looked closer I see you have a test for this. Awesome!

[ldionne]

Fix documentation per review comments.

[ldionne]

I addressed review comments, so this should be good to go!

[delcypher]

LGTM.

[jdenny]

Sorry to be late to this review....

This allows defining substitutions in terms of other substitutions. For
example, a %build substitution could be defined in terms of a %cxx
substitution as '%cxx %s -o %t.exe' and the script would be properly
expanded.

@ldionne : Thanks for working on this. Howver, as one of the test cases added by this patch suggests, the above example is already supported if %build appears earlier in the list of substitutions than %cxx. For example, llvm/utils/lit/tests/lit.cfg defines %{lit} in terms of %{python}. There's no need to think about infinite recursion or recursion limits. Instead, you have to think about the search-and-replace order.

Could you please explain a bit why the above behavior is not sufficient for your use case? I'm not necessarily arguing against this patch, but I'd like to better understand its motivation.

By default, substitutions are expanded exactly once, so that if e.g. a
substitution ``%build`` is defined in top of another substitution ``%cxx``,
``%build`` will expand to ``%cxx`` textually, not to what ``%cxx`` expands to.
However, if the ``recursiveExpansionLimit`` property of the ``LitConfig`` is
set to a non-negative integer, substitutions will be expanded recursively until
that limit is reached. It is an error if the limit is reached and expanding
substitutions again would yield a different result.

As a result of the existing behavior, the above documentation is not accurate, and neither is the name recursiveExpansionLimit. That is, if you append substitutions in the order of the recursion levels, recursiveExpansionLimit=0 permits any number of recursion levels in the substitution definitions. A name like expansionPassLimit would be more accurate.

An advantage of this patch over the existing behavior would appear to be that substitution definition order no longer matters. Actually, it does matter because changing the order can affect the required value of recursiveExpansionLimit. Generally, test authors shouldn't have to think about the number of levels of recursion. To ease the maintenance burdern as substitution definitions evolve, perhaps the documentation should say that choosing large values (say, multiples of 100) even when small, more exact values are sufficient is preferable and incurs zero performance penalty (as long as definitions are not infinitely recursive).

[ldionne]

In D76178#1950099, @jdenny wrote:

Sorry to be late to this review....

This allows defining substitutions in terms of other substitutions. For
example, a %build substitution could be defined in terms of a %cxx
substitution as '%cxx %s -o %t.exe' and the script would be properly
expanded.

[...]

An advantage of this patch over the existing behavior would appear to be that substitution definition order no longer matters. Actually, it does matter because changing the order can affect the required value of recursiveExpansionLimit. Generally, test authors shouldn't have to think about the number of levels of recursion. To ease the maintenance burdern as substitution definitions evolve, perhaps the documentation should say that choosing large values (say, multiples of 100) even when small, more exact values are sufficient is preferable and incurs zero performance penalty (as long as definitions are not infinitely recursive).

You're right that if one sets up substitutions in the correct order (and assuming no circular dependencies), a single pass is sufficient to expand substitutions. However, the problem is precisely that one usually doesn't have control over the order in which substitutions are set up, and frankly I don't think it should matter. In the current state of things, the order in which substitutions are performed is essentially an implementation detail, and I believe it should stay that way unless we can provide a reasonable way for users to control it.

Given that, what we could do instead is switch the implementation from doing multiple passes to doing a topological sort of the substitutions based on whether a substitution is required by another one. The recursiveExpansionLimit would then become a boolean like orderSubstitutionsSomething. It would be an error if no linearization can be found, i.e. if there's a dependency cycle in substitutions. Note that it would still have to be opt-in, because some test suites use patterns without delimiters and they (almost certainly unknowingly) rely on the fact that their substitutions happen to be processed in a specific order.

I thought about this and I both couldn't find an implementation of topological sort in the Python Standard Library, and also thought that solution was overkill. Please let me know if you think that direction should be explored, and I'll research it some. However, let's not revert this because the feature is useful in its current state and the libc++ test suite needs it -- if we switch to a topo sort the usage will be mostly the same so it'll be easy to change libc++ at the same time.

[jdenny]

In D76178#1950193, @ldionne wrote:

You're right that if one sets up substitutions in the correct order (and assuming no circular dependencies), a single pass is sufficient to expand substitutions. However, the problem is precisely that one usually doesn't have control over the order in which substitutions are set up,

When does this problem occur? So far, I've found I had sufficient control, but I probably haven't tried to do what you have.

and frankly I don't think it should matter.

I agree it's messy.

Given that, what we could do instead is switch the implementation from doing multiple passes to doing a topological sort of the substitutions based on whether a substitution is required by another one. The recursiveExpansionLimit would then become a boolean like orderSubstitutionsSomething. It would be an error if no linearization can be found, i.e. if there's a dependency cycle in substitutions.

Are we sure there's no case where the result of a substitution combines with neighboring text (perhaps from another substitution) to form a new substitution?

If not, then it should be straight-forward to recursively expand a substitution upon its first occurrence and cache results for it and for any nested substitutions. Two new arrays would be needed: one for the full expansions (None until first occurrence) and one for marks to detect infinite recursion. This seems efficient.

To avoid accidentally permitting substitutions to combine with neighboring text to form a new substitution, it is probably worthwhile to split the string up to avoid searching previously substituted text while searching for other substitutions.

Note that it would still have to be opt-in, because some test suites use patterns without delimiters and they (almost certainly unknowingly) rely on the fact that their substitutions happen to be processed in a specific order.

One issue is that of prefixing, such as %foo vs. %foo-bar. I believe lit would still just process those in the order defined, and there wouldn't be backward-compatibility issues. Ideally, lit would have a longest-match mode that test suites would eventually adopt, but a backward-compatible first-match mode might have to be the default at first.

The issue I mentioned above, where substitutions might combine with neighboring text, might require this feature to be opt-in.

I thought about this and I both couldn't find an implementation of topological sort in the Python Standard Library,

If Python offers something helpful, then great, but the algorithm I mentioned above seems straight-forward. Is it harder than I think?

and also thought that solution was overkill. Please let me know if you think that direction should be explored, and I'll research it some

I need a better understanding of the use case to respond to this.

However, let's not revert this because the feature is useful in its current state and the libc++ test suite needs it -- if we switch to a topo sort the usage will be mostly the same so it'll be easy to change libc++ at the same time.

In the short term, I think the documentation could be improved, in the ways I pointed out in my last comment.

In the long term, I'm hoping for a more complete solution.

Thanks for working on this. I agree lit substitutions could be cleaner.

[yln]

My feedback (also sent via email):

We are now defining two different modes of execution, which I think could be a source of confusion.

If I read it right, then the main concerns w.r.t. this feature are:

1. Possibility of non-termination (currently mitigated via recursion limit)
2. Performance
3. Complicates debugging

I think all of these can be addressed/mitigated:

1. Non-termination can be solved in a more principled way (by sorting substitutions or another similar algorithm).

2. I don't think performance will be an issue, but let's measure to make sure. Louis already timed a complete run for libc++. In addition, we can measure env LIT_OPTS=--no-execute ninja check-all. --no-execute skips executing the actual tests, so we should get a good sense of lit overhead.

3. Debugging is a valid concern I think, especially because it doesn't have a purely technical solution. However, IMO it has been given too much weight. Let me try to explain my thoughts: the person doing the debugging is either aware of recursive expansion of substitutions or they aren't. If you don't know what to look for, i.e., you don't know that your are in the "recursive expansion" mode, there is not much we can help with. This can always happen and is even more insidious exactly because we have two different modes. For experts, we can provide an ergonomic debugging helper, e.g., print(config.expand('%clang')).

On the other hand, the configuration option adds complexity:
We had a long discussion where it should reside (I do think TestingConfig is the right place) and the infrastructure for the mode is almost as much code as the feature itself. Not making this a configuration option sidesteps these issues.
Also, complexity tends to accumulate over time. A good "bad example" from the past: individual test timeouts, which sounds like a small, innocent feature. We now have maxIndividualTestTimeIsSupported which has a special implementation for AIX! (https://reviews.llvm.org/D64251)

Since (1, 2) have a purely technical solution, and (3) the "debuggability" argument is messy IMO (introducing separate modes has it's own downsides), I vote for not making this configurable at all.

I talked to Louis. He proposed the following plan and is willing to the work:

1. Implement longest-match matching of substitutions (this is a useful improvement in itself)
2. Address non-termination in a more principled way (by sorting substitutions or another similar algorithm)
3. Measure performance
4. Provide ergonomic helper to print expanded substitutions to aid debugging
5. Remove option in the config, turn on by default

My thoughts on related issues:

Prefix matching
E.g, %clang_asan expanding for %clang, two solutions:

1. Use unique identifier, e.g., %{clang} or %clang%
2. Implement longest match

I prefer 2), because again it's a technical solution, while 2) is more convention-based (human) and would require a lot of changes to widely adopt.

Ordering of substitutions
I think the order of substitutions should not matter. IMO, this is just another source of confusion.
Ideally substitutions would be a dictionary (unique keys) instead of a list of tuples.

[jdenny]

@yln : I definitely like the goals you describe. I don't have a good feel for how many test suites will require adjustments to work correctly with rules like longest match, but they'll be easier to understand if they do.

[ldionne]

I'm revisiting this now. Comments below.

In D76178#1970410, @yln wrote:

My feedback (also sent via email):

I talked to Louis. He proposed the following plan and is willing to the work:

1. Implement longest-match matching of substitutions (this is a useful improvement in itself)
2. Address non-termination in a more principled way (by sorting substitutions or another similar algorithm)
3. Measure performance
4. Provide ergonomic helper to print expanded substitutions to aid debugging
5. Remove option in the config, turn on by default

Now that I'm looking at the changes required, and after letting this sleep for some time, I think it might be reasonable to short circuit some of this. What I'd propose is:

1. Always sort the substitutions in reverse order of length, i.e.%clang_exe will always be processed before %clang. This is a simple and efficient way to implement longest-match.
2. Always process substitutions recursively, up to a fixed point or some arbitrary depth. I suggest something like 50.
3. Remove the option in the config.

All these steps would have to be performed at once, though, since reordering the substitutions in (1) requires processing them recursively. I tried otherwise and some test suites do use recursive substitutions by ordering the substitutions in a way that it works, which would be broken if we do (1) in isolation. I think it might be possible to do these step-by-step, but at a significant cost in complexity especially for implementing longest-match.

I looked into addressing non-termination in a more principled way, and the issue is that doing it properly requires figuring out the dependencies between substitutions, which is equivalent to building a graph where nodes are substitution-keys and edges represent the is contained in the result of substituting relationship. The topological sort of this graph, if it exists, is the order in which we should apply the substitutions. If no such ordering exists, there's a cycle and we should error out. There are two problems with that:

1. It's fairly involved to build that graph: I'd ballpark O(n^2) since for each substitution, we need to examine all other substitutions to see whether they depend on it. And then we need to sort the substitutions based on that graph representation, which is also not free. I'm concerned that it would be less efficient than just processing substitutions until a fixed point. One should keep in mind that cycles should never happen (they are basically a programmer error when setting up the test suite), and the fixed point should be reached after only a few passes in almost all cases.
2. The sort required for longest-match and the one for recursive substitutions might not agree. For example, consider the following set of substitutions: [('%clang_exe', '/usr/bin/c++'), ('%clang', '%clang_exe')]. The recursive substitution sort tells us to apply %clang before %clang_exe, but the longest-match consideration would require that we do the opposite. I can't think of a way to satisfy both these criteria.

So, if you think my reasoning makes sense, the algorithm for substitutions would be:

1. Sort substitutions in reverse order of length (to avoid unexpected substitution in the prefix of other substitutions)
2. Apply substitutions in order until a fixed point is encountered, or N steps have been performed. I suggest N=50 or something along those lines -- we should strive to use a value of N that will make all legitimate uses we can think of work, while still catching a cyclic substitution eventually.

It's a simple and fairly efficient algorithm, given that in most cases just one or two passes would be required (i.e. in the best case, it's equivalent to not having recursive substitutions at all). WDYT?

[yln]

I think this is a great plan! I am not too worried about performance in this case, but I am always a fan for keeping things simple. Doing things at once is justified IMO.
@jdenny also has provided a lot of good feedback for me.

2. The sort required for longest-match and the one for recursive substitutions might not agree. For example, consider the following set of substitutions: [('%clang_exe', '/usr/bin/c++'), ('%clang', '%clang_exe')]. The recursive substitution sort tells us to apply %clang before %clang_exe, but the longest-match consideration would require that we do the opposite. I can't think of a way to satisfy both these criteria.

This is the only part that I am not completely following. Are there any situations for which the recursive order is preferable? In this example, wouldn't substituting %clang first result in infinite recursion?

llvm/docs/CommandGuide/lit.rst

 --- the root of this configuration chain will always be a test suite.  Once the
 test configuration is cloned :program:`lit` checks for a *lit.local.cfg* file
 in the subdirectory.  If present, this file will be loaded and can be used to
 specialize the configuration for each individual directory.  This facility can
 be used to define subdirectories of optional tests, or to change other
 configuration parameters --- for example, to change the test format, or the
 suffixes which identify test files.
 
-PRE-DEFINED SUBSTITUTIONS
-~~~~~~~~~~~~~~~~~~~~~~~~~~
+SUBSTITUTIONS
+~~~~~~~~~~~~~
 
-:program:`lit` provides various patterns that can be used with the RUN command.
-These are defined in TestRunner.py. The base set of substitutions are:
+:program:`lit` allows patterns to be substituted inside RUN commands. It also
+provides the following base set of substitutions, which are defined in
+TestRunner.py:
 
  ======================= ==============
   Macro                   Substitution
  ======================= ==============
  %s                      source path (path to the file currently being run)
  %S                      source dir (directory of the file currently being run)
  %p                      same as %S
  %{pathsep}              path separator

  %:T                     On Windows, %/T but a ``:`` is removed if its the second character.
                          Otherwise, %T but with a single leading ``/`` removed.
  ======================= ==============
 
 Other substitutions are provided that are variations on this base set and
 further substitution patterns can be defined by each test module. See the
 modules :ref:`local-configuration-files`.
 
+By default, substitutions are expanded exactly once, so that if e.g. a
+substitution ``%build`` is defined in top of another substitution ``%cxx``,
+``%build`` will expand to ``%cxx`` textually, not to what ``%cxx`` expands to.
+However, if the ``recursiveExpansionLimit`` property of the ``LitConfig`` is
+set to a non-negative integer, substitutions will be expanded recursively until
+that limit is reached. It is an error if the limit is reached and expanding
+substitutions again would yield a different result.
+
 More detailed information on substitutions can be found in the
 :doc:`../TestingGuide`.
 
 TEST RUN OUTPUT FORMAT
 ~~~~~~~~~~~~~~~~~~~~~~
 
 The :program:`lit` output for a test run conforms to the following schema, in
 both short and verbose modes (although in short mode no PASS lines will be

llvm/utils/lit/lit/LitConfig.py

class LitConfig(object):
 
     def __init__(self, progname, path, quiet,
                  useValgrind, valgrindLeakCheck, valgrindArgs,
                  noExecute, debug, isWindows,
                  params, config_prefix = None,
                  maxIndividualTestTime = 0,
                  parallelism_groups = {},
                  echo_all_commands = False):
         # The name of the test runner.
         self.progname = progname
         # The items to add to the PATH environment variable.
         self.path = [str(p) for p in path]
         self.quiet = bool(quiet)
         self.useValgrind = bool(useValgrind)
         self.valgrindLeakCheck = bool(valgrindLeakCheck)
         self.valgrindUserArgs = list(valgrindArgs)
         self.noExecute = noExecute
def __init__(self, progname, path, quiet,
             else:
                 # The default is 'summary'.
                 self.valgrindArgs.append('--leak-check=no')
             self.valgrindArgs.extend(self.valgrindUserArgs)
 
         self.maxIndividualTestTime = maxIndividualTestTime
         self.parallelism_groups = parallelism_groups
         self.echo_all_commands = echo_all_commands
+        self._recursiveExpansionLimit = None
+
+    @property
+    def recursiveExpansionLimit(self):
+        return self._recursiveExpansionLimit
+
+    @recursiveExpansionLimit.setter
+    def recursiveExpansionLimit(self, value):
+        if value is not None and not isinstance(value, int):
+            self.fatal('recursiveExpansionLimit must be either None or an integer (got <{}>)'.format(value))
+        if isinstance(value, int) and value < 0:
+            self.fatal('recursiveExpansionLimit must be a non-negative integer (got <{}>)'.format(value))
+        self._recursiveExpansionLimit = value
 
     @property
     def maxIndividualTestTime(self):
         """
             Interface for getting maximum time to spend executing
             a single test
         """
         return self._maxIndividualTestTime

llvm/utils/lit/lit/TestRunner.py

def memoized(x):
             cache[x] = f(x)
         return cache[x]
     return memoized
 
 @_memoize
 def _caching_re_compile(r):
     return re.compile(r)
 
-def applySubstitutions(script, substitutions):
-    """Apply substitutions to the script.  Allow full regular expression syntax.
+def applySubstitutions(script, substitutions, recursion_limit=None):
+    """
+    Apply substitutions to the script.  Allow full regular expression syntax.
     Replace each matching occurrence of regular expression pattern a with
-    substitution b in line ln."""
+    substitution b in line ln.
+
+    If a substitution expands into another substitution, it is expanded
+    recursively until the line has no more expandable substitutions. If
+    the line can still can be substituted after being substituted
+    `recursion_limit` times, it is an error. If the `recursion_limit` is
+    `None` (the default), no recursive substitution is performed at all.
+    """
     def processLine(ln):
         # Apply substitutions
         for a,b in substitutions:
             if kIsWindows:
                 b = b.replace("\\","\\\\")
             # re.compile() has a built-in LRU cache with 512 entries. In some
             # test suites lit ends up thrashing that cache, which made e.g.
             # check-llvm run 50% slower.  Use an explicit, unbounded cache
             # to prevent that from happening.  Since lit is fairly
             # short-lived, since the set of substitutions is fairly small, and
             # since thrashing has such bad consequences, not bounding the cache
             # seems reasonable.
             ln = _caching_re_compile(a).sub(b, ln)
 
         # Strip the trailing newline and any extra whitespace.
         return ln.strip()
+
+    def processLineToFixedPoint(ln):
+        assert isinstance(recursion_limit, int) and recursion_limit >= 0
+        origLine = ln
+        steps = 0
+        processed = processLine(ln)
+        while processed != ln and steps < recursion_limit:
+            ln = processed
+            processed = processLine(ln)
+            steps += 1
+
+        if processed != ln:
+            raise ValueError("Recursive substitution of '%s' did not complete "
+                             "in the provided recursion limit (%s)" % \
+                             (origLine, recursion_limit))
+
+        return processed
+
     # Note Python 3 map() gives an iterator rather than a list so explicitly
     # convert to list before returning.
-    return list(map(processLine, script))
+    process = processLine if recursion_limit is None else processLineToFixedPoint
+    return list(map(process, script))
 
 
 class ParserKind(object):
     """
     An enumeration representing the style of an integrated test keyword or
     command.
 
     TAG: A keyword taking no value. Ex 'END.'
def executeShTest(test, litConfig, useExternalSh,
 
     if litConfig.noExecute:
         return lit.Test.Result(Test.PASS)
 
     tmpDir, tmpBase = getTempPaths(test)
     substitutions = list(extra_substitutions)
     substitutions += getDefaultSubstitutions(test, tmpDir, tmpBase,
                                              normalize_slashes=useExternalSh)
-    script = applySubstitutions(script, substitutions)
+    script = applySubstitutions(script, substitutions,
+                                recursion_limit=litConfig.recursiveExpansionLimit)
 
     # Re-run failed tests up to test.allowed_retries times.
     attempts = test.allowed_retries + 1
     for i in range(attempts):
         res = _runShTest(test, litConfig, useExternalSh, script, tmpBase)
         if res.code != Test.FAIL:
             break
     # If we had to run the test more than once, count it as a flaky pass. These
     # will be printed separately in the test summary.
     if i > 0 and res.code == Test.PASS:
         res.code = Test.FLAKYPASS
     return res

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/does-not-substitute-no-limit/lit.cfg

+import lit.formats
+config.name = 'does-not-substitute-no-limit'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+config.substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                        ("%rec3", "%rec2"), ("%rec4", "%rec3"),
+                        ("%rec5", "%rec4")]

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/does-not-substitute-no-limit/test.py

+# RUN: echo %rec5

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/does-not-substitute-within-limit/lit.cfg

+import lit.formats
+config.name = 'does-not-substitute-within-limit'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+config.substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                        ("%rec3", "%rec2"), ("%rec4", "%rec3"),
+                        ("%rec5", "%rec4")]
+
+lit_config.recursiveExpansionLimit = 2

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/does-not-substitute-within-limit/test.py

+# RUN: echo %rec5

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/negative-integer/lit.cfg

+import lit.formats
+config.name = 'negative-integer'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+lit_config.recursiveExpansionLimit = -4

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/negative-integer/test.py

+# RUN: true

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/not-an-integer/lit.cfg

+import lit.formats
+config.name = 'not-an-integer'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+lit_config.recursiveExpansionLimit = "not-an-integer"

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/not-an-integer/test.py

+# RUN: true

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/set-to-none/lit.cfg

+import lit.formats
+config.name = 'set-to-none'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+lit_config.recursiveExpansionLimit = None

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/set-to-none/test.py

+# RUN: true

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/substitutes-within-limit/lit.cfg

+import lit.formats
+config.name = 'substitutes-within-limit'
+config.suffixes = ['.py']
+config.test_format = lit.formats.ShTest()
+config.test_source_root = None
+config.test_exec_root = None
+
+config.substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                        ("%rec3", "%rec2"), ("%rec4", "%rec3"),
+                        ("%rec5", "%rec4")]
+
+lit_config.recursiveExpansionLimit = 5

llvm/utils/lit/tests/Inputs/shtest-recursive-substitution/substitutes-within-limit/test.py

+# RUN: echo %rec5

llvm/utils/lit/tests/shtest-recursive-substitution.py

+# Check that the config.recursiveExpansionLimit is picked up and will cause
+# lit substitutions to be expanded recursively.
+
+# RUN: %{lit} -j 1 %{inputs}/shtest-recursive-substitution/substitutes-within-limit --show-all | FileCheck --check-prefix=CHECK-TEST1 %s
+# CHECK-TEST1: PASS: substitutes-within-limit :: test.py
+# CHECK-TEST1: $ "echo" "STOP"
+
+# RUN: not %{lit} -j 1 %{inputs}/shtest-recursive-substitution/does-not-substitute-within-limit --show-all | FileCheck --check-prefix=CHECK-TEST2 %s
+# CHECK-TEST2: UNRESOLVED: does-not-substitute-within-limit :: test.py
+# CHECK-TEST2: ValueError: Recursive substitution of
+
+# RUN: %{lit} -j 1 %{inputs}/shtest-recursive-substitution/does-not-substitute-no-limit --show-all | FileCheck --check-prefix=CHECK-TEST3 %s
+# CHECK-TEST3: PASS: does-not-substitute-no-limit :: test.py
+# CHECK-TEST3: $ "echo" "%rec4"
+
+# RUN: not %{lit} -j 1 %{inputs}/shtest-recursive-substitution/not-an-integer --show-all 2>&1 | FileCheck --check-prefix=CHECK-TEST4 %s
+# CHECK-TEST4: recursiveExpansionLimit must be either None or an integer
+
+# RUN: not %{lit} -j 1 %{inputs}/shtest-recursive-substitution/negative-integer --show-all 2>&1 | FileCheck --check-prefix=CHECK-TEST5 %s
+# CHECK-TEST5: recursiveExpansionLimit must be a non-negative integer
+
+# RUN: %{lit} -j 1 %{inputs}/shtest-recursive-substitution/set-to-none --show-all | FileCheck --check-prefix=CHECK-TEST6 %s
+# CHECK-TEST6: PASS: set-to-none :: test.py

llvm/utils/lit/tests/unit/TestRunner.py

def test_bad_keywords(self):
             IntegratedTestKeywordParser("CUSTOM_NO_PARSER:",
                                         ParserKind.CUSTOM),
             self.fail("CUSTOM_NO_PARSER: failed to raise an exception")
         except ValueError as e:
             pass
         except BaseException as e:
             self.fail("CUSTOM_NO_PARSER: raised the wrong exception: %r" % e)
 
+class TestApplySubtitutions(unittest.TestCase):
+    def test_simple(self):
+        script = ["echo %bar"]
+        substitutions = [("%bar", "hello")]
+        result = lit.TestRunner.applySubstitutions(script, substitutions)
+        self.assertEqual(result, ["echo hello"])
+
+    def test_multiple_substitutions(self):
+        script = ["echo %bar %baz"]
+        substitutions = [("%bar", "hello"),
+                         ("%baz", "world"),
+                         ("%useless", "shouldnt expand")]
+        result = lit.TestRunner.applySubstitutions(script, substitutions)
+        self.assertEqual(result, ["echo hello world"])
+
+    def test_multiple_script_lines(self):
+        script = ["%cxx %compile_flags -c -o %t.o",
+                  "%cxx %link_flags %t.o -o %t.exe"]
+        substitutions = [("%cxx", "clang++"),
+                         ("%compile_flags", "-std=c++11 -O3"),
+                         ("%link_flags", "-lc++")]
+        result = lit.TestRunner.applySubstitutions(script, substitutions)
+        self.assertEqual(result, ["clang++ -std=c++11 -O3 -c -o %t.o",
+                                  "clang++ -lc++ %t.o -o %t.exe"])
+
+    def test_recursive_substitution_real(self):
+        script = ["%build %s"]
+        substitutions = [("%cxx", "clang++"),
+                         ("%compile_flags", "-std=c++11 -O3"),
+                         ("%link_flags", "-lc++"),
+                         ("%build", "%cxx %compile_flags %link_flags %s -o %t.exe")]
+        result = lit.TestRunner.applySubstitutions(script, substitutions, recursion_limit=3)
+        self.assertEqual(result, ["clang++ -std=c++11 -O3 -lc++ %s -o %t.exe %s"])
+
+    def test_recursive_substitution_limit(self):
+        script = ["%rec5"]
+        # Make sure the substitutions are not in an order where the global
+        # substitution would appear to be recursive just because they are
+        # processed in the right order.
+        substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                         ("%rec3", "%rec2"), ("%rec4", "%rec3"), ("%rec5", "%rec4")]
+        for limit in [5, 6, 7]:
+            result = lit.TestRunner.applySubstitutions(script, substitutions, recursion_limit=limit)
+            self.assertEqual(result, ["STOP"])
+
+    def test_recursive_substitution_limit_exceeded(self):
+        script = ["%rec5"]
+        substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                         ("%rec3", "%rec2"), ("%rec4", "%rec3"), ("%rec5", "%rec4")]
+        for limit in [0, 1, 2, 3, 4]:
+            try:
+                lit.TestRunner.applySubstitutions(script, substitutions, recursion_limit=limit)
+                self.fail("applySubstitutions should have raised an exception")
+            except ValueError:
+                pass
+
+    def test_recursive_substitution_invalid_value(self):
+        script = ["%rec5"]
+        substitutions = [("%rec1", "STOP"), ("%rec2", "%rec1"),
+                         ("%rec3", "%rec2"), ("%rec4", "%rec3"), ("%rec5", "%rec4")]
+        for limit in [-1, -2, -3, "foo"]:
+            try:
+                lit.TestRunner.applySubstitutions(script, substitutions, recursion_limit=limit)
+                self.fail("applySubstitutions should have raised an exception")
+            except AssertionError:
+                pass
+
+
 if __name__ == '__main__':
     TestIntegratedTestKeywordParser.load_keyword_parser_lit_tests()
     unittest.main(verbosity=2)