Two suggestions for safe refcounting

[Zach the Mystic via Digitalmars-d]

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.