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