CPython's Union Type Implementation in C (X | Y)

Python’s X | Y syntax (and typing.Union[X, Y]) produces an object of type types.UnionType. Unlike Ellipsis or None, a union is a real allocated object: it owns references to its arguments, participates in garbage collection, and can be weakly referenced. The whole implementation lives in Objects/unionobject.c. This article traces it through the 3.15 source.

The struct: `unionobject`

c
// Objects/unionobject.c
typedef struct {
    PyObject_HEAD
    PyObject *args;             // all args (tuple)
    PyObject *hashable_args;    // frozenset or NULL
    PyObject *unhashable_args;  // tuple or NULL
    PyObject *parameters;
    PyObject *weakreflist;
} unionobject;

args is the ordered, deduplicated tuple of members, in the order they were first seen. This is what __args__ exposes and what repr iterates.
hashable_args is a frozenset of the members that hash successfully. It exists so that two unions can be compared/hashed cheaply.
unhashable_args is a tuple of members that do not hash (e.g. lists, or types containing unhashable parameters). It may be NULL.
parameters is lazily computed (type variables found in args), guarded by a critical section.
weakreflist supports weakref.ref(union).

The type: `_PyUnion_Type`

c
// Objects/unionobject.c
PyTypeObject _PyUnion_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    .tp_name = "typing.Union",
    .tp_doc = PyDoc_STR("Represent a union type\n\nE.g. for int | str"),
    .tp_basicsize = sizeof(unionobject),
    .tp_dealloc = unionobject_dealloc,
    .tp_alloc = PyType_GenericAlloc,
    .tp_free = PyObject_GC_Del,
    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
    .tp_traverse = union_traverse,
    .tp_hash = union_hash,
    .tp_getattro = union_getattro,
    .tp_members = union_members,        // __args__
    .tp_methods = union_methods,        // __mro_entries__, __class_getitem__
    .tp_richcompare = union_richcompare,
    .tp_as_mapping = &union_as_mapping, // __getitem__
    .tp_as_number = &union_as_number,   // __or__
    .tp_repr = union_repr,
    .tp_getset = union_properties,      // __name__, __qualname__, __origin__, __parameters__
    .tp_weaklistoffset = offsetof(unionobject, weakreflist),
};

Key points:

tp_name is "typing.Union" even though Python exposes it as types.UnionType. types.UnionType = type(int | str) (see Lib/types.py), and _typesmodule.c exports _PyUnion_Type under the name "UnionType".
It is a GC type (Py_TPFLAGS_HAVE_GC, tp_traverse, tp_free = PyObject_GC_Del), because it owns references to arbitrary objects.
It is not a heap type and is statically allocated, so it is immortal and safe to export with EXPORT_STATIC_TYPE.
tp_weaklistoffset enables weak references.

It is exported here:

c
// Modules/_typesmodule.c
EXPORT_STATIC_TYPE("UnionType", _PyUnion_Type);

Deallocation and GC

c
// Objects/unionobject.c
static void
unionobject_dealloc(PyObject *self)
{
    unionobject *alias = (unionobject *)self;

    _PyObject_GC_UNTRACK(self);
    FT_CLEAR_WEAKREFS(self, alias->weakreflist);

    Py_XDECREF(alias->args);
    Py_XDECREF(alias->hashable_args);
    Py_XDECREF(alias->unhashable_args);
    Py_XDECREF(alias->parameters);
    Py_TYPE(self)->tp_free(self);
}

static int
union_traverse(PyObject *self, visitproc visit, void *arg)
{
    unionobject *alias = (unionobject *)self;
    Py_VISIT(alias->args);
    Py_VISIT(alias->hashable_args);
    Py_VISIT(alias->unhashable_args);
    Py_VISIT(alias->parameters);
    return 0;
}

FT_CLEAR_WEAKREFS clears weak references before freeing. tp_free is PyObject_GC_Del, matching GC allocation.

Equality and hashing

A union is hashable only if all of its members are hashable. The split into hashable_args (a frozenset) and unhashable_args (a tuple) lets equality and hashing be computed without re-hashing members on every call:

