Brace Expansion in {n1..n2..n3} is returning incorrect results in some cases.
rwmills opened this issue · 3 comments
Extract from 1.0.7 man page:
Brace Expansion
In the remaining forms, a field is created for each number starting at n1 and continuing until it reaches n2 incrementing n1 by n3. The cases where n3 is not specified behave as if n3 where 1 if n1<=n2 and -1 otherwise. If forms which specify %fmt any format flags, widths and precisions can be specified and fmt can end in any of the specifiers cdiouxX. For example, {a,z}{1..5..3%02d}{b..c}x expands to the 8 fields, a01bx, a01cx, a04bx, a04cx, z01bx, z01cx, z04bx and z04cx.
{n1..n2..n3} is returning incorrect results in some cases. The table below shows some examples.
.
| command | result | expected |
|---|---|---|
| echo {1696512000..1696512000..300} | wc -w | 47722 | 1 |
| echo {1696512000..1696512000..1} | wc -w | 1 | 1 |
| echo {1696512000..1696512000..10} | wc -w | 1 | 1 |
| echo {1696512000..1696512000..99} | wc -w | 1 | 1 |
| echo {1696512000..1696512000..100} | wc -w | 429497 | 1 |
| echo {1696512000..1696512100..99} | wc -w | 2 | 2 |
| echo {1696512000..1696512100..100} | wc -w | 2 | 2 |
Thanks for the report.
The behaviour is identical on ksh 93u+ 2012-08-01 and on ksh2020.
The issue seems to be 32-bit integer overflow in path_generate():
Line 250 in e0218fc
The overflow likely occurs here:
Line 408 in e0218fc
The obvious fix is to switch to 64-bit integers, but then we'd get the same problem again with huge numbers, because that line has an inherent overflow problem due to the multiplication by incr.
You'd think that
if(incr*(first+incr) > last*incr)can be simplified to:
if(first+incr > last)However, that doesn't work because incr may be negative. The comparison operator also needs to adapt to the negativity of incr. The following patch does that:
diff --git a/src/cmd/ksh93/sh/expand.c b/src/cmd/ksh93/sh/expand.c
index 940dbe08c..1191f8fed 100644
--- a/src/cmd/ksh93/sh/expand.c
+++ b/src/cmd/ksh93/sh/expand.c
@@ -405,7 +405,7 @@ endloop1:
*(rescan - 1) = '}';
*(cp = end) = 0;
}
- if(incr*(first+incr) > last*incr)
+ if(incr < 0 ? (first + incr < last) : (first + incr > last))
*cp = '}';
else
first += incr;That should fix the bug reported (please test).
A more complete fix will be to change to 64-bit integers as well. However, that will take more testing, as the % formatting, also supported by brace expansion, may break in subtle or architecture-dependent ways.
Have rebuilt ksh after applying your fix and done some tests. Results are looking good. Will let you know if I find any problems with the fix. Thanks for the quick response.