IssueTracker

Hello, can you please attach a sample that reproduces your error?

I’ve attached two screen recordings demonstrating the mediator's behavior during the first and second launches after installation. Additionally, https://gist.github.com/yatiksihag01/20106aa4855bd438e3eb982034d4bb7d is link to a GitHub Gist containing the code for my remote mediator file for your reference.

Based on first_launch_after_installation.mp4, your paging state is indeed showing null for nextKey, so it makes sense that Paging concluded there are no more items to load.

So I think the question is why the PagingState contains only an empty page and null values. My guess is either

1. RemoteMediator REFRESH actually returned empty data - what is the returned allNewsItems value on initial REFRESH?
2. RemoteMediator REFRESH successfully loaded data and inserted it into database, but Paging hasn't processed that yet by the time Append is triggered, so PagingState is empty.

The second case doesn't seem likely though.

If you attach an executable app, I can look into this further.

Otherwise, you may gain more insight through Paging logs with adb shell setprop log.tag.Paging VERBOSE. You can also try implementing RemoteKeys in this codelab which addresses possible races between Refresh and subsequent loads.

Hey! I ran into this same issue. It is in fact the second case you mentioned and is documented here.

I've published a repo reproducing the issue and filed a ticket proposing how this could be changed.

I don't think the complexity here is completely avoidable from library perspective. Moving contents of movableContentOf generally involves:

• Cutting - inserting part of the slot table
• Removing - inserting nodes in applier
• Running side effects of node lifecycle (modifiers, etc)
• Relayout / replace / redraw

While applier overhead might be noticeable, the ripple effect of moving a node is much more significant, so I am not sure it is worth optimizing much here.

However, like I said, this puts the onus on the user, which is not desirable if it is avoidable, which I suspect is the case here.

From the performance perspective, it is more practical to minimize any movement instead of library trying to optimize for it.

I would like to clarify, for the case of single Composable/node insertion at the start of a list: Is the complexity of slot table operations (cutting/inserting slots & groups) actually quadratic, i.e. equivalent to the typical applier complexity in this case? I assumed that the slot table would typically re-use almost everything, and might just periodically need to push things over in its data structure when running out of space.

The other two bullet points only apply to Compose UI use cases. This issue is not about Compose UI and there is next to no ripple effect outside of composition & applier.

The complexity of moving slot table content scales with the number of movable content references rather than nodes, since the removal and insertion of each reference has constant overhead.

Slot table might reuse most of the memory, but cleanup + insertion still require copying data inside the table which is not exactly trivial. This operation might get cheaper at some point with a prototype of a new slot table that is currently in the works, but that is outside of this discussion.

Focusing on just the Applier, and not how to lift order higher in composition...

The current Applier was certainly designed around updating a tree structure and was designed in a way that the applier is agnostic to how the nodes are implemented but it does, as you point out, assume that an ordered access is efficient and meaningful. This is not a good fit for unordered structures. One benefit of the current API, however, is the Composer never reads back the structure produced by the Applier or any data from the Applier.

In other words, the applier is free to lie to the composer in certain ways. For example, it can encode the key and the item together as the node. Or just return the key, and keep the node to itself. However, this means that remove is challenging to implement given that the Applier would need to pay attention to index just to know what nodes are being removed.

I believe the simplest change would be to introduce an UnorderedApplier which would not need the index and it would pass the node to be removed as a parameter to remove instead of an index and length. The composer would then just have to check on deletes whether the to call the ordered or unordered version of remove. The rest of the uses of index can be ignored.

To be more disiplined, lets go over every member to see what assumptions it makes on order and hierarchy,

Here Agnostic means that the member would exist in if order or hierarchy was removed and would be unchanged. Ignoreable means that the composer assumes nothing about this and the applier is free to ignore it. As can be seen, the hierarchy can be ignored entirely and order can be ignored in most cases.

From this table (assuming it is right) the only problematic member is remove(...). The simplest change would be to introduce,

interface UnorderedApplier<N> : Applier<N> {
    remove(instance: N)
}

which the composer would query for when a delete occurs and call remove(instance: N) for all nodes that are removed by remove(index: Int, count: Int).

