/* LanguageTool, a natural language style checker
 * Copyright (C) 2020 Peter Gromov
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
 * USA
 */
package org.languagetool.rules.patterns;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.Sets;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import org.languagetool.tools.InterruptibleCharSequence;

import java.util.*;
import java.util.function.Function;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * An object encapsulating a text pattern and the way it's matched (case-sensitivity / regular expression),
 * plus some optimizations over standard regular expression matching.
 * @since 5.3
 */
public abstract class StringMatcher {
  
  final String pattern;
  final boolean caseSensitive;
  final boolean isRegExp;
  
  public final static int MAX_MATCH_LENGTH = 250;

  private StringMatcher(String pattern, boolean isRegExp, boolean caseSensitive) {
    this.pattern = pattern;
    this.caseSensitive = caseSensitive;
    this.isRegExp = isRegExp;
  }

  /**
   * @return all values that this matcher can possibly accept (e.g. extracted from regexps like "foo|bar"),
   * or {@code null} if it's not possible to determine those.
   */
  @Nullable
  public abstract Set<String> getPossibleValues();

  /**
   * @return whether the given string is accepted by this matcher.
   */
  public abstract boolean matches(String s);

  /**
   * Create a case-sensitive regexp matcher.
   * @since 5.6
   */
  public static StringMatcher regexp(String pattern) {
    return create(pattern, true, true);
  }

  public static StringMatcher create(String pattern, boolean isRegExp, boolean caseSensitive) {
    return create(pattern, isRegExp, caseSensitive, Function.identity());
  }

  static StringMatcher create(String pattern, boolean isRegExp, boolean caseSensitive, Function<String, String> internString) {
    if (!isRegExp || "\\0".equals(pattern)) {
      return stringEquals(pattern, isRegExp, caseSensitive);
    }

    // always compile the pattern to check it's well-formed
    Pattern compiled = Pattern.compile(pattern, caseSensitive ? 0 : Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE);

    Set<String> possibleRegexpValues = getPossibleRegexpValues(pattern);
    if (possibleRegexpValues != null) {
      Set<String> set = possibleRegexpValues.stream().map(internString).collect(Collectors.toSet());
      if (set.size() == 1) {
        return stringEquals(set.iterator().next(), true, caseSensitive);
      }
      if (!caseSensitive) {
        String[] sorted = set.toArray(new String[0]);
        Arrays.sort(sorted, String.CASE_INSENSITIVE_ORDER);
        return new StringMatcher(pattern, true, false) {
          @Override
          public Set<String> getPossibleValues() {
            return Sets.newHashSet(sorted);
          }

          @Override
          public boolean matches(String s) {
            if (s.length() > MAX_MATCH_LENGTH) {
              return false;
            }
            return Arrays.binarySearch(sorted, s, String.CASE_INSENSITIVE_ORDER) >= 0;
          }
        };
      }
      return new StringMatcher(pattern, true, true) {
        @Override
        public Set<String> getPossibleValues() {
          return Collections.unmodifiableSet(set);
        }

        @Override
        public boolean matches(String s) {
          if (s.length() > MAX_MATCH_LENGTH) {
            return false;
          }
          return set.contains(s);
        }
      };
    }

    Substrings required = getRequiredSubstrings(pattern);
    Substrings exhaustive = required == null ? null : required.checkCanReplaceRegex(pattern);
    boolean substringsAreSufficient = exhaustive != null;
    Substrings substrings = substringsAreSufficient ? exhaustive : required;

    return new StringMatcher(pattern, true, caseSensitive) {
      @Nullable
      @Override
      public Set<String> getPossibleValues() {
        return null;
      }

      @Override
      public boolean matches(String s) {
        if (s.length() > MAX_MATCH_LENGTH) {
          return false;
        }
        if (substrings != null && !substrings.matches(s, caseSensitive)) return false;
        if (substringsAreSufficient) return true;
        return compiled.matcher(new InterruptibleCharSequence(s)).matches();
      }
    };
  }

