QGAL: identify unfeasible setups even when graph is simplified

The calculate graphs now can return early due to unfeasible anchor
setups found out during simplification. This allows finding out
problems in parallel anchors, when one anchor has maximum size smaller
than the minimum size of the other anchor.

The order for simplification and refreshing size hints also has been swaped:

- First, refresh size hints for all anchors in the graph. If the graph is
  simplified, the refreshSizeHints() call will reach the children anchors.
- Then, if the simplificated graph is invalid, rebuild it. During this
  rebuild, refreshSizeHints_helper() will be called for all levels.

So in both situations we can identify an unfeasible setup.  Note that
this test alone is not enough to classify the graph as feasible, depending
on the graph, it will still need to go through the Simplex.

A test case was added and the function that traverse the graph
refreshing now is called refreshAllSizeHints(). The old name was not
so clear since the function will not fill only the anchors that have
items associated.

Last but not least, the lastCalculationUsedSimplex variable is cleared
when starting calculateGraphs(), since we now can leave the function
earlier, without reaching calculateTrunk(), which is the function that
sets it.

Signed-off-by: Caio Marcelo de Oliveira Filho <caio.oliveira@openbossa.org>
Reviewed-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org>

3 files changed, 122 insertions, 34 deletions

diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
index 8b7ff08..8d13b2b 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -648,15 +648,17 @@ static AnchorData *createSequence(Graph<AnchorVertex, AnchorData> *graph,
    2. Go to (1)
    3. Done
 
+   When creating the parallel anchors, the algorithm might identify unfeasible situations. In this
+   case the simplification process stops and returns false. Otherwise returns true.
 */
-void QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
+bool QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
 {
     static bool noSimplification = !qgetenv("QT_ANCHORLAYOUT_NO_SIMPLIFICATION").isEmpty();
     if (noSimplification || items.isEmpty())
-        return;
+        return true;
 
     if (graphSimplified[orientation])
-        return;
+        return true;
     graphSimplified[orientation] = true;
 
 #if 0
@@ -665,12 +667,18 @@ void QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
 #endif
 
     if (!graph[orientation].rootVertex())
-        return;
+        return true;
 
     bool dirty;
+    bool feasible = true;
     do {
-        dirty = simplifyGraphIteration(orientation);
-    } while (dirty);
+        dirty = simplifyGraphIteration(orientation, &feasible);
+    } while (dirty && feasible);
+
+    if (!feasible)
+        graphSimplified[orientation] = false;
+
+    return feasible;
 }
 
 /*!
@@ -687,7 +695,8 @@ void QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
     Note that there are some catches to this that are not covered by the above explanation, see
     the function comments for more details.
 */
-bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutPrivate::Orientation orientation)
+bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutPrivate::Orientation orientation,
+                                                          bool *feasible)
 {
     Q_Q(QGraphicsAnchorLayout);
     Graph<AnchorVertex, AnchorData> &g = graph[orientation];
@@ -835,6 +844,11 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
         // create a parallel anchor between the new sequence and the old anchor.
         AnchorData *newAnchor = addAnchorMaybeParallel(&g, sequence);
 
+        if (!newAnchor) {
+            *feasible = false;
+            return false;
+        }
+
         // When a new parallel anchor is create in the graph, we finish the iteration and return
         // true to indicate a new iteration is needed. This happens because a parallel anchor
         // changes the number of adjacents one vertex has, possibly opening up oportunities for
@@ -1679,38 +1693,52 @@ QList<AnchorData *> getVariables(QList<QSimplexConstraint *> constraints)
 }
 
 /*!
-  \internal
+    \internal
 
-  Calculate graphs is the method that puts together all the helper routines
-  so that the AnchorLayout can calculate the sizes of each item.
+    Calculate graphs is the method that puts together all the helper routines
+    so that the AnchorLayout can calculate the sizes of each item.
 
-  In a nutshell it should do:
+    In a nutshell it should do:
 
-  1) Update anchor nominal sizes, that is, the size that each anchor would
-     have if no other restrictions applied. This is done by quering the
-     layout style and the sizeHints of the items belonging to the layout.
+    1) Refresh anchor nominal sizes, that is, the size that each anchor would
+       have if no other restrictions applied. This is done by quering the
+       layout style and the sizeHints of the items belonging to the layout.
 
-  2) Simplify the graph by grouping together parallel and sequential anchors
-     into "group anchors". These have equivalent minimum, preferred and maximum
-     sizeHints as the anchors they replace.
+    2) Simplify the graph by grouping together parallel and sequential anchors
+       into "group anchors". These have equivalent minimum, preferred and maximum
+       sizeHints as the anchors they replace.
 
-  3) Check if we got to a trivial case. In some cases, the whole graph can be
-     simplified into a single anchor. If so, use this information. If not,
-     then call the Simplex solver to calculate the anchors sizes.
+    3) Check if we got to a trivial case. In some cases, the whole graph can be
+       simplified into a single anchor. If so, use this information. If not,
+       then call the Simplex solver to calculate the anchors sizes.
 
-  4) Once the root anchors had its sizes calculated, propagate that to the
-     anchors they represent.
+    4) Once the root anchors had its sizes calculated, propagate that to the
+       anchors they represent.
 */
 void QGraphicsAnchorLayoutPrivate::calculateGraphs(
     QGraphicsAnchorLayoutPrivate::Orientation orientation)
 {
     Q_Q(QGraphicsAnchorLayout);
 
-    // Simplify the graph
-    simplifyGraph(orientation);
+#if defined(QT_DEBUG) || defined(Q_AUTOTEST_EXPORT)
+    lastCalculationUsedSimplex[orientation] = false;
+#endif
+
+    // Reset the nominal sizes of each anchor based on the current item sizes.  This function
+    // works with both simplified and non-simplified graphs, so it'll work when the
+    // simplification is going to be reused.
+    if (!refreshAllSizeHints(orientation)) {
+        qWarning("QGraphicsAnchorLayout: anchor setup is not feasible.");
+        graphHasConflicts[orientation] = true;
+        return;
+    }
 
-    // Reset the nominal sizes of each anchor based on the current item sizes
-    setAnchorSizeHintsFromItems(orientation);
+    // Simplify the graph
+    if (!simplifyGraph(orientation)) {
+        qWarning("QGraphicsAnchorLayout: anchor setup is not feasible.");
+        graphHasConflicts[orientation] = true;
+        return;
+    }
 
     // Traverse all graph edges and store the possible paths to each vertex
     findPaths(orientation);
@@ -1878,12 +1906,16 @@ bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList<QSimplexConstra
 }
 
 /*!
-  \internal
+    \internal
 
-  For graph edges ("anchors") that represent items, this method updates their
-  intrinsic size restrictions, based on the item size hints.
+    Traverse the graph refreshing the size hints. Complex anchors will call the
+    refresh method of their children anchors. Simple anchors, if are internal
+    anchors, will query the associated item for their size hints.
+
+    Returns false if some unfeasibility was found in the graph regarding the
+    complex anchors.
 */
-void QGraphicsAnchorLayoutPrivate::setAnchorSizeHintsFromItems(Orientation orientation)
+bool QGraphicsAnchorLayoutPrivate::refreshAllSizeHints(Orientation orientation)
 {
     Graph<AnchorVertex, AnchorData> &g = graph[orientation];
     QList<QPair<AnchorVertex *, AnchorVertex *> > vertices = g.connections();
@@ -1893,8 +1925,13 @@ void QGraphicsAnchorLayoutPrivate::setAnchorSizeHintsFromItems(Orientation orien
     for (int i = 0; i < vertices.count(); ++i) {
         AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);;
         Q_ASSERT(data->from && data->to);
-        data->refreshSizeHints(spacing);
+
+        // During the traversal we check the feasibility of the complex anchors.
+        if (!data->refreshSizeHints(spacing))
+            return false;
     }
+
+    return true;
 }
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
index d4eb2d4..a3de6f6 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
@@ -428,8 +428,8 @@ public:
     qreal effectiveSpacing(Orientation orientation) const;
 
     // Activation methods
