<commit_before>/*
 * Copyright 2000-2013 JetBrains s.r.o.
 *
 * 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.intellij.psi.codeStyle;

import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.util.TextRange;
import com.intellij.openapi.util.text.StringUtil;
import com.intellij.util.containers.FList;
import com.intellij.util.io.IOUtil;
import com.intellij.util.text.Matcher;
import org.jetbrains.annotations.NonNls;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.BitSet;
import java.util.Iterator;

/**
* @author peter
*/
public class MinusculeMatcher implements Matcher {
  private static final Logger LOG = Logger.getInstance("#com.intellij.psi.codeStyle.MinusculeMatcher");
  /**
   * Lowercase humps don't work for parts separated by these characters
   * Need either an explicit uppercase letter or the same separator character in prefix
   */
  private static final String HARD_SEPARATORS = " ()";
  private final ThreadLocal<MatchingState> myMatchingState = new ThreadLocal<MatchingState>() {
    @Override
    protected MatchingState initialValue() {
      return new MatchingState();
    }
  };

  private final char[] myPattern;
  private final NameUtil.MatchingCaseSensitivity myOptions;
  private final boolean myHasHumps;
  private final boolean myHasSeparators;
  private final boolean myHasDots;
  private final boolean[] isLowerCase;
  private final boolean[] isUpperCase;
  private final boolean[] isWordSeparator;
  private final char[] toUpperCase;
  private final char[] toLowerCase;
  private final boolean myHasWildCards;

  public MinusculeMatcher(@NotNull String pattern, @NotNull NameUtil.MatchingCaseSensitivity options) {
    myOptions = options;
    myPattern = StringUtil.trimEnd(pattern, "* ").toCharArray();
    isLowerCase = new boolean[myPattern.length];
    isUpperCase = new boolean[myPattern.length];
    isWordSeparator = new boolean[myPattern.length];
    toUpperCase = new char[myPattern.length];
    toLowerCase = new char[myPattern.length];
    for (int k = 0; k < myPattern.length; k++) {
      char c = myPattern[k];
      isLowerCase[k] = Character.isLowerCase(c);
      isUpperCase[k] = Character.isUpperCase(c);
      isWordSeparator[k] = isWordSeparator(c);
      toUpperCase[k] = StringUtil.toUpperCase(c);
      toLowerCase[k] = StringUtil.toLowerCase(c);
    }
    int i = 0;
    while (isWildcard(i)) i++;
    myHasHumps = hasFlag(i + 1, isUpperCase) && hasFlag(i, isLowerCase);
    myHasSeparators = hasFlag(i, isWordSeparator);
    myHasDots = hasDots(i);
    myHasWildCards = hasWildCards();
  }

  private static boolean isWordSeparator(char c) {
    return Character.isWhitespace(c) || c == '_' || c == '-' || c == ':' || c == '+';
  }

  private static boolean isWordStart(String text, int i) {
    char c = text.charAt(i);
    if (Character.isUpperCase(c)) {
      if (i > 0 && Character.isUpperCase(text.charAt(i - 1))) {
        // check that we're not in the middle of an all-caps word
        return i + 1 < text.length() && Character.isLowerCase(text.charAt(i + 1));
      }
      return true;
    }
    if (Character.isDigit(c)) {
      return true;
    }
    if (!Character.isLetter(c)) {
      return false;
    }
    return i == 0 || !Character.isLetterOrDigit(text.charAt(i - 1));
  }

  private boolean hasWildCards() {
    for (int i = 0; i < myPattern.length; i++) {
      if (isWildcard(i)) {
        return true;
      }
    }
    return false;
  }

  private boolean hasFlag(int start, boolean[] flags) {
    for (int i = start; i < myPattern.length; i++) {
      if (flags[i]) {
        return true;
      }
    }
    return false;
  }

  private boolean hasDots(int start) {
    for (int i = start; i < myPattern.length; i++) {
      if (myPattern[i] == '.') {
        return true;
      }
    }
    return false;
  }

  private static FList<TextRange> prependRange(@NotNull FList<TextRange> ranges, int from, int length) {
    TextRange head = ranges.getHead();
    if (head != null && head.getStartOffset() == from + length) {
      return ranges.getTail().prepend(new TextRange(from, head.getEndOffset()));
    }
    return ranges.prepend(TextRange.from(from, length));
  }

