Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /* class that manages rules for positioning floats */
8 :
9 : #include "nsFloatManager.h"
10 :
11 : #include <algorithm>
12 : #include <initializer_list>
13 :
14 : #include "gfxContext.h"
15 : #include "mozilla/ReflowInput.h"
16 : #include "mozilla/ShapeUtils.h"
17 : #include "nsBlockFrame.h"
18 : #include "nsDeviceContext.h"
19 : #include "nsError.h"
20 : #include "nsImageRenderer.h"
21 : #include "nsIPresShell.h"
22 : #include "nsMemory.h"
23 :
24 : using namespace mozilla;
25 : using namespace mozilla::image;
26 : using namespace mozilla::gfx;
27 :
28 : int32_t nsFloatManager::sCachedFloatManagerCount = 0;
29 : void* nsFloatManager::sCachedFloatManagers[NS_FLOAT_MANAGER_CACHE_SIZE];
30 :
31 0 : /////////////////////////////////////////////////////////////////////////////
32 0 : // nsFloatManager
33 :
34 : nsFloatManager::nsFloatManager(nsIPresShell* aPresShell,
35 : WritingMode aWM)
36 : :
37 : #ifdef DEBUG
38 : mWritingMode(aWM),
39 : #endif
40 : mLineLeft(0), mBlockStart(0),
41 : mFloatDamage(aPresShell),
42 0 : mPushedLeftFloatPastBreak(false),
43 : mPushedRightFloatPastBreak(false),
44 0 : mSplitLeftFloatAcrossBreak(false),
45 0 : mSplitRightFloatAcrossBreak(false)
46 : {
47 0 : MOZ_COUNT_CTOR(nsFloatManager);
48 : }
49 0 :
50 0 : nsFloatManager::~nsFloatManager()
51 : {
52 : MOZ_COUNT_DTOR(nsFloatManager);
53 0 : }
54 :
55 0 : // static
56 : void* nsFloatManager::operator new(size_t aSize) CPP_THROW_NEW
57 : {
58 0 : if (sCachedFloatManagerCount > 0) {
59 : // We have cached unused instances of this class, return a cached
60 : // instance in stead of always creating a new one.
61 : return sCachedFloatManagers[--sCachedFloatManagerCount];
62 : }
63 0 :
64 : // The cache is empty, this means we have to create a new instance using
65 : // the global |operator new|.
66 : return moz_xmalloc(aSize);
67 0 : }
68 :
69 0 : void
70 : nsFloatManager::operator delete(void* aPtr, size_t aSize)
71 : {
72 : if (!aPtr)
73 : return;
74 : // This float manager is no longer used, if there's still room in
75 0 : // the cache we'll cache this float manager, unless the layout
76 : // module was already shut down.
77 :
78 : if (sCachedFloatManagerCount < NS_FLOAT_MANAGER_CACHE_SIZE &&
79 : sCachedFloatManagerCount >= 0) {
80 0 : // There's still space in the cache for more instances, put this
81 0 : // instance in the cache in stead of deleting it.
82 :
83 : sCachedFloatManagers[sCachedFloatManagerCount++] = aPtr;
84 : return;
85 : }
86 0 :
87 : // The cache is full, or the layout module has been shut down,
88 : // delete this float manager.
89 : free(aPtr);
90 : }
91 0 :
92 :
93 : /* static */
94 : void nsFloatManager::Shutdown()
95 : {
96 : // The layout module is being shut down, clean up the cache and
97 : // disable further caching.
98 0 :
99 0 : int32_t i;
100 0 :
101 0 : for (i = 0; i < sCachedFloatManagerCount; i++) {
102 : void* floatManager = sCachedFloatManagers[i];
103 : if (floatManager)
104 : free(floatManager);
105 0 : }
106 0 :
107 : // Disable further caching.
108 : sCachedFloatManagerCount = -1;
109 : }
110 :
111 : #define CHECK_BLOCK_AND_LINE_DIR(aWM) \
112 : NS_ASSERTION((aWM).GetBlockDir() == mWritingMode.GetBlockDir() && \
113 : (aWM).IsLineInverted() == mWritingMode.IsLineInverted(), \
114 0 : "incompatible writing modes")
115 :
116 : nsFlowAreaRect
117 : nsFloatManager::GetFlowArea(WritingMode aWM, nscoord aBCoord, nscoord aBSize,
118 : BandInfoType aBandInfoType, ShapeType aShapeType,
119 0 : LogicalRect aContentArea, SavedState* aState,
120 0 : const nsSize& aContainerSize) const
121 0 : {
122 : CHECK_BLOCK_AND_LINE_DIR(aWM);
123 : NS_ASSERTION(aBSize >= 0, "unexpected max block size");
124 0 : NS_ASSERTION(aContentArea.ISize(aWM) >= 0,
125 0 : "unexpected content area inline size");
126 0 :
127 0 : nscoord blockStart = aBCoord + mBlockStart;
128 : if (blockStart < nscoord_MIN) {
129 : NS_WARNING("bad value");
130 : blockStart = nscoord_MIN;
131 : }
132 0 :
133 : // Determine the last float that we should consider.
134 0 : uint32_t floatCount;
135 0 : if (aState) {
136 : // Use the provided state.
137 : floatCount = aState->mFloatInfoCount;
138 0 : MOZ_ASSERT(floatCount <= mFloats.Length(), "bad state");
139 : } else {
140 : // Use our current state.
141 : floatCount = mFloats.Length();
142 : }
143 0 :
144 0 : // If there are no floats at all, or we're below the last one, return
145 0 : // quickly.
146 0 : if (floatCount == 0 ||
147 0 : (mFloats[floatCount-1].mLeftBEnd <= blockStart &&
148 148 : mFloats[floatCount-1].mRightBEnd <= blockStart)) {
149 : return nsFlowAreaRect(aWM, aContentArea.IStart(aWM), aBCoord,
150 : aContentArea.ISize(aWM), aBSize,
151 : nsFlowAreaRectFlags::NO_FLAGS);
152 0 : }
153 :
154 : nscoord blockEnd;
155 0 : if (aBSize == nscoord_MAX) {
156 : // This warning (and the two below) are possible to hit on pages
157 : // with really large objects.
158 0 : NS_WARNING_ASSERTION(aBandInfoType == BandInfoType::BandFromPoint, "bad height");
159 0 : blockEnd = nscoord_MAX;
160 0 : } else {
161 0 : blockEnd = blockStart + aBSize;
162 : if (blockEnd < blockStart || blockEnd > nscoord_MAX) {
163 : NS_WARNING("bad value");
164 0 : blockEnd = nscoord_MAX;
165 0 : }
166 0 : }
167 0 : nscoord lineLeft = mLineLeft + aContentArea.LineLeft(aWM, aContainerSize);
168 0 : nscoord lineRight = mLineLeft + aContentArea.LineRight(aWM, aContainerSize);
169 : if (lineRight < lineLeft) {
170 : NS_WARNING("bad value");
171 : lineRight = lineLeft;
172 : }
173 :
174 : // Walk backwards through the floats until we either hit the front of
175 0 : // the list or we're above |blockStart|.
176 0 : bool haveFloats = false;
177 0 : bool mayWiden = false;
178 : for (uint32_t i = floatCount; i > 0; --i) {
179 : const FloatInfo &fi = mFloats[i-1];
180 : if (fi.mLeftBEnd <= blockStart && fi.mRightBEnd <= blockStart) {
181 0 : // There aren't any more floats that could intersect this band.
182 : break;
183 : }
184 : if (fi.IsEmpty(aShapeType)) {
185 : // Ignore empty float areas.
186 : // https://drafts.csswg.org/css-shapes/#relation-to-box-model-and-float-behavior
187 0 : continue;
188 0 : }
189 0 :
190 : nscoord floatBStart = fi.BStart(aShapeType);
191 0 : nscoord floatBEnd = fi.BEnd(aShapeType);
192 0 : if (blockStart < floatBStart && aBandInfoType == BandInfoType::BandFromPoint) {
193 : // This float is below our band. Shrink our band's height if needed.
194 : if (floatBStart < blockEnd) {
195 : blockEnd = floatBStart;
196 : }
197 : }
198 : // If blockStart == blockEnd (which happens only with WidthWithinHeight),
199 : // we include floats that begin at our 0-height vertical area. We
200 0 : // need to do this to satisfy the invariant that a
201 0 : // WidthWithinHeight call is at least as narrow on both sides as a
202 0 : // BandFromPoint call beginning at its blockStart.
203 : else if (blockStart < floatBEnd &&
204 : (floatBStart < blockEnd ||
205 : (floatBStart == blockEnd && blockStart == blockEnd))) {
206 0 : // This float is in our band.
207 :
208 : // Shrink our band's width if needed.
209 : StyleFloat floatStyle = fi.mFrame->StyleDisplay()->PhysicalFloats(aWM);
210 :
211 0 : // When aBandInfoType is BandFromPoint, we're only intended to
212 0 : // consider a point along the y axis rather than a band.
213 : const nscoord bandBlockEnd =
214 : aBandInfoType == BandInfoType::BandFromPoint ? blockStart : blockEnd;
215 0 : if (floatStyle == StyleFloat::Left) {
216 0 : // A left float
217 0 : nscoord lineRightEdge =
218 : fi.LineRight(aShapeType, blockStart, bandBlockEnd);
219 : if (lineRightEdge > lineLeft) {
220 : lineLeft = lineRightEdge;
221 : // Only set haveFloats to true if the float is inside our
222 0 : // containing block. This matches the spec for what some
223 : // callers want and disagrees for other callers, so we should
224 : // probably provide better information at some point.
225 : haveFloats = true;
226 0 :
227 : // Our area may widen in the block direction if this float may
228 : // narrow in the block direction.
229 : mayWiden = mayWiden || fi.MayNarrowInBlockDirection(aShapeType);
230 : }
231 0 : } else {
232 0 : // A right float
233 0 : nscoord lineLeftEdge =
234 : fi.LineLeft(aShapeType, blockStart, bandBlockEnd);
235 0 : if (lineLeftEdge < lineRight) {
236 0 : lineRight = lineLeftEdge;
237 : // See above.
238 : haveFloats = true;
239 : mayWiden = mayWiden || fi.MayNarrowInBlockDirection(aShapeType);
240 : }
241 0 : }
242 0 :
243 : // Shrink our band's height if needed.
244 : if (floatBEnd < blockEnd && aBandInfoType == BandInfoType::BandFromPoint) {
245 : blockEnd = floatBEnd;
246 : }
247 0 : }
248 0 : }
249 :
250 0 : nscoord blockSize = (blockEnd == nscoord_MAX) ?
251 0 : nscoord_MAX : (blockEnd - blockStart);
252 0 : // convert back from LineLeft/Right to IStart
253 0 : nscoord inlineStart = aWM.IsBidiLTR()
254 : ? lineLeft - mLineLeft
255 : : mLineLeft - lineRight +
256 0 : LogicalSize(aWM, aContainerSize).ISize(aWM);
257 0 :
258 : nsFlowAreaRectFlags flags =
259 0 : (haveFloats ? nsFlowAreaRectFlags::HAS_FLOATS : nsFlowAreaRectFlags::NO_FLAGS) |
260 0 : (mayWiden ? nsFlowAreaRectFlags::MAY_WIDEN : nsFlowAreaRectFlags::NO_FLAGS);
261 :
262 : return nsFlowAreaRect(aWM, inlineStart, blockStart - mBlockStart,
263 : lineRight - lineLeft, blockSize, flags);
264 0 : }
265 :
266 : void
267 0 : nsFloatManager::AddFloat(nsIFrame* aFloatFrame, const LogicalRect& aMarginRect,
268 0 : WritingMode aWM, const nsSize& aContainerSize)
269 0 : {
270 : CHECK_BLOCK_AND_LINE_DIR(aWM);
271 : NS_ASSERTION(aMarginRect.ISize(aWM) >= 0, "negative inline size!");
272 0 : NS_ASSERTION(aMarginRect.BSize(aWM) >= 0, "negative block size!");
273 :
274 : FloatInfo info(aFloatFrame, mLineLeft, mBlockStart, aMarginRect, aWM,
275 0 : aContainerSize);
276 0 :
277 0 : // Set mLeftBEnd and mRightBEnd.
278 0 : if (HasAnyFloats()) {
279 : FloatInfo &tail = mFloats[mFloats.Length() - 1];
280 0 : info.mLeftBEnd = tail.mLeftBEnd;
281 0 : info.mRightBEnd = tail.mRightBEnd;
282 : } else {
283 0 : info.mLeftBEnd = nscoord_MIN;
284 0 : info.mRightBEnd = nscoord_MIN;
285 : }
286 : StyleFloat floatStyle = aFloatFrame->StyleDisplay()->PhysicalFloats(aWM);
287 0 : MOZ_ASSERT(floatStyle == StyleFloat::Left || floatStyle == StyleFloat::Right,
288 0 : "Unexpected float style!");
289 0 : nscoord& sideBEnd =
290 0 : floatStyle == StyleFloat::Left ? info.mLeftBEnd : info.mRightBEnd;
291 : nscoord thisBEnd = info.BEnd();
292 0 : if (thisBEnd > sideBEnd)
293 0 : sideBEnd = thisBEnd;
294 :
295 : mFloats.AppendElement(std::move(info));
296 : }
297 0 :
298 : // static
299 : LogicalRect
300 : nsFloatManager::CalculateRegionFor(WritingMode aWM,
301 : nsIFrame* aFloat,
302 : const LogicalMargin& aMargin,
303 0 : const nsSize& aContainerSize)
304 0 : {
305 0 : // We consider relatively positioned frames at their original position.
306 : LogicalRect region(aWM, nsRect(aFloat->GetNormalPosition(),
307 : aFloat->GetSize()),
308 0 : aContainerSize);
309 :
310 : // Float region includes its margin
311 : region.Inflate(aWM, aMargin);
312 0 :
313 : // Don't store rectangles with negative margin-box width or height in
314 : // the float manager; it can't deal with them.
315 0 : if (region.ISize(aWM) < 0) {
316 0 : // Preserve the right margin-edge for left floats and the left
317 0 : // margin-edge for right floats
318 0 : const nsStyleDisplay* display = aFloat->StyleDisplay();
319 : StyleFloat floatStyle = display->PhysicalFloats(aWM);
320 0 : if ((StyleFloat::Left == floatStyle) == aWM.IsBidiLTR()) {
321 : region.IStart(aWM) = region.IEnd(aWM);
322 0 : }
323 0 : region.ISize(aWM) = 0;
324 : }
325 0 : if (region.BSize(aWM) < 0) {
326 : region.BSize(aWM) = 0;
327 : }
328 : return region;
329 : }
330 :
331 0 : NS_DECLARE_FRAME_PROPERTY_DELETABLE(FloatRegionProperty, nsMargin)
332 :
333 : LogicalRect
334 0 : nsFloatManager::GetRegionFor(WritingMode aWM, nsIFrame* aFloat,
335 0 : const nsSize& aContainerSize)
336 0 : {
337 0 : LogicalRect region = aFloat->GetLogicalRect(aWM, aContainerSize);
338 0 : void* storedRegion = aFloat->GetProperty(FloatRegionProperty());
339 : if (storedRegion) {
340 0 : nsMargin margin = *static_cast<nsMargin*>(storedRegion);
341 : region.Inflate(aWM, LogicalMargin(aWM, margin));
342 : }
343 : return region;
344 0 : }
345 :
346 : void
347 : nsFloatManager::StoreRegionFor(WritingMode aWM, nsIFrame* aFloat,
348 0 : const LogicalRect& aRegion,
349 0 : const nsSize& aContainerSize)
350 0 : {
351 0 : nsRect region = aRegion.GetPhysicalRect(aWM, aContainerSize);
352 : nsRect rect = aFloat->GetRect();
353 : if (region.IsEqualEdges(rect)) {
354 0 : aFloat->DeleteProperty(FloatRegionProperty());
355 0 : }
356 0 : else {
357 0 : nsMargin* storedMargin = aFloat->GetProperty(FloatRegionProperty());
358 : if (!storedMargin) {
359 0 : storedMargin = new nsMargin();
360 : aFloat->SetProperty(FloatRegionProperty(), storedMargin);
361 0 : }
362 : *storedMargin = region - rect;
363 : }
364 0 : }
365 :
366 0 : nsresult
367 : nsFloatManager::RemoveTrailingRegions(nsIFrame* aFrameList)
368 : {
369 : if (!aFrameList) {
370 : return NS_OK;
371 : }
372 : // This could be a good bit simpler if we could guarantee that the
373 0 : // floats given were at the end of our list, so we could just search
374 : // for the head of aFrameList. (But we can't;
375 0 : // layout/reftests/bugs/421710-1.html crashes.)
376 0 : nsTHashtable<nsPtrHashKey<nsIFrame> > frameSet(1);
377 :
378 : for (nsIFrame* f = aFrameList; f; f = f->GetNextSibling()) {
379 0 : frameSet.PutEntry(f);
380 0 : }
381 0 :
382 : uint32_t newLength = mFloats.Length();
383 : while (newLength > 0) {
384 : if (!frameSet.Contains(mFloats[newLength - 1].mFrame)) {
385 : break;
386 0 : }
387 : --newLength;
388 : }
389 0 : mFloats.TruncateLength(newLength);
390 0 :
391 : #ifdef DEBUG
392 : for (uint32_t i = 0; i < mFloats.Length(); ++i) {
393 : NS_ASSERTION(!frameSet.Contains(mFloats[i].mFrame),
394 : "Frame region deletion was requested but we couldn't delete it");
395 0 : }
396 : #endif
397 :
398 : return NS_OK;
399 72 : }
400 :
401 72 : void
402 : nsFloatManager::PushState(SavedState* aState)
403 : {
404 : MOZ_ASSERT(aState, "Need a place to save state");
405 :
406 : // This is a cheap push implementation, which
407 : // only saves the (x,y) and last frame in the mFrameInfoMap
408 : // which is enough info to get us back to where we should be
409 : // when pop is called.
410 : //
411 : // This push/pop mechanism is used to undo any
412 : // floats that were added during the unconstrained reflow
413 : // in nsBlockReflowContext::DoReflowBlock(). (See bug 96736)
414 : //
415 : // It should also be noted that the state for mFloatDamage is
416 : // intentionally not saved or restored in PushState() and PopState(),
417 : // since that could lead to bugs where damage is missed/dropped when
418 : // we move from position A to B (during the intermediate incremental
419 : // reflow mentioned above) and then from B to C during the subsequent
420 72 : // reflow. In the typical case A and C will be the same, but not always.
421 0 : // Allowing mFloatDamage to accumulate the damage incurred during both
422 72 : // reflows ensures that nothing gets missed.
423 0 : aState->mLineLeft = mLineLeft;
424 0 : aState->mBlockStart = mBlockStart;
425 0 : aState->mPushedLeftFloatPastBreak = mPushedLeftFloatPastBreak;
426 0 : aState->mPushedRightFloatPastBreak = mPushedRightFloatPastBreak;
427 0 : aState->mSplitLeftFloatAcrossBreak = mSplitLeftFloatAcrossBreak;
428 : aState->mSplitRightFloatAcrossBreak = mSplitRightFloatAcrossBreak;
429 : aState->mFloatInfoCount = mFloats.Length();
430 0 : }
431 :
432 0 : void
433 : nsFloatManager::PopState(SavedState* aState)
434 0 : {
435 0 : MOZ_ASSERT(aState, "No state to restore?");
436 0 :
437 0 : mLineLeft = aState->mLineLeft;
438 0 : mBlockStart = aState->mBlockStart;
439 0 : mPushedLeftFloatPastBreak = aState->mPushedLeftFloatPastBreak;
440 : mPushedRightFloatPastBreak = aState->mPushedRightFloatPastBreak;
441 0 : mSplitLeftFloatAcrossBreak = aState->mSplitLeftFloatAcrossBreak;
442 : mSplitRightFloatAcrossBreak = aState->mSplitRightFloatAcrossBreak;
443 0 :
444 0 : NS_ASSERTION(aState->mFloatInfoCount <= mFloats.Length(),
445 : "somebody misused PushState/PopState");
446 : mFloats.TruncateLength(aState->mFloatInfoCount);
447 0 : }
448 :
449 0 : nscoord
450 : nsFloatManager::GetLowestFloatTop() const
451 : {
452 0 : if (mPushedLeftFloatPastBreak || mPushedRightFloatPastBreak) {
453 : return nscoord_MAX;
454 : }
455 0 : if (!HasAnyFloats()) {
456 : return nscoord_MIN;
457 : }
458 : return mFloats[mFloats.Length() -1].BStart() - mBlockStart;
459 : }
460 0 :
461 : #ifdef DEBUG_FRAME_DUMP
462 0 : void
463 0 : DebugListFloatManager(const nsFloatManager *aFloatManager)
464 : {
465 : aFloatManager->List(stdout);
466 0 : }
467 :
468 0 : nsresult
469 : nsFloatManager::List(FILE* out) const
470 : {
471 0 : if (!HasAnyFloats())
472 0 : return NS_OK;
473 :
474 0 : for (uint32_t i = 0; i < mFloats.Length(); ++i) {
475 : const FloatInfo &fi = mFloats[i];
476 0 : fprintf_stderr(out, "Float %u: frame=%p rect={%d,%d,%d,%d} BEnd={l:%d, r:%d}\n",
477 : i, static_cast<void*>(fi.mFrame),
478 : fi.LineLeft(), fi.BStart(), fi.ISize(), fi.BSize(),
479 : fi.mLeftBEnd, fi.mRightBEnd);
480 : }
481 : return NS_OK;
482 : }
483 0 : #endif
484 :
485 : nscoord
486 0 : nsFloatManager::ClearFloats(nscoord aBCoord, StyleClear aBreakType,
487 : uint32_t aFlags) const
488 : {
489 0 : if (!(aFlags & DONT_CLEAR_PUSHED_FLOATS) && ClearContinues(aBreakType)) {
490 : return nscoord_MAX;
491 : }
492 : if (!HasAnyFloats()) {
493 0 : return aBCoord;
494 : }
495 0 :
496 0 : nscoord blockEnd = aBCoord + mBlockStart;
497 :
498 0 : const FloatInfo &tail = mFloats[mFloats.Length() - 1];
499 0 : switch (aBreakType) {
500 0 : case StyleClear::Both:
501 : blockEnd = std::max(blockEnd, tail.mLeftBEnd);
502 0 : blockEnd = std::max(blockEnd, tail.mRightBEnd);
503 0 : break;
504 : case StyleClear::Left:
505 0 : blockEnd = std::max(blockEnd, tail.mLeftBEnd);
506 0 : break;
507 : case StyleClear::Right:
508 : blockEnd = std::max(blockEnd, tail.mRightBEnd);
509 : break;
510 : default:
511 : // Do nothing
512 0 : break;
513 : }
514 0 :
515 : blockEnd -= mBlockStart;
516 :
517 : return blockEnd;
518 0 : }
519 :
520 0 : bool
521 0 : nsFloatManager::ClearContinues(StyleClear aBreakType) const
522 0 : {
523 0 : return ((mPushedLeftFloatPastBreak || mSplitLeftFloatAcrossBreak) &&
524 0 : (aBreakType == StyleClear::Both ||
525 0 : aBreakType == StyleClear::Left)) ||
526 : ((mPushedRightFloatPastBreak || mSplitRightFloatAcrossBreak) &&
527 : (aBreakType == StyleClear::Both ||
528 : aBreakType == StyleClear::Right));
529 : }
530 :
531 : /////////////////////////////////////////////////////////////////////////////
532 : // ShapeInfo is an abstract class for implementing all the shapes in CSS
533 : // Shapes Module. A subclass needs to override all the methods to adjust
534 : // the flow area with respect to its shape.
535 : //
536 : class nsFloatManager::ShapeInfo
537 : {
538 : public:
539 : virtual ~ShapeInfo() {}
540 :
541 : virtual nscoord LineLeft(const nscoord aBStart,
542 : const nscoord aBEnd) const = 0;
543 : virtual nscoord LineRight(const nscoord aBStart,
544 : const nscoord aBEnd) const = 0;
545 : virtual nscoord BStart() const = 0;
546 : virtual nscoord BEnd() const = 0;
547 : virtual bool IsEmpty() const = 0;
548 :
549 : // Does this shape possibly get inline narrower in the BStart() to BEnd()
550 : // span when proceeding in the block direction? This is false for unrounded
551 : // rectangles that span all the way to BEnd(), but could be true for other
552 : // shapes. Note that we don't care if the BEnd() falls short of the margin
553 : // rect -- the ShapeInfo can only affect float behavior in the span between
554 : // BStart() and BEnd().
555 : virtual bool MayNarrowInBlockDirection() const = 0;
556 :
557 : // Translate the current origin by the specified offsets.
558 : virtual void Translate(nscoord aLineLeft, nscoord aBlockStart) = 0;
559 :
560 : static LogicalRect ComputeShapeBoxRect(
561 : const StyleShapeSource& aShapeOutside,
562 : nsIFrame* const aFrame,
563 : const LogicalRect& aMarginRect,
564 : WritingMode aWM);
565 0 :
566 : // Convert the LogicalRect to the special logical coordinate space used
567 : // in float manager.
568 : static nsRect ConvertToFloatLogical(const LogicalRect& aRect,
569 : WritingMode aWM,
570 0 : const nsSize& aContainerSize)
571 : {
572 : return nsRect(aRect.LineLeft(aWM, aContainerSize), aRect.BStart(aWM),
573 : aRect.ISize(aWM), aRect.BSize(aWM));
574 : }
575 :
576 : static UniquePtr<ShapeInfo> CreateShapeBox(
577 : nsIFrame* const aFrame,
578 : nscoord aShapeMargin,
579 : const LogicalRect& aShapeBoxRect,
580 : WritingMode aWM,
581 : const nsSize& aContainerSize);
582 :
583 : static UniquePtr<ShapeInfo> CreateBasicShape(
584 : const UniquePtr<StyleBasicShape>& aBasicShape,
585 : nscoord aShapeMargin,
586 : nsIFrame* const aFrame,
587 : const LogicalRect& aShapeBoxRect,
588 : const LogicalRect& aMarginRect,
589 : WritingMode aWM,
590 : const nsSize& aContainerSize);
591 :
592 : static UniquePtr<ShapeInfo> CreateInset(
593 : const UniquePtr<StyleBasicShape>& aBasicShape,
594 : nscoord aShapeMargin,
595 : nsIFrame* aFrame,
596 : const LogicalRect& aShapeBoxRect,
597 : WritingMode aWM,
598 : const nsSize& aContainerSize);
599 :
600 : static UniquePtr<ShapeInfo> CreateCircleOrEllipse(
601 : const UniquePtr<StyleBasicShape>& aBasicShape,
602 : nscoord aShapeMargin,
603 : nsIFrame* const aFrame,
604 : const LogicalRect& aShapeBoxRect,
605 : WritingMode aWM,
606 : const nsSize& aContainerSize);
607 :
608 : static UniquePtr<ShapeInfo> CreatePolygon(
609 : const UniquePtr<StyleBasicShape>& aBasicShape,
610 : nscoord aShapeMargin,
611 : nsIFrame* const aFrame,
612 : const LogicalRect& aShapeBoxRect,
613 : const LogicalRect& aMarginRect,
614 : WritingMode aWM,
615 : const nsSize& aContainerSize);
616 :
617 : static UniquePtr<ShapeInfo> CreateImageShape(
618 : const UniquePtr<nsStyleImage>& aShapeImage,
619 : float aShapeImageThreshold,
620 : nscoord aShapeMargin,
621 : nsIFrame* const aFrame,
622 : const LogicalRect& aMarginRect,
623 : WritingMode aWM,
624 : const nsSize& aContainerSize);
625 :
626 : protected:
627 : // Compute the minimum line-axis difference between the bounding shape
628 : // box and its rounded corner within the given band (block-axis region).
629 : // This is used as a helper function to compute the LineRight() and
630 : // LineLeft(). See the picture in the implementation for an example.
631 : // RadiusL and RadiusB stand for radius on the line-axis and block-axis.
632 : //
633 : // Returns radius-x diff on the line-axis, or 0 if there's no rounded
634 : // corner within the given band.
635 : static nscoord ComputeEllipseLineInterceptDiff(
636 : const nscoord aShapeBoxBStart, const nscoord aShapeBoxBEnd,
637 : const nscoord aBStartCornerRadiusL, const nscoord aBStartCornerRadiusB,
638 : const nscoord aBEndCornerRadiusL, const nscoord aBEndCornerRadiusB,
639 : const nscoord aBandBStart, const nscoord aBandBEnd);
640 :
641 : static nscoord XInterceptAtY(const nscoord aY, const nscoord aRadiusX,
642 : const nscoord aRadiusY);
643 :
644 : // Convert the physical point to the special logical coordinate space
645 : // used in float manager.
646 : static nsPoint ConvertToFloatLogical(const nsPoint& aPoint,
647 : WritingMode aWM,
648 : const nsSize& aContainerSize);
649 :
650 : // Convert the half corner radii (nscoord[8]) to the special logical
651 : // coordinate space used in float manager.
652 : static UniquePtr<nscoord[]> ConvertToFloatLogical(
653 : const nscoord aRadii[8],
654 : WritingMode aWM);
655 :
656 : // Some ShapeInfo subclasses may define their float areas in intervals.
657 : // Each interval is a rectangle that is one device pixel deep in the block
658 : // axis. The values are stored as block edges in the y coordinates,
659 : // and inline edges as the x coordinates. Interval arrays should be sorted
660 : // on increasing y values. This function uses a binary search to find the
661 : // first interval that contains aTargetY. If no such interval exists, this
662 : // function returns aIntervals.Length().
663 : static size_t MinIntervalIndexContainingY(const nsTArray<nsRect>& aIntervals,
664 : const nscoord aTargetY);
665 :
666 : // This interval function is designed to handle the arguments to ::LineLeft()
667 : // and LineRight() and interpret them for the supplied aIntervals.
668 : static nscoord LineEdge(const nsTArray<nsRect>& aIntervals,
669 : const nscoord aBStart,
670 : const nscoord aBEnd,
671 : bool aIsLineLeft);
672 :
673 : // These types, constants, and functions are useful for ShapeInfos that
674 : // allocate a distance field. Efficient distance field calculations use
675 : // integer values that are 5X the Euclidean distance. MAX_MARGIN_5X is the
676 : // largest possible margin that we can calculate (in 5X integer dev pixels),
677 : // given these constraints.
678 : typedef uint16_t dfType;
679 : static const dfType MAX_CHAMFER_VALUE;
680 : static const dfType MAX_MARGIN;
681 : static const dfType MAX_MARGIN_5X;
682 :
683 : // This function returns a typed, overflow-safe value of aShapeMargin in
684 : // 5X integer dev pixels.
685 : static dfType CalcUsedShapeMargin5X(nscoord aShapeMargin,
686 : int32_t aAppUnitsPerDevPixel);
687 : };
688 :
689 : const nsFloatManager::ShapeInfo::dfType
690 : nsFloatManager::ShapeInfo::MAX_CHAMFER_VALUE = 11;
691 :
692 : const nsFloatManager::ShapeInfo::dfType
693 : nsFloatManager::ShapeInfo::MAX_MARGIN = (std::numeric_limits<dfType>::max() -
694 : MAX_CHAMFER_VALUE) / 5;
695 :
696 : const nsFloatManager::ShapeInfo::dfType
697 : nsFloatManager::ShapeInfo::MAX_MARGIN_5X = MAX_MARGIN * 5;
698 :
699 : /////////////////////////////////////////////////////////////////////////////
700 : // EllipseShapeInfo
701 0 : //
702 : // Implements shape-outside: circle() and shape-outside: ellipse().
703 : //
704 : class nsFloatManager::EllipseShapeInfo final : public nsFloatManager::ShapeInfo
705 : {
706 : public:
707 : // Construct the float area using math to calculate the shape boundary.
708 : // This is the fast path and should be used when shape-margin is negligible,
709 : // or when the two values of aRadii are roughly equal. Those two conditions
710 : // are defined by ShapeMarginIsNegligible() and RadiiAreRoughlyEqual(). In
711 : // those cases, we can conveniently represent the entire float area using
712 : // an ellipse.
713 : EllipseShapeInfo(const nsPoint& aCenter,
714 : const nsSize& aRadii,
715 : nscoord aShapeMargin);
716 :
717 : // Construct the float area using rasterization to calculate the shape
718 : // boundary. This constructor accounts for the fact that applying
719 : // 'shape-margin' to an ellipse produces a shape that is not mathematically
720 : // representable as an ellipse.
721 : EllipseShapeInfo(const nsPoint& aCenter,
722 : const nsSize& aRadii,
723 : nscoord aShapeMargin,
724 : int32_t aAppUnitsPerDevPixel);
725 :
726 : static bool ShapeMarginIsNegligible(nscoord aShapeMargin) {
727 : // For now, only return true for a shape-margin of 0. In the future, if
728 : // we want to enable use of the fast-path constructor more often, this
729 : // limit could be increased;
730 : static const nscoord SHAPE_MARGIN_NEGLIGIBLE_MAX(0);
731 : return aShapeMargin <= SHAPE_MARGIN_NEGLIGIBLE_MAX;
732 : }
733 :
734 : static bool RadiiAreRoughlyEqual(const nsSize& aRadii) {
735 : // For now, only return true when we are exactly equal. In the future, if
736 0 : // we want to enable use of the fast-path constructor more often, this
737 : // could be generalized to allow radii that are in some close proportion
738 : // to each other.
739 : return aRadii.width == aRadii.height;
740 : }
741 : nscoord LineEdge(const nscoord aBStart,
742 : const nscoord aBEnd,
743 : bool aLeft) const;
744 : nscoord LineLeft(const nscoord aBStart,
745 0 : const nscoord aBEnd) const override;
746 0 : nscoord LineRight(const nscoord aBStart,
747 : const nscoord aBEnd) const override;
748 0 : nscoord BStart() const override {
749 0 : return mCenter.y - mRadii.height - mShapeMargin;
750 : }
751 0 : nscoord BEnd() const override {
752 : return mCenter.y + mRadii.height + mShapeMargin;
753 : }
754 : bool IsEmpty() const override {
755 0 : // An EllipseShapeInfo is never empty, because an ellipse or circle with
756 : // a zero radius acts like a point, and an ellipse with one zero radius
757 0 : // acts like a line.
758 0 : return false;
759 : }
760 : bool MayNarrowInBlockDirection() const override {
761 0 : return true;
762 : }
763 0 :
764 : void Translate(nscoord aLineLeft, nscoord aBlockStart) override
765 0 : {
766 0 : mCenter.MoveBy(aLineLeft, aBlockStart);
767 :
768 0 : for (nsRect& interval : mIntervals) {
769 : interval.MoveBy(aLineLeft, aBlockStart);
770 : }
771 : }
772 :
773 : private:
774 : // The position of the center of the ellipse. The coordinate space is the
775 : // same as FloatInfo::mRect.
776 : nsPoint mCenter;
777 : // The radii of the ellipse in app units. The width and height represent
778 : // the line-axis and block-axis radii of the ellipse.
779 : nsSize mRadii;
780 : // The shape-margin of the ellipse in app units. If this value is greater
781 : // than zero, then we calculate the bounds of the ellipse + margin using
782 : // numerical methods and store the values in mIntervals.
783 : nscoord mShapeMargin;
784 :
785 : // An interval is slice of the float area defined by this EllipseShapeInfo.
786 : // Each interval is a rectangle that is one pixel deep in the block
787 : // axis. The values are stored as block edges in the y coordinates,
788 : // and inline edges as the x coordinates.
789 :
790 : // The intervals are stored in ascending order on y.
791 0 : nsTArray<nsRect> mIntervals;
792 : };
793 0 :
794 : nsFloatManager::EllipseShapeInfo::EllipseShapeInfo(const nsPoint& aCenter,
795 : const nsSize& aRadii,
796 0 : nscoord aShapeMargin)
797 : : mCenter(aCenter)
798 0 : , mRadii(aRadii)
799 : , mShapeMargin(0) // We intentionally ignore the value of aShapeMargin here.
800 : {
801 : MOZ_ASSERT(RadiiAreRoughlyEqual(aRadii) ||
802 : ShapeMarginIsNegligible(aShapeMargin),
803 : "This constructor should only be called when margin is "
804 : "negligible or radii are roughly equal.");
805 0 :
806 0 : // We add aShapeMargin into the radii, and we earlier stored a mShapeMargin
807 0 : // of zero.
808 : mRadii.width += aShapeMargin;
809 0 : mRadii.height += aShapeMargin;
810 : }
811 :
812 0 : nsFloatManager::EllipseShapeInfo::EllipseShapeInfo(const nsPoint& aCenter,
813 : const nsSize& aRadii,
814 : nscoord aShapeMargin,
815 0 : int32_t aAppUnitsPerDevPixel)
816 : : mCenter(aCenter)
817 0 : , mRadii(aRadii)
818 : , mShapeMargin(aShapeMargin)
819 : {
820 0 : if (RadiiAreRoughlyEqual(aRadii) || ShapeMarginIsNegligible(aShapeMargin)) {
821 0 : // Mimic the behavior of the simple constructor, by adding aShapeMargin
822 0 : // into the radii, and then storing mShapeMargin of zero.
823 0 : mRadii.width += mShapeMargin;
824 : mRadii.height += mShapeMargin;
825 : mShapeMargin = 0;
826 : return;
827 : }
828 :
829 : // We have to calculate a distance field from the ellipse edge, then build
830 : // intervals based on pixels with less than aShapeMargin distance to an
831 : // edge pixel.
832 :
833 : // mCenter and mRadii have already been translated into logical coordinates.
834 : // x = inline, y = block. Due to symmetry, we only need to calculate the
835 : // distance field for one quadrant of the ellipse. We choose the positive-x,
836 : // positive-y quadrant (the lower right quadrant in horizontal-tb writing
837 : // mode). We choose this quadrant because it allows us to traverse our
838 : // distance field in memory order, which is more cache efficient.
839 : // When we apply these intervals in LineLeft() and LineRight(), we
840 : // account for block ranges that hit other quadrants, or hit multiple
841 : // quadrants.
842 :
843 : // Given this setup, computing the distance field is a one-pass O(n)
844 : // operation that runs from block top-to-bottom, inline left-to-right. We
845 : // use a chamfer 5-7-11 5x5 matrix to compute minimum distance to an edge
846 : // pixel. This integer math computation is reasonably close to the true
847 : // Euclidean distance. The distances will be approximately 5x the true
848 0 : // distance, quantized in integer units. The 5x is factored away in the
849 : // comparison which builds the intervals.
850 : dfType usedMargin5X = CalcUsedShapeMargin5X(aShapeMargin,
851 : aAppUnitsPerDevPixel);
852 :
853 : // Calculate the bounds of one quadrant of the ellipse, in integer device
854 0 : // pixels. These bounds are equal to the rectangle defined by the radii,
855 0 : // plus the shape-margin value in both dimensions.
856 : const LayoutDeviceIntSize bounds =
857 : LayoutDevicePixel::FromAppUnitsRounded(mRadii, aAppUnitsPerDevPixel) +
858 : LayoutDeviceIntSize(usedMargin5X / 5, usedMargin5X / 5);
859 :
860 : // Since our distance field is computed with a 5x5 neighborhood, but only
861 : // looks in the negative block and negative inline directions, it is
862 : // effectively a 3x3 neighborhood. We need to expand our distance field
863 : // outwards by a further 2 pixels in both axes (on the minimum block edge
864 : // and the minimum inline edge). We call this edge area the expanded region.
865 :
866 : static const uint32_t iExpand = 2;
867 : static const uint32_t bExpand = 2;
868 :
869 : // Clamp the size of our distance field sizes to prevent multiplication
870 0 : // overflow.
871 0 : static const uint32_t DF_SIDE_MAX =
872 0 : floor(sqrt((double)(std::numeric_limits<int32_t>::max())));
873 0 : const uint32_t iSize = std::min(bounds.width + iExpand, DF_SIDE_MAX);
874 : const uint32_t bSize = std::min(bounds.height + bExpand, DF_SIDE_MAX);
875 : auto df = MakeUniqueFallible<dfType[]>(iSize * bSize);
876 : if (!df) {
877 : // Without a distance field, we can't reason about the float area.
878 : return;
879 : }
880 :
881 : // Single pass setting distance field, in positive block direction, three
882 : // cases:
883 : // 1) Expanded region pixel: set to MAX_MARGIN_5X.
884 : // 2) Pixel within the ellipse: set to 0.
885 0 : // 3) Other pixel: set to minimum neighborhood distance value, computed
886 0 : // with 5-7-11 chamfer.
887 0 :
888 0 : for (uint32_t b = 0; b < bSize; ++b) {
889 : bool bIsInExpandedRegion(b < bExpand);
890 : nscoord bInAppUnits = (b - bExpand) * aAppUnitsPerDevPixel;
891 : bool bIsMoreThanEllipseBEnd(bInAppUnits > mRadii.height);
892 :
893 : // Find the i intercept of the ellipse edge for this block row, and
894 : // adjust it to compensate for the expansion of the inline dimension.
895 : // If we're in the expanded region, or if we're using a b that's more
896 : // than the bEnd of the ellipse, the intercept is nscoord_MIN.
897 : // We have one other special case to consider: when the ellipse has no
898 : // height. In that case we treat the bInAppUnits == 0 case as
899 0 : // intercepting at the width of the ellipse. All other cases solve
900 0 : // the intersection mathematically.
901 0 : const int32_t iIntercept =
902 0 : (bIsInExpandedRegion || bIsMoreThanEllipseBEnd) ? nscoord_MIN :
903 : iExpand + NSAppUnitsToIntPixels(
904 0 : (!!mRadii.height || bInAppUnits) ?
905 : XInterceptAtY(bInAppUnits, mRadii.width, mRadii.height) :
906 : mRadii.width,
907 0 : aAppUnitsPerDevPixel);
908 :
909 0 : // Set iMax in preparation for this block row.
910 0 : int32_t iMax = iIntercept;
911 0 :
912 : for (uint32_t i = 0; i < iSize; ++i) {
913 : const uint32_t index = i + b * iSize;
914 : MOZ_ASSERT(index < (iSize * bSize),
915 0 : "Our distance field index should be in-bounds.");
916 :
917 : // Handle our three cases, in order.
918 0 : if (i < iExpand ||
919 0 : bIsInExpandedRegion) {
920 : // Case 1: Expanded reqion pixel.
921 : df[index] = MAX_MARGIN_5X;
922 : } else if ((int32_t)i <= iIntercept) {
923 0 : // Case 2: Pixel within the ellipse, or just outside the edge of it.
924 : // Having a positive height indicates that there's an area we can
925 : // be inside of.
926 : df[index] = (!!mRadii.height) ? 0 : 5;
927 : } else {
928 : // Case 3: Other pixel.
929 :
930 : // Backward-looking neighborhood distance from target pixel X
931 : // with chamfer 5-7-11 looks like:
932 : //
933 : // +--+--+--+
934 : // | |11| |
935 : // +--+--+--+
936 : // |11| 7| 5|
937 : // +--+--+--+
938 : // | | 5| X|
939 : // +--+--+--+
940 0 : //
941 : // X should be set to the minimum of the values of all of the numbered
942 : // neighbors summed with the value in that chamfer cell.
943 : MOZ_ASSERT(index - iSize - 2 < (iSize * bSize) &&
944 : index - (iSize * 2) - 1 < (iSize * bSize),
945 0 : "Our distance field most extreme indices should be "
946 0 : "in-bounds.");
947 0 :
948 0 : df[index] = std::min<dfType>(df[index - 1] + 5,
949 0 : std::min<dfType>(df[index - iSize] + 5,
950 : std::min<dfType>(df[index - iSize - 1] + 7,
951 : std::min<dfType>(df[index - iSize - 2] + 11,
952 : df[index - (iSize * 2) - 1] + 11))));
953 0 :
954 0 : // Check the df value and see if it's less than or equal to the
955 : // usedMargin5X value.
956 : if (df[index] <= usedMargin5X) {
957 : MOZ_ASSERT(iMax < (int32_t)i);
958 : iMax = i;
959 : } else {
960 : // Since we're computing the bottom-right quadrant, there's no way
961 : // for a later i value in this row to be within the usedMargin5X
962 : // value. Likewise, every row beyond us will encounter this
963 : // condition with an i value less than or equal to our i value now.
964 : // Since our chamfer only looks upward and leftward, we can stop
965 : // calculating for the rest of the row, because the distance field
966 : // values there will never be looked at in a later row's chamfer
967 : // calculation.
968 : break;
969 : }
970 : }
971 : }
972 :
973 0 : // It's very likely, though not guaranteed that we will find an pixel
974 : // within the shape-margin distance for each block row. This may not
975 : // always be true due to rounding errors.
976 0 : if (iMax > nscoord_MIN) {
977 : // Origin for this interval is at the center of the ellipse, adjusted
978 : // in the positive block direction by bInAppUnits.
979 0 : nsPoint origin(aCenter.x, aCenter.y + bInAppUnits);
980 0 : // Size is an inline iMax plus 1 (to account for the whole pixel) dev
981 0 : // pixels, by 1 block dev pixel. We convert this to app units.
982 : nsSize size((iMax - iExpand + 1) * aAppUnitsPerDevPixel,
983 : aAppUnitsPerDevPixel);
984 : mIntervals.AppendElement(nsRect(origin, size));
985 : }
986 : }
987 0 : }
988 :
989 : nscoord
990 : nsFloatManager::EllipseShapeInfo::LineEdge(const nscoord aBStart,
991 : const nscoord aBEnd,
992 0 : bool aIsLineLeft) const
993 : {
994 0 : // If no mShapeMargin, just compute the edge using math.
995 : if (mShapeMargin == 0) {
996 0 : nscoord lineDiff =
997 0 : ComputeEllipseLineInterceptDiff(BStart(), BEnd(),
998 0 : mRadii.width, mRadii.height,
999 0 : mRadii.width, mRadii.height,
1000 : aBStart, aBEnd);
1001 : return mCenter.x + (aIsLineLeft ? (-mRadii.width + lineDiff) :
1002 : (mRadii.width - lineDiff));
1003 0 : }
1004 0 :
1005 0 : // We are checking against our intervals. Make sure we have some.
1006 : if (mIntervals.IsEmpty()) {
1007 : NS_WARNING("With mShapeMargin > 0, we can't proceed without intervals.");
1008 : return aIsLineLeft ? nscoord_MAX : nscoord_MIN;
1009 : }
1010 :
1011 : // Map aBStart and aBEnd into our intervals. Our intervals are calculated
1012 0 : // for the lower-right quadrant (in terms of horizontal-tb writing mode).
1013 0 : // If aBStart and aBEnd span the center of the ellipse, then we know we
1014 0 : // are at the maximum displacement from the center.
1015 0 : bool bStartIsAboveCenter = (aBStart < mCenter.y);
1016 0 : bool bEndIsBelowOrAtCenter = (aBEnd >= mCenter.y);
1017 : if (bStartIsAboveCenter && bEndIsBelowOrAtCenter) {
1018 : return mCenter.x + (aIsLineLeft ? (-mRadii.width - mShapeMargin) :
1019 : (mRadii.width + mShapeMargin));
1020 : }
1021 :
1022 : // aBStart and aBEnd don't span the center. Since the intervals are
1023 : // strictly wider approaching the center (the start of the mIntervals
1024 : // array), we only need to find the interval at the block value closest to
1025 : // the center. We find the min of aBStart, aBEnd, and their reflections --
1026 : // whichever two of them are within the lower-right quadrant. When we
1027 : // reflect from the upper-right quadrant to the lower-right, we have to
1028 : // subtract 1 from the reflection, to account that block values are always
1029 : // addressed from the leading block edge.
1030 :
1031 : // The key example is when we check with aBStart == aBEnd at the top of the
1032 : // intervals. That block line would be considered contained in the
1033 0 : // intervals (though it has no height), but its reflection would not be
1034 0 : // within the intervals unless we subtract 1.
1035 : nscoord bSmallestWithinIntervals = std::min(
1036 0 : bStartIsAboveCenter ? aBStart + (mCenter.y - aBStart) * 2 - 1 : aBStart,
1037 : bEndIsBelowOrAtCenter ? aBEnd : aBEnd + (mCenter.y - aBEnd) * 2 - 1);
1038 :
1039 : MOZ_ASSERT(bSmallestWithinIntervals >= mCenter.y &&
1040 0 : bSmallestWithinIntervals < BEnd(),
1041 0 : "We should have a block value within the float area.");
1042 0 :
1043 : size_t index = MinIntervalIndexContainingY(mIntervals,
1044 : bSmallestWithinIntervals);
1045 : if (index >= mIntervals.Length()) {
1046 : // This indicates that our intervals don't cover the block value
1047 : // bSmallestWithinIntervals. This can happen when rounding error in the
1048 : // distance field calculation resulted in the last block pixel row not
1049 : // contributing to the float area. As long as we're within one block pixel
1050 0 : // past the last interval, this is an expected outcome.
1051 0 : #ifdef DEBUG
1052 0 : nscoord onePixelPastLastInterval =
1053 : mIntervals[mIntervals.Length() - 1].YMost() +
1054 : mIntervals[mIntervals.Length() - 1].Height();
1055 : NS_WARNING_ASSERTION(bSmallestWithinIntervals < onePixelPastLastInterval,
1056 0 : "We should have found a matching interval for this "
1057 : "block value.");
1058 : #endif
1059 : return aIsLineLeft ? nscoord_MAX : nscoord_MIN;
1060 : }
1061 :
1062 : // The interval is storing the line right value. If aIsLineLeft is true,
1063 : // return the line right value reflected about the center. Since this is
1064 0 : // an inline measurement, it's just checking the distance to an edge, and
1065 0 : // not a collision with a specific pixel. For that reason, we don't need
1066 : // to subtract 1 from the reflection, as we did with the block reflection.
1067 : nscoord iLineRight = mIntervals[index].XMost();
1068 : return aIsLineLeft ? iLineRight - (iLineRight - mCenter.x) * 2
1069 : : iLineRight;
1070 0 : }
1071 :
1072 : nscoord
1073 0 : nsFloatManager::EllipseShapeInfo::LineLeft(const nscoord aBStart,
1074 : const nscoord aBEnd) const
1075 : {
1076 : return LineEdge(aBStart, aBEnd, true);
1077 0 : }
1078 :
1079 : nscoord
1080 0 : nsFloatManager::EllipseShapeInfo::LineRight(const nscoord aBStart,
1081 : const nscoord aBEnd) const
1082 : {
1083 : return LineEdge(aBStart, aBEnd, false);
1084 : }
1085 :
1086 : /////////////////////////////////////////////////////////////////////////////
1087 : // RoundedBoxShapeInfo
1088 0 : //
1089 : // Implements shape-outside: <shape-box> and shape-outside: inset().
1090 : //
1091 0 : class nsFloatManager::RoundedBoxShapeInfo final : public nsFloatManager::ShapeInfo
1092 : {
1093 0 : public:
1094 0 : RoundedBoxShapeInfo(const nsRect& aRect,
1095 0 : UniquePtr<nscoord[]> aRadii)
1096 0 : : mRect(aRect)
1097 : , mRadii(std::move(aRadii))
1098 : , mShapeMargin(0)
1099 : {}
1100 :
1101 : RoundedBoxShapeInfo(const nsRect& aRect,
1102 : UniquePtr<nscoord[]> aRadii,
1103 : nscoord aShapeMargin,
1104 : int32_t aAppUnitsPerDevPixel);
1105 :
1106 : nscoord LineLeft(const nscoord aBStart,
1107 0 : const nscoord aBEnd) const override;
1108 0 : nscoord LineRight(const nscoord aBStart,
1109 0 : const nscoord aBEnd) const override;
1110 : nscoord BStart() const override { return mRect.y; }
1111 : nscoord BEnd() const override { return mRect.YMost(); }
1112 : bool IsEmpty() const override {
1113 : // A RoundedBoxShapeInfo is never empty, because if it is collapsed to
1114 0 : // zero area, it acts like a point. If it is collapsed further, to become
1115 : // inside-out, it acts like a rect in the same shape as the inside-out
1116 0 : // rect.
1117 : return false;
1118 0 : }
1119 : bool MayNarrowInBlockDirection() const override {
1120 : // Only possible to narrow if there are non-null mRadii.
1121 0 : return !!mRadii;
1122 : }
1123 0 :
1124 : void Translate(nscoord aLineLeft, nscoord aBlockStart) override
1125 0 : {
1126 0 : mRect.MoveBy(aLineLeft, aBlockStart);
1127 :
1128 : if (mShapeMargin > 0) {
1129 0 : MOZ_ASSERT(mLogicalTopLeftCorner && mLogicalTopRightCorner &&
1130 0 : mLogicalBottomLeftCorner && mLogicalBottomRightCorner,
1131 0 : "If we have positive shape-margin, we should have corners.");
1132 0 : mLogicalTopLeftCorner->Translate(aLineLeft, aBlockStart);
1133 : mLogicalTopRightCorner->Translate(aLineLeft, aBlockStart);
1134 0 : mLogicalBottomLeftCorner->Translate(aLineLeft, aBlockStart);
1135 : mLogicalBottomRightCorner->Translate(aLineLeft, aBlockStart);
1136 0 : }
1137 0 : }
1138 0 :
1139 0 : static bool EachCornerHasBalancedRadii(const nscoord* aRadii) {
1140 0 : return (aRadii[eCornerTopLeftX] == aRadii[eCornerTopLeftY] &&
1141 : aRadii[eCornerTopRightX] == aRadii[eCornerTopRightY] &&
1142 : aRadii[eCornerBottomLeftX] == aRadii[eCornerBottomLeftY] &&
1143 : aRadii[eCornerBottomRightX] == aRadii[eCornerBottomRightY]);
1144 : }
1145 :
1146 : private:
1147 : // The rect of the rounded box shape in the float manager's coordinate
1148 : // space.
1149 : nsRect mRect;
1150 : // The half corner radii of the reference box. It's an nscoord[8] array
1151 : // in the float manager's coordinate space. If there are no radii, it's
1152 : // nullptr.
1153 : const UniquePtr<nscoord[]> mRadii;
1154 :
1155 : // A shape-margin value extends the boundaries of the float area. When our
1156 : // first constructor is used, it is for the creation of rounded boxes that
1157 : // can ignore shape-margin -- either because it was specified as zero or
1158 : // because the box shape and radii can be inflated to account for it. When
1159 : // our second constructor is used, we store the shape-margin value here.
1160 : const nscoord mShapeMargin;
1161 :
1162 : // If our second constructor is called (which implies mShapeMargin > 0),
1163 : // we will construct EllipseShapeInfo objects for each corner. We use the
1164 : // float logical naming here, where LogicalTopLeftCorner means the BStart
1165 : // LineLeft corner, and similarly for the other corners.
1166 : UniquePtr<EllipseShapeInfo> mLogicalTopLeftCorner;
1167 : UniquePtr<EllipseShapeInfo> mLogicalTopRightCorner;
1168 : UniquePtr<EllipseShapeInfo> mLogicalBottomLeftCorner;
1169 0 : UniquePtr<EllipseShapeInfo> mLogicalBottomRightCorner;
1170 : };
1171 :
1172 0 : nsFloatManager::RoundedBoxShapeInfo::RoundedBoxShapeInfo(const nsRect& aRect,
1173 : UniquePtr<nscoord[]> aRadii,
1174 0 : nscoord aShapeMargin,
1175 0 : int32_t aAppUnitsPerDevPixel)
1176 : : mRect(aRect)
1177 0 : , mRadii(std::move(aRadii))
1178 : , mShapeMargin(aShapeMargin)
1179 : {
1180 : MOZ_ASSERT(mShapeMargin > 0 && !EachCornerHasBalancedRadii(mRadii.get()),
1181 : "Slow constructor should only be used for for shape-margin > 0 "
1182 : "and radii with elliptical corners.");
1183 :
1184 0 : // Before we inflate mRect by mShapeMargin, construct each of our corners.
1185 0 : // If we do it in this order, it's a bit simpler to calculate the center
1186 0 : // of each of the corners.
1187 0 : mLogicalTopLeftCorner = MakeUnique<EllipseShapeInfo>(
1188 0 : nsPoint(mRect.X() + mRadii[eCornerTopLeftX],
1189 : mRect.Y() + mRadii[eCornerTopLeftY]),
1190 0 : nsSize(mRadii[eCornerTopLeftX], mRadii[eCornerTopLeftY]),
1191 0 : mShapeMargin, aAppUnitsPerDevPixel);
1192 0 :
1193 0 : mLogicalTopRightCorner = MakeUnique<EllipseShapeInfo>(
1194 0 : nsPoint(mRect.XMost() - mRadii[eCornerTopRightX],
1195 : mRect.Y() + mRadii[eCornerTopRightY]),
1196 0 : nsSize(mRadii[eCornerTopRightX], mRadii[eCornerTopRightY]),
1197 0 : mShapeMargin, aAppUnitsPerDevPixel);
1198 0 :
1199 0 : mLogicalBottomLeftCorner = MakeUnique<EllipseShapeInfo>(
1200 0 : nsPoint(mRect.X() + mRadii[eCornerBottomLeftX],
1201 : mRect.YMost() - mRadii[eCornerBottomLeftY]),
1202 0 : nsSize(mRadii[eCornerBottomLeftX], mRadii[eCornerBottomLeftY]),
1203 0 : mShapeMargin, aAppUnitsPerDevPixel);
1204 0 :
1205 0 : mLogicalBottomRightCorner = MakeUnique<EllipseShapeInfo>(
1206 0 : nsPoint(mRect.XMost() - mRadii[eCornerBottomRightX],
1207 : mRect.YMost() - mRadii[eCornerBottomRightY]),
1208 : nsSize(mRadii[eCornerBottomRightX], mRadii[eCornerBottomRightY]),
1209 0 : mShapeMargin, aAppUnitsPerDevPixel);
1210 0 :
1211 : // Now we inflate our mRect by mShapeMargin.
1212 : mRect.Inflate(mShapeMargin);
1213 0 : }
1214 :
1215 : nscoord
1216 0 : nsFloatManager::RoundedBoxShapeInfo::LineLeft(const nscoord aBStart,
1217 0 : const nscoord aBEnd) const
1218 0 : {
1219 : if (mShapeMargin == 0) {
1220 : if (!mRadii) {
1221 : return mRect.x;
1222 0 : }
1223 :
1224 0 : nscoord lineLeftDiff =
1225 0 : ComputeEllipseLineInterceptDiff(
1226 0 : mRect.y, mRect.YMost(),
1227 0 : mRadii[eCornerTopLeftX], mRadii[eCornerTopLeftY],
1228 : mRadii[eCornerBottomLeftX], mRadii[eCornerBottomLeftY],
1229 : aBStart, aBEnd);
1230 0 : return mRect.x + lineLeftDiff;
1231 : }
1232 :
1233 : MOZ_ASSERT(mLogicalTopLeftCorner && mLogicalBottomLeftCorner,
1234 0 : "If we have positive shape-margin, we should have corners.");
1235 0 :
1236 : // Determine if aBEnd is within our top corner.
1237 : if (aBEnd < mLogicalTopLeftCorner->BEnd()) {
1238 : return mLogicalTopLeftCorner->LineLeft(aBStart, aBEnd);
1239 0 : }
1240 0 :
1241 : // Determine if aBStart is within our bottom corner.
1242 : if (aBStart >= mLogicalBottomLeftCorner->BStart()) {
1243 : return mLogicalBottomLeftCorner->LineLeft(aBStart, aBEnd);
1244 : }
1245 :
1246 0 : // Either aBStart or aBEnd or both are within the flat part of our left
1247 : // edge. Because we've already inflated our mRect to encompass our
1248 : // mShapeMargin, we can just return the edge.
1249 : return mRect.X();
1250 0 : }
1251 :
1252 : nscoord
1253 0 : nsFloatManager::RoundedBoxShapeInfo::LineRight(const nscoord aBStart,
1254 0 : const nscoord aBEnd) const
1255 0 : {
1256 : if (mShapeMargin == 0) {
1257 : if (!mRadii) {
1258 : return mRect.XMost();
1259 0 : }
1260 :
1261 0 : nscoord lineRightDiff =
1262 0 : ComputeEllipseLineInterceptDiff(
1263 0 : mRect.y, mRect.YMost(),
1264 0 : mRadii[eCornerTopRightX], mRadii[eCornerTopRightY],
1265 : mRadii[eCornerBottomRightX], mRadii[eCornerBottomRightY],
1266 : aBStart, aBEnd);
1267 0 : return mRect.XMost() - lineRightDiff;
1268 : }
1269 :
1270 : MOZ_ASSERT(mLogicalTopRightCorner && mLogicalBottomRightCorner,
1271 0 : "If we have positive shape-margin, we should have corners.");
1272 0 :
1273 : // Determine if aBEnd is within our top corner.
1274 : if (aBEnd < mLogicalTopRightCorner->BEnd()) {
1275 : return mLogicalTopRightCorner->LineRight(aBStart, aBEnd);
1276 0 : }
1277 0 :
1278 : // Determine if aBStart is within our bottom corner.
1279 : if (aBStart >= mLogicalBottomRightCorner->BStart()) {
1280 : return mLogicalBottomRightCorner->LineRight(aBStart, aBEnd);
1281 : }
1282 :
1283 0 : // Either aBStart or aBEnd or both are within the flat part of our right
1284 : // edge. Because we've already inflated our mRect to encompass our
1285 : // mShapeMargin, we can just return the edge.
1286 : return mRect.XMost();
1287 : }
1288 :
1289 : /////////////////////////////////////////////////////////////////////////////
1290 : // PolygonShapeInfo
1291 0 : //
1292 : // Implements shape-outside: polygon().
1293 : //
1294 : class nsFloatManager::PolygonShapeInfo final : public nsFloatManager::ShapeInfo
1295 : {
1296 : public:
1297 : explicit PolygonShapeInfo(nsTArray<nsPoint>&& aVertices);
1298 : PolygonShapeInfo(nsTArray<nsPoint>&& aVertices,
1299 : nscoord aShapeMargin,
1300 : int32_t aAppUnitsPerDevPixel,
1301 : const nsRect& aMarginRect);
1302 :
1303 : nscoord LineLeft(const nscoord aBStart,
1304 0 : const nscoord aBEnd) const override;
1305 0 : nscoord LineRight(const nscoord aBStart,
1306 0 : const nscoord aBEnd) const override;
1307 : nscoord BStart() const override { return mBStart; }
1308 : nscoord BEnd() const override { return mBEnd; }
1309 : bool IsEmpty() const override {
1310 : // A PolygonShapeInfo is never empty, because the parser prevents us from
1311 0 : // creating a shape with no vertices. If we only have 1 vertex, the
1312 : // shape acts like a point. With 2 non-coincident vertices, the shape
1313 0 : // acts like a line.
1314 : return false;
1315 : }
1316 : bool MayNarrowInBlockDirection() const override { return true; }
1317 :
1318 : void Translate(nscoord aLineLeft, nscoord aBlockStart) override;
1319 :
1320 : private:
1321 : // Helper method for determining the mBStart and mBEnd based on the
1322 : // vertices' y extent.
1323 : void ComputeExtent();
1324 :
1325 : // Helper method for implementing LineLeft() and LineRight().
1326 : nscoord ComputeLineIntercept(
1327 : const nscoord aBStart,
1328 : const nscoord aBEnd,
1329 : nscoord (*aCompareOp) (std::initializer_list<nscoord>),
1330 : const nscoord aLineInterceptInitialValue) const;
1331 :
1332 : // Given a horizontal line y, and two points p1 and p2 forming a line
1333 : // segment L. Solve x for the intersection of y and L. This method
1334 : // assumes y and L do intersect, and L is *not* horizontal.
1335 : static nscoord XInterceptAtY(const nscoord aY,
1336 : const nsPoint& aP1,
1337 : const nsPoint& aP2);
1338 :
1339 : // The vertices of the polygon in the float manager's coordinate space.
1340 : nsTArray<nsPoint> mVertices;
1341 :
1342 : // An interval is slice of the float area defined by this PolygonShapeInfo.
1343 : // These are only generated and used in float area calculations for
1344 : // shape-margin > 0. Each interval is a rectangle that is one device pixel
1345 : // deep in the block axis. The values are stored as block edges in the y
1346 : // coordinates, and inline edges as the x coordinates.
1347 :
1348 : // The intervals are stored in ascending order on y.
1349 : nsTArray<nsRect> mIntervals;
1350 :
1351 : // Computed block start and block end value of the polygon shape. These
1352 : // initial values are set to correct values in ComputeExtent(), which is
1353 : // called from all constructors. Afterwards, mBStart is guaranteed to be
1354 : // less than or equal to mBEnd.
1355 : nscoord mBStart = nscoord_MAX;
1356 0 : nscoord mBEnd = nscoord_MIN;
1357 0 : };
1358 :
1359 0 : nsFloatManager::PolygonShapeInfo::PolygonShapeInfo(nsTArray<nsPoint>&& aVertices)
1360 0 : : mVertices(aVertices)
1361 : {
1362 0 : ComputeExtent();
1363 : }
1364 :
1365 : nsFloatManager::PolygonShapeInfo::PolygonShapeInfo(
1366 0 : nsTArray<nsPoint>&& aVertices,
1367 0 : nscoord aShapeMargin,
1368 : int32_t aAppUnitsPerDevPixel,
1369 0 : const nsRect& aMarginRect)
1370 : : mVertices(aVertices)
1371 : {
1372 0 : MOZ_ASSERT(aShapeMargin > 0, "This constructor should only be used for a "
1373 : "polygon with a positive shape-margin.");
1374 :
1375 : ComputeExtent();
1376 :
1377 : // With a positive aShapeMargin, we have to calculate a distance
1378 : // field from the opaque pixels, then build intervals based on
1379 : // them being within aShapeMargin distance to an opaque pixel.
1380 :
1381 : // Roughly: for each pixel in the margin box, we need to determine the
1382 : // distance to the nearest opaque image-pixel. If that distance is less
1383 : // than aShapeMargin, we consider this margin-box pixel as being part of
1384 : // the float area.
1385 :
1386 : // Computing the distance field is a two-pass O(n) operation.
1387 : // We use a chamfer 5-7-11 5x5 matrix to compute minimum distance
1388 : // to an opaque pixel. This integer math computation is reasonably
1389 : // close to the true Euclidean distance. The distances will be
1390 : // approximately 5x the true distance, quantized in integer units.
1391 0 : // The 5x is factored away in the comparison used in the final
1392 : // pass which builds the intervals.
1393 : dfType usedMargin5X = CalcUsedShapeMargin5X(aShapeMargin,
1394 : aAppUnitsPerDevPixel);
1395 :
1396 : // Allocate our distance field. The distance field has to cover
1397 : // the entire aMarginRect, since aShapeMargin could bleed into it.
1398 0 : // Conveniently, our vertices have been converted into this same space,
1399 0 : // so if we cover the aMarginRect, we cover all the vertices.
1400 : const LayoutDeviceIntSize marginRectDevPixels =
1401 : LayoutDevicePixel::FromAppUnitsRounded(aMarginRect.Size(),
1402 : aAppUnitsPerDevPixel);
1403 :
1404 : // Since our distance field is computed with a 5x5 neighborhood,
1405 : // we need to expand our distance field by a further 4 pixels in
1406 : // both axes, 2 on the leading edge and 2 on the trailing edge.
1407 : // We call this edge area the "expanded region".
1408 : static const uint32_t kiExpansionPerSide = 2;
1409 : static const uint32_t kbExpansionPerSide = 2;
1410 :
1411 : // Clamp the size of our distance field sizes to prevent multiplication
1412 : // overflow.
1413 : static const uint32_t DF_SIDE_MAX =
1414 : floor(sqrt((double)(std::numeric_limits<int32_t>::max())));
1415 :
1416 : // Clamp the margin plus 2X the expansion values between expansion + 1 and
1417 0 : // DF_SIDE_MAX. This ensures that the distance field allocation doesn't
1418 : // overflow during multiplication, and the reverse iteration doesn't
1419 : // underflow.
1420 0 : const uint32_t iSize = std::max(std::min(marginRectDevPixels.width +
1421 0 : (kiExpansionPerSide * 2),
1422 : DF_SIDE_MAX),
1423 : kiExpansionPerSide + 1);
1424 0 : const uint32_t bSize = std::max(std::min(marginRectDevPixels.height +
1425 : (kbExpansionPerSide * 2),
1426 : DF_SIDE_MAX),
1427 : kbExpansionPerSide + 1);
1428 :
1429 : // Since the margin-box size is CSS controlled, and large values will
1430 0 : // generate large iSize and bSize values, we do a fallible allocation for
1431 0 : // the distance field. If allocation fails, we early exit and layout will
1432 : // be wrong, but we'll avoid aborting from OOM.
1433 0 : auto df = MakeUniqueFallible<dfType[]>(iSize * bSize);
1434 : if (!df) {
1435 : // Without a distance field, we can't reason about the float area.
1436 : return;
1437 : }
1438 :
1439 : // First pass setting distance field, starting at top-left, three cases:
1440 : // 1) Expanded region pixel: set to MAX_MARGIN_5X.
1441 : // 2) Pixel within the polygon: set to 0.
1442 0 : // 3) Other pixel: set to minimum backward-looking neighborhood
1443 : // distance value, computed with 5-7-11 chamfer.
1444 :
1445 : for (uint32_t b = 0; b < bSize; ++b) {
1446 : // Find the left and right i intercepts of the polygon edge for this
1447 : // block row, and adjust them to compensate for the expansion of the
1448 0 : // inline dimension. If we're in the expanded region, or if we're using
1449 0 : // a b that's less than the bStart of the polygon, the intercepts are
1450 0 : // the nscoord min and max limits.
1451 : nscoord bInAppUnits = (b - kbExpansionPerSide) * aAppUnitsPerDevPixel;
1452 : bool bIsInExpandedRegion(b < kbExpansionPerSide ||
1453 : b >= bSize - kbExpansionPerSide);
1454 :
1455 : // We now figure out the i values that correspond to the left edge and
1456 : // the right edge of the polygon at one-dev-pixel-thick strip of b. We
1457 : // have a ComputeLineIntercept function that takes and returns app unit
1458 : // coordinates in the space of aMarginRect. So to pass in b values, we
1459 0 : // first have to add the aMarginRect.y value. And for the values that we
1460 0 : // get out, we have to subtract away the aMarginRect.x value before
1461 0 : // converting the app units to dev pixels.
1462 : nscoord bInAppUnitsMarginRect = bInAppUnits + aMarginRect.y;
1463 0 : bool bIsLessThanPolygonBStart(bInAppUnitsMarginRect < mBStart);
1464 0 : bool bIsMoreThanPolygonBEnd(bInAppUnitsMarginRect > mBEnd);
1465 0 :
1466 0 : const int32_t iLeftEdge = (bIsInExpandedRegion ||
1467 0 : bIsLessThanPolygonBStart ||
1468 : bIsMoreThanPolygonBEnd) ? nscoord_MAX :
1469 0 : kiExpansionPerSide + NSAppUnitsToIntPixels(
1470 0 : ComputeLineIntercept(bInAppUnitsMarginRect,
1471 : bInAppUnitsMarginRect + aAppUnitsPerDevPixel,
1472 : std::min<nscoord>, nscoord_MAX) - aMarginRect.x,
1473 0 : aAppUnitsPerDevPixel);
1474 0 :
1475 0 : const int32_t iRightEdge = (bIsInExpandedRegion ||
1476 0 : bIsLessThanPolygonBStart ||
1477 : bIsMoreThanPolygonBEnd) ? nscoord_MIN :
1478 0 : kiExpansionPerSide + NSAppUnitsToIntPixels(
1479 0 : ComputeLineIntercept(bInAppUnitsMarginRect,
1480 : bInAppUnitsMarginRect + aAppUnitsPerDevPixel,
1481 0 : std::max<nscoord>, nscoord_MIN) - aMarginRect.x,
1482 0 : aAppUnitsPerDevPixel);
1483 0 :
1484 : for (uint32_t i = 0; i < iSize; ++i) {
1485 : const uint32_t index = i + b * iSize;
1486 : MOZ_ASSERT(index < (iSize * bSize),
1487 0 : "Our distance field index should be in-bounds.");
1488 0 :
1489 : // Handle our three cases, in order.
1490 : if (i < kiExpansionPerSide ||
1491 0 : i >= iSize - kiExpansionPerSide ||
1492 0 : bIsInExpandedRegion) {
1493 : // Case 1: Expanded pixel.
1494 : df[index] = MAX_MARGIN_5X;
1495 : } else if ((int32_t)i >= iLeftEdge && (int32_t)i <= iRightEdge) {
1496 0 : // Case 2: Polygon pixel, either inside or just adjacent to the right
1497 : // edge. We need this special distinction to detect a space between
1498 : // edges that is less than one dev pixel.
1499 : df[index] = (int32_t)i < iRightEdge ? 0 : 5;
1500 : } else {
1501 : // Case 3: Other pixel.
1502 :
1503 : // Backward-looking neighborhood distance from target pixel X
1504 : // with chamfer 5-7-11 looks like:
1505 : //
1506 : // +--+--+--+--+--+
1507 : // | |11| |11| |
1508 : // +--+--+--+--+--+
1509 : // |11| 7| 5| 7|11|
1510 : // +--+--+--+--+--+
1511 : // | | 5| X| | |
1512 : // +--+--+--+--+--+
1513 : //
1514 0 : // X should be set to the minimum of MAX_MARGIN_5X and the
1515 : // values of all of the numbered neighbors summed with the
1516 : // value in that chamfer cell.
1517 : MOZ_ASSERT(index - (iSize * 2) - 1 < (iSize * bSize) &&
1518 : index - iSize - 2 < (iSize * bSize),
1519 0 : "Our distance field most extreme indices should be "
1520 0 : "in-bounds.");
1521 0 :
1522 0 : df[index] = std::min<dfType>(MAX_MARGIN_5X,
1523 0 : std::min<dfType>(df[index - (iSize * 2) - 1] + 11,
1524 0 : std::min<dfType>(df[index - (iSize * 2) + 1] + 11,
1525 0 : std::min<dfType>(df[index - iSize - 2] + 11,
1526 0 : std::min<dfType>(df[index - iSize - 1] + 7,
1527 0 : std::min<dfType>(df[index - iSize] + 5,
1528 : std::min<dfType>(df[index - iSize + 1] + 7,
1529 : std::min<dfType>(df[index - iSize + 2] + 11,
1530 : df[index - 1] + 5))))))));
1531 : }
1532 : }
1533 : }
1534 :
1535 : // Okay, time for the second pass. This pass is in reverse order from
1536 : // the first pass. All of our opaque pixels have been set to 0, and all
1537 : // of our expanded region pixels have been set to MAX_MARGIN_5X. Other
1538 : // pixels have been set to some value between those two (inclusive) but
1539 : // this hasn't yet taken into account the neighbors that were processed
1540 : // after them in the first pass. This time we reverse iterate so we can
1541 : // apply the forward-looking chamfer.
1542 :
1543 : // This time, we constrain our outer and inner loop to ignore the
1544 : // expanded region pixels. For each pixel we iterate, we set the df value
1545 : // to the minimum forward-looking neighborhood distance value, computed
1546 : // with a 5-7-11 chamfer. We also check each df value against the
1547 : // usedMargin5X threshold, and use that to set the iMin and iMax values
1548 : // for the interval we'll create for that block axis value (b).
1549 0 :
1550 0 : // At the end of each row, if any of the other pixels had a value less
1551 : // than usedMargin5X, we create an interval.
1552 : for (uint32_t b = bSize - kbExpansionPerSide - 1;
1553 : b >= kbExpansionPerSide; --b) {
1554 0 : // iMin tracks the first df pixel and iMax the last df pixel whose
1555 0 : // df[] value is less than usedMargin5X. Set iMin and iMax in
1556 : // preparation for this row or column.
1557 0 : int32_t iMin = iSize;
1558 0 : int32_t iMax = -1;
1559 0 :
1560 0 : for (uint32_t i = iSize - kiExpansionPerSide - 1;
1561 : i >= kiExpansionPerSide; --i) {
1562 : const uint32_t index = i + b * iSize;
1563 : MOZ_ASSERT(index < (iSize * bSize),
1564 : "Our distance field index should be in-bounds.");
1565 0 :
1566 : // Only apply the chamfer calculation if the df value is not
1567 : // already 0, since the chamfer can only reduce the value.
1568 : if (df[index]) {
1569 : // Forward-looking neighborhood distance from target pixel X
1570 : // with chamfer 5-7-11 looks like:
1571 : //
1572 : // +--+--+--+--+--+
1573 : // | | | X| 5| |
1574 : // +--+--+--+--+--+
1575 : // |11| 7| 5| 7|11|
1576 : // +--+--+--+--+--+
1577 : // | |11| |11| |
1578 : // +--+--+--+--+--+
1579 : //
1580 0 : // X should be set to the minimum of its current value and
1581 : // the values of all of the numbered neighbors summed with
1582 : // the value in that chamfer cell.
1583 : MOZ_ASSERT(index + (iSize * 2) + 1 < (iSize * bSize) &&
1584 : index + iSize + 2 < (iSize * bSize),
1585 0 : "Our distance field most extreme indices should be "
1586 0 : "in-bounds.");
1587 0 :
1588 0 : df[index] = std::min<dfType>(df[index],
1589 0 : std::min<dfType>(df[index + (iSize * 2) + 1] + 11,
1590 0 : std::min<dfType>(df[index + (iSize * 2) - 1] + 11,
1591 0 : std::min<dfType>(df[index + iSize + 2] + 11,
1592 0 : std::min<dfType>(df[index + iSize + 1] + 7,
1593 0 : std::min<dfType>(df[index + iSize] + 5,
1594 : std::min<dfType>(df[index + iSize - 1] + 7,
1595 : std::min<dfType>(df[index + iSize - 2] + 11,
1596 : df[index + 1] + 5))))))));
1597 : }
1598 0 :
1599 0 : // Finally, we can check the df value and see if it's less than
1600 0 : // or equal to the usedMargin5X value.
1601 : if (df[index] <= usedMargin5X) {
1602 0 : if (iMax == -1) {
1603 : iMax = i;
1604 : }
1605 : MOZ_ASSERT(iMin > (int32_t)i);
1606 : iMin = i;
1607 0 : }
1608 : }
1609 :
1610 : if (iMax != -1) {
1611 : // Our interval values, iMin, iMax, and b are all calculated from
1612 : // the expanded region, which is based on the margin rect. To create
1613 : // our interval, we have to subtract kiExpansionPerSide from iMin and
1614 : // iMax, and subtract kbExpansionPerSide from b to account for the
1615 : // expanded region edges. This produces coords that are relative to
1616 : // our margin-rect.
1617 :
1618 0 : // Origin for this interval is at the aMarginRect origin, adjusted in
1619 0 : // the block direction by b in app units, and in the inline direction
1620 0 : // by iMin in app units.
1621 0 : nsPoint origin(aMarginRect.x +
1622 : (iMin - kiExpansionPerSide) * aAppUnitsPerDevPixel,
1623 : aMarginRect.y +
1624 : (b - kbExpansionPerSide) * aAppUnitsPerDevPixel);
1625 :
1626 : // Size is the difference in iMax and iMin, plus 1 (to account for the
1627 : // whole pixel) dev pixels, by 1 block dev pixel. We don't bother
1628 0 : // subtracting kiExpansionPerSide from iMin and iMax in this case
1629 0 : // because we only care about the distance between them. We convert
1630 : // everything to app units.
1631 0 : nsSize size((iMax - iMin + 1) * aAppUnitsPerDevPixel,
1632 : aAppUnitsPerDevPixel);
1633 :
1634 : mIntervals.AppendElement(nsRect(origin, size));
1635 : }
1636 0 : }
1637 :
1638 : // Reverse the intervals keep the array sorted on the block direction.
1639 : mIntervals.Reverse();
1640 :
1641 0 : // Adjust our extents by aShapeMargin. This may cause overflow of some
1642 0 : // kind if aShapeMargin is large, so we do some clamping to maintain the
1643 : // invariant mBStart <= mBEnd.
1644 : mBStart = std::min(mBStart, mBStart - aShapeMargin);
1645 : mBEnd = std::max(mBEnd, mBEnd + aShapeMargin);
1646 0 : }
1647 :
1648 : nscoord
1649 : nsFloatManager::PolygonShapeInfo::LineLeft(const nscoord aBStart,
1650 0 : const nscoord aBEnd) const
1651 0 : {
1652 : // Use intervals if we have them.
1653 : if (!mIntervals.IsEmpty()) {
1654 : return LineEdge(mIntervals, aBStart, aBEnd, true);
1655 : }
1656 :
1657 : // We want the line-left-most inline-axis coordinate where the
1658 : // (block-axis) aBStart/aBEnd band crosses a line segment of the polygon.
1659 : // To get that, we start as line-right as possible (at nscoord_MAX). Then
1660 : // we iterate each line segment to compute its intersection point with the
1661 : // band (if any) and using std::min() successively to get the smallest
1662 : // inline-coordinates among those intersection points.
1663 0 : //
1664 : // Note: std::min<nscoord> means the function std::min() with template
1665 : // parameter nscoord, not the minimum value of nscoord.
1666 : return ComputeLineIntercept(aBStart, aBEnd, std::min<nscoord>, nscoord_MAX);
1667 0 : }
1668 :
1669 : nscoord
1670 : nsFloatManager::PolygonShapeInfo::LineRight(const nscoord aBStart,
1671 0 : const nscoord aBEnd) const
1672 0 : {
1673 : // Use intervals if we have them.
1674 : if (!mIntervals.IsEmpty()) {
1675 : return LineEdge(mIntervals, aBStart, aBEnd, false);
1676 : }
1677 :
1678 : // Similar to LineLeft(). Though here, we want the line-right-most
1679 0 : // inline-axis coordinate, so we instead start at nscoord_MIN and use
1680 : // std::max() to get the biggest inline-coordinate among those
1681 : // intersection points.
1682 : return ComputeLineIntercept(aBStart, aBEnd, std::max<nscoord>, nscoord_MIN);
1683 0 : }
1684 :
1685 : void
1686 : nsFloatManager::PolygonShapeInfo::ComputeExtent()
1687 : {
1688 0 : // mBStart and mBEnd are the lower and the upper bounds of all the
1689 0 : // vertex.y, respectively. The vertex.y is actually on the block-axis of
1690 0 : // the float manager's writing mode.
1691 : for (const nsPoint& vertex : mVertices) {
1692 : mBStart = std::min(mBStart, vertex.y);
1693 0 : mBEnd = std::max(mBEnd, vertex.y);
1694 : }
1695 0 :
1696 : MOZ_ASSERT(mBStart <= mBEnd, "Start of float area should be less than "
1697 : "or equal to the end.");
1698 0 : }
1699 :
1700 : nscoord
1701 : nsFloatManager::PolygonShapeInfo::ComputeLineIntercept(
1702 : const nscoord aBStart,
1703 : const nscoord aBEnd,
1704 0 : nscoord (*aCompareOp) (std::initializer_list<nscoord>),
1705 : const nscoord aLineInterceptInitialValue) const
1706 : {
1707 0 : MOZ_ASSERT(aBStart <= aBEnd,
1708 0 : "The band's block start is greater than its block end?");
1709 :
1710 : const size_t len = mVertices.Length();
1711 : nscoord lineIntercept = aLineInterceptInitialValue;
1712 :
1713 : // We have some special treatment of horizontal lines between vertices.
1714 : // Generally, we can ignore the impact of the horizontal lines since their
1715 : // endpoints will be included in the lines preceeding or following them.
1716 : // However, it's possible the polygon is entirely a horizontal line,
1717 : // possibly built from more than one horizontal segment. In such a case,
1718 0 : // we need to have the horizontal line(s) contribute to the line intercepts.
1719 : // We do this by accepting horizontal lines until we find a non-horizontal
1720 : // line, after which all further horizontal lines are ignored.
1721 0 : bool canIgnoreHorizontalLines = false;
1722 0 :
1723 0 : // Iterate each line segment {p0, p1}, {p1, p2}, ..., {pn, p0}.
1724 : for (size_t i = 0; i < len; ++i) {
1725 : const nsPoint* smallYVertex = &mVertices[i];
1726 : const nsPoint* bigYVertex = &mVertices[(i + 1) % len];
1727 0 :
1728 : // Swap the two points to satisfy the requirement for calling
1729 : // XInterceptAtY.
1730 : if (smallYVertex->y > bigYVertex->y) {
1731 : std::swap(smallYVertex, bigYVertex);
1732 : }
1733 :
1734 : // Generally, we need to ignore line segments that either don't intersect
1735 0 : // the band, or merely touch it. However, if the polygon has no block extent
1736 0 : // (it is a point, or a horizontal line), and the band touches the line
1737 : // segment, we let that line segment through.
1738 : if ((aBStart >= bigYVertex->y || aBEnd <= smallYVertex->y) &&
1739 : !(mBStart == mBEnd && aBStart == bigYVertex->y)) {
1740 : // Skip computing the intercept if the band doesn't intersect the
1741 : // line segment.
1742 : continue;
1743 : }
1744 :
1745 0 : nscoord bStartLineIntercept;
1746 : nscoord bEndLineIntercept;
1747 0 :
1748 : if (smallYVertex->y == bigYVertex->y) {
1749 : // The line is horizontal; see if we can ignore it.
1750 : if (canIgnoreHorizontalLines) {
1751 : continue;
1752 : }
1753 :
1754 : // For a horizontal line that we can't ignore, we treat the two x value
1755 0 : // ends as the bStartLineIntercept and bEndLineIntercept. It doesn't
1756 0 : // matter which is applied to which, because they'll both be applied
1757 : // to aCompareOp.
1758 : bStartLineIntercept = smallYVertex->x;
1759 : bEndLineIntercept = bigYVertex->x;
1760 0 : } else {
1761 : // This is not a horizontal line. We can now ignore all future
1762 0 : // horizontal lines.
1763 : canIgnoreHorizontalLines = true;
1764 0 :
1765 : bStartLineIntercept =
1766 : aBStart <= smallYVertex->y
1767 0 : ? smallYVertex->x
1768 0 : : XInterceptAtY(aBStart, *smallYVertex, *bigYVertex);
1769 : bEndLineIntercept =
1770 : aBEnd >= bigYVertex->y
1771 : ? bigYVertex->x
1772 : : XInterceptAtY(aBEnd, *smallYVertex, *bigYVertex);
1773 : }
1774 :
1775 0 : // If either new intercept is more extreme than lineIntercept (per
1776 : // aCompareOp), then update lineIntercept to that value.
1777 : lineIntercept =
1778 0 : aCompareOp({lineIntercept, bStartLineIntercept, bEndLineIntercept});
1779 : }
1780 :
1781 : return lineIntercept;
1782 0 : }
1783 :
1784 : void
1785 0 : nsFloatManager::PolygonShapeInfo::Translate(nscoord aLineLeft,
1786 0 : nscoord aBlockStart)
1787 : {
1788 0 : for (nsPoint& vertex : mVertices) {
1789 0 : vertex.MoveBy(aLineLeft, aBlockStart);
1790 : }
1791 0 : for (nsRect& interval : mIntervals) {
1792 0 : interval.MoveBy(aLineLeft, aBlockStart);
1793 0 : }
1794 : mBStart += aBlockStart;
1795 : mBEnd += aBlockStart;
1796 0 : }
1797 :
1798 : /* static */ nscoord
1799 : nsFloatManager::PolygonShapeInfo::XInterceptAtY(const nscoord aY,
1800 : const nsPoint& aP1,
1801 : const nsPoint& aP2)
1802 : {
1803 0 : // Solve for x in the linear equation: x = x1 + (y-y1) * (x2-x1) / (y2-y1),
1804 : // where aP1 = (x1, y1) and aP2 = (x2, y2).
1805 :
1806 : MOZ_ASSERT(aP1.y <= aY && aY <= aP2.y,
1807 0 : "This function won't work if the horizontal line at aY and "
1808 : "the line segment (aP1, aP2) do not intersect!");
1809 :
1810 0 : MOZ_ASSERT(aP1.y != aP2.y,
1811 : "A horizontal line segment results in dividing by zero error!");
1812 :
1813 : return aP1.x + (aY - aP1.y) * (aP2.x - aP1.x) / (aP2.y - aP1.y);
1814 : }
1815 :
1816 : /////////////////////////////////////////////////////////////////////////////
1817 : // ImageShapeInfo
1818 0 : //
1819 : // Implements shape-outside: <image>
1820 : //
1821 : class nsFloatManager::ImageShapeInfo final : public nsFloatManager::ShapeInfo
1822 : {
1823 : public:
1824 : ImageShapeInfo(uint8_t* aAlphaPixels,
1825 : int32_t aStride,
1826 : const LayoutDeviceIntSize& aImageSize,
1827 : int32_t aAppUnitsPerDevPixel,
1828 : float aShapeImageThreshold,
1829 : nscoord aShapeMargin,
1830 : const nsRect& aContentRect,
1831 : const nsRect& aMarginRect,
1832 : WritingMode aWM,
1833 : const nsSize& aContainerSize);
1834 :
1835 : nscoord LineLeft(const nscoord aBStart,
1836 0 : const nscoord aBEnd) const override;
1837 0 : nscoord LineRight(const nscoord aBStart,
1838 0 : const nscoord aBEnd) const override;
1839 0 : nscoord BStart() const override { return mBStart; }
1840 : nscoord BEnd() const override { return mBEnd; }
1841 : bool IsEmpty() const override { return mIntervals.IsEmpty(); }
1842 : bool MayNarrowInBlockDirection() const override { return true; }
1843 :
1844 : void Translate(nscoord aLineLeft, nscoord aBlockStart) override;
1845 :
1846 : private:
1847 : // An interval is slice of the float area defined by this ImageShapeInfo.
1848 : // Each interval is a rectangle that is one pixel deep in the block
1849 : // axis. The values are stored as block edges in the y coordinates,
1850 : // and inline edges as the x coordinates.
1851 :
1852 : // The intervals are stored in ascending order on y.
1853 : nsTArray<nsRect> mIntervals;
1854 :
1855 : nscoord mBStart = nscoord_MAX;
1856 : nscoord mBEnd = nscoord_MIN;
1857 :
1858 : // CreateInterval transforms the supplied aIMin and aIMax and aB
1859 : // values into an interval that respects the writing mode. An
1860 : // aOffsetFromContainer can be provided if the aIMin, aIMax, aB
1861 : // values were generated relative to something other than the container
1862 : // rect (such as the content rect or margin rect).
1863 : void CreateInterval(int32_t aIMin,
1864 : int32_t aIMax,
1865 : int32_t aB,
1866 : int32_t aAppUnitsPerDevPixel,
1867 : const nsPoint& aOffsetFromContainer,
1868 : WritingMode aWM,
1869 0 : const nsSize& aContainerSize);
1870 : };
1871 :
1872 : nsFloatManager::ImageShapeInfo::ImageShapeInfo(
1873 : uint8_t* aAlphaPixels,
1874 : int32_t aStride,
1875 : const LayoutDeviceIntSize& aImageSize,
1876 : int32_t aAppUnitsPerDevPixel,
1877 : float aShapeImageThreshold,
1878 : nscoord aShapeMargin,
1879 0 : const nsRect& aContentRect,
1880 : const nsRect& aMarginRect,
1881 0 : WritingMode aWM,
1882 : const nsSize& aContainerSize)
1883 : {
1884 0 : MOZ_ASSERT(aShapeImageThreshold >=0.0 && aShapeImageThreshold <=1.0,
1885 : "The computed value of shape-image-threshold is wrong!");
1886 0 :
1887 : const uint8_t threshold = NSToIntFloor(aShapeImageThreshold * 255);
1888 0 :
1889 0 : MOZ_ASSERT(aImageSize.width >= 0 && aImageSize.height >= 0,
1890 : "Image size must be non-negative for our math to work.");
1891 0 : const uint32_t w = aImageSize.width;
1892 : const uint32_t h = aImageSize.height;
1893 :
1894 : if (aShapeMargin <= 0) {
1895 : // Without a positive aShapeMargin, all we have to do is a
1896 : // direct threshold comparison of the alpha pixels.
1897 : // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
1898 :
1899 : // Scan the pixels in a double loop. For horizontal writing modes, we do
1900 0 : // this row by row, from top to bottom. For vertical writing modes, we do
1901 0 : // column by column, from left to right. We define the two loops
1902 0 : // generically, then figure out the rows and cols within the inner loop.
1903 : const uint32_t bSize = aWM.IsVertical() ? w : h;
1904 : const uint32_t iSize = aWM.IsVertical() ? h : w;
1905 : for (uint32_t b = 0; b < bSize; ++b) {
1906 : // iMin and max store the start and end of the float area for the row
1907 : // or column represented by this iteration of the outer loop.
1908 0 : int32_t iMin = -1;
1909 0 : int32_t iMax = -1;
1910 0 :
1911 0 : for (uint32_t i = 0; i < iSize; ++i) {
1912 : const uint32_t col = aWM.IsVertical() ? b : i;
1913 : const uint32_t row = aWM.IsVertical() ? i : b;
1914 : const uint32_t index = col + row * aStride;
1915 :
1916 : // Determine if the alpha pixel at this row and column has a value
1917 0 : // greater than the threshold. If it does, update our iMin and iMax
1918 0 : // values to track the edges of the float area for this row or column.
1919 0 : // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
1920 0 : const uint8_t alpha = aAlphaPixels[index];
1921 : if (alpha > threshold) {
1922 0 : if (iMin == -1) {
1923 : iMin = i;
1924 : }
1925 : MOZ_ASSERT(iMax < (int32_t)i);
1926 : iMax = i;
1927 : }
1928 0 : }
1929 :
1930 : // At the end of a row or column; did we find something?
1931 : if (iMin != -1) {
1932 0 : // We need to supply an offset of the content rect top left, since
1933 0 : // our col and row have been calculated from the content rect,
1934 : // instead of the margin rect (against which floats are applied).
1935 : CreateInterval(iMin, iMax, b, aAppUnitsPerDevPixel,
1936 : aContentRect.TopLeft(), aWM, aContainerSize);
1937 0 : }
1938 : }
1939 :
1940 : if (aWM.IsVerticalRL()) {
1941 : // vertical-rl or sideways-rl.
1942 0 : // Because we scan the columns from left to right, we need to reverse
1943 : // the array so that it's sorted (in ascending order) on the block
1944 : // direction.
1945 : mIntervals.Reverse();
1946 : }
1947 : } else {
1948 : // With a positive aShapeMargin, we have to calculate a distance
1949 : // field from the opaque pixels, then build intervals based on
1950 : // them being within aShapeMargin distance to an opaque pixel.
1951 :
1952 : // Roughly: for each pixel in the margin box, we need to determine the
1953 : // distance to the nearest opaque image-pixel. If that distance is less
1954 : // than aShapeMargin, we consider this margin-box pixel as being part of
1955 : // the float area.
1956 :
1957 : // Computing the distance field is a two-pass O(n) operation.
1958 : // We use a chamfer 5-7-11 5x5 matrix to compute minimum distance
1959 : // to an opaque pixel. This integer math computation is reasonably
1960 : // close to the true Euclidean distance. The distances will be
1961 : // approximately 5x the true distance, quantized in integer units.
1962 0 : // The 5x is factored away in the comparison used in the final
1963 : // pass which builds the intervals.
1964 : dfType usedMargin5X = CalcUsedShapeMargin5X(aShapeMargin,
1965 : aAppUnitsPerDevPixel);
1966 :
1967 : // Allocate our distance field. The distance field has to cover
1968 : // the entire aMarginRect, since aShapeMargin could bleed into it,
1969 0 : // beyond the content rect covered by aAlphaPixels. To make this work,
1970 : // we calculate a dfOffset value which is the top left of the content
1971 : // rect relative to the margin rect.
1972 0 : nsPoint offsetPoint = aContentRect.TopLeft() - aMarginRect.TopLeft();
1973 : LayoutDeviceIntPoint dfOffset =
1974 : LayoutDevicePixel::FromAppUnitsRounded(offsetPoint,
1975 : aAppUnitsPerDevPixel);
1976 :
1977 : // Since our distance field is computed with a 5x5 neighborhood,
1978 : // we need to expand our distance field by a further 4 pixels in
1979 : // both axes, 2 on the leading edge and 2 on the trailing edge.
1980 : // We call this edge area the "expanded region".
1981 :
1982 : // Our expansion amounts need to be the same for our math to work.
1983 : static uint32_t kExpansionPerSide = 2;
1984 0 : // Since dfOffset will be used in comparisons against expanded region
1985 0 : // pixel values, it's convenient to add expansion amounts to dfOffset in
1986 : // both axes, to simplify comparison math later.
1987 : dfOffset.x += kExpansionPerSide;
1988 : dfOffset.y += kExpansionPerSide;
1989 :
1990 : // In all these calculations, we purposely ignore aStride, because
1991 : // we don't have to replicate the packing that we received in
1992 0 : // aAlphaPixels. When we need to convert from df coordinates to
1993 0 : // alpha coordinates, we do that with math based on row and col.
1994 : const LayoutDeviceIntSize marginRectDevPixels =
1995 : LayoutDevicePixel::FromAppUnitsRounded(aMarginRect.Size(),
1996 : aAppUnitsPerDevPixel);
1997 :
1998 : // Clamp the size of our distance field sizes to prevent multiplication
1999 : // overflow.
2000 : static const uint32_t DF_SIDE_MAX =
2001 : floor(sqrt((double)(std::numeric_limits<int32_t>::max())));
2002 :
2003 : // Clamp the margin plus 2X the expansion values between expansion + 1
2004 0 : // and DF_SIDE_MAX. This ensures that the distance field allocation
2005 0 : // doesn't overflow during multiplication, and the reverse iteration
2006 : // doesn't underflow.
2007 0 : const uint32_t wEx = std::max(std::min(marginRectDevPixels.width +
2008 0 : (kExpansionPerSide * 2),
2009 : DF_SIDE_MAX),
2010 : kExpansionPerSide + 1);
2011 0 : const uint32_t hEx = std::max(std::min(marginRectDevPixels.height +
2012 : (kExpansionPerSide * 2),
2013 : DF_SIDE_MAX),
2014 : kExpansionPerSide + 1);
2015 :
2016 : // Since the margin-box size is CSS controlled, and large values will
2017 0 : // generate large wEx and hEx values, we do a falliable allocation for
2018 0 : // the distance field. If allocation fails, we early exit and layout will
2019 : // be wrong, but we'll avoid aborting from OOM.
2020 0 : auto df = MakeUniqueFallible<dfType[]>(wEx * hEx);
2021 : if (!df) {
2022 : // Without a distance field, we can't reason about the float area.
2023 0 : return;
2024 0 : }
2025 :
2026 : const uint32_t bSize = aWM.IsVertical() ? wEx : hEx;
2027 : const uint32_t iSize = aWM.IsVertical() ? hEx : wEx;
2028 :
2029 : // First pass setting distance field, starting at top-left, three cases:
2030 : // 1) Expanded region pixel: set to MAX_MARGIN_5X.
2031 : // 2) Image pixel with alpha greater than threshold: set to 0.
2032 : // 3) Other pixel: set to minimum backward-looking neighborhood
2033 : // distance value, computed with 5-7-11 chamfer.
2034 :
2035 : // Scan the pixels in a double loop. For horizontal writing modes, we do
2036 0 : // this row by row, from top to bottom. For vertical writing modes, we do
2037 0 : // column by column, from left to right. We define the two loops
2038 0 : // generically, then figure out the rows and cols within the inner loop.
2039 0 : for (uint32_t b = 0; b < bSize; ++b) {
2040 0 : for (uint32_t i = 0; i < iSize; ++i) {
2041 0 : const uint32_t col = aWM.IsVertical() ? b : i;
2042 : const uint32_t row = aWM.IsVertical() ? i : b;
2043 : const uint32_t index = col + row * wEx;
2044 : MOZ_ASSERT(index < (wEx * hEx),
2045 0 : "Our distance field index should be in-bounds.");
2046 0 :
2047 0 : // Handle our three cases, in order.
2048 0 : if (col < kExpansionPerSide ||
2049 : col >= wEx - kExpansionPerSide ||
2050 0 : row < kExpansionPerSide ||
2051 0 : row >= hEx - kExpansionPerSide) {
2052 0 : // Case 1: Expanded pixel.
2053 0 : df[index] = MAX_MARGIN_5X;
2054 0 : } else if ((int32_t)col >= dfOffset.x &&
2055 0 : (int32_t)col < (dfOffset.x + aImageSize.width) &&
2056 0 : (int32_t)row >= dfOffset.y &&
2057 : (int32_t)row < (dfOffset.y + aImageSize.height) &&
2058 0 : aAlphaPixels[col - dfOffset.x +
2059 0 : (row - dfOffset.y) * aStride] > threshold) {
2060 0 : // Case 2: Image pixel that is opaque.
2061 : DebugOnly<uint32_t> alphaIndex = col - dfOffset.x +
2062 : (row - dfOffset.y) * aStride;
2063 0 : MOZ_ASSERT(alphaIndex < (aStride * h),
2064 : "Our aAlphaPixels index should be in-bounds.");
2065 :
2066 0 : df[index] = 0;
2067 : } else {
2068 : // Case 3: Other pixel.
2069 : if (aWM.IsVertical()) {
2070 : // Column-by-column, starting at the left, each column
2071 : // top-to-bottom.
2072 : // Backward-looking neighborhood distance from target pixel X
2073 : // with chamfer 5-7-11 looks like:
2074 : //
2075 : // +--+--+--+
2076 : // | |11| | | +
2077 : // +--+--+--+ | /|
2078 : // |11| 7| 5| | / |
2079 : // +--+--+--+ | / V
2080 : // | | 5| X| |/
2081 : // +--+--+--+ +
2082 : // |11| 7| |
2083 : // +--+--+--+
2084 : // | |11| |
2085 : // +--+--+--+
2086 : //
2087 0 : // X should be set to the minimum of MAX_MARGIN_5X and the
2088 : // values of all of the numbered neighbors summed with the
2089 : // value in that chamfer cell.
2090 : MOZ_ASSERT(index - wEx - 2 < (iSize * bSize) &&
2091 : index + wEx - 2 < (iSize * bSize) &&
2092 : index - (wEx * 2) - 1 < (iSize * bSize),
2093 0 : "Our distance field most extreme indices should be "
2094 0 : "in-bounds.");
2095 0 :
2096 0 : df[index] = std::min<dfType>(MAX_MARGIN_5X,
2097 0 : std::min<dfType>(df[index - wEx - 2] + 11,
2098 0 : std::min<dfType>(df[index + wEx - 2] + 11,
2099 0 : std::min<dfType>(df[index - (wEx * 2) - 1] + 11,
2100 0 : std::min<dfType>(df[index - wEx - 1] + 7,
2101 0 : std::min<dfType>(df[index - 1] + 5,
2102 : std::min<dfType>(df[index + wEx - 1] + 7,
2103 : std::min<dfType>(df[index + (wEx * 2) - 1] + 11,
2104 : df[index - wEx] + 5))))))));
2105 : } else {
2106 : // Row-by-row, starting at the top, each row left-to-right.
2107 : // Backward-looking neighborhood distance from target pixel X
2108 : // with chamfer 5-7-11 looks like:
2109 : //
2110 : // +--+--+--+--+--+
2111 : // | |11| |11| | ----+
2112 : // +--+--+--+--+--+ /
2113 : // |11| 7| 5| 7|11| /
2114 : // +--+--+--+--+--+ /
2115 : // | | 5| X| | | +-->
2116 : // +--+--+--+--+--+
2117 : //
2118 0 : // X should be set to the minimum of MAX_MARGIN_5X and the
2119 : // values of all of the numbered neighbors summed with the
2120 : // value in that chamfer cell.
2121 : MOZ_ASSERT(index - (wEx * 2) - 1 < (iSize * bSize) &&
2122 : index - wEx - 2 < (iSize * bSize),
2123 0 : "Our distance field most extreme indices should be "
2124 0 : "in-bounds.");
2125 0 :
2126 0 : df[index] = std::min<dfType>(MAX_MARGIN_5X,
2127 0 : std::min<dfType>(df[index - (wEx * 2) - 1] + 11,
2128 0 : std::min<dfType>(df[index - (wEx * 2) + 1] + 11,
2129 0 : std::min<dfType>(df[index - wEx - 2] + 11,
2130 0 : std::min<dfType>(df[index - wEx - 1] + 7,
2131 0 : std::min<dfType>(df[index - wEx] + 5,
2132 : std::min<dfType>(df[index - wEx + 1] + 7,
2133 : std::min<dfType>(df[index - wEx + 2] + 11,
2134 : df[index - 1] + 5))))))));
2135 : }
2136 : }
2137 : }
2138 : }
2139 :
2140 : // Okay, time for the second pass. This pass is in reverse order from
2141 : // the first pass. All of our opaque pixels have been set to 0, and all
2142 : // of our expanded region pixels have been set to MAX_MARGIN_5X. Other
2143 : // pixels have been set to some value between those two (inclusive) but
2144 : // this hasn't yet taken into account the neighbors that were processed
2145 : // after them in the first pass. This time we reverse iterate so we can
2146 : // apply the forward-looking chamfer.
2147 :
2148 : // This time, we constrain our outer and inner loop to ignore the
2149 : // expanded region pixels. For each pixel we iterate, we set the df value
2150 : // to the minimum forward-looking neighborhood distance value, computed
2151 : // with a 5-7-11 chamfer. We also check each df value against the
2152 : // usedMargin5X threshold, and use that to set the iMin and iMax values
2153 : // for the interval we'll create for that block axis value (b).
2154 :
2155 : // At the end of each row (or column in vertical writing modes),
2156 0 : // if any of the other pixels had a value less than usedMargin5X,
2157 0 : // we create an interval. Note: "bSize - kExpansionPerSide - 1" is the
2158 : // index of the final row of pixels before the trailing expanded region.
2159 : for (uint32_t b = bSize - kExpansionPerSide - 1;
2160 : b >= kExpansionPerSide; --b) {
2161 0 : // iMin tracks the first df pixel and iMax the last df pixel whose
2162 0 : // df[] value is less than usedMargin5X. Set iMin and iMax in
2163 : // preparation for this row or column.
2164 : int32_t iMin = iSize;
2165 : int32_t iMax = -1;
2166 0 :
2167 0 : // Note: "iSize - kExpansionPerSide - 1" is the index of the final row
2168 0 : // of pixels before the trailing expanded region.
2169 0 : for (uint32_t i = iSize - kExpansionPerSide - 1;
2170 0 : i >= kExpansionPerSide; --i) {
2171 0 : const uint32_t col = aWM.IsVertical() ? b : i;
2172 : const uint32_t row = aWM.IsVertical() ? i : b;
2173 : const uint32_t index = col + row * wEx;
2174 : MOZ_ASSERT(index < (wEx * hEx),
2175 : "Our distance field index should be in-bounds.");
2176 0 :
2177 0 : // Only apply the chamfer calculation if the df value is not
2178 : // already 0, since the chamfer can only reduce the value.
2179 : if (df[index]) {
2180 : if (aWM.IsVertical()) {
2181 : // Column-by-column, starting at the right, each column
2182 : // bottom-to-top.
2183 : // Forward-looking neighborhood distance from target pixel X
2184 : // with chamfer 5-7-11 looks like:
2185 : //
2186 : // +--+--+--+
2187 : // | |11| | +
2188 : // +--+--+--+ /|
2189 : // | | 7|11| A / |
2190 : // +--+--+--+ | / |
2191 : // | X| 5| | |/ |
2192 : // +--+--+--+ + |
2193 : // | 5| 7|11|
2194 : // +--+--+--+
2195 : // | |11| |
2196 : // +--+--+--+
2197 : //
2198 0 : // X should be set to the minimum of its current value and
2199 : // the values of all of the numbered neighbors summed with
2200 : // the value in that chamfer cell.
2201 : MOZ_ASSERT(index + wEx + 2 < (wEx * hEx) &&
2202 : index + (wEx * 2) + 1 < (wEx * hEx) &&
2203 : index - (wEx * 2) + 1 < (wEx * hEx),
2204 0 : "Our distance field most extreme indices should be "
2205 0 : "in-bounds.");
2206 0 :
2207 0 : df[index] = std::min<dfType>(df[index],
2208 0 : std::min<dfType>(df[index + wEx + 2] + 11,
2209 0 : std::min<dfType>(df[index - wEx + 2] + 11,
2210 0 : std::min<dfType>(df[index + (wEx * 2) + 1] + 11,
2211 0 : std::min<dfType>(df[index + wEx + 1] + 7,
2212 0 : std::min<dfType>(df[index + 1] + 5,
2213 : std::min<dfType>(df[index - wEx + 1] + 7,
2214 : std::min<dfType>(df[index - (wEx * 2) + 1] + 11,
2215 : df[index + wEx] + 5))))))));
2216 : } else {
2217 : // Row-by-row, starting at the bottom, each row right-to-left.
2218 : // Forward-looking neighborhood distance from target pixel X
2219 : // with chamfer 5-7-11 looks like:
2220 : //
2221 : // +--+--+--+--+--+
2222 : // | | | X| 5| | <--+
2223 : // +--+--+--+--+--+ /
2224 : // |11| 7| 5| 7|11| /
2225 : // +--+--+--+--+--+ /
2226 : // | |11| |11| | +----
2227 : // +--+--+--+--+--+
2228 : //
2229 0 : // X should be set to the minimum of its current value and
2230 : // the values of all of the numbered neighbors summed with
2231 : // the value in that chamfer cell.
2232 : MOZ_ASSERT(index + (wEx * 2) + 1 < (wEx * hEx) &&
2233 : index + wEx + 2 < (wEx * hEx),
2234 0 : "Our distance field most extreme indices should be "
2235 0 : "in-bounds.");
2236 0 :
2237 0 : df[index] = std::min<dfType>(df[index],
2238 0 : std::min<dfType>(df[index + (wEx * 2) + 1] + 11,
2239 0 : std::min<dfType>(df[index + (wEx * 2) - 1] + 11,
2240 0 : std::min<dfType>(df[index + wEx + 2] + 11,
2241 0 : std::min<dfType>(df[index + wEx + 1] + 7,
2242 0 : std::min<dfType>(df[index + wEx] + 5,
2243 : std::min<dfType>(df[index + wEx - 1] + 7,
2244 : std::min<dfType>(df[index + wEx - 2] + 11,
2245 : df[index + 1] + 5))))))));
2246 : }
2247 : }
2248 0 :
2249 0 : // Finally, we can check the df value and see if it's less than
2250 0 : // or equal to the usedMargin5X value.
2251 : if (df[index] <= usedMargin5X) {
2252 0 : if (iMax == -1) {
2253 : iMax = i;
2254 : }
2255 : MOZ_ASSERT(iMin > (int32_t)i);
2256 : iMin = i;
2257 0 : }
2258 : }
2259 :
2260 : if (iMax != -1) {
2261 : // Our interval values, iMin, iMax, and b are all calculated from
2262 : // the expanded region, which is based on the margin rect. To create
2263 : // our interval, we have to subtract kExpansionPerSide from (iMin,
2264 : // iMax, and b) to account for the expanded region edges. This
2265 0 : // produces coords that are relative to our margin-rect, so we pass
2266 0 : // in aMarginRect.TopLeft() to make CreateInterval convert to our
2267 0 : // container's coordinate space.
2268 : CreateInterval(iMin - kExpansionPerSide, iMax - kExpansionPerSide,
2269 : b - kExpansionPerSide, aAppUnitsPerDevPixel,
2270 : aMarginRect.TopLeft(), aWM, aContainerSize);
2271 0 : }
2272 : }
2273 :
2274 : if (!aWM.IsVerticalRL()) {
2275 : // Anything other than vertical-rl or sideways-rl.
2276 0 : // Because we assembled our intervals on the bottom-up pass,
2277 : // they are reversed for most writing modes. Reverse them to
2278 : // keep the array sorted on the block direction.
2279 : mIntervals.Reverse();
2280 0 : }
2281 0 : }
2282 0 :
2283 : if (!mIntervals.IsEmpty()) {
2284 : mBStart = mIntervals[0].Y();
2285 : mBEnd = mIntervals.LastElement().YMost();
2286 : }
2287 0 : }
2288 :
2289 : void
2290 : nsFloatManager::ImageShapeInfo::CreateInterval(
2291 : int32_t aIMin,
2292 : int32_t aIMax,
2293 : int32_t aB,
2294 : int32_t aAppUnitsPerDevPixel,
2295 : const nsPoint& aOffsetFromContainer,
2296 : WritingMode aWM,
2297 : const nsSize& aContainerSize)
2298 : {
2299 : // Store an interval as an nsRect with our inline axis values stored in x
2300 : // and our block axis values stored in y. The position is dependent on
2301 : // the writing mode, but the size is the same for all writing modes.
2302 :
2303 0 : // Size is the difference in inline axis edges stored as x, and one
2304 0 : // block axis pixel stored as y. For the inline axis, we add 1 to aIMax
2305 : // because we want to capture the far edge of the last pixel.
2306 : nsSize size(((aIMax + 1) - aIMin) * aAppUnitsPerDevPixel,
2307 : aAppUnitsPerDevPixel);
2308 :
2309 : // Since we started our scanning of the image pixels from the top left,
2310 0 : // the interval position starts from the origin of the content rect,
2311 : // converted to logical coordinates.
2312 : nsPoint origin = ConvertToFloatLogical(aOffsetFromContainer, aWM,
2313 0 : aContainerSize);
2314 :
2315 : // Depending on the writing mode, we now move the origin.
2316 : if (aWM.IsVerticalRL()) {
2317 : // vertical-rl or sideways-rl.
2318 : // These writing modes proceed from the top right, and each interval
2319 0 : // moves in a positive inline direction and negative block direction.
2320 0 : // That means that the intervals will be reversed after all have been
2321 : // constructed. We add 1 to aB to capture the end of the block axis pixel.
2322 : origin.MoveBy(aIMin * aAppUnitsPerDevPixel, (aB + 1) * -aAppUnitsPerDevPixel);
2323 : } else if (aWM.IsVerticalLR() && !aWM.IsLineInverted()) {
2324 : // sideways-lr.
2325 : // Checking IsLineInverted is the only reliable way to distinguish
2326 : // vertical-lr from sideways-lr. IsSideways and IsInlineReversed are both
2327 : // affected by bidi and text-direction, and so complicate detection.
2328 0 : // These writing modes proceed from the bottom left, and each interval
2329 : // moves in a negative inline direction and a positive block direction.
2330 : // We add 1 to aIMax to capture the end of the inline axis pixel.
2331 : origin.MoveBy((aIMax + 1) * -aAppUnitsPerDevPixel, aB * aAppUnitsPerDevPixel);
2332 : } else {
2333 0 : // horizontal-tb or vertical-lr.
2334 : // These writing modes proceed from the top left and each interval
2335 : // moves in a positive step in both inline and block directions.
2336 0 : origin.MoveBy(aIMin * aAppUnitsPerDevPixel, aB * aAppUnitsPerDevPixel);
2337 0 : }
2338 :
2339 : mIntervals.AppendElement(nsRect(origin, size));
2340 0 : }
2341 :
2342 : nscoord
2343 0 : nsFloatManager::ImageShapeInfo::LineLeft(const nscoord aBStart,
2344 : const nscoord aBEnd) const
2345 : {
2346 : return LineEdge(mIntervals, aBStart, aBEnd, true);
2347 0 : }
2348 :
2349 : nscoord
2350 0 : nsFloatManager::ImageShapeInfo::LineRight(const nscoord aBStart,
2351 : const nscoord aBEnd) const
2352 : {
2353 : return LineEdge(mIntervals, aBStart, aBEnd, false);
2354 0 : }
2355 :
2356 : void
2357 0 : nsFloatManager::ImageShapeInfo::Translate(nscoord aLineLeft,
2358 0 : nscoord aBlockStart)
2359 : {
2360 : for (nsRect& interval : mIntervals) {
2361 0 : interval.MoveBy(aLineLeft, aBlockStart);
2362 0 : }
2363 0 :
2364 : mBStart += aBlockStart;
2365 : mBEnd += aBlockStart;
2366 : }
2367 :
2368 0 : /////////////////////////////////////////////////////////////////////////////
2369 : // FloatInfo
2370 :
2371 : nsFloatManager::FloatInfo::FloatInfo(nsIFrame* aFrame,
2372 0 : nscoord aLineLeft, nscoord aBlockStart,
2373 : const LogicalRect& aMarginRect,
2374 0 : WritingMode aWM,
2375 0 : const nsSize& aContainerSize)
2376 : : mFrame(aFrame)
2377 0 : , mRect(ShapeInfo::ConvertToFloatLogical(aMarginRect, aWM, aContainerSize) +
2378 : nsPoint(aLineLeft, aBlockStart))
2379 0 : {
2380 : MOZ_COUNT_CTOR(nsFloatManager::FloatInfo);
2381 :
2382 : if (IsEmpty()) {
2383 : // Per spec, a float area defined by a shape is clipped to the float’s
2384 : // margin box. Therefore, no need to create a shape info if the float's
2385 : // margin box is empty, since a float area can only be smaller than the
2386 : // margin box.
2387 :
2388 : // https://drafts.csswg.org/css-shapes/#relation-to-box-model-and-float-behavior
2389 0 : return;
2390 : }
2391 0 :
2392 0 : const nsStyleDisplay* styleDisplay = mFrame->StyleDisplay();
2393 0 : const StyleShapeSource& shapeOutside = styleDisplay->mShapeOutside;
2394 0 :
2395 0 : nscoord shapeMargin = (shapeOutside.GetType() == StyleShapeSourceType::None)
2396 : ? 0
2397 0 : : nsLayoutUtils::ResolveToLength<true>(
2398 : styleDisplay->mShapeMargin,
2399 : LogicalSize(aWM, aContainerSize).ISize(aWM));
2400 :
2401 : switch (shapeOutside.GetType()) {
2402 : case StyleShapeSourceType::None:
2403 0 : // No need to create shape info.
2404 : return;
2405 :
2406 : case StyleShapeSourceType::URL:
2407 0 : MOZ_ASSERT_UNREACHABLE("shape-outside doesn't have URL source type!");
2408 0 : return;
2409 :
2410 : case StyleShapeSourceType::Image: {
2411 0 : float shapeImageThreshold = styleDisplay->mShapeImageThreshold;
2412 : mShapeInfo = ShapeInfo::CreateImageShape(shapeOutside.GetShapeImage(),
2413 : shapeImageThreshold,
2414 0 : shapeMargin,
2415 0 : mFrame,
2416 : aMarginRect,
2417 : aWM,
2418 : aContainerSize);
2419 : if (!mShapeInfo) {
2420 : // Image is not ready, or fails to load, etc.
2421 : return;
2422 : }
2423 :
2424 : break;
2425 : }
2426 0 :
2427 0 : case StyleShapeSourceType::Box: {
2428 : // Initialize <shape-box>'s reference rect.
2429 0 : LogicalRect shapeBoxRect =
2430 : ShapeInfo::ComputeShapeBoxRect(shapeOutside, mFrame, aMarginRect, aWM);
2431 : mShapeInfo = ShapeInfo::CreateShapeBox(mFrame, shapeMargin,
2432 : shapeBoxRect, aWM,
2433 : aContainerSize);
2434 0 : break;
2435 : }
2436 :
2437 0 : case StyleShapeSourceType::Shape: {
2438 0 : const UniquePtr<StyleBasicShape>& basicShape = shapeOutside.GetBasicShape();
2439 : // Initialize <shape-box>'s reference rect.
2440 0 : LogicalRect shapeBoxRect =
2441 : ShapeInfo::ComputeShapeBoxRect(shapeOutside, mFrame, aMarginRect, aWM);
2442 : mShapeInfo = ShapeInfo::CreateBasicShape(basicShape, shapeMargin, mFrame,
2443 : shapeBoxRect, aMarginRect, aWM,
2444 : aContainerSize);
2445 0 : break;
2446 : }
2447 : }
2448 :
2449 0 : MOZ_ASSERT(mShapeInfo,
2450 : "All shape-outside values except none should have mShapeInfo!");
2451 :
2452 : // Translate the shape to the same origin as nsFloatManager.
2453 0 : mShapeInfo->Translate(aLineLeft, aBlockStart);
2454 0 : }
2455 0 :
2456 0 : #ifdef NS_BUILD_REFCNT_LOGGING
2457 0 : nsFloatManager::FloatInfo::FloatInfo(FloatInfo&& aOther)
2458 0 : : mFrame(std::move(aOther.mFrame))
2459 : , mLeftBEnd(std::move(aOther.mLeftBEnd))
2460 0 : , mRightBEnd(std::move(aOther.mRightBEnd))
2461 0 : , mRect(std::move(aOther.mRect))
2462 : , mShapeInfo(std::move(aOther.mShapeInfo))
2463 0 : {
2464 : MOZ_COUNT_CTOR(nsFloatManager::FloatInfo);
2465 0 : }
2466 0 :
2467 : nsFloatManager::FloatInfo::~FloatInfo()
2468 : {
2469 : MOZ_COUNT_DTOR(nsFloatManager::FloatInfo);
2470 0 : }
2471 : #endif
2472 :
2473 : nscoord
2474 0 : nsFloatManager::FloatInfo::LineLeft(ShapeType aShapeType,
2475 0 : const nscoord aBStart,
2476 : const nscoord aBEnd) const
2477 : {
2478 0 : if (aShapeType == ShapeType::Margin) {
2479 0 : return LineLeft();
2480 0 : }
2481 :
2482 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2483 : if (!mShapeInfo) {
2484 : return LineLeft();
2485 : }
2486 0 : // Clip the flow area to the margin-box because
2487 : // https://drafts.csswg.org/css-shapes-1/#relation-to-box-model-and-float-behavior
2488 : // says "When a shape is used to define a float area, the shape is clipped
2489 : // to the float’s margin box."
2490 0 : return std::max(LineLeft(), mShapeInfo->LineLeft(aBStart, aBEnd));
2491 : }
2492 :
2493 : nscoord
2494 0 : nsFloatManager::FloatInfo::LineRight(ShapeType aShapeType,
2495 0 : const nscoord aBStart,
2496 : const nscoord aBEnd) const
2497 : {
2498 0 : if (aShapeType == ShapeType::Margin) {
2499 0 : return LineRight();
2500 0 : }
2501 :
2502 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2503 0 : if (!mShapeInfo) {
2504 : return LineRight();
2505 : }
2506 : // Clip the flow area to the margin-box. See LineLeft().
2507 0 : return std::min(LineRight(), mShapeInfo->LineRight(aBStart, aBEnd));
2508 : }
2509 0 :
2510 0 : nscoord
2511 : nsFloatManager::FloatInfo::BStart(ShapeType aShapeType) const
2512 : {
2513 0 : if (aShapeType == ShapeType::Margin) {
2514 0 : return BStart();
2515 0 : }
2516 :
2517 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2518 0 : if (!mShapeInfo) {
2519 : return BStart();
2520 : }
2521 : // Clip the flow area to the margin-box. See LineLeft().
2522 0 : return std::max(BStart(), mShapeInfo->BStart());
2523 : }
2524 0 :
2525 0 : nscoord
2526 : nsFloatManager::FloatInfo::BEnd(ShapeType aShapeType) const
2527 : {
2528 0 : if (aShapeType == ShapeType::Margin) {
2529 0 : return BEnd();
2530 0 : }
2531 :
2532 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2533 0 : if (!mShapeInfo) {
2534 : return BEnd();
2535 : }
2536 : // Clip the flow area to the margin-box. See LineLeft().
2537 0 : return std::min(BEnd(), mShapeInfo->BEnd());
2538 : }
2539 0 :
2540 0 : bool
2541 : nsFloatManager::FloatInfo::IsEmpty(ShapeType aShapeType) const
2542 : {
2543 0 : if (aShapeType == ShapeType::Margin) {
2544 0 : return IsEmpty();
2545 0 : }
2546 :
2547 0 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2548 : if (!mShapeInfo) {
2549 : return IsEmpty();
2550 : }
2551 0 : return mShapeInfo->IsEmpty();
2552 : }
2553 :
2554 : bool
2555 : nsFloatManager::FloatInfo::MayNarrowInBlockDirection(ShapeType aShapeType) const
2556 : {
2557 : // This function mirrors the cases of the three argument versions of
2558 0 : // LineLeft() and LineRight(). This function returns true if and only if
2559 : // either of those functions could possibly return "narrower" values with
2560 : // increasing aBStart values. "Narrower" means closer to the far end of
2561 : // the float shape.
2562 0 : if (aShapeType == ShapeType::Margin) {
2563 0 : return false;
2564 : }
2565 :
2566 : MOZ_ASSERT(aShapeType == ShapeType::ShapeOutside);
2567 0 : if (!mShapeInfo) {
2568 : return false;
2569 : }
2570 :
2571 : return mShapeInfo->MayNarrowInBlockDirection();
2572 : }
2573 :
2574 0 : /////////////////////////////////////////////////////////////////////////////
2575 : // ShapeInfo
2576 :
2577 : /* static */ LogicalRect
2578 : nsFloatManager::ShapeInfo::ComputeShapeBoxRect(
2579 : const StyleShapeSource& aShapeOutside,
2580 0 : nsIFrame* const aFrame,
2581 : const LogicalRect& aMarginRect,
2582 0 : WritingMode aWM)
2583 : {
2584 0 : LogicalRect rect = aMarginRect;
2585 :
2586 : switch (aShapeOutside.GetReferenceBox()) {
2587 0 : case StyleGeometryBox::ContentBox:
2588 : rect.Deflate(aWM, aFrame->GetLogicalUsedPadding(aWM));
2589 : MOZ_FALLTHROUGH;
2590 0 : case StyleGeometryBox::PaddingBox:
2591 0 : rect.Deflate(aWM, aFrame->GetLogicalUsedBorder(aWM));
2592 : MOZ_FALLTHROUGH;
2593 : case StyleGeometryBox::BorderBox:
2594 : rect.Deflate(aWM, aFrame->GetLogicalUsedMargin(aWM));
2595 : break;
2596 : case StyleGeometryBox::MarginBox:
2597 0 : // Do nothing. rect is already a margin rect.
2598 : break;
2599 : case StyleGeometryBox::NoBox:
2600 : default:
2601 : MOZ_ASSERT(aShapeOutside.GetType() != StyleShapeSourceType::Box,
2602 0 : "Box source type must have <shape-box> specified!");
2603 : break;
2604 : }
2605 :
2606 0 : return rect;
2607 : }
2608 :
2609 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2610 : nsFloatManager::ShapeInfo::CreateShapeBox(
2611 : nsIFrame* const aFrame,
2612 : nscoord aShapeMargin,
2613 : const LogicalRect& aShapeBoxRect,
2614 0 : WritingMode aWM,
2615 : const nsSize& aContainerSize)
2616 : {
2617 0 : nsRect logicalShapeBoxRect
2618 : = ConvertToFloatLogical(aShapeBoxRect, aWM, aContainerSize);
2619 :
2620 0 : // Inflate logicalShapeBoxRect by aShapeMargin.
2621 0 : logicalShapeBoxRect.Inflate(aShapeMargin);
2622 0 :
2623 0 : nscoord physicalRadii[8];
2624 : bool hasRadii = aFrame->GetShapeBoxBorderRadii(physicalRadii);
2625 : if (!hasRadii) {
2626 : return MakeUnique<RoundedBoxShapeInfo>(logicalShapeBoxRect,
2627 0 : UniquePtr<nscoord[]>());
2628 0 : }
2629 :
2630 : // Add aShapeMargin to each of the radii.
2631 0 : for (nscoord& r : physicalRadii) {
2632 0 : r += aShapeMargin;
2633 0 : }
2634 :
2635 : return MakeUnique<RoundedBoxShapeInfo>(logicalShapeBoxRect,
2636 : ConvertToFloatLogical(physicalRadii,
2637 0 : aWM));
2638 : }
2639 :
2640 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2641 : nsFloatManager::ShapeInfo::CreateBasicShape(
2642 : const UniquePtr<StyleBasicShape>& aBasicShape,
2643 : nscoord aShapeMargin,
2644 : nsIFrame* const aFrame,
2645 : const LogicalRect& aShapeBoxRect,
2646 0 : const LogicalRect& aMarginRect,
2647 : WritingMode aWM,
2648 : const nsSize& aContainerSize)
2649 0 : {
2650 : switch (aBasicShape->GetShapeType()) {
2651 : case StyleBasicShapeType::Polygon:
2652 : return CreatePolygon(aBasicShape, aShapeMargin, aFrame, aShapeBoxRect,
2653 : aMarginRect, aWM, aContainerSize);
2654 0 : case StyleBasicShapeType::Circle:
2655 : case StyleBasicShapeType::Ellipse:
2656 : return CreateCircleOrEllipse(aBasicShape, aShapeMargin, aFrame,
2657 0 : aShapeBoxRect, aWM,
2658 : aContainerSize);
2659 : case StyleBasicShapeType::Inset:
2660 : return CreateInset(aBasicShape, aShapeMargin, aFrame, aShapeBoxRect,
2661 : aWM, aContainerSize);
2662 : }
2663 0 : return nullptr;
2664 : }
2665 :
2666 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2667 : nsFloatManager::ShapeInfo::CreateInset(
2668 : const UniquePtr<StyleBasicShape>& aBasicShape,
2669 : nscoord aShapeMargin,
2670 : nsIFrame* aFrame,
2671 : const LogicalRect& aShapeBoxRect,
2672 : WritingMode aWM,
2673 : const nsSize& aContainerSize)
2674 : {
2675 0 : // Use physical coordinates to compute inset() because the top, right,
2676 : // bottom and left offsets are physical.
2677 0 : // https://drafts.csswg.org/css-shapes-1/#funcdef-inset
2678 : nsRect physicalShapeBoxRect =
2679 : aShapeBoxRect.GetPhysicalRect(aWM, aContainerSize);
2680 0 : nsRect insetRect =
2681 0 : ShapeUtils::ComputeInsetRect(aBasicShape, physicalShapeBoxRect);
2682 :
2683 : nsRect logicalInsetRect =
2684 : ConvertToFloatLogical(LogicalRect(aWM, insetRect, aContainerSize),
2685 0 : aWM, aContainerSize);
2686 : nscoord physicalRadii[8];
2687 : bool hasRadii =
2688 0 : ShapeUtils::ComputeInsetRadii(aBasicShape, insetRect, physicalShapeBoxRect,
2689 0 : physicalRadii);
2690 0 :
2691 0 : // With a zero shape-margin, we will be able to use the fast constructor.
2692 : if (aShapeMargin == 0) {
2693 0 : if (!hasRadii) {
2694 0 : return MakeUnique<RoundedBoxShapeInfo>(logicalInsetRect,
2695 0 : UniquePtr<nscoord[]>());
2696 : }
2697 : return MakeUnique<RoundedBoxShapeInfo>(logicalInsetRect,
2698 : ConvertToFloatLogical(physicalRadii,
2699 : aWM));
2700 : }
2701 :
2702 0 : // With a positive shape-margin, we might still be able to use the fast
2703 0 : // constructor. With no radii, we can build a rounded box by inflating
2704 0 : // logicalInsetRect, and supplying aShapeMargin as the radius for all
2705 0 : // corners.
2706 0 : if (!hasRadii) {
2707 : logicalInsetRect.Inflate(aShapeMargin);
2708 0 : auto logicalRadii = MakeUnique<nscoord[]>(8);
2709 0 : for (int32_t i = 0; i < 8; ++i) {
2710 : logicalRadii[i] = aShapeMargin;
2711 : }
2712 : return MakeUnique<RoundedBoxShapeInfo>(logicalInsetRect,
2713 : std::move(logicalRadii));
2714 0 : }
2715 0 :
2716 0 : // If we have radii, and they have balanced/equal corners, we can inflate
2717 0 : // both logicalInsetRect and all the radii and use the fast constructor.
2718 : if (RoundedBoxShapeInfo::EachCornerHasBalancedRadii(physicalRadii)) {
2719 0 : logicalInsetRect.Inflate(aShapeMargin);
2720 0 : for (nscoord& r : physicalRadii) {
2721 0 : r += aShapeMargin;
2722 : }
2723 : return MakeUnique<RoundedBoxShapeInfo>(logicalInsetRect,
2724 : ConvertToFloatLogical(physicalRadii,
2725 : aWM));
2726 0 : }
2727 0 :
2728 0 : // With positive shape-margin and elliptical radii, we have to use the
2729 0 : // slow constructor.
2730 : nsDeviceContext* dc = aFrame->PresContext()->DeviceContext();
2731 0 : int32_t appUnitsPerDevPixel = dc->AppUnitsPerDevPixel();
2732 : return MakeUnique<RoundedBoxShapeInfo>(logicalInsetRect,
2733 : ConvertToFloatLogical(physicalRadii,
2734 : aWM),
2735 0 : aShapeMargin, appUnitsPerDevPixel);
2736 : }
2737 :
2738 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2739 : nsFloatManager::ShapeInfo::CreateCircleOrEllipse(
2740 : const UniquePtr<StyleBasicShape>& aBasicShape,
2741 : nscoord aShapeMargin,
2742 : nsIFrame* const aFrame,
2743 : const LogicalRect& aShapeBoxRect,
2744 : WritingMode aWM,
2745 : const nsSize& aContainerSize)
2746 : {
2747 0 : // Use physical coordinates to compute the center of circle() or ellipse()
2748 : // since the <position> keywords such as 'left', 'top', etc. are physical.
2749 0 : // https://drafts.csswg.org/css-shapes-1/#funcdef-ellipse
2750 : nsRect physicalShapeBoxRect =
2751 0 : aShapeBoxRect.GetPhysicalRect(aWM, aContainerSize);
2752 : nsPoint physicalCenter =
2753 : ShapeUtils::ComputeCircleOrEllipseCenter(aBasicShape, physicalShapeBoxRect);
2754 0 : nsPoint logicalCenter =
2755 0 : ConvertToFloatLogical(physicalCenter, aWM, aContainerSize);
2756 0 :
2757 : // Compute the circle or ellipse radii.
2758 0 : nsSize radii;
2759 : StyleBasicShapeType type = aBasicShape->GetShapeType();
2760 : if (type == StyleBasicShapeType::Circle) {
2761 0 : nscoord radius = ShapeUtils::ComputeCircleRadius(aBasicShape, physicalCenter,
2762 0 : physicalShapeBoxRect);
2763 : // Circles can use the three argument, math constructor for
2764 : // EllipseShapeInfo.
2765 0 : radii = nsSize(radius, radius);
2766 : return MakeUnique<EllipseShapeInfo>(logicalCenter, radii, aShapeMargin);
2767 : }
2768 0 :
2769 0 : MOZ_ASSERT(type == StyleBasicShapeType::Ellipse);
2770 0 : nsSize physicalRadii =
2771 : ShapeUtils::ComputeEllipseRadii(aBasicShape, physicalCenter,
2772 : physicalShapeBoxRect);
2773 : LogicalSize logicalRadii(aWM, physicalRadii);
2774 : radii = nsSize(logicalRadii.ISize(aWM), logicalRadii.BSize(aWM));
2775 :
2776 0 : // If radii are close to the same value, or if aShapeMargin is small
2777 0 : // enough (as specified in css pixels), then we can use the three argument
2778 0 : // constructor for EllipseShapeInfo, which uses math for a more efficient
2779 : // method of float area computation.
2780 : if (EllipseShapeInfo::ShapeMarginIsNegligible(aShapeMargin) ||
2781 : EllipseShapeInfo::RadiiAreRoughlyEqual(radii)) {
2782 : return MakeUnique<EllipseShapeInfo>(logicalCenter, radii, aShapeMargin);
2783 0 : }
2784 0 :
2785 0 : // We have to use the full constructor for EllipseShapeInfo. This
2786 0 : // computes the float area using a rasterization method.
2787 : nsDeviceContext* dc = aFrame->PresContext()->DeviceContext();
2788 : int32_t appUnitsPerDevPixel = dc->AppUnitsPerDevPixel();
2789 : return MakeUnique<EllipseShapeInfo>(logicalCenter, radii, aShapeMargin,
2790 0 : appUnitsPerDevPixel);
2791 : }
2792 :
2793 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2794 : nsFloatManager::ShapeInfo::CreatePolygon(
2795 : const UniquePtr<StyleBasicShape>& aBasicShape,
2796 : nscoord aShapeMargin,
2797 : nsIFrame* const aFrame,
2798 : const LogicalRect& aShapeBoxRect,
2799 : const LogicalRect& aMarginRect,
2800 : WritingMode aWM,
2801 : const nsSize& aContainerSize)
2802 : {
2803 0 : // Use physical coordinates to compute each (xi, yi) vertex because CSS
2804 : // represents them using physical coordinates.
2805 : // https://drafts.csswg.org/css-shapes-1/#funcdef-polygon
2806 : nsRect physicalShapeBoxRect =
2807 0 : aShapeBoxRect.GetPhysicalRect(aWM, aContainerSize);
2808 :
2809 : // Get physical vertices.
2810 0 : nsTArray<nsPoint> vertices =
2811 0 : ShapeUtils::ComputePolygonVertices(aBasicShape, physicalShapeBoxRect);
2812 :
2813 : // Convert all the physical vertices to logical.
2814 0 : for (nsPoint& vertex : vertices) {
2815 0 : vertex = ConvertToFloatLogical(vertex, aWM, aContainerSize);
2816 : }
2817 :
2818 0 : if (aShapeMargin == 0) {
2819 : return MakeUnique<PolygonShapeInfo>(std::move(vertices));
2820 : }
2821 :
2822 0 : nsRect marginRect = ConvertToFloatLogical(aMarginRect, aWM, aContainerSize);
2823 0 :
2824 0 : // We have to use the full constructor for PolygonShapeInfo. This
2825 : // computes the float area using a rasterization method.
2826 : int32_t appUnitsPerDevPixel = aFrame->PresContext()->AppUnitsPerDevPixel();
2827 : return MakeUnique<PolygonShapeInfo>(std::move(vertices), aShapeMargin,
2828 0 : appUnitsPerDevPixel, marginRect);
2829 : }
2830 :
2831 : /* static */ UniquePtr<nsFloatManager::ShapeInfo>
2832 : nsFloatManager::ShapeInfo::CreateImageShape(
2833 : const UniquePtr<nsStyleImage>& aShapeImage,
2834 : float aShapeImageThreshold,
2835 : nscoord aShapeMargin,
2836 : nsIFrame* const aFrame,
2837 0 : const LogicalRect& aMarginRect,
2838 : WritingMode aWM,
2839 : const nsSize& aContainerSize)
2840 : {
2841 0 : MOZ_ASSERT(aShapeImage ==
2842 0 : aFrame->StyleDisplay()->mShapeOutside.GetShapeImage(),
2843 : "aFrame should be the frame that we got aShapeImage from");
2844 0 :
2845 : nsImageRenderer imageRenderer(aFrame, aShapeImage.get(),
2846 : nsImageRenderer::FLAG_SYNC_DECODE_IMAGES);
2847 :
2848 : if (!imageRenderer.PrepareImage()) {
2849 0 : // The image is not ready yet.
2850 : return nullptr;
2851 : }
2852 0 :
2853 0 : nsRect contentRect = aFrame->GetContentRect();
2854 :
2855 0 : // Create a draw target and draw shape image on it.
2856 0 : nsDeviceContext* dc = aFrame->PresContext()->DeviceContext();
2857 : int32_t appUnitsPerDevPixel = dc->AppUnitsPerDevPixel();
2858 : LayoutDeviceIntSize contentSizeInDevPixels =
2859 : LayoutDeviceIntSize::FromAppUnitsRounded(contentRect.Size(),
2860 0 : appUnitsPerDevPixel);
2861 :
2862 : // Use empty CSSSizeOrRatio to force set the preferred size as the frame's
2863 0 : // content box size.
2864 0 : imageRenderer.SetPreferredSize(CSSSizeOrRatio(), contentRect.Size());
2865 0 :
2866 0 : RefPtr<gfx::DrawTarget> drawTarget =
2867 : gfxPlatform::GetPlatform()->CreateOffscreenCanvasDrawTarget(
2868 : contentSizeInDevPixels.ToUnknownSize(),
2869 : gfx::SurfaceFormat::A8);
2870 0 : if (!drawTarget) {
2871 0 : return nullptr;
2872 : }
2873 :
2874 0 : RefPtr<gfxContext> context = gfxContext::CreateOrNull(drawTarget);
2875 : MOZ_ASSERT(context); // already checked the target above
2876 0 :
2877 : ImgDrawResult result =
2878 : imageRenderer.DrawShapeImage(aFrame->PresContext(), *context);
2879 :
2880 : if (result != ImgDrawResult::SUCCESS) {
2881 0 : return nullptr;
2882 0 : }
2883 0 :
2884 : // Retrieve the pixel image buffer to create the image shape info.
2885 0 : RefPtr<SourceSurface> sourceSurface = drawTarget->Snapshot();
2886 : RefPtr<DataSourceSurface> dataSourceSurface = sourceSurface->GetDataSurface();
2887 : DataSourceSurface::ScopedMap map(dataSourceSurface, DataSourceSurface::READ);
2888 :
2889 0 : if (!map.IsMapped()) {
2890 : return nullptr;
2891 : }
2892 0 :
2893 : MOZ_ASSERT(sourceSurface->GetSize() == contentSizeInDevPixels.ToUnknownSize(),
2894 0 : "Who changes the size?");
2895 0 :
2896 : nsRect marginRect = aMarginRect.GetPhysicalRect(aWM, aContainerSize);
2897 :
2898 : uint8_t* alphaPixels = map.GetData();
2899 0 : int32_t stride = map.GetStride();
2900 :
2901 : // NOTE: ImageShapeInfo constructor does not keep a persistent copy of
2902 : // alphaPixels; it's only used during the constructor to compute pixel ranges.
2903 : return MakeUnique<ImageShapeInfo>(alphaPixels,
2904 : stride,
2905 : contentSizeInDevPixels,
2906 : appUnitsPerDevPixel,
2907 : aShapeImageThreshold,
2908 0 : aShapeMargin,
2909 : contentRect,
2910 : marginRect,
2911 : aWM,
2912 0 : aContainerSize);
2913 : }
2914 :
2915 : /* static */ nscoord
2916 : nsFloatManager::ShapeInfo::ComputeEllipseLineInterceptDiff(
2917 : const nscoord aShapeBoxBStart, const nscoord aShapeBoxBEnd,
2918 : const nscoord aBStartCornerRadiusL, const nscoord aBStartCornerRadiusB,
2919 : const nscoord aBEndCornerRadiusL, const nscoord aBEndCornerRadiusB,
2920 : const nscoord aBandBStart, const nscoord aBandBEnd)
2921 : {
2922 : // An example for the band intersecting with the top right corner of an
2923 : // ellipse with writing-mode horizontal-tb.
2924 : //
2925 : // lineIntercept lineDiff
2926 : // | |
2927 : // +---------------------------------|-------|-+---- aShapeBoxBStart
2928 : // | ##########^ | | |
2929 : // | ##############|#### | | |
2930 : // +---------#################|######|-------|-+---- aBandBStart
2931 : // | ###################|######|## | |
2932 : // | aBStartCornerRadiusB |######|### | |
2933 : // | ######################|######|##### | |
2934 : // +---#######################|<-----------><->^---- aBandBEnd
2935 : // | ########################|############## |
2936 : // | ########################|############## |---- b
2937 : // | #########################|############### |
2938 : // | ######################## v<-------------->v
2939 : // |###################### aBStartCornerRadiusL|
2940 : // |###########################################|
2941 : // |###########################################|
2942 : // |###########################################|
2943 : // |###########################################|
2944 : // | ######################################### |
2945 : // | ######################################### |
2946 : // | ####################################### |
2947 : // | ####################################### |
2948 : // | ##################################### |
2949 : // | ################################### |
2950 : // | ############################### |
2951 : // | ############################# |
2952 : // | ######################### |
2953 0 : // | ################### |
2954 0 : // | ########### |
2955 : // +-------------------------------------------+----- aShapeBoxBEnd
2956 0 :
2957 : NS_ASSERTION(aShapeBoxBStart <= aShapeBoxBEnd, "Bad shape box coordinates!");
2958 : NS_ASSERTION(aBandBStart <= aBandBEnd, "Bad band coordinates!");
2959 :
2960 0 : nscoord lineDiff = 0;
2961 0 :
2962 0 : // If the band intersects both the block-start and block-end corners, we
2963 : // don't need to enter either branch because the correct lineDiff is 0.
2964 0 : if (aBStartCornerRadiusB > 0 &&
2965 : aBandBEnd >= aShapeBoxBStart &&
2966 0 : aBandBEnd <= aShapeBoxBStart + aBStartCornerRadiusB) {
2967 0 : // The band intersects only the block-start corner.
2968 0 : nscoord b = aBStartCornerRadiusB - (aBandBEnd - aShapeBoxBStart);
2969 0 : nscoord lineIntercept =
2970 : XInterceptAtY(b, aBStartCornerRadiusL, aBStartCornerRadiusB);
2971 : lineDiff = aBStartCornerRadiusL - lineIntercept;
2972 0 : } else if (aBEndCornerRadiusB > 0 &&
2973 : aBandBStart >= aShapeBoxBEnd - aBEndCornerRadiusB &&
2974 0 : aBandBStart <= aShapeBoxBEnd) {
2975 0 : // The band intersects only the block-end corner.
2976 : nscoord b = aBEndCornerRadiusB - (aShapeBoxBEnd - aBandBStart);
2977 : nscoord lineIntercept =
2978 0 : XInterceptAtY(b, aBEndCornerRadiusL, aBEndCornerRadiusB);
2979 : lineDiff = aBEndCornerRadiusL - lineIntercept;
2980 : }
2981 :
2982 0 : return lineDiff;
2983 : }
2984 :
2985 : /* static */ nscoord
2986 : nsFloatManager::ShapeInfo::XInterceptAtY(const nscoord aY,
2987 0 : const nscoord aRadiusX,
2988 0 : const nscoord aRadiusY)
2989 : {
2990 : // Solve for x in the ellipse equation (x/radiusX)^2 + (y/radiusY)^2 = 1.
2991 : MOZ_ASSERT(aRadiusY > 0);
2992 0 : return aRadiusX * std::sqrt(1 - (aY * aY) / double(aRadiusY * aRadiusY));
2993 : }
2994 :
2995 : /* static */ nsPoint
2996 : nsFloatManager::ShapeInfo::ConvertToFloatLogical(
2997 0 : const nsPoint& aPoint,
2998 : WritingMode aWM,
2999 0 : const nsSize& aContainerSize)
3000 : {
3001 : LogicalPoint logicalPoint(aWM, aPoint, aContainerSize);
3002 : return nsPoint(logicalPoint.LineRelative(aWM, aContainerSize),
3003 0 : logicalPoint.B(aWM));
3004 : }
3005 :
3006 0 : /* static */ UniquePtr<nscoord[]>
3007 : nsFloatManager::ShapeInfo::ConvertToFloatLogical(const nscoord aRadii[8],
3008 : WritingMode aWM)
3009 : {
3010 : UniquePtr<nscoord[]> logicalRadii(new nscoord[8]);
3011 0 :
3012 0 : // Get the physical side for line-left and line-right since border radii
3013 0 : // are on the physical axis.
3014 0 : Side lineLeftSide =
3015 0 : aWM.PhysicalSide(aWM.LogicalSideForLineRelativeDir(eLineRelativeDirLeft));
3016 0 : logicalRadii[eCornerTopLeftX] =
3017 0 : aRadii[SideToHalfCorner(lineLeftSide, true, false)];
3018 0 : logicalRadii[eCornerTopLeftY] =
3019 0 : aRadii[SideToHalfCorner(lineLeftSide, true, true)];
3020 : logicalRadii[eCornerBottomLeftX] =
3021 : aRadii[SideToHalfCorner(lineLeftSide, false, false)];
3022 0 : logicalRadii[eCornerBottomLeftY] =
3023 0 : aRadii[SideToHalfCorner(lineLeftSide, false, true)];
3024 0 :
3025 0 : Side lineRightSide =
3026 0 : aWM.PhysicalSide(aWM.LogicalSideForLineRelativeDir(eLineRelativeDirRight));
3027 0 : logicalRadii[eCornerTopRightX] =
3028 0 : aRadii[SideToHalfCorner(lineRightSide, false, false)];
3029 0 : logicalRadii[eCornerTopRightY] =
3030 0 : aRadii[SideToHalfCorner(lineRightSide, false, true)];
3031 : logicalRadii[eCornerBottomRightX] =
3032 0 : aRadii[SideToHalfCorner(lineRightSide, true, false)];
3033 : logicalRadii[eCornerBottomRightY] =
3034 : aRadii[SideToHalfCorner(lineRightSide, true, true)];
3035 :
3036 : if (aWM.IsLineInverted()) {
3037 : // When IsLineInverted() is true, i.e. aWM is vertical-lr,
3038 0 : // line-over/line-under are inverted from block-start/block-end. So the
3039 0 : // relationship reverses between which corner comes first going
3040 0 : // clockwise, and which corner is block-start versus block-end. We need
3041 0 : // to swap the values stored in top and bottom corners.
3042 : std::swap(logicalRadii[eCornerTopLeftX], logicalRadii[eCornerBottomLeftX]);
3043 : std::swap(logicalRadii[eCornerTopLeftY], logicalRadii[eCornerBottomLeftY]);
3044 0 : std::swap(logicalRadii[eCornerTopRightX], logicalRadii[eCornerBottomRightX]);
3045 : std::swap(logicalRadii[eCornerTopRightY], logicalRadii[eCornerBottomRightY]);
3046 : }
3047 :
3048 0 : return logicalRadii;
3049 : }
3050 :
3051 : /* static */ size_t
3052 : nsFloatManager::ShapeInfo::MinIntervalIndexContainingY(
3053 : const nsTArray<nsRect>& aIntervals,
3054 : const nscoord aTargetY)
3055 0 : {
3056 0 : // Perform a binary search to find the minimum index of an interval
3057 0 : // that contains aTargetY. If no such interval exists, return a value
3058 0 : // equal to the number of intervals.
3059 0 : size_t startIdx = 0;
3060 : size_t endIdx = aIntervals.Length();
3061 : while (startIdx < endIdx) {
3062 0 : size_t midIdx = startIdx + (endIdx - startIdx) / 2;
3063 0 : if (aIntervals[midIdx].ContainsY(aTargetY)) {
3064 0 : return midIdx;
3065 : }
3066 : nscoord midY = aIntervals[midIdx].Y();
3067 : if (midY < aTargetY) {
3068 : startIdx = midIdx + 1;
3069 : } else {
3070 : endIdx = midIdx;
3071 : }
3072 : }
3073 :
3074 0 : return endIdx;
3075 : }
3076 :
3077 : /* static */ nscoord
3078 : nsFloatManager::ShapeInfo::LineEdge(const nsTArray<nsRect>& aIntervals,
3079 0 : const nscoord aBStart,
3080 : const nscoord aBEnd,
3081 : bool aIsLineLeft)
3082 : {
3083 : MOZ_ASSERT(aBStart <= aBEnd,
3084 : "The band's block start is greater than its block end?");
3085 :
3086 : // Find all the intervals whose rects overlap the aBStart to
3087 : // aBEnd range, and find the most constraining inline edge
3088 : // depending on the value of aLeft.
3089 :
3090 0 : // Since the intervals are stored in block-axis order, we need
3091 : // to find the first interval that overlaps aBStart and check
3092 0 : // succeeding intervals until we get past aBEnd.
3093 0 :
3094 0 : nscoord lineEdge = aIsLineLeft ? nscoord_MAX : nscoord_MIN;
3095 :
3096 : size_t intervalCount = aIntervals.Length();
3097 : for (size_t i = MinIntervalIndexContainingY(aIntervals, aBStart);
3098 0 : i < intervalCount; ++i) {
3099 0 : // We can always get the bCoord from the intervals' mLineLeft,
3100 0 : // since the y() coordinate is duplicated in both points in the
3101 : // interval.
3102 : auto& interval = aIntervals[i];
3103 : nscoord bCoord = interval.Y();
3104 0 : if (bCoord >= aBEnd) {
3105 0 : break;
3106 : }
3107 0 : // Get the edge from the interval point indicated by aLeft.
3108 : if (aIsLineLeft) {
3109 : lineEdge = std::min(lineEdge, interval.X());
3110 : } else {
3111 0 : lineEdge = std::max(lineEdge, interval.XMost());
3112 : }
3113 : }
3114 :
3115 0 : return lineEdge;
3116 : }
3117 :
3118 : /* static */ nsFloatManager::ShapeInfo::dfType
3119 : nsFloatManager::ShapeInfo::CalcUsedShapeMargin5X(
3120 : nscoord aShapeMargin,
3121 : int32_t aAppUnitsPerDevPixel)
3122 : {
3123 : // Our distance field has to be able to hold values equal to the
3124 : // maximum shape-margin value that we care about faithfully rendering,
3125 : // times 5. A 16-bit unsigned int can represent up to ~ 65K which means
3126 : // we can handle a margin up to ~ 13K device pixels. That's good enough
3127 : // for practical usage. Any supplied shape-margin value higher than this
3128 : // maximum will be clamped.
3129 0 : static const float MAX_MARGIN_5X_FLOAT = (float)MAX_MARGIN_5X;
3130 0 :
3131 0 : // Convert aShapeMargin to dev pixels, convert that into 5x-dev-pixel
3132 : // space, then clamp to MAX_MARGIN_5X_FLOAT.
3133 : float shapeMarginDevPixels5X = 5.0f *
3134 : NSAppUnitsToFloatPixels(aShapeMargin, aAppUnitsPerDevPixel);
3135 : NS_WARNING_ASSERTION(shapeMarginDevPixels5X <= MAX_MARGIN_5X_FLOAT,
3136 : "shape-margin is too large and is being clamped.");
3137 :
3138 : // We calculate a minimum in float space, which takes care of any overflow
3139 : // or infinity that may have occurred earlier from multiplication of
3140 : // too-large aShapeMargin values.
3141 : float usedMargin5XFloat = std::min(shapeMarginDevPixels5X,
3142 : MAX_MARGIN_5X_FLOAT);
3143 : return (dfType)NSToIntRound(usedMargin5XFloat);
3144 : }
3145 :
3146 : //----------------------------------------------------------------------
3147 :
3148 : nsAutoFloatManager::~nsAutoFloatManager()
3149 : {
3150 : // Restore the old float manager in the reflow input if necessary.
3151 : if (mNew) {
3152 : #ifdef DEBUG
3153 : if (nsBlockFrame::gNoisyFloatManager) {
3154 : printf("restoring old float manager %p\n", mOld);
3155 : }
3156 : #endif
3157 :
3158 : mReflowInput.mFloatManager = mOld;
3159 :
3160 : #ifdef DEBUG
3161 : if (nsBlockFrame::gNoisyFloatManager) {
3162 : if (mOld) {
3163 : mReflowInput.mFrame->ListTag(stdout);
3164 : printf(": float manager %p after reflow\n", mOld);
3165 : mOld->List(stdout);
3166 : }
3167 : }
3168 : #endif
3169 : }
3170 : }
3171 :
3172 : void
3173 : nsAutoFloatManager::CreateFloatManager(nsPresContext *aPresContext)
3174 : {
3175 : MOZ_ASSERT(!mNew, "Redundant call to CreateFloatManager!");
3176 :
3177 : // Create a new float manager and install it in the reflow
3178 : // input. `Remember' the old float manager so we can restore it
3179 : // later.
3180 : mNew = MakeUnique<nsFloatManager>(aPresContext->PresShell(),
3181 : mReflowInput.GetWritingMode());
3182 :
3183 : #ifdef DEBUG
3184 : if (nsBlockFrame::gNoisyFloatManager) {
3185 : printf("constructed new float manager %p (replacing %p)\n",
3186 : mNew.get(), mReflowInput.mFloatManager);
3187 : }
3188 : #endif
3189 :
3190 : // Set the float manager in the existing reflow input.
3191 : mOld = mReflowInput.mFloatManager;
3192 : mReflowInput.mFloatManager = mNew.get();
3193 : }
|
