Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
1102 lines (814 sloc) 14.8 KB

Zombie Killer Specification

This document describes how Zombie Killer kills various YCP zombies. It serves both as a human-readable documentation and as an executable specification. Technically, this is implemented by translating this document from Markdown into RSpec.

Table Of Contents

  1. Concepts
  2. Literals
  3. Variables
  4. Assigments
    1. And-assignment
    2. Or-assignment
  5. Calls Preserving Niceness
    1. Calls Generating Niceness
  6. Translation Below Top Level
  7. Chained Translation
  8. If
  9. Case
  10. Loops
    1. While and Until
    2. For
  11. Exceptions
  12. Blocks
  13. Formatting

Concepts

A zombie is a Ruby method call emulating a quirk of the YCP language that YaST was formerly implemented in. Ops.add will serve as an example of a simple zombie. The library implementation simply returns nil if any argument is nil. Compare this to + which raises an exception if it gets nil. Therefore Ops.add can be translated to the + operator, as long as its arguments are not nil.

A nice value is one that cannot be nil and is therefore suitable as an argument to a native operator.

An ugly value is one that may be nil.

Literals

String and integer literals are obviously nice. nil is a literal too but it is ugly.

Zombie Killer translates Ops.add of two string literals.

Original

Ops.add("Hello", "World")

Translated

"Hello" + "World"

Zombie Killer translates Ops.add of two integer literals.

Original

Ops.add(40, 2)

Translated

40 + 2

Zombie Killer translates assignment of Ops.add of two string literals. (Move this to "translate deeper than at top level")

Original

v = Ops.add("Hello", "World")

Translated

v = "Hello" + "World"

Zombie Killer does not translate Ops.add if any argument is ugly.

Unchanged

Ops.add("Hello", world)

Zombie Killer does not translate Ops.add if any argument is the nil literal.

Unchanged

Ops.add("Hello", nil)

Variables

If a local variable is assigned a nice value, we remember that.

Zombie Killer translates Ops.add(nice_variable, literal).

Original

v = "Hello"
Ops.add(v, "World")

Translated

v = "Hello"
v + "World"

Zombie Killer doesn't translate Ops.add(nice_variable, literal) when the variable got it's niceness via multiple assignemnt. We chose to ignore multiple assigments for now because of their complicated semantics (especially in presence of splats).

Unchanged

v1, v2 = "Hello", "World"
Ops.add(v1, v2)

Zombie Killer translates Ops.add(nontrivially_nice_variable, literal).

Original

v  = "Hello"
v2 = v
v  = uglify
Ops.add(v2, "World")

Translated

v  = "Hello"
v2 = v
v  = uglify
v2 + "World"

We have to take care to revoke a variable's niceness if appropriate.

Zombie Killer does not translate Ops.add(mutated_variable, literal).

Unchanged

v = "Hello"
v = f(v)
Ops.add(v, "World")

Zombie Killer does not confuse variables across defs.

Unchanged

def a
  v = "literal"
end

def b(v)
  Ops.add(v, "literal")
end

Zombie Killer does not confuse variables across def self.s.

Unchanged

v = 1

def self.foo(v)
  Ops.add(v, 1)
end

Zombie Killer does not confuse variables across modules.

Unchanged

module A
  v = "literal"
end

module B
  # The assignment is needed to convince Ruby parser that the "v" reference in
  # the "Ops.add" call later refers to a variable, not a method. This means it
  # will be parsed as a "lvar" node (which can possibly be nice), not a "send"
  # node (which can't be nice).

  v = v
  Ops.add(v, "literal")
end

Zombie Killer does not confuse variables across classs.

Unchanged

class A
  v = "literal"
end

class B
  # The assignment is needed to convince Ruby parser that the "v" reference in
  # the "Ops.add" call later refers to a variable, not a method. This means it
  # will be parsed as a "lvar" node (which can possibly be nice), not a "send"
  # node (which can't be nice).

  v = v
  Ops.add(v, "literal")
end

Zombie Killer does not confuse variables across singleton classs.

Unchanged

class << self
  v = "literal"
end

class << self
  # The assignment is needed to convince Ruby parser that the "v" reference in
  # the "Ops.add" call later refers to a variable, not a method. This means it
  # will be parsed as a "lvar" node (which can possibly be nice), not a "send"
  # node (which can't be nice).

  v = v
  Ops.add(v, "literal")
end

Assignments

And-assignment

Zombie Killer manages niceness correctly in presence of &&=.

Original

nice1 = true
nice2 = true
ugly1 = nil
ugly2 = nil

nice1 &&= true
nice2 &&= nil
ugly1 &&= true
ugly2 &&= nil

Ops.add(nice1, 1)
Ops.add(nice2, 1)
Ops.add(ugly1, 1)
Ops.add(ugly2, 1)

Translated

nice1 = true
nice2 = true
ugly1 = nil
ugly2 = nil

nice1 &&= true
nice2 &&= nil
ugly1 &&= true
ugly2 &&= nil

nice1 + 1
Ops.add(nice2, 1)
Ops.add(ugly1, 1)
Ops.add(ugly2, 1)

Or-assignment

Zombie Killer manages niceness correctly in presence of ||=.

Original

nice1 = true
nice2 = true
ugly1 = nil
ugly2 = nil

nice1 ||= true
nice2 ||= nil
ugly1 ||= true
ugly2 ||= nil

Ops.add(nice1, 1)
Ops.add(nice2, 1)
Ops.add(ugly1, 1)
Ops.add(ugly2, 1)

Translated

nice1 = true
nice2 = true
ugly1 = nil
ugly2 = nil

nice1 ||= true
nice2 ||= nil
ugly1 ||= true
ugly2 ||= nil

nice1 + 1
nice2 + 1
ugly1 + 1
Ops.add(ugly2, 1)

Calls Preserving Niceness

A localized string literal is nice.

Original

v = _("Hello")
Ops.add(v, "World")

Translated

v = _("Hello")
v + "World"

Calls Generating Niceness

nil? makes any value a nice value but unfortunately it seems of little practical use. Even though there are two zombies that have boolean arguments (Builtins.find and Builtins.filter), they are just fine with nil since it is a falsey value.

Translation Below Top Level

Zombie Killer translates a zombie nested in other calls.

Original

v = 1
foo(bar(Ops.add(v, 1), baz))

Translated

v = 1
foo(bar(v + 1, baz))

Chained Translation

Zombie Killer translates a left-associative chain of nice zombies.

Original

Ops.add(Ops.add(1, 2), 3)

Translated

(1 + 2) + 3

Zombie Killer translates a right-associative chain of nice zombies.

Original

Ops.add(1, Ops.add(2, 3))

Translated

1 + (2 + 3)

In case arguments are translated already

Zombie Killer translates Ops.add of plus and literal.

Original

Ops.add("Hello" + " ", "World")

Translated

("Hello" + " ") + "World"

Zombie Killer translates Ops.add of parenthesized plus and literal.

Original

Ops.add(("Hello" + " "), "World")

Translated

("Hello" + " ") + "World"

Zombie Killer translates Ops.add of literal and plus.

Original

Ops.add("Hello", " " + "World")

Translated

"Hello" + (" " + "World")

If

With a single-pass top-down data flow analysis, that we have been using, we can process the if statement but not beyond it, because we cannot know which branch was taken.

We can proceed after the if statement but must start with a clean slate. More precisely we should remove knowledge of all variables affected in either branch of the if statement, but we will first simplify the job and wipe all state for the processed method.

Zombie Killer translates the then body of an if statement.

Original

if cond
  Ops.add(1, 1)
end

Translated

if cond
  1 + 1
end

Zombie Killer translates the then body of an unless statement.

Original

unless cond
  Ops.add(1, 1)
end

Translated

unless cond
  1 + 1
end

It translates both branches of an if statement, independently of each other.

Original

v = 1
if cond
  Ops.add(v, 1)
  v = nil
else
  Ops.add(1, v)
  v = nil
end

Translated

v = 1
if cond
  v + 1
  v = nil
else
  1 + v
  v = nil
end

The condition also contributes to the data state.

Original

if cond(v = 1)
  Ops.add(v, 1)
end

Translated

if cond(v = 1)
  v + 1
end

A variable is not nice after its niceness was invalidated by an if

Plain if

Unchanged

v = 1
if cond
  v = nil
end
Ops.add(v, 1)

Trailing if.

Unchanged

v = 1
v = nil if cond
Ops.add(v, 1)

Plain unless.

Unchanged

v = 1
unless cond
  v = nil
end
Ops.add(v, 1)

Trailing unless.

Unchanged

v = 1
v = nil unless cond
Ops.add(v, 1)

Resuming with a clean slate after an if

It translates zombies whose arguments were found nice after an if.

Original

if cond
   v = nil
end
v = 1
Ops.add(v, 1)

Translated

if cond
   v = nil
end
v = 1
v + 1

Case

With a single-pass top-down data flow analysis, that we have been using, we can process the case statement but not beyond it, because we cannot know which branch was taken.

We can proceed after the case statement but must start with a clean slate. More precisely we should remove knowledge of all variables affected in either branch of the case statement, but we will first simplify the job and wipe all state for the processed method.

Zombie Killer translates the when body of a case statement.

Original

case expr
  when 1
    Ops.add(1, 1)
end

Translated

case expr
  when 1
    1 + 1
end

It translates all branches of a case statement, independently of each other.

Original

v = 1
case expr
  when 1
    Ops.add(v, 1)
    v = nil
  when 2
    Ops.add(v, 2)
    v = nil
  else
    Ops.add(1, v)
    v = nil
end

Translated

