blob: 7e14ebbd01222fb6b63b023cb8588a92d3323bfc [file] [log] [blame]
// 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);