Line data    Source code

       1             : // Copyright (C) 2011 The Android Open Source Project
       2             : //
       3             : // Licensed under the Apache License, Version 2.0 (the "License");
       4             : // you may not use this file except in compliance with the License.
       5             : // You may obtain a copy of the License at
       6             : //
       7             : // http://www.apache.org/licenses/LICENSE-2.0
       8             : //
       9             : // Unless required by applicable law or agreed to in writing, software
      10             : // distributed under the License is distributed on an "AS IS" BASIS,
      11             : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12             : // See the License for the specific language governing permissions and
      13             : // limitations under the License.
      14             : 
      15             : package com.google.gerrit.server.permissions;
      16             : 
      17             : import static com.google.common.collect.ImmutableList.toImmutableList;
      18             : 
      19             : import com.google.auto.value.AutoValue;
      20             : import com.google.auto.value.extension.memoized.Memoized;
      21             : import com.google.common.cache.Cache;
      22             : import com.google.common.collect.ImmutableList;
      23             : import com.google.common.flogger.FluentLogger;
      24             : import com.google.gerrit.entities.AccessSection;
      25             : import com.google.gerrit.server.cache.CacheModule;
      26             : import com.google.gerrit.server.util.MostSpecificComparator;
      27             : import com.google.inject.Inject;
      28             : import com.google.inject.Module;
      29             : import com.google.inject.Singleton;
      30             : import com.google.inject.name.Named;
      31             : import java.util.ArrayList;
      32             : import java.util.IdentityHashMap;
      33             : import java.util.List;
      34             : import java.util.concurrent.Callable;
      35             : import java.util.concurrent.ExecutionException;
      36             : 
      37             : /**
      38             :  * Caches the order AccessSections should be sorted for evaluation.
      39             :  *
      40             :  * <p>Access specifications for a more specific ref (eg. refs/heads/master rather than refs/heads/*)
      41             :  * take precedence in ACL evaluations. So for each combination of (ref, list of access specs) we
      42             :  * have to order the access specs by their distance from the ref to be matched. This is expensive,
      43             :  * so cache the sorted ordering.
      44             :  */
      45             : @Singleton
      46             : public class SectionSortCache {
      47         152 :   private static final FluentLogger logger = FluentLogger.forEnclosingClass();
      48             : 
      49             :   private static final String CACHE_NAME = "permission_sort";
      50             : 
      51             :   public static Module module() {
      52         152 :     return new CacheModule() {
      53             :       @Override
      54             :       protected void configure() {
      55         152 :         cache(CACHE_NAME, EntryKey.class, EntryVal.class);
      56         152 :         bind(SectionSortCache.class);
      57         152 :       }
      58             :     };
      59             :   }
      60             : 
      61             :   private final Cache<EntryKey, EntryVal> cache;
      62             : 
      63             :   @Inject
      64         148 :   SectionSortCache(@Named(CACHE_NAME) Cache<EntryKey, EntryVal> cache) {
      65         148 :     this.cache = cache;
      66         148 :   }
      67             : 
      68             :   /**
      69             :    * Sorts the given sections in-place, but does not disturb ordering between equally exact
      70             :    * sections.
      71             :    */
      72             :   void sort(String ref, List<AccessSection> sections) {
      73         145 :     final int cnt = sections.size();
      74         145 :     if (cnt <= 1) {
      75         144 :       return;
      76             :     }
      77         145 :     EntryKey key = EntryKey.create(ref, sections);
      78             :     EntryVal val;
      79             :     try {
      80         145 :       val = cache.get(key, new Loader(key, sections));
      81           0 :     } catch (ExecutionException e) {
      82           0 :       logger.atWarning().withCause(e).log("Error happened while sorting access sections.");
      83           0 :       return;
      84         145 :     }
      85         145 :     ImmutableList<Integer> order = val.order();
      86         145 :     List<AccessSection> sorted = new ArrayList<>();
      87         145 :     for (int i = 0; i < cnt; i++) {
      88         145 :       sorted.add(sections.get(order.get(i)));
      89             :     }
      90         145 :     for (int i = 0; i < cnt; i++) {
      91         145 :       sections.set(i, sorted.get(i));
      92             :     }
      93         145 :   }
      94             : 
      95             :   private static class Loader implements Callable<EntryVal> {
      96             :     private final List<AccessSection> sections;
      97             :     EntryKey key;
      98             : 
      99         145 :     Loader(EntryKey key, List<AccessSection> sections) {
     100         145 :       this.key = key;
     101         145 :       this.sections = sections;
     102         145 :     }
     103             : 
     104             :     @Override
     105             :     public EntryVal call() throws Exception {
     106             :       // We use IdentityHashMap (which uses reference equality for keys/values) to preserve distinct
     107             :       // entries in the map for identical AccessSection keys
     108         145 :       IdentityHashMap<AccessSection, Integer> srcMap = new IdentityHashMap<>();
     109         145 :       for (int i = 0; i < sections.size(); i++) {
     110         145 :         srcMap.put(sections.get(i), i);
     111             :       }
     112         145 :       ImmutableList<AccessSection> sorted =
     113         145 :           sections.stream()
     114         145 :               .sorted(new MostSpecificComparator(key.ref()))
     115         145 :               .collect(toImmutableList());
     116         145 :       ImmutableList.Builder<Integer> order = ImmutableList.builderWithExpectedSize(sections.size());
     117         145 :       for (int i = 0; i < sorted.size(); i++) {
     118         145 :         order.add(srcMap.get(sorted.get(i)));
     119             :       }
     120         145 :       return EntryVal.create(order.build());
     121             :     }
     122             :   }
     123             : 
     124             :   @AutoValue
     125         145 :   abstract static class EntryKey {
     126             :     public abstract String ref();
     127             : 
     128             :     public abstract ImmutableList<String> patterns();
     129             : 
     130             :     static EntryKey create(String refName, List<AccessSection> sections) {
     131         145 :       ImmutableList.Builder<String> patterns =
     132         145 :           ImmutableList.builderWithExpectedSize(sections.size());
     133         145 :       for (AccessSection s : sections) {
     134         145 :         patterns.add(s.getName());
     135         145 :       }
     136         145 :       return new AutoValue_SectionSortCache_EntryKey(refName, patterns.build());
     137             :     }
     138             : 
     139             :     @Memoized
     140             :     @Override
     141             :     public int hashCode() {
     142         145 :       int hc = ref().hashCode();
     143         145 :       for (String n : patterns()) {
     144         145 :         hc = hc * 31 + n.hashCode();
     145         145 :       }
     146         145 :       return hc;
     147             :     }
     148             :   }
     149             : 
     150             :   @AutoValue
     151         145 :   abstract static class EntryVal {
     152             :     /**
     153             :      * Maps the input index to the output index.
     154             :      *
     155             :      * <p>For {@code x == order[y]} the expression means move the item at source position {@code x}
     156             :      * to the output position {@code y}.
     157             :      */
     158             :     abstract ImmutableList<Integer> order();
     159             : 
     160             :     static EntryVal create(ImmutableList<Integer> order) {
     161         145 :       return new AutoValue_SectionSortCache_EntryVal(order);
     162             :     }
     163             :   }
     164             : }