diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 1b45009..fad548a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -1649,13 +1649,12 @@
       String msgReason = reason != null ? " (" + reason + ")" : "";
       if (isWarning) {
         return String.format(
-            "%s'%s'%s is unexpected here%s; continuing anyway",
-            msgPrefix, prerequisite.getLabel(), AliasProvider.printVisibilityChain(prerequisite),
+            "%s%s is unexpected here%s; continuing anyway",
+            msgPrefix, AliasProvider.printLabelWithAliasChain(prerequisite),
             msgReason);
       }
-      return String.format(
-          "%s'%s'%s is misplaced here%s", msgPrefix, prerequisite.getLabel(),
-          AliasProvider.printVisibilityChain(prerequisite), msgReason);
+      return String.format("%s%s is misplaced here%s",
+          msgPrefix, AliasProvider.printLabelWithAliasChain(prerequisite), msgReason);
     }
 
     private void reportBadPrerequisite(Attribute attribute, String targetKind,
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
index 508de47..ef82170 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
@@ -195,29 +195,22 @@
     private void validateDirectPrerequisiteVisibility(
         RuleContext.Builder context, ConfiguredTarget prerequisite, String attrName) {
       Rule rule = context.getRule();
-      if (rule.getLabel().getPackageFragment().equals(Label.EXTERNAL_PACKAGE_NAME)) {
-        // //external: labels are special. They have access to everything and visibility is checked
-        // at the edge that points to the //external: label.
-        return;
-      }
       Target prerequisiteTarget = prerequisite.getTarget();
-      Label prerequisiteLabel = prerequisiteTarget.getLabel();
       if (!context.getRule().getLabel().getPackageIdentifier().equals(
-              prerequisite.getTarget().getLabel().getPackageIdentifier())
+              AliasProvider.getDependencyLabel(prerequisite).getPackageIdentifier())
           && !context.isVisible(prerequisite)) {
         if (!context.getConfiguration().checkVisibility()) {
           context.ruleWarning(String.format("Target '%s' violates visibility of target "
-              + "'%s'. Continuing because --nocheck_visibility is active",
-              rule.getLabel(), prerequisiteLabel));
+              + "%s. Continuing because --nocheck_visibility is active",
+              rule.getLabel(), AliasProvider.printLabelWithAliasChain(prerequisite)));
         } else {
           // Oddly enough, we use reportError rather than ruleError here.
           context.reportError(rule.getLocation(),
-              String.format("Target '%s' is not visible from target '%s'%s. Check "
+              String.format("Target %s is not visible from target '%s'. Check "
                   + "the visibility declaration of the former target if you think "
                   + "the dependency is legitimate",
-                  prerequisiteLabel,
-                  rule.getLabel(),
-                  AliasProvider.printVisibilityChain(prerequisite)));
+                  AliasProvider.printLabelWithAliasChain(prerequisite),
+                  rule.getLabel()));
         }
       }
 
@@ -230,9 +223,9 @@
                 + rule.getRuleClass()
                 + " rule "
                 + rule.getLabel()
-                + ": package group '"
-                + prerequisiteLabel
-                + "' is misplaced here "
+                + ": package group "
+                + AliasProvider.printLabelWithAliasChain(prerequisite)
+                + " is misplaced here "
                 + "(they are only allowed in the visibility attribute)");
       }
     }
@@ -248,12 +241,11 @@
       }
 
       Target prerequisiteTarget = prerequisite.getTarget();
