Trill ARC

ARC.md

Automatic Reference Counting

Previously, Trill used the TinyGC garbage collector to manage memory allocated by indirect types. This garbage collector, though able to clean up these heap structures, does not afford the ability to introspect a data structure for its references, which is necessary to implement Copy on Write. As such, we have elected to move to an Automatic Reference Counting model for automatically managing the allocation of indirect types in the Trill language.

What is ARC?

ARC is used to automatically track references of objects that are allocated on the heap. It's done in a way that is predictable and will deterministically tear down objects when the number of references to them hits zero.

In an ARC world, the compiler instruments copies of and references to managed objects by manipulating a "retain count" that's stored alongside the object on the heap. When a new object or variable references a managed object, the compiler will insert an appropriate call to "retain" the object, increasing it's retain count by 1. Similarly, when that reference goes out of scope, the compiler will insert a call to "release" that object, decreasing its retain count by 1. When the retain count of an object hits zero, the compiler will automatically:

• Run a deinitializer that's specified in the source code
• Make a "release" call to all managed objects that are owned by this object
• Deallocate the memory for this object

It is an error to retain, release, or use an object after it has been deallocated.

Specification

Terminology

Term	Definition
trivially copyable	A type is considered "trivially copyable" if: • It is a primitive with no stored properties, or • It is a non-indirect type, and all of its stored properties are themselves trivially copyable.
passing	Any implicit copy or addition of a reference to an object.
+0	The object will not be retained, and it's the target's responsibility to retain the object.
+1	The object will be retained prior to the pass.
-0	The object will not be released by the target of a pass, and it will be the passer's responsibility to release it.
-1	The object will be released by the target of a pass, and will be returned to the passee.

There are a number of places in the Trill compiler that will require instrumentation:

Initialization

Managed objects will be initialized +1. It is the responsibility of the owner of the initialized object to release that object.

For example:

indirect type A {}

func main() {
    let a = A() // a has a retain count of 1 here
    release(a)  // This drops a's retain count to 0 and deallocates it 
}

Function Calls

If a function takes a parameter that is a managed type, then the object will be passed +0 and returned from the function -1. The callee will not need to retain or release the value. The code will desugar to this:

func takesIndirect(_ a: A) { // a is received +0
    retain(a) // a's retain count is now incremented, as this function owns a reference to a
    // use a
    release(a) // a's retain count is decremented, as this function is finished with a
}

func main() {
    let a = A() // a's retain count is 1, from initialization
    takesIndirect(a) // a's retain count will be incremented and decremented inside takesIndirect(_:)
    release(a) // a's retain count will be decremented and a will be deallocated
}

Promotion to Any

An Any is itself a managed object. It has a retain count alongside whatever it contains inside. When a managed object is promoted to an Any, it will be passed +1 into the promotion.

The deinitializer for an Any will check to see if it is currently holding a managed object internally, and that managed object is not nil. If so, it releases the underlying value explicitly. Otherwise, it performs no action.

func main() {
  // a's retain count is 1, from initialization
  let a = A()
  
  // a's retain count is now 2, because it will be held by the Any. 
  retain(a)
  
  // Here, any's retain count is 1, from initialization of the Any box.
  let any: Any = a
  
  // Here, any's retain count is dropped to 0.
  // As such, any will release its inner object, dropping a's retain count back to 1.
  release(any) 
  
  // a's retain count is dropped to 0, deallocating it.
  release(a)
}

When a value is cast out of an Any back to its specific type, then it is explicitly retained, and it is up to the caller to release the new reference.

func main() {
  // a's retain count is 1 from initialization
  let a = A()
  
  // a is retained in preparation for the `Any`, bringing its retain count to 2
  retain(a)
  
  // any's retain count is 1
  let any: Any = a
  
  // a's retain count is now 3, as the downcast causes a retain
  let newA = any as A
  
  // any's retain count drops to 0, which causes a release of a.
  // a's retain count is now 2
  release(any)

  // explicitly release newA, a's retain count is 1
  release(newA)
  
  // a's retain count is now 0, and a is deallocated.
  release(a)
}

Storage into Value Types

Value types are allowed to contain references to indirect types. If a value type contains a reference to an indirect type, then it participates in the retain/release cycle as well.

// TODO: Fill more cases out