Module: Laser::Analysis::ControlFlow::Simulation

221
222
223

# File 'lib/laser/analysis/control_flow/simulation.rb', line 221

def should_simulate_call(method, opts)
  method.predictable && (opts[:mutation] || !method.mutation)
end

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# File 'lib/laser/analysis/control_flow/simulation.rb', line 32

def simulate(formal_vals=[], opts={})
  opts = DEFAULT_SIMULATION_OPTS.merge(opts)
  opts[:formals] = formal_vals
  clear_analyses
  current_block = opts[:start_block] || @enter
  previous_block = nil
  begin
    loop do
      simulate_take_step(opts)
      from, next_block = simulate_block(current_block,
          opts.merge(previous_block: previous_block, current_block: current_block))
      from.add_flag(next_block, ControlFlowGraph::EDGE_EXECUTABLE)
      current_block, previous_block = next_block, current_block
    end
  rescue ExitedNormally => err
    current_block.add_flag(current_block.normal_successors.first,
        ControlFlowGraph::EDGE_EXECUTABLE)
    err.result
  rescue NonDeterminismHappened => err
    Laser.debug_puts "Simulation ended at nondeterminism: #{err.message}"
    Laser.debug_puts '>>> -- Starting Backup CP -- <<<'
    perform_constant_propagation(initial_block: current_block, no_wipe: true)
    Laser.debug_puts '>>> -- Finished Backup CP -- <<<'
    raise err
  rescue SimulationNonterminationError => err
    Laser.debug_puts "Simulation failed to terminate: #{err.message}"
    Laser.debug_p err.backtrace
    @root.add_error(TopLevelSimulationRaised.new(err.message, @root, err))
  rescue ExitedAbnormally => err
    current_block.add_flag(current_block.exception_successors.first,
        ControlFlowGraph::EDGE_EXECUTABLE)
    if opts[:on_raise] == :annotate
      msg = LaserObject === err.error ? err.error.laser_simulate('message', []) : err.error.message
      Laser.debug_puts "Simulation exited abnormally: #{msg}"
      @root.add_error(TopLevelSimulationRaised.new(msg, @root, err.error))
    elsif opts[:on_raise] == :raise
      raise err
    end
  rescue NotImplementedError => err
    Laser.debug_puts "Simulation attempted: #{err.message}"
    Laser.debug_p err.backtrace
  end
end

208
209
210
211
212
213
214
215
216
217
218
219

# File 'lib/laser/analysis/control_flow/simulation.rb', line 208

def simulate_args(insn)
  case insn.type
  when :call
    insn[4..-2].map(&:value)
  when :call_vararg
    insn[4].value
  when :super
    insn[2..-2].map(&:value)
  when :super_vararg
    insn[2].value
  end
end

146
147
148
149
150
151
152

# File 'lib/laser/analysis/control_flow/simulation.rb', line 146

def simulate_assignment(lhs, rhs, opts)
  if Bindings::Base === rhs
    lhs.bind! rhs.value
  else
    lhs.bind! rhs
  end
end

82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

# File 'lib/laser/analysis/control_flow/simulation.rb', line 82

def simulate_block(block, opts)
  return if block.name == 'Exit'
  
  Laser.debug_puts "Entering block #{block.name}"
  # phi nodes always go first
  block.phi_nodes.each do |node|
    simulate_deterministic_phi_node(node, opts)
  end
  block.natural_instructions[0..-2].each do |insn|
    simulate_instruction(insn, opts)
  end
  if block.instructions.empty?
    [opts[:current_block], block.real_successors.first]
  else
    simulate_exit_instruction(block.instructions.last, opts)
  end
end

196
197
198
199
200
201
202
203
204
205
206

# File 'lib/laser/analysis/control_flow/simulation.rb', line 196

def simulate_call(receiver, method, insn, opts)
  args = simulate_args(insn)
  block_to_use = insn[-1][:block] && insn[-1][:block].value
  result = simulate_call_dispatch(receiver, method, args, block_to_use, opts)
  if insn[1] 
    insn[1].bind! result
    if method == ClassRegistry['Array'].singleton_class.instance_method(:[])
      insn[1].inferred_type = Types::TupleType.new(result.map { |x| Utilities.type_for(x) })
    end
  end
end

225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

# File 'lib/laser/analysis/control_flow/simulation.rb', line 225

