| // Copyright (C) 2011 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.git; |
| |
| package com.google.gerrit.server.project; |
| |
| import static com.google.gerrit.server.project.RefControl.isRE; |
| import static com.google.gerrit.server.project.RefControl.shortestExample; |
| import static com.google.gerrit.server.project.RefControl.toRegExp; |
| |
| import com.google.gerrit.common.data.AccessSection; |
| import com.google.gerrit.server.cache.Cache; |
| import com.google.gerrit.server.cache.CacheModule; |
| import com.google.inject.Inject; |
| import com.google.inject.Module; |
| import com.google.inject.Singleton; |
| import com.google.inject.TypeLiteral; |
| import com.google.inject.name.Named; |
| |
| import org.apache.commons.lang.StringUtils; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.IdentityHashMap; |
| import java.util.List; |
| |
| /** Caches the order AccessSections should be sorted for evaluation. */ |
| @Singleton |
| public class SectionSortCache { |
| private static final Logger log = |
| LoggerFactory.getLogger(SectionSortCache.class); |
| |
| private static final String CACHE_NAME = "permission_sort"; |
| |
| public static Module module() { |
| return new CacheModule() { |
| @Override |
| protected void configure() { |
| final TypeLiteral<Cache<EntryKey, EntryVal>> type = |
| new TypeLiteral<Cache<EntryKey, EntryVal>>() {}; |
| core(type, CACHE_NAME); |
| bind(SectionSortCache.class); |
| } |
| }; |
| } |
| |
| private final Cache<EntryKey, EntryVal> cache; |
| |
| @Inject |
| SectionSortCache(@Named(CACHE_NAME) Cache<EntryKey, EntryVal> cache) { |
| this.cache = cache; |
| } |
| |
| void sort(String ref, List<AccessSection> sections) { |
| final int cnt = sections.size(); |
| if (cnt <= 1) { |
| return; |
| } |
| |
| EntryKey key = new EntryKey(ref, sections); |
| EntryVal val = cache.get(key); |
| if (val != null) { |
| int[] srcIdx = val.order; |
| if (srcIdx != null) { |
| AccessSection[] srcList = copy(sections); |
| for (int i = 0; i < cnt; i++) { |
| sections.set(i, srcList[srcIdx[i]]); |
| } |
| } else { |
| // Identity transform. No sorting is required. |
| } |
| |
| } else { |
| boolean poison = false; |
| IdentityHashMap<AccessSection, Integer> srcMap = |
| new IdentityHashMap<AccessSection, Integer>(); |
| for (int i = 0; i < cnt; i++) { |
| poison |= srcMap.put(sections.get(i), i) != null; |
| } |
| |
| Collections.sort(sections, new MostSpecificComparator(ref)); |
| |
| int srcIdx[]; |
| if (isIdentityTransform(sections, srcMap)) { |
| srcIdx = null; |
| } else { |
| srcIdx = new int[cnt]; |
| for (int i = 0; i < cnt; i++) { |
| srcIdx[i] = srcMap.get(sections.get(i)); |
| } |
| } |
| |
| if (poison) { |
| log.error("Received duplicate AccessSection instances, not caching sort"); |
| } else { |
| cache.put(key, new EntryVal(srcIdx)); |
| } |
| } |
| } |
| |
| private static AccessSection[] copy(List<AccessSection> sections) { |
| return sections.toArray(new AccessSection[sections.size()]); |
| } |
| |
| private static boolean isIdentityTransform(List<AccessSection> sections, |
| IdentityHashMap<AccessSection, Integer> srcMap) { |
| for (int i = 0; i < sections.size(); i++) { |
| if (i != srcMap.get(sections.get(i))) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| static final class EntryKey { |
| private final String ref; |
| private final String[] patterns; |
| private final int hashCode; |
| |
| EntryKey(String refName, List<AccessSection> sections) { |
| int hc = refName.hashCode(); |
| ref = refName; |
| patterns = new String[sections.size()]; |
| for (int i = 0; i < patterns.length; i++) { |
| String n = sections.get(i).getName(); |
| patterns[i] = n; |
| hc = hc * 31 + n.hashCode(); |
| } |
| hashCode = hc; |
| } |
| |
| @Override |
| public int hashCode() { |
| return hashCode; |
| } |
| |
| @Override |
| public boolean equals(Object other) { |
| if (other instanceof EntryKey) { |
| EntryKey b = (EntryKey) other; |
| return ref.equals(b.ref) && Arrays.equals(patterns, b.patterns); |
| } |
| return false; |
| } |
| } |
| |
| static final class EntryVal { |
| /** |
| * Maps the input index to the output index. |
| * <p> |
| * For {@code x == order[y]} the expression means move the item at |
| * source position {@code x} to the output position {@code y}. |
| */ |
| final int[] order; |
| |
| EntryVal(int[] order) { |
| this.order = order; |
| } |
| } |
| |
| /** |
| * Order the Ref Pattern by the most specific. This sort is done by: |
| * <ul> |
| * <li>1 - The minor value of Levenshtein string distance between the branch |
| * name and the regex string shortest example. A shorter distance is a more |
| * specific match. |
| * <li>2 - Finites first, infinities after. |
| * <li>3 - Number of transitions. |
| * <li>4 - Length of the expression text. |
| * </ul> |
| * |
| * Levenshtein distance is a measure of the similarity between two strings. |
| * The distance is the number of deletions, insertions, or substitutions |
| * required to transform one string into another. |
| * |
| * For example, if given refs/heads/m* and refs/heads/*, the distances are 5 |
| * and 6. It means that refs/heads/m* is more specific because it's closer to |
| * refs/heads/master than refs/heads/*. |
| * |
| * Another example could be refs/heads/* and refs/heads/[a-zA-Z]*, the |
| * distances are both 6. Both are infinite, but refs/heads/[a-zA-Z]* has more |
| * transitions, which after all turns it more specific. |
| */ |
| private static final class MostSpecificComparator implements |
| Comparator<AccessSection> { |
| private final String refName; |
| |
| MostSpecificComparator(String refName) { |
| this.refName = refName; |
| } |
| |
| public int compare(AccessSection a, AccessSection b) { |
| return compare(a.getName(), b.getName()); |
| } |
| |
| private int compare(final String pattern1, final String pattern2) { |
| int cmp = distance(pattern1) - distance(pattern2); |
| if (cmp == 0) { |
| boolean p1_finite = finite(pattern1); |
| boolean p2_finite = finite(pattern2); |
| |
| if (p1_finite && !p2_finite) { |
| cmp = -1; |
| } else if (!p1_finite && p2_finite) { |
| cmp = 1; |
| } else /* if (f1 == f2) */{ |
| cmp = 0; |
| } |
| } |
| if (cmp == 0) { |
| cmp = transitions(pattern1) - transitions(pattern2); |
| } |
| if (cmp == 0) { |
| cmp = pattern2.length() - pattern1.length(); |
| } |
| return cmp; |
| } |
| |
| private int distance(String pattern) { |
| String example; |
| if (isRE(pattern)) { |
| example = shortestExample(pattern); |
| |
| } else if (pattern.endsWith("/*")) { |
| example = pattern.substring(0, pattern.length() - 1) + '1'; |
| |
| } else if (pattern.equals(refName)) { |
| return 0; |
| |
| } else { |
| return Math.max(pattern.length(), refName.length()); |
| } |
| return StringUtils.getLevenshteinDistance(example, refName); |
| } |
| |
| private boolean finite(String pattern) { |
| if (isRE(pattern)) { |
| return toRegExp(pattern).toAutomaton().isFinite(); |
| |
| } else if (pattern.endsWith("/*")) { |
| return false; |
| |
| } else { |
| return true; |
| } |
| } |
| |
| private int transitions(String pattern) { |
| if (isRE(pattern)) { |
| return toRegExp(pattern).toAutomaton().getNumberOfTransitions(); |
| |
| } else if (pattern.endsWith("/*")) { |
| return pattern.length(); |
| |
| } else { |
| return pattern.length(); |
| } |
| } |
| } |
| } |