www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - proposal for general dup function

reply "Dan" <dbdavidson yahoo.com> writes:
Phobos can and should have a general dup function, capable of 
duping (i.e. recursive deep copy) structs without requiring any 
effort from struct developers. This can be done to cover the vast 
majority of object copy issues for structs and would have these 
benefits:

- no need to write (and potentially mess up) a dup function for 
your own structs
- ability to dup structs that others have written for which you 
don't have direct read access to all the fields
- as your structs grow less chance of bugs (the general dup would 
recognize and incorporate new fields)
- it addresses the inability to copy const and immutable 
reference structs (which Walter and Andrei may be looking to 
address with copy constructor feature)
- it would add more formality to the dup convention

Issues not covered:

- custom memory management by struct, some structs want to do low 
level stuff themselves. This is ok, though, as the struct 
developer can write his own dup and that will be honored by the 
general dup when composition requires it
- some resources are based on handles that can lead to 
indirection. For example, deep copy of file handles could cause 
unintended sharing. In these cases the back door is for the 
developer to write a custom dup or disable dup.
- classes not covered. Maybe the approach could be extended to 
support classes - but it is much more complicated.

Sample implementation:

I've written one called gdup just to distinguish it from dup. It 
is a function and a property, so the usage should feel natural. 
An example usage is shown below. Implementation and tests are 
located at:

https://github.com/patefacio/d-help/blob/master/d-help/opmix/mix.d
https://github.com/patefacio/d-help/blob/master/d-help/opmix/d_test/gdup_suite.d

A pdf writeup exists in section "dup and Global Dup" at:
https://github.com/patefacio/d-help/blob/master/doc/canonical.pdf?raw=true

The specific functions related to gdup are:

 property auto gdup(T)(const ref T t)
void gdup(T1, T2)(ref T1 t1, const ref T2 t2)
ref T opDupPreferred(T, F)(ref T target, const ref F src)

Some sample questions to the news group where this feature in the 
standard library would solve a user problem:

http://forum.dlang.org/thread/mailman.1946.1352987649.5162.digitalmars-d-learn puremagic.com?page=3
http://forum.dlang.org/thread/pzuparprsetydynbcuce forum.dlang.org
http://forum.dlang.org/thread/urvdcpflzajhpackmxyz forum.dlang.org


Thanks
Dan

   static struct A {
     char[] c;
   }
   static struct B {
     A a;
   }
   static struct C {
     B b;
   }
   void main() {
     const(C) c = C(B(A(['a'])));
     C c2 = c.gdup;
   }
Dec 09 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-09 15:45, Dan wrote:

 Phobos can and should have a general dup function, capable of duping
 (i.e. recursive deep copy) structs without requiring any effort from
 struct developers.


[snip]

I think much of this functionality could be shared with serialization. A 
few questions and comments.

* Are array slices properly handled
* I think there need to be a way to explicitly say that a given field 
and a whole struct shouldn't be duped
* All the public strings used for mixins should be templates

Orange serialization library, supports classes as well:

https://github.com/jacob-carlborg/orange

-- 
/Jacob Carlborg
Dec 09 2012
parent reply "Dan" <dbdavidson yahoo.com> writes:
On Sunday, 9 December 2012 at 16:26:12 UTC, Jacob Carlborg wrote:

 On 2012-12-09 15:45, Dan wrote:

 Phobos can and should have a general dup function, capable of 
 duping
 (i.e. recursive deep copy) structs without requiring any 
 effort from
 struct developers.


 [snip]

 I think much of this functionality could be shared with 
 serialization. A few questions and comments.


I am talking about a much smaller scope (just a few of functions 
- 200 lines of code tops) - but there are similarities.


 * Are array slices properly handled


Both array slices and associative arrays are properly handled. 
Let me know if you find otherwise.


 * I think there need to be a way to explicitly say that a given 
 field and a whole struct shouldn't be duped


I definitely see need for that in serialization. Not sure about a 
generalized dup function, though. I have a similar function for 
deeply comparing instances and I think this should always hold:

assert(typesDeepEqual(t, t.gdup))

If you skipped fields it would not.


 * All the public strings used for mixins should be templates


The mixins in the code are for higher-up functionality, some of 
it on top of the dup. There is no need for mixin for a general 
dup. The mixin(PostBlit) is there if you want to provide a dup 
for your struct so assignments in generic code gets the deep copy 
semantics with opAssign and copy construction. However, if 
template mixins are preferred to string mixins I suppose that is 
a good idea for that code and I'll check it out.

I have refactored the dup into its own module, so there is no 
need for mixin:
https://github.com/patefacio/d-help/blob/master/d-help/opmix/dup.d


 Orange serialization library, supports classes as well:

 https://github.com/jacob-carlborg/orange
