Related to: https://github.com/bazelbuild/bazel/issues/4680 Done as of 58d3f17. Follow-up in #8830 
Tags to execution requirements propagation in Native Rules
It is not a secret that by default bazel does not propagate tags to the actions' execution requirements, the only exception would be the rules that are specifically adopted to do the propagation (e.g. test related tags are already propagated by the test runner).

Tags should be propagated to the action from targets for Native rules.

Design:
https://docs.google.com/document/d/1X2GtuuNT6UqYYOK5lJWQEdPjAgsbdB3nFjjmjso-XHo/edit?usp=sharing

Related github issue for Starlark rules: #7766.

See #8830 for details.
src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java
src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java
src/test/shell/bazel/tags_propagation_native_test.sh
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
index cfc20bcc494691..0a31a9daa54a57 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
@@ -38,12 +38,15 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 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.TargetUtils;
 import com.google.devtools.build.lib.rules.java.JavaConfiguration.JavaClasspathMode;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
 import javax.annotation.Nullable;
 
 /**
@@ -189,7 +192,8 @@ public JavaCompileAction createCompileAction(
       Artifact outputJar,
       Artifact manifestProtoOutput,
       @Nullable Artifact gensrcOutputJar,
-      @Nullable Artifact nativeHeaderOutput) {
+      @Nullable Artifact nativeHeaderOutput)
+      throws InterruptedException {
 
     JavaTargetAttributes attributes = getAttributes();
 
@@ -252,13 +256,19 @@ && getTranslations().isEmpty()) {
     return builder.build(ruleContext, semantics);
   }
 
-  private ImmutableMap<String, String> getExecutionInfo() {
-    return getConfiguration()
-        .modifiedExecutionInfo(
-            javaToolchain.getJavacSupportsWorkers()
-                ? ExecutionRequirements.WORKER_MODE_ENABLED
-                : ImmutableMap.of(),
-            JavaCompileActionBuilder.MNEMONIC);
+  private ImmutableMap<String, String> getExecutionInfo() throws InterruptedException {
+    Map<String, String> executionInfo = new LinkedHashMap<>();
+    executionInfo.putAll(
+        getConfiguration()
+            .modifiedExecutionInfo(
+                javaToolchain.getJavacSupportsWorkers()
+                    ? ExecutionRequirements.WORKER_MODE_ENABLED
+                    : ImmutableMap.of(),
+                JavaCompileActionBuilder.MNEMONIC));
+    executionInfo.putAll(
+        TargetUtils.getExecutionInfo(ruleContext.getRule(), ruleContext.isAllowTagsPropagation()));
+
+    return ImmutableMap.copyOf(executionInfo);
   }
 
   /** Returns the bootclasspath explicit set in attributes if present, or else the default. */
