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