Adding `expansion.bzl` for Fully Expanding Environment Variables

[CauhxMilloy]

The built-in functionality (exposed Skylark methods on ctx) for expanding environment variables leaves a lot of implementation to do in bzl files. This PR adds in that missing functionality for easy reuse with a new expansion struct. expansion has various methods for expanding environment variables with a flexible API.

The existing APIs handle only one piece at a time:

• ctx.expand_location() only handles $(location ...) (and similar) expansion. It does not handle any "make variable" expansion (no expansion from TemplateVariableInfo or other providers via toolchains).
• ctx.expand_make_variables() only handles make variables. If it encounters $(location ...) (or similar), it errors out with no means of recovery. This method is also marked as deprecated, with ctx.var listed as the preferred API.
• ctx.var is a simple dictionary, which contains resolved mappings based on toolchains. However, being a simple data structure (not a function) leaves recursive functionality and/or integration with ctx.expand_location() to be implemented by hand (or in this PR).

Many internal systems make use of functionality that fully resolves both make variables and $(location ...) (and does so recursively). This is done with ruleContext.getExpander().withDataLocations() (example). However, this is never exposed to skylark. This means that built-in rules will have the env attribute fully expanded, but custom rules cannot (easily).

The above mentioned methods have their own (somewhat duplicated) implementations (ctx.expand_location(), ctx.expand_make_variables(), ctx.var). Note the identical ConfigurationMakeVariableContext initialization here and here -- identical except for the use of additionalSubstitutionsMap, which could have been delegated (similar to the impl of LocationTemplateContext). Also note the separate/duplicated parsing implementations in LocationTemplateContext and in LocationExpander.

This PR tries to avoid more duplicate implementations (which can't really happen anyway; as this is in external Skylark, not Java / Bazel runtime). There is one extra implementation to mention (in cc_helper), used by cc_binary(). This is referenced in Skylark here, and implemented here. This implementation is also not consistent with the above listed Java-based implementations and it is also not accessible/exposed to other bzl files (can't access cc_helper from @rules_cc//). This implementation is done differently, as to allow for all the listed functionality.

PR details:

• These new methods make use of ctx.expand_location() and ctx.var to allow fully recursive variable expansion that incorporates both inputs (toolchains and location).
• The methods avoid copies/string mutations/extra loops when necessary to ensure that the functions can run quickly.
• The methods' API allows for manual/direct data structures (lists/dicts) as input, or for pulling values directly from ctx.
• Supports $VAR, $(VAR), and ${VAR} for variable expansion.
• Rechecks env dict for recursion (not only checking location/toolchains).
• Adds validation logic to check that all (non-escaped) variables have been properly expanded.
• tests/expansion_tests.bzl added to test all added methods.

This PR is being submitted here so that it can be reused (instead of copied in many repos). It is also preferable to add functionality here in Skylib, instead of (or in addition to) any changes in the Bazel repo so that it can be more easily pulled into projects with a pinned Bazel version.

Please feel free to leave comments or suggestion on ways to improve this PR, or let me know if you have any questions. Thanks!

[comius]

Wow, this is one nice PR. It's a shame it's here for 1.5 years.