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 len;
  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     len = strlen ((const char *)v1_string);
  99
 100     return (double)(len - n) / (double)len;
 101 }
 102
 103 static double
 104 FcCompareLang (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 105 {
 106     FcLangResult    result;
 107     FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
 108
 109     switch ((int) value1.type) {
 110     case FcTypeLangSet:
 111         switch ((int) value2.type) {
 112         case FcTypeLangSet:
 113             result = FcLangSetCompare (value1.u.l, value2.u.l);
 114             break;
 115         case FcTypeString:
 116             result = FcLangSetHasLang (value1.u.l,
 117                                        value2.u.s);
 118             break;
 119         default:
 120             return -1.0;
 121         }
 122         break;
 123     case FcTypeString:
 124         switch ((int) value2.type) {
 125         case FcTypeLangSet:
 126             result = FcLangSetHasLang (value2.u.l, value1.u.s);
 127             break;
 128         case FcTypeString:
 129             result = FcLangCompare (value1.u.s,
 130                                     value2.u.s);
 131             break;
 132         default:
 133             return -1.0;
 134         }
 135         break;
 136     default:
 137         return -1.0;
 138     }
 139     *bestValue = FcValueCanonicalize (v2);
 140     switch (result) {
 141     case FcLangEqual:
 142         return 0;
 143     case FcLangDifferentCountry:
 144         return 1;
 145     case FcLangDifferentLang:
 146     default:
 147         return 2;
 148     }
 149 }
 150
 151 static double
 152 FcCompareBool (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 153 {
 154     if (v2->type != FcTypeBool || v1->type != FcTypeBool)
 155         return -1.0;
 156
 157     if (v2->u.b != FcDontCare)
 158         *bestValue = FcValueCanonicalize (v2);
 159     else
 160         *bestValue = FcValueCanonicalize (v1);
 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         abort();
 241         b1 = value1.u.r->begin;
 242         e1 = value1.u.r->end;
 243         break;
 244     default:
 245         return -1;
 246     }
 247     switch ((int) value2.type) {
 248     case FcTypeInteger:
 249         b2 = e2 = value2.u.i;
 250         break;
 251     case FcTypeDouble:
 252         b2 = e2 = value2.u.d;
 253         break;
 254     case FcTypeRange:
 255         b2 = value2.u.r->begin;
 256         e2 = value2.u.r->end;
 257         break;
 258     default:
 259         return -1;
 260     }
 261
 262     bestValue->type = FcTypeDouble;
 263     bestValue->u.d = (b1 + e1) * .5;
 264
 265     /* If the ranges overlap, it's a match, otherwise return closest distance. */
 266     if (e1 < b2 || e2 < b1)
 267         return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
 268     if (b2 != e2 && b1 == e2) /* Semi-closed interval. */
 269         return 1e-15;
 270     else
 271         return 0.0;
 272 }
 273
 274 static double
 275 FcCompareFilename (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
 276 {
 277     const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
 278     *bestValue = FcValueCanonicalize (v2);
 279     if (FcStrCmp (s1, s2) == 0)
 280         return 0.0;
 281     else if (FcStrCmpIgnoreCase (s1, s2) == 0)
 282         return 1.0;
 283     else if (FcStrGlobMatch (s1, s2))
 284         return 2.0;
 285     else
 286         return 3.0;
 287 }
 288
 289
 290 /* Define priorities to -1 for objects that don't have a compare function. */
 291
 292 #define PRI_NULL(n)                             \
 293     PRI_ ## n ## _STRONG = -1,                  \
 294     PRI_ ## n ## _WEAK = -1,
 295 #define PRI1(n)
 296 #define PRI_FcCompareFamily(n)          PRI1(n)
 297 #define PRI_FcCompareString(n)          PRI1(n)
 298 #define PRI_FcCompareNumber(n)          PRI1(n)
 299 #define PRI_FcCompareBool(n)            PRI1(n)
 300 #define PRI_FcCompareFilename(n)        PRI1(n)
 301 #define PRI_FcCompareCharSet(n)         PRI1(n)
 302 #define PRI_FcCompareLang(n)            PRI1(n)
 303 #define PRI_FcComparePostScript(n)      PRI1(n)
 304 #define PRI_FcCompareRange(n)           PRI1(n)
 305 #define PRI_FcCompareSize(n)            PRI1(n)
 306
 307 #define FC_OBJECT(NAME, Type, Cmp)      PRI_##Cmp(NAME)
 308
 309 typedef enum _FcMatcherPriorityDummy {
 310 #include "fcobjs.h"
 311 } FcMatcherPriorityDummy;
 312
 313 #undef FC_OBJECT
 314
 315
 316 /* Canonical match priority order. */
 317
 318 #undef PRI1
 319 #define PRI1(n)                                 \
 320     PRI_ ## n,                                  \
 321     PRI_ ## n ## _STRONG = PRI_ ## n,           \
 322     PRI_ ## n ## _WEAK = PRI_ ## n
 323
 324 typedef enum _FcMatcherPriority {
 325     PRI1(FILE),
 326     PRI1(FONTFORMAT),
 327     PRI1(VARIABLE),
 328     PRI1(SCALABLE),
 329     PRI1(COLOR),
 330     PRI1(FOUNDRY),
 331     PRI1(CHARSET),
 332     PRI_FAMILY_STRONG,
 333     PRI_POSTSCRIPT_NAME_STRONG,
 334     PRI1(LANG),
 335     PRI_FAMILY_WEAK,
 336     PRI_POSTSCRIPT_NAME_WEAK,
 337     PRI1(SYMBOL),
 338     PRI1(SPACING),
 339     PRI1(SIZE),
 340     PRI1(PIXEL_SIZE),
 341     PRI1(STYLE),
 342     PRI1(SLANT),
 343     PRI1(WEIGHT),
 344     PRI1(WIDTH),
 345     PRI1(DECORATIVE),
 346     PRI1(ANTIALIAS),
 347     PRI1(RASTERIZER),
 348     PRI1(OUTLINE),
 349     PRI1(FONTVERSION),
 350     PRI_END
 351 } FcMatcherPriority;
 352
 353 #undef PRI1
 354
 355 typedef struct _FcMatcher {
 356     FcObject object;
 357     double   (*compare) (const FcValue *v1, const FcValue *v2, FcValue *bestValue);
 358     int      strong, weak;
 359 } FcMatcher;
 360
 361 /*
 362  * Order is significant, it defines the precedence of
 363  * each value, earlier values are more significant than
 364  * later values
 365  */
 366 #define FC_OBJECT(NAME, Type, Cmp)      { FC_##NAME##_OBJECT,   Cmp,    PRI_##NAME##_STRONG,    PRI_##NAME##_WEAK },
 367 static const FcMatcher _FcMatchers [] = {
 368     { FC_INVALID_OBJECT, NULL, -1, -1 },
 369 #include "fcobjs.h"
 370 };
 371 #undef FC_OBJECT
 372
 373 static const FcMatcher*
 374 FcObjectToMatcher (FcObject object,
 375                    FcBool   include_lang)
 376 {
 377     if (include_lang)
 378     {
 379         switch (object) {
 380         case FC_FAMILYLANG_OBJECT:
 381         case FC_STYLELANG_OBJECT:
 382         case FC_FULLNAMELANG_OBJECT:
 383             object = FC_LANG_OBJECT;
 384             break;
 385         }
 386     }
 387     if (object > FC_MAX_BASE_OBJECT ||
 388         !_FcMatchers[object].compare ||
 389         _FcMatchers[object].strong == -1 ||
 390         _FcMatchers[object].weak == -1)
 391         return NULL;
 392
 393     return _FcMatchers + object;
 394 }
 395
 396 static FcBool
 397 FcCompareValueList (FcObject         object,
 398                     const FcMatcher *match,
 399                     FcValueListPtr   v1orig,    /* pattern */
 400                     FcValueListPtr   v2orig,    /* target */
 401                     FcValue         *bestValue,
 402                     double          *value,
 403                     int             *n,
 404                     FcResult        *result)
 405 {
 406     FcValueListPtr  v1, v2;
 407     double          v, best, bestStrong, bestWeak;
 408     int             j, k, pos = 0;
 409
 410     if (!match)
 411     {
 412         if (bestValue)
 413             *bestValue = FcValueCanonicalize(&v2orig->value);
 414         if (n)
 415             *n = 0;
 416         return FcTrue;
 417     }
 418
 419     best = 1e99;
 420     bestStrong = 1e99;
 421     bestWeak = 1e99;
 422     j = 0;
 423     for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
 424     {
 425         for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
 426         {
 427             FcValue matchValue;
 428             v = (match->compare) (&v1->value, &v2->value, &matchValue);
 429             if (v < 0)
 430             {
 431                 *result = FcResultTypeMismatch;
 432                 return FcFalse;
 433             }
 434             v = v * 1000 + j;
 435             if (v < best)
 436             {
 437                 if (bestValue)
 438                     *bestValue = matchValue;
 439                 best = v;
 440                 pos = k;
 441             }
 442             if (v1->binding == FcValueBindingStrong)
 443             {
 444                 if (v < bestStrong)
 445                     bestStrong = v;
 446             }
 447             else
 448             {
 449                 if (v < bestWeak)
 450                     bestWeak = v;
 451             }
 452         }
 453         j++;
 454     }
 455     if (FcDebug () & FC_DBG_MATCHV)
 456     {
 457         printf (" %s: %g ", FcObjectName (object), best);
 458         FcValueListPrint (v1orig);
 459         printf (", ");
 460         FcValueListPrint (v2orig);
 461         printf ("\n");
 462     }
 463     if (value)
 464     {
 465         int weak    = match->weak;
 466         int strong  = match->strong;
 467         if (weak == strong)
 468             value[strong] += best;
 469         else
 470         {
 471             value[weak] += bestWeak;
 472             value[strong] += bestStrong;
 473         }
 474     }
 475     if (n)
 476         *n = pos;
 477
 478     return FcTrue;
 479 }
 480
 481 /*
 482  * Return a value indicating the distance between the two lists of
 483  * values
 484  */
 485
 486 static FcBool
 487 FcCompare (FcPattern    *pat,
 488            FcPattern    *fnt,
 489            double       *value,
 490            FcResult     *result)
 491 {
 492     int             i, i1, i2;
 493
 494     for (i = 0; i < PRI_END; i++)
 495         value[i] = 0.0;
 496
 497     i1 = 0;
 498     i2 = 0;
 499     while (i1 < pat->num && i2 < fnt->num)
 500     {
 501         FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
 502         FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
 503
 504         i = FcObjectCompare(elt_i1->object, elt_i2->object);
 505         if (i > 0)
 506             i2++;
 507         else if (i < 0)
 508             i1++;
 509         else
 510         {
 511             const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
 512             if (!FcCompareValueList (elt_i1->object, match,
 513                                      FcPatternEltValues(elt_i1),
 514                                      FcPatternEltValues(elt_i2),
 515                                      NULL, value, NULL, result))
 516                 return FcFalse;
 517             i1++;
 518             i2++;
 519         }
 520     }
 521     return FcTrue;
 522 }
 523
 524 FcPattern *
 525 FcFontRenderPrepare (FcConfig       *config,
 526                      FcPattern      *pat,
 527                      FcPattern      *font)
 528 {
 529     FcPattern       *new;
 530     int             i;
 531     FcPatternElt    *fe, *pe;
 532     FcValue         v;
 533     FcResult        result;
 534     FcBool          variable = FcFalse;
 535     FcStrBuf        variations;
 536
 537     assert (pat != NULL);
 538     assert (font != NULL);
 539
 540     FcPatternObjectGetBool (font, FC_VARIABLE_OBJECT, 0, &variable);
 541     assert (variable != FcDontCare);
 542     if (variable)
 543         FcStrBufInit (&variations, NULL, 0);
 544
 545     new = FcPatternCreate ();
 546     if (!new)
 547         return NULL;
 548     for (i = 0; i < font->num; i++)
 549     {
 550         fe = &FcPatternElts(font)[i];
 551         if (fe->object == FC_FAMILYLANG_OBJECT ||
 552             fe->object == FC_STYLELANG_OBJECT ||
 553             fe->object == FC_FULLNAMELANG_OBJECT)
 554         {
 555             /* ignore those objects. we need to deal with them
 556              * another way */
 557             continue;
 558         }
 559         if (fe->object == FC_FAMILY_OBJECT ||
 560             fe->object == FC_STYLE_OBJECT ||
 561             fe->object == FC_FULLNAME_OBJECT)
 562         {
 563             FcPatternElt    *fel, *pel;
 564
 565             FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
 566             FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
 567             FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
 568
 569             fel = FcPatternObjectFindElt (font, fe->object + 1);
 570             pel = FcPatternObjectFindElt (pat, fe->object + 1);
 571
 572             if (fel && pel)
 573             {
 574                 /* The font has name languages, and pattern asks for specific language(s).
 575                  * Match on language and and prefer that result.
 576                  * Note:  Currently the code only give priority to first matching language.
 577                  */
 578                 int n = 1, j;
 579                 FcValueListPtr l1, l2, ln = NULL, ll = NULL;
 580                 const FcMatcher *match = FcObjectToMatcher (pel->object, FcTrue);
 581
 582                 if (!FcCompareValueList (pel->object, match,
 583                                          FcPatternEltValues (pel),
 584                                          FcPatternEltValues (fel), NULL, NULL, &n, &result))
 585                 {
 586                     FcPatternDestroy (new);
 587                     return NULL;
 588                 }
 589
 590                 for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
 591                      l1 != NULL || l2 != NULL;
 592                      j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
 593                 {
 594                     if (j == n)
 595                     {
 596                         if (l1)
 597                             ln = FcValueListPrepend (ln,
 598                                                      FcValueCanonicalize (&l1->value),
 599                                                      FcValueBindingStrong);
 600                         if (l2)
 601                             ll = FcValueListPrepend (ll,
 602                                                      FcValueCanonicalize (&l2->value),
 603                                                      FcValueBindingStrong);
 604                     }
 605                     else
 606                     {
 607                         if (l1)
 608                             ln = FcValueListAppend (ln,
 609                                                     FcValueCanonicalize (&l1->value),
 610                                                     FcValueBindingStrong);
 611                         if (l2)
 612                             ll = FcValueListAppend (ll,
 613                                                     FcValueCanonicalize (&l2->value),
 614                                                     FcValueBindingStrong);
 615                     }
 616                 }
 617                 FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
 618                 FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
 619
 620                 continue;
 621             }
 622             else if (fel)
 623             {
 624                 /* Pattern doesn't ask for specific language.  Copy all for name and
 625                  * lang. */
 626                 FcValueListPtr l1, l2;
 627
 628                 l1 = FcValueListDuplicate (FcPatternEltValues (fe));
 629                 l2 = FcValueListDuplicate (FcPatternEltValues (fel));
 630                 FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
 631                 FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
 632
 633                 continue;
 634             }
 635         }
 636
 637         pe = FcPatternObjectFindElt (pat, fe->object);
 638         if (pe)
 639         {
 640             const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
 641             if (!FcCompareValueList (pe->object, match,
 642                                      FcPatternEltValues(pe),
 643                                      FcPatternEltValues(fe), &v, NULL, NULL, &result))
 644             {
 645                 FcPatternDestroy (new);
 646                 return NULL;
 647             }
 648             FcPatternObjectAdd (new, fe->object, v, FcFalse);
 649
 650             /* Set font-variations settings for standard axes in variable fonts. */
 651             if (variable &&
 652                 FcPatternEltValues(fe)->value.type == FcTypeRange &&
 653                 (fe->object == FC_WEIGHT_OBJECT ||
 654                  fe->object == FC_WIDTH_OBJECT ||
 655                  fe->object == FC_SIZE_OBJECT))
 656             {
 657                 double num;
 658                 FcChar8 temp[128];
 659                 const char *tag = "    ";
 660                 assert (v.type == FcTypeDouble);
 661                 num = v.u.d;
 662                 if (variations.len)
 663                     FcStrBufChar (&variations, ',');
 664                 switch (fe->object)
 665                 {
 666                     case FC_WEIGHT_OBJECT:
 667                         tag = "wght";
 668                         num = FcWeightToOpenType (num);
 669                         break;
 670
 671                     case FC_WIDTH_OBJECT:
 672                         tag = "wdth";
 673                         break;
 674
 675                     case FC_SIZE_OBJECT:
 676                         tag = "opsz";
 677                         break;
 678                 }
 679                 sprintf ((char *) temp, "%4s=%g", tag, num);
 680                 FcStrBufString (&variations, temp);
 681             }
 682         }
 683         else
 684         {
 685             if (FcRefIsConst (&font->ref) && fe->object == FC_FILE_OBJECT)
 686             {
 687                 FcValueListPtr l = FcPatternEltValues (fe);
 688                 FcChar8 *dir, *alias;
 689
 690                 while (l->value.type != FcTypeString)
 691                     l = FcValueListNext (l);
 692                 if (!l)
 693                     goto bail0;
 694                 dir = FcStrDirname (FcValueString (&l->value));
 695                 if (!config)
 696                     config = FcConfigGetCurrent ();
 697                 if (config && FcHashTableFind (config->alias_table, dir, (void **) &alias))
 698                 {
 699                     FcChar8 *base = FcStrBasename (FcValueString (&l->value));
 700                     FcChar8 *s = FcStrBuildFilename (alias, base, NULL);
 701                     FcValue v;
 702
 703                     FcStrFree (alias);
 704                     FcStrFree (base);
 705                     v.type = FcTypeString;
 706                     v.u.s = s;
 707                     FcPatternObjectAddWithBinding (new, fe->object,
 708                                                    FcValueCanonicalize (&v),
 709                                                    l->binding,
 710                                                    FcTrue);
 711                     FcStrFree (s);
 712                     FcStrFree (dir);
 713                     goto bail0;
 714                 }
 715                 else
 716                     FcStrFree (dir);
 717             }
 718             FcPatternObjectListAdd (new, fe->object,
 719                                     FcValueListDuplicate (FcPatternEltValues (fe)),
 720                                     FcTrue);
 721           bail0:;
 722         }
 723     }
 724     for (i = 0; i < pat->num; i++)
 725     {
 726         pe = &FcPatternElts(pat)[i];
 727         fe = FcPatternObjectFindElt (font, pe->object);
 728         if (!fe &&
 729             pe->object != FC_FAMILYLANG_OBJECT &&
 730             pe->object != FC_STYLELANG_OBJECT &&
 731             pe->object != FC_FULLNAMELANG_OBJECT)
 732         {
 733             FcPatternObjectListAdd (new, pe->object,
 734                                     FcValueListDuplicate (FcPatternEltValues(pe)),
 735                                     FcFalse);
 736         }
 737     }
 738
 739     if (variable && variations.len)
 740     {
 741         FcChar8 *vars = NULL;
 742         if (FcPatternObjectGetString (new, FC_FONT_VARIATIONS_OBJECT, 0, &vars) == FcResultMatch)
 743         {
 744             FcStrBufChar (&variations, ',');
 745             FcStrBufString (&variations, vars);
 746             FcPatternObjectDel (new, FC_FONT_VARIATIONS_OBJECT);
 747         }
 748
 749         FcPatternObjectAddString (new, FC_FONT_VARIATIONS_OBJECT, FcStrBufDoneStatic (&variations));
 750         FcStrBufDestroy (&variations);
 751     }
 752
 753     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 754     return new;
 755 }
 756
 757 static FcPattern *
 758 FcFontSetMatchInternal (FcFontSet   **sets,
 759                         int         nsets,
 760                         FcPattern   *p,
 761                         FcResult    *result)
 762 {
 763     double          score[PRI_END], bestscore[PRI_END];
 764     int             f;
 765     FcFontSet       *s;
 766     FcPattern       *best;
 767     int             i;
 768     int             set;
 769
 770     for (i = 0; i < PRI_END; i++)
 771         bestscore[i] = 0;
 772     best = 0;
 773     if (FcDebug () & FC_DBG_MATCH)
 774     {
 775         printf ("Match ");
 776         FcPatternPrint (p);
 777     }
 778     for (set = 0; set < nsets; set++)
 779     {
 780         s = sets[set];
 781         if (!s)
 782             continue;
 783         for (f = 0; f < s->nfont; f++)
 784         {
 785             if (FcDebug () & FC_DBG_MATCHV)
 786             {
 787                 printf ("Font %d ", f);
 788                 FcPatternPrint (s->fonts[f]);
 789             }
 790             if (!FcCompare (p, s->fonts[f], score, result))
 791                 return 0;
 792             if (FcDebug () & FC_DBG_MATCHV)
 793             {
 794                 printf ("Score");
 795                 for (i = 0; i < PRI_END; i++)
 796                 {
 797                     printf (" %g", score[i]);
 798                 }
 799                 printf ("\n");
 800             }
 801             for (i = 0; i < PRI_END; i++)
 802             {
 803                 if (best && bestscore[i] < score[i])
 804                     break;
 805                 if (!best || score[i] < bestscore[i])
 806                 {
 807                     for (i = 0; i < PRI_END; i++)
 808                         bestscore[i] = score[i];
 809                     best = s->fonts[f];
 810                     break;
 811                 }
 812             }
 813         }
 814     }
 815     if (FcDebug () & FC_DBG_MATCH)
 816     {
 817         printf ("Best score");
 818         for (i = 0; i < PRI_END; i++)
 819             printf (" %g", bestscore[i]);
 820         printf ("\n");
 821         FcPatternPrint (best);
 822     }
 823     if (FcDebug () & FC_DBG_MATCH2)
 824     {
 825         char *env = getenv ("FC_DBG_MATCH_FILTER");
 826         FcObjectSet *os = NULL;
 827
 828         if (env)
 829         {
 830             char *ss, *s;
 831             char *p;
 832             FcBool f = FcTrue;
 833
 834             ss = s = strdup (env);
 835             os = FcObjectSetCreate ();
 836             while (f)
 837             {
 838                 size_t len;
 839                 char *x;
 840
 841                 if (!(p = strchr (s, ',')))
 842                 {
 843                     f = FcFalse;
 844                     len = strlen (s) + 1;
 845                 }
 846                 else
 847                 {
 848                     len = (p - s) + 1;
 849                 }
 850                 x = malloc (sizeof (char) * len);
 851                 strncpy (x, s, len - 1);
 852                 x[len - 1] = 0;
 853                 if (FcObjectFromName (x) > 0)
 854                     FcObjectSetAdd (os, x);
 855                 s = p + 1;
 856                 free (x);
 857             }
 858             free (ss);
 859         }
 860         FcPatternPrint2 (p, best, os);
 861         if (os)
 862             FcObjectSetDestroy (os);
 863     }
 864     /* assuming that 'result' is initialized with FcResultNoMatch
 865      * outside this function */
 866     if (best)
 867         *result = FcResultMatch;
 868
 869     return best;
 870 }
 871
 872 FcPattern *
 873 FcFontSetMatch (FcConfig    *config,
 874                 FcFontSet   **sets,
 875                 int         nsets,
 876                 FcPattern   *p,
 877                 FcResult    *result)
 878 {
 879     FcPattern       *best;
 880
 881     assert (sets != NULL);
 882     assert (p != NULL);
 883     assert (result != NULL);
 884
 885     *result = FcResultNoMatch;
 886
 887     if (!config)
 888     {
 889         config = FcConfigGetCurrent ();
 890         if (!config)
 891             return 0;
 892     }
 893     best = FcFontSetMatchInternal (sets, nsets, p, result);
 894     if (best)
 895         return FcFontRenderPrepare (config, p, best);
 896     else
 897         return NULL;
 898 }
 899
 900 FcPattern *
 901 FcFontMatch (FcConfig   *config,
 902              FcPattern  *p,
 903              FcResult   *result)
 904 {
 905     FcFontSet   *sets[2];
 906     int         nsets;
 907     FcPattern   *best;
 908
 909     assert (p != NULL);
 910     assert (result != NULL);
 911
 912     *result = FcResultNoMatch;
 913
 914     if (!config)
 915     {
 916         config = FcConfigGetCurrent ();
 917         if (!config)
 918             return 0;
 919     }
 920     nsets = 0;
 921     if (config->fonts[FcSetSystem])
 922         sets[nsets++] = config->fonts[FcSetSystem];
 923     if (config->fonts[FcSetApplication])
 924         sets[nsets++] = config->fonts[FcSetApplication];
 925
 926     best = FcFontSetMatchInternal (sets, nsets, p, result);
 927     if (best)
 928         return FcFontRenderPrepare (config, p, best);
 929     else
 930         return NULL;
 931 }
 932
 933 typedef struct _FcSortNode {
 934     FcPattern   *pattern;
 935     double      score[PRI_END];
 936 } FcSortNode;
 937
 938 static int
 939 FcSortCompare (const void *aa, const void *ab)
 940 {
 941     FcSortNode  *a = *(FcSortNode **) aa;
 942     FcSortNode  *b = *(FcSortNode **) ab;
 943     double      *as = &a->score[0];
 944     double      *bs = &b->score[0];
 945     double      ad = 0, bd = 0;
 946     int         i;
 947
 948     i = PRI_END;
 949     while (i-- && (ad = *as++) == (bd = *bs++))
 950         ;
 951     return ad < bd ? -1 : ad > bd ? 1 : 0;
 952 }
 953
 954 static FcBool
 955 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
 956 {
 957     FcBool ret = FcFalse;
 958     FcCharSet *cs;
 959     int i;
 960
 961     cs = 0;
 962     if (trim || csp)
 963     {
 964         cs = FcCharSetCreate ();
 965         if (cs == NULL)
 966             goto bail;
 967     }
 968
 969     for (i = 0; i < nnode; i++)
 970     {
 971         FcSortNode      *node = *n++;
 972         FcBool          adds_chars = FcFalse;
 973
 974         /*
 975          * Only fetch node charset if we'd need it
 976          */
 977         if (cs)
 978         {
 979             FcCharSet   *ncs;
 980
 981             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
 982                 FcResultMatch)
 983                 continue;
 984
 985             if (!FcCharSetMerge (cs, ncs, &adds_chars))
 986                 goto bail;
 987         }
 988
 989         /*
 990          * If this font isn't a subset of the previous fonts,
 991          * add it to the list
 992          */
 993         if (!i || !trim || adds_chars)
 994         {
 995             FcPatternReference (node->pattern);
 996             if (FcDebug () & FC_DBG_MATCHV)
 997             {
 998                 printf ("Add ");
 999                 FcPatternPrint (node->pattern);
1000             }
1001             if (!FcFontSetAdd (fs, node->pattern))
1002             {
1003                 FcPatternDestroy (node->pattern);
1004                 goto bail;
1005             }
1006         }
1007     }
1008     if (csp)
1009     {
1010         *csp = cs;
1011         cs = 0;
1012     }
1013
1014     ret = FcTrue;
1015
1016 bail:
1017     if (cs)
1018         FcCharSetDestroy (cs);
1019
1020     return ret;
1021 }
1022
1023 void
1024 FcFontSetSortDestroy (FcFontSet *fs)
1025 {
1026     FcFontSetDestroy (fs);
1027 }
1028
1029 FcFontSet *
1030 FcFontSetSort (FcConfig     *config FC_UNUSED,
1031                FcFontSet    **sets,
1032                int          nsets,
1033                FcPattern    *p,
1034                FcBool       trim,
1035                FcCharSet    **csp,
1036                FcResult     *result)
1037 {
1038     FcFontSet       *ret;
1039     FcFontSet       *s;
1040     FcSortNode      *nodes;
1041     FcSortNode      **nodeps, **nodep;
1042     int             nnodes;
1043     FcSortNode      *new;
1044     int             set;
1045     int             f;
1046     int             i;
1047     int             nPatternLang;
1048     FcBool          *patternLangSat;
1049     FcValue         patternLang;
1050
1051     assert (sets != NULL);
1052     assert (p != NULL);
1053     assert (result != NULL);
1054
1055     /* There are some implementation that relying on the result of
1056      * "result" to check if the return value of FcFontSetSort
1057      * is valid or not.
1058      * So we should initialize it to the conservative way since
1059      * this function doesn't return NULL anymore.
1060      */
1061     if (result)
1062         *result = FcResultNoMatch;
1063
1064     if (FcDebug () & FC_DBG_MATCH)
1065     {
1066         printf ("Sort ");
1067         FcPatternPrint (p);
1068     }
1069     nnodes = 0;
1070     for (set = 0; set < nsets; set++)
1071     {
1072         s = sets[set];
1073         if (!s)
1074             continue;
1075         nnodes += s->nfont;
1076     }
1077     if (!nnodes)
1078         return FcFontSetCreate ();
1079
1080     for (nPatternLang = 0;
1081          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
1082          nPatternLang++)
1083         ;
1084
1085     /* freed below */
1086     nodes = malloc (nnodes * sizeof (FcSortNode) +
1087                     nnodes * sizeof (FcSortNode *) +
1088                     nPatternLang * sizeof (FcBool));
1089     if (!nodes)
1090         goto bail0;
1091     nodeps = (FcSortNode **) (nodes + nnodes);
1092     patternLangSat = (FcBool *) (nodeps + nnodes);
1093
1094     new = nodes;
1095     nodep = nodeps;
1096     for (set = 0; set < nsets; set++)
1097     {
1098         s = sets[set];
1099         if (!s)
1100             continue;
1101         for (f = 0; f < s->nfont; f++)
1102         {
1103             if (FcDebug () & FC_DBG_MATCHV)
1104             {
1105                 printf ("Font %d ", f);
1106                 FcPatternPrint (s->fonts[f]);
1107             }
1108             new->pattern = s->fonts[f];
1109             if (!FcCompare (p, new->pattern, new->score, result))
1110                 goto bail1;
1111             if (FcDebug () & FC_DBG_MATCHV)
1112             {
1113                 printf ("Score");
1114                 for (i = 0; i < PRI_END; i++)
1115                 {
1116                     printf (" %g", new->score[i]);
1117                 }
1118                 printf ("\n");
1119             }
1120             *nodep = new;
1121             new++;
1122             nodep++;
1123         }
1124     }
1125
1126     nnodes = new - nodes;
1127
1128     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1129            FcSortCompare);
1130
1131     for (i = 0; i < nPatternLang; i++)
1132         patternLangSat[i] = FcFalse;
1133
1134     for (f = 0; f < nnodes; f++)
1135     {
1136         FcBool  satisfies = FcFalse;
1137         /*
1138          * If this node matches any language, go check
1139          * which ones and satisfy those entries
1140          */
1141         if (nodeps[f]->score[PRI_LANG] < 2000)
1142         {
1143             for (i = 0; i < nPatternLang; i++)
1144             {
1145                 FcValue     nodeLang;
1146
1147                 if (!patternLangSat[i] &&
1148                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
1149                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
1150                 {
1151                     FcValue matchValue;
1152                     double  compare = FcCompareLang (&patternLang, &nodeLang, &matchValue);
1153                     if (compare >= 0 && compare < 2)
1154                     {
1155                         if (FcDebug () & FC_DBG_MATCHV)
1156                         {
1157                             FcChar8 *family;
1158                             FcChar8 *style;
1159
1160                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
1161                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
1162                                 printf ("Font %s:%s matches language %d\n", family, style, i);
1163                         }
1164                         patternLangSat[i] = FcTrue;
1165                         satisfies = FcTrue;
1166                         break;
1167                     }
1168                 }
1169             }
1170         }
1171         if (!satisfies)
1172         {
1173             nodeps[f]->score[PRI_LANG] = 10000.0;
1174         }
1175     }
1176
1177     /*
1178      * Re-sort once the language issues have been settled
1179      */
1180     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1181            FcSortCompare);
1182
1183     ret = FcFontSetCreate ();
1184     if (!ret)
1185         goto bail1;
1186
1187     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
1188         goto bail2;
1189
1190     free (nodes);
1191
1192     if (FcDebug() & FC_DBG_MATCH)
1193     {
1194         printf ("First font ");
1195         FcPatternPrint (ret->fonts[0]);
1196     }
1197     if (ret->nfont > 0)
1198         *result = FcResultMatch;
1199
1200     return ret;
1201
1202 bail2:
1203     FcFontSetDestroy (ret);
1204 bail1:
1205     free (nodes);
1206 bail0:
1207     return 0;
1208 }
1209
1210 FcFontSet *
1211 FcFontSort (FcConfig    *config,
1212             FcPattern   *p,
1213             FcBool      trim,
1214             FcCharSet   **csp,
1215             FcResult    *result)
1216 {
1217     FcFontSet   *sets[2];
1218     int         nsets;
1219
1220     assert (p != NULL);
1221     assert (result != NULL);
1222
1223     *result = FcResultNoMatch;
1224
1225     if (!config)
1226     {
1227         config = FcConfigGetCurrent ();
1228         if (!config)
1229             return 0;
1230     }
1231     nsets = 0;
1232     if (config->fonts[FcSetSystem])
1233         sets[nsets++] = config->fonts[FcSetSystem];
1234     if (config->fonts[FcSetApplication])
1235         sets[nsets++] = config->fonts[FcSetApplication];
1236     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1237 }
1238 #define __fcmatch__
1239 #include "fcaliastail.h"
1240 #undef __fcmatch__