compilation cache: various bugfixes; works for the compiler itself

12 files changed, 301 insertions, 142 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index c20e504d1..30989f392 100755
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -293,7 +293,10 @@ type
     tfAcyclic,        # type is acyclic (for GC optimization)
     tfEnumHasHoles,   # enum cannot be mapped into a range
     tfShallow,        # type can be shallow copied on assignment
-    tfThread          # proc type is marked as ``thread``
+    tfThread,         # proc type is marked as ``thread``
+    tfFromGeneric     # type is an instantiation of a generic; this is needed
+                      # because for instantiations of objects, structural
+                      # type equality has to be used
 
   TTypeFlags* = set[TTypeFlag]
 
@@ -487,14 +490,14 @@ type
                               # same id; there may be multiple copies of a type
                               # in memory!
     kind*: TTypeKind          # kind of type
+    callConv*: TCallingConvention # for procs
+    flags*: TTypeFlags        # flags of the type
     sons*: TTypeSeq           # base types, etc.
     n*: PNode                 # node for types:
                               # for range types a nkRange node
                               # for record types a nkRecord node
                               # for enum types a list of symbols
                               # else: unused
-    flags*: TTypeFlags        # flags of the type
-    callConv*: TCallingConvention # for procs
     owner*: PSym              # the 'owner' of the type
     sym*: PSym                # types have the sym associated with them
                               # it is used for converting types to strings
diff --git a/compiler/ccgexprs.nim b/compiler/ccgexprs.nim
index a06a5db43..5839db2be 100755
--- a/compiler/ccgexprs.nim
+++ b/compiler/ccgexprs.nim
@@ -1395,8 +1395,7 @@ proc genRangeChck(p: BProc, n: PNode, d: var TLoc, magic: string) =
         toRope(magic)]))
 
 proc genConv(p: BProc, e: PNode, d: var TLoc) =
-  if equalOrDistinctOf(e.typ, e.sons[1].typ) or
-     equalOrDistinctOf(e.sons[1].typ, e.typ):
+  if compareTypes(e.typ, e.sons[1].typ, dcEqIgnoreDistinct):
     expr(p, e.sons[1], d)
   else:
     genCast(p, e, d)
diff --git a/compiler/ccgutils.nim b/compiler/ccgutils.nim
index 555d401ca..fab67b294 100755
--- a/compiler/ccgutils.nim
+++ b/compiler/ccgutils.nim
@@ -56,35 +56,70 @@ proc hashString*(s: string): biggestInt =
     a = a +% `shl`(a, 15'i32)
     result = a
 
-var gTypeTable: array[TTypeKind, TIdTable]
+var 
+  gTypeTable: array[TTypeKind, TIdTable]
+  gCanonicalTypes: array[TTypeKind, PType]
 
 proc initTypeTables() = 
   for i in countup(low(TTypeKind), high(TTypeKind)): InitIdTable(gTypeTable[i])
+
+when false:
+  proc echoStats*() =
+    for i in countup(low(TTypeKind), high(TTypeKind)): 
+      echo i, " ", gTypeTable[i].counter
   
 proc GetUniqueType*(key: PType): PType = 
   # this is a hotspot in the compiler!
-  result = key
   if key == nil: return 
   var k = key.kind
-  case k 
-  of tyObject, tyEnum: 
-    result = PType(IdTableGet(gTypeTable[k], key))
-    if result == nil: 
-      IdTablePut(gTypeTable[k], key, key)
+  case k
+  of  tyNone, tyBool, tyChar, tyEmpty,
+      tyNil, tyExpr, tyStmt, tyTypeDesc, tyPointer, tyString, tyCString, 
+      tyInt, tyInt8, tyInt16, tyInt32, tyInt64,
+      tyFloat, tyFloat32, tyFloat64, tyFloat128,
+      tyUInt, tyUInt8, tyUInt16, tyUInt32, tyUInt64, tyBigNum:
+    result = gCanonicalTypes[k]
+    if result == nil:
+      gCanonicalTypes[k] = key
       result = key
-  of tyGenericInst, tyDistinct, tyOrdinal, tyMutable, tyConst, tyIter: 
+  of tyGenericInst, tyDistinct, tyOrdinal, tyMutable, tyConst, tyIter:
     result = GetUniqueType(lastSon(key))
-  of tyProc: 
-    nil
-  else: 
+  of tyArrayConstr, tyGenericInvokation, tyGenericBody, tyGenericParam,
+     tyOpenArray, tyArray, tyTuple, tySet, tyRange, 
+     tyPtr, tyRef, tySequence, tyForward, tyVarargs, tyProxy:
     # we have to do a slow linear search because types may need
     # to be compared by their structure:
-    if IdTableHasObjectAsKey(gTypeTable[k], key): return 
+    if IdTableHasObjectAsKey(gTypeTable[k], key): return key 
     for h in countup(0, high(gTypeTable[k].data)): 
       var t = PType(gTypeTable[k].data[h].key)
-      if (t != nil) and sameType(t, key): 
+      if t != nil and sameType(t, key): 
         return t
     IdTablePut(gTypeTable[k], key, key)
+    result = key
+  of tyObject:
+    if tfFromGeneric notin key.flags:
+      # fast case; lookup per id suffices:
+      result = PType(IdTableGet(gTypeTable[k], key))
+      if result == nil: 
+        IdTablePut(gTypeTable[k], key, key)
+        result = key
+    else:
+      # ugly slow case: need to compare by structure
+      if IdTableHasObjectAsKey(gTypeTable[k], key): return key
+      for h in countup(0, high(gTypeTable[k].data)): 
+        var t = PType(gTypeTable[k].data[h].key)
+        if t != nil and sameType(t, key): 
+          return t
+      IdTablePut(gTypeTable[k], key, key)
+      result = key
+  of tyEnum:
+    result = PType(IdTableGet(gTypeTable[k], key))
+    if result == nil: 
+      IdTablePut(gTypeTable[k], key, key)
+      result = key
+  of tyProc, tyVar: 
+    # tyVar is not 100% correct, but speeds things up a little:
+    result = key
 
 proc TableGetType*(tab: TIdTable, key: PType): PObject = 
   # returns nil if we need to declare this type
diff --git a/compiler/nversion.nim b/compiler/nversion.nim
index 0c0630dfd..1038a8ea6 100755
--- a/compiler/nversion.nim
+++ b/compiler/nversion.nim
@@ -18,3 +18,5 @@ const
   VersionPatch* = 13
   VersionAsString* = $VersionMajor & "." & $VersionMinor & "." & $VersionPatch
 
+  RodFileVersion* = "1030"       # modify this if the rod-format changes!
+
diff --git a/compiler/procfind.nim b/compiler/procfind.nim
index 30455c4c6..012d572fa 100755
--- a/compiler/procfind.nim
+++ b/compiler/procfind.nim
@@ -56,16 +56,17 @@ proc SearchForProc(c: PContext, fn: PSym, tos: int): PSym =
           nil
     result = NextIdentIter(it, c.tab.stack[tos])
 
-proc paramsFitBorrow(a, b: PNode): bool = 
-  var length = sonsLen(a)
+proc paramsFitBorrow(child, parent: PNode): bool = 
+  var length = sonsLen(child)
   result = false
-  if length == sonsLen(b): 
+  if length == sonsLen(parent): 
     for i in countup(1, length - 1): 
-      var m = a.sons[i].sym
-      var n = b.sons[i].sym
+      var m = child.sons[i].sym
+      var n = parent.sons[i].sym
       assert((m.kind == skParam) and (n.kind == skParam))
-      if not equalOrDistinctOf(m.typ, n.typ): return 
-    if not equalOrDistinctOf(a.sons[0].typ, b.sons[0].typ): return 
+      if not compareTypes(m.typ, n.typ, dcEqOrDistinctOf): return 
+    if not compareTypes(child.sons[0].typ, parent.sons[0].typ,
+                        dcEqOrDistinctOf): return
     result = true
 
 proc SearchForBorrowProc(c: PContext, fn: PSym, tos: int): PSym = 
diff --git a/compiler/rodread.nim b/compiler/rodread.nim
index cd6719f35..08721fd4a 100755
--- a/compiler/rodread.nim
+++ b/compiler/rodread.nim
@@ -141,9 +141,6 @@ type
   
   PRodReader* = ref TRodReader
 
-const 
-  FileVersion* = "1026"       # modify this if the rod-format changes!
-
 var rodCompilerprocs*: TStrTable
 
 proc handleSymbolFile*(module: PSym, filename: string): PRodReader
@@ -376,7 +373,6 @@ proc decodeSym(r: PRodReader, info: TLineInfo): PSym =
   if r.s[r.pos] == '@': 
     inc(r.pos)
     result.magic = TMagic(decodeVInt(r.s, r.pos))
-  if r.s[r.pos] == '(': result.ast = decodeNode(r, result.info)
   if r.s[r.pos] == '!': 
     inc(r.pos)
     result.options = cast[TOptions](int32(decodeVInt(r.s, r.pos)))
@@ -395,6 +391,7 @@ proc decodeSym(r: PRodReader, info: TLineInfo): PSym =
     result.offset = - 1
   decodeLoc(r, result.loc, result.info)
   result.annex = decodeLib(r, info)
+  if r.s[r.pos] == '(': result.ast = decodeNode(r, result.info)
   #echo "decoded: ", ident.s, "}"
 
 proc skipSection(r: PRodReader) = 
@@ -618,7 +615,7 @@ proc newRodReader(modfilename: string, crc: TCrc32,
       add(version, r.s[r.pos])
       inc(r.pos)
     if r.s[r.pos] == '\x0A': inc(r.pos)
-    if version == FileVersion: 
+    if version == RodFileVersion: 
       # since ROD files are only for caching, no backwarts compatibility is
       # needed
       processRodFile(r, crc)
diff --git a/compiler/rodwrite.nim b/compiler/rodwrite.nim
index 5a08ee144..a2cb44a43 100755
--- a/compiler/rodwrite.nim
+++ b/compiler/rodwrite.nim
@@ -46,8 +46,6 @@ proc addInterfaceSym(w: PRodWriter, s: PSym)
 proc addStmt(w: PRodWriter, n: PNode)
 proc writeRod(w: PRodWriter)
 
-proc processStacks(w: PRodWriter)
-
 proc getDefines(): string = 
   var it: TTabIter
   var s = InitTabIter(it, gSymbols)
@@ -282,7 +280,20 @@ proc encodeSym(w: PRodWriter, s: PSym, result: var string) =
   if s.magic != mNone:
     result.add('@')
     encodeVInt(ord(s.magic), result)
-  if s.ast != nil: 
+  if s.options != w.options: 
+    result.add('!')
+    encodeVInt(cast[int32](s.options), result)
+  if s.position != 0: 
+    result.add('%')
+    encodeVInt(s.position, result)
+  if s.offset != - 1:
+    result.add('`')
+    encodeVInt(s.offset, result)
+  encodeLoc(w, s.loc, result)
+  if s.annex != nil: encodeLib(w, s.annex, s.info, result)
+  # lazy loading will soon reload the ast lazily, so the ast needs to be
+  # the last entry of a symbol:
+  if s.ast != nil:
     # we used to attempt to save space here by only storing a dummy AST if
     # it is not necessary, but Nimrod's heavy compile-time evaluation features
     # make that unfeasible nowadays:
@@ -297,17 +308,6 @@ proc encodeSym(w: PRodWriter, s: PSym, result: var string) =
       if codeAst != nil:
         # resore the AST:
         s.ast.sons[codePos] = codeAst
-  if s.options != w.options: 
-    result.add('!')
-    encodeVInt(cast[int32](s.options), result)
-  if s.position != 0: 
-    result.add('%')
-    encodeVInt(s.position, result)
-  if s.offset != - 1:
-    result.add('`')
-    encodeVInt(s.offset, result)
-  encodeLoc(w, s.loc, result)
-  if s.annex != nil: encodeLib(w, s.annex, s.info, result)
   
 proc addToIndex(w: var TIndex, key, val: int) =
   if key - w.lastIdxKey == 1:
@@ -327,11 +327,14 @@ const debugWrittenIds = false
 when debugWrittenIds:
   var debugWritten = initIntSet()
 
-proc symStack(w: PRodWriter) =
+proc symStack(w: PRodWriter): int =
   var i = 0
   while i < len(w.sstack): 
     var s = w.sstack[i]
-    if IiTableGet(w.index.tab, s.id) == invalidKey: 
+    if sfForward in s.flags:
+      w.sstack[result] = s
+      inc result
+    elif IiTableGet(w.index.tab, s.id) == invalidKey:
       var m = getModule(s)
       if m == nil: InternalError("symStack: module nil: " & s.name.s)
       if (m.id == w.module.id) or (sfFromGeneric in s.flags): 
@@ -367,29 +370,40 @@ proc symStack(w: PRodWriter) =
             debug(s)
             debug(s.owner)
             debug(m)
-            InternalError("BUG!!!!")
+            InternalError("Symbol referred to but never written")
     inc(i)
-  setlen(w.sstack, 0)
+  setlen(w.sstack, result)
 
-proc typeStack(w: PRodWriter) = 
+proc typeStack(w: PRodWriter): int = 
   var i = 0
   while i < len(w.tstack): 
-    if IiTableGet(w.index.tab, w.tstack[i].id) == invalidKey: 
+    var t = w.tstack[i]
+    if t.kind == tyForward:
+      w.tstack[result] = t
+      inc result
+    elif IiTableGet(w.index.tab, t.id) == invalidKey: 
       var L = w.data.len
-      addToIndex(w.index, w.tstack[i].id, L)
-      encodeType(w, w.tstack[i], w.data)
+      addToIndex(w.index, t.id, L)
+      encodeType(w, t, w.data)
       add(w.data, rodNL)
     inc(i)
-  setlen(w.tstack, 0)
-
-proc processStacks(w: PRodWriter) = 
-  while (len(w.tstack) > 0) or (len(w.sstack) > 0): 
-    symStack(w)
-    typeStack(w)
+  setlen(w.tstack, result)
+
+proc processStacks(w: PRodWriter, finalPass: bool) =
+  var oldS = 0
+  var oldT = 0
+  while true:
+    var slen = symStack(w)
+    var tlen = typeStack(w)
+    if slen == oldS and tlen == oldT: break
+    oldS = slen
+    oldT = tlen
+  if finalPass and (oldS != 0 or oldT != 0):
+    InternalError("could not serialize some forwarded symbols/types")
 
 proc rawAddInterfaceSym(w: PRodWriter, s: PSym) = 
   pushSym(w, s)
-  processStacks(w)
+  processStacks(w, false)
 
 proc addInterfaceSym(w: PRodWriter, s: PSym) = 
   if w == nil: return 
@@ -402,17 +416,17 @@ proc addStmt(w: PRodWriter, n: PNode) =
   add(w.init, rodNL)
   encodeNode(w, UnknownLineInfo(), n, w.data)
   add(w.data, rodNL)
-  processStacks(w)
+  processStacks(w, false)
 
 proc writeRod(w: PRodWriter) = 
-  processStacks(w)
+  processStacks(w, true)
   var f: TFile
   if not open(f, completeGeneratedFilePath(changeFileExt(w.filename, "rod")),
               fmWrite):
     return
   # write header:
   f.write("NIM:")
-  f.write(FileVersion)
+  f.write(RodFileVersion)
   f.write(rodNL)
   var id = "ID:"
   encodeVInt(w.module.id, id)
diff --git a/compiler/semexprs.nim b/compiler/semexprs.nim
index e93644457..a806cdb67 100755
--- a/compiler/semexprs.nim
+++ b/compiler/semexprs.nim
@@ -128,8 +128,7 @@ proc checkConvertible(info: TLineInfo, castDest, src: PType) =
     # we use d, s here to speed up that operation a bit:
     case cmpTypes(d, s)
     of isNone, isGeneric: 
-      if not equalOrDistinctOf(castDest, src) and
-          not equalOrDistinctOf(src, castDest): 
+      if not compareTypes(castDest, src, dcEqIgnoreDistinct):
         GlobalError(info, errGenerated, `%`(
             MsgKindToString(errIllegalConvFromXtoY), 
             [typeToString(src), typeToString(castDest)]))
@@ -381,8 +380,7 @@ proc isAssignable(c: PContext, n: PNode): TAssignableResult =
     # Object and tuple conversions are still addressable, so we skip them
     if skipTypes(n.typ, abstractPtrs).kind in {tyOpenArray, tyTuple, tyObject}: 
       result = isAssignable(c, n.sons[1])
-    elif equalOrDistinctOf(n.typ, n.sons[1].typ) or 
-         equalOrDistinctOf(n.sons[1].typ, n.typ):
+    elif compareTypes(n.typ, n.sons[1].typ, dcEqIgnoreDistinct):
       # types that are equal modulo distinction preserve l-value:
       result = isAssignable(c, n.sons[1])
   of nkHiddenDeref, nkDerefExpr: 
diff --git a/compiler/semstmts.nim b/compiler/semstmts.nim
index d98d60224..c5ac1f153 100755
--- a/compiler/semstmts.nim
+++ b/compiler/semstmts.nim
@@ -502,7 +502,14 @@ proc typeSectionRightSidePass(c: PContext, n: PNode) =
       s.typ.kind = tyGenericBody
       if s.typ.containerID != 0: 
         InternalError(a.info, "semTypeSection: containerID")
-      s.typ.containerID = getID()
+      s.typ.containerID = s.typ.id
+      # XXX for generic type aliases this is not correct! We need the
+      # underlying Id really: 
+      #
+      # type
+      #   TGObj[T] = object
+      #   TAlias[T] = TGObj[T]
+      # 
       a.sons[1] = semGenericParamList(c, a.sons[1], s.typ)
       s.typ.size = -1 # could not be computed properly
       # we fill it out later. For magic generics like 'seq', it won't be filled
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
index 5ce9d4688..0473f2f74 100755
--- a/compiler/semtypinst.nim
+++ b/compiler/semtypinst.nim
@@ -44,7 +44,7 @@ proc searchInstTypes(tab: TIdTable, key: PType): PType =
     for h in countup(0, high(tab.data)): 
       var t = PType(tab.data[h].key)
       if t != nil: 
-        if key.containerId == t.containerID: 
+        if key.containerId == t.containerId: 
           var match = true
           for j in countup(0, sonsLen(t) - 1): 
             # XXX sameType is not really correct for nested generics?
@@ -184,6 +184,7 @@ proc ReplaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType =
   else:
     if containsGenericType(t):
       result = copyType(t, t.owner, false)
+      incl(result.flags, tfFromGeneric)
       result.size = -1 # needs to be recomputed
       for i in countup(0, sonsLen(result) - 1):
         result.sons[i] = ReplaceTypeVarsT(cl, result.sons[i])
diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim
index f91d4798a..fac7815d1 100755
--- a/compiler/sigmatch.nim
+++ b/compiler/sigmatch.nim
@@ -161,9 +161,9 @@ proc handleFloatRange(f, a: PType): TTypeRelation =
     elif (k >= tyFloat) and (k <= tyFloat128): result = isConvertible
     else: result = isNone
   
-proc isObjectSubtype(a, f: PType): bool = 
+proc isObjectSubtype(a, f: PType): bool =
   var t = a
-  while t != nil and t.id != f.id: t = base(t)
+  while t != nil and not sameObjectTypes(f, t): t = t.sons[0]
   result = t != nil
 
 proc minRel(a, b: TTypeRelation): TTypeRelation = 
@@ -240,8 +240,8 @@ proc typeRel(mapping: var TIdTable, f, a: PType): TTypeRelation =
     return typeRel(mapping, f, a.sons[0])
   case f.kind
   of tyEnum: 
-    if a.kind == f.kind and a.id == f.id: result = isEqual
-    elif skipTypes(a, {tyRange}).id == f.id: result = isSubtype
+    if a.kind == f.kind and sameEnumTypes(f, a): result = isEqual
+    elif sameEnumTypes(f, skipTypes(a, {tyRange})): result = isSubtype
   of tyBool, tyChar: 
     if a.kind == f.kind: result = isEqual
     elif skipTypes(a, {tyRange}).kind == f.kind: result = isSubtype
@@ -327,11 +327,11 @@ proc typeRel(mapping: var TIdTable, f, a: PType): TTypeRelation =
   of tyTuple: 
     if a.kind == tyTuple: result = tupleRel(mapping, f, a)
   of tyObject: 
-    if a.kind == tyObject: 
-      if a.id == f.id: result = isEqual
+    if a.kind == tyObject:
+      if sameObjectTypes(f, a): result = isEqual
       elif isObjectSubtype(a, f): result = isSubtype
   of tyDistinct: 
-    if (a.kind == tyDistinct) and (a.id == f.id): result = isEqual
+    if (a.kind == tyDistinct) and sameDistinctTypes(f, a): result = isEqual
   of tySet: 
     if a.kind == tySet: 
       if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): 
diff --git a/compiler/types.nim b/compiler/types.nim
index f02f5064a..7c88e2335 100755
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -32,9 +32,7 @@ proc IterOverType*(t: PType, iter: TTypeIter, closure: PObject): bool
   # Returns result of `iter`.
 proc mutateType*(t: PType, iter: TTypeMutator, closure: PObject): PType
   # Returns result of `iter`.
-proc SameType*(x, y: PType): bool
-proc SameTypeOrNil*(a, b: PType): bool
-proc equalOrDistinctOf*(x, y: PType): bool
+
 type 
   TParamsEquality* = enum     # they are equal, but their
                               # identifiers or their return
@@ -543,6 +541,53 @@ proc lengthOrd(t: PType): biggestInt =
   of tyInt64, tyInt32, tyInt: result = lastOrd(t)
   of tyDistinct, tyConst, tyMutable: result = lengthOrd(t.sons[0])
   else: result = lastOrd(t) - firstOrd(t) + 1
+
+# -------------- type equality -----------------------------------------------
+
+type
+  TDistinctCompare* = enum ## how distinct types are to be compared
+    dcEq,                  ## a and b should be the same type
+    dcEqIgnoreDistinct,    ## compare symetrically: (distinct a) == b, a == b
+                           ## or a == (distinct b)
+    dcEqOrDistinctOf       ## a equals b or a is distinct of b
+
+  TSameTypeClosure = object {.pure.}
+    cmp: TDistinctCompare
+    initSets: bool
+    recCheck: int
+    a: TIntSet
+    b: TIntSet
+
+proc initSameTypeClosure: TSameTypeClosure =
+  # we do the initialization lazy for performance (avoids memory allocations)
+  nil
+
+proc containsOrIncl(c: var TSameTypeClosure, a, b: PType): bool =
+  result = c.initSets and c.a.contains(a.id) and c.b.contains(b.id)
+  if not result:
+    if not c.initSets:
+      c.initSets = true
+      c.a = initIntSet()
+      c.b = initIntSet()
+    c.a.incl(a.id)
+    c.b.incl(b.id)
+
+proc SameTypeAux(x, y: PType, c: var TSameTypeClosure): bool
+proc SameTypeOrNilAux(a, b: PType, c: var TSameTypeClosure): bool =
+  if a == b:
+    result = true
+  else:
+    if a == nil or b == nil: result = false
+    else: result = SameTypeAux(a, b, c)
+
+proc SameTypeOrNil*(a, b: PType): bool =
+  if a == b:
+    result = true
+  else: 
+    if a == nil or b == nil: result = false
+    else: 
+      var c = initSameTypeClosure()
+      result = SameTypeAux(a, b, c)
   
 proc equalParam(a, b: PSym): TParamsEquality = 
   if SameTypeOrNil(a.typ, b.typ): 
@@ -587,13 +632,6 @@ proc equalParams(a, b: PNode): TParamsEquality =
         result = paramsIncompatible # overloading by different
                                     # result types does not work
   
-proc SameTypeOrNil(a, b: PType): bool = 
-  if a == b: 
-    result = true
-  else: 
-    if a == nil or b == nil: result = false
-    else: result = SameType(a, b)
-  
 proc SameLiteral(x, y: PNode): bool = 
   if x.kind == y.kind: 
     case x.kind
@@ -606,15 +644,14 @@ proc SameRanges(a, b: PNode): bool =
   result = SameLiteral(a.sons[0], b.sons[0]) and
            SameLiteral(a.sons[1], b.sons[1])
 
-proc sameTuple(a, b: PType, DistinctOf: bool): bool = 
+proc sameTuple(a, b: PType, c: var TSameTypeClosure): bool = 
   # two tuples are equivalent iff the names, types and positions are the same;
   # however, both types may not have any field names (t.n may be nil) which
   # complicates the matter a bit.
   if sonsLen(a) == sonsLen(b): 
     result = true
     for i in countup(0, sonsLen(a) - 1): 
-      if DistinctOf: result = equalOrDistinctOf(a.sons[i], b.sons[i])
-      else: result = SameType(a.sons[i], b.sons[i])
+      result = SameTypeAux(a.sons[i], b.sons[i], c)
       if not result: return 
     if a.n != nil and b.n != nil: 
       for i in countup(0, sonsLen(a.n) - 1): 
@@ -627,74 +664,138 @@ proc sameTuple(a, b: PType, DistinctOf: bool): bool =
         if not result: break 
   else: 
     result = false
-  
-proc SameType(x, y: PType): bool = 
+
+template IfFastObjectTypeCheckFailed(a, b: PType, body: stmt) =
+  if tfFromGeneric notin a.flags + b.flags:
+    # fast case: id comparison suffices:
+    result = a.id == b.id
+  else:
+    # expensive structural equality test; however due to the way generic and
+    # objects work, if one of the types does **not** contain tfFromGeneric,
+    # they cannot be equal. The check ``a.sym.Id == b.sym.Id`` checks
+    # for the same origin and is essential because we don't want "pure" 
+    # structural type equivalence:
+    #
+    # type
+    #   TA[T] = object
+    #   TB[T] = object
+    # --> TA[int] != TB[int]
+    if tfFromGeneric in a.flags * b.flags and a.sym.Id == b.sym.Id:
+      # ok, we need the expensive structural check
+      body
+
+proc sameObjectTypes*(a, b: PType): bool =
+  # specialized for efficiency (sigmatch uses it)
+  IfFastObjectTypeCheckFailed(a, b):
+    var c = initSameTypeClosure()
+    result = sameTypeAux(a, b, c)
+
+proc sameDistinctTypes*(a, b: PType): bool {.inline.} =
+  result = sameObjectTypes(a, b)
+
+proc sameEnumTypes*(a, b: PType): bool {.inline.} =
+  result = a.id == b.id
+
+proc SameObjectTree(a, b: PNode, c: var TSameTypeClosure): bool =
+  if a == b:
+    result = true
+  elif (a != nil) and (b != nil) and (a.kind == b.kind):
+    if sameTypeOrNilAux(a.typ, b.typ, c):
+      case a.kind
+      of nkSym:
+        # same symbol as string is enough:
+        result = a.sym.name.id == b.sym.name.id
+      of nkIdent: result = a.ident.id == b.ident.id
+      of nkCharLit..nkInt64Lit: result = a.intVal == b.intVal
+      of nkFloatLit..nkFloat64Lit: result = a.floatVal == b.floatVal
+      of nkStrLit..nkTripleStrLit: result = a.strVal == b.strVal
+      of nkEmpty, nkNilLit, nkType: result = true
+      else:
+        if sonsLen(a) == sonsLen(b): 
+          for i in countup(0, sonsLen(a) - 1): 
+            if not SameObjectTree(a.sons[i], b.sons[i], c): return 
+          result = true
+
+proc sameObjectStructures(a, b: PType, c: var TSameTypeClosure): bool =
+  # check base types:
+  if sonsLen(a) != sonsLen(b): return
+  for i in countup(0, sonsLen(a) - 1):
+    if not SameTypeOrNilAux(a.sons[i], b.sons[i], c): return
+  if not SameObjectTree(a.n, b.n, c): return
+  result = true
+
+proc SameTypeAux(x, y: PType, c: var TSameTypeClosure): bool = 
+  template CycleCheck() =
+    # believe it or not, the direct check for ``containsOrIncl(c, a, b)``
+    # increases bootstrapping time from 2.4s to 3.3s on my laptop! So we cheat
+    # again: Since the recursion check is only to not get caught in an endless
+    # recursion, we use a counter and only if it's value is over some 
+    # threshold we perform the expansive exact cycle check:
+    if c.recCheck < 20:
+      inc c.recCheck
+    else:
+      if containsOrIncl(c, a, b): return true
+
   if x == y: return true
   var a = skipTypes(x, {tyGenericInst})
   var b = skipTypes(y, {tyGenericInst})
   assert(a != nil)
   assert(b != nil)
-  if a.kind != b.kind: 
-    return false
+  if a.kind != b.kind:
+    case c.cmp
+    of dcEq: return false
+    of dcEqIgnoreDistinct:
+      while a.kind == tyDistinct: a = a.sons[0]
+      while b.kind == tyDistinct: b = b.sons[0]
+      if a.kind != b.kind: return false
+    of dcEqOrDistinctOf:
+      while a.kind == tyDistinct: a = a.sons[0]
+      if a.kind != b.kind: return false
   case a.Kind
   of tyEmpty, tyChar, tyBool, tyNil, tyPointer, tyString, tyCString, 
      tyInt..tyBigNum, tyExpr, tyStmt, tyTypeDesc: 
     result = true
-  of tyEnum, tyForward, tyObject, tyDistinct, tyProxy: result = (a.id == b.id)
-  of tyTuple: result = sameTuple(a, b, false)
-  of tyGenericInst: result = sameType(lastSon(a), lastSon(b))
-  of tyGenericParam, tyGenericInvokation, tyGenericBody, tySequence, tyOrdinal, 
-     tyOpenArray, tySet, tyRef, tyPtr, tyVar, tyArrayConstr, tyArray, tyProc,
-     tyConst, tyMutable, tyVarargs, tyIter: 
-    if sonsLen(a) == sonsLen(b): 
+  of tyObject:
+    IfFastObjectTypeCheckFailed(a, b):
+      CycleCheck()
+      result = sameObjectStructures(a, b, c)
+  of tyDistinct:
+    CycleCheck()
+    result = sameTypeAux(a.sons[0], b.sons[0], c)
+  of tyEnum, tyForward, tyProxy:
+    # XXX generic enums do not make much sense, but require structural checking
+    result = a.id == b.id
+  of tyTuple:
+    CycleCheck()
+    result = sameTuple(a, b, c)
+  of tyGenericInst: result = sameTypeAux(lastSon(a), lastSon(b), c)
+  of tyGenericParam, tyGenericInvokation, tyGenericBody, tySequence,
+     tyOrdinal, tyOpenArray, tySet, tyRef, tyPtr, tyVar, tyArrayConstr,
+     tyArray, tyProc, tyConst, tyMutable, tyVarargs, tyIter: 
+    if sonsLen(a) == sonsLen(b):
+      CycleCheck()
       result = true
-      for i in countup(0, sonsLen(a) - 1): 
-        result = SameTypeOrNil(a.sons[i], b.sons[i]) # BUGFIX
+      for i in countup(0, sonsLen(a) - 1):
+        result = SameTypeOrNilAux(a.sons[i], b.sons[i], c)
         if not result: return 
       if result and (a.kind == tyProc): 
-        result = a.callConv == b.callConv # BUGFIX
-    else: 
-      result = false
-  of tyRange: 
-    result = SameTypeOrNil(a.sons[0], b.sons[0]) and
+        result = a.callConv == b.callConv
+  of tyRange:
+    CycleCheck()    
+    result = SameTypeOrNilAux(a.sons[0], b.sons[0], c) and
         SameValue(a.n.sons[0], b.n.sons[0]) and
         SameValue(a.n.sons[1], b.n.sons[1])
   of tyNone: result = false
+
+proc SameType*(x, y: PType): bool =
+  var c = initSameTypeClosure()
+  result = sameTypeAux(x, y, c)
   
-proc equalOrDistinctOf(x, y: PType): bool = 
-  if x == y: return true
-  if x == nil or y == nil: return false
-  var a = skipTypes(x, {tyGenericInst})
-  var b = skipTypes(y, {tyGenericInst})
-  assert(a != nil)
-  assert(b != nil)
-  if a.kind != b.kind: 
-    if a.kind == tyDistinct: a = a.sons[0]
-    if a.kind != b.kind: 
-      return false
-  case a.Kind
-  of tyEmpty, tyChar, tyBool, tyNil, tyPointer, tyString, tyCString, 
-     tyInt..tyBigNum, tyExpr, tyStmt, tyTypeDesc: 
-    result = true
-  of tyEnum, tyForward, tyObject, tyDistinct, tyProxy: result = (a.id == b.id)
-  of tyTuple: result = sameTuple(a, b, true)
-  of tyGenericInst: result = equalOrDistinctOf(lastSon(a), lastSon(b))
-  of tyGenericParam, tyGenericInvokation, tyGenericBody, tySequence, tyOrdinal, 
-     tyOpenArray, tySet, tyRef, tyPtr, tyVar, tyArrayConstr, tyArray, tyProc,
-     tyConst, tyMutable, tyVarargs, tyIter: 
-    if sonsLen(a) == sonsLen(b): 
-      result = true
-      for i in countup(0, sonsLen(a) - 1): 
-        result = equalOrDistinctOf(a.sons[i], b.sons[i])
-        if not result: return 
-      if result and (a.kind == tyProc): result = a.callConv == b.callConv
-    else: 
-      result = false
-  of tyRange: 
-    result = equalOrDistinctOf(a.sons[0], b.sons[0]) and
-        SameValue(a.n.sons[0], b.n.sons[0]) and
-        SameValue(a.n.sons[1], b.n.sons[1])
-  of tyNone: result = false
+proc compareTypes*(x, y: PType, cmp: TDistinctCompare): bool =
+  ## compares two type for equality (modulo type distinction)
+  var c = initSameTypeClosure()
+  c.cmp = cmp
+  result = sameTypeAux(x, y, c)
   
 proc typeAllowedAux(marker: var TIntSet, typ: PType, kind: TSymKind): bool
 proc typeAllowedNode(marker: var TIntSet, n: PNode, kind: TSymKind): bool = 
@@ -927,8 +1028,9 @@ proc computeSize(typ: PType): biggestInt =
 
 proc getReturnType*(s: PSym): PType =
   # Obtains the return type of a iterator/proc/macro/template
-  assert s.kind in { skProc, skTemplate, skMacro, skIterator }
-  result = s.typ.n.sons[0].typ
+  assert s.kind in {skProc, skTemplate, skMacro, skIterator}
+  # XXX ask Zahary if this change broke something
+  result = s.typ.sons[0]
 
 proc getSize(typ: PType): biggestInt = 
   result = computeSize(typ)