I need to think about the implications of lifting unorder higher in composition as this change, as pointed out above, is necessary but not sufficient for this to be implemented unordered node composition efficiently.

The key issue difference between unordered and order structures is identity. In an ordered structure, the order is the identity. Compose assume it can use order as identity and that is rather core to Compose. This means that compose fundamentally assumes the data structure it is maintaining is ordered.

To incrementally update the structure I need to know is this a new node of the structure or if this is an existing node that is being updated. Compose heavily leans on order of composition to determine this. It assumes, for example, that if the flow control changes then it can remove the content of the branch not taken and the new branch take has only new content. If the flow of control is the same, the structure is being updated in place, not changed.

To lift this higher compose would need to have a different way to track identity. As pointed out above, mutableContentOf does this by using the lambda instance (or, rather, a private key captured by the instance) as the root identity for a sub-tree of nodes. Moving the identity will move the content with the identity. Making each node a movableContentOf, however, is prohibitively expensive, as Andrei points out above. It was built with the assumption that the content it is tracking is relatively large and moves are rare. For unordered structures, neither assumption is true. The new slot table doesn't change these assumptions, it just makes certain operations movable content uses faster.

Order dependence is not just assumed by the nodes, it is assumed by remember as well. remember is based on positional memoization where the ordered position in the composition is assumed to part of the key for the remember. In other words, order in composition is the identity of the remember. Even if Compose handled unorder data we would need define what remember means in this context which is not currently clear to me.

For Compose to efficiently update unordered data structures we would need to decide when order identity matters and when it doesn't. We also need to define how the key for unordered data is declared and tracked. We may be able to use the underlying principles of movableContentOf to do this but we should not use it directly.

A straw man proposal for this would be to introduce UnorderedComposeNode. An UnorderedComposeNode would act much like movable content, in that it introduces a root for where order matters and the identity of remember is tracked with the key given to UnorderedComposeNode (e.g. the node key is the identity). A UnorderedComposeNode can move within a parent UnorderedComposeNode (or sub-composition, if the nodes are roots in composition) but cannot move between parents or other compositions without using movableContentOf. Limiting where the unorder content can move makes this tractable as it can handled in the Composer.

Thank you for the thorough elaboration, Chuck & Andrei. I had a couple thoughts while reading through it, that may not be out in the open clearly, at least for outside readers:

• The issue title is a bit misleading: there is no concern about supporting hierarchy in the Applier, there just is no significant natural hierarchy coming from composition in this use case.
• Regarding the order/hierarchy assumptions table: remove in combination with up and down does appear to have hierarchy dependence, to identify the node.

UnorderedComposeNode sounds ok to me from the Applier side.

It has seemed strange to me that the Applier has so much, somewhat "pretend", flexibility about how to implement its very specific operations, I wonder if it truly is a good thing. It would feel more natural to me, and easier to understand for a newbie, if I could emit different types of hierarchy nodes directly into the Applier, that have their own specific operations, rather than having one set of operations for the entire Applier, and leaving it up to a library author to implement the Applier operations in a reasonable manner. This is not quite what you have in mind with UnorderedComposeNode, I think, but might go in a similar direction.

What you suggest doesn't seem possible or I completely misunderstand what you mean. The Applier<N> just reflects the operations that the runtime tracks; it cannot be arbitrary or different without requiring changes to the internals of the Composer. The composer was designed to track a tree and the API reflects that. It was also designed based on my experience of working on several UI libraries, for all of which order and hierarchy mattered. This is the first time I have encountered an UI structure where order didn't matter. In other words, I designed an API for the Applier that would work with any of the UI frameworks I ever worked on.

As for up and down, they certainly imply hierarchy but whether there is one is purely up to the @Composable functions targeting the applier. That is, if you don't use the lambda based version of ComposeNode, which implies a container, you will never receive an up or down as all operations would be on the root. That means it can be ignored which is what I was trying to get to above by saying it is Ignorable as it is in the UnorderedComposeNode case because they would never be called. remove, on the other hand, can only be interpreted correctly based on index; that is, you must know what the order the nodes tracked by the composer to know what to delete. The current API is efficient for a tree data-structure like LayoutNode which uses MutableList<T> like data structure to hold the list of children. However, this is completely the wrong API for an unordered lists which you point out above. I believe the simplest changes, as I pointed out above, is to allow an applier to request a remove(node: N) be called instead of remove(index: Int, count: Int) which would then make index ignorable by an applier. It would also be more efficient for the composer to not track the order either when UnorderedComposeNode is used but that could be done as an optimization without API impact.

