summary refs log tree commit diff stats
path: root/lib/system/syslocks.nim
blob: b8ed29cfc6208705eaac04d41529c6eadfb5c3aa (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#
#
#            Nimrod's Runtime Library
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## Low level system locks and condition vars.

when defined(Windows):
  type
    THandle = int
    TSysLock {.final, pure.} = object # CRITICAL_SECTION in WinApi
      DebugInfo: pointer
      LockCount: int32
      RecursionCount: int32
      OwningThread: int
      LockSemaphore: int
      Reserved: int32

    TSysCond = THandle
          
  proc initSysLock(L: var TSysLock) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "InitializeCriticalSection".}
    ## Initializes the lock `L`.

  proc tryAcquireSysAux(L: var TSysLock): int32 {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "TryEnterCriticalSection".}
    ## Tries to acquire the lock `L`.
    
  proc tryAcquireSys(L: var TSysLock): bool {.inline.} = 
    result = TryAcquireSysAux(L) != 0'i32

  proc acquireSys(L: var TSysLock) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "EnterCriticalSection".}
    ## Acquires the lock `L`.
    
  proc releaseSys(L: var TSysLock) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "LeaveCriticalSection".}
    ## Releases the lock `L`.

  proc deinitSys(L: var TSysLock) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "DeleteCriticalSection".}

  proc createEvent(lpEventAttributes: pointer, 
                   bManualReset, bInitialState: int32,
                   lpName: cstring): TSysCond {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "CreateEventA".}
  
  proc closeHandle(hObject: THandle) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "CloseHandle".}
  proc waitForSingleObject(hHandle: THandle, dwMilliseconds: int32): int32 {.
    stdcall, dynlib: "kernel32", importc: "WaitForSingleObject", noSideEffect.}

  proc signalSysCond(hEvent: TSysCond) {.stdcall, noSideEffect,
    dynlib: "kernel32", importc: "SetEvent".}
  
  proc initSysCond(cond: var TSysCond) {.inline.} =
    cond = createEvent(nil, 0'i32, 0'i32, nil)
  proc deinitSysCond(cond: var TSysCond) {.inline.} =
    closeHandle(cond)
  proc waitSysCond(cond: var TSysCond, lock: var TSysLock) =
    releaseSys(lock)
    discard waitForSingleObject(cond, -1'i32)
    acquireSys(lock)

  proc waitSysCondWindows(cond: var TSysCond) =
    discard waitForSingleObject(cond, -1'i32)

else:
  type
    TSysLock {.importc: "pthread_mutex_t", pure, final,
               header: "<sys/types.h>".} = object
    TSysCond {.importc: "pthread_cond_t", pure, final,
               header: "<sys/types.h>".} = object

  proc initSysLock(L: var TSysLock, attr: pointer = nil) {.
    importc: "pthread_mutex_init", header: "<pthread.h>", noSideEffect.}

  proc acquireSys(L: var TSysLock) {.noSideEffect,
    importc: "pthread_mutex_lock", header: "<pthread.h>".}
  proc tryAcquireSysAux(L: var TSysLock): cint {.noSideEffect,
    importc: "pthread_mutex_trylock", header: "<pthread.h>".}

  proc tryAcquireSys(L: var TSysLock): bool {.inline.} = 
    result = tryAcquireSysAux(L) == 0'i32

  proc releaseSys(L: var TSysLock) {.noSideEffect,
    importc: "pthread_mutex_unlock", header: "<pthread.h>".}
  proc deinitSys(L: var TSysLock) {.noSideEffect,
    importc: "pthread_mutex_destroy", header: "<pthread.h>".}

  proc initSysCond(cond: var TSysCond, cond_attr: pointer = nil) {.
    importc: "pthread_cond_init", header: "<pthread.h>", noSideEffect.}
  proc waitSysCond(cond: var TSysCond, lock: var TSysLock) {.
    importc: "pthread_cond_wait", header: "<pthread.h>", noSideEffect.}
  proc signalSysCond(cond: var TSysCond) {.
    importc: "pthread_cond_signal", header: "<pthread.h>", noSideEffect.}
  
  proc deinitSysCond(cond: var TSysCond) {.noSideEffect,
    importc: "pthread_cond_destroy", header: "<pthread.h>".}
  
href='#n852'>852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951
#
#
#           The Nimrod Compiler
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

# included from cgen.nim

# ------------------------- Name Mangling --------------------------------

proc mangleField(name: string): string = 
  case name[0]
  of 'a'..'z': 
    result = ""
    add(result, chr(ord(name[0]) - ord('a') + ord('A')))
  of '0'..'9', 'A'..'Z': 
    result = ""
    add(result, name[0])
  else: result = "HEX" & toHex(ord(name[0]), 2)
  for i in countup(1, len(name) - 1): 
    case name[i]
    of 'A'..'Z': 
      add(result, chr(ord(name[i]) - ord('A') + ord('a')))
    of '_': 
      nil
    of 'a'..'z', '0'..'9': 
      add(result, name[i])
    else: 
      add(result, "HEX")
      add(result, toHex(ord(name[i]), 2))

proc mangle(name: string): string = 
  when false:
    case name[0]
    of 'a'..'z': 
      result = ""
      add(result, chr(ord(name[0]) - ord('a') + ord('A')))
    of '0'..'9', 'A'..'Z': 
      result = ""
      add(result, name[0])
    else: result = "HEX" & toHex(ord(name[0]), 2)
  result = ""
  for i in countup(0, len(name) - 1): 
    case name[i]
    of 'A'..'Z': 
      add(result, chr(ord(name[i]) - ord('A') + ord('a')))
    of '_': 
      nil
    of 'a'..'z', '0'..'9': 
      add(result, name[i])
    else: 
      add(result, "HEX")
      add(result, toHex(ord(name[i]), 2))

proc isKeyword(w: PIdent): bool =
  # nimrod and C++ share some keywords
  # it's more efficient to test the whole nimrod keywords range
  case w.id
  of ccgKeywordsLow..ccgKeywordsHigh,
     nimKeywordsLow..nimKeywordsHigh,
     ord(wInline): return true
  else: return false

proc mangleName(s: PSym): PRope = 
  result = s.loc.r
  if result == nil: 
    if gCmd == cmdCompileToLLVM: 
      case s.kind
      of skProc, skMethod, skConverter, skConst: 
        result = toRope("@")
      of skVar, skForVar, skResult, skLet: 
        if sfGlobal in s.flags: result = toRope("@")
        else: result = toRope("%")
      of skTemp, skParam, skType, skEnumField, skModule: 
        result = toRope("%")
      else: InternalError(s.info, "mangleName")
    when oKeepVariableNames:
      let keepOrigName = s.kind in skLocalVars - {skForVar} and 
        {sfFromGeneric, sfGlobal, sfShadowed} * s.flags == {} and
        not isKeyword(s.name)
      # XXX: This is still very experimental
      #
      # Even with all these inefficient checks, the bootstrap
      # time is actually improved. This is probably because so many
      # rope concatenations and are now eliminated.
      #
      # Future notes:
      # sfFromGeneric seems to be needed in order to avoid multiple
      # definitions of certain varialbes generated in transf with
      # names such as:
      # `r`, `res`
      # I need to study where these come from.
      #
      # about sfShadowed:
      # consider the following nimrod code:
      #   var x = 10
      #   block:
      #     var x = something(x)
      # The generated C code will be:
      #   NI x;
      #   x = 10;
      #   {
      #     NI x;
      #     x = something(x); // Oops, x is already shadowed here
      #   }
      # Right now, we work-around by not keeping the original name
      # of the shadowed variable, but we can do better - we can
      # create an alternative reference to it in the outer scope and
      # use that in the inner scope.
      #
      # about isCKeyword:
      # nimrod variable names can be C keywords.
      # We need to avoid such names in the generated code.
      # XXX: Study whether mangleName is called just once per variable.
      # Otherwise, there might be better place to do this.
      #
      # about sfGlobal:
      # This seems to be harder - a top level extern variable from
      # another modules can have the same name as a local one.
      # Maybe we should just implement sfShadowed for them too.
      #
      # about skForVar:
      # These are not properly scoped now - we need to add blocks
      # around for loops in transf
      if keepOrigName:
        result = s.name.s.mangle.toRope
      else:
        app(result, toRope(mangle(s.name.s)))
        app(result, "_")
        app(result, toRope(s.id))
    else:
      app(result, toRope(mangle(s.name.s)))
      app(result, "_")
      app(result, toRope(s.id))
    s.loc.r = result

proc isCompileTimeOnly(t: PType): bool =
  result = t.kind in {tyTypedesc, tyExpr}

proc containsCompileTimeOnly(t: PType): bool =
  if isCompileTimeOnly(t): return true
  if t.sons != nil:
    for i in 0 .. <t.sonsLen:
      if t.sons[i] != nil and isCompileTimeOnly(t.sons[i]):
        return true
  return false

var anonTypeName = toRope"TY"

proc typeName(typ: PType): PRope =
  result = if typ.sym != nil: typ.sym.name.s.mangle.toRope
           else: anonTypeName

proc getTypeName(typ: PType): PRope = 
  if (typ.sym != nil) and ({sfImportc, sfExportc} * typ.sym.flags != {}) and
      (gCmd != cmdCompileToLLVM): 
    result = typ.sym.loc.r
  else:
    if typ.loc.r == nil:
      typ.loc.r = if gCmd != cmdCompileToLLVM: con(typ.typeName, typ.id.toRope)
                  else: con(["%".toRope, typ.typeName, typ.id.toRope])
    result = typ.loc.r
  if result == nil: InternalError("getTypeName: " & $typ.kind)
  
proc mapSetType(typ: PType): TCTypeKind =
  case int(getSize(typ))
  of 1: result = ctInt8
  of 2: result = ctInt16
  of 4: result = ctInt32
  of 8: result = ctInt64
  else: result = ctArray

proc mapType(typ: PType): TCTypeKind = 
  case typ.kind
  of tyNone, tyStmt: result = ctVoid
  of tyBool: result = ctBool
  of tyChar: result = ctChar
  of tySet: result = mapSetType(typ)
  of tyOpenArray, tyArrayConstr, tyArray, tyVarargs: result = ctArray
  of tyObject, tyTuple: result = ctStruct
  of tyGenericBody, tyGenericInst, tyGenericParam, tyDistinct, tyOrdinal,
     tyConst, tyMutable, tyIter, tyTypeDesc:
    result = mapType(lastSon(typ))
  of tyEnum: 
    if firstOrd(typ) < 0: 
      result = ctInt32
    else: 
      case int(getSize(typ))
      of 1: result = ctUInt8
      of 2: result = ctUInt16
      of 4: result = ctInt32
      of 8: result = ctInt64
      else: internalError("mapType")
  of tyRange: result = mapType(typ.sons[0])
  of tyPtr, tyVar, tyRef: 
    var base = skipTypes(typ.sons[0], abstractInst)
    case base.kind
    of tyOpenArray, tyArrayConstr, tyArray, tyVarargs: result = ctArray
    else: result = ctPtr
  of tyPointer: result = ctPtr
  of tySequence: result = ctNimSeq
  of tyProc: result = if typ.callConv != ccClosure: ctProc else: ctStruct
  of tyString: result = ctNimStr
  of tyCString: result = ctCString
  of tyInt..tyUInt64:
    result = TCTypeKind(ord(typ.kind) - ord(tyInt) + ord(ctInt))
  else: InternalError("mapType")
  
proc mapReturnType(typ: PType): TCTypeKind = 
  if skipTypes(typ, abstractInst).kind == tyArray: result = ctPtr
  else: result = mapType(typ)
  
proc getTypeDescAux(m: BModule, typ: PType, check: var TIntSet): PRope
proc needsComplexAssignment(typ: PType): bool = 
  result = containsGarbageCollectedRef(typ)

proc isInvalidReturnType(rettype: PType): bool = 
  # Arrays and sets cannot be returned by a C procedure, because C is
  # such a poor programming language.
  # We exclude records with refs too. This enhances efficiency and
  # is necessary for proper code generation of assignments.
  if rettype == nil: result = true
  else: 
    case mapType(rettype)
    of ctArray: 
      result = not (skipTypes(rettype, abstractInst).kind in
          {tyVar, tyRef, tyPtr})
    of ctStruct: 
      result = needsComplexAssignment(skipTypes(rettype, abstractInst))
    else: result = false
  
const 
  CallingConvToStr: array[TCallingConvention, string] = ["N_NIMCALL", 
    "N_STDCALL", "N_CDECL", "N_SAFECALL", 
    "N_SYSCALL", # this is probably not correct for all platforms,
                 # but one can #define it to what one wants 
    "N_INLINE", "N_NOINLINE", "N_FASTCALL", "N_CLOSURE", "N_NOCONV"]
  CallingConvToStrLLVM: array[TCallingConvention, string] = ["fastcc $1", 
    "stdcall $1", "ccc $1", "safecall $1", "syscall $1", "$1 alwaysinline", 
    "$1 noinline", "fastcc $1", "ccc $1", "$1"]

proc CacheGetType(tab: TIdTable, key: PType): PRope = 
  # returns nil if we need to declare this type
  # since types are now unique via the ``GetUniqueType`` mechanism, this slow
  # linear search is not necessary anymore:
  result = PRope(IdTableGet(tab, key))

proc getTempName(): PRope = 
  result = ropeff("TMP$1", "%TMP$1", [toRope(backendId())])

proc getGlobalTempName(): PRope = 
  result = ropeff("TMP$1", "@TMP$1", [toRope(backendId())])

proc ccgIntroducedPtr(s: PSym): bool = 
  var pt = skipTypes(s.typ, abstractInst)
  assert skResult != s.kind
  if tfByRef in pt.flags: return true
  elif tfByCopy in pt.flags: return false
  case pt.Kind
  of tyObject:
    if (optByRef in s.options) or (getSize(pt) > platform.floatSize * 2): 
      result = true           # requested anyway
    elif (tfFinal in pt.flags) and (pt.sons[0] == nil): 
      result = false          # no need, because no subtyping possible
    else: 
      result = true           # ordinary objects are always passed by reference,
                              # otherwise casting doesn't work
  of tyTuple: 
    result = (getSize(pt) > platform.floatSize*2) or (optByRef in s.options)
  else: result = false
  
proc fillResult(param: PSym) = 
  fillLoc(param.loc, locParam, param.typ, ropeff("Result", "%Result", []), 
          OnStack)
  if (mapReturnType(param.typ) != ctArray) and IsInvalidReturnType(param.typ): 
    incl(param.loc.flags, lfIndirect)
    param.loc.s = OnUnknown

proc getParamTypeDesc(m: BModule, t: PType, check: var TIntSet): PRope =
  when false:
    if t.Kind in {tyRef, tyPtr, tyVar}:
      var b = skipTypes(t.sons[0], abstractInst)
      if b.kind == tySet and mapSetType(b) == ctArray:
        return getTypeDescAux(m, b, check)
  result = getTypeDescAux(m, t, check)

proc genProcParams(m: BModule, t: PType, rettype, params: var PRope, 
                   check: var TIntSet, declareEnvironment=true) = 
  params = nil
  if (t.sons[0] == nil) or isInvalidReturnType(t.sons[0]): 
    rettype = toRope("void")
  else: 
    rettype = getTypeDescAux(m, t.sons[0], check)
  for i in countup(1, sonsLen(t.n) - 1): 
    if t.n.sons[i].kind != nkSym: InternalError(t.n.info, "genProcParams")
    var param = t.n.sons[i].sym
    if isCompileTimeOnly(param.typ): continue
    if params != nil: app(params, ", ")
    fillLoc(param.loc, locParam, param.typ, mangleName(param), OnStack)
    app(params, getParamTypeDesc(m, param.typ, check))
    if ccgIntroducedPtr(param): 
      app(params, "*")
      incl(param.loc.flags, lfIndirect)
      param.loc.s = OnUnknown
    app(params, " ")
    app(params, param.loc.r)
    # declare the len field for open arrays:
    var arr = param.typ
    if arr.kind == tyVar: arr = arr.sons[0]
    var j = 0
    while arr.Kind in {tyOpenArray, tyVarargs}:
      # this fixes the 'sort' bug:
      if param.typ.kind == tyVar: param.loc.s = OnUnknown
      # need to pass hidden parameter:
      appff(params, ", NI $1Len$2", ", @NI $1Len$2", [param.loc.r, j.toRope])
      inc(j)
      arr = arr.sons[0]
  if (t.sons[0] != nil) and isInvalidReturnType(t.sons[0]): 
    var arr = t.sons[0]
    if params != nil: app(params, ", ")
    app(params, getTypeDescAux(m, arr, check))
    if (mapReturnType(t.sons[0]) != ctArray) or (gCmd == cmdCompileToLLVM): 
      app(params, "*")
    appff(params, " Result", " @Result", [])
  if t.callConv == ccClosure and declareEnvironment: 
    if params != nil: app(params, ", ")
    app(params, "void* ClEnv")
  if tfVarargs in t.flags: 
    if params != nil: app(params, ", ")
    app(params, "...")
  if params == nil and gCmd != cmdCompileToLLVM: app(params, "void)")
  else: app(params, ")")
  params = con("(", params)

proc isImportedType(t: PType): bool = 
  result = (t.sym != nil) and (sfImportc in t.sym.flags)

proc typeNameOrLiteral(t: PType, literal: string): PRope = 
  if (t.sym != nil) and (sfImportc in t.sym.flags) and (t.sym.magic == mNone): 
    result = getTypeName(t)
  else: 
    result = toRope(literal)
  
proc getSimpleTypeDesc(m: BModule, typ: PType): PRope = 
  const 
    NumericalTypeToStr: array[tyInt..tyUInt64, string] = [
      "NI", "NI8", "NI16", "NI32", "NI64",
      "NF", "NF32", "NF64", "NF128",
      "NU", "NU8", "NU16", "NU32", "NU64",]
  case typ.Kind
  of tyPointer: 
    result = typeNameOrLiteral(typ, "void*")
  of tyEnum: 
    if firstOrd(typ) < 0: 
      result = typeNameOrLiteral(typ, "NI32")
    else: 
      case int(getSize(typ))
      of 1: result = typeNameOrLiteral(typ, "NU8")
      of 2: result = typeNameOrLiteral(typ, "NU16")
      of 4: result = typeNameOrLiteral(typ, "NI32")
      of 8: result = typeNameOrLiteral(typ, "NI64")
      else: 
        internalError(typ.sym.info, "getSimpleTypeDesc: " & $(getSize(typ)))
        result = nil
  of tyString: 
    discard cgsym(m, "NimStringDesc")
    result = typeNameOrLiteral(typ, "NimStringDesc*")
  of tyCstring: result = typeNameOrLiteral(typ, "NCSTRING")
  of tyBool: result = typeNameOrLiteral(typ, "NIM_BOOL")
  of tyChar: result = typeNameOrLiteral(typ, "NIM_CHAR")
  of tyNil: result = typeNameOrLiteral(typ, "0")
  of tyInt..tyUInt64: 
    result = typeNameOrLiteral(typ, NumericalTypeToStr[typ.Kind])
  of tyRange: result = getSimpleTypeDesc(m, typ.sons[0])
  else: result = nil
  
proc getTypePre(m: BModule, typ: PType): PRope = 
  if typ == nil: result = toRope("void")
  else: 
    result = getSimpleTypeDesc(m, typ)
    if result == nil: result = CacheGetType(m.typeCache, typ)
  
proc getForwardStructFormat(): string = 
  if gCmd == cmdCompileToCpp: result = "struct $1;$n"
  else: result = "typedef struct $1 $1;$n"
  
proc getTypeForward(m: BModule, typ: PType): PRope = 
  result = CacheGetType(m.forwTypeCache, typ)
  if result != nil: return 
  result = getTypePre(m, typ)
  if result != nil: return 
  case typ.kind
  of tySequence, tyTuple, tyObject: 
    result = getTypeName(typ)
    if not isImportedType(typ): 
      appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
    IdTablePut(m.forwTypeCache, typ, result)
  else: InternalError("getTypeForward(" & $typ.kind & ')')
  
proc mangleRecFieldName(field: PSym, rectype: PType): PRope = 
  if (rectype.sym != nil) and
      ({sfImportc, sfExportc} * rectype.sym.flags != {}): 
    result = field.loc.r
  else:
    result = toRope(mangleField(field.name.s))
  if result == nil: InternalError(field.info, "mangleRecFieldName")
  
proc genRecordFieldsAux(m: BModule, n: PNode, 
                        accessExpr: PRope, rectype: PType, 
                        check: var TIntSet): PRope = 
  var 
    ae, uname, sname, a: PRope
    k: PNode
    field: PSym
  result = nil
  case n.kind
  of nkRecList: 
    for i in countup(0, sonsLen(n) - 1): 
      app(result, genRecordFieldsAux(m, n.sons[i], accessExpr, rectype, check))
  of nkRecCase: 
    if (n.sons[0].kind != nkSym): InternalError(n.info, "genRecordFieldsAux")
    app(result, genRecordFieldsAux(m, n.sons[0], accessExpr, rectype, check))
    uname = toRope(mangle(n.sons[0].sym.name.s) & 'U')
    if accessExpr != nil: ae = ropef("$1.$2", [accessExpr, uname])
    else: ae = uname
    app(result, "union {" & tnl)
    for i in countup(1, sonsLen(n) - 1): 
      case n.sons[i].kind
      of nkOfBranch, nkElse: 
        k = lastSon(n.sons[i])
        if k.kind != nkSym: 
          sname = con("S", toRope(i))
          a = genRecordFieldsAux(m, k, ropef("$1.$2", [ae, sname]), rectype, 
                                 check)
          if a != nil: 
            app(result, "struct {")
            app(result, a)
            appf(result, "} $1;$n", [sname])
        else: 
          app(result, genRecordFieldsAux(m, k, ae, rectype, check))
      else: internalError("genRecordFieldsAux(record case branch)")
    appf(result, "} $1;$n", [uname])
  of nkSym: 
    field = n.sym
    #assert(field.ast == nil)
    sname = mangleRecFieldName(field, rectype)
    if accessExpr != nil: ae = ropef("$1.$2", [accessExpr, sname])
    else: ae = sname
    fillLoc(field.loc, locField, field.typ, ae, OnUnknown)
    appf(result, "$1 $2;$n", [getTypeDescAux(m, field.loc.t, check), sname])
  else: internalError(n.info, "genRecordFieldsAux()")
  
proc getRecordFields(m: BModule, typ: PType, check: var TIntSet): PRope = 
  result = genRecordFieldsAux(m, typ.n, nil, typ, check)

proc getRecordDesc(m: BModule, typ: PType, name: PRope, 
                   check: var TIntSet): PRope = 
  # declare the record:
  var hasField = false
  if typ.kind == tyObject: 
    if typ.sons[0] == nil: 
      if (typ.sym != nil and sfPure in typ.sym.flags) or tfFinal in typ.flags: 
        result = ropecg(m, "struct $1 {$n", [name])
      else: 
        result = ropecg(m, "struct $1 {$n#TNimType* m_type;$n", [name])
        hasField = true
    elif gCmd == cmdCompileToCpp: 
      result = ropecg(m, "struct $1 : public $2 {$n", 
                      [name, getTypeDescAux(m, typ.sons[0], check)])
      hasField = true
    else: 
      result = ropecg(m, "struct $1 {$n  $2 Sup;$n", 
                      [name, getTypeDescAux(m, typ.sons[0], check)])
      hasField = true
  else: 
    result = ropef("struct $1 {$n", [name])
  var desc = getRecordFields(m, typ, check)
  if (desc == nil) and not hasField: 
    appf(result, "char dummy;$n", [])
  else: 
    app(result, desc)
  app(result, "};" & tnl)

proc getTupleDesc(m: BModule, typ: PType, name: PRope, 
                  check: var TIntSet): PRope = 
  result = ropef("struct $1 {$n", [name])
  var desc: PRope = nil
  for i in countup(0, sonsLen(typ) - 1): 
    appf(desc, "$1 Field$2;$n", 
         [getTypeDescAux(m, typ.sons[i], check), toRope(i)])
  if (desc == nil): app(result, "char dummy;" & tnl)
  else: app(result, desc)
  app(result, "};" & tnl)

proc pushType(m: BModule, typ: PType) = 
  add(m.typeStack, typ)

proc getTypeDescAux(m: BModule, typ: PType, check: var TIntSet): PRope = 
  # returns only the type's name
  var 
    name, rettype, desc, recdesc: PRope
    n: biggestInt
    t, et: PType
  t = getUniqueType(typ)
  if t == nil: InternalError("getTypeDescAux: t == nil")
  if t.sym != nil: useHeader(m, t.sym)
  result = getTypePre(m, t)
  if result != nil: return 
  if ContainsOrIncl(check, t.id): 
    InternalError("cannot generate C type for: " & typeToString(typ)) 
    # XXX: this BUG is hard to fix -> we need to introduce helper structs,
    # but determining when this needs to be done is hard. We should split
    # C type generation into an analysis and a code generation phase somehow.
  case t.Kind
  of tyRef, tyPtr, tyVar: 
    et = getUniqueType(t.sons[0])
    if et.kind in {tyArrayConstr, tyArray, tyOpenArray, tyVarargs}: 
      # this is correct! sets have no proper base type, so we treat
      # ``var set[char]`` in `getParamTypeDesc`
      et = getUniqueType(elemType(et))
    case et.Kind
    of tyObject, tyTuple: 
      # no restriction! We have a forward declaration for structs
      name = getTypeForward(m, et)
      result = con(name, "*")
      IdTablePut(m.typeCache, t, result)
      pushType(m, et)
    of tySequence: 
      # no restriction! We have a forward declaration for structs
      name = getTypeForward(m, et)
      result = con(name, "**")
      IdTablePut(m.typeCache, t, result)
      pushType(m, et)
    else: 
      # else we have a strong dependency  :-(
      result = con(getTypeDescAux(m, et, check), "*")
      IdTablePut(m.typeCache, t, result)
  of tyOpenArray, tyVarargs: 
    et = getUniqueType(t.sons[0])
    result = con(getTypeDescAux(m, et, check), "*")
    IdTablePut(m.typeCache, t, result)
  of tyProc: 
    result = getTypeName(t)
    IdTablePut(m.typeCache, t, result)
    genProcParams(m, t, rettype, desc, check)
    if not isImportedType(t): 
      if t.callConv != ccClosure: # procedure vars may need a closure!
        appf(m.s[cfsTypes], "typedef $1_PTR($2, $3) $4;$n", 
             [toRope(CallingConvToStr[t.callConv]), rettype, result, desc])
      else:
        appf(m.s[cfsTypes], "typedef struct {$n" &
            "N_NIMCALL_PTR($2, ClPrc) $3;$n" & 
            "void* ClEnv;$n} $1;$n",
             [result, rettype, desc])
  of tySequence: 
    # we cannot use getTypeForward here because then t would be associated
    # with the name of the struct, not with the pointer to the struct:
    result = CacheGetType(m.forwTypeCache, t)
    if result == nil: 
      result = getTypeName(t)
      if not isImportedType(t): 
        appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
      IdTablePut(m.forwTypeCache, t, result)
    assert(CacheGetType(m.typeCache, t) == nil)
    IdTablePut(m.typeCache, t, con(result, "*"))
    if not isImportedType(t): 
      if skipTypes(t.sons[0], abstractInst).kind != tyEmpty: 
        const
          cppSeq = "struct $2 : #TGenericSeq {$n"
          cSeq = "struct $2 {$n" &
                 "  #TGenericSeq Sup;$n"
        appcg(m, m.s[cfsSeqTypes],
            (if gCmd == cmdCompileToCpp: cppSeq else: cSeq) &
            "  $1 data[SEQ_DECL_SIZE];$n" & 
            "};$n", [getTypeDescAux(m, t.sons[0], check), result])
      else: 
        result = toRope("TGenericSeq")
    app(result, "*")
  of tyArrayConstr, tyArray: 
    n = lengthOrd(t)
    if n <= 0: 
      n = 1                   # make an array of at least one element
    result = getTypeName(t)
    IdTablePut(m.typeCache, t, result)
    if not isImportedType(t): 
      appf(m.s[cfsTypes], "typedef $1 $2[$3];$n", 
           [getTypeDescAux(m, t.sons[1], check), result, ToRope(n)])
  of tyObject, tyTuple: 
    result = CacheGetType(m.forwTypeCache, t)
    if result == nil: 
      result = getTypeName(t)
      if not isImportedType(t): 
        appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
      IdTablePut(m.forwTypeCache, t, result)
    IdTablePut(m.typeCache, t, result) # always call for sideeffects:
    if t.kind != tyTuple: recdesc = getRecordDesc(m, t, result, check)
    else: recdesc = getTupleDesc(m, t, result, check)
    if not isImportedType(t): app(m.s[cfsTypes], recdesc)
  of tySet: 
    case int(getSize(t))
    of 1: result = toRope("NU8")
    of 2: result = toRope("NU16")
    of 4: result = toRope("NU32")
    of 8: result = toRope("NU64")
    else: 
      result = getTypeName(t)
      IdTablePut(m.typeCache, t, result)
      if not isImportedType(t): 
        appf(m.s[cfsTypes], "typedef NU8 $1[$2];$n", 
             [result, toRope(getSize(t))])
  of tyGenericInst, tyDistinct, tyOrdinal, tyConst, tyMutable, 
      tyIter, tyTypeDesc:
    result = getTypeDescAux(m, lastSon(t), check)
  else:
    InternalError("getTypeDescAux(" & $t.kind & ')')
    result = nil
  # fixes bug #145:
  excl(check, t.id)

proc getTypeDesc(m: BModule, typ: PType): PRope = 
  var check = initIntSet()
  result = getTypeDescAux(m, typ, check)

type
  TClosureTypeKind = enum
    clHalf, clHalfWithEnv, clFull

proc getClosureType(m: BModule, t: PType, kind: TClosureTypeKind): PRope =
  assert t.kind == tyProc
  var check = initIntSet()
  result = getTempName()
  var rettype, desc: PRope
  genProcParams(m, t, rettype, desc, check, declareEnvironment=kind != clHalf)
  if not isImportedType(t):
    if t.callConv != ccClosure or kind != clFull:
      appf(m.s[cfsTypes], "typedef $1_PTR($2, $3) $4;$n", 
           [toRope(CallingConvToStr[t.callConv]), rettype, result, desc])
    else:
      appf(m.s[cfsTypes], "typedef struct {$n" &
          "N_NIMCALL_PTR($2, ClPrc) $3;$n" & 
          "void* ClEnv;$n} $1;$n",
           [result, rettype, desc])

proc getTypeDesc(m: BModule, magic: string): PRope = 
  var sym = magicsys.getCompilerProc(magic)
  if sym != nil: 
    result = getTypeDesc(m, sym.typ)
  else: 
    rawMessage(errSystemNeeds, magic)
    result = nil

proc finishTypeDescriptions(m: BModule) = 
  var i = 0
  while i < len(m.typeStack): 
    discard getTypeDesc(m, m.typeStack[i])
    inc(i)
  
proc genProcHeader(m: BModule, prc: PSym): PRope = 
  var 
    rettype, params: PRope
  genCLineDir(result, prc.info)
  # using static is needed for inline procs
  if gCmd != cmdCompileToLLVM and lfExportLib in prc.loc.flags:
    if m.isHeaderFile:
      result.app "N_LIB_IMPORT "
    else:
      result.app "N_LIB_EXPORT "
  elif prc.typ.callConv == ccInline:
    result.app "static "
  var check = initIntSet()
  fillLoc(prc.loc, locProc, prc.typ, mangleName(prc), OnUnknown)
  genProcParams(m, prc.typ, rettype, params, check)
  # careful here! don't access ``prc.ast`` as that could reload large parts of
  # the object graph!
  appf(result, "$1($2, $3)$4", 
       [toRope(CallingConvToStr[prc.typ.callConv]), rettype, prc.loc.r, params])

# ------------------ type info generation -------------------------------------

proc genTypeInfo(m: BModule, typ: PType): PRope
proc getNimNode(m: BModule): PRope = 
  result = ropef("$1[$2]", [m.typeNodesName, toRope(m.typeNodes)])
  inc(m.typeNodes)

when false:
  proc getNimType(m: BModule): PRope = 
    result = ropef("$1[$2]", [m.nimTypesName, toRope(m.nimTypes)])
    inc(m.nimTypes)

  proc allocMemTI(m: BModule, typ: PType, name: PRope) = 
    var tmp = getNimType(m)
    appf(m.s[cfsTypeInit2], "$2 = &$1;$n", [tmp, name])

proc genTypeInfoAuxBase(m: BModule, typ: PType, name, base: PRope) = 
  var nimtypeKind: int
  #allocMemTI(m, typ, name)
  if (typ.kind == tyObject) and (tfFinal in typ.flags) and
      (typ.sons[0] == nil): 
    nimtypeKind = ord(tyPureObject)
  else:
    nimtypeKind = ord(typ.kind)
  
  var size: PRope
  if tfIncompleteStruct in typ.flags: size = toRope"void*"
  else: size = getTypeDesc(m, typ)
  appf(m.s[cfsTypeInit3], 
       "$1.size = sizeof($2);$n" & "$1.kind = $3;$n" & "$1.base = $4;$n", 
       [name, size, toRope(nimtypeKind), base])
  # compute type flags for GC optimization
  var flags = 0
  if not containsGarbageCollectedRef(typ): flags = flags or 1
  if not canFormAcycle(typ): flags = flags or 2        
  #else MessageOut("can contain a cycle: " & typeToString(typ))
  if flags != 0: 
    appf(m.s[cfsTypeInit3], "$1.flags = $2;$n", [name, toRope(flags)])
  discard cgsym(m, "TNimType")
  appf(m.s[cfsVars], "TNimType $1; /* $2 */$n", 
       [name, toRope(typeToString(typ))])

proc genTypeInfoAux(m: BModule, typ: PType, name: PRope) = 
  var base: PRope
  if (sonsLen(typ) > 0) and (typ.sons[0] != nil): 
    base = genTypeInfo(m, typ.sons[0])
  else: 
    base = toRope("0")
  genTypeInfoAuxBase(m, typ, name, base)

proc discriminatorTableName(m: BModule, objtype: PType, d: PSym): PRope = 
  # bugfix: we need to search the type that contains the discriminator:
  var objtype = objtype
  while lookupInRecord(objtype.n, d.name) == nil:
    objtype = objtype.sons[0]
  if objType.sym == nil: 
    InternalError(d.info, "anonymous obj with discriminator")
  result = ropef("NimDT_$1_$2", [
    toRope(objType.sym.name.s), toRope(d.name.s)])

proc discriminatorTableDecl(m: BModule, objtype: PType, d: PSym): PRope = 
  discard cgsym(m, "TNimNode")
  var tmp = discriminatorTableName(m, objtype, d)
  result = ropef("TNimNode* $1[$2];$n", [tmp, toRope(lengthOrd(d.typ)+1)])

proc genObjectFields(m: BModule, typ: PType, n: PNode, expr: PRope) = 
  case n.kind
  of nkRecList: 
    var L = sonsLen(n)
    if L == 1: 
      genObjectFields(m, typ, n.sons[0], expr)
    elif L > 0: 
      var tmp = getTempName()
      appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", [tmp, toRope(L)])
      for i in countup(0, L-1): 
        var tmp2 = getNimNode(m)
        appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(i), tmp2])
        genObjectFields(m, typ, n.sons[i], tmp2)
      appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n", 
           [expr, toRope(L), tmp])
    else:
      appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2;$n", [expr, toRope(L)])
  of nkRecCase: 
    assert(n.sons[0].kind == nkSym)
    var field = n.sons[0].sym
    var tmp = discriminatorTableName(m, typ, field)
    var L = lengthOrd(field.typ)
    assert L > 0
    appf(m.s[cfsTypeInit3], "$1.kind = 3;$n" &
        "$1.offset = offsetof($2, $3);$n" & "$1.typ = $4;$n" &
        "$1.name = $5;$n" & "$1.sons = &$6[0];$n" &
        "$1.len = $7;$n", [expr, getTypeDesc(m, typ), field.loc.r, 
                           genTypeInfo(m, field.typ), 
                           makeCString(field.name.s), 
                           tmp, toRope(L)])
    appf(m.s[cfsData], "TNimNode* $1[$2];$n", [tmp, toRope(L+1)])
    for i in countup(1, sonsLen(n)-1): 
      var b = n.sons[i]           # branch
      var tmp2 = getNimNode(m)
      genObjectFields(m, typ, lastSon(b), tmp2)
      case b.kind
      of nkOfBranch: 
        if sonsLen(b) < 2: 
          internalError(b.info, "genObjectFields; nkOfBranch broken")
        for j in countup(0, sonsLen(b) - 2): 
          if b.sons[j].kind == nkRange: 
            var x = int(getOrdValue(b.sons[j].sons[0]))
            var y = int(getOrdValue(b.sons[j].sons[1]))
            while x <= y: 
              appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(x), tmp2])
              inc(x)
          else: 
            appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", 
                 [tmp, toRope(getOrdValue(b.sons[j])), tmp2])
      of nkElse: 
        appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", 
             [tmp, toRope(L), tmp2])
      else: internalError(n.info, "genObjectFields(nkRecCase)")
  of nkSym: 
    var field = n.sym
    appf(m.s[cfsTypeInit3], "$1.kind = 1;$n" &
        "$1.offset = offsetof($2, $3);$n" & "$1.typ = $4;$n" &
        "$1.name = $5;$n", [expr, getTypeDesc(m, typ), 
        field.loc.r, genTypeInfo(m, field.typ), makeCString(field.name.s)])
  else: internalError(n.info, "genObjectFields")
  
