Implement the rendering of basic shape polygon() for CSS shape-outside

RESOLVED FIXED in Firefox 55

Status

()

RESOLVED FIXED
2 years ago
a year ago

People

(Reporter: TYLin, Assigned: TYLin)

Tracking

(Blocks: 1 bug, {dev-doc-complete})

Trunk
mozilla55
dev-doc-complete
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

(URL)

Attachments

(6 attachments, 8 obsolete attachments)

1.56 KB, patch
TYLin
: review+
Details | Diff | Splinter Review
1.21 KB, patch
TYLin
: review+
Details | Diff | Splinter Review
10.68 KB, patch
TYLin
: review+
Details | Diff | Splinter Review
9.44 KB, patch
dholbert
: review+
Details | Diff | Splinter Review
5.22 KB, patch
TYLin
: review+
Details | Diff | Splinter Review
71.93 KB, patch
TYLin
: review+
Details | Diff | Splinter Review
(Assignee)

Description

2 years ago
This bug is for implementing shape-outside: polygon().
Blocks: 1334227
(Assignee)

Updated

2 years ago
Assignee: nobody → tlin
Status: NEW → ASSIGNED
(Assignee)

Comment 1

2 years ago
Created attachment 8843949 [details] [diff] [review]
Part 1 - Annotate EllipseShapeInfo as 'final'. (v1)
(Assignee)

Comment 2

2 years ago
Created attachment 8843950 [details] [diff] [review]
Part 2 - Rewrite the return expression of ComputeCircleOrEllipseCenter(). (v1)
(Assignee)

Comment 3

2 years ago
Created attachment 8843951 [details] [diff] [review]
Part 3 - Remove unneeded WritingMode parameter. (v1)

Remove WritingMode parameter from LineRight() and LineLeft() in both
FloatInfo and ShapeInfo.

Bug 1316549 Part 3 added the parameter to compute the border radii under
writing-modes correctly. However, bug 1326407 Part 6 already cached the
border radii, so the WritingMode parameter is no longer needed.
(Assignee)

Comment 4

2 years ago
Created attachment 8843952 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v1)
(Assignee)

Comment 5

2 years ago
Created attachment 8843953 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v1)

The <fill-rule> in the polygon() syntax is not handled because it doesn't
matter to shape-outside at all.

The reftests are numbered from 018 to avoid conflict with the w3c upstream
ones according to this list.
https://test.csswg.org/harness/results/css-shapes-1_dev/grouped/

Reftest 018 to 025 are under various writing-modes, and 026 to 029 are
testing empty float area.
(Assignee)

Comment 6

2 years ago
David, would you help review these patches, please? Or let me know if I should redirect the review to other reviewers.
Flags: needinfo?(dbaron)
Perhaps redirect the review to :mats or :dholbert?  (Maybe ask them how their review queues are?)
Flags: needinfo?(dbaron)
(Assignee)

Comment 8

2 years ago
Daniel, do you have free time and interesting in reviewing this?
Flags: needinfo?(dholbert)
Sure, I can review this over the next day or so.
Comment on attachment 8843949 [details] [diff] [review]
Part 1 - Annotate EllipseShapeInfo as 'final'. (v1)

Review of attachment 8843949 [details] [diff] [review]:
-----------------------------------------------------------------

r=me
Attachment #8843949 - Flags: review+
Comment on attachment 8843950 [details] [diff] [review]
Part 2 - Rewrite the return expression of ComputeCircleOrEllipseCenter(). (v1)

Review of attachment 8843950 [details] [diff] [review]:
-----------------------------------------------------------------

Nice. r=me
Attachment #8843950 - Flags: review+
Comment on attachment 8843951 [details] [diff] [review]
Part 3 - Remove unneeded WritingMode parameter. (v1)

Review of attachment 8843951 [details] [diff] [review]:
-----------------------------------------------------------------

r=me, though you might want to tweak the commit message as noted below. Quoting the extended commit message:
> Bug 1316549 Part 3 added the parameter to compute the border radii under
> writing-modes correctly. However, bug 1326407 Part 6 already cached the
> border radii, so the WritingMode parameter is no longer needed.

I think you want s/already cached/later made us cache/

(Right now, the usage of "already" makes it sounds like we were *already* caching the WM *when Bug 1316549 Part 3* landed. And I think that's not what you mean to say here.)
Attachment #8843951 - Flags: review+
Comment on attachment 8843952 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v1)

Review of attachment 8843952 [details] [diff] [review]:
-----------------------------------------------------------------

I'd like to see the updated patch, so I'm marking this as r- for now.

