Header compiler args resolution heuristic doesn't work well for projects with separate include and source directories

[betasheet]

If used with compile_commands.json, ccls needs to infer compiler arguments for a header file from a related entry in the compilation database. To choose this entry, it uses a "similar file name" heuristic (ComputeGuessScore() in src/project.cc).

This heuristic currently computes a similarity score by comparing the prefix + suffix and counting the number of different directories between two files. This works fine for headers that are close to their respective sources (e.g. in same directory), but not so well for projects with separate include and source directories, e.g. "inc/long/path/to/my_file.h" and "src/long/path/to/my_file.cc", because neither prefix nor suffix match.

Would it be possible to update the heuristic to take into account the matching substring in the middle?

For example, I modified ComputeGuessScore locally as below, which works well for my project with separate src/include directories:

// Computes a score based on how well |a| and |b| match. This is used for
// argument guessing.
int ComputeGuessScore(std::string_view a, std::string_view b) {
  // Increase score based on common prefix and suffix. Prefixes are prioritized.
  if (a.size() > b.size())
    std::swap(a, b);
  size_t i = std::mismatch(a.begin(), a.end(), b.begin()).first - a.begin();
  size_t j = std::mismatch(a.rbegin(), a.rend(), b.rbegin()).first - a.rbegin();
  int score = 10 * i + j;
  if (i + j < a.size())
    score -= 100 * (std::count(a.begin() + i, a.end() - j, '/') +
                    std::count(b.begin() + i, b.end() - j, '/'));
  // Increase score for a common substring in the middle (e.g. in case of
  // separate source and include dirs.
  size_t max_middle = 0;
  size_t max_middle_dirs = 0;
  for (; i < a.size(); ++i) {
    for (size_t k = j; k < b.size(); ++k) {
      size_t matching = std::mismatch(a.begin() + i, a.end(), b.begin() + k, b.end()).first - (a.begin() + i);
      size_t dirs = std::count(a.begin() + i, a.begin() + i + matching, '/');
      max_middle = std::max(max_middle, matching);
      max_middle_dirs = std::max(max_middle_dirs, dirs);
    }
  }
  score += 10 * max_middle;
  score += 100 * max_middle_dirs;
  return score;
}

[MaskRay]

for (; i < a.size(); ++i) {
for (size_t k = j; k < b.size(); ++k) {
size_t matching = std::mismatch(a.begin() + i, a.end(), b.begin() + k, b.end()).first - (a.begin() + i);

The snippet is O(n^3). We should be a bit careful with the performance here.

Can you try #445?

[betasheet]

#445 seems to work well with one small modification :) b5ee0f7#r305709023

Thanks!

[MaskRay]

Merged #445