Recursive Variant: A simple library for Recursive Variant Types

rva::variant — Recursive Sum Types for C++

Provided by the Recursive Variant Authority. We stand united in opposition to the TVA. May your variants never be pruned.

Variants are exceedingly useful in C++, but they suffer from a singular and fundamental shortcoming: unlike sum types in many other languages, there's no mechanism to define recursive variants in C++.

The Recursive Variant Authority provides a solution in the form of rva::variant, which allows you to write arbitrary recursive sum types with functionality identical to that provided by std::variant.

Understanding Recursive Variants

To understand what a recursive variant is, and why it's useful, consider something like a value in json. It can be any of the following:

  • A null value
  • A string
  • A number (usually represented as a double)
  • A boolean value (either true or false),
  • An object (aka, a map between strings and json values)
  • An array of values.

In a language like haskell, we could copy that definition pretty much verbatim (accounting for syntax, of course):

data JsonValue = JsonNull
               | JsonBoolean Bool
               | JsonNumber Double
               | JsonStr String
               | JsonObject (Map String JsonValue)
               | JsonArray [JsonValue]

It's important to note that JsonValue is being used in it's own definition: it's a recursive type.

Recursive types in C++

While this may seem a bit strange at first, recursive types aren't all that unusual. C++ has them too, and it's common for a type to store pointers to itself in situations such as a binary tree or a linked list. We can even define json_value as a recursive type using a union:

class json_value {
    int state = -1;
    union {
        /* state 0 */ std::nullptr_t m_null;
        /* state 1 */ bool m_bool;
        /* state 2 */ double m_number;
        /* state 3 */ std::string m_string;
        /* state 4 */ std::map<std::string, json_value> m_object;
        /* state 5 */ std::vector<json_value> m_array;
    };

   public:
    json_value(std::nullptr_t) : state(0), m_null() {}
    json_value(bool b) : state(1), m_bool(b) {}
    json_value(double d) : state(2), m_number(d) {}
    json_value(std::string const& str) : state(3), m_string(str) {}
    json_value(std::map<std::string, json_value> const& map) : state(4), m_object(map) {}
    json_value(std::vector<json_value> const& arr) : state(5), m_object(m_array) {}

    // Now we need to write move constructors...
    json_value(std::string&& str) : state(3), m_string(std::move(str)) {}
    json_value(std::map<std::string, json_value>&& map) : state(4), m_object(std::move(map)) {}
    json_value(std::vector<json_value>&& arr) : state(5), m_object(std::move(m_array)) {}

    // Now assignment operators...

    // Now comparison operators...

    // .emplace() might be nice

    // Oh hey did we forget copy and move assignment for json_value?

    // maybe we should have a way to check what the index of the currently active element is
};

std::variant is only a partial solution

It quickly becomes apparent that the class we're writing is essentially a specialization of std::variant, which (thankfully) simplifies a lot of the code:

class json_value {
    std::variant<
        std::nullptr_t,
        bool,
        double,
        std::string,
        std::map<std::string, json_value>,
        std::vector<json_value>> value;

   public:
    json_value() = default;
    json_value(json_value const&) = default;
    json_value(json_value&&) = default;
    template <class T>
    json_value(T&& object) : value(std::forward<T>(object)) {}


    // Now assignment operators...

    // Now comparison operators...

    // .emplace() might be nice

    // maybe we should have a way to check what the index of the currently active element is
};

This is better, and signifigantly less bug prone, but there's still a lot of boilerplate code that needs to be written.

Here's the thing: at it's core, some types (like json_value) are best expressed as sum types! Anything we write to wrap one will just be a specialization of a sum type, and will usually involve a lot of boilerplate code to do the wrapping.

At this point, it might be prudent to ask: can we define json_value directly as a std::variant? Would a recursive using declaration work? I wish it did. I really, really wish it did.

