Add support for less/greater than comparisons

Was added upstream in 31847b67 (kconfig: allow use of relations other
than (in)equality). Completely unused (and undocumented) in the kernel
except for in DEBUG_UART_8250_WORD in arch/arm/Kconfig.debug:

   depends on DEBUG_UART_8250_SHIFT >= 2

(That line was added before lt/gt support by the way, and assumed a
feature that wasn't there.)

This change (and the upstream one) also slightly changes how
(in)equality comparisons work, making e.g.

  MY_HEX = 0x00037

evaluate to 'y' if MY_HEX is 0x37. Prior to this change, the strings
needed to match exactly.

8 files changed, 242 insertions, 31 deletions

diff --git a/kconfiglib.py b/kconfiglib.py
index 5b9a2a9..12da848 100644
--- a/kconfiglib.py
+++ b/kconfiglib.py
@@ -1179,12 +1179,12 @@ class Config(object):
             # For conditional expressions ('depends on <expr>',
             # '... if <expr>', # etc.), "m" and m are rewritten to
             # "m" && MODULES.
-            if next_token != T_EQUAL and next_token != T_UNEQUAL:
+            if next_token not in TOKEN_TO_RELATION:
                 if self._transform_m and (token is self.m or token == "m"):
                     return (AND, ["m", self._sym_lookup("MODULES")])
                 return token
 
-            relation = EQUAL if (feed.get_next() == T_EQUAL) else UNEQUAL
+            relation = TOKEN_TO_RELATION[feed.get_next()]
             token_2 = feed.get_next()
             if self._cur_item is not None and isinstance(token_2, Symbol):
                 self._cur_item.referenced_syms.add(token_2)
@@ -1356,11 +1356,33 @@ class Config(object):
                     else:
                         append(T_NOT)
 
-                elif c == "=": append(T_EQUAL)
-                elif c == "(": append(T_OPEN_PAREN)
-                elif c == ")": append(T_CLOSE_PAREN)
+                elif c == "=":
+                    append(T_EQUAL)
+
+                elif c == "(":
+                    append(T_OPEN_PAREN)
+
+                elif c == ")":
+                    append(T_CLOSE_PAREN)
+
                 elif c == "#": break # Comment
 
+                # Very rare
+                elif c == "<":
+                    if i < len(s) and s[i] == "=":
+                        append(T_LESS_EQUAL)
+                        i += 1
+                    else:
+                        append(T_LESS)
+
+                # Very rare
+                elif c == ">":
+                    if i < len(s) and s[i] == "=":
+                        append(T_GREATER_EQUAL)
+                        i += 1
+                    else:
+                        append(T_GREATER)
+
                 else: continue # Invalid characters are ignored
 
             previous = tokens[-1]
@@ -1452,11 +1474,43 @@ class Config(object):
             # short-circuiting "y" case in the loop.
             return res
 
-        if expr[0] == EQUAL:
-            return "y" if (_str_val(expr[1]) == _str_val(expr[2])) else "n"
+        if expr[0] in RELATIONS:
+            # Implements <, <=, >, >= comparisons as well. These were added to
+            # kconfig in 31847b67 (kconfig: allow use of relations other than
+            # (in)equality).
+
+            # This mirrors the C implementation pretty closely. Perhaps there's
+            # a more pythonic way to structure this.
 
-        if expr[0] == UNEQUAL:
-            return "y" if (_str_val(expr[1]) != _str_val(expr[2])) else "n"
+            oper, op1, op2 = expr
+            op1_type, op1_str = _type_and_val(op1)
+            op2_type, op2_str = _type_and_val(op2)
+
+            # If both operands are strings...
+            if op1_type == STRING and op2_type == STRING:
+                # ...then compare them lexicographically
+                comp = _strcmp(op1_str, op2_str)
+            else:
+                # Otherwise, try to compare them as numbers
+                try:
+                    comp = int(op1_str, TYPE_TO_BASE[op1_type]) - \
+                           int(op2_str, TYPE_TO_BASE[op2_type])
+                except ValueError:
+                    # They're not both valid numbers. If the comparison is
+                    # anything but = or !=, return 'n'. Otherwise, reuse
+                    # _strcmp() to check for (in)equality.
+                    if oper not in (EQUAL, UNEQUAL):
+                        return "n"
+                    comp = _strcmp(op1_str, op2_str)
+
+            if   oper == EQUAL:         res = comp == 0
+            elif oper == UNEQUAL:       res = comp != 0
+            elif oper == LESS:          res = comp < 0
+            elif oper == LESS_EQUAL:    res = comp <= 0
+            elif oper == GREATER:       res = comp > 0
+            elif oper == GREATER_EQUAL: res = comp >= 0
+
+            return "y" if res else "n"
 
         _internal_error("Internal error while evaluating expression: "
                         "unknown operation {0}.".format(expr[0]))
@@ -3292,7 +3346,7 @@ def _get_expr_syms_rec(expr, res):
             _get_expr_syms_rec(term, res)
     elif expr[0] == NOT:
         _get_expr_syms_rec(expr[1], res)
-    elif expr[0] == EQUAL or expr[0] == UNEQUAL:
+    elif expr[0] in RELATIONS:
         if isinstance(expr[1], Symbol):
             res.add(expr[1])
         if isinstance(expr[2], Symbol):
@@ -3338,7 +3392,7 @@ def _intersperse(lst, op):
 
     def handle_sub_expr(expr):
         no_parens = isinstance(expr, (str, Symbol)) or \
-                    expr[0] in (EQUAL, UNEQUAL) or \
+                    expr[0] in RELATIONS or \
                     PRECEDENCE[op] <= PRECEDENCE[expr[0]]
         if not no_parens:
             res.append("(")
@@ -3376,7 +3430,7 @@ def _expr_to_str_rec(expr):
             res.append(")")
         return res
 
-    if expr[0] in (EQUAL, UNEQUAL):
+    if expr[0] in RELATIONS:
         return [_sym_str_string(expr[1]),
                 OP_TO_STR[expr[0]],
                 _sym_str_string(expr[2])]
@@ -3384,6 +3438,14 @@ def _expr_to_str_rec(expr):
 def _expr_to_str(expr):
     return "".join(_expr_to_str_rec(expr))
 
+def _type_and_val(obj):
+    """Helper to hack around the fact that we don't represent plain strings as
+    Symbols. Takes either a plain string or a Symbol and returns a
+    (<type>, <value>) tuple."""
+    if isinstance(obj, str):
+        return (STRING, obj)
+    return (obj.type, obj.get_value())
+
 def _indentation(line):
     """Returns the length of the line's leading whitespace, treating tab stops
     as being spaced 8 characters apart."""
@@ -3404,6 +3466,10 @@ def _is_base_n(s, n):
     except ValueError:
         return False
 
+def _strcmp(s1, s2):
+    """strcmp()-alike that returns -1, 0, or 1."""
+    return (s1 > s2) - (s1 < s2)
+
 def _lines(*args):
     """Returns a string consisting of all arguments, with newlines inserted
     between them."""
@@ -3454,6 +3520,7 @@ def _internal_error(msg):
 (T_AND, T_OR, T_NOT,
  T_OPEN_PAREN, T_CLOSE_PAREN,
  T_EQUAL, T_UNEQUAL,
+ T_LESS, T_LESS_EQUAL, T_GREATER, T_GREATER_EQUAL,
  T_MAINMENU, T_MENU, T_ENDMENU,
  T_SOURCE, T_CHOICE, T_ENDCHOICE,
  T_COMMENT, T_CONFIG, T_MENUCONFIG,
@@ -3462,7 +3529,7 @@ def _internal_error(msg):
  T_BOOL, T_TRISTATE, T_HEX, T_INT, T_STRING,
  T_DEF_BOOL, T_DEF_TRISTATE,
  T_SELECT, T_IMPLY, T_RANGE, T_OPTION, T_ALLNOCONFIG_Y, T_ENV,
- T_DEFCONFIG_LIST, T_MODULES, T_VISIBLE) = range(40)
+ T_DEFCONFIG_LIST, T_MODULES, T_VISIBLE) = range(44)
 
 # The leading underscore before the function assignments below prevent pydoc
 # from listing them. The constants could be hidden too, but they're fairly
