diff --git a/site/docs/skylark/backward-compatibility.md b/site/docs/skylark/backward-compatibility.md
index cb99910..032588b 100644
--- a/site/docs/skylark/backward-compatibility.md
+++ b/site/docs/skylark/backward-compatibility.md
@@ -30,6 +30,7 @@
 The following are the backward incompatible changes that are implemented and
 guarded behind flags in the current release:
 
+*   [Set constructor](#set-constructor)
 *   [Keyword-only arguments](#keyword-only-arguments)
 *   [Mutating `+=`](#mutating)
 *   [Dictionary concatenation](#dictionary-concatenation)
@@ -43,6 +44,18 @@
 *   [New actions API](#new-actions-api)
 *   [Checked arithmetic](#checked-arithmetic)
 
+### Set constructor
+
+We are removing the `set` constructor. Use `depset` instead. `set` and `depset`
+are equivalent, you just need to do search and replace to update the old code.
+
+We are doing this to reduce confusion between the specialized
+[depset](depsets.md) data structure and Python's set datatype.
+
+*   Flag: `--incompatible_disallow_set_constructor`
+*   Default: `true`
+
+
 ### Keyword-only arguments
 
 Keyword-only parameters are parameters that can be called only using their name.
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
index 6b6fde0..05cc7a1 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
@@ -102,20 +102,23 @@
  * dependencies-after-parent ordering. Note that the latter is usually more important, so please use
  * LINK_ORDER whenever possible.
  */
-// TODO(bazel-team): Remove deprecated names from the documentation above.
+// TODO(bazel-team): Remove deprecatedSkylarkName and it's associated helpers before Bazel 1.0.
 public enum Order {
-  STABLE_ORDER("default"),
-  COMPILE_ORDER("postorder"),
-  LINK_ORDER("topological"),
-  NAIVE_LINK_ORDER("preorder");
+  STABLE_ORDER("default", "stable"),
+  COMPILE_ORDER("postorder", "compile"),
+  LINK_ORDER("topological", "link"),
+  NAIVE_LINK_ORDER("preorder", "naive_link");
 
   private static final ImmutableMap<String, Order> VALUES;
+  private static final ImmutableMap<String, Order> DEPRECATED_VALUES;
 
   private final String skylarkName;
+  private final String deprecatedSkylarkName;
   private final NestedSet<?> emptySet;
 
-  private Order(String skylarkName) {
+  private Order(String skylarkName, String deprecatedSkylarkName) {
     this.skylarkName = skylarkName;
+    this.deprecatedSkylarkName = deprecatedSkylarkName;
     this.emptySet = new NestedSet<>(this);
   }
 
@@ -131,6 +134,35 @@
     return skylarkName;
   }
 
+  public String getDeprecatedSkylarkName() {
+    return deprecatedSkylarkName;
+  }
+
+  /**
+   * Parses the given string as a nested set order
+   *
+   * @param name unique name of the order
+   * @param forbidDeprecatedOrderNames if true, old style ordering names will be rejected
+   * @return the appropriate order instance
+   * @throws IllegalArgumentException if the name is not valid
+   */
+  public static Order parse(String name, boolean forbidDeprecatedOrderNames) {
+    if (VALUES.containsKey(name)) {
+      return VALUES.get(name);
+    } else if (DEPRECATED_VALUES.containsKey(name)) {
+      if (forbidDeprecatedOrderNames) {
+        throw new IllegalArgumentException(String.format(
+            "Order name '%s' is deprecated, use '%s' instead",
+            name,
+            DEPRECATED_VALUES.get(name).getSkylarkName()
+        ));
+      }
+      return DEPRECATED_VALUES.get(name);
+    } else {
+      throw new IllegalArgumentException("Invalid order: " + name);
+    }
+  }
+
   /**
    * Parses the given string as a nested set order
    *
@@ -139,11 +171,7 @@
    * @throws IllegalArgumentException if the name is not valid
    */
   public static Order parse(String name) {
-    if (VALUES.containsKey(name)) {
-      return VALUES.get(name);
-    } else {
-      throw new IllegalArgumentException("Invalid order: " + name);
-    }
+    return parse(name, false);
   }
 
   /**
@@ -163,11 +191,14 @@
     Order[] tmpValues = Order.values();
 
     HashMap<String, Order> entries = Maps.newHashMapWithExpectedSize(tmpValues.length);
+    HashMap<String, Order> deprecatedEntries = Maps.newHashMapWithExpectedSize(tmpValues.length);
 
     for (Order current : tmpValues) {
       entries.put(current.getSkylarkName(), current);
+      deprecatedEntries.put(current.getDeprecatedSkylarkName(), current);
     }
 
     VALUES = ImmutableMap.copyOf(entries);
+    DEPRECATED_VALUES = ImmutableMap.copyOf(deprecatedEntries);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java
index 52db1ce..e36eca2 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java
@@ -47,6 +47,7 @@
     codedOut.writeBoolNoTag(semantics.incompatibleDictLiteralHasNoDuplicates());
     codedOut.writeBoolNoTag(semantics.incompatibleDisallowDictPlus());
     codedOut.writeBoolNoTag(semantics.incompatibleDisallowKeywordOnlyArgs());
+    codedOut.writeBoolNoTag(semantics.incompatibleDisallowSetConstructor());
     codedOut.writeBoolNoTag(semantics.incompatibleDisallowToplevelIfStatement());
     codedOut.writeBoolNoTag(semantics.incompatibleListPlusEqualsInplace());
     codedOut.writeBoolNoTag(semantics.incompatibleLoadArgumentIsLabel());
@@ -69,6 +70,7 @@
     builder.incompatibleDictLiteralHasNoDuplicates(codedIn.readBool());
     builder.incompatibleDisallowDictPlus(codedIn.readBool());
     builder.incompatibleDisallowKeywordOnlyArgs(codedIn.readBool());
+    builder.incompatibleDisallowSetConstructor(codedIn.readBool());
     builder.incompatibleDisallowToplevelIfStatement(codedIn.readBool());
     builder.incompatibleListPlusEqualsInplace(codedIn.readBool());
     builder.incompatibleLoadArgumentIsLabel(codedIn.readBool());
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
index 0f8e0c4..2a7220d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
@@ -146,6 +146,17 @@
   public boolean incompatibleDisallowKeywordOnlyArgs;
 
   @Option(
+    name = "incompatible_disallow_set_constructor",
+    defaultValue = "true",
+    category = "incompatible changes",
+    documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+    effectTags = {OptionEffectTag.UNKNOWN},
+    metadataTags = {OptionMetadataTag.INCOMPATIBLE_CHANGE},
+    help = "If set to true, disables the deprecated `set` constructor for depsets."
+  )
+  public boolean incompatibleDisallowSetConstructor;
+
+  @Option(
     name = "incompatible_disallow_toplevel_if_statement",
     defaultValue = "true",
     category = "incompatible changes",
@@ -243,6 +254,7 @@
         .incompatibleDictLiteralHasNoDuplicates(incompatibleDictLiteralHasNoDuplicates)
         .incompatibleDisallowDictPlus(incompatibleDisallowDictPlus)
         .incompatibleDisallowKeywordOnlyArgs(incompatibleDisallowKeywordOnlyArgs)
+        .incompatibleDisallowSetConstructor(incompatibleDisallowSetConstructor)
         .incompatibleDisallowToplevelIfStatement(incompatibleDisallowToplevelIfStatement)
         .incompatibleListPlusEqualsInplace(incompatibleListPlusEqualsInplace)
         .incompatibleLoadArgumentIsLabel(incompatibleLoadArgumentIsLabel)
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
index 110c9e1..20111ce 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
@@ -114,7 +114,8 @@
         defaultValue = "None"
       )
     },
-    useLocation = true
+    useLocation = true,
+    useEnvironment = true
   )
   private static final BuiltinFunction depset =
       new BuiltinFunction("depset") {
@@ -123,11 +124,13 @@
             String orderString,
             Object direct,
             Object transitive,
-            Location loc)
+            Location loc,
+            Environment env)
             throws EvalException {
           Order order;
           try {
-            order = Order.parse(orderString);
+            order = Order.parse(
+                orderString, env.getSemantics().incompatibleDisallowSetConstructor());
           } catch (IllegalArgumentException ex) {
             throw new EvalException(loc, ex);
           }
@@ -175,6 +178,52 @@
   }
 
   @SkylarkSignature(
+    name = "set",
+    returnType = SkylarkNestedSet.class,
+    documentationReturnType = SkylarkNestedSet.LegacySet.class,
+    doc =
+        "A temporary alias for <a href=\"#depset\">depset</a>. "
+            + "Deprecated in favor of <code>depset</code>.",
+    parameters = {
+      @Param(
+        name = "items",
+        type = Object.class,
+        defaultValue = "[]",
+        doc = "Same as for <a href=\"#depset\">depset</a>."
+      ),
+      @Param(
+        name = "order",
+        type = String.class,
+        defaultValue = "\"default\"",
+        doc = "Same as for <a href=\"#depset\">depset</a>."
+      )
+    },
+    useLocation = true,
+    useEnvironment = true
+  )
+  private static final BuiltinFunction set =
+      new BuiltinFunction("set") {
+        public SkylarkNestedSet invoke(Object items, String order, Location loc, Environment env)
+            throws EvalException {
+          if (env.getSemantics().incompatibleDisallowSetConstructor()) {
+            throw new EvalException(
+                loc,
+                "The `set` constructor for depsets is deprecated and will be removed. Please use "
+                    + "the `depset` constructor instead. You can temporarily enable the "
+                    + "deprecated `set` constructor by passing the flag "
+                    + "--incompatible_disallow_set_constructor=false");
+          }
+          try {
+            return new SkylarkNestedSet(
+                Order.parse(order, /*forbidDeprecatedOrderNames=*/false),
+                items, loc);
+          } catch (IllegalArgumentException ex) {
+            throw new EvalException(loc, ex);
+          }
+        }
+      };
+
+  @SkylarkSignature(
     name = "union",
     objectType = SkylarkNestedSet.class,
     returnType = SkylarkNestedSet.class,
@@ -255,7 +304,7 @@
       };
 
   private static Environment.Frame createGlobals() {
-    List<BaseFunction> bazelGlobalFunctions = ImmutableList.of(select, depset, type);
+    List<BaseFunction> bazelGlobalFunctions = ImmutableList.of(select, depset, set, type);
 
     try (Mutability mutability = Mutability.create("BUILD")) {
       Environment env = Environment.builder(mutability)
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 f72f689..2915a8d 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
@@ -92,6 +92,20 @@
   @Nullable
   private final List<NestedSet> transitiveItems;
 
+  // Dummy class used to create a documentation for the deprecated `set` type
+  // TODO(bazel-team): remove before the end of 2017
+  @SkylarkModule(
+      name = "set",
+      category = SkylarkModuleCategory.BUILTIN,
+      doc = "A deprecated alias for <a href=\"depset.html\">depset</a>. "
+          + "Please use <a href=\"depset.html\">depset</a> instead. "
+          + "If you need a hash set that supports O(1) membership testing "
+          + "consider using a <a href=\"dict.html\">dict</a>."
+  )
+  static final class LegacySet {
+    private LegacySet() {}
+  }
+
   public SkylarkNestedSet(Order order, Object item, Location loc) throws EvalException {
     this(order, SkylarkType.TOP, item, loc, null);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java
index 105768f..8d1fa59 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java
@@ -46,6 +46,7 @@
   public abstract boolean incompatibleDictLiteralHasNoDuplicates();
   public abstract boolean incompatibleDisallowDictPlus();
   public abstract boolean incompatibleDisallowKeywordOnlyArgs();
+  public abstract boolean incompatibleDisallowSetConstructor();
   public abstract boolean incompatibleDisallowToplevelIfStatement();
   public abstract boolean incompatibleListPlusEqualsInplace();
   public abstract boolean incompatibleLoadArgumentIsLabel();
@@ -67,6 +68,7 @@
       .incompatibleDictLiteralHasNoDuplicates(true)
       .incompatibleDisallowDictPlus(false)
       .incompatibleDisallowKeywordOnlyArgs(true)
+      .incompatibleDisallowSetConstructor(true)
       .incompatibleDisallowToplevelIfStatement(true)
       .incompatibleListPlusEqualsInplace(true)
       .incompatibleLoadArgumentIsLabel(false)
@@ -88,6 +90,7 @@
     public abstract Builder incompatibleDictLiteralHasNoDuplicates(boolean value);
     public abstract Builder incompatibleDisallowDictPlus(boolean value);
     public abstract Builder incompatibleDisallowKeywordOnlyArgs(boolean value);
+    public abstract Builder incompatibleDisallowSetConstructor(boolean value);
     public abstract Builder incompatibleDisallowToplevelIfStatement(boolean value);
     public abstract Builder incompatibleListPlusEqualsInplace(boolean value);
     public abstract Builder incompatibleLoadArgumentIsLabel(boolean value);
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java
index 00d8ca7..30ef309 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java
@@ -30,6 +30,7 @@
   public void testParsing() throws Exception {
     for (Order current : Order.values()) {
       assertThat(Order.parse(current.getSkylarkName())).isEqualTo(current);
+      assertThat(Order.parse(current.getDeprecatedSkylarkName())).isEqualTo(current);
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
index f0f203e..3e1708f 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
@@ -112,6 +112,7 @@
         "--incompatible_dict_literal_has_no_duplicates=" + rand.nextBoolean(),
         "--incompatible_disallow_dict_plus=" + rand.nextBoolean(),
         "--incompatible_disallow_keyword_only_args=" + rand.nextBoolean(),
+        "--incompatible_disallow_set_constructor=" + rand.nextBoolean(),
         "--incompatible_disallow_toplevel_if_statement=" + rand.nextBoolean(),
         "--incompatible_list_plus_equals_inplace=" + rand.nextBoolean(),
         "--incompatible_load_argument_is_label=" + rand.nextBoolean(),
@@ -136,6 +137,7 @@
         .incompatibleDictLiteralHasNoDuplicates(rand.nextBoolean())
         .incompatibleDisallowDictPlus(rand.nextBoolean())
         .incompatibleDisallowKeywordOnlyArgs(rand.nextBoolean())
+        .incompatibleDisallowSetConstructor(rand.nextBoolean())
         .incompatibleDisallowToplevelIfStatement(rand.nextBoolean())
         .incompatibleListPlusEqualsInplace(rand.nextBoolean())
         .incompatibleLoadArgumentIsLabel(rand.nextBoolean())
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 c93311d..d61cb8a 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
@@ -15,6 +15,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.expectThrows;
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -36,6 +37,25 @@
 public class SkylarkNestedSetTest extends EvaluationTestCase {
 
   @Test
+  public void testLegacyConstructor() throws Exception {
+    env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=false");
+    eval("s = set([1, 2, 3], order='postorder')");
+    SkylarkNestedSet s = get("s");
+    assertThat(s.getOrder().getSkylarkName()).isEqualTo("postorder");
+    assertThat(s.getSet(Object.class)).containsExactly(1, 2, 3);
+  }
+
+  @Test
+  public void testLegacyConstructorDeprecation() throws Exception {
+    env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=true");
+    EvalException e = expectThrows(
+        EvalException.class,
+        () -> eval("s = set([1, 2, 3], order='postorder')")
+    );
+    assertThat(e).hasMessageThat().contains("The `set` constructor for depsets is deprecated");
+  }
+
+  @Test
   public void testConstructor() throws Exception {
     eval("s = depset(order='default')");
     assertThat(lookup("s")).isInstanceOf(SkylarkNestedSet.class);
@@ -130,6 +150,21 @@
   }
 
   @Test
+  public void testDeprecatedOrder() throws Exception {
+    env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=false");
+    eval("s = depset(['a', 'b'], order='compile')");
+    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
+
+    env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=true");
+    Exception e = expectThrows(
+        Exception.class,
+        () -> eval("s = depset(['a', 'b'], order='compile')")
+    );
+    assertThat(e).hasMessageThat().contains(
+          "Order name 'compile' is deprecated, use 'postorder' instead");
+  }
+
+  @Test
   public void testBadOrder() throws Exception {
     new BothModesTest().testIfExactError(
         "Invalid order: non_existing",