def simulate_call_dispatch(receiver, method, args, block, opts)
  Laser.debug_puts("simulate_call(#{receiver.inspect}, #{method.name}, #{args.inspect}, #{block.inspect}, #{opts.inspect})")
  opts = opts.merge(method: method)
  if block
    new_invocation_sites = opts[:invocation_sites].merge(block => opts[:invocation_sites][block] | Set[opts[:current_block]])
    opts = opts.merge(invocation_sites: new_invocation_sites, on_raise: :raise)
  end
  method.been_used!
  if method.special
    simulate_special_method(receiver, method, args, block, opts)
  elsif method.builtin
    begin
      if !block
        receiver.send(method.name, *args)
      else
        result = receiver.send(method.name, *args) do |*given_args, &given_blk|
          # self is this because no builtins change self... right?
          block.simulate(given_args, given_blk, opts)
        end
        result
      end
    rescue ExitedAbnormally => abnormal
      Bootstrap::EXCEPTION_STACK.value.push(abnormal.error)
      raise abnormal
    # Extremely unsafe exception handler: assumes my code does not raise
    # exceptions!
    rescue Exception => err
      Laser.debug_puts("Internal exception raised: #{err.message}")
      Laser.debug_pp(err.backtrace)
      Bootstrap::EXCEPTION_STACK.value.push(err)
      raise ExitedAbnormally.new(err)
    end
  else
    Laser.debug_puts "About to simulate #{method.owner.name}##{method.name}"
    result = method.simulate_with_args(receiver, args, block, opts)
    Laser.debug_puts "Finished simulating #{method.owner.name}##{method.name} => #{result.inspect}"
    result
  end
end

174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

# File 'lib/laser/analysis/control_flow/simulation.rb', line 174

def simulate_call_instruction(insn, opts)
  if insn.operands.any? { |op| op.value == VARYING || op.value == UNDEFINED }
    raise NonDeterminismHappened.new(
        "Nondeterministic operand (#{op.name}=#{op.value} in #{insn.inspect})")
  end
  receiver = insn[2].value
  klass = Utilities.klass_for(receiver)
  if insn.type == :call || insn.type == :call_vararg
    method = klass.instance_method(insn[3])  # normal method dispatch
  else
    # super method dispatch
    method = opts[:method].super_method
  end
  if !method
    simulate_method_missing(insn, klass)
  elsif should_simulate_call(method, opts)
    simulate_call(receiver, method, insn, opts)
  else
    raise NonDeterminismHappened.new("Nondeterministic call: #{method.owner.name}##{method.name}")
  end
end

341
342
343
344
345
346
347
348
349

# File 'lib/laser/analysis/control_flow/simulation.rb', line 341

def simulate_define_method(receiver, args, block)
  if args.size == 1 && block
    receiver.define_method(args.first, block)
  elsif args.size == 2
    receiver.define_method(args[0], args[1])
  else
    raise ArgumentError.new("wrong number of arguments (#{args.size} for 1..2)")
  end
end

140
141
142
143
144

# File 'lib/laser/analysis/control_flow/simulation.rb', line 140

def simulate_deterministic_phi_node(node, opts)
  # Laser.debug_puts "Simulating #{node.inspect} from #{opts[:previous_block].name}"
  index_of_predecessor = node.block.predecessors.to_a.index(opts[:previous_block])
  simulate_assignment(node[1], node[2 + index_of_predecessor], opts)
end

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

# File 'lib/laser/analysis/control_flow/simulation.rb', line 100

def simulate_exit_instruction(insn, opts)
  Laser.debug_puts "Simulating exit insn: #{insn.inspect}"
  natural_exit = insn.block.normal_successors.first
  case insn[0]
  when :jump
    [opts[:current_block], insn.block.real_successors.first]
  when :branch
    Laser.debug_puts "Branching on: #{insn[1].value.inspect}"
    [opts[:current_block], insn[1].value ? insn.true_successor : insn.false_successor]
  when :call, :call_vararg, :super, :super_vararg
    # todo: block edge!
    begin
      simulate_instruction(insn, opts)
      if (call_block = insn[-1][:block])
        block_proc = call_block.value
        if opts[:invocation_counts][block_proc][opts[:current_block]] > 0
          executed_succ = opts[:current_block].successors.find { |b| b.name == block_proc.start_block.name }
          opts[:current_block].add_flag(executed_succ,
              ControlFlowGraph::EDGE_EXECUTABLE)
          [self[block_proc.exit_block], natural_exit]
        else
          [opts[:current_block], natural_exit]
        end
      else
        [opts[:current_block], natural_exit]
      end
    rescue ExitedAbnormally => err
      Laser.debug_puts "Exception raised by call, taking abnormal edge. Error: #{err.error}"
      Laser.debug_pp(err.backtrace)
      [opts[:current_block], insn.block.exception_successors.first]
    end
  when :return
    raise ExitedNormally.new(insn[1].value)
  when :raise
    raise ExitedAbnormally.new(insn[1].value)
  else
    raise ArgumentError.new("Unexpected instruction type #{insn[0].inspect}")
  end 
end

154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

# File 'lib/laser/analysis/control_flow/simulation.rb', line 154

def simulate_instruction(insn, opts)
  Laser.debug_puts "Simulating insn: #{insn.inspect}"
  case insn[0]
  when :assign then simulate_assignment(insn[1], insn[2], opts)
  when :call, :call_vararg
    # cases: special method we intercept, builtin we direct-send, and cfg we simulate
    simulate_call_instruction(insn, opts)
  when :super, :super_vararg
    if opts[:method].nil?
      raise ExitedAbnormally.new(NoMethodError.new('super called outside of method'))
    else
      simulate_call_instruction(insn, opts)
    end
  when :declare
    # do nothing
  else
    raise ArgumentError.new("Unexpected instruction type #{insn[0].inspect}")
  end
