wrong order of elements in QList

[qtbeginner0]

Hi all,

I'm trying to find out the cause of a bug in an open source project (LibreCAD). I am at my wit's end.
The problem is (from the perspective of a user) that some arcs are drawn in the wrong direction.
Here is an example:


The left half of the image is the way how it should look like. On the right side you can see the bug.
It's an image of a 0,0/200,100 rectangle which should be filled with a hatch (the hatch is called "arcs")

What some other guys and I found out so far:
#this bug seems to be present in release version only
#may!!! only effect 32bit os

My recent debugging orgy led to these results:
The order of the start point and end point of the arc to be drawn are transposed in the QList "is2":

QList<std::shared_ptr<RS_Vector> > is2;

QList<std::shared_ptr<RS_Vector> > is2;

To copy to clipboard, switch view to plain text mode 

As "is2" is created/filled in the sort section I think the bug have to be somewhere there.
Here is the code snippet of the sorting:

...
// sort the intersection points into is2:
        RS_Vector sp = startPoint;
        double sa = center.angleTo(sp);
        if(ellipse != NULL) sa=ellipse->getEllipseAngle(sp);
        QList<std::shared_ptr<RS_Vector> > is2;
        bool done;
        double minDist;
        double dist = 0.0;
        std::shared_ptr<RS_Vector> av;
        std::shared_ptr<RS_Vector> v;
        RS_Vector last = RS_Vector(false);
        do {
            done = true;
            minDist = RS_MAXDOUBLE;
            av.reset();
            for (int i = 0; i < is.size(); ++i) {
                v = is.at(i);
                double a;
                switch(e->rtti()){
                case RS2::EntityLine:
                    dist = sp.distanceTo(*v);
                    break;
                case RS2::EntityArc:
                case RS2::EntityCircle:
                    a = center.angleTo(*v);
                    dist = reversed?
                                fmod(sa - a + 2.*M_PI,2.*M_PI):
                                fmod(a - sa + 2.*M_PI,2.*M_PI);
                    break;
                case RS2::EntityEllipse:
                    a = ellipse->getEllipseAngle(*v);
                    dist = reversed?
                                fmod(sa - a + 2.*M_PI,2.*M_PI):
                                fmod(a - sa + 2.*M_PI,2.*M_PI);
                    break;
                default:
                    break;
 
                }
 
                if (dist<minDist) {
                    minDist = dist;
                    done = false;
                    av = v;
                }
            }
 
            // copy to sorted list, removing double points
            if (!done && av.get()!=NULL) {
                if (last.valid==false || last.distanceTo(*av)>RS_TOLERANCE) {
                    is2.append(std::shared_ptr<RS_Vector>(new RS_Vector(*av)));
                    last = *av;
                }
#if QT_VERSION < 0x040400
                emu_qt44_removeOne(is, av);
#else
                is.removeOne(av);
#endif
 
                av.reset();
            }
        } while(!done);
...

...
// sort the intersection points into is2:
        RS_Vector sp = startPoint;
        double sa = center.angleTo(sp);
        if(ellipse != NULL) sa=ellipse->getEllipseAngle(sp);
        QList<std::shared_ptr<RS_Vector> > is2;
        bool done;
        double minDist;
        double dist = 0.0;
        std::shared_ptr<RS_Vector> av;
        std::shared_ptr<RS_Vector> v;
        RS_Vector last = RS_Vector(false);
        do {
            done = true;
            minDist = RS_MAXDOUBLE;
            av.reset();
            for (int i = 0; i < is.size(); ++i) {
                v = is.at(i);
                double a;
                switch(e->rtti()){
                case RS2::EntityLine:
                    dist = sp.distanceTo(*v);
                    break;
                case RS2::EntityArc:
                case RS2::EntityCircle:
                    a = center.angleTo(*v);
                    dist = reversed?
                                fmod(sa - a + 2.*M_PI,2.*M_PI):
                                fmod(a - sa + 2.*M_PI,2.*M_PI);
                    break;
                case RS2::EntityEllipse:
                    a = ellipse->getEllipseAngle(*v);
                    dist = reversed?
                                fmod(sa - a + 2.*M_PI,2.*M_PI):
                                fmod(a - sa + 2.*M_PI,2.*M_PI);
                    break;
                default:
                    break;

                }

                if (dist<minDist) {
                    minDist = dist;
                    done = false;
                    av = v;
                }
            }

            // copy to sorted list, removing double points
            if (!done && av.get()!=NULL) {
                if (last.valid==false || last.distanceTo(*av)>RS_TOLERANCE) {
                    is2.append(std::shared_ptr<RS_Vector>(new RS_Vector(*av)));
                    last = *av;
                }
#if QT_VERSION < 0x040400
                emu_qt44_removeOne(is, av);
#else
                is.removeOne(av);
#endif

                av.reset();
            }
        } while(!done);
