Add Union, contains() to SkylarkType

Refactor SkylarkType, notably adding Union types and runtime typechecks.
These are pre-requisites to unifying all Skylark function calls to use the same
code path, that will check types (like SkylarkFunction currently does) as well
handle a more complete Python calling convention (like MixedModeFunction is
almost but not quite able to do).

A SkylarkType can be either
* a Simple type corresponding to a Java class, with special types TOP and BOTTOM
 corresponding respectively to Object and EmptyType (similar to Void).
* a Combination of a generic class (LIST, MAP or SET) and an argument type
* a Union of a finite number of types
* a FunctionType associated with a name and a returnType (with ugly
 validation-time side-effects that we should probably move out of the type)

Unions are necessary because:
1- the type of some builtin function arguments are actually the Union of some
 type and a function type for a callback that computes the actual value.
2- the type of some builtin function arguments declared as "List" is actually
 the Union of java List and SkylarkList.
3- instead of adding lots of special cases at the point of argument validation,
 it's cleaner and more generally useful to have explicit Union types, that can
 then be displayed to users for documentation or debugging purposes.

Validation-time "type inference" is re-expressed simply as type intersection.

None is treated specially as inferred into TOP instead of NoneType.

Combination types are printed as genericType of argTypes, e.g. "dict of ints". "type" and "generic1" become "genericType" and "argType". In SkylarkList and SkylarkNestedSet, genericType becomes contentType.

--
MOS_MIGRATED_REVID=87340881

9 files changed, 728 insertions, 252 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index d7c142713e..778bc7bd8b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -285,8 +285,6 @@ public final class BinaryOperatorExpression extends Expression {
   SkylarkType validate(ValidationEnvironment env) throws EvalException {
     SkylarkType ltype = lhs.validate(env);
     SkylarkType rtype = rhs.validate(env);
-    String lname = EvalUtils.getDataTypeNameFromClass(ltype.getType());
-    String rname = EvalUtils.getDataTypeNameFromClass(rtype.getType());
 
     switch (operator) {
       case AND: {
@@ -320,19 +318,19 @@ public final class BinaryOperatorExpression extends Expression {
 
         // struct + struct
         if (ltype.isStruct() && rtype.isStruct()) {
-          return SkylarkType.of(ClassObject.class);
+          return SkylarkType.STRUCT;
         }
 
         if (ltype.isNset()) {
           if (rtype.isNset()) {
             return ltype.infer(rtype, "nested set", rhs.getLocation(), lhs.getLocation());
           } else if (rtype.isList()) {
-            return ltype.infer(SkylarkType.of(SkylarkNestedSet.class, rtype.getGenericType1()),
+            return ltype.infer(SkylarkType.of(SkylarkType.SET, rtype.getArgType()),
                 "nested set", rhs.getLocation(), lhs.getLocation());
           }
           if (rtype != SkylarkType.UNKNOWN) {
             throw new EvalException(getLocation(), String.format("can only concatenate nested sets "
-                + "with other nested sets or list of items, not '" + rname + "'"));
+                    + "with other nested sets or list of items, not '%s'", rtype));
           }
         }
 
@@ -384,7 +382,7 @@ public final class BinaryOperatorExpression extends Expression {
       case GREATER:
       case GREATER_EQUALS: {
         if (ltype != SkylarkType.UNKNOWN && !(Comparable.class.isAssignableFrom(ltype.getType()))) {
-          throw new EvalException(getLocation(), lname + " is not comparable");
+          throw new EvalException(getLocation(), ltype + " is not comparable");
         }
         ltype.infer(rtype, "comparison", lhs.getLocation(), rhs.getLocation());
         return SkylarkType.BOOL;
@@ -399,8 +397,7 @@ public final class BinaryOperatorExpression extends Expression {
         } else {
           if (rtype != SkylarkType.UNKNOWN) {
             throw new EvalException(getLocation(), String.format("operand 'in' only works on "
-                + "strings, dictionaries, lists, sets or tuples, not on a(n) %s",
-                EvalUtils.getDataTypeNameFromClass(rtype.getType())));
+                    + "strings, dictionaries, lists, sets or tuples, not on a(n) %s", rtype));
           }
         }
       }
@@ -411,7 +408,7 @@ public final class BinaryOperatorExpression extends Expression {
     if (ltype != SkylarkType.UNKNOWN && rtype != SkylarkType.UNKNOWN) {
       throw new EvalException(getLocation(),
           String.format("unsupported operand type(s) for %s: '%s' and '%s'",
-              operator, lname, rname));
+              operator, ltype, rtype));
     }
     return SkylarkType.UNKNOWN;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
index a69605e4a0..05190ab1e8 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.syntax;
 import com.google.common.collect.ImmutableMap;
 
 import java.util.LinkedHashMap;
-import java.util.Map;
 
 /**
  * Syntax node for dictionary comprehension expressions.
@@ -68,11 +67,8 @@ public class DictComprehension extends Expression {
   @Override
   SkylarkType validate(ValidationEnvironment env) throws EvalException {
     SkylarkType elementsType = listExpression.validate(env);
-    // TODO(bazel-team): GenericType1 should be a SkylarkType.
-    Class<?> listElementType = elementsType.getGenericType1();
-    SkylarkType listElementSkylarkType = listElementType.equals(Object.class)
-        ? SkylarkType.UNKNOWN : SkylarkType.of(listElementType);
-    env.update(loopVar.getName(), listElementSkylarkType, getLocation());
+    SkylarkType listElementType = SkylarkType.getGenericArgType(elementsType);
+    env.update(loopVar.getName(), listElementType, getLocation());
     SkylarkType keyType = keyExpression.validate(env);
     if (!keyType.isSimple()) {
       // TODO(bazel-team): this is most probably dead code but it's better to have it here
@@ -83,7 +79,7 @@ public class DictComprehension extends Expression {
     if (elementsType != SkylarkType.UNKNOWN && !elementsType.isList()) {
       throw new EvalException(getLocation(), "Dict comprehension elements must be a list");
     }
-    return SkylarkType.of(Map.class, keyType.getType());
+    return SkylarkType.of(SkylarkType.MAP, keyType);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 02c10a26e1..9448c32b2b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -187,11 +187,11 @@ public abstract class EvalUtils {
       if (list.isTuple()) {
         return "tuple";
       } else {
-        return "list" + (full ? " of " + list.getGenericType() + "s" : "");
+        return "list" + (full ? " of " + list.getContentType() + "s" : "");
       }
     } else if (object instanceof SkylarkNestedSet) {
       SkylarkNestedSet set = (SkylarkNestedSet) object;
-      return "set" + (full ? " of " + set.getGenericType() + "s" : "");
+      return "set" + (full ? " of " + set.getContentType() + "s" : "");
     } else {
       return getDataTypeNameFromClass(object.getClass());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
index 6a13ba846b..c48fe64319 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
@@ -128,6 +128,6 @@ public final class ListComprehension extends Expression {
       env.update(list.getKey().getName(), SkylarkType.UNKNOWN, getLocation());
     }
     elementExpression.validate(env);
-    return SkylarkType.of(SkylarkList.class);
+    return SkylarkType.LIST;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
index d8c7811d30..fc43c2fbcd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
@@ -129,6 +129,6 @@ public final class ListLiteral extends Expression {
         type = type.infer(nextType, "list literal", expr.getLocation(), getLocation());
       }
     }
-    return SkylarkType.of(SkylarkList.class, type.getType());
+    return SkylarkType.of(SkylarkType.LIST, type);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkFunction.java
index e6959e8fe2..ecfd660c48 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkFunction.java
@@ -162,55 +162,19 @@ public abstract class SkylarkFunction extends AbstractFunction {
       arguments.put(paramName, value);
       return;
     }
-    cast(getName(), paramName, param.type(), param.generic1(), value, loc, param.doc());
+    checkType(getName(), paramName, SkylarkType.of(param.type(), param.generic1()),
+        value, loc, param.doc());
     arguments.put(paramName, value);
   }
 
-  /**
-   * Throws an EvalException of realValue is not of the expected type, otherwise returns realValue.
-   * 
-   * @param functionName - name of the function
-   * @param paramName - name of the parameter
-   * @param expectedType - the expected type of the parameter
-   * @param expectedGenericType - the expected generic type of the parameter, or
-   * Object.class if undefined
-   * @param realValue - the actual value of the parameter
-   * @param loc - the location info used in the EvalException
-   * @param paramDoc - the documentation of the parameter to print in the error message
-   */
-  @SuppressWarnings("unchecked")
-  public static <T> T cast(String functionName, String paramName,
-      Class<T> expectedType, Class<?> expectedGenericType,
-      Object realValue, Location loc, String paramDoc) throws EvalException {
-    if (!(expectedType.isAssignableFrom(realValue.getClass()))) {
-      throw new EvalException(loc, String.format("expected %s for '%s' but got %s instead\n"
-          + "%s.%s: %s",
-          EvalUtils.getDataTypeNameFromClass(expectedType), paramName,
-          EvalUtils.getDataTypeName(realValue), functionName, paramName, paramDoc));
-    }
-    if (expectedType.equals(SkylarkList.class)) {
-      checkGeneric(functionName, paramName, expectedType, expectedGenericType,
-          realValue, ((SkylarkList) realValue).getGenericType(), loc, paramDoc);
-    } else if (expectedType.equals(SkylarkNestedSet.class)) {
-      checkGeneric(functionName, paramName, expectedType, expectedGenericType,
-          realValue, ((SkylarkNestedSet) realValue).getGenericType(), loc, paramDoc);
-    }
-    return (T) realValue;
-  }
-
-  private static void checkGeneric(String functionName, String paramName,
-      Class<?> expectedType, Class<?> expectedGenericType,
-      Object realValue, Class<?> realGenericType,
-      Location loc, String paramDoc) throws EvalException {
-    if (!realGenericType.equals(Object.class)
-        && !expectedGenericType.isAssignableFrom(realGenericType)) {
-      String mainType = EvalUtils.getDataTypeNameFromClass(expectedType);
-      throw new EvalException(loc, String.format(
-          "expected %s of %ss for '%s' but got %s of %ss instead\n%s.%s: %s",
-        mainType, EvalUtils.getDataTypeNameFromClass(expectedGenericType),
-        paramName,
-        EvalUtils.getDataTypeName(realValue), EvalUtils.getDataTypeNameFromClass(realGenericType),
-        functionName, paramName, paramDoc));
+  public static void checkType(String functionName, String paramName,
+      SkylarkType type, Object value, Location loc, String paramDoc) throws EvalException {
+    if (type != null && value != null) { // TODO(bazel-team): should we give a pass to NONE here?
+      if (!type.contains(value)) {
+        throw new EvalException(loc, String.format(
+            "expected %s for '%s' while calling %s but got %s instead: %s",
+            type, paramName, functionName, EvalUtils.getDataTypeName(value, true), value));
+      }
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
index 5e00f057ee..c30824f1af 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
@@ -40,15 +40,15 @@ import java.util.List;
         + "List elements have to be of the same type, <code>[1, 2, \"c\"]</code> results in an "
         + "error. Lists - just like everything - are immutable, therefore <code>x[1] = \"a\""
         + "</code> is not supported.")
-  // TODO(bazel-team): should we instead implements List<Object> like ImmutableList does?
-  public abstract class SkylarkList implements Iterable<Object> {
+// TODO(bazel-team): should we instead have it implement List<Object> like ImmutableList does?
+public abstract class SkylarkList implements Iterable<Object> {
 
   private final boolean tuple;
-  private final Class<?> genericType;
+  private final SkylarkType contentType;
 
-  private SkylarkList(boolean tuple, Class<?> genericType) {
+  private SkylarkList(boolean tuple, SkylarkType contentType) {
     this.tuple = tuple;
-    this.genericType = genericType;
+    this.contentType = contentType;
   }
 
   /**
@@ -74,8 +74,8 @@ import java.util.List;
   }
 
   @VisibleForTesting
-  public Class<?> getGenericType() {
-    return genericType;
+  public SkylarkType getContentType() {
+    return contentType;
   }
 
   @Override
@@ -88,17 +88,17 @@ import java.util.List;
   /**
    * Converts this Skylark list to a Java list.
    */
-  public abstract List<?> toList();
+  public abstract List<Object> toList();
 
   @SuppressWarnings("unchecked")
   public <T> Iterable<T> to(Class<T> type) {
-    Preconditions.checkArgument(this == EMPTY_LIST || type.isAssignableFrom(genericType));
+    Preconditions.checkArgument(this == EMPTY_LIST || contentType.canBeCastTo(type));
     return (Iterable<T>) this;
   }
 
   private static final class EmptySkylarkList extends SkylarkList {
     private EmptySkylarkList(boolean tuple) {
-      super(tuple, Object.class);
+      super(tuple, SkylarkType.TOP);
     }
 
     @Override
@@ -122,7 +122,7 @@ import java.util.List;
     }
 
     @Override
-    public List<?> toList() {
+    public List<Object> toList() {
       return isTuple() ? ImmutableList.of() : Lists.newArrayList();
     }
 
@@ -137,11 +137,16 @@ import java.util.List;
    */
   public static final SkylarkList EMPTY_LIST = new EmptySkylarkList(false);
 
+  /**
+   * An empty Skylark tuple.
+   */
+  public static final SkylarkList EMPTY_TUPLE = new EmptySkylarkList(true);
+
   private static final class SimpleSkylarkList extends SkylarkList {
     private final ImmutableList<Object> list;
 
-    private SimpleSkylarkList(ImmutableList<Object> list, boolean tuple, Class<?> genericType) {
-      super(tuple, genericType);
+    private SimpleSkylarkList(ImmutableList<Object> list, boolean tuple, SkylarkType contentType) {
+      super(tuple, contentType);
       this.list = Preconditions.checkNotNull(list);
     }
 
@@ -166,7 +171,7 @@ import java.util.List;
     }
 
     @Override
-    public List<?> toList() {
+    public List<Object> toList() {
       return isTuple() ? list : Lists.newArrayList(list);
     }
 
@@ -203,8 +208,8 @@ import java.util.List;
     private final Iterable<Object> iterable;
     private ImmutableList<Object> list = null;
 
-    private LazySkylarkList(Iterable<Object> iterable, boolean tuple, Class<?> genericType) {
-      super(tuple, genericType);
+    private LazySkylarkList(Iterable<Object> iterable, boolean tuple, SkylarkType contentType) {
+      super(tuple, contentType);
       this.iterable = Preconditions.checkNotNull(iterable);
     }
 
@@ -229,7 +234,7 @@ import java.util.List;
     }
 
     @Override
-    public List<?> toList() {
+    public List<Object> toList() {
       return getList();
     }
 
@@ -250,8 +255,8 @@ import java.util.List;
     private final SkylarkList right;
 
     private ConcatenatedSkylarkList(
-        SkylarkList left, SkylarkList right, boolean tuple, Class<?> genericType) {
-      super(tuple, genericType);
+        SkylarkList left, SkylarkList right, boolean tuple, SkylarkType contentType) {
+      super(tuple, contentType);
       this.left = Preconditions.checkNotNull(left);
       this.right = Preconditions.checkNotNull(right);
     }
@@ -286,59 +291,91 @@ import java.util.List;
     }
 
     @Override
-    public List<?> toList() {
+    public ImmutableList<Object> toList() {
       return ImmutableList.<Object>builder().addAll(left).addAll(right).build();
     }
   }
 
   /**
-   * Returns a Skylark list containing elements without a type check. Only use if all elements
-   * are of the same type.
+   * @param elements the contents of the list
+   * @param contentType a SkylarkType for the contents of the list
+   * @return a Skylark list containing elements without a type check
+   * Only use if you already know for sure all elements are of the specified type.
    */
-  public static SkylarkList list(Collection<?> elements, Class<?> genericType) {
+  public static SkylarkList list(Collection<?> elements, SkylarkType contentType) {
     if (elements.isEmpty()) {
       return EMPTY_LIST;
     }
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), false, genericType);
+    return new SimpleSkylarkList(ImmutableList.copyOf(elements), false, contentType);
+  }
+
+  /**
+   * @param elements the contents of the list
+   * @param contentType a Java class for the contents of the list
+   * @return a Skylark list containing elements without a type check.
+   * Only use if you already know for sure all elements are of the specified type.
+   */
+  @SuppressWarnings("unchecked")
+  public static SkylarkList list(Collection<?> elements, Class<?> contentType) {
+    return list(elements, SkylarkType.of(contentType));
   }
 
   /**
-   * Returns a Skylark list containing elements without a type check and without creating
-   * an immutable copy. Therefore the iterable containing elements must be immutable
-   * (which is not checked here so callers must be extra careful). This way
-   * it's possibly to create a SkylarkList without requesting the original iterator. This
-   * can be useful for nested set - list conversions.
+   * @param elements the contents of the list
+   * @param contentType a SkylarkType for the contents of the list
+   * @return a Skylark list without a type check and without creating an immutable copy.
+   * Therefore the iterable containing elements must be immutable
+   * (which is not checked here so callers must be extra careful).
+   * This way it's possibly to create a SkylarkList without requesting the original iterator.
+   * This can be useful for nested set - list conversions.
    */
   @SuppressWarnings("unchecked")
-  public static SkylarkList lazyList(Iterable<?> elements, Class<?> genericType) {
-    return new LazySkylarkList((Iterable<Object>) elements, false, genericType);
+  public static SkylarkList lazyList(Iterable<?> elements, SkylarkType contentType) {
+    return new LazySkylarkList((Iterable<Object>) elements, false, contentType);
   }
 
   /**
-   * Returns a Skylark list containing elements. Performs type check and throws an exception
-   * in case the list contains elements of different type.
+   * @param elements the contents of the list
+   * @param contentType a Java class for the contents of the list
+   * @return a Skylark list without a type check and without creating an immutable copy.
+   * Therefore the iterable containing elements must be immutable
+   * (which is not checked here so callers must be extra careful).
+   * This way it's possibly to create a SkylarkList without requesting the original iterator.
+   * This can be useful for nested set - list conversions.
+   */
+  @SuppressWarnings("unchecked")
+  public static SkylarkList lazyList(Iterable<?> elements, Class<?> contentType) {
+    return lazyList(elements, SkylarkType.of(contentType));
+  }
+
+  /**
+   * @param elements the contents of the list
+   * @return a Skylark list containing elements
+   * @throws an EvalException in case the list is not monomorphic
    */
   public static SkylarkList list(Collection<?> elements, Location loc) throws EvalException {
     if (elements.isEmpty()) {
       return EMPTY_LIST;
     }
     return new SimpleSkylarkList(
-        ImmutableList.copyOf(elements), false, getGenericType(elements, loc));
+        ImmutableList.copyOf(elements), false, getContentType(elements, loc));
   }
 
-  private static Class<?> getGenericType(Collection<?> elements, Location loc)
+  private static SkylarkType getContentType(Collection<?> elements, Location loc)
       throws EvalException {
-    Class<?> genericType = elements.iterator().next().getClass();
+    SkylarkType type = SkylarkType.TOP;
     for (Object element : elements) {
-      Class<?> type = element.getClass();
-      if (!EvalUtils.getSkylarkType(genericType).equals(EvalUtils.getSkylarkType(type))) {
+      SkylarkType elementType = SkylarkType.typeOf(element);
+      SkylarkType inter = SkylarkType.intersection(type, elementType);
+      if (inter == SkylarkType.BOTTOM) {
         throw new EvalException(loc, String.format(
-            "Incompatible types in list: found a %s but the first element is a %s",
-            EvalUtils.getDataTypeNameFromClass(type),
-            EvalUtils.getDataTypeNameFromClass(genericType)));
+            "Incompatible types in list: found a %s but the previous elements were %ss",
+            elementType, type));
+      } else {
+        type = inter;
       }
     }
-    return genericType;
+    return type;
   }
 
   /**
@@ -356,12 +393,12 @@ import java.util.List;
     if (right == EMPTY_LIST) {
       return left;
     }
-    if (!left.genericType.equals(right.genericType)) {
+    SkylarkType type = SkylarkType.intersection(left.contentType, right.contentType);
+    if (type == SkylarkType.BOTTOM) {
       throw new EvalException(loc, String.format("cannot concatenate list of %s with list of %s",
-          EvalUtils.getDataTypeNameFromClass(left.genericType),
-          EvalUtils.getDataTypeNameFromClass(right.genericType)));
+              left.contentType, right.contentType));
     }
-    return new ConcatenatedSkylarkList(left, right, left.isTuple(), left.genericType);
+    return new ConcatenatedSkylarkList(left, right, left.isTuple(), type);
   }
 
   /**
@@ -369,6 +406,6 @@ import java.util.List;
    */
   public static SkylarkList tuple(List<?> elements) {
     // Tuple elements do not have to have the same type.
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), true, Object.class);
+    return new SimpleSkylarkList(ImmutableList.copyOf(elements), true, SkylarkType.TOP);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
index 44729cf23e..5ba7f4d3cc 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
@@ -26,7 +26,6 @@ import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
-import java.util.Map;
 
 import javax.annotation.Nullable;
 
@@ -47,18 +46,18 @@ import javax.annotation.Nullable;
 @Immutable
 public final class SkylarkNestedSet implements Iterable<Object> {
 
-  private final Class<?> genericType;
+  private final SkylarkType contentType;
   @Nullable private final List<Object> items;
   @Nullable private final List<NestedSet<Object>> transitiveItems;
   private final NestedSet<?> set;
 
   public SkylarkNestedSet(Order order, Object item, Location loc) throws EvalException {
-    this(order, Object.class, item, loc, new ArrayList<Object>(),
+    this(order, SkylarkType.TOP, item, loc, new ArrayList<Object>(),
         new ArrayList<NestedSet<Object>>());
   }
 
   public SkylarkNestedSet(SkylarkNestedSet left, Object right, Location loc) throws EvalException {
-    this(left.set.getOrder(), left.genericType, right, loc,
+    this(left.set.getOrder(), left.contentType, right, loc,
         new ArrayList<Object>(checkItems(left.items, loc)),
         new ArrayList<NestedSet<Object>>(checkItems(left.transitiveItems, loc)));
   }
@@ -76,27 +75,27 @@ public final class SkylarkNestedSet implements Iterable<Object> {
 
   // This is safe because of the type checking
   @SuppressWarnings("unchecked")
-  private SkylarkNestedSet(Order order, Class<?> genericType, Object item, Location loc,
+  private SkylarkNestedSet(Order order, SkylarkType contentType, Object item, Location loc,
       List<Object> items, List<NestedSet<Object>> transitiveItems) throws EvalException {
 
     // Adding the item
     if (item instanceof SkylarkNestedSet) {
       SkylarkNestedSet nestedSet = (SkylarkNestedSet) item;
       if (!nestedSet.isEmpty()) {
-        genericType = checkType(genericType, nestedSet.genericType, loc);
+        contentType = checkType(contentType, nestedSet.contentType, loc);
         transitiveItems.add((NestedSet<Object>) nestedSet.set);
       }
     } else if (item instanceof SkylarkList) {
       // TODO(bazel-team): we should check ImmutableList here but it screws up genrule at line 43
       for (Object object : (SkylarkList) item) {
-        genericType = checkType(genericType, object.getClass(), loc);
+        contentType = checkType(contentType, SkylarkType.of(object.getClass()), loc);
         items.add(object);
       }
     } else {
       throw new EvalException(loc,
           String.format("cannot add '%s'-s to nested sets", EvalUtils.getDataTypeName(item)));
     }
-    this.genericType = Preconditions.checkNotNull(genericType, "type cannot be null");
+    this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null");
 
     // Initializing the real nested set
     NestedSetBuilder<Object> builder = new NestedSetBuilder<Object>(order);
@@ -116,43 +115,55 @@ public final class SkylarkNestedSet implements Iterable<Object> {
   /**
    * Returns a type safe SkylarkNestedSet. Use this instead of the constructor if possible.
    */
-  public static <T> SkylarkNestedSet of(Class<T> genericType, NestedSet<T> set) {
-    return new SkylarkNestedSet(genericType, set);
+  public static <T> SkylarkNestedSet of(SkylarkType contentType, NestedSet<T> set) {
+    return new SkylarkNestedSet(contentType, set);
+  }
+
+  /**
+   * Returns a type safe SkylarkNestedSet. Use this instead of the constructor if possible.
+   */
+  public static <T> SkylarkNestedSet of(Class<T> contentType, NestedSet<T> set) {
+    return of(SkylarkType.of(contentType), set);
   }
 
   /**
    * A not type safe constructor for SkylarkNestedSet. It's discouraged to use it unless type
    * generic safety is guaranteed from the caller side.
    */
-  SkylarkNestedSet(Class<?> genericType, NestedSet<?> set) {
+  SkylarkNestedSet(SkylarkType contentType, NestedSet<?> set) {
     // This is here for the sake of FuncallExpression.
-    this.genericType = Preconditions.checkNotNull(genericType, "type cannot be null");
+    this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null");
     this.set = Preconditions.checkNotNull(set, "set cannot be null");
     this.items = null;
     this.transitiveItems = null;
   }
 
-  private static Class<?> checkType(Class<?> builderType, Class<?> itemType, Location loc)
+  /**
+   * A not type safe constructor for SkylarkNestedSet, specifying type as a Java class.
+   * It's discouraged to use it unless type generic safety is guaranteed from the caller side.
+   */
+  SkylarkNestedSet(Class<?> contentType, NestedSet<?> set) {
+    this(SkylarkType.of(contentType), set);
+  }
+
+  private static SkylarkType checkType(SkylarkType builderType, SkylarkType itemType, Location loc)
       throws EvalException {
-    if (Map.class.isAssignableFrom(itemType) || SkylarkList.class.isAssignableFrom(itemType)
-        || ClassObject.class.isAssignableFrom(itemType)) {
+    if (SkylarkType.intersection(
+        SkylarkType.Union.of(SkylarkType.MAP, SkylarkType.LIST, SkylarkType.STRUCT),
+        itemType) != SkylarkType.BOTTOM) {
       throw new EvalException(loc, String.format("nested set item is composite (type of %s)",
-          EvalUtils.getDataTypeNameFromClass(itemType)));
+              itemType));
     }
-    if (!EvalUtils.isSkylarkImmutable(itemType)) {
+    if (!EvalUtils.isSkylarkImmutable(itemType.getType())) {
       throw new EvalException(loc, String.format("nested set item is not immutable (type of %s)",
-          EvalUtils.getDataTypeNameFromClass(itemType)));
-    }
-    if (builderType.equals(Object.class)) {
-      return itemType;
+              itemType));
     }
-    if (!EvalUtils.getSkylarkType(builderType).equals(EvalUtils.getSkylarkType(itemType))) {
+    SkylarkType newType = SkylarkType.intersection(builderType, itemType);
+    if (newType == SkylarkType.BOTTOM) {
       throw new EvalException(loc, String.format(
-          "nested set item is type of %s but the nested set accepts only %s-s",
-          EvalUtils.getDataTypeNameFromClass(itemType),
-          EvalUtils.getDataTypeNameFromClass(builderType)));
+          "cannot add an item of type %s to a nested %s", itemType, builderType));
     }
-    return builderType;
+    return newType;
   }
 
   /**
@@ -165,10 +176,10 @@ public final class SkylarkNestedSet implements Iterable<Object> {
     if (set.isEmpty()) {
       return (NestedSet<T>) set;
     }
-    Preconditions.checkArgument(type.isAssignableFrom(genericType),
-        String.format("Expected %s as a type but got %s",
+    Preconditions.checkArgument(contentType.canBeCastTo(type),
+        String.format("Expected a set of %ss but got a set of %ss",
             EvalUtils.getDataTypeNameFromClass(type),
-            EvalUtils.getDataTypeNameFromClass(genericType)));
+            contentType));
     return (NestedSet<T>) set;
   }
 
@@ -188,8 +199,8 @@ public final class SkylarkNestedSet implements Iterable<Object> {
   }
 
   @VisibleForTesting
-  public Class<?> getGenericType() {
-    return genericType;
+  public SkylarkType getContentType() {
+    return contentType;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
index 04c345fc33..2272be68a2 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
@@ -13,7 +13,11 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.common.collect.Interners;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
 
@@ -21,6 +25,9 @@ import java.lang.reflect.Method;
 import java.lang.reflect.ParameterizedType;
 import java.lang.reflect.Type;
 import java.lang.reflect.WildcardType;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -29,162 +36,519 @@ import javax.annotation.Nullable;
 
 /**
  * A class representing types available in Skylark.
+ *
+ * <p>A SkylarkType can be one of:
+ * <ul>
+ * <li>a Simple type that contains exactly the objects in a given class,
+ *  (including the special TOP and BOTTOM types that respectively contain
+ *  all the objects (Simple type for Object.class) and no object at all
+ *  (Simple type for EmptyType.class, isomorphic to Void.class).
+ * <li>a Combination of a generic class (one of LIST, MAP, SET)
+ *  and an argument type (that itself need not be Simple).
+ * <li>a Union of a finite set of types
+ * <li>a FunctionType associated with a name and a returnType
+ *  _that changes during validation_
+ * </ul>
+ *
+ * <p>In a style reminiscent of Java's null, Skylark's None is in all the types
+ *  as far as type inference goes, yet actually no type .contains(it).
+ *
+ * <p>The current implementation fails to distinguish between TOP and ANY,
+ * between BOTTOM and EMPTY (VOID, ZERO, FALSE):
+ * <ul>
+ * <li>In type analysis, we often distinguish a notion of "the type of this object"
+ *  from the notion of "what I know about the type of this object".
+ *  Some languages have a Universal Base Class that contains all objects, and would be the ANY type.
+ *  The Skylark runtime, written in Java, has this ANY type, Java's Object.class.
+ *  But the Skylark validation engine doesn't really have a concept of an ANY class;
+ *  however, it does have a concept of a yet-undermined class, the TOP class
+ *  (called UNKOWN in previous code). In the future, we may have to distinguish between the two,
+ *  at which point type constructor classes would have to be generic in
+ *  "actual type" vs "partial knowledge of type".
+ * <li>Similarly, and EMPTY type (also known as VOID, ZERO or FALSE, in other contexts)
+ *  is a type that has no instance, whereas the BOTTOM type is the type analysis that says
+ *  that there is no possible runtime type for the given object, which may imply that
+ *  the point in the program at which the object is evaluated cannot be reached, etc.
+ * </ul>
+ * So for now, we have puns between TOP and ANY, BOTTOM and EMPTY, between runtime (eval) and
+ * validation-time (validate). Yet in the future, we may need to make a clear distinction,
+ * especially if we are to have types such List(Any) vs List(Top), which contains the former,
+ * but also plenty of other quite distinct types. And yet in a future future, the TOP type
+ * would not be represented explicitly, instead a new type variable would be inserted everywhere
+ * a type is unknown, to be unified with further type information as it becomes available.
  */
-public class SkylarkType {
+// TODO(bazel-team): move the FunctionType side-effect out of the type object
+// and into the validation environment.
+public abstract class SkylarkType {
 
-  private static final class Global {}
+  // The main primitives to override in subclasses
 
-  public static final SkylarkType UNKNOWN = new SkylarkType(Object.class);
-  public static final SkylarkType NONE = new SkylarkType(Environment.NoneType.class);
-  public static final SkylarkType GLOBAL = new SkylarkType(Global.class);
+  /** Is the given value an element of this type? By default, no (empty type) */
+  public boolean contains(Object value) {
+    return false;
+  }
 
-  public static final SkylarkType STRING = new SkylarkType(String.class);
-  public static final SkylarkType INT = new SkylarkType(Integer.class);
-  public static final SkylarkType BOOL = new SkylarkType(Boolean.class);
+  /**
+   * intersectWith() is the internal method from which function intersection(t1, t2) is computed.
+   * OVERRIDE this method in your classes, but DO NOT TO CALL it: only call intersection().
+   * When computing intersection(t1, t2), whichever type defined before the other
+   * knows nothing about the other and about their intersection, and returns BOTTOM;
+   * the other knows about the former, and returns their intersection (which may be BOTTOM).
+   * intersection() will call in one order then the other, and return whichever answer
+   * isn't BOTTOM, if any. By default, types are disjoint and their intersection is BOTTOM.
+   */
+  // TODO(bazel-team): should we define and use an Exception instead?
+  protected SkylarkType intersectWith(SkylarkType other) {
+    return BOTTOM;
+  }
 
-  private final Class<?> type;
+  /** @return true if any object of this SkylarkType can be cast to that Java class */
+  public boolean canBeCastTo(Class<?> type) {
+    return Simple.of(type).includes(this);
+  }
 
-  // TODO(bazel-team): Change this to SkylarkType and check generics of generics etc.
-  // Object.class is used for UNKNOWN.
-  private Class<?> generic1;
+  /** @return true if some non-null objects of that Java class can be cast to this SkylarkType
+   * Note that this is much weaker than an .includes() predicate.
+   */
+  public boolean canBeCastFrom(Class<?> type) {
+    return this.getType().isAssignableFrom(type);
+  }
 
-  public static SkylarkType of(Class<?> type, Class<?> generic1) {
-    return new SkylarkType(type, generic1);
+  /** @return the smallest java Class known to contain all elements of this type */
+  // Note: most user-code should be using a variant that throws an Exception
+  // if the result is Object.class but the type isn't TOP.
+  public Class<?> getType() {
+    return Object.class;
   }
 
-  public static SkylarkType of(Class<?> type) {
-    if (type.equals(Object.class)) {
-      return SkylarkType.UNKNOWN;
-    } else if (type.equals(String.class)) {
-      return SkylarkType.STRING;
-    } else if (type.equals(Integer.class)) {
-      return SkylarkType.INT;
-    } else if (type.equals(Boolean.class)) {
-      return SkylarkType.BOOL;
+  // The actual intersection function for users to use
+
+  public static SkylarkType intersection(SkylarkType t1, SkylarkType t2) {
+    if (t1.equals(t2)) {
+      return t1;
+    }
+    SkylarkType t = t1.intersectWith(t2);
+    if (t == BOTTOM) {
+      return t2.intersectWith(t1);
+    } else {
+      return t;
     }
-    return new SkylarkType(type);
   }
 
-  private SkylarkType(Class<?> type, Class<?> generic1) {
-    this.type = Preconditions.checkNotNull(type);
-    this.generic1 = Preconditions.checkNotNull(generic1);
+  public boolean includes(SkylarkType other) {
+    return intersection(this, other) == other;
   }
 
-  private SkylarkType(Class<?> type) {
-    this.type = Preconditions.checkNotNull(type);
-    this.generic1 = Object.class;
+  public boolean includes(Class<?> other) {
+    return includes(Simple.of(other));
   }
 
-  public Class<?> getType() {
-    return type;
+  public SkylarkType getArgType() {
+    return TOP;
   }
 
-  Class<?> getGenericType1() {
-    return generic1;
-  }
+  private final class Empty { }; // Empty type, used as basis for Bottom
+
+  private static Map<Class<?>, Simple> simpleCache = // cache used by Simple
+      new HashMap<Class<?>, Simple>();
+
+  // Notable types
+
+  /** A singleton for the TOP type, that at analysis time means that any type is possible. */
+  public static final Top TOP = new Top();
+
+  /** UNKNOWN, an alias for the TOP type, for backward compatibility */
+  public static final Top UNKNOWN = TOP;
 
+  /** A singleton for the ANY type, that at run time means that any object is possible. */
+  // NB: right now, it has the same representation as TOP or UNKNOWN,
+  // but means something subtly different.
+  public static final SkylarkType ANY = Simple.of(Object.class);
+
+  /** A singleton for the BOTTOM type, that contains no element */
+  public static final Bottom BOTTOM = new Bottom();
+
+  /** NONE, the Unit type, isomorphic to Void, except its unique element prints as None */
+  // Note that we currently consider at validation time that None is in every type,
+  // by declaring its type as TOP instead of NONE, even though at runtime,
+  // we reject None from all types but NONE, and in particular from e.g. lists of Files.
+  // TODO(bazel-team): resolve this inconsistency, one way or the other.
+  public static final Simple NONE = Simple.of(Environment.NoneType.class);
+
+  private static final class Global {}
   /**
-   * Returns the stronger type of this and o if they are compatible. Stronger means that
-   * the more information is available, e.g. STRING is stronger than UNKNOWN and
-   * LIST&lt;STRING> is stronger than LIST&lt;UNKNOWN>. Note than there's no type
-   * hierarchy in Skylark.
-   * <p>If they are not compatible an EvalException is thrown.
+   * placeholder type for the namespace that global methods are relative to,
+   * used in the validation environment only.
    */
-  SkylarkType infer(SkylarkType o, String name, Location thisLoc, Location originalLoc)
-      throws EvalException {
-    if (this == o) {
-      return this;
+  public static final Simple GLOBAL = Simple.of(Global.class);
+
+  /** The STRING type, for strings */
+  public static final Simple STRING = Simple.of(String.class);
+
+  /** The INTEGER type, for 32-bit signed integers */
+  public static final Simple INT = Simple.of(Integer.class);
+
+  /** The BOOLEAN type, that contains TRUE and FALSE */
+  public static final Simple BOOL = Simple.of(Boolean.class);
+
+  /** The STRUCT type, for all Struct's */
+  public static final Simple STRUCT = Simple.of(ClassObject.class);
+
+  /** The FUNCTION type, that contains all functions, otherwise dynamically typed at call-time */
+  public static final SkylarkFunctionType FUNCTION = new SkylarkFunctionType("unknown", TOP);
+
+  /** The MAP type, that contains all Map's, and the generic combinator for maps */
+  public static final Simple MAP = Simple.of(Map.class);
+
+  /** The LIST type, that contains all SkylarkList's, and the generic combinator for them */
+  public static final Simple LIST = Simple.of(SkylarkList.class);
+
+  /** The STRING_LIST type, a SkylarkList of strings */
+  public static final SkylarkType STRING_LIST = Combination.of(LIST, STRING);
+
+  /** The INT_LIST type, a SkylarkList of integers */
+  public static final SkylarkType INT_LIST = Combination.of(LIST, INT);
+
+  /** The SET type, that contains all SkylarkList's, and the generic combinator for them */
+  public static final Simple SET = Simple.of(SkylarkNestedSet.class);
+
+
+  // Common subclasses of SkylarkType
+
+  /** the Top type contains all objects */
+  private static class Top extends Simple {
+    private Top() {
+      super(Object.class);
     }
-    if (this == UNKNOWN || this.equals(SkylarkType.NONE)) {
-      return o;
+
+    @Override public boolean contains(Object value) {
+      return true;
     }
-    if (o == UNKNOWN || o.equals(SkylarkType.NONE)) {
-      return this;
+    @Override public SkylarkType intersectWith(SkylarkType other) {
+      return other;
     }
-    if (!type.equals(o.type)) {
-      throw new EvalException(thisLoc, String.format("bad %s: %s is incompatible with %s at %s",
-          name,
-          EvalUtils.getDataTypeNameFromClass(o.getType()),
-          EvalUtils.getDataTypeNameFromClass(this.getType()),
-          originalLoc));
+    @Override public String toString() {
+      return "Object";
     }
-    if (generic1.equals(Object.class)) {
-      return o;
+  }
+
+  /** the Bottom type contains no element */
+  private static class Bottom extends Simple {
+    private Bottom() {
+      super(Empty.class);
     }
-    if (o.generic1.equals(Object.class)) {
+
+    @Override public SkylarkType intersectWith(SkylarkType other) {
       return this;
     }
-    if (!generic1.equals(o.generic1)) {
-      throw new EvalException(thisLoc, String.format("bad %s: incompatible generic variable types "
-          + "%s with %s",
-          name,
-          EvalUtils.getDataTypeNameFromClass(o.generic1),
-          EvalUtils.getDataTypeNameFromClass(this.generic1)));
+    @Override public String toString() {
+      return "EmptyType";
     }
-    return this;
   }
 
-  boolean isStruct() {
-    return type.equals(ClassObject.class);
-  }
+  /** a Simple type contains the instance of a Java class */
+  public static class Simple extends SkylarkType {
+    private final Class<?> type;
 
-  boolean isList() {
-    return SkylarkList.class.isAssignableFrom(type);
-  }
+    public Simple(Class<?> type) {
+      this.type = type;
+    }
 
-  boolean isDict() {
-    return Map.class.isAssignableFrom(type);
+    @Override public boolean contains(Object value) {
+      return type.isAssignableFrom(value.getClass());
+    }
+    @Override public Class<?> getType() {
+      return type;
+    }
+    @Override public boolean equals(Object other) {
+      return this == other
+          || (this.getClass() == other.getClass() && this.type.equals(((Simple) other).getType()));
+    }
+    @Override public int hashCode() {
+      return 0x513973 + type.hashCode() * 503; // equal underlying types yield the same hashCode
+    }
+    @Override public String toString() {
+      return EvalUtils.getDataTypeNameFromClass(type);
+    }
+    @Override public boolean canBeCastTo(Class<?> type) {
+      return this.type == type || super.canBeCastTo(type);
+    }
+    public static Simple of(Class<?> type) {
+      Simple cached = simpleCache.get(type);
+      if (cached != null) {
+        return cached;
+      }
+      Simple simple;
+      if (type == Object.class) {
+        // Note that this is a bad encoding for "anything", not for "everything", i.e.
+        // for skylark there isn't a type that contains everything, but there's a Top type
+        // that corresponds to not knowing yet which more special type it will be.
+        simple = TOP;
+      } else if (type == Empty.class) {
+        simple = BOTTOM;
+      } else if (type == Environment.NoneType.class) {
+        // For the purpose of validation-time type inference, treat NONE as being of type TOP,
+        // i.e. None like null in Java is in every type.
+        // TODO(bazel-team): Should we have .contains also always return true for NONE?
+        simple = TOP;
+      } else if (ClassObject.class != type && ClassObject.class.isAssignableFrom(type)) {
+        simple = of(ClassObject.class);
+      } else {
+        simple = new Simple(type);
+      }
+      simpleCache.put(type, simple);
+      return simple;
+    }
   }
 
-  boolean isSet() {
-    return Set.class.isAssignableFrom(type);
-  }
+  /** Combination of a generic type and an argument type */
+  public static class Combination extends SkylarkType {
+    // For the moment, we can only combine a Simple type with a Simple type,
+    // and the first one has to be a Java generic class,
+    // and in practice actually one of SkylarkList or SkylarkNestedSet
+    private final SkylarkType genericType; // actually always a Simple, for now.
+    private final SkylarkType argType; // not always Simple
+    public Combination(SkylarkType genericType, SkylarkType argType) {
+      this.genericType = genericType;
+      this.argType = argType;
+    }
 
-  boolean isNset() {
-    // TODO(bazel-team): NestedSets are going to be a bit strange with 2 type info (validation
-    // and execution time). That can be cleaned up once we have complete type inference.
-    return SkylarkNestedSet.class.isAssignableFrom(type);
-  }
+    public boolean contains(Object value) {
+      // The empty collection is member of compatible types
+      if (!genericType.contains(value)) {
+        return false;
+      } else {
+        SkylarkType valueArgType = getGenericArgType(value);
+        return valueArgType == TOP // empty objects are universal
+            || argType.includes(valueArgType);
+      }
+    }
+    @Override public SkylarkType intersectWith(SkylarkType other) {
+      // For now, we only accept generics with a single covariant parameter
+      if (genericType.equals(other)) {
+        return this;
+      } else if (other instanceof Combination
+          && genericType.equals(((Combination) other).getGenericType())
+          && argType.includes(((Combination) other).getArgType())) {
+        return other;
+      } else if ((LIST.equals(other) || SET.equals(other)) && genericType.equals(other)) {
+        return this;
+      } else {
+        return BOTTOM;
+      }
+    }
 
-  boolean isSimple() {
-    return !isStruct() && !isDict() && !isList() && !isNset() && !isSet();
-  }
+    @Override public boolean equals(Object other) {
+      if (this == other) {
+        return true;
+      } else if (this.getClass() == other.getClass()) {
+        Combination o = (Combination) other;
+        return genericType.equals(o.getGenericType())
+            && argType.equals(o.getArgType());
+      } else {
+        return false;
+      }
+    }
+    @Override public int hashCode() {
+      // equal underlying types yield the same hashCode
+      return 0x20B14A71 + genericType.hashCode() * 1009 + argType.hashCode() * 1013;
+    }
+    @Override public Class<?> getType() {
+      return genericType.getType();
+    }
+    SkylarkType getGenericType() {
+      return genericType;
+    }
+    @Override
+    public SkylarkType getArgType() {
+      return argType;
+    }
+    @Override public String toString() {
+      return genericType.toString() + " of " + argType.toString() + "s";
+    }
+
+    private static Interner<Combination> combinationInterner =
+        Interners.<Combination>newWeakInterner();
 
-  @Override
-  public String toString() {
-    return this == UNKNOWN ? "Unknown" : EvalUtils.getDataTypeNameFromClass(type);
+    public static SkylarkType of(SkylarkType generic, SkylarkType argument) {
+      // assume all combinations with TOP are the same as the simple type, and canonicalize.
+      Preconditions.checkArgument(generic instanceof Simple);
+      if (argument == TOP) {
+        return generic;
+      } else {
+        return combinationInterner.intern(new Combination(generic, argument));
+      }
+    }
+    public static SkylarkType of(Class<?> generic, Class<?> argument) {
+      return of(Simple.of(generic), Simple.of(argument));
+    }
   }
 
-  // hashCode() and equals() only uses the type field
+  /** Union types, used a lot in "dynamic" languages such as Python or Skylark */
+  public static class Union extends SkylarkType {
+    private final ImmutableList<SkylarkType> types;
+    private Union(ImmutableList<SkylarkType> types) {
+      this.types = types;
+    }
 
-  @Override
-  public boolean equals(Object other) {
-    if (this == other) {
-      return true;
+    public boolean contains(Object value) {
+      for (SkylarkType type : types) {
+        if (type.contains(value)) {
+          return true;
+        }
+      }
+      return false;
     }
-    if (!(other instanceof SkylarkType)) {
+    @Override public boolean equals(Object other) {
+      if (this.getClass() == other.getClass()) {
+        Union o = (Union) other;
+        if (types.containsAll(o.types) && o.types.containsAll(types)) {
+          return true;
+        }
+      }
       return false;
     }
-    SkylarkType o = (SkylarkType) other;
-    return this.type.equals(o.type);
+    @Override public int hashCode() {
+      // equal underlying types yield the same hashCode
+      int h = 0x4104;
+      for (SkylarkType type : types) {
+        // Important: addition is commutative, like Union
+        h += type.hashCode();
+      }
+      return h;
+    }
+    @Override public String toString() {
+      return Joiner.on(" or ").join(types);
+    }
+    public static List<SkylarkType> addElements(List<SkylarkType> list, SkylarkType type) {
+      if (type instanceof Union) {
+        list.addAll(((Union) type).types);
+      } else if (type != BOTTOM) {
+        list.add(type);
+      }
+      return list;
+    }
+    @Override public SkylarkType intersectWith(SkylarkType other) {
+      List<SkylarkType> otherTypes = addElements(new ArrayList<SkylarkType>(), other);
+      List<SkylarkType> results = new ArrayList<>();
+      for (SkylarkType element : types) {
+        for (SkylarkType otherElement : otherTypes) {
+          addElements(results, intersection(element, otherElement));
+        }
+      }
+      return Union.of(results);
+    }
+    public static SkylarkType of(List<SkylarkType> types) {
+      // When making the union of many types,
+      // canonicalize them into elementary (non-Union) types,
+      // and then eliminate trivially redundant types from the list.
+
+      // list of all types in the input
+      ArrayList<SkylarkType> elements = new ArrayList<>();
+      for (SkylarkType type : types) {
+        addElements(elements, type);
+      }
+
+      // canonicalized list of types
+      ArrayList<SkylarkType> canonical = new ArrayList<>();
+
+      for (SkylarkType newType : elements) {
+        boolean done = false; // done with this element?
+        int i = 0;
+        for (SkylarkType existingType : canonical) {
+          SkylarkType both = intersection(newType, existingType);
+          if (newType.equals(both)) { // newType already included
+            done = true;
+            break;
+          } else if (existingType.equals(both)) { // newType supertype of existingType
+            canonical.set(i, newType);
+            done = true;
+            break;
+          }
+        }
+        if (!done) {
+          canonical.add(newType);
+        }
+      }
+      if (canonical.isEmpty()) {
+        return BOTTOM;
+      } else if (canonical.size() == 1) {
+        return canonical.get(0);
+      } else {
+        return new Union(ImmutableList.<SkylarkType>copyOf(canonical));
+      }
+    }
+    public static SkylarkType of(SkylarkType... types) {
+      return of(Arrays.asList(types));
+    }
+    public static SkylarkType of(SkylarkType t1, SkylarkType t2) {
+      return of(ImmutableList.<SkylarkType>of(t1, t2));
+    }
+    public static SkylarkType of(Class<?> t1, Class<?> t2) {
+      return of(Simple.of(t1), Simple.of(t2));
+    }
   }
 
-  @Override
-  public int hashCode() {
-    return type.hashCode();
+  public static SkylarkType of(Class<?> type) {
+    if (SkylarkList.class.isAssignableFrom(type)) {
+      return LIST;
+    } else if (SkylarkNestedSet.class.isAssignableFrom(type)) {
+      return SET;
+    } else {
+      return Simple.of(type);
+    }
+  }
+
+  public static SkylarkType of(SkylarkType t1, SkylarkType t2) {
+    return Combination.of(t1, t2);
   }
+  public static SkylarkType of(Class<?> t1, Class<?> t2) {
+    return Combination.of(t1, t2);
+  }
+
 
   /**
    * A class representing the type of a Skylark function.
    */
+  // TODO(bazel-team): move the side-effect out of the type object, into the validation environment?
   public static final class SkylarkFunctionType extends SkylarkType {
-
     private final String name;
     @Nullable private SkylarkType returnType;
     @Nullable private Location returnTypeLoc;
 
+    @Override public SkylarkType intersectWith(SkylarkType other) {
+      // This gives the wrong result if both return types are incompatibly updated later!
+      if (other instanceof SkylarkFunctionType) {
+        SkylarkFunctionType fun = (SkylarkFunctionType) other;
+        SkylarkType type1 = returnType == null ? TOP : returnType;
+        SkylarkType type2 = fun.returnType == null ? TOP : fun.returnType;
+        SkylarkType bothReturnType = intersection(returnType, fun.returnType);
+        if (type1.equals(bothReturnType)) {
+          return this;
+        } else if (type2.equals(bothReturnType)) {
+          return fun;
+        } else {
+          return new SkylarkFunctionType(name, bothReturnType);
+        }
+      } else {
+        return BOTTOM;
+      }
+    }
+    @Override public Class<?> getType() {
+      return Function.class;
+    }
+    @Override public String toString() {
+      return (returnType == TOP || returnType == null ? "" : returnType + "-returning ")
+          + "function";
+    }
+
+    public boolean contains(Object value) {
+      // This returns true a bit too much, but it looks
+      return Function.class.isAssignableFrom(value.getClass());
+    }
+
     public static SkylarkFunctionType of(String name) {
-      return new SkylarkFunctionType(name, null);
+      return SkylarkFunctionType.of(name, TOP);
     }
 
     public static SkylarkFunctionType of(String name, SkylarkType returnType) {
@@ -192,7 +556,6 @@ public class SkylarkType {
     }
 
     private SkylarkFunctionType(String name, SkylarkType returnType) {
-      super(Function.class);
       this.name = name;
       this.returnType = returnType;
     }
@@ -203,26 +566,98 @@ public class SkylarkType {
 
     /**
      * Sets the return type of the function type if it's compatible with the existing return type.
-     * Note that setting NONE only has an effect if the return type hasn't been set previously.
      */
     public void setReturnType(SkylarkType newReturnType, Location newLoc) throws EvalException {
       if (returnType == null) {
         returnType = newReturnType;
         returnTypeLoc = newLoc;
       } else if (newReturnType != SkylarkType.NONE) {
-        returnType =
+        // At validation-time, we allow NONE in any type, just like null in Java.
+        SkylarkType intersectionType =
             returnType.infer(newReturnType, "return type of " + name, newLoc, returnTypeLoc);
-        if (returnType == newReturnType) {
+        if (!returnType.equals(intersectionType)) {
+          returnType = intersectionType;
           returnTypeLoc = newLoc;
         }
       }
     }
   }
 
+
+  // Utility functions regarding types
+
+  /**
+   * Returns the stronger type of this and o if they are compatible. Stronger means that
+   * the more information is available, e.g. STRING is stronger than UNKNOWN and
+   * LIST&lt;STRING> is stronger than LIST&lt;UNKNOWN>.
+   *
+   * <p>If they are not compatible an EvalException is thrown.
+   */
+  SkylarkType infer(SkylarkType o, String name, Location thisLoc, Location originalLoc)
+      throws EvalException {
+    SkylarkType both = intersection(this, o);
+    if (both == BOTTOM) {
+      throw new EvalException(thisLoc, String.format("bad %s: %s is incompatible with %s at %s",
+              name, o, this, originalLoc));
+    } else {
+      return both;
+    }
+  }
+
+  public static SkylarkType typeOf(Object value) {
+    if (value == null) {
+      return BOTTOM;
+    } else if (value instanceof SkylarkList) {
+      return of(LIST, ((SkylarkList) value).getContentType());
+    } else if (value instanceof SkylarkNestedSet) {
+      return of(SET, ((SkylarkNestedSet) value).getContentType());
+    } else if (value instanceof ClassObject) {
+      return STRUCT;
+    } else {
+      return Simple.of(value.getClass());
+    }
+  }
+
+  public static SkylarkType getGenericArgType(Object value) {
+    if (value instanceof SkylarkList) {
+      return ((SkylarkList) value).getContentType();
+    } else if (value instanceof SkylarkNestedSet) {
+      return ((SkylarkNestedSet) value).getContentType();
+    } else {
+      return TOP;
+    }
+  }
+
+  boolean isStruct() {
+    return ClassObject.class.isAssignableFrom(getType());
+  }
+
+  boolean isList() {
+    return SkylarkList.class.isAssignableFrom(getType());
+  }
+
+  boolean isDict() {
+    return Map.class.isAssignableFrom(getType());
+  }
+
+  boolean isSet() {
+    return Set.class.isAssignableFrom(getType());
+  }
+
+  boolean isNset() {
+    // TODO(bazel-team): NestedSets are going to be a bit strange with 2 type info (validation
+    // and execution time). That can be cleaned up once we have complete type inference.
+    return SkylarkNestedSet.class.isAssignableFrom(getType());
+  }
+
+  boolean isSimple() {
+    return !isStruct() && !isDict() && !isList() && !isNset() && !isSet();
+  }
+
   private static boolean isTypeAllowedInSkylark(Object object) {
     if (object instanceof NestedSet<?>) {
       return false;
-    } else if (object instanceof List<?>) {
+    } else if (object instanceof List<?> && !(object instanceof SkylarkList)) {
       return false;
     }
     return true;
@@ -239,6 +674,44 @@ public class SkylarkType {
     }
   }
 
+  /**
+   * General purpose type-casting facility.
+   *
+   * @param value - the actual value of the parameter
+   * @param type - the expected Class for the value
+   * @param loc - the location info used in the EvalException
+   * @param format - a format String
+   * @param args - arguments to format, in case there's an exception
+   */
+  public static <T> T cast(Object value, Class<T> type,
+      Location loc, String format, Object... args) throws EvalException {
+    try {
+      return type.cast(value);
+    } catch (ClassCastException e) {
+      throw new EvalException(loc, String.format(format, args));
+    }
+  }
+
+  /**
+   * General purpose type-casting facility.
+   *
+   * @param value - the actual value of the parameter
+   * @param genericType - a generic class of one argument for the value
+   * @param argType - a covariant argument for the generic class
+   * @param loc - the location info used in the EvalException
+   * @param format - a format String
+   * @param args - arguments to format, in case there's an exception
+   */
+  @SuppressWarnings("unchecked")
+  public static <T> T cast(Object value, Class<T> genericType, Class<?> argType,
+      Location loc, String format, Object... args) throws EvalException {
+    if (of(genericType, argType).contains(value)) {
+      return (T) value;
+    } else {
+      throw new EvalException(loc, String.format(format, args));
+    }
+  }
+
   private static Class<?> getGenericTypeFromMethod(Method method) {
     // This is where we can infer generic type information, so SkylarkNestedSets can be
     // created in a safe way. Eventually we should probably do something with Lists and Maps too.
@@ -296,12 +769,10 @@ public class SkylarkType {
    * Creates a SkylarkType from the SkylarkBuiltin annotation.
    */
   public static SkylarkType getReturnType(SkylarkBuiltin annotation) {
-    if (annotation.returnType().equals(Object.class)) {
-      return SkylarkType.UNKNOWN;
-    }
     if (Function.class.isAssignableFrom(annotation.returnType())) {
       return SkylarkFunctionType.of(annotation.name());
+    } else {
+      return Simple.of(annotation.returnType());
     }
-    return SkylarkType.of(annotation.returnType());
   }
 }