Bug 44729 – Add support for GPU accelerated path rendering

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Kenneth Russell]

As part of the effort to perform more of WebKit's rendering using the GPU, support is needed for rendering paths on the GPU.

The approach taken in this bug will be an implementation of Loop and Blinn's "Rendering Vector Art on the GPU" in Chapter 25 of GPU Gems 3.

[Kenneth Russell]

Created attachment 65642 [details]
Core data structures: Arena, RedBlackTree and IntervalTree

From the ChangeLog:

This initial patch adds two key data structures needed for the processing of paths, and a specialized arena allocator which does not call the destructors of allocated objects. It will be more obvious how these data structures are used in later patches. We can consider making them more general and incorporating them into WTF, but this will require very careful thought and possibly significant redesign, and I would like to first land a working version of this code.

The scoping of #include paths and the use of a sub-namespace is deliberate. While this pattern is rarely used in the WebKit project, there are existing examples (WTF), and I believe that it is a good one to enforce modularity. I strongly desire to avoid collisions with other headers and class names in WebCore, and want to be able to export a few selected classes from this package.

The few style violations are the scoped #include guards and the use of streams for debug-only printing code. The former are necessary to avoid header collisions; the latter could be changed if desired.

[WebKit Review Bot]

Attachment 65642 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/Arena.h:38:  #ifndef header guard has wrong style, please use: Arena_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/IntervalTree.h:33:  #ifndef header guard has wrong style, please use: IntervalTree_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/IntervalTree.h:42:  Streams are highly discouraged.  [readability/streams] [3]
WebCore/platform/graphics/gpu/RedBlackTree.h:68:  #ifndef header guard has wrong style, please use: RedBlackTree_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/RedBlackTree.h:76:  Streams are highly discouraged.  [readability/streams] [3]
Total errors found: 5 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Darin Adler]

Because of the way that Xcode processes headers, using scoped #includes won't prevent collisions. If I understand your comment correctly, then I think it’s not right.

[James Robinson]

Could you elaborate?  What does XCode do differently from other build systems?

[Chris Marrin]

I'm not sure why the additional 'gpu' namespace is needed. Seems like it makes thing unnecessarily complex.

[Sam Weinig]

Comment on attachment 65642 [details]
Core data structures: Arena, RedBlackTree and IntervalTree

A redblack tree implementation should not be in platform/graphics but rather in WTF.

r-

[Kenneth Russell]

