Internals of Fastscapelib#

This section provides information about Fastscapelib’s internals, its design and architecture. It is intended for anyone who wants to contribute improving Fastscapelib or who wants to simply understand how it works under the hood.

Note

Fastscapelib makes use of advanced techniques and patterns such as template meta-programming, CRTP, type erasure, etc. Being familiar with these techniques in C++ will help you better understand its internals.

Xtensor & Language Bindings#

Fastscapelib heavily relies on the Xtensor C++ library for both its API and its internals. Xtensor provides multi-dimensional array containers that may be handled in a very similar way than NumPy arrays in Python.

For usage within C++ there are two main container types xt::xtensor and xt::xarray with a static and dynamic number of dimensions, respectively. In addition, Xtensor supports adapting other existing containers and therefore enables seamless interoperability with array structures exposed in other C++ libraries or other languages.

Python#

Fastscapelib’s Python bindings are built with the help of Pybind11 and Xtensor-python. The latter provides two container types xt::pytensor and xt::pyarray that each adapt CPython’s buffer protocol. This allows using the Fastscapelib C++ algorithm implementations from Python directly with NumPy arrays without copying any data.

Supporting Other Languages#

Unlike for Python, first-class support for other language bindings is not planned at the moment.

It shouldn’t be too hard doing it, though, at least for a few other languages popular in scientific computing. Like Xtensor-python for NumPy arrays, Xtensor-R and Xtensor-julia provide ready-to-use adaptors for using in-place R and Julia arrays, respectively.

Supporting languages like Fortran or MatLab would require writing custom Xtensor adaptors. Xtensor array containers support multiple layouts for representing multi-dimensional arrays (i.e., row-major vs. column-major).

Container Selectors#

In order to avoid duplicating their implementation for each Xtensor container type, most of Fastscapelib’s classes (grid classes, flow_graph, etc.) expose a template parameter that allows choosing the type of container to use for their array data members.

See Xtensor container selectors and Xtensor’s documentation for more details.

Grids#

Class Hierarchy (CRTP)#

All grid classes in Fastscapelib provide a common interface via their grid base class, which allows implementing algorithms in a grid-agnostic fashion.

Grids may greatly differ from each other (e.g., 1-dimensional vs. 2-dimensional, structured vs. unstructured) such that implementing a unified grid API is best achieved using polymorphism.

Since the grid API is often called a lot of times in inner loops (i.e., iterate over grid nodes and their neighbors), static polymorphism (at compile time) is preferred over dynamic polymorphism (at runtime). It is implemented using the Curiously Recurring Template Pattern (CRTP):

  • the grid and structured_grid base classes both have a G template parameter that represents one of the grid final (leaf) classes

  • those base classes also have a derived_grid() protected method to cast the grid instance into the G grid (leaf) type

See the class diagram below (showing only a subset of the public API for clarity). See also the grid API reference for more details.