Dec 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-12-10 13:56, Dan wrote:


 However, if template mixins are preferred to
 string mixins I suppose that is a good idea for that code and I'll check
 it out.


Yes, templates are always preferred. One should try to avoid putting 
code in string literals as much as possible.

-- 
/Jacob Carlborg
Dec 10 2012
prev sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 12/09/2012 03:45 PM, Dan wrote:

 Phobos can and should have a general dup function, capable of duping (i.e.
 recursive deep copy) structs without requiring any effort from struct
 developers. This can be done to cover the vast majority of object copy issues
 for structs


We already had some discussion about your gdup on d-learn, but just for clarity 
-- it's possible to do a gidup as well as gdup, correct?
Dec 10 2012
parent reply "Dan" <dbdavidson yahoo.com> writes:
On Monday, 10 December 2012 at 15:36:44 UTC, Joseph Rushton 
Wakeling wrote:

 On 12/09/2012 03:45 PM, Dan wrote:

 Phobos can and should have a general dup function, capable of 
 duping (i.e.
 recursive deep copy) structs without requiring any effort from 
 struct
 developers. This can be done to cover the vast majority of 
 object copy issues
 for structs


 We already had some discussion about your gdup on d-learn, but 
 just for clarity -- it's possible to do a gidup as well as 
 gdup, correct?


I think so. Here is a claim I think is true: gdup must do full 
deep copy to be safe and guarantee the transitive 
const/immutable. If it is implemented such that there are no 
casts, then the compiler does its job and ensures everything is 
good. If there are casts they need to be deemed safe - I have one 
cast to work around issues in associative array iteration. 
Assuming that is fine - I claim that gidup or igdup or whatever 
can just be:

 property auto gidup(T)(const ref T t) {
   immutable(T) result = cast(immutable)(t.gdup);
   return result;
}

     auto another = c.gidup;
     pragma(msg, typeof(another));
     assertNotEquals(another.b.a.c.ptr, c.b.a.c.ptr);
     assert(0==typesDeepCmp(another,c));

That is, since gdup does a full deep copy, casting the result to 
immutable is fine as there is no aliasing.

Thanks,
Dan
Dec 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-10 17:06, Dan wrote:


 I think so. Here is a claim I think is true: gdup must do full deep copy
 to be safe and guarantee the transitive const/immutable. If it is
 implemented such that there are no casts, then the compiler does its job
 and ensures everything is good. If there are casts they need to be
 deemed safe - I have one cast to work around issues in associative array
 iteration.


I'm pretty sure it can't be done. For classes one need to bypass the 
constructor. The constructor is the only place where you can initialize 
const/immutable fields. For class instance one would need to cast it to 
a ubyte pointer (or similar) and then set the const/immutable fields 
that way.

I think it can be done safely, but not something the compiler can guarantee.

-- 
/Jacob Carlborg
Dec 10 2012
next sibling parent reply "Dan" <dbdavidson yahoo.com> writes:
On Monday, 10 December 2012 at 18:55:09 UTC, Jacob Carlborg wrote:


 I'm pretty sure it can't be done. For classes one need to 
 bypass the constructor. The constructor is the only place where 
 you can initialize const/immutable fields. For class instance 
 one would need to cast it to a ubyte pointer (or similar) and 
 then set the const/immutable fields that way.

 I think it can be done safely, but not something the compiler 
 can guarantee.


Only talking about structs here. classes were listed under issues 
not covered.

Thanks
Dan
Dec 10 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-10 20:07, Dan wrote:


 Only talking about structs here. classes were listed under issues not
 covered.


You might have the same problem with structs. That is, if it's possible 
to have const/immutable files which are not initialized in the declaration.

-- 
/Jacob Carlborg
Dec 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-10 20:37, Jacob Carlborg wrote:


 You might have the same problem with structs. That is, if it's possible
 to have const/immutable files which are not initialized in the declaration.


That should have been "fields".

-- 
/Jacob Carlborg
Dec 10 2012
parent reply "Dan" <dbdavidson yahoo.com> writes:
On Monday, 10 December 2012 at 19:40:52 UTC, Jacob Carlborg wrote:

 On 2012-12-10 20:37, Jacob Carlborg wrote:


 You might have the same problem with structs. That is, if it's 
 possible
 to have const/immutable files which are not initialized in the 
 declaration.


 That should have been "fields".


