src/fcmatch.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
   3  *
   4  * Copyright © 2000 Keith Packard
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 #include <string.h>
  26 #include <ctype.h>
  27 #include "fcint.h"
  28 #include <stdio.h>
  29
  30 static double
  31 FcCompareNumber (FcValue *value1, FcValue *value2)
  32 {
  33     double  v1, v2, v;
  34
  35     switch (value1->type) {
  36     case FcTypeInteger:
  37         v1 = (double) value1->u.i;
  38         break;
  39     case FcTypeDouble:
  40         v1 = value1->u.d;
  41         break;
  42     default:
  43         return -1.0;
  44     }
  45     switch (value2->type) {
  46     case FcTypeInteger:
  47         v2 = (double) value2->u.i;
  48         break;
  49     case FcTypeDouble:
  50         v2 = value2->u.d;
  51         break;
  52     default:
  53         return -1.0;
  54     }
  55     v = v2 - v1;
  56     if (v < 0)
  57         v = -v;
  58     return v;
  59 }
  60
  61 static double
  62 FcCompareString (FcValue *v1, FcValue *v2)
  63 {
  64     return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
  65 }
  66
  67 static double
  68 FcCompareFamily (FcValue *v1, FcValue *v2)
  69 {
  70     /* rely on the guarantee in FcPatternAddWithBinding that
  71      * families are always FcTypeString. */
  72     const FcChar8* v1_string = fc_value_string(v1);
  73     const FcChar8* v2_string = fc_value_string(v2);
  74
  75     if (FcToLower(*v1_string) != FcToLower(*v2_string))
  76        return 1.0;
  77
  78     return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
  79 }
  80
  81 static double
  82 FcCompareLang (FcValue *v1, FcValue *v2)
  83 {
  84     FcLangResult    result;
  85     FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
  86
  87     switch (value1.type) {
  88     case FcTypeLangSet:
  89         switch (value2.type) {
  90         case FcTypeLangSet:
  91             result = FcLangSetCompare (value1.u.l, value2.u.l);
  92             break;
  93         case FcTypeString:
  94             result = FcLangSetHasLang (value1.u.l,
  95                                        value2.u.s);
  96             break;
  97         default:
  98             return -1.0;
  99         }
 100         break;
 101     case FcTypeString:
 102         switch (value2.type) {
 103         case FcTypeLangSet:
 104             result = FcLangSetHasLang (value2.u.l, value1.u.s);
 105             break;
 106         case FcTypeString:
 107             result = FcLangCompare (value1.u.s,
 108                                     value2.u.s);
 109             break;
 110         default:
 111             return -1.0;
 112         }
 113         break;
 114     default:
 115         return -1.0;
 116     }
 117     switch (result) {
 118     case FcLangEqual:
 119         return 0;
 120     case FcLangDifferentCountry:
 121         return 1;
 122     case FcLangDifferentLang:
 123     default:
 124         return 2;
 125     }
 126 }
 127
 128 static double
 129 FcCompareBool (FcValue *v1, FcValue *v2)
 130 {
 131     if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
 132         return -1.0;
 133     return (double) v2->u.b != v1->u.b;
 134 }
 135
 136 static double
 137 FcCompareCharSet (FcValue *v1, FcValue *v2)
 138 {
 139     return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
 140 }
 141
 142 static double
 143 FcCompareSize (FcValue *value1, FcValue *value2)
 144 {
 145     double  v1, v2, v;
 146
 147     switch (value1->type) {
 148     case FcTypeInteger:
 149         v1 = value1->u.i;
 150         break;
 151     case FcTypeDouble:
 152         v1 = value1->u.d;
 153         break;
 154     default:
 155         return -1;
 156     }
 157     switch (value2->type) {
 158     case FcTypeInteger:
 159         v2 = value2->u.i;
 160         break;
 161     case FcTypeDouble:
 162         v2 = value2->u.d;
 163         break;
 164     default:
 165         return -1;
 166     }
 167     if (v2 == 0)
 168         return 0;
 169     v = v2 - v1;
 170     if (v < 0)
 171         v = -v;
 172     return v;
 173 }
 174
 175 typedef struct _FcMatcher {
 176     const char      *object;
 177     FcObjectPtr     objectPtr;
 178     double          (*compare) (FcValue *value1, FcValue *value2);
 179     int             strong, weak;
 180 } FcMatcher;
 181
 182 /*
 183  * Order is significant, it defines the precedence of
 184  * each value, earlier values are more significant than
 185  * later values
 186  */
 187 static FcMatcher _FcMatchers [] = {
 188     { FC_FOUNDRY,       0, FcCompareString,     0, 0 },
 189 #define MATCH_FOUNDRY       0
 190 #define MATCH_FOUNDRY_INDEX 0
 191
 192     { FC_CHARSET,       0, FcCompareCharSet,    1, 1 },
 193 #define MATCH_CHARSET       1
 194 #define MATCH_CHARSET_INDEX 1
 195
 196     { FC_FAMILY,        0, FcCompareFamily,     2, 4 },
 197 #define MATCH_FAMILY        2
 198 #define MATCH_FAMILY_STRONG_INDEX   2
 199 #define MATCH_FAMILY_WEAK_INDEX     4
 200
 201     { FC_LANG,          0, FcCompareLang,       3, 3 },
 202 #define MATCH_LANG          3
 203 #define MATCH_LANG_INDEX    3
 204
 205     { FC_SPACING,       0, FcCompareNumber,     5, 5 },
 206 #define MATCH_SPACING       4
 207 #define MATCH_SPACING_INDEX 5
 208
 209     { FC_PIXEL_SIZE,    0, FcCompareSize,       6, 6 },
 210 #define MATCH_PIXEL_SIZE    5
 211 #define MATCH_PIXEL_SIZE_INDEX  6
 212
 213     { FC_STYLE,         0, FcCompareString,     7, 7 },
 214 #define MATCH_STYLE         6
 215 #define MATCH_STYLE_INDEX   7
 216
 217     { FC_SLANT,         0, FcCompareNumber,     8, 8 },
 218 #define MATCH_SLANT         7
 219 #define MATCH_SLANT_INDEX   8
 220
 221     { FC_WEIGHT,        0, FcCompareNumber,     9, 9 },
 222 #define MATCH_WEIGHT        8
 223 #define MATCH_WEIGHT_INDEX  9
 224
 225     { FC_WIDTH,         0, FcCompareNumber,     10, 10 },
 226 #define MATCH_WIDTH         9
 227 #define MATCH_WIDTH_INDEX   10
 228
 229     { FC_ANTIALIAS,     0, FcCompareBool,       11, 11 },
 230 #define MATCH_ANTIALIAS     10
 231 #define MATCH_ANTIALIAS_INDEX       11
 232
 233     { FC_RASTERIZER,    0, FcCompareString,     12, 12 },
 234 #define MATCH_RASTERIZER    11
 235 #define MATCH_RASTERIZER_INDEX    12
 236
 237     { FC_OUTLINE,       0, FcCompareBool,       13, 13 },
 238 #define MATCH_OUTLINE       12
 239 #define MATCH_OUTLINE_INDEX         13
 240
 241     { FC_FONTVERSION,   0, FcCompareNumber,     14, 14 },
 242 #define MATCH_FONTVERSION   13
 243 #define MATCH_FONTVERSION_INDEX   14
 244 };
 245
 246 #define NUM_MATCH_VALUES    15
 247
 248 static FcBool matchObjectPtrsInit = FcFalse;
 249
 250 static void
 251 FcMatchObjectPtrsInit (void)
 252 {
 253     _FcMatchers[MATCH_FOUNDRY].objectPtr = FcObjectToPtr(FC_FOUNDRY);
 254     _FcMatchers[MATCH_CHARSET].objectPtr = FcObjectToPtr(FC_CHARSET);
 255     _FcMatchers[MATCH_FAMILY].objectPtr = FcObjectToPtr(FC_FAMILY);
 256     _FcMatchers[MATCH_LANG].objectPtr = FcObjectToPtr(FC_LANG);
 257     _FcMatchers[MATCH_SPACING].objectPtr = FcObjectToPtr(FC_SPACING);
 258     _FcMatchers[MATCH_PIXEL_SIZE].objectPtr = FcObjectToPtr(FC_PIXEL_SIZE);
 259     _FcMatchers[MATCH_STYLE].objectPtr = FcObjectToPtr(FC_STYLE);
 260     _FcMatchers[MATCH_SLANT].objectPtr = FcObjectToPtr(FC_SLANT);
 261     _FcMatchers[MATCH_WEIGHT].objectPtr = FcObjectToPtr(FC_WEIGHT);
 262     _FcMatchers[MATCH_WIDTH].objectPtr = FcObjectToPtr(FC_WIDTH);
 263     _FcMatchers[MATCH_ANTIALIAS].objectPtr = FcObjectToPtr(FC_ANTIALIAS);
 264     _FcMatchers[MATCH_RASTERIZER].objectPtr = FcObjectToPtr(FC_RASTERIZER);
 265     _FcMatchers[MATCH_OUTLINE].objectPtr = FcObjectToPtr(FC_OUTLINE);
 266     _FcMatchers[MATCH_FONTVERSION].objectPtr = FcObjectToPtr(FC_FONTVERSION);
 267     matchObjectPtrsInit = FcTrue;
 268 }
 269
 270 static FcMatcher*
 271 FcObjectPtrToMatcher (FcObjectPtr o)
 272 {
 273     int         i;
 274     const char  *object = FcObjectPtrU(o);
 275
 276     i = -1;
 277     switch (object[0]) {
 278     case 'f':
 279         switch (object[1]) {
 280         case 'o':
 281             switch (object[2]) {
 282             case 'u':
 283                 i = MATCH_FOUNDRY; break;
 284             case 'n':
 285                 i = MATCH_FONTVERSION; break;
 286             }
 287             break;
 288         case 'a':
 289             i = MATCH_FAMILY; break;
 290         }
 291         break;
 292     case 'c':
 293         i = MATCH_CHARSET; break;
 294     case 'a':
 295         i = MATCH_ANTIALIAS; break;
 296     case 'l':
 297         i = MATCH_LANG; break;
 298     case 's':
 299         switch (object[1]) {
 300         case 'p':
 301             i = MATCH_SPACING; break;
 302         case 't':
 303             i = MATCH_STYLE; break;
 304         case 'l':
 305             i = MATCH_SLANT; break;
 306         }
 307         break;
 308     case 'p':
 309         i = MATCH_PIXEL_SIZE; break;
 310     case 'w':
 311         switch (object[1]) {
 312         case 'i':
 313             i = MATCH_WIDTH; break;
 314         case 'e':
 315             i = MATCH_WEIGHT; break;
 316         }
 317         break;
 318     case 'r':
 319         i = MATCH_RASTERIZER; break;
 320     case 'o':
 321         i = MATCH_OUTLINE; break;
 322     }
 323
 324     if (i < 0)
 325         return 0;
 326
 327     if (!matchObjectPtrsInit)
 328         FcMatchObjectPtrsInit();
 329
 330     if (o != _FcMatchers[i].objectPtr)
 331         return 0;
 332
 333     return _FcMatchers+i;
 334 }
 335
 336 static FcBool
 337 FcCompareValueList (FcObjectPtr o,
 338                     FcValueListPtr v1orig,      /* pattern */
 339                     FcValueListPtr v2orig,      /* target */
 340                     FcValue     *bestValue,
 341                     double      *value,
 342                     FcResult    *result)
 343 {
 344     FcValueListPtr  v1, v2;
 345     FcValueList     *v1_ptrU, *v2_ptrU;
 346     double          v, best, bestStrong, bestWeak;
 347     int             j;
 348     const char      *object = FcObjectPtrU(o);
 349     FcMatcher       *match = FcObjectPtrToMatcher(o);
 350
 351     if (!match)
 352     {
 353         if (bestValue)
 354             *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
 355         return FcTrue;
 356     }
 357
 358     best = 1e99;
 359     bestStrong = 1e99;
 360     bestWeak = 1e99;
 361     j = 0;
 362     for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
 363          v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1))
 364     {
 365         for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); v2_ptrU;
 366              v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
 367         {
 368             v = (match->compare) (&v1_ptrU->value, &v2_ptrU->value);
 369             if (v < 0)
 370             {
 371                 *result = FcResultTypeMismatch;
 372                 return FcFalse;
 373             }
 374             v = v * 100 + j;
 375             if (v < best)
 376             {
 377                 if (bestValue)
 378                     *bestValue = FcValueCanonicalize(&v2_ptrU->value);
 379                 best = v;
 380             }
 381             if (v1_ptrU->binding == FcValueBindingStrong)
 382             {
 383                 if (v < bestStrong)
 384                     bestStrong = v;
 385             }
 386             else
 387             {
 388                 if (v < bestWeak)
 389                     bestWeak = v;
 390             }
 391         }
 392         j++;
 393     }
 394     if (FcDebug () & FC_DBG_MATCHV)
 395     {
 396         printf (" %s: %g ", object, best);
 397         FcValueListPrint (v1orig);
 398         printf (", ");
 399         FcValueListPrint (v2orig);
 400         printf ("\n");
 401     }
 402     if (value)
 403     {
 404         int weak    = match->weak;
 405         int strong  = match->strong;
 406         if (weak == strong)
 407             value[strong] += best;
 408         else
 409         {
 410             value[weak] += bestWeak;
 411             value[strong] += bestStrong;
 412         }
 413     }
 414     return FcTrue;
 415 }
 416
 417 /*
 418  * Return a value indicating the distance between the two lists of
 419  * values
 420  */
 421
 422 static FcBool
 423 FcCompare (FcPattern    *pat,
 424            FcPattern    *fnt,
 425            double       *value,
 426            FcResult     *result)
 427 {
 428     int             i, i1, i2;
 429
 430     for (i = 0; i < NUM_MATCH_VALUES; i++)
 431         value[i] = 0.0;
 432
 433     i1 = 0;
 434     i2 = 0;
 435     while (i1 < pat->num && i2 < fnt->num)
 436     {
 437         FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
 438         FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
 439
 440         i = FcObjectPtrCompare(elt_i1->object, elt_i2->object);
 441         if (i > 0)
 442             i2++;
 443         else if (i < 0)
 444             i1++;
 445         else
 446         {
 447             if (!FcCompareValueList (elt_i1->object,
 448                                      elt_i1->values, elt_i2->values,
 449                                      0, value, result))
 450                 return FcFalse;
 451             i1++;
 452             i2++;
 453         }
 454     }
 455     return FcTrue;
 456 }
 457
 458 FcPattern *
 459 FcFontRenderPrepare (FcConfig       *config,
 460                      FcPattern      *pat,
 461                      FcPattern      *font)
 462 {
 463     FcPattern       *new;
 464     int             i;
 465     FcPatternElt    *fe, *pe;
 466     FcValue         v;
 467     FcResult        result;
 468
 469     new = FcPatternCreate ();
 470     if (!new)
 471         return 0;
 472     for (i = 0; i < font->num; i++)
 473     {
 474         fe = FcPatternEltU(font->elts)+i;
 475         pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
 476         if (pe)
 477         {
 478             if (!FcCompareValueList (pe->object, pe->values,
 479                                      fe->values, &v, 0, &result))
 480             {
 481                 FcPatternDestroy (new);
 482                 return 0;
 483             }
 484         }
 485         else
 486             v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
 487         FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
 488     }
 489     for (i = 0; i < pat->num; i++)
 490     {
 491         pe = FcPatternEltU(pat->elts)+i;
 492         fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
 493         if (!fe)
 494             FcPatternAdd (new, FcObjectPtrU(pe->object),
 495                           FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
 496     }
 497
 498     if (FcPatternFindElt (font, FC_FILE))
 499         FcPatternTransferFullFname (new, font);
 500
 501     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 502     return new;
 503 }
 504
 505 FcPattern *
 506 FcFontSetMatch (FcConfig    *config,
 507                 FcFontSet   **sets,
 508                 int         nsets,
 509                 FcPattern   *p,
 510                 FcResult    *result)
 511 {
 512     double          score;
 513     double          bestscore;
 514     int             f;
 515     FcFontSet       *s;
 516     FcPattern       *best;
 517     int             scoring_index;
 518     int             *sets_offset;
 519     int             set;
 520     int             nfonts;
 521     int             fonts_left;
 522     FcMatcher       *matcher;
 523     FcMatcher       *strong_matchers[NUM_MATCH_VALUES];
 524     FcMatcher       *weak_matchers[NUM_MATCH_VALUES];
 525     FcPatternElt    *pat_elts[NUM_MATCH_VALUES];
 526     int             pat_elt;
 527     int             *match_blocked;
 528     int             block_start;
 529
 530     if (!nsets || !sets || !p)
 531     {
 532         *result = FcResultNoMatch;
 533         return 0;
 534     }
 535
 536     if (FcDebug () & FC_DBG_MATCH)
 537     {
 538         printf ("Match ");
 539         FcPatternPrint (p);
 540     }
 541     if (!config)
 542     {
 543         config = FcConfigGetCurrent ();
 544         if (!config)
 545         {
 546             *result = FcResultOutOfMemory;
 547             return 0;
 548         }
 549     }
 550
 551     sets_offset = (int *)calloc(nsets, sizeof (int));
 552
 553     nfonts = 0;
 554     for (set = 0; set < nsets; ++set)
 555     {
 556         sets_offset[set] = nfonts;
 557         if (sets[set])
 558             nfonts += sets[set]->nfont;
 559     }
 560
 561     fonts_left = nfonts;
 562
 563     match_blocked = (int*)calloc(nfonts, sizeof(int));
 564
 565     /* Find out all necessary matchers first, so we don't need to find them
 566      * in every loop.
 567      */
 568
 569     memset(strong_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
 570     memset(weak_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
 571     memset(pat_elts, 0, sizeof (FcPatternElt*) * NUM_MATCH_VALUES);
 572
 573     for (pat_elt = 0; pat_elt < p->num; ++pat_elt)
 574     {
 575         matcher = FcObjectPtrToMatcher
 576                         ((FcPatternEltU(p->elts)+pat_elt)->object);
 577         if (matcher)
 578         {
 579             strong_matchers[matcher->strong] = matcher;
 580             weak_matchers[matcher->weak] = matcher;
 581             pat_elts [matcher->strong] = pat_elts [matcher->weak] =
 582                     (FcPatternEltU(p->elts)+pat_elt);
 583         }
 584     }
 585
 586     /* The old algorithm checked if each font beat 'best',
 587      * scanning all of the value lists for all of the pattern elts. */
 588     /* This algorithm checks each font on a element-by-element basis
 589      * and blocks fonts that have already lost on some element from
 590      * further consideration from being best.  Basically, we've
 591      * swapped the order of loops and short-circuited fonts that
 592      * are out of contention right away.
 593      * This saves a lot of time! */
 594     best = 0;
 595     block_start = 0;
 596     for (scoring_index = 0; scoring_index < NUM_MATCH_VALUES; ++scoring_index)
 597     {
 598         FcValueListPtr  v1;
 599         FcValueList     *v1_ptrU;
 600         int             v1_offset = 0;
 601
 602         if (!strong_matchers [scoring_index] && !weak_matchers [scoring_index])
 603             continue;
 604
 605         for (v1 = pat_elts[scoring_index]->values, v1_ptrU = FcValueListPtrU(v1);
 606              v1_ptrU;
 607              v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1), ++v1_offset)
 608         {
 609             matcher = (v1_ptrU->binding == FcValueBindingWeak) ?
 610                 weak_matchers[scoring_index] : strong_matchers[scoring_index];
 611
 612             if (!matcher) continue;
 613
 614             bestscore = 1e99;
 615
 616             if (FcDebug () & FC_DBG_MATCHV)
 617             {
 618                 printf("Scoring Index %d, Value %d: %d(%d) fonts left\n",
 619                         scoring_index, v1_offset, fonts_left, nfonts);
 620             }
 621
 622             for (set = 0; set < nsets; ++set)
 623             {
 624                 s = sets[set];
 625                 if (!s) continue;
 626
 627                 /* All fonts before block_start should have been knocked out. */
 628                 for (f = (block_start > sets_offset[set]) ? (block_start - sets_offset[set]) : 0;
 629                      f < s->nfont; ++f)
 630                 {
 631                     int             cand_elt;
 632                     FcPatternElt    *cand_elts;
 633
 634                     if (match_blocked[f + sets_offset[set]] == 1)
 635                         continue;
 636
 637                     score = 1e99;
 638                     cand_elts = FcPatternEltU(s->fonts[f]->elts);
 639
 640                     /* Look for the appropriate element in this candidate
 641                      * pattern 'f' and evaluate its score wrt 'p'. */
 642                     for (cand_elt = 0; cand_elt < s->fonts[f]->num; ++cand_elt)
 643                     {
 644                         if (cand_elts[cand_elt].object == pat_elts[scoring_index]->object)
 645                         {
 646                             FcValueListPtr  v2;
 647                             FcValueList     *v2_ptrU;
 648
 649                             for (v2 = cand_elts[cand_elt].values, v2_ptrU = FcValueListPtrU(v2);
 650                                  v2_ptrU;
 651                                  v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
 652                             {
 653                                 double v = (matcher->compare)(&v1_ptrU->value, &v2_ptrU->value);
 654
 655                                 if (v < 0)
 656                                 {
 657                                     *result = FcResultTypeMismatch;
 658                                     free (match_blocked);
 659                                     free (sets_offset);
 660                                     return 0;
 661                                 }
 662
 663                                 /* I'm actually kind of surprised that
 664                                  * this isn't v + 100 * v1_offset. -PL */
 665                                 v = v * 100 + v1_offset;
 666                                 /* The old patch said score += v, which
 667                                  * seems to be wrong when you have
 668                                  * multiple matchers.  This takes the
 669                                  * best score it can find for that font. */
 670                                 if (v < score)
 671                                     score = v;
 672                             }
 673                         }
 674                     }
 675
 676                     /* We had no matching, just try the next one */
 677                     if (score == 1e99)
 678                     {
 679                         match_blocked[f + sets_offset[set]] = 2;
 680                         continue;
 681                     }
 682                     match_blocked[f + sets_offset[set]] = 0;
 683                     /* If there's a previous champion, and current score
 684                      * beats previous best score, on this element, then
 685                      * knock out the previous champion and anything
 686                      * else that we would have visited previous to f;
 687                      * clearly anything previous to f would have been
 688                      * less than f on this score. */
 689                     if (!best || score < bestscore)
 690                     {
 691                         if (best)
 692                         {
 693                             int b;
 694                             for (b = block_start; b < f + sets_offset[set]; ++b)
 695                                 if (!match_blocked[b])
 696                                 {
 697                                     match_blocked[b] = 1;
 698                                     --fonts_left;
 699                                 }
 700                         }
 701
 702                         bestscore = score;
 703                         best = s->fonts[f];
 704                         /* This kills too many fonts, unfortunately. */
 705                         /* block_start = f + sets_offset[set]; */
 706                     }
 707
 708                     /* If f loses, then it's out too. */
 709                     if (best && score > bestscore)
 710                     {
 711                         match_blocked[f + sets_offset[set]] = 1;
 712                         --fonts_left;
 713                     }
 714
 715                     /* If there is only 1 font left and the best is set,
 716                      * then just return this font
 717                      */
 718                     if (fonts_left == 1 && best)
 719                         goto end;
 720
 721                     /* Otherwise, f is equal to best on this element.
 722                      * Carry on to next pattern element. */
 723                 }
 724             }
 725             if ((FcDebug () & FC_DBG_MATCHV) && best)
 726             {
 727                 printf ("Best match (scoring index %d) candidate %d ", scoring_index, block_start);
 728                 FcPatternPrint (best);
 729             }
 730         }
 731     }
 732
 733 end:
 734     free (match_blocked);
 735     free (sets_offset);
 736
 737     if ((FcDebug () & FC_DBG_MATCH) && best)
 738     {
 739         printf ("Best match (scoring index %d) %d ", scoring_index, block_start);
 740         FcPatternPrint (best);
 741     }
 742     if (!best)
 743     {
 744         *result = FcResultNoMatch;
 745         return 0;
 746     }
 747     return FcFontRenderPrepare (config, p, best);
 748 }
 749
 750 FcPattern *
 751 FcFontMatch (FcConfig   *config,
 752              FcPattern  *p,
 753              FcResult   *result)
 754 {
 755     FcFontSet   *sets[2];
 756     int         nsets;
 757
 758     if (!config)
 759     {
 760         config = FcConfigGetCurrent ();
 761         if (!config)
 762             return 0;
 763     }
 764     nsets = 0;
 765     if (config->fonts[FcSetSystem])
 766         sets[nsets++] = config->fonts[FcSetSystem];
 767     if (config->fonts[FcSetApplication])
 768         sets[nsets++] = config->fonts[FcSetApplication];
 769     return FcFontSetMatch (config, sets, nsets, p, result);
 770 }
 771
 772 typedef struct _FcSortNode {
 773     FcPattern   *pattern;
 774     double      score[NUM_MATCH_VALUES];
 775 } FcSortNode;
 776
 777 static int
 778 FcSortCompare (const void *aa, const void *ab)
 779 {
 780     FcSortNode  *a = *(FcSortNode **) aa;
 781     FcSortNode  *b = *(FcSortNode **) ab;
 782     double      *as = &a->score[0];
 783     double      *bs = &b->score[0];
 784     double      ad = 0, bd = 0;
 785     int         i;
 786
 787     i = NUM_MATCH_VALUES;
 788     while (i-- && (ad = *as++) == (bd = *bs++))
 789         ;
 790     return ad < bd ? -1 : ad > bd ? 1 : 0;
 791 }
 792
 793 static FcBool
 794 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
 795 {
 796     FcCharSet   *ncs;
 797     FcSortNode  *node;
 798
 799     while (nnode--)
 800     {
 801         node = *n++;
 802         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 803             FcResultMatch)
 804         {
 805             /*
 806              * If this font isn't a subset of the previous fonts,
 807              * add it to the list
 808              */
 809             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 810             {
 811                 if (trim || build_cs)
 812                 {
 813                     if (*cs)
 814                     {
 815                         ncs = FcCharSetUnion (ncs, *cs);
 816                         if (!ncs)
 817                             return FcFalse;
 818                         FcCharSetDestroy (*cs);
 819                     }
 820                     else
 821                         ncs = FcCharSetCopy (ncs);
 822                     *cs = ncs;
 823                 }
 824
 825                 FcPatternReference (node->pattern);
 826                 if (FcDebug () & FC_DBG_MATCH)
 827                 {
 828                     printf ("Add ");
 829                     FcPatternPrint (node->pattern);
 830                 }
 831                 if (!FcFontSetAdd (fs, node->pattern))
 832                 {
 833                     FcPatternDestroy (node->pattern);
 834                     return FcFalse;
 835                 }
 836             }
 837         }
 838     }
 839     return FcTrue;
 840 }
 841
 842 void
 843 FcFontSetSortDestroy (FcFontSet *fs)
 844 {
 845     FcFontSetDestroy (fs);
 846 }
 847
 848 FcFontSet *
 849 FcFontSetSort (FcConfig     *config,
 850                FcFontSet    **sets,
 851                int          nsets,
 852                FcPattern    *p,
 853                FcBool       trim,
 854                FcCharSet    **csp,
 855                FcResult     *result)
 856 {
 857     FcFontSet       *ret;
 858     FcFontSet       *s;
 859     FcSortNode      *nodes;
 860     FcSortNode      **nodeps, **nodep;
 861     int             nnodes;
 862     FcSortNode      *new;
 863     FcCharSet       *cs;
 864     int             set;
 865     int             f;
 866     int             i;
 867     int             nPatternLang;
 868     FcBool          *patternLangSat;
 869     FcValue         patternLang;
 870
 871     if (FcDebug () & FC_DBG_MATCH)
 872     {
 873         printf ("Sort ");
 874         FcPatternPrint (p);
 875     }
 876     nnodes = 0;
 877     for (set = 0; set < nsets; set++)
 878     {
 879         s = sets[set];
 880         if (!s)
 881             continue;
 882         nnodes += s->nfont;
 883     }
 884     if (!nnodes)
 885         goto bail0;
 886
 887     for (nPatternLang = 0;
 888          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
 889          nPatternLang++)
 890         ;
 891
 892     /* freed below */
 893     nodes = malloc (nnodes * sizeof (FcSortNode) +
 894                     nnodes * sizeof (FcSortNode *) +
 895                     nPatternLang * sizeof (FcBool));
 896     if (!nodes)
 897         goto bail0;
 898     nodeps = (FcSortNode **) (nodes + nnodes);
 899     patternLangSat = (FcBool *) (nodeps + nnodes);
 900
 901     new = nodes;
 902     nodep = nodeps;
 903     for (set = 0; set < nsets; set++)
 904     {
 905         s = sets[set];
 906         if (!s)
 907             continue;
 908         for (f = 0; f < s->nfont; f++)
 909         {
 910             if (FcDebug () & FC_DBG_MATCHV)
 911             {
 912                 printf ("Font %d ", f);
 913                 FcPatternPrint (s->fonts[f]);
 914             }
 915             new->pattern = s->fonts[f];
 916             if (!FcCompare (p, new->pattern, new->score, result))
 917                 goto bail1;
 918             if (FcDebug () & FC_DBG_MATCHV)
 919             {
 920                 printf ("Score");
 921                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 922                 {
 923                     printf (" %g", new->score[i]);
 924                 }
 925                 printf ("\n");
 926             }
 927             *nodep = new;
 928             new++;
 929             nodep++;
 930         }
 931     }
 932
 933     nnodes = new - nodes;
 934
 935     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 936            FcSortCompare);
 937
 938     for (i = 0; i < nPatternLang; i++)
 939         patternLangSat[i] = FcFalse;
 940
 941     for (f = 0; f < nnodes; f++)
 942     {
 943         FcBool  satisfies = FcFalse;
 944         /*
 945          * If this node matches any language, go check
 946          * which ones and satisfy those entries
 947          */
 948         if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
 949         {
 950             for (i = 0; i < nPatternLang; i++)
 951             {
 952                 FcValue     nodeLang;
 953
 954                 if (!patternLangSat[i] &&
 955                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
 956                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
 957                 {
 958                     double  compare = FcCompareLang (&patternLang, &nodeLang);
 959                     if (compare >= 0 && compare < 2)
 960                     {
 961                         if (FcDebug () & FC_DBG_MATCHV)
 962                         {
 963                             FcChar8 *family;
 964                             FcChar8 *style;
 965
 966                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
 967                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
 968                                 printf ("Font %s:%s matches language %d\n", family, style, i);
 969                         }
 970                         patternLangSat[i] = FcTrue;
 971                         satisfies = FcTrue;
 972                         break;
 973                     }
 974                 }
 975             }
 976         }
 977         if (!satisfies)
 978             nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
 979     }
 980
 981     /*
 982      * Re-sort once the language issues have been settled
 983      */
 984     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 985            FcSortCompare);
 986
 987     ret = FcFontSetCreate ();
 988     if (!ret)
 989         goto bail1;
 990
 991     cs = 0;
 992
 993     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
 994         goto bail2;
 995
 996     if (csp)
 997         *csp = cs;
 998     else
 999     {
1000         if (cs)
1001             FcCharSetDestroy (cs);
1002     }
1003
1004     free (nodes);
1005
1006     return ret;
1007
1008 bail2:
1009     if (cs)
1010         FcCharSetDestroy (cs);
1011     FcFontSetDestroy (ret);
1012 bail1:
1013     free (nodes);
1014 bail0:
1015     return 0;
1016 }
1017
1018 FcFontSet *
1019 FcFontSort (FcConfig    *config,
1020             FcPattern   *p,
1021             FcBool      trim,
1022             FcCharSet   **csp,
1023             FcResult    *result)
1024 {
1025     FcFontSet   *sets[2];
1026     int         nsets;
1027
1028     if (!config)
1029     {
1030         config = FcConfigGetCurrent ();
1031         if (!config)
1032             return 0;
1033     }
1034     nsets = 0;
1035     if (config->fonts[FcSetSystem])
1036         sets[nsets++] = config->fonts[FcSetSystem];
1037     if (config->fonts[FcSetApplication])
1038         sets[nsets++] = config->fonts[FcSetApplication];
1039     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1040 }