DEV Community

Cover image for Deterministic Does Not Mean Alphabetical: Dependency Ordering in PHP Package Tooling
Vladyslav
Vladyslav

Posted on

Deterministic Does Not Mean Alphabetical: Dependency Ordering in PHP Package Tooling

Coretsia Engineering Notes — 01

Two package installers can generate exactly the same set of autoload entries for the same application and still produce different runtime behavior. One generated bootstrap initializes successfully, while the other fails with an undefined-function error before reaching the application's own entry point. The difference lies not in which files were installed, but in the order in which they are executed.

Sorting generated PHP artifacts alphabetically may seem like a straightforward way to achieve determinism. While this approach works well for unordered collections, executable initialization sequences require stronger guarantees: their ordering must preserve the underlying dependency relationships.

When deterministic ordering breaks application startup

While exploring PHP package tooling, I came across an interesting problem involving the order of generated autoload entries. A package installer can correctly identify every file that needs to be included, yet generate an invalid initialization sequence by sorting packages alphabetically instead of respecting their dependency relationships. If a package invokes a function provided by one of its dependencies during initialization, loading the dependent package first may cause application startup to fail despite all required packages being correctly installed.

This raises an important engineering question: what does it actually mean for a generated artifact to be deterministic? Comparing package lists, file counts or unordered collections of autoload entries is insufficient when execution order is itself part of the contract.

Why autoload.files is different

PHP's class autoloading mechanism can resolve a class when it is needed, but it does not provide an equivalent mechanism for discovering arbitrary standalone function definitions. Composer's autoload.files addresses this by eagerly including designated PHP files when vendor/autoload.php is required, after the class loader has been registered.

The Composer schema documentation defines dependency-aware inclusion order, alphabetical ordering for equally ranked packages, and the placement of root-package files after dependency files. This distinction matters because an autoload.files entry is not simply a path in a lookup table: it represents executable PHP code. If that code invokes a function supplied by another package during inclusion, the function must already exist.

A minimal reproduction

To isolate the underlying ordering problem, I prepared a minimal reproduction consisting of two local PHP packages, without external package dependencies. The package names are intentional: application sorts before helpers, even though the dependency must be initialized first.

acme/application requires acme/helpers
Enter fullscreen mode Exit fullscreen mode

packages/helpers/composer.json:

{
    "name": "acme/helpers",
    "version": "1.0.0",
    "autoload": {"files": ["functions.php"]}
}
Enter fullscreen mode Exit fullscreen mode

packages/helpers/functions.php:

<?php

declare(strict_types=1);

namespace Acme\Helpers;

function greeting(): string
{
    return 'Application initialized';
}
Enter fullscreen mode Exit fullscreen mode

packages/application/composer.json:

{
    "name": "acme/application",
    "version": "1.0.0",
    "require": {"acme/helpers": "1.0.0"},
    "autoload": {"files": ["bootstrap.php"]}
}
Enter fullscreen mode Exit fullscreen mode

packages/application/bootstrap.php:

<?php

declare(strict_types=1);

echo \Acme\Helpers\greeting(), PHP_EOL;
Enter fullscreen mode Exit fullscreen mode

The reproduction script reads the local package manifests, extracts their declared dependencies and autoload files, and selects one of two ordering strategies. Unlike a hard-coded inclusion sequence, this allows the dependency-aware order to be derived directly from package metadata. The experiment operates on a predefined package collection without performing version resolution or package installation. The graph strategy uses the dependencyOrder() function defined in order.php, presented later in the article.

reproduce.php:

<?php

declare(strict_types=1);

require __DIR__ . '/order.php';

$mode = $argv[1] ?? '';

if (!in_array($mode, ['lexical', 'graph'], true)) {
    fwrite(STDERR, "Usage: php reproduce.php lexical|graph\n");
    exit(2);
}

$requires = [];
$files = [];

foreach (glob(__DIR__ . '/packages/*/composer.json') as $manifestPath) {
    $manifest = json_decode(file_get_contents($manifestPath), true, 512, JSON_THROW_ON_ERROR);
    $name = $manifest['name'];
    $requires[$name] = array_keys($manifest['require'] ?? []);
    $files[$name] = array_map(
        static fn (string $file): string => dirname($manifestPath) . '/' . $file,
        $manifest['autoload']['files'] ?? [],
    );
}

if ($mode === 'lexical') {
    $order = array_keys($requires);
    sort($order, SORT_STRING);
} else {
    $order = dependencyOrder($requires);
}

echo 'Order: ', implode(' -> ', $order), PHP_EOL;

foreach ($order as $name) {
    foreach ($files[$name] as $file) {
        require $file;
    }
}
Enter fullscreen mode Exit fullscreen mode

Before running the following commands, save the reproduction files, including order.php presented later in the article, and execute the commands from the project root. I executed both strategies in separate PHP processes on Windows using PHP 8.4.24, without invoking Composer. The first execution uses alphabetical ordering:

php reproduce.php lexical
Enter fullscreen mode Exit fullscreen mode

Output (local paths and stack trace omitted):

Order: acme/application -> acme/helpers
PHP Fatal error: Uncaught Error: Call to undefined function Acme\Helpers\greeting()
Enter fullscreen mode Exit fullscreen mode

The second execution derives the order from the dependency graph:

php reproduce.php graph
Enter fullscreen mode Exit fullscreen mode

Output:

Order: acme/helpers -> acme/application
Application initialized
Enter fullscreen mode Exit fullscreen mode
Ordering Execution sequence Result
Alphabetical application → helpers Undefined function
Dependency-first helpers → application Successful initialization

Both strategies operate on the same package metadata and the same collection of PHP files. The alphabetical strategy attempts to initialize the dependent package before its prerequisite and fails, while the dependency-aware strategy preserves the declared relationship and completes the bootstrap successfully. This experiment isolates the ordering failure without implementing a complete package installer or relying on the behavior of any particular third-party installation tool.

Use Composer as a reference

To compare the experiment with real Composer-generated artifacts, add this root composer.json:

{
    "name": "example/dependency-ordering-reproduction",
    "description": "A local, two-package fixture for files autoload ordering",
    "type": "project",
    "require": {
        "php": "^8.4",
        "acme/application": "1.0.0"
    },
    "repositories": [
        {"packagist.org": false},
        {"type": "path", "url": "packages/*", "options": {"symlink": false}}
    ]
}
Enter fullscreen mode Exit fullscreen mode

Using Composer 2.10.2 with PHP 8.4.24, I resolved and installed both local packages:

composer update --no-interaction --no-scripts --no-plugins
Enter fullscreen mode Exit fullscreen mode

Composer successfully resolved the declared dependency, installed both packages and generated the autoload artifacts. To verify the generated file order and execute the actual autoloader, the reproduction includes a separate verification script.

composer-check.php:

<?php

declare(strict_types=1);

$files = require __DIR__ . '/vendor/composer/autoload_files.php';
$paths = array_map(static fn (string $path): string => str_replace('\\', '/', $path), array_values($files));

$find = static function (string $suffix) use ($paths): int {
    foreach ($paths as $index => $path) {
        if (str_ends_with($path, $suffix)) {
            return $index;
        }
    }

    throw new LogicException("Missing generated entry: $suffix");
};

if ($find('/acme/helpers/functions.php') >= $find('/acme/application/bootstrap.php')) {
    throw new LogicException('Dependency must precede dependent');
}

require __DIR__ . '/vendor/autoload.php';

echo 'Composer ordering verified', PHP_EOL;
Enter fullscreen mode Exit fullscreen mode

Running the verification:

php composer-check.php
Enter fullscreen mode Exit fullscreen mode

Output:

Application initialized
Composer ordering verified
Enter fullscreen mode Exit fullscreen mode

The verification confirms two properties: the generated autoload file map places the dependency before the dependent package, and the actual Composer autoloader initializes the application successfully. Checking both properties is important because inspecting generated metadata alone does not establish that the generated bootstrap is executable.

Determinism and correctness are separate properties

For a package dependency edge, define the ordering invariant as:

A requires B  =>  index(B) < index(A)
Enter fullscreen mode Exit fullscreen mode

For an acyclic resolved graph, this is a topological-ordering problem. There may be multiple valid orders, and determinism selects a reproducible one without removing the underlying invariant. One way to implement that selection is Kahn's algorithm with a deterministic tie-breaker:

  1. Count unresolved dependencies for each package.
  2. Collect packages that have no remaining prerequisites.
  3. Select the lexically smallest eligible package.
  4. Emit it, decrement the remaining dependency counts of its dependents, and repeat.
  5. If unprocessed packages remain but none are eligible, reject the graph under an acyclic-graph policy.

The significant property of this algorithm is that the next package in the output sequence is selected lexically from the currently eligible packages. The following educational implementation operates on a predefined dependency graph and is used by the reproduction script.

order.php:

<?php

declare(strict_types=1);

/**
 * Educational DAG sorter, not a Composer PackageSorter implementation.
 *
 * @param array<string, list<string>> $requires Resolved package dependencies.
 * @return list<string>
 */
function dependencyOrder(array $requires): array
{
    $remaining = [];
    $dependents = [];

    foreach ($requires as $name => $dependencies) {
        $dependencies = array_unique($dependencies);
        $remaining[$name] = count($dependencies);

        foreach ($dependencies as $dependency) {
            if (!array_key_exists($dependency, $requires)) {
                throw new LogicException("Missing dependency: $dependency");
            }

            $dependents[$dependency][] = $name;
        }
    }

    $ready = array_keys($remaining, 0, true);
    $order = [];

    while ($ready !== []) {
        sort($ready, SORT_STRING);
        $name = array_shift($ready);
        $order[] = $name;

        foreach ($dependents[$name] ?? [] as $dependent) {
            if (--$remaining[$dependent] === 0) {
                $ready[] = $dependent;
            }
        }
    }

    if (count($order) !== count($requires)) {
        throw new LogicException('Dependency cycle');
    }

    return $order;
}
Enter fullscreen mode Exit fullscreen mode

For the reproduction:

$order = dependencyOrder([
    'acme/application' => ['acme/helpers'],
    'acme/helpers' => [],
]);

// ['acme/helpers', 'acme/application']
Enter fullscreen mode Exit fullscreen mode

The dependency relationship constrains the sequence first, while string ordering resolves ambiguity between eligible packages. To verify this behavior beyond the two-package example, the following script checks transitive dependencies, input-order independence, deterministic tie-breaking, duplicate dependency edges, empty graphs, missing dependencies and cycles.

checks.php:

<?php

declare(strict_types=1);

require __DIR__ . '/order.php';

function expectOrder(array $requires, array $expected): void
{
    if (dependencyOrder($requires) !== $expected) {
        throw new LogicException('Unexpected dependency order');
    }
}

function expectFailure(array $requires, string $message): void
{
    try {
        dependencyOrder($requires);
    } catch (LogicException $exception) {
        if ($exception->getMessage() === $message) {
            return;
        }

        throw $exception;
    }

    throw new LogicException('Expected graph rejection');
}

$graph = [
    'acme/application' => ['acme/bridge'],
    'acme/bridge' => ['acme/helpers'],
    'acme/helpers' => [],
    'acme/extra' => [],
];

$expected = ['acme/extra', 'acme/helpers', 'acme/bridge', 'acme/application'];

expectOrder($graph, $expected);
expectOrder(array_reverse($graph, true), $expected);
expectOrder(['a' => ['z', 'z'], 'z' => []], ['z', 'a']);
expectOrder([], []);
expectFailure(['a' => ['missing']], 'Missing dependency: missing');
expectFailure(['a' => ['b'], 'b' => ['a']], 'Dependency cycle');

echo 'Graph checks passed', PHP_EOL;
Enter fullscreen mode Exit fullscreen mode

Running the checks:

php checks.php
Enter fullscreen mode Exit fullscreen mode

Output:

Graph checks passed
Enter fullscreen mode Exit fullscreen mode

These checks verify both valid ordering behavior and the rejection of invalid dependency graphs. Reversing the input arrangement preserves the expected sequence, while missing dependencies and dependency cycles are explicitly rejected.

This implementation is intentionally limited to resolved dependency graphs and is not a replacement for Composer's PackageSorter. Composer has its own dependency-weight policy, package semantics and root-package handling. A compatible installer must additionally account for virtual packages, replacements, platform requirements, development dependencies and Composer's behavior on cyclic graphs. Producing a valid deterministic topological order for an acyclic graph is therefore not sufficient to establish full Composer compatibility.

The same distinction in framework composition

The same distinction between canonical ordering and dependency-aware execution exists in Coretsia, the modular PHP framework I am developing. Coretsia relies on Composer for package installation, while its kernel resolves enabled framework modules and uses the resolved module plan to build application artifacts and compile the container graph. These responsibilities operate at different architectural boundaries, but share the requirement to preserve dependency semantics.

Coretsia's module dependency graph is distinct from Composer's package dependency graph. Framework module dependencies are declared through extra.coretsia.requires metadata and expressed in terms of module identifiers rather than Composer package names. Within the resolved ModulePlan, the enabled() and excluded() collections are represented as canonical, sorted lists of unique module identifiers, while topologicalOrder() preserves the dependency-first sequence without alphabetical re-sorting.

The current implementation distributes these responsibilities across dedicated components:

Component Responsibility
ModuleGraphResolver Expands the required dependency closure and handles missing dependencies, exclusions and conflicts before topological ordering.
TopologicalSorter Computes dependency-first order for enabled modules and detects dependency cycles.
ModulePlan Stores canonical enabled and excluded module sets separately from the resolved topological order, preserving the latter without alphabetical re-sorting.
ContainerProviderPlanResolver Builds the provider plan in topological module order, preserving provider declaration order within each module.
RuntimeContainerGraphCompiler Invokes container definition providers in the resolved provider order, merges their definitions and compiles the container graph.
ModuleManifestBuilder Builds the module-manifest@1 artifact using the canonical ModulePlan payload.
ModulePlanArtifactHydrator Hydrates the module plan, validates its graph semantics and rejects an artifact whose topological order differs from the recomputed canonical order.

The kernel's TopologicalSorter follows the same general topological-ordering principle as the educational algorithm presented earlier, but operates on enabled ModulePlanEntry instances rather than Composer package manifests. It delegates deterministic string ordering to Foundation's DeterministicOrder, which uses byte-order comparison through strcmp() when priorities are equal. All module identifiers receive equal priority for this operation, so the next module is selected from the currently eligible identifiers in ascending byte order.

Unlike the educational implementation, Coretsia separates missing dependency classification from topological sorting. ModuleGraphResolver expands the required dependency closure and handles missing or excluded dependencies and enabled-module conflicts before invoking the sorter. TopologicalSorter considers only the enabled module graph, detects cycles and preserves dependency precedence without re-sorting the resulting sequence alphabetically.

Evidence from the Coretsia test suite

The distinction is explicitly covered by TopologicalSorterDeterministicOrderTest. One of its synthetic test graphs makes core.kernel depend on platform.cli, forcing platform.cli to precede core.kernel even though its identifier sorts after it alphabetically. These relationships belong to the test fixture and do not represent the production dependency graph of Coretsia. The test asserts the following topological order:

core.foundation
platform.cli
core.kernel
platform.http
platform.routing
Enter fullscreen mode Exit fullscreen mode

Additional tests compare the resulting order across different input arrangements and available collation locales, verify that provider planning follows the resolved module order, and ensure that providers retain their declared order within each module. The relevant tests include:

  • TopologicalSorterDeterministicOrderTest
  • ContainerProviderPlanUsesTopologicalModuleOrderTest
  • ContainerProviderPlanPreservesDeclaredProviderOrderTest
  • RuntimeContainerGraphCompilerUsesProviderPlanTest
  • ModulePlanArtifactHydratorContractTest

The provider-order contract has observable consequences beyond ordering metadata. RuntimeContainerGraphCompilerUsesProviderPlanTest verifies that reversing the declared provider sequence changes which implementation is selected for the ClockInterface alias in the compiled container graph. ModulePlanArtifactHydratorContractTest independently verifies that invalid topological ordering and cyclic dependency graphs are rejected.

The Kernel implementation and its tests are located under packages/core/kernel/, while the shared DeterministicOrder primitive belongs to packages/core/foundation/. The module graph semantics are documented in docs/adr/ADR-0025-kernel-conflicts-exclusion-policy.md. These components address framework module composition and container compilation, rather than Composer autoload generation. The connection between these systems is a shared engineering invariant: deterministic representation must never override semantic dependency order.

What I would test in package tooling

If I were reviewing a new autoload generator, I would want at least these tests:

  • A dependency whose name sorts after the dependent must still load first.
  • A transitive relationship must survive even when an intermediate package has no autoload.files entries.
  • Different permutations of the same resolved input must produce the same canonical output.
  • File declaration order within a package and root-package precedence must be preserved.
  • The generated eager-file sequence, including the static autoload representation, must agree with the chosen compatibility policy.
  • The generated vendor/autoload.php must actually run in a fresh PHP process; comparing sets or checksums is not enough.

For a Composer-compatible tool, I would add differential tests: generate the bootstrap from the same lock file using Composer and the alternative installer, compare ordered file sequences and execute both autoloaders in isolated processes. That moves the tests from internal consistency to observable compatibility.

Conclusion

Alphabetical ordering is useful for canonical sets and deterministic representation, particularly when an explicit string comparator makes the result independent of input permutations. However, it cannot replace a dependency graph when execution order is part of the contract. A generated artifact can be reproducible and still be wrong if its ordering violates the relationships required by its consumers.

The principle I follow in tooling and framework design is simple: preserve semantic constraints first; make the remaining freedom deterministic second. This applies equally to generated autoload artifacts, module composition plans, service provider sequences and other ordered initialization processes.

If you maintain a PHP package manager, Composer plugin, framework kernel or modular application, how do you verify that your generated artifacts preserve their semantic order? I would be interested in approaches and counterexamples, especially where a valid topological order is not sufficient to match a reference implementation.

References

Disclosure: AI was used to help draft this article and prepare the example.

Top comments (0)