Improve find all references (for tree shaking)

[alexdima]

TypeScript Version: 2.9.2

Search Terms: references, rename, incorrect, duck-typing

Code

class A {
    dispose(): void {
        console.log(`disposed!`);
    }
}

interface IDisposable {
    dispose(): void;
}

var a: IDisposable;
a = new A();
a.dispose();

Expected behavior:
Finding all references of dispose on the last line should return the method called dispose in class A, even if there is no explicit implements IDisposable heritage clause.

Actual behavior:
Finding all references of dispose returns only two results.

Related Issues:
Renaming the dispose on the last line (via F2 in VSCode) suffers from the same issue and ends up introducing a compilation error.

---

If you believe the user-facing find all references should not be changed, can we at least have a good working find all references in the typescriptServices.ts? I'm asking because I wrote a tree shaker for the Monaco Editor (the editor is extracted from VSCode's sources and a lot of utility methods or members of classes are not used -- running the tree shaker results in a 14% size reduction of the minified editor). The tree shaker is here and it is a shame that I need to maintain a file with fake references partly because find all references does not return all the references.

Since I have your attention, I wanted to bring up that fixing the above issue allows one to pretty-easily build a tree shaker. It would be great if you would consider adding tree shaking inside the compiler, it doesn't seem that difficult to implement and perhaps other projects besides the Monaco Editor would benefit from it.

[ghost]

It seems like you would need to do an analysis of every pair of types to determine what's assignable to what. We wouldn't be able to do that performantly in an editor, but we could expose that ability in the API -- see #9879.
By the way, if you are doing an anlysis on the entire program, doing find-all-references at every location is probably not what you want -- it would probably be faster to just walk over the tree, get the symbol at every location, and add an entry to the result.

[mhegazy]

The fact that an interface IDisposable has a property called dispose that is structurally equivalent to a another property on another type A is not sufficient to deem it a reference. you also need to know if an instance of type A has ever been assigned to or passed as an argument to call that expects a type IDisposable.

That analysis is not cheep. to do this correctly, the compiler first needs to find all types that have 1. a property with the same name, and 2. are structurally compatible to the one we are searching for, then 3. find all references of that type, and see if ever an instance of the type being searched for was ever compared/assigned/extended to the other type.

I am not saying this is not doable, i am saying find-all-refs is not the place for it.

If you are interested in optimization, property renames, and/or tree shaking, i suggests you talk to @rbuckton and @DanielRosenwasser offline, they would have more info for you.

The find all refs suggestion is already tracked by #6388.

[alexdima]

@andy-ms

It seems like you would need to do an analysis of every pair of types to determine what's assignable to what.

I'm not exactly asking for that. Note that I included the statement a = new A();. I am not asking for find all references to find the A.dispose() method if that assignment statement is missing.

I am a compiler noob, but IMHO as part of type checking you must be checking if the type A is assignable to IDisposable using the rules of duck-typing. When this happens, you could mark the type A and add an "implicit heritage clause" to IDisposable.

In other words, once the type checker sees a = new A();, where a is IDisposable, it could treat the entire code-base as if the heritage clause were explicit:

class A implements IDisposable { // note the explicit heritage clause
    dispose(): void {
        console.log(`disposed!`);
    }
}

interface IDisposable {
    dispose(): void;
}

var a: IDisposable;
a = new A();
a.dispose();

---

By the way, if you are doing an anlysis on the entire program, doing find-all-references at every location is probably not what you want -- it would probably be faster to just walk over the tree, get the symbol at every location, and add an entry to the result.

I'm happy you bring it up. The tree shaker I wrote has two variants: shaking only of top level class declarations, interfaces, functions, enums or exported variables, or also shaking of unused members.

In the simpler case of shaking only top level class declarations, the algorithm uses a simple queue of nodes. Each visited node is marked, and its children are also walked. For each child node that points to a symbol, the declaration of that symbol is added to the queue, etc. It is surprisingly simple and works well, and does not need find all references. I had to borrow -- :) -- some of the go to definition code from you, as the symbol sometimes points to the local import (which I need to mark and then jump to the actual definition), or the symbol is weird in the case of literals with properties with the same name (e.g. { foo: foo } vs { foo }, etc).

In the more complex case of shaking also members, the algorithm uses two queues, one queue is black and another queue is gray. The problem here like in the above code-base is that no symbol will end up pointing to A.dispose, as the invocation in the statement a.dispose will have a symbol which points to IDisposable.dispose. The trick here is whenever hitting a symbol which is an interface or class member, to mark the name node (and the heritage clause) of the interface/class as black and the member as black, and then run find all references on the member. All the references are added to a gray queue. The reason is: simply because a class implements IDisposable does not mean its dispose method should survive tree-shaking, as the class could never be instantiated. When the black queue becomes empty, gray nodes that appear in classes/interfaces which have a black node (most likely the name) are moved over to the black queue.

In other words, it covers the case:

interface IDisposable { dispose(): void }
class A implements IDisposable { dispose:() {} }
class B implements IDisposable { dispose:() {} }
var a: IDisposable = new A();
a.dispose();

where the class B should be removed when tree-shaking, even if B.dispose is found while searching for references of IDisposable.dispose via a.dispose().

Here is the current implementation which pretty much works (I use it to ship the Monaco Editor) -- https://github.com/Microsoft/vscode/blob/master/build/lib/treeshaking.ts

The reason I was reaching out is because I found it so surprisingly easy to build a top level declaration tree shaker and it would be also pretty easy to tree shake members if find all references could find cases like this. One possible solution is for type-checking to record via "implicit heritage clauses" duck-typing assignments.

---

@mhegazy

👍 to close this bug in favor of #6388 .

I am a compiler noob, so take my suggestions lightly :). But from an implementation point of view the fact that one type T1 was checked and found "duck-typing compatible" with another type T2 could be something the checker records in the "primary type-checking inner loop". Perhaps you already do this as an optimisation today? i.e. if the type checker needs to check the same situation again, will you spend CPU cycles to do so or is this cached. e.g.

class A { dispose() { } }
interface IDisposable { dispose(): void; }

var a: IDisposable;
var b: IDisposable;
a = new A();
b = new A();

When checking a = new A() it seems reasonable to mark somehow the class A as being "duck-typing" assignable to IDisposable. When checking b = new A(), this cache can be used and the previous result can be trusted. Finally, this cache is something that could be used by find all references.

---

I just wanted to bring up how fixing this issue can IMHO give you a pretty easy implementation of tree shaking... I've also only tried this tree-shaking code on VSCode's codebase so perhaps the algorithm has flaws and is not correct over other cases.

[typescript-bot]

Automatically closing this issue for housekeeping purposes. The issue labels indicate that it is unactionable at the moment or has already been addressed.

[alexdima]

@andy-ms @mhegazy Did you get any chance to read through my previous comment. Specifically this part:

[...] from an implementation point of view the fact that one type T1 was checked and found "duck-typing compatible" with another type T2 could be something the checker records in the "primary type-checking inner loop". Perhaps you already do this as an optimisation today? i.e. if the type checker needs to check the same situation again, will you spend CPU cycles to do so or is this cached [...]

Is there a straight-forward way in the type checker to remember when a certain type is checked for "duck-typing compatibility" with another type? I could then attempt to access this information in the tree shaker.

Thanks!

[mhegazy]

I do not think this can be exposed as a feature of the language service. it requires a full path over the program to "link" properties of similar names. Let's sync offline. VSCode and TS have a sync meeting on Thursdays at 11.

//cc @kieferrm