kicad-developers team mailing list archive

[Lorenzo Marcantonio <l.marcantonio@xxxxxxxxxxxx>]

On Tue, Aug 13, 2013 at 12:54:10AM -0500, Dick Hollenbeck wrote:

Huge mail, but very interesting...

> I cannot see how coroutines would work in a wx GUI program. Coroutines by definition are
> the same OS thread under a second or more CPU stack region.  So we are talking about one
> thread mimicking multiple.  Or are you using a contorted definition?  No way coroutines
> will work in a wx program IMO.

More or less the reason for which I doubted it works... coroutines in
this case are used to suspend/restart the process to avoid a state
variable in a state machine. The main issue here is what to do when a
coroutine need to exit... *if* these are created in the right
environment you could just dispose of the stack and then return to the
caller (unwinding the last frame would be tricky). There is a whole
theory of continuation-style programming, most of that can't be applied
to C++, since it requires a branched stack (IIRC that's the reason for
the call limitation in python generators)

I think that if:
- Coroutine are created with a 'neutral' stack (i.e. nothing living
  after their return)
- Every event dispatch to the coroutine until a yield or terminate
  occur

It should work without any big trouble (maybe some limitation in what
can be done in the coroutine, but I don't think a lot).

> The goal of the tool event handler should be to cooperatively return as fast as it can,
> since it is being called on the wx event handler thread.  If you cannot process the event
> and cooperatively return as fast as you can, you need a separate wxThread to do on going
> work.  This, at least if you want the user to continue to see quick interactive behaviour.

Well, that's not very different using a coroutine... in fact the old
windows 3.1 application ran as huge coroutines from the OS yielding on
GetMessage (and few other functions). MacOS class was cooperative too,
AFAIK.

Paraphrasing: "the goal of the tool coroutine handler should be to
*yield* as fast as it can, since it is being called on the wx event
handler thread". The key here is that it yields, not return, so it keeps
the whole processing state. All your consideration about a competing
tool thread are correct *but* we have *no thread safety whatsoever* in
kicad so it will be a huge work and source of race conditions.

Also there should be a theorem somewhere stating that all what you can
do with a state machine can be done with a coroutine (and the converse);
it's only a programming convenience (just like you could program kicad
on a Turing machine, yeah:D)

A more realistic stance: what would have to do the tool code that would
need a separate thread? Since it need to provide feedback, he would have
to wait for that thread anyway (making the fork not useful...). IMHO
most performance problems in pcbnew can be solved with better data
structures (like spatial indices as discussed).

> If you were to duplicate the pcbnew behaviours we have now under the new tool
> architecture, your tools would mostly all have one state in them.  The act of changing
> tools would be the main state machine.  You only need more than one state, within the same
> tool, when you plan on doing something different with the same kind of event.  If you
> always intend to do the same thing with any given event type, you do not need more than
> one state in a tool.  The tool can be thought of as a sub-state machine.  The tool change
> is the topmost state machine.

I don't feel the 'tool change' is a transition... otherwise even moving
the cursor would be:D is more like swapping one state machine with
another and aborting the previous one. Your sub-state machine would be
the tool state machine, I agree with that. Track lying use case
(extremely simplified)

S1: pick the start point
S2: drag trace

With a pure state machine that would be like:

S1/mouse move -> update cursor -> S1
S1/click -> validate start position, pin start -> S2
S2/mouse move -> update rubber track -> S2
S2/click -> validate rubber track, pin start -> S2
S2/end track -> validate rubber track -> S1

With a coroutine it would be like (heavily pseudocoded, I'm focusing on
the coroutine view *not* on how event are dispatched in it). Please
correct me if I misunderstood something here

forever {
    while (!start_pinned) {
        event = yield();
        switch (event) { // or some clever dispatch
        case click:
            pin_start();

        case move:
            update_cursor;
        }
    }

    while (!track_done) {
        event = yield;
        switch (event) {
        case click:
            validate_track();
            pin_start();

        case move:
            update_rubber_track

        case end_track:
            validate_track();
            track_done = true;
        }
    }
}

The coroutine better show the tool code flow, the state machine is more
'elegant' in a formal way... I think it all go to personal preference.
In fact in tail-recursive languages FSM are usually implemented with
tail calls (which are optimized to goto) like this:

state_S1()
{
    event = yield();
    switch (event) { // or some clever dispatch
    case click:
        pin_start();
        state_S2();

    case move:
        update_cursor;
        state_S1();
    }
}


state_S2()
{
    event = yield;
    switch (event) {
    case click:
        validate_track();
        pin_start();
        state_S1();

    case move:
        update_rubber_track()
        state_S1();

    case end_track:
        validate_track();
        state_S2();
    }
}

