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
: WebKit
Platform
: 528+ (Nightly build)
: All All
: P2 Normal
Assigned To:
:
:
: 48026 48215
: 52551
  Show dependency treegraph
 
Reported: 2010-10-20 17:02 PST by
Modified: 2011-02-15 18:04 PST (History)


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


Note

You need to log in before you can comment on or make changes to this bug.


Description From 2010-10-20 17:02:07 PST
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 From 2010-10-26 16:00:27 PST -------
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 From 2010-10-26 23:10:41 PST -------
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 From 2010-10-26 23:23:49 PST -------
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 From 2010-10-27 01:07:48 PST -------
Sounds good!
------- Comment #5 From 2010-12-14 15:06:32 PST -------
Created an attachment (id=76578) [details]
Patch
------- Comment #6 From 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 From 2010-12-15 09:18:16 PST -------
(From update of attachment 76578 [details])
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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 2011-01-02 11:23:59 PST -------
(From update of attachment 76578 [details])
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 From 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 From 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 From 2011-01-03 13:35:48 PST -------
I can't assign this bug to myself :(
------- Comment #20 From 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 From 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 From 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 From 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 From 2011-01-10 22:25:12 PST -------
Created an attachment (id=78494) [details]
Patch
------- Comment #25 From 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 From 2011-01-10 22:31:24 PST -------
Created an attachment (id=78495) [details]
Patch
------- Comment #27 From 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 From 2011-01-13 02:49:48 PST -------
(From update of attachment 78495 [details])
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 From 2011-01-13 16:17:27 PST -------
Created an attachment (id=78871) [details]
Patch
------- Comment #30 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 2011-01-18 18:32:25 PST -------
(From update of attachment 78871 [details])
You win :-)

But seriously, I concur with your implementation. Now on to TransformationMatrix!
------- Comment #48 From 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 From 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 From 2011-01-19 03:49:48 PST -------
(From update of attachment 78871 [details])
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 From 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 From 2011-01-19 10:55:46 PST -------
(From update of attachment 78871 [details])
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 From 2011-01-19 12:10:25 PST -------
(From update of attachment 78871 [details])
Clearing flags on attachment: 78871

Committed r76146: <http://trac.webkit.org/changeset/76146>
------- Comment #54 From 2011-01-19 12:10:36 PST -------
All reviewed patches have been landed.  Closing bug.
------- Comment #55 From 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.