path: root/jimfs/src/main/java/com/google/common/jimfs/GlobToRegex.java

/*
 * Copyright 2013 Google Inc.
 *
 * 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.common.jimfs;

import static com.google.common.base.Preconditions.checkNotNull;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.regex.PatternSyntaxException;

/**
 * Translates globs to regex patterns.
 *
 * @author Colin Decker
 */
final class GlobToRegex {

  /**
   * Converts the given glob to a regular expression pattern. The given separators determine what
   * characters the resulting expression breaks on for glob expressions such as * which should not
   * cross directory boundaries.
   *
   * <p>Basic conversions (assuming / as only separator):
   *
   * <pre>{@code
   * ?        = [^/]
   * *        = [^/]*
   * **       = .*
   * [a-z]    = [[^/]&&[a-z]]
   * [!a-z]   = [[^/]&&[^a-z]]
   * {a,b,c}  = (a|b|c)
   * }</pre>
   */
  public static String toRegex(String glob, String separators) {
    return new GlobToRegex(glob, separators).convert();
  }

  private static final InternalCharMatcher REGEX_RESERVED =
      InternalCharMatcher.anyOf("^$.?+*\\[]{}()");

  private final String glob;
  private final String separators;
  private final InternalCharMatcher separatorMatcher;

  private final StringBuilder builder = new StringBuilder();
  private final Deque<State> states = new ArrayDeque<>();
  private int index;

  private GlobToRegex(String glob, String separators) {
    this.glob = checkNotNull(glob);
    this.separators = separators;
    this.separatorMatcher = InternalCharMatcher.anyOf(separators);
  }

  /**
   * Converts the glob to a regex one character at a time. A state stack (states) is maintained,
   * with the state at the top of the stack being the current state at any given time. The current
   * state is always used to process the next character. When a state processes a character, it may
   * pop the current state or push a new state as the current state. The resulting regex is written
   * to {@code builder}.
   */
  private String convert() {
    pushState(NORMAL);
    for (index = 0; index < glob.length(); index++) {
      currentState().process(this, glob.charAt(index));
    }
    currentState().finish(this);
    return builder.toString();
  }

  /** Enters the given state. The current state becomes the previous state. */
  private void pushState(State state) {
    states.push(state);
  }

  /** Returns to the previous state. */
  private void popState() {
    states.pop();
  }

  /** Returns the current state. */
  private State currentState() {
    return states.peek();
  }

  /** Throws a {@link PatternSyntaxException}. */
  private PatternSyntaxException syntaxError(String desc) {
    throw new PatternSyntaxException(desc, glob, index);
  }

  /** Appends the given character as-is to the regex. */
  private void appendExact(char c) {
    builder.append(c);
  }

  /** Appends the regex form of the given normal character or separator from the glob. */
  private void append(char c) {
    if (separatorMatcher.matches(c)) {
      appendSeparator();
    } else {
      appendNormal(c);
    }
  }

  /** Appends the regex form of the given normal character from the glob. */
  private void appendNormal(char c) {
    if (REGEX_RESERVED.matches(c)) {
      builder.append('\\');
    }
    builder.append(c);
  }

  /** Appends the regex form matching the separators for the path type. */
  private void appendSeparator() {
    if (separators.length() == 1) {
      appendNormal(separators.charAt(0));
    } else {
      builder.append('[');
      for (int i = 0; i < separators.length(); i++) {
        appendInBracket(separators.charAt(i));
      }
      builder.append("]");
    }
  }

  /** Appends the regex form that matches anything except the separators for the path type. */
  private void appendNonSeparator() {
    builder.append("[^");
    for (int i = 0; i < separators.length(); i++) {
      appendInBracket(separators.charAt(i));
    }
    builder.append(']');
  }

  /** Appends the regex form of the glob ? character. */
  private void appendQuestionMark() {
    appendNonSeparator();
  }

  /** Appends the regex form of the glob * character. */
  private void appendStar() {
    appendNonSeparator();
    builder.append('*');
  }

  /** Appends the regex form of the glob ** pattern. */
  private void appendStarStar() {
    builder.append(".*");
  }

  /** Appends the regex form of the start of a glob [] section. */
  private void appendBracketStart() {
    builder.append('[');
    appendNonSeparator();
    builder.append("&&[");
  }

  /** Appends the regex form of the end of a glob [] section. */
  private void appendBracketEnd() {
    builder.append("]]");
  }

  /** Appends the regex form of the given character within a glob [] section. */
  private void appendInBracket(char c) {
    // escape \ in regex character class
    if (c == '\\') {
      builder.append('\\');
    }

    builder.append(c);
  }