Look! No helper variables and advantages from both the FSM and the
coroutine model:D too bad that in C/C++ this isn't guaranteed to not
blow the stack...  I do this all the time in mcu assembly (the state
change is...  horror... a goto!). Also coroutines in these environments
are usually more prevedible...

> Then in the debugger m_state will always show with its *named* value.  No such joy with a
> member function pointer.  If the enums are all sequential from zero, then the

Why? Doesn't the debugger decode the function pointer? Strange...
I don't often use the debugger except for decoding dumps, so I have no
experience.

>  switch( m_state )
> 
> statement will be translated to an array like jump table by the compiler and this is only
> basically two machine instructions.

Yes but you have to maintain a switch and the associated function...
instead of new_state = ENUM_STATE, using new_state = state_function is
only an indirect call and no enumeration or switch is needed (could be
even a little faster but I think we are counting the clock cycles,
that's not the reason for doing that). Of course it's a personal
preference too, but I'd prefer to write less code :P (exception: some
MCU don't have indirect calls and can't manipulate the return stack, so
you *have* to do a switch; hated it on the PIC16)

> The base tool class could be rigged to duplicate some of the event classification that
> wxWindow::ProcessEvent() does.  This way you can at least get your mouse events and
> keyboard events into to separate virtual functions, and derived tool classes would need to
> override these if they want to do anything tool specific within these categories of
> events.  It could also be a runtime decision as to whether the base tool class does the
> classification and routes mouse events to OnMouseHandler(), or not.  A boolean to the
> constructor could decide yeah or nay at the base tool class.

That would be an effective event filter, yes. Infrastructure could be
built on that, if necessary.

> If you are going to use multiple states in a tool, and a OnMouseHandler(), and a
> OnKeyHandler(), then you would need a switch( m_state ) in each overloaded virtual member
> function.

Or using multiple classes for the different states, someone likes to do
that. In that case the state is not an enum, nor a function but a whole
fscking class pointer! As before, personal preference and how that would
make clear the working dictate the style.

> A quick way to learn more about this is to outfit a wxEvtHandler derived class with event
> printing functions, and simply hook it into a wxFrame in a test program.  If you do not
> handle the event according to the wxEvent protocol (see wxEvent.Skip()) then wx passes
> that event onto the next wxEvtHandler on the stack.
> This may not be necessary

No experience on the wxEvt so can't state a thing:P

> So much of the work is done.   I do think some duplication of wxWindow::ProcessEvent()
> will need to happen in the base class tool.

For the filtering behaviour, I presume... what about wx changing the
event behaviour in the next subrelease? duplication of dependant code is
risky... also since you don't need to queue there isn't much of wx to
not have to rewrite with an independent event system.

> Actually I cannot see where you even have UI ids any more.  Don't you just translate an
> event into a an action call within the tool?

Well, I suppose that the tool select click would need a UI id for the wx
button, but at least all the sub-thingies should not.

> Again, getting me to believe in coroutines for a wxApp will require a brain transplant for me.

Maybe you're just not a coroutine fan:D 

> a thing that we consider really useful and simplifying tool
> > development (a small demo is in pcbnew/tools/selection_tool.cpp in 
> > kicad-gal-orson branch). Is it possible to marry coroutines with the wx 
> > event system? 
> 
> No, not even sensible in a wx program.

Could be done, as I said, usefulness could be limited depending on how
you switch on event in the coroutine.

> wxThread.

Would need massive interlocking to be safe; I'd avoid if possible (never
actually *needed* a thread in my life, of course programming style
and/or application type dictate the need).

> > - Wanted to avoid translating between VECTOR2<>/BOX2<> and 
> > wxRect/wxPoint in the tools.
> 
> Should be an operator overload.

I think his problem is about precision or something like that...

> Again, you may have to duplicate some of wxWindow::ProcessEvent() or see if we can use a
> hidden wxWindow as the base tool class.

As before there is the risk to marry into prone-to-change wx behaviour.
You always talk about using interfaces and then propose to duplicate the
implementation? strange:D

> KiCad is based on wx, moving off of it would a multi man-year project.  I would have not
> help.  Fighting wx makes the integration harder.  Learning to use it to your advantage is
> the clever path forward.

Well, this is not an integration, is a parallel subsystem... also, like
collections you are *not* enforced to use wx facilities for everything.
The inkscape people wrote an entire new event dispatch system because
the GTK one was not adequate for their project, for example.

-- 
Lorenzo Marcantonio
Logos Srl