Implement real version constraint (sat) solver #240

Open
tuncer opened this Issue Mar 5, 2014 · 31 comments

Comments

Projects
None yet
7 participants
Contributor

tuncer commented Mar 5, 2014

I think it's inevitable to eventually implement a real version constraint (sat) solver (e.g >= 1.2.* && < 1.7.*). The various require_*_vsn options and version strings in dependency specs do not cover all real world use cases. @thijsterlouw submitted a patch to implement semver vsn checking. Would that be universal enough, or would it limit what constraints are supported?

See #163 #222 basho/rebar#262 basho/rebar#263

yfyf commented Mar 6, 2014

I'm considering implementing this, however I'm thinking of what's a good way to handle more complicated versioning, e.g. fork / patch / build tags. The original implementation of @thijsterlouw is workable, but does not cover many corner cases, like untagged / weirdly tagged dependencies.

One approach is to follow the semver spec 2.0, however it is slightly inconvenient in this context, e.g. git describe --tags will return 1.0.0-<commit_hash> for some commit following the tag 1.0.0. According to the semver spec, this would be considered a pre-release and hence older than 1.0.0, so we would need a translation scheme to cover use cases like that. Not a biggie though, it's probably better to follow an existing standard than to invent yet another one.

I would also suggest stripping prefixes like "v", so that v1.0.0 == 1.0.0

What do you think?

@nox already has a pretty nice semver 2.0 parser, so it would be quite easy to hook it up with rebar:
https://github.com/nox/mouture/

Contributor

nox commented Mar 6, 2014

@nox already has a pretty nice semver 2.0 parser, so it would be quite easy to hook it up with rebar:
https://github.com/nox/mouture/

Please note that I will never, ever, compromise on what is accepted by Mouture. If it isn’t a semantic version as per semver 2.0.0, it won’t get parsed by Mouture, ever.

So don’t plan to rely on it to parse weird and dubious version numbers.

That being said, I am not against improving stuff in it, as shown by the first issue I filed on it.

yfyf commented Mar 6, 2014

@nox sure, but hopefully that's not needed, if something extra needs to be done, it most likely can be implemented as a pre-parsing stage in rebar (e.g. the stripping which I mentioned).

Contributor

nox commented Mar 6, 2014

Just being honest about my project, that's all :)

yfyf commented Mar 19, 2014

After some thinking, I think enforcing pure semver might not make sense, many projects use ad-hoc versioning schemes and rebar should probably be liberal enough to allow them.

The RPM versioning scheme is quite simple and flexible (and also easy to implement). However it's incompatible with semver 2.0, since RPM doesn't treat 1.0-alpha as a pre-release for 1.0 (and a few other reasons).

Nevertheless, I would say go for RPM style versioning by default. rebar could provide tags / parsers for other version schemes in the style of:

{deps, [
     {rpm_versioned_dep, "1.2.3", ...}
     {non_rpm_versioned_dep, {semver, "0.1.1-alpha+build2"}, ..}
     {ugly_dep, {custom_vsn, "dog"}, ...}
]},

which could be implemented as rebar plugins and executed as pre_get-deps hooks, internally mapping e.g. 0.1.1-alpha+build2 to an RPM style version using a predefined parser respecting semver ordering. The parsed version should only be used for comparing.

This way it will work as expected for 99% of the users and will still be flexible enough to be used in the remaining more complex cases, without having to re-tag your projects.

@tuncer what are your thoughts on this?

Contributor

tuncer commented Mar 26, 2014

@yfyf I'm not sure rebar should delegate version checks to external plugins.

  • What exactly is RPM style versioning?
  • Did you intentionally leave out the rest of the dep spec(s)?
  • What part of your example refers to the external vsn check plugin?
  • How precisely is the comparison of version strings like "0.1.1-alpha+build2" defined in the semver spec? There are different version string styles (e.g. "0.1.0.99.2" vs "0.1.1-alpha+build2") in use, and maybe rebar needs to support most of them out of the box.

yfyf commented Mar 26, 2014

@tuncer Thanks for the reply, and sorry, this got rather long, but hopefully explains everything in detail:

@yfyf I'm not sure rebar should delegate version checking to external plugins.

I didn't say that, I meant that projects which have super-custom version schemes, could use a separate plugin for translating into rebar's chosen version scheme. This is also an optional consideration, not key to the whole discussion.

