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