Hello all,

I'm writing some code which is meant to represent a network of linked nodes.

Each node is represented by a struct that contains the node's ID and an array of links to other nodes.  Just as an experiment, I've tried out two different ways of doing this:

////////////////////////////////////////////////////////////////
struct Node1
{
	uint id;
	Link[] links;

	this(uint id)
	{
		this.id = id;
	}

	void addLink(uint l)
	{
		links ~= Link(l);
	}
}

struct Node2
{
	uint id;
	Array!(Link) links;

	this(uint id)
	{
		this.id = id;
	}

	void addLink(uint l)
	{
		links.insert(Link(l));
	}
}
////////////////////////////////////////////////////////////////

Now, either of these seem to work fine per se.  Just as a simple test, you can do something like,

	auto n1 = Node1(1);
	auto n2 = Node2(2);

	n1.addLink(5);
	n1.addLink(6);
	writeln(n1.links[0].id, "\t", n1.links[1].id);

	n2.addLink(7);
	n2.addLink(8);
	writeln(n2.links[0].id, "\t", n2.links[1].id);

... and all the correct results come out as you'd expect.

Now, suppose I want to implement a struct that groups together these nodes. Here's a go:

////////////////////////////////////////////////////////////////
struct Network(Node)
{
	Node[uint] nodes;

	void add(uint i, uint j)
	{
		if((i in nodes) is null)
			nodes[i] = Node(i);
		if((j in nodes) is null)
			nodes[j] = Node(j);

		nodes[i].addLink(j);
		nodes[j].addLink(i);
	}

	void print()
	{
		foreach(k; nodes.keys)
		{
			write("[", k, "]");
			foreach(l; nodes[k].links)
				write(" ", l.id);
			writeln();
		}
		writeln();
	}
}
////////////////////////////////////////////////////////////////

However, while this structure (which is essentially a wrapper around an associative array between node IDs and actual nodes) works fine with Node1, the dynamic array-based node structure, it fails with Node2, which is based on std.container.Array.

e.g. this works:

	Network!Node1 net1;
	net1.add(1, 5);
	net1.print();
	net1.add(1, 6);
	net1.print();

... but this segfaults:

	Network!Node2 net2;
	net2.add(1, 7);

I'm a bit confused as to why.  By the look of things it's actually the creation of new entries in the Node[uint] associative array, rather than appending links to the individual nodes.  Can anyone advise?

On a slightly different note, where std.container.Array is concerned: how come I can't use a foreach(i, x; myArray) formulation?  I.e. one where the foreach can infer the index value as well as the contained value ...

Thanks & best wishes,

     -- Joe

On 11/26/2012 04:07 PM, Joseph Rushton Wakeling wrote:
> I'm a bit confused as to why.  By the look of things it's actually the creation
> of new entries in the Node[uint] associative array, rather than appending links
> to the individual nodes.  Can anyone advise?

I have noticed that changing Node1 and Node2 from structs to classes means the code no longer segfaults, so presumably it's something related to reference versus value types ... ?

On Monday, 26 November 2012 at 19:14:09 UTC, Joseph Rushton Wakeling wrote:
> On 11/26/2012 04:07 PM, Joseph Rushton Wakeling wrote:
>> I'm a bit confused as to why.  By the look of things it's actually the creation
>> of new entries in the Node[uint] associative array, rather than appending links
>> to the individual nodes.  Can anyone advise?
>
> I have noticed that changing Node1 and Node2 from structs to classes means the code no longer segfaults, so presumably it's something related to reference versus value types ... ?

I think it is probably more to do with the interplay of Array as a value type in a hash, as this produces the same crash.

--------------------------------------
import std.container;
unittest {
  alias Array!int IntArr;
  IntArr[int] map;
  map[1] = IntArr();
}

On Monday, 26 November 2012 at 19:14:09 UTC, Joseph Rushton Wakeling wrote:
> On 11/26/2012 04:07 PM, Joseph Rushton Wakeling wrote:

Ok, now I really want to know why it crashes. I've narrowed it down to an example below. It seems there is a problem with RefCounted being used as value in a map.

At the bottom I've included some dissassembly. If anyone can shed light and maybe suggest techniques for debugging that would be great. The issue is the assignment 'map[1] = Foo()' is calling into 'void opAssign(typeof(this) rhs)' of RefCounted!int. But upon entry the this pointer looks reasonable but the store is bogus:
(gdb) p this
$28 = (struct std.typecons.RefCounted!(int).RefCounted *) 0x7fffffffd790
(gdb) p *this
$29 = {RefCounted = {_store = 0xffffffffffffffff}}

The rhs of the opAssign looks good:
p rhs
$30 = {RefCounted = {_store = 0x0}}

Any suggestions/pointers/ideas welcome.

Thanks
Dan

-------------------------
import std.typecons;
import std.stdio;

alias RefCounted!(int) Foo;
Foo[int] map;

unittest {
  map[1] = Foo();
}
--------------------
Dump of assembler code for function _D3lnk11__unittest1FZv:
   0x000000000044367c <+0>:	push   %rbp
   0x000000000044367d <+1>:	mov    %rsp,%rbp
   0x0000000000443680 <+4>:	sub    $0x38,%rsp
   0x0000000000443684 <+8>:	push   %rbx
   0x0000000000443685 <+9>:	movl   $0x1,-0x30(%rbp)
   0x000000000044368c <+16>:	lea    -0x30(%rbp),%rcx
   0x0000000000443690 <+20>:	movabs $0x8,%rdx
   0x000000000044369a <+30>:	movabs $0x481340,%rsi
   0x00000000004436a4 <+40>:	mov    %fs:0x0,%rdi
   0x00000000004436ad <+49>:	add    0x2478d4(%rip),%rdi        # 0x68af88
   0x00000000004436b4 <+56>:	callq  0x44df08 <_aaGetX>
   0x00000000004436b9 <+61>:	mov    %rax,-0x28(%rbp)
   0x00000000004436bd <+65>:	test   %rax,%rax
   0x00000000004436c0 <+68>:	jne    0x4436cc <_D3lnk11__unittest1FZv+80>
   0x00000000004436c2 <+70>:	mov    $0x8,%edi
   0x00000000004436c7 <+75>:	callq  0x44c50c <_D3lnk7__arrayZ>
   0x00000000004436cc <+80>:	sub    $0x8,%rsp
   0x00000000004436d0 <+84>:	xor    %rax,%rax
   0x00000000004436d3 <+87>:	mov    %rax,-0x10(%rbp)
   0x00000000004436d7 <+91>:	mov    %rax,-0x18(%rbp)
   0x00000000004436db <+95>:	lea    -0x18(%rbp),%rbx
   0x00000000004436df <+99>:	pushq  (%rbx)
   0x00000000004436e1 <+101>:	lea    -0x20(%rbp),%rdi
   0x00000000004436e5 <+105>:	callq  0x443d60 <_D3std8typecons18__T10RefCountedTiZ10RefCounted8opAssignMFS3std8typecons18__T10RefCountedTiZ10RefCountedZv>
=> 0x00000000004436ea <+110>:	add    $0x10,%rsp
   0x00000000004436ee <+114>:	lea    -0x20(%rbp),%rsi
   0x00000000004436f2 <+118>:	mov    -0x28(%rbp),%rdi
   0x00000000004436f6 <+122>:	mov    %rdi,-0x38(%rbp)
   0x00000000004436fa <+126>:	movsq  %ds:(%rsi),%es:(%rdi)
   0x00000000004436fc <+128>:	mov    -0x38(%rbp),%rax
   0x0000000000443700 <+132>:	mov    %rax,-0x8(%rbp)
   0x0000000000443704 <+136>:	callq  0x44370b <_D3lnk11__unittest1FZv+143>
   0x0000000000443709 <+141>:	jmp    0x443715 <_D3lnk11__unittest1FZv+153>
   0x000000000044370b <+143>:	lea    -0x20(%rbp),%rdi
   0x000000000044370f <+147>:	callq  0x443ce4 <_D3std8typecons18__T10RefCountedTiZ10RefCounted6__dtorMFZv>
   0x0000000000443714 <+152>:	retq
   0x0000000000443715 <+153>:	pop    %rbx
   0x0000000000443716 <+154>:	leaveq
   0x0000000000443717 <+155>:	retq
End of assembler dump.

On 11/26/2012 11:42 PM, Dan wrote:
> Ok, now I really want to know why it crashes. I've narrowed it down to an
> example below. It seems there is a problem with RefCounted being used as value
> in a map.

I don't have the expertise to understand the assembly, but just to note that even with all the structs converted to classes, nodes.d only compiles with dmd.  With ldmd2 or gdmd it exits with an error:

    container.d:2248: Error: cannot compare const(Tuple!(uint,"id")[]) and const(Tuple!(uint,"id")[])

... regardless of whether Node1 and Node2 are declared as structs or classes.

On Monday, 26 November 2012 at 22:42:53 UTC, Dan wrote:
> On Monday, 26 November 2012 at 19:14:09 UTC, Joseph Rushton Wakeling wrote:
>> On 11/26/2012 04:07 PM, Joseph Rushton Wakeling wrote:
>
> Ok, now I really want to know why it crashes. I've narrowed it down to an example below. It seems there is a problem with RefCounted being used as value in a map.
>
> <skipped rest>

I think it crashes because of using associative array. Assignment to an absent aa member causes memory allocation without proper object construction, and immediately after compiler issues call to opAssign for not-constructed object - that is why "this" pointer is "bogus" on entering function.

import std.stdio;

struct S
{
    int i = 42;
    struct SS
    {
        int ii = 41;
        this(this) { writeln("SS postblit"); }
        void opAssign(SS rhs) { writeln("SS opAssign"); }
    }
    SS ss;
    this(this) { writeln("S postblit"); }
    void opAssign(S rhs)
    {
        writeln("S opAssign");
    }
    ~this()
    {
        writefln("i=%d, ii=%d", i, ss.ii);
    }
}

