DEV Community: weiqiang.shan

Proof for Floyd’s tortoise and hare

weiqiang.shan — Sun, 17 Aug 2025 01:22:46 +0000

Type systems: Part III Json

weiqiang.shan — Sun, 10 Aug 2025 01:22:46 +0000

Previously:

Now:

json itself is a kind of data format, NOT type format. To operate on json, we need a type format, which is the program to operate json data. This program might be a dynamic typing system, like nolmann::json or static typing system, for example a program that can only parse data that are of specific json format.
json schema can be loosely compared with type, since a json schema actually defines a class of json data format, like what the type does
Since user directly write json data, which means that the format is inherently dynamic, so json inherently needs a dynamic type system to represent json data. Of course, static type system can also be used, but this requires that the user write the json data with fixed format, otherwise, the parse will fail.
nlohmann::json is a dynamic typing system to represent json. It’s dynamic in the sense of that it can represent any json, but itself is static. All programs are static in the low level, dynamic only are acheived through static programs. To dynamically support json data format, nlohmann::json combines underlying type format and dynamic typing sytem into one, and also support compile time conversion with user type through C++ meta-programming.

This is a json file. It’s a data format, meaning that this is a piece of data. It is unique and can not have any other instantiation.

{
    "MyMessage": [
        {
            "name": "weiqiang.shan"
        },
        {
            "age": 18
        },
        23,
        "Hello"
    ]
}

This is a json schema. It describes one kind of json data. This schema can have many json data instantiations, like above json file. It works like a type. But it is not actually a type, since there is no type name. It is just a descriptor of what should a json data look like, what attributes json data should have, etc. It does not define a generalized type that can be reused with a type name.

{
  "$schema": "http://json-schema.org/draft-07/schema#",
  "type": "object",
  "properties": {
    "MyMessage": {
      "type": "array",
      "minItems": 4,
      "maxItems": 4,
      "items": [
        {
          "type": "object",
          "properties": {
            "name": {
              "type": "string"
            }
          },
          "required": ["name"],
          "additionalProperties": false
        },
        {
          "type": "object",
          "properties": {
            "age": {
              "type": "number"
            }
          },
          "required": ["age"],
          "additionalProperties": false
        },
        {
          "type": "number"
        },
        {
          "type": "string"
        }
      ]
    }
  },
  "required": ["MyMessage"],
  "additionalProperties": false
}

This is a mirror protobuf definition for above json schema. It can be used to represent above json data. If we use this protobuf definiton to write a program, we build a static typing system for above json schema, which can only parse this kind of json data. Unlike json schema, every type has a name, which can be used to instantiate type instance and can be reused.

syntax = "proto3";

package tmp;

// Message representing the root object
message RootMessage {
  repeated MyMessageItem MyMessage = 1;
}

// Union type to represent the mixed array items
message MyMessageItem {
  oneof value {
    NameObject name_value = 1;
    AgeObject age_value = 2;
    int32 number_value = 3;
    string string_value = 4;
  }
}

// Object with name property
message NameObject {
  string name = 1;
}

// Object with age property  
message AgeObject {
  int32 age = 1;
}

This is how the nlohmann::json dynamically represents all json data. At it’s core, it actually is a type erasure system. All json data, whether it’s numbers, strings, binary, object , list are type erased and be represent using one single type. Type erasure happens during construction, when the binding of constructor and destructor is finished, through value_t, which is enum to represent type of json data. Different value_t will be created and destructed differently. This is the core idea of type erasure: hide specific type information in implementation, while in the interface expose unified type representation and complete the binding during construction..

    /*!
    @brief a JSON value

    The actual storage for a JSON value of the @ref basic_json class. This
    union combines the different storage types for the JSON value types
    defined in @ref value_t.

    JSON type | value_t type | used type
    --------- | --------------- | ------------------------
    object | object | pointer to @ref object_t
    array | array | pointer to @ref array_t
    string | string | pointer to @ref string_t
    boolean | boolean | @ref boolean_t
    number | number_integer | @ref number_integer_t
    number | number_unsigned | @ref number_unsigned_t
    number | number_float | @ref number_float_t
    binary | binary | pointer to @ref binary_t
    null | null | *no value is stored*

    @note Variable-length types (objects, arrays, and strings) are stored as
    pointers. The size of the union should not exceed 64 bits if the default
    value types are used.

    @since version 1.0.0
    */
    union json_value
    {
        /// object (stored with pointer to save storage)
        object_t* object;
        /// array (stored with pointer to save storage)
        array_t* array;
        /// string (stored with pointer to save storage)
        string_t* string;
        /// binary (stored with pointer to save storage)
        binary_t* binary;
        /// boolean
        boolean_t boolean;
        /// number (integer)
        number_integer_t number_integer;
        /// number (unsigned integer)
        number_unsigned_t number_unsigned;
        /// number (floating-point)
        number_float_t number_float;

        /// default constructor (for null values)
        json_value() = default;
        /// constructor for booleans
        json_value(boolean_t v) noexcept : boolean(v) {}
        /// constructor for numbers (integer)
        json_value(number_integer_t v) noexcept : number_integer(v) {}
        /// constructor for numbers (unsigned)
        json_value(number_unsigned_t v) noexcept : number_unsigned(v) {}
        /// constructor for numbers (floating-point)
        json_value(number_float_t v) noexcept : number_float(v) {}
        /// constructor for empty values of a given type
        json_value(value_t t)
        {
            switch (t)
            {
                case value_t::object:
                {
                    object = create<object_t>();
                    break;
                }

                case value_t::array:
                {
                    array = create<array_t>();
                    break;
                }

                case value_t::string:
                {
                    string = create<string_t>("");
                    break;
                }

                case value_t::binary:
                {
                    binary = create<binary_t>();
                    break;
                }

                case value_t::boolean:
                {
                    boolean = static_cast<boolean_t>(false);
                    break;
                }

                case value_t::number_integer:
                {
                    number_integer = static_cast<number_integer_t>(0);
                    break;
                }

                case value_t::number_unsigned:
                {
                    number_unsigned = static_cast<number_unsigned_t>(0);
                    break;
                }

                case value_t::number_float:
                {
                    number_float = static_cast<number_float_t>(0.0);
                    break;
                }

                case value_t::null:
                {
                    object = nullptr; // silence warning, see #821
                    break;
                }

                case value_t::discarded:
                default:
                {
                    object = nullptr; // silence warning, see #821
                    if (JSON_HEDLEY_UNLIKELY(t == value_t::null))
                    {
                        JSON_THROW(other_error::create(500, "961c151d2e87f2686a955a9be24d316f1362bf21 3.11.3", nullptr)); // LCOV_EXCL_LINE
                    }
                    break;
                }
            }
        }

        /// constructor for strings
        json_value(const string_t& value) : string(create<string_t>(value)) {}

        /// constructor for rvalue strings
        json_value(string_t&& value) : string(create<string_t>(std::move(value))) {}

        /// constructor for objects
        json_value(const object_t& value) : object(create<object_t>(value)) {}

        /// constructor for rvalue objects
        json_value(object_t&& value) : object(create<object_t>(std::move(value))) {}

        /// constructor for arrays
        json_value(const array_t& value) : array(create<array_t>(value)) {}

        /// constructor for rvalue arrays
        json_value(array_t&& value) : array(create<array_t>(std::move(value))) {}

        /// constructor for binary arrays
        json_value(const typename binary_t::container_type& value) : binary(create<binary_t>(value)) {}

        /// constructor for rvalue binary arrays
        json_value(typename binary_t::container_type&& value) : binary(create<binary_t>(std::move(value))) {}

        /// constructor for binary arrays (internal type)
        json_value(const binary_t& value) : binary(create<binary_t>(value)) {}

        /// constructor for rvalue binary arrays (internal type)
        json_value(binary_t&& value) : binary(create<binary_t>(std::move(value))) {}

        void destroy(value_t t)
        {
            if (
                (t == value_t::object && object == nullptr) ||
                (t == value_t::array && array == nullptr) ||
                (t == value_t::string && string == nullptr) ||
                (t == value_t::binary && binary == nullptr)
            )
            {
                //not initialized (e.g. due to exception in the ctor)
                return;
            }
            if (t == value_t::array || t == value_t::object)
            {
                // flatten the current json_value to a heap-allocated stack
                std::vector<basic_json> stack;

                // move the top-level items to stack
                if (t == value_t::array)
                {
                    stack.reserve(array->size());
                    std::move(array->begin(), array->end(), std::back_inserter(stack));
                }
                else
                {
                    stack.reserve(object->size());
                    for (auto&& it : *object)
                    {
                        stack.push_back(std::move(it.second));
                    }
                }

                while (!stack.empty())
                {
                    // move the last item to local variable to be processed
                    basic_json current_item(std::move(stack.back()));
                    stack.pop_back();

                    // if current_item is array/object, move
                    // its children to the stack to be processed later
                    if (current_item.is_array())
                    {
                        std::move(current_item.m_data.m_value.array->begin(), current_item.m_data.m_value.array->end(), std::back_inserter(stack));

                        current_item.m_data.m_value.array->clear();
                    }
                    else if (current_item.is_object())
                    {
                        for (auto&& it : *current_item.m_data.m_value.object)
                        {
                            stack.push_back(std::move(it.second));
                        }

                        current_item.m_data.m_value.object->clear();
                    }

                    // it's now safe that current_item get destructed
                    // since it doesn't have any children
                }
            }

            switch (t)
            {
                case value_t::object:
                {
                    AllocatorType<object_t> alloc;
                    std::allocator_traits<decltype(alloc)>::destroy(alloc, object);
                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, object, 1);
                    break;
                }

                case value_t::array:
                {
                    AllocatorType<array_t> alloc;
                    std::allocator_traits<decltype(alloc)>::destroy(alloc, array);
                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, array, 1);
                    break;
                }

                case value_t::string:
                {
                    AllocatorType<string_t> alloc;
                    std::allocator_traits<decltype(alloc)>::destroy(alloc, string);
                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, string, 1);
                    break;
                }

                case value_t::binary:
                {
                    AllocatorType<binary_t> alloc;
                    std::allocator_traits<decltype(alloc)>::destroy(alloc, binary);
                    std::allocator_traits<decltype(alloc)>::deallocate(alloc, binary, 1);
                    break;
                }

                case value_t::null:
                case value_t::boolean:
                case value_t::number_integer:
                case value_t::number_unsigned:
                case value_t::number_float:
                case value_t::discarded:
                default:
                {
                    break;
                }
            }
        }
    };

Type systems: Part IV Python

weiqiang.shan — Sun, 10 Aug 2025 01:22:46 +0000

Previously:

Now:

PyTypeObject

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

_PyObject_HEAD_EXTRA macro: pointers that points to previous PyObject and next PyObject
ob_refcnt: reference counter
ob_type: type of current PyObject instance

The PyTypeObject is the most important type in Python implementation that enables dynamic typing. Type erasure is achieved through this type. See the C-API for CPython. The most important thing that this type object contains are function pointers, which are responsible for various operations on instances of this type: allocation, deallocation, hash, etc. This is exactly where the type erasure happens: binding of function pointers during construction and hide detailed operation inside implementation. Once the binding is finished, an instance, even it’s Python variable, it’s type is fixed, the functions that used to operate on this instance is fixed, until it’s destruction. Even though this Python variable can be bind to another Python instance, might be a different typed instance, but the underlying PyObject’s type is fixed. Compare this with std::function:

std::function variable can be used to bind to different typed callables, underneath std::function keeps different function pointers that implement these callables.
std::function variable can be reassigned to another callable with the same signature, with the previous callable properly deallocated by it’s bound deallocators and with new instance + new set of function pointers kept inside the same std::function

Python’s dynamic typing works very much like std::function, using type erasure technique. A PyTypeObject is itself a PyObject instance at runtime.

When a new object is created, its ob_type is set to the appropriate PyTypeObject( binding during construction, as in type erasure ). For example:

