Parsing RBS

RubyKaigi 2023

Transcript

1. Parsing RBS দຊ फଠ࿠ (Soutaro Matsumoto)
2. Parsing RBS দຊ फଠ࿠ (Soutaro Matsumoto) Matsumoto is here
3. Parsing RBS দຊ फଠ࿠ (Soutaro Matsumoto) Matsumoto is here Where is Soutaro?
4. Where is Soutaro?
5. Tokyo Matsumoto
6. Tokyo Matsumoto Soutaro
7. Tokyo Matsumoto Soutaro Soutaro
8. Soutaro station (Forget the transliteration variations in photos)
9. Soutaro station Soutaro timetable (Forget the transliteration variations in photos)
10. Soutaro station Soutaro timetable Soutaro bus stop (Forget the transliteration variations in photos)
11. Soutaro station Soutaro timetable Soutaro bus stop Soutaro cedar trees (Forget the transliteration variations in photos)
12. Soutaro station Soutaro timetable Soutaro bus stop Soutaro cedar trees Soutaro park (Forget the transliteration variations in photos)
13. Parsing RBS Soutaro Matsumoto
14. Recent updates on Steep/RBS • RBS 3.1 • Steep 1.4
15. New syntaxes in RBS 3.0 Class/module alias syntax Use syntax (Import in Java/C# for RBS) (RBS) (Ruby)
16. Steep 1.4 • RBS 3.0 support • Signature help • Better completion in RBS
17. Signature help • A method signature list pops up on method calls to help developers typing arguments
18. Signature help • A method signature list pops up on method calls to help developers typing arguments
19. Better type name completion • Typing chan resolves to Parseg::TokenFactory::change • It inserts shorter names based on the current module nesting context
20. Better type name completion • Typing chan resolves to Parseg::TokenFactory::change • It inserts shorter names based on the current module nesting context
23. Why two di ff erent type names here? 🤔
24. • When parameter type is being typed, it has syntax error and the module nesting context is lost → Absolute type name is inserted 🤷 module Parseg module ParsingSession def intersect?: (Parseg::TokenFactory::change) end end module Parseg module ParsingSession def intersect?: (c) end end
25. • When return type is being typed, it's valid syntax → Relative type name is inserted 🙆 module Parseg module ParsingSession def intersect?: ... -> TokenFactory::change end end module Parseg module ParsingSession def intersect?: ... -> c end end
26. Parsing broken RBS matters • The inconsistency is caused by parsing errors • We need a parser that continue working even with syntax errors to provide advanced IDE features
29. 1. Demo 2. Top-down parser outline 3. Error recovery (1) 4. Error recovery (2) 5. Error recovery (3) You will be able to write a top-down parser with error recovery. 💪
30. Error tolerant parser generator • Generates top-down parser with error recovery • Grammar de fi nition in Ruby DSL • (Doesn't generate any parser code yet 😜) https://github.com/soutaro/parseg
31. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
32. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
33. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
34. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
35. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
36. Grammar De fi nition class_decl ::= class module_name 
 class_member* 
 end module_name ::= UIDENT class_member ::= class_decl | method_definition | attr_reader | ...
37. Output
38. Output
39. Output
40. Output
41. Output
42. Output
43. Output
44. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
45. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
46. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
47. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
48. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
49. Parser implementation class_decl ::= class module_name 
 class_member* 
 end • Each non-terminal symbols has corresponding method • Call the parsing methods to construct the content of the tree
50. • Alternation is implemented with case analysis on the fi rst token of the input class_member ::= class_decl | method_definition | attr_reader | ...
51. • Alternation is implemented with case analysis on the fi rst token of the input class_member ::= class_decl | method_definition | attr_reader | ...
52. • Alternation is implemented with case analysis on the fi rst token of the input class_member ::= class_decl | method_definition | attr_reader | ...
53. • Alternation is implemented with case analysis on the fi rst token of the input class_member ::= class_decl | method_definition | attr_reader | ...
54. Parsing result class_decl ::= class module_name class_member* end method_definition ::= def method_name : method_type
55. Parsing result class_decl ::= class module_name class_member* end method_definition ::= def method_name : method_type
56. Parsing result class_decl ::= class module_name class_member* end method_definition ::= def method_name : method_type
61. Parsing error • We can fi nd some structure from the input, even it has a syntax error • There is a class declaration • There is a method de fi nition • Non tolerant parser tells you nothing
62. method_definition ::= def method_name : method_type
63. method_definition ::= def method_name : method_type
64. method_definition ::= def method_name : method_type
65. Introduce MissingTree
66. method_definition ::= def method_name : method_type
67. method_definition ::= def method_name : method_type
71. Error tolerant parser (1) • Inserts MissingTree instead of raising errors 😃
72. #initialize de fi nition disappeared 🤔
73. → MissingTree
74. → MissingTree → MissingTree
75. → MissingTree → MissingTree → MissingTree
76. → MissingTree → MissingTree → MissingTree The -> token stays at the beginning of the input
77. Skip tokens • One token blocks further parsing when no rule handles the token • 💡 Skip that tokens to continue parsing
78. • Tokens that may be consumed by the parsing methods are: • Possible fi rst tokens of type (UIDENT, void, untyped, ...) • class, attr_reader, and def for next class_member • end for closing the class declaration • class for next class declaration attr_reader ::= attr_reader attribute_name : type
79. Implementation • Skips tokens that cannot be consumed in the rule before processing every rule • (And calculate the consumable tokens set)
81. Error tolerant parser (2) • Inserts MissingTree instead of raising errors • Skip tokens that cannot be consumed with other possible rules 😃 This is well-known error recovery strategy for top-down parsers. 
 (https://github.com/microsoft/tolerant-php-parser)
82. 🤔
87. Nested declaration • Inner class declaration eats the following method de fi nition • Conference#initialize disappears and unexpected type error will be detected • Better error recovery is to close the Talk de fi nition immediately
88. What was happening? class Conference def initialize: (String, Integer) -> void end
89. What was happening? class Conference def initialize: (String, Integer) -> void end class Conference class Talk def initialize: (String, Integer) -> void end
90. What was happening? class Conference def initialize: (String, Integer) -> void end class Conference class Talk def initialize: (String, Integer) -> void end class Conference class Talk end def initialize: (String, Integer) -> void end
91. What was happening? class Conference def initialize: (String, Integer) -> void end class Conference class Talk def initialize: (String, Integer) -> void end class Conference class Talk end def initialize: (String, Integer) -> void end class Conference
92. Key ideas • Let parser use the changes made on input since the last successful parsing result • Avoid moving existing elements into new trees
93. Key ideas • Let parser use the changes made on input since the last successful parsing result • Avoid moving existing elements into new trees 😵 😁
94. Change based error recovery • Identify which tokens are changed since the last successful parsing • Closes the declaration at the end of change Inserted tokens Close the declaration
95. class Conference def initialize : ...
96. class Conference def initialize : ... Text inserted class Talk
97. class Conference def initialize : ... class Conference class Talk def initialize : ... Changed tokens Text inserted class Talk
98. class Conference def initialize : ... class Conference class Talk def initialize : ... Changed tokens Text inserted class Talk class Conference class Talk [EOC] def initialize : ... Inserts a marker token
99. class Conference class Talk [EOC] def initialize : ...
100. class Conference class Talk [EOC] def initialize : ...
101. class Conference class Talk [EOC] def initialize : ...
102. class Conference class Talk [EOC] def initialize : ...
103. class Conference class Talk [EOC] def initialize : ...
104. class Conference class Talk [EOC] def initialize : ...
105. class Conference class Talk [EOC] def initialize : ...
106. class Conference class Talk [EOC] def initialize : ...
107. class Conference class Talk [EOC] def initialize : ...
108. class Conference class Talk [EOC] def initialize : ...
109. class Conference class Talk [EOC] def initialize : ...
110. class Conference class Talk [EOC] def initialize : ...
111. Change based error recovery • The error recovery runs only after normal parsing fails to keep successful results identical to the results of original parser
114. Change based error recovery • 👍 Minimal grammar modi fi cation • 👍 Token based change detection • No tree di ff calculation required • Changed tokens are easily detected by LSP edit noti fi cations • 😵 Unsupported text editing patterns may result in confusing errors
115. Error tolerant parser (3) • Inserts MissingTree instead of raising errors • Skip tokens that cannot be consumed with other possible rules • Avoid moving existing elements if parsing fails 😃
116. 🎉
117. Open problems • Translating the concrete syntax tree to AST • AST de fi nes a successful parsing result Attribute declarations must have names and types
118. Summary • Planning to replace RBS parser for better development experience • Making a top-down parser error tolerant • Generates parsing tree even with syntax errors • Change based error recovery
120. • Trial 1: Based on ML's type inference (2007) • Trial 2: Based on control fl ow analysis (2009) • (Break until Oedo RubyKaigi 2017) • Trial 3: Steep -- introducing type declarations My 15 years for type checking Ruby programs
121. • Trial 1: Based on ML's type inference (2007) • Trial 2: Based on control fl ow analysis (2009) • (Break until Oedo RubyKaigi 2017) • Trial 3: Steep -- introducing type declarations My 15 years for type checking Ruby programs
122. • Trial 1: Based on ML's type inference (2007) • Trial 2: Based on control fl ow analysis (2009) • (Break until Oedo RubyKaigi 2017) • Trial 3: Steep -- introducing type declarations My 15 years for type checking Ruby programs
124. It was called .rbi
125. No class It was called .rbi
126. Dedicated syntax for types in Ruby No class It was called .rbi
127. Ruby with Steep is the best Ruby programming experience to me ⭐
129. • @soutaro on GitHub/Twitter • @soutaro@ruby.social • matsumoto@soutaro.com