README

一个用于安排依赖任务执行的计划库。

目标是能够构建一个依赖实体网络，例如任务 ID，然后可以按正确的执行顺序排序。这意味着如果任务 B 依赖于任务 A，那么在排序顺序中，任务 A 会出现在任务 B 之前。

目录

• 需求
• 安装
• 用法
• 工作原理
• 测试
• 变更日志
• 许可

需求

PHP 7.1+

安装

$ composer require pwm/deepend

用法

以下是创建 4 个任务之间依赖关系的简单示例

// Create an empty store
$deepEnd = new DeepEnd();

// Add some entries, in our example they are the task ids
$deepEnd->add('t1');
$deepEnd->add('t2');
$deepEnd->add('t3');
$deepEnd->add('t4');

// Specify dependencies between them. A pointing to B, ie. an arrow from A to B,
// means that B depends on A therefore A has to happen before B can happen.
$deepEnd->draw((new Arrow)->from('t1')->to('t2'));
$deepEnd->draw((new Arrow)->from('t1')->to('t3'));
$deepEnd->draw((new Arrow)->from('t2')->to('t4'));

// Get a valid execution order
$order = $deepEnd->sort(); // $order = ['t1', 't3', 't2', 't4']

您还可以将数据（包括函数和对象）添加到您的任务中以供以后使用。在这种情况下，请使用 sortToMap() 方法，该方法返回一个以 ID 为键，添加的数据为值的映射。使用上面 4 个任务的示例，我们可以做以下操作

function taskRunner(string $taskId, string $taskData): void
{
    echo sprintf('Running task %s with data %s ... done.', $taskId, $taskData) . PHP_EOL;
}

$deepEnd = new DeepEnd();

$deepEnd->add('t1', 't1-data');
$deepEnd->add('t2', 't2-data');
$deepEnd->add('t3', 't3-data');
$deepEnd->add('t4', 't4-data');

$deepEnd->draw((new Arrow)->from('t1')->to('t2'));
$deepEnd->draw((new Arrow)->from('t1')->to('t3'));
$deepEnd->draw((new Arrow)->from('t2')->to('t4'));

$orderedTasks = $deepEnd->sortToMap();
foreach ($orderedTasks as $taskId => $taskData) {
    taskRunner($taskId, $taskData);
}

// Running task t1 with data t1-data ... done.
// Running task t3 with data t3-data ... done.
// Running task t2 with data t2-data ... done.
// Running task t4 with data t4-data ... done.

工作原理

当通过 add() 方法添加条目并通过 draw() 方法添加箭头时，您实际上正在构建一个图，更具体地说是一个有向无环图 (DAG)，其中节点通过 add() 添加，边/箭头通过 draw() 添加。

每次您想从节点 A 到节点 B 绘制新箭头时，DeepEnd 都会检查它是否会创建循环。如果答案是肯定的，它将以异常的形式告诉您。这样做的方式是，在绘制箭头之前，DeepEnd 会检查 A 是否可以从 B 达到，即是否存在从 B 到 A 的路径。如果有，那么从 A 到 B 的箭头会导致循环，因为您已经可以从 B 到 A，然后通过新箭头回到 B。

一旦构建了您的图，就可以使用 sort() 方法对您的 DAG 执行所谓的拓扑排序。这是通过深度优先搜索实现的，其中 DeepEnd 在访问节点并离开时逐步索引节点。这被称为后序遍历。完成后，它将按逆序对节点进行排序，从具有最高后序索引的节点开始。这导致了一个顺序，其中依赖于其他节点的节点位于其依赖项之后，这是我们想要的顺序。

测试

$ vendor/bin/phpunit
$ composer phpcs
$ composer phpstan

变更日志

点击此处

许可

MIT