Move min left/right bearing calculations to QFontEngine baseclass

The logic used in the FreeType font engine can be generalized
and move to the QFontEngine baseclass. This allows the CoreText
font engine to correctly report the minimum left/right bearings,
which decreases the chance that an optimization in QTextLayout's
line breaking algorithm will produce wrong results.

The calculation of left and right bearing has been moved to the
glyph_metrics_t type to reduce code duplication. This allows us
to use the with and height of the bounding box to determine if
the glyph has any contours.

Change-Id: I864697d3f31ed56f22f04666199b6c5023c5e585
Reviewed-by: Eskil Abrahamsen Blomfeldt <eskil.abrahamsen-blomfeldt@theqtcompany.com>

9 files changed, 92 insertions, 77 deletions

diff --git a/src/gui/text/qfontengine.cpp b/src/gui/text/qfontengine.cpp
index 2087bad9f6..102946b545 100644
--- a/src/gui/text/qfontengine.cpp
+++ b/src/gui/text/qfontengine.cpp
@@ -54,6 +54,7 @@
 #include <private/qharfbuzz_p.h>
 
 #include <algorithm>
+#include <limits.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -235,10 +236,14 @@ Q_AUTOTEST_EXPORT QList<QFontEngine *> QFontEngine_stopCollectingEngines()
 
 // QFontEngine
 
+#define kBearingNotInitialized std::numeric_limits<qreal>::max()
+
 QFontEngine::QFontEngine(Type type)
     : m_type(type), ref(0),
       font_(0), font_destroy_func(0),
-      face_(0), face_destroy_func(0)
+      face_(0), face_destroy_func(0),
+      m_minLeftBearing(kBearingNotInitialized),
+      m_minRightBearing(kBearingNotInitialized)
 {
     faceData.user_data = this;
     faceData.get_font_table = qt_get_font_table_default;
@@ -562,11 +567,55 @@ void QFontEngine::getGlyphPositions(const QGlyphLayout &glyphs, const QTransform
 void QFontEngine::getGlyphBearings(glyph_t glyph, qreal *leftBearing, qreal *rightBearing)
 {
     glyph_metrics_t gi = boundingBox(glyph);
-    bool isValid = gi.isValid();
     if (leftBearing != 0)
-        *leftBearing = isValid ? gi.x.toReal() : 0.0;
+        *leftBearing = gi.leftBearing().toReal();
     if (rightBearing != 0)
-        *rightBearing = isValid ? (gi.xoff - gi.x - gi.width).toReal() : 0.0;
+        *rightBearing = gi.rightBearing().toReal();
+}
+
+qreal QFontEngine::minLeftBearing() const
+{
+    if (m_minLeftBearing == kBearingNotInitialized)
+        minRightBearing(); // Initializes both (see below)
+
+    return m_minLeftBearing;
+}
+
+qreal QFontEngine::minRightBearing() const
+{
+    if (m_minRightBearing == kBearingNotInitialized) {
+
+        // To balance performance and correctness we only look at a subset of the
+        // possible glyphs in the font, based on which characters are more likely
+        // to have a left or right bearing.
+        static const ushort characterSubset[] = {
+            '(', 'C', 'F', 'K', 'V', 'X', 'Y', ']', '_', 'f', 'r', '|',
+            127, 205, 645, 884, 922, 1070, 12386
+        };
+
+        // The font may have minimum bearings larger than 0, so we have to start at the max
+        m_minLeftBearing = m_minRightBearing = std::numeric_limits<qreal>::max();
+
+        for (uint i = 0; i < (sizeof(characterSubset) / sizeof(ushort)); ++i) {
+            const glyph_t glyph = glyphIndex(characterSubset[i]);
+            if (!glyph)
+                continue;
+
+            glyph_metrics_t glyphMetrics = const_cast<QFontEngine *>(this)->boundingBox(glyph);
+
+            // Glyphs with no contours shouldn't contribute to bearings
+            if (!glyphMetrics.width || !glyphMetrics.height)
+                continue;
+
+            m_minLeftBearing = qMin(m_minLeftBearing, glyphMetrics.leftBearing().toReal());
+            m_minRightBearing = qMin(m_minRightBearing, glyphMetrics.rightBearing().toReal());
+        }
+
+        if (m_minLeftBearing == kBearingNotInitialized || m_minRightBearing == kBearingNotInitialized)
+            qWarning() << "Failed to compute left/right minimum bearings for" << fontDef.family;
+    }
+
+    return m_minRightBearing;
 }
 
 glyph_metrics_t QFontEngine::tightBoundingBox(const QGlyphLayout &glyphs)
@@ -1469,8 +1518,7 @@ QFixed QFontEngine::lastRightBearing(const QGlyphLayout &glyphs, bool round)
         glyph_t glyph = glyphs.glyphs[glyphs.numGlyphs - 1];
         glyph_metrics_t gi = boundingBox(glyph);
         if (gi.isValid())
-            return round ? QFixed(qRound(gi.xoff - gi.x - gi.width))
-                         : QFixed(gi.xoff - gi.x - gi.width);
+            return round ? qRound(gi.rightBearing()) : gi.rightBearing();
     }
     return 0;
 }
