Boost C++ Libraries: Ticket #4400: BOOST_PP_SEQ_REPLACE fails in corner cases

Sat, 03 Jul 2010 11:35:58 GMT

After fiddling with the code a bit, I suggest, as a safe and quick fix, a replacement of

boost/preprocessor/seq/replace.hpp

******
#  *                                                                          *
#  *     (C) Copyright Paul Mensonides 2002.
#  *     Distributed under the Boost Software License, Version 1.0. (See
#  *     accompanying file LICENSE_1_0.txt or copy at
#  *     http://www.boost.org/LICENSE_1_0.txt)
#  *                                                                          *
#  ************************************************************************** */
#
# /* See http://www.boost.org for most recent version. */
#
# ifndef BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
# define BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
#
# include <boost/preprocessor/arithmetic/inc.hpp>
# include <boost/preprocessor/config/config.hpp>
# include <boost/preprocessor/seq/first_n.hpp>
#
# /* BOOST_PP_SEQ_REPLACE */
#
# if ~BOOST_PP_CONFIG_FLAGS() & BOOST_PP_CONFIG_EDG()
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_NP1(i, seq)
#    define BOOST_PP_SEQ_REST_NP1(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# else
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_REPLACE_I(seq, i, elem)
#    define BOOST_PP_SEQ_REPLACE_I(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_NP1(i, seq)
#    define BOOST_PP_SEQ_REST_NP1(i, seq) BOOST_PP_SEQ_REST_NP1_I(n, seq)
#    define BOOST_PP_SEQ_REST_NP1_I(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# endif
#
# endif

The idea behind this rework is to use a dedicated version of BOOST_PP_REST_N, called BOOST_PP_REST_NP1 here (NP1 stands for N + 1), and not rely on undocumented behavor of BOOST_PP_REST_N any more.

Since the former code called BOOST_PP_REST_N with its first argument at least 1, the replacement code can be simplified a little. The sentinel element (nil) in the replacement code of BOOST_PP_REST_N is needed to allows for 0 as n, which is not used here, so (nil) can be eliminated. As a consequence, arithmetic ssaturation can be avoided as well.

Cheers

Wolf Lammen

Sun, 04 Jul 2010 15:59:13 GMT

a) some include's should be present to keep the code self contained

b) use explicit macro name BOOST_PP_SEQ_REST_N_PLUS_1

******
#  *                                                                          *
#  *     (C) Copyright Paul Mensonides 2002.
#  *     Distributed under the Boost Software License, Version 1.0. (See
#  *     accompanying file LICENSE_1_0.txt or copy at
#  *     http://www.boost.org/LICENSE_1_0.txt)
#  *                                                                          *
#  ************************************************************************** */
#
# /* See http://www.boost.org for most recent version. */
#
# ifndef BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
# define BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
#
# include <boost/preprocessor/arithmetic/inc.hpp>
# include <boost/preprocessor/config/config.hpp>
# include <boost/preprocessor/seq/detail/split.hpp>
# include <boost/preprocessor/seq/first_n.hpp>
# include <boost/preprocessor/facilities/empty.hpp>
# include <boost/preprocessor/tuple/elem.hpp>
#
# /* BOOST_PP_SEQ_REPLACE */
#
# if ~BOOST_PP_CONFIG_FLAGS() & BOOST_PP_CONFIG_EDG()
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_N_PLUS_1(i, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# else
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_REPLACE_I(seq, i, elem)
#    define BOOST_PP_SEQ_REPLACE_I(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_NP1(i, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1(i, seq) BOOST_PP_SEQ_REST_N_PLUS_1_I(n, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1_I(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# endif
#
# endif

ookami1@… — Mon, 05 Jul 2010 07:37:40 GMT

somehow I missed a couple of characters when copying & pasting the code. Make sure the first (commentary) line looks more like

#  /***************************************************************************

Sun, 11 Jul 2010 06:31:37 GMT

wrote a test suite checking my fix. It found a bug in the EDG branch. Here's the updated file:

#  ****************************************************************************
#  *                                                                          *
#  *     (C) Copyright Paul Mensonides 2002.
#  *     Distributed under the Boost Software License, Version 1.0. (See
#  *     accompanying file LICENSE_1_0.txt or copy at
#  *     http://www.boost.org/LICENSE_1_0.txt)
#  *                                                                          *
#  ************************************************************************** */
#
# /* See http://www.boost.org for most recent version. */
#
# ifndef BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
# define BOOST_PREPROCESSOR_SEQ_REPLACE_HPP
#
# include <boost/preprocessor/arithmetic/inc.hpp>
# include <boost/preprocessor/config/config.hpp>
# include <boost/preprocessor/seq/detail/split.hpp>
# include <boost/preprocessor/seq/first_n.hpp>
# include <boost/preprocessor/facilities/empty.hpp>
# include <boost/preprocessor/tuple/elem.hpp>
#
# /* BOOST_PP_SEQ_REPLACE */
#
# if ~BOOST_PP_CONFIG_FLAGS() & BOOST_PP_CONFIG_EDG()
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_N_PLUS_1(i, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# else
#    define BOOST_PP_SEQ_REPLACE(seq, i, elem) BOOST_PP_SEQ_REPLACE_I(seq, i, elem)
#    define BOOST_PP_SEQ_REPLACE_I(seq, i, elem) BOOST_PP_SEQ_FIRST_N(i, seq) (elem) BOOST_PP_SEQ_REST_NP1(i, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1(n, seq) BOOST_PP_SEQ_REST_N_PLUS_1_I(n, seq)
#    define BOOST_PP_SEQ_REST_N_PLUS_1_I(n, seq) BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_SPLIT(BOOST_PP_INC(n), seq BOOST_PP_EMPTY))()
# endif
#
# endif

Edward Diener — Mon, 18 May 2015 20:38:57 GMT

Fixed in the latest preprocessor code on the 'develop' branch.

anonymous — Sun, 24 May 2015 07:54:03 GMT

Replying to eldiener:

Fixed in the latest preprocessor code on the 'develop' branch.

I cannot check the develop branch as I use only git, so I don't know whether you spotted the following yourself.

5 years ago I wrote "wrote a test suite checking my fix. It found a bug in the EDG branch", because the renaming BOOST_PP_SEQ_REST_NP1 -> BOOST_PP_SEQ_REST_N_PLUS_1 wasn't carried out completely.

Unfortunately, the code in comment5 isn't the fixed one. It still refers to BOOST_PP_SEQ_REST_NP1 in one place, like the one in comment3.

I am awfully sorry for that.

Wolf Lammen

Edward Diener — Sun, 24 May 2015 11:56:06 GMT

| "I cannot check the develop branch as I use only git"

I do not know what this means.

The 'develop' branch uses Boost on Github, which means Boost now uses git. My solution does not involve your patches.

For getting the latest Boost source on git, see https://svn.boost.org/trac/boost/wiki/ModularBoost and https://svn.boost.org/trac/boost/wiki/TryModBoost.

ookami1@… — Sun, 24 May 2015 13:56:33 GMT

Replying to eldiener:

| "I cannot check the develop branch as I use only git"

I do not know what this means.

I checked out 'develop' on the top level directory, which did not affect the subdirectory 'libs/preprocessor'.

After checking out 'develop' in 'libs/preprocessor' I can see your changes now.

Seems I did not understand the organization of the boost source tree at once. So, please, forgive me. I just posted the comment in order to prevent a glitch making its way into boost sources.

Wolf Lammen

ookami1@… — Sun, 24 May 2015 17:49:41 GMT

After having looked at your solution, here are my comments:

Lets look at BOOST_PP_SEQ_REPLACE((a),0,b)

I can tell from the list of replacements that you somewhere in the middle call

BOOST_PP_SEQ_FIRST_N(0,(a))

expecting it to return an empty replacement.

Ok, we know both, BOOST_PP_SEQ_FIRST_N does the right thing by pure chance and returns an empty sequence. But given your formalistic stance, shouldn't usage of index 0 with BOOST_PP_SEQ_FIRST_N be banned as much as BOOST_PP_SEQ_REST_N is with an index == size of sequence? Don't you rely on undefined behavior as well?

And your solution comes with a price: The number of replacements increases from 28 to 38 in the above simple case, goes up from 57 to 117 in a 24-element sequence, such getting worse by the size. Another minor fault is the different spacing in the part before a replacement and after it: "(a) (a) (a) (b) (a)(a)(a)". This is less of a problem as long as you do just macro magic, but becomes essentiell once you stringize a sequence as I did.

See, you and Mr Mensonides had difficulties in getting these things right, let alone an averaged programmer like me. If you ask me, I still prefer a change in interface and let BOOST_PP_SEQ_FIRST_N and BOOST_PP_SEQ_REST_N either return a sequence, if exists, or an empty string, in the range 0..size of seq. This is the right result in all instances where you concatenate sequences, and it does not hurt elsewhere.

cheers Wolf

Edward Diener — Sun, 24 May 2015 18:25:55 GMT

I agree with you that I am relying on what I tell the user is undefined behavior. But that does not mean that the user should rely on that behavior. In particular I do not want the user to rely on such behavior.

You talk about a change in interface as if it exists in an ideal vacuum. What happens when that change of interface starts breaking current code, such as thousands of lines that used to work fine ? No, sir, while I might be willing to add some new macro I am not going to break anything which people using Boost PP rely on.

In your approach an empty seq is perfectly fine, despite the fact that testing for emptiness is highly flawed when variadic macros are not supported by the compiler. I know about this issue as my entire Boost.VMD library is based around the fact that for a compiler which does support variadic macros ( which VMD must have ) testing for emptiness is still very slightly flawed, but the VMD library can live with that flaw. In Boost PP allowing a seq to be empty, ( or allowing a tuple to be empty ), is going to cause all sorts of problems in Boost PP simply because it cannot be reliably tested in a library which does support non-variadic macros.

I could add to VMD a tuple or a seq which could be empty, because then those who use VMD functionality to work with such a seq or tuple will not be involved with code breakage, but I am not going to do it with Boost PP.

If you want to propose a separate macro to be added to Boost PP please feel free to do it. I admit I did not look deeply into your solution because I was looking for the easiest fix. If your fix is much more efficient, using either a separate public macro, or a separate internal macro, I will look at this issue again. But please realize that having empty seqs ( or tuples ) in current Boost PP, or changing how the public macro BOOST_PP_SEQ_REST_N works or should be used, is not an option.

ookami1@… — Sun, 24 May 2015 23:07:04 GMT

In your approach an empty seq is perfectly fine, despite the fact that testing for emptiness is highly flawed..

I'm well aware of the limitations of empty sequences, and therefore do not propose their support. As I wrote in #4421

"seq_first_rest_n.patch fixes BOOST_PP_SEQ_FIRST_N and BOOST_PP_SEQ_REST_N, so they both accept sequences of length 256 now. As a bonus feature, for preprocessors sufficiantly handling empty arguments (or those expanding to nothing), both macros process empty sequences as well. Usage of empty sequences is outside of the specs of the preprocessor code, and is not generally supported by the preprocessor library."

This is not about general support of empty sequences, let alone about breaking interfaces (When only did I propose that??). This is about more robustness. And that is seemingly needed, as you can see from the following bug, again because of bad usage of BOOST_PP_SEQ_REST_N (SEQ_256 is defined as above in the bug report)

// does not remove the last element
char x[] = BOOST_PP_STRINGIZE(BOOST_PP_SEQ_REMOVE(SEQ_256,255));

People, Boost programmers not excluded, seem to misunderstand/disregard the interface of these macros on a regular base, fortunately without consequences most of the time.

Ok, that is why I had preferred seeing after both macros. I guess they are mostly used when sequences are rearranged. In that context, at the head or tail of a sequence, an empty expansion (!= empty sequence) is a sensible result, at least better than the same result, occasionally replaced with junk.

And yes, I know that variadic macros provide better support. And that template programming is often a viable replacement for macros. This here is all about technology from the past decade. The bug number stands for that.

Edward Diener — Mon, 25 May 2015 00:10:04 GMT

What do you mean by:

"BOOST_PP_SEQ_FIRST_N and BOOST_PP_SEQ_REST_N, so they both accept sequences of length 256 now" ?

If there is a bug involving them and a seq of 256 elements would you please file separate bug reports or make a pull request on the preprocessor 'develop' branch and I will look at it.

Similarly if BOOST_PP_SEQ_REMOVE fails in the situation above would you please file a separate bug report or make a pull request on the preprocessor 'develop' branch and I will look at it.

anonymous — Tue, 26 May 2015 14:17:38 GMT

Replying to eldiener:

What do you mean by:

"BOOST_PP_SEQ_FIRST_N and BOOST_PP_SEQ_REST_N, so they both accept sequences of length 256 now" ?

If there is a bug involving them and a seq of 256 elements would you please file separate bug reports or make a pull request on the preprocessor 'develop' branch and I will look at it.

Meaning, I am repeating myself over and over again. I think, by now I made clear enough, what this is about.

Similarly if BOOST_PP_SEQ_REMOVE fails in the situation above would you please file a separate bug report or make a pull request on the preprocessor 'develop' branch and I will look at it.

You can safely drop the 'if'.

I did not present the bug in order to set off another round in symptom hunting and curing. I wanted to prove by evidence that not adhering to http://en.wikipedia.org/wiki/Design_by_contract has its decent downsides. IMHO either fixing 1 serving macro or hundreds of invocations is in order.

I am certain you have good reason to address this issue in a different manner, but as far as I am concerned, I am out of business.

Wolf Lammen

Edward Diener — Sun, 31 May 2015 04:29:19 GMT

I have fixed the problem with BOOST_PP_SEQ_REMOVE on the 'develop' branch. I also went through all the basic seq operations dealing with changes to a seq of the maximum of 256 elements to make sure they now work properly.

Edward Diener — Fri, 21 Aug 2015 13:35:22 GMT

The problem is now fixed in the latest Boost 1.59 release.

status changed; resolution set

Edward Diener — Fri, 21 Aug 2015 13:37:04 GMT

status new → closed
resolution → fixed