Patch by Darin and me, reviewed by Maciej.
[WebKit-https.git] / JavaScriptCore / kjs / collector.cpp
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  *  This file is part of the KDE libraries
4  *  Copyright (C) 2003, 2004, 2005, 2006 Apple Computer, Inc.
5  *
6  *  This library is free software; you can redistribute it and/or
7  *  modify it under the terms of the GNU Lesser General Public
8  *  License as published by the Free Software Foundation; either
9  *  version 2 of the License, or (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  *  Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public
17  *  License along with this library; if not, write to the Free Software
18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19  *
20  */
21
22 #include "config.h"
23 #include "collector.h"
24
25 #include <wtf/FastMalloc.h>
26 #include <wtf/FastMallocInternal.h>
27 #include <wtf/HashCountedSet.h>
28 #include "internal.h"
29 #include "list.h"
30 #include "value.h"
31
32 #include <setjmp.h>
33 #include <algorithm>
34
35 #if PLATFORM(DARWIN)
36
37 #include <pthread.h>
38 #include <mach/mach_port.h>
39 #include <mach/task.h>
40 #include <mach/thread_act.h>
41
42 #elif PLATFORM(WIN_OS)
43
44 #include <windows.h>
45
46 #elif PLATFORM(UNIX)
47
48 #include <pthread.h>
49
50 #if HAVE(PTHREAD_NP_H)
51 #include <pthread_np.h>
52 #endif
53
54 #endif
55
56 #define DEBUG_COLLECTOR 0
57
58 using std::max;
59
60 namespace KJS {
61
62 // tunable parameters
63 const size_t MINIMUM_CELL_SIZE = 48;
64 const size_t BLOCK_SIZE = (8 * 4096);
65 const size_t SPARE_EMPTY_BLOCKS = 2;
66 const size_t MIN_ARRAY_SIZE = 14;
67 const size_t GROWTH_FACTOR = 2;
68 const size_t LOW_WATER_FACTOR = 4;
69 const size_t ALLOCATIONS_PER_COLLECTION = 1000;
70
71 // derived constants
72 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
73 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
74 const size_t CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
75
76
77
78 struct CollectorCell {
79   union {
80     double memory[CELL_ARRAY_LENGTH];
81     struct {
82       void *zeroIfFree;
83       ptrdiff_t next;
84     } freeCell;
85   } u;
86 };
87
88
89 struct CollectorBlock {
90   CollectorCell cells[CELLS_PER_BLOCK];
91   uint32_t usedCells;
92   CollectorCell *freeList;
93 };
94
95 struct CollectorHeap {
96   CollectorBlock **blocks;
97   size_t numBlocks;
98   size_t usedBlocks;
99   size_t firstBlockWithPossibleSpace;
100   
101   CollectorCell **oversizeCells;
102   size_t numOversizeCells;
103   size_t usedOversizeCells;
104
105   size_t numLiveObjects;
106   size_t numLiveObjectsAtLastCollect;
107 };
108
109 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
110
111 bool Collector::memoryFull = false;
112
113 void* Collector::allocate(size_t s)
114 {
115   assert(JSLock::lockCount() > 0);
116
117   // collect if needed
118   size_t numLiveObjects = heap.numLiveObjects;
119   size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
120   size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
121
122   if (numNewObjects >= ALLOCATIONS_PER_COLLECTION && numNewObjects >= numLiveObjectsAtLastCollect) {
123     collect();
124     numLiveObjects = heap.numLiveObjects;
125   }
126   
127   if (s > CELL_SIZE) {
128     // oversize allocator
129     size_t usedOversizeCells = heap.usedOversizeCells;
130     size_t numOversizeCells = heap.numOversizeCells;
131
132     if (usedOversizeCells == numOversizeCells) {
133       numOversizeCells = max(MIN_ARRAY_SIZE, numOversizeCells * GROWTH_FACTOR);
134       heap.numOversizeCells = numOversizeCells;
135       heap.oversizeCells = static_cast<CollectorCell **>(fastRealloc(heap.oversizeCells, numOversizeCells * sizeof(CollectorCell *)));
136     }
137     
138     void *newCell = fastMalloc(s);
139     heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
140     heap.usedOversizeCells = usedOversizeCells + 1;
141     heap.numLiveObjects = numLiveObjects + 1;
142
143     return newCell;
144   }
145   
146   // slab allocator
147   
148   size_t usedBlocks = heap.usedBlocks;
149
150   size_t i = heap.firstBlockWithPossibleSpace;
151   CollectorBlock *targetBlock;
152   size_t targetBlockUsedCells;
153   if (i != usedBlocks) {
154     targetBlock = heap.blocks[i];
155     targetBlockUsedCells = targetBlock->usedCells;
156     assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
157     while (targetBlockUsedCells == CELLS_PER_BLOCK) {
158       if (++i == usedBlocks)
159         goto allocateNewBlock;
160       targetBlock = heap.blocks[i];
161       targetBlockUsedCells = targetBlock->usedCells;
162       assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
163     }
164     heap.firstBlockWithPossibleSpace = i;
165   } else {
166 allocateNewBlock:
167     // didn't find one, need to allocate a new block
168     size_t numBlocks = heap.numBlocks;
169     if (usedBlocks == numBlocks) {
170       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
171       heap.numBlocks = numBlocks;
172       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
173     }
174
175     targetBlock = static_cast<CollectorBlock *>(fastCalloc(1, sizeof(CollectorBlock)));
176     targetBlock->freeList = targetBlock->cells;
177     targetBlockUsedCells = 0;
178     heap.blocks[usedBlocks] = targetBlock;
179     heap.usedBlocks = usedBlocks + 1;
180     heap.firstBlockWithPossibleSpace = usedBlocks;
181   }
182   
183   // find a free spot in the block and detach it from the free list
184   CollectorCell *newCell = targetBlock->freeList;
185   
186   // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized
187   // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
188   targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);
189
190   targetBlock->usedCells = targetBlockUsedCells + 1;
191   heap.numLiveObjects = numLiveObjects + 1;
192
193   return newCell;
194 }
195
196 #if USE(MULTIPLE_THREADS)
197
198 struct Collector::Thread {
199   Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
200   Thread *next;
201   pthread_t posixThread;
202   mach_port_t machThread;
203 };
204
205 pthread_key_t registeredThreadKey;
206 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
207 Collector::Thread *registeredThreads;
208   
209 static void destroyRegisteredThread(void *data) 
210 {
211   Collector::Thread *thread = (Collector::Thread *)data;
212
213   if (registeredThreads == thread) {
214     registeredThreads = registeredThreads->next;
215   } else {
216     Collector::Thread *last = registeredThreads;
217     for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
218       if (t == thread) {
219         last->next = t->next;
220           break;
221       }
222       last = t;
223     }
224   }
225
226   delete thread;
227 }
228
229 static void initializeRegisteredThreadKey()
230 {
231   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
232 }
233
234 void Collector::registerThread()
235 {
236   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
237
238   if (!pthread_getspecific(registeredThreadKey)) {
239     pthread_t pthread = pthread_self();
240     WTF::fastMallocRegisterThread(pthread);
241     Collector::Thread *thread = new Collector::Thread(pthread, pthread_mach_thread_np(pthread));
242     thread->next = registeredThreads;
243     registeredThreads = thread;
244     pthread_setspecific(registeredThreadKey, thread);
245   }
246 }
247
248 #endif
249
250 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
251
252 // cells are 8-byte aligned
253 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
254
255 void Collector::markStackObjectsConservatively(void *start, void *end)
256 {
257   if (start > end) {
258     void *tmp = start;
259     start = end;
260     end = tmp;
261   }
262
263   assert(((char *)end - (char *)start) < 0x1000000);
264   assert(IS_POINTER_ALIGNED(start));
265   assert(IS_POINTER_ALIGNED(end));
266   
267   char **p = (char **)start;
268   char **e = (char **)end;
269   
270   size_t usedBlocks = heap.usedBlocks;
271   CollectorBlock **blocks = heap.blocks;
272   size_t usedOversizeCells = heap.usedOversizeCells;
273   CollectorCell **oversizeCells = heap.oversizeCells;
274
275   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
276
277   while (p != e) {
278     char *x = *p++;
279     if (IS_CELL_ALIGNED(x) && x) {
280       for (size_t block = 0; block < usedBlocks; block++) {
281         size_t offset = x - reinterpret_cast<char *>(blocks[block]);
282         if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0)
283           goto gotGoodPointer;
284       }
285       for (size_t i = 0; i != usedOversizeCells; i++)
286         if (x == reinterpret_cast<char *>(oversizeCells[i]))
287           goto gotGoodPointer;
288       continue;
289
290 gotGoodPointer:
291       if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
292         JSCell *imp = reinterpret_cast<JSCell *>(x);
293         if (!imp->marked())
294           imp->mark();
295       }
296     }
297   }
298 }
299
300 void Collector::markCurrentThreadConservatively()
301 {
302     jmp_buf registers;
303     setjmp(registers);
304
305 #if PLATFORM(DARWIN)
306     pthread_t thread = pthread_self();
307     void *stackBase = pthread_get_stackaddr_np(thread);
308 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
309     NT_TIB *pTib;
310     __asm {
311         MOV EAX, FS:[18h]
312         MOV pTib, EAX
313     }
314     void *stackBase = (void *)pTib->StackBase;
315 #elif PLATFORM(UNIX)
316     static void *stackBase = 0;
317     static pthread_t stackThread;
318     pthread_t thread = pthread_self();
319     if (stackBase == 0 || thread != stackThread) {
320         pthread_attr_t sattr;
321 #if HAVE(PTHREAD_NP_H)
322         // e.g. on FreeBSD 5.4, neundorf@kde.org
323         pthread_attr_get_np(thread, &sattr);
324 #else
325         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
326         pthread_getattr_np(thread, &sattr);
327 #endif
328         // Should work but fails on Linux (?)
329         //  pthread_attr_getstack(&sattr, &stackBase, &stackSize);
330         pthread_attr_getstackaddr(&sattr, &stackBase);
331         assert(stackBase);
332         stackThread = thread;
333     }
334 #else
335 #error Need a way to get the stack base on this platform
336 #endif
337
338     void *dummy;
339     void *stackPointer = &dummy;
340
341     markStackObjectsConservatively(stackPointer, stackBase);
342 }
343
344 #if USE(MULTIPLE_THREADS)
345
346 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
347
348 void Collector::markOtherThreadConservatively(Thread *thread)
349 {
350   thread_suspend(thread->machThread);
351
352 #if PLATFORM(X86)
353   i386_thread_state_t regs;
354   unsigned user_count = sizeof(regs)/sizeof(int);
355   thread_state_flavor_t flavor = i386_THREAD_STATE;
356 #elif PLATFORM(X86_64)
357   x86_thread_state64_t  regs;
358   unsigned user_count = x86_THREAD_STATE64_COUNT;
359   thread_state_flavor_t flavor = x86_THREAD_STATE64;
360 #elif PLATFORM(PPC)
361   ppc_thread_state_t  regs;
362   unsigned user_count = PPC_THREAD_STATE_COUNT;
363   thread_state_flavor_t flavor = PPC_THREAD_STATE;
364 #elif PLATFORM(PPC64)
365   ppc_thread_state64_t  regs;
366   unsigned user_count = PPC_THREAD_STATE64_COUNT;
367   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
368 #else
369 #error Unknown Architecture
370 #endif
371   // get the thread register state
372   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
373   
374   // scan the registers
375   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
376    
377   // scan the stack
378 #if PLATFORM(X86) && __DARWIN_UNIX03
379   markStackObjectsConservatively((void *)regs.__esp, pthread_get_stackaddr_np(thread->posixThread));
380 #elif PLATFORM(X86)
381   markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
382 #elif PLATFORM(X86_64) && __DARWIN_UNIX03
383   markStackObjectsConservatively((void *)regs.__rsp, pthread_get_stackaddr_np(thread->posixThread));
384 #elif PLATFORM(X86_64)
385   markStackObjectsConservatively((void *)regs.rsp, pthread_get_stackaddr_np(thread->posixThread));
386 #elif (PLATFORM(PPC) || PLATFORM(PPC64)) && __DARWIN_UNIX03
387   markStackObjectsConservatively((void *)regs.__r1, pthread_get_stackaddr_np(thread->posixThread));
388 #elif PLATFORM(PPC) || PLATFORM(PPC64)
389   markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
390 #else
391 #error Unknown Architecture
392 #endif
393
394   thread_resume(thread->machThread);
395 }
396
397 #endif
398
399 void Collector::markStackObjectsConservatively()
400 {
401   markCurrentThreadConservatively();
402
403 #if USE(MULTIPLE_THREADS)
404   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
405     if (thread->posixThread != pthread_self()) {
406       markOtherThreadConservatively(thread);
407     }
408   }
409 #endif
410 }
411
412 typedef HashCountedSet<JSCell *> ProtectCounts;
413
414 static ProtectCounts& protectedValues()
415 {
416     static ProtectCounts pv;
417     return pv;
418 }
419
420 void Collector::protect(JSValue *k)
421 {
422     assert(k);
423     assert(JSLock::lockCount() > 0);
424
425     if (JSImmediate::isImmediate(k))
426       return;
427
428     protectedValues().add(k->downcast());
429 }
430
431 void Collector::unprotect(JSValue *k)
432 {
433     assert(k);
434     assert(JSLock::lockCount() > 0);
435
436     if (JSImmediate::isImmediate(k))
437       return;
438
439     protectedValues().remove(k->downcast());
440 }
441
442 void Collector::markProtectedObjects()
443 {
444   ProtectCounts& pv = protectedValues();
445   ProtectCounts::iterator end = pv.end();
446   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
447     JSCell *val = it->first;
448     if (!val->marked())
449       val->mark();
450   }
451 }
452
453 bool Collector::collect()
454 {
455   assert(JSLock::lockCount() > 0);
456
457 #if USE(MULTIPLE_THREADS)
458     bool currentThreadIsMainThread = !pthread_is_threaded_np() || pthread_main_np();
459 #else
460     bool currentThreadIsMainThread = true;
461 #endif
462     
463   if (Interpreter::s_hook) {
464     Interpreter* scr = Interpreter::s_hook;
465     do {
466       scr->mark(currentThreadIsMainThread);
467       scr = scr->next;
468     } while (scr != Interpreter::s_hook);
469   }
470
471   // MARK: first mark all referenced objects recursively starting out from the set of root objects
472
473   markStackObjectsConservatively();
474   markProtectedObjects();
475   List::markProtectedLists();
476
477   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
478   
479   size_t emptyBlocks = 0;
480   size_t numLiveObjects = heap.numLiveObjects;
481
482   for (size_t block = 0; block < heap.usedBlocks; block++) {
483     CollectorBlock *curBlock = heap.blocks[block];
484
485     size_t usedCells = curBlock->usedCells;
486     CollectorCell *freeList = curBlock->freeList;
487
488     if (usedCells == CELLS_PER_BLOCK) {
489       // special case with a block where all cells are used -- testing indicates this happens often
490       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
491         CollectorCell *cell = curBlock->cells + i;
492         JSCell *imp = reinterpret_cast<JSCell *>(cell);
493         if (imp->m_marked) {
494           imp->m_marked = false;
495         } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
496           // special case for allocated but uninitialized object
497           // (We don't need this check earlier because nothing prior this point assumes the object has a valid vptr.)
498           if (cell->u.freeCell.zeroIfFree == 0)
499             continue;
500
501           imp->~JSCell();
502           --usedCells;
503           --numLiveObjects;
504
505           // put cell on the free list
506           cell->u.freeCell.zeroIfFree = 0;
507           cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
508           freeList = cell;
509         }
510       }
511     } else {
512       size_t minimumCellsToProcess = usedCells;
513       for (size_t i = 0; (i < minimumCellsToProcess) & (i < CELLS_PER_BLOCK); i++) {
514         CollectorCell *cell = curBlock->cells + i;
515         if (cell->u.freeCell.zeroIfFree == 0) {
516           ++minimumCellsToProcess;
517         } else {
518           JSCell *imp = reinterpret_cast<JSCell *>(cell);
519           if (imp->m_marked) {
520             imp->m_marked = false;
521           } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
522             imp->~JSCell();
523             --usedCells;
524             --numLiveObjects;
525
526             // put cell on the free list
527             cell->u.freeCell.zeroIfFree = 0;
528             cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
529             freeList = cell;
530           }
531         }
532       }
533     }
534     
535     curBlock->usedCells = usedCells;
536     curBlock->freeList = freeList;
537
538     if (usedCells == 0) {
539       emptyBlocks++;
540       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
541 #if !DEBUG_COLLECTOR
542         fastFree(curBlock);
543 #endif
544         // swap with the last block so we compact as we go
545         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
546         heap.usedBlocks--;
547         block--; // Don't move forward a step in this case
548
549         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
550           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
551           heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
552         }
553       }
554     }
555   }
556
557   if (heap.numLiveObjects != numLiveObjects)
558     heap.firstBlockWithPossibleSpace = 0;
559   
560   size_t cell = 0;
561   while (cell < heap.usedOversizeCells) {
562     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
563     
564     if (!imp->m_marked && (currentThreadIsMainThread || imp->m_destructorIsThreadSafe)) {
565       imp->~JSCell();
566 #if DEBUG_COLLECTOR
567       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
568 #else
569       fastFree(imp);
570 #endif
571
572       // swap with the last oversize cell so we compact as we go
573       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
574
575       heap.usedOversizeCells--;
576       numLiveObjects--;
577
578       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
579         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
580         heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
581       }
582     } else {
583       imp->m_marked = false;
584       cell++;
585     }
586   }
587   
588   bool deleted = heap.numLiveObjects != numLiveObjects;
589
590   heap.numLiveObjects = numLiveObjects;
591   heap.numLiveObjectsAtLastCollect = numLiveObjects;
592   
593   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
594
595   return deleted;
596 }
597
598 size_t Collector::size() 
599 {
600   return heap.numLiveObjects; 
601 }
602
603 #ifdef KJS_DEBUG_MEM
604 void Collector::finalCheck()
605 {
606 }
607 #endif
608
609 size_t Collector::numInterpreters()
610 {
611   size_t count = 0;
612   if (Interpreter::s_hook) {
613     Interpreter* scr = Interpreter::s_hook;
614     do {
615       ++count;
616       scr = scr->next;
617     } while (scr != Interpreter::s_hook);
618   }
619   return count;
620 }
621
622 size_t Collector::numProtectedObjects()
623 {
624   return protectedValues().size();
625 }
626
627 static const char *typeName(JSCell *val)
628 {
629   const char *name = "???";
630   switch (val->type()) {
631     case UnspecifiedType:
632       break;
633     case UndefinedType:
634       name = "undefined";
635       break;
636     case NullType:
637       name = "null";
638       break;
639     case BooleanType:
640       name = "boolean";
641       break;
642     case StringType:
643       name = "string";
644       break;
645     case NumberType:
646       name = "number";
647       break;
648     case ObjectType: {
649       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
650       name = info ? info->className : "Object";
651       break;
652     }
653     case GetterSetterType:
654       name = "gettersetter";
655       break;
656   }
657   return name;
658 }
659
660 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
661 {
662     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
663
664     ProtectCounts& pv = protectedValues();
665     ProtectCounts::iterator end = pv.end();
666     for (ProtectCounts::iterator it = pv.begin(); it != end; ++it)
667         counts->add(typeName(it->first));
668
669     return counts;
670 }
671
672 } // namespace KJS