  @NotNull
  private static StringMatcher stringEquals(String pattern, final boolean isRegExp, boolean caseSensitive) {
    return new StringMatcher(pattern, isRegExp, caseSensitive) {
      @Override
      public Set<String> getPossibleValues() {
        return Collections.singleton(pattern);
      }

      @Override
      public boolean matches(String s) {
        if (s.length() > MAX_MATCH_LENGTH) {
          return false;
        }
        return caseSensitive ? s.equals(pattern) : s.equalsIgnoreCase(pattern);
      }
    };
  }

  /**
   * @return the substrings that any text would necessarily contain or start/end with if it matches the given regexp,
   * or {@code null} if no such substrings can be found
   */
  @Nullable
  static Substrings getRequiredSubstrings(String regexp) {
    Substrings UNKNOWN = new Substrings(false, false, new String[0]);

    RegexpParser<Substrings> parser = new RegexpParser<Substrings>(regexp) {
      @Override
      Substrings handleConcatenation(Substrings left, Substrings right) {
        return left.concat(right);
      }

      @Override
      Substrings handleOr(List<Substrings> components) {
        return UNKNOWN;
      }

      @Override
      protected Substrings optional(Substrings groupResults, char op) {
        return UNKNOWN;
      }

      @Override
      protected Substrings unknown() {
        return UNKNOWN;
      }

      @Override
      protected Substrings literal(String literal) {
        return new Substrings(true, true, new String[]{literal});
      }
    };
    try {
      Substrings result = parser.disjunction();
      return result.substrings.length == 0 ? null : result;
    } catch (TooComplexRegexp e) {
      return null;
    }
  }

  /**
   * @return all strings that the given regexp can ever match, or {@code null} if such set couldn't be enumerated
   */
  @Nullable
  @VisibleForTesting
  static Set<String> getPossibleRegexpValues(String regexp) {
    RegexpParser<Stream<String>> parser = new RegexpParser<Stream<String>>(regexp) {
      @Override
      Stream<String> handleConcatenation(Stream<String> left, Stream<String> right) {
        List<String> groupResults = right.collect(Collectors.toList());
        return left.flatMap(s1 -> groupResults.stream().map(s2 -> s1 + s2));
      }

      @Override
      Stream<String> handleOr(List<Stream<String>> components) {
        return components.stream().flatMap(Function.identity());
      }

      @Override
      protected Stream<String> optional(Stream<String> groupResults, char op) {
        return op == '?' ? Stream.concat(Stream.of(""), groupResults) : unknown();
      }

      @Override
      protected Stream<String> unknown() {
        throw TooComplexRegexp.INSTANCE;
      }

      @Override
      protected Stream<String> literal(String literal) {
        return Stream.of(literal);
      }
    };
    try {
      return parser.disjunction().collect(Collectors.toSet());
    } catch (TooComplexRegexp e) {
      return null;
    }
  }

  private static abstract class RegexpParser<T> {
    private static final String unsupported = "?$^{}*+";
    private static final String finishing = ")|";
    private static final String starting = "([\\";
    private static final String nonLiteral = finishing + unsupported + starting + ".";

    private final String regexp;
    private int pos;

    RegexpParser(String regexp) {
      if (regexp.startsWith("\\b")) {
        regexp = regexp.substring(2);
      }
      if (regexp.startsWith("^")) {
        regexp = regexp.substring(1);
      }
      if (regexp.endsWith("\\b") && !regexp.endsWith("\\\\b")) {
        regexp = regexp.substring(0, regexp.length() - 2);
      }
      if (regexp.endsWith("$") && !regexp.endsWith("\\$")) {
        regexp = regexp.substring(0, regexp.length() - 1);
      }
      this.regexp = regexp;
    }

    T disjunction() {
      List<T> components = new ArrayList<>();
      components.add(concatenation());
      while (true) {
        if (pos >= regexp.length() || regexp.charAt(pos) != '|') {
          return components.size() == 1 ? components.get(0) : handleOr(components);
        }
        pos++;
        components.add(concatenation());
      }
    }