diff --git a/src/gui/text/qfontengine_ft.cpp b/src/gui/text/qfontengine_ft.cpp
index 246df127ad..0d28785aa1 100644
--- a/src/gui/text/qfontengine_ft.cpp
+++ b/src/gui/text/qfontengine_ft.cpp
@@ -688,7 +688,6 @@ bool QFontEngineFT::init(FaceId faceId, bool antialias, GlyphFormat format,
         symbol = bool(fontDef.family.contains(QLatin1String("symbol"), Qt::CaseInsensitive));
     }
 
-    lbearing = rbearing = SHRT_MIN;
     freetype->computeSize(fontDef, &xsize, &ysize, &defaultGlyphSet.outline_drawing);
 
     FT_Face face = lockFace();
@@ -1258,54 +1257,6 @@ qreal QFontEngineFT::maxCharWidth() const
     return metrics.max_advance >> 6;
 }
 
-static const ushort char_table[] = {
-        40,
-        67,
-        70,
-        75,
-        86,
-        88,
-        89,
-        91,
-        95,
-        102,
-        114,
-        124,
-        127,
-        205,
-        645,
-        884,
-        922,
-        1070,
-        12386
-};
-
-static const int char_table_entries = sizeof(char_table)/sizeof(ushort);
-
-
-qreal QFontEngineFT::minLeftBearing() const
-{
-    if (lbearing == SHRT_MIN)
-        (void) minRightBearing(); // calculates both
-    return lbearing.toReal();
-}
-
-qreal QFontEngineFT::minRightBearing() const
-{
-    if (rbearing == SHRT_MIN) {
-        lbearing = rbearing = 0;
-        for (int i = 0; i < char_table_entries; ++i) {
-            const glyph_t glyph = glyphIndex(char_table[i]);
-            if (glyph != 0) {
-                glyph_metrics_t gi = const_cast<QFontEngineFT *>(this)->boundingBox(glyph);
-                lbearing = qMin(lbearing, gi.x);
-                rbearing = qMin(rbearing, (gi.xoff - gi.x - gi.width));
-            }
-        }
-    }
-    return rbearing.toReal();
-}
-
 QFixed QFontEngineFT::lineThickness() const
 {
     return line_thickness;
diff --git a/src/gui/text/qfontengine_ft_p.h b/src/gui/text/qfontengine_ft_p.h
index b81e51bf2e..83f9a4ef3d 100644
--- a/src/gui/text/qfontengine_ft_p.h
+++ b/src/gui/text/qfontengine_ft_p.h
@@ -208,8 +208,6 @@ private:
     virtual QFixed averageCharWidth() const Q_DECL_OVERRIDE;
 
     virtual qreal maxCharWidth() const Q_DECL_OVERRIDE;
-    virtual qreal minLeftBearing() const Q_DECL_OVERRIDE;
-    virtual qreal minRightBearing() const Q_DECL_OVERRIDE;
     virtual QFixed lineThickness() const Q_DECL_OVERRIDE;
     virtual QFixed underlinePosition() const Q_DECL_OVERRIDE;
 
@@ -324,8 +322,6 @@ private:
     int xsize;
     int ysize;
 
-    mutable QFixed lbearing;
-    mutable QFixed rbearing;
     QFixed line_thickness;
     QFixed underline_position;
 
diff --git a/src/gui/text/qfontengine_p.h b/src/gui/text/qfontengine_p.h
index 780104bc37..5282a4033e 100644
--- a/src/gui/text/qfontengine_p.h
+++ b/src/gui/text/qfontengine_p.h
@@ -214,8 +214,8 @@ public:
     virtual QFixed underlinePosition() const;
 
     virtual qreal maxCharWidth() const = 0;
-    virtual qreal minLeftBearing() const { return qreal(); }
-    virtual qreal minRightBearing() const { return qreal(); }
+    virtual qreal minLeftBearing() const;
+    virtual qreal minRightBearing() const;
 
     virtual void getGlyphBearings(glyph_t glyph, qreal *leftBearing = 0, qreal *rightBearing = 0);
 
@@ -323,6 +323,10 @@ private:
 
 private:
     QVariant m_userData;
+
+    mutable qreal m_minLeftBearing;
+    mutable qreal m_minRightBearing;
+
 };
 
 Q_DECLARE_OPERATORS_FOR_FLAGS(QFontEngine::ShaperFlags)
