Reference to show that if (this == NULL) implies undefined behaviour

[Carlos Moreno]

Hi,

Clarification up-front: I'm not after a discussion or to explain
to me how or why this works or doesn't work. What I'm really
after is a *specific* reference to a section on the standard, or
maybe on a book like TC++PL, that *very explicitly* says
something about the issue.

So, the issue: I'm trying to convince a colleague of mine that
using recursion in a tree structure, and allowing it to step outside
the tree by calling the method on the NULL pointers is not legal
(as in, it invokes undefined behaviour).

The thing is, it's proving to be an "uphill battle", in that the
solution, legal or not, simply happens to work (quite likely works
on every compiler that has ever existed --- at least every "real"
compiler, as opposed to academic/proof-of-concept compilers),
and it simplifies the code a bit. For example, to compute the
sum of all nodes in a tree (say that it's a binary tree of integer
values). So, the solution would go more or less like:

int Node::sum () const
{
if (this == NULL)
{
return 0; // no data members accessed (and this is why
// it *happens* to work)
}
else
{
return value() + left_node()->sum() + right_node()->sum();
}
}

The alternative, though in my opinion is *conceptually* simpler,
is, with respect to the code, a bit more cumbersome:

int Node::sum () const
{
int total = value();
if (left_node() != NULL)
{
total += left_node()->sum();
}
if (right_node() != NULL)
{
total += right_node()->sum();
}
return total;
}

I guess it could be made more compact with the ternary operator,
but still, instead of a single validation for self, we need two
validations, one for each pointer.

Now, this means that we are dereferencing a NULL-pointer, and
thus introduces undefined behaviour. The thing is, I can not find
any concrete reference to the standard, or an authoritative book
such as TC++PL, that *explicitly* says that this is the case.

In a thread back from August (subject "Why does this work?", if
I remember correctly), many replies (including mine) pointed
out that it was undefined behaviour, yet explained why it
*happens to work* --- despite one of the replies asking for an
explicit statement in the standard that it is undefined behaviour,
everyone just *said* it is U.B., but no-one pointed to the *actual*
place in the standard where it explicitly says that it is U.B.

I would be interested also in knowing whether the standard
contains statements such as "accessing nonstatic data members
through a NULL pointer is undefined behaviour" --- as such a
statement would seem to imply that the technique may be legal.

Again, I'm definitely not interested in a debate over the merits
of the technique, or why it would or wouldn't be, or should or
shouldn't be, undefined behaviour. Neither on whether you
personally believe that it is or it's not. (which of course does
not prevent you from saying so, or shifting the direction of the
thread --- I'm just saying, I'm not interested in such as debate
or such replies; hope I'm not sounding too hostile :-) )

Any help, please?

Thanks,

Carlos
--


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Leigh Johnston]

>From n3242:

8.3.2/5
"A reference shall be initialized to refer to a valid object
or function. [ Note: in particular, a null reference cannot exist in a
well-defined program, because the only
way to create such a reference would be to bind it to the “object”
obtained by dereferencing a null pointer,
which causes undefined behavior. As described in 9.6, a reference cannot
be bound directly to a bit-field.
—end note ]"

/Leigh

[Pete Becker]

On 2011-11-07 20:02:34 +0000, Carlos Moreno said:

> Clarification up-front: I'm not after a discussion or to explain
> to me how or why this works or doesn't work. What I'm really
> after is a *specific* reference to a section on the standard, or
> maybe on a book like TC++PL, that *very explicitly* says
> something about the issue.
>
> So, the issue: I'm trying to convince a colleague of mine that
> using recursion in a tree structure, and allowing it to step outside
> the tree by calling the method on the NULL pointers is not legal
> (as in, it invokes undefined behaviour).

[class.mfct.non-static]/1 starts with:

A non-static member function may be called for an object of its class type,
or for an object of a class derived (Clause 10) from its class type, using
the class member access syntax

The challenge for someone who wants to call a non-static member
function without an object is to find similar words that permit it.
There aren't any.

>
> int Node::sum () const
> {
> int total = value();
> if (left_node() != NULL)
> {
> total += left_node()->sum();
> }
> if (right_node() != NULL)
> {
> total += right_node()->sum();
> }
> return total;
> }
>

Another approach is to add a wrapper:

inline int get_sum(Node *ptr) {
if (ptr)
return ptr->sum();
else
return 0;
}

Then the code gets simpler:

total = value() + get_sum(left_node()) + get_sum(right_node());

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Joshua Maurice]

IIRC, it's an "almost defect" in the standard. It's not written
anywhere explicitly except for a potentially non-normative note near
the start. With some good standardeze rules lawyering, I think you're
able to derive that dereferencing a null pointer is UB through some of
the rvalue to lvalue rules and array to rvalue rules, but even then
there's a loophole. I'm unable to find the old thread where I posted
the analysis, and I don't feel like redoing the analysis here. The
short version is that it's known to be UB by the vast majority of
programmers, experts, compiler writers, and standards writers, and
there really isn't a debate. Programming to standards and contracts is
useful insofaras it helps you write working code. In the OP's case,
hiding behind a pedantic technicality asking for a citation misses the
entire point.

[Daniel Krügler]

Am 07.11.2011 21:02, schrieb Carlos Moreno:
> Clarification up-front: I'm not after a discussion or to explain
> to me how or why this works or doesn't work. What I'm really
> after is a *specific* reference to a section on the standard, or
> maybe on a book like TC++PL, that *very explicitly* says
> something about the issue.
>
> So, the issue: I'm trying to convince a colleague of mine that
> using recursion in a tree structure, and allowing it to step outside
> the tree by calling the method on the NULL pointers is not legal
> (as in, it invokes undefined behaviour).

Since this question has repeatedly asked for and answered in diverse
newsgroups I can only assume that this colleague has already found his
opinion and any further discussion won't change anything. There is a
simple logical error in the example code given to "prove" that checking
for a NULL 'this' value inside a member function would prevent UB,
simply because once the underlying assumption is that the UB could
happen between the member function call (with a NULL object pointer) and
the point within the function body. This is like arguing that it is OK
to cross the border of a foreign country without any extra permission to
do so, because *once* you are one the ground of your embassy within that
country, you are effectively on the ground of your own country, q.e.d.

Pictorial arguments aside, 5.2.2 [expr.call] p4 says:

"4 When a function is called, each parameter (8.3.5) shall be
initialized (8.5, 12.8, 12.1) with its corresponding argument. [ Note:
Such initializations are indeterminately sequenced with respect to each
other (1.9) — end note ] If the function is a non-static member
function, the this parameter of the function (9.3.2) shall be
initialized with a pointer to the object of the call, converted as if by
an explicit type conversion (5.4)."

If you use a null pointer, this does not satisfy "initialized with a
pointer to the object of the call" because there would be no object
involved.

HTH & Greetings from Bremen,

Daniel Krügler

[Carlos Moreno]

On 11-11-07 06:32 PM, Joshua Maurice wrote:

> In the OP's case,
> hiding behind a pedantic technicality asking for a citation misses the
> entire point.

Wait a second --- notice that I said I'm trying to convince
someone that the trick invokes undefined behaviour; but the
thing is, his argument is that he got the idea from C++ books
(not sure which one(s), as I don't recall seeing the technique
in books), found it to produce simpler code than the alternative,
and it simply *works* on every existing compiler (well, I should
probably add that it is likely that it works on every existing
compiler).

So, it does make sense that he invited/challenged me to show
him a reputable reference that states that the technique is
not legal. (I mean, we have to agree that those aspects in
the above paragraph, put together, constitute quite solid
evidence in favor of using the technique).

And when you think about it, it is *conceivable* that the standard
could have specifically indicated that accessing nonstatic data
members (and only that) through a NULL pointer is what causes
undefined behaviour (though I guess barely conceivable, in that
this indirectly deals with compiler implementation issues, and
the standard tends to be agnostic about those).

Still, it seems quite shocking that the standard would not
explicitly say something about accessing any member through
dereferencing a NULL pointer. Or, for that matter, simply
stating something about dereferencing a null pointer. I
mean, for example, what would be the wording that states
that the following is undefined behaviour:

int * p = NULL;
int a = *p;

How would that wording (which I'm sure there has to be some
*explicit* statement about the undefined-behaviour-ness of the
above) not be general enough to cover the use of a NULL pointer
to invoke a method on the pointed (inexistent) object as well??

Thanks,

Carlos

[Goran]

On Nov 7, 9:02 pm, Carlos Moreno <moreno_n...@mailinator.com> wrote:
> Hi,
>
> Clarification up-front: I'm not after a discussion or to explain
> to me how or why this works or doesn't work. What I'm really
> after is a *specific* reference to a section on the standard, or
> maybe on a book like TC++PL, that *very explicitly* says
> something about the issue.
>
> So, the issue: I'm trying to convince a colleague of mine that
> using recursion in a tree structure, and allowing it to step outside
> the tree by calling the method on the NULL pointers is not legal
> (as in, it invokes undefined behaviour).

1. No idea whether it's legal or not, but I know this: make your
colleague call a virtual method on NULL pointer. Then ask him whether
he'd like to take the chance of code ceasing to work because method
used was changed to virtual.

2. When I am confronted to these sorts of arguments, I strive to prove
that stepping into NULL is not simpler than not doing it, so I'll try
it again:

Your first variant merely avoids an explicit "if" block (it's still
executed, but written once). It trades two exit points (multiple exit
points are not a bad thing per se to me, personally, but less is
better) for a temporary (total). How about you do this:

int sum(const Node* n)
{
if (n == NULL)
{
return 0;
}
else
{
return n->sum();

}
}

int Node::sum () const
{

return sum(left_node()) + sum(right_node());
}

The above does what first variant does, in a clearly legal way, but at
a price of another function. That function can easily be shortened
with a rather typical use of a ternary:

int sum(const Node* n)
{
return n ? n->sum() : 0;
}

Same could be done in the first or second variant, but at a price of a
loss of clarity IMO, as e.g. nested ternaries are an eyesore.

All in all, the issue, in practice, is: your colleague insists on
using a dubious (at best) practice for a trivial to nonexistent gain.
That's just shoddy work.

HTH,

Goran.

[Jens Auer]

On 8 Nov., 09:06, Carlos Moreno <moreno_n...@mailinator.com> wrote:
> Still, it seems quite shocking that the standard would not
> explicitly say something about accessing any member through
> dereferencing a NULL pointer. Or, for that matter, simply
> stating something about dereferencing a null pointer. I
> mean, for example, what would be the wording that states
> that the following is undefined behaviour:
>
> int * p = NULL;
> int a = *p;
>
> How would that wording (which I'm sure there has to be some
> *explicit* statement about the undefined-behaviour-ness of the
> above) not be general enough to cover the use of a NULL pointer
> to invoke a method on the pointed (inexistent) object as well??

I don't have a copy of the new C++11 standard, but the old one says
so:
1.9.4: "Certain other operations are described in this International
Standard as undefined (for example, the effect of dereferencing the
null pointer)."

[Daniel Krügler]

On 2011-11-08 09:06, Carlos Moreno wrote:
> Still, it seems quite shocking that the standard would not
> explicitly say something about accessing any member through
> dereferencing a NULL pointer. Or, for that matter, simply
> stating something about dereferencing a null pointer. I
> mean, for example, what would be the wording that states
> that the following is undefined behaviour:
>
> int * p = NULL;
> int a = *p;

This follows from normative statements from two sub-clauses in the standard:

a) [basic.lval] p1:

"
— An lvalue [..] designates a function or an object.
[..]
— An xvalue (an “eXpiring” value) also refers to an object,
[..]
— A glvalue (“generalized” lvalue) is an lvalue or an xvalue.
"

This defines an lvalue/gvalue as designating/referencing a function or
object.

b) [conv.lval] p1:

"A glvalue (3.10) of a non-function, non-array type T can be converted
to a prvalue. [..] If the object to which the glvalue refers is not
an object of type T and is not an object of a type derived from T, or if
the object is uninitialized, a program that necessitates this conversion
has undefined behavior."

This makes an lvalue-to-rvalue conversion defined, if (and only if) the
converted (g)lvalue refers to an initialized object.

