Skip to content

[css-typed-om-1] "equal numeric values" algorithm is possibly problematic #681

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
bzbarsky opened this issue Feb 16, 2018 · 6 comments
Closed

Comments

@bzbarsky
Copy link

In https://drafts.css-houdini.org/css-typed-om-1/#equal-numeric-value say value1 and value2 are both CSSMathSums. Specifically, say value1 is CSSMathSum(2em, 1px, 2em) and value2 is CSSMathSum(1px, 2em, 1px). Pretty sure you can get those via add().

AS the algorithm is currently written in step 3 the "values" slots have the same sizes, so step 3 substep 1 does not return.

In step 3 substep 2, each item in value1 does in fact have a corresponding equal numeric item value in value2, so we do not return. Depending on how one defines "corresponding", but the usual meaning is basically "a function from the items in value1 to the items in value 2".

In step 3 substep 3 true is returned. But these two values should not be considered numerically equal.

The simplest way to fix is probably to say that we should return true if there is a one-to-one correspondence between the items of value1 and the items of value 2 such that corresponding items are equal numeric value. That fixes the problem of the function not being bijective.

@darrnshn
Copy link
Collaborator

Yeah by corresponding, I actually meant list1[i] == list2[i] for all i (there's probably a better word for this). Currently in Blink's implementation, order matters (so CSSMathSum(1px, 2px) != CSSMathSum(2px, 1px)). We'll probably have to decide on #682 first.

@bzbarsky
Copy link
Author

bzbarsky commented Feb 16, 2018

Ah. I definitely read this algorithm as "order does not matter". So no matter what we need to fix the wording to really say what it means.

Speccing the "order matters" version is simplest if done explictly: walk i from 0 to n and compare the things at index i.

@darrnshn
Copy link
Collaborator

The original algorithm was written by @tabatkins and I just rephrased it, so I might've accidentally changed the algorithm semantics :P I'll wait till Tab clarifies whether order matters and I'll change the wording to be more precise :)

@tabatkins
Copy link
Member

I had also assumed that order doesn't matter when I wrote/editted it, so if that's the assumption we're making it definitely needs to be spelled out more clearly. ^_^

@bzbarsky
Copy link
Author

One thing, in case we care. If order matters, equality can be determined in O(N) time in length of the lists. If order does not matter, it's O(N^2). I don't have a good feel for what sort of N we can expect here, especially as people use these APIs instead of hand-authoring their calc() expressions.

@tabatkins
Copy link
Member

Well, clever impls could get it down to N*log(N). ^_^ But yeah, given that we're deliberating giving up on many other possible simplifications that we could apply to get a wider notion of equality, I think it's fine to be order-dependent, and the perf bonus is nice too. (In earlier discussions we do explicitly acknowledge that a much looser notion of equality would probably be useful to have as well, in the future.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants