Fix reassignment tracking performance issues - #2218

Much nicer!

Can this not be UNDEFINED_EXPRESSION?

There originally was an UNDEFINED_EXPRESSION but it turned out to be equivalent to UNKNOWN_EXPRESSION so I dropped it. With the new literal value tracking, re-introducing it would actually make sense. Since this is intended to be a bug-fix, I would postpone this for a PR explicitly addressing #2223.

Why is the prototype is treated as a special case in the following:

function x () {}
x.prototype = unknown;
x.thing = unknown;

x.prototype.a.b;
x.thing.a.b;

when surely any deep reassignment on a function or object should apply effects?

This is about the not-so-deep reassignments. More specifically, this very important situation that is often part of initialization code is not a side-effect:

function X(){};
X.prototype.myMethod = function() { console.log('hello'); }

while this is:

function X(){};
X.doesNotExist.myMethod = function() { console.log('hello'); }

Note that if X is included for whatever reason, all prototype assignments will be included as well. I think as long as we do not have proper flow tracking, a simple flag to take care of the prototype should be enough to handle situations such as this:

function X(){}
X.prototype.myMethod = function() {}

function Y(){}
Y.prototype = X.prototype; // this will mark the prototype of `Y` as reassigned
Y.prototype.myMethod = function() { console.log('hello'); } //  this mutation needs to be retained

const x = new X();
x.myMethod();

Thanks for the clear explanation that makes complete sense. To continue to help aid my understanding I added a further question about more generic path reassignment checking below, which seems like it is related here.

Does this mean that a function whose return expression is not explicitly the last statement will then be treated as having unknown return?

It seems here's an example case that is invalided by this change:

function x () {}
function y () {}
function f () {
  if (Math.random() > 0.5)
    return y;
  return x;
}
f()();

that would otherwise be tree-shaken.

It doesn't seem a huge loss to me though as it is really hypothetical.

I wonder though if we could not treat the whole function itself as having a "single type" (set from the first return), and only opt-out only if we find that a return value doesn't follow that type rule? That might stop the deep loops while still retaining the basic functionality here? Just a thought.

I guess you wouldn't know that x and y are the same without the full deep analysis though... so yeah. But perhaps having a type like f: PURE_FUNCTION or f: STRING_LITERAL would be useful?

It might be but it would also mean creating a whole new analysis step and another layer of types. I would rather wait for us to have some basic SSA going and use this as a base for much better analysis. Otherwise I would not take action unless there are some situations in important libraries for which this change would provide important gains.

As related to your first comment, rollup also does not yet detect unreachable code after return, break or throw statements. So this would be treated as "unknown" as well:

function x() {
  return false;
  const unimportant = false;
}

if (x()) console.log('not removed');

Sure, as I say these certainly seem suitable compromises to me.

Very nice to get rid of this.

This is a very impressive simplification. I can't say I've followed exactly, but I've tested the cases (as you've seen...) and it seems to definitely work well with what I've tried.

Basically the logic has moved to object expression. Which makes much more sense IMO as

• this goes much better with the notion of mutations of object references
• different types react different to mutations. E.g. a number will throw an error when properties are mutated (in strict mode) and itself not be mutated.

In theory hasCertainHit should have caught this case:

var x = {
	a () {
	},
	[unknown] () {
  }
};
x.a();

but it seems it wasn't applying to such a thing anyway so that removing this is fine.

That said, if we extend this type of logic to deal with progressive property sets within reduced control flows like:

var exports = {};

exports.a = function () {
}

exports.a();

then we may want to be detecting this again.

in theory hasCertainHit should have caught this case

Not 100% sure what you mean by "caught" as I do not see any side-effects to be detected. In general one thing this algorithm tries to capture is that when two properties with the same name appear in a literal, the second overwrites the first. Thus when we access .a and an unknown property appears after a, both need to be considered while any unknown properties before a can be safely ignored. When there are only unknown properties, calling a property is always a side-effect: REPL

