1/* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28package org.antlr.test; 29 30import org.antlr.analysis.Label; 31import org.antlr.misc.IntervalSet; 32import org.junit.Test; 33 34import java.util.ArrayList; 35import java.util.List; 36 37 38public class TestIntervalSet extends BaseTest { 39 40 /** Public default constructor used by TestRig */ 41 public TestIntervalSet() { 42 } 43 44 @Test public void testSingleElement() throws Exception { 45 IntervalSet s = IntervalSet.of(99); 46 String expecting = "99"; 47 assertEquals(s.toString(), expecting); 48 } 49 50 @Test public void testIsolatedElements() throws Exception { 51 IntervalSet s = new IntervalSet(); 52 s.add(1); 53 s.add('z'); 54 s.add('\uFFF0'); 55 String expecting = "{1, 122, 65520}"; 56 assertEquals(s.toString(), expecting); 57 } 58 59 @Test public void testMixedRangesAndElements() throws Exception { 60 IntervalSet s = new IntervalSet(); 61 s.add(1); 62 s.add('a','z'); 63 s.add('0','9'); 64 String expecting = "{1, 48..57, 97..122}"; 65 assertEquals(s.toString(), expecting); 66 } 67 68 @Test public void testSimpleAnd() throws Exception { 69 IntervalSet s = IntervalSet.of(10,20); 70 IntervalSet s2 = IntervalSet.of(13,15); 71 String expecting = "13..15"; 72 String result = (s.and(s2)).toString(); 73 assertEquals(result, expecting); 74 } 75 76 @Test public void testRangeAndIsolatedElement() throws Exception { 77 IntervalSet s = IntervalSet.of('a','z'); 78 IntervalSet s2 = IntervalSet.of('d'); 79 String expecting = "100"; 80 String result = (s.and(s2)).toString(); 81 assertEquals(result, expecting); 82 } 83 84 @Test public void testEmptyIntersection() throws Exception { 85 IntervalSet s = IntervalSet.of('a','z'); 86 IntervalSet s2 = IntervalSet.of('0','9'); 87 String expecting = "{}"; 88 String result = (s.and(s2)).toString(); 89 assertEquals(result, expecting); 90 } 91 92 @Test public void testEmptyIntersectionSingleElements() throws Exception { 93 IntervalSet s = IntervalSet.of('a'); 94 IntervalSet s2 = IntervalSet.of('d'); 95 String expecting = "{}"; 96 String result = (s.and(s2)).toString(); 97 assertEquals(result, expecting); 98 } 99 100 @Test public void testNotSingleElement() throws Exception { 101 IntervalSet vocabulary = IntervalSet.of(1,1000); 102 vocabulary.add(2000,3000); 103 IntervalSet s = IntervalSet.of(50,50); 104 String expecting = "{1..49, 51..1000, 2000..3000}"; 105 String result = (s.complement(vocabulary)).toString(); 106 assertEquals(result, expecting); 107 } 108 109 @Test public void testNotSet() throws Exception { 110 IntervalSet vocabulary = IntervalSet.of(1,1000); 111 IntervalSet s = IntervalSet.of(50,60); 112 s.add(5); 113 s.add(250,300); 114 String expecting = "{1..4, 6..49, 61..249, 301..1000}"; 115 String result = (s.complement(vocabulary)).toString(); 116 assertEquals(result, expecting); 117 } 118 119 @Test public void testNotEqualSet() throws Exception { 120 IntervalSet vocabulary = IntervalSet.of(1,1000); 121 IntervalSet s = IntervalSet.of(1,1000); 122 String expecting = "{}"; 123 String result = (s.complement(vocabulary)).toString(); 124 assertEquals(result, expecting); 125 } 126 127 @Test public void testNotSetEdgeElement() throws Exception { 128 IntervalSet vocabulary = IntervalSet.of(1,2); 129 IntervalSet s = IntervalSet.of(1); 130 String expecting = "2"; 131 String result = (s.complement(vocabulary)).toString(); 132 assertEquals(result, expecting); 133 } 134 135 @Test public void testNotSetFragmentedVocabulary() throws Exception { 136 IntervalSet vocabulary = IntervalSet.of(1,255); 137 vocabulary.add(1000,2000); 138 vocabulary.add(9999); 139 IntervalSet s = IntervalSet.of(50,60); 140 s.add(3); 141 s.add(250,300); 142 s.add(10000); // this is outside range of vocab and should be ignored 143 String expecting = "{1..2, 4..49, 61..249, 1000..2000, 9999}"; 144 String result = (s.complement(vocabulary)).toString(); 145 assertEquals(result, expecting); 146 } 147 148 @Test public void testSubtractOfCompletelyContainedRange() throws Exception { 149 IntervalSet s = IntervalSet.of(10,20); 150 IntervalSet s2 = IntervalSet.of(12,15); 151 String expecting = "{10..11, 16..20}"; 152 String result = (s.subtract(s2)).toString(); 153 assertEquals(result, expecting); 154 } 155 156 @Test public void testSubtractOfOverlappingRangeFromLeft() throws Exception { 157 IntervalSet s = IntervalSet.of(10,20); 158 IntervalSet s2 = IntervalSet.of(5,11); 159 String expecting = "12..20"; 160 String result = (s.subtract(s2)).toString(); 161 assertEquals(result, expecting); 162 163 IntervalSet s3 = IntervalSet.of(5,10); 164 expecting = "11..20"; 165 result = (s.subtract(s3)).toString(); 166 assertEquals(result, expecting); 167 } 168 169 @Test public void testSubtractOfOverlappingRangeFromRight() throws Exception { 170 IntervalSet s = IntervalSet.of(10,20); 171 IntervalSet s2 = IntervalSet.of(15,25); 172 String expecting = "10..14"; 173 String result = (s.subtract(s2)).toString(); 174 assertEquals(result, expecting); 175 176 IntervalSet s3 = IntervalSet.of(20,25); 177 expecting = "10..19"; 178 result = (s.subtract(s3)).toString(); 179 assertEquals(result, expecting); 180 } 181 182 @Test public void testSubtractOfCompletelyCoveredRange() throws Exception { 183 IntervalSet s = IntervalSet.of(10,20); 184 IntervalSet s2 = IntervalSet.of(1,25); 185 String expecting = "{}"; 186 String result = (s.subtract(s2)).toString(); 187 assertEquals(result, expecting); 188 } 189 190 @Test public void testSubtractOfRangeSpanningMultipleRanges() throws Exception { 191 IntervalSet s = IntervalSet.of(10,20); 192 s.add(30,40); 193 s.add(50,60); // s has 3 ranges now: 10..20, 30..40, 50..60 194 IntervalSet s2 = IntervalSet.of(5,55); // covers one and touches 2nd range 195 String expecting = "56..60"; 196 String result = (s.subtract(s2)).toString(); 197 assertEquals(result, expecting); 198 199 IntervalSet s3 = IntervalSet.of(15,55); // touches both 200 expecting = "{10..14, 56..60}"; 201 result = (s.subtract(s3)).toString(); 202 assertEquals(result, expecting); 203 } 204 205 /** The following was broken: 206 {0..113, 115..65534}-{0..115, 117..65534}=116..65534 207 */ 208 @Test public void testSubtractOfWackyRange() throws Exception { 209 IntervalSet s = IntervalSet.of(0,113); 210 s.add(115,200); 211 IntervalSet s2 = IntervalSet.of(0,115); 212 s2.add(117,200); 213 String expecting = "116"; 214 String result = (s.subtract(s2)).toString(); 215 assertEquals(result, expecting); 216 } 217 218 @Test public void testSimpleEquals() throws Exception { 219 IntervalSet s = IntervalSet.of(10,20); 220 IntervalSet s2 = IntervalSet.of(10,20); 221 Boolean expecting = new Boolean(true); 222 Boolean result = new Boolean(s.equals(s2)); 223 assertEquals(result, expecting); 224 225 IntervalSet s3 = IntervalSet.of(15,55); 226 expecting = new Boolean(false); 227 result = new Boolean(s.equals(s3)); 228 assertEquals(result, expecting); 229 } 230 231 @Test public void testEquals() throws Exception { 232 IntervalSet s = IntervalSet.of(10,20); 233 s.add(2); 234 s.add(499,501); 235 IntervalSet s2 = IntervalSet.of(10,20); 236 s2.add(2); 237 s2.add(499,501); 238 Boolean expecting = new Boolean(true); 239 Boolean result = new Boolean(s.equals(s2)); 240 assertEquals(result, expecting); 241 242 IntervalSet s3 = IntervalSet.of(10,20); 243 s3.add(2); 244 expecting = new Boolean(false); 245 result = new Boolean(s.equals(s3)); 246 assertEquals(result, expecting); 247 } 248 249 @Test public void testSingleElementMinusDisjointSet() throws Exception { 250 IntervalSet s = IntervalSet.of(15,15); 251 IntervalSet s2 = IntervalSet.of(1,5); 252 s2.add(10,20); 253 String expecting = "{}"; // 15 - {1..5, 10..20} = {} 254 String result = s.subtract(s2).toString(); 255 assertEquals(result, expecting); 256 } 257 258 @Test public void testMembership() throws Exception { 259 IntervalSet s = IntervalSet.of(15,15); 260 s.add(50,60); 261 assertTrue(!s.member(0)); 262 assertTrue(!s.member(20)); 263 assertTrue(!s.member(100)); 264 assertTrue(s.member(15)); 265 assertTrue(s.member(55)); 266 assertTrue(s.member(50)); 267 assertTrue(s.member(60)); 268 } 269 270 // {2,15,18} & 10..20 271 @Test public void testIntersectionWithTwoContainedElements() throws Exception { 272 IntervalSet s = IntervalSet.of(10,20); 273 IntervalSet s2 = IntervalSet.of(2,2); 274 s2.add(15); 275 s2.add(18); 276 String expecting = "{15, 18}"; 277 String result = (s.and(s2)).toString(); 278 assertEquals(result, expecting); 279 } 280 281 @Test public void testIntersectionWithTwoContainedElementsReversed() throws Exception { 282 IntervalSet s = IntervalSet.of(10,20); 283 IntervalSet s2 = IntervalSet.of(2,2); 284 s2.add(15); 285 s2.add(18); 286 String expecting = "{15, 18}"; 287 String result = (s2.and(s)).toString(); 288 assertEquals(result, expecting); 289 } 290 291 @Test public void testComplement() throws Exception { 292 IntervalSet s = IntervalSet.of(100,100); 293 s.add(101,101); 294 IntervalSet s2 = IntervalSet.of(100,102); 295 String expecting = "102"; 296 String result = (s.complement(s2)).toString(); 297 assertEquals(result, expecting); 298 } 299 300 @Test public void testComplement2() throws Exception { 301 IntervalSet s = IntervalSet.of(100,101); 302 IntervalSet s2 = IntervalSet.of(100,102); 303 String expecting = "102"; 304 String result = (s.complement(s2)).toString(); 305 assertEquals(result, expecting); 306 } 307 308 @Test public void testComplement3() throws Exception { 309 IntervalSet s = IntervalSet.of(1,96); 310 s.add(99,Label.MAX_CHAR_VALUE); 311 String expecting = "97..98"; 312 String result = (s.complement(1,Label.MAX_CHAR_VALUE)).toString(); 313 assertEquals(result, expecting); 314 } 315 316 @Test public void testMergeOfRangesAndSingleValues() throws Exception { 317 // {0..41, 42, 43..65534} 318 IntervalSet s = IntervalSet.of(0,41); 319 s.add(42); 320 s.add(43,65534); 321 String expecting = "0..65534"; 322 String result = s.toString(); 323 assertEquals(result, expecting); 324 } 325 326 @Test public void testMergeOfRangesAndSingleValuesReverse() throws Exception { 327 IntervalSet s = IntervalSet.of(43,65534); 328 s.add(42); 329 s.add(0,41); 330 String expecting = "0..65534"; 331 String result = s.toString(); 332 assertEquals(result, expecting); 333 } 334 335 @Test public void testMergeWhereAdditionMergesTwoExistingIntervals() throws Exception { 336 // 42, 10, {0..9, 11..41, 43..65534} 337 IntervalSet s = IntervalSet.of(42); 338 s.add(10); 339 s.add(0,9); 340 s.add(43,65534); 341 s.add(11,41); 342 String expecting = "0..65534"; 343 String result = s.toString(); 344 assertEquals(result, expecting); 345 } 346 347 @Test public void testMergeWithDoubleOverlap() throws Exception { 348 IntervalSet s = IntervalSet.of(1,10); 349 s.add(20,30); 350 s.add(5,25); // overlaps two! 351 String expecting = "1..30"; 352 String result = s.toString(); 353 assertEquals(result, expecting); 354 } 355 356 @Test public void testSize() throws Exception { 357 IntervalSet s = IntervalSet.of(20,30); 358 s.add(50,55); 359 s.add(5,19); 360 String expecting = "32"; 361 String result = String.valueOf(s.size()); 362 assertEquals(result, expecting); 363 } 364 365 @Test public void testToList() throws Exception { 366 IntervalSet s = IntervalSet.of(20,25); 367 s.add(50,55); 368 s.add(5,5); 369 String expecting = "[5, 20, 21, 22, 23, 24, 25, 50, 51, 52, 53, 54, 55]"; 370 List foo = new ArrayList(); 371 String result = String.valueOf(s.toList()); 372 assertEquals(result, expecting); 373 } 374 375 /** The following was broken: 376 {'\u0000'..'s', 'u'..'\uFFFE'} & {'\u0000'..'q', 's'..'\uFFFE'}= 377 {'\u0000'..'q', 's'}!!!! broken... 378 'q' is 113 ascii 379 'u' is 117 380 */ 381 @Test public void testNotRIntersectionNotT() throws Exception { 382 IntervalSet s = IntervalSet.of(0,'s'); 383 s.add('u',200); 384 IntervalSet s2 = IntervalSet.of(0,'q'); 385 s2.add('s',200); 386 String expecting = "{0..113, 115, 117..200}"; 387 String result = (s.and(s2)).toString(); 388 assertEquals(result, expecting); 389 } 390 391} 392