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/TextAutosizer.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 #include "wtf/text/AtomicStringHash.h"
  42
  43 namespace WebCore {
  44
  45 class Document;
  46 class RenderBlock;
  47 class RenderListItem;
  48 class RenderListMarker;
  49
  50 // Single-pass text autosizer (work in progress). Works in two stages:
  51 // (1) record information about page elements during style recalc
  52 // (2) inflate sizes during layout
  53 // See: http://tinyurl.com/chromium-fast-autosizer
  54
  55 class FastTextAutosizer FINAL {
  56     WTF_MAKE_NONCOPYABLE(FastTextAutosizer);
  57
  58 public:
  59     static PassOwnPtr<FastTextAutosizer> create(const Document* document)
  60     {
  61         return adoptPtr(new FastTextAutosizer(document));
  62     }
  63
  64     void record(const RenderBlock*);
  65     void destroy(const RenderBlock*);
  66     void inflateListItem(RenderListItem*, RenderListMarker*);
  67
  68     class LayoutScope {
  69     public:
  70         explicit LayoutScope(Document& document, RenderBlock* block)
  71             : m_block(0)
  72         {
  73             m_textAutosizer = document.fastTextAutosizer();
  74             if (m_textAutosizer) {
  75                 if (!m_textAutosizer->enabled()) {
  76                     m_textAutosizer = 0;
  77                     return;
  78                 }
  79                 m_block = block;
  80                 m_textAutosizer->beginLayout(m_block);
  81             }
  82         }
  83
  84         ~LayoutScope()
  85         {
  86             if (m_textAutosizer)
  87                 m_textAutosizer->endLayout(m_block);
  88         }
  89     private:
  90         FastTextAutosizer* m_textAutosizer;
  91         RenderBlock* m_block;
  92     };
  93
  94 private:
  95     typedef HashSet<const RenderBlock*> BlockSet;
  96
  97     // A supercluster represents autosizing information about a set of two or
  98     // more blocks that all have the same fingerprint. Clusters whose roots
  99     // belong to a supercluster will share a common multiplier and
 100     // text-length-based autosizing status.
 101     struct Supercluster {
 102         explicit Supercluster(const BlockSet* roots)
 103             : m_roots(roots)
 104             , m_multiplier(0)
 105             , m_anyClusterHasEnoughText(false)
 106         {
 107         }
 108
 109         const BlockSet* const m_roots;
 110         float m_multiplier;
 111         bool m_anyClusterHasEnoughText;
 112     };
 113
 114     struct Cluster {
 115         explicit Cluster(const RenderBlock* root, bool autosize, Cluster* parent, Supercluster* supercluster = 0)
 116             : m_root(root)
 117             , m_deepestBlockContainingAllText(0)
 118             , m_parent(parent)
 119             , m_autosize(autosize)
 120             , m_multiplier(0)
 121             , m_textLength(-1)
 122             , m_supercluster(supercluster)
 123         {
 124         }
 125
 126         const RenderBlock* const m_root;
 127         // The deepest block containing all text is computed lazily (see:
 128         // deepestBlockContainingAllText). A value of 0 indicates the value has not been computed yet.
 129         const RenderBlock* m_deepestBlockContainingAllText;
 130         Cluster* m_parent;
 131         bool m_autosize;
 132         // The multiplier is computed lazily (see: clusterMultiplier) because it must be calculated
 133         // after the lowest block containing all text has entered layout (the
 134         // m_blocksThatHaveBegunLayout assertions cover this). Note: the multiplier is still
 135         // calculated when m_autosize is false because child clusters may depend on this multiplier.
 136         float m_multiplier;
 137         // Text length is computed lazily (see: textLength). This is an approximation and characters
 138         // are assumed to be 1em wide. Negative values indicate the length has not been computed.
 139         int m_textLength;
 140         // A set of blocks that are similar to this block.
 141         Supercluster* m_supercluster;
 142     };
 143
 144     enum TextLeafSearch {
 145         First,
 146         Last
 147     };
 148
 149     typedef HashMap<AtomicString, OwnPtr<Supercluster> > SuperclusterMap;
 150     typedef Vector<OwnPtr<Cluster> > ClusterStack;
 151
 152     // Fingerprints are computed during style recalc, for (some subset of)
 153     // blocks that will become cluster roots.
 154     class FingerprintMapper {
 155     public:
 156         void add(const RenderBlock*, AtomicString);
 157         void remove(const RenderBlock*);
 158         AtomicString get(const RenderBlock*);
 159         BlockSet& getBlocks(AtomicString);
 160     private:
 161         typedef HashMap<const RenderBlock*, AtomicString> FingerprintMap;
 162         typedef HashMap<AtomicString, OwnPtr<BlockSet> > ReverseFingerprintMap;
 163
 164         FingerprintMap m_fingerprints;
 165         ReverseFingerprintMap m_blocksForFingerprint;
 166     };
 167
 168     explicit FastTextAutosizer(const Document*);
 169
 170     void beginLayout(RenderBlock*);
 171     void endLayout(RenderBlock*);
 172     void inflate(RenderBlock*);
 173     bool enabled();
 174     void prepareRenderViewInfo();
 175     bool isFingerprintingCandidate(const RenderBlock*);
 176     bool clusterHasEnoughTextToAutosize(Cluster*);
 177     bool clusterWouldHaveEnoughTextToAutosize(const RenderBlock*);
 178     float textLength(Cluster*);
 179     AtomicString computeFingerprint(const RenderBlock*);
 180     Cluster* maybeCreateCluster(const RenderBlock*);
 181     Supercluster* getSupercluster(const RenderBlock*);
 182     const RenderBlock* deepestCommonAncestor(BlockSet&);
 183     float clusterMultiplier(Cluster*);
 184     float superclusterMultiplier(Supercluster*);
 185     float multiplierFromBlock(const RenderBlock*);
 186     void applyMultiplier(RenderObject*, float);
 187     bool mightBeWiderOrNarrowerDescendant(const RenderBlock*);
 188     bool isWiderDescendant(Cluster*);
 189     bool isNarrowerDescendant(Cluster*);
 190     bool isLayoutRoot(const RenderBlock*) const;
 191
 192     Cluster* currentCluster() const;
 193
 194     RenderObject* nextChildSkippingChildrenOfBlocks(const RenderObject*, const RenderObject*);
 195
 196     const RenderBlock* deepestBlockContainingAllText(Cluster*);
 197     const RenderBlock* deepestBlockContainingAllText(const RenderBlock*);
 198     // Returns the first text leaf that is in the current cluster. We attempt to not include text
 199     // from descendant clusters but because descendant clusters may not exist, this is only an approximation.
 200     // The TraversalDirection controls whether we return the first or the last text leaf.
 201     const RenderObject* findTextLeaf(const RenderObject*, size_t&, TextLeafSearch);
 202
 203     const Document* m_document;
 204     int m_frameWidth; // Frame width in density-independent pixels (DIPs).
 205     int m_layoutWidth; // Layout width in CSS pixels.
 206     float m_baseMultiplier; // Includes accessibility font scale factor and device scale adjustment.
 207 #ifndef NDEBUG
 208     bool m_renderViewInfoPrepared;
 209     BlockSet m_blocksThatHaveBegunLayout; // Used to ensure we don't compute properties of a block before beginLayout() is called on it.
 210 #endif
 211
 212     // Clusters are created and destroyed during layout. The map key is the
 213     // cluster root. Clusters whose roots share the same fingerprint use the
 214     // same multiplier.
 215     SuperclusterMap m_superclusters;
 216     ClusterStack m_clusterStack;
 217     FingerprintMapper m_fingerprintMapper;
 218 };
 219
 220 } // namespace WebCore
 221
 222 #endif // FastTextAutosizer_h