@@ -3522,12 +3589,28 @@ DEFAULT_VALUE = {BOOL: "n", TRISTATE: "n", STRING: "", INT: "", HEX: ""}
 NO_SELECTION = 0
 
 # Integers representing expression types
-AND, OR, NOT, EQUAL, UNEQUAL = range(5)
+AND, OR, NOT, EQUAL, UNEQUAL, LESS, LESS_EQUAL, GREATER, \
+GREATER_EQUAL = range(9)
+
+# Token to relation (=, !=, <, ...) mapping
+TOKEN_TO_RELATION = {T_EQUAL: EQUAL, T_UNEQUAL: UNEQUAL, T_LESS: LESS,
+                     T_LESS_EQUAL: LESS_EQUAL, T_GREATER: GREATER,
+                     T_GREATER_EQUAL: GREATER_EQUAL}
+
+RELATIONS = frozenset((EQUAL, UNEQUAL, LESS, LESS_EQUAL, GREATER,
+                       GREATER_EQUAL))
+
+# Used in comparisons. 0 means the base is inferred from the format of the
+# string. The entries for BOOL and TRISTATE are a convenience - they should
+# never convert to valid numbers.
+TYPE_TO_BASE = {UNKNOWN: 0, BOOL: 0, TRISTATE: 0, STRING: 0, HEX: 16, INT: 10}
 
 # Map from tristate values to integers
 TRI_TO_INT = {"n": 0, "m": 1, "y": 2}
 
 # Printing-related stuff
 
