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