Does https://github.com/bazelbuild/bazel/pull/14600 fix this issue? Aw, I was hopeful.  I fixed some merge conflicts (looks like "../".replace() -> Strings.replace("../", ...) and I still get the same failure.

```
==================== Test output for @aos//aos:condition_test:
/var/lib/worker/work/3/exec/bazel-out/k8-opt/bin/external/aos/aos/condition_test.runfiles/repo/../aos/aos/condition_test: error while loading shared libraries: libexternal_Saos_Saos_Slibcondition.so: cannot open shared object file: No such file or directory
``` Could you check whether https://github.com/bazelbuild/bazel/pull/16008 fixes the issue? It includes an integration test that I distilled from your reproducer. It does!  Great work, thanks for the prompt response and prompt resolution.  I really appreciate it.

FYI, there's the same merge conflict with Strings.replace.  Not a hard thing to fix though. Assigning to @oquenchil since the linked fix is about cc rules. Aw, @fmeum , looks like this fixed almost all of the tests except one which expects $(location) and RPATH to agree on the path to the shared libraries.  https://github.com/bazelbuild/bazel/issues/16108 is the issue since it smells different enough to be a new bug. @bazel-io fork 5.3.1 The fix introduced a regression (see https://github.com/bazelbuild/bazel/pull/16008#issuecomment-1224267553), which we will probably need a patch release for. Seeing a very similar problem when upgrading from 5.2.0 to 5.3.0:
```
error while loading shared libraries: libexternal_Sopenvkl_Slibispc_Uutil_Uispc.so: cannot open shared object file: No such file or directory
```
But trying out 5.3.1rc2, it looks like that particular problem is resolved for us. Hello @AustinSchuh, Are you still seeing this issue with Release 5.3.1 ?  5.3.1 works for me.  I'm hitting https://github.com/bazelbuild/bazel/issues/16108 but that feels separate. Thanks for the update @AustinSchuh!
Bazel 5.3 fails to run external tests
### Description of the bug:


Bazel fails to run C++ tests in external repositories on remote execution.

Running locally passes, even with linux-sandbox.  Bazel 5.0 worked.  This has broken bazel > 5.0 for us, and is blocking all upgrades.

### What's the simplest, easiest way to reproduce this bug? Please provide a minimal example if possible.


`bazel test -c opt --config=engflow --config=build_without_the_bytes @aos//aos:condition_test`

