ccollins476ad closed pull request #235: resolve: Prune orphan packages during
dependency resolution
URL: https://github.com/apache/mynewt-newt/pull/235
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git a/newt/resolve/resolve.go b/newt/resolve/resolve.go
index a85c97e5..ef13e6a4 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
@@ -89,9 +90,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 {
@@ -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(),
@@ -169,6 +171,7 @@ func NewResolvePkg(lpkg *pkg.LocalPackage) *ResolvePackage {
Lpkg: lpkg,
reqApiMap: map[string]resolveReqApi{},
Deps: map[*ResolvePackage]*ResolveDep{},
+ revDeps: map[*ResolvePackage]struct{}{},
}
}
@@ -187,17 +190,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 +215,8 @@ func (rpkg *ResolvePackage) AddDep(
rpkg.reqApiMap[api] = apiReq
}
- apiPkg.refCount++
+ depPkg.revDeps[rpkg] = struct{}{}
+
return true
}
@@ -338,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 a reference count of one),
delete
- // them as well.
- for rdep, _ := range rpkg.Deps {
- if rdep.refCount <= 0 {
+ // 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 dep, _ := range rpkg.Deps {
+ if len(dep.revDeps) == 0 {
return util.FmtNewtError(
- "package %s unexpectedly has refcount <= 0",
- rdep.Lpkg.FullName())
+ "package %s unexpectedly has 0 reverse
dependencies",
+ dep.Lpkg.FullName())
}
- rdep.refCount--
- if rdep.refCount == 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
}
}
}
@@ -406,12 +416,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
}
@@ -476,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
@@ -510,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
}
@@ -535,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
}
@@ -554,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
}
}
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
