A bug in my code

[Denis Koroskin]

On Sat, 06 Sep 2008 05:12:56 +0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> This code isn't short, but can someone help me spot the bug/problem (D1,  
> DMD)?
> I have tried to write clean & short code, to help spotting problems.
>
> It produces an (no error line given):
> Error: overlapping array copy
>
> It's just a stack data structure (here for simplicity just for items of  
> type int), made with a single linked list of blocks that become  
> geometrically bigger.
>
>
> import std.gc: malloc, hasNoPointers;
>
> int min(int a, int b) {
>     return a <= b ? a : b;
> }
>
>
> class IntStack {
>     struct Block {
>         int len;
>         Block* next;
>         int* data;
>     }
>
>     Block* list_head, list_tail;
>     int total_len;
>     int used_last_block; // how many items are used in the last (tail)  
> block
>
>
>     this() {
>         this.list_head = block_alloc(4);
>         this.list_tail = list_head;
>     }
>
>
>     ubyte* mem_alloc(int nbytes) {
>         auto p  = cast(ubyte*)malloc(nbytes);
>         if (p is null)
>             throw new Error("not enough mem");
>         hasNoPointers(p);
>         return p;
>     }
>
>
>     Block* block_alloc(int nints) {
>         auto new_block = cast(Block*)mem_alloc(Block.sizeof);
>         new_block.data = cast(int*)mem_alloc(nints * int.sizeof);
>         new_block.len = nints;
>         new_block.next = null;
>         return new_block;
>     }
>
>
>     final void opCatAssign(int x) {
>         if (this.used_last_block == this.list_tail.len) {
>             // then last block is full and we must create a new one
>             this.used_last_block = 0;
>             auto new_block = block_alloc(this.list_tail.len * 2);
>
>             // append to the linked list
>             this.list_tail.next = new_block;
>             this.list_tail = new_block;
>         }
>
>         this.list_tail.data[this.used_last_block] = x;
>         this.used_last_block++;
>         this.total_len++;
>     }
>
>
>     int[] toarray() {
>         if (!this.total_len)
>             return null;
>
>         int* result_ptr = cast(int*)mem_alloc(this.total_len *  
> int.sizeof);
>         int[] result = result_ptr[0 .. this.total_len];
>
>         Block* aux_ptr = this.list_head;
>         int pos;
>
>         // Here: Error: overlapping array copy
>         while (aux_ptr != null) {
>             // in the last block copy only up to the total_len
>             int ncopy = min(aux_ptr.len, this.total_len - pos);
>            result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
>             pos += ncopy;
>             aux_ptr = aux_ptr.next;
>         }
>
>         return result;
>     }
> }
>
>
> void main() {
>     auto st = new IntStack();
>
>     for (int i; i < 70_000; i++)
>         st ~= i;
>
>     auto aux = st.toarray;
>     aux = st.toarray;
> }
>
>
>
> ---------------------
>
> Note: in that code I haven't used variable-length structs, like the  
> following idiom sometimes used in C, because it gives array bounds  
> errors:
>
>
> struct Block {
>     int len;
>     Block* next;
>     int[1] data;
> }
> ...
> auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) *  
> int.sizeof);
>
>
> I presume that can't be done in D (I don't want to write code that works  
> only in release mode).
>
> Bye and thank you,
> bearophile

Just started digging your case. This behaviour is 100% repeatable with  
DMD1.028 but never takes place with DMD1.029+ (Windows).