Run a c++ test for an external repository on remote execution.  (I can't give you a remote execution cluster)

### Which operating system are you running Bazel on?


Debian Bullseye

### What is the output of `bazel info release`?


release 5.3.0-202207291633+f440f8ec3f

### If `bazel info release` returns `development version` or `(@non-git)`, tell us how you built Bazel.

```
#!/bin/bash

# This script builds a Debian package from a Bazel source tree with the
# correct version.
# The only argument is the path to a Bazel source tree.

set -e
set -u

BAZEL_SOURCE="$1"

VERSION="5.3.0-$(date +%Y%m%d%H%M)+$(GIT_DIR="${BAZEL_SOURCE}/.git" git rev-parse --short HEAD)"
OUTPUT="bazel_${VERSION}"

(
cd "${BAZEL_SOURCE}"
bazel build -c opt //src:bazel --embed_label="${VERSION}" --stamp=yes
)

cp "${BAZEL_SOURCE}/bazel-bin/src/bazel" "${OUTPUT}"

echo "Output is at ${OUTPUT}"
```

### What's the output of `git remote get-url origin; git rev-parse master; git rev-parse HEAD` ?


```text
austin[504] cmbr (release-5.3.0) ~/local/bazel
$ git remote get-url origin; git rev-parse master; git rev-parse HEAD
https://github.com/bazelbuild/bazel
master
fatal: ambiguous argument 'master': unknown revision or path not in the working tree.
Use '--' to separate paths from revisions, like this:
'git <command> [<revision>...] -- [<file>...]'
f440f8ec3f63e5d663e1f9d9614f05a39422102a
```


### Have you found anything relevant by searching the web?

Reverting https://github.com/bazelbuild/bazel/commit/00805727b867d33fd922e63ca82b0d9825ad79fe fixes it.  https://github.com/bazelbuild/bazel/issues/12821 suggested that I add linkstatic to every C++ test we want to run, which seems like 1k's of lines of diffs off upstream, since no reasonable upstream would accept that patch.

### Any other information, logs, or outputs that you want to share?

```
bazel test -c opt --config=remote_execution --config=build_without_the_bytes @aos//aos:condition_test
INFO: Invocation ID: d91e1b30-a290-4282-99c6-029e4102ed35
INFO: Analyzed target @aos//aos:condition_test (86 packages loaded, 20904 targets configured).
INFO: Found 1 test target...
FAIL: @aos//aos:condition_test (see /home/austin/.cache/bazel/_bazel_austin/f5b123ff4a0d503fd09f4c4da36644a6/execroot/repo/bazel-out/k8-opt/testlogs/external/aos/aos/condition_test/test.log)
INFO: From Testing @aos//aos:condition_test:
==================== Test output for @aos//aos:condition_test:
/var/lib/worker/work/1/exec/bazel-out/k8-opt/bin/external/aos/aos/condition_test.runfiles/repo/../aos/aos/condition_test: error while loading shared libraries: libexternal_Saos_Saos_Slibcondition.so: cannot open shared object file: No such file or directory
================================================================================
Target @aos//aos:condition_test up-to-date:
  bazel-bin/external/aos/aos/condition_test
INFO: Elapsed time: 166.038s, Critical Path: 153.48s
INFO: 52 processes: 50 remote cache hit, 2 remote.
@aos//aos:condition_test                                                 FAILED in 127.2s
  /home/austin/.cache/bazel/_bazel_austin/f5b123ff4a0d503fd09f4c4da36644a6/execroot/repo/bazel-out/k8-opt/testlogs/external/aos/aos/condition_test/test.log

Executed 1 out of 1 test: 1 fails remotely.
INFO: Build completed, 1 test FAILED, 52 total actions
```

And to prove I'm not crazy:

```
bazel test -c opt -k @aos//aos:condition_test
INFO: Build options --experimental_inmemory_dotd_files, --experimental_inmemory_jdeps_files, --extra_execution_platforms, and 2 more have changed, discarding analysis cache.
INFO: Analyzed target @aos//aos:condition_test (0 packages loaded, 20897 targets configured).
INFO: Found 1 test target...
Target @aos//aos:condition_test up-to-date:
  bazel-bin/external/aos/aos/condition_test
INFO: Elapsed time: 12.246s, Critical Path: 10.91s
INFO: 120 processes: 42 internal, 78 linux-sandbox.
INFO: Build completed successfully, 120 total actions
@aos//aos:condition_test                                                 PASSED in 2.3s

Executed 1 out of 1 test: 1 test passes.
INFO: Build completed successfully, 120 total actions
```
src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
src/test/shell/bazel/remote/remote_execution_test.sh
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
index 330bcdce43b2cd..6624c1c5b4c4be 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ParameterFile;
+import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.RuleErrorConsumer;
 import com.google.devtools.build.lib.analysis.actions.ActionConstructionContext;
 import com.google.devtools.build.lib.analysis.actions.ParameterFileWriteAction;
@@ -798,7 +799,8 @@ public CppLinkAction build() throws InterruptedException, RuleErrorException {
             allowLtoIndexing,
             nonExpandedLinkerInputs,
             needWholeArchive,
-            ruleErrorConsumer);
+            ruleErrorConsumer,
+            ((RuleContext) actionConstructionContext).getWorkspaceName());
     CollectedLibrariesToLink collectedLibrariesToLink =
         librariesToLinkCollector.collectLibrariesToLink();
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
index a1bb3b99d64b2d..27be6f49d23b6f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.RuleErrorConsumer;
+import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
@@ -69,7 +70,8 @@ public LibrariesToLinkCollector(
       boolean allowLtoIndexing,
       Iterable<LinkerInput> linkerInputs,
       boolean needWholeArchive,
-      RuleErrorConsumer ruleErrorConsumer) {
+      RuleErrorConsumer ruleErrorConsumer,
+      String workspaceName) {
     this.isNativeDeps = isNativeDeps;
     this.cppConfiguration = cppConfiguration;
     this.ccToolchainProvider = toolchain;
@@ -106,10 +108,20 @@ public LibrariesToLinkCollector(
       // there's no *one* RPATH setting that fits all targets involved in the sharing.
       rpathRoot = ccToolchainProvider.getSolibDirectory() + "/";
     } else {
-      rpathRoot =
-          Strings.repeat("../", outputArtifact.getRootRelativePath().segmentCount() - 1)
-              + ccToolchainProvider.getSolibDirectory()
-              + "/";
+      // When executed from within a runfiles directory, the binary lies under a path such as
+      // target.runfiles/some_repo/pkg/file, whereas the solib directory is located under
+      // target.runfiles/main_repo.
+      PathFragment runfilesPath = outputArtifact.getRunfilesPath();
+      String runfilesExecRoot;
+      if (runfilesPath.startsWith(LabelConstants.EXTERNAL_RUNFILES_PATH_PREFIX)) {
+        // runfilesPath is of the form ../some_repo/pkg/file, walk back some_repo/pkg and then
+        // descend into the main workspace.
+        runfilesExecRoot = Strings.repeat("../", runfilesPath.segmentCount() - 2) + workspaceName + "/";
+      } else {
+        // runfilesPath is of the form pkg/file, walk back pkg to reach the main workspace.
+        runfilesExecRoot = Strings.repeat("../", runfilesPath.segmentCount() - 1);
+      }
+      rpathRoot = runfilesExecRoot + ccToolchainProvider.getSolibDirectory() + "/";
     }
 
     ltoMap = generateLtoMap();

diff --git a/src/test/shell/bazel/remote/remote_execution_test.sh b/src/test/shell/bazel/remote/remote_execution_test.sh
index e79b2dfe4f4d49..318fdccd25cd54 100755
--- a/src/test/shell/bazel/remote/remote_execution_test.sh
+++ b/src/test/shell/bazel/remote/remote_execution_test.sh
@@ -3811,4 +3811,62 @@ EOF
   expect_log "Executing genrule .* failed: (Exit 1):"
 }
 
