Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
<?php
// Nodes.
abstract class Node implements Visitable {}
class Number extends Node {
public function __construct(public float $value){}
public function accept(Visitor $visitor) {
return $visitor->visitNumber($this);
}
}
class Add extends Node {
public function __construct(public Node $left, public Node $right){}
public function accept(Visitor $visitor) {
return $visitor->visitAdd($this);
}
}
class Substract extends Node {
public function __construct(public Node $left, public Node $right){}
public function accept(Visitor $visitor) {
return $visitor->visitSubstract($this);
}
}
class Minus extends Node {
public function __construct(public Node $node){}
public function accept(Visitor $visitor) {
return $visitor->visitMinus($this);
}
}
class Assign extends Node {
public function __construct(public string $variable, public Node $node){}
public function accept(Visitor $visitor) {
return $visitor->visitAssign($this);
}
}
class Get extends Node {
public function __construct(public string $variable){}
public function accept(Visitor $visitor) {
return $visitor->visitGet($this);
}
}
class Calculator extends Node {
public function __construct(public array $statements){}
public function accept(Visitor $visitor) {
return $visitor->visitCalculator($this);
}
}
// Visitor contracts.
interface Visitable {
public function accept(Visitor $visitor);
}
abstract class Visitor {
abstract public function visitNumber(Number $node);
abstract public function visitAdd(Add $node);
abstract public function visitSubstract(Substract $node);
abstract public function visitMinus(Minus $node);
abstract public function visitAssign(Assign $node);
abstract public function visitGet(Get $node);
abstract public function visitCalculator(Calculator $node);
}
// Evaluating through a visitor.
class EvaluateVisitor extends Visitor
{
protected array $assignments;
public function __construct(array $preDefinedAssignments = [])
{
$this->assignments = $preDefinedAssignments;
}
public function visitNumber(Number $node)
{
return $node->value;
}
public function visitAdd(Add $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return $leftValue + $rightValue;
}
public function visitSubstract(Substract $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return $leftValue - $rightValue;
}
public function visitMinus(Minus $node)
{
$childValue = $node->node->accept($this);
return - $childValue;
}
public function visitAssign(Assign $node)
{
// Evaluate the child node.
$childValue = $node->node->accept($this);
// Store its value.
$this->assignments[$node->variable] = $childValue;
// Use the child value as the "Assign" value too.
return $childValue;
}
public function visitGet(Get $node)
{
if (! isset($this->assignments[$node->variable])) {
throw new \RuntimeException("Variable [{$node->variable}] was not assigned.");
}
return $this->assignments[$node->variable];
}
public function visitCalculator(Calculator $node)
{
if (empty($node->statements)) {
throw new \RuntimeException('The Calculator node requires at least one statement.');
}
$lastStatementValue = null;
foreach ($node->statements as $statement) {
$lastStatementValue = $statement->accept($this);
}
return $lastStatementValue;
}
}
// Calculator example.
$firstStatement = new Assign('foo', new Add(new Number(1), new Number(5)));
$secondStatement = new Substract(new Number(100), new Minus(new Get('foo')));
$calculator = new Calculator([$firstStatement, $secondStatement]);
// Evaluation.
$evaluateVisitor = new EvaluateVisitor();
echo $firstStatement->accept($evaluateVisitor) . "\n"; // Returns: 6
// echo $secondStatement->accept($evaluateVisitor) . "\n"; // Throws: Variable [foo] was not assigned.
echo $calculator->accept($evaluateVisitor) . "\n"; // Returns: 106
// Evaluation with predefined assignments.
$thirdStatement = new Add(new Get('answerToLifeTheUniverseAndEverything'), new Number(8));
$evaluateVisitorWithPredefinedAssignments = new EvaluateVisitor([
'answerToLifeTheUniverseAndEverything' => 42,
]);
echo $thirdStatement->accept($evaluateVisitorWithPredefinedAssignments) . "\n"; // Returns: 50
// Printing through a visitor.
class PrintVisitor extends Visitor
{
public function visitNumber(Number $node)
{
return $node->value;
}
public function visitAdd(Add $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return "$leftValue + $rightValue";
}
public function visitSubstract(Substract $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return "$leftValue - $rightValue";
}
public function visitMinus(Minus $node)
{
$childValue = $node->node->accept($this);
return "- $childValue";
}
public function visitAssign(Assign $node)
{
$childValue = $node->node->accept($this);
return "\${$node->variable} = $childValue";
}
public function visitGet(Get $node)
{
return "\${$node->variable}";
}
public function visitCalculator(Calculator $node)
{
$print = '';
foreach ($node->statements as $statement) {
$print .= $statement->accept($this) . ";\n";
}
return $print;
}
}
$printVisitor = new PrintVisitor();
echo $calculator->accept($printVisitor);
// Returns:
// $foo = 1 + 5;
// 100 - - $foo;
// Chaining visitors.
class RemoveDoubleNegationVisitor extends Visitor
{
protected bool $negative = false;
public function visitNumber(Number $node)
{
// Take both the negative boolean and the value into account
// So that we ensure the number's value is kept positive.
$negativeValue = ($this->negative xor ($node->value < 0));
$newNode = new Number(abs($node->value));
return $negativeValue ? new Minus($newNode) : $newNode;
}
public function visitAdd(Add $node)
{
// Give the same negative values to both branches
// And they will sort themselves out.
$negativeAddition = $this->negative;
$newLeft = $node->left->accept($this);
$this->negative = $negativeAddition;
$newRight = $node->right->accept($this);
// Bonus: Since we now know the right branch has no double negatives
// we can make an optimisation and replace "A + - B" with "A - B".
if ($newRight instanceof Minus) {
return new Substract($newLeft, $newRight->node);
}
return new Add($newLeft, $newRight);
}
public function visitSubstract(Substract $node)
{
// Since "A - B" is equivalent to "A + (-B)", let's
// transform our node and delegate to the `visitAdd` method.
$addition = new Add($node->left, new Minus($node->right));
return $addition->accept($this);
}
public function visitMinus(Minus $node)
{
// We inverse the negative boolean and let
// the child handle the change of sign.
$this->negative = ! $this->negative;
$newChild = $node->node->accept($this);
return $newChild;
}
public function visitAssign(Assign $node)
{
// Keep track of the current negative boolean.
$negativeAssignment = $this->negative;
// Reset it for the descedants.
$this->negative = false;
$newChild = $node->node->accept($this);
$newAssignment = new Assign($node->variable, $newChild);
// If the assignement was negative, wrap it in a Minus node
// since the Minus nodes auto-delete themselves in this visitor.
return $negativeAssignment ? new Minus($newAssignment) : $newAssignment;
}
public function visitGet(Get $node)
{
$newNode = new Get($node->variable);
return $this->negative ? new Minus($newNode) : $newNode;
}
public function visitCalculator(Calculator $node)
{
$newStatements = [];
foreach ($node->statements as $statement) {
// We reset the negative boolean for each statement.
$this->negative = false;
$newStatements[] = $statement->accept($this);
}
return new Calculator($newStatements);
}
}
$calculatorWithoutDoubleNegative = $calculator->accept(new RemoveDoubleNegationVisitor());
echo $calculatorWithoutDoubleNegative->accept(new PrintVisitor());
// Returns:
// $foo = 1 + 5;
// 100 + $foo;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment