001/* Type hierarchy of token classes. 002 003 Copyright (c) 1997-2015 The Regents of the University of California. 004 All rights reserved. 005 Permission is hereby granted, without written agreement and without 006 license or royalty fees, to use, copy, modify, and distribute this 007 software and its documentation for any purpose, provided that the above 008 copyright notice and the following two paragraphs appear in all copies 009 of this software. 010 011 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY 012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF 014 THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF 015 SUCH DAMAGE. 016 017 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, 018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE 020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF 021 CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, 022 ENHANCEMENTS, OR MODIFICATIONS. 023 024 PT_COPYRIGHT_VERSION_2 025 COPYRIGHTENDKEY 026 027 */ 028package ptolemy.data.type; 029 030import java.util.Iterator; 031import java.util.Set; 032import java.util.concurrent.ConcurrentHashMap; 033 034import ptolemy.data.ActorToken; 035import ptolemy.data.Token; 036import ptolemy.graph.CPO; 037import ptolemy.graph.DirectedAcyclicGraph; 038 039/////////////////////////////////////////////////////////////////// 040//// TypeLattice 041 042/** 043 Type hierarchy for token classes. 044 <p> 045 There is exactly one instance of the type lattice. It is constructed 046 once and then does not change during execution. A concurrent hash 047 table is used to cache type comparison results to optimize for 048 frequently occurring type comparisons. 049 </p> 050 <p><a href="http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html">The Java Language Spec, 3rd ed.</a> 051 says: 052 <blockquote> 053 "The integral types are byte, short, int, and long, 054 whose values are 8-bit, 16-bit, 32-bit and 64-bit 055 signed two's-complement integers, respectively, and 056 char, whose values are 16-bit unsigned integers 057 representing UTF-16 code units (3.1). 058 059 The floating-point types are float, whose values 060 include the 32-bit IEEE 754 floating-point numbers, 061 and double, whose values include the 64-bit IEEE 062 754 floating-point numbers" 063 </blockquote> 064 065 Thus, 066 <menu> 067 <li>16-bit shorts are not losslessly convertable into 068 16-bit chars (unsigned integers). 069 <li>32-bit ints are not losslessly convertable into 070 32-bit floats. 071 <li>64-bit longs are not losslessly convertable into 072 64-bit doubles. 073 </menu> 074 075 @author Yuhong Xiong, Steve Neuendorffer, Marten Lohstroh 076 @version $Id$ 077 @since Ptolemy II 0.4 078 @Pt.ProposedRating Red (yuhong) 079 @Pt.AcceptedRating Red 080 @see ptolemy.graph.CPO 081 */ 082public class TypeLattice { 083 /////////////////////////////////////////////////////////////////// 084 //// public methods //// 085 086 /** Return the an instance of CPO representing the basic type 087 * lattice. 088 * @return an instance of CPO. 089 */ 090 public static CPO basicLattice() { 091 return _lattice._basicLattice; 092 } 093 094 /** Compare the types of the two specified tokens in the type lattice. 095 * This method returns one of ptolemy.graph.CPO.LOWER, 096 * ptolemy.graph.CPO.SAME, ptolemy.graph.CPO.HIGHER, 097 * ptolemy.graph.CPO.INCOMPARABLE, indicating the the type of the 098 * first argument is lower than, equal to, higher than, or 099 * incomparable with that of the second in the type hierarchy, 100 * respectively. 101 * @param token1 a Token. 102 * @param token2 a Token. 103 * @return An integer. 104 */ 105 public static int compare(Token token1, Token token2) { 106 if (token1 == null || token2 == null) { 107 throw new IllegalArgumentException( 108 "TypeLattice.compare(Token, Token): " 109 + "one or both of the argument tokens is null: " 110 + " token1 = " + token1 + ", token2 = " + token2); 111 } 112 113 return compare(token1.getType(), token2.getType()); 114 } 115 116 /** Compare the types of the two specified tokens in the type lattice. 117 * This method returns one of ptolemy.graph.CPO.LOWER, 118 * ptolemy.graph.CPO.SAME, ptolemy.graph.CPO.HIGHER, 119 * ptolemy.graph.CPO.INCOMPARABLE, indicating the the type of the 120 * first argument is lower than, equal to, higher than, or 121 * incomparable with that of the second in the type hierarchy, 122 * respectively. 123 * @param token a Token. 124 * @param type a Type. 125 * @return An integer. 126 */ 127 public static int compare(Token token, Type type) { 128 if (token == null) { 129 throw new IllegalArgumentException( 130 "TypeLattice.compare(Token, Type): " 131 + "token argument is null"); 132 } 133 134 return compare(token.getType(), type); 135 } 136 137 /** Compare the types of the two specified tokens in the type lattice. 138 * This method returns one of ptolemy.graph.CPO.LOWER, 139 * ptolemy.graph.CPO.SAME, ptolemy.graph.CPO.HIGHER, 140 * ptolemy.graph.CPO.INCOMPARABLE, indicating the the type of the 141 * first argument is lower than, equal to, higher than, or 142 * incomparable with that of the second in the type hierarchy, 143 * respectively. 144 * @param token a Token. 145 * @param type a Type. 146 * @return An integer. 147 */ 148 public static int compare(Type type, Token token) { 149 if (token == null) { 150 throw new IllegalArgumentException( 151 "TypeLattice.compare(Type, Token): " 152 + "token argument is null"); 153 } 154 155 return compare(type, token.getType()); 156 } 157 158 /** Compare two types in the type lattice. 159 * This method returns one of ptolemy.graph.CPO.LOWER, 160 * ptolemy.graph.CPO.SAME, ptolemy.graph.CPO.HIGHER, 161 * ptolemy.graph.CPO.INCOMPARABLE, indicating the first argument 162 * is lower than, equal to, higher than, or incomparable with the 163 * second argument in the type hierarchy, respectively. 164 * @param type1 an instance of Type. 165 * @param type2 an instance of Type. 166 * @return An integer. 167 */ 168 public static int compare(Type type1, Type type2) { 169 return _lattice.compare(type1, type2); 170 } 171 172 /** Return the an instance of CPO representing the infinite type 173 * lattice. 174 * @return an instance of CPO. 175 */ 176 public static CPO lattice() { 177 return _lattice; 178 } 179 180 /** Return the least upper bound of the two given types. 181 * @param type1 The first given type. 182 * @param type2 The second given type. 183 * @return The least upper bound of type1 and type2. 184 */ 185 public static Type leastUpperBound(Type type1, Type type2) { 186 return (Type) _lattice.leastUpperBound(type1, type2); 187 } 188 189 /////////////////////////////////////////////////////////////////// 190 //// inner class //// 191 192 // The infinite type lattice 193 private static class TheTypeLattice implements CPO<Object> { 194 /** Return the bottom element of the type lattice, which is UNKNOWN. 195 * @return The Type object representing UNKNOWN. 196 */ 197 @Override 198 public Object bottom() { 199 return _basicLattice.bottom(); 200 } 201 202 /** Compare two types in the type lattice. The arguments must be 203 * instances of Type, otherwise an exception will be thrown. 204 * This method returns one of ptolemy.graph.CPO.LOWER, 205 * ptolemy.graph.CPO.SAME, ptolemy.graph.CPO.HIGHER, 206 * ptolemy.graph.CPO.INCOMPARABLE, indicating the first argument 207 * is lower than, equal to, higher than, or incomparable with the 208 * second argument in the type hierarchy, respectively. 209 * @param t1 an instance of Type. 210 * @param t2 an instance of Type. 211 * @return An integer. 212 * @exception IllegalArgumentException If one or both arguments 213 * are not instances of Type. 214 */ 215 @Override 216 public int compare(Object t1, Object t2) { 217 if (!(t1 instanceof Type) || !(t2 instanceof Type)) { 218 throw new IllegalArgumentException("TheTypeLattice.compare: " 219 + "Arguments are not instances of Type: " + " type1 = " 220 + t1 + ", type2 = " + t2); 221 } 222 // System.out.println("compare " + type1 + " and " + type2 + " = " + _lattice.compare(type1, type2)); 223 224 if (t1 == t2) { 225 return SAME; 226 } 227 Integer val; 228 StringBuilder key = new StringBuilder(((Type) t1).toString()); 229 key.append("<"); 230 key.append(((Type) t2).toString()); 231 232 // Uncommment the false below to measure the impact of 233 // _lattice.compare() on ptolemy.data package performance... Run 234 // ptolemy/data/type/test/performance.xml before and after...(zk) 235 if (//false && 236 (val = _getCachedTypeComparisonResult(key.toString())) != null) { 237 return val; 238 } 239 240 Type ct1 = (Type) t1; 241 Type ct2 = (Type) t2; 242 243 Type t1Rep = _toRepresentative(ct1); 244 Type t2Rep = _toRepresentative(ct2); 245 246 int result = INCOMPARABLE; 247 if (t1Rep.equals(t2Rep) && t1Rep instanceof StructuredType) { 248 result = ((StructuredType) t1)._compare((StructuredType) t2); 249 } else if (t1Rep instanceof ArrayType 250 && !(t2Rep instanceof ArrayType) 251 && !t2.equals(BaseType.UNKNOWN) 252 && !t2.equals(BaseType.GENERAL) 253 && !t2.equals(BaseType.ARRAY_BOTTOM)) { 254 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 255 ArrayType arrayType = (ArrayType) t1; 256 if (arrayType.hasKnownLength() && arrayType.length() != 1) { 257 // If we have a Const with {1,2,3} -> Display 258 // then we used to fail here. 259 result = INCOMPARABLE; 260 } else { 261 int elementComparison = compare( 262 ((ArrayType) ct1).getElementType(), t2Rep); 263 if (elementComparison == SAME 264 || elementComparison == HIGHER) { 265 result = HIGHER; 266 } else { 267 if (t2Rep == BaseType.GENERAL) { 268 result = LOWER; 269 } else { 270 result = INCOMPARABLE; 271 } 272 } 273 } 274 } else if (t2Rep instanceof ArrayType 275 && !(t1Rep instanceof ArrayType) 276 && !t1.equals(BaseType.UNKNOWN) 277 && !t1.equals(BaseType.GENERAL) 278 && !t1.equals(BaseType.ARRAY_BOTTOM)) { 279 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 280 ArrayType arrayType = (ArrayType) t2; 281 if (arrayType.hasKnownLength() && arrayType.length() != 1 282 && !t1.equals(BaseType.GENERAL)) { 283 result = INCOMPARABLE; 284 } else { 285 int elementComparison = compare( 286 ((ArrayType) ct2).getElementType(), t1Rep); 287 if (elementComparison == SAME 288 || elementComparison == HIGHER) { 289 result = LOWER; 290 } else { 291 if (t1Rep == BaseType.GENERAL) { 292 result = HIGHER; 293 } else { 294 result = INCOMPARABLE; 295 } 296 } 297 } 298 } else if (_basicLattice.containsNodeWeight(t1Rep) 299 && _basicLattice.containsNodeWeight(t2Rep)) { 300 // Both are neither the same structured type, nor an array 301 // and non-array pair, so their type relation is defined 302 // by the basic lattice. 303 result = _basicLattice.compare(t1Rep, t2Rep); 304 } else { 305 // Both arguments are not the same structured type, and 306 // at least one is user defined, so their relation is 307 // rather simple. 308 if (t1Rep.equals(t2Rep)) { 309 result = SAME; 310 } else if (t1Rep == BaseType.UNKNOWN 311 || t2Rep == BaseType.GENERAL) { 312 result = LOWER; 313 } else if (t2Rep == BaseType.UNKNOWN 314 || t1Rep == BaseType.GENERAL) { 315 result = HIGHER; 316 } else { 317 result = INCOMPARABLE; 318 } 319 } 320 321 _setCachedTypeComparisonResult(key.toString(), result); 322 323 return result; 324 } 325 326 /** Throw an exception. This operation is not supported since the 327 * type lattice is infinite, 328 * @exception UnsupportedOperationException Always thrown. 329 */ 330 @Override 331 public Object[] downSet(Object e) { 332 throw new UnsupportedOperationException( 333 "TheTypeLattice.downSet(): operation not supported for " 334 + "the type lattice."); 335 } 336 337 /** Return the greatest lower bound of two types. 338 * @param t1 an instance of Type. 339 * @param t2 an instance of Type. 340 * @return an instance of Type. 341 * @exception IllegalArgumentException If one or both of the 342 * specified arguments are not instances of Type. 343 */ 344 @Override 345 public Object greatestLowerBound(Object t1, Object t2) { 346 if (!(t1 instanceof Type) || !(t2 instanceof Type)) { 347 throw new IllegalArgumentException( 348 "TheTypeLattice.greatestLowerBound: " 349 + "Arguments are not instances of Type."); 350 } 351 352 Type ct1 = (Type) t1; 353 Type ct2 = (Type) t2; 354 355 Type t1Rep = _toRepresentative(ct1); 356 Type t2Rep = _toRepresentative(ct2); 357 358 if (t1Rep.equals(t2Rep) && t1Rep instanceof StructuredType) { 359 return ((StructuredType) t1) 360 ._greatestLowerBound((StructuredType) t2); 361 } else if (t1Rep instanceof ArrayType 362 && !(t2Rep instanceof ArrayType) 363 && !t2.equals(BaseType.UNKNOWN) 364 && !t2.equals(BaseType.ARRAY_BOTTOM)) { 365 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 366 ArrayType arrayType = (ArrayType) t1; 367 int elementComparison = compare( 368 ((ArrayType) ct1).getElementType(), t2Rep); 369 if (elementComparison == SAME || elementComparison == HIGHER) { 370 if (arrayType.hasKnownLength() && arrayType.length() != 1) { 371 return BaseType.UNKNOWN; 372 } else { 373 return t2; 374 } 375 } else { 376 if (t2Rep == BaseType.GENERAL) { 377 return t1; 378 } else { 379 // INCOMPARABLE 380 if (_basicLattice.containsNodeWeight(t2Rep)) { 381 return _basicLattice.greatestLowerBound(t1Rep, 382 t2Rep); 383 } else { 384 // t2 is a user type (has no representative in the 385 // basic lattice). Arrays of this type are not supported. 386 return BaseType.UNKNOWN; 387 } 388 } 389 } 390 } else if (t2Rep instanceof ArrayType 391 && !(t1Rep instanceof ArrayType) 392 && !t1.equals(BaseType.UNKNOWN) 393 && !t1.equals(BaseType.ARRAY_BOTTOM)) { 394 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 395 ArrayType arrayType = (ArrayType) t2; 396 int elementComparison = compare( 397 ((ArrayType) ct2).getElementType(), t1Rep); 398 if (elementComparison == SAME || elementComparison == HIGHER) { 399 if (arrayType.hasKnownLength() && arrayType.length() != 1) { 400 return BaseType.UNKNOWN; 401 } else { 402 return t1; 403 } 404 } else { 405 if (t1Rep == BaseType.GENERAL) { 406 return t2; 407 } else { 408 // INCOMPARABLE 409 if (_basicLattice.containsNodeWeight(t1Rep)) { 410 return _basicLattice.greatestLowerBound(t1Rep, 411 t2Rep); 412 } else { 413 // t1 is a user type (has no representative in the 414 // basic lattice). Arrays of this type are not supported. 415 return BaseType.UNKNOWN; 416 } 417 } 418 } 419 } else if (_basicLattice.containsNodeWeight(t1Rep) 420 && _basicLattice.containsNodeWeight(t2Rep)) { 421 // Both are neither the same structured type, nor an array 422 // and non-array pair, so their type relation is defined 423 // by the basic lattice. 424 int relation = _basicLattice.compare(t1Rep, t2Rep); 425 426 if (relation == SAME) { 427 return t1; 428 } else if (relation == LOWER) { 429 return t1; 430 } else if (relation == HIGHER) { 431 return t2; 432 } else { // INCOMPARABLE 433 return _basicLattice.greatestLowerBound(t1Rep, t2Rep); 434 } 435 } else { 436 // Both arguments are not the same structured type, and 437 // at least one is user defined, so their relation is 438 // rather simple. 439 if (t1Rep.equals(t2Rep)) { 440 return t1; 441 } else if (t1Rep == BaseType.UNKNOWN 442 || t2Rep == BaseType.GENERAL) { 443 return t1; 444 } else if (t2Rep == BaseType.UNKNOWN 445 || t1Rep == BaseType.GENERAL) { 446 return t2; 447 } else { 448 return bottom(); 449 } 450 } 451 } 452 453 /** Return the greatest lower bound of a subset. 454 * @param subset a set of Types. 455 * @return an instance of Type. 456 */ 457 @Override 458 public Object greatestLowerBound(Set<Object> subset) { 459 if (subset.size() == 0) { 460 return BaseType.GENERAL; 461 } 462 463 Iterator<?> itr = subset.iterator(); 464 Object glb = itr.next(); 465 466 // start looping from index 0 so that subset[0] is checked for 467 // possible exception, in case the subset has only one element. 468 while (itr.hasNext()) { 469 glb = greatestLowerBound(glb, itr.next()); 470 } 471 472 return glb; 473 } 474 475 /** Return the greatest type of a set of types, or null if the 476 * greatest one does not exist. 477 * 478 * Note, that this only returns an element within the subset. 479 * To find the least upper bound of a set, see 480 * {@link #leastUpperBound(Set)}. 481 * 482 * @param subset a set of Types. 483 * @return A Type or null. 484 */ 485 @Override 486 public Object greatestElement(Set<Object> subset) { 487 // Compare each element with all of the other elements to search 488 // for the greatest one. This is a simple, brute force algorithm, 489 // but may be inefficient. A more efficient one is used in 490 // the graph package, but more complex. 491 for (Object o1 : subset) { 492 boolean isGreatest = true; 493 494 for (Object o2 : subset) { 495 int result = compare(o1, o2); 496 497 if (result == CPO.LOWER || result == CPO.INCOMPARABLE) { 498 isGreatest = false; 499 break; 500 } 501 } 502 503 if (isGreatest == true) { 504 return o1; 505 } 506 } 507 // Otherwise, the subset does not contain a greatest element. 508 return null; 509 } 510 511 /** Return true. 512 * @return true. 513 */ 514 @Override 515 public boolean isLattice() { 516 return true; 517 } 518 519 /** Return the least type of a set of types, or null if the 520 * least one does not exist. 521 * 522 * Note, that this only returns an element within the subset. 523 * To find the greatest lower bound of a set, see 524 * {@link #greatestLowerBound(Set)}. 525 * 526 * @param subset a set of Types. 527 * @return A Type or null. 528 */ 529 @Override 530 public Object leastElement(Set<Object> subset) { 531 // Compare each element with all of the other elements to search 532 // for the least one. This is a simple, brute force algorithm, 533 // but may be inefficient. A more efficient one is used in 534 // the graph package, but more complex. 535 for (Object o1 : subset) { 536 boolean isLeast = true; 537 538 for (Object o2 : subset) { 539 int result = compare(o1, o2); 540 541 if (result == CPO.HIGHER || result == CPO.INCOMPARABLE) { 542 isLeast = false; 543 break; 544 } 545 } 546 547 if (isLeast == true) { 548 return o1; 549 } 550 } 551 // Otherwise, the subset does not contain a least element. 552 return null; 553 } 554 555 /** Return the least upper bound of two types. 556 * @param t1 an instance of Type. 557 * @param t2 an instance of Type. 558 * @return an instance of Type. 559 */ 560 @Override 561 public Object leastUpperBound(Object t1, Object t2) { 562 if (!(t1 instanceof Type) || !(t2 instanceof Type)) { 563 throw new IllegalArgumentException( 564 "TheTypeLattice.leastUpperBound: " 565 + "Arguments are not instances of Type."); 566 } 567 568 // System.out.println("LUB of " + t1 + " and " + t2); 569 Type ct1 = (Type) t1; 570 Type ct2 = (Type) t2; 571 572 Type t1Rep = _toRepresentative(ct1); 573 Type t2Rep = _toRepresentative(ct2); 574 575 if (t1Rep.equals(t2Rep) && t1Rep instanceof StructuredType) { 576 return ((StructuredType) t1) 577 ._leastUpperBound((StructuredType) t2); 578 } else if (t1Rep instanceof ArrayType 579 && !(t2Rep instanceof ArrayType) 580 && !t2.equals(BaseType.UNKNOWN) 581 && !t2.equals(BaseType.GENERAL) 582 && !t2.equals(BaseType.ARRAY_BOTTOM)) { 583 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 584 ArrayType arrayType = (ArrayType) t1; 585 Type elementType = ((ArrayType) ct1).getElementType(); 586 int elementComparison = compare(elementType, t2Rep); 587 if (elementComparison == SAME || elementComparison == HIGHER) { 588 if (arrayType.hasKnownLength() && arrayType.length() != 1) { 589 // Least upper bound is unsized type. 590 return new ArrayType(elementType); 591 } else { 592 return t1; 593 } 594 } else { 595 if (t2Rep == BaseType.GENERAL) { 596 return t2; 597 } else { 598 // INCOMPARABLE 599 if (_basicLattice.containsNodeWeight(t2Rep) 600 && _basicLattice 601 .containsNodeWeight(elementType)) { 602 // The least upper bound is an array of the LUB 603 // of t2Rep and the element type of t1. 604 return new ArrayType((Type) _basicLattice 605 .leastUpperBound(elementType, t2Rep)); 606 } else { 607 // t2 is a user type (has no representative in the 608 // basic lattice). Arrays of this type are not supported. 609 return BaseType.GENERAL; 610 } 611 } 612 } 613 } else if (t1.equals(BaseType.ARRAY_BOTTOM) 614 && !(t2Rep instanceof ArrayType) 615 && !t2.equals(BaseType.UNKNOWN) 616 && !t2.equals(BaseType.GENERAL) 617 && !t2.equals(BaseType.ARRAY_BOTTOM)) { 618 // NOTE: Added by EAL, 10/8/12, to make lub(arrayBottom, double) = {double} 619 // INCOMPARABLE 620 if (_basicLattice.containsNodeWeight(t2Rep)) { 621 // The least upper bound is an array of t2Rep. 622 return new ArrayType(t2Rep); 623 } else { 624 // t2 is a user type (has no representative in the 625 // basic lattice). Arrays of this type are not supported. 626 return BaseType.GENERAL; 627 } 628 } else if (t2Rep instanceof ArrayType 629 && !(t1Rep instanceof ArrayType) 630 && !t1.equals(BaseType.UNKNOWN) 631 && !t1.equals(BaseType.GENERAL) 632 && !t1.equals(BaseType.ARRAY_BOTTOM)) { 633 // NOTE: Added by EAL, 7/16/06, to make scalar < {scalar} 634 ArrayType arrayType = (ArrayType) t2; 635 Type elementType = ((ArrayType) ct2).getElementType(); 636 int elementComparison = compare(elementType, t1Rep); 637 if (elementComparison == SAME || elementComparison == HIGHER) { 638 if (arrayType.hasKnownLength() && arrayType.length() != 1) { 639 // Least upper bound is unsized type. 640 return new ArrayType(elementType); 641 } else { 642 return t2; 643 } 644 } else { 645 if (t1Rep == BaseType.GENERAL) { 646 return t1; 647 } else { 648 // INCOMPARABLE 649 if (_basicLattice.containsNodeWeight(t1Rep) 650 && _basicLattice 651 .containsNodeWeight(elementType)) { 652 // The least upper bound is an array of the LUB 653 // of t2Rep and the element type of t1. 654 return new ArrayType((Type) _basicLattice 655 .leastUpperBound(elementType, t1Rep)); 656 } else { 657 // t1 is a user type (has no representative in the 658 // basic lattice). Arrays of this type are not supported. 659 return BaseType.GENERAL; 660 } 661 } 662 } 663 } else if (t2.equals(BaseType.ARRAY_BOTTOM) 664 && !(t1Rep instanceof ArrayType) 665 && !t1.equals(BaseType.UNKNOWN) 666 && !t1.equals(BaseType.GENERAL) 667 && !t1.equals(BaseType.ARRAY_BOTTOM)) { 668 // NOTE: Added by EAL, 10/8/12, to make lub(double, arrayBottom) = {double} 669 // INCOMPARABLE 670 if (_basicLattice.containsNodeWeight(t1Rep)) { 671 // The least upper bound is an array of t2Rep. 672 return new ArrayType(t1Rep); 673 } else { 674 // t2 is a user type (has no representative in the 675 // basic lattice). Arrays of this type are not supported. 676 return BaseType.GENERAL; 677 } 678 } else if (_basicLattice.containsNodeWeight(t1Rep) 679 && _basicLattice.containsNodeWeight(t2Rep)) { 680 // Both are neither the same structured type, nor an array 681 // and non-array pair, so their type relation is defined 682 // by the basic lattice. 683 int relation = _basicLattice.compare(t1Rep, t2Rep); 684 685 if (relation == SAME) { 686 return t1; 687 } else if (relation == LOWER) { 688 return t2; 689 } else if (relation == HIGHER) { 690 return t1; 691 } else { // INCOMPARABLE 692 return _basicLattice.leastUpperBound(t1Rep, t2Rep); 693 } 694 } else { 695 // Both arguments are not the same structured type, and 696 // at least one is user defined, so their relation is 697 // rather simple. 698 if (t1Rep.equals(t2Rep)) { 699 return t1; 700 } else if (t1Rep == BaseType.UNKNOWN 701 || t2Rep == BaseType.GENERAL) { 702 return t2; 703 } else if (t2Rep == BaseType.UNKNOWN 704 || t1Rep == BaseType.GENERAL) { 705 return t1; 706 } else { 707 return top(); 708 } 709 } 710 } 711 712 /** Return the least upper bound of a subset. 713 * @param subset a set of Types. 714 * @return an instance of Type. 715 */ 716 @Override 717 public Object leastUpperBound(Set<Object> subset) { 718 if (subset.size() == 0) { 719 return BaseType.UNKNOWN; 720 } 721 722 Iterator<?> itr = subset.iterator(); 723 Object lub = itr.next(); 724 725 // start looping from index 0 so that subset[0] is checked for 726 // possible exception, in case the subset has only one element. 727 while (itr.hasNext()) { 728 lub = leastUpperBound(lub, itr.next()); 729 } 730 731 return lub; 732 } 733 734 /** Return the top element of the type lattice, which is General. 735 * @return The Type object representing General. 736 */ 737 @Override 738 public Object top() { 739 return _basicLattice.top(); 740 } 741 742 /** Throw an exception. This operation is not supported since the 743 * type lattice is infinite, 744 * this operation is not supported. 745 * @exception UnsupportedOperationException Always thrown. 746 */ 747 @Override 748 public Object[] upSet(Object e) { 749 throw new UnsupportedOperationException( 750 "TheTypeLattice.upSet(): operation not supported for " 751 + "the type lattice."); 752 } 753 754 /////////////////////////////////////////////////////////////// 755 //// private constructor //// 756 // the constructor is private so only the outer class can use it. 757 private TheTypeLattice() { 758 _basicLattice = new DirectedAcyclicGraph(); 759 760 StructuredType arrayRep = new ArrayType(BaseType.UNKNOWN) 761 ._getRepresentative(); 762 763 String[] labels = new String[0]; 764 Type[] types = new Type[0]; 765 StructuredType recordRep = new RecordType(labels, types) 766 ._getRepresentative(); 767 StructuredType unionRep = new UnionType(labels, types) 768 ._getRepresentative(); 769 770 // FindBugs: Return value of FunctionType._getRepresentative() ignored, but method has no side effect 771 /*StructuredType functionRep = *//*new ptolemy.data.type.FunctionType( 772 new ptolemy.data.type.Type[0], 773 ptolemy.data.type.BaseType.UNKNOWN)._getRepresentative();*/ 774 775 _basicLattice.addNodeWeight(BaseType.BOOLEAN); 776 _basicLattice.addNodeWeight(BaseType.BOOLEAN_MATRIX); 777 _basicLattice.addNodeWeight(BaseType.UNSIGNED_BYTE); 778 _basicLattice.addNodeWeight(BaseType.COMPLEX); 779 _basicLattice.addNodeWeight(BaseType.COMPLEX_MATRIX); 780 _basicLattice.addNodeWeight(BaseType.DOUBLE); 781 _basicLattice.addNodeWeight(BaseType.DOUBLE_MATRIX); 782 _basicLattice.addNodeWeight(BaseType.UNSIZED_FIX); 783 _basicLattice.addNodeWeight(BaseType.SIZED_FIX); 784 _basicLattice.addNodeWeight(BaseType.FIX_MATRIX); 785 _basicLattice.addNodeWeight(BaseType.FLOAT); 786 _basicLattice.addNodeWeight(BaseType.INT); 787 _basicLattice.addNodeWeight(BaseType.INT_MATRIX); 788 _basicLattice.addNodeWeight(BaseType.LONG); 789 _basicLattice.addNodeWeight(BaseType.LONG_MATRIX); 790 _basicLattice.addNodeWeight(BaseType.MATRIX); 791 _basicLattice.addNodeWeight(BaseType.UNKNOWN); 792 // NOTE: Removed NUMERICAL from the type lattice, EAL 7/22/06. 793 // _basicLattice.addNodeWeight(BaseType.NUMERICAL); 794 _basicLattice.addNodeWeight(BaseType.OBJECT); 795 _basicLattice.addNodeWeight(BaseType.DATE); 796 797 // Strange bug here, see moml/test/aJVMBug.xml 798 // and ptdevel email from 7/21. 799 //_basicLattice.addNodeWeight(BaseType.ACTOR); 800 _basicLattice.addNodeWeight(ActorToken.TYPE); 801 802 _basicLattice.addNodeWeight(BaseType.XMLTOKEN); 803 _basicLattice.addNodeWeight(BaseType.SCALAR); 804 _basicLattice.addNodeWeight(BaseType.SHORT); 805 _basicLattice.addNodeWeight(BaseType.STRING); 806 _basicLattice.addNodeWeight(BaseType.EVENT); 807 _basicLattice.addNodeWeight(BaseType.GENERAL); 808 _basicLattice.addNodeWeight(BaseType.PETITE); 809 _basicLattice.addNodeWeight(BaseType.NIL); 810 811 _basicLattice.addNodeWeight(arrayRep); 812 _basicLattice.addNodeWeight(BaseType.ARRAY_BOTTOM); 813 _basicLattice.addNodeWeight(recordRep); 814 _basicLattice.addNodeWeight(unionRep); 815 816 _basicLattice.addEdge(BaseType.XMLTOKEN, BaseType.GENERAL); 817 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.XMLTOKEN); 818 _basicLattice.addEdge(BaseType.OBJECT, BaseType.GENERAL); 819 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.OBJECT); 820 _basicLattice.addEdge(BaseType.DATE, BaseType.STRING); 821 // Allowing a conversion from STRING to a DATE would make the lattice cyclic 822 //_basicLattice.addEdge(BaseType.STRING, BaseType.DATE); 823 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.DATE); 824 825 // More of the strange jvm bug, see above. 826 //_basicLattice.addEdge(BaseType.ACTOR, BaseType.GENERAL); 827 //_basicLattice.addEdge(BaseType.UNKNOWN, BaseType.ACTOR); 828 _basicLattice.addEdge(ActorToken.TYPE, BaseType.GENERAL); 829 _basicLattice.addEdge(BaseType.UNKNOWN, ActorToken.TYPE); 830 831 _basicLattice.addEdge(BaseType.STRING, BaseType.GENERAL); 832 _basicLattice.addEdge(BaseType.MATRIX, BaseType.STRING); 833 _basicLattice.addEdge(BaseType.BOOLEAN_MATRIX, BaseType.MATRIX); 834 _basicLattice.addEdge(BaseType.BOOLEAN, BaseType.BOOLEAN_MATRIX); 835 _basicLattice.addEdge(BaseType.BOOLEAN, BaseType.SCALAR); 836 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.BOOLEAN); 837 838 // NOTE: Removed NUMERICAL from the type lattice, EAL 7/22/06. 839 // _basicLattice.addEdge(BaseType.NUMERICAL, BaseType.MATRIX); 840 _basicLattice.addEdge(BaseType.FIX_MATRIX, BaseType.MATRIX); 841 _basicLattice.addEdge(BaseType.SCALAR, BaseType.MATRIX); 842 _basicLattice.addEdge(BaseType.LONG_MATRIX, BaseType.MATRIX); 843 _basicLattice.addEdge(BaseType.COMPLEX_MATRIX, BaseType.MATRIX); 844 845 _basicLattice.addEdge(BaseType.UNSIZED_FIX, BaseType.FIX_MATRIX); 846 _basicLattice.addEdge(BaseType.SIZED_FIX, BaseType.UNSIZED_FIX); 847 _basicLattice.addEdge(BaseType.UNSIZED_FIX, BaseType.SCALAR); 848 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.SIZED_FIX); 849 _basicLattice.addEdge(BaseType.LONG, BaseType.SCALAR); 850 _basicLattice.addEdge(BaseType.LONG, BaseType.LONG_MATRIX); 851 _basicLattice.addEdge(BaseType.INT_MATRIX, BaseType.LONG_MATRIX); 852 _basicLattice.addEdge(BaseType.INT, BaseType.LONG); 853 _basicLattice.addEdge(BaseType.INT, BaseType.INT_MATRIX); 854 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.UNSIGNED_BYTE); 855 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.PETITE); 856 _basicLattice.addEdge(BaseType.INT_MATRIX, BaseType.DOUBLE_MATRIX); 857 _basicLattice.addEdge(BaseType.DOUBLE_MATRIX, 858 BaseType.COMPLEX_MATRIX); 859 _basicLattice.addEdge(BaseType.DOUBLE, BaseType.DOUBLE_MATRIX); 860 _basicLattice.addEdge(BaseType.INT, BaseType.DOUBLE); 861 _basicLattice.addEdge(BaseType.DOUBLE, BaseType.SCALAR); 862 863 _basicLattice.addEdge(BaseType.PETITE, BaseType.DOUBLE); 864 _basicLattice.addEdge(BaseType.COMPLEX, BaseType.SCALAR); 865 _basicLattice.addEdge(BaseType.COMPLEX, BaseType.COMPLEX_MATRIX); 866 867 _basicLattice.addEdge(BaseType.DOUBLE, BaseType.COMPLEX); 868 _basicLattice.addEdge(BaseType.UNSIGNED_BYTE, BaseType.SHORT); 869 _basicLattice.addEdge(BaseType.SHORT, BaseType.INT); 870 _basicLattice.addEdge(BaseType.SHORT, BaseType.FLOAT); 871 _basicLattice.addEdge(BaseType.FLOAT, BaseType.DOUBLE); 872 873 _basicLattice.addEdge(BaseType.EVENT, BaseType.GENERAL); 874 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.EVENT); 875 876 // NOTE: Below used to add an edge to BaseType.STRING, but 877 // other concrete array types are not < STRING (see compare methods above). 878 // EAL 10/8/12. 879 _basicLattice.addEdge(arrayRep, BaseType.GENERAL); 880 _basicLattice.addEdge(BaseType.ARRAY_BOTTOM, arrayRep); 881 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.ARRAY_BOTTOM); 882 883 _basicLattice.addEdge(recordRep, BaseType.GENERAL); 884 _basicLattice.addEdge(BaseType.UNKNOWN, recordRep); 885 886 _basicLattice.addEdge(unionRep, BaseType.GENERAL); 887 _basicLattice.addEdge(BaseType.UNKNOWN, unionRep); 888 889 _basicLattice.addEdge(BaseType.UNKNOWN, BaseType.NIL); 890 _basicLattice.addEdge(BaseType.NIL, BaseType.BOOLEAN); 891 // NOTE: Redundant, given edge to UnsignedByte 892 // _basicLattice.addEdge(BaseType.NIL, BaseType.DOUBLE); 893 // _basicLattice.addEdge(BaseType.NIL, BaseType.LONG); 894 // _basicLattice.addEdge(BaseType.NIL, BaseType.INT); 895 _basicLattice.addEdge(BaseType.NIL, BaseType.UNSIGNED_BYTE); 896 897 assert _basicLattice.isLattice(); 898 } 899 900 /////////////////////////////////////////////////////////////// 901 //// private methods //// 902 903 /** Return the result for the types that have the given two 904 * indexes as hashes. 905 */ 906 private static final Integer _getCachedTypeComparisonResult( 907 String key) { 908 return _compareCache.get(key); 909 } 910 911 /** Set the result for the types that have the given two 912 * indexes as hashes. 913 */ 914 private static final void _setCachedTypeComparisonResult(String key, 915 int value) { 916 _compareCache.put(key, value); 917 } 918 919 // If the argument is a structured type, return its representative; 920 // otherwise, return the argument. In the latter case, the argument 921 // is either a base type or a user defined type that is not a 922 // structured type. 923 private Type _toRepresentative(Type t) { 924 if (t instanceof StructuredType) { 925 return ((StructuredType) t)._getRepresentative(); 926 } else { 927 return t; 928 } 929 } 930 931 /////////////////////////////////////////////////////////////// 932 //// private variables //// 933 934 private DirectedAcyclicGraph _basicLattice; 935 936 /** The result cache for parts of the type lattice. */ 937 private final static ConcurrentHashMap<String, Integer> _compareCache = new ConcurrentHashMap<String, Integer>(); 938 939 } 940 941 /////////////////////////////////////////////////////////////////// 942 //// private variables //// 943 944 /** The infinite type lattice. */ 945 private static TheTypeLattice _lattice = new TheTypeLattice(); 946}