Implement Build Algorithm for Only Changed/Affected Patterns

[bmuenzenmeyer]

An idea has been floating around for a while to walk pattern lineage or reverse lineage when a pattern is changed, instead of rebuilding the whole pattern tree.

This is a large effort- but discussion can start here and move to implementation as we go.

Related concept: #327

[tburny]

Proposal

Initially patternlab would build as normal, resolving the lineage and reverse lineage of each pattern.
We can then use the (reverse?) lineage to build a dependency graph of the patterns. Each node would consist of
a (pseudo-)pattern, a timestamp at which the source file (template or JSON) was last modified and a state.
When patternlab finishes, the state of each node is set to clean and the graph is written to a file (e.g. JSON).
Such a graph could either be stored as a matrix or via adjacency list (i.e. given a pattern, have an array of all other patterns it depends upon) (-> TBD).

On the next run, patternlab would read the file and compare the modification dates to the moditication timestamps of each file.
(Corner case: When a pattern is added or deleted, the graph will be updated accordingly by adding or removing edges to dependant patterns. So we need to check for differences in the file list.)
If the modification timestamp of the file is greater than the one in the graph, its node will be marked as dirty.
Now we simply need to build the transitive closure of all dirty nodes to know which patterns we have to process.
I'll be using A -> B to denote that pattern A includes B as partial pattern.
So given A -> B -> C -> D, if C is dirty so are B and A. We do not need to recompile C and can skip it completely, because it has no dependencies.

For example you might think of it as A is Template, B is an Organism, C is a Molecule and D is an Atom. When rebuilding a changed molecule, no atoms are harmed.

When a pattern is compiling, we set its state to compiling and to clean when done. This way we know when something went wrong.

Still, we need to know the compilation order of all dirty nodes, so we apply a sprinkle of Topological sorting to the transitive closure to determine which templates we need to compile next.
The difference to the lineage is that here the pattern dependencies are known:
Given A -> B and A -> C where B and C are dirty, we first need to build B and C before we can rebuild A.
A valid topological sorting therefore would be C, B, A or B, C, A.

By only rebuilding all dirty patterns, we should be able to boil down compile times to a few hunded milliseconds maximum, which would be an exponential speed up.

I haven't been diving through all of the patternlab-node source code. Does anyone have suggestions where to hook this in? Also I'd love to hear some feedback and see some thumbs :)

Future extensions

Patternlab could either

• be run using patternlab:serve which watches
  for file changes via grunt
• use a file system watcher such as cheerio to collect a list of changed patterns (running forever). The list then can be used to update the graph accordingly and proceed as described above. This would be a sort of "instant preview" feature.

Note that IMHO the second case sort of extends the first.

[tburny]

Somehow rebasing with git behaves a bit strange :(

Nevertheless the current state is a prototype which propagates compile state changes through the graph. There are still a few bugs.