src/fcmatch.c

   1 /*
   2  * fontconfig/src/fcmatch.c
   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 the author(s) not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  The authors make 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  * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL THE AUTHOR(S) 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 "fcint.h"
  26
  27 static double
  28 FcCompareNumber (FcValue *value1, FcValue *value2)
  29 {
  30     double  v1, v2, v;
  31
  32     switch ((int) value1->type) {
  33     case FcTypeInteger:
  34         v1 = (double) value1->u.i;
  35         break;
  36     case FcTypeDouble:
  37         v1 = value1->u.d;
  38         break;
  39     default:
  40         return -1.0;
  41     }
  42     switch ((int) value2->type) {
  43     case FcTypeInteger:
  44         v2 = (double) value2->u.i;
  45         break;
  46     case FcTypeDouble:
  47         v2 = value2->u.d;
  48         break;
  49     default:
  50         return -1.0;
  51     }
  52     v = v2 - v1;
  53     if (v < 0)
  54         v = -v;
  55     return v;
  56 }
  57
  58 static double
  59 FcCompareString (FcValue *v1, FcValue *v2)
  60 {
  61     return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
  62 }
  63
  64 static double
  65 FcCompareFamily (FcValue *v1, FcValue *v2)
  66 {
  67     /* rely on the guarantee in FcPatternObjectAddWithBinding that
  68      * families are always FcTypeString. */
  69     const FcChar8* v1_string = FcValueString(v1);
  70     const FcChar8* v2_string = FcValueString(v2);
  71
  72     if (FcToLower(*v1_string) != FcToLower(*v2_string) &&
  73         *v1_string != ' ' && *v2_string != ' ')
  74        return 1.0;
  75
  76     return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
  77 }
  78
  79 static double
  80 FcCompareLang (FcValue *v1, FcValue *v2)
  81 {
  82     FcLangResult    result;
  83     FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
  84
  85     switch ((int) value1.type) {
  86     case FcTypeLangSet:
  87         switch ((int) value2.type) {
  88         case FcTypeLangSet:
  89             result = FcLangSetCompare (value1.u.l, value2.u.l);
  90             break;
  91         case FcTypeString:
  92             result = FcLangSetHasLang (value1.u.l,
  93                                        value2.u.s);
  94             break;
  95         default:
  96             return -1.0;
  97         }
  98         break;
  99     case FcTypeString:
 100         switch ((int) value2.type) {
 101         case FcTypeLangSet:
 102             result = FcLangSetHasLang (value2.u.l, value1.u.s);
 103             break;
 104         case FcTypeString:
 105             result = FcLangCompare (value1.u.s,
 106                                     value2.u.s);
 107             break;
 108         default:
 109             return -1.0;
 110         }
 111         break;
 112     default:
 113         return -1.0;
 114     }
 115     switch (result) {
 116     case FcLangEqual:
 117         return 0;
 118     case FcLangDifferentCountry:
 119         return 1;
 120     case FcLangDifferentLang:
 121     default:
 122         return 2;
 123     }
 124 }
 125
 126 static double
 127 FcCompareBool (FcValue *v1, FcValue *v2)
 128 {
 129     if (v2->type != FcTypeBool || v1->type != FcTypeBool)
 130         return -1.0;
 131     return (double) v2->u.b != v1->u.b;
 132 }
 133
 134 static double
 135 FcCompareCharSet (FcValue *v1, FcValue *v2)
 136 {
 137     return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
 138 }
 139
 140 static double
 141 FcCompareSize (FcValue *value1, FcValue *value2)
 142 {
 143     double  v1, v2, v;
 144
 145     switch ((int) value1->type) {
 146     case FcTypeInteger:
 147         v1 = value1->u.i;
 148         break;
 149     case FcTypeDouble:
 150         v1 = value1->u.d;
 151         break;
 152     default:
 153         return -1;
 154     }
 155     switch ((int) value2->type) {
 156     case FcTypeInteger:
 157         v2 = value2->u.i;
 158         break;
 159     case FcTypeDouble:
 160         v2 = value2->u.d;
 161         break;
 162     default:
 163         return -1;
 164     }
 165     if (v2 == 0)
 166         return 0;
 167     v = v2 - v1;
 168     if (v < 0)
 169         v = -v;
 170     return v;
 171 }
 172
 173 static double
 174 FcCompareFilename (FcValue *v1, FcValue *v2)
 175 {
 176         const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
 177         if (FcStrCmp (s1, s2) == 0)
 178             return 0.0;
 179         else if (FcStrCmpIgnoreCase (s1, s2) == 0)
 180             return 1.0;
 181         else if (FcStrRegexCmp (s2, s1))
 182             return 2.0;
 183         else if (FcStrRegexCmpIgnoreCase (s2, s1))
 184             return 3.0;
 185         else
 186             return 4.0;
 187 }
 188
 189 #define PRI_NULL(n)                             \
 190     PRI_ ## n ## _STRONG = -1,                  \
 191     PRI_ ## n ## _WEAK = -1,
 192 #define PRI1(n)
 193 #define PRI_FcCompareFamily(n)          PRI1(n)
 194 #define PRI_FcCompareString(n)          PRI1(n)
 195 #define PRI_FcCompareNumber(n)          PRI1(n)
 196 #define PRI_FcCompareSize(n)            PRI1(n)
 197 #define PRI_FcCompareBool(n)            PRI1(n)
 198 #define PRI_FcCompareFilename(n)        PRI1(n)
 199 #define PRI_FcCompareCharSet(n)         PRI1(n)
 200 #define PRI_FcCompareLang(n)            PRI1(n)
 201
 202 #define FC_OBJECT(NAME, Type, Cmp)      PRI_##Cmp(NAME)
 203
 204 typedef enum _FcMatcherPriorityDummy {
 205 #include "fcobjs.h"
 206 } FcMatcherPriorityDummy;
 207
 208 #undef FC_OBJECT
 209
 210 #undef PRI1
 211 #define PRI1(n)                 \
 212     PRI_ ## n ## _STRONG,       \
 213     PRI_ ## n ## _WEAK
 214
 215 typedef enum _FcMatcherPriority {
 216     PRI1(HASH),
 217     PRI1(FILE),
 218     PRI1(FOUNDRY),
 219     PRI1(CHARSET),
 220     PRI_FAMILY_STRONG,
 221     PRI_LANG_STRONG,
 222     PRI_LANG_WEAK,
 223     PRI_FAMILY_WEAK,
 224     PRI1(SPACING),
 225     PRI1(PIXEL_SIZE),
 226     PRI1(STYLE),
 227     PRI1(SLANT),
 228     PRI1(WEIGHT),
 229     PRI1(WIDTH),
 230     PRI1(DECORATIVE),
 231     PRI1(ANTIALIAS),
 232     PRI1(RASTERIZER),
 233     PRI1(OUTLINE),
 234     PRI1(FONTVERSION),
 235     PRI_END
 236 } FcMatcherPriority;
 237
 238 #undef PRI1
 239
 240 typedef struct _FcMatcher {
 241     FcObject object;
 242     double   (*compare) (FcValue *value1, FcValue *value2);
 243     int      strong, weak;
 244 } FcMatcher;
 245
 246 /*
 247  * Order is significant, it defines the precedence of
 248  * each value, earlier values are more significant than
 249  * later values
 250  */
 251 #define FC_OBJECT(NAME, Type, Cmp)      { FC_##NAME##_OBJECT,   Cmp,    PRI_##NAME##_STRONG,    PRI_##NAME##_WEAK },
 252 static const FcMatcher _FcMatchers [] = {
 253     { FC_INVALID_OBJECT, NULL, -1, -1 },
 254 #include "fcobjs.h"
 255 };
 256 #undef FC_OBJECT
 257
 258 static const FcMatcher*
 259 FcObjectToMatcher (FcObject object,
 260                    FcBool   include_lang)
 261 {
 262     if (include_lang)
 263     {
 264         switch (object) {
 265         case FC_FAMILYLANG_OBJECT:
 266         case FC_STYLELANG_OBJECT:
 267         case FC_FULLNAMELANG_OBJECT:
 268             object = FC_LANG_OBJECT;
 269             break;
 270         }
 271     }
 272     if (object > FC_MAX_BASE_OBJECT ||
 273         !_FcMatchers[object].compare ||
 274         _FcMatchers[object].strong == -1 ||
 275         _FcMatchers[object].weak == -1)
 276         return NULL;
 277
 278     return _FcMatchers + object;
 279 }
 280
 281 static FcBool
 282 FcCompareValueList (FcObject         object,
 283                     const FcMatcher *match,
 284                     FcValueListPtr   v1orig,    /* pattern */
 285                     FcValueListPtr   v2orig,    /* target */
 286                     FcValue         *bestValue,
 287                     double          *value,
 288                     int             *n,
 289                     FcResult        *result)
 290 {
 291     FcValueListPtr  v1, v2;
 292     double          v, best, bestStrong, bestWeak;
 293     int             j, k, pos = 0;
 294
 295     if (!match)
 296     {
 297         if (bestValue)
 298             *bestValue = FcValueCanonicalize(&v2orig->value);
 299         if (n)
 300             *n = 0;
 301         return FcTrue;
 302     }
 303
 304     best = 1e99;
 305     bestStrong = 1e99;
 306     bestWeak = 1e99;
 307     j = 1;
 308     for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
 309     {
 310         for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
 311         {
 312             v = (match->compare) (&v1->value, &v2->value);
 313             if (v < 0)
 314             {
 315                 *result = FcResultTypeMismatch;
 316                 return FcFalse;
 317             }
 318             v = v * 1000 + j;
 319             if (v < best)
 320             {
 321                 if (bestValue)
 322                     *bestValue = FcValueCanonicalize(&v2->value);
 323                 best = v;
 324                 pos = k;
 325             }
 326             if (v1->binding == FcValueBindingStrong)
 327             {
 328                 if (v < bestStrong)
 329                     bestStrong = v;
 330             }
 331             else
 332             {
 333                 if (v < bestWeak)
 334                     bestWeak = v;
 335             }
 336         }
 337         j++;
 338     }
 339     if (FcDebug () & FC_DBG_MATCHV)
 340     {
 341         printf (" %s: %g ", FcObjectName (object), best);
 342         FcValueListPrint (v1orig);
 343         printf (", ");
 344         FcValueListPrint (v2orig);
 345         printf ("\n");
 346     }
 347     if (value)
 348     {
 349         int weak    = match->weak;
 350         int strong  = match->strong;
 351         if (weak == strong)
 352             value[strong] += best;
 353         else
 354         {
 355             value[weak] += bestWeak;
 356             value[strong] += bestStrong;
 357         }
 358     }
 359     if (n)
 360         *n = pos;
 361
 362     return FcTrue;
 363 }
 364
 365 /*
 366  * Return a value indicating the distance between the two lists of
 367  * values
 368  */
 369
 370 static FcBool
 371 FcCompare (FcPattern    *pat,
 372            FcPattern    *fnt,
 373            double       *value,
 374            FcResult     *result)
 375 {
 376     int             i, i1, i2;
 377
 378     for (i = 0; i < PRI_END; i++)
 379         value[i] = 0.0;
 380
 381     i1 = 0;
 382     i2 = 0;
 383     while (i1 < pat->num && i2 < fnt->num)
 384     {
 385         FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
 386         FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
 387
 388         i = FcObjectCompare(elt_i1->object, elt_i2->object);
 389         if (i > 0)
 390             i2++;
 391         else if (i < 0)
 392             i1++;
 393         else
 394         {
 395             const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
 396             if (!FcCompareValueList (elt_i1->object, match,
 397                                      FcPatternEltValues(elt_i1),
 398                                      FcPatternEltValues(elt_i2),
 399                                      NULL, value, NULL, result))
 400                 return FcFalse;
 401             i1++;
 402             i2++;
 403         }
 404     }
 405     return FcTrue;
 406 }
 407
 408 FcPattern *
 409 FcFontRenderPrepare (FcConfig       *config,
 410                      FcPattern      *pat,
 411                      FcPattern      *font)
 412 {
 413     FcPattern       *new;
 414     int             i;
 415     FcPatternElt    *fe, *pe, *fel, *pel;
 416     FcValue         v;
 417     FcResult        result;
 418
 419     assert (pat != NULL);
 420     assert (font != NULL);
 421
 422     new = FcPatternCreate ();
 423     if (!new)
 424         return NULL;
 425     for (i = 0; i < font->num; i++)
 426     {
 427         fe = &FcPatternElts(font)[i];
 428         if (fe->object == FC_FAMILYLANG_OBJECT ||
 429             fe->object == FC_STYLELANG_OBJECT ||
 430             fe->object == FC_FULLNAMELANG_OBJECT)
 431         {
 432             /* ignore those objects. we need to deal with them
 433              * another way */
 434             continue;
 435         }
 436         if (fe->object == FC_FAMILY_OBJECT ||
 437             fe->object == FC_STYLE_OBJECT ||
 438             fe->object == FC_FULLNAME_OBJECT)
 439         {
 440             FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
 441             FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
 442             FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
 443
 444             fel = FcPatternObjectFindElt (font, fe->object + 1);
 445             pel = FcPatternObjectFindElt (pat, fe->object + 1);
 446         }
 447         else
 448         {
 449             fel = NULL;
 450             pel = NULL;
 451         }
 452         pe = FcPatternObjectFindElt (pat, fe->object);
 453         if (pe)
 454         {
 455             const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
 456
 457             if (!FcCompareValueList (pe->object, match,
 458                                      FcPatternEltValues(pe),
 459                                      FcPatternEltValues(fe), &v, NULL, NULL, &result))
 460             {
 461                 FcPatternDestroy (new);
 462                 return NULL;
 463             }
 464             if (fel && pel)
 465             {
 466                 int n = 1, j;
 467                 FcValueListPtr l1, l2, ln = NULL, ll = NULL;
 468
 469                 match = FcObjectToMatcher (pel->object, FcTrue);
 470                 if (!FcCompareValueList (pel->object, match,
 471                                          FcPatternEltValues (pel),
 472                                          FcPatternEltValues (fel), NULL, NULL, &n, &result))
 473                 {
 474                     FcPatternDestroy (new);
 475                     return NULL;
 476                 }
 477
 478                 for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
 479                      l1 != NULL || l2 != NULL;
 480                      j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
 481                 {
 482                     if (j == n)
 483                     {
 484                         if (l1)
 485                             ln = FcValueListPrepend (ln,
 486                                                      FcValueCanonicalize (&l1->value),
 487                                                      FcValueBindingStrong);
 488                         if (l2)
 489                             ll = FcValueListPrepend (ll,
 490                                                      FcValueCanonicalize (&l2->value),
 491                                                      FcValueBindingStrong);
 492                     }
 493                     else
 494                     {
 495                         if (l1)
 496                             ln = FcValueListAppend (ln,
 497                                                     FcValueCanonicalize (&l1->value),
 498                                                     FcValueBindingStrong);
 499                         if (l2)
 500                             ll = FcValueListAppend (ll,
 501                                                     FcValueCanonicalize (&l2->value),
 502                                                     FcValueBindingStrong);
 503                     }
 504                 }
 505                 FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
 506                 FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
 507
 508                 continue;
 509             }
 510             else if (fel)
 511             {
 512                 FcValueListPtr l1, l2;
 513
 514             copy_lang:
 515                 l1 = FcValueListDuplicate (FcPatternEltValues (fe));
 516                 l2 = FcValueListDuplicate (FcPatternEltValues (fel));
 517                 FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
 518                 FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
 519
 520                 continue;
 521             }
 522         }
 523         else
 524         {
 525             if (fel)
 526                 goto copy_lang;
 527             v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
 528         }
 529         FcPatternObjectAdd (new, fe->object, v, FcFalse);
 530     }
 531     for (i = 0; i < pat->num; i++)
 532     {
 533         pe = &FcPatternElts(pat)[i];
 534         fe = FcPatternObjectFindElt (font, pe->object);
 535         if (!fe)
 536         {
 537             FcPatternObjectListAdd (new, pe->object,
 538                                     FcValueListDuplicate (FcPatternEltValues(pe)),
 539                                     FcFalse);
 540         }
 541     }
 542
 543     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 544     return new;
 545 }
 546
 547 static FcPattern *
 548 FcFontSetMatchInternal (FcFontSet   **sets,
 549                         int         nsets,
 550                         FcPattern   *p,
 551                         FcResult    *result)
 552 {
 553     double          score[PRI_END], bestscore[PRI_END];
 554     int             f;
 555     FcFontSet       *s;
 556     FcPattern       *best;
 557     int             i;
 558     int             set;
 559
 560     for (i = 0; i < PRI_END; i++)
 561         bestscore[i] = 0;
 562     best = 0;
 563     if (FcDebug () & FC_DBG_MATCH)
 564     {
 565         printf ("Match ");
 566         FcPatternPrint (p);
 567     }
 568     for (set = 0; set < nsets; set++)
 569     {
 570         s = sets[set];
 571         if (!s)
 572             continue;
 573         for (f = 0; f < s->nfont; f++)
 574         {
 575             if (FcDebug () & FC_DBG_MATCHV)
 576             {
 577                 printf ("Font %d ", f);
 578                 FcPatternPrint (s->fonts[f]);
 579             }
 580             if (!FcCompare (p, s->fonts[f], score, result))
 581                 return 0;
 582             if (FcDebug () & FC_DBG_MATCHV)
 583             {
 584                 printf ("Score");
 585                 for (i = 0; i < PRI_END; i++)
 586                 {
 587                     printf (" %g", score[i]);
 588                 }
 589                 printf ("\n");
 590             }
 591             for (i = 0; i < PRI_END; i++)
 592             {
 593                 if (best && bestscore[i] < score[i])
 594                     break;
 595                 if (!best || score[i] < bestscore[i])
 596                 {
 597                     for (i = 0; i < PRI_END; i++)
 598                         bestscore[i] = score[i];
 599                     best = s->fonts[f];
 600                     break;
 601                 }
 602             }
 603         }
 604     }
 605     if (FcDebug () & FC_DBG_MATCH)
 606     {
 607         printf ("Best score");
 608         for (i = 0; i < PRI_END; i++)
 609             printf (" %g", bestscore[i]);
 610         printf ("\n");
 611         FcPatternPrint (best);
 612     }
 613     /* assuming that 'result' is initialized with FcResultNoMatch
 614      * outside this function */
 615     if (best)
 616         *result = FcResultMatch;
 617
 618     return best;
 619 }
 620
 621 FcPattern *
 622 FcFontSetMatch (FcConfig    *config,
 623                 FcFontSet   **sets,
 624                 int         nsets,
 625                 FcPattern   *p,
 626                 FcResult    *result)
 627 {
 628     FcPattern       *best;
 629
 630     assert (sets != NULL);
 631     assert (p != NULL);
 632     assert (result != NULL);
 633
 634     *result = FcResultNoMatch;
 635
 636     if (!config)
 637     {
 638         config = FcConfigGetCurrent ();
 639         if (!config)
 640             return 0;
 641     }
 642     best = FcFontSetMatchInternal (sets, nsets, p, result);
 643     if (best)
 644         return FcFontRenderPrepare (config, p, best);
 645     else
 646         return NULL;
 647 }
 648
 649 FcPattern *
 650 FcFontMatch (FcConfig   *config,
 651              FcPattern  *p,
 652              FcResult   *result)
 653 {
 654     FcFontSet   *sets[2];
 655     int         nsets;
 656     FcPattern   *best;
 657
 658     assert (p != NULL);
 659     assert (result != NULL);
 660
 661     *result = FcResultNoMatch;
 662
 663     if (!config)
 664     {
 665         config = FcConfigGetCurrent ();
 666         if (!config)
 667             return 0;
 668     }
 669     nsets = 0;
 670     if (config->fonts[FcSetSystem])
 671         sets[nsets++] = config->fonts[FcSetSystem];
 672     if (config->fonts[FcSetApplication])
 673         sets[nsets++] = config->fonts[FcSetApplication];
 674
 675     best = FcFontSetMatchInternal (sets, nsets, p, result);
 676     if (best)
 677         return FcFontRenderPrepare (config, p, best);
 678     else
 679         return NULL;
 680 }
 681
 682 typedef struct _FcSortNode {
 683     FcPattern   *pattern;
 684     double      score[PRI_END];
 685 } FcSortNode;
 686
 687 static int
 688 FcSortCompare (const void *aa, const void *ab)
 689 {
 690     FcSortNode  *a = *(FcSortNode **) aa;
 691     FcSortNode  *b = *(FcSortNode **) ab;
 692     double      *as = &a->score[0];
 693     double      *bs = &b->score[0];
 694     double      ad = 0, bd = 0;
 695     int         i;
 696
 697     i = PRI_END;
 698     while (i-- && (ad = *as++) == (bd = *bs++))
 699         ;
 700     return ad < bd ? -1 : ad > bd ? 1 : 0;
 701 }
 702
 703 static FcBool
 704 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
 705 {
 706     FcBool ret = FcFalse;
 707     FcCharSet *cs;
 708
 709     cs = 0;
 710     if (trim || csp)
 711     {
 712         cs = FcCharSetCreate ();
 713         if (cs == NULL)
 714             goto bail;
 715     }
 716
 717     while (nnode--)
 718     {
 719         FcSortNode      *node = *n++;
 720         FcBool          adds_chars = FcFalse;
 721
 722         /*
 723          * Only fetch node charset if we'd need it
 724          */
 725         if (cs)
 726         {
 727             FcCharSet   *ncs;
 728
 729             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
 730                 FcResultMatch)
 731                 continue;
 732
 733             if (!FcCharSetMerge (cs, ncs, &adds_chars))
 734                 goto bail;
 735         }
 736
 737         /*
 738          * If this font isn't a subset of the previous fonts,
 739          * add it to the list
 740          */
 741         if (!trim || adds_chars)
 742         {
 743             FcPatternReference (node->pattern);
 744             if (FcDebug () & FC_DBG_MATCHV)
 745             {
 746                 printf ("Add ");
 747                 FcPatternPrint (node->pattern);
 748             }
 749             if (!FcFontSetAdd (fs, node->pattern))
 750             {
 751                 FcPatternDestroy (node->pattern);
 752                 goto bail;
 753             }
 754         }
 755     }
 756     if (csp)
 757     {
 758         *csp = cs;
 759         cs = 0;
 760     }
 761
 762     ret = FcTrue;
 763
 764 bail:
 765     if (cs)
 766         FcCharSetDestroy (cs);
 767
 768     return ret;
 769 }
 770
 771 void
 772 FcFontSetSortDestroy (FcFontSet *fs)
 773 {
 774     FcFontSetDestroy (fs);
 775 }
 776
 777 FcFontSet *
 778 FcFontSetSort (FcConfig     *config FC_UNUSED,
 779                FcFontSet    **sets,
 780                int          nsets,
 781                FcPattern    *p,
 782                FcBool       trim,
 783                FcCharSet    **csp,
 784                FcResult     *result)
 785 {
 786     FcFontSet       *ret;
 787     FcFontSet       *s;
 788     FcSortNode      *nodes;
 789     FcSortNode      **nodeps, **nodep;
 790     int             nnodes;
 791     FcSortNode      *new;
 792     int             set;
 793     int             f;
 794     int             i;
 795     int             nPatternLang;
 796     FcBool          *patternLangSat;
 797     FcValue         patternLang;
 798
 799     assert (sets != NULL);
 800     assert (p != NULL);
 801     assert (result != NULL);
 802
 803     /* There are some implementation that relying on the result of
 804      * "result" to check if the return value of FcFontSetSort
 805      * is valid or not.
 806      * So we should initialize it to the conservative way since
 807      * this function doesn't return NULL anymore.
 808      */
 809     if (result)
 810         *result = FcResultNoMatch;
 811
 812     if (FcDebug () & FC_DBG_MATCH)
 813     {
 814         printf ("Sort ");
 815         FcPatternPrint (p);
 816     }
 817     nnodes = 0;
 818     for (set = 0; set < nsets; set++)
 819     {
 820         s = sets[set];
 821         if (!s)
 822             continue;
 823         nnodes += s->nfont;
 824     }
 825     if (!nnodes)
 826         return FcFontSetCreate ();
 827
 828     for (nPatternLang = 0;
 829          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
 830          nPatternLang++)
 831         ;
 832
 833     /* freed below */
 834     nodes = malloc (nnodes * sizeof (FcSortNode) +
 835                     nnodes * sizeof (FcSortNode *) +
 836                     nPatternLang * sizeof (FcBool));
 837     if (!nodes)
 838         goto bail0;
 839     nodeps = (FcSortNode **) (nodes + nnodes);
 840     patternLangSat = (FcBool *) (nodeps + nnodes);
 841
 842     new = nodes;
 843     nodep = nodeps;
 844     for (set = 0; set < nsets; set++)
 845     {
 846         s = sets[set];
 847         if (!s)
 848             continue;
 849         for (f = 0; f < s->nfont; f++)
 850         {
 851             if (FcDebug () & FC_DBG_MATCHV)
 852             {
 853                 printf ("Font %d ", f);
 854                 FcPatternPrint (s->fonts[f]);
 855             }
 856             new->pattern = s->fonts[f];
 857             if (!FcCompare (p, new->pattern, new->score, result))
 858                 goto bail1;
 859             if (FcDebug () & FC_DBG_MATCHV)
 860             {
 861                 printf ("Score");
 862                 for (i = 0; i < PRI_END; i++)
 863                 {
 864                     printf (" %g", new->score[i]);
 865                 }
 866                 printf ("\n");
 867             }
 868             *nodep = new;
 869             new++;
 870             nodep++;
 871         }
 872     }
 873
 874     nnodes = new - nodes;
 875
 876     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 877            FcSortCompare);
 878
 879     for (i = 0; i < nPatternLang; i++)
 880         patternLangSat[i] = FcFalse;
 881
 882     for (f = 0; f < nnodes; f++)
 883     {
 884         FcBool  satisfies = FcFalse;
 885         /*
 886          * If this node matches any language, go check
 887          * which ones and satisfy those entries
 888          */
 889         if (nodeps[f]->score[PRI_LANG_STRONG] < 2000 ||
 890             nodeps[f]->score[PRI_LANG_WEAK] < 2000)
 891         {
 892             for (i = 0; i < nPatternLang; i++)
 893             {
 894                 FcValue     nodeLang;
 895
 896                 if (!patternLangSat[i] &&
 897                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
 898                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
 899                 {
 900                     double  compare = FcCompareLang (&patternLang, &nodeLang);
 901                     if (compare >= 0 && compare < 2)
 902                     {
 903                         if (FcDebug () & FC_DBG_MATCHV)
 904                         {
 905                             FcChar8 *family;
 906                             FcChar8 *style;
 907
 908                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
 909                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
 910                                 printf ("Font %s:%s matches language %d\n", family, style, i);
 911                         }
 912                         patternLangSat[i] = FcTrue;
 913                         satisfies = FcTrue;
 914                         break;
 915                     }
 916                 }
 917             }
 918         }
 919         if (!satisfies)
 920         {
 921             nodeps[f]->score[PRI_LANG_STRONG] = 10000.0;
 922             nodeps[f]->score[PRI_LANG_WEAK] = 10000.0;
 923         }
 924     }
 925
 926     /*
 927      * Re-sort once the language issues have been settled
 928      */
 929     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 930            FcSortCompare);
 931
 932     ret = FcFontSetCreate ();
 933     if (!ret)
 934         goto bail1;
 935
 936     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
 937         goto bail2;
 938
 939     free (nodes);
 940
 941     if (FcDebug() & FC_DBG_MATCH)
 942     {
 943         printf ("First font ");
 944         FcPatternPrint (ret->fonts[0]);
 945     }
 946     if (ret->nfont > 0)
 947         *result = FcResultMatch;
 948
 949     return ret;
 950
 951 bail2:
 952     FcFontSetDestroy (ret);
 953 bail1:
 954     free (nodes);
 955 bail0:
 956     return 0;
 957 }
 958
 959 FcFontSet *
 960 FcFontSort (FcConfig    *config,
 961             FcPattern   *p,
 962             FcBool      trim,
 963             FcCharSet   **csp,
 964             FcResult    *result)
 965 {
 966     FcFontSet   *sets[2];
 967     int         nsets;
 968
 969     assert (p != NULL);
 970     assert (result != NULL);
 971
 972     *result = FcResultNoMatch;
 973
 974     if (!config)
 975     {
 976         config = FcConfigGetCurrent ();
 977         if (!config)
 978             return 0;
 979     }
 980     nsets = 0;
 981     if (config->fonts[FcSetSystem])
 982         sets[nsets++] = config->fonts[FcSetSystem];
 983     if (config->fonts[FcSetApplication])
 984         sets[nsets++] = config->fonts[FcSetApplication];
 985     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 986 }
 987 #define __fcmatch__
 988 #include "fcaliastail.h"
 989 #undef __fcmatch__