@Wyverald Just noticed that this could also be relevant to your proposal.
Repository rule restart behavior depends on attribute names
### Description of the problem / feature request:
As the documentation clearly states, repository rules will be restarted whenever the content of any file used and referred to by a label changes. If a repository rule depends on a filegroup for example and the contents of a file in that filegroup changes, the rule will not be restarted.

However, the logic that finds all files referred to directly by attributes stops on the first label-attribute that doesn't resolve to an existing files. On top of that, the order in which the attributes are checked seems to depend on the names of those attributes. That means that a repository rule depending on both a direct file and a filegroup can have the direct file as a restarting dependency or not, depending on the names of the attributes.

The restarting behavior can also be confirmed in the `@<external_name>.marker` files in the output base, where it only in some cases lists the direct file on a `FILE:`-line.

### Feature requests: what underlying problem are you trying to solve with this feature?
Make repository rule restarting behavior well defined and more predictable.

### Bugs: what's the simplest, easiest way to reproduce this bug? Please provide a minimal example if possible.
Small example with a repository downloading a file with a dependency on two empty local files `foo` and `bar`:

``` python
# WORKSPACE
load("my_http_download.bzl", "my_http_download")

my_http_download(
    name = "example",
    foo = "//:foo",
    bar = "//:bar",
)   
```
``` python
# my_http_download.bzl
def _my_http_download(ctx):
    ctx.download(
        url = "https://example.com",
        output = "index.html",
    )
    ctx.file("WORKSPACE")
    ctx.file("BUILD", content="exports_files(['index.html'])")

my_http_download = repository_rule(
    implementation = _my_http_download,
    attrs = {
        "foo": attr.label(),
        "bar": attr.label(),
    }
)
```
``` python
# BUILD
filegroup(
    name = "foo_filegroup",
    srcs = ["foo"],
    visibility = ["//visibility:public"],
)   

filegroup(
    name = "bar_filegroup",
    srcs = ["bar"],
    visibility = ["//visibility:public"],
)   
```
and `bazel build @example//:index.html`

* Changing the dependency on `//:foo` into `//:foo_filegroup` makes the rule only restart when `bar` changes (as expected).
* Changing the dependency on `//:bar` into `//:bar_filegroup` (but keeping the dependency on `//:foo`) makes the rule NOT restart when `foo` changes.

If the name of the `foo` attribute changes to `afoo` the incorrect behavior is the other way around:
* Changing the dependency on `//:bar` into `//:bar_filegroup` makes the rule only restart when `foo` changes (as expected).
* Changing the dependency on `//:foo` into `//:foo_filegroup` (but keeping the dependency on `//:bar`) makes the rule NOT restart when `bar` changes.

### What operating system are you running Bazel on?
Arch Linux, same behavior observed on CentOS 7.

### What's the output of `bazel info release`?
release 4.0.0

###  Have you found anything relevant by searching the web?
The checking on direct files seems to happen here: https://github.com/bazelbuild/bazel/blob/master/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java#L189

As the `EvalException` is caught outside the loop, the other attributes are not checked anymore after throwing.
src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java
src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java
src/test/shell/bazel/starlark_prefetching_test.sh
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java
index 2a8b59d80e5d25..dd8ad14c9b9fc8 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryContext.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.packages.StructProvider;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.repository.RepositoryFetchProgress;
+import com.google.devtools.build.lib.rules.repository.NeedsSkyframeRestartException;
 import com.google.devtools.build.lib.rules.repository.RepositoryFunction.RepositoryFunctionException;
 import com.google.devtools.build.lib.rules.repository.WorkspaceAttributeMapper;
 import com.google.devtools.build.lib.runtime.ProcessWrapper;
