memviews.nim

#? strongSpaces
# Copyright (C) 2015, René du R. Sacramento. All rights reserved.
# MIT License. Look at license.txt for more info.


## The ``memviews`` module implements a very thin wrapper around array like
## types in Nim or any contiguous memory region you have a pointer to.
## Currently this means it can only point mutable data on the heap.
## It can be used to make shallow slices of your data, have a uniform interface
## to both seq and string (among other types) and acess C arrays more naturally
## and with optional bounds checking.
##
## Be carefull with the lifetime of the allocations you are viewing into, as
## the view possess only an unmanaged pointer to the data. If the GC collects
## your data, or you explicily deallocate it, this pointer may become invalid
## and undefined behaviour ensues. You may have to use GC_ref() and GC_unref()
## to manually stick the memory around.
##
## The same may happen if the data is reallocated to another point in the
## memory. For example, when a sequence has to grow as a result of ".add()".
## One should abstain to change the original seq in those ways.
## MemViews don't suport growth or add() as it don't owns the data it is
## pointing to. However, you can mutate any point of this memory. There are
## still no read-only MemViews.
##
##
## It is similar to Adrian Veith ``seqslices``, but much simpler, less safe and
## more general.
##
## :Author: René du R. Sacramento
## :Copyright: 2015

import ptrmath, strutils

type
  MemView* {.final, pure, shallow.} [T] = object
    data: ptr T
    len*: int  ## You can access directly to retrive or change the lenght
               ## of a MemView. Be careful as there is no bounds checking
               ## when changing the lenght.
               ## Use the slicing operation for safety.
  
  # Not used (yet?)
  SView* {.final, pure, shallow.} [T] = object # GC safe view
    data: ptr T
    len*: int
    orig: ptr T

  CSView = distinct SView # constant/immutable GC safe view
  # etc... I'm not sure if this type zoo will work.


# I need to redefine those, otherwise I get: Error: invalid argument for 'low'
proc low(s: MemView): int {.inline.} = 0
proc high(s: MemView): int {.inline.} = s.len - 1

template xBoundsCheck(s, i) =
  # Bounds check for the array like acceses.
  when compileOption("boundChecks"):  # d:release should disable this.
    if unlikely(i >= s.len):  # i < s.low is taken care by the Natural parameter
      raise newException(IndexError,
                         "Out of bounds: " & $i & " > " & $(s.len-1))
  discard

proc `[]`*[T](s: MemView[T], i: Natural) : T {.inline.} =
  ## Array like access of element ``i``.
  xBoundsCheck(s, i)
  return s.data[i]

proc `[]`*[T](s: var MemView[T], i: Natural): var T {.inline.} =
  ## Mutable array like access of element ``i``.
  xBoundsCheck(s, i)
  return s.data[i]

proc `[]=`* [T] (s: var MemView[T], i: Natural, val : T) {.inline.} =
  ## Change element ``i`` of the view.
  xBoundsCheck(s, i)
  s.data[i] = val

iterator items*[T](s: MemView[T]): T {.inline.} =
  ## Iterate over all items of a view.
  for i in 0 ..< s.len:
    yield s.data[i]

iterator mitems*[T](s: var MemView[T]): var T {.inline.} =
  ## Iterate over all items of a view and be capable to change them in place.
  for i in 0 ..< s.len:
    yield s.data[i]

iterator pairs*[T](s: MemView[T]): tuple[key: int, val: T] {.inline.} =
  ## Iterate over all (index, item) pairs of a view.
  for i in 0 ..< s.len:
    yield (i, s.data[i])

proc `==`*[T](a, b: MemView[T]): bool {.inline.} =
  ## Compare two views for equality. Two views are equal iff they have the
  ## same lenght and for every position ``i`` on both views it's elements
  ## are equal.
  if a.len != b.len: return false
  for i in 0 ..< a.len:
    if a[i] != b[i]: return false
  return true

template sliceBoundsCheck(data, bounds) =
  when compileOption("boundChecks"):  # d:release disables this.
    if bounds.a < data.low or (data.low + bounds.b) > data.high:
      raise newException(IndexError, "Bounds for view() are out of bounds")
  discard

template viewImpl() =
  sliceBoundsCheck(data, bounds)
  result.data = addr(data[bounds.a])
  result.len = bounds.b - bounds.a + 1

proc view*[T](data: var seq[T], bounds: Slice[int]): MemView[T] {.inline.} =
  ## Creates a view for a part of an seq. It is the equivalent of an slice
  ## but no copies are made.
  ## If the compile option ``boundsCheck`` is on, it checks if the bounds are
  ## whichin the seq bounds here. Views can't be larger than the original
  ## data.
  viewImpl()

proc view*(data: var string, bounds: Slice[int]): MemView[char] {.inline.} =
  ## Creates a view for a part of an string. It is the equivalent of an slice
  ## but no copies are made. Also, there is no guarantee that the view will end
  ## in a `\0`.
  ## If the compile option "boundsCheck" is on, it checks if the bounds are
  ## whichin the string bounds here. Views can't be larger than the original
  ## data.
  viewImpl()

proc view*[T](data: ptr T; len: Positive): MemView[T] {.inline.} =
  ## Constructs a view from a pointer to the first element of a contiguous
  ## memory region and a lenght. Can be used with C pointers for
  ## example.
  ## If you want a slice of the original data, either adjust the
  ## pointer to the starting place or call again view() on the output of
  ## this view().
  result.data = data
  result.len = len

proc view*[T](data: MemView[T], bounds: Slice[int]): MemView[T] {.inline.} =
  ## Creates a view for a part of an array, seq or another view. It is the
  ## equivalent of an slice but no copies are made.
  ## If the compile option ``boundsCheck`` is on, it checks if the bounds are
  ## whichin the original MemView bounds here. Views can't be larger than the
  ## original data.
  sliceBoundsCheck(data, bounds)
  result.data = data.data + bounds.a  # pointer arithmetic
  result.len = bounds.b - bounds.a + 1

