[Boost-bugs] [Boost C++ Libraries] #4455: clean up preprocessor/seq/fold_left.hpp

Subject: [Boost-bugs] [Boost C++ Libraries] #4455: clean up preprocessor/seq/fold_left.hpp
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-07-20 15:06:02

#4455: clean up preprocessor/seq/fold_left.hpp
--------------------------+-------------------------------------------------
 Reporter:  anonymous     |       Owner:         
     Type:  Bugs          |      Status:  new    
Milestone:  Boost 1.44.0  |   Component:  None   
  Version:  Boost 1.44.0  |    Severity:  Problem
 Keywords:                |  
--------------------------+-------------------------------------------------
 introductionary notes:

 BOOST_PP_SEQ_FOLD_LEFT is a macro that applies a submitted macro
 (henceforth called operation) to all elements of a sequence, starting with
 element 0 (leftmost). The operation macro op(n, state, elem) takes three
 arguments, the first being a counter starting from 2 and incremented after
 each operation, second, an arbitrary sequence of preprocessing tokens
 comprising the intermediate result (or current state), and finally the
 current element, stripped of the embracing parentheses. The result of the
 operation is an updated state, passed on to the next call to the
 operation.

 BOOST_PP_SEQ_FOLD_LEFT is called with three parameters: first, the name of
 the operation macro, second, the initial state, and third, the sequence to
 which to apply the operation element-wise. It returnes the final state.

 Since the above mentioned counter starts from 2, submitting a sequence of
 length 256 to BOOST_SEQ_FOLD_LEFT will result in a final call to the
 operation macro with its first parameter set to 257. I neither expect a
 counter starting from anything but 0 or 1, nor do I expect, it might get
 me out of the arithmetic range, so I consider this a really bad design
 decision.

 The 1.43 implementation of BOOST_PP_SEQ_FOLD_LEFT contains a huge amount
 of what seems to be leftovers from a major rework, not having been removed
 yet, and, in addition, allows for significant reduction of evaluation
 costs.

 fold_left.hpp is now simplified in 3 major steps.

 step 1:

 The definition of BOOST_PP_SEQ_FOLD_LEFT entails a call to
 BOOST_PP_AUTO_REC. In short, this call turns out to be completely
 pointless, as it will always return 1 as result, and can be simply
 replaced by this constant.

 This can be seen as follows:

 BOOST_PP_AUTO_REC operates on macros P(n), that
 - take integers from 1 to 256 as paramater;
 - are binary, i.e. yields only 0 or 1 as a result;
 - are monotonely rising, i.e. there is an integer n such that P(i) == 0
 for i < n and == 1 otherwise.
 BOOST_PP_AUTO_SEC is designed to find the 'leap position' where P assumes
 1 for the first time.

 BOOST_PP_SEQ_FOLD_LEFT_P is such a P(n). Although the replacement of
 BOOST_PP_SEQ_FOLD_LEFT_P looks complex, a closer look at


 {{{
 BOOST_PP_SEQ_FOLD_LEFT_I_ ## n(BOOST_PP_SEQ_FOLD_LEFT_O, BOOST_PP_NIL,
 (nil), 1)
 }}}


 reveals, that this expression, independently of n, will always expand to
 BOOST_PP_NIL, and after some more replacing, BOOST_PP_SEQ_FOLD_LEFT_P
 turns out to be constantly 1. Consequently, BOOST_PP_AUTO_REC, applied to
 this (constant) macro, will yield 1 as a result.

 Hence simplify the definition of BOOST_PP_SEQ_FOLD_LEFT:


 {{{
 # define BOOST_PP_SEQ_FOLD_LEFT BOOST_PP_SEQ_FOLD_LEFT_1
 }}}


 step 2:

 Now, that BOOST_PP_SEQ_FOLD_LEFT_P has been eliminated, its definition may
 be removed. Then, none of the BOOST_PP_SEQ_FOLD_LEFT_CHECK_* macros are
 called any more (not only in fold_left.hpp, but throughout the whole
 preprocessor branch). The same holds for some other macros as well. Here
 is the list:
 - BOOST_PP_SEQ_FOLD_LEFT_P;
 - BOOST_PP_SEQ_FOLD_LEFT_O;
 - BOOST_PP_SEQ_FOLD_LEFT_CHECK_*;
 - BOOST_PP_SEQ_FOLD_LEFT_*257;
 - BOOST_PP_SEQ_FOLD_LEFT_n for 2 <= n <= 256;

 Drop their definitions.

 step 3

 The loop iterating over the elements has been unrolled disadvantageously.
 Although the length of the sequence is determined in advance, the loop
 starts in a forward manner and, thus, has to permanently check when to
 terminate. A countdown strategy is more appropriate here, automatically
 terminating when iteration 1 is reached. This saves a couple of macro
 replacements per iteration. Because of the 257 quirk of
 BOOST_PP_SEQ_FOLD_LEFT mentioned in the first section, an extra parameter
 q257 has to be introduced, controlling the setting of the counter to the
 somewhat irregular value 257 when a sequence of length 256 is encountered.

 While the reduction and dropping in step 1 and 2 should not be affected by
 preprocessor quirks, the optimization carried out here might be
 susceptible to them. So, for safety reasons, this optimization takes
 effect only when BOOST_PP_CONFIG_FLAGS() is equal to
 BOOST_PP_CONFIG_STRICT().

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4455>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.