-OP_TO_STR = {AND: " && ", OR: " || ", EQUAL: " = ", UNEQUAL: " != "}
+OP_TO_STR = {AND: " && ", OR: " || ", EQUAL: " = ", UNEQUAL: " != ",
+             LESS: " < ", LESS_EQUAL: " <= ", GREATER: " > ",
+             GREATER_EQUAL: " >= "}
 PRECEDENCE = {OR: 0, AND: 1, NOT: 2}
diff --git a/tests/Kchain b/tests/Kchain
index dc57ee5..643a949 100644
--- a/tests/Kchain
+++ b/tests/Kchain
@@ -119,5 +119,9 @@ config DUMMY_3
 endchoice
 
 config CHAIN_25
-    string "chain 25"
+    int "chain 25"
     depends on CHAIN_24
+
+config CHAIN_26
+    int "chain 26"
+    default 0 if y && 0 < CHAIN_25
diff --git a/tests/Kdep b/tests/Kdep
index 87defaa..bde8790 100644
--- a/tests/Kdep
+++ b/tests/Kdep
@@ -140,6 +140,26 @@ config D31
 config D32
     tristate "D32"
 
+config D33
+    int "D33"
+    default 0 if D < 0
+
+config D34
+    int "D34"
+    default 0 if 0 < D
+
+config D35
+    int "D35"
+    default 0 if 0 <= D
+
+config D36
+    int "D36"
+    default 0 if 0 > D
+
+config D37
+    int "D37"
+    default 0 if 0 >= D
+
 #
 # Choices
 #
diff --git a/tests/Keval b/tests/Keval
index 191f518..64bd4d8 100644
--- a/tests/Keval
+++ b/tests/Keval
@@ -19,10 +19,14 @@ config FOO_BAR_STRING
     string
     default "foo bar"
 
-config INT_3
+config INT_37
     int
-    default 3
+    default 37
 
-config HEX_0X3
+config HEX_0X37
     hex
-    default 0x3
+    default 0x37
+
+config HEX_37
+    hex
+    default 37
diff --git a/tests/Klocation b/tests/Klocation
index 76a886b..404e5ae 100644
--- a/tests/Klocation
+++ b/tests/Klocation
@@ -65,3 +65,9 @@ config I
     range A 0
     range 0 A
     range 0 1 if A
+    default J if A < 0
+    default K if 0 < A
+    default L if 0 <= A
+    default M if 0 > A
+    default N if 0 >= A
+    default N if y && 0 < A
diff --git a/tests/Kref b/tests/Kref
index a60561e..b538b15 100644
--- a/tests/Kref
+++ b/tests/Kref
@@ -20,7 +20,7 @@ config MANY_REF
     select N if (A || !(B && (C = O)))
     imply P if Q = R || S != T
     imply U if (A || !(B && (C = V)))
-
+    default A if A < W || X < A || A <= Y || A > Z || A >= AA
 endif
 
 endmenu
diff --git a/tests/Ktext b/tests/Ktext
index c645bde..958ee18 100644
--- a/tests/Ktext
+++ b/tests/Ktext
@@ -10,7 +10,7 @@ config ADVANCED
     imply IMPLIED_1 if BASIC || DUMMY
     imply IMPLIED_2 if !(DUMMY && BASIC)
     default y if BASIC && !BASIC