You are correct. const or immutable fields won't work. But then, 
if you had a field that was const or immutable you might as well 
make it static. Any problems with gdup in that case would be the 
same you would see if you wanted to implement your own.
Dec 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-12-10 20:55, Dan wrote:


 You are correct. const or immutable fields won't work. But then, if you
 had a field that was const or immutable you might as well make it
 static. Any problems with gdup in that case would be the same you would
 see if you wanted to implement your own.


As I wrote in a previous post, it's possible to implement. I've done it 
in my serialization library.

-- 
/Jacob Carlborg
Dec 10 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/12 2:07 PM, Dan wrote:

 On Monday, 10 December 2012 at 18:55:09 UTC, Jacob Carlborg wrote:


 I'm pretty sure it can't be done. For classes one need to bypass the
 constructor. The constructor is the only place where you can
 initialize const/immutable fields. For class instance one would need
 to cast it to a ubyte pointer (or similar) and then set the
 const/immutable fields that way.

 I think it can be done safely, but not something the compiler can
 guarantee.


 Only talking about structs here. classes were listed under issues not
 covered.

 Thanks
 Dan


There will be the same problems with structs containing pointers.

Andrei
Dec 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/12 1:55 PM, Jacob Carlborg wrote:

 On 2012-12-10 17:06, Dan wrote:


 I think so. Here is a claim I think is true: gdup must do full deep copy
 to be safe and guarantee the transitive const/immutable. If it is
 implemented such that there are no casts, then the compiler does its job
 and ensures everything is good. If there are casts they need to be
 deemed safe - I have one cast to work around issues in associative array
 iteration.


 I'm pretty sure it can't be done.


Just like Dan I thought it can be done but actually ownership is 
impossible to establish in general. Consider:

class List(T) {
     List next;
     T payload;
     ...
}

versus

class Window {
     Window parent;
     ...
}

It's pretty obvious from the name that duplicating a List would entail 
duplicating its tail, whereas duplicating a Window would entail just 
copying the reference to the same parent. However, at the type level 
there's no distinction between the two members.

Now, user-defined attributes could change the playfield radically here. 
Consider we define things like  owned and  foreign that would inform the 
gdup or deepdup function appropriately:

class List(T) {
      owned List next;
     T payload;
     ...
}

versus

class Window {
      foreign Window parent;
     ...
}

Now a generic deep duplication function has enough information to 
duplicate things appropriately.


Andrei
Dec 10 2012
next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 10 December 2012 at 19:46:18 UTC, Andrei Alexandrescu 
wrote:

 On 12/10/12 1:55 PM, Jacob Carlborg wrote:

 On 2012-12-10 17:06, Dan wrote:


 I think so. Here is a claim I think is true: gdup must do 
 full deep copy
 to be safe and guarantee the transitive const/immutable. If 
 it is
 implemented such that there are no casts, then the compiler 
 does its job
 and ensures everything is good. If there are casts they need 
 to be
 deemed safe - I have one cast to work around issues in 
 associative array
 iteration.


 I'm pretty sure it can't be done.


 Just like Dan I thought it can be done but actually ownership 
 is impossible to establish in general. Consider:

 class List(T) {
     List next;
     T payload;
     ...
 }

 versus

 class Window {
     Window parent;
     ...
 }

 It's pretty obvious from the name that duplicating a List would 
 entail duplicating its tail, whereas duplicating a Window would 
 entail just copying the reference to the same parent. However, 
 at the type level there's no distinction between the two 
 members.


Unless the tail is immutable, but in general yes.


 Now, user-defined attributes could change the playfield 
 radically here. Consider we define things like  owned and 
  foreign that would inform the gdup or deepdup function 
 appropriately:

 class List(T) {
      owned List next;
     T payload;
     ...
 }

 versus

 class Window {
      foreign Window parent;
     ...
 }

 Now a generic deep duplication function has enough information 
 to duplicate things appropriately.


That is indeed a perfect use case for attributes.
Dec 10 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-10 20:46, Andrei Alexandrescu wrote:


 Just like Dan I thought it can be done but actually ownership is
 impossible to establish in general. Consider:

 class List(T) {
      List next;
      T payload;
      ...
 }

 versus

 class Window {
      Window parent;
      ...
 }

 It's pretty obvious from the name that duplicating a List would entail
 duplicating its tail, whereas duplicating a Window would entail just
 copying the reference to the same parent. However, at the type level
 there's no distinction between the two members.


I'm not sure, why wouldn't you want to copy the parent window as well?