classDiagram grid~G~ <|-- structured_grid~G~ grid~G~ <|-- trimesh_xt structured_grid~G~ <|-- profile_grid_xt structured_grid~G~ <|-- raster_grid_xt class grid~G~{ #derived_grid() +is_structured() +is_uniform() +neighbors_count(idx) +neighbors_indices(idx) +neighbors_distances(idx) +neighbors(idx) } class structured_grid~G~{ +spacing() +length() +shape() } class profile_grid_xt class raster_grid_xt{ +neighbors_indices(row, col) +neighbors(row, col) } class trimesh_xt

Python Bindings#

Note that since we use static polymorphism, only the grid leaf classes are exposed in Python, i.e., grid and structured_grid have no Python bindings and the grid Python classes have no common base class.

Grid Inner Types#

The grid base classes need some types and values that are specific to each grid derived type (e.g., grid resolution, number of dimensions of grid field arrays, maximum number of node neighbors, etc.) and that must therefore be defined in grid leaf classes.

However, with CRTP this is not possible since a CRTP leaf class is only declared when the CRTP base class is being defined.

As a workaround, those grid inner types and values are defined in a separate template class grid_inner_types that is specialized for each grid leaf class.

Flow Graph#

Implementation(s)#

The template class flow_graph is distinct from its implementation done in the template class flow_graph_impl<G, S, Tag>. Both expose the same template parameters, where Tag is used for selecting a given graph implementation (or representation).

Currently, Fastscapelib only supports one implementation based on fixed-shape arrays to store the graph topology. This implementation is selected via the flow_graph_fixed_array_tag type. Other implementations may be added in the future, for example based on linked-lists or sparse matrices, maybe reusing C++ graph libraries like the Boost Graph Library or a GraphBLAS C++ API.

The same template parameter Tag is also used by the flow operator implementation classes.

Python Bindings#

It is not possible with Pybind11 to expose in Python a C++ template class that is not fully specialized.

Since the template class flow_graph has the grid (leaf) type as template parameter G, we rely on the type erasure technique in order to avoid exposing separate flow graph classes in Python for each grid type.

Flow Operators#

Like the flow graph, the architecture of flow operators decouples an operator from its implementation(s) so that it will be possible to later support other graph internal representations while reusing the same operators. It also makes easier exposing the flow operator classes in Python, since flow_operator is not a template class, nor any of its subclasses.

The architecture of flow operators is a bit more complex, as shown in the diagram below.

classDiagram flow_operator "1" *-- "1" flow_operator_impl_base~FG, OP~: shared pointer flow_operator_impl_base~OP~ <|-- flow_operator_impl~FG, OP, Tag~ flow_operator_impl~FG, OP, Tag~ "1" *-- "1" flow_operator_impl_facade~FG~ : type erasure flow_operator_sequence~FG~ "1" --* "n" flow_operator_impl_facade~FG~ flow_operator_sequence~FG~ "1" *-- "1" flow_graph~G, S, Tag~ class flow_operator{ +elevation_updated +graph_updated +in_flowdir +out_flowdir +virtual name() } class flow_graph~G, S, Tag~{ +operators() } class flow_operator_impl_base~FG, OP~{ #m_op_ptr +apply(...) +save(...) } class flow_operator_impl~FG, OP, Tag~ class flow_operator_impl_facade~FG~{ +apply(...) +save(...) } class flow_operator_sequence~FG~{ +elevation_updated() +graph_updated() +out_flowdir() }

Operator (Interface) Classes#

The flow_operator abstract base class provides the operator interface. Each operator must be defined as a subclass, within which the operator parameters (if any) should also be defined.

Operator Implementation (Template) Class#

The flow_operator_impl<FG, OP, Tag> template class is where all the operators are implemented. It must be partially specialized for the two following template parameters:

  • OP (flow operator type): at least one specialization must exist for each flow_operator subclass.

  • Tag (flow graph implementation tag): a flow operator may be implemented for one or more of the available flow graph representations.

It is not specialized regarding the FG parameter (actual flow graph implementation type), which also depends on the grid (leaf) type G passed from the flow graph (i.e., FG is equivalent to flow_graph_impl<G, S, Tag>).

flow_operator_impl<FG, OP, Tag> inherits from a base class that has the following methods and members:

  • apply(): method through which the actual logic of the operator is executed and that should be re-implemented by every operator

  • save(): method re-implemented by flow_snapshot and generally not re-implemented by other operators

  • m_op_ptr: a shared pointer to an instance of OP, useful for accessing from within the implementation code the current values set for the operator parameters, if any

Operator Sequence Class#

The template class flow_operator_sequence<FG> serves as an intermediate for instantiating the implementation of each of the operators that have been passed to flow_graph. This is done via the template class flow_operator_impl_facade<FG>, which implements type erasure so that instances of flow_operator_impl<FG, OP, Tag> of arbitrary operators types OP can be built and added to the sequence at runtime.