Go Minimal Version Selection Notes
This is a reading note to summarise the build list and dependency requirements of minimal version selection of go. If you want to learn more about minimal version select(MVS), please read the documentation and design docs below.
In short, MVS produces the build list as output, the list of module versions used for a build. The "minimal" in MVS means it selects the minimal version of each module that satisfies all requirements, instead of automatically choosing the highest available version. For example, if the requirements are "v1.1, v1.2, v1.3", the version v1.3 is the minimal version that satisfies all requirements. According to the MVS, v1.3 is selected.
Dependency Requirements and Build list
- dependency requirements(or requirement list): a list of minimum versions of other modules, go.mod represents the dependency requirements.
- build list: list of modules and versions for use in a given build.
The build list are always bigger than dependency requirements as some modules are omitted in dependency requirements but need to show inside build list.
For example, dependency requirements of main for module import graph main-> B-> C could be B only because we can load all information of C from B. Note that the real case is more complex but the idea is the same. However, the build list should contain both B and C, as it must load all necessary modules for build. Note that the MVS doesn't talk about the module graph pruning, we can treat it as an additional optimization on the top of MVS. Hence, the build list here should be understood as all modules constructed.
The dependency requirements are calculated from the build list, and the Algorithm R. Compute a Minimal Requirement List describes the approach.
Construct Build List
Details of build list construction is described in Algorithm 1: Construct Build List. The post describes the recursive construction and reachable graph traversal approach, and the recursive is bad because it's inefficient.
A literal implementation of that definition would be too inefficient, potentially requiring time exponential in the size of an acyclic module requirement graph and running forever on a cyclic graph.
Traversing requirement graph may encounter the same version with different versions. It's very common because different module uses different version for a module. Build list will use the highest version among these versions, which means there is only one version for each module.