// LIES!!! This code doesn't work
// error: use of undeclared identifier 'json_value'
using json_value = std::variant<
    std::nullptr_t,                          // json null
    bool,                                    // json boolean
    double,                                  // json number
    std::string,                             // json string
    std::map<std::string, json_value>,       // json object
    std::vector<json_value>>;                // json array

The Recursive Variant Authority provides a complete solution!

rva::variant allows you to write recursive variants without any boilerplate by passing rva::self_t in the places where you want your recursive type to go! When you write a statement like this, rva::variant will replace instances of rva::self_t with a properly specified instance of it's type, and it does this as a paper-thin wrapper over std::variant that provides all your boilerplate code for you. And there was a lot of boilerplate code to write.

using json_value = rva::variant<
    std::nullptr_t,                       // json null
    bool,                                 // json boolean
    double,                               // json number
    std::string,                          // json string
    std::map<std::string, rva::self_t>,   // json object, type is std::map<std::string, json_value>
    std::vector<rva::self_t>>;            // json array, type is std::vector<json_value>

rva::variant provides the full set of functionality given by std::variant, including:

  • visit,
  • get,
  • get_if,
  • holds_alternative,
  • std::variant_size,
  • std::variant_alternative,
  • std::hash)

And it does so as a drop-in replacement (or as close to one as the standard would allow)!

The Recursive Variant Authority hopes that you enjoy your time using rva::variant, and we encourage you to make full use of it's capabilities when writing your code.

Usage & Installation

The most straight-forward way to use rva::variant is by using CMake's FetchContent interface to find and fetch the library:

FetchContent_Declare(
    rva
    GIT_REPOSITORY https://github.com/codeinred/recursive-variant.git
    GIT_TAG        main
)
FetchContent_MakeAvailable(rva)

Alternatively, you can install it as a CMake package like so. Please note that it's not necessary to build it in release mode, as it's a header-only library.

git clone https://github.com/codeinred/recursive-variant.git rva
cd rva
cmake -B build -DBUILD_TESTING=OFF
cmake --build build
sudo cmake --install build

Once installed, the library can then be discovered as a CMake package:

find_package(rva REQUIRED)

In either case, whether obtained via FetchContent, or installed as a package, you can use it via target_link_libraries. The library is header-only, but this will ensure that it's added to the include path for that target.

target_link_libraries(<your target> PRIVATE rva::rva)

Running tests

You may have noticed that the installation process "built" the library with testing off. Installing the library doesn't require running tests, however if you wish to run them, you may do so by ommitting the flag disabling testing, and then running build/test_rva -s. Testing is done via the Catch2 Testing framework. You will see a lot of {?} in the test output, but that's just because Catch2 doesn't know how to print a variant.

Tests may be found in the test/ directory.

git clone https://github.com/codeinred/recursive-variant.git rva
cd rva
cmake -B build
cmake --build build -j 8
build/test_rva -s
Owner
Alecto Irene Perez
Undergrad at UNM; interested in Web Development, Modern C++, Haskell, and Machine Learning
Alecto Irene Perez
Similar Resources

Extension types for geospatial data for use with 'Arrow'

geoarrow The goal of geoarrow is to prototype Arrow representations of geometry. This is currently a first-draft specification and nothing here should

Sep 15, 2022

Strong type - C++ implementation of strong types

strong_type C++ implementation of strong types Build Status Linux (gcc-8, clang-8) / OSX Table of contents Table of contents What is this ? A tour of

Sep 9, 2022

General purpose power controller, capable of driving soldering irons using different voltages and probe types.

General purpose power controller, capable of driving soldering irons using different voltages and probe types.

All-purpose Power Micro Controller This general purpose power micro controller features: Wheatstone Bridge front-end New Texas Instruments INA823 inst

Sep 14, 2022

std::tuple like methods for user defined types without any macro or boilerplate code

Boost.PFR This is a C++14 library for very basic reflection that gives you access to structure elements by index and provides other std::tuple like me

Sep 16, 2022

