gfx/thebes/src/gfxTextRunWordCache.cpp

   1 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is Mozilla Foundation code.
  16  *
  17  * The Initial Developer of the Original Code is Mozilla Foundation.
  18  * Portions created by the Initial Developer are Copyright (C) 2006
  19  * the Initial Developer. All Rights Reserved.
  20  *
  21  * Contributor(s):
  22  *   Vladimir Vukicevic <vladimir@pobox.com>
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #include "gfxTextRunWordCache.h"
  39
  40 #ifdef DEBUG
  41 #include <stdio.h>
  42 #endif
  43
  44 /**
  45  * Cache individual "words" (strings delimited by white-space or white-space-like
  46  * characters that don't involve kerning or ligatures) in textruns.
  47  *
  48  * The characters treated as word boundaries are defined by IsWordBoundary
  49  * below. The characters are: space, NBSP, and all the characters
  50  * defined by gfxFontGroup::IsInvalidChar. The latter are all converted
  51  * to invisible missing glyphs in this code. Thus, this class ensures
  52  * that none of those invalid characters are ever passed to platform
  53  * textrun implementations.
  54  *
  55  * Some platforms support marks combining with spaces to form clusters.
  56  * In such cases we treat "before the space" as a word boundary but
  57  * "after the space" is not a word boundary; words with a leading space
  58  * are kept out of the cache. Also, words at the start of text, which start
  59  * with combining marks that would combine with a space if there was one,
  60  * are also kept out of the cache.
  61  */
  62
  63 class TextRunWordCache {
  64 public:
  65     TextRunWordCache() {
  66         mCache.Init(100);
  67     }
  68     ~TextRunWordCache() {
  69         NS_WARN_IF_FALSE(mCache.Count() == 0, "Textrun cache not empty!");
  70     }
  71
  72     /**
  73      * Create a textrun using cached words.
  74      * Invalid characters (see gfxFontGroup::IsInvalidChar) will be automatically
  75      * treated as invisible missing.
  76      * @param aFlags the flags TEXT_IS_ASCII and TEXT_HAS_SURROGATES must be set
  77      * by the caller, if applicable
  78      * @param aIsInCache if true is returned, then RemoveTextRun must be called
  79      * before the textrun changes or dies.
  80      */
  81     gfxTextRun *MakeTextRun(const PRUnichar *aText, PRUint32 aLength,
  82                             gfxFontGroup *aFontGroup,
  83                             const gfxFontGroup::Parameters *aParams,
  84                             PRUint32 aFlags);
  85     /**
  86      * Create a textrun using cached words.
  87      * Invalid characters (see gfxFontGroup::IsInvalidChar) will be automatically
  88      * treated as invisible missing.
  89      * @param aFlags the flag TEXT_IS_ASCII must be set by the caller,
  90      * if applicable
  91      * @param aIsInCache if true is returned, then RemoveTextRun must be called
  92      * before the textrun changes or dies.
  93      */
  94     gfxTextRun *MakeTextRun(const PRUint8 *aText, PRUint32 aLength,
  95                             gfxFontGroup *aFontGroup,
  96                             const gfxFontGroup::Parameters *aParams,
  97                             PRUint32 aFlags);
  98
  99     /**
 100      * Remove a textrun from the cache. This must be called before aTextRun
 101      * is deleted! The text in the textrun must still be valid.
 102      */
 103     void RemoveTextRun(gfxTextRun *aTextRun);
 104
 105 #ifdef DEBUG
 106     void Dump();
 107 #endif
 108
 109 protected:
 110     struct CacheHashKey {
 111         void        *mFontOrGroup;
 112         const void  *mString;
 113         PRUint32     mLength;
 114         PRUint32     mAppUnitsPerDevUnit;
 115         PRUint32     mStringHash;
 116         PRUint64     mUserFontSetGeneration;
 117         PRPackedBool mIsDoubleByteText;
 118         PRPackedBool mIsRTL;
 119         PRPackedBool mEnabledOptionalLigatures;
 120         PRPackedBool mOptimizeSpeed;
 121
 122         CacheHashKey(gfxTextRun *aBaseTextRun, void *aFontOrGroup,
 123                      PRUint32 aStart, PRUint32 aLength, PRUint32 aHash)
 124             : mFontOrGroup(aFontOrGroup), mString(aBaseTextRun->GetTextAt(aStart)),
 125               mLength(aLength),
 126               mAppUnitsPerDevUnit(aBaseTextRun->GetAppUnitsPerDevUnit()),
 127               mStringHash(aHash),
 128               mUserFontSetGeneration(aBaseTextRun->GetUserFontSetGeneration()),
 129               mIsDoubleByteText((aBaseTextRun->GetFlags() & gfxTextRunFactory::TEXT_IS_8BIT) == 0),
 130               mIsRTL(aBaseTextRun->IsRightToLeft()),
 131               mEnabledOptionalLigatures((aBaseTextRun->GetFlags() & gfxTextRunFactory::TEXT_DISABLE_OPTIONAL_LIGATURES) == 0),
 132               mOptimizeSpeed((aBaseTextRun->GetFlags() & gfxTextRunFactory::TEXT_OPTIMIZE_SPEED) != 0)
 133         {
 134         }
 135     };
 136
 137     class CacheHashEntry : public PLDHashEntryHdr {
 138     public:
 139         typedef const CacheHashKey &KeyType;
 140         typedef const CacheHashKey *KeyTypePointer;
 141
 142         // When constructing a new entry in the hashtable, the caller of Put()
 143         // will fill us in.
 144         CacheHashEntry(KeyTypePointer aKey) : mTextRun(nsnull), mWordOffset(0),
 145             mHashedByFont(PR_FALSE) { }
 146         CacheHashEntry(const CacheHashEntry& toCopy) { NS_ERROR("Should not be called"); }
 147         ~CacheHashEntry() { }
 148
 149         PRBool KeyEquals(const KeyTypePointer aKey) const;
 150         static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; }
 151         static PLDHashNumber HashKey(const KeyTypePointer aKey);
 152         enum { ALLOW_MEMMOVE = PR_TRUE };
 153
 154         gfxTextRun *mTextRun;
 155         // The offset of the start of the word in the textrun. The length of
 156         // the word is not stored here because we can figure it out by
 157         // looking at the textrun's text.
 158         PRUint32    mWordOffset:31;
 159         // This is set to true when the cache entry was hashed by the first
 160         // font in mTextRun's fontgroup; it's false when the cache entry
 161         // was hashed by the fontgroup itself.
 162         PRUint32    mHashedByFont:1;
 163     };
 164
 165     // Used to track words that should be copied from one textrun to
 166     // another during the textrun construction process
 167     struct DeferredWord {
 168         gfxTextRun *mSourceTextRun;
 169         PRUint32    mSourceOffset;
 170         PRUint32    mDestOffset;
 171         PRUint32    mLength;
 172         PRUint32    mHash;
 173     };
 174
 175     PRBool LookupWord(gfxTextRun *aTextRun, gfxFont *aFirstFont,
 176                       PRUint32 aStart, PRUint32 aEnd, PRUint32 aHash,
 177                       nsTArray<DeferredWord>* aDeferredWords);
 178     void FinishTextRun(gfxTextRun *aTextRun, gfxTextRun *aNewRun,
 179                        const gfxFontGroup::Parameters *aParams,
 180                        const nsTArray<DeferredWord>& aDeferredWords,
 181                        PRBool aSuccessful);
 182     void RemoveWord(gfxTextRun *aTextRun, PRUint32 aStart,
 183                     PRUint32 aEnd, PRUint32 aHash);
 184
 185     nsTHashtable<CacheHashEntry> mCache;
 186
 187 #ifdef DEBUG
 188     static PLDHashOperator CacheDumpEntry(CacheHashEntry* aEntry, void* userArg);
 189 #endif
 190 };
 191
 192 static PRLogModuleInfo *gWordCacheLog = PR_NewLogModule("wordCache");
 193
 194 static inline PRUint32
 195 HashMix(PRUint32 aHash, PRUnichar aCh)
 196 {
 197     return (aHash >> 28) ^ (aHash << 4) ^ aCh;
 198 }
 199
 200 // If the substring of the textrun is rendered entirely in the first font
 201 // of the textrun's fontgroup, then return that font. Otherwise return the
 202 // fontgroup.  When a user font set is in use, always return the font group.
 203 static void *GetWordFontOrGroup(gfxTextRun *aTextRun, PRUint32 aOffset,
 204                                 PRUint32 aLength)
 205 {
 206     gfxFontGroup *fontGroup = aTextRun->GetFontGroup();
 207     if (fontGroup->GetUserFontSet() != nsnull)
 208         return fontGroup;
 209
 210     PRUint32 glyphRunCount;
 211     const gfxTextRun::GlyphRun *glyphRuns = aTextRun->GetGlyphRuns(&glyphRunCount);
 212     PRUint32 glyphRunIndex = aTextRun->FindFirstGlyphRunContaining(aOffset);
 213     gfxFont *firstFont = fontGroup->GetFontAt(0);
 214     if (glyphRuns[glyphRunIndex].mFont != firstFont)
 215         return fontGroup;
 216
 217     PRUint32 glyphRunEnd = glyphRunIndex == glyphRunCount - 1
 218         ? aTextRun->GetLength() : glyphRuns[glyphRunIndex + 1].mCharacterOffset;
 219     if (aOffset + aLength <= glyphRunEnd)
 220         return firstFont;
 221     return fontGroup;
 222 }
 223
 224 #define UNICODE_NBSP 0x00A0
 225
 226 // XXX should we treat NBSP or SPACE combined with other characters as a word
 227 // boundary? Currently this does.
 228 static PRBool
 229 IsBoundarySpace(PRUnichar aChar)
 230 {
 231     return aChar == ' ' || aChar == UNICODE_NBSP;
 232 }
 233
 234 static PRBool
 235 IsWordBoundary(PRUnichar aChar)
 236 {
 237     return IsBoundarySpace(aChar) || gfxFontGroup::IsInvalidChar(aChar);
 238 }
 239
 240 /**
 241  * Looks up a word in the cache. If the word is found in the cache
 242  * (which could be from an existing textrun or an earlier word in the same
 243  * textrun), we copy the glyphs from the word into the textrun, unless
 244  * aDeferredWords is non-null (meaning that all words from now on must be
 245  * copied later instead of now), in which case we add the word to be copied
 246  * to the list.
 247  *
 248  * If the word is not found in the cache then we add it to the cache with
 249  * aFirstFont as the key, on the assumption that the word will be matched
 250  * by aFirstFont. If this assumption is false we fix up the cache later in
 251  * FinishTextRun. We make this assumption for two reasons:
 252  * 1) it's usually true so it saves an extra cache lookup if we had to insert
 253  * the entry later
 254  * 2) we need to record words that appear in the string in some kind
 255  * of hash table so we can detect and use them if they appear later in the
 256  * (in general the string might be huge and contain many repeated words).
 257  * We might as well use the master hash table for this.
 258  *
 259  * @return true if the word was found in the cache, false otherwise.
 260  */
 261 PRBool
 262 TextRunWordCache::LookupWord(gfxTextRun *aTextRun, gfxFont *aFirstFont,
 263                              PRUint32 aStart, PRUint32 aEnd, PRUint32 aHash,
 264                              nsTArray<DeferredWord>* aDeferredWords)
 265 {
 266     if (aEnd <= aStart)
 267         return PR_TRUE;
 268
 269     gfxFontGroup *fontGroup = aTextRun->GetFontGroup();
 270
 271     PRBool useFontGroup = (fontGroup->GetUserFontSet() != nsnull);
 272     CacheHashKey key(aTextRun, (useFontGroup ? (void*)fontGroup : (void*)aFirstFont), aStart, aEnd - aStart, aHash);
 273     CacheHashEntry *fontEntry = mCache.PutEntry(key);
 274     if (!fontEntry)
 275         return PR_FALSE;
 276     CacheHashEntry *existingEntry = nsnull;
 277
 278     if (fontEntry->mTextRun) {
 279         existingEntry = fontEntry;
 280     } else if (useFontGroup) {
 281         PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): added using font group", aTextRun, aStart, aEnd - aStart, aHash));
 282     } else {
 283         // test to see if this can be found using the font group instead
 284         PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): added using font", aTextRun, aStart, aEnd - aStart, aHash));
 285         key.mFontOrGroup = aTextRun->GetFontGroup();
 286         CacheHashEntry *groupEntry = mCache.GetEntry(key);
 287         if (groupEntry) {
 288             existingEntry = groupEntry;
 289             mCache.RawRemoveEntry(fontEntry);
 290             PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): removed using font", aTextRun, aStart, aEnd - aStart, aHash));
 291             fontEntry = nsnull;
 292         }
 293     }
 294     // At this point, either existingEntry is non-null and points to (surprise!)
 295     // an entry for a word in an existing textrun, or fontEntry points
 296     // to a cache entry for this word with aFirstFont, which needs to be
 297     // filled in or removed.
 298
 299     if (existingEntry) {
 300         if (aDeferredWords) {
 301             DeferredWord word = { existingEntry->mTextRun,
 302                   existingEntry->mWordOffset, aStart, aEnd - aStart, aHash };
 303             aDeferredWords->AppendElement(word);
 304         } else {
 305             aTextRun->CopyGlyphDataFrom(existingEntry->mTextRun,
 306                 existingEntry->mWordOffset, aEnd - aStart, aStart, PR_FALSE);
 307         }
 308         return PR_TRUE;
 309     }
 310
 311 #ifdef DEBUG
 312     ++aTextRun->mCachedWords;
 313 #endif
 314     // Set up the cache entry so that if later in this textrun we hit this
 315     // entry, we'll copy within our own textrun
 316     fontEntry->mTextRun = aTextRun;
 317     fontEntry->mWordOffset = aStart;
 318     if (!useFontGroup)
 319         fontEntry->mHashedByFont = PR_TRUE;
 320     return PR_FALSE;
 321 }
 322
 323 /**
 324  * Processes all deferred words. Each word is copied from the source
 325  * textrun to the output textrun. (The source may be an earlier word in the
 326  * output textrun.) If the word was not matched by the textrun's fontgroup's
 327  * first font, then we remove the entry we optimistically added to the cache
 328  * with that font in the key, and add a new entry keyed with the fontgroup
 329  * instead.
 330  *
 331  * @param aSuccessful if false, then we don't do any word copies and we don't
 332  * add anything to the cache, but we still remove all the optimistic cache
 333  * entries.
 334  */
 335 void
 336 TextRunWordCache::FinishTextRun(gfxTextRun *aTextRun, gfxTextRun *aNewRun,
 337                                 const gfxFontGroup::Parameters *aParams,
 338                                 const nsTArray<DeferredWord>& aDeferredWords,
 339                                 PRBool aSuccessful)
 340 {
 341     aTextRun->SetFlagBits(gfxTextRunWordCache::TEXT_IN_CACHE);
 342
 343     PRUint32 i;
 344     gfxFontGroup *fontGroup = aTextRun->GetFontGroup();
 345     gfxFont *font = fontGroup->GetFontAt(0);
 346
 347     // need to use the font group when user font set is around, since
 348     // the first font may change as the result of a font download
 349     PRBool useFontGroup = (fontGroup->GetUserFontSet() != nsnull);
 350
 351     // copy deferred words from various sources into destination textrun
 352     for (i = 0; i < aDeferredWords.Length(); ++i) {
 353         const DeferredWord *word = &aDeferredWords[i];
 354         gfxTextRun *source = word->mSourceTextRun;
 355         if (!source) {
 356             source = aNewRun;
 357         }
 358         // If the word starts inside a cluster we don't want this word
 359         // in the cache, so we'll remove the associated cache entry
 360         PRBool wordStartsInsideCluster =
 361             !source->IsClusterStart(word->mSourceOffset);
 362         PRBool wordStartsInsideLigature =
 363             !source->IsLigatureGroupStart(word->mSourceOffset);
 364         if (source == aNewRun) {
 365             // We created a cache entry for this word based on the assumption
 366             // that the word matches GetFontAt(0). If this assumption is false,
 367             // we need to remove that cache entry and replace it with an entry
 368             // keyed off the fontgroup.
 369             PRBool rekeyWithFontGroup =
 370                 GetWordFontOrGroup(aNewRun, word->mSourceOffset, word->mLength) != font && !useFontGroup;
 371             if (!aSuccessful || rekeyWithFontGroup ||
 372                 wordStartsInsideCluster || wordStartsInsideLigature) {
 373                 // We need to remove the current placeholder cache entry
 374                 CacheHashKey key(aTextRun, (useFontGroup ? (void*)fontGroup : (void*)font), word->mDestOffset, word->mLength,
 375                                  word->mHash);
 376                 NS_ASSERTION(mCache.GetEntry(key),
 377                              "This entry should have been added previously!");
 378                 mCache.RemoveEntry(key);
 379 #ifdef DEBUG
 380                 --aTextRun->mCachedWords;
 381 #endif
 382                 PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): removed using font", aTextRun, word->mDestOffset, word->mLength, word->mHash));
 383
 384                 if (aSuccessful && !wordStartsInsideCluster && !wordStartsInsideLigature) {
 385                     key.mFontOrGroup = fontGroup;
 386                     CacheHashEntry *groupEntry = mCache.PutEntry(key);
 387                     if (groupEntry) {
 388 #ifdef DEBUG
 389                         ++aTextRun->mCachedWords;
 390 #endif
 391                         PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): added using fontgroup", aTextRun, word->mDestOffset, word->mLength, word->mHash));
 392                         groupEntry->mTextRun = aTextRun;
 393                         groupEntry->mWordOffset = word->mDestOffset;
 394                         groupEntry->mHashedByFont = PR_FALSE;
 395                         NS_ASSERTION(mCache.GetEntry(key),
 396                                      "We should find the thing we just added!");
 397                     }
 398                 }
 399             }
 400         }
 401         if (aSuccessful) {
 402             // Copy the word. If the source is aNewRun, then
 403             // allow CopyGlyphDataFrom to steal the internal data of
 404             // aNewRun since that's only temporary anyway.
 405             PRUint32 sourceOffset = word->mSourceOffset;
 406             PRUint32 destOffset = word->mDestOffset;
 407             PRUint32 length = word->mLength;
 408             nsAutoPtr<gfxTextRun> tmpTextRun;
 409             PRBool stealData = source == aNewRun;
 410             if (wordStartsInsideCluster || wordStartsInsideLigature) {
 411                 NS_ASSERTION(sourceOffset > 0, "How can the first character be inside a cluster?");
 412                 if (wordStartsInsideCluster && destOffset > 0 &&
 413                     IsBoundarySpace(aTextRun->GetChar(destOffset - 1))) {
 414                     // The first character of the word formed a cluster
 415                     // with the preceding space.
 416                     // We should copy over data for the preceding space
 417                     // as well. The glyphs have probably been attached
 418                     // to that character.
 419                     --sourceOffset;
 420                     --destOffset;
 421                     ++length;
 422                 } else {
 423                     // URK! This case sucks! We have combining marks or
 424                     // part of a ligature at the start of the text. We
 425                     // had to prepend a space just so we could detect this
 426                     // situation (so we can keep this "word" out of the
 427                     // cache). But now the data in aNewRun is no use to us.
 428                     // We need to find out what the platform would do
 429                     // if the characters were at the start of the text.
 430                     tmpTextRun = aNewRun->GetFontGroup()->MakeTextRun(
 431                         source->GetTextUnicode() + sourceOffset, length, aParams,
 432                         aNewRun->GetFlags());
 433                     source = tmpTextRun;
 434                     sourceOffset = 0;
 435                     stealData = PR_TRUE;
 436                 }
 437             }
 438             aTextRun->CopyGlyphDataFrom(source, sourceOffset, length,
 439                 destOffset, stealData);
 440             // Fill in additional spaces
 441             PRUint32 endCharIndex;
 442             if (i + 1 < aDeferredWords.Length()) {
 443                 endCharIndex = aDeferredWords[i + 1].mDestOffset;
 444             } else {
 445                 endCharIndex = aTextRun->GetLength();
 446             }
 447             PRUint32 charIndex;
 448             for (charIndex = word->mDestOffset + word->mLength;
 449                  charIndex < endCharIndex; ++charIndex) {
 450                 if (IsBoundarySpace(aTextRun->GetChar(charIndex))) {
 451                     aTextRun->SetSpaceGlyph(font, aParams->mContext, charIndex);
 452                 }
 453             }
 454         }
 455     }
 456 }
 457
 458 static gfxTextRun *
 459 MakeBlankTextRun(const void* aText, PRUint32 aLength,
 460                          gfxFontGroup *aFontGroup,
 461                          const gfxFontGroup::Parameters *aParams,
 462                          PRUint32 aFlags)
 463 {
 464     nsAutoPtr<gfxTextRun> textRun;
 465     textRun = gfxTextRun::Create(aParams, aText, aLength, aFontGroup, aFlags);
 466     if (!textRun || !textRun->GetCharacterGlyphs())
 467         return nsnull;
 468     gfxFont *font = aFontGroup->GetFontAt(0);
 469     textRun->AddGlyphRun(font, 0);
 470     return textRun.forget();
 471 }
 472
 473 gfxTextRun *
 474 TextRunWordCache::MakeTextRun(const PRUnichar *aText, PRUint32 aLength,
 475                               gfxFontGroup *aFontGroup,
 476                               const gfxFontGroup::Parameters *aParams,
 477                               PRUint32 aFlags)
 478 {
 479     // update font list when using user fonts (assures generation is current)
 480     aFontGroup->UpdateFontList();
 481
 482     if (aFontGroup->GetStyle()->size == 0) {
 483         // Short-circuit for size-0 fonts, as Windows and ATSUI can't handle
 484         // them, and always create at least size 1 fonts, i.e. they still
 485         // render something for size 0 fonts.
 486         return MakeBlankTextRun(aText, aLength, aFontGroup, aParams, aFlags);
 487     }
 488
 489     nsAutoPtr<gfxTextRun> textRun;
 490     textRun = gfxTextRun::Create(aParams, aText, aLength, aFontGroup, aFlags);
 491     if (!textRun || !textRun->GetCharacterGlyphs())
 492         return nsnull;
 493 #ifdef DEBUG
 494     textRun->mCachedWords = 0;
 495 #endif
 496
 497     gfxFont *font = aFontGroup->GetFontAt(0);
 498     nsresult rv = textRun->AddGlyphRun(font, 0);
 499     NS_ENSURE_SUCCESS(rv, nsnull);
 500
 501     nsAutoTArray<PRUnichar,200> tempString;
 502     nsAutoTArray<DeferredWord,50> deferredWords;
 503     PRUint32 i;
 504     PRUint32 wordStart = 0;
 505     PRUint32 hash = 0;
 506     for (i = 0; i <= aLength; ++i) {
 507         PRUnichar ch = i < aLength ? aText[i] : ' ';
 508         if (IsWordBoundary(ch)) {
 509             PRBool hit = LookupWord(textRun, font, wordStart, i, hash,
 510                                     deferredWords.Length() == 0 ? nsnull : &deferredWords);
 511             if (!hit) {
 512                 // Always put a space before the word so we can detect
 513                 // combining characters at the start of a word
 514                 tempString.AppendElement(' ');
 515                 PRUint32 offset = tempString.Length();
 516                 PRUint32 length = i - wordStart;
 517                 PRUnichar *chars = tempString.AppendElements(length);
 518                 if (!chars) {
 519                     FinishTextRun(textRun, nsnull, nsnull, deferredWords, PR_FALSE);
 520                     return nsnull;
 521                 }
 522                 memcpy(chars, aText + wordStart, length*sizeof(PRUnichar));
 523                 DeferredWord word = { nsnull, offset, wordStart, length, hash };
 524                 deferredWords.AppendElement(word);
 525             }
 526
 527             if (deferredWords.Length() == 0) {
 528                 if (IsBoundarySpace(ch) && i < aLength) {
 529                     textRun->SetSpaceGlyph(font, aParams->mContext, i);
 530                 } // else we should set this character to be invisible missing,
 531                   // but it already is because the textrun is blank!
 532             }
 533             hash = 0;
 534             wordStart = i + 1;
 535         } else {
 536             hash = HashMix(hash, ch);
 537         }
 538     }
 539
 540     if (deferredWords.Length() == 0) {
 541         // We got everything from the cache, so we're done. No point in calling
 542         // FinishTextRun.
 543         // This textrun is not referenced by the cache.
 544         return textRun.forget();
 545     }
 546
 547     // create textrun for unknown words
 548     gfxTextRunFactory::Parameters params =
 549         { aParams->mContext, nsnull, nsnull, nsnull, 0, aParams->mAppUnitsPerDevUnit };
 550     nsAutoPtr<gfxTextRun> newRun;
 551     newRun = aFontGroup->MakeTextRun(tempString.Elements(), tempString.Length(),
 552                                      &params, aFlags | gfxTextRunFactory::TEXT_IS_PERSISTENT);
 553
 554     FinishTextRun(textRun, newRun, aParams, deferredWords, newRun != nsnull);
 555     return textRun.forget();
 556 }
 557
 558 gfxTextRun *
 559 TextRunWordCache::MakeTextRun(const PRUint8 *aText, PRUint32 aLength,
 560                               gfxFontGroup *aFontGroup,
 561                               const gfxFontGroup::Parameters *aParams,
 562                               PRUint32 aFlags)
 563 {
 564     // update font list when using user fonts (assures generation is current)
 565     aFontGroup->UpdateFontList();
 566
 567     if (aFontGroup->GetStyle()->size == 0) {
 568         // Short-circuit for size-0 fonts, as Windows and ATSUI can't handle
 569         // them, and always create at least size 1 fonts, i.e. they still
 570         // render something for size 0 fonts.
 571         return MakeBlankTextRun(aText, aLength, aFontGroup, aParams, aFlags);
 572     }
 573
 574     aFlags |= gfxTextRunFactory::TEXT_IS_8BIT;
 575     nsAutoPtr<gfxTextRun> textRun;
 576     textRun = gfxTextRun::Create(aParams, aText, aLength, aFontGroup, aFlags);
 577     if (!textRun || !textRun->GetCharacterGlyphs())
 578         return nsnull;
 579 #ifdef DEBUG
 580     textRun->mCachedWords = 0;
 581 #endif
 582
 583     gfxFont *font = aFontGroup->GetFontAt(0);
 584     nsresult rv = textRun->AddGlyphRun(font, 0);
 585     NS_ENSURE_SUCCESS(rv, nsnull);
 586
 587     nsAutoTArray<PRUint8,200> tempString;
 588     nsAutoTArray<DeferredWord,50> deferredWords;
 589     PRUint32 i;
 590     PRUint32 wordStart = 0;
 591     PRUint32 hash = 0;
 592     for (i = 0; i <= aLength; ++i) {
 593         PRUint8 ch = i < aLength ? aText[i] : ' ';
 594         if (IsWordBoundary(ch)) {
 595             PRBool hit = LookupWord(textRun, font, wordStart, i, hash,
 596                                     deferredWords.Length() == 0 ? nsnull : &deferredWords);
 597             if (!hit) {
 598                 if (tempString.Length() > 0) {
 599                     tempString.AppendElement(' ');
 600                 }
 601                 PRUint32 offset = tempString.Length();
 602                 PRUint32 length = i - wordStart;
 603                 PRUint8 *chars = tempString.AppendElements(length);
 604                 if (!chars) {
 605                     FinishTextRun(textRun, nsnull, nsnull, deferredWords, PR_FALSE);
 606                     return nsnull;
 607                 }
 608                 memcpy(chars, aText + wordStart, length*sizeof(PRUint8));
 609                 DeferredWord word = { nsnull, offset, wordStart, length, hash };
 610                 deferredWords.AppendElement(word);
 611             }
 612
 613             if (deferredWords.Length() == 0) {
 614                 if (IsBoundarySpace(ch) && i < aLength) {
 615                     textRun->SetSpaceGlyph(font, aParams->mContext, i);
 616                 } // else we should set this character to be invisible missing,
 617                   // but it already is because the textrun is blank!
 618             }
 619             hash = 0;
 620             wordStart = i + 1;
 621         } else {
 622             hash = HashMix(hash, ch);
 623         }
 624     }
 625
 626     if (deferredWords.Length() == 0) {
 627         // We got everything from the cache, so we're done. No point in calling
 628         // FinishTextRun.
 629         // This textrun is not referenced by the cache.
 630         return textRun.forget();
 631     }
 632
 633     // create textrun for unknown words
 634     gfxTextRunFactory::Parameters params =
 635         { aParams->mContext, nsnull, nsnull, nsnull, 0, aParams->mAppUnitsPerDevUnit };
 636     nsAutoPtr<gfxTextRun> newRun;
 637     newRun = aFontGroup->MakeTextRun(tempString.Elements(), tempString.Length(),
 638                                      &params, aFlags | gfxTextRunFactory::TEXT_IS_PERSISTENT);
 639
 640     FinishTextRun(textRun, newRun, aParams, deferredWords, newRun != nsnull);
 641     return textRun.forget();
 642 }
 643
 644 void
 645 TextRunWordCache::RemoveWord(gfxTextRun *aTextRun, PRUint32 aStart,
 646                              PRUint32 aEnd, PRUint32 aHash)
 647 {
 648     if (aEnd <= aStart)
 649         return;
 650
 651     PRUint32 length = aEnd - aStart;
 652     CacheHashKey key(aTextRun, GetWordFontOrGroup(aTextRun, aStart, length),
 653                      aStart, length, aHash);
 654
 655     CacheHashEntry *entry = mCache.GetEntry(key);
 656     if (entry && entry->mTextRun == aTextRun) {
 657         // XXX would like to use RawRemoveEntry here plus some extra method
 658         // that conditionally shrinks the hashtable
 659         mCache.RemoveEntry(key);
 660 #ifdef DEBUG
 661         --aTextRun->mCachedWords;
 662 #endif
 663         PR_LOG(gWordCacheLog, PR_LOG_DEBUG, ("%p(%d-%d,%d): removed using %s",
 664             aTextRun, aStart, length, aHash,
 665             key.mFontOrGroup == aTextRun->GetFontGroup() ? "fontgroup" : "font"));
 666     }
 667 }
 668
 669 // Remove a textrun from the cache by looking up each word and removing it
 670 void
 671 TextRunWordCache::RemoveTextRun(gfxTextRun *aTextRun)
 672 {
 673     PRUint32 i;
 674     PRUint32 wordStart = 0;
 675     PRUint32 hash = 0;
 676     for (i = 0; i < aTextRun->GetLength(); ++i) {
 677         PRUnichar ch = aTextRun->GetChar(i);
 678         if (IsWordBoundary(ch)) {
 679             RemoveWord(aTextRun, wordStart, i, hash);
 680             hash = 0;
 681             wordStart = i + 1;
 682         } else {
 683             hash = HashMix(hash, ch);
 684         }
 685     }
 686     RemoveWord(aTextRun, wordStart, i, hash);
 687 #ifdef DEBUG
 688     NS_ASSERTION(aTextRun->mCachedWords == 0,
 689                  "Textrun was not completely removed from the cache!");
 690 #endif
 691 }
 692
 693 static PRBool
 694 CompareDifferentWidthStrings(const PRUint8 *aStr1, const PRUnichar *aStr2,
 695                              PRUint32 aLength)
 696 {
 697     PRUint32 i;
 698     for (i = 0; i < aLength; ++i) {
 699         if (aStr1[i] != aStr2[i])
 700             return PR_FALSE;
 701     }
 702     return PR_TRUE;
 703 }
 704
 705 static PRBool
 706 IsWordEnd(gfxTextRun *aTextRun, PRUint32 aOffset)
 707 {
 708     PRUint32 runLength = aTextRun->GetLength();
 709     if (aOffset == runLength)
 710         return PR_TRUE;
 711     if (aOffset > runLength)
 712         return PR_FALSE;
 713     return IsWordBoundary(aTextRun->GetChar(aOffset));
 714 }
 715
 716 static void *
 717 GetFontOrGroup(gfxFontGroup *aFontGroup, PRBool aUseFont)
 718 {
 719     return aUseFont
 720         ? static_cast<void *>(aFontGroup->GetFontAt(0))
 721         : static_cast<void *>(aFontGroup);
 722 }
 723
 724 PRBool
 725 TextRunWordCache::CacheHashEntry::KeyEquals(const KeyTypePointer aKey) const
 726 {
 727     if (!mTextRun)
 728         return PR_FALSE;
 729
 730     PRUint32 length = aKey->mLength;
 731     gfxFontGroup *fontGroup = mTextRun->GetFontGroup();
 732     if (!IsWordEnd(mTextRun, mWordOffset + length) ||
 733         GetFontOrGroup(fontGroup, mHashedByFont) != aKey->mFontOrGroup ||
 734         aKey->mAppUnitsPerDevUnit != mTextRun->GetAppUnitsPerDevUnit() ||
 735         aKey->mIsRTL != mTextRun->IsRightToLeft() ||
 736         aKey->mEnabledOptionalLigatures != ((mTextRun->GetFlags() & gfxTextRunFactory::TEXT_DISABLE_OPTIONAL_LIGATURES) == 0) ||
 737         aKey->mOptimizeSpeed != ((mTextRun->GetFlags() & gfxTextRunFactory::TEXT_OPTIMIZE_SPEED) != 0) ||
 738         aKey->mUserFontSetGeneration != (mTextRun->GetUserFontSetGeneration()))
 739         return PR_FALSE;
 740
 741     if (mTextRun->GetFlags() & gfxFontGroup::TEXT_IS_8BIT) {
 742         const PRUint8 *text = mTextRun->GetText8Bit() + mWordOffset;
 743         if (!aKey->mIsDoubleByteText)
 744             return memcmp(text, aKey->mString, length) == 0;
 745         return CompareDifferentWidthStrings(text,
 746                                             static_cast<const PRUnichar *>(aKey->mString), length);
 747     } else {
 748         const PRUnichar *text = mTextRun->GetTextUnicode() + mWordOffset;
 749         if (aKey->mIsDoubleByteText)
 750             return memcmp(text, aKey->mString, length*sizeof(PRUnichar)) == 0;
 751         return CompareDifferentWidthStrings(static_cast<const PRUint8 *>(aKey->mString),
 752                                             text, length);
 753     }
 754 }
 755
 756 PLDHashNumber
 757 TextRunWordCache::CacheHashEntry::HashKey(const KeyTypePointer aKey)
 758 {
 759     // only use lower 32 bits of generation counter in hash key,
 760     // since these vary the most
 761     PRUint32 fontSetGen;
 762     LL_L2UI(fontSetGen, aKey->mUserFontSetGeneration);
 763
 764     return aKey->mStringHash + fontSetGen + (long)aKey->mFontOrGroup + aKey->mAppUnitsPerDevUnit +
 765         aKey->mIsDoubleByteText + aKey->mIsRTL*2 + aKey->mEnabledOptionalLigatures*4 +
 766         aKey->mOptimizeSpeed*8;
 767 }
 768
 769 #ifdef DEBUG
 770 PLDHashOperator
 771 TextRunWordCache::CacheDumpEntry(CacheHashEntry* aEntry, void* userArg)
 772 {
 773     FILE* output = static_cast<FILE*>(userArg);
 774     if (!aEntry->mTextRun) {
 775         fprintf(output, "<EMPTY>\n");
 776         return PL_DHASH_NEXT;
 777     }
 778     fprintf(output, "Word at %p:%d => ", static_cast<void*>(aEntry->mTextRun), aEntry->mWordOffset);
 779     aEntry->mTextRun->Dump(output);
 780     fprintf(output, " (hashed by %s)\n", aEntry->mHashedByFont ? "font" : "fontgroup");
 781     return PL_DHASH_NEXT;
 782 }
 783
 784 void
 785 TextRunWordCache::Dump()
 786 {
 787     mCache.EnumerateEntries(CacheDumpEntry, stdout);
 788 }
 789 #endif
 790
 791 static TextRunWordCache *gTextRunWordCache = nsnull;
 792
 793 nsresult
 794 gfxTextRunWordCache::Init()
 795 {
 796     gTextRunWordCache = new TextRunWordCache();
 797     return gTextRunWordCache ? NS_OK : NS_ERROR_OUT_OF_MEMORY;
 798 }
 799
 800 void
 801 gfxTextRunWordCache::Shutdown()
 802 {
 803     delete gTextRunWordCache;
 804     gTextRunWordCache = nsnull;
 805 }
 806
 807 gfxTextRun *
 808 gfxTextRunWordCache::MakeTextRun(const PRUnichar *aText, PRUint32 aLength,
 809                                  gfxFontGroup *aFontGroup,
 810                                  const gfxFontGroup::Parameters *aParams,
 811                                  PRUint32 aFlags)
 812 {
 813     if (!gTextRunWordCache)
 814         return nsnull;
 815     return gTextRunWordCache->MakeTextRun(aText, aLength, aFontGroup, aParams, aFlags);
 816 }
 817
 818 gfxTextRun *
 819 gfxTextRunWordCache::MakeTextRun(const PRUint8 *aText, PRUint32 aLength,
 820                                  gfxFontGroup *aFontGroup,
 821                                  const gfxFontGroup::Parameters *aParams,
 822                                  PRUint32 aFlags)
 823 {
 824     if (!gTextRunWordCache)
 825         return nsnull;
 826     return gTextRunWordCache->MakeTextRun(aText, aLength, aFontGroup, aParams, aFlags);
 827 }
 828
 829 void
 830 gfxTextRunWordCache::RemoveTextRun(gfxTextRun *aTextRun)
 831 {
 832     if (!gTextRunWordCache)
 833         return;
 834     gTextRunWordCache->RemoveTextRun(aTextRun);
 835 }