v = 1
case expr
  when 1
    v + 1
    v = nil
  when 2
    v + 2
    v = nil
  else
    1 + v
    v = nil
end

The expression also contributes to the data state.

Original

case v = 1
  when 1
    Ops.add(v, 1)
end

Translated

case v = 1
  when 1
    v + 1
end

The test also contributes to the data state.

Original

case expr
  when v = 1
    Ops.add(v, 1)
end

Translated

case expr
  when v = 1
    v + 1
end

A variable is not nice after its niceness was invalidated by a case

Unchanged

v = 1
case expr
  when 1
    v = nil
end
Ops.add(v, 1)

Resuming with a clean slate after a case

It translates zombies whose arguments were found nice after a case.

Original

case expr
  when 1
    v = nil
end
v = 1
Ops.add(v, 1)

Translated

case expr
  when 1
    v = nil
end
v = 1
v + 1

Loops

While and Until

while and its negated twin until are loops which means assignments later in its body can affect values earlier in its body and in the condition. Therefore we cannot process either one and we must clear the state afterwards.

Zombie Killer does not translate anything in the outer scope that contains a while.

Unchanged

v = 1
while Ops.add(v, 1)
  Ops.add(1, 1)
end
Ops.add(v, 1)

Zombie Killer does not translate anything in the outer scope that contains an until.

Unchanged

v = 1
until Ops.add(v, 1)
  Ops.add(1, 1)
end
Ops.add(v, 1)

Zombie Killer can continue processing after a while. Pun!

Original

while cond
  foo
end
v = 1
Ops.add(v, 1)

Translated

while cond
  foo
end
v = 1
v + 1

Zombie Killer can continue processing after an until. No pun.

Original

until cond
  foo
end
v = 1
Ops.add(v, 1)

Translated

until cond
  foo
end
v = 1
v + 1

Zombie Killer can parse both the syntactic and semantic post-condition.

Unchanged

body_runs_after_condition while cond
body_runs_after_condition until cond

begin
  body_runs_before_condition
end while cond

begin
  body_runs_before_condition
end until cond

For

for loops are just syntax sugar for an each call with a block. Thus, we need to treat them as blocks.

Zombie Killer does not translate inside a for and resumes with a clean slate.

Original

v = 1
v = Ops.add(v, 1)

for i in [1, 2, 3]
  v = Ops.add(v, 1)
  v = uglify
end

v = Ops.add(v, 1)
w = 1
w = Ops.add(w, 1)

Translated

v = 1
v = v + 1

for i in [1, 2, 3]
  v = Ops.add(v, 1)
  v = uglify
end

v = Ops.add(v, 1)
w = 1
w = w + 1

Exceptions

Raising an exception is not a problem at the raise site. There it means that all remaining code in a def is skipped. It is a problem at the rescue or ensure site where it means that some of the preceding code was not executed.

Zombie Killer translates the parts, joining else, rescue separately.

Original

def foo
  v = 1
  Ops.add(v, 1)
rescue
  w = 1
  Ops.add(w, 1)
  v = nil
rescue
  Ops.add(w, 1)
else
  Ops.add(v, 1)
end

Translated

def foo
  v = 1
  v + 1
rescue
  w = 1
  w + 1
  v = nil
rescue
  Ops.add(w, 1)
else
  v + 1
end

Skipping Code

Zombie Killer does not translate code that depends on niceness skipped via an exception.

Unchanged

def a_problem
  v = nil
  w = 1 / 0
  v = 1
rescue
  puts "Oops", Ops.add(v, 1)
end

Exception Syntax

Zombie Killer can parse the syntactic variants of exception handling.

Unchanged

begin
  foo
  raise "LOL"
  foo
rescue Error
  foo
rescue Bug, Blunder => b
  foo
rescue => e
  foo
rescue
  foo
ensure
  foo
end
yast rescue nil

Retry

The retry statement makes the begin-body effectively a loop which limits our translation possibilities.

Zombie Killer does not translate a begin-body when a rescue contains a retry.

Unchanged

def foo
  v = 1
  begin
    Ops.add(v, 1)
    maybe_raise
  rescue
    v = nil
    retry
  end
end

Blocks

Inside a block the data flow is more complex than we handle now. After it, we start anew.

Zombie Killer does not translate inside a block and resumes with a clean slate.

Original

v = 1
v = Ops.add(v, 1)

2.times do
  v = Ops.add(v, 1)
  v = uglify
end

v = Ops.add(v, 1)
w = 1
w = Ops.add(w, 1)

Translated

v = 1
v = v + 1

2.times do
  v = Ops.add(v, 1)
  v = uglify
end

v = Ops.add(v, 1)
w = 1
w = w + 1

Formatting

Zombie Killer does not translate Ops.add if any argument has a comment.

Unchanged

Ops.add(
  "Hello",
  # foo
  "World"
)

Templates

It translates.

Original

Translated

It does not translate.

Unchanged