Test for avoiding exponential tree traversal of DAG constants
Change-Id: Ib62db28a7a6d21fe859f32f092e1096c0c166752
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/109160
Commit-Queue: Stephen Adams <sra@google.com>
Reviewed-by: Lasse R.H. Nielsen <lrn@google.com>
diff --git a/tests/language/const/constant_dag_test.dart b/tests/language/const/constant_dag_test.dart
new file mode 100644
index 0000000..7e14ebb
--- /dev/null
+++ b/tests/language/const/constant_dag_test.dart
@@ -0,0 +1,67 @@
+// Copyright (c) 2021, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "package:expect/expect.dart";
+
+// Test the efficient processing of constants that are DAGs.
+//
+// This test requires processing a constant that is a DAG of N nodes (N=40). If
+// the DAG is traversed as a tree, it will require exponential node visits and
+// take time O(2^N) i.e. 2^40, and the test will time out.
+
+main() {
+ Expect.equals(40, n40.lengthA);
+ Expect.equals(40, n40.lengthB);
+}
+
+class Node {
+ final Node? a;
+ final Node? b;
+ const Node(this.a, this.b);
+
+ int get lengthA => a == null ? 0 : 1 + a!.lengthA;
+ int get lengthB => a == null ? 0 : 1 + b!.lengthB;
+}
+
+const n0 = Node(null, null);
+const n1 = Node(n0, n0);
+const n2 = Node(n1, n1);
+const n3 = Node(n2, n2);
+const n4 = Node(n3, n3);
+const n5 = Node(n4, n4);
+const n6 = Node(n5, n5);
+const n7 = Node(n6, n6);
+const n8 = Node(n7, n7);
+const n9 = Node(n8, n8);
+const n10 = Node(n9, n9);
+const n11 = Node(n10, n10);
+const n12 = Node(n11, n11);
+const n13 = Node(n12, n12);
+const n14 = Node(n13, n13);
+const n15 = Node(n14, n14);
+const n16 = Node(n15, n15);
+const n17 = Node(n16, n16);
+const n18 = Node(n17, n17);
+const n19 = Node(n18, n18);
+const n20 = Node(n19, n19);
+const n21 = Node(n20, n20);
+const n22 = Node(n21, n21);
+const n23 = Node(n22, n22);
+const n24 = Node(n23, n23);
+const n25 = Node(n24, n24);
+const n26 = Node(n25, n25);
+const n27 = Node(n26, n26);
+const n28 = Node(n27, n27);
+const n29 = Node(n28, n28);
+const n30 = Node(n29, n29);
+const n31 = Node(n30, n30);
+const n32 = Node(n31, n31);
+const n33 = Node(n32, n32);
+const n34 = Node(n33, n33);
+const n35 = Node(n34, n34);
+const n36 = Node(n35, n35);
+const n37 = Node(n36, n36);
+const n38 = Node(n37, n37);
+const n39 = Node(n38, n38);
+const n40 = Node(n39, n39);
diff --git a/tests/language_2/const/constant_dag_test.dart b/tests/language_2/const/constant_dag_test.dart
new file mode 100644
index 0000000..3be6889
--- /dev/null
+++ b/tests/language_2/const/constant_dag_test.dart
@@ -0,0 +1,67 @@
+// Copyright (c) 2021, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "package:expect/expect.dart";
+
+// Test the efficient processing of constants that are DAGs.
+//
+// This test requires processing a constant that is a DAG of N nodes (N=40). If
+// the DAG is traversed as a tree, it will require exponential node visits and
+// take time O(2^N) i.e. 2^40, and the test will time out.
+
+main() {
+ Expect.equals(40, n40.lengthA);
+ Expect.equals(40, n40.lengthB);
+}
+
+class Node {
+ final Node a;
+ final Node b;
+ const Node(this.a, this.b);
+
+ int get lengthA => a == null ? 0 : 1 + a.lengthA;
+ int get lengthB => b == null ? 0 : 1 + b.lengthB;
+}
+
+const n0 = Node(null, null);
+const n1 = Node(n0, n0);
+const n2 = Node(n1, n1);
+const n3 = Node(n2, n2);
+const n4 = Node(n3, n3);
+const n5 = Node(n4, n4);
+const n6 = Node(n5, n5);
+const n7 = Node(n6, n6);
+const n8 = Node(n7, n7);
+const n9 = Node(n8, n8);
+const n10 = Node(n9, n9);
+const n11 = Node(n10, n10);
+const n12 = Node(n11, n11);
+const n13 = Node(n12, n12);
+const n14 = Node(n13, n13);
+const n15 = Node(n14, n14);
+const n16 = Node(n15, n15);
+const n17 = Node(n16, n16);
+const n18 = Node(n17, n17);
+const n19 = Node(n18, n18);
+const n20 = Node(n19, n19);
+const n21 = Node(n20, n20);
+const n22 = Node(n21, n21);
+const n23 = Node(n22, n22);
+const n24 = Node(n23, n23);
+const n25 = Node(n24, n24);
+const n26 = Node(n25, n25);
+const n27 = Node(n26, n26);
+const n28 = Node(n27, n27);
+const n29 = Node(n28, n28);
+const n30 = Node(n29, n29);
+const n31 = Node(n30, n30);
+const n32 = Node(n31, n31);
+const n33 = Node(n32, n32);
+const n34 = Node(n33, n33);
+const n35 = Node(n34, n34);
+const n36 = Node(n35, n35);
+const n37 = Node(n36, n36);
+const n38 = Node(n37, n37);
+const n39 = Node(n38, n38);
+const n40 = Node(n39, n39);
