DepS: Dependencies for Squeak
Last updated at 3:36 pm UTC on 15 August 2004
from Stephan Rudlof
Readme
This Readme is thought as a central point for important info.
Parts of this page outside this Readme are outdated, please only read it with care, if you already know the Deps links pages (if in doubt, they are the correct ones).
DepS links
History
Contents
Feedback
ToDo
- terminology changes
- version -> compatibility code?
- Package -> PackageVersion or Version?
Foreword
Triggered by a recent help request regarding dependencies from Goran, I've started thinking about the issues around and this is the result...
Some time ago I've made some stuff in direction of a Meak (make for Squeak), its importance has sunken after the release of VMMaker.
Now my idea is to make a very general dependency mechanism, which should be usable to build both a Debian apt-like package system, and a make tool as well. Some of the logic is similar.
This paper - I think it's OK to call it so (any better idea?) - should not be seen as a rock solid concept paper: it has undergone some iterations so far, and is in flux.
To the reader
I know, it takes some time to read through this paper (it also has taken
some time to write it ;-) ), but I hope you will find some interesting
thoughts in it.
Overview
If you are not interested in the technical, but in the social issues,
you nevertheless should read section
'Application to packages'
and especially its
'Application to packages'->'Versions'
subsection!
Otherwise please take a look into 'Contents' or just continue reading
from here...
Technical Terms
Caps
There are Capabilities (Caps) each describing the capability to do
something.
Caps mostly depend on other Caps, which are prerequisites of
them.
In the following Caps means Capabilities or a union of them.
Transformations
Transformations describe how it is possible to change a set of Caps:
they may - virtually at first - add or remove Caps or both. They
transform one set of Caps into another one. To do their work they
perform Actions.
Inputs are
I.1. requires: required Caps, and
I.2. conflicts: conflicting Caps,
outputs are
O.1. provides: newly generated Caps, and
O.2. deletes: deleted Caps.
Properties:
- provides are const sets, but
- deletes are configuration dependent.
Outputs are expressed as
- set of (named) Caps.
Inputs are expressed as
1. set of (named) Caps (as for outputs), or
2. as a Block
- taking a Caps set as an argument, returning
- true, if the requirement/conflict has been fullfilled,
- false, otherwise.
To Blocks as input
——————
It is computational expensive to use Blocks as input, since in principle
all existing Caps and those somehow generatable by whatever
Transformation combination (!) have to be checked.
An - important, I think - improvement for the case of expressing
conflicts may be to divide the Blocks into two classes (later there may
be more):
1. Blocks just checking conflicts with Caps generated additionally by
the packages generating the requirement Caps, under the precondition,
that the requirement Caps are given as set.
2. Other Blocks.
See section "To Lex's example" below for a motivation of Blocks as
arguments here and the suggested improvement.
Boolean logic
————-
Require sets model a logical AND of requirements. Logical ORs - and
therefrom Boolean logic - can be modeled via additional Transformations
with newly introduced Caps names. This is far more efficient as trying
to do this in one Transformation using the Blocks mechanism!
Outlook to packages
——————-
A package removal can be modeled by transforming the all over package
Caps as requires into deletes of this and all other package related Caps.
How to model dynamic provides?
——————————
The restriction 'provides are const sets' eases some things, but it is
not a limitation AFAICS.
Example: Installing a package WebBrowser may result into more Caps if
some other package SuperFonts is there.
This can easily be modeled by a _logical_ (no Action) package
Transformation describing the all over functionality of the packages
combo, with
- requires: Caps ('WebBrowser', 'SuperFonts'), and
- provides: something like ('WebBrowserWithSuperFonts').
Note
—-
It's questionable, if naming both set and Block inputs the same is a
good idea, but I want to stop for now...
Actions
Actions are commands leading to a change of the (set of) Caps in the
system. If triggered, they add and/or remove one or more Caps in reality.
Algorithms
Before there is no good model of the domain, it is not urgent to think
about algorithms. I don't fear not to find some...
A few things I'm currently expecting to be faced with:
Easy:
- depth first traversing of dependency graphs,
- back tracking with detection of cycles.
Not so easy:
- combinatorial explosion, if Blocks as inputs for Transformation
requires and conflicts come into play (but section 'Transformations->To
Blocks as input' contains a first idea for embanking it).
Application to packages
Packages
Note: DepS Packages (uppercase 'P') correspond to SMPackageReleases (the terminology may change to avoid confusion)!
A Package provides Caps: these are representing some things to be made
with or by the Package (interfaces, commands). There may be more than
one Caps per Package!
A Package needs Caps provided from other packages (requires).
A Package providing some Caps may conflict with another Package
(providing other and/or the same Caps).
To be able to express these conflicts at Caps level it is necessary that
all packages are mutually different in at least one Caps! But this is
easy to accomplish, if there is just one Caps named so, that it contains
the - unique - name of them.
A conflicting Package has to be removed (this can be difficult) before
installing a new one, leading into a reduction of its provided Caps
(there may be logical ones left, which are also provided by another
package).
There may also be Packages, which only remove Caps without adding new
ones (system shrink)!
Versions
The term version will be replaced by the term Compatibility levels and compatibility codes.
This section has become very long and is very crucial regarding its
social aspects.
There _have_ to be policies to be followed by the package maintainers.
I'm currently thinking of version numbers like
1.1.3.4.2 #(1 1 3 4 2)
2.7.3.1.1 #(2 7 3 1 1)
, where a change in one of the numbers means:
1. incompatible, changed interface semantics, called major package
number: the package is expected to be incompatible with older or newer
ones having another number here (at this position);
2. downwards compatible, called minor package number: the package has
changed, and their may be new features, but it is expected to work with
software written for lower numbers here (but with same 1. number, of
course);
3. downwards _and_ upwards compatible: the package has changed, but
there are _no_ new features here (but it may be faster for example), so
it is expected to work with software written for higher numbers here
(but with same 1., 2. numbers, of course);
4. compatible: 'small' fixes without changed functionality in the sense
above (also see 'Classification issues' below);
5. no code changes at all: no changed semantics, but e.g. improved class
comments.
After this scheme, a version number a.b.c.d. for a package P corresponds
to the Caps
'P',
'P_a',
'P_a.b',
'P_a.b.c',
'P_a.b.c.d',
'P_a.b.c.d.e'.
Caps 'P_a.b' - normally - includes _every_ Caps 'P_a.x', x b, since
the functionality/interface has just been smaller then. The longer
numbers are for expressing conflicts and requirements in a world not
being perfect.
This means, we finally have defined a relationship between Caps and
version numbers!
And it should be clear now, why there is this funny plural with the
'Caps' term: it is a normal case for a package-version combo, that it
provides a _set_ of Capabilities!
Classification issues
———————
It seems to be difficult to classify fixes (4.) correctly.
Fixes definitely change the formal semantics, so one has a good reason
to rank them higher and exchange them with 3. for example. A version
number change in 3. normally doesn't change the formal semantics (but
may introduce new bugs as a change in 4. as well, changing the formal
semantics then).
But if a 'small' fix just makes the package working with some seldom
used other package being the only one running into the bug, then the
classification as 4. makes sense (3. may introduce new bugs affecting
many packages).
But if the fix removes some serious problems affecting many other
packages, it may as well classified as 2., since there is good reason to
view this as an important upgrade.
A similar argumentation could be made for changes in the functionality
classified as 3.: a piece of code just running much faster without
changing the formal semantics, could open up new use cases. This may as
well earn a classification in 2..
Currently I think the intelligence of the package maintainers is
questioned here, since 'it depends'...
Note to fixes
————-
An important fix (changed version number 4.) can make the package work
the first time with another one. It may make sense - especially if the
major number recently has changed - to apply such a fix to an older
version, too!
This would lead to a new older package with a new number, of course.
Automatically upgrading
———————–
In general automatically upgrading should
- apply to all packages increasing their minor or lower ranked version
number,
- _not_ apply to packages increasing their major version number.
A harvesting process could be introduced using this technical solution
as follows: addditional classifications of packages as
stable/unstable/etc. could prefilter the number of packages to be
searched for fulfilling dependencies (this classification could also be
realised by just putting them into classified - different - package
directories).
Why major version number 1. at all?
———————————–
After this versioning policy automatically upgrading would (mostly) work
from version to version with a _fixed_ first version number. If the
major number changes, there are incompatible versions (since we have
defined it so!). This could lead to the question, why not to ommit this
major number and to force the package maintainer to publish a new
package with a different name instead.
Arguments for a major version number increase instead of a name change:
- There are cases for expressing the existence of some functionality at
a very high level independent from the major number: e.g. some package
wants to have a package WebBrowserStandard for enforcing to give the
user a chance of viewing its generated HTML files (without assuming any
API for calling it itself): a newly created name (how to guess it for
other package maintainers?) instead of a major number increase would
make expressing this dependency impossible.
- Though an interface has changed, the functionality may be very
similar, and the package name should express functionality.
- The package name combined with the major number could be seen as the -
technically and socially - needed new name.
Consequences
————
This is a client POV versioning policy.
There may be others, of course: IMHO it's not so important which policy
to have, but
___ It's very important to have a policy at all! ___
Otherwise a technically working dependency mechanism doesn't work for
packages because of social reasons...
Technically this means to define some
Caps <-> version number
relation with an order of Caps corresponding to an order of
version numbers like described above (or to use a similar mechanism).
___ Otherwise the technical solution _cannot_ work! ___
Installation of packages
In general there are
- pre-install,
- do-install,
- post-install,
- pre-remove,
- do-remove,
- post-remove,
Scripts (they may be empty). They are triggered by performing an
(package install/removal) Action.
Normally the install phase results into adding all provided Caps and the
remove phase into the removal of them. Potential conflicts have to be
solved _before_ installation!
Different kind of installs
————————–
There are different kind of installs:
- upgrading,
- full installation with a previous removal of an older version (if it
exists).
Examples (for looking, if the concepts are working)
Package WebBrowserStandard
- Provides Caps 'WebBrowser' and more;
- needs Caps 'SocketStuff' and 'RenderingMachine';
- exists in versions 1.1.3.1.7, 2.1.2.3.1, 2.2.1.1.1;
- conflicts with package 'WebBrowserNicerButSlow' and some special
SocketStuff versions.
Each package version combo
WebBrowserStandard_1.1.3.1.7,
WebBrowserStandard_2.1.2.3.1, and
WebBrowserStandard_2.2.1.1.1
needs a Transformation describing pre- and post Caps sets.
E.g. for WebBrowser_2.2.1.1.1 there is the following:
a) It provides
Caps 'WebBrowserStandard_2.2' being a super set including all Caps
provided by WebBrowserStandard_2.1.2.3.1, but _not_ all Caps provided
by WebBrowser_1.1.3.1.7 (since the major number has changed);
b) It may require
Caps
('SocketStuff_3.4', 'RenderingMachine_2').
A package RenderingMachine_2.1 would provide the last requirement.
c) It may conflict
- with package WebBrowserNicerButSlow in general (since it uses the
same sockets); and
- with SocketStuff_3.4.3.7.x (arbitrary x), since the bugfix there had
some very special side effect - unfortunately another installed
important package PWorkaround needs exactly one of this versions of
SocketStuff: it made a workaround not compatible with a newer version of
it, where the side effect has been removed... (world is not perfect).
Note: if the user wants to install WebBrowserNicerButSlow or any other
package, all packages have to be checked for conflicts.
How to model c)?
- The conflict with package WebBrowserNicerButSlow is an all over
package conflict and will be modeled as a conflict with Caps
('WebBrowserNicerButSlow'), which includes all Caps
('WebBrowserNicerButSlow_a.b.c.d.e') for arbitrary a, b, c, d, e.
- The conflict with SocketStuff in versions 3.4.3.7.x is _not_ an all
over package conflict, it is a package-version conflict. This will be
modeled as a conflict with Caps ('SocketStuff_3.4.3.7').
d) It has a Transformation
requires: ('SocketStuff_3.4', 'RenderingMachine_2.1')
conflicts: ('SocketStuff_3.4.3.7')
|
V
provides: ('WebBrowserStandard', "all over package Caps"
'WebBrowserStandard_2', "major release"
'WebBrowserStandard_2.2', "minor release"
'WebBrowserStandard_2.2.1',
'WebBrowserStandard_2.2.1.1',
'WebBrowserStandard_2.2.1.1.1',
'WebBrowser' "logical Caps").
The last Caps in the result is a logical Caps provided by both packages
WebBrowserStandard and WebBrowserNicerButSlow. Such a beast makes sense
for expressing dependencies which shouldn't be bounded to a certain
package: in this example there may be a point in the system
automatically starting the installed WebBrowser, whatever it may be
(WebBrowserStandard or WebBrowserNicerButSlow).
The question in case of holding package PWorkaround is, if there is a
version SocketStuff_3.a.b.c.x with
a >= 4,
b, c, x arbitrary, but
not ((a = 4) & (b = 3) & (c = 7)),
which also gives the input Caps 'SocketStuff_3.4'! Otherwise it wouldn't
be possible to install WebBrowserStandard without removing PWorkaround
first.
So the package-version conflicts are reducing the number of packages
capable of providing the needed input caps.
Upgrades
An upgrading of WebBrowserStandard_2.1.2.3.1 to
WebBrowserStandard_2.2.1.1.1 may be modeled by
- a deletion of the package WebBrowserStandard_2.1.2.3.1, followed by
- an installation of WebBrowserStandard_2.2.1.1.1,
or by
- an incremental upgrade.
Upgrade by deletion/install
—————————
requires: ('WebBrowserStandard')
|
V
deletes: ('WebBrowserStandard', "all over package Caps"
'WebBrowserStandard_2', "major release"
'WebBrowserStandard_2.1', "minor release"
'WebBrowserStandard_2.1.2',
'WebBrowserStandard_2.1.2.3',
'WebBrowserStandard_2.1.2.3.1',
'WebBrowser' "only deleted, if there is no other package providing it").
Note: deletes are depending from the installed version and computed
dynamically.
This is followed by a Transformation installing the new version
WebBrowserStandard_2.2:
requires: ('SocketStuff_3.4', 'RenderingMachine_2.1')
conflicts: ('SocketStuff_3.4.3.7'
| 'WebBrowserStandard' "this is the point here!")
V
provides: ('WebBrowserStandard', "all over package Caps"
'WebBrowserStandard_2', "major release"
'WebBrowserStandard_2.2', "minor release"
'WebBrowserStandard_2.2.1',
'WebBrowserStandard_2.2.1.1',
'WebBrowserStandard_2.2.1.1.1',
'WebBrowser' "logical Caps").
The conflict of Caps 'WebBrowserStandard_2.2' with Caps
'WebBrowserStandard' leads to a search for the deletion Transformation:
after the deletion Transformation the conflict is resolved, and after
the installation Transformation Caps 'WebBrowserStandard' is back again.
This works independently from the installed older or newer version!
Incremental upgrade
——————-
requires: ('WebBrowserStandard_2.1')
|
V
deletes: ('WebBrowserStandard_2.1', "minor release"
'WebBrowserStandard_2.1.2',
'WebBrowserStandard_2.1.2.3',
'WebBrowserStandard_2.1.2.3.1')
provides: ('WebBrowserStandard_2.2', "minor release"
'WebBrowserStandard_2.2.1',
'WebBrowserStandard_2.2.1.1',
'WebBrowserStandard_2.2.1.1.1').
Note: the Caps for all over package 'WebBrowserStandard', the major
release 'WebBrowserStandard_2' and the logical 'WebBrowser' haven't been
changed here.
Make tool
A Caps set needed by an executable corresponds to e.g. a couple of
object files created from another couple of source and header files.
The important point here is, that changing a required (e.g. a header)
file leads to the need for regenerating all files depending on it:
- if all the requirement files are older, all is OK; but
- if just one requirement file is newer, the target has to be build again.
Each file corresponds to a provided Caps. The semantics of a such a Caps
is, that
- the file exists, and
- it is newer than its required Caps corresponding to files (there may
be more).
Note: this is another motivation for the use of plural in Caps...
Each not automatically generated file (e.g. header, source files)
fulfills the first condition, but not necessarily the second.
Dependencies may be modeled
- flat, so that the Transformation for each generated file requires all
direct or indirect files in the dependency chain (e.g. both headers, if
there is a header including another header);
- hierarchically, so that the Transformation for each generated file
requires only the direct dependencies.
An example for Transformations:
requires: ('funnyLib.so' 'fancyProg.o')
| action: linking
V
provides: ('fancyProg')
requires: ('funnyLib.o' 'someSysLib.so')
| action: linking
V
provides: ('funnyLib.so')
requires: ('funnyLib.c' 'funnyLib.h')
| action: compiling
V
provides: ('funnyLib.o')
requires: ('fancyProg.c' 'funnyLib.h')
| action: compiling
V
provides: ('fancyProg.o')
"header to header dependency"
requires: ('someSysLib.h')
| action: updating time stamp
V
provides: ('funnyLib.h')
This is a hierarchical modeling of dependencies.
For a flat modeling the previous "header to header
dependency"-Transformation could be omitted, but then two others
providing ('fancyProg.o') and ('funnyLib.o') had to be changed:
requires: ('fancyProg.c' 'funnyLib.h' 'someSysLib.h')
| action: compiling
V
provides: ('fancyProg.o')
requires: ('funnyLib.c' 'funnyLib.h' 'someSysLib.h')
| action: compiling
V
provides: ('funnyLib.o')
The algorithm would be a depth first traversing of the dependency graph
and performing the corresponding Action, if the output Caps conditions
(file exists and time stamp is newer than this of its requirements) are
not fulfilled. In the case of the header to header dependency above,
the Action would just be a 'touch' of the file.
A first step before could be to traverse the dependency graph without
performing the Actions, to see, if it is possible to build fancyProg at
all. This shows the two aspects of Transformations:
- describing the dependencies, and
- describing the actions to fullfill them.
Remark to packages: before installing a package the first aspect alone
is the interesting one to check for conflicts and missing dependencies.
To Lex's example
Obviously Lex has argued with another - not set oriented - dependency
mechanism in mind. His points are valid with this background.
So I've just used his example
- to show how it would work with the mechanisms described here, and
- _not_ to argue against him!
lex@cc.gatech.edu wrote:
> ...
> Let me run you through a small example. Packages A and B depend on
> Collections:
>
> A 1.0 needs Collections 1.0
> B 1.0 needs Collections 1.0
>
> Fine so far, I install all three packages. Now the collections
> library gets updated to 1.1. I cannot install the upgrade without
> breaking the dependencies of A and B!!
After the proposed versioning policy the upgrade would be possible,
since Caps ('Collections_1.1') is a superset of ('Collections_1.0').
But here again: we _need_ a versioning policy, which people are following!
> So, I wait before installing
> it, even though I might be the main developer of package C, which
> also uses Collections. Okay, so eventually tthe author of A, being a
> great citizen, upgrades their Collection package and reruns their
> tests – shock, nothing brock. While they are at it, they add a few
> class comments, and then post A 1.1 which depends on Collections 1.1.
"Transformation for A 1.1"
requires: ('Collections_1.1')
| action: installing
V
provides: ('A_1.1', ...)
> Drats, I still cannot update my Collections library, because that
> will make me uninstall B. Note that I still cannot upgrade my
> Collections library, unless I uninstall B.
There is no problem with the proposed scheme here.
But lets introduce an odd incompatibility:
Transformation for B 1.0
requires: ('Collections_1.0')
conflicts: ('Collections_1.1')
| action: installing
V
provides: ('B_1.0', ...)
, which is a violation of our policy; but hey, shit happens. Let's
further assume that ('Collections_1.x'), x >= 2 would be OK again.
This would trigger a conflict if trying to upgrade to A 1.1, which is
the wished thing here, since there is a real problem then.
But after Collections 1.2 being out, the A 1.1 upgrade would work, since
then dependency resolver would just use the Transformation to Caps
('Collections_1.2') as a superset providing ('Collections_1.1') as well.
But thinking about this sheds light to a related problem.
What about B 1.0 being incompatible to _all_ versions of Collections
above 1.0?
At first this would be a serious violation of the versioning policy.
Second, this leads to the feature request of being able to express such
an incompatibility as argument to 'conflicts:' (this has led to a change
in the definition of Transformations above).
>
> Finally, suppose Collections gets updated to 1.2, and finally B gets
> around to doing an upgrade. B 1.1 depends on Collections 1.2. Now
> what? I _still_ cannot upgade B, because it depends on Collections
> 1.2, which is inconsistent with all available versions of A. I end
> up using A 1.0, B 1.0, and Collections 1.0. And I still cannot
> update the version of Collections that my C package works with,
> because I can't install the Collections update anyway. If I'm lucky,
> package A will release a version that works with 1.2 and I can
> upgrade everything. But notice: int hat case, every single package
> in the example has had to _synchronize_ their releases, in order to
> reach a state where the jigsaw has a solution. I could as well be
> unlucky, and A might declare itself compatible with Collections
> 1.3.....
>
> It appears that all the packages need to be upgraded in lockstep. I
> can't offer you a proof for the more general case :), but I imagine
> it will only get _worse_ as more packages enter the picture. Is it
> acceptible that every package needs to be tested with each
> incremental version of every other package, and thus achieve the
> lockstep progression? That seems very inefficient if most package
> updates are compatibility-preserving bug fixes.
Thinking in capability sets and a versioning policy is needed.
But testing is nevertheless important: it would be very good to have
many automatically runnable tests to classify package combinations as
stable/unstable/bleedingEdge/etc.. Since we are faced with a
combinatorial explosion here, hints regarding
stable/unstable/bleedingEdge/etc. from the package maintainers would be
helpful though...
> ...
Relationships with existing tools and concepts
SM
If the proposed version policy would be used for classifying packages at
SM, the release flag of packages would be replaced or modelled by a
corresponding version number, which is much more fine granular.
An important question:
Who is responsible for maintaining logical packages?
An - already known - example: packages WebBrowserStandard and
WebBrowserNicerButSlow may both generate Caps 'WebBrowser' by an
installation. There also may be a logical package WebBrowser which just
depends on one of them. But who makes the choice? This is similar to the
question, who decides which stuff is worth enough to come into the
official distribution.
It would be interesting to enrich SM with a dependency mechanism as
described in this paper...
Monticello
Monticello versions are _not_ package versions as described here! A
'released' Monticello version needs to be assigned a package version
number with some policy as described above.
Class extensions
It would be nice to have a detection of class extension conflicts. The
most simple variant (there are more!) would be to detect, if some
installation tries to overwrite an existing class extension method with
changed _code_ (a changed comment doesn't matter) and ask the user how
to proceed.
Note: I have had the problem of wanting to use a class extension which
another package also had made, without having a dependency from the
other package (I just used this small class extension and not the other
package). I haven't changed the code (and therefore semantics) of this
method (so this has not been a problem _here_); but it was just by
chance, that I had seen this class extension from the other package at
all (since it was installed incidentally).
It's easy to introduce a not compatible class extension without knowing...
While thinking about this, I have an idea: what about a repository
server registering class extensions? Then tools could check for a
potential conflict with whatever package introducing them...
Missing Stuff
Naturally many things are missing here, a few of them are
- security considerations:
- web of trust of package maintainers,
- signature of packages,
- data encryption while communicating with the package
- directory,
- repositories;
- Debian-like unstable -> testing -> stable process;
- single or multiple package directories (SMs).
Roadmap (loosely, may change)
Getting a consensus for a compatibility code policy (to come to a consensus at this point is _very_ important, _independently_ from the chosen technical solution!) by
- getting feedback via ML discussions,
- posting an improved draft,
for some iterations.
Going further with discussions about technical ideas: the concepts should be good _before_ coding. This doesn't mean to discuss forever and not to start with coding after a while...
Personal remarks
Don't try to be too perfect: KISS!
I have to admit that KISS seams to be quite complex in this domain...
I'm willingly to invest some more time - e.g. by coding - into
Dependencies for Squeak, but there should be a good chance, that
the results won't be thrown into the trash can...
Stephan