end

265
266
267
268
269
270
271

# File 'lib/laser/analysis/control_flow/simulation.rb', line 265

def simulate_method_missing(insn, klass)
  error_klass = insn.node.type == :vcall ? 'NameError' : 'NoMethodError'
  missing_method_error = ClassRegistry[error_klass].laser_simulate(
      'new', ["Method missing: #{klass.name}##{insn[3]}", insn[3].to_s])
  Bootstrap::EXCEPTION_STACK.value.push(missing_method_error)
  raise ExitedAbnormally.new(missing_method_error)
end

372
373
374
375
376
377
378
379
380
381
382
383
384
385
386

# File 'lib/laser/analysis/control_flow/simulation.rb', line 372

def simulate_module_eval(receiver, args, block)
  # essentially: parse, compile with a custom scope + lexical target (cref), simulate.
  if args.size > 0
    text = args[0]
    file = args[1] || "(eval)"
    line = args[2] || 1  # ignored currently
    tree = Sexp.new(RipperPlus.sexp(text), file, text)
    Annotations.ordered_annotations.each do |annotator|
      annotator.annotate_with_text(tree, text)
    end
    custom_scope = ClosedScope.new(Scope::GlobalScope, receiver.binding)
    cfg = GraphBuilder.new(tree, [], custom_scope).build
    cfg.analyze
  end
end

353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370

# File 'lib/laser/analysis/control_flow/simulation.rb', line 353

def simulate_require(args)
  file = args.first
  load_path = Scope::GlobalScope.lookup('$:').value
  loaded_values = Scope::GlobalScope.lookup('$"').value
  to_load = file + '.rb'
  load_path.each do |path|
    joined = File.join(path, to_load)
    if File.exist?(joined)
      if !loaded_values.include?(joined)
        tree = Annotations.annotate_inputs([[joined, File.read(joined)]], optimize: false)
        #node.errors.concat tree[0][1].all_errors
        return true
      end
      return false
    end
  end
  raise LoadError.new("No such file: #{file}")
end

273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

# File 'lib/laser/analysis/control_flow/simulation.rb', line 273

def simulate_special_method(receiver, method, args, block, opts)
  case method
  when ClassRegistry['Class'].instance_method(:allocate)
    LaserObject.new(receiver, nil)
  when ClassRegistry['Class'].singleton_class.instance_method(:new)
    LaserClass.new(ClassRegistry['Class'], nil) do |klass|
      klass.superclass = args.first
    end
  when ClassRegistry['Module'].singleton_class.instance_method(:new)
    LaserModule.new
  when ClassRegistry['Kernel'].instance_method(:require)
    simulate_require(args)
  when ClassRegistry['Kernel'].instance_method(:send)
    method_name, *actual_args = args
    klass = Utilities.klass_for(receiver)
    method = klass.instance_method(method_name)
    if should_simulate_call(method, opts)
      simulate_call_dispatch(receiver, method, actual_args, block, opts)
    else
      raise NonDeterminismHappened.new("Nondeterministic call: #{method.inspect}")
    end
  when ClassRegistry['Module'].instance_method(:define_method)
    simulate_define_method(receiver, args, block)
  when ClassRegistry['Module'].instance_method(:module_eval)
    simulate_module_eval(receiver, args, block)
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:get_global)
    Scope::GlobalScope.lookup(args.first).value
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:set_global)
    Scope::GlobalScope.lookup(args[0]).bind!(args[1])
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_self)
    opts[:self]
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_block)
    opts[:block]
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_arity)
    opts[:formals].size
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_argument)
    opts[:formals][args.first]
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_argument_range)
    opts[:formals][args[0], args[1]]
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:current_exception),
       ClassRegistry['Laser#Magic'].singleton_class.instance_method(:get_just_raised_exception)
    Bootstrap::EXCEPTION_STACK.value.last
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:push_exception)
    Bootstrap::EXCEPTION_STACK.value.push args[0]
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:pop_exception)
    Bootstrap::EXCEPTION_STACK.value.pop
  when ClassRegistry['Laser#Magic'].singleton_class.instance_method(:responds?)
    receiver, method_name = args
    Utilities.klass_for(receiver).instance_method(method_name)
  when Scope::GlobalScope.self_ptr.singleton_class.instance_method(:private)
    ClassRegistry['Object'].private(*args)
  when Scope::GlobalScope.self_ptr.singleton_class.instance_method(:public)
    ClassRegistry['Object'].public(*args)
  end
end

76
77
78
79
80

# File 'lib/laser/analysis/control_flow/simulation.rb', line 76

def simulate_take_step(opts)
  if (opts[:remaining_blocks] -= 1) <= 0
    raise SimulationNonterminationError.new('Simulation failed to terminate')
  end
end