# # # Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # # Garbage Collector # # The basic algorithm is *Deferrent Reference Counting* with cycle detection. # This is achieved by combining a Deutsch-Bobrow garbage collector # together with Christoper's partial mark-sweep garbage collector. # # Special care has been taken to avoid recursion as far as possible to avoid # stack overflows when traversing deep datastructures. It is well-suited # for soft real time applications (like games). {.push profiler:off.} const CycleIncrease = 2 # is a multiplicative increase InitialCycleThreshold = 4*1024*1024 # X MB because cycle checking is slow ZctThreshold = 500 # we collect garbage if the ZCT's size # reaches this threshold # this seems to be a good value withRealTime = defined(useRealtimeGC) when withRealTime and not declared(getTicks): include "system/timers" when defined(memProfiler): proc nimProfile(requestedSize: int) const rcShift = 6 # the reference count is shifted so we can use # the least significat bits for additinal flags: rcAlive = 0b00000 # object is reachable. # color *black* in the original paper rcCycleCandidate = 0b00001 # possible root of a cycle. *purple* rcDecRefApplied = 0b00010 # the first dec-ref phase of the # collector was already applied to this # object. *gray* rcMaybeDead = 0b00011 # this object is a candidate for deletion # during the collect cycles algorithm. # *white*. rcReallyDead = 0b00100 # this is proved to be garbage rcRetiredBuffer = 0b00101 # this is a seq or string buffer that # was replaced by a resize operation. # see growObj for details rcColorMask = TRefCount(0b00111) rcZct = 0b01000 # already added to ZCT rcInCycleRoots = 0b10000 # already buffered as cycle candidate rcHasStackRef = 0b100000 # the object had a stack ref in the last # cycle collection rcMarkBit = rcHasStackRef # this is currently used for leak detection # when traceGC is on rcBufferedAnywhere = rcZct or rcInCycleRoots rcIncrement = 1 shl rcShift # don't touch the color bits const NewObjectsAreCycleRoots = true # the alternative is to use the old strategy of adding cycle roots # in incRef (in the compiler itself, this doesn't change much) IncRefRemovesCandidates = false # this is safe only if we can reliably track the fact that the object # has stack references. This could be easily done by adding another bit # to the refcount field and setting it up in unmarkStackAndRegisters. # The bit must also be set for new objects that are not rc1 and it must be # examined in the decref loop in collectCycles. # XXX: not implemented yet as tests didn't show any improvement from this MarkingSkipsAcyclicObjects = true # Acyclic objects can be safely ignored in the mark and scan phases, # because they cannot contribute to the internal count. # XXX: if we generate specialized `markCyclic` and `markAcyclic` # procs we can further optimize this as there won't be need for any # checks in the code MinimumStackMarking = false # Try to scan only the user stack and ignore the part of the stack # belonging to the GC itself. see setStackTop for further info. # XXX: still has problems in release mode in the compiler itself. # investigate how it affects growObj CollectCyclesStats = false type TWalkOp = enum waPush TFinalizer {.compilerproc.} = proc (self: pointer) {.nimcall.} # A ref type can have a finalizer that is called before the object's # storage is freed. TGcStat {.final, pure.} = object stackScans: int # number of performed stack scans (for statistics) cycleCollections: int # number of performed full collections maxThreshold: int # max threshold that has been set maxStackSize: int # max stack size maxStackCells: int # max stack cells in ``decStack`` cycleTableSize: int # max entries in cycle table maxPause: int64 # max measured GC pause in nanoseconds TGcHeap {.final, pure.} = object # this contains the zero count and # non-zero count table stackBottom: pointer stackTop: pointer cycleThreshold: int zct: TCellSeq # the zero count table decStack: TCellSeq # cells in the stack that are to decref again cycleRoots: TCellSeq tempStack: TCellSeq # temporary stack for recursion elimination freeStack: TCellSeq # objects ready to be freed recGcLock: int # prevent recursion via finalizers; no thread lock cycleRootsTrimIdx: int # Trimming is a light-weight collection of the # cycle roots table that uses a cheap linear scan # to find only possitively dead objects. # One strategy is to perform it only for new objects # allocated between the invocations of collectZCT. # This index indicates the start of the range of # such new objects within the table. when withRealTime: maxPause: TNanos # max allowed pause in nanoseconds; active if > 0 region: TMemRegion # garbage collected region stat: TGcStat var gch* {.rtlThreadVar.}: TGcHeap when not defined(useNimRtl): instantiateForRegion(gch.region) template acquire(gch: TGcHeap) = when hasThreadSupport and hasSharedHeap: AcquireSys(HeapLock) template release(gch: TGcHeap) = when hasThreadSupport and hasSharedHeap: releaseSys(HeapLock) template setColor(c: PCell, color) = c.refcount = (c.refcount and not rcColorMask) or color template color(c: PCell): expr = c.refcount and rcColorMask template isBitDown(c: PCell, bit): expr = (c.refcount and bit) == 0 template isBitUp(c: PCell, bit): expr = (c.refcount and bit) != 0 template setBit(c: PCell, bit): expr = c.refcount = c.refcount or bit template isDead(c: Pcell): expr = c.isBitUp(rcReallyDead) # also covers rcRetiredBuffer template clearBit(c: PCell, bit): expr = c.refcount = c.refcount and (not TRefCount(bit)) when debugGC: var gcCollectionIdx = 0 proc colorStr(c: PCell): cstring = let color = c.color case color of rcAlive: return "alive" of rcMaybeDead: return "maybedead" of rcCycleCandidate: return "candidate" of rcDecRefApplied: return "marked" of rcRetiredBuffer: return "retired" of rcReallyDead: return "dead" else: return "unknown?" proc inCycleRootsStr(c: PCell): cstring = if c.isBitUp(rcInCycleRoots): result = "cycleroot" else: result = "" proc inZctStr(c: PCell): cstring = if c.isBitUp(rcZct): result = "zct" else: result = "" proc writeCell*(msg: CString, c: PCell, force = false) = var kind = -1 if c.typ != nil: kind = ord(c.typ.kind) when trackAllocationSource: c_fprintf(c_stdout, "[GC %d] %s: %p %d rc=%ld %s %s %s from %s(%ld)\n", gcCollectionIdx, msg, c, kind, c.refcount shr rcShift, c.colorStr, c.inCycleRootsStr, c.inZctStr, c.filename, c.line) else: c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld\n", msg, c, kind, c.refcount shr rcShift) proc addZCT(zct: var TCellSeq, c: PCell) {.noinline.} = if c.isBitDown(rcZct): c.setBit rcZct zct.add c template setStackTop(gch) = # This must be called immediately after we enter the GC code # to minimize the size of the scanned stack. The stack consumed # by the GC procs may amount to 200-400 bytes depending on the # build settings and this contributes to false-positives # in the conservative stack marking when MinimumStackMarking: var stackTop {.volatile.}: pointer gch.stackTop = addr(stackTop) template addCycleRoot(cycleRoots: var TCellSeq, c: PCell) = if c.color != rcCycleCandidate: c.setColor rcCycleCandidate # the object may be buffered already. for example, consider: # decref; incref; decref if c.isBitDown(rcInCycleRoots): c.setBit rcInCycleRoots cycleRoots.add c proc cellToUsr(cell: PCell): pointer {.inline.} = # convert object (=pointer to refcount) to pointer to userdata result = cast[pointer](cast[ByteAddress](cell)+%ByteAddress(sizeof(TCell))) proc usrToCell*(usr: pointer): PCell {.inline.} = # convert pointer to userdata to object (=pointer to refcount) result = cast[PCell](cast[ByteAddress](usr)-%ByteAddress(sizeof(TCell))) proc canbeCycleRoot(c: PCell): bool {.inline.} = result = ntfAcyclic notin c.typ.flags proc extGetCellType(c: pointer): PNimType {.compilerproc.} = # used for code generation concerning debugging result = usrToCell(c).typ proc internRefcount(p: pointer): int {.exportc: "getRefcount".} = result = int(usrToCell(p).refcount) shr rcShift # this that has to equals zero, otherwise we have to round up UnitsPerPage: when BitsPerPage mod (sizeof(int)*8) != 0: {.error: "(BitsPerPage mod BitsPerUnit) should be zero!".} # forward declarations: proc collectCT(gch: var TGcHeap) proc isOnStack*(p: pointer): bool {.noinline.} proc forAllChildren(cell: PCell, op: TWalkOp) proc doOperation(p: pointer, op: TWalkOp) proc forAllChildrenAux(dest: pointer, mt: PNimType, op: TWalkOp) # we need the prototype here for debugging purposes proc prepareDealloc(cell: PCell) = if cell.typ.finalizer != nil: # the finalizer could invoke something that # allocates memory; this could trigger a garbage # collection. Since we are already collecting we # prevend recursive entering here by a lock. # XXX: we should set the cell's children to nil! inc(gch.recGcLock) (cast[TFinalizer](cell.typ.finalizer))(cellToUsr(cell)) dec(gch.recGcLock) when traceGC: # traceGC is a special switch to enable extensive debugging type TCellState = enum csAllocated, csFreed var states: array[TCellState, TCellSet] proc traceCell(c: PCell, state: TCellState) = case state of csAllocated: if c in states[csAllocated]: writeCell("attempt to alloc an already allocated cell", c) sysAssert(false, "traceCell 1") excl(states[csFreed], c) # writecell("allocated", c) of csFreed: if c in states[csFreed]: writeCell("attempt to free a cell twice", c) sysAssert(false, "traceCell 2") if c notin states[csAllocated]: writeCell("attempt to free not an allocated cell", c) sysAssert(false, "traceCell 3") excl(states[csAllocated], c) # writecell("freed", c) incl(states[state], c) proc computeCellWeight(c: PCell): int = var x: TCellSet x.init let startLen = gch.tempStack.len c.forAllChildren waPush while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if c in states[csFreed]: continue inc result if c notin x: x.incl c c.forAllChildren waPush template markChildrenRec(cell) = let startLen = gch.tempStack.len cell.forAllChildren waPush let isMarked = cell.isBitUp(rcMarkBit) while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if c in states[csFreed]: continue if c.isBitDown(rcMarkBit): c.setBit rcMarkBit c.forAllChildren waPush if c.isBitUp(rcMarkBit) and not isMarked: writecell("cyclic cell", cell) cprintf "Weight %d\n", cell.computeCellWeight proc writeLeakage(onlyRoots: bool) = if onlyRoots: for c in elements(states[csAllocated]): if c notin states[csFreed]: markChildrenRec(c) var f = 0 var a = 0 for c in elements(states[csAllocated]): inc a if c in states[csFreed]: inc f elif c.isBitDown(rcMarkBit): writeCell("leak", c) cprintf "Weight %d\n", c.computeCellWeight cfprintf(cstdout, "Allocations: %ld; freed: %ld\n", a, f) template gcTrace(cell, state: expr): stmt {.immediate.} = when logGC: writeCell($state, cell) when traceGC: traceCell(cell, state) template WithHeapLock(blk: stmt): stmt = when hasThreadSupport and hasSharedHeap: AcquireSys(HeapLock) blk when hasThreadSupport and hasSharedHeap: ReleaseSys(HeapLock) proc rtlAddCycleRoot(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! WithHeapLock: addCycleRoot(gch.cycleRoots, c) proc rtlAddZCT(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! WithHeapLock: addZCT(gch.zct, c) type TCyclicMode = enum Cyclic, Acyclic, MaybeCyclic TReleaseType = enum AddToZTC FreeImmediately THeapType = enum LocalHeap SharedHeap template `++` (rc: TRefCount, heapType: THeapType): stmt = when heapType == SharedHeap: discard atomicInc(rc, rcIncrement) else: inc rc, rcIncrement template `--`(rc: TRefCount): expr = dec rc, rcIncrement rc <% rcIncrement template `--` (rc: TRefCount, heapType: THeapType): expr = (when heapType == SharedHeap: atomicDec(rc, rcIncrement) <% rcIncrement else: --rc) template doDecRef(cc: PCell, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = var c = cc sysAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") # XXX: move this elesewhere sysAssert(c.refcount >=% rcIncrement, "decRef") if c.refcount--(heapType): # this is the last reference from the heap # add to a zero-count-table that will be matched against stack pointers rtlAddZCT(c) else: when cycleFlag != Acyclic: if cycleFlag == Cyclic or canBeCycleRoot(c): # a cycle may have been broken rtlAddCycleRoot(c) template doIncRef(cc: PCell, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = var c = cc c.refcount++(heapType) when cycleFlag != Acyclic: when NewObjectsAreCycleRoots: if canbeCycleRoot(c): addCycleRoot(gch.cycleRoots, c) elif IncRefRemovesCandidates: c.setColor rcAlive # XXX: this is not really atomic enough! proc nimGCref(p: pointer) {.compilerProc, inline.} = doIncRef(usrToCell(p)) proc nimGCunref(p: pointer) {.compilerProc, inline.} = doDecRef(usrToCell(p)) proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = sysAssert(allocInv(gch.region), "begin nimGCunrefNoCycle") var c = usrToCell(p) sysAssert(isAllocatedPtr(gch.region, c), "nimGCunrefNoCycle: isAllocatedPtr") if c.refcount--(LocalHeap): rtlAddZCT(c) sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 2") sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 5") template doAsgnRef(dest: PPointer, src: pointer, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = sysAssert(not isOnStack(dest), "asgnRef") # BUGFIX: first incRef then decRef! if src != nil: doIncRef(usrToCell(src), heapType, cycleFlag) if dest[] != nil: doDecRef(usrToCell(dest[]), heapType, cycleFlag) dest[] = src proc asgnRef(dest: PPointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc! doAsgnRef(dest, src, LocalHeap, MaybeCyclic) proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc if it is known at compile time that no # cycle is possible. doAsgnRef(dest, src, LocalHeap, Acyclic) proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerProc.} = # unsureAsgnRef updates the reference counters only if dest is not on the # stack. It is used by the code generator if it cannot decide wether a # reference is in the stack or not (this can happen for var parameters). if not isOnStack(dest): if src != nil: doIncRef(usrToCell(src)) # XXX we must detect a shared heap here # better idea may be to just eliminate the need for unsureAsgnRef # # XXX finally use assembler for the stack checking instead! # the test for '!= nil' is correct, but I got tired of the segfaults # resulting from the crappy stack checking: if cast[int](dest[]) >=% PageSize: doDecRef(usrToCell(dest[])) else: # can't be an interior pointer if it's a stack location! sysAssert(interiorAllocatedPtr(gch.region, dest)==nil, "stack loc AND interior pointer") dest[] = src when hasThreadSupport and hasSharedHeap: # shared heap version of the above procs proc asgnRefSh(dest: PPointer, src: pointer) {.compilerProc, inline.} = doAsgnRef(dest, src, SharedHeap, MaybeCyclic) proc asgnRefNoCycleSh(dest: PPointer, src: pointer) {.compilerProc, inline.} = doAsgnRef(dest, src, SharedHeap, Acyclic) proc initGC() = when not defined(useNimRtl): when traceGC: for i in low(TCellState)..high(TCellState): init(states[i]) gch.cycleThreshold = InitialCycleThreshold gch.stat.stackScans = 0 gch.stat.cycleCollections = 0 gch.stat.maxThreshold = 0 gch.stat.maxStackSize = 0 gch.stat.maxStackCells = 0 gch.stat.cycleTableSize = 0 # init the rt init(gch.zct) init(gch.tempStack) init(gch.freeStack) init(gch.cycleRoots) init(gch.decStack) proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: TWalkOp) = var d = cast[ByteAddress](dest) case n.kind of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op) of nkList: for i in 0..n.len-1: # inlined for speed if n.sons[i].kind == nkSlot: if n.sons[i].typ.kind in {tyRef, tyString, tySequence}: doOperation(cast[PPointer](d +% n.sons[i].offset)[], op) else: forAllChildrenAux(cast[pointer](d +% n.sons[i].offset), n.sons[i].typ, op) else: forAllSlotsAux(dest, n.sons[i], op) of nkCase: var m = selectBranch(dest, n) if m != nil: forAllSlotsAux(dest, m, op) of nkNone: sysAssert(false, "forAllSlotsAux") proc forAllChildrenAux(dest: pointer, mt: PNimType, op: TWalkOp) = var d = cast[ByteAddress](dest) if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind of tyRef, tyString, tySequence: # leaf: doOperation(cast[PPointer](d)[], op) of tyObject, tyTuple: forAllSlotsAux(dest, mt.node, op) of tyArray, tyArrayConstr, tyOpenArray: for i in 0..(mt.size div mt.base.size)-1: forAllChildrenAux(cast[pointer](d +% i *% mt.base.size), mt.base, op) else: discard proc forAllChildren(cell: PCell, op: TWalkOp) = sysAssert(cell != nil, "forAllChildren: 1") sysAssert(cell.typ != nil, "forAllChildren: 2") sysAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 3" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.kind of tyRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[ByteAddress](cellToUsr(cell)) var s = cast[PGenericSeq](d) if s != nil: let baseAddr = d +% GenericSeqSize for i in 0..s.len-1: forAllChildrenAux(cast[pointer](baseAddr +% i *% cell.typ.base.size), cell.typ.base, op) else: discard proc addNewObjToZCT(res: PCell, gch: var TGcHeap) {.inline.} = # we check the last 8 entries (cache line) for a slot that could be reused. # In 63% of all cases we succeed here! But we have to optimize the heck # out of this small linear search so that ``newObj`` is not slowed down. # # Slots to try cache hit # 1 32% # 4 59% # 8 63% # 16 66% # all slots 68% var L = gch.zct.len var d = gch.zct.d when true: # loop unrolled for performance: template replaceZctEntry(i: expr) = c = d[i] if c.refcount >=% rcIncrement: c.clearBit(rcZct) d[i] = res return if L > 8: var c: PCell replaceZctEntry(L-1) replaceZctEntry(L-2) replaceZctEntry(L-3) replaceZctEntry(L-4) replaceZctEntry(L-5) replaceZctEntry(L-6) replaceZctEntry(L-7) replaceZctEntry(L-8) add(gch.zct, res) else: d[L] = res inc(gch.zct.len) else: for i in countdown(L-1, max(0, L-8)): var c = d[i] if c.refcount >=% rcIncrement: c.clearBit(rcZct) d[i] = res return add(gch.zct, res) proc rawNewObj(typ: PNimType, size: int, gch: var TGcHeap, rc1 = false): pointer = # generates a new object and sets its reference counter to 0 acquire(gch) sysAssert(allocInv(gch.region), "rawNewObj begin") sysAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") collectCT(gch) sysAssert(allocInv(gch.region), "rawNewObj after collect") var res = cast[PCell](rawAlloc(gch.region, size + sizeof(TCell))) sysAssert(allocInv(gch.region), "rawNewObj after rawAlloc") sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") res.typ = typ when trackAllocationSource and not hasThreadSupport: if framePtr != nil and framePtr.prev != nil and framePtr.prev.prev != nil: res.filename = framePtr.prev.prev.filename res.line = framePtr.prev.prev.line else: res.filename = "nofile" if rc1: res.refcount = rcIncrement # refcount is 1 else: # its refcount is zero, so add it to the ZCT: res.refcount = rcZct addNewObjToZCT(res, gch) if NewObjectsAreCycleRoots and canBeCycleRoot(res): res.setBit(rcInCycleRoots) res.setColor rcCycleCandidate gch.cycleRoots.add res sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") when logGC: writeCell("new cell", res) gcTrace(res, csAllocated) release(gch) result = cellToUsr(res) sysAssert(allocInv(gch.region), "rawNewObj end") {.pop.} proc freeCell(gch: var TGcHeap, c: PCell) = # prepareDealloc(c) gcTrace(c, csFreed) when reallyDealloc: rawDealloc(gch.region, c) else: sysAssert(c.typ != nil, "collectCycles") zeroMem(c, sizeof(TCell)) template eraseAt(cells: var TCellSeq, at: int): stmt = cells.d[at] = cells.d[cells.len - 1] dec cells.len template trimAt(roots: var TCellSeq, at: int): stmt = # This will remove a cycle root candidate during trimming. # a candidate is removed either because it received a refup and # it's no longer a candidate or because it received further refdowns # and now it's dead for sure. let c = roots.d[at] c.clearBit(rcInCycleRoots) roots.eraseAt(at) if c.isBitUp(rcReallyDead) and c.refcount <% rcIncrement: # This case covers both dead objects and retired buffers # That's why we must also check the refcount (it may be # kept possitive by stack references). freeCell(gch, c) proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} = setStackTop(gch) result = rawNewObj(typ, size, gch, false) zeroMem(result, size) when defined(memProfiler): nimProfile(size) proc newObjNoInit(typ: PNimType, size: int): pointer {.compilerRtl.} = setStackTop(gch) result = rawNewObj(typ, size, gch, false) when defined(memProfiler): nimProfile(size) proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} = setStackTop(gch) # `newObj` already uses locks, so no need for them here. let size = addInt(mulInt(len, typ.base.size), GenericSeqSize) result = newObj(typ, size) cast[PGenericSeq](result).len = len cast[PGenericSeq](result).reserved = len proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = setStackTop(gch) result = rawNewObj(typ, size, gch, true) when defined(memProfiler): nimProfile(size) proc newSeqRC1(typ: PNimType, len: int): pointer {.compilerRtl.} = setStackTop(gch) let size = addInt(mulInt(len, typ.base.size), GenericSeqSize) result = newObjRC1(typ, size) cast[PGenericSeq](result).len = len cast[PGenericSeq](result).reserved = len proc growObj(old: pointer, newsize: int, gch: var TGcHeap): pointer = acquire(gch) collectCT(gch) var ol = usrToCell(old) sysAssert(ol.typ != nil, "growObj: 1") sysAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") sysAssert(allocInv(gch.region), "growObj begin") var res = cast[PCell](rawAlloc(gch.region, newsize + sizeof(TCell))) var elemSize = if ol.typ.kind != tyString: ol.typ.base.size else: 1 var oldsize = cast[PGenericSeq](old).len*elemSize + GenericSeqSize # XXX: This should happen outside # call user-defined move code # call user-defined default constructor copyMem(res, ol, oldsize + sizeof(TCell)) zeroMem(cast[pointer](cast[ByteAddress](res)+% oldsize +% sizeof(TCell)), newsize-oldsize) sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "growObj: 3") sysAssert(res.refcount shr rcShift <=% 1, "growObj: 4") when false: if ol.isBitUp(rcZct): var j = gch.zct.len-1 var d = gch.zct.d while j >= 0: if d[j] == ol: d[j] = res break dec(j) if ol.isBitUp(rcInCycleRoots): for i in 0 .. pre { line-height: 125%; } td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; } span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; } td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; } span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; } .highlight .hll { background-color: #ffffcc } .highlight .c { color: #888888 } /* Comment */ .highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */ .highlight .k { color: #008800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
#
#
#        The Nim Installation Generator
#        (c) Copyright 2015 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

