FileNameMatcher.java

  1. /*
  2.  * Copyright (C) 2008, Florian Köberle <florianskarten@web.de> and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.fnmatch;

  13. import java.util.ArrayList;
  14. import java.util.Collections;
  15. import java.util.List;
  16. import java.util.ListIterator;
  17. import java.util.regex.Matcher;
  18. import java.util.regex.Pattern;

  20. import org.eclipse.jgit.errors.InvalidPatternException;
  21. import org.eclipse.jgit.errors.NoClosingBracketException;

  23. /**
  24.  * This class can be used to match filenames against fnmatch like patterns. It
  25.  * is not thread save.
  26.  * <p>
  27.  * Supported are the wildcard characters * and ? and groups with:
  28.  * <ul>
  29.  * <li>characters e.g. [abc]</li>
  30.  * <li>ranges e.g. [a-z]</li>
  31.  * <li>the following character classes
  32.  * <ul>
  33.  * <li>[:alnum:]</li>
  34.  * <li>[:alpha:]</li>
  35.  * <li>[:blank:]</li>
  36.  * <li>[:cntrl:]</li>
  37.  * <li>[:digit:]</li>
  38.  * <li>[:graph:]</li>
  39.  * <li>[:lower:]</li>
  40.  * <li>[:print:]</li>
  41.  * <li>[:punct:]</li>
  42.  * <li>[:space:]</li>
  43.  * <li>[:upper:]</li>
  44.  * <li>[:word:]</li>
  45.  * <li>[:xdigit:]</li>
  46.  * </ul>
  47.  * e. g. [[:xdigit:]]</li>
  48.  * </ul>
  49.  * Any character can be escaped by prepending it with a \
  50.  */
  51. public class FileNameMatcher {
  52.     static final List<Head> EMPTY_HEAD_LIST = Collections.emptyList();

  54.     private static final Pattern characterClassStartPattern = Pattern
  55.             .compile("\\[[.:=]"); //$NON-NLS-1$

  57.     private List<Head> headsStartValue;

  59.     private List<Head> heads;

  61.     /**
  62.      * {{@link #extendStringToMatchByOneCharacter(char)} needs a list for the
  63.      * new heads, allocating a new array would be bad for the performance, as
  64.      * the method gets called very often.
  65.      *
  66.      */
  67.     private List<Head> listForLocalUseage;

  69.     /**
  70.      *
  71.      * @param headsStartValue
  72.      *            must be a list which will never be modified.
  73.      */
  74.     private FileNameMatcher(List<Head> headsStartValue) {
  75.         this(headsStartValue, headsStartValue);
  76.     }

  78.     /**
  79.      *
  80.      * @param headsStartValue
  81.      *            must be a list which will never be modified.
  82.      * @param heads
  83.      *            a list which will be cloned and then used as current head
  84.      *            list.
  85.      */
  86.     private FileNameMatcher(final List<Head> headsStartValue,
  87.             final List<Head> heads) {
  88.         this.headsStartValue = headsStartValue;
  89.         this.heads = new ArrayList<>(heads.size());
  90.         this.heads.addAll(heads);
  91.         this.listForLocalUseage = new ArrayList<>(heads.size());
  92.     }

  94.     /**
  95.      * Constructor for FileNameMatcher
  96.      *
  97.      * @param patternString
  98.      *            must contain a pattern which fnmatch would accept.
  99.      * @param invalidWildgetCharacter
  100.      *            if this parameter isn't null then this character will not
  101.      *            match at wildcards(* and ? are wildcards).
  102.      * @throws org.eclipse.jgit.errors.InvalidPatternException
  103.      *             if the patternString contains a invalid fnmatch pattern.
  104.      */
  105.     public FileNameMatcher(final String patternString,
  106.             final Character invalidWildgetCharacter)
  107.             throws InvalidPatternException {
  108.         this(createHeadsStartValues(patternString, invalidWildgetCharacter));
  109.     }

  111.     /**
  112.      * A Copy Constructor which creates a new
  113.      * {@link org.eclipse.jgit.fnmatch.FileNameMatcher} with the same state and
  114.      * reset point like <code>other</code>.
  115.      *
  116.      * @param other
  117.      *            another {@link org.eclipse.jgit.fnmatch.FileNameMatcher}
  118.      *            instance.
  119.      */
  120.     public FileNameMatcher(FileNameMatcher other) {
  121.         this(other.headsStartValue, other.heads);
  122.     }

  124.     private static List<Head> createHeadsStartValues(
  125.             final String patternString, final Character invalidWildgetCharacter)
  126.             throws InvalidPatternException {

  128.         final List<AbstractHead> allHeads = parseHeads(patternString,
  129.                 invalidWildgetCharacter);

  131.         List<Head> nextHeadsSuggestion = new ArrayList<>(2);
  132.         nextHeadsSuggestion.add(LastHead.INSTANCE);
  133.         for (int i = allHeads.size() - 1; i >= 0; i--) {
  134.             final AbstractHead head = allHeads.get(i);

  136.             // explanation:
  137.             // a and * of the pattern "a*b"
  138.             // need *b as newHeads
  139.             // that's why * extends the list for it self and it's left neighbor.
  140.             if (head.isStar()) {
  141.                 nextHeadsSuggestion.add(head);
  142.                 head.setNewHeads(nextHeadsSuggestion);
  143.             } else {
  144.                 head.setNewHeads(nextHeadsSuggestion);
  145.                 nextHeadsSuggestion = new ArrayList<>(2);
  146.                 nextHeadsSuggestion.add(head);
  147.             }
  148.         }
  149.         return nextHeadsSuggestion;
  150.     }

  152.     private static int findGroupEnd(final int indexOfStartBracket,
  153.             final String pattern) throws InvalidPatternException {
  154.         int firstValidCharClassIndex = indexOfStartBracket + 1;
  155.         int firstValidEndBracketIndex = indexOfStartBracket + 2;

  157.         if (indexOfStartBracket + 1 >= pattern.length())
  158.             throw new NoClosingBracketException(indexOfStartBracket, "[", "]", //$NON-NLS-1$ //$NON-NLS-2$
  159.                     pattern);

  161.         if (pattern.charAt(firstValidCharClassIndex) == '!') {
  162.             firstValidCharClassIndex++;
  163.             firstValidEndBracketIndex++;
  164.         }

  166.         final Matcher charClassStartMatcher = characterClassStartPattern
  167.                 .matcher(pattern);

  169.         int groupEnd = -1;
  170.         while (groupEnd == -1) {

  172.             final int possibleGroupEnd = indexOfUnescaped(pattern, ']',
  173.                     firstValidEndBracketIndex);
  174.             if (possibleGroupEnd == -1)
  175.                 throw new NoClosingBracketException(indexOfStartBracket, "[", //$NON-NLS-1$
  176.                         "]", pattern); //$NON-NLS-1$

  178.             final boolean foundCharClass = charClassStartMatcher
  179.                     .find(firstValidCharClassIndex);

  181.             if (foundCharClass
  182.                     && charClassStartMatcher.start() < possibleGroupEnd) {

  184.                 final String classStart = charClassStartMatcher.group(0);
  185.                 final String classEnd = classStart.charAt(1) + "]"; //$NON-NLS-1$

  187.                 final int classStartIndex = charClassStartMatcher.start();
  188.                 final int classEndIndex = pattern.indexOf(classEnd,
  189.                         classStartIndex + 2);

  191.                 if (classEndIndex == -1)
  192.                     throw new NoClosingBracketException(classStartIndex,
  193.                             classStart, classEnd, pattern);

  195.                 firstValidCharClassIndex = classEndIndex + 2;
  196.                 firstValidEndBracketIndex = firstValidCharClassIndex;
  197.             } else {
  198.                 groupEnd = possibleGroupEnd;
  199.             }
  200.         }
  201.         return groupEnd;
  202.     }

  204.     private static List<AbstractHead> parseHeads(final String pattern,
  205.             final Character invalidWildgetCharacter)
  206.             throws InvalidPatternException {

  208.         int currentIndex = 0;
  209.         List<AbstractHead> heads = new ArrayList<>();
  210.         while (currentIndex < pattern.length()) {
  211.             final int groupStart = indexOfUnescaped(pattern, '[', currentIndex);
  212.             if (groupStart == -1) {
  213.                 final String patternPart = pattern.substring(currentIndex);
  214.                 heads.addAll(createSimpleHeads(patternPart,
  215.                         invalidWildgetCharacter));
  216.                 currentIndex = pattern.length();
  217.             } else {
  218.                 final String patternPart = pattern.substring(currentIndex,
  219.                         groupStart);
  220.                 heads.addAll(createSimpleHeads(patternPart,
  221.                         invalidWildgetCharacter));

  223.                 final int groupEnd = findGroupEnd(groupStart, pattern);
  224.                 final String groupPart = pattern.substring(groupStart + 1,
  225.                         groupEnd);
  226.                 heads.add(new GroupHead(groupPart, pattern));
  227.                 currentIndex = groupEnd + 1;
  228.             }
  229.         }
  230.         return heads;
  231.     }

  233.     private static List<AbstractHead> createSimpleHeads(
  234.             final String patternPart, final Character invalidWildgetCharacter) {
  235.         final List<AbstractHead> heads = new ArrayList<>(
  236.                 patternPart.length());

  238.         boolean escaped = false;
  239.         for (int i = 0; i < patternPart.length(); i++) {
  240.             final char c = patternPart.charAt(i);
  241.             if (escaped) {
  242.                 final CharacterHead head = new CharacterHead(c);
  243.                 heads.add(head);
  244.                 escaped = false;
  245.             } else {
  246.                 switch (c) {
  247.                 case '*': {
  248.                     final AbstractHead head = createWildCardHead(
  249.                             invalidWildgetCharacter, true);
  250.                     heads.add(head);
  251.                     break;
  252.                 }
  253.                 case '?': {
  254.                     final AbstractHead head = createWildCardHead(
  255.                             invalidWildgetCharacter, false);
  256.                     heads.add(head);
  257.                     break;
  258.                 }
  259.                 case '\\':
  260.                     escaped = true;
  261.                     break;
  262.                 default:
  263.                     final CharacterHead head = new CharacterHead(c);
  264.                     heads.add(head);
  265.                 }
  266.             }
  267.         }
  268.         return heads;
  269.     }

  271.     private static AbstractHead createWildCardHead(
  272.             final Character invalidWildgetCharacter, final boolean star) {
  273.         if (invalidWildgetCharacter != null) {
  274.             return new RestrictedWildCardHead(invalidWildgetCharacter
  275.                     .charValue(), star);
  276.         }
  277.         return new WildCardHead(star);
  278.     }

  280.     /**
  281.      * @param c new character to append
  282.      * @return true to continue, false if the matcher can stop appending
  283.      */
  284.     private boolean extendStringToMatchByOneCharacter(char c) {
  285.         final List<Head> newHeads = listForLocalUseage;
  286.         newHeads.clear();
  287.         List<Head> lastAddedHeads = null;
  288.         for (int i = 0; i < heads.size(); i++) {
  289.             final Head head = heads.get(i);
  290.             final List<Head> headsToAdd = head.getNextHeads(c);
  291.             // Why the next performance optimization isn't wrong:
  292.             // Some times two heads return the very same list.
  293.             // We save future effort if we don't add these heads again.
  294.             // This is the case with the heads "a" and "*" of "a*b" which
  295.             // both can return the list ["*","b"]
  296.             if (headsToAdd != lastAddedHeads) {
  297.                 if (!headsToAdd.isEmpty())
  298.                     newHeads.addAll(headsToAdd);
  299.                 lastAddedHeads = headsToAdd;
  300.             }
  301.         }
  302.         listForLocalUseage = heads;
  303.         heads = newHeads;
  304.         return !newHeads.isEmpty();
  305.     }

  307.     private static int indexOfUnescaped(final String searchString,
  308.             final char ch, final int fromIndex) {
  309.         for (int i = fromIndex; i < searchString.length(); i++) {
  310.             char current = searchString.charAt(i);
  311.             if (current == ch)
  312.                 return i;
  313.             if (current == '\\')
  314.                 i++; // Skip the next char as it is escaped }
  315.         }
  316.         return -1;
  317.     }

  319.     /**
  320.      * Append to the string which is matched against the patterns of this class
  321.      *
  322.      * @param stringToMatch
  323.      *            extends the string which is matched against the patterns of
  324.      *            this class.
  325.      */
  326.     public void append(String stringToMatch) {
  327.         for (int i = 0; i < stringToMatch.length(); i++) {
  328.             final char c = stringToMatch.charAt(i);
  329.             if (!extendStringToMatchByOneCharacter(c))
  330.                 break;
  331.         }
  332.     }

  334.     /**
  335.      * Resets this matcher to it's state right after construction.
  336.      */
  337.     public void reset() {
  338.         heads.clear();
  339.         heads.addAll(headsStartValue);
  340.     }

  342.     /**
  343.      * Create a {@link org.eclipse.jgit.fnmatch.FileNameMatcher} instance which
  344.      * uses the same pattern like this matcher, but has the current state of
  345.      * this matcher as reset and start point
  346.      *
  347.      * @return a {@link org.eclipse.jgit.fnmatch.FileNameMatcher} instance which
  348.      *         uses the same pattern like this matcher, but has the current
  349.      *         state of this matcher as reset and start point.
  350.      */
  351.     public FileNameMatcher createMatcherForSuffix() {
  352.         final List<Head> copyOfHeads = new ArrayList<>(heads.size());
  353.         copyOfHeads.addAll(heads);
  354.         return new FileNameMatcher(copyOfHeads);
  355.     }

  357.     /**
  358.      * Whether the matcher matches
  359.      *
  360.      * @return whether the matcher matches
  361.      */
  362.     public boolean isMatch() {
  363.         if (heads.isEmpty())
  364.             return false;

  366.         final ListIterator<Head> headIterator = heads
  367.                 .listIterator(heads.size());
  368.         while (headIterator.hasPrevious()) {
  369.             final Head head = headIterator.previous();
  370.             if (head == LastHead.INSTANCE) {
  371.                 return true;
  372.             }
  373.         }
  374.         return false;
  375.     }

  377.     /**
  378.      * Whether a match can be appended
  379.      *
  380.      * @return a boolean.
  381.      */
  382.     public boolean canAppendMatch() {
  383.         for (Head head : heads) {
  384.             if (head != LastHead.INSTANCE) {
  385.                 return true;
  386.             }
  387.         }
  388.         return false;
  389.     }
  390. }
Created with JaCoCo 0.8.7.202105040129