0000-array-private-classes

- Feature Name: array_private_classes
- Start Date: 2022-01-08
- RFC PR: (leave this empty)
- Pony Issue: (leave this empty)

# Summary

Collection classes should not expose internal classes through iterators functions.

Following information hiding design principle, the builtin classes of collection
data structures must not be made visible through iterator functions like `ArrayKeys`,
`ArrayValues` and `ArrayPairs`. These classes can be made private as they are
only used as return types for `Array` functions `keys`, `values` and `pairs`.
The return values for these functions are changed to the more general interface
`Iterator`.

A new interface `RewindableIterator` is defined to allow for rewindable iterators,
like it is the case for `Array` `values`.

This design principle is applied to the other collection classes that expose
internals too like:

* `List`
* `Map`
* persistent `Map`
* `Vec`
* persistent `Vec`
* `Set`
* `Itertools`

This is a breaking change for collections' client code that use now internal
classes but a search on Github repositories shows that the impact should be
limited.

# Motivation

This change brings:

- Applying the design principle of
[hiding implementation details](https://en.wikipedia.org/wiki/Information_hiding)
but offer a general and stable interface. Returning interfaces instead of concrete
classes allows changing the implementation. Usually, one must return the most
general type that fullfils the contract of the function (in the case of the
functions discussed in this RFC, iteration).
- Collections' functions `keys`, `values` and `pairs` definitions are made more
general. Iterators implementation details are not public. Internal classes used
by implementation like `*Keys`, `*Values` and `*Pairs` are now
[opaque data types](https://en.wikipedia.org/wiki/Opaque_data_type). Generally,
when using these collection classes, clients are not interested by the iterators
implementation, but by the types these iterators return and that is provided by
the generic parameters.
- The generic return signature of these 3 iterating functions is simpler to
understand for clients of collection classes.
- Reduces the number of public classes in the standard library by hiding 18
specialised classes (iterators implementations) of which 3 are from the
`builtin` module.
- The interface `RewindableIterator` is added to create rewindable iterators
(can be re-start from first value).

This change remains compatible with the existing code base but for client code
that is directly using the classes `*Keys`, `*Values` and `*Pairs`. A search on
Github shows that the impact is very limited.

# Detailed design

Iterating functions in collections `keys`, `values` and `pairs` are changed to
return `Iterator` and the classes that implement these iterators are made private.
Here are the full implementation of these functions for the `Array` class (changes
in other collection classes are identical).

As the function `values` of class `Array` uses an iterator with a `rewind` function
that is not part of the `Iterator` interface, a new interface `RewindableIterator`
is added to enable creation of rewindable iterators.

```pony
  fun keys(): Iterator[USize]^ =>
    """
    Return an iterator over the indices in the array.
    """
    _ArrayKeys[A, this->Array[A]](this)

  fun values(): RewindableIterator[this->A]^ =>
    """
    Return an iterator over the values in the array.
    """
    _ArrayValues[A, this->Array[A]](this)

  fun pairs(): Iterator[(USize, this->A)]^ =>
    """
    Return an iterator over the (index, value) pairs in the array.
    """
    _ArrayPairs[A, this->Array[A]](this)
```

Note: To remain consistent with `Array` behaviour, functions `keys` and `pairs`
should return a `RewindableIterator` too but we limited the API change to minimum
as we did not understood why it was not already the case.

```pony
interface RewindableIterator[A] is Iterator[A]
  """
  A `RewindableIterator` is an iterator that can be rewinded, that is start
  again from first item. The data structure being iterated on can't change the
  order it return iterated items.
  """
  fun has_next(): Bool
    """
    Return `true` when function `next` can be called to get next iteration item.
    """

  fun ref next(): A ?
    """
    Return the next item of the iteration or an error in case there are no other
    items. A previous call to `has_next` check if we can continue iteration.
    """

  fun ref rewind(): Iterator[A]^
    """
    Start the iterator over again from the beginning.
    """
```

The code of the standard library is adapted to remove use of these now private
classes, mainly in tests. Here are the files that must be changed:

* `packages/builtin/array.pony` as shown above
* `packages/itertools/iter.pony` in function `cycle`
* `packages/collections/heap.pony` in function `values`
* `packages/collection/builtin/_test.pony` in class `_TestArrayValuesRewind`
* `packages/collections/list.pony`
* `packages/collections/map.pony`
* `packages/collections/persistent/map.pony`
* `packages/collections/persistent/vec.pony`
* `packages/collections/set.pony`
* `test/libponyc/util.cc` to change the name of the class to `_ArrayValues`

## Detailed changes

In order to judge how the API becomes simpler to understand for clients of the
collections classes, here are the changes in the functions' signatures. The `-`
line shows the old signature while the `+` one is the new:

```pony
// Array
-  fun keys(): ArrayKeys[A, this->Array[A]]^ =>
+  fun keys(): Iterator[USize]^ =>
-  fun values(): ArrayValues[A, this->Array[A]]^ =>
+  fun values(): RewindableIterator[this->A]^ =>
-  fun pairs(): ArrayPairs[A, this->Array[A]]^ =>
+  fun pairs(): Iterator[(USize, this->A)]^ =>

// Heap
-  fun values(): ArrayValues[A, this->Array[A]]^ =>
+  fun values(): Iterator[this->A]^ =>

// List
-  fun nodes(): ListNodes[A, this->ListNode[A]]^ =>
+  fun nodes(): Iterator[this->ListNode[A]]^ =>
-  fun rnodes(): ListNodes[A, this->ListNode[A]]^ =>
+  fun rnodes(): Iterator[this->ListNode[A]]^ =>
-  fun values(): ListValues[A, this->ListNode[A]]^ =>
+  fun values(): Iterator[this->A]^ =>
-  fun rvalues(): ListValues[A, this->ListNode[A]]^ =>
+  fun rvalues(): Iterator[this->A]^ =>

// Map
-  fun keys(): MapKeys[K, V, H, this->HashMap[K, V, H]]^ =>
+  fun keys(): Iterator[this->K]^ =>
-  fun values(): MapValues[K, V, H, this->HashMap[K, V, H]]^ =>
+  fun values(): Iterator[this->V]^ =>
-  fun pairs(): MapPairs[K, V, H, this->HashMap[K, V, H]]^ =>
+  fun pairs(): Iterator[(this->K, this->V)]^ =>

// Persistent Map
-  fun val keys(): MapKeys[K, V, H] =>
+  fun val keys(): Iterator[K] =>
-  fun val values(): MapValues[K, V, H] =>
+  fun val values(): Iterator[V] =>
-  fun val pairs(): MapPairs[K, V, H] =>
+  fun val pairs(): Iterator[(K, V)] =>

// Persistent Vec
-  fun val keys(): VecKeys[A]^ =>
+  fun val keys(): Iterator[USize]^ =>
-  fun val values(): VecValues[A]^ =>
+  fun val values(): Iterator[A]^ =>
-  fun val pairs(): VecPairs[A]^ =>
+  fun val pairs(): Iterator[(USize, A)]^ =>

// Set
-  fun values(): SetValues[A, H, this->HashSet[A, H]]^ =>
+  fun values(): Iterator[this->A]^ =>
```

# How We Teach This

This change keeps the code compatible in the vast majority of cases. When client
classes are defining objects of these now private types, the reason is usually
to get access to the function `rewind` that was not defined in `Iterator`. By
adding the interface `RewindableIterator`, client code can easily be adapted,
replacing `ArrayValues[A]` by `RewindableIterator[A]`.

Also, client code generally uses these functions to iterate on the returned types
and does not try to access the iterator directly but is interested by the iterated
items. When client code refers to the iterator type, that's generally useless and
the code can be rewritten to be made shorter and more future proof.

A [search on Github Pony code](https://github.com/search?q=%22ArrayValues%22+language%3APony&type=code)
finds 24 files using the class `ArrayValues`, of which 6 are copies of `array.pony` file.

For instance, in
[xml2xpath.pony](https://github.com/redvers/pony-libxml2/blob/bbca5d98d48854bfec2c6ee110220873ecc4df34/pony-libxml2/xml2xpath.pony#L41),
the code can be changed from

```pony
  fun values(): ArrayValues[Xml2node, this->Array[Xml2node]]^ ? =>
    if (allocated) then
      ArrayValues[Xml2node, this->Array[Xml2node]](nodearray)
    else
      error
    end
```

to

```pony
  fun values(): RewindableIterator[Xml2node]^ ? =>
    if (allocated) then
      nodearray.values()
    else
      error
    end
```

In this sample, the developer was not really concerned by the type of the iterator
but that the `values` function must return an `RewindableIterator` over `Xml2node`.
The new version makes the code simpler to understand.

This change in `array.pony` and other collections will break such code but it
can be easily adapted to use the new API. And it will make the standard library
easier to learn by reducing the number of public types.

# How We Test This

Pony tests must continue to pass. No additional tests are need as after review
the existing coverage in Pony standard library tests is sufficient

# Drawbacks

Will break any existing code that uses any of the classes that are currently
public and will be made private by this RFC.

# Alternatives

Stay as is. Continue the
[discussion on Zulip](https://ponylang.zulipchat.com/#narrow/stream/189959-RFCs/topic/Make.20Array.20iterators.20private).

Instead of defining a new type of iterator with the `RewindableIterator` interface,
we can consider only the rewindable part of it in an `Rewindable` interface:

```pony
interface Rewindable[A]
  fun ref rewind(): Iterator[A]^
    """
    Start the iterator over again from the beginning.
    """
```

Then one can create a rewindable iterator by composing these two interfaces:

```pony
type RewindableIterator[A] is (Iterator[A] & Rewindable[A])
```

The rewindable type can be used with other types than `Iterator`, like a data
structure that would implement a rewindable property. This alternative was
[put aside](https://github.com/ponylang/rfcs/pull/193#discussion_r780793165) to
prevent name colisions in `builtin` with user-named types.

# Unresolved questions

Pony language definition is not precise about
[type variance](https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science))
and its impact in collections classes, particularly for covariant return types
of functions (in this RFC, `keys`, `values` and `pairs`).