etcd-io / etcd-io/etcd

pkg/adt: Int64Comparable.Compare overflows for extreme int64 values

Open Beginner friendly
#22,357 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
52.3k
Forks
10.5k
Avg merge
2d 21h
Merged PRs (30d)
43

Description

`pkg/adt.Int64Comparable.Compare` computes `cmp := v - vc` and takes the sign. The subtraction overflows for extreme values, breaking the trichotomy contract:

```go
Int64Comparable(math.MaxInt64).Compare(Int64Comparable(math.MinInt64)) // returns -1, expected 1
Int64Comparable(math.MaxInt64).Compare(Int64Comparable(-1)) // returns -1, expected 1
```

On top of that, `NewInt64Point(math.MaxInt64)` builds `[MaxInt64, MaxInt64+1)` where `a+1` wraps to `MinInt64`, producing an interval with `Begin > End` and violating the tree's `Begin <= End` invariant.

There are no in-tree production callers of the int64 interval constructors, but `pkg/adt` is an exported package used by downstream consumers, so the API should not return wrong orderings or invalid intervals for extreme input.

Proposed fix: compare `v` and `vc` directly without subtracting, and return a degenerate (empty) `[a, a)` interval for `NewInt64Point(math.MaxInt64)`, preserving the invariant. A regression test will assert the comparator trichotomy at extremes and the point invariant.

Contributor guide

Open the contributing guide

Research direction

Start in pkg/adt with Int64Comparable.Compare and NewInt64Point, then locate the related interval-tree tests. Run the existing pkg/adt tests before adding regression coverage for extreme int64 comparisons and the MaxInt64 point invariant. Done means comparisons preserve trichotomy and the point interval always satisfies Begin <= End.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
backend
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
78/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.