Page MenuHomePhabricator

[ConstantRange] Make exhaustive testing more principled (NFC)
ClosedPublic

Authored by nikic on Sep 26 2020, 6:36 AM.

Details

Summary

The current infrastructure for exhaustive ConstantRange testing is somewhat confusing in what exactly it tests (D88283) and currently cannot even be used for operations that produce smallest-size results, rather than signed/unsigned approximations.

This patch tries to make the testing more principled by collecting the exact set of results of an operation into a bit set and then comparing it against the range approximation by:

  • Checking conservative correctness: All elements in the set must be in the range.
  • Checking optimality under a given preference function: None of the (slack-free) ranges that can be constructed from the set are preferred over the computed range.

Implemented preference functions are:

  • PreferSmallest: Smallest range regardless of signed/unsigned wrapping behavior. Probably what we would call "optimal" without further qualification.
  • PreferSmallestUnsigned/Signed: Smallest range that has no unsigned/signed wrapping. We use this if our calculation is precise only up to signed/unsigned envelope.
  • PreferSmallestNonFullUnsigned/Signed: Smallest range that has no unsigned/signed wrapping -- but preferring a smaller wrapping range over a (non-wrapping) full range. We use this if we have a fully precise calculation but apply a sign preference to the result (union/intersection). Even with a sign preference, returning a wrapping range is still "strictly better" than returning a full one.

Diff Detail

Event Timeline

nikic created this revision.Sep 26 2020, 6:36 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 26 2020, 6:36 AM
nikic requested review of this revision.Sep 26 2020, 6:36 AM
nikic updated this revision to Diff 294504.Sep 26 2020, 8:08 AM
nikic edited the summary of this revision. (Show Details)

Use preference function instead of filter function, making the testing approach more broadly applicable.

nikic edited the summary of this revision. (Show Details)Sep 26 2020, 8:18 AM
nikic updated this revision to Diff 294512.Sep 26 2020, 11:24 AM
nikic edited the summary of this revision. (Show Details)

Simplify implementation. There's no need to collect all the best ranges explicitly.

nikic added a subscriber: lebedev.ri.

@lebedev.ri Any thoughts on this testing approach relative to what we do currently and your proposal at D88283? I thought this was quite nice in how it brings everything under one umbrella, including cases we could not test before (add, sub) or only with a lot of effort (testBinarySetOperationExhaustive), but I'm not sure it addresses your concerns.

nikic added a comment.Jan 24 2021, 1:54 AM

Ping :) I'd also be happy with an "I don't really care", as I'm not really looking for technical review for testing changes. Just want to make sure I'm not stepping on any toes, as you also did work in this area.

This revision was not accepted when it landed; it landed in state Needs Review.Sat, Feb 20, 3:39 AM
This revision was automatically updated to reflect the committed changes.