On 30/04/2020 00.24, Matthew Bentley via SG14 wrote:
> current version of colony proposal has a preliminary attempt at formal wording in the Technical Specifications section, if anyone has the time to look at the proposal and respond with feedback I'd appreciate it:
> https://raw.githubusercontent.com/WG21-SG14/SG14/master/Docs/Proposals/D0447R11%20-%20Introduction%20of%20colony%20to%20the%20Standard%20Library.html

I'm only looking at the "Technical Specification", which should be
self-contained, ignoring the rest of the paper.

 - Please suggest stable labels and a location in the standard
where the additional container should go.

 - The standard uses American-style spelling "-ize", e.g. in "amortized".


Overview:

"Storage management is handled automatically and is specifically organised in
multiple blocks of sequential elements, including block metadata."

At least the "including block metadata" is an implementation detail
that shouldn't be in the standard.

 - I think this data structure wants to be better than "*amortized* constant
time" for insert and erase, where the "constant" relates to the number
of elements present in the container.


 - The "Skipfield" template parameter is not specified.
Which restrictions apply? (For example, can it be void,
an array of unknown bound, an abstract base class, a function
type, or a non-copyable class type?)

 - Would it be useful to give the default template argument
for Skipfield a user-visible name? We also use the public
name std::allocator for the default argument of Allocator etc.

 - The following:

using size_type = implementation-defined;
using difference_type = implementation-defined;
using iterator = implementation-defined;
using const_iterator = implementation-defined;

should have cross-references to [container.requirements.general]
(cf. vector).


 - "const size_type min/max_block_capacity"
drop "const"; it's ignored in a non-defining function declaration anyway.

 - Remove space between "operator" and "=".

 - The synopsis should show "assign" member functions near "operator=".

 - "// iterators:"

drop colon


 - " // Since this could be derived from --end() depending on implementation, and that could result in undefined behaviour in a colony with no insertions and unbounded iterators, whether this is noexcept is implementation-defined"

"Since" is rationale that doesn't belong in normative text. Do you want to say
noexcept( see below ) , or what?

Why is "rbegin() const" not so marked? Same question for crbegin().

Why do we need this funny restriction anyway? Can the implementation
specialize reverse_iterator<colony::iterator> to do the right thing and
avoid the undefined behavior for rbegin() with no runtime cost and no
insane code cost? If so, that should be required, not implementation-defined.


 - " // Approximate so as to allow for platform-based constraints and alignment"

Rationale should go into the prose sections of the paper.

 - "// Element memory block capacity limit functions:"

Drop trailing colon.

 - These block capacity functions use a "Skipfield" type (plus redundant const),
but the default arguments in the constructor use size_type. That seems inconsistent.

 - In general, the standard doesn't do "get_" and "set_" prefixes for getting/setting values.
Instead, we have
     name_for_value(x) to set a value
     name_for_value() to retrieve the value

   If you need to return several values, use a struct with nice member names.


 - "// Type-changing functions:"

Drop trailing colon.

 - " // Cannot be noexcept as colony could be empty or pointer invalid"

Rationale doesn't belong into the normative wording. Move it to the prose
section of the paper.

 - Why do we need a separate get_reverse_iterator_from_pointer function?
Can't we just use get_iterator_from_pointer and have the user turn that
into a reverse iterator, if desired?

 - get_index_from_iterator: We use pass-by-value for iterators, in general.
(cf. constructor templates of colony) If the implementation wants to do
pass-by-reference, it can do so, I believe.

 - get_index_from_iterator: Similar to erase, it's enough to allow for
const_iterators; the modifiable iterators can convert implicitly.

 - " // Cannot be noexcept as colony could be empty"

Rationale doesn't belong into the normative wording. Move it to the prose
section of the paper.

 - get_iterator_from_index: Why is this not spelled std::advance(begin(), n) ?