What exactly is RPM style versioning?

The version scheme used for RPM packages. It's described decently here and here. In short, it tokenises the string into numeric and alphabetic blocks and then compares them pairwise + lexicographically.

This is very flexible and has the intuitive semantics, since e.g. 1.0.0-foo01 will be tokenised as [1, 0, 0, "foo", 1].

I think it's better to re-use an existing and well-adopted version scheme than to invent yet another one.

Did you intentionally leave out the rest of the dep spec(s)?

Yes, only the version part is relevant for this discussion.

What part of your example refers to the external vsn check plugin?

The version tag wrappers {semver, _} and {custom_vsn , _} should be processed by the external plugin to produce unwrapped values accepted by rebar.
Again, as I mentioned, this is optional / extra functionality.

How precisely is the comparison of version strings like "0.1.1-alpha+build2" defined in the semver spec? There are different version string styles (e.g. "0.1.0.99.2" vs "0.1.1-alpha+build2") in use, and maybe rebar needs to support most of them out of the box.

0.1.0.99.2 is not a valid semver version, hence why I'm suggesting the more flexible RPM version scheme. semver strips the +... part completely (so no comparison based on it is done) and considers $VSN-alpha < $VSN.

RPM would consider 0.1.0.99.2 < 0.1.1 < 0.1.1-alpha+build2. This higlights the (IMHO) single problem with RPM versioning: pre-releases will be treated as newer than actual releases. Possible treaments are described in one of the previous links. In short, you can just say that the final release will always have version 0.1.1-1 and then 0.1.1-1 > 0.1.1-<alphabetic>. The version parser could even automatically append the -1 in case it is not present, I see no harm in this.

Due to the same reason, RPM ordering is incompatible with semver, but I suggest to resolve these with the external / builtin vsn parsers. It's easy to translate from semver to a compatible representation in RPM versioning.

Hope this clears things up.

Contributor

tuncer commented Mar 26, 2014

So, semver is unable to compare 0.1.1-alpha+build2 and 0.1.1-alpha+build3 as one would intuitively expect, right?

How does the rpm vsn scheme compare 0.1.1-alpha+build2, 0.1.1-alpha+build3, and 0.1.1-beta?

The beauty of 0.1.0.99.2 < 0.1.1 is that you can use 0.1.0.99.n to version as many pre-releases of 0.1.1 as required, and you can document x.y.90.n as alpha and x.y.99.n as beta.

yfyf commented Mar 26, 2014

So, semver is unable to compare 0.1.1-alpha+build2 and 0.1.1-alpha+build3 as one would intuitively expect, right?

Well, semver is just a spec and it says:

Build metadata SHOULD be ignored when determining version precedence. Thus two versions that differ only in the build metadata, have the same precedence.

So, although a particular project might choose to interpret its version metadata, a general tool should not.

How does the rpm vsn scheme compare 0.1.1-alpha+build2, 0.1.1-alpha+build3, and 0.1.1-beta?

In the correct way: 0.1.1-alpha+build2 < 0.1.1-alpha+build3 < 0.1.1-beta.
Because it parses these as

[0, 1, 1, "alpha", "build", 2] < [0, 1, 1, "alpha", "build", 3] < [0, 1, 1, "beta"]

since "alpha" < "beta" lexicographically.

The beauty of 0.1.0.99.2 < 0.1.1 is that you can use 0.1.0.99.n to version as many pre-releases of 0.1.1 as required, and you can document x.y.90.n as alpha and x.y.99.n as beta.

Yup. It's very easy to use RPM versioning to fit any kind of reasonable needs, IMHO.

Contributor

tuncer commented Mar 26, 2014

But the semver spec does not define any and all trailing "+foo" suffix as build meta data, does it?

rpm versioning looks sane, and I don't know why semver is defined to ignore build metadata. I suppose there's a good reason, but I don't see it.

As long as rebar only processes source deps, does it ever have to handle version strings extended with build metadata? I don't think it has to.

In an ideal world all Erlang projects would use the same versioning scheme. I mean, would it work to apply the rpm versioning rules to semver and rpm vsn strings?

yfyf commented Mar 26, 2014

But the semver spec does not define any and all trailing "+foo" suffix as build meta data, does it?

It does.

