seq pop malfunctions in array of seqs

[bptato]

Description

Following code

proc main() =
  var trimMap = [@[1], @[2]]
  var z = 0
  for j in 0 ..< 2:
    var i = trimMap.high
    while i >= 0:
      #let len {.volatile} = trimMap[i].len # this way it "works"
      let len = trimMap[i].len
      if len > 0:
        z = trimMap[i].pop()
        echo "set"
        break
      dec i
    echo "popped ", i
    doAssert z != 0
  echo "z", z

main()

prints:

set
popped 1
set
popped 1
fatal.nim(53)            sysFatal
Error: unhandled exception: z.nim(15, 5) `z != 0`  [AssertionDefect]

on both devel and 2.0.14, when compiled like:

nim c --mm:arc -d:danger -d:lto --cc:clang z.nim

with clang version 18.1.8. (-d:release instead of -d:danger has the same effect.)

The crash disappears if I do any of:

• set len to volatile
• --passc:-fno-strict-aliasing
• disable LTO
• --mm:refc

It also disappears if I switch to GCC, but this is probably by accident.
The original program that I reduced this from crashes under GCC as well.

len is supposed to be set in shrink:

/* z.nim.c */
struct tySequence__qwqHTkRvwhrRyENtudHQ7g {
	NI len;
	tySequence__qwqHTkRvwhrRyENtudHQ7g_Content* p;
};
struct tySequence__qwqHTkRvwhrRyENtudHQ7g_Content {
	NI cap;
	NI data[SEQ_DECL_SIZE];
};

static N_INLINE(NI, pop__z_u27)(tySequence__qwqHTkRvwhrRyENtudHQ7g* s_p0) {
	NI result;
NI L;
NI T1_;
T1_ = (*s_p0).len;
L = ((NI) (T1_ - ((NI) 1)));
result = ((*s_p0)).p->data[L];
((*s_p0)).p->data[L] = 0;
shrink__z_u42(s_p0, (L));
	return result;
}

/* system.nim.c */
typedef struct tyObject_NimSeqPayload__g7Ny9bTlNzn6dsxoJOHv6LQ tyObject_NimSeqPayload__g7Ny9bTlNzn6dsxoJOHv6LQ;
/* ^ incomplete struct; never gets defined anywhere */
struct tyObject_NimSeqV2__PEQQ33xihBDluJkSxo81LQ {
	NI len;
	tyObject_NimSeqPayload__g7Ny9bTlNzn6dsxoJOHv6LQ* p;
};

N_LIB_PRIVATE N_NIMCALL(void, shrink__z_u42)(tySequence__qwqHTkRvwhrRyENtudHQ7g* x_p0, NI newLen_p1) {
	(*((tyObject_NimSeqV2__PEQQ33xihBDluJkSxo81LQ*) (x_p0))).len = newLen_p1;
}

Perhaps the cast violates strict aliasing?

Nim Version

Nim Compiler Version 2.3.1 [Linux: amd64]
Compiled at 2025-01-01
Copyright (c) 2006-2025 by Andreas Rumpf

git hash: 3dda60a8ce32cb7d5e3e99111399a1550c145176
active boot switches: -d:release

Current Output

No response

Expected Output

set
popped 1
set
popped 0
z1

Known Workarounds

No response

Additional Information

ETA: this seems to fix it

diff --git a/lib/system/seqs_v2.nim b/lib/system/seqs_v2.nim
index 572e77408..3817b6bc5 100644
--- a/lib/system/seqs_v2.nim
+++ b/lib/system/seqs_v2.nim
@@ -133,7 +133,7 @@ proc shrink*[T](x: var seq[T]; newLen: Natural) {.tags: [], raises: [].} =
         reset x[i]
     # XXX This is wrong for const seqs that were moved into 'x'!
     {.noSideEffect.}:
-      cast[ptr NimSeqV2[T]](addr x).len = newLen
+      cast[ptr int](addr x)[] = newLen
 
 proc grow*[T](x: var seq[T]; newLen: Natural; value: T) {.nodestroy.} =
   let oldLen = x.len

C allows aliasing with the first member, so it makes sense.
But if it's a strict aliasing problem, then it's not an adequate fix, because the cast is also performed in other functions.

[juancarlospaco]

!nim c --gc:arc -d:lto

proc main() =
  var trimMap = [@[1], @[2]]
  var z = 0
  for j in 0 ..< 2:
    var i = trimMap.high
    while i >= 0:
      #let len {.volatile} = trimMap[i].len # this way it "works"
      let len = trimMap[i].len
      if len > 0:
        z = trimMap[i].pop()
        echo "set"
        break
      dec i
    echo "popped ", i
    doAssert z != 0
  echo "z", z

main()

[github-actions]

🐧 Linux bisect by @juancarlospaco (collaborator)

devel 👍 OK

Output

Filesize 91.98 Kb (94,192 bytes)
Duration

stable 👍 OK

Output

Filesize 91.75 Kb (93,952 bytes)
Duration

2.0.10 👍 OK

Output

Filesize 92.02 Kb (94,224 bytes)
Duration

2.0.0 👍 OK

Output

Filesize 88.00 Kb (90,112 bytes)
Duration

1.6.20 👍 OK

Output

Filesize 86.63 Kb (88,704 bytes)
Duration

1.4.8 👎 FAIL

Output

Filesize 86.63 Kb (88,704 bytes)
Duration

1.2.18 👍 OK

Output

Filesize 82.89 Kb (84,880 bytes)
Duration

1.0.10 👎 FAIL

Output

Filesize 82.89 Kb (84,880 bytes)
Duration

#a4f9bc55c ➡️ 🐛

Diagnostics

cooldome introduced a bug at 2020-10-28 13:00:49 +0000 on commit #a4f9bc55c with message:

The bug is in the files:

The bug can be in the commits:

• #051c20106
• #b0291b88f
• #1b5b98c94
• #645200aa3
• #a7bd58ed0
• #4a95d45b2
• #60403c9e6
• #e39b01e12
• #a4f9bc55c
• #e27f595ae

(Diagnostics sometimes off-by-one).

Stats

• GCC 11.4.0
• Clang 14.0.0
• NodeJS 20.5
• Created 2025-01-01T17:11:03Z
• Comments 1
• Commands nim c --gc:arc -d:lto -d:nimArcDebug -d:nimArcIds --run -d:nimDebug -d:nimDebugDlOpen -d:ssl -d:nimDisableCertificateValidation --forceBuild:on --colors:off --verbosity:0 --hints:off --lineTrace:off --nimcache:/home/runner/work/Nim/Nim --out:/home/runner/work/Nim/Nim/temp /home/runner/work/Nim/Nim/temp.nim

🤖 Bug found in 3 mins bisecting 327 commits at 82 commits per second

[bptato]

Reduced to

# nim r --mm:arc -d:danger -d:lto --cc:clang --nimcache:test z.nim 1 1
proc c_atoi(s: cstring): cint {.importc: "atoi", header: "<stdlib.h>".}

var cmdLine {.importc: "cmdLine".}: cstringArray

proc main() =
  var s = [@['a'], @['b']]
  let ap = cmdLine[1]
  let bp = cmdLine[2]
  let a = c_atoi(ap)
  let b = c_atoi(bp)
  discard s[a].pop()
  doAssert s[b].len == 0

main()

It very much looks like a strict aliasing issue. I suppose casting tySequence__{hash} to tyObject_NimSeqV2__{hash} is invalid because the struct tag is different, even if the layout is identical.
Now I wonder why the original program crashes with gcc, even though -opt:speed enables -fno-strict-aliasing for it. (In fact, gcc works fine in the reduced examples even with strict aliasing...)

[bptato]

Update: I haven't been able to reproduce the crash of the original program with gcc. I must have somehow enabled strict aliasing with gcc too when I first reported this (I remember manually compiling the C files at some point...)
So the cause is clear now, but I don't know how to fix it cleanly. For now I'll just open a PR to disable strict aliasing in nim.cfg with clang too, because miscompiling seqs by default seems rather problematic.

