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

[Alexei Sheplyakov]

Hi!

I've stumbled upon the following code in ginac/exparseq.cpp:expairseq::match()

422                 // Now, for every term of the pattern, look for a matching term in
423                 // the expression and remove the match
424                 for (size_t i=0; i<pattern.nops(); i++) {
425                         ex p = pattern.op(i);
426                         if (has_global_wildcard && p.is_equal(global_wildcard))
427                                 continue;
428                         exvector::iterator it = ops.begin(), itend = ops.end();
429                         while (it != itend) {

So far so good...

430                                 lst::const_iterator last_el = repl_lst.end();
431                                 --last_el;
432                                 if (it->match(p, repl_lst)) {
433                                         ops.erase(it);
434                                         goto found;
435                                 }

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).


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.

So, the questions are:

1. What I'm missing here?
2. What is the actual purpose of this code (lines 436 -- 443)?
3. According to git-blame, this (a little bit strange) code was introduced
by commit 73f0ce4cf8d91f073f35a45443f5fbe886921c5c. The commit message says:
"Fixed bug in ::match." What was the bug in first place?

Could anyone please enlighten me?

Best regards,
	Alexei


-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20080714/64943a2e/attachment.sig