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
  27 static double
  28 FcCompareNumber (const FcValue *value1, const FcValue *value2, FcValue *bestValue)
  29 {
  30     double  v1, v2, v;
  31
  32     switch ((int) value1->type) {
  33     case FcTypeInteger:
  34         v1 = (double) value1->u.i;
  35         break;
  36     case FcTypeDouble:
  37         v1 = value1->u.d;
  38         break;
  39     default:
  40         return -1.0;
  41     }
  42     switch ((int) value2->type) {
  43     case FcTypeInteger:
  44         v2 = (double) value2->u.i;
  45         break;
  46     case FcTypeDouble:
  47         v2 = value2->u.d;
  48         break;
  49     default:
  50         return -1.0;
  51     }
  52     v = v2 - v1;
  53     if (v < 0)
  54         v = -v;
  55     *bestValue = FcValueCanonicalize (value2);
  56     return v;
  57 }
  58
  59 static double
  60 FcCompareString (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
  61 {
  62     *bestValue = FcValueCanonicalize (v2);
  63     return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
  64 }
  65
  66 static double
  67 FcCompareFamily (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
  68 {
  69     /* rely on the guarantee in FcPatternObjectAddWithBinding that
  70      * families are always FcTypeString. */
  71     const FcChar8* v1_string = FcValueString(v1);
  72     const FcChar8* v2_string = FcValueString(v2);
  73
  74     *bestValue = FcValueCanonicalize (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 FcComparePostScript (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
  85 {
  86     const FcChar8 *v1_string = FcValueString (v1);
  87     const FcChar8 *v2_string = FcValueString (v2);
  88     int n;
  89     size_t len1, len2, mlen;
  90
  91     *bestValue = FcValueCanonicalize (v2);
  92
  93     if (FcToLower (*v1_string) != FcToLower (*v2_string) &&
  94         *v1_string != ' ' && *v2_string != ' ')
  95         return 1.0;
  96
  97     n = FcStrMatchIgnoreCaseAndDelims (v1_string, v2_string, (const FcChar8 *)" -");
  98     len1 = strlen ((const char *)v1_string);
  99     len2 = strlen ((const char *)v2_string);
 100     mlen = FC_MAX (len1, len2);
 101
 102     return (double)(mlen - n) / (double)mlen;
 103 }
 104
 105 static double
 106 FcCompareLang (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 107 {
 108     FcLangResult    result;
 109
 110     switch ((int) v1->type) {
 111     case FcTypeLangSet:
 112         switch ((int) v2->type) {
 113         case FcTypeLangSet:
 114             result = FcLangSetCompare (FcValueLangSet (v1), FcValueLangSet (v2));
 115             break;
 116         case FcTypeString:
 117             result = FcLangSetHasLang (FcValueLangSet (v1), FcValueString (v2));
 118             break;
 119         default:
 120             return -1.0;
 121         }
 122         break;
 123     case FcTypeString:
 124         switch ((int) v2->type) {
 125         case FcTypeLangSet:
 126             result = FcLangSetHasLang (FcValueLangSet (v2), FcValueString (v1));
 127             break;
 128         case FcTypeString:
 129             result = FcLangCompare (FcValueString (v1), FcValueString (v2));
 130             break;
 131         default:
 132             return -1.0;
 133         }
 134         break;
 135     default:
 136         return -1.0;
 137     }
 138     *bestValue = FcValueCanonicalize (v2);
 139     switch (result) {
 140     case FcLangEqual:
 141         return 0;
 142     case FcLangDifferentCountry:
 143         return 1;
 144     case FcLangDifferentLang:
 145     default:
 146         return 2;
 147     }
 148 }
 149
 150 static double
 151 FcCompareBool (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 152 {
 153     if (v2->type != FcTypeBool || v1->type != FcTypeBool)
 154         return -1.0;
 155
 156     bestValue->type = FcTypeBool;
 157     if (v2->u.b != FcDontCare)
 158         bestValue->u.b = v2->u.b;
 159     else
 160         bestValue->u.b = v1->u.b;
 161
 162     return (double) ((v2->u.b ^ v1->u.b) == 1);
 163 }
 164
 165 static double
 166 FcCompareCharSet (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 167 {
 168     *bestValue = FcValueCanonicalize (v2); /* TODO Improve. */
 169     return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
 170 }
 171
 172 static double
 173 FcCompareRange (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 174 {
 175     FcValue value1 = FcValueCanonicalize (v1);
 176     FcValue value2 = FcValueCanonicalize (v2);
 177     double b1, e1, b2, e2, d;
 178
 179     switch ((int) value1.type) {
 180     case FcTypeInteger:
 181         b1 = e1 = value1.u.i;
 182         break;
 183     case FcTypeDouble:
 184         b1 = e1 = value1.u.d;
 185         break;
 186     case FcTypeRange:
 187         b1 = value1.u.r->begin;
 188         e1 = value1.u.r->end;
 189         break;
 190     default:
 191         return -1;
 192     }
 193     switch ((int) value2.type) {
 194     case FcTypeInteger:
 195         b2 = e2 = value2.u.i;
 196         break;
 197     case FcTypeDouble:
 198         b2 = e2 = value2.u.d;
 199         break;
 200     case FcTypeRange:
 201         b2 = value2.u.r->begin;
 202         e2 = value2.u.r->end;
 203         break;
 204     default:
 205         return -1;
 206     }
 207
 208     if (e1 < b2)
 209       d = b2;
 210     else if (e2 < b1)
 211       d = e2;
 212     else
 213       d = (FC_MAX (b1, b2) + FC_MIN (e1, e2)) * .5;
 214
 215     bestValue->type = FcTypeDouble;
 216     bestValue->u.d = d;
 217
 218     /* If the ranges overlap, it's a match, otherwise return closest distance. */
 219     if (e1 < b2 || e2 < b1)
 220         return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
 221     else
 222         return 0.0;
 223 }
 224
 225 static double
 226 FcCompareSize (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 227 {
 228     FcValue value1 = FcValueCanonicalize (v1);
 229     FcValue value2 = FcValueCanonicalize (v2);
 230     double b1, e1, b2, e2;
 231
 232     switch ((int) value1.type) {
 233     case FcTypeInteger:
 234         b1 = e1 = value1.u.i;
 235         break;
 236     case FcTypeDouble:
 237         b1 = e1 = value1.u.d;
 238         break;
 239     case FcTypeRange:
 240         b1 = value1.u.r->begin;
 241         e1 = value1.u.r->end;
 242         break;
 243     default:
 244         return -1;
 245     }
 246     switch ((int) value2.type) {
 247     case FcTypeInteger:
 248         b2 = e2 = value2.u.i;
 249         break;
 250     case FcTypeDouble:
 251         b2 = e2 = value2.u.d;
 252         break;
 253     case FcTypeRange:
 254         b2 = value2.u.r->begin;
 255         e2 = value2.u.r->end;
 256         break;
 257     default:
 258         return -1;
 259     }
 260
 261     bestValue->type = FcTypeDouble;
 262     bestValue->u.d = (b1 + e1) * .5;
 263
 264     /* If the ranges overlap, it's a match, otherwise return closest distance. */
 265     if (e1 < b2 || e2 < b1)
 266         return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
 267     if (b2 != e2 && b1 == e2) /* Semi-closed interval. */
 268         return 1e-15;
 269     else
 270         return 0.0;
 271 }
 272
 273 static double
 274 FcCompareFilename (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 275 {
 276     const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
 277     *bestValue = FcValueCanonicalize (v2);
 278     if (FcStrCmp (s1, s2) == 0)
 279         return 0.0;
 280     else if (FcStrCmpIgnoreCase (s1, s2) == 0)
 281         return 1.0;
 282     else if (FcStrGlobMatch (s1, s2))
 283         return 2.0;
 284     else
 285         return 3.0;
 286 }
 287
 288
 289 /* Define priorities to -1 for objects that don't have a compare function. */
 290
 291 #define PRI_NULL(n)                             \
 292     PRI_ ## n ## _STRONG = -1,                  \
 293     PRI_ ## n ## _WEAK = -1,
 294 #define PRI1(n)
 295 #define PRI_FcCompareFamily(n)          PRI1(n)
 296 #define PRI_FcCompareString(n)          PRI1(n)
 297 #define PRI_FcCompareNumber(n)          PRI1(n)
 298 #define PRI_FcCompareBool(n)            PRI1(n)
 299 #define PRI_FcCompareFilename(n)        PRI1(n)
 300 #define PRI_FcCompareCharSet(n)         PRI1(n)
 301 #define PRI_FcCompareLang(n)            PRI1(n)
 302 #define PRI_FcComparePostScript(n)      PRI1(n)
 303 #define PRI_FcCompareRange(n)           PRI1(n)
 304 #define PRI_FcCompareSize(n)            PRI1(n)
 305
 306 #define FC_OBJECT(NAME, Type, Cmp)      PRI_##Cmp(NAME)
 307
 308 typedef enum _FcMatcherPriorityDummy {
 309 #include "fcobjs.h"
 310 } FcMatcherPriorityDummy;
 311
 312 #undef FC_OBJECT
 313
 314
 315 /* Canonical match priority order. */
 316
 317 #undef PRI1
 318 #define PRI1(n)                                 \
 319     PRI_ ## n,                                  \
 320     PRI_ ## n ## _STRONG = PRI_ ## n,           \
 321     PRI_ ## n ## _WEAK = PRI_ ## n
 322
 323 typedef enum _FcMatcherPriority {
 324     PRI1(FILE),
 325     PRI1(FONTFORMAT),
 326     PRI1(VARIABLE),
 327     PRI1(SCALABLE),
 328     PRI1(COLOR),
 329     PRI1(FOUNDRY),
 330     PRI1(CHARSET),
 331     PRI_FAMILY_STRONG,
 332     PRI_POSTSCRIPT_NAME_STRONG,
 333     PRI1(LANG),
 334     PRI_FAMILY_WEAK,
 335     PRI_POSTSCRIPT_NAME_WEAK,
 336     PRI1(SYMBOL),
 337     PRI1(SPACING),
 338     PRI1(SIZE),
 339     PRI1(PIXEL_SIZE),
 340     PRI1(STYLE),
 341     PRI1(SLANT),
 342     PRI1(WEIGHT),
 343     PRI1(WIDTH),
 344     PRI1(FONT_HAS_HINT),
 345     PRI1(DECORATIVE),
 346     PRI1(ANTIALIAS),
 347     PRI1(RASTERIZER),
 348     PRI1(OUTLINE),
 349     PRI1(ORDER),
 350     PRI1(FONTVERSION),
 351     PRI_END
 352 } FcMatcherPriority;
 353
 354 #undef PRI1
 355
 356 typedef struct _FcMatcher {
 357     FcObject object;
 358     double   (*compare) (const FcValue *v1, const FcValue *v2, FcValue *bestValue);
 359     int      strong, weak;
 360 } FcMatcher;
 361
 362 /*
 363  * Order is significant, it defines the precedence of
 364  * each value, earlier values are more significant than
 365  * later values
 366  */
 367 #define FC_OBJECT(NAME, Type, Cmp)      { FC_##NAME##_OBJECT,   Cmp,    PRI_##NAME##_STRONG,    PRI_##NAME##_WEAK },
 368 static const FcMatcher _FcMatchers [] = {
 369     { FC_INVALID_OBJECT, NULL, -1, -1 },
 370 #include "fcobjs.h"
 371 };
 372 #undef FC_OBJECT
 373
 374 static const FcMatcher*
 375 FcObjectToMatcher (FcObject object,
 376                    FcBool   include_lang)
 377 {
 378     if (include_lang)
 379     {
 380         switch (object) {
 381         case FC_FAMILYLANG_OBJECT:
 382         case FC_STYLELANG_OBJECT:
 383         case FC_FULLNAMELANG_OBJECT:
 384             object = FC_LANG_OBJECT;
 385             break;
 386         }
 387     }
 388     if (object > FC_MAX_BASE_OBJECT ||
 389         !_FcMatchers[object].compare ||
 390         _FcMatchers[object].strong == -1 ||
 391         _FcMatchers[object].weak == -1)
 392         return NULL;
 393
 394     return _FcMatchers + object;
 395 }
 396
 397 static FcBool
 398 FcCompareValueList (FcObject         object,
 399                     const FcMatcher *match,
 400                     FcValueListPtr   v1orig,    /* pattern */
 401                     FcValueListPtr   v2orig,    /* target */
 402                     FcValue         *bestValue,
 403                     double          *value,
 404                     int             *n,
 405                     FcResult        *result)
 406 {
 407     FcValueListPtr  v1, v2;
 408     double          v, best, bestStrong, bestWeak;
 409     int             j, k, pos = 0;
 410     int weak, strong;
 411
 412     if (!match)
 413     {
 414         if (bestValue)
 415             *bestValue = FcValueCanonicalize(&v2orig->value);
 416         if (n)
 417             *n = 0;
 418         return FcTrue;
 419     }
 420
 421     weak    = match->weak;
 422     strong  = match->strong;
 423
 424     best = 1e99;
 425     bestStrong = 1e99;
 426     bestWeak = 1e99;
 427     for (v1 = v1orig, j = 0; v1; v1 = FcValueListNext(v1), j++)
 428     {
 429         for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
 430         {
 431             FcValue matchValue;
 432             v = (match->compare) (&v1->value, &v2->value, &matchValue);
 433             if (v < 0)
 434             {
 435                 *result = FcResultTypeMismatch;
 436                 return FcFalse;
 437             }
 438             v = v * 1000 + j * 100 + k * (v2->value.type == FcTypeString ? 1 : 0);
 439             if (v < best)
 440             {
 441                 if (bestValue)
 442                     *bestValue = matchValue;
 443                 best = v;
 444                 pos = k;
 445             }
 446             if (weak == strong)
 447             {
 448                 /* found the best possible match */
 449                 if (best < 1000)
 450                     goto done;
 451             }
 452             else if (v1->binding == FcValueBindingStrong)
 453             {
 454                 if (v < bestStrong)
 455                     bestStrong = v;
 456             }
 457             else
 458             {
 459                 if (v < bestWeak)
 460                     bestWeak = v;
 461             }
 462         }
 463     }
 464 done:
 465     if (FcDebug () & FC_DBG_MATCHV)
 466     {
 467         printf (" %s: %g ", FcObjectName (object), best);
 468         FcValueListPrint (v1orig);
 469         printf (", ");
 470         FcValueListPrint (v2orig);
 471         printf ("\n");
 472     }
 473     if (value)
 474     {
 475         if (weak == strong)
 476             value[strong] += best;
 477         else
 478         {
 479             value[weak] += bestWeak;
 480             value[strong] += bestStrong;
 481         }
 482     }
 483     if (n)
 484         *n = pos;
 485
 486     return FcTrue;
 487 }
 488
 489 /* The bulk of the time in FcFontMatch and FcFontSort goes to
 490  * walking long lists of family names. We speed this up with a
 491  * hash table.
 492  */
 493 typedef struct
 494 {
 495     double strong_value;
 496     double weak_value;
 497 } FamilyEntry;
 498
 499 typedef struct
 500 {
 501     FcHashTable *family_hash;
 502 } FcCompareData;
 503
 504 static void
 505 FcCompareDataClear (FcCompareData *data)
 506 {
 507     FcHashTableDestroy (data->family_hash);
 508 }
 509
 510 static void
 511 FcCompareDataInit (FcPattern     *pat,
 512                    FcCompareData *data)
 513 {
 514     FcHashTable *table;
 515     FcPatternElt *elt;
 516     FcValueListPtr l;
 517     int i;
 518     const void *key;
 519     FamilyEntry *e;
 520
 521     table = FcHashTableCreate ((FcHashFunc)FcStrHashIgnoreBlanksAndCase,
 522                                (FcCompareFunc)FcStrCmpIgnoreBlanksAndCase,
 523                                NULL,
 524                                NULL,
 525                                NULL,
 526                                free);
 527
 528     elt = FcPatternObjectFindElt (pat, FC_FAMILY_OBJECT);
 529     if (elt)
 530     {
 531         for (l = FcPatternEltValues(elt), i = 0; l; l = FcValueListNext(l), i++)
 532         {
 533             key = FcValueString (&l->value);
 534             if (!FcHashTableFind (table, key, (void **)&e))
 535             {
 536                 e = malloc (sizeof (FamilyEntry));
 537                 e->strong_value = 1e99;
 538                 e->weak_value = 1e99;
 539                 FcHashTableAdd (table, (void *)key, e);
 540             }
 541             if (l->binding == FcValueBindingWeak)
 542             {
 543                 if (i < e->weak_value)
 544                     e->weak_value = i;
 545             }
 546             else
 547             {
 548                 if (i < e->strong_value)
 549                     e->strong_value = i;
 550             }
 551         }
 552     }
 553
 554     data->family_hash = table;
 555 }
 556
 557 static FcBool
 558 FcCompareFamilies (FcPattern       *pat,
 559                    FcValueListPtr   v1orig,
 560                    FcPattern       *fnt,
 561                    FcValueListPtr   v2orig,
 562                    double          *value,
 563                    FcResult        *result,
 564                    FcHashTable     *table)
 565 {
 566     FcValueListPtr v2;
 567     double strong_value;
 568     double weak_value;
 569     const void *key;
 570     FamilyEntry *e;
 571
 572     assert (table != NULL);
 573
 574     strong_value = 1e99;
 575     weak_value = 1e99;
 576
 577     for (v2 = v2orig; v2; v2 = FcValueListNext(v2))
 578     {
 579         key = FcValueString (&v2->value);
 580         if (FcHashTableFind (table, key, (void **)&e))
 581         {
 582             if (e->strong_value < strong_value)
 583                 strong_value = e->strong_value;
 584             if (e->weak_value < weak_value)
 585                 weak_value = e->weak_value;
 586         }
 587     }
 588     if (FcDebug () & FC_DBG_MATCHV)
 589     {
 590         printf ("%s: %g ", FcObjectName (FC_FAMILY_OBJECT), strong_value);
 591         FcValueListPrint (v1orig);
 592         printf (", ");
 593         FcValueListPrint (v2orig);
 594         printf ("\n");
 595     }
 596
 597     value[PRI_FAMILY_STRONG] = strong_value;
 598     value[PRI_FAMILY_WEAK] = weak_value;
 599
 600     return FcTrue;
 601 }
 602
 603 /*
 604  * Return a value indicating the distance between the two lists of
 605  * values
 606  */
 607
 608 static FcBool
 609 FcCompare (FcPattern    *pat,
 610            FcPattern    *fnt,
 611            double       *value,
 612            FcResult     *result,
 613            FcCompareData *data)
 614 {
 615     int             i, i1, i2;
 616
 617     for (i = 0; i < PRI_END; i++)
 618         value[i] = 0.0;
 619
 620     i1 = 0;
 621     i2 = 0;
 622     while (i1 < pat->num && i2 < fnt->num)
 623     {
 624         FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
 625         FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
 626
 627         i = FcObjectCompare(elt_i1->object, elt_i2->object);
 628         if (i > 0)
 629             i2++;
 630         else if (i < 0)
 631             i1++;
 632         else if (elt_i1->object == FC_FAMILY_OBJECT && data->family_hash)
 633         {
 634             if (!FcCompareFamilies (pat, FcPatternEltValues(elt_i1),
 635                                     fnt, FcPatternEltValues(elt_i2),
 636                                     value, result,
 637                                     data->family_hash))
 638                 return FcFalse;
 639             i1++;
 640             i2++;
 641         }
 642         else
 643         {
 644             const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
 645             if (!FcCompareValueList (elt_i1->object, match,
 646                                      FcPatternEltValues(elt_i1),
 647                                      FcPatternEltValues(elt_i2),
 648                                      NULL, value, NULL, result))
 649                 return FcFalse;
 650             i1++;
 651             i2++;
 652         }
 653     }
 654     return FcTrue;
 655 }
 656
 657 FcPattern *
 658 FcFontRenderPrepare (FcConfig       *config,
 659                      FcPattern      *pat,
 660                      FcPattern      *font)
 661 {
 662     FcPattern       *new;
 663     int             i;
 664     FcPatternElt    *fe, *pe;
 665     FcValue         v;
 666     FcResult        result;
 667     FcBool          variable = FcFalse;
 668     FcStrBuf        variations;
 669
 670     assert (pat != NULL);
 671     assert (font != NULL);
 672
 673     FcPatternObjectGetBool (font, FC_VARIABLE_OBJECT, 0, &variable);
 674     assert (variable != FcDontCare);
 675     if (variable)
 676         FcStrBufInit (&variations, NULL, 0);
 677
 678     new = FcPatternCreate ();
 679     if (!new)
 680         return NULL;
 681     for (i = 0; i < font->num; i++)
 682     {
 683         fe = &FcPatternElts(font)[i];
 684         if (fe->object == FC_FAMILYLANG_OBJECT ||
 685             fe->object == FC_STYLELANG_OBJECT ||
 686             fe->object == FC_FULLNAMELANG_OBJECT)
 687         {
 688             /* ignore those objects. we need to deal with them
 689              * another way */
 690             continue;
 691         }
 692         if (fe->object == FC_FAMILY_OBJECT ||
 693             fe->object == FC_STYLE_OBJECT ||
 694             fe->object == FC_FULLNAME_OBJECT)
 695         {
 696             FcPatternElt    *fel, *pel;
 697
 698             FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
 699             FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
 700             FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
 701
 702             fel = FcPatternObjectFindElt (font, fe->object + 1);
 703             pel = FcPatternObjectFindElt (pat, fe->object + 1);
 704
 705             if (fel && pel)
 706             {
 707                 /* The font has name languages, and pattern asks for specific language(s).
 708                  * Match on language and and prefer that result.
 709                  * Note:  Currently the code only give priority to first matching language.
 710                  */
 711                 int n = 1, j;
 712                 FcValueListPtr l1, l2, ln = NULL, ll = NULL;
 713                 const FcMatcher *match = FcObjectToMatcher (pel->object, FcTrue);
 714
 715                 if (!FcCompareValueList (pel->object, match,
 716                                          FcPatternEltValues (pel),
 717                                          FcPatternEltValues (fel), NULL, NULL, &n, &result))
 718                 {
 719                     FcPatternDestroy (new);
 720                     return NULL;
 721                 }
 722
 723                 for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
 724                      l1 != NULL || l2 != NULL;
 725                      j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
 726                 {
 727                     FcValueListPtr (* func) (FcValueListPtr, FcValue, FcValueBinding);
 728                     FcValueBinding binding = FcValueBindingEnd;
 729
 730                     if (j == n)
 731                     {
 732                         binding = FcValueBindingStrong;
 733                         func = FcValueListPrepend;
 734                     }
 735                     else
 736                         func = FcValueListAppend;
 737                     if (l1)
 738                     {
 739                         ln = func (ln,
 740                                    FcValueCanonicalize (&l1->value),
 741                                    l1->binding);
 742                     }
 743                     if (l2)
 744                     {
 745                         if (binding == FcValueBindingEnd)
 746                             binding = l2->binding;
 747                         ll = func (ll,
 748                                    FcValueCanonicalize (&l2->value),
 749                                    binding);
 750                     }
 751                 }
 752                 FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
 753                 FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
 754
 755                 continue;
 756             }
 757             else if (fel)
 758             {
 759                 /* Pattern doesn't ask for specific language.  Copy all for name and
 760                  * lang. */
 761                 FcValueListPtr l1, l2;
 762
 763                 l1 = FcValueListDuplicate (FcPatternEltValues (fe));
 764                 l2 = FcValueListDuplicate (FcPatternEltValues (fel));
 765                 FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
 766                 FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
 767
 768                 continue;
 769             }
 770         }
 771
 772         pe = FcPatternObjectFindElt (pat, fe->object);
 773         if (pe)
 774         {
 775             const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
 776             if (!FcCompareValueList (pe->object, match,
 777                                      FcPatternEltValues(pe),
 778                                      FcPatternEltValues(fe), &v, NULL, NULL, &result))
 779             {
 780                 FcPatternDestroy (new);
 781                 return NULL;
 782             }
 783             FcPatternObjectAdd (new, fe->object, v, FcFalse);
 784
 785             /* Set font-variations settings for standard axes in variable fonts. */
 786             if (variable &&
 787                 FcPatternEltValues(fe)->value.type == FcTypeRange &&
 788                 (fe->object == FC_WEIGHT_OBJECT ||
 789                  fe->object == FC_WIDTH_OBJECT ||
 790                  fe->object == FC_SIZE_OBJECT))
 791             {
 792                 double num;
 793                 FcChar8 temp[128];
 794                 const char *tag = "    ";
 795                 assert (v.type == FcTypeDouble);
 796                 num = v.u.d;
 797                 if (variations.len)
 798                     FcStrBufChar (&variations, ',');
 799                 switch (fe->object)
 800                 {
 801                     case FC_WEIGHT_OBJECT:
 802                         tag = "wght";
 803                         num = FcWeightToOpenType (num);
 804                         break;
 805
 806                     case FC_WIDTH_OBJECT:
 807                         tag = "wdth";
 808                         break;
 809
 810                     case FC_SIZE_OBJECT:
 811                         tag = "opsz";
 812                         break;
 813                 }
 814                 sprintf ((char *) temp, "%4s=%g", tag, num);
 815                 FcStrBufString (&variations, temp);
 816             }
 817         }
 818         else
 819         {
 820             FcPatternObjectListAdd (new, fe->object,
 821                                     FcValueListDuplicate (FcPatternEltValues (fe)),
 822                                     FcTrue);
 823         }
 824     }
 825     for (i = 0; i < pat->num; i++)
 826     {
 827         pe = &FcPatternElts(pat)[i];
 828         fe = FcPatternObjectFindElt (font, pe->object);
 829         if (!fe &&
 830             pe->object != FC_FAMILYLANG_OBJECT &&
 831             pe->object != FC_STYLELANG_OBJECT &&
 832             pe->object != FC_FULLNAMELANG_OBJECT)
 833         {
 834             FcPatternObjectListAdd (new, pe->object,
 835                                     FcValueListDuplicate (FcPatternEltValues(pe)),
 836                                     FcFalse);
 837         }
 838     }
 839
 840     if (variable && variations.len)
 841     {
 842         FcChar8 *vars = NULL;
 843         if (FcPatternObjectGetString (new, FC_FONT_VARIATIONS_OBJECT, 0, &vars) == FcResultMatch)
 844         {
 845             FcStrBufChar (&variations, ',');
 846             FcStrBufString (&variations, vars);
 847             FcPatternObjectDel (new, FC_FONT_VARIATIONS_OBJECT);
 848         }
 849
 850         FcPatternObjectAddString (new, FC_FONT_VARIATIONS_OBJECT, FcStrBufDoneStatic (&variations));
 851         FcStrBufDestroy (&variations);
 852     }
 853
 854     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 855     return new;
 856 }
 857
 858 static FcPattern *
 859 FcFontSetMatchInternal (FcFontSet   **sets,
 860                         int         nsets,
 861                         FcPattern   *p,
 862                         FcResult    *result)
 863 {
 864     double          score[PRI_END], bestscore[PRI_END];
 865     int             f;
 866     FcFontSet       *s;
 867     FcPattern       *best, *pat = NULL;
 868     int             i;
 869     int             set;
 870     FcCompareData   data;
 871     const FcPatternElt *elt;
 872
 873     for (i = 0; i < PRI_END; i++)
 874         bestscore[i] = 0;
 875     best = 0;
 876     if (FcDebug () & FC_DBG_MATCH)
 877     {
 878         printf ("Match ");
 879         FcPatternPrint (p);
 880     }
 881
 882     FcCompareDataInit (p, &data);
 883
 884     for (set = 0; set < nsets; set++)
 885     {
 886         s = sets[set];
 887         if (!s)
 888             continue;
 889         for (f = 0; f < s->nfont; f++)
 890         {
 891             if (FcDebug () & FC_DBG_MATCHV)
 892             {
 893                 printf ("Font %d ", f);
 894                 FcPatternPrint (s->fonts[f]);
 895             }
 896             if (!FcCompare (p, s->fonts[f], score, result, &data))
 897             {
 898                 FcCompareDataClear (&data);
 899                 return 0;
 900             }
 901             if (FcDebug () & FC_DBG_MATCHV)
 902             {
 903                 printf ("Score");
 904                 for (i = 0; i < PRI_END; i++)
 905                 {
 906                     printf (" %g", score[i]);
 907                 }
 908                 printf ("\n");
 909             }
 910             for (i = 0; i < PRI_END; i++)
 911             {
 912                 if (best && bestscore[i] < score[i])
 913                     break;
 914                 if (!best || score[i] < bestscore[i])
 915                 {
 916                     for (i = 0; i < PRI_END; i++)
 917                         bestscore[i] = score[i];
 918                     best = s->fonts[f];
 919                     break;
 920                 }
 921             }
 922         }
 923     }
 924
 925     FcCompareDataClear (&data);
 926
 927     /* Update the binding according to the score to indicate how exactly values matches on. */
 928     if (best)
 929     {
 930         pat = FcPatternCreate ();
 931         elt = FcPatternElts (best);
 932         for (i = 0; i < FcPatternObjectCount (best); i++)
 933         {
 934             const FcMatcher *match = FcObjectToMatcher (elt[i].object, FcFalse);
 935             FcValueListPtr l = FcPatternEltValues (&elt[i]);
 936
 937             if (!match)
 938                 FcPatternObjectListAdd(pat, elt[i].object,
 939                                        FcValueListDuplicate(l), FcTrue);
 940             else
 941             {
 942                 FcValueBinding binding = FcValueBindingWeak;
 943                 FcValueListPtr new = NULL, ll, t = NULL;
 944                 FcValue v;
 945
 946                 /* If the value was matched exactly, update the binding to Strong. */
 947                 if (bestscore[match->strong] < 1000)
 948                     binding = FcValueBindingStrong;
 949
 950                 for (ll = l; ll != NULL; ll = FcValueListNext (ll))
 951                 {
 952                     if (!new)
 953                     {
 954                         t = new = FcValueListCreate ();
 955                     }
 956                     else
 957                     {
 958                         t->next = FcValueListCreate ();
 959                         t = FcValueListNext (t);
 960                     }
 961                     v = FcValueCanonicalize (&ll->value);
 962                     t->value = FcValueSave (v);
 963                     t->binding = binding;
 964                     t->next = NULL;
 965                 }
 966                 FcPatternObjectListAdd (pat, elt[i].object, new, FcTrue);
 967             }
 968         }
 969     }
 970     if (FcDebug () & FC_DBG_MATCH)
 971     {
 972         printf ("Best score");
 973         for (i = 0; i < PRI_END; i++)
 974             printf (" %g", bestscore[i]);
 975         printf ("\n");
 976         FcPatternPrint (pat);
 977     }
 978     if (FcDebug () & FC_DBG_MATCH2)
 979     {
 980         char *env = getenv ("FC_DBG_MATCH_FILTER");
 981         FcObjectSet *os = NULL;
 982
 983         if (env)
 984         {
 985             char *ss, *s;
 986             char *p;
 987             FcBool f = FcTrue;
 988
 989             ss = s = strdup (env);
 990             os = FcObjectSetCreate ();
 991             while (f)
 992             {
 993                 size_t len;
 994                 char *x;
 995
 996                 if (!(p = strchr (s, ',')))
 997                 {
 998                     f = FcFalse;
 999                     len = strlen (s);
1000                 }
1001                 else
1002                 {
1003                     len = (p - s);
1004                 }
1005                 x = malloc (sizeof (char) * (len + 1));
1006                 if (x)
1007                 {
1008                     strcpy (x, s);
1009                     if (FcObjectFromName (x) > 0)
1010                         FcObjectSetAdd (os, x);
1011                     s = p + 1;
1012                     free (x);
1013                 }
1014             }
1015             free (ss);
1016         }
1017         FcPatternPrint2 (p, pat, os);
1018         if (os)
1019             FcObjectSetDestroy (os);
1020     }
1021     /* assuming that 'result' is initialized with FcResultNoMatch
1022      * outside this function */
1023     if (pat)
1024         *result = FcResultMatch;
1025
1026     return pat;
1027 }
1028
1029 FcPattern *
1030 FcFontSetMatch (FcConfig    *config,
1031                 FcFontSet   **sets,
1032                 int         nsets,
1033                 FcPattern   *p,
1034                 FcResult    *result)
1035 {
1036     FcPattern       *best, *ret = NULL;
1037
1038     assert (sets != NULL);
1039     assert (p != NULL);
1040     assert (result != NULL);
1041
1042     *result = FcResultNoMatch;
1043
1044     config = FcConfigReference (config);
1045     if (!config)
1046             return NULL;
1047     best = FcFontSetMatchInternal (sets, nsets, p, result);
1048     if (best)
1049     {
1050         ret = FcFontRenderPrepare (config, p, best);
1051         FcPatternDestroy (best);
1052     }
1053
1054     FcConfigDestroy (config);
1055
1056     return ret;
1057 }
1058
1059 FcPattern *
1060 FcFontMatch (FcConfig   *config,
1061              FcPattern  *p,
1062              FcResult   *result)
1063 {
1064     FcFontSet   *sets[2];
1065     int         nsets;
1066     FcPattern   *best, *ret = NULL;
1067
1068     assert (p != NULL);
1069     assert (result != NULL);
1070
1071     *result = FcResultNoMatch;
1072
1073     config = FcConfigReference (config);
1074     if (!config)
1075         return NULL;
1076     nsets = 0;
1077     if (config->fonts[FcSetSystem])
1078         sets[nsets++] = config->fonts[FcSetSystem];
1079     if (config->fonts[FcSetApplication])
1080         sets[nsets++] = config->fonts[FcSetApplication];
1081
1082     best = FcFontSetMatchInternal (sets, nsets, p, result);
1083     if (best)
1084     {
1085         ret = FcFontRenderPrepare (config, p, best);
1086         FcPatternDestroy (best);
1087     }
1088
1089     FcConfigDestroy (config);
1090
1091     return ret;
1092 }
1093
1094 typedef struct _FcSortNode {
1095     FcPattern   *pattern;
1096     double      score[PRI_END];
1097 } FcSortNode;
1098
1099 static int
1100 FcSortCompare (const void *aa, const void *ab)
1101 {
1102     FcSortNode  *a = *(FcSortNode **) aa;
1103     FcSortNode  *b = *(FcSortNode **) ab;
1104     double      *as = &a->score[0];
1105     double      *bs = &b->score[0];
1106     double      ad = 0, bd = 0;
1107     int         i;
1108
1109     i = PRI_END;
1110     while (i-- && (ad = *as++) == (bd = *bs++))
1111         ;
1112     return ad < bd ? -1 : ad > bd ? 1 : 0;
1113 }
1114
1115 static FcBool
1116 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
1117 {
1118     FcBool ret = FcFalse;
1119     FcCharSet *cs;
1120     int i;
1121
1122     cs = 0;
1123     if (trim || csp)
1124     {
1125         cs = FcCharSetCreate ();
1126         if (cs == NULL)
1127             goto bail;
1128     }
1129
1130     for (i = 0; i < nnode; i++)
1131     {
1132         FcSortNode      *node = *n++;
1133         FcBool          adds_chars = FcFalse;
1134
1135         /*
1136          * Only fetch node charset if we'd need it
1137          */
1138         if (cs)
1139         {
1140             FcCharSet   *ncs;
1141
1142             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
1143                 FcResultMatch)
1144                 continue;
1145
1146             if (!FcCharSetMerge (cs, ncs, &adds_chars))
1147                 goto bail;
1148         }
1149
1150         /*
1151          * If this font isn't a subset of the previous fonts,
1152          * add it to the list
1153          */
1154         if (!i || !trim || adds_chars)
1155         {
1156             FcPatternReference (node->pattern);
1157             if (FcDebug () & FC_DBG_MATCHV)
1158             {
1159                 printf ("Add ");
1160                 FcPatternPrint (node->pattern);
1161             }
1162             if (!FcFontSetAdd (fs, node->pattern))
1163             {
1164                 FcPatternDestroy (node->pattern);
1165                 goto bail;
1166             }
1167         }
1168     }
1169     if (csp)
1170     {
1171         *csp = cs;
1172         cs = 0;
1173     }
1174
1175     ret = FcTrue;
1176
1177 bail:
1178     if (cs)
1179         FcCharSetDestroy (cs);
1180
1181     return ret;
1182 }
1183
1184 void
1185 FcFontSetSortDestroy (FcFontSet *fs)
1186 {
1187     FcFontSetDestroy (fs);
1188 }
1189
1190 FcFontSet *
1191 FcFontSetSort (FcConfig     *config FC_UNUSED,
1192                FcFontSet    **sets,
1193                int          nsets,
1194                FcPattern    *p,
1195                FcBool       trim,
1196                FcCharSet    **csp,
1197                FcResult     *result)
1198 {
1199     FcFontSet       *ret;
1200     FcFontSet       *s;
1201     FcSortNode      *nodes;
1202     FcSortNode      **nodeps, **nodep;
1203     int             nnodes;
1204     FcSortNode      *new;
1205     int             set;
1206     int             f;
1207     int             i;
1208     int             nPatternLang;
1209     FcBool          *patternLangSat;
1210     FcValue         patternLang;
1211     FcCompareData   data;
1212
1213     assert (sets != NULL);
1214     assert (p != NULL);
1215     assert (result != NULL);
1216
1217     /* There are some implementation that relying on the result of
1218      * "result" to check if the return value of FcFontSetSort
1219      * is valid or not.
1220      * So we should initialize it to the conservative way since
1221      * this function doesn't return NULL anymore.
1222      */
1223     if (result)
1224         *result = FcResultNoMatch;
1225
1226     if (FcDebug () & FC_DBG_MATCH)
1227     {
1228         printf ("Sort ");
1229         FcPatternPrint (p);
1230     }
1231     nnodes = 0;
1232     for (set = 0; set < nsets; set++)
1233     {
1234         s = sets[set];
1235         if (!s)
1236             continue;
1237         nnodes += s->nfont;
1238     }
1239     if (!nnodes)
1240         return FcFontSetCreate ();
1241
1242     for (nPatternLang = 0;
1243          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
1244          nPatternLang++)
1245         ;
1246
1247     /* freed below */
1248     nodes = malloc (nnodes * sizeof (FcSortNode) +
1249                     nnodes * sizeof (FcSortNode *) +
1250                     nPatternLang * sizeof (FcBool));
1251     if (!nodes)
1252         goto bail0;
1253     nodeps = (FcSortNode **) (nodes + nnodes);
1254     patternLangSat = (FcBool *) (nodeps + nnodes);
1255
1256     FcCompareDataInit (p, &data);
1257
1258     new = nodes;
1259     nodep = nodeps;
1260     for (set = 0; set < nsets; set++)
1261     {
1262         s = sets[set];
1263         if (!s)
1264             continue;
1265         for (f = 0; f < s->nfont; f++)
1266         {
1267             if (FcDebug () & FC_DBG_MATCHV)
1268             {
1269                 printf ("Font %d ", f);
1270                 FcPatternPrint (s->fonts[f]);
1271             }
1272             new->pattern = s->fonts[f];
1273             if (!FcCompare (p, new->pattern, new->score, result, &data))
1274                 goto bail1;
1275             if (FcDebug () & FC_DBG_MATCHV)
1276             {
1277                 printf ("Score");
1278                 for (i = 0; i < PRI_END; i++)
1279                 {
1280                     printf (" %g", new->score[i]);
1281                 }
1282                 printf ("\n");
1283             }
1284             *nodep = new;
1285             new++;
1286             nodep++;
1287         }
1288     }
1289
1290     FcCompareDataClear (&data);
1291
1292     nnodes = new - nodes;
1293
1294     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1295            FcSortCompare);
1296
1297     for (i = 0; i < nPatternLang; i++)
1298         patternLangSat[i] = FcFalse;
1299
1300     for (f = 0; f < nnodes; f++)
1301     {
1302         FcBool  satisfies = FcFalse;
1303         /*
1304          * If this node matches any language, go check
1305          * which ones and satisfy those entries
1306          */
1307         if (nodeps[f]->score[PRI_LANG] < 2000)
1308         {
1309             for (i = 0; i < nPatternLang; i++)
1310             {
1311                 FcValue     nodeLang;
1312
1313                 if (!patternLangSat[i] &&
1314                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
1315                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
1316                 {
1317                     FcValue matchValue;
1318                     double  compare = FcCompareLang (&patternLang, &nodeLang, &matchValue);
1319                     if (compare >= 0 && compare < 2)
1320                     {
1321                         if (FcDebug () & FC_DBG_MATCHV)
1322                         {
1323                             FcChar8 *family;
1324                             FcChar8 *style;
1325
1326                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
1327                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
1328                                 printf ("Font %s:%s matches language %d\n", family, style, i);
1329                         }
1330                         patternLangSat[i] = FcTrue;
1331                         satisfies = FcTrue;
1332                         break;
1333                     }
1334                 }
1335             }
1336         }
1337         if (!satisfies)
1338         {
1339             nodeps[f]->score[PRI_LANG] = 10000.0;
1340         }
1341     }
1342
1343     /*
1344      * Re-sort once the language issues have been settled
1345      */
1346     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1347            FcSortCompare);
1348
1349     ret = FcFontSetCreate ();
1350     if (!ret)
1351         goto bail1;
1352
1353     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
1354         goto bail2;
1355
1356     free (nodes);
1357
1358     if (FcDebug() & FC_DBG_MATCH)
1359     {
1360         printf ("First font ");
1361         FcPatternPrint (ret->fonts[0]);
1362     }
1363     if (ret->nfont > 0)
1364         *result = FcResultMatch;
1365
1366     return ret;
1367
1368 bail2:
1369     FcFontSetDestroy (ret);
1370 bail1:
1371     free (nodes);
1372 bail0:
1373     return 0;
1374 }
1375
1376 FcFontSet *
1377 FcFontSort (FcConfig    *config,
1378             FcPattern   *p,
1379             FcBool      trim,
1380             FcCharSet   **csp,
1381             FcResult    *result)
1382 {
1383     FcFontSet   *sets[2], *ret;
1384     int         nsets;
1385
1386     assert (p != NULL);
1387     assert (result != NULL);
1388
1389     *result = FcResultNoMatch;
1390
1391     config = FcConfigReference (config);
1392     if (!config)
1393         return NULL;
1394     nsets = 0;
1395     if (config->fonts[FcSetSystem])
1396         sets[nsets++] = config->fonts[FcSetSystem];
1397     if (config->fonts[FcSetApplication])
1398         sets[nsets++] = config->fonts[FcSetApplication];
1399     ret = FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1400     FcConfigDestroy (config);
1401
1402     return ret;
1403 }
1404 #define __fcmatch__
1405 #include "fcaliastail.h"
1406 #undef __fcmatch__