January 08, 2012
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
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
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
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
Very interesting discussion. Tk u all.
January 09, 2012
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
> 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
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
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
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