pointers.go 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167
  1. package litter
  2. import (
  3. "fmt"
  4. "reflect"
  5. "sort"
  6. )
  7. // mapReusedPointers takes a structure, and recursively maps all pointers mentioned in the tree,
  8. // detecting circular references, and providing a list of all pointers that was referenced at
  9. // least twice by the provided structure.
  10. func mapReusedPointers(v reflect.Value) ptrmap {
  11. pm := &pointerVisitor{}
  12. pm.consider(v)
  13. return pm.reused
  14. }
  15. // A map of pointers.
  16. type ptrinfo struct {
  17. id int
  18. parent *ptrmap
  19. }
  20. func (p *ptrinfo) label() string {
  21. if p.id == -1 {
  22. p.id = p.parent.count
  23. p.parent.count++
  24. }
  25. return fmt.Sprintf("p%d", p.id)
  26. }
  27. type ptrkey struct {
  28. p uintptr
  29. t reflect.Type
  30. }
  31. func ptrkeyFor(v reflect.Value) (k ptrkey) {
  32. k.p = v.Pointer()
  33. for v.Kind() == reflect.Ptr {
  34. v = v.Elem()
  35. }
  36. if v.IsValid() {
  37. k.t = v.Type()
  38. }
  39. return
  40. }
  41. type ptrmap struct {
  42. m map[ptrkey]*ptrinfo
  43. count int
  44. }
  45. // Returns true if contains a pointer.
  46. func (pm *ptrmap) contains(v reflect.Value) bool {
  47. if pm.m != nil {
  48. _, ok := pm.m[ptrkeyFor(v)]
  49. return ok
  50. }
  51. return false
  52. }
  53. // Gets a pointer.
  54. func (pm *ptrmap) get(v reflect.Value) (*ptrinfo, bool) {
  55. if pm.m != nil {
  56. p, ok := pm.m[ptrkeyFor(v)]
  57. return p, ok
  58. }
  59. return nil, false
  60. }
  61. // Removes a pointer.
  62. func (pm *ptrmap) remove(v reflect.Value) {
  63. if pm.m != nil {
  64. delete(pm.m, ptrkeyFor(v))
  65. }
  66. }
  67. // Adds a pointer.
  68. func (pm *ptrmap) add(p reflect.Value) bool {
  69. if pm.contains(p) {
  70. return false
  71. }
  72. pm.put(p)
  73. return true
  74. }
  75. // Adds a pointer (slow path).
  76. func (pm *ptrmap) put(v reflect.Value) {
  77. if pm.m == nil {
  78. pm.m = make(map[ptrkey]*ptrinfo, 31)
  79. }
  80. key := ptrkeyFor(v)
  81. if _, ok := pm.m[key]; !ok {
  82. pm.m[key] = &ptrinfo{id: -1, parent: pm}
  83. }
  84. }
  85. type pointerVisitor struct {
  86. pointers ptrmap
  87. reused ptrmap
  88. }
  89. // Recursively consider v and each of its children, updating the map according to the
  90. // semantics of MapReusedPointers
  91. func (pv *pointerVisitor) consider(v reflect.Value) {
  92. if v.Kind() == reflect.Invalid {
  93. return
  94. }
  95. if isPointerValue(v) { // pointer is 0 for unexported fields
  96. if pv.tryAddPointer(v) {
  97. // No use descending inside this value, since it have been seen before and all its descendants
  98. // have been considered
  99. return
  100. }
  101. }
  102. // Now descend into any children of this value
  103. switch v.Kind() {
  104. case reflect.Slice, reflect.Array:
  105. for i := 0; i < v.Len(); i++ {
  106. pv.consider(v.Index(i))
  107. }
  108. case reflect.Interface:
  109. pv.consider(v.Elem())
  110. case reflect.Ptr:
  111. pv.consider(v.Elem())
  112. case reflect.Map:
  113. keys := v.MapKeys()
  114. sort.Sort(mapKeySorter{
  115. keys: keys,
  116. options: &Config,
  117. })
  118. for _, key := range keys {
  119. pv.consider(key)
  120. pv.consider(v.MapIndex(key))
  121. }
  122. case reflect.Struct:
  123. numFields := v.NumField()
  124. for i := 0; i < numFields; i++ {
  125. pv.consider(v.Field(i))
  126. }
  127. }
  128. }
  129. // addPointer to the pointerMap, update reusedPointers. Returns true if pointer was reused
  130. func (pv *pointerVisitor) tryAddPointer(v reflect.Value) bool {
  131. // Is this allready known to be reused?
  132. if pv.reused.contains(v) {
  133. return true
  134. }
  135. // Have we seen it once before?
  136. if pv.pointers.contains(v) {
  137. // Add it to the register of pointers we have seen more than once
  138. pv.reused.add(v)
  139. return true
  140. }
  141. // This pointer was new to us
  142. pv.pointers.add(v)
  143. return false
  144. }