kc3-lang/libxkbcommon

diff --git a/doc/message-registry.md b/doc/message-registry.md
index b5358f0..c3e3ec0 100644
--- a/doc/message-registry.md
+++ b/doc/message-registry.md
@@ -39,6 +39,7 @@ There are currently 54 entries.
 | [XKB-338] | `included-file-not-found` | Could not find a file used in an include statement | Error |
 | [XKB-345] | `unknown-operator` | Use of an operator that is unknown and thus unsupported | Error |
 | [XKB-378] | `duplicate-entry` | An entry is duplicated and will be ignored | Warning |
+| [XKB-386] | `recursive-include` | Included files form cycle | Error |
 | [XKB-407] | `conflicting-key-type-definitions` | Conflicting definitions of a key type | Warning |
 | [XKB-428] | `wrong-scope` | A statement is in a wrong scope and should be moved | Error |
 | [XKB-433] | `missing-default-section` | Missing default section in included file | Warning |
@@ -327,6 +328,14 @@ as numbers and as identifiers `LevelN`, where `N` is in the range (1..8).
   <dt>Summary</dt><dd>An entry is duplicated and will be ignored</dd>
 </dl>
 
+### XKB-386 – Recursive include {#XKB-386}
+
+<dl>
+  <dt>Since</dt><dd>1.7.0</dd>
+  <dt>Type</dt><dd>Error</dd>
+  <dt>Summary</dt><dd>Included files form cycle</dd>
+</dl>
+
 ### XKB-407 – Conflicting key type definitions {#XKB-407}
 
 <dl>
@@ -657,6 +666,7 @@ The modifiers used in `map` or `preserve` entries should be declared using the e
 [XKB-338]: @ref XKB-338
 [XKB-345]: @ref XKB-345
 [XKB-378]: @ref XKB-378
+[XKB-386]: @ref XKB-386
 [XKB-407]: @ref XKB-407
 [XKB-428]: @ref XKB-428
 [XKB-433]: @ref XKB-433
diff --git a/doc/message-registry.yaml b/doc/message-registry.yaml
index 0b7db81..ff1fece 100644
--- a/doc/message-registry.yaml
+++ b/doc/message-registry.yaml
@@ -180,6 +180,11 @@
   added: ALWAYS
   type: warning
   description: "An entry is duplicated and will be ignored"
+- id: "recursive-include"
+  code: 386
+  added: 1.7.0
+  type: error
+  description: "Included files form cycle"
 - id: "conflicting-key-type-definitions"
   code: 407
   added: ALWAYS
