Safe interval pointer [Was: Re: Perfect hashing for string switch]

[bearophile]

Matti Niemenmaa:
> Your test6 is invalid: it reads beyond the bounds of the given array. 
> For example with input "th", it will check whether the third character 
> is 'i'; but the length of the array is only 2, so it shouldn't be doing 
> that.

Shame on me, I am sorry -.- Thank you. I will try to improve the code later.

The good thing is that D2 allows me to implement something to catch that kind of out-of-range pointer errors at run-time (D1 is not good enough here). That code at the bottom is not well tested yet, so it can contain many bugs. And probably it's not const-aware yet (if someone has suggestions to improve it I will appreciate them). In programs a certain percentage of pointers run inside an interval of memory, so something like this can be useful. Do you think this is (once well debugged and improved) useful for Phobos2?

Up sides:
- this code seems to work and catchs the bug at runtime in the test6() function I've written.

Downsides:
- currently compiled with D2 the test6() gets slower even when the code is not in debug release. Future D2 compilers will need to reduce to zero or near zero this overhead, so safer pointers can be used more freely.

Possible future improvements: use an "interval tree" where necessary to quickly find if the pointer is inside more than one interval. This is probably a quite less common need.

Bye,
bearophile

---------------------

import std.stdio: writeln, write;


template IsMutable(T) {
    enum bool IsMutable = __traits(compiles, { T a; a = T.init; });
}

unittest { // of IsMutable(T)
    auto s1 = "hello1";
    static assert( !IsMutable!(typeof(s1[0])) );

    char[] s2 = cast(char[])"hello2";
    static assert( IsMutable!(typeof(s2[0])) );
}


/// ***** NOT tested well enough yet *****
struct IntervalPtr(T) {
    T* ptr; // can be null

    debug {
        private T* start_ptr; // can't be null if present
        private T* end_ptr;   // can't be null if present

        invariant() {
            assert(start_ptr != null);
            assert(end_ptr != null);
            assert(start_ptr <= end_ptr);
            assert(ptr == null || (ptr >= start_ptr && ptr < end_ptr));
        }
    } else {
        this(T* aptr) {
            this.ptr = aptr;
        }
    }

    this(T* start, T* end) {
        this.ptr = start;
        debug {
            assert(start != null);
            assert(end != null);
            assert(start <= end);
            this.start_ptr = start;
            this.end_ptr = end;
        }
    }

    this(T* start, T* end, T* aptr) {
        this.ptr = aptr;
        debug {
            assert(end != null);
            assert(end != null);
            assert(start <= end);
            if (aptr != null) {
                assert(aptr >= start);
                assert(aptr < end);
            }
            this.start_ptr = start;
            this.end_ptr = end;
        }
    }

    T opStar() {
        return *this.ptr;
    }

    void opPostInc() {
        debug assert(this.ptr < (this.end_ptr - 1));
        this.ptr++;
    }

    void opPostDec() {
        debug assert(this.ptr > this.start_ptr);
        this.ptr--;
    }

    void opAddAssign(size_t i) {
        debug assert(this.ptr < (this.end_ptr - i));
        this.ptr += i;
    }

    void opSubAssign(size_t i) {
        debug assert(this.ptr >= (this.start_ptr + i));
        this.ptr -= i;
    }

    void opAssign(T* other_ptr) {
        debug {
            if (other_ptr != null) {
                assert(other_ptr >= this.start_ptr);
                assert(other_ptr < this.end_ptr);
            }
        }
        this.ptr = other_ptr;
    }

    void opAssign(IntervalPtr other) {
        debug {
            assert(other.start_ptr != null);
            assert(other.end_ptr != null);
            assert(other.end_ptr != null);
            if (other.ptr != null) {
                assert(other.ptr >= other.start_ptr);
                assert(other.ptr < other.end_ptr);
            }
            this.start_ptr = other.start_ptr;
            this.end_ptr = other.end_ptr;
        }
        this.ptr = other.ptr;
    }

    const bool opEquals(ref const(IntervalPtr) other) {
        return this.ptr == other.ptr;
    }

    /*ref ?*/ T opIndex(size_t i) {
        debug {
            assert((this.ptr + i) >= this.start_ptr);
            assert((this.ptr + i) < this.end_ptr);
        }
        return this.ptr[i];
    }

    static if (IsMutable!T) {
        void opIndexAssign(T value, size_t i) {
            debug {
                assert((this.ptr + i) >= this.start_ptr);
                assert((this.ptr + i) < this.end_ptr);
            }
            this.ptr[i] = value;
        }
    }
}


IntervalPtr!T intervalPtr(T)(/*inout ?*/ T[] arr) {
    debug
        return IntervalPtr!T(arr.ptr, arr.ptr + arr.length);
    else
        return IntervalPtr!T(arr.ptr);
}

IntervalPtr!T intervalPtr(T)(/*inout ?*/ T[] arr, T* aptr) {
    debug
        return IntervalPtr!T(arr.ptr, arr.ptr + arr.length, aptr);
    else
        return IntervalPtr!T(aptr);
}

IntervalPtr!T intervalPtr(T)(T* start, T* end) {
    debug
        return IntervalPtr!T(start, end);
    else
        return IntervalPtr!T(start);
}

IntervalPtr!T intervalPtr(T)(T* start, T* end, T* aptr) {
    debug
        return IntervalPtr!T(start, end, aptr);
    else
        return IntervalPtr!T(aptr);
}


void main() {
    auto s = "hello";
    writeln("String: ", s);
    auto p1 = s.intervalPtr();
    writeln("intervalPtr sizeof: ", p1.sizeof);

    foreach (_; 0 .. 4) {
        write(">", *p1, "< ");
        ++p1;
    }
    writeln(">", *p1, "< ");

    auto p2 = intervalPtr(s.ptr, s.ptr + s.length);
    foreach (_; 0 .. 4) {
        write(">", *p2, "< ");
        p2++;
    }
    writeln(">", *p2, "< ");

    p1 = s.ptr; // p1 reset to the start
    foreach (i; 0 .. s.length)
        write(">", p1[i], "< ");
    writeln();
}