proc genObjectInfo(m: BModule, typ: PType, name: PRope) = 
  if typ.kind == tyObject: genTypeInfoAux(m, typ, name)
  else: genTypeInfoAuxBase(m, typ, name, toRope("0"))
  var tmp = getNimNode(m)
  genObjectFields(m, typ, typ.n, tmp)
  appf(m.s[cfsTypeInit3], "$1.node = &$2;$n", [name, tmp])

proc genTupleInfo(m: BModule, typ: PType, name: PRope) =
  genTypeInfoAuxBase(m, typ, name, toRope("0"))
  var expr = getNimNode(m)
  var length = sonsLen(typ)
  if length > 0: 
    var tmp = getTempName()
    appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", [tmp, toRope(length)])
    for i in countup(0, length - 1): 
      var a = typ.sons[i]
      var tmp2 = getNimNode(m)
      appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(i), tmp2])
      appf(m.s[cfsTypeInit3], "$1.kind = 1;$n" &
          "$1.offset = offsetof($2, Field$3);$n" & 
          "$1.typ = $4;$n" &
          "$1.name = \"Field$3\";$n", 
           [tmp2, getTypeDesc(m, typ), toRope(i), genTypeInfo(m, a)])
    appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n", 
         [expr, toRope(length), tmp])
  else: 
    appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2;$n", 
         [expr, toRope(length)])
  appf(m.s[cfsTypeInit3], "$1.node = &$2;$n", [name, expr])