That being said, maybe you could propose a different API and we can discuss if the API could be adopted. I would rather talk about concrete proposals as they is less chances of misunderstanding.

Triage notes: Needs further discussion, retaining on backlog.

Thanks, Chuck, for elaborating more about up/down, makes sense.

I took your mention of a straw man proposal as an invitation to chime in with potentially infeasible thoughts; what I had in mind is unlikely to be compatible with the present Applier approach, and I don't have a deep enough understanding of the composer to say if it could be made compatible there. I also am not aware of all the ins & outs of the current Applier design.

It's worth noting that Compose is suffering from its own success here: it's useful and attractive for declarative programming outside Compose UI. I'd expect more "unordered" use cases to appear.

Regarding movableContentOf, I'm not clear if your proposal intends to keep it usable for unordered cases; I think it would be nice to use it here, it could make things easier for the API user, as they wouldn't have to worry about keys much when iterating.

Just to make it more clear what I had in mind earlier: it's nothing fancy, mainly a more object-oriented approach to tree building, as opposed to the generic tree traversal approach from Applier. Mainly because the tree is no longer uniform due to having both ordered and unordered sub-trees. Also because in the end I'd think that most Applier implementations have to re-invent something like this anyway.

The API I was thinking of would deemphasize the Applier, and move Applier operations to different types of "Nodes" that have their own distinct sets of operations. The different types of Nodes with their operations would be well-defined by Compose via interfaces, and most Node implementations would implement several interfaces at once. Implementation of operations would be less flexible than currently, and there is no up/down/current. Right now the Nodes would be along these lines:

ContentNode: has apply()

ReusableNode: has reuse()

RootNode: stores data tied to the entire hierarchy and operations relevant to being a root (e.g. onBeginChanges/onEndChanges/clear)

OrderedParentNode: data & operations for being a parent to an ordered collection of children; most ops from today's Applier

UnorderedParentNode: data & operations for being a parent to an unordered collection of children; uses key-based operations

I designed the Applier to be indenpendent of heirarchy. For example, it can work with Views where using interfaces as you describe, would require an adapter instance for every view. They Applier allows performaning all the operations required by the composer without requiring either 1) the nodes knowing about the composer operations, or 2) requring an additional allocation per node to adapt to be usable by the composer. The current approach doesn't even require the hierarchy to be instances (though it would require boxing, unfortunately, due to the erasure model of generics). I would resist losing this flexability).

The addition of remove(instance: N), as described above, would allow you to implement Applier<N> for each of the above set of interfaces without futher changes to the runtime.

Thanks, remove(instance: N) may be a good choice then. This would address the primary concern I think.

Still, it sounds like the above usage pattern for movableContentOf would cause performance degradation in the Composer for non-Compose UI, unordered use cases. Conceptually, essentially everything is unordered in my use case, so I'd not even want to explicitly use movableContentOf, but just let the Composer take care of it under the hood somehow. movableContentOf seems more of a crutch in this case, to adapt the unordered world to the ordered one. Perhaps there could be a more elegant under-the-hood way to achieve this, even if it meant extra slots or something. Like under-the-hood key() tracking of MovableContent IDs.

I don't propose that movableContent be used for unordered content for the reasons you state and I believe it is justified to consider built-in handling of unordered content. What I was envisioning is very close to what you suggest. The key would be used to select the part of the slot table that stores the previous state and the order in which these keys encountered is not considered relevant (e.g. no change is detect and applier is not notified when the nodes are encountered in a different order). In other words, random enumeration of a map would not be detected as a change.

That sounds terrific. Performance considerations aside, the explicit need for key in loops to track the appropriate State object (MarkerState in particular, which tracks Map Marker position that is owned by the underlying Maps View API) has been a pitfall in this library, and there are many issues filed that trip over it in some way. It sounds like the envisioned solution could greatly simplify this aspect.