A list object has ob_type set to &PyList_Type. An integer object has ob_type set to &PyLong_Type. For custom types, you define a PyTypeObject and set the object’s ob_type to point to it.

ob_type is used for type checking functions like isinstance(obj, cls) and issubclass(cls1, cls2). For instance, PyObject_IsInstance(inst, cls) checks if inst->ob_type is cls or if cls is in the base classes of inst->ob_type. This is supported by Python C API: Object Protocol, which lists functions like PyObject_IsInstance and P_IsSubclass, relying on the type hierarchy defined by tp_base and tp_bases in PyTypeObject.

When an operation is performed on an object, Python uses ob_type to find the appropriate function pointers in the PyTypeObject. For example: Calling len() on a list uses list->ob_type->tp_as_sequence->sq_length.

While possible, changing ob_type (e.g., via class assignment) is restricted. From Python C API: Type Objects, it’s noted that class assignment is only supported for mutable types or ModuleType subclasses, to prevent crashes or undefined behavior:

# Class definion in Python actually will instantiate a PyTypeObject
# instance in C during runtime. It is also a PyObject instance and
# have the same lifetime management with other Python instances.
# When this type is not used anymore, it is deallocated. When defined
# this type belongs to a module, tmp.py, and it is reference by this
# module.
class MyClass:
    class_var = 10

    def __init__ (self, x):
        self.x = x

    def method(self):
        print(f"Original method, class_var={self.class_var}")

# Create an instance using this type. This instance is also
# a PyObject and add one more reference count to MyClass's
# PyTypeObject. The type binding happens here during instance
# construction.
obj = MyClass(5)
obj.method() # Outputs: Original method, class_var=10

# Redefine the class. This creates a new PyTypeObject instance and
# makes the original MyClass's reference count one less count. Since
# Now tmp.py module has a new MyClass type. But the original MyClass
# is still in memory, because the obj instance still refers to it.
class MyClass:
    class_var = 20

    def __init__ (self, x, y):
        self.x = x
        self.y = y

    def method(self):
        print(f"New method, class_var={self.class_var}")

# Check existing instance. obj still use the original MyClass, since
# the binding is not changed.
obj.method() # Outputs: Original method, class_var=10

# Create a new instance. Now the new MyClass is used, since inside
# module tmp.py, the MyClass now is the new PyTypeObject.
new_obj = MyClass(5, 10)
new_obj.method() # Outputs: New method, class_var=20

def m(self, sec):
    print("New individual method")

# We can change the class attributes like any other python instance
# Underneath, a type in Python is just a PyTypeObject in C.
MyClass.method = m
# error
# new_obj.method("dummy")
new_obj.method("dummy")

# This is dangerous!! Since it will reduce reference count of the
# orinal MyClass object(class are also runtime PyObject instances)
# to zero, and it will be freed from memory. This will change the
# type of obj, which determines member function poitners,
# destructor pointers, etc, hence create a inconsistency between
# obj's memory and it's type, since it's memory is created by the
# original MyClass type.
obj. __class__ = MyClass
print(obj.class_var)

Inheritence

The PyTypeObject structure contains fields that implement inheritance:

typedef struct _typeobject {
    PyObject_VAR_HEAD
    const char *tp_name; /* For printing, in format "<module>.<name>" */
    Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */

    /* Methods to implement standard operations */
    destructor tp_dealloc;
    printfunc tp_print;
    getattrfunc tp_getattr;
    setattrfunc tp_setattr;
    PyAsyncMethods *tp_as_async; /* formerly known as tp_compare (Python 2) or tp_reserved (Python 3) */
    reprfunc tp_repr;

    /* Method suites for standard classes */
    PyNumberMethods *tp_as_number;
    PySequenceMethods *tp_as_sequence;
    PyMappingMethods *tp_as_mapping;

    /* More standard operations (here for binary compatibility) */
    hashfunc tp_hash;
    ternaryfunc tp_call;
    reprfunc tp_str;
    getattrofunc tp_getattro;
    setattrofunc tp_setattro;

    /* Functions to access object as input/output buffer */
    PyBufferProcs *tp_as_buffer;

    /* Flags to define presence of optional/expanded features */
    unsigned long tp_flags;

    const char *tp_doc; /* Documentation string */

    /* call function for all accessible objects */
    traverseproc tp_traverse;

    /* delete references to contained objects */
    inquiry tp_clear;

    /* rich comparisons */
    richcmpfunc tp_richcompare;

    /* weak reference enabler */
    Py_ssize_t tp_weaklistoffset;

    /* Iterators */
    getiterfunc tp_iter;
    iternextfunc tp_iternext;

    /* Attribute descriptor and subclassing stuff */
    struct PyMethodDef *tp_methods;
    struct PyMemberDef *tp_members;
    struct PyGetSetDef *tp_getset;
    struct _typeobject *tp_base;
    PyObject *tp_dict;
    descrgetfunc tp_descr_get;
    descrsetfunc tp_descr_set;
    Py_ssize_t tp_dictoffset;
    initproc tp_init;
    allocfunc tp_alloc;
    newfunc tp_new;
    freefunc tp_free; /* Low-level free-memory routine */
    inquiry tp_is_gc; /* For PyObject_IS_GC */
    PyObject *tp_bases;
    PyObject *tp_mro; /* method resolution order */
    PyObject *tp_cache;
    PyObject *tp_subclasses;
    PyObject *tp_weaklist;
    destructor tp_del;

    /* Type attribute cache version tag. Added in version 2.6 */
    unsigned int tp_version_tag;

    destructor tp_finalize;

} PyTypeObject;

The key fields for inheritance are:

tp_base: Points to the immediate base class(PyTypeObject)
tp_bases: Tuple of all base classes(PyTypeObject)
tp_mro: Method Resolution Order tuple

When you define a class in Python:

class Child(Parent):
    pass

The Python runtime:

Creates a new PyTypeObject for Child
Sets Child->tp_base to point to Parent’s PyTypeObject
Sets Child->tp_bases to a tuple containing Parent’s PyTypeObject
Computes the MRO (Method Resolution Order) and stores it in Child->tp_mro

Inheritence enable current class inherit attributes from it’s base classes:

Class (PyTypeObject)
    tp_base → Parent Class (PyTypeObject)
    tp_bases → (Parent1, Parent2, ...) (PyTypeObject)
    tp_mro → (Class, Parent1, Parent2, ..., object)
    tp_dict → {attribute_name: attribute_value, ...}
    tp_new, tp_init, tp_dealloc → function pointers

Metaclasses

Metaclasses are also PyTypeObject instances. When you define a metaclass:

class Meta(type):
    pass

class MyClass(metaclass=Meta):
    pass

The relationship is:

MyClass.ob_type points to Meta’s PyTypeObject
Meta.ob_type points to type’s PyTypeObject (since Meta inherits from type)
type.ob_type points to itself (since type is its own metaclass)

metaclass are classes that inherits from type, since type is a PyObject that can create PyTypeObject, which are classes:

Instance (PyObject)
    ob_type → Class (PyTypeObject)
        ob_type → Metaclass (PyTypeObject)  
            ob_type → type (PyTypeObject)
                ob_type → type (self-referential)

Every PyObject only have one ob_type pointer, hence can only point to one metaclass :

class Meta1(type):
    pass

class Meta2(type):
    pass

# SyntaxError: keyword argument repeated: metaclass
class MyClass(metaclass=Meta1, metaclass=Meta2):
    pass

metaclass support inheritence:

class MetaBase(type):
    def __new__ (cls, name, bases, namespace):
        print(f"MetaBase. __new__ : {name}")
        namespace['base_attr'] = 'from_meta_base'
        return super(). __new__ (cls, name, bases, namespace)

class MetaMiddle(MetaBase):
    def __new__ (cls, name, bases, namespace):
        print(f"MetaMiddle. __new__ : {name}")
        namespace['middle_attr'] = 'from_meta_middle'
        return super(). __new__ (cls, name, bases, namespace)

class MetaTop(MetaMiddle):
    def __new__ (cls, name, bases, namespace):
        print(f"MetaTop. __new__ : {name}")
        namespace['top_attr'] = 'from_meta_top'
        return super(). __new__ (cls, name, bases, namespace)

class MyClass(metaclass=MetaTop):
    pass

# Output:
# MetaBase. __new__ : MyClass
# MetaMiddle. __new__ : MyClass  
# MetaTop. __new__ : MyClass

print(MyClass.base_attr) # 'from_meta_base'
print(MyClass.middle_attr) # 'from_meta_middle'
print(MyClass.top_attr) # 'from_meta_top'

At C level:

MyClass.ob_type → MetaTop's PyTypeObject
    ob_type → MetaMiddle's PyTypeObject
        ob_type → MetaBase's PyTypeObject
            ob_type → type's PyTypeObject
                ob_type → type's PyTypeObject (self-referential)

Both inheritence and metaclass can add attributes to a class, but they work at totally different level:

Inheritence only inherit attributes from it’s parents
Metaclass directly operate on class’s attributes, during class creation

class Meta(type):
    def __new__ (cls, name, bases, namespace):
        print(f"Metaclass executing during class creation")
        namespace['meta_attr'] = 'added by metaclass'
        return super(). __new__ (cls, name, bases, namespace)

class Base:
    base_attr = 'inherited from base'
    def __init__ (self):
        print("Base class executing during instance creation")

# Metaclass executes NOW (during class definition)
class MyClass(Base, metaclass=Meta):
    pass

# Base class attributes are already available
print(MyClass.meta_attr) # 'added by metaclass'
print(MyClass.base_attr) # 'inherited from base'

Metaclass can directly operate on the raw namespace of the class type: namespace. Inheritence only inherit attributes from base classes through inheritence lookup:

Metaclass creates class just like anyother PyTypeObject create instances, internally it’s type erasure and once instances are created, the binding is fixed, attributes are added permanently on this class.
Inheritence is just pointers to parent classes, they can be changed dynamically.

Memory in inheritence

When a class has parents, all parents attributes and the child class attributes are stored in one single dictionary:

class Parent:
    def __init__ (self):
        self.a = 1

class Child(Parent):
    def __init__ (self):
        super(). __init__ ()
        self.b = 2

c = Child()


>>> c. __dict__
{'a': 1, 'b': 2}

You can’t quite do a true C++-style “object slicing” in Python, because Python doesn’t physically store a separate “Parent object” inside a “Child object.”

In Python:

c is the Child instance.
The “Parent part” isn’t a separate object — it’s just that Child inherits the methods and attributes of Parent.
When you call a Parent method on c, Python simply follows the Method Resolution Order (MRO) to find that method in Parent, but still passes the same c object as self.

class Parent:
    def p_method(self):
        print("Parent method, self is:", self)

class Child(Parent):
    def c_method(self):
        print("Child method, self is:", self)

c = Child()
c.p_method() # Works — no casting needed


Parent method, self is: < __main__.Child object at 0x10100dbe0>

Type Erasure Part Three: The Downside

weiqiang.shan — Tue, 08 Jul 2025 17:00:00 +0000

I talk about two drawbacks about type erasure: confusing type erasure with object slicing and the need for manual memory management.

Confused with Object slicing

Object slicing is a different concept. However, it can be confused with type erasure:

class A {
public:
    virtual void foo() { std::cout << "A::foo()" << std::endl; }
    int data_a = 1;
};

class B : public A {
public:
    virtual void foo() override { std::cout << "B::foo()" << std::endl; }
    int data_b = 2;
};

std::vector<A> vec;
B b;
vec.push_back(b); // Object slicing occurs here

Above example has a false indication that std::vector<A> can both store objects of type A and type B. That’s not true, since all objects of B is sliced to become A. What if we use std::vector<std::shared_ptr<A>>? Does this avoid object slicing? The answer is yes and no, because of the resources leakage problem. The final puzzle is a virtual destructor. Let em summarize all possible scenarios:

Stored as	vdtor	not vdtor
Objects	[1]	[2]
Pointers	[3]	[4]