That said, if we extend this type of logic to deal with progressive property sets

Yes, these cases should certainly still be considered. I think there should already be some tests for this. I have thought a little about how an SSA form could be extended to handle property reassignments. One concept that comes to my mind is considering object expressions to be like "scopes" where the properties are the "variables" that are duplicated:

// code
const x = {a: false};
const y = x;
x.a = true;
if (y.a) console.log('properly tracked');

// "SSA form"
// the object expression OE on the right side keeps track of its properties
const x1 = {a1: false};
const y1 = x1;

// we define version 2 of property a; the actual representation will probably be different
// note that this does NOT define a new x2 as x still refers to the same object reference OE
x1.a2 = true;

// as we know that y1 refers to OE, we know we need to use version 2 here
if (y1.a2) console.log('properly tracked');

// tree-shaken result
console.log('properly tracked');

You can already see that something like this needs very sophisticated analysis and for the first attempt at SSA I would not include property assignments but focus on actual variable reassignments.

In theory, unknown could be equal to 'a', which would then take precedence meaning it is not a certain hit even though there is an explicit 'a' defined. certainHit logic has precedence logic in it (loop in reverse order), yet doesn't quite go all the way in taking these concepts to their complete conclusions.

We lose the ability to go back on this here, but yes it's a super edge case. I'm mentioning because we are so close to handling the edge case, and now moving away from it. Projects that get massive traction need to be watertight - that is a big difference between a useful software project, and a massively supported and used project.

Very interesting object interpretation of SSA.

Somewhat unrelated, but I've long wanted to have the available analysis to form the following optimization:

var x = 'asdf';
var z = 'g';

export function y () {
  console.log(z);
}

export function p() {
  console.log(x);
}

If one module uses just y and another module uses just p, we don't need to keep the definitions of y and p in the same chunk necessarily and can actually split the above module into two separate modules:

var x = 'asdf';
export function p() {
  console.log(x);
}

var z = 'g';
export function y () {
  console.log(z);
}

This is a super complex long-term code splitting optimization I've wanted to implement for a while, and likely won't be able to implement for a while - but mentioning here as it would usefully piggy-back off similar analysis.

In theory, unknown could be equal to 'a', which would then take precedence meaning it is not a certain hit even though there is an explicit 'a' defined. certainHit logic has precedence logic in it (loop in reverse order), yet doesn't quite go all the way in taking these concepts to their complete conclusions

Actually as far as I know, it does go all the way 😜 Let me elaborate:
hasCertainHit means "we are certain there is a property of the given name". It does not mean we are certain which one it is! And in fact it is only used in the negative: When we are not certain there is a property of the given name, calling it must always be a side-effect.

If we are certain on the other hand, we check a whole array of properties for side-effects. Cf. this example: REPL

Here we do have a certain hit; the algorithm, however, does not only check the last method
with name "a" for side-effects but also all computed properties after it.

I have added this example + some variations as a function test to make sure this works even after the update and keeps working in the future.

Somewhat unrelated, but I've long wanted to have the available analysis to form the following optimization

Doing this in an arbitrary way might be difficult if the right hand side of the declaration itself depends on other variables. Something simpler that might be able to solve this problem in some situations and that I would consider quite doable would be inlining variables that are only used in one place (if they are used in more places, you would loose the reference identity). If done right i.e. in a way that "a variable can be inlined if it is only used once or only depends on other variables that can be inlined", then this would inline .e.g z into y and move both into the chunk where they are used

