State |
Final |
Date |
2009-11-01 |
Proposed by |
Ichthyostega |
The situation addressed by this concept is when an API needs to expose a sequence of results, values or objects, instead of just yielding a function result value. The naive solution of passing an pointer or array creates coupling to internals, and thus was superseded by the GoF Iterator pattern. Iteration can be implemented by convention, polymorphism or by generic programming; we use the latter approach.
Lumiera Forward Iterator concept
An Iterator is a self-contained token value, representing the promise to pull a sequence of data
-
rather then deriving from an specific interface, anything behaving appropriately can be used as Lumiera Forward Iterator.
-
the client finds a typedef at a suitable, nearby location. Objects of this iterator type can be created, copied and compared.
-
any Lumiera forward iterator can be in exhausted (invalid) state, which can be checked by
boolconversion. -
Notably, all default constructed iterators are fixed to that state. Non-exhausted iterators may only be obtained by API call.
-
the exhausted state is final and can not be reset, implying that any iterator is a disposable one-way-off object.
-
when an iterator is not in the exhausted state, it may be dereferenced (
*i) to yield the “current value” -
moreover, iterators may be incremented (
++i) until exhaustion.
Discussion
The Lumiera Forward Iterator concept is a blend of the STL iterators and iterator concepts found in Java, C#, Python and Ruby. The chosen syntax should look familiar to C++ programmers and indeed is compatible to STL containers and ranges. However, while a STL iterator can be thought off as being actually “just a disguised pointer”, the semantics of Lumiera Forward Iterators is deliberately reduced to a single, one-way-off forward iteration, they can’t be reset or manipulated by any arithmetic, and the result of assigning to an dereferenced iterator is unspecified, as is the meaning of post-increment and stored copies in general. You should not think of an iterator as something to describe a position — rather it is a one-time promise to pull some data.
Another notable difference to the STL iterators is the default ctor and the
bool conversion. The latter allows using iterators painlessly within for
and while loops; a default constructed iterator is equivalent to the STL
container’s end() value — and indeed, any container-like object exposing
Lumiera Forward Iteration is encouraged to provide such an end()-function,
additionally enabling iteration by std::for_each.
Implementation notes
iter-adapter.hpp provides some helper templates for building Lumiera Forward
Iterators.
-
IterAdapter is the most flexible variant, intended for use by custom facilities. An IterAdapter maintains an internal back-link to a facilitiy exposing an iteration control API, which is accessed through free functions as extension point. This iteration control API is similar to C#, allowing to advance to the next result and to check the current iteration state.
-
RangeIter wraps two existing iterators — usually obtained from
begin()andend()of an STL container embedded within the implementation. This allows for iterator chaining. -
PtrDerefIter works similar, but can be used on an STL container holding pointers, to be dereferenced automatically on access
Similar to the STL habits, Lumiera Forward Iterators should expose typedefs for
pointer, reference and value_type. Additionally, they may be used for
resource management purposes by “carrying” a ref-counting facility, e.g.
allowing to keep a snapshot or restult set around until it can’t be accessed
anymore.
Tasks
The concept was implemented both for unit test and to be used on the QueryResolver facility; thus it can be expected to show up on the session interface, as the PlacementIndex implements QueryResolver. QueryFocus also relies on that interface for discovering session contents. Besides that, we need more implementation experience.
Some existing iterators or collection-style interfaces should be retro-fitted. See Ticket #349. Moreover, we need to gain experience about mapping this concept down into a flat C-style API.
Alternatives
-
expose pointers or arrays
-
inherit from an Iterator ABC
-
unfold the iteration control functions into the custom types
-
define a selection of common container types to be allowed on APIs
-
use active iteration, i.e. pass a closure or callback
Rationale
APIs should be written in a way that avoids to tie them to the current implementation. Exposing iterators is known to create a strong incentive in this direction and thus furthers the creation of clean APIs.
Especially in Steam-Layer we employ already several iterator implementations, but without an uniform concept, these remain just slightly disguised implementation types of a specific container. Furthermore, the STL defines several quite elaborate iterator concepts. Ichthyo considers most of these an overkill and an outdated implementation-centric approach. Many modern programming languages rely on a very simple iterator concept with much success.
Thus the idea is to formulate a concept in compliance with STL’s forward iterator — but augmented by an stop-iteration test. This would give us basic STL integration and look familiar to C++ and Java programmers without compromising the clean APIs.
Comments
This scheme is now in use since more then a year, without turning up any serious problems.
The only minor concern I can see is that this concept, as such, does not solve the
problem with exposing implementation details of the underlying container on the API.
Similar to STL Iterators, the actual implementation representation is only disguised
behind a typedef'. But, generally speaking, this is an inevitable consequence of the
``zero overhead'' abstraction. For the cases when an indirection (via VTable) is feasible,
I've created the **`IterSource** template, which adheres to this Lumiera Forward Iterator
concept, yet provides an opaque frontend, allowing to decouple completely from the
actual implementation. Besides that, over time, I have written several standard adaptors
for the most common STL containers, plus Map, key and value extractors.
- Ichthyostega
-
Sa 16 Apr 2011 00:20:13 CEST
minor change: removed support for post-increment. It doesn’t fit with the concept and caused serious problems in practice. A correct implementation of post-increment would require a “deep copy” of any underlying data structures.
- Ichthyostega
-
Sa 07 Jan 2012 21:49:09 CET <prg@ichthyostega.de>
|
Lumiera Forward Iterators can be made to work together conveniently
with the »Range-for Loop«, as introduced with C++11. The preferred
solution is to define the necessary free functions begin and end
for ADL. This is best done on a per implementation base. |
Considered at a conceptual level, this may seem surprising, since the
Range-Iteration from the C++ standard and our Forward-Iteration do not mesh
up completely, and build upon a different understanding: The standard Range-for
Loop assumes “a container”, or at least “a data range”, while our
Forward Iterator Concept deals with “abstract data sources”. So
these are two concepts operating at a different level of abstraction,
yet able to be stacked upon each other. However, the user needs
to understand the fine points of those conceptual differences:
-
if you apply the Range-
forconstruct on a container, you can iterate as often as you like. Even if the iterators of that container are implemented in compliance with the Lumiera Forward Iterator concept. -
but if you apply the range-
forconstruct on a given iterator, you can do so only once. There is no way to reset that iterator, other than obtaining a new one.
See 71167be9c9aaa for the typical bridge implementation
- Ichthyostega
-
Sa 04 Jul 2015 22:57:51 CEST <prg@ichthyostega.de>
Final
Accepted on developer meeting
- Christian Thaeter
-
Thur 14 Apr 2011 02:52:30 CEST
|
The Lumiera Forward Iterator became a widely used scheme.
One notable extension built on top is the filter pipeline template IterExplorer.
Another point worth mentioning is that such an iterator can not only yield values
(as described in this RfC), but may also expose a reference into an underlying
State Core — which makes high-performance collaboration protocols possible,
while keeping all participants opaque. |
Back to Lumiera Design Process overview