ReSharper SDK Adventures Part 7 — Factoring expressions

Dmitri Nesteruk

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!

Factoring

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.

Checking Availability

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 IAdditiveExpression and 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 becomes just a+b+c. In fact, we keep it as a simple list.

• Do the same thing for the inner multiplications, so that (a*b)*c can be treated as just a*b*c.

The actual implementation uses our Flatten<T>() function as well as a special FlattenMultiplications() function.

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.

Conclusion

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 a monthly digest curated from the .NET Tools blog:

Subscribe form

By submitting this form, I agree to the JetBrains Privacy Policy Notification icon

By submitting this form, I agree that JetBrains s.r.o. ("JetBrains") may use my name, email address, and location data to send me newsletters, including commercial communications, and to process my personal data for this purpose. I agree that JetBrains may process said data using third-party services for this purpose in accordance with the JetBrains Privacy Policy. I understand that I can revoke this consent at any time in my profile. In addition, an unsubscribe link is included in each email.

Submit

Thanks, we've got you!