proc genEnumInfo(m: BModule, typ: PType, name: PRope) =
  # Type information for enumerations is quite heavy, so we do some
  # optimizations here: The ``typ`` field is never set, as it is redundant
  # anyway. We generate a cstring array and a loop over it. Exceptional
  # positions will be reset after the loop.
  genTypeInfoAux(m, typ, name)
  var nodePtrs = getTempName()
  var length = sonsLen(typ.n)
  appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", 
       [nodePtrs, toRope(length)])
  var enumNames, specialCases: PRope
  var firstNimNode = m.typeNodes
  var hasHoles = false
  for i in countup(0, length - 1): 
    assert(typ.n.sons[i].kind == nkSym)
    var field = typ.n.sons[i].sym
    var elemNode = getNimNode(m)
    if field.ast == nil:
      # no explicit string literal for the enum field, so use field.name:
      app(enumNames, makeCString(field.name.s))
    else:
      app(enumNames, makeCString(field.ast.strVal))
    if i < length - 1: app(enumNames, ", " & tnl)
    if field.position != i or tfEnumHasHoles in typ.flags:
      appf(specialCases, "$1.offset = $2;$n", [elemNode, toRope(field.position)])
      hasHoles = true
  var enumArray = getTempName()
  var counter = getTempName()
  appf(m.s[cfsTypeInit1], "NI $1;$n", [counter])
  appf(m.s[cfsTypeInit1], "static char* NIM_CONST $1[$2] = {$n$3};$n", 
       [enumArray, toRope(length), enumNames])
  appf(m.s[cfsTypeInit3], "for ($1 = 0; $1 < $2; $1++) {$n" &
      "$3[$1+$4].kind = 1;$n" & "$3[$1+$4].offset = $1;$n" &
      "$3[$1+$4].name = $5[$1];$n" & "$6[$1] = &$3[$1+$4];$n" & "}$n", [counter, 
      toRope(length), m.typeNodesName, toRope(firstNimNode), enumArray, nodePtrs])
  app(m.s[cfsTypeInit3], specialCases)
  appf(m.s[cfsTypeInit3], 
       "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n$4.node = &$1;$n", 
       [getNimNode(m), toRope(length), nodePtrs, name])
  if hasHoles:
    # 1 << 2 is {ntfEnumHole}
    appf(m.s[cfsTypeInit3], "$1.flags = 1<<2;$n", [name])

proc genSetInfo(m: BModule, typ: PType, name: PRope) = 
  assert(typ.sons[0] != nil)
  genTypeInfoAux(m, typ, name)
  var tmp = getNimNode(m)
  appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 0;$n" & "$3.node = &$1;$n", 
       [tmp, toRope(firstOrd(typ)), name])

proc genArrayInfo(m: BModule, typ: PType, name: PRope) = 
  genTypeInfoAuxBase(m, typ, name, genTypeInfo(m, typ.sons[1]))

proc fakeClosureType(owner: PSym): PType =
  # we generate the same RTTI as for a tuple[pointer, ref tuple[]]
  result = newType(tyTuple, owner)
  result.rawAddSon(newType(tyPointer, owner))
  var r = newType(tyRef, owner)
  r.rawAddSon(newType(tyTuple, owner))
  result.rawAddSon(r)

type
  TTypeInfoReason = enum  ## for what do we need the type info?
    tiNew,                ## for 'new'
    tiNewSeq,             ## for 'newSeq'
    tiNonVariantAsgn,     ## for generic assignment without variants
    tiVariantAsgn         ## for generic assignment with variants

include ccgtrav

proc genTypeInfo(m: BModule, typ: PType): PRope = 
  var t = getUniqueType(typ)
  result = ropef("NTI$1", [toRope(t.id)])
  let owner = typ.skipTypes(abstractPtrs).owner.getModule
  if owner != m.module:
    # make sure the type info is created in the owner module
    discard genTypeInfo(owner.bmod, typ)
    # refenrece the type info as extern here
    discard cgsym(m, "TNimType")
    discard cgsym(m, "TNimNode")
    appf(m.s[cfsVars], "extern TNimType $1; /* $2 */$n", 
         [result, toRope(typeToString(t))])
    return con("(&".toRope, result, ")".toRope)
  if ContainsOrIncl(m.typeInfoMarker, t.id):
    return con("(&".toRope, result, ")".toRope)
  case t.kind
  of tyEmpty: result = toRope"0"
  of tyPointer, tyBool, tyChar, tyCString, tyString, tyInt..tyUInt64, tyVar:
    genTypeInfoAuxBase(m, t, result, toRope"0")
  of tyProc:
    if t.callConv != ccClosure:
      genTypeInfoAuxBase(m, t, result, toRope"0")
    else:
      genTupleInfo(m, fakeClosureType(t.owner), result)
  of tySequence, tyRef:
    genTypeInfoAux(m, t, result)
    if optRefcGC in gGlobalOptions:
      let markerProc = genTraverseProc(m, t, tiNew)
      appf(m.s[cfsTypeInit3], "$1.marker = $2;$n", [result, markerProc])
  of tyPtr, tyRange: genTypeInfoAux(m, t, result)
  of tyArrayConstr, tyArray: genArrayInfo(m, t, result)
  of tySet: genSetInfo(m, t, result)
  of tyEnum: genEnumInfo(m, t, result)
  of tyObject: genObjectInfo(m, t, result)
  of tyTuple: 
    # if t.n != nil: genObjectInfo(m, t, result)
    # else:
    # BUGFIX: use consistently RTTI without proper field names; otherwise
    # results are not deterministic!
    genTupleInfo(m, t, result)
  else: InternalError("genTypeInfo(" & $t.kind & ')')
  result = con("(&".toRope, result, ")".toRope)

proc genTypeSection(m: BModule, n: PNode) = 
  nil