@@ -516,26 +517,42 @@ public String toString() {
    */
   // TODO(wyv): somehow migrate this to the base context too.
   public void enforceLabelAttributes() throws EvalException, InterruptedException {
+    // TODO: If a labels fails to resolve to an existing regular file, we do not add a dependency on
+    //  that fact - if the file is created later or changes its type, it will not trigger a rerun of
+    //  the repository function.
     StructImpl attr = getAttr();
     for (String name : attr.getFieldNames()) {
       Object value = attr.getValue(name);
       if (value instanceof Label) {
-        getPathFromLabel((Label) value);
+        dependOnLabelIgnoringErrors((Label) value);
       }
       if (value instanceof Sequence) {
         for (Object entry : (Sequence) value) {
           if (entry instanceof Label) {
-            getPathFromLabel((Label) entry);
+            dependOnLabelIgnoringErrors((Label) entry);
           }
         }
       }
       if (value instanceof Dict) {
         for (Object entry : ((Dict) value).keySet()) {
           if (entry instanceof Label) {
-            getPathFromLabel((Label) entry);
+            dependOnLabelIgnoringErrors((Label) entry);
           }
         }
       }
     }
   }
+
+  private void dependOnLabelIgnoringErrors(Label label)
+      throws InterruptedException, NeedsSkyframeRestartException {
+    try {
+      getPathFromLabel(label);
+    } catch (NeedsSkyframeRestartException e) {
+      throw e;
+    } catch (EvalException e) {
+      // EvalExceptions indicate labels not referring to existing files. This is fine,
+      // as long as they are never resolved to files in the execution of the rule; we allow
+      // non-strict rules.
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java
index 83772d1fd28194..140697445739bb 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/starlark/StarlarkRepositoryFunction.java
@@ -198,11 +198,6 @@ public RepositoryDirectoryValue.Builder fetch(
       } catch (NeedsSkyframeRestartException e) {
         // Missing values are expected; just restart before we actually start the rule
         return null;
-      } catch (EvalException e) {
-        // EvalExceptions indicate labels not referring to existing files. This is fine,
-        // as long as they are never resolved to files in the execution of the rule; we allow
-        // non-strict rules. So now we have to start evaluating the actual rule, even if that
-        // means the rule might get restarted for legitimate reasons.
       }
 
       // This rule is mainly executed for its side effect. Nevertheless, the return value is

diff --git a/src/test/shell/bazel/starlark_prefetching_test.sh b/src/test/shell/bazel/starlark_prefetching_test.sh
index f12c7426c617bd..69e5bfda740c30 100755
--- a/src/test/shell/bazel/starlark_prefetching_test.sh
+++ b/src/test/shell/bazel/starlark_prefetching_test.sh
@@ -227,4 +227,48 @@ EOF
   bazel build @ext//:foo || fail "expected success"
 }
 
+# Regression test for https://github.com/bazelbuild/bazel/issues/13441
+function test_files_tracked_with_non_existing_files() {
+  cat > rules.bzl <<'EOF'
+def _repo_impl(ctx):
+    ctx.symlink(ctx.path(Label("@//:WORKSPACE")).dirname, "link")
+    print("b.txt: " + ctx.read("link/b.txt"))
+    print("c.txt: " + ctx.read("link/c.txt"))
+
+    ctx.file("BUILD")
+    ctx.file("WORKSPACE")
+
+repo = repository_rule(
+    _repo_impl,
+    attrs = {"_files": attr.label_list(
+        default = [
+            Label("@//:a.txt"),
+            Label("@//:b.txt"),
+            Label("@//:c.txt"),
+        ],
+    )},
+)
+EOF
+
+  cat > WORKSPACE <<'EOF'
+load(":rules.bzl", "repo")
+repo(name = "ext")
+EOF
+  touch BUILD
+
+  # a.txt is intentionally not created
+  echo "bbbb" > b.txt
+  echo "cccc" > c.txt
+
+  # The missing file dependency is tolerated.
+  bazel build @ext//:all &> "$TEST_log" || fail "Expected repository rule to build"
+  expect_log "b.txt: bbbb"
+  expect_log "c.txt: cccc"
+
+  echo "not_cccc" > c.txt
+  bazel build @ext//:all &> "$TEST_log" || fail "Expected repository rule to build"
+  expect_log "b.txt: bbbb"
+  expect_log "c.txt: not_cccc"
+}
+
 run_suite "Starlark repo prefetching tests"