Before going deeper, we first clarify one important point: the memories that are allocated during object creation, new operation, will be freed during using delete, whether it is called manually, or by other means(std::shared_ptr will call delete for us). Those memory size are stored in metadata during new. This means if we using new to allocate a object A, then cast it to B, then delete B’s pointer, the delete will free the size allocated during new, not caring about B’s impact, which will have many implications. We here differentiate two types of resources:

Memory blocks allocated using new, we call it memory block.
Other resources managed by the object itself, we call it dynamic resources, such as heap memories, file descriptors.

Ok now let’s discuss one by one:

Stored as objects and with virtual destructors: object slicing happens. The derived class’s destructor will be called on the sliced object and delete operator will also operate on the sliced object, both of which are undefined behavior due to the memory slicing.
Stored as objects and without virtual destructors: object slicing happens. The base class’s destructor will be called on the sliced object, which is ok. But the dynamic resoruces managed by the derived class will be not released. delete operator will operate on sliced objects, which is UB.
Stored as pointers and with virtual destructor: everything is ok. delete will free memory block and virtual destructor will properly manage dynamic resources.
Stored as pointers and without virtual destructor: delete will work fine since there are no object slicing. But the dynamic resources managed by the derived class will not be properly released.

The only way is to store a pointer and use virtual destructor. The virtual destructor is not the same as other virtual functions. It will always be called during destruction phase, so it must be implemented, even it is a pure virtual function. The virtual property of destructor assures that the derived class’s destructor always be called, hence release the relvent dynamic resources.

Manual Memory Management

Due to the fact that type is erased, what if user wants to copy, create, move a type erased object? With type information these can be done easily, but with type erased, we do not know the exct type anymore. So we have to manually create these operations. Here is an example:

#include <iostream>
#include <vector>

// Example classes to test with
class A {
public:
    void foo() { std::cout << "A::foo()" << std::endl; }
};

class B {
public:
    void foo() { std::cout << "B::foo()" << std::endl; }
};

class TypeErased {
    struct Concept {
        virtual ~Concept() = default;
        virtual void foo() = 0;
        virtual Concept* clone() const = 0;
    };

    template<typename T>
    struct Model : Concept {
        T data;
        Model(T x) : data(std::move(x)) {}
        void foo() override { data.foo(); }
        Concept* clone() const override { 
            return new Model(data);
        }
    };

    Concept* ptr;

public:
    // Constructor
    template<typename T>
    TypeErased(T x) : ptr(new Model<T>(std::move(x))) {}

    // Destructor
    ~TypeErased() { 
        delete ptr; 
    }

    // Copy Constructor
    TypeErased(const TypeErased& other) : ptr(other.ptr->clone()) {}

    // Copy Assignment Operator
    TypeErased& operator=(const TypeErased& other) {
        if (this != &other) {
            delete ptr;
            ptr = other.ptr->clone();
        }
        return *this;
    }

    // Move Constructor
    TypeErased(TypeErased&& other) noexcept : ptr(other.ptr) {
        other.ptr = nullptr;
    }

    // Move Assignment Operator
    TypeErased& operator=(TypeErased&& other) noexcept {
        if (this != &other) {
            delete ptr;
            ptr = other.ptr;
            other.ptr = nullptr;
        }
        return *this;
    }

    // Member function
    void foo() { ptr->foo(); }
};

int main() {
    std::cout << "=== Testing all special member functions ===" << std::endl;

    // Constructor
    TypeErased obj1(A{});
    std::cout << "obj1: ";
    obj1.foo();

    // Copy Constructor
    TypeErased obj2(obj1);
    std::cout << "obj2 (copy of obj1): ";
    obj2.foo();

    // Copy Assignment
    TypeErased obj3(B{});
    std::cout << "obj3: ";
    obj3.foo();

    obj3 = obj1; // Copy assignment
    std::cout << "obj3 (after copy assignment): ";
    obj3.foo();

    // Move Constructor
    TypeErased obj4(std::move(obj2));
    std::cout << "obj4 (moved from obj2): ";
    obj4.foo();

    // Move Assignment
    TypeErased obj5(B{});
    std::cout << "obj5: ";
    obj5.foo();

    obj5 = std::move(obj4); // Move assignment
    std::cout << "obj5 (after move assignment): ";
    obj5.foo();

    // Test with containers
    std::vector<TypeErased> vec;
    vec.push_back(A{}); // Uses move constructor
    vec.push_back(B{}); // Uses move constructor

    std::cout << "\nVector elements:" << std::endl;
    for (auto& item : vec) {
        item.foo();
    }

    return 0;
}

In this example, both type A and type B provides foo method, we use the TypeErased to erase the type information, user does not need to know A or B, or anyother classes that have method foo.

Type Erasure Part Two: How std::function Works

weiqiang.shan — Sun, 29 Jun 2025 02:00:00 +0000

std::function Implementation:

Inherits _Function_base to get the storage, responsible for data, itself contains _M_invoker:

_M_functor : A union structure that stores actual callable, might be pointer or heap allocated callable objects. The _M_init_functor will move __f, the callable to be stored in _M_functor
_M_manager : A function pointer in _Function_handler to create/destroy/… the _M_functor
_M_invoker : A function pointer in _Function_handler to call the callable
&_My_handler::_M_invoke/&_My_handler::_M_manager : Static functions bound with _Functor type providing clone/destroy operations, which operates on the stored callable object. So the stored callable must be compatible with those static function pointers, which is done during construction.

Points to _Function_handler type that do the type erasure of the passed actual callable type, responsible for code

After construction, the binding is fixed to a specific _functor, aka user callable. Even though std::function’s type is only determined by callable signature, _Function_handler’s type is also determined by the actual callable type that is passed by user during construction.

The binding between data and code is done at construction phase at compile time. If we assign a std::function variable to another instance, the data and code must be both changed at the same time, which is done during run time (using the swap(...) member function). This data and code binding pattern happens for all methods of implementing type erasure:

Virtual classes are bound to their vtable during compile time
Statically generated template functions (or user written functions implementing type erasure) bind data and code at compile time

This data and code binding during compile time is at the core of how type erasure works, since only after the binding, type can be erased.

Type systems: Part II Protobuf Reflection

weiqiang.shan — Sat, 14 Jun 2025 01:22:46 +0000

Previously:

Type systems: Part I

GPB Workflow

The main workflow starts from proto definition files and the static interpreter protoc compiler will compile them into C++ types, which user will use directly. The process can be illustrated like following:

The main design pattern of GPB is static generation plus type erasure in C++. All user-defined specific types inherit from the Message base type. All user-defined type information, like field name, field type, message name, field offsets are statically generated and stored in protoc-generated C++ files. During runtime, before main, those information will be registered into global DescriptorPool.

How reflection work

The message creation is based on type erasure. Member access is based on static offset information and type descriptor information. Dynamic type creation is based on DynamicMessage type.

When user calls MessageFactory::generated_factory()->GetPrototype(descriptor)->New(), GPB returns a Message type. Underneath this virtual type, there are two possibilities:

The protoc-generated C++ type, which is specific C++ type, and the returned Message type can be cast to it dynamically.
DynamicMessage type, which is constructed at runtime by protobuf library.

Code demo

Here I did a demonstration about protocol buffers advanced usage, the whole code can be found at protobuf reflection code demo.

#include "my_message.pb.h" // Generated by protoc
#include <absl/strings/string_view.h>
#include <google/protobuf/compiler/importer.h>
#include <google/protobuf/compiler/parser.h>
#include <google/protobuf/descriptor.pb.h>
#include <google/protobuf/dynamic_message.h>
#include <google/protobuf/text_format.h>
#include <iomanip>
#include <iostream>
#include <memory>

using namespace std;

// Custom SourceTree for in-memory .proto files
class MemorySourceTree : public google::protobuf::compiler::SourceTree {
public:
  MemorySourceTree(const std::string &name, const std::string &content)
      : filename_(name), content_(content) {}

  google::protobuf::io::ZeroCopyInputStream *
  Open(absl::string_view filename) override {
    if (filename != filename_)
      return nullptr;
    return new google::protobuf::io::ArrayInputStream(
        content_.data(), static_cast<int>(content_.size()));
  }

private:
  std::string filename_;
  std::string content_;
};

