A complete(?) algorithm to resolve dependencies in the SPDX 3 model

[maxhbr]

Here I want to try to find a complete and correct algorithm to identify the direct dependencies of some package element.

Assumptions:

• we are within some SPDX data, e.g. the result of parsing a SPDX json file
• we know a Package (called $package), as a starting point.
• this talks about validity of relationships, which was proposed

The Algorihm:

(one initially should freeze some timestamp, that is used to identify validity, to avoid inconsistencies)

Step 1: early exit

Step 1.a: Look, that the type is matching

• If the $package element is not a /Software/Package, this algorithm shall fail

Step 1.b: Look at relations

If there is a validity date attached to relations, this needs to be respected and relations need to be filtered accordingly.

• If there is a relation of the kind other, this algorithm shall fail, as a human needs to read the comment
• If there is an amends relation going out of $package to $otherElement, one should instead resolve its dependencies
  • if there is exactly one, run the algorithm with the $otherElement
  • unless there is one or multiple amends relations that amend the amends relation
    • ... (recursively)
  • if there are multiple, this algorithm shall fail
• If there is a Bundle, that is linked with a describes relation to $package, that bundle probably describes the dependencies.
  • this algorithm shall fail, if it is probably the wrong approach
  • if there are also dependsOn or other relevant relation, this might be conflicting information

Step 2: identify relevant relationships

If there is a validity date attached to relations, this needs to be respected and relations need to be filtered accordingly.

Step 2.a:

• Find all relationships outgoing from $package, of the type dependsOn
  • for every relation
  • drop, if no longer valid
  • if there is a amends relationship between this and something else, follow that
    • unless there is one or multiple amends relations that amend this amends relation
    • ... (recursively)
  • if there is any other relation attached, this algorithm shall fail, as a human needs to read the comment
  • fail, if the item on the other end are not just packages
• de-duplicate these relations, since amends relations might have caused duplicates

Step 2.b:

• if more then one of the found relationships have completeness == complete, this shall fail as it is inconsistent information

Step 2.c:

• merge all packages from the to side
  • remove duplicates

Step 3:

• if there is another package contained in $packege via contains relationship, also resolve its dependencies and merge it into the above list

Output:

The result is the merged list of all above found artifacts.

Transitive dependencies:

To collect transitive dependencies, one should recursively call the above algorithm, with some kind of cycle detection

Questions:

• is that approach valid?
• what to do, if there is something linked with the dependencyManifest relation?
• how to handle requirementFor?

[kestewart]

@iamwillbar - does the flow as Max articulates, align with your understanding?

[goneall]

This should probably be re-worked for the latest relationship definitions.

I don't think this will impact the 3.0 spec - moving to 3.1