diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/LabelValidator.java b/src/main/java/com/google/devtools/build/lib/cmdline/LabelValidator.java
index a2f419e..633946c 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/LabelValidator.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/LabelValidator.java
@@ -24,8 +24,14 @@
  */
 public final class LabelValidator {
 
+  // Target names allow all 7-bit ASCII characters except
+  // 0-31 (control characters)
+  // 58 ':' (colon)
+  // 92 '\' (backslash) - directory separator (on Windows); may be allowed in the future
+  // 127 (delete)
   /** Matches punctuation in target names which requires quoting in a blaze query. */
-  private static final CharMatcher PUNCTUATION_REQUIRING_QUOTING = CharMatcher.anyOf("+,=~# ()$");
+  private static final CharMatcher PUNCTUATION_REQUIRING_QUOTING =
+      CharMatcher.anyOf(" \"#$&'()*+,;<=>?[]{|}~");
 
   /**
    * Matches punctuation in target names which doesn't require quoting in a blaze query.
@@ -33,16 +39,21 @@
    * Note that . is also allowed in target names, and doesn't require quoting, but has restrictions
    * on its surrounding characters; see {@link #validateTargetName(String)}.
    */
-  private static final CharMatcher PUNCTUATION_NOT_REQUIRING_QUOTING = CharMatcher.anyOf("_@-");
+  private static final CharMatcher PUNCTUATION_NOT_REQUIRING_QUOTING =
+      CharMatcher.anyOf("!%-@^_`");
 
-  /**
-   * Matches characters allowed in package name.
-   */
+  // Package names allow all 7-bit ASCII characters except
+  // 0-31 (control characters)
+  // 58 ':' (colon) - target name separator
+  // 64 '@' (at-sign) - workspace name prefix
+  // 92 '\' (backslash) - directory separator (on Windows); may be allowed in the future
+  // 127 (delete)
+  /** Matches characters allowed in package name. */
   private static final CharMatcher ALLOWED_CHARACTERS_IN_PACKAGE_NAME =
       CharMatcher.inRange('0', '9')
           .or(CharMatcher.inRange('a', 'z'))
           .or(CharMatcher.inRange('A', 'Z'))
-          .or(CharMatcher.anyOf("/-._ $()"))
+          .or(CharMatcher.anyOf(" !\"#$%&'()*+,-./;<=>?[]^_`{|}~"))
           .precomputed();
 
   /**
@@ -59,7 +70,8 @@
 
   @VisibleForTesting
   static final String PACKAGE_NAME_ERROR =
-      "package names may contain only A-Z, a-z, 0-9, '/', '-', '.', ' ', '$', '(', ')' and '_'";
+      "package names may contain A-Z, a-z, 0-9, or any of ' !\"#$%&'()*+,-./;<=>?[]^_`{|}~'"
+          + " (most 127-bit ascii characters except 0-31, 127, ':', '@', or '\\')";
 
   @VisibleForTesting
   static final String PACKAGE_NAME_DOT_ERROR =
diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index a486ddb..f9d885d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -174,6 +174,10 @@
       // invalid as a label, plus users should say explicitly if they
       // really want to name the package directory.
       if (!relative.isEmpty()) {
+        if (relative.charAt(0) == '@') {
+          // Add explicit colon to disambiguate from external repository.
+          relative = ":" + relative;
+        }
         result.add(relative);
       }
     }
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
index 7e34cc6..be61b94 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
@@ -30,7 +30,8 @@
 @RunWith(JUnit4.class)
 public class LabelTest {
 
-  private static final String BAD_PACKAGE_CHARS = "package names may contain only";
+  private static final String BAD_PACKAGE_CHARS =
+      "package names may contain A-Z, a-z, 0-9, or any of";
   private static final String INVALID_TARGET_NAME = "invalid target name";
   private static final String INVALID_PACKAGE_NAME = "invalid package name";
 
@@ -89,7 +90,7 @@
   @Test
   public void testLabelResolutionBadSyntax() throws Exception {
     try {
-      parseCommandLine("//absolute:A+bad%syntax", "");
+      parseCommandLine("//absolute:A+bad:syntax", "");
       fail();
     } catch (LabelSyntaxException e) {
       // Expected exception
@@ -303,12 +304,6 @@
                       "//foo:bar:");
     assertSyntaxError("target names may not contain ':'",
                       "//foo/bar::");
-    assertSyntaxError("target names may not contain '&'",
-                      "//foo:bar&");
-    // Warning: if these assertions are false, tools that assume that they can safely quote labels
-    // may need to be fixed. Please consult with bazel-dev before loosening these restrictions.
-    assertSyntaxError("target names may not contain '''", "//foo/bar:baz'foo");
-    assertSyntaxError("target names may not contain '\"'", "//foo/bar:baz\"foo");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
index 2156ddf..fcb187f 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelValidatorTest.java
@@ -53,6 +53,37 @@
     assertThat(LabelValidator.validatePackageName("a/b..")).isNull();
     assertThat(LabelValidator.validatePackageName("a$( )/b..")).isNull();
 
+    // These are in ascii code order.
+    assertThat(LabelValidator.validatePackageName("foo!bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo\"bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo#bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo$bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo%bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo&bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo'bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo(bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo)bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo*bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo+bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo,bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo-bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo.bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo+bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo;bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo<bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo=bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo>bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo?bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo[bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo]bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo^bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo_bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo`bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo{bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo|bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo}bar")).isNull();
+    assertThat(LabelValidator.validatePackageName("foo~bar")).isNull();
+
     // Bad:
     assertThat(LabelValidator.validatePackageName("/foo"))
         .isEqualTo("package names may not start with '/'");
@@ -82,16 +113,39 @@
 
   @Test
   public void testValidateTargetName() throws Exception {
-
     assertThat(LabelValidator.validateTargetName("foo")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo!bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo\"bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo#bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo$bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo%bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo&bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo'bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo(bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo)bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo*bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo+bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo_bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo=bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo,bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo-bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo.bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo@bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo+bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo;bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo<bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo=bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo>bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo?bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo[bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo]bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo^bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo_bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo`bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo{bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo|bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo}bar")).isNull();
     assertThat(LabelValidator.validateTargetName("foo~bar")).isNull();
-    assertThat(LabelValidator.validateTargetName("foo#bar")).isNull();
+
+    assertThat(LabelValidator.validateTargetName("foo/bar")).isNull();
+    assertThat(LabelValidator.validateTargetName("foo@bar")).isNull();
 
     assertThat(LabelValidator.validateTargetName("foo/"))
         .isEqualTo("target names may not end with '/'");
@@ -99,8 +153,6 @@
         .isEqualTo("target names may not contain ':'");
     assertThat(LabelValidator.validateTargetName("bar:"))
         .isEqualTo("target names may not contain ':'");
-    assertThat(LabelValidator.validateTargetName("bar&"))
-        .isEqualTo("target names may not contain '&'");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
index 012e120..e33d1f3 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
@@ -50,7 +50,7 @@
   @Test
   public void testInvalidPatterns() throws TargetParsingException {
     try {
-      parse("Bar&&&java");
+      parse("Bar@java");
       fail();
     } catch (TargetParsingException expected) {
     }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java b/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
index 57b7c59..c422f77 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/OutputFileTest.java
@@ -167,7 +167,7 @@
             "bad_out_name/BUILD",
             "genrule(name='a',",
             "        cmd='ls',",
-            "        outs=['!@#'])");
+            "        outs=['!@#:'])");
 
     reporter.removeHandler(failFastHandler);
     packageFactory.createPackageForTesting(
@@ -175,7 +175,7 @@
         buildfile,
         getPackageManager(),
         reporter);
-    assertContainsEvent("illegal output file name '!@#' in rule //bad_out_name:a");
+    assertContainsEvent("illegal output file name '!@#:' in rule //bad_out_name:a");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
index e4729d3..ba07b68 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
@@ -236,10 +236,10 @@
 
   @Test
   public void testGetPackageWithInvalidName() throws Exception {
-    scratch.file("invalidpackagename&42/BUILD", "cc_library(name = 'foo') # a BUILD file");
+    scratch.file("invalidpackagename:42/BUILD", "cc_library(name = 'foo') # a BUILD file");
     checkGetPackageFails(
-        "invalidpackagename&42",
-        "no such package 'invalidpackagename&42': Invalid package name 'invalidpackagename&42'");
+        "invalidpackagename:42",
+        "no such package 'invalidpackagename:42': Invalid package name 'invalidpackagename:42'");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
index f6ec361..a7f81a2 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluatorTest.java
@@ -712,8 +712,6 @@
   public void testFailingValidations() {
     expectValidationFail("");
     expectValidationFail("\\");
-    expectValidationFail("foo:**");
-    expectValidationFail("//foo/*");
   }
 
   private void expectValidationFail(String target) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
index 195d987..4d63399 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -243,8 +243,8 @@
 
   @Test
   public void testInvalidPackageName() throws Exception {
-    scratch.file("parentpackage/invalidpackagename%42/BUILD");
-    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/invalidpackagename%42");
+    scratch.file("parentpackage/invalidpackagename:42/BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/invalidpackagename:42");
     assertThat(packageLookupValue.packageExists()).isFalse();
     assertThat(packageLookupValue.getErrorReason()).isEqualTo(ErrorReason.INVALID_PACKAGE_NAME);
     assertThat(packageLookupValue.getErrorMsg()).isNotNull();