On Fri, Aug 01, 2014 at 10:19:25PM +0200, Markus Teich wrote:
> Silvan Jegen wrote:
> > http://sillymon.ch/data/funcfsm.png
> > (source: http://sillymon.ch/data/funcfsm.dot )
>
> Heyho Silvan,
>
> this seems to be way too complex.
I agree that it is quite complex but it has some merits (I will be
mentioning those at the end).
> > To simplify the states I assume that a count ([0-9]+) can only occur before
> > the movement command (jklhw etc.) and not before the operator (ydc). That
> > means that "d3w" is valid but "3dw" isn't.
>
> What about "5s", "3x" or "10p"? This is just another prefix. In vim if you type
I ignored those but to take these into account you would have to separate
the count state from the move state. You would then get the count and
depending on whether you get "x" or "s" next you would either call count *
"dl" or count * "dl" and then enter insert mode.
> "2d3w" the amounts get multiplied and you delete 6 words.
I did not know that this was possible! :-) Still, I do not think it is
necessary since you can just use "d6w" instead. If people really want
to be able to use both forms we could just rearrange the states in a
way that allows the count state to be visited before the operator and
before the movement/object state (which would be necessary in order to
implement the operators above as well).
> > The fsm_* functions would need to read input to decide on the transitions (i.
> > e. functions to call; to extract the count argument for move(), fsm_move would
> > have to read in a loop). I think maybe passing a function pointer to these
> > functions would make sense. The passed function pointer would then determine
> > whether the next input is read from stdin or a buffer (useful for macros?) or
> > from wherever.
>
> So you have to synchronously wait for input in these functions? o.O
Yes but since a text editor should not be doing much without receiving
a command I think that is okay. Also, nothing in the FSM depends on it
being done in the main thread AFAICT. You can do the FSM processing in its
own thread and do something else in the main thread.
In my approach you still have to read in most of the state functions
which I don't like.
> > I have not written one line of code yet because I am not sure this is the best
> > approach. Do you see issues with this proposal or do you have a better
> > idea/implementation in mind?
>
> I would rather propose a much simpler, but generic FSM/DFA for parsing keyboard
> commands:
>
> http://fs.tum.de/~teichm/sandy_keys.png
I get the impression that we operate at a different level of
abstraction. My graph specifies the function calls that would have to be
done to implement a FSM while yours deals with the distinct states for
the state machine but does not specify which functions are called when
and what information they depend on. Additionally, mine includes visual
and insert modes :-)
> We should implement a global state something like this:
>
> struct action {
> int amount;
> union {
> enum op o;
> enum preop po;
> } cmd;
> union {
> struct {
> int inner;
> enum textobj o;
> } to;
> enum movement mov;
> } m;
> };
>
> text-objects would have a mandatory prefix either 'i' for inner or 'a' for
> outer.
>
> The enum could contain the following values:
> preop: a i o p r s v x
> textobj: w s p " ' ` [ ] { } < > { } t
> movement: b e h j k l n w
> op: c d y
>
> for example resulting in:
> enum op {
> OP_CHANGE = 'c',
> OP_DELETE = 'd',
> OP_YANK = 'y',
> };
>
> Then we could just collect the information through a state dependent function
> table:
>
> int (*q0_transitions[256])(char input) = {
> ['0'] = transition_number,
> …
> [PREOP_PASTE] = transition_preop,
> …
> [MOV_WORD] = transition_mov,
> …
> [OP_CHANGE] = transition_op,
> …
> };
>
> The transition_number(char input) function would just do
> action.amount *= 10;
> action.amount += input - '0';
>
> After we reach an end-state, we have collected all the info in our struct
> action, can execute the apropriate commands (again through a function table),
> reset the action struct and the state to q0.
I assume that you have a function array for each state, correct? So on
each keypress you will have to check which state you are in and then
search for the function in the appropriate function array (by indexing
into the array). Additionally you have to set the global state when
reading input and traversing the FSM.
Let me try to trace through one example. For the input "d3w" we would
Your suggestion (checking global state at every func call):
1. call the transition_op from the q0_transitions array with argument
'd', set global state to q3 and set cmd.op in the action struct
to OP_DELETE.
2. call transition_number in the q3_transitions array which sets the
amount to 3.
3. call transition_mov in the q3_transitions array with argument 'w' which
calls some delete function that acts according to the action struct.
Set global state to q0.
My suggestion (reading input in every function call):
1. call fsm_delete function
2. call fsm_move which reads count in loop
3. call move(3, OBJ_WORD)
4. fsm_move returns to- and from coordinates to fsm_delete
5. call delete(from, to) and return to initial state
> I feel this is much easier to manage and even extend with custom mappings within
> config.h. What do you think?
It looks like a tradeoff to me.
If I understand your proposal correctly you have to check/set global
state at every input and maintain function arrays for every state while
in my approach you have to read input in every state transition function
and have a more complex call hierarchy to maintain. I am not sure which
is better (but I do like the function array idea as well).
BTW, I think it's a really interesting discussion/topic! Further input
is certainly welcome.
Cheers,
Silvan
Received on Sat Aug 02 2014 - 12:52:45 CEST
