kicad-developers team mailing list archive

[Chris Gagneraud <chgans@xxxxxxxxxxxxxx>]

On 9 March 2016 at 09:42, Chris Pavlina <pavlina.chris@xxxxxxxxx> wrote:
> Personally I agree with your assessment, and I like the looks of some of what
> you're doing, though I only had a chance to give it a quick glance. Perhaps you
> could get in touch directly with Tom Włostowski? This is pretty much 'his' code
> for the time being.

Hi Chris,

I have stepped down a little bit, as I was trying to understand how I
broke the PNS during my refactoring session, I realised it would be
quite an heavy operation.

https://github.com/chgans/kicad/commit/49151832f3023172aa262fd06a7ea7d54217a239

I wanted to remove PNS_ROUTER dependency from PNS_ALGORITHM when it
comes to PSN_NODE management. that is instead of this chain of action:
user action -> router.fixupRoute() -> algo.fixupRoute() -> router.commit()
I wanted something flattened like:
user action -> router.fixupRoute() -> algo.fixupRoute()
                                                      -> algo.getWorld()
                                                      -> world.commit()

This is easily doable for all algorithm but the line placer. The
reason for this is just the way the line placer have been coded:
LinePlacer::FixupRoute()
{
  stuff();
  router().commit();
  moreStuff(); // Refactoring impediment
  evenMoreStuff(); // Refactoring impediment
  return true or false; // Refactoring impediment
}
The other algortihm are more straight forward and dead-easy to fix,
because they simply do:
OtherPlacer::FixupRoute()
{
 stuff();
 router.commit();
 return true;
}

Anyway, I'm not completely giving up, I'm just stepping back and
trying to understand what is at stake in the PNS router code, I'm
trying to get the big pictures, and the details as well.

I really love all the ideas behind the PNS router, conceptually
speaking it is really simple and beautiful.
But sometimes implementing the
https://en.wikipedia.org/wiki/KISS_principle can be quite tricky
indeed.

Chris