(In reply to comment #5)
> I'm not sure why the additional 'gpu' namespace is needed. Seems like it makes thing unnecessarily complex.

I mentioned in the ChangeLog that there are some classes that I do not necessarily want to expose from this directory to the rest of WebCore. The public interface to this functionality can be extremely narrow, but there are several implementing classes behind it. I believe that enclosing it in a sub-namespace is the best way to encapsulate it.

[Kenneth Russell]

(In reply to comment #6)
> (From update of attachment 65642 [details])
> A redblack tree implementation should not be in platform/graphics but rather in WTF.
> 
> r-

Please don't blindly r- this patch for this reason. As I mentioned in the ChangeLog, this red/black tree can potentially be promoted to WTF, but this will require a significant restructuring (and I'll need to ask for help from template experts in order to do it) and I strongly desire to land a working version of this code before beginning major restructuring. These few classes are only about 25% of the code to be checked in to this directory; there are more patches to follow.

I'm going to proactively change this back to r?. Please consider the above.

[Sam Weinig]

(In reply to comment #8)
> (In reply to comment #6)
> > (From update of attachment 65642 [details] [details])
> > A redblack tree implementation should not be in platform/graphics but rather in WTF.
> > 
> > r-
> 
> Please don't blindly r- this patch for this reason. As I mentioned in the ChangeLog, this red/black tree can potentially be promoted to WTF, but this will require a significant restructuring (and I'll need to ask for help from template experts in order to do it) and I strongly desire to land a working version of this code before beginning major restructuring. These few classes are only about 25% of the code to be checked in to this directory; there are more patches to follow.

It seems like the only dependency for the red black tree is Arena, which could also go into WTF.  What changes do you think need to be made to it.

Why should we land this code before it is right?

[Darin Adler]

(In reply to comment #4)
> Could you elaborate?  What does XCode do differently from other build systems?

It has something called a header map that works with a flat namespace for all header files in the project. Mark Rowe might know more details than I do.

[Simon Fraser (smfr)]

(In reply to comment #8)
> (In reply to comment #6)
> > (From update of attachment 65642 [details] [details])
> > A redblack tree implementation should not be in platform/graphics but rather in WTF.
> > 
> > r-
> 
> Please don't blindly r- this patch for this reason. As I mentioned in the ChangeLog, this red/black tree can potentially be promoted to WTF, but this will require a significant restructuring (and I'll need to ask for help from template experts in order to do it) and I strongly desire to land a working version of this code before beginning major restructuring. These few classes are only about 25% of the code to be checked in to this directory; there are more patches to follow.

So the way we normally recommend development of significant new pieces of functionality like this is to do so on a branch first, and then merge them to TOT once they have baked for a while. Chris Rogers is doing this with Web Audio, and I think you should do the same here.

[Kenneth Russell]

(In reply to comment #9)
> (In reply to comment #8)
> > (In reply to comment #6)
> > > (From update of attachment 65642 [details] [details] [details])
> > > A redblack tree implementation should not be in platform/graphics but rather in WTF.
> > > 
> > > r-
> > 
> > Please don't blindly r- this patch for this reason. As I mentioned in the ChangeLog, this red/black tree can potentially be promoted to WTF, but this will require a significant restructuring (and I'll need to ask for help from template experts in order to do it) and I strongly desire to land a working version of this code before beginning major restructuring. These few classes are only about 25% of the code to be checked in to this directory; there are more patches to follow.
> 
> It seems like the only dependency for the red black tree is Arena, which could also go into WTF.  What changes do you think need to be made to it.

This red/black tree and arena are currently deliberately designed to only hold and allocate POD (plain old data) or classes or structs bottoming out to only POD, which do not allocate any dynamic storage and whose destructors do not need to be called. The curve processing algorithm allocates many small structures while running and there is a strong desire to not have to do the same kind of alloc/free bookkeeping typically done for a fully general data structure, but to be able to deallocate these structures in bulk.

I gather that it may be possible to both make this data structure fully general and also allow the optimization above using traits, but I currently have no experience with this. I would be interested in generalizing it, but doing so before checkpointing the working, tested code puts the project at risk.

> Why should we land this code before it is right?

The code is not wrong. It matches the desired uses well and is a good starting point for generalization. I think the right thing to do is to incorporate the entire working algorithm and then iterate on the implementation.

[Kenneth Russell]

(In reply to comment #11)
> (In reply to comment #8)
> > (In reply to comment #6)
> > > (From update of attachment 65642 [details] [details] [details])
> > > A redblack tree implementation should not be in platform/graphics but rather in WTF.
> > > 
> > > r-
> > 
> > Please don't blindly r- this patch for this reason. As I mentioned in the ChangeLog, this red/black tree can potentially be promoted to WTF, but this will require a significant restructuring (and I'll need to ask for help from template experts in order to do it) and I strongly desire to land a working version of this code before beginning major restructuring. These few classes are only about 25% of the code to be checked in to this directory; there are more patches to follow.
> 
> So the way we normally recommend development of significant new pieces of functionality like this is to do so on a branch first, and then merge them to TOT once they have baked for a while. Chris Rogers is doing this with Web Audio, and I think you should do the same here.

I respectfully disagree. Several people are actively collaborating on GPU acceleration of various aspects of WebKit's rendering, and this code is not a prototype -- it has been baking for several months in a non-WebKit project (Google's O3D web plugin). Forcing it onto a branch will make collaboration extremely difficult. There seems to be strong interest in incorporating this functionality in multiple ports, which is why I have submitted the patch under a platform-neutral directory. If there are objections to placement there, it could be placed under platform/graphics/chromium/, but that will defeat code sharing.

[Kenneth Russell]

Created attachment 65655 [details]
Cubic curve classification, texture coordinate assignment, local triangulation and math utilities

It seems to me that it will make it easier to understand the motivation for some of this code to have all of it available for perusal in patch form, so I am continuing to upload patches before review decisions are made on earlier ones.

From the ChangeLog:

This patch adds the classification of cubic curve segments into categories, assignment of texture coordinates to the curves' control points for later rendering on the GPU, the algorithm for triangulating an individual cubic curve and walking its interior edges for assembly into a complete filled shape, and several utility routines related to geometry and cubic curve processing, some ported from Skia.

The reason for the style violations in the header guards is described in the earlier patch. There is another violation around the use of the letter l as an identifier, but the algorithm defines coordinates k, l, and m, so it seems best to match the algorithm's terminology rather than the style guide in this case.

[WebKit Review Bot]

Attachment 65655 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/LocalTriangulator.h:32:  #ifndef header guard has wrong style, please use: LocalTriangulator_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/LocalTriangulator.h:70:  l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
WebCore/platform/graphics/gpu/LocalTriangulator.h:134:  m_l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
WebCore/platform/graphics/gpu/CubicMathUtils.h:32:  #ifndef header guard has wrong style, please use: CubicMathUtils_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/CubicClassifier.h:35:  #ifndef header guard has wrong style, please use: CubicClassifier_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/CubicTextureCoords.h:36:  #ifndef header guard has wrong style, please use: CubicTextureCoords_h  [build/header_guard] [5]
Total errors found: 6 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Kenneth Russell]

Created attachment 65657 [details]
Path processing results and shader management classes

From the ChangeLog:

This patch adds the PathCache data structure produced by the path processing algorithm (to follow), as well as helper classes to manage the shaders used to fill the paths.

The reason for the style violations in the header guards is described in an earlier patch.

[WebKit Review Bot]

Attachment 65657 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/PathCache.h:32:  #ifndef header guard has wrong style, please use: PathCache_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/ShaderCache.h:32:  #ifndef header guard has wrong style, please use: ShaderCache_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/ShaderObject.h:32:  #ifndef header guard has wrong style, please use: ShaderObject_h  [build/header_guard] [5]
Total errors found: 3 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Kenneth Russell]

I just realized I incorrectly named the new source files with the .cc suffix instead of the .cpp suffix, and that was why check-webkit-style wasn't catching style errors in them. Correcting this now and uploading new patches.

[Kenneth Russell]

Created attachment 65661 [details]
Cubic curve classification, texture coordinate assignment, local triangulation and math utilities

Revised version of cubic curve classification patch. Renamed .cc files to .cpp and fixed style violations. Updated ChangeLog.

[Kenneth Russell]

Created attachment 65663 [details]
Path processing results and shader management classes

Renamed new .cc files to .cpp and fixed style violations. Updated ChangeLog.

[Kenneth Russell]

Created attachment 65664 [details]
The PathProcessor, which implements the main algorithm

From the ChangeLog:

This is the main algorithm. It takes as input a Path which may contain one or more closed contours including holes. It produces as output two triangle meshes which, when drawn on the GPU, render the filled path. The mesh can be transformed arbitrarily with no re-processing, and the resulting on-screen curves maintain resolution independence.

PathProcessor::process is the main entry point, and should illustrate the steps of the algorithm fairly clearly.

The two style violations are the style of the include guards, the reason for which is described in an earlier patch, and the use of streams for debug-only printing, which could be changed if necessary.

[WebKit Review Bot]

Attachment 65661 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/LocalTriangulator.h:32:  #ifndef header guard has wrong style, please use: LocalTriangulator_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/LocalTriangulator.h:70:  l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
WebCore/platform/graphics/gpu/LocalTriangulator.h:134:  m_l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
WebCore/platform/graphics/gpu/CubicMathUtils.h:32:  #ifndef header guard has wrong style, please use: CubicMathUtils_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/CubicClassifier.h:35:  #ifndef header guard has wrong style, please use: CubicClassifier_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/CubicTextureCoords.h:36:  #ifndef header guard has wrong style, please use: CubicTextureCoords_h  [build/header_guard] [5]
Total errors found: 6 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[WebKit Review Bot]

Attachment 65663 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/PathCache.h:32:  #ifndef header guard has wrong style, please use: PathCache_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/ShaderCache.h:32:  #ifndef header guard has wrong style, please use: ShaderCache_h  [build/header_guard] [5]
WebCore/platform/graphics/gpu/ShaderObject.h:32:  #ifndef header guard has wrong style, please use: ShaderObject_h  [build/header_guard] [5]
Total errors found: 3 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[WebKit Review Bot]

Attachment 65664 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/PathProcessor.cpp:54:  Streams are highly discouraged.  [readability/streams] [3]
WebCore/platform/graphics/gpu/PathProcessor.h:35:  #ifndef header guard has wrong style, please use: PathProcessor_h  [build/header_guard] [5]
Total errors found: 2 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Stephen White]

Could we consider moving the arena and red/black tree implementation, etc to WTF as-is for now, with strongly-worded comments indicating the caveats (only to be used for POD types), and that they could be generalized later?

[Darin Fisher (:fishd, Google)]

(In reply to comment #13)
> > So the way we normally recommend development of significant new pieces of functionality like this is to do so on a branch first, and then merge them to TOT once they have baked for a while. Chris Rogers is doing this with Web Audio, and I think you should do the same here.
> 
> I respectfully disagree. Several people are actively collaborating on GPU acceleration of various aspects of WebKit's rendering, and this code is not a prototype -- it has been baking for several months in a non-WebKit project (Google's O3D web plugin). Forcing it onto a branch will make collaboration extremely difficult. There seems to be strong interest in incorporating this functionality in multiple ports, which is why I have submitted the patch under a platform-neutral directory. If there are objections to placement there, it could be placed under platform/graphics/chromium/, but that will defeat code sharing.

Agreed, there's no need to punt this to a branch.  Moreover, Chromium development happens much better when done on ToT.  We have infrastructure to support development of new features on ToT that we'd like to leverage here.  I have not been a big fan of the audio branch because it doesn't benefit from that infrastructure.

[Darin Fisher (:fishd, Google)]

So, it sounds like there are three main objections to this patch:

  1- The namespace
  2- The scoped includes
  3- The arena class

Those are all fairly cosmetic to the core of what this patch adds.

When Ken asked me about the namespace and scoping before he posted this patch, I pointed out that it didn't seem to match convention.  However, I agreed with him that it seemed to have merits.  For one thing, the namespace helps identify this subcomponent.  The scoped include has a similar benefit.

There also seemed to be some recent convention for subcomponents getting their own namespace (JSC::Yarr::), and even some convention for scoped includes (#include "yarr/RegexJIT.h").  Since Yarr was created "recently," I figured this might even be a popular new convention!  (Perhaps "gpu::" should be "Gpu::" or "GPU::" instead.)

As for the Arena class, I tend to agree that housing it in platform/graphics/gpu/ is suboptimal.  It makes sense to put it either in wtf/ or platform/ along side the existing Arena.h.  One idea would be to simply call this new Arena class PODArena instead.  That would both avoid conflicts with the existing Arena and help clarify the feature that destructors are not called.

[Adam Barth]

Comment on attachment 65642 [details]
Core data structures: Arena, RedBlackTree and IntervalTree

WebCore/platform/graphics/gpu/Arena.h:81
 +              return ::malloc(size);
Why ::malloc instead of fastMalloc?

WebCore/platform/graphics/gpu/Arena.h:86
 +              ::free(ptr);
fastFree?

WebCore/platform/graphics/gpu/Arena.h:126
 +              m_current = new Chunk(m_allocator.get(), m_currentChunkSize);
naked new.  Did you mean to call adoptPtr?

WebCore/platform/graphics/gpu/Arena.h:133
 +              new(ptr) T();
Multiline if should have { }.  Also, I'm not familiar with this construct, but I assume others are.

WebCore/platform/graphics/gpu/Arena.h:226
 +      Chunk* m_current;
OwnPtr?  I don't understand the ownership of this memory.

WebCore/platform/graphics/gpu/Arena.h:227
 +      Vector<Chunk*> m_chunks;
Does this variable own this memory?

WebCore/platform/graphics/gpu/IntervalTree.h:42
 +  #include <iostream>
We don't usually use iostream.  Perhaps you means to use LOG?

WebCore/platform/graphics/gpu/IntervalTree.h:96
 +      const T& low() const
These can be on a single line.

WebCore/platform/graphics/gpu/IntervalTree.h:122
 +      // Returns true if this interval overlaps the other.
This comment is pretty content-free.

WebCore/platform/graphics/gpu/IntervalTree.h:112
 +      // given low and high endpoints.
This comment is pretty content-free.

WebCore/platform/graphics/gpu/IntervalTree.h:144
 +      // Summary information needed for efficient queries.
Please remove this comment.

WebCore/platform/graphics/gpu/IntervalTree.h:154
 +      void setMaxHigh(const T& maxHigh) const
Seems strange to have a const setter.

WebCore/platform/graphics/gpu/IntervalTree.h:218
 +      void allOverlaps(const IntervalType& interval,
These parameters should be on one line.

WebCore/platform/graphics/gpu/IntervalTree.h:221
 +          // gcc requires explicit dereference of "this" here
Why?  Is there a variable shadowing root?

WebCore/platform/graphics/gpu/IntervalTree.h:228
 +                                       const UserData data = 0)
One line for these parameters.

WebCore/platform/graphics/gpu/IntervalTree.h:226
 +      static IntervalType makeInterval(const T& low,
Usually we call these sorts of functions createInterval.

WebCore/platform/graphics/gpu/IntervalTree.h:234
 +      // Returns true if the tree's invariants are preserved.
Maybe remove this comment and rename to checkInvariants?

WebCore/platform/graphics/gpu/IntervalTree.h:251
 +          // gcc requires explicit dereference of "this" here
??

WebCore/platform/graphics/gpu/IntervalTree.h:260
 +                                 Vector<IntervalType>& res)
One line

WebCore/platform/graphics/gpu/IntervalTree.h:272
 +              // interval.low() <= left->data().maxHigh()
Can we make this an ASSERT instead of a comment?

WebCore/platform/graphics/gpu/IntervalTree.h:282
 +          // node->data().low() <= interval.high()
Again, perhaps an ASSERT?

WebCore/platform/graphics/gpu/IntervalTree.h:293
 +          if (left)
Multiline if should have { }

WebCore/platform/graphics/gpu/IntervalTree.h:297
 +          if (right)
ditto

WebCore/platform/graphics/gpu/IntervalTree.h:309
 +      // Returns true if the tree's invariants are preserved.
Again, why not just name the function what this comment says and remove the comment?

WebCore/platform/graphics/gpu/RedBlackTree.h:69
 +  #define gpu_RedBlackTree_h
As the stylebot says, these include guards don't match the style guide.

WebCore/platform/graphics/gpu/RedBlackTree.h:71
 +  #ifndef NDEBUG
We don't need to guard these includes.

WebCore/platform/graphics/gpu/RedBlackTree.h:93
 +          virtual ~Visitor() {}
Are you really going to destruct the visitor?  I'd move this to a private destructor.

WebCore/platform/graphics/gpu/RedBlackTree.h:122
 +      virtual ~RedBlackTree()
One line is sufficient here.

WebCore/platform/graphics/gpu/RedBlackTree.h:126
 +      // Inserts a datum into the tree.
Please remove useless comment.

WebCore/platform/graphics/gpu/RedBlackTree.h:146
 +      bool contains(const T& data)
One line.  What's the point of having this function if it just calls through to treeSearch?

WebCore/platform/graphics/gpu/RedBlackTree.h:152
 +      // each one.
Please remove useless comment.

WebCore/platform/graphics/gpu/RedBlackTree.h:155
 +          if (m_root)
Prefer early returns.

WebCore/platform/graphics/gpu/RedBlackTree.h:159
 +      // Returns the number of elements in the tree.
Really?

WebCore/platform/graphics/gpu/RedBlackTree.h:223
 +          Color color() const
One line.

WebCore/platform/graphics/gpu/RedBlackTree.h:358
 +      void treeInsert(Node* z)
These variable names are kind of mysterious to me.  Maybe z -> newNode?

WebCore/platform/graphics/gpu/RedBlackTree.h:511
 +                          if (m_verboseDebugging)
Bad indent?

WebCore/platform/graphics/gpu/RedBlackTree.h:723
 +          int count()
One line.  const

[Adam Barth]

Comment on attachment 65661 [details]
Cubic curve classification, texture coordinate assignment, local triangulation and math utilities

WebCore/platform/graphics/gpu/CubicClassifier.cpp:44
 +                                                    float b3x, float b3y) {
{ should be on the next line.

WebCore/platform/graphics/gpu/CubicClassifier.cpp:45
 +      Vector3 b0(b0x, b0y, 1);
These names are terrible.

WebCore/platform/graphics/gpu/CubicClassifier.h:67
 +          CurveType curveType() const
one line

WebCore/platform/graphics/gpu/CubicClassifier.h:72
 +          float d1() const
one line

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:52
 +      // p3 = (x3, y3)
This comment is mysterious to me.  Should we be using a Point class instead of passing around disconnected floats?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:114
 +               != orientation(p1x, p1y, q1x, q1y, q2x, q2y))
Please merge with previous line.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:116
 +                  != orientation(p2x, p2y, q2x, q2y, q1x, q1y)));
Please merge with previous line.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:119
 +  bool pointInTriangle(float px, float py,
All this code is really begging for FloatPoint (see IntPoint in the render tree for the int version).

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:156
 +      // Derived from coplanar_tri_tri() at
What's the license on that code?  If this is a derived work, we need to be careful about copyright. 

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:162
 +      if (edgeAgainstTriEdges(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y))
Can we merge all these using || ?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:190
 +  #define NearlyZeroConstant (1.0f / (1 << 12))
Why a macro and not a const float?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:194
 +      ASSERT(tolerance > 0.0);
This could be a COMPILE_ASSERT

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:201
 +  static inline float interp(float a, float b, float t)
Please don't abbreviate word like this.  You and I might know what interp means, but someone reading this code in the future might be confused.  Also, static is redundant with inline.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:218
 +      float bcd = interp(bc, cd, t);
More mysterious variable names.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:224
 +  static bool evalCubicAt(const FloatPoint cubic[4], float t, FloatPoint& pt)
Oh!  We do have FloatPoint!  We should really use that all over this code.  Also, instead of declaring all these functions static, just put them in an anonymous namespace.  That's the C++ way of doing the same thing.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:230
 +  static bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool* ambiguous)
We use non-const references for outparams.  Yes, that sucks, but it's the way we roll.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:249
 +      bool pointAtExtremum = (xRay.y() == cubic[3].y());
const?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:278
 +      float upperT;
What is T?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:290
 +          float t = 0.5 * (upperT + lowerT);
I see.  Hum...

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:296
 +      } while (++iter < MaxIter && !nearlyZero(eval.y() - xRay.y()));
I usually put a blank line after a do .. while since they're pretty rare.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:305
 +  static int validUnitDivide(float numer, float denom, float* ratio)
again, & for outparams

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:324
 +      return 1;
In this case, maybe we should just return a struct?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:315
 +          return 0;
Why 0/1 instead of true/false?  I don't quite get what's going on here.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:347
 +      r += validUnitDivide(c, Q, r);
I see.  That's pretty mysterious.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:423
 +      for (int i = 0; i < roots - 1; i++) {
We prefer preincrement.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:432
 +              memcpy(dst, src, 4*sizeof(FloatPoint));
Ouch!  Shouldn't we use Vector<FloatPoint> rather than raw pointers!

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:430
 +      if (dst) {
early return rather than massive nesting level?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:433
 +          else {
early return?

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:444
 +                  memcpy(tmp, dst, 4 * sizeof(FloatPoint));
This is a really unsafe pattern.  This code has no way to be sure how big dst or tValues are.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:445
 +                  src = tmp;
Yuck!  Please don't assign to your input parameters.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:489
 +      for (int i = 0; i < 7; i++)
Magic constants make me sad.  Even if they are lucky number 7.

WebCore/platform/graphics/gpu/CubicMathUtils.cpp:493
 +  // Public XRay queries.
Ok.  I got tired.  This is as far as I got.

[Adam Barth]

Comment on attachment 65663 [details]
Path processing results and shader management classes

WebCore/platform/graphics/gpu/PathCache.cpp:39
 +  unsigned int PathCache::numVertices() const
We usually just say "unsigned" and drop the int.

WebCore/platform/graphics/gpu/PathCache.cpp:39
 +  unsigned int PathCache::numVertices() const
Why not just put this in the header?

WebCore/platform/graphics/gpu/PathCache.cpp:59
 +                            float k, float l, float m)
More inscrutable variable names

WebCore/platform/graphics/gpu/PathCache.cpp:78
 +  unsigned int PathCache::numInteriorVertices() const
Move to header?

WebCore/platform/graphics/gpu/PathCache.h:51
 +      PathCache()
We can't just use the constructor the compiler gives us?

WebCore/platform/graphics/gpu/PathCache.h:55
 +      // The number of vertices in the mesh.
Remove useless comment.

WebCore/platform/graphics/gpu/PathCache.h:61
 +      // vertices in the mesh.
Can we use some data structures here instead of just a vector of floats?  It seems like this ought to be a vector of FloatPoints.  Also, why not just expose a getter for the underlying Vector?  Splitting up the length and the pointer seems counter productive.  A client can always get them from the vector, but you can't really get the vector back.

WebCore/platform/graphics/gpu/PathCache.h:67
 +      // there are no vertices in the mesh.
Again, some structuring of data would make these comments self-evident.

WebCore/platform/graphics/gpu/PathCache.h:77
 +      // The number of interior vertices.
Really?

WebCore/platform/graphics/gpu/PathCache.h:78
 +      unsigned int numInteriorVertices() const;
Please don't abbreviate words.

WebCore/platform/graphics/gpu/ShaderCache.cpp:45
 +      , m_shaders(new OwnPtr<ShaderObject>[NumShaderTypes * NumRegionTypes * NumAntialiasTypes])
Wat?  OwnPtr is a stack-object.  We don't allocate them on the heap.  This isn't the right patter here.

WebCore/platform/graphics/gpu/ShaderCache.cpp:50
 +      const char* uniforms;
what are these?  Some more informative variable names would be helpful.

WebCore/platform/graphics/gpu/ShaderCache.cpp:76
 +                   antialiasIndex);
Wow, that's kind of nutty.  Also, why the giant ( ) around the whole thing?

WebCore/platform/graphics/gpu/ShaderCache.cpp:94
 +          vertexShaderSource +=
Please use StringBuilder rather than +=.  += makes folks cry.

WebCore/platform/graphics/gpu/ShaderCache.cpp:88
 +      String vertexShaderSource =
Did you want a Unicode string here or an 8-bit string?

WebCore/platform/graphics/gpu/ShaderCache.cpp:82
 +  PassOwnPtr<ShaderObject> ShaderCache::loadShader(ShaderType shaderType,
One line for parameters.

WebCore/platform/graphics/gpu/ShaderCache.cpp:84
 +                                                   AntialiasType antialiasType)
Ok, this function is really nutty.  Can we do something that's easier to understand?  I feel like the pattern you're using will quickly turn into spagetti (if it's not already there).

WebCore/platform/graphics/gpu/ShaderCache.cpp:180
 +          fprintf(stderr, "ShaderCache: error compiling shader: %s\n", log.ascii().data());
fprintf?  LOG maybe?

WebCore/platform/graphics/gpu/ShaderCache.cpp:169
 +  Platform3DObject ShaderCache::createShaderFromSource(GraphicsContext3D::WebGLEnumType shaderType,
One line.

WebCore/platform/graphics/gpu/ShaderCache.h:73
 +      ShaderObject* getShader(ShaderType shaderType,
One line.

WebCore/platform/graphics/gpu/ShaderCache.h:78
 +      PassOwnPtr<ShaderObject> loadShader(ShaderType shaderType,
createShader?  One line.

WebCore/platform/graphics/gpu/ShaderCache.h:81
 +      Platform3DObject createShaderFromSource(GraphicsContext3D::WebGLEnumType shaderType,
One line.

WebCore/platform/graphics/gpu/ShaderCache.h:85
 +      OwnArrayPtr<OwnPtr<ShaderObject> > m_shaders;
Oh, maybe that's ok.  That's kind of strange, but it might just work.

WebCore/platform/graphics/gpu/ShaderObject.cpp:40
 +                             Platform3DObject program)
one line.

WebCore/platform/graphics/gpu/ShaderObject.cpp:54
 +      if (iter == m_uniformLocations.end()) {
I'd permute these for early return, but that's a matter of personal preference.

WebCore/platform/graphics/gpu/ShaderObject.cpp:55
 +          // Look it up
Remove useless comment.

WebCore/platform/graphics/gpu/ShaderObject.cpp:67
 +          // Look it up
ditto

WebCore/platform/graphics/gpu/ShaderObject.h:51
 +      void use();
Maybe rename to makeProgramCurrentInContext() ?  In general, you shouldn't need a comment to explain what a function like this does.  Just name the function what you would have written in the comment.

WebCore/platform/graphics/gpu/ShaderObject.h:53
 +      // Returns the location of the given uniform, or -1 if it does not
mjs will be sad about this in-band signaling.

[Adam Barth]

Comment on attachment 65664 [details]
The PathProcessor, which implements the main algorithm

Please consider using one bug per patch.  This bug will quickly become impossible to understand.

WebCore/platform/graphics/gpu/PathProcessor.cpp:81
 +  T min3(const T& v1, const T& v2, const T& v3)
We can rely on C++ overloading to avoid having to number these functions.

WebCore/platform/graphics/gpu/PathProcessor.cpp:87
 +  T max3(const T& v1, const T& v2, const T& v3)
Why are these functions here instead of in a more general location?

WebCore/platform/graphics/gpu/PathProcessor.cpp:109
 +  class BBox : public Noncopyable {
BBox => BoundingBox?

WebCore/platform/graphics/gpu/PathProcessor.cpp:120
 +      void setup(float minX,
One line.  Again, FloatPoint calls to you.

WebCore/platform/graphics/gpu/PathProcessor.cpp:131
 +      // Initializes the bounding box to surround the given triangle.
Really?  Maybe call the function initialize?  Why isn't this a constructor?

WebCore/platform/graphics/gpu/PathProcessor.cpp:148
 +      // Initializes this bounding box to the contents of the other.
Kind of like a copy constructor?  Why is the class NonCopyable then?

WebCore/platform/graphics/gpu/PathProcessor.cpp:166
 +      float minX() const
these should all be on one line.

WebCore/platform/graphics/gpu/PathProcessor.cpp:187
 +      float m_minX;
Isn't this just FloatRect?  Why about this class is specific to bounding boxes versus other types of FloatRects?  If you like explicitness of the name, you can make an empty subclass of FloatRect.

WebCore/platform/graphics/gpu/PathProcessor.cpp:198
 +      ostr << "[BBox minX=" << arg.minX()
Please don't use iostream.

WebCore/platform/graphics/gpu/PathProcessor.cpp:215
 +  class Segment : public Noncopyable {
Many of my comments for BBox apply to Segment.

WebCore/platform/graphics/gpu/PathProcessor.cpp:267
 +      // Returns the kind of segment.
For realz?

WebCore/platform/graphics/gpu/PathProcessor.cpp:344
 +      Segment* subdivide()
Can we give this a different name to more clearly distinguish it from the above function?

WebCore/platform/graphics/gpu/PathProcessor.cpp:360
 +      int numCrossingsForXRay(FloatPoint pt, bool* ambiguous) const
pt -> point?  Again, & for outparams.

WebCore/platform/graphics/gpu/PathProcessor.cpp:372
 +                       CubicTextureCoords::Result* texCoords);
One line.

WebCore/platform/graphics/gpu/PathProcessor.cpp:401
 +          return 2;
Magic constants are sadness.

WebCore/platform/graphics/gpu/PathProcessor.cpp:219
 +          kCubic,
We don't use the k prefix.

WebCore/platform/graphics/gpu/PathProcessor.cpp:468
 +          default:
Please omit the default case.  The compiler will error out if we don't handle all the cases.

WebCore/platform/graphics/gpu/PathProcessor.cpp:519
 +      // Adds a segment to this contour.
...

WebCore/platform/graphics/gpu/PathProcessor.cpp:565
 +      Segment* begin() const
Why not call this first?

WebCore/platform/graphics/gpu/PathProcessor.cpp:574
 +      //       cur = cur->next()) {
I see.  Maybe we should define a proper iterator class to make this easier?

WebCore/platform/graphics/gpu/PathProcessor.cpp:583
 +      bool ccw() const
ccw => isOrientedCounterclockwise

WebCore/platform/graphics/gpu/PathProcessor.cpp:588
 +      void setCCW(bool ccw)
setXYZZY(bool xyzzy)

WebCore/platform/graphics/gpu/PathProcessor.cpp:593
 +      // Returns the bounding box of this contour.
...

WebCore/platform/graphics/gpu/PathProcessor.cpp:612
 +      bool fillRightSide() const
This function name sounds like a verb, which would seem to instruct this object to fill the right side.  Perhaps isRightSideFilled() ?

WebCore/platform/graphics/gpu/PathProcessor.cpp:614
 +          return m_fillRightSide;
and then you can rename m_fillRightSide => m_isRightSideFilled

WebCore/platform/graphics/gpu/PathProcessor.cpp:630
 +      Segment m_sentinel;
Can't we just use null for the sentinel?  Better yet, we should have a real iterator instead of a fake half-iterator.

WebCore/platform/graphics/gpu/PathProcessor.cpp:633
 +      bool m_ccw;
Again, the comments is unnecessary if the variable is named m_isOrientedCounterclockwise.

WebCore/platform/graphics/gpu/PathProcessor.cpp:635
 +      // This contour's bounding box.
really?

WebCore/platform/graphics/gpu/PathProcessor.cpp:658
 +      for (int i = 0; i < 4; i++) {
magic 4

WebCore/platform/graphics/gpu/PathProcessor.cpp:660
 +          if (texCoords)
Multiline if should have  {} .  Or just put the function call on one line.

WebCore/platform/graphics/gpu/PathProcessor.cpp:677
 +  // PathProcessor
Ok.  I got tired and stopped here.

[Adam Barth]

These patches are pretty large and generally far out of WebKit style / convention.  They read like code from another project rather than like WebKit code.  Hopefully the comments above are a useful starting point for revising these patches.  Again, please consider using one patch per bug and liking then against the master bug using the blocks relation in bugzilla.

[Simon Fraser (smfr)]

I'd also like to see some consideration of how you plan to test that these new data structures don't have bugs, and that the higher level features are working as expected.

[Kenneth Russell]

(In reply to comment #32)
> These patches are pretty large and generally far out of WebKit style / convention.  They read like code from another project rather than like WebKit code.  Hopefully the comments above are a useful starting point for revising these patches.  Again, please consider using one patch per bug and liking then against the master bug using the blocks relation in bugzilla.

You're right, the majority of this code originated in a project (O3D) covered by the Google C++ style guide, and it was ported over to WebKit style. Some of the math utilities were ported verbatim from Skia, which is why they diverge even more from both coding styles.

Thanks for your extensive comments. I'll go through and address them, and probably file separate additional bugs and make this one depend on them.

[Kenneth Russell]

(In reply to comment #33)
> I'd also like to see some consideration of how you plan to test that these new data structures don't have bugs, and that the higher level features are working as expected.

Extensive unit tests were written for these data structures in their originating project. See the various _test.cc files in http://src.chromium.org/viewvc/chrome/trunk/src/o3d/core/cross/gpu2d/ . I would be very happy to port these unit tests over. Does WebKit have a unit testing framework?

The best way I have found so far to verify the higher level functionality is to do manual or side-by-side verification of the rendering results. The algorithm is known to produce correct results for several samples including the SVG butterfly. More content needs to be fed through the algorithm to shake out any remaining bugs.

[Darin Fisher (:fishd, Google)]

(In reply to comment #35)
> (In reply to comment #33)
> > I'd also like to see some consideration of how you plan to test that these new data structures don't have bugs, and that the higher level features are working as expected.
> 
> Extensive unit tests were written for these data structures in their originating project. See the various _test.cc files in http://src.chromium.org/viewvc/chrome/trunk/src/o3d/core/cross/gpu2d/ . I would be very happy to port these unit tests over. Does WebKit have a unit testing framework?

The Chromium port does.  You can add unit tests in WebKit/chromium/tests/.  This is not the best location for generic unit tests, but it seems like a reasonable starting point since the framework exists.

[Maciej Stachowiak]

I agree that fundamental data structures should go in WTF and should be aligned with our general approach for basic data structures (handles all types, matching style of API, etc). This definitely applies to the RedBlackTree. As for the Arena, ideally I would like to see it merged with the current Arena class, or else hear a clear reason for why it is beneficial to have a separate arena implementation.

I am dubious about the idea of landing the code first and fixing it later, particularly since later is unspecified, may be much later, and may have to be done by someone else. Doing things on a rush basis, where you overlook certain problems, creates technical debt for the project. This project, though aiming at highly desirable goals, is somewhat experimental in the sense that the WebKit community is not 100% clear that the approach is quire right. It's hard to see how a project can both be experimental and yet worth incurring technical debt.

It would also be much easier to review this if it were split into smaller and logically coherent pieces. These chunks are somewhat large, and have some recurring issues. Here are some examples:

- The class Vector3 is used throughout at least one of these patches, but none of them contain its definition (it doesn't seem to already exist in WebKit).

- It's not entirely clear why Vector3 is used to represent 2-dimentional points instead of using FloatPoint.

- Many functions take coordinates as individual floats instead of using FloatPoint or Vector3.

- Many variables have mysterious 1-3 letter names - this is not up to our standards of variable naming.

- A bunch of the code uses "long" without a clear indication of why it needs to vary between 32-bit and 64-bit platforms. We usually use size_t or a similar typedef to make variable-size integer types self-documenting.

- The BBox class seems to duplicate FloatRect. If it has added functionality, that should go in FloatRect.

Due to these issues, as well as the many that Adam spotted, I think all of these patches should be r- for now.

[Eric Seidel (no email)]

I agree with Maciej that we should r- all these patchs and try again with a master bug, and a bunch of blocking bugs.

If I were doing this work, I would start by landing each of the individual data structures one at a time. OR, alternatively landing a version of some of the later work using existing data structures, with the idea to move them to better ones when the better ones land.

I strongly oppose the idea of doing this work on a branch.  WebKit has a horrible track record of merging branches.  I believe Ken already has a pretty good sense of WebKit (demonstrated by the fact that he's a reviewer if nothing else).

I would r- all these patches, close this bug, and start over.  I think we've learned a lot here.  Starting by adding one data structure to WTF or adding a version of PathProcessor or some of the math utilities which are self-contained would be fine.  I'm happy to review smaller (ideally <20k) versions of these patches.

[Maciej Stachowiak]

(In reply to comment #38)
> I agree with Maciej that we should r- all these patchs and try again with a master bug, and a bunch of blocking bugs.
> 
> If I were doing this work, I would start by landing each of the individual data structures one at a time. OR, alternatively landing a version of some of the later work using existing data structures, with the idea to move them to better ones when the better ones land.
> 
> I strongly oppose the idea of doing this work on a branch.  WebKit has a horrible track record of merging branches.  I believe Ken already has a pretty good sense of WebKit (demonstrated by the fact that he's a reviewer if nothing else).

Using a branch might not be the best fit for this work. Here's the tradeoffs:

On a branch, you are free to land code that doesn't properly integrate with WebKit or follow the style guidelines. This makes it easier to sprint to demonstrate that an experimental idea is viable before you expend the effort to properly integrate it with WebKit.

On the other hand, getting work from a branch in shape for trunk can be really hard - we don't have a whole lot of successes here yet.

Short version, it's probably better to do the code on trunk, but with all the care and caution that any other WebKit code would call for.

[Kenneth Russell]

(In reply to comment #37)
> I agree that fundamental data structures should go in WTF and should be aligned with our general approach for basic data structures (handles all types, matching style of API, etc). This definitely applies to the RedBlackTree. As for the Arena, ideally I would like to see it merged with the current Arena class, or else hear a clear reason for why it is beneficial to have a separate arena implementation.
> 
> I am dubious about the idea of landing the code first and fixing it later, particularly since later is unspecified, may be much later, and may have to be done by someone else. Doing things on a rush basis, where you overlook certain problems, creates technical debt for the project. This project, though aiming at highly desirable goals, is somewhat experimental in the sense that the WebKit community is not 100% clear that the approach is quire right. It's hard to see how a project can both be experimental and yet worth incurring technical debt.
> 
> It would also be much easier to review this if it were split into smaller and logically coherent pieces. These chunks are somewhat large, and have some recurring issues. Here are some examples:
> 
> - The class Vector3 is used throughout at least one of these patches, but none of them contain its definition (it doesn't seem to already exist in WebKit).
> 
> - It's not entirely clear why Vector3 is used to represent 2-dimentional points instead of using FloatPoint.

There are some situations where 3-dimensional operations like cross products need to be done. I originally thought the right thing to do was to expose a Vector3 class (see https://bugs.webkit.org/show_bug.cgi?id=44666 ), but now I realize the better approach would have been to enhance FloatPoint3D slightly, which I'm going to do instead. In some places like LocalTriangulator I'll switch it to use FloatPoint, though.

> - Many functions take coordinates as individual floats instead of using FloatPoint or Vector3.

I'll improve these.

> - Many variables have mysterious 1-3 letter names - this is not up to our standards of variable naming.

Most of these are either because the paper describes (k, l, m) coordinates, or because the code was originally ported from Skia and I was hesitant to do widespread variable renaming.

> - A bunch of the code uses "long" without a clear indication of why it needs to vary between 32-bit and 64-bit platforms. We usually use size_t or a similar typedef to make variable-size integer types self-documenting.

These are artifacts of GraphicsContext3D's use of long. We should clean up that class.

> - The BBox class seems to duplicate FloatRect. If it has added functionality, that should go in FloatRect.

Agreed, the BBox class is an artifact from the previous framework, which didn't have an appropriate class.

> Due to these issues, as well as the many that Adam spotted, I think all of these patches should be r- for now.

I agree. I'll revise the code according to all review feedback and try again, submitting each patch under an individual bug.

[Kenneth Russell]

(In reply to comment #38)
> I would r- all these patches, close this bug, and start over.  I think we've learned a lot here.  Starting by adding one data structure to WTF or adding a version of PathProcessor or some of the math utilities which are self-contained would be fine.  I'm happy to review smaller (ideally <20k) versions of these patches.

Please go ahead and r- all of these patches. However, I think we should leave this bug open as the master bug. I'll open new bugs for the new individual patches, and make this one dependent on those.

[Chris Marrin]

Comment on attachment 65642 [details]
Core data structures: Arena, RedBlackTree and IntervalTree

Reject patch based on recent discussion

[Chris Marrin]

Comment on attachment 65661 [details]
Cubic curve classification, texture coordinate assignment, local triangulation and math utilities

Reject patch based on recent discussion

[Chris Marrin]

Comment on attachment 65663 [details]
Path processing results and shader management classes

Reject patch based on recent discussion

[Chris Marrin]

Comment on attachment 65664 [details]
The PathProcessor, which implements the main algorithm

Reject patch based on recent discussion

[Kenneth Russell]

The revised red-black tree is out for review under https://bugs.webkit.org/show_bug.cgi?id=45059 , but I'd like to reply to these review comments here.

The Arena class has been gutted, is now named PODArena and uses Arena.h for its implementation. Removing all of the review feedback for that class below.

(In reply to comment #28)
> (From update of attachment 65642 [details])
> WebCore/platform/graphics/gpu/IntervalTree.h:42
>  +  #include <iostream>
> We don't usually use iostream.  Perhaps you means to use LOG?

Changed throughout.

> WebCore/platform/graphics/gpu/IntervalTree.h:96
>  +      const T& low() const
> These can be on a single line.

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:122
>  +      // Returns true if this interval overlaps the other.
> This comment is pretty content-free.

Removed. There were a bunch of redundant comments in the previous code to obey the Google C++ coding style.

> WebCore/platform/graphics/gpu/IntervalTree.h:112
>  +      // given low and high endpoints.
> This comment is pretty content-free.

Removed.

> WebCore/platform/graphics/gpu/IntervalTree.h:144
>  +      // Summary information needed for efficient queries.
> Please remove this comment.

Done, though I think it is probably worth documenting what it is.

> WebCore/platform/graphics/gpu/IntervalTree.h:154
>  +      void setMaxHigh(const T& maxHigh) const
> Seems strange to have a const setter.

This was only to obey Google C++ style rules, which don't allow non-const references. Changed.

> WebCore/platform/graphics/gpu/IntervalTree.h:218
>  +      void allOverlaps(const IntervalType& interval,
> These parameters should be on one line.

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:221
>  +          // gcc requires explicit dereference of "this" here
> Why?  Is there a variable shadowing root?

No, it's because of C++ rules about inheritance in template classes. It just happens that certain non-compliant C++ compilers allow "this" to be elided. Updated the comment.

> WebCore/platform/graphics/gpu/IntervalTree.h:228
>  +                                       const UserData data = 0)
> One line for these parameters.

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:226
>  +      static IntervalType makeInterval(const T& low,
> Usually we call these sorts of functions createInterval.

Changed.

> WebCore/platform/graphics/gpu/IntervalTree.h:234
>  +      // Returns true if the tree's invariants are preserved.
> Maybe remove this comment and rename to checkInvariants?

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:251
>  +          // gcc requires explicit dereference of "this" here
> ??

See above.

> WebCore/platform/graphics/gpu/IntervalTree.h:260
>  +                                 Vector<IntervalType>& res)
> One line

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:272
>  +              // interval.low() <= left->data().maxHigh()
> Can we make this an ASSERT instead of a comment?

No, because the whole point is to avoid needing operator <= on type T. Adjusted the comment.

> WebCore/platform/graphics/gpu/IntervalTree.h:282
>  +          // node->data().low() <= interval.high()
> Again, perhaps an ASSERT?

See above.

> WebCore/platform/graphics/gpu/IntervalTree.h:293
>  +          if (left)
> Multiline if should have { }

This is really unclear in the WebKit style guidelines. I had been thinking that if the if or else clause was a single expression that there were supposed to be no braces. Changed.

> WebCore/platform/graphics/gpu/IntervalTree.h:297
>  +          if (right)
> ditto

Done.

> WebCore/platform/graphics/gpu/IntervalTree.h:309
>  +      // Returns true if the tree's invariants are preserved.
> Again, why not just name the function what this comment says and remove the comment?

Done.

> WebCore/platform/graphics/gpu/RedBlackTree.h:69
>  +  #define gpu_RedBlackTree_h
> As the stylebot says, these include guards don't match the style guide.

I've removed the nested namespace.

> WebCore/platform/graphics/gpu/RedBlackTree.h:71
>  +  #ifndef NDEBUG
> We don't need to guard these includes.

They are unused except in debug mode, where the printing code is enabled. I think it is better to guard them.

> WebCore/platform/graphics/gpu/RedBlackTree.h:93
>  +          virtual ~Visitor() {}
> Are you really going to destruct the visitor?  I'd move this to a private destructor.

I've made the virtual destructor protected, which seems to match the style in other interface-like classes in WebKit.

> WebCore/platform/graphics/gpu/RedBlackTree.h:122
>  +      virtual ~RedBlackTree()
> One line is sufficient here.

Done.

> WebCore/platform/graphics/gpu/RedBlackTree.h:126
>  +      // Inserts a datum into the tree.
> Please remove useless comment.

Done.

> WebCore/platform/graphics/gpu/RedBlackTree.h:146
>  +      bool contains(const T& data)
> One line.  What's the point of having this function if it just calls through to treeSearch?

Done. The wrapper is needed. TreeSearch returns a private Node* data type, and is called from more than one public method.

> WebCore/platform/graphics/gpu/RedBlackTree.h:152
>  +      // each one.
> Please remove useless comment.

Done.

> WebCore/platform/graphics/gpu/RedBlackTree.h:155
>  +          if (m_root)
> Prefer early returns.

Changed.

> WebCore/platform/graphics/gpu/RedBlackTree.h:159
>  +      // Returns the number of elements in the tree.
> Really?

Ha ha. Removed.

> WebCore/platform/graphics/gpu/RedBlackTree.h:223
>  +          Color color() const
> One line.

Done.

> WebCore/platform/graphics/gpu/RedBlackTree.h:358
>  +      void treeInsert(Node* z)
> These variable names are kind of mysterious to me.  Maybe z -> newNode?

The names match those in the algorithms book. I *really* do not want to change them.

> WebCore/platform/graphics/gpu/RedBlackTree.h:511
>  +                          if (m_verboseDebugging)
> Bad indent?

Fixed.

> WebCore/platform/graphics/gpu/RedBlackTree.h:723
>  +          int count()
> One line.  const

Done.

[Kenneth Russell]

I've uploaded a new patch for the classifier under https://bugs.webkit.org/show_bug.cgi?id=45249, but I'll reply to your review feedback here.

(In reply to comment #29)
> (From update of attachment 65661 [details])
> WebCore/platform/graphics/gpu/CubicClassifier.cpp:44
>  +                                                    float b3x, float b3y) {
> { should be on the next line.

This code has been rewritten to use FloatPoint, so this line doesn't exist in this form any more.

> WebCore/platform/graphics/gpu/CubicClassifier.cpp:45
>  +      Vector3 b0(b0x, b0y, 1);
> These names are terrible.

These match precisely the terminology in the GPU Gems 3 chapter. I've added a comment indicating this.

> WebCore/platform/graphics/gpu/CubicClassifier.h:67
>  +          CurveType curveType() const
> one line

Done.

> WebCore/platform/graphics/gpu/CubicClassifier.h:72
>  +          float d1() const
> one line

Done.

[Kenneth Russell]

I've uploaded a new patch for the math utilities needed for this algorithm under https://bugs.webkit.org/show_bug.cgi?id=45251 , but I'll reply to your review feedback here.

Note that I rewrote the code based on your and Maciej's feedback to use FloatPoint everywhere possible, which cleaned it up quite a bit (thanks) and addresses several of your review points.

(In reply to comment #29)
> (From update of attachment 65661 [details])
> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:52
>  +      // p3 = (x3, y3)
> This comment is mysterious to me.  Should we be using a Point class instead of passing around disconnected floats?

Yes. Done.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:114
>  +               != orientation(p1x, p1y, q1x, q1y, q2x, q2y))
> Please merge with previous line.

Done.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:116
>  +                  != orientation(p2x, p2y, q2x, q2y, q1x, q1y)));
> Please merge with previous line.

Done.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:119
>  +  bool pointInTriangle(float px, float py,
> All this code is really begging for FloatPoint (see IntPoint in the render tree for the int version).

Agreed. It's been rewritten.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:156
>  +      // Derived from coplanar_tri_tri() at
> What's the license on that code?  If this is a derived work, we need to be careful about copyright. 

There is no explicit license in the original code or any mentioned in the paper.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:162
>  +      if (edgeAgainstTriEdges(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y))
> Can we merge all these using || ?

Yes. Done.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:190
>  +  #define NearlyZeroConstant (1.0f / (1 << 12))
> Why a macro and not a const float?

Only because it was a macro in the original Skia code. Changed.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:194
>  +      ASSERT(tolerance > 0.0);
> This could be a COMPILE_ASSERT

I don't follow this. Left it as is.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:201
>  +  static inline float interp(float a, float b, float t)
> Please don't abbreviate word like this.  You and I might know what interp means, but someone reading this code in the future might be confused.  Also, static is redundant with inline.

Sorry. Renamed to interpolate. Removed static.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:218
>  +      float bcd = interp(bc, cd, t);
> More mysterious variable names.

This particular code came directly from Skia and I really don't want to mess with the naming conventions.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:224
>  +  static bool evalCubicAt(const FloatPoint cubic[4], float t, FloatPoint& pt)
> Oh!  We do have FloatPoint!  We should really use that all over this code.  Also, instead of declaring all these functions static, just put them in an anonymous namespace.  That's the C++ way of doing the same thing.

Changed to use FloatPoint and anonymous namespaces.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:230
>  +  static bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool* ambiguous)
> We use non-const references for outparams.  Yes, that sucks, but it's the way we roll.

Changed.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:249
>  +      bool pointAtExtremum = (xRay.y() == cubic[3].y());
> const?

Changed.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:278
>  +      float upperT;
> What is T?

Basically the evaluation parameter for the cubic, [0..1].

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:290
>  +          float t = 0.5 * (upperT + lowerT);
> I see.  Hum...
> 
> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:296
>  +      } while (++iter < MaxIter && !nearlyZero(eval.y() - xRay.y()));
> I usually put a blank line after a do .. while since they're pretty rare.

Done.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:305
>  +  static int validUnitDivide(float numer, float denom, float* ratio)
> again, & for outparams

I can't change this one. This code came from Skia, again, and does some pretty hairy pointer arithmetic while solving for roots.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:324
>  +      return 1;
> In this case, maybe we should just return a struct?

Code came from Skia. I really don't want to touch it.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:315
>  +          return 0;
> Why 0/1 instead of true/false?  I don't quite get what's going on here.
> 
> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:347
>  +      r += validUnitDivide(c, Q, r);
> I see.  That's pretty mysterious.

Agreed. Again, this code came verbatim from Skia and I don't want to mess with it.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:423
>  +      for (int i = 0; i < roots - 1; i++) {
> We prefer preincrement.

Changed.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:432
>  +              memcpy(dst, src, 4*sizeof(FloatPoint));
> Ouch!  Shouldn't we use Vector<FloatPoint> rather than raw pointers!

Again, this code came verbatim from Skia and I don't want to mess with it.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:430
>  +      if (dst) {
> early return rather than massive nesting level?

Sure. Changed this particular Skia code.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:433
>  +          else {
> early return?

Sure. Changed this Skia code too.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:444
>  +                  memcpy(tmp, dst, 4 * sizeof(FloatPoint));
> This is a really unsafe pattern.  This code has no way to be sure how big dst or tValues are.

I agree, but this code came from Skia and I don't want to change it.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:445
>  +                  src = tmp;
> Yuck!  Please don't assign to your input parameters.

Skia code again.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:489
>  +      for (int i = 0; i < 7; i++)
> Magic constants make me sad.  Even if they are lucky number 7.

Skia code again.

> WebCore/platform/graphics/gpu/CubicMathUtils.cpp:493
>  +  // Public XRay queries.
> Ok.  I got tired.  This is as far as I got.

I think you'll find that this function and the one below (which I contributed to Skia and then ported out) are reasonably well structured.

[Kenneth Russell]

Created attachment 82741 [details]
Patch

[Mike Reed]

LGTM

[James Robinson]

Comment on attachment 82741 [details]
Patch

R=me

[Kenneth Russell]

Committed r78923: <http://trac.webkit.org/changeset/78923>

[WebKit Review Bot]

http://trac.webkit.org/changeset/78923 might have broken Leopard Intel Release (Build)