rpm versioning looks sane, and I don't know why semver is defined to ignore build metadata. I suppose there's a good reason, but I don't see it.

To be honest, the only good thing about semver is the minor / major / patch convention. The rest is largely under-thought, IMHO. It's not really extensible and the fact that lexicographic ordering is broken is very annoying.

As long as rebar only processes source deps, does it ever have to handle version strings extended with build metadata? I don't think it has to.

It would just be nice to have a consistent and long-term choice for this. So if someone has a funky versioning scheme, where "+" denotes e.g. patches, rebar should handle a version constraint like >= 1.0.0+patch1 without problems.

In an ideal world all Erlang projects would use the same versioning scheme. I mean, would it work to apply the rpm versioning rules to semver and rpm vsn strings?

Well, it will be identical for at least 95% of the cases where only MAJOR.MINOR.PATCH is used.

To resolve the pre-build / metadata incompability, we can take the version-remapping approach I described earlier i.e. if a user wants to enforce strict semver, use {semver, CONSTRAINT}.

E.g. if the version constraint for CoolApp5000 is >= 1.0.0, we want 1.0.0 and 1.0.0+bar to satisfy this constraint under both semver and RPM, but 1.0.0-foo to satisfy it under RPM spec, but fail under semver.

To make this possible, the user can specify that CoolApp5000 is versioned according to strict semver by writing the constraint as {semver, ">= 1.0.0"}, like in my previous example.
Rebar (or a plugin) would then, before doing the constraint solving, remap the versions as e.g.

  • 1.0.0 to 1.0.0
  • 1.0.0+bar to 1.0.0 (strip metadata)
  • 1.0.0-foo to 0.9999.9999+1.0.0-foo (ensure pre-build ordering of semver)

making the RPM order of the mapped versions match the semver order of the original versions.

This is sort of a hack, but should work fairly well. Perhaps we can ignore this initially and add this later if someone really demands it. I guess my whole point is that if we go with RPM versioning, rebar could still host other versioning schemes "on top of it", if needed.

Contributor

tuncer commented Mar 26, 2014

Sounds reasonable to me.

ferd added the enhancement label Jun 16, 2014

Ugh, multiple version resolution strategies sounds like a very annoying path to walk. We should make a decision on just using a single method and stick to that. Things that don't work with that scheme become incorrect ways to tag your versions with rebar. There's nothing wrong with taking a stand on specific issues.

More specifically, MAJOR.MINOR.PATCH should be the only thing rebar supports. Other metadata should be an error.

yfyf commented Jun 17, 2014

Ugh, multiple version resolution strategies sounds like a very annoying path to walk. We should make a decision on just using a single method and stick to that.

Agree, that's why I'm suggesting RPM style versioning. I'm only sketching the (hacky) ways to host other versioning schemes in case it is desperately needed.

More specifically, MAJOR.MINOR.PATCH should be the only thing rebar supports. Other metadata should be an error.

How would that benefit anyone? rebar is not a package manager, it is pointless to enforce such a thing. People use all kinds of different setups, with developement / testing branches specified and etc. This would break all of those projects and potentially force a change in upstream tagging schemes -- not an option.

I'm advocating for making it a package manager, clearly. :)

Contributor

nox commented Jun 17, 2014

Let's implement everything in a single tool, what could go wrong! Rebar is a build tool.

@nox in other tickets I've advocated for removing other unnecessary features. There's context to go along with what I said here. :)

Contributor

nox commented Jun 18, 2014

@AeroNotix Doesn't change that package management will never be rebar's forte, nor that it should be.

Do I understand you correctly, that this feature will never be implemented in rebar and version constraints checking is not in your plans?

Contributor

ferd commented Feb 6, 2015

This could be attempted, but frankly I won't be the one to put time into it. An alternative approach (using distance from the root rather than versions) has been chosen for rebar3, which is where @tsloughter and others have been spending time trying to fix these things.

Member

tsloughter commented Feb 6, 2015

And there is no way without a package index would a sat solver work. Certainly not something that could be implemented on top of rebar2 without also adding support for some package repository.

So, safe to say rebar2 will never have a depsolver :)

