API `Distribution.Types.VersionInterval` dropped `intersectVersionIntervals` etc. in 3.6

[andreasabel]

Background: I am looking to implement a check whether some version constraint subsumes another one, for hackage-trustees/hackage-cli#28. We know that a subsumes b can e.g. be implemented as (a intersect b) = b.

I notice that up to 3.4, there was intersectVersionIntervals, and I traced this back to 2.4 (maybe even older).
In 3.6 this function is gone, apparently due to a rewrite:

cabal/Cabal/src/Distribution/Types/VersionInterval.hs

Lines 3 to 6 in 96ea35d

	-- | In @Cabal-3.6@ this module have been rewritten.
	--
	--
	module Distribution.Types.VersionInterval (

It seems that the whole module Distribution.Types.VersionInterval was moved to Distribution.Types.VersionInterval.Legacy and the former module was reimplemented from scratch, but supplying only parts of the former API. The legacy module is announced to be deleted in 3.8.

I propose to restore the deleted functionality to Distribution.Types.VersionInterval, at least the mathematically essential functions. Basically, all the algebraic operations present for the "syntactic" form VersionRange should be implemented for the "semantic" form VersionIntervals as well; both are Boolean algebras.

(For my use in hackage-cli that would mean I could now support 2.4, then upgrade to 3.4, then to 3.8---needing to skip 3.6.)

[phadej]

The legacy intersectVersionIntervals is wrong. It destroys the ^>= semantics. Please, implement proper Intervals, which preserve the ^>= specification: then everyone wins. The refactoring of existing intervals was done to make adding proper ^>= intervals simpler. (There should be hints in the comments).

Until then, just use the Legacy module. It's there exactly for the backward compat.

[andreasabel]

@phadej, I am trying to understand your comment:

The legacy intersectVersionIntervals is wrong. It destroys the ^>= semantics.

According to the docs, https://cabal.readthedocs.io/en/latest/cabal-package.html#pkg-field-build-depends , the semantics of ^>= x is >= x && < x.1 and that of ^>= x.y... is >= x.y... && < x.(y+1). Both the legacy and the new VersionIntervals module implement this semantics.

Further, both modules use the same representation of intervals:

... increasing sequence of non-overlapping, non-empty intervals.
... canonical representation for the semantics of VersionRanges.

Canonical means that different VersionIntervals have different semantics. Thus, the intervals need to be separated (i.e. non-overlapping and non-touching). Given that version intervals form a Boolean algebra the intersectVersionIntervals can only be wrong when it is buggy. I checked but found no bugs.
Note that the requirements of correctness and canonicity leave no wiggle space. Ordered sequences of separated intervals are the and the only representation (there could be different, isormorphic ways of realizing ordered sequences or the individual intervals, but this does not matter here, and is not the case in the two implementation).

So I wonder what can be the difference between the old and the new implementation. Can you provide me evidence that points out the difference, an issue, a unit test, a regression test, an explanation, ...?

[phadej]

According to the docs, https://cabal.readthedocs.io/en/latest/cabal-package.html#pkg-field-build-depends ,

See https://cabal.readthedocs.io/en/3.6/cabal-project.html?highlight=allow-newer#cfg-field-allow-newer

The syntax also allows to prefix the dependee package with a modifier symbol to modify the scope/semantic of the relaxation transformation in a additional ways. Currently only one modifier symbol is defined, i.e. ^ (i.e. caret) which causes the relaxation to be applied only to ^>= operators and leave all other version operators untouched.

The ^>= x.y and >= x.y && <x.(y+1) are not the same. If you wish, latter is a hard bound, former is soft.

---

That is current state. I don't think that many would change soft bounds to hard when evidence arises that the "guess" was in fact correct. But to make the above bounds-specifications exactly the same you need to cleanup docs and remove all other details where they differ (i.e. ^ modifier in allow-newer).

(Note: there was some debate whether cabal should have soft and hard bounds; it has now, but they aren't used. And to repeat, I don't think authors would revise soft bounds to hard ones when releases occur.)

[Mikolaj]

If it's not clear it's really used, could we grep Hackage and verity the situation and, if only possible, RFC and simplify as much as possible?

[phadej]

If it's not clear it's really used,

^>= is definitely used. But I'm 100% it's used as if it had hard semantics.

Whether anyone uses allow-newer: ^foo, we cannot know. I doubt.

EDIT: that (soft vs. hard upper bound distinction) is a feature where small group of power users could use for great benefit (e.g. testing whether new release of a lib breaks everything or not, and then making hard revisions where needed). But Hackage is large group of non-power users: the feature is on the obscure side, not understood, not used "correctly".

[Mikolaj]

Oh, I see. So we'd need a RFC, publicized on https://discourse.haskell.org, asking if anybody really needs it for anything, in particular for allow-newer, given that removing it would simplify API and help tools that use the Cabal library and lessen cabal/tools/others maintenance burden. Who came up with the feature initially, so that we ask for a comment? @gbaz: what do you think?

[phadej]

Who came up with the feature initially

Soft-hard distinction? Herbert.

[andreasabel]

What the new module Distribution.Types.VersionInterval concerns, I cannot see where it reflects the distinction between soft and hard constraints. As I already said, it interprets the caret-operator ^.>= in exactly the same way as the "legacy" module:

cabal/Cabal/src/Distribution/Types/VersionInterval.hs

Lines 96 to 97 in ddb58fb

	-- ^>= version-range's upper bound should be MajorBound
	alg (MajorBoundVersionF v) = [VersionInterval (LowerBound v InclusiveBound) (UpperBound (majorUpperBound v) ExclusiveBound)]

Also, it makes no efforts to recover ^>= when translating back to VersionRange:

cabal/Cabal/src/Distribution/Types/VersionInterval.hs

Lines 294 to 319 in ddb58fb

	intervalToVersionRange :: VersionInterval -> VersionRange
	intervalToVersionRange (VersionInterval (LowerBound v vb) upper') = case upper' of
	NoUpperBound
	-> lowerBound
	UpperBound u ub
	| vb == InclusiveBound
	, ub == InclusiveBound
	, v == u
	-> thisVersion v
	UpperBound u ub -> withLowerBound (makeUpperBound u ub)
	where
	lowerBound :: VersionRange
	lowerBound = case vb of
	InclusiveBound -> orLaterVersion v
	ExclusiveBound -> laterVersion v
	withLowerBound :: VersionRange -> VersionRange
	withLowerBound vr
	| isVersion0 v, vb == InclusiveBound = vr
	| otherwise = intersectVersionRanges lowerBound vr
	makeUpperBound :: Version -> Bound -> VersionRange
	makeUpperBound u InclusiveBound = orEarlierVersion u
	makeUpperBound u ExclusiveBound = earlierVersion u

If one wanted to implement soft constraints, one would have to change/parametrize the translation from VersionRange to VersionIntervals, but at the semantic level, meaning VersionIntervals, there is no soft/hard, it is simply a subset of the set of possible versions.
I do not have to repeat myself that a canonical representation of the semantics leaves not choices on the functionality of intersection/union etc., all implementation are extensionally equivalent.

I notice though that the new implementation regresses asymptotic complexity from O(n+m) to O(nm).
Also, the new implementations are less perspicuous and harder to verify.

My propsal for Distribution.Types.VersionInterval:

• restore the old "legacy" module, except:
• salvage improvements made in the representation (like data instead of tuple`)
• salvage new functionality.

The discussion about soft/hard constraints is orthogonal to the OP and should be happening elsewhere.

[phadej]

As I already said, it interprets the caret-operator

Yes, it does. Because I hadn't time to do the further changes. I said that already.

Also, it makes no efforts to recover ^>= when translating back to VersionRange:

It cannot. The VersionInterval type should preserve the ^>= originated intervals as separate constructor.

[phadej]

If such constructor is added, then (IIRC) modifying intersectInterval, unionUpper, doesNotTouch would be enough for rest of normalization to work. But I never got to make the final change.

Note how in soft semantics, foo: ^>=0.1 && <0.3 makes some sense. the bound behaves differently, depending if you don't allow-newer, allow-newer: foo or allow-newer: ^foo.

distinction could work, if say stackage was always run with allow-newer: ^*, and the negative build results were propagated back as metadata revision. but to repeat myself, I don't think package maintainers would do that.