[GiNaC-devel] Questions about expairseq::match().

[Jens Vollinga]

Hi,

see
   http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
for an explanation.

Alexei Sheplyakov schrieb:
> This fragment looks a bit confusing. it->match(p, repl_lst) can change
> repl_lst, so iterators become invalid. Fortunately, in that case match
> returns true, so we jump out of the loop. So, we can initialize
> the iterator last_el *after* checking for possible matches, like this:
> 
>                                     if (it->match(p, repl_lst)) {
>                                             ops.erase(it);
>                                             goto found;
>                                     }
>                                     lst::const_iterator last_el = repl_lst.end();
>                                     --last_el;
> 
> Unless I'm missing something this code is equivalent to the previous
> variant, but it's more readable (i.e. no confusion about possible invalidation
> of last_el iterator).

It also looks strange to me, but I am not 100% sure whether it is wrong 
or serves some purpose, yet.

> 436                                 while(true) {
> 437                                         lst::const_iterator next_el = last_el;
> 438                                         ++next_el;
> 439                                         if(next_el == repl_lst.end())
> 440                                                 break;
> 441                                         else
> 442                                                 repl_lst.remove_last();
> 443                                 }
> 
> There's definitely something fishy about this chunk. First of all, it seems
> like next_el at the line 439 is always repl_lst.end(), so this code doesn't
> do anything at all. Secondly, if it next_el ever changes its value from
> repl_lst.end(), repl_lst.remove_last() invalidates iterators (both next_el
> *and* last_el), so the result of next iteration is unpredictable.

First, in the current code last_el can be different from repl_lst.end() 
if in line 432 the call to match changes repl_lst.
Second, (almost) no iterators are invalidated here. These are list 
iterators, not vector or deque iterators! The "almost" refers to the 
recursive call of match in line 432. Obviously, repl_lst is expected to 
change, but the code seems to be okay only for the case that the last 
element in repl_lst is not deleted. I am not sure about this yet, as I 
wrote above.

Regards,
Jens