kicad-developers team mailing list archive

[Chris Gagneraud <chgans@xxxxxxxxxxxxxx>]

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