-      Label prerequisiteLabel = prerequisiteTarget.getLabel();
       String thisPackage = rule.getLabel().getPackageName();
 
       if (isTestOnlyRule(prerequisiteTarget) && !isTestOnlyRule(rule)) {
-        String message = "non-test target '" + rule.getLabel() + "' depends on testonly target '"
-            + prerequisiteLabel + "'" + AliasProvider.printVisibilityChain(prerequisite)
+        String message = "non-test target '" + rule.getLabel() + "' depends on testonly target "
+            + AliasProvider.printLabelWithAliasChain(prerequisite)
             + " and doesn't have testonly attribute set";
         if (thisPackage.startsWith("experimental/")) {
           context.ruleWarning(message);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java b/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java
index a6950b2..e3300cb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java
@@ -68,12 +68,12 @@
     return aliasChain;
   }
 
-  public static String printVisibilityChain(ConfiguredTarget target) {
+  public static String printLabelWithAliasChain(ConfiguredTarget target) {
     AliasProvider aliasProvider = target.getProvider(AliasProvider.class);
-    if (aliasProvider == null) {
-      return "";
-    }
+    String suffix = aliasProvider == null
+        ? ""
+        : " (aliased through '" + Joiner.on("' -> '").join(aliasProvider.getAliasChain()) + "')";
 
-    return " (aliased through '" + Joiner.on("' -> '").join(aliasProvider.getAliasChain()) + "')";
+    return "'" + target.getLabel() + "'" + suffix;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java b/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
index 1b89ced..9f199a1 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
@@ -19,7 +19,11 @@
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
-import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
+import com.google.devtools.build.lib.analysis.VisibilityProvider;
+import com.google.devtools.build.lib.analysis.VisibilityProviderImpl;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
+import com.google.devtools.build.lib.packages.PackageSpecification;
 import com.google.devtools.build.lib.rules.AliasConfiguredTarget;
 import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory;
@@ -43,6 +47,9 @@
         ruleContext.getConfiguration(),
         actual,
         ImmutableMap.<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>of(
-            AliasProvider.class, AliasProvider.fromAliasRule(ruleContext.getLabel(), actual)));
+            AliasProvider.class, AliasProvider.fromAliasRule(ruleContext.getLabel(), actual),
+            VisibilityProvider.class, new VisibilityProviderImpl(
+                NestedSetBuilder.create(Order.STABLE_ORDER, PackageSpecification.everything()))));
+
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/AliasTest.java b/src/test/java/com/google/devtools/build/lib/rules/AliasTest.java
index 17d3ea1..4b456a3 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/AliasTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/AliasTest.java
@@ -79,7 +79,7 @@
     reporter.removeHandler(failFastHandler);
     getConfiguredTarget("//c:c");
     assertContainsEvent(
-        "Target '//a:a' is not visible from target '//c:c' (aliased through '//b:b')");
+        "Target '//a:a' (aliased through '//b:b') is not visible from target '//c:c'");
   }
 
   @Test
@@ -96,7 +96,18 @@
     reporter.removeHandler(failFastHandler);
     getConfiguredTarget("//d:d");
     assertContainsEvent(
-        "Target '//a:a' is not visible from target '//d:d' (aliased through '//c:c' -> '//b:b')");
+        "Target '//a:a' (aliased through '//c:c' -> '//b:b') is not visible from target '//d:d'");
+  }
+
+  @Test
+  public void testAliasWithPrivateVisibilityAccessibleFromSamePackage() throws Exception {
+    scratch.file("a/BUILD", "exports_files(['af'])");
+    scratch.file("b/BUILD",
+        "package(default_visibility=['//visibility:private'])",
+        "alias(name='al', actual='//a:af')",
+        "filegroup(name='ta', srcs=[':al'])");
+
+    getConfiguredTarget("//b:tf");
   }
 
   @Test
diff --git a/src/test/shell/bazel/external_skylark_load_test.sh b/src/test/shell/bazel/external_skylark_load_test.sh
index 49c603e..6c503f1 100755
--- a/src/test/shell/bazel/external_skylark_load_test.sh
+++ b/src/test/shell/bazel/external_skylark_load_test.sh
@@ -247,8 +247,8 @@
 cat > BUILD <<EOF
 load("//:rule.bzl", "test_rule")
 
-filegroup(name = "x1")
-filegroup(name = "x2")
+filegroup(name = "x1", visibility = ["//visibility:public"])
+filegroup(name = "x2", visibility = ["//visibility:public"])
 test_rule(
     name = "tr",
     deps = ["//external:x1", "//external:x2"],
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index 4145267..851911c 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -842,7 +842,7 @@
 
   bazel build @r//:public >& $TEST_log || fail "failed to build public target"
   bazel build @r//:private >& $TEST_log && fail "could build private target"
-  expect_log "Target '//:private' is not visible from target '@r//:private'"
+  expect_log "Target '//:private' is not visible from target '//external:private'"
 }
 
 function test_load_in_remote_repository() {