Binary Search Trees in PHP

Full credit to googleguy, who can be found on Freenode IRC channel ##php (sometimes).

Imagine you’re a phone company and you want to implement an automated system on your website for assigning phone numbers for your customers. There are two use cases. One, is that the customer can ask if a specific number is available. The other, is that the customer can ask for any random number that’s available. What data structure would you use to efficiently store and search these phone numbers? Keep in mind that you could potentially have billions of these phone numbers (1011 if we include international numbers).

If you use an Array, access is O(1) so it seems like a good idea at first, but that’s only in cases where you know the index of the value you want to access. Finding that index means searching the entire array, which is really O(n). If you use a Hash Table, the cost of search is O(1) so it seems like a better idea, but the cost of deletion and insertion can be O(n) in the worst case scenario (where you have 100% collision).

The best answer is to use a BST or Binary Search Tree, because they have average O(log n) for search, insertion, and deletion. That is assuming it’s a self-balancing tree implementation.


If you’re not at all familiar with Binary Search Trees or Binary Trees in general, let me give you a simple analogy to try and grasp this particular concept of search in computer science.

Let’s say a friend of yours is stuck on the road due to car trouble. Like a good friend you go to pick them up. You know they are stuck at a fork on this road and you arrive at a fork. At the fork there is a sign with a number on it. The number is 5 and your friend sees a sign with the number 16. You know that if you go left, you will only find numbers less than 5 and if you go right you will find numbers greater than 5. So you go right and arrive at another fork. This time you see a sign with the number 11. What do you do?

Knowing how to get to your friend, on this road, is no different than knowing how to search a (BST). You must always know two things, and always be able to make one of two simple choices. Is this number more than or less than the number I’m searching for? Do I go left, or do I go right at the fork?

Learning Opportunity

A BST is a data structure made up of nodes (the forks in our road analogy) which have left and right branches that, may or may not, each have an attached node (i.e there could be a dead end). A node attached to the left branch is less than the current node. A node attached to the right branch is greater than the current node. This always holds true no matter which node you’re currently looking at. The entirety of the structure makes up what looks like a tree, given all these nodes connected by branches. The fact that there can only be two branches on each node is what makes it binary. In the context of search these distinct properties are what make a BST very efficient.

The idea here is that you can always discard one-half of the tree with every iteration. This makes it possible to search for any value in the tree logarithmically, i.e. O(log n). Consequently, the cost of insertion or deletion to and from the tree are the same.

So say we have 9 random integers in a BST and we want to find out if the integer 16 is one of them. You always start at the root node of the tree and compare the given value to the search value. If the node’s value is greater than the search value we move to the node in the left branch. If the node’s value is less than the search value we move to the node in the right branch. Repeat this step until you find the value or reach the end (a null branch).

In PHP, we know that arrays are really just ordered hashmaps, and the cost of search in a hashmap is O(1), which makes it much faster than O(log n). However, BSTs have other properties that make them more desirable than a hashmap in many use cases. For example, finding the min or max value in a hashmap is O(n) whereas in a BST it is O(log n). In a real vector, or contiguous block, the values would need to be sorted before search can be O(1), but Quicksort requires O(n log n) making it very inefficient for insertion and deletion, because you have to resort each time you insert or delete.

Implementation in PHP

The best way to learn is to just roll up your sleeves and do it, right? So let’s implement a BST in PHP and learn something!

We already know that a binary search tree is made up of nodes. The properties that best describe these nodes is that they have a value, a left branch, and a right branch. Each branch can also contain a node. So let’s write up the node class first since it’s simply described by a set of properties and doesn’t have any real behavior (i.e. methods).

class Node
{
    public $value, $left, $right;

    public function __construct($value)
    {
        $this->value = $value;
    }
}

Simple enough. Now that we have a way to create a node, we’ll need the actual binary search tree implementation to be able to create the tree. So far we understand that a BST has a root node, so that will be one of the properties that describe this object.

The BST also has a couple of behaviors, that will make up the methods of this class. We’ll start by implementing the simplest of these behaviors, which is search.

class BST
{
    public $root;

    public function __construct($value = null)
    {
        if ($value !== null) {
            $this->root = new Node($value);
        }
    }

    public function search($value)
    {
        $node = $this->root;

        while($node) {
            if ($value > $node->value) {
                $node = $node->right;
            } elseif ($value < $node->value) {
                $node = $node->left;
            } else {
                break;
            }
        }

        return $node;
    }
}

