<commit_before>// RUN: %target-run-simple-swift
// REQUIRES: executable_test

// https://bugs.swift.org/browse/SR-122
//
// Summary
// =======
//
// This file implements a prototype for a collection model where
// indices can't move themselves forward or backward.  Instead, the
// corresponding collection moves the indices.
//
// Problem
// =======
//
// In practice it has turned out that every one of our concrete
// collection's non random-access indices holds a reference to the
// collection it traverses.  This introduces complexity in
// implementations (especially as we try to avoid multiple-reference
// effects that can cause unnecessary COW copies -- see `Dictionary`
// and `Set`) and presumably translates into less-efficient codegen.
// We should consider other schemes.
//
// Solution
// ========
//
// Change indices so that they can't be moved forward or backward by
// themselves (`i.successor()`).  Then indices can store the minimal
// amount of information about the element position in the collection,
// and avoid keeping a reference to the whole collection.

// Issues
// ======
//
// 1. Conflicting requirements for `MyRange`:
//
// * range bounds need to be comparable and incrementable, in order for
//   `MyRange` to conform to `MyForwardCollectionType`,
//
// * we frequently want to use `MyRange` as a "transport" data type, just
//   to carry a pair of indices around.  Indices are neither comparable nor
//   incrementable.
//
// Possible solution: conditional conformance for `MyRange` to
// `MyForwardCollectionType` when the bounds are comparable and
// incrementable (when the bounds conform to
// `MyRandomAccessCollectionType`?).
//
// 2. We can't specify constraints on associated types.  This forces many
//    trivial algorithms to specify useless constraints.

infix operator  ...* { associativity none precedence 135 }
infix operator  ..<* { associativity none precedence 135 }

public protocol MyGeneratorType {
  associatedtype Element<commit_msg>CollectionsMoveIndices: expand the discussion comment<commit_after>// RUN: %target-run-simple-swift
// REQUIRES: executable_test

// https://bugs.swift.org/browse/SR-122
//
// Summary
// =======
//
// This file implements a prototype for a collection model where
// indices can't move themselves forward or backward.  Instead, the
// corresponding collection moves the indices.
//
// Problem
// =======
//
// Swift standard library defines three kinds of collection indices:
// forward, bidirectional and random access.  A collection uses one of
// these indices based on the capabilities of the backing data
// structure.  For example, a singly-linked list can only have forward
// indices, a tree with parent pointers has bidirectional indices, and
// Array and Deque has random access indices.
//
// It turned out that in practice, every one of the non-random-access
// indices holds a reference to the collection it traverses, or to
// some part of it, to implement `.successor()` and `.predecessor()`.
// This introduces extra complexity in implementations and presumably
// translates into less-efficient code that does reference counting on
// indices.  Indices referencing collections also conflicts with COW
// -- a live index makes a collection non-uniquely referenced, causing
// unnecessary copies (see `Dictionary` and `Set`, that have to use a
// double-indirection trick to avoid these extra copies).  We should
// consider other schemes that don't require these tricks.
//
// Proposed Solution
// =================
//
// Change indices so that they can't be moved forward or backward by
// themselves (`i.successor()` is not allowed).  Then indices can
// store the minimal amount of information only about the element
// position in the collection.  Usually index can be represented as
// one or a couple of integers that encode the "path" in the
// data structure from the root to the element.  In this
// representation, only a collection can move indices (e.g.,
// `c.next(i)`).
//
// Advantages:
// * indices don't need to keep a reference to the collection.
//   - indices are simpler to implement.
//   - indices are not reference-countable, and thus cheaper to
//     handle.
// * the hierarchy of index protocols is removed, and instead we add
//   protocols for forward, bidirectional and random-access
//   collections.  This is closer to how people generally talk about
//   collections.  Writing a generic constraint for bidirectional and
//   random-access collections becomes simpler.
//
// Disadvantages:
// * a value-typed linked list can't conform to CollectionType.  A
//   reference-typed one can.

// Issues
// ======
//
// 1. Conflicting requirements for `MyRange`:
//
// * range bounds need to be comparable and incrementable, in order for
//   `MyRange` to conform to `MyForwardCollectionType`,
//
// * we frequently want to use `MyRange` as a "transport" data type, just
//   to carry a pair of indices around.  Indices are neither comparable nor
//   incrementable.
//
// Possible solution: conditional conformance for `MyRange` to
// `MyForwardCollectionType` when the bounds are comparable and
// incrementable (when the bounds conform to
// `MyRandomAccessCollectionType`?).
//
// 2. We can't specify constraints on associated types.  This forces many
//    trivial algorithms to specify useless constraints.

infix operator  ...* { associativity none precedence 135 }
infix operator  ..<* { associativity none precedence 135 }

public protocol MyGeneratorType {
  associatedtype Element
{'fraction_non_alphanumeric': 0.10313008865569025, 'fraction_numerical': 0.003980459562149448, 'mean_word_length': 3.4473049074818984, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7650111', 'n_tokens_mistral': 1439, 'n_tokens_neox': 1357, 'n_words': 668}