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