[转] Flip-flop operator

转自 http://blogs.msdn.com/b/tomas/archive/2008/10/27/flip-flop-operator.aspx

Although its usage is discouraged the – a range used in a condition – is still a Ruby language feature. Let's take a look at how IronRuby implements it. First, we need to figure out what exactly it is supposed to do. The general behavior is described in books on Ruby, however to implement it in a compiler you need to sort out all the edge cases. So let's play with it a little.

What distinguishes a flip-flop from a range?

The syntax is the same: expression ‘..’ expression (end-inclusive range) or expression ‘...’ expression (end-exclusive range). A range is considered a flip-flop operator if any of its bound is not an integer literal and if it is used as a condition of the following expressions:

• condition ‘?’ expression ‘:’ expression
• statement ‘if’ condition
• statement ‘unless’ condition
• statement ‘while’ condition
• statement ‘until’ condition
• ‘if’ condition then statements if-tail ‘end’
• ‘unless’ condition then statements else-opt ‘end’
• ‘while’ condition ‘do’ statements ‘end’
• ‘until’ condition ‘do’ statements ‘end’

For example:

irb(main):001:0> 1 if TRUE..FALSE 
=> 1

In addition, parenthesized ranges used in a condition are also flip-flops, e.g.:

irb(main):001:0> 1 if (TRUE..FALSE) 
=> 1

‘(‘ statements ‘)’ is a block expression with a single statement expression TRUE..FALSE. If there are more statements in the block in front of the range it is no longer a flip-flop operator:

irb(main):008:0> 1 if (puts;TRUE..FALSE) 
ArgumentError: bad value for range 

The exception is raised since a range bounds cannot be Booleans.

Any number of nested block expressions works:

irb(main):001:0> 1 if ((((TRUE..FALSE)))) 
=> 1 

And begin-end blocks work as well:

irb(main):032:0> 1 if begin TRUE..FALSE end 
=> 1 

As do any combinations of the two (but only in Ruby 1.9, in Ruby 1.8.6 some combinations don’t work, which I consider a bug):

irb(main):001:0> 1 if (begin (((begin begin TRUE..FALSE end end))) end) 
=> 1 

Also, ranges used in Boolean expressions used as conditions are considered flip-flops:

irb(main):018:0> 1 if t(1)..f(2) and not t(3)..f(4) or t(5)..f(6) 
123456=> 1 
irb(main):018:0> 1 if (t(1)..f(2)) && !(t(3)..f(4)) || (t(5)..f(6)) 
123456=> 1 

where t and f are functions that print the argument and return true and false respectively. The second example also doesn’t work in Ruby 1.8.6, oups.

Let’s summarize what have we just found out: block expressions (parenthesized or begin-end) containing a single range and Boolean expressions propagate the “in-condition” property to their children AST nodes. The “in-condition” property then turns ranges into flip-flop operators. Other nodes don’t propagate it. A method call doesn’t, for example:

irb(main):018:0> 1 if puts(t(1)..f(2)) 
ArgumentError: bad value for range 

Side note: this property is also applied on regular expressions. If a regex is “in-condition” it is compiled as a match against $_ variable:

irb(main):029:0> $_ = 'xz' 
=> "xz" 
irb(main):030:0> 1 if /y/ or ((begin((/x/ and /(z)/))end)) 
=> 1 
irb(main):031:0> $1 
=> "z" 

How does flip-flop work?

We know from the books that flip-flop would probably define some state variable that changes values as the expressions of the operator are evaluated. To figure out how exactly it works I wrote a simple script:

F = false
T = true
x = X = '!'

B = [F,T,x,x,x,T,x,F,F]
E = [x,x,F,F,T,x,T,x,x]
       
def b
  step('b',B)
end

def e
  step('e',E)
end

def step name,value
  r = value[$j]
  puts "#{$j}: #{name} -> #{r.inspect}"
  
  $j += 1
  
  $continue = !r.nil?  
  r == X ? raise : r  
end

