diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
index 3c87b27..2097997 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTest.java
@@ -441,7 +441,7 @@
         "  ctx.action(outputs = [f], command = 'echo foo > \"$1\"')",
         "  return struct(output=f)",
         "def _rule_impl(ctx):",
-        "  return struct(files=set([artifact.output for artifact in ctx.attr.deps]))",
+        "  return struct(files=depset([artifact.output for artifact in ctx.attr.deps]))",
         "aspect1 = aspect(_aspect_impl, attr_aspects=['deps'], ",
         "    attrs = {'parameter': attr.string(values = ['param_value'])})",
         "testrule = rule(_rule_impl, attrs = { ",
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
index c4d0f88..dbe7efa 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
@@ -180,8 +180,8 @@
     scratch.file(
         "test/aspect.bzl",
         "def _impl(target, ctx):",
-        "   s = set([target.label])",
-        "   c = set([ctx.rule.kind])",
+        "   s = depset([target.label])",
+        "   c = depset([ctx.rule.kind])",
         "   for i in ctx.rule.attr.deps:",
         "       s += i.target_labels",
         "       c += i.rule_kinds",
@@ -233,8 +233,8 @@
     scratch.file(
         "test/aspect.bzl",
         "def _impl(target, ctx):",
-        "   s = set([target.label])",
-        "   c = set([ctx.rule.kind])",
+        "   s = depset([target.label])",
+        "   c = depset([ctx.rule.kind])",
         "   a = ctx.rule.attr",
         "   if hasattr(a, '_stl') and a._stl:",
         "       s += a._stl.target_labels",
@@ -368,13 +368,13 @@
     scratch.file(
         "test/aspect.bzl",
         "def _aspect_impl(target, ctx):",
-        "   s = set([target.label])",
+        "   s = depset([target.label])",
         "   for i in ctx.rule.attr.deps:",
         "       s += i.target_labels",
         "   return struct(target_labels = s)",
         "",
         "def _rule_impl(ctx):",
-        "   s = set([])",
+        "   s = depset([])",
         "   for i in ctx.attr.attr:",
         "       s += i.target_labels",
         "   return struct(rule_deps = s)",
@@ -629,18 +629,17 @@
         "def _impl(target, ctx):",
         "  f = ctx.new_file('f.txt')",
         "  ctx.file_action(f, 'f')",
-        "  return struct(output_groups = { 'duplicate' : set([f]) })",
+        "  return struct(output_groups = { 'duplicate' : depset([f]) })",
         "",
         "MyAspect = aspect(implementation=_impl)",
         "def _rule_impl(ctx):",
         "  g = ctx.new_file('g.txt')",
         "  ctx.file_action(g, 'g')",
-        "  return struct(output_groups = { 'duplicate' : set([g]) })",
+        "  return struct(output_groups = { 'duplicate' : depset([g]) })",
         "my_rule = rule(_rule_impl)",
         "def _noop(ctx):",
         "  pass",
-        "rbase = rule(_noop, attrs = { 'dep' : attr.label(aspects = [MyAspect]) })"
-    );
+        "rbase = rule(_noop, attrs = { 'dep' : attr.label(aspects = [MyAspect]) })");
     scratch.file(
         "test/BUILD",
         "load(':aspect.bzl', 'my_rule', 'rbase')",
@@ -666,7 +665,7 @@
         "def _a1_impl(target, ctx):",
         "  f = ctx.new_file(target.label.name + '_a1.txt')",
         "  ctx.file_action(f, 'f')",
-        "  return struct(output_groups = { 'a1_group' : set([f]) })",
+        "  return struct(output_groups = { 'a1_group' : depset([f]) })",
         "",
         "a1 = aspect(implementation=_a1_impl, attr_aspects = ['dep'])",
         "def _rule_impl(ctx):",
@@ -678,11 +677,10 @@
         "def _a2_impl(target, ctx):",
         "  g = ctx.new_file(target.label.name + '_a2.txt')",
         "  ctx.file_action(g, 'f')",
-        "  return struct(output_groups = { 'a2_group' : set([g]) })",
+        "  return struct(output_groups = { 'a2_group' : depset([g]) })",
         "",
         "a2 = aspect(implementation=_a2_impl, attr_aspects = ['dep'])",
-        "my_rule2 = rule(_rule_impl, attrs = { 'dep' : attr.label(aspects = [a2]) })"
-        );
+        "my_rule2 = rule(_rule_impl, attrs = { 'dep' : attr.label(aspects = [a2]) })");
     scratch.file(
         "test/BUILD",
         "load(':aspect.bzl', 'my_rule1', 'my_rule2')",
@@ -710,7 +708,7 @@
         "def _a1_impl(target, ctx):",
         "  f = ctx.new_file(target.label.name + '_a1.txt')",
         "  ctx.file_action(f, 'f')",
-        "  return struct(output_groups = { 'a1_group' : set([f]) })",
+        "  return struct(output_groups = { 'a1_group' : depset([f]) })",
         "",
         "a1 = aspect(implementation=_a1_impl, attr_aspects = ['dep'])",
         "def _rule_impl(ctx):",
@@ -722,11 +720,10 @@
         "def _a2_impl(target, ctx):",
         "  g = ctx.new_file(target.label.name + '_a2.txt')",
         "  ctx.file_action(g, 'f')",
-        "  return struct(output_groups = { 'a1_group' : set([g]) })",
+        "  return struct(output_groups = { 'a1_group' : depset([g]) })",
         "",
         "a2 = aspect(implementation=_a2_impl, attr_aspects = ['dep'])",
-        "my_rule2 = rule(_rule_impl, attrs = { 'dep' : attr.label(aspects = [a2]) })"
-    );
+        "my_rule2 = rule(_rule_impl, attrs = { 'dep' : attr.label(aspects = [a2]) })");
     scratch.file(
         "test/BUILD",
         "load(':aspect.bzl', 'my_rule1', 'my_rule2')",
@@ -1213,51 +1210,52 @@
 
   private String[] aspectBzlFile(String attrAspects) {
     return new String[] {
-        "def _repro_aspect_impl(target, ctx):",
-        "    s = set([str(target.label)])",
-        "    for d in ctx.rule.attr.deps:",
-        "       if hasattr(d, 'aspect_info'):",
-        "         s = s | d.aspect_info",
-        "    return struct(aspect_info = s)",
-        "",
-        "_repro_aspect = aspect(",
-        "    _repro_aspect_impl,",
-        "    attr_aspects = [" + attrAspects + "],",
-        ")",
-        "",
-        "def repro_impl(ctx):",
-        "    s = set()",
-        "    for d in ctx.attr.deps:",
-        "       if hasattr(d, 'aspect_info'):",
-        "         s = s | d.aspect_info",
-        "    return struct(rule_info = s)",
-        "",
-        "def repro_no_aspect_impl(ctx):",
-        "    pass",
-        "",
-        "repro_no_aspect = rule(implementation = repro_no_aspect_impl,",
-        "             attrs = {",
-        "                       'deps': attr.label_list(",
-        "                             allow_files = True,",
-        "                       )",
-        "                      },",
-        ")",
-        "",
-        "repro = rule(implementation = repro_impl,",
-        "             attrs = {",
-        "                       'deps': attr.label_list(",
-        "                             allow_files = True,",
-        "                             aspects = [_repro_aspect],",
-        "                       )",
-        "                      },",
-        ")"
+      "def _repro_aspect_impl(target, ctx):",
+      "    s = depset([str(target.label)])",
+      "    for d in ctx.rule.attr.deps:",
+      "       if hasattr(d, 'aspect_info'):",
+      "         s = s | d.aspect_info",
+      "    return struct(aspect_info = s)",
+      "",
+      "_repro_aspect = aspect(",
+      "    _repro_aspect_impl,",
+      "    attr_aspects = [" + attrAspects + "],",
+      ")",
+      "",
+      "def repro_impl(ctx):",
+      "    s = depset()",
+      "    for d in ctx.attr.deps:",
+      "       if hasattr(d, 'aspect_info'):",
+      "         s = s | d.aspect_info",
+      "    return struct(rule_info = s)",
+      "",
+      "def repro_no_aspect_impl(ctx):",
+      "    pass",
+      "",
+      "repro_no_aspect = rule(implementation = repro_no_aspect_impl,",
+      "             attrs = {",
+      "                       'deps': attr.label_list(",
+      "                             allow_files = True,",
+      "                       )",
+      "                      },",
+      ")",
+      "",
+      "repro = rule(implementation = repro_impl,",
+      "             attrs = {",
+      "                       'deps': attr.label_list(",
+      "                             allow_files = True,",
+      "                             aspects = [_repro_aspect],",
+      "                       )",
+      "                      },",
+      ")"
     };
   }
 
 
   @Test
   public void aspectOutputsToBinDirectory() throws Exception {
-    scratch.file("foo/extension.bzl",
+    scratch.file(
+        "foo/extension.bzl",
         "def _aspect_impl(target, ctx):",
         "   file = ctx.new_file('aspect-output-' + target.label.name)",
         "   ctx.file_action(file, 'data')",
@@ -1268,14 +1266,13 @@
         "rule_bin_out = rule(_rule_impl, output_to_genfiles=False)",
         "rule_gen_out = rule(_rule_impl, output_to_genfiles=True)",
         "def _main_rule_impl(ctx):",
-        "   s = set()",
+        "   s = depset()",
         "   for d in ctx.attr.deps:",
-        "       s = s | set([d.aspect_file])",
+        "       s = s | depset([d.aspect_file])",
         "   return struct(aspect_files = s)",
         "main_rule = rule(_main_rule_impl,",
         "   attrs = { 'deps' : attr.label_list(aspects = [my_aspect]) },",
-        ")"
-    );
+        ")");
 
     scratch.file("foo/BUILD",
         "load('extension', 'rule_bin_out', 'rule_gen_out', 'main_rule')",
@@ -1413,7 +1410,7 @@
     scratch.file(
         "test/aspect.bzl",
         "def _impl(target, ctx):",
-        "   s = set([target.label])",
+        "   s = depset([target.label])",
         "   if hasattr(ctx.rule.attr, 'runtime_deps'):",
         "     for i in ctx.rule.attr.runtime_deps:",
         "       s += i.target_labels",
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkCommandLineTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkCommandLineTest.java
index cd7a716..7d68bcd 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkCommandLineTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkCommandLineTest.java
@@ -18,7 +18,6 @@
 
 import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
 import com.google.devtools.build.lib.syntax.SkylarkList;
-
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -46,7 +45,7 @@
     Object result =
         evalRuleContextCode(
             createRuleContext("//foo:foo"),
-            "cmd_helper.template(set(ruleContext.files.srcs), '--%{short_path}=%{path}')");
+            "cmd_helper.template(depset(ruleContext.files.srcs), '--%{short_path}=%{path}')");
     SkylarkList list = (SkylarkList) result;
     assertThat(list).containsExactly("--foo/a.txt=foo/a.txt", "--foo/b.img=foo/b.img").inOrder();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
index 9a5dff2..cb94367 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
@@ -236,7 +236,7 @@
         "test/skylark/extension.bzl",
         "def _impl(ctx):",
         "  f = ctx.attr.dep.output_groups['_hidden_top_level" + INTERNAL_SUFFIX + "']",
-        "  g = ctx.attr.dep.output_groups['_hidden_top_level" + INTERNAL_SUFFIX + "'] | set([])",
+        "  g = ctx.attr.dep.output_groups['_hidden_top_level" + INTERNAL_SUFFIX + "'] | depset([])",
         "  return struct(result = g, ",
         "                output_groups = { 'my_group' : g })",
         "my_rule = rule(implementation = _impl,",
@@ -331,7 +331,7 @@
         "load('/test/skylark/functions', 'first')",
         "def custom_rule_impl(ctx):",
         "  attr1 = ctx.files.attr1",
-        "  ftb = set(attr1)",
+        "  ftb = depset(attr1)",
         "  foo()",
         "  return struct(provider_key = ftb)",
         "def foo():",
@@ -365,7 +365,7 @@
         "test/skylark/extension.bzl",
         "def custom_rule_impl(ctx):",
         "  attr1 = ctx.files.attr1",
-        "  ftb = set(attr1)",
+        "  ftb = depset(attr1)",
         "  return struct(runfiles = ctx.runfiles(), files = ftb)",
         "",
         "custom_rule = rule(implementation = custom_rule_impl,",
@@ -602,7 +602,7 @@
         "test/skylark/extension.bzl",
         "def custom_rule_impl(ctx):",
         "  attr1 = ctx.files.attr1",
-        "  ftb = set(attr1)",
+        "  ftb = depset(attr1)",
         "  return struct(provider_key = ftb)",
         "",
         "custom_rule = rule(implementation = custom_rule_impl,",
@@ -688,7 +688,7 @@
         "  ctx.action(",
         "    outputs = files,",
         "    command = 'echo')",
-        "  ftb = set(files)",
+        "  ftb = depset(files)",
         "  return struct(runfiles = ctx.runfiles(), files = ftb)",
         "",
         "def output_func(attr1, attr2):",
@@ -725,7 +725,7 @@
         "  ctx.action(",
         "    outputs = files,",
         "    command = 'echo')",
-        "  return struct(files = set(files))",
+        "  return struct(files = depset(files))",
         "",
         "custom_rule = rule(implementation = custom_rule_impl,",
         "  attrs = {",
@@ -844,7 +844,7 @@
         "  ctx.action(",
         "    outputs = files,",
         "    command = 'echo')",
-        "  ftb = set(files)",
+        "  ftb = depset(files)",
         "  for i in ctx.outputs.out:",
         "    ctx.file_action(output=i, content='hi there')",
         "",
@@ -936,7 +936,7 @@
     scratch.file(
         "test/skylark/extension.bzl",
         "def _impl(ctx):",
-        "  return struct(bad=set([set([])]))",
+        "  return struct(bad=depset([depset([])]))",
         "my_rule = rule(implementation = _impl)");
     scratch.file(
         "test/skylark/BUILD",
@@ -944,7 +944,7 @@
         "my_rule(name = 'r')");
 
     getConfiguredTarget("//test/skylark:r");
-    assertContainsEvent("Value of provider 'bad' is of an illegal type: set\n");
+    assertContainsEvent("Value of provider 'bad' is of an illegal type: depset\n");
   }
 
   @Test
@@ -1006,7 +1006,7 @@
     scratch.file(
         "test/skylark/extension.bzl",
         "def helper_func(attr1):",
-        "  return set(attr1)",
+        "  return depset(attr1)",
         "",
         "def custom_rule_impl(ctx):",
         "  attr1 = ctx.files.attr1",
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
index 066c544..69783f2 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
@@ -943,7 +943,7 @@
 
   @Test
   public void testStructsInSets() throws Exception {
-    eval("set([struct(a='a')])");
+    eval("depset([struct(a='a')])");
   }
 
   @Test
@@ -977,9 +977,7 @@
 
   @Test
   public void testNsetGoodCompositeItem() throws Exception {
-    eval("def func():",
-        "  return set([struct(a='a')])",
-        "s = func()");
+    eval("def func():", "  return depset([struct(a='a')])", "s = func()");
     Collection<Object> result = ((SkylarkNestedSet) lookup("s")).toCollection();
     assertThat(result).hasSize(1);
     assertThat(result.iterator().next()).isInstanceOf(SkylarkClassObject.class);
@@ -987,8 +985,8 @@
 
   @Test
   public void testNsetBadMutableItem() throws Exception {
-    checkEvalError("sets cannot contain mutable items", "set([([],)])");
-    checkEvalError("sets cannot contain mutable items", "set([struct(a=[])])");
+    checkEvalError("depsets cannot contain mutable items", "depset([([],)])");
+    checkEvalError("depsets cannot contain mutable items", "depset([struct(a=[])])");
   }
 
   private static SkylarkClassObject makeStruct(String field, Object value) {
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
index 802142f..e8a3675 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
@@ -229,7 +229,7 @@
   @SuppressWarnings("unchecked")
   @Test
   public void testListComprehensionsWithNestedSet() throws Exception {
-    Object result = eval("[x + x for x in set([1, 2, 3])]");
+    Object result = eval("[x + x for x in depset([1, 2, 3])]");
     assertThat((Iterable<Object>) result).containsExactly(2, 4, 6).inOrder();
   }
 
@@ -675,9 +675,9 @@
   @Test
   public void testRunfilesBadSetGenericType() throws Exception {
     checkErrorContains(
-        "expected set of Files or NoneType for 'transitive_files' while calling runfiles "
-            + "but got set of ints instead: set([1, 2, 3])",
-        "ruleContext.runfiles(transitive_files=set([1, 2, 3]))");
+        "expected depset of Files or NoneType for 'transitive_files' while calling runfiles "
+            + "but got depset of ints instead: depset([1, 2, 3])",
+        "ruleContext.runfiles(transitive_files=depset([1, 2, 3]))");
   }
 
   @Test
@@ -728,7 +728,7 @@
     Object result =
         evalRuleContextCode(
             ruleContext,
-            "ftb = set() + ruleContext.files.srcs",
+            "ftb = depset() + ruleContext.files.srcs",
             "ruleContext.runfiles(transitive_files = ftb)");
     assertEquals(
         ActionsTestUtil.baseArtifactNames(getRunfileArtifacts(result)),
@@ -803,7 +803,7 @@
   @Test
   public void testNsetContainsList() throws Exception {
     checkErrorContains(
-        "sets cannot contain items of type 'list'", "set() + [ruleContext.files.srcs]");
+        "depsets cannot contain items of type 'list'", "depset() + [ruleContext.files.srcs]");
   }
 
   @Test
@@ -811,7 +811,7 @@
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     Object result =
         evalRuleContextCode(
-            ruleContext, "f = set(ruleContext.files.srcs)", "cmd_helper.join_paths(':', f)");
+            ruleContext, "f = depset(ruleContext.files.srcs)", "cmd_helper.join_paths(':', f)");
     assertEquals("foo/a.txt:foo/b.img", result);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
index dfe9a0c..debcaf0 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
@@ -232,7 +232,7 @@
 
   @Test
   public void testSetComparison() throws Exception {
-    newTest().testIfExactError("Cannot compare sets", "set([1, 2]) < set([3, 4])");
+    newTest().testIfExactError("Cannot compare depsets", "depset([1, 2]) < depset([3, 4])");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
index 5c90866..5fc8aae 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
@@ -71,7 +71,9 @@
 
   @Test
   public void testMinWithSet() throws Exception {
-    new BothModesTest().testStatement("min(set([-1]))", -1).testStatement("min(set([5, 2, 3]))", 2);
+    new BothModesTest()
+        .testStatement("min(depset([-1]))", -1)
+        .testStatement("min(depset([5, 2, 3]))", 2);
   }
 
   @Test
@@ -123,7 +125,9 @@
 
   @Test
   public void testMaxWithSet() throws Exception {
-    new BothModesTest().testStatement("max(set([-1]))", -1).testStatement("max(set([5, 2, 3]))", 5);
+    new BothModesTest()
+        .testStatement("max(depset([-1]))", -1)
+        .testStatement("max(depset([5, 2, 3]))", 5);
   }
 
   @Test
@@ -295,9 +299,9 @@
   @Test
   public void testAllWithSet() throws Exception {
     new BothModesTest()
-        .testStatement("all(set([0]))", false)
-        .testStatement("all(set([1, 0]))", false)
-        .testStatement("all(set([1]))", true);
+        .testStatement("all(depset([0]))", false)
+        .testStatement("all(depset([1, 0]))", false)
+        .testStatement("all(depset([1]))", true);
   }
 
   @Test
@@ -336,8 +340,8 @@
   @Test
   public void testAnyWithSet() throws Exception {
     new BothModesTest()
-        .testStatement("any(set([0]))", false)
-        .testStatement("any(set([1, 0]))", true);
+        .testStatement("any(depset([0]))", false)
+        .testStatement("any(depset([1, 0]))", true);
   }
 
   @Test
@@ -386,7 +390,7 @@
                 + LINE_SEPARATOR
                 + "\t\ts[0]",
             "def foo():",
-            "  s = set()",
+            "  s = depset()",
             "  if s[0] == 1:",
             "    x = 1",
             "foo()");
@@ -438,9 +442,9 @@
   public void testBuiltinFunctionErrorMessage() throws Exception {
     new BothModesTest()
         .testIfErrorContains(
-            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
+            "Method depset.union(new_elements: Iterable) is not applicable for arguments (string): "
                 + "'new_elements' is string, but should be Iterable",
-            "set([]).union('a')")
+            "depset([]).union('a')")
         .testIfErrorContains(
             "Method string.startswith(sub: string, start: int, end: int or NoneType) is not "
                 + "applicable for arguments (int, int, NoneType): 'sub' is int, "
@@ -455,7 +459,7 @@
   @Test
   public void testHasAttr() throws Exception {
     new SkylarkTest()
-        .testStatement("hasattr(set(), 'union')", Boolean.TRUE)
+        .testStatement("hasattr(depset(), 'union')", Boolean.TRUE)
         .testStatement("hasattr('test', 'count')", Boolean.TRUE)
         .testStatement("hasattr(dict(a = 1, b = 2), 'items')", Boolean.TRUE)
         .testStatement("hasattr({}, 'items')", Boolean.TRUE);
@@ -969,7 +973,7 @@
             "Argument to reversed() must be a sequence, not a dictionary.", "reversed({1: 3})");
     new SkylarkTest()
         .testIfExactError(
-            "Argument to reversed() must be a sequence, not a set.", "reversed(set([1]))");
+            "Argument to reversed() must be a sequence, not a depset.", "reversed(depset([1]))");
   }
 
   @Test
@@ -1112,7 +1116,7 @@
         .testEval("sorted(['a','x','b','z'])", "[\"a\", \"b\", \"x\", \"z\"]")
         .testEval("sorted([sorted, sorted])", "[sorted, sorted]")
         .testEval("sorted({1: True, 5: True, 4: False})", "[1, 4, 5]")
-        .testEval("sorted(set([1, 5, 4]))", "[1, 4, 5]");
+        .testEval("sorted(depset([1, 5, 4]))", "[1, 4, 5]");
   }
 
   @Test
@@ -1411,42 +1415,47 @@
 
   @Test
   public void testSetUnionWithList() throws Exception {
-    evaluateSet("set([]).union(['a', 'b', 'c'])", "a", "b", "c");
-    evaluateSet("set(['a']).union(['b', 'c'])", "a", "b", "c");
-    evaluateSet("set(['a', 'b']).union(['c'])", "a", "b", "c");
-    evaluateSet("set(['a', 'b', 'c']).union([])", "a", "b", "c");
+    evaluateSet("depset([]).union(['a', 'b', 'c'])", "a", "b", "c");
+    evaluateSet("depset(['a']).union(['b', 'c'])", "a", "b", "c");
+    evaluateSet("depset(['a', 'b']).union(['c'])", "a", "b", "c");
+    evaluateSet("depset(['a', 'b', 'c']).union([])", "a", "b", "c");
   }
 
   @Test
   public void testSetUnionWithSet() throws Exception {
-    evaluateSet("set([]).union(set(['a', 'b', 'c']))", "a", "b", "c");
-    evaluateSet("set(['a']).union(set(['b', 'c']))", "a", "b", "c");
-    evaluateSet("set(['a', 'b']).union(set(['c']))", "a", "b", "c");
-    evaluateSet("set(['a', 'b', 'c']).union(set([]))", "a", "b", "c");
+    evaluateSet("depset([]).union(depset(['a', 'b', 'c']))", "a", "b", "c");
+    evaluateSet("depset(['a']).union(depset(['b', 'c']))", "a", "b", "c");
+    evaluateSet("depset(['a', 'b']).union(depset(['c']))", "a", "b", "c");
+    evaluateSet("depset(['a', 'b', 'c']).union(depset([]))", "a", "b", "c");
   }
 
   @Test
   public void testSetUnionDuplicates() throws Exception {
-    evaluateSet("set(['a', 'b', 'c']).union(['a', 'b', 'c'])", "a", "b", "c");
-    evaluateSet("set(['a', 'a', 'a']).union(['a', 'a'])", "a");
+    evaluateSet("depset(['a', 'b', 'c']).union(['a', 'b', 'c'])", "a", "b", "c");
+    evaluateSet("depset(['a', 'a', 'a']).union(['a', 'a'])", "a");
 
-    evaluateSet("set(['a', 'b', 'c']).union(set(['a', 'b', 'c']))", "a", "b", "c");
-    evaluateSet("set(['a', 'a', 'a']).union(set(['a', 'a']))", "a");
+    evaluateSet("depset(['a', 'b', 'c']).union(depset(['a', 'b', 'c']))", "a", "b", "c");
+    evaluateSet("depset(['a', 'a', 'a']).union(depset(['a', 'a']))", "a");
   }
 
   @Test
   public void testSetUnionError() throws Exception {
     new BothModesTest()
-        .testIfErrorContains("insufficient arguments received by union", "set(['a']).union()")
+        .testIfErrorContains("insufficient arguments received by union", "depset(['a']).union()")
         .testIfErrorContains(
-            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
+            "Method depset.union(new_elements: Iterable) is not applicable for arguments (string): "
                 + "'new_elements' is string, but should be Iterable",
-            "set(['a']).union('b')");
+            "depset(['a']).union('b')");
   }
 
   @Test
   public void testSetUnionSideEffects() throws Exception {
-    eval("def func():", "  n1 = set(['a'])", "  n2 = n1.union(['b'])", "  return n1", "n = func()");
+    eval(
+        "def func():",
+        "  n1 = depset(['a'])",
+        "  n2 = n1.union(['b'])",
+        "  return n1",
+        "n = func()");
     assertEquals(ImmutableList.of("a"), ((SkylarkNestedSet) lookup("n")).toCollection());
   }
 