...

To copy to clipboard, switch view to plain text mode 

The sort process should sort the points/elements in the list "is" and add them in the correct order* to "is2".
*the order should be: start point, the point next to the start point, ..., the end point

The funny thing (at least for me) is, when I add qDebug("angle centerToNextIntersection: %f",a);
after these lines :

case RS2::EntityArc:
case RS2::EntityCircle:
       a = center.angleTo(*v);
       dist = reversed?
                     fmod(sa - a + 2.*M_PI,2.*M_PI):
                     fmod(a - sa + 2.*M_PI,2.*M_PI);
->here->here->

case RS2::EntityArc:
case RS2::EntityCircle:
       a = center.angleTo(*v);
       dist = reversed?
                     fmod(sa - a + 2.*M_PI,2.*M_PI):
                     fmod(a - sa + 2.*M_PI,2.*M_PI);
->here->here->

To copy to clipboard, switch view to plain text mode 

the weird behaviour seems to be gone!

If you would like to have a look at the discussion of this bug in the LibreCAD forum (there are more pictures of the bug):
http://forum.librecad.org/bugs-probl...tp5708894.html

If you would like to have a look at the whole file where the bug is present:
https://github.com/LibreCAD/LibreCAD...e/rs_hatch.cpp
(the sort process begins at about the line 335)

Are the elements of QList added/removed in the wrong way?
What could also lead to a behaviour where the order of QList may become upside down/incorrect?

ANY help is appreciated!
(also hints about things I could try)

using:
ubuntu 12.04 32bit
Compiler: GNU GCC 4.6.3
Qt Version: 4.8.1

[Lesiok]

QList is not sorted list. Conclusion is that your sorting function is not working properly.

[stampede]

ANY help is appreciated!
(also hints about things I could try)

Try to insert elements to "is" in correct order to avoid the sorting function.

[Lesiok]

It may be easier to make a comparison function two items and apply standard qsort function ?

[qtbeginner0]

Thanks for the replys guys. As I would like to understand the bug first I will try the workarounds after that.
After you pointed me to the sorting, I did some more research.
Can someone explain the strange stepping through the code in QtCreator?
(the order of the steps when I use "Step Over" are placed at the end of the code lines)

case RS2::EntityCircle:  
  a = center.angleTo(*v);                                                  1.
  dist = reversed?
              fmod(sa - a + 2.*M_PI,2.*M_PI):                              3.
              fmod(a - sa + 2.*M_PI,2.*M_PI);                              2. 4. 6.
//            qDebug("angle centerTostartPoint: %f",sa);
//            qDebug("angle centerToNextIntersection: %f",a);
//            qDebug("distance: %f",dist);
  qDebug("counted the useres: %d",v.use_count());                          5. 7.
  break;

case RS2::EntityCircle:  
  a = center.angleTo(*v);                                                  1.
  dist = reversed?
              fmod(sa - a + 2.*M_PI,2.*M_PI):                              3.
              fmod(a - sa + 2.*M_PI,2.*M_PI);                              2. 4. 6.
