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

[bzbarsky]

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]

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]

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]

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]

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]

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]

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.)