1// Copyright 2018 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package mvs implements Minimal Version Selection. 6// See https://research.swtch.com/vgo-mvs. 7package mvs 8 9import ( 10 "fmt" 11 "sort" 12 "sync" 13 14 "cmd/go/internal/base" 15 "cmd/go/internal/module" 16 "cmd/go/internal/par" 17) 18 19// A Reqs is the requirement graph on which Minimal Version Selection (MVS) operates. 20// 21// The version strings are opaque except for the special version "none" 22// (see the documentation for module.Version). In particular, MVS does not 23// assume that the version strings are semantic versions; instead, the Max method 24// gives access to the comparison operation. 25// 26// It must be safe to call methods on a Reqs from multiple goroutines simultaneously. 27// Because a Reqs may read the underlying graph from the network on demand, 28// the MVS algorithms parallelize the traversal to overlap network delays. 29type Reqs interface { 30 // Required returns the module versions explicitly required by m itself. 31 // The caller must not modify the returned list. 32 Required(m module.Version) ([]module.Version, error) 33 34 // Max returns the maximum of v1 and v2 (it returns either v1 or v2). 35 // 36 // For all versions v, Max(v, "none") must be v, 37 // and for the tanget passed as the first argument to MVS functions, 38 // Max(target, v) must be target. 39 // 40 // Note that v1 < v2 can be written Max(v1, v2) != v1 41 // and similarly v1 <= v2 can be written Max(v1, v2) == v2. 42 Max(v1, v2 string) string 43 44 // Upgrade returns the upgraded version of m, 45 // for use during an UpgradeAll operation. 46 // If m should be kept as is, Upgrade returns m. 47 // If m is not yet used in the build, then m.Version will be "none". 48 // More typically, m.Version will be the version required 49 // by some other module in the build. 50 // 51 // If no module version is available for the given path, 52 // Upgrade returns a non-nil error. 53 // TODO(rsc): Upgrade must be able to return errors, 54 // but should "no latest version" just return m instead? 55 Upgrade(m module.Version) (module.Version, error) 56 57 // Previous returns the version of m.Path immediately prior to m.Version, 58 // or "none" if no such version is known. 59 Previous(m module.Version) (module.Version, error) 60} 61 62type MissingModuleError struct { 63 Module module.Version 64} 65 66func (e *MissingModuleError) Error() string { 67 return fmt.Sprintf("missing module: %v", e.Module) 68} 69 70// BuildList returns the build list for the target module. 71// The first element is the target itself, with the remainder of the list sorted by path. 72func BuildList(target module.Version, reqs Reqs) ([]module.Version, error) { 73 return buildList(target, reqs, nil) 74} 75 76func buildList(target module.Version, reqs Reqs, upgrade func(module.Version) module.Version) ([]module.Version, error) { 77 // Explore work graph in parallel in case reqs.Required 78 // does high-latency network operations. 79 var work par.Work 80 work.Add(target) 81 var ( 82 mu sync.Mutex 83 min = map[string]string{target.Path: target.Version} 84 firstErr error 85 ) 86 work.Do(10, func(item interface{}) { 87 m := item.(module.Version) 88 required, err := reqs.Required(m) 89 90 mu.Lock() 91 if err != nil && firstErr == nil { 92 firstErr = err 93 } 94 if firstErr != nil { 95 mu.Unlock() 96 return 97 } 98 if v, ok := min[m.Path]; !ok || reqs.Max(v, m.Version) != v { 99 min[m.Path] = m.Version 100 } 101 mu.Unlock() 102 103 for _, r := range required { 104 if r.Path == "" { 105 base.Errorf("Required(%v) returned zero module in list", m) 106 continue 107 } 108 work.Add(r) 109 } 110 111 if upgrade != nil { 112 u := upgrade(m) 113 if u.Path == "" { 114 base.Errorf("Upgrade(%v) returned zero module", m) 115 return 116 } 117 work.Add(u) 118 } 119 }) 120 121 if firstErr != nil { 122 return nil, firstErr 123 } 124 if v := min[target.Path]; v != target.Version { 125 panic(fmt.Sprintf("mistake: chose version %q instead of target %+v", v, target)) // TODO: Don't panic. 126 } 127 128 list := []module.Version{target} 129 listed := map[string]bool{target.Path: true} 130 for i := 0; i < len(list); i++ { 131 m := list[i] 132 required, err := reqs.Required(m) 133 if err != nil { 134 return nil, err 135 } 136 for _, r := range required { 137 v := min[r.Path] 138 if r.Path != target.Path && reqs.Max(v, r.Version) != v { 139 panic(fmt.Sprintf("mistake: version %q does not satisfy requirement %+v", v, r)) // TODO: Don't panic. 140 } 141 if !listed[r.Path] { 142 list = append(list, module.Version{Path: r.Path, Version: v}) 143 listed[r.Path] = true 144 } 145 } 146 } 147 148 tail := list[1:] 149 sort.Slice(tail, func(i, j int) bool { 150 return tail[i].Path < tail[j].Path 151 }) 152 return list, nil 153} 154 155// Req returns the minimal requirement list for the target module 156// that results in the given build list, with the constraint that all 157// module paths listed in base must appear in the returned list. 158func Req(target module.Version, list []module.Version, base []string, reqs Reqs) ([]module.Version, error) { 159 // Note: Not running in parallel because we assume 160 // that list came from a previous operation that paged 161 // in all the requirements, so there's no I/O to overlap now. 162 163 // Compute postorder, cache requirements. 164 var postorder []module.Version 165 reqCache := map[module.Version][]module.Version{} 166 reqCache[target] = nil 167 var walk func(module.Version) error 168 walk = func(m module.Version) error { 169 _, ok := reqCache[m] 170 if ok { 171 return nil 172 } 173 required, err := reqs.Required(m) 174 if err != nil { 175 return err 176 } 177 reqCache[m] = required 178 for _, m1 := range required { 179 if err := walk(m1); err != nil { 180 return err 181 } 182 } 183 postorder = append(postorder, m) 184 return nil 185 } 186 for _, m := range list { 187 if err := walk(m); err != nil { 188 return nil, err 189 } 190 } 191 192 // Walk modules in reverse post-order, only adding those not implied already. 193 have := map[string]string{} 194 walk = func(m module.Version) error { 195 if v, ok := have[m.Path]; ok && reqs.Max(m.Version, v) == v { 196 return nil 197 } 198 have[m.Path] = m.Version 199 for _, m1 := range reqCache[m] { 200 walk(m1) 201 } 202 return nil 203 } 204 max := map[string]string{} 205 for _, m := range list { 206 if v, ok := max[m.Path]; ok { 207 max[m.Path] = reqs.Max(m.Version, v) 208 } else { 209 max[m.Path] = m.Version 210 } 211 } 212 // First walk the base modules that must be listed. 213 var min []module.Version 214 for _, path := range base { 215 m := module.Version{Path: path, Version: max[path]} 216 min = append(min, m) 217 walk(m) 218 } 219 // Now the reverse postorder to bring in anything else. 220 for i := len(postorder) - 1; i >= 0; i-- { 221 m := postorder[i] 222 if max[m.Path] != m.Version { 223 // Older version. 224 continue 225 } 226 if have[m.Path] != m.Version { 227 min = append(min, m) 228 walk(m) 229 } 230 } 231 sort.Slice(min, func(i, j int) bool { 232 return min[i].Path < min[j].Path 233 }) 234 return min, nil 235} 236 237// UpgradeAll returns a build list for the target module 238// in which every module is upgraded to its latest version. 239func UpgradeAll(target module.Version, reqs Reqs) ([]module.Version, error) { 240 return buildList(target, reqs, func(m module.Version) module.Version { 241 if m.Path == target.Path { 242 return target 243 } 244 245 latest, err := reqs.Upgrade(m) 246 if err != nil { 247 panic(err) // TODO 248 } 249 m.Version = latest.Version 250 return m 251 }) 252} 253 254// Upgrade returns a build list for the target module 255// in which the given additional modules are upgraded. 256func Upgrade(target module.Version, reqs Reqs, upgrade ...module.Version) ([]module.Version, error) { 257 list, err := reqs.Required(target) 258 if err != nil { 259 panic(err) // TODO 260 } 261 // TODO: Maybe if an error is given, 262 // rerun with BuildList(upgrade[0], reqs) etc 263 // to find which ones are the buggy ones. 264 list = append([]module.Version(nil), list...) 265 list = append(list, upgrade...) 266 return BuildList(target, &override{target, list, reqs}) 267} 268 269// Downgrade returns a build list for the target module 270// in which the given additional modules are downgraded. 271// 272// The versions to be downgraded may be unreachable from reqs.Latest and 273// reqs.Previous, but the methods of reqs must otherwise handle such versions 274// correctly. 275func Downgrade(target module.Version, reqs Reqs, downgrade ...module.Version) ([]module.Version, error) { 276 list, err := reqs.Required(target) 277 if err != nil { 278 panic(err) // TODO 279 } 280 max := make(map[string]string) 281 for _, r := range list { 282 max[r.Path] = r.Version 283 } 284 for _, d := range downgrade { 285 if v, ok := max[d.Path]; !ok || reqs.Max(v, d.Version) != d.Version { 286 max[d.Path] = d.Version 287 } 288 } 289 290 var ( 291 added = make(map[module.Version]bool) 292 rdeps = make(map[module.Version][]module.Version) 293 excluded = make(map[module.Version]bool) 294 ) 295 var exclude func(module.Version) 296 exclude = func(m module.Version) { 297 if excluded[m] { 298 return 299 } 300 excluded[m] = true 301 for _, p := range rdeps[m] { 302 exclude(p) 303 } 304 } 305 var add func(module.Version) 306 add = func(m module.Version) { 307 if added[m] { 308 return 309 } 310 added[m] = true 311 if v, ok := max[m.Path]; ok && reqs.Max(m.Version, v) != v { 312 exclude(m) 313 return 314 } 315 list, err := reqs.Required(m) 316 if err != nil { 317 panic(err) // TODO 318 } 319 for _, r := range list { 320 add(r) 321 if excluded[r] { 322 exclude(m) 323 return 324 } 325 rdeps[r] = append(rdeps[r], m) 326 } 327 } 328 329 var out []module.Version 330 out = append(out, target) 331List: 332 for _, r := range list { 333 add(r) 334 for excluded[r] { 335 p, err := reqs.Previous(r) 336 if err != nil { 337 return nil, err // TODO 338 } 339 // If the target version is a pseudo-version, it may not be 340 // included when iterating over prior versions using reqs.Previous. 341 // Insert it into the right place in the iteration. 342 // If v is excluded, p should be returned again by reqs.Previous on the next iteration. 343 if v := max[r.Path]; reqs.Max(v, r.Version) != v && reqs.Max(p.Version, v) != p.Version { 344 p.Version = v 345 } 346 if p.Version == "none" { 347 continue List 348 } 349 add(p) 350 r = p 351 } 352 out = append(out, r) 353 } 354 355 return out, nil 356} 357 358type override struct { 359 target module.Version 360 list []module.Version 361 Reqs 362} 363 364func (r *override) Required(m module.Version) ([]module.Version, error) { 365 if m == r.target { 366 return r.list, nil 367 } 368 return r.Reqs.Required(m) 369} 370