diff --git a/src/messages-codes.h b/src/messages-codes.h
index 3206831..b90677f 100644
--- a/src/messages-codes.h
+++ b/src/messages-codes.h
@@ -66,6 +66,8 @@ enum xkb_message_code {
     XKB_ERROR_UNKNOWN_OPERATOR = 345,
     /** An entry is duplicated and will be ignored */
     XKB_WARNING_DUPLICATE_ENTRY = 378,
+    /** Included files form cycle */
+    XKB_ERROR_RECURSIVE_INCLUDE = 386,
     /** Conflicting definitions of a key type */
     XKB_WARNING_CONFLICTING_KEY_TYPE_DEFINITIONS = 407,
     /** A statement is in a wrong scope and should be moved */
diff --git a/src/xkbcomp/compat.c b/src/xkbcomp/compat.c
index 9b6f9de..1df9e03 100644
--- a/src/xkbcomp/compat.c
+++ b/src/xkbcomp/compat.c
@@ -86,6 +86,7 @@ typedef struct {
 typedef struct {
     char *name;
     int errorCount;
+    unsigned int include_depth;
     SymInterpInfo default_interp;
     darray(SymInterpInfo) interps;
     LedInfo default_led;
@@ -148,10 +149,12 @@ ReportLedNotArray(CompatInfo *info, LedInfo *ledi, const char *field)
 
 static void
 InitCompatInfo(CompatInfo *info, struct xkb_context *ctx,
+               unsigned int include_depth,
                ActionsInfo *actions, const struct xkb_mod_set *mods)
 {
     memset(info, 0, sizeof(*info));
     info->ctx = ctx;
+    info->include_depth = include_depth;
     info->actions = actions;
     info->mods = *mods;
     info->default_interp.merge = MERGE_OVERRIDE;
@@ -430,7 +433,13 @@ HandleIncludeCompatMap(CompatInfo *info, IncludeStmt *include)
 {
     CompatInfo included;
 
-    InitCompatInfo(&included, info->ctx, info->actions, &info->mods);
+    if (ExceedsIncludeMaxDepth(info->ctx, info->include_depth)) {
+        info->errorCount += 10;
+        return false;
+    }
+
+    InitCompatInfo(&included, info->ctx, 0 /* unused */,
+                   info->actions, &info->mods);
     included.name = include->stmt;
     include->stmt = NULL;
 
@@ -445,7 +454,8 @@ HandleIncludeCompatMap(CompatInfo *info, IncludeStmt *include)
             return false;
         }
 
-        InitCompatInfo(&next_incl, info->ctx, info->actions, &included.mods);
+        InitCompatInfo(&next_incl, info->ctx, info->include_depth + 1,
+                       info->actions, &included.mods);
         next_incl.default_interp = info->default_interp;
         next_incl.default_interp.merge = stmt->merge;
         next_incl.default_led = info->default_led;
@@ -914,7 +924,7 @@ CompileCompatMap(XkbFile *file, struct xkb_keymap *keymap,
     if (!actions)
         return false;
 
-    InitCompatInfo(&info, keymap->ctx, actions, &keymap->mods);
+    InitCompatInfo(&info, keymap->ctx, 0, actions, &keymap->mods);
     info.default_interp.merge = merge;
     info.default_led.merge = merge;
 
diff --git a/src/xkbcomp/include.c b/src/xkbcomp/include.c
index 1fa2153..31df8d2 100644
--- a/src/xkbcomp/include.c
+++ b/src/xkbcomp/include.c
@@ -286,6 +286,20 @@ out:
     return file;
 }
 
+bool
+ExceedsIncludeMaxDepth(struct xkb_context *ctx, unsigned int include_depth)
+{
+    if (include_depth >= INCLUDE_MAX_DEPTH) {
+        log_err(ctx,
+                XKB_ERROR_RECURSIVE_INCLUDE,
+                "Exceeded include depth threshold (%d)",
+                INCLUDE_MAX_DEPTH);
+        return true;
+    } else {
+        return false;
+    }
+}
+
 XkbFile *
 ProcessIncludeFile(struct xkb_context *ctx, IncludeStmt *stmt,
                    enum xkb_file_type file_type)
@@ -334,7 +348,5 @@ ProcessIncludeFile(struct xkb_context *ctx, IncludeStmt *stmt,
                     stmt->file);
     }
 
-    /* FIXME: we have to check recursive includes here (or somewhere) */
-
     return xkb_file;
 }
diff --git a/src/xkbcomp/include.h b/src/xkbcomp/include.h
index 8f360e3..5a5d331 100644
--- a/src/xkbcomp/include.h
+++ b/src/xkbcomp/include.h
@@ -27,6 +27,9 @@
 #ifndef XKBCOMP_INCLUDE_H
 #define XKBCOMP_INCLUDE_H
 
+/* Reasonable threshold, with plenty of margin for keymaps in the wild */
+#define INCLUDE_MAX_DEPTH 15
+
 bool
 ParseIncludeMap(char **str_inout, char **file_rtrn, char **map_rtrn,
                 char *nextop_rtrn, char **extra_data);
@@ -36,6 +39,9 @@ FindFileInXkbPath(struct xkb_context *ctx, const char *name,
                   enum xkb_file_type type, char **pathRtrn,
                   unsigned int *offset);
 
+bool
+ExceedsIncludeMaxDepth(struct xkb_context *ctx, unsigned int include_depth);
+
 XkbFile *
 ProcessIncludeFile(struct xkb_context *ctx, IncludeStmt *stmt,
                    enum xkb_file_type file_type);
diff --git a/src/xkbcomp/keycodes.c b/src/xkbcomp/keycodes.c
index 91471ea..700cd1c 100644
--- a/src/xkbcomp/keycodes.c
+++ b/src/xkbcomp/keycodes.c
@@ -47,6 +47,7 @@ typedef struct {
 typedef struct {
     char *name;
     int errorCount;
+    unsigned int include_depth;
 
     xkb_keycode_t min_key_code;
     xkb_keycode_t max_key_code;
@@ -155,10 +156,12 @@ ClearKeyNamesInfo(KeyNamesInfo *info)
 }
 
 static void
-InitKeyNamesInfo(KeyNamesInfo *info, struct xkb_context *ctx)
+InitKeyNamesInfo(KeyNamesInfo *info, struct xkb_context *ctx,
+                 unsigned int include_depth)
 {
     memset(info, 0, sizeof(*info));
     info->ctx = ctx;
+    info->include_depth = include_depth;
     info->min_key_code = XKB_KEYCODE_INVALID;
 #if XKB_KEYCODE_INVALID < XKB_KEYCODE_MAX
 #error "Hey, you can't be changing stuff like that."
@@ -339,7 +342,12 @@ HandleIncludeKeycodes(KeyNamesInfo *info, IncludeStmt *include)
 {
     KeyNamesInfo included;
 
-    InitKeyNamesInfo(&included, info->ctx);
+    if (ExceedsIncludeMaxDepth(info->ctx, info->include_depth)) {
+        info->errorCount += 10;
+        return false;
+    }
+
+    InitKeyNamesInfo(&included, info->ctx, 0 /* unused */);
     included.name = include->stmt;
     include->stmt = NULL;
 
@@ -354,7 +362,7 @@ HandleIncludeKeycodes(KeyNamesInfo *info, IncludeStmt *include)
             return false;
         }
 
-        InitKeyNamesInfo(&next_incl, info->ctx);
+        InitKeyNamesInfo(&next_incl, info->ctx, info->include_depth + 1);
 
         HandleKeycodesFile(&next_incl, file, MERGE_OVERRIDE);
 
@@ -662,7 +670,7 @@ CompileKeycodes(XkbFile *file, struct xkb_keymap *keymap,
 {
     KeyNamesInfo info;
 
-    InitKeyNamesInfo(&info, keymap->ctx);
+    InitKeyNamesInfo(&info, keymap->ctx, 0);
 
     HandleKeycodesFile(&info, file, merge);
     if (info.errorCount != 0)
diff --git a/src/xkbcomp/symbols.c b/src/xkbcomp/symbols.c
index 20eebeb..0c4fbeb 100644
--- a/src/xkbcomp/symbols.c
+++ b/src/xkbcomp/symbols.c
@@ -175,6 +175,7 @@ typedef struct {
 typedef struct {
     char *name;         /* e.g. pc+us+inet(evdev) */
     int errorCount;
+    unsigned int include_depth;
     enum merge_mode merge;
     xkb_layout_index_t explicit_group;
     darray(KeyInfo) keys;
@@ -191,10 +192,12 @@ typedef struct {
 
 static void
 InitSymbolsInfo(SymbolsInfo *info, const struct xkb_keymap *keymap,
+                unsigned int include_depth,
                 ActionsInfo *actions, const struct xkb_mod_set *mods)
 {
     memset(info, 0, sizeof(*info));
     info->ctx = keymap->ctx;
+    info->include_depth = include_depth;
     info->keymap = keymap;
     info->merge = MERGE_OVERRIDE;
     InitKeyInfo(keymap->ctx, &info->default_key);
@@ -569,7 +572,13 @@ HandleIncludeSymbols(SymbolsInfo *info, IncludeStmt *include)
 {
     SymbolsInfo included;
 
-    InitSymbolsInfo(&included, info->keymap, info->actions, &info->mods);
+    if (ExceedsIncludeMaxDepth(info->ctx, info->include_depth)) {
+        info->errorCount += 10;
+        return false;
+    }
+
+    InitSymbolsInfo(&included, info->keymap, 0 /* unused */,
+                    info->actions, &info->mods);
     included.name = include->stmt;
     include->stmt = NULL;
 
@@ -584,8 +593,8 @@ HandleIncludeSymbols(SymbolsInfo *info, IncludeStmt *include)
             return false;
         }
 
-        InitSymbolsInfo(&next_incl, info->keymap, info->actions,
-                        &included.mods);
+        InitSymbolsInfo(&next_incl, info->keymap, info->include_depth + 1,
+                        info->actions, &included.mods);
         if (stmt->modifier) {
             next_incl.explicit_group = atoi(stmt->modifier) - 1;
             if (next_incl.explicit_group >= XKB_MAX_GROUPS) {
@@ -1638,7 +1647,7 @@ CompileSymbols(XkbFile *file, struct xkb_keymap *keymap,
     if (!actions)
         return false;
 
-    InitSymbolsInfo(&info, keymap, actions, &keymap->mods);
+    InitSymbolsInfo(&info, keymap, 0, actions, &keymap->mods);
     info.default_key.merge = merge;
 
     HandleSymbolsFile(&info, file, merge);
diff --git a/src/xkbcomp/types.c b/src/xkbcomp/types.c
index 183aa50..f22c9ef 100644
--- a/src/xkbcomp/types.c
+++ b/src/xkbcomp/types.c
@@ -53,6 +53,7 @@ typedef struct {
 typedef struct {
     char *name;
     int errorCount;
+    unsigned int include_depth;
 
     darray(KeyTypeInfo) types;
     struct xkb_mod_set mods;
@@ -100,10 +101,12 @@ ReportTypeBadType(KeyTypesInfo *info, xkb_message_code_t code,
 
 static void
 InitKeyTypesInfo(KeyTypesInfo *info, struct xkb_context *ctx,
+                 unsigned int include_depth,
                  const struct xkb_mod_set *mods)
 {
     memset(info, 0, sizeof(*info));
     info->ctx = ctx;
+    info->include_depth = include_depth;
     info->mods = *mods;
 }
 
@@ -219,7 +222,12 @@ HandleIncludeKeyTypes(KeyTypesInfo *info, IncludeStmt *include)
 {
     KeyTypesInfo included;
 
-    InitKeyTypesInfo(&included, info->ctx, &info->mods);
+    if (ExceedsIncludeMaxDepth(info->ctx, info->include_depth)) {
+        info->errorCount += 10;
+        return false;
+    }
+
+    InitKeyTypesInfo(&included, info->ctx, 0 /* unused */, &info->mods);
     included.name = include->stmt;
     include->stmt = NULL;
 
@@ -234,7 +242,8 @@ HandleIncludeKeyTypes(KeyTypesInfo *info, IncludeStmt *include)
             return false;
         }
 
-        InitKeyTypesInfo(&next_incl, info->ctx, &included.mods);
+        InitKeyTypesInfo(&next_incl, info->ctx, info->include_depth + 1,
+                         &included.mods);
 
         HandleKeyTypesFile(&next_incl, file, stmt->merge);
 
@@ -754,7 +763,7 @@ CompileKeyTypes(XkbFile *file, struct xkb_keymap *keymap,
 {
     KeyTypesInfo info;
 
-    InitKeyTypesInfo(&info, keymap->ctx, &keymap->mods);
+    InitKeyTypesInfo(&info, keymap->ctx, 0, &keymap->mods);
 
     HandleKeyTypesFile(&info, file, merge);
     if (info.errorCount != 0)
diff --git a/test/buffercomp.c b/test/buffercomp.c
index 091a876..f111763 100644
--- a/test/buffercomp.c
+++ b/test/buffercomp.c
@@ -84,6 +84,88 @@ test_encodings(struct xkb_context *ctx)
     return true;
 }
 
+static void
+test_recursive(void)
+{
+    struct xkb_context *ctx = test_get_context(0);
+    struct xkb_keymap *keymap;
+
+    assert(ctx);
+
+    const char* const keymaps[] = {
+        /* Recursive keycodes */
+        "Keycodes: recursive",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev+recursive\" };"
+        "  xkb_types { include \"complete\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        "Keycodes: recursive(bar)",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev+recursive(bar)\" };"
+        "  xkb_types { include \"complete\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        /* Recursive key types */
+        "Key types: recursive",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"recursive\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        "Key types: recursive(bar)",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"recursive(bar)\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        /* Recursive compat */
+        "Compat: recursive",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"recursive\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        "Compat: recursive(bar)",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"complete\" };"
+        "  xkb_compat { include \"recursive(bar)\" };"
+        "  xkb_symbols { include \"pc\" };"
+        "};",
+        /* Recursive symbols */
+        "Symbols: recursive",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"complete\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"recursive\" };"
+        "};",
+        "Symbols: recursive(bar)",
+        "xkb_keymap {"
+        "  xkb_keycodes { include \"evdev\" };"
+        "  xkb_types { include \"complete\" };"
+        "  xkb_compat { include \"complete\" };"
+        "  xkb_symbols { include \"recursive(bar)\" };"
+        // "};"
+    };
+
+    int len = sizeof(keymaps) / sizeof(keymaps[0]);
+
+    for (int k = 0; k < len; k++) {
+        fprintf(stderr, "*** Recursive test: %s ***\n", keymaps[k++]);
+        keymap = test_compile_buffer(ctx, keymaps[k], strlen(keymaps[k]));
+        assert(!keymap);
+    }
+
+    xkb_context_unref(ctx);
+}
+
 int
 main(int argc, char *argv[])
 {
@@ -147,5 +229,7 @@ main(int argc, char *argv[])
 
     xkb_context_unref(ctx);
 
+    test_recursive();
+
     return 0;
 }
diff --git a/test/data/compat/recursive b/test/data/compat/recursive
new file mode 100644
index 0000000..3273ead
--- /dev/null
+++ b/test/data/compat/recursive
@@ -0,0 +1,12 @@
+default
+xkb_compatibility "foo" {
+    include "recursive"
+};
+
+xkb_compatibility "bar" {
+    include "recursive(baz)"
+};
+
+xkb_compatibility "baz" {
+    include "recursive(bar)"
+};
diff --git a/test/data/keycodes/recursive b/test/data/keycodes/recursive
new file mode 100644
index 0000000..6711a60
--- /dev/null
+++ b/test/data/keycodes/recursive
@@ -0,0 +1,15 @@
+default
+xkb_keycodes "foo" {
+    include "recursive"
+    <FOO> = 0x100000;
+};
+
+xkb_keycodes "bar" {
+    include "recursive(baz)"
+    <BAR> = 0x100001;
+};
+
+xkb_keycodes "baz" {
+    include "recursive(bar)"
+    <BAZ> = 0x100002;
+};
diff --git a/test/data/symbols/recursive b/test/data/symbols/recursive
new file mode 100644
index 0000000..2a9ad63
--- /dev/null
+++ b/test/data/symbols/recursive
@@ -0,0 +1,12 @@
+default
+xkb_symbols "foo" {
+    include "recursive"
+};
+
+xkb_symbols "bar" {
+    include "recursive(baz)"
+};
+
+xkb_symbols "baz" {
+    include "recursive(bar)"
+};
diff --git a/test/data/types/recursive b/test/data/types/recursive
new file mode 100644
index 0000000..4b75a34
--- /dev/null
+++ b/test/data/types/recursive
@@ -0,0 +1,27 @@
+default
+xkb_types "foo" {
+    type "FOO" {
+        modifiers = None;
+        map[None] = Level1;
+        level_name[Level1]= "Any";
+    };
+    include "recursive"
+};
+
+xkb_types "bar" {
+    type "BAR" {
+        modifiers = None;
+        map[None] = Level1;
+        level_name[Level1]= "Any";
+    };
+    include "recursive(baz)"
+};
+
+xkb_types "baz" {
+    type "BAZ" {
+        modifiers = None;
+        map[None] = Level1;
+        level_name[Level1]= "Any";
+    };
+    include "recursive(bar)"
+};
diff --git a/tools/messages.c b/tools/messages.c
index a0ffd95..ad819a5 100644
--- a/tools/messages.c
+++ b/tools/messages.c
@@ -63,6 +63,7 @@ static const struct xkb_message_entry xkb_messages[] = {
     {XKB_ERROR_INCLUDED_FILE_NOT_FOUND, "Included file not found"},
     {XKB_ERROR_UNKNOWN_OPERATOR, "Unknown operator"},
     {XKB_WARNING_DUPLICATE_ENTRY, "Duplicate entry"},
+    {XKB_ERROR_RECURSIVE_INCLUDE, "Recursive include"},
     {XKB_WARNING_CONFLICTING_KEY_TYPE_DEFINITIONS, "Conflicting key type definitions"},
     {XKB_ERROR_WRONG_SCOPE, "Wrong scope"},
     {XKB_WARNING_MISSING_DEFAULT_SECTION, "Missing default section"},