View mode: basic / threaded / horizontal-split · Log in · Help
January 08, 2012
Re: associative arrays
Jonathan M Davis wrote:

> In this case, it's very much like dealing with C++ iterators

A relevant part of Andrei's thread on "associative arrays iteration":

http://www.digitalmars.com/d/archives/digitalmars/D/associative_arrays_
iteration_is_finally_here_99576.html#N99614

-manfred
January 08, 2012
Re: associative arrays
On 08.01.2012 14:40, Jonathan M Davis wrote:
> On Sunday, January 08, 2012 14:24:32 simendsjo wrote:
>> Thanks for your clarifications.
>>
>> Does this mean even this is undefined?
>> aa["a"] = new C();
>> auto c = "a" in aa;
>> aa["b"] = new C();
>> // Using c here is undefined as an element was added to aa
>
> Yes. Depending on the current implementation of AAs and the state of aa when
> "b" is added to it, c could still point to exactly what it did before, or aa
> could have been rehashed, which could move any or all of its elements around,
> in which case who knows what c points to.
>
> - Jonathan M Davis

Thanks! You've saved me a couple of future bugs :)
January 08, 2012
Re: associative arrays
On Sunday, January 08, 2012 14:57:51 simendsjo wrote:
> On 08.01.2012 14:40, Jonathan M Davis wrote:
> > On Sunday, January 08, 2012 14:24:32 simendsjo wrote:
> >> Thanks for your clarifications.
> >> 
> >> Does this mean even this is undefined?
> >> aa["a"] = new C();
> >> auto c = "a" in aa;
> >> aa["b"] = new C();
> >> // Using c here is undefined as an element was added to aa
> > 
> > Yes. Depending on the current implementation of AAs and the state of aa
> > when "b" is added to it, c could still point to exactly what it did
> > before, or aa could have been rehashed, which could move any or all of
> > its elements around, in which case who knows what c points to.
> > 
> > - Jonathan M Davis
> 
> Thanks! You've saved me a couple of future bugs :)

No problem. It's a bit like how an array could be reallocated after you append 
to it, which causes slices to no longer point to that array, except that 
unlike the slice the pointer may not point to valid memory. Given that it's 
managed by the GC, it probably isn't pointing to complete garbage, but it 
could be used for something else now.

In general, if you insert or remove elements from a container, you must be 
very careful about any references to the data within the container - be they 
pointers to elements in the container, or iterators or ranges for the 
container. That's why std.container has the stable functions. They guarantee 
that the container's existing ranges don't get invalidated when they're 
called, whereas the ones that aren't stable make no such guarantees. The 
issues with in are just one of the manifestations of the more general issue.

- Jonathan M Davis
January 08, 2012
Re: associative arrays
Based on these arguments does that mean std.file.remove should 
not be throwing when a file doesn't exist?

Or more precisely should I add a bugzilla entry to change this. I 
certainly have a lot of if(exists) remove() in my code and end up 
having to change where I just use remove().

On Sunday, 8 January 2012 at 05:03:45 UTC, Manfred Nowak wrote:
> Jonathan M Davis wrote:
>
>> So, as far as I can tell, the current situation is more 
>> efficient
>
> There are some more arguments:
>
> 1) Different threads might want to `remove' the same key from 
> the AA. I don't see a reason why only the first served thread 
> should complete the operation without an error.
>
> 2) Because there is only one operation for insertion of a key 
> into an AA, only one operation should be used for removing that 
> key.
>
> Note: This argument vanishes if insertions are divided in
> a:declaration of a key as valid in that AA,
> b:first assignment to the value of a key,
> c:reassignment to the value of a key
>
> 3) Reverse operations should not implement more functionality 
> than the reversed operation. Because `remove' is the reverse 
> operation for inserting a key and that operation does not cause 
> any error, neither should errors be given from `remove'.
>
> Note: Reassigning to the value of a key might very well treated 
> as an error.
>
> -manfred
January 08, 2012
Re: associative arrays
Very interesting discussion. Tk u all.
January 09, 2012
Re: associative arrays
Looks like this is fixed for 2.058.

https://github.com/D-Programming-Language/dmd/commit/3e23b0f5834acb32eaee20d88c30ead7e03bb2f4

On 08/01/2012 3:43 AM, Jonathan M Davis wrote:
> On Sunday, January 08, 2012 03:24:22 Kapps wrote:
>> Ah, found the bug / pull request.
>>
>> https://github.com/D-Programming-Language/dmd/pull/597
>> http://d.puremagic.com/issues/show_bug.cgi?id=4523
>
> Ah, TDPL says that it returns bool. Well, then it definitely needs to be
> changed, and it's good to see that that there's a pull request for it. So, it
> should be fixed in the next release. In fact, the number of TDPL-related bugs
> fixed for the next release should be quite high, which is great.
>
> - Jonathan M Davis
January 09, 2012
Re: associative arrays
> assert(key in aa);
> aa.remove(key);
>
> So, as far as I can tell, the current situation is more efficient, and it
> doesn't cost you any expressiveness. You can still have an exception thrown
> when remove fails if you use enforce before the call if you want an exception
> thrown when the element isn't there.

but then it should be called optional_remove - because it "mabye" removes

its like file_delete, DeleteFile (and all the others) on non existing 
files - why is there an exception/error neeeded if missing?

the "maybe"-situation is not that often used in good code - because you 
can't find your errors if many routines would work like remove
January 09, 2012
Re: associative arrays
On Sun, 08 Jan 2012 08:40:27 -0500, Jonathan M Davis <jmdavisProg@gmx.com>  
wrote:

> On Sunday, January 08, 2012 14:24:32 simendsjo wrote:
>> Thanks for your clarifications.
>>
>> Does this mean even this is undefined?
>> aa["a"] = new C();
>> auto c = "a" in aa;
>> aa["b"] = new C();
>> // Using c here is undefined as an element was added to aa
>
> Yes. Depending on the current implementation of AAs and the state of aa  
> when
> "b" is added to it, c could still point to exactly what it did before,  
> or aa
> could have been rehashed, which could move any or all of its elements  
> around,
> in which case who knows what c points to.

Actually, not invalid for the current implementation.  I don't know if  
it's stated whether an AA specifically requires that elements do not  
re-associate on a rehash.

There are certain hash implementations (such as ones that involve a single  
array), which would invalidate pointers on a rehash.  So there is the  
potential (if it's not a stated requirement to the contrary in the spec)  
that some future AA implementation would invalidated references.  However,  
I'd say it's unlikely this would happen.

BTW, dcollections' HashMap, HashSet, and HashMultiset do guarantee that  
adding elements does not invalidated cursors (dcollections' safe version  
of pointers) as long as you use the default Hash implementation.  However,  
I just noticed this is not stated anywhere in the docs (will fix).



-Steve
January 09, 2012
Re: associative arrays
On Monday, January 09, 2012 09:25:14 Steven Schveighoffer wrote:
> Actually, not invalid for the current implementation. I don't know if
> it's stated whether an AA specifically requires that elements do not
> re-associate on a rehash.

Well, like I said, it depends on the current implementation. There are hash 
table implementations where rehashing would invalidate the pointer returned by 
in, and I don't believe that the spec specificies that D's AA guarantees that 
rehashing doesn't do that. So in the future, it _could_ be changed to an 
implementation which invalidates the pointers on rehash. As such, it doesn't 
really matter what the current implementation does. Relying on the current 
behavior is unsafe if it's not guaranteed by the spec. Now, if we want to 
change the spec to make such guarantees, that's fine, but I don't believe it 
makes them right now. Good to know what the current implementation is doing 
though.

- Jonathan m Davis
January 09, 2012
Re: associative arrays
On 1/9/12, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> BTW, dcollections' HashMap, HashSet, and HashMultiset do guarantee that
> adding elements does not invalidated cursors (dcollections' safe version
> of pointers) as long as you use the default Hash implementation.  However,
> I just noticed this is not stated anywhere in the docs (will fix).

Funny, I was looking at the docs a few days ago and it said "Adding an
element can invalidate cursors depending on the implementation.", so I
just assumed it did invalidate the cursors.

I do think those are dcollections v1 docs though. Anyway glad to hear
from you about this.
1 2 3 4 5
Top | Discussion index | About this forum | D home