src/third_party/WebKit/Source/core/rendering/FastTextAutosizer.h

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #ifndef FastTextAutosizer_h
  32 #define FastTextAutosizer_h
  33
  34 #include "core/rendering/RenderObject.h"
  35 #include "core/rendering/RenderTable.h"
  36 #include "wtf/HashMap.h"
  37 #include "wtf/HashSet.h"
  38 #include "wtf/Noncopyable.h"
  39 #include "wtf/OwnPtr.h"
  40 #include "wtf/PassOwnPtr.h"
  41
  42 namespace WebCore {
  43
  44 class Document;
  45 class RenderBlock;
  46 class RenderListItem;
  47 class RenderListMarker;
  48
  49 // Single-pass text autosizer (work in progress). Works in two stages:
  50 // (1) record information about page elements during style recalc
  51 // (2) inflate sizes during layout
  52 // See: http://tinyurl.com/chromium-fast-autosizer
  53
  54 class FastTextAutosizer FINAL {
  55     WTF_MAKE_NONCOPYABLE(FastTextAutosizer);
  56
  57 public:
  58     static PassOwnPtr<FastTextAutosizer> create(const Document* document)
  59     {
  60         return adoptPtr(new FastTextAutosizer(document));
  61     }
  62
  63     void updatePageInfoInAllFrames();
  64     void updatePageInfo();
  65     void record(const RenderBlock*);
  66     void destroy(const RenderBlock*);
  67     void inflateListItem(RenderListItem*, RenderListMarker*);
  68
  69     class LayoutScope {
  70     public:
  71         explicit LayoutScope(RenderBlock*);
  72         ~LayoutScope();
  73     private:
  74         FastTextAutosizer* m_textAutosizer;
  75         RenderBlock* m_block;
  76     };
  77
  78     class DeferUpdatePageInfo {
  79     public:
  80         explicit DeferUpdatePageInfo(Page*);
  81         ~DeferUpdatePageInfo();
  82     private:
  83         RefPtr<LocalFrame> m_mainFrame;
  84     };
  85
  86 private:
  87     typedef HashSet<const RenderBlock*> BlockSet;
  88
  89     enum HasEnoughTextToAutosize {
  90         UnknownAmountOfText,
  91         HasEnoughText,
  92         NotEnoughText
  93     };
  94
  95     enum RelayoutBehavior {
  96         AlreadyInLayout, // The default; appropriate if we are already in layout.
  97         LayoutNeeded // Use this if changing a multiplier outside of layout.
  98     };
  99
 100     enum BeginLayoutBehavior {
 101         StopLayout,
 102         ContinueLayout
 103     };
 104
 105     enum BlockFlag {
 106         // A block that is evaluated for becoming a cluster root.
 107         POTENTIAL_ROOT = 1 << 0,
 108         // A cluster root that establishes an independent multiplier.
 109         INDEPENDENT = 1 << 1,
 110         // A cluster root with an explicit width. These are likely to be independent.
 111         EXPLICIT_WIDTH = 1 << 2,
 112         // A cluster that is wider or narrower than its parent. These also create an
 113         // independent multiplier, but this state cannot be determined until layout.
 114         WIDER_OR_NARROWER = 1 << 3,
 115         // A cluster that suppresses autosizing.
 116         SUPPRESSING = 1 << 4
 117     };
 118
 119     typedef unsigned BlockFlags;
 120
 121     // A supercluster represents autosizing information about a set of two or
 122     // more blocks that all have the same fingerprint. Clusters whose roots
 123     // belong to a supercluster will share a common multiplier and
 124     // text-length-based autosizing status.
 125     struct Supercluster {
 126         explicit Supercluster(const BlockSet* roots)
 127             : m_roots(roots)
 128             , m_hasEnoughTextToAutosize(UnknownAmountOfText)
 129             , m_multiplier(0)
 130         {
 131         }
 132
 133         const BlockSet* const m_roots;
 134         HasEnoughTextToAutosize m_hasEnoughTextToAutosize;
 135         float m_multiplier;
 136     };
 137
 138     struct Cluster {
 139         explicit Cluster(const RenderBlock* root, BlockFlags flags, Cluster* parent, Supercluster* supercluster = 0)
 140             : m_root(root)
 141             , m_flags(flags)
 142             , m_deepestBlockContainingAllText(0)
 143             , m_parent(parent)
 144             , m_multiplier(0)
 145             , m_hasEnoughTextToAutosize(UnknownAmountOfText)
 146             , m_supercluster(supercluster)
 147             , m_hasTableAncestor(root->isTableCell() || (m_parent && m_parent->m_hasTableAncestor))
 148         {
 149         }
 150
 151         const RenderBlock* const m_root;
 152         BlockFlags m_flags;
 153         // The deepest block containing all text is computed lazily (see:
 154         // deepestBlockContainingAllText). A value of 0 indicates the value has not been computed yet.
 155         const RenderBlock* m_deepestBlockContainingAllText;
 156         Cluster* m_parent;
 157         // The multiplier is computed lazily (see: clusterMultiplier) because it must be calculated
 158         // after the lowest block containing all text has entered layout (the
 159         // m_blocksThatHaveBegunLayout assertions cover this). Note: the multiplier is still
 160         // calculated when m_autosize is false because child clusters may depend on this multiplier.
 161         float m_multiplier;
 162         HasEnoughTextToAutosize m_hasEnoughTextToAutosize;
 163         // A set of blocks that are similar to this block.
 164         Supercluster* m_supercluster;
 165         bool m_hasTableAncestor;
 166     };
 167
 168     enum TextLeafSearch {
 169         First,
 170         Last
 171     };
 172
 173     struct FingerprintSourceData {
 174         FingerprintSourceData()
 175             : m_parentHash(0)
 176             , m_qualifiedNameHash(0)
 177             , m_packedStyleProperties(0)
 178             , m_column(0)
 179             , m_width(0)
 180         {
 181         }
 182
 183         unsigned m_parentHash;
 184         unsigned m_qualifiedNameHash;
 185         // Style specific selection of signals
 186         unsigned m_packedStyleProperties;
 187         unsigned m_column;
 188         float m_width;
 189     };
 190     // Ensures efficient hashing using StringHasher.
 191     COMPILE_ASSERT(!(sizeof(FingerprintSourceData) % sizeof(UChar)),
 192         Sizeof_FingerprintSourceData_must_be_multiple_of_UChar);
 193
 194     typedef unsigned Fingerprint;
 195     typedef HashMap<Fingerprint, OwnPtr<Supercluster> > SuperclusterMap;
 196     typedef Vector<OwnPtr<Cluster> > ClusterStack;
 197
 198     // Fingerprints are computed during style recalc, for (some subset of)
 199     // blocks that will become cluster roots.
 200     class FingerprintMapper {
 201     public:
 202         void add(const RenderObject*, Fingerprint);
 203         void addTentativeClusterRoot(const RenderBlock*, Fingerprint);
 204         // Returns true if any BlockSet was modified or freed by the removal.
 205         bool remove(const RenderObject*);
 206         Fingerprint get(const RenderObject*);
 207         BlockSet& getTentativeClusterRoots(Fingerprint);
 208     private:
 209         typedef HashMap<const RenderObject*, Fingerprint> FingerprintMap;
 210         typedef HashMap<Fingerprint, OwnPtr<BlockSet> > ReverseFingerprintMap;
 211
 212         FingerprintMap m_fingerprints;
 213         ReverseFingerprintMap m_blocksForFingerprint;
 214 #ifndef NDEBUG
 215         void assertMapsAreConsistent();
 216 #endif
 217     };
 218
 219     struct PageInfo {
 220         PageInfo()
 221             : m_frameWidth(0)
 222             , m_layoutWidth(0)
 223             , m_baseMultiplier(0)
 224             , m_pageNeedsAutosizing(false)
 225             , m_hasAutosized(false)
 226             , m_settingEnabled(false)
 227         {
 228         }
 229
 230         int m_frameWidth; // LocalFrame width in density-independent pixels (DIPs).
 231         int m_layoutWidth; // Layout width in CSS pixels.
 232         float m_baseMultiplier; // Includes accessibility font scale factor and device scale adjustment.
 233         bool m_pageNeedsAutosizing;
 234         bool m_hasAutosized;
 235         bool m_settingEnabled;
 236     };
 237
 238     explicit FastTextAutosizer(const Document*);
 239
 240     void beginLayout(RenderBlock*);
 241     void endLayout(RenderBlock*);
 242     void inflateTable(RenderTable*);
 243     void inflate(RenderBlock*);
 244     bool shouldHandleLayout() const;
 245     void setAllTextNeedsLayout();
 246     void resetMultipliers();
 247     BeginLayoutBehavior prepareForLayout(const RenderBlock*);
 248     void prepareClusterStack(const RenderObject*);
 249     bool clusterHasEnoughTextToAutosize(Cluster*, const RenderBlock* widthProvider = 0);
 250     bool superclusterHasEnoughTextToAutosize(Supercluster*, const RenderBlock* widthProvider = 0);
 251     bool clusterWouldHaveEnoughTextToAutosize(const RenderBlock* root, const RenderBlock* widthProvider = 0);
 252     Fingerprint getFingerprint(const RenderObject*);
 253     Fingerprint computeFingerprint(const RenderObject*);
 254     Cluster* maybeCreateCluster(const RenderBlock*);
 255     Supercluster* getSupercluster(const RenderBlock*);
 256     float clusterMultiplier(Cluster*);
 257     float superclusterMultiplier(Cluster*);
 258     // A cluster's width provider is typically the deepest block containing all text.
 259     // There are exceptions, such as tables and table cells which use the table itself for width.
 260     const RenderBlock* clusterWidthProvider(const RenderBlock*);
 261     const RenderBlock* maxClusterWidthProvider(const Supercluster*, const RenderBlock* currentRoot);
 262     // Typically this returns a block's computed width. In the case of tables layout, this
 263     // width is not yet known so the fixed width is used if it's available, or the containing
 264     // block's width otherwise.
 265     float widthFromBlock(const RenderBlock*);
 266     float multiplierFromBlock(const RenderBlock*);
 267     void applyMultiplier(RenderObject*, float, RelayoutBehavior = AlreadyInLayout);
 268     bool isWiderOrNarrowerDescendant(Cluster*);
 269     Cluster* currentCluster() const;
 270     const RenderBlock* deepestBlockContainingAllText(Cluster*);
 271     const RenderBlock* deepestBlockContainingAllText(const RenderBlock*);
 272     // Returns the first text leaf that is in the current cluster. We attempt to not include text
 273     // from descendant clusters but because descendant clusters may not exist, this is only an approximation.
 274     // The TraversalDirection controls whether we return the first or the last text leaf.
 275     const RenderObject* findTextLeaf(const RenderObject*, size_t&, TextLeafSearch);
 276     bool shouldDescendForTableInflation(RenderObject*);
 277     BlockFlags classifyBlock(const RenderObject*, BlockFlags mask = UINT_MAX);
 278 #ifdef AUTOSIZING_DOM_DEBUG_INFO
 279     void writeClusterDebugInfo(Cluster*);
 280 #endif
 281
 282     const Document* m_document;
 283     const RenderBlock* m_firstBlockToBeginLayout;
 284 #ifndef NDEBUG
 285     BlockSet m_blocksThatHaveBegunLayout; // Used to ensure we don't compute properties of a block before beginLayout() is called on it.
 286 #endif
 287
 288     // Clusters are created and destroyed during layout. The map key is the
 289     // cluster root. Clusters whose roots share the same fingerprint use the
 290     // same multiplier.
 291     SuperclusterMap m_superclusters;
 292     ClusterStack m_clusterStack;
 293     FingerprintMapper m_fingerprintMapper;
 294     Vector<RefPtr<RenderStyle> > m_stylesRetainedDuringLayout;
 295     // FIXME: All frames should share the same m_pageInfo instance.
 296     PageInfo m_pageInfo;
 297     bool m_updatePageInfoDeferred;
 298 };
 299
 300 } // namespace WebCore
 301
 302 #endif // FastTextAutosizer_h