As you can see search is quite simple. We merely compare the search value to the current node (starting at the root node). If it’s greater than the value of the current node, we go to the node in the right branch. If it’s less than the value of the current node we go to the node in the left branch. If they’re equal we return the current node. This repeats in the loop until we reach a branch that is null. This tells us that the value does not exist in the tree.

Insertion

Now let’s implement the insert functionality of the tree in order to make it really useful. This is very similar to our search behavior, with one difference. We’re looking for a null branch to insert the value. So ideally, our insert function should look fairly similar to our search function with the minor difference being that we will attach a new node to the null branch reached at the end of our loop.

public function insert($value)
{
    $node = $this->root;
    if (!$node) {
        return $this->root = new Node($value);
    }

    while($node) {
        if ($value > $node->value) {
            if ($node->right) {
                $node = $node->right;
            } else {
                $node = $node->right = new Node($value);
                break;
            }
        } elseif ($value < $node->value) {
            if ($node->left) {
                $node = $node->left;
            } else {
                $node = $node->left = new Node($value);
                break;
            }
        } else {
            break;
        }
    }
    return $node;
}

OK, so what’s going on here? Every time we go right or left we check to see if the branch is null before proceeding and based on that information we make a decision to either attach a new node to the branch and break from the loop, or move to the next node. So insertion happens just before the point where we would normally end up with null and break from the loop, but since we can’t attach a node to null, we attach just before the $node is assigned null, and then break.

Min

Before we can learn about deleting nodes from the tree we must first grasp an important concept of binary search trees, which is how to find their minimum and maximum values. Remember that every time you go left in a BST you are guaranteed to get a value smaller than its parent. So if we start at the root node, and keep going left until we arrive at a node with a null left branch, we should have reached the smallest value in the tree.

So our implementation of min in the BST class should look something like this.

public function min()
{
    if (!$this->root) {
        throw new Exception('Tree root is empty!');
    }

    $node = $this->root;
    return $node->min();
}

Notice that BST::min() will only call on root->min() so we must implement the actual functionality in our Node class. This makes sense since we will likely find it useful to find the minimum value from a specific branch in the tree and not just from the root.

So our implementation of min in the Node class should look something like this.

public function min()
{
    $node = $this;
    while ($node->left) {
        if (!$node->left) {
            break;
        }
        $node = $node->left;
    }
    return $node;
}

Notice that if you start at the root and keep going left in our example tree illustrated earlier, you will ultimately reach the smallest value in the tree, but consequently, if you were to start at any other node in the tree and keep going left until you arrive at a null left branch, you will have the smallest value in that branch.

Max

You can probably guess how the implementation for max will work in our BST class…

public function max()
{
    if (!$this->root) {
        throw new Exception('Tree root is empty!');
    }

    $node = $this->root;
    return $node->max();
}

In our Node class the same concept applies, but we’re going right instead of left.

public function max()
{
    $node = $this;
    while ($node->right) {
        if (!$node->right) {
            break;
        }
        $node = $node->right;
    }
    return $node;
}

Deletion

Great, now we have a way to insert nodes into the tree and a way to search the tree. Next, we need to have a way to delete nodes from the tree. Deletion is slightly trickier than search and insertion, but that’s OK, because we’re super ninja programmers that can code our way out of any problem, right?

Crickets…

There are three kinds of deletion in a binary search tree we should be aware of, because they’re each handled just a little differently.

  1. Deleting a node that has no children
  2. Deleting a node that has one child node
  3. Deleting a node that has two child nodes

The easiest is the first one with no nodes, obviously. You simply just delete the node by assigning null to its parent branch, which means you must keep track of the parent branch. So in our earlier BST, if we decided to delete the node with the value of 1, its parent node 2, would then have a left branch of null and the node would be removed from the tree.

Now, let’s say we want to delete the node with the value 2, which at this point only has one branch (containing the node with the value 4). It doesn’t actually matter if the child’s branch is right or left. As long as it only has one branch we simply take the node in that branch and attach it to the parent branch of the node we’re about to delete.

Finally, the last case is when we wish to delete a node that has both branches occupied. To do this we must first find the smallest node of its right branch. We can do this using the node’s min method that we implemented earlier.

Now we assign that min value to value of the node we’re trying to delete, which will give us duplicate nodes.

Next we apply a delete operation to the duplicate node.

Now, to make this concept a little easier to implement we can make one small modification to our Node class. By allowing each node to keep track of its parent node, we never need to pass along the parent by keeping track of it from the calling context. This will simplify the last and most complex case of deletion for us quite a bit. It will also make it easier to walk the tree later.

class Node
{
    public $parent, $value, $left, $right;

    public function __construct($value, Node $parent = null)
    {
        $this->value = $value;
        $this->parent = $parent;
    }
}

Now we just need to modify the insert method of our BST class to pass the parent into the Node’s constructor when doing insertion.

What this gives us is a doubly-linked list of nodes. Making it possible for a child node, in the tree, to know about its parent node. This is also a recursive relationship, because the child stores the parent property as the parent node object itself. So, be careful of (recursion there) recursion there.

public function insert($value)
{
    $node = $this->root;
    if (!$node) {
        return $this->root = new Node($value);
    }

    while($node) {
        if ($value > $node->value) {
            if ($node->right) {
                $node = $node->right;
            } else {
                $node = $node->right = new Node($value, $node);
                break;
            }
        } elseif ($value < $node->value) {
            if ($node->left) {
                $node = $node->left;
            } else {
                $node = $node->left = new Node($value, $node);
                break;
            }
        } else {
            break;
        }
    }
    return $node;
}

The root will have a null parent, and that’s fine. So nothing else should change in our implementation. We’re now ready to implement delete in our BST class.

public function delete($value)
{
    $node = $this->search($value);
    if ($node) {
        $node->delete();
    }
}

The delete method in our BST class is rather simple. It just searches for the node we’re trying to delete, and calls the delete method on that Node. The Node should be able to take care of the rest from here.

public function delete()
{
    if ($this->left && $this->right) {
        $min = $this->right->min();
        $this->value = $min->value;
        $min->delete();
    } elseif ($this->right) {
        if ($this->parent->left === $this) {
            $this->parent->left = $this->right;
            $this->right->parent = $this->parent->left;
        } elseif ($this->parent->right === $this) {
            $this->parent->right = $this->right;
            $this->right->parent = $this->parent->right;
        }
        $this->parent = null;
        $this->right   = null;
    } elseif ($this->left) {
        if ($this->parent->left === $this) {
            $this->parent->left = $this->left;
            $this->left->parent = $this->parent->left;
        } elseif ($this->parent->right === $this) {
            $this->parent->right = $this->left;
            $this->left->parent = $this->parent->right;
        }
        $this->parent = null;
        $this->left   = null;
    } else {
        if ($this->parent->right === $this) {
            $this->parent->right = null;
        } elseif ($this->parent->left === $this) {
            $this->parent->left = null;
        }
        $this->parent = null;
    }
}

Our Node::delete(), on the other hand, is not so simple.

The first if condition, in this method, is the number 3 scenario on our list, mentioned earlier. When the node we’re trying to delete has both a left and right branch, we must first find the min of its right branch and set its value to the value of that node. Then we call delete on that node. Notice, once we do that the min node cannot meet the first condition again. It will only fall into one of the other two scenarios—it either has one child or no children at all (because it will never have a left branch).

The animation here, highlights the most complex of deletion cases, where we need to perform a delete on a node that has both left and right branches occupied.

Let’s Take a Walk

Now, we’ll look at how you can walk through the binary search tree and some of the different ways you can do it.

One thing you should note about tree structures like the binary search tree is that they are not linear structures, like vectors, or linked lists. They can not be viewed sequentially. They are actually traversed as graphs, which means there is more than one way to traverse them. However, there must be a systematic way in which you can visit every node in the tree exactly once. Otherwise, the implementation is considered inefficient and potentially defective. Imagine you wanted to print all of the node values in the tree and your method allowed some nodes to be visited more than once. This wouldn’t be very helpful.

There are two conceptual ways in which you can traverse a binary tree. One way is iterative, meaning it works sequentially (one after the other), but requires a little more memory. The other way is to do it recursively, and since a binary tree is by definition is a corecursive structure, that would make sense. Doing it iteratively requires storing or deferring some nodes to memory before traversing them. This is usually accomplished by using a stack or queue data structure. I actually find it easier to implement a walk method on a tree recursively, but that’s just me. Then again, I’m the one writing this so, what do I care how you like to do it?!

Now whether the method of implementation is recursive or iterative, you still have to choose the order of traversal on the tree, which can be either Depth First or Breadth First. Breadth First order is also sometimes referred to as level order, because you visit every node on a particular level of the tree before moving down to the next level.