int main() {
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  // ============================================
  // Section 1: Static Message Creation
  // Demonstrates creating a message using the generated C++ class
  // This is the most common and straightforward way to use protobuf
  // ============================================
  test::MyMessage static_msg;
  static_msg.set_id(123);
  static_msg.set_name("Static Message");

  cout << "\n=== Section 1: Static Message Creation ===\n";
  cout << "----------------------------------------\n";
  cout << "Message Content:\n" << static_msg.DebugString();
  cout << "Type: " << static_msg.GetTypeName() << "\n\n";

  // ============================================
  // Section 2: Dynamic Message Creation
  // Shows how to create a message using the descriptor and reflection APIs
  // This is useful when you don't have the generated C++ class at compile time
  // ============================================
  const google::protobuf::Descriptor *descriptor =
      google::protobuf::DescriptorPool::generated_pool()->FindMessageTypeByName(
          "test.MyMessage");

  if (!descriptor) {
    cerr << "Descriptor not found!" << endl;
    return 1;
  }

  google::protobuf::Message *dynamic_msg =
      google::protobuf::MessageFactory::generated_factory()
          ->GetPrototype(descriptor)
          ->New();

  // ============================================
  // Section 3: Type Identity Verification
  // Proves that static and dynamic messages are of the same type
  // Demonstrates that dynamic messages can be cast to their static counterparts
  // ============================================
  cout << "\n=== Section 3: Type Identity Verification ===\n";
  cout << "-------------------------------------------\n";
  cout << "Are descriptors identical? "
       << (descriptor == test::MyMessage::descriptor() ? "YES" : "NO") << "\n";

  test::MyMessage *converted_msg = dynamic_cast<test::MyMessage *>(dynamic_msg);
  cout << "Dynamic cast successful? " << (converted_msg ? "YES" : "NO")
       << "\n\n";

  // ============================================
  // Section 4: Memory Compatibility Test
  // Shows that dynamic messages can be modified and accessed just like static
  // ones Demonstrates the memory layout compatibility between static and
  // dynamic messages
  // ============================================
  cout << "\n=== Section 4: Memory Compatibility Test ===\n";
  cout << "------------------------------------------\n";

  // Set the same values in dynamic_msg as in static_msg
  const google::protobuf::Reflection *compat_reflection =
      dynamic_msg->GetReflection();
  const google::protobuf::Descriptor *compat_desc =
      dynamic_msg->GetDescriptor();

  const google::protobuf::FieldDescriptor *compat_id_field =
      compat_desc->FindFieldByName("id");
  const google::protobuf::FieldDescriptor *compat_name_field =
      compat_desc->FindFieldByName("name");

  compat_reflection->SetInt32(dynamic_msg, compat_id_field, static_msg.id());
  compat_reflection->SetString(dynamic_msg, compat_name_field,
                               static_msg.name());

  cout << "Static message content:\n" << static_msg.DebugString() << "\n";
  cout << "Dynamic message content:\n" << dynamic_msg->DebugString() << "\n";

  // Compare serialized values
  string compat_static_serialized, compat_dynamic_serialized;
  static_msg.SerializeToString(&compat_static_serialized);
  dynamic_msg->SerializeToString(&compat_dynamic_serialized);

  cout << "Serialized values identical? "
       << (compat_static_serialized == compat_dynamic_serialized ? "YES" : "NO")
       << "\n";
  if (compat_static_serialized != compat_dynamic_serialized) {
    cout << "Static serialized size: " << compat_static_serialized.size()
         << "\n";
    cout << "Dynamic serialized size: " << compat_dynamic_serialized.size()
         << "\n";
  }
  cout << "\n";

  // ============================================
  // Section 5: Basic Reflection API Usage
  // Demonstrates how to use the reflection API to access message fields
  // Shows the basic operations for getting and setting field values
  // ============================================
  test::MyMessage message;
  const google::protobuf::Reflection *reflection = message.GetReflection();
  const google::protobuf::Descriptor *descriptor_message =
      message.GetDescriptor();
  const google::protobuf::FieldDescriptor *id_field =
      descriptor_message->FindFieldByName("id");

  int32_t id_value = reflection->GetInt32(message, id_field);
  reflection->SetInt32(&message, id_field, 42);
  cout << "\n=== Section 5: Basic Reflection API Usage ===\n";
  cout << "-------------------------------------------\n";
  cout << "Message ID after reflection: " << message.id() << "\n\n";

  delete dynamic_msg; // Must manage dynamic allocation
  google::protobuf::ShutdownProtobufLibrary();

  // ============================================
  // Section 6: Dynamic Message Type Creation
  // Shows how to create a new message type programmatically
  // Useful for creating message types at runtime without .proto files
  // ============================================
  cout << "\n=== Section 6: Dynamic Message Type Creation ===\n";
  cout << "----------------------------------------------\n";
  google::protobuf::DescriptorPool pool(
      google::protobuf::DescriptorPool::generated_pool());
  google::protobuf::FileDescriptorProto file_proto;
  file_proto.set_name("my_dynamic.proto");
  file_proto.set_package("mypackage");

  google::protobuf::DescriptorProto *message_proto =
      file_proto.add_message_type();
  message_proto->set_name("MyDynamicMessage");

  google::protobuf::FieldDescriptorProto *field = message_proto->add_field();
  field->set_name("my_field");
  field->set_number(1);
  field->set_type(google::protobuf::FieldDescriptorProto::TYPE_STRING);

  const google::protobuf::FileDescriptor *file_desc =
      pool.BuildFile(file_proto);
  if (!file_desc) {
    std::cerr << "Failed to build file descriptor!" << std::endl;
    return 1;
  }

  const google::protobuf::Descriptor *message_desc = file_desc->message_type(0);
  if (!message_desc) {
    std::cerr << "Failed to get message descriptor!" << std::endl;
    return 1;
  }

  google::protobuf::DynamicMessageFactory factory;
  google::protobuf::Message *message_dyn =
      factory.GetPrototype(message_desc)->New();

  const google::protobuf::Reflection *dyn_reflection =
      message_dyn->GetReflection();
  const google::protobuf::FieldDescriptor *field_desc =
      message_desc->FindFieldByName("my_field");

  dyn_reflection->SetString(message_dyn, field_desc,
                            "Hello from dynamic message!");
  std::string value = dyn_reflection->GetString(*message_dyn, field_desc);
  std::cout << "Dynamic message field value: " << value << std::endl;

  // Without this, there will be seg fault; this is a because the underlyting
  // derived type is not protoc generated c++ class type anymore, it's
  // DynamicMessage type, the reason is unknown
  google::protobuf::UnknownFieldSet *unknown =
      message_dyn->GetReflection()->MutableUnknownFields(message_dyn);
  if (unknown) {
    unknown->AddVarint(999999, 0);
  }
  std::cout << message_dyn->DebugString() << std::endl;

  // ============================================
  // Section 6.5: Immutability of built descriptors
  // Demonstrates that once a descriptor is built, it cannot be modified
  // ============================================
  cout << "\n=== Section 6.5: Immutability of built descriptors ===\n";
  cout << "----------------------------------------------------\n";

  // Try to add another field to message_proto
  google::protobuf::FieldDescriptorProto *field2 = message_proto->add_field();
  field2->set_name("another_field");
  field2->set_number(2);
  field2->set_type(google::protobuf::FieldDescriptorProto::TYPE_INT32);

  cout << "Added 'another_field' to FileDescriptorProto in memory.\n";

  // The existing message_desc is immutable and won't see the change.
  const google::protobuf::FieldDescriptor *field_desc2 =
      message_desc->FindFieldByName("another_field");

  cout << "Is 'another_field' found in the original descriptor? "
       << (field_desc2 ? "YES" : "NO") << "\n";
  cout << "Original descriptor field count: " << message_desc->field_count()
       << "\n\n";

  // To use the new field, you would have to build a new FileDescriptor.
  // Building with the same name will fail because it's already in the pool.
  const google::protobuf::FileDescriptor *new_file_desc_fail =
      pool.BuildFile(file_proto);
  cout << "Trying to build with same name again: "
       << (new_file_desc_fail ? "succeeded (unexpected!)"
                              : "failed as expected")
       << "\n";

  // We have to change the name to build a new version.
  file_proto.set_name("my_dynamic_v2.proto");
  // We must also change the message name to avoid a symbol collision in the
  // pool.
  message_proto->set_name("MyDynamicMessageV2");
  const google::protobuf::FileDescriptor *new_file_desc_ok =
      pool.BuildFile(file_proto);
  if (new_file_desc_ok) {
    cout << "Building with a new file and message name succeeded.\n";
    const google::protobuf::Descriptor *new_message_desc =
        new_file_desc_ok->FindMessageTypeByName("MyDynamicMessageV2");
    if (new_message_desc) {
      cout << "Found new message: '" << new_message_desc->full_name() << "'\n";
      cout << "New descriptor field count: " << new_message_desc->field_count()
           << "\n";
      const google::protobuf::FieldDescriptor *new_field_desc =
          new_message_desc->FindFieldByName("another_field");
      cout << "Is 'another_field' found in the new descriptor? "
           << (new_field_desc ? "YES" : "NO") << "\n";
    } else {
      cout << "Failed to find 'MyDynamicMessageV2' in new file "
              "descriptor.\n";
    }
  } else {
    cout << "Building with a new name failed unexpectedly.\n";
  }

  // ============================================
  // Section 7: Proto File String Parsing
  // Demonstrates how to create message types from a .proto file content string
  // Shows how to use the compiler infrastructure to parse proto definitions
  // ============================================
  cout << "\n=== Section 7: Proto File String Parsing ===\n";
  cout << "------------------------------------------\n";
  std::string proto_content = R"(
        syntax = "proto3";
        package dynamic;

        message DynamicPerson {
            string name = 1;
            int32 age = 2;
            repeated string hobbies = 3;
            bool is_active = 4;
        }
    )";

  google::protobuf::DescriptorPool descriptor_pool(
      google::protobuf::DescriptorPool::generated_pool());
  MemorySourceTree source_tree("person.proto", proto_content);
  google::protobuf::compiler::SourceTreeDescriptorDatabase source_tree_db(
      &source_tree);

  google::protobuf::FileDescriptorProto file_desc_proto;
  if (!source_tree_db.FindFileByName("person.proto", &file_desc_proto)) {
    std::cerr << "Failed to parse proto content!" << std::endl;
    return 1;
  }

  const google::protobuf::FileDescriptor *file_desc_dyn =
      descriptor_pool.BuildFile(file_desc_proto);
  if (!file_desc_dyn) {
    std::cerr << "Failed to build file descriptor!" << std::endl;
    return 1;
  }

  const google::protobuf::Descriptor *descriptor_dyn =
      file_desc_dyn->FindMessageTypeByName("DynamicPerson");
  if (!descriptor_dyn) {
    std::cerr << "Failed to find message descriptor!" << std::endl;
    return 1;
  }

  google::protobuf::DynamicMessageFactory factory_dyn(&descriptor_pool);
  const google::protobuf::Message *prototype =
      factory_dyn.GetPrototype(descriptor_dyn);
  if (!prototype) {
    std::cerr << "Failed to get message prototype!" << std::endl;
    return 1;
  }

  std::unique_ptr<google::protobuf::Message> message_dyn_(prototype->New());
  if (!message_dyn_) {
    std::cerr << "Failed to create dynamic message!" << std::endl;
    return 1;
  }

  // Without this, there will be seg fault
  google::protobuf::UnknownFieldSet *unknown_fields =
      message_dyn_->GetReflection()->MutableUnknownFields(message_dyn_.get());
  if (unknown_fields) {
    unknown_fields->AddVarint(999999, 0);
  }

  const google::protobuf::Reflection *reflection_dyn =
      message_dyn_->GetReflection();
  if (!reflection_dyn) {
    std::cerr << "Failed to get reflection interface!" << std::endl;
    return 1;
  }

  const google::protobuf::FieldDescriptor *name_field =
      descriptor_dyn->FindFieldByName("name");
  const google::protobuf::FieldDescriptor *age_field =
      descriptor_dyn->FindFieldByName("age");
  const google::protobuf::FieldDescriptor *hobbies_field =
      descriptor_dyn->FindFieldByName("hobbies");
  const google::protobuf::FieldDescriptor *is_active_field =
      descriptor_dyn->FindFieldByName("is_active");

  if (!name_field || !age_field || !hobbies_field || !is_active_field) {
    std::cerr << "Failed to find required fields!" << std::endl;
    return 1;
  }

  reflection_dyn->SetString(message_dyn_.get(), name_field, "John Doe");
  reflection_dyn->SetInt32(message_dyn_.get(), age_field, 30);
  reflection_dyn->SetBool(message_dyn_.get(), is_active_field, true);
  reflection_dyn->AddString(message_dyn_.get(), hobbies_field, "Reading");
  reflection_dyn->AddString(message_dyn_.get(), hobbies_field, "Hiking");
  reflection_dyn->AddString(message_dyn_.get(), hobbies_field, "Programming");

  std::cout << "\nDebug Information:\n";
  std::cout << "Message Type: " << message_dyn_->GetTypeName() << "\n";
  std::cout << "Descriptor Name: " << descriptor_dyn->full_name() << "\n";
  std::cout << "Number of Fields: " << descriptor_dyn->field_count() << "\n";
  std::cout << "Unknown Fields Size: "
            << message_dyn_->GetReflection()
                   ->GetUnknownFields(*message_dyn_)
                   .field_count()
            << "\n";

  std::cout << "\nTrying DebugString():\n";
  std::cout << message_dyn_->DebugString() << "\n\n";

  // ============================================
  // Section 8: Static vs Dynamic Message Comparison
  // Creates a static DynamicPerson message and compares its serialization
  // with the dynamic message to verify they are identical
  // ============================================
  cout << "\n=== Section 8: Static vs Dynamic Message Comparison ===\n";
  cout << "------------------------------------------\n";
  test::DynamicPerson static_person;
  static_person.set_name("John Doe");
  static_person.set_age(30);
  static_person.set_is_active(true);
  static_person.add_hobbies("Reading");
  static_person.add_hobbies("Hiking");
  static_person.add_hobbies("Programming");

  // Clear unknown fields before serialization for fair comparison
  message_dyn_->GetReflection()
      ->MutableUnknownFields(message_dyn_.get())
      ->Clear();

  std::string static_serialized, dynamic_serialized;
  static_person.SerializeToString(&static_serialized);
  message_dyn_->SerializeToString(&dynamic_serialized);

  std::cout << "Static vs Dynamic Message Comparison:\n";
  std::cout << "Serialized data identical? "
            << (static_serialized == dynamic_serialized ? "YES" : "NO") << "\n";

  if (static_serialized != dynamic_serialized) {
    std::cout << "Static serialized size: " << static_serialized.size() << "\n";
    std::cout << "Dynamic serialized size: " << dynamic_serialized.size()
              << "\n";

    // Print hex representation of both serialized messages for debugging
    std::cout << "Static serialized (hex): ";
    for (unsigned char c : static_serialized) {
      printf("%02x ", c);
    }
    std::cout << "\nDynamic serialized (hex): ";
    for (unsigned char c : dynamic_serialized) {
      printf("%02x ", c);
    }
    cout << "\n";
  }

  return 0;
}

GPB is static typing

GPB support dynamic type creation, dynamic data creation, but it relies on pre-defined schema and once the type is built, it is immutable:

