Type annotation in C++

In systems like game engines and our HTML renderer Hummingbird, developers have to work with objects transformed in different coordinate systems. Using one generic type can lead to confusion on what object is required in a particular situation. Errors are often subtle and hard to track. I tried to mitigate this by using stringent static typing in our software. New types are created by annotating them with metadata.

In the HTML visual model, almost everything is a box (a rectangle), and it’s size and position is calculated by the layout engine. The boxes however have to go through additional transformations until they reach their final positions on-screen – they can be scrolled, 2D/3D transformed by CSS properties etc. This is similar to a game engine where objects also undergo different transformations between coordinate systems – model, view, world, shadow and so on. Some calculations in the code require boxes in the Layout coordinate system, others need them scrolled, others need them transformed.

We used a Rectangle C++ struct everywhere in Hummingbird to represent a Box. It became a common error to pass the wrong Rectangle to an operation. For instance a certain calculation needs a Layout box, but the programmer passes by error a scrolled one. A more explicit system was required.
If we look at a typical C++ function signature in the style:

bool HitTest(float2 coords, const Rectangle& box);

It is unclear what the exact type of the box has to be – in our software the programmer could pass a scrolled box, while a layout one is required. Testing this is also tricky, because if the box has no scroll (it is 0,0) then it’ll work most of the time but break upon scrolling.

The issue was solved by “documenting” the requirement:

// Requires a layout box
bool HitTest(float2 coords, const Rectangle& layoutBox);

Unfortunately this is still error-prone as relies only on the programmer and code reviewer attention.

It’s better to have the C++ static type system help in the situation:

bool HitTest(float2 coords, const LayoutRectangle& box);

Now this is much more clear and will avoid accidental errors.

The idea can be extended to cover also the transformations themselves that lead to a certain box. The transformation (a matrix) is also strongly typed and encodes compile-time the coordinate system it work in. Instead of having a generic Matrix class we have a ScrollMatrix, CSSTransformMatrix etc as types. The product of a box transformation is defined by the input box and the matrix applied.

LayoutRectangle lb = LayoutElement(element);
ScrollMatrix scroll = GetScroll(element);
ScrollRectangle sr = lb.Transform(scroll);

The system will automatically generate the correct type from the input parameter and the typed transform.

Implementation

The system has the following requirements:

  • No runtime overhead
  • Types are defined by the transforms they encode
    • DisplayRectangle is Rectangle with {Layout, Scroll and CSSTransform}
    • ScrollRectangle is Rectangle with {Layout and Scroll}
  • Maximum static checking on types and improve code readability
  • Typed transforms must generate correct new types
  • Types that are a subset of another are allowed to be assigned on them. For instance:
    • DisplayRectangle ds = ScrollRectangle sr(..);

The final requirement may seem like a defeat on the static type system but it makes sense. A DisplayRectangle created from a ScrollRectangle is simply one that has an identity CSSTransform. It significantly simplifies intermediate calculations and avoids redundant copies.

The implementation of the system relies on template metaprogramming. It is one of the few cases where I find a good application for it’s somewhat esoteric constructs.
Coordinate systems are defined as types:

namespace CoordComponents
{
     struct Layout{};
     struct Scroll{};
// ..
}

Typed Rectangle is a thin wrapper around our generic Rectangle class.

template<typename… Components>
class Rectangle
{
// …
};

Commonly used types are defined as:

using LayoutRectangle = Rectangle<CoordComponents::Layout>;
using ScrolledRectangle = Rectangle<CoordComponents::Layout, CoordComponents::Scroll>;

The same principle is applied to the Matrix class which has a list of transformation components as its type signature.
The gist of the method validation and type synthesis can be seen in the Unite2D and Transform methods.

template<typename… RhsComponents>
void Unite2D(const Rectangle<RhsComponents…>& other, bool allowEmpty = false)
{
    static_assert(sizeof…(Components) >= sizeof…(RhsComponents), “Cannot assign to type with less components than operand!”);
    static_assert(meta_contains_types<meta_packer<Components…>, meta_packer<RhsComponents…>>::value, “Operand has components that are not part  of this object!”);
    m_Value.Unite2D(other.m_Value, allowEmpty);
}

Unite2D can take as parameter any other type of Rectangle but we validate:

  1. That the components of the this rectangle are less or equal those of the parameter. This avoids applying “broader” transforms to narrower ones, like uniting a ScrolledRectangle on a LayoutRectangle. They belong to different coordinate systems, so the operation is invalid.
  2. The second check handles situations where the two Rectangles might have a different set of components. Uniting a Rectangle<Layout, Scroll> with a Rectangle<Layout, Transform> is invalid.

The static_assert use some meta functions that implement the actual type checking.

The Transform method show type synthesis:

template<typename… MatrixComponents>
typename meta_unite_params<Rectangle<Components…>, Matrix<MatrixComponents…>>::type
Transform(const Matrix<MatrixComponents…>& mat) const
{
    typename meta_unite_params<Rectangle<Components…>, Matrix<MatrixComponents…>>::type result;
    result.m_Value = m_Value.Transform(mat.Unwrap());
    return result;
}

The declaration is definitely a mouthful, but basically says: “make a Rectangle, whose components are the union of the current one and the ones of the Matrix”. For instance:

Rectangle lr{…};
Matrix<Scroll, Transform> mst {…};
auto result = lr.Transform(mst); /*result is Rectangle<Layout, Scroll, Transform>*/

In this case “result” will have a type Rectangle<Layout, Scroll, Transform>, that is a Rectangle that is a Layout box with scrolling and some CSS transformation.

Results

The system is relatively new in our code, so the long time impact still has to be measured. I find however that local operations and data members are now much clearer in their intent and the amount of confusion has definitely decreased. I was concerned about compilation times but found no significant slowdown since the introduction of the system.

While the implementation is somewhat complex due to the meta programming stuff, the benefits outweigh it and the usage itself is straightforward.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s