-
Notifications
You must be signed in to change notification settings - Fork 142
[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
Comments
Yeah by corresponding, I actually meant |
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. |
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 :) |
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. ^_^ |
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. |
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.) |
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 isCSSMathSum(1px, 2em, 1px)
. Pretty sure you can get those viaadd()
.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.
The text was updated successfully, but these errors were encountered: