Reduce tap dance memory usage, move state out of data (#25415)

* Use less tap dance memory.

Use dynamically allocated sparse array for tap dance state, dynamically allocate tap dance state when needed and free it when the tap dance is done.

* new approach

* Use null, check for null

* Reformat with docker

* Use uint8 with idx rather than uint16 with keycode in state

* fix accidental change

* reformat

* Add null check

* add documentation tip suggested by tzarc

* Only allow tap dance state allocation on key down, not on key up

Co-authored-by: Sergey Vlasov <sigprof@gmail.com>

* Only allow tap dance allocation on key down, not on key up

Co-authored-by: Sergey Vlasov <sigprof@gmail.com>

* add user action required section

---------

Co-authored-by: Sergey Vlasov <sigprof@gmail.com>

5 files changed, 152 insertions, 44 deletions

diff --git a/docs/ChangeLog/20250831/pr25415.md b/docs/ChangeLog/20250831/pr25415.md
new file mode 100644
index 0000000000..54eb8c737e
--- /dev/null
+++ b/docs/ChangeLog/20250831/pr25415.md
@@ -0,0 +1,47 @@
+# Tap dance state removed from `tap_dance_action_t`
+
+The tap dance state has been separated from the action structure. Custom tap dance functions now receive the state as a separate parameter instead of accessing it through `action->state`.
+
+## User Action Required
+
+If your keymap uses custom tap dance functions that access the tap dance state, you need to update your code.
+
+ - You can't use `action->state`. Instead you need to call `tap_dance_state_t *tap_dance_get_state(uint8_t tap_dance_idx)` to get the state.
+ - You now get a pointer to the state, so use `->` notation rather than `.` notation to get fields from it.
+
+### Before:
+```c
+bool process_record_user(uint16_t keycode, keyrecord_t *record) {
+    tap_dance_action_t *action;
+
+    switch (keycode) {
+        case TD(CT_CLN):
+            action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(keycode));
+            if (!record->event.pressed && action->state.count && !action->state.finished) {
+                tap_dance_tap_hold_t *tap_hold = (tap_dance_tap_hold_t *)action->user_data;
+                tap_code16(tap_hold->tap);
+            }
+
+    }
+    return true;
+}
+```
+
+### After:
+```c
+bool process_record_user(uint16_t keycode, keyrecord_t *record) {
+    tap_dance_action_t *action;
+    tap_dance_state_t* state;
+
+    switch (keycode) {
+        case TD(CT_CLN):
+            action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(keycode));
+            state = tap_dance_get_state(QK_TAP_DANCE_GET_INDEX(keycode));
+            if (!record->event.pressed && state != NULL && state->count && !state->finished) {
+                tap_dance_tap_hold_t *tap_hold = (tap_dance_tap_hold_t *)action->user_data;
+                tap_code16(tap_hold->tap);
+            }
+    }
+    return true;
+}
+```
diff --git a/docs/features/tap_dance.md b/docs/features/tap_dance.md
index d533e41aaa..688241a16b 100644
--- a/docs/features/tap_dance.md
+++ b/docs/features/tap_dance.md
@@ -40,6 +40,10 @@ Similar to the first option, the second and third option are good for simple lay
 
 For more complicated cases, like blink the LEDs, fiddle with the backlighting, and so on, use the fourth or fifth option. Examples of each are listed below.
 
+::: tip 
+If too many tap dances are active at the same time, later ones won't have any effect. You need to increase `TAP_DANCE_MAX_SIMULTANEOUS` by adding `#define TAP_DANCE_MAX_SIMULTANEOUS 5` (or higher) to your keymap's `config.h` file if you expect that users may hold down many tap dance keys simultaneously. By default, only 3 tap dance keys can be used together at the same time.
+:::
+
 ## Implementation Details {#implementation}
 
 Well, that's the bulk of it! You should now be able to work through the examples below, and to develop your own Tap Dance functionality. But if you want a deeper understanding of what's going on behind the scenes, then read on for the explanation of how it all works!
@@ -209,11 +213,13 @@ tap_dance_action_t tap_dance_actions[] = {
 
 bool process_record_user(uint16_t keycode, keyrecord_t *record) {
     tap_dance_action_t *action;
+    tap_dance_state_t* state;
 
     switch (keycode) {
-        case TD(CT_CLN): // list all tap dance keycodes with tap-hold configurations
-            action = &tap_dance_actions[QK_TAP_DANCE_GET_INDEX(keycode)];
-            if (!record->event.pressed && action->state.count && !action->state.finished) {
+        case TD(CT_CLN):
+            action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(keycode));
+            state = tap_dance_get_state(QK_TAP_DANCE_GET_INDEX(keycode));
+            if (!record->event.pressed && state != NULL && state->count && !state->finished) {
                 tap_dance_tap_hold_t *tap_hold = (tap_dance_tap_hold_t *)action->user_data;
                 tap_code16(tap_hold->tap);
             }
diff --git a/quantum/process_keycode/process_tap_dance.c b/quantum/process_keycode/process_tap_dance.c
index 11df62763d..36a94d8d28 100644
--- a/quantum/process_keycode/process_tap_dance.c
+++ b/quantum/process_keycode/process_tap_dance.c
@@ -24,8 +24,46 @@
 #include "keymap_introspection.h"
 
 static uint16_t active_td;
+
+#ifndef TAP_DANCE_MAX_SIMULTANEOUS
+#    define TAP_DANCE_MAX_SIMULTANEOUS 3
+#endif
+
+static tap_dance_state_t tap_dance_states[TAP_DANCE_MAX_SIMULTANEOUS];
+
 static uint16_t last_tap_time;
 
+static tap_dance_state_t *tap_dance_get_or_allocate_state(uint8_t tap_dance_idx, bool allocate) {
+    uint8_t i;
+    if (tap_dance_idx >= tap_dance_count()) {
+        return NULL;
+    }
+    // Search for a state already used for this keycode
+    for (i = 0; i < TAP_DANCE_MAX_SIMULTANEOUS; i++) {
+        if (tap_dance_states[i].in_use && tap_dance_states[i].index == tap_dance_idx) {
+            return &tap_dance_states[i];
+        }
+    }
+    // No existing state found; bail out if new state allocation is not allowed
+    if (!allocate) {
+        return NULL;
+    }
+    // Search for the first available state
+    for (i = 0; i < TAP_DANCE_MAX_SIMULTANEOUS; i++) {
+        if (!tap_dance_states[i].in_use) {
+            tap_dance_states[i].index  = tap_dance_idx;
+            tap_dance_states[i].in_use = true;
+            return &tap_dance_states[i];
+        }
+    }
+    // No states are available, tap dance won't happen
+    return NULL;
+}
+
+tap_dance_state_t *tap_dance_get_state(uint8_t tap_dance_idx) {
+    return tap_dance_get_or_allocate_state(tap_dance_idx, false);
+}
+
 void tap_dance_pair_on_each_tap(tap_dance_state_t *state, void *user_data) {
     tap_dance_pair_t *pair = (tap_dance_pair_t *)user_data;
 
@@ -86,58 +124,64 @@ static inline void _process_tap_dance_action_fn(tap_dance_state_t *state, void *
     }
 }
 
-static inline void process_tap_dance_action_on_each_tap(tap_dance_action_t *action) {
-    action->state.count++;
-    action->state.weak_mods = get_mods();
-    action->state.weak_mods |= get_weak_mods();
+static inline void process_tap_dance_action_on_each_tap(tap_dance_action_t *action, tap_dance_state_t *state) {
+    state->count++;
+    state->weak_mods = get_mods();
+    state->weak_mods |= get_weak_mods();
 #ifndef NO_ACTION_ONESHOT
-    action->state.oneshot_mods = get_oneshot_mods();
+    state->oneshot_mods = get_oneshot_mods();
 #endif
-    _process_tap_dance_action_fn(&action->state, action->user_data, action->fn.on_each_tap);
+    _process_tap_dance_action_fn(state, action->user_data, action->fn.on_each_tap);
 }
 
-static inline void process_tap_dance_action_on_each_release(tap_dance_action_t *action) {
-    _process_tap_dance_action_fn(&action->state, action->user_data, action->fn.on_each_release);
+static inline void process_tap_dance_action_on_each_release(tap_dance_action_t *action, tap_dance_state_t *state) {
+    _process_tap_dance_action_fn(state, action->user_data, action->fn.on_each_release);
 }
 
-static inline void process_tap_dance_action_on_reset(tap_dance_action_t *action) {
-    _process_tap_dance_action_fn(&action->state, action->user_data, action->fn.on_reset);
-    del_weak_mods(action->state.weak_mods);
+static inline void process_tap_dance_action_on_reset(tap_dance_action_t *action, tap_dance_state_t *state) {
+    _process_tap_dance_action_fn(state, action->user_data, action->fn.on_reset);
+    del_weak_mods(state->weak_mods);
 #ifndef NO_ACTION_ONESHOT
-    del_mods(action->state.oneshot_mods);
+    del_mods(state->oneshot_mods);
 #endif
     send_keyboard_report();
-    action->state = (const tap_dance_state_t){0};
+    // Clear the tap dance state and mark it as unused
+    memset(state, 0, sizeof(tap_dance_state_t));
 }
 
-static inline void process_tap_dance_action_on_dance_finished(tap_dance_action_t *action) {
-    if (!action->state.finished) {
-        action->state.finished = true;
-        add_weak_mods(action->state.weak_mods);
+static inline void process_tap_dance_action_on_dance_finished(tap_dance_action_t *action, tap_dance_state_t *state) {
+    if (!state->finished) {
+        state->finished = true;
+        add_weak_mods(state->weak_mods);
 #ifndef NO_ACTION_ONESHOT
-        add_mods(action->state.oneshot_mods);
+        add_mods(state->oneshot_mods);
 #endif
         send_keyboard_report();
-        _process_tap_dance_action_fn(&action->state, action->user_data, action->fn.on_dance_finished);
+        _process_tap_dance_action_fn(state, action->user_data, action->fn.on_dance_finished);
     }
     active_td = 0;
-    if (!action->state.pressed) {
+    if (!state->pressed) {
         // There will not be a key release event, so reset now.
-        process_tap_dance_action_on_reset(action);
+        process_tap_dance_action_on_reset(action, state);
     }
 }
 
 bool preprocess_tap_dance(uint16_t keycode, keyrecord_t *record) {
     tap_dance_action_t *action;
+    tap_dance_state_t * state;
 
     if (!record->event.pressed) return false;
 
     if (!active_td || keycode == active_td) return false;
 
-    action                             = tap_dance_get(QK_TAP_DANCE_GET_INDEX(active_td));
-    action->state.interrupted          = true;
-    action->state.interrupting_keycode = keycode;
-    process_tap_dance_action_on_dance_finished(action);
+    action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(active_td));
+    state  = tap_dance_get_state(QK_TAP_DANCE_GET_INDEX(active_td));
+    if (state == NULL) {
+        return false;
+    }
+    state->interrupted          = true;
+    state->interrupting_keycode = keycode;
+    process_tap_dance_action_on_dance_finished(action, state);
 
     // Tap dance actions can leave some weak mods active (e.g., if the tap dance is mapped to a keycode with
     // modifiers), but these weak mods should not affect the keypress which interrupted the tap dance.
@@ -151,8 +195,9 @@ bool preprocess_tap_dance(uint16_t keycode, keyrecord_t *record) {
 }
 
 bool process_tap_dance(uint16_t keycode, keyrecord_t *record) {
-    int                 td_index;
+    uint8_t             td_index;
     tap_dance_action_t *action;
+    tap_dance_state_t * state;
 
     switch (keycode) {
         case QK_TAP_DANCE ... QK_TAP_DANCE_MAX:
@@ -161,16 +206,19 @@ bool process_tap_dance(uint16_t keycode, keyrecord_t *record) {
                 return false;
             }
             action = tap_dance_get(td_index);
-
-            action->state.pressed = record->event.pressed;
+            state  = tap_dance_get_or_allocate_state(td_index, record->event.pressed);
+            if (state == NULL) {
+                return false;
+            }
+            state->pressed = record->event.pressed;
             if (record->event.pressed) {
                 last_tap_time = timer_read();
-                process_tap_dance_action_on_each_tap(action);
-                active_td = action->state.finished ? 0 : keycode;
+                process_tap_dance_action_on_each_tap(action, state);
+                active_td = state->finished ? 0 : keycode;
             } else {
-                process_tap_dance_action_on_each_release(action);
-                if (action->state.finished) {
-                    process_tap_dance_action_on_reset(action);
+                process_tap_dance_action_on_each_release(action, state);
+                if (state->finished) {
+                    process_tap_dance_action_on_reset(action, state);
                     if (active_td == keycode) {
                         active_td = 0;
                     }
@@ -185,16 +233,18 @@ bool process_tap_dance(uint16_t keycode, keyrecord_t *record) {
 
 void tap_dance_task(void) {
     tap_dance_action_t *action;
+    tap_dance_state_t * state;
 
     if (!active_td || timer_elapsed(last_tap_time) <= GET_TAPPING_TERM(active_td, &(keyrecord_t){})) return;
 
     action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(active_td));
-    if (!action->state.interrupted) {
-        process_tap_dance_action_on_dance_finished(action);
+    state  = tap_dance_get_state(QK_TAP_DANCE_GET_INDEX(active_td));
+    if (state != NULL && !state->interrupted) {
+        process_tap_dance_action_on_dance_finished(action, state);
     }
 }
 
 void reset_tap_dance(tap_dance_state_t *state) {
     active_td = 0;
-    process_tap_dance_action_on_reset((tap_dance_action_t *)state);
+    process_tap_dance_action_on_reset(tap_dance_get(state->index), state);
 }
diff --git a/quantum/process_keycode/process_tap_dance.h b/quantum/process_keycode/process_tap_dance.h
index 5cccbdf439..5a972cee5a 100644
--- a/quantum/process_keycode/process_tap_dance.h
+++ b/quantum/process_keycode/process_tap_dance.h
@@ -28,15 +28,16 @@ typedef struct {
 #ifndef NO_ACTION_ONESHOT
     uint8_t oneshot_mods;
 #endif
-    bool pressed : 1;
-    bool finished : 1;
-    bool interrupted : 1;
+    bool    pressed : 1;
+    bool    finished : 1;
+    bool    interrupted : 1;
+    bool    in_use : 1;
+    uint8_t index;
 } tap_dance_state_t;
 
 typedef void (*tap_dance_user_fn_t)(tap_dance_state_t *state, void *user_data);
 
 typedef struct tap_dance_action_t {
-    tap_dance_state_t state;
     struct {
         tap_dance_user_fn_t on_each_tap;
         tap_dance_user_fn_t on_dance_finished;
@@ -80,6 +81,8 @@ typedef struct {
 
 void reset_tap_dance(tap_dance_state_t *state);
 
+tap_dance_state_t *tap_dance_get_state(uint8_t tap_dance_idx);
+
 /* To be used internally */
 
 bool preprocess_tap_dance(uint16_t keycode, keyrecord_t *record);
diff --git a/tests/tap_dance/examples.c b/tests/tap_dance/examples.c
index 4b6bdb2090..6aaf008232 100644
--- a/tests/tap_dance/examples.c
+++ b/tests/tap_dance/examples.c
@@ -81,11 +81,13 @@ typedef struct {
 
 bool process_record_user(uint16_t keycode, keyrecord_t *record) {
     tap_dance_action_t *action;
+    tap_dance_state_t* state;
 
     switch (keycode) {
         case TD(CT_CLN):
             action = tap_dance_get(QK_TAP_DANCE_GET_INDEX(keycode));
-            if (!record->event.pressed && action->state.count && !action->state.finished) {
+            state = tap_dance_get_state(QK_TAP_DANCE_GET_INDEX(keycode));
+            if (!record->event.pressed && state != NULL && state->count && !state->finished) {
                 tap_dance_tap_hold_t *tap_hold = (tap_dance_tap_hold_t *)action->user_data;
                 tap_code16(tap_hold->tap);
             }