const
  haveZipLib = false # zip not in stdlib anymore

when haveZipLib:
  import zipfiles

import
  os, osproc, strutils, parseopt, parsecfg, strtabs, streams, debcreation,
  std / sha1

const
  maxOS = 20 # max number of OSes
  maxCPU = 20 # max number of CPUs
  buildShFile = "build.sh"
  buildBatFile = "build.bat"
  buildBatFile32 = "build32.bat"
  buildBatFile64 = "build64.bat"
  makeFile = "makefile"
  installShFile = "install.sh"
  deinstallShFile = "deinstall.sh"

type
  AppType = enum appConsole, appGUI
  Action = enum
    actionNone,   # action not yet known
    actionCSource # action: create C sources
    actionInno,   # action: create Inno Setup installer
    actionNsis,   # action: create NSIS installer
    actionScripts # action: create install and deinstall scripts
    actionZip,    # action: create zip file
    actionXz,     # action: create xz file
    actionDeb     # action: prepare deb package

  FileCategory = enum
    fcWinBin,     # binaries for Windows
    fcConfig,     # configuration files
    fcData,       # data files
    fcDoc,        # documentation files
    fcLib,        # library files
    fcOther,      # other files; will not be copied on UNIX
    fcWindows,    # files only for Windows
    fcUnix,       # files only for Unix; must be after ``fcWindows``
    fcUnixBin,    # binaries for Unix
    fcDocStart,   # links to documentation for Windows installer
    fcNimble      # nimble package files to copy to /opt/nimble/pkgs/pkg-ver

  ConfigData = object of RootObj
    actions: set[Action]
    cat: array[FileCategory, seq[string]]
    binPaths, authors, oses, cpus, downloads: seq[string]
    cfiles: array[1..maxOS, array[1..maxCPU, seq[string]]]
    platforms: array[1..maxOS, array[1..maxCPU, bool]]
    ccompiler, linker, innosetup, nsisSetup: tuple[path, flags: string]
    name, displayName, version, description, license, infile, outdir: string
    mainfile, libpath: string
    innoSetupFlag, installScript, uninstallScript: bool
    explicitPlatforms: bool
    vars: StringTableRef
    app: AppType
    nimArgs: string
    debOpts: TDebOptions
    nimblePkgName: string

const
  unixDirVars: array[fcConfig..fcLib, string] = [
    "$configdir", "$datadir", "$docdir", "$libdir"
  ]

proc iniConfigData(c: var ConfigData) =
  c.actions = {}
  for i in low(FileCategory)..high(FileCategory): c.cat[i] = @[]
  c.binPaths =