c
// Objects/unionobject.c
static Py_hash_t
union_hash(PyObject *self)
{
    unionobject *alias = (unionobject *)self;
    if (alias->unhashable_args) {
        // Attempt to get an error from one of the values.
        assert(PyTuple_CheckExact(alias->unhashable_args));
        Py_ssize_t n = PyTuple_GET_SIZE(alias->unhashable_args);
        for (Py_ssize_t i = 0; i < n; i++) {
            PyObject *arg = PyTuple_GET_ITEM(alias->unhashable_args, i);
            Py_hash_t hash = PyObject_Hash(arg);
            if (hash == -1) {
                return -1;
            }
        }
        // The unhashable values somehow became hashable again. Still raise
        // an error.
        PyErr_Format(PyExc_TypeError, "union contains %zd unhashable elements", n);
        return -1;
    }
    return PyObject_Hash(alias->hashable_args);
}

unions_equal first compares the frozensets, then (if both sides have unhashable members) checks mutual containment of the unhashable tuples. This makes int | str == str | int true while still distinguishing unions that differ only in unhashable members.

union_richcompare only handles ==/!= between two unions; anything else returns NotImplemented.

Building a union: `unionbuilder`

Construction is not done by directly filling the struct. Instead a small builder accumulates members, deduplicates them, flattens nested unions, and collapses single-member results:

c
// Objects/unionobject.c
typedef struct {
    PyObject *args;            // list
    PyObject *hashable_args;   // set
    PyObject *unhashable_args; // list or NULL
    bool is_checked;           // whether to call type_check()
} unionbuilder;

unionbuilder_init creates an empty args list and an empty hashable set. unionbuilder_add_single is the core:

c
// Objects/unionobject.c
static bool
unionbuilder_add_single(unionbuilder *ub, PyObject *arg)
{
    if (Py_IsNone(arg)) {
        arg = (PyObject *)&_PyNone_Type;  // immortal, so no refcounting needed
    }
    else if (_PyUnion_Check(arg)) {
        PyObject *args = ((unionobject *)arg)->args;
        return unionbuilder_add_tuple(ub, args);  // flatten nested unions
    }
    if (ub->is_checked) {
        PyObject *type = type_check(arg, "Union[arg, ...]: each arg must be a type.");
        if (type == NULL) {
            return false;
        }
        bool result = unionbuilder_add_single_unchecked(ub, type);
        Py_DECREF(type);
        return result;
    }
    else {
        return unionbuilder_add_single_unchecked(ub, arg);
    }
}

Two important behaviors:

None is normalized to NoneType (_PyNone_Type), so int | None becomes int | NoneType.
Nested unions are flattened: adding an existing UnionType splices its args tuple into the new builder, so (int | str) | float is the same as int | str | float.

unionbuilder_add_single_unchecked does the dedup:

c
// Objects/unionobject.c
static bool
unionbuilder_add_single_unchecked(unionbuilder *ub, PyObject *arg)
{
    Py_hash_t hash = PyObject_Hash(arg);
    if (hash == -1) {
        PyErr_Clear();
        if (ub->unhashable_args == NULL) {
            ub->unhashable_args = PyList_New(0);
            ...
        }
        else {
            int contains = PySequence_Contains(ub->unhashable_args, arg);
            if (contains < 0) return false;
            if (contains == 1) return true;   // duplicate, skip
        }
        if (PyList_Append(ub->unhashable_args, arg) < 0) return false;
    }
    else {
        int contains = PySet_Contains(ub->hashable_args, arg);
        if (contains < 0) return false;
        if (contains == 1) return true;       // duplicate, skip
        if (PySet_Add(ub->hashable_args, arg) < 0) return false;
    }
    return PyList_Append(ub->args, arg) == 0;
}

Hashable members go into a set for O(1) dedup; unhashable members fall back to linear PySequence_Contains. Either way, args (the ordered list) only gets the member if it is new.

make_union finalizes:

