As per deadalnix's request, a summary of my thoughts regarding the thread "RCArray is unsafe":

It's rather easy to guarantee memory safety from the safe confines of a garbage collected system. Let's take this as a given.

It's much harder when you step outside that system and try to figure out when it is or isn't safe to delete memory. It shouldn't be too surprising, therefore, that there are lots of pitfalls. Reference counting is a lonely outpost in the wilderness which is otherwise occupied by manual memory management. It's the only alternative to chaos.

But the walls protecting this outpost are easily breached by any dangling reference which is not accounted for.

We have seen two instances of how this can occur. The first, when boiled down to its essence, is that there is no corresponding bump in the reference count for a parameter which can alias an existing reference:

void fun(ref RCStruct a, ref RCStruct b);
RCStruct c;
fun(c,c); // c aliases itself

void gun(ref RCStruct a);
static RCStruct d;
gun(d); // d aliases global d

Because the workarounds are easy:
{
  RCStruct c;
  auto tmp = c;
  fun(c,tmp);

  auto tmp2 = d;
  gun(tmp2);
}
...it seems okay to mark these rare violations @system.

The second, harder problem, is when you take a reference to a subcomponent of an RC'd type, e.g. an individual E of an RCArray of E:

struct RCArray(E) {
  E[] array;
  int* count;
  ...
}
auto x =  RCArray([E()]);
E* t = &x[0];

Here's the problem. If x is assigned to a different RCArray, the one t points to will be deleted. On the other hand, if some special logic allows the definition of t to increment the reference count, then you have a memory leak, because t is not designed to keep track of x's original counter.

I don't know if we can get out of this mess. My suggestion represents a best-effort attempt. The only way I can see out of this problem is to redesign RCArray.

The problem with RCArray is that it "owns" the data it references. If a type different from RCArray, i.e. an individual E* into the array of E[], tries to reference the data, it's stuck, because it's not an RCArray!E. Therefore, you need to separate out the core data from the different types that can point to it. The natural place would be right next to its reference counter, in a separate struct:

