6 files changed, 104 insertions, 19 deletions
diff --git a/source/blender/blenlib/BLI_generic_virtual_array.hh b/source/blender/blenlib/BLI_generic_virtual_array.hh
index 3fce2947d0d..985d914f4a4 100644
--- a/source/blender/blenlib/BLI_generic_virtual_array.hh
+++ b/source/blender/blenlib/BLI_generic_virtual_array.hh
@@ -934,15 +934,15 @@ template<typename T> inline GVArray::GVArray(const VArray<T> &varray)
   if (varray.try_assign_GVArray(*this)) {
     return;
   }
-  /* Need to check this before the span/single special cases, because otherwise we might loose
-   * ownership to the referenced data when #varray goes out of scope. */
-  if (varray.may_have_ownership()) {
-    *this = GVArray::For<GVArrayImpl_For_VArray<T>>(varray);
-  }
-  else if (varray.is_single()) {
+  if (varray.is_single()) {
     T value = varray.get_internal_single();
     *this = GVArray::ForSingle(CPPType::get<T>(), varray.size(), &value);
   }
+  /* Need to check this before the span special case, because otherwise we might loose
+   * ownership to the referenced data when #varray goes out of scope. */
+  else if (varray.may_have_ownership()) {
+    *this = GVArray::For<GVArrayImpl_For_VArray<T>>(varray);
+  }
   else if (varray.is_span()) {
     Span<T> data = varray.get_internal_span();
     *this = GVArray::ForSpan(data);
@@ -962,14 +962,14 @@ template<typename T> inline VArray<T> GVArray::typed() const
   if (this->try_assign_VArray(varray)) {
     return varray;
   }
-  if (this->may_have_ownership()) {
-    return VArray<T>::template For<VArrayImpl_For_GVArray<T>>(*this);
-  }
   if (this->is_single()) {
     T value;
     this->get_internal_single(&value);
     return VArray<T>::ForSingle(value, this->size());
   }
+  if (this->may_have_ownership()) {
+    return VArray<T>::template For<VArrayImpl_For_GVArray<T>>(*this);
+  }
   if (this->is_span()) {
     const Span<T> span = this->get_internal_span().typed<T>();
     return VArray<T>::ForSpan(span);
diff --git a/source/blender/blenlib/BLI_math_base.hh b/source/blender/blenlib/BLI_math_base.hh
index 3057e30dc03..b15179f75b6 100644
--- a/source/blender/blenlib/BLI_math_base.hh
+++ b/source/blender/blenlib/BLI_math_base.hh
@@ -44,6 +44,16 @@ template<typename T> inline T max(const T &a, const T &b)
   return std::max(a, b);
 }
 
+template<typename T> inline void max_inplace(T &a, const T &b)
+{
+  a = math::max(a, b);
+}
+
+template<typename T> inline void min_inplace(T &a, const T &b)
+{
+  a = math::min(a, b);
+}
+
 template<typename T> inline T clamp(const T &a, const T &min, const T &max)
 {
   return std::clamp(a, min, max);
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 109230ebfa7..95b4987596e 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -445,6 +445,7 @@ if(WITH_GTESTS)
     tests/BLI_index_range_test.cc
     tests/BLI_inplace_priority_queue_test.cc
     tests/BLI_kdopbvh_test.cc
+    tests/BLI_kdtree_test.cc
     tests/BLI_length_parameterize_test.cc
     tests/BLI_linear_allocator_test.cc
     tests/BLI_linklist_lockfree_test.cc
diff --git a/source/blender/blenlib/intern/kdtree_impl.h b/source/blender/blenlib/intern/kdtree_impl.h
index d9ae826093c..6614f1bf964 100644
--- a/source/blender/blenlib/intern/kdtree_impl.h
+++ b/source/blender/blenlib/intern/kdtree_impl.h
@@ -927,6 +927,14 @@ int BLI_kdtree_nd_(calc_duplicates_fast)(const KDTree *tree,
 /** \name BLI_kdtree_3d_deduplicate
  * \{ */
 
+static int kdtree_cmp_bool(const bool a, const bool b)
+{
+  if (a == b) {
+    return 0;
+  }
+  return b ? -1 : 1;
+}
+
 static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
 {
   const KDTreeNode *n0 = n0_p;
@@ -939,17 +947,16 @@ static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
       return 1;
     }
   }
-  /* Sort by pointer so the first added will be used.
-   * assignment below ignores const correctness,
-   * however the values aren't used for sorting and are to be discarded. */
-  if (n0 < n1) {
-    ((KDTreeNode *)n1)->d = KD_DIMS; /* tag invalid */
-    return -1;
-  }
-  else {
-    ((KDTreeNode *)n0)->d = KD_DIMS; /* tag invalid */
-    return 1;
+
+  if (n0->d != KD_DIMS && n1->d != KD_DIMS) {
+    /* Two nodes share identical `co`
+     * Both are still valid.
+     * Cast away `const` and tag one of them as invalid. */
+    ((KDTreeNode *)n1)->d = KD_DIMS;
   }
+
+  /* Keep sorting until each unique value has one and only one valid node. */
+  return kdtree_cmp_bool(n0->d == KD_DIMS, n1->d == KD_DIMS);
 }
 
 /**
diff --git a/source/blender/blenlib/intern/string_utf8.c b/source/blender/blenlib/intern/string_utf8.c
index 94efb0dd9e7..0cbf62cce03 100644
--- a/source/blender/blenlib/intern/string_utf8.c
+++ b/source/blender/blenlib/intern/string_utf8.c
@@ -363,6 +363,10 @@ size_t BLI_strncpy_wchar_from_utf8(wchar_t *__restrict dst_w,
 
 int BLI_wcwidth(char32_t ucs)
 {
+  /* Treat private use areas (icon fonts), symbols, and emoticons as double-width. */
+  if (ucs >= 0xf0000 || (ucs >= 0xe000 && ucs < 0xf8ff) || (ucs >= 0x1f300 && ucs < 0x1fbff)) {
+    return 2;
+  }
   return mk_wcwidth(ucs);
 }
 
diff --git a/source/blender/blenlib/tests/BLI_kdtree_test.cc b/source/blender/blenlib/tests/BLI_kdtree_test.cc
new file mode 100644
index 00000000000..f8675ef332d
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_kdtree_test.cc
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: Apache-2.0 */
+
+#include "testing/testing.h"
+
+#include "BLI_kdtree.h"
+
+#include <math.h>
+
+/* -------------------------------------------------------------------- */
+/* Tests */
+
+static void standard_test()
+{
+  for (int tree_size = 30; tree_size < 500; tree_size++) {
+    int tree_index = 0;
+    KDTree_1d *tree = BLI_kdtree_1d_new(tree_size);
+    int mask = tree_size & 31;
+    bool occupied[32] = {false};
+
+    for (int i = 0; i < tree_size; i++) {
+      int index = i & mask;
+      occupied[index] = true;
+      float value = fmodf(index * 7.121f, 0.6037f); /* Co-prime. */
+      float key[1] = {value};
+      BLI_kdtree_1d_insert(tree, tree_index++, key);
+    }
+    int expected = 0;
+    for (int j = 0; j < 32; j++) {
+      if (occupied[j]) {
+        expected++;
+      }
+    }
+
+    int dedup_count = BLI_kdtree_1d_deduplicate(tree);
+    EXPECT_EQ(dedup_count, expected);
+    BLI_kdtree_1d_free(tree);
+  }
+}
+
+static void deduplicate_test()
+{
+  for (int tree_size = 1; tree_size < 40; tree_size++) {
+    int tree_index = 0;
+    KDTree_1d *tree = BLI_kdtree_1d_new(tree_size);
+    for (int i = 0; i < tree_size; i++) {
+      float key[1] = {1.0f};
+      BLI_kdtree_1d_insert(tree, tree_index++, key);
+    }
+    int dedup_count = BLI_kdtree_1d_deduplicate(tree);
+    EXPECT_EQ(dedup_count, 1);
+    BLI_kdtree_1d_free(tree);
+  }
+}
+
+TEST(kdtree, Standard)
+{
+  standard_test();
+}
+
+TEST(kdtree, Deduplicate)
+{
+  deduplicate_test();
+}