Conforming to Collection will require adding startIndex and endIndex properties (firstKey and lastKey), as well as an index(after: ) (basically nextKey) method.
We should likely just convert Given the new understandings of what we will need to do too get true conformance to a Collection (w.r.t. runtime complexities), combining the two will probably lead to a big file, so splitting it may just be more manageable and organized. SWIFT-195's Document+Sequence extension to be Document+Collection and have it all live there.
The documentation notes that "Types that conform to Collection are expected to provide the startIndex and endIndex properties and subscript access to elements as O(1) operations. Types that are not able to guarantee this performance must document the departure, because many collection operations depend on O(1) subscripting performance for their own performance guarantees."
We could potentially provide the startIndex and endIndex properties in O(1) if we wanted to store them in the Document. We would be unable to do that for subscript access, but it seems like it's ok to just document that departure.