diff --git a/src/main/java/com/google/devtools/build/lib/packages/Type.java b/src/main/java/com/google/devtools/build/lib/packages/Type.java
index 778019c..f240876 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Type.java
@@ -35,6 +35,7 @@
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.RandomAccess;
 import java.util.Set;
 import java.util.logging.Level;
 import javax.annotation.Nullable;
@@ -467,9 +468,11 @@
 
     @Override
     public <T> void visitLabels(LabelVisitor<T> visitor, Object value, T context) {
-      for (Map.Entry<KeyT, ValueT> entry : cast(value).entrySet()) {
-        keyType.visitLabels(visitor, entry.getKey(), context);
-        valueType.visitLabels(visitor, entry.getValue(), context);
+      if (labelClass != LabelClass.NONE) {
+        for (Map.Entry<KeyT, ValueT> entry : cast(value).entrySet()) {
+          keyType.visitLabels(visitor, entry.getKey(), context);
+          valueType.visitLabels(visitor, entry.getValue(), context);
+        }
       }
     }
 
@@ -585,9 +588,13 @@
 
     @Override
     public <T> void visitLabels(LabelVisitor<T> visitor, Object value, T context) {
+      if (elemType.getLabelClass() == LabelClass.NONE) {
+        return;
+      }
+
       List<ElemT> elems = cast(value);
       // Hot code path. Optimize for lists with O(1) access to avoid iterator garbage.
-      if (elems instanceof ImmutableList || elems instanceof ArrayList) {
+      if (elems instanceof RandomAccess) {
         for (int i = 0; i < elems.size(); i++) {
           elemType.visitLabels(visitor, elems.get(i), context);
         }