Changeset 166342 in webkit


Ignore:
Timestamp:
Mar 26, 2014 9:16:32 PM (10 years ago)
Author:
rniwa@webkit.org
Message:

Make _processText and _traverseNode in HTMLConverter more efficient
​https://bugs.webkit.org/show_bug.cgi?id=130769

Reviewed by Sam Weinig.

Rewrote a bunch of code in C++ and avoided creating wrappers.
This reduces the runtime of Interactive/CopyAll.html from ~16.5s to 15s.

  • editing/cocoa/HTMLConverter.mm:

(HTMLConverterCaches::isAncestorsOfStartToBeConverted):
(HTMLConverter::HTMLConverter):
(HTMLConverter::~HTMLConverter):
(HTMLConverter::_processElement):
(HTMLConverter::_processText):
(HTMLConverter::_traverseNode):
(HTMLConverter::_traverseFooterNode):
(HTMLConverterCaches::cacheAncestorsOfStartToBeConverted):
(HTMLConverter::_loadFromDOMRange):

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r166341 r166342  
     12014-03-26  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Make _processText and _traverseNode in HTMLConverter more efficient
     4        https://bugs.webkit.org/show_bug.cgi?id=130769
     5
     6        Reviewed by Sam Weinig.
     7
     8        Rewrote a bunch of code in C++ and avoided creating wrappers.
     9        This reduces the runtime of Interactive/CopyAll.html from ~16.5s to 15s.
     10
     11        * editing/cocoa/HTMLConverter.mm:
     12        (HTMLConverterCaches::isAncestorsOfStartToBeConverted):
     13        (HTMLConverter::HTMLConverter):
     14        (HTMLConverter::~HTMLConverter):
     15        (HTMLConverter::_processElement):
     16        (HTMLConverter::_processText):
     17        (HTMLConverter::_traverseNode):
     18        (HTMLConverter::_traverseFooterNode):
     19        (HTMLConverterCaches::cacheAncestorsOfStartToBeConverted):
     20        (HTMLConverter::_loadFromDOMRange):
     21
    1222014-03-26  Adenilson Cavalcanti  <cavalcantii@gmail.com>
    223

  • trunk/Source/WebCore/editing/cocoa/HTMLConverter.mm

    r166335 r166342  
    5050#import "FrameLoader.h"
    5151#import "HTMLElement.h"
     52#import "HTMLFrameElementBase.h"
    5253#import "HTMLNames.h"
    5354#import "HTMLParserIdioms.h"
    … …  
    6162#import <objc/runtime.h>
    6263#import <wtf/ASCIICType.h>
     64#import <wtf/text/StringBuilder.h>
    6365
    6466#if PLATFORM(IOS)
    … …  
    417419    PassRefPtr<CSSValue> inlineStylePropertyForElement(Element&, CSSPropertyID);
    418420
     421    Node* cacheAncestorsOfStartToBeConverted(const Range&);
     422    bool isAncestorsOfStartToBeConverted(Node* node) const { return m_ancestorsUnderCommonAncestor.contains(node); }
     423
    419424private:
    420425    HashMap<Element*, std::unique_ptr<ComputedStyleExtractor>> m_computedStyles;
     426    HashSet<Node*> m_ancestorsUnderCommonAncestor;
    421427};
    422428
    … …  
    455461    DOMDocument *_document;
    456462    DOMRange *_domRange;
    457     NSMutableArray *_domStartAncestors;
    458463    WebCore::DocumentLoader *_dataSource;
    459464    NSMutableArray *_textLists;
    … …  
    488493    PlatformColor *_colorForElement(Element&, CSSPropertyID);
    489494   
    490     void _traverseNode(DOMNode *node, NSInteger depth, BOOL embedded);
     495    void _traverseNode(Node* node, unsigned depth, bool embedded);
    491496    void _traverseFooterNode(DOMNode *node, NSInteger depth);
    492497   
    … …  
    511516    void _addMarkersToList(NSTextList *list, NSRange range);
    512517    void _exitElement(DOMElement *element, NSInteger depth, NSUInteger startIndex);
    513     void _processText(DOMCharacterData *text);
     518    void _processText(CharacterData&);
    514519    void _adjustTrailingNewline();
    515520};
    … …  
    522527    _baseURL = nil;
    523528    _document = nil;
    524     _domStartAncestors = nil;
    525529    _dataSource = nullptr;
    526530    _textLists = [[NSMutableArray alloc] init];
    … …  
    553557    [_documentAttrs release];
    554558    [_domRange release];
    555     [_domStartAncestors release];
    556559    [_textLists release];
    557560    [_textBlocks release];
    … …  
    19811984                retval = !_addAttachmentForElement(element, url, isBlockLevel, NO);
    19821985        }
    1983     } else if (coreElement.hasTagName(frameTag)) {
    1984         if ([element respondsToSelector:@selector(contentDocument)]) {
    1985             DOMDocument *contentDocument = [(DOMHTMLFrameElement *)element contentDocument];
    1986             if (contentDocument)
    1987                 _traverseNode(contentDocument, depth + 1, YES);
    1988         }
    1989         retval = NO;
    1990     } else if (coreElement.hasTagName(iframeTag)) {
    1991         if ([element respondsToSelector:@selector(contentDocument)]) {
    1992             DOMDocument *contentDocument = [(DOMHTMLIFrameElement *)element contentDocument];
    1993             if (contentDocument) {
    1994                 _traverseNode(contentDocument, depth + 1, YES);
    1995                 retval = NO;
    1996             }
     1986    } else if (coreElement.hasTagName(frameTag) || coreElement.hasTagName(iframeTag)) {
     1987        if (Document* contentDocument = toHTMLFrameElementBase(coreElement).contentDocument()) {
     1988            _traverseNode(contentDocument, depth + 1, true /* embedded */);
     1989            retval = NO;
    19971990        }
    19981991    } else if (coreElement.hasTagName(brTag)) {
    … …  
    22702263}
    22712264
    2272 void HTMLConverter::_processText(DOMCharacterData *text)
    2273 {
    2274     ASSERT(text);
    2275     CharacterData& characterData = *core(text);
    2276     NSString *instr = [text data];
    2277     NSString *outstr = instr;
     2265void HTMLConverter::_processText(CharacterData& characterData)
     2266{
    22782267    NSUInteger textLength = [_attrStr length];
    2279     NSUInteger startOffset = 0;
    2280     NSUInteger endOffset = [instr length];
    22812268    unichar lastChar = (textLength > 0) ? [[_attrStr string] characterAtIndex:textLength - 1] : '\n';
    2282     BOOL wasSpace = NO;
    2283     BOOL wasLeading = YES;
    22842269    BOOL suppressLeadingSpace = ((_flags.isSoft && lastChar == ' ') || lastChar == '\n' || lastChar == '\r' || lastChar == '\t' || lastChar == NSParagraphSeparatorCharacter || lastChar == NSLineSeparatorCharacter || lastChar == NSFormFeedCharacter || lastChar == WebNextLineCharacter);
    22852270    NSRange rangeToReplace = NSMakeRange(textLength, 0);
    22862271    CFMutableStringRef mutstr = NULL;
    22872272
     2273    String originalString = characterData.data();
     2274    unsigned startOffset = 0;
     2275    unsigned endOffset = originalString.length();
    22882276    if (_domRange) {
    2289         if (text == [_domRange startContainer]) {
     2277        if (&characterData == core([_domRange startContainer])) {
    22902278            startOffset = (NSUInteger)[_domRange startOffset];
    22912279            _domRangeStartIndex = [_attrStr length];
    22922280            _flags.reachedStart = YES;
    22932281        }
    2294         if (text == [_domRange endContainer]) {
     2282        if (&characterData == core([_domRange endContainer])) {
    22952283            endOffset = (NSUInteger)[_domRange endOffset];
    22962284            _flags.reachedEnd = YES;
    22972285        }
    2298         if ((startOffset > 0 || endOffset < [instr length]) && endOffset >= startOffset) {
    2299             instr = [instr substringWithRange:NSMakeRange(startOffset, endOffset - startOffset)];
    2300             outstr = instr;
    2301         }
    2302     }
    2303 
     2286        if ((startOffset > 0 || endOffset < originalString.length()) && endOffset >= startOffset)
     2287            originalString = originalString.substring(startOffset, endOffset - startOffset);
     2288    }
     2289    String outputString = originalString;
     2290
     2291    // FIXME: Use RenderText's content instead.
     2292    bool wasSpace = false;
    23042293    if (_caches->propertyValueForNode(characterData, CSSPropertyWhiteSpace).startsWith("pre")) {
    2305         if (textLength > 0 && [instr length] > 0 && _flags.isSoft) {
    2306             unichar c = [instr characterAtIndex:0];
     2294        if (textLength && originalString.length() && _flags.isSoft) {
     2295            unichar c = originalString.at(0);
    23072296            if (c == '\n' || c == '\r' || c == NSParagraphSeparatorCharacter || c == NSLineSeparatorCharacter || c == NSFormFeedCharacter || c == WebNextLineCharacter)
    23082297                rangeToReplace = NSMakeRange(textLength - 1, 1);
    23092298        }
    23102299    } else {
    2311         CFStringInlineBuffer inlineBuffer;
    2312         const unsigned int TextBufferSize = 255;
    2313 
    2314         unichar buffer[TextBufferSize + 1];
    2315         NSUInteger i, count = [instr length], idx = 0;
    2316 
    2317         mutstr = CFStringCreateMutable(NULL, 0);
    2318         CFStringInitInlineBuffer((CFStringRef)instr, &inlineBuffer, CFRangeMake(0, count));
    2319         for (i = 0; i < count; i++) {
    2320             unichar c = CFStringGetCharacterFromInlineBuffer(&inlineBuffer, i);
    2321             if (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == 0xc || c == 0x200b) {
     2300        unsigned count = originalString.length();
     2301        bool wasLeading = true;
     2302        StringBuilder builder;
     2303        for (unsigned i = 0; i < count; i++) {
     2304            UChar c = originalString.at(i);
     2305            bool isWhitespace = c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == 0xc || c == 0x200b;
     2306            if (isWhitespace)
    23222307                wasSpace = (!wasLeading || !suppressLeadingSpace);
    2323             } else {
     2308            else {
    23242309                if (wasSpace)
    2325                     buffer[idx++] = ' ';
    2326                 buffer[idx++] = c;
    2327                 if (idx >= TextBufferSize) {
    2328                     CFStringAppendCharacters(mutstr, buffer, idx);
    2329                     idx = 0;
    2330                 }
    2331                 wasSpace = wasLeading = NO;
     2310                    builder.append(' ');
     2311                builder.append(c);
     2312                wasSpace = false;
     2313                wasLeading = false;
    23322314            }
    23332315        }
    23342316        if (wasSpace)
    2335             buffer[idx++] = ' ';
    2336         if (idx > 0)
    2337             CFStringAppendCharacters(mutstr, buffer, idx);
    2338         outstr = (NSString *)mutstr;
    2339     }
    2340     if ([outstr length] > 0) {
     2317            builder.append(' ');
     2318        outputString = builder.toString();
     2319    }
     2320
     2321    if (outputString.length()) {
    23412322        String textTransform = _caches->propertyValueForNode(characterData, CSSPropertyTextTransform);
    23422323        if (textTransform.length()) {
    2343             if (textTransform == "capitalize")
    2344                 outstr = [outstr capitalizedString];
    2345             else if (textTransform == "uppercase")
    2346                 outstr = [outstr uppercaseString];
     2324            if (textTransform == "capitalize") {// FIXME: This is extremely inefficient.
     2325                NSString *temporaryString = outputString;
     2326                outputString = [temporaryString capitalizedString];
     2327            } else if (textTransform == "uppercase")
     2328                outputString = outputString.upper();
    23472329            else if (textTransform == "lowercase")
    2348                 outstr = [outstr lowercaseString];
    2349         }
    2350 
    2351         [_attrStr replaceCharactersInRange:rangeToReplace withString:outstr];
    2352         rangeToReplace.length = [outstr length];
     2330                outputString = outputString.lower();
     2331        }
     2332
     2333        [_attrStr replaceCharactersInRange:rangeToReplace withString:outputString];
     2334        rangeToReplace.length = outputString.length();
    23532335        RetainPtr<NSDictionary> attrs;
    2354         DOMElement *element = (DOMElement *)text;
    2355         while (element) {
     2336        Node* ancestor = characterData.parentNode();
     2337        while (ancestor) {
    23562338            // Fill attrs dictionary with attributes from parent nodes, not overwriting ones deeper in the tree
    2357             if([element nodeType] == DOM_ELEMENT_NODE) {
    2358                 RetainPtr<NSMutableDictionary> newAttrs = adoptNS([_attributesForElement(element) mutableCopy]);
     2339            if(ancestor->isElementNode()) {
     2340                RetainPtr<NSMutableDictionary> newAttrs = adoptNS([_attributesForElement(kit(toElement(ancestor))) mutableCopy]);
    23592341                if (attrs) {
    23602342                    // Already-set attributes (from lower in the tree) overwrite the higher ones.
    … …  
    23632345                attrs = newAttrs;
    23642346            }
    2365             element = (DOMElement *)[element parentNode];
     2347            ancestor = ancestor->parentNode();
    23662348        }
    23672349        if (rangeToReplace.length > 0)
    … …  
    23732355}
    23742356
    2375 void HTMLConverter::_traverseNode(DOMNode *node, NSInteger depth, BOOL embedded)
    2376 {
    2377     unsigned short nodeType;
    2378     NSArray *childNodes;
    2379     NSUInteger count;
    2380     NSUInteger startOffset;
    2381     NSUInteger endOffset;
    2382     BOOL isStart = NO;
    2383     BOOL isEnd = NO;
    2384 
    2385     if (_flags.reachedEnd)
     2357void HTMLConverter::_traverseNode(Node* node, unsigned depth, bool embedded)
     2358{
     2359    if (!node || _flags.reachedEnd)
    23862360        return;
    2387     if (_domRange && !_flags.reachedStart && _domStartAncestors && ![_domStartAncestors containsObject:node])
     2361    if (_domRange && !_flags.reachedStart && !_caches->isAncestorsOfStartToBeConverted(node))
    23882362        return;
    2389    
    2390     nodeType = [node nodeType];
    2391     childNodes = _childrenForNode(node);
    2392     count = [childNodes count];
    2393     startOffset = 0;
    2394     endOffset = count;
    2395 
     2363
     2364    unsigned startOffset = 0;
     2365    unsigned endOffset = UINT_MAX;
     2366    bool isStart = false;
     2367    bool isEnd = false;
    23962368    if (_domRange) {
    2397         if (node == [_domRange startContainer]) {
     2369        if (node == core([_domRange startContainer])) {
    23982370            startOffset = (NSUInteger)[_domRange startOffset];
    2399             isStart = YES;
     2371            isStart = true;
    24002372            _flags.reachedStart = YES;
    24012373        }
    2402         if (node == [_domRange endContainer]) {
     2374        if (node == core([_domRange endContainer])) {
    24032375            endOffset = (NSUInteger)[_domRange endOffset];
    2404             isEnd = YES;
    2405         }
    2406     }
    2407    
    2408     if (nodeType == DOM_DOCUMENT_NODE || nodeType == DOM_DOCUMENT_FRAGMENT_NODE) {
    2409         for (NSUInteger i = 0; i < count; i++) {
     2376            isEnd = true;
     2377        }
     2378    }
     2379   
     2380    if (node->isDocumentNode() || node->isDocumentFragment()) {
     2381        Node* child = node->firstChild();
     2382        for (NSUInteger i = 0; child; i++) {
    24102383            if (isStart && i == startOffset)
    24112384                _domRangeStartIndex = [_attrStr length];
    24122385            if ((!isStart || startOffset <= i) && (!isEnd || endOffset > i))
    2413                 _traverseNode([childNodes objectAtIndex:i], depth + 1, embedded);
     2386                _traverseNode(child, depth + 1, embedded);
    24142387            if (isEnd && i + 1 >= endOffset)
    24152388                _flags.reachedEnd = YES;
    2416             if (_flags.reachedEnd) break;
    2417         }
    2418     } else if (nodeType == DOM_ELEMENT_NODE) {
    2419         DOMElement *element = (DOMElement *)node;
     2389            if (_flags.reachedEnd)
     2390                break;
     2391            child = child->nextSibling();
     2392        }
     2393    } else if (node->isElementNode()) {
     2394        DOMElement* element = kit(toElement(node));
    24202395        if (_enterElement(element, embedded)) {
    24212396            NSUInteger startIndex = [_attrStr length];
    24222397            if (_processElement(element, depth)) {
    2423                 for (NSUInteger i = 0; i < count; i++) {
     2398                Node* child = node->firstChild();
     2399                for (NSUInteger i = 0; child; i++) {
    24242400                    if (isStart && i == startOffset)
    24252401                        _domRangeStartIndex = [_attrStr length];
    24262402                    if ((!isStart || startOffset <= i) && (!isEnd || endOffset > i))
    2427                         _traverseNode([childNodes objectAtIndex:i], depth + 1, embedded);
     2403                        _traverseNode(child, depth + 1, embedded);
    24282404                    if (isEnd && i + 1 >= endOffset)
    24292405                        _flags.reachedEnd = YES;
    24302406                    if (_flags.reachedEnd)
    24312407                        break;
     2408                    child = child->nextSibling();
    24322409                }
    24332410                _exitElement(element, depth, startIndex);
    24342411            }
    24352412        }
    2436     } else if (nodeType == DOM_TEXT_NODE || nodeType == DOM_CDATA_SECTION_NODE) {
    2437         _processText((DOMCharacterData *)node);
    2438     }
    2439    
     2413    } else if (node->isCharacterDataNode())
     2414        _processText(*toCharacterData(node));
     2415
    24402416    if (isEnd)
    24412417        _flags.reachedEnd = YES;
    … …  
    24452421{
    24462422    DOMElement *element = (DOMElement *)node;
    2447     NSArray *childNodes = _childrenForNode(node);
    2448     NSUInteger count = [childNodes count];
    2449     NSUInteger startOffset = 0;
    2450     NSUInteger endOffset = count;
    2451     BOOL isStart = NO;
    2452     BOOL isEnd = NO;
    24532423
    24542424    if (_flags.reachedEnd)
    24552425        return;
    2456     if (_domRange && !_flags.reachedStart && _domStartAncestors && ![_domStartAncestors containsObject:node])
     2426    if (_domRange && !_flags.reachedStart && !_caches->isAncestorsOfStartToBeConverted(core(node)))
    24572427        return;
     2428
     2429    unsigned startOffset = 0;
     2430    unsigned endOffset = UINT_MAX;
     2431    bool isStart = false;
     2432    bool isEnd = false;
    24582433    if (_domRange) {
    24592434        if (node == [_domRange startContainer]) {
    24602435            startOffset = (NSUInteger)[_domRange startOffset];
    2461             isStart = YES;
     2436            isStart = true;
    24622437            _flags.reachedStart = YES;
    24632438        }
    24642439        if (node == [_domRange endContainer]) {
    24652440            endOffset = (NSUInteger)[_domRange endOffset];
    2466             isEnd = YES;
     2441            isEnd = true;
    24672442        }
    24682443    }
    … …  
    24702445        NSUInteger startIndex = [_attrStr length];
    24712446        if (_processElement(element, depth)) {
    2472             for (NSUInteger i = 0; i < count; i++) {
     2447            Node* child = core(element)->firstChild();
     2448            for (NSUInteger i = 0; child; i++) {
    24732449                if (isStart && i == startOffset)
    24742450                    _domRangeStartIndex = [_attrStr length];
    24752451                if ((!isStart || startOffset <= i) && (!isEnd || endOffset > i))
    2476                     _traverseNode([childNodes objectAtIndex:i], depth + 1, YES);
     2452                    _traverseNode(child, depth + 1, true /* embedded */);
    24772453                if (isEnd && i + 1 >= endOffset)
    24782454                    _flags.reachedEnd = YES;
    24792455                if (_flags.reachedEnd)
    24802456                    break;
     2457                child = child->nextSibling();
    24812458            }
    24822459            _exitElement(element, depth, startIndex);
    … …  
    24962473}
    24972474
     2475Node* HTMLConverterCaches::cacheAncestorsOfStartToBeConverted(const Range& range)
     2476{
     2477    Node* commonAncestor = range.commonAncestorContainer(ASSERT_NO_EXCEPTION);
     2478    Node* ancestor = range.startContainer();
     2479
     2480    while (ancestor) {
     2481        m_ancestorsUnderCommonAncestor.add(ancestor);
     2482        if (ancestor == commonAncestor)
     2483            break;
     2484        ancestor = ancestor->parentNode();
     2485    }
     2486
     2487    return commonAncestor;
     2488}
     2489
    24982490void HTMLConverter::_loadFromDOMRange()
    24992491{
     2492    ASSERT(_domRange);
    25002493    if (-1 == _errorCode) {
    2501         DOMNode *commonAncestorContainer = [_domRange commonAncestorContainer];
    2502         DOMNode *ancestorContainer = [_domRange startContainer];
    2503        
    2504         _domStartAncestors = [[NSMutableArray alloc] init];
    2505         while (ancestorContainer) {
    2506             [_domStartAncestors addObject:ancestorContainer];
    2507             if (ancestorContainer == commonAncestorContainer)
    2508                 break;
    2509             ancestorContainer = [ancestorContainer parentNode];
    2510         }
    2511        
    2512         _document = [commonAncestorContainer ownerDocument];
     2494        Node* commonAncestorContainer = _caches->cacheAncestorsOfStartToBeConverted(*core(_domRange));
     2495        ASSERT(commonAncestorContainer);
     2496
     2497        _document = kit(commonAncestorContainer->ownerDocument());
    25132498        _dataSource = (DocumentLoader *)core(_document)->frame()->loader().documentLoader();
    25142499       
    … …  
    25162501            _domRangeStartIndex = 0;
    25172502            _errorCode = 0;
    2518             _traverseNode(commonAncestorContainer, 0, NO);
     2503            _traverseNode(commonAncestorContainer, 0, false /* embedded */);
    25192504            if (_domRangeStartIndex > 0 && _domRangeStartIndex <= [_attrStr length])
    25202505                [_attrStr deleteCharactersInRange:NSMakeRange(0, _domRangeStartIndex)];
Note: See TracChangeset for help on using the changeset viewer.