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. * Future kinds of special triggers, which are activated by magic code in dpkg itself. Currently none are defined besides file triggers. 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 :

. 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 interested packages(s) are added to the triggering package's list of triggers-awaited packages; the triggering 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 yes always No postinst triggered + fix awaited pkg(s) t.-awaited no always No fix awaited package(s) t.-pending always never Yes postinst triggered installed never never Yes n/a Packages in t-awaited and t-pending demand satisfaction of their dependencies just like packages in installed. Details - triggering package ---------------------------- When a package T activates a trigger in which a 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. (If T chooses, explicit trigger activation using dpkg-trigger of I by T need not make T become triggers-awaited in this way..) 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'. Packages in `config-files' or `not-installed' do not await triggers. Details - triggered package --------------------------- When one of the triggers in which a package is interested is activated, the triggered package 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 "

..." 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 | | triggers-pending | postinst | request) | | or | "configure" | | | t.-awaited with some pending | | | `------------------------------' | | | ^ |`----->------'| | | | error | postinst | | | | "triggered" | | trigger(s) | | (automatic) | | activated | | | | | `-----<-----------'| | | error | | | | | V V | ,--------------------------------------------------. | installed or t.-awaited with none pending | `--------------------------------------------------' Packages in `config-failed' or worse are never considered to have lists of pending triggers. A package whose postinst is being run can however acquire pending triggers during that run (ie, a package can trigger itself). 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'. Or to put it another way, triggered actions are considered irrelevant if the interested package I is not configured. When I's postinst is called with `configure', it must do whatever actions are necessary to deal with any trigger activations which might have occured while it was not configured, just as if the package was being configured for the first time. Trigger processing should be idempotent. The list of triggers being processed is provided to the postinst only so that it can optimise away redundant processing. In that case, where an interested package has more than one trigger and wants to process them differently, the list of triggers can be can be examined in a shell script like this: case " $3 " in *" trigger-name-a "*) process-trigger-a ;; esac Generally each trigger name should be tested for separately, as the postinst will often be called for several triggers at once. Note that if a package both activates triggers in other packages, and is interested in triggers of its own, its postinst may run for trigger processing before the postinst(s) of the package(s) it has triggered. 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 activated 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, if such a package (between `half-installed' and `config-failed' inclusive) declares some trigger interests then the triggering packages *will* await their configuration (which implies completion of any necessary 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 triggering 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 modified at times other than package management, should not rely on file triggers detecting all modifications; 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 triggering 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. Changes made by dpkg to the link count of a file, or to solely the inode number (ie, if dpkg atomically replaces it with another identical file), are not guaranteed to cause trigger activation. Because of the restriction on trigger names, it is not possible to declare a file trigger for a directory whose name contains whitespace, i18n characters, etc. Such a trigger should not be necessary. Package declarations regarding triggers --------------------------------------- See deb-triggers(5). Support future extension of the trigger name syntax with additional dpkg-generated triggers is as follows: a package which is interested in any unsupported trigger kinds cannot be configured (since such a package cannot be guaranteed to have these triggers properly activated by dpkg). Therefore no package can be interested in any unsupported trigger kinds and they can be freely activated (both by `activate' and by dpkg-trigger). dpkg-deb will be changed to warn about unrecognised trigger names syntaxes and unrecognised trigger control directives. New command-line interfaces to dpkg tools ----------------------------------------- See dpkg(1). Here is a summary of the behaviours: Command line Trigproc Trigproc Configure these any triggered ----------------------+---------------+---------------+----------------- --unpack no usually[1] none --remove n/a usually[1] none --install n/a usually[1] these --configure -a any needed usually[1] any needed --configure if needed usually[1] must, or trigproc --triggers-only -a any needed usually[1] none --triggers-only must usually not[1] none [1] can be specified explicitly by --triggers or --no-triggers See dpkg-trigger(1). A trigger may be activated explicitly with: dpkg-trigger [--by-package ] dpkg-trigger --no-await 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. 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-pending' (or indeed `triggers-awaited') with dpkg --triggers-only ... or dpkg --no-triggers --configure ..., or similar approaches. This might defeat dpkg's trigger cycle detection. A package management tool which will run dpkg --configure --pending at the end may use --no-triggers on its other dpkg runs. This would be more efficient as it allows more aggressive deferral (and hence more unification) of trigger processing. Error handling -------------- Packages should be written so that they DO NOT BREAK just because their pending triggers have not yet been run. It is allowed for the functionality relating to the unprocessed trigger to 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 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. This option is recommended for situations where the coupling between the interested and triggering package is particularly loose; an example of such a loose coupling would be Python modules. 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-now -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-now -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 - Make the postinst modifications as described above. - Rename scrollkeeper-update to scrollkeeper-update-now - Provide a new wrapper script as scrollkeeper-update: #!/bin/sh -e if type dpkg-trigger >/dev/null 2>&1 && \ dpkg-trigger /usr/share/omf; then exit 0 fi exec scrollkeeper-update-now "$@" 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. One of dh_scrollkeeper or lintian should be changed to issue a warning for packages with 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 drop their dependency on scrollkeeper. This is 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. Unfortunately, dh_scrollkeeper doesn't generate the scrollkeeper dependency in the control file, which makes it excessively hard to get the dependency up to date. The bad consequences of the inaccurate dependencies are less severe than the contortions which would be required to deal with the problem. TRANSITION PLAN =============== 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 (if this deferred triggers condition exists). (Any triggers activated or reactivated *after* this mass-activation will be processed in the normal way.) 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 packages 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. * Edit update-consumer so that if it is called without --real it does the following: if type dpkg-trigger >/dev/null 2>&1 && \ dpkg-trigger name-of-trigger; then exit 0 fi If this fails to cause update-consumer to exit, it should do its normal update processing. Alternatively, if it is more convenient, update-consumer could be renamed and supplanted with a wrapper script which conditionally runs the real update-consumer. * In the postinst, arrange for the new `triggered' invocation to run update-consumer --real. The consumer package's postinst will already run update-consumer during configuration, and this should be retained and supplemented with the --real option (or changed to call the real script rather than the wrapper). 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. This can be done at our leisure. Ideally for loosely coupled packages this would be done only in the release after the one containing the triggers-interested consumer, to facilitate partial upgrades and backports. 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: -- NOTE - this part of the transition plan is still a proof of concept and we might yet improve on it 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: * Make the registration scripts called by producers try to activate the trigger and if that succeeds quit without doing any work (as for bullet 2 in the simple case above). * 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 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 individual 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 suffer from 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/ is a list of the interested packages, one per line. These interest files are not updated to remove a package just because a state change causes it not to be interested in any triggers any more - they are updated when we remove or unpack. For each package which has pending triggers, the status file contains a Triggers-Pending field which contains the space-separated names of the pending triggers. For each package which awaits triggers the status file contains 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 relate Triggers-Pending, Triggers-Awaited, and Status. During dpkg's execution, /var/lib/dpkg/triggers/Unincorp 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. The triggering package name "-" is used to indicate one or more package(s) which did not need to await the trigger. /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 updates interests). Therefore this lock is always acquired with F_GETLKW so as to serialise rather than fail on contention. Processing ---------- dpkg-trigger updates triggers/Unincorp, and does not read or write the status file or take out the dpkg status lock. dpkg (and dpkg-query) reads triggers/Unincorp after reading /var/lib/dpkg/status, and after running a maintainer script. If the status database is opened for writing then the data from Unincorp is moved to updates as Triggers-Pending and Triggers-Awaited entries and corresponding Status changes. This means that 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/Unincorp. When the triggers-supporting dpkg starts up without this it will set each package's list of pending triggers equal to its interests (obviously only for packages which are in `installed' or `triggers-pending'). This may result in a package going from `installed' to `triggers-pending' but it will not create the directory at this time. Packages marked as triggers-pending in this way will not be scheduled for trigger processing in this dpkg run. dpkg will also at this time create /var/lib/dpkg/triggers if necessary, triggers/File, triggers/Unincorp, and the per-trigger package lists in /var/lib/dpkg/triggers/, so that future trigger activations will be processed properly. Only dpkg may create /var/lib/dpkg/triggers and only when it is holding the overall dpkg status lock. 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 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 tuples.) (See `Processing' above for discussion of dependency cycles.) --