Runtime type creation is just defered compile time type registration. When user use protoc to generate types and those types are registered during program start up, before main. The registration process is the same as the so-called runtime type creation, both reading from a text and compose a type descriptor, then register it to DescriptorPool. More importantly, once the type has been registered, it can not be modified: GPB can not update all instance of this type if the type itself can be modified during runtime. Think about what happens if one type is changed, might be a new field is added, and the existing instancees can not be updated to contain this new field in data.
DynamicMessage type do bring GPB one step close to true dynamic type. It works very much like PyObject class in Python. However, it still depend on Descriptor to contruct one message, yet again Descriptor can not be changed once registered, it’s immutable. In Python, class attributes and instance attributes are added into a dynamic expanding list, which can be added and deleted at runtime. This can not be done with GPB’s descriptor. For GPB to be truely dynamic, it must make Descriptor type dynamic at runtime, since the descriptors are the real ones that defines a type. But in GPB, Descriptor can be created and changed during runtime, but it can not be changed once registered.

GPB supports runtime descriptor construction and dynamic message handling (via DynamicMessage), but the immutability of registered descriptors and the inability to propagate type changes to existing instances make it a static type system with limited runtime flexibility—not a true dynamic typing system. This design prioritizes performance, safety, and serialization reliability over full runtime dynamism. GPB only dynamically create a object according to a descriptor. It’s like building a house according to a drawing. With reflection and DynamicMessage, Protobuf does have limited dynamic typing feature, such as creating type and instance at runtime, but the immutable feature of it’s type limit it’s power.

Python achieves the propagation of type changes to existing instances through its dynamic object model, leveraging two key features:

Mutable class dictionaries
Attribute lookup delegation

In Python, an instance (obj) stores only its unique instance-level attributes in its own dict (dictionary).For class-level attributes (including methods), the instance delegates to its class. The class holds these attributes in its dict. If you modify a class’s dict (e.g., add/change attributes), all existing instances immediately reflect the changes because attribute lookup always queries the class dynamically. When you access obj.attr: Python checks obj. dict for an instance attribute attr. If not found, it delegates to the class’s dict . If the class doesn’t have it, it checks base classes (MRO). Class-level changes are visible instantly because the lookup happens at runtime, not at instance creation.

class MyClass:
    pass

def new_method(self):
    print(self.x * 2)

obj1 = MyClass()
MyClass.double_x = new_method
obj1.x = 5
obj2 = MyClass()

# obj1 can find double_x and x, can success
obj1.double_x()
# obj2 can find double_x, but not x, fail
obj2.double_x()

For dynamic types, the programmer are programming towards interpreter. For static types, the programmer are programming towards compiler

Compile-Time vs. Run-Time

weiqiang.shan — Thu, 12 Jun 2025 11:22:46 +0000

This blog post was co-authored with AI assistance.

Compile-Time vs. Run-Time

Picture compile-time as the resume screener for a job, checking your credentials before you’re hired, and run-time as your actual performance on the job, where real-world challenges test your mettle.

Compile-Time: The Resume Screener

Compile-time is all about static inspection —it’s the phase where the compiler plays bouncer, making sure your code meets the “hard requirements” before it’s allowed to execute. Think of it as a recruiter scanning your resume: Does your syntax check out? Are your types aligned? Are you following the rules?

Type Safety : The compiler catches mismatches early. For example, in C# or Java:

string my_value = Console.ReadLine();
int i = my_value; // Compiler: "Nope, string can’t be an int!"

This prevents runtime chaos by enforcing type rules upfront.

Syntax Rules : Miss a semicolon in C++ or mismatch function parameters? The compiler flags it immediately.
Scope and Visibility : Try accessing an undeclared variable or a private member, and you’ll get a stern “access denied” before the code even runs.

It’s like fixing a typo on your resume before the interview—preventive and efficient.

Run-Time: The Real-World Test

Once your code passes the compile-time “resume check,” it’s time for run-time —the dynamic phase where your program faces the unpredictable. This is your job performance after being hired: the resume got you in, but now you’re dealing with real tasks, unexpected inputs, and shifting conditions.

Dynamic Type Conversion : Syntax might be fine, but the data? That’s another story:

int i = int.Parse(my_value); // If my_value is "abc", hello FormatException!

The compiler approves, but run-time decides if the conversion works.

Polymorphism : In languages like C++:

Base* b = new Derived();
b->func(); // Run-time picks Derived::func() via the vtable

This flexibility—deciding behavior on the fly—is pure run-time magic.

Resource Checks : Java and C# watch array bounds (throwing exceptions if you overstep), while C leaves you to fend for yourself:

int arr[5];
int x = arr[10]; // Undefined behavior—good luck!

Run-time is your safety net when the real world throws curveballs.

Qualification Meets Execution

Compile-time and run-time aren’t rivals—they’re a progressive duo. Compile-time ensures your code is qualified to execute (“You meet the minimum standards”), while run-time checks if it executes successfully (“Can you handle the real thing?”).

The Big Picture: A Staged Defense

In the end, compile-time and run-time are like design-time protection and operation-time monitoring in safety engineering. Compile-time is your preventive review, weeding out structural flaws. Run-time is your dynamic insurance, adapting to chaos and keeping things afloat.

Next time your compiler yells or your program crashes, think of it as this layered system at work: compile-time says, “You can do this,” and run-time proves, “You did it.” It’s this balance that drives modern programming languages, blending performance, safety, and flexibility into the tools we love.

Static Storage and Nifty Counter

weiqiang.shan — Fri, 23 May 2025 13:22:46 +0000

This is reading notes for static initialization order fiasco problem and its solutions.

static storage duration includes:

Global variables: external linkage
static members of a class: external linkage
static variables: internal linkage
static local variables inside functions: no linkage

Since the static initialization order fiasco only happens between static objects which have external linkage, we only consider global variables and static members of a class. I call them static objects in the following content.

Initialization and destruction order of static objects

Simply put:

Inside one translation unit (TU), static objects are initialized in the order of their appearance and deinitialized in reverse order.
Across TUs, the order is unspecified.
Initialization order:
- Global variables and static class members: Initialization happens before main; Deinitialization happens after main
- static local variables: initialization at first use and deinitialization after main
- static variables inside TU: Initialization happens before main; Deinitialization happens after main

static initialization order fiasco happens when static objects across TUs depend on each other:

// file1.h
class A {
public:
    void doSomething() { /* ... */ }
};
extern A aObj;

// file1.cpp
A aObj;

// file2.h
class B {
public:
    B() { aObj.doSomething(); } // Potential problem: aObj might not be initialized yet
    static B bObj;
};

// file2.cpp
#include "file1.h" 
#include "file2.h"
B B::bObj;

int main() {
  return 0;
}

Construct On First Use Idiom

Construction On First Use Idiom uses static local variable inside function to avoid the problem. Since static local variable inside a function has no linkage and is initialized when first used, this will prevent the order problem:

Fred& x()
{
  static Fred* ans = new Fred();
  return *ans;
}

The ans will never be destructed, which avoids the problem of destruction order. The memory will be freed when the process terminates by the operating system.

If:

Fred& x()
{
  static Fred ans; // was static Fred* ans = new Fred();
  return ans; // was return *ans;
}

If some static object that depends on ans is destructed after ans is destructed, there will be the same problem as static initialization order fiasco.

Nifty Counter Idiom

Nifty Counter Idiom can solve both initialization and deinitialization order problems. Here I quote the full explanation:

// Stream.h
#ifndef STREAM_H
#define STREAM_H

struct Stream {
  Stream ();
  ~Stream ();
};
extern Stream& stream; // global stream object

static struct StreamInitializer {
  StreamInitializer ();
  ~StreamInitializer ();
} streamInitializer; // static initializer for every translation unit

#endif // STREAM_H


// Stream.cpp
#include "Stream.h"

#include <new> // placement new
#include <type_traits> // aligned_storage

static int nifty_counter; // zero initialized at load time
static typename std::aligned_storage<sizeof (Stream), alignof (Stream)>::type
  stream_buf; // memory for the stream object
Stream& stream = reinterpret_cast<Stream&> (stream_buf);

Stream::Stream ()
{
  // initialize things
}
Stream::~Stream ()
{
  // clean-up
} 

StreamInitializer::StreamInitializer ()
{
  if (nifty_counter++ == 0) new (&stream) Stream (); // placement new
}
StreamInitializer::~StreamInitializer ()
{
  if (--nifty_counter == 0) stream.~Stream ();
}

The header file of the Stream class must be included before any member function can be called on the Stream object. An instance of the StreamInitializer class is included in each compilation unit. Any use of the Stream object follows the inclusion of the header, which ensures that the constructor of the initializer object is called before the Stream object is used.

The Stream class’ header file declares a reference to the Stream object. In addition this reference is extern, meaning it is defined in one translation unit and accesses to it are resolved by the linker rather than the compiler. The implementation file for the Stream class finally defines the Stream object, but in an unusual way: it first defines a static (i.e. local to the translation unit) buffer. This buffer is both properly aligned and big enough to store an object of type Stream. The reference to the Stream object defined in the header is then set to point to this buffer. This buffer workaround enables fine-grained control of when the Stream object’s constructor and destructor are called. In the example above, the constructor is called within the constructor of the first StreamInitializer object, using placement new to place it within the buffer. The Stream object’s destructor is called when the last StreamInitializer object is destroyed.

This workaround is necessary because defining a Stream variable within Stream.cpp - be it static or not - would define it after the StreamInitializer, which is defined by including the header. Then, the StreamInitializer’s constructor would run before theStream’s constructor, and even worse, the initializer’s destructor would run after the Stream object’s destructor. The buffer solution above avoids this.

Type Erasure: Part I

weiqiang.shan — Sun, 20 Apr 2025 01:22:46 +0000

This is understanding notes for this presentation: C++ Type Erasure Demystified - Fedor G Pikus - C++Now 2024. Ppt at here.

Core logic behind type erasure
Implementation methods for type erasure
Abstraction of type
Type erasure of std::function
Type erasure of std::shared_ptr deleter
More about binding
std::variant

Core logic behind type erasure

Encapsulate type infomation in implementation, remove type information in interface
Different implementation for different types might be manually coded or generated by compiler(C++)
- Template instantiation
- Virtual inheritence
Dispatch of implementation happens at construction phase. It might happens at compile time or runtime:
- For template instantiated implementations, it happens at compile time
- For virtual inheritence, it happens at runtime Dispatch is all about redirection of function pointers
The user of the interface is not aware of the passed type information, hence the type is erased.

What’s the benifit of type erasure? Even though there is a type erased interface, like qsort, but when the qsort is actually used, we still need to pass correct implementation of the comparision function to qsort, we just defer the choice of implementation to later time. The qsort function acts as a variation point, it abstract the sorting logic functionality by using only the type erased compare function. When qsort is called, it binds the sorting logic to the actual type compare implementation. Without qsort that use the type-erased compare interface to implement common behavior of sorting, the type-erased compare interface will have no practical meaning:

The qsort algorithm stands for the common behavior, which utilize the type-erased interface
The implementation of this common behavior abstract out any specific type information
When the implementation of this common behavior is used, user decides which type it is actually operates on(the common behavior implementation still know nothing about type whatsoever)

Without this abstraction, we have to implement qsort for each individual type and the sorting algorithm has to be coded every time for each type. Now with type erasure, we only need to code the actual sorting algorithm once for all possible types. Of cource the compare function has to be implemented for each type, since each type has their own comparing logic.

Implementation methods for type erasure

Virtual inheritance: redirection hanppens when using base class pointer to call implementation in derived class(whose type is erased)
Static templated functions: C++ compiler will generate code implementation for each template instantiation. It’s the same as C, but code generated instead of manually written. Note that generated static functions are class members, which means that the amount of instantiations equals the number of generated class member functions.
Vtable: similar as 2, this time use a vtable to point to generated static class member functions.

Note: Method 3 is how std::function is implemented.

#include <cstdlib>

// Following code are in *.cpp file, without Some exposed
// But user will call this code through type erased interface: void
// print_data(const void *p). This is the core of type erasure: encapsulate type
// infomation in implementation, remove type information in interface.
struct Some {
  int data;
};
bool less(const void *l, const void *r) {
  return static_cast<const Some *>(l)->data <
         static_cast<const Some *>(r)->data;
}

// The declaration in *.h, exposed to external user
// ! Here is where the type erasure happens
bool less(const void *, const void *);

