Add some tests about range types.

test/cctest/test-types.cc

Index: test/cctest/test-types.cc
diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc
index 0cd24728c38cecd21321eea51e029af783d28bb5..ef6e91613633a663432aff35b8eb6914c9c22329 100644
--- a/test/cctest/test-types.cc
+++ b/test/cctest/test-types.cc
@@ -11,9 +11,23 @@
 
 using namespace v8::internal;
 
+
 // Testing auxiliaries (breaking the Type abstraction).
+
+
+static bool IsInteger(double x) {
+  return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities.
+}
+
+
+static bool IsInteger(i::Object* x) {
+  return x->IsNumber() && IsInteger(x->Number());
+}
+
+
 typedef uint32_t bitset;
 
+
 struct ZoneRep {
   typedef void* Struct;
 
@@ -502,6 +516,17 @@ struct Tests : Rep {
         CHECK(Equal(type1, type2) == (*map1 == *map2));
       }
     }
+
+    // Subtyping: Class(M1)->Is(Class(M2)) iff M1 = M2

[rossberg, 2014/09/24 12:59:09]

Hm, I'd rather leave the subtyping tests where they were. Some layering is
useful, and tests like Class and Constant are meant to just test the basic type
constructors, not anything about relations defined on top. (Which was also the
reason why I did not use subtyping in the Equal predicate originally.)

[neis1, 2014/09/24 15:12:08]

I changed it back now.  But if you look at e.g. Constant(), you'll see that
there already are a couple dozen subtyping tests in there.

+    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
+      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
+        Handle<i::Map> map1 = *mt1;
+        Handle<i::Map> map2 = *mt2;
+        TypeHandle class_type1 = T.Class(map1);
+        TypeHandle class_type2 = T.Class(map2);
+        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
+      }
+    }
   }
 
   void Constant() {
@@ -530,6 +555,17 @@ struct Tests : Rep {
       }
     }
 
+    // Subtyping: Constant(V1)->Is(Constant(V2)) iff V1 = V2
+    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
+      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
+        Handle<i::Object> value1 = *vt1;
+        Handle<i::Object> value2 = *vt2;
+        TypeHandle const_type1 = T.Constant(value1);
+        TypeHandle const_type2 = T.Constant(value2);
+        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
+      }
+    }
+
     // Typing of numbers
     Factory* fac = isolate->factory();
     CHECK(T.Constant(fac->NewNumber(0))->Is(T.UnsignedSmall));
@@ -617,6 +653,151 @@ struct Tests : Rep {
         }
       }
     }
+
+    // Subtyping:
+    // Range(x1, y1)->Is(Range(x2, y2)) iff x1 >= x2 /\ y1 <= y2
+    for (ValueIterator i1 = T.integers.begin();
+        i1 != T.integers.end(); ++i1) {
+      for (ValueIterator j1 = i1;
+          j1 != T.integers.end(); ++j1) {
+        for (ValueIterator i2 = T.integers.begin();
+             i2 != T.integers.end(); ++i2) {
+          for (ValueIterator j2 = i2;
+               j2 != T.integers.end(); ++j2) {
+            i::Handle<i::Object> min1 = *i1;
+            i::Handle<i::Object> max1 = *j1;
+            i::Handle<i::Object> min2 = *i2;
+            i::Handle<i::Object> max2 = *j2;
+            if (min1->Number() > max1->Number()) std::swap(min1, max1);
+            if (min2->Number() > max2->Number()) std::swap(min2, max2);
+            TypeHandle type1 = T.Range(min1, max1);
+            TypeHandle type2 = T.Range(min2, max2);
+            CHECK(type1->Is(type2) ==
+                (min2->Number() <= min1->Number() &&
+                 max1->Number() <= max2->Number()));
+          }
+        }
+      }
+    }
+
+    // Subtyping: If IsInteger(v) then Constant(v)->Is(Range(v, v)).
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->IsConstant() && IsInteger(*type->AsConstant()->Value())) {
+        CHECK(type->Is(
+            T.Range(type->AsConstant()->Value(), type->AsConstant()->Value())));
+      }
+    }
+
+    // If Constant(x)->Is(Range(min,max)) then IsInteger(v) and min <= x <= max.
+    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
+      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
+        TypeHandle type1 = *it1;
+        TypeHandle type2 = *it2;
+        if (type1->IsConstant() && type2->IsRange() && type1->Is(type2)) {
+          double x = type1->AsConstant()->Value()->Number();
+          double min = type2->AsRange()->Min()->Number();
+          double max = type2->AsRange()->Max()->Number();
+          CHECK(IsInteger(x) && min <= x && x <= max);
+        }
+      }
+    }
+
+    // Lub(Range(x,y))->Is(T.Union(T.Integral32, T.OtherNumber))
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->IsRange()) {
+        TypeHandle lub = Rep::BitsetType::New(
+            Rep::BitsetType::Lub(type), T.region());
+        CHECK(lub->Is(T.Union(T.Integral32, T.OtherNumber)));
+      }
+    }
+
+    // If b is regular numberic bitset, then b->Min() and b->Max() are integers.

