RFC: Design improved relationships for Package, Dependencies, Embeds and Requirements

[pombredanne]

We need to design improved models for Package, Dependencies, Embeds and Requirements.

Some background:

• What we routinely calls "dependencies" are not really dependencies: more often these are requirements that are "resolved" to actual concrete dependencies. To really "depend" on a software package, you need to know the exact resolved version. On the other hand, a requirement expresses the need for some range of versions (even if it's a range of a single version).

• We should distinguish a "require" relationship between packages vs. an actual "resolved" dependency to a concrete version, and track if the resolved dependency is present in the codebase or not.

• Dependencies (or requirements) may be only documented in a package manifest (like pom.xml) or a lockfile (like package-lock.json), or also be present in the codebase.

• We need to track also when a package contains another package (or for that matter when an app contains or embeds packages).

Therefore we may have three levels of tree-like data we need to track for packages:

• "potential" requirements (we call these dependencies today). This is a logically a flat list of PURLs with VERS attached to a package instance.
• "resolved" dependencies (we call these dependencies today too, but sometimes also packages). This is logically a tree (or graph) of PURLs with a resolved version. Each such dependency is derived and satisfies one or more "requirement".
• "embeds" are packages embedded in other packages, e.g., they are physically copied, vendor and or built into a product codebase. These could have been the results of provisioning/fetching resolved dependencies, or could be a straight copy. These are not much tracked as such today.

We have agreed on some key model updates, based on discussions here and in our weekly calls:

• Enhance ScanCode.io models to support relating dependencies to packages
• Enhance ScanCode Toolkit models to support relating dependencies to packages
• DJC: Enhance DejaCode models to support relating dependencies to packages dejacode#138
• Enhance PurlDB models to support relating dependencies to packages purldb#485
• Enhance python-inspector models to support relating dependencies to packages using the new models
• Enhance nuget-inspector models to support relating dependencies to packages using the new models
• Create dependency-inspector to relate dependencies to packages using the new models

The https://github.com/nexB/dependency-inspector tickets to create lockfiles are:

• Create a yarn.lock lock file with yarn dependency-inspector#3
• Create lock file with pnpm dependency-inspector#5
• Create a package-json.lock lock file with npm dependency-inspector#4
• Create SwiftPM lockfile dependency-inspector#12
• Create cocoapods lockfile dependency-inspector#10
• Create Python frozen requirements file dependency-inspector#8
• Create .Net lock file with dotnet restore and other built in commands dependency-inspector#11

Then for the effective resolution of dependencies as a tree from manifests and lockfiles:

• npm: SCIO: Lock and resolve locked npm dependencies from yarn and npm #1201 and SCIO: Resolve npm dependencies based on lockfiles #1237
• pypi: SCIO: Detect frozen Python requirements locked with deplock #1262
• nuget: SCIO: Detect frozen .NuGet dependencies locked with deplock #1263
• cocoapods: SCIO: Detect and resolve locked Cocoapods requirements #1279
• swift: SCIO: Detect and resolve locked Swift requirements #1278

And beyond:

• Extend Lockfile checker and generator dependency-inspector#13

Here are also some related issues, but not directly need to complete this feature:

• Support packages embedded in other packages
  • RFC: Introduce "primary package" vs. "embedded- or sub-packages" scancode-toolkit#2418
  • RFC: Introduce idea of embedded package purldb#177
  • Store if source code file paths contain "third party" hints purldb#163
• Improve the definition of a package and dependency
  • Definitions for DiscoveredPackage and DiscoverdDependency are very different #885
  • Should a dependency tree be scoped to a single project ? #888
• Introduce successor packages Introduce the concept of a "successor package" to the purldb data model purldb#175
• and also https://github.com/nexB/python-inspector, https://github.com/nexB/nuget-inspector and other inspectors.

[pombredanne]

Note that this is as much for ScanCode.io as it is for ScanCode Toolkit, DejaCode and PurlDB

[AyanSinhaMahapatra]

Summarizing the discussion we had on the community call on this issue:

We need to have dependencies also as packages, and not
as a separate model (with the skinny purl-only package data and optionally
resolved packages nested inside) we have today. And dependencies here
would be preserved as relationships between these packages, and the actual
primary package -> secondary packages (either dependencies/embedded packages)
would also be preserved by creating relationships between them.

Here we have some types of packages:

1. Primary package instances
2. Resolved package dependency with package data/files
3. Resolved package dependency without package data/files (just PURL)
4. Secondary/Embedded package (files embedded in primary package files)
5. Package requirements (package + version range)

This approach has some benefits:

• We don't have to change massively our package models, just some attribute addition/deletion
  as we are changing how we report the data within those models, and the output format
  remains the same essentially.
• Resolved packages won't be nested, everything will be there as package instances.
• This is straightforward, as dependency is really a relationship and not a separate model.
• Similar to what users expect/other tools provide, and essentially what we will have if
  we scan a package with pre-resolved dependencies present in the code tree, there too
  since we have the packages detected as instances, we have them as packages.

For example, in SCIO we could have filters for primary packages, secondary/embedded packages,
so that these are differentiated and looked at separately as required, and the dependency tab
could have the relations between them.

Two possible implementations in this:

a) We have everything (packages, resolved/embedded dependencies, dependency purls and even requirements)
returned as Packages.

