Skip to content

Instantly share code, notes, and snippets.

@ohader
Created November 24, 2022 18:04
Show Gist options
  • Save ohader/bc72d64a5152fa99b33b47d9482b9e9b to your computer and use it in GitHub Desktop.
Save ohader/bc72d64a5152fa99b33b47d9482b9e9b to your computer and use it in GitHub Desktop.
Lupine: Detect endless loops
<?php
class Node
{
/**
* @var list<Node>
*/
public array $prev = [];
/**
* @var list<Node>
*/
public array $next = [];
public string $name;
public function __construct(string $name)
{
$this->name = $name;
}
public function __toString(): string
{
return sprintf(
'%s->{%s}',
$this->name,
implode(',', array_map(static fn (Node $node) => $node->name, $this->next))
);
}
public function findInAncestors(Node $node): ?Node
{
foreach ($this->prev as $prev) {
if ($prev === $node) {
return $this;
}
$ancestor = $prev->findInAncestors($node);
if ($ancestor !== null) {
return $ancestor;
}
}
return null;
}
}
class Collection
{
/**
* @var array<string, Node>
*/
public array $items = [];
public function add(string $currentName, string $nextName): void
{
if (!isset($this->items[$currentName])) {
$this->items[$currentName] = new Node($currentName);
}
$current = $this->items[$currentName];
if (!isset($this->items[$nextName])) {
$this->items[$nextName] = new Node($nextName);
}
$next = $this->items[$nextName];
if (!in_array($next, $current->next,true)) {
$current->next[] = $next;
}
if ($current->findInAncestors($next)) {
throw new \RuntimeException(
sprintf('Recursion when adding %s to %s', $next, $current)
);
}
if (!in_array($current, $next->prev, true)) {
$next->prev[] = $current;
}
}
public function getEntryNodes(): array
{
return array_filter($this->items, static fn (Node $item) => $item->prev === []);
}
public function getLeafNodes(): array
{
return array_filter($this->items, static fn (Node $item) => $item->next === []);
}
}
// will later show error `Recursion when adding B->{C,222} to E->{B}`
$text =<<< 'EOT'
A->B, B->C, C->111, B->222, 111->D, D->E, D->333, E->B
EOT;
$collection = new Collection();
$items = explode(',', $text);
$items = array_map('trim', $items);
try {
foreach ($items as $item) {
list($currentName, $nextName) = explode('->', $item, 2);
$collection->add($currentName, $nextName);
}
} catch (\Exception $e) {
echo $e->getMessage() . PHP_EOL;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment