From anonymous, 3 Months ago, written in Diff-output.
Embed
  1. # note; need to implement 'update' method too
  2. diff --git a/qutebrowser/keyinput/basekeyparser.py b/qutebrowser/keyinput/basekeyparser.py
  3. index 7847c34cd..290431dd0 100644
  4. --- a/qutebrowser/keyinput/basekeyparser.py
  5. +++ b/qutebrowser/keyinput/basekeyparser.py
  6. @@ -21,7 +21,9 @@
  7.  
  8.  import string
  9.  import types
  10. +from typing import Mapping, List, Optional, Union
  11.  
  12. +import attr
  13.  from PyQt5.QtCore import pyqtSignal, QObject
  14.  from PyQt5.QtGui import QKeySequence
  15.  
  16. @@ -30,6 +32,73 @@ from qutebrowser.utils import usertypes, log, utils
  17.  from qutebrowser.keyinput import keyutils
  18.  
  19.  
  20. +@attr.s(slots=True)
  21. +class BindingTrie:
  22. +
  23. +    """Helper class for key parser. Represents a set of bindings.
  24. +
  25. +    Except for the root item, there is no children BindingTrie with no bound
  26. +    commands.
  27. +
  28. +    Attributes:
  29. +        child: A map. Keys of this map can be get from the KeyInfo.to_int
  30. +               method.
  31. +        command: Command associated with the root trie node.
  32. +    """
  33. +
  34. +    child = attr.ib(type=Mapping[int, 'BindingTrie'], factory=dict)
  35. +    command = attr.ib(type=Optional[str], default=None)
  36. +
  37. +    def __setitem__(
  38. +            self, sequence: Union[keyutils.KeySequence, List[int]], command):
  39. +        if isinstance(sequence, keyutils.KeySequence):
  40. +            sequence = [key.to_int() for key in sequence]
  41. +        if not sequence:
  42. +            self.command = command
  43. +            return
  44. +        if sequence[0] not in self.child:
  45. +            self.child[sequence[0]] = BindingTrie()
  46. +        self.child[sequence[0]][sequence[1:]] = command
  47. +
  48. +    def __delitem__(self, sequence):
  49. +        raise NotImplementedError
  50. +
  51. +    def __getitem__(self, sequence):
  52. +        raise NotImplementedError
  53. +
  54. +    def matches(self, sequence: Union[keyutils.KeySequence, List[int]]):
  55. +        """Try to match a given keystring with any bound keychain.
  56. +
  57. +        Have time complexity at most quadratic in the length of the sequence,
  58. +        assume dictionary indexing have constant time.
  59. +
  60. +        Args:
  61. +            sequence: The command string to find.
  62. +
  63. +        Return:
  64. +            A tuple (matchtype, binding).
  65. +                matchtype: QKeySequence.ExactMatch, QKeySequence.PartialMatch
  66. +                           or QKeySequence.NoMatch.
  67. +                binding: - None with QKeySequence.PartialMatch or
  68. +                           QKeySequence.NoMatch.
  69. +                         - The found binding with QKeySequence.ExactMatch.
  70. +        """
  71. +        if isinstance(sequence, keyutils.KeySequence):
  72. +            sequence = [key.to_int() for key in sequence]
  73. +        if not sequence:
  74. +            if self.command is not None:
  75. +                return QKeySequence.ExactMatch, self.command
  76. +            elif self.child:
  77. +                return QKeySequence.PartialMatch, None
  78. +            else:  # This can only happen when there is no bindings
  79. +                return QKeySequence.NoMatch, None
  80. +
  81. +        try:
  82. +            return self.child[sequence[0]].matches(sequence[1:])
  83. +        except KeyError:
  84. +            return QKeySequence.NoMatch, None
  85. +
  86. +
  87.  class BaseKeyParser(QObject):
  88.  
  89.      """Parser for vim-like key sequences and shortcuts.
  90. @@ -76,7 +145,7 @@ class BaseKeyParser(QObject):
  91.          self._sequence = keyutils.KeySequence()
  92.          self._count = ''
  93.          self._supports_count = supports_count
  94. -        self.bindings = {}
  95. +        self.bindings = BindingTrie()
  96.          config.instance.changed.connect(self._on_config_changed)
  97.  
  98.      def __repr__(self):
  99. @@ -105,17 +174,8 @@ class BaseKeyParser(QObject):
  100.          """
  101.          assert sequence
  102.          assert not isinstance(sequence, str)
  103. -        result = QKeySequence.NoMatch
  104. -
  105. -        for seq, cmd in self.bindings.items():
  106. -            assert not isinstance(seq, str), seq
  107. -            match = sequence.matches(seq)
  108. -            if match == QKeySequence.ExactMatch:
  109. -                return match, cmd
  110. -            elif match == QKeySequence.PartialMatch:
  111. -                result = QKeySequence.PartialMatch
  112.  
  113. -        return result, None
  114. +        return self.bindings.matches(sequence)
  115.  
  116.      def _match_without_modifiers(self, sequence):
  117.          """Try to match a key with optional modifiers stripped."""
  118. @@ -236,7 +296,7 @@ class BaseKeyParser(QObject):
  119.              modename = self._modename
  120.          else:
  121.              self._modename = modename
  122. -        self.bindings = {}
  123. +        self.bindings = BindingTrie()
  124.  
  125.          for key, cmd in config.key_instance.get_bindings_for(modename).items():
  126.              assert not isinstance(key, str), key
  127.