  public int matchingDegree(@NotNull String name) {
    FList<TextRange> iterable = matchingFragments(name);
    if (iterable == null) return Integer.MIN_VALUE;
    if (iterable.isEmpty()) return 0;

    final TextRange first = iterable.getHead();
    boolean startMatch = first.getStartOffset() == 0;

    int matchingCase = 0;
    int p = -1;

    int integral = 0; // -sum of matching-char-count * hump-index over all matched humps; favors longer fragments matching earlier words
    int humpIndex = 1;
    int nextHumpStart = 0;
    for (TextRange range : iterable) {
      for (int i = range.getStartOffset(); i < range.getEndOffset(); i++) {
        boolean isHumpStart = false;
        while (nextHumpStart <= i) {
          if (nextHumpStart == i) {
            isHumpStart = true;
          }
          nextHumpStart = NameUtil.nextWord(name, nextHumpStart);
          if (first != range) {
            humpIndex++;
          }
        }
        integral -= humpIndex;

        char c = name.charAt(i);
        p = StringUtil.indexOf(myPattern, c, p + 1, myPattern.length, false);
        if (p < 0) {
          break;
        }

        if (c == myPattern[p]) {
          if (isUpperCase[p]) matchingCase += 50; // strongly prefer user's uppercase matching uppercase: they made an effort to press Shift
          else if (i == 0 && startMatch) matchingCase += 15; // the very first letter case distinguishes classes in Java etc
          else if (isHumpStart) matchingCase += 1; // if a lowercase matches lowercase hump start, that also means something 
        } else if (isHumpStart) {
          // disfavor hump starts where pattern letter case doesn't match name case
          matchingCase -= 20;
        }
      }
    }

    int startIndex = first.getStartOffset();
    boolean afterSeparator = StringUtil.indexOfAny(name, HARD_SEPARATORS, 0, startIndex) >= 0;
    boolean wordStart = startIndex == 0 || isWordStart(name, startIndex) && !isWordStart(name, startIndex - 1);
    boolean finalMatch = iterable.get(iterable.size() - 1).getEndOffset() == name.length();

    return (wordStart ? 1000 : 0) + 
           integral * 10 + 
           matchingCase * (startMatch ? 10 : 1) + // in start matches, case is more important; in middle matches - fragment length (integral)
           (afterSeparator ? 0 : 2) + 
           (finalMatch ? 1 : 0);
  }

  public boolean isStartMatch(@NotNull String name) {
    Iterable<TextRange> fragments = matchingFragments(name);
    if (fragments != null) {
      Iterator<TextRange> iterator = fragments.iterator();
      if (!iterator.hasNext() || iterator.next().getStartOffset() == 0) {
        return true;
      }
    }
    return false;
  }

  @Override
  public boolean matches(@NotNull String name) {
    // optimisation: name too short for this pattern
    if (!myHasWildCards && name.length() < myPattern.length) return false;

    return matchingFragments(name) != null;
  }

  @Nullable
  public FList<TextRange> matchingFragments(@NotNull String name) {
    long start = System.currentTimeMillis();
    MatchingState state = myMatchingState.get();
    state.initializeState(name);
    try {
      return matchWildcards(name, 0, 0, state);
    }
    finally {
      state.releaseState();
      if (System.currentTimeMillis() - start > 1000 &&
          // if there's little free memory, it might have been the gc affecting the performance
          Runtime.getRuntime().freeMemory() > Runtime.getRuntime().totalMemory() * 3 / 10) {
        LOG.error("Too long matching: name=" + name + "; prefix=" + new String(myPattern));
      }
    }
  }

