====== Request for Comments: SPL Improvements: Data Structures ======
  * Version: 1.0
  * Date: 2012-02-07
  * Author: Levi Morrison <levim@php.net>
  * Status: Work-in-progress


===== Introduction =====

The data structures in the SPL are flawed in many ways.  See [[/rfc/spl-improvements]] for more information on the SPL.
===== What is wrong with the data structures? =====

   * **The data-structures are inconsistent in how they act when in the same situation.** Consider the following example where an [[http://php.net/manual/en/class.spldoublylinkedlist.php|SplDoublyLinkedList]] and an [[http://php.net/manual/en/class.splfixedarray.php|SplFixedArray]] encounter the same problem: an index greater than the size of the container was accessed.
   * <code php><?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";
}
?></code>The result: <code text>OutOfRangeException: Offset invalid or out of range
RuntimeException: Index invalid or out of range</code> 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: <code php><?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";
}
?></code> The result: <code text>OutOfRangeException: Offset invalid or out of range
OutOfRangeException: Offset invalid or out of range
RuntimeException: Can't pop from an empty datastructure</code>
      - 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.
      -  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. 
      - Popping from an empty container caused a generic RuntimeException to be thrown.  The more correct exception would be [[http://php.net/UnderflowException|UnderflowException]].

    * **[[http://php.net/manual/en/class.splobjectstorage.php|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.

    * [[http://php.net/manual/en/class.splstack.php|SplStack]] and [[http://php.net/manual/en/class.splqueue.php|SplQueue]] are fully exposed [[http://php.net/manual/en/class.spldoublylinkedlist.php|SplDoublyLinkedList]]s.  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.
===== Proposal =====

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

===== Changelog =====