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.util;
      16             : 
      17             : import com.google.gerrit.entities.AccessSection;
      18             : import com.google.gerrit.server.project.RefPattern;
      19             : import java.util.Comparator;
      20             : import org.apache.commons.text.similarity.LevenshteinDistance;
      21             : 
      22             : /**
      23             :  * Order the Ref Pattern by the most specific. This sort is done by:
      24             :  *
      25             :  * <ul>
      26             :  *   <li>1 - The minor value of Levenshtein string distance between the branch name and the regex
      27             :  *       string shortest example. A shorter distance is a more specific match.
      28             :  *   <li>2 - Finites first, infinities after.
      29             :  *   <li>3 - Number of transitions. More transitions is more specific.
      30             :  *   <li>4 - Length of the expression text.
      31             :  * </ul>
      32             :  *
      33             :  * Levenshtein distance is a measure of the similarity between two strings. The distance is the
      34             :  * number of deletions, insertions, or substitutions required to transform one string into another.
      35             :  *
      36             :  * <p>For example, if given refs/heads/m* and refs/heads/*, the distances are 5 and 6. It means that
      37             :  * refs/heads/m* is more specific because it's closer to refs/heads/master than refs/heads/*.
      38             :  *
      39             :  * <p>Another example could be refs/heads/* and refs/heads/[a-zA-Z]*, the distances are both 6. Both
      40             :  * are infinite, but refs/heads/[a-zA-Z]* has more transitions, which after all turns it more
      41             :  * specific.
      42             :  */
      43             : public final class MostSpecificComparator implements Comparator<AccessSection> {
      44             :   private final String refName;
      45             : 
      46         145 :   public MostSpecificComparator(String refName) {
      47         145 :     this.refName = refName;
      48         145 :   }
      49             : 
      50             :   @Override
      51             :   public int compare(AccessSection a, AccessSection b) {
      52         145 :     return compare(a.getName(), b.getName());
      53             :   }
      54             : 
      55             :   public int compare(String pattern1, String pattern2) {
      56         145 :     int cmp = distance(pattern1) - distance(pattern2);
      57         145 :     if (cmp == 0) {
      58          75 :       boolean p1_finite = finite(pattern1);
      59          75 :       boolean p2_finite = finite(pattern2);
      60             : 
      61          75 :       if (p1_finite && !p2_finite) {
      62           1 :         cmp = -1;
      63          75 :       } else if (!p1_finite && p2_finite) {
      64           0 :         cmp = 1;
      65             :       } else /* if (f1 == f2) */ {
      66          75 :         cmp = 0;
      67             :       }
      68             :     }
      69         145 :     if (cmp == 0) {
      70          75 :       cmp = transitions(pattern2) - transitions(pattern1);
      71             :     }
      72         145 :     if (cmp == 0) {
      73          75 :       cmp = pattern2.length() - pattern1.length();
      74             :     }
      75         145 :     return cmp;
      76             :   }
      77             : 
      78             :   private int distance(String pattern) {
      79             :     String example;
      80         145 :     if (RefPattern.isRE(pattern)) {
      81           1 :       example = RefPattern.shortestExample(pattern);
      82             : 
      83         145 :     } else if (pattern.endsWith("/*")) {
      84         145 :       example = pattern;
      85             : 
      86         140 :     } else if (pattern.equals(refName)) {
      87         140 :       return 0;
      88             : 
      89             :     } else {
      90          20 :       return Math.max(pattern.length(), refName.length());
      91             :     }
      92         145 :     return LevenshteinDistance.getDefaultInstance().apply(example, refName);
      93             :   }
      94             : 
      95             :   private boolean finite(String pattern) {
      96          75 :     if (RefPattern.isRE(pattern)) {
      97           1 :       return RefPattern.toRegExp(pattern).toAutomaton().isFinite();
      98             : 
      99          75 :     } else if (pattern.endsWith("/*")) {
     100          74 :       return false;
     101             : 
     102             :     } else {
     103          13 :       return true;
     104             :     }
     105             :   }
     106             : 
     107             :   private int transitions(String pattern) {
     108          75 :     if (RefPattern.isRE(pattern)) {
     109           1 :       return RefPattern.toRegExp(pattern).toAutomaton().getNumberOfTransitions();
     110             : 
     111          75 :     } else if (pattern.endsWith("/*")) {
     112          74 :       return pattern.length();
     113             : 
     114             :     } else {
     115          13 :       return pattern.length();
     116             :     }
     117             :   }
     118             : }