summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--chrome/browser/site_details_browsertest.cc263
-rw-r--r--chrome/chrome_tests.gypi1
-rw-r--r--content/test/data/cross_site_iframe_factory.html169
-rw-r--r--content/test/data/tree_parser_util.js153
4 files changed, 586 insertions, 0 deletions
diff --git a/chrome/browser/site_details_browsertest.cc b/chrome/browser/site_details_browsertest.cc
new file mode 100644
index 0000000..b84be4c
--- /dev/null
+++ b/chrome/browser/site_details_browsertest.cc
@@ -0,0 +1,263 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/site_details.h"
+
+#include "base/bind_helpers.h"
+#include "base/message_loop/message_loop.h"
+#include "base/path_service.h"
+#include "base/test/histogram_tester.h"
+#include "chrome/browser/metrics/metrics_memory_details.h"
+#include "chrome/browser/ui/browser.h"
+#include "chrome/browser/ui/tabs/tab_strip_model.h"
+#include "chrome/test/base/in_process_browser_test.h"
+#include "chrome/test/base/ui_test_utils.h"
+#include "content/public/browser/notification_service.h"
+#include "content/public/test/browser_test_utils.h"
+#include "content/public/test/test_utils.h"
+#include "net/dns/mock_host_resolver.h"
+#include "net/test/embedded_test_server/embedded_test_server.h"
+#include "testing/gmock/include/gmock/gmock.h"
+
+using base::Bucket;
+using testing::ContainerEq;
+using testing::ElementsAre;
+
+namespace {
+
+class TestMemoryDetails : public MetricsMemoryDetails {
+ public:
+ TestMemoryDetails()
+ : MetricsMemoryDetails(base::Bind(&base::DoNothing), nullptr) {}
+
+ void StartFetchAndWait() {
+ uma_.reset(new base::HistogramTester());
+ StartFetch(FROM_CHROME_ONLY);
+ content::RunMessageLoop();
+ }
+
+ // Returns a HistogramTester which observed the most recent call to
+ // StartFetchAndWait().
+ base::HistogramTester* uma() { return uma_.get(); }
+
+ private:
+ ~TestMemoryDetails() override {}
+
+ void OnDetailsAvailable() override {
+ MetricsMemoryDetails::OnDetailsAvailable();
+ // Exit the loop initiated by StartFetchAndWait().
+ base::MessageLoop::current()->Quit();
+ }
+
+ scoped_ptr<base::HistogramTester> uma_;
+
+ DISALLOW_COPY_AND_ASSIGN(TestMemoryDetails);
+};
+
+} // namespace
+
+class SiteDetailsBrowserTest : public InProcessBrowserTest {
+ public:
+ SiteDetailsBrowserTest() {}
+ ~SiteDetailsBrowserTest() override {}
+
+ void SetUpOnMainThread() override {
+ host_resolver()->AddRule("*", "127.0.0.1");
+
+ // Add content/test/data so we can use cross_site_iframe_factory.html
+ base::FilePath test_data_dir;
+ ASSERT_TRUE(PathService::Get(base::DIR_SOURCE_ROOT, &test_data_dir));
+ embedded_test_server()->ServeFilesFromDirectory(
+ test_data_dir.AppendASCII("content/test/data/"));
+ ASSERT_TRUE(embedded_test_server()->InitializeAndWaitUntilReady());
+ }
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(SiteDetailsBrowserTest);
+};
+
+// Test the accuracy of SiteDetails process estimation, in the presence of
+// multiple iframes, navigation, multiple BrowsingInstances, and multiple tabs
+// in the same BrowsingInstance.
+IN_PROC_BROWSER_TEST_F(SiteDetailsBrowserTest, ManyCrossSiteIframes) {
+ // Page with 14 nested oopifs across 9 sites (a.com through i.com).
+ // None of these are https.
+ GURL abcdefghi_url = embedded_test_server()->GetURL(
+ "a.com",
+ "/cross_site_iframe_factory.html?a(b(a(b,c,d,e,f,g,h)),c,d,e,i(f))");
+ ui_test_utils::NavigateToURL(browser(), abcdefghi_url);
+
+ // Get the metrics.
+ scoped_refptr<TestMemoryDetails> details = new TestMemoryDetails();
+ details->StartFetchAndWait();
+
+ EXPECT_THAT(
+ details->uma()->GetAllSamples("SiteIsolation.BrowsingInstanceCount"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.CurrentRendererProcessCount"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountEstimate"),
+ ElementsAre(Bucket(9, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(9, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(9, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountEstimate"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(1, 1)));
+
+ // Navigate to a different, disjoint set of 7 sites.
+ GURL pqrstuv_url = embedded_test_server()->GetURL(
+ "p.com",
+ "/cross_site_iframe_factory.html?p(q(r),r(s),s(t),t(q),u(u),v(p))");
+ ui_test_utils::NavigateToURL(browser(), pqrstuv_url);
+
+ details = new TestMemoryDetails();
+ details->StartFetchAndWait();
+
+ EXPECT_THAT(
+ details->uma()->GetAllSamples("SiteIsolation.BrowsingInstanceCount"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.CurrentRendererProcessCount"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountEstimate"),
+ ElementsAre(Bucket(7, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(7, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(7, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountEstimate"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(1, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(1, 1)));
+
+ // Open a second tab (different BrowsingInstance) with 4 sites (a through d).
+ GURL abcd_url = embedded_test_server()->GetURL(
+ "a.com", "/cross_site_iframe_factory.html?a(b(c(d())))");
+ AddTabAtIndex(1, abcd_url, ui::PAGE_TRANSITION_TYPED);
+
+ details = new TestMemoryDetails();
+ details->StartFetchAndWait();
+
+ EXPECT_THAT(
+ details->uma()->GetAllSamples("SiteIsolation.BrowsingInstanceCount"),
+ ElementsAre(Bucket(2, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.CurrentRendererProcessCount"),
+ ElementsAre(Bucket(2, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountEstimate"),
+ ElementsAre(Bucket(11, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(11, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(11, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountEstimate"),
+ ElementsAre(Bucket(2, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(1, 1))); // TODO(nick): This should be 2.
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(2, 1)));
+
+ // Open a third tab (different BrowsingInstance) with the same 4 sites.
+ AddTabAtIndex(2, abcd_url, ui::PAGE_TRANSITION_TYPED);
+
+ details = new TestMemoryDetails();
+ details->StartFetchAndWait();
+
+ EXPECT_THAT(
+ details->uma()->GetAllSamples("SiteIsolation.BrowsingInstanceCount"),
+ ElementsAre(Bucket(3, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.CurrentRendererProcessCount"),
+ ElementsAre(Bucket(3, 1)));
+ // Could be 11 if subframe processes were reused across BrowsingInstances.
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountEstimate"),
+ ElementsAre(Bucket(15, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(11, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(15, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountEstimate"),
+ ElementsAre(Bucket(3, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(1, 1))); // TODO(nick): This should be 3.
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(3, 1)));
+
+ // Do a window.open() to obtain a fourth tab in the same BrowsingInstance as
+ // the third tab. The new page uses the same four sites "a-d" as third tab,
+ // plus an additional site "e". The estimated process counts should increase
+ // by one (not five) from the previous result, since the new tab can reuse the
+ // four processes already in the BrowsingInstance.
+ GURL dcbae_url = embedded_test_server()->GetURL(
+ "a.com", "/cross_site_iframe_factory.html?d(c(b(a(e))))");
+ ui_test_utils::UrlLoadObserver load_complete(
+ dcbae_url, content::NotificationService::AllSources());
+ ASSERT_EQ(3, browser()->tab_strip_model()->count());
+ ASSERT_TRUE(content::ExecuteScript(
+ browser()->tab_strip_model()->GetActiveWebContents(),
+ "window.open('" + dcbae_url.spec() + "');"));
+ ASSERT_EQ(4, browser()->tab_strip_model()->count());
+ load_complete.Wait();
+
+ details = new TestMemoryDetails();
+ details->StartFetchAndWait();
+
+ EXPECT_THAT(
+ details->uma()->GetAllSamples("SiteIsolation.BrowsingInstanceCount"),
+ ElementsAre(Bucket(3, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.CurrentRendererProcessCount"),
+ ElementsAre(Bucket(3, 1)));
+ // Could be 11 if subframe processes were reused across BrowsingInstances.
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountEstimate"),
+ ElementsAre(Bucket(16, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(12, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateAllSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(16, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountEstimate"),
+ ElementsAre(Bucket(3, 1)));
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountLowerBound"),
+ ElementsAre(Bucket(1, 1))); // TODO(nick): This should be 3.
+ EXPECT_THAT(details->uma()->GetAllSamples(
+ "SiteIsolation.IsolateHttpsSitesProcessCountNoLimit"),
+ ElementsAre(Bucket(3, 1)));
+}
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index ec0d930..39c28d6 100644
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -400,6 +400,7 @@
'browser/sessions/session_restore_browsertest.cc',
'browser/sessions/session_restore_browsertest_chromeos.cc',
'browser/sessions/tab_restore_browsertest.cc',
+ 'browser/site_details_browsertest.cc',
'browser/spellchecker/spellcheck_service_browsertest.cc',
'browser/ssl/captive_portal_blocking_page_browsertest.cc',
'browser/ssl/certificate_reporting_test_utils.cc',
diff --git a/content/test/data/cross_site_iframe_factory.html b/content/test/data/cross_site_iframe_factory.html
new file mode 100644
index 0000000..2a01c40
--- /dev/null
+++ b/content/test/data/cross_site_iframe_factory.html
@@ -0,0 +1,169 @@
+<html>
+<!-- This page can create whatever iframe structure you want, across whatever
+sites you want. This is useful for testing site isolation.
+
+Example usage in a browsertest, explained:
+
+ GURL url =
+ test_server()->GetURL("a.com", "/cross_site_iframe_factory.html?a(b(c,d))");
+
+When you navigate to the above URL, the outer document (on a.com) will create a
+single iframe:
+
+ <iframe src="http://b.com:1234/cross_site_iframe_factory.html?b(c(),d())">
+
+Inside of which, then, are created the two leaf iframes:
+
+ <iframe src="http://c.com:1234/cross_site_iframe_factory.html?c()">
+ <iframe src="http://d.com:1234/cross_site_iframe_factory.html?d()">
+
+To make this page work, your browsertest needs a MockHostResolver, like:
+
+ void SetUpOnMainThread() override {
+ host_resolver()->AddRule("*", "127.0.0.1");
+ ASSERT_TRUE(embedded_test_server()->InitializeAndWaitUntilReady());
+ }
+
+You can play around with the arguments by loading this page via file://, but
+you probably won't get the same process behavior as if you loaded via http. -->
+<head>
+<title>Cross-site iframe factory</title>
+<style>
+body {
+ font-family: Sans-Serif;
+ text-align: center;
+}
+iframe {
+ border-radius: 7px;
+ border-style: solid;
+ vertical-align: top;
+ margin: 2px;
+ box-shadow: 2px 2px 2px #888888;
+}
+</style>
+</head>
+<body>
+<h2 id='siteNameHeading'></h2>
+
+
+<script src='tree_parser_util.js'></script>
+<script type='text/javascript'>
+
+/**
+ * Determines a random pastel-ish color from the first character of a string.
+ */
+function pastelColorForFirstCharacter(seedString, lightness) {
+ // Map the first character to an index. This could be negative, we don't
+ // really care.
+ var index = seedString.charCodeAt(0) - 'a'.charCodeAt(0);
+
+ // If the first character is 'a', this will the the starting color.
+ var hueOfA = 200; // Spoiler alert: it's blue.
+
+ // Color palette generation articles suggest that spinning the hue wheel by
+ // the golden ratio yields a magically nice color distribution. Something
+ // about sunflower seeds. I am skeptical of the rigor of that claim (probably
+ // any irrational number at a slight offset from 2/3 would do) but it does
+ // look pretty.
+ var phi = 2 / (1 + Math.pow(5, .5));
+ var hue = Math.round((360 * index * phi + hueOfA) % 360);
+ return 'hsl(' + hue + ', 60%, ' + Math.round(100 * lightness) + '%)';
+}
+
+function backgroundColorForSite(site) {
+ // Light pastel.
+ return pastelColorForFirstCharacter(site, .75);
+}
+
+function borderColorForSite(site) {
+ // Darker color in the same hue has the background.
+ return pastelColorForFirstCharacter(site, .32);
+}
+
+/**
+ * Adds ".com" to an argument if it doesn't already have a top level domain.
+ * This cuts down on noise in the query string, letting you use single-letter
+ * names.
+ */
+function canonicalizeSite(siteString) {
+ if (siteString.indexOf('.') == -1)
+ return siteString + '.com';
+ return siteString;
+}
+
+/**
+ * Simple recursive layout heuristic, since frames can't size themselves.
+ * This scribbles .layoutX and .layoutY properties into |tree|.
+ */
+function layout(tree) {
+ // Step 1: layout children.
+ var numFrames = tree.children.length;
+ for (var i = 0; i < numFrames; i++) {
+ layout(tree.children[i]);
+ }
+
+ // Step 2: find largest child.
+ var largestChildX = 0;
+ var largestChildY = 0;
+ for (var i = 0; i < numFrames; i++) {
+ largestChildX = Math.max(largestChildX, tree.children[i].layoutX);
+ largestChildY = Math.max(largestChildY, tree.children[i].layoutY);
+ }
+
+ // Step 3: Tweakable control parameters.
+ var minX = 110; // Should be wide enough to fit a decent sized domain.
+ var minY = 110; // Could be less, but squares look nice.
+ var extraYPerLevel = 50; // Needs to be tall enough to fit a line of text.
+ var extraXPerLevel = 50; // Could be less, but squares look nice.
+
+ // Account for padding around each <iframe>.
+ largestChildX += 30;
+ largestChildY += 30;
+
+ // Step 4: Assume a gridSizeX-by-gridSizeY layout that's big enough to fit if
+ // all children were the size of the largest one.
+ var gridSizeX = Math.ceil(Math.sqrt(numFrames));
+ var gridSizeY = Math.round(Math.sqrt(numFrames));
+ tree.layoutX = Math.max(gridSizeX * largestChildX + extraXPerLevel, minX);
+ tree.layoutY = Math.max(gridSizeY * largestChildY + extraYPerLevel, minY);
+}
+
+function main() {
+ var goCrossSite = !window.location.protocol.startsWith('file');
+ var queryString = decodeURIComponent(window.location.search.substring(1));
+ var frameTree = TreeParserUtil.parse(queryString);
+ var currentSite = canonicalizeSite(frameTree.value);
+
+ // Apply style to the current document.
+ document.getElementById('siteNameHeading').appendChild(
+ document.createTextNode(currentSite));
+ document.body.style.backgroundColor = backgroundColorForSite(currentSite);
+
+ // Determine how big the children should be (using a very rough heuristic).
+ layout(frameTree);
+
+ for (var i = 0; i < frameTree.children.length; i++) {
+ // Compute the URL for this iframe .
+ var site = canonicalizeSite(frameTree.children[i].value);
+ var subtreeString = TreeParserUtil.flatten(frameTree.children[i]);
+ var url = '';
+ url += window.location.protocol + '//'; // scheme (preserved)
+ url += goCrossSite ? site : window.location.host; // host
+ if (window.location.port)
+ url += ':' + window.location.port; // port (preserved)
+ url += window.location.pathname; // path (preserved)
+ url += '?' + encodeURIComponent(subtreeString); // query
+
+ // Add the iframe to the document.
+ var iframe = document.createElement('iframe');
+ iframe.src = url;
+ iframe.style.borderColor = borderColorForSite(site);
+ iframe.width = frameTree.children[i].layoutX;
+ iframe.height = frameTree.children[i].layoutY;
+ document.body.appendChild(iframe);
+ }
+}
+
+main();
+</script>
+</body></html>
diff --git a/content/test/data/tree_parser_util.js b/content/test/data/tree_parser_util.js
new file mode 100644
index 0000000..4f83fdd
--- /dev/null
+++ b/content/test/data/tree_parser_util.js
@@ -0,0 +1,153 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+/**
+ * Parser for a simple grammar that describes a tree structure using a function-
+ * like "a(b(c,d))" syntax. Original intended usage: to have browsertests
+ * specify an arbitrary tree of iframes, loaded from various sites, without
+ * having to write a .html page for each level or do crazy feats of data: url
+ * escaping. But there's nothing really iframe-specific here. See below for some
+ * examples of the grammar and the parser output.
+ *
+ * @example <caption>Basic syntax: an identifier followed by arg list.</caption>
+ * TreeParserUtil.parse('abc ()'); // returns { value: 'abc', children: [] }
+ *
+ * @example <caption>The arg list is optional. Dots are legal in ids.</caption>
+ * TreeParserUtil.parse('b.com'); // returns { value: 'b.com', children: [] }
+ *
+ * @example <caption>Commas separate children in the arg list.</caption>
+ * // returns { value: 'b', children: [
+ * // { value: 'c', children: [] },
+ * // { value: 'd', children: [] }
+ * // ]}
+ * TreeParserUtil.parse('b (c, d)';
+ *
+ * @example <caption>Children can have children, and so on.</caption>
+ * // returns { value: 'e', children: [
+ * // { value: 'f', children: [
+ * // { value: 'g', children: [
+ * // { value: 'h', children: [] },
+ * // { value: 'i', children: [
+ * // { value: 'j', children: [] }
+ * // ]},
+ * // ]}
+ * // ]}
+ * // ]}
+ * TreeParserUtil.parse('e(f(g(h(),i(j))))';
+ *
+ * @example <caption>flatten() converts a [sub]tree back to a string.</caption>
+ * var tree = TreeParserUtil.parse('b.com (c.com(e.com), d.com)');
+ * TreeParserUtil.flatten(tree.children[0]); // returns 'c.com(e.com())'
+ */
+var TreeParserUtil = (function() {
+ 'use strict';
+
+ /**
+ * Parses an input string into a tree. See class comment for examples.
+ * @returns A tree of the form {value: <string>, children: <Array.<tree>>}.
+ */
+ function parse(input) {
+ var tokenStream = lex(input);
+
+ var result = takeIdAndChild(tokenStream);
+ if (tokenStream.length != 0)
+ throw new Error('Expected end of stream, but found "' +
+ tokenStream[0] + '".')
+ return result;
+ }
+
+ /**
+ * Inverse of |parse|. Converts a parsed tree object into a string. Can be
+ * used to forward a subtree as an argument to a nested document.
+ */
+ function flatten(tree) {
+ return tree.value + '(' + tree.children.map(flatten).join(',') + ')';
+ }
+
+ /**
+ * Lexer function to convert an input string into a token stream. Splits the
+ * input along whitespace, parens and commas. Whitespace is removed, while
+ * parens and commas are preserved as standalone tokens.
+ *
+ * @param {string} input The input string.
+ * @return {Array.<string>} The resulting token stream.
+ */
+ function lex(input) {
+ return input.split(/(\s+|\(|\)|,)/).reduce(
+ function (resultArray, token) {
+ var trimmed = token.trim();
+ if (trimmed) {
+ resultArray.push(trimmed);
+ }
+ return resultArray;
+ }, []);
+ }
+
+
+ /**
+ * Consumes from the stream an identifier and optional child list, returning
+ * its parsed representation.
+ */
+ function takeIdAndChild(tokenStream) {
+ return { value: takeIdentifier(tokenStream),
+ children: takeChildList(tokenStream) };
+ }
+
+ /**
+ * Consumes from the stream an identifier, returning its value (as a string).
+ */
+ function takeIdentifier(tokenStream) {
+ if (tokenStream.length == 0)
+ throw new Error('Expected an identifier, but found end-of-stream.');
+ var token = tokenStream.shift();
+ if (!token.match(/[a-zA-Z0-9.-]+/))
+ throw new Error('Expected an identifier, but found "' + token + '".');
+ return token;
+ }
+
+ /**
+ * Consumes an optional child list from the token stream, returning a list of
+ * the parsed children.
+ */
+ function takeChildList(tokenStream) {
+ // Remove the next token from the stream if it matches |token|.
+ function tryToEatA(token) {
+ if (tokenStream[0] == token) {
+ tokenStream.shift();
+ return true;
+ }
+ return false;
+ }
+
+ // Bare identifier case, as in 'b' in the input '(a (b, c))'
+ if (!tryToEatA('('))
+ return [];
+
+ // Empty list case, as in 'b' in the input 'a (b (), c)'.
+ if (tryToEatA(')')) {
+ return [];
+ }
+
+ // List with at least one entry.
+ var result = [ takeIdAndChild(tokenStream) ];
+
+ // Additional entries allowed with commas.
+ while (tryToEatA(',')) {
+ result.push(takeIdAndChild(tokenStream));
+ }
+
+ // End of list.
+ if (tryToEatA(')')) {
+ return result;
+ }
+ if (tokenStream.length == 0)
+ throw new Error('Expected ")" or ",", but found end-of-stream.');
+ throw new Error('Expected ")" or ",", but found "' + tokenStream[0] + '".');
+ }
+
+ return {
+ parse: parse,
+ flatten: flatten
+ };
+})();