IEEE NaN makes std/algorithm.nextPermutation infinite loop

[c-blake]

Description

import std/[math, algorithm, formatFloat]
let x  = sqrt(-1.0)               #NOTE, Re: IEEE: x != x
var xs = [1.0, x, x]
xs.sort; echo xs                  # works as if nan<1, but
while xs.nextPermutation: echo xs #..this never terminates
# Also, `nextPermutation` doc should note that initial
# `sort` order must be ASCENDING to get all perms.

Nim Version

Nim Compiler Version 2.1.1 [Linux: amd64]
Compiled at 2024-04-22
Copyright (c) 2006-2024 by Andreas Rumpf

active boot switches: -d:release -d:danger -d:nimUseLinenoise

7e3bac9 but I really doubt any of this matters..

Current Output

[nan, nan, 1.0]
[nan, 1.0, nan]
[nan, nan, 1.0]
...repeating forever

The need to repeat is obvious since we hit a cycle.

Expected Output

Depending upon whether nan is mapped to be >1 or <1, respectively, either:

[1.0, nan, nan]
[nan, 1.0, nan]
[nan, nan, 1.0]

or

[nan, nan, 1.0]
[nan, 1.0, nan]
[1.0, nan, nan]

Possible Solution

Four ideas in order of likely selection:

1. Document failure/risk for generic T = IEEE floats with NaNs in play. Probably document need for ascending order as well as noted in source code snippet. { I mean, granted NaNs are a PITA almost everywhere and this documentation may be redundant upon using floats at all, but then again infinite loops on unforseen/unclean data are particularly nasty footguns that maybe deserve extra warning here. }

2. Avoid the cycle somehow (maybe by fiddling with the boolean logic of comparisons). sort itself seems to dodge the problem.

3. Some layer of indirection/transformation. Right now higher level caller can just replace nan with something compare-able like +-inf.

4. Add some generic constraint like not SomeFloat.

Additional Information

I'm not sure where the Julia guys landed in their stdlib/ecosystem, but there is really very little discussion of this topic anywhere that I could find besides here: https://groups.google.com/g/julia-users/c/BswpTOoHdfA (and even there it is kind of mentioned tangentially to the main issue of uniqueness/name bikeshedding).

I mostly thought I should report this since, like me, someone might someday run into the problem and then read the module docs and then search for a bug or PR and find nothing.

[litlighilit]

### Expected Output

And

### Possible Solution

These block formats are ill-formatted.

---

culprit

sort

sort uses system.cmp by default.

When either of its operands is NaN, it returns 1. For example, cmp(NaN, NaN) == 1

nextPermutation & prevPermutation

uses >= <= and <= <,

They all return false if either of operands is NaN