> How would that wording (which I'm sure there has to be some
> *explicit* statement about the undefined-behaviour-ness of the
> above) not be general enough to cover the use of a NULL pointer
> to invoke a method on the pointed (inexistent) object as well??

Your example and above quoted normative statements don't help much in
the originally discussed example, where no lvalue-to-rvalue conversion
is involved.

HTH & Greetings from Bremen,

Daniel Krügler

[Ulrich Eckhardt]

Am 07.11.2011 21:02, schrieb Carlos Moreno:

> So, the issue: I'm trying to convince a colleague of mine that
> using recursion in a tree structure, and allowing it to step outside
> the tree by calling the method on the NULL pointers is not legal
> (as in, it invokes undefined behaviour).
>
> The thing is, it's proving to be an "uphill battle", in that the
> solution, legal or not, simply happens to work (quite likely works
> on every compiler that has ever existed --- at least every "real"
> compiler, as opposed to academic/proof-of-concept compilers),
> and it simplifies the code a bit.

Just make the function virtual and watch it break. ;)

That said, there is at least one compiler out there that (implicitly)
guarantees that you can call non-virtual functions on null pointers, and
that is MSVC (and probably Intel's in MSVC-compat-mode). MS use this in
their MFC class library (e.g. CWnd::GetSafeHWND()).

Uli

[Johannes Sixt]

On 8 Nov., 09:06, Carlos Moreno <moreno_n...@mailinator.com> wrote:

> Wait a second --- notice that I said I'm trying to convince
> someone that the trick invokes undefined behaviour; but the
> thing is, his argument is that he got the idea from C++ books
> (not sure which one(s), as I don't recall seeing the technique
> in books), found it to produce simpler code than the alternative,
> and it simply *works* on every existing compiler (well, I should
> probably add that it is likely that it works on every existing
> compiler).

It does not work with gcc. The following prints "this is not NULL",
even though the member function was clearly invoked on a null pointer:

----- 8< ------
#include <iostream>

struct B1
{
int b1; // something to avoid empty base class optimization
};
struct B2
{
int b2; // ditto
void f() {
if (this == NULL)
std::cout << "this is NULL" << std::endl;
else
std::cout << "this is not NULL" << std::endl;
}
};

struct D : B1, B2 { };

void g(D* p)
{
p->f();
}

int main()
{
g(NULL);
}
----- 8< ------

-- Hannes

[Roman Kutlak]

> Wait a second --- notice that I said I'm trying to convince
> someone that the trick invokes undefined behaviour;

Hi. I had a look at the c++11 standard and as far as I can tell the
syntax and the semantics are defined.

4.10 Pointer conversions [conv.ptr]
1 A null pointer constant is an integral constant expression (5.19)
prvalue of integer type that evaluates to zero or a prvalue of type
std::nullptr_t. A null pointer constant can be converted to a pointer
type;

I interpret this as ((Foo*)0) converts to Foo* with no problems.

9.3.2 The this pointer [class.this]
1 In the body of a non-static (9.3) member function, the keyword this
is a prvalue expression whose value is the address of the object for
which the function is called. ...

This just says (to me anyway) that 'this' will be treated as a pointer
to the object that called the function. And since the function is non-
virtual member function, the call to left_node()->sum() will be
interpreted as Node::sum(NULL).

The undefined behaviour comes from accessing data members because
'this' points to 0 (non-existent object) or calling virtual methods
(no table to look up the available functions).

I would like to point out that my experience with C++ is quite limited
and that I am still learning. My answer should be interpreted with
caution :-)

Regards,

Roman

[Carlos Moreno]

On 11-11-08 03:05 AM, Daniel Krügler wrote:

> Pictorial arguments aside, 5.2.2 [expr.call] p4 says:
>
> "4 When a function is called, each parameter (8.3.5) shall be
> initialized (8.5, 12.8, 12.1) with its corresponding argument. [ Note:
> Such initializations are indeterminately sequenced with respect to each
> other (1.9) — end note ] If the function is a non-static member
> function, the this parameter of the function (9.3.2) shall be
> initialized with a pointer to the object of the call, converted as if by
> an explicit type conversion (5.4)."

I assume this is some recent version of the standard?? I have
a copy of the 1998 standard, and 5.2.2/4 reads completely different
(it starts with the same sentence, but the rest of the paragraph is
not even similar). Could you confirm?

Thanks,

Carlos

[Kevin McCarty]

On Nov 7, 12:02 pm, Carlos Moreno <moreno_n...@mailinator.com> wrote:

> So, the issue: I'm trying to convince a colleague of mine that
> using recursion in a tree structure, and allowing it to step outside
> the tree by calling the method on the NULL pointers is not legal
> (as in, it invokes undefined behaviour).
>
> The thing is, it's proving to be an "uphill battle", in that the
> solution, legal or not, simply happens to work (quite likely works
> on every compiler that has ever existed --- at least every "real"
> compiler, as opposed to academic/proof-of-concept compilers),
> and it simplifies the code a bit. For example, to compute the
> sum of all nodes in a tree (say that it's a binary tree of integer
> values). So, the solution would go more or less like:
>
> int Node::sum () const
> {
> if (this == NULL)
> {
> return 0; // no data members accessed (and this is why
> // it *happens* to work)
> }
> else
> {
> return value() + left_node()->sum() + right_node()->sum();
> }
>
> }

I know you asked for standardese, but let me try to reach your actual
goal (of convincing your colleagues) from a different angle. Since
the standard implicitly makes calling a non-static member function
through a NULL pointer undefined behavior, there is nothing to stop a
future revision of a compiler from optimizing out the check for NULL,
and still being standards-compliant. So a compiler could easily end
up producing object code from the above that is the equivalent of
this:

int Node::sum() const

{ return value() + left_node()->sum() + right_node()->sum(); }

which will clearly break if any child nodes are NULL.

People have been bitten before by new versions of compilers optimizing
away NULL checks in cases where having a NULL pointer would cause
undefined behavior anyway. This has caused for instance an exploit in
the Linux kernel:

http://lwn.net/Articles/342330/

