list.d

module persistent_list;

debug import std.stdio;

// NB: no dynamic allocator instance, everything that deals with immutability
// warrants maximum specialization to be maintainable

struct PersistentList(T, alias allocator)
{
    import std.exception : enforce;
    import std.experimental.allocator;

    static assert (
        is(T == immutable),
        "Pesistent data structures may only contain immutable data"
    );

    static assert(
        !is(typeof(this) == immutable),
        "PersistentList itself must be mutable for allocation / RC purposes"
    );

    private
    {
        struct Node
        {
            // TODO: may need to be stored as T*
            // and managed by different allocator. Managing immutable and
            // mutable memory in same blocks feels like trouble.

            T payload;
            Node* next;
            long refs;

            invariant () { assert(this.refs >= 0); }

            void incRef()
            {
                ++this.refs;
                debug writefln("inc %x to %s", &this, this.refs);
            }

            void decRef() @trusted
            {
                --this.refs;
                debug writefln("dec %x to %s", &this, this.refs);
                if (this.refs == 0)
                {
                    if (this.next)
                        this.next.decRef();
                    destroy(this);
                    allocator.deallocate((cast(void*) &this)[0 .. Node.sizeof]);
                }
            }

            static Node* create(T value)
            {
                import std.traits : Unqual;

                auto node = cast(Node*) allocator.allocate(Node.sizeof);
                debug writefln("creating %x", node);
                // this is currently unclear bit in immutable specification,
                // technically even immediate modification like this can be
                // UB if allocator placed immutable data in RO memory
                * (cast(Unqual!T*) &node.payload) = value;
                node.refs = 0;
                node.next = null;
                node.incRef();
                return node;
            }
        }

        Node* root;

        void incRef()
        {
            if (this.root)
                this.root.incRef();
        }

        void decRef()
        {
            if (this.root)
                this.root.decRef();
        }
    }


    this(this)
    {
        this.incRef();
    }

    ~this()
    {
        this.decRef();
    }

    this(Node* node = null)
    {
        if (node)
            node.incRef();
        this.root = node;
    }

    static auto create(U...)(U values)
    {
        PersistentList instance;

        if (values.length == 0)
            return instance;

        Node** place_into = &instance.root;

        foreach (i, _; U)
        {
            // reverse the order so that appending can be done without
            // affecting existing aliases. not clear if it is practical
            // with RC approach
            auto node = Node.create(values[$ - i - 1]);
            *place_into = node;
            place_into = &node.next;
        }

        return instance;
    }

    PersistentList removeLast()
    {
        enforce(this.root);
        return PersistentList(this.root.next);
    }

    PersistentList opBinary(string op)(T head)
        if (op == "~")
    {
        auto node = Node.create(head);
        node.next = this.root;
        this.incRef();

        PersistentList instance;
        instance.root = node;
        return instance;
    }

    // NB: this relies on "const == scope" convention and doesn't additionally
    // increase refcount for const slice

    auto opSlice() const
    {
        static struct Range
        {
            // will iterate in reverse because of how nodes are stored
            // not sure if it needs to be fixed and if yes - how

            private
            {
                const(Node)* element;
            }

            bool empty() const
            {
                return this.element is null;
            }

            ref T front() const
            {
                assert(this.element !is null);
                return this.element.payload;
            }

            void popFront()
            {
                assert(!this.empty());
                this.element = this.element.next;
            }
        }

        return Range(this.root);
    }
}

import std.experimental.allocator;
import std.experimental.allocator.mallocator;

shared Mallocator allocator;

alias List = PersistentList!(immutable int, allocator);

void print(const List list)
{
    import std.stdio;
    writeln(list[]);
}

unittest
{
    auto list = List();
    print(list);
}

unittest
{
    auto list = List.create(42, 43, 44);
    print(list);
}

unittest
{
    auto list = List.create(42, 43, 44);
    auto list2 = list ~ 50;
    print(list);
    print(list2);
}