This is an automated email from the ASF dual-hosted git repository. ccollins pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/mynewt-newt.git
commit 7b42efd83e6a2373c526897d7d2c61c82a33274c Author: Christopher Collins <[email protected]> AuthorDate: Thu Jan 16 12:59:02 2020 -0800 Simplify repo dependencies Remove two features from Mynewt's repo dependency support: 1. The ability to depend on a range of repo versions, and 2. Mandatory version.yml files. This change is described in more detail here: https://github.com/apache/mynewt-newt/pull/365 --- newt/deprepo/deprepo.go | 345 +++++++++++++++++++----------------------- newt/deprepo/graph.go | 152 ++++++------------- newt/deprepo/matrix.go | 172 --------------------- newt/downloader/downloader.go | 28 +++- newt/install/install.go | 287 +++++------------------------------ newt/newtutil/repo_version.go | 31 ++-- newt/project/project.go | 1 - newt/repo/repo.go | 1 - newt/repo/version.go | 147 ++---------------- 9 files changed, 299 insertions(+), 865 deletions(-) diff --git a/newt/deprepo/deprepo.go b/newt/deprepo/deprepo.go index 56c65ab..159bac0 100644 --- a/newt/deprepo/deprepo.go +++ b/newt/deprepo/deprepo.go @@ -25,6 +25,8 @@ import ( "sort" "strings" + log "github.com/sirupsen/logrus" + "mynewt.apache.org/newt/newt/newtutil" "mynewt.apache.org/newt/newt/repo" "mynewt.apache.org/newt/util" @@ -39,10 +41,29 @@ type VersionMap map[string]newtutil.RepoVersion // [repo-name] => requirements-for-key-repo type RequirementMap map[string]newtutil.RepoVersion -// Indicates an inability to find an acceptable version of a particular repo. +type ConflictEntry struct { + Dependent RVPair + DependeeVer newtutil.RepoVersion +} + +// Indicates dependencies on different versions of the same repo. type Conflict struct { - RepoName string - Filters []Filter + DependeeName string + Entries []ConflictEntry +} + +func (c *Conflict) SortEntries() { + sort.Slice(c.Entries, func(i int, j int) bool { + ci := c.Entries[i] + cj := c.Entries[j] + + x := CompareRVPairs(ci.Dependent, cj.Dependent) + if x != 0 { + return x < 0 + } + + return newtutil.CompareRepoVersions(ci.DependeeVer, cj.DependeeVer) < 0 + }) } // Returns a sorted slice of all constituent repo names. @@ -86,27 +107,6 @@ func (vm VersionMap) String() string { return s } -// Constructs a version matrix from the specified repos. Each row in the -// resulting matrix corresponds to a repo in the supplied slice. Each row node -// represents a single version of the repo. -func BuildMatrix(repos []*repo.Repo, vm VersionMap) (Matrix, error) { - m := Matrix{} - - for _, r := range repos { - if !r.IsLocal() { - vers, err := r.NormalizedVersions() - if err != nil { - return m, err - } - if err := m.AddRow(r.Name(), vers); err != nil { - return m, err - } - } - } - - return m, nil -} - // Builds a repo dependency graph from the repo requirements expressed in the // `project.yml` file. func BuildDepGraph(repos RepoMap, rootReqs RequirementMap) (DepGraph, error) { @@ -120,7 +120,7 @@ func BuildDepGraph(repos RepoMap, rootReqs RequirementMap) (DepGraph, error) { return nil, err } - if err := dg.AddRootDep(repoName, []newtutil.RepoVersion{normalizedReq}); err != nil { + if err := dg.AddRootDep(repoName, normalizedReq); err != nil { return nil, err } } @@ -151,86 +151,6 @@ func BuildDepGraph(repos RepoMap, rootReqs RequirementMap) (DepGraph, error) { return dg, nil } -// Prunes unusable repo versions from the specified matrix. -func PruneMatrix(m *Matrix, repos RepoMap, rootReqs RequirementMap) error { - pruned := map[*repo.RepoDependency]struct{}{} - - // Removes versions of the depended-on package that fail to satisfy the - // dependent's requirements. Each of the depended-on package's - // dependencies are then recursively visited. - var recurse func(dependentName string, dep *repo.RepoDependency) error - recurse = func(dependentName string, dep *repo.RepoDependency) error { - // Don't prune the same dependency twice; prevents infinite - // recursion. - if _, ok := pruned[dep]; ok { - return nil - } - pruned[dep] = struct{}{} - - // Remove versions of this depended-on package that don't satisfy the - // dependency's version requirements. - r := repos[dep.Name] - normalizedReq, err := r.NormalizeVerReq(dep.VerReqs) - if err != nil { - return err - } - filter := Filter{ - Name: dependentName, - Req: normalizedReq, - } - m.ApplyFilter(dep.Name, filter) - - // If there is only one version of the depended-on package left in the - // matrix, we can recursively call this function on all its - // dependencies. - // - // We don't do it, but it is possible to prune when there is more than - // one version remaining. To accomplish this, we would collect the - // requirements from all versions, find their union, and remove - // depended-on packages that satisfy none of the requirements in the - // union. The actual implementation (only prune when one version - // remains) is a simplified implementation of this general procedure. - // In exchange for simplicity, some unusable versions remain in the - // matrix that could have been pruned. These unsuable versions must be - // evaluated unnecessarily when the matrix is being searched for an - // acceptable version set. - row := m.FindRow(r.Name()) - if row != nil && len(row.Vers) == 1 { - ver := row.Vers[0] - commit, err := r.CommitFromVer(ver) - if err != nil { - return err - } - depRepo := repos[dep.Name] - for _, ddep := range depRepo.CommitDepMap()[commit] { - name := fmt.Sprintf("%s,%s", depRepo.Name(), ver.String()) - if err := recurse(name, ddep); err != nil { - return err - } - } - } - - return nil - } - - // Prune versions that are guaranteed to be unusable. Any repo version - // which doesn't satisfy a requirement in `project.yml` is a - // known-bad-version and can be removed. These repos' dependencies can - // then be pruned in turn. - for repoName, req := range rootReqs { - dep := &repo.RepoDependency{ - Name: repoName, - VerReqs: req, - } - - if err := recurse("project.yml", dep); err != nil { - return err - } - } - - return nil -} - // PruneDepGraph removes all entries from a depgraph that aren't in the given // repo slice. This is necessary when the user wants to upgrade only a subset // of repos in the project. @@ -264,12 +184,16 @@ func ConflictError(conflicts []Conflict) error { } s += fmt.Sprintf(" Installation of repo \"%s\" is blocked:", - c.RepoName) + c.DependeeName) lines := []string{} - for _, f := range c.Filters { - lines = append(lines, fmt.Sprintf("\n %30s requires %s %s", - f.Name, c.RepoName, f.Req.String())) + for _, e := range c.Entries { + dependee := RVPair{ + Name: c.DependeeName, + Ver: e.DependeeVer, + } + lines = append(lines, fmt.Sprintf("\n %30s requires %s", + e.Dependent.String(), dependee.String())) } sort.Strings(lines) s += strings.Join(lines, "") @@ -278,100 +202,149 @@ func ConflictError(conflicts []Conflict) error { return util.NewNewtError("Repository conflicts:\n" + s) } -// Searches a version matrix for a set of acceptable repo versions. If there -// isn't an acceptable set of versions, the set with the fewest conflicts is -// returned. +// ResolveRepoDeps calculates the set of repo versions a project should be +// upgraded to. // -// @param m Matrix containing all unpruned repo versions. -// @param dg The repo dependency graph. +// dg: The project's repo dependency graph. This includes root dependencies +// (i.e., dependencies expressed in `project.yml`). // -// @return VersionMap The first perfect set of repo versions, or the -// closest match if there is no perfect set. -// @return []string nil if a perfect set was found, else the names -// of the repos that lack a suitable version -// in the returned version map. -func findClosestMatch(m Matrix, dg DepGraph) (VersionMap, []string) { - // Tracks the best match seen so far. - type Best struct { - vm VersionMap - failures []string +// Returns a version map on success; a set of conflicts on failure. +func ResolveRepoDeps(dg DepGraph) (VersionMap, []Conflict) { + // Represents an entry in the working set. + type WSNode struct { + highPrio bool // If true, always "wins" without conflict. + dependent RVPair // Repo that expresses this dependency. + dependee RVPair // Repo that is depended on. + } + + ws := map[string]WSNode{} // Working set (key=dependent). + cm := map[string]*Conflict{} // Conflict map (key=dependee). + visited := map[string]struct{}{} // Tracks which nodes have been visited. + + // Updates (or inserts a new) conflict object into the conflict map (cm). + addConflict := func(dependent RVPair, dependee RVPair) { + c := cm[dependee.Name] + if c == nil { + wsn := ws[dependee.Name] + + c = &Conflict{ + DependeeName: repoNameString(dependee.Name), + Entries: []ConflictEntry{ + ConflictEntry{ + Dependent: RVPair{ + Name: repoNameString(wsn.dependent.Name), + Ver: wsn.dependent.Ver, + }, + DependeeVer: wsn.dependee.Ver, + }, + }, + } + cm[dependee.Name] = c + } + + c.Entries = append(c.Entries, ConflictEntry{ + Dependent: dependent, + DependeeVer: dependee.Ver, + }) } - var best Best - - for { - vm := m.CurVersions() - badRepos := dg.conflictingRepos(vm) - if len(badRepos) == 0 { - // Found a perfect match. Return it. - return vm, nil + + // Attempts to add a single node to the working set. In case of a + // conflict, the conflict map is updated instead. + addWsNode := func(dependent RVPair, dependee RVPair) { + old, ok := ws[dependee.Name] + if !ok { + // This is the first time we've seen this repo. + ws[dependee.Name] = WSNode{ + highPrio: false, + dependent: dependent, + dependee: dependee, + } + return } - if best.failures == nil || len(badRepos) < len(best.failures) { - best.vm = vm - best.failures = badRepos + if newtutil.CompareRepoVersions(old.dependee.Ver, dependee.Ver) == 0 { + // We have already seen this exact dependency. Ignore the + // duplicate. + return } - // Evaluate the next set of versions on the following iteration. - if !m.Increment() { - // All version sets evaluated. Return the best match. - return best.vm, best.failures + // There is already a dependency for a different version of this repo. + // Handle the conflict. + if old.highPrio { + // Root commit dependencies take priority over all others. + log.Debugf("discarding repo dependency in favor "+ + "of root override: dep=%s->%s root=%s->%s", + dependent.String(), dependee.String(), + old.dependent.String(), old.dependee.String()) + } else { + addConflict(dependent, dependee) } } -} -// Finds the first set of repo versions which satisfies the dependency graph. -// If there is no acceptable set, a slice of conflicts is returned instead. -// -// @param m Matrix containing all unpruned repo versions. -// @param dg The repo dependency graph. -// @return VersionMap The first perfect set of repo versions, or nil -// if there is no perfect set. -// @return []Conflict nil if a perfect set was found, else the set of -// conflicts preventing a perfect match from -// being returned. -func FindAcceptableVersions(m Matrix, dg DepGraph) (VersionMap, []Conflict) { - vm, failures := findClosestMatch(m, dg) - if len(failures) == 0 { - // No failures implies a perfect match was found. Return it. - return vm, nil + // Adds one entry to the working set (ws) for each of the given repo's + // dependencies. + visit := func(rvp RVPair) { + nodes := dg[rvp] + for _, node := range nodes { + addWsNode(rvp, node) + } + + visited[rvp.Name] = struct{}{} } - // A perfect version set doesn't exist. Generate the set of relevant - // conflicts and return it. - conflicts := make([]Conflict, len(failures)) + // Insert all the root dependencies (dependencies in `project.yml`) into + // the working set. A root dependency is "high priority" if it points to a + // git commit rather than a version number. + rootDeps := dg[RVPair{}] + for _, dep := range rootDeps { + ws[dep.Name] = WSNode{ + highPrio: dep.Ver.Commit != "", + dependent: RVPair{Name: rootDependencyName}, + dependee: dep, + } + } - // Build a reverse dependency graph. This will make it easy to determine - // which version requirements are relevant to the failure. - rg := dg.Reverse() - for i, f := range failures { - conflict := Conflict{ - RepoName: f, + // Repeatedly iterate through the working set, visiting each unvisited + // node. Stop looping when an iteration produces no new nodes. + for len(visited) < len(ws) { + // Iterate the working set in a consistent order. The order doesn't + // matter for well-defined projects. For invalid projects, different + // iteration orders can result in different conflicts being reported. + names := make([]string, 0, len(ws)) + for name, _ := range ws { + names = append(names, name) } - for _, node := range rg[f] { - // Determine if this filter is responsible for any conflicts. - // Record the name of the filter if it applies. - var filterName string - if node.Name == rootDependencyName { - filterName = "project.yml" - } else { - // If the version of the repo in the closest-match version map - // is the same one that imposes this version requirement, - // include it in the conflict object. - if newtutil.CompareRepoVersions(vm[node.Name], node.Ver) == 0 { - filterName = fmt.Sprintf( - "%s,%s", node.Name, node.Ver.String()) - } - } + sort.Strings(names) - if filterName != "" { - conflict.Filters = append(conflict.Filters, Filter{ - Name: filterName, - Req: node.VerReq, - }) + for _, name := range names { + wsn := ws[name] + if _, ok := visited[name]; !ok { + visit(wsn.dependee) } } - conflicts[i] = conflict } - return vm, conflicts + // It is an error if any conflicts were detected. + if len(cm) > 0 { + var cs []Conflict + for _, c := range cm { + c.SortEntries() + cs = append(cs, *c) + } + + sort.Slice(cs, func(i int, j int) bool { + return strings.Compare(cs[i].DependeeName, cs[j].DependeeName) < 0 + }) + + return nil, cs + } + + // The working set now contains the target version of each repo in the + // project. + vm := VersionMap{} + for name, wsn := range ws { + vm[name] = wsn.dependee.Ver + } + + return vm, nil } diff --git a/newt/deprepo/graph.go b/newt/deprepo/graph.go index 676b9dd..25564f7 100644 --- a/newt/deprepo/graph.go +++ b/newt/deprepo/graph.go @@ -34,40 +34,32 @@ import ( "mynewt.apache.org/newt/util" ) -// Describes a repo that depends on other repos. -type Dependent struct { - Name string - Ver newtutil.RepoVersion -} - const rootDependencyName = "" const rootRepoName = "project.yml" // Represents a top-level repo dependency (i.e., a repo specified in // `project.yml`). -var rootDependent = Dependent{Name: rootDependencyName} +var rootDependent = RVPair{Name: rootDependencyName} -// A single node in a repo dependency graph. -type DepGraphNode struct { - // Name of depended-on repo. +// Represents a repo-name,version pair. +type RVPair struct { Name string - // Expresses the versions of the repo that satisfy this dependency. - VerReq newtutil.RepoVersion + Ver newtutil.RepoVersion } // A repo dependency graph. // Key: A repo with dependencies. // Value: The corresponding list of dependencies. -type DepGraph map[Dependent][]DepGraphNode +type DepGraph map[RVPair][]RVPair // A single node in a repo reverse dependency graph. type RevdepGraphNode struct { // The name of the dependent repo. Name string // The version of the dependent repo. - Ver newtutil.RepoVersion - // The dependent's version requirements that apply to the graph key. - VerReq newtutil.RepoVersion + DependentVer newtutil.RepoVersion + // The version of the dependee repo that is required. + DependeeVer newtutil.RepoVersion } // A repo reverse dependency graph. @@ -75,20 +67,38 @@ type RevdepGraphNode struct { // Value: The corresponding list of dependencies. type RevdepGraph map[string][]RevdepGraphNode -func repoNameVerString(repoName string, ver newtutil.RepoVersion) string { +func repoNameString(repoName string) string { if repoName == rootDependencyName { return rootRepoName } else { - return fmt.Sprintf("%s-%s", repoName, ver.String()) + return repoName + } +} + +func repoNameVerString(repoName string, ver newtutil.RepoVersion) string { + if repoName == rootDependencyName || repoName == rootRepoName { + return rootRepoName + } else { + return fmt.Sprintf("%s/%s", repoName, ver.String()) } } -func (dep *Dependent) String() string { - return repoNameVerString(dep.Name, dep.Ver) +func (rvp *RVPair) String() string { + return repoNameVerString(rvp.Name, rvp.Ver) } -func (dgn *DepGraphNode) String() string { - return fmt.Sprintf("%s,%s", dgn.Name, dgn.VerReq.String()) +func CompareRVPairs(a RVPair, b RVPair) int { + x := strings.Compare(a.Name, b.Name) + if x != 0 { + return x + } + + x = newtutil.CompareRepoVersions(a.Ver, b.Ver) + if x != 0 { + return x + } + + return 0 } func (dg DepGraph) String() string { @@ -108,8 +118,8 @@ func (dg DepGraph) String() string { } func (rgn *RevdepGraphNode) String() string { - return fmt.Sprintf("%s,%s", repoNameVerString(rgn.Name, rgn.Ver), - rgn.VerReq.String()) + return fmt.Sprintf("%s,%s", repoNameVerString(rgn.Name, rgn.DependentVer), + rgn.DependeeVer.String()) } func (rg RevdepGraph) String() string { @@ -137,7 +147,7 @@ func (rg RevdepGraph) String() string { func (dg DepGraph) AddRepoVer(repoName string, repoVer newtutil.RepoVersion, reqMap RequirementMap) error { - dep := Dependent{ + dep := RVPair{ Name: repoName, Ver: repoVer, } @@ -149,9 +159,9 @@ func (dg DepGraph) AddRepoVer(repoName string, repoVer newtutil.RepoVersion, } for depName, depReq := range reqMap { - dg[dep] = append(dg[dep], DepGraphNode{ - Name: depName, - VerReq: depReq, + dg[dep] = append(dg[dep], RVPair{ + Name: depName, + Ver: depReq, }) } @@ -159,9 +169,7 @@ func (dg DepGraph) AddRepoVer(repoName string, repoVer newtutil.RepoVersion, } // Adds a root dependency (i.e., required repo specified in `project.yml`). -func (dg DepGraph) AddRootDep(repoName string, - verReqs []newtutil.RepoVersion) error { - +func (dg DepGraph) AddRootDep(repoName string, ver newtutil.RepoVersion) error { rootDeps := dg[rootDependent] for _, d := range rootDeps { if d.Name == repoName { @@ -171,9 +179,9 @@ func (dg DepGraph) AddRootDep(repoName string, } } - dg[rootDependent] = append(dg[rootDependent], DepGraphNode{ - Name: repoName, - VerReq: verReqs[0], + dg[rootDependent] = append(dg[rootDependent], RVPair{ + Name: repoName, + Ver: ver, }) return nil @@ -191,12 +199,13 @@ func (dg DepGraph) Reverse() RevdepGraph { for dependent, nodes := range dg { for _, node := range nodes { - // Nothing depends on project.yml (""), so exclude it from the result. + // Nothing depends on project.yml (""), so exclude it from the + // result. if node.Name != "" { rg[node.Name] = append(rg[node.Name], RevdepGraphNode{ - Name: dependent.Name, - Ver: dependent.Ver, - VerReq: node.VerReq, + Name: dependent.Name, + DependentVer: dependent.Ver, + DependeeVer: node.Ver, }) } } @@ -204,70 +213,3 @@ func (dg DepGraph) Reverse() RevdepGraph { return rg } - -// Identifies repos which cannot satisfy all their dependents. For example, if -// `project.yml` requires X1 and Y2, but Y2 requires X2, then X is a -// conflicting repo (no overlap in requirement sets). -// -// Returns the names of all repos that cannot be included in the build. For -// example, if: -// * X depends on Z 1.0.0 -// * Y depends on Z 2.0.0 -// then Z is included in the returned slice because it can't satisfy all its -// dependents. X and Y are *not* included (unless they also have depedents -// that cannot be satisfied). -func (dg DepGraph) conflictingRepos(vm VersionMap) []string { - badRepoMap := map[string]struct{}{} - - // Create a reverse dependency graph. - rg := dg.Reverse() - - for dependeeName, nodes := range rg { - dependeeVer, ok := vm[dependeeName] - if !ok { - // This version was pruned from the matrix. It is unusable. - badRepoMap[dependeeName] = struct{}{} - continue - } - - // Dependee is the repo being depended on. We want to determine if it - // can be included in the project without violating any dependency - // requirements. - // - // For each repo that depends on dependee (i.e., for each dependent): - // 1. Determine which of the dependent's requirements apply to the - // dependee (e.g., if we are evaluating v2 of the dependent, then - // v1's requirements do not apply). - // 2. Check if the dependee satisfies all applicable requirements. - for _, node := range nodes { - var nodeApplies bool - if node.Name == rootDependencyName { - // project.yml requirements are always applicable. - nodeApplies = true - } else { - // Repo dependency requirements only apply if they are - // associated with the version of the dependent that we are - // evaluating. - dependentVer, ok := vm[node.Name] - if ok { - nodeApplies = newtutil.CompareRepoVersions( - dependentVer, node.Ver) == 0 - } - } - if nodeApplies { - if !dependeeVer.Satisfies(node.VerReq) { - badRepoMap[dependeeName] = struct{}{} - break - } - } - } - } - - badRepoSlice := make([]string, 0, len(badRepoMap)) - for repoName, _ := range badRepoMap { - badRepoSlice = append(badRepoSlice, repoName) - } - sort.Strings(badRepoSlice) - - return badRepoSlice -} diff --git a/newt/deprepo/matrix.go b/newt/deprepo/matrix.go deleted file mode 100644 index ca7d99a..0000000 --- a/newt/deprepo/matrix.go +++ /dev/null @@ -1,172 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -// deprepo: Package for resolving repo dependencies. -package deprepo - -import ( - "fmt" - "strings" - - "mynewt.apache.org/newt/newt/newtutil" - "mynewt.apache.org/newt/util" -) - -// Eliminates non-matching version numbers when applied to a matrix row. -type Filter struct { - Name string - Req newtutil.RepoVersion -} - -// Contains all versions of a single repo. These version numbers are read from -// the repo's `repository.yml` file. Only normalized versions are included. -type MatrixRow struct { - // The name of the repo that the row corresponds to. - RepoName string - - // All normalized versions of the repo. - Vers []newtutil.RepoVersion - - // Indicates the version of this repo currently being evaluated for - // conflicts. - VerIdx int - - // All filters that have been applied to this row. This is only used - // during reporting. - Filters []Filter -} - -// Contains all versions of a set of repos. Each row correponds to a single -// repo. Each element within a row represents a single version of the repo. -// -// The Matrix type serves two purposes: -// -// 1. Simple lookup: Provides a convenient means of determining whether a -// specific version of a repo exists. -// -// 2. Requirements matching: The client can cycle through all combinations of -// repo versions via the `Increment()` function. Each combination can be -// exported as a version map via the `CurVersions()` function. By evaluating -// each version map against a set of requirements, the client can find the set -// of repo versions to upgrade to. -type Matrix struct { - rows []MatrixRow -} - -func (m *Matrix) String() string { - lines := make([]string, len(m.rows)) - - for i, row := range m.rows { - line := fmt.Sprintf("%s:", row.RepoName) - for _, v := range row.Vers { - line += fmt.Sprintf(" %s", v.String()) - } - - lines[i] = line - } - - return strings.Join(lines, "\n") -} - -// Adjusts the matrix to point to the next possible set of repo versions. -// -// @return bool true if the matrix points to a new set; -// false if the matrix wrapped around to the first -// set. -func (m *Matrix) Increment() bool { - for i := range m.rows { - row := &m.rows[i] - - row.VerIdx++ - if row.VerIdx < len(row.Vers) { - return true - } - - // No more versions left for this repo; proceed to next. - row.VerIdx = 0 - } - - // All version combinations evaluated. - return false -} - -func (m *Matrix) findRowIdx(repoName string) int { - for i, row := range m.rows { - if row.RepoName == repoName { - return i - } - } - - return -1 -} - -func (m *Matrix) FindRow(repoName string) *MatrixRow { - idx := m.findRowIdx(repoName) - if idx == -1 { - return nil - } - return &m.rows[idx] -} - -func (m *Matrix) AddRow(repoName string, - vers []newtutil.RepoVersion) error { - - if m.findRowIdx(repoName) != -1 { - return util.FmtNewtError("Duplicate repo \"%s\" in repo matrix", - repoName) - } - - m.rows = append(m.rows, MatrixRow{ - RepoName: repoName, - Vers: newtutil.SortedVersionsDesc(vers), - }) - - return nil -} - -// Removes all non-matching versions of the specified repo from the matrix. -func (m *Matrix) ApplyFilter(repoName string, filter Filter) { - rowIdx := m.findRowIdx(repoName) - if rowIdx == -1 { - return - } - row := &m.rows[rowIdx] - - goodVers := []newtutil.RepoVersion{} - for _, v := range row.Vers { - if v.Satisfies(filter.Req) { - goodVers = append(goodVers, v) - } - } - - row.Vers = goodVers - row.Filters = append(row.Filters, filter) -} - -// Constructs a version map from the matrix's current state. -func (m *Matrix) CurVersions() VersionMap { - vm := make(VersionMap, len(m.rows)) - for _, row := range m.rows { - if len(row.Vers) > 0 { - vm[row.RepoName] = row.Vers[row.VerIdx] - } - } - - return vm -} diff --git a/newt/downloader/downloader.go b/newt/downloader/downloader.go index 53c0457..c36ee3c 100644 --- a/newt/downloader/downloader.go +++ b/newt/downloader/downloader.go @@ -578,20 +578,40 @@ func (gd *GenericDownloader) CommitsFor( commit = fixupCommitString(commit) - var commits []string + cm := map[string]struct{}{} - // Add all commits that are equivalent to the specified string. + // Add all cm that are equivalent to the specified string. for _, c := range gd.commits { if commit == c.hash { // User specified a hash; add the corresponding branch or tag name. - commits = append(commits, c.name) + cm[c.name] = struct{}{} } else if commit == c.name { // User specified a branch or tag; add the corresponding hash. - commits = append(commits, c.hash) + cm[c.hash] = struct{}{} + } + } + + // If the user specified a hash, add the hash itself. + ct, err := gd.CommitType(path, commit) + if err != nil { + return nil, err + } + + if ct == COMMIT_TYPE_HASH { + hash, err := gd.HashFor(path, commit) + if err != nil { + return nil, err } + cm[hash] = struct{}{} } + // Sort the list of commit strings. + var commits []string + for cstring, _ := range cm { + commits = append(commits, cstring) + } sort.Strings(commits) + return commits, nil } diff --git a/newt/install/install.go b/newt/install/install.go index 4105f84..9085f28 100644 --- a/newt/install/install.go +++ b/newt/install/install.go @@ -36,16 +36,6 @@ // "version specifiers". Version specifiers map to "official releases", while // git commits typically map to "custom versions". // -// Before newt can do anything with a repo requirement, it needs to extrapolate -// two pieces of information: -// 1. The normalized version number. -// 2. The git commit. -// -// Newt needs the normalized version to determine the repo's dependencies, and -// to ensure the version of the repo is compatible with the version of newt -// being used. Newt needs the git commit so that it knows how to checkout the -// desired repo version. -// // ### VERSION SPECIFIERS // // A repo's `repository.yml` file maps version specifiers to git commits in its @@ -59,32 +49,6 @@ // By performing a series of recursive lookups, newt converts a version // specifier to a normalized-version,git-commit pair. // -// ### GIT COMMITS -// -// When newt encounters a git commit in the `project.yml` file, it already has -// one piece of information that it needs: the git commit. Newt uses the -// following procedure to extrapolate its corresponding repo version: -// -// 1. If the repo at the commit contains a `version.yml` file, read the version -// from this file. -// 2. Else, if the repo's `repository.yml` file maps the commit to a version -// number, use that version number. -// 3. Else, warn the user and assume 0.0.0. -// -// The `version.yml` file is expected to be present in every commit in a repo. -// It has the following form: -// repo.version: <normalized-version-number> -// -// For example, if commit 10 of repo X contains the following `version.yml` -// file: -// repo.version: 1.10.0 -// -// and commit 20 of repo X changes `version.yml` to: -// repo.version: 2.0.0 -// -// then newt extrapolates 1.10.0 from commits 10 through 19 (inclusive). -// Commit 20 and beyond correspond to 2.0.0. -// // ### VERSION STRINGS // // Newt uses the following procedure when displaying a repo version to the @@ -93,11 +57,8 @@ // Official releases are expressed as a normalized version. // e.g., 1.10.0 // -// Custom versions are expressed with the following form: -// <extrapolated-version>/<git-commit> -// -// E.g.,: -// 0.0.0/0aae710654b48d9a84d54de771cc18427709df7d +// Custom versions are expressed as a git hash. +// e.g., 0aae710654b48d9a84d54de771cc18427709df7d // ---------------------------------------------------------------------------- package install @@ -106,7 +67,6 @@ import ( "bufio" "fmt" "os" - "sort" "strings" log "github.com/sirupsen/logrus" @@ -126,8 +86,7 @@ const ( ) // Determines the currently installed version of the specified repo. If the -// repo doesn't have a valid `version.yml` file, and it isn't using a commit -// that maps to a version, 0.0.0 is returned. +// repo isn't using a commit that maps to a version, 0.0.0 is returned. func detectVersion(r *repo.Repo) (newtutil.RepoVersion, error) { ver, err := r.InstalledVersion() if err != nil { @@ -254,104 +213,6 @@ func (inst *Installer) ensureDepsInList(repos []*repo.Repo, return deps } -// Normalizes the installer's set of repo requirements. Only the repos in the -// specified slice are considered. -// -// A repo requirement takes one of two forms: -// * Version specifier (e.g., 1.3.0. or 0-dev). -// * Git commit (e.g., 1f48a3c or master). -// -// This function converts requirements from the second form to the first. A -// git commit is converted to a version number with this procedure: -// -// 1. If the specified commit contains a `version.yml` file, read the version -// from this file. -// 2. Else, if the repo's `repository.yml` file maps the commit to a version -// number, use that version number. -// 3. Else, assume 0.0.0. -func (inst *Installer) inferReqVers(repos []*repo.Repo) error { - for _, r := range repos { - req, ok := inst.reqs[r.Name()] - if ok { - if req.Commit != "" { - ver, err := r.NonInstalledVersion(req.Commit) - if err != nil { - return err - } - - if ver == nil { - util.OneTimeWarning( - "Could not detect version of requested repo "+ - "%s:%s; assuming 0.0.0", - r.Name(), req.Commit) - - ver = &req - } - req = *ver - req.Commit, err = r.HashFromVer(req) - if err != nil { - return err - } - - inst.reqs[r.Name()] = req - } - } - } - - return nil -} - -// Determines if the `project.yml` file specifies a nonexistent repo version. -// Only the repos in the specified slice are considered. -// -// @param repos The list of repos to consider during the check. -// @param m A matrix containing all versions of the -// specified repos. -// -// @return error Error if any repo requirement is invalid. -func (inst *Installer) detectIllegalRepoReqs( - repos []*repo.Repo, m deprepo.Matrix) error { - - var lines []string - for _, r := range repos { - req, ok := inst.reqs[r.Name()] - if ok { - row := m.FindRow(r.Name()) - if row == nil { - return util.FmtNewtError( - "internal error; repo \"%s\" missing from matrix", r.Name()) - } - - r := inst.repos[r.Name()] - nreq, err := r.NormalizeVerReq(req) - if err != nil { - return err - } - - anySatisfied := false - for _, ver := range row.Vers { - if ver.Satisfies(nreq) { - anySatisfied = true - break - } - } - if !anySatisfied { - line := fmt.Sprintf(" %s,%s", r.Name(), nreq.String()) - lines = append(lines, line) - } - } - } - - if len(lines) > 0 { - sort.Strings(lines) - return util.NewNewtError( - "project.yml file specifies nonexistent repo versions:\n" + - strings.Join(lines, "\n")) - } - - return nil -} - // Indicates whether a repo should be upgraded to the specified version. A // repo should be upgraded if it is not currently installed, or if a version // other than the desired one is installed. @@ -399,7 +260,8 @@ func (inst *Installer) filterUpgradeList( filtered := deprepo.VersionMap{} - for name, ver := range vm { + for _, name := range vm.SortedNames() { + ver := vm[name] doUpgrade, err := inst.shouldUpgradeRepo(name, ver) if err != nil { return nil, err @@ -526,22 +388,6 @@ func (inst *Installer) installPrompt(vm deprepo.VersionMap, op installOp, } } -// Filters out repos from a version map, keeping only those which are present -// in the supplied slice. -func filterVersionMap( - vm deprepo.VersionMap, keep []*repo.Repo) deprepo.VersionMap { - - filtered := deprepo.VersionMap{} - for _, r := range keep { - name := r.Name() - if ver, ok := vm[name]; ok { - filtered[name] = ver - } - } - - return filtered -} - // Creates a slice of repos, each corresponding to an element in the provided // version map. The returned slice is sorted by repo name. func (inst *Installer) versionMapRepos( @@ -564,34 +410,6 @@ func (inst *Installer) versionMapRepos( return repos, nil } -// assignCommits applies commit hashes to the selected version of each repo in -// a version map. In other words, it propagates `<...>-commit` requirements -// from `project.yml` and `repository.yml` files. If override is false, -// attempting to set a commit for the same repo twice results in an error. -func (inst *Installer) assignCommits(vm deprepo.VersionMap, repoName string, - req newtutil.RepoVersion, override bool) error { - - curVer := vm[repoName] - if curVer.Satisfies(req) { - if req.Commit != "" { - prevCommit := vm[repoName].Commit - newCommit := req.Commit - - if !override && prevCommit != "" && prevCommit != newCommit { - return util.FmtNewtError( - "repo %s: multiple commits: %s, %s", - repoName, vm[repoName].Commit, req.Commit) - - } - ver := vm[repoName] - ver.Commit = req.Commit - vm[repoName] = ver - } - } - - return nil -} - // Calculates a map of repos and version numbers that should be included in an // install or upgrade operation. func (inst *Installer) calcVersionMap(candidates []*repo.Repo) ( @@ -619,25 +437,23 @@ func (inst *Installer) calcVersionMap(candidates []*repo.Repo) ( } } - m, err := deprepo.BuildMatrix(repoList, inst.vers) - if err != nil { - return nil, err - } - - if err := inst.inferReqVers(repoList); err != nil { - return nil, err - } - - // If the `project.yml` file specifies an invalid repo version, abort now. - if err := inst.detectIllegalRepoReqs(repoList, m); err != nil { - return nil, err - } - - // Remove blocked repo versions from the table. - if err := deprepo.PruneMatrix( - &m, inst.repos, inst.reqs); err != nil { + // Ensure project.yml doesn't specify any invalid versions + for repoName, repoVer := range inst.reqs { + rvp := deprepo.RVPair{ + Name: repoName, + Ver: repoVer, + } + r := inst.repos[repoName] + if r == nil { + return nil, util.FmtNewtError( + "project.yml depends on an unknown repo: %s", rvp.String()) + } - return nil, err + if !r.VersionIsValid(repoVer) { + return nil, util.FmtNewtError( + "project.yml depends on an unknown repo version: %s", + rvp.String()) + } } // Construct a repo dependency graph from the `project.yml` version @@ -647,54 +463,21 @@ func (inst *Installer) calcVersionMap(candidates []*repo.Repo) ( return nil, err } - log.Debugf("Repo dependency graph:\n%s\n", dg.String()) - log.Debugf("Repo reverse dependency graph:\n%s\n", dg.Reverse().String()) + log.Debugf("repo dependency graph:\n%s\n", dg.String()) + log.Debugf("repo reverse dependency graph:\n%s\n", dg.Reverse().String()) - // Don't consider repos that the user excluded (if a repo list was - // specified). - deprepo.PruneDepGraph(dg, candidates) + // Don't consider repos that the user excluded (i.e., if a partial repo + // list was specified). + deprepo.PruneDepGraph(dg, repoList) - // Try to find a version set that satisfies the dependency graph. If no - // such set exists, report the conflicts and abort. - vm, conflicts := deprepo.FindAcceptableVersions(m, dg) + vm, conflicts := deprepo.ResolveRepoDeps(dg) if len(conflicts) > 0 { return nil, deprepo.ConflictError(conflicts) } - // If repos specify git commits in their repo-dependencies, ensure we get - // them. - rg := dg.Reverse() - for name, nodes := range rg { - for _, node := range nodes { - if newtutil.CompareRepoVersions(node.Ver, vm[node.Name]) == 0 { - // Don't consider project.yml dependencies here. Those get - // assigned last so that they can override inter-repo - // dependencies. - if node.Name != "" { - if err := inst.assignCommits(vm, name, node.VerReq, false); err != nil { - return nil, err - } - } - } - } - } - - // If project.yml specified any specific git commits, ensure we get them. - // Commits specified in project.yml override those from repo-dependencies. - for name, reqs := range inst.reqs { - if err := inst.assignCommits(vm, name, reqs, true); err != nil { - return nil, err - } - } - - log.Debugf("repo version map after project.yml overrides:\n%s", + log.Debugf("repo version map:\n%s", vm.String()) - // Now that we know which repo versions we want, we can eliminate some - // false-positives from the repo list. - repoList = inst.ensureDepsInList(candidates, vm) - vm = filterVersionMap(vm, repoList) - return vm, nil } @@ -918,18 +701,20 @@ func (inst *Installer) remoteRepoInfo(r *repo.Repo, vm *deprepo.VersionMap) { ri := inst.gatherInfo(r, vm) s := fmt.Sprintf(" * %s:", r.Name()) - s += fmt.Sprintf(" %s,", ri.commitHash) + s += fmt.Sprintf(" %s", ri.commitHash) if ri.installedVer == nil { - s += " (not installed)" + s += ", (not installed)" } else if ri.errorText != "" { - s += fmt.Sprintf(" (unknown: %s)", ri.errorText) + s += fmt.Sprintf(", (unknown: %s)", ri.errorText) } else { - s += fmt.Sprintf(" %s", ri.installedVer.String()) + if ri.installedVer.Commit == "" { + s += fmt.Sprintf(", %s", ri.installedVer.String()) + } if ri.dirtyState != "" { - s += fmt.Sprintf(" (dirty: %s)", ri.dirtyState) + s += fmt.Sprintf(", (dirty: %s)", ri.dirtyState) } if ri.needsUpgrade { - s += " (needs upgrade)" + s += ", (needs upgrade)" } } util.StatusMessage(util.VERBOSITY_DEFAULT, "%s\n", s) diff --git a/newt/newtutil/repo_version.go b/newt/newtutil/repo_version.go index 5e64b42..b8516db 100644 --- a/newt/newtutil/repo_version.go +++ b/newt/newtutil/repo_version.go @@ -71,31 +71,40 @@ func (v *RepoVersion) toComparable() RepoVersion { return clone } -func CompareRepoVersions(v1 RepoVersion, v2 RepoVersion) int64 { +func CompareRepoVersions(v1 RepoVersion, v2 RepoVersion) int { v1 = v1.toComparable() v2 = v2.toComparable() + toInt := func(i64 int64) int { + if i64 < 0 { + return -1 + } else if i64 > 0 { + return 1 + } else { + return 0 + } + } + if r := v1.Major - v2.Major; r != 0 { - return r + return toInt(r) } if r := v1.Minor - v2.Minor; r != 0 { - return r + return toInt(r) } if r := v1.Revision - v2.Revision; r != 0 { - return r + return toInt(r) } return 0 } -// XXX: Remove this -func (v *RepoVersion) Satisfies(verReq RepoVersion) bool { - return CompareRepoVersions(verReq, *v) == 0 -} - func (ver *RepoVersion) String() string { + if ver.Commit != "" { + return ver.Commit + } + s := fmt.Sprintf("%d", ver.Major) if ver.Minor != VERSION_FLOATING { s += fmt.Sprintf(".%d", ver.Minor) @@ -108,10 +117,6 @@ func (ver *RepoVersion) String() string { s += fmt.Sprintf("-%s", ver.Stability) } - if ver.Commit != "" { - s += fmt.Sprintf("/%s", ver.Commit) - } - return s } diff --git a/newt/project/project.go b/newt/project/project.go index 42e4669..05beb1c 100644 --- a/newt/project/project.go +++ b/newt/project/project.go @@ -189,7 +189,6 @@ func (proj *Project) FindRepoPath(rname string) string { func (proj *Project) GetRepoVersion( rname string) (*newtutil.RepoVersion, error) { - // First, try to read the repo's `version.yml` file. r := proj.repos[rname] if r == nil { return nil, nil diff --git a/newt/repo/repo.go b/newt/repo/repo.go index 075e0bf..17d9e60 100644 --- a/newt/repo/repo.go +++ b/newt/repo/repo.go @@ -43,7 +43,6 @@ const REPO_NAME_LOCAL = "local" const REPO_DEFAULT_PERMS = 0755 const REPO_FILE_NAME = "repository.yml" -const REPO_VER_FILE_NAME = "version.yml" const REPOS_DIR = "repos" type Repo struct { diff --git a/newt/repo/version.go b/newt/repo/version.go index 561477e..5f0329b 100644 --- a/newt/repo/version.go +++ b/newt/repo/version.go @@ -26,14 +26,10 @@ import ( log "github.com/sirupsen/logrus" - "mynewt.apache.org/newt/newt/config" "mynewt.apache.org/newt/newt/newtutil" "mynewt.apache.org/newt/util" ) -var versionYmlMissing = util.FmtNewtError("version.yml missing") -var versionYmlBad = util.FmtNewtError("version.yml bad") - func versString(vers []newtutil.RepoVersion) string { s := "[" @@ -123,6 +119,16 @@ func (r *Repo) CommitFromVer(ver newtutil.RepoVersion) (string, error) { return commit, nil } +func (r *Repo) VersionIsValid(ver newtutil.RepoVersion) bool { + if ver.Commit == "" { + _, err := r.CommitFromVer(ver) + return err == nil + } + + cs, _ := r.downloader.CommitsFor(r.Path(), ver.Commit) + return len(cs) > 0 +} + // Determines whether the two specified commits refer to the same point in the // repo's history. func (r *Repo) CommitsEquivalent(c1 string, c2 string) (bool, error) { @@ -302,113 +308,15 @@ func (r *Repo) VersionsEqual(v1 newtutil.RepoVersion, return h1 == h2 } -// Parses the `version.yml` file at the specified path. On success, the parsed -// version is returned. -func parseVersionYml(path string) (newtutil.RepoVersion, error) { - yc, err := config.ReadFile(path) - if err != nil { - if util.IsNotExist(err) { - return newtutil.RepoVersion{}, versionYmlMissing - } else { - return newtutil.RepoVersion{}, versionYmlBad - } - } - - verString, err := yc.GetValString("repo.version", nil) - util.OneTimeWarningError(err) - - if verString == "" { - return newtutil.RepoVersion{}, versionYmlBad - } - - ver, err := newtutil.ParseRepoVersion(verString) - if err != nil || !ver.IsNormalized() { - return newtutil.RepoVersion{}, versionYmlBad - } - - return ver, nil -} - -// Reads and parses the `version.yml` file belonging to an installed repo. -func (r *Repo) installedVersionYml() (*newtutil.RepoVersion, error) { - ver, err := parseVersionYml(r.Path() + "/" + REPO_VER_FILE_NAME) - if err != nil { - return nil, err - } - - return &ver, nil -} - -// Downloads and parses the `version.yml` file from the repo at the specified -// commit. -func (r *Repo) nonInstalledVersionYml( - commit string) (*newtutil.RepoVersion, error) { - - filePath, err := r.downloadFile(commit, REPO_VER_FILE_NAME) - if err != nil { - // The download failed. Determine if the commit string is bad or if - // the file just doesn't exist in that commit. - if _, e2 := r.downloader.CommitType(r.localPath, commit); e2 != nil { - // Bad commit string. - return nil, err - } - - // The commit exists, but it doesn't contain a `version.yml` file. - // Assume the commit corresponds to version 0.0.0. - return nil, versionYmlMissing - } - - ver, err := parseVersionYml(filePath) - if err != nil { - return nil, err - } - - return &ver, nil -} - -// Tries to determine which repo version meets the specified criteria: -// * Maps to the specified commit string (or an equivalent commit). -// * Is equal to the specified version read from `version.yml` (if not-null). -func (r *Repo) inferVersion(commit string, vyVer *newtutil.RepoVersion) ( - *newtutil.RepoVersion, error) { - +// Tries to determine which repo version maps to the specified commit string +// (or an equivalent commit). +func (r *Repo) inferVersion(commit string) (*newtutil.RepoVersion, error) { // Search `repository.yml` for versions that the specified commit maps to. ryVers, err := r.VersFromEquivCommit(commit) if err != nil { return nil, err } - // If valid versions were derived from both `version.yml` and the specified - // commit+`repository.yml`, look for a common version. - if vyVer != nil { - if len(ryVers) > 0 { - for _, cv := range ryVers { - if newtutil.CompareRepoVersions(*vyVer, cv) == 0 { - return vyVer, nil - } - } - - util.OneTimeWarning( - "Version mismatch in %s:%s; repository.yml:%s, version.yml:%s", - r.Name(), commit, versString(ryVers), vyVer.String()) - } else { - // If the set of commits doesn't contain a version from - // `repository.yml`, record the commit hash in the version - // specifier. This will distinguish the returned version from its - // corresponding official release. - hash, err := r.downloader.HashFor(r.Path(), commit) - if err != nil { - return nil, err - } - vyVer.Commit = hash - } - - // Always prefer the version in `version.yml`. - log.Debugf("Inferred version %s from %s:%s from version.yml", - vyVer.String(), r.Name(), commit) - return vyVer, nil - } - if len(ryVers) > 0 { log.Debugf("Inferred version %s for %s:%s from repository.yml", ryVers[0].String(), r.Name(), commit) @@ -421,11 +329,6 @@ func (r *Repo) inferVersion(commit string, vyVer *newtutil.RepoVersion) ( // Retrieves the installed version of the repo. Returns nil if the version // cannot be detected. func (r *Repo) InstalledVersion() (*newtutil.RepoVersion, error) { - vyVer, err := r.installedVersionYml() - if err != nil && err != versionYmlMissing && err != versionYmlBad { - return nil, err - } - hash, err := r.CurrentHash() if err != nil { return nil, err @@ -434,7 +337,7 @@ func (r *Repo) InstalledVersion() (*newtutil.RepoVersion, error) { return nil, nil } - ver, err := r.inferVersion(hash, vyVer) + ver, err := r.inferVersion(hash) if err != nil { return nil, err } @@ -447,30 +350,10 @@ func (r *Repo) InstalledVersion() (*newtutil.RepoVersion, error) { func (r *Repo) NonInstalledVersion( commit string) (*newtutil.RepoVersion, error) { - ver, versionYmlErr := r.nonInstalledVersionYml(commit) - if versionYmlErr != nil && - versionYmlErr != versionYmlMissing && - versionYmlErr != versionYmlBad { - - return nil, versionYmlErr - } - - ver, err := r.inferVersion(commit, ver) + ver, err := r.inferVersion(commit) if err != nil { return nil, err } - if ver == nil { - if versionYmlErr == versionYmlMissing { - util.OneTimeWarning( - "%s:%s does not contain a `version.yml` file.", - r.Name(), commit) - } else if versionYmlErr == versionYmlBad { - util.OneTimeWarning( - "%s:%s contains a malformed `version.yml` file.", - r.Name(), commit) - } - } - return ver, nil }
