store the instantiation cache in the generic symbol

6 files changed, 80 insertions, 70 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index 6d6a7b96e..7e57d0e85 100755
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -587,11 +587,26 @@ type
     generated*: bool          # needed for the backends:
     name*: PRope
     path*: PNode              # can be a string literal!
-    
-
+  
+  TInstantiation* = object
+    sym*: PSym
+    concreteTypes*: seq[PType]
+    usedBy*: seq[int32]       # list of modules using the generic
+                              # needed in caas mode for purging the cache
+                              # XXX: it's possible to switch to a 
+                              # simple ref count here
+  
+  PInstantiation* = ref TInstantiation
+      
   PLib* = ref TLib
   TSym* = object of TIdObj
-    kind*: TSymKind
+    case kind*: TSymKind
+    of skType:                # generic instantiation caches
+      typeInstCache*: seq[PType]
+    of routineKinds:
+      procInstCache*: seq[PInstantiation]
+    else: nil
+
     magic*: TMagic
     typ*: PType
     name*: PIdent
@@ -615,13 +630,14 @@ type
                               # for a conditional:
                               # 1 iff the symbol is defined, else 0
                               # (or not in symbol table)
-                              # for modules, a unique index corresponding
-                              # to the order of compilation 
+                              # for modules, an unique index corresponding
+                              # to the module's fileIdx
+
     offset*: int              # offset of record field
     loc*: TLoc
     annex*: PLib              # additional fields (seldom used, so we use a
                               # reference to another object to safe space)
-  
+      
   TTypeSeq* = seq[PType]
   TType* = object of TIdObj   # types are identical iff they have the
                               # same id; there may be multiple copies of a type
diff --git a/compiler/main.nim b/compiler/main.nim
index b5ba04245..15fa8b4fb 100755
--- a/compiler/main.nim
+++ b/compiler/main.nim
@@ -85,18 +85,6 @@ proc doCRC(fileIdx: int32) =
     # echo "FIRST CRC: ", fileIdx.ToFilename
     gMemCacheData[fileIdx].crc = crcFromFile(fileIdx.toFilename)
 
-proc safeAdd*[T](x: var seq[T], y: T) {.noSideEffect.} =
-  if x == nil: x = @[y]
-  else: x.add(y)
-
-proc safeAdd*(x: var string, y: char) =
-  if x == nil: x = ""
-  x.add(y)
-
-proc safeAdd*(x: var string, y: string) =
-  if x == nil: x = y
-  else: x.add(y)
-
 proc addDep(x: Psym, dep: int32) =
   growCache gMemCacheData, dep
   gMemCacheData[x.position].deps.safeAdd(dep)
diff --git a/compiler/sem.nim b/compiler/sem.nim
index 65aa7095c..b136cc035 100755
--- a/compiler/sem.nim
+++ b/compiler/sem.nim
@@ -190,7 +190,7 @@ include semtypes, semtempl, semgnrc, semstmts, semexprs
 
 proc addCodeForGenerics(c: PContext, n: PNode) = 
   for i in countup(c.generics.lastGenericIdx, Len(c.generics.generics) - 1):
-    var prc = c.generics.generics[i].instSym
+    var prc = c.generics.generics[i].inst.sym
     if prc.kind in {skProc, skMethod, skConverter} and prc.magic == mNone: 
       if prc.ast == nil or prc.ast.sons[bodyPos] == nil: 
         InternalError(prc.info, "no code for " & prc.name.s)
diff --git a/compiler/semdata.nim b/compiler/semdata.nim
index df59d88e9..d3122bb1e 100755
--- a/compiler/semdata.nim
+++ b/compiler/semdata.nim
@@ -36,17 +36,16 @@ type
                               # in standalone ``except`` and ``finally``
     next*: PProcCon           # used for stacking procedure contexts
   
-  TInstantiatedSymbol* {.final.} = object
-    genericSym*, instSym*: PSym
-    concreteTypes*: seq[PType]
-  
+  TInstantiationPair* = object
+    genericSym*: PSym
+    inst*: PInstantiation
+
   # If we generate an instance of a generic, we'd like to re-use that
   # instance if possible across module boundaries. However, this is not
   # possible if the compilation cache is enabled. So we give up then and use
   # the caching of generics only per module, not per project.
   TGenericsCache* {.final.} = object
-    InstTypes*: TIdTable # map PType to PType
-    generics*: seq[TInstantiatedSymbol] # a list of the things to compile
+    generics*: seq[TInstantiationPair] # a list of the things to compile
     lastGenericIdx*: int      # used for the generics stack
   
   PGenericsCache* = ref TGenericsCache
