1 /* 2 * Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. 3 * Use of this file is governed by the BSD 3-clause license that 4 * can be found in the LICENSE.txt file in the project root. 5 */ 6 7 package org.antlr.v4.test.tool; 8 9 import org.antlr.v4.runtime.atn.ArrayPredictionContext; 10 import org.antlr.v4.runtime.atn.PredictionContext; 11 import org.antlr.v4.runtime.atn.PredictionContextCache; 12 import org.antlr.v4.runtime.atn.SingletonPredictionContext; 13 import org.junit.Before; 14 import org.junit.Ignore; 15 import org.junit.Test; 16 17 import java.util.ArrayDeque; 18 import java.util.Deque; 19 import java.util.IdentityHashMap; 20 import java.util.Map; 21 22 import static org.junit.Assert.assertEquals; 23 24 public class TestGraphNodes { 25 PredictionContextCache contextCache; 26 27 @Before setUp()28 public void setUp() { 29 PredictionContext.globalNodeCount = 1; 30 contextCache = new PredictionContextCache(); 31 } 32 rootIsWildcard()33 public boolean rootIsWildcard() { return true; } fullCtx()34 public boolean fullCtx() { return false; } 35 test_$_$()36 @Test public void test_$_$() { 37 PredictionContext r = PredictionContext.merge(PredictionContext.EMPTY, 38 PredictionContext.EMPTY, 39 rootIsWildcard(), null); 40 // System.out.println(toDOTString(r, rootIsWildcard())); 41 String expecting = 42 "digraph G {\n" + 43 "rankdir=LR;\n" + 44 " s0[label=\"*\"];\n" + 45 "}\n"; 46 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 47 } 48 test_$_$_fullctx()49 @Test public void test_$_$_fullctx() { 50 PredictionContext r = PredictionContext.merge(PredictionContext.EMPTY, 51 PredictionContext.EMPTY, 52 fullCtx(), null); 53 // System.out.println(toDOTString(r, fullCtx())); 54 String expecting = 55 "digraph G {\n" + 56 "rankdir=LR;\n" + 57 " s0[label=\"$\"];\n" + 58 "}\n"; 59 assertEquals(expecting, toDOTString(r, fullCtx())); 60 } 61 test_x_$()62 @Test public void test_x_$() { 63 PredictionContext r = PredictionContext.merge(x(), PredictionContext.EMPTY, rootIsWildcard(), null); 64 // System.out.println(toDOTString(r, rootIsWildcard())); 65 String expecting = 66 "digraph G {\n" + 67 "rankdir=LR;\n" + 68 " s0[label=\"*\"];\n" + 69 "}\n"; 70 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 71 } 72 test_x_$_fullctx()73 @Test public void test_x_$_fullctx() { 74 PredictionContext r = PredictionContext.merge(x(), PredictionContext.EMPTY, fullCtx(), null); 75 // System.out.println(toDOTString(r, fullCtx())); 76 String expecting = 77 "digraph G {\n" + 78 "rankdir=LR;\n" + 79 " s0[shape=record, label=\"<p0>|<p1>$\"];\n" + 80 " s1[label=\"$\"];\n" + 81 " s0:p0->s1[label=\"9\"];\n" + 82 "}\n"; 83 assertEquals(expecting, toDOTString(r, fullCtx())); 84 } 85 test_$_x()86 @Test public void test_$_x() { 87 PredictionContext r = PredictionContext.merge(PredictionContext.EMPTY, x(), rootIsWildcard(), null); 88 // System.out.println(toDOTString(r, rootIsWildcard())); 89 String expecting = 90 "digraph G {\n" + 91 "rankdir=LR;\n" + 92 " s0[label=\"*\"];\n" + 93 "}\n"; 94 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 95 } 96 test_$_x_fullctx()97 @Test public void test_$_x_fullctx() { 98 PredictionContext r = PredictionContext.merge(PredictionContext.EMPTY, x(), fullCtx(), null); 99 // System.out.println(toDOTString(r, fullCtx())); 100 String expecting = 101 "digraph G {\n" + 102 "rankdir=LR;\n" + 103 " s0[shape=record, label=\"<p0>|<p1>$\"];\n" + 104 " s1[label=\"$\"];\n" + 105 " s0:p0->s1[label=\"9\"];\n" + 106 "}\n"; 107 assertEquals(expecting, toDOTString(r, fullCtx())); 108 } 109 test_a_a()110 @Test public void test_a_a() { 111 PredictionContext r = PredictionContext.merge(a(), a(), rootIsWildcard(), null); 112 // System.out.println(toDOTString(r, rootIsWildcard())); 113 String expecting = 114 "digraph G {\n" + 115 "rankdir=LR;\n" + 116 " s0[label=\"0\"];\n" + 117 " s1[label=\"*\"];\n" + 118 " s0->s1[label=\"1\"];\n" + 119 "}\n"; 120 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 121 } 122 test_a$_ax()123 @Test public void test_a$_ax() { 124 PredictionContext a1 = a(); 125 PredictionContext x = x(); 126 PredictionContext a2 = createSingleton(x, 1); 127 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 128 // System.out.println(toDOTString(r, rootIsWildcard())); 129 String expecting = 130 "digraph G {\n" + 131 "rankdir=LR;\n" + 132 " s0[label=\"0\"];\n" + 133 " s1[label=\"*\"];\n" + 134 " s0->s1[label=\"1\"];\n" + 135 "}\n"; 136 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 137 } 138 test_a$_ax_fullctx()139 @Test public void test_a$_ax_fullctx() { 140 PredictionContext a1 = a(); 141 PredictionContext x = x(); 142 PredictionContext a2 = createSingleton(x, 1); 143 PredictionContext r = PredictionContext.merge(a1, a2, fullCtx(), null); 144 // System.out.println(toDOTString(r, fullCtx())); 145 String expecting = 146 "digraph G {\n" + 147 "rankdir=LR;\n" + 148 " s0[label=\"0\"];\n" + 149 " s1[shape=record, label=\"<p0>|<p1>$\"];\n" + 150 " s2[label=\"$\"];\n" + 151 " s0->s1[label=\"1\"];\n" + 152 " s1:p0->s2[label=\"9\"];\n" + 153 "}\n"; 154 assertEquals(expecting, toDOTString(r, fullCtx())); 155 } 156 test_ax$_a$()157 @Test public void test_ax$_a$() { 158 PredictionContext x = x(); 159 PredictionContext a1 = createSingleton(x, 1); 160 PredictionContext a2 = a(); 161 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 162 // System.out.println(toDOTString(r, rootIsWildcard())); 163 String expecting = 164 "digraph G {\n" + 165 "rankdir=LR;\n" + 166 " s0[label=\"0\"];\n" + 167 " s1[label=\"*\"];\n" + 168 " s0->s1[label=\"1\"];\n" + 169 "}\n"; 170 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 171 } 172 test_aa$_a$_$_fullCtx()173 @Test public void test_aa$_a$_$_fullCtx() { 174 PredictionContext empty = PredictionContext.EMPTY; 175 PredictionContext child1 = createSingleton(empty, 8); 176 PredictionContext right = PredictionContext.merge(empty, child1, false, null); 177 PredictionContext left = createSingleton(right, 8); 178 PredictionContext merged = PredictionContext.merge(left, right, false, null); 179 String actual = toDOTString(merged, false); 180 // System.out.println(actual); 181 String expecting = 182 "digraph G {\n" + 183 "rankdir=LR;\n" + 184 " s0[shape=record, label=\"<p0>|<p1>$\"];\n" + 185 " s1[shape=record, label=\"<p0>|<p1>$\"];\n" + 186 " s2[label=\"$\"];\n" + 187 " s0:p0->s1[label=\"8\"];\n" + 188 " s1:p0->s2[label=\"8\"];\n" + 189 "}\n"; 190 assertEquals(expecting, actual); 191 } 192 test_ax$_a$_fullctx()193 @Test public void test_ax$_a$_fullctx() { 194 PredictionContext x = x(); 195 PredictionContext a1 = createSingleton(x, 1); 196 PredictionContext a2 = a(); 197 PredictionContext r = PredictionContext.merge(a1, a2, fullCtx(), null); 198 // System.out.println(toDOTString(r, fullCtx())); 199 String expecting = 200 "digraph G {\n" + 201 "rankdir=LR;\n" + 202 " s0[label=\"0\"];\n" + 203 " s1[shape=record, label=\"<p0>|<p1>$\"];\n" + 204 " s2[label=\"$\"];\n" + 205 " s0->s1[label=\"1\"];\n" + 206 " s1:p0->s2[label=\"9\"];\n" + 207 "}\n"; 208 assertEquals(expecting, toDOTString(r, fullCtx())); 209 } 210 test_a_b()211 @Test public void test_a_b() { 212 PredictionContext r = PredictionContext.merge(a(), b(), rootIsWildcard(), null); 213 // System.out.println(toDOTString(r, rootIsWildcard())); 214 String expecting = 215 "digraph G {\n" + 216 "rankdir=LR;\n" + 217 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 218 " s1[label=\"*\"];\n" + 219 " s0:p0->s1[label=\"1\"];\n" + 220 " s0:p1->s1[label=\"2\"];\n" + 221 "}\n"; 222 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 223 } 224 test_ax_ax_same()225 @Test public void test_ax_ax_same() { 226 PredictionContext x = x(); 227 PredictionContext a1 = createSingleton(x, 1); 228 PredictionContext a2 = createSingleton(x, 1); 229 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 230 // System.out.println(toDOTString(r, rootIsWildcard())); 231 String expecting = 232 "digraph G {\n" + 233 "rankdir=LR;\n" + 234 " s0[label=\"0\"];\n" + 235 " s1[label=\"1\"];\n" + 236 " s2[label=\"*\"];\n" + 237 " s0->s1[label=\"1\"];\n" + 238 " s1->s2[label=\"9\"];\n" + 239 "}\n"; 240 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 241 } 242 test_ax_ax()243 @Test public void test_ax_ax() { 244 PredictionContext x1 = x(); 245 PredictionContext x2 = x(); 246 PredictionContext a1 = createSingleton(x1, 1); 247 PredictionContext a2 = createSingleton(x2, 1); 248 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 249 // System.out.println(toDOTString(r, rootIsWildcard())); 250 String expecting = 251 "digraph G {\n" + 252 "rankdir=LR;\n" + 253 " s0[label=\"0\"];\n" + 254 " s1[label=\"1\"];\n" + 255 " s2[label=\"*\"];\n" + 256 " s0->s1[label=\"1\"];\n" + 257 " s1->s2[label=\"9\"];\n" + 258 "}\n"; 259 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 260 } 261 test_abx_abx()262 @Test public void test_abx_abx() { 263 PredictionContext x1 = x(); 264 PredictionContext x2 = x(); 265 PredictionContext b1 = createSingleton(x1, 2); 266 PredictionContext b2 = createSingleton(x2, 2); 267 PredictionContext a1 = createSingleton(b1, 1); 268 PredictionContext a2 = createSingleton(b2, 1); 269 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 270 // System.out.println(toDOTString(r, rootIsWildcard())); 271 String expecting = 272 "digraph G {\n" + 273 "rankdir=LR;\n" + 274 " s0[label=\"0\"];\n" + 275 " s1[label=\"1\"];\n" + 276 " s2[label=\"2\"];\n" + 277 " s3[label=\"*\"];\n" + 278 " s0->s1[label=\"1\"];\n" + 279 " s1->s2[label=\"2\"];\n" + 280 " s2->s3[label=\"9\"];\n" + 281 "}\n"; 282 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 283 } 284 test_abx_acx()285 @Test public void test_abx_acx() { 286 PredictionContext x1 = x(); 287 PredictionContext x2 = x(); 288 PredictionContext b = createSingleton(x1, 2); 289 PredictionContext c = createSingleton(x2, 3); 290 PredictionContext a1 = createSingleton(b, 1); 291 PredictionContext a2 = createSingleton(c, 1); 292 PredictionContext r = PredictionContext.merge(a1, a2, rootIsWildcard(), null); 293 // System.out.println(toDOTString(r, rootIsWildcard())); 294 String expecting = 295 "digraph G {\n" + 296 "rankdir=LR;\n" + 297 " s0[label=\"0\"];\n" + 298 " s1[shape=record, label=\"<p0>|<p1>\"];\n" + 299 " s2[label=\"2\"];\n" + 300 " s3[label=\"*\"];\n" + 301 " s0->s1[label=\"1\"];\n" + 302 " s1:p0->s2[label=\"2\"];\n" + 303 " s1:p1->s2[label=\"3\"];\n" + 304 " s2->s3[label=\"9\"];\n" + 305 "}\n"; 306 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 307 } 308 test_ax_bx_same()309 @Test public void test_ax_bx_same() { 310 PredictionContext x = x(); 311 PredictionContext a = createSingleton(x, 1); 312 PredictionContext b = createSingleton(x, 2); 313 PredictionContext r = PredictionContext.merge(a, b, rootIsWildcard(), null); 314 // System.out.println(toDOTString(r, rootIsWildcard())); 315 String expecting = 316 "digraph G {\n" + 317 "rankdir=LR;\n" + 318 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 319 " s1[label=\"1\"];\n" + 320 " s2[label=\"*\"];\n" + 321 " s0:p0->s1[label=\"1\"];\n" + 322 " s0:p1->s1[label=\"2\"];\n" + 323 " s1->s2[label=\"9\"];\n" + 324 "}\n"; 325 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 326 } 327 test_ax_bx()328 @Test public void test_ax_bx() { 329 PredictionContext x1 = x(); 330 PredictionContext x2 = x(); 331 PredictionContext a = createSingleton(x1, 1); 332 PredictionContext b = createSingleton(x2, 2); 333 PredictionContext r = PredictionContext.merge(a, b, rootIsWildcard(), null); 334 // System.out.println(toDOTString(r, rootIsWildcard())); 335 String expecting = 336 "digraph G {\n" + 337 "rankdir=LR;\n" + 338 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 339 " s1[label=\"1\"];\n" + 340 " s2[label=\"*\"];\n" + 341 " s0:p0->s1[label=\"1\"];\n" + 342 " s0:p1->s1[label=\"2\"];\n" + 343 " s1->s2[label=\"9\"];\n" + 344 "}\n"; 345 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 346 } 347 test_ax_by()348 @Test public void test_ax_by() { 349 PredictionContext a = createSingleton(x(), 1); 350 PredictionContext b = createSingleton(y(), 2); 351 PredictionContext r = PredictionContext.merge(a, b, rootIsWildcard(), null); 352 // System.out.println(toDOTString(r, rootIsWildcard())); 353 String expecting = 354 "digraph G {\n" + 355 "rankdir=LR;\n" + 356 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 357 " s2[label=\"2\"];\n" + 358 " s3[label=\"*\"];\n" + 359 " s1[label=\"1\"];\n" + 360 " s0:p0->s1[label=\"1\"];\n" + 361 " s0:p1->s2[label=\"2\"];\n" + 362 " s2->s3[label=\"10\"];\n" + 363 " s1->s3[label=\"9\"];\n" + 364 "}\n"; 365 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 366 } 367 test_a$_bx()368 @Test public void test_a$_bx() { 369 PredictionContext x2 = x(); 370 PredictionContext a = a(); 371 PredictionContext b = createSingleton(x2, 2); 372 PredictionContext r = PredictionContext.merge(a, b, rootIsWildcard(), null); 373 // System.out.println(toDOTString(r, rootIsWildcard())); 374 String expecting = 375 "digraph G {\n" + 376 "rankdir=LR;\n" + 377 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 378 " s2[label=\"2\"];\n" + 379 " s1[label=\"*\"];\n" + 380 " s0:p0->s1[label=\"1\"];\n" + 381 " s0:p1->s2[label=\"2\"];\n" + 382 " s2->s1[label=\"9\"];\n" + 383 "}\n"; 384 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 385 } 386 test_a$_bx_fullctx()387 @Test public void test_a$_bx_fullctx() { 388 PredictionContext x2 = x(); 389 PredictionContext a = a(); 390 PredictionContext b = createSingleton(x2, 2); 391 PredictionContext r = PredictionContext.merge(a, b, fullCtx(), null); 392 // System.out.println(toDOTString(r, fullCtx())); 393 String expecting = 394 "digraph G {\n" + 395 "rankdir=LR;\n" + 396 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 397 " s2[label=\"2\"];\n" + 398 " s1[label=\"$\"];\n" + 399 " s0:p0->s1[label=\"1\"];\n" + 400 " s0:p1->s2[label=\"2\"];\n" + 401 " s2->s1[label=\"9\"];\n" + 402 "}\n"; 403 assertEquals(expecting, toDOTString(r, fullCtx())); 404 } 405 406 @Ignore("Known inefficiency but deferring resolving the issue for now") test_aex_bfx()407 @Test public void test_aex_bfx() { 408 // TJP: this is inefficient as it leaves the top x nodes unmerged. 409 PredictionContext x1 = x(); 410 PredictionContext x2 = x(); 411 PredictionContext e = createSingleton(x1, 5); 412 PredictionContext f = createSingleton(x2, 6); 413 PredictionContext a = createSingleton(e, 1); 414 PredictionContext b = createSingleton(f, 2); 415 PredictionContext r = PredictionContext.merge(a, b, rootIsWildcard(), null); 416 // System.out.println(toDOTString(r, rootIsWildcard())); 417 String expecting = 418 "digraph G {\n" + 419 "rankdir=LR;\n" + 420 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 421 " s2[label=\"2\"];\n" + 422 " s3[label=\"3\"];\n" + 423 " s4[label=\"*\"];\n" + 424 " s1[label=\"1\"];\n" + 425 " s0:p0->s1[label=\"1\"];\n" + 426 " s0:p1->s2[label=\"2\"];\n" + 427 " s2->s3[label=\"6\"];\n" + 428 " s3->s4[label=\"9\"];\n" + 429 " s1->s3[label=\"5\"];\n" + 430 "}\n"; 431 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 432 } 433 434 // Array merges 435 test_A$_A$_fullctx()436 @Test public void test_A$_A$_fullctx() { 437 ArrayPredictionContext A1 = array(PredictionContext.EMPTY); 438 ArrayPredictionContext A2 = array(PredictionContext.EMPTY); 439 PredictionContext r = PredictionContext.merge(A1, A2, fullCtx(), null); 440 // System.out.println(toDOTString(r, fullCtx())); 441 String expecting = 442 "digraph G {\n" + 443 "rankdir=LR;\n" + 444 " s0[label=\"$\"];\n" + 445 "}\n"; 446 assertEquals(expecting, toDOTString(r, fullCtx())); 447 } 448 test_Aab_Ac()449 @Test public void test_Aab_Ac() { // a,b + c 450 SingletonPredictionContext a = a(); 451 SingletonPredictionContext b = b(); 452 SingletonPredictionContext c = c(); 453 ArrayPredictionContext A1 = array(a, b); 454 ArrayPredictionContext A2 = array(c); 455 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 456 // System.out.println(toDOTString(r, rootIsWildcard())); 457 String expecting = 458 "digraph G {\n" + 459 "rankdir=LR;\n" + 460 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 461 " s1[label=\"*\"];\n" + 462 " s0:p0->s1[label=\"1\"];\n" + 463 " s0:p1->s1[label=\"2\"];\n" + 464 " s0:p2->s1[label=\"3\"];\n" + 465 "}\n"; 466 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 467 } 468 test_Aa_Aa()469 @Test public void test_Aa_Aa() { 470 SingletonPredictionContext a1 = a(); 471 SingletonPredictionContext a2 = a(); 472 ArrayPredictionContext A1 = array(a1); 473 ArrayPredictionContext A2 = array(a2); 474 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 475 // System.out.println(toDOTString(r, rootIsWildcard())); 476 String expecting = 477 "digraph G {\n" + 478 "rankdir=LR;\n" + 479 " s0[label=\"0\"];\n" + 480 " s1[label=\"*\"];\n" + 481 " s0->s1[label=\"1\"];\n" + 482 "}\n"; 483 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 484 } 485 test_Aa_Abc()486 @Test public void test_Aa_Abc() { // a + b,c 487 SingletonPredictionContext a = a(); 488 SingletonPredictionContext b = b(); 489 SingletonPredictionContext c = c(); 490 ArrayPredictionContext A1 = array(a); 491 ArrayPredictionContext A2 = array(b, c); 492 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 493 // System.out.println(toDOTString(r, rootIsWildcard())); 494 String expecting = 495 "digraph G {\n" + 496 "rankdir=LR;\n" + 497 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 498 " s1[label=\"*\"];\n" + 499 " s0:p0->s1[label=\"1\"];\n" + 500 " s0:p1->s1[label=\"2\"];\n" + 501 " s0:p2->s1[label=\"3\"];\n" + 502 "}\n"; 503 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 504 } 505 test_Aac_Ab()506 @Test public void test_Aac_Ab() { // a,c + b 507 SingletonPredictionContext a = a(); 508 SingletonPredictionContext b = b(); 509 SingletonPredictionContext c = c(); 510 ArrayPredictionContext A1 = array(a, c); 511 ArrayPredictionContext A2 = array(b); 512 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 513 // System.out.println(toDOTString(r, rootIsWildcard())); 514 String expecting = 515 "digraph G {\n" + 516 "rankdir=LR;\n" + 517 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 518 " s1[label=\"*\"];\n" + 519 " s0:p0->s1[label=\"1\"];\n" + 520 " s0:p1->s1[label=\"2\"];\n" + 521 " s0:p2->s1[label=\"3\"];\n" + 522 "}\n"; 523 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 524 } 525 test_Aab_Aa()526 @Test public void test_Aab_Aa() { // a,b + a 527 ArrayPredictionContext A1 = array(a(), b()); 528 ArrayPredictionContext A2 = array(a()); 529 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 530 // System.out.println(toDOTString(r, rootIsWildcard())); 531 String expecting = 532 "digraph G {\n" + 533 "rankdir=LR;\n" + 534 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 535 " s1[label=\"*\"];\n" + 536 " s0:p0->s1[label=\"1\"];\n" + 537 " s0:p1->s1[label=\"2\"];\n" + 538 "}\n"; 539 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 540 } 541 test_Aab_Ab()542 @Test public void test_Aab_Ab() { // a,b + b 543 ArrayPredictionContext A1 = array(a(), b()); 544 ArrayPredictionContext A2 = array(b()); 545 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 546 // System.out.println(toDOTString(r, rootIsWildcard())); 547 String expecting = 548 "digraph G {\n" + 549 "rankdir=LR;\n" + 550 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 551 " s1[label=\"*\"];\n" + 552 " s0:p0->s1[label=\"1\"];\n" + 553 " s0:p1->s1[label=\"2\"];\n" + 554 "}\n"; 555 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 556 } 557 test_Aax_Aby()558 @Test public void test_Aax_Aby() { // ax + by but in arrays 559 SingletonPredictionContext a = createSingleton(x(), 1); 560 SingletonPredictionContext b = createSingleton(y(), 2); 561 ArrayPredictionContext A1 = array(a); 562 ArrayPredictionContext A2 = array(b); 563 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 564 // System.out.println(toDOTString(r, rootIsWildcard())); 565 String expecting = 566 "digraph G {\n" + 567 "rankdir=LR;\n" + 568 " s0[shape=record, label=\"<p0>|<p1>\"];\n" + 569 " s2[label=\"2\"];\n" + 570 " s3[label=\"*\"];\n" + 571 " s1[label=\"1\"];\n" + 572 " s0:p0->s1[label=\"1\"];\n" + 573 " s0:p1->s2[label=\"2\"];\n" + 574 " s2->s3[label=\"10\"];\n" + 575 " s1->s3[label=\"9\"];\n" + 576 "}\n"; 577 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 578 } 579 test_Aax_Aay()580 @Test public void test_Aax_Aay() { // ax + ay -> merged singleton a, array parent 581 SingletonPredictionContext a1 = createSingleton(x(), 1); 582 SingletonPredictionContext a2 = createSingleton(y(), 1); 583 ArrayPredictionContext A1 = array(a1); 584 ArrayPredictionContext A2 = array(a2); 585 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 586 // System.out.println(toDOTString(r, rootIsWildcard())); 587 String expecting = 588 "digraph G {\n" + 589 "rankdir=LR;\n" + 590 " s0[label=\"0\"];\n" + 591 " s1[shape=record, label=\"<p0>|<p1>\"];\n" + 592 " s2[label=\"*\"];\n" + 593 " s0->s1[label=\"1\"];\n" + 594 " s1:p0->s2[label=\"9\"];\n" + 595 " s1:p1->s2[label=\"10\"];\n" + 596 "}\n"; 597 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 598 } 599 test_Aaxc_Aayd()600 @Test public void test_Aaxc_Aayd() { // ax,c + ay,d -> merged a, array parent 601 SingletonPredictionContext a1 = createSingleton(x(), 1); 602 SingletonPredictionContext a2 = createSingleton(y(), 1); 603 ArrayPredictionContext A1 = array(a1, c()); 604 ArrayPredictionContext A2 = array(a2, d()); 605 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 606 // System.out.println(toDOTString(r, rootIsWildcard())); 607 String expecting = 608 "digraph G {\n" + 609 "rankdir=LR;\n" + 610 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 611 " s2[label=\"*\"];\n" + 612 " s1[shape=record, label=\"<p0>|<p1>\"];\n" + 613 " s0:p0->s1[label=\"1\"];\n" + 614 " s0:p1->s2[label=\"3\"];\n" + 615 " s0:p2->s2[label=\"4\"];\n" + 616 " s1:p0->s2[label=\"9\"];\n" + 617 " s1:p1->s2[label=\"10\"];\n" + 618 "}\n"; 619 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 620 } 621 test_Aaubv_Acwdx()622 @Test public void test_Aaubv_Acwdx() { // au,bv + cw,dx -> [a,b,c,d]->[u,v,w,x] 623 SingletonPredictionContext a = createSingleton(u(), 1); 624 SingletonPredictionContext b = createSingleton(v(), 2); 625 SingletonPredictionContext c = createSingleton(w(), 3); 626 SingletonPredictionContext d = createSingleton(x(), 4); 627 ArrayPredictionContext A1 = array(a, b); 628 ArrayPredictionContext A2 = array(c, d); 629 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 630 // System.out.println(toDOTString(r, rootIsWildcard())); 631 String expecting = 632 "digraph G {\n" + 633 "rankdir=LR;\n" + 634 " s0[shape=record, label=\"<p0>|<p1>|<p2>|<p3>\"];\n" + 635 " s4[label=\"4\"];\n" + 636 " s5[label=\"*\"];\n" + 637 " s3[label=\"3\"];\n" + 638 " s2[label=\"2\"];\n" + 639 " s1[label=\"1\"];\n" + 640 " s0:p0->s1[label=\"1\"];\n" + 641 " s0:p1->s2[label=\"2\"];\n" + 642 " s0:p2->s3[label=\"3\"];\n" + 643 " s0:p3->s4[label=\"4\"];\n" + 644 " s4->s5[label=\"9\"];\n" + 645 " s3->s5[label=\"8\"];\n" + 646 " s2->s5[label=\"7\"];\n" + 647 " s1->s5[label=\"6\"];\n" + 648 "}\n"; 649 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 650 } 651 test_Aaubv_Abvdx()652 @Test public void test_Aaubv_Abvdx() { // au,bv + bv,dx -> [a,b,d]->[u,v,x] 653 SingletonPredictionContext a = createSingleton(u(), 1); 654 SingletonPredictionContext b1 = createSingleton(v(), 2); 655 SingletonPredictionContext b2 = createSingleton(v(), 2); 656 SingletonPredictionContext d = createSingleton(x(), 4); 657 ArrayPredictionContext A1 = array(a, b1); 658 ArrayPredictionContext A2 = array(b2, d); 659 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 660 // System.out.println(toDOTString(r, rootIsWildcard())); 661 String expecting = 662 "digraph G {\n" + 663 "rankdir=LR;\n" + 664 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 665 " s3[label=\"3\"];\n" + 666 " s4[label=\"*\"];\n" + 667 " s2[label=\"2\"];\n" + 668 " s1[label=\"1\"];\n" + 669 " s0:p0->s1[label=\"1\"];\n" + 670 " s0:p1->s2[label=\"2\"];\n" + 671 " s0:p2->s3[label=\"4\"];\n" + 672 " s3->s4[label=\"9\"];\n" + 673 " s2->s4[label=\"7\"];\n" + 674 " s1->s4[label=\"6\"];\n" + 675 "}\n"; 676 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 677 } 678 test_Aaubv_Abwdx()679 @Test public void test_Aaubv_Abwdx() { // au,bv + bw,dx -> [a,b,d]->[u,[v,w],x] 680 SingletonPredictionContext a = createSingleton(u(), 1); 681 SingletonPredictionContext b1 = createSingleton(v(), 2); 682 SingletonPredictionContext b2 = createSingleton(w(), 2); 683 SingletonPredictionContext d = createSingleton(x(), 4); 684 ArrayPredictionContext A1 = array(a, b1); 685 ArrayPredictionContext A2 = array(b2, d); 686 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 687 // System.out.println(toDOTString(r, rootIsWildcard())); 688 String expecting = 689 "digraph G {\n" + 690 "rankdir=LR;\n" + 691 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 692 " s3[label=\"3\"];\n" + 693 " s4[label=\"*\"];\n" + 694 " s2[shape=record, label=\"<p0>|<p1>\"];\n" + 695 " s1[label=\"1\"];\n" + 696 " s0:p0->s1[label=\"1\"];\n" + 697 " s0:p1->s2[label=\"2\"];\n" + 698 " s0:p2->s3[label=\"4\"];\n" + 699 " s3->s4[label=\"9\"];\n" + 700 " s2:p0->s4[label=\"7\"];\n" + 701 " s2:p1->s4[label=\"8\"];\n" + 702 " s1->s4[label=\"6\"];\n" + 703 "}\n"; 704 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 705 } 706 test_Aaubv_Abvdu()707 @Test public void test_Aaubv_Abvdu() { // au,bv + bv,du -> [a,b,d]->[u,v,u]; u,v shared 708 SingletonPredictionContext a = createSingleton(u(), 1); 709 SingletonPredictionContext b1 = createSingleton(v(), 2); 710 SingletonPredictionContext b2 = createSingleton(v(), 2); 711 SingletonPredictionContext d = createSingleton(u(), 4); 712 ArrayPredictionContext A1 = array(a, b1); 713 ArrayPredictionContext A2 = array(b2, d); 714 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 715 // System.out.println(toDOTString(r, rootIsWildcard())); 716 String expecting = 717 "digraph G {\n" + 718 "rankdir=LR;\n" + 719 " s0[shape=record, label=\"<p0>|<p1>|<p2>\"];\n" + 720 " s2[label=\"2\"];\n" + 721 " s3[label=\"*\"];\n" + 722 " s1[label=\"1\"];\n" + 723 " s0:p0->s1[label=\"1\"];\n" + 724 " s0:p1->s2[label=\"2\"];\n" + 725 " s0:p2->s1[label=\"4\"];\n" + 726 " s2->s3[label=\"7\"];\n" + 727 " s1->s3[label=\"6\"];\n" + 728 "}\n"; 729 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 730 } 731 test_Aaubu_Acudu()732 @Test public void test_Aaubu_Acudu() { // au,bu + cu,du -> [a,b,c,d]->[u,u,u,u] 733 SingletonPredictionContext a = createSingleton(u(), 1); 734 SingletonPredictionContext b = createSingleton(u(), 2); 735 SingletonPredictionContext c = createSingleton(u(), 3); 736 SingletonPredictionContext d = createSingleton(u(), 4); 737 ArrayPredictionContext A1 = array(a, b); 738 ArrayPredictionContext A2 = array(c, d); 739 PredictionContext r = PredictionContext.merge(A1, A2, rootIsWildcard(), null); 740 // System.out.println(toDOTString(r, rootIsWildcard())); 741 String expecting = 742 "digraph G {\n" + 743 "rankdir=LR;\n" + 744 " s0[shape=record, label=\"<p0>|<p1>|<p2>|<p3>\"];\n" + 745 " s1[label=\"1\"];\n" + 746 " s2[label=\"*\"];\n" + 747 " s0:p0->s1[label=\"1\"];\n" + 748 " s0:p1->s1[label=\"2\"];\n" + 749 " s0:p2->s1[label=\"3\"];\n" + 750 " s0:p3->s1[label=\"4\"];\n" + 751 " s1->s2[label=\"6\"];\n" + 752 "}\n"; 753 assertEquals(expecting, toDOTString(r, rootIsWildcard())); 754 } 755 756 757 // ------------ SUPPORT ------------------------- 758 a()759 protected SingletonPredictionContext a() { 760 return createSingleton(PredictionContext.EMPTY, 1); 761 } 762 b()763 private SingletonPredictionContext b() { 764 return createSingleton(PredictionContext.EMPTY, 2); 765 } 766 c()767 private SingletonPredictionContext c() { 768 return createSingleton(PredictionContext.EMPTY, 3); 769 } 770 d()771 private SingletonPredictionContext d() { 772 return createSingleton(PredictionContext.EMPTY, 4); 773 } 774 u()775 private SingletonPredictionContext u() { 776 return createSingleton(PredictionContext.EMPTY, 6); 777 } 778 v()779 private SingletonPredictionContext v() { 780 return createSingleton(PredictionContext.EMPTY, 7); 781 } 782 w()783 private SingletonPredictionContext w() { 784 return createSingleton(PredictionContext.EMPTY, 8); 785 } 786 x()787 private SingletonPredictionContext x() { 788 return createSingleton(PredictionContext.EMPTY, 9); 789 } 790 y()791 private SingletonPredictionContext y() { 792 return createSingleton(PredictionContext.EMPTY, 10); 793 } 794 createSingleton(PredictionContext parent, int payload)795 public SingletonPredictionContext createSingleton(PredictionContext parent, int payload) { 796 SingletonPredictionContext a = SingletonPredictionContext.create(parent, payload); 797 return a; 798 } 799 array(SingletonPredictionContext... nodes)800 public ArrayPredictionContext array(SingletonPredictionContext... nodes) { 801 PredictionContext[] parents = new PredictionContext[nodes.length]; 802 int[] invokingStates = new int[nodes.length]; 803 for (int i=0; i<nodes.length; i++) { 804 parents[i] = nodes[i].parent; 805 invokingStates[i] = nodes[i].returnState; 806 } 807 return new ArrayPredictionContext(parents, invokingStates); 808 } 809 toDOTString(PredictionContext context, boolean rootIsWildcard)810 private static String toDOTString(PredictionContext context, boolean rootIsWildcard) { 811 StringBuilder nodes = new StringBuilder(); 812 StringBuilder edges = new StringBuilder(); 813 Map<PredictionContext, PredictionContext> visited = new IdentityHashMap<PredictionContext, PredictionContext>(); 814 Map<PredictionContext, Integer> contextIds = new IdentityHashMap<PredictionContext, Integer>(); 815 Deque<PredictionContext> workList = new ArrayDeque<PredictionContext>(); 816 visited.put(context, context); 817 contextIds.put(context, contextIds.size()); 818 workList.add(context); 819 while (!workList.isEmpty()) { 820 PredictionContext current = workList.pop(); 821 nodes.append(" s").append(contextIds.get(current)).append('['); 822 823 if (current.size() > 1) { 824 nodes.append("shape=record, "); 825 } 826 827 nodes.append("label=\""); 828 829 if (current.isEmpty()) { 830 nodes.append(rootIsWildcard ? '*' : '$'); 831 } else if (current.size() > 1) { 832 for (int i = 0; i < current.size(); i++) { 833 if (i > 0) { 834 nodes.append('|'); 835 } 836 837 nodes.append("<p").append(i).append('>'); 838 if (current.getReturnState(i) == PredictionContext.EMPTY_RETURN_STATE) { 839 nodes.append(rootIsWildcard ? '*' : '$'); 840 } 841 } 842 } else { 843 nodes.append(contextIds.get(current)); 844 } 845 846 nodes.append("\"];\n"); 847 848 if (current.isEmpty()) { 849 continue; 850 } 851 852 for (int i = 0; i < current.size(); i++) { 853 if (current.getReturnState(i) == PredictionContext.EMPTY_RETURN_STATE) { 854 continue; 855 } 856 857 if (visited.put(current.getParent(i), current.getParent(i)) == null) { 858 contextIds.put(current.getParent(i), contextIds.size()); 859 workList.push(current.getParent(i)); 860 } 861 862 edges.append(" s").append(contextIds.get(current)); 863 if (current.size() > 1) { 864 edges.append(":p").append(i); 865 } 866 867 edges.append("->"); 868 edges.append('s').append(contextIds.get(current.getParent(i))); 869 edges.append("[label=\"").append(current.getReturnState(i)).append("\"]"); 870 edges.append(";\n"); 871 } 872 } 873 874 StringBuilder builder = new StringBuilder(); 875 builder.append("digraph G {\n"); 876 builder.append("rankdir=LR;\n"); 877 builder.append(nodes); 878 builder.append(edges); 879 builder.append("}\n"); 880 return builder.toString(); 881 } 882 } 883