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 ((int) 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 ((int) 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 ((int) value1.type) {
  90     case FcTypeLangSet:
  91         switch ((int) 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 ((int) 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 ((int) 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 ((int) 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 (FcFontSet   **sets,
 567                         int         nsets,
 568                         FcPattern   *p,
 569                         FcResult    *result)
 570 {
 571     double          score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
 572     int             f;
 573     FcFontSet       *s;
 574     FcPattern       *best;
 575     int             i;
 576     int             set;
 577
 578     for (i = 0; i < NUM_MATCH_VALUES; i++)
 579         bestscore[i] = 0;
 580     best = 0;
 581     if (FcDebug () & FC_DBG_MATCH)
 582     {
 583         printf ("Match ");
 584         FcPatternPrint (p);
 585     }
 586     for (set = 0; set < nsets; set++)
 587     {
 588         s = sets[set];
 589         if (!s)
 590             continue;
 591         for (f = 0; f < s->nfont; f++)
 592         {
 593             if (FcDebug () & FC_DBG_MATCHV)
 594             {
 595                 printf ("Font %d ", f);
 596                 FcPatternPrint (s->fonts[f]);
 597             }
 598             if (!FcCompare (p, s->fonts[f], score, result))
 599                 return 0;
 600             if (FcDebug () & FC_DBG_MATCHV)
 601             {
 602                 printf ("Score");
 603                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 604                 {
 605                     printf (" %g", score[i]);
 606                 }
 607                 printf ("\n");
 608             }
 609             for (i = 0; i < NUM_MATCH_VALUES; i++)
 610             {
 611                 if (best && bestscore[i] < score[i])
 612                     break;
 613                 if (!best || score[i] < bestscore[i])
 614                 {
 615                     for (i = 0; i < NUM_MATCH_VALUES; i++)
 616                         bestscore[i] = score[i];
 617                     best = s->fonts[f];
 618                     break;
 619                 }
 620             }
 621         }
 622     }
 623     if (FcDebug () & FC_DBG_MATCH)
 624     {
 625         printf ("Best score");
 626         for (i = 0; i < NUM_MATCH_VALUES; i++)
 627             printf (" %g", bestscore[i]);
 628         printf ("\n");
 629         FcPatternPrint (best);
 630     }
 631     /* assuming that 'result' is initialized with FcResultNoMatch
 632      * outside this function */
 633     if (best)
 634         *result = FcResultMatch;
 635
 636     return best;
 637 }
 638
 639 FcPattern *
 640 FcFontSetMatch (FcConfig    *config,
 641                 FcFontSet   **sets,
 642                 int         nsets,
 643                 FcPattern   *p,
 644                 FcResult    *result)
 645 {
 646     FcPattern       *best;
 647
 648     assert (sets != NULL);
 649     assert (p != NULL);
 650     assert (result != NULL);
 651
 652     *result = FcResultNoMatch;
 653
 654     if (!config)
 655     {
 656         config = FcConfigGetCurrent ();
 657         if (!config)
 658             return 0;
 659     }
 660     best = FcFontSetMatchInternal (sets, nsets, p, result);
 661     if (best)
 662         return FcFontRenderPrepare (config, p, best);
 663     else
 664         return NULL;
 665 }
 666
 667 FcPattern *
 668 FcFontMatch (FcConfig   *config,
 669              FcPattern  *p,
 670              FcResult   *result)
 671 {
 672     FcFontSet   *sets[2];
 673     int         nsets;
 674     FcPattern   *best;
 675
 676     assert (p != NULL);
 677     assert (result != NULL);
 678
 679     *result = FcResultNoMatch;
 680
 681     if (!config)
 682     {
 683         config = FcConfigGetCurrent ();
 684         if (!config)
 685             return 0;
 686     }
 687     nsets = 0;
 688     if (config->fonts[FcSetSystem])
 689         sets[nsets++] = config->fonts[FcSetSystem];
 690     if (config->fonts[FcSetApplication])
 691         sets[nsets++] = config->fonts[FcSetApplication];
 692
 693     best = FcFontSetMatchInternal (sets, nsets, p, result);
 694     if (best)
 695         return FcFontRenderPrepare (config, p, best);
 696     else
 697         return NULL;
 698 }
 699
 700 typedef struct _FcSortNode {
 701     FcPattern   *pattern;
 702     double      score[NUM_MATCH_VALUES];
 703 } FcSortNode;
 704
 705 static int
 706 FcSortCompare (const void *aa, const void *ab)
 707 {
 708     FcSortNode  *a = *(FcSortNode **) aa;
 709     FcSortNode  *b = *(FcSortNode **) ab;
 710     double      *as = &a->score[0];
 711     double      *bs = &b->score[0];
 712     double      ad = 0, bd = 0;
 713     int         i;
 714
 715     i = NUM_MATCH_VALUES;
 716     while (i-- && (ad = *as++) == (bd = *bs++))
 717         ;
 718     return ad < bd ? -1 : ad > bd ? 1 : 0;
 719 }
 720
 721 static FcBool
 722 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
 723 {
 724     FcBool ret = FcFalse;
 725     FcCharSet *cs;
 726
 727     cs = 0;
 728     if (trim || csp)
 729     {
 730         cs = FcCharSetCreate ();
 731         if (cs == NULL)
 732             goto bail;
 733     }
 734
 735     while (nnode--)
 736     {
 737         FcSortNode      *node = *n++;
 738         FcBool          adds_chars = FcFalse;
 739
 740         /*
 741          * Only fetch node charset if we'd need it
 742          */
 743         if (cs)
 744         {
 745             FcCharSet   *ncs;
 746
 747             if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
 748                 FcResultMatch)
 749                 continue;
 750
 751             if (!FcCharSetMerge (cs, ncs, &adds_chars))
 752                 goto bail;
 753         }
 754
 755         /*
 756          * If this font isn't a subset of the previous fonts,
 757          * add it to the list
 758          */
 759         if (!trim || adds_chars)
 760         {
 761             FcPatternReference (node->pattern);
 762             if (FcDebug () & FC_DBG_MATCHV)
 763             {
 764                 printf ("Add ");
 765                 FcPatternPrint (node->pattern);
 766             }
 767             if (!FcFontSetAdd (fs, node->pattern))
 768             {
 769                 FcPatternDestroy (node->pattern);
 770                 goto bail;
 771             }
 772         }
 773     }
 774     if (csp)
 775     {
 776         *csp = cs;
 777         cs = 0;
 778     }
 779
 780     ret = FcTrue;
 781
 782 bail:
 783     if (cs)
 784         FcCharSetDestroy (cs);
 785
 786     return ret;
 787 }
 788
 789 void
 790 FcFontSetSortDestroy (FcFontSet *fs)
 791 {
 792     FcFontSetDestroy (fs);
 793 }
 794
 795 FcFontSet *
 796 FcFontSetSort (FcConfig     *config FC_UNUSED,
 797                FcFontSet    **sets,
 798                int          nsets,
 799                FcPattern    *p,
 800                FcBool       trim,
 801                FcCharSet    **csp,
 802                FcResult     *result)
 803 {
 804     FcFontSet       *ret;
 805     FcFontSet       *s;
 806     FcSortNode      *nodes;
 807     FcSortNode      **nodeps, **nodep;
 808     int             nnodes;
 809     FcSortNode      *new;
 810     int             set;
 811     int             f;
 812     int             i;
 813     int             nPatternLang;
 814     FcBool          *patternLangSat;
 815     FcValue         patternLang;
 816
 817     assert (sets != NULL);
 818     assert (p != NULL);
 819     assert (result != NULL);
 820
 821     /* There are some implementation that relying on the result of
 822      * "result" to check if the return value of FcFontSetSort
 823      * is valid or not.
 824      * So we should initialize it to the conservative way since
 825      * this function doesn't return NULL anymore.
 826      */
 827     if (result)
 828         *result = FcResultNoMatch;
 829
 830     if (FcDebug () & FC_DBG_MATCH)
 831     {
 832         printf ("Sort ");
 833         FcPatternPrint (p);
 834     }
 835     nnodes = 0;
 836     for (set = 0; set < nsets; set++)
 837     {
 838         s = sets[set];
 839         if (!s)
 840             continue;
 841         nnodes += s->nfont;
 842     }
 843     if (!nnodes)
 844         return FcFontSetCreate ();
 845
 846     for (nPatternLang = 0;
 847          FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
 848          nPatternLang++)
 849         ;
 850
 851     /* freed below */
 852     nodes = malloc (nnodes * sizeof (FcSortNode) +
 853                     nnodes * sizeof (FcSortNode *) +
 854                     nPatternLang * sizeof (FcBool));
 855     if (!nodes)
 856         goto bail0;
 857     nodeps = (FcSortNode **) (nodes + nnodes);
 858     patternLangSat = (FcBool *) (nodeps + nnodes);
 859
 860     new = nodes;
 861     nodep = nodeps;
 862     for (set = 0; set < nsets; set++)
 863     {
 864         s = sets[set];
 865         if (!s)
 866             continue;
 867         for (f = 0; f < s->nfont; f++)
 868         {
 869             if (FcDebug () & FC_DBG_MATCHV)
 870             {
 871                 printf ("Font %d ", f);
 872                 FcPatternPrint (s->fonts[f]);
 873             }
 874             new->pattern = s->fonts[f];
 875             if (!FcCompare (p, new->pattern, new->score, result))
 876                 goto bail1;
 877             if (FcDebug () & FC_DBG_MATCHV)
 878             {
 879                 printf ("Score");
 880                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 881                 {
 882                     printf (" %g", new->score[i]);
 883                 }
 884                 printf ("\n");
 885             }
 886             *nodep = new;
 887             new++;
 888             nodep++;
 889         }
 890     }
 891
 892     nnodes = new - nodes;
 893
 894     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 895            FcSortCompare);
 896
 897     for (i = 0; i < nPatternLang; i++)
 898         patternLangSat[i] = FcFalse;
 899
 900     for (f = 0; f < nnodes; f++)
 901     {
 902         FcBool  satisfies = FcFalse;
 903         /*
 904          * If this node matches any language, go check
 905          * which ones and satisfy those entries
 906          */
 907         if (nodeps[f]->score[MATCH_LANG_INDEX] < 2000)
 908         {
 909             for (i = 0; i < nPatternLang; i++)
 910             {
 911                 FcValue     nodeLang;
 912
 913                 if (!patternLangSat[i] &&
 914                     FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
 915                     FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
 916                 {
 917                     double  compare = FcCompareLang (&patternLang, &nodeLang);
 918                     if (compare >= 0 && compare < 2)
 919                     {
 920                         if (FcDebug () & FC_DBG_MATCHV)
 921                         {
 922                             FcChar8 *family;
 923                             FcChar8 *style;
 924
 925                             if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
 926                                 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
 927                                 printf ("Font %s:%s matches language %d\n", family, style, i);
 928                         }
 929                         patternLangSat[i] = FcTrue;
 930                         satisfies = FcTrue;
 931                         break;
 932                     }
 933                 }
 934             }
 935         }
 936         if (!satisfies)
 937             nodeps[f]->score[MATCH_LANG_INDEX] = 10000.0;
 938     }
 939
 940     /*
 941      * Re-sort once the language issues have been settled
 942      */
 943     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 944            FcSortCompare);
 945
 946     ret = FcFontSetCreate ();
 947     if (!ret)
 948         goto bail1;
 949
 950     if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
 951         goto bail2;
 952
 953     free (nodes);
 954
 955     if (FcDebug() & FC_DBG_MATCH)
 956     {
 957         printf ("First font ");
 958         FcPatternPrint (ret->fonts[0]);
 959     }
 960     if (ret->nfont > 0)
 961         *result = FcResultMatch;
 962
 963     return ret;
 964
 965 bail2:
 966     FcFontSetDestroy (ret);
 967 bail1:
 968     free (nodes);
 969 bail0:
 970     return 0;
 971 }
 972
 973 FcFontSet *
 974 FcFontSort (FcConfig    *config,
 975             FcPattern   *p,
 976             FcBool      trim,
 977             FcCharSet   **csp,
 978             FcResult    *result)
 979 {
 980     FcFontSet   *sets[2];
 981     int         nsets;
 982
 983     assert (p != NULL);
 984     assert (result != NULL);
 985
 986     *result = FcResultNoMatch;
 987
 988     if (!config)
 989     {
 990         config = FcConfigGetCurrent ();
 991         if (!config)
 992             return 0;
 993     }
 994     nsets = 0;
 995     if (config->fonts[FcSetSystem])
 996         sets[nsets++] = config->fonts[FcSetSystem];
 997     if (config->fonts[FcSetApplication])
 998         sets[nsets++] = config->fonts[FcSetApplication];
 999     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1000 }
1001 #define __fcmatch__
1002 #include "fcaliastail.h"
1003 #undef __fcmatch__