// User of type erasure: qsort does not need to know which type it will sort,
// type is erased from qsort: type erasure is an abstraction for multiple
// implementations that provide the same behavior, the relevent behavior is what
// matters, not the type. In this example, `compare` parameter requires that two
// elements can be compared, qsort does not care about how it is compared, as
// long as it return a bool value. This gives chances to implement the compare
// logic in source code, instead of in interface code.

// Since type erasure is about abstraction of behavior, it alwarys involve
// redirection of function pointers, no matter which way it is implemented. This
// redirection of function pointer is called dispatch, which is another core
// brick in implementing type erasure. Dispatch might happen both at compile
// time or runtime.

// Compared with C, C++ ONLY add implementation methods for type erasure. In C,
// we have to manually write different implementations, like the `less` and
// `more` function in below. In C++, we have the compiler to generate different
// implementation code for us. They all involves template and are done at
// construction phase. The three ways are:
// 1. virtual inheritance: redirection hanppens when using base class pointer to
// call implementation in derived class(whose type is erased)
// 2. static templated functions: C++ compiler will generate
// code implementation for each template instantiation. It's the same as C, but
// code generated instead of manually written. Note that generated static
// functions are class members, which means that the amount of instantiations
// equals the number of generated class member functions.
// 3. vtable: Similar as 2, this time use a vtable to point to instead of
// generating static class member functions.

// One more important fact is that all the C++ ways are of value semantics. The
// implementation is stored as value(function pointers can be seen as value of
// function variables).

// Now we can summarize type erasure as follow:

// Core logic of type erasure:
// 1. Encapsulate type infomation in implementation, remove type information in
// interface.
// 2. The interface provide same behavior, regardless of specific type

// Implementation steps of type erasure involve two distinct phase: how
// implementation code is generated at compile time and how those implementation
// is dispatched to at runtime:

// 1. Statically write type erased code implementation, either manually, or by
// compiler(C++). The type must be inside cpp, not in header(interface)
// 2. Dynamically dispatch function call to the right implementation at runtime.
// How the dispatch is done varies. It can simply be hard coded(like in C qsort
// example in following code). Or it can be done using virtual inheritance in
// C++. Either way, the dispatch, or redirection is determined during
// construction phase. As soon as the construction is complete, the dispatch
// manner is determined.

void qsort(void *base, size_t nmeb, size_t size,
           bool (*compare)(const void *, const void *));

// Following give another type that also use qsort
struct Tome {
  int data;
};
bool more(const void *l, const void *r) {
  return static_cast<const Tome *>(l)->data <
         static_cast<const Tome *>(r)->data;
}
bool more(const void *, const void *);

int main() {
  Some a[10];
  Tome b[10];
  // qsort is universal, thanks to the redirection of `compare` parameter
  qsort(a, 10, 4, less);
  qsort(b, 10, 4, more);
}

Abstraction of type

Type erasure, C++ template, C++ concept, virtual inheritence, what is the common characteristic among them? They both allow us to write code logic for a group of types, instead of just one type. The code logic is the common behavior for those types. The binding of specific types are deferred to later times: for type erasure and virtual inheritence, this binding is defered to runtime; for C++ template and C++ concept, this binding is deferred to compile time:

We can write binary libraries which can be used on difference types using type erasure and virtual inheritence
We can write templated source code libraries which can be used on difference types using C++ template and C++ concept

C++ concept is more restricted C++ template. C++ virtual inheritence is special kind of type erasure, with vtable as runtime dispatch method. All being said, at the core, they are all function pointer binding methods, at compile time, or at runtime. When bind at runtime, it’s always during the construction phase.

Type erasure of std::function

After the signature is specified through template paramter, std::function variable can be used to store difference kinds of types, as long as they both have the same signature. This is done through type erasure. std::function has value semantics and can be copied and moved. After the template signature is determined the code for all methods is fixed for the compiler. After a std::function instance is constructed, the implementation binding is fixed.

See std::function implementation

Type erasure of std::shared_ptr deleter

std::shared_ptr type use virtual base class to do type erasure. If user pass a custom deleter during construction, the pointer instance will be bound to a unified base class and points to the implementation of this custom deleter.

// Support for custom deleter and/or allocator
template <typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp>
class _Sp_counted_deleter final : public _Sp_counted_base<_Lp> {
  class _Impl : _Sp_ebo_helper<0, _Deleter>, _Sp_ebo_helper<1, _Alloc> {
    typedef _Sp_ebo_helper<0, _Deleter> _Del_base;
    typedef _Sp_ebo_helper<1, _Alloc> _Alloc_base;

  public:
    _Impl(_Ptr __p, _Deleter__ d, const _Alloc &__a) noexcept
        : _M_ptr(__p), _Del_base(std::move(__d)), _Alloc_base(__a) {}

    _Deleter &_M_del() noexcept { return _Del_base::_S_get(*this); }
    _Alloc &_M_alloc() noexcept { return _Alloc_base::_S_get(*this); }

    _Ptr _M_ptr;
  };

public:
  using __allocator_type =__ alloc_rebind<_Alloc, _Sp_counted_deleter>;

  // __d(__p) must not throw.
  _Sp_counted_deleter(_Ptr __p, _Deleter__ d) noexcept
      : _M_impl(__p, std::move(__d), _Alloc()) {}

  // __d(__p) must not throw.
  _Sp_counted_deleter(_Ptr __p, _Deleter__ d, const _Alloc &__a) noexcept
      : _M_impl(__p, std::move(__d), __a) {}

  ~_Sp_counted_deleter() noexcept {}

  virtual void _M_dispose() noexcept { _M_impl._M_del()(_M_impl._M_ptr); }

  virtual void _M_destroy() noexcept {
    __allocator_type__ a(_M_impl._M_alloc());
    __allocated_ptr<__ allocator_type> __guard_ptr{__ a, this};
    this->~_Sp_counted_deleter();
  }

  virtual void *_M_get_deleter(const std::type_info &__ti) noexcept {
#if __cpp_rtti
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2400. shared_ptr's get_deleter() should use addressof()
    return __ti == typeid(_Deleter) ? std::__addressof(_M_impl._M_del())
                                    : nullptr;
#else
    return nullptr;
#endif
  }

private:
  _Impl _M_impl;
};

_Deleter type is erased at compile time, std::shared_ptr type will only store a pointer of _Sp_counted_base type, which makes the std::shared_ptr type not depend on custom deleters.

More about binding

After a type is erased, we have to bind to the correct implementations. The implementation must coorespond to this type, otherwise, there will be errors if we pass a void pointer to this implementation, since inside this implementation, the void pointer will be cast back to this type. Of course, there can be multiple implementations for this type, but, there is only one binding. Better use examples:

Whether it’s compile time or runtime, as long as the binding is finished, it cannot be changed.
For virtual class, when a derived class instance is created, it’s vtable is bound to vtable of this class, it’s wrong to change it.
For template functions, which binds at compile time, it’s fixed after compilation, and cannot be changed.
For std::function, we can have multiple variable for the same signature: std::function<int(int)> a, std::function<int(int)>b, and they can have different implementations. However, after construction of a, b, their binding to implementation is fixed, we cannot change a’s implementation to b’s. Of course, we can assign a to b, which will create a copy of b, but this is not changing the binding of a. Even though a and b are of the same type, but they contain and bind to different callables:

template <typename _Res, typename... _ArgTypes>
template <typename _Functor, typename, typename>
function<_Res(_ArgTypes...)>::function(_Functor __f) : _Function_base() {
typedef _Function_handler<_Res(_ArgTypes...), _Functor> _My_handler;

if (_My_handler::_M_not_empty_function(__f)) {
  _My_handler::_M_init_functor(_M_functor, std::move(__f));
  _M_invoker = &_My_handler::_M_invoke;
  _M_manager = &_My_handler::_M_manager;
}
}

After construction the binding is fixed and can not be changed.

std::variant

std::variant itself is not type erasure, it’s a union and will record flags to indicate which type it currently stores
std::visit involves two phase:
- Dispatch right function according to specific type stored in std::variant at runtime
- Each function is stored type erased, like std::function

Reactor and Proactor Exectuion Context

weiqiang.shan — Sat, 29 Mar 2025 01:22:46 +0000

Following content aggregates materials about reactor and proactor, along with some keynotes about it.

References

Reactor and Proactor, Examples of event handling patterns: Great material on what is reactor and what is proactor.
The Proactor Design Pattern: Concurrency Without Threads: Explains the boost.asio proactor design pattern. What is key about this material is that it also explains the relationship between reactor and proactor in Linux: proactor is implemented on top of reactor(epoll).
Proactor Wikipedia: The wiki page reveals an important fact about proactor: The proactor pattern can be considered to be an asynchronous variant of the synchronous reactor pattern.

Keynotes

Reactor in Linux has native OS support through system primitives like epoll. But Linux does not have native support for proactor. Windows have native support for proactor, IOCP
In Linux, proactor is implemented on top of reactor.
Reactor is synchronous I/O, while proactor is asynchronous I/O.
Again and important: The proactor pattern can be considered to be an asynchronous variant of the synchronous reactor pattern.
Reactor in Linux can be simplified as I/O multiplexing.

Execution Context

One thing that have long been confusing me about proactor is it’s execution context. For reactor, it occupies one execution context(eg, a thread) and blockingly waiting for any of file descriptors to be ready for relevant events. Since in Linux proactors are implemented on top of reactor, does proactor need additional execution context? In Boost, proactor is called The Proactor Design Pattern: Concurrency Without Threads, which indicates that there are no additional threads required for proactor. Then how to implement proactor in one thread, knowing that reactor itself already occupies one thread?

The foundation here is to know that(in the context of boost.asio):

There is a underlying reactor, which is normally implemented using epoll in Linux.
There is one execution context, io_context, which will be called in one thread io_context.run(), which will call epoll wait under the hood.
That epoll can monitor multiple file descriptors and can be updated.

Yet there is one brick missing to understanding the proactor pattern: software events. Epoll can only monitor file descriptors, like if a file descriptor is readable, writable, etc. But proactor requires that the epoll_wait be unblocked if a user async operation is completed. How can epoll monitor these kinds of events? In the reactor that is used to implement proactor, there is an pre-defined additional file descriptor, it might be a pipe, uds socket, or something else, as long as it can be written and read. This fd is used to unblock epoll_wait whenever there is software events. For example, epoll_wait monitor this fd, fd_events and another socket fd, fd_socket. fd_socket is to read bytes from a connection. fd_events is a, for example, pipe. There is a async reading operation initiated by user to read n bytes from fd_socket, and also a completion handler is provided and registered. Now the epoll_wait is blocked waiting to read from fd_socket, and the execution context thread is suspended in OS. Now n-1 bytes are recieved from kernel and is ready to be read. The epoll_wait is unblocked and find that fd_socket is ready to read from. The reactor calls relevant callbacks to read from this socket. Since the callback only read n-1 bytes, not n bytes, which is required by the async operation, it exit the loop and give control to epoll_wait again. Next, the last one byte finally arrived, again the epoll_wait is unblocked and the registered callback is called to read the last one byte. After reading, inside the callback, it knows that the operation is finally completed as required from the async operation. It now writes the completion information to the fd_events and exit the loop to go back to epoll_wait again. This time the epoll_wait immediately unblocks since there are content to be read from fd_events, software events happen. The reactor calls relevant software events callback and process the software events. Inside the callback, it first read from the fd_events and knows which software events happen and according to the information,it finds the corresponding completion handler and executes it. It goes on until all completed software events handlers are executed, then goes to epoll_wait again.

Let’s understand above process with the help of following code snippet:

#include "make_day_time.h"
#include <asio.hpp>
#include <memory>

#ifndef ASYNC_UDP
#define ASYNC_UDP

using asio::ip::udp;
class udp_server {
public:
  udp_server(asio::io_context &io_context)
      : socket_(io_context, udp::endpoint(udp::v4(), 5002)) {
    start_receive();
  }

private:
  udp::socket socket_;
  udp::endpoint remote_endpoint;
  std::array<char, 1> buffer;