diff --git a/src/gui/text/qtextengine_p.h b/src/gui/text/qtextengine_p.h
index d2b39f274c..160daa0cfd 100644
--- a/src/gui/text/qtextengine_p.h
+++ b/src/gui/text/qtextengine_p.h
@@ -107,6 +107,22 @@ struct Q_GUI_EXPORT glyph_metrics_t
 
     glyph_metrics_t transformed(const QTransform &xform) const;
     inline bool isValid() const {return x != 100000 && y != 100000;}
+
+    inline QFixed leftBearing() const
+    {
+        if (!isValid())
+            return QFixed();
+
+        return x;
+    }
+
+    inline QFixed rightBearing() const
+    {
+        if (!isValid())
+            return QFixed();
+
+        return xoff - x - width;
+    }
 };
 Q_DECLARE_TYPEINFO(glyph_metrics_t, Q_PRIMITIVE_TYPE);
 
diff --git a/src/gui/text/qtextlayout.cpp b/src/gui/text/qtextlayout.cpp
index 0c729c74d1..d68a59fae3 100644
--- a/src/gui/text/qtextlayout.cpp
+++ b/src/gui/text/qtextlayout.cpp
@@ -1966,9 +1966,16 @@ void QTextLine::layout_helper(int maxGlyphs)
                 // end up breaking due to the current glyph being too wide.
                 QFixed previousRightBearing = lbh.rightBearing;
 
-                // We ignore the right bearing if the minimum negative bearing is too little to
-                // expand the text beyond the edge.
-                if (lbh.calculateNewWidth(line) - lbh.minimumRightBearing > line.width)
+                // We skip calculating the right bearing if the minimum negative bearing is too
+                // small to possibly expand the text beyond the edge. Note that this optimization
+                // will in some cases fail, as the minimum right bearing reported by the font
+                // engine may not cover all the glyphs in the font. The result is that we think
+                // we don't need to break at the current glyph (because the right bearing is 0),
+                // and when we then end up breaking on the next glyph we compute the right bearing
+                // and end up with a line width that is slightly larger width than what was requested.
+                // Unfortunately we can't remove this optimization as it will slow down text
+                // layouting significantly, so we accept the slight correctnes issue.
+                if ((lbh.calculateNewWidth(line) + qAbs(lbh.minimumRightBearing)) > line.width)
                     lbh.calculateRightBearing();
 
                 if (lbh.checkFullOtherwiseExtend(line)) {
diff --git a/src/platformsupport/fontdatabases/mac/qfontengine_coretext.mm b/src/platformsupport/fontdatabases/mac/qfontengine_coretext.mm
index 7e1dfd9275..732aead62a 100644
--- a/src/platformsupport/fontdatabases/mac/qfontengine_coretext.mm
+++ b/src/platformsupport/fontdatabases/mac/qfontengine_coretext.mm
@@ -361,16 +361,6 @@ qreal QCoreTextFontEngine::maxCharWidth() const
     return bb.xoff.toReal();
 }
 
