Class: Necropsy::CallGraph

Inherits:
Object
  • Object
show all
Includes:
BlockerMatching, DynamicEvidenceTracking, EvidenceStore, ResolutionStore
Defined in:
lib/necropsy/graph/call_graph.rb

Constant Summary

Constants included from ResolutionStore

ResolutionStore::DIAGNOSTIC_SAMPLE_LIMIT, ResolutionStore::EMPTY_RESOLUTION_RECORDS, ResolutionStore::INVALID_SCOPE_LIMIT, ResolutionStore::RESOLUTION_STATUSES

Constants included from EvidenceStore

EvidenceStore::PROJECTIONS

Constants included from DynamicEvidenceTracking

DynamicEvidenceTracking::RESOLUTION_STATUSES, DynamicEvidenceTracking::SAMPLE_LIMIT

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from ResolutionStore

#call_sites_resolving_definition, #resolution_conflicts, #resolution_issues, #resolution_records, #resolution_status_counts

Methods included from BlockerMatching

#add_blocker, #blockers, #matching_blockers

Methods included from EvidenceStore

#evidence_collisions, #evidence_record, #evidence_records, normalize_projection

Methods included from DynamicEvidenceTracking

#dynamic_evidence_diagnostic, #dynamic_observation?

Constructor Details

#initialize(scan_result, ambiguity_limit: 4) ⇒ CallGraph

Returns a new instance of CallGraph.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/necropsy/graph/call_graph.rb', line 14

def initialize(scan_result, ambiguity_limit: 4)
  @nodes = DefinitionIndex.new
  @edges = {}
  @incoming_edges = {}
  initialize_evidence_store
  @call_sites = scan_result.call_sites
  @instantiated_classes = scan_result.instantiated_classes.dup
  @class_infos = scan_result.class_infos.to_h { |info| [info.id, info] }
  @direct_subclasses = Hash.new { |hash, key| hash[key] = [] }
  @class_infos.each_value do |info|
    @direct_subclasses[info.superclass] << info.id if info.superclass
  end
  @direct_subclasses.each_value(&:sort!)
  @entrypoint_hints = scan_result.entrypoint_hints
  @file_statuses = scan_result.file_statuses.to_h do |file, status|
    [file.to_s, status.to_sym]
  end
  @source_errors = scan_result.source_errors.dup
  @source_domains = scan_result.source_domains.to_h do |file, domain|
    [file.to_s, domain.to_sym]
  end
  @scope_diagnostics = scan_result.scope_diagnostics.dup
  @method_signatures = scan_result.method_signatures.dup
  @ambiguity_limit = ambiguity_limit
  @blockers = []
  initialize_blocker_indexes
  @entry_points = []
  @profiles = []
  @uncertainties = scan_result.uncertainties.to_h do |node_id, messages|
    [node_id, Array(messages).dup]
  end
  @dynamic_alive = {}
  @observation = {}
  record_generated_macro_observation(scan_result.nodes)
  initialize_resolution_store
  @descendants = {}
  @rta_instantiated_owner_cache = {}
  @duplicate_blockers_initialized = false
  scan_result.nodes.each { |node| add_node(node) }
  register_duplicate_definition_blockers
  @duplicate_blockers_initialized = true
  register_incomplete_source_blockers
  scan_result.semantic_blockers.each { |blocker| add_blocker(blocker) }
  retain_known_instantiated_classes
end

Instance Attribute Details

#ambiguity_limit ⇒ Object (readonly)

Returns the value of attribute ambiguity_limit.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def ambiguity_limit
  @ambiguity_limit
end

#call_sites ⇒ Object (readonly)

Returns the value of attribute call_sites.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def call_sites
  @call_sites
end

#class_infos ⇒ Object (readonly)

Returns the value of attribute class_infos.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def class_infos
  @class_infos
end

#entry_points ⇒ Object (readonly)

Returns the value of attribute entry_points.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def entry_points
  @entry_points
end

#entrypoint_hints ⇒ Object (readonly)

