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