-qreal QCoreTextFontEngine::minLeftBearing() const
-{
-    return 0;
-}
-
-qreal QCoreTextFontEngine::minRightBearing() const
-{
-    return 0;
-}
-
 void QCoreTextFontEngine::draw(CGContextRef ctx, qreal x, qreal y, const QTextItemInt &ti, int paintDeviceHeight)
 {
     QVarLengthArray<QFixedPoint> positions;
diff --git a/src/platformsupport/fontdatabases/mac/qfontengine_coretext_p.h b/src/platformsupport/fontdatabases/mac/qfontengine_coretext_p.h
index f8ec1d326f..1c33ae7d84 100644
--- a/src/platformsupport/fontdatabases/mac/qfontengine_coretext_p.h
+++ b/src/platformsupport/fontdatabases/mac/qfontengine_coretext_p.h
@@ -96,8 +96,6 @@ public:
     QImage alphaRGBMapForGlyph(glyph_t, QFixed subPixelPosition, const QTransform &t) Q_DECL_OVERRIDE;
     glyph_metrics_t alphaMapBoundingBox(glyph_t glyph, QFixed, const QTransform &matrix, GlyphFormat) Q_DECL_OVERRIDE;
     QImage bitmapForGlyph(glyph_t, QFixed subPixelPosition, const QTransform &t) Q_DECL_OVERRIDE;
-    qreal minRightBearing() const Q_DECL_OVERRIDE;
-    qreal minLeftBearing() const Q_DECL_OVERRIDE;
     QFixed emSquareSize() const Q_DECL_OVERRIDE;
 
     bool supportsTransformation(const QTransform &transform) const Q_DECL_OVERRIDE;
diff --git a/tests/auto/gui/text/qtextlayout/tst_qtextlayout.cpp b/tests/auto/gui/text/qtextlayout/tst_qtextlayout.cpp
index 18da61925d..de0c2d6dbe 100644
--- a/tests/auto/gui/text/qtextlayout/tst_qtextlayout.cpp
+++ b/tests/auto/gui/text/qtextlayout/tst_qtextlayout.cpp
@@ -1985,7 +1985,12 @@ void tst_QTextLayout::textWidthVsWIdth()
                        "./libs -I/home/ettrich/dev/creator/tools -I../../plugins -I../../shared/scriptwrapper -I../../libs/3rdparty/botan/build -Idialogs -Iactionmanager -Ieditorma"
                        "nager -Iprogressmanager -Iscriptmanager -I.moc/debug-shared -I.uic -o .obj/debug-shared/sidebar.o sidebar.cpp"));
 
-    // textWidth includes right bearing, but it should never be LARGER than width if there is space for at least one character
+    // The naturalTextWidth includes right bearing, but should never be LARGER than line width if
+    // there is space for at least one character. Unfortunately that assumption may not hold if the
+    // font engine fails to report an accurate minimum right bearing for the font, eg. when the
+    // minimum right bearing reported by the font engine doesn't cover all the glyphs in the font.
+    // The result is that this test may fail in some cases. We should fix this by running the test
+    // with a font that we know have no suprising right bearings. See qtextlayout.cpp for details.
     for (int width = 100; width < 1000; ++width) {
         layout.beginLayout();
         QTextLine line = layout.createLine();