    abstract T handleOr(List<T> components);

    abstract T handleConcatenation(T left, T right);

    protected abstract T optional(T groupResults, char op);

    protected abstract T literal(String literal);

    protected abstract T unknown();

    private T concatenation() {
      T result = postfix();

      while (pos < regexp.length()) {
        char c = regexp.charAt(pos);
        if (finishing.indexOf(c) >= 0) break;
        if (unsupported.indexOf(c) >= 0) throw TooComplexRegexp.INSTANCE;

        result = handleConcatenation(result, postfix());
      }
      return result;
    }

    private T postfix() {
      T groupResults = atom();
      if (pos < regexp.length()) {
        char next = regexp.charAt(pos);
        if (next == '{') {
          int closing = regexp.indexOf('}', pos + 1);
          if (closing < 0) throw new AssertionError("Closing } expected after " + pos);
          pos = closing + 1;
          groupResults = unknown();
          if (pos >= regexp.length()) {
            return groupResults;
          }
          next = regexp.charAt(pos);
        }
        if ("*+?".indexOf(next) >= 0) {
          pos++;
          return optional(groupResults, next);
        }
      }
      return groupResults;
    }

    private T atom() {
      if (pos >= regexp.length()) return literal("");
      
      switch (regexp.charAt(pos)) {
        case '(':
          if (regexp.charAt(++pos) == '?') {
            if (regexp.charAt(++pos) != ':') {
              throw TooComplexRegexp.INSTANCE;
            }
            pos++;
          }
          T group = disjunction();
          if (regexp.charAt(pos++) != ')') throw TooComplexRegexp.INSTANCE;
          return group;
        case '[':
          return squareBracketGroup();
        case '\\':
          pos++;
          return charLiteral(escape());
        case '.':
          pos++;
          return unknown();
        default:
          int literalStart = pos;
          while (pos < regexp.length() && nonLiteral.indexOf(regexp.charAt(pos)) < 0) pos++;
          if (literalStart + 1 < pos && pos < regexp.length() && regexp.charAt(pos) == '?') pos--;
          return literal(regexp.substring(literalStart, pos));
      }
    }

    private T squareBracketGroup() {
      int start = ++pos;
      List<Character> options = new ArrayList<>();
      while (true) {
        char c1 = regexp.charAt(pos++);
        if (c1 == ']') break;

        if (c1 == '-' && pos != start + 1 && regexp.charAt(pos) != ']') {
          Character last = options == null ? null : options.get(options.size() - 1);
          char next = regexp.charAt(pos++);
          if (last == null || next == '\\' || next - last > 10) {
            options = null;
          }
          if (options != null) {
            for (int c = last + 1; c <= next; c++) {
              options.add((char) c);
            }
          }
        } else if (c1 == '^') {
          options = null;
        } else if (c1 == '[') {
          throw TooComplexRegexp.INSTANCE;
        } else {
          Character simpleChar = c1 == '\\' ? escape() : (Character) c1;
          if (options != null) {
            options.add(simpleChar);
          }
        }
      }
      if (options == null) return unknown();
      List<T> components = options.stream().map(c -> charLiteral(c)).collect(Collectors.toList());
      if (components.isEmpty()) throw TooComplexRegexp.INSTANCE;
      return components.size() == 1 ? components.get(0) : handleOr(components);
    }

    private T charLiteral(@Nullable Character c) {
      return c == null ? unknown() : literal(String.valueOf(c));
    }

    @Nullable
    private Character escape() {
      char next = regexp.charAt(pos++);
      if ("0xucpP".indexOf(next) >= 0) throw TooComplexRegexp.INSTANCE;
      if (Character.isLetterOrDigit(next)) return null;
      return next;
    }

  }

  private static class TooComplexRegexp extends RuntimeException {
    private static final TooComplexRegexp INSTANCE = new TooComplexRegexp();
  }

}
