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