Draft spec for new dpkg "triggers" feature (v2, repost)
In late January and February we had a thread about my proposals for a
new dpkg triggers feature. Thanks very much to everyone who provided
feedback.
Following some very cogent criticisms from Florent Rougon I posted a
significantly version on the 2nd of March but we were all too busy
trying to release and/or being flamed, and it seems that no-one read
my article. At least, no-one replied. So herewith a repost with a
slightly wider distribution.
I'd appreciate it if particularly people who maintain large groups of
packages which might use the triggers feature would take some time to
read my draft specification and comment on it. If you don't tell me
now why it's broken then please don't blame me later after I've
implemented it and it ate your system :-).
Followups should probably go to debian-dpkg.
Thanks,
Ian.
TRIGGERS
========
Introduction
------------
A dpkg trigger is a facility that allows events caused by one package
but of interest to another package to be recorded and aggregated, and
processed later by the interested package. This feature simplifies
various registration and system-update tasks and reduces duplication
of processing.
(NB: Triggers are intended for events that occur during package
installation, not events that occur in general operation.)
Concepts
--------
Each trigger is named, and at any time zero or more packages may be
interested in it.
We currently envisage three kinds of triggers:
* Explicit triggers. These can be activated by any program
by running dpkg-trigger (at any time, but ideally from a maintainer
script).
* File triggers. These are activated automatically by dpkg
when a matching file is installed, upgraded or removed as part
of a package. They may also be explicitly activated by running
dpkg-trigger.
* Special triggers, which activate magic code in dpkg itself.
Currently none of these are defined.
A trigger is always activated by a particular package.
Trigger names contain only printing 7-bit ascii characters (no
whitespace). Each trigger kind has a distinct subset of the trigger
name space so that the kind can be determined from the name. After we
run out of straightforward syntaxes, we will use <kind>:<details>.
When a trigger is activated, it becomes pending for every package
which is interested in the trigger at that time. Each package has a
list of zero or more pending triggers. Repeated activation of the
same trigger has no additional effect. Note that in general a trigger
will not be processed immediately when it is activated; processing is
deferred until it is convenient (as described below).
At a trigger activation, the activating interested packages(s) are
added to the activating package's list of triggers-awaited packages;
the activating package is said to await the trigger processing.
A package which has pending triggers, or which awaits triggers, is not
considered properly installed. There are two new dpkg status values,
`triggers-pending' and `triggers-awaited', which lie between
`config-failed' and `installed'.
Details - Overview table
------------------------
Status Pending Awaited Satisfies Remedy
triggers triggers Depends
unpacked never maybe No postinst configure
c.-failed never maybe No postinst configure (when requested)
t.-awaited no always No postinst triggered + fix awaited pkg(s)
t.-awaited yes always No fix awaited package(s)
t.-pending always never Yes postinst triggered
installed never never Yes n/a
Details - triggering package
----------------------------
When a package T activates a trigger in which an package I is
interested, I is added to the list of packages whose trigger
processing is awaited by T. Zero or more packages I may be added as a
result of any particular trigger activation, depending on how many
packages were interested.
A package which awaits trigger processing but would otherwise be
`installed' or `triggers-pending' is considered to be in state
`triggers-awaited'. Packages in `triggers-awaited' do not satisfy
Depends dependencies.
Every triggered package I in T's list of awaited packages either has a
nonempty list of pending triggers, or is in `config-failed' or worse.
When I enters `installed' (or `config-files' or `not-installed'), the
entry in T's list of awaited packages is removed so that T may, if it
no longer awaits any packages, become `installed' or
`triggers-pending'.
Details - triggered package
---------------------------
When one of the triggers in which a package is interested is activated
the triggered package goes has the trigger added to its list of
pending triggers. Packages with a nonempty list of pending triggers
which would otherwise be in state `installed' are in state
`triggers-pending' instead, so if the package was previously
`installed' it becomes `triggers-pending'.
If a package has nonempty lists both of pending and awaited triggers,
then it is in `triggers-awaited'. Nevertheless efforts will still be
made to process its triggers so as to make the list of pending
triggers empty.
To restore a package in state `triggers-pending' to `installed', or to
process pending triggers of a package with both pending and awaited
triggers, dpkg will run the postinst script:
postinst triggered "<trigger-name> <trigger-name> ..."
This will be attempted for each relevant package at the end of each
dpkg run; so, normally, in the same dpkg run as the event which made
the package go to `triggers-pending'. This leaves packages in
reasonable states by default.
If the `postinst triggered' run fails the package goes to
`config-failed', so that the trigger processing will not be attempted
again until explictly requested.
|
V
,------------.
| unpacked |
`------------'
|
|
(automatic)| ,----------.
| | config- |
| | failed |
| `----------'
| | ^
| | |
|,---<--' |
| (user |
postinst | request) |
"configure" | | ,------------------.
| | | triggers-pending |
| | `------------------'
|`----->------'| | ^
| error | postinst | |
| | "triggered" | | trigger(s)
| | (automatic) | | activated
| | | |
| `-----<-----------'| |
| error | |
| | |
V V |
,------------------------------------------------.
| installed |
`------------------------------------------------'
Packages in `config-failed' or worse are never considered to have
lists of pending triggers.
This means that if a triggering package T awaits trigger processing by
an interested package I, and I goes to `config-failed' or worse (eg,
during unpack for upgrade), then when I is reconfigured (goes to
`installed') or removed, T will no longer await processing by I, so
that T may automatically go from `triggers-awaited' to `installed'.
Timing guarantees, races, etc.
------------------------------
Activating a trigger will not have any immediate effect, although
putative resulting status changes will show up in dpkg --status etc.
(Putative because the actual status changes may depend on the state of
trigger interests when dpkg processes the trigger activation into
the status database, rather than that when dpkg --status is run.)
A package is only guaranteed to become notified of a trigger
activation if it is continuously interested in the trigger, and never
in `config-failed' or worse, during the period from when the trigger
is activatated until dpkg runs the package postinst (either due to
--configure --pending, or at the end of the relevant run, as described
above). Subsequent to activation and before notification, the
interested package will not be considered in state `installed', so
long as the package remains interested, and the triggering package
will not be considered `installed'.
If the package is not in state `installed', `triggers-pending' or
`triggers-awaited' then pending triggers are not accumulated.
However, such a package (between `half-installed' and `config-failed'
inclusive) declares some trigger interests then the triggering
packages *will* await their trigger processing (or removal).
It is not defined in what order triggers will run. dpkg will make
some effort to minimise redundant work in the case where many packages
have postinst trigger processing activating another package's triggers
(for example, by processing triggers in fifo order during a single
dpkg run). Cycles in the triggering graph are prohibited and will
eventually, perhaps after some looping, be detected by dpkg and cause
trigger processing to fail; when this happens one of the packages
involved will be put in state `config-failed' so that the trigger loop
will not be reattempted. See `Cycle detection' below.
Explicit triggers
-----------------
Explicit triggers have names with the same syntax as package names,
*but* should *not* normally be named identically to a package.
When choosing an explicit trigger name it is usually good to include a
relevant package name or some other useful identifier to help make the
trigger name unique. On the other hand, explicit triggers should
generally not be renamed just because the interested or activating
packages' names change.
Explicit trigger names form part of the interface between packages.
Therefore in case of wider use of any trigger the name and purpose
should be discussed in the usual way and documented in the appropriate
packaging guidelines (eg, in policy).
File triggers
-------------
File triggers have names of the form
/path/to/directory/or/file
and are activated when the specified filesystem object, or any object
under the specified subdirectory, is created, updated or deleted by
dpkg during package unpack or removal. The pathname must be absolute.
File triggers should not generally be used without mutual consent.
The use of a file trigger, and the name of the trigger used, should be
stated in policy, so that a package which creates a relevant file in a
maintainer script can activate the trigger explictly.
File triggers must definitely not be used as an escalation tool in
disagreements between different packages as to the desired contents of
the filesystem. Trigger activation due to a particular file should
not generally modify that file again.
Configuration files (whether dpkg-handled conffiles or not), or any
other files which are modifed at times other than package management,
should not be used for file triggers; dpkg triggers are not a general
mechanism for filesystem monitoring.
If there are or might be directory symlinks which result in packages
referring to files by different names, then to be sure of activation
all of the paths which might be included in packages should be listed.
The path specified by the interested package is matched against the
path included in the activating package, not against the truename of
the file as installed. Only textually identical filenames (or
filenames where the interest is a directory prefix of the installed
file) are guaranteed to match.
A file trigger is guaranteed to be activated before the file in
question is modified by dpkg; on the other hand, a file trigger might
be activated even though no file was actually modified.
Because of the restriction on trigger names, it is not possible to
declare a file trigger for a directory whose name contains
whitespace. Such a trigger should not be necessary.
Package declarations regarding triggers
---------------------------------------
A package declares its relationship to some trigger(s) by including a
`triggers' file in its control archive (ie, DEBIAN/triggers during
package creation). This file contains directives, one per line.
Leading and trailing whitespace is trimmed and lines starting with #
and empty lines will be ignored.
The trigger control directives currently supported are:
interest <trigger-name>
Specifies that the package is interested in the named trigger.
All triggers in which a package is interested must be listed using
this directive in the triggers control file.
Trigger names not matching any currently supported trigger kind
name syntax are ignored for `interest'. This will allow future
extensions (see TRANSITION PLAN, below).
activate <trigger-name>
Arranges that any change of the package's state will activate the
specified trigger. The trigger will be activated just before the
package state changes.
Unknown directives, or unknown trigger name syntaxes for `activate',
are an error which will prevent installation of the package. dpkg-deb
will be changed to to warn about unrecognised trigger names syntaxes
and unrecognised trigger control directives.
New command-line interfaces to dpkg tools
-----------------------------------------
dpkg will grow new options:
--suppress-triggers
Do not run any triggers in this run (activations will still be
recorded). If used with dpkg --configure <some package> or
--process-triggers <some package> then the named package
postinst will still be run even if only a triggers run is
needed.
--no-suppress-triggers
Cancels a previous --suppress-triggers.
--triggers
Processes only triggers. All pending triggers will be
processed. If package names are supplied only those packages'
triggers will be processed, exactly once each where necessary.
Use of --suppress-triggers, or an explicit list of packages with
--triggers, may leave packages in the improper `triggers' state. This
can be fixed later by running one of:
dpkg --configure --pending
dpkg --triggers
A trigger may be activated explicitly with:
dpkg-trigger [--verbose] [--by-package <package>] <name-of-trigger>
dpkg-trigger --query <name-of-trigger>
This can be used by maintainer scripts in complex and conditional
situations where the file triggers, or the declarative `activate'
triggers control file directive, are insufficiently rich. It can also
be used for testing and by system administrators (but note that the
triggers won't actually be run by dpkg-trigger - see `Timing...',
above).
The --by-package option should not normally be necessary. dpkg will
be modified to set an environment variable DPKG_MAINTSCRIPT_PACKAGE in
the environment of maintainer scripts, naming the package to which the
script belongs, and this will be used by default.
The --verbose and --query options will show which packages were
interested and what the current activation state is, on stdout in
human- and machine-readable (untranslated) format. Without any
options there will be no output to stdout, and none to stderr unless
dpkg-trigger is unable to make a record of the trigger activation.
With --query no trigger is activated.
Unrecognised trigger name syntaxes are an error for dpkg-trigger.
NB that in the case of a file trigger the name of the trigger is
needed, not the name of a file which would match the trigger.
apt and aptitude
----------------
These must be taught about the new `triggers-awaited' and
`triggers-pending' states. Packages in these states should be treated
roughly like those in `unpacked': the remedy is to run dpkg
--configure.
Normally apt and aptitude will not see packages in `triggers-pending'
since dpkg will generally attempt to run the triggers thus leaving the
package in `config-failed' or `installed'.
Note that automatic package management tools which call dpkg (like apt
and aptitude) should not attempt to configure individual packages in
state `triggers' with dpkg --triggers <package>... or dpkg
--suppress-triggers --configure <package>..., or similar approaches.
This would defeat dpkg's trigger cycle detection.
Error handling
--------------
Packages should be written so that they DO NOT BREAK just because
their pending triggers have not yet been run. The functionality
relating to the unprocessed trigger may fail (ie, the package which is
awaiting the trigger processing may be broken), but the remainder of
the interested package must work normally.
For example, a package which uses file triggers to register addons
must cope with (a) an addon being dropped into the filesystem but not
yet registered and (b) an addon being removed but not yet
deregistered. In both of these cases the package's main functionality
must continue to work normally; failure of the addon in question is
expected, warning messages are tolerable, but complete failure of the
whole package, or failures of other addons, are not acceptable.
dpkg cannot ensure that triggers are run in a timely enough manner for
those pathological error behaviours to be tolerable.
Where a trigger script finds bad data provided by a triggering
package, it should generally report to stderr the problem with the bad
data and exit nonzero, leaving the interested package in config-failed
and the triggering package in triggers-awaited and thus signalling the
problem to the user.
Alternatively, in some situations it may be more desirable to allow
the interested package to be configured even though it can only
provide partial service. In this case clear information will have to
be given in appropriate places about the missing functionality, and a
record should be made of the cause of the errors. However, this
option is not normally recommended unless the coupling between the
interested and triggering package is particularly loose.
WORKED EXAMPLE - SCROLLKEEPER
=============================
Currently, every Gnome program which comes with some help installs the
help files in /usr/share/gnome/help and then in the postinst runs
scrollkeeper-update. scrollkeeper-update reads, parses and rewrites
some large xml files in /var/lib/scrollkeeper; currently this
occurs at every relevant package installation, upgrade or removal.
When triggers are available, this will work as follows:
* gnome-foobar will ship its `omf' file in /usr/share/omf as
normal, but will not contain any special machinery to invoke
scrollkeeper.
* scrollkeeper will in its triggers control file say:
interest /usr/share/omf
and in its postinst say:
scrollkeeper-update -q
dpkg will arrange that this is run once at the end of each run
where any documentation was updated.
Note that it is not necessary to execute this only on particular
postinst "$1" values; however, at the time of writing, scrollkeeper
does this:
if [ "$1" = "configure" ]; then
printf "Rebuilding the database. This may take some time.\n"
scrollkeeper-rebuilddb -q
fi
and to retain this behaviour, something along the following lines
would be sensible:
if [ "$1" = "configure" ]; then
printf "Rebuilding the database. This may take some time.\n"
scrollkeeper-rebuilddb -q
else
printf "Updating GNOME help database.\n"
scrollkeeper-update -q
fi
* dh_scrollkeeper will only adjust the DTD declarations and no longer
edit maintainer scripts.
Full implementation of the transition plan defined below, for
scrollkeeper, goes like this:
1. Update scrollkeeper:
- Add a `triggers' control archive file containing
interest /usr/share/omf
- Declare a versioned dependency on the triggers-supporting
dpkg.
- Make the postinst modifications as described above.
2. In gnome-policy chapter 2, `Use of scrollkeeper',
- delete the requirement that the package must depend on
scrollkeeper
- delete the requirement that the package must invoke
scrollkeeper in the postinst and postrm
- instead say:
OMF files should be installed under /usr/share/omf in the
usual way. A dpkg trigger is used to arrange to update the
scrollkeeper documentation index automatically and no special
care need be taken in packages which supply OMFs.
If an OMF file is placed, modified or removed other than as
an file installed in the ordinary way by dpkg, the dpkg file
trigger `/usr/share/omf' should be activated; see the dpkg
triggers specification for details.
Existing packages which Depend on scrollkeeper (>= 3.8)
because of dh_scrollkeeper or explicit calls to
scrollkeeper-update should be modified not to Depend on
scrollkeeper.
3. Update debhelper's dh_scrollkeeper not to edit maintainer
scripts. dh_scrollkeeper should also issue a warning if it finds
scrollkeeper (>= 3.8) in the Depends control file line.
4. Remove the spurious dependencies on scrollkeeper, at our leisure.
As a bonus, after this is complete it will be possible to remove
scrollkeeper while keeping all of the documentation-supplying
gnome packages installed.
5. If there are any packages which do by hand what dh_scrollkeeper
does, change them not to call scrollkeeper-update and change their
dependency to refer to the triggers-interested scrollkeeper
version, or delete the dependency entirely.
This not 100% in keeping with the full transition plan defined below:
if a new gnome package is used with an old scrollkeeper, there is some
possibility that the help will not properly be available.
However, dh_scrollkeeper doesn't generate the scrollkeeper dependency
in the control file, which makes it excessively hard to get the
dependency up to date. (This was a mistake in the design of
dh_scrollkeeper.) The bad consequences of the inaccurate dependencies
are less severe than the contortions which would be required to deal
with the problem.
TRANSITION PLAN
===============
>From old dpkg to new dpkg
-------------------------
The first time a trigger-supporting dpkg is run on any system, it will
activate all triggers in which anyone is interested, immediately.
These trigger activations will not be processed in the same dpkg run,
to avoid unexpectedly processing triggers while attempting an
unrelated operation. dpkg --configure --pending (and not other dpkg
operations) will run the triggers, and the dpkg postinst will warn the
user about the need to run it.
To use this correctly:
* Packages which are interested in triggers, or which want to
explicitly activate triggers, should Depend on the
triggers-supporting version of dpkg.
* Update instructions and tools should arrange to run
dpkg --configure --pending
after the install; this will process the pending triggers.
dpkg's prerm will check for attempts to downgrade while triggers are
pending and refuse. (Since the new dpkg would be installed but then
refuse to read the status file.) In case this is necessary a separate
tool will be provided which will:
* Put all with any pending triggers into state `config-failed'
and remove the list of pending triggers.
* Remove the list of awaited triggers from every package. This
may cause packages to go from `triggers-awaited' to `installed'
which is not 100% accurate but the best that can be done.
* Remove /var/lib/dpkg/triggers (to put the situation to that which
we would have seen if the trigger-supporting dpkg had never been
installed).
Higher-level programs
---------------------
The new dpkg will declare versioned Conflicts against apt and aptitude
and other critical package management tools which will be broken by
the new Status field values. Therefore, the new higher-level tools
will have to be deployed first.
The new dpkg will declare versioned Breaks against any known
noncritical package management tools which will be broken by the new
Status field value.
Transition hints for existing packages
--------------------------------------
When a central (consumer) package defines a directory where other leaf
(producer) packages may place files and/or directories, and currently
the producer packages are required to run an `update-consumer' script
in their postinst:
1. In the relevant policy, define a trigger name which is the name of
the directory where the individual files are placed by producer
packages.
2. Update the consumer package:
* Declare an interest in the trigger.
* Declare a versioned dependency on a triggers-supporting dpkg.
* In the postinst, arrange for the new `trigger' invocation to run
update-consumer. (The consumer package's postinst will alread
run update-consumer during configuration, and this should be
retained.)
3. Update the producer packages:
* In the postinst, remove the call to update-consumer
* Change the dependency on consumer to be versioned, specifying a
trigger-interested consumer.
4. After all producer packages have been updated according to step 3,
`update-consumer' has become an interface internal to the consumer
and need no longer be kept stable. If un-updated producers are
still of interest, incompatible changes to `update-consumer' imply
a versioned Breaks against the old producers.
(See also `Transition plan', below.)
If there are several consumer packages all of which are interested in
the features provided by producer packages, the current arrangements
usually involve an additional central switchboard package (eg,
emacsen-common). In this case:
1. Define the trigger name.
2. Update the switchboard to have any new functionality needed by the
consumers in step 3 (2nd bullet).
3. Update the consumer packages:
* Declare an interest in the trigger.
* In the postinst, arrange for the new `trigger' invocation to run
the compilation/registration process. This may involve scanning
for new or removed producers, and may involve new common
functionality from the switchboard (in which case a versioned
Depends is needed).
* The old interface allowing the switchboard to run
compilation/registration should be preserved, including
calls to the switchboard to register this consumer.
4. When all consumers have been updated, update the switchboard:
* Versioned dependency on triggers-supporting dpkg.
* Make the registration scripts called by producers be no-ops.
* Versioned Breaks, against the old (pre-step-3) consumers.
5. After the switchboard has been updated, producers can be updated:
* Remove the calls to the switchboard registration/compilation
functions.
* Change the dependency on the switchboard to a versioned one,
specifying the one which Breaks old consumers. Alternatively,
it may be the case that the switchboard is no longer needed (or
not needed for this producer), in which case the dependency on
the switchboard can be removed in favour of an appropriate
versioned Breaks (probably, identical to that in the new
switchboard).
6. After all the producers have been updated, the cruft in the
consumers can go away:
* Remove the calls to the switchboard's registration system.
* Versioned Breaks against old switchboards, or versioned Depends
on new switchboards, depending on whether the switchboard is
still needed for other common functionality.
7. After all of the producers and consumers have been updated, the
cruft in the switchboard can go away:
* Remove the switchboard's registration system (but not obviously
the common functionality from step 3, discussed above).
* Versioned Breaks against pre-step-6 consumers and pre-step-5
producers.
DISCUSSION
==========
The activation of a trigger does not record details of the activating
event. For example, file triggers do not inform the package of the
filename. In the future this might be added as an additional feature,
but there are some problems with this.
Broken producer packages, and error reporting
---------------------------------------------
Often trigger processing by will involve a central package
registering, compiling or generally parsing some data provided by a
leaf package.
If the central package finds problems with the leaf package data it is
usually more correct for only the inidividual leaf package to be
recorded as not properly installed. There is not currently any way to
do this and there are no plans to provide one.
The naive approach of giving the postinst a list of the triggering
packages does not work because this information is not recorded in the
right way (it might contain lacunae); enhancing the bookkeeping for
this to work would be possible but it is far better simply to make the
system more idempotent. See above for the recommended approach.
INTERNALS
=========
On-disk state
-------------
A single file /var/lib/dpkg/triggers/File lists all of the filename
trigger interests in the form
/path/to/directory/or/file package
For each explicit trigger in which any package is interested,
a file /var/lib/dpkg/triggers/<name-of-trigger> is a list of
the interested packages, one per line.
For each package which has pending triggers, the status field contains
an Triggers-Pending field which contains the space-separated names of
the pending triggers, and a Triggers-Awaited field which contains the
*package* names of the packages whose trigger processing is awaited.
See `Details - Overview table' above for the invariants which related
Triggers-Pending, Triggers-Awaited, and Status.
During dpkg's running /var/lib/dpkg/triggers/Deferred is a list of the
triggers which have been requested by dpkg-trigger but not yet
incorporated in the status file. Each line is a trigger name followed
by one or more triggering package names.
/var/lib/dpkg/triggers/Lock is the fcntl lockfile for the trigger
system. Processes hang onto this lock only briefly: dpkg-trigger
to add new activations, or dpkg to incorporate activations (and
perhaps when it update interests). Therefore this lock is always
acquired with F_GETLKW so as to serialise rather than fail on
contention.
Processing
----------
dpkg-trigger updates triggers/Deferred, and does not read or write the
status file or take out the dpkg status lock. dpkg (and dpkg-query)
reads triggers/Deferred after reading /var/lib/dpkg/status, and after
running a maintainer script. If the status database is opened for
writing then the data from Deferred is moved to updates as
Triggers-Pending and Triggers-Awaited entries and corresponding Status
changes.
This means that the dpkg is guaranteed to reincorporate pending
trigger information into the status file only 1. when a maintainer
script has finished, or 2. when dpkg starts up with a view to
performing some operation.
When a package is unpacked or removed, its triggers control file will
be parsed and /var/lib/dpkg/triggers/* updated accordingly.
Triggers are run as part of configuration. dpkg will try to first
configure all packages which do not depend on packages which are
awaiting triggers, and then run triggers one package at a time in the
hope of making useful progress. (This will involve a new `dependtry'
level in configure.c's algorithm.) The only constraint on the
ordering of postinsts is only the normal Depends constraint, so the
usual Depends cycle breaking will function properly. See `Cycle
detection' below regarding cycles in the `A triggers B' relation.
Processing - Transitional
-------------------------
The case where a triggers-supporting dpkg is run for the first time is
detected by the absence of /var/lib/dpkg/triggers/File. Each time the
triggers-supporting dpkg starts up without this file, it will set each
`installed' or `triggered' package to `triggers-pending' with a list
of triggers equal to its interests - but it will not create File at
this time.
When --configure --pending is run, indicating that the triggers system
should now be enabled, File and the per-trigger package lists in
/var/lib/dpkg/triggers/<trigger-name>, will be created from the
`triggers' control files of already-installed packages.
dpkg and/or dpkg-deb will be made to reject packages containing
Triggers-Pending and Triggers-Awaited control file fields, to prevent
accidents.
Cycle detection
---------------
In addition to dependency cycles, triggers raise the possibility of
mutually triggering packages - a cycle detectable only dynamically,
which we will call a `trigger cycle'.
Trigger cycles are detected using the usual hare-and-tortoise
approach. Each time after dpkg runs a postinst for triggers, dpkg
records the set of pending triggers (ie, the set of activated
<package, trigger name> tuples). If the hare set is a superset of the
tortoise set, a cycle has been found.
For guaranteed termination, it would be sufficient to declare a cycle
only when the two sets are identical, but because of the requirement
to make progress we can cut this short. Formally, there is supposed
to be a complete ordering of pending trigger sets satisfying the
condition that any set of pending triggers is (strictly) greater than
all its (strict) subsets. Trigger processing is supposed to
monotonically decrease the set in this ordering. (The set elements
are <package, trigger name> tuples.)
(See `Processing' above for discussion of dependency cycles.)
--
Reply to: