diff options
| -rw-r--r-- | compiler/forloops.nim | 89 | ||||
| -rw-r--r-- | doc/nimc.txt | 2 | ||||
| -rw-r--r-- | doc/tut1.txt | 5 | ||||
| -rw-r--r-- | tests/closure/tfib50.nim | 22 |
4 files changed, 115 insertions, 3 deletions
diff --git a/compiler/forloops.nim b/compiler/forloops.nim new file mode 100644 index 000000000..efe000968 --- /dev/null +++ b/compiler/forloops.nim @@ -0,0 +1,89 @@ +# +# +# The Nim Compiler +# (c) Copyright 2015 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## This module implements for loop detection for better C code generation. + +import ast, astalgo + +const + someCmp = {mEqI, mEqI64, mEqF64, mEqEnum, mEqCh, mEqB, mEqRef, mEqProc, + mEqUntracedRef, mLeI, mLeI64, mLeF64, mLeU, mLeU64, mLeEnum, + mLeCh, mLeB, mLePtr, mLtI, mLtI64, mLtF64, mLtU, mLtU64, mLtEnum, + mLtCh, mLtB, mLtPtr} + +proc isCounter(s: PSym): bool {.inline.} = + s.kind in {skResult, skVar, skLet, skTemp} and + {sfGlobal, sfAddrTaken} * s.flags == {} + +proc isCall(n: PNode): bool {.inline.} = + n.kind in nkCallKinds and n[0].kind == nkSym + +proc fromSystem(op: PSym): bool = sfSystemModule in getModule(op).flags + +proc getCounter(lastStmt: PNode): PSym = + if lastStmt.isCall: + let op = lastStmt.sym + if op.magic in {mDec, mInc} or + ((op.name.s == "+=" or op.name.s == "-=") and op.fromSystem): + if op[1].kind == nkSym and isCounter(op[1].sym): + result = op[1].sym + +proc counterInTree(n, loop: PNode; counter: PSym): bool = + # prune the search tree: within the loop the counter may be used: + if n == loop: return + case n.kind + of nkSym: + if n.sym == counter: return true + of nkVarSection, nkLetSection: + # definitions are fine! + for it in n: + if counterInTree(it.lastSon): return true + else: + for i in 0 .. <safeLen(n): + if counterInTree(n[i], loop, counter): return true + +proc copyExcept(n: PNode, x, dest: PNode) = + if x == n: return + if n.kind in {nkStmtList, nkStmtListExpr}: + for i in 0 .. <n.len: copyExcept(n[i], x, dest) + else: + dest.add n + +type + ForLoop* = object + counter*: PSym + init*, cond*, increment*, body*: PNode + +proc extractForLoop*(loop, fullTree: PNode): ForLoop = + ## returns 'counter == nil' if the while loop 'n' is not a for loop: + assert loop.kind == nkWhileStmt + let cond == loop[0] + + if not cond.isCall: return + if cond[0].sym.magic notin someCmp: return + + var lastStmt = loop[1] + while lastStmt.kind in {nkStmtList, nkStmtListExpr}: + lastStmt = lastStmt.lastSon + + let counter = getCounter(lastStmt) + if counter.isNil or counter.ast.isNil: return + + template `=~`(a, b): expr = a.kind == nkSym and a.sym == b + + if cond[1] =~ counter or cond[2] =~ counter: + # ok, now check 'counter' is not used *after* the loop + if counterInTree(fullTree, loop, counter): return + # ok, success, fill in the fields: + result.counter = counter + result.init = counter.ast + result.cond = cond + result.increment = lastStmt + result.body = newNodeI(nkStmtList, loop[1].info) + copyExcept(loop[1], lastStmt, result.body) diff --git a/doc/nimc.txt b/doc/nimc.txt index 84d596e3c..c5d5dea5a 100644 --- a/doc/nimc.txt +++ b/doc/nimc.txt @@ -569,7 +569,7 @@ language for object types: type StdMap {.importcpp: "std::map", header: "<map>".} [K, V] = object proc `[]=`[K, V](this: var StdMap[K, V]; key: K; val: V) {. - importcpp: "#[#] = #".} + importcpp: "#[#] = #", header: "<map>".} var x: StdMap[cint, cdouble] x[6] = 91.4 diff --git a/doc/tut1.txt b/doc/tut1.txt index b2991ba80..cb5a0c8dd 100644 --- a/doc/tut1.txt +++ b/doc/tut1.txt @@ -749,7 +749,8 @@ Forward declarations -------------------- Every variable, procedure, etc. needs to be declared before it can be used. -(The reason for this is compilation efficiency.) +(The reason for this is that it is non-trivial to do better than that in a +language that supports meta programming as extensively as Nim does.) However, this cannot be done for mutually recursive procedures: .. code-block:: nim @@ -767,7 +768,7 @@ introduced to the compiler before it is completely defined. The syntax for such a forward declaration is simple: just omit the ``=`` and the procedure's body. -Later versions of the language may get rid of the need for forward +Later versions of the language will weaken the requirements for forward declarations. The example also shows that a proc's body can consist of a single expression diff --git a/tests/closure/tfib50.nim b/tests/closure/tfib50.nim new file mode 100644 index 000000000..21a4afa9a --- /dev/null +++ b/tests/closure/tfib50.nim @@ -0,0 +1,22 @@ +discard """ + output: "20365011074" +""" + +import tables + +proc memoize(f: proc (a: int): int): proc (a: int): int = + var previous = initTable[int, int]() + return proc(i: int): int = + if not previous.hasKey i: + previous[i] = f(i) + return previous[i] + +var fib: proc(a: int): int + +fib = memoize(proc (i: int): int = + if i == 0 or i == 1: + return 1 + return fib(i-1) + fib(i-2) +) + +echo fib(50) |