• Would be less confusing and straightforward, having everything stored similarly.
• We can do a resolve requirements to the oldest version available within
  the required versions, or something similar, to have a proper package instance.

b) We have everything else but requirements (packages, resolved/embedded dependencies, dependency purls)
as packages. Requirements (does not have exact version, therefore does not point to a package)

• Requirements do not have a version, so these aren't really package instances as
  they are not concrete packages which can be identified in a unique way. So these
  should not be confused with packages.
• Even for dependency purls we can get package metadata/download the packages and scan them, but we
  cannot do the same for dependency requirements, as they are not package instances.
• If we try to resolve these dependency requirements incorrectly (to the oldest version available within
  the required versions) this would be incorrect and misleading for any compliance. As package licenses
  could change between versions and without correct versions we cannot check vulnerabilities. So these
  are essentially false positives.

cc @pombredanne @tdruez

[pombredanne]

The latest design is to go in this direction:

• We are transforming the DiscoveredDependency model to add a foreign key to the corresponding resolved DiscoveredPackage something like a "resolved_to" relationship
• We will have a dependency resolution process in a pipeline where we look at the dependencies and resolve them to actual found packages or can also use a resolver, even if very crude.
• We may also track if a package is physically found on disk in a codebase
• This can stay optional
• We will need to ensure that we are doing the right thing too on the scancode toolkit side
• The same solution will be then propagated to PurlDB and possibly to DejaCode

See also attached:

To clarify, we would go with option 1:

1. We do not create a "resolved to" until we "run" a resolution

2. We resolve as below possibly in a dumb way. We are aware that looking for the latest version of a package is a somewhat dumb "mock resolution" and may not have a lot of value

3. When we have a lockfile (that contains pinned dependencies) we could create the "resolved to" Package at the same time

