You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mynewt.apache.org by cc...@apache.org on 2018/11/14 17:02:23 UTC
[mynewt-newt] branch master updated (4353b71 -> 88ad5de)
This is an automated email from the ASF dual-hosted git repository.
ccollins pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/mynewt-newt.git.
from 4353b71 Update newt version: 1.4.9999 --> 1.5.9900
new a1d3d27 resolve: Maintain reverse dependency list per-pkg
new 88ad5de resolve: Prune orphan packages during dep resolutn
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
newt/resolve/resolve.go | 158 +++++++++++++++++++++++++++++++++++-------------
1 file changed, 115 insertions(+), 43 deletions(-)
[mynewt-newt] 01/02: resolve: Maintain reverse dependency list
per-pkg
Posted by cc...@apache.org.
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 a1d3d2722a36e76779a929fb9c3074dfd9ea26f1
Author: Christopher Collins <cc...@apache.org>
AuthorDate: Wed Nov 7 09:46:18 2018 -0800
resolve: Maintain reverse dependency list per-pkg
Replace `ResolvePackage`'s reference count with a reverse dependency
list (implemented as map). This is less error prone, and it allows for
package removal to be more efficient.
---
newt/resolve/resolve.go | 34 ++++++++++++++++++----------------
1 file changed, 18 insertions(+), 16 deletions(-)
diff --git a/newt/resolve/resolve.go b/newt/resolve/resolve.go
index a85c97e..02d69f9 100644
--- a/newt/resolve/resolve.go
+++ b/newt/resolve/resolve.go
@@ -89,9 +89,9 @@ type ResolvePackage struct {
depsResolved bool
- // Tracks this package's number of dependents. If this number reaches 0,
- // this package can be deleted from the resolver.
- refCount int
+ // Tracks this package's dependents (things that depend on us). If this
+ // map becomes empty, this package can be deleted from the resolver.
+ revDeps map[*ResolvePackage]struct{}
}
type ResolveSet struct {
@@ -169,6 +169,7 @@ func NewResolvePkg(lpkg *pkg.LocalPackage) *ResolvePackage {
Lpkg: lpkg,
reqApiMap: map[string]resolveReqApi{},
Deps: map[*ResolvePackage]*ResolveDep{},
+ revDeps: map[*ResolvePackage]struct{}{},
}
}
@@ -187,17 +188,17 @@ func (r *Resolver) resolveDep(dep *pkg.Dependency, depender string) (*pkg.LocalP
// @return true if the package's dependency list was
// modified.
func (rpkg *ResolvePackage) AddDep(
- apiPkg *ResolvePackage, api string, expr string) bool {
+ depPkg *ResolvePackage, api string, expr string) bool {
- if dep := rpkg.Deps[apiPkg]; dep != nil {
+ if dep := rpkg.Deps[depPkg]; dep != nil {
if dep.Api != "" && api == "" {
dep.Api = api
} else {
return false
}
} else {
- rpkg.Deps[apiPkg] = &ResolveDep{
- Rpkg: apiPkg,
+ rpkg.Deps[depPkg] = &ResolveDep{
+ Rpkg: depPkg,
Api: api,
Expr: expr,
}
@@ -212,7 +213,8 @@ func (rpkg *ResolvePackage) AddDep(
rpkg.reqApiMap[api] = apiReq
}
- apiPkg.refCount++
+ depPkg.revDeps[rpkg] = struct{}{}
+
return true
}
@@ -339,16 +341,16 @@ func (r *Resolver) deletePkg(rpkg *ResolvePackage) error {
r.cfg.DeletePkg(rpkg.Lpkg)
// If the deleted package is the only depender for any other packages
- // (i.e., if any of its dependencies have a reference count of one), delete
- // them as well.
+ // (i.e., if any of its dependencies have only one reverse dependency),
+ // delete them as well.
for rdep, _ := range rpkg.Deps {
- if rdep.refCount <= 0 {
+ if len(rdep.revDeps) == 0 {
return util.FmtNewtError(
- "package %s unexpectedly has refcount <= 0",
+ "package %s unexpectedly has 0 reverse dependencies",
rdep.Lpkg.FullName())
}
- rdep.refCount--
- if rdep.refCount == 0 {
+ delete(rdep.revDeps, rpkg)
+ if len(rdep.revDeps) == 0 {
if err := r.deletePkg(rdep); err != nil {
return nil
}
@@ -406,12 +408,12 @@ func (r *Resolver) loadDepsForPkg(rpkg *ResolvePackage) (bool, error) {
for rdep, _ := range rpkg.Deps {
if _, ok := seen[rdep]; !ok {
delete(rpkg.Deps, rdep)
- rdep.refCount--
+ delete(rdep.revDeps, rpkg)
changed = true
// If we just deleted the last reference to a package, remove the
// package entirely from the resolver and syscfg.
- if rdep.refCount == 0 {
+ if len(rdep.revDeps) == 0 {
if err := r.deletePkg(rdep); err != nil {
return true, err
}
[mynewt-newt] 02/02: resolve: Prune orphan packages during dep
resolutn
Posted by cc...@apache.org.
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 88ad5de6f0826c71f961adba6c907e27e18755b4
Author: Christopher Collins <cc...@apache.org>
AuthorDate: Tue Nov 6 17:18:02 2018 -0800
resolve: Prune orphan packages during dep resolutn
This fixes #233.
Detect orphan packages as follows: starting from each seed package,
recursively traverse the package's dependency list, keeping track of
which packages were visited. After the traversal is complete, any
non-visited package in the resolver are orphans and can be removed.
---
newt/resolve/resolve.go | 132 ++++++++++++++++++++++++++++++++++++------------
1 file changed, 101 insertions(+), 31 deletions(-)
diff --git a/newt/resolve/resolve.go b/newt/resolve/resolve.go
index 02d69f9..ef13e6a 100644
--- a/newt/resolve/resolve.go
+++ b/newt/resolve/resolve.go
@@ -58,6 +58,7 @@ type resolveReqApi struct {
type Resolver struct {
apis map[string]resolveApi
pkgMap map[*pkg.LocalPackage]*ResolvePackage
+ seedPkgs []*pkg.LocalPackage
injectedSettings map[string]string
flashMap flash.FlashMap
cfg syscfg.Cfg
@@ -134,6 +135,7 @@ func newResolver(
r := &Resolver{
apis: map[string]resolveApi{},
pkgMap: map[*pkg.LocalPackage]*ResolvePackage{},
+ seedPkgs: seedPkgs,
injectedSettings: injectedSettings,
flashMap: flashMap,
cfg: syscfg.NewCfg(),
@@ -340,19 +342,25 @@ func (r *Resolver) deletePkg(rpkg *ResolvePackage) error {
// Delete the package from syscfg.
r.cfg.DeletePkg(rpkg.Lpkg)
- // If the deleted package is the only depender for any other packages
- // (i.e., if any of its dependencies have only one reverse dependency),
+ // Remove all dependencies on the deleted package.
+ for revdep, _ := range rpkg.revDeps {
+ delete(revdep.Deps, rpkg)
+ }
+
+ // Remove all reverse dependencies pointing to the deleted package. If the
+ // deleted package is the only depender for any other packages (i.e., if
+ // any of its dependencies have only one reverse dependency),
// delete them as well.
- for rdep, _ := range rpkg.Deps {
- if len(rdep.revDeps) == 0 {
+ for dep, _ := range rpkg.Deps {
+ if len(dep.revDeps) == 0 {
return util.FmtNewtError(
"package %s unexpectedly has 0 reverse dependencies",
- rdep.Lpkg.FullName())
+ dep.Lpkg.FullName())
}
- delete(rdep.revDeps, rpkg)
- if len(rdep.revDeps) == 0 {
- if err := r.deletePkg(rdep); err != nil {
- return nil
+ delete(dep.revDeps, rpkg)
+ if len(dep.revDeps) == 0 {
+ if err := r.deletePkg(dep); err != nil {
+ return err
}
}
}
@@ -478,31 +486,94 @@ func (r *Resolver) reloadCfg() (bool, error) {
return false, nil
}
-func (r *Resolver) resolveDepsOnce() (bool, error) {
- // Circularly resolve dependencies, APIs, and required APIs until no new
- // ones exist.
- newDeps := false
- for {
- reprocess := false
- for _, rpkg := range r.pkgMap {
- newDeps, err := r.resolvePkg(rpkg)
- if err != nil {
+// @return bool True if any packages were pruned, false
+// otherwise.
+// @return err Error
+func (r *Resolver) pruneOrphans() (bool, error) {
+ seenMap := map[*ResolvePackage]struct{}{}
+
+ // This function traverses the specified package's dependency list,
+ // recording each visited packges in `seenMap`.
+ var visit func(rpkg *ResolvePackage)
+ visit = func(rpkg *ResolvePackage) {
+ if _, ok := seenMap[rpkg]; ok {
+ return
+ }
+
+ seenMap[rpkg] = struct{}{}
+ for dep, _ := range rpkg.Deps {
+ visit(dep)
+ }
+ }
+
+ // Starting from each seed package, recursively traverse the package's
+ // dependency list, keeping track of which packages were visited.
+ for _, lpkg := range r.seedPkgs {
+ rpkg := r.pkgMap[lpkg]
+ if rpkg == nil {
+ panic("Resolver lacks mapping for seed package " + lpkg.FullName())
+ }
+
+ visit(rpkg)
+ }
+
+ // Any non-visited packages in the resolver are orphans and can be removed.
+ anyPruned := false
+ for _, rpkg := range r.pkgMap {
+ if _, ok := seenMap[rpkg]; !ok {
+ anyPruned = true
+ if err := r.deletePkg(rpkg); err != nil {
return false, err
}
+ }
+ }
- if newDeps {
- // The new dependencies need to be processed. Iterate again
- // after this iteration completes.
- reprocess = true
- }
+ return anyPruned, nil
+}
+
+func (r *Resolver) resolveHardDepsOnce() (bool, error) {
+ // Circularly resolve dependencies, APIs, and required APIs until no new
+ // ones exist.
+ reprocess := false
+ for _, rpkg := range r.pkgMap {
+ newDeps, err := r.resolvePkg(rpkg)
+ if err != nil {
+ return false, err
}
- if !reprocess {
- break
+ if newDeps {
+ // The new dependencies need to be processed. Iterate again
+ // after this iteration completes.
+ reprocess = true
}
}
- return newDeps, nil
+ if reprocess {
+ return true, nil
+ }
+
+ // Now prune orphan packages.
+ anyPruned, err := r.pruneOrphans()
+ if err != nil {
+ return false, err
+ }
+
+ return anyPruned, nil
+}
+
+// Fully resolves all hard dependencies (i.e., packages listed in `pkg.deps`;
+// not API dependencies).
+func (r *Resolver) resolveHardDeps() error {
+ for {
+ reprocess, err := r.resolveHardDepsOnce()
+ if err != nil {
+ return err
+ }
+
+ if !reprocess {
+ return nil
+ }
+ }
}
// Given a fully calculated syscfg and API map, resolves package dependencies
@@ -512,7 +583,7 @@ func (r *Resolver) resolveDepsOnce() (bool, error) {
// resolved separately, after the master syscfg and API map have been
// calculated.
func (r *Resolver) resolveDeps() ([]*ResolvePackage, error) {
- if _, err := r.resolveDepsOnce(); err != nil {
+ if err := r.resolveHardDeps(); err != nil {
return nil, err
}
@@ -537,7 +608,7 @@ func (r *Resolver) resolveDeps() ([]*ResolvePackage, error) {
// 2. Determines which packages satisfy which API requirements.
// 3. Resolves package dependencies by populating the resolver's package map.
func (r *Resolver) resolveDepsAndCfg() error {
- if _, err := r.resolveDepsOnce(); err != nil {
+ if err := r.resolveHardDeps(); err != nil {
return err
}
@@ -556,12 +627,11 @@ func (r *Resolver) resolveDepsAndCfg() error {
}
}
- newDeps, err := r.resolveDepsOnce()
- if err != nil {
+ if err := r.resolveHardDeps(); err != nil {
return err
}
- if !newDeps && !cfgChanged {
+ if !cfgChanged {
break
}
}