A walk can start from multiple roots, so making the Ancestors and
Descendents methods variadic is the easiest way to add access to that
via the API with no changes in existing callers. We can use this from
terraform to avoid repeatedly walking overlapping sets of nodes.
This functionality is now provided by the "errors" package in the standard
library, so the HashiCorp-specific library is obsolete.
This also removed our one direct use of github.com/pkg/errors, which we
were using in a way that was totally redundant with the stdlib package
errors. However, it lives on as an indirect dependency through the Consul
backend's dependency on the Consul SDK, which uses that library.
When reading this code to check Terraform's graph sorting behavior, I got very
confused about the direction of traversal for several methods. Although some of
these methods would also probably benefit from renames, this commit only updates
their doc comments to use the same directional terminology that we use in the
`Edge` interface (source/target).
We previously did two levels of DynamicExpand to go from ConfigResource to
AbsResource and then from AbsResource to AbsResourceInstance.
We'll now do the full expansion from ConfigResource to AbsResourceInstance
in a single DynamicExpand step inside nodeExpandPlannableResource.
The new approach is essentially functionally equivalent to the old except
that it fixes a bug in the previous implementation: we will now call
checkState.ReportCheckableObjects only once for the entire set of
instances for a particular resource, which is what the checkable objects
infrastructure expects so that it can always mention all of the checkable
objects in the check report even if we bail out partway through due to
a downstream error.
This is essentially the same code but now turned into additional methods
on nodeExpandPlannableResource instead of having the extra graph node
type. This has the further advantage of this now being straight-through
code with standard control flow, instead of the unusual inversion of
control we were doing before bouncing in and out of different Execute and
DynamicExpand implementations to get this done.
A topological walk was previously only done in Terraform via the
concurrent method used for walking the primary dependency graph in core.
Sometime however we want a dependency ordering without the overhead of
instantiating the concurrent walk with the channel-based edges.
Add TopologicalOrder and ReverseTopologicalOrder to obtain a list of
nodes which can be used to visit each while ensuring that all
dependencies are satisfied.
Make DAG walks test-able, and add tests for more complex graph ordering.
We also add breadth-first for comparison, though it's not used currently
in Terraform.
When creating a Set of BasicEdges, the Hashcode function is used to determine
map keys for the underlying set data structure.
The string hex representation of the two vertices' pointers is unsafe to use
as a map key, since these addresses may change between the time they are added
to the set and the time the set is operated on.
Instead we modify the Hashcode function to maintain the references to the
underlying vertices so they cannot be garbage collected during the lifetime
of the Set.
TransitiveReduction does not rely on having a single root, and only
must be free of cycles.
DepthFirstWalk and ReverseDepthFirstWalk do not do a topological sort,
so if order matters TransitiveReduction must be run first.
These two functions were left during a refactor to ensure the old
behavior of a sorted walk was still accessible in some manner. The
package has since been removed from any public API, and the sorted
versions are no longer called, so we can remove them.
This is part of a general effort to move all of Terraform's non-library
package surface under internal in order to reinforce that these are for
internal use within Terraform only.
If you were previously importing packages under this prefix into an
external codebase, you could pin to an earlier release tag as an interim
solution until you've make a plan to achieve the same functionality some
other way.
This is part of a general effort to move all of Terraform's non-library
package surface under internal in order to reinforce that these are for
internal use within Terraform only.
If you were previously importing packages under this prefix into an
external codebase, you could pin to an earlier release tag as an interim
solution until you've make a plan to achieve the same functionality some
other way.
