www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4021] New: [CTFE] AA rehash

reply d-bugmail puremagic.com writes:
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



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: -------
Mar 28 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4021


Michael Rynn <y0uf00bar gmail.com> changed:

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



---
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: -------
Apr 08 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4021




---
// 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: -------
Apr 08 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4021




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: -------
Aug 26 2010
prev sibling parent d-bugmail puremagic.com writes:
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



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: -------
Aug 03 2011