[![screenshot_01](/wp-content/uploads/2012/12/screenshot_01.png)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenshot_01-7/)

**This is part two of my three part series on the internals of Recursive, an extension for Chrome. In the [first post](/posts/?p=2287) I talked about the general structure of Recursive and some of the lessons I learnt from dealing with Typescript. In the [second post](/posts/?p=2296) I discussed how Recursive goes about crawling and parsing the web. In this, the final post, i'm going to talk about how Recursive represents, lays out and renders that crawled data on the screen.**



### Code Structure

As mentioned in the first post in the series I have tried to keep the rendering logic as separate as possible from the actual crawling logic. This separation between the renderer and the crawler makes things simpler to understand in the code. The crawler is a model and the renderer is the view. The renderer simply displays whatever state the model contains.

### Representation

The question how to represent all the masses of data that the crawling process generates was tricky to decide upon and took quite a bit of tinkering before it ended up in its current form. I first toyed with the idea of displaying the data as a simple list of links where each list represents the next depth in the recurse, I demonstrated this concept in an early video:

<iframe src="https://www.youtube.com/embed/k4PD5yPLtp8" height="480" width="640" allowfullscreen="" frameborder="0"></iframe>

The problem, as can be seen in the above, is that there is still far too much data to display in that manner. I also wanted something that was more immediately visual, something that lets you see relative importance of nodes in the graph at a glance, simple lists of links couldn't provide this.

I remembered when I first launched Chrome Crawler a while back someone sent a video in which they had cleverly used Chrome Crawler and the open-source graphing program Gephi to great effect:

<iframe src="https://www.youtube.com/embed/C8P6ZttaZRo" height="360" width="640" allowfullscreen="" frameborder="0"></iframe>

When thinking about the problem of how to represent the data I was aware that a key difficulty was representing the relative importance of nodes and edges in the crawl graph but not to swamp the user with too much information. I eventually decided that grouping pages and files together under the domains that the crawler found them would be a good way of giving a sense of the relative size of each domain and the number and type of files found there.

[![screenshot_02](/wp-content/uploads/2012/12/screenshot_021.png)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenshot_02-11/)

Nodes, I decided, would be joined by a single line from the parent domain that crawled it. This way there wouldn't be too many confusing lines on the render yet you could still see how various domains were connected.

### Layout

Once I had the idea how I was going to represent the data from the crawler it was then a matter of working out how to lay out the nodes. I knew that the nodes were going to be circles and I knew that I didn't want them to overlap, I also wanted a dynamic looking graph (like the one in Gephi video above).

To achieve this I decided to use Box2D the popular physics engine to take some of the difficulties with positioning away for me. Using Box2D each edge between the nodes is a distance joint and the nodes themselves are simple circle shapes. Then I just let the simulation run and the nodes move and naturally try to separate from each other.

[![screenshot_03](/wp-content/uploads/2012/12/screenshot_031.png)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenshot_03-7/)

This solution worked in some situation however it was sub-optimal in others. The problem is that because each crawl is different you can end up in situations where there are many small nodes grouped about a parent or a few very large nodes:

[![ScreenHunter_01 Dec. 27 12.49](/wp-content/uploads/2012/12/ScreenHunter_01-Dec.-27-12.49.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_01-dec-27-12-49/)

I spent a good long while trying to ‘frig’ it so that the length of the distance joints between the nodes were right in most instances so that the nodes didn't overlap. The code was starting to look really messy and complex incorporating rules that depended on the number of children / siblings, the relative size of the nodes, the total length of the sibling nodes, the area values with proportion to the total area and so on.

No matter how many times I multiplied here, divided here I couldn't hack it into a form that worked for every crawl. So I decided to go back to the drawing board and rethink the layout problem.

[![ScreenHunter_02 Dec. 27 12.54](/wp-content/uploads/2012/12/ScreenHunter_02-Dec.-27-12.54.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_02-dec-27-12-54/)

After some scribbling I decided that what I needed to calculate was the total amount of space required for a node and the amount of space its parent had to allocate to fit it. Once I could correctly calculate those two it should be a relatively simple matter of spacing child nodes correctly about their parent.

I also noted that each node’s required area is simply the recursive sum of the space required by its children:

[![ScreenHunter_03 Dec. 27 12.59](/wp-content/uploads/2012/12/ScreenHunter_03-Dec.-27-12.59.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_03-dec-27-12-59/)

At the smallest scale the total space required by a single node is just its radius. If you add a child to that node then total space required is the nodes radius plus a constant distance plus the diameter of the child.

[![ScreenHunter_04 Dec. 27 13.00](/wp-content/uploads/2012/12/ScreenHunter_04-Dec.-27-13.00.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_04-dec-27-13-00/)

As you add more children however you run into the problem that there won't be enough space about the parent:

[![ScreenHunter_05 Dec. 27 13.02](/wp-content/uploads/2012/12/ScreenHunter_05-Dec.-27-13.02.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_05-dec-27-13-02/)

So now you must layer those children into concentric rings so that there is definitely enough space for each child. So how to do that. Well that was the tricky part and required some trigonometry (just about the only thing I remembered from high school maths).

[![ScreenHunter_06 Dec. 27 13.13](/wp-content/uploads/2012/12/ScreenHunter_06-Dec.-27-13.13.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_06-dec-27-13-13/)

Because we know the distance between the centre of the child and its parent and we know the radius of the child we can calculate the angle between two lines that extend from the parent and lie on points on the outside of the child’s radius and are perpendicular to the child's centre.

When we have this angle its a simple matter of looping through all of the (sorted smallest to largest) children adding up the angle required until you reach the maximum 360 degrees. Then you increase the distance between the parent by the diameter of the last node and start again on the second layer of children. This way you can guarantee that every child will have sufficient space about the parent.

[![ScreenHunter_01 Dec. 29 12.31](/wp-content/uploads/2012/12/ScreenHunter_01-Dec.-29-12.31.jpg)](/posts/recursive-nuts-bolts-part-3-rendering-the-results-3-of-3/attachment/screenhunter_01-dec-29-12-31/)

### Rendering

I knew that the graph would get very large and would be complex to render so performance was critical. I didn't want to spend ages messing around with WebGL, having done some before I knew that potentially it could take a lot longer than the relatively simple canvas2d. Because Chrome has a hardware accelerated canvas2d I reasoned that the performance should be okay.

Unfortunately even on a decent machine, the rendering is still rather slow, so that you usually cant crawl beyond about a depth of 3\. I tried all the common tips and tricks that can be found on the internet such as minimizing context switches when drawing lines and circles and caching commonly drawn things together in an image so that there are fewer draw calls. I even tried to assist chrome by putting the icons on one large image sheet, thinking it would be represented by a single texture behind the scenes thus minimise context switches when rendering to the GPU.

It seems however, that if you want performance in the browser you are going to have to go with WebGL.

### Improvements

Given more time it would be nice to explore swapping out the 2d rendering pipeline with a purely 3d one using WebGL, that should increase the speed of things a great deal. One idea is I could use point-sprite particles to render each icon within a 3d graph with wireframe lines to represent the edges between the nodes.

I did some work on point sprite particles in WebGL [a little while ago](/posts/hxaria-infinite-terrain-haxe-webgldat-gui/) so I know it should be possible to render millions (literally) of nodes and edges that way.

### Finally

Well thats the end of my series on the internals of Recursive, I hope you have enjoyed it. I haven't decided whether I want to release the source code just yet, I may return to the project in the future, but if you are interested in looking over the code send me an email: mike.cann@gmail.com

[![screenshot_05](/wp-content/uploads/2012/12/screenshot_05.png)](/posts/recursive-nuts-bolts-part-2-crawling-the-world-wide-web-2-of-3/attachment/screenshot_05-5/)

**This is part two of my three part series on the internals of Recursive, an extension for Google Chrome. In the [first post](/posts/?p=2287) I laid the groundwork for the contents of this and the next post. In this post i'm going to talk a little about what Recursive does internally once given  a URL.**

### Chrome Crawler



Recursive is actually based on an extension called Chrome Crawler I wrote [about a year ago](/posts/chrome-crawler-a-web-crawler-written-in-javascript/), but I had to change the name of due to Google's branding policy for Chrome Extensions. So although Recursive was rewritten from the ground up, a lot of the ideas discussed below stem from that project.

### Cross-Origin XMLHttpRequest

Much in the same way that search engine crawlers work, Recursive, downloads a url, scans it for links then recursively follows them.

Normally this sort of behaviour isn’t permitted to Javascript (or Flash for that matter) when running within a web page due to the [Same Origin Policy](https://en.wikipedia.org/wiki/Same_origin_policy) without specific permission from the server you are calling. Chrome extensions however don't have this restriction and thus (with permission given in the extension manifest) the extension is able to download content from any server.

This special behaviour is called the Cross-Origin [XMLHttpRequest](https://developer.chrome.com/extensions/xhr.html) and is what allows Recursive to work its magic.

### Code Structure

As briefly mentioned in the previous post the Crawling logic is separated from the Rendering logic. This differs from how Chrome Crawler was implemented where he rendering and crawling logic were mushed together. This separation took a little more thought and planning the result however is that the crawling logic makes much more sense and doesn't contain anything that doesn't purely pertain to the logic and data involved with crawling.

The crawling code is split up into three main files the Graph, the Crawler and the Parser.

[![screenshot_06](/wp-content/uploads/2012/12/screenshot_06.png)](/posts/recursive-nuts-bolts-part-2-crawling-the-world-wide-web-2-of-3/attachment/screenshot_06-4/)

The Graph is the central class that drives the crawling process. Only one of these exists for the application. It provides a number of functions for starting, stopping and pausing the crawling process. It also has a number of events (exposed through signals) that it uses to let listeners (the renderer) know when a particular event occurs.

The Crawler represents a single crawl instance. Its responsibility is to follow a single URL then report when it progresses, returns or errors. The Parser takes the returned HTML from the Crawler and scans it looking for links and files. It then returns the results which are then stored in the Crawler instance.

### Parsing Problems

One issue I encountered while developing Recursive (and Chrome Crawler) was the performance and security issues involved with parsing the HTML returned from the crawl. The way I originally handled this was to pass the entire HTML to JQuery then ask it for all ‘src’ and ‘href’ attributes:

```

function getAllLinksOnPage(page)
{
var links = new Array();
$(page).find('[src]').each(function(){ links.push($(this).attr('src')); });
$(page).find('[href]').each(function(){ links.push($(this).attr('href')) });
return links;
}

```

The problem with this is that behind the scenes jQuery is constructing a DOM which it uses for querying. Normally this is what you want, but in this instance its a problem because its rather slow process, also the browser executes the script tags and other elements when it generates the DOM. The result of which is the crawling is really slow and there were many security errors generated while crawling.

The solution was to use regex to parse the HTML and look for the attributes manually like so:

```

var links = new string[];

// Grab all HREF links
var results = c.pageHTML.match(/hrefs*=s*"([^"]*)/g);
if (results) results.forEach(s=>links.push(s.split(""")[1]));

// And all SRC links
results = c.pageHTML.match(/srcs*=s*"([^"]*)/g);
if (results) results.forEach(s=>links.push(s.split(""")[1]));

```

I was worried that the sheer amount of html text that must be parsed by the regex would result in things being really slow however it seems to hold up quite well, and is definitely not the bottle neck in the app.

### Custom File Filter

One addition to the result parsing that was added in v.1.1 was the ability to define a custom file filter:

[![Screenshot_002](/wp-content/uploads/2012/12/Screenshot_002.png)](/posts/recursive-v-1-1/attachment/screenshot_002/)

Enabling this adds a third regex call into the results parser. Any matches are added to the Crawler’s files as a special kind of file. When the user opens the files dialog all the matches are shown under a special category:

[![Screenshot_003](/wp-content/uploads/2012/12/Screenshot_003.png)](/posts/recursive-v-1-1/attachment/screenshot_003/)

### Improvements

Although the regex doesn't take very long to execute when parsing the HTML I had the thought that Javascript workers could be used to take advantage of the multiple cores that are present in most CPUs these days. Perhaps if I decide to perform some more complex sort of parsing i'll revisit this idea.

### Finally

Thats about it for part two of my three part discussion on some of the internals of Recursive. Head over to the third part to find out more about the layout and rendering of the returned data.