  void start_receive() {
    socket_.async_receive_from(
        asio::buffer(buffer), remote_endpoint,
        [this](const std::error_code &error, std::size_t) {
          if (!error) {
            std::shared_ptr<std::string> msg =
                std::make_shared<std::string>(make_daytime_string());
            socket_.async_send_to(
                asio::buffer(*msg), remote_endpoint,
                [](const std::error_code &error, std::size_t) {});
            start_receive();
          }
        });
  }
};

#endif

io_context serves as the sole execution context. It will be run inside one thread. The reactor is implemented inside asio::io_context
socket_.async_receive_from is the asyn operation initialized from user. It provides two requirements:
- The receive operation should fill the buffer
- After the buffer is filled, the lambda completion handler should be called Inside this call, it will register:
- Monitoring of this socket to io_context, when it’s available to read, epoll will unblock. Note that after the reading is completed, inside the callback registered to the reactor, it will deregister the monitoring of this socket from the reactor. Then also inside the callback, it will trigger software events to make the execution context execute completion handler in next loop of epoll_wait.
- Register software event and it’s handler(the lambda) to this same io_context, expecting it to be called when the reading is completed. This call returns immediately.
Inside the lambda, socket_.async_send_to is called to give feedback. Again it’s the same pattern as socket_.async_receive_from , except that this time the reactor will unblock when this socket is available to write. After the writing complete, the completion lambda is again called as software event.
Inside the socket_.async_send_to completion handler, start_receive(); is called recursively, which starts the loop again.
Note that the send-recieve-send-recieve is executed in order.

Do not call async read and write operations before the last one is completed. There is no meaning to do that anyway:

Interleaved read/write is meaningless, even if it is possible(I don’t know if it is possible in asio)
Even if the async operations are queued by asio(again I don’t know if it is the case in asio), we can chain the read/write in completion handlers to have the same effect.

Expressions: type and value category

weiqiang.shan — Fri, 28 Feb 2025 01:22:46 +0000

According to my experience, the most difficult part in understanding C++ is however the most basic one: the expression. Only by having a comprehensive understanding of expression, one can further have a clear understanding about lvalue, rvalue, type deduction, auto keyword, universal reference, decltype, move semantics,etc. As you can see, above-mentioned concepts are at the core of C++ 11 and afterwards.

This blog summarize information, concepts, references around expression. It does not provide additional knowledge, but act as a understanding note.

Expressions
- Type
- Value Category
- Type vs ValueCategory
Type Deduction
- Deduction context
- Function template parameter type deduction
- auto deduction
- More about Universal Reference
- Reference Collapsing Rules
- Key Points & Golden Rules
- std::forward explained
Named Variables
decltype
- Print valueness
static_cast vs decltype
declval

Expressions

C++ expressions

Each C++ expression (an operator with its operands, a literal, a variable name, etc.) is characterized by two independent properties: a type and a value category. Each expression has some non-reference type, and each expression belongs to exactly one of the three primary value categories: prvalue, xvalue, and lvalue.

Type

An expression can have basic type, user-defined type, const/non-const, reference/non-reference types. However, If an expression initially has the type “reference to T” (8.3.2, 8.5.3), the type is adjusted to T prior to any further analysis., which indicates that expression can have reference types. Expressions can have Reference Type:

Today I got email about some information in Effective Modern C++. The email included the statement, “An expression never has reference type.” This is easily shown to be incorrect, but people assert it to me often enough that I’m writing this blog entry so that I can refer people to it in the future.

Section 5/5 of the Standard is quite clear (I’ve put the relevant text in bold):

If an expression initially has the type “reference to T” (8.3.2, 8.5.3), the type is adjusted to T prior to any further analysis. The expression designates the object or function denoted by the reference, and the expression is an lvalue or an xvalue, depending on the expression.

There’d clearly be no need for this part of the Standard if expressions couldn’t have reference type.

If that’s not enough to settle the matter, consider the type of an expression that consists of a function call. For example:
int& f(); // f returns int&
auto x = f(); // a call to f
What is the type of the expression “f()”, i.e., the type of the expression consisting of a call to f? It’s hard to imagine anybody arguing that it’s not int&, i.e., a reference type. But what does the Standard say? Per 5.2.2/3 (where I’ve again put the relevant text in bold and where I’m grateful to Marcel Wid for correcting the error I had in an earlier version of this post that referred to 5.2.2/10):

If the postfix-expression designates a destructor (12.4), the type of the function call expression is void; otherwise, the type of the function call expression is the return type of the statically chosen function (i.e., ignoring the virtual keyword), even if the type of the function actually called is different. This return type shall be an object type, a reference type or cv void.

It’s very clear that expressions can have reference type. Section 5/5 takes those expressions and strips the reference-ness off of them before doing anything else, but that’s not the same as the reference-ness never being present in the first place.

Value Category

C++ value_category

With the introduction of move semantics in C++11, value categories were redefined to characterize two independent properties of expressions[5]:

has identity: it’s possible to determine whether the expression refers to the same entity as another expression, such as by comparing addresses of the objects or the functions they identify (obtained directly or indirectly);

can be moved from: move constructor, move assignment operator, or another function overload that implements move semantics can bind to the expression.

In C++11, expressions that:

have identity and cannot be moved from are called lvalue expressions;

have identity and can be moved from are called xvalue expressions;

do not have identity and can be moved from are called prvalue (“pure rvalue”) expressions;

do not have identity and cannot be moved from are not used[6].

The expressions that have identity are called “glvalue expressions” (glvalue stands for “generalized lvalue”). Both lvalues and xvalues are glvalue expressions.

The expressions that can be moved from are called “rvalue expressions”. Both prvalues and xvalues are rvalue expressions.

   ____________

  / X \

 / / \ \

| l | x | pr |

 \ \ / /

  \ ______X______ /

 gl r

Above diagram describes the general relationship between lvalue(l), xvalue(x), prvalue(pr), glvalue(gl), rvalue(r)

Type vs ValueCategory

Lvalueness or rvalueness of an expression is independent of its type, it’s possible to have lvalues whose type is rvalue reference, and it’s also possible to have rvalues of the type rvalue reference. See examples from Universal References in C++11, Scott Meyers:

Widget makeWidget();
 // factory function for Widget
Widget&& var1 = makeWidget()
 // var1 is an lvalue, but
 // its type is rvalue reference (to Widget)
Widget var2 = static_cast<Widget&&>(var1);
 // the cast expression yields an rvalue, but
 // its type is rvalue reference (to Widget)

Note that the valueness of expression static_cast is decided by static_cast itself:

As with all cast expressions, the result is:

An lvalue if target-type is an lvalue reference type or an rvalue reference to function type(since C++11);

A xvalue if target-type is an rvalue reference to object type; swq: how std::move is implemented

A prvalue otherwise.

Type Deduction

Deduction context

We consider two occasions where type deduction happens:

Function template parameter type deduction
auto

Additionally, a special kind of type deduction, universal reference is considered.

During compile time compiler has mainly two ways to deduce template parameter types: from user and auto deduction. In the case of user input, whatever user specifies, compiler will use them. If user specified reference, reference collapsing rules apply. Also in C++ 17, class template parameter type can also be deduced: Class template argument deduction (CTAD) (since C++17).

Function template parameter type deduction

Note: Most content of this paragraph comes from the book: Effective Modern C++, Scott Meyers. I only copies them here to make this artical complete.

Take:

template<typename T>
void f(ParamType param);
f(expr); // deduce T and ParamType from expr

// Above pseudo code can represent most cases, since reference, const are not allowed insdie parameter list: template<typename const T> and template<typename T&> and template<typename T&&> are both not valid. However, when user specify T, const and reference types can be used and reference collapsing rules apply.

Note: typename can only be class, or typename, no additional qualifiers are possible: type-parameter-key -either typename or class

Case 1: ParamType is a Reference or Pointer, but not a Universal Reference
- If expr’s type is a reference, ignore the reference part
- Then pattern-match expr’s type against ParamType to determine T.
Case 2: ParamType is a Universal Reference
- If expr is an lvalue, both T and ParamType are deduced to be lvalue references. That’s doubly unusual. First, it’s the only situation in template type deduction where T is deduced to be a reference. Second, although ParamType is declared using the syntax for an rvalue reference, its deduced type is an lvalue reference.
- If expr is an rvalue, the “normal” (i.e., Case 1) rules apply.
Case 3: ParamType is Neither a Pointer nor a Reference
- As before, if expr’s type is a reference, ignore the reference part
- If, after ignoring expr’s reference-ness, expr is const, ignore that, too. If it’s volatile, also ignore that.

auto deduction

It’s essentially the same as function template parameter type deduction like above, the mappings relationships are:

auto –> T
Expression before = –> ParamType
Expression after = –> expr

For example:

auto x = 27; // case 3 (x is neither ptr nor reference)
const auto cx = x; // case 3 (cx isn't either)
const auto& rx = x; // case 1 (rx is a non-universal ref.)
// T --> auto; const auto& --> ParamType; x --> expr

auto can also be used in lamda and support universal reference:


#include <algorithm>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

class A {
public:
  // Default constructor
  A() { std::cout << "Default constructor called\n"; }

  // Destructor
  ~A() { std::cout << "Destructor called\n"; }

  // Copy constructor
  A(const A &) { std::cout << "Copy constructor called\n"; }

  // Move constructor
  A(A &&) noexcept { std::cout << "Move constructor called\n"; }

  // Copy assignment operator
  A &operator=(const A &) {
    std::cout << "Copy assignment operator called\n";
    return *this;
  }

  // Move assignment operator
  A &operator=(A &&) noexcept {
    std::cout << "Move assignment operator called\n";
    return *this;
  }
};

int main() {

  std::vector<A> vec(2);
  std::for_each(vec.begin(), vec.end(),
                // e is of lvalue, copy contructor called
                // Note: e is not expression here, decltype get the real type of
                // e, for universal reference, it's either non-reference type or
                // lvalue reference type
                [](auto &&e) { auto a = std::forward<decltype(e)>(e); });

  std::for_each(std::make_move_iterator(vec.begin()),
                std::make_move_iterator(vec.end()),
                // e is of xvalue, move contructor called
                // Note: e is not expression here, decltype get the real type of
                // e, for universal reference, it's either non-reference type or
                // lvalue reference type
                [](auto &&e) { auto a = std::forward<decltype(e)>(e); });
}

More about Universal Reference

Universal References in C++11, Scott Meyers

Reference Collapsing Rules

C++ Reference

An rvalue reference to an rvalue reference becomes (‘collapses into’) an rvalue reference.
All other references to references (i.e., all combinations involving an lvalue reference) collapse into an lvalue reference.

Key Points & Golden Rules

Remember that “&&” indicates a universal reference only where type deduction takes place. Where there’s no type deduction, there’s no universal reference. In such cases, “&&” in type declarations always means rvalue reference.
Apply std::move to rvalue references and std::forward to universal references
Only use std::forward with universal references
Universal reference type deduction is the only situation a template parameter is deduced as reference(when passed type is of lvalue).

std::forward explained

std::forward

Only use std::forward with universal reference. So the template argument for it should always be deduced, instead of specified.
- This implies that the deduced type T is either non-reference type or a lvalue reference.
- Always use universal reference template paramter T directly for std::forward’s template paramters, do not manually add additional const/reference to it. Note that T can be decorated: like forward<decltype(forward<T>(arg).get())>, as long as T itself is the same as the universal reference.
std::forward is an expression and function, it’s value category conform to normal C++ expression rules. It always return reference:
- When return lvalue reference, its value category is lvalue
- When return rvalue reference, its value category is rvalue(xvalue or prvalue)
- Above behavior is due to the fact that when cast to rvalue reference, the result of static_cast is of xvalue; when cast to non-reference, the result is of prvalue; when cast to lvalue reference, the result is of lvalue.
The type and valueness is decided by static_cast, which is the internal implementation of std::forward

