Merge branch 'find-unique-completion-pair'

4 files changed, 120 insertions, 20 deletions

diff --git a/CHANGES b/CHANGES
index 106f997b..2b0ff4ed 100644
--- a/CHANGES
+++ b/CHANGES
@@ -68,6 +68,7 @@ bash-completion (2.x)
   * Improve ssh -o suboption completion (Alioth: #312122).
   * Fix NFS mounts completion (Alioth: #312285).
   * Fix completion of usernames (Alioth: #311396, Debian: #511788).
+  * Fix chown test crashing on systems with no root group (Alioth: #312306).
 
   [ Raphaël Droz ]
   * Add xsltproc completion (Alioth: #311843).
diff --git a/test/lib/completions/chown.exp b/test/lib/completions/chown.exp
index 3312f5bf..953b2b02 100644
--- a/test/lib/completions/chown.exp
+++ b/test/lib/completions/chown.exp
@@ -17,26 +17,21 @@ assert_complete $users "chown "
 sync_after_int
 
 
-# All the tests use the root:root user and group. They're assumed to exist.
-set fulluser "root"
-set fullgroup "root"
-
-# Partial username is assumed to be unambiguous.
-set partuser "roo"
-set partgroup "roo"
-
-# Skip tests if root:root not available or if roo:roo matches multiple
-# users/groups
-#
-# compgen -A is used because it's a bash builtin and available everywhere.
-# The || true part prevents exec from throwing an exception if nothing is
-# found.
-if {[exec bash -c "compgen -A user $partuser || true" | wc -l] > 1 ||
-    [exec bash -c "compgen -A user $fulluser || true" | wc -l] != 1 ||
-    [exec bash -c "compgen -A group $partgroup || true" | wc -l] > 1 ||
-    [exec bash -c "compgen -A group $fullgroup || true" | wc -l] != 1} {
-    untested "Not running complex chown tests."
-} else {
+# Find user/group suitable for testing.
+set failed_find_unique_completion 0
+foreach ug {user group} {
+    # compgen -A is used because it's a bash builtin and available everywhere.
+    # The || true part prevents exec from throwing an exception if nothing is
+    # found (very very unlikely).
+    set list [split [exec bash -c "compgen -A $ug || true"] "\n"]
+    if {![find_unique_completion_pair $list part$ug full$ug]} {
+        untested "Not running complex chown tests; no suitable test $ug found."
+        set failed_find_unique_completion 1
+    }
+}
+
+# These tests require an unique completion.
+if {!$failed_find_unique_completion} {
     assert_complete $fulluser "chown $partuser"
     sync_after_int
 
diff --git a/test/lib/library.exp b/test/lib/library.exp
index 387b40b7..3de310bf 100644
--- a/test/lib/library.exp
+++ b/test/lib/library.exp
@@ -721,6 +721,73 @@ proc split_words_bash {line} {
 }; # split_words_bash()
 
 
+# Given a list of items this proc finds a (part, full) pair so that when
+# completing from $part $full will be the only option.
+#
+# Arguments:
+#       list        The list of full completions.
+#       partName    Output parameter for the partial string.
+#       fullName    Output parameter for the full string, member of item.
+#
+# Results:
+#       1, or 0 if no suitable result was found.
+proc find_unique_completion_pair {{list} {partName} {fullName}} {
+    upvar $partName part
+    upvar $fullName full
+    set bestscore 0
+    set list [lsort $list]
+    set n [llength $list]
+    for {set i 0} {$i < $n} {incr i} {
+        set cur [lindex $list $i]
+        set curlen [string length $cur]
+
+        set prev [lindex $list [expr {$i - 1}]]
+        set next [lindex $list [expr {$i + 1}]]
+        set diffprev [expr {$prev == ""}]
+        set diffnext [expr {$next == ""}]
+
+        # Analyse each item of the list and look for the minimum length of the
+        # partial prefix which is distinct from both $next and $prev. The list
+        # is sorted so the prefix will be unique in the entire list.
+        #
+        # In the worst case we analyse every character in the list 3 times.
+        # That's actually very fast, sorting could take more.
+        for {set j 0} {$j < $curlen} {incr j} {
+            set curchar [string index $cur $j]
+            if {!$diffprev && [string index $prev $j] != $curchar} {
+                set diffprev 1
+            }
+            if {!$diffnext && [string index $next $j] != $curchar} {
+                set diffnext 1
+            }
+            if {$diffnext && $diffprev} {
+                break
+            }
+        }
+
+        # At the end of the loop $j is the index of last character of
+        # the unique partial prefix. The length is one plus that.
+        set parlen [expr {$j + 1}]
+        if {$parlen >= $curlen} {
+            continue
+        }
+
+        # Try to find the most "readable pair"; look for a long pair where
+        # $part is about half of $full.
+        if {$parlen < $curlen / 2} {
+            set parlen [expr {$curlen / 2}]
+        }
+        set score [expr {$curlen - $parlen}]
+        if {$score > $bestscore} {
+            set bestscore $score
+            set part [string range $cur 0 [expr {$parlen - 1}]]
+            set full $cur
+        }
+    }
+    return [expr {$bestscore != 0}]
+}
+
+
 # Start bash running as test environment.
 proc start_bash {} {
     global TESTDIR TOOL_EXECUTABLE spawn_id
diff --git a/test/unit/find_unique_completion_pair.exp b/test/unit/find_unique_completion_pair.exp
new file mode 100644
index 00000000..ec7f040d
--- /dev/null
+++ b/test/unit/find_unique_completion_pair.exp
@@ -0,0 +1,37 @@
+# Note: This test actually tests a function in the test library. It doesn't
+# need bash running; but it doesn't hurt either.
+
+# Run one test. Look below for usage.
+proc test_find_ucp {{list} {epart} {econt} {eret 1}} {
+    set efull "$epart$econt"
+    set rret [find_unique_completion_pair $list rpart rfull]
+    if {$eret != $rret} {
+        if {$eret} {
+            fail "find_unique_completion_pair: Nothing found for {$list}"
+        } else {
+            fail "find_unique_completion_pair: Expected failure for {$list}"
+        }
+    } elseif {!$eret} {
+        pass "find_unique_completion_pair: No results for list {$list}"
+    } elseif {$rpart != $epart || $rfull != $efull} {
+        fail "find_unique_completion_pair: Got \"$rpart\", \"$rfull\" \
+                instead of \"$epart\", \"$efull\" for list {$list}"
+    } else {
+        pass "find_unique_completion_pair: Got \"$epart\", \"$efull\" \
+                for list {$list}"
+    }
+}
+
+test_find_ucp {a} 0 0 0
+test_find_ucp {ab} a b
+test_find_ucp {a ab abcd abc} 0 0 0
+test_find_ucp {a ab abcde abc} abcd e
+test_find_ucp {user1 user2} 0 0 0
+test_find_ucp {root username2 username1} ro ot
+test_find_ucp {root username21 username2} ro ot
+test_find_ucp {long_user_name lang_user_name long_usor_name} lang_us er_name
+test_find_ucp {lang_user_name1 long_user_name lang_user_name long_usor_name} \
+          long_use r_name
+test_find_ucp {root username} user name
+test_find_ucp {a aladin} ala din
+test_find_ucp {ala aladin} alad in