template view*(data: var string | var MemView | var seq): expr =
  ## Create a view of the entire seq/string.
  ## It is the equivalent of:
  ## data.view(0 .. data.high)
  data.view(0 .. data.high)

#template view*(data: string | MemView | seq): expr =
#  data.view(0 .. data.high)

proc `[]`*[T](data: MemView[T], bounds: Slice[int]): MemView[T] {.inline.} =
  ## Same as view().
  data.view(bounds)
  
proc `^`[T](x:int; y: MemView[T]): int =
  ## Builtin `roof`:idx: operator that can be used for convenient array access.
  ## ``a[^x]`` is rewritten to ``a[a.len-x]``.
  # FIX-ME: Maybe I need to sprinkle some {.noSideEffects} for the built-in magic
  # to work here?
  y.len-x
  

proc `$`*[T](s: MemView[T]): string =
  ## Gives a string representation of a view as if it was an array.
  if s.len == 0:
    return "[]"
  result = "[" & $s[0]
  for i in 1 .. s.len - 1:
    result &= ", " & $s[i]
  result &= "]"

proc dataPtr*[T](s: MemView[T]): ptr T {.inline.} =
  ## Retrive a pointer to the first element of the data that the view is
  ## accessing.
  result = s.data

proc advance*[T](s: var MemView[T], x: int = 1) {.inline.} =
  ## Advance the base of the seq by ``x`` positions. ``x`` can be negative.
  ## Equivalent to s[x .. ^1] but in-place, unsafe and more efficient.
  ## The lenght of the memview can become 0 or negative after calling this proc.
  s.data += x  # pointer arithmetic
  s.len -= x
  #assert s.len > 0

proc toSeq*[T](s: Memview[T]): seq[T] =
  ## Shallow copy the content in the memview to a new seq.
  result = newSeq(s.len)
  for i, e in s:
    shallowCopy(result[i], e)  # TODO: optimize for types w/o refs

proc toString*(s:MemView[char]): string =
  result = newString(s.len)
  for i, e in s:
    result[i] = e

# proc setLen[T](s: var MemView[T], newLen: int) {.inline.}=
#   ## Change the len of a view. Equivalent to using `len=`.
#   ## Not sure if it is needed.
#   s.len = newLen


## Convenience converters.

#converter toMemView*[T](data: var seq[T]): MemView[T] =
#  data.view(0 .. data.high)

#converter toMemView*(data: var string): MemView[char] =
#  data.view(0 .. data.high)

## Example procs using memviews

template cfor(preLoop, condition, postLoop, body:stmt) {.immediate.} =
  ## C style for loop. It is useful over the normal for when you need to
  ## change the loop counter inside the loop, for example.
  ## To see what exactly it does, look at the source. It is beautifully simple.
  ## Use with #! strongSpaces so you don't need parenthesis around all the arguments.
  ## Use a () around the first argument to transform it in an expression.
  ## For example: (var i = 0; c = 1) or (discard).
  block:
    preLoop
    while condition:
      body
      postLoop

iterator shallowSplit*(s: MemView[char], seps: set[char] = Whitespace): MemView[char] =
  var last = 0
  while last < s.len:
    while s[last] in seps: inc last
    var first = last
    while last < s.len and s[last] notin seps: inc last
    if first <= last - 1:
      yield s[first ..< last]

iterator shallowSplit*[T](s: MemView[T], sep: T ): MemView[T] =
  if s.len > 0:
    cfor (var last = 0), last <= s.len, inc last:
      var first = last
      while last < s.len and s[last] != sep: inc last
      yield s[first, last-1]

iterator shallowSplit*[T](s: MemView[T], sep: MemView[T] ): MemView[T] =
    if s.len > 0:
      cfor (var last = 0), last <= s.len, last += sep.len:
        var first = last
        while last < s.len and s[last ..< sep.len] != sep: inc last
        yield s[first, last-1]




when isMainModule:
  template acesses(test) =
    echo "test: ", test
    echo test[test.low]
    echo test[2]
    echo "last:", test[^1], " space ", test[test.len - 1]

  proc testAcceptance(s: MemView) =
    echo s[1]

  var s = @[1,2,3,4,5,6,7,8,9]
  #import times
  #s.add(int times.getTime()) # trying to force it to be allocated on the heap
  #echo s
  echo repr s
  echo "Now starts the test:"
  var test = s.view
  #GC_fullCollect()
  acesses(test)

  var test2 = test.view(0 .. 3)
  acesses(test2)

  for x in test2.mitems:
    x = 0

  echo test
  #testAcceptance(s)

  var str = ""
  str &= "abcdef"
  var teststr = str.view(1 .. 4)
  GC_fullCollect()
  teststr.acesses()
  #testAcceptance(teststr)

ptrmath.nim

template `+`*[T](p: ptr T, off: int): ptr T =
  cast[ptr type(p[])](cast[ByteAddress](p) +% off * sizeof(p[]))

template `+=`*[T](p: ptr T, off: int) =
  p = p + off

template `++`*[T](p: ptr T) =
  p + 1

proc `+++`*[T](p: var ptr T): ptr T =
  result = p
  ++p

template `-`*[T](p: ptr T, off: int): ptr T =
  cast[ptr type(p[])](cast[ByteAddress](p) -% off * sizeof(p[]))

template `-=`*[T](p: ptr T, off: int) =
  p = p - off

template `[]`*[T](p: ptr T, off: int): T =
  (p + off)[]

template `[]=`*[T](p: ptr T, off: int, val: T) =
  (p + off)[] = val