(swift package index) knowledge sharing: dependency graph evolution over time

Evolution Discussion
1

there is no swiftpackageindex.com topic, so i am posting this here.

one of the issues i’m currently running into with the swiftinit.org reference docs is how to model the evolution of package dependency graphs across different package versions/toolchain tags. in particular, i assume that there are two main axes by which different package+version tuples can depend on each other:

  1. “spatial” dependency, e.g. swift-foo @ v0.1.0 depends on swift-bar @ v0.1.3

  2. “temporal” dependency, e.g. swift-foo @ v0.2.0 depends on swift-foo @ v0.1.0.

obviously we can compute a “spatial” DAG for the ecosystem through the process of dependency resolution, so we can just cross-link API docs by loading the packages’ documentation in the sort-order of the directed graph. and we can do something similar for the temporal axis.

however, it has dawned on me that the combined ecosystem dependency graph for both spatial and temporal dependencies can contain cycles, if the polarity of a dependency reverses between package versions.

Y ← X := “X depends on Y”

1. `png` 3.0.0 depends on `swift-image-tools`
2. `swift-image-tools` depends on `swift-png` 4.0.2 
3. `swift-png` 4.0.2 is a newer version of `png`, 
    which was renamed to `swift-png`

   png  ←---------- swift-png  
  3.0.0               4.0.2
        ↘           ↗
      swift-image-tools
            0.2.0

since the SPM has no well-behaved notion of package identity, it will not detect the dependency cycle while compiling png 3.0.0, since it considers swift-png a distinct package. it can end up depending on a future version of itself if, for example, swift-image-tools overwrites the v0.2.0 git tag which is apparently commonplace enough among the ecosystem that we probably need to handle it.

this sounds like a problem that swiftpackageindex.com may have already encountered, so rather than re-inventing the wheel here, i was wondering how the swiftpackageindex.com site has dealt with this problem, and if any useful insights been learned already?

cc: @finestructure @daveverwer

1 Like
2

If I follow your problem description, you're concerned about a cycle not in the "SPM package resolution" sense per se but rather in the sense that drawing a DAG of package dependencies over time might contain cycles.

We certainly haven't encountered any issues. Or rather, if we would, my guess is they'd just be "normal" package resolution problems. The way I understand your example is that in such a case, swift package resolve would simply fail, because it would resolve conflicting package versions (leaving aside how packages are identified for the moment).

I guess the edge case you describe would eventually be solved via the proposed package identities and a package registry. But since the repository owner is part of the package url I'm not sure how likely it is for surprising or malicious package mismatches to happen in this scenario, even without ids.

I mean, I guess you could make someone accidentally import a different one of your packages by shuffling them around. But anything you could do in that package you could have easily done in the original one to begin with.

1 Like
3

how is the SPI site currently handling repo migrations? it looks like png is returning a 404, even though the GitHub URL is still redirecting properly.

4

We detect redirects in a nightly job which adds the "new" package and removes the "old" one: swift-png – Swift Package Index

I suppose we could improve the 404 page by detecting that the redirect of the package you're trying to browse is actually in the index and offer it as a link instead of the "Add this package" button (which would fail, because adding the package does detect it's a duplicate later on in the flow).

2 Likes