[rossberg, 2014/09/24 12:59:09]

How about introducing a separate test MinMax for testing the general properties
of the Min and Max methods?

Typo: numeric

[neis1, 2014/09/24 15:12:08]

Done.

+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (this->IsBitset(type) && type->Is(T.Number) &&
+          !type->Is(T.None) && !type->Is(T.NaN)) {
+        CHECK(IsInteger(type->Min()) && IsInteger(type->Max()));
+      }
+    }
+
+    // If b is regular numberic bitset, then Range(b->Min(), b->Max())->Is(b).

[rossberg, 2014/09/24 12:59:09]

Typo

[neis1, 2014/09/24 15:12:08]

Done.

+    // TODO(neis): Need to ignore representation for this to be true.
+    /*
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (this->IsBitset(type) && type->Is(T.Number) &&
+          !type->Is(T.None) && !type->Is(T.NaN)) {
+        TypeHandle range = T.Range(
+            isolate->factory()->NewNumber(type->Min()),
+            isolate->factory()->NewNumber(type->Max()));
+        CHECK(range->Is(type));
+      }
+    }
+    */
+
+    // If b1 and b2 are regular numeric bitsets with b1->Is(b2), then
+    // b1->Min() >= b2->Min() and b1->Max() <= b2->Max().
+    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
+      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
+        TypeHandle type1 = *it1;
+        TypeHandle type2 = *it2;
+        if (this->IsBitset(type1) && type1->Is(type2) && type2->Is(T.Number) &&
+            !type1->Is(T.NaN) && !type2->Is(T.NaN)) {
+          CHECK(type1->Min() >= type2->Min());
+          CHECK(type1->Max() <= type2->Max());
+        }
+      }
+    }
+
+    // Lub(Range(x,y))->Min() <= x and y <= Lub(Range(x,y))->Max()
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->IsRange()) {
+        TypeHandle lub = Rep::BitsetType::New(
+            Rep::BitsetType::Lub(type), T.region());
+        CHECK(lub->Min() <= type->Min() && type->Max() <= lub->Max());
+      }
+    }
+  }
+
+  void Context() {
+    // Constructor
+    for (int i = 0; i < 20; ++i) {
+      TypeHandle type = T.Random();
+      TypeHandle context = T.Context(type);
+      CHECK(context->Iscontext());
+    }
+
+    // Attributes
+    for (int i = 0; i < 20; ++i) {
+      TypeHandle type = T.Random();
+      TypeHandle context = T.Context(type);
+      CheckEqual(type, context->AsContext()->Outer());
+    }
+
+    // Functionality & Injectivity: Context(T1) = Context(T2) iff T1 = T2
+    for (int i = 0; i < 20; ++i) {
+      for (int j = 0; j < 20; ++j) {
+        TypeHandle type1 = T.Random();
+        TypeHandle type2 = T.Random();
+        TypeHandle context1 = T.Context(type1);
+        TypeHandle context2 = T.Context(type2);
+        CHECK(Equal(context1, context2) == Equal(type1, type2));
+      }
+    }
+
+    // Subtyping: Context(T1)->Is(Context(T2)) iff T1 = T2
+    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
+      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
+        TypeHandle outer1 = *it1;
+        TypeHandle outer2 = *it2;
+        TypeHandle type1 = T.Context(outer1);
+        TypeHandle type2 = T.Context(outer2);
+        CHECK(type1->Is(type2) == outer1->Equals(outer2));
+      }
+    }
   }
 
   void Array() {
@@ -644,6 +825,17 @@ struct Tests : Rep {
         CHECK(Equal(array1, array2) == Equal(type1, type2));
       }
     }
