Skip to main content

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