@@ -1791,7 +1800,7 @@
         .testStatement("str(zip([1], []))", "[]")
         .testIfErrorContains("type 'int' is not iterable", "zip(123)")
         .testIfErrorContains("type 'int' is not iterable", "zip([1], 1)")
-        .testStatement("str(zip([1], set([2])))", "[(1, 2)]");
+        .testStatement("str(zip([1], depset([2])))", "[(1, 2)]");
   }
 
   @Test
@@ -1854,7 +1863,7 @@
   public void testTupleCoercion() throws Exception {
     new BothModesTest()
         .testStatement("tuple([1, 2]) == (1, 2)", true)
-        .testStatement("tuple(set([1, 2])) == (1, 2)", true)
+        .testStatement("tuple(depset([1, 2])) == (1, 2)", true)
         // Depends on current implementation of dict
         .testStatement("tuple({1: 'foo', 2: 'bar'}) == (1, 2)", true);
   }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index e949290..bc2753b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -854,16 +854,17 @@
 
   @Test
   public void testInSet() throws Exception {
-    new SkylarkTest().testStatement("'b' in set(['a', 'b'])", Boolean.TRUE)
-        .testStatement("'c' in set(['a', 'b'])", Boolean.FALSE)
-        .testStatement("1 in set(['a', 'b'])", Boolean.FALSE);
+    new SkylarkTest()
+        .testStatement("'b' in depset(['a', 'b'])", Boolean.TRUE)
+        .testStatement("'c' in depset(['a', 'b'])", Boolean.FALSE)
+        .testStatement("1 in depset(['a', 'b'])", Boolean.FALSE);
   }
 
   @Test
   public void testUnionSet() throws Exception {
     new SkylarkTest()
-        .testStatement("str(set([1, 3]) | set([1, 2]))", "set([1, 2, 3])")
-        .testStatement("str(set([1, 2]) | [1, 3])", "set([1, 2, 3])")
+        .testStatement("str(depset([1, 3]) | depset([1, 2]))", "depset([1, 2, 3])")
+        .testStatement("str(depset([1, 2]) | [1, 3])", "depset([1, 2, 3])")
         .testIfExactError("unsupported operand type(s) for |: 'int' and 'int'", "2 | 4");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
index a0d8420..e6a5935 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
@@ -17,6 +17,7 @@
 import static org.junit.Assert.assertEquals;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
@@ -35,50 +36,56 @@
 public class SkylarkNestedSetTest extends EvaluationTestCase {
 
   @Test
+  public void testLegacySetConstructor() throws Exception {
+    eval("ds = set([1, 2, 3], order='compile')");
+    SkylarkNestedSet ds = get("ds");
+    assertThat(ds.getOrder().getName()).isEqualTo("compile");
+    assertThat(ds.expandedSet()).isEqualTo(ImmutableSet.of(1, 2, 3));
+  }
+
+  @Test
   public void testNsetBuilder() throws Exception {
-    eval("n = set(order='stable')");
+    eval("n = depset(order='stable')");
     assertThat(lookup("n")).isInstanceOf(SkylarkNestedSet.class);
   }
 
   @Test
   public void testNsetOrder() throws Exception {
-    eval("n = set(['a', 'b'], order='compile')");
+    eval("n = depset(['a', 'b'], order='compile')");
     assertEquals(Order.COMPILE_ORDER, get("n").getSet(String.class).getOrder());
   }
 
   @Test
   public void testEmptyNsetGenericType() throws Exception {
-    eval("n = set()");
+    eval("n = depset()");
     assertEquals(SkylarkType.TOP, get("n").getContentType());
   }
 
   @Test
   public void testFunctionReturnsNset() throws Exception {
-    eval("def func():",
-         "  n = set()",
-         "  n += ['a']",
-         "  return n",
-         "s = func()");
+    eval("def func():", "  n = depset()", "  n += ['a']", "  return n", "s = func()");
     assertEquals(ImmutableList.of("a"), get("s").toCollection());
   }
 
   @Test
   public void testNsetTwoReferences() throws Exception {
-    eval("def func():",
-         "  n1 = set()",
-         "  n1 += ['a']",
-         "  n2 = n1",
-         "  n2 += ['b']",
-         "  return n1",
-         "n = func()");
+    eval(
+        "def func():",
+        "  n1 = depset()",
+        "  n1 += ['a']",
+        "  n2 = n1",
+        "  n2 += ['b']",
+        "  return n1",
+        "n = func()");
     assertEquals(ImmutableList.of("a"), get("n").toCollection());
   }
 
   @Test
   public void testNsetNestedItem() throws Exception {
-    eval("def func():",
-        "  n1 = set()",
-        "  n2 = set()",
+    eval(
+        "def func():",
+        "  n1 = depset()",
+        "  n2 = depset()",
         "  n1 += ['a']",
         "  n2 += ['b']",
         "  n1 += n2",
@@ -89,26 +96,24 @@
 
   @Test
   public void testNsetNestedItemBadOrder() throws Exception {
-    checkEvalError("LINK_ORDER != COMPILE_ORDER",
-        "set(['a', 'b'], order='compile') + set(['c', 'd'], order='link')");
+    checkEvalError(
+        "LINK_ORDER != COMPILE_ORDER",
+        "depset(['a', 'b'], order='compile') + depset(['c', 'd'], order='link')");
   }
 
   @Test
   public void testNsetItemList() throws Exception {
-    eval("def func():",
-        "  n = set()",
-        "  n += ['a', 'b']",
-        "  return n",
-        "n = func()");
+    eval("def func():", "  n = depset()", "  n += ['a', 'b']", "  return n", "n = func()");
     assertEquals(ImmutableList.of("a", "b"), get("n").toCollection());
   }
 
   @Test
   public void testNsetFuncParamNoSideEffects() throws Exception {
-    eval("def func1(n):",
+    eval(
+        "def func1(n):",
         "  n += ['b']",
         "def func2():",
-        "  n = set()",
+        "  n = depset()",
         "  n += ['a']",
         "  func1(n)",
         "  return n",
@@ -118,11 +123,12 @@
 
   @Test
   public void testNsetTransitiveOrdering() throws Exception {
-    eval("def func():",
-        "  na = set(['a'], order='compile')",
-        "  nb = set(['b'], order='compile')",
-        "  nc = set(['c'], order='compile') + na",
-        "  return set() + nb + nc",
+    eval(
+        "def func():",
+        "  na = depset(['a'], order='compile')",
+        "  nb = depset(['b'], order='compile')",
+        "  nc = depset(['c'], order='compile') + na",
+        "  return depset() + nb + nc",
         "n = func()");
     // The iterator lists the Transitive sets first
     assertEquals(ImmutableList.of("b", "a", "c"), get("n").toCollection());
@@ -130,8 +136,9 @@
 
   @Test
   public void testNsetOrdering() throws Exception {
-    eval("def func():",
-        "  na = set()",
+    eval(
+        "def func():",
+        "  na = depset()",
         "  na += [4]",
         "  na += [2, 4]",
         "  na += [3, 4, 5]",
@@ -143,26 +150,24 @@
 
   @Test
   public void testNsetBadOrder() throws Exception {
-    checkEvalError("Invalid order: non_existing", "set(order='non_existing')");
+    checkEvalError("Invalid order: non_existing", "depset(order='non_existing')");
   }
 
   @Test
   public void testNsetBadRightOperand() throws Exception {
-    checkEvalError("cannot add value of type 'string' to a set", "l = ['a']\n" + "set() + l[0]");
+    checkEvalError("cannot add value of type 'string' to a depset", "l = ['a']", "depset() + l[0]");
   }
 
   @Test
   public void testNsetToString() throws Exception {
-    eval("s = set() + [2, 4, 6] + [3, 4, 5]",
-        "x = str(s)");
-    assertEquals("set([2, 4, 6, 3, 5])", lookup("x"));
+    eval("s = depset() + [2, 4, 6] + [3, 4, 5]", "x = str(s)");
+    assertEquals("depset([2, 4, 6, 3, 5])", lookup("x"));
   }
 
   @Test
   public void testNsetToStringWithOrder() throws Exception {
-    eval("s = set(order = 'link') + [2, 4, 6] + [3, 4, 5]",
-        "x = str(s)");
-    assertEquals("set([2, 4, 6, 3, 5], order = \"link\")", lookup("x"));
+    eval("s = depset(order = 'link') + [2, 4, 6] + [3, 4, 5]", "x = str(s)");
+    assertEquals("depset([2, 4, 6, 3, 5], order = \"link\")", lookup("x"));
   }
 
   @SuppressWarnings("unchecked")
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
index e471f71..b420ffd 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
@@ -215,7 +215,7 @@
 
   @Test
   public void testModulesReadOnlyInFuncDefBody() {
-    parse("def func():", "  cmd_helper = set()");
+    parse("def func():", "  cmd_helper = depset()");
   }
 
   @Test