In Depth First order there are three different algorithms commonly used for traversal.

  1. Pre-order
  2. In-order
  3. Post-order

We’re not going to go through all of these approaches here. In this article, we’re just going to use Depth First In-order traversal, since I find it to make the most sense for demonstration purposes.

Depth First In-order Traversal

First, let’s plot out our chartered course so that I have some high-level view of where we want to go, before we try to get there.

The sequence looks kind of like a roller coaster ride, but this particular aproach will give us the nodes in order.

So the result is all values in ascending order as [1, 2, 4, 5, 7, 11, 16, 23, 34], which is what you’d expect if this was a sorted array, for example.

public function walk(Node $node = null)
{
    if (!$node) {
        $node = $this->root;
    }
    if (!$node) {
        return false;
    }
    if ($node->left) {
        yield from $this->walk($node->left);
    }
    yield $node;
    if ($node->right) {
        yield from $this->walk($node->right);
    }
}

I’ve used a generator implementation, which will only work in PHP 7, but that’s just because it makes the implementation so much simpler. You can accomplish the same thing in PHP 5 by replacing the yield calls with an array assignment, for example, and then using array_reduce to return the actual results back to the caller. You might need a wrapper function for this, but the concept is the same. It’s just so much less code using a generator!

If we ran this code…

// Instantiate a new tree with root node of 5
$bst = new BST(5);

// Insert left branch nodes
$bst->insert(2);
$bst->insert(1);
$bst->insert(4);

// Insert right branch nodes
$bst->insert(11);
$bst->insert(7);
$bst->insert(23);
$bst->insert(16);
$bst->insert(34);

// Walk the tree
$tree = $bst->walk();
foreach($tree as $node) {
    echo "{$node->value}\n";
}

We should get output like this…

1
2
4
5
7
11
16
23
34

Other Real World Applications

So, you’re probably thinking, what on earth would I need a binary tree for, and especially in a language like PHP? And you’re probably very right for thinking that, but don’t confuse what you’ll need it for with why you almost never need to implement a binary tree in practice. In PHP, particularly, the performance gains of binary search are dwarfed by the context-switching overhead of having to implement them as objects (it takes a lot longer to carry out a function call in PHP than it would to do simple pointer dereferencing in a language like C, for example).

It’s very important to know about and understand this data structure in concert with other data structures so that you’re aware of the performance (time and memory) characteristics of each in a given problem. In many cases, you’ll be using tools that implement a btree quite frequently, but will rarely be required to implement one yourself. For example, your Database Management System (DBMS) implements a type of btree commonly referred to as B+ tree. In 3D computer graphics, many games will often implement a kind of btree usually called a Binary Space Parition (BSP), which allows for recursively subdividing a space into convex sets by hyperplanes.

There are many areas where trees or graphs (nodes and edges) are generally useful in a wide array of programming problems. So having a good grasp of BST, is not a bad start!

Final Thoughts

As mentioned in the beginning of this article, only a self-balancing implementation of a BST, such as AVL-tree will accomplish average O(log n) in search, insertion, and deletion, because as you can see by our implementation if I were to simply insert the numbers [1,2,3,4,5] or [5,4,3,2,1] you would have O(n) since the tree would be entirely right or left heavy.

So, as always, I like to leave something up to the imagination. So I’ll leave it to you to play around with the implementation and see if you can figure out how to implement a balance method that will automatically balance the tree.

Advertisements

Setup HATEOAS hal+json API responses