Returns the value of attribute entrypoint_hints.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def entrypoint_hints
  @entrypoint_hints
end

#file_statuses ⇒ Object (readonly)

Returns the value of attribute file_statuses.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def file_statuses
  @file_statuses
end

#instantiated_classes ⇒ Object (readonly)

Returns the value of attribute instantiated_classes.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def instantiated_classes
  @instantiated_classes
end

#method_signatures ⇒ Object (readonly)

Returns the value of attribute method_signatures.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def method_signatures
  @method_signatures
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def nodes
  @nodes
end

#observation ⇒ Object (readonly)

Returns the value of attribute observation.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def observation
  @observation
end

#profiles ⇒ Object (readonly)

Returns the value of attribute profiles.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def profiles
  @profiles
end

#scope_diagnostics ⇒ Object (readonly)

Returns the value of attribute scope_diagnostics.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def scope_diagnostics
  @scope_diagnostics
end

#source_domains ⇒ Object (readonly)

Returns the value of attribute source_domains.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def source_domains
  @source_domains
end

#source_errors ⇒ Object (readonly)

Returns the value of attribute source_errors.



10
11
12
 
# File 'lib/necropsy/graph/call_graph.rb', line 10

def source_errors
  @source_errors
end

Instance Method Details

#add_alive(node_id, evidence) ⇒ Object 



185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/necropsy/graph/call_graph.rb', line 185

def add_alive(node_id, evidence)
  definitions = resolve_definitions(node_id)
  if definitions.empty?
    register_evidence(evidence)
    return false
  end

  record_ambiguous_input(:alive, node_id, definitions)
  definitions.each do |definition|
    evidence_id = register_evidence(evidence, domain: definition.test ? :test : :runtime)
    next unless evidence_id

    @dynamic_alive[definition.graph_id] ||= Set.new
    @dynamic_alive[definition.graph_id] << evidence_id
  end
  true
end

#add_edge(caller_id, callee_id, evidence) ⇒ Object 



168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/necropsy/graph/call_graph.rb', line 168

def add_edge(caller_id, callee_id, evidence)
  callers = resolve_definitions(caller_id)
  callees = resolve_definitions(callee_id)
  if callers.empty? || callees.empty?
    domain = callers.any? && callers.all?(&:test) ? :test : :runtime
    register_evidence(evidence, domain: domain)
    return false
  end

  record_ambiguous_input(:edge_caller, caller_id, callers)
  record_ambiguous_input(:edge_callee, callee_id, callees)
  callers.product(callees).each do |caller, callee|
    add_physical_edge(caller.graph_id, callee.graph_id, evidence)
  end
  true
end

#add_entry_point(node_id, reason, domain: nil, evidence: nil) ⇒ Object 



102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/necropsy/graph/call_graph.rb', line 102

def add_entry_point(node_id, reason, domain: nil, evidence: nil)
  resolve_definitions(node_id).each do |definition|
    entry = Root.new(
      definition_id: definition.graph_id,
      domain: domain,
      reason: reason,
      evidence: evidence
    )
    entry_points << entry unless entry_points.include?(entry)
  end
end

#add_node(node) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/necropsy/graph/call_graph.rb', line 60

def add_node(node)
  existing = nodes.exact(node.graph_id)
  return existing if existing

  @method_nodes = nil
  @nodes_by_name = nil
  @runtime_nodes_by_name = nil
  @dispatch_cache = nil
  @lookup_chain_cache = nil
  @singleton_lookup_chain_cache = nil
  @owner_ancestor_cache = nil
  @flow_lookup_cache = nil
  @rta_instantiated_owner_cache = {}
  @dynamic_ancestry_cache = {}
  added = nodes.add(node)
  register_duplicate_definition_blocker(node.symbol_id) if @duplicate_blockers_initialized
  refresh_resolution_derived_state
  added
end

#add_profile(profile) ⇒ Object 



164
165
166
 
# File 'lib/necropsy/graph/call_graph.rb', line 164

def add_profile(profile)
  profiles << profile
end

#alive_evidences(node_id, projection: :conservative, scope: nil) ⇒ Object 



209
210
211
212
213
214
215
 
# File 'lib/necropsy/graph/call_graph.rb', line 209

def alive_evidences(node_id, projection: :conservative, scope: nil)
  projection = normalize_projection(projection)
  evidence_ids = resolve_definitions(node_id).flat_map do |definition|
    @dynamic_alive.fetch(definition.graph_id, Set.new).to_a
  end
  projected_evidence_records(evidence_ids.uniq, projection: projection, scope: scope)
end

#ambiguity_exceeded?(message, domain: nil) ⇒ Boolean

Returns:

  • (Boolean) 


374
375
376
 
# File 'lib/necropsy/graph/call_graph.rb', line 374

def ambiguity_exceeded?(message, domain: nil)
  candidate_nodes(message, domain: domain).size > ambiguity_limit
end

#ambiguous_fallback_candidates(message, domain: nil) ⇒ Object 



366
367
368
369
370
371
372
 
# File 'lib/necropsy/graph/call_graph.rb', line 366

def ambiguous_fallback_candidates(message, domain: nil)
  candidates = candidate_nodes(message, domain: domain)
  return candidates if candidates.one?
  return [] if candidates.size > @ambiguity_limit

  candidates
end

#ambiguous_resolution? ⇒ Boolean

Returns:

  • (Boolean) 


378
379
380
 
# File 'lib/necropsy/graph/call_graph.rb', line 378

def ambiguous_resolution?
  @ambiguity_limit > 1
end

#analyze_source?(file) ⇒ Boolean

Returns:

  • (Boolean) 


307
308
309
 
# File 'lib/necropsy/graph/call_graph.rb', line 307

def analyze_source?(file)
  source_domains.fetch(file.to_s, :analyze) == :analyze
end

#apply_result(result, refresh: true) ⇒ Object 



123
124
125
126
127
128
129
130
 
# File 'lib/necropsy/graph/call_graph.rb', line 123

def apply_result(result, refresh: true)
  staged = transactional_copy
  staged.send(:apply_result!, result, refresh: refresh)
  staged.instance_variables.each do |name|
    instance_variable_set(name, staged.instance_variable_get(name))
  end
  nil
end

#call_sites_for_message(message) ⇒ Object 



118
119
120
121
 
# File 'lib/necropsy/graph/call_graph.rb', line 118

def call_sites_for_message(message)
  @call_sites_by_message ||= call_sites.group_by { |site| site.message.to_s }.transform_values(&:freeze).freeze
  @call_sites_by_message.fetch(message.to_s, [])
end

#callable_method_lookup(_site) ⇒ Object 



565
566
567
 
# File 'lib/necropsy/graph/call_graph.rb', line 565

def callable_method_lookup(_site)
  incomplete_method_lookup([], [], 'callable_invocation')
end

#candidate_nodes(message, domain: nil) ⇒ Object 



361
362
363
364
 
# File 'lib/necropsy/graph/call_graph.rb', line 361

def candidate_nodes(message, domain: nil)
  index = domain&.to_sym == :runtime ? runtime_nodes_by_name : nodes_by_name
  index.fetch(message, [])
end

#cha_method_lookup(site) ⇒ Object 



398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
 
# File 'lib/necropsy/graph/call_graph.rb', line 398

def cha_method_lookup(site)
  primary = method_lookup(site)
  return primary if primary.complete?

  lookups = case site.receiver_kind
            when :constant
              receiver_candidates(site).map { |owner| canonical_receiver_lookup(site, owner, :constant) }
            when :instance
              receiver_candidates(site).flat_map do |owner|
                descendants_of(owner).map { |candidate| canonical_receiver_lookup(site, candidate, :instance) }
              end
            else
              []
            end
  targets = [primary, *lookups].flat_map(&:targets).uniq(&:graph_id).sort_by(&:graph_id)
  chain = [primary, *lookups].flat_map(&:lookup_chain).uniq
  incomplete_method_lookup(targets, chain, 'cha_canonical_lookup')
end

#class_info(owner) ⇒ Object 



332
333
334
 
# File 'lib/necropsy/graph/call_graph.rb', line 332

def class_info(owner)
  class_infos[owner]
end

#constructor_dispatch_exact?(owner, site) ⇒ Boolean

Returns:

  • (Boolean) 


538
539
540
541
542
543
544
545
546
547
548
 
# File 'lib/necropsy/graph/call_graph.rb', line 538

def constructor_dispatch_exact?(owner, site)
  info = class_info(owner)
  return false unless info && !info.dynamic
  return false if dynamic_ancestry_uncertain?(site)

  entries = singleton_lookup_entries(owner)
  return false if dynamic_lookup_chain?(entries)
  return false if entries.any? { |candidate, separator| definitions_for("#{candidate}#{separator}new").any? }

  !constructor_mutation_blocker?(owner, entries, site)
end

#constructor_mutation_blocker?(owner, entries, site) ⇒ Boolean

Returns:

  • (Boolean) 


550
551
552
553
554
555
556
557
558
 
# File 'lib/necropsy/graph/call_graph.rb', line 550

def constructor_mutation_blocker?(owner, entries, site)
  owners = [owner, *entries.map(&:first)].to_set
  @blockers.any? do |blocker|
    next false unless %i[dynamic_ancestry unsupported_refinement variable_eval].include?(blocker.kind)
    next false unless blocker.caller_domain == :runtime || site.test

    blocker.scope_kind == :global || (blocker.scope_kind == :owner && owners.include?(blocker.scope_value))
  end
end

#definitions_for(symbol_id) ⇒ Object 



114
115
116
 
# File 'lib/necropsy/graph/call_graph.rb', line 114

def definitions_for(symbol_id)
  nodes.definitions_for(symbol_id)
end

#descendants_of(owner) ⇒ Object 



336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
 
# File 'lib/necropsy/graph/call_graph.rb', line 336

def descendants_of(owner)
  @descendants[owner] ||= begin
    descendants = []
    queue = class_infos.key?(owner) ? [owner] : []
    seen = Set.new
    head = 0
    while head < queue.length
      candidate = queue.fetch(head)
      head += 1
      next unless seen.add?(candidate)

      descendants << candidate
      queue.concat(@direct_subclasses.fetch(candidate, []))
    end
    descendants.freeze
  end
end

#dynamic_alive?(node_id) ⇒ Boolean

Returns:

  • (Boolean) 


203
204
205
206
207
 
# File 'lib/necropsy/graph/call_graph.rb', line 203

def dynamic_alive?(node_id)
  resolve_definitions(node_id).any? do |definition|
    @dynamic_alive.fetch(definition.graph_id, Set.new).any? { |evidence_id| evidence_record(evidence_id) }
  end
end

#dynamic_enabled? ⇒ Boolean

Returns:

  • (Boolean) 


217
218
219
 
# File 'lib/necropsy/graph/call_graph.rb', line 217

def dynamic_enabled?
  @dynamic_alive.any?
end

#edge_present?(caller_id, callee_id) ⇒ Boolean

Returns:

  • (Boolean) 


253
254
255
 
# File 'lib/necropsy/graph/call_graph.rb', line 253

def edge_present?(caller_id, callee_id)
  @edges.dig(caller_id, callee_id)&.any? { |evidence_id| evidence_record(evidence_id) }
end

#edge_relations(projection: :conservative, scope: nil) ⇒ Object 



267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
 
# File 'lib/necropsy/graph/call_graph.rb', line 267

def edge_relations(projection: :conservative, scope: nil)
  projection = normalize_projection(projection)
  @edges.flat_map do |caller_id, callees|
    callees.filter_map do |callee_id, evidence_ids|
      projected_ids = projected_evidence_ids(evidence_ids, projection: projection, scope: scope)
      next if projected_ids.empty?

      EdgeRelation.new(
        caller_id: caller_id,
        callee_id: callee_id,
        evidence_ids: projected_ids,
        projection: projection
      )
    end
  end.sort_by { |edge| [edge.caller_id, edge.callee_id] }