+function test_external_cc_test() {
+  if [[ "$PLATFORM" == "darwin" ]]; then
+    # TODO(b/37355380): This test is disabled due to RemoteWorker not supporting
+    # setting SDKROOT and DEVELOPER_DIR appropriately, as is required of
+    # action executors in order to select the appropriate Xcode toolchain.
+    return 0
+  fi
+
+  cat >> WORKSPACE <<'EOF'
+local_repository(
+  name = "other_repo",
+  path = "other_repo",
+)
+EOF
+
+  mkdir -p other_repo
+  touch other_repo/WORKSPACE
+
+  mkdir -p other_repo/lib
+  cat > other_repo/lib/BUILD <<'EOF'
+cc_library(
+  name = "lib",
+  srcs = ["lib.cpp"],
+  hdrs = ["lib.h"],
+  visibility = ["//visibility:public"],
+)
+EOF
+  cat > other_repo/lib/lib.h <<'EOF'
+void print_greeting();
+EOF
+  cat > other_repo/lib/lib.cpp <<'EOF'
+#include <cstdio>
+void print_greeting() {
+  printf("Hello, world!\n");
+}
+EOF
+
+  mkdir -p other_repo/test
+  cat > other_repo/test/BUILD <<'EOF'
+cc_test(
+  name = "test",
+  srcs = ["test.cpp"],
+  deps = ["//lib"],
+)
+EOF
+  cat > other_repo/test/test.cpp <<'EOF'
+#include "lib/lib.h"
+int main() {
+  print_greeting();
+}
+EOF
+
+  bazel test \
+      --test_output=errors \
+      --remote_executor=grpc://localhost:${worker_port} \
+      @other_repo//test >& $TEST_log || fail "Test should pass"
+}
+
 run_suite "Remote execution and remote cache tests"