The standard implements std::forward:

  /**
   * @brief Forward an lvalue.
   * @return The parameter cast to the specified type.
   *
   * This function is used to implement "perfect forwarding".
   */
  template<typename _Tp>
    constexpr _Tp&&
    forward(typename std::remove_reference<_Tp>::type& __t) noexcept
    { return static_cast<_Tp&&>(__t); }

  /**
   * @brief Forward an rvalue.
   * @return The parameter cast to the specified type.
   *
   * This function is used to implement "perfect forwarding".
   */
  template<typename _Tp>
    constexpr _Tp&&
    forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
    {
      static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
            " substituting _Tp is an lvalue reference type");
      return static_cast<_Tp&&>(__t);
    }

_Tp is the type deduced from universal references, which might be non-reference type or lvalue reference type. __t is the parameter passed to std::forward, which is of lvalue category, since inside function, parameters are passed always as lvalues. The aim of std::forward is to restore the value category of the passed parameter:

When _Tp is of non-reference type, which means the universal reference is deduced based on passed rvalue parameter:
- __t is of _Tp&& type, the second overload is used, std::forward return rvalue category, rvalue reference type object
When _Tp is of lvalue reference type, which means the universal reference is deduced based on passed lvalue parameter:
- __t is of _Tp& type, the first overload is used, std::forward return lvalue category, lvalue reference type object

Note: Type is not changed when parameters are passed down to nested function calls, only value category are changed. This is how std:forward do overload based on types

Usage1: Forwards lvalues as either lvalues or as rvalues, depending on T:

template<class T>
void wrapper(T&& arg)
{
    // arg is always lvalue
    foo(std::forward<T>(arg)); // Forward as lvalue or as rvalue, depending on T
}

When T is deduced to non-reference type,the expression std::forward is of:
- type: rvalue reference to T
- value category: rvalue
When T is deduced to lvalue reference type, the expression std::forward is of:
- type: lvalue reference to T
- value category: lvalue

Note: This usage is to restore the value category of the passed parameter, whose valueness, due to the nested argument passing, is all treated as lvalue category.

Usage2: Forwards rvalues as rvalues and prohibits forwarding of rvalues as lvalues.

struct Arg
{
    int i = 1;
    int get() && { return i; } // call to this overload is rvalue
    int& get() & { return i; } // call to this overload is lvalue
};
// transforming wrapper
template<class T>
void wrapper(T&& arg)
{
    foo(forward<decltype(forward<T>(arg).get())>(forward<T>(arg).get()));
}

The decltype(forward<T>(arg).get()) evalues the type:
- If T is deduced to non-reference type, the expression forward<T>(arg).get() will have type int and have xvalueness. decltype will result in type int&&
- If T is deduced to lvalue reference type, the expression forward<T>(arg).get() will have type int& and have lvalueness. decltype will result int type int&
The second appearance of forward<T>(arg).get() just call proper implementation of get()

Note: when using decltype as parameter argument to std::forward, we only need to care about whether the expression in decltype is lvalue or rvalue, no need to care about the type(only need to know the non-reference type of T). Since if the expression is lvalue, decltype will result in lvalue reference type, which result in lvalue reference type(lvalueness) for the std::forward. Otherwise, if the expression inside decltype is of xvalue or prvalue, decltype results in non-reference type or rvalue reference type, which both result in a rvalue reference type(rvalueness) for the std::forward expression. decltype and std::forward together to pass the valueness down to nested function calls.

Note: If we use foo(forward<int&>(forward<T>(arg).get())); and pass a rvalue of Arg instance to wrapper, there will be compile time error, since we try to forward rvalue as lvalue(the valueness of the return of std::forward).

std::forward can be used together with auto&& in lambdas, which needs the help of decltype to infer the correct type:

  std::vector<std::string> source = {"a", "b", "c"};

  // This is totally generic
  auto forwarder = [](auto &&container) {
    // If container is of lvalue, it's type is lvalue reference type, decltype
    // return lvalue reference.
    // If container is of rvalue, it's type is rvalue reference type, decltype
    // return rvalue reference
    auto dest = std::forward<decltype(container)>(container);
  };

  forwarder(std::move(source));
  std::cout << source.size() << std::endl;

  std::vector<std::string> source2 = {"x", "y", "z"};
  forwarder(source2);
  std::cout << source2.size() << std::endl;

However, using of std::forward in range-based for loop with auto&& will not work as expected:

  std::vector<std::string> source = {"a", "b", "c"};

  // item is std::string& type, even with std::move
  for (auto &&item : std::move(source)) {
    // After std::forward the return type is still std::string&
    auto dst = std::forward<decltype(item)>(item);
  }
  std::cout << source[0] << std::endl;

In above code snippet, std::move(source) will not trigger move operation for source and item is of lvalue category and lvalue reference type. This behavior can be explained by looking at the internal implementation of range-based for in C++:


{

auto&& /* range */ = range-initializer ;
for (auto /* begin */ = /* begin-expr */, /* end */ = /* end-expr */;
/* begin */ != /* end */; ++/* begin */)
{
item-declaration = */* begin */;
statement
}
}

First the auto&& universal reference is used to create a local variable, which is itself a lvalue
Then use iterator to iterate over this lvalue and dereference this lvalue and create a local variable using item-declaration, which is the user specified auto &&item
auto &&item will always be deduced as lvalue reference
If auto item is used, item will be a copy, and the original const qualifier will be removed

To iterate and move element out of a container, move iterators can be used:

  std::vector<std::string> source = {"a", "b", "c"};

  // This will move the element
  for (auto it = std::make_move_iterator(source.begin());
       it != std::make_move_iterator(source.end()); ++it) {
    auto dst = *it;
  }
  std::cout << source[0] << std::endl;

Named Variables

Named variables and parameters of rvalue reference type are lvalues. Also from Universal References in C++11, Scott Meyers:

template<typename T>
class Widget {
 ...
 Widget(Widget&& rhs);
 // rhs's type is rvalue reference, but rhs
 // itself is an lvalue
 ...
};
template<typename T1>
class Gadget {
 ...
 template <typename T2>
 Gadget(T2&& rhs);
 // rhs is a universal reference whose type will
 // eventually become an rvalue reference or an
 // lvalue reference, but rhs itself is an lvalue
 ...
};

To create rvalue, std::move, std::forward, static_cast specifier has to be used:


#include <iostream>
#include <utility>
class A {
public:
  // Default constructor
  A() { std::cout << "Default constructor called\n"; }

  // Destructor
  ~A() { std::cout << "Destructor called\n"; }

  // Copy constructor
  A(const A &) { std::cout << "Copy constructor called\n"; }

  // Move constructor
  A(A &&) noexcept { std::cout << "Move constructor called\n"; }

  // Copy assignment operator
  A &operator=(const A &) {
    std::cout << "Copy assignment operator called\n";
    return *this;
  }

  // Move assignment operator
  A &operator=(A &&) noexcept {
    std::cout << "Move assignment operator called\n";
    return *this;
  }
};

int main() {

  A a;
  A &&b = std::move(a);

  // ! This will call copy constructor, NOT move constructor, even b is rvalue
  // reference type, but it's lvalue
  A c(b);

  // ! This will call move constructor
  A d(std::move(c));
}

decltype

C++ decltype

Inspects the declared type of an entity or the type and value category of an expression. This implies two funtionality of decltype:

When used as decltype ( entity ), where entity is unparenthesized id-expression or class memeber expression, it yields the type of entity
When used as decltype ( expression ), where expression is any other expression, it inspects the expression’s value type(eg,T) and value category and yields following types accordingly:

if value category of expression is xvalue, it yields T&&
if value category of expression is lvalue, it yields T&
if value category of expression is prvalue, it yields T

Note: if variable id-expression or class memeber access expression is parenthesized, it is treated as ordinary lvalue expression(which is reasonable, because named variables are always lvalue expressions)

class Widget {};
Widget makeWidget() { return Widget(); }

int main() {

  Widget &&var1 = makeWidget();
  // var1 is an lvalue, but
  // its type is rvalue reference (to Widget)
  Widget var2 = static_cast<Widget &&>(var1);
  // the cast expression yields an rvalue, but
  // its type is rvalue reference (to Widget)
  decltype(static_cast<Widget &&>(var1)) var3 = makeWidget();
  // expression type is Widget &&, value category of expression is xvalue,
  // first get the non-reference type Widget, so var3 is of Widget&& type.
  Widget &var4 = var2;
  decltype(std::move(var4)) var5 = makeWidget();
  // expression type is Widget &, value category of expression is xvalue; first
  // get the non-reference type Widget, so var5 is of Widget && type

  decltype((var4)) var6 = var2;
  // expression type is Widget &, value category of expression is lvalue; first
  // get the non-reference type Widget, so var6 is of Widget & type

  decltype(makeWidget()) var7 = makeWidget();
  // expression type is Widget , value category of expression is prvalue; first
  // get the non-reference type Widget, so var6 is of Widget type
}

Note: When doing all deduction the expression type T will use the non-reference version, since as the standard says:

If an expression initially has the type “reference to T” (8.3.2, 8.5.3), the type is adjusted to T prior to any further analysis.

decltype links valueness of an expression to type.

Print valueness

First approach, we can check whether the yield type of decltype(expression) is lvalue or rvalue reference, if rvalue reference, the expression is xvalue; if lvalue reference, the expression is lvalue; otherwise, the expression is prvalue

#include <iostream>
#include <utility> // for std::move

class Widget {};
Widget makeWidget() { return Widget(); }

template <typename T> struct value_category {
  static constexpr const char *str() { return "prvalue"; }
};

template <typename T> struct value_category<T &> {
  static constexpr const char *str() { return "lvalue"; }
};

template <typename T> struct value_category<T &&> {
  static constexpr const char *str() { return "xvalue"; }
};

// Macro to check the value category of an expression
#define PRINT_VALUE_CATEGORY(expr) \
  std::cout << "The expression '" #expr "' is a " \
            << value_category<decltype((expr))>::str() << std::endl;

int main() {
  Widget &&var1 = makeWidget();
  Widget var2 = static_cast<Widget &&>(var1);
  Widget &var4 = var2;

  PRINT_VALUE_CATEGORY(var1); // lvalue
  PRINT_VALUE_CATEGORY(static_cast<Widget &&>(var1)); // xvalue
  PRINT_VALUE_CATEGORY(var4); // lvalue
  PRINT_VALUE_CATEGORY((var4)); // lvalue
  PRINT_VALUE_CATEGORY(std::move(var4)); // xvalue
  PRINT_VALUE_CATEGORY(makeWidget()); // prvalue
}

static_cast vs decltype

Let’s compare static_cast and decltype:

With static_cast:

As with all cast expressions, the result is:

An lvalue if target-type is an lvalue reference type or an rvalue reference to function type(since C++11);

A xvalue if target-type is an rvalue reference to object type; swq: how std::move is implemented

A prvalue otherwise.(non-reference type)

With decltype:

if value category of expression is xvalue, it yields T&&

if value category of expression is lvalue, it yields T&

if value category of expression is prvalue, it yields T

They do reverse operations:

static_cast sets the type/value category (via the target type).
decltype infers the type/value category (from the expression).

declval

C++ declval

declval can return a reference to a type, without going through actual construction.

Implementation:

template<typename T>
typename std::add_rvalue_reference<T>::type declval() noexcept
{
    static_assert(false, "declval not allowed in an evaluated context");
}

What declval does is simply add rvalue reference to type T
The static_cast statement make sure that it can only be used in unevaluated context, like inside decltype

Why add rvalue reference, instead of lvalue reference?

The reason is related to reference collapsing rules: only by adding rvalue reference, declval might have the possibility return a rvalue reference, so as to have more possibility to call methods, such as methods that can only be called by rvalue.

Variable-length shared memory ring buffer

weiqiang.shan — Sun, 12 Jan 2025 01:22:46 +0000

A variable-length shard memory ring buffer that supports sharing variable length payloads data between processes. This is based on https://github.com/bo-yang/shm\_ring\_buffer, which only support POD fixed length data. The idea is illustrated in following diagram:

Github: shm_ring_buffer