1// Copyright 2017 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 5package gps 6 7import ( 8 "fmt" 9 "sort" 10 11 "github.com/Masterminds/semver" 12 "github.com/golang/dep/gps/internal/pb" 13) 14 15// VersionType indicates a type for a Version that conveys some additional 16// semantics beyond that which is literally embedded on the Go type. 17type VersionType uint8 18 19// VersionTypes for the four major classes of version. 20const ( 21 IsRevision VersionType = iota 22 IsVersion 23 IsSemver 24 IsBranch 25) 26 27// Version represents one of the different types of versions used by gps. 28// 29// Version composes Constraint, because all versions can be used as a constraint 30// (where they allow one, and only one, version - themselves), but constraints 31// are not necessarily discrete versions. 32// 33// Version is an interface, but it contains private methods, which restricts it 34// to gps's own internal implementations. We do this for the confluence of 35// two reasons: the implementation of Versions is complete (there is no case in 36// which we'd need other types), and the implementation relies on type magic 37// under the hood, which would be unsafe to do if other dynamic types could be 38// hiding behind the interface. 39type Version interface { 40 Constraint 41 42 // Indicates the type of version - Revision, Branch, Version, or Semver. 43 Type() VersionType 44} 45 46// PairedVersion represents a normal Version, but paired with its corresponding, 47// underlying Revision. 48type PairedVersion interface { 49 Version 50 51 // Revision returns the immutable Revision that identifies this Version. 52 Revision() Revision 53 54 // Unpair returns the surface-level UnpairedVersion that half of the pair. 55 // 56 // It does NOT modify the original PairedVersion. 57 Unpair() UnpairedVersion 58 59 // Ensures it is impossible to be both a PairedVersion and an 60 // UnpairedVersion. 61 _pair(int) 62} 63 64// UnpairedVersion represents a normal Version, with a method for creating a 65// VersionPair by indicating the version's corresponding, underlying Revision. 66type UnpairedVersion interface { 67 Version 68 // Pair takes the underlying Revision that this UnpairedVersion corresponds 69 // to and unites them into a PairedVersion. 70 Pair(Revision) PairedVersion 71 // Ensures it is impossible to be both a PairedVersion and an 72 // UnpairedVersion. 73 _pair(bool) 74} 75 76// types are weird 77func (branchVersion) _pair(bool) {} 78func (plainVersion) _pair(bool) {} 79func (semVersion) _pair(bool) {} 80func (versionPair) _pair(int) {} 81 82// NewBranch creates a new Version to represent a floating version (in 83// general, a branch). 84func NewBranch(body string) UnpairedVersion { 85 return branchVersion{ 86 name: body, 87 // We always set isDefault to false here, because the property is 88 // specifically designed to be internal-only: only the SourceManager 89 // gets to mark it. This is OK because nothing that client code is 90 // responsible for needs to care about has to touch it it. 91 // 92 // TODO(sdboyer) ...maybe. this just ugly. 93 isDefault: false, 94 } 95} 96 97func newDefaultBranch(body string) UnpairedVersion { 98 return branchVersion{ 99 name: body, 100 isDefault: true, 101 } 102} 103 104// NewVersion creates a Semver-typed Version if the provided version string is 105// valid semver, and a plain/non-semver version if not. 106func NewVersion(body string) UnpairedVersion { 107 sv, err := semver.NewVersion(body) 108 109 if err != nil { 110 return plainVersion(body) 111 } 112 return semVersion{sv: sv} 113} 114 115// A Revision represents an immutable versioning identifier. 116type Revision string 117 118// String converts the Revision back into a string. 119func (r Revision) String() string { 120 return string(r) 121} 122 123// ImpliedCaretString follows the same rules as String(), but in accordance with 124// the Constraint interface will always print a leading "=", as all Versions, 125// when acting as a Constraint, act as exact matches. 126func (r Revision) ImpliedCaretString() string { 127 return r.String() 128} 129 130func (r Revision) typedString() string { 131 return "r-" + string(r) 132} 133 134// Type indicates the type of version - for revisions, "revision". 135func (r Revision) Type() VersionType { 136 return IsRevision 137} 138 139// Matches is the Revision acting as a constraint; it checks to see if the provided 140// version is the same Revision as itself. 141func (r Revision) Matches(v Version) bool { 142 switch tv := v.(type) { 143 case Revision: 144 return r == tv 145 case versionPair: 146 return r == tv.r 147 } 148 149 return false 150} 151 152// MatchesAny is the Revision acting as a constraint; it checks to see if the provided 153// version is the same Revision as itself. 154func (r Revision) MatchesAny(c Constraint) bool { 155 switch tc := c.(type) { 156 case anyConstraint: 157 return true 158 case noneConstraint: 159 return false 160 case Revision: 161 return r == tc 162 case versionPair: 163 return r == tc.r 164 } 165 166 return false 167} 168 169// Intersect computes the intersection of the Constraint with the provided 170// Constraint. For Revisions, this can only be another, exactly equal 171// Revision, or a PairedVersion whose underlying Revision is exactly equal. 172func (r Revision) Intersect(c Constraint) Constraint { 173 switch tc := c.(type) { 174 case anyConstraint: 175 return r 176 case noneConstraint: 177 return none 178 case Revision: 179 if r == tc { 180 return r 181 } 182 case versionPair: 183 if r == tc.r { 184 return r 185 } 186 } 187 188 return none 189} 190 191func (r Revision) identical(c Constraint) bool { 192 r2, ok := c.(Revision) 193 if !ok { 194 return false 195 } 196 return r == r2 197} 198 199func (r Revision) copyTo(msg *pb.Constraint) { 200 msg.Type = pb.Constraint_Revision 201 msg.Value = string(r) 202} 203 204type branchVersion struct { 205 name string 206 isDefault bool 207} 208 209func (v branchVersion) String() string { 210 return string(v.name) 211} 212 213func (v branchVersion) ImpliedCaretString() string { 214 return v.String() 215} 216 217func (v branchVersion) typedString() string { 218 return fmt.Sprintf("b-%s", v.String()) 219} 220 221func (v branchVersion) Type() VersionType { 222 return IsBranch 223} 224 225func (v branchVersion) Matches(v2 Version) bool { 226 switch tv := v2.(type) { 227 case branchVersion: 228 return v.name == tv.name 229 case versionPair: 230 if tv2, ok := tv.v.(branchVersion); ok { 231 return tv2.name == v.name 232 } 233 } 234 return false 235} 236 237func (v branchVersion) MatchesAny(c Constraint) bool { 238 switch tc := c.(type) { 239 case anyConstraint: 240 return true 241 case noneConstraint: 242 return false 243 case branchVersion: 244 return v.name == tc.name 245 case versionPair: 246 if tc2, ok := tc.v.(branchVersion); ok { 247 return tc2.name == v.name 248 } 249 } 250 251 return false 252} 253 254func (v branchVersion) Intersect(c Constraint) Constraint { 255 switch tc := c.(type) { 256 case anyConstraint: 257 return v 258 case noneConstraint: 259 return none 260 case branchVersion: 261 if v.name == tc.name { 262 return v 263 } 264 case versionPair: 265 if tc2, ok := tc.v.(branchVersion); ok { 266 if v.name == tc2.name { 267 return v 268 } 269 } 270 } 271 272 return none 273} 274 275func (v branchVersion) Pair(r Revision) PairedVersion { 276 return versionPair{ 277 v: v, 278 r: r, 279 } 280} 281 282func (v branchVersion) identical(c Constraint) bool { 283 v2, ok := c.(branchVersion) 284 if !ok { 285 return false 286 } 287 return v == v2 288} 289 290func (v branchVersion) copyTo(msg *pb.Constraint) { 291 if v.isDefault { 292 msg.Type = pb.Constraint_DefaultBranch 293 } else { 294 msg.Type = pb.Constraint_Branch 295 } 296 msg.Value = v.name 297} 298 299type plainVersion string 300 301func (v plainVersion) String() string { 302 return string(v) 303} 304 305func (v plainVersion) ImpliedCaretString() string { 306 return v.String() 307} 308 309func (v plainVersion) typedString() string { 310 return fmt.Sprintf("pv-%s", v.String()) 311} 312 313func (v plainVersion) Type() VersionType { 314 return IsVersion 315} 316 317func (v plainVersion) Matches(v2 Version) bool { 318 switch tv := v2.(type) { 319 case plainVersion: 320 return v == tv 321 case versionPair: 322 if tv2, ok := tv.v.(plainVersion); ok { 323 return tv2 == v 324 } 325 } 326 return false 327} 328 329func (v plainVersion) MatchesAny(c Constraint) bool { 330 switch tc := c.(type) { 331 case anyConstraint: 332 return true 333 case noneConstraint: 334 return false 335 case plainVersion: 336 return v == tc 337 case versionPair: 338 if tc2, ok := tc.v.(plainVersion); ok { 339 return tc2 == v 340 } 341 } 342 343 return false 344} 345 346func (v plainVersion) Intersect(c Constraint) Constraint { 347 switch tc := c.(type) { 348 case anyConstraint: 349 return v 350 case noneConstraint: 351 return none 352 case plainVersion: 353 if v == tc { 354 return v 355 } 356 case versionPair: 357 if tc2, ok := tc.v.(plainVersion); ok { 358 if v == tc2 { 359 return v 360 } 361 } 362 } 363 364 return none 365} 366 367func (v plainVersion) Pair(r Revision) PairedVersion { 368 return versionPair{ 369 v: v, 370 r: r, 371 } 372} 373 374func (v plainVersion) identical(c Constraint) bool { 375 v2, ok := c.(plainVersion) 376 if !ok { 377 return false 378 } 379 return v == v2 380} 381 382func (v plainVersion) copyTo(msg *pb.Constraint) { 383 msg.Type = pb.Constraint_Version 384 msg.Value = string(v) 385} 386 387type semVersion struct { 388 sv semver.Version 389} 390 391func (v semVersion) String() string { 392 str := v.sv.Original() 393 if str == "" { 394 str = v.sv.String() 395 } 396 return str 397} 398 399func (v semVersion) ImpliedCaretString() string { 400 return v.sv.ImpliedCaretString() 401} 402 403func (v semVersion) typedString() string { 404 return fmt.Sprintf("sv-%s", v.String()) 405} 406 407func (v semVersion) Type() VersionType { 408 return IsSemver 409} 410 411func (v semVersion) Matches(v2 Version) bool { 412 switch tv := v2.(type) { 413 case semVersion: 414 return v.sv.Equal(tv.sv) 415 case versionPair: 416 if tv2, ok := tv.v.(semVersion); ok { 417 return tv2.sv.Equal(v.sv) 418 } 419 } 420 return false 421} 422 423func (v semVersion) MatchesAny(c Constraint) bool { 424 switch tc := c.(type) { 425 case anyConstraint: 426 return true 427 case noneConstraint: 428 return false 429 case semVersion: 430 return v.sv.Equal(tc.sv) 431 case semverConstraint: 432 return tc.Intersect(v) != none 433 case versionPair: 434 if tc2, ok := tc.v.(semVersion); ok { 435 return tc2.sv.Equal(v.sv) 436 } 437 } 438 439 return false 440} 441 442func (v semVersion) Intersect(c Constraint) Constraint { 443 switch tc := c.(type) { 444 case anyConstraint: 445 return v 446 case noneConstraint: 447 return none 448 case semVersion: 449 if v.sv.Equal(tc.sv) { 450 return v 451 } 452 case semverConstraint: 453 return tc.Intersect(v) 454 case versionPair: 455 if tc2, ok := tc.v.(semVersion); ok { 456 if v.sv.Equal(tc2.sv) { 457 return v 458 } 459 } 460 } 461 462 return none 463} 464 465func (v semVersion) Pair(r Revision) PairedVersion { 466 return versionPair{ 467 v: v, 468 r: r, 469 } 470} 471 472func (v semVersion) identical(c Constraint) bool { 473 v2, ok := c.(semVersion) 474 if !ok { 475 return false 476 } 477 return v == v2 478} 479 480func (v semVersion) copyTo(msg *pb.Constraint) { 481 msg.Type = pb.Constraint_Semver 482 msg.Value = v.String() //TODO better encoding which doesn't require re-parsing 483} 484 485type versionPair struct { 486 v UnpairedVersion 487 r Revision 488} 489 490func (v versionPair) String() string { 491 return v.v.String() 492} 493 494func (v versionPair) ImpliedCaretString() string { 495 return v.v.ImpliedCaretString() 496} 497 498func (v versionPair) typedString() string { 499 return fmt.Sprintf("%s-%s", v.Unpair().typedString(), v.Revision().typedString()) 500} 501 502func (v versionPair) Type() VersionType { 503 return v.v.Type() 504} 505 506func (v versionPair) Revision() Revision { 507 return v.r 508} 509 510func (v versionPair) Unpair() UnpairedVersion { 511 return v.v 512} 513 514func (v versionPair) Matches(v2 Version) bool { 515 switch tv2 := v2.(type) { 516 case versionPair: 517 return v.r == tv2.r 518 case Revision: 519 return v.r == tv2 520 } 521 522 switch tv := v.v.(type) { 523 case plainVersion, branchVersion: 524 if tv.Matches(v2) { 525 return true 526 } 527 case semVersion: 528 if tv2, ok := v2.(semVersion); ok { 529 if tv.sv.Equal(tv2.sv) { 530 return true 531 } 532 } 533 } 534 535 return false 536} 537 538func (v versionPair) MatchesAny(c2 Constraint) bool { 539 return c2.Matches(v) 540} 541 542func (v versionPair) Intersect(c2 Constraint) Constraint { 543 switch tc := c2.(type) { 544 case anyConstraint: 545 return v 546 case noneConstraint: 547 return none 548 case versionPair: 549 if v.r == tc.r { 550 return v.r 551 } 552 case Revision: 553 if v.r == tc { 554 return v.r 555 } 556 case semverConstraint: 557 if tv, ok := v.v.(semVersion); ok { 558 if tc.Intersect(tv) == v.v { 559 return v 560 } 561 } 562 // If the semver intersection failed, we know nothing could work 563 return none 564 } 565 566 switch tv := v.v.(type) { 567 case plainVersion, branchVersion: 568 if c2.Matches(v) { 569 return v 570 } 571 case semVersion: 572 if tv2, ok := c2.(semVersion); ok { 573 if tv.sv.Equal(tv2.sv) { 574 return v 575 } 576 } 577 } 578 579 return none 580} 581 582func (v versionPair) identical(c Constraint) bool { 583 v2, ok := c.(versionPair) 584 if !ok { 585 return false 586 } 587 if v.r != v2.r { 588 return false 589 } 590 return v.v.identical(v2.v) 591} 592 593func (v versionPair) copyTo(*pb.Constraint) { 594 panic("versionPair should never be serialized; it is solver internal-only") 595} 596 597// compareVersionType is a sort func helper that makes a coarse-grained sorting 598// decision based on version type. 599// 600// Make sure that l and r have already been converted from versionPair (if 601// applicable). 602func compareVersionType(l, r Version) int { 603 // Big fugly double type switch. No reflect, because this can be smack in a hot loop 604 switch l.(type) { 605 case Revision: 606 switch r.(type) { 607 case Revision: 608 return 0 609 case branchVersion, plainVersion, semVersion: 610 return 1 611 } 612 613 case plainVersion: 614 switch r.(type) { 615 case Revision: 616 return -1 617 case plainVersion: 618 return 0 619 case branchVersion, semVersion: 620 return 1 621 } 622 623 case branchVersion: 624 switch r.(type) { 625 case Revision, plainVersion: 626 return -1 627 case branchVersion: 628 return 0 629 case semVersion: 630 return 1 631 } 632 633 case semVersion: 634 switch r.(type) { 635 case Revision, branchVersion, plainVersion: 636 return -1 637 case semVersion: 638 return 0 639 } 640 } 641 panic("unknown version type") 642} 643 644// SortForUpgrade sorts a slice of []Version in roughly descending order, so 645// that presumably newer versions are visited first. The rules are: 646// 647// - All semver versions come first, and sort mostly according to the semver 648// 2.0 spec (as implemented by github.com/Masterminds/semver lib), with one 649// exception: 650// - Semver versions with a prerelease are after *all* non-prerelease semver. 651// Within this subset they are sorted first by their numerical component, then 652// lexicographically by their prerelease version. 653// - The default branch(es) is next; the exact semantics of that are specific 654// to the underlying source. 655// - All other branches come next, sorted lexicographically. 656// - All non-semver versions (tags) are next, sorted lexicographically. 657// - Revisions, if any, are last, sorted lexicographically. Revisions do not 658// typically appear in version lists, so the only invariant we maintain is 659// determinism - deeper semantics, like chronology or topology, do not matter. 660// 661// So, given a slice of the following versions: 662// 663// - Branch: master devel 664// - Semver tags: v1.0.0, v1.1.0, v1.1.0-alpha1 665// - Non-semver tags: footag 666// - Revision: f6e74e8d 667// 668// Sorting for upgrade will result in the following slice: 669// 670// [v1.1.0 v1.0.0 v1.1.0-alpha1 master devel footag f6e74e8d] 671func SortForUpgrade(vl []Version) { 672 sort.Sort(upgradeVersionSorter(vl)) 673} 674 675// SortPairedForUpgrade has the same behavior as SortForUpgrade, but operates on 676// []PairedVersion types. 677func SortPairedForUpgrade(vl []PairedVersion) { 678 sort.Sort(pvupgradeVersionSorter(vl)) 679} 680 681// SortForDowngrade sorts a slice of []Version in roughly ascending order, so 682// that presumably older versions are visited first. 683// 684// This is *not* the same as reversing SortForUpgrade (or you could simply 685// sort.Reverse()). The type precedence is the same, including the semver vs. 686// semver-with-prerelease relation. Lexicographical comparisons within 687// non-semver tags, branches, and revisions remains the same as well; because we 688// treat these domains as having no ordering relation, there can be no real 689// concept of "upgrade" vs "downgrade", so there is no reason to reverse them. 690// 691// Thus, the only binary relation that is reversed for downgrade is within-type 692// comparisons for semver. 693// 694// So, given a slice of the following versions: 695// 696// - Branch: master devel 697// - Semver tags: v1.0.0, v1.1.0, v1.1.0-alpha1 698// - Non-semver tags: footag 699// - Revision: f6e74e8d 700// 701// Sorting for downgrade will result in the following slice: 702// 703// [v1.0.0 v1.1.0 v1.1.0-alpha1 footag devel master f6e74e8d] 704func SortForDowngrade(vl []Version) { 705 sort.Sort(downgradeVersionSorter(vl)) 706} 707 708// SortPairedForDowngrade has the same behavior as SortForDowngrade, but 709// operates on []PairedVersion types. 710func SortPairedForDowngrade(vl []PairedVersion) { 711 sort.Sort(pvdowngradeVersionSorter(vl)) 712} 713 714type upgradeVersionSorter []Version 715 716func (vs upgradeVersionSorter) Len() int { 717 return len(vs) 718} 719 720func (vs upgradeVersionSorter) Swap(i, j int) { 721 vs[i], vs[j] = vs[j], vs[i] 722} 723 724func (vs upgradeVersionSorter) Less(i, j int) bool { 725 l, r := vs[i], vs[j] 726 return vLess(l, r, false) 727} 728 729type pvupgradeVersionSorter []PairedVersion 730 731func (vs pvupgradeVersionSorter) Len() int { 732 return len(vs) 733} 734 735func (vs pvupgradeVersionSorter) Swap(i, j int) { 736 vs[i], vs[j] = vs[j], vs[i] 737} 738func (vs pvupgradeVersionSorter) Less(i, j int) bool { 739 l, r := vs[i], vs[j] 740 return vLess(l, r, false) 741} 742 743type downgradeVersionSorter []Version 744 745func (vs downgradeVersionSorter) Len() int { 746 return len(vs) 747} 748 749func (vs downgradeVersionSorter) Swap(i, j int) { 750 vs[i], vs[j] = vs[j], vs[i] 751} 752 753func (vs downgradeVersionSorter) Less(i, j int) bool { 754 l, r := vs[i], vs[j] 755 return vLess(l, r, true) 756} 757 758type pvdowngradeVersionSorter []PairedVersion 759 760func (vs pvdowngradeVersionSorter) Len() int { 761 return len(vs) 762} 763 764func (vs pvdowngradeVersionSorter) Swap(i, j int) { 765 vs[i], vs[j] = vs[j], vs[i] 766} 767func (vs pvdowngradeVersionSorter) Less(i, j int) bool { 768 l, r := vs[i], vs[j] 769 return vLess(l, r, true) 770} 771 772func vLess(l, r Version, down bool) bool { 773 if tl, ispair := l.(versionPair); ispair { 774 l = tl.v 775 } 776 if tr, ispair := r.(versionPair); ispair { 777 r = tr.v 778 } 779 780 switch compareVersionType(l, r) { 781 case -1: 782 return true 783 case 1: 784 return false 785 case 0: 786 break 787 default: 788 panic("unreachable") 789 } 790 791 switch tl := l.(type) { 792 case branchVersion: 793 tr := r.(branchVersion) 794 if tl.isDefault != tr.isDefault { 795 // If they're not both defaults, then return the left val: if left 796 // is the default, then it is "less" (true) b/c we want it earlier. 797 // Else the right is the default, and so the left should be later 798 // (false). 799 return tl.isDefault 800 } 801 return l.String() < r.String() 802 case Revision, plainVersion: 803 // All that we can do now is alpha sort 804 return l.String() < r.String() 805 } 806 807 // This ensures that pre-release versions are always sorted after ALL 808 // full-release versions 809 lsv, rsv := l.(semVersion).sv, r.(semVersion).sv 810 lpre, rpre := lsv.Prerelease() == "", rsv.Prerelease() == "" 811 if (lpre && !rpre) || (!lpre && rpre) { 812 return lpre 813 } 814 815 if down { 816 return lsv.LessThan(rsv) 817 } 818 return lsv.GreaterThan(rsv) 819} 820 821func hidePair(pvl []PairedVersion) []Version { 822 vl := make([]Version, 0, len(pvl)) 823 for _, v := range pvl { 824 vl = append(vl, v) 825 } 826 return vl 827} 828 829// VersionComponentStrings decomposes a Version into the underlying number, branch and revision. 830func VersionComponentStrings(v Version) (revision string, branch string, version string) { 831 switch tv := v.(type) { 832 case UnpairedVersion: 833 case Revision: 834 revision = tv.String() 835 case PairedVersion: 836 revision = tv.Revision().String() 837 } 838 839 switch v.Type() { 840 case IsBranch: 841 branch = v.String() 842 case IsSemver, IsVersion: 843 version = v.String() 844 } 845 846 return 847} 848