and in fact GCC has been making this optimization in at least some
cases for > 10 years now:

http://gcc.gnu.org/news/null.html


Let me give you a second argument, too. In practice, the code above
is also fragile as soon as you involve inheritance even if the NULL
check isn't optimized away. Suppose you refactor and make Node a
derived class of, let's say, NodeBase, all the child nodes are
pointers to NodeBase rather than Node, and suppose sum() is made
virtual. This seems not an unreasonable thing to do if you also want
to have binary trees where the sum() is only over leaves, or only over
branches.

In the body of Node::sum(), suppose that 'this' is non-NULL but that
left_node() is NULL. So you reach the call to left_node()->sum(). In
a typical implementation, that will try to read the class vtable from
left_node() to find the correct override of sum(). But that's NULL.
Oops. Note that this happens BEFORE the actual call to left_node()-
>Node::sum() and its own check for 'if (this == NULL)' can be reached.

- Kevin B. McCarty

[Joshua Maurice]

On Nov 8, 12:06 am, Carlos Moreno <moreno_n...@mailinator.com> wrote:
> On 11-11-07 06:32 PM, Joshua Maurice wrote:
>
> > In the OP's case,
> > hiding behind a pedantic technicality asking for a citation misses the
> > entire point.
>
> Wait a second --- notice that I said I'm trying to convince
> someone that the trick invokes undefined behaviour; but the
> thing is, his argument is that he got the idea from C++ books
> (not sure which one(s), as I don't recall seeing the technique
> in books),

Those are some mighty bad C++ books then. Unfortunately, bad C++ books
do exist.

> found it to produce simpler code than the alternative,

This I highly doubt. It's about the same amount of code either way,
and it looks about exactly the same.
class X { /*...*/ void foo() { /*...*/ } };
/*...*/
X* x = 0;
x->foo();
vs:
class X { /*...*/ static void foo() { /*...*/ } };
/*...*/
X::foo();

> and it simply *works* on every existing compiler (well, I should
> probably add that it is likely that it works on every existing
> compiler).

I would hope that there exists some compilers with good debug checking
which would catch this. However, I do not know.

> So, it does make sense that he invited/challenged me to show
> him a reputable reference that states that the technique is
> not legal. (I mean, we have to agree that those aspects in
> the above paragraph, put together, constitute quite solid
> evidence in favor of using the technique).

Not really, no. That again misses the entire point. The point of
programming to contracts and standards is that we all agree on what is
to be guaranteed now and in the future, and what isn't. This allows
implementers in the future to change things up and still abide by the
written contract. That it happens to work on all current
implementations is a rather poor argument.

> And when you think about it, it is *conceivable* that the standard
> could have specifically indicated that accessing nonstatic data
> members (and only that) through a NULL pointer is what causes
> undefined behaviour (though I guess barely conceivable, in that
> this indirectly deals with compiler implementation issues, and
> the standard tends to be agnostic about those).

Yes. I consider the wording in C++98 and C++03 to be quite deficient
in this regard. I haven't looked at C++11 yet with this issue in mind.
It's relatively unimportant when more or less everyone is on the same
page.

> Still, it seems quite shocking that the standard would not
> explicitly say something about accessing any member through
> dereferencing a NULL pointer. Or, for that matter, simply
> stating something about dereferencing a null pointer. I
> mean, for example, what would be the wording that states
> that the following is undefined behaviour:
>
> int * p = NULL;
> int a = *p;
>
> How would that wording (which I'm sure there has to be some
> *explicit* statement about the undefined-behaviour-ness of the
> above) not be general enough to cover the use of a NULL pointer
> to invoke a method on the pointed (inexistent) object as well??

