⚠️ This is ready for review but shouldn't be merged yet. ⚠️

Turns out the required frame dependencies are much more limited than what I originally thought and this PR can be hugely simplified, thanks @amirh. 🎉 Updated with a new patch to only cache one required frame over the limit at a time.

This is also now ready to merge whenever it gets LGTM.

Thanks Michael! great to see this simplified!

What do you think about further simplifying by removing our initialization step of marking required frames?
I believe we can instead just keep 2 members (one for the previous required frame and one for the previous frame) which should be enough to make sure we always have the required frame in memory.
We should then be able to treat all other frames with equal caching priority.

I believe we can instead just keep 2 members (one for the previous required frame and one for the previous frame) which should be enough to make sure we always have the required frame in memory.

Just to make sure @amirh: you mean these two members in addition to the regular map of cached bitmaps within our decoded limit, right? Since we'd still want the frame-indexed cache for non-required frames after looping.

If I'm understanding your suggestion right, I think this would work but it would end up taking more memory at runtime. I think we'd need to cache 2 frames over the limit instead of just 1 in cases where we were using required frames at all, and in cases where we weren't we'd always cache 1 frame over the limit instead of 0. We'd want to always cache the N-1 frame in case it ends up being required, even in GIFs that don't have any required frames at all or only one required frame. Since we'd no longer be saving this info about the frames at initialization, we'd need to assume the worst. In cases of overflow always caching N-1 would also mean inserting and deleting from the cache every frame, too. And then on top of that we'd always want to cache the actual last required frame (if it exists) in case a previously required frame is used again instead of the N-1 frame. I don't think it would be preferable to the initialization step since it would end up using more memory, and I don't think the initialization step is really costing us much. What do you think?

We talked about this offline. So far the frameBitmaps_ cache has been mixing concerns about caching extraneous frames under the limit and caching required frames in general, which makes the caching logic hard to follow because it's special casing the required frames. I didn't remove the initialization step entirely, but I did update the patch so that it always keeps the last required frame completely separate from the frameBitmaps_ collection of generic decoded frames. I think the logic is more straightforward now.