  /** Appends the regex form of the start of a glob {} section. */
  private void appendCurlyBraceStart() {
    builder.append('(');
  }

  /** Appends the regex form of the separator (,) within a glob {} section. */
  private void appendSubpatternSeparator() {
    builder.append('|');
  }

  /** Appends the regex form of the end of a glob {} section. */
  private void appendCurlyBraceEnd() {
    builder.append(')');
  }

  /** Converter state. */
  private abstract static class State {
    /**
     * Process the next character with the current state, transitioning the converter to a new state
     * if necessary.
     */
    abstract void process(GlobToRegex converter, char c);

    /** Called after all characters have been read. */
    void finish(GlobToRegex converter) {}
  }

  /** Normal state. */
  private static final State NORMAL =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          switch (c) {
            case '?':
              converter.appendQuestionMark();
              return;
            case '[':
              converter.appendBracketStart();
              converter.pushState(BRACKET_FIRST_CHAR);
              return;
            case '{':
              converter.appendCurlyBraceStart();
              converter.pushState(CURLY_BRACE);
              return;
            case '*':
              converter.pushState(STAR);
              return;
            case '\\':
              converter.pushState(ESCAPE);
              return;
            default:
              converter.append(c);
          }
        }

        @Override
        public String toString() {
          return "NORMAL";
        }
      };

  /** State following the reading of a single \. */
  private static final State ESCAPE =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          converter.append(c);
          converter.popState();
        }

        @Override
        void finish(GlobToRegex converter) {
          throw converter.syntaxError("Hanging escape (\\) at end of pattern");
        }

        @Override
        public String toString() {
          return "ESCAPE";
        }
      };

  /** State following the reading of a single *. */
  private static final State STAR =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          if (c == '*') {
            converter.appendStarStar();
            converter.popState();
          } else {
            converter.appendStar();
            converter.popState();
            converter.currentState().process(converter, c);
          }
        }

        @Override
        void finish(GlobToRegex converter) {
          converter.appendStar();
        }

        @Override
        public String toString() {
          return "STAR";
        }
      };

  /** State immediately following the reading of a [. */
  private static final State BRACKET_FIRST_CHAR =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          if (c == ']') {
            // A glob like "[]]" or "[]q]" is apparently fine in Unix (when used with ls for
            // example) but doesn't work for the default java.nio.file implementations. In the cases
            // of "[]]" it produces:
            // java.util.regex.PatternSyntaxException: Unclosed character class near index 13
            // ^[[^/]&&[]]\]$
            //              ^
            // The error here is slightly different, but trying to make this work would require some
            // kind of lookahead and break the simplicity of char-by-char conversion here. Also, if
            // someone wants to include a ']' inside a character class, they should escape it.
            throw converter.syntaxError("Empty []");
          }
          if (c == '!') {
            converter.appendExact('^');
          } else if (c == '-') {
            converter.appendExact(c);
          } else {
            converter.appendInBracket(c);
          }
          converter.popState();
          converter.pushState(BRACKET);
        }

        @Override
        void finish(GlobToRegex converter) {
          throw converter.syntaxError("Unclosed [");
        }

        @Override
        public String toString() {
          return "BRACKET_FIRST_CHAR";
        }
      };

  /** State inside [brackets], but not at the first character inside the brackets. */
  private static final State BRACKET =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          if (c == ']') {
            converter.appendBracketEnd();
            converter.popState();
          } else {
            converter.appendInBracket(c);
          }
        }

        @Override
        void finish(GlobToRegex converter) {
          throw converter.syntaxError("Unclosed [");
        }

        @Override
        public String toString() {
          return "BRACKET";
        }
      };

  /** State inside {curly braces}. */
  private static final State CURLY_BRACE =
      new State() {
        @Override
        void process(GlobToRegex converter, char c) {
          switch (c) {
            case '?':
              converter.appendQuestionMark();
              break;
            case '[':
              converter.appendBracketStart();
              converter.pushState(BRACKET_FIRST_CHAR);
              break;
            case '{':
              throw converter.syntaxError("{ not allowed in subpattern group");
            case '*':
              converter.pushState(STAR);
              break;
            case '\\':
              converter.pushState(ESCAPE);
              break;
            case '}':
              converter.appendCurlyBraceEnd();
              converter.popState();
              break;
            case ',':
              converter.appendSubpatternSeparator();
              break;
            default:
              converter.append(c);
          }
        }

        @Override
        void finish(GlobToRegex converter) {
          throw converter.syntaxError("Unclosed {");
        }

        @Override
        public String toString() {
          return "CURLY_BRACE";
        }
      };
}