If anyone is interested in vsn checking, i created small plugin for rebar (https://github.com/define-null/rebar_version_checker), to solve this task. It's can be still not mature enough, so any feedback is welcomed.

Ideas borrowed both from this thread and basho/rebar#262

Contributor

tuncer commented Feb 12, 2015

@define-null, thanks for sharing. While this ticket is about a solver for constraints like >= 1.2.* && < 1.7.*, a simple solver for only >= 1.2.* seems like an improvement over the vsn regexes we have now. So, if this is what users want, and you submit a pull request, I'm in favor of integrating it as an alternative to regexes.

@tuncer Well, >= 1.2.* && < 1.7.* constrain can be written in terms of the plugin as [">= 1.2.0", "< 1.7.0"].
Don't know whether * should be allowed, or for example an option to exclude some intervals of versions.. i really don't think full regexp support if good for solving this tasks.

As for the pullrequest the plugin solves our compani's needs now, and separate section for version checking seems to be ok cause it does not violate old projects and it's easy to integrate.

I don't see better solution right now for constrain support without breaking compatability with old versions.

Contributor

tuncer commented Feb 12, 2015

@define-null, sounds good, and what about ||?

1.2.* should mean the same as 1.2, but I wouldn't mind not supporting *.

Also, of course the question remains what to compare against (index, vcs tags, ...). How do you use it at your company?

Contributor

tuncer commented Feb 12, 2015

Just to be clear, like I suggested in @psyeugenic's gears thread on erlang-questions, a proper solution requires integration in erts, stdlib, and kernel, in order to fully support this in apps and releases. Still, that doesn't mean a simple enhancement in rebar won't be useful.

@tuncer yes, plugin can be extended to use || and also '(' ')', but I also faced with the fact that 'git' tag versioning in rebar is not compatible with semver at all, and extra work should be done to treat 'git' tag in the other way. ( for example 0.6.0-5-g0c95039 < 0.6.0 in semver but in case of 'git' tag in rebar it means that 5 commits were created after 0.6.0 tag, so 0.6.0-5-g0c95039 should be always greater. I think 0.6.0-5-g0c95039 should look like 0.6.0+build.5.g0c95039 to be semver compatible )

Anyway if you have any suggestions please post an issue or send pullrequest to the github repo mentioned above.

Contributor

tuncer commented Feb 14, 2015

That's not a tag, so it doesn't have to be supported. Tags are created explicitly.

Contributor

nox commented Feb 14, 2015

I think 0.6.0-5-g0c95039 should look like 0.6.0+build.5.g0c95039 to be semver compatible

And note that with this change, this version would still not be greater than 0.6.0 because build metadata isn't taken into consideration when comparing versions in semver.

@nox yeah, i know, but how to name the dev version after 0.6.0 which does not have breaking changes in semver without extra version? It's ok for me that 0.6.0+build.5.g0c95039 at least not smaller then 0.6.0, better then nothing..

@tuncer sorry for my poor english, by the "git tag" i meant {vsn, git} approach in app.src.

That's not a tag, so it doesn't have to be supported. Tags are created explicitly.

Personally I don't want ever to specify version explicitly in app.src, version should be generated based on the tag I added with git or other vcs,

Of course anyone can use {vsn, cmd} instead to define his own versioning schema, but it would be great to have one, available in rebar, which support simple version constraints as discussed above. May be semver is not good enough for this.

Contributor

tuncer commented Feb 15, 2015

@define-null wrote:

@tuncer sorry for my poor english, by the "git tag" i meant {vsn, git} approach in app.src.

No need to excuse, your English is fine, and you just seem to have left out that bit :).

Personally I don't want ever to specify version explicitly in app.src, version should be generated based on the tag I added with git or other vcs,

You don't have to:

  1. When the rev is a tag, this will be reflected correctly in your generated .app. This is the only scenario where listing tags and trying to solve the vsn constraint against that (because there's no index) will work.
  2. If you do not want to depend on a specific tag, you will most likely ask for a branch, and therefore you will be best served with the regex vsn match.
  3. If you do want to depend on a specific rev that isn't tagged yet, you will ask for that commit (rev) and again use the regex vsn match.

Of course anyone can use {vsn, cmd} instead to define his own versioning schema, but it would be great to have one, available in rebar, which support simple version constraints as discussed above. May be semver is not good enough for this.

Yeah, as you can read above in the rpm versioning discussion, semver appears to be underspecified and insufficient.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment