diff options
author | ridiculousfish <corydoras@ridiculousfish.com> | 2015-08-07 13:28:47 -0700 |
---|---|---|
committer | ridiculousfish <corydoras@ridiculousfish.com> | 2015-08-08 13:55:51 -0700 |
commit | b92acd3cf2d90caf3914d02c21ac5cddea8ec2b4 (patch) | |
tree | ea13a6ed845a1c7976ebc0be985ab902821d5a68 /src | |
parent | fd96bafbc85d44ea74f39cc2a1b4cbd846f5f51f (diff) |
Initial implementation of intermediate fuzzy completion
e.g. /u/l/b<tab> may be expanded to /usr/local/bin
Diffstat (limited to 'src')
-rw-r--r-- | src/fish_tests.cpp | 70 | ||||
-rw-r--r-- | src/reader.cpp | 2 | ||||
-rw-r--r-- | src/wildcard.cpp | 106 |
3 files changed, 166 insertions, 12 deletions
diff --git a/src/fish_tests.cpp b/src/fish_tests.cpp index 04d12ced..4a1c9563 100644 --- a/src/fish_tests.cpp +++ b/src/fish_tests.cpp @@ -63,6 +63,7 @@ #include "parse_util.h" #include "pager.h" #include "input.h" +#include "wildcard.h" #include "utf8.h" #include "env_universal_common.h" #include "wcstringutil.h" @@ -1440,14 +1441,30 @@ static void test_expand() expand_test(L"foo\\$bar", EXPAND_SKIP_VARIABLES, L"foo$bar", 0, L"Failed to handle dollar sign in variable-skipping expansion"); + + /* + b + x + bar + baz + xxx + yyy + bax + xxx + .foo + */ + if (system("mkdir -p /tmp/fish_expand_test/")) err(L"mkdir failed"); + if (system("mkdir -p /tmp/fish_expand_test/b/")) err(L"mkdir failed"); if (system("mkdir -p /tmp/fish_expand_test/baz/")) err(L"mkdir failed"); if (system("mkdir -p /tmp/fish_expand_test/bax/")) err(L"mkdir failed"); if (system("touch /tmp/fish_expand_test/.foo")) err(L"touch failed"); + if (system("touch /tmp/fish_expand_test/b/x")) err(L"touch failed"); if (system("touch /tmp/fish_expand_test/bar")) err(L"touch failed"); if (system("touch /tmp/fish_expand_test/bax/xxx")) err(L"touch failed"); if (system("touch /tmp/fish_expand_test/baz/xxx")) err(L"touch failed"); + if (system("touch /tmp/fish_expand_test/baz/yyy")) err(L"touch failed"); // This is checking that .* does NOT match . and .. (https://github.com/fish-shell/fish-shell/issues/270). But it does have to match literal components (e.g. "./*" has to match the same as "*" const wchar_t * const wnull = NULL; @@ -1461,26 +1478,44 @@ static void test_expand() expand_test(L"/tmp/fish_expand_test/*/xxx", 0, L"/tmp/fish_expand_test/bax/xxx", L"/tmp/fish_expand_test/baz/xxx", wnull, - L"Glob did the wrong thing"); + L"Glob did the wrong thing 1"); expand_test(L"/tmp/fish_expand_test/*z/xxx", 0, L"/tmp/fish_expand_test/baz/xxx", wnull, - L"Glob did the wrong thing"); + L"Glob did the wrong thing 2"); expand_test(L"/tmp/fish_expand_test/**z/xxx", 0, L"/tmp/fish_expand_test/baz/xxx", wnull, - L"Glob did the wrong thing"); + L"Glob did the wrong thing 3"); expand_test(L"/tmp/fish_expand_test/b**", 0, - L"/tmp/fish_expand_test/bar", L"/tmp/fish_expand_test/bax", L"/tmp/fish_expand_test/bax/xxx", L"/tmp/fish_expand_test/baz", L"/tmp/fish_expand_test/baz/xxx", wnull, - L"Glob did the wrong thing"); + L"/tmp/fish_expand_test/b", L"/tmp/fish_expand_test/b/x", L"/tmp/fish_expand_test/bar", L"/tmp/fish_expand_test/bax", L"/tmp/fish_expand_test/bax/xxx", L"/tmp/fish_expand_test/baz", L"/tmp/fish_expand_test/baz/xxx", L"/tmp/fish_expand_test/baz/yyy", wnull, + L"Glob did the wrong thing 4"); expand_test(L"/tmp/fish_expand_test/BA", EXPAND_FOR_COMPLETIONS, L"/tmp/fish_expand_test/bar", L"/tmp/fish_expand_test/bax/", L"/tmp/fish_expand_test/baz/", wnull, L"Case insensitive test did the wrong thing"); - + expand_test(L"/tmp/fish_expand_test/BA", EXPAND_FOR_COMPLETIONS, + L"/tmp/fish_expand_test/bar", L"/tmp/fish_expand_test/bax/", L"/tmp/fish_expand_test/baz/", wnull, + L"Case insensitive test did the wrong thing"); + + expand_test(L"/tmp/fish_expand_test/b/yyy", EXPAND_FOR_COMPLETIONS, + /* nothing! */ wnull, + L"Wrong fuzzy matching 1"); + expand_test(L"/tmp/fish_expand_test/b/x", EXPAND_FOR_COMPLETIONS | EXPAND_FUZZY_MATCH, + L"", wnull, // We just expect the empty string since this is an exact match + L"Wrong fuzzy matching 2"); + + expand_test(L"/tmp/fish_expand_test/b/xx*", EXPAND_FOR_COMPLETIONS | EXPAND_FUZZY_MATCH, + format_string(L"/tmp/fish_expand_test/bax/xx%lc", (wint_t)ANY_STRING).c_str(), format_string(L"/tmp/fish_expand_test/baz/xx%lc", (wint_t)ANY_STRING).c_str(), wnull, + L"Wrong fuzzy matching 3"); + + expand_test(L"/tmp/fish_expand_test/b/yyy", EXPAND_FOR_COMPLETIONS | EXPAND_FUZZY_MATCH, + L"/tmp/fish_expand_test/baz/yyy", wnull, + L"Wrong fuzzy matching 4"); + if (! expand_test(L"/tmp/fish_expand_test/.*", 0, L"/tmp/fish_expand_test/.foo", 0)) { err(L"Expansion not correctly handling dotfiles"); @@ -1489,7 +1524,30 @@ static void test_expand() { err(L"Expansion not correctly handling literal path components in dotfiles"); } + + char saved_wd[PATH_MAX] = {}; + if (NULL == getcwd(saved_wd, sizeof saved_wd)) + { + err(L"getcwd failed"); + return; + } + + if (chdir("/tmp/fish_expand_test")) + { + err(L"chdir failed"); + return; + } + + expand_test(L"b/xx", EXPAND_FOR_COMPLETIONS | EXPAND_FUZZY_MATCH, + L"bax/xxx", L"baz/xxx", wnull, + L"Wrong fuzzy matching 5"); + + if (chdir(saved_wd)) + { + err(L"chdir failed"); + } + if (system("rm -Rf /tmp/fish_expand_test")) err(L"rm failed"); } diff --git a/src/reader.cpp b/src/reader.cpp index 7aae5f6f..2b0874d7 100644 --- a/src/reader.cpp +++ b/src/reader.cpp @@ -1907,7 +1907,7 @@ static bool handle_completions(const std::vector<completion_t> &comp, bool conti assert(el->position >= prefix_start); len = el->position - prefix_start; - if (match_type_requires_full_replacement(best_match_type)) + if (will_replace_token || match_type_requires_full_replacement(best_match_type)) { // No prefix prefix.clear(); 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*<tab>" -> "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<completion_t> *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) { |