Revert "Revert "Add project permission for removing votes/labels.""

This reverts commit 7b91e4e06fd1ff5bdfcebb4561fcee32cf48caf2.

Reason for revert: Re-adding the feature with the needed fixes.

Issues with the original change:

1. The added dependency on ChangeData::notes() while checking for
 permissions broke the query flow.
2. For backward compatibility, removing label should be allowed with
either remove-reviewer or remove-vote permissions.
3. ChangeInfoDiffer.getAddedForMap failed when the old map was null.

Bug: Google b/245706858
Bug: Google b/265447204
Change-Id: I5c74804d1dbb51cf6d97de653e47654acd2bf263
Forward-Compatible: checked
Release-Notes: New project permission for removing votes/labels
diff --git a/Documentation/access-control.txt b/Documentation/access-control.txt
index f2f5a66..9a40b27 100644
--- a/Documentation/access-control.txt
+++ b/Documentation/access-control.txt
@@ -800,6 +800,22 @@
 Users without this access right who are able to upload changes can
 still do the revert locally and upload the revert commit as a new change.
 
+[[category_remove_label]]
+=== Remove Label (Remove Vote)
+
+For every configured label `My-Name` in the project, there is a
+corresponding permission `removeLabel-My-Name` with a range corresponding to
+the defined values. For these values, the users are permitted to remove
+other users' votes from a change.
+
+Change owners can always remove zero or positive votes (even without
+having the `Remove Vote` access right assigned).
+
+Project owners and site administrators can always remove any vote (even
+without having the `Remove Vote` access right assigned).
+
+Users without this access right can still remove their own votes.
+
 [[category_remove_reviewer]]
 === Remove Reviewer
 
diff --git a/Documentation/rest-api-changes.txt b/Documentation/rest-api-changes.txt
index 359361c..2f144c6 100644
--- a/Documentation/rest-api-changes.txt
+++ b/Documentation/rest-api-changes.txt
@@ -824,6 +824,26 @@
         "+2"
       ]
     },
+    "removable_labels": {
+      "Code-Review": {
+        "-1": [
+          {
+            "_account_id": 1000096,
+            "name": "John Doe",
+            "email": "john.doe@example.com",
+            "username": "jdoe"
+          }
+        ],
+        "+1": [
+          {
+            "_account_id": 1000097,
+            "name": "Jane Roe",
+            "email": "jane.roe@example.com",
+            "username": "jroe"
+          }
+        ]
+      }
+    },
     "removable_reviewers": [
       {
         "_account_id": 1000096,
@@ -7071,6 +7091,13 @@
 A map of the permitted labels that maps a label name to the list of
 values that are allowed for that label. +
 Only set if link:#detailed-labels[detailed labels] are requested.
+|`removable_labels`   |optional|
+A map of the removable labels that maps a label name to the map of
+values and reviewers (
+link:rest-api-accounts.html#account-info[AccountInfo] entities)
+that are allowed to be removed from the change. +
+Only set if link:#labels[labels] or
+link:#detailed-labels[detailed labels] are requested.
 |`removable_reviewers`|optional|
 The reviewers that can be removed by the calling user as a list of
 link:rest-api-accounts.html#account-info[AccountInfo] entities. +
diff --git a/java/com/google/gerrit/acceptance/AbstractDaemonTest.java b/java/com/google/gerrit/acceptance/AbstractDaemonTest.java
index 5b4a9e5..ccf74d1 100644
--- a/java/com/google/gerrit/acceptance/AbstractDaemonTest.java
+++ b/java/com/google/gerrit/acceptance/AbstractDaemonTest.java
@@ -1393,6 +1393,17 @@
     }
   }
 
+  protected void assertOnlyRemovableLabel(
+      ChangeInfo info, String labelId, String labelValue, TestAccount reviewer) {
+    assertThat(info.removableLabels).hasSize(1);
+    assertThat(info.removableLabels).containsKey(labelId);
+    assertThat(info.removableLabels.get(labelId)).hasSize(1);
+    assertThat(info.removableLabels.get(labelId)).containsKey(labelValue);
+    assertThat(info.removableLabels.get(labelId).get(labelValue)).hasSize(1);
+    assertThat(info.removableLabels.get(labelId).get(labelValue).get(0).email)
+        .isEqualTo(reviewer.email());
+  }
+
   protected void assertPermissions(
       Project.NameKey project,
       GroupReference groupReference,
diff --git a/java/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImpl.java b/java/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImpl.java
index b1cd506..69139ce 100644
--- a/java/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImpl.java
+++ b/java/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImpl.java
@@ -197,8 +197,13 @@
         PermissionRule.Builder rule = newRule(projectConfig, p.group());
         rule.setAction(p.action());
         rule.setRange(p.min(), p.max());
-        String permissionName =
-            p.impersonation() ? Permission.forLabelAs(p.name()) : Permission.forLabel(p.name());
+        String permissionName;
+        if (p.isAddPermission()) {
+          permissionName =
+              p.impersonation() ? Permission.forLabelAs(p.name()) : Permission.forLabel(p.name());
+        } else {
+          permissionName = Permission.forRemoveLabel(p.name());
+        }
         projectConfig.upsertAccessSection(
             p.ref(), as -> as.upsertPermission(permissionName).add(rule));
       }
diff --git a/java/com/google/gerrit/acceptance/testsuite/project/TestProjectUpdate.java b/java/com/google/gerrit/acceptance/testsuite/project/TestProjectUpdate.java
index 9a9a21a..5634c78 100644
--- a/java/com/google/gerrit/acceptance/testsuite/project/TestProjectUpdate.java
+++ b/java/com/google/gerrit/acceptance/testsuite/project/TestProjectUpdate.java
@@ -162,12 +162,34 @@
 
   /** Starts a builder for allowing a label permission. */
   public static TestLabelPermission.Builder allowLabel(String name) {
-    return TestLabelPermission.builder().name(name).action(PermissionRule.Action.ALLOW);
+    return TestLabelPermission.builder()
+        .name(name)
+        .isAddPermission(true)
+        .action(PermissionRule.Action.ALLOW);
   }
 
   /** Starts a builder for denying a label permission. */
   public static TestLabelPermission.Builder blockLabel(String name) {
-    return TestLabelPermission.builder().name(name).action(PermissionRule.Action.BLOCK);
+    return TestLabelPermission.builder()
+        .name(name)
+        .isAddPermission(true)
+        .action(PermissionRule.Action.BLOCK);
+  }
+
+  /** Starts a builder for allowing a remove-label permission. */
+  public static TestLabelPermission.Builder allowLabelRemoval(String name) {
+    return TestLabelPermission.builder()
+        .name(name)
+        .isAddPermission(false)
+        .action(PermissionRule.Action.ALLOW);
+  }
+
+  /** Starts a builder for denying a remove-label permission. */
+  public static TestLabelPermission.Builder blockLabelRemoval(String name) {
+    return TestLabelPermission.builder()
+        .name(name)
+        .isAddPermission(false)
+        .action(PermissionRule.Action.BLOCK);
   }
 
   /** Records a label permission to be updated. */
@@ -191,6 +213,8 @@
 
     abstract boolean impersonation();
 
+    abstract boolean isAddPermission();
+
     /** Builder for {@link TestLabelPermission}. */
     @AutoValue.Builder
     public abstract static class Builder {
@@ -208,6 +232,8 @@
 
       abstract Builder max(int max);
 
+      abstract Builder isAddPermission(boolean isAddPermission);
+
       /** Sets the minimum and maximum values for the permission. */
       public Builder range(int min, int max) {
         checkArgument(min != 0 || max != 0, "empty range");
@@ -243,6 +269,12 @@
     return TestPermissionKey.builder().name(Permission.forLabel(name));
   }
 
+  /** Starts a builder for describing a label removal permission key for deletion. */
+  public static TestPermissionKey.Builder labelRemovalPermissionKey(String name) {
+    checkLabelName(name);
+    return TestPermissionKey.builder().name(Permission.forRemoveLabel(name));
+  }
+
   /** Starts a builder for describing a capability key for deletion. */
   public static TestPermissionKey.Builder capabilityKey(String name) {
     return TestPermissionKey.builder().name(name).section(GLOBAL_CAPABILITIES);
diff --git a/java/com/google/gerrit/entities/Permission.java b/java/com/google/gerrit/entities/Permission.java
index 6d2fa32..d029fad 100644
--- a/java/com/google/gerrit/entities/Permission.java
+++ b/java/com/google/gerrit/entities/Permission.java
@@ -43,6 +43,7 @@
   public static final String FORGE_SERVER = "forgeServerAsCommitter";
   public static final String LABEL = "label-";
   public static final String LABEL_AS = "labelAs-";
+  public static final String REMOVE_LABEL = "removeLabel-";
   public static final String OWNER = "owner";
   public static final String PUSH = "push";
   public static final String PUSH_MERGE = "pushMerge";
@@ -60,6 +61,7 @@
   private static final List<String> NAMES_LC;
   private static final int LABEL_INDEX;
   private static final int LABEL_AS_INDEX;
+  private static final int REMOVE_LABEL_INDEX;
 
   static {
     NAMES_LC = new ArrayList<>();
@@ -79,6 +81,7 @@
     NAMES_LC.add(FORGE_SERVER.toLowerCase());
     NAMES_LC.add(LABEL.toLowerCase());
     NAMES_LC.add(LABEL_AS.toLowerCase());
+    NAMES_LC.add(REMOVE_LABEL.toLowerCase());
     NAMES_LC.add(OWNER.toLowerCase());
     NAMES_LC.add(PUSH.toLowerCase());
     NAMES_LC.add(PUSH_MERGE.toLowerCase());
@@ -93,15 +96,19 @@
 
     LABEL_INDEX = NAMES_LC.indexOf(Permission.LABEL);
     LABEL_AS_INDEX = NAMES_LC.indexOf(Permission.LABEL_AS.toLowerCase());
+    REMOVE_LABEL_INDEX = NAMES_LC.indexOf(Permission.REMOVE_LABEL.toLowerCase());
   }
 
   /** Returns true if the name is recognized as a permission name. */
   public static boolean isPermission(String varName) {
-    return isLabel(varName) || isLabelAs(varName) || NAMES_LC.contains(varName.toLowerCase());
+    return isLabel(varName)
+        || isLabelAs(varName)
+        || isRemoveLabel(varName)
+        || NAMES_LC.contains(varName.toLowerCase());
   }
 
   public static boolean hasRange(String varName) {
-    return isLabel(varName) || isLabelAs(varName);
+    return isLabel(varName) || isLabelAs(varName) || isRemoveLabel(varName);
   }
 
   /** Returns true if the permission name is actually for a review label. */
@@ -114,6 +121,11 @@
     return var.startsWith(LABEL_AS) && LABEL_AS.length() < var.length();
   }
 
+  /** Returns true if the permission is for impersonated review labels. */
+  public static boolean isRemoveLabel(String var) {
+    return var.startsWith(REMOVE_LABEL) && REMOVE_LABEL.length() < var.length();
+  }
+
   /** Returns permission name for the given review label. */
   public static String forLabel(String labelName) {
     return LABEL + labelName;
@@ -124,12 +136,19 @@
     return LABEL_AS + labelName;
   }
 
+  /** Returns permission name to remove a label for another user. */
+  public static String forRemoveLabel(String labelName) {
+    return REMOVE_LABEL + labelName;
+  }
+
   @Nullable
   public static String extractLabel(String varName) {
     if (isLabel(varName)) {
       return varName.substring(LABEL.length());
     } else if (isLabelAs(varName)) {
       return varName.substring(LABEL_AS.length());
+    } else if (isRemoveLabel(varName)) {
+      return varName.substring(REMOVE_LABEL.length());
     }
     return null;
   }
@@ -205,6 +224,8 @@
       return LABEL_INDEX;
     } else if (isLabelAs(a.getName())) {
       return LABEL_AS_INDEX;
+    } else if (isRemoveLabel(a.getName())) {
+      return REMOVE_LABEL_INDEX;
     }
 
     int index = NAMES_LC.indexOf(a.getName().toLowerCase());
diff --git a/java/com/google/gerrit/extensions/common/ChangeInfo.java b/java/com/google/gerrit/extensions/common/ChangeInfo.java
index 40ae2ec..a865187 100644
--- a/java/com/google/gerrit/extensions/common/ChangeInfo.java
+++ b/java/com/google/gerrit/extensions/common/ChangeInfo.java
@@ -105,6 +105,7 @@
   public Map<String, ActionInfo> actions;
   public Map<String, LabelInfo> labels;
   public Map<String, Collection<String>> permittedLabels;
+  public Map<String, Map<String, List<AccountInfo>>> removableLabels;
   public Collection<AccountInfo> removableReviewers;
   public Map<ReviewerState, Collection<AccountInfo>> reviewers;
   public Map<ReviewerState, Collection<AccountInfo>> pendingReviewers;
diff --git a/java/com/google/gerrit/extensions/common/ChangeInfoDiffer.java b/java/com/google/gerrit/extensions/common/ChangeInfoDiffer.java
index 24182cc..51c35dc 100644
--- a/java/com/google/gerrit/extensions/common/ChangeInfoDiffer.java
+++ b/java/com/google/gerrit/extensions/common/ChangeInfoDiffer.java
@@ -150,16 +150,17 @@
   /** Returns {@code null} if nothing has been added to {@code oldCollection} */
   @Nullable
   private static ImmutableList<?> getAddedForCollection(
-      Collection<?> oldCollection, Collection<?> newCollection) {
-    ImmutableList<?> notInOldCollection = getAdditions(oldCollection, newCollection);
+      @Nullable Collection<?> oldCollection, Collection<?> newCollection) {
+    ImmutableList<?> notInOldCollection = getAdditionsForCollection(oldCollection, newCollection);
     return notInOldCollection.isEmpty() ? null : notInOldCollection;
   }
 
   @Nullable
-  private static ImmutableList<Object> getAdditions(
-      Collection<?> oldCollection, Collection<?> newCollection) {
-    if (oldCollection == null)
-      return newCollection != null ? ImmutableList.copyOf(newCollection) : null;
+  private static ImmutableList<Object> getAdditionsForCollection(
+      @Nullable Collection<?> oldCollection, Collection<?> newCollection) {
+    if (oldCollection == null) {
+      return ImmutableList.copyOf(newCollection);
+    }
 
     Map<Object, List<Object>> duplicatesMap = newCollection.stream().collect(groupingBy(v -> v));
     oldCollection.forEach(
@@ -173,7 +174,18 @@
 
   /** Returns {@code null} if nothing has been added to {@code oldMap} */
   @Nullable
-  private static ImmutableMap<Object, Object> getAddedForMap(Map<?, ?> oldMap, Map<?, ?> newMap) {
+  private static ImmutableMap<Object, Object> getAddedForMap(
+      @Nullable Map<?, ?> oldMap, Map<?, ?> newMap) {
+    ImmutableMap<Object, Object> notInOldMap = getAdditionsForMap(oldMap, newMap);
+    return notInOldMap.isEmpty() ? null : notInOldMap;
+  }
+
+  @Nullable
+  private static ImmutableMap<Object, Object> getAdditionsForMap(
+      @Nullable Map<?, ?> oldMap, Map<?, ?> newMap) {
+    if (oldMap == null) {
+      return ImmutableMap.copyOf(newMap);
+    }
     ImmutableMap.Builder<Object, Object> additionsBuilder = ImmutableMap.builder();
     for (Map.Entry<?, ?> entry : newMap.entrySet()) {
       Object added = getAdded(oldMap.get(entry.getKey()), entry.getValue());
@@ -181,8 +193,7 @@
         additionsBuilder.put(entry.getKey(), added);
       }
     }
-    ImmutableMap<Object, Object> additions = additionsBuilder.build();
-    return additions.isEmpty() ? null : additions;
+    return additionsBuilder.build();
   }
 
   private static Object get(Field field, Object obj) {
diff --git a/java/com/google/gerrit/server/change/ChangeJson.java b/java/com/google/gerrit/server/change/ChangeJson.java
index 500bb77..912d202 100644
--- a/java/com/google/gerrit/server/change/ChangeJson.java
+++ b/java/com/google/gerrit/server/change/ChangeJson.java
@@ -146,7 +146,7 @@
   public static final SubmitRuleOptions SUBMIT_RULE_OPTIONS_STRICT =
       ChangeField.SUBMIT_RULE_OPTIONS_STRICT.toBuilder().build();
 
-  static final ImmutableSet<ListChangesOption> REQUIRE_LAZY_LOAD =
+  public static final ImmutableSet<ListChangesOption> REQUIRE_LAZY_LOAD =
       ImmutableSet.of(
           ALL_COMMITS,
           ALL_REVISIONS,
@@ -688,6 +688,7 @@
             !cd.change().isAbandoned()
                 ? labelsJson.permittedLabels(user.getAccountId(), cd)
                 : ImmutableMap.of();
+        out.removableLabels = labelsJson.removableLabels(accountLoader, user, cd);
       }
     }
 
diff --git a/java/com/google/gerrit/server/change/LabelsJson.java b/java/com/google/gerrit/server/change/LabelsJson.java
index cfa15ae..5555ba6 100644
--- a/java/com/google/gerrit/server/change/LabelsJson.java
+++ b/java/com/google/gerrit/server/change/LabelsJson.java
@@ -36,15 +36,19 @@
 import com.google.gerrit.entities.LabelValue;
 import com.google.gerrit.entities.PatchSetApproval;
 import com.google.gerrit.entities.SubmitRecord;
+import com.google.gerrit.extensions.common.AccountInfo;
 import com.google.gerrit.extensions.common.ApprovalInfo;
 import com.google.gerrit.extensions.common.LabelInfo;
 import com.google.gerrit.extensions.common.VotingRangeInfo;
 import com.google.gerrit.server.ChangeUtil;
+import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.AccountLoader;
 import com.google.gerrit.server.notedb.ReviewerStateInternal;
 import com.google.gerrit.server.permissions.LabelPermission;
 import com.google.gerrit.server.permissions.PermissionBackend;
 import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.project.DeleteVoteControl;
+import com.google.gerrit.server.project.RemoveReviewerControl;
 import com.google.gerrit.server.query.change.ChangeData;
 import com.google.inject.Inject;
 import com.google.inject.Singleton;
@@ -69,10 +73,17 @@
   private static final FluentLogger logger = FluentLogger.forEnclosingClass();
 
   private final PermissionBackend permissionBackend;
+  private final DeleteVoteControl deleteVoteControl;
+  private final RemoveReviewerControl removeReviewerControl;
 
   @Inject
-  LabelsJson(PermissionBackend permissionBackend) {
+  LabelsJson(
+      PermissionBackend permissionBackend,
+      DeleteVoteControl deleteVoteControl,
+      RemoveReviewerControl removeReviewerControl) {
     this.permissionBackend = permissionBackend;
+    this.deleteVoteControl = deleteVoteControl;
+    this.removeReviewerControl = removeReviewerControl;
   }
 
   /**
@@ -133,6 +144,46 @@
     return permitted.asMap();
   }
 
+  /**
+   * Returns A map of all labels that the provided user has permission to remove.
+   *
+   * @param accountLoader to load the reviewers' data with.
+   * @param user a Gerrit user.
+   * @param cd {@link ChangeData} corresponding to a specific gerrit change.
+   * @return A Map of {@code labelName} -> {Map of {@code value} -> List of {@link AccountInfo}}
+   *     that the user can remove votes from.
+   */
+  Map<String, Map<String, List<AccountInfo>>> removableLabels(
+      AccountLoader accountLoader, CurrentUser user, ChangeData cd)
+      throws PermissionBackendException {
+    if (cd.change().isMerged()) {
+      return new HashMap<>();
+    }
+
+    Map<String, Map<String, List<AccountInfo>>> res = new HashMap<>();
+    LabelTypes labelTypes = cd.getLabelTypes();
+    for (PatchSetApproval approval : cd.currentApprovals()) {
+      Optional<LabelType> labelType = labelTypes.byLabel(approval.labelId());
+      if (!labelType.isPresent()) {
+        continue;
+      }
+      if (!(deleteVoteControl.testDeleteVotePermissions(user, cd, approval, labelType.get())
+          || removeReviewerControl.testRemoveReviewer(
+              cd, user, approval.accountId(), approval.value()))) {
+        continue;
+      }
+      if (!res.containsKey(approval.label())) {
+        res.put(approval.label(), new HashMap<>());
+      }
+      String labelValue = LabelValue.formatValue(approval.value());
+      if (!res.get(approval.label()).containsKey(labelValue)) {
+        res.get(approval.label()).put(labelValue, new ArrayList<>());
+      }
+      res.get(approval.label()).get(labelValue).add(accountLoader.get(approval.accountId()));
+    }
+    return res;
+  }
+
   private static void clearOnlyZerosEntries(SetMultimap<String, String> permitted) {
     List<String> toClear = Lists.newArrayListWithCapacity(permitted.keySet().size());
     for (Map.Entry<String, Collection<String>> e : permitted.asMap().entrySet()) {
@@ -217,10 +268,10 @@
     }
   }
 
-  private Map<String, Short> currentLabels(Account.Id accountId, ChangeData cd) {
+  private Map<String, Short> currentLabels(@Nullable Account.Id accountId, ChangeData cd) {
     Map<String, Short> result = new HashMap<>();
     for (PatchSetApproval psa : cd.currentApprovals()) {
-      if (psa.accountId().equals(accountId)) {
+      if (accountId == null || psa.accountId().equals(accountId)) {
         result.put(psa.label(), psa.value());
       }
     }
diff --git a/java/com/google/gerrit/server/permissions/AbstractLabelPermission.java b/java/com/google/gerrit/server/permissions/AbstractLabelPermission.java
new file mode 100644
index 0000000..622f0cf
--- /dev/null
+++ b/java/com/google/gerrit/server/permissions/AbstractLabelPermission.java
@@ -0,0 +1,155 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.permissions;
+
+import static com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser.ON_BEHALF_OF;
+import static java.util.Objects.requireNonNull;
+
+import com.google.gerrit.entities.LabelType;
+import com.google.gerrit.server.util.LabelVote;
+
+/** Abstract permission representing a label. */
+public abstract class AbstractLabelPermission implements ChangePermissionOrLabel {
+  public enum ForUser {
+    SELF,
+    ON_BEHALF_OF
+  }
+
+  protected final ForUser forUser;
+  protected final String name;
+
+  /**
+   * Construct a reference to an abstract label permission.
+   *
+   * @param forUser {@code SELF} (default) or {@code ON_BEHALF_OF} for labelAs behavior.
+   * @param name name of the label, e.g. {@code "Code-Review"} or {@code "Verified"}.
+   */
+  public AbstractLabelPermission(ForUser forUser, String name) {
+    this.forUser = requireNonNull(forUser, "ForUser");
+    this.name = LabelType.checkName(name);
+  }
+
+  /** Returns {@code SELF} or {@code ON_BEHALF_OF} (or labelAs). */
+  public ForUser forUser() {
+    return forUser;
+  }
+
+  /** Returns name of the label, e.g. {@code "Code-Review"}. */
+  public String label() {
+    return name;
+  }
+
+  protected abstract String permissionPrefix();
+
+  protected String permissionName() {
+    if (forUser == ON_BEHALF_OF) {
+      return permissionPrefix() + "As";
+    }
+    return permissionPrefix();
+  }
+
+  @Override
+  public final String describeForException() {
+    if (forUser == ON_BEHALF_OF) {
+      return permissionPrefix() + " on behalf of " + name;
+    }
+    return permissionPrefix() + " " + name;
+  }
+
+  @Override
+  public final int hashCode() {
+    return (permissionPrefix() + name).hashCode();
+  }
+
+  @Override
+  @SuppressWarnings("EqualsGetClass")
+  public final boolean equals(Object other) {
+    if (this.getClass().isAssignableFrom(other.getClass())) {
+      AbstractLabelPermission b = (AbstractLabelPermission) other;
+      return forUser == b.forUser && name.equals(b.name);
+    }
+    return false;
+  }
+
+  @Override
+  public final String toString() {
+    return permissionName() + "[" + name + ']';
+  }
+
+  /** A {@link AbstractLabelPermission} at a specific value. */
+  public abstract static class WithValue implements ChangePermissionOrLabel {
+    private final ForUser forUser;
+    private final LabelVote label;
+
+    /**
+     * Construct a reference to an abstract label permission at a specific value.
+     *
+     * @param forUser {@code SELF} (default) or {@code ON_BEHALF_OF} for labelAs behavior.
+     * @param label label name and vote.
+     */
+    public WithValue(ForUser forUser, LabelVote label) {
+      this.forUser = requireNonNull(forUser, "ForUser");
+      this.label = requireNonNull(label, "LabelVote");
+    }
+
+    /** Returns {@code SELF} or {@code ON_BEHALF_OF} (or labelAs). */
+    public ForUser forUser() {
+      return forUser;
+    }
+
+    /** Returns name of the label, e.g. {@code "Code-Review"}. */
+    public String label() {
+      return label.label();
+    }
+
+    /** Returns specific value of the label, e.g. 1 or 2. */
+    public short value() {
+      return label.value();
+    }
+
+    public abstract String permissionName();
+
+    @Override
+    public final String describeForException() {
+      if (forUser == ON_BEHALF_OF) {
+        return permissionName() + " on behalf of " + label.formatWithEquals();
+      }
+      return permissionName() + " " + label.formatWithEquals();
+    }
+
+    @Override
+    public final int hashCode() {
+      return (permissionName() + label).hashCode();
+    }
+
+    @Override
+    @SuppressWarnings("EqualsGetClass")
+    public final boolean equals(Object other) {
+      if (this.getClass().isAssignableFrom(other.getClass())) {
+        AbstractLabelPermission.WithValue b = (AbstractLabelPermission.WithValue) other;
+        return forUser == b.forUser && label.equals(b.label);
+      }
+      return false;
+    }
+
+    @Override
+    public final String toString() {
+      if (forUser == ON_BEHALF_OF) {
+        return permissionName() + "As[" + label.format() + ']';
+      }
+      return permissionName() + "[" + label.format() + ']';
+    }
+  }
+}
diff --git a/java/com/google/gerrit/server/permissions/ChangeControl.java b/java/com/google/gerrit/server/permissions/ChangeControl.java
index 8d432c8..6f7d761 100644
--- a/java/com/google/gerrit/server/permissions/ChangeControl.java
+++ b/java/com/google/gerrit/server/permissions/ChangeControl.java
@@ -14,8 +14,8 @@
 
 package com.google.gerrit.server.permissions;
 
+import static com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser.ON_BEHALF_OF;
 import static com.google.gerrit.server.permissions.DefaultPermissionMappings.labelPermissionName;
-import static com.google.gerrit.server.permissions.LabelPermission.ForUser.ON_BEHALF_OF;
 
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -240,10 +240,10 @@
     private boolean can(ChangePermissionOrLabel perm) throws PermissionBackendException {
       if (perm instanceof ChangePermission) {
         return can((ChangePermission) perm);
-      } else if (perm instanceof LabelPermission) {
-        return can((LabelPermission) perm);
-      } else if (perm instanceof LabelPermission.WithValue) {
-        return can((LabelPermission.WithValue) perm);
+      } else if (perm instanceof AbstractLabelPermission) {
+        return can((AbstractLabelPermission) perm);
+      } else if (perm instanceof AbstractLabelPermission.WithValue) {
+        return can((AbstractLabelPermission.WithValue) perm);
       }
       throw new PermissionBackendException(perm + " unsupported");
     }
@@ -288,11 +288,11 @@
       throw new PermissionBackendException(perm + " unsupported");
     }
 
-    private boolean can(LabelPermission perm) {
+    private boolean can(AbstractLabelPermission perm) {
       return !label(labelPermissionName(perm)).isEmpty();
     }
 
-    private boolean can(LabelPermission.WithValue perm) {
+    private boolean can(AbstractLabelPermission.WithValue perm) {
       PermissionRange r = label(labelPermissionName(perm));
       if (perm.forUser() == ON_BEHALF_OF && r.isEmpty()) {
         return false;
diff --git a/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java b/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
index 2824efd..f59ba02 100644
--- a/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
+++ b/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
@@ -16,5 +16,5 @@
 
 import com.google.gerrit.extensions.api.access.GerritPermission;
 
-/** A {@link ChangePermission} or a {@link LabelPermission}. */
+/** A {@link ChangePermission} or a {@link AbstractLabelPermission}. */
 public interface ChangePermissionOrLabel extends GerritPermission {}
diff --git a/java/com/google/gerrit/server/permissions/DefaultPermissionMappings.java b/java/com/google/gerrit/server/permissions/DefaultPermissionMappings.java
index 9d69d9b..89f0493 100644
--- a/java/com/google/gerrit/server/permissions/DefaultPermissionMappings.java
+++ b/java/com/google/gerrit/server/permissions/DefaultPermissionMappings.java
@@ -24,7 +24,7 @@
 import com.google.gerrit.extensions.api.access.GlobalOrPluginPermission;
 import com.google.gerrit.extensions.api.access.PluginPermission;
 import com.google.gerrit.extensions.api.access.PluginProjectPermission;
-import com.google.gerrit.server.permissions.LabelPermission.ForUser;
+import com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser;
 import java.util.EnumSet;
 import java.util.Optional;
 import java.util.Set;
@@ -160,19 +160,29 @@
     return Optional.ofNullable(CHANGE_PERMISSIONS.inverse().get(permissionName));
   }
 
-  public static String labelPermissionName(LabelPermission labelPermission) {
-    if (labelPermission.forUser() == ForUser.ON_BEHALF_OF) {
-      return Permission.forLabelAs(labelPermission.label());
+  public static String labelPermissionName(AbstractLabelPermission labelPermission) {
+    if (labelPermission instanceof LabelPermission) {
+      if (labelPermission.forUser() == ForUser.ON_BEHALF_OF) {
+        return Permission.forLabelAs(labelPermission.label());
+      }
+      return Permission.forLabel(labelPermission.label());
+    } else if (labelPermission instanceof LabelRemovalPermission) {
+      return Permission.forRemoveLabel(labelPermission.label());
     }
-    return Permission.forLabel(labelPermission.label());
+    throw new IllegalStateException("invalid AbstractLabelPermission subtype");
   }
 
   // TODO(dborowitz): Can these share a common superinterface?
-  public static String labelPermissionName(LabelPermission.WithValue labelPermission) {
-    if (labelPermission.forUser() == ForUser.ON_BEHALF_OF) {
-      return Permission.forLabelAs(labelPermission.label());
+  public static String labelPermissionName(AbstractLabelPermission.WithValue labelPermission) {
+    if (labelPermission instanceof LabelPermission.WithValue) {
+      if (labelPermission.forUser() == ForUser.ON_BEHALF_OF) {
+        return Permission.forLabelAs(labelPermission.label());
+      }
+      return Permission.forLabel(labelPermission.label());
+    } else if (labelPermission instanceof LabelRemovalPermission.WithValue) {
+      return Permission.forRemoveLabel(labelPermission.label());
     }
-    return Permission.forLabel(labelPermission.label());
+    throw new IllegalStateException("invalid AbstractLabelPermission.WithValue subtype");
   }
 
   private DefaultPermissionMappings() {}
diff --git a/java/com/google/gerrit/server/permissions/LabelPermission.java b/java/com/google/gerrit/server/permissions/LabelPermission.java
index c266caa..4652364 100644
--- a/java/com/google/gerrit/server/permissions/LabelPermission.java
+++ b/java/com/google/gerrit/server/permissions/LabelPermission.java
@@ -14,24 +14,14 @@
 
 package com.google.gerrit.server.permissions;
 
-import static com.google.gerrit.server.permissions.LabelPermission.ForUser.ON_BEHALF_OF;
-import static com.google.gerrit.server.permissions.LabelPermission.ForUser.SELF;
-import static java.util.Objects.requireNonNull;
+import static com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser.SELF;
 
 import com.google.gerrit.entities.LabelType;
 import com.google.gerrit.entities.LabelValue;
 import com.google.gerrit.server.util.LabelVote;
 
 /** Permission representing a label. */
-public class LabelPermission implements ChangePermissionOrLabel {
-  public enum ForUser {
-    SELF,
-    ON_BEHALF_OF;
-  }
-
-  private final ForUser forUser;
-  private final String name;
-
+public class LabelPermission extends AbstractLabelPermission {
   /**
    * Construct a reference to a label permission.
    *
@@ -67,55 +57,16 @@
    * @param name name of the label, e.g. {@code "Code-Review"} or {@code "Verified"}.
    */
   public LabelPermission(ForUser forUser, String name) {
-    this.forUser = requireNonNull(forUser, "ForUser");
-    this.name = LabelType.checkName(name);
-  }
-
-  /** Returns {@code SELF} or {@code ON_BEHALF_OF} (or labelAs). */
-  public ForUser forUser() {
-    return forUser;
-  }
-
-  /** Returns name of the label, e.g. {@code "Code-Review"}. */
-  public String label() {
-    return name;
+    super(forUser, name);
   }
 
   @Override
-  public String describeForException() {
-    if (forUser == ON_BEHALF_OF) {
-      return "label on behalf of " + name;
-    }
-    return "label " + name;
-  }
-
-  @Override
-  public int hashCode() {
-    return name.hashCode();
-  }
-
-  @Override
-  public boolean equals(Object other) {
-    if (other instanceof LabelPermission) {
-      LabelPermission b = (LabelPermission) other;
-      return forUser == b.forUser && name.equals(b.name);
-    }
-    return false;
-  }
-
-  @Override
-  public String toString() {
-    if (forUser == ON_BEHALF_OF) {
-      return "LabelAs[" + name + ']';
-    }
-    return "Label[" + name + ']';
+  public String permissionPrefix() {
+    return "label";
   }
 
   /** A {@link LabelPermission} at a specific value. */
-  public static class WithValue implements ChangePermissionOrLabel {
-    private final ForUser forUser;
-    private final LabelVote label;
-
+  public static class WithValue extends AbstractLabelPermission.WithValue {
     /**
      * Construct a reference to a label at a specific value.
      *
@@ -195,53 +146,12 @@
      * @param label label name and vote.
      */
     public WithValue(ForUser forUser, LabelVote label) {
-      this.forUser = requireNonNull(forUser, "ForUser");
-      this.label = requireNonNull(label, "LabelVote");
-    }
-
-    /** Returns {@code SELF} or {@code ON_BEHALF_OF} (or labelAs). */
-    public ForUser forUser() {
-      return forUser;
-    }
-
-    /** Returns name of the label, e.g. {@code "Code-Review"}. */
-    public String label() {
-      return label.label();
-    }
-
-    /** Returns specific value of the label, e.g. 1 or 2. */
-    public short value() {
-      return label.value();
+      super(forUser, label);
     }
 
     @Override
-    public String describeForException() {
-      if (forUser == ON_BEHALF_OF) {
-        return "label on behalf of " + label.formatWithEquals();
-      }
-      return "label " + label.formatWithEquals();
-    }
-
-    @Override
-    public int hashCode() {
-      return label.hashCode();
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (other instanceof WithValue) {
-        WithValue b = (WithValue) other;
-        return forUser == b.forUser && label.equals(b.label);
-      }
-      return false;
-    }
-
-    @Override
-    public String toString() {
-      if (forUser == ON_BEHALF_OF) {
-        return "LabelAs[" + label.format() + ']';
-      }
-      return "Label[" + label.format() + ']';
+    public String permissionName() {
+      return "label";
     }
   }
 }
diff --git a/java/com/google/gerrit/server/permissions/LabelRemovalPermission.java b/java/com/google/gerrit/server/permissions/LabelRemovalPermission.java
new file mode 100644
index 0000000..2553601
--- /dev/null
+++ b/java/com/google/gerrit/server/permissions/LabelRemovalPermission.java
@@ -0,0 +1,94 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.permissions;
+
+import static com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser.SELF;
+
+import com.google.gerrit.entities.LabelType;
+import com.google.gerrit.entities.LabelValue;
+import com.google.gerrit.server.util.LabelVote;
+
+/** Permission representing a label removal. */
+public class LabelRemovalPermission extends AbstractLabelPermission {
+  /**
+   * Construct a reference to a label removal permission.
+   *
+   * @param type type description of the label.
+   */
+  public LabelRemovalPermission(LabelType type) {
+    this(type.getName());
+  }
+
+  /**
+   * Construct a reference to a label removal permission.
+   *
+   * @param name name of the label, e.g. {@code "Code-Review"} or {@code "Verified"}.
+   */
+  public LabelRemovalPermission(String name) {
+    super(SELF, name);
+  }
+
+  @Override
+  public String permissionPrefix() {
+    return "removeLabel";
+  }
+
+  /** A {@link LabelRemovalPermission} at a specific value. */
+  public static class WithValue extends AbstractLabelPermission.WithValue {
+    /**
+     * Construct a reference to a label removal at a specific value.
+     *
+     * @param type description of the label.
+     * @param value numeric score assigned to the label.
+     */
+    public WithValue(LabelType type, LabelValue value) {
+      this(type.getName(), value.getValue());
+    }
+
+    /**
+     * Construct a reference to a label removal at a specific value.
+     *
+     * @param type description of the label.
+     * @param value numeric score assigned to the label.
+     */
+    public WithValue(LabelType type, short value) {
+      this(type.getName(), value);
+    }
+
+    /**
+     * Construct a reference to a label removal at a specific value.
+     *
+     * @param name name of the label, e.g. {@code "Code-Review"} or {@code "Verified"}.
+     * @param value numeric score assigned to the label.
+     */
+    public WithValue(String name, short value) {
+      this(LabelVote.create(name, value));
+    }
+
+    /**
+     * Construct a reference to a label removal at a specific value.
+     *
+     * @param label label name and vote.
+     */
+    public WithValue(LabelVote label) {
+      super(SELF, label);
+    }
+
+    @Override
+    public String permissionName() {
+      return "removeLabel";
+    }
+  }
+}
diff --git a/java/com/google/gerrit/server/permissions/PermissionBackend.java b/java/com/google/gerrit/server/permissions/PermissionBackend.java
index fea2827..eb5e053 100644
--- a/java/com/google/gerrit/server/permissions/PermissionBackend.java
+++ b/java/com/google/gerrit/server/permissions/PermissionBackend.java
@@ -474,6 +474,18 @@
     }
 
     /**
+     * Test which values of a label the user may be able to remove.
+     *
+     * @param label definition of the label to test values of.
+     * @return set containing values the user may be able to use; may be empty if none.
+     * @throws PermissionBackendException if failure consulting backend configuration.
+     */
+    public Set<LabelRemovalPermission.WithValue> testRemoval(LabelType label)
+        throws PermissionBackendException {
+      return test(removalValuesOf(requireNonNull(label, "LabelType")));
+    }
+
+    /**
      * Test which values of a group of labels the user may be able to set.
      *
      * @param types definition of the labels to test values of.
@@ -486,10 +498,29 @@
       return test(types.stream().flatMap(t -> valuesOf(t).stream()).collect(toSet()));
     }
 
+    /**
+     * Test which values of a group of labels the user may be able to remove.
+     *
+     * @param types definition of the labels to test values of.
+     * @return set containing values the user may be able to use; may be empty if none.
+     * @throws PermissionBackendException if failure consulting backend configuration.
+     */
+    public Set<LabelRemovalPermission.WithValue> testLabelRemovals(Collection<LabelType> types)
+        throws PermissionBackendException {
+      requireNonNull(types, "LabelType");
+      return test(types.stream().flatMap(t -> removalValuesOf(t).stream()).collect(toSet()));
+    }
+
     private static Set<LabelPermission.WithValue> valuesOf(LabelType label) {
       return label.getValues().stream()
           .map(v -> new LabelPermission.WithValue(label, v))
           .collect(toSet());
     }
+
+    private static Set<LabelRemovalPermission.WithValue> removalValuesOf(LabelType label) {
+      return label.getValues().stream()
+          .map(v -> new LabelRemovalPermission.WithValue(label, v))
+          .collect(toSet());
+    }
   }
 }
diff --git a/java/com/google/gerrit/server/project/DeleteVoteControl.java b/java/com/google/gerrit/server/project/DeleteVoteControl.java
new file mode 100644
index 0000000..3f3f88a
--- /dev/null
+++ b/java/com/google/gerrit/server/project/DeleteVoteControl.java
@@ -0,0 +1,81 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.project;
+
+import com.google.gerrit.entities.Account;
+import com.google.gerrit.entities.Change;
+import com.google.gerrit.entities.LabelType;
+import com.google.gerrit.entities.PatchSetApproval;
+import com.google.gerrit.server.CurrentUser;
+import com.google.gerrit.server.notedb.ChangeNotes;
+import com.google.gerrit.server.permissions.GlobalPermission;
+import com.google.gerrit.server.permissions.LabelRemovalPermission;
+import com.google.gerrit.server.permissions.PermissionBackend;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.permissions.RefPermission;
+import com.google.gerrit.server.query.change.ChangeData;
+import com.google.inject.Inject;
+import java.util.Set;
+
+public class DeleteVoteControl {
+  private final PermissionBackend permissionBackend;
+  private final ChangeData.Factory changeDataFactory;
+
+  @Inject
+  public DeleteVoteControl(
+      PermissionBackend permissionBackend, ChangeData.Factory changeDataFactory) {
+    this.permissionBackend = permissionBackend;
+    this.changeDataFactory = changeDataFactory;
+  }
+
+  public boolean testDeleteVotePermissions(
+      CurrentUser user, ChangeNotes notes, PatchSetApproval approval, LabelType labelType)
+      throws PermissionBackendException {
+    return testDeleteVotePermissions(user, changeDataFactory.create(notes), approval, labelType);
+  }
+
+  public boolean testDeleteVotePermissions(
+      CurrentUser user, ChangeData cd, PatchSetApproval approval, LabelType labelType)
+      throws PermissionBackendException {
+    if (canRemoveReviewerWithoutRemoveLabelPermission(
+        cd.change(), user, approval.accountId(), approval.value())) {
+      return true;
+    }
+    // Test if the user is allowed to remove vote of the given label type and value.
+    Set<LabelRemovalPermission.WithValue> allowed =
+        permissionBackend.user(user).change(cd).testRemoval(labelType);
+    return allowed.contains(new LabelRemovalPermission.WithValue(labelType, approval.value()));
+  }
+
+  private boolean canRemoveReviewerWithoutRemoveLabelPermission(
+      Change change, CurrentUser user, Account.Id reviewer, int value)
+      throws PermissionBackendException {
+    if (user.isIdentifiedUser()) {
+      Account.Id aId = user.getAccountId();
+      if (aId.equals(reviewer)) {
+        return true; // A user can always remove their own votes.
+      } else if (aId.equals(change.getOwner()) && 0 <= value) {
+        return true; // The change owner may remove any zero or positive score.
+      }
+    }
+
+    // Users with the remove reviewer permission, the branch owner, project
+    // owner and site admin can remove anyone
+    PermissionBackend.WithUser withUser = permissionBackend.user(user);
+    PermissionBackend.ForProject forProject = withUser.project(change.getProject());
+    return forProject.ref(change.getDest().branch()).test(RefPermission.WRITE_CONFIG)
+        || withUser.test(GlobalPermission.ADMINISTRATE_SERVER);
+  }
+}
diff --git a/java/com/google/gerrit/server/project/RemoveReviewerControl.java b/java/com/google/gerrit/server/project/RemoveReviewerControl.java
index 1bc309c..3fda87a 100644
--- a/java/com/google/gerrit/server/project/RemoveReviewerControl.java
+++ b/java/com/google/gerrit/server/project/RemoveReviewerControl.java
@@ -32,10 +32,12 @@
 @Singleton
 public class RemoveReviewerControl {
   private final PermissionBackend permissionBackend;
+  private final ChangeData.Factory changeDataFactory;
 
   @Inject
-  RemoveReviewerControl(PermissionBackend permissionBackend) {
+  RemoveReviewerControl(PermissionBackend permissionBackend, ChangeData.Factory changeDataFactory) {
     this.permissionBackend = permissionBackend;
+    this.changeDataFactory = changeDataFactory;
   }
 
   /**
@@ -64,6 +66,20 @@
 
   /** Returns true if the user is allowed to remove this reviewer. */
   public boolean testRemoveReviewer(
+      ChangeNotes notes, CurrentUser currentUser, PatchSetApproval approval)
+      throws PermissionBackendException {
+    return testRemoveReviewer(notes, currentUser, approval.accountId(), approval.value());
+  }
+
+  /** Returns true if the user is allowed to remove this reviewer. */
+  public boolean testRemoveReviewer(
+      ChangeNotes notes, CurrentUser currentUser, Account.Id reviewer, int value)
+      throws PermissionBackendException {
+    return testRemoveReviewer(changeDataFactory.create(notes), currentUser, reviewer, value);
+  }
+
+  /** Returns true if the user is allowed to remove this reviewer. */
+  public boolean testRemoveReviewer(
       ChangeData cd, CurrentUser currentUser, Account.Id reviewer, int value)
       throws PermissionBackendException {
     if (canRemoveReviewerWithoutPermissionCheck(
diff --git a/java/com/google/gerrit/server/restapi/change/DeleteVoteOp.java b/java/com/google/gerrit/server/restapi/change/DeleteVoteOp.java
index a0fc121..0e1a218 100644
--- a/java/com/google/gerrit/server/restapi/change/DeleteVoteOp.java
+++ b/java/com/google/gerrit/server/restapi/change/DeleteVoteOp.java
@@ -20,6 +20,7 @@
 import com.google.common.flogger.FluentLogger;
 import com.google.gerrit.entities.Account;
 import com.google.gerrit.entities.Change;
+import com.google.gerrit.entities.LabelType;
 import com.google.gerrit.entities.LabelTypes;
 import com.google.gerrit.entities.PatchSet;
 import com.google.gerrit.entities.PatchSetApproval;
@@ -37,7 +38,9 @@
 import com.google.gerrit.server.mail.send.DeleteVoteSender;
 import com.google.gerrit.server.mail.send.MessageIdGenerator;
 import com.google.gerrit.server.mail.send.ReplyToChangeSender;
+import com.google.gerrit.server.permissions.LabelRemovalPermission;
 import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.project.DeleteVoteControl;
 import com.google.gerrit.server.project.ProjectCache;
 import com.google.gerrit.server.project.RemoveReviewerControl;
 import com.google.gerrit.server.update.BatchUpdateOp;
@@ -75,6 +78,7 @@
   private final VoteDeleted voteDeleted;
   private final DeleteVoteSender.Factory deleteVoteSenderFactory;
 
+  private final DeleteVoteControl deleteVoteControl;
   private final RemoveReviewerControl removeReviewerControl;
   private final MessageIdGenerator messageIdGenerator;
 
@@ -96,8 +100,9 @@
       ChangeMessagesUtil cmUtil,
       VoteDeleted voteDeleted,
       DeleteVoteSender.Factory deleteVoteSenderFactory,
-      RemoveReviewerControl removeReviewerControl,
+      DeleteVoteControl deleteVoteControl,
       MessageIdGenerator messageIdGenerator,
+      RemoveReviewerControl removeReviewerControl,
       @Assisted Project.NameKey projectName,
       @Assisted AccountState reviewerToDeleteVoteFor,
       @Assisted String label,
@@ -109,6 +114,7 @@
     this.cmUtil = cmUtil;
     this.voteDeleted = voteDeleted;
     this.deleteVoteSenderFactory = deleteVoteSenderFactory;
+    this.deleteVoteControl = deleteVoteControl;
     this.removeReviewerControl = removeReviewerControl;
     this.messageIdGenerator = messageIdGenerator;
 
@@ -143,12 +149,7 @@
         newApprovals.put(a.label(), a.value());
         continue;
       } else if (enforcePermissions) {
-        // For regular users, check if they are allowed to remove the vote.
-        try {
-          removeReviewerControl.checkRemoveReviewer(ctx.getNotes(), ctx.getUser(), a);
-        } catch (AuthException e) {
-          throw new AuthException("delete vote not permitted", e);
-        }
+        checkPermissions(ctx, labelTypes.byLabel(a.labelId()).get(), a);
       }
       // Set the approval to 0 if vote is being removed.
       newApprovals.put(a.label(), (short) 0);
@@ -209,4 +210,21 @@
         user.isIdentifiedUser() ? user.asIdentifiedUser().state() : null,
         ctx.getWhen());
   }
+
+  private void checkPermissions(ChangeContext ctx, LabelType labelType, PatchSetApproval approval)
+      throws PermissionBackendException, AuthException {
+    boolean permitted =
+        removeReviewerControl.testRemoveReviewer(ctx.getNotes(), ctx.getUser(), approval)
+            || deleteVoteControl.testDeleteVotePermissions(
+                ctx.getUser(), ctx.getNotes(), approval, labelType);
+    if (!permitted) {
+      throw new AuthException(
+          "Delete vote not permitted.",
+          new AuthException(
+              "Both "
+                  + new LabelRemovalPermission.WithValue(labelType, approval.value())
+                      .describeForException()
+                  + " and remove-reviewer are not permitted"));
+    }
+  }
 }
diff --git a/java/com/google/gerrit/server/restapi/change/PostReview.java b/java/com/google/gerrit/server/restapi/change/PostReview.java
index 259e71d..22eb32c 100644
--- a/java/com/google/gerrit/server/restapi/change/PostReview.java
+++ b/java/com/google/gerrit/server/restapi/change/PostReview.java
@@ -17,7 +17,7 @@
 import static com.google.common.base.MoreObjects.firstNonNull;
 import static com.google.common.collect.ImmutableSet.toImmutableSet;
 import static com.google.gerrit.entities.Patch.PATCHSET_LEVEL;
-import static com.google.gerrit.server.permissions.LabelPermission.ForUser.ON_BEHALF_OF;
+import static com.google.gerrit.server.permissions.AbstractLabelPermission.ForUser.ON_BEHALF_OF;
 import static com.google.gerrit.server.project.ProjectCache.illegalState;
 import static java.nio.charset.StandardCharsets.UTF_8;
 import static java.util.stream.Collectors.groupingBy;
diff --git a/javatests/com/google/gerrit/acceptance/api/change/ChangeIT.java b/javatests/com/google/gerrit/acceptance/api/change/ChangeIT.java
index 211baeb..215d1e8 100644
--- a/javatests/com/google/gerrit/acceptance/api/change/ChangeIT.java
+++ b/javatests/com/google/gerrit/acceptance/api/change/ChangeIT.java
@@ -28,6 +28,7 @@
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allowLabel;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.block;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.blockLabel;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.blockLabelRemoval;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.labelPermissionKey;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.permissionKey;
 import static com.google.gerrit.entities.RefNames.changeMetaRef;
@@ -160,6 +161,7 @@
 import com.google.gerrit.index.query.PostFilterPredicate;
 import com.google.gerrit.server.ChangeMessagesUtil;
 import com.google.gerrit.server.account.AccountControl;
+import com.google.gerrit.server.change.ChangeJson;
 import com.google.gerrit.server.change.ChangeMessages;
 import com.google.gerrit.server.change.ChangeResource;
 import com.google.gerrit.server.change.testing.TestChangeETagComputation;
@@ -2406,7 +2408,68 @@
                     .id(r.getChangeId())
                     .reviewer(admin.id().toString())
                     .deleteVote(LabelId.CODE_REVIEW));
-    assertThat(thrown).hasMessageThat().contains("delete vote not permitted");
+    assertThat(thrown).hasMessageThat().contains("Delete vote not permitted");
+  }
+
+  @Test
+  public void deleteVoteAlwaysPermittedForSelfVotes() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            allowLabel(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/heads/*").group(REGISTERED_USERS))
+        .update();
+
+    PushOneCommit.Result r = createChange();
+    String changeId = r.getChangeId();
+
+    requestScopeOperations.setApiUser(user.id());
+    gApi.changes().id(changeId).revision(r.getCommit().name()).review(ReviewInput.approve());
+
+    gApi.changes()
+        .id(r.getChangeId())
+        .reviewer(user.id().toString())
+        .deleteVote(LabelId.CODE_REVIEW);
+  }
+
+  @Test
+  public void deleteVoteAlwaysPermittedForAdmin() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            allowLabel(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/heads/*").group(REGISTERED_USERS))
+        .update();
+
+    PushOneCommit.Result r = createChange();
+    String changeId = r.getChangeId();
+
+    requestScopeOperations.setApiUser(user.id());
+    gApi.changes().id(changeId).revision(r.getCommit().name()).review(ReviewInput.approve());
+
+    requestScopeOperations.setApiUser(admin.id());
+    gApi.changes()
+        .id(r.getChangeId())
+        .reviewer(user.id().toString())
+        .deleteVote(LabelId.CODE_REVIEW);
   }
 
   @Test
@@ -2996,7 +3059,11 @@
         .review(ReviewInput.approve());
     gApi.changes().id(r1.getChangeId()).revision(r1.getCommit().name()).submit();
 
-    createChange();
+    PushOneCommit.Result change = createChange();
+    // Populate change with a reasonable set of fields. We can't exhaustively
+    // test all possible variations, but can try to cover a reasonable set.
+    approve(change.getChangeId());
+    gApi.changes().id(change.getChangeId()).addReviewer(user.email());
 
     requestScopeOperations.setApiUser(user.id());
     try (AutoCloseable ignored = disableNoteDb()) {
@@ -3011,6 +3078,34 @@
   }
 
   @Test
+  public void nonLazyloadQueryOptionsDoNotTouchDatabase() throws Exception {
+    requestScopeOperations.setApiUser(admin.id());
+    PushOneCommit.Result r1 = createChange();
+    gApi.changes()
+        .id(r1.getChangeId())
+        .revision(r1.getCommit().name())
+        .review(ReviewInput.approve());
+    gApi.changes().id(r1.getChangeId()).revision(r1.getCommit().name()).submit();
+
+    PushOneCommit.Result change = createChange();
+    // Populate change with a reasonable set of fields. We can't exhaustively
+    // test all possible variations, but can try to cover a reasonable set.
+    approve(change.getChangeId());
+    gApi.changes().id(change.getChangeId()).addReviewer(user.email());
+
+    requestScopeOperations.setApiUser(user.id());
+    try (AutoCloseable ignored = disableNoteDb()) {
+      assertThat(
+              gApi.changes()
+                  .query()
+                  .withQuery("project:{" + project.get() + "} (status:open OR status:closed)")
+                  .withOptions(EnumSet.complementOf(EnumSet.copyOf(ChangeJson.REQUIRE_LAZY_LOAD)))
+                  .get())
+          .hasSize(2);
+    }
+  }
+
+  @Test
   public void votable() throws Exception {
     PushOneCommit.Result r = createChange();
     String triplet = project.get() + "~master~" + r.getChangeId();
@@ -3275,6 +3370,7 @@
     assertThat(change.status).isEqualTo(ChangeStatus.NEW);
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertThat(change.permittedLabels.keySet()).containsExactly(LabelId.CODE_REVIEW);
+    assertThat(change.removableLabels).isEmpty();
 
     // add new label and assert that it's returned for existing changes
     AccountGroup.UUID registeredUsers = systemGroupBackend.getGroup(REGISTERED_USERS).getUUID();
@@ -3304,6 +3400,9 @@
         .id(r.getChangeId())
         .revision(r.getCommit().name())
         .review(new ReviewInput().label(verified.getName(), verified.getMax().getValue()));
+    change = gApi.changes().id(r.getChangeId()).get();
+    assertPermitted(change, LabelId.VERIFIED, -1, 0, 1);
+    assertOnlyRemovableLabel(change, LabelId.VERIFIED, "+1", admin);
 
     try (ProjectConfigUpdate u = updateProject(project)) {
       // remove label and assert that it's no longer returned for existing
@@ -3323,6 +3422,7 @@
     change = gApi.changes().id(r.getChangeId()).get();
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertThat(change.permittedLabels.keySet()).containsExactly(LabelId.CODE_REVIEW);
+    assertThat(change.removableLabels).isEmpty();
 
     // abandon the change and see that the returned labels stay the same
     // while all permitted labels disappear.
@@ -3331,6 +3431,7 @@
     assertThat(change.status).isEqualTo(ChangeStatus.ABANDONED);
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertThat(change.permittedLabels).isEmpty();
+    assertThat(change.removableLabels).isEmpty();
   }
 
   @Test
@@ -3447,6 +3548,7 @@
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW, LabelId.VERIFIED);
     assertPermitted(change, LabelId.CODE_REVIEW, 2);
     assertPermitted(change, LabelId.VERIFIED, 1);
+    assertThat(change.removableLabels).isEmpty();
 
     // remove label and assert that it's no longer returned for existing
     // changes, even if there is an approval for it
@@ -3464,6 +3566,7 @@
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertThat(change.permittedLabels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertPermitted(change, LabelId.CODE_REVIEW, 2);
+    assertThat(change.removableLabels).isEmpty();
   }
 
   @Test
@@ -3560,6 +3663,7 @@
         .containsExactly(LabelId.CODE_REVIEW, "Non-Author-Code-Review");
     assertThat(change.permittedLabels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertPermitted(change, LabelId.CODE_REVIEW, 0, 1, 2);
+    assertThat(change.removableLabels).isEmpty();
   }
 
   @Test
@@ -3575,6 +3679,7 @@
     assertThat(change.submissionId).isNotNull();
     assertThat(change.labels.keySet()).containsExactly(LabelId.CODE_REVIEW);
     assertPermitted(change, LabelId.CODE_REVIEW, 0, 1, 2);
+    assertThat(change.removableLabels).isEmpty();
   }
 
   @Test
@@ -4281,8 +4386,12 @@
             ListChangesOption.SKIP_DIFFSTAT);
 
     PushOneCommit.Result change = createChange();
-    int number = gApi.changes().id(change.getChangeId()).get()._number;
+    // Populate change with a reasonable set of fields. We can't exhaustively
+    // test all possible variations, but can try to cover a reasonable set.
+    approve(change.getChangeId());
+    gApi.changes().id(change.getChangeId()).addReviewer(user.email());
 
+    int number = gApi.changes().id(change.getChangeId()).get()._number;
     try (AutoCloseable ignored = changeIndexOperations.disableReadsAndWrites()) {
       assertThat(gApi.changes().id(project.get(), number).get(options).changeId)
           .isEqualTo(change.getChangeId());
diff --git a/javatests/com/google/gerrit/acceptance/rest/change/DeleteVoteIT.java b/javatests/com/google/gerrit/acceptance/rest/change/DeleteVoteIT.java
index c57d285..016b1e6 100644
--- a/javatests/com/google/gerrit/acceptance/rest/change/DeleteVoteIT.java
+++ b/javatests/com/google/gerrit/acceptance/rest/change/DeleteVoteIT.java
@@ -15,16 +15,24 @@
 package com.google.gerrit.acceptance.rest.change;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allow;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allowLabelRemoval;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.block;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.blockLabelRemoval;
 import static com.google.gerrit.extensions.client.ReviewerState.REVIEWER;
+import static com.google.gerrit.server.group.SystemGroupBackend.REGISTERED_USERS;
 
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
 import com.google.gerrit.acceptance.PushOneCommit;
 import com.google.gerrit.acceptance.RestResponse;
+import com.google.gerrit.acceptance.TestAccount;
+import com.google.gerrit.acceptance.testsuite.project.ProjectOperations;
 import com.google.gerrit.acceptance.testsuite.request.RequestScopeOperations;
 import com.google.gerrit.entities.Account;
 import com.google.gerrit.entities.LabelId;
+import com.google.gerrit.entities.Permission;
 import com.google.gerrit.extensions.api.changes.ReviewInput;
 import com.google.gerrit.extensions.common.AccountInfo;
 import com.google.gerrit.extensions.common.ChangeInfo;
@@ -39,56 +47,141 @@
 import org.junit.Test;
 
 public class DeleteVoteIT extends AbstractDaemonTest {
+  @Inject private ProjectOperations projectOperations;
   @Inject private RequestScopeOperations requestScopeOperations;
 
   @Test
-  public void deleteVoteOnChange() throws Exception {
-    deleteVote(false);
+  public void deleteVoteOnChange_withRemoveLabelPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            allowLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyDeleteVote(false);
   }
 
   @Test
-  public void deleteVoteOnRevision() throws Exception {
-    deleteVote(true);
+  public void deleteVoteOnChange_withRemoveReviewerPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(allow(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyDeleteVote(false);
   }
 
-  private void deleteVote(boolean onRevisionLevel) throws Exception {
+  @Test
+  public void deleteVoteOnChange_noPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyCannotDeleteVote(false);
+  }
+
+  @Test
+  public void deleteVoteOnRevision_withRemoveLabelPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            allowLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyDeleteVote(true);
+  }
+
+  @Test
+  public void deleteVoteOnRevision_withRemoveReviewerPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(allow(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyDeleteVote(true);
+  }
+
+  @Test
+  public void deleteVoteOnRevision_noPermission() throws Exception {
+    projectOperations
+        .project(project)
+        .forUpdate()
+        .add(
+            blockLabelRemoval(LabelId.CODE_REVIEW)
+                .ref("refs/heads/*")
+                .group(REGISTERED_USERS)
+                .range(-2, 2))
+        .add(block(Permission.REMOVE_REVIEWER).ref("refs/*").group(REGISTERED_USERS))
+        .update();
+    verifyCannotDeleteVote(true);
+  }
+
+  private void verifyDeleteVote(boolean onRevisionLevel) throws Exception {
     PushOneCommit.Result r = createChange();
     gApi.changes().id(r.getChangeId()).revision(r.getCommit().name()).review(ReviewInput.approve());
 
     PushOneCommit.Result r2 = amendChange(r.getChangeId());
 
-    requestScopeOperations.setApiUser(user.id());
+    requestScopeOperations.setApiUser(admin.id());
+    recommend(r.getChangeId());
+
+    TestAccount user2 = accountCreator.user2();
+    requestScopeOperations.setApiUser(user2.id());
     recommend(r.getChangeId());
 
     sender.clear();
-    String endPoint =
+    String deleteAdminVoteEndPoint =
         "/changes/"
             + r.getChangeId()
             + (onRevisionLevel ? ("/revisions/" + r2.getCommit().getName()) : "")
             + "/reviewers/"
-            + user.id().toString()
+            + admin.id().toString()
             + "/votes/Code-Review";
 
-    RestResponse response = adminRestSession.delete(endPoint);
+    RestResponse response = userRestSession.delete(deleteAdminVoteEndPoint);
     response.assertNoContent();
 
     List<FakeEmailSender.Message> messages = sender.getMessages();
     assertThat(messages).hasSize(1);
     FakeEmailSender.Message msg = messages.get(0);
-    assertThat(msg.rcpt()).containsExactly(user.getNameEmail());
-    assertThat(msg.body()).contains(admin.fullName() + " has removed a vote from this change.");
+    assertThat(msg.rcpt()).containsExactly(admin.getNameEmail(), user2.getNameEmail());
+    assertThat(msg.body()).contains(user.fullName() + " has removed a vote from this change.");
     assertThat(msg.body())
-        .contains("Removed Code-Review+1 by " + user.fullName() + " <" + user.email() + ">\n");
+        .contains("Removed Code-Review+1 by " + admin.fullName() + " <" + admin.email() + ">\n");
 
-    endPoint =
+    String viewVotesEndPoint =
         "/changes/"
             + r.getChangeId()
             + (onRevisionLevel ? ("/revisions/" + r2.getCommit().getName()) : "")
             + "/reviewers/"
-            + user.id().toString()
+            + admin.id().toString()
             + "/votes";
 
-    response = adminRestSession.get(endPoint);
+    response = userRestSession.get(viewVotesEndPoint);
     response.assertOK();
 
     Map<String, Short> m =
@@ -99,14 +192,38 @@
     ChangeInfo c = gApi.changes().id(r.getChangeId()).get();
 
     ChangeMessageInfo message = Iterables.getLast(c.messages);
-    assertThat(message.author._accountId).isEqualTo(admin.id().get());
+    assertThat(message.author._accountId).isEqualTo(user.id().get());
     assertThat(message.message)
         .isEqualTo(
             String.format(
                 "Removed Code-Review+1 by %s\n",
-                AccountTemplateUtil.getAccountTemplate(user.id())));
+                AccountTemplateUtil.getAccountTemplate(admin.id())));
     assertThat(getReviewers(c.reviewers.get(REVIEWER)))
-        .containsExactlyElementsIn(ImmutableSet.of(admin.id(), user.id()));
+        .containsExactlyElementsIn(ImmutableSet.of(user2.id(), admin.id()));
+  }
+
+  private void verifyCannotDeleteVote(boolean onRevisionLevel) throws Exception {
+    PushOneCommit.Result r = createChange();
+    gApi.changes().id(r.getChangeId()).revision(r.getCommit().name()).review(ReviewInput.approve());
+
+    PushOneCommit.Result r2 = amendChange(r.getChangeId());
+
+    requestScopeOperations.setApiUser(admin.id());
+    recommend(r.getChangeId());
+
+    sender.clear();
+    String deleteAdminVoteEndPoint =
+        "/changes/"
+            + r.getChangeId()
+            + (onRevisionLevel ? ("/revisions/" + r2.getCommit().getName()) : "")
+            + "/reviewers/"
+            + admin.id().toString()
+            + "/votes/Code-Review";
+
+    RestResponse response = userRestSession.delete(deleteAdminVoteEndPoint);
+    response.assertForbidden();
+
+    assertThat(sender.getMessages()).isEmpty();
   }
 
   private Iterable<Account.Id> getReviewers(Collection<AccountInfo> r) {
diff --git a/javatests/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImplTest.java b/javatests/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImplTest.java
index c1a7627..661802e 100644
--- a/javatests/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImplTest.java
+++ b/javatests/com/google/gerrit/acceptance/testsuite/project/ProjectOperationsImplTest.java
@@ -18,11 +18,14 @@
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allow;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allowCapability;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allowLabel;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.allowLabelRemoval;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.block;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.blockLabel;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.blockLabelRemoval;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.capabilityKey;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.deny;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.labelPermissionKey;
+import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.labelRemovalPermissionKey;
 import static com.google.gerrit.acceptance.testsuite.project.TestProjectUpdate.permissionKey;
 import static com.google.gerrit.common.data.GlobalCapability.ADMINISTRATE_SERVER;
 import static com.google.gerrit.common.data.GlobalCapability.DEFAULT_MAX_QUERY_LIMIT;
@@ -443,6 +446,73 @@
   }
 
   @Test
+  public void addAllowLabelRemovalPermission() throws Exception {
+    Project.NameKey key = projectOperations.newProject().create();
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .add(allowLabelRemoval("Code-Review").ref("refs/foo").group(REGISTERED_USERS).range(-1, 2))
+        .update();
+
+    Config config = projectOperations.project(key).getConfig();
+    assertThat(config).sections().containsExactly("access", "submit");
+    assertThat(config).subsections("access").containsExactly("refs/foo");
+    assertThat(config)
+        .subsectionValues("access", "refs/foo")
+        .containsExactly("removeLabel-Code-Review", "-1..+2 group global:Registered-Users");
+  }
+
+  @Test
+  public void addBlockLabelRemovalPermission() throws Exception {
+    Project.NameKey key = projectOperations.newProject().create();
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .add(blockLabelRemoval("Code-Review").ref("refs/foo").group(REGISTERED_USERS).range(-1, 2))
+        .update();
+
+    Config config = projectOperations.project(key).getConfig();
+    assertThat(config).sections().containsExactly("access", "submit");
+    assertThat(config).subsections("access").containsExactly("refs/foo");
+    assertThat(config)
+        .subsectionValues("access", "refs/foo")
+        .containsExactly("removeLabel-Code-Review", "block -1..+2 group global:Registered-Users");
+  }
+
+  @Test
+  public void addAllowExclusiveLabelRemovalPermission() throws Exception {
+    Project.NameKey key = projectOperations.newProject().create();
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .add(allowLabelRemoval("Code-Review").ref("refs/foo").group(REGISTERED_USERS).range(-1, 2))
+        .setExclusiveGroup(labelRemovalPermissionKey("Code-Review").ref("refs/foo"), true)
+        .update();
+
+    Config config = projectOperations.project(key).getConfig();
+    assertThat(config).sections().containsExactly("access", "submit");
+    assertThat(config).subsections("access").containsExactly("refs/foo");
+    assertThat(config)
+        .subsectionValues("access", "refs/foo")
+        .containsExactly(
+            "removeLabel-Code-Review", "-1..+2 group global:Registered-Users",
+            "exclusiveGroupPermissions", "removeLabel-Code-Review");
+
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .setExclusiveGroup(labelRemovalPermissionKey("Code-Review").ref("refs/foo"), false)
+        .update();
+
+    config = projectOperations.project(key).getConfig();
+    assertThat(config).sections().containsExactly("access", "submit");
+    assertThat(config).subsections("access").containsExactly("refs/foo");
+    assertThat(config)
+        .subsectionValues("access", "refs/foo")
+        .containsExactly("removeLabel-Code-Review", "-1..+2 group global:Registered-Users");
+  }
+
+  @Test
   public void addAllowCapability() throws Exception {
     Config config = projectOperations.project(allProjects).getConfig();
     assertThat(config)
@@ -540,6 +610,31 @@
   }
 
   @Test
+  public void removeLabelRemovalPermission() throws Exception {
+    Project.NameKey key = projectOperations.newProject().create();
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .add(allowLabelRemoval("Code-Review").ref("refs/foo").group(REGISTERED_USERS).range(-1, 2))
+        .add(allowLabelRemoval("Code-Review").ref("refs/foo").group(PROJECT_OWNERS).range(-2, 1))
+        .update();
+    assertThat(projectOperations.project(key).getConfig())
+        .subsectionValues("access", "refs/foo")
+        .containsExactly(
+            "removeLabel-Code-Review", "-1..+2 group global:Registered-Users",
+            "removeLabel-Code-Review", "-2..+1 group global:Project-Owners");
+
+    projectOperations
+        .project(key)
+        .forUpdate()
+        .remove(labelRemovalPermissionKey("Code-Review").ref("refs/foo").group(REGISTERED_USERS))
+        .update();
+    assertThat(projectOperations.project(key).getConfig())
+        .subsectionValues("access", "refs/foo")
+        .containsExactly("removeLabel-Code-Review", "-2..+1 group global:Project-Owners");
+  }
+
+  @Test
   public void removeCapability() throws Exception {
     projectOperations
         .allProjectsForUpdate()
diff --git a/javatests/com/google/gerrit/entities/PermissionTest.java b/javatests/com/google/gerrit/entities/PermissionTest.java
index 3175671..d25d833 100644
--- a/javatests/com/google/gerrit/entities/PermissionTest.java
+++ b/javatests/com/google/gerrit/entities/PermissionTest.java
@@ -36,6 +36,7 @@
 
     assertThat(Permission.isPermission(Permission.LABEL + LabelId.CODE_REVIEW)).isTrue();
     assertThat(Permission.isPermission(Permission.LABEL_AS + LabelId.CODE_REVIEW)).isTrue();
+    assertThat(Permission.isPermission(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW)).isTrue();
     assertThat(Permission.isPermission(LabelId.CODE_REVIEW)).isFalse();
   }
 
@@ -56,6 +57,7 @@
 
     assertThat(Permission.isLabel(Permission.LABEL + LabelId.CODE_REVIEW)).isTrue();
     assertThat(Permission.isLabel(Permission.LABEL_AS + LabelId.CODE_REVIEW)).isFalse();
+    assertThat(Permission.isLabel(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW)).isFalse();
     assertThat(Permission.isLabel(LabelId.CODE_REVIEW)).isFalse();
   }
 
@@ -66,10 +68,22 @@
 
     assertThat(Permission.isLabelAs(Permission.LABEL + LabelId.CODE_REVIEW)).isFalse();
     assertThat(Permission.isLabelAs(Permission.LABEL_AS + LabelId.CODE_REVIEW)).isTrue();
+    assertThat(Permission.isLabelAs(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW)).isFalse();
     assertThat(Permission.isLabelAs(LabelId.CODE_REVIEW)).isFalse();
   }
 
   @Test
+  public void isRemoveLabel() {
+    assertThat(Permission.isRemoveLabel(Permission.ABANDON)).isFalse();
+    assertThat(Permission.isRemoveLabel("no-permission")).isFalse();
+
+    assertThat(Permission.isRemoveLabel(Permission.LABEL + LabelId.CODE_REVIEW)).isFalse();
+    assertThat(Permission.isRemoveLabel(Permission.LABEL_AS + LabelId.CODE_REVIEW)).isFalse();
+    assertThat(Permission.isRemoveLabel(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW)).isTrue();
+    assertThat(Permission.isRemoveLabel(LabelId.CODE_REVIEW)).isFalse();
+  }
+
+  @Test
   public void forLabel() {
     assertThat(Permission.forLabel(LabelId.CODE_REVIEW))
         .isEqualTo(Permission.LABEL + LabelId.CODE_REVIEW);
@@ -82,11 +96,19 @@
   }
 
   @Test
+  public void forRemoveLabel() {
+    assertThat(Permission.forRemoveLabel(LabelId.CODE_REVIEW))
+        .isEqualTo(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW);
+  }
+
+  @Test
   public void extractLabel() {
     assertThat(Permission.extractLabel(Permission.LABEL + LabelId.CODE_REVIEW))
         .isEqualTo(LabelId.CODE_REVIEW);
     assertThat(Permission.extractLabel(Permission.LABEL_AS + LabelId.CODE_REVIEW))
         .isEqualTo(LabelId.CODE_REVIEW);
+    assertThat(Permission.extractLabel(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW))
+        .isEqualTo(LabelId.CODE_REVIEW);
     assertThat(Permission.extractLabel(LabelId.CODE_REVIEW)).isNull();
     assertThat(Permission.extractLabel(Permission.ABANDON)).isNull();
   }
@@ -103,6 +125,10 @@
             Permission.canBeOnAllProjects(
                 AccessSection.ALL, Permission.LABEL_AS + LabelId.CODE_REVIEW))
         .isTrue();
+    assertThat(
+            Permission.canBeOnAllProjects(
+                AccessSection.ALL, Permission.REMOVE_LABEL + LabelId.CODE_REVIEW))
+        .isTrue();
 
     assertThat(Permission.canBeOnAllProjects("refs/heads/*", Permission.ABANDON)).isTrue();
     assertThat(Permission.canBeOnAllProjects("refs/heads/*", Permission.OWNER)).isTrue();
@@ -113,6 +139,10 @@
             Permission.canBeOnAllProjects(
                 "refs/heads/*", Permission.LABEL_AS + LabelId.CODE_REVIEW))
         .isTrue();
+    assertThat(
+            Permission.canBeOnAllProjects(
+                "refs/heads/*", Permission.REMOVE_LABEL + LabelId.CODE_REVIEW))
+        .isTrue();
   }
 
   @Test
@@ -126,6 +156,8 @@
         .isEqualTo(LabelId.CODE_REVIEW);
     assertThat(Permission.create(Permission.LABEL_AS + LabelId.CODE_REVIEW).getLabel())
         .isEqualTo(LabelId.CODE_REVIEW);
+    assertThat(Permission.create(Permission.REMOVE_LABEL + LabelId.CODE_REVIEW).getLabel())
+        .isEqualTo(LabelId.CODE_REVIEW);
     assertThat(Permission.create(LabelId.CODE_REVIEW).getLabel()).isNull();
     assertThat(Permission.create(Permission.ABANDON).getLabel()).isNull();
   }
diff --git a/javatests/com/google/gerrit/extensions/common/ChangeInfoDifferTest.java b/javatests/com/google/gerrit/extensions/common/ChangeInfoDifferTest.java
index 7ed236a..f45d33b 100644
--- a/javatests/com/google/gerrit/extensions/common/ChangeInfoDifferTest.java
+++ b/javatests/com/google/gerrit/extensions/common/ChangeInfoDifferTest.java
@@ -48,6 +48,7 @@
     assertThat(diff.added().messages).isNull();
     assertThat(diff.added().reviewers).isNull();
     assertThat(diff.added().hashtags).isNull();
+    assertThat(diff.added().removableLabels).isNull();
     assertThat(diff.removed()._number).isNull();
     assertThat(diff.removed().branch).isNull();
     assertThat(diff.removed().project).isNull();
@@ -56,6 +57,7 @@
     assertThat(diff.removed().messages).isNull();
     assertThat(diff.removed().reviewers).isNull();
     assertThat(diff.removed().hashtags).isNull();
+    assertThat(diff.removed().removableLabels).isNull();
   }
 
   @Test
@@ -315,6 +317,295 @@
   }
 
   @Test
+  public void getDiff_removableLabelsEmpty_returnsNullRemovableLabels() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    oldChangeInfo.removableLabels = ImmutableMap.of();
+    newChangeInfo.removableLabels = ImmutableMap.of();
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels).isNull();
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsNullAndEmpty_returnsEmptyRemovableLabels() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    newChangeInfo.removableLabels = ImmutableMap.of();
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels).isEmpty();
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsEmptyAndNull_returnsEmptyRemovableLabels() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    oldChangeInfo.removableLabels = ImmutableMap.of();
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels).isNull();
+    assertThat(diff.removed().removableLabels).isEmpty();
+  }
+
+  @Test
+  public void getDiff_removableLabelsLabelAdded() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "Cow";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "Pig";
+    AccountInfo acc3 = new AccountInfo();
+    acc3.name = "Cat";
+    AccountInfo acc4 = new AccountInfo();
+    acc4.name = "Dog";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)),
+            "Verified",
+            ImmutableMap.of("-1", ImmutableList.of(acc4)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Verified", ImmutableMap.of("-1", ImmutableList.of(acc4))));
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsLabelRemoved() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "Cow";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "Pig";
+    AccountInfo acc3 = new AccountInfo();
+    acc3.name = "Cat";
+    AccountInfo acc4 = new AccountInfo();
+    acc4.name = "Dog";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)),
+            "Verified",
+            ImmutableMap.of("-1", ImmutableList.of(acc4)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels).isNull();
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Verified", ImmutableMap.of("-1", ImmutableList.of(acc4))));
+  }
+
+  @Test
+  public void getDiff_removableLabelsVoteAdded() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+    AccountInfo acc3 = new AccountInfo();
+    acc3.name = "acc3";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("-1", ImmutableList.of(acc2, acc3))));
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsVoteRemoved() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+    AccountInfo acc3 = new AccountInfo();
+    acc3.name = "acc3";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of(
+            "Code-Review",
+            ImmutableMap.of("+1", ImmutableList.of(acc1), "-1", ImmutableList.of(acc2, acc3)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels).isNull();
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("-1", ImmutableList.of(acc2, acc3))));
+  }
+
+  @Test
+  public void getDiff_removableLabelsAccountAdded() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1, acc2)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc2))));
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsAccountRemoved() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1, acc2)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc2))));
+    assertThat(diff.removed().removableLabels).isNull();
+  }
+
+  @Test
+  public void getDiff_removableLabelsAccountChanged() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc2)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc2))));
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1))));
+  }
+
+  @Test
+  public void getDiff_removableLabelsScoreChanged() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("-1", ImmutableList.of(acc1)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("-1", ImmutableList.of(acc1))));
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1))));
+  }
+
+  @Test
+  public void getDiff_removableLabelsLabelChanged() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Verified", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Verified", ImmutableMap.of("+1", ImmutableList.of(acc1))));
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1))));
+  }
+
+  @Test
+  public void getDiff_removableLabelsLabelScoreAndAccountChanged() {
+    ChangeInfo oldChangeInfo = new ChangeInfo();
+    ChangeInfo newChangeInfo = new ChangeInfo();
+    AccountInfo acc1 = new AccountInfo();
+    acc1.name = "acc1";
+    AccountInfo acc2 = new AccountInfo();
+    acc2.name = "acc2";
+
+    oldChangeInfo.removableLabels =
+        ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1)));
+    newChangeInfo.removableLabels =
+        ImmutableMap.of("Verified", ImmutableMap.of("-1", ImmutableList.of(acc2)));
+
+    ChangeInfoDifference diff = ChangeInfoDiffer.getDifference(oldChangeInfo, newChangeInfo);
+
+    assertThat(diff.added().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Verified", ImmutableMap.of("-1", ImmutableList.of(acc2))));
+    assertThat(diff.removed().removableLabels)
+        .containsExactlyEntriesIn(
+            ImmutableMap.of("Code-Review", ImmutableMap.of("+1", ImmutableList.of(acc1))));
+  }
+
+  @Test
   public void getDiff_assertCanConstructAllChangeInfoReferences() throws Exception {
     buildObjectWithFullFields(ChangeInfo.class);
   }