(The implementation can specialize to make it efficient.)

 - similar for get_index_from_iterator; Why can't we use std::distance(begin(), it)
instead?
(We have "Complexity: Same as distance specialized algorithm, see below.", so there
seems to be no benefit.)

 - " // May throw exception if iterators are invalid."

Rationale doesn't belong into the normative wording. Move it to the prose
section of the paper.


ctor p6:

"If n is larger than min_block_capacity, the capacity of the first block created will be the smaller of n or max_block_capacity."

If you want the min/max block capacity to have any normative impact,
you need to establish an actual abstract model you can tie into.
Otherwise, why does the capacity of some block matter at all?

p11
"If iterators are random-access and total number of elements n is calculable from (last - first)"

At first sight, this sounds stupid. "last-first" only works if an iterator is
random-access. (However, library front matter defines "last-first" for any
iterator type.)

Maybe: "If first and last are random-access iterators (xref), let n be last-first; if n is larger..."


capacity p2

 - I think you're referring to old-style constraints, so those should be spelled
Cpp17MoveInsertable etc. And CopyInsertable can go entirely (move will fall back
to copy automatically).

 - Why do we need MoveInsertable for "reserve" anyway? Aren't we just allocating
a new memory block of the desired size, without any moves?

 - And "must" is a forbidden word in technical specifications. Either "shall" or (here) simply "is".

 - And please don't use "Requires", use "Mandates", "Constraints", "Preconditions" as appropriate.

 - p8 "singular" -> "single"

 - " there are no effects." comma in front

 - "Hence the insertion time complexity is amortised."

Rationale doesn't belong into the normative wording. Move it to the prose
section of the paper.

 - In general, creating a new memory block does not factor into the complexity
consideration, which is stated in terms of the number of elements touched.
Unless you're saying that creating a new memory block is somehow creating
elements.

 - "erase" p7 needs similar cleanup.

 - "behaviour": The standard uses US-style spelling.

 - Some "the"s appear to be missing. Example:

"according to supplied comparison function"

 - sort p13
"Complexity: Implementation-defined. One strong strategy involves using the standard library's sort function to sort an array of pointers to colony elements by the value of the elements they point to, and would have std::sort()'s complexity."

This is, of course, idle chatter. If there is a reasonable implementation
strategy that is O(n log n), we should simply require that complexity and be
done with it.

 - splice p15: This wants to talk about elements, not about memory blocks.
You can certainly say that no element copies or moves happen.

 - splice p17:
"Better performance may be gained in some cases by allowing the source blocks to go to the front rather than the back, depending on how full the final block in x's iterative sequence is. This is because unused elements that are not at the back of colony's iterative sequence will need to be marked as skipped, and skipping over large numbers of elements will incur a small performance disadvantage during iteration compared to skipping over a small number of elements, due to memory locality."

You must be kidding me, right? Burn that with fire and move the ashes
to the prose section of the paper.

 - approximate_memory_use p19
"Complexity: Implementation-defined. Should typically be constant."

If there is a reasonable implementation strategy to make this constant, then make it so
in the spec.

 - Why is reinitialize needed? Can't you just do my_colony = colony(min_block_size, max_block_size) ?
Oh, we don't have that constructor, but it seems we should definitely have it.

 - get_iterator_from_pointer p1: "pointer is not invalid" : The name of the parameter is element_pointer
(which is a bit verbose, though, just call it "p"). I think we need a precondition that the pointer
points to an element of *this.

 - In general, I think we need to be more clear which operations invalidate iterators,
and we should do so in an overall introductory paragraph of the normative wording.

 - In general, we should say somewhere that the iteration sequence is unspecified
or say when it changes in unpredictable ways.

 - "it's final destination block" -> "its"

and of course the lengthy explanation of the complexity doesn't belong here. Just say O(n)
or maybe O(max_block_size), and be done with it. (And that would be one of the
places where max_block_size is actually used for something normative.)

Jens