b7f3718a65e94f9b7b88cc68e14e56dde4d2b648
[WebKit-https.git] / Source / WebCore / rendering / TextAutosizer.cpp
1 /*
2  * Copyright (C) 2012 Google Inc. All rights reserved.
3  * Copyright (C) 2012 Apple Inc. All rights reserved.
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB.  If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  */
20
21 #include "config.h"
22
23 #if ENABLE(TEXT_AUTOSIZING)
24
25 #include "TextAutosizer.h"
26
27 #include "Document.h"
28 #include "HTMLElement.h"
29 #include "InspectorInstrumentation.h"
30 #include "IntSize.h"
31 #include "RenderObject.h"
32 #include "RenderStyle.h"
33 #include "RenderText.h"
34 #include "RenderView.h"
35 #include "Settings.h"
36 #include "StyleInheritedData.h"
37
38 #include <algorithm>
39 #include <wtf/StdLibExtras.h>
40 #include <wtf/Vector.h>
41
42 namespace WebCore {
43
44 using namespace HTMLNames;
45
46 struct TextAutosizingWindowInfo {
47     IntSize windowSize;
48     IntSize minLayoutSize;
49 };
50
51 // Represents cluster related data. Instances should not persist between calls to processSubtree.
52 struct TextAutosizingClusterInfo {
53     explicit TextAutosizingClusterInfo(RenderBlock* root)
54         : root(root)
55         , blockContainingAllText(0)
56         , maxAllowedDifferenceFromTextWidth(150)
57     {
58     }
59
60     RenderBlock* root;
61     const RenderBlock* blockContainingAllText;
62
63     // Upper limit on the difference between the width of the cluster's block containing all
64     // text and that of a narrow child before the child becomes a separate cluster.
65     float maxAllowedDifferenceFromTextWidth;
66
67     // Descendants of the cluster that are narrower than the block containing all text and must be
68     // processed together.
69     Vector<TextAutosizingClusterInfo> narrowDescendants;
70 };
71
72
73 static const Vector<QualifiedName>& formInputTags()
74 {
75     // Returns the tags for the form input elements.
76     DEFINE_STATIC_LOCAL(Vector<QualifiedName>, formInputTags, ());
77     if (formInputTags.isEmpty()) {
78         formInputTags.append(inputTag);
79         formInputTags.append(buttonTag);
80         formInputTags.append(selectTag);
81     }
82     return formInputTags;
83 }
84
85 TextAutosizer::TextAutosizer(Document* document)
86     : m_document(document)
87 {
88 }
89
90 TextAutosizer::~TextAutosizer()
91 {
92 }
93
94 bool TextAutosizer::processSubtree(RenderObject* layoutRoot)
95 {
96     // FIXME: Text Autosizing should only be enabled when m_document->page()->mainFrame()->view()->useFixedLayout()
97     // is true, but for now it's useful to ignore this so that it can be tested on desktop.
98     if (!m_document->settings() || !m_document->settings()->textAutosizingEnabled() || layoutRoot->view()->printing() || !m_document->page())
99         return false;
100
101     Frame* mainFrame = m_document->page()->mainFrame();
102
103     TextAutosizingWindowInfo windowInfo;
104
105     // Window area, in logical (density-independent) pixels.
106     windowInfo.windowSize = m_document->settings()->textAutosizingWindowSizeOverride();
107     if (windowInfo.windowSize.isEmpty()) {
108         bool includeScrollbars = !InspectorInstrumentation::shouldApplyScreenWidthOverride(mainFrame);
109         windowInfo.windowSize = mainFrame->view()->unscaledVisibleContentSize(includeScrollbars);
110         if (!m_document->settings()->applyDeviceScaleFactorInCompositor())
111             windowInfo.windowSize.scale(1 / m_document->page()->deviceScaleFactor());
112     }
113
114     // Largest area of block that can be visible at once (assuming the main
115     // frame doesn't get scaled to less than overview scale), in CSS pixels.
116     windowInfo.minLayoutSize = mainFrame->view()->layoutSize();
117     for (Frame* frame = m_document->frame(); frame; frame = frame->tree()->parent()) {
118         if (!frame->view()->isInChildFrameWithFrameFlattening())
119             windowInfo.minLayoutSize = windowInfo.minLayoutSize.shrunkTo(frame->view()->layoutSize());
120     }
121
122     // The layoutRoot could be neither a container nor a cluster, so walk up the tree till we find each of these.
123     RenderBlock* container = layoutRoot->isRenderBlock() ? toRenderBlock(layoutRoot) : layoutRoot->containingBlock();
124     while (container && !isAutosizingContainer(container))
125         container = container->containingBlock();
126
127     RenderBlock* cluster = container;
128     while (cluster && (!isAutosizingContainer(cluster) || !isIndependentDescendant(cluster)))
129         cluster = cluster->containingBlock();
130
131     TextAutosizingClusterInfo clusterInfo(cluster);
132     processCluster(clusterInfo, container, layoutRoot, windowInfo);
133     return true;
134 }
135
136 void TextAutosizer::processCluster(TextAutosizingClusterInfo& clusterInfo, RenderBlock* container, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
137 {
138     // Many pages set a max-width on their content. So especially for the
139     // RenderView, instead of just taking the width of |cluster| we find
140     // the lowest common ancestor of the first and last descendant text node of
141     // the cluster (i.e. the deepest wrapper block that contains all the text),
142     // and use its width instead.
143     clusterInfo.blockContainingAllText = findDeepestBlockContainingAllText(clusterInfo.root);
144     float textWidth = clusterInfo.blockContainingAllText->contentLogicalWidth();
145
146     float multiplier = 1;
147     if (clusterShouldBeAutosized(clusterInfo, textWidth)) {
148         int logicalWindowWidth = clusterInfo.root->isHorizontalWritingMode() ? windowInfo.windowSize.width() : windowInfo.windowSize.height();
149         int logicalLayoutWidth = clusterInfo.root->isHorizontalWritingMode() ? windowInfo.minLayoutSize.width() : windowInfo.minLayoutSize.height();
150         // Ignore box width in excess of the layout width, to avoid extreme multipliers.
151         float logicalClusterWidth = std::min<float>(textWidth, logicalLayoutWidth);
152
153         multiplier = logicalClusterWidth / logicalWindowWidth;
154         multiplier *= m_document->settings()->textAutosizingFontScaleFactor();
155         multiplier = std::max(1.0f, multiplier);
156     }
157
158     processContainer(multiplier, container, clusterInfo, subtreeRoot, windowInfo);
159
160     Vector<TextAutosizingClusterInfo>& narrowDescendants = clusterInfo.narrowDescendants;
161     for (size_t i = 0; i < narrowDescendants.size(); ++i) {
162         TextAutosizingClusterInfo& descendantClusterInfo = narrowDescendants[i];
163         processCluster(descendantClusterInfo, descendantClusterInfo.root, descendantClusterInfo.root, windowInfo);
164     }
165 }
166
167 void TextAutosizer::processContainer(float multiplier, RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, RenderObject* subtreeRoot, const TextAutosizingWindowInfo& windowInfo)
168 {
169     ASSERT(isAutosizingContainer(container));
170
171     float localMultiplier = containerShouldBeAutosized(container) ? multiplier: 1;
172
173     RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(subtreeRoot, subtreeRoot);
174     while (descendant) {
175         if (descendant->isText()) {
176             if (localMultiplier != descendant->style()->textAutosizingMultiplier()) {
177                 setMultiplier(descendant, localMultiplier);
178                 setMultiplier(descendant->parent(), localMultiplier); // Parent does line spacing.
179             }
180             // FIXME: Increase list marker size proportionately.
181         } else if (isAutosizingContainer(descendant)) {
182             RenderBlock* descendantBlock = toRenderBlock(descendant);
183             TextAutosizingClusterInfo descendantClusterInfo(descendantBlock);
184             if (isWiderDescendant(descendantBlock, clusterInfo) || isIndependentDescendant(descendantBlock))
185                 processCluster(descendantClusterInfo, descendantBlock, descendantBlock, windowInfo);
186             else if (isNarrowDescendant(descendantBlock, clusterInfo)) {
187                 // Narrow descendants are processed together later to be able to apply the same multiplier
188                 // to each of them if necessary.
189                 clusterInfo.narrowDescendants.append(descendantClusterInfo);
190             } else
191                 processContainer(multiplier, descendantBlock, clusterInfo, descendantBlock, windowInfo);
192         }
193         descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, subtreeRoot);
194     }
195 }
196
197 void TextAutosizer::setMultiplier(RenderObject* renderer, float multiplier)
198 {
199     RefPtr<RenderStyle> newStyle = RenderStyle::clone(renderer->style());
200     newStyle->setTextAutosizingMultiplier(multiplier);
201     renderer->setStyle(newStyle.release());
202 }
203
204 float TextAutosizer::computeAutosizedFontSize(float specifiedSize, float multiplier)
205 {
206     // Somewhat arbitrary "pleasant" font size.
207     const float pleasantSize = 16;
208
209     // Multiply fonts that the page author has specified to be larger than
210     // pleasantSize by less and less, until huge fonts are not increased at all.
211     // For specifiedSize between 0 and pleasantSize we directly apply the
212     // multiplier; hence for specifiedSize == pleasantSize, computedSize will be
213     // multiplier * pleasantSize. For greater specifiedSizes we want to
214     // gradually fade out the multiplier, so for every 1px increase in
215     // specifiedSize beyond pleasantSize we will only increase computedSize
216     // by gradientAfterPleasantSize px until we meet the
217     // computedSize = specifiedSize line, after which we stay on that line (so
218     // then every 1px increase in specifiedSize increases computedSize by 1px).
219     const float gradientAfterPleasantSize = 0.5;
220
221     float computedSize;
222     if (specifiedSize <= pleasantSize)
223         computedSize = multiplier * specifiedSize;
224     else {
225         computedSize = multiplier * pleasantSize + gradientAfterPleasantSize * (specifiedSize - pleasantSize);
226         if (computedSize < specifiedSize)
227             computedSize = specifiedSize;
228     }
229     return computedSize;
230 }
231
232 bool TextAutosizer::isAutosizingContainer(const RenderObject* renderer)
233 {
234     // "Autosizing containers" are the smallest unit for which we can
235     // enable/disable Text Autosizing.
236     // - Must not be inline, as different multipliers on one line looks terrible.
237     //   Exceptions are inline-block and alike elements (inline-table, -webkit-inline-*),
238     //   as they often contain entire multi-line columns of text.
239     // - Must not be list items, as items in the same list should look consistent (*).
240     // - Must not be normal list items, as items in the same list should look
241     //   consistent, unless they are floating or position:absolute/fixed.
242     if (!renderer->isRenderBlock() || (renderer->isInline() && !renderer->style()->isDisplayReplacedType()))
243         return false;
244     if (renderer->isListItem())
245         return renderer->isFloating() || renderer->isOutOfFlowPositioned();
246     // Avoid creating containers for text within text controls, buttons, or <select> buttons.
247     Node* parentNode = renderer->parent() ? renderer->parent()->generatingNode() : 0;
248     if (parentNode && parentNode->isElementNode() && formInputTags().contains(toElement(parentNode)->tagQName()))
249         return false;
250
251     return true;
252 }
253
254 bool TextAutosizer::isNarrowDescendant(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
255 {
256     ASSERT(isAutosizingContainer(renderer));
257
258     // Autosizing containers that are significantly narrower than the |blockContainingAllText| of
259     // their enclosing cluster may be acting as separate columns, hence must be autosized
260     // separately. For example the 2nd div in:
261     // <body>
262     //     <div style="float: right; width: 50%"></div>
263     //     <div style="width: 50%"></div>
264     // <body>
265     // is the left column, and should be autosized differently from the body.
266     // If however the container is only narrower by 150px or less, it's considered part of
267     // the enclosing cluster. This 150px limit is adjusted whenever a descendant container is
268     // less than 50px narrower than the current limit.
269     const float differenceFromMaxWidthDifference = 50;
270     float contentWidth = renderer->contentLogicalWidth();
271     float clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
272     float widthDifference = clusterTextWidth - contentWidth;
273
274     if (widthDifference - parentClusterInfo.maxAllowedDifferenceFromTextWidth > differenceFromMaxWidthDifference)
275         return true;
276
277     parentClusterInfo.maxAllowedDifferenceFromTextWidth = std::max(widthDifference, parentClusterInfo.maxAllowedDifferenceFromTextWidth);
278     return false;
279 }
280
281 bool TextAutosizer::isWiderDescendant(const RenderBlock* renderer, const TextAutosizingClusterInfo& parentClusterInfo)
282 {
283     ASSERT(isAutosizingContainer(renderer));
284
285     // Autosizing containers that are wider than the |blockContainingAllText| of their enclosing
286     // cluster are treated the same way as autosizing clusters to be autosized separately.
287     float contentWidth = renderer->contentLogicalWidth();
288     float clusterTextWidth = parentClusterInfo.blockContainingAllText->contentLogicalWidth();
289     return contentWidth > clusterTextWidth;
290 }
291
292 bool TextAutosizer::isIndependentDescendant(const RenderBlock* renderer)
293 {
294     ASSERT(isAutosizingContainer(renderer));
295
296     // "Autosizing clusters" are special autosizing containers within which we
297     // want to enforce a uniform text size multiplier, in the hopes of making
298     // the major sections of the page look internally consistent.
299     // All their descendants (including other autosizing containers) must share
300     // the same multiplier, except for subtrees which are themselves clusters,
301     // and some of their descendant containers might not be autosized at all
302     // (for example if their height is constrained).
303     // Additionally, clusterShouldBeAutosized requires each cluster to contain a
304     // minimum amount of text, without which it won't be autosized.
305     //
306     // Clusters are chosen using very similar criteria to CSS flow roots, aka
307     // block formatting contexts (http://w3.org/TR/css3-box/#flow-root), since
308     // flow roots correspond to box containers that behave somewhat
309     // independently from their parent (for example they don't overlap floats).
310     // The definition of a flow root also conveniently includes most of the
311     // ways that a box and its children can have significantly different width
312     // from the box's parent (we want to avoid having significantly different
313     // width blocks within a cluster, since the narrower blocks would end up
314     // larger than would otherwise be necessary).
315     return renderer->isRenderView()
316         || renderer->isFloating()
317         || renderer->isOutOfFlowPositioned()
318         || renderer->isTableCell()
319         || renderer->isTableCaption()
320         || renderer->isFlexibleBoxIncludingDeprecated()
321         || renderer->hasColumns()
322         || renderer->containingBlock()->isHorizontalWritingMode() != renderer->isHorizontalWritingMode()
323         || renderer->style()->isDisplayReplacedType();
324     // FIXME: Tables need special handling to multiply all their columns by
325     // the same amount even if they're different widths; so do hasColumns()
326     // containers, and probably flexboxes...
327 }
328
329 bool TextAutosizer::isAutosizingCluster(const RenderBlock* renderer, TextAutosizingClusterInfo& parentClusterInfo)
330 {
331     ASSERT(isAutosizingContainer(renderer));
332
333     return isNarrowDescendant(renderer, parentClusterInfo)
334         || isWiderDescendant(renderer, parentClusterInfo)
335         || isIndependentDescendant(renderer);
336 }
337
338 bool TextAutosizer::containerShouldBeAutosized(const RenderBlock* container)
339 {
340     if (containerContainsOneOfTags(container, formInputTags()))
341         return false;
342
343     if (containerIsRowOfLinks(container))
344         return false;
345
346     // Don't autosize block-level text that can't wrap (as it's likely to
347     // expand sideways and break the page's layout).
348     if (!container->style()->autoWrap())
349         return false;
350
351     return !contentHeightIsConstrained(container);
352 }
353
354 bool TextAutosizer::containerContainsOneOfTags(const RenderBlock* container, const Vector<QualifiedName>& tags)
355 {
356     const RenderObject* renderer = container;
357     while (renderer) {
358         const Node* rendererNode = renderer->node();
359         if (rendererNode && rendererNode->isElementNode()) {
360             if (tags.contains(toElement(rendererNode)->tagQName()))
361                 return true;
362         }
363         renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
364     }
365
366     return false;
367 }
368
369 bool TextAutosizer::containerIsRowOfLinks(const RenderObject* container)
370 {
371     // A "row of links" is a container for which holds:
372     //  1. it should not contain non-link text elements longer than 3 characters
373     //  2. it should contain min. 3 inline links and all links should
374     //     have the same specified font size
375     //  3. it should not contain <br> elements
376     //  4. it should contain only inline elements unless they are containers,
377     //     children of link elements or children of sub-containers.
378     int linkCount = 0;
379     RenderObject* renderer = container->nextInPreOrder(container);
380     float matchingFontSize = -1;
381
382     while (renderer) {
383         if (!isAutosizingContainer(renderer)) {
384             if (renderer->isText() && toRenderText(renderer)->text()->stripWhiteSpace()->length() > 3)
385                 return false;
386             if (!renderer->isInline())
387                 return false;
388             if (renderer->isBR())
389                 return false;
390         }
391         if (renderer->style()->isLink()) {
392             if (matchingFontSize < 0)
393                 matchingFontSize = renderer->style()->specifiedFontSize();
394             else {
395                 if (matchingFontSize != renderer->style()->specifiedFontSize())
396                     return false;
397             }
398
399             linkCount++;
400             // Skip traversing descendants of the link.
401             renderer = renderer->nextInPreOrderAfterChildren(container);
402         } else
403             renderer = nextInPreOrderSkippingDescendantsOfContainers(renderer, container);
404     }
405
406     return (linkCount >= 3);
407 }
408
409 bool TextAutosizer::contentHeightIsConstrained(const RenderBlock* container)
410 {
411     // FIXME: Propagate constrainedness down the tree, to avoid inefficiently walking back up from each box.
412     // FIXME: This code needs to take into account vertical writing modes.
413     // FIXME: Consider additional heuristics, such as ignoring fixed heights if the content is already overflowing before autosizing kicks in.
414     for (; container; container = container->containingBlock()) {
415         RenderStyle* style = container->style();
416         if (style->overflowY() >= OSCROLL)
417             return false;
418         if (style->height().isSpecified() || style->maxHeight().isSpecified()) {
419             // Some sites (e.g. wikipedia) set their html and/or body elements to height:100%,
420             // without intending to constrain the height of the content within them.
421             return !container->isRoot() && !container->isBody();
422         }
423         if (container->isFloatingOrOutOfFlowPositioned())
424             return false;
425     }
426     return false;
427 }
428
429 bool TextAutosizer::clusterShouldBeAutosized(TextAutosizingClusterInfo& clusterInfo, float blockWidth)
430 {
431     // Don't autosize clusters that contain less than 4 lines of text (in
432     // practice less lines are required, since measureDescendantTextWidth
433     // assumes that characters are 1em wide, but most characters are narrower
434     // than that, so we're overestimating their contribution to the linecount).
435     //
436     // This is to reduce the likelihood of autosizing things like headers and
437     // footers, which can be quite visually distracting. The rationale is that
438     // if a cluster contains very few lines of text then it's ok to have to zoom
439     // in and pan from side to side to read each line, since if there are very
440     // few lines of text you'll only need to pan across once or twice.
441     const float minLinesOfText = 4;
442     float minTextWidth = blockWidth * minLinesOfText;
443     float textWidth = 0;
444     measureDescendantTextWidth(clusterInfo.blockContainingAllText, clusterInfo, minTextWidth, textWidth);
445     if (textWidth >= minTextWidth)
446         return true;
447     return false;
448 }
449
450 void TextAutosizer::measureDescendantTextWidth(const RenderBlock* container, TextAutosizingClusterInfo& clusterInfo, float minTextWidth, float& textWidth)
451 {
452     bool skipLocalText = !containerShouldBeAutosized(container);
453
454     RenderObject* descendant = nextInPreOrderSkippingDescendantsOfContainers(container, container);
455     while (descendant) {
456         if (!skipLocalText && descendant->isText()) {
457             textWidth += toRenderText(descendant)->renderedTextLength() * descendant->style()->specifiedFontSize();
458         } else if (isAutosizingContainer(descendant)) {
459             RenderBlock* descendantBlock = toRenderBlock(descendant);
460             if (!isAutosizingCluster(descendantBlock, clusterInfo))
461                 measureDescendantTextWidth(descendantBlock, clusterInfo, minTextWidth, textWidth);
462         }
463         if (textWidth >= minTextWidth)
464             return;
465         descendant = nextInPreOrderSkippingDescendantsOfContainers(descendant, container);
466     }
467 }
468
469 RenderObject* TextAutosizer::nextInPreOrderSkippingDescendantsOfContainers(const RenderObject* current, const RenderObject* stayWithin)
470 {
471     if (current == stayWithin || !isAutosizingContainer(current))
472         return current->nextInPreOrder(stayWithin);
473     return current->nextInPreOrderAfterChildren(stayWithin);
474 }
475
476 const RenderBlock* TextAutosizer::findDeepestBlockContainingAllText(const RenderBlock* cluster)
477 {
478     size_t firstDepth = 0;
479     const RenderObject* firstTextLeaf = findFirstTextLeafNotInCluster(cluster, firstDepth, FirstToLast);
480     if (!firstTextLeaf)
481         return cluster;
482
483     size_t lastDepth = 0;
484     const RenderObject* lastTextLeaf = findFirstTextLeafNotInCluster(cluster, lastDepth, LastToFirst);
485     ASSERT(lastTextLeaf);
486
487     // Equalize the depths if necessary. Only one of the while loops below will get executed.
488     const RenderObject* firstNode = firstTextLeaf;
489     const RenderObject* lastNode = lastTextLeaf;
490     while (firstDepth > lastDepth) {
491         firstNode = firstNode->parent();
492         --firstDepth;
493     }
494     while (lastDepth > firstDepth) {
495         lastNode = lastNode->parent();
496         --lastDepth;
497     }
498
499     // Go up from both nodes until the parent is the same. Both pointers will point to the LCA then.
500     while (firstNode != lastNode) {
501         firstNode = firstNode->parent();
502         lastNode = lastNode->parent();
503     }
504
505     if (firstNode->isRenderBlock())
506         return toRenderBlock(firstNode);
507
508     // containingBlock() should never leave the cluster, since it only skips ancestors when finding the
509     // container of position:absolute/fixed blocks, and those cannot exist between a cluster and its text
510     // nodes lowest common ancestor as isAutosizingCluster would have made them into their own independent
511     // cluster.
512     RenderBlock* containingBlock = firstNode->containingBlock();
513     ASSERT(containingBlock->isDescendantOf(cluster));
514
515     return containingBlock;
516 }
517
518 const RenderObject* TextAutosizer::findFirstTextLeafNotInCluster(const RenderObject* parent, size_t& depth, TraversalDirection direction)
519 {
520     if (parent->isEmpty())
521         return parent->isText() ? parent : 0;
522
523     ++depth;
524     const RenderObject* child = (direction == FirstToLast) ? parent->firstChild() : parent->lastChild();
525     while (child) {
526         if (!isAutosizingContainer(child) || !isIndependentDescendant(toRenderBlock(child))) {
527             const RenderObject* leaf = findFirstTextLeafNotInCluster(child, depth, direction);
528             if (leaf)
529                 return leaf;
530         }
531         child = (direction == FirstToLast) ? child->nextSibling() : child->previousSibling();
532     }
533     --depth;
534
535     return 0;
536 }
537
538 } // namespace WebCore
539
540 #endif // ENABLE(TEXT_AUTOSIZING)