digitalmars.D.learn - idiomatic D: what to use instead of pointers in constructing a tree
- Laeeth Isharc (10/10) Jan 07 2015 Another schoolboy question.
- H. S. Teoh via Digitalmars-d-learn (5/13) Jan 07 2015 Not true. If you're using a tree structure, you *should* use pointers.
- Laeeth Isharc (11/15) Jan 07 2015 Thanks v much.
- Paulo Pinto (4/20) Jan 07 2015 ref is a reserved keyword.
- Laeeth Isharc (2/3) Jan 07 2015 doh!
- Baz (6/31) Jan 07 2015 this conversation is so funny: well what's wrong with this . It's
- Tobias Pankrath (1/16) Jan 08 2015 No need to make fun of anyone.
- Laeeth Isharc (4/9) Jan 08 2015 Man afraid to ask stoopid questions stays stoopid. And compiler
- Mengu (2/11) Jan 08 2015 don't worry about it. use whatever you're comfortable with.
- H. S. Teoh via Digitalmars-d-learn (7/17) Jan 08 2015 Vim supports syntax highlighting.
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (4/7) Jan 08 2015 I am halfway there: I use syntax highlighting in Emacs but I chose to
- Paulo Pinto (6/26) Jan 08 2015 I don't get this, then again I am using syntax highlighting
- H. S. Teoh via Digitalmars-d-learn (14/22) Jan 08 2015 [...]
- Joseph Rushton Wakeling via Digitalmars-d-learn (8/13) Jan 08 2015 Small recommendation (apart from the reserved word issue which you fixed...
- Laeeth Isharc (3/11) Jan 10 2015 Thanks for the reminder. I use D Style when I am writing
- Laeeth Isharc (5/23) Jan 13 2015 The GC is allowed to move structs around, as I undestand it.
- Tobias Pankrath (6/9) Jan 13 2015 None, a GC that moves structs around must update every pointer
- Laeeth Isharc (3/14) Jan 14 2015 Got it - thanks.
- H. S. Teoh via Digitalmars-d-learn (90/104) Jan 14 2015 Having a pointer inside a struct that points to itself can also cause
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (4/12) Jan 14 2015 If it actually had value semantics you would not be allowed to
- H. S. Teoh via Digitalmars-d-learn (6/16) Jan 14 2015 Huh? ints have value semantics, yet you can take the address of a local
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (16/19) Jan 14 2015 Strictly speaking the "int" looses its value semantics if you
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (2/2) Jan 14 2015 (( It follows from this that it will be challenging to achieve
- Tobias Pankrath (6/7) Jan 07 2015 struct Tree
- Meta (14/21) Jan 07 2015 You can add some nice sugar for this as well:
- anonymous (4/23) Jan 07 2015 [...]
- Meta (3/4) Jan 07 2015 Oh, whoops. I thought those special variadic args were always
- Steven Schveighoffer (11/15) Jan 08 2015 Nope,
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. I also could just use integer array index references. A slice seems overkill to refer to just one object, but is that the best way ?
Jan 07 2015
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
Jan 07 2015
Not true. If you're using a tree structure, you *should* usepointers. Unless you're using classes, which are by-reference, in which case you can just use the class as-is. :-)Thanks v much. I just came to that realization also when I stepped away. class node { string name; node ref; } what's wrong with the code above ? i get an error no identifier for declarator node. (I have not used classes much, since structs often seem to be enough for what I need to do mostly).
Jan 07 2015
On Wednesday, 7 January 2015 at 15:02:34 UTC, Laeeth Isharc wrote:Not true. If you're using a tree structure, you *should* useref is a reserved keyword. -- Paulopointers. Unless you're using classes, which are by-reference, in which case you can just use the class as-is. :-)Thanks v much. I just came to that realization also when I stepped away. class node { string name; node ref; } what's wrong with the code above ? i get an error no identifier for declarator node. (I have not used classes much, since structs often seem to be enough for what I need to do mostly).
Jan 07 2015
ref is a reserved keyword.doh! Thanks.
Jan 07 2015
On Wednesday, 7 January 2015 at 15:04:24 UTC, Paulo Pinto wrote:On Wednesday, 7 January 2015 at 15:02:34 UTC, Laeeth Isharc wrote:this conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...Not true. If you're using a tree structure, you *should* useref is a reserved keyword. -- Paulopointers. Unless you're using classes, which are by-reference, in which case you can just use the class as-is. :-)Thanks v much. I just came to that realization also when I stepped away. class node { string name; node ref; } what's wrong with the code above ? i get an error no identifier for declarator node. (I have not used classes much, since structs often seem to be enough for what I need to do mostly).
Jan 07 2015
No need to make fun of anyone.this conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...what's wrong with the code above ? i get an error no identifier for declarator node. (I have not used classes much, since structs often seem to be enough for what I need to do mostly).ref is a reserved keyword. -- Paulo
Jan 08 2015
this conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...Man afraid to ask stoopid questions stays stoopid. And compiler error message far from informative. Not everyone is very visually oriented, and sometimes vi is quicker.
Jan 08 2015
On Thursday, 8 January 2015 at 11:29:30 UTC, Laeeth Isharc wrote:don't worry about it. use whatever you're comfortable with.this conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...Man afraid to ask stoopid questions stays stoopid. And compiler error message far from informative. Not everyone is very visually oriented, and sometimes vi is quicker.
Jan 08 2015
On Thu, Jan 08, 2015 at 11:29:29AM +0000, Laeeth Isharc via Digitalmars-d-learn wrote:Vim supports syntax highlighting. But I don't use it either -- I find it distracts from clarity of thought. I use plain vanilla vim in a text-only terminal. T -- Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at it. -- Pete Bleackleythis conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...Man afraid to ask stoopid questions stays stoopid. And compiler error message far from informative. Not everyone is very visually oriented, and sometimes vi is quicker.
Jan 08 2015
On 01/08/2015 09:40 AM, H. S. Teoh via Digitalmars-d-learn wrote:Vim supports syntax highlighting. But I don't use it either -- I find it distracts from clarity of thought. I use plain vanilla vim in a text-only terminal.I am halfway there: I use syntax highlighting in Emacs but I chose to make keywords and variables the same color. Ali
Jan 08 2015
On Thursday, 8 January 2015 at 17:42:23 UTC, H. S. Teoh via Digitalmars-d-learn wrote:On Thu, Jan 08, 2015 at 11:29:29AM +0000, Laeeth Isharc via Digitalmars-d-learn wrote:I don't get this, then again I am using syntax highlighting editors since MS-DOS IDEs supported it. -- PauloVim supports syntax highlighting. But I don't use it either -- I find it distracts from clarity of thought. I use plain vanilla vim in a text-only terminal. Tthis conversation is so funny: well what's wrong with this . It's a keyword... Aa Ha ha ha ha , rol. Seriously, is it so complicated to use a D editor ? I mean with syntax color...Man afraid to ask stoopid questions stays stoopid. And compiler error message far from informative. Not everyone is very visually oriented, and sometimes vi is quicker.
Jan 08 2015
On Thu, Jan 08, 2015 at 07:13:28PM +0000, Paulo Pinto via Digitalmars-d-learn wrote:On Thursday, 8 January 2015 at 17:42:23 UTC, H. S. Teoh via Digitalmars-d-learn wrote:[...][...]Vim supports syntax highlighting. But I don't use it either -- I find it distracts from clarity of thought. I use plain vanilla vim in a text-only terminal.I don't get this, then again I am using syntax highlighting editors since MS-DOS IDEs supported it.[...] It's just a personal preference. I find that overuse of colors produces a kaleidoscopic rainbow pattern on the screen which, while pretty, distracts from the essence of the code itself, which is what I'm focusing on. It's like a webpage with every other word italicized and/or bolded -- after a while, your brain just tunes it out and it becomes just meaningless (and distracting) noise. I much rather learn to parse the text (resp. code) accurately by eye and let it speak for itself. T -- Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at it. -- Pete Bleackley
Jan 08 2015
On 07/01/15 16:02, Laeeth Isharc via Digitalmars-d-learn wrote:class node { string name; node ref; }Small recommendation (apart from the reserved word issue which you fixed): it's generally considered good D style to give structs and classes names that start with capital letters, JustLikeThis. So, I suggest Node rather than node. Very minor point, and of course, your code is yours to style as you wish, but it can be helpful to meet the "standard" style conventions in order to make it as easy as possible for everyone else to understand. See also: http://dlang.org/dstyle.html
Jan 08 2015
Small recommendation (apart from the reserved word issue which you fixed): it's generally considered good D style to give structs and classes names that start with capital letters, JustLikeThis. So, I suggest Node rather than node. Very minor point, and of course, your code is yours to style as you wish, but it can be helpful to meet the "standard" style conventions in order to make it as easy as possible for everyone else to understand.Thanks for the reminder. I use D Style when I am writing properly, but haven't yet internalized it for a quick example and old habits die hard.
Jan 10 2015
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: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?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
Jan 13 2015
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.
Jan 13 2015
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:Got it - thanks.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.
Jan 14 2015
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: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 WattsOn Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:Got it - thanks.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.
Jan 14 2015
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. :-PIf it actually had value semantics you would not be allowed to take the address of it... :-P
Jan 14 2015
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: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.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. :-PIf it actually had value semantics you would not be allowed to take the address of it... :-P
Jan 14 2015
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.)
Jan 14 2015
(( It follows from this that it will be challenging to achieve full memory safety without fixing the type system first. ))
Jan 14 2015
A slice seems overkill to refer to just one object, but is thatthe best way ?struct Tree { Tree[] children; } Is one way to do it.
Jan 07 2015
On Wednesday, 7 January 2015 at 16:17:47 UTC, Tobias Pankrath wrote:A slice seems overkill to refer to just one object, but is thatYou can add some nice sugar for this as well: struct Tree { this(string data, Tree[] children...) { this.data = data; this.children = children; } string data; Tree[] children; } http://dpaste.dzfl.pl/76a8a4c44345the best way ?struct Tree { Tree[] children; } Is one way to do it.
Jan 07 2015
On Wednesday, 7 January 2015 at 20:25:10 UTC, Meta wrote:struct Tree { this(string data, Tree[] children...) { this.data = data; this.children = children;Don't do this without `dup`ing. Quoting the documentation:An implementation may construct the object or array instance on the stack. Therefore, it is an error to refer to that instance after the variadic function has returned:[...]int[] test(int[] a ...) { return a; // error, array contents invalid after return return a[0..1]; // error, array contents invalid after return return a.dup; // ok, since copy is made }http://dlang.org/function#variadic} string data; Tree[] children; }
Jan 07 2015
On Wednesday, 7 January 2015 at 23:27:19 UTC, anonymous wrote:Don't do this without `dup`ing. Quoting the documentation:Oh, whoops. I thought those special variadic args were always allocated on the heap.
Jan 07 2015
On 1/8/15 12:15 AM, Meta wrote:On Wednesday, 7 January 2015 at 23:27:19 UTC, anonymous wrote:Nope, Which makes it annoying, what if the argument IS passed on the heap? Fortunately, there is a solution (one I use in dcollections): foo(T[] x...) foo(T[] x) Can be overloaded. If you ever pass in parameters one at a time, the first is called, and x is guaranteed to be on the stack. The second is called with an actual array only, you are able to not 'dup', and just warn people that x will NOT be dup'd in that case. -SteveDon't do this without `dup`ing. Quoting the documentation:Oh, whoops. I thought those special variadic args were always allocated on the heap.
Jan 08 2015