A Case of Mistaken Iterator
Earlier this week, I spent most of a day tracing through code in search of the source of a bug that was causing part of our application to fail in strange ways.
In the back end, we have models that connect to CouchDB. These models implement the Iterator pattern to allow easy traversal of a record’s keys.
When I wrote the code to implement Iterator
several months
ago, I dutifully checked the PHP
Manual and adapted the reference example that I found there:
<?php class Record implements Iterator { // (partial class, showing the iterator implementation only) public $_data = array(); public function rewind() { reset($this->_data); } public function current() { return current($this->_data); } public function key() { return key($this->_data); } public function next() { return next($this->_data); } public function valid() { return (current($this->_data) !== false); } }
Little did I realize that this implementation is very broken. I’ll explain why, below.
Over the past few years, I’ve implemented many iterators in
this way, using PHP’s implicit array manipulation functions
(reset()
, current()
, key()
,
next()
). These functions are very convenient because PHP
arrays are so powerful — arrays in PHP work like ordered hash tables in other
languages.
PHP’s implicit management of an array’s iteration index
(the value that is incremented by next()
and
referenced by key()
) is indeed convenient, but the convenience
can sometimes be offset by its very implicitness — the value is hidden from
you, the PHP programmer.
In PHP, generic array iteration (without the implicit iterator) isn’t actually as simple as it sounds. Remember that arrays aren’t arrays in the traditional sense, but ordered hash tables. Consider this:
$data = array('zero','one','two','three'); for ($i=0; $i<count($data); $i++) { // yeah, don't calculate count() on every iteration echo "{$data[$i]}\n"; }
Output:
zero
one
two
three
This first example is easy to iterate — the array contains sequential, numeric, zero-based keys. It gets more complicated when using non-sequential, and non-numeric keys:
$data = array( 'apple', 'cow' => 'moo', 'pig' => 'oink', 'orange' ); for ($i=0; $i<count($data); $i++) { echo "{$data[$i]}\n"; }
Output:
apple
orange
Notice: Undefined offset: 2 in - on line 10
Notice: Undefined offset: 3 in - on line 10
I could use foreach
, but because a numeric loop illustrates the point more clearly, here’s how I might implement the above code so that it works:
$data = array( 'apple', 'cow' => 'moo', 'pig' => 'oink', 'orange' ); $k = array_keys($data); for ($i=0; $i<count($data); $i++) { echo "{$data[$k[$i]]}\n"; }
Output:
apple
moo
oink
orange
This brings us back to the Iterator
implementation. Why
isn’t the code above correct? Take a closer look at this:
public function valid() { return (current($this->_data) !== false); }
A value of false
in the array is indistinguishable from a
false
value returned by current()
. Using the
above implementation with the following array would cause it to bail after
orange
(and subsequently might cause you to waste a day
tracking down the cause):
array( 'apple', 'orange', false, 'banana', );
On Tuesday night, I
updated the manual
to use an
improved Iterator
implementation.
It’s probably a bit slower (so you
can use the internal-indexing implementation if you’re sure your arrays
will never contain false
), but my implementation is more
robust.
<?php /** * A mixed-key iterator implementation * * Note: these array_keys() calls are slow. The array keys could be cached * as long as the cache value is invalidated when $_data is changed. */ class It implements Iterator { public $_data = array(); protected $_index = 0; public function rewind() { $this->_index = 0; } public function current() { $k = array_keys($this->_data); return $this->_data[$k[$this->_index]]; } public function key() { $k = array_keys($this->_data); return $k[$this->_index]; } public function next() { $k = array_keys($this->_data); if (isset($k[++$this->_index])) { return $this->_data[$k[$this->_index]]; } else { return false; } } public function valid() { $k = array_keys($this->_data); return isset($k[$this->_index]); } }
To use it:
$it = new It; $it->_data = array( 'one' => 1, 'two' => 2, false, 'four' => 4 ); foreach ($it as $k => $v) { echo "{$k}: {$v}\n"; }
Output:
one: 1
two: 2
0:
four: 4