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


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-
Review Patch | 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 Review Patch | 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+
Review Patch | 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+
Review Patch | Details | Formatted Diff | Diff
Remove conflict markers from changelog in patch. (14.91 KB, patch)
2009-11-04 18:49 PST, Jeff Schiller
commit-queue: commit‑queue-
eric: review-
Review Patch | 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 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 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 From 2007-11-20 03:16:34 PST -------
Oops.  This should be easy to fix. :)
------- Comment #2 From 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 From 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 From 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 From 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 From 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 From 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 From 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 From 2009-03-19 10:04:50 PST -------
Removing cairo keyword, as this doesn't seem to be cairo specific.
------- Comment #10 From 2009-11-03 21:15:34 PST -------
Created an attachment (id=42446) [details]
Test case exhibiting the problem

WebKit browsers get the multiplication incorrect (m.e = 200!) while all other browsers pass
------- Comment #11 From 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 From 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 From 2009-11-03 22:27:53 PST -------
Yep - got it now, thanks.
------- Comment #14 From 2009-11-04 07:40:52 PST -------
See also bug 23243.
------- Comment #15 From 2009-11-04 10:23:42 PST -------
Created an attachment (id=42492) [details]
Patch adds a custom method to JSVGMatrix to ensure proper matrix multiplication
------- Comment #16 From 2009-11-04 10:26:49 PST -------
(From update of attachment 42492 [details])
Tabs in the file.  No ChangeLog.  I'm not sure this is the right place to fix this.
------- Comment #17 From 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 From 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 From 2009-11-04 11:59:15 PST -------
Created an attachment (id=42505) [details]
Updated patch: spaces instead of tabs, added test and changelogs
------- Comment #20 From 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 From 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 From 2009-11-04 12:16:14 PST -------
Created an attachment (id=42507) [details]
Updated patch: added check for enough arguments.  Also added copyright as this change is now over 10 lines.
------- Comment #23 From 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 From 2009-11-04 13:57:45 PST -------
(From update of attachment 42507 [details])
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 From 2009-11-04 15:06:48 PST -------
Created an attachment (id=42527) [details]
Reworked CSSMatrix test and added further tests for all other SVGMatrix functionality.
------- Comment #26 From 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 From 2009-11-04 17:12:48 PST -------
(From update of attachment 42527 [details])
> 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 From 2009-11-04 17:54:07 PST -------
Thanks Jeff for fixing this bug! Patch looks good to me as well.
------- Comment #29 From 2009-11-04 18:49:27 PST -------
Created an attachment (id=42535) [details]
Remove conflict markers from changelog in patch.
------- Comment #30 From 2009-11-04 19:55:18 PST -------
(From update of attachment 42535 [details])
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 From 2009-11-04 19:55:53 PST -------
Thanks again for the patch Jeff.  And thanks for the quick review Simon!
------- Comment #32 From 2009-11-04 19:57:33 PST -------
(From update of attachment 42535 [details])
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 From 2009-11-04 19:58:03 PST -------
(From update of attachment 42535 [details])
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 From 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 From 2009-11-04 20:03:41 PST -------
(From update of attachment 42535 [details])
This can't be landed as is with the broken patch file, so marking r-.
------- Comment #36 From 2009-11-05 04:34:33 PST -------
Created an attachment (id=42556) [details]
Updated correct patch via svn-create-patch with apologies :)
------- Comment #37 From 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 From 2009-11-05 07:04:54 PST -------
(From update of attachment 42556 [details])
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 From 2009-11-05 07:12:18 PST -------
(From update of attachment 42556 [details])
Going to try commit-queue? again
------- Comment #40 From 2009-11-05 07:28:46 PST -------
(From update of attachment 42556 [details])
Clearing flags on attachment: 42556

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