src/fcmatch.c

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