[yglukhov]

There's this comment # XXX This is wrong for const seqs that were moved into 'x'!, isn't it precisely the case in your tests? I don't know why exactly it's wrong, but -fno-strict-aliasing is a pretty tough compromise, don't you find?

[bptato]

I don't see why constness would matter. The core problem is that for seq[T], ARC generates code like this:

struct tySequence__qwqHTkRvwhrRyENtudHQ7g {
  NI len; tySequence__qwqHTkRvwhrRyENtudHQ7g_Content* p;
};
struct tySequence__qwqHTkRvwhrRyENtudHQ7g_Content { NI cap; NI data[SEQ_DECL_SIZE]; };

Let's call this struct a.
Then, the seqs_v2 implementation casts this struct to NimSeqV2[T], which generates another struct type (struct b):

struct tyObject_NimSeqV2__UJL9cu4tbrNCZCf2UdPtxbg {
	NI len;
	tyObject_NimSeqPayload__TINBeuSMmKEKXOgCHHb9b1Q* p;
};
struct tyObject_NimSeqPayload__TINBeuSMmKEKXOgCHHb9b1Q {
	NI cap;
	NI data[SEQ_DECL_SIZE];
};

The struct layout is equivalent, but in C, they are not compatible so long as the struct tag is different. Ergo casting struct a to struct b is UB. (I suppose clang sees this after inlining pop, and since len is already in a register, it will optimize out a second read of it.)

By the way, this casting pattern is used in the entire seqs_v2 module, and it seems even in typeinfo. So a local fix is insufficient.

but -fno-strict-aliasing is a pretty tough compromise, don't you find?

I actually think it's an improvement over the status quo. Right now, in the default nim.cfg:

• GCC opt:speed sets -fno-strict-aliasing. opt:size doesn't, even though it still applies there.
• clang doesn't set -fno-strict-aliasing at all.

The proposed patch at least makes it consistent.
Of course, I would also prefer to get rid of the flag instead, for this I see two ways:

1. Try to avoid the casts. I've actually tried this one, but doing it an actually standard-conforming way is frighteningly ugly. (The diff is 80 lines of weirdness, complete with casting seqs to ptr int and memcpy. And I'm still not sure if it's 100% right.)
2. Make the structs compatible. That means in the generated code, tyObject_NimSeqV2__hash becomes tySequence_hash, and tyObject_NimSeqPayload__hash becomes tySequence__hash_Content (or vice versa). As I said, I don't know how to do this, I've tried adding a magic but I got lost in the compiler code.

[yglukhov]

I actually think it's an improvement over the status quo

FWIW it increases code size in my wasm programs by ~0.5%, whereas your cast[ptr int] hack doesn't affect them in any way. Hence I would prefer the hack, or smth like {.emit: "`x`->len = `newLen`;".} which also works and produces identical assembly. But that's just my 2 cents.

[bptato]

FWIW it increases code size in my wasm programs by ~0.5%

To me that sounds like a fair compromise for a reliable seq.

whereas your cast[ptr int] hack doesn't affect them in any way. Hence I would prefer the hack

OK, here's the complete version: bptato@c14b59a

Is this still better?

[Araq]

Nim's cast is not C's cast, make the codegen use a memcpy.

[Araq]

But it seems to already use a union so I don't get the problem.

[bptato]

Nim's cast is not C's cast, make the codegen use a memcpy.

You mean to spit out a memcpy for every single read/store through a pointer?
(memcpy'ing the pointer itself is of course useless; the UB isn't casting per se, it's accessing the value through an incompatible type.)

But it seems to already use a union so I don't get the problem.

It doesn't, this is latest devel:

N_LIB_PRIVATE N_NIMCALL(void, shrink__x_u30)(tySequence__lBgZ7a89beZGYPl8PiANMTA* x_p0, NI newLen_p1) {
	(*((tyObject_NimSeqV2__xvFuaFKmaJ0Jo7e42e0lbA*) (x_p0))).len = newLen_p1;
}

Anyway, a union only helps if both the store and the read happen through said union type (ref). So for our purposes it would be useless.