www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9975] New: pointsTo asserts because of false pointer in union

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975

           Summary: pointsTo asserts because of false pointer in union
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: code dawg.eu



import std.exception;

struct S
{
    union
    {
        size_t sz;
        string s;
    }
}

void main()
{
    S a, b;
    a.sz = -1;
    assert(!pointsTo(a, b));
}

----

The problem is that pointsTo checks every .tupleof member thus the example
asserts because a.s pointsTo b.

http://www.digitalmars.com/d/archives/digitalmars/D/learn/overzealous_pointsTo_23203.html

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 21 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975


monarchdodra gmail.com changed:

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



But isn't this the expected behavior though?

By setting sz to -1, s becomes a string (dynamic array), that starts at null,
and spans size_t.max. So in that sense, b is inside a.sz, so a points to b.

Looking at the provided link, where it shows that non anonymous unions don't
show this "problem", I'm really tempted to say it actually reveils that
pointsTo *doesn't* support unions correctly, as *both* asserts should have
failed...

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975




https://github.com/D-Programming-Language/phobos/pull/1277

Fix Issue 9975 - pointsTo asserts because of false pointer in union

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 26 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975




Commit pushed to master at https://github.com/D-Programming-Language/dmd

https://github.com/D-Programming-Language/dmd/commit/7518f83d0082e5cd339ef5d7c215f13a0287ad4b
Do not include test case for issue 9975

It's not behavior that we guarantee.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975






 Commit pushed to master at https://github.com/D-Programming-Language/dmd
 
 https://github.com/D-Programming-Language/dmd/commit/7518f83d0082e5cd339ef5d7c215f13a0287ad4b
 Do not include test case for issue 9975
 
 It's not behavior that we guarantee.


The commit is not for this issue. Please ignore it.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975




Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/e44adcd9edfd025fa7074501e1743e54ecbbda33
Fix Issue 9975 - pointsTo asserts because of false pointer in union

https://github.com/D-Programming-Language/phobos/commit/af14a7f0aad058587fa498bbcdfd0ad84c204deb


Fix Issue 9975 - pointsTo asserts because of false pointer in union

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 16 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975




This function is used throughout std.algorithm so marking this as documented
behavior is not a good solution because it mean basic algorithms like sort
can't be used with such structs.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 17 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975






 This function is used throughout std.algorithm so marking this as documented
 behavior is not a good solution because it mean basic algorithms like sort
 can't be used with such structs.


Which behavior exactly are you mentioning? And do you mean *any* structs, or
just structs containing unions?

As far as documentation goes, all I added was that when doing pointsTo on a
union, you "could" get a false positive. I don't think there is any way around
it, since pointsTo would have no way to know *which* members to check.

That, and a false positive is always safer than a false negative.

In case of the original example in this bug, it is not tested nor documented.

Could you explain in more detail what you think is wrong and/or what should be
changed?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 17 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975








 This function is used throughout std.algorithm so marking this as documented
 behavior is not a good solution because it mean basic algorithms like sort
 can't be used with such structs.


 
 Which behavior exactly are you mentioning? And do you mean *any* structs, or
 just structs containing unions?
 


Returning false positives.
Any struct that might trigger false positives on pointsTo.

It's really a serious issue, I stumbled over this while sorting JSON values.
I don't think we can afford to say that sort or swap can't be used with
algebraic types because they trigger false positive assertions.
Of course this is mainly an issue with swap so we need to look at both sides.


 Could you explain in more detail what you think is wrong and/or what should be


changed?

Maybe it's possible to mitigate the problem by reliably identifying that
something can't be a valid pointer.
But to really fix the swap issue we could make this configurable, i.e. either
add an `ignoreFalsePointer` parameter or return a tri-state result. Then swap
could at least work for most cases.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975










 This function is used throughout std.algorithm so marking this as documented
 behavior is not a good solution because it mean basic algorithms like sort
 can't be used with such structs.


 
 Which behavior exactly are you mentioning? And do you mean *any* structs, or
 just structs containing unions?
 


 Returning false positives.
 Any struct that might trigger false positives on pointsTo.


It'd be even worst to have a false negative, IMO. Of course, the best would be
to not have any "false".


 It's really a serious issue, I stumbled over this while sorting JSON values.
 I don't think we can afford to say that sort or swap can't be used with
 algebraic types because they trigger false positive assertions.
 Of course this is mainly an issue with swap so we need to look at both sides.


Just to be clear, algebraic types don't trigger false positives.

The only things that answer true to pointsTo are true pointer types (including
slices and classes). Everything other basic type is statically known not to be
a pointer type. Basically, points to knows what is pointer type, and what
isn't. There are (AFAIK) no "false pointers"

The problem really only appears once unions get into the way.

If a union contains an int, and a pointer (which is basically the example
provided), then there is literally no way to know which of the union members
should be taken into account. The union legitimately contains both the states
pointsTo and !pointsTo :/ That's where the problem is. Given that pointsTo
anser true as soon as at least a member pointsTo something, the reasonable
answer to give in case of dual state is true...

It *is* a problem, but I don't think it is as big a problem as you think it is
(or at least, not in your wording of "sort can't be used with structs").

A tristate answer might be the answer. Given that pointsTo is mostly only ever
used in assertive conditions, we could assert only if pointsTo is true. If
pointsTo is "maybe", the swap can be more lenient and go ahead anyways...?

We'd need to have a tribool type in phobos first though, if we want to do this
in a (mostly) non breaking way.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975






 It *is* a problem, but I don't think it is as big a problem as you think it is
 (or at least, not in your wording of "sort can't be used with structs").
 


These kind of things just have to work.

auto result = get("http://example.com").parseJSON().sort!((a, b) => a["id"] <
b["id"])();

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975








 It *is* a problem, but I don't think it is as big a problem as you think it is
 (or at least, not in your wording of "sort can't be used with structs").
 


 
 These kind of things just have to work.
 
 auto result = get("http://example.com").parseJSON().sort!((a, b) => a["id"] <
 b["id"])();


That didn't compile for me, but I suppose it's supposed to assert in "swap" ?

In any case, I'm not sure how to go about fixing this, it's either false
negatives, or false positives.

I looked into doing a tri-state answer, à la boost::tribool, however, this does
not work in D at all (due to overloads being implemented in terms of others):
(a != b) => !(a == b)
(!a)     => !cast(bool)a

Maybe an extra parameter, eg "enums = {falsePositive, falseNegative}" could
work?

Or maybe we should just say that "pointsTo" is mostly only ever used in
asserts, so prefers false negatives?

I'll look into what I can provide...

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975


Martin Nowak <code dawg.eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei erdani.com





 auto result = get("http://example.com").parseJSON().sort!((a, b) => a["id"] <
 b["id"])();


 
 That didn't compile for me, but I suppose it's supposed to assert in "swap" ?
 


OK, it's a bit longer. And yes it might fail in swap.

auto result = get("http://example.com").parseJSON.array.sort!((a, b) =>
a["id"].uinteger < b["id"].uinteger)();

I added Andrei to the CC list, maybe he has a good idea how to solve this.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975






 OK, it's a bit longer. And yes it might fail in swap.
 
 auto result = get("http://example.com").parseJSON.array.sort!((a, b) =>
 a["id"].uinteger < b["id"].uinteger)();
 
 I added Andrei to the CC list, maybe he has a good idea how to solve this.


I just thought of another problem (which is in the original message): While we
might be able to special case named unions, we can't for anonymous unions. This
means that what we have right now (unless I'm missing information), is the best
we can do.

I'm really just wondering what business swap has asserting if there are
pointers to either of the members... Having such a pointer is a *sign* of
stink, but I don't think it is 100% certifiably wrong... in which case it
should not assert.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 18 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9975






 I'm really just wondering what business swap has asserting if there are
 pointers to either of the members... Having such a pointer is a *sign* of
 stink, but I don't think it is 100% certifiably wrong... in which case it
 should not assert.


Done: https://github.com/D-Programming-Language/phobos/pull/1390

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