6LeakCanary2Analyze

graph TB
subgraph binarySearch二分查找
SortedBytesMap
end

subgraph 广度优先遍历
State.findPathsFromGcRoots:BFS
end

HeapAnalyzer.analyze-->Hprof.open:HprofFile
HeapAnalyzer.analyze-->HprofHeapGraph.indexHprof
HeapAnalyzer.analyze-->FindLeakInput.analyzeGraph
HprofHeapGraph.indexHprof-->reader.readHprofRecords-->|callback HprofRecord|indexBuilderListener.onHprofRecord-->UnsortedByteEntries("UnsortedByteEntries,ScatterMap")
HprofHeapGraph.indexHprof-->indexBuilderListener.buildIndex-->|Sort entries by keys|SortedBytesMap-->HprofInMemoryIndex-->HprofHeapGraph
FindLeakInput.analyzeGraph-->FindLeakInput.findLeaks
FindLeakInput.findLeaks-->State.findPathsFromGcRoots:BFS-->|start by enqueueGcRoots|findObjectById("graph.findObjectById")-->readFieldsAndEnqueue

graph TB
HprofFile-->HprofRecord
HprofRecord-->UnsortedByteEntries("UnsortedByteEntries(class,instance,objectArray,primitiveArray)")
UnsortedByteEntries-->|Sort entries by keys|SortedBytesMap(SortedBytesMap: get perform binarySearch)
SortedBytesMap-->HprofInMemoryIndex
SortedBytesMap-->|get return|ByteSubArray
ByteSubArray-->|indexedObjectOrNull|IndexedObject
IndexedObject-->|wrapIndexedObject|HeapObject
HprofRecord-->ScatterMap("ScatterMap(hprofStringCache, classNames)")
ScatterMap-->HprofInMemoryIndex
HprofInMemoryIndex-->HprofHeapGraph
LruCache:objectCache-->|cached when readObjectRecord|HprofHeapGraph

//ScatterMap contains: classNames and hprofStringCache

// LRU cache size of 3000 is a sweet spot to balance hits vs memory usage.
// This is based on running InstrumentationLeakDetectorTest a bunch of time on a
// Pixel 2 XL API 28. Hit count was ~120K, miss count ~290K
private val objectCache = LruCache<Long, ObjectRecord>(3000)

graph LR
HprofRecord-->StringRecord
HprofRecord-->LoadClassRecord
HprofRecord-->StackFrameRecord
HprofRecord-->StackTraceRecord
HprofRecord-->HeapDumpRecord
HeapDumpRecord-->GcRootRecord
HeapDumpRecord-->ObjectRecord
ObjectRecord-->ClassDumpRecord
ObjectRecord-->InstanceDumpRecord
ObjectRecord-->ObjectArrayDumpRecord
ObjectRecord-->PrimitiveArrayDumpRecord

graph LR
ReferencePathNode-->RootNode
ReferencePathNode-->ChildNode
RootNode-->LibraryLeakRootNode
RootNode-->NormalRootNode
ChildNode-->NormalNode:ContainsParent
ChildNode-->LibraryLeakChildNode:ContainsParent

/**
 * Analyzes heap dumps to look for leaks.
 */

/**
 * Searches the heap dump for leaking instances and then computes the shortest strong reference
 * path from those instances to the GC roots.
 */
