Hi,
I recently started developing a small package for unrolling for-loops at compile-time (https://github.com/schneiderfelipe/unrolled). It is around 110 lines of useful code and works fine in most cases,
var total: int
unroll for i in 1..3:
total += i
# =>
# var total: int
# block:
# total += 1
# block:
# total += 2
# block:
# total += 3
But I'm having a hard time generalizing it to some corner cases. For instance, in order to make it work with array`s, the `unroll now receives a typed parameter (see code here).
But then things suddenly break. Namely, loops containing variable definitions (issue #1) and nested loops (#2) don't work anymore and I have no clue why. Take the following code, for instance,
expandMacros:
var x: int
unroll for i in 1..3:
var j = i + 1
x += j
assert x == (1 + 1) + (2 + 1) + (3 + 1)
First of all, it fails (x is actually 6 when it should be 9). But take a look at the expanded code below (using expandMacros):
var x: int
block:
var j = 2
x += j
block:
var j = 3
x += j
block:
var j = 4
x += j
The output is the same when receiving an untyped parameter, but then the test passes!
As you already realize the issue with the j variable in the unrolled loop is that the "same" value is used in all branches.
This is because the symbols are already being bound in the typed body. Essentially you are using the same j symbol in all branches that is declared in the first block. In hand written code this couldn't happen, but macro magic and it suddenly does.
One way to work around it is to simply convert your AST back to untyped before emitting the final code.
A quickly written toUntyped procedure:
proc toUntyped(n: NimNode): NimNode =
case n.kind
of nnkSym: result = ident(n.strVal)
else:
if n.len == 0: return n
result = newTree(n.kind)
for ch in n:
result.add ch.toUntyped()
which you can just use as the last line in the unroll macro:
result = result.toUntyped
This issue keeps coming up. The macro module really needs something like this.
@Hlaaftana Good idea. And JavaScript gives me a... `9`! Here's the thing, both
$ nim c -d:danger -r unrolled.nim
$ nim cpp -d:danger -r unrolled.nim
give the wrong result (`6`). But JS is fine with it,
nim js -d:danger -r unrolled.nim
produces 9.
(Leaving -d:danger out does not change anything.)
Here's the important part in the JS output:
L1: do {
var x_10670015 = [0];
L2: do {
var j_10670026 = [2];
x_10670015[0] += j_10670026[0];
} while(false);
L3: do {
var j_10670026 = [3];
x_10670015[0] += j_10670026[0];
} while(false);
L4: do {
var j_10670026 = [4];
x_10670015[0] += j_10670026[0];
} while(false);
rawEcho(cstrToNimstr((x_10670015[0])+""));
} while(false);
Seems to be the right thing: only two variables were generated. The complete code is here.
Compare that to the C output:
/* section: NIM_merge_VARS */
// ... some output ...
N_LIB_PRIVATE NI j__oW7Ei9a3JMvM4TX9a7zX9aC8w = ((NI) 2);
// ... some more output ...
tyArray__nHXaesL0DJZHyVS07ARPRA T5_;
{
x__cJwvvv9cqwzBci0Lkoro5zA += j__oW7Ei9a3JMvM4TX9a7zX9aC8w;
}
{
x__cJwvvv9cqwzBci0Lkoro5zA += j__oW7Ei9a3JMvM4TX9a7zX9aC8w;
}
{
x__cJwvvv9cqwzBci0Lkoro5zA += j__oW7Ei9a3JMvM4TX9a7zX9aC8w;
}
nimZeroMem((void*)T5_, sizeof(tyArray__nHXaesL0DJZHyVS07ARPRA));
T5_[0] = nimIntToStr(x__cJwvvv9cqwzBci0Lkoro5zA);
echoBinSafe(T5_, 1);
See the complete C code here.
I compiled everything at the same point in time (commit fae56e3).
Hi @Vindaar, thanks a lot! I'll try this out.
Do you have any idea why this doesn't happen with the JS backend?
Do you have any idea why this doesn't happen with the JS backend?
To be honest no, not really. The two backends are different enough that scoping rules and what kind of code will be generated for what kind of Nim construct makes it hard to say. I'm not too familiar with the JS backend, especially not in terms of macros.
This issue keeps coming up. The macro module really needs something like this.
Except its too difficult to do as a macro, this macro is not enough. There are more things to be "untyped", like varargs calls and more.
You could do something like this:
import macros
macro genTuple(a : static[int]) : untyped =
result = nnkTupleConstr.newTree()
for i in 0..<a:
result.add newLit(i)
if result.len == 0:
result = nnkTupleTy.newTree()
template unroll[T,G](i : untyped, a : static[array[T,G]], body : untyped) : untyped =
for index in fields(genTuple(a.len)):
const
i = a[index]
body
var
x : int
const
xx = [1,2,3]
unroll(i,xx):
var
j = i + 1
x += j
echo x
assert x == (1 + 1) + (2 + 1) + (3 + 1)
You could add an artificial block into the typed code: The result of the t macro will be a stmtList with a series of blocks in it. It will be completely predictable output that you can manipulate. It is advisable to replace all typed generated symbols with new symbols anyway. This could be extended to work on arbitrary for loops as long as the length of the loop is known at compiletime.
import macros
macro genTuple(a, b : static[int]) : untyped =
result = nnkTupleConstr.newTree()
for i in a..b:
result.add newLit(i)
template unroll[T,G](i : untyped, a : array[T,G], body : untyped) : untyped =
for index in fields(genTuple(a.low.int,a.high.int)):
block: #added block
#you can remove it later when you inspect the ast
#and replace any symbols in subsequent loops
const
i = a[typeof(T)(index)]
body
macro t(a : typed) : untyped =
expectKind(a,nnkStmtList)
expectLen(a,1)
expectKind(a[0],nnkStmtList)
var
blocksToInspect : seq[NimNode]
for i in 0..<len(a[0]):
expectKind(a[0][i],nnkBlockStmt)
blocksToInspect.add a[0][i][1]
result = a
var
x : int
const
xx = [1,2,3]
t:
unroll(i,xx):
var
j = i + 1
x += j
echo x
assert x == (1 + 1) + (2 + 1) + (3 + 1)
For that matter if you know the length of the loop at compiletime the resulting code will will be equivalent to
body
for item in call():
body
var
l {.compiletime.} = 0
for item in call():
l += 1
l
Still:
Your ideas are good, but they don't solve the (two) problem(s):
This discrepancy between backends makes me think it is a bug. @Araq
You might be interested in my own unroller: https://github.com/mratsim/constantine/blob/c2d716b0/helpers/static_for.nim
Basically you need to regenerate untyped idents from typed symbols to avoid issues:
import std/macros
proc replaceNodes(ast: NimNode, what: NimNode, by: NimNode): NimNode =
# Replace "what" ident node by "by"
proc inspect(node: NimNode): NimNode =
case node.kind:
of {nnkIdent, nnkSym}:
if node.eqIdent(what):
return by
return node
of nnkEmpty:
return node
of nnkLiterals:
return node
else:
var rTree = node.kind.newTree()
for child in node:
rTree.add inspect(child)
return rTree
result = inspect(ast)
macro staticFor*(idx: untyped{nkIdent}, start, stopEx: static int, body: untyped): untyped =
result = newStmtList()
for i in start ..< stopEx:
result.add nnkBlockStmt.newTree(
ident("unrolledIter_" & $idx & $i),
body.replaceNodes(idx, newLit i)
)