From b92acd3cf2d90caf3914d02c21ac5cddea8ec2b4 Mon Sep 17 00:00:00 2001 From: ridiculousfish Date: Fri, 7 Aug 2015 13:28:47 -0700 Subject: Initial implementation of intermediate fuzzy completion e.g. /u/l/b may be expanded to /usr/local/bin --- src/wildcard.cpp | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 101 insertions(+), 5 deletions(-) (limited to 'src/wildcard.cpp') diff --git a/src/wildcard.cpp b/src/wildcard.cpp index 520d5435..e178a191 100644 --- a/src/wildcard.cpp +++ b/src/wildcard.cpp @@ -155,10 +155,10 @@ static enum fuzzy_match_type_t wildcard_match_internal(const wchar_t *str, const } /* Hackish fuzzy match support */ - if (0 && ! wildcard_has(wc, true)) + if (! wildcard_has(wc, true)) { const string_fuzzy_match_t match = string_fuzzy_match_string(wc, str); - return match.type <= max_type ? match.type : fuzzy_match_none; + return (match.type <= max_type ? match.type : fuzzy_match_none); } if (*wc == ANY_STRING || *wc == ANY_STRING_RECURSIVE) @@ -180,7 +180,9 @@ static enum fuzzy_match_type_t wildcard_match_internal(const wchar_t *str, const { enum fuzzy_match_type_t subresult = wildcard_match_internal(str, wc+1, leading_dots_fail_to_match, false, max_type); if (subresult != fuzzy_match_none) + { return subresult; + } } while (*str++ != 0); return fuzzy_match_none; } @@ -287,7 +289,7 @@ static bool wildcard_complete_internal(const wchar_t *str, } /* Locate the next wildcard character position, e.g. ANY_CHAR or ANY_STRING */ - size_t next_wc_char_pos = wildcard_find(wc); + const size_t next_wc_char_pos = wildcard_find(wc); /* Maybe we have no more wildcards at all. This includes the empty string. */ if (next_wc_char_pos == wcstring::npos) @@ -362,6 +364,12 @@ static bool wildcard_complete_internal(const wchar_t *str, case ANY_STRING: { + /* Hackish. If this is the last character of the wildcard, then just complete with the empty string. This fixes cases like "f*" -> "f*o" */ + if (wc[1] == L'\0') + { + return wildcard_complete_internal(L"", L"", params, flags, out); + } + /* Try all submatches. #929: if the recursive call gives us a prefix match, just stop. This is sloppy - what we really want to do is say, once we've seen a match of a particular type, ignore all matches of that type further down the string, such that the wildcard produces the "minimal match.". */ bool has_match = false; for (size_t i=0; str[i] != L'\0'; i++) @@ -417,6 +425,11 @@ bool wildcard_match(const wcstring &str, const wcstring &wc, bool leading_dots_f enum fuzzy_match_type_t match = wildcard_match_internal(str.c_str(), wc.c_str(), leading_dots_fail_to_match, true /* first */, fuzzy_match_exact); return match != fuzzy_match_none; } + +enum fuzzy_match_type_t wildcard_match_fuzzy(const wcstring &str, const wcstring &wc, bool leading_dots_fail_to_match, enum fuzzy_match_type_t max_type) +{ + return wildcard_match_internal(str.c_str(), wc.c_str(), leading_dots_fail_to_match, true /* first */, max_type); +} /** Obtain a description string for the file specified by the filename. @@ -665,6 +678,11 @@ class wildcard_expander_t */ void expand_intermediate_segment(const wcstring &base_dir, DIR *base_dir_fp, const wcstring &wc_segment, const wchar_t *wc_remainder); + /* Given a directory base_dir, which is opened as base_dir_fp, expand an intermediate literal segment. + Use a fuzzy matching algorithm. + */ + void expand_literal_intermediate_segment_with_fuzz(const wcstring &base_dir, DIR *base_dir_fp, const wcstring &wc_segment, const wchar_t *wc_remainder); + /* Given a directory base_dir, which is opened as base_dir_fp, expand the last segment of the wildcard. Treat ANY_STRING_RECURSIVE as ANY_STRING. wc is the wildcard segment to use for matching @@ -825,6 +843,81 @@ void wildcard_expander_t::expand_intermediate_segment(const wcstring &base_dir, this->expand(full_path, wc_remainder); } } + +void wildcard_expander_t::expand_literal_intermediate_segment_with_fuzz(const wcstring &base_dir, DIR *base_dir_fp, const wcstring &wc_segment, const wchar_t *wc_remainder) +{ + // This only works with tab completions + // Ordinary wildcard expansion should never go fuzzy + wcstring name_str; + while (!interrupted() && wreaddir(base_dir_fp, name_str)) + { + /* Don't bother with . and .. */ + if (contains(name_str, L".", L"..")) + { + continue; + } + + // Skip cases that don't match or match exactly + // The match-exactly case was handled directly in expand() + const string_fuzzy_match_t match = string_fuzzy_match_string(wc_segment, name_str); + if (match.type == fuzzy_match_none || match.type == fuzzy_match_exact) + { + continue; + } + + wcstring new_full_path = base_dir + name_str; + new_full_path.push_back(L'/'); + struct stat buf; + if (0 != wstat(new_full_path, &buf) || !S_ISDIR(buf.st_mode)) + { + /* We either can't stat it, or we did but it's not a directory */ + continue; + } + + // Ok, this directory matches. Recurse to it. + // Then perform serious surgery on each result! + // Each result was computed with a prefix of original_wildcard + // We need to replace our segment of that with our name_str + // We also have to mark the completion as replacing and fuzzy + const size_t before = this->resolved_completions->size(); + + this->expand(new_full_path, wc_remainder); + const size_t after = this->resolved_completions->size(); + + assert(before <= after); + for (size_t i=before; i < after; i++) + { + completion_t *c = &this->resolved_completions->at(i); + // Mark the completion as replacing + if (!(c->flags & COMPLETE_REPLACES_TOKEN)) + { + c->flags |= COMPLETE_REPLACES_TOKEN; + c->prepend_token_prefix(this->original_wildcard); + c->prepend_token_prefix(this->original_base); + } + // Ok, it's now replacing and is prefixed with the segment base, plus our original wildcard + // Replace our segment with name_str + // Our segment starts at the length of the original wildcard, minus what we have left to process, minus the length of our segment + // This logic is way too picky. Need to clean this up. + // One possibility is to send the "resolved wildcard" along with the actual wildcard + const size_t original_wildcard_len = wcslen(this->original_wildcard); + const size_t wc_remainder_len = wcslen(wc_remainder); + const size_t segment_len = wc_segment.length(); + assert(c->completion.length() >= original_wildcard_len); + const size_t segment_start = original_wildcard_len + this->original_base.size() - wc_remainder_len - wc_segment.length() - 1; // -1 for the slash after our segment + assert(segment_start < original_wildcard_len); + assert(c->completion.substr(segment_start, segment_len) == wc_segment); + c->completion.replace(segment_start, segment_len, name_str); + + // And every match must be made at least as fuzzy as ours + if (match.compare(c->match) > 0) + { + // Our match is fuzzier + c->match = match; + } + } + } +} void wildcard_expander_t::expand_last_segment(const wcstring &base_dir, DIR *base_dir_fp, const wcstring &wc) { @@ -906,13 +999,14 @@ void wildcard_expander_t::expand(const wcstring &base_dir, const wchar_t *wc) /* This just trumps everything */ size_t before = this->resolved_completions->size(); this->expand(base_dir + wc_segment + L'/', wc_remainder); - if (this->resolved_completions->size() == before) + if ((this->flags & EXPAND_FUZZY_MATCH) && this->resolved_completions->size() == before) { /* Nothing was found with the literal match. Try a fuzzy match (#94). */ + assert(this->flags & EXPAND_FOR_COMPLETIONS); DIR *base_dir_fd = open_dir(base_dir); if (base_dir_fd != NULL) { - this->expand_intermediate_segment(base_dir, base_dir_fd, wc_segment, wc_remainder); + this->expand_literal_intermediate_segment_with_fuzz(base_dir, base_dir_fd, wc_segment, wc_remainder); closedir(base_dir_fd); } } @@ -973,6 +1067,8 @@ static int wildcard_expand(const wchar_t *wc, int wildcard_expand_string(const wcstring &wc, const wcstring &base_dir, expand_flags_t flags, std::vector *output) { assert(output != NULL); + /* Fuzzy matching only if we're doing completions */ + assert((flags & (EXPAND_FUZZY_MATCH | EXPAND_FOR_COMPLETIONS)) != EXPAND_FUZZY_MATCH); /* Hackish fix for 1631. We are about to call c_str(), which will produce a string truncated at any embedded nulls. We could fix this by passing around the size, etc. However embedded nulls are never allowed in a filename, so we just check for them and return 0 (no matches) if there is an embedded null. */ if (wc.find(L'\0') != wcstring::npos) { -- cgit v1.2.3