type check

t.cc

// Quoted from K. Palacz and J. Vitek, "Java Subtype Tests in Real-Time", ECOOP '03, 2003.
// CT for single subtyping. One particularly effective idea due to Cohen [7]
// is a variation of Dijkstra’s “displays” [10]. Each type is identified by
// a unique type identifier, tid, which is simply a number. The runtime type
// information data structure also records the complete path of each type to
// the root as a se- quence of type identifiers. The key trick is to build,
// for each type x, an array of card(ancestors(x)) type identifiers so that
// for each ancestor y, the tid of y is stored at an offset equal to level(y)
// in the array. With this encoding, type inclusion tests reduce to a
// bound-checked array access and a comparison opera- tion. The bound check
// is necessary if array sizes are not uniform. This approach is being used
// for extends checks in the Jikes RVM as described in [2] and in Wirth’s Oberon.

#include <iostream>
#include <cstdint>
#include <vector>

typedef uint8_t TypeIDInLevel;

class TypeRegistry {
public:
    uint8_t registerForLevel(uint32_t level)
    {
        if (level < m_currentMaxTypeIDInLevels.size())
            return m_currentMaxTypeIDInLevels[level]++;
        m_currentMaxTypeIDInLevels.resize(level + 1, 0);
        return m_currentMaxTypeIDInLevels[level]++;
    }

    std::vector<TypeIDInLevel> m_currentMaxTypeIDInLevels;
};

static TypeRegistry* typeRegistry()
{
    static TypeRegistry registry;
    return &registry;
}

class Type {
public:
    Type(const Type* parent)
        : m_parent(parent)
    {
        // init display
        if (!m_parent)
            m_display.push_back(typeRegistry()->registerForLevel(0));
        else {
            m_display = m_parent->m_display;
            m_display.push_back(typeRegistry()->registerForLevel(m_parent->level() + 1));
        }
    }

    const Type* parent() const
    {
        return m_parent;
    }

    uint32_t id() const
    {
        return m_display.back();
    }

    uint32_t level() const
    {
        return m_display.size() - 1;
    }

    bool instanceOf(const Type* ancestor) const
    {
        uint32_t ancestorLevel = ancestor->level();
        if (ancestorLevel >= level())
            return false;
        return m_display[ancestorLevel] == ancestor->id();
    }

private:
    const Type* m_parent;
    std::vector<TypeIDInLevel> m_display;
};

static const Type* Object()
{
    static const Type type(nullptr);
    return &type;
}

static const Type* Array()
{
    static const Type type(Object());
    return &type;
}

static const Type* DataView()
{
    static const Type type(Object());
    return &type;
}

static const Type* TypedArray()
{
    static const Type type(DataView());
    return &type;
}

static const Type* Date()
{
    static const Type type(Object());
    return &type;
}

int main(int argc, char** argv)
{
    std::cout << Object()->instanceOf(Array()) << std::endl;
    std::cout << Array()->instanceOf(Object()) << std::endl;
    std::cout << Date()->instanceOf(Object()) << std::endl;
    std::cout << Array()->instanceOf(Date()) << std::endl;
    std::cout << TypedArray()->instanceOf(DataView()) << std::endl;
    return 0;
}