64f7a84f340664467f74da5c007076d272a643b9
[WebKit-https.git] / Source / WebCore / layout / Verification.cpp
1 /*
2  * Copyright (C) 2018 Apple 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
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "LayoutState.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "DisplayBox.h"
32 #include "InlineTextBox.h"
33 #include "LayoutBox.h"
34 #include "LayoutContainer.h"
35 #include "LayoutTreeBuilder.h"
36 #include "RenderBox.h"
37 #include "RenderInline.h"
38 #include "RenderView.h"
39 #include <wtf/text/TextStream.h>
40
41 namespace WebCore {
42 namespace Layout {
43
44 static bool areEssentiallyEqual(float a, LayoutUnit b)
45 {
46     if (a == b.toFloat())
47         return true;
48
49     return fabs(a - b.toFloat()) <= 4 * LayoutUnit::epsilon();
50 }
51
52 static bool outputMismatchingSimpleLineInformationIfNeeded(TextStream& stream, const LayoutState& layoutState, const RenderBlockFlow& blockFlow, const Container& inlineFormattingRoot)
53 {
54     auto* lineLayoutData = blockFlow.simpleLineLayout();
55     if (!lineLayoutData) {
56         ASSERT_NOT_REACHED();
57         return true;
58     }
59
60     auto& inlineFormattingState = layoutState.establishedFormattingState(inlineFormattingRoot);
61     ASSERT(is<InlineFormattingState>(inlineFormattingState));
62     auto& inlineRunList = downcast<InlineFormattingState>(inlineFormattingState).inlineRuns();
63
64     if (inlineRunList.size() != lineLayoutData->runCount()) {
65         stream << "Mismatching number of runs: simple runs(" << lineLayoutData->runCount() << ") inline runs(" << inlineRunList.size() << ")";
66         stream.nextLine();
67         return true;
68     }
69
70     auto mismatched = false;
71     for (unsigned i = 0; i < lineLayoutData->runCount(); ++i) {
72         auto& simpleRun = lineLayoutData->runAt(i);
73         auto& inlineRun = inlineRunList[i];
74
75         auto matchingRuns = areEssentiallyEqual(simpleRun.logicalLeft, inlineRun.logicalLeft()) && areEssentiallyEqual(simpleRun.logicalRight, inlineRun.logicalRight());
76         if (matchingRuns)
77             matchingRuns = (simpleRun.start == inlineRun.textContext()->start() && simpleRun.end == (inlineRun.textContext()->start() + inlineRun.textContext()->length()));
78         if (matchingRuns)
79             continue;
80
81         stream << "Mismatching: simple run(" << simpleRun.start << ", " << simpleRun.end << ") (" << simpleRun.logicalLeft << ", " << simpleRun.logicalRight << ") layout run(" << inlineRun.textContext()->start() << ", " << inlineRun.textContext()->start() + inlineRun.textContext()->length() << ") (" << inlineRun.logicalLeft() << ", " << inlineRun.logicalRight() << ")";
82         stream.nextLine();
83         mismatched = true;
84     }
85     return mismatched;
86 }
87
88 static bool checkForMatchingNonTextRuns(const InlineRun& inlineRun, const WebCore::InlineBox& inlineBox)
89 {
90     return areEssentiallyEqual(inlineBox.logicalLeft(), inlineRun.logicalLeft())
91         && areEssentiallyEqual(inlineBox.logicalRight(), inlineRun.logicalRight())
92         && areEssentiallyEqual(inlineBox.logicalHeight(), inlineRun.logicalHeight());
93 }
94
95 static bool checkForMatchingTextRuns(const InlineRun& inlineRun, float logicalLeft, float logicalRight, unsigned start, unsigned end, float logicalHeight)
96 {
97     return areEssentiallyEqual(logicalLeft, inlineRun.logicalLeft())
98         && areEssentiallyEqual(logicalRight, inlineRun.logicalRight())
99         && start == inlineRun.textContext()->start()
100         && (end == (inlineRun.textContext()->start() + inlineRun.textContext()->length()))
101         && areEssentiallyEqual(logicalHeight, inlineRun.logicalHeight());
102 }
103
104 static void collectFlowBoxSubtree(const InlineFlowBox& flowbox, Vector<WebCore::InlineBox*>& inlineBoxes)
105 {
106     auto* inlineBox = flowbox.firstLeafChild();
107     auto* lastLeafChild = flowbox.lastLeafChild();
108     while (inlineBox) {
109         inlineBoxes.append(inlineBox);
110         if (inlineBox == lastLeafChild)
111             break;
112         inlineBox = inlineBox->nextLeafChild();
113     }
114 }
115
116 static void collectInlineBoxes(const RenderBlockFlow& root, Vector<WebCore::InlineBox*>& inlineBoxes)
117 {
118     for (auto* rootLine = root.firstRootBox(); rootLine; rootLine = rootLine->nextRootBox()) {
119         for (auto* inlineBox = rootLine->firstChild(); inlineBox; inlineBox = inlineBox->nextOnLine()) {
120             if (!is<InlineFlowBox>(inlineBox)) {
121                 inlineBoxes.append(inlineBox);
122                 continue;
123             }
124             collectFlowBoxSubtree(downcast<InlineFlowBox>(*inlineBox), inlineBoxes);
125         }
126     }
127 }
128
129 static LayoutUnit resolveForRelativePositionIfNeeded(const InlineTextBox& inlineTextBox)
130 {
131     LayoutUnit xOffset;
132     auto* parent = inlineTextBox.parent();
133     while (is<InlineFlowBox>(parent)) {
134         auto& renderer = parent->renderer();
135         if (renderer.isInFlowPositioned())
136             xOffset = downcast<RenderInline>(renderer).offsetForInFlowPosition().width();
137         parent = parent->parent();
138     }
139     return xOffset;
140 }
141
142 static bool outputMismatchingComplexLineInformationIfNeeded(TextStream& stream, const LayoutState& layoutState, const RenderBlockFlow& blockFlow, const Container& inlineFormattingRoot)
143 {
144     auto& inlineFormattingState = layoutState.establishedFormattingState(inlineFormattingRoot);
145     ASSERT(is<InlineFormattingState>(inlineFormattingState));
146     auto& inlineRunList = downcast<InlineFormattingState>(inlineFormattingState).inlineRuns();
147
148     // Collect inlineboxes.
149     Vector<WebCore::InlineBox*> inlineBoxes;
150     collectInlineBoxes(blockFlow, inlineBoxes);
151
152     auto mismatched = false;
153     unsigned runIndex = 0;
154
155     if (inlineBoxes.size() != inlineRunList.size()) {
156         stream << "Warning: mismatching number of runs: inlineboxes(" << inlineBoxes.size() << ") vs. inline runs(" << inlineRunList.size() << ")";
157         stream.nextLine();
158     }
159
160     for (unsigned inlineBoxIndex = 0; inlineBoxIndex < inlineBoxes.size() && runIndex < inlineRunList.size(); ++inlineBoxIndex) {
161         auto* inlineBox = inlineBoxes[inlineBoxIndex];
162         auto* inlineTextBox = is<InlineTextBox>(inlineBox) ? downcast<InlineTextBox>(inlineBox) : nullptr;
163
164         auto& inlineRun = inlineRunList[runIndex];
165         auto matchingRuns = false;
166         if (inlineTextBox) {
167             auto xOffset = resolveForRelativePositionIfNeeded(*inlineTextBox);
168             matchingRuns = checkForMatchingTextRuns(inlineRun, inlineTextBox->logicalLeft() + xOffset,
169                 inlineTextBox->logicalRight() + xOffset,
170                 inlineTextBox->start(),
171                 inlineTextBox->end() + 1,
172                 inlineTextBox->logicalHeight());
173
174             // <span>foobar</span>foobar generates 2 inline text boxes while we only generate one inline run.
175             // also <div>foo<img style="float: left;">bar</div> too.
176             auto inlineRunEnd = inlineRun.textContext()->start() + inlineRun.textContext()->length();
177             auto textRunMightBeExtended = !matchingRuns && inlineTextBox->end() < inlineRunEnd && inlineBoxIndex < inlineBoxes.size() - 1;
178
179             if (textRunMightBeExtended) {
180                 auto logicalLeft = inlineTextBox->logicalLeft() + xOffset;
181                 auto logicalRight = inlineTextBox->logicalRight() + xOffset;
182                 auto start = inlineTextBox->start();
183                 auto end = inlineTextBox->end() + 1;
184                 auto index = ++inlineBoxIndex;
185                 for (; index < inlineBoxes.size(); ++index) {
186                     auto* inlineBox = inlineBoxes[index];
187                     auto* inlineTextBox = is<InlineTextBox>(inlineBox) ? downcast<InlineTextBox>(inlineBox) : nullptr;
188                     // Can't mix different inline boxes.
189                     if (!inlineTextBox)
190                         break;
191
192                     auto xOffset = resolveForRelativePositionIfNeeded(*inlineTextBox);
193                     logicalRight = inlineTextBox->logicalRight() + xOffset;
194                     end += (inlineTextBox->end() + 1);
195                     if (checkForMatchingTextRuns(inlineRun, logicalLeft, logicalRight, start, end, inlineTextBox->logicalHeight())) {
196                         matchingRuns = true;
197                         inlineBoxIndex = index;
198                         break;
199                     }
200
201                     // Went too far?
202                     if (end >= inlineRunEnd)
203                         break;
204                 }
205             }
206         } else
207             matchingRuns = checkForMatchingNonTextRuns(inlineRun, *inlineBox);
208
209
210         if (!matchingRuns) {
211             stream << "Mismatching: run ";
212
213             if (inlineTextBox)
214                 stream << "(" << inlineTextBox->start() << ", " << inlineTextBox->end() + 1 << ")";
215             stream << " (" << inlineBox->logicalLeft() << ", " << inlineBox->logicalRight() << ") (" << inlineBox->logicalWidth() << "x" << inlineBox->logicalHeight() << ")";
216
217             stream << "inline run ";
218             if (inlineRun.textContext())
219                 stream << "(" << inlineRun.textContext()->start() << ", " << inlineRun.textContext()->start() + inlineRun.textContext()->length() << ") ";
220             stream << "(" << inlineRun.logicalLeft() << ", " << inlineRun.logicalRight() << ") (" << inlineRun.logicalWidth() << "x" << inlineRun.logicalHeight() << ")";
221             stream.nextLine();
222             mismatched = true;
223         }
224         ++runIndex;
225     }
226     return mismatched;
227 }
228
229 static bool outputMismatchingBlockBoxInformationIfNeeded(TextStream& stream, const LayoutState& context, const RenderBox& renderer, const Box& layoutBox)
230 {
231     bool firstMismatchingRect = true;
232     auto outputRect = [&] (const String& prefix, const LayoutRect& rendererRect, const LayoutRect& layoutRect) {
233         if (firstMismatchingRect) {
234             stream << (renderer.element() ? renderer.element()->nodeName().utf8().data() : "") << " " << renderer.renderName() << "(" << &renderer << ") layoutBox(" << &layoutBox << ")";
235             stream.nextLine();
236             firstMismatchingRect = false;
237         }
238
239         stream  << prefix.utf8().data() << "\trenderer->(" << rendererRect.x() << "," << rendererRect.y() << ") (" << rendererRect.width() << "x" << rendererRect.height() << ")"
240             << "\tlayout->(" << layoutRect.x() << "," << layoutRect.y() << ") (" << layoutRect.width() << "x" << layoutRect.height() << ")"; 
241         stream.nextLine();
242     };
243
244     auto renderBoxLikeMarginBox = [](auto& displayBox) {
245         // Produce a RenderBox matching margin box.
246         auto borderBox = displayBox.borderBox();
247
248         return Display::Box::Rect {
249             borderBox.top() - displayBox.nonCollapsedMarginBefore(),
250             borderBox.left() - displayBox.computedMarginStart().valueOr(0),
251             displayBox.computedMarginStart().valueOr(0) + borderBox.width() + displayBox.computedMarginEnd().valueOr(0),
252             displayBox.nonCollapsedMarginBefore() + borderBox.height() + displayBox.nonCollapsedMarginAfter()
253         };
254     };
255
256     auto& displayBox = context.displayBoxForLayoutBox(layoutBox);
257
258     auto frameRect = renderer.frameRect();
259     // rendering does not offset for relative positioned boxes.
260     if (renderer.isInFlowPositioned())
261         frameRect.move(renderer.offsetForInFlowPosition());
262
263     if (frameRect != displayBox.rect()) {
264         outputRect("frameBox", renderer.frameRect(), displayBox.rect());
265         return true;
266     }
267
268     if (renderer.marginBoxRect() != renderBoxLikeMarginBox(displayBox)) {
269         outputRect("marginBox", renderer.marginBoxRect(), renderBoxLikeMarginBox(displayBox));
270         return true;
271     }
272
273     if (renderer.borderBoxRect() != displayBox.borderBox()) {
274         outputRect("borderBox", renderer.borderBoxRect(), displayBox.borderBox());
275         return true;
276     }
277
278     if (renderer.paddingBoxRect() != displayBox.paddingBox()) {
279         outputRect("paddingBox", renderer.paddingBoxRect(), displayBox.paddingBox());
280         return true;
281     }
282
283     if (renderer.contentBoxRect() != displayBox.contentBox()) {
284         outputRect("contentBox", renderer.contentBoxRect(), displayBox.contentBox());
285         return true;
286     }
287
288     return false;
289 }
290
291 static bool verifyAndOutputSubtree(TextStream& stream, const LayoutState& context, const RenderBox& renderer, const Box& layoutBox)
292 {
293     auto mismtachingGeometry = outputMismatchingBlockBoxInformationIfNeeded(stream, context, renderer, layoutBox);
294
295     if (!is<Container>(layoutBox))
296         return mismtachingGeometry;
297
298     auto& container = downcast<Container>(layoutBox);
299     auto* childBox = container.firstChild();
300     auto* childRenderer = renderer.firstChild();
301
302     while (childRenderer) {
303         if (!is<RenderBox>(*childRenderer)) {
304             childRenderer = childRenderer->nextSibling();
305             continue;
306         }
307
308         if (!childBox) {
309             stream  << "Trees are out of sync!";
310             stream.nextLine();
311             return true;
312         }
313
314         if (is<RenderBlockFlow>(*childRenderer) && childBox->establishesInlineFormattingContext()) {
315             ASSERT(childRenderer->childrenInline());
316             auto& blockFlow = downcast<RenderBlockFlow>(*childRenderer);
317             auto& formattingRoot = downcast<Container>(*childBox);
318             mismtachingGeometry |= blockFlow.lineLayoutPath() == RenderBlockFlow::SimpleLinesPath ? outputMismatchingSimpleLineInformationIfNeeded(stream, context, blockFlow, formattingRoot) : outputMismatchingComplexLineInformationIfNeeded(stream, context, blockFlow, formattingRoot);
319         } else {
320             auto mismatchingSubtreeGeometry = verifyAndOutputSubtree(stream, context, downcast<RenderBox>(*childRenderer), *childBox);
321             mismtachingGeometry |= mismatchingSubtreeGeometry;
322         }
323
324         childBox = childBox->nextSibling();
325         childRenderer = childRenderer->nextSibling();
326     }
327
328     return mismtachingGeometry;
329 }
330
331 void LayoutState::verifyAndOutputMismatchingLayoutTree(const RenderView& renderView) const
332 {
333     TextStream stream;
334     auto mismatchingGeometry = verifyAndOutputSubtree(stream, *this, renderView, initialContainingBlock());
335     if (!mismatchingGeometry)
336         return;
337 #if ENABLE(TREE_DEBUGGING)
338     showRenderTree(&renderView);
339     showLayoutTree(initialContainingBlock(), this);
340 #endif
341     WTFLogAlways("%s", stream.release().utf8().data());
342     ASSERT_NOT_REACHED();
343 }
344
345 }
346 }
347
348 #endif