main: Start modeling Nvim as pushdown automaton

From a very high level point of view, Vim/Nvim can be described as state
machines following these instructions in a loop:

- Read user input
- Peform some action. The action is determined by the current state and can
  switch states.
- Possibly display some feedback to the user.

This is not immediately visible because these instructions spread across dozens
of nested loops and function calls, making it very hard to modify the state
machine(to support more event types, for example).

So far, the approach Nvim has taken to allow more events is this:

- At the very core function that blocks for input, poll for arbitrary events.
- If the event received from the OS is user input, just return it normally to
  the callers.
- If the event is not direct result of user input(possibly a vimscript function
  call coming from a msgpack-rpc socket or a job control callback), return a
  special key code(`K_EVENT`) that is handled by callers where it is safer to
  perform arbitrary actions.

One problem with this approach is that the `K_EVENT` signal is being sent across
multiple states that may be unaware of it. This was partially fixed with the
`input_enable_events`/`input_disable_events` functions, which were added as a
mechanism that the upper layers can use to tell the core input functions that it
is ready to accept `K_EVENT`.

Another problem is that the mapping engine is implemented in getchar.c
which is called from every state, but the mapping engine is not aware of
`K_EVENT` so events can break mappings.

While it is theoretically possible to modify getchar.c to make it aware of
`K_EVENT`, this commit fixes the problem with a different approach: Model Nvim
as a pushdown automaton(https://en.wikipedia.org/wiki/Pushdown_automaton). This
design has many advantages which include:

- Decoupling the event loop from the states reponsible for handling events.
- Better control of state transition with less dependency on global variable
  hacks(eg: 'restart_edit' global variable).
- Easier removal of global variables and function splitting. That is because
  many variables are for state-specific information, and probably ended up being
  global to simplify communication between functions, which we fix by storing
  state-specific information in specialized structures.

The final goal is to let Nvim have a single top-level event loop represented by
the following pseudo-code:

```
while not quitting
  let event = read_event
  current_state(event)
  update_screen()
```

This closely mirrors the state machine description above and makes it easier to
understand, extend and debug the program.

Note that while the pseudo code suggests an explicit stack of states that
doesn't rely on return addresses(as suggested by the principles of
automata-based programming:
https://en.wikipedia.org/wiki/Automata-based_programming), for now we'll use the
call stack as a structure to manage state transitioning as it would be very
difficult to refactor Nvim to use an explicit stack of states, and the benefits
would be small.

While this change may seem like an endless amount of work, it is possible to
do it incrementally as was shown in the previous commits. The general procedure
is:

1- Find a blocking `vgetc()`(or derivatives) call. This call represents an
   implicit state of the program.

2- Split the code before and after the `vgetc()` call into functions that match
   the signature of `state_check_callback` and `state_execute_callback.
   Only `state_execute_callback` is required.

3- Create a `VimState` "subclass" and a initializer function that sets the
   function pointers and performs any other required initialization steps. If
   the state has no local variables, just use `VimState` without subclassing.

4- Instead of calling the original function containing the `vgetc()`,
   initialize a stack-allocated `VimState` subclass, then call `state_enter` to
   begin processing events in the state.

5- The check/execute callbacks can return 1 to continue normally, 0 to break the
   loop or -1 to skip to the next iteration. These callbacks contain code that
   execute before and after the old `vgetc()` call.

The functions created in step 2 may contain other `vgetc()` calls. These
represent implicit sub-states of the current state, but it is fine to remove
them later in smaller steps since we didn't break compatibility with existing
code.

4 files changed, 93 insertions, 43 deletions

diff --git a/src/nvim/main.c b/src/nvim/main.c
index 06fd116b86..eb2a1567e7 100644
--- a/src/nvim/main.c
+++ b/src/nvim/main.c
@@ -54,6 +54,7 @@
 #include "nvim/profile.h"
 #include "nvim/quickfix.h"
 #include "nvim/screen.h"
+#include "nvim/state.h"
 #include "nvim/strings.h"
 #include "nvim/syntax.h"
 #include "nvim/ui.h"
diff --git a/src/nvim/normal.c b/src/nvim/normal.c
index 8f08fe2eed..29e82c5e77 100644
--- a/src/nvim/normal.c
+++ b/src/nvim/normal.c
@@ -61,11 +61,13 @@
 #include "nvim/mouse.h"
 #include "nvim/undo.h"
 #include "nvim/window.h"
+#include "nvim/state.h"
 #include "nvim/event/loop.h"
 #include "nvim/os/time.h"
 #include "nvim/os/input.h"
 
 typedef struct normal_state {
+  VimState state;
   linenr_T conceal_old_cursor_line;
   linenr_T conceal_new_cursor_line;
   bool conceal_update_lines;
@@ -98,6 +100,8 @@ static int restart_VIsual_select = 0;
 static inline void normal_state_init(NormalState *s)
 {
   memset(s, 0, sizeof(NormalState));
+  s->state.check = normal_check;
+  s->state.execute = normal_execute;
 }
 
 /*
@@ -455,46 +459,7 @@ void normal_enter(bool cmdwin, bool noexmode)
   state.cmdwin = cmdwin;
   state.noexmode = noexmode;
   state.toplevel = !cmdwin && !noexmode;
-
-  for (;;) {
-    int check_result = normal_check(&state);
-    if (!check_result) {
-      break;
-    } else if (check_result == -1) {
-      continue;
-    }
-
-    int key;
-
-    if (char_avail() || using_script() || input_available()) {
-      // Don't block for events if there's a character already available for
-      // processing. Characters can come from mappings, scripts and other
-      // sources, so this scenario is very common.
-      key = safe_vgetc();
-    } else if (!queue_empty(loop.events)) {
-      // Event was made available after the last queue_process_events call
-      key = K_EVENT;
-    } else {
-      input_enable_events();
-      // Flush screen updates before blocking
-      ui_flush();
-      // Call `os_inchar` directly to block for events or user input without
-      // consuming anything from `input_buffer`(os/input.c) or calling the
-      // mapping engine. If an event was put into the queue, we send K_EVENT
-      // directly.
-      (void)os_inchar(NULL, 0, -1, 0);
-      input_disable_events();
-      key = !queue_empty(loop.events) ? K_EVENT : safe_vgetc();
-    }
-
-    if (key == K_EVENT) {
-      may_sync_undo();
-    }
-
-    if (!normal_execute(&state, key)) {
-      break;
-    }
-  }
+  state_enter(&state.state);
 }
 
 static void normal_prepare(NormalState *s)
@@ -543,8 +508,9 @@ static void normal_prepare(NormalState *s)
   }
 }
 
-static int normal_execute(NormalState *s, int c)
+static int normal_execute(VimState *state, int c)
 {
+  NormalState *s = (NormalState *)state;
   bool ctrl_w = false;                  /* got CTRL-W command */
   int old_col = curwin->w_curswant;
   bool need_flushbuf;                   /* need to call ui_flush() */
@@ -1106,8 +1072,9 @@ normal_end:
 //   1 if the iteration should continue normally
 //   -1 if the iteration should be skipped
 //   0 if the main loop must exit
-static int normal_check(NormalState *s)
+static int normal_check(VimState *state)
 {
+  NormalState *s = (NormalState *)state;
   if (stuff_empty()) {
     did_check_timestamps = false;
 
@@ -7625,6 +7592,6 @@ void normal_cmd(oparg_T *oap, bool toplevel)
   s.toplevel = toplevel;
   s.oa = *oap;
   normal_prepare(&s);
-  (void)normal_execute(&s, safe_vgetc());
+  (void)normal_execute(&s.state, safe_vgetc());
   *oap = s.oa;
 }
diff --git a/src/nvim/state.c b/src/nvim/state.c
new file mode 100644
index 0000000000..b2f3f0bebe
--- /dev/null
+++ b/src/nvim/state.c
@@ -0,0 +1,62 @@
+#include <assert.h>
+
+#include "nvim/lib/kvec.h"
+
+#include "nvim/state.h"
+#include "nvim/vim.h"
+#include "nvim/getchar.h"
+#include "nvim/ui.h"
+#include "nvim/os/input.h"
+
+#ifdef INCLUDE_GENERATED_DECLARATIONS
+# include "state.c.generated.h"
+#endif
+
+
+void state_enter(VimState *s)
+{
+  for (;;) {
+    int check_result = s->check ? s->check(s) : 1;
+
+    if (!check_result) {
+      break;
+    } else if (check_result == -1) {
+      continue;
+    }
+
+    int key;
+
+getkey:
+    if (char_avail() || using_script() || input_available()) {
+      // Don't block for events if there's a character already available for
+      // processing. Characters can come from mappings, scripts and other
+      // sources, so this scenario is very common.
+      key = safe_vgetc();
+    } else if (!queue_empty(loop.events)) {
+      // Event was made available after the last queue_process_events call
+      key = K_EVENT;
+    } else {
+      input_enable_events();
+      // Flush screen updates before blocking
+      ui_flush();
+      // Call `os_inchar` directly to block for events or user input without
+      // consuming anything from `input_buffer`(os/input.c) or calling the
+      // mapping engine. If an event was put into the queue, we send K_EVENT
+      // directly.
+      (void)os_inchar(NULL, 0, -1, 0);
+      input_disable_events();
+      key = !queue_empty(loop.events) ? K_EVENT : safe_vgetc();
+    }
+
+    if (key == K_EVENT) {
+      may_sync_undo();
+    }
+
+    int execute_result = s->execute(s, key);
+    if (!execute_result) {
+      break;
+    } else if (execute_result == -1) {
+      goto getkey;
+    }
+  }
+}
diff --git a/src/nvim/state.h b/src/nvim/state.h
new file mode 100644
index 0000000000..8027514148
--- /dev/null
+++ b/src/nvim/state.h
@@ -0,0 +1,20 @@
+#ifndef NVIM_STATE_H
+#define NVIM_STATE_H
+
+#include <stddef.h>
+
+typedef struct vim_state VimState;
+
+typedef int(*state_check_callback)(VimState *state);
+typedef int(*state_execute_callback)(VimState *state, int key);
+
+struct vim_state {
+  state_check_callback check;
+  state_execute_callback execute;
+};
+
+#ifdef INCLUDE_GENERATED_DECLARATIONS
+# include "state.h.generated.h"
+#endif
+
+#endif  // NVIM_STATE_H