c
// Objects/unionobject.c
static PyObject *
make_union(unionbuilder *ub)
{
    Py_ssize_t n = PyList_GET_SIZE(ub->args);
    if (n == 0) {
        PyErr_SetString(PyExc_TypeError, "Cannot take a Union of no types.");
        ...
        return NULL;
    }
    if (n == 1) {
        PyObject *result = PyList_GET_ITEM(ub->args, 0);
        Py_INCREF(result);
        unionbuilder_finalize(ub);
        return result;          // collapse single-member "union" to the member
    }
    ... // build args tuple, hashable frozenset, unhashable tuple
    unionobject *result = PyObject_GC_New(unionobject, &_PyUnion_Type);
    ...
    _PyObject_GC_TRACK(result);
    return (PyObject*)result;
}

So int | int evaluates to int, and int | with no arguments is an error. The single-member collapse is what makes int | int is int true.

Entry points

`X | Y` (binary `|`)

type and GenericAlias both install _Py_union_type_or as their nb_or:

c
// Objects/typeobject.c
static PyNumberMethods type_as_number = {
    .nb_or = _Py_union_type_or,
};

// Objects/genericaliasobject.c
... .nb_or = _Py_union_type_or ...

_Py_union_type_or first checks is_unionable:

c
// Objects/unionobject.c
static int
is_unionable(PyObject *obj)
{
    if (obj == Py_None ||
        PyType_Check(obj) ||
        PySentinel_Check(obj) ||
        _PyGenericAlias_Check(obj) ||
        _PyUnion_Check(obj) ||
        Py_IS_TYPE(obj, &_PyTypeAlias_Type)) {
        return 1;
    }
    return 0;
}

PyObject *
_Py_union_type_or(PyObject* self, PyObject* other)
{
    if (!is_unionable(self) || !is_unionable(other)) {
        Py_RETURN_NOTIMPLEMENTED;   // lets normal __or__ / TypeError handling proceed
    }
    unionbuilder ub;
    // unchecked because we already checked is_unionable()
    if (!unionbuilder_init(&ub, false)) return NULL;
    if (!unionbuilder_add_single(&ub, self) ||
        !unionbuilder_add_single(&ub, other)) {
        unionbuilder_finalize(&ub);
        return NULL;
    }
    PyObject *new_union = make_union(&ub);
    return new_union;
}

Because it returns NotImplemented for non-unionable operands, int | 5 falls through to the default int.__or__, which raises TypeError. The builder is unchecked here (is_checked = false), so members are stored as-is rather than being run through type_check.

`typing.Union[X, Y]` and `UnionType[X, Y]`

c
// Objects/unionobject.c
static PyObject *
union_class_getitem(PyObject *cls, PyObject *args)
{
    return _Py_union_from_tuple(args);
}

PyObject *
_Py_union_from_tuple(PyObject *args)
{
    unionbuilder ub;
    if (!unionbuilder_init(&ub, true)) return NULL;   // checked
    if (PyTuple_CheckExact(args)) {
        if (!unionbuilder_add_tuple(&ub, args)) { ... }
    }
    else {
        if (!unionbuilder_add_single(&ub, args)) { ... }
    }
    return make_union(&ub);
}

__class_getitem__ is registered as a classmethod, so types.UnionType[int, str] works. The builder is checked (is_checked = true), meaning each member passes through type_check:

c
// Objects/unionobject.c
static PyObject *
type_check(PyObject *arg, const char *msg)
{
    if (Py_IsNone(arg)) {
        return (PyObject *)Py_TYPE(arg);   // None -> NoneType
    }
    if (is_unionable(arg)) {
        return Py_NewRef(arg);
    }
    PyObject *message_str = PyUnicode_FromString(msg);
    PyObject *args[2] = {arg, message_str};
    PyObject *result = call_typing_func_object("_type_check", args, 2);
    Py_DECREF(message_str);
    return result;
}

Fast path for already-unionable objects; otherwise it calls typing._type_check (which may raise TypeError for invalid members). This is why Union[int, "str"] (string forward reference) can resolve, while Union[int, 42] raises.

Substitution: `union.getitem`

Unions support U[int] to substitute type variables:

c
// Objects/unionobject.c
static PyObject *
union_getitem(PyObject *self, PyObject *item)
{
    unionobject *alias = (unionobject *)self;
    if (union_init_parameters(alias) < 0) return NULL;

    PyObject *newargs = _Py_subs_parameters(self, alias->args,
                                            alias->parameters, item);
    if (newargs == NULL) return NULL;

    PyObject *res = _Py_union_from_tuple(newargs);
    Py_DECREF(newargs);
    return res;
}