I’m busy setting up HAL on our API (see the spec here http://stateless.co/hal_specification.html), which we’re building in Symfony 3. We have used the FOSRestBundle, and JMS Serialiser to set up the API to begin with, and the incredible Swagger for documenting it.

If you aren’t using Symfony, you can integrate this package yourself:

composer require willdurand/hateoas

And if you do use Symfony, there’s a bundle.

composer require willdurand/hateoas-bundle

Register the bundle in app/AppKernel.php.

// .. in array of bundles
new Bazinga\Bundle\HateoasBundle\BazingaHateoasBundle(),

Self Link

Open your entity, add the use statement,  and edit the class DocBlock:

use Hateoas\Configuration\Annotation as Hateoas;
@Hateoas\Relation("self", href = "expr('/employees/' ~ object.getId())")

This annotation says that the REST link to an employee is /employees/:id.

Collections with pagination links

Here’s a testAction I made in my EmployeeController:

/**
 * @Rest\Post("/employees/test/test")
 *
 * @SWG\Post(
 *     path="/employees/test/test",
 *     description="Fake call for testing purposes",
 *     operationId="test",
 *     produces={"application/hal+json"},
 *     tags={"employees"},
 *     @SWG\Parameter(
 *         name="page",
 *         in="query",
 *         type="integer",
 *         description="the page you want",
 *         required=false,
 *         default=1
 *     ),
 *     @SWG\Parameter(
 *         name="limit",
 *         in="query",
 *         type="integer",
 *         description="the number of results per page",
 *         required=false,
 *         default=1
 *     ),
 *     @SWG\Response(
 *         response=200,
 *         description="Returned when successful",
 *         @SWG\Schema(ref="#/definitions/listEmployee")
 *     ),
 *     @SWG\Response(
 *         response="default",
 *         description="unexpected error",
 *         @SWG\Schema(
 *             ref="#/definitions/ErrorModel"
 *         )
 *     )
 * )
 *
 *
 * @return PaginatedRepresentation
 */
public function testAction(Request $request)
{
    $page = $request->get('page') ?? 1;
    $numPerPage = $request->get('limit') ?? 1;

    $co = new Company();
    $co->setName('KGB Inc.')
       ->setCode(999999.1);
    $employee = new Employee();
    $employee
        ->setCompany($co)
        ->setId(666)
        ->setEmployeeId(999)
        ->setName('Vladimir Putin');

    $collection = new EntityCollection();
    $collection->add($employee);

    $co = new Company();
    $co->setName('MAGA Inc.')
       ->setCode(999999.1);
    $employee = new Employee();
    $employee
        ->setCompany($co)
        ->setId(999)
        ->setEmployeeId(666)
        ->setName('Donald J Trump');

    $collection->add($employee);

    $numPages = ceil (count($collection) / $numPerPage);

    $filter = new CollectionFilter();
    $filter->getPaginationFilter()
        ->setNumPerPage(1)
        ->setPage($page);

    $collection = $filter->filterArrayResults($collection->toArray());

    $halCollection = new CollectionRepresentation(
        $collection,
        'employees',
        'employees'
    );

    $pager = new PaginatedRepresentation(
        $halCollection,
        'test',
        array(),
        $page,
        $numPerPage,
        $numPages
    );

    return $pager;
}

There’s quite a bit here, but let me explain.

The @Rest\Post(“/employees/test/test”) annotation is the FOSRestBundle. When we call thae URL, it ensures we send POST otherwise we get a 405 response.

The @SWG stuff is Swagger documentation annotation, which hopefully should be self explanatory. The only part you might question is the Schema, which you docblock annotate in the entity class itself. See full Swagger docs for that, but here’s our annotation for a single employee:

* @SWG\Definition(
*   definition="singleEmployee",
*   type="object",
*   allOf={
*       @SWG\Schema(
*           @SWG\Property(property="id", type="integer"),
*           @SWG\Property(property="employeeId", type="integer"),
*           @SWG\Property(property="name", type="string"),
*           @SWG\Property(property="firstName", type="string"),
*           @SWG\Property(property="company",type="object", ref="#/definitions/singleCompany"),
*           @SWG\Property(property="functionDescription", type="string"),
*           @SWG\Property(property="nationalRegisterNumber", type="string"),
*       ),
*   }
* )

@return PaginatedRepresentation returns our collection, wrapped in HAL stuff now.

In the method itself, I create two fake employees (Trump & Putin), add them to the EntityCollection, then I run CollectionFilter on it (https://github.com/delboy1978uk/collection-filter, which I made last week as a filter/paginator system for working with full resultsets). So the interesting bit is $halCollection & $pager. We pass our $collection into CollectionRepresentation, and pass that into PaginatedRepresentation.

So now, we go to https://api.yoursite.com/docs, try our endpoint, and you should see…

Screen Shot 2017-10-30 at 4.43.34 PM

Have fun! 😀

Creating custom annotations in Symfony 3

I’m currently building a backend API for a site which requires requests to be signed with an access token header. My problem is, the default @Security annotation feature doesn’t fit with our requirements, because we don’t actually have any users on our site! We actually consume our clients SOAP service, which is where all the important data is stored.

Currently, in a typical controller action, I have the following code:

/**
 *@Rest\Put("/auth/change-password")
 */
public function changePasswordAction(Request $request)
{
 $tokenId = $paramFetcher->get('token');
 $tokenSvc = $this->get('Our\SuperbBundle\Service\TokenService');

 // Check the token exists and is valid
 // throws exception if not found or expired
 $tokenSvc->findToken($tokenId); 
 // actual change password logic here
}

We are going to have several controllers with multiple calls, so we don’t want to add this in every single controller action, so we will create our own custom annotation.

<?php

namespace Our\CustomerZoneBundle\Annotation;

/**
 * Class SecureToken
 * @package Our\CustomerZoneBundle\Annotation
 * @Annotation
 */
class SecureToken
{
}

The next thing we do is create an Annotation listener, which I’ll explain below:

<?php

namespace Our\CustomerZoneBundle\EventListener;

use Doctrine\Common\Annotations\AnnotationReader;
use Doctrine\Common\Util\ClassUtils;
use Our\CustomerZoneBundle\Annotation\SecureToken;
use Our\CustomerZoneBundle\Model\Exception\TokenException;
use Our\CustomerZoneBundle\Service\TokenService;
use ReflectionClass;
use ReflectionObject;
use Symfony\Bundle\FrameworkBundle\Controller\Controller;
use Symfony\Component\HttpFoundation\RequestStack;
use Symfony\Component\HttpFoundation\Response;
use Symfony\Component\HttpKernel\Event\FilterControllerEvent;
use Symfony\Component\HttpKernel\Exception\AccessDeniedHttpException;

class SecureTokenAnnotationListener
{
    /** @var AnnotationReader $reader */
    protected $reader;

    /** @var RequestStack $requestStack */
    protected $requestStack;

    /** @var TokenService $tokenService */
    protected $tokenService;

    /**
     * SecureTokenAnnotationListener constructor.
     * @param AnnotationReader $reader
     * @param RequestStack $stack
     * @param TokenService $tokenService
     */
    public function __construct(AnnotationReader $reader, RequestStack $stack, TokenService $tokenService)
    {
        $this->reader = $reader;
        $this->requestStack = $stack;
        $this->tokenService = $tokenService;
    }

    /**
     * @param FilterControllerEvent $event
     */
    public function onKernelController(FilterControllerEvent $event)
    {
        $controller = $event->getController();
        /*
         * $controller passed can be either a class or a Closure.
         * This is not usual in Symfony2 but it may happen.
         * If it is a class, it comes in array format
         *
         */
        if (!is_array($controller)) {
            return;
        }

        /** @var Controller $controllerObject */
        list($controllerObject, $methodName) = $controller;

        $request = $this->requestStack->getCurrentRequest();
        $cookies = $request->cookies;
        $mkzCookie = $cookies->get('mkz');

        // Override the response only if the annotation is used for method or class
        if ($this->hasSecureTokenAnnotation($controllerObject, $methodName)) {
            try {
                if (!$mkzCookie) {
                    throw new TokenException(TokenException::ERROR_NOT_FOUND, 404);
                }
                $this->tokenService->findToken($mkzCookie);
            } catch (TokenException $e) {
                throw new AccessDeniedHttpException($e->getMessage(), $e);
            }
        }
    }

    /**
     * @param Controller $controllerObject
     * @param string $methodName
     * @return bool
     */
    private function hasSecureTokenAnnotation(Controller $controllerObject, string $methodName) : bool
    {
        $tokenAnnotation = SecureToken::class;

        $hasAnnotation = false;

        // Get class annotation
        // Using ClassUtils::getClass in case the controller is an proxy
        $classAnnotation = $this->reader->getClassAnnotation(
            new ReflectionClass(ClassUtils::getClass($controllerObject)), $tokenAnnotation
        );

        if ($classAnnotation) {
            $hasAnnotation = true;
        }

        // Get method annotation
        $controllerReflectionObject = new ReflectionObject($controllerObject);
        $reflectionMethod = $controllerReflectionObject->getMethod($methodName);
        $methodAnnotation = $this->reader->getMethodAnnotation($reflectionMethod, $tokenAnnotation);

        if ($methodAnnotation) {
            $hasAnnotation = true;
        }

        return $hasAnnotation;
    }
}

Our event listener uses the annotation reader class, and takes the request object. When the event triggers, the onKernelController() method is called, where we get the Access Token cookie from the request. Then it checks for the @SecureToken annotation, which can either cover an entire class, or can be set in individual method docblocks.

Next, we hook up the service autowiring in the config services.yml:

our.event_listener.secure_token:
    class: Our\CustomerZoneBundle\EventListener\SecureTokenAnnotationListener
    autowire: true
    tags:
        - { name: kernel.event_listener, event: kernel.controller }

Symfony autowiring is pretty cool. the autowire true key allows Symfony to take care of object instantiation, so we don’t even need to fetch the annotation reader or request for the constructor!

Finally, we add our annotation to our method, and remove our check from inside the method:

/**
 * @Rest\Put("/auth/change-password")
 * @SecureToken
 */
public function changePasswordAction(Request $request)
{
    // actual change password logic here
}

Now using whatever HTTP client you like (POSTman 😉 !) when we add our Access Token cookie header, the check happens automatically! Removing the cookie now gives us a 403 response! Success! Have fun! 😀

Codeception Acceptance tests with Javascript

I had an issue on this old legacy site in work where I was writing a basic acceptance test where it clicks all the links in the top section of the home page. The problem was that one of the links opened another window using JavaScript. So I had to reconfigure Codeception to get it running.

There are various different drivers that codeception uses, PhpBrowser which doesn’t do JS, Selenium WebDriver does, and you have several options; you could install Selenium, chrome headless browser, or phantomjs. I chose phantomjs, as it was easiest (for me) to get up and running on a non X Server.

First up, you’ll need phantomjs. Go download it, unpack the zip, move the folder somewhere, and then symlink the bin/phantomjs to /usr/bin/phantomjs.

Next, launch phantomjs like so:

phantomjs --webdriver=4444 --ignore-ssl-errors=true --ssl-protocol=any

Now, in your YAML:

# Codeception Test Suite Configuration

# suite for acceptance tests.
# Run the following command FIRST:
# phantomjs --webdriver=4444 --ignore-ssl-errors=true --ssl-protocol=any

# RUN `build` COMMAND AFTER ADDING/REMOVING MODULES.

class_name: WebGuy
modules:
     enabled:
         - WebDriver
         - WebHelper
     config:
         WebDriver:
             url: 'https://USER:PASS@YOUR_URL_HERE'
             browser: phantomjs
             capabilities:
                 acceptSslCerts: true

If you have a site using HTTP Basic Auth, put USER:PASSWORD@ in yopur URL, if not, remove it.

Now in your acceptance test, you can write:

$i->click('Nouvel abonnement');
$i->switchToWindow('webformswin');

Note that, in your Javascript, when you run the open window function, you specify a name. This is the name you use, and not the title from the HTML <head> section!

And there you have it! We can now test with javascript functionality!

Debugging a Twig View

Just a quick note here to save future hunting.

Ever seen this crap error message?

An exception has been thrown during the rendering of a templat

It totally sucks, right? And then you try debugging with XDebug, only to find you can’t most of the time, since Twig uses eval().

Anyway, to save you looking, if you set a breakpoint where that message is thrown you can get to see your own Exception:

vendor/twig/twig/lib/Twig/Template.php

Look at line 401 (this may have changed in later versions):

} catch (Exception $e) {
    throw new Twig_Error_Runtime(sprintf('An exception has been thrown during the rendering of a template ("%s").', $e->getMessage()), -1, $this->getTemplateName(), $e);
}

You can now see your Exception!

Creating DOMElements from HTML strings

DOMDocuments are cool, and a really nice way of dealing with HTML in an OO fashion. However, sometimes, we have an HTML string element which we need to add to our Document. Here’s how you do it:

    function createNodesFromHTML(DOMDocument $doc,$str) 
    {
        $nodes = array();
        $d = new DOMDocument();
        $d->loadHTML("<html>{$str}</html>");
        $child = $d->documentElement->firstChild->firstChild;
        while($child) {
            $nodes[] = $doc->importNode($child,true);
            $child = $child->nextSibling;
        }
        return $nodes;
    }


        $dom = new DOMDocument();
        $icon = '<i class="fa fa-remove"></i>'; // This is our string

        $button = $dom->createElement('a');
        $button->setAttribute('href', '/whatever/delete/12345');
        $button->setAttribute('class', 'btn btn-sm btn-danger');
        
        // This is us turning the string(s) into nodes we can add
        $nodes = createNodesFromHTML($dom, $icon);
        $button->appendChild($nodes[0]);
        
        $dom->appendChild($button);
        echo $dom->saveHTML();