I've implemented a parse-tree based ContentRewriter using the existing plumbing (same caching semantics et al), as ParseTreeDefaultContentRewriter and ParseTreeHtmlRewriter, respectively. The latter contains essentially all rewriting functionality from the previous HtmlTagTransformer classes. The parse-tree based rewriter is now functionally equivalent to the previous rewriter. The new classes use a Caja-based HTML parser under the hood. This proves out the functional viability of a tree-based rewriter, but performance also needs to be assessed.
I've gone ahead and profiled the comparative performance of each rewriter, "Lexer" based and "ParseTree" based. To no surprise, "Lexer" wins out every time essentially by definition, since obviously Caja's parser uses its own lexer under the hood. Summary: * The performance of each is fundamentally O(n), though... * For any given input size, Lexer-based rewriting averages between 2.5 - 3.5x faster than ParseTree-based (ie. c =~ 3.5 at worst). * By far, the majority of time involved in ParseTree-based optimization is initial parsing: 75% of all processing. Details: 1. I wrote a simple rewriter/parser profiler which rewrites (the sample rewriter gadget's content * X repetitions) N times, recording the resulting run time. The run time of parse-based rewriting degraded as N increased, in all likelihood due to the additional cost of object management (lexer-based rewriting involves few intermediate objects). Given that the results of rewriting will be variously cached, it's very unlikely that rewriting will happen in immediate succession hundreds or thousands of times. As such, I fixed N = 1 to re-run the tests in relative isolation from one another. Results from a given run: LEX-BASED*100 rewriter, 1 runs in 177047 microsecs [177.04704] millis/run PARSE-BASED*100 rewriter, 1 runs in 609136 microsecs [609.136128] millis/run Parse/lex ratio: 3.4405327398939263 LEX-BASED*50 rewriter, 1 runs in 43936 microsecs [43.936] millis/run PARSE-BASED*50 rewriter, 1 runs in 148980 microsecs [148.979968] millis/run Parse/lex ratio: 3.3908412235979606 LEX-BASED*10 rewriter, 1 runs in 3093 microsecs [3.092992] millis/run PARSE-BASED*10 rewriter, 1 runs in 11020 microsecs [11.020032] millis/run Parse/lex ratio: 3.5628839314581313 LEX-BASED*1 rewriter, 1 runs in 600 microsecs [0.600064] millis/run PARSE-BASED*1 rewriter, 1 runs in 1819 microsecs [1.819136] millis/run Parse/lex ratio: 3.0316666666666667 2. Drilling down, I added simple operation profiling to each component of parse-tree rewriting: original parse (CajaHtmlParser); building mutable tree nodes; rewriting links; concatenating JS nodes; rewriting style blocks; rendering parse tree. I then reran the same tests. Results from subsequent run: LEX-BASED*100 rewriter, 1 runs in 165321 microsecs [165.32096] millis/run PARSE-BASED*100 rewriter, 1 runs in 646884 microsecs [646.88384] millis/run Parse/lex ratio: 3.912896728183352 [PARSE OPS] Op[style-rewrite] min:25.419ms, max:25.419ms, avg:25.419ms Op[render] min:36.851ms, max:36.851ms, avg:36.851ms Op[js-rewrite] min:53.983ms, max:53.983ms, avg:53.983ms Op[link-rewrite] min:31.136ms, max:31.136ms, avg:31.136ms Op[build-nodes] min:32.929ms, max:32.929ms, avg:32.929ms Op[parse] min:464.211ms, max:464.211ms, avg:464.211ms LEX-BASED*50 rewriter, 1 runs in 30684 microsecs [30.683904] millis/run PARSE-BASED*50 rewriter, 1 runs in 161132 microsecs [161.132032] millis/run Parse/lex ratio: 5.251336201277539 [PARSE OPS] Op[style-rewrite] min:8.581ms, max:8.581ms, avg:8.581ms Op[render] min:5.184ms, max:5.184ms, avg:5.184ms Op[js-rewrite] min:11.606ms, max:11.606ms, avg:11.606ms Op[link-rewrite] min:7.533ms, max:7.533ms, avg:7.533ms Op[build-nodes] min:3.41ms, max:3.41ms, avg:3.41ms Op[parse] min:121.367ms, max:121.367ms, avg:121.367ms LEX-BASED*10 rewriter, 1 runs in 3371 microsecs [3.371008] millis/run PARSE-BASED*10 rewriter, 1 runs in 10336 microsecs [10.336] millis/run Parse/lex ratio: 3.066152477009789 [PARSE OPS] Op[style-rewrite] min:0.563ms, max:0.563ms, avg:0.563ms Op[render] min:0.678ms, max:0.678ms, avg:0.678ms Op[js-rewrite] min:1.374ms, max:1.374ms, avg:1.374ms Op[link-rewrite] min:0.718ms, max:0.718ms, avg:0.718ms Op[build-nodes] min:0.295ms, max:0.295ms, avg:0.295ms Op[parse] min:6.466ms, max:6.466ms, avg:6.466ms LEX-BASED*1 rewriter, 1 runs in 592 microsecs [0.592128] millis/run PARSE-BASED*1 rewriter, 1 runs in 2083 microsecs [2.083072] millis/run Parse/lex ratio: 3.518581081081081 [PARSE OPS] Op[style-rewrite] min:0.082ms, max:0.082ms, avg:0.082ms Op[render] min:0.077ms, max:0.077ms, avg:0.077ms Op[js-rewrite] min:0.143ms, max:0.143ms, avg:0.143ms Op[link-rewrite] min:0.111ms, max:0.111ms, avg:0.111ms Op[build-nodes] min:0.043ms, max:0.043ms, avg:0.043ms Op[parse] min:1.437ms, max:1.437ms, avg:1.437ms 3. Drilling further, I wrote a separate test breaking out the performance components to parsing: calling the Caja DomParser.parseFragment(...) API, and subsequently wrapping the results of that call with ParsedHtmlNode objects to satisfy interface requirements: Typical run: Caja parser [size*1, runs:1] in 97538 microsecs [97.538048] millis/run [PARSER COMPONENTS] Op[raw-caja-parse] min:70.033ms, max:70.033ms, avg:70.033ms Op[build-parse-nodes] min:3.644ms, max:3.644ms, avg:3.644ms Caja parser [size*10, runs:1] in 42915 microsecs [42.915072] millis/run [PARSER COMPONENTS] Op[raw-caja-parse] min:34.676ms, max:34.676ms, avg:34.676ms Op[build-parse-nodes] min:7.148ms, max:7.148ms, avg:7.148ms Caja parser [size*50, runs:1] in 157048 microsecs [157.048064] millis/run [PARSER COMPONENTS] Op[raw-caja-parse] min:138.904ms, max:138.904ms, avg:138.904ms Op[build-parse-nodes] min:17.313ms, max:17.313ms, avg:17.313ms Caja parser [size*100, runs:1] in 236073 microsecs [236.07296] millis/run [PARSER COMPONENTS] Op[raw-caja-parse] min:173.743ms, max:173.743ms, avg:173.743ms Op[build-parse-nodes] min:43.295ms, max:43.295ms, avg:43.295ms Conclusions and Discussion: The purpose of this task was to prove that tree-based parsing is functionally viable, which has succeeded. Past that, it's a matter of choosing functionality vs. performance. Given that rewriting results are cached, perhaps even ~3x increase in rewriting cost will be worth paying. That's particularly true given the new class of optimizations/rewrites made possible with a parse tree, as well as some bugs that are more easily fixed using it. For instance, I recently discovered a bug with the existing JS tag rewriter which ignores type="..." attributes and doesn't maintain "id" attributes in certain situations. These can be resolved in the lexer case, but are clearer in the parser one. Lastly, as mentioned at the beginning of this thread, I plan to maintain the ability to manipulate a gadget by string, meaning a lexer-based approach can still be used where desired and parse-tree isn't required. Next steps: 1. My next step is to add modularity to content rewriting, but again without changing any caching semantics. Instead, rather than a single ContentRewriter being injected, a ContentRewriterRegistry will be. The default Registry will support injection of a single ContentRewriter to maintain backward compatibility for now. 2. GadgetSpec immutability restored, ensuring post-rewritten caching. 3. ContentRewriter API cleanup. --John On Tue, Aug 12, 2008 at 7:43 PM, John Hjelmstad <[EMAIL PROTECTED]> wrote: > Interesting idea, and sounds fine to me. Concretely, this lets me sidestep > SHINDIG-500 for a little while, which is nice (though I'd _really_ like to > see the API cleanup go in! :)), in favor of migrating the existing rewriter > to a tree-based approach. Turns out I've been working on #1 and #2 > independently anyway. I'll post a patch soon. Thanks! > > John > > > On Tue, Aug 12, 2008 at 7:14 PM, Louis Ryan <[EMAIL PROTECTED]> wrote: > >> Can we prove this out incrementally bottom-up. In general I think using >> DOM >> is the right thing to do from a rewriting standpoint. So here's how I >> propose we proceed >> >> 1. If the Caja dom is a little awkward wrap it, if not lets just use it as >> is. We can always resolve this later >> 2. Change the existing content rewriters to use the DOM instead of a >> lexer, >> should be pretty easy. Maybe add some fancier rewriting like moving CSS >> into >> HEAD >> 3. Do some perf testing, look into memory overhead of dom transformation >> etc. >> 4. Alter GadgetSpec's to retain the dom when they are cached >> 5. Alter the gadget rendering phase to serialize the content of the dom to >> output >> 6. Annotate the dom at parse time to make render time user-pref >> substituions >> faster, this should be easy enough too... >> >> This should be enough to prove out the pipeline end-to-end and identify >> any >> major perf niggles. Once this is done we can look into how to inject a >> rewriter pipeline into the parsing phase and the rendering phase. >> >> -Louis >> >> >> >> On Tue, Aug 12, 2008 at 5:57 PM, John Hjelmstad <[EMAIL PROTECTED]> wrote: >> >> > Re-responding in order to apply the last few exchanges to >> > google-caja-discuss@ (@gmail vs. @google membership issues). >> > >> > On Tue, Aug 12, 2008 at 4:48 PM, John Hjelmstad <[EMAIL PROTECTED]> >> wrote: >> > >> > > Hello, >> > > >> > > While beginning to refactor the rewriter APIs I've discovered that >> there >> > > unfortunately is one semantic difference inherent to moving >> getContent() >> > and >> > > setContent() methods into the Gadget object (replacing >> > > View.get/setRewrittenContent()): BasicGadgetSpecFactory no longer >> caches >> > > rewritten content. >> > > >> > > I've written a discussion of this in issue SHINDIG-500, which tracks >> this >> > > implementation sub-task: >> > https://issues.apache.org/jira/browse/SHINDIG-500 >> > > >> > > To summarize: >> > > 1. Is this change acceptable for the time being? >> > > 2. I suggest that we can, at a later date, move fetching of gadget >> specs >> > > into GadgetServer while injecting a Gadget(Spec) cache there as well, >> > > offering finer-tuned control over caching characteristics. >> > > >> > > Thanks, >> > > John >> > > >> > > >> > > On Mon, Aug 11, 2008 at 2:20 PM, John Hjelmstad <[EMAIL PROTECTED]> >> > wrote: >> > > >> > >> I understand these concerns, and should be clear that I don't >> (despite >> > my >> > >> personal interest in experimenting with the idea, agreed that we >> don't >> > have >> > >> time for it at the moment) have any plans to introduce this sort of >> RPC >> > >> anywhere - certainly not in Shindig itself, as any such call would be >> > hidden >> > >> behind an interface anyway. >> > >> >> > >> Putting the RPC hypothetical aside, I still feel that there's value >> to >> > >> implementing HTML parsing in terms of an interface: >> > >> * Clearer separation of concerns/boundary between projects. >> > >> - Corollary simplicity in testing. >> > >> * Clearer API for content manipulation (that doesn't require >> knowledge >> > of >> > >> Caja). >> > >> >> > >> I could be convinced otherwise, but at this point the code involved >> > seems >> > >> of manageable size, so still worth doing. Thoughts? >> > >> >> > >> John >> > >> >> > >> >> > >> >> > >> On Mon, Aug 11, 2008 at 1:00 PM, Kevin Brown <[EMAIL PROTECTED]> >> wrote: >> > >> >> > >>> I agree with Louis -- that's just not practical. Every rewriting >> > >>> operation >> > >>> must work in real time. Caja's existing html parser is adequate for >> our >> > >>> needs, and we shouldn't go out of our way to tolerate every oddity >> of >> > >>> random >> > >>> web browsers (especially as it simply wouldn't work unless you >> farmed >> > it >> > >>> out >> > >>> to *every* browser). Any new code needs to be grounded in practical, >> > >>> current >> > >>> needs, not theoretical options. We can always change code later if >> we >> > >>> find a >> > >>> real need for something like that. We have real work to do in the >> > >>> meantime. >> > >>> >> > >>> On Mon, Aug 11, 2008 at 12:06 PM, Louis Ryan <[EMAIL PROTECTED]> >> wrote: >> > >>> >> > >>> > John, >> > >>> > >> > >>> > From a practicality standpoint I'm a little nervous about this >> plan >> > to >> > >>> make >> > >>> > RPCs calls out of a Java process to a native process to fetch a >> parse >> > >>> tree >> > >>> > for transformations that have to occur realtime. I don't think the >> > >>> > motivating factor here is to accept all inputs that browsers can. >> > >>> Gadget >> > >>> > developers will tailor their markup to the platform as they have >> done >> > >>> > already. I would greatly prefer us to pick one 'good' parser and >> > stick >> > >>> with >> > >>> > it for all the manageability and consumability benefits that come >> > with >> > >>> that >> > >>> > decision. Perhaps Im missing something here? >> > >>> > >> > >>> > -Louis >> > >>> > >> > >>> > On Mon, Aug 11, 2008 at 11:59 AM, John Hjelmstad < >> [EMAIL PROTECTED]> >> > >>> wrote: >> > >>> > >> > >>> > > On Fri, Aug 8, 2008 at 6:10 AM, Ben Laurie <[EMAIL PROTECTED]> >> > wrote: >> > >>> > > >> > >>> > > > [+google-caja-discuss] >> > >>> > > > >> > >>> > > > On Thu, Aug 7, 2008 at 9:27 PM, John Hjelmstad < >> [EMAIL PROTECTED] >> > > >> > >>> > wrote: >> > >>> > > > > On Thu, Aug 7, 2008 at 3:20 AM, Ben Laurie <[EMAIL PROTECTED] >> > >> > >>> wrote: >> > >>> > > > > >> > >>> > > > >> On Wed, Aug 6, 2008 at 11:34 PM, John Hjelmstad < >> > >>> [EMAIL PROTECTED]> >> > >>> > > > wrote: >> > >>> > > > >> > This proposal effectively enables the renderer to become >> a >> > >>> > > multi-pass >> > >>> > > > >> > compiler for gadget content (essentially, arbitrary web >> > >>> content). >> > >>> > > Such >> > >>> > > > a >> > >>> > > > >> > compiler can provide several benefits: static >> optimization >> > of >> > >>> > gadget >> > >>> > > > >> content >> > >>> > > > >> > (auto-proxying of images, whitespace/comment removal, >> > >>> > consolidation >> > >>> > > of >> > >>> > > > >> CSS >> > >>> > > > >> > blocks), security benefits (caja et al), new >> functionality >> > >>> > > (annotation >> > >>> > > > of >> > >>> > > > >> > content for stats, document analysis, container-specific >> > >>> > features), >> > >>> > > > etc. >> > >>> > > > >> To >> > >>> > > > >> > my knowledge no such infrastructure exists today (with >> the >> > >>> > possible >> > >>> > > > >> > exception of Caja itself, which I'd like to dovetail with >> > this >> > >>> > > work). >> > >>> > > > >> >> > >>> > > > >> Caja clearly provides a large chunk of the code you'd need >> for >> > >>> this. >> > >>> > > > >> I'd like to hear how we'd manage to avoid duplication >> between >> > >>> the >> > >>> > two >> > >>> > > > >> projects. >> > >>> > > > >> >> > >>> > > > >> A generalised framework for manipulating content sounds >> like a >> > >>> great >> > >>> > > > >> idea, but probably should not live in either of the two >> > projects >> > >>> > (Caja >> > >>> > > > >> and Shindig) but rather should be shared by both of them, I >> > >>> suspect. >> > >>> > > > > >> > >>> > > > > >> > >>> > > > > I agree on both counts. As I mentioned, the piece of this >> idea >> > >>> that I >> > >>> > > > expect >> > >>> > > > > to change the most is the parse tree, and Caja's >> .parser.html >> > and >> > >>> > > > > .parser.css packages contain much of what I've thrown in >> here >> > as >> > >>> a >> > >>> > > base. >> > >>> > > > > >> > >>> > > > > My key requirements are: >> > >>> > > > > * Lightweight framework. >> > >>> > > > > * Parser modularity, mostly for HTML parsers (to re-use the >> > good >> > >>> work >> > >>> > > > done >> > >>> > > > > by WebKit or Gecko.. CSS/JS can come direct from Caja I'd >> bet) >> > >>> > > > > * Automatic maintenance of DOM<->String conversion. >> > >>> > > > > * Easy to manipulate structure. >> > >>> > > > >> > >>> > > > I'm not sure what the value of parser modularity is? If the >> > >>> resulting >> > >>> > > > tree is different, then that's a problem for people processing >> > the >> > >>> > > > tree. And if it is not, then why do we care? >> > >>> > > >> > >>> > > >> > >>> > > IMO the value of parser modularity is that the lenient parsers >> > native >> > >>> to >> > >>> > > browsers can be used in place of those that might not accept all >> > >>> inputs. >> > >>> > > One >> > >>> > > could (and I'd like to) adapt WebKit or Gecko's parsing code >> into a >> > >>> > server >> > >>> > > that runs parallel to Shindig and provides a "local RPC" service >> > for >> > >>> > > parsing >> > >>> > > semi-structured HTML. The resulting tree for WebKit's parser >> might >> > be >> > >>> > > different than that for an XHTML parser, Gecko's parser, etc, >> but >> > if >> > >>> the >> > >>> > > algorithm implemented atop it is rule-based rather than >> > >>> strict-structure >> > >>> > > based that should be fine, no? >> > >>> > > >> > >>> > > >> > >>> > > > >> > >>> > > > >> > >>> > > > > >> > >>> > > > > I'd love to see both projects share the same base syntax >> tree >> > >>> > > > > representations. I considered .parser.html(.DomTree) and >> > >>> .parser.css >> > >>> > > for >> > >>> > > > > these, but at the moment these appeared to be a little more >> > tied >> > >>> to >> > >>> > > > Caja's >> > >>> > > > > lexer/parser implementation than I preferred (though I admit >> > >>> > > > > AbstractParseTreeNode contains most of what's needed). >> > >>> > > > > >> > >>> > > > > To be sure, I don't see this as an end-all-be-all >> > transformation >> > >>> > system >> > >>> > > > in >> > >>> > > > > any way. I'd just like to put *something* reasonable in >> place >> > >>> that we >> > >>> > > can >> > >>> > > > > play with, provide some benefit, and enhance into a truly >> > >>> > sophisticated >> > >>> > > > > vision of document rewriting. >> > >>> > > > > >> > >>> > > > > >> > >>> > > > >> >> > >>> > > > >> >> > >>> > > > >> > c. Add Gadget.getParsedContent(). >> > >>> > > > >> > i. Returns a mutable GadgetContentParseTree used to >> > >>> manipulate >> > >>> > > > Gadget >> > >>> > > > >> > Contents. >> > >>> > > > >> > ii. Mutable tree calls back to the Gadget object >> > indicating >> > >>> > when >> > >>> > > > any >> > >>> > > > >> > change is made, and emits an error if setContent() has >> been >> > >>> called >> > >>> > > in >> > >>> > > > the >> > >>> > > > >> > interim. >> > >>> > > > >> >> > >>> > > > >> In Caja we have been moving towards immutable trees... >> > >>> > > > > >> > >>> > > > > >> > >>> > > > > Interested to hear more about this. The whole idea is for >> the >> > >>> > gadget's >> > >>> > > > tree >> > >>> > > > > representation to be modifiable. Doing that with immutable >> > trees >> > >>> to >> > >>> > me >> > >>> > > > > suggests that a rewriter would have to create a completely >> new >> > >>> tree >> > >>> > and >> > >>> > > > set >> > >>> > > > > it as a representation of new content. That's convenient as >> far >> > >>> as >> > >>> > the >> > >>> > > > > Gadget's maintenance of String<->Tree representations is >> > >>> concerned... >> > >>> > > but >> > >>> > > > > seems pretty heavyweight for many types of edits: in-situ >> > >>> > modifications >> > >>> > > > of >> > >>> > > > > text, content reordering, etc. That's particularly so in a >> > >>> > > > single-threaded >> > >>> > > > > (viz rewriting) environment. >> > >>> > > > >> > >>> > > > Never having been entirely sold on the concept, I'll let those >> on >> > >>> the >> > >>> > > > Caja team who advocate immutability explain why. >> > >>> > > > >> > >>> > > >> > >>> > >> > >>> >> > >> >> > >> >> > > >> > >> > >
