# # # The Nim Compiler # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # # Algorithms for the abstract syntax tree: hash tables, lists # and sets of nodes are supported. Efficiency is important as # the data structures here are used in various places of the compiler. import ast, hashes, intsets, strutils, options, msgs, ropes, idents, rodutils proc hashNode*(p: RootRef): THash proc treeToYaml*(n: PNode, indent: int = 0, maxRecDepth: int = - 1): Rope # Convert a tree into its YAML representation; this is used by the # YAML code generator and it is invaluable for debugging purposes. # If maxRecDepht <> -1 then it won't print the whole graph. proc typeToYaml*(n: PType, indent: int = 0, maxRecDepth: int = - 1): Rope proc symToYaml*(n: PSym, indent: int = 0, maxRecDepth: int = - 1): Rope proc lineInfoToStr*(info: TLineInfo): Rope # ----------------------- node sets: --------------------------------------- proc objectSetContains*(t: TObjectSet, obj: RootRef): bool # returns true whether n is in t proc objectSetIncl*(t: var TObjectSet, obj: RootRef) # include an element n in the table t proc objectSetContainsOrIncl*(t: var TObjectSet, obj: RootRef): bool # more are not needed ... # ----------------------- (key, val)-Hashtables ---------------------------- proc tablePut*(t: var TTable, key, val: RootRef) proc tableGet*(t: TTable, key: RootRef): RootRef type TCmpProc* = proc (key, closure: RootRef): bool {.nimcall.} # true if found proc tableSearch*(t: TTable, key, closure: RootRef, comparator: TCmpProc): RootRef # return val as soon as comparator returns true; if this never happens, # nil is returned # ----------------------- str table ----------------------------------------- proc strTableContains*(t: TStrTable, n: PSym): bool proc strTableAdd*(t: var TStrTable, n: PSym) proc strTableGet*(t: TStrTable, name: PIdent): PSym type TTabIter*{.final.} = object # consider all fields here private h*: THash # current hash proc initTabIter*(ti: var TTabIter, tab: TStrTable): PSym proc nextIter*(ti: var TTabIter, tab: TStrTable): PSym # usage: # var # i: TTabIter # s: PSym # s = InitTabIter(i, table) # while s != nil: # ... # s = NextIter(i, table) # type TIdentIter*{.final.} = object # iterator over all syms with same identifier h*: THash # current hash name*: PIdent proc initIdentIter*(ti: var TIdentIter, tab: TStrTable, s: PIdent): PSym proc nextIdentIter*(ti: var TIdentIter, tab: TStrTable): PSym # these are for debugging only: They are not really deprecated, but I want # the warning so that release versions do not contain debugging statements: proc debug*(n: PSym) {.deprecated.} proc debug*(n: PType) {.deprecated.} proc debug*(n: PNode) {.deprecated.} # --------------------------- ident tables ---------------------------------- proc idTableGet*(t: TIdTable, key: PIdObj): RootRef proc idTableGet*(t: TIdTable, key: int): RootRef proc idTablePut*(t: var TIdTable, key: PIdObj, val: RootRef) proc idTableHasObjectAsKey*(t: TIdTable, key: PIdObj): bool # checks if `t` contains the `key` (compared by the pointer value, not only # `key`'s id) proc idNodeTableGet*(t: TIdNodeTable, key: PIdObj): PNode proc idNodeTablePut*(t: var TIdNodeTable, key: PIdObj, val: PNode) # --------------------------------------------------------------------------- proc getSymFromList*(list: PNode, ident: PIdent, start: int = 0): PSym proc lookupInRecord*(n: PNode, field: PIdent): PSym proc getModule*(s: PSym): PSym proc mustRehash*(length, counter: int): bool proc nextTry*(h, maxHash: THash): THash {.inline.} # ------------- table[int, int] --------------------------------------------- const InvalidKey* = low(int) type TIIPair*{.final.} = object key*, val*: int TIIPairSeq* = seq[TIIPair] TIITable*{.final.} = object # table[int, int] counter*: int data*: TIIPairSeq proc initIiTable*(x: var TIITable) proc iiTableGet*(t: TIITable, key: int): int proc iiTablePut*(t: var TIITable, key, val: int) # implementation proc skipConvAndClosure*(n: PNode): PNode = result = n while true: case result.kind of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64, nkClosure: result = result.sons[0] of nkHiddenStdConv, nkHiddenSubConv, nkConv: result = result.sons[1] else: break proc sameValue*(a, b: PNode): bool = result = false case a.kind of nkCharLit..nkUInt64Lit: if b.kind in {nkCharLit..nkUInt64Lit}: result = a.intVal == b.intVal of nkFloatLit..nkFloat64Lit: if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal == b.floatVal of nkStrLit..nkTripleStrLit: if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal == b.strVal else: # don't raise an internal error for 'nimrod check': #InternalError(a.info, "SameValue") discard proc leValue*(a, b: PNode): bool = # a <= b? result = false case a.kind of nkCharLit..nkUInt32Lit: if b.kind in {nkCharLit..nkUInt32Lit}: result = a.intVal <= b.intVal of nkFloatLit..nkFloat64Lit: if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal <= b.floatVal of nkStrLit.
#
#
#            Nim's Runtime Library
#        (c) Copyright 2020 Nim contributors
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module implements `enumerate` syntactic sugar based on Nim's
## macro system.

