[WIP] nim needs a slice type analag to D's T[] dynamic array

[timotheecour]

[Closing until I flesh out more details]
TODO: maybe move to a repo so other can contribute to proposal

motivation

• efficiency: with slices (aka views), there is less copying being done

use cases

• string manipulation with 0 allocations
• image processing (eg in C++ cv::Mat allows returning sub-matrices of a matrix with 0 allocation)
• FFI: foreign function interface with 0 allocation: slice from input pointer + length

exists in other languages

• eg: in D, they're built in as T[]
• in C++: span
• in python: eg, numpy slices
• Rust call that slice Slices are a view into a block of memory represented as a pointer and a length.
• [CHECKME] Pascal/Oberon/Modula Open Array https://github.com/nim-lang/Nim/issues/7337#issuecomment-373758177

leads to cleaner / leaner / more orthogonal and composable API's

• eg: ospaths.searchExtPos wouldn't be needed with splitExt ; a ton more examples

syntax and semantics

Should follow semantics of D dynamic arrays, cf https://dlang.org/spec/arrays.html ; only difference is that the nim GC is thread-local unlike D's GC

Conceptually, a slice is:

type slice*[T] = object #TODO: slice or Slice? I prefer Capital for types but we have seq[T]...
  pointer: prt T #CHECKME
  length: int # can have a proc `len` that retrieves this `length`

type T = int # for eg
let n = 10
let a = newSlice[T](n) # allocates
assert type(a) is slice[T]
let b = a[3 .. 6] # no allocation
assert b.ptr == a.ptr + 3
assert b.len == 4
b[0] = 100
assert a[3] = 100 # original slice is affected

## create a slice from ptr + len (no allocation)
let b2 = initSlice(b.ptr, b.len) #TODO: not sure what's the best syntax here
assert type(b2) is slice[T]
assert b2 == b # does element-wise comparison

# TODO: show .dup, .array, setting .len, assignment

what about openArray

there's lack of clarity on what openArray is; eg https://github.com/nim-lang/Nim/issues/6528 argues it should be a concept; but others don't, eg:

• forum:seq vs array vs open array

OpenArrays are just a proc parameter type that accept arrays and seqs

• forum:borrowed array slices

I want to keep openArray and turn it into borrowed array slices. The borrowing aspect is hard to achieve with a concept. The better way to do it is to simply patch the stdlib to use a concept where it makes sense

openArray is not the same thing as Slice, it's a concept suitable for interfaces, and most analog to D's random access range trait, see https://dlang.org/library/std/range/primitives/is_random_access_range.html

• not first class citizen, cf ICE's and bugs with openarray #8259 : some issues are fixable but some seem less so, eg: "Error: invalid type: 'openarray[int]' for var"

• can't be defined from arbitrary pointer (eg provided by a C foreign function call)

How to accomodate slice in standard library?

The value of that would be ability to make standard library work regardless of types (otherwise a large number of standard library features may not be available to slices);

Could Nim seq be implemented in terms of slice?

Maybe impossible, because would break too many programs, eg assignment copies for seq, but not slice

Could Nim string be implemented in terms of slice, as in D?

Maybe impossible, because would break too many programs, eg assignment copies for seq, but not slice
Note: lessons learned from D: auto-decoding is bad, and shouldn't be reproduced in Nim

related discussions

• https://github.com/nim-lang/Nim/issues/5753 [RFC] View/slice #5753
• Introduce View[T] type #5957
• https://github.com/nim-lang/Nim/issues/7337
• feature-request pointer size pair, (openArray as value) #5437 feature-request pointer size pair, (openArray as value) feature-request pointer size pair, (openArray as value) #5437
• PR: Introduce View[T] type #5957 Introduce View[T] type Introduce View[T] type #5957

[yglukhov]

Relevant: https://github.com/status-im/nim-ranges/blob/master/ranges/typedranges.nim