On Wednesday, 4 March 2015 at 18:17:41 UTC, Andrei Alexandrescu wrote:
> Yah, this is a fork in the road: either we solve this with DIP25 + implementation, or we add stricter static checking disallowing two lent references to data in the same scope.

The third solution is to keep track of lifetimes, recognize refcounted types for structs the same as suggested for classes in DIP74, and wrap the lifetime of the subreference `t.s` in an opAdd/Release cycle for `t`, as illustrated in my other reply. You could have the compiler recognize a refcounted struct by simply declaring "void opAddRef();" and "void opRelease();", with the compiler automatically aliasing them to "this(this)" and "~this".

On Wednesday, 4 March 2015 at 10:49:06 UTC, Walter Bright wrote:
> On 3/4/2015 2:03 AM, deadalnix wrote:
>> A free list does not work as the data can be live.
>
> It is a "to free" list.
>

What I wanted to illustrate is that it is not a free list (which use the freed storage to maintain its state) as you cannot recycle storage.

>> You need to maintain metadata about allocation in
>> another structure.
>
> I don't see why.
>

Isn't it what the "to free" list is ?

>> Also you cannot free anything until all the refcount are to 0.
>
> Right.
>
>> This RC system will only cut it for short lived entities.
>
> Not a problem if they aren't constantly reassigning the value.

Having pool of object you recycle is a common strategy to reduce allocations when performance is critical. It is for instance incompatible with RC as proposed.

On Wednesday, 4 March 2015 at 10:50:54 UTC, Walter Bright wrote:
> On 3/4/2015 1:16 AM, bearophile wrote:
>> Walter Bright:
>>> The complexity of a free list doesn't remotely compare to that of adding an
>>> ownership system.
>> A sound complete ownership system is the only good enough solution for D. That's
>> my opinion.
>
> How do you type an an array of pointers with different owners?
>

Either the array is owning its elements or is is borrowing them. There is no array of element with different owners.

> How do you deal with the combinatoric explosion of template instantiations with all those different ownership types?

It is better than the combinatoric explosion of the code I have to write to support the various scheme proposed here (here RC and GC are 100% separet worlds).

As long as RC require bookkeeping, the codegen must be different anyway.

On Wednesday, 4 March 2015 at 19:22:25 UTC, Zach the Mystic wrote:
> On Wednesday, 4 March 2015 at 18:17:41 UTC, Andrei Alexandrescu wrote:
>> Yah, this is a fork in the road: either we solve this with DIP25 + implementation, or we add stricter static checking disallowing two lent references to data in the same scope.
>
> The third solution is to keep track of lifetimes, recognize refcounted types for structs the same as suggested for classes in DIP74, and wrap the lifetime of the subreference `t.s` in an opAdd/Release cycle for `t`, as illustrated in my other reply. You could have the compiler recognize a refcounted struct by simply declaring "void opAddRef();" and "void opRelease();", with the compiler automatically aliasing them to "this(this)" and "~this".

I'm sorry, I just realized this proposal is too complicated, and it wouldn't even work.

I think stricter static checking in @safe code is the way to go. When passing a global RC type to an impure, or duplicating the same RC reference variable in a function call, it's unsafe. The workaround is to make copies and use them:

static RcType s; // global
RcType c;

// Instead of:
func(s);
func(c, c);

// ...do this:
auto tmp = s; // get stack reference
func(tmp);
auto d = c; // copy Rc'd type
func(c, d);

Expensive, perhaps, but safe.

On Wednesday, 4 March 2015 at 18:05:52 UTC, Zach the Mystic wrote:
> On Wednesday, 4 March 2015 at 17:22:15 UTC, Steven Schveighoffer wrote:
>> Again, I think this is an issue with the expectation of RCArray. You cannot *save* a ref to an array element, only a ref to the array itself, because you lose control over the reference count.
>
> What you need is a special RCSlave type, which is reference counted not to the type of its *own* data, but to its parent's. In this case, a RCArraySlave!(T) holds data of type T, but a pointer to an RCArray, which it decrements when it gets destroyed. This could get expensive, with an extra pointer per instance than a regular T, but it would probably be safe.

A way to do this is to have a core RCData type which has the count itself and the chunk of memory the count refers to in type ambiguous form:

struct RCData {
  int count;
  // the point is that RCData can be type ambiguous
  void[] chunk;

  this(size_t size)
  {
    chunk = new void[size];
    count = 0;
  }
  void addRef() {
    ++count;
  }
  void decRef() {
    if (count && --count == 0)
      delete chunk;
  }
}

Over top of that you create a basic element type which refcounts an RCData rather than itself:

struct RCType(E) {
  E element;
  RCType* data;

  this(this)
  {
    data.addRef();
  }

  ~this()
  {
    data.decRef();
  }
  [...etc...]
}

Then you have an RCArray which returns RCType elements when indexed rather than naked types:

struct RCArray(E) {

  E[] array;
  private RCData* data;

  RCElement!E opIndex(size_t i) return
  {
    return RCElement!E(array[start + i], data);
  }

