🚀 go-pugleaf

Philippe Verdy wrote:
> 
> Many recursive data structures require algorithms to handle
> them which have to mark and unmark all scanned objects in
> order to avoid infinite recursion when walking on that
> structure, or when building items iterator.
> Such algorithms will use the mark() and unmark() private
> methods in each visited node, so that we can detect paths
> which have already been visited. his is critical for example
> when managing with auto-references, graphs, dictionnaries
> of polymorphic objects (containing dictionnaries like in
> a PostScript interpret).
> However, how can we apply standard read-only methods on such
> objects: these methods are specified as const in one of the
> base classes, and virtual override requires not to change the
> constness of the derived object.
> So we cannot mark such structures, because even a private
> member cannot be modified in a const instance.
> We can effectively change temporarily the constness of the
> object to realize this mark, but in that case we would write
> the following :[snip]
> The problem is that now mark() and unmark() methods are not
> const so they cannot be used in read-only methods like show().
> So we have to use a const_cast<T&> or const_cast<T*> to
> suppress this constness.
> 
> This is not obvious, and has the big disadvantage of globally
> suppressing the constness of the object. So this is quite
> dangerous, because some-times, we do not know really if a
> method has an impact on the semantic value of the instance
> on which we apply this cast. So this is a security hole which
> should be avoided.
> 
> We can avoid const_casting to call mark() and unmark() by
> declaring them as const, like this:[snip]
> but this is really hard to write, and is it semantically
> correct ? It would from the public point of view, but what
> on the private point of view ?
> 
> We can also use explicitly (const_cast<T*>this)->mark(); and
> (const_cast<T*>this)->unmark(); calls in the show()
> implementation, but this is quite hard to write, so that many
> users refrain using const specifiers on their classes.
> [snip]
> What do you think ?
> 
> And is constness definition a semantic only definition,
> or does it involve a more strict sense in which the compiler
> optimizer would have an influence (such as in common
> subexpressions reduction) ?

There are two schools of thought regarding const-ness.  One 
requires strict bitwise constness.  That means that if you 
construct a const object, did a memcpy of the object to some 
suitable buffer, exercised the object using any permissible 
(const) mfs, in any combination, then compared the object with 
the memcpy'd buffer, there would be no change.

The other requires only logical constness.  That means that the 
object always appears the same through its public and protected 
interfaces.  You can do what you want inside the object, 
provided it always appears the same to the class user.

The compiler obviously enforces the former definition.  You must 
cast away constness when you want the latter.  That definition 
is the one you're employing here.

According to how you've described mark and unmark, they must be 
controlled by other functions such that the original state is 
restored before return to the caller.  That is, some other 
function must use mark and unmark, in matched sets for each 
node, in order to preserve the external state of the object.  

Therefore, it is not mark and unmark which should cast away 
constness, but those functions that make use of them.  mark and 
unmark should be non-const; they each change the state in a way 
that affects the external state of the class.  Those functions 
calling them must cast away constness to use them.

As for your question about some language extension to permit 
that behavior, it could only apply to functions calling mark and 
unmark in their use of them.  That is, since only 
functions using mark and unmark can ensure that the 
original state is restored--thus preserving the logical 
constness--only they can be used on const objects.  Therefore, 
they should be the ones to get special dispensation to use 
non-const mfs in such a way that they retain logical constness.

The difficulty is with maintenance.  Sure, after some design and 
debugging work, you can get the functions to work correctly such 
that you retain logical constness.  The maintainer of your code 
may have more trouble or may not realize the consequence of his 
actions, and destroy logical constness.  Once you violate the 
bitwise constness of the compiler, you're on your own.  This is 
true of casting away constness yourself, but would we really 
want a language feature which makes it easy and makes less clear 
where special attention is required?

I don't think so.  Instead, you should consider how to build a 
base class that encapsulates the iteration process to which you 
can pass a derived class mf to process each node you encounter.  
The implementation will appear once in your code and shouldn't 
require maintenance once you fix the bugs.  All the rest of your 
code that needs to iterate the container will make use of that 
base class functionality, but won't need to worry about casting 
away constness.

-- 
Robert Stewart		| My opinions are usually my own.
Datalytics, Inc.	| stew@datalytics.com
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]