Bug 48031 - Make AffineTransform and TransformationMatrix do matrix multiplication in the correct order (Column Major)
: Make AffineTransform and TransformationMatrix do matrix multiplication in the...
Status: RESOLVED FIXED
Product: WebKit
Classification: Unclassified
Component: Platform
: 528+ (Nightly build)
: All All
: P2 Normal
Assigned To: Shane Stephens
:
Depends on: 48026 48215
Blocks: 52551
  Show dependency treegraph
 
Reported: 2010-10-20 17:02 PDT by Shane Stephens
Modified: 2011-02-15 18:04 PST (History)
9 users (show)

See Also:


Attachments
Patch (22.42 KB, patch)
2010-12-14 15:06 PST, Shane Stephens
no flags Details | Formatted Diff | Diff
Patch (23.62 KB, patch)
2011-01-10 22:25 PST, Shane Stephens
no flags Details | Formatted Diff | Diff
Patch (23.63 KB, patch)
2011-01-10 22:31 PST, Shane Stephens
no flags Details | Formatted Diff | Diff
Patch (22.75 KB, patch)
2011-01-13 16:17 PST, Shane Stephens
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Shane Stephens 2010-10-20 17:02:07 PDT
The result of a matrix multiplication is dependent on the order of the operands.  if I have the following code:

AffineTransform a = ...
AffineTransform b = ...
AffineTransform c = a * b;

currently c is given the value of b * a, not a * b.  Looking through the code, we see:

// result = *this * t (i.e. a multRight)
AffineTransform operator*(const AffineTransform& t) const
{
  AffineTransform result = t;
  result.multLeft(*this);
  return result;
}

multLeft is a post-multiply - i.e. result.multLeft(*this) assigns result * this to result.  This means that we return t * this, not this * t as expected.

Note that this is fairly difficult to fix as a lot of code uses the incorrect definition, with reversed arguments to generate the correct behaviour.  I'd also be interested in renaming the multLeft method to something less confusing (e.g. postMultiply) in order to reduce the chance of this happening again.
Comment 1 Shane Stephens 2010-10-26 16:00:27 PDT
I'm preparing a patch for this but would like to wait for 48026 and 48215 to be committed first, to keep the switching of argument order consistent in all places where it is required.
Comment 2 Dirk Schulze 2010-10-26 23:10:41 PDT
Hm, I'm a bit confused. You say that *operator is wrong. But you want to change the operand order there first to get correct results. But after these patches you want to fix AffineTransform (have not lookad at AffineTransform yet). Won't you break SVGText and SVGStyledTransformable again?
Comment 3 Shane Stephens 2010-10-26 23:23:49 PDT
Yeah - I want to fix SVGText and SVGStyledTransformable first as they are definitely producing incorrect behaviour and have small, self-contained fixes.

Once they are in and protected by layout tests, I want to fix AffineTransform operator* and switch operand order for ALL cases that use it (including the fixed versions in SVGText and SVGStyledTranformable).  This is a relatively invasive change so I want to simplify it as much as possible; it's also a change that (hopefully) won't change any behaviour and is thus much less urgent than the SVGText and SVGStyledTransformable fixes.
Comment 4 Dirk Schulze 2010-10-27 01:07:48 PDT
Sounds good!
Comment 5 Shane Stephens 2010-12-14 15:06:32 PST
Created attachment 76578 [details]
Patch
Comment 6 Nikolas Zimmermann 2010-12-15 05:27:29 PST
Hi Shane,

I didn't yet look into your patch in detail. Just noticed that on trunk LayoutTests/svg/W3C-SVG-1.1/animate-elem-24-t.svg is broken, which worked some weeks (months?) ago. Is it maybe caused by one of your patches?

Thanks in advance,
Niko
Comment 7 Dirk Schulze 2010-12-15 09:18:16 PST
Comment on attachment 76578 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=76578&action=review

> WebCore/platform/graphics/cg/PatternCG.cpp:57
> +    AffineTransform patternTransform = userSpaceTransformation * m_patternSpaceTransformation;

I'm unsure if multLeft could be faster, since it memcopy's the values for affine1 = affine2 IIRC. And might have some additional improvements. Can you check this please? It's some time ago that I looked at AffineTransform :-P
Comment 8 Shane Stephens 2010-12-15 14:45:27 PST
I looked at performance in some detail, as I didn't want to cause degradation.  The story is basically this:

The old multLeft didn't really multLeft, and is now called postMultiply - same implementation and same performance characteristics.

The old operator* code:
    AffineTransform operator*(const AffineTransform& t) const
    {
        AffineTransform result = t;
        result.multLeft(*this);
        return result;
    }

This contains two copies of AffineTransform - once when t is assigned to result, and once when result is returned by value.

The old operator*= is implemented in terms of operator*, and multiply in terms of operator*=.  Thus all of these operations cost at least 2 copies of AffineTransform plus the implementation of multLeft.

The new multiply and operator*= implementations use postMultiply directly, and are thus cheaper by at least 2 copies of AffineTransform.  The new operator* is implemented in the same way as the old operator*:
        AffineTransform result = *this;
        result *= t;
        return result;
and incurs the same 2 copies, costing the same as the old operator*.

Hence, by replacing the old use of multiply with operator* here, I'm not incurring any additional cost.  Actually, by eliminating an assignment I'm reducing the cost by one AffineTransform copy.

I think you're right that doing the following:

AffineTransform patternTransform = userSpaceTransformation;
patternTransform.multiply(m_patternSpaceTransformation);

