5572d85396ddd89f422d43b8f5a2c077bccc7b84
[WebKit-https.git] / Tools / LayoutReloaded / FormattingContext / FloatingContext.js
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. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 // All geometry here is absolute to the formatting context's root.
27 class FloatingContext {
28     constructor(formattingContext) {
29         this.m_leftFloatingBoxStack = new Array();
30         this.m_rightFloatingBoxStack = new Array();
31         this.m_lastFloating = null;
32         this.m_formattingContext = formattingContext;
33     }
34
35     computePosition(layoutBox) {
36         if (layoutBox.isOutOfFlowPositioned())
37             return;
38         let displayBox = this._formattingContext().displayBox(layoutBox);
39         if (layoutBox.isFloatingPositioned()) {
40             displayBox.setTopLeft(this._positionForFloating(layoutBox));
41             this._addFloating(layoutBox);
42             return;
43         }
44         if (Utils.hasClear(layoutBox))
45             return displayBox.setTopLeft(this._positionForClear(layoutBox));
46         // Intruding floats might force this box move.
47         displayBox.setTopLeft(this._computePositionToAvoidIntrudingFloats(layoutBox));
48     }
49
50     bottom() {
51         let leftBottom = this._bottom(this.m_leftFloatingBoxStack);
52         let rightBottom = this._bottom(this.m_rightFloatingBoxStack);
53         if (Number.isNaN(leftBottom) && Number.isNaN(rightBottom))
54             return Number.NaN;
55         if (!Number.isNaN(leftBottom) && !Number.isNaN(rightBottom))
56             return Math.max(leftBottom, rightBottom);
57         if (!Number.isNaN(leftBottom))
58             return leftBottom;
59         return rightBottom;
60     }
61
62     _positionForFloating(floatingBox) {
63         let absoluteFloatingBox = this._formattingContext().absoluteMarginBox(floatingBox);
64         if (this._isEmpty())
65             return this._adjustedFloatingPosition(floatingBox, absoluteFloatingBox.top());
66         let verticalPosition = Math.max(absoluteFloatingBox.top(), this.m_lastFloating.top());
67         let spaceNeeded = absoluteFloatingBox.width();
68         while (true) {
69             let floatingPair = this._findInnerMostLeftAndRight(verticalPosition);
70             if (this._availableSpace(floatingBox.containingBlock(), floatingPair) >= spaceNeeded)
71                 return this._adjustedFloatingPosition(floatingBox, verticalPosition, floatingPair);
72             verticalPosition = this._moveToNextVerticalPosition(floatingPair);
73         }
74         return Math.Nan;
75     }
76
77     _positionForClear(layoutBox) {
78         ASSERT(Utils.hasClear(layoutBox));
79         let displayBox = this._formattingContext().displayBox(layoutBox);
80         if (this._isEmpty())
81             return displayBox.topLeft();
82
83         let leftBottom = Number.NaN;
84         let rightBottom = Number.NaN;
85         if (Utils.hasClearLeft(layoutBox) || Utils.hasClearBoth(layoutBox))
86             leftBottom = this._bottom(this.m_leftFloatingBoxStack);
87         if (Utils.hasClearRight(layoutBox) || Utils.hasClearBoth(layoutBox))
88             rightBottom = this._bottom(this.m_rightFloatingBoxStack);
89
90         if (!Number.isNaN(leftBottom) && !Number.isNaN(rightBottom))
91             return new LayoutPoint(Math.max(leftBottom, rightBottom), displayBox.left());
92         if (!Number.isNaN(leftBottom))
93             return new LayoutPoint(leftBottom, displayBox.left());
94         if (!Number.isNaN(rightBottom))
95             return new LayoutPoint(rightBottom, displayBox.left());
96         return displayBox.topLeft();
97     }
98
99     _computePositionToAvoidIntrudingFloats(layoutBox) {
100         if (!layoutBox.establishesBlockFormattingContext() || this._isEmpty())
101             return this._formattingContext().displayBox(layoutBox).topLeft();
102         // The border box of a table, a block-level replaced element, or an element in the normal flow that establishes
103         // a new block formatting context (such as an element with 'overflow' other than 'visible') must not overlap the
104         // margin box of any floats in the same block formatting context as the element itself.
105         // For some reason, we position this as if it was floating left.
106         return this._positionForFloating(layoutBox);
107     }
108
109     _addFloating(floatingBox) {
110         // Convert floating box to absolute.
111         let floatingDisplayBox = this._formattingContext().displayBox(floatingBox).clone();
112         floatingDisplayBox.setRect(this._formattingContext().absoluteMarginBox(floatingBox));
113         this.m_lastFloating = floatingDisplayBox;
114         if (Utils.isFloatingLeft(floatingBox)) {
115             this.m_leftFloatingBoxStack.push(floatingDisplayBox);
116             return;
117         }
118         this.m_rightFloatingBoxStack.push(floatingDisplayBox);
119     }
120
121     _findInnerMostLeftAndRight(verticalPosition) {
122         let leftFloating = this._findFloatingAtVerticalPosition(verticalPosition, this.m_leftFloatingBoxStack);
123         let rightFloating = this._findFloatingAtVerticalPosition(verticalPosition, this.m_rightFloatingBoxStack);
124         return { left: leftFloating, right: rightFloating };
125     }
126
127     _moveToNextVerticalPosition(floatingPair) {
128         if (!floatingPair.left && !floatingPair.right)
129             return Math.NaN;
130         let leftBottom = Number.POSITIVE_INFINITY;
131         let rightBottom = Number.POSITIVE_INFINITY;
132         if (floatingPair.left)
133             leftBottom = floatingPair.left.bottom();
134         if (floatingPair.right)
135             rightBottom = floatingPair.right.bottom();
136         return Math.min(leftBottom, rightBottom);
137     }
138
139     _availableSpace(containingBlock, floatingPair) {
140         let containingBlockContentBox = this._formattingContext().displayBox(containingBlock);
141         if (floatingPair.left && floatingPair.right)
142             return floatingPair.right.left() - floatingPair.left.right();
143         if (floatingPair.left)
144             return containingBlockContentBox.width() - (floatingPair.left.right() - this._formattingContext().absoluteBorderBox(containingBlock).left());
145         if (floatingPair.right)
146             return floatingPair.right.left();
147         return containingBlockContentBox.width();
148     }
149
150     _findFloatingAtVerticalPosition(verticalPosition, floatingStack) {
151         let index = floatingStack.length;
152         while (--index >= 0 && floatingStack[index].bottom() <= verticalPosition);
153         return index >= 0 ? floatingStack[index] : null;
154     }
155
156     _isEmpty() {
157         return !this.m_leftFloatingBoxStack.length && !this.m_rightFloatingBoxStack.length;
158     }
159
160     _adjustedFloatingPosition(floatingBox, verticalPosition, leftRightFloatings) {
161         let containingBlock = floatingBox.containingBlock();
162         // Convert all coordinates relative to formatting context's root.
163         let left = this._formattingContext().absoluteContentBox(containingBlock).left();
164         let right = this._formattingContext().absoluteContentBox(containingBlock).right();
165         if (leftRightFloatings) {
166             if (leftRightFloatings.left) {
167                 let floatingBoxRight = leftRightFloatings.left.right();
168                 if (floatingBoxRight > left)
169                     left = floatingBoxRight;
170             }
171
172             if (leftRightFloatings.right) {
173                 let floatingBoxLeft = leftRightFloatings.right.left();
174                 if (floatingBoxLeft < right)
175                     right = floatingBoxLeft;
176             }
177         }
178         left += this._formattingContext().marginLeft(floatingBox);
179         right -= this._formattingContext().marginRight(floatingBox);
180         verticalPosition += this._formattingContext().marginTop(floatingBox);
181         // No convert them back relative to the floatingBox's containing block.
182         let containingBlockLeft = this._formattingContext().absoluteBorderBox(containingBlock).left();
183         let containingBlockTop = this._formattingContext().absoluteBorderBox(containingBlock).top();
184         left -= containingBlockLeft;
185         right -= containingBlockLeft;
186         verticalPosition -= containingBlockTop;
187
188         if (Utils.isFloatingLeft(floatingBox) || !Utils.isFloatingPositioned(floatingBox))
189             return new LayoutPoint(verticalPosition, left);
190         return new LayoutPoint(verticalPosition, right - this._formattingContext().displayBox(floatingBox).rect().width());
191     }
192
193     _bottom(floatingStack) {
194         if (!floatingStack || !floatingStack.length)
195             return Number.NaN;
196         let max = Number.NEGATIVE_INFINITY;
197         for (let i = 0; i < floatingStack.length; ++i)
198             max = Math.max(floatingStack[i].bottom(), max);
199         return max;
200     }
201
202     _formattingContext() {
203         return this.m_formattingContext;
204     }
205 }