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