+
+    // Subtyping: Array(T1)->Is(Array(T2)) iff T1 = T2
+    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
+      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
+        TypeHandle element1 = *it1;
+        TypeHandle element2 = *it2;
+        TypeHandle type1 = T.Array1(element1);
+        TypeHandle type2 = T.Array1(element2);
+        CHECK(type1->Is(type2) == element1->Equals(element2));
+      }
+    }
   }
 
   void Function() {
@@ -713,6 +905,21 @@ struct Tests : Rep {
         }
       }
     }
+
+    // Subtyping:
+    // Function0(S1, T1)->Is(Function0(S2, T2)) iff S1 = S2 and T1 = T2
+    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
+      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
+        TypeHandle result1 = *i;
+        TypeHandle receiver1 = *j;
+        TypeHandle type1 = T.Function0(result1, receiver1);
+        TypeHandle result2 = T.Random();
+        TypeHandle receiver2 = T.Random();
+        TypeHandle type2 = T.Function0(result2, receiver2);
+        CHECK(type1->Is(type2) ==
+            (result1->Equals(result2) && receiver1->Equals(receiver2)));
+      }
+    }
   }
 
   void Of() {
@@ -923,90 +1130,6 @@ struct Tests : Rep {
       }
     }
 
-    // Class(M1)->Is(Class(M2)) iff M1 = M2
-    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
-      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
-        Handle<i::Map> map1 = *mt1;
-        Handle<i::Map> map2 = *mt2;
-        TypeHandle class_type1 = T.Class(map1);
-        TypeHandle class_type2 = T.Class(map2);
-        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
-      }
-    }
-
-    // Constant(V1)->Is(Constant(V2)) iff V1 = V2
-    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
-      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
-        Handle<i::Object> value1 = *vt1;
-        Handle<i::Object> value2 = *vt2;
-        TypeHandle const_type1 = T.Constant(value1);
-        TypeHandle const_type2 = T.Constant(value2);
-        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
-      }
-    }
-
-    // Range(min1, max1)->Is(Range(min2, max2)) iff
-    // min1 >= min2 /\ max1 <= max2
-    for (ValueIterator i1 = T.integers.begin();
-        i1 != T.integers.end(); ++i1) {
-      for (ValueIterator j1 = T.integers.begin();
-          j1 != T.integers.end(); ++j1) {
-        for (ValueIterator i2 = T.integers.begin();
-             i2 != T.integers.end(); ++i2) {
-          for (ValueIterator j2 = T.integers.begin();
-               j2 != T.integers.end(); ++j2) {
-            i::Handle<i::Object> min1 = *i1;
-            i::Handle<i::Object> max1 = *j1;
-            i::Handle<i::Object> min2 = *i2;
-            i::Handle<i::Object> max2 = *j2;
-            if (min1->Number() > max1->Number()) std::swap(min1, max1);
-            if (min2->Number() > max2->Number()) std::swap(min2, max2);
-            TypeHandle type1 = T.Range(min1, max1);
-            TypeHandle type2 = T.Range(min2, max2);
-            CHECK(type1->Is(type2) ==
-                (min2->Number() <= min1->Number() &&
-                 max1->Number() <= max2->Number()));
-          }
-        }
-      }
-    }
-
-    // Context(T1)->Is(Context(T2)) iff T1 = T2
-    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
-      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
-        TypeHandle outer1 = *it1;
-        TypeHandle outer2 = *it2;
-        TypeHandle type1 = T.Context(outer1);
-        TypeHandle type2 = T.Context(outer2);
-        CHECK(type1->Is(type2) == outer1->Equals(outer2));
-      }
-    }
-
-    // Array(T1)->Is(Array(T2)) iff T1 = T2
-    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
-      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
-        TypeHandle element1 = *it1;
-        TypeHandle element2 = *it2;
-        TypeHandle type1 = T.Array1(element1);
-        TypeHandle type2 = T.Array1(element2);
-        CHECK(type1->Is(type2) == element1->Equals(element2));
-      }
-    }
-
-    // Function0(S1, T1)->Is(Function0(S2, T2)) iff S1 = S2 and T1 = T2
-    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
-      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
-        TypeHandle result1 = *i;
-        TypeHandle receiver1 = *j;
-        TypeHandle type1 = T.Function0(result1, receiver1);
-        TypeHandle result2 = T.Random();
-        TypeHandle receiver2 = T.Random();
-        TypeHandle type2 = T.Function0(result2, receiver2);
-        CHECK(type1->Is(type2) ==
-            (result1->Equals(result2) && receiver1->Equals(receiver2)));
-      }
-    }
-
     // (In-)Compatibilities.
     for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
       for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
