strit

Overview ¶

Package strit introduces a string iterator of "push" type, as well as a number of iterator constructors and wrappers.

Typically, iteration over some source of data involves creating an object of some reader type, then repeatedly calling a method on the object to get the data elements, and finally calling some method to release the resources allocated inside the reader object. And in the languages without exceptions (like Go) there must be an error check on each step. In other words, there is an interface and some protocol all the clients must follow, which usually results in certain amount of boilerplate code to write.

The above example describes the so called "pull" model of iteration where the client has to call a method on the reader to "pull" the next data element out of the reader object. Alternative to that is the "push" model where client gives the iterator a callback function to be invoked once per each element of input data.

Another aspect of the iteration model is about dealing with errors. In the absence of exceptions, like in Go language, the "pull" model implies that the result of each step of the iteration is either a data item, or an error. The same is true for pure "push" model where each invocation of the callback has to receive two parameters: a data element and an error. Or there maybe two callbacks, one for data and another for errors, but this is conceptually the same.

This library is an experiment in combining both "push" and "pull" models: it utilises "push" model for data elements, and "pull" model for error propagation. The data elements here are strings only, as currently the Go language does not offer any generic programming mechanism. The iterator type itself is a function that invokes the supplied callback once per each input string, and it returns either an error or nil. This arrangement reduces the amount of boilerplate code, at least in the most common scenarios, plus it allows for easy iterator combination, especially useful where dynamic creation of string processing pipelines is required.

The string iterator type used throughout this library is simply a function of the type func(Func) error, where Func is the type of the callback, func([]byte) error. Strings are represented as byte slices for performance reasons, to allow for in-place modifications where possible, like in bytes.TrimSpace() function. Iteration is simply an invocation of the iterator function with a callback to receive strings. The iterator function returns whatever error may have occurred during the iteration. The callback function itself may also return an error which will stop the iteration and will be returned from the iterator function. The special error value of io.EOF is treated as a request to stop the iteration and will not be propagated up to the caller.

The library offers a number of iterator constructors making iterators from different sources like strings, byte slices, byte readers, files and shell command outputs. There is also a number of mapping and filtering functions, as well as writers for strings, byte slices and files. All the above is composable using fluent API. For example, reading a file line by line, removing leading and trailing whitespace from each line, selecting only non-empty lines that also do not start from the character '#', and storing the result in a slice of strings, may look like this:

lines, err := strit.FromFile("some-file").
              Map(bytes.TrimSpace).
              Filter(strit.Not(strit.Empty).OrNot(strit.StartsWith("#"))).
              Strings()

Here strit.FromFile is an iterator constructor, Map and Filter operations are iterator wrappers each creating a new iterator from the existing one, and Strings() is the iterator invocation. Also notice the use of the provided predicate combinators in the parameter to the Filter() function.

Given that each iterator is itself a function, other iterators can be derived from the existing ones. For example, the following function takes an iterator and creates a new iterator that prepends the line number to each line from the original iterator:

func Numbered(iter Iter) Iter {
    return func(fn Func) error { // this is the new iterator function
        i := 0

        // this is the invocation of the original iterator function
        return iter(func(line []byte) error {
            i++
            line = []byte(fmt.Sprintf("%d %s", i, string(line)))
            return fn(line)	// invocation of the callback
        })
    }
}

Iterators in this library are lazy, meaning that the actual iteration happens only when the iterator function is called, not when it is created. Some of the provided iterators are reusable, meaning that such iterator may be called more than once, but in general this property cannot be guaranteed for those sources that cannot be read multiple times (like io.Reader), so in general it is advised that in the absence of any specific knowledge every iterator should be treated as not reusable. All the iterator implementations have O(n) complexity in time and O(1) in space.

One disadvantage of the suggested model is the complex implementation of parallel composition of iterators, see the comment to the Merge() function for more details. Also, there is a certain cost of abstraction incurred, in other words, a straight-forward implementation of the above example could be somewhat more efficient in terms of CPU cycles and memory consumption, though the difference would mostly come from the extra function calls and as such would probably be not so substantial, especially for i/o-bound sources. The actual benchmaking of some simple processing scenarios shows that the performance difference is truly minor.