Implemented `mSlice` on the VM allowing `toOpenArray` to work at compile time. (#20586)

* Implemented opcSlice to make 'toOpenArray' work on the VM

* Added nkOpenArray for VM to reduce bodgeness

* Fixed range issues and erraneous comments

* Range check correctly for openArrays in opcLdArr

* Inverted logic for ldArr checking

* vm now supports slicing strings

* Added string tests

* Removed usage of 'nkOpenArray' and redundant operations

* Refactored vmSlice implementation, removing redundant and incorrect code

* Made tuples go throw opcWrObj for field assignment

* All strkinds should be considered for openarrays

4 files changed, 204 insertions, 30 deletions

diff --git a/compiler/vm.nim b/compiler/vm.nim
index a7d65d1a1..a8d256b72 100644
--- a/compiler/vm.nim
+++ b/compiler/vm.nim
@@ -535,6 +535,15 @@ template takeAddress(reg, source) =
   reg.nodeAddr = addr source
   GC_ref source
 
+proc takeCharAddress(c: PCtx, src: PNode, index: BiggestInt, pc: int): TFullReg =
+  let typ = newType(tyPtr, nextTypeId c.idgen, c.module.owner)
+  typ.add getSysType(c.graph, c.debug[pc], tyChar)
+  var node = newNodeIT(nkIntLit, c.debug[pc], typ) # xxx nkPtrLit
+  node.intVal = cast[int](src.strVal[index].addr)
+  node.flags.incl nfIsPtr
+  TFullReg(kind: rkNode, node: node)
+
+
 proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
   var pc = start
   var tos = tos
@@ -668,6 +677,48 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
         else:
           ensureKind(rkNode)
           regs[ra].node = nb
+    of opcSlice:
+      # A bodge, but this takes in `toOpenArray(rb, rc, rc)` and emits
+      # nkTupleConstr(x, y, z) into the `regs[ra]`. These can later be used for calculating the slice we have taken.
+      decodeBC(rkNode)
+      let
+        collection = regs[ra].node
+        leftInd = regs[rb].intVal
+        rightInd = regs[rc].intVal
+
+      proc rangeCheck(left, right: BiggestInt, safeLen: BiggestInt) =
+        if left < 0:
+          stackTrace(c, tos, pc, formatErrorIndexBound(left, safeLen))
+
+        if right > safeLen:
+          stackTrace(c, tos, pc, formatErrorIndexBound(right, safeLen))
+
+      case collection.kind
+      of nkTupleConstr: # slice of a slice
+        let safeLen = collection[2].intVal - collection[1].intVal
+        rangeCheck(leftInd, rightInd, safeLen)
+        let
+          leftInd = leftInd + collection[1].intVal # Slice is from the start of the old
+          rightInd = rightInd + collection[1].intVal
+
+        regs[ra].node = newTree(
+          nkTupleConstr,
+          collection[0],
+          newIntNode(nkIntLit, BiggestInt leftInd),
+          newIntNode(nkIntLit, BiggestInt rightInd)
+        )
+
+      else:
+        let safeLen = safeArrLen(collection) - 1
+        rangeCheck(leftInd, rightInd, safeLen)
+        regs[ra].node = newTree(
+          nkTupleConstr,
+          collection,
+          newIntNode(nkIntLit, BiggestInt leftInd),
+          newIntNode(nkIntLit, BiggestInt rightInd)
+        )
+
+
     of opcLdArr:
       # a = b[c]
       decodeBC(rkNode)
@@ -675,7 +726,24 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
         stackTrace(c, tos, pc, formatErrorIndexBound(regs[rc].intVal, high(int)))
       let idx = regs[rc].intVal.int
       let src = regs[rb].node
-      if src.kind in {nkStrLit..nkTripleStrLit}:
+      case src.kind
+      of nkTupleConstr: # refer to `of opcSlice`
+        let
+          left = src[1].intVal
+          right = src[2].intVal
+          realIndex = left + idx
+        if idx in 0..(right - left):
+          case src[0].kind
+          of nkStrKinds:
+            regs[ra].node =  newIntNode(nkCharLit, ord src[0].strVal[int realIndex])
+          of nkBracket:
+            regs[ra].node = src[0][int realIndex]
+          else:
+            stackTrace(c, tos, pc, "opcLdArr internal error")
+        else:
+          stackTrace(c, tos, pc, formatErrorIndexBound(idx, int right))
+
+      of nkStrLit..nkTripleStrLit:
         if idx <% src.strVal.len:
           regs[ra].node = newNodeI(nkCharLit, c.debug[pc])
           regs[ra].node.intVal = src.strVal[idx].ord
@@ -692,10 +760,27 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
         stackTrace(c, tos, pc, formatErrorIndexBound(regs[rc].intVal, high(int)))
       let idx = regs[rc].intVal.int
       let src = if regs[rb].kind == rkNode: regs[rb].node else: regs[rb].nodeAddr[]
-      if src.kind notin {nkEmpty..nkTripleStrLit} and idx <% src.len:
-        takeAddress regs[ra], src.sons[idx]
+      case src.kind
+      of nkTupleConstr:
+        let
+          left = src[1].intVal
+          right = src[2].intVal
+          realIndex = left + idx
+        if idx in 0..(right - left): # Refer to `opcSlice`
+          case src[0].kind
+          of nkStrKinds:
+            regs[ra] = takeCharAddress(c, src[0], realIndex, pc)
+          of nkBracket:
+            takeAddress regs[ra], src.sons[0].sons[realIndex]
+          else:
+            stackTrace(c, tos, pc, "opcLdArrAddr internal error")
+        else:
+          stackTrace(c, tos, pc, formatErrorIndexBound(idx, int right))
       else:
-        stackTrace(c, tos, pc, formatErrorIndexBound(idx, src.safeLen-1))
+        if src.kind notin {nkEmpty..nkTripleStrLit} and idx <% src.len:
+          takeAddress regs[ra], src.sons[idx]
+        else:
+          stackTrace(c, tos, pc, formatErrorIndexBound(idx, src.safeLen-1))
     of opcLdStrIdx:
       decodeBC(rkInt)
       let idx = regs[rc].intVal.int
@@ -712,13 +797,7 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
       let idx = regs[rc].intVal.int
       let s = regs[rb].node.strVal.addr # or `byaddr`
       if idx <% s[].len:
-         # `makePtrType` not accessible from vm.nim
-        let typ = newType(tyPtr, nextTypeId c.idgen, c.module.owner)
-        typ.add getSysType(c.graph, c.debug[pc], tyChar)
-        let node = newNodeIT(nkIntLit, c.debug[pc], typ) # xxx nkPtrLit
-        node.intVal = cast[int](s[][idx].addr)
-        node.flags.incl nfIsPtr
-        regs[ra].node = node
+        regs[ra] = takeCharAddress(c, regs[rb].node, idx, pc)
       else:
         stackTrace(c, tos, pc, formatErrorIndexBound(idx, s[].len-1))
     of opcWrArr:
@@ -726,7 +805,24 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
       decodeBC(rkNode)
       let idx = regs[rb].intVal.int
       let arr = regs[ra].node
-      if arr.kind in {nkStrLit..nkTripleStrLit}:
+      case arr.kind
+      of nkTupleConstr: # refer to `opcSlice`
+        let
+          src = arr[0]
+          left = arr[1].intVal
+          right = arr[2].intVal
+          realIndex = left + idx
+        if idx in 0..(right - left):
+          case src.kind
+          of nkStrKinds:
+            src.strVal[int(realIndex)] = char(regs[rc].intVal)
+          of nkBracket:
+            src[int(realIndex)] = regs[rc].node
+          else:
+            stackTrace(c, tos, pc, "opcWrArr internal error")
+        else:
+          stackTrace(c, tos, pc, formatErrorIndexBound(idx, int right))
+      of {nkStrLit..nkTripleStrLit}:
         if idx <% arr.strVal.len:
           arr.strVal[idx] = chr(regs[rc].intVal)
         else:
@@ -884,14 +980,21 @@ proc rawExecute(c: PCtx, start: int, tos: PStackFrame): TFullReg =
     of opcLenSeq:
       decodeBImm(rkInt)
       #assert regs[rb].kind == nkBracket
-      let high = (imm and 1) # discard flags
+      let
+        high = (imm and 1) # discard flags
+        node = regs[rb].node
       if (imm and nimNodeFlag) != 0:
         # used by mNLen (NimNode.len)
         regs[ra].intVal = regs[rb].node.safeLen - high
       else:
-        # safeArrLen also return string node len
-        # used when string is passed as openArray in VM
-        regs[ra].intVal = regs[rb].node.safeArrLen - high
+        case node.kind
+        of nkTupleConstr: # refer to `of opcSlice`
+          regs[ra].intVal = node[2].intVal - node[1].intVal + 1 - high
+        else:
+          # safeArrLen also return string node len
+          # used when string is passed as openArray in VM
+          regs[ra].intVal = node.safeArrLen - high
+
     of opcLenStr:
       decodeBImm(rkInt)
       assert regs[rb].kind == rkNode
diff --git a/compiler/vmdef.nim b/compiler/vmdef.nim
index c653501ca..54876f37d 100644
--- a/compiler/vmdef.nim
+++ b/compiler/vmdef.nim
@@ -81,6 +81,7 @@ type
     opcWrStrIdx,
     opcLdStrIdx, # a = b[c]
     opcLdStrIdxAddr,  # a = addr(b[c])
+    opcSlice, # toOpenArray(collection, left, right)
 
     opcAddInt,
     opcAddImmInt,
diff --git a/compiler/vmgen.nim b/compiler/vmgen.nim
index a326428f9..037f9a9fc 100644
--- a/compiler/vmgen.nim
+++ b/compiler/vmgen.nim
@@ -640,9 +640,19 @@ proc genCheckedObjAccessAux(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags
 proc genAsgnPatch(c: PCtx; le: PNode, value: TRegister) =
   case le.kind
   of nkBracketExpr:
-    let dest = c.genx(le[0], {gfNode})
-    let idx = c.genIndex(le[1], le[0].typ)
-    c.gABC(le, opcWrArr, dest, idx, value)
+    let
+      dest = c.genx(le[0], {gfNode})
+      idx = c.genIndex(le[1], le[0].typ)
+      collTyp = le[0].typ.skipTypes(abstractVarRange-{tyTypeDesc})
+
+    case collTyp.kind
+    of tyString, tyCstring:
+      c.gABC(le, opcWrStrIdx, dest, idx, value)
+    of tyTuple:
+      c.gABC(le, opcWrObj, dest, int le[1].intVal, value)
+    else:
+      c.gABC(le, opcWrArr, dest, idx, value)
+
     c.freeTemp(dest)
     c.freeTemp(idx)
   of nkCheckedFieldExpr:
@@ -1054,6 +1064,18 @@ proc genMagic(c: PCtx; n: PNode; dest: var TDest; m: TMagic) =
     of tyString: genUnaryABI(c, n, dest, opcLenStr)
     of tyCstring: genUnaryABI(c, n, dest, opcLenCstring)
     else: doAssert false, $n[1].typ.kind
+  of mSlice:
+    var
+      d = c.genx(n[1])
+      left = c.genIndex(n[2], n[1].typ)
+      right = c.genIndex(n[3], n[1].typ)
+    if dest < 0: dest = c.getTemp(n.typ)
+    c.gABC(n, opcNodeToReg, dest, d)
+    c.gABC(n, opcSlice, dest, left, right)
+    c.freeTemp(left)
+    c.freeTemp(right)
+    c.freeTemp(d)
+
   of mIncl, mExcl:
     unused(c, n, dest)
     var d = c.genx(n[1])
@@ -1179,7 +1201,7 @@ proc genMagic(c: PCtx; n: PNode; dest: var TDest; m: TMagic) =
     var d = c.genx(n[1])
     # XXX use ldNullOpcode() here?
     c.gABx(n, opcLdNull, d, c.genType(n[1].typ))
-    c.gABx(n, opcNodeToReg, d, d)
+    c.gABC(n, opcNodeToReg, d, d)
     c.genAsgnPatch(n[1], d)
   of mDefault, mZeroDefault:
     if dest < 0: dest = c.getTemp(n.typ)
@@ -1507,12 +1529,16 @@ proc preventFalseAlias(c: PCtx; n: PNode; opc: TOpcode;
 proc genAsgn(c: PCtx; le, ri: PNode; requiresCopy: bool) =
   case le.kind
   of nkBracketExpr:
-    let dest = c.genx(le[0], {gfNode})
-    let idx = c.genIndex(le[1], le[0].typ)
-    let tmp = c.genx(ri)
-    if le[0].typ.skipTypes(abstractVarRange-{tyTypeDesc}).kind in {
-        tyString, tyCstring}:
+    let
+      dest = c.genx(le[0], {gfNode})
+      idx = c.genIndex(le[1], le[0].typ)
+      tmp = c.genx(ri)
+      collTyp = le[0].typ.skipTypes(abstractVarRange-{tyTypeDesc})
+    case collTyp.kind
+    of tyString, tyCstring:
       c.preventFalseAlias(le, opcWrStrIdx, dest, idx, tmp)
+    of tyTuple:
+      c.preventFalseAlias(le, opcWrObj, dest, int le[1].intVal, tmp)
     else:
       c.preventFalseAlias(le, opcWrArr, dest, idx, tmp)
     c.freeTemp(tmp)
@@ -1676,9 +1702,7 @@ proc genArrAccessOpcode(c: PCtx; n: PNode; dest: var TDest; opc: TOpcode;
   c.freeTemp(a)
   c.freeTemp(b)
 
-proc genObjAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
-  let a = c.genx(n[0], flags)
-  let b = genField(c, n[1])
+proc genObjAccessAux(c: PCtx; n: PNode; a, b: int, dest: var TDest; flags: TGenFlags) =
   if dest < 0: dest = c.getTemp(n.typ)
   if {gfNodeAddr} * flags != {}:
     c.gABC(n, opcLdObjAddr, dest, a, b)
@@ -1691,6 +1715,11 @@ proc genObjAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
     c.gABC(n, opcLdObj, dest, a, b)
   c.freeTemp(a)
 
+proc genObjAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
+  genObjAccessAux(c, n, c.genx(n[0], flags), genField(c, n[1]), dest, flags)
+
+
+
 proc genCheckedObjAccessAux(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
   internalAssert c.config, n.kind == nkCheckedFieldExpr
   # nkDotExpr to access the requested field
@@ -1758,10 +1787,13 @@ proc genCheckedObjAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
 
 proc genArrAccess(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags) =
   let arrayType = n[0].typ.skipTypes(abstractVarRange-{tyTypeDesc}).kind
-  if arrayType in {tyString, tyCstring}:
+  case arrayType
+  of tyString, tyCstring:
     let opc = if gfNodeAddr in flags: opcLdStrIdxAddr else: opcLdStrIdx
     genArrAccessOpcode(c, n, dest, opc, flags)
-  elif arrayType == tyTypeDesc:
+  of tyTuple:
+    c.genObjAccessAux(n, c.genx(n[0], flags), int n[1].intVal, dest, flags)
+  of tyTypeDesc:
     c.genTypeLit(n.typ, dest)
   else:
     let opc = if gfNodeAddr in flags: opcLdArrAddr else: opcLdArr
diff --git a/tests/vm/topenarrays.nim b/tests/vm/topenarrays.nim
new file mode 100644
index 000000000..4e3bef480
--- /dev/null
+++ b/tests/vm/topenarrays.nim
@@ -0,0 +1,38 @@
+proc mutate(a: var openarray[int]) =
+  var i = 0
+  for x in a.mitems:
+    x = i
+    inc i
+
+proc mutate(a: var openarray[char]) =
+  var i = 1
+  for ch in a.mitems:
+    ch = 'a'
+
+
+static:
+  var a = [10, 20, 30]
+  assert a.toOpenArray(1, 2).len == 2
+
+  mutate(a)
+  assert a.toOpenArray(0, 2) == [0, 1, 2]
+  assert a.toOpenArray(0, 0) == [0]
+  assert a.toOpenArray(1, 2) == [1, 2]
+  assert "Hello".toOpenArray(1, 4) == "ello"
+  var str = "Hello"
+  str.toOpenArray(2, 4).mutate()
+  assert str.toOpenArray(0, 4).len == 5
+  assert str.toOpenArray(0, 0).len == 1
+  assert str.toOpenArray(0, 0).high == 0
+  assert str == "Heaaa"
+  assert str.toOpenArray(0, 4) == "Heaaa"
+
+  var arr: array[3..4, int] = [1, 2]
+  assert arr.toOpenArray(3, 4) == [1, 2]
+  assert arr.toOpenArray(3, 4).len == 2
+  assert arr.toOpenArray(3, 3).high == 0
+
+  assert arr.toOpenArray(3, 4).toOpenArray(0, 0) == [1]
+
+
+