  /**
   * After a wildcard (* or space), search for the first non-wildcard pattern character in the name starting from nameIndex
   * and try to {@link #matchFragment(String, int, int, com.intellij.psi.codeStyle.MinusculeMatcher.MatchingState)} for it.
   */
  @Nullable
  private FList<TextRange> matchWildcards(@NotNull String name,
                                          int patternIndex,
                                          int nameIndex,
                                          MatchingState matchingState) {
    if (nameIndex < 0) {
      return null;
    }
    if (!isWildcard(patternIndex)) {<commit_msg>MinusculeMatcher: don't make grand claims about slowness on the basis of just one measurement<commit_after>/*
 * Copyright 2000-2013 JetBrains s.r.o.
 *
 * 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.intellij.psi.codeStyle;

import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.util.TextRange;
import com.intellij.openapi.util.text.StringUtil;
import com.intellij.util.containers.FList;
import com.intellij.util.io.IOUtil;
import com.intellij.util.text.Matcher;
import org.jetbrains.annotations.NonNls;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.BitSet;
import java.util.Iterator;

/**
* @author peter
*/
public class MinusculeMatcher implements Matcher {
  private static final Logger LOG = Logger.getInstance("#com.intellij.psi.codeStyle.MinusculeMatcher");
  /**
   * Lowercase humps don't work for parts separated by these characters
   * Need either an explicit uppercase letter or the same separator character in prefix
   */
  private static final String HARD_SEPARATORS = " ()";
  private final ThreadLocal<MatchingState> myMatchingState = new ThreadLocal<MatchingState>() {
    @Override
    protected MatchingState initialValue() {
      return new MatchingState();
    }
  };

  private final char[] myPattern;
  private final NameUtil.MatchingCaseSensitivity myOptions;
  private final boolean myHasHumps;
  private final boolean myHasSeparators;
  private final boolean myHasDots;
  private final boolean[] isLowerCase;
  private final boolean[] isUpperCase;
  private final boolean[] isWordSeparator;
  private final char[] toUpperCase;
  private final char[] toLowerCase;
  private final boolean myHasWildCards;

  public MinusculeMatcher(@NotNull String pattern, @NotNull NameUtil.MatchingCaseSensitivity options) {
    myOptions = options;
    myPattern = StringUtil.trimEnd(pattern, "* ").toCharArray();
    isLowerCase = new boolean[myPattern.length];
    isUpperCase = new boolean[myPattern.length];
    isWordSeparator = new boolean[myPattern.length];
    toUpperCase = new char[myPattern.length];
    toLowerCase = new char[myPattern.length];
    for (int k = 0; k < myPattern.length; k++) {
      char c = myPattern[k];
      isLowerCase[k] = Character.isLowerCase(c);
      isUpperCase[k] = Character.isUpperCase(c);
      isWordSeparator[k] = isWordSeparator(c);
      toUpperCase[k] = StringUtil.toUpperCase(c);
      toLowerCase[k] = StringUtil.toLowerCase(c);
    }
    int i = 0;
    while (isWildcard(i)) i++;
    myHasHumps = hasFlag(i + 1, isUpperCase) && hasFlag(i, isLowerCase);
    myHasSeparators = hasFlag(i, isWordSeparator);
    myHasDots = hasDots(i);
    myHasWildCards = hasWildCards();
  }

  private static boolean isWordSeparator(char c) {
    return Character.isWhitespace(c) || c == '_' || c == '-' || c == ':' || c == '+';
  }

  private static boolean isWordStart(String text, int i) {
    char c = text.charAt(i);
    if (Character.isUpperCase(c)) {
      if (i > 0 && Character.isUpperCase(text.charAt(i - 1))) {
        // check that we're not in the middle of an all-caps word
        return i + 1 < text.length() && Character.isLowerCase(text.charAt(i + 1));
      }
      return true;
    }
    if (Character.isDigit(c)) {
      return true;
    }
    if (!Character.isLetter(c)) {
      return false;
    }
    return i == 0 || !Character.isLetterOrDigit(text.charAt(i - 1));
  }

  private boolean hasWildCards() {
    for (int i = 0; i < myPattern.length; i++) {
      if (isWildcard(i)) {
        return true;
      }
    }
    return false;
  }

  private boolean hasFlag(int start, boolean[] flags) {
    for (int i = start; i < myPattern.length; i++) {
      if (flags[i]) {
        return true;
      }
    }
    return false;
  }

  private boolean hasDots(int start) {
    for (int i = start; i < myPattern.length; i++) {
      if (myPattern[i] == '.') {
        return true;
      }
    }
    return false;
  }

  private static FList<TextRange> prependRange(@NotNull FList<TextRange> ranges, int from, int length) {
    TextRange head = ranges.getHead();
    if (head != null && head.getStartOffset() == from + length) {
      return ranges.getTail().prepend(new TextRange(from, head.getEndOffset()));
    }
    return ranges.prepend(TextRange.from(from, length));
  }

  public int matchingDegree(@NotNull String name) {
    FList<TextRange> iterable = matchingFragments(name);
    if (iterable == null) return Integer.MIN_VALUE;
    if (iterable.isEmpty()) return 0;

    final TextRange first = iterable.getHead();
    boolean startMatch = first.getStartOffset() == 0;

    int matchingCase = 0;
    int p = -1;

    int integral = 0; // -sum of matching-char-count * hump-index over all matched humps; favors longer fragments matching earlier words
    int humpIndex = 1;
    int nextHumpStart = 0;
    for (TextRange range : iterable) {
      for (int i = range.getStartOffset(); i < range.getEndOffset(); i++) {
        boolean isHumpStart = false;
        while (nextHumpStart <= i) {
          if (nextHumpStart == i) {
            isHumpStart = true;
          }
          nextHumpStart = NameUtil.nextWord(name, nextHumpStart);
          if (first != range) {
            humpIndex++;
          }
        }
        integral -= humpIndex;

        char c = name.charAt(i);
        p = StringUtil.indexOf(myPattern, c, p + 1, myPattern.length, false);
        if (p < 0) {
          break;
        }

        if (c == myPattern[p]) {
          if (isUpperCase[p]) matchingCase += 50; // strongly prefer user's uppercase matching uppercase: they made an effort to press Shift
          else if (i == 0 && startMatch) matchingCase += 15; // the very first letter case distinguishes classes in Java etc
          else if (isHumpStart) matchingCase += 1; // if a lowercase matches lowercase hump start, that also means something 
        } else if (isHumpStart) {
          // disfavor hump starts where pattern letter case doesn't match name case
          matchingCase -= 20;
        }
      }
    }

    int startIndex = first.getStartOffset();
    boolean afterSeparator = StringUtil.indexOfAny(name, HARD_SEPARATORS, 0, startIndex) >= 0;
    boolean wordStart = startIndex == 0 || isWordStart(name, startIndex) && !isWordStart(name, startIndex - 1);
    boolean finalMatch = iterable.get(iterable.size() - 1).getEndOffset() == name.length();

    return (wordStart ? 1000 : 0) + 
           integral * 10 + 
           matchingCase * (startMatch ? 10 : 1) + // in start matches, case is more important; in middle matches - fragment length (integral)
           (afterSeparator ? 0 : 2) + 
           (finalMatch ? 1 : 0);
  }

  public boolean isStartMatch(@NotNull String name) {
    Iterable<TextRange> fragments = matchingFragments(name);
    if (fragments != null) {
      Iterator<TextRange> iterator = fragments.iterator();
      if (!iterator.hasNext() || iterator.next().getStartOffset() == 0) {
        return true;
      }
    }
    return false;
  }

  @Override
  public boolean matches(@NotNull String name) {
    // optimisation: name too short for this pattern
    if (!myHasWildCards && name.length() < myPattern.length) return false;

    return matchingFragments(name) != null;
  }

  @Nullable
  private FList<TextRange> calcMatchingFragments(@NotNull String name) {
    MatchingState state = myMatchingState.get();
    state.initializeState(name);
    try {
      return matchWildcards(name, 0, 0, state);
    }
    finally {
      state.releaseState();
    }
  }

  @Nullable
  public FList<TextRange> matchingFragments(@NotNull String name) {
    long start = System.currentTimeMillis();
    FList<TextRange> result = calcMatchingFragments(name);
    if (System.currentTimeMillis() - start > 1000 &&
        // if there's little free memory, it might have been the gc affecting the performance
        Runtime.getRuntime().freeMemory() > Runtime.getRuntime().totalMemory() * 3 / 10) {
      start = System.currentTimeMillis();
      calcMatchingFragments(name);
      if (System.currentTimeMillis() - start > 1000) {
        LOG.error("Too long name matching: name=" + name + "; prefix=" + new String(myPattern));
      }
    }
    return result;
  }

  /**
   * After a wildcard (* or space), search for the first non-wildcard pattern character in the name starting from nameIndex
   * and try to {@link #matchFragment(String, int, int, com.intellij.psi.codeStyle.MinusculeMatcher.MatchingState)} for it.
   */
  @Nullable
  private FList<TextRange> matchWildcards(@NotNull String name,
                                          int patternIndex,
                                          int nameIndex,
                                          MatchingState matchingState) {
    if (nameIndex < 0) {
      return null;
    }
    if (!isWildcard(patternIndex)) {
{'fraction_non_alphanumeric': 0.1117592542114158, 'fraction_numerical': 0.007741372730741973, 'mean_word_length': 2.933948102080206, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6079087', 'n_tokens_mistral': 5556, 'n_tokens_neox': 5355, 'n_words': 1576}