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

Modelling State Machines with Ragel

nelstrom
August 18, 2013

Modelling State Machines with Ragel

Ragel is a State Machine Compiler, which can generate Ruby code (as well as C, Java, Go, and more). It can be used for writing robust protocol implementations, parsing data formats, and performing lexical analysis of programming languages. Ragel is used in many open source projects including Gherkin, Thin, Min, Mongrel, Redcloth, Radiant, and Hpricot.

To demonstrate Ragel's capabilities we'll model Vim, which is a Finite State Machine. We'll do so by parsing a stream of Vim keystrokes, using Ragel state machines to manage the transitions between Vim's modes. We'll see how to generate state chart visualisations with Ragel, and how these can be used to debug our state machines. The resulting program will enable us to analyse and visualise the interactions of a Vim user.

nelstrom

August 18, 2013
Tweet

More Decks by nelstrom

Other Decks in Technology

Transcript

  1. MODELLING STATE MACHINES WITH RAGEL Eurucamp, 2013 Drew Neil @nelstrom

    “Charles Babbage’s Difference Engine No. 2” by Ricardo Ferreira
  2. Chapter 3 The Simplest Computers A Finite State Machine, also

    known as a Finite Automaton, is a drastically simplified model of a computer that is easy to understand, easy to reason about, and easy to implement in hardware or software.
  3. Chapter 3 The Simplest Computers It’s possible to convert any

    regular expression into an equivalent Nondeterministic Finite Automaton -- every string matched by the regular expression is accepted by the NFA, and vice versa.
  4. Ragel state machines can not only recognize byte sequences as

    regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language.
  5. host %% inline ragel %%{ multi-line ragel action { host

    }; }%% host Birds-eye view of a ragel file
  6. $ ragel -h | grep "host language" host language: -C

    The host language is C (default) -D The host language is D -Z The host language is Go -J The host language is Java -R The host language is Ruby -A The host language is C# -O The host language is OCaml Supported host languages
  7. $ ragel -R source.rl Compile source.rl using Ruby as host

    language Producing source.rb as output $ ragel -V source.rl > graph.dot Generate a visualisation in .dot format Can be viewed with Graphviz Compiling Ragel
  8. %%{ machine accepter; motion = [hjklbwe0]; switch = [iIaAsSoO]; escape

    = 27; input = (any - escape); insert_mode := ( input* escape @{ fret; } ); normal_mode := ( motion | switch @{ fcall insert_mode; } )*; }%% class Accepter attr_accessor :data def initialize() %% write data; end def process(input) @data = input.unpack("c*") stack = [] %% write init; %% write exec; return cs end end accepter.rl
  9. def process(input) @data = input.unpack("c*") stack = [] begin "

    p ||= 0 " pe ||= data.length " cs = accepter_start " top = 0 end begin " _klen, _trans, _keys, _acts = nil " _goto_level = 0 " _resume = 10 " _eof_trans = 15 " _again = 20 # 150 more LOC like this... end return cs end " def process(input) @data = input.unpack("c*") stack = [] %% write init; %% write exec; return cs end
  10. h e l l o h e l l o

    ␛ h move left e move to end of word l move right l move right o hello enter “hello” on a new line ␛ return to Normal mode
  11. Machine definition: <label> = <expression>; Ragel syntax Machine instantiation: <label>

    := <expression>; # TOKENS motion = [hjklbwe0]; switch = [iIaAsSoO]; escape = 27; input = (any - escape); # PARSER normal_mode := (motion)*;
  12. Ragel control flow fcall <label>; Push the target state and

    jump to the entry point defined by <label> fret; Return to the target state of the transition on which the last fcall was made. PUSH POP
  13. %%{ machine accepter; # ... normal_mode := ( motion |

    switch @{ fcall insert_mode; } )*; }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/accepter.rl
  14. %%{ machine accepter; # ... insert_mode := ( input* escape

    @{ fret; } ); }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/accepter.rl
  15. %%{ machine accepter; motion = [hjklbwe0]; switch = [iIaAsSoO]; escape

    = 27; input = (any - escape); insert_mode := ( input* escape @{ fret; } ); normal_mode := ( motion | switch @{ fcall insert_mode; } )*; }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/accepter.rl
  16. 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l',

    'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF
  17. class Accepter def process(input) @data = input.unpack("c*") %% write init;

    %% write exec; return cs end def accept?(input) process(input) > 0 end end https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/accepter.rl
  18. describe Accepter do it 'accepts hellohello<Esc>' do assert Accepter.new.accept?("hellohello\e") end

    it 'rejects visual mode (for example)' do refute Accepter.new.accept?("viw") end end https://github.com/nelstrom/ragel-vim-demo/blob/master/test/accepter_test.rb
  19. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 0 cs = 2
  20. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 1 cs = 2
  21. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 2 cs = 2
  22. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 3 cs = 2
  23. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 4 cs = 2
  24. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 5 cs = 1
  25. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 6 cs = 1
  26. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 7 cs = 1
  27. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 8 cs = 1
  28. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 9 cs = 1
  29. index character 0 1 2 3 4 5 6 7

    8 9 10 h e l l o h e l l o <Esc> Ragel’s cursor 2 IN 1 insert_mode normal_mode '0', 'b', 'e', 'h', 'j'..'l', 'w' 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / push_insert_mode 3 27 / return DEF p = 10 cs = 3
  30. %%{ machine emitter; action H { @head = p }

    action T { @tail = p } # TOKENS motion = [hjklbwe0] >H@T; switch = [iIaAsSoO] >H@T; escape = 27 >H@T; input = (any - escape) >H@T; # ... }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/emitter.rl
  31. class Emitter attr_accessor :data # initialize # process def strokes

    @data[@head..@tail].pack('c*') end end https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/emitter.rl
  32. %%{ machine emitter; motion = [hjklbwe0] >H@T @{ @events <<

    {motion: strokes} }; switch = [iIaAsSoO] >H@T @{ @events << {switch: strokes} }; escape = 27 >H@T @{ @events << {escape: '<Esc>'} }; input = (any - escape) >H@T @{ @events << {input: strokes} }; # ... }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/emitter.rl
  33. describe Emitter do it 'accepts motions, switches, and insertions' do

    Emitter.new(events = []).process("hellohello\e") assert_equal [ {:motion=>"h"}, {:motion=>"e"}, {:motion=>"l"}, {:motion=>"l"}, {:switch=>"o"}, {:input=>"h"}, {:input=>"e"}, {:input=>"l"}, {:input=>"l"}, {:input=>"o"}, {:escape=>"<Esc>"} ], events end end https://github.com/nelstrom/ragel-vim-demo/blob/master/test/emitter_test.rb
  34. h e l l Normal Normal > Visual ␛ Normal

    Change selection b iw v c hello Normal > Insert
  35. fcall <label>; Push the target state and jump to the

    entry point defined by <label> fret; Return to the target state of the transition on which the last fcall was made. fnext <label>; Set the next state to be the entry point defined by label. PUSH POP SWITCH Ragel control flow
  36. %%{ machine visual; action H { @head = p }

    action T { @tail = p } # ... start_visual = 'v' >H@T @{ @events << {start_visual: strokes} }; normal_mode := ( motion | start_visual @{ fcall visual_mode; } )*; }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/visual.rl
  37. %%{ machine visual; action H { @head = p }

    action T { @tail = p } # ... text_object = ([ai][bBpstwW]) >H@T @{ @events << {text_object: strokes} }; v_switch = [sScC] >H@T @{ @events << {switch: strokes} }; # ... }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/visual.rl
  38. %%{ machine visual; # ... visual_mode := ( ( motion

    | text_object )* ( v_switch @{ fnext insert_mode; } | escape @{ fret; } ) ); }%% https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/visual.rl
  39. it 'accepts vhjiwhello<Esc>el' do Visual.new(events = []).process("vhjiwchello\eel") assert_equal [ {:start_visual=>"v"},

    {:motion=>"h"}, {:motion=>"j"}, {:text_object=>"iw"}, {:switch=>"c"}, {:input=>"h"}, {:input=>"e"}, {:input=>"l"}, {:input=>"l"}, {:input=>"o"}, {:escape=>"<Esc>"}, {:motion=>"e"}, {:motion=>"l"} ], events end https://github.com/nelstrom/ragel-vim-demo/blob/master/test/visual_test.rb
  40. 4 IN 1 insert_mode 2 visual_mode normal_mode '0', 'b', 'e',

    'h', 'j'..'l', 'w' / H, T, 6:33 'A', 'I', 'O', 'S', 'a', 'i', 'o', 's' / H, T, 7:33, 30:13 'v' / H, T, 11:40, 31:19 5 6 27 / H, T, 8:33, 17:13 DEF / H, T, 9:33 27 / H, T, 8:33, 24:15 '0', 'b', 'e', 'h', 'j'..'l', 'w' / H, T, 6:33 'C', 'S', 'c', 's' / H, T, 13:40, 23:17 3 'a', 'i' / H 'B', 'W', 'b', 'p', 's'..'t', 'w' / T, 12:40
  41. ["x]x Delete [count] characters under and after the cursor [into

    register x]. Does the same as "dl". :help x x cut 1 character, save to default register 2x cut 2 characters, save to default register “ax cut 1 character, save to register a
  42. 2”ax cut 2 characters, save to register a “a2x cut

    2 characters, save to register a 3“a2x cut 6 characters, save to register a ["x]x Delete [count] characters under and after the cursor [into register x]. Does the same as "dl". :help x
  43. count = [1-9]; register = '"' [a-z]; cut_command = count?

    register? count? 'x'; normal_mode := (cut_command)*; https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/faulty_cut.rl
  44. 5 IN normal_mode 1 '"' 4 '1'..'9' 'x' 2 'a'..'z'

    3 '1'..'9' 'x' 'x' '"' '1'..'9' 'x'
  45. count = [1-9]; register = '"' [a-z]; cut_command = count?

    register? count? 'x'; normal_mode := (cut_command)*; https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/faulty_cut.rl
  46. count = [1-9]; register = '"' [a-z]; cut_command = (

    count? register )? count? 'x'; normal_mode := (cut_command)*; https://github.com/nelstrom/ragel-vim-demo/blob/master/lib/cut.rl
  47. 5 IN normal_mode 1 '"' 4 '1'..'9' 'x' 2 'a'..'z'

    3 '1'..'9' 'x' 'x' '"' 'x' 2x
  48. 5 IN normal_mode 1 '"' 4 '1'..'9' 'x' 2 'a'..'z'

    3 '1'..'9' 'x' 'x' '"' 'x' “a2x
  49. 5 IN normal_mode 1 '"' 4 '1'..'9' 'x' 2 'a'..'z'

    3 '1'..'9' 'x' 'x' '"' 'x' 3“a2x