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);