fun analyze(
  heapDumpFile: File,
  leakingObjectFinder: LeakingObjectFinder,
  referenceMatchers: List<ReferenceMatcher> = emptyList(),
  computeRetainedHeapSize: Boolean = false,
  objectInspectors: List<ObjectInspector> = emptyList(),
  metadataExtractor: MetadataExtractor = MetadataExtractor.NO_OP,
  proguardMapping: ProguardMapping? = null
): HeapAnalysis {
  
        Hprof.open(heapDumpFile)
          .use { hprof ->
            val graph = HprofHeapGraph.indexHprof(hprof, proguardMapping)
            val helpers =
              FindLeakInput(graph, referenceMatchers, computeRetainedHeapSize, objectInspectors)
            helpers.analyzeGraph(
                metadataExtractor, leakingObjectFinder, heapDumpFile, analysisStartNanoTime
            )
          }
 

private class FindLeakInput(
  val graph: HeapGraph,
  val referenceMatchers: List<ReferenceMatcher>,
  val computeRetainedHeapSize: Boolean,
  val objectInspectors: List<ObjectInspector>
)

private fun FindLeakInput.analyzeGraph(
  metadataExtractor: MetadataExtractor,
  leakingObjectFinder: LeakingObjectFinder,
  heapDumpFile: File,
  analysisStartNanoTime: Long
): HeapAnalysisSuccess {
  listener.onAnalysisProgress(EXTRACTING_METADATA)
  val metadata = metadataExtractor.extractMetadata(graph)

  listener.onAnalysisProgress(FINDING_RETAINED_OBJECTS)
  val leakingObjectIds = leakingObjectFinder.findLeakingObjectIds(graph)

  val (applicationLeaks, libraryLeaks) = findLeaks(leakingObjectIds)

  return HeapAnalysisSuccess(
      heapDumpFile = heapDumpFile,
      createdAtTimeMillis = System.currentTimeMillis(),
      analysisDurationMillis = since(analysisStartNanoTime),
      metadata = metadata,
      applicationLeaks = applicationLeaks,
      libraryLeaks = libraryLeaks
  )
}

private fun FindLeakInput.findLeaks(leakingObjectIds: Set<Long>): Pair<List<ApplicationLeak>, List<LibraryLeak>> {
  val pathFinder = PathFinder(graph, listener, referenceMatchers)
  val pathFindingResults =
    pathFinder.findPathsFromGcRoots(leakingObjectIds, computeRetainedHeapSize)

  SharkLog.d { "Found ${leakingObjectIds.size} retained objects" }
  return buildLeakTraces(pathFindingResults)
}

/**
 * Finds the shortest path from leaking references to a gc root, first ignoring references
 * identified as "to visit last" and then visiting them as needed if no path is
 * found.
 */
internal class PathFinder(
  
private class State(
    val leakingObjectIds: Set<Long>,
    val sizeOfObjectInstances: Int,
    val computeRetainedHeapSize: Boolean
  ) {
      /** Set of objects to visit */
    val toVisitQueue: Deque<ReferencePathNode> = ArrayDeque()

    /**
     * Objects to visit when [toVisitQueue] is empty. Should contain [JavaFrame] gc roots first,
     * then [LibraryLeakNode].
     */
    val toVisitLastQueue: Deque<ReferencePathNode> = ArrayDeque()

    /**
     * Enables fast checking of whether a node is already in the queue.
     */
    val toVisitSet = HashSet<Long>()
    val toVisitLastSet = HashSet<Long>()

    val visitedSet = LongScatterSet()

fun findPathsFromGcRoots(
  leakingObjectIds: Set<Long>,
  computeRetainedHeapSize: Boolean
): PathFindingResults {
  listener.onAnalysisProgress(FINDING_PATHS_TO_RETAINED_OBJECTS)

  val sizeOfObjectInstances = determineSizeOfObjectInstances(graph)

  val state = State(leakingObjectIds, sizeOfObjectInstances, computeRetainedHeapSize)

  return state.findPathsFromGcRoots()
}

/**
 * Map of objects to their leaking dominator.
 
key: currentObjectId --> value: directDominatorObjectId

 * If an object has been added to [toVisitSet] or [visitedSet] and is missing from
 * [dominatedObjectIds] then it's considered "undomitable" ie it is dominated by gc roots
 * and cannot be dominated by a leaking object.
 */
val dominatedObjectIds = LongLongScatterMap()

//main algorithm to find the shortest path to GCRoot, BFS is useful because when the first time we visit leakObject, the shortest path is found. Use ChildNode to find the parent ReferencePathNode
private fun State.findPathsFromGcRoots(): PathFindingResults {
  //iterate different type GcRoot and enqueue them into toVisitQueue or toVisitLastQueue
  enqueueGcRoots()
  
      val shortestPathsToLeakingObjects = mutableListOf<ReferencePathNode>()
    visitingQueue@ while (queuesNotEmpty) {
      val node = poll()

      if (checkSeen(node)) {
        throw IllegalStateException(
            "Node $node objectId=${node.objectId} should not be enqueued when already visited or enqueued"
        )
      }

      if (node.objectId in leakingObjectIds) {
        shortestPathsToLeakingObjects.add(node)
        // Found all refs, stop searching (unless computing retained size)
        if (shortestPathsToLeakingObjects.size == leakingObjectIds.size) {
          if (computeRetainedHeapSize) {
            listener.onAnalysisProgress(FINDING_DOMINATORS)
          } else {
            break@visitingQueue
          }
        }
      }

      when (val heapObject = graph.findObjectById(node.objectId)) {
        is HeapClass -> visitClassRecord(heapObject, node)
        is HeapInstance -> visitInstance(heapObject, node)
        is HeapObjectArray -> visitObjectArray(heapObject, node)
      }
    }
    return PathFindingResults(shortestPathsToLeakingObjects, dominatedObjectIds)
}

private fun State.visitInstance(
  instance: HeapInstance,
  parent: ReferencePathNode
) {
      val fieldNamesAndValues = instance.readFields()
        .filter { it.value.isNonNullReference }//only reference type need to be iterate, primitive is not.
        .toMutableList()

    fieldNamesAndValues.sortBy { it.name }

    fieldNamesAndValues.forEach { field ->
      val objectId = field.value.asObjectId!!
      if (computeRetainedHeapSize) {
        updateDominatorWithSkips(parent.objectId, objectId)
      }

      val node = when (val referenceMatcher = fieldReferenceMatchers[field.name]) {
        null -> NormalNode(
            objectId = objectId,
            parent = parent,
            refFromParentType = INSTANCE_FIELD,
            refFromParentName = field.name
        )
        is LibraryLeakReferenceMatcher ->
          LibraryLeakChildNode(
              objectId = objectId,
              parent = parent,
              refFromParentType = INSTANCE_FIELD,
              refFromParentName = field.name,
              matcher = referenceMatcher
          )
        is IgnoredReferenceMatcher -> null
      }
      if (node != null) {
        enqueue(node)
      }
    }

@Suppress("ReturnCount")
private fun State.enqueue(
  node: ReferencePathNode
) {
  
     val visitLast =
      node is LibraryLeakNode ||
          // We deprioritize thread objects because on Lollipop the thread local values are stored
          // as a field.
          (node is RootNode && node.gcRoot is ThreadObject) ||
          (node is NormalNode && node.parent is RootNode && node.parent.gcRoot is JavaFrame)

    if (toVisitLastSet.contains(node.objectId)) {
      // Already enqueued => shorter or equal distance amongst library leak ref patterns.
      if (visitLast) {
        return
      } else {
        toVisitQueue.add(node)
        toVisitSet.add(node.objectId)
        val nodeToRemove = toVisitLastQueue.first { it.objectId == node.objectId }
        toVisitLastQueue.remove(nodeToRemove)
        toVisitLastSet.remove(node.objectId)
        return
      }
    }
  
      val isLeakingObject = node.objectId in leakingObjectIds

    if (!isLeakingObject) {
      val skip = when (val graphObject = graph.findObjectById(node.objectId)) {
        is HeapClass -> false
        is HeapInstance ->
          when {
            graphObject.isPrimitiveWrapper -> true
            graphObject.instanceClassName == "java.lang.String" -> true
            graphObject.instanceClass.instanceByteSize <= sizeOfObjectInstances -> true
            else -> false
          }
        is HeapObjectArray -> when {
          graphObject.isPrimitiveWrapperArray -> true
          else -> false
        }
        is HeapPrimitiveArray -> true
      }
      if (skip) {
        return
      }
    }
    if (visitLast) {
      toVisitLastQueue.add(node)
      toVisitLastSet.add(node.objectId)
    } else {
      toVisitQueue.add(node)
      toVisitSet.add(node.objectId)
    }

private fun State.enqueueGcRoots() {
  val gcRoots = sortedGcRoots()
  ......
}

private fun State.updateDominator(//contains very detail doc about the algorithm to generate dominator tree

/**
 * A [HeapGraph] that reads from an indexed [Hprof]. Create a new instance with [indexHprof].
 */

class HprofHeapGraph internal constructor(
  private val hprof: Hprof,
  private val index: HprofInMemoryIndex
) : HeapGraph {

companion object {
  fun indexHprof(
    hprof: Hprof,
    proguardMapping: ProguardMapping? = null,
    indexedGcRootTypes: Set<KClass<out GcRoot>> = setOf(
        JniGlobal::class,
        JavaFrame::class,
        JniLocal::class,
        MonitorUsed::class,
        NativeStack::class,
        StickyClass::class,
        ThreadBlock::class,
        // ThreadObject points to threads, which we need to find the thread that a JavaLocalPattern
        // belongs to
        ThreadObject::class,
        JniMonitor::class
        /*
        Not included here:

        VmInternal: Ignoring because we've got 150K of it, but is this the right thing
        to do? What's VmInternal exactly? History does not go further than
        https://android.googlesource.com/platform/dalvik2/+/refs/heads/master/hit/src/com/android/hit/HprofParser.java#77
        We should log to figure out what objects VmInternal points to.

        ReferenceCleanup: We used to keep it, but the name doesn't seem like it should create a leak.

        Unknown: it's unknown, should we care?

        We definitely don't care about those for leak finding: InternedString, Finalizing, Debugger, Unreachable
         */
    )
  ): HeapGraph {
    val index = HprofInMemoryIndex.createReadingHprof(hprof, proguardMapping, indexedGcRootTypes)
    return HprofHeapGraph(hprof, index)
  }
}

override fun findClassByName(className: String): HeapClass? {
  val classId = index.classId(className)
  return if (classId == null) {
    null
  } else {
    return findObjectById(classId) as HeapClass
  }
}

override fun findObjectById(objectId: Long): HeapObject {
  return findObjectByIdOrNull(objectId) ?: throw IllegalArgumentException(
      "Object id $objectId not found in heap dump."
  )
}

override fun findObjectByIdOrNull(objectId: Long): HeapObject? {
  if (objectId == javaLangObjectClass?.objectId) return javaLangObjectClass

  val indexedObject = index.indexedObjectOrNull(objectId) ?: return null
  return wrapIndexedObject(indexedObject, objectId)
}

private fun wrapIndexedObject(
  indexedObject: IndexedObject,
  objectId: Long
): HeapObject {
  return when (indexedObject) {
    is IndexedClass -> HeapClass(this, indexedObject, objectId)
    is IndexedInstance -> {
      val isPrimitiveWrapper = index.primitiveWrapperTypes.contains(indexedObject.classId)
      HeapInstance(this, indexedObject, objectId, isPrimitiveWrapper)
    }
    is IndexedObjectArray -> {
      val isPrimitiveWrapperArray =
        index.primitiveWrapperTypes.contains(indexedObject.arrayClassId)
      HeapObjectArray(this, indexedObject, objectId, isPrimitiveWrapperArray)
    }
    is IndexedPrimitiveArray -> HeapPrimitiveArray(this, indexedObject, objectId)
  }
}

fun createReadingHprof(
  hprof: Hprof,
  proguardMapping: ProguardMapping?,
  indexedGcRootTypes: Set<KClass<out GcRoot>>
): HprofInMemoryIndex {
  val recordTypes = setOf(
      StringRecord::class,
      LoadClassRecord::class,
      ClassSkipContentRecord::class,
      InstanceSkipContentRecord::class,
      ObjectArraySkipContentRecord::class,
      PrimitiveArraySkipContentRecord::class,
      GcRootRecord::class
  )
  val reader = hprof.reader

   // First pass to count and correctly size arrays once and for all.
      var classCount = 0
      var instanceCount = 0
      var objectArrayCount = 0
      var primitiveArrayCount = 0
      reader.readHprofRecords(setOf(
          LoadClassRecord::class,
          InstanceSkipContentRecord::class,
          ObjectArraySkipContentRecord::class,
          PrimitiveArraySkipContentRecord::class
      ), OnHprofRecordListener { position, record ->
        when (record) {
          is LoadClassRecord -> classCount++
          is InstanceSkipContentRecord -> instanceCount++
          is ObjectArraySkipContentRecord -> objectArrayCount++
          is PrimitiveArraySkipContentRecord -> primitiveArrayCount++
        }
      })

      hprof.moveReaderTo(reader.startPosition)
      val indexBuilderListener =
        Builder(
            reader.identifierByteSize == 8, hprof.fileLength, classCount, instanceCount,
            objectArrayCount, primitiveArrayCount, indexedGcRootTypes.map { it.java }
            .toSet()
        )

      reader.readHprofRecords(recordTypes, indexBuilderListener)

      return indexBuilderListener.buildIndex(proguardMapping)

/**
 * Map of string id to string
 * This currently keeps all the hprof strings that we could care about: class names,
 * static field names and instance fields names
 */
// TODO Replacing with a radix trie reversed into a sparse array of long to trie leaf could save
// memory. Can be stored as 3 arrays: array of keys, array of values which are indexes into
// a large array of string bytes. Each "entry" consists of a size, the index of the previous
// segment and then the segment content.

private val hprofStringCache = LongObjectScatterMap<String>()

/**
 * class id to string id
 */
private val classNames = LongLongScatterMap(expectedElements = classCount)

private val classIndex = UnsortedByteEntries(
    bytesPerValue = positionSize + identifierSize + 4,
    longIdentifiers = longIdentifiers,
    initialCapacity = classCount
)
private val instanceIndex = UnsortedByteEntries(
    bytesPerValue = positionSize + identifierSize,
    longIdentifiers = longIdentifiers,
    initialCapacity = instanceCount
)
private val objectArrayIndex = UnsortedByteEntries(
    bytesPerValue = positionSize + identifierSize,
    longIdentifiers = longIdentifiers,
    initialCapacity = objectArrayCount
)
private val primitiveArrayIndex = UnsortedByteEntries(
    bytesPerValue = positionSize + 1,
    longIdentifiers = longIdentifiers,
    initialCapacity = primitiveArrayCount
)

  override fun onHprofRecord(
      position: Long,
      record: HprofRecord
    ) {
      when (record) {
        is StringRecord -> {
          if (PRIMITIVE_WRAPPER_TYPES.contains(record.string)) {
            primitiveWrapperClassNames.add(record.id)
          }
          // JVM heap dumps use "/" for package separators (vs "." for Android heap dumps)
          hprofStringCache[record.id] = record.string.replace('/', '.')
        }
        is LoadClassRecord -> {
          classNames[record.id] = record.classNameStringId
          if (primitiveWrapperClassNames.contains(record.classNameStringId)) {
            primitiveWrapperTypes.add(record.id)
          }
        }
        is GcRootRecord -> {
          val gcRoot = record.gcRoot
          if (gcRoot.id != ValueHolder.NULL_REFERENCE
              && indexedGcRootsTypes.contains(gcRoot.javaClass)
          ) {
            gcRoots += gcRoot
          }
        }
        is ClassSkipContentRecord -> {
          classIndex.append(record.id)//write id in an entry
              .apply {//write value bytes
                writeTruncatedLong(position, positionSize)
                writeId(record.superclassId)
                writeInt(record.instanceSize)
              }
        }
        is InstanceSkipContentRecord -> {
          instanceIndex.append(record.id)
              .apply {
                writeTruncatedLong(position, positionSize)
                writeId(record.classId)
              }
        }
        is ObjectArraySkipContentRecord -> {
          objectArrayIndex.append(record.id)
              .apply {
                writeTruncatedLong(position, positionSize)
                writeId(record.arrayClassId)
              }
        }
        is PrimitiveArraySkipContentRecord -> {
          primitiveArrayIndex.append(record.id)
              .apply {
                writeTruncatedLong(position, positionSize)
                writeByte(record.type.ordinal.toByte())
              }
        }
      }
    }

fun buildIndex(
  proguardMapping: ProguardMapping?
): HprofInMemoryIndex {
  val sortedInstanceIndex = instanceIndex.moveToSortedMap()
  val sortedObjectArrayIndex = objectArrayIndex.moveToSortedMap()
  val sortedPrimitiveArrayIndex = primitiveArrayIndex.moveToSortedMap()
  val sortedClassIndex = classIndex.moveToSortedMap()
  // Passing references to avoid copying the underlying data structures.
  return HprofInMemoryIndex(
      positionSize,
      hprofStringCache, classNames, sortedClassIndex, sortedInstanceIndex,
      sortedObjectArrayIndex,
      sortedPrimitiveArrayIndex, gcRoots,
      proguardMapping,
      primitiveWrapperTypes
  )
}

fun indexedObjectOrNull(objectId: Long): IndexedObject? {
  var array: ByteSubArray? = classIndex[objectId]
  if (array != null) {
    return IndexedClass(
        position = array.readTruncatedLong(positionSize),
        superclassId = array.readId(),
        instanceSize = array.readInt()
    )
  }
  array = instanceIndex[objectId]
  if (array != null) {
    return IndexedInstance(
        position = array.readTruncatedLong(positionSize),
        classId = array.readId()
    )
  }
   array = objectArrayIndex[objectId]
    if (array != null) {
      return IndexedObjectArray(
          position = array.readTruncatedLong(positionSize),
          arrayClassId = array.readId()
      )
    }
    array = primitiveArrayIndex[objectId]
    if (array != null) {
      return IndexedPrimitiveArray(
          position = array.readTruncatedLong(positionSize),
          primitiveType = PrimitiveType.values()[array.readByte()
              .toInt()]
      )
    }
    return null
  }

/**
 * Reads all hprof records from [source].
 * Assumes the [reader] was has a source that currently points to the start position of hprof
 * records.
 */
@Suppress("ComplexMethod", "LongMethod")
fun readHprofRecords(
  recordTypes: Set<KClass<out HprofRecord>>,
  listener: OnHprofRecordListener
) {
  while (!exhausted()) {
      // type of the record
      val tag = readUnsignedByte()

      // number of microseconds since the time stamp in the header
      skip(intByteSize)

      // number of bytes that follow and belong to this record
      val length = readUnsignedInt()

      when (tag) {
        STRING_IN_UTF8 -> {
          if (readStringRecord) {
            val recordPosition = position
            val id = readId()
            val stringLength = length - identifierByteSize
            val string = readUtf8(stringLength)
            val record = StringRecord(id, string)
            listener.onHprofRecord(recordPosition, record)
          } else {
            skip(length)
          }
        }
        LOAD_CLASS -> {
          if (readLoadClassRecord) {
            val recordPosition = position
            val classSerialNumber = readInt()
            val id = readId()
            val stackTraceSerialNumber = readInt()
            val classNameStringId = readId()
            reusedLoadClassRecord.apply {
              this.classSerialNumber = classSerialNumber
              this.id = id
              this.stackTraceSerialNumber = stackTraceSerialNumber
              this.classNameStringId = classNameStringId
            }
            listener.onHprofRecord(recordPosition, reusedLoadClassRecord)
          } else {
            skip(length)
          }
        }
        STACK_FRAME -> {}
        STACK_TRACE -> {}
        HEAP_DUMP, HEAP_DUMP_SEGMENT -> {
          val heapDumpStart = position
          var previousTag = 0
          var previousTagPosition = 0L
          while (position - heapDumpStart < length) {
            val heapDumpTagPosition = position
            val heapDumpTag = readUnsignedByte()//position increase

            when (heapDumpTag) {
              ROOT_UNKNOWN -> {
                if (readGcRootRecord) {
                  val recordPosition = position
                  val record = GcRootRecord(gcRoot = Unknown(id = readId()))
                  listener.onHprofRecord(recordPosition, record)
                } else {
                  skip(identifierByteSize)//position increase
                }
              }
              ROOT_JNI_GLOBAL -> {
                if (readGcRootRecord) {
                  val recordPosition = position
                  val gcRootRecord =
                    GcRootRecord(gcRoot = JniGlobal(id = readId(), jniGlobalRefId = readId()))
                  listener.onHprofRecord(recordPosition, gcRootRecord)
                } else {
                  skip(identifierByteSize + identifierByteSize)
                }
              }
        }
        HEAP_DUMP_END -> {
          if (readHeapDumpEndRecord) {
            val recordPosition = position
            val record = HeapDumpEndRecord
            listener.onHprofRecord(recordPosition, record)
          }
        }
        else -> {
          skip(length)
        }

/**
 * A Hprof record. These data structure map 1:1 with how records are written in hprof files.
 */
sealed class HprofRecord {
    class StringRecord(
    val id: Long,
    val string: String
  ) : HprofRecord()
  
    class LoadClassRecord(
    classSerialNumber: Int,
    id: Long,
    stackTraceSerialNumber: Int,
    classNameStringId: Long
  ) : HprofRecord() {
      ......

sealed class ObjectRecord : HeapDumpRecord() {
  
    class ClassDumpRecord(
        val id: Long,
        val stackTraceSerialNumber: Int,
        val superclassId: Long,
        val classLoaderId: Long,
        val signersId: Long,
        val protectionDomainId: Long,
        val instanceSize: Int,
        val staticFields: List<StaticFieldRecord>,
        val fields: List<FieldRecord>
      ) : ObjectRecord() {
        }
  
        class InstanceDumpRecord(
        val id: Long,
        val stackTraceSerialNumber: Int,
        val classId: Long,
        /**
         * Instance field values (this class, followed by super class, etc)
         */
        val fieldValues: ByteArray
      ) : ObjectRecord()
  
  
        class ObjectArrayDumpRecord(
        val id: Long,
        val stackTraceSerialNumber: Int,
        val arrayClassId: Long,
        val elementIds: LongArray
      ) : ObjectRecord()
  
  sealed class PrimitiveArrayDumpRecord : ObjectRecord() {
  }

/**
 * An object in the heap dump.
 */

/**
 * This [HeapObject] as a [HeapClass] if it is one, or null otherwise
 */
val asClass: HeapClass?
  get() = if (this is HeapClass) this else null

/**
 * This [HeapObject] as a [HeapInstance] if it is one, or null otherwise
 */
val asInstance: HeapInstance?
  get() = if (this is HeapInstance) this else null



  /**
   * A class in the heap dump.
   */
  class HeapClass internal constructor(
    private val hprofGraph: HprofHeapGraph,
    private val indexedObject: IndexedClass,
    override val objectId: Long
  ) : HeapObject() {
        /**
     * Returns a [HeapField] object that reflects the specified declared
     * field of the class represented by this [HeapClass] object, or null if this field does not
     * exist. The [name] parameter specifies the simple name of the desired field.
     *
     * Also available as a convenience operator: [get]
     *
     * This may trigger IO reads.
     */
    fun readStaticField(fieldName: String): HeapField? {
      for (fieldRecord in readRecord().staticFields) {
        if (hprofGraph.staticFieldName(objectId, fieldRecord) == fieldName) {
          return HeapField(
              this, hprofGraph.staticFieldName(objectId, fieldRecord),
              HeapValue(hprofGraph, fieldRecord.value)
          )
        }
      }
      return null
    }
  }


  /**
   * An instance in the heap dump.
   */
  class HeapInstance internal constructor(
    private val hprofGraph: HprofHeapGraph,
    internal val indexedObject: IndexedInstance,
    override val objectId: Long,
    /**
     * Whether this is an instance of a primitive wrapper type.
     */
    val isPrimitiveWrapper: Boolean
  ) : HeapObject() {
        /**
     * Returns a [HeapField] object that reflects the specified declared
     * field of the instance represented by this [HeapInstance] object, or null if this field does
     * not exist. The [declaringClassName] specifies the class in which the desired field is
     * declared, and the [fieldName] parameter specifies the simple name of the desired field.
     *
     * Also available as a convenience operator: [get]
     *
     * This may trigger IO reads.
     */
    fun readField(
      declaringClassName: String,
      fieldName: String
    ): HeapField? {
      return readFields().firstOrNull { field -> field.declaringClass.name == declaringClassName && field.name == fieldName }
    }
  }

/**
 * The fields of this instance, as a sequence of [HeapField].
 *
 * This may trigger IO reads.
 */
fun readFields(): Sequence<HeapField> {
  val fieldReader by lazy {
    hprofGraph.createFieldValuesReader(readRecord())
  }
  return instanceClass.classHierarchy
      .map { heapClass ->
        heapClass.readRecord()
            .fields.asSequence()
            .map { fieldRecord ->
              val fieldName = hprofGraph.fieldName(heapClass.objectId, fieldRecord)
              val fieldValue = fieldReader.readValue(fieldRecord)
              HeapField(heapClass, fieldName, HeapValue(hprofGraph, fieldValue))
            }
      }
      .flatten()//change two dimensional sequence into one dimensional
}

internal sealed class IndexedObject {
    abstract val position: Long

  class IndexedClass(
    override val position: Long,
    val superclassId: Long,
    val instanceSize: Int
  ) : IndexedObject()

  class IndexedInstance(
    override val position: Long,
    val classId: Long
  ) : IndexedObject()
  
    class IndexedObjectArray(
    override val position: Long,
    val arrayClassId: Long
  ) : IndexedObject()

  class IndexedPrimitiveArray(
    override val position: Long,
    primitiveType: PrimitiveType
  ) : IndexedObject() {
    private val primitiveTypeOrdinal: Byte = primitiveType.ordinal.toByte()
    val primitiveType: PrimitiveType
      get() = PrimitiveType.values()[primitiveTypeOrdinal.toInt()]
  }
}
  

/**
 * Wraps a byte array of entries where each entry is an id followed by bytes for the value.
 * `id` is a long if [longIdentifiers] is true and an int otherwise. Each entry has [bytesPerValue]
 * value bytes. Entries are appended into the array via [append]. Once done, the backing array
 * is sorted and turned into a [SortedBytesMap] by calling [moveToSortedMap].
 */
internal class UnsortedByteEntries(
  private val bytesPerValue: Int,
  private val longIdentifiers: Boolean,
  private val initialCapacity: Int = 4,
  private val growthFactor: Double = 2.0
) {
  private val bytesPerEntry = bytesPerValue + if (longIdentifiers) 8 else 4

  private var entries: ByteArray? = null
  private val subArray = MutableByteSubArray()
  private var subArrayIndex = 0

  private var assigned: Int = 0
  private var currentCapacity = 0

fun append(
  key: Long
): MutableByteSubArray {
  if (entries == null) {
    currentCapacity = initialCapacity
    entries = ByteArray(currentCapacity * bytesPerEntry)
  } else {
    if (currentCapacity == assigned) {
      val newCapacity = (currentCapacity * growthFactor).toInt()
      growEntries(newCapacity)
      currentCapacity = newCapacity
    }
  }
  assigned++
  subArrayIndex = 0
  subArray.writeId(key)
  return subArray
}

fun moveToSortedMap(): SortedBytesMap {
  if (assigned == 0) {
    return SortedBytesMap(longIdentifiers, bytesPerValue, ByteArray(0))
  }
  val entries = entries!!
  // Sort entries by keys, which are ids of 4 or 8 bytes.
  ByteArrayTimSort.sort(entries, 0, assigned, bytesPerEntry, object : ByteArrayComparator {
    override fun compare(
      entrySize: Int,
      o1Array: ByteArray,
      o1Index: Int,
      o2Array: ByteArray,
      o2Index: Int
    ): Int {
      return if (longIdentifiers) {
        readLong(o1Array, o1Index * entrySize)
            .compareTo(
                readLong(o2Array, o2Index * entrySize)
            )
      } else {
        readInt(o1Array, o1Index * entrySize)
            .compareTo(
                readInt(o2Array, o2Index * entrySize)
            )
      }
    }
  })
  val sortedEntries = if (entries.size > assigned * bytesPerEntry) {
    entries.copyOf(assigned * bytesPerEntry)
  } else entries
  this.entries = null
  assigned = 0
  return SortedBytesMap(
      longIdentifiers, bytesPerValue, sortedEntries
  )
}

/**
 * A read only map of `id` => `byte array` sorted by id, where `id` is a long if [longIdentifiers]
 * is true and an int otherwise. Each entry has a value byte array of size [bytesPerValue].
 *
 * Instances are created by [UnsortedByteEntries]
 *
 * [get] and [contains] perform a binary search to locate a specific entry by key.
 */
internal class SortedBytesMap(
  private val longIdentifiers: Boolean,
  private val bytesPerValue: Int,
  private val sortedEntries: ByteArray
) {
  private val bytesPerKey = if (longIdentifiers) 8 else 4
  private val bytesPerEntry = bytesPerKey + bytesPerValue

  private val size = sortedEntries.size / bytesPerEntry

operator fun get(key: Long): ByteSubArray? {
  val keyIndex = binarySearch(key)
  if (keyIndex < 0) {
    return null
  }
  val valueIndex = keyIndex * bytesPerEntry + bytesPerKey
  return ByteSubArray(sortedEntries, valueIndex, bytesPerValue, longIdentifiers)
}

private fun binarySearch(
  key: Long
): Int {
  val startIndex = 0
  val endIndex = size
  var lo = startIndex
  var hi = endIndex - 1
  while (lo <= hi) {
    val mid = (lo + hi).ushr(1)
    val midVal = keyAt(mid)
    when {
      midVal < key -> lo = mid + 1
      midVal > key -> hi = mid - 1
      else -> return mid
    }
  }
  return lo.inv()
}

/**
 * Being given a key looks it up in the map and returns the slot where element sits, so it later
 * can be retrieved with [getSlotValue]; return '-1' if element not found.
 * Why so complicated and not just make [get] return null if value not found? The reason is performance:
 * this approach prevents unnecessary boxing of the primitive long that would happen with nullable Long?
 */
fun getSlot(key: Long): Int {
  if (key == 0L) {
    return if (hasEmptyKey) mask + 1 else -1
  } else {
    val keys = this.keys
    val mask = this.mask
    var slot = hashKey(key) and mask

    var existing = keys[slot]
    while (existing != 0L) {
      if (existing == key) {
        return slot
      }
      slot = slot + 1 and mask
      existing = keys[slot]
    }

    return -1
  }
}

 * Being given a slot of element retrieves it from the collection
 */
fun getSlotValue(slot: Int): Long = values[slot]