  this(E[] a)
  {
    data = new RCData(a * sizeof(a));
    array = cast(E[]) data.chunk;

  }

  this(this)
  {
    data.addRef();
  }

  ~this()
  {
    data.decRef();
  }

  //...
}

This might work. The idea is to only leak references to types which also have pointers to the original data.

Kind of OT, but your train of thought is very difficult to follow the way you are communicating (ie by updating on previous post by answering to yourself).

Could you post some more global overview at some point, so one does not need to gather various information for various posts please ?

On Wednesday, 4 March 2015 at 08:56:20 UTC, Ivan Timokhin wrote:
> Excuse me if I miss something obvious, but:
>
>     void main()
>     {
>         auto arr = RCArray!int([0]);
>         foo(arr, arr[0]);
>     }
>
>     void foo(ref RCArray!int arr, ref int val)
>     {
>         {
>             auto copy = arr; //arr's (and copy's) reference counts are both 2
>             arr = RCArray!int([]); // There is another owner, so arr
>                                    // forgets about the old payload
>         } // Last owner of the array ('copy') gets destroyed and happily
>           // frees the payload.
>         val = 3; // Oops.
>     }
>



struct PileInfo		"Red" 	TOP of PILE
{
	int refCount;
	RCDataBlock * top;
	RCDataBlock * bottom;
}

struct RCDataBlock	"Blue"	
{
	PileInfo * pileInfo;
	RCDataBlock * next;
	Array * payload;	//Actual Data.
}

struct RCArray
{
	RCDataBlock * block;
}


RCArray a,b,c,d;	//all different piles

a = b;
b = c;
d = a;			//makes them one single pile.


What if you pile them up. Blue cubes which contain the data.
And a Red cube containing the reference count equal to
the sum of all references to the blue cube of the same pile.
Basically a pile of blue cubes with a red cube on top.



1) RCArray a,b,c,d;		//------------

[1]
 x <-a

[1]
 x <-b

[1]
 x <-c

[1]
 x <-d


2) a = b;	//------------

[2]
 x <-[old b1]
 x <-a,b

[1]
 x <-c

[1]
 x <-d

3) b = c;	//------------


[3]
 x <-b,c
 x <-[old b1]
 x <-a,[old b2]

[1]
 x <-d


4) d=a;		//------------

[4]
 x <-b,c
 x <-[old b1]
 x <-[old a1],[old b2]
 x <-d,a

On Thursday, 5 March 2015 at 18:41:31 UTC, deadalnix wrote:
> Kind of OT, but your train of thought is very difficult to follow the way you are communicating (ie by updating on previous post by answering to yourself).
>
> Could you post some more global overview at some point, so one does not need to gather various information for various posts please ?

Okay. I seem to be mixing my more well-thought out ideas with ideas I get on the spur of the moment. Then they come out in a jumble. I have to confess that a lot of my ideas just pop into my head.

Did you want me to talk about how I would do ownership with my reference safety system?

On Thursday, 5 March 2015 at 20:47:55 UTC, Zach the Mystic wrote:
> Did you want me to talk about how I would do ownership with my reference safety system?

I'd like you to expose what is pretty settled down in your mind so we can have a base to understand the in flux part of the ideas :)

On 04/03/2015 08:55, Ivan Timokhin wrote:
>      void main()
>      {
>          auto arr = RCArray!int([0]);
>          foo(arr, arr[0]);
>      }
>
>      void foo(ref RCArray!int arr, ref int val)
>      {
>          {
>              auto copy = arr; //arr's (and copy's) reference counts are both 2
>              arr = RCArray!int([]); // There is another owner, so arr
>                                     // forgets about the old payload
>          } // Last owner of the array ('copy') gets destroyed and happily
>            // frees the payload.
>          val = 3; // Oops.
>      }

We could prevent reassignment of arr while val is alive, but perhaps still allow mutation of existing elements through arr.

I've changed Marc Schütz's example to explore this:

void main() {
    auto a = RCArray!int([5]); // a's refcount is now 1
    foo(a, a[0]); // pass by ref
}
void foo(ref RCArray!int a, ref int t) {
    a[0] = 4; // ok
    a = RCArray!int([]); // drop the old a
    t = 3; // oops, t is gone
}

I think Rust would enforce that either a *or* t can be mutably borrowed at once (and for a, t can't even be immutably-borrowed). Without designing a system, in theory foo is OK if a is const, but that prevents a[0] = 4. This could be allowed as long as a is not reassigned (i.e. a is head-const).

To support RCDynamicArray that supports appending and resizing, these operations also need to be excluded, whilst potentially allowing existing elements to be mutated.

(I've seen Andrei's solution for the above example, but it doesn't work for Ivan Timokhin's code, and for the former it can be non-ideal).

Perhaps a parameter attribute similar to head-const (but somehow configurable by the container author) could enforce this. The author of foo would need to use this attribute for a. The container could mark the safe mutation operations with this attribute.

Just an idea. I haven't considered other types of container, maybe it would help those also.