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             FcPatternObjectAdd (new, fe->object, v, FcFalse);
 556         }
 557         else
 558         {
 559             if (fel)
 560                 goto copy_lang;
 561             FcPatternObjectListAdd (new, fe->object,
 562                                     FcValueListDuplicate (FcPatternEltValues (fe)),
 563                                     FcTrue);
 564         }
 565     }
 566     for (i = 0; i < pat->num; i++)
 567     {
 568         pe = &FcPatternElts(pat)[i];
 569         fe = FcPatternObjectFindElt (font, pe->object);
 570         if (!fe &&
 571             pe->object != FC_FAMILYLANG_OBJECT &&
 572             pe->object != FC_STYLELANG_OBJECT &&
 573             pe->object != FC_FULLNAMELANG_OBJECT)
 574         {
 575             FcPatternObjectListAdd (new, pe->object,
 576                                     FcValueListDuplicate (FcPatternEltValues(pe)),
 577                                     FcFalse);
 578         }
 579     }
 580
 581     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 582     return new;
 583 }
 584
 585 static FcPattern *
 586 FcFontSetMatchInternal (FcFontSet   **sets,
 587                         int         nsets,
 588                         FcPattern   *p,
 589                         FcResult    *result)
 590 {
 591     double          score[PRI_END], bestscore[PRI_END];
 592     int             f;
 593     FcFontSet       *s;
 594     FcPattern       *best;
 595     int             i;
 596     int             set;
 597
 598     for (i = 0; i < PRI_END; i++)
 599         bestscore[i] = 0;
 600     best = 0;
 601     if (FcDebug () & FC_DBG_MATCH)
 602     {
 603         printf ("Match ");
 604         FcPatternPrint (p);
 605     }
 606     for (set = 0; set < nsets; set++)
 607     {
 608         s = sets[set];
 609         if (!s)
 610             continue;
 611         for (f = 0; f < s->nfont; f++)
 612         {
 613             if (FcDebug () & FC_DBG_MATCHV)
 614             {
 615                 printf ("Font %d ", f);
 616                 FcPatternPrint (s->fonts[f]);
 617             }
 618             if (!FcCompare (p, s->fonts[f], score, result))
 619                 return 0;
 620             if (FcDebug () & FC_DBG_MATCHV)
 621             {
 622                 printf ("Score");
 623                 for (i = 0; i < PRI_END; i++)
 624                 {
 625                     printf (" %g", score[i]);
 626                 }
 627                 printf ("\n");
 628             }
 629             for (i = 0; i < PRI_END; i++)
 630             {
 631                 if (best && bestscore[i] < score[i])
 632                     break;
 633                 if (!best || score[i] < bestscore[i])
 634                 {
 635                     for (i = 0; i < PRI_END; i++)
 636                         bestscore[i] = score[i];
 637                     best = s->fonts[f];
 638                     break;
 639                 }
 640             }
 641         }
 642     }
 643     if (FcDebug () & FC_DBG_MATCH)
 644     {
 645         printf ("Best score");
 646         for (i = 0; i < PRI_END; i++)
 647             printf (" %g", bestscore[i]);
 648         printf ("\n");
 649         FcPatternPrint (best);
 650     }
 651     /* assuming that 'result' is initialized with FcResultNoMatch
 652      * outside this function */
 653     if (best)
 654         *result = FcResultMatch;
 655
 656     return best;
 657 }
 658
 659 FcPattern *
 660 FcFontSetMatch (FcConfig    *config,
 661                 FcFontSet   **sets,
 662                 int         nsets,
 663                 FcPattern   *p,
 664                 FcResult    *result)
 665 {
 666     FcPattern       *best;
 667
 668     assert (sets != NULL);
 669     assert (p != NULL);
 670     assert (result != NULL);
 671
 672     *result = FcResultNoMatch;
 673
 674     if (!config)
 675     {
 676         config = FcConfigGetCurrent ();
 677         if (!config)
 678             return 0;
 679     }
 680     best = FcFontSetMatchInternal (sets, nsets, p, result);
 681     if (best)
 682         return FcFontRenderPrepare (config, p, best);
 683     else
 684         return NULL;
 685 }
 686
 687 FcPattern *
 688 FcFontMatch (FcConfig   *config,
 689              FcPattern  *p,
 690              FcResult   *result)
 691 {
 692     FcFontSet   *sets[2];
 693     int         nsets;
 694     FcPattern   *best;
 695
 696     assert (p != NULL);
 697     assert (result != NULL);
 698
 699     *result = FcResultNoMatch;
 700
 701     if (!config)
 702     {
 703         config = FcConfigGetCurrent ();
 704         if (!config)
 705             return 0;
 706     }
 707     nsets = 0;
 708     if (config->fonts[FcSetSystem])
 709         sets[nsets++] = config->fonts[FcSetSystem];
 710     if (config->fonts[FcSetApplication])
 711         sets[nsets++] = config->fonts[FcSetApplication];
 712
 713     best = FcFontSetMatchInternal (sets, nsets, p, result);
 714     if (best)
 715         return FcFontRenderPrepare (config, p, best);
 716     else
 717         return NULL;
 718 }
 719
 720 typedef struct _FcSortNode {
 721     FcPattern   *pattern;
 722     double      score[PRI_END];
 723 } FcSortNode;
 724
 725 static int
 726 FcSortCompare (const void *aa, const void *ab)
 727 {
 728     FcSortNode  *a = *(FcSortNode **) aa;
 729     FcSortNode  *b = *(FcSortNode **) ab;
 730     double      *as = &a->score[0];
 731     double      *bs = &b->score[0];
 732     double      ad = 0, bd = 0;
 733     int         i;
 734
 735     i = PRI_END;
 736     while (i-- && (ad = *as++) == (bd = *bs++))
 737         ;
 738     return ad < bd ? -1 : ad > bd ? 1 : 0;
 739 }
 740
 741 static FcBool
 742 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
 743 {
 744     FcBool ret = FcFalse;
 745     FcCharSet *cs;
 746
 747     cs = 0;
 748     if (trim || csp)
 749     {
 750         cs = FcCharSetCreate ();
 751         if (cs == NULL)
 752             goto bail;
 753     }
 754
 755     while (nnode--)
 756     {
 757         FcSortNode      *node = *n++;
 758         FcBool          adds_chars = FcFalse;
 759
 760         /*
 761          * Only fetch node charset if we'd need it
 762          */
 763         if (cs)
 764         {
 765             FcCharSet   *ncs;
 766
 767             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
 768                 FcResultMatch)
 769                 continue;
 770
 771             if (!FcCharSetMerge (cs, ncs, &adds_chars))
 772                 goto bail;
 773         }
 774
 775         /*
 776          * If this font isn't a subset of the previous fonts,
 777          * add it to the list
 778          */
 779         if (!trim || adds_chars)
 780         {
 781             FcPatternReference (node->pattern);
 782             if (FcDebug () & FC_DBG_MATCHV)
 783             {
 784                 printf ("Add ");
 785                 FcPatternPrint (node->pattern);
 786             }
 787             if (!FcFontSetAdd (fs, node->pattern))
 788             {
 789                 FcPatternDestroy (node->pattern);
 790                 goto bail;
 791             }
 792         }
 793     }
 794     if (csp)
 795     {
 796         *csp = cs;
 797         cs = 0;
 798     }
 799
 800     ret = FcTrue;
 801
 802 bail:
 803     if (cs)
 804         FcCharSetDestroy (cs);
 805
 806     return ret;
 807 }
 808
 809 void
 810 FcFontSetSortDestroy (FcFontSet *fs)
 811 {
 812     FcFontSetDestroy (fs);
 813 }
 814
 815 FcFontSet *
 816 FcFontSetSort (FcConfig     *config FC_UNUSED,
 817                FcFontSet    **sets,
 818                int          nsets,
 819                FcPattern    *p,
 820                FcBool       trim,
 821                FcCharSet    **csp,
 822                FcResult     *result)
 823 {
 824     FcFontSet       *ret;
 825     FcFontSet       *s;
 826     FcSortNode      *nodes;
 827     FcSortNode      **nodeps, **nodep;
 828     int             nnodes;
 829     FcSortNode      *new;
 830     int             set;
 831     int             f;
 832     int             i;
 833     int             nPatternLang;
 834     FcBool          *patternLangSat;
 835     FcValue         patternLang;
 836
 837     assert (sets != NULL);
 838     assert (p != NULL);
 839     assert (result != NULL);
 840
 841     /* There are some implementation that relying on the result of
 842      * "result" to check if the return value of FcFontSetSort
 843      * is valid or not.
 844      * So we should initialize it to the conservative way since
 845      * this function doesn't return NULL anymore.
 846      */
 847     if (result)
 848         *result = FcResultNoMatch;
 849
 850     if (FcDebug () & FC_DBG_MATCH)
 851     {
 852         printf ("Sort ");
 853         FcPatternPrint (p);
 854     }
 855     nnodes = 0;
 856     for (set = 0; set < nsets; set++)
 857     {
 858         s = sets[set];
 859         if (!s)
 860             continue;
 861         nnodes += s->nfont;
 862     }
 863     if (!nnodes)
 864         return FcFontSetCreate ();
 865
 866     for (nPatternLang = 0;
 867          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
 868          nPatternLang++)
 869         ;
 870
 871     /* freed below */
 872     nodes = malloc (nnodes * sizeof (FcSortNode) +
 873                     nnodes * sizeof (FcSortNode *) +
 874                     nPatternLang * sizeof (FcBool));
 875     if (!nodes)
 876         goto bail0;
 877     nodeps = (FcSortNode **) (nodes + nnodes);
 878     patternLangSat = (FcBool *) (nodeps + nnodes);
 879
 880     new = nodes;
 881     nodep = nodeps;
 882     for (set = 0; set < nsets; set++)
 883     {
 884         s = sets[set];
 885         if (!s)
 886             continue;
 887         for (f = 0; f < s->nfont; f++)
 888         {
 889             if (FcDebug () & FC_DBG_MATCHV)
 890             {
 891                 printf ("Font %d ", f);
 892                 FcPatternPrint (s->fonts[f]);
 893             }
 894             new->pattern = s->fonts[f];
 895             if (!FcCompare (p, new->pattern, new->score, result))
 896                 goto bail1;
 897             if (FcDebug () & FC_DBG_MATCHV)
 898             {
 899                 printf ("Score");
 900                 for (i = 0; i < PRI_END; i++)
 901                 {
 902                     printf (" %g", new->score[i]);
 903                 }
 904                 printf ("\n");
 905             }
 906             *nodep = new;
 907             new++;
 908             nodep++;
 909         }
 910     }
 911
 912     nnodes = new - nodes;
 913
 914     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 915            FcSortCompare);
 916
 917     for (i = 0; i < nPatternLang; i++)
 918         patternLangSat[i] = FcFalse;
 919
 920     for (f = 0; f < nnodes; f++)
 921     {
 922         FcBool  satisfies = FcFalse;
 923         /*
 924          * If this node matches any language, go check
 925          * which ones and satisfy those entries
 926          */
 927         if (nodeps[f]->score[PRI_LANG] < 2000)
 928         {
 929             for (i = 0; i < nPatternLang; i++)
 930             {
 931                 FcValue     nodeLang;
 932
 933                 if (!patternLangSat[i] &&
 934                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
 935                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
 936                 {
 937                     double  compare = FcCompareLang (&patternLang, &nodeLang);
 938                     if (compare >= 0 && compare < 2)
 939                     {
 940                         if (FcDebug () & FC_DBG_MATCHV)
 941                         {
 942                             FcChar8 *family;
 943                             FcChar8 *style;
 944
 945                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
 946                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
 947                                 printf ("Font %s:%s matches language %d\n", family, style, i);
 948                         }
 949                         patternLangSat[i] = FcTrue;
 950                         satisfies = FcTrue;
 951                         break;
 952                     }
 953                 }
 954             }
 955         }
 956         if (!satisfies)
 957         {
 958             nodeps[f]->score[PRI_LANG] = 10000.0;
 959         }
 960     }
 961
 962     /*
 963      * Re-sort once the language issues have been settled
 964      */
 965     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 966            FcSortCompare);
 967
 968     ret = FcFontSetCreate ();
 969     if (!ret)
 970         goto bail1;
 971
 972     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
 973         goto bail2;
 974
 975     free (nodes);
 976
 977     if (FcDebug() & FC_DBG_MATCH)
 978     {
 979         printf ("First font ");
 980         FcPatternPrint (ret->fonts[0]);
 981     }
 982     if (ret->nfont > 0)
 983         *result = FcResultMatch;
 984
 985     return ret;
 986
 987 bail2:
 988     FcFontSetDestroy (ret);
 989 bail1:
 990     free (nodes);
 991 bail0:
 992     return 0;
 993 }
 994
 995 FcFontSet *
 996 FcFontSort (FcConfig    *config,
 997             FcPattern   *p,
 998             FcBool      trim,
 999             FcCharSet   **csp,
1000             FcResult    *result)
1001 {
1002     FcFontSet   *sets[2];
1003     int         nsets;
1004
1005     assert (p != NULL);
1006     assert (result != NULL);
1007
1008     *result = FcResultNoMatch;
1009
1010     if (!config)
1011     {
1012         config = FcConfigGetCurrent ();
1013         if (!config)
1014             return 0;
1015     }
1016     nsets = 0;
1017     if (config->fonts[FcSetSystem])
1018         sets[nsets++] = config->fonts[FcSetSystem];
1019     if (config->fonts[FcSetApplication])
1020         sets[nsets++] = config->fonts[FcSetApplication];
1021     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1022 }
1023 #define __fcmatch__
1024 #include "fcaliastail.h"
1025 #undef __fcmatch__