Home | History | Annotate | Download | only in rendering 
      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     protected:
     74         FastTextAutosizer* m_textAutosizer;
     75         RenderBlock* m_block;
     76     };
     77 
     78     class TableLayoutScope : LayoutScope {
     79     public:
     80         explicit TableLayoutScope(RenderTable*);
     81     };
     82 
     83     class DeferUpdatePageInfo {
     84     public:
     85         explicit DeferUpdatePageInfo(Page*);
     86         ~DeferUpdatePageInfo();
     87     private:
     88         RefPtr<LocalFrame> m_mainFrame;
     89     };
     90 
     91 private:
     92     typedef HashSet<const RenderBlock*> BlockSet;
     93 
     94     enum HasEnoughTextToAutosize {
     95         UnknownAmountOfText,
     96         HasEnoughText,
     97         NotEnoughText
     98     };
     99 
    100     enum RelayoutBehavior {
    101         AlreadyInLayout, // The default; appropriate if we are already in layout.
    102         LayoutNeeded // Use this if changing a multiplier outside of layout.
    103     };
    104 
    105     enum BeginLayoutBehavior {
    106         StopLayout,
    107         ContinueLayout
    108     };
    109 
    110     enum InflateBehavior {
    111         ThisBlockOnly,
    112         DescendToInnerBlocks
    113     };
    114 
    115     enum BlockFlag {
    116         // A block that is evaluated for becoming a cluster root.
    117         POTENTIAL_ROOT = 1 << 0,
    118         // A cluster root that establishes an independent multiplier.
    119         INDEPENDENT = 1 << 1,
    120         // A cluster root with an explicit width. These are likely to be independent.
    121         EXPLICIT_WIDTH = 1 << 2,
    122         // A cluster that is wider or narrower than its parent. These also create an
    123         // independent multiplier, but this state cannot be determined until layout.
    124         WIDER_OR_NARROWER = 1 << 3,
    125         // A cluster that suppresses autosizing.
    126         SUPPRESSING = 1 << 4
    127     };
    128 
    129     typedef unsigned BlockFlags;
    130 
    131     // A supercluster represents autosizing information about a set of two or
    132     // more blocks that all have the same fingerprint. Clusters whose roots
    133     // belong to a supercluster will share a common multiplier and
    134     // text-length-based autosizing status.
    135     struct Supercluster {
    136         explicit Supercluster(const BlockSet* roots)
    137             : m_roots(roots)
    138             , m_hasEnoughTextToAutosize(UnknownAmountOfText)
    139             , m_multiplier(0)
    140         {
    141         }
    142 
    143         const BlockSet* const m_roots;
    144         HasEnoughTextToAutosize m_hasEnoughTextToAutosize;
    145         float m_multiplier;
    146     };
    147 
    148     struct Cluster {
    149         explicit Cluster(const RenderBlock* root, BlockFlags flags, Cluster* parent, Supercluster* supercluster = 0)
    150             : m_root(root)
    151             , m_flags(flags)
    152             , m_deepestBlockContainingAllText(0)
    153             , m_parent(parent)
    154             , m_multiplier(0)
    155             , m_hasEnoughTextToAutosize(UnknownAmountOfText)
    156             , m_supercluster(supercluster)
    157             , m_hasTableAncestor(root->isTableCell() || (m_parent && m_parent->m_hasTableAncestor))
    158         {
    159         }
    160 
    161         const RenderBlock* const m_root;
    162         BlockFlags m_flags;
    163         // The deepest block containing all text is computed lazily (see:
    164         // deepestBlockContainingAllText). A value of 0 indicates the value has not been computed yet.
    165         const RenderBlock* m_deepestBlockContainingAllText;
    166         Cluster* m_parent;
    167         // The multiplier is computed lazily (see: clusterMultiplier) because it must be calculated
    168         // after the lowest block containing all text has entered layout (the
    169         // m_blocksThatHaveBegunLayout assertions cover this). Note: the multiplier is still
    170         // calculated when m_autosize is false because child clusters may depend on this multiplier.
    171         float m_multiplier;
    172         HasEnoughTextToAutosize m_hasEnoughTextToAutosize;
    173         // A set of blocks that are similar to this block.
    174         Supercluster* m_supercluster;
    175         bool m_hasTableAncestor;
    176     };
    177 
    178     enum TextLeafSearch {
    179         First,
    180         Last
    181     };
    182 
    183     struct FingerprintSourceData {
    184         FingerprintSourceData()
    185             : m_parentHash(0)
    186             , m_qualifiedNameHash(0)
    187             , m_packedStyleProperties(0)
    188             , m_column(0)
    189             , m_width(0)
    190         {
    191         }
    192 
    193         unsigned m_parentHash;
    194         unsigned m_qualifiedNameHash;
    195         // Style specific selection of signals
    196         unsigned m_packedStyleProperties;
    197         unsigned m_column;
    198         float m_width;
    199     };
    200     // Ensures efficient hashing using StringHasher.
    201     COMPILE_ASSERT(!(sizeof(FingerprintSourceData) % sizeof(UChar)),
    202         Sizeof_FingerprintSourceData_must_be_multiple_of_UChar);
    203 
    204     typedef unsigned Fingerprint;
    205     typedef HashMap<Fingerprint, OwnPtr<Supercluster> > SuperclusterMap;
    206     typedef Vector<OwnPtr<Cluster> > ClusterStack;
    207 
    208     // Fingerprints are computed during style recalc, for (some subset of)
    209     // blocks that will become cluster roots.
    210     class FingerprintMapper {
    211     public:
    212         void add(const RenderObject*, Fingerprint);
    213         void addTentativeClusterRoot(const RenderBlock*, Fingerprint);
    214         // Returns true if any BlockSet was modified or freed by the removal.
    215         bool remove(const RenderObject*);
    216         Fingerprint get(const RenderObject*);
    217         BlockSet& getTentativeClusterRoots(Fingerprint);
    218     private:
    219         typedef HashMap<const RenderObject*, Fingerprint> FingerprintMap;
    220         typedef HashMap<Fingerprint, OwnPtr<BlockSet> > ReverseFingerprintMap;
    221 
    222         FingerprintMap m_fingerprints;
    223         ReverseFingerprintMap m_blocksForFingerprint;
    224 #ifndef NDEBUG
    225         void assertMapsAreConsistent();
    226 #endif
    227     };
    228 
    229     struct PageInfo {
    230         PageInfo()
    231             : m_frameWidth(0)
    232             , m_layoutWidth(0)
    233             , m_baseMultiplier(0)
    234             , m_pageNeedsAutosizing(false)
    235             , m_hasAutosized(false)
    236             , m_settingEnabled(false)
    237         {
    238         }
    239 
    240         int m_frameWidth; // LocalFrame width in density-independent pixels (DIPs).
    241         int m_layoutWidth; // Layout width in CSS pixels.
    242         float m_baseMultiplier; // Includes accessibility font scale factor and device scale adjustment.
    243         bool m_pageNeedsAutosizing;
    244         bool m_hasAutosized;
    245         bool m_settingEnabled;
    246     };
    247 
    248     explicit FastTextAutosizer(const Document*);
    249 
    250     void beginLayout(RenderBlock*);
    251     void endLayout(RenderBlock*);
    252     void inflateAutoTable(RenderTable*);
    253     float inflate(RenderObject*, InflateBehavior = ThisBlockOnly, float multiplier = 0);
    254     bool shouldHandleLayout() const;
    255     void setAllTextNeedsLayout();
    256     void resetMultipliers();
    257     BeginLayoutBehavior prepareForLayout(const RenderBlock*);
    258     void prepareClusterStack(const RenderObject*);
    259     bool clusterHasEnoughTextToAutosize(Cluster*, const RenderBlock* widthProvider = 0);
    260     bool superclusterHasEnoughTextToAutosize(Supercluster*, const RenderBlock* widthProvider = 0);
    261     bool clusterWouldHaveEnoughTextToAutosize(const RenderBlock* root, const RenderBlock* widthProvider = 0);
    262     Fingerprint getFingerprint(const RenderObject*);
    263     Fingerprint computeFingerprint(const RenderObject*);
    264     Cluster* maybeCreateCluster(const RenderBlock*);
    265     Supercluster* getSupercluster(const RenderBlock*);
    266     float clusterMultiplier(Cluster*);
    267     float superclusterMultiplier(Cluster*);
    268     // A cluster's width provider is typically the deepest block containing all text.
    269     // There are exceptions, such as tables and table cells which use the table itself for width.
    270     const RenderBlock* clusterWidthProvider(const RenderBlock*);
    271     const RenderBlock* maxClusterWidthProvider(const Supercluster*, const RenderBlock* currentRoot);
    272     // Typically this returns a block's computed width. In the case of tables layout, this
    273     // width is not yet known so the fixed width is used if it's available, or the containing
    274     // block's width otherwise.
    275     float widthFromBlock(const RenderBlock*);
    276     float multiplierFromBlock(const RenderBlock*);
    277     void applyMultiplier(RenderObject*, float, RelayoutBehavior = AlreadyInLayout);
    278     bool isWiderOrNarrowerDescendant(Cluster*);
    279     Cluster* currentCluster() const;
    280     const RenderBlock* deepestBlockContainingAllText(Cluster*);
    281     const RenderBlock* deepestBlockContainingAllText(const RenderBlock*);
    282     // Returns the first text leaf that is in the current cluster. We attempt to not include text
    283     // from descendant clusters but because descendant clusters may not exist, this is only an approximation.
    284     // The TraversalDirection controls whether we return the first or the last text leaf.
    285     const RenderObject* findTextLeaf(const RenderObject*, size_t&, TextLeafSearch);
    286     BlockFlags classifyBlock(const RenderObject*, BlockFlags mask = UINT_MAX);
    287 #ifdef AUTOSIZING_DOM_DEBUG_INFO
    288     void writeClusterDebugInfo(Cluster*);
    289 #endif
    290 
    291     const Document* m_document;
    292     const RenderBlock* m_firstBlockToBeginLayout;
    293 #ifndef NDEBUG
    294     BlockSet m_blocksThatHaveBegunLayout; // Used to ensure we don't compute properties of a block before beginLayout() is called on it.
    295 #endif
    296 
    297     // Clusters are created and destroyed during layout. The map key is the
    298     // cluster root. Clusters whose roots share the same fingerprint use the
    299     // same multiplier.
    300     SuperclusterMap m_superclusters;
    301     ClusterStack m_clusterStack;
    302     FingerprintMapper m_fingerprintMapper;
    303     Vector<RefPtr<RenderStyle> > m_stylesRetainedDuringLayout;
    304     // FIXME: All frames should share the same m_pageInfo instance.
    305     PageInfo m_pageInfo;
    306     bool m_updatePageInfoDeferred;
    307 };
    308 
    309 } // namespace WebCore
    310 
    311 #endif // FastTextAutosizer_h
    312