//            qDebug("angle centerTostartPoint: %f",sa);
//            qDebug("angle centerToNextIntersection: %f",a);
//            qDebug("distance: %f",dist);
  qDebug("counted the useres: %d",v.use_count());                          5. 7.
  break;

To copy to clipboard, switch view to plain text mode 

I would have expected the following order of the stepping:
line2
line5 (until now that's the same what QtCreator does; reversed is false)
line9

[wysota]

What is so strange in the order the debugger steps through the code? That's the order the code executes.

[qtbeginner0]

What I don't understand is, why QtCreator steps to line 4 in the 3. step. Cause reversed is false, shouldn't it just leave out line 4?
Why does QtCreator execute line 5 again in step 4? Wasn't that already done in step 2. ?
Why does QtCreator jump back to line 5 in step 6. for the third time?

What I was thinking it would do:
1. assign a ->line 2
2. check reversed -> line 3
3. reversed is false -> line 5
4. assign dist -> line 3
5. qDebug

[wysota]

Creator does not step into anything. The debugger does based on the order of which instructions are executed. Apparently the compiler builds the code in such a way, that the execution takes place in such particular order. As for "line 4" in my opinion this is a mark that the "?" instruction is executed and as it is the last symbol in line 3, the compiler (becasue of whatever reason) marks it as the next line. I really wouldn't worry about this, if you have doubts take a look at the instructions on assembly level or disable optimizations and then run the code through the debugger again. All this however does not bring you any closer to solving your original problem.

What I was thinking it would do:
1. assign a ->line 2
2. check reversed -> line 3
3. reversed is false -> line 5
4. assign dist -> line 3
5. qDebug

I would think it first calculates 2.*M_PI as this is used in both cases so it can be precalculated, then it'd check the condition, calculate sa-a or a-sa based on the condition, then add the result to 2*M_PI, then execute fmod on the result, then assign it to the dist variable and finally print out the debug statement. Of course, if v.use_count() is independent of the result of "dist", the compiler might put the debug statement between any two instructions in the whole section.

[qtbeginner0]

All this however does not bring you any closer to solving your original problem.

Ok.

...the compiler might put the debug statement between any two instructions in the whole section

Didn't know that.

So I had some more debugging fun.
The problem is, that calculation of "a" is a little off compared to sa.
I don't know why this happens cause both angles are calculated using the SAME function and the SAME
point.

double sa = center.angleTo(sp);
...
double a;
...
a = center.angleTo(*v);

double sa = center.angleTo(sp);
...
double a;
...
a = center.angleTo(*v);

To copy to clipboard, switch view to plain text mode 

double angleTo(const RS_Vector& v) const;

double angleTo(const RS_Vector& v) const;

To copy to clipboard, switch view to plain text mode 

here is sp and v from the watch list (they are the same point/coordinates)

sp RS_Vector
valid true bool
x 170.15564366033121 double
y 20.000000048775643 double
z 0 double


v std::shared_ptr<RS_Vector>
__shared_ptr<RS_Vector, (__gnu_cxx::_Lock_policy)2> std::__shared_ptr<RS_Vector, (__gnu_cxx::_Lock_policy)2>
_M_ptr @0x8ac7ff0 RS_Vector
valid true bool
x 170.15564366033121 double
y 20.000000048775643 double
z 0 double
_M_refcount std::__shared_count<(__gnu_cxx::_Lock_policy)2>



here is the result of a - sa (as you can see it's e-16) (should be 0 as it is the same point in this case)

result of a - sa: -4.4408920985006261617e-16

As I already told, adding qDebug("angle centerToNextIntersection: %f",a) will somehow lead to
the result 0 of a - sa. Does anybody have an idea what qDebug does to "a"?
I don't get how qDebug does influence the calculation of "a" and why the reseults of calculating
the same angle of the same point using the same function, differ from each other (without qDebug())?