src/fcmatch.c

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