-    void simplifyGraph(Orientation orientation);
-    bool simplifyGraphIteration(Orientation orientation);
+    bool simplifyGraph(Orientation orientation);
+    bool simplifyGraphIteration(Orientation orientation, bool *feasible);
     void restoreSimplifiedGraph(Orientation orientation);
 
     void calculateGraphs();
@@ -441,7 +441,7 @@ public:
     bool calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
                            const QList<AnchorData *> &variables);
 
-    void setAnchorSizeHintsFromItems(Orientation orientation);
+    bool refreshAllSizeHints(Orientation orientation);
     void findPaths(Orientation orientation);
     void constraintsFromPaths(Orientation orientation);
     void updateAnchorSizes(Orientation orientation);
diff --git a/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp b/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp
index 7b87969..facc1ef 100644
--- a/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp
+++ b/tests/auto/qgraphicsanchorlayout/tst_qgraphicsanchorlayout.cpp
@@ -82,6 +82,7 @@ private slots:
     void expandingParallel();
     void floatConflict();
     void infiniteMaxSizes();
+    void simplifiableUnfeasible();
 };
 
 class RectWidget : public QGraphicsWidget
@@ -1755,5 +1756,55 @@ void tst_QGraphicsAnchorLayout::infiniteMaxSizes()
     QCOMPARE(d->geometry(), QRectF(QWIDGETSIZE_MAX - 50, 0, 50, 10));
 }
 
+void tst_QGraphicsAnchorLayout::simplifiableUnfeasible()
+{
+    QGraphicsWidget *a = createItem(QSizeF(70.0, 100.0),
+                                    QSizeF(100.0, 100.0),
+                                    QSizeF(100.0, 100.0), "A");
+
+    QGraphicsWidget *b = createItem(QSizeF(110.0, 100.0),
+                                    QSizeF(150.0, 100.0),
+                                    QSizeF(190.0, 100.0), "B");
+
+    QGraphicsAnchorLayout *l = new QGraphicsAnchorLayout;
+    l->setContentsMargins(0, 0, 0, 0);
+    l->setSpacing(0);
+
+    l->addAnchor(l, Qt::AnchorTop, a, Qt::AnchorTop);
+    l->addAnchor(a, Qt::AnchorBottom, b, Qt::AnchorTop);
+    l->addAnchor(b, Qt::AnchorBottom, l, Qt::AnchorBottom);
+
+    l->addAnchors(l, a, Qt::Horizontal);
+    l->addAnchor(l, Qt::AnchorLeft, b, Qt::AnchorLeft);
+    l->addAnchor(b, Qt::AnchorRight, a, Qt::AnchorRight);
+
+    QCOMPARE(l->count(), 2);
+
+    QGraphicsWidget p;
+    p.setLayout(l);
+
+    l->invalidate();
+    QVERIFY(layoutHasConflict(l));
+    if (hasSimplification)
+        QVERIFY(!usedSimplex(l, Qt::Horizontal));
+
+    // Now we make it valid again
+    b->setMinimumWidth(100);
+
+    l->invalidate();
+    QVERIFY(!layoutHasConflict(l));
+    if (hasSimplification)
+        QVERIFY(!usedSimplex(l, Qt::Horizontal));
+
+    // And make it invalid again
+    a->setPreferredWidth(70);
+    a->setMaximumWidth(70);
+
+    l->invalidate();
+    QVERIFY(layoutHasConflict(l));
+    if (hasSimplification)
+        QVERIFY(!usedSimplex(l, Qt::Horizontal));
+}
+
 QTEST_MAIN(tst_QGraphicsAnchorLayout)
 #include "tst_qgraphicsanchorlayout.moc"