end

#edges(projection: :conservative, scope: nil) ⇒ Object 



257
258
259
260
261
262
263
264
265
 
# File 'lib/necropsy/graph/call_graph.rb', line 257

def edges(projection: :conservative, scope: nil)
  projection = normalize_projection(projection)
  @edges.flat_map do |caller_id, callees|
    callees.filter_map do |callee_id, evidence_ids|
      evidences = projected_evidence_records(evidence_ids, projection: projection, scope: scope)
      Edge.new(caller_id: caller_id, callee_id: callee_id, evidences: evidences) unless evidences.empty?
    end
  end.sort_by { |edge| [edge.caller_id, edge.callee_id] }
end

#edges_from(node_id, projection: :conservative, scope: nil) ⇒ Object 



240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/necropsy/graph/call_graph.rb', line 240

def edges_from(node_id, projection: :conservative, scope: nil)
  projection = normalize_projection(projection)
  evidence_ids_by_callee = resolve_definitions(node_id).each_with_object(Hash.new { |hash, key| hash[key] = Set.new }) do |definition, merged|
    @edges.fetch(definition.graph_id, {}).each do |callee_id, evidence_ids|
      merged[callee_id].merge(evidence_ids)
    end
  end
  evidence_ids_by_callee.each_with_object({}) do |(callee_id, evidence_ids), projected|
    records = projected_evidence_records(evidence_ids, projection: projection, scope: scope)
    projected[callee_id] = records unless records.empty?
  end
end

#fallback_resolution?(site, resolved: nil) ⇒ Boolean

Returns:

  • (Boolean) 


602
603
604
605
606
607
608
609
610
 
# File 'lib/necropsy/graph/call_graph.rb', line 602

def fallback_resolution?(site, resolved: nil)
  resolved ||= resolve_call_site(site)
  return false if resolved.empty?

  lookup = method_lookup(site)
  domain = site.test ? :test : :runtime
  fallback = ambiguous_fallback_candidates(site.message, domain: domain)
  !lookup.complete? && resolved.map(&:graph_id).sort == fallback.map(&:graph_id).sort
end

#flow_callable?(site) ⇒ Boolean

Returns:

  • (Boolean) 


560
561
562
563
 
# File 'lib/necropsy/graph/call_graph.rb', line 560

def flow_callable?(site)
  fact = site.metadata['receiver_value_fact'] || site.metadata[:receiver_value_fact]
  fact.is_a?(Hash) && hash_value(fact, 'kind').to_s == 'callable_set' && hash_value(fact, 'exact') == true
end

#flow_instance_method_lookup(site) ⇒ Object 



460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
 
# File 'lib/necropsy/graph/call_graph.rb', line 460

def flow_instance_method_lookup(site)
  @flow_lookup_cache ||= {}
  cache_key = [site.call_site_id, flow_instance_types(site)]
  return @flow_lookup_cache[cache_key] if @flow_lookup_cache.key?(cache_key)

  results = flow_instance_types(site).map do |owner|
    ordered_method_lookup(
      site,
      instance_lookup_entries(owner),
      reason: 'flow_instance_lookup',
      completeness_entries: [[owner, '#']]
    )
  end
  result = results.first if results.one?
  return @flow_lookup_cache[cache_key] = result if result

  @flow_lookup_cache[cache_key] = merge_flow_method_lookups(results)
end

#flow_instance_types(site) ⇒ Object 



513
514
515
516
517
518
519
520
521
522
523
524
 
# File 'lib/necropsy/graph/call_graph.rb', line 513

def flow_instance_types(site)
  fact = site.metadata['receiver_value_fact'] || site.metadata[:receiver_value_fact]
  return nil unless fact.is_a?(Hash)
  return nil unless hash_value(fact, 'kind').to_s == 'instance_types'
  return nil unless hash_value(fact, 'exact')

  values = Array(hash_value(fact, 'values')).map(&:to_s).reject(&:empty?).uniq.sort
  return nil if values.empty?
  return nil unless values.all? { |owner| constructor_dispatch_exact?(owner, site) }

  values