::: layout/base/ShapeUtils.cpp
@@ +160,5 @@
> +  const nsTArray<nsStyleCoord>& coords = aBasicShape->Coordinates();
> +  MOZ_ASSERT(coords.Length() % 2 == 0 &&
> +             coords.Length() >= 2, "Wrong number of arguments!");
> +
> +  for (size_t i = 0; i < coords.Length(); i += 2) {

For extra-security's sake, could we make the loop-condition (the length comparison) use "i + 1" rather than "i"?

We deref coords[i+1] inside this loop, so we really should be sure coords is long enough to have something at that index.  "i < Length()" isn't a strong enough condition to ensure that.

(You do have assertions that 'coords' has an even length, which kinda means we're OK, but that won't be enforced here in opt builds, so we can't really rely on it as a guarantee of this loop's safety.)

@@ +161,5 @@
> +  MOZ_ASSERT(coords.Length() % 2 == 0 &&
> +             coords.Length() >= 2, "Wrong number of arguments!");
> +
> +  for (size_t i = 0; i < coords.Length(); i += 2) {
> +    aOutVertices.AppendElement(

Before the "for" loop here, you should prompt aOutVertices to allocate its full size, so that it doesn't just grow bit-by-bit with successive AppendElement calls. (Which is its default beahvior, using a doubling strategy or somesuch)

I believe you want:
  aOutVertices.EnsureCapacity(coords.Length() / 2);

::: layout/base/ShapeUtils.h
@@ +73,5 @@
>      const nsRect& aInsetRect,
>      const nsRect& aRefBox,
>      nscoord aRadii[8]);
> +
> +  // Compute the vertices for an polygon.

s/an/a/

@@ +78,5 @@
> +  // @param aRefBox the reference box of the polygon.
> +  // @param aOutVertices the returned vertices in app units; the coordinate
> +  //                     space is the same as aRefBox.
> +  static void ComputePolygonVertices(
> +    mozilla::StyleBasicShape* const aBasicShape,

This "const" here doesn't seem particularly useful.

I think you really want this to be a *pointer to a const value*, rather than a const pointer-address. (Nobody really cares if the function stomps on the pointer *address*, internally.  But the *object pointed to* is expected to stay unmodified, I expect!)

So this really wants to be:
  "const mozilla::StyleBasicShape* aBasicShape"

This affects pretty much every (preexisting) function in this ShapeUtils file -- could you fix those ones up in a helper patch (or a helper bug), if I'm not misunderstanding something?

::: layout/svg/nsCSSClipPathInstance.cpp
@@ +159,3 @@
>    nscoord appUnitsPerDevPixel =
>      mTargetFrame->PresContext()->AppUnitsPerDevPixel();
> +  builder->MoveTo(Point(vertices[0].x, vertices[0].y) / appUnitsPerDevPixel);

It's not clear from just looking at this code here how/why we know that it's safe to do vertices[0] -- i.e. how we know it's is nonempty.  (It's a little clearer after looking at the internals of ComputePolygonVertices, but even then we're kind of relying on assertions.)

Let's wrap everything after ComputePolygonVertices in a check, like so:

  if (vertices.IsEmpty()) {
    MOZ_ASSERT_UNREACHABLE("ComputePolygonVertices should've given us some vertices");
  } else {
    nscoord appUnitsPerDevPixel = [...]
    builder-MoveTo(...)
    for(...)
  }
  builder->Close();
  return builder->Finish();

@@ +159,5 @@
>    nscoord appUnitsPerDevPixel =
>      mTargetFrame->PresContext()->AppUnitsPerDevPixel();
> +  builder->MoveTo(Point(vertices[0].x, vertices[0].y) / appUnitsPerDevPixel);
> +  for (size_t i = 1; i < vertices.Length(); ++i) {
> +    builder->LineTo(Point(vertices[i].x, vertices[i].y) / appUnitsPerDevPixel);

This should really be:
  builder->LineTo(NSPointToPoint(vertices[i], appUnitsPerDevPixel));

https://dxr.mozilla.org/mozilla-central/rev/b7e42143bbbc9dc3e5c05bd1e93b6485ce1d0ad4/layout/base/nsLayoutUtils.h#2986-2990

I think that's equivalent to what you have here, but it's a little cleaner.
Attachment #8843952 - Flags: review-
Comment on attachment 8843953 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v1)

Review of attachment 8843953 [details] [diff] [review]:
-----------------------------------------------------------------

Partial review of part 4 -- haven't been through the whole thing yet:

::: layout/generic/nsFloatManager.cpp
@@ +598,5 @@
> +
> +nsFloatManager::PolygonShapeInfo::PolygonShapeInfo(nsTArray<nsPoint>&& aVertices)
> +  : mVertices(aVertices)
> +{
> +  // Polygons with less than three vertices result in an empty area.

s/less/fewer/

( https://en.oxforddictionaries.com/usage/less-or-fewer )

@@ +607,5 @@
> +  }
> +
> +  auto Determinant = [] (const nsPoint& aP0, const nsPoint& aP1) {
> +    // The determinant of the two points equals to 0 means that they're
> +    // colinear with respect to the origin.

This wording is a bit hard to parse. How about:
  // If the determinant of two points is 0, that means they're ...

THOUGH, this comment doesn't really belong inside of this lambda. This lambda is just implementing the determinant -- it's not doing any comparisons to 0 or concerning itself with colinear points.

I think this comment maybe wants to move further down, underneath your "Compute the number of colinear vertices" comment maybe? (merging together with that comment)

@@ +612,5 @@
> +    // https://en.wikipedia.org/wiki/Determinant#2_.C3.97_2_matrices
> +    return aP0.x * aP1.y - aP0.y * aP1.x;
> +  };
> +
> +  // Compute the number of colinear vertices.

This comment isn't quite accurate.  I think it really wants to say:
 // Compute the number of vertices that are colinear with the first two.
BUT, don't use that language, because I don't think you actually need to bother finding the number -- you really just need to determine **whether there is at least one such point**.

So I think this really wants to say:
  // See if we have any vertices that are non-colinear with the first two.
  // (If a polygon's vertices are all colinear, it encloses no area.)
  ...
  bool isEntirelyColinear = true;
  for (size_t i = 2 ...) {
    // If the determinant of two points is 0, [...]
    // Therefore if it's nonzero, then they're non-colinear with respect to the origin.
    if (Determinant(...) != 0) {
      isEntirelyColinear = false;
      break;
    }
  }

  if (isEntirelyColinear) {
    mEmpty = true;
    return;
  }

@@ +633,5 @@
> +  // mBStart and mBEnd are the lower and the upper bounds of all the
> +  // vertex.y, respectively.
> +  for (const nsPoint& vertex : mVertices) {
> +    mBStart = std::min(mBStart, vertex.y);
> +    mBEnd = std::max(mBEnd, vertex.y);

This "y" + "B" intermixing looks suspiciously writing-mode-unfriendly.  Is "y" really the y-axis here?  If so, does that mean this is bogus for vertical writing-mode-cases?

[EDIT: later on I'm now seeing that (despite the nsPoint type & "x"/"y" variables) these vertices are probably in logical space, produced by ConvertToFloatLogical. Please extend the comment here to make that clearer, so that the y-->B is not as much of a red-flag.]

@@ +641,5 @@
> +nscoord
> +nsFloatManager::PolygonShapeInfo::LineLeft(const nscoord aBStart,
> +                                           const nscoord aBEnd) const
> +{
> +  return ComputeLineIntercept(aBStart, aBEnd, std::min<nscoord>, nscoord_MAX);

Why the std::min<nscoord> vs. nscoord_MAX here? (and vice versa in the next function, LineRight)  We probably should just use the nscoord_MIN & nscoord_MAX macros consistently, and avoid std::min, since all values more extreme than nscoord_MAX/MIN are kind of forbidden/sentinels/bogus.

@@ +664,5 @@
> +
> +  size_t len = mVertices.Length();
> +  nscoord lineIntercept = aLineInterceptInitialValue;
> +
> +  // Iterate each line segments {p0, p1}, {p1, p2}, ..., {pn, p0}.

s/segments/segment/  ("each" is singular)

@@ +716,5 @@
> +{
> +  // Solve for x in the linear equation: x = x1 + (y-y1) * (x2-x1) / (y2-y1),
> +  // where p1 = (x1, y1) and p2 = (x2, y2).
> +
> +  MOZ_ASSERT(aP1.y <= aY && aY <= aP2.y);

Unexpained assertions are an anti-pattern, except for trivial stuff like obvious null-checks.  Please add a string to explain what's being asserted/why.

@@ +765,5 @@
>  
>      switch (basicShape->GetShapeType()) {
>        case StyleBasicShapeType::Polygon:
> +        mShapeInfo =
> +          ShapeInfo::CreatePolygon(basicShape, shapeBoxRect, aWM, aContainerSize);

This line is too long. Please wrap before "aContainerSize" like the case below does.

@@ +1032,5 @@
> +
> +  nsTArray<nsPoint> logicalVertices(physicalVertices.Length());
> +  for (const nsPoint& vertex : physicalVertices) {
> +    logicalVertices.AppendElement(
> +      ConvertToFloatLogical(vertex, aWM, aContainerSize));

Rather than having two separate nsTArrays here (of the same type & representing the same data), how about we rename physicalVertices to just "vertices", and add a code comment saying up-front that it's physical, and then that we're converting it to logical in the loop here?

And the loop would look like:
   for (nsPoint& vertex : vertices) {
     vertex = ConvertToFloatLogical(vertex, aWM, aContainerSize);
   }

That would save us some memory here.

::: layout/generic/nsFloatManager.h
@@ +393,5 @@
>        mozilla::WritingMode aWM,
>        const nsSize& aContainerSize);
>  
> +    static mozilla::UniquePtr<ShapeInfo> CreatePolygon(
> +      mozilla::StyleBasicShape* const aBasicShape,

As with the previous part, I'm pretty sure the const is in the wrong spot here (it's making the address const, rather than the value stored in that address).

You probably want "const mozilla::StyleBasicShape*" to give standard guarantees for input-variable-not-being-touched.

@@ +526,5 @@
> +                                 const nsPoint& aP1,
> +                                 const nsPoint& aP2);
> +
> +    // The vertices of the polygon in the float manager's coordinate space.
> +    nsTArray<nsPoint> mVertices;

Could you make this "const nsTArray"?  It looks like this is never modified after receiving its value in the constructor init list.  So, we might as well document/enforce that by making it const.

@@ +527,5 @@
> +                                 const nsPoint& aP2);
> +
> +    // The vertices of the polygon in the float manager's coordinate space.
> +    nsTArray<nsPoint> mVertices;
> +    // mEmpty is true means the polygon enclose no area.

The wording is a little awkward here.  This would be a bit clearer:
  // If mEmpty is true, that means the polygon encloses no area.

@@ +530,5 @@
> +    nsTArray<nsPoint> mVertices;
> +    // mEmpty is true means the polygon enclose no area.
> +    bool mEmpty = false;
> +    // Computed block start and block end of the polygon shape.
> +    nscoord mBStart = nscoord_MAX;

You should briefly explain what it means if mBStart is larger than mBEnd, since that's a confusing scenario to be in, and it also happens to be the initial state of this object. :)  (mBStart is initially nscoord_MAX and mBEnd is initially nscoord_MIN -- and they're left that way forever in some cases, too.)
Attachment #8843953 - Flags: review-
(Assignee)

Comment 15

2 years ago
Created attachment 8844935 [details] [diff] [review]
Part 1 - Annotate EllipseShapeInfo as 'final'. (v2)

Change r=dholbert.
Attachment #8844935 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8843949 - Attachment is obsolete: true
(Assignee)

Comment 16

2 years ago
Created attachment 8844936 [details] [diff] [review]
Part 2 - Rewrite the return expression of ComputeCircleOrEllipseCenter(). (v2)

Change r=dholbert
Attachment #8844936 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8843950 - Attachment is obsolete: true
(Assignee)

Comment 17

2 years ago
Created attachment 8844937 [details] [diff] [review]
Part 3 - Remove unneeded WritingMode parameter. (v2)

Addressed comment 12, and change r=dholbert.
Attachment #8844937 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8843951 - Attachment is obsolete: true
(Assignee)

Comment 18

2 years ago
Created attachment 8844939 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v2)

Addressed comment 13.
Attachment #8844939 - Flags: review?(dholbert)
(Assignee)

Updated

2 years ago
Attachment #8843952 - Attachment is obsolete: true
(Assignee)

Comment 19

2 years ago
Created attachment 8844940 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v2)

Addressed comment 14.
Attachment #8844940 - Flags: review?(dholbert)
(Assignee)

Updated

2 years ago
Attachment #8843953 - Attachment is obsolete: true
(Assignee)

Comment 20

2 years ago
Created attachment 8844941 [details] [diff] [review]
Part 6 - Convert aBasicShape to a pointer to a const value. (v1)

To address reviewer's comments in bug 1326409 comment 13 and comment 14.
Attachment #8844941 - Flags: review?(dholbert)
(Assignee)

Comment 21

2 years ago
Comment on attachment 8843952 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v1)

Review of attachment 8843952 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/base/ShapeUtils.cpp
@@ +161,5 @@
> +  MOZ_ASSERT(coords.Length() % 2 == 0 &&
> +             coords.Length() >= 2, "Wrong number of arguments!");
> +
> +  for (size_t i = 0; i < coords.Length(); i += 2) {
> +    aOutVertices.AppendElement(

OK. I added SetCapacity() because EnsureCapacity() is not an public API.

::: layout/base/ShapeUtils.h
@@ +78,5 @@
> +  // @param aRefBox the reference box of the polygon.
> +  // @param aOutVertices the returned vertices in app units; the coordinate
> +  //                     space is the same as aRefBox.
> +  static void ComputePolygonVertices(
> +    mozilla::StyleBasicShape* const aBasicShape,

Yes. We don't want to aBsaicShape to be modified. I added Part 6 to fix other functions.

::: layout/svg/nsCSSClipPathInstance.cpp
@@ +159,5 @@
>    nscoord appUnitsPerDevPixel =
>      mTargetFrame->PresContext()->AppUnitsPerDevPixel();
> +  builder->MoveTo(Point(vertices[0].x, vertices[0].y) / appUnitsPerDevPixel);
> +  for (size_t i = 1; i < vertices.Length(); ++i) {
> +    builder->LineTo(Point(vertices[i].x, vertices[i].y) / appUnitsPerDevPixel);

Thanks for the tip! By instinct, I feel NSPointToPoint should exist somewhere, but I was fail to find one :( 

Perhaps it's a good idea to transform it to an nsPoint's method, and call it something like ToGfxPoint() to make it more discoverable? (And rewrite all NSPointToPoint.)
(Assignee)

Comment 22

2 years ago
Comment on attachment 8843953 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v1)

Review of attachment 8843953 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/generic/nsFloatManager.cpp
@@ +612,5 @@
> +    // https://en.wikipedia.org/wiki/Determinant#2_.C3.97_2_matrices
> +    return aP0.x * aP1.y - aP0.y * aP1.x;
> +  };
> +
> +  // Compute the number of colinear vertices.

Oh, this is better! Indeed, we don't need to find the number of colinear points. It's sufficient to find one non-colinear points, and we are done.

@@ +641,5 @@
> +nscoord
> +nsFloatManager::PolygonShapeInfo::LineLeft(const nscoord aBStart,
> +                                           const nscoord aBEnd) const
> +{
> +  return ComputeLineIntercept(aBStart, aBEnd, std::min<nscoord>, nscoord_MAX);

Here, std::min() passes to ComputeLineIntercept() for computing the LineLeft() However, std::min() is a templated function, so I need to explicitly write the template argument |nscoord| to compile.  I know std::min<nscoord> looks like the  min value of nscoord :)

@@ +1032,5 @@
> +
> +  nsTArray<nsPoint> logicalVertices(physicalVertices.Length());
> +  for (const nsPoint& vertex : physicalVertices) {
> +    logicalVertices.AppendElement(
> +      ConvertToFloatLogical(vertex, aWM, aContainerSize));

Using the same array sounds good to me. Let's do this.

::: layout/generic/nsFloatManager.h
@@ +526,5 @@
> +                                 const nsPoint& aP1,
> +                                 const nsPoint& aP2);
> +
> +    // The vertices of the polygon in the float manager's coordinate space.
> +    nsTArray<nsPoint> mVertices;

We cannot make mVertices a const array because Translate() needs to move the shape's origin.

@@ +530,5 @@
> +    nsTArray<nsPoint> mVertices;
> +    // mEmpty is true means the polygon enclose no area.
> +    bool mEmpty = false;
> +    // Computed block start and block end of the polygon shape.
> +    nscoord mBStart = nscoord_MAX;

Added more comments.
Comment on attachment 8844939 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v2)

Review of attachment 8844939 [details] [diff] [review]:
-----------------------------------------------------------------

r=me

::: layout/svg/nsCSSClipPathInstance.cpp
@@ +155,5 @@
>                          FillRule::FILL_WINDING : FillRule::FILL_EVEN_ODD;
>    RefPtr<PathBuilder> builder = aDrawTarget->CreatePathBuilder(fillRule);
>  
> +  nsTArray<nsPoint> vertices;
> +  ShapeUtils::ComputePolygonVertices(basicShape, aRefBox, vertices);

Rather than using an outparam (and a void return type), let's just have ComputePolygonVertices directly return a nsTArray.  (Return-value-optimization should mean there's no copying involved.)

This will make it a bit clearer what's going on, and it removes the footgun of being able to pass an already-populated nsTArray as the outparam (which would produce weird/bad results).
Attachment #8844939 - Flags: review?(dholbert) → review+
(In reply to Ting-Yu Lin [:TYLin] (UTC+8) from comment #21)
> Perhaps it's a good idea to transform it [NSPointToPoint] to an nsPoint's method, and call it
> something like ToGfxPoint() to make it more discoverable? (And rewrite all
> NSPointToPoint.)

I'd lean against that, I think; IMO it's kind of nice to have the various Point/Rect/Margin/etc. classes be independent of another.  I'd rather not hardcode in knowledge-of-other-point-classes into the implementation of each point class.
Flags: needinfo?(dholbert)
Comment on attachment 8844941 [details] [diff] [review]
Part 6 - Convert aBasicShape to a pointer to a const value. (v1)

Review of attachment 8844941 [details] [diff] [review]:
-----------------------------------------------------------------

r=me on the const-cleanup patch -- thanks for adding that.
Attachment #8844941 - Flags: review?(dholbert) → review+
(Assignee)

Comment 26

2 years ago
Created attachment 8845247 [details] [diff] [review]
Part 4 - Extract a function to compute polygon vertices. (v3)

Addressed comment 23 by having ComputePolygonVertices() returns nsTArray.
Part 5 needs to be changed accordingly, but I'll upload a new patch until
the next review pass.
Attachment #8845247 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8844939 - Attachment is obsolete: true
Comment on attachment 8844940 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v2)

Review of attachment 8844940 [details] [diff] [review]:
-----------------------------------------------------------------

This is nearly there!  The only thing I'm not sure about is the std::min horizontal-line case. This is probably r+ once I'm confident we've got that correct, but r- for now.

::: layout/generic/nsFloatManager.cpp
@@ +606,5 @@
> +    return;
> +  }
> +
> +  auto Determinant = [] (const nsPoint& aP0, const nsPoint& aP1) {
> +    // https://en.wikipedia.org/wiki/Determinant#2_.C3.97_2_matrices

As I note further down, "Determinant" is an operation on matrices, not on points -- so this function-signature doesn't quite make sense.

Please add a comment like:
 // Returns the determinant of the matrix [aP0 aP1]
...to explain what this function is actually doing in terms of its (non-matrix) args.

@@ +612,5 @@
> +  };
> +
> +  // See if we have any vertices that are non-colinear with the first two.
> +  // (If a polygon's vertices are all colinear, it encloses no area.)
> +  bool isEntirelyColinear = true;

Google suggests that "colinear" is actually supposed to be spelled with two L's ("collinear")

Please fix that throughout this patch (probably with search-and-replace), in comments, variable names, etc.

@@ +619,5 @@
> +  for (size_t i = 2; i < mVertices.Length(); ++i) {
> +    const nsPoint& p2 = mVertices[i];
> +
> +    // If the determinant of the two points is 0, that means they're
> +    // colinear with respect to the origin. Here, if it's nonzero, then p1

Please replace the first clause here with:
 // If the determinant of the matrix formed by two points is 0,

Specifically:
*  s/the two/two/ (drop "the").  "The two points" gives the mistaken impression that there are already two points that we've been working with/discussing before this line, and those are the two points you're talking about here (but that's not the case).
* A determinant is an operation on matrices, not on points, right?  So "the determinant of (the) two points" is a bit of a bogus concept here.

@@ +647,5 @@
> +nsFloatManager::PolygonShapeInfo::LineLeft(const nscoord aBStart,
> +                                           const nscoord aBEnd) const
> +{
> +  MOZ_ASSERT(!mEmpty, "Shouldn't be called if the polygon encloses no area.");
> +  return ComputeLineIntercept(aBStart, aBEnd, std::min<nscoord>, nscoord_MAX);

Please add a code-comment to hint at
 (a) what we're actually doing here
 (b) what std::min<nscoord> signifies (to help readers avoid making the same mistake that I made when first reading this patch, misinterpreting this as "the minimimum nscoord value")

How about something like the following (please correct my language if I'm misstating what this code does):

"We want the line-left-most inline-axis coordinate where the (block-axis) aBStart/aBEnd band crosses a line segment of the polygon. To get that, we start as line-right as possible (at nscoord_MAX) and then sweep the band line-leftwards (using std::min()) through successively smaller inline-coordinates of intersection points."

@@ +655,5 @@
> +nsFloatManager::PolygonShapeInfo::LineRight(const nscoord aBStart,
> +                                            const nscoord aBEnd) const
> +{
> +  MOZ_ASSERT(!mEmpty, "Shouldn't be called if the polygon encloses no area.");
> +  return ComputeLineIntercept(aBStart, aBEnd, std::max<nscoord>, nscoord_MIN);

Please add a similar comment here (in LineRight) to the one that I'm requesting in LineLeft.

(If it makes sense, feel free to use a simpler comment that points to the other one -- e.g. "Similar to LineLeft() -- though here, we instead want [...] and so we use [...]")

@@ +668,5 @@
> +{
> +  MOZ_ASSERT(aBStart <= aBEnd,
> +             "The band's block start is greater than its block end?");
> +
> +  size_t len = mVertices.Length();

Declare this as "const"

@@ +698,5 @@
> +      ? bigYVertex->x
> +      : XInterceptAtY(aBEnd, *smallYVertex, *bigYVertex);
> +
> +    lineIntercept =
> +      aCompareOp({lineIntercept, bStartLineIntercept, bEndLineIntercept});

Perhaps add a comment here to hint at what this is doing, since "aCompareOp" is kind of abstract?

(Partly because, at first glance, this looks like it could be "minmax" operation -- i.e. it looks kinda like foo = NS_CSS_MINMAX(foo, min, max) -- but that's not what it is.)

Possible comment:
    // If either new intercept is more extreme than lineIntercept
    // (per aCompareOp), then update lineIntercept to that value.

@@ +721,5 @@
> +                                                const nsPoint& aP1,
> +                                                const nsPoint& aP2)
> +{
> +  // Solve for x in the linear equation: x = x1 + (y-y1) * (x2-x1) / (y2-y1),
> +  // where p1 = (x1, y1) and p2 = (x2, y2).

s/p1/aP1/
s/p2/aP2/

@@ +728,5 @@
> +             "This function won't work if the horizontal line y and the line "
> +             "segment (p1, p2) do not intersect!");
> +
> +  if (aP1.y == aP2.y) {
> +    return std::min(aP1.x, aP2.x);

I'm not sure I understand why std::min is always correct for this horizontal-line scenario.  (Even if it is correct, you should include a comment here to hint at why.)

Should we perhaps use aCompareOp (sometimes std::min, sometimes std::max) like we do in the caller?  Or something like that?  (I'm not sure we should, but it just seems asymmetrical that we always do std::min here, and that feels like a red flag.)

@@ +1030,5 @@
> +  WritingMode aWM,
> +  const nsSize& aContainerSize)
> +{
> +  // Use physical coordinates to compute each (xi, yi) vertex because it's
> +  // on x and y axis according to the spec.

The phrase "it's on x and y axis" doesn't quite make sense. (A point that is "on the axis" has a 0 component in the other axis -- e.g. (0,100) is a point on the Y axis.)

Perhaps replace with:
  // Use physical coordinates to compute each (xi, yi) vertex, because CSS
  // represents them using physical coordinates.
Attachment #8844940 - Flags: review?(dholbert) → review-
Comment on attachment 8844940 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v2)

Review of attachment 8844940 [details] [diff] [review]:
-----------------------------------------------------------------

(Observation: Chrome (Dev 58) fails tests 020-025. It looks like it's because they don't understand the "offset-block-start"/"offset-inline-start" CSS properties in the reference cases. Too bad, ok.)

::: layout/reftests/w3c-css/submitted/shapes1/shape-outside-polygon-026-ref.html
@@ +8,5 @@
> +  <link rel="author" title="Ting-Yu Lin" href="mailto:tlin@mozilla.com">
> +  <link rel="author" title="Mozilla" href="http://www.mozilla.org/">
> +  <style>
> +  .container {
> +    writing-mode: horizontal-tb;

Drop the "horizontal-tb" writing mode from the reference case here. It's not present in the corresponding testcase, and it doesn't add any value here since it's the initial value anyway.  (And this test isn't testing writing-modes anyway -- it's testing empty-area polygons.)

::: layout/reftests/w3c-css/submitted/shapes1/shape-outside-polygon-027-ref.html
@@ +8,5 @@
> +  <link rel="author" title="Ting-Yu Lin" href="mailto:tlin@mozilla.com">
> +  <link rel="author" title="Mozilla" href="http://www.mozilla.org/">
> +  <style>
> +  .container {
> +    writing-mode: horizontal-tb;

same here.
(Assignee)

Comment 29

2 years ago
Created attachment 8845817 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v3)

Addressed comment 27 and comment 28.

This change updated ComputeLineIntercept() to skip computing intercept for
horizontal line segments, and disallow horizontal lines to be pass into
XInterceptAtY(). Also, added two new reftest 030 and 031 for this.
Attachment #8845817 - Flags: review?(dholbert)
(Assignee)

Updated

2 years ago
Attachment #8844940 - Attachment is obsolete: true
(Assignee)

Comment 30

2 years ago
Comment on attachment 8844940 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v2)

Review of attachment 8844940 [details] [diff] [review]:
-----------------------------------------------------------------

In general, I appreciate the wording/sentence tweaking advice throughout the review. It's really helpful for non-native English speaker like me. Thank you :)

::: layout/generic/nsFloatManager.cpp
@@ +619,5 @@
> +  for (size_t i = 2; i < mVertices.Length(); ++i) {
> +    const nsPoint& p2 = mVertices[i];
> +
> +    // If the determinant of the two points is 0, that means they're
> +    // colinear with respect to the origin. Here, if it's nonzero, then p1

Right. We are talking about the determinant of a matrix forming by two points. (or two vector with their origin at (0, 0))

@@ +728,5 @@
> +             "This function won't work if the horizontal line y and the line "
> +             "segment (p1, p2) do not intersect!");
> +
> +  if (aP1.y == aP2.y) {
> +    return std::min(aP1.x, aP2.x);

I found a bug after thinking this again. I've fixed this Part 5 (v3). See comment 29 and the code comments.
Comment on attachment 8845817 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v3)

Review of attachment 8845817 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with nits addressed:

::: layout/generic/nsFloatManager.cpp
@@ +746,5 @@
> +  // Solve for x in the linear equation: x = x1 + (y-y1) * (x2-x1) / (y2-y1),
> +  // where aP1 = (x1, y1) and aP2 = (x2, y2).
> +
> +  MOZ_ASSERT(aP1.y <= aY && aY <= aP2.y,
> +             "This function won't work if the horizontal line y and the line "

s/line y/line at aY/

@@ +1058,5 @@
> +    aShapeBoxRect.GetPhysicalRect(aWM, aContainerSize);
> +
> +  // Get physical vertices.
> +  nsTArray<nsPoint> vertices
> +    = ShapeUtils::ComputePolygonVertices(aBasicShape, physicalShapeBoxRect);

Put the "=" on the previous line (for consistency with the assignment that happens just before it, and with prevailing coding style)

::: layout/reftests/w3c-css/submitted/shapes1/shape-outside-polygon-028.html
@@ +18,5 @@
> +  }
> +
> +  .shape {
> +    float: left;
> +    /* All vertices are colinear, resulting an empty area. */

s/colinear/collinear/ (two L's)

::: layout/reftests/w3c-css/submitted/shapes1/shape-outside-polygon-029.html
@@ +19,5 @@
> +  }
> +
> +  .shape {
> +    float: right;
> +    /* All vertices are colinear, resulting an empty area. */

s/colinear/collinear/ (two L's)
Attachment #8845817 - Flags: review?(dholbert) → review+
(In reply to Ting-Yu Lin [:TYLin] (UTC+8) from comment #30)
> In general, I appreciate the wording/sentence tweaking advice throughout the
> review. It's really helpful for non-native English speaker like me. Thank
> you :)

I'm glad it's helpful - thanks for being receptive to the feedback! :)
(Assignee)

Comment 34

2 years ago
Created attachment 8846466 [details] [diff] [review]
Part 5 - Implement shape-outside: polygon(). (v4)

Addressed comment 32.
Attachment #8846466 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8845817 - Attachment is obsolete: true

Comment 35

2 years ago
Pushed by tlin@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/c41191ce3b13
Part 1 - Annotate EllipseShapeInfo as 'final'. r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/23c0f2c6ee17
Part 2 - Rewrite the return expression of ComputeCircleOrEllipseCenter(). r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/f9df20da5431
Part 3 - Remove unneeded WritingMode parameter. r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/64d939893426
Part 4 - Extract a function to compute polygon vertices. r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/8f39505ab1ec
Part 5 - Implement shape-outside: polygon(). r=dholbert
https://hg.mozilla.org/integration/mozilla-inbound/rev/3080ed7f8562
Part 6 - Convert aBasicShape to a pointer to a const value. r=dholbert
I've updated the reference page browser support info and experimental features page to mention the polygon() function:

https://developer.mozilla.org/en-US/docs/Web/CSS/shape-outside#Browser_compatibility
https://developer.mozilla.org/en-US/Firefox/Experimental_features#CSS

Let me know if that looks OK. Thanks!
Keywords: dev-doc-needed → dev-doc-complete
(Assignee)

Comment 38

2 years ago
Chris, thank you for the documentation update. It looks good to me.
You need to log in before you can comment on or make changes to this bug.