ReSharper SDK Adventures Part 7 — Factoring expressions
Welcome to another part of the SDK adventures. Most of the sample plugins shown so far have been fairly simple, with implementation times ranging from a few minutes to an hour, at most. In this part of the series I want to show what developing a fully-fledged, complicated feature is like.
Since complex features take a long time to develop, this post will only show the initial phases of development of a factoring context action that we will later refine and improve. Let’s get started!
When writing numeric expressions, you may come accross something like the following:
The above expression is worth analyzing because it’s not perfectly efficient: it’s doing one more multiplication than is needed to get the result. Here’s a better form:
Wouldn’t it be great if ReSharper could help factor out terms in similar expressions? Of course it would, and this is what we’re going to do here. However, as it turns out, this problem is a lot more complicated than it looks.
If you open up an expression such as the one above in ReSharper’s PSI Viewer (you’ll need to be running in Internal mode for this), you’ll see that it’s basically a combination of
IBinaryExpressions of type
IMultiplicativeExpression. The operator precedence has already been applied, but there’s a caveat that additive expressions represent either addition or subtraction, whereas multiplicative ones represent either multiplication or division. We’ll ignore this distinction for now, as a proper solution for all of these is even more complicated than what you’re about to see.
Given that an expression such as
a+b+c is really represented as
(a+b)+c, we have good reason to implement a flattening algorithm that turns a binary tree into a flat list:
We can now think about checking the applicability of our context action. The analysis is deep, but it begins with finding the ‘root’ additive expression:
At this point, we need to do two things:
Flatten the top-level addition so that
a+b+c. In fact, we keep it as a simple list.
Do the same thing for the inner multiplications, so that
(a*b)*ccan be treated as just
The actual implementation uses our
Flatten<T>() function as well as a special
Flattening multiplications is a similar operation that gives us even better data: it returns a list-of-list-of-expressions, i.e. data that we can work with to be able to actually analyze the commonality of terms:
What we do now is build a frequency table of the terms — what they are, where they appear and how often. For example, for the expression
a*x*x + b*x + c we would get a table such as:
The implementation is not particularly difficult:
Having the terms in a histogram of sorts, we find out the one that’s used most:
Once we have the term, we find out how many times we’re going to extract if (for example, in
a*x*x*x + b*x*x it needs to be taken out twice), and we can finally return
true. Note that we also keep a record of affected terms, because even a term with a
zero in it may either be a multiplicand of the term we’ve extracted, or not.
Applying the Action
The first thing we output is the multiplier term and the opening brace to our subexpression:
Then, we set up a lambda that outputs the sum-of-products in a neat fashion:
And then, of course, we generate the new expression and replace the old one:
Seeing it in Action
Let’s try a simple example. Say we have this method that computes a polynomial:
Executing the factoring action once, we get
Firing it again within the braces we get
And this is what our action is ultimately about.
Our approach works, but suffers from a few methodological deficiencies, namely
We currently do not handle subtraction and division well
We can only factor out one variable
The algorithm is not recursive, so we have to invoke it several times to fully optimize the expression
In the next part of the series, we’ll take a look at fixing these issues. Meanwhile, check out the source code and stay tuned for more! ■
Subscribe to Blog updates
Thanks, we've got you!
Another Look into the Future with Rider’s Predictive Debugger
In the 2023.2 release cycle, we’ve introduced the Predictive Debugger in ReSharper, which gives you predictions about code paths and variables beyond the current execution pointer. We’ve written extensively about its advantages compared to alternative debugging strategies like thorough thinking, log…
Visualize Entity Framework Relationships and Additional Query Analysis in ReSharper 2023.3
A lot of teams are using Entity Framework or EF Core to work with their database. As an Object-Relational Mapper (ORM), it bridges objects in code to a relational database model, so that as a developer you don’t have to worry too much about the actual database. We all know: that’s not entirely tr…
Automatically Analyze ASP.NET Core Performance With Dynamic Program Analysis
Slow web pages may make your users or customers abandon your web application, even before they’ve had a proper look at it. You’ve likely also been frustrated working with a web application that is slow to load. The good news is that the latest versions of ReSharper and JetBrains Rider’s Dynamic P…
OSS Power-Ups: MassTransit – Webinar Recording
The recording of our webinar, OSS Power-Ups: MassTransit, with Chris Patterson, is available. This was the thirteenth episode of our OSS Power-Ups series, where we put a spotlight on open-source .NET projects. Subscribe to our community newsletter to receive notifications about future webinars.…