HarfBuzz Study: hb-iter
behdad
August 5, 2022
Introduction
To implement the HarfBuzz font subsetter library, we introduced facilities called the hb-iter, that is in its function similar to the C++20 Ranges library, which itself is based on the earlier range-v3 library work by Eric Niebler et al.
While the range-v3 library is available for C++ as early as C++14, it still is not available for C++11 which is the version of C++ that HarfBuzz currently requires. As such, we built our own solution, hb-iter, which is a vastly simplified version of the same ideas. This writeup introduces hb-iter and how it helped our needs.
C++20 Ranges
A C++20 Range in its simplest form can be thought of as a [begin,end) pair of C++ iterators. Whereas in earlier versions of C++ one would have to pass a begin iterator and an end iterator to most algorithms, with a range, one would just pass one object around. This allows for composition in a way that was not possible before. In particular, with the pipeline overloaded operator “|”, one can do things like:
#include <ranges>
#include <iostream>
int main()
{
auto const ints = {0,1,2,3,4,5};
auto even = [](int i) { return 0 == i % 2; };
auto square = [](int i) { return i * i; };
// "pipe" syntax of composing the views:
for (int i : ints | std::views::filter(even) | std::views::transform(square)) {
std::cout << i << ' ';
}
// is equivalent to a traditional "functional" composing syntax:
for (int i : std::views::transform(std::views::filter(ints, even), square)) {
std::cout << i << ' ';
}
}
The hb-iter equivalent would be:
for (int i : ints | hb_filter(even) | hb_map(square)) {
std::cout << i << ' ';
}
The pipeline syntax
The pipeline syntax, eg. “it | hb_filter(pred)” is nothing but syntactic sugar for composing algorithms. The “L | R”, in HarfBuzz, when C is an iterator, simply returns “R(L)”:
template <typename Lhs, typename Rhs,
hb_requires (hb_is_iterator (Lhs))>
static inline auto
operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN
(std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs)))
This allows for building pipelines in C++ code the same way that we build in, eg. shell scripts.
The dagger
In hb-iter, we use operator overloading extensively, like the C++ library does as well. One operator we also overload is the unary-plus operator (+it), to return a copy of an iterator. You might notice that what we call an iterator in hb-iter is what C++20 calls a range, that is, a pair of [begin,end) C++ iterators. Another way to think of the unary-plus iterator is that it gives you a copy of an rvalue from an lvalue. At any rate, it is useful to make sure you don’t drain an iterator but use a copy of it.
The idiom of creating a copy from an iterator (even unnecessarily), passing it through a pipeline and draining it and ending the statement, when formatted vertically, forms a statement block that we call a dagger. For example:
+ hb_zip (this+coverage, substitute)
| hb_filter (c->parent_active_glyphs (), hb_first)
| hb_map (hb_second)
| hb_sink (c->output)
;
This replaces a block of code that walks two containers, this+coverage and substitute, together, checks that the first item belongs to c->parent_active_glyphs(), and if that passes, adds the second item to c->output. We find the dagger version easier to reason about, and it has the same performance as the best hand-written code.
The hb_sink in that block needs calling out, because as far as I know it does not exist in the C++20 Ranges library in that form. It feeds an iterator into a container by way of operator <<, and our containers implement that.
Tools of composition
The tools of iterator composition are the same in every language eg. Python: you have filter, map (aka transform), apply, and the zip, enumerate, range, iota, repeat, concat, reduce, all, any, none, …
How it works
Unlike C++ iterators, hb-iter iterators all inherit from hb_iter_t, which uses the CRTP pattern for static polymorphism. This class implements all the various overloaded operators (correctly!) and hands off to the concrete implementation for the actual operations, namely: __end__(), __more__(), __len__(), __item__(), __item_at_(), __forward__(), __next__(), __rewind__(), __prev__().
Iterators may be random-access or not. If an iterator is not random-access, they need not implement some of the methods, namely, __len__(), __item_at(), __forward__(), __rewind__(). There is a hb_iter_fallback_mixin_t that subclasses can inherit from, that will fill in the missing implementations the slow way by calling the other methods repeatedly.
Moreover, if, eg. an iterator is not bidirectional, it simply would not implement __prev__(), and it would only fail at compile time if it is tried to be used for backward traversal.
A collection will return an iterator via its .iter() method. The hb_iter() function calls that method on its argument. By default collections return a read-only iterator. Collections that support it, will return a writable iterator via their .writer() methods.
Like in C++, an iterator is its own iterator. And both collections and iterators expose .begin() and .end(), so they work with C++ range loops.
Finally, the hb_iter_t also exports .is_iterator = true, as well an .item_t type, such that we can easier detect iterators and write generic code against iterators.
Writing generic code
For writing generic templated function code there exist two predicates macros:
hb_is_iterable
hb_is_iterator
Or even more precisely, one can request an iterator of a specific item type via:
hb_is_iterator_of
However, most of the time, that is not what one should use, but the alternative:
hb_is_source_of
which takes type conversions into account.
Iterators also declare whether they are sorted. So there also exist the sorted variants below, to allow expressing that an API expects sorted input, and enforce it at compile-time:
hb_is_sorted_iterator
hb_is_sorted_iterator_of
hb_is_sorted_source_of
Finally, there is hb_is_sink_of, which declares a requirement that a type be able to receive a certain item type.
Here is an example of using putting these all together:
template<typename IteratorIn, typename IteratorOut,
hb_requires (hb_is_source_of (IteratorIn, unsigned)),
hb_requires (hb_is_sink_of (IteratorOut, unsigned))>
static void
_write_loca (IteratorIn it, bool short_offsets, IteratorOut&& dest)
{
unsigned right_shift = short_offsets ? 1 : 0;
unsigned int offset = 0;
dest << 0;
+ it
| hb_map ([=, &offset] (unsigned int padded_size)
{
offset += padded_size;
return offset >> right_shift;
})
| hb_sink (dest)
;
}
Subsetting example
The HarfBuzz font subsetter library is why we implemented hb-iter in the first place. Font subsetting is the process of taking an input font, and an input specification, and producing an output font that is a subset of the input font adhering to the specification. The specification typically involves a list of Unicode characters that the output font must support, as well as other aspects.
This problem is ripe for iterator composition because the font data structures are full of arrays that need to be iterated over, sometimes in parallel (zipped) with other arrays, filtered, mapped (transformed), and finally written out. That is exactly how we use hb-iter in the subsetter code. For example:
void closure (hb_closure_context_t *c) const
{
+ hb_zip (this+coverage, sequence)
| hb_filter (c->parent_active_glyphs (), hb_first)
| hb_map (hb_second)
| hb_map (hb_add (this))
| hb_apply ([c] (const Sequence<Types> &_) { _.closure (c); })
;
}
void collect_glyphs (hb_collect_glyphs_context_t *c) const
{
if (unlikely (!(this+coverage).collect_coverage (c->input))) return;
+ hb_zip (this+coverage, sequence)
| hb_map (hb_second)
| hb_map (hb_add (this))
| hb_apply ([c] (const Sequence<Types> &_) { _.collect_glyphs (c); })
;
}
bool subset (hb_subset_context_t *c) const
{
TRACE_SUBSET (this);
const hb_set_t &glyphset = *c->plan->glyphset_gsub ();
const hb_map_t &glyph_map = *c->plan->glyph_map;
auto *out = c->serializer->start_embed (*this);
if (unlikely (!c->serializer->extend_min (out))) return_trace (false);
out->format = format;
hb_sorted_vector_t<hb_codepoint_t> new_coverage;
+ hb_zip (this+coverage, sequence)
| hb_filter (glyphset, hb_first)
| hb_filter (subset_offset_array (c, out->sequence, this), hb_second)
| hb_map (hb_first)
| hb_map (glyph_map)
| hb_sink (new_coverage)
;
out->coverage.serialize_serialize (c->serializer, new_coverage.iter ());
return_trace (bool (new_coverage));
}
Hashmap example
As a final example, we look into how our hashmap’s own iterators are implemented. The hashmap has six iterators: items, keys, values, and referenced versions of those. Instead of manually writing these iterators, we wrote them using iterator composition:
auto iter () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::get_pair)
)
auto iter_ref () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::get_pair_ref)
)
auto keys () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::key)
| hb_map (hb_ridentity)
)
auto keys_ref () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::key)
)
auto values () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::value)
| hb_map (hb_ridentity)
)
auto values_ref () const HB_AUTO_RETURN
(
+ hb_array (items, mask ? mask + 1 : 0)
| hb_filter (&item_t::is_real)
| hb_map (&item_t::value)
)
Conclusions
C++20 Ranges library offers a powerful and succinct syntax for algorithm composition. With hb-iter we brought some of those benefits to our C++11 codebase. The result has been code that is shorter and easier to reason about, without any performance loss.