Bug 130820 - HTMLConverter::_processText is slow because it walks up ancestor elements
Summary: HTMLConverter::_processText is slow because it walks up ancestor elements
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords:
Depends on:
Blocks: 130227
  Show dependency tree / graph
 
Reported: 2014-03-26 22:30 PDT by Ryosuke Niwa
Modified: 2014-03-26 23:23 PDT (History)
5 users (show)

See Also:

Attachments
Adds a new cache (4.99 KB, patch)
2014-03-26 22:35 PDT, Ryosuke Niwa 		no flags Details | Formatted Diff | Diff
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2014-03-26 22:30:53 PDT 
Right now HTMLConverter::_processText walks up the entire ancestor chain to merge their attributed strings.
Doing that for every text node results in O(kn) runtime complexity where k is the depth of the tree and n is the number of text nodes in the tree.
Comment 1 Ryosuke Niwa 2014-03-26 22:35:46 PDT 
Created attachment 227922 [details]
Adds a new cache
Comment 2 WebKit Commit Bot 2014-03-26 23:23:15 PDT 
Comment on attachment 227922 [details]
Adds a new cache

Clearing flags on attachment: 227922

Committed r166347: <http://trac.webkit.org/changeset/166347>
Comment 3 WebKit Commit Bot 2014-03-26 23:23:18 PDT 
All reviewed patches have been landed.  Closing bug.