Branch selection textbox should filter branches using fuzzy matching

Issue #4589 closed
Yuri Bochkarev
created an issue

Please filter branch suggestions in the branch selection textbox using a fuzzy matching.

At the moment, it looks like the filtering is performed using a variant of startswith, which is not helpful in my case. I have a ton of branches and they all have a numerical prefix RT123456_implement_some_feature. I can remember part of the branch name but there is no way I can remember the numerical code in the beginning. Fuzzy matching will be very helpful in this case.

https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm may be a good candidate. Alternative algorithms: https://github.com/jhawthorn/fzy/blob/master/ALGORITHM.md

Thank you!

Comments (10)

  1. Yuri Bochkarev reporter

    Yes, you are right. Actually, I've managed to come up with a simple class that does exactly this. Here is the demo (http://imgur.com/a/9y5D9) branch-filter.gif

    Here is my patch (http://sprunge.us/PNEe)

    --- repofilter.py   2016-08-02 20:08:10.000000000 +0300
    +++ tortoisehg-3.9/tortoisehg/hgqt/repofilter.py    2016-09-08 20:17:02.954700926 +0300
    @@ -21,6 +21,30 @@
                           'tagged()', 'bookmark()',
                           'file(".hgsubstate") or file(".hgsub")')
    
    +
    +class ExactMultipartFilterModel(QSortFilterProxyModel):
    +    """
    +    This model is used to filter view by a pattern that contains words,
    +    separated with spaces. Each word of the pattern should be present in a row.
    +    """
    +    def __init__(self, parent):
    +        super(ExactMultipartFilterModel, self).__init__(parent)
    +        self._filteringRegExp = None
    +
    +    def setFilterString(self, text):
    +        pattern = text.toLower().replace(QRegExp("\s+"), ".*")
    +        self._filteringRegExp = QRegExp(pattern, Qt.CaseInsensitive)
    +        self.invalidateFilter()
    +
    +    def filterAcceptsRow(self, intSourceRow, sourceParent):
    +        if self._filteringRegExp is None:
    +            return False
    +
    +        index0 = self.sourceModel().index(intSourceRow, 0, sourceParent)
    +        data = self.sourceModel().data(index0).toString()
    +        return data.contains(self._filteringRegExp)
    +
    +
     def _firstword(query):
         try:
             for token, value, _pos in hgrevset.tokenize(hglib.fromunicode(query)):
    @@ -377,6 +401,15 @@
             self._branchCombo.setMaxVisibleItems(30)
             self._branchCombo.currentIndexChanged.connect(self._emitBranchChanged)
             completer = QCompleter(self._branchCombo.model(), self._branchCombo)
    +
    +        self._custom_branch_filter = ExactMultipartFilterModel(self)
    +        self._custom_branch_filter.setSourceModel(self._branchCombo.model())
    +        self._branchCombo.lineEdit().textEdited[unicode].connect(
    +            self._custom_branch_filter.setFilterString)
    +
    +        completer.setModel(self._custom_branch_filter)
    +        completer.setCompletionMode(QCompleter.UnfilteredPopupCompletion)
    +
             self._branchCombo.setCompleter(completer)
    
             self.addWidget(self._branchLabel)
    

    Would you be willing to consider including my patch? Thank you!

  2. Yuya Nishihara

    Using word patterns would be debatable since we don't do that in other places. So I suggest you to start with a simpler substring matcher.

    Anyway, there's no need to subclass QSortFilterProxyModel.

  3. Log in to comment