[Issue 3930] New: AAs horribly broken

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=3930

           Summary: AAs horribly broken
           Product: D
           Version: 2.041
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Severity: regression
          Priority: P1
         Component: druntime
        AssignedTo: s...@invisibleduck.org
        ReportedBy: dsim...@yahoo.com


--- Comment #0 from David Simcha <dsim...@yahoo.com> 2010-03-10 20:17:54 PST ---
The following code tests the builtin associative array by comparing its
behavior to the behavior of an AA implemented via linear search.  It works on
2.040 but produces an access violation on 2.041.

import std.stdio, std.random;

// Quick, dirty and inefficient AA using linear search, useful for testing.
struct LinearAA(K, V) {
    K[] keys;
    V[] values;

    V opIndex(K key) {
        foreach(i, k; keys) {
            if(k == key) {
                return values[i];
            }
        }

        assert(0, "Key not present.");
    }

    V opIndexAssign(V val, K key) {
        foreach(i, k; keys) {
            if(k == key) {
                return values[i] = val;
            }
        }

        keys ~= key;
        values ~= val;
        return val;
    }

    V* opIn_r(K key) {
        foreach(i, k; keys) {
            if(key == k) {
                return values.ptr + i;
            }
        }

        return null;
    }

    void remove(K key) {
        size_t i = 0;
        for(; i < keys.length; i++) {
            if(keys[i] == key) {
                break;
            }
        }

        assert(i < keys.length);

        for(; i < keys.length - 1; i++) {
            keys[i] = keys[i + 1];
            values[i] = values[i + 1];
        }

        keys = keys[0..$ - 1];
        values = values[0..$ - 1];
    }

    uint length() {
        return values.length;
    }
}

void main() {
    foreach(iter; 0..10) {  // Bug only happens after a few iterations.
        writeln(iter);
        uint[uint] builtin;
        LinearAA!(uint, uint) linAA;
        uint[] nums = new uint[100_000];
        foreach(ref num; nums) {
            num = uniform(0U, uint.max);
        }

        foreach(i; 0..10_000) {
            auto index = uniform(0, nums.length);
            if(index in builtin) {
                assert(index in linAA);
                assert(builtin[index] == nums[index]);
                assert(linAA[index] == nums[index]);
                builtin.remove(index);
                linAA.remove(index);
            } else {
                assert(!(index in linAA));
                builtin[index] = nums[index];
                linAA[index] = nums[index];
            }
        }

        assert(builtin.length == linAA.length);
        foreach(k, v; builtin) {
            assert(k in linAA);
            assert(*(k in builtin) == *(k in linAA));
            assert(linAA[k] == v);
        }
    }
}

This is probably related to Bug 3929.  Since the current builtin AA
implementation uses free() quite liberally as a practical necessity due to
false pointer issues, we see some very subtle, hard to reproduce bugs.  (The
only way I can reproduce them is by monte carlo unittesting different AA
implementations against each other like above.  Even then it depends somewhat
sensitively on what code was executed previously, hence the multiple
iterations.)  For me, this is a blocker for using this version of DMD, as the
project I'm working on lately uses AAs very heavily.  I think this is severe
enough to merit its own release.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------