Parameters are populated lazily and cached under a critical section:

c
// Objects/unionobject.c
static int
union_init_parameters(unionobject *alias)
{
    int result = 0;
    Py_BEGIN_CRITICAL_SECTION(alias);
    if (alias->parameters == NULL) {
        alias->parameters = _Py_make_parameters(alias->args);
        if (alias->parameters == NULL) result = -1;
    }
    Py_END_CRITICAL_SECTION();
    return result;
}

So U[T][int] rebuilds the union from substituted args via _Py_union_from_tuple.

Repr

c
// Objects/unionobject.c
static PyObject *
union_repr(PyObject *self)
{
    unionobject *alias = (unionobject *)self;
    Py_ssize_t len = PyTuple_GET_SIZE(alias->args);
    Py_ssize_t estimate = (len <= PY_SSIZE_T_MAX / 6) ? len * 6 : len;
    PyUnicodeWriter *writer = PyUnicodeWriter_Create(estimate);
    ...
    for (Py_ssize_t i = 0; i < len; i++) {
        if (i > 0 && PyUnicodeWriter_WriteASCII(writer, " | ", 3) < 0) goto error;
        PyObject *p = PyTuple_GET_ITEM(alias->args, i);
        if (_Py_typing_type_repr(writer, p) < 0) goto error;
    }
    return PyUnicodeWriter_Finish(writer);
    ...
}

Members are rendered with _Py_typing_type_repr, joined by " | ". That helper is what turns _PyNone_Type back into NoneType and handles generics.

Attributes and properties

c
// Objects/unionobject.c
static PyMemberDef union_members[] = {
    {"__args__", _Py_T_OBJECT, offsetof(unionobject, args), Py_READONLY},
    {0}
};

static PyGetSetDef union_properties[] = {
    {"__name__", union_name, ...},       // "Union"
    {"__qualname__", union_name, ...},    // "Union"
    {"__origin__", union_origin, ...},    // always _PyUnion_Type
    {"__parameters__", union_parameters, ...},
    {0}
};

__args__ is a read-only member pointing directly at args. __parameters__ is lazily initialized (see above). __mro_entries__ raises TypeError, so unions cannot be subclassed.

union_getattro special-cases __module__, forwarding it to the type object, for compatibility with the typing module.

Comparison with `typing.Union`

types.UnionType is the C implementation; typing.Union is the legacy pure-Python form. Modern code paths (int | str, Union[int, str], types.UnionType[...]) all funnel through _PyUnion_Type. The typing module still provides _type_check and _type_repr-adjacent helpers, but the object itself, its hashing, equality, substitution, and GC are all in C.

Memory layout

text

unionobject (GC object)
+----------------------------+
| ob_refcnt / ob_type ...    |   PyObject_HEAD
+----------------------------+
| args            -> tuple   |
| hashable_args   -> frozenset (or NULL) |
| unhashable_args -> tuple (or NULL)     |
| parameters      -> tuple (lazy, or NULL) |
| weakreflist     -> weakref list (or NULL) |
+----------------------------+

Allocated with PyObject_GC_New and freed with PyObject_GC_Del; tracked by the GC from creation (_PyObject_GC_TRACK).

Key takeaways

types.UnionType is _PyUnion_Type, defined in Objects/unionobject.c and exported by Modules/_typesmodule.c.
A union is a GC-tracked struct holding an ordered args tuple plus a hashable frozenset and an optional unhashable tuple, plus lazy parameters and a weakref list.
unionbuilder flattens nested unions, normalizes None to NoneType, deduplicates members (set for hashable, linear scan for unhashable), and collapses single-member results.
X | Y routes through type.__or__ / GenericAlias.__or__ = _Py_union_type_or (unchecked builder); Union[X, Y] routes through __class_getitem__ = _Py_union_from_tuple (checked builder, calls typing._type_check).
U[item] substitutes parameters and rebuilds the union.
Equality compares frozensets plus mutual containment of unhashable members; hashing fails if any member is unhashable.
Unions cannot be subclassed (__mro_entries__ raises).

The struct: unionobject

The type: _PyUnion_Type