On Wednesday, 7 January 2015 at 14:59:58 UTC, H. S. Teoh via Digitalmars-d-learn wrote:
> On Wed, Jan 07, 2015 at 02:52:51PM +0000, Laeeth Isharc via Digitalmars-d-learn wrote:
>> Another schoolboy question.
>> 
>> Suppose I am constructing a tree (in this case it is an AST).  In C I
>> would have a pointer for the child to find the parent, and an array or
>> linked list of pointers to find the children from the parent.
>> 
>> Obviously, I could still use pointers, but that would not be
>> idiomatic.
>
> Not true. If you're using a tree structure, you *should* use pointers.
> Unless you're using classes, which are by-reference, in which case you
> can just use the class as-is. :-)
>
>
> --T

The GC is allowed to move structs around, as I undestand it.  Under what circumstances do I get into trouble having a pointer to them?

On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:
>
> The GC is allowed to move structs around, as I undestand it.  Under what circumstances do I get into trouble having a pointer to them?

None, a GC that moves structs around must update every pointer afterwards and as far as I know, the standard GC doesn't do that (moving things around).

You may not have a pointer inside a struct that points to the struct itself. This allows the compiler to elide some copies.

On Tuesday, 13 January 2015 at 17:41:53 UTC, Tobias Pankrath wrote:
> On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:
>>
>> The GC is allowed to move structs around, as I undestand it.  Under what circumstances do I get into trouble having a pointer to them?
>
> None, a GC that moves structs around must update every pointer afterwards and as far as I know, the standard GC doesn't do that (moving things around).
>
> You may not have a pointer inside a struct that points to the struct itself. This allows the compiler to elide some copies.

Got it - thanks.

On Wed, Jan 14, 2015 at 07:05:16PM +0000, Laeeth Isharc via Digitalmars-d-learn wrote:
> On Tuesday, 13 January 2015 at 17:41:53 UTC, Tobias Pankrath wrote:
> >On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:
> >>
> >>The GC is allowed to move structs around, as I undestand it.  Under what circumstances do I get into trouble having a pointer to them?
> >
> >None, a GC that moves structs around must update every pointer afterwards and as far as I know, the standard GC doesn't do that (moving things around).
> >
> >You may not have a pointer inside a struct that points to the struct itself. This allows the compiler to elide some copies.
> 
> Got it - thanks.

Having a pointer inside a struct that points to itself can also cause unexpected and sometimes very hard to find bugs. Example from real code where this bug occurred:

	struct S {
		// Resources we wish to cleanup
		Resource1 r1;
		Resource2 r2;
		...

		// List of cleanup routines we'd like to run when the
		// struct is destroyed.
		void delegate()[] cleanups;

		this(...) {
			// Acquire a resource
			r1 = acquireResource1();

			// Clean it up once we're done.
			// N.B.: the delegate implicitly closes over
			// 'this' -- this is what gets us in trouble
			// later.
			cleanups ~= { freeResource1(this.r1); };

			r2 = acquireResource2();
			cleanups ~= { freeResource2(this.r2); };

			...
		}

		~this() {
			// Cleanup resources in reverse order we
			// acquired them.
			foreach_reverse(dg; cleanups) {
				dg();
			}
		}
	}

	/* This function works without any problems. */
	void func1() {
		auto s = S(...); // create an instance of S
		doStuff();
		// Here, S gets cleaned up, and S's dtor releases the
		// resources correctly. No problem.
	}

	/* The following pair of functions, however, have problems... */
	S makeS() {
		// This is just a convenience function for creating an
		// instance of S. Useful for factoring out any messy
		// implementation details that may be needed from the
		// body of func2().
		return S(...);
	}
	void func2() {
		// Make an instance of S, as before.
		auto s = makeS();

		// Do some stuff
		doStuff();

		// And now we are done, so s's dtor should cleanup.
		// ... except, it crashes instead. Why??
	}

func1() runs perfectly normally, no problem. However, func2() crashes
upon exit. Why?

The reason is that the delegates created by S.this() close over the 'this' pointer to the new instance of S. But since S is a struct, this pointer is actually a pointer to a local variable on the stack of the caller. This is not a problem in func1() because this local variable resides in the same scope as the body of func1(), so the cleanup delegates get invoked before the local variable goes out of scope. However, in makeS(), we are returning a newly-created instance of S. The compiler actually implements this by creating a temporary local variable to hold the new instance of S, which means the 'this' pointer closed over by the delegates points to this temporary local variable, and then when the new instance of S is returned to func2(), since S is a by-value type, it gets bitwise copied into *another* local variable, that is, 's' in func2(). So the instance of S that func2() sees is actually a different copy of S than the one created by makeS(). The copy created by makeS() has now gone out of scope; however, the delegates registered in s.cleanups have not been adjusted, so they are still closing over the address of the original copy of S in makeS().

Now when func2() finishes and prepares to return, s's dtor gets invoked, and it calls the cleanup delegates which attempt to access the instance of S at the original address, which is now invalid. The result is that they see garbage data instead of the real values of .r1 and .r2, and it crashes the program. (If you're lucky, that is. If you're not so lucky, it won't crash, but will corrupt memory and/or get into an inconsistent state which causes malfunctions later on. Good luck tracing down the problem then!)

Moral of the story: don't have struct fields that point to the struct itself. This is almost always a bad idea. Structs have value semantics, and the implicit copying around will almost certainly break any self-referencing pointers, which leads to dangling pointers, good friends of memory corruption, et al. :-P


T

-- 
Trying to define yourself is like trying to bite your own teeth. -- Alan Watts

On Wednesday, 14 January 2015 at 19:36:44 UTC, H. S. Teoh via Digitalmars-d-learn wrote:
> Moral of the story: don't have struct fields that point to the struct
> itself. This is almost always a bad idea. Structs have value semantics,
> and the implicit copying around will almost certainly break any
> self-referencing pointers, which leads to dangling pointers, good
> friends of memory corruption, et al. :-P

If it actually had value semantics you would not be allowed to take the address of it... :-P

On Wed, Jan 14, 2015 at 07:43:17PM +0000, via Digitalmars-d-learn wrote:
> On Wednesday, 14 January 2015 at 19:36:44 UTC, H. S. Teoh via Digitalmars-d-learn wrote:
> >Moral of the story: don't have struct fields that point to the struct itself. This is almost always a bad idea. Structs have value semantics, and the implicit copying around will almost certainly break any self-referencing pointers, which leads to dangling pointers, good friends of memory corruption, et al. :-P
> 
> If it actually had value semantics you would not be allowed to take the address of it... :-P

Huh? ints have value semantics, yet you can take the address of a local int variable. What's your point?


T

-- 
Not all rumours are as misleading as this one.

On Wednesday, 14 January 2015 at 20:23:26 UTC, H. S. Teoh via Digitalmars-d-learn wrote:
> Huh? ints have value semantics, yet you can take the address of a local
> int variable. What's your point?

Strictly speaking the "int" looses its value semantics if you take the address of it, hold it and give it a new name (assign it to a pointer). It is forced to be an object with an identity (cannot sit in a register and is no longer alias free and indistinguishable from other ints with same value). Same issue with your struct, you turn it into an object with identity by holding the identity, yet keep acting if it is a value.

C's type system has questionable soundness, but I guess it could be corrected with behavioural typing... I.e. the preceding events and the state is part of the type and determines what actions it can participate it. Like a behavioural type for a file would make it an error at compile time to close a file before opening it. You could do something similar for taking the address of an int. (Which is kinda what linear typing tries to do.)

(( It follows from this that it will be challenging to achieve full memory safety without fixing the type system first. ))