Again, just off the top of my head, I'm not sure that exists either
(in a simple, explicit rule). Again, with some good standardeze rules
lawyering with the lvalue to rvalue conversion rules of C++03, IIRC
you can derive that the above example is UB. (There are some loopholes
in those rules though where programs ought to have UB but the standard
doesn't properly describe them as such.)

PS: This reminds me greatly of the whole volatile debacle. Volatile
was never specced to work as a threading primitive, but some ignorant
people insisted that it did, and continue to do so, with the same
arguments that "it works on X implementation" (possible) or "it works
on all current implementations" (unlikely). They don't get how
programming to contracts work, and they argue from implementation
details such as "it happens to work today". Those arguments are the
same as your colleague's arguments, and they're just as bunk. They're
simply wrong, and sometimes it's frustratingly difficult to convince
them otherwise.

[Carlos Moreno]

On 11-11-08 06:57 PM, Kevin McCarty wrote:

> I know you asked for standardese, but let me try to reach your actual
> goal (of convincing your colleagues) from a different angle. Since
> the standard implicitly makes calling a non-static member function
> through a NULL pointer undefined behavior, there is nothing to stop a
> future revision of a compiler from optimizing out the check for NULL,
> and still being standards-compliant. So a compiler could easily end
> up producing object code from the above that is the equivalent of
> this:
>
> int Node::sum() const
> { return value() + left_node()->sum() + right_node()->sum(); }
>
> which will clearly break if any child nodes are NULL.
>
> People have been bitten before by new versions of compilers optimizing
> away NULL checks in cases where having a NULL pointer would cause
> undefined behavior anyway. This has caused for instance an exploit in
> the Linux kernel:
>
> http://lwn.net/Articles/342330/
>
> and in fact GCC has been making this optimization in at least some
> cases for> 10 years now:
>
> http://gcc.gnu.org/news/null.html

Huh ... the examples do not specifically mention a situation where
this is checked for NULL --- though I understand it as a fact that
this situation is covered, it's still not convincing evidence for
someone that wants "proof" that the trick I described in the initial
post leads to undefined behaviour (again, I'm not saying that it
is not or that it may not be --- to me, it is clear that it is UB,
and my argument is now about the validity of these examples as
convincing evidence that the trick causes UB).

But still, the examples and the links are great!! Thank you so
much for posting them; one of my recent interests is the area of
computer security --- and I guess I should be embarrassed to see
that it took me more than two years to learn about this incident!!

Agreed on the second part (the virtual function part). In fact I
had already mentioned that detail to my colleague.


BTW, at this point he is convinced that the trick indeed invokes
undefined behaviour --- and for everyone's peace of mind, the trick
was not being used in production code, but rather on a demo used
for internal purposes; that simply triggered the discussion, and
I found it curious that I had so much difficulty finding some
concrete references to support my argument!


Thanks!

Carlos

[Dave Abrahams]

on Mon Nov 07 2011, Pete Becker <pete-AT-versatilecoding.com> wrote:

> On 2011-11-07 20:02:34 +0000, Carlos Moreno said:
>
>> Clarification up-front: I'm not after a discussion or to explain
>> to me how or why this works or doesn't work. What I'm really
>> after is a *specific* reference to a section on the standard, or
>> maybe on a book like TC++PL, that *very explicitly* says
>> something about the issue.
>>
>> So, the issue: I'm trying to convince a colleague of mine that
>> using recursion in a tree structure, and allowing it to step outside
>> the tree by calling the method on the NULL pointers is not legal
>> (as in, it invokes undefined behaviour).
>
> [class.mfct.non-static]/1 starts with:
>
> A non-static member function may be called for an object of its class type,
> or for an object of a class derived (Clause 10) from its class type, using
> the class member access syntax
>
> The challenge for someone who wants to call a non-static member
> function without an object is to find similar words that permit it.
> There aren't any.

Let me just point back to Pete's answer, because people keep trying to
come up with more elaborate ones. If you want to make an argument based
on standardese, your audience needs to understand how to interpret it.
You won't find words in the standard explicitly prohibiting many things
that are illegal.

,----
| To highlight what everybody else might be missing, it says "for an
| object..." and NULL does not point to an object.
`----

Pete has it right and everybody else should just sit down ;-).

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[Daniel Krügler]

On 2011-11-09 00:49, Jens Auer wrote:
> On 8 Nov., 09:06, Carlos Moreno<moreno_n...@mailinator.com> wrote:
>> Still, it seems quite shocking that the standard would not
>> explicitly say something about accessing any member through
>> dereferencing a NULL pointer. Or, for that matter, simply
>> stating something about dereferencing a null pointer. I
>> mean, for example, what would be the wording that states
>> that the following is undefined behaviour:
>>
>> int * p = NULL;
>> int a = *p;
>>
>> How would that wording (which I'm sure there has to be some
>> *explicit* statement about the undefined-behaviour-ness of the
>> above) not be general enough to cover the use of a NULL pointer
>> to invoke a method on the pointed (inexistent) object as well??
>
> I don't have a copy of the new C++11 standard, but the old one says
> so:
> 1.9.4: "Certain other operations are described in this International
> Standard as undefined (for example, the effect of dereferencing the
> null pointer)."

This is not such a good example, because the core language is currently
in the process to replace this example by another one, because they want
to allow for "empty lvalues", which cannot undergo lvalue-to-rvalue
conversion. For more details see

http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#232

HTH & Greetings from Bremen,

Daniel Krügler

[Daniel Krügler]

On 2011-11-09 00:56, Carlos Moreno wrote:
> On 11-11-08 03:05 AM, Daniel Krügler wrote:
>
>> Pictorial arguments aside, 5.2.2 [expr.call] p4 says:
>>
>> "4 When a function is called, each parameter (8.3.5) shall be
>> initialized (8.5, 12.8, 12.1) with its corresponding argument. [ Note:
>> Such initializations are indeterminately sequenced with respect to each
>> other (1.9) — end note ] If the function is a non-static member
>> function, the this parameter of the function (9.3.2) shall be
>> initialized with a pointer to the object of the call, converted as if by
>> an explicit type conversion (5.4)."
>
> I assume this is some recent version of the standard?? I have
> a copy of the 1998 standard, and 5.2.2/4 reads completely different
> (it starts with the same sentence, but the rest of the paragraph is
> not even similar). Could you confirm?

Yes, this is from the C++11 standard. But in C++03 the content is
essentially the same for this particular scenario, see ISO/IEC
14882:2003(E), 5.2.2 [expr.call] p4:

"When a function is called, each parameter (8.3.5) shall be initialized

(8.5, 12.8, 12.1) with its corresponding argument. If the function is a
nonstatic member function, the “this” parameter of the function (9.3.2)

shall be initialized with a pointer to the object of the call, converted
as if by an explicit type conversion (5.4)."

HTH & Greetings from Bremen,

Daniel Krügler

[Dave Abrahams]

on Wed Nov 09 2011, Carlos Moreno <moreno_news-AT-mailinator.com> wrote:

> BTW, at this point he is convinced that the trick indeed invokes
> undefined behaviour --- and for everyone's peace of mind, the trick
> was not being used in production code, but rather on a demo used
> for internal purposes; that simply triggered the discussion, and
> I found it curious that I had so much difficulty finding some
> concrete references to support my argument!

If "the trick" is evaluating "this == NULL," then no, it doesn't invoke
undefined behavior. The point is that if the test ever passed, it
implies that undefined behavior *has already been invoked*.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[Pete Becker]

On 2011-11-08 23:50:30 +0000, Johannes Sixt said:

> On 8 Nov., 09:06, Carlos Moreno <moreno_n...@mailinator.com> wrote:
>> Wait a second --- notice that I said I'm trying to convince
>> someone that the trick invokes undefined behaviour; but the
>> thing is, his argument is that he got the idea from C++ books
>> (not sure which one(s), as I don't recall seeing the technique
>> in books), found it to produce simpler code than the alternative,
>> and it simply *works* on every existing compiler (well, I should
>> probably add that it is likely that it works on every existing
>> compiler).
>
> It does not work with gcc. The following prints "this is not NULL",
> even though the member function was clearly invoked on a null pointer:

And it probably gets the same result with any other compiler. But
different isn't the same. Changing to multiple inheritance or, as
mentioned earlier, changing to a virtual function, changes the context.
Calling a non-static member function requires an object. Somehow
magically calling a non-static member function without an object makes
the behavior of the program undefined. In the original example (no
inheritance, no virtual functions involved) there's no good reason for
a compiler to generate code that does unexpected things. Nevertheless,
the behavior of such a program is formally undefined, and writing code
like that is risky except with a compiler that explicitly documents
what it does.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Carlos Moreno]

On 11-11-09 01:31 AM, Joshua Maurice wrote:

>> Wait a second --- notice that I said I'm trying to convince
>> someone that the trick invokes undefined behaviour; but the
>> thing is, his argument is that he got the idea from C++ books
>> (not sure which one(s), as I don't recall seeing the technique
>> in books),
>
> Those are some mighty bad C++ books then. Unfortunately, bad C++ books
> do exist.

*sigh* tell me about it (long story --- suffice it to say that
the poor quality of books, and even when only seen as the
*educational* quality of books, has been a pet peeve of mine
for quite a long time!)

>> and it simply *works* on every existing compiler (well, I should
>> probably add that it is likely that it works on every existing
>> compiler).

> [ ... ]

>> So, it does make sense that he invited/challenged me to show
>> him a reputable reference that states that the technique is
>> not legal. (I mean, we have to agree that those aspects in
>> the above paragraph, put together, constitute quite solid
>> evidence in favor of using the technique).
>
> Not really, no. That again misses the entire point. The point of
> programming to contracts and standards is that we all agree on what is

> to be guaranteed now and in the future [ ... ]

I'm not disagreeing with that --- and for what is worth, the part
that "it simply works" was added by me (it was not one of his
arguments). His main argument is that he found the technique
in *two* different books, and he did find that the code was
simpler (I do agree, but I won't necessarily defend that idea
too strongly).

But what I'm saying is that those elements *combined* (you're
focusing too much on the issue that "it works today", as if that
was the only reason, and as if we were specifically ignoring an
explicit label of UB just because we observe that it works when
we try). In the abscence of knowledge or certainty about whether
that is UB, you see the technique in two separate books, you try
it, it works, I think it is more than reasonable to assume that
it works because it is supposed to work, and not by mere
coincidence (as it is the case).

Cheers,

Carlos

[Nikolay Ivchenkov]

On 8 Nov, 12:05, Daniel Krügler wrote:
>
> Pictorial arguments aside, 5.2.2 [expr.call] p4 says:
>
> "4 When a function is called, each parameter (8.3.5) shall be
> initialized (8.5, 12.8, 12.1) with its corresponding argument. [ Note:
> Such initializations are indeterminately sequenced with respect to each
> other (1.9) — end note ] If the function is a non-static member
> function, the this parameter of the function (9.3.2) shall be
> initialized with a pointer to the object of the call, converted as if by
> an explicit type conversion (5.4)."
>
> If you use a null pointer, this does not satisfy "initialized with a
> pointer to the object of the call" because there would be no object
> involved.

1) AFAICS, the standard does not describe the meaning of "the this
parameter" (in contrast to "implicit object parameter").

2) It is unclear what constitutes a "function call". A function can be
"called" in an evaluated or a non-evaluated context.

struct X
{
int f();
};

int main()
{
sizeof ((X *)0)->f();
}

This code is intended to be well-defined, though neither an actual
region of storage nor even a function definition was provided. Should
wording

"If the function is a non-static member function, the this
parameter of the function (9.3.2) shall be initialized with a pointer
to the object of the call, converted as if by an explicit type
conversion (5.4)."

make sense for such an unevaluated context?

[Daniel Krügler]

Am 09.11.2011 00:52, schrieb Roman Kutlak:
>> Wait a second --- notice that I said I'm trying to convince
>> someone that the trick invokes undefined behaviour;
>
> Hi. I had a look at the c++11 standard and as far as I can tell the
> syntax and the semantics are defined.
>
> 4.10 Pointer conversions [conv.ptr]
> 1 A null pointer constant is an integral constant expression (5.19)
> prvalue of integer type that evaluates to zero or a prvalue of type
> std::nullptr_t. A null pointer constant can be converted to a pointer
> type;
>
> I interpret this as ((Foo*)0) converts to Foo* with no problems.

I agree but this does has no relation to the problem mentioned by the OP.

> 9.3.2 The this pointer [class.this]
> 1 In the body of a non-static (9.3) member function, the keyword this
> is a prvalue expression whose value is the address of the object for
> which the function is called. ...
>
> This just says (to me anyway) that 'this' will be treated as a pointer
> to the object that called the function. And since the function is non-
> virtual member function, the call to left_node()->sum() will be
> interpreted as Node::sum(NULL).

The wording you are quoting just describes the semantics of this. This
wording does not say *anything* about whether the 'this' pointer might
be a null pointer or not. This wording is not relevant for the question
asked.

> The undefined behaviour comes from accessing data members because
> 'this' points to 0 (non-existent object) or calling virtual methods
> (no table to look up the available functions).

These criteria are not sufficient. Additional to lvalue-to-rvalue
conversion of an "empty" lvalue (such as *((Foo*)0)) the standard makes
it undefined, if the so-called object-expression (This is the left side
of any class member access E1.E2; E1->E2 has the semantics of
(*(E1)).E2) does not refer to a valid object if E2 is a non-static
member. Note that for a static member, the call expression is
well-formed if applied to a NULL pointer. E.g.

struct A {
static void f() {}
};

int main() {
((A*) 0)->f();
}

is OK, see

http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_closed.html#315

for further details.

HTH & Greetings from Bremen,

Daniel Krügler

[Kaba]

Pete Becker wrote:
> Another approach is to add a wrapper:
>
> inline int get_sum(Node *ptr) {
> if (ptr)
> return ptr->sum();
> else
> return 0;
> }
>
> Then the code gets simpler:
>
> total = value() + get_sum(left_node()) + get_sum(right_node());

I would favor a sentinel node:) It gets rid of boundary cases, and so
essentially mirrors a legal alternative to the idea in the OP's post.

http://kaba.hilvi.org/pastel/pastel/sys/redblacktree_implementation.htm

For those who don't bother to open a link:

"The sentinel node plays an essential role in the RedBlackTree
implementation. The idea is that every parent link and child link points
to some valid node, where the sentinel node is interpreted as an empty
node. Thus, for example, if a node does not have children, then the
child pointers are assigned the sentinel node. This makes the
implementation much more easier, since then we can stop worrying about
boundary cases, and whether we are accessing a null-pointer or not. In
addition to this, the sentinel node works as the one-past-end iterator,
when the tree is interpreted as an ordered sequence. When the parent of
the sentinel node points to the maximum node, one is able to naturally
get to the precedessor (the maximum node) from the one-past-end
iterator. The color of the sentinel node is black, and it does not have
any children. The children of the entinel node point to itself, a unique
property which can be used to identify a sentinel node. Using the
sentinel node is a standard trick, but its connection to the one-past-
end iterator is rarely mentioned."

--
http://kaba.hilvi.org

[Carlos Moreno]

On 11-11-09 03:58 PM, Pete Becker wrote:

> [ ... ] In the original example (no

> inheritance, no virtual functions involved) there's no good reason for
> a compiler to generate code that does unexpected things.

Huh??? (care to elaborate on how exactly you define "unexpected"
in the above sentence?? :-) )

What do you mean "no good reason"??? You don't find the fact that
this *is not allowed to be NULL* reason enough for the compiler to
optimize away that if, thus guaranteeing that the program will
crash ???

True, the examples given by the previous poster did not really
address the this pointer, and it was mainly situations where
the sequence of executed statements is what hints the compiler
about "impossibility" of a pointer being NULL. But still, if
indeed (or I should say, *given that* indeed) the this pointer
*is not allowed* to take the NULL value, then it seems perfectly
reasonable for the compiler to replace if (this == NULL) with
if (false), including entirely removing the corresponding block
associated to that if.

Am I missing something??

Carlos
--
PS: Notice that, from the point of view of my original post,
the argument by the previous poster is not completely
useful, in that I was trying to convince someone that
allowing a situation where this == NULL is not legal;
the argument by the previous poster goes more along the
lines of presenting an example that shows why that
particular instance of UB *can* have consequences in
real-life situations. (but if the person is not convinced
that it *is* UB, then the example would tell him nothing.
Just a remark --- I highly appreciated the example!!)


--

[Carlos Moreno]

On 11-11-09 03:39 PM, Dave Abrahams wrote:
> on Wed Nov 09 2011, Carlos Moreno<moreno_news-AT-mailinator.com> wrote:
>
>> BTW, at this point he is convinced that the trick indeed invokes
>> undefined behaviour --- and for everyone's peace of mind, the trick
>> was not being used in production code, but rather on a demo used
>> for internal purposes; that simply triggered the discussion, and
>> I found it curious that I had so much difficulty finding some
>> concrete references to support my argument!
>
> If "the trick" is evaluating "this == NULL," then no, it doesn't invoke
> undefined behavior. The point is that if the test ever passed, it
> implies that undefined behavior *has already been invoked*.

Nitpicking, much? :-)

I was referring to "the trick" as a whole --- the approach to
implement the recursive tree traversal allowing execution to step
outside the actual tree... Evaluating this == NULL is an essential
part of that approach.

Notice that in the subject line, I was very careful not to say that
this == NULL is/invokes undefined behaviour, but that it *implies*
UB; as in, that validation implies that there is UB. True, the
statement in the subject is "incomplete", in that what I really
meant is that if (this == NULL) being a check on which the approach
relies, that means that there is UB. And with this clarification
I'm emphasizing the fact that you can always place a statement if
(this == NULL) with the knowledge that it will always evaluate to
false, or even place it somewhere where you know it will never be
executed, such as right after a return or a throw, and of course
it does not imply that there must be UB.

Notice, BTW, that the way you phrased it is also somewhat questionable,
even though your statement is not false --- but what happens if the
compiler, knowing that this is not allowed to be NULL, removes the
if and the associated block? The condition will never evaluate to
true, since the condition is never evaluated!! Yet there will be
undefined behaviour since now we're unconditionally calling methods
on NULL subtrees that will access nonstatic data, surely causing a
crash (not to mention that when the compiler removes the if
(this == NULL) and associated code, we now have an infinite loop!)

I know, your statement says that *if it evaluates to true*, then
UB has already happened (which is true). But what I mean is that
that phrasing does not draw the complete picture of the issue.

Anyway, we're hopefully clear and in sync about what we all mean
when discussing the issue! Hopefully the thread will be about to
close, and not about to turn into a philosophical discussion :-)

Cheers,

Carlos
--


--

[Pete Becker]

On 2011-11-10 19:11:44 +0000, Carlos Moreno said:

> On 11-11-09 03:58 PM, Pete Becker wrote:
>
>> [ ... ] In the original example (no
>> inheritance, no virtual functions involved) there's no good reason for
>> a compiler to generate code that does unexpected things.
>
> Huh??? (care to elaborate on how exactly you define "unexpected"
> in the above sentence?? :-) )
>
> What do you mean "no good reason"??? You don't find the fact that
> this *is not allowed to be NULL* reason enough for the compiler to
> optimize away that if, thus guaranteeing that the program will
> crash ???

Gosh, you're cherry-picking from my response. But, yes, optimization is
perhaps a good reason. What I was pointing out is that this typically
works, but is not guaranteed. Which is, if I recall correctly, what I
explicitly said in text that you snipped.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Gil]

On Nov 8, 3:05 am, Daniel Krügler <daniel.krueg...@googlemail.com>
wrote:

using 5.2.2 [expr.call] to argument that calling non static methods
through null pointer results in undefined behavior is weak and
contextual.

with regard to the OP's UB question the argument in 5.2.2 is even
weaker
than simply using 9.3.1/2 [class.mfct.non-static]:
"If a non-static member function of a class X is called for an object
that is not of type X, or of a type derived from X, the behavior is
undefined."

note that 9.3.1/2 adds additional requirements to the 'object'
involved whilst
5.2.2 doesn't describe any potential invalid situations.

however, imo both 5.2.2 and 9.3.1/2 do not handle the invalidity of
'empty object'.
so we definitely have a defect that should be addressed with a wording
change
in 9.3.1/2:

"...or if the object is an empty object, the behavior is undefined."

together with
http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#232
as noted.

but meanwhile, 9.3.1/2 is the best argument we have for UB when
calling
non static methods through null pointer because 'there is no object of
type X'.

Note: we cannot use the old argument logic involving '*' operator
semantics,
for example:

5.2.5/2 "The expression E1->E2 is converted to the equivalent form
(*(E1)).E2;"
5.2.5/1 “postfix expression before the dot or arrow is evaluated”
5.3.1/1 “unary * operator performs indirection: [...] and the result
is an lvalue
referring to the object or function to which the expression points”

because the new standard changed the old imperative
3.10/2 “An lvalue refers to an object or function”

to something more flexible:
3.10/1 "An lvalue [...] designates a function or an object."

gil

[Dave Abrahams]

on Thu Nov 10 2011, Carlos Moreno <moreno_news-AT-mailinator.com> wrote:

>> If "the trick" is evaluating "this == NULL," then no, it doesn't invoke
>> undefined behavior. The point is that if the test ever passed, it
>> implies that undefined behavior *has already been invoked*.
>
> Nitpicking, much? :-)

Not intentionally.

> I was referring to "the trick" as a whole --- the approach to
> implement the recursive tree traversal allowing execution to step
> outside the actual tree...

I overlooked that earlier reference, couldn't find the word "trick"
in your earlier posting, and didn't see anything in the code you posted
that looked "tricky" other than the test.

> Notice that in the subject line, I was very careful not to say that
> this == NULL is/invokes undefined behaviour, but that it *implies*
> UB; as in, that validation implies that there is UB.

I did notice that.

> Notice, BTW, that the way you phrased it is also somewhat questionable,
> even though your statement is not false --- but what happens if the
> compiler, knowing that this is not allowed to be NULL, removes the
> if and the associated block?

Irrelevant. That's just one legit way to compile that code.

> The condition will never evaluate to true, since the condition is
> never evaluated!! Yet there will be undefined behaviour since now
> we're unconditionally calling methods on NULL subtrees that will
> access nonstatic data, surely causing a crash (not to mention that
> when the compiler removes the if (this == NULL) and associated code,
> we now have an infinite loop!)

Now you've shown me that I wasn't nitpicking at all. Your description
of UB after "since" above is already happening much later than the first
UB, which occurs when you call the method on the NULL object.

> I know, your statement says that *if it evaluates to true*, then
> UB has already happened (which is true). But what I mean is that
> that phrasing does not draw the complete picture of the issue.

I believe it does. The complete picture of the issue ends where UB
begins.

> Anyway, we're hopefully clear and in sync about what we all mean
> when discussing the issue! Hopefully the thread will be about to
> close, and not about to turn into a philosophical discussion :-)

Sorry to disappoint, but I honestly think your focus is in the wrong
place. You posted in search of enough understanding about this UB to
explain the case to your colleagues. It can be a subtle thing to
understand, so I'm trying to clarify. Call that nitpicking if you like,
but I'm trying to help.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[Carlos Moreno]

On 11-11-11 08:28 AM, Gil wrote:

> with regard to the OP's UB question the argument in 5.2.2 is even
> weaker
> than simply using 9.3.1/2 [class.mfct.non-static]:
> "If a non-static member function of a class X is called for an object
> that is not of type X, or of a type derived from X, the behavior is
> undefined."

Hmmm, I'm not too sure that this would be a convincing argument,
in that someone insisting on using the trick of this == NULL could
still insist that the *static type* of the pointer is the right
type, so you're "formally" calling the member function for an
object of the correct type.

IOW, I think 9.3.1/2 is more contextual than the previous one
posted by Daniel, since this one puts the emphasis on *the type*
of the object.

> however, imo both 5.2.2 and 9.3.1/2 do not handle the invalidity of
> 'empty object'.

Empty object??? What does a NULL pointer have to do with *empty*
object?? The situation here is *no object*, which is what a NULL
pointer describes.

> so we definitely have a defect that should be addressed with a wording
> change
> in 9.3.1/2:
>
> "...or if the object is an empty object, the behavior is undefined."

I don't think the standard would ever use the wording "empty object",
since there is no such thing. (someone correct me if I'm wrong)


Carlos

[Carlos Moreno]

On 11-11-11 08:29 AM, Dave Abrahams wrote:

>> Anyway, we're hopefully clear and in sync about what we all mean
>> when discussing the issue! Hopefully the thread will be about to
>> close, and not about to turn into a philosophical discussion :-)
>
> Sorry to disappoint, but I honestly think your focus is in the wrong
> place. You posted in search of enough understanding about this UB to
> explain the case to your colleagues. It can be a subtle thing to
> understand, so I'm trying to clarify. Call that nitpicking if you like,
> but I'm trying to help.

Of course --- and like with pretty much all of the replies that I got,
I do appreciate it!

I guess my reaction was because you were clarifying/emphasizing
something that was very clear in my mind. (and I had explained
that aspect to my colleague, who at that point rather wanted some
*official* legislation on the issue).

Cheers,

Carlos
--

[Pete Becker]

On 2011-11-11 19:27:36 +0000, Carlos Moreno said:

> Empty object??? What does a NULL pointer have to do with *empty*
> object?? The situation here is *no object*, which is what a NULL
> pointer describes.

Exactly. And since a non-static member function can only be called *on an object*, calling it through a null pointer is not permitted. But you seem to be ignoring this point, so I won't mention it again.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The Standard C++ Library Extensions: a Tutorial and Reference (www.petebecker.com/tr1book)

[Gil]

> [ Seehttp://www.gotw.ca/resources/clcm.htmfor info about ]

> [ comp.lang.c++.moderated. First time posters: Do this! ]

read http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#232

also notice that new standard has distanced itself already from
considering dereferencing a NULL pointer UB, both example and note
in 1.9/4 and 8.3.2/4 were replaced.
(dereferencing a NULL pointer creates an empty lvalue)

also read cwg issue(s) 315 and 342.

the standard is moving toward validating some operations on null or
'empty' objects.

Now, a quiz. Name compiler and platform for which the assertion is
triggered:

#include <assert.h>

struct B1 { char c; };

struct B2 {
void * this_pointer( ) { return this; }
};

struct D : B1, B2 { };

int main( )
{
D * p = 0;
assert( !p->this_pointer( ) );