Improve isstored logic

[mtfishman]

The changes to the code logic of isstored in #44 and #45 turned out to cause a lot of method ambiguities that were difficult to circumvent, this PR is meant to improve that, which makes ITensor/BlockSparseArrays.jl#79 easier to implement.

This may require marking it as a breaking change, we'll see from the downstream tests. Also as discussed, some of this logic will be superseded by #39, where we'll also have to think about which part of the isstored logic should be at the @interface level. It seems like it is better to not put the logic handling wrappers and index canonicalization at the @interface level from experiments here and in ITensor/BlockSparseArrays.jl#79, for the sake of minimizing method ambiguities.

[codecov]

Codecov Report

Attention: Patch coverage is 80.00000% with 4 lines in your changes missing coverage. Please review.

Project coverage is 75.21%. Comparing base (1236822) to head (4197ec4).
Report is 1 commits behind head on main.

Files with missing lines	Patch %	Lines
src/wrappers.jl	71.42%	4 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main      #46      +/-   ##
==========================================
- Coverage   75.59%   75.21%   -0.39%     
==========================================
  Files           7        7              
  Lines         463      472       +9     
==========================================
+ Hits          350      355       +5     
- Misses        113      117       +4     

Flag	Coverage Δ
docs	35.53% <45.00%> (?)

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[mtfishman]

This breaks the current release of BlockSparseArrays.jl so I marked it as breaking, ITensor/BlockSparseArrays.jl#79 updates BlockSparseArrays.jl based on the changes here.

[lkdvos]

Given what you already started doing here, and the reported ambiguities, it seems like the @interface approach might also just not necessarily be the best way to implement isstored. In principle, since there is no problem with having multiple (mixed) array types in the arguments, we might as well just dispatch on the array type, since writing @derive is about the same amount of work as just implementing this function.
That would remove once source of ambiguity: we no longer have an abstract interface type in the mix, so then the ambiguity resolution strategy could be:

• isstored(x::AbstractArray, I::MyIndType) is implemented generically to correctly dispatch to isstored(x::AbstractArray{T,N}, I::Vararg{Int,N}) or isstored(x::AbstractArray, I::Int).
• isstored(x::MyArrayType, I::Int) or isstored(x::MyArrayType{T,N}, I::Vararg{Int,N}) is specialized for the implementation

[mtfishman]

That's definitely a possibility. The use case I still have in mind are types that don't follow a convenient type hierarchy, for example SparseArrays.SpareMatrixCSC and LinearAlgebra.Diagonal aren't SparseArraysBase.AbstractSparseArray subtypes, but we still might want to derive the AbstractSparseArrayInterface definition of isstored for them.

So, I think it can still potentially fit into the plan you outlined, since isstored(x::MyArrayType, I::Int) or isstored(x::MyArrayType{T,N}, I::Vararg{Int,N}) could be implemented by deriving an interface version of isstored, or it could be implemented manually, or make use of a generic definition based on the type hierarchy, but the logic you outlined can be at the non-interface level.

Partially I'm bringing that up to play devil's advocate, and also start a discussion about when and why we might want to make a function into an interface function. Probably we'll have to decide based on a case-by-case basis about what can really be made generic across types, and maybe isstored is low-level enough (and has a simple enough implementation, or an implementation that is very dependent on the specific types) where that isn't worth it.

[mtfishman]

As a practical aspect, I'm a bit hesitant to start making wider changes to the isstored logic since things will be changing in #39 anyway, how do you think we should proceed with that? Is it worth putting off this change for now and doing it in #39?

[lkdvos]

I see what you mean about SparseMatrixCSC and Diagonal, but I don't think that's a great argument: comparing the following cases:

@derive (T=Diagonal,) isstored(::T, ::Int,::Int)

isstored(A::Diagonal, i::Int, j::Int) = i == j

or

@derive (T=SparseMatrixCSC,) isstored(::T, ::Int, ::Int)

function isstored(A::SparseMatrixCSC, i::Int, j::Int)
    i in nzrange(A, j)
end

It's not clear to me that these have good general definitions that would catch that, and even if they do, I'm not convinced the @derive implementation gives a great benefit over just manually implementing them.

---

That being said, I'm okay with merging this as is, exactly because we should rework it in #39 , so if this fixes the issues you are describing for now that works for me.

[mtfishman]

That's a reasonable argument. What I had in mind originally was trying to implement it as a generic function, with a definition like:

isstored(a::AbstractArray{<:Any,N}, I::Vararg{Int,N}) where {N} = CartesianIndex(I) in eachstoredindex(a)

and then as long as eachstoredindex has fast lookup, that definition would "just work". My original goal was to experiment with trying to make the most minimal interface as possible, but I think this is probably hitting the limit where that isn't worth it and requiring isstored as part of the required minimal interface makes the most sense (and also is probably expecting too much of eachstoredindex, since then it would both need to be an iterator over the stored indices and also have fast lookup).

I'll go ahead and merge this PR, since I think it moves things in the right direction and we can make more ambitious changes in #39.