import std/private/since
import macros


macro enumerate*(x: ForLoopStmt): untyped {.since: (1, 3).} =
  ## Enumerating iterator for collections.
  ##
  ## It yields `(count, value)` tuples (which must be immediately unpacked).
  ## The default starting count `0` can be manually overridden if needed.
  runnableExamples:
    let a = [10, 20, 30]
    var b: seq[(int, int)]
    for i, x in enumerate(a):
      b.add((i, x))
    assert b == @[(0, 10), (1, 20), (2, 30)]

    let c = "abcd"
    var d: seq[(int, char)]
    for (i, x) in enumerate(97, c):
      d.add((i, x))
    assert d == @[(97, 'a'), (98, 'b'), (99, 'c'), (100, 'd')]

  template genCounter(x): untyped =
    # We strip off the first for loop variable and use it as an integer counter.
    # We must immediately decrement it by one, because it gets incremented before
    # the loop body - to be able to use the final expression in other macros.
    newVarStmt(x, infix(countStart, "-", newLit(1)))

  template genInc(x): untyped =
    newCall(bindSym"inc", x)

  expectKind x, nnkForStmt
  # check if the starting count is specified:
  var countStart = if x[^2].len == 2: newLit(0) else: x[^2][1]
  result = newStmtList()
  var body = x[^1]
  if body.kind != nnkStmtList:
    body = newTree(nnkStmtList, body)
  var newFor = newTree(nnkForStmt)
  if x.len == 3: # single iteration variable
    if x[0].kind == nnkVarTuple: # for (x, y, ...) in iter
      result.add genCounter(x[0][0])
      body.insert(0, genInc(x[0][0]))
      for i in 1 .. x[0].len-2:
        newFor.add x[0][i]
    else:
      error("Missing second for loop variable") # for x in iter
  else: # for x, y, ... in iter
    result.add genCounter(x[0])
    body.insert(0, genInc(x[0]))
    for i in 1 .. x.len-3:
      newFor.add x[i]
  # transform enumerate(X) to 'X'
  newFor.add x[^2][^1]
  newFor.add body
  result.add newFor
  # now wrap the whole macro in a block to create a new scope
  result = newBlockStmt(result)
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-05-25 01:42:32 +0000
ab: TStrTable, s: PIdent): PSym = ti.h = s.h ti.name = s if tab.counter == 0: result = nil else: result = nextIdentIter(ti, tab) proc nextIdentIter(ti: var TIdentIter, tab: TStrTable): PSym = var h = ti.h and high(tab.data) var start = h result = tab.data[h] while result != nil: if result.name.id == ti.name.id: break h = nextTry(h, high(tab.data)) if h == start: result = nil break result = tab.data[h] ti.h = nextTry(h, high(tab.data)) proc nextIdentExcluding*(ti: var TIdentIter, tab: TStrTable, excluding: IntSet): PSym = var h: THash = ti.h and high(tab.data) var start = h result = tab.data[h] while result != nil: if result.name.id == ti.name.id and not contains(excluding, result.id): break h = nextTry(h, high(tab.data)) if h == start: result = nil break result = tab.data[h] ti.h = nextTry(h, high(tab.data)) if result != nil and contains(excluding, result.id): result = nil proc firstIdentExcluding*(ti: var TIdentIter, tab: TStrTable, s: PIdent, excluding: IntSet): PSym = ti.h = s.h ti.name = s if tab.counter == 0: result = nil else: result = nextIdentExcluding(ti, tab, excluding) proc initTabIter(ti: var TTabIter, tab: TStrTable): PSym = ti.h = 0 # we start by zero ... if tab.counter == 0: result = nil # FIX 1: removed endless loop else: result = nextIter(ti, tab) proc nextIter(ti: var TTabIter, tab: TStrTable): PSym = result = nil while (ti.h <= high(tab.data)): result = tab.data[ti.h] inc(ti.h) # ... and increment by one always if result != nil: break iterator items*(tab: TStrTable): PSym = var it: TTabIter var s = initTabIter(it, tab) while s != nil: yield s s = nextIter(it, tab) proc hasEmptySlot(data: TIdPairSeq): bool = for h in countup(0, high(data)): if data[h].key == nil: return true result = false proc idTableRawGet(t: TIdTable, key: int): int = var h: THash h = key and high(t.data) # start with real hash value while t.data[h].key != nil: if t.data[h].key.id == key: return h h = nextTry(h, high(t.data)) result = - 1 proc idTableHasObjectAsKey(t: TIdTable, key: PIdObj): bool = var index = idTableRawGet(t, key.id) if index >= 0: result = t.data[index].key == key else: result = false proc idTableGet(t: TIdTable, key: PIdObj): RootRef = var index = idTableRawGet(t, key.id) if index >= 0: result = t.data[index].val else: result = nil proc idTableGet(t: TIdTable, key: int): RootRef = var index = idTableRawGet(t, key) if index >= 0: result = t.data[index].val else: result = nil iterator pairs*(t: TIdTable): tuple[key: int, value: RootRef] = for i in 0..high(t.data): if t.data[i].key != nil: yield (t.data[i].key.id, t.data[i].val) proc idTableRawInsert(data: var TIdPairSeq, key: PIdObj, val: RootRef) = var h: THash h = key.id and high(data) while data[h].key != nil: assert(data[h].key.id != key.id) h = nextTry(h, high(data)) assert(data[h].key == nil) data[h].key = key data[h].val = val proc idTablePut(t: var TIdTable, key: PIdObj, val: RootRef) = var index: int n: TIdPairSeq index = idTableRawGet(t, key.id) if index >= 0: assert(t.data[index].key != nil) t.data[index].val = val else: if mustRehash(len(t.data), t.counter): newSeq(n, len(t.data) * GrowthFactor) for i in countup(0, high(t.data)): if t.data[i].key != nil: idTableRawInsert(n, t.data[i].key, t.data[i].val) assert(hasEmptySlot(n)) swap(t.data, n) idTableRawInsert(t.data, key, val) inc(t.counter) iterator idTablePairs*(t: TIdTable): tuple[key: PIdObj, val: RootRef] = for i in 0 .. high(t.data): if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val) proc idNodeTableRawGet(t: TIdNodeTable, key: PIdObj): int = var h: THash h = key.id and high(t.data) # start with real hash value while t.data[h].key != nil: if t.data[h].key.id == key.id: return h h = nextTry(h, high(t.data)) result = - 1 proc idNodeTableGet(t: TIdNodeTable, key: PIdObj): PNode = var index: int index = idNodeTableRawGet(t, key) if index >= 0: result = t.data[index].val else: result = nil proc idNodeTableGetLazy*(t: TIdNodeTable, key: PIdObj): PNode = if not isNil(t.data): result = idNodeTableGet(t, key) proc idNodeTableRawInsert(data: var TIdNodePairSeq, key: PIdObj, val: PNode) = var h: THash h = key.id and high(data) while data[h].key != nil: assert(data[h].key.id != key.id) h = nextTry(h, high(data)) assert(data[h].key == nil) data[h].key = key data[h].val = val proc idNodeTablePut(t: var TIdNodeTable, key: PIdObj, val: PNode) = var index = idNodeTableRawGet(t, key) if index >= 0: assert(t.data[index].key != nil) t.data[index].val = val else: if mustRehash(len(t.data), t.counter): var n: TIdNodePairSeq newSeq(n, len(t.data) * GrowthFactor) for i in countup(0, high(t.data)): if t.data[i].key != nil: idNodeTableRawInsert(n, t.data[i].key, t.data[i].val) swap(t.data, n) idNodeTableRawInsert(t.data, key, val) inc(t.counter) proc idNodeTablePutLazy*(t: var TIdNodeTable, key: PIdObj, val: PNode) = if isNil(t.data): initIdNodeTable(t) idNodeTablePut(t, key, val) iterator pairs*(t: TIdNodeTable): tuple[key: PIdObj, val: PNode] = for i in 0 .. high(t.data): if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val) proc initIITable(x: var TIITable) = x.counter = 0 newSeq(x.data, StartSize) for i in countup(0, StartSize - 1): x.data[i].key = InvalidKey proc iiTableRawGet(t: TIITable, key: int): int = var h: THash h = key and high(t.data) # start with real hash value while t.data[h].key != InvalidKey: if t.data[h].key == key: return h h = nextTry(h, high(t.data)) result = -1 proc iiTableGet(t: TIITable, key: int): int = var index = iiTableRawGet(t, key) if index >= 0: result = t.data[index].val else: result = InvalidKey proc iiTableRawInsert(data: var TIIPairSeq, key, val: int) = var h: THash h = key and high(data) while data[h].key != InvalidKey: assert(data[h].key != key) h = nextTry(h, high(data)) assert(data[h].key == InvalidKey) data[h].key = key data[h].val = val proc iiTablePut(t: var TIITable, key, val: int) = var index = iiTableRawGet(t, key) if index >= 0: assert(t.data[index].key != InvalidKey) t.data[index].val = val else: if mustRehash(len(t.data), t.counter): var n: TIIPairSeq newSeq(n, len(t.data) * GrowthFactor) for i in countup(0, high(n)): n[i].key = InvalidKey for i in countup(0, high(t.data)): if t.data[i].key != InvalidKey: iiTableRawInsert(n, t.data[i].key, t.data[i].val) swap(t.data, n) iiTableRawInsert(t.data, key, val) inc(t.counter)