Request for Comments: SPL Improvements: Data Structures

• Version: 1.0
• Date: 2012-02-07
• Author: Levi Morrison levim@php.net
• Status: Work-in-progress

The data structures in the SPL are flawed in many ways. See spl-improvements for more information on the SPL.

• The data-structures are inconsistent in how they act when in the same situation. Consider the following example where an SplDoublyLinkedList and an SplFixedArray encounter the same problem: an index greater than the size of the container was accessed.

• <?php
  try {
      $linkedList = new SplDoublyLinkedList();
      $linkedList[1];
  } catch(Exception $error) {
      echo get_class($error) . ': ' . $error->getMessage(). "\n";
  }
  try {
      $fixedArray = new SplFixedArray();
      $fixedArray[1];
  } catch(Exception $error) {
      echo get_class($error) . ': ' . $error->getMessage(). "\n";
  }
  ?>

  The result:

  OutOfRangeException: Offset invalid or out of range
  RuntimeException: Index invalid or out of range

  They do not throw the same exception. Furthermore, SplDoublyLinkedList throws an exception that inherits from LogicException when it is not a logical exception but a runtime one.

• The data-structures do not throw the most appropriate and specific exceptions they can. Throwing specific exceptions makes it easier to debug applications. Consider the following example using an SplDoublyLinkedList where an attempt is made to access an out-of-bounds index, to set an index using a class, and to call pop on an empty container:

  <?php
  $linkedList = new SplDoublyLinkedList();
   
  try {
      $linkedList[1];
  } catch(Exception $error) {
      echo get_class($error) . ': ' . $error->getMessage() . "\n";
  }
   
  try {
      $linkedList[new StdClass()] = 'class';
  } catch(Exception $error) {
      echo get_class($error) . ': ' . $error->getMessage() . "\n";
  }
   
  try {
      $linkedList->pop();
  } catch(Exception $error) {
      echo get_class($error) . ': ' . $error->getMessage() . "\n";
  }
  ?>

  The result:

  OutOfRangeException: Offset invalid or out of range
  OutOfRangeException: Offset invalid or out of range
  RuntimeException: Can't pop from an empty datastructure

  1. Accessing an out-of-bounds index led to an incorrect exception type of OutOfRangeException, a child of LogicException. The actual problem encountered was not a logical exception, but a runtime one.
  2. Trying to set an index using an invalid type (a class) led to an OutOfRangeException. The name is ambiguous, but the meaning is correct. The message that the exception provides is the real problem here. It does not provide what went wrong but presents two options.
  3. Popping from an empty container caused a generic RuntimeException to be thrown. The more correct exception would be UnderflowException.

• SplObjectStorage violates the idea of single responsibility. It is performing duties as a Map and a Set. The API is difficult to use because of this dual-identity.

• SplStack and SplQueue are fully exposed SplDoublyLinkedLists. This means you can use an SplStack or SplQueue just as you would use an array. This exposes too much of the implementation to the user and could be a source of bugs.

• SplStack and SplQueue should not publicly inherit from SplDoublyLinkedList.
• SplObjectStorage should be split into a Map(Dictionary) and Set.