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