end

#incoming_edges(node_id, projection: :conservative, scope: nil) ⇒ Object 



284
285
286
287
288
289
290
291
292
 
# File 'lib/necropsy/graph/call_graph.rb', line 284

def incoming_edges(node_id, projection: :conservative, scope: nil)
  projection = normalize_projection(projection)
  resolve_definitions(node_id).flat_map do |definition|
    @incoming_edges.fetch(definition.graph_id, {}).filter_map do |caller_id, evidence_ids|
      evidences = projected_evidence_records(evidence_ids, projection: projection, scope: scope)
      Edge.new(caller_id: caller_id, callee_id: definition.graph_id, evidences: evidences) unless evidences.empty?
    end
  end.sort_by { |edge| [edge.caller_id, edge.callee_id] }
end

#incomplete_files ⇒ Object 



303
304
305
 
# File 'lib/necropsy/graph/call_graph.rb', line 303

def incomplete_files
  file_statuses.filter_map { |file, status| file unless status == :complete }.sort
end

#merge_flow_method_lookups(results) ⇒ Object 



495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
 
# File 'lib/necropsy/graph/call_graph.rb', line 495

def merge_flow_method_lookups(results)
  targets = results.flat_map(&:targets).uniq(&:graph_id).sort_by(&:graph_id)
  chain = results.flat_map(&:lookup_chain).uniq
  return incomplete_method_lookup(targets, chain, 'flow_instance_lookup_incomplete') unless results.all?(&:complete?)

  accepted_ids = targets.to_set(&:graph_id)
  rejections = results.flat_map(&:rejected_targets).reject do |rejection|
    accepted_ids.include?(rejection.definition_id)
  end.uniq { |rejection| [rejection.definition_id, rejection.reason] }
  MethodLookup.new(
    targets: targets,
    status: :complete,
    rejected_targets: rejections,
    lookup_chain: chain,
    reason: 'flow_instance_lookup'
  )
end

#method_lookup(site) ⇒ Object 



427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
 
# File 'lib/necropsy/graph/call_graph.rb', line 427

def method_lookup(site)
  return fallback_method_lookup(site, reason: 'dynamic_message') if site.dynamic
  return physical_target_lookup(site) if physical_target_id(site)
  return unproven_initialize_lookup(site) if unproven_initialize_dispatch?(site)
  return callable_method_lookup(site) if flow_callable?(site)
  return flow_instance_method_lookup(site) if flow_instance_types(site)

  case site.receiver_kind
  when :constant
    owner = resolved_receiver_owner(site)
    ordered_method_lookup(
      site,
      singleton_lookup_entries(owner),
      reason: 'singleton_lookup',
      completeness_entries: [[owner, '.']]
    )
  when :instance
    owner = resolved_receiver_owner(site)
    ordered_method_lookup(
      site,
      instance_lookup_entries(owner),
      reason: 'instance_lookup',
      completeness_entries: [[owner, '#']]
    )
  when :self, :implicit
    self_method_lookup(site)
  when :super
    super_method_lookup(site)
  else
    fallback_method_lookup(site, reason: 'unknown_receiver')
  end
end

#method_nodes ⇒ Object 



324
325
326
 
# File 'lib/necropsy/graph/call_graph.rb', line 324

def method_nodes
  @method_nodes ||= nodes.values.select(&:method?)
end

#modules_for(owner) ⇒ Object 



354
355
356
357
358
359
 
# File 'lib/necropsy/graph/call_graph.rb', line 354

def modules_for(owner)
  info = class_info(owner)
  return [] unless info

  (info.prepends + info.includes + info.extends).uniq
end

#nodes_by_name ⇒ Object 



328
329
330
 
# File 'lib/necropsy/graph/call_graph.rb', line 328

def nodes_by_name
  @nodes_by_name ||= method_nodes.group_by(&:name).freeze
end

#owner_reachable_from_ancestor?(owner, ancestor) ⇒ Boolean

