fuzzy search cannot handle same-distance case

[Brano Zarnovican]

When exact command match is not found, fuzzy search will trigger. It will calculate the Levenshtein distance from entered string to each command. Commands with minimum distance are then offered as suggestion.

Problem:
When all commands have the same distance then the code will bomb-out with IndexError.

To reproduce:
1. create an App with two implicit commands "complete", "help"
2. add one custom command "user"
3. execute cliff app with "node" as command

Expected output:
cliff should suggest all three commands

Actual Result:
$ python myapp.py node
Traceback (most recent call last):
  File "myapp.py", line 31, in <module>
    sys.exit(main(sys.argv[1:]))
  File "myapp.py", line 27, in main
    return app.run(argv)
  File "/home/zarnovic/venv/cliff/lib/python2.7/site-packages/cliff/app.py", line 255, in run
    result = self.run_subcommand(remainder)
  File "/home/zarnovic/venv/cliff/lib/python2.7/site-packages/cliff/app.py", line 343, in run_subcommand
    fuzzy_matches = self.get_fuzzy_matches(the_cmd)
  File "/home/zarnovic/venv/cliff/lib/python2.7/site-packages/cliff/app.py", line 331, in get_fuzzy_matches
    while (dist[i][1] == best_similarity):
IndexError: list index out of range

In the attached example code, there are three commands: "complete", "help", "user". First two are implicit. String "node" entered on command-line has the same distance from all three. Iterating loop looking for the command with the next higher distance will fall over the edge.

There are two similar problems around the same code. It assumes that list of commands is non-empty. It also has problem in case when entered command is a prefix of all command. Since "complete" and "help" are always present and they don't have common prefix, this is not an issue (now).

This problem was originally spotted and analyzed by Radek Smidl.

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/228466

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/228466
Committed: https://git.openstack.org/cgit/openstack/cliff/commit/?id=b8e7a78a45951d8e48c157703bfd616b2fe40ddd
Submitter: Jenkins
Branch: master

commit b8e7a78a45951d8e48c157703bfd616b2fe40ddd
Author: Brano Zarnovican <email address hidden>
Date: Mon Sep 28 14:33:51 2015 +0200

    fix fuzzy search for same-distance case

    get_fuzzy_matches() cannot handle case where all
    commands have the same Levenshtein distance
    from searched command. It will bomb-out with
    IndexError (dist[i][1] referencing one element
    after the end).

    It also does not handle no-commands case or
    the case where searched command is the prefix of
    all commands. The latter two cases are minor, since
    'help' and 'complete' commands are always present.

    We fix it by iterating over the partial result
    safely, consuming only candidates with distance==0
    (prefix commands) and those of the same minimum
    distance.

    Closes-Bug: #1500445
    Change-Id: Iae5e77b64dc0d96e040acdcadf019db66a416648

[Doug Hellmann (doug-hellmann)]

This issue was fixed in the openstack/cliff 1.16.0 release.