AbstractArray or Composite?

Background

This issue does stuff with FillArrays, and got be thinking about a problem we've known about for a while but not successfully resolved.

Say that you have a Fill x of length N and you call getindex on it:

x[1]

How should the differential dx w.r.t x associated with this operation be represented? Some options:

1. (bad) a dense array with a single non-zero element.
2. (better) a fancy 1-hot array.
3. (great) a Composite{Fill{eltype(x)}}.

Option 1 is bad because it's obviously O(N)

Option 2 appears to be performant, but only until you consider adding it to another differential. Say that you also got x[2] at some point in your programme. At some point you'll have to accumulate the differential for x[1] and x[2], whose sum is clearly not also a 1-hot array. Consequently, we've lost performance, and essentially regressed to O(N) if you start adding lots of 1-hot arrays together.

Option 3 is great, because when adding two Composite{Fill{eltype(x)}} you get another one in O(1)-time and memory.

Upshot

As presented above, what needs to happen for Fills is quite obvious imho. What is less obvious is how this generalises. There's been a discussion going on for a while about the correct way to represent the differential of an AbstractArray.

It seems that the correct thing to do with an Array is represent it as another Array, and this seems to be because an Array is already completely general in that its elements can take any value you like.

What is less clear it what to do for structured arrays. Take, for example, Diagonal. Should we allow its adjoint to be represented by any other AbstractArray, or should be we using a Composite? My feeling is that this observation regarding Fills provides evidence in favour of the latter, and that we need to figure out ways to handle resulting problems that arise (e.g. say that a Composite representing a Diagonal was propagated into the rrule for matrix-matrix multiply. We would need to know what to do with it)

No implementation files or tests are named. Start by reading the discussion around Fill, Composite, Diagonal, AbstractArray, and getindex, including the linked pull request, then define the agreed differential representation and its behavior when propagated into matrix-matrix multiplication; done requires a settled design rather than an isolated edit.