-    default n if BASIC = DUMMY
+    default n if BASIC = DUMMY && X < Y && X <= Y && X > Y && X >= Y
 
 config ADVANCED
     tristate "advanced prompt 2"
diff --git a/testsuite.py b/testsuite.py
index c8f504c..162bad8 100644
--- a/testsuite.py
+++ b/testsuite.py
@@ -396,10 +396,15 @@ def run_selftests():
     verify_eval("Y_STRING = 'y'", "y")
     verify_eval('FOO_BAR_STRING = "foo bar"', "y")
     verify_eval('FOO_BAR_STRING != "foo bar baz"', "y")
-    verify_eval('INT_3 = 3', "y")
-    verify_eval("INT_3 = '3'", "y")
-    verify_eval('HEX_0X3 = 0x3', "y")
-    verify_eval("HEX_0X3 = '0x3'", "y")
+    verify_eval('INT_37 = 37', "y")
+    verify_eval("INT_37 = '37'", "y")
+    verify_eval('HEX_0X37 = 0x37', "y")
+    verify_eval("HEX_0X37 = '0x37'", "y")
+
+    # These should also hold after 31847b67 (kconfig: allow use of relations
+    # other than (in)equality)
+    verify_eval("HEX_0X37 = '0x037'", "y")
+    verify_eval("HEX_0X37 = '0x0037'", "y")
 
     # Compare some constants...
     verify_eval('"foo" != "bar"', "y")
@@ -411,6 +416,88 @@ def run_selftests():
     verify_eval("not_defined_2 = not_defined_2", "y")
     verify_eval("not_defined_1 != not_defined_2", "y")
 
+    # Test less than/greater than
+
+    # Basic evaluation
+    verify_eval("INT_37 < 38", "y")
+    verify_eval("38 < INT_37", "n")
+    verify_eval("INT_37 < '38'", "y")
+    verify_eval("'38' < INT_37", "n")
+    verify_eval("INT_37 < 138", "y")
+    verify_eval("138 < INT_37", "n")
+    verify_eval("INT_37 < '138'", "y")
+    verify_eval("'138' < INT_37", "n")
+    verify_eval("INT_37 < -138", "n")
+    verify_eval("-138 < INT_37", "y")
+    verify_eval("INT_37 < '-138'", "n")
+    verify_eval("'-138' < INT_37", "y")
+    verify_eval("INT_37 < 37", "n")
+    verify_eval("37 < INT_37", "n")
+    verify_eval("INT_37 < 36", "n")
+    verify_eval("36 < INT_37", "y")
+
+    # Different formats in comparison
+    verify_eval("INT_37 < 0x26", "y") # 38
+    verify_eval("INT_37 < 0x25", "n") # 37
+    verify_eval("INT_37 < 0x24", "n") # 36
+    verify_eval("HEX_0X37 < 56", "y") # 0x38
+    verify_eval("HEX_0X37 < 55", "n") # 0x37
+    verify_eval("HEX_0X37 < 54", "n") # 0x36
+
+    # Other int comparisons
+    verify_eval("INT_37 <= 38", "y")
+    verify_eval("INT_37 <= 37", "y")
+    verify_eval("INT_37 <= 36", "n")
+    verify_eval("INT_37 >  38", "n")
+    verify_eval("INT_37 >  37", "n")
+    verify_eval("INT_37 >  36", "y")
+    verify_eval("INT_37 >= 38", "n")
+    verify_eval("INT_37 >= 37", "y")
+    verify_eval("INT_37 >= 36", "y")
+
+    # Other hex comparisons
+    verify_eval("HEX_0X37 <= 0x38", "y")
+    verify_eval("HEX_0X37 <= 0x37", "y")
+    verify_eval("HEX_0X37 <= 0x36", "n")
+    verify_eval("HEX_0X37 >  0x38", "n")
+    verify_eval("HEX_0X37 >  0x37", "n")
+    verify_eval("HEX_0X37 >  0x36", "y")
+    verify_eval("HEX_0X37 >= 0x38", "n")
+    verify_eval("HEX_0X37 >= 0x37", "y")
+    verify_eval("HEX_0X37 >= 0x36", "y")
+
+    # A hex holding a value without a "0x" prefix should still be treated as
+    # hexadecimal
+    verify_eval("HEX_37 < 0x38", "y")
+    verify_eval("HEX_37 < 0x37", "n")
+    verify_eval("HEX_37 < 0x36", "n")
+
+    # Symbol comparisons
+    verify_eval("INT_37   <  HEX_0X37", "y")
+    verify_eval("INT_37   >  HEX_0X37", "n")
+    verify_eval("HEX_0X37 <  INT_37  ", "n")
+    verify_eval("HEX_0X37 >  INT_37  ", "y")
+    verify_eval("INT_37   <  INT_37  ", "n")
+    verify_eval("INT_37   <= INT_37  ", "y")
+    verify_eval("INT_37   >  INT_37  ", "n")
+    verify_eval("INT_37   <= INT_37  ", "y")
+
+    # Strings compare lexicographically
+    verify_eval("'aa' < 'ab'", "y")
+    verify_eval("'aa' > 'ab'", "n")
+    verify_eval("'ab' < 'aa'", "n")
+    verify_eval("'ab' > 'aa'", "y")
+
+    # If one operand is numeric and the other not a valid number, we get 'n'
+    verify_eval("INT_37 <  oops  ", "n")
+    verify_eval("INT_37 <= oops  ", "n")
+    verify_eval("INT_37 >  oops  ", "n")
+    verify_eval("INT_37 >= oops  ", "n")
+    verify_eval("oops   <  INT_37", "n")
+    verify_eval("oops   <= INT_37", "n")
+    verify_eval("oops   >  INT_37", "n")
+    verify_eval("oops   >= INT_37", "n")
+
     # The C implementation's parser can be pretty lax about syntax. Kconfiglib
     # sometimes needs to emulate that. Verify that some bad stuff throws
     # Kconfig_Syntax_Error at least.
