Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
10540151:
First pass at version constraint solver. (Closed)
|
Created:
8 years, 6 months ago by Bob Nystrom Modified:
8 years, 6 months ago Reviewers:
nweiz CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionFirst pass at version constraint solver.
It does:
- Walk dependency graphs.
- Unify shared constraints.
- Go through Source to get dependency and version information.
- Handle the fact that everything is async.
- Find best versions that match all constraints.
- Error out if it can't find a match or gets stuck in a loop.
- Have an OK amount of tests.
It does not:
- Handle dependencies from different sources.
- Integrate with the rest of pub.
- Implement an actual "pub update" command.
- Do very much to minimize server traffic.
(Though it does cache pubspecs it has requested.)
Committed: https://code.google.com/p/dart/source/detail?r=8985
Patch Set 1 #
Total comments: 81
Patch Set 2 : Respond to review. #Patch Set 3 : Use Futures.wait() instead of nested chain() calls. #Patch Set 4 : Request all versions from the source, and not just the best. #
Messages
Total messages: 8 (0 generated)
Argh, forgot to actually send it out for review yesterday...
https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/package.dart File utils/pub/package.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/package.dart... utils/pub/package.dart:65: // it worth keeping this around? Seems fine to me. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:39: Future<Version> findVersion(String name, Shouldn't "name" be "description" instead? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { This puts a lot of burden onto the sources for understanding every type of VersionConstraint that exists. This seems dangerous, since additional VersionConstraints could potentially break third-party sources. Maybe a better API would be a listVersions method that just returns a list of all versions available for a given package? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart File utils/pub/version.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:324: // If the range is just a single version. There are other cases where it could just be a single version. For example: intersectMin = 0.0.1 intersectMax = 0.0.2 intersectIncludeMin = true intersectIncludeMax = false intersectMin = 0.0.1 intersectMax = 0.0.3 intersectIncludeMin = false intersectIncludeMax = false https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:362: if (min == null && max == null) buffer.add('any'); We should only print this if we parse "any" as allowing any version. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:376: final _emptyVersion = const _EmptyVersion(); Why is this necessary? Can't const automatically canonicalize values? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:395: factory VersionConstraint.intersect(Collection<VersionConstraint> constraints) { Line length. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:405: // one is whitespace sensitive (you can't do "< 1.2.3") and "<" is I'm coming around on quoting constraints in general, but I definitely don't think we should disallow "< 1.2.3". It wouldn't be too hard to have it be space-separated and still allow that. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:408: if (text.startsWith('<=')) { I think you could save some repetition here by parsing this with a regular expression. E.g.: var match = const RegExp(r"^([<>]=?)?(.*)$").firstMatch(text); var operator = match[1]; var version = match[2]; https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... File utils/pub/version_solver.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:47: Future<Map<String, Version>> resolveVersions( This could use some docs. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:69: enqueue(new ChangeConstraint('(entrypoint)', root.name, root.version)); What happens if some other package depends on the root package? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:81: // when we have a better picture of real-world package topologies. Are we planning to try to manually catch infinite loops, with this as a backup? Or will this be our sole method of loop-detection? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:91: // when it's done. Otherwise, just loop synchronously. Wouldn't it be possible to process other work items while the asynchronous ones are pending? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:132: * The constraint solver works by iteratively processing a queue work items. "a queue of work items" https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:135: * from servers) as well as avoiding deeply nest recursion. "avoid deeply nested recursion" https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:171: return getDependencies(solver, version).transform((newDependencies) { You could increase parallelism and reduce nesting here by using Futures.wait([getDependencies(solver, oldVersion), getDependencies(solver, version)]). https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:177: constraint = newDependencies[dependency.name].version; constraint = newDependencies.remove(dependency.name).version; https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:202: Future<Map<String, PackageRef>> getDependencies(VersionSolver solver, This name is confusing, since the method doesn't have anything to do with Dependency objects. Maybe getDependencyRefs? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:224: * [dependent]. This is inaccurate. "[package]" and "[dependent]" don't refer to anything, and "[from]" and "[to]" are package names rather than constraints. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:235: final String to; I'm finding "from" and "to" confusing when reading the code in #process. Maybe "depender" and "dependee"? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:240: final VersionConstraint version; I'd call this "constraint", since it's a VersionConstraint and not always a Version. I might also change the "version" field in PackageRef to "constraint" as well. Trying to figure out what was a Version and what was a VersionConstraint tripped me up while reading this code. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:250: // If we the package is over-constrained, i.e. the packages depending "If the package is" https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:283: // system cache. Rather than making a separate cache of just pubspecs, I think we should make use of the pubspecs for the packages installed in the cache if such packages exist and just fetch from the source otherwise. Keeping our own, separate pubspec cache may violate some assumptions the sources make about when the spec might update. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:285: * Maintains a synchronous cache of previously-loaded pubspecs. Used to What do you mean by "synchronous"? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:363: void setConstraint(String package, VersionConstraint constraint) { "addConstraint" would be a clearer name. It's true that that name is a little misleading when called twice with the same package, but the current name is misleading when this method is called only once, since it implies that there's a single constraint for the dependency being set. Since in practice this is called only once at a time, I think "add" is clearer. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:380: final VersionConstraint version; s/version/constraint/. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_solver_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:138: // infinite loop on unstable graphs. Remove TODO https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:139: testResolve('unstable dependency graph', { Shouldn't this stabilize at a=1.0.0? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:203: // exception. It seems like sufficient information for debugging should be printed by default. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:214: class MockSource extends Source { Maybe it's time to make MockSource its own library in utils/tests/pub? It's defined three separate times now. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:248: Package mockPackage(String name, String version, Map dependencies) { It seems like you could simplify this method and avoid taking a SourceRegistry in the constructor if you just use the Package._ constructor. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_test.dart:198: expect(!range.allows(new Version.parse('1.2.2'))); It seems weird that you use expect(..., isFalse) some places and expect(!...) others.
Thanks! https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/package.dart File utils/pub/package.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/package.dart... utils/pub/package.dart:65: // it worth keeping this around? On 2012/06/18 18:29:19, nweiz wrote: > Seems fine to me. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:39: Future<Version> findVersion(String name, On 2012/06/18 18:29:19, nweiz wrote: > Shouldn't "name" be "description" instead? Yeah. Right now, this giant patch punts on how different sources should be handled and just does the dumb default of treating packages as name/version pairs. It should do this better, and there are some TODOs to that effect. If it's OK with you, I'd like to handle that in a separate patch. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { On 2012/06/18 18:29:19, nweiz wrote: > This puts a lot of burden onto the sources for understanding every type of > VersionConstraint that exists. This seems dangerous, since additional > VersionConstraints could potentially break third-party sources. > > Maybe a better API would be a listVersions method that just returns a list of > all versions available for a given package? Maybe I'm being premature, but I worry that that could be slow/redundant if a package has a ton of released versions, many of which you already know of locally. Right now, a VersionConstraint is always a contiguous range (which may be inclusive, exclusive, or open on either end) even though the API doesn't make that clear. If we want, we can make that implicit fact explicitly declared and then a Source can rely on always being asked for the set of versions within a range. Or, if we don't want to worry about that, keep in mind that the simplest implementation of this for a source is just: 1. Get all versions. 2. Walk the list and see which ones the constraint allows. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart File utils/pub/version.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:324: // If the range is just a single version. On 2012/06/18 18:29:19, nweiz wrote: > There are other cases where it could just be a single version. For example: > > intersectMin = 0.0.1 > intersectMax = 0.0.2 > intersectIncludeMin = true > intersectIncludeMax = false That can still have other versions, like: 0.0.1+hotfix1 > intersectMin = 0.0.1 > intersectMax = 0.0.3 > intersectIncludeMin = false > intersectIncludeMax = false Ditto: 0.0.2-alpha, 0.0.2-beta, 0.0.2+patch1, etc. Given prerelease and build suffixes, version numbers are essentially points on the real number line, I believe. You can think of it as a three digit floating point number where the digits to the left of the decimal point are base infinity, and the digits (of which there are can be arbitrarily many) to the right are base 256 ASCII. :) https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:362: if (min == null && max == null) buffer.add('any'); On 2012/06/18 18:29:19, nweiz wrote: > We should only print this if we parse "any" as allowing any version. Done. Added parse support for it. That should make pubspecs a bit nicer too: dependencies: foo: any https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:376: final _emptyVersion = const _EmptyVersion(); On 2012/06/18 18:29:19, nweiz wrote: > Why is this necessary? Can't const automatically canonicalize values? Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:395: factory VersionConstraint.intersect(Collection<VersionConstraint> constraints) { On 2012/06/18 18:29:19, nweiz wrote: > Line length. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:405: // one is whitespace sensitive (you can't do "< 1.2.3") and "<" is On 2012/06/18 18:29:19, nweiz wrote: > I'm coming around on quoting constraints in general, but I definitely don't > think we should disallow "< 1.2.3". It wouldn't be too hard to have it be > space-separated and still allow that. Agreed, this is too finicky, but is it OK to be simple for this patch? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:408: if (text.startsWith('<=')) { On 2012/06/18 18:29:19, nweiz wrote: > I think you could save some repetition here by parsing this with a regular > expression. E.g.: > > var match = const RegExp(r"^([<>]=?)?(.*)$").firstMatch(text); > var operator = match[1]; > var version = match[2]; Done. Good call. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... File utils/pub/version_solver.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:69: enqueue(new ChangeConstraint('(entrypoint)', root.name, root.version)); On 2012/06/18 18:29:19, nweiz wrote: > What happens if some other package depends on the root package? There TODOs to add tests for that. Added tests. They pass! If the constraint of the other dependency still allows the root's concrete version, then it should pass, otherwise it's an overconstraint error. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:81: // when we have a better picture of real-world package topologies. On 2012/06/18 18:29:19, nweiz wrote: > Are we planning to try to manually catch infinite loops, with this as a backup? > Or will this be our sole method of loop-detection? Right now, it's the sole method. Catching loops will, I think, require keeping track of previous states that the resolver has been in and that adds some complexity. If you think it's worth doing, I'm open to the idea. For the first pass, I just went with something simple. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:91: // when it's done. Otherwise, just loop synchronously. On 2012/06/18 18:29:19, nweiz wrote: > Wouldn't it be possible to process other work items while the asynchronous ones > are pending? In theory yes, but that adds a lot of complexity I wanted to try to avoid. You can get in nasty situations like: 1. We get a constraint on foo >=1.0.0, so we ask the server for what versions of foo it has. 2. Meanwhile, some other server response completes whose result is to remove the dependency on foo (or just change its constraint). 3. The response from 1 comes in and we pick a version from a constraint that no longer applies. It is possible to make this work, but I'm not sure it's worth the extra complexity. Do you think it is? https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:132: * The constraint solver works by iteratively processing a queue work items. On 2012/06/18 18:29:19, nweiz wrote: > "a queue of work items" Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:135: * from servers) as well as avoiding deeply nest recursion. On 2012/06/18 18:29:19, nweiz wrote: > "avoid deeply nested recursion" Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:171: return getDependencies(solver, version).transform((newDependencies) { On 2012/06/18 18:29:19, nweiz wrote: > You could increase parallelism and reduce nesting here by using > Futures.wait([getDependencies(solver, oldVersion), getDependencies(solver, > version)]). I think I had that at one point but it felt like overkill for a list of two items. If you prefer that, I could change it. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:177: constraint = newDependencies[dependency.name].version; On 2012/06/18 18:29:19, nweiz wrote: > constraint = newDependencies.remove(dependency.name).version; Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:202: Future<Map<String, PackageRef>> getDependencies(VersionSolver solver, On 2012/06/18 18:29:19, nweiz wrote: > This name is confusing, since the method doesn't have anything to do with > Dependency objects. Maybe getDependencyRefs? Done. What I wouldn't give for a shorter synonym for "dependency". https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:224: * [dependent]. On 2012/06/18 18:29:19, nweiz wrote: > This is inaccurate. "[package]" and "[dependent]" don't refer to anything, and > "[from]" and "[to]" are package names rather than constraints. Stale comment is stale. This went through a few iterations. Fixed. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:235: final String to; On 2012/06/18 18:29:19, nweiz wrote: > I'm finding "from" and "to" confusing when reading the code in #process. Maybe > "depender" and "dependee"? Changed to "depender" (which kind of sounds like suspenders for old people diapers to me) and "dependent". https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:240: final VersionConstraint version; On 2012/06/18 18:29:19, nweiz wrote: > I'd call this "constraint", since it's a VersionConstraint and not always a > Version. I might also change the "version" field in PackageRef to "constraint" > as well. Trying to figure out what was a Version and what was a > VersionConstraint tripped me up while reading this code. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:250: // If we the package is over-constrained, i.e. the packages depending On 2012/06/18 18:29:19, nweiz wrote: > "If the package is" Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:283: // system cache. On 2012/06/18 18:29:19, nweiz wrote: > Rather than making a separate cache of just pubspecs, I think we should make use > of the pubspecs for the packages installed in the cache if such packages exist Agreed that we should do this. > and just fetch from the source otherwise. Keeping our own, separate pubspec > cache may violate some assumptions the sources make about when the spec might > update. Hmm good point. Right now, this is just an in-memory cache. That's important because the solver may need a given pubspec multiple times during a single solve and we don't want to hit the server each time for that. If we ever look into making that more persistent, we'll do some design on it. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:285: * Maintains a synchronous cache of previously-loaded pubspecs. Used to On 2012/06/18 18:29:19, nweiz wrote: > What do you mean by "synchronous"? Stale comment. This used to have a synchronous "get" method for pubspecs that were known to be in the cache. ChangeVersion would try to use that to reduce the nested async calls but it was more trouble than it was worth. Fixed the comment. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:363: void setConstraint(String package, VersionConstraint constraint) { On 2012/06/18 18:29:19, nweiz wrote: > "addConstraint" would be a clearer name. It's true that that name is a little > misleading when called twice with the same package, but the current name is > misleading when this method is called only once, since it implies that there's a > single constraint for the dependency being set. Since in practice this is called > only once at a time, I think "add" is clearer. Changed to "placeConstraint". :) https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:380: final VersionConstraint version; On 2012/06/18 18:29:19, nweiz wrote: > s/version/constraint/. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_solver_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:138: // infinite loop on unstable graphs. On 2012/06/18 18:29:19, nweiz wrote: > Remove TODO Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:139: testResolve('unstable dependency graph', { On 2012/06/18 18:29:19, nweiz wrote: > Shouldn't this stabilize at a=1.0.0? That would be a valid solution, but the solver is greedy. It won't pick a non-best version for a constraint just to avoid other dependencies that would lead to a non-solution. In other words, if it gives you a solution, the versions it picks should be the best versions for the constraints in the dependency graph of that solution. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:203: // exception. On 2012/06/18 18:29:19, nweiz wrote: > It seems like sufficient information for debugging should be printed by default. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:214: class MockSource extends Source { On 2012/06/18 18:29:19, nweiz wrote: > Maybe it's time to make MockSource its own library in utils/tests/pub? It's > defined three separate times now. Maybe. I think each one does different things, and I kind of like mocks that are minimal and tailored to each use. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:248: Package mockPackage(String name, String version, Map dependencies) { On 2012/06/18 18:29:19, nweiz wrote: > It seems like you could simplify this method and avoid taking a SourceRegistry > in the constructor if you just use the Package._ constructor. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_test.dart:198: expect(!range.allows(new Version.parse('1.2.2'))); On 2012/06/18 18:29:19, nweiz wrote: > It seems weird that you use expect(..., isFalse) some places and expect(!...) > others. Done.
https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:39: Future<Version> findVersion(String name, On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > Shouldn't "name" be "description" instead? > > Yeah. Right now, this giant patch punts on how different sources should be > handled and just does the dumb default of treating packages as name/version > pairs. > > It should do this better, and there are some TODOs to that effect. If it's OK > with you, I'd like to handle that in a separate patch. Sure, it's reasonable to put this off. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > This puts a lot of burden onto the sources for understanding every type of > > VersionConstraint that exists. This seems dangerous, since additional > > VersionConstraints could potentially break third-party sources. > > > > Maybe a better API would be a listVersions method that just returns a list of > > all versions available for a given package? > > Maybe I'm being premature, but I worry that that could be slow/redundant if a > package has a ton of released versions, many of which you already know of > locally. > > Right now, a VersionConstraint is always a contiguous range (which may be > inclusive, exclusive, or open on either end) even though the API doesn't make > that clear. If we want, we can make that implicit fact explicitly declared and > then a Source can rely on always being asked for the set of versions within a > range. > > Or, if we don't want to worry about that, keep in mind that the simplest > implementation of this for a source is just: > > 1. Get all versions. > 2. Walk the list and see which ones the constraint allows. If we do pass VersionConstraints to sources, we should definitely be explicit about what the sources can assume about them. I still don't think that's a good idea, though. Right now, in order for the source to avoid massive numbers of HTTP fetches, it also needs to have caching logic for the list of all sources, and it has to have its own logic for choosing the "best" version (which means it needs to decide for itself how to handle e.g. prerelease versions). It's not as simple as the two-step process you outline. I think for now, worrying about this optimization isn't worth it. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart File utils/pub/version.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:324: // If the range is just a single version. On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > There are other cases where it could just be a single version. For example: > > > > intersectMin = 0.0.1 > > intersectMax = 0.0.2 > > intersectIncludeMin = true > > intersectIncludeMax = false > > That can still have other versions, like: 0.0.1+hotfix1 > > > intersectMin = 0.0.1 > > intersectMax = 0.0.3 > > intersectIncludeMin = false > > intersectIncludeMax = false > > Ditto: 0.0.2-alpha, 0.0.2-beta, 0.0.2+patch1, etc. Given prerelease and build > suffixes, version numbers are essentially points on the real number line, I > believe. > > You can think of it as a three digit floating point number where the digits to > the left of the decimal point are base infinity, and the digits (of which there > are can be arbitrarily many) to the right are base 256 ASCII. :) Good point. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version.dart... utils/pub/version.dart:405: // one is whitespace sensitive (you can't do "< 1.2.3") and "<" is On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > I'm coming around on quoting constraints in general, but I definitely don't > > think we should disallow "< 1.2.3". It wouldn't be too hard to have it be > > space-separated and still allow that. > > Agreed, this is too finicky, but is it OK to be simple for this patch? Yes, definitely. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... File utils/pub/version_solver.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:81: // when we have a better picture of real-world package topologies. On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > Are we planning to try to manually catch infinite loops, with this as a > backup? > > Or will this be our sole method of loop-detection? > > Right now, it's the sole method. Catching loops will, I think, require keeping > track of previous states that the resolver has been in and that adds some > complexity. If you think it's worth doing, I'm open to the idea. For the first > pass, I just went with something simple. It seems like a nice thing to do once we run out of actual features to add. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:91: // when it's done. Otherwise, just loop synchronously. On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > Wouldn't it be possible to process other work items while the asynchronous > ones > > are pending? > > In theory yes, but that adds a lot of complexity I wanted to try to avoid. You > can get in nasty situations like: > > 1. We get a constraint on foo >=1.0.0, so we ask the server for what versions of > foo it has. > 2. Meanwhile, some other server response completes whose result is to remove the > dependency on foo (or just change its constraint). > 3. The response from 1 comes in and we pick a version from a constraint that no > longer applies. > > It is possible to make this work, but I'm not sure it's worth the extra > complexity. Do you think it is? Probably not... that could also (potentially) make the version resolution process non-deterministic, which we don't want. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:171: return getDependencies(solver, version).transform((newDependencies) { On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > You could increase parallelism and reduce nesting here by using > > Futures.wait([getDependencies(solver, oldVersion), getDependencies(solver, > > version)]). > > I think I had that at one point but it felt like overkill for a list of two > items. If you prefer that, I could change it. I think it would be cleaner. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:202: Future<Map<String, PackageRef>> getDependencies(VersionSolver solver, On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > This name is confusing, since the method doesn't have anything to do with > > Dependency objects. Maybe getDependencyRefs? > > Done. What I wouldn't give for a shorter synonym for "dependency". You could always use "dep". https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_solver_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:139: testResolve('unstable dependency graph', { On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > Shouldn't this stabilize at a=1.0.0? > > That would be a valid solution, but the solver is greedy. It won't pick a > non-best version for a constraint just to avoid other dependencies that would > lead to a non-solution. But shouldn't it resolve this like so: * Set a=2.0.0 * Add constraint to b: =1.0.0 * Set b=1.0.0 * Add constraint to a: =1.0.0 * Set a=1.0.0 > In other words, if it gives you a solution, the versions it picks should be the > best versions for the constraints in the dependency graph of that solution. But if chose a=1.0.0 and b=1.0.0, then that's the case since there is no better version of b and a=1.0.0 is the best that satisfies all the constraints. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:214: class MockSource extends Source { On 2012/06/20 01:40:04, Bob Nystrom wrote: > On 2012/06/18 18:29:19, nweiz wrote: > > Maybe it's time to make MockSource its own library in utils/tests/pub? It's > > defined three separate times now. > > Maybe. I think each one does different things, and I kind of like mocks that are > minimal and tailored to each use. I prefer libraries that are re-usable, personally.
Thanks! https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { On 2012/06/20 21:08:48, nweiz wrote: > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > On 2012/06/18 18:29:19, nweiz wrote: > > > This puts a lot of burden onto the sources for understanding every type of > > > VersionConstraint that exists. This seems dangerous, since additional > > > VersionConstraints could potentially break third-party sources. > > > > > > Maybe a better API would be a listVersions method that just returns a list > of > > > all versions available for a given package? > > > > Maybe I'm being premature, but I worry that that could be slow/redundant if a > > package has a ton of released versions, many of which you already know of > > locally. > > > > Right now, a VersionConstraint is always a contiguous range (which may be > > inclusive, exclusive, or open on either end) even though the API doesn't make > > that clear. If we want, we can make that implicit fact explicitly declared and > > then a Source can rely on always being asked for the set of versions within a > > range. > > > > Or, if we don't want to worry about that, keep in mind that the simplest > > implementation of this for a source is just: > > > > 1. Get all versions. > > 2. Walk the list and see which ones the constraint allows. > > If we do pass VersionConstraints to sources, we should definitely be explicit > about what the sources can assume about them. I still don't think that's a good > idea, though. > > Right now, in order for the source to avoid massive numbers of HTTP fetches, it > also needs to have caching logic for the list of all sources, and it has to have > its own logic for choosing the "best" version (which means it needs to decide > for itself how to handle e.g. prerelease versions). It's not as simple as the > two-step process you outline. My intent is that that caching would live outside of source. So pub itself would keep a cache of the known version numbers for a given package. When the solver requests all of the versions in a given range, pub can intersect that with the ranges that it already knows it has and pass that remaining constraint to the source. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... File utils/pub/version_solver.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:171: return getDependencies(solver, version).transform((newDependencies) { On 2012/06/20 21:08:48, nweiz wrote: > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > On 2012/06/18 18:29:19, nweiz wrote: > > > You could increase parallelism and reduce nesting here by using > > > Futures.wait([getDependencies(solver, oldVersion), getDependencies(solver, > > > version)]). > > > > I think I had that at one point but it felt like overkill for a list of two > > items. If you prefer that, I could change it. > > I think it would be cleaner. Done. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:202: Future<Map<String, PackageRef>> getDependencies(VersionSolver solver, On 2012/06/20 21:08:48, nweiz wrote: > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > On 2012/06/18 18:29:19, nweiz wrote: > > > This name is confusing, since the method doesn't have anything to do with > > > Dependency objects. Maybe getDependencyRefs? > > > > Done. What I wouldn't give for a shorter synonym for "dependency". > > You could always use "dep". For some reason, that bugs me. Maybe I just don't like abbreviations. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_solver_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:139: testResolve('unstable dependency graph', { On 2012/06/20 21:08:48, nweiz wrote: > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > On 2012/06/18 18:29:19, nweiz wrote: > > > Shouldn't this stabilize at a=1.0.0? > > > > That would be a valid solution, but the solver is greedy. It won't pick a > > non-best version for a constraint just to avoid other dependencies that would > > lead to a non-solution. > > But shouldn't it resolve this like so: > > * Set a=2.0.0 > * Add constraint to b: =1.0.0 > * Set b=1.0.0 > * Add constraint to a: =1.0.0 > * Set a=1.0.0 When it sets a=1.0.0, that removes the dependency that a=2.0.0 has on b=1.0.0. That removes b from the graph. That in turn removes b's constraint on a=1.0.0. Since a's constraint changed, we look for the new best version that meets that constraint and now it becomes a 2.0.0. > > > In other words, if it gives you a solution, the versions it picks should be > the > > best versions for the constraints in the dependency graph of that solution. > > But if chose a=1.0.0 and b=1.0.0, then that's the case since there is no better > version of b and a=1.0.0 is the best that satisfies all the constraints. a=1.0.0 is the best version that satisfied the set of all possible constraints that could exist in when considering all versions of those dependencies. But it's not the best version that matches the actual constraints present in the resulting graph. We can't settle on a=1.0.0 and b=1.0.0 because that doesn't make sense: we would be including b even though nothing actually depends on it and it isn't being used. If we settle on a=1.0.0 and no b that graph's constraint on a is just >=1.0.0, and 1.0.0 isn't the best version that meets that constraint: 2.0.0 is. It would be a valid graph, but it's confusing. The graph itself doesn't tell you why that version of a was selected. You would have to know that selecting a different version of a would have other implications that aren't solvable.
https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { On 2012/06/20 22:29:54, Bob Nystrom wrote: > On 2012/06/20 21:08:48, nweiz wrote: > > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > > On 2012/06/18 18:29:19, nweiz wrote: > > > > This puts a lot of burden onto the sources for understanding every type of > > > > VersionConstraint that exists. This seems dangerous, since additional > > > > VersionConstraints could potentially break third-party sources. > > > > > > > > Maybe a better API would be a listVersions method that just returns a list > > of > > > > all versions available for a given package? > > > > > > Maybe I'm being premature, but I worry that that could be slow/redundant if > a > > > package has a ton of released versions, many of which you already know of > > > locally. > > > > > > Right now, a VersionConstraint is always a contiguous range (which may be > > > inclusive, exclusive, or open on either end) even though the API doesn't > make > > > that clear. If we want, we can make that implicit fact explicitly declared > and > > > then a Source can rely on always being asked for the set of versions within > a > > > range. > > > > > > Or, if we don't want to worry about that, keep in mind that the simplest > > > implementation of this for a source is just: > > > > > > 1. Get all versions. > > > 2. Walk the list and see which ones the constraint allows. > > > > If we do pass VersionConstraints to sources, we should definitely be explicit > > about what the sources can assume about them. I still don't think that's a > good > > idea, though. > > > > Right now, in order for the source to avoid massive numbers of HTTP fetches, > it > > also needs to have caching logic for the list of all sources, and it has to > have > > its own logic for choosing the "best" version (which means it needs to decide > > for itself how to handle e.g. prerelease versions). It's not as simple as the > > two-step process you outline. > > My intent is that that caching would live outside of source. So pub itself would > keep a cache of the known version numbers for a given package. When the solver > requests all of the versions in a given range, pub can intersect that with the > ranges that it already knows it has and pass that remaining constraint to the > source. My point is that if the source receives findVersion("foo", >= 5.6.0 < 6.0.0), the algorithm you outlined would have it request all versions and find the most recent that matches the constraint. In order to make this efficient, it would need to cache the result of the "all versions" request. This isn't something that can be cached externally, since the external code has no knowledge of the full set of versions downloaded. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... File utils/pub/version_solver.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/version_solv... utils/pub/version_solver.dart:202: Future<Map<String, PackageRef>> getDependencies(VersionSolver solver, On 2012/06/20 22:29:54, Bob Nystrom wrote: > On 2012/06/20 21:08:48, nweiz wrote: > > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > > On 2012/06/18 18:29:19, nweiz wrote: > > > > This name is confusing, since the method doesn't have anything to do with > > > > Dependency objects. Maybe getDependencyRefs? > > > > > > Done. What I wouldn't give for a shorter synonym for "dependency". > > > > You could always use "dep". > > For some reason, that bugs me. Maybe I just don't like abbreviations. You used "ref" ;). I don't actually care either way; I like "dependency" just fine. https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... File utils/tests/pub/version_solver_test.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/tests/pub/versio... utils/tests/pub/version_solver_test.dart:139: testResolve('unstable dependency graph', { On 2012/06/20 22:29:54, Bob Nystrom wrote: > On 2012/06/20 21:08:48, nweiz wrote: > > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > > On 2012/06/18 18:29:19, nweiz wrote: > > > > Shouldn't this stabilize at a=1.0.0? > > > > > > That would be a valid solution, but the solver is greedy. It won't pick a > > > non-best version for a constraint just to avoid other dependencies that > would > > > lead to a non-solution. > > > > But shouldn't it resolve this like so: > > > > * Set a=2.0.0 > > * Add constraint to b: =1.0.0 > > * Set b=1.0.0 > > * Add constraint to a: =1.0.0 > > * Set a=1.0.0 > > When it sets a=1.0.0, that removes the dependency that a=2.0.0 has on b=1.0.0. > That removes b from the graph. That in turn removes b's constraint on a=1.0.0. > Since a's constraint changed, we look for the new best version that meets that > constraint and now it becomes a 2.0.0. > > > > > > In other words, if it gives you a solution, the versions it picks should be > > the > > > best versions for the constraints in the dependency graph of that solution. > > > > But if chose a=1.0.0 and b=1.0.0, then that's the case since there is no > better > > version of b and a=1.0.0 is the best that satisfies all the constraints. > > a=1.0.0 is the best version that satisfied the set of all possible constraints > that could exist in when considering all versions of those dependencies. But > it's not the best version that matches the actual constraints present in the > resulting graph. > > We can't settle on a=1.0.0 and b=1.0.0 because that doesn't make sense: we would > be including b even though nothing actually depends on it and it isn't being > used. > > If we settle on a=1.0.0 and no b that graph's constraint on a is just >=1.0.0, > and 1.0.0 isn't the best version that meets that constraint: 2.0.0 is. It would > be a valid graph, but it's confusing. The graph itself doesn't tell you why that > version of a was selected. You would have to know that selecting a different > version of a would have other implications that aren't solvable. Ah, I see now.
Requests all versions from the source now. PTAL, thanks! https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart File utils/pub/source.dart (right): https://chromiumcodereview.appspot.com/10540151/diff/1/utils/pub/source.dart#... utils/pub/source.dart:40: VersionConstraint constraint) { On 2012/06/20 23:47:45, nweiz wrote: > On 2012/06/20 22:29:54, Bob Nystrom wrote: > > On 2012/06/20 21:08:48, nweiz wrote: > > > On 2012/06/20 01:40:04, Bob Nystrom wrote: > > > > On 2012/06/18 18:29:19, nweiz wrote: > > > > > This puts a lot of burden onto the sources for understanding every type > of > > > > > VersionConstraint that exists. This seems dangerous, since additional > > > > > VersionConstraints could potentially break third-party sources. > > > > > > > > > > Maybe a better API would be a listVersions method that just returns a > list > > > of > > > > > all versions available for a given package? > > > > > > > > Maybe I'm being premature, but I worry that that could be slow/redundant > if > > a > > > > package has a ton of released versions, many of which you already know of > > > > locally. > > > > > > > > Right now, a VersionConstraint is always a contiguous range (which may be > > > > inclusive, exclusive, or open on either end) even though the API doesn't > > make > > > > that clear. If we want, we can make that implicit fact explicitly declared > > and > > > > then a Source can rely on always being asked for the set of versions > within > > a > > > > range. > > > > > > > > Or, if we don't want to worry about that, keep in mind that the simplest > > > > implementation of this for a source is just: > > > > > > > > 1. Get all versions. > > > > 2. Walk the list and see which ones the constraint allows. > > > > > > If we do pass VersionConstraints to sources, we should definitely be > explicit > > > about what the sources can assume about them. I still don't think that's a > > good > > > idea, though. > > > > > > Right now, in order for the source to avoid massive numbers of HTTP fetches, > > it > > > also needs to have caching logic for the list of all sources, and it has to > > have > > > its own logic for choosing the "best" version (which means it needs to > decide > > > for itself how to handle e.g. prerelease versions). It's not as simple as > the > > > two-step process you outline. > > > > My intent is that that caching would live outside of source. So pub itself > would > > keep a cache of the known version numbers for a given package. When the solver > > requests all of the versions in a given range, pub can intersect that with the > > ranges that it already knows it has and pass that remaining constraint to the > > source. > > My point is that if the source receives findVersion("foo", >= 5.6.0 < 6.0.0), > the algorithm you outlined would have it request all versions and find the most > recent that matches the constraint. In order to make this efficient, it would > need to cache the result of the "all versions" request. This isn't something > that can be cached externally, since the external code has no knowledge of the > full set of versions downloaded. Ah, sorry. I see what you're getting at. I forgot I'd changed findVersion() to just return one version. Fixed.
lgtm++ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