struct RCData {
  int count = 0;
  void[] chunk;

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

Now RCArray can be redesigned to point to an RCData type. All new RC types will also contain a pointer to an RCData instance:

struct RCArray(E) {
  E[] array;
  private RCData* data;

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

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

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

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

Note how the last member, opIndex, doesn't return a raw E*, but only an E* which is paired with a pointer to the same RCData instance as the RCArray is:

struct RCElement(E) {
  E* element;
  private RCData* data;

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

This is the best I could do.

On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:
...
> Note how the last member, opIndex, doesn't return a raw E*, but only an E* which is paired with a pointer to the same RCData instance as the RCArray is:
>
> struct RCElement(E) {
>   E* element;
>   private RCData* data;
>
>   this(this) {
>     data.addRef();
>   }
>   ~this() {
>     data.decRef();
>   }
> }
>
> This is the best I could do.

It's needed to change type of this from RCArray to tuple!(RCArray, RCData). But as for me better to use Array and cahnge typeof(this) to RefCounter!Array:
assert(typeid(typeof(this)) == typeid(RefCounter!Array));

So how to deal with it:
struct RefCounter(T) // this is struct!
{
void opAddRef();
void opRelease();
alias this = __data;
void[] allocate(size_t)

// Hendler for sharing owned resources
auto opShareRes(MemberType)(ref MemberType field)
{
    return makeRefCounter(field, __count);
}

private:
size_t __count;
T __data;
}

@resource_owner(RefCounter)
class Array
{
ref int opIndex(size_t i) return
{
    return _data[i];
}

//// opIndex will be replaced with this function
//RefCounter!int opIndex(size_t i) // @return?
//{
//    assert(typeid(this) == typeid(RefCounter!Array));
//    return this.opShareResource(_data[i]);
//    // after inlining: return makeRefCounter(_data[i], __count);
//}

private int[] _data;
}

Method opShareRes is to move resources away(share with other owner) and an @return method will change its return type to opSharedRes return type. opShareRes also wraps access to public fields(and may change type of result).

Now Array is actualy alias to RefCounter!Array. Array creation is special case. "new Array" have to use RefCounter!Array.allocate. So owner manage array parts sharing, allocation and removing.

Options for @resource_owner
@resource_owner(this) - class provides opAddRef/opRelease/opShareRes by itself as in DIP74
@resource_owner(this, MyRCMixin) - MyRCMixin provides opAddRef/opRelease/opShareRes and will be mixed in class.(What DIP74 has in mind)
@resource_owner(Owner) - Owner is a template. Whenever you use owned type T it will be replaced with Owner!T(even type of "this"). This case prohibits changing owning strategy.

Resourse owning is close to memory management. Maybe resource owner have to set memory allocation strategy instead of providing method allocate.

On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:
> The second, harder problem, is when you take a reference to a subcomponent of an RC'd type, e.g. an individual E of an RCArray of E:
>
> struct RCArray(E) {
>   E[] array;
>   int* count;
>   ...
> }
> auto x =  RCArray([E()]);
> E* t = &x[0];

But taking that address is unsafe to begim with. Do arguably, this isn't that big of a problem.

Your first dual reference issue seems much more problematic, as there are always cases the compiler can't catch.

On Friday, 6 March 2015 at 14:59:46 UTC, monarch_dodra wrote:
>> struct RCArray(E) {
>>  E[] array;
>>  int* count;
>>  ...
>> }
>> auto x =  RCArray([E()]);
>> E* t = &x[0];
>
> But taking that address is unsafe to begin with. Do arguably, this isn't that big of a problem.

Taking the address is only really unsafe (in a non-RC'd type) if you don't have a lifetime tracking system. As long as the lifetime of the address taker is shorter than the address of the takee, it's not inherently unsafe. Whether D will end up with such a system is a different question.

But I still think there's value in having a separate RCData type, because you can save one pointer per instance of RCArray. Right now, if you take a slice of an RCArray, your working array might not start at the same place as the reserved memory array. Therefore you need to keep a pointer to the reserved memory in addition to your active working array. If the counter and the pointer to the original memory are in the same place, one pointer will get you both.

I think the idea is worth exploring.

> Your first dual reference issue seems much more problematic, as there are always cases the compiler can't catch.

How so? If all we're talking about is RC'd types, the compiler can catch everything. I think the greater concern is that the workarounds will take a toll in runtime performance. I'll try to illustrate:

void fun(ref RCStruct a, ref RCStruct b);

auto x = new RCStruct;
fun(x, x);

This wouldn't be safe. If fun() contained a line "a = new RCStruct;", b will point to deleted memory for the rest of the function. The normal way to protect this to make sure there's another reference:

auto y = x;
fun(x,x);

This is actually safe, because y bumps the reference counter to 2 when initialized, which is enough to cover all possible reassignments of x. The compiler could do this automatically. It could detect that the parameter x aliases itself and create a temporary copy of x. But it would mean the runtime performance cost of the copy and postblit and destructor call. So D probably can't invest in that strategy, since the programmer should have a choice about it.

So it's not about it being impossible to deal with the safety problems here, just that the runtime cost is too high.

But there are some ways out. If the given type has no postblit, for example (or "opAddRef" for  classes), there's no reason to mark the operation unsafe, since you know it's not reference counted. Also, const parameters are safe and won't be affected.

On Friday, 6 March 2015 at 14:40:31 UTC, Volodymyr wrote:
> On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:
> ...
>> Note how the last member, opIndex, doesn't return a raw E*, but only an E* which is paired with a pointer to the same RCData instance as the RCArray is:
>>
>> struct RCElement(E) {
>>  E* element;
>>  private RCData* data;
>>
>>  this(this) {
>>    data.addRef();
>>  }
>>  ~this() {
>>    data.decRef();
>>  }
>> }
>>
>> This is the best I could do.
>
> It's needed to change type of this from RCArray to tuple!(RCArray, RCData). But as for me better to use Array and cahnge typeof(this) to RefCounter!Array:
> assert(typeid(typeof(this)) == typeid(RefCounter!Array));
>
> So how to deal with it:
> struct RefCounter(T) // this is struct!
> {
> void opAddRef();
> void opRelease();
> alias this = __data;
> void[] allocate(size_t)
>
> // Hendler for sharing owned resources
> auto opShareRes(MemberType)(ref MemberType field)
> {
>     return makeRefCounter(field, __count);
> }
>
> private:
> size_t __count;
> T __data;
> }
>
> @resource_owner(RefCounter)
> class Array
> {
> ref int opIndex(size_t i) return
> {
>     return _data[i];
> }
>
> //// opIndex will be replaced with this function
> //RefCounter!int opIndex(size_t i) // @return?
> //{
> //    assert(typeid(this) == typeid(RefCounter!Array));
> //    return this.opShareResource(_data[i]);
> //    // after inlining: return makeRefCounter(_data[i], __count);
> //}
>
> private int[] _data;
> }
>
> Method opShareRes is to move resources away(share with other owner) and an @return method will change its return type to opSharedRes return type. opShareRes also wraps access to public fields(and may change type of result).
>
> Now Array is actualy alias to RefCounter!Array. Array creation is special case. "new Array" have to use RefCounter!Array.allocate. So owner manage array parts sharing, allocation and removing.
>
> Options for @resource_owner
> @resource_owner(this) - class provides opAddRef/opRelease/opShareRes by itself as in DIP74
> @resource_owner(this, MyRCMixin) - MyRCMixin provides opAddRef/opRelease/opShareRes and will be mixed in class.(What DIP74 has in mind)
> @resource_owner(Owner) - Owner is a template. Whenever you use owned type T it will be replaced with Owner!T(even type of "this"). This case prohibits changing owning strategy.

You've packed a lot of ideas into one post. Your solution might work, but it's hard for me to tell.

> Resourse owning is close to memory management. Maybe resource owner have to set memory allocation strategy instead of providing method allocate.

This is an open question. I'm still wrestling with understanding all the interlocking systems. The only reason I keep exploring them is that sometimes it seems like nobody else understands them either. ^_^

On Friday, 6 March 2015 at 22:41:16 UTC, Zach the Mystic wrote:

> You've packed a lot of ideas into one post. Your solution might work, but it's hard for me to tell.

Yeah... How about this one:
In C++ type of "this" is T*. If we could pass shared_ptr<T> as
"this" (instead of raw ptr) system will be much safer. Same
solution may be applied for D's "this" with RefCounter!T