Implementation notes for collection paging

[evanp]

Based on w3c/activitystreams#748 , we have a vague warning about implementing paging in the AS2 standard:

Using paging with an OrderedCollection can be tricky because there are no guarantees that implementations will process the sequence of pages in any predictable order.

It may be better to add more specific issues to the AP document instead; either in the "Collections" section, or in an appendix.

[evanp]

I did a blog post about this recently:

https://ghost.evanp.me/implementing-pagination-for-activitypub-collections/

I think we should add requirements to the "Collections" section that cover the following:

• A collection is represented by a top-level Collection or OrderedCollection object, plus a singly- or doubly-linked list of CollectionPage objects or OrderedCollectionPage objects. For this discussion, I'm going to stick just with OrderedCollection and OrderedCollectionPage, which are the best representation.
• The OrderedCollection should include a totalItems property, with the total item count, plus either an orderedItems property with all the items in it, or a first property with the id for the first OrderedCollectionPage in the list. It can also have a last property with the id of the last OrderedCollectionPage in the list if the list is doubly-linked, but I'm going to concentrate on singly-linked lists in this discussion.
• The OrderedCollectionPage should include a partOf property with the id of the OrderedCollection. It should have an orderedItems property with zero or more items, either as ids or as embedded objects. It should have a next property with the id of the next page, except for the last page.
• Items in the collection should be in reverse chronological order by insertion time. A new item added to the collection should be the first item in the first page. Items should be sorted within pages and across pages.
• The paging should be continuous. The last item in one page should be immediately newer than the first item in the next page. There should be no gaps between pages. There should be no overlap between pages.
• An item can be added to the front of a collection; the new item is always the first item in the first page or the first item in the collection if it doesn't have pages.
• Any arbitrary item can be removed from a collection; any item on any page can be removed.

[evanp]

@snarfed and I discussed whether insertion time sorting is always the right model. For example, if you are merging two accounts with e.g. LOLA it would be nice to interleave activities in their correct published order, not insertion order. There may be other situations where insertion order is not as useful.