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

           Summary: [CTFE] AA rehash
           Product: D
           Version: future
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Keywords: rejects-valid
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2010-03-28 06:37:43 PDT ---
This program, with dmd 2.042:


int foo() {
    int[int] aa = [1: 1];
    aa.rehash;
    return 1;
}
enum _ = foo();
void main() {}


Generates the errors:
...\dmd\src\druntime\import\object.di(318): Error: cannot evaluate
_aaRehash(&this.p,(& D12TypeInfo_Hii6__initZ)) at compile time
test.d(3): Error: cannot evaluate aa.rehash() at compile time
test.d(6): Error: cannot evaluate foo() at compile time
test.d(6): Error: cannot evaluate foo() at compile time

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

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


Michael Rynn <y0uf00bar@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |y0uf00bar@gmail.com


--- Comment #1 from Michael Rynn <y0uf00bar@gmail.com> 2010-04-08 17:28:49 PDT ---
Regarding calls to _aaRehash(aaA* paa, TypeInfo keyti) from the .rehash property.  The D 2.042 passes to aaRehash a  TypeInfo instance that is inconsistent with other internal calls to it by _aaGet  .rehash passes the AA typeinfo, while _aaGet passes the key TypeInfo.

    private char* cstr(string s)
    {
        char[] buf = new char[s.length+1];

        uint slen = s.length;
        for(int si = 0; si < slen; si++)
        {
            buf[si] = s[si];
        }
        buf[slen] = 0;
        return buf.ptr;
    }

void* _aaRehash(AA* paa, TypeInfo keyti)
{
    BB newb;
//**************** stick these lines in, and you will see what I mean.., and
might be motivated to fix it soon.

    TypeInfo origti = paa.a.keyti;
    if (origti != keyti)
    {
        printf("wrong ti - need %s, not %s\n", cstr(origti.toString()),
cstr(keyti.toString()));
    }
//****************

More explanation ad nauseum.

_aaGet calls _aaRehash with the keyti it got (which is really the TypeInfo of the key), and caches it in struct BB. _d_assocarrayliteralT also figures out and caches the key TypeInfo from the TypeInfo_AssociativeArray.

_aaRehash is written so that it must use same key TypeInfo as aaGet, and _d_assocarrayliteralT, in the keyti.compare, otherwise, keys may end up differently ordered after a rehash, and subsequent searches may fail. I was very puzzled when this happened when testing .rehash. This bug has been present for some time now, so maybe .rehash is not frequently used.

When .rehash is called from D code, and _aaRehash is called with the TypeInfo of the AA , presumed to be a TypeInfo_AssociativeArray, and not that of the key.

This is just a bit more evidence that the AA C interface is old and rickety.

It could at least be made more consistent, and less dangerously redundent. _aaRehash should not need a TypeInfo passed to it at all.  It already has the correct keyti in struct BB, if there has been any entries added.

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

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



--- Comment #2 from Michael Rynn <y0uf00bar@gmail.com> 2010-04-08 18:22:50 PDT ---
// I feel obliged to submit a version of function _aaRehash that ignores the TypeInfo passed to it, to make the keyti argument redundent. ( druntime/src/rt/aaA.d).

void* _aaRehash(AA* paa, TypeInfo keyti)
{
    BB newb;

    TypeInfo origti;

    void _aaRehash_x(aaA* olde)
    {
        while (1)
        {
            auto left = olde.left;
            auto right = olde.right;
            olde.left = null;
            olde.right = null;

            aaA *e;

            //printf("rehash %p\n", olde);
            auto key_hash = olde.hash;
            size_t i = key_hash % newb.b.length;
            auto pe = &newb.b[i];
            while ((e = *pe) !is null)
            {
                //printf("\te = %p, e.left = %p, e.right = %p\n", e, e.left,
e.right);
                assert(e.left != e);
                assert(e.right != e);
                if (key_hash == e.hash)
                {
                    auto c = origti.compare(olde + 1, e + 1);
                    assert(c != 0);
                    pe = (c < 0) ? &e.left : &e.right;
                }
                else
                    pe = (key_hash < e.hash) ? &e.left : &e.right;
            }
            *pe = olde;

            if (right)
            {
                if (!left)
                {   olde = right;
                    continue;
                }
                _aaRehash_x(right);
            }
            if (!left)
                break;
            olde = left;
        }
    }

    //printf("Rehash\n");
    if (paa.a)
    {
        auto aa = paa.a;
        auto len = _aaLen(*paa);

        if (len)
        {
            size_t i;

            origti = aa.keyti;
            for (i = 0; i < prime_list.length - 1; i++)
            {
                if (len <= prime_list[i])
                    break;
            }
            len = prime_list[i];
            newb.b = new aaA*[len];

            foreach (e; aa.b)
            {
                if (e)
                    _aaRehash_x(e);
            }
            delete aa.b;

            newb.nodes = aa.nodes;
            newb.keyti = aa.keyti;
        }

        *paa.a = newb;
        _aaBalance(paa);
    }
    return (*paa).a;
}

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

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



--- Comment #3 from bearophile_hugs@eml.cc 2010-08-26 06:31:44 PDT ---
With dmd 2.048 the error message is a little different:

...\dmd\src\druntime\import\object.di(354): Error: _aaRehash cannot be
interpreted at compile time, because it has no available source code
test.d(3): Error: cannot evaluate aa.rehash() at compile time
test.d(6): Error: cannot evaluate foo() at compile time
test.d(6): Error: cannot evaluate foo() at compile time

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

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


Walter Bright <bugzilla@digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |bugzilla@digitalmars.com
         Resolution|                            |FIXED


--- Comment #4 from Walter Bright <bugzilla@digitalmars.com> 2011-08-03 17:15:06 PDT ---
https://github.com/D-Programming-Language/dmd/commit/9318dc44c3e9aa75907966b9fd122c0cc6700891

https://github.com/D-Programming-Language/dmd/commit/571661646ca420aa4c3fb348e86e35ed8faae624

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