But wait, putting things into a defined order isn't that hard, right? Why would one need dedicated tools for this? Database records are ordered by SQL expressions, PHP provides more sort functions than there are sand grains on earth and just in case, TYPO3's List module has those neat arrows where the human can decide the order manually. So, what is this all about?
Well, we call it "relative ordering"!
There has been this pre-historic time in TYPO3, where the extensions one wants to load were defined in a simple list. What most people did not know, or learned the hard way, is that the order of extensions provided in this list also determined the order the extension were loaded, i.e. the order the configuration from
ext_localconf.php and other files was parsed. If extensions had hidden dependencies on other extensions, one had to know where to put it in the list.
Back in the days the Core team launched an attempt to get rid of this manual labour and error prone process. Why not creating this list automatically? Why should the integrator know about those inner details?
This was the birth of the infamous
Putting items into an order can be as simple as to assign a number to each item and then sorting those items by the number. Easy.
Things get out of hand once those numbers are not assigned by a central entity (call it integrator), but by multiple entities (call them extension authors).
Considering that all items have to be arranged for being consumed (e.g. hook registration) and the smaller number wins, one can be sure that there are at least two problems:
- Extension first_ext takes number 1 and extension second_ext takes number 2. How does extension third_ext squeeze inbetween if it has to?
- All extensions want to be first and choose number 1. The last (or first) one wins, all others are discarded.
These problems are standard problems when thinking about ordering. Be it "call order", "priority determination" or similar.
Considering those standard use cases there is one important observeration: Individual items are never interested in their absolute position! The actual number does not matter to them.
What matters is the relation between the items:
- Item A needs to be before item B
- Item C before B
- Item D after A
This ultimately already yields a defined order, but without using any absolute metric.
The cool thing is, there are algorithms that can cope with such rule sets and calculate the final order.
All of a sudden the entity controlling an item does not need to know the whole set of items out there. Also numbers do not matter anymore. All that is needed is a way to define the rules about the relation of items one entity cares about or is aware of.
In terms of extensions within the TYPO3 ecosystem: "I need to be before the news extension."
Quick an dirty this is how the
DependencyOrderingService is used:
$elementListWithRules = [ 'a' => ['before' => ['b']], 'c' => ['before' => ['b']], 'd' => ['after' => ['a']], ]; $orderedElements = GeneralUtility::makeInstance(DependencyOrderingService::class)->orderByDependencies($elementListWithRules);
The versatility of this service led to the current state where this service is used with the TYPO3 Core more than 50 times, for a lot of different usages.
Just to name a few:
- Package Manager: The
PackageStates.php, which holds the ordered list of loaded extensions, is created with the service. The ordering criteria are the dependencies of an extension to other extensions.
- Form Engine: The data fed into an edit form in the backend is collected using a large collection of specialized processors. The order of these processors and which is to used when is determined by the
- The order of the tables shown in the List module can be influenced by page TSconfig using this service. 
In order to derive a flat list of items from the given rule set, the rules are coded into an adjacency matrix representing a directed acyclic graph (DAG). We call it the dependency graph. The graph is then processed in multiple steps to validate and optimize it. Finally, a topolicial sorting algorithm is used to produce the flat list of items. 
There are times where order is based on some dependencies (like extensions), but the referenced dependencies are not necessarily present in the system. We call that optional dependencies. The
DependencyOrderingService has an option to cope with such situations, which was explicitly crafted for the Package Manager in TYPO3. Take a look into the code if you are interested into these mechanics.
So, should you always use this service from now on? Definitely NO. Think about the use case, what has to be put into order. Keep in mind that sorting some numbers is the fastest thing you can do, whereas this service does take some resources to come up with a result. It is a graph algorithm after all.
Why does Reelworx know so much about this in detail? Well, ... we crafted it back in 2013 and we are happy it was a success!