Returns:

  • (Boolean) 


382
383
384
385
386
387
388
389
390
 
# File 'lib/necropsy/graph/call_graph.rb', line 382

def owner_reachable_from_ancestor?(owner, ancestor)
  @owner_ancestor_cache ||= {}
  key = [owner, ancestor]
  return @owner_ancestor_cache[key] if @owner_ancestor_cache.key?(key)

  @owner_ancestor_cache[key] = descendants_of(ancestor).any? do |descendant|
    cached_lookup_chain(descendant).include?(owner)
  end
end

#performance_counts ⇒ Object 



229
230
231
232
233
234
235
236
237
238
 
# File 'lib/necropsy/graph/call_graph.rb', line 229

def performance_counts
  {
    'definitions' => nodes.length,
    'call_sites' => call_sites.length,
    'edges' => edges.length,
    'blockers' => blockers.length,
    'resolution_cache_hits' => @resolution_cache_hits.to_i,
    'resolution_cache_misses' => @resolution_cache_misses.to_i
  }
end

#physical_target_id(site) ⇒ Object 



479
480
481
 
# File 'lib/necropsy/graph/call_graph.rb', line 479

def physical_target_id(site)
  hash_value(site.metadata, 'physical_target_definition_id')
end

#physical_target_lookup(site) ⇒ Object 



483
484
485
486
487
488
489
490
491
492
493
 
# File 'lib/necropsy/graph/call_graph.rb', line 483

def physical_target_lookup(site)
  target = nodes.exact(physical_target_id(site).to_s)
  return incomplete_method_lookup([], [], 'physical_target_missing') unless target

  MethodLookup.new(
    targets: [target],
    status: :complete,
    lookup_chain: [target.owner],
    reason: 'physical_definition_relation'
  )
end

#reconcile_rta_result(result) ⇒ Object 



573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
 
# File 'lib/necropsy/graph/call_graph.rb', line 573

def reconcile_rta_result(result)
  analyzed_sites = result.observation.dig('rta', 'analyzed_sites')
  return unless analyzed_sites

  analyzed_keys = analyzed_sites.to_set { |site| call_site_key(site) }
  allowed = result.edge_evidences.each_with_object(Hash.new { |hash, key| hash[key] = Set.new }) do |edge, memo|
    memo[call_site_key(edge.evidence.metadata)] << edge.callee_id
  end

  @edges.each_value do |callees|
    callees.each do |callee_id, evidence_ids|
      evidence_ids.delete_if do |evidence_id|
        item = evidence_record(evidence_id)
        next false unless item

        producer = item.producer || item.analyzer
        next false unless %w[name_resolution cha].include?(producer.to_s)

        key = call_site_key(item.metadata)
        analyzed_keys.include?(key) && !allowed[key].include?(callee_id)
      end
    end
    callees.delete_if { |_callee_id, evidence_ids| evidence_ids.empty? }
  end
  @edges.delete_if { |_caller_id, callees| callees.empty? }
  rebuild_incoming_edges
  refresh_resolution_derived_state
end

#refresh_derived_state ⇒ Object 



160
161
162
 
# File 'lib/necropsy/graph/call_graph.rb', line 160

def refresh_derived_state
  refresh_resolution_derived_state
end

#residual_scope_for(site) ⇒ Object 



417
418
419
420
421
422
423
424
425
 
# File 'lib/necropsy/graph/call_graph.rb', line 417

def residual_scope_for(site)
  return UnknownScope.new(scope_kind: :message, scope_value: site.message, match: :exact) if site.receiver_kind == :unknown

  owners = receiver_candidates(site)
  owners = [nodes.exact(site.caller_id)&.owner].compact if owners.empty?
  return UnknownScope.new(scope_kind: :message, scope_value: site.message, match: :exact) if owners.empty?

  UnknownScope.new(scope_kind: :owner, scope_value: owners.sort, match: :exact)
end

#resolve_call_site(site, rta: false) ⇒ Object 



392
393
394
395
396
 
