Ichthyostega
b556d2b770
Some sections of the Lumiera website document meeting minutes, discussion protocols and design proposals from the early days of the project; these pages were initially authored in the »Moin Moin Wiki« operated by Cehteh on pipapo.org at that time; this wiki backed the first publications of the »Cinelerra-3« initiative, which turned into the Lumiera project eventually. Some years later, those pages were transliterated into Asciidoc semi-automatically, resulting in a lot of broken markup and links. This is a long standing maintenance problem problem plaguing the Lumiera website, since those breakages cause a lot of warnings and flood the logs of any linkchecker run.
199 lines
9 KiB
Text
199 lines
9 KiB
Text
Design Process: Forward Iterator
|
|
================================
|
|
|
|
[options="autowidth"]
|
|
|====================================
|
|
|*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
|
|
https://en.wikipedia.org/wiki/Iterator[Iterator pattern]. Iteration can be
|
|
implemented by _convention_, _polymorphism_ or by _generic programming;_
|
|
we use the latter approach.
|
|
|
|
|
|
Lumiera Forward Iterator concept
|
|
--------------------------------
|
|
.Definition
|
|
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 `bool` conversion.
|
|
- 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()+
|
|
and +end()+ 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 https://issues.lumiera.org/ticket/349[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
|
|
--------
|
|
//comments: append below
|
|
|
|
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>~
|
|
|
|
NOTE: 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-`for` construct 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-`for` construct 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>~
|
|
|
|
|
|
//endof_comments:
|
|
|
|
|
|
Final
|
|
~~~~~
|
|
Accepted on
|
|
link:{ldoc}/devel/meeting_summary/2011-04-13.html#_lumiera_forward_iterator[developer meeting]
|
|
|
|
Christian Thaeter:: 'Thur 14 Apr 2011 02:52:30 CEST'
|
|
|
|
TIP: 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 link:/x/DesignProcess.html[Lumiera Design Process overview]
|