@@ -526,7 +613,7 @@ def run_selftests():
        y (value: "y")
         Condition: BASIC && !BASIC (value: "n")
        n (value: "n")
-        Condition: BASIC = DUMMY (value: "n")
+        Condition: BASIC = DUMMY && X < Y && X <= Y && X > Y && X >= Y (value: "n")
       Selects:
        SELECTED_1 if BASIC && DUMMY (value: "n")
        SELECTED_2 if !(DUMMY || BASIC) (value: "y")
@@ -772,7 +859,13 @@ def run_selftests():
       ("Kconfiglib/tests/Klocation_included", 40),
       ("Kconfiglib/tests/Klocation", 65),
       ("Kconfiglib/tests/Klocation", 66),
-      ("Kconfiglib/tests/Klocation", 67))
+      ("Kconfiglib/tests/Klocation", 67),
+      ("Kconfiglib/tests/Klocation", 68),
+      ("Kconfiglib/tests/Klocation", 69),
+      ("Kconfiglib/tests/Klocation", 70),
+      ("Kconfiglib/tests/Klocation", 71),
+      ("Kconfiglib/tests/Klocation", 72),
+      ("Kconfiglib/tests/Klocation", 73))
     verify_ref_locations("C")
     verify_ref_locations("NOT_DEFINED",
       ("Kconfiglib/tests/Klocation", 12),
@@ -1240,7 +1333,8 @@ def run_selftests():
     verify_sym_refs("NO_REF", [], [])
     verify_sym_refs("ONE_REF", ["A"], ["A"])
     own_refs = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L",
-                "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V"]
+                "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X",
+                "Y", "Z", "AA"]
     verify_sym_refs("MANY_REF",
       own_refs,
       own_refs + ["IF_REF_1", "IF_REF_2", "MENU_REF_1",
@@ -1852,7 +1946,7 @@ def run_selftests():
 
     # Test twice to cover dependency caching
     for i in range(0, 2):
-        n_deps = 32
+        n_deps = 37
         # Verify that D1, D2, .., D<n_deps> are dependent on D
         verify_dependent("D", ["D{0}".format(i) for i in range(1, n_deps + 1)])
         # Choices
@@ -1867,7 +1961,7 @@ def run_selftests():
     c = kconfiglib.Config("Kconfiglib/tests/Kchain")
 
     for i in range(0, 2):
-        verify(c["CHAIN_25"] in c["CHAIN_1"]._get_dependent(),
+        verify(c["CHAIN_26"] in c["CHAIN_1"]._get_dependent(),
                "Dependency chain broken")
 
     print("\nAll selftests passed\n" if _all_ok else