S[int] map ;
// S[2] map;
// S[] map = [S(), S()];

void main()
{
    map[1] = S();
}

AA version on windows 2.060 prints

SS postblit
S opAssign
i=42, ii=41
i=4269990, ii=4269984 //garbage

Switching to dynamic or static array fixes the program.

On 11/27/2012 10:04 AM, Maxim Fomin wrote:
> On Monday, 26 November 2012 at 22:42:53 UTC, Dan wrote:
>> On Monday, 26 November 2012 at 19:14:09 UTC, Joseph Rushton Wakeling
>> wrote:
>>> On 11/26/2012 04:07 PM, Joseph Rushton Wakeling wrote:
>>
>> Ok, now I really want to know why it crashes. I've narrowed it down to
>> an example below. It seems there is a problem with RefCounted being
>> used as value in a map.
>>
>> <skipped rest>
>
> I think it crashes because of using associative array. Assignment to an
> absent aa member causes memory allocation without proper object
> construction, and immediately after compiler issues call to opAssign for
> not-constructed object - that is why "this" pointer is "bogus" on
> entering function.
>
> import std.stdio;
>
> struct S
> {
> int i = 42;
> struct SS
> {
> int ii = 41;
> this(this) { writeln("SS postblit"); }
> void opAssign(SS rhs) { writeln("SS opAssign"); }
> }
> SS ss;
> this(this) { writeln("S postblit"); }
> void opAssign(S rhs)
> {
> writeln("S opAssign");
> }
> ~this()
> {
> writefln("i=%d, ii=%d", i, ss.ii);
> }
> }
>
> S[int] map ;
> // S[2] map;
> // S[] map = [S(), S()];
>
> void main()
> {
> map[1] = S();
> }
>
> AA version on windows 2.060 prints
>
> SS postblit
> S opAssign
> i=42, ii=41
> i=4269990, ii=4269984 //garbage
>
> Switching to dynamic or static array fixes the program.

Same problem under Linux. Somebody, please file this bug! Thank you! :)

Ali

On Tuesday, 27 November 2012 at 18:30:07 UTC, Ali Çehreli wrote:
> Same problem under Linux. Somebody, please file this bug! Thank you! :)
>
> Ali

http://d.puremagic.com/issues/show_bug.cgi?id=9084

On Tuesday, 27 November 2012 at 18:04:19 UTC, Maxim Fomin wrote:

>
> I think it crashes because of using associative array. Assignment to an absent aa member causes memory allocation without proper object construction, and immediately after compiler issues call to opAssign for not-constructed object - that is why "this" pointer is "bogus" on entering function.
>

Thanks. Good troubleshooting.

On Monday, 26 November 2012 at 15:44:42 UTC, Joseph Rushton Wakeling wrote:
> Hello all,
>
> I'm writing some code which is meant to represent a network of linked nodes.
[snip]

Ok, another follow up. I can reproduce your segfault using your posted code, it is included below. But the interesting thing is, I was doing the "testing" out of your Network!Node2 in a unittest section. By whittling down, the smallest crash case I could come up with is this:

import std.typecons;
import std.stdio;
alias RefCounted!(int) Foo;
unittest {
  Foo[int] map;
  map[1] = Foo();
}

When I change that unittest block to a 'void main()' it works just fine. I tried the same change of unittest to 'void main()' on your code and found the same results - no crash. I think the crash issue might not be with map (even though Maxim found some troubling stuff with uninitialized structs being destructed when inserting a key that is not present). Or maybe it is just a map problem and by switching to main I am just getting lucky in not getting a crash.

It would be interesting to know if Joseph was doing his "testing" out in unittest or in a main.

Thanks
Dan

Here is the code that crashes. Change unittest to 'void main()' and it works??

-------------------
import std.container;
import std.stdio;

struct Link {
  int id;
  this(int i) { id=i; }
}

struct Node1
{
  uint id;
  Link[] links;

  this(uint id)
  {
    this.id = id;
  }

  void addLink(uint l)
  {
    links ~= Link(l);
  }
}

struct Node2
{
  uint id;
  Array!(Link) links;

  this(uint id)
  {
    this.id = id;
  }

  void addLink(uint l)
  {
    links.insert(Link(l));
  }
}
struct Network(Node)
{
  Node[uint] nodes;

  void add(uint i, uint j)
  {
    if((i in nodes) is null)
      nodes[i] = Node(i);
    if((j in nodes) is null)
      nodes[j] = Node(j);

    nodes[i].addLink(j);
    nodes[j].addLink(i);
  }

  void print()
  {
    foreach(k; nodes.keys)
      {
        write("[", k, "]");
        foreach(l; nodes[k].links)
          write(" ", l.id);
        writeln();
      }
    writeln();
  }
}

unittest {
  Network!Node2 net2;
  net2.add(1, 7);
  writeln(net2);
}