@@ -89,13 +88,16 @@ type
 var
   gGenericsCache: PGenericsCache # save for modularity
 
+proc makeInstPair*(s: PSym, inst: PInstantiation): TInstantiationPair =
+  result.genericSym = s
+  result.inst = inst
+
 proc filename*(c: PContext): string =
   # the module's filename
   return c.module.filename
 
 proc newGenericsCache*(): PGenericsCache =
   new(result)
-  initIdTable(result.InstTypes)
   result.generics = @[]
 
 proc newContext*(module: PSym): PContext
diff --git a/compiler/seminst.nim b/compiler/seminst.nim
index 8e164531a..0533d62ad 100755
--- a/compiler/seminst.nim
+++ b/compiler/seminst.nim
@@ -11,7 +11,7 @@
 # included from sem.nim
 
 proc instantiateGenericParamList(c: PContext, n: PNode, pt: TIdTable,
-                                 entry: var TInstantiatedSymbol) = 
+                                 entry: var TInstantiation) = 
   if n.kind != nkGenericParams: 
     InternalError(n.info, "instantiateGenericParamList; no generic params")
   newSeq(entry.concreteTypes, n.len)
@@ -43,22 +43,18 @@ proc instantiateGenericParamList(c: PContext, n: PNode, pt: TIdTable,
     addDecl(c, s)
     entry.concreteTypes[i] = t
 
-proc sameInstantiation(a, b: TInstantiatedSymbol): bool =
-  if a.genericSym.id == b.genericSym.id and 
-      a.concreteTypes.len == b.concreteTypes.len:
-    for i in 0 .. < a.concreteTypes.len:
+proc sameInstantiation(a, b: TInstantiation): bool =
+  if a.concreteTypes.len == b.concreteTypes.len:
+    for i in 0..a.concreteTypes.high:
       if not compareTypes(a.concreteTypes[i], b.concreteTypes[i],
                           flags = {TypeDescExactMatch}): return
     result = true
 
-proc GenericCacheGet(c: PContext, entry: var TInstantiatedSymbol): PSym = 
-  for i in countup(0, Len(c.generics.generics) - 1):
-    if sameInstantiation(entry, c.generics.generics[i]):
-      result = c.generics.generics[i].instSym
-      # checking for the concrete parameter list is wrong and unnecessary!
-      #if equalParams(b.typ.n, instSym.typ.n) == paramsEqual:
-      #echo "found in cache: ", getProcHeader(result)
-      return
+proc GenericCacheGet(genericSym: Psym, entry: TInstantiation): PSym =
+  if genericSym.procInstCache != nil:
+    for inst in genericSym.procInstCache:
+      if sameInstantiation(entry, inst[]):
+        return inst.sym
 
 proc removeDefaultParamValues(n: PNode) = 
   # we remove default params, because they cannot be instantiated properly
@@ -110,7 +106,7 @@ proc instantiateBody(c: PContext, n: PNode, result: PSym) =
 proc fixupInstantiatedSymbols(c: PContext, s: PSym) =
   for i in countup(0, Len(c.generics.generics) - 1):
     if c.generics.generics[i].genericSym.id == s.id:
-      var oldPrc = c.generics.generics[i].instSym
+      var oldPrc = c.generics.generics[i].inst.sym
       pushInfoContext(oldPrc.info)
       openScope(c.tab)
       var n = oldPrc.ast
@@ -155,10 +151,9 @@ proc generateInstance(c: PContext, fn: PSym, pt: TIdTable,
     InternalError(n.info, "generateInstance")
   n.sons[namePos] = newSymNode(result)
   pushInfoContext(info)
-  var entry: TInstantiatedSymbol
-  entry.instSym = result
-  entry.genericSym = fn
-  instantiateGenericParamList(c, n.sons[genericParamsPos], pt, entry)
+  var entry = TInstantiation.new
+  entry.sym = result
+  instantiateGenericParamList(c, n.sons[genericParamsPos], pt, entry[])
   n.sons[genericParamsPos] = ast.emptyNode
   # semantic checking for the parameters:
   if n.sons[paramsPos].kind != nkEmpty:
@@ -168,9 +163,10 @@ proc generateInstance(c: PContext, fn: PSym, pt: TIdTable,
     result.typ = newTypeS(tyProc, c)
     rawAddSon(result.typ, nil)
   result.typ.callConv = fn.typ.callConv
-  var oldPrc = GenericCacheGet(c, entry)
+  var oldPrc = GenericCacheGet(fn, entry[])
   if oldPrc == nil:
-    c.generics.generics.add(entry)
+    fn.procInstCache.safeAdd(entry)
+    c.generics.generics.add(makeInstPair(fn, entry))
     if n.sons[pragmasPos].kind != nkEmpty:
       pragma(c, result, n.sons[pragmasPos], allRoutinePragmas)
     if isNil(n.sons[bodyPos]):
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
index e12640945..82ebc4b5f 100755
--- a/compiler/semtypinst.nim
+++ b/compiler/semtypinst.nim
@@ -31,24 +31,31 @@ proc checkConstructedType*(info: TLineInfo, typ: PType) =
       if t.sons[0].kind != tyObject or tfFinal in t.sons[0].flags: 
         localError(info, errInheritanceOnlyWithNonFinalObjects)
 
-proc searchInstTypes(tab: TIdTable, key: PType): PType = 
-  # returns nil if we need to declare this type
-  result = PType(IdTableGet(tab, key))
-  if result == nil and tab.counter > 0: 
-    # we have to do a slow linear search because types may need
-    # to be compared by their structure:
-    for h in countup(0, high(tab.data)): 
-      var t = PType(tab.data[h].key)
-      if t != nil: 
-        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?
-            if not sameType(t.sons[j], key.sons[j]): 
-              match = false
-              break 
-          if match: 
-            return PType(tab.data[h].val)
+proc searchInstTypes(key: PType): PType =
+  let genericTyp = key.sons[0]
+  InternalAssert genericTyp.kind == tyGenericBody and
+                 key.sons[0] == genericTyp and
+                 genericTyp.sym != nil
+
+  if genericTyp.sym.typeInstCache == nil:
+    return
+
+  for inst in genericTyp.sym.typeInstCache:
+    InternalAssert inst.sons.len == key.sons.len + 1
+    if inst.id == key.id: return inst
+    block MatchType:
+      for j in 1 .. high(key.sons):
+        # XXX sameType is not really correct for nested generics?
+        if not sameType(inst.sons[j], key.sons[j]):
+          break MatchType
+      
+      return inst
+
+proc cacheTypeInst(inst: PType) =
+  # XXX: add to module's generics
+  #      update the refcount
+  let genericTyp = inst.sons[0]
+  genericTyp.sym.typeInstCache.safeAdd(inst)
 
 type
   TReplTypeVars* {.final.} = object 
@@ -134,7 +141,7 @@ proc handleGenericInvokation(cl: var TReplTypeVars, t: PType): PType =
   var header: PType = nil
   when true:
     # search for some instantiation here:
-    result = searchInstTypes(cl.c.generics.InstTypes, t)
+    result = searchInstTypes(t)
     if result != nil: return
     for i in countup(1, sonsLen(t) - 1):
       var x = t.sons[i]
@@ -145,7 +152,7 @@ proc handleGenericInvokation(cl: var TReplTypeVars, t: PType): PType =
         #idTablePut(cl.typeMap, body.sons[i-1], x)
     if header != nil:
       # search again after first pass:
-      result = searchInstTypes(cl.c.generics.InstTypes, header)
+      result = searchInstTypes(header)
       if result != nil: return
     else:
       header = copyType(t, t.owner, false)
@@ -153,15 +160,16 @@ proc handleGenericInvokation(cl: var TReplTypeVars, t: PType): PType =
     # we need to add the candidate here, before it's fully instantiated for
     # recursive instantions:
     result = newType(tyGenericInst, t.sons[0].owner)
-    idTablePut(cl.c.generics.InstTypes, header, result)
-
+    result.rawAddSon(header.sons[0])
+    cacheTypeInst(result)
+ 
     for i in countup(1, sonsLen(t) - 1):
       var x = replaceTypeVarsT(cl, t.sons[i])
       assert x.kind != tyGenericInvokation
       header.sons[i] = x
       idTablePut(cl.typeMap, body.sons[i-1], x)
     
-    for i in countup(0, sonsLen(t) - 1): 
+    for i in countup(1, sonsLen(t) - 1): 
       # if one of the params is not concrete, we cannot do anything
       # but we already raised an error!
       rawAddSon(result, header.sons[i])
@@ -212,7 +220,7 @@ proc ReplaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType =
       result = handleGenericInvokation(cl, result)
   of tyGenericInvokation: 
     result = handleGenericInvokation(cl, t)
-  of tyGenericBody: 
+  of tyGenericBody:
     InternalError(cl.info, "ReplaceTypeVarsT: tyGenericBody")
     result = ReplaceTypeVarsT(cl, lastSon(t))
   of tyInt: