Re: Fusion-ifying proto parse trees

Joel de Guzman wrote:
> Eric Niebler wrote:
> > Joel de Guzman wrote:
> > > Eric Niebler wrote:
> > > > What do you think? Zero-copy expression template construction and 
> > > > segmented iteration over the tree -- I think there's potential there.
> > >
> > > Or, simply use the raw view returned from push_back without doing
> > > a fusion::as_list call. That also amounts to zero-copy expression
> > > template construction.
> >
> >
> > Yes, sure but then the view returned by push_back will be, 
> > essentially, a proto parse tree. :-) And you'll want Fusion algorithms 
> > to work efficiently with them, so they should use a segmented 
> > iteration scheme. In other words, a Fusion join_view is a text-book 
> > example of a segmented data structure. If we add segmented algorithms 
> > to Fusion, they'll work better with your lazy views.
>
> Not quite. I still have information about the types of nodes that
> are collapsable, so, the resulting view will be essentially flat.
> I won't try to convince you, now, other than to say that I've
> thought about this scheme already and I *can* prove that the
> resulting view is trivially and *externally* iteratable.


I'm looking at the code, and I'm not seeing it. What I see in 
joint_view/detail/next_impl.hpp is this:

   template <>
   struct next_impl<joint_view_iterator_tag>
   {
       template <typename Iterator>
       struct apply
       {
           typedef typename Iterator::first_type first_type;
           typedef typename Iterator::last_type last_type;
           typedef typename Iterator::concat_type concat_type;
           typedef typename result_of::next<first_type>::type next_type;
           typedef result_of::equal_to<next_type, last_type> equal_to;

           typedef typename
               mpl::if_<
                   equal_to
                 , concat_type
                 , joint_view_iterator<
                       next_type, last_type, concat_type>
               >::type
           type;


Every time you increment a joint view iterator, you're checking to see 
if you've reached the end of the first sequence, so you know when to 
start the second. And if Iterator::first_type is itself a joint view 
iterator, it *also* must check to see if it's at the end of *its* first 
sequence to know if it should start its second. And so on. If you do a 
bunch of push_backs and end up with a joint_view of a joint_view of a 
joint_view, iterating it will be far from trivial. This sort of 
flattening-on-the-fly is *exactly* the problem that non-segmented proto 
has, and is the problem that segmented iterators solve.


> For the record, I agree that it would be good fusion to have
> the segmented algos. It's just that I am not yet convinced that
> Spirit-2 needs to use them. There must be a simpler solution and
> that's what I am aiming for.


A simpler solution would be nice. The current implementation of 
join_view_iterator can't get much simpler. It can get faster, though. ;-)


--
Eric Niebler
Boost Consulting
www.boost-consulting.com


-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642