By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps are generated.(including broken line graph,histogram and curve graph)

Auto-drawing-speed-range-map By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps a

May 14, 2022

Node1D and other 1-dimensional node types for making 1D games in Godot.

Node1D and other 1-dimensional node types for making 1D games in Godot.

Godot 1D Node1D and other 1-dimensional node types for making 1D games in Godot. Have you ever wanted to make 1D games in Godot? ...no? You say you ha

Jul 31, 2022

Tools for working with Wwise file types (only extraction at the moment)

Wwise Audio Tools This repository is for a static and dynamic library as well as a simple command line tool used to convert Wwise WEM files to OGG fil

May 26, 2022

SSD1306 library and simple graphics core library based on Adafruit GFX Library.

Raspberry Pico SSD1306 + GFX Library Based on Adafruit GFX Library https://github.com/adafruit/Adafruit-GFX-Library Usage Hardware Connect your SSD130

Sep 1, 2022

A simple implementation of a parser and its use to calculate simple mathematical expressions

Calculator C Parser A simple implementation of a parser and its use to calculate simple mathematical expressions I haven't written a detailed descript

Nov 8, 2021
Comments
  • can we change it to support define a List?

    can we change it to support define a List?

    For example, a list can be defined in Haskell as List a = Nil | Cons a (List a), can we support it by changing std::tuple and std::variant? Going a step further, can we do it at zero cost?

Minimal library to Visualize C++ recursive functions using graphviz.

VGraph Minimal library to Visualize C++ recursive functions using graphviz. dependencies It needs the graphviz to be additionaly installed. specifical

Dec 25, 2021
Any - A simple variant type for C++

ANY Variant type for C++ This is similar to Boost.Any in that any type can be encapsulated and retrieved, but this implementation does not have any de

Oct 24, 2020
rax/RAX is a C++ extension library designed to provide new, fast, and reliable cross-platform class types.

rax rax/RAX is a C++ extension library designed to provide cross-platform new, fast, and reliable class types for different fields such as work with I

May 2, 2022
Tiny - low-level library for minimizing the size of your types
Tiny - low-level library for minimizing the size of your types

foonathan/tiny Note: This project is currently WIP, no guarantees are made until an 0.1 release. This project is a C++11 library for putting every las

Jul 30, 2022
high performance C++20 implementation of std::variant

A minimal compile-time overhead, C++20 implementation of std::variant. Fully standard conforming with a couple of documented differences.

Sep 16, 2022
A cleaner and more intuitive std::variant alternative

[WIP] ExtendedVariant This single header library is part of my C++ extended standard stdex libraries. Check our my profile for more. Working with C++

Jun 13, 2021
EDK2 port for Lumia 630 & it's 512mb variants. 1gb variant coming soon.

Lumia930Pkg WIP Custom ARM UEFI firmware for Lumia930 Current Status EMMC MMU PMIC GPIO Working Linux Notes Linux kernel do boots but crashes pretty s

Jan 2, 2022
A refactored Proof-of-concept originally developed in 2017 to print all function calls with their arguments data types and values using Ptrace during program execution.

print-function-args-debugger A refactored Proof-of-concept originally developed in 2017 to print all function calls with their arguments data types an

Jun 17, 2022
USENIX 2021 - Nyx: Greybox Hypervisor Fuzzing using Fast Snapshots and Affine Types
USENIX 2021 - Nyx: Greybox Hypervisor Fuzzing using Fast Snapshots and Affine Types

Nyx: Greybox Hypervisor Fuzzing using Fast Snapshots and Affine Types Nyx is fast full-VM snapshot fuzzer for type-2 hypervisors. It's built upon kAFL

Aug 29, 2022
"SaferCPlusPlus" is essentially a collection of safe data types intended to facilitate memory and data race safe C++ programming

A collection of safe data types that are compatible with, and can substitute for, common unsafe native c++ types.

Sep 21, 2022