Would reduce the cost still further, so I'm going to roll that into this patch.
Comment 9 Shane Stephens 2010-12-15 14:50:13 PST
Niko, that test is passing for me locally - can you show me a buildbot server or something where it's failing so I can see what the failure mode is?
Comment 10 Shane Stephens 2010-12-15 16:05:59 PST
Actually my analysis is wrong, RVO means that 1 of these copies will not happen anyway, so I don't think we buy anything by this change.
Comment 11 Nikolas Zimmermann 2010-12-16 01:12:38 PST
(In reply to comment #9)
> Niko, that test is passing for me locally - can you show me a buildbot server or something where it's failing so I can see what the failure mode is?

The test will pass when running it with run-webkit-tests. That's because of the fact that the actual animations are _not_ executed. The test is sampled at it's initial state. Any test containing <animate>/... elements that doesn't use the "SVG animation snapshot API" (as the tests in svg/animations) will not actually execute the animation.

So you have to manually open it. You'll notice that the "It's alive" text is flying in the wrong location.
Can you confirm?
Comment 12 Shane Stephens 2010-12-19 15:07:07 PST
Yes, this test is failing locally and it's probably failing as a result of 48215.  Unfortunately the bug I fixed in 48215 introduced another bug that's now evident in LayoutTests/svg/W3C-SVG-1.1/animate-elem-24-t.svg :(

The messy details:

SVGStyledTransformableElement instances have a TransformList and a supplementalTransform.  While AnimateTransform elements update values in the TransformList, AnimateMotion elements update the supplementalTransform.  Crucially, transform values provided in the transform attribute of an element also appear in the TransformList.

The order in which these matrices are accumulated matters - for example, a rotate followed by a translate does not produce the same result as a translate followed by a rotate.

The problem that I fixed in 48215 was caused by the AnimateMotion's transform being applied first, before anything in the TransformList; whereas the specification indicates that this transform should be applied after values in the transform attribute.

Unfortunately, what I did was move the application of AnimateMotion to the end - i.e. after everything in the TransformList.  From the animate-elem-24-t.svg test, it appears that this is also wrong.  In fact, it's possible that the supplementalTransform needs to apply after some TransformList values but before others, in which case it might make sense to remove the supplementalTransform altogether and use the TransformList for AnimateMotion as well.  I'll read the specification carefully and seek guidance on the svg-wg list if necessary to determine what's appropriate.

This current bug, however, is unrelated in that it doesn't (or at least, shouldn't) change the behaviour of any of the code - it's simply about fixing the order of operands in matrix multiplication.  So I'd like to propose filing the fact that animate-elem-24-t.svg fails as a separate bug.  While we're at it, it seems like we should be modifying or copying any animation tests in this directory so that we have versions that actually work with run-webkit-tests.  If this test was actually testing when I was working on 48215 I probably would have picked up the issue then.
Comment 13 Eric Seidel 2010-12-24 17:07:25 PST
I'm entertained by this, since I believe we had * reversed for SVGMatrix for the longest time.  We might still?
Comment 14 Nikolas Zimmermann 2010-12-26 03:33:15 PST
(In reply to comment #12)
> Yes, this test is failing locally and it's probably failing as a result of 48215.  Unfortunately the bug I fixed in 48215 introduced another bug that's now evident in LayoutTests/svg/W3C-SVG-1.1/animate-elem-24-t.svg :(
Okay.

> 
> The messy details:
> 
> SVGStyledTransformableElement instances have a TransformList and a supplementalTransform.  While AnimateTransform elements update values in the TransformList, AnimateMotion elements update the supplementalTransform.  Crucially, transform values provided in the transform attribute of an element also appear in the TransformList.
Yes, in my opinion the supplementalTransform stuff is a huge hack anyway, as it forces each element transformable element to store another AffineTransform object, even when not animated. It was a crude hack, when animation was implemented in the beginning, to get Acid3 going...

> 
> The order in which these matrices are accumulated matters - for example, a rotate followed by a translate does not produce the same result as a translate followed by a rotate.
> 
> The problem that I fixed in 48215 was caused by the AnimateMotion's transform being applied first, before anything in the TransformList; whereas the specification indicates that this transform should be applied after values in the transform attribute.
Right.

> 
> Unfortunately, what I did was move the application of AnimateMotion to the end - i.e. after everything in the TransformList.  From the animate-elem-24-t.svg test, it appears that this is also wrong.  In fact, it's possible that the supplementalTransform needs to apply after some TransformList values but before others, in which case it might make sense to remove the supplementalTransform altogether and use the TransformList for AnimateMotion as well.  I'll read the specification carefully and seek guidance on the svg-wg list if necessary to determine what's appropriate.
Great. I think you should investigate to use TransformList directly. When we have animVal support, this is the way to go anyways. (transformList.animVal needs to reflect any animation done by animateTransform and/or animateMotion).

> 
> This current bug, however, is unrelated in that it doesn't (or at least, shouldn't) change the behaviour of any of the code - it's simply about fixing the order of operands in matrix multiplication.  So I'd like to propose filing the fact that animate-elem-24-t.svg fails as a separate bug. 
Fine with me! I'll review this patch soon.

> While we're at it, it seems like we should be modifying or copying any animation tests in this directory so that we have versions that actually work with run-webkit-tests.  If this test was actually testing when I was working on 48215 I probably would have picked up the issue then.
That would be great! You'd need to copy the tests from svg/W3C-SVG-1.1/animate* to svg/animations, and extend them to use the SVG Animation snapshot API.
But it will take a huge amount of time to convert them all to use the DRT snapshot API, as you have to write JS code for each sampling point, checking the values, whether they are correct etc etc.
If you want to work on that, it would be highly appreciated!

Cheers,
Niko
Comment 15 Nikolas Zimmermann 2010-12-26 03:34:11 PST
(In reply to comment #13)
> I'm entertained by this, since I believe we had * reversed for SVGMatrix for the longest time.  We might still?
Indeed, SVGMatrix is working around the * reversal a long time :-) The SVGMatrix exposed API works as expected, but only as foo * bar, is rewritten as foo.postMultiply(bar) internally :-)
Thanks to Shane, the root of the confusion is now fixed.
Comment 16 Dirk Schulze 2011-01-02 11:23:59 PST
Comment on attachment 76578 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=76578&action=review

The patch looks good in general, but I'd prefer to use multiply and postMultiply where ever possible. Another question, would it make sense to rename multiply with preMultiply corresponding to postMultiply?

r- for the questions above and the wrong comment style.

> WebCore/platform/graphics/transforms/AffineTransform.cpp:170
> +/**
> + * Multiplies this AffineTransform by the provided AffineTransform - i.e.
> + * this = this * other;
> + */

Comments with //
Comment 17 Simon Fraser (smfr) 2011-01-02 12:16:37 PST
Bug 16062 gives some back story into the various matrix multiplication issues.

But I'm not convinced that there is a bug here.

> multLeft is a post-multiply - i.e. result.multLeft(*this) assigns result * this to result.  This means that we return t * this, not this * t as expected.

In my reading result.multLeft(*this) is result = *this * result.

TransformationMatrix has the same code. If you fix AffineTransform, please fix that as well.

BTW, if you're working on a bug, please assign it to yourself.
Comment 18 Shane Stephens 2011-01-03 13:34:59 PST
Dirk: both multiply and postMultiply do the same thing.  The following all produce the same result:

a *= b
a.multiply(b)
a.postMultiply(b)

Furthermore, the same result can be obtained in a fresh AffineTransform using:

a * b

The reason I'm keener on using a *=b and a * b over multiply, postMultiply or a new preMultiply function is that I think there's significant potential for confusion of what postMultiply and preMultiply *mean*, and multiply could conceivably mean either one or the other.

On the other hand, I think a * b is unambiguous and has a reasonably obvious meaning - there's only one correct answer, which is to multiply a on the left by b on the right.  Similarly a *= b is well understood to be equivalent to a = a * b.

Simon: For the clearest example of why this is a bug, look at the implementation of a * b.  The result is currently b * a.  Say that 'a' is a translation matrix (1, 0, 0, 1, 100, 10), and 'b' is a scale matrix (1.5, 0, 0, 1.2, 0, 0).

[ 1   0   100] [1.5   0    0 ] [1.5   0    100]
[ 0   1   10 ]x[ 0   1.2   0 ]=[ 0   1.2   10 ]
[(0) (0)  (1)] [(0)  (0)  (1)] [(0)  (0)   (1)]

However AffineTransform's operand gives (1.5, 0, 0, 1.2, 150, 12), which is b * a.  This is independent of 16062 - as you can see this notation already uses SVG's column vector orientation and does not arise because of translation to CG matrices.
Comment 19 Shane Stephens 2011-01-03 13:35:48 PST
I can't assign this bug to myself :(
Comment 20 Simon Fraser (smfr) 2011-01-03 13:36:47 PST
(In reply to comment #19)
> I can't assign this bug to myself :(
Ask for editbugs privs on webkit-dev.
Comment 21 Dirk Schulze 2011-01-03 14:24:31 PST
(In reply to comment #18)
> Dirk: both multiply and postMultiply do the same thing.  The following all produce the same result:
> 
> a *= b
> a.multiply(b)
> a.postMultiply(b)
> 
> Furthermore, the same result can be obtained in a fresh AffineTransform using:
> 
> a * b
> 
> The reason I'm keener on using a *=b and a * b over multiply, postMultiply or a new preMultiply function is that I think there's significant potential for confusion of what postMultiply and preMultiply *mean*, and multiply could conceivably mean either one or the other.
> 
> On the other hand, I think a * b is unambiguous and has a reasonably obvious meaning - there's only one correct answer, which is to multiply a on the left by b on the right.  Similarly a *= b is well understood to be equivalent to a = a * b.
> 
> Simon: For the clearest example of why this is a bug, look at the implementation of a * b.  The result is currently b * a.  Say that 'a' is a translation matrix (1, 0, 0, 1, 100, 10), and 'b' is a scale matrix (1.5, 0, 0, 1.2, 0, 0).
> 
> [ 1   0   100] [1.5   0    0 ] [1.5   0    100]
> [ 0   1   10 ]x[ 0   1.2   0 ]=[ 0   1.2   10 ]
> [(0) (0)  (1)] [(0)  (0)  (1)] [(0)  (0)   (1)]
> 
> However AffineTransform's operand gives (1.5, 0, 0, 1.2, 150, 12), which is b * a.  This is independent of 16062 - as you can see this notation already uses SVG's column vector orientation and does not arise because of translation to CG matrices.

Independent of what AffineTransfrom is doing right now, I don't want multiple function names for the same operation. To be honest a.multiply(b) already sounds like a = a * b; for me, why I would prefer multiply against postMultiply. And multLeft should do the opposite.
Comment 22 Shane Stephens 2011-01-03 14:30:37 PST
Yes, that seems fair.

There's never actually been a multLeft / preMultiply - the function that was called multLeft was implemented incorrectly and actually did a multRight.  I can add one if you want - it'll make some code paths slightly faster.  If I do, I'd like to call it preMultiply, keep postMultiply, and remove multiply.  

Alternatively, if we don't want to add a preMultiply, I'd like to remove postMultiply altogether, and just have multiply, * and *=.

In other words, I think we should either have multiply / * / *=, all of which do the same thing, or preMultiply / postMultiply / * / *=, with preMultiply doing the opposite of the rest.

What do you think?
Comment 23 Chris Marrin 2011-01-03 15:52:00 PST
Simon and I discussed this issue just now. We've agreed for a while now (and the 3D CSS Transform spec says this) that we use "column-major" matrices throughout. That means you can look at an affine transform as:

        A    C    tx
        B    D    ty

where (AB) forms a 2D vector which defines the X axis transformation, and (CD) defines the Y axis. That's column-major because the row index changes more quickly than the column index, as you extract the vectors (A is row 0, column 0, B is row 1, column 0). An identity matrix is:

        1    0    0
        0    1    0

The first column is a vector along the X axis and the second column is a vector along the Y axis. That would be the same if this were a row-major matrix, too, of course. But if you rotate the vectors by 45 degrees, you get an X vector at (0.707, 0.707) and a Y vector at (-0.707, 0.707). Plug those in and you get:

        0.707    -0.707    0
        0.707      0.707    0

If this were a row-major matrix the -0.707, would be in the lower left corner instead. Move these concepts to the 4x4 matrix and you get the translation values in the rightmost column, the X vector in the first column and so on. 

I think the most confusing thing in the implementation currently (except for misnaming multLeft) is that the attributes for the 4x4 matrix go column, row, rather than row, column. So tx is in m41. But I think this is the right labeling since the numbering goes MAJOR, minor. Column is the major index, so it goes first. 

One other thing we discussed is what it means to "multiply". What happens when you multiply: translate(0, 5) * rotate(45deg)? That is a translation matrix and to its right, a rotation matrix. If you start with the identity matrix and multiply that by the translation matrix (with the translation on the right), you get the translation matrix of course. But what is happening is that you are changing the local coordinate space by the translation value. So now, point (0,0,0) in the local coordinate space is actually (0,5,0) in the global coordinate space. Now when you rotate that you are rotating about (0,0,0) in the local coordinate space. If you start with a box at (0,0,0) you will end up with a box rotated 45 degrees whose center is at (0,5,0).

So that's the definition of multRight. If we had done it in the opposite order (rotate and then translate) we would end up with a box still rotated 45 degrees, but whose center is (-3.54, 3.54, 0). That's because you first rotate the local coordinate space so that now the Y axis goes up and to the left, at a 45 degree angle. We translate along that axis and end up with a box out in the middle of quadrant 2.

If you look at TransformationMatrix.cpp you'll see a function called multLeft(). But if you look at what it's multiplying it's actually a multRight. AffineMatrix also has a translateRight() function which is actually doing a multLeft!

I like the fact that your patch gets rid of any multRight or multLeft functions and just has the one postMultiply, which is doing a multRight. I think we should also get rid of translateRight and change the call sites to use multiply() or operator*. In TransformationMatrix I think we should also get rid of the incorrectly named functions in a similar way.

I hope this makes things more clear rather than less! I know I feel more clear on it.
Comment 24 Shane Stephens 2011-01-10 22:25:12 PST
Created attachment 78494 [details]
Patch
Comment 25 WebKit Review Bot 2011-01-10 22:27:22 PST
Attachment 78494 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1
Source/WebCore/ChangeLog:8:  Line contains tab character.  [whitespace/tab] [5]
Source/WebCore/ChangeLog:9:  Line contains tab character.  [whitespace/tab] [5]
Total errors found: 2 in 22 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 26 Shane Stephens 2011-01-10 22:31:24 PST
Created attachment 78495 [details]
Patch
Comment 27 Shane Stephens 2011-01-10 22:31:49 PST
This patch removes postMultiply from AffineTransform altogether and fixes the style issues commented on.

I'd like to update AffineTransform's translateRight and fix the TransformationMatrix issues as two additional bugs - each is quite large and I've not yet completely gotten across the internals of TransformationMatrix.

Accordingly, I think this patch is ready to go - it fixes the operand order issue in AffineTransform, makes sure that the arguments are switched appropriately in all the call sites, and ensures that the multiplication calls in AffineTransform are easier to understand.

Let me know if this is OK, and I'll file separate bugs for translateRight and TransformationMatrix and start working on them :)
Comment 28 Nikolas Zimmermann 2011-01-13 02:49:48 PST
Comment on attachment 78495 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=78495&action=review

Looks good, though still some things to resolve IMHO.

> Source/WebCore/platform/graphics/transforms/AffineTransform.h:149
> +        return this->multiply(t);

s/this->// it's not needed.

> Source/WebCore/platform/graphics/transforms/AffineTransform.h:183
> +    AffineTransform& postMultiply(const AffineTransform&);

Where is postMultiply defined/used??

> Source/WebCore/rendering/svg/RenderSVGResourceContainer.cpp:18
> + *

Looks unrelated.

> Source/WebCore/rendering/svg/RenderSVGResourceGradient.cpp:21
> + *

Ditto.

> Source/WebCore/rendering/svg/RenderSVGResourcePattern.cpp:19
> + *

Ditto.

> Source/WebCore/rendering/svg/SVGImageBufferTools.cpp:46
> -        absoluteTransform.multiply(current->localToParentTransform());
> +        absoluteTransform = current->localToParentTransform() * absoluteTransform;

This is a place, where your postMultiply method would be useful, no?
absoluteTransform.postMultiply(current->localToParentTransform()).

I think this would be easier to read/understand, as the current solution, and it's for sure faster, as it avoids the assignment operator usage, after the multiplication.

> Source/WebCore/rendering/svg/SVGImageBufferTools.cpp:87
> -    contentTransformation.multiply(subtreeContentTransformation);
> +    contentTransformation = subtreeContentTransformation * contentTransformation;
>  

Ditto.

> Source/WebCore/rendering/svg/SVGTextLayoutEngine.cpp:324
> -                transform.multiply(textBoxTransformation);
> +                transform = textBoxTransformation * transform;

Ditto. (Several more places which could make use of postMultiply, didn't mention all of them)
Comment 29 Shane Stephens 2011-01-13 16:17:27 PST
Created attachment 78871 [details]
Patch
Comment 30 Shane Stephens 2011-01-13 16:48:26 PST
Just a note about postMultiply - the old function (multLeft) was in fact a postMultiply.  I was going to rename it to that (and did in the first patch), but now I'm just renaming it to multiply instead.  What that function (multLeft / postMultiply / multiply) does is the following:
a.multiply(b) causes a to take on the value of a * b.

There has never been an efficient function in AffineTransform to do a true multLeft (also called preMultiply) - i.e. a.preMultiply(b) taking a to b * a.  The current (pre this patch) implementations of *, multiply, and *= all performed this, but quite inefficiently.

This patch is actually all about removing the confusing state of affairs we currently have, where multLeft really does a multRight, and multiply, * and *= do a multLeft - the opposite of what you'd expect.

To see what I mean by inefficiently, have a look at the pre-patch version of operator*:
    AffineTransform operator*(const AffineTransform& t) const
    {
        AffineTransform result = t;
        result.multLeft(*this);
        return result;
    }

and operator*=:
    AffineTransform& operator*=(const AffineTransform& t)
    {
        *this = *this * t;
        return *this;
    }


So to do a *=, we
(1) calculate *this * t, which:
   (a) copies t into result
   (b) does a multLeft (which is really a postMultiply, remember)
   (c) returns the result
(2) copy the result back into *this

That's just a postMultiply with two copies!  (I think - RVO doesn't apply here because the input and the output to operator* are the same object), which is exactly what happens with this:

absoluteTransform = current->localToParentTransform() * absoluteTransform;

This is actually potentially faster as there's one less function call :)  It's also easier to read than what previously existed, because what previously existed was actually wrong (the inputs were switched around):

absoluteTransform.multiply(current->localToParentTransform());

But note that if we were to try and write this more efficiently, we'd actually want a *preMultiply*, not a postMultiply - i.e. something like:

absoluteTransform.preMultiply(current->localToParentTransform());

Now, I could implement one of these, and I'd be very happy to, either in this bug or as a new one (I'd prefer doing it in a separate bug as I think the current change stands on its own as clearing up an important confusion).  But it's important to remember that:
(1) what was called multLeft was misnamed and in fact should be called multRight, multiply or postMultiply.
(2) operator*, operator*= and multiply all currently don't do what they advertise - they should do a multRight but they do a multLeft
(3) there has *never* been a genuine, fast multLeft / preMultiply - operator*, operator*= and multiply provide this functionality but only by switching the arguments around and using multLeft's postMultiply functionality.
So this patch is strictly an improvement.

I've fixed the other problems that you noticed, thanks for having a look at the patch!
Comment 31 Nikolas Zimmermann 2011-01-14 01:53:48 PST
(In reply to comment #30)
> Just a note about postMultiply - the old function (multLeft) was in fact a postMultiply.  I was going to rename it to that (and did in the first patch), but now I'm just renaming it to multiply instead.  What that function (multLeft / postMultiply / multiply) does is the following:
> a.multiply(b) causes a to take on the value of a * b.
> 
> There has never been an efficient function in AffineTransform to do a true multLeft (also called preMultiply) - i.e. a.preMultiply(b) taking a to b * a.  The current (pre this patch) implementations of *, multiply, and *= all performed this, but quite inefficiently.
> 
> This patch is actually all about removing the confusing state of affairs we currently have, where multLeft really does a multRight, and multiply, * and *= do a multLeft - the opposite of what you'd expect.
> 
> To see what I mean by inefficiently, have a look at the pre-patch version of operator*:
>     AffineTransform operator*(const AffineTransform& t) const
>     {
>         AffineTransform result = t;
>         result.multLeft(*this);
>         return result;
>     }
> 
> and operator*=:
>     AffineTransform& operator*=(const AffineTransform& t)
>     {
>         *this = *this * t;
>         return *this;
>     }
> 
> 
> So to do a *=, we
> (1) calculate *this * t, which:
>    (a) copies t into result
>    (b) does a multLeft (which is really a postMultiply, remember)
>    (c) returns the result
> (2) copy the result back into *this
> 
> That's just a postMultiply with two copies!  (I think - RVO doesn't apply here because the input and the output to operator* are the same object), which is exactly what happens with this:
> 
> absoluteTransform = current->localToParentTransform() * absoluteTransform;
> 
> This is actually potentially faster as there's one less function call :)  It's also easier to read than what previously existed, because what previously existed was actually wrong (the inputs were switched around):
> 
> absoluteTransform.multiply(current->localToParentTransform());
> 
> But note that if we were to try and write this more efficiently, we'd actually want a *preMultiply*, not a postMultiply - i.e. something like:
> 
> absoluteTransform.preMultiply(current->localToParentTransform());
> 
> Now, I could implement one of these, and I'd be very happy to, either in this bug or as a new one (I'd prefer doing it in a separate bug as I think the current change stands on its own as clearing up an important confusion).  But it's important to remember that:
> (1) what was called multLeft was misnamed and in fact should be called multRight, multiply or postMultiply.
> (2) operator*, operator*= and multiply all currently don't do what they advertise - they should do a multRight but they do a multLeft
> (3) there has *never* been a genuine, fast multLeft / preMultiply - operator*, operator*= and multiply provide this functionality but only by switching the arguments around and using multLeft's postMultiply functionality.
> So this patch is strictly an improvement.
> 
> I've fixed the other problems that you noticed, thanks for having a look at the patch!

Okay, fair enough, I follow your argumentation.
I'm only worried if we shouldn't just agree on a single way to do pre-multiplications / post-multiplications.

eg. either
a = a * b or a *= b
a = b * a

or
a.preMultiply(b) (a = b * a)
a.postMultiply(b) (a = a * b)

Instead of having multiple choices... what do you think?
Comment 32 Dirk Schulze 2011-01-14 01:56:37 PST
> eg. either
> a = a * b or a *= b
> a = b * a
> 
> or
> a.preMultiply(b) (a = b * a)
> a.postMultiply(b) (a = a * b)
> 
> Instead of having multiple choices... what do you think?

In my opinion we should use pre- and postMultiply in all places. But that's my opinion.
Comment 33 Chris Marrin 2011-01-14 15:02:40 PST
It would be much better now and in the future if we just did matrix multiplication in one direction. There should be a multiply function where a.multiply(b) is the same as a * b, operator* which does the obvious order and operator *= where a *= b is the same as a = a * b. It needs to be made clear somewhere that for matrix math a * b != b * a. But I think anyone using these functions will already know that.

The problem we have had in the past has been with the confusion of row-major vs column-major, which changes the meaning of 'multLeft' and 'multRight'. The terms pre- and postMultiply don't help either. We should have one way to do things and give it the simplest name. If someone wants b * a, he can change the order when making the call.
Comment 34 Dirk Schulze 2011-01-14 15:20:50 PST
(In reply to comment #33)
> It would be much better now and in the future if we just did matrix multiplication in one direction. There should be a multiply function where a.multiply(b) is the same as a * b, operator* which does the obvious order and operator *= where a *= b is the same as a = a * b. It needs to be made clear somewhere that for matrix math a * b != b * a. But I think anyone using these functions will already know that.
That matrices are no commutative should be clear and sometimes it is necessary to take b * a instead of a * b.

> The problem we have had in the past has been with the confusion of row-major vs column-major, which changes the meaning of 'multLeft' and 'multRight'. The terms pre- and postMultiply don't help either. We should have one way to do things and give it the simplest name. If someone wants b * a, he can change the order when making the call.

Ok so we don't use names at all but just operators? I guess this is less confusing and may shorten the discussion about the correct naming of a multiplication :-P.
Comment 35 Chris Marrin 2011-01-14 16:08:29 PST
(In reply to comment #34)
> (In reply to comment #33)
> > It would be much better now and in the future if we just did matrix multiplication in one direction. There should be a multiply function where a.multiply(b) is the same as a * b, operator* which does the obvious order and operator *= where a *= b is the same as a = a * b. It needs to be made clear somewhere that for matrix math a * b != b * a. But I think anyone using these functions will already know that.
> That matrices are no commutative should be clear and sometimes it is necessary to take b * a instead of a * b.
> 
> > The problem we have had in the past has been with the confusion of row-major vs column-major, which changes the meaning of 'multLeft' and 'multRight'. The terms pre- and postMultiply don't help either. We should have one way to do things and give it the simplest name. If someone wants b * a, he can change the order when making the call.
> 
> Ok so we don't use names at all but just operators? I guess this is less confusing and may shorten the discussion about the correct naming of a multiplication :-P.

I'd like to see us have a multiply() function which does the same thing as operator*. There are many cases where I want to use a function name to clarify chained operations. Of course, per my recent thread, maybe multiply() should be the same as operator*=. Or maybe we should have multiply which is the same as operator* and applyMutiplication() which is the same as operator*=.

Help me, Mr. Wizard!

For now, it would probably be the simplest and most sane, to have operator*, operator*= and multiply(), which does the same thing as operator*. I think that's the closest to the way it is today, right?
Comment 36 Shane Stephens 2011-01-16 14:40:39 PST
Almost - with this patch we have operator*, operator*= and multiply; however multiply does the same thing as *=.

I'm not sure that it makes sense for multiply (a normal instance method) to do the same thing as operator* - I think there's an expectation that instance methods operate directly on the instance.
Comment 37 Shane Stephens 2011-01-16 22:25:15 PST
I've removed translateRight from AffineTransform as a separate patch in 52551.  That patch relies on this one to work correctly.
Comment 38 Chris Marrin 2011-01-17 10:19:05 PST
(In reply to comment #36)
> Almost - with this patch we have operator*, operator*= and multiply; however multiply does the same thing as *=.
> 
> I'm not sure that it makes sense for multiply (a normal instance method) to do the same thing as operator* - I think there's an expectation that instance methods operate directly on the instance.

The problem with that is CSSMatrix and SVGMatrix both have multiply() functions which are immutable. I would not mind having a function which does what operator*= does, but we should call it something else: applyMultiplication (ick), applyMultiply (bad grammar), applyMatrix (maybe)? I don't have any better ideas.
Comment 39 Shane Stephens 2011-01-17 14:24:20 PST
In that case, in the interests of consistency, I think we should rename SVGMatrix::multiply with SVGMatrix::operator*, then provide a new multiply method that acts in-place (SVGMatrix is based on AffineTransform so this is trivial to do) and make use of it where we can.  We should of course also do the same thing with CSSMatrix :)

If you're amenable to this I'll track it and supply a patch in a separate bug.
Comment 40 Chris Marrin 2011-01-17 14:30:54 PST
(In reply to comment #39)
> In that case, in the interests of consistency, I think we should rename SVGMatrix::multiply with SVGMatrix::operator*, then provide a new multiply method that acts in-place (SVGMatrix is based on AffineTransform so this is trivial to do) and make use of it where we can.  We should of course also do the same thing with CSSMatrix :)

But making multiply() mutable is the opposite of what the JavaScript methods do. So for now, I'd rather any function named "multiply()" is immutable. We can deal with making a consistent set of mutable functions later.
Comment 41 Shane Stephens 2011-01-17 14:56:33 PST
Ah, that is a shame.

I tend to feel that methods should operate on the instance they're called on, in the sense that operator*= does.  Binary operators like an immutable multiply should instead be functions of two arguments in this world view.  Of course this is complicated because C++ treats operator* as a method even though it should never modify the called instance.

I guess we have to stick with what we've got, though :)  Given that multiply is currently identical to *=, I could just remove multiply altogether for this patch?

On the other hand, there is currently a multiply function in AffineTransform, and it does currently do the same thing as *=.  Another alternative is to restrict an immutable understanding of multiply() to the Javascript API.
Comment 42 Nikolas Zimmermann 2011-01-18 07:52:59 PST
(In reply to comment #38)
> (In reply to comment #36)
> > Almost - with this patch we have operator*, operator*= and multiply; however multiply does the same thing as *=.
> > 
> > I'm not sure that it makes sense for multiply (a normal instance method) to do the same thing as operator* - I think there's an expectation that instance methods operate directly on the instance.
> 
> The problem with that is CSSMatrix and SVGMatrix both have multiply() functions which are immutable. I would not mind having a function which does what operator*= does, but we should call it something else: applyMultiplication (ick), applyMultiply (bad grammar), applyMatrix (maybe)? I don't have any better ideas.

I think we should clarify what you meant with an immutable multiply() function.
I assume you mean that eg. SVGMatrix::multiply() returns a new SVGMatrix, which you can mutate freely, it just doesn't have any effect on the original SVGMatrix object, where you invoked the multiply() function from.

In JS words:
Let "var someMatrix" point to an existing SVGMatrix object, e.g. by declaring a <rect id="myRect" transform="matrix(....)".. in the markup and retrieving it from JS using "someMatrix = myRect.transform.baseVal.at(0));".

'someMatrix' is tied to the 'myRect' <rect> element.
someMatrix.a += 2 from JS takes immediate effect on 'myRect'.

Let "var otherMatrix" point to another existing SVGMatrix object (eg. representing a scale operation).
When using "resultMatrix = someMatrix.multiply(otherMatrix)" a new SVGMatrix object is created, not tied to any DOM element. That means you can still call "resultMatrix.a += 2" without any problem, but it takes no effect on any DOM element.

Is my interpretation of your 'immutable' definition, correct?

I'm asking because I think in C++ in WebCore "a.multiply(b)" should NOT return a new AffineTransform object, but rather mutate the underlying AffineTransform (this). I'd like a.multiply(b) to behave like a *= b, aka. a = a * b, _internally_.

The demand for the JS bindings to return 'new' SVGMatrix objects can easily be implemented in SVGMatrix, as SVGMatrix just inherits from AffineTransform, and thus can override any function it wants, especially provide an overloaded multiply() function, taking a SVGMatrix. That's exactly what we do now:

    SVGMatrix multiply(const SVGMatrix& other)
    {
        AffineTransform copy = *this;
        copy.multLeft(static_cast<const AffineTransform&>(other));
        return static_cast<SVGMatrix>(copy);
    }

(With Shanes patch that would just have to say "copy.multiply(other)", not multLeft, but that's another story)

--> We can choose freely how our internal usage of AffineTransform/TransformationMatrix should happen in C++, the bindings to JS can always implement their demand on top of that.

To summarize:
I'd like a.multiply(b) to behave like "a *= b" inside WebCore, for any outside usage through the JS bindings a.multiply(b) should behave like "a * b".

Do we agree on that?
Comment 43 Chris Marrin 2011-01-18 13:30:48 PST
(In reply to comment #42)
...
> The demand for the JS bindings to return 'new' SVGMatrix objects can easily be implemented in SVGMatrix, as SVGMatrix just inherits from AffineTransform, and thus can override any function it wants, especially provide an overloaded multiply() function, taking a SVGMatrix. That's exactly what we do now:
> 
>     SVGMatrix multiply(const SVGMatrix& other)
>     {
>         AffineTransform copy = *this;
>         copy.multLeft(static_cast<const AffineTransform&>(other));
>         return static_cast<SVGMatrix>(copy);
>     }
> 
> (With Shanes patch that would just have to say "copy.multiply(other)", not multLeft, but that's another story)
> 
> --> We can choose freely how our internal usage of AffineTransform/TransformationMatrix should happen in C++, the bindings to JS can always implement their demand on top of that.
> 
> To summarize:
> I'd like a.multiply(b) to behave like "a *= b" inside WebCore, for any outside usage through the JS bindings a.multiply(b) should behave like "a * b".
> 
> Do we agree on that?

I believe we are trying to avoid confusion. What looks better programmatically is very subjective and I don't think we should make this decision based on personal preference. There is a well known programming philosophy which states that a function returning an object should not also mutate that object. So if you have:

    Matrix multiply(const Matrix&) const; (1)

That function would not mutate 'this'. But:

    void multiply(const Matrix&); (2)

would.

The multiply operation exposed in SVGMatrix and CSSMatrix follows this convention using signature (1). So either way we go, we should be consistent with the above convention. My preference is that we follow signature (1) simply because it would reduce confusion with the related JavaScript calls. But I would be fine with (2) if it allows us to achieve consensus. But the current proposal both mutates and returns the object, which I am against.
Comment 44 Shane Stephens 2011-01-18 14:43:38 PST
The current proposal returns a reference to the current object, not a new object.  This is effectively proposal (2) with allowances made for chaining.

Thus, I take it we're all sufficiently in agreement for this patch to proceed?
Comment 45 Chris Marrin 2011-01-18 14:56:16 PST
(In reply to comment #44)
> The current proposal returns a reference to the current object, not a new object.  This is effectively proposal (2) with allowances made for chaining.
> 
> Thus, I take it we're all sufficiently in agreement for this patch to proceed?

 Since we're having difficulty with this, I think it would be best for now to remove any multiply() functions in either AffineTransform or TransformationMatrix. That avoids the multiply() issue and allows us to define it later when we tackle the bigger issue of making mutable matrix functions available to JavaScript.
Comment 46 Shane Stephens 2011-01-18 15:14:20 PST
As I've mentioned before, this patch deals with AffineTransform only.  TransformationMatrix work will take place in a separate bug.

It seems to me that we are all sufficiently in agreement as to how the multiply method works for it to remain.  We all agree that it should either return a new object or multiply in-place and there seems to be a majority opinion in favour of multiplication in-place.

I really don't care whether multiply returns a reference to an AffineTransform or not, however:
* returning a reference is not the same as returning a new object
* returning a reference does clearly indicate that the method is performing in-place modification
* returning a reference allows chaining of matrix modification calls
* there is a strong precedence within the class (scale, scaleNonUniform, rotate, rotateFromVector, translate, shear, flipX, flipY, skew, skewX, skewY) for calls that in-place modify and return a reference
* it seems bizarre that multiply should be treated differently to these methods, just because it also has operators

So overall, I'm in favour of submitting this patch as-is and getting on with fixing the myriad of other issues that have been identified.
Comment 47 Chris Marrin 2011-01-18 18:32:25 PST
Comment on attachment 78871 [details]
Patch

You win :-)

But seriously, I concur with your implementation. Now on to TransformationMatrix!
Comment 48 Shane Stephens 2011-01-18 19:28:45 PST
Great!

This needs to go on the commit queue, and once it's through there's 52551 (for translateRight) which is ready to go.  A TransformationMatrix patch will be ready soon.
Comment 49 Nikolas Zimmermann 2011-01-19 01:51:18 PST
(In reply to comment #46)
> As I've mentioned before, this patch deals with AffineTransform only.  TransformationMatrix work will take place in a separate bug.
> 
> It seems to me that we are all sufficiently in agreement as to how the multiply method works for it to remain.  We all agree that it should either return a new object or multiply in-place and there seems to be a majority opinion in favour of multiplication in-place.
> 
> I really don't care whether multiply returns a reference to an AffineTransform or not, however:
> * returning a reference is not the same as returning a new object
> * returning a reference does clearly indicate that the method is performing in-place modification
> * returning a reference allows chaining of matrix modification calls
> * there is a strong precedence within the class (scale, scaleNonUniform, rotate, rotateFromVector, translate, shear, flipX, flipY, skew, skewX, skewY) for calls that in-place modify and return a reference
> * it seems bizarre that multiply should be treated differently to these methods, just because it also has operators
> 
> So overall, I'm in favour of submitting this patch as-is and getting on with fixing the myriad of other issues that have been identified.

Completly fine with me. multiply shoul behave as the other methods, for now. We should first fix the other issues, align with TransformationMatrix, then we can think again about optimizing/changing the multiply concept to align better with the demands of the bindings.
Comment 50 WebKit Commit Bot 2011-01-19 03:49:48 PST
Comment on attachment 78871 [details]
Patch

Rejecting attachment 78871 [details] from commit-queue.

Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=eseidel-sf-cq', 'bu..." exit_code: 2

Last 500 characters of output:
ests/css ....
http/tests/eventsource .......
http/tests/eventsource/workers .
http/tests/globalhistory ....
http/tests/history .............................
http/tests/incremental ......
http/tests/inspector-enabled .
http/tests/inspector ......
http/tests/inspector/extensions-resources-redirect.html -> failed

Exiting early after 1 failures. 21476 tests run.
542.17s total testing time

21475 test cases (99%) succeeded
1 test case (<1%) had incorrect layout
11 test cases (<1%) had stderr output

Full output: http://queues.webkit.org/results/7602184
Comment 51 WebKit Commit Bot 2011-01-19 04:07:02 PST
The commit-queue encountered the following flaky tests while processing attachment 78871 [details]:

http/tests/inspector/extensions-resources-redirect.html bug 52709 (author: caseq@chromium.org)
The commit-queue is continuing to process your patch.
Comment 52 Eric Seidel 2011-01-19 10:55:46 PST
Comment on attachment 78871 [details]
Patch

Two instances of the queue grabbed your patch (due to a cq bug), and one of them failed out due to flaky tests, the other saw the test was flaky and didn't fail out, but then stopped because the first instance had already cq-'d the patch.

sorry for the confusion.
Comment 53 WebKit Commit Bot 2011-01-19 12:10:25 PST
Comment on attachment 78871 [details]
Patch

Clearing flags on attachment: 78871

Committed r76146: <http://trac.webkit.org/changeset/76146>
Comment 54 WebKit Commit Bot 2011-01-19 12:10:36 PST
All reviewed patches have been landed.  Closing bug.
Comment 55 Shane Stephens 2011-01-19 20:51:46 PST
fyi: there's now a patch to fix TransformationMatrix multiply operations in https://bugs.webkit.org/show_bug.cgi?id=52780.