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