Topsort Laravel Package

Getting Started

Minimal Setup

1. Installation:

   composer require marcj/topsort
   

   Add to composer.json under require or require-dev depending on use case.

2. First Use Case: Resolve dependencies for a simple service loader or package autoloader.

   use MarcJ\TopSort\StringSort;
   
   $sorter = new StringSort();
   $sorter->add('Database', ['Logger']);
   $sorter->add('Logger');
   
   $sorted = $sorter->sort(); // ['Logger', 'Database']
   

3. Where to Look First:

   • StringSort for basic dependency resolution (fastest implementation).
   • GroupedStringSort for grouping dependencies by type (e.g., database connections, services).
   • ArraySort if you need array-based dependency lists (slower but familiar syntax).

Implementation Patterns

Dependency Injection Container Integration

Use StringSort to resolve service dependencies in a custom DI container:

$sorter = new StringSort();
$sorter->add('UserService', ['Database', 'Cache']);
$sorter->add('Database');
$sorter->add('Cache');

$services = $sorter->sort();
foreach ($services as $service) {
    $container->bind($service, fn() => new $service());
}

Laravel Service Providers

Leverage in register() to load providers in dependency order:

public function register()
{
    $sorter = new StringSort();
    $sorter->add('App\Providers\AuthServiceProvider', ['Database']);
    $sorter->add('App\Providers\DatabaseServiceProvider');

    foreach ($sorter->sort() as $provider) {
        $this->app->register($provider);
    }
}

Dynamic Dependency Resolution

For runtime dependency checks (e.g., plugin systems):

$sorter = new GroupedStringSort('type');
$sorter->add('Plugin.A', ['Plugin.B'], 'plugin');
$sorter->add('Plugin.B', [], 'plugin');

$plugins = $sorter->sort();
foreach ($plugins as $plugin) {
    $this->loadPlugin($plugin);
}

Caching Sorted Results

Cache the sorted output for performance-critical paths:

$sorted = Cache::remember('dependency_order', 60, function () {
    $sorter = new StringSort();
    // ... add dependencies ...
    return $sorter->sort();
});

Gotchas and Tips

Performance Caveats

• StringSort vs ArraySort: StringSort is 20x faster but requires string keys. Use ArraySort only if you need array-based dependencies.

  // Slow (but familiar)
  $sorter = new ArraySort();
  $sorter->add(['id' => 1, 'deps' => [2]]);
  
  // Fast (recommended)
  $sorter = new StringSort();
  $sorter->add('item1', ['item2']);
  

Circular Dependency Detection

• No built-in cycle detection: The package assumes valid DAGs (Directed Acyclic Graphs). Add validation:

  try {
      $sorted = $sorter->sort();
  } catch (\RuntimeException $e) {
      Log::error('Circular dependency detected: ' . $e->getMessage());
      throw new \RuntimeException('Dependency cycle found!');
  }
  

Grouped Sorting Quirks

• Grouping by type: GroupedStringSort requires a group key (e.g., 'type'). Misconfiguration causes silent failures:

  // Correct: Groups by 'type'
  $sorter = new GroupedStringSort('type');
  $sorter->add('Plugin.A', ['Plugin.B'], 'plugin');
  
  // Incorrect: No grouping applied
  $sorter = new GroupedStringSort(); // Throws exception
  

Laravel-Specific Tips

• Service Binding Order: Use StringSort in a macro or helper to enforce order:

  if (!class_exists('App\Helpers\DependencySorter')) {
      class DependencySorter {
          public static function sort(array $dependencies): array
          {
              $sorter = new StringSort();
              foreach ($dependencies as $service => $deps) {
                  $sorter->add($service, $deps);
              }
              return $sorter->sort();
          }
      }
  }
  

• Event Listeners: Resolve listener priorities dynamically:

  $sorter = new StringSort();
  $sorter->add('App\Listeners\LogEvent', ['AuthenticateUser']);
  $sorter->add('App\Listeners\AuthenticateUser');
  
  $listeners = $sorter->sort();
  foreach ($listeners as $listener) {
      $this->listenFor($listener);
  }
  

Debugging

• Dry Runs: Test with ->debug() to visualize the graph:

  $sorter->debug(); // Outputs dependency tree to CLI
  

• Edge Cases: Empty dependencies or isolated nodes may cause unexpected ordering. Explicitly add all nodes:

  $sorter->add('IsolatedNode'); // Ensures it appears in the result