[Issue 4625] New: "in" operator for AAs in SafeD code

[d-bugmail at puremagic.com]

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

           Summary: "in" operator for AAs in SafeD code
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: druntime
        AssignedTo: sean at invisibleduck.org
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-08-11 15:19:01 PDT ---
This comes after a short discussion in D.learn, where simendsjo in D.learn has
shown few examples.

I presume "in" done on an Associative Array currently returns a pointer to
remove dual AA lookup in a common situation:

auto ptr = x in aa;
if (ptr) {
    // do something with *ptr
} else {
    // do something else
}



But this code shows that it's hard to accept in SafeD the currently designed
"in" operator for associative arrays:

void main() {
    auto aa = [1 : 2];
    auto p1 = 1 in aa;
    aa.rehash;
    // p1 invalidated by rehashing

    auto p2 = 1 in aa;
    aa.remove(1);
    // p2 invalidated by removal
}


On the other hand "x in AA" is a basic operation that I need to perform in
SafeD code too.

I can see two possible solutions, but I like only the second one:

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

1) 

This first solutions needs two changes at the same time:
- "in" done on associative arrays always returns a bool, this is memory safe.
- improve the optimizer part of the compiler so it is able to remove most cases
of dual lookups in AAs.

If the compiler is naive then code like this:

if (x in aa) {
    auto value = aa[x];
    // ...
}

requires two searches inside the hash, the first to tell if the key is present,
and the second to find it again and fetch its value.

A better compiler (LDC1 is already able to do this) can recognize that the code
is performing two nearby key searches with the same key, and it can remove the
second one, essentially replacing that code with this one:

auto __tmp = x in aa;
if (__tmp) {
    auto value = *__tmp;
    // ...
}

If the key is removed or a rehash is performed, the compiler doesn't perform
that optimization. This is good in theory, but in practice sometimes there is
some distance between the first and second lookup, so I think sometimes the
compiler may not be able to optimize away the second lookup.

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

2) So I prefer a second solution that has less demands on the optimizer:

- Add to AAs a contains() method that always return a boolean.
- In SafeD code Disallow the "in" operator for AAs. So in SafeD code you can
use aa.contains().
- Improve the optimizer a bit so it's able to remove some cases of dual lookups
in AAs (both in SafeD and non SafeD code).

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