summaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/debugger/debugger_marshalls.cpp34
-rw-r--r--core/debugger/debugger_marshalls.h4
-rw-r--r--core/io/missing_resource.cpp4
-rw-r--r--core/io/missing_resource.h2
-rw-r--r--core/io/resource_format_binary.cpp10
-rw-r--r--core/io/resource_importer.h2
-rw-r--r--core/io/resource_loader.cpp21
-rw-r--r--core/object/class_db.cpp104
-rw-r--r--core/os/os.cpp10
-rw-r--r--core/os/spin_lock.h47
-rw-r--r--core/os/thread.h18
-rw-r--r--core/string/fuzzy_search.cpp351
-rw-r--r--core/string/fuzzy_search.h103
-rw-r--r--core/string/ustring.cpp15
-rw-r--r--core/string/ustring.h4
-rw-r--r--core/templates/list.h6
16 files changed, 670 insertions, 65 deletions
diff --git a/core/debugger/debugger_marshalls.cpp b/core/debugger/debugger_marshalls.cpp
index 4bb324db08..0f49167646 100644
--- a/core/debugger/debugger_marshalls.cpp
+++ b/core/debugger/debugger_marshalls.cpp
@@ -149,3 +149,37 @@ bool DebuggerMarshalls::OutputError::deserialize(const Array &p_arr) {
CHECK_END(p_arr, idx, "OutputError");
return true;
}
+
+Array DebuggerMarshalls::serialize_key_shortcut(const Ref<Shortcut> &p_shortcut) {
+ ERR_FAIL_COND_V(p_shortcut.is_null(), Array());
+ Array keys;
+ for (const Ref<InputEvent> ev : p_shortcut->get_events()) {
+ const Ref<InputEventKey> kev = ev;
+ ERR_CONTINUE(kev.is_null());
+ if (kev->get_physical_keycode() != Key::NONE) {
+ keys.push_back(true);
+ keys.push_back(kev->get_physical_keycode_with_modifiers());
+ } else {
+ keys.push_back(false);
+ keys.push_back(kev->get_keycode_with_modifiers());
+ }
+ }
+ return keys;
+}
+
+Ref<Shortcut> DebuggerMarshalls::deserialize_key_shortcut(const Array &p_keys) {
+ Array key_events;
+ ERR_FAIL_COND_V(p_keys.size() % 2 != 0, Ref<Shortcut>());
+ for (int i = 0; i < p_keys.size(); i += 2) {
+ ERR_CONTINUE(p_keys[i].get_type() != Variant::BOOL);
+ ERR_CONTINUE(p_keys[i + 1].get_type() != Variant::INT);
+ key_events.push_back(InputEventKey::create_reference((Key)p_keys[i + 1].operator int(), p_keys[i].operator bool()));
+ }
+ if (key_events.is_empty()) {
+ return Ref<Shortcut>();
+ }
+ Ref<Shortcut> shortcut;
+ shortcut.instantiate();
+ shortcut->set_events(key_events);
+ return shortcut;
+}
diff --git a/core/debugger/debugger_marshalls.h b/core/debugger/debugger_marshalls.h
index abc72bea83..abd1732c3a 100644
--- a/core/debugger/debugger_marshalls.h
+++ b/core/debugger/debugger_marshalls.h
@@ -33,6 +33,7 @@
#ifndef DEBUGGER_MARSHALLS_H
#define DEBUGGER_MARSHALLS_H
+#include "core/input/shortcut.h"
#include "core/object/script_language.h"
struct DebuggerMarshalls {
@@ -70,6 +71,9 @@ struct DebuggerMarshalls {
Array serialize();
bool deserialize(const Array &p_arr);
};
+
+ static Array serialize_key_shortcut(const Ref<Shortcut> &p_shortcut);
+ static Ref<Shortcut> deserialize_key_shortcut(const Array &p_keys);
};
#endif // DEBUGGER_MARSHALLS_H
diff --git a/core/io/missing_resource.cpp b/core/io/missing_resource.cpp
index 4736f790f5..77b50fa27f 100644
--- a/core/io/missing_resource.cpp
+++ b/core/io/missing_resource.cpp
@@ -76,6 +76,10 @@ bool MissingResource::is_recording_properties() const {
return recording_properties;
}
+String MissingResource::get_save_class() const {
+ return original_class;
+}
+
void MissingResource::_bind_methods() {
ClassDB::bind_method(D_METHOD("set_original_class", "name"), &MissingResource::set_original_class);
ClassDB::bind_method(D_METHOD("get_original_class"), &MissingResource::get_original_class);
diff --git a/core/io/missing_resource.h b/core/io/missing_resource.h
index 291a894d96..f838014b4a 100644
--- a/core/io/missing_resource.h
+++ b/core/io/missing_resource.h
@@ -59,6 +59,8 @@ public:
void set_recording_properties(bool p_enable);
bool is_recording_properties() const;
+ virtual String get_save_class() const override;
+
MissingResource();
};
diff --git a/core/io/resource_format_binary.cpp b/core/io/resource_format_binary.cpp
index a714a065b5..fe199653ec 100644
--- a/core/io/resource_format_binary.cpp
+++ b/core/io/resource_format_binary.cpp
@@ -835,7 +835,7 @@ Error ResourceLoaderBinary::load() {
}
bool set_valid = true;
- if (value.get_type() == Variant::OBJECT && missing_resource != nullptr) {
+ if (value.get_type() == Variant::OBJECT && missing_resource == nullptr && ResourceLoader::is_creating_missing_resources_if_class_unavailable_enabled()) {
// If the property being set is a missing resource (and the parent is not),
// then setting it will most likely not work.
// Instead, save it as metadata.
@@ -2227,10 +2227,10 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Ref<Re
List<ResourceData> resources;
- Dictionary missing_resource_properties = p_resource->get_meta(META_MISSING_RESOURCES, Dictionary());
-
{
for (const Ref<Resource> &E : saved_resources) {
+ Dictionary missing_resource_properties = E->get_meta(META_MISSING_RESOURCES, Dictionary());
+
ResourceData &rd = resources.push_back(ResourceData())->get();
rd.type = _resource_get_class(E);
@@ -2245,7 +2245,7 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Ref<Re
continue;
}
- if ((F.usage & PROPERTY_USAGE_STORAGE)) {
+ if ((F.usage & PROPERTY_USAGE_STORAGE) || missing_resource_properties.has(F.name)) {
Property p;
p.name_idx = get_string_index(F.name);
@@ -2260,7 +2260,7 @@ Error ResourceFormatSaverBinaryInstance::save(const String &p_path, const Ref<Re
p.value = E->get(F.name);
}
- if (p.pi.type == Variant::OBJECT && missing_resource_properties.has(F.name)) {
+ if (F.type == Variant::OBJECT && missing_resource_properties.has(F.name)) {
// Was this missing resource overridden? If so do not save the old value.
Ref<Resource> res = p.value;
if (res.is_null()) {
diff --git a/core/io/resource_importer.h b/core/io/resource_importer.h
index eae1c40216..3127097d8f 100644
--- a/core/io/resource_importer.h
+++ b/core/io/resource_importer.h
@@ -150,7 +150,7 @@ public:
virtual String get_option_group_file() const { return String(); }
virtual Error import(const String &p_source_file, const String &p_save_path, const HashMap<StringName, Variant> &p_options, List<String> *r_platform_variants, List<String> *r_gen_files = nullptr, Variant *r_metadata = nullptr) = 0;
- virtual bool can_import_threaded() const { return true; }
+ virtual bool can_import_threaded() const { return false; }
virtual void import_threaded_begin() {}
virtual void import_threaded_end() {}
diff --git a/core/io/resource_loader.cpp b/core/io/resource_loader.cpp
index 97e6f6da06..08b6b6e982 100644
--- a/core/io/resource_loader.cpp
+++ b/core/io/resource_loader.cpp
@@ -284,13 +284,13 @@ Ref<Resource> ResourceLoader::_load(const String &p_path, const String &p_origin
load_paths_stack.push_back(original_path);
// Try all loaders and pick the first match for the type hint
- bool found = false;
+ bool loader_found = false;
Ref<Resource> res;
for (int i = 0; i < loader_count; i++) {
if (!loader[i]->recognize_path(p_path, p_type_hint)) {
continue;
}
- found = true;
+ loader_found = true;
res = loader[i]->load(p_path, original_path, r_error, p_use_sub_threads, r_progress, p_cache_mode);
if (!res.is_null()) {
break;
@@ -305,15 +305,24 @@ Ref<Resource> ResourceLoader::_load(const String &p_path, const String &p_origin
return res;
}
- ERR_FAIL_COND_V_MSG(found, Ref<Resource>(),
- vformat("Failed loading resource: %s. Make sure resources have been imported by opening the project in the editor at least once.", p_path));
+ if (!loader_found) {
+ if (r_error) {
+ *r_error = ERR_FILE_UNRECOGNIZED;
+ }
+ ERR_FAIL_V_MSG(Ref<Resource>(), vformat("No loader found for resource: %s (expected type: %s)", p_path, p_type_hint));
+ }
#ifdef TOOLS_ENABLED
Ref<FileAccess> file_check = FileAccess::create(FileAccess::ACCESS_RESOURCES);
- ERR_FAIL_COND_V_MSG(!file_check->file_exists(p_path), Ref<Resource>(), vformat("Resource file not found: %s (expected type: %s)", p_path, p_type_hint));
+ if (!file_check->file_exists(p_path)) {
+ if (r_error) {
+ *r_error = ERR_FILE_NOT_FOUND;
+ }
+ ERR_FAIL_V_MSG(Ref<Resource>(), vformat("Resource file not found: %s (expected type: %s)", p_path, p_type_hint));
+ }
#endif
- ERR_FAIL_V_MSG(Ref<Resource>(), vformat("No loader found for resource: %s (expected type: %s)", p_path, p_type_hint));
+ ERR_FAIL_V_MSG(Ref<Resource>(), vformat("Failed loading resource: %s. Make sure resources have been imported by opening the project in the editor at least once.", p_path));
}
// This implementation must allow re-entrancy for a task that started awaiting in a deeper stack frame.
diff --git a/core/object/class_db.cpp b/core/object/class_db.cpp
index 3ec1f6e7b4..b85525cb7d 100644
--- a/core/object/class_db.cpp
+++ b/core/object/class_db.cpp
@@ -752,69 +752,87 @@ void ClassDB::set_object_extension_instance(Object *p_object, const StringName &
}
bool ClassDB::can_instantiate(const StringName &p_class) {
- OBJTYPE_RLOCK;
+ String script_path;
+ {
+ OBJTYPE_RLOCK;
- ClassInfo *ti = classes.getptr(p_class);
- if (!ti) {
- if (!ScriptServer::is_global_class(p_class)) {
- ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ ClassInfo *ti = classes.getptr(p_class);
+ if (!ti) {
+ if (!ScriptServer::is_global_class(p_class)) {
+ ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ }
+ script_path = ScriptServer::get_global_class_path(p_class);
+ goto use_script; // Open the lock for resource loading.
}
- String path = ScriptServer::get_global_class_path(p_class);
- Ref<Script> scr = ResourceLoader::load(path);
- return scr.is_valid() && scr->is_valid() && !scr->is_abstract();
- }
#ifdef TOOLS_ENABLED
- if ((ti->api == API_EDITOR || ti->api == API_EDITOR_EXTENSION) && !Engine::get_singleton()->is_editor_hint()) {
- return false;
- }
+ if ((ti->api == API_EDITOR || ti->api == API_EDITOR_EXTENSION) && !Engine::get_singleton()->is_editor_hint()) {
+ return false;
+ }
#endif
- return _can_instantiate(ti);
+ return _can_instantiate(ti);
+ }
+
+use_script:
+ Ref<Script> scr = ResourceLoader::load(script_path);
+ return scr.is_valid() && scr->is_valid() && !scr->is_abstract();
}
bool ClassDB::is_abstract(const StringName &p_class) {
- OBJTYPE_RLOCK;
+ String script_path;
+ {
+ OBJTYPE_RLOCK;
- ClassInfo *ti = classes.getptr(p_class);
- if (!ti) {
- if (!ScriptServer::is_global_class(p_class)) {
- ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ ClassInfo *ti = classes.getptr(p_class);
+ if (!ti) {
+ if (!ScriptServer::is_global_class(p_class)) {
+ ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ }
+ script_path = ScriptServer::get_global_class_path(p_class);
+ goto use_script; // Open the lock for resource loading.
}
- String path = ScriptServer::get_global_class_path(p_class);
- Ref<Script> scr = ResourceLoader::load(path);
- return scr.is_valid() && scr->is_valid() && scr->is_abstract();
- }
- if (ti->creation_func != nullptr) {
- return false;
- }
- if (!ti->gdextension) {
- return true;
- }
+ if (ti->creation_func != nullptr) {
+ return false;
+ }
+ if (!ti->gdextension) {
+ return true;
+ }
#ifndef DISABLE_DEPRECATED
- return ti->gdextension->create_instance2 == nullptr && ti->gdextension->create_instance == nullptr;
+ return ti->gdextension->create_instance2 == nullptr && ti->gdextension->create_instance == nullptr;
#else
- return ti->gdextension->create_instance2 == nullptr;
+ return ti->gdextension->create_instance2 == nullptr;
#endif // DISABLE_DEPRECATED
+ }
+
+use_script:
+ Ref<Script> scr = ResourceLoader::load(script_path);
+ return scr.is_valid() && scr->is_valid() && scr->is_abstract();
}
bool ClassDB::is_virtual(const StringName &p_class) {
- OBJTYPE_RLOCK;
+ String script_path;
+ {
+ OBJTYPE_RLOCK;
- ClassInfo *ti = classes.getptr(p_class);
- if (!ti) {
- if (!ScriptServer::is_global_class(p_class)) {
- ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ ClassInfo *ti = classes.getptr(p_class);
+ if (!ti) {
+ if (!ScriptServer::is_global_class(p_class)) {
+ ERR_FAIL_V_MSG(false, vformat("Cannot get class '%s'.", String(p_class)));
+ }
+ script_path = ScriptServer::get_global_class_path(p_class);
+ goto use_script; // Open the lock for resource loading.
}
- String path = ScriptServer::get_global_class_path(p_class);
- Ref<Script> scr = ResourceLoader::load(path);
- return scr.is_valid() && scr->is_valid() && scr->is_abstract();
- }
#ifdef TOOLS_ENABLED
- if ((ti->api == API_EDITOR || ti->api == API_EDITOR_EXTENSION) && !Engine::get_singleton()->is_editor_hint()) {
- return false;
- }
+ if ((ti->api == API_EDITOR || ti->api == API_EDITOR_EXTENSION) && !Engine::get_singleton()->is_editor_hint()) {
+ return false;
+ }
#endif
- return (_can_instantiate(ti) && ti->is_virtual);
+ return (_can_instantiate(ti) && ti->is_virtual);
+ }
+
+use_script:
+ Ref<Script> scr = ResourceLoader::load(script_path);
+ return scr.is_valid() && scr->is_valid() && scr->is_abstract();
}
void ClassDB::_add_class2(const StringName &p_class, const StringName &p_inherits) {
diff --git a/core/os/os.cpp b/core/os/os.cpp
index b41ea0a87f..4b599c70ee 100644
--- a/core/os/os.cpp
+++ b/core/os/os.cpp
@@ -441,6 +441,11 @@ bool OS::has_feature(const String &p_feature) {
}
#if defined(__x86_64) || defined(__x86_64__) || defined(__amd64__) || defined(__i386) || defined(__i386__) || defined(_M_IX86) || defined(_M_X64)
#if defined(__x86_64) || defined(__x86_64__) || defined(__amd64__) || defined(_M_X64)
+#if defined(MACOS_ENABLED)
+ if (p_feature == "universal") {
+ return true;
+ }
+#endif
if (p_feature == "x86_64") {
return true;
}
@@ -454,6 +459,11 @@ bool OS::has_feature(const String &p_feature) {
}
#elif defined(__arm__) || defined(__aarch64__) || defined(_M_ARM) || defined(_M_ARM64)
#if defined(__aarch64__) || defined(_M_ARM64)
+#if defined(MACOS_ENABLED)
+ if (p_feature == "universal") {
+ return true;
+ }
+#endif
if (p_feature == "arm64") {
return true;
}
diff --git a/core/os/spin_lock.h b/core/os/spin_lock.h
index d6de00f043..ddf5c2e87a 100644
--- a/core/os/spin_lock.h
+++ b/core/os/spin_lock.h
@@ -35,6 +35,10 @@
#include "core/typedefs.h"
+#ifdef _MSC_VER
+#include <intrin.h>
+#endif
+
#if defined(__APPLE__)
#include <os/lock.h>
@@ -54,19 +58,52 @@ public:
#else
+#include "core/os/thread.h"
+
#include <atomic>
-class SpinLock {
- mutable std::atomic_flag locked = ATOMIC_FLAG_INIT;
+_ALWAYS_INLINE_ static void _cpu_pause() {
+#if defined(_MSC_VER)
+// ----- MSVC.
+#if defined(_M_ARM) || defined(_M_ARM64) // ARM.
+ __yield();
+#elif defined(_M_IX86) || defined(_M_X64) // x86.
+ _mm_pause();
+#endif
+#elif defined(__GNUC__) || defined(__clang__)
+// ----- GCC/Clang.
+#if defined(__i386__) || defined(__x86_64__) // x86.
+ __builtin_ia32_pause();
+#elif defined(__arm__) || defined(__aarch64__) // ARM.
+ asm volatile("yield");
+#elif defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) // PowerPC.
+ asm volatile("or 27,27,27");
+#elif defined(__riscv) // RISC-V.
+ asm volatile(".insn i 0x0F, 0, x0, x0, 0x010");
+#endif
+#endif
+}
+
+static_assert(std::atomic_bool::is_always_lock_free);
+
+class alignas(Thread::CACHE_LINE_BYTES) SpinLock {
+ mutable std::atomic<bool> locked = ATOMIC_VAR_INIT(false);
public:
_ALWAYS_INLINE_ void lock() const {
- while (locked.test_and_set(std::memory_order_acquire)) {
- // Continue.
+ while (true) {
+ bool expected = false;
+ if (locked.compare_exchange_weak(expected, true, std::memory_order_acquire, std::memory_order_relaxed)) {
+ break;
+ }
+ do {
+ _cpu_pause();
+ } while (locked.load(std::memory_order_relaxed));
}
}
+
_ALWAYS_INLINE_ void unlock() const {
- locked.clear(std::memory_order_release);
+ locked.store(false, std::memory_order_release);
}
};
diff --git a/core/os/thread.h b/core/os/thread.h
index e2e9065ec3..0da9a37a6b 100644
--- a/core/os/thread.h
+++ b/core/os/thread.h
@@ -44,6 +44,8 @@
#include "core/templates/safe_refcount.h"
#include "core/typedefs.h"
+#include <new>
+
#ifdef MINGW_ENABLED
#define MINGW_STDTHREAD_REDUNDANCY_WARNING
#include "thirdparty/mingw-std-threads/mingw.thread.h"
@@ -87,6 +89,20 @@ public:
void (*term)() = nullptr;
};
+#if defined(__cpp_lib_hardware_interference_size) && !defined(ANDROID_ENABLED) // This would be OK with NDK >= 26.
+#if defined(__GNUC__) && !defined(__clang__)
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Winterference-size"
+#endif
+ static constexpr size_t CACHE_LINE_BYTES = std::hardware_destructive_interference_size;
+#if defined(__GNUC__) && !defined(__clang__)
+#pragma GCC diagnostic pop
+#endif
+#else
+ // At a negligible memory cost, we use a conservatively high value.
+ static constexpr size_t CACHE_LINE_BYTES = 128;
+#endif
+
private:
friend class Main;
@@ -137,6 +153,8 @@ public:
typedef uint64_t ID;
+ static constexpr size_t CACHE_LINE_BYTES = sizeof(void *);
+
enum : ID {
UNASSIGNED_ID = 0,
MAIN_ID = 1
diff --git a/core/string/fuzzy_search.cpp b/core/string/fuzzy_search.cpp
new file mode 100644
index 0000000000..57b82ac829
--- /dev/null
+++ b/core/string/fuzzy_search.cpp
@@ -0,0 +1,351 @@
+/**************************************************************************/
+/* fuzzy_search.cpp */
+/**************************************************************************/
+/* This file is part of: */
+/* REDOT ENGINE */
+/* https://redotengine.org */
+/**************************************************************************/
+/* Copyright (c) 2024-present Redot Engine contributors */
+/* (see REDOT_AUTHORS.md) */
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/**************************************************************************/
+
+#include "fuzzy_search.h"
+
+constexpr float cull_factor = 0.1f;
+constexpr float cull_cutoff = 30.0f;
+const String boundary_chars = "/\\-_.";
+
+static bool _is_valid_interval(const Vector2i &p_interval) {
+ // Empty intervals are represented as (-1, -1).
+ return p_interval.x >= 0 && p_interval.y >= p_interval.x;
+}
+
+static Vector2i _extend_interval(const Vector2i &p_a, const Vector2i &p_b) {
+ if (!_is_valid_interval(p_a)) {
+ return p_b;
+ }
+ if (!_is_valid_interval(p_b)) {
+ return p_a;
+ }
+ return Vector2i(MIN(p_a.x, p_b.x), MAX(p_a.y, p_b.y));
+}
+
+static bool _is_word_boundary(const String &p_str, int p_index) {
+ if (p_index == -1 || p_index == p_str.size()) {
+ return true;
+ }
+ return boundary_chars.find_char(p_str[p_index]) != -1;
+}
+
+bool FuzzySearchToken::try_exact_match(FuzzyTokenMatch &p_match, const String &p_target, int p_offset) const {
+ p_match.token_idx = idx;
+ p_match.token_length = string.length();
+ int match_idx = p_target.find(string, p_offset);
+ if (match_idx == -1) {
+ return false;
+ }
+ p_match.add_substring(match_idx, string.length());
+ return true;
+}
+
+bool FuzzySearchToken::try_fuzzy_match(FuzzyTokenMatch &p_match, const String &p_target, int p_offset, int p_miss_budget) const {
+ p_match.token_idx = idx;
+ p_match.token_length = string.length();
+ int run_start = -1;
+ int run_len = 0;
+
+ // Search for the subsequence p_token in p_target starting from p_offset, recording each substring for
+ // later scoring and display.
+ for (int i = 0; i < string.length(); i++) {
+ int new_offset = p_target.find_char(string[i], p_offset);
+ if (new_offset < 0) {
+ p_miss_budget--;
+ if (p_miss_budget < 0) {
+ return false;
+ }
+ } else {
+ if (run_start == -1 || p_offset != new_offset) {
+ if (run_start != -1) {
+ p_match.add_substring(run_start, run_len);
+ }
+ run_start = new_offset;
+ run_len = 1;
+ } else {
+ run_len += 1;
+ }
+ p_offset = new_offset + 1;
+ }
+ }
+
+ if (run_start != -1) {
+ p_match.add_substring(run_start, run_len);
+ }
+
+ return true;
+}
+
+void FuzzyTokenMatch::add_substring(int p_substring_start, int p_substring_length) {
+ substrings.append(Vector2i(p_substring_start, p_substring_length));
+ matched_length += p_substring_length;
+ Vector2i substring_interval = { p_substring_start, p_substring_start + p_substring_length - 1 };
+ interval = _extend_interval(interval, substring_interval);
+}
+
+bool FuzzyTokenMatch::intersects(const Vector2i &p_other_interval) const {
+ if (!_is_valid_interval(interval) || !_is_valid_interval(p_other_interval)) {
+ return false;
+ }
+ return interval.y >= p_other_interval.x && interval.x <= p_other_interval.y;
+}
+
+bool FuzzySearchResult::can_add_token_match(const FuzzyTokenMatch &p_match) const {
+ if (p_match.get_miss_count() > miss_budget) {
+ return false;
+ }
+
+ if (p_match.intersects(match_interval)) {
+ if (token_matches.size() == 1) {
+ return false;
+ }
+ for (const FuzzyTokenMatch &existing_match : token_matches) {
+ if (existing_match.intersects(p_match.interval)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+bool FuzzyTokenMatch::is_case_insensitive(const String &p_original, const String &p_adjusted) const {
+ for (const Vector2i &substr : substrings) {
+ const int end = substr.x + substr.y;
+ for (int i = substr.x; i < end; i++) {
+ if (p_original[i] != p_adjusted[i]) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+void FuzzySearchResult::score_token_match(FuzzyTokenMatch &p_match, bool p_case_insensitive) const {
+ // This can always be tweaked more. The intuition is that exact matches should almost always
+ // be prioritized over broken up matches, and other criteria more or less act as tie breakers.
+
+ p_match.score = -20 * p_match.get_miss_count() - (p_case_insensitive ? 3 : 0);
+
+ for (const Vector2i &substring : p_match.substrings) {
+ // Score longer substrings higher than short substrings.
+ int substring_score = substring.y * substring.y;
+ // Score matches deeper in path higher than shallower matches
+ if (substring.x > dir_index) {
+ substring_score *= 2;
+ }
+ // Score matches on a word boundary higher than matches within a word
+ if (_is_word_boundary(target, substring.x - 1) || _is_word_boundary(target, substring.x + substring.y)) {
+ substring_score += 4;
+ }
+ // Score exact query matches higher than non-compact subsequence matches
+ if (substring.y == p_match.token_length) {
+ substring_score += 100;
+ }
+ p_match.score += substring_score;
+ }
+}
+
+void FuzzySearchResult::maybe_apply_score_bonus() {
+ // This adds a small bonus to results which match tokens in the same order they appear in the query.
+ int *token_range_starts = (int *)alloca(sizeof(int) * token_matches.size());
+
+ for (const FuzzyTokenMatch &match : token_matches) {
+ token_range_starts[match.token_idx] = match.interval.x;
+ }
+
+ int last = token_range_starts[0];
+ for (int i = 1; i < token_matches.size(); i++) {
+ if (last > token_range_starts[i]) {
+ return;
+ }
+ last = token_range_starts[i];
+ }
+
+ score += 1;
+}
+
+void FuzzySearchResult::add_token_match(const FuzzyTokenMatch &p_match) {
+ score += p_match.score;
+ match_interval = _extend_interval(match_interval, p_match.interval);
+ miss_budget -= p_match.get_miss_count();
+ token_matches.append(p_match);
+}
+
+void remove_low_scores(Vector<FuzzySearchResult> &p_results, float p_cull_score) {
+ // Removes all results with score < p_cull_score in-place.
+ int i = 0;
+ int j = p_results.size() - 1;
+ FuzzySearchResult *results = p_results.ptrw();
+
+ while (true) {
+ // Advances i to an element to remove and j to an element to keep.
+ while (j >= i && results[j].score < p_cull_score) {
+ j--;
+ }
+ while (i < j && results[i].score >= p_cull_score) {
+ i++;
+ }
+ if (i >= j) {
+ break;
+ }
+ results[i++] = results[j--];
+ }
+
+ p_results.resize(j + 1);
+}
+
+void FuzzySearch::sort_and_filter(Vector<FuzzySearchResult> &p_results) const {
+ if (p_results.is_empty()) {
+ return;
+ }
+
+ float avg_score = 0;
+ float max_score = 0;
+
+ for (const FuzzySearchResult &result : p_results) {
+ avg_score += result.score;
+ max_score = MAX(max_score, result.score);
+ }
+
+ // TODO: Tune scoring and culling here to display fewer subsequence soup matches when good matches
+ // are available.
+ avg_score /= p_results.size();
+ float cull_score = MIN(cull_cutoff, Math::lerp(avg_score, max_score, cull_factor));
+ remove_low_scores(p_results, cull_score);
+
+ struct FuzzySearchResultComparator {
+ bool operator()(const FuzzySearchResult &p_lhs, const FuzzySearchResult &p_rhs) const {
+ // Sort on (score, length, alphanumeric) to ensure consistent ordering.
+ if (p_lhs.score == p_rhs.score) {
+ if (p_lhs.target.length() == p_rhs.target.length()) {
+ return p_lhs.target < p_rhs.target;
+ }
+ return p_lhs.target.length() < p_rhs.target.length();
+ }
+ return p_lhs.score > p_rhs.score;
+ }
+ };
+
+ SortArray<FuzzySearchResult, FuzzySearchResultComparator> sorter;
+
+ if (p_results.size() > max_results) {
+ sorter.partial_sort(0, p_results.size(), max_results, p_results.ptrw());
+ p_results.resize(max_results);
+ } else {
+ sorter.sort(p_results.ptrw(), p_results.size());
+ }
+}
+
+void FuzzySearch::set_query(const String &p_query) {
+ tokens.clear();
+ for (const String &string : p_query.split(" ", false)) {
+ tokens.append({ static_cast<int>(tokens.size()), string });
+ }
+
+ case_sensitive = !p_query.is_lowercase();
+
+ struct TokenComparator {
+ bool operator()(const FuzzySearchToken &A, const FuzzySearchToken &B) const {
+ if (A.string.length() == B.string.length()) {
+ return A.idx < B.idx;
+ }
+ return A.string.length() > B.string.length();
+ }
+ };
+
+ // Prioritize matching longer tokens before shorter ones since match overlaps are not accepted.
+ tokens.sort_custom<TokenComparator>();
+}
+
+bool FuzzySearch::search(const String &p_target, FuzzySearchResult &p_result) const {
+ p_result.target = p_target;
+ p_result.dir_index = p_target.rfind_char('/');
+ p_result.miss_budget = max_misses;
+
+ String adjusted_target = case_sensitive ? p_target : p_target.to_lower();
+
+ // For each token, eagerly generate subsequences starting from index 0 and keep the best scoring one
+ // which does not conflict with prior token matches. This is not ensured to find the highest scoring
+ // combination of matches, or necessarily the highest scoring single subsequence, as it only considers
+ // eager subsequences for a given index, and likewise eagerly finds matches for each token in sequence.
+ for (const FuzzySearchToken &token : tokens) {
+ FuzzyTokenMatch best_match;
+ int offset = start_offset;
+
+ while (true) {
+ FuzzyTokenMatch match;
+ if (allow_subsequences) {
+ if (!token.try_fuzzy_match(match, adjusted_target, offset, p_result.miss_budget)) {
+ break;
+ }
+ } else {
+ if (!token.try_exact_match(match, adjusted_target, offset)) {
+ break;
+ }
+ }
+ if (p_result.can_add_token_match(match)) {
+ p_result.score_token_match(match, match.is_case_insensitive(p_target, adjusted_target));
+ if (best_match.token_idx == -1 || best_match.score < match.score) {
+ best_match = match;
+ }
+ }
+ if (_is_valid_interval(match.interval)) {
+ offset = match.interval.x + 1;
+ } else {
+ break;
+ }
+ }
+
+ if (best_match.token_idx == -1) {
+ return false;
+ }
+
+ p_result.add_token_match(best_match);
+ }
+
+ p_result.maybe_apply_score_bonus();
+ return true;
+}
+
+void FuzzySearch::search_all(const PackedStringArray &p_targets, Vector<FuzzySearchResult> &p_results) const {
+ p_results.clear();
+
+ for (const String &target : p_targets) {
+ FuzzySearchResult result;
+ if (search(target, result)) {
+ p_results.append(result);
+ }
+ }
+
+ sort_and_filter(p_results);
+}
diff --git a/core/string/fuzzy_search.h b/core/string/fuzzy_search.h
new file mode 100644
index 0000000000..4e2564421c
--- /dev/null
+++ b/core/string/fuzzy_search.h
@@ -0,0 +1,103 @@
+/**************************************************************************/
+/* fuzzy_search.h */
+/**************************************************************************/
+/* This file is part of: */
+/* REDOT ENGINE */
+/* https://redotengine.org */
+/**************************************************************************/
+/* Copyright (c) 2024-present Redot Engine contributors */
+/* (see REDOT_AUTHORS.md) */
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/**************************************************************************/
+
+#ifndef FUZZY_SEARCH_H
+#define FUZZY_SEARCH_H
+
+#include "core/variant/variant.h"
+
+class FuzzyTokenMatch;
+
+struct FuzzySearchToken {
+ int idx = -1;
+ String string;
+
+ bool try_exact_match(FuzzyTokenMatch &p_match, const String &p_target, int p_offset) const;
+ bool try_fuzzy_match(FuzzyTokenMatch &p_match, const String &p_target, int p_offset, int p_miss_budget) const;
+};
+
+class FuzzyTokenMatch {
+ friend struct FuzzySearchToken;
+ friend class FuzzySearchResult;
+ friend class FuzzySearch;
+
+ int matched_length = 0;
+ int token_length = 0;
+ int token_idx = -1;
+ Vector2i interval = Vector2i(-1, -1); // x and y are both inclusive indices.
+
+ void add_substring(int p_substring_start, int p_substring_length);
+ bool intersects(const Vector2i &p_other_interval) const;
+ bool is_case_insensitive(const String &p_original, const String &p_adjusted) const;
+ int get_miss_count() const { return token_length - matched_length; }
+
+public:
+ int score = 0;
+ Vector<Vector2i> substrings; // x is start index, y is length.
+};
+
+class FuzzySearchResult {
+ friend class FuzzySearch;
+
+ int miss_budget = 0;
+ Vector2i match_interval = Vector2i(-1, -1);
+
+ bool can_add_token_match(const FuzzyTokenMatch &p_match) const;
+ void score_token_match(FuzzyTokenMatch &p_match, bool p_case_insensitive) const;
+ void add_token_match(const FuzzyTokenMatch &p_match);
+ void maybe_apply_score_bonus();
+
+public:
+ String target;
+ int score = 0;
+ int dir_index = -1;
+ Vector<FuzzyTokenMatch> token_matches;
+};
+
+class FuzzySearch {
+ Vector<FuzzySearchToken> tokens;
+
+ void sort_and_filter(Vector<FuzzySearchResult> &p_results) const;
+
+public:
+ int start_offset = 0;
+ bool case_sensitive = false;
+ int max_results = 100;
+ int max_misses = 2;
+ bool allow_subsequences = true;
+
+ void set_query(const String &p_query);
+ bool search(const String &p_target, FuzzySearchResult &p_result) const;
+ void search_all(const PackedStringArray &p_targets, Vector<FuzzySearchResult> &p_results) const;
+};
+
+#endif // FUZZY_SEARCH_H
diff --git a/core/string/ustring.cpp b/core/string/ustring.cpp
index 9bfc0a67cb..033b5f2864 100644
--- a/core/string/ustring.cpp
+++ b/core/string/ustring.cpp
@@ -3389,7 +3389,7 @@ int String::find(const char *p_str, int p_from) const {
return -1;
}
-int String::find_char(const char32_t &p_char, int p_from) const {
+int String::find_char(char32_t p_char, int p_from) const {
return _cowdata.find(p_char, p_from);
}
@@ -3626,6 +3626,10 @@ int String::rfind(const char *p_str, int p_from) const {
return -1;
}
+int String::rfind_char(char32_t p_char, int p_from) const {
+ return _cowdata.rfind(p_char, p_from);
+}
+
int String::rfindn(const String &p_str, int p_from) const {
// establish a limit
int limit = length() - p_str.length();
@@ -3839,6 +3843,15 @@ bool String::is_quoted() const {
return is_enclosed_in("\"") || is_enclosed_in("'");
}
+bool String::is_lowercase() const {
+ for (const char32_t *str = &operator[](0); *str; str++) {
+ if (is_unicode_upper_case(*str)) {
+ return false;
+ }
+ }
+ return true;
+}
+
int String::_count(const String &p_string, int p_from, int p_to, bool p_case_insensitive) const {
if (p_string.is_empty()) {
return 0;
diff --git a/core/string/ustring.h b/core/string/ustring.h
index 11be148084..d363228ecb 100644
--- a/core/string/ustring.h
+++ b/core/string/ustring.h
@@ -289,11 +289,12 @@ public:
String substr(int p_from, int p_chars = -1) const;
int find(const String &p_str, int p_from = 0) const; ///< return <0 if failed
int find(const char *p_str, int p_from = 0) const; ///< return <0 if failed
- int find_char(const char32_t &p_char, int p_from = 0) const; ///< return <0 if failed
+ int find_char(char32_t p_char, int p_from = 0) const; ///< return <0 if failed
int findn(const String &p_str, int p_from = 0) const; ///< return <0 if failed, case insensitive
int findn(const char *p_str, int p_from = 0) const; ///< return <0 if failed
int rfind(const String &p_str, int p_from = -1) const; ///< return <0 if failed
int rfind(const char *p_str, int p_from = -1) const; ///< return <0 if failed
+ int rfind_char(char32_t p_char, int p_from = -1) const; ///< return <0 if failed
int rfindn(const String &p_str, int p_from = -1) const; ///< return <0 if failed, case insensitive
int rfindn(const char *p_str, int p_from = -1) const; ///< return <0 if failed
int findmk(const Vector<String> &p_keys, int p_from = 0, int *r_key = nullptr) const; ///< return <0 if failed
@@ -307,6 +308,7 @@ public:
bool is_subsequence_of(const String &p_string) const;
bool is_subsequence_ofn(const String &p_string) const;
bool is_quoted() const;
+ bool is_lowercase() const;
Vector<String> bigrams() const;
float similarity(const String &p_string) const;
String format(const Variant &values, const String &placeholder = "{_}") const;
diff --git a/core/templates/list.h b/core/templates/list.h
index 30c572e1df..619e631cfb 100644
--- a/core/templates/list.h
+++ b/core/templates/list.h
@@ -226,7 +226,7 @@ private:
Element *last = nullptr;
int size_cache = 0;
- bool erase(const Element *p_I) {
+ bool erase(Element *p_I) {
ERR_FAIL_NULL_V(p_I, false);
ERR_FAIL_COND_V(p_I->data != this, false);
@@ -246,7 +246,7 @@ private:
p_I->next_ptr->prev_ptr = p_I->prev_ptr;
}
- memdelete_allocator<Element, A>(const_cast<Element *>(p_I));
+ memdelete_allocator<Element, A>(p_I);
size_cache--;
return true;
@@ -432,7 +432,7 @@ public:
/**
* erase an element in the list, by iterator pointing to it. Return true if it was found/erased.
*/
- bool erase(const Element *p_I) {
+ bool erase(Element *p_I) {
if (_data && p_I) {
bool ret = _data->erase(p_I);