@@ -1443,7 +1566,9 @@ struct Tests : Rep {
     }
 
     // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
-    // This does NOT hold!
+    // This does NOT hold!  For example:
+    // (Unsigned32 \/ Range(0,5)) \/ Range(-5,0) = Unsigned32 \/ Range(-5,0)
+    // Unsigned32 \/ (Range(0,5) \/ Range(-5,0)) = Unsigned32 \/ Range(-5,5)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1483,7 +1608,9 @@ struct Tests : Rep {
     }
 
     // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Range(-5,-1) <= Signed32
+    // Range(-5,-1) \/ Range(1,5) = Range(-5,5) </= Signed32 \/ Range(1,5)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1502,8 +1629,10 @@ struct Tests : Rep {
 
   void Union2() {
     // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
-    // This does NOT hold.  TODO(neis): Could fix this by splitting
-    // OtherNumber into a negative and a positive part.
+    // This does NOT hold.  For example:
+    // Range(-2^33, -2^33) <= OtherNumber
+    // Range(2^33, 2^33) <= OtherNumber
+    // Range(-2^33, 2^33) </= OtherNumber
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1685,7 +1814,11 @@ struct Tests : Rep {
 
     // Associativity:
     // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3)
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // (Class(..stringy1..) /\ Class(..stringy2..)) /\ Constant(..string..) =
+    // None
+    // Class(..stringy1..) /\ (Class(..stringy2..) /\ Constant(..string..)) =
+    // Constant(..string..)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1704,7 +1837,11 @@ struct Tests : Rep {
     */
 
     // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2)
-    // This does NOT hold.  Not even the disjunction.
+    // This does NOT hold.  For example:
+    // Class(..stringy..) /\ Constant(..string..) = Constant(..string..)
+    // Currently, not even the disjunction holds:
+    // Class(Internal/TaggedPtr) /\ (Any/Untagged \/ Context(..)) =
+    // Class(Internal/TaggedPtr) \/ Context(..)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1728,7 +1865,10 @@ struct Tests : Rep {
     }
 
     // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Class(OtherObject/TaggedPtr) <= Any/TaggedPtr
+    // Class(OtherObject/TaggedPtr) /\ Any/UntaggedInt1 = Class(..)
+    // Any/TaggedPtr /\ Any/UntaggedInt1 = None
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1745,7 +1885,10 @@ struct Tests : Rep {
     */
 
     // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3)
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Class(..stringy..) <= Class(..stringy..)
+    // Class(..stringy..) /\ Constant(..string..) = Constant(..string..)
+    // Constant(..string..) </= Class(..stringy..)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1762,8 +1905,6 @@ struct Tests : Rep {
     */
 
     // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
-    // This does NOT hold.
-    /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
@@ -1776,7 +1917,6 @@ struct Tests : Rep {
         }
       }
     }
-    */

[neis1, 2014/09/24 12:01:01]

I'm not sure why I thought this wouldn't hold anymore.

 
     // Bitset-class
     CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass);
@@ -1880,7 +2020,11 @@ struct Tests : Rep {
 
   void Distributivity() {
     // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Untagged \/ (Untagged /\ Class(../Tagged)) = Untagged \/ Class(../Tagged)
+    // (Untagged \/ Untagged) /\ (Untagged \/ Class(../Tagged)) =
+    // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
+    // because Untagged <= Untagged \/ Class(../Tagged)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -1900,7 +2044,10 @@ struct Tests : Rep {
     */
 
     // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
+    // (Untagged /\ Untagged) \/ (Untagged /\ Class(../Tagged)) =
+    // Untagged \/ Class(../Tagged)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
@@ -2098,13 +2245,11 @@ TEST(Intersect) {
 }
 
 
-/*
 TEST(Distributivity) {
   CcTest::InitializeVM();
   ZoneTests().Distributivity();
   HeapTests().Distributivity();
 }
-*/
 
 
 TEST(Convert) {