@@ -352,7 +362,8 @@ private boolean shouldUseHeaderCompilation() {
    *     for new artifacts.
    */
   private Artifact createHeaderCompilationAction(
-      Artifact runtimeJar, JavaCompilationArtifacts.Builder artifactBuilder) {
+      Artifact runtimeJar, JavaCompilationArtifacts.Builder artifactBuilder)
+      throws InterruptedException {
 
     Artifact headerJar =
         getAnalysisEnvironment()
@@ -628,7 +639,7 @@ public void createSourceJarAction(Artifact outputJar, @Nullable Artifact gensrcJ
    * @return the header jar (if requested), or ijar (if requested), or else the class jar
    */
   public Artifact createCompileTimeJarAction(
-      Artifact runtimeJar, JavaCompilationArtifacts.Builder builder) {
+      Artifact runtimeJar, JavaCompilationArtifacts.Builder builder) throws InterruptedException {
     Artifact jar;
     boolean isFullJar = false;
     if (shouldUseHeaderCompilation()) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
index 06e0187cdaeec3..90234c95af5b69 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
@@ -44,6 +44,7 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 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.TargetUtils;
 import com.google.devtools.build.lib.rules.java.JavaCompileAction.ProgressMessage;
 import com.google.devtools.build.lib.rules.java.JavaConfiguration.JavaClasspathMode;
 import com.google.devtools.build.lib.rules.java.JavaPluginInfoProvider.JavaPluginInfo;
@@ -53,7 +54,9 @@
 import com.google.devtools.build.lib.view.proto.Deps;
 import java.io.IOException;
 import java.io.InputStream;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.function.Consumer;
 import javax.annotation.Nullable;
 
@@ -215,7 +218,7 @@ public JavaHeaderCompileActionBuilder setToolsJars(NestedSet<Artifact> toolsJars
   }
 
   /** Builds and registers the action for a header compilation. */
-  public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavabase) {
+  public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavabase) throws InterruptedException {
     checkNotNull(outputDepsProto, "outputDepsProto must not be null");
     checkNotNull(sourceFiles, "sourceFiles must not be null");
     checkNotNull(sourceJars, "sourceJars must not be null");
@@ -369,9 +372,9 @@ public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavab
               /* commandLineLimits= */ ruleContext.getConfiguration().getCommandLineLimits(),
               /* isShellCommand= */ false,
               /* env= */ actionEnvironment,
-              /* executionInfo= */ ruleContext
+              /* executionInfo= */ addTags(ruleContext
                   .getConfiguration()
-                  .modifiedExecutionInfo(executionInfo, "Turbine"),
+                  .modifiedExecutionInfo(executionInfo, "Turbine")),
               /* progressMessage= */ progressMessage,
               /* runfilesSupplier= */ CompositeRunfilesSupplier.fromSuppliers(runfilesSuppliers),
               /* mnemonic= */ "Turbine",
@@ -417,7 +420,7 @@ public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavab
               /* transitiveInputs= */ classpathEntries,
               /* directJars= */ directJars,
               /* outputs= */ outputs,
-              /* executionInfo= */ executionInfo,
+              /* executionInfo= */ addTags(executionInfo),
               /* extraActionInfoSupplier= */ null,
               /* executableLine= */ executableLine,
               /* flagLine= */ commandLine.build(),
@@ -454,9 +457,9 @@ public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavab
             /* commandLineLimits= */ ruleContext.getConfiguration().getCommandLineLimits(),
             /* isShellCommand= */ false,
             /* env= */ actionEnvironment,
-            /* executionInfo= */ ruleContext
+            /* executionInfo= */ addTags(ruleContext
                 .getConfiguration()
-                .modifiedExecutionInfo(executionInfo, "JavacTurbine"),
+                .modifiedExecutionInfo(executionInfo, "JavacTurbine")),
             /* progressMessage= */ progressMessage,
             /* runfilesSupplier= */ CompositeRunfilesSupplier.fromSuppliers(runfilesSuppliers),
             /* mnemonic= */ "JavacTurbine",
@@ -465,6 +468,15 @@ public void build(JavaToolchainProvider javaToolchain, JavaRuntimeInfo hostJavab
             /* resultConsumer= */ resultConsumer));
   }
 
+  private ImmutableMap<String, String> addTags(ImmutableMap<String, String> executionInfo) throws InterruptedException {
+    Map<String, String> executionInfoBuilder = new LinkedHashMap<>();
+
+    executionInfoBuilder.putAll(executionInfo);
+    executionInfoBuilder.putAll(TargetUtils.getExecutionInfo(ruleContext.getRule(), ruleContext.isAllowTagsPropagation()));
+
+    return ImmutableMap.copyOf(executionInfoBuilder);
+  }
+
   /**
    * Creates a consumer that reads the produced .jdeps file into memory. Pulled out into a separate
    * function to avoid capturing a data member, which would keep the entire builder instance alive.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java
index d5184b75c40e1f..be6208cafe29df 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfoBuildHelper.java
@@ -292,7 +292,7 @@ public JavaInfo createJavaCompileAction(
       JavaSemantics javaSemantics,
       Location location,
       Environment environment)
-      throws EvalException {
+          throws EvalException, InterruptedException {
 
     if (sourceJars.isEmpty()
         && sourceFiles.isEmpty()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
index ece3c58bfa4570..55326445a553b5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
@@ -182,7 +182,7 @@ public JavaCompilationArtifacts build(
       JavaRuntimeInfo hostJavabase,
       JavaRuleOutputJarsProvider.Builder outputJarsBuilder,
       boolean createOutputSourceJar,
-      @Nullable Artifact outputSourceJar) {
+      @Nullable Artifact outputSourceJar) throws InterruptedException {
     return build(
         semantics,
         javaToolchainProvider,
@@ -204,7 +204,7 @@ public JavaCompilationArtifacts build(
       @Nullable Artifact outputSourceJar,
       @Nullable JavaInfo.Builder javaInfoBuilder,
       Iterable<JavaGenJarsProvider> transitiveJavaGenJars,
-      ImmutableList<Artifact> additionalJavaBaseInputs) {
+      ImmutableList<Artifact> additionalJavaBaseInputs) throws InterruptedException {
 
     Preconditions.checkState(output != null, "must have an output file; use setOutput()");
     Preconditions.checkState(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
index da899079159f1d..f4f4ae52933a8c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
@@ -172,7 +172,7 @@ private static class Impl {
                   "exports", RuleConfiguredTarget.Mode.TARGET, JavaCompilationArgsProvider.class));
     }
 
-    void addProviders(ConfiguredAspect.Builder aspect) {
+    void addProviders(ConfiguredAspect.Builder aspect) throws InterruptedException {
       JavaInfo.Builder javaInfo = JavaInfo.Builder.create();
       // Represents the result of compiling the code generated for this proto, including all of its
       // dependencies.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
index 93ac592dd93965..98df054f5eeef5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
@@ -192,7 +192,7 @@ private static class Impl {
                     JavaCompilationArgsProvider.class));
     }
 
-    void addProviders(ConfiguredAspect.Builder aspect) {
+    void addProviders(ConfiguredAspect.Builder aspect) throws InterruptedException {
       // Represents the result of compiling the code generated for this proto, including all of its
       // dependencies.
       JavaInfo.Builder javaInfo = JavaInfo.Builder.create();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java
index 422ce7b994398c..5318467f4c1d0e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspectCommon.java
@@ -108,7 +108,7 @@ public JavaCompilationArgsProvider createJavaCompileAction(
       String injectingRuleKind,
       Artifact sourceJar,
       Artifact outputJar,
-      JavaCompilationArgsProvider dep) {
+      JavaCompilationArgsProvider dep) throws InterruptedException {
     JavaLibraryHelper helper =
         new JavaLibraryHelper(ruleContext)
             .setInjectingRuleKind(injectingRuleKind)

diff --git a/src/test/shell/bazel/tags_propagation_native_test.sh b/src/test/shell/bazel/tags_propagation_native_test.sh
index 7ffee2fab58800..969f3fbf549761 100755
--- a/src/test/shell/bazel/tags_propagation_native_test.sh
+++ b/src/test/shell/bazel/tags_propagation_native_test.sh
@@ -98,6 +98,119 @@ EOF
   assert_contains "no-remote:" output1
 }
 
+function test_java_library_tags_propagated() {
+  mkdir -p test
+  cat > test/BUILD <<EOF
+package(default_visibility = ["//visibility:public"])
+java_library(
+  name = 'test',
+  srcs = [ 'Hello.java' ],
+  tags = ["no-cache", "no-remote", "local"]
+)
+EOF
+
+	cat > test/Hello.java <<EOF
+public class Main {
+  public static void main(String[] args) {
+    System.out.println("Hello there");
+  }
+}
+EOF
+
+  bazel aquery --experimental_allow_tags_propagation '//test:test' > output1 2> $TEST_log \
+      || fail "should have generated output successfully"
+
+  assert_contains "ExecutionInfo: {" output1
+  assert_contains "local:" output1
+  assert_contains "no-cache:" output1
+  assert_contains "no-remote:" output1
+}
+
+function test_java_binary_tags_propagated() {
+  mkdir -p test
+  cat > test/BUILD <<EOF
+package(default_visibility = ["//visibility:public"])
+java_binary(
+  name = 'test',
+  srcs = [ 'Hello.java' ],
+  main_class = 'main.Hello',
+  tags = ["no-cache", "no-remote", "local"]
+)
+EOF
+
+	cat > test/Hello.java <<EOF
+public class Main {
+  public static void main(String[] args) {
+    System.out.println("Hello there");
+  }
+}
+EOF
+
+  bazel aquery --experimental_allow_tags_propagation '//test:test' > output1 2> $TEST_log \
+      || fail "should have generated output successfully"
+
+  assert_contains "ExecutionInfo: {" output1
+  assert_contains "local:" output1
+  assert_contains "no-cache:" output1
+  assert_contains "no-remote:" output1
+}
+
+function write_hello_library_files() {
+  local -r pkg="$1"
+  mkdir -p $pkg/java/main || fail "mkdir"
+  cat >$pkg/java/main/BUILD <<EOF
+java_binary(
+    name = 'main',
+    deps = ['//$pkg/java/hello_library'],
+    srcs = ['Main.java'],
+    main_class = 'main.Main',
+    tags = ["no-cache", "no-remote", "local"],
+    deploy_manifest_lines = ['k1: v1', 'k2: v2'])
+EOF
+
+  cat >$pkg/java/main/Main.java <<EOF
+package main;
+import hello_library.HelloLibrary;
+public class Main {
+  public static void main(String[] args) {
+    HelloLibrary.funcHelloLibrary();
+    System.out.println("Hello, World!");
+  }
+}
+EOF
+
+  mkdir -p $pkg/java/hello_library || fail "mkdir"
+  cat >$pkg/java/hello_library/BUILD <<EOF
+package(default_visibility=['//visibility:public'])
+java_library(name = 'hello_library',
+             srcs = ['HelloLibrary.java']);
+EOF
+
+  cat >$pkg/java/hello_library/HelloLibrary.java <<EOF
+package hello_library;
+public class HelloLibrary {
+  public static void funcHelloLibrary() {
+    System.out.print("Hello, Library!;");
+  }
+}
+EOF
+}
+
+function test_java_header_tags_propagated() {
+  local -r pkg="${FUNCNAME[0]}"
+  mkdir "$pkg" || fail "mkdir $pkg"
+  write_hello_library_files "$pkg"
+
+  bazel aquery --experimental_allow_tags_propagation --java_header_compilation=true //$pkg/java/main:main > output1 2> $TEST_log \
+      || fail "should have generated output successfully"
+
+  assert_contains "ExecutionInfo: {" output1
+  assert_contains "local:" output1
+  assert_contains "no-cache:" output1
+  assert_contains "no-remote:" output1
+
+}
+
 function test_genrule_tags_propagated() {
   mkdir -p test
   cat > test/BUILD <<EOF
@@ -193,4 +306,31 @@ EOF
   assert_not_contains "no-remote:" output1
 }
 
-run_suite "tags propagation: skylark rule tests"
+function test_java_tags_not_propagated_when_incompatible_flag_off() {
+  mkdir -p test
+  cat > test/BUILD <<EOF
+package(default_visibility = ["//visibility:public"])
+java_library(
+  name = 'test',
+  srcs = [ 'Hello.java' ],
+  tags = ["no-cache", "no-remote", "local"]
+)
+EOF
+
+	cat > test/Hello.java <<EOF
+public class Main {
+  public static void main(String[] args) {
+    System.out.println("Hello there");
+  }
+}
+EOF
+
+  bazel aquery --experimental_allow_tags_propagation=false '//test:test' > output1 2> $TEST_log \
+      || fail "should have generated output successfully"
+
+  assert_not_contains "local:" output1
+  assert_not_contains "no-cache:" output1
+  assert_not_contains "no-remote:" output1
+}
+
+run_suite "tags propagation: native rule tests"
