Upgrade to Pro — share decks privately, control downloads, hide ads and more …

A Type-level Ruby Interpreter for Testing and Understanding

A Type-level Ruby Interpreter for Testing and Understanding

Yusuke Endoh

April 18, 2019

More Decks by Yusuke Endoh

Other Decks in Programming


  1. PR: Cookpad Booth (3F) •Cookpad Daily Ruby Puzzles •Get a

    problem sheet • Complete "Hello world" by adding minimum letters and get a prize! def foo "Hello world" if false end puts foo def foo "Hello world" if !false end puts foo !
  2. The plan towards Ruby 3 static analysis Sorbet Steep RDL

    Library code type signature Type error warnings Application code type signature type signature Type Profiler Type error warnings This talk
  3. This talk is about "Type Profiler" •A type analyzer for

    Ruby 3 applicable to a non-annotated Ruby code • Level-1 type checking •Type signature prototyping •Note: The analysis is not "sound" • It may miss bugs and print wrong signature
  4. What Type Profiler is •Target: A normal Ruby code •No

    type signature/annotation required •Objectives: Testing and understanding • Testing: Warns possible errors of Ruby code •Understanding: Prototypes type signature
  5. Type Profiler for Testing •Finds NoMethodError, TypeError, etc. def foo(n)

    if n < 10 n.timees {|x| } end end foo(42) Type Profiler t.rb:3: [error] undefined method: Integer#timees Typo
  6. Type Profiler for Understanding •Generates a prototype of type definition

    def foo(n) n.to_s end foo(42) Type Profiler Object#foo :: (Integer) -> String
  7. How Type Profiler does •Runs a Ruby code in "type-level"

    Normal interpreter def foo(n) n.to_s end foo(42) Calls w/ 42 Returns "42" Type profiler def foo(n) n.to_s end foo(42) Calls w/ Integer Returns String Object#foo :: (Integer) -> String
  8. How does TP handle a branch? •"Forks" the execution def

    foo(n) if n < 10 n else "error" end end foo(42) Fork! Now here; We cannot tell taken true or false as we just know n is Integer Returns Integer Returns String Object#foo :: (Integer) -> (Integer | String)
  9. Is a method executed at every call? •No, the result

    is reused if possible def foo(n) n.to_s end x=foo(42) y=foo(43) z=foo(42.0) Calls w/ Integer Returns String We already know foo::(Integer)->String; Immediately returns String Calls w/ Float Returns String Object#foo :: (Integer)->String Object#foo :: (Float)->String
  10. Is Type Profiler a type checker? Normal type checker is

    intra-procedural def foo(n:int):str n.to_s end ret = foo(42) Assume Integer Check if String Check if Integer Assume String Type profiler is inter-procedural def foo(n) n.to_s end foo(42) Calls w/ Integer Returns String
  11. What this technique is? Easy to scale but restrictive Flexible

    but hard to scale Type checking Abstract interpretation Symbolic execution Type profiler...? Flow analysis Steep Sorbet RDL Excuse: This figure is just my personal opinion
  12. Demos •You can see the demo programs •https://github.com/mame/ruby-type-profiler •But the

    spec is still under consideration • The output format (and even behavior) may change in future
  13. Demo: Overloading def my_to_s(x) x.to_s end my_to_s(42) my_to_s("STR") my_to_s(:sym) Type

    Profiler Object#my_to_s :: (Integer) -> String Object#my_to_s :: (String) -> String Object#my_to_s :: (Symbol) -> String
  14. Demo: User-defined classes class Foo end class Bar def make_foo

    Foo.new end end Bar.new.make_foo Type Profiler Bar#make_foo :: () -> Foo
  15. Demo: Instance variables class Foo attr_accessor :ivar end Foo.new.ivar =

    42 Foo.new.ivar = "STR" Foo.new.ivar Type Profiler Foo#@ivar :: Integer | String Foo#ivar= :: (Integer) -> Integer Foo#ivar= :: (String) -> String Foo#ivar :: () -> (String | Integer)
  16. Demo: Block def foo(x) yield 42 end s = "str"

    foo(1) do |x| s end Type Profiler Object#foo :: (Integer, &Proc[(Integer) -> String]) -> String
  17. Demo: Tuple-like array def swap(a) [a[1], a[0]] end a =

    [42, "str"] swap(a) Type Profiler Object#swap :: ([Integer, String]) -> [String, Integer]
  18. Demo: Sequence-like array def foo [1] + ["str"] end foo

    Type Profiler Object#foo :: Array[Integer | String]
  19. Demo: Recursive method def fib(n) if n > 1 fib(n-1)

    + fib(n-2) else n end end fib(10000) Type Profiler Object#fib :: (Integer) -> Integer
  20. Demo: Unanalyzable method a = eval("1 + 1") a.foobar Type

    Profiler t.rb:1: cannot handle eval; the result is any A call is not warned when the receiver is any
  21. Looks good? •I think it would be good enough •To

    be fair, Type Profiler is never perfect •Can tell lies (false positive) • Requires tests (false negative) •Cannot handle some Ruby features • May be very slow (state explosion)
  22. Problem: False positives if n < 10 x = 42

    else x = "str" end if n < 10 x += 1 end String + Integer? Error! This path is not feasible because of the conditions Possible workaround: Please don't write such a untypeable code!
  23. Problem: A test is required Possible workaround: • Write a

    test! • TP may be improved in some cases def foo(x) x.timees end Type Profiler (nothing) Type Profiler cannot guess the argument type......
  24. Problem: Intractable features •Object#send •Singleton class • TP abstracts all

    values as a type (class) • But a singleton class is unique to the value •Workaround: Difficult... (TP plugin?) send(method_name) Type Profiler Type Profiler cannot identify the method being called!
  25. Problem: State explosion a=b=c=d=e=nil a = 42 if n <

    10 b = 42 if n < 10 c = 42 if n < 10 d = 42 if n < 10 e = 42 if n < 10 Fork! Fork! Fork! Fork! Fork! 2 4 8 16 32 The number of states Possible workaround: • Write an annotation...? → a::NilClass|Integer • Merge a pair of similar states (not implemented yet)
  26. Problems •Type Profiler is never perfect •But "better than nothing"

    • Only one choice for no-type Ruby lovers •You can use a type checker if you want a type • You may use Type Profiler to get a prototype of type signatures •I'm still thinking of the improvement • Stay tuned...
  27. Implementation overview •Core: A Type-level Ruby VM •Runs a YARV

    bytecode • A variable has a type instead of a value •A branch copies the state for each target •Profiling features • Reports all type errors during execution • Records all method arguments and return values (for type signature prototype)
  28. State enumeration •Enumerate all reachable states •From the first line

    of the entry program • Until fixed-point •The same states are merged • To avoid redundant execution • TODO: merge "similar" states if n < 10 a=1+1 else a=2+2 end ... The two states are the same
  29. Method return •TP state has no call stack •To avoid

    state explosion • Cannot identify return address •Returns to all calls •This handles recursive calls elegantly def foo ... return 42 end foo() foo() foo() foo() foo()
  30. Three method types 1. User-defined method • When called, TP

    enters its method body 2. Type-defined method • TP just checks argument types and returns its return type • For built-in methods or libraries 3. Custom special method • TP executes custom behavior • (TP plugin can exploit this?) def foo(n) ... end Integer#+ :: (Integer)->Integer Object#require???
  31. Excuse: TP is very preliminary... •Currently supports • Basic language

    features • Limited built-in classes (shown in Demos) •No-support-yet • Almost all built-in classes including Hash • Complex arguments (optional, rest, keywords) • Exceptions • Modules (Mix-in) • etc etc.
  32. Experiment 1: Self-profiling •Apply Type Profiler to itself •TP statistics:

    2167 LOC, 221 methods •Quantitative result: •Reached 91 methods in 10 minutes (!) •Qualitative result: Found an actual bug •TP said "a method receives NilClass" • It is not intended, and turned out a bug
  33. Why many methods not reached? •Because of not-implemented-yet features •For

    example, Array#<< is not implemented •Some methods are defined but unused •Idea: virtually call all methods with "any" arguments? a = [] a << Foo.new a[0].bar Foo#bar cannot be reached
  34. Type Profiler code coverage 42 A method State#run is not

    reached state is any for state.run state = states.pop caused nil because Array#pop was not implemented yet
  35. Experiment 2: optcarrot •Apply Type Profiler to optcarrot • 8bit

    hardware emulator written in Ruby • statistics: 4476 LOC, 394 methods •Result: • Reached 40 methods in 3 minutes? • Object#send and Fiber are not implemented yet • CPU uses Object#send for instruction dispatch • GPU uses Fiber for state machine
  36. Why did it took so long? •State explosion •A method

    returns Array or Integer •Calling it forks the state •Idea: Merge similar states more intelligently foo() foo() foo() foo() foo() Fork! Fork! Fork! Fork! Fork! foo :: () -> (Array[Integer] | Integer)
  37. Agenda •What "Type Profiler" is •Demos and Problems •Implementation •Very

    preliminary evaluation ➔(Related work and) Conclusion
  38. Related Work •mruby-meta-circular (Hideki Miura) • A very similar approach

    for mruby JIT • This inspired Type Profiler (Thanks!) •HPC Ruby (Koichi Nakamura) • Convert Ruby to C for HPC by abstract interp. •pytype (Google's unofficial project) • Python abstract interpreter for type analysis • More concrete than TP • Limits the stack depth to three
  39. Acknowledgement •Hideki Miura •Matz, Akr, Ko1 •PPL paper co-authors •

    Soutaro Matsumoto • Katsuhiro Ueno • Eijiro Sumii •Stripe team & Jeff Foster •And many people
  40. Conclusion •A yet another type analyzer for Ruby 3 applicable

    to a non-annotated Ruby code • Based on abstract interpretation technique • Little change for Ruby programming experience •Contribution is really welcome! •The development is very preliminary • https://github.com/mame/ruby-type-profiler
  41. (A lot of) Future work • Support language features •

    Almost all built-in classes including Hash • Complex arguments (optional, rest, keywords) • Exceptions • Modules (Mix-in) • etc etc. • Write a type definition for built-in classes/methods • Read type definition file • Improve performance • Make it useful • Code coverage • Flow-sensitive analysis • Heuristic type aggregation • Diagnosis feature • Incremental type profiling • etc etc.