OLD | NEW |
| (Empty) |
1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 /// A transformation to create a self-contained modular kernel without | |
6 /// unnecessary references to other libraries. | |
7 library fasta.kernel.kernel_outline_shaker; | |
8 | |
9 import 'package:kernel/ast.dart'; | |
10 import 'package:kernel/core_types.dart'; | |
11 | |
12 import '../errors.dart' show internalError; | |
13 | |
14 /// Removes from [program] unnecessary libraries, classes, and members. | |
15 /// | |
16 /// This applies a simple "tree-shaking" technique: the full body of libraries | |
17 /// whose URI match [isIncluded] is preserved, and so is the outline of the | |
18 /// members and classes which are indicated by [data] (which should | |
19 /// practically include all members and classes transitively visible from the | |
20 /// included libraries). | |
21 /// | |
22 /// The intent is that the resulting program has the entire code that is meant | |
23 /// to be included and the minimum required to prevent dangling references and | |
24 /// allow modular program transformations. | |
25 /// | |
26 /// Note that the resulting program may include libraries not in [isIncluded], | |
27 /// but those will be marked as external. There should be no method bodies for | |
28 /// any members of those libraries. | |
29 void trimProgram(Program program, RetainedData data, bool isIncluded(Uri uri)) { | |
30 new KernelOutlineShaker(data, isIncluded).transform(program); | |
31 } | |
32 | |
33 /// Informs about which libraries, classes, and members should be retained by | |
34 /// the [KernelOutlineShaker] when tree-shaking. | |
35 abstract class RetainedData { | |
36 /// Whether a library should be preserved and mark as external. | |
37 bool isLibraryUsed(Library library); | |
38 | |
39 /// Whether a class should be preserved. If a class is preserved, its | |
40 /// supertypes will be preserved too, but some of it members may not be | |
41 /// included. | |
42 bool isClassUsed(Class cls); | |
43 | |
44 /// Whether a member should be preserved. If so, its enclosing class/library | |
45 /// will be preserved too. | |
46 bool isMemberUsed(Member member); | |
47 } | |
48 | |
49 /// A builder of [RetainedData] that recursively marks transitive dependencies. | |
50 /// | |
51 /// This builder contains APIs to mark the roots that are needed (e.g. | |
52 /// [markClass] and [markMember]). Note this builder does not determine what | |
53 /// roots to keep, that is done either directly by fasta while it is parsing, or | |
54 /// by using a visitor like the [RootsMarker] below. | |
55 class RetainedDataBuilder extends RetainedData { | |
56 /// Libraries that contained code that is transitively reachable from the | |
57 /// included libraries. | |
58 final Set<Library> libraries = new Set<Library>(); | |
59 | |
60 /// Classes that are transitively reachable from the included libraries. | |
61 final Set<Class> classes = new Set<Class>(); | |
62 | |
63 /// Members that are transitively reachable from the included libraries. | |
64 final Set<Member> members = new Set<Member>(); | |
65 | |
66 TypeMarker typeMarker; | |
67 | |
68 @override | |
69 bool isLibraryUsed(Library library) => libraries.contains(library); | |
70 | |
71 @override | |
72 bool isClassUsed(Class cls) => classes.contains(cls); | |
73 | |
74 @override | |
75 bool isMemberUsed(Member m) => members.contains(m); | |
76 | |
77 RetainedDataBuilder() { | |
78 typeMarker = new TypeMarker(this); | |
79 } | |
80 | |
81 /// Mark a library as used. | |
82 void markLibrary(Library lib) { | |
83 libraries.add(lib); | |
84 } | |
85 | |
86 /// Mark a class and it's supertypes as used. | |
87 void markClass(Class cls) { | |
88 if (cls == null || !classes.add(cls)) return; | |
89 markLibrary(cls.parent); | |
90 // TODO(sigmund): retain annotations? | |
91 // visitList(cls.annotations, this); | |
92 markSupertype(cls.supertype); | |
93 markSupertype(cls.mixedInType); | |
94 cls.implementedTypes.forEach(markSupertype); | |
95 cls.typeParameters.forEach((t) => t.bound.accept(typeMarker)); | |
96 } | |
97 | |
98 /// Mark the class and type arguments of [node]. | |
99 void markSupertype(Supertype node) { | |
100 if (node == null) return; | |
101 markClass(node.classNode); | |
102 node.typeArguments.forEach((t) => t.accept(typeMarker)); | |
103 } | |
104 | |
105 /// Mark a member and types mentioned on its interface. | |
106 void markMember(Member m) { | |
107 if (m == null || !members.add(m)) return; | |
108 markMemberInterface(m); | |
109 var parent = m.parent; | |
110 if (parent is Library) { | |
111 markLibrary(parent); | |
112 } else if (parent is Class) { | |
113 markClass(parent); | |
114 } | |
115 } | |
116 | |
117 void markMemberInterface(Member node) { | |
118 if (node is Field) { | |
119 node.type.accept(typeMarker); | |
120 } else if (node is Procedure) { | |
121 var function = node.function; | |
122 function.typeParameters.forEach((p) => p.bound.accept(typeMarker)); | |
123 function.positionalParameters.forEach((p) => p.type.accept(typeMarker)); | |
124 function.namedParameters.forEach((p) => p.type.accept(typeMarker)); | |
125 function.returnType.accept(typeMarker); | |
126 } | |
127 } | |
128 } | |
129 | |
130 /// A helper visitor used to mark transitive types by the [RetainedDataBuilder]. | |
131 class TypeMarker extends DartTypeVisitor { | |
132 RetainedDataBuilder data; | |
133 | |
134 TypeMarker(this.data); | |
135 | |
136 visitInterfaceType(InterfaceType node) { | |
137 data.markClass(node.classNode); | |
138 node.typeArguments.forEach((t) => t.accept(this)); | |
139 } | |
140 | |
141 visitFunctionType(FunctionType node) { | |
142 node.typeParameters.forEach((t) => t.bound.accept(this)); | |
143 node.positionalParameters.forEach((t) => t.accept(this)); | |
144 node.namedParameters.forEach((t) => t.type.accept(this)); | |
145 node.returnType.accept(this); | |
146 } | |
147 | |
148 visitTypeParameterType(TypeParameterType node) { | |
149 // Note: node.parameter is marked by marking the enclosing element. | |
150 } | |
151 | |
152 visitTypedefType(TypedefType node) { | |
153 node.typeArguments.forEach((t) => t.accept(this)); | |
154 } | |
155 } | |
156 | |
157 /// Determines the root APIs that need to be retained before running the | |
158 /// tree-shaker. | |
159 /// | |
160 /// This is implemented using a visitor that walks through the sources that are | |
161 /// intended to be part of the kernel output. | |
162 // TODO(sigmund): delete. We should collect this information while | |
163 // building kernel without having to run a visitor afterwards. | |
164 class RootsMarker extends RecursiveVisitor { | |
165 final RetainedDataBuilder data; | |
166 RootsMarker(this.data); | |
167 | |
168 void run(Program program, bool isIncluded(Uri uri)) { | |
169 markRequired(program); | |
170 data.markMember(program.mainMethod); | |
171 for (var library in program.libraries) { | |
172 if (isIncluded(library.importUri)) { | |
173 library.accept(this); | |
174 } | |
175 } | |
176 } | |
177 | |
178 /// Marks classes and members that are assumed to exist by fasta or by | |
179 /// transformers. | |
180 // TODO(sigmund): consider being more fine-grained and only marking what is | |
181 // seen and used. | |
182 void markRequired(Program program) { | |
183 var coreTypes = new CoreTypes(program); | |
184 coreTypes.objectClass.members.forEach(data.markMember); | |
185 | |
186 // These are assumed to be available by fasta: | |
187 data.markClass(coreTypes.objectClass); | |
188 data.markClass(coreTypes.nullClass); | |
189 data.markClass(coreTypes.boolClass); | |
190 data.markClass(coreTypes.intClass); | |
191 data.markClass(coreTypes.numClass); | |
192 data.markClass(coreTypes.doubleClass); | |
193 data.markClass(coreTypes.stringClass); | |
194 data.markClass(coreTypes.listClass); | |
195 data.markClass(coreTypes.mapClass); | |
196 data.markClass(coreTypes.iterableClass); | |
197 data.markClass(coreTypes.iteratorClass); | |
198 data.markClass(coreTypes.futureClass); | |
199 data.markClass(coreTypes.streamClass); | |
200 data.markClass(coreTypes.symbolClass); | |
201 data.markClass(coreTypes.internalSymbolClass); | |
202 data.markClass(coreTypes.typeClass); | |
203 data.markClass(coreTypes.functionClass); | |
204 data.markClass(coreTypes.invocationClass); | |
205 data.markMember(coreTypes.getMember("dart:_internal", "ExternalName", "")); | |
206 | |
207 // These are needed by the continuation (async/await) transformer: | |
208 data.markClass(coreTypes.getClass('dart:core', 'Iterator')); | |
209 data.markClass(coreTypes.getClass('dart:async', 'Future')); | |
210 data.markClass(coreTypes.getClass('dart:async', 'FutureOr')); | |
211 data.markClass(coreTypes.getClass('dart:async', 'Completer')); | |
212 data.markMember(coreTypes.getMember('dart:async', 'Completer', 'sync')); | |
213 data.markMember(coreTypes.getMember('dart:core', '_SyncIterable', '')); | |
214 data.markMember(coreTypes.getMember('dart:async', '_StreamIterator', '')); | |
215 data.markMember(coreTypes.getMember('dart:async', 'Future', 'microtask')); | |
216 data.markMember( | |
217 coreTypes.getMember('dart:async', '_AsyncStarStreamController', '')); | |
218 data.markMember(coreTypes.getTopLevelMember('dart:core', 'print')); | |
219 data.markMember( | |
220 coreTypes.getTopLevelMember('dart:async', '_asyncThenWrapperHelper')); | |
221 data.markMember( | |
222 coreTypes.getTopLevelMember('dart:async', '_asyncErrorWrapperHelper')); | |
223 data.markMember(coreTypes.getTopLevelMember('dart:async', '_awaitHelper')); | |
224 | |
225 // These are needed by the mixin transformer | |
226 data.markMember(coreTypes.getMember('dart:core', '_InvocationMirror', '')); | |
227 data.markMember(coreTypes.getMember('dart:core', 'List', 'from')); | |
228 } | |
229 | |
230 visitConstructor(Constructor node) { | |
231 if (!node.initializers.any((i) => i is SuperInitializer)) { | |
232 // super() is currently implicit. | |
233 for (var ctor in node.enclosingClass.supertype.classNode.constructors) { | |
234 if (ctor.name.name == '') data.markMember(ctor); | |
235 } | |
236 } | |
237 node.visitChildren(this); | |
238 } | |
239 | |
240 @override | |
241 visitSuperInitializer(SuperInitializer node) { | |
242 data.markMember(node.target); | |
243 node.visitChildren(this); | |
244 } | |
245 | |
246 @override | |
247 visitRedirectingInitializer(RedirectingInitializer node) { | |
248 data.markMember(node.target); | |
249 node.visitChildren(this); | |
250 } | |
251 | |
252 @override | |
253 visitConstructorInvocation(ConstructorInvocation node) { | |
254 data.markMember(node.target); | |
255 node.visitChildren(this); | |
256 } | |
257 | |
258 @override | |
259 visitStaticInvocation(StaticInvocation node) { | |
260 data.markMember(node.target); | |
261 node.visitChildren(this); | |
262 } | |
263 | |
264 @override | |
265 visitDirectMethodInvocation(DirectMethodInvocation node) { | |
266 if (node.receiver is! ThisExpression) { | |
267 return internalError('Direct calls are only supported on "this"'); | |
268 } | |
269 data.markMember(node.target); | |
270 node.visitChildren(this); | |
271 } | |
272 | |
273 @override | |
274 visitMethodInvocation(MethodInvocation node) { | |
275 data.markMember(node.interfaceTarget); | |
276 node.visitChildren(this); | |
277 } | |
278 | |
279 @override | |
280 visitStaticGet(StaticGet node) { | |
281 data.markMember(node.target); | |
282 node.visitChildren(this); | |
283 } | |
284 | |
285 @override | |
286 visitStaticSet(StaticSet node) { | |
287 data.markMember(node.target); | |
288 node.visitChildren(this); | |
289 } | |
290 | |
291 @override | |
292 visitDirectPropertyGet(DirectPropertyGet node) { | |
293 data.markMember(node.target); | |
294 node.visitChildren(this); | |
295 } | |
296 | |
297 @override | |
298 visitDirectPropertySet(DirectPropertySet node) { | |
299 data.markMember(node.target); | |
300 node.visitChildren(this); | |
301 } | |
302 | |
303 @override | |
304 visitSuperPropertyGet(SuperPropertyGet node) { | |
305 data.markMember(node.interfaceTarget); | |
306 node.visitChildren(this); | |
307 } | |
308 | |
309 @override | |
310 visitSuperPropertySet(SuperPropertySet node) { | |
311 data.markMember(node.interfaceTarget); | |
312 node.visitChildren(this); | |
313 } | |
314 | |
315 @override | |
316 visitPropertyGet(PropertyGet node) { | |
317 data.markMember(node.interfaceTarget); | |
318 node.visitChildren(this); | |
319 } | |
320 | |
321 @override | |
322 visitPropertySet(PropertySet node) { | |
323 data.markMember(node.interfaceTarget); | |
324 node.visitChildren(this); | |
325 } | |
326 | |
327 @override | |
328 visitInterfaceType(InterfaceType node) { | |
329 data.markClass(node.classNode); | |
330 node.visitChildren(this); | |
331 } | |
332 | |
333 @override | |
334 visitSupertype(Supertype node) { | |
335 data.markClass(node.classNode); | |
336 node.visitChildren(this); | |
337 } | |
338 | |
339 @override | |
340 visitTypedefReference(Typedef node) { | |
341 return internalError('not implemented'); | |
342 } | |
343 } | |
344 | |
345 /// Transformer that trims everything in the excluded libraries that is not | |
346 /// marked as preserved by the given [RetainedData]. For every member in these | |
347 /// excluded libraries, this transformer also removes function bodies and | |
348 /// initializers. | |
349 class KernelOutlineShaker extends Transformer { | |
350 final RetainedData data; | |
351 final Filter isIncluded; | |
352 | |
353 KernelOutlineShaker(this.data, this.isIncluded); | |
354 | |
355 void transform(Program program) { | |
356 var toRemove = new Set<Library>(); | |
357 for (var library in program.libraries) { | |
358 if (!isIncluded(library.importUri)) { | |
359 if (!data.isLibraryUsed(library)) { | |
360 toRemove.add(library); | |
361 } else { | |
362 library.isExternal = true; | |
363 library.transformChildren(this); | |
364 } | |
365 } | |
366 } | |
367 program.libraries.removeWhere(toRemove.contains); | |
368 } | |
369 | |
370 Class visitClass(Class node) { | |
371 if (!data.isClassUsed(node)) { | |
372 node.canonicalName?.unbind(); | |
373 return null; // Remove the class. | |
374 } else { | |
375 node.transformChildren(this); | |
376 return node; | |
377 } | |
378 } | |
379 | |
380 Member defaultMember(Member node) { | |
381 if (!data.isMemberUsed(node)) { | |
382 node.canonicalName?.unbind(); | |
383 return null; | |
384 } else { | |
385 if (node is Procedure) { | |
386 node.function.body = null; | |
387 } else if (node is Field) { | |
388 node.initializer = null; | |
389 } else if (node is Constructor) { | |
390 node.initializers.clear(); | |
391 node.function.body = null; | |
392 } | |
393 return node; | |
394 } | |
395 } | |
396 | |
397 /// Types appear to be encoded directly, so we have no need to preserve | |
398 /// typedefs. | |
399 // TODO(sigmund): revisit if this is not the case, the `inputError` in | |
400 // [RootsMarker] is meant to detect this. | |
401 Typedef visitTypedef(Typedef node) => null; | |
402 | |
403 TreeNode defaultTreeNode(TreeNode node) => node; | |
404 } | |
405 | |
406 typedef bool Filter(Uri uri); | |
OLD | NEW |