# File 'lib/necropsy/graph/call_graph.rb', line 392

def resolve_call_site(site, rta: false)
  candidates = rta ? rta_candidates_for_receiver(site) : method_lookup(site).targets
  candidates = candidates.select { |node| rta_candidate?(node, site) } if rta
  candidates
end

#retain_rta_candidates(candidates, site) ⇒ Object 



569
570
571
 
# File 'lib/necropsy/graph/call_graph.rb', line 569

def retain_rta_candidates(candidates, site)
  candidates.select { |node| rta_candidate?(node, site) }
end

#runtime_feedback(observed_targets:, max_fixtures: RuntimeFeedback::DEFAULT_FIXTURE_LIMIT) ⇒ Object 



221
222
223
224
225
226
227
 
# File 'lib/necropsy/graph/call_graph.rb', line 221

def runtime_feedback(observed_targets:, max_fixtures: RuntimeFeedback::DEFAULT_FIXTURE_LIMIT)
  RuntimeFeedback.from_graph(
    self,
    observed_targets: observed_targets,
    max_fixtures: max_fixtures
  ).call
end

#source_incompleteness ⇒ Object 



311
312
313
314
315
316
317
318
319
320
321
322
 
# File 'lib/necropsy/graph/call_graph.rb', line 311

def source_incompleteness
  {
    'incomplete_files' => incomplete_files.length,
    'files' => incomplete_files.map do |file|
      {
        'file' => file,
        'status' => file_statuses.fetch(file).to_s,
        'errors' => source_errors.select { |error| error.file == file }.map(&:to_h)
      }
    end
  }
end

#to_h ⇒ Object 



612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
 
# File 'lib/necropsy/graph/call_graph.rb', line 612

def to_h
  {
    'nodes' => nodes.values.map(&:to_h),
    'call_sites' => call_sites.map(&:to_h),
    'edges' => edges.map(&:to_h),
    'edge_projection' => 'conservative',
    'edge_relations' => edge_relations.map(&:to_h),
    'evidence_records' => evidence_records.map(&:to_h),
    'evidence_collisions' => evidence_collisions,
    'entry_points' => entry_points.map(&:to_h),
    'class_infos' => class_infos.values.map(&:to_h),
    'instantiated_classes' => instantiated_classes.to_a.sort,
    'profiles' => profiles.map(&:to_h),
    'resolutions' => resolution_records.map(&:to_h),
    'resolution_conflicts' => resolution_conflicts,
    'blockers' => blockers.map(&:to_h),
    'file_statuses' => file_statuses.transform_values(&:to_s),
    'source_errors' => source_errors.map(&:to_h),
    'source_domains' => source_domains.transform_values(&:to_s),
    'scope_diagnostics' => scope_diagnostics,
    'observation' => observation
  }
end

#uncertainties(node_id = nil) ⇒ Object 



294
295
296
297
298
299
300
301
 
# File 'lib/necropsy/graph/call_graph.rb', line 294

def uncertainties(node_id = nil)
  return @uncertainties unless node_id

  resolved = resolve_definitions(node_id)
  return @uncertainties.fetch(node_id, []) if resolved.empty?

  resolved.flat_map { |definition| @uncertainties.fetch(definition.graph_id, []) }.uniq
end

#unproven_initialize_dispatch?(site) ⇒ Boolean

Returns:

  • (Boolean) 


526
527
528
529
530
531
 
# File 'lib/necropsy/graph/call_graph.rb', line 526

def unproven_initialize_dispatch?(site)
  metadata = site.metadata
  return false unless hash_value(metadata, 'implicit_from').to_s == 'new'

  !constructor_dispatch_exact?(resolved_receiver_owner(site), site)
end

#unproven_initialize_lookup(site) ⇒ Object 



533
534
535
536
 
# File 'lib/necropsy/graph/call_graph.rb', line 533

def unproven_initialize_lookup(site)
  owner = resolved_receiver_owner(site)
  incomplete_method_lookup([], instance_lookup_entries(owner), 'constructor_dispatch_unproven')
end