search

Galooshi / happo

Visual diffing in CI for user interfaces
504 stars 16 forks source link

Replace adiff with our own, iterative, LCS implementation #158

Closed trotzig closed 7 years ago

trotzig commented 7 years ago

The adiff package served us well, but it was ultimately not the right tool for the job:

Most of those ^^ are covered in 1.

I've been exploring rolling our own LCS implementation for a while, and this commit is the result of that. Instead of using recursion (as adiff is doing), we're taking an iterative approach. By using memoization and a traceback approach, we can carefully inject placeholders in the before and after array to make the two align with each other. Consider this example:

A = 'ABCD' B = 'GAFFC'

We can see that the LCS of these two strings is 'AC'. Now, if we inject placeholders (the +'es below) in a few places we can make the A and C characters align:

A = '+AB+CD' B = 'GAFFC+'

When the arrays align, we know that they're of the same size. We can then feed them along to the ImageDiff worker comparing them pixel by pixel.

To be able to test the algorithm, I've added a Jest/Jasmine test. For that to work, I had to add a few package dependencies, following the guide on the Jest homepage 2.

While developing the LCS implementation, I found this to be a good resource: http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/ The longestCommonSubsequence function is basically my interpretation of the (Java) example on that page.

lencioni commented 7 years ago

Yeah, for node jobs, Travis will run npm test by default.

On Tue, Sep 27, 2016, 11:53 PM Henric Trotzig notifications@github.com wrote:

@trotzig commented on this pull request.

In package.json https://github.com/Galooshi/happo/pull/158:

@@ -4,7 +4,7 @@ "description": "Command-line tool to visually diff JavaScript components", "scripts": { "eslint": "eslint --ext .js,.jsx",

  • "test": "npm run --silent eslint -- .",
  • "test": "jest",

I don't think I understand how that is set up. Is this done automagically by travis? I don't see it referenced in .travis.yml.

I'll put it back.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/Galooshi/happo/pull/158, or mute the thread https://github.com/notifications/unsubscribe-auth/AAL7ziWJ3VrugqSRogR9YeHOxwXQUqQVks5qug7sgaJpZM4KHU0X .