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             FcPatternObjectListAdd (new, fe->object,
 686                                     FcValueListDuplicate (FcPatternEltValues (fe)),
 687                                     FcTrue);
 688         }
 689     }
 690     for (i = 0; i < pat->num; i++)
 691     {
 692         pe = &FcPatternElts(pat)[i];
 693         fe = FcPatternObjectFindElt (font, pe->object);
 694         if (!fe &&
 695             pe->object != FC_FAMILYLANG_OBJECT &&
 696             pe->object != FC_STYLELANG_OBJECT &&
 697             pe->object != FC_FULLNAMELANG_OBJECT)
 698         {
 699             FcPatternObjectListAdd (new, pe->object,
 700                                     FcValueListDuplicate (FcPatternEltValues(pe)),
 701                                     FcFalse);
 702         }
 703     }
 704
 705     if (variable && variations.len)
 706     {
 707         FcChar8 *vars = NULL;
 708         if (FcPatternObjectGetString (new, FC_FONT_VARIATIONS_OBJECT, 0, &vars) == FcResultMatch)
 709         {
 710             FcStrBufChar (&variations, ',');
 711             FcStrBufString (&variations, vars);
 712             FcPatternObjectDel (new, FC_FONT_VARIATIONS_OBJECT);
 713         }
 714
 715         FcPatternObjectAddString (new, FC_FONT_VARIATIONS_OBJECT, FcStrBufDoneStatic (&variations));
 716         FcStrBufDestroy (&variations);
 717     }
 718
 719     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 720     return new;
 721 }
 722
 723 static FcPattern *
 724 FcFontSetMatchInternal (FcFontSet   **sets,
 725                         int         nsets,
 726                         FcPattern   *p,
 727                         FcResult    *result)
 728 {
 729     double          score[PRI_END], bestscore[PRI_END];
 730     int             f;
 731     FcFontSet       *s;
 732     FcPattern       *best;
 733     int             i;
 734     int             set;
 735
 736     for (i = 0; i < PRI_END; i++)
 737         bestscore[i] = 0;
 738     best = 0;
 739     if (FcDebug () & FC_DBG_MATCH)
 740     {
 741         printf ("Match ");
 742         FcPatternPrint (p);
 743     }
 744     for (set = 0; set < nsets; set++)
 745     {
 746         s = sets[set];
 747         if (!s)
 748             continue;
 749         for (f = 0; f < s->nfont; f++)
 750         {
 751             if (FcDebug () & FC_DBG_MATCHV)
 752             {
 753                 printf ("Font %d ", f);
 754                 FcPatternPrint (s->fonts[f]);
 755             }
 756             if (!FcCompare (p, s->fonts[f], score, result))
 757                 return 0;
 758             if (FcDebug () & FC_DBG_MATCHV)
 759             {
 760                 printf ("Score");
 761                 for (i = 0; i < PRI_END; i++)
 762                 {
 763                     printf (" %g", score[i]);
 764                 }
 765                 printf ("\n");
 766             }
 767             for (i = 0; i < PRI_END; i++)
 768             {
 769                 if (best && bestscore[i] < score[i])
 770                     break;
 771                 if (!best || score[i] < bestscore[i])
 772                 {
 773                     for (i = 0; i < PRI_END; i++)
 774                         bestscore[i] = score[i];
 775                     best = s->fonts[f];
 776                     break;
 777                 }
 778             }
 779         }
 780     }
 781     if (FcDebug () & FC_DBG_MATCH)
 782     {
 783         printf ("Best score");
 784         for (i = 0; i < PRI_END; i++)
 785             printf (" %g", bestscore[i]);
 786         printf ("\n");
 787         FcPatternPrint (best);
 788     }
 789     if (FcDebug () & FC_DBG_MATCH2)
 790     {
 791         char *env = getenv ("FC_DBG_MATCH_FILTER");
 792         FcObjectSet *os = NULL;
 793
 794         if (env)
 795         {
 796             char *ss, *s;
 797             char *p;
 798             FcBool f = FcTrue;
 799
 800             ss = s = strdup (env);
 801             os = FcObjectSetCreate ();
 802             while (f)
 803             {
 804                 size_t len;
 805                 char *x;
 806
 807                 if (!(p = strchr (s, ',')))
 808                 {
 809                     f = FcFalse;
 810                     len = strlen (s);
 811                 }
 812                 else
 813                 {
 814                     len = (p - s);
 815                 }
 816                 x = malloc (sizeof (char) * (len + 1));
 817                 if (x)
 818                 {
 819                     strcpy (x, s);
 820                     if (FcObjectFromName (x) > 0)
 821                         FcObjectSetAdd (os, x);
 822                     s = p + 1;
 823                     free (x);
 824                 }
 825             }
 826             free (ss);
 827         }
 828         FcPatternPrint2 (p, best, os);
 829         if (os)
 830             FcObjectSetDestroy (os);
 831     }
 832     /* assuming that 'result' is initialized with FcResultNoMatch
 833      * outside this function */
 834     if (best)
 835         *result = FcResultMatch;
 836
 837     return best;
 838 }
 839
 840 FcPattern *
 841 FcFontSetMatch (FcConfig    *config,
 842                 FcFontSet   **sets,
 843                 int         nsets,
 844                 FcPattern   *p,
 845                 FcResult    *result)
 846 {
 847     FcPattern       *best;
 848
 849     assert (sets != NULL);
 850     assert (p != NULL);
 851     assert (result != NULL);
 852
 853     *result = FcResultNoMatch;
 854
 855     if (!config)
 856     {
 857         config = FcConfigGetCurrent ();
 858         if (!config)
 859             return 0;
 860     }
 861     best = FcFontSetMatchInternal (sets, nsets, p, result);
 862     if (best)
 863         return FcFontRenderPrepare (config, p, best);
 864     else
 865         return NULL;
 866 }
 867
 868 FcPattern *
 869 FcFontMatch (FcConfig   *config,
 870              FcPattern  *p,
 871              FcResult   *result)
 872 {
 873     FcFontSet   *sets[2];
 874     int         nsets;
 875     FcPattern   *best;
 876
 877     assert (p != NULL);
 878     assert (result != NULL);
 879
 880     *result = FcResultNoMatch;
 881
 882     if (!config)
 883     {
 884         config = FcConfigGetCurrent ();
 885         if (!config)
 886             return 0;
 887     }
 888     nsets = 0;
 889     if (config->fonts[FcSetSystem])
 890         sets[nsets++] = config->fonts[FcSetSystem];
 891     if (config->fonts[FcSetApplication])
 892         sets[nsets++] = config->fonts[FcSetApplication];
 893
 894     best = FcFontSetMatchInternal (sets, nsets, p, result);
 895     if (best)
 896         return FcFontRenderPrepare (config, p, best);
 897     else
 898         return NULL;
 899 }
 900
 901 typedef struct _FcSortNode {
 902     FcPattern   *pattern;
 903     double      score[PRI_END];
 904 } FcSortNode;
 905
 906 static int
 907 FcSortCompare (const void *aa, const void *ab)
 908 {
 909     FcSortNode  *a = *(FcSortNode **) aa;
 910     FcSortNode  *b = *(FcSortNode **) ab;
 911     double      *as = &a->score[0];
 912     double      *bs = &b->score[0];
 913     double      ad = 0, bd = 0;
 914     int         i;
 915
 916     i = PRI_END;
 917     while (i-- && (ad = *as++) == (bd = *bs++))
 918         ;
 919     return ad < bd ? -1 : ad > bd ? 1 : 0;
 920 }
 921
 922 static FcBool
 923 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
 924 {
 925     FcBool ret = FcFalse;
 926     FcCharSet *cs;
 927     int i;
 928
 929     cs = 0;
 930     if (trim || csp)
 931     {
 932         cs = FcCharSetCreate ();
 933         if (cs == NULL)
 934             goto bail;
 935     }
 936
 937     for (i = 0; i < nnode; i++)
 938     {
 939         FcSortNode      *node = *n++;
 940         FcBool          adds_chars = FcFalse;
 941
 942         /*
 943          * Only fetch node charset if we'd need it
 944          */
 945         if (cs)
 946         {
 947             FcCharSet   *ncs;
 948
 949             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
 950                 FcResultMatch)
 951                 continue;
 952
 953             if (!FcCharSetMerge (cs, ncs, &adds_chars))
 954                 goto bail;
 955         }
 956
 957         /*
 958          * If this font isn't a subset of the previous fonts,
 959          * add it to the list
 960          */
 961         if (!i || !trim || adds_chars)
 962         {
 963             FcPatternReference (node->pattern);
 964             if (FcDebug () & FC_DBG_MATCHV)
 965             {
 966                 printf ("Add ");
 967                 FcPatternPrint (node->pattern);
 968             }
 969             if (!FcFontSetAdd (fs, node->pattern))
 970             {
 971                 FcPatternDestroy (node->pattern);
 972                 goto bail;
 973             }
 974         }
 975     }
 976     if (csp)
 977     {
 978         *csp = cs;
 979         cs = 0;
 980     }
 981
 982     ret = FcTrue;
 983
 984 bail:
 985     if (cs)
 986         FcCharSetDestroy (cs);
 987
 988     return ret;
 989 }
 990
 991 void
 992 FcFontSetSortDestroy (FcFontSet *fs)
 993 {
 994     FcFontSetDestroy (fs);
 995 }
 996
 997 FcFontSet *
 998 FcFontSetSort (FcConfig     *config FC_UNUSED,
 999                FcFontSet    **sets,
1000                int          nsets,
1001                FcPattern    *p,
1002                FcBool       trim,
1003                FcCharSet    **csp,
1004                FcResult     *result)
1005 {
1006     FcFontSet       *ret;
1007     FcFontSet       *s;
1008     FcSortNode      *nodes;
1009     FcSortNode      **nodeps, **nodep;
1010     int             nnodes;
1011     FcSortNode      *new;
1012     int             set;
1013     int             f;
1014     int             i;
1015     int             nPatternLang;
1016     FcBool          *patternLangSat;
1017     FcValue         patternLang;
1018
1019     assert (sets != NULL);
1020     assert (p != NULL);
1021     assert (result != NULL);
1022
1023     /* There are some implementation that relying on the result of
1024      * "result" to check if the return value of FcFontSetSort
1025      * is valid or not.
1026      * So we should initialize it to the conservative way since
1027      * this function doesn't return NULL anymore.
1028      */
1029     if (result)
1030         *result = FcResultNoMatch;
1031
1032     if (FcDebug () & FC_DBG_MATCH)
1033     {
1034         printf ("Sort ");
1035         FcPatternPrint (p);
1036     }
1037     nnodes = 0;
1038     for (set = 0; set < nsets; set++)
1039     {
1040         s = sets[set];
1041         if (!s)
1042             continue;
1043         nnodes += s->nfont;
1044     }
1045     if (!nnodes)
1046         return FcFontSetCreate ();
1047
1048     for (nPatternLang = 0;
1049          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
1050          nPatternLang++)
1051         ;
1052
1053     /* freed below */
1054     nodes = malloc (nnodes * sizeof (FcSortNode) +
1055                     nnodes * sizeof (FcSortNode *) +
1056                     nPatternLang * sizeof (FcBool));
1057     if (!nodes)
1058         goto bail0;
1059     nodeps = (FcSortNode **) (nodes + nnodes);
1060     patternLangSat = (FcBool *) (nodeps + nnodes);
1061
1062     new = nodes;
1063     nodep = nodeps;
1064     for (set = 0; set < nsets; set++)
1065     {
1066         s = sets[set];
1067         if (!s)
1068             continue;
1069         for (f = 0; f < s->nfont; f++)
1070         {
1071             if (FcDebug () & FC_DBG_MATCHV)
1072             {
1073                 printf ("Font %d ", f);
1074                 FcPatternPrint (s->fonts[f]);
1075             }
1076             new->pattern = s->fonts[f];
1077             if (!FcCompare (p, new->pattern, new->score, result))
1078                 goto bail1;
1079             if (FcDebug () & FC_DBG_MATCHV)
1080             {
1081                 printf ("Score");
1082                 for (i = 0; i < PRI_END; i++)
1083                 {
1084                     printf (" %g", new->score[i]);
1085                 }
1086                 printf ("\n");
1087             }
1088             *nodep = new;
1089             new++;
1090             nodep++;
1091         }
1092     }
1093
1094     nnodes = new - nodes;
1095
1096     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1097            FcSortCompare);
1098
1099     for (i = 0; i < nPatternLang; i++)
1100         patternLangSat[i] = FcFalse;
1101
1102     for (f = 0; f < nnodes; f++)
1103     {
1104         FcBool  satisfies = FcFalse;
1105         /*
1106          * If this node matches any language, go check
1107          * which ones and satisfy those entries
1108          */
1109         if (nodeps[f]->score[PRI_LANG] < 2000)
1110         {
1111             for (i = 0; i < nPatternLang; i++)
1112             {
1113                 FcValue     nodeLang;
1114
1115                 if (!patternLangSat[i] &&
1116                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
1117                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
1118                 {
1119                     FcValue matchValue;
1120                     double  compare = FcCompareLang (&patternLang, &nodeLang, &matchValue);
1121                     if (compare >= 0 && compare < 2)
1122                     {
1123                         if (FcDebug () & FC_DBG_MATCHV)
1124                         {
1125                             FcChar8 *family;
1126                             FcChar8 *style;
1127
1128                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
1129                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
1130                                 printf ("Font %s:%s matches language %d\n", family, style, i);
1131                         }
1132                         patternLangSat[i] = FcTrue;
1133                         satisfies = FcTrue;
1134                         break;
1135                     }
1136                 }
1137             }
1138         }
1139         if (!satisfies)
1140         {
1141             nodeps[f]->score[PRI_LANG] = 10000.0;
1142         }
1143     }
1144
1145     /*
1146      * Re-sort once the language issues have been settled
1147      */
1148     qsort (nodeps, nnodes, sizeof (FcSortNode *),
1149            FcSortCompare);
1150
1151     ret = FcFontSetCreate ();
1152     if (!ret)
1153         goto bail1;
1154
1155     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
1156         goto bail2;
1157
1158     free (nodes);
1159
1160     if (FcDebug() & FC_DBG_MATCH)
1161     {
1162         printf ("First font ");
1163         FcPatternPrint (ret->fonts[0]);
1164     }
1165     if (ret->nfont > 0)
1166         *result = FcResultMatch;
1167
1168     return ret;
1169
1170 bail2:
1171     FcFontSetDestroy (ret);
1172 bail1:
1173     free (nodes);
1174 bail0:
1175     return 0;
1176 }
1177
1178 FcFontSet *
1179 FcFontSort (FcConfig    *config,
1180             FcPattern   *p,
1181             FcBool      trim,
1182             FcCharSet   **csp,
1183             FcResult    *result)
1184 {
1185     FcFontSet   *sets[2];
1186     int         nsets;
1187
1188     assert (p != NULL);
1189     assert (result != NULL);
1190
1191     *result = FcResultNoMatch;
1192
1193     if (!config)
1194     {
1195         config = FcConfigGetCurrent ();
1196         if (!config)
1197             return 0;
1198     }
1199     nsets = 0;
1200     if (config->fonts[FcSetSystem])
1201         sets[nsets++] = config->fonts[FcSetSystem];
1202     if (config->fonts[FcSetApplication])
1203         sets[nsets++] = config->fonts[FcSetApplication];
1204     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1205 }
1206 #define __fcmatch__
1207 #include "fcaliastail.h"
1208 #undef __fcmatch__