diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..04fd719
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,3 @@
+Language: Cpp
+BasedOnStyle: Google
+ColumnLimit: 0
diff --git a/.clang-tidy b/.clang-tidy
new file mode 100644
index 0000000..237092a
--- /dev/null
+++ b/.clang-tidy
@@ -0,0 +1,20 @@
+Checks: '
+-*,
+google-*,
+-google-runtime-references,
+-google-readability-avoid-underscore-in-googletest-name,
+llvm-include-order,
+llvm-namespace-comment,
+misc-throw-by-value-catch-by-reference,
+modernize*,
+-modernize-use-trailing-return-type,
+readability-container-size-empty,
+'
+
+WarningsAsErrors: '*'
+
+HeaderFilterRegex: './src/**/*'
+
+CheckOptions:
+- key: google-readability-braces-around-statements.ShortStatementLines
+ value: '3'
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..88eb5a1
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+build
+.cache
+compile_commands.json
+.luacheckcache
\ No newline at end of file
diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..a0e4cd8
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,60 @@
+cmake_minimum_required(VERSION 3.16)
+set(PROJECT_VERSION_NAME "v0.0.1")
+
+# Split and sanatize the project version so it can be uses as pars and used as
+# the project version "v1.1.1" is not a valida version number
+string(REPLACE "v" "" PROJECT_VERSION ${PROJECT_VERSION_NAME})
+string(REPLACE "." ";" VERSION_LIST ${PROJECT_VERSION})
+list(GET VERSION_LIST 0 PROJECT_VERSION_MAJOR)
+list(GET VERSION_LIST 1 PROJECT_VERSION_MINOR)
+list(GET VERSION_LIST 2 PROJECT_VERSION_PATCH)
+
+project ("Ivy" VERSION ${PROJECT_VERSION})
+set(CMAKE_CXX_STANDARD 17)
+set(CMAKE_CXX_STANDARD_REQUIRED ON)
+
+# Set the build type if its not test
+if(NOT CMAKE_BUILD_TYPE)
+ set(CMAKE_BUILD_TYPE "Release")
+endif()
+
+# Ensure the build type is valid
+if(NOT "${CMAKE_BUILD_TYPE}" STREQUAL "Debug" AND
+ NOT "${CMAKE_BUILD_TYPE}" STREQUAL "Release" AND
+ NOT "${CMAKE_BUILD_TYPE}" STREQUAL "MinSizeRel" AND
+ NOT "${CMAKE_BUILD_TYPE}" STREQUAL "RelWithDebInfo")
+ message(FATAL_ERROR "Unknown build type \"${CMAKE_BUILD_TYPE}\". Allowed values are Debug, Release, RelWithDebInfo, and MinSizeRel.")
+endif()
+
+# detect operating system and host processor
+message(STATUS "We are on a ${CMAKE_SYSTEM_NAME} system")
+message(STATUS "The host processor is ${CMAKE_HOST_SYSTEM_PROCESSOR}")
+
+# Place binaries and libraries according to GNU standards. For example
+# executables created with `add_executable` will be built into the `bin`
+# directory
+include(GNUInstallDirs)
+set(CMAKE_ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/${CMAKE_INSTALL_LIBDIR})
+set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/${CMAKE_INSTALL_LIBDIR})
+set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/${CMAKE_INSTALL_BINDIR})
+
+# Set the default compiler flags for GNU
+if(CMAKE_CXX_COMPILER_ID MATCHES GNU)
+ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wunreachable-code -Wno-unknown-pragmas -Wno-sign-compare -Wwrite-strings -Wno-unused")
+ set(CMAKE_CXX_FLAGS_DEBUG "-O0 -g3")
+ set(CMAKE_CXX_FLAGS_RELEASE "-O3 -DNDEBUG")
+endif()
+
+find_package(PkgConfig REQUIRED)
+find_package(Threads REQUIRED)
+
+file(GLOB_RECURSE IVY_HEADER "${CMAKE_CURRENT_LIST_DIR}/cpp/*.hpp")
+file(GLOB_RECURSE IVY_SOURCE "${CMAKE_CURRENT_LIST_DIR}/cpp/*.cpp")
+list(FILTER IVY_SOURCE EXCLUDE REGEX "_test\\.cpp$")
+list(FILTER IVY_SOURCE EXCLUDE REGEX "cli\\.cpp$")
+
+add_library(ivy SHARED ${IVY_SOURCE} ${IVY_HEADER})
+target_link_libraries(ivy Threads::Threads)
+
+add_executable(ivycli ${IVY_SOURCE} ${IVY_HEADER} ${CMAKE_CURRENT_LIST_DIR}/cpp/cli.cpp)
+target_link_libraries(ivycli Threads::Threads)
diff --git a/README.md b/README.md
index 14b5ab0..1b92924 100644
--- a/README.md
+++ b/README.md
@@ -1,61 +1,76 @@
# ivy.nvim
An [ivy-mode](https://github.com/abo-abo/swiper#ivy) port to neovim. Ivy is a
generic completion mechanism for ~~Emacs~~ Nvim
## Installation
### Manually
```sh
git clone https://github.com/AdeAttwood/ivy.nvim ~/.config/nvim/pack/bundle/start/ivy.nvim
```
### Plugin managers
TODO: Add docs in the plugin managers I don't use any
+### Compiling
+
+For the native searching, you will need to compile the shard library. You can
+do that by running the below command in the root of the plugin.
+
+```sh
+cmake -DCMAKE_BUILD_TYPE=Release -B build/Release && (cd build/Release; make -j)
+```
+
+If you are missing build dependencies, you can install them via apt.
+
+```sh
+sudo apt-get install build-essential pkg-config cmake
+```
+
## Features
### Commands
A command can be run that will launch the completion UI
| Command | Key Map | Description |
| ---------- | ----------- | ------------------------------------------------------ |
| IvyFd | \p | Find files in your project with the fd cli file finder |
| IvyAg | \/ | Find content in files using the silver searcher |
| IvyBuffers | | Search though open buffers |
### Actions
Action can be run on selected candidates provide functionality
| Action | Description |
| -------- | ------------------------------------------------------------------------------ |
| Complete | Run the completion function, usually this will be opening a file |
| Peek | Run the completion function on a selection, but don't close the results window |
## API
```lua
vim.ivy.run(
-- Call back function to get all the candidates that will be displayed in
-- the results window, The `input` will be passed in, so you can filter
-- your results with the value from the prompt
function(input) return { "One", "Two", Three } end,
-- Action callback that will be called on the completion or peek actions.
The currently selected item is passed in as the result.
function(result) vim.cmd("edit " .. result) end
)
```
## Other stuff you might like
- [ivy-mode](https://github.com/abo-abo/swiper#ivy) - An emacs package that was the inspiration for this nvim plugin
- [Command-T](https://github.com/wincent/command-t) - Vim plugin I used before I started this one
- [telescope.nvim](https://github.com/nvim-telescope/telescope.nvim) - Another competition plugin, lots of people are using
diff --git a/cpp/cli.cpp b/cpp/cli.cpp
new file mode 100644
index 0000000..9bd6d15
--- /dev/null
+++ b/cpp/cli.cpp
@@ -0,0 +1,35 @@
+#include
+#include
+#include
+#include
+#include
+
+#include "./file_scanner.hpp"
+#include "./sorter.hpp"
+
+int main(int argc, char* argv[]) {
+ std::vector args;
+ args.reserve(argc);
+ // Skip the first argument because that will be the programme name.
+ for (int i = 1; i < argc; i++) {
+ args.emplace_back(argv[i]);
+ }
+
+ if (args.empty()) {
+ std::cout << "Missing required search term" << std::endl;
+ return 1;
+ }
+
+ auto base_dir = std::filesystem::current_path();
+ std::string search = args.at(0);
+
+ auto sorter = ivy::Sorter(search);
+ auto scanner = ivy::FileScanner(base_dir);
+
+ std::regex pattern("([" + search + "])");
+ for (ivy::Match const& match : sorter.sort(scanner.scan())) {
+ std::cout << match.score << " " << std::regex_replace(match.content, pattern, "\033[1m$&\033[0m") << std::endl;
+ }
+
+ return 0;
+}
diff --git a/cpp/file_scanner.hpp b/cpp/file_scanner.hpp
new file mode 100644
index 0000000..3fc8209
--- /dev/null
+++ b/cpp/file_scanner.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+#include
+#include
+#include
+
+namespace fs = std::filesystem;
+
+namespace ivy {
+class FileScanner {
+ std::string m_base_dir;
+
+ public:
+ explicit FileScanner(const std::string base_dir) : m_base_dir(base_dir) {}
+
+ std::vector scan() {
+ std::vector results;
+ for (const fs::directory_entry& dir_entry : fs::recursive_directory_iterator(m_base_dir)) {
+ fs::path path = dir_entry.path();
+
+ // TODO(ade): sort out some kind of ignore thing. This will be needed
+ // when we start adding wildcard ignore functionality
+ if (path.string().find(".git") != std::string::npos) {
+ continue;
+ }
+
+ if (dir_entry.is_regular_file()) {
+ results.emplace_back(fs::relative(path, m_base_dir));
+ }
+ }
+
+ return results;
+ }
+};
+} // namespace ivy
diff --git a/cpp/fuzzy_match.cpp b/cpp/fuzzy_match.cpp
new file mode 100644
index 0000000..6a5d15d
--- /dev/null
+++ b/cpp/fuzzy_match.cpp
@@ -0,0 +1,198 @@
+// Copyright 2017-2018 ccls Authors
+// SPDX-License-Identifier: Apache-2.0
+
+// https://github.com/MaskRay/ccls/blob/master/src/fuzzy_match.cc
+
+#include "fuzzy_match.hpp"
+
+#include
+#include
+
+#include
+#include
+
+namespace ivy {
+namespace {
+enum CharClass { Other,
+ Lower,
+ Upper };
+enum CharRole { None,
+ Tail,
+ Head };
+
+CharClass getCharClass(int c) {
+ if (islower(c))
+ return Lower;
+ if (isupper(c))
+ return Upper;
+ return Other;
+}
+
+void calculateRoles(std::string_view s, int roles[], int *class_set) {
+ if (s.empty()) {
+ *class_set = 0;
+ return;
+ }
+ CharClass pre = Other, cur = getCharClass(s[0]), suc;
+ *class_set = 1 << cur;
+ auto fn = [&]() {
+ if (cur == Other)
+ return None;
+ // U(U)L is Head while U(U)U is Tail
+ return pre == Other || (cur == Upper && (pre == Lower || suc == Lower))
+ ? Head
+ : Tail;
+ };
+ for (size_t i = 0; i < s.size() - 1; i++) {
+ suc = getCharClass(s[i + 1]);
+ *class_set |= 1 << suc;
+ roles[i] = fn();
+ pre = cur;
+ cur = suc;
+ }
+ roles[s.size() - 1] = fn();
+}
+} // namespace
+
+int FuzzyMatcher::missScore(int j, bool last) {
+ int s = -3;
+ if (last)
+ s -= 10;
+ if (text_role[j] == Head)
+ s -= 10;
+ return s;
+}
+
+int FuzzyMatcher::matchScore(int i, int j, bool last) {
+ int s = 0;
+ // Case matching.
+ if (pat[i] == text[j]) {
+ s++;
+ // pat contains uppercase letters or prefix matching.
+ if ((pat_set & 1 << Upper) || i == j)
+ s++;
+ }
+ if (pat_role[i] == Head) {
+ if (text_role[j] == Head)
+ s += 30;
+ else if (text_role[j] == Tail)
+ s -= 10;
+ }
+ // Matching a tail while previous char wasn't matched.
+ if (text_role[j] == Tail && i && !last)
+ s -= 30;
+ // First char of pat matches a tail.
+ if (i == 0 && text_role[j] == Tail)
+ s -= 40;
+ return s;
+}
+
+FuzzyMatcher::FuzzyMatcher(std::string_view pattern, int sensitivity) {
+ calculateRoles(pattern, pat_role, &pat_set);
+ if (sensitivity == 1)
+ sensitivity = pat_set & 1 << Upper ? 2 : 0;
+ case_sensitivity = sensitivity;
+ size_t n = 0;
+ for (size_t i = 0; i < pattern.size(); i++)
+ if (pattern[i] != ' ') {
+ pat += pattern[i];
+ low_pat[n] = (char)::tolower(pattern[i]);
+ pat_role[n] = pat_role[i];
+ n++;
+ }
+}
+
+int FuzzyMatcher::match(std::string_view text, bool strict) {
+ if (pat.empty() != text.empty())
+ return kMinScore;
+ int n = int(text.size());
+ if (n > kMaxText)
+ return kMinScore + 1;
+ this->text = text;
+ for (int i = 0; i < n; i++)
+ low_text[i] = (char)::tolower(text[i]);
+ calculateRoles(text, text_role, &text_set);
+ if (strict && n && !!pat_role[0] != !!text_role[0])
+ return kMinScore;
+ dp[0][0][0] = dp[0][0][1] = 0;
+ for (int j = 0; j < n; j++) {
+ dp[0][j + 1][0] = dp[0][j][0] + missScore(j, false);
+ dp[0][j + 1][1] = kMinScore * 2;
+ }
+ for (int i = 0; i < int(pat.size()); i++) {
+ int(*pre)[2] = dp[i & 1];
+ int(*cur)[2] = dp[(i + 1) & 1];
+ cur[i][0] = cur[i][1] = kMinScore;
+ for (int j = i; j < n; j++) {
+ cur[j + 1][0] = std::max(cur[j][0] + missScore(j, false),
+ cur[j][1] + missScore(j, true));
+ // For the first char of pattern, apply extra restriction to filter bad
+ // candidates (e.g. |int| in |PRINT|)
+ cur[j + 1][1] = (case_sensitivity ? pat[i] == text[j]
+ : low_pat[i] == low_text[j] &&
+ (i || text_role[j] != Tail ||
+ pat[i] == text[j]))
+ ? std::max(pre[j][0] + matchScore(i, j, false),
+ pre[j][1] + matchScore(i, j, true))
+ : kMinScore * 2;
+ }
+ }
+
+ // Enumerate the end position of the match in str. Each removed trailing
+ // character has a penulty.
+ int ret = kMinScore;
+ for (int j = pat.size(); j <= n; j++)
+ ret = std::max(ret, dp[pat.size() & 1][j][1] - 2 * (n - j));
+ return ret;
+}
+} // namespace ivy
+
+#if 0
+TEST_SUITE("fuzzy_match") {
+ bool Ranks(std::string_view pat, std::vector texts) {
+ FuzzyMatcher fuzzy(pat, 0);
+ std::vector scores;
+ for (auto text : texts)
+ scores.push_back(fuzzy.Match(text));
+ bool ret = true;
+ for (size_t i = 0; i < texts.size() - 1; i++)
+ if (scores[i] < scores[i + 1]) {
+ ret = false;
+ break;
+ }
+ if (!ret) {
+ for (size_t i = 0; i < texts.size(); i++)
+ printf("%s %d ", texts[i], scores[i]);
+ puts("");
+ }
+ return ret;
+ }
+
+ TEST_CASE("test") {
+ FuzzyMatcher fuzzy("", 0);
+ CHECK(fuzzy.Match("") == 0);
+ CHECK(fuzzy.Match("aaa") < 0);
+
+ // case
+ CHECK(Ranks("monad", {"monad", "Monad", "mONAD"}));
+ // initials
+ CHECK(Ranks("ab", {"ab", "aoo_boo", "acb"}));
+ CHECK(Ranks("CC", {"CamelCase", "camelCase", "camelcase"}));
+ CHECK(Ranks("cC", {"camelCase", "CamelCase", "camelcase"}));
+ CHECK(Ranks("c c", {"camelCase", "camel case", "CamelCase", "camelcase",
+ "camel ace"}));
+ CHECK(Ranks("Da.Te",
+ {"Data.Text", "Data.Text.Lazy", "Data.Aeson.Encoding.text"}));
+ CHECK(Ranks("foo bar.h", {"foo/bar.h", "foobar.h"}));
+ // prefix
+ CHECK(Ranks("is", {"isIEEE", "inSuf"}));
+ // shorter
+ CHECK(Ranks("ma", {"map", "many", "maximum"}));
+ CHECK(Ranks("print", {"printf", "sprintf"}));
+ // score(PRINT) = kMinScore
+ CHECK(Ranks("ast", {"ast", "AST", "INT_FAST16_MAX"}));
+ // score(PRINT) > kMinScore
+ CHECK(Ranks("Int", {"int", "INT", "PRINT"}));
+ }
+}
+#endif
diff --git a/cpp/fuzzy_match.hpp b/cpp/fuzzy_match.hpp
new file mode 100644
index 0000000..9a02670
--- /dev/null
+++ b/cpp/fuzzy_match.hpp
@@ -0,0 +1,37 @@
+// Copyright 2017-2018 ccls Authors
+// SPDX-License-Identifier: Apache-2.0
+
+#pragma once
+
+#include
+#include
+#include
+
+namespace ivy {
+class FuzzyMatcher {
+ public:
+ constexpr static int kMaxPat = 100;
+ constexpr static int kMaxText = 200;
+ // Negative but far from INT_MIN so that intermediate results are hard to
+ // overflow.
+ constexpr static int kMinScore = INT_MIN / 4;
+
+ // 0: case-insensitive
+ // 1: case-folded, i.e. insensitive if no input character is uppercase.
+ // 2: case-sensitive
+ FuzzyMatcher(std::string_view pattern, int case_sensitivity);
+ int match(std::string_view text, bool strict);
+
+ private:
+ int case_sensitivity;
+ std::string pat;
+ std::string_view text;
+ int pat_set, text_set;
+ char low_pat[kMaxPat], low_text[kMaxText];
+ int pat_role[kMaxPat], text_role[kMaxText];
+ int dp[2][kMaxText + 1][2];
+
+ int matchScore(int i, int j, bool last);
+ int missScore(int j, bool last);
+};
+} // namespace ivy
diff --git a/cpp/lib.cpp b/cpp/lib.cpp
new file mode 100644
index 0000000..aadf00a
--- /dev/null
+++ b/cpp/lib.cpp
@@ -0,0 +1,41 @@
+#include
+#include