4. When we have already existing Packages and a Dependencies, we should be able to relate as a resolution the existing Packages (a sort of mock resolution

[pombredanne]

@AyanSinhaMahapatra I had some other notes too... did you capture some?

[pombredanne]

We have a mostly working PR with #896 by @Hritik14

[tdruez]

I would recommend an implementation in multiple stages:

1. Add new resolved_to field on DiscoveredDependency #1066 #1240
2. Add the resolution processing to create packages and feed the new resolved_to field. That's also at that time we can add the new DiscoveredPackage fields that will help to qualify the package "level" regarding the dependency tree.
3. Add the methods to collect and use the dependency tree within a project and include the tree in the outputs such as CycloneDX.

[tdruez]

@AyanSinhaMahapatra The new resolved_to field is now merged.

Could you start a PR on the resolution part? #1066 (comment)
As a side note we want to keep the resolution tree, meaning a package defined as resolved_to can also be defined as a for_package. The model should support this approach fine.

[pombredanne]

Here are some notes as how I understand this model will work:

We are updating these existing relationships (and their reverses):

• DiscoveredDependency > for_package > DiscoveredPackage
• DiscoveredPackage > declared_dependencies > DiscoveredDependency

We are creating these new relationships (and their reverses):

• DiscoveredDependency > resolved_to > DiscoveredPackage
• DiscoveredPackage > resolved_dependencies > DiscoveredDependency

A resolution would start with this:

1. Starting "universe":

foo@1.2
 - direct deps: bar > 2.0
 
bar@3.0
 - direct deps: baz >= 1.0

baz@1.0
 - direct deps: None

2. If we resolve for foo@1.2 then the Tree is:

foo@1.2
 - direct deps: bar > 2.0
   - resolved_to: bar@3.0
     - direct deps: baz >= 1.0
       - resolved_to: baz@1.0

[Hritik14]

As per above and #896, now ResolvedDependency instead of being a concrete model of its own will act as an associative table that connects any two DiscoveredPackage in a many-to-many fashion.
This looks like the following:

Now, adding the above suggestion of direct deps or requirement might look something like:

A package has requirements, a requirement resolves to a dependency and a dependency maps to a package. Packages retain their many to many relationship via the dependency associative but every dependency also has a one to one relationship with a requirement.

@tdruez
#1240 looks good to me, although should we call resolved_dependencies as resolved_parents or just parents ? Having declared_dependencies and resolved_dependencies both on DiscoveredPackage does not make sense.

[pombredanne]

@Hritik14 If I expand on the topic of #1066 (comment) then we have these records and relationships (I have added a few extra packages/deps)

Before resolution:

• DiscoveredPackage > declared_dependencies > DiscoveredDependency

  foo@1.2                 >             bar > 2.0
  foo@1.2                 >             biz > 3.0
  bar@3.0                 >             baz >= 1.0
  biz@4.0                 >             baz >= 0.1
  baz@1.0

• DiscoveredDependency > for_package > DiscoveredPackage

  bar > 2.0               >             foo@1.2
  biz > 3.0               >             foo@1.2
  baz >= 1.0              >             bar@3.0
  baz >= 0.1              >             biz@4.0

After resolution:

• DiscoveredPackage > resolved_dependencies > DiscoveredDependency

  bar@3.0                 >             bar > 2.0
  baz@1.0                 >             baz >= 1.0
  baz@1.0                 >             baz >= 0.1
  biz@4.0                 >             biz > 3.0

• DiscoveredDependency > resolved_to > DiscoveredPackage

  bar > 2.0               >             bar@3.0
  baz >= 1.0              >             baz@1.0
  baz >= 0.1              >             baz@1.0
  biz > 3.0               >             biz@4.0

What does having an intermediate DiscoveredRequirement brings that we cannot do with the newly updated model? (The idea here is to avoid changing fundamentally the model structure)

With that said resolved_dependencies could be renamed as resolved_from_dependencies as multiple dependencies "requirements" could be resolved to a single version as seen here

[AyanSinhaMahapatra]

Could you start a PR on the resolution part? #1066 (comment)
As a side note we want to keep the resolution tree, meaning a package defined as resolved_to can also be defined as a for_package. The model should support this approach fine.

@tdruez @pombredanne I've added an initial implementation for the resolution process, this is now:

• populating the newly added resolved_to attribute in the dependency relationships
• creating new resolved packages from the resolved_package attribute we have already in SCTK output. This is stored in dependencies for PackageData objects, for the corresponding lockfile resource.
• Added this as optional groups in both resolve_dependencies and inspect_packages pipeline, uses the same function for this. (need feedback on the UI/pipelines flow and group name, is this okay? Or should we do an addon pipeline instead)

Things remaining [WIP]:

• Add also resolved_packages for dependencies in other manifests with is_resolved as True (but these might not have the fully resolved tree, just some pinned dependencies)
• Do some sort of merging of dependency relations (same dependency/requirements present in multiple manifests)
• On the SCTK side improving the dependencies parsing in npm, yarn and pnpm with https://github.com/nexB/scancode-toolkit/tree/improve-npm-support to fully address SCIO: Resolve npm dependencies based on lockfiles #1237

Questions:
I'm not sure on the attribute names for the following:

add the new DiscoveredPackage fields that will help to qualify the package "level" regarding the dependency tree.

Can we implement the above with #880
where we can have some indication of a Package being created from static resolver?

Also, should we use https://github.com/nexB/univers more in SCTK and make sure is_resolved is correctly populated in all cases?

[AyanSinhaMahapatra]

This is now there with 08c54b1 and support has been added for pypi, poetry, swift, nuget, cocoapods, npm, yarn also with additional help from deplock at https://github.com/nexB/dependency-inspector to generate lockfiles if they are not present, and then parse, store and resolve dependencies to form a graph.
Follow up issues are there on scancode-toolkit, dejacode, purldb.
Closing!