Writing my own custom-indexing array: type piracy from OffsetArrays methods

array

#1

I have implemented a simple circular buffer type similar to this, but with cumulative indexing, so that it has offset field that grows each time an element is pushed back to the full buffer. (That’s why I did not used immutable OffsetArray with its offsets tuple).

mutable struct SlidingBuffer{T} <: AbstractVector{T}
    buffer::Vector{T}
    len::Int
    contentLen::Int
    first::Int
    last::Int
    offset::Int
    function SlidingBuffer{T}(len::Int) where T
        new{T}(Vector{T}(undef, len), len, 0, 0, 1, 0, 0)
    end
end

# custom indexing
@inline Base.axes(A::SlidingBuffer) =
    (UnitRange{Int}(A.offset + 1, A.offset + A.contentLen),)

# and other methods from AbstractArray interface ...

It behaves in the following way:

b = SlidingBuffer{Int}(10)
> SlidingBuffer{Int64} with indices 1:0

[push!(b, 123) for _=1:15]
b
> SlidingBuffer{Int64} with indices 6:15:
 123
 123
 123
 123
   ⋮
 123
 123
 123
 123

Then, I figured that I miss some similar methods from https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array-1
and maybe used UnitRange instead of AbstractUnitRange.

And on some operations, like b = b*3 these methods are taken from OffsetArray.jl package, automatically converting my buffer to OffsetArray, due to this method:

Base.similar(::Type{T}, shape::Tuple{OffsetAxis,Vararg{OffsetAxis}}) where {T<:AbstractArray} =
    OffsetArray(T(undef, map(indexlength, shape)), map(indexoffset, shape))

with OffsetAxis broadly defined as:

const OffsetAxis = Union{Integer, UnitRange, Base.OneTo, IdentityUnitRange}

All these function recalls with different types are somewhat confusing. How should I write those similar and axes methods for my simple buffer type to not have any type inference between packages?


#2

Just a note on terminology: this is an ambiguity as a result of type-piracy. Inference/inferring is what Julia does to figure out types as it’s compiling and is wholly unrelated.

So, yes, OffsetArrays is doing a bit of type-piracy here — it’s defining a method assuming that it’ll be the only offset array package loaded at any given time. It’s generally a “bad thing” to define methods in a package where all the arguments come from other packages — or base itself! It leads to these sorts of situations, where two packages want the same signature. In general we try to design our interfaces such that this isn’t a problem, but this is a case where we’ve not found a great solution. And thus Base is coded with the expectation that there is exactly one OffsetArrays package loaded at any given time. You can still work with this, though, if your package depends on OffsetArrays and you define:

Base.similar(::Type{T}, shape::Tuple{OffsetAxis,Vararg{OffsetAxis}}) where {T<:SlidingBuffer} = ...

There are probably other definitions you’ll need here, too. Defining a custom offset array isn’t something that we’ve worked on making simple or easy (yet).

Note that as of Julia 1.1, we’re using Base.IdentityUnitRange as the type of offset axes.


#3

Thank you for explanation!
Yes, I noted that there is IdentityUnitRange, but what’s the point behind it? Also, tutorial says about using CustomUnitRanges.jl. So, should I use IdentityUnitRange or URange, or just stay with UnitRange?


#4

Ah, shoot! I missed that documentation when I changed this — that’s now out of date.

We’ve slowly been discovering that if the axes of an offset array are themselves also offset, then it makes a number of one-based algorithms magically work again. In short: it seems that the identity ax[i] == i is an important features of 1-based axes. In 1.0 we had used the special Base.Slice to provide this property, but it had first been used by SubArray for a slightly different purpose, leading to some strange bugs when we tried to shoehorn both uses together.

Lots more details here:



#5

More precisely, it’s doing a bit of piracy and “arrogantly” assuming the mantle of the default offset array package. (It’s probably good to have one of those.) It’s entirely possible to have more than one loaded at once; indeed, because one offset array package is sometimes just not enough :smile:, ImageFiltering.jl loads OffsetArrays, CatIndices.jl and FFTViews.jl at the same time. Because CatIndices and FFTViews define their own AbstractUnitRange types, there is no confusion.