>
> On Mon, Mar 07, 2016 at 10:59:10PM +1300, Chris Gagneraud wrote:
>> Hi there,
>>
>> I stumbled across the FOSDEM 2015 presentation recently, and was
>> really impressed by the work done on the router. Near the last slides,
>> something caught my attention:
>>  - Written in C++ / Boost (optional, unordered)
>>  - Separate data model.
>>  - No UI library dependencies.
>>  - Can be integrated into other F/OSS EDA tools
>>    without much hassle.
>>
>> It all sounded so great to me that I decided to have a roll and see
>> how I could use PNS within my own projects.
>>
>> To my surprises, dependecies were a bit heavier than expected:
>>  - Boost (OK)
>>  - Geom/math kernel (OK)
>>  - Wx widgets (not too good)
>>  - pcbnew/kicad (ouch!)
>>
>> I knew there was a dependency on boost, I was not surprised to see a
>> dependency on a tailored made math and geometry library, the wxWidget
>> dependency didn't surprise me (knowing it is the toolkit used by
>> KiCad), what worried me was the dependency on pcbnew itself.
>>
>> The problem was quite simple to spot, yet not easy to fix:
>>  - PNS_ROUTER is a god object, it knows everything, and everyone
>>    relies on it.
>>  - PNS_ROUTER is full of Wx and KiCad stuff
>>  - The whole PNS core (NODE, INDEX, ITEM, ALGORITHM) depend on
>>    PNS_ROUTER
>>  - As a consequence the whole PNS core depends on Wx and KiCad.
>>  - And anyway, part of PNS core directly depends on KiCad and
>>    WxWidgets (like the "God forgive me doing this..." and the
>>    diff-pair hacks. ;))
>>
>> To fix this, I used a step by step refactoring approach (hence the
>> hight amount of commits):
>>  - Remove non-real dependencies on Wx and KiCad (unnecesary includes
>>    files, unnecessary forward declarations)
>>  - Move all KiCad dependend responsabilities from PNS_ALGORITHM,
>>    PNS_NODE, PNS_INDEX, PNS_ITEM to PNS_ROUTER, This is about making
>>    the core relying solely on the router to handle KiCad specific
>>    stuff.
>>  - Split PNS' router into a pure interface PNS_ROUTER_INTERFACE and
>>    it's KiCad's implementation: PNS_ROUTER.
>>  - Stuff PNS_ROUTER_INTERFACE with the strict minimum functions needed
>>    to get the PNS core building (Node, Index, Algorithm, ...).
>>  - Stuff PNS_ROUTER with everything else (PNS_ROUTER being now
>>    unreachable from PNS core).
>>
>> At that point the PNS core objects use a pointer to a
>> PNS_ROUTER_INTERFACE and doesn't contains (almost) any KiCad
>> dependencies (some exceptions were made for stuff I didn't fully
>> understand at that time).
>>
>> From there, the game could start:
>>  - Do refactoring by grouping PNS_ROUTER_INTERFACE functions in
>>  logical group, by either creating a new class to handle each group,
>>  or modify existing ones. Examples include:
>>    - PNS_CLEARANCE_RESOLVER (nee PNS_CLEARANCE_FUNC)
>>    - PNS_NET_RESOLVER (Deal only with paired nets for now)
>>    - PNS_DEBUG_DECORATOR (used solely by placers)
>>  - Make ALGORITHM objects relies on world instead of router. The
>>    router is still there, but now it actively assign the solvers to
>>    the world NODE, and the algorithm access these solvers through the
>>    world instead of through the router. Same story goes with SETTINGS.
>>  - Commit, hack, rebase, hack, amend, hack, repeat forever until
>>    brain's cooked up.
>>  - Once the PNS_ROUTER_INTERFACE is empty, removes any reference to it
>>    from PNS core.
>>
>> At that point PNS_ROUTER looks more like a controller than a god
>> object, and no PNS core objects depends on it. Cherry on the cake, all
>> KiCad dependencies are gone, and only wxString, translation macro
>> (underscore-brackets) and wxTimer.
>>
>> And that's where I stopped, I think I've already made big enough
>> modifications before i can keep going. I need to discuss this further
>> with you guys, to see if you are interested in this kind of work, to
>> organise a code review, get a feeling, ...
>>
>> You can see that as an Hackaton session, I did all this in 4 days
>> (part time, sorry!).
>>
>> I broke a few things in the process, but I do think that they should
>> be easy to fix (especially through code review, as my commits are
>> organised in logical chunks).
>>
>> I think the PNS router is an awesome framework, I like it's approach:
>>  - Spatial indexing of the PCB features (with layer and joint
>>    awareness)
>>  - Clever branch/merge of indexes.
>>  - Algorithm to handle PCB modifications
>>  - Separate data model
>>  - No UI dependencies
>>
>> But my feeling is there's still need for refactoring. For example:
>>
>> On the inner side:
>>  - Completely get rid of wxDeps (string, translation and timers)
>>  - Make ALGO straight forward to use: setWorld(), configure(),
>> execute(), getResult()
>>  - Properly fix coupling of KiCad/PNS via and layer(set). (my solution
>>    look more like a gross hack for now).
>>  - Remove PLACER dependency from items (why pns_meander.cpp needs
>>    pns_meander_placer_base.h?)
>>  - Remove NODE dependency from some items (line, meander, via)
>>  - Remove NODE dependency from SETTINGS
>>  - Remove NODE dependency from OPTIMISER and TOPOLOGY (I think it's
>>    doable by making them rely on a PNS_INDEX interface, provided by
>>    NODE with a proxy/facade design pattern.)
>>  - Only router and algorithm should have access to NODE
>>  - ITEM, TOPOLOGY and OPTIMISER should relies only on INDEX (INDEX is
>>    the spacial specialist, NODE is the branch/merge specialist)
>>
>> On the outer side:
>>  - Split the remaining code of the PNS_ROUTER into an implementation
>>    independent controller (the real PNS routing public interface) and
>>    it's KiCad implementation/usage.
>>
>>
>>
>>
>> That's it! I hope you will welcome my ideas, and I'm looking forward
>> to hear your feedback (positive or negative). I am definitely willing
>> to re-work my patches until it is acceptable to the PNS maintainers.
>>
>> I have 26 commits, they are available on GitHub at
>> https://github.com/chgans/kicad/.
>>
>> What would be the next step to get this RFC going on?
>> For convenience, I could open a pull request against GitHuib official
>> mirror. I know you guys use bazar, but at this point I just want my
>> hacks^W work to be commented on, a GitHub pull request could allow
>> that. Or I could send all the patch on the mailing list as they do
>> with other open source projects, I don't mind that either.
>>
>> Best regards,
>> Chris
>>
>> _______________________________________________
>> Mailing list: https://launchpad.net/~kicad-developers
>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> Unsubscribe : https://launchpad.net/~kicad-developers
>> More help   : https://help.launchpad.net/ListHelp
>
> --
> Chris