What I mean by being inconsistent is that the example is tree-shaken - https://rollupjs.org/repl?version=0.59.2&shareable=JTdCJTIybW9kdWxlcyUyMiUzQSU1QiU3QiUyMm5hbWUlMjIlM0ElMjJtYWluLmpzJTIyJTJDJTIyY29kZSUyMiUzQSUyMnZhciUyMHglMjAlM0QlMjAlN0IlNUNuJTVDdGElMjAoKSUyMCU3QiU1Q24lNUN0JTdEJTJDJTVDbiU1Q3QlNUJ1bmtub3duJTVEJTIwKCklMjAlN0IlNUNuJTIwJTIwJTdEJTVDbiU3RCUzQiU1Q254LmEoKSUzQiUyMiU3RCU1RCUyQyUyMm9wdGlvbnMlMjIlM0ElN0IlMjJmb3JtYXQlMjIlM0ElMjJjanMlMjIlMkMlMjJuYW1lJTIyJTNBJTIybXlCdW5kbGUlMjIlMkMlMjJnbG9iYWxzJTIyJTNBJTdCJTdEJTJDJTIyYW1kJTIyJTNBJTdCJTIyaWQlMjIlM0ElMjIlMjIlN0QlN0QlMkMlMjJleGFtcGxlJTIyJTNBbnVsbCU3RA== when in theory it shouldn't necessarily be.

Doing this in an arbitrary way might be difficult if the right hand side of the declaration itself depends on other variables. Something simpler that might be able to solve this problem in some situations and that I would consider quite doable would be inlining variables that are only used in one place (if they are used in more places, you would loose the reference identity). If done right i.e. in a way that "a variable can be inlined if it is only used once or only depends on other variables that can be inlined", then this would inline .e.g z into y and move both into the chunk where they are used

I feel quite strongly on this one that "gathering related branches" is an important part of the module splitting process.

when in theory it shouldn't necessarily be

In which theory? Add a side-effect and it will not be removed. Do you want the algorithm to be dumber in this place? Why?

In which theory? Add a side-effect and it will not be removed. Do you want the algorithm to be dumber in this place? Why?

Oh wow, you are right, and this works perfectly with precedence with the change. Sorry to doubt :)

I wasn't able to come up with any test that checks this behaviour. Any ideas? Would be nice to capture as much of this as possible through coverage.

You are very right. I added some tests around these lines and also discovered a bug while doing so...

To follow-on the comment about the prototype, ideally would it not be the job of reassignPath to track all reassignments to fully distinguish SSA-analyzable paths from non-SSA-analyzable paths?

Further, ideally reassignPath should be the same here for both objects and functions surely, apart from some core opt-outs like length which would throw on reassignment?

Yes and no. At the moment, all paths of a function except the prototype are treated as "unknown". So tracking reassignments here would just mean an "unknown" gets replaced by another "unknown" so there is no use doing more analysis.

I thought about adding more logic here but I think it only makes sense if there are at least a few more function properties that are known to rollup. Until then, a single flag for the prototype seemed like enough logic.

Thanks for the clear explanation that makes complete sense. To continue to help aid my understanding I added a further question about more generic path reassignment checking below, which seems like it is related here.

Sure, as I say these certainly seem suitable compromises to me.

In theory, unknown could be equal to 'a', which would then take precedence meaning it is not a certain hit even though there is an explicit 'a' defined. certainHit logic has precedence logic in it (loop in reverse order), yet doesn't quite go all the way in taking these concepts to their complete conclusions.

We lose the ability to go back on this here, but yes it's a super edge case. I'm mentioning because we are so close to handling the edge case, and now moving away from it. Projects that get massive traction need to be watertight - that is a big difference between a useful software project, and a massively supported and used project.

Very interesting object interpretation of SSA.

Somewhat unrelated, but I've long wanted to have the available analysis to form the following optimization:

var x = 'asdf';
var z = 'g';

export function y () {
  console.log(z);
}

export function p() {
  console.log(x);
}

If one module uses just y and another module uses just p, we don't need to keep the definitions of y and p in the same chunk necessarily and can actually split the above module into two separate modules:

var x = 'asdf';
export function p() {
  console.log(x);
}

var z = 'g';
export function y () {
  console.log(z);
}

This is a super complex long-term code splitting optimization I've wanted to implement for a while, and likely won't be able to implement for a while - but mentioning here as it would usefully piggy-back off similar analysis.