These inspections have been available for Java for a long time and have proved invaluable in finding numerous obscure bugs. However, no such inspections have ever been implemented for Scala. This became the focus of my internship with the IntelliJ Scala<\/a> team this summer, and now we\u2019re happy to announce that we\u2019re bringing dataflow-based inspections to Scala developers.<\/p>\n\n\n\n They come enriched with special support for many important Scala-specific structures, like case classes or sequences. You can already try them out in our regular Nightly builds<\/a> or wait until the next major IntelliJ IDEA release at the end of November 2021.<\/p>\n\n\n\n Dataflow analysis consists of two major phases: control flow building<\/strong> and proper dataflow analysis<\/strong>.<\/p>\n\n\n\n First, we transform the abstract syntax tree<\/strong><\/a> of the program into something that will give us more information about its actual execution flow \u2013 the control flow graph<\/strong><\/a>. In IntelliJ IDEA, we represent control flow using our own stack-based intermediate representation<\/strong><\/a>, which is similar to Java bytecode. In short, we compile the user code into this bytecode-like representation.<\/p>\n\n\n\n Each method is then analyzed separately. We partially execute its body, using the body’s control flow representation and keeping track of useful semantic information, especially possible variable values<\/strong>. However, most of those are unknown and will only become known at runtime (e.g. values of method parameters). That is why often we can only obtain and process abstract information like \u201cx<\/em> is even and greater than 10\u201d <\/em>or \u201cy <\/em>is an immutable list with five elements\u201d<\/em>. For this reason, this procedure is called abstract interpretation<\/strong><\/a>.<\/p>\n\n\n\n Once we collect all of that dataflow information<\/strong>, we can analyze it<\/strong> to identify suspicious places<\/strong> and possible bugs<\/strong> in the code, like a complex expression that always evaluates to the same value or an access to a collection with an index larger than its size.<\/p>\n\n\n\n To illustrate this more concretely, let\u2019s have a look at this very simple piece of code.<\/p>\n\n\n\n When we analyze the first method, we know everything about x.<\/em> The condition 2 > 3<\/em> is always false, so x<\/em> will always be 7<\/em>. We can propagate this information and use it later when we see x<\/em> again in the code \u2013 in this case in the returned expression.<\/p>\n\n\n\n In the second method however, we don\u2019t know much about y<\/em>. The values of a<\/em> and b<\/em> are unknown, so there are two possible paths: y<\/em> can either be 5<\/em> or 7<\/em>, but we don\u2019t know which one. But this is already a lot of information \u2013 we can\u2019t say anything about y == 7<\/em>, but we can confidently say that y > 4<\/em> is always true in any possible program execution scenario.<\/p>\n\n\n\n This example is very simple, but the power of dataflow analysis lies in the fact that we can choose to track many different kinds of information about those variables. Those pieces of information can then be combined with each other, leading us to powerful insights about the code being analyzed. Let\u2019s briefly take a look at several examples of what Scala DFA is capable of in its current state.<\/p>\n\n\n\n One cool thing about the IntelliJ DFA framework, on top of which we built our Scala DFA, is that it can track relations<\/strong> between variables, even if nothing else is known about them.<\/p>\n\n\n\n In the first example, dataflow analysis is able to figure out the relation between the otherwise unknown a<\/em> and c<\/em> by applying transitivity<\/strong> to the information it has collected from the outer condition. In the second one, it knows that inside the body of the else<\/em> branch, !(a != b), <\/em>which means a == b<\/em>, and therefore a – b == 0<\/em>.<\/p>\n\n\n\n A major advantage of this DFA is that many of its features easily extend to all types<\/strong>, not just simple ones like Int<\/em>.<\/p>\n\n\n\n A number of Scala-specific methods, <\/strong>including some standard math functions<\/strong>, receive their own special support<\/strong> in Scala DFA.<\/p>\n\n\n\n We have also added special support for Scala collections<\/strong>. Dataflow analysis can, for example, tell you that two sequences cannot be equal because they\u2019re of different sizes, or that your collection access will produce an IndexOutOfBoundsException<\/em> or NoSuchElementException<\/em>.<\/p>\n\n\n\n Several of the most common sequence methods are supported as well.<\/p>\n\n\n\n Dataflow analysis in IntelliJ IDEA analyzes the body of each method separately. As such, it inherently doesn\u2019t support interprocedural analysis<\/strong>. This means that code like this won\u2019t be fully analyzed in Java (the analysis won\u2019t go inside absoluteDifference<\/em>).<\/p>\n\n\n\n To be fair, the team responsible for Java DFA has been trying to overcome this limitation in many creative and efficient ways, like through static constant evaluation, getter inlining, contracts, etc., but in the vast majority of cases, it won\u2019t do any interprocedural analysis.<\/p>\n\n\n\n In Scala, a fundamentally functional language, this is a much more significant limitation, and we decided we needed to overcome it. We\u2019ve laid a solid foundation for interprocedural analysis that, in the current state, supports two major features: interprocedural analysis for invocations of private and final methods<\/strong> (including methods in final classes and objects) and tracking class parameters<\/strong>. In effect, if we translate the above code to Scala, Scala DFA will go inside the external method and analyze it completely.<\/p>\n\n\n\n Another advantage of our analysis is that it supports all of the many kinds of Scala invocations and their syntactic sugars, like infix notation, apply <\/em>methods, right-associativity, or named and default parameters. So it will still work if you do something like this.<\/p>\n\n\n\n As mentioned before, our DFA can also process and track class parameters.<\/p>\n\n\n\n The overall scope of the Scala DFA project is large. A lot has already been done, but the number of potential additions or improvements is even greater. That is why, from the very beginning, one of our main focuses was to lay a strong foundation that would make it easy to add new things in the future. Along the way, we encountered several major challenges, and many of the design ideas we came up with to overcome them are very interesting in their own right. Probably the best example of this is Invocation Info<\/strong>.<\/p>\n\n\n\n The problem we faced was that, in Scala, a huge variety of things are some kind of method invocation. In Java, a method invocation is always either something.method(arg1, arg2)<\/em> or Something.method(arg1, arg2)<\/em>. In Scala, both of these are present as well, but all of the following are also method invocations.<\/p>\n\n\n\n This is nice for a programmer who uses the language, but it is a nightmare for any compiler programmer, especially if you add named, default, and implicit parameters, multiple parameter lists, varargs, etc. Imagine needing to extract precise information about an invocation while having to remember and depend on every possible variant of this syntax in every possible place where we\u2019re dealing with invocations.<\/p>\n\n\n\n This is why we designed and implemented an abstraction called Invocation Info<\/strong>. We have a factory that takes any possible invocation as its input, in any syntactic variant, and produces an InvocationInfo <\/strong>instance.<\/p>\n\n\n\n This class represents all possible Scala invocations in a standardized, convenient, and syntax-agnostic way. All sugared and desugared versions of equivalent invocations (like 3 + 8<\/em> and 3.+(8)<\/em>) generate the same InvocationInfo. There are some fine details here, for example x :: list <\/em>is almost equivalent to list.::(x) <\/em>(because ::<\/em> is right-associative), but argument expressions in Scala are always evaluated from left to right and this creates a slight difference in the semantics of these two expressions.<\/p>\n\n\n\n Invocation Info is designed to collect and offer all necessary information about the original invocation, including multiple argument lists, by-name arguments, evaluation order, this<\/em> argument, etc.<\/p>\n\n\n\n The details of Invocation Info\u2019s design and how it is used in the control flow builder and the analysis itself would make for another long and interesting article. But the key takeaway is that implementing all of that special support for various methods would have been impossible without it. We strongly believe that this tool and our control flow builder are so useful that they may find many different applications outside of dataflow analysis in the future development of the Scala plugin.<\/p>\n\n\n\n I highly recommend watching the IntelliJ IDEA Conf talk by Tagir Valeev<\/a>, which summarizes how our dataflow analysis in IntelliJ IDEA works behind the scenes, what it can do, and how we manipulate it to extract as many useful insights and high-quality inspections as possible.<\/p>\n\n\n\n If you\u2019re curious about what kinds of bugs dataflow analysis can help you find, read Tagir\u2019s JetBrains Blog article<\/a>, where he discusses lots of real-life examples.<\/p>\n\n\n\n Special thanks to Tobias Kahlert<\/a> who supervised my project, in particular for a great theoretical and practical introduction to the DFA field and many really fruitful design discussions and ideas.<\/p>\n\n\n\n Achieving such good results also wouldn\u2019t have been possible if I hadn\u2019t built on the existing, robust, and extensible IntelliJ DFA framework. Most of it has been created by Tagir Valeev<\/a>, with whom I\u2019ve also had several helpful discussions throughout my project. Tagir has also been implementing DFA for Kotlin, which was helpful for me as a reference in the early stages of my work.<\/p>\n\n\n\n We need your feedback!<\/strong> If you encounter any bugs in this feature, please report them to our YouTrack<\/a>. If you have any questions, feel free to ask them in our Gitter<\/a>.<\/p>\n\n\n\n <\/p>\n","protected":false},"author":1298,"featured_media":196678,"comment_status":"closed","ping_status":"closed","template":"","categories":[808,8058,6945],"tags":[6713,3369,6796,83,31,225,6799],"cross-post-tag":[],"acf":[],"_links":{"self":[{"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/scala\/196208"}],"collection":[{"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/scala"}],"about":[{"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/types\/scala"}],"author":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/users\/1298"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/comments?post=196208"}],"version-history":[{"count":7,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/scala\/196208\/revisions"}],"predecessor-version":[{"id":198352,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/scala\/196208\/revisions\/198352"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/media\/196678"}],"wp:attachment":[{"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/media?parent=196208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/categories?post=196208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/tags?post=196208"},{"taxonomy":"cross-post-tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ko\/wp-json\/wp\/v2\/cross-post-tag?post=196208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Dataflow analysis in a nutshell<\/h2>\n\n\n\n
Control flow building<\/h3>\n\n\n\n
Proper dataflow analysis<\/h3>\n\n\n\n
How it works<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image12.png\")
<\/figure>\n\n\n\n
Current capabilities of Scala DFA<\/h2>\n\n\n\nTracking relations<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image7-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image4-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image6-1.png\")
<\/figure>\n\n\n\nSupport for known methods<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image3-2.png\")
<\/figure>\n\n\n\nSupport for Scala collections<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image5-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image1-1.png\")
<\/figure>\n\n\n\nInterprocedural analysis <\/h2>\n\n\n\n
Java DFA<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image10-1.png\")
<\/figure>\n\n\n\nScala DFA<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image2-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image11-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image9-1.png\")
<\/figure>\n\n\n\nArchitecture and Invocation Info<\/h2>\n\n\n\n
The challenge<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/11\/image8-1.png\")
<\/figure>\n\n\n\nThe solution<\/h3>\n\n\n\n
Learn more about DFA<\/h2>\n\n\n\n
Credits<\/h2>\n\n\n\n
Feedback<\/h2>\n\n\n\n