[geary/wip/224-subfolders-missing: 2/2] Fix FolderPath mis-sorting doubly-disjoint paths

[Michael Gratton <mjog src gnome org>]

commit af676e057209d1aa582714e257da7dc4e4eeca74
Author: Michael Gratton <mike vee net>
Date:   Tue Feb 19 16:44:03 2019 +1100

    Fix FolderPath mis-sorting doubly-disjoint paths
    
    E.g. a>d should be less than b>c, not the other way around.
    
    Fixes #224

 src/engine/api/geary-folder-path.vala       |  90 +++++++-----------
 test/engine/api/geary-folder-path-test.vala | 141 ++++++++++++++++++++++------
 2 files changed, 146 insertions(+), 85 deletions(-)
---
diff --git a/src/engine/api/geary-folder-path.vala b/src/engine/api/geary-folder-path.vala
index ac91ce92..2dafabcf 100644
--- a/src/engine/api/geary-folder-path.vala
+++ b/src/engine/api/geary-folder-path.vala
@@ -36,6 +36,19 @@ public class Geary.FolderPath :
     /** The base name of this folder, excluding parents. */
     public string name { get; private set; }
 
+    /** The number of children under the root in this path. */
+    public uint length {
+        get {
+            uint length = 0;
+            FolderPath parent = this.parent;
+            while (parent != null) {
+                length++;
+                parent = parent.parent;
+            }
+            return length;
+        }
+    }
+
     /**
      * Whether this path is lexiographically case-sensitive.
      *
@@ -201,37 +214,7 @@ public class Geary.FolderPath :
 
     /** {@inheritDoc} */
     public bool equal_to(FolderPath other) {
-        if (this == other) {
-            return true;
-        }
-
-        FolderPath? a = this;
-        FolderPath? b = other;
-        while (a != null || b != null) {
-            if (a == b) {
-                return true;
-            }
-
-            if ((a != null && b == null) ||
-                (a == null && b != null)) {
-                return false;
-            }
-
-            if (a.case_sensitive || b.case_sensitive) {
-                if (a.name != b.name) {
-                    return false;
-                }
-            } else {
-                if (a.name.down() != b.name.down()) {
-                    return false;
-                }
-            }
-
-            a = a.parent;
-            b = b.parent;
-        }
-
-        return true;
+        return this.compare_internal(other, true, false) == 0;
     }
 
     /**
@@ -259,23 +242,29 @@ public class Geary.FolderPath :
     private int compare_internal(FolderPath other,
                                  bool allow_case_sensitive,
                                  bool normalize) {
-        if (this == other)
+        if (this == other) {
             return 0;
+        }
 
-        FolderPath a = this;
-        FolderPath b = other;
-
-        // Get the common-length prefix of both
-        while (a.path.length != b.path.length) {
-            if (a.path.length > b.path.length) {
-                a = a.parent;
-            } else if (b.path.length > a.path.length) {
-                b = b.parent;
-            }
+        int a_len = (int) this.length;
+        int b_len = (int) other.length;
+        if (a_len != b_len) {
+            return a_len - b_len;
         }
 
-        // Compare the common-length prefixes of both
-        while (a != null && b != null) {
+        return compare_names(this, other, allow_case_sensitive, normalize);
+    }
+
+    private static int compare_names(FolderPath a, FolderPath b,
+                                     bool allow_case_sensitive,
+                                     bool normalize) {
+        int cmp = 0;
+        if (a.parent != null && b.parent != null) {
+            cmp = compare_names(
+                a.parent, b.parent, allow_case_sensitive, normalize
+            );
+        }
+        if (cmp == 0) {
             string a_name = a.name;
             string b_name = b.name;
 
@@ -291,18 +280,9 @@ public class Geary.FolderPath :
                 b_name = b_name.casefold();
             }
 
-            int result = a_name.collate(b_name);
-            if (result != 0) {
-                return result;
-            }
-
-            a = a.parent;
-            b = b.parent;
+            return strcmp(a_name, b_name);
         }
-
-        // paths up to the min element count are equal, shortest path
-        // is less-than, otherwise equal paths
-        return this.path.length - other.path.length;
+        return cmp;
     }
 
 }
diff --git a/test/engine/api/geary-folder-path-test.vala b/test/engine/api/geary-folder-path-test.vala
index 18db7308..eecfe81f 100644
--- a/test/engine/api/geary-folder-path-test.vala
+++ b/test/engine/api/geary-folder-path-test.vala
@@ -25,6 +25,7 @@ public class Geary.FolderPathTest : TestCase {
         add_test("path_hash", path_hash);
         add_test("path_compare", path_compare);
         add_test("path_compare_normalised", path_compare_normalised);
+        add_test("distinct_roots_compare", distinct_roots_compare);
     }
 
     public override void set_up() {
@@ -156,94 +157,174 @@ public class Geary.FolderPathTest : TestCase {
     public void path_compare() throws GLib.Error {
         assert_int(0, this.root.compare_to(this.root), "Root equality");
         assert_int(0,
-            this.root.get_child("test").compare_to(this.root.get_child("test")),
+            this.root.get_child("a").compare_to(this.root.get_child("a")),
             "Equal child comparison"
         );
 
+        // a is less than b
         assert_int(
             -1,
-            this.root.get_child("test1").compare_to(this.root.get_child("test2")),
+            this.root.get_child("a").compare_to(this.root.get_child("b")),
             "Greater than child comparison"
         );
+
+        // b is greater than than a
         assert_int(
             1,
-            this.root.get_child("test2").compare_to(this.root.get_child("test1")),
+            this.root.get_child("b").compare_to(this.root.get_child("a")),
             "Less than child comparison"
         );
 
+        assert_int(
+            1,
+            this.root.get_child("a").get_child("test")
+            .compare_to(this.root.get_child("a")),
+            "Greater than descendant"
+        );
         assert_int(
             -1,
-            this.root.get_child("test1").get_child("test")
-            .compare_to(this.root.get_child("test2").get_child("test")),
-            "Greater than disjoint parents"
+            this.root.get_child("a")
+            .compare_to(this.root.get_child("a").get_child("test")),
+            "Less than descendant"
         );
+
         assert_int(
-            1,
-            this.root.get_child("test2").get_child("test")
-            .compare_to(this.root.get_child("test1").get_child("test")),
-            "Less than disjoint parents"
+            0,
+            this.root.get_child("a").get_child("b")
+            .compare_to(this.root.get_child("a").get_child("b")),
+            "N-path equality"
         );
 
+        assert_int(
+            -1,
+            this.root.get_child("a").get_child("test")
+            .compare_to(this.root.get_child("b").get_child("test")),
+            "Greater than disjoint paths"
+        );
         assert_int(
             1,
-            this.root.get_child("test1").get_child("test")
-            .compare_to(this.root.get_child("test1")),
-            "Greater than descendant"
+            this.root.get_child("b").get_child("test")
+            .compare_to(this.root.get_child("a").get_child("test")),
+            "Less than disjoint paths"
         );
+
         assert_int(
             -1,
-            this.root.get_child("test1")
-            .compare_to(this.root.get_child("test1").get_child("test")),
-            "Less than descendant"
+            this.root.get_child("a").get_child("d")
+            .compare_to(this.root.get_child("b").get_child("c")),
+            "Greater than double disjoint"
+        );
+        assert_int(
+            1,
+            this.root.get_child("b").get_child("c")
+            .compare_to(this.root.get_child("a").get_child("d")),
+            "Less than double disjoint"
         );
+
     }
 
     public void path_compare_normalised() throws GLib.Error {
         assert_int(0, this.root.compare_normalized_ci(this.root), "Root equality");
         assert_int(0,
-            this.root.get_child("test")
-            .compare_normalized_ci(this.root.get_child("test")),
+            this.root.get_child("a").compare_normalized_ci(this.root.get_child("a")),
             "Equal child comparison"
         );
 
+        // a is less than b
         assert_int(
             -1,
-            this.root.get_child("test1")
-            .compare_normalized_ci(this.root.get_child("test2")),
+            this.root.get_child("a").compare_normalized_ci(this.root.get_child("b")),
             "Greater than child comparison"
         );
+
+        // b is greater than than a
         assert_int(
             1,
-            this.root.get_child("test2")
-            .compare_normalized_ci(this.root.get_child("test1")),
+            this.root.get_child("b").compare_normalized_ci(this.root.get_child("a")),
             "Less than child comparison"
         );
 
         assert_int(
             -1,
-            this.root.get_child("test1").get_child("test")
-            .compare_normalized_ci(this.root.get_child("test2").get_child("test")),
+            this.root.get_child("a").get_child("test")
+            .compare_normalized_ci(this.root.get_child("b").get_child("test")),
             "Greater than disjoint parents"
         );
         assert_int(
             1,
-            this.root.get_child("test2").get_child("test")
-            .compare_normalized_ci(this.root.get_child("test1").get_child("test")),
+            this.root.get_child("b").get_child("test")
+            .compare_normalized_ci(this.root.get_child("a").get_child("test")),
             "Less than disjoint parents"
         );
 
         assert_int(
             1,
-            this.root.get_child("test1").get_child("test")
-            .compare_normalized_ci(this.root.get_child("test1")),
+            this.root.get_child("a").get_child("test")
+            .compare_normalized_ci(this.root.get_child("a")),
+            "Greater than descendant"
+        );
+        assert_int(
+            -1,
+            this.root.get_child("a")
+            .compare_normalized_ci(this.root.get_child("a").get_child("test")),
+            "Less than descendant"
+        );
+    }
+
+    public void distinct_roots_compare() throws GLib.Error {
+        assert_int(0, this.root.compare_to(new FolderRoot(false)), "Root equality");
+        assert_int(0,
+            this.root.get_child("a").compare_to(new FolderRoot(false).get_child("a")),
+            "Equal child comparison"
+        );
+
+        // a is less than b
+        assert_int(
+            -1,
+            this.root.get_child("a").compare_to(new FolderRoot(false).get_child("b")),
+            "Greater than child comparison"
+        );
+
+        // b is greater than than a
+        assert_int(
+            1,
+            this.root.get_child("b").compare_to(new FolderRoot(false).get_child("a")),
+            "Less than child comparison"
+        );
+
+        assert_int(
+            1,
+            this.root.get_child("a").get_child("test")
+            .compare_to(new FolderRoot(false).get_child("a")),
             "Greater than descendant"
         );
         assert_int(
             -1,
-            this.root.get_child("test1")
-            .compare_normalized_ci(this.root.get_child("test1").get_child("test")),
+            this.root.get_child("a")
+            .compare_to(new FolderRoot(false).get_child("a").get_child("test")),
             "Less than descendant"
         );
+
+        assert_int(
+            0,
+            this.root.get_child("a").get_child("b")
+            .compare_to(new FolderRoot(false).get_child("a").get_child("b")),
+            "N-path equality"
+        );
+
+        assert_int(
+            -1,
+            this.root.get_child("a").get_child("a")
+            .compare_to(new FolderRoot(false).get_child("b").get_child("b")),
+            "Greater than double disjoint"
+        );
+        assert_int(
+            1,
+            this.root.get_child("b").get_child("a")
+            .compare_to(new FolderRoot(false).get_child("a").get_child("a")),
+            "Less than double disjoint"
+        );
+
     }
 
 }