Bug 16062 - SVGMatrix multiply method is wrong way around
: SVGMatrix multiply method is wrong way around
Status: RESOLVED FIXED
Product: WebKit
Classification: Unclassified
Component: SVG
: 523.x (Safari 3)
: Macintosh Mac OS X 10.4
: P2 Normal
Assigned To: Jeff Schiller
javascript:alert(function(){var g = d...
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2007-11-20 00:30 PST by David Jones
Modified: 2009-11-05 07:28 PST (History)
10 users (show)

See Also:


Attachments
Test case exhibiting the problem (880 bytes, image/svg+xml)
2009-11-03 21:15 PST, Jeff Schiller
no flags Details
Patch adds a custom method to JSVGMatrix to ensure proper matrix multiplication (1.60 KB, patch)
2009-11-04 10:23 PST, Jeff Schiller
eric: review-
Details | Formatted Diff | Diff
Updated patch: spaces instead of tabs, added test and changelogs (4.85 KB, patch)
2009-11-04 11:59 PST, Jeff Schiller
no flags Details | Formatted Diff | Diff
Updated patch: added check for enough arguments. Also added copyright as this change is now over 10 lines. (5.23 KB, patch)
2009-11-04 12:16 PST, Jeff Schiller
simon.fraser: review+
Details | Formatted Diff | Diff
Reworked CSSMatrix test and added further tests for all other SVGMatrix functionality. (14.94 KB, patch)
2009-11-04 15:06 PST, Jeff Schiller
simon.fraser: review+
Details | Formatted Diff | Diff
Remove conflict markers from changelog in patch. (14.91 KB, patch)
2009-11-04 18:49 PST, Jeff Schiller
eric: review-
commit-queue: commit‑queue-
Details | Formatted Diff | Diff
Updated correct patch via svn-create-patch with apologies :) (14.46 KB, patch)
2009-11-05 04:34 PST, Jeff Schiller
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description David Jones 2007-11-20 00:30:47 PST
(In JavaScript) If A and B are each an SVGMatrix then A.multiply(B) multiplies them.  According to my best reading of the spec the product should be AB.  Safari computes BA. Firefox computes AB.  Opera (as far as I can tell) computes AB.

URL is a bookmarklet that alerts the results of multiplying matrix(0 1 1 0 0 0) by translate(1 0).  It should produce the 6 numbers: 0,1,1,0,0,1 (for example, on Firefox).  Safari produces: 0,1,1,0,1,0.

There's more discussion at a blog article I wrote, http://drj11.wordpress.com/2007/11/19/the-trouble-with-matrix-multiplication/ , but you probably don't need that.

If you think WebKit is right and Gecko is wrong, you can duke it out on the Moz bug I made earlier: https://bugzilla.mozilla.org/show_bug.cgi?id=404221
Comment 1 Eric Seidel 2007-11-20 03:16:34 PST
Oops.  This should be easy to fix. :)
Comment 2 Eric Seidel 2007-11-20 03:17:28 PST
This probably regressed during the initial import of KDOM and conversion of SVGMatrix to use AffineTransform.  AffineTransform does matrix math inverted from how SVGMatrix used to.  We probably never swapped this multiply correctly.  I'll investigate.
Comment 3 Eric Seidel 2007-11-20 03:54:49 PST
Ok, trying this code with AffineTransform:

    {
        AffineTransform L(0,1,1,0,0,0);
        AffineTransform R(0,0,0,0,1,0);
        AffineTransform LR = L*R;
        AffineTransform RL = R*L;
        printf("LR: %f,%f,%f,%f,%f,%f\n", LR.a(), LR.b(), LR.c(), LR.d(), LR.e(), LR.f());
        printf("RL: %f,%f,%f,%f,%f,%f\n", RL.a(), RL.b(), RL.c(), RL.d(), RL.e(), RL.f());
    }

Produced:

LR: 0.000000,0.000000,0.000000,0.000000,1.000000,0.000000
RL: 0.000000,0.000000,0.000000,0.000000,0.000000,1.000000

Which is reversed from what is expected, according to 
http://drj11.wordpress.com/2007/11/19/the-trouble-with-matrix-multiplication/

Interesting to note, the matrix layout shown:
http://www.w3.org/TR/SVG/coords.html#TransformMatrixDefined
is different from the one used by CG:
http://developer.apple.com/documentation/GraphicsImaging/Reference/CGAffineTransform/Reference/reference.html#//apple_ref/c/func/CGAffineTransformMake
Comment 4 Eric Seidel 2007-11-20 04:01:20 PST
If I did my math right, the differing matrix layouts could cause this issue:

When laid out the SVG-way my hand-calculated result of LR = 0,0,0,0,0,1, when laid out the CG way: 0,0,0,0,1,0.
Comment 5 David Jones 2007-11-20 04:51:11 PST
(In reply to comment #3)
> 
> Interesting to note, the matrix layout shown:
> http://www.w3.org/TR/SVG/coords.html#TransformMatrixDefined
> is different from the one used by CG:
> http://developer.apple.com/documentation/GraphicsImaging/Reference/CGAffineTransform/Reference/reference.html#//apple_ref/c/func/CGAffineTransformMake
> 

Oh-oh.  SVG is using the column vector convention where a matrix M operates on a column vector V by the multiplication MV.  Note V is a 3 row by 1 column vector so MV is too.  Looks like CG is using the row-vector convention so a matrix M operates on a vector V by VM; this time V is a 1 row by 3 column vector so VM is too.  Oh, that couldn't possibly be confusing could it?
Comment 6 mitz@webkit.org 2007-11-22 17:26:15 PST
I think it's just that AffineTransform has got it wrong. I'm seeing the same problem with CSS transforms.
Comment 7 David Jones 2007-11-23 00:33:02 PST
(In reply to comment #6)
> I think it's just that AffineTransform has got it wrong. I'm seeing the same
> problem with CSS transforms.

I think it's just that SVG/CSS use column vectors, and CG/AffineTransform uses row vectors.

As far as I can tell AffineTransform has it right.

As you know matrices operate on vectors and can be considered as linear transformations in a vector space.  But it matters whether you talk about row vectors or column vectors.

A matrix M operates on a column vector v by acting on the left, we form the product Mv.  A matrix operates on a row vector by acting on the right: vM.

Essentially CG operates in a "transpose world" compared to SVG.  So instead of doing the operating Mv, in CG we do (v^T)(M^T) where (@^T) denote transpose.  That's why Eric notes in comment 3 that CG and SVG use different matrix layouts (they are transposes of each).

Essentially when SVG asks for a vector transformation Mv, what you actually perform in CG is ((v^T)(M^T))^T.  The transposition comes "for free" as you write the entries into the vector and matrix and read the result out.

This is no trouble until you need to multiply matrices.  If SVG asks you to compute ABv then in transpose world you need to compute (v^T)(B^T)(A^T) because (AB)^T = (B^T)(A^T).
Comment 8 mitz@webkit.org 2007-11-23 00:58:27 PST
(In reply to comment #7) 
> As far as I can tell AffineTransform has it right.

Yeah, I agree now. Callers need to change. I am going to change CSS transforms.
Comment 9 Gustavo Noronha (kov) 2009-03-19 10:04:50 PDT
Removing cairo keyword, as this doesn't seem to be cairo specific.
Comment 10 Jeff Schiller 2009-11-03 21:15:34 PST
Created attachment 42446 [details]
Test case exhibiting the problem

WebKit browsers get the multiplication incorrect (m.e = 200!) while all other browsers pass
Comment 11 Jeff Schiller 2009-11-03 21:20:39 PST
Did this implementation change since Comment #7?  I don't find it to match what the test case exhibits.  In the test I take two matrices:

1  0 100
0  1   0
0  0   1

and

2  0  0
0  1  0
0  0  1

Multiplying these together gives:

2  0 100
0  1   0
0  0   1

But WebKit gives:

2  0 200
0  1   0
0  0   1

And I can't figure out any matrix operation that would generate that result.
Comment 12 Brendan Kenny 2009-11-03 22:20:15 PST
That's the expected behavior from the "multiply method is wrong way around." Your first matrix (A) is a translation by 100 in x. The second (B) is a scale by a factor of 2 in x. In this case, B is applied in the global coordinates, so a space already translated by 100 in x gets scaled, translating to 200.

You are trying to multiply on the right (A*B), but since WebKit stores matrices as the transpose of what you have written there, a multiply of a transpose by a transpose on the right (A^T*B^T) is equivalent to a multiply on the left of the matrices you have written there (B*A).
Comment 13 Jeff Schiller 2009-11-03 22:27:53 PST
Yep - got it now, thanks.
Comment 14 Simon Fraser (smfr) 2009-11-04 07:40:52 PST
See also bug 23243.
Comment 15 Jeff Schiller 2009-11-04 10:23:42 PST
Created attachment 42492 [details]
Patch adds a custom method to JSVGMatrix to ensure proper matrix multiplication
Comment 16 Eric Seidel 2009-11-04 10:26:49 PST
Comment on attachment 42492 [details]
Patch adds a custom method to JSVGMatrix to ensure proper matrix multiplication

Tabs in the file.  No ChangeLog.  I'm not sure this is the right place to fix this.
Comment 17 Simon Fraser (smfr) 2009-11-04 10:54:30 PST
Jeff and I talked this over, and we think this is the right approach. But I'm not sure if JSSVGMatrix::multiply() needs to check the number of args before getting args.at(0). JSSVGMatrix::rotateFromVector() may also be bad in this regard.

The patch also needs a testcase.
Comment 18 Brendan Kenny 2009-11-04 11:38:37 PST
The patch should make SVGMatrix functionally equivalent to the transpose of its actual representation, so this does seem like the best place to make the change.

Any thoughts on if a similar change should be applied to WebKitCSSMatrix? The draft spec is less explicit than SVG's, but the implication seems to be that it should follow SVGMatrix in convention.
Comment 19 Jeff Schiller 2009-11-04 11:59:15 PST
Created attachment 42505 [details]
Updated patch: spaces instead of tabs, added test and changelogs
Comment 20 Jeff Schiller 2009-11-04 12:01:50 PST
@Brendan: no idea about CSSMatrix, sorry.

@Simon: For your arglist checking question, I found JavaScriptCore/runtime/ArgList.h which has ArgList::at() defined:

        JSValue at(size_t idx) const
        {
            if (idx < m_argCount)
                return m_args[idx];
            return jsUndefined();
        }

This means that if there are no arguments, an at(0) will return jsUndefined() - which should fail this if and return a Type Error:

    if (!args.at(0).inherits(&JSSVGMatrix::s_info))

I checked DOM2 and DOM3 and there is no standard exception as far as I can tell for 'not enough arguments'.  My own belief is that a Type Error is just fine, so that's what the patch has.

Mozilla throws a NS_ERROR_XPC_NOT_ENOUGH_ARGS exception.  Does WebKit have something similar?  If so, I can check args.size() first and throw that if you prefer.

I cannot comment on rotateFromVector() and would suggest a separate patch for it.
Comment 21 Jeff Schiller 2009-11-04 12:08:41 PST
Hm, I found this in about 20 places in WebKit:

    if (args.size() < 1)
        return throwError(exec, SyntaxError, "Not enough arguments");

Do we prefer that?
Comment 22 Jeff Schiller 2009-11-04 12:16:14 PST
Created attachment 42507 [details]
Updated patch: added check for enough arguments.  Also added copyright as this change is now over 10 lines.
Comment 23 Jeff Schiller 2009-11-04 12:16:49 PST
Since I prefer that (from a author/debugging point of view), I went ahead and made the syntax error check in multiply().
Comment 24 Simon Fraser (smfr) 2009-11-04 13:57:45 PST
Comment on attachment 42507 [details]
Updated patch: added check for enough arguments.  Also added copyright as this change is now over 10 lines.

I think this is good, but you might want to consider adding the test to SVGMatrix-interface.svg rather than creating a new test. Ideally SVGMatrix-interface.svg would be a much more comprehensive test of the SVGMatrix interface. See LayoutTests/transforms/cssmatrix-2d-interface.xhtml which could probably be converted to SVGMatrix easily.
Comment 25 Jeff Schiller 2009-11-04 15:06:48 PST
Created attachment 42527 [details]
Reworked CSSMatrix test and added further tests for all other SVGMatrix functionality.
Comment 26 Jeff Schiller 2009-11-04 15:16:42 PST
If this patch is accepted, we can then remove the following test files as they are no longer needed:

LayoutTests/svg/custom/SVGMatrix-interface.svg 
LayoutTests/platform/mac/svg/custom/SVGMatrix-interface-*

(there is no reason to test this in platform-specific code, this is just a DOM object that has no visual representation)
Comment 27 Simon Fraser (smfr) 2009-11-04 17:12:48 PST
Comment on attachment 42527 [details]
Reworked CSSMatrix test and added further tests for all other SVGMatrix functionality.

> Index: WebCore/ChangeLog
> ===================================================================

> +>>>>>>> .r50529

You have a conflict marker in the patch.

> Index: LayoutTests/ChangeLog
> ===================================================================

> +>>>>>>> .r50529

Ditto.

r=me with those fixed. You should attach a clean patch and we can put it in the commit-queue.
Comment 28 Nikolas Zimmermann 2009-11-04 17:54:07 PST
Thanks Jeff for fixing this bug! Patch looks good to me as well.
Comment 29 Jeff Schiller 2009-11-04 18:49:27 PST
Created attachment 42535 [details]
Remove conflict markers from changelog in patch.
Comment 30 Eric Seidel 2009-11-04 19:55:18 PST
Comment on attachment 42535 [details]
Remove conflict markers from changelog in patch.

Patches have to be marked r+ as well as cq+.  Patches marked with just a cq+ get ignored by the commit-queue.  I guess I could teach it to reject patches with just a cq+, but that seems draconian.  The issue is that a committer can cq+ a patch, but it takes a reviewer's OK as well for something to get committed.
Comment 31 Eric Seidel 2009-11-04 19:55:53 PST
Thanks again for the patch Jeff.  And thanks for the quick review Simon!
Comment 32 Eric Seidel 2009-11-04 19:57:33 PST
Comment on attachment 42535 [details]
Remove conflict markers from changelog in patch.

It seems an even slicker solution would have been to have a custom JSSVGStaticPODTypeWrapper<TransformationMatrix> subclass called SVGMatrix which defined a special mutiply() function.  As is, this will require v8 to fix it the exact same way.  But this is OK for now.
Comment 33 WebKit Commit Bot 2009-11-04 19:58:03 PST
Comment on attachment 42535 [details]
Remove conflict markers from changelog in patch.

Rejecting patch 42535 from commit-queue.

Failed to run "['/Users/eseidel/Projects/CommitQueue/WebKitTools/Scripts/svn-apply', '--reviewer', 'Eric Seidel', '--force']" exit_code: 2
patching file WebCore/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patch: **** malformed patch at line 28:  

patching file WebCore/bindings/js/JSSVGMatrixCustom.cpp
patching file WebCore/svg/SVGMatrix.idl
patching file LayoutTests/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patch: **** malformed patch at line 25:  

patching file LayoutTests/svg/dom/SVGMatrix-interface-expected.txt
patching file LayoutTests/svg/dom/SVGMatrix-interface.xhtml
Comment 34 Eric Seidel 2009-11-04 20:02:57 PST
Ha!  You edited the patch file directly it looks like.  Unless you know how to speak patch, that will just get you in trouble. :)

You can read the documentation on unified diffs here: http://en.wikipedia.org/wiki/Diff#Unified_format  But the better thing to do is to just always re-make the patch instead of modifying the patch file.
Comment 35 Eric Seidel 2009-11-04 20:03:41 PST
Comment on attachment 42535 [details]
Remove conflict markers from changelog in patch.

This can't be landed as is with the broken patch file, so marking r-.
Comment 36 Jeff Schiller 2009-11-05 04:34:33 PST
Created attachment 42556 [details]
Updated correct patch via svn-create-patch with apologies :)
Comment 37 Jeff Schiller 2009-11-05 04:37:03 PST
Sorry about the malformed patch, Eric.

About Comment #32, I didn't realize (but I should have) that this would require separate fixing from V8 side.  Looks like it's time for me to check out chromium :)
Comment 38 WebKit Commit Bot 2009-11-05 07:04:54 PST
Comment on attachment 42556 [details]
Updated correct patch via svn-create-patch with apologies :)

Rejecting patch 42556 from commit-queue.

codedread@gmail.com does not have committer permissions according to http://trac.webkit.org/browser/trunk/WebKitTools/Scripts/modules/committers.py.
Comment 39 Jeff Schiller 2009-11-05 07:12:18 PST
Comment on attachment 42556 [details]
Updated correct patch via svn-create-patch with apologies :)

Going to try commit-queue? again
Comment 40 WebKit Commit Bot 2009-11-05 07:28:46 PST
Comment on attachment 42556 [details]
Updated correct patch via svn-create-patch with apologies :)

Clearing flags on attachment: 42556

Committed r50561: <http://trac.webkit.org/changeset/50561>
Comment 41 WebKit Commit Bot 2009-11-05 07:28:52 PST
All reviewed patches have been landed.  Closing bug.