$j = 0
$continue = true
while $continue
  if b..e 
    puts "#{$j}: TRUE" 
  else
    puts "#{$j}: FALSE" 
  end
end

In this code we evaluate an end-inclusive flip-flop in a loop. Each time the flip-flop operator is evaluated ‘b’ or ‘e’ method is called, or both methods are called. Global variable $j is an index into B and E arrays defined at the top. The arrays define a sequence of values the methods b and e should return. If x value (‘!’) is to be returned an exception is thrown. This way we can track what the automaton behind the flip-flop operator does. Using the output of the script we can easily deduce how the automaton could look like:

0: b -> false
1: FALSE
1: b -> true
2: TRUE
2: e -> false
3: TRUE
3: e -> false
4: TRUE
4: e -> true
5: TRUE
5: b -> true
6: TRUE
6: e -> true
7: TRUE
7: b -> false
8: FALSE
8: b -> false
9: FALSE
9: b -> nil
10: FALSE.

It has four states: BEFORE, INSIDE, AFTER and a lambda state. In each state b or e expression is evaluated and the automaton transitions to another state based upon the result: true (T) or false (F). If it transitions to INSIDE or AFTER state the flip-flop operator returns true. If it transitions to BEFORE state the operator returns false. If it transitions to the lambda state the operator evaluates b and does one more transition.

The previous automaton works for an end-inclusive flip-flop operator. The one bellow does for an end-exclusive operator – the lambda state is gone:

What code does IronRuby emit?

We emit the following code for end-inclusive flip-flop operator {begin}..{end}:

if state || IsTrue({begin})
  state = IsFalse({end})
  true
else  
  false
end  

The state variable is a Boolean and it’s true iff the automaton is in INSIDE or lambda state. In both states this means evaluate {end} expression, transition to the state given by negated result and return true. If the state variable is false we are either in AFTER or in BEFORE state. In any case {begin} is evaluated. If it returns false we go to/stay in BEFORE state and the result of the flip-flop operator is false. Otherwise we go to the lambda state and evaluate end.

Similarly, the end-exclusive flip-flop operator {begin}...{end} is implemented as

if state
  state = IsFalse({end}) 
  true
else
  state = IsTrue({begin})
end

 

The state variable is allocated in the inner-most method scope. A flip-flop operator used in a block preserves the state across multiple calls to the block:

def y *a; yield *a; end

def test
  $p = proc { |b,e|
    puts b..e ? TRUE : FALSE
  }
  
  y false, &$p  
  y true, true, &$p
  y false, &$p
  y true, false, &$p
end

test

Output:

false 
true 
false 
true 

The method that transforms IronRuby’s RangeExpression node into DLR AST in the case the range is a flip-flop operator looks like:

private MSA.Expression/*!*/ TransformReadCondition(AstGenerator/*!*/ gen) { // Define state variable in the inner most method scope. var stateVariable = gen.CurrentMethod.Builder.DefineHiddenVariable("#in_range", typeof(bool)); var begin = Ast.Box(_begin.TransformRead(gen)); var end = Ast.Box(_end.TransformRead(gen)); if (_isExclusive) { return Ast.Condition(
            stateVariable,
            Ast.Comma(Ast.Assign(stateVariable, Methods.IsFalse.OpCall(end)), Ast.True()),
            Ast.Assign(stateVariable, Methods.IsTrue.OpCall(begin))
        );  
    } else { return Ast.Condition(
            Ast.OrElse(stateVariable, Methods.IsTrue.OpCall(begin)),
            Ast.Comma(Ast.Assign(stateVariable, Methods.IsFalse.OpCall(end)), Ast.True()),
            Ast.False()
        );
                          
    }
}

This code can be found in Ruby\Compiler\Ast\Expressions\RangeExpression.cs. Propagation of “in-condition” property to AST nodes is performed by ToCondition virtual method overridden by RangeExpression, RegularExpression, AndExpression, OrExpression and BodyExpression and called from parser (Ruby\Compiler\Parser\Parser.y).