Skip to content

Fix LongIndexed.compareTo overflow for large index deltas #936

Open

Description

@gciatto

Context

LongIndexed<T> (:utils, utils/src/commonMain/kotlin/it/unibo/tuprolog/utils/LongIndexed.kt) is a Comparable value ordered by its Long index. The interface declares a correct default:

override fun compareTo(other: LongIndexed<T>): Int = index.compareTo(other.index)

but the only implementation, LongIndexedImpl (utils/src/commonMain/kotlin/it/unibo/tuprolog/utils/impl/LongIndexedImpl.kt), overrides it with a subtraction-based comparison:

override fun compareTo(other: LongIndexed<T>): Int = (index - other.index).toInt()

Problem

(a - b).toInt() truncates the Long difference to its low 32 bits, so the sign of the result is wrong whenever |a - b| >= 2^31 (and the subtraction itself can overflow for operands near Long.MIN_VALUE/Long.MAX_VALUE). Example: index = 2^32, other.index = 0 gives (2^32).toInt() == 0, i.e. the two values compare as equal; index = 2^31 vs 0 compares as less than.

Expected: LongIndexed.of(a, x).compareTo(LongIndexed.of(b, y)) has the same sign as a.compareTo(b) for all Long values.

Affected code

  • :utils — LongIndexedImpl.compareTo (used by Sequence.longIndexed() in IterUtils.kt).
  • :theory — IndexedClause (theory/src/commonMain/kotlin/it/unibo/tuprolog/collections/rete/custom/clause/IndexedClause.kt) extends LongIndexed<Clause> and wraps LongIndexed.of(...), so the RETE-based clause ordering (e.g. mergeSequences(..., SituatedIndexedClause::compareTo) in rete/custom/Utils.kt) inherits the bug for theories whose clause indices diverge by more than Int.MAX_VALUE.

Possible approach

Delete the compareTo override from LongIndexedImpl so the correct interface default (index.compareTo(other.index)) applies, and add a regression test in :utils comparing indices far apart (e.g. 0 vs 1L shl 32, Long.MIN_VALUE vs Long.MAX_VALUE).

Original description

LongIndexed.compareTo can overflow and misorder values when index deltas are large. Spotted during the documentation pass; not fixed in commit 5dfb787.

Activity

  1. gciatto commented on Oct 4, 2026

    @gciatto
    ContributorAuthor

    Still applies on current master: LongIndexedImpl.compareTo (utils/src/commonMain/kotlin/it/unibo/tuprolog/utils/impl/LongIndexedImpl.kt) still uses (index - other.index).toInt(), overriding the correct default in LongIndexed. Expanded the description with details and a suggested one-line fix (drop the override), and labelled it.

    Triage performed by Claude Code on behalf of @gciatto.

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions