simpleqt opened a new pull request, #348:
URL: https://github.com/apache/commons-math/pull/348
`MathArrays.distance1(int[], int[])` and `MathArrays.distanceInf(int[],
int[])` computed the offset of each pair as `JdkMath.abs(p1[i] - p2[i])` in
`int`.
The difference of two `int` values does not always fit in an `int`, and
`Math.abs` does not make it fit:
* `Integer.MAX_VALUE - (-1)` overflows to `Integer.MIN_VALUE`, and
`Math.abs(Integer.MIN_VALUE)` is `Integer.MIN_VALUE` itself, so `distance1`
returns a **negative** distance;
* `distanceInf` takes `max(0, that)` and therefore returns **0**, i.e. it
reports that two points far apart are identical.
## Reproducer
```java
int[] a = {Integer.MAX_VALUE};
int[] b = {-1};
MathArrays.distance1(a, b); // -2147483648 (expected 2147483648)
MathArrays.distanceInf(a, b); // 0 (expected 2147483648)
```
`distance1` returns a negative value whenever an offset exceeds
`Integer.MAX_VALUE`. Other affected inputs include `{Integer.MIN_VALUE}` vs
`{0}` (returns `-2147483648`) and `{Integer.MAX_VALUE}` vs
`{Integer.MIN_VALUE}` (returns `1`). Oversized results can also accumulate from
individually representable offsets, e.g. `{Integer.MAX_VALUE, 0}` vs `{0,
Integer.MAX_VALUE}` sums to `4294967294`.
## Fix
Widen the subtraction to `long` before taking the absolute value, so the
offset is always exact, and saturate the accumulated result at
`Integer.MAX_VALUE`, the largest representable distance. `distance1` now
reports `Integer.MAX_VALUE` rather than a negative "distance", and
`distanceInf` reports `Integer.MAX_VALUE` rather than `0`. Distances that fit
in an `int` are unchanged.
This also makes the result monotonic in the offsets and symmetric in the
arguments, which the previous result was not: before the fix
`distance1({Integer.MAX_VALUE}, {-1})` was negative while `distance1({1, 1},
{0, 0})` was `2`.
The `double[]` overloads are not affected: `JdkMath.abs` on a `double`
difference cannot overflow, and `MathArraysTest.testL1DistanceDouble`,
`testL2DistanceDouble` and `testLInfDistanceDouble` are unchanged.
## Tests
Adds `testL1DistanceIntOverflow` and `testLInfDistanceIntOverflow` to
`MathArraysTest`, covering the overflowing inputs, the saturated multi-element
accumulation, the exact `Integer.MAX_VALUE` boundary, and the fitting values
that must not change.
Verified against the source tree at
`e253f396ba47edf008f60c903c4623496c7eef49`:
* **Before** the fix, the two new tests fail:
* `testL1DistanceIntOverflow:197 distance1 of [-2147483648, 0]
expected:<2147483647> but was:<-2147483648>`
* `testLInfDistanceIntOverflow:227 distanceInf of [-2147483648, 0]
expected:<2147483647> but was:<0>`
* **After** the fix, the whole `commons-math-legacy-core` module is green:
`Tests run: 295, Failures: 0, Errors: 0, Skipped: 0` (47 in `MathArraysTest`).
## Notes
* Both methods are reached through `ManhattanDistance` and
`ChebyshevDistance` only via their `double[]` overloads; inside this repository
the `int[]` overloads are exercised by tests alone. I am fixing them because
the overflow is silent and returns a *plausible-looking but wrong* number, not
because there is a known in-tree caller.
* This changes the result for inputs whose distance is not representable as
an `int`, from an overflowed value to a saturated `Integer.MAX_VALUE`. That is
a behaviour change for those inputs, so I have documented it in the `@return`
tags. I considered widening the return type but the two methods are part of the
API and the `double[]` overloads already cover distances beyond `int` range.
* There is no MATH Jira ticket: I do not have an Apache Jira account, and I
did not want to invent a key. `CONTRIBUTING.md` asks for one, so please tell me
the key to use and I will rename the branch and amend the commit.
* AI assistance disclosure: this change was produced with AI assistance,
hence the `Assisted-By` trailer. I ran the tests above myself and have not run
the full multi-module `mvn clean verify`. If you would prefer a different
disclosure or none, say so and I will amend.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
