IC: use tables instead of huge seqs because the compiler can create l… (#23737)

…ots of dummy syms and types

5 files changed, 67 insertions, 49 deletions

diff --git a/compiler/ic/ic.nim b/compiler/ic/ic.nim
index c9f546c76..22b886ff4 100644
--- a/compiler/ic/ic.nim
+++ b/compiler/ic/ic.nim
@@ -59,8 +59,8 @@ type
     emittedTypeInfo*: seq[string]
     backendFlags*: set[ModuleBackendFlag]
 
-    syms*: seq[PackedSym]
-    types*: seq[PackedType]
+    syms*: OrderedTable[int32, PackedSym]
+    types*: OrderedTable[int32, PackedType]
     strings*: BiTable[string] # we could share these between modules.
     numbers*: BiTable[BiggestInt] # we also store floats in here so
                                   # that we can assure that every bit is kept
@@ -362,10 +362,10 @@ proc storeType(t: PType; c: var PackedEncoder; m: var PackedModule): PackedItemI
   result = PackedItemId(module: toLitId(t.uniqueId.module.FileIndex, c, m), item: t.uniqueId.item)
 
   if t.uniqueId.module == c.thisModule and not c.typeMarker.containsOrIncl(t.uniqueId.item):
-    if t.uniqueId.item >= m.types.len:
-      setLen m.types, t.uniqueId.item+1
+    #if t.uniqueId.item >= m.types.len:
+    #  setLen m.types, t.uniqueId.item+1
 
-    var p = PackedType(kind: t.kind, flags: t.flags, callConv: t.callConv,
+    var p = PackedType(id: t.uniqueId.item, kind: t.kind, flags: t.flags, callConv: t.callConv,
       size: t.size, align: t.align, nonUniqueId: t.itemId.item,
       paddingAtEnd: t.paddingAtEnd)
     storeNode(p, t, n)
@@ -396,12 +396,12 @@ proc storeSym*(s: PSym; c: var PackedEncoder; m: var PackedModule): PackedItemId
   result = PackedItemId(module: toLitId(s.itemId.module.FileIndex, c, m), item: s.itemId.item)
 
   if s.itemId.module == c.thisModule and not c.symMarker.containsOrIncl(s.itemId.item):
-    if s.itemId.item >= m.syms.len:
-      setLen m.syms, s.itemId.item+1
+    #if s.itemId.item >= m.syms.len:
+    #  setLen m.syms, s.itemId.item+1
 
     assert sfForward notin s.flags
 
-    var p = PackedSym(kind: s.kind, flags: s.flags, info: s.info.toPackedInfo(c, m), magic: s.magic,
+    var p = PackedSym(id: s.itemId.item, kind: s.kind, flags: s.flags, info: s.info.toPackedInfo(c, m), magic: s.magic,
       position: s.position, offset: s.offset, disamb: s.disamb, options: s.options,
       name: s.name.s.toLitId(m))
 
@@ -613,6 +613,10 @@ proc loadRodFile*(filename: AbsoluteFile; m: var PackedModule; config: ConfigRef
     f.loadSection section
     f.loadSeq data
 
+  template loadTableSection(section, data) {.dirty.} =
+    f.loadSection section
+    f.loadOrderedTable data
+
   template loadTabSection(section, data) {.dirty.} =
     f.loadSection section
     f.load data
@@ -645,8 +649,8 @@ proc loadRodFile*(filename: AbsoluteFile; m: var PackedModule; config: ConfigRef
     loadTabSection topLevelSection, m.topLevel
 
     loadTabSection bodiesSection, m.bodies
-    loadSeqSection symsSection, m.syms
-    loadSeqSection typesSection, m.types
+    loadTableSection symsSection, m.syms
+    loadTableSection typesSection, m.types
 
     loadSeqSection typeInstCacheSection, m.typeInstCache
     loadSeqSection procInstCacheSection, m.procInstCache
@@ -691,6 +695,10 @@ proc saveRodFile*(filename: AbsoluteFile; encoder: var PackedEncoder; m: var Pac
     f.storeSection section
     f.store data
 
+  template storeTableSection(section, data) {.dirty.} =
+    f.storeSection section
+    f.storeOrderedTable data
+
   storeTabSection stringsSection, m.strings
 
   storeSeqSection checkSumsSection, m.includes
@@ -714,9 +722,9 @@ proc saveRodFile*(filename: AbsoluteFile; encoder: var PackedEncoder; m: var Pac
   storeTabSection topLevelSection, m.topLevel
 
   storeTabSection bodiesSection, m.bodies
-  storeSeqSection symsSection, m.syms
+  storeTableSection symsSection, m.syms
 
-  storeSeqSection typesSection, m.types
+  storeTableSection typesSection, m.types
 
   storeSeqSection typeInstCacheSection, m.typeInstCache
   storeSeqSection procInstCacheSection, m.procInstCache
@@ -767,8 +775,8 @@ type
     status*: ModuleStatus
     symsInit, typesInit, loadedButAliveSetChanged*: bool
     fromDisk*: PackedModule
-    syms: seq[PSym] # indexed by itemId
-    types: seq[PType]
+    syms: OrderedTable[int32, PSym] # indexed by itemId
+    types: OrderedTable[int32, PType]
     module*: PSym # the one true module symbol.
     iface, ifaceHidden: Table[PIdent, seq[PackedItemId]]
       # PackedItemId so that it works with reexported symbols too
@@ -961,11 +969,11 @@ proc loadSym(c: var PackedDecoder; g: var PackedModuleGraph; thisModule: int; s:
         loadToReplayNodes(g, c.config, c.cache, m, g[int m])
 
     assert g[si].status in {loaded, storing, stored}
-    if not g[si].symsInit:
-      g[si].symsInit = true
-      setLen g[si].syms, g[si].fromDisk.syms.len
+    #if not g[si].symsInit:
+    #  g[si].symsInit = true
+    #  setLen g[si].syms, g[si].fromDisk.syms.len
 
-    if g[si].syms[s.item] == nil:
+    if g[si].syms.getOrDefault(s.item) == nil:
       if g[si].fromDisk.syms[s.item].kind != skModule:
         result = symHeaderFromPacked(c, g, g[si].fromDisk.syms[s.item], si, s.item)
         # store it here early on, so that recursions work properly:
@@ -1012,11 +1020,11 @@ proc loadType(c: var PackedDecoder; g: var PackedModuleGraph; thisModule: int; t
     assert g[si].status in {loaded, storing, stored}
     assert t.item > 0
 
-    if not g[si].typesInit:
-      g[si].typesInit = true
-      setLen g[si].types, g[si].fromDisk.types.len
+    #if not g[si].typesInit:
+    #  g[si].typesInit = true
+    #  setLen g[si].types, g[si].fromDisk.types.len
 
-    if g[si].types[t.item] == nil:
+    if g[si].types.getOrDefault(t.item) == nil:
       result = typeHeaderFromPacked(c, g, g[si].fromDisk.types[t.item], si, t.item)
       # store it here early on, so that recursions work properly:
       g[si].types[t.item] = result
@@ -1155,10 +1163,7 @@ proc loadProcBody*(config: ConfigRef, cache: IdentCache;
 proc loadTypeFromId*(config: ConfigRef, cache: IdentCache;
                      g: var PackedModuleGraph; module: int; id: PackedItemId): PType =
   bench g.loadType:
-    if id.item < g[module].types.len:
-      result = g[module].types[id.item]
-    else:
-      result = nil
+    result = g[module].types.getOrDefault(id.item)
     if result == nil:
       var decoder = PackedDecoder(
         lastModule: int32(-1),
@@ -1171,10 +1176,7 @@ proc loadTypeFromId*(config: ConfigRef, cache: IdentCache;
 proc loadSymFromId*(config: ConfigRef, cache: IdentCache;
                     g: var PackedModuleGraph; module: int; id: PackedItemId): PSym =
   bench g.loadSym:
-    if id.item < g[module].syms.len:
-      result = g[module].syms[id.item]
-    else:
-      result = nil
+    result = g[module].syms.getOrDefault(id.item)
     if result == nil:
       var decoder = PackedDecoder(
         lastModule: int32(-1),
@@ -1190,19 +1192,6 @@ proc translateId*(id: PackedItemId; g: PackedModuleGraph; thisModule: int; confi
   else:
     ItemId(module: toFileIndex(id.module, g[thisModule].fromDisk, config).int32, item: id.item)
 
-proc checkForHoles(m: PackedModule; config: ConfigRef; moduleId: int) =
-  var bugs = 0
-  for i in 1 .. high(m.syms):
-    if m.syms[i].kind == skUnknown:
-      echo "EMPTY ID ", i, " module ", moduleId, " ", toFullPath(config, FileIndex(moduleId))
-      inc bugs
-  assert bugs == 0
-  when false:
-    var nones = 0
-    for i in 1 .. high(m.types):
-      inc nones, m.types[i].kind == tyNone
-    assert nones < 1
-
 proc simulateLoadedModule*(g: var PackedModuleGraph; conf: ConfigRef; cache: IdentCache;
                            moduleSym: PSym; m: PackedModule) =
   # For now only used for heavy debugging. In the future we could use this to reduce the
diff --git a/compiler/ic/integrity.nim b/compiler/ic/integrity.nim
index d78e56847..3e8ea2503 100644
--- a/compiler/ic/integrity.nim
+++ b/compiler/ic/integrity.nim
@@ -10,7 +10,7 @@
 ## Integrity checking for a set of .rod files.
 ## The set must cover a complete Nim project.
 
-import std/sets
+import std/[sets, tables]
 
 when defined(nimPreviewSlimSystem):
   import std/assertions
@@ -108,18 +108,18 @@ proc checkModule(c: var CheckedContext; m: PackedModule) =
   # We check that:
   # - Every symbol references existing types and symbols.
   # - Every tree node references existing types and symbols.
-  for i in 0..high(m.syms):
-    checkLocalSym c, int32(i)
+  for _, v in pairs(m.syms):
+    checkLocalSym c, v.id
 
   checkTree c, m.toReplay
   checkTree c, m.topLevel
 
   for e in m.exports:
-    assert e[1] >= 0 and e[1] < m.syms.len
+    #assert e[1] >= 0 and e[1] < m.syms.len
     assert e[0] == m.syms[e[1]].name
 
   for e in m.compilerProcs:
-    assert e[1] >= 0 and e[1] < m.syms.len
+    #assert e[1] >= 0 and e[1] < m.syms.len
     assert e[0] == m.syms[e[1]].name
 
   checkLocalSymIds c, m, m.converters
diff --git a/compiler/ic/navigator.nim b/compiler/ic/navigator.nim
index da8e7e597..ca2f981a1 100644
--- a/compiler/ic/navigator.nim
+++ b/compiler/ic/navigator.nim
@@ -11,7 +11,7 @@
 ## IDE-like features. It uses the set of .rod files to accomplish
 ## its task. The set must cover a complete Nim project.
 
-import std/sets
+import std/[sets, tables]
 
 from std/os import nil
 from std/private/miscdollars import toLocation
diff --git a/compiler/ic/packed_ast.nim b/compiler/ic/packed_ast.nim
index 2599e07d1..392f6b325 100644
--- a/compiler/ic/packed_ast.nim
+++ b/compiler/ic/packed_ast.nim
@@ -47,6 +47,7 @@ type
     path*: NodeId
 
   PackedSym* = object
+    id*: int32
     kind*: TSymKind
     name*: LitId
     typ*: PackedItemId
@@ -71,6 +72,7 @@ type
     instantiatedFrom*: PackedItemId
 
   PackedType* = object
+    id*: int32
     kind*: TTypeKind
     callConv*: TCallingConvention
     #nodekind*: TNodeKind
diff --git a/compiler/ic/rodfiles.nim b/compiler/ic/rodfiles.nim
index 5eef3874a..ac995dd2e 100644
--- a/compiler/ic/rodfiles.nim
+++ b/compiler/ic/rodfiles.nim
@@ -19,6 +19,8 @@ from std/typetraits import supportsCopyMem
 when defined(nimPreviewSlimSystem):
   import std/[syncio, assertions]
 
+import std / tables
+
 ## Overview
 ## ========
 ## `RodFile` represents a Rod File (versioned binary format), and the
@@ -170,6 +172,18 @@ proc storeSeq*[T](f: var RodFile; s: seq[T]) =
     for i in 0..<s.len:
       storePrim(f, s[i])
 
+proc storeOrderedTable*[K, T](f: var RodFile; s: OrderedTable[K, T]) =
+  if f.err != ok: return
+  if s.len >= high(int32):
+    setError f, tooBig
+    return
+  var lenPrefix = int32(s.len)
+  if writeBuffer(f.f, addr lenPrefix, sizeof(lenPrefix)) != sizeof(lenPrefix):
+    setError f, ioFailure
+  else:
+    for _, v in s:
+      storePrim(f, v)
+
 proc loadPrim*(f: var RodFile; s: var string) =
   ## Read a string, the length was stored as a prefix
   if f.err != ok: return
@@ -211,6 +225,19 @@ proc loadSeq*[T](f: var RodFile; s: var seq[T]) =
     for i in 0..<lenPrefix:
       loadPrim(f, s[i])
 
+proc loadOrderedTable*[K, T](f: var RodFile; s: var OrderedTable[K, T]) =
+  ## `T` must be compatible with `copyMem`, see `loadPrim`
+  if f.err != ok: return
+  var lenPrefix = int32(0)
+  if readBuffer(f.f, addr lenPrefix, sizeof(lenPrefix)) != sizeof(lenPrefix):
+    setError f, ioFailure
+  else:
+    s = initOrderedTable[K, T](lenPrefix)
+    for i in 0..<lenPrefix:
+      var x = default T
+      loadPrim(f, x)
+      s[x.id] = x
+
 proc storeHeader*(f: var RodFile; cookie = defaultCookie) =
   ## stores the header which is described by `cookie`.
   if f.err != ok: return