-- 
/Jacob Carlborg
Dec 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/12 2:54 PM, Jacob Carlborg wrote:

 On 2012-12-10 20:46, Andrei Alexandrescu wrote:


 Just like Dan I thought it can be done but actually ownership is
 impossible to establish in general. Consider:

 class List(T) {
 List next;
 T payload;
 ...
 }

 versus

 class Window {
 Window parent;
 ...
 }

 It's pretty obvious from the name that duplicating a List would entail
 duplicating its tail, whereas duplicating a Window would entail just
 copying the reference to the same parent. However, at the type level
 there's no distinction between the two members.


 I'm not sure, why wouldn't you want to copy the parent window as well?


You want to create a new window with the same parent. At the top level 
there's one desktop window, and probably having two would be odd.

Andrei
Dec 10 2012
next sibling parent "Dan" <dbdavidson yahoo.com> writes:
On Monday, 10 December 2012 at 20:10:25 UTC, Andrei Alexandrescu 
wrote:


 You want to create a new window with the same parent. At the 
 top level there's one desktop window, and probably having two 
 would be odd.


Ok - so I'm only talking about structs.

What you say is what you want here and it makes sense. But that 
is not what I'm proposing. I'm just talking deep copy of structs 
that is always deep copy - period (bearophile called it 
transitive copy). By design that means there is no aliasing at 
all. So in this case the parent window would be deep copied. This 
can be done without any change to the struct (cycles when 
pointers are used are one design issue that would need to be 
addressed). This is also why gdup can be used to copy any 
immutable(T) into T (assuming is(T==struct)) and get around the 
"how do I copy const/immutable instances" we see so often.

Below illustrates what would happen and you would not want it for 
Window parent/child relationships - but you see the consistency. 
For what you describe you want reference semantics and gdup is 
not needed.

Given this - I think the original claim still holds.
     I claim that gidup or igdup or whatever
     can just be:

      property auto gidup(T)(const ref T t) {
       immutable(T) result = cast(immutable)(t.gdup);
       return result;
     }

I am not saying you can or should gdup any struct instance willy 
nilly, just that the cast to immutable here is safe because all 
fields are deep copied recursively.


------------------- output -------
Window("c1", 5, 5, 7FFF5BF3F4F0)
Window("c1", 5, 5, 7FAC74004FE0)
-------------------
import std.stdio;
import opmix.mix;

struct Window {
   string name;
   int x, y;
   Window *parent;
}

void main() {
   auto window = Window("root", 1, 1);
   auto child = Window("c1", 5, 5, &window);
   auto c2 = child.gdup;
   writeln(child);
   writeln(c2);
}
Dec 10 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-12-10 21:10, Andrei Alexandrescu wrote:


 You want to create a new window with the same parent. At the top level
 there's one desktop window, and probably having two would be odd.


There are many applications that support several top level windows. 
These are mostly document based.

-- 
/Jacob Carlborg
Dec 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/12 4:20 PM, Jacob Carlborg wrote:

 On 2012-12-10 21:10, Andrei Alexandrescu wrote:


 You want to create a new window with the same parent. At the top level
 there's one desktop window, and probably having two would be odd.


 There are many applications that support several top level windows.
 These are mostly document based.


Are we really up for continuing to debate this?

Andrei
Dec 10 2012
next sibling parent "Dan" <dbdavidson yahoo.com> writes:
On Monday, 10 December 2012 at 21:24:09 UTC, Andrei Alexandrescu 
wrote:

 On 12/10/12 4:20 PM, Jacob Carlborg wrote:

 On 2012-12-10 21:10, Andrei Alexandrescu wrote:


 You want to create a new window with the same parent. At the 
 top level
 there's one desktop window, and probably having two would be 
 odd.


 There are many applications that support several top level 
 windows.
 These are mostly document based.


 Are we really up for continuing to debate this?

 Andrei


I'm not up for this debate about Windows - just the original 
about gdup :-)

It is not an attempt to automatically determine reference or 
value semantics, even though your ideas on  owned and  foreign 
make sense and are a fine use of attributes. It is about a single 
phobos/library [g]dup function for structs that provides 
recursive deep copy without the need for struct designer to do 
anything extra. I think the benefits pointed out in the original 
make sense and are worth pursuing.

I have a feeling Walter would disagree - simply because 
apparently he is not a fan of postblits, which serve similar 
purpose. Further, from another thread he is not a fan of deep 
copy semantics in general, as he said there is almost never a 
need (which I would love to hear more commentary on). Yet TDPL 
shows the a prime example for the need in 7.1.3 (Widget). Plus we 
get questions all the time on how to cross from the 
const/immutable world to the mutable - which gdup provides.

Thanks
Dan
Dec 10 2012
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-12-10 22:24, Andrei Alexandrescu wrote:


 Are we really up for continuing to debate this?


No, not really. It's kind of a useless discussion. End.

-- 
/Jacob Carlborg
Dec 10 2012