Avoid allocation and bottom-type on Link
Change-Id: Ib23e596edf55285cc63e3a391da3712b2bcb1224
Reviewed-on: https://dart-review.googlesource.com/56761
Reviewed-by: Johnni Winther <johnniwinther@google.com>
diff --git a/pkg/compiler/lib/src/kernel/element_map_impl.dart b/pkg/compiler/lib/src/kernel/element_map_impl.dart
index a9eb519..e067c26 100644
--- a/pkg/compiler/lib/src/kernel/element_map_impl.dart
+++ b/pkg/compiler/lib/src/kernel/element_map_impl.dart
@@ -311,11 +311,12 @@
node.implementedTypes.forEach((ir.Supertype supertype) {
linkBuilder.addLast(processSupertype(supertype));
});
- Link<InterfaceType> interfaces = linkBuilder.toLink();
+ Link<InterfaceType> interfaces =
+ linkBuilder.toLink(const Link<InterfaceType>());
OrderedTypeSetBuilder setBuilder =
new _KernelOrderedTypeSetBuilder(this, cls);
data.orderedTypeSet = setBuilder.createOrderedTypeSet(
- data.supertype, interfaces.reverse());
+ data.supertype, interfaces.reverse(const Link<InterfaceType>()));
data.interfaces = new List<InterfaceType>.from(interfaces.toList());
}
}
diff --git a/pkg/compiler/lib/src/ordered_typeset.dart b/pkg/compiler/lib/src/ordered_typeset.dart
index 67c594a..0df07ef 100644
--- a/pkg/compiler/lib/src/ordered_typeset.dart
+++ b/pkg/compiler/lib/src/ordered_typeset.dart
@@ -283,7 +283,7 @@
}
}
return new OrderedTypeSet.internal(
- levels, levels.last, allSupertypes.toLink());
+ levels, levels.last, allSupertypes.toLink(const Link<InterfaceType>()));
}
String toString() {
@@ -291,13 +291,7 @@
for (int depth = 0; depth <= maxDepth; depth++) {
sb.write('$depth: ');
LinkEntry<InterfaceType> first = map[depth];
- if (first.isNotEmpty) {
- sb.write('${first.head}');
- while (first.tail.isNotEmpty) {
- sb.write(', ${first.tail.head}');
- first = first.tail;
- }
- }
+ first.printOn(sb, ", ");
sb.write('\n');
}
return sb.toString();
diff --git a/pkg/compiler/lib/src/util/util.dart b/pkg/compiler/lib/src/util/util.dart
index 113a2ed..c4452f6 100644
--- a/pkg/compiler/lib/src/util/util.dart
+++ b/pkg/compiler/lib/src/util/util.dart
@@ -210,7 +210,7 @@
if (isExternal) builder.addLast('external');
if (isCovariant) builder.addLast('covariant');
StringBuffer buffer = new StringBuffer();
- builder.toLink().printOn(buffer, ', ');
+ builder.toLink(const Link<String>()).printOn(buffer, ', ');
return buffer.toString();
}
diff --git a/pkg/front_end/lib/src/fasta/util/link.dart b/pkg/front_end/lib/src/fasta/util/link.dart
index 5236d28..4debdc7 100644
--- a/pkg/front_end/lib/src/fasta/util/link.dart
+++ b/pkg/front_end/lib/src/fasta/util/link.dart
@@ -61,7 +61,7 @@
bool get isEmpty => true;
bool get isNotEmpty => false;
- Link<T> reverse() => this;
+ Link<T> reverse(Link<T> tail) => this;
Link<T> reversePrependAll(Link<T> from) {
if (from.isEmpty) return this;
@@ -121,8 +121,6 @@
return true;
}
- Link copyWithout(e) => this;
-
//
// Unsupported Iterable<T> methods.
//
@@ -159,7 +157,7 @@
/// Prepends all elements added to the builder to [tail]. The resulting list
/// is returned and the builder is cleared.
- Link<T> toLink([Link<T> tail]);
+ Link<T> toLink(Link<T> tail);
/// Creates a new fixed length containing all added elements. The
/// resulting list is returned and the builder is cleared.
diff --git a/pkg/front_end/lib/src/fasta/util/link_implementation.dart b/pkg/front_end/lib/src/fasta/util/link_implementation.dart
index 5ff4693..9849ecb 100644
--- a/pkg/front_end/lib/src/fasta/util/link_implementation.dart
+++ b/pkg/front_end/lib/src/fasta/util/link_implementation.dart
@@ -88,10 +88,11 @@
return buffer.toString();
}
- Link<T> reverse() {
- Link<T> result = const Link<Null>();
+ @override
+ Link<T> reverse(Link<T> tail) {
+ Link<T> result = tail;
for (Link<T> link = this; link.isNotEmpty; link = link.tail) {
- result = new LinkEntry<T>(link.head, result);
+ result = result.prepend(link.head);
}
return result;
}
@@ -146,17 +147,6 @@
}
return length;
}
-
- Link copyWithout(e) {
- LinkBuilder copy = new LinkBuilder();
- Link link = this;
- for (; link.isNotEmpty; link = link.tail) {
- if (link.head != e) {
- copy.addLast(link.head);
- }
- }
- return copy.toLink(link);
- }
}
class LinkBuilderImplementation<T> implements LinkBuilder<T> {
@@ -166,13 +156,9 @@
LinkBuilderImplementation();
- Link<T> toLink([Link<T> tail]) {
- if (head == null) {
- // TODO(ahe): We should consider making the [tail] argument mandatory to
- // avoid creating unneeded objects.
- return tail ?? new Link<T>();
- }
- tail ??= const Link<Null>();
+ @override
+ Link<T> toLink(Link<T> tail) {
+ if (head == null) return tail;
lastLink.tail = tail;
Link<T> link = head;
lastLink = null;
diff --git a/pkg/front_end/test/fasta/link_test.dart b/pkg/front_end/test/fasta/link_test.dart
index a248fbd..5fe7b42 100644
--- a/pkg/front_end/test/fasta/link_test.dart
+++ b/pkg/front_end/test/fasta/link_test.dart
@@ -9,25 +9,36 @@
main() {
Link<String> strings = const Link<String>().prepend("B").prepend("A");
Expect.stringEquals("[ A, B ]", "${strings}");
- Expect.stringEquals("[ B, A ]", "${strings.reverse()}");
-
- strings = (new LinkBuilder<String>()..addLast("A")..addLast("B")).toLink();
-
- Expect.stringEquals("[ A, B ]", "${strings}");
- Expect.stringEquals("[ B, A ]", "${strings.reverse()}");
-
- strings = new LinkBuilder<String>().toLink().prepend("B").prepend("A");
-
- Expect.stringEquals("[ A, B ]", "${strings}");
- Expect.stringEquals("[ B, A ]", "${strings.reverse()}");
-
- strings = const Link<String>().reverse().prepend("B").prepend("A");
- Expect.stringEquals("[ A, B ]", "${strings}");
- Expect.stringEquals("[ B, A ]", "${strings.reverse()}");
+ Expect.stringEquals("[ B, A ]", "${strings.reverse(const Link<String>())}");
strings = (new LinkBuilder<String>()..addLast("A")..addLast("B"))
.toLink(const Link<String>());
Expect.stringEquals("[ A, B ]", "${strings}");
- Expect.stringEquals("[ B, A ]", "${strings.reverse()}");
+ Expect.stringEquals("[ B, A ]", "${strings.reverse(const Link<String>())}");
+
+ strings = new LinkBuilder<String>()
+ .toLink(const Link<String>())
+ .prepend("B")
+ .prepend("A");
+
+ Expect.stringEquals("[ A, B ]", "${strings}");
+ Expect.stringEquals("[ B, A ]", "${strings.reverse(const Link<String>())}");
+
+ strings = const Link<String>()
+ .reverse(const Link<String>())
+ .prepend("B")
+ .prepend("A");
+ Expect.stringEquals("[ A, B ]", "${strings}");
+ Expect.stringEquals("[ B, A ]", "${strings.reverse(const Link<String>())}");
+
+ strings = (new LinkBuilder<String>()..addLast("A")..addLast("B"))
+ .toLink(const Link<String>());
+
+ Expect.stringEquals("[ A, B ]", "${strings}");
+ Expect.stringEquals("[ B, A ]", "${strings.reverse(const Link<String>())}");
+
+ Link<int> ints =
+ const Link<int>().prepend(1).reverse(const Link<int>()).tail.prepend(1);
+ Expect.stringEquals("[ 1 ]", "${ints}");
}
diff --git a/tests/compiler/dart2js/link_test.dart b/tests/compiler/dart2js/link_test.dart
index 841c89f..eabf688 100644
--- a/tests/compiler/dart2js/link_test.dart
+++ b/tests/compiler/dart2js/link_test.dart
@@ -21,8 +21,6 @@
testFromList([0, 1, 2, 3, 4]);
testFromList([0, 1, 2, 3, 4, 5]);
testSkip();
-
- testCopyWithout();
}
testFromList(List list) {
@@ -63,14 +61,3 @@
Expect.isTrue(emptyLink.skip(0).isEmpty);
Expect.throws(() => emptyLink.skip(1), (e) => e is RangeError);
}
-
-testCopyWithout() {
- test(const Link().copyWithout(0), []);
-
- test(LinkFromList([0]).copyWithout(0), []);
- test(LinkFromList([0, 1]).copyWithout(0), [1]);
- test(LinkFromList([0, 1, 2]).copyWithout(0), [1, 2]);
- test(LinkFromList([0, 1, 2]).copyWithout(1), [0, 2]);
- test(LinkFromList([0, 1, 2]).copyWithout(2), [0, 1]);
- test(LinkFromList([0, 1, 2]).copyWithout(3), [0, 1, 2]);
-}
