src/fcmatch.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
   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 Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes 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  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD 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 <string.h>
  26 #include <ctype.h>
  27 #include "fcint.h"
  28 #include <stdio.h>
  29
  30 static double
  31 FcCompareNumber (char *object, FcValue value1, FcValue value2)
  32 {
  33     double  v1, v2, v;
  34
  35     switch (value1.type) {
  36     case FcTypeInteger:
  37         v1 = (double) value1.u.i;
  38         break;
  39     case FcTypeDouble:
  40         v1 = value1.u.d;
  41         break;
  42     default:
  43         return -1.0;
  44     }
  45     switch (value2.type) {
  46     case FcTypeInteger:
  47         v2 = (double) value2.u.i;
  48         break;
  49     case FcTypeDouble:
  50         v2 = value2.u.d;
  51         break;
  52     default:
  53         return -1.0;
  54     }
  55     v = v2 - v1;
  56     if (v < 0)
  57         v = -v;
  58     return (double) v;
  59 }
  60
  61 static double
  62 FcCompareString (char *object, FcValue value1, FcValue value2)
  63 {
  64     if (value2.type != FcTypeString || value1.type != FcTypeString)
  65         return -1.0;
  66     return (double) FcStrCmpIgnoreCase (value1.u.s, value2.u.s) != 0;
  67 }
  68
  69 static double
  70 FcCompareFamily (char *object, FcValue value1, FcValue value2)
  71 {
  72     if (value2.type != FcTypeString || value1.type != FcTypeString)
  73         return -1.0;
  74     return (double) FcStrCmpIgnoreBlanksAndCase (value1.u.s, value2.u.s) != 0;
  75 }
  76
  77 static double
  78 FcCompareLang (char *object, FcValue value1, FcValue value2)
  79 {
  80     FcLangResult    result;
  81
  82     switch (value1.type) {
  83     case FcTypeLangSet:
  84         switch (value2.type) {
  85         case FcTypeLangSet:
  86             result = FcLangSetCompare (value1.u.l, value2.u.l);
  87             break;
  88         case FcTypeString:
  89             result = FcLangSetHasLang (value1.u.l, value2.u.s);
  90             break;
  91         default:
  92             return -1.0;
  93         }
  94         break;
  95     case FcTypeString:
  96         switch (value2.type) {
  97         case FcTypeLangSet:
  98             result = FcLangSetHasLang (value2.u.l, value1.u.s);
  99             break;
 100         case FcTypeString:
 101             result = FcLangCompare (value1.u.s, value2.u.s);
 102             break;
 103         default:
 104             return -1.0;
 105         }
 106         break;
 107     default:
 108         return -1.0;
 109     }
 110     switch (result) {
 111     case FcLangEqual:
 112         return 0;
 113     case FcLangDifferentCountry:
 114         return 1;
 115     case FcLangDifferentLang:
 116     default:
 117         return 2;
 118     }
 119 }
 120
 121 static double
 122 FcCompareBool (char *object, FcValue value1, FcValue value2)
 123 {
 124     if (value2.type != FcTypeBool || value1.type != FcTypeBool)
 125         return -1.0;
 126     return (double) value2.u.b != value1.u.b;
 127 }
 128
 129 static double
 130 FcCompareCharSet (char *object, FcValue value1, FcValue value2)
 131 {
 132     if (value2.type != FcTypeCharSet || value1.type != FcTypeCharSet)
 133         return -1.0;
 134     return (double) FcCharSetSubtractCount (value1.u.c, value2.u.c);
 135 }
 136
 137 static double
 138 FcCompareSize (char *object, FcValue value1, FcValue value2)
 139 {
 140     double  v1, v2, v;
 141
 142     switch (value1.type) {
 143     case FcTypeInteger:
 144         v1 = value1.u.i;
 145         break;
 146     case FcTypeDouble:
 147         v1 = value1.u.d;
 148         break;
 149     default:
 150         return -1;
 151     }
 152     switch (value2.type) {
 153     case FcTypeInteger:
 154         v2 = value2.u.i;
 155         break;
 156     case FcTypeDouble:
 157         v2 = value2.u.d;
 158         break;
 159     default:
 160         return -1;
 161     }
 162     if (v2 == 0)
 163         return 0;
 164     v = v2 - v1;
 165     if (v < 0)
 166         v = -v;
 167     return v;
 168 }
 169
 170 typedef struct _FcMatcher {
 171     char            *object;
 172     double          (*compare) (char *object, FcValue value1, FcValue value2);
 173     int             strong, weak;
 174 } FcMatcher;
 175
 176 /*
 177  * Order is significant, it defines the precedence of
 178  * each value, earlier values are more significant than
 179  * later values
 180  */
 181 static FcMatcher _FcMatchers [] = {
 182     { FC_FOUNDRY,       FcCompareString,        0, 0 },
 183 #define MATCH_FOUNDRY       0
 184
 185     { FC_CHARSET,       FcCompareCharSet,       1, 1 },
 186 #define MATCH_CHARSET       1
 187
 188     { FC_FAMILY,        FcCompareFamily,        2, 4 },
 189 #define MATCH_FAMILY        2
 190
 191     { FC_LANG,          FcCompareLang,          3, 3 },
 192 #define MATCH_LANG          3
 193
 194     { FC_SPACING,       FcCompareNumber,        5, 5 },
 195 #define MATCH_SPACING       4
 196
 197     { FC_PIXEL_SIZE,    FcCompareSize,          6, 6 },
 198 #define MATCH_PIXEL_SIZE    5
 199
 200     { FC_STYLE,         FcCompareString,        7, 7 },
 201 #define MATCH_STYLE         6
 202
 203     { FC_SLANT,         FcCompareNumber,        8, 8 },
 204 #define MATCH_SLANT         7
 205
 206     { FC_WEIGHT,        FcCompareNumber,        9, 9 },
 207 #define MATCH_WEIGHT        8
 208
 209     { FC_ANTIALIAS,     FcCompareBool,          10, 10 },
 210 #define MATCH_ANTIALIAS     9
 211
 212     { FC_RASTERIZER,    FcCompareString,        11, 11 },
 213 #define MATCH_RASTERIZER    10
 214
 215     { FC_OUTLINE,       FcCompareBool,          12, 12 },
 216 #define MATCH_OUTLINE       11
 217
 218     { FC_FONTVERSION,   FcCompareNumber,        13, 13 },
 219 #define MATCH_FONTVERSION   12
 220 };
 221
 222 #define NUM_MATCH_VALUES    14
 223
 224 static FcBool
 225 FcCompareValueList (const char  *object,
 226                     FcValueList *v1orig,        /* pattern */
 227                     FcValueList *v2orig,        /* target */
 228                     FcValue     *bestValue,
 229                     double      *value,
 230                     FcResult    *result)
 231 {
 232     FcValueList    *v1, *v2;
 233     double          v, best, bestStrong, bestWeak;
 234     int             i;
 235     int             j;
 236
 237     /*
 238      * Locate the possible matching entry by examining the
 239      * first few characters in object
 240      */
 241     i = -1;
 242     switch (FcToLower (object[0])) {
 243     case 'f':
 244         switch (FcToLower (object[1])) {
 245         case 'o':
 246             switch (FcToLower (object[2])) {
 247             case 'u':
 248                 i = MATCH_FOUNDRY; break;
 249             case 'n':
 250                 i = MATCH_FONTVERSION; break;
 251             }
 252             break;
 253         case 'a':
 254             i = MATCH_FAMILY; break;
 255         }
 256         break;
 257     case 'c':
 258         i = MATCH_CHARSET; break;
 259     case 'a':
 260         i = MATCH_ANTIALIAS; break;
 261     case 'l':
 262         i = MATCH_LANG; break;
 263     case 's':
 264         switch (FcToLower (object[1])) {
 265         case 'p':
 266             i = MATCH_SPACING; break;
 267         case 't':
 268             i = MATCH_STYLE; break;
 269         case 'l':
 270             i = MATCH_SLANT; break;
 271         }
 272         break;
 273     case 'p':
 274         i = MATCH_PIXEL_SIZE; break;
 275     case 'w':
 276         i = MATCH_WEIGHT; break;
 277     case 'r':
 278         i = MATCH_RASTERIZER; break;
 279     case 'o':
 280         i = MATCH_OUTLINE; break;
 281     }
 282     if (i == -1 ||
 283         FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
 284                             (FcChar8 *) object) != 0)
 285     {
 286         if (bestValue)
 287             *bestValue = v2orig->value;
 288         return FcTrue;
 289     }
 290 #if 0
 291     for (i = 0; i < NUM_MATCHER; i++)
 292     {
 293         if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
 294                                  (FcChar8 *) object))
 295             break;
 296     }
 297     if (i == NUM_MATCHER)
 298     {
 299         if (bestValue)
 300             *bestValue = v2orig->value;
 301         return FcTrue;
 302     }
 303 #endif
 304     best = 1e99;
 305     bestStrong = 1e99;
 306     bestWeak = 1e99;
 307     j = 0;
 308     for (v1 = v1orig; v1; v1 = v1->next)
 309     {
 310         for (v2 = v2orig; v2; v2 = v2->next)
 311         {
 312             v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
 313                                             v1->value,
 314                                             v2->value);
 315             if (v < 0)
 316             {
 317                 *result = FcResultTypeMismatch;
 318                 return FcFalse;
 319             }
 320             if (FcDebug () & FC_DBG_MATCHV)
 321                 printf (" v %g j %d ", v, j);
 322             v = v * 100 + j;
 323             if (v < best)
 324             {
 325                 if (bestValue)
 326                     *bestValue = v2->value;
 327                 best = v;
 328             }
 329             if (v1->binding == FcValueBindingStrong)
 330             {
 331                 if (v < bestStrong)
 332                     bestStrong = v;
 333             }
 334             else
 335             {
 336                 if (v < bestWeak)
 337                     bestWeak = v;
 338             }
 339         }
 340         j++;
 341     }
 342     if (FcDebug () & FC_DBG_MATCHV)
 343     {
 344         printf (" %s: %g ", object, best);
 345         FcValueListPrint (v1orig);
 346         printf (", ");
 347         FcValueListPrint (v2orig);
 348         printf ("\n");
 349     }
 350     if (value)
 351     {
 352         int weak    = _FcMatchers[i].weak;
 353         int strong  = _FcMatchers[i].strong;
 354         if (weak == strong)
 355             value[strong] += best;
 356         else
 357         {
 358             value[weak] += bestWeak;
 359             value[strong] += bestStrong;
 360         }
 361     }
 362     return FcTrue;
 363 }
 364
 365 /*
 366  * Return a value indicating the distance between the two lists of
 367  * values
 368  */
 369
 370 static FcBool
 371 FcCompare (FcPattern    *pat,
 372            FcPattern    *fnt,
 373            double       *value,
 374            FcResult     *result)
 375 {
 376     int             i, i1, i2;
 377
 378     for (i = 0; i < NUM_MATCH_VALUES; i++)
 379         value[i] = 0.0;
 380
 381     i1 = 0;
 382     i2 = 0;
 383     while (i1 < pat->num && i2 < fnt->num)
 384     {
 385         i = strcmp (pat->elts[i1].object, fnt->elts[i2].object);
 386         if (i > 0)
 387             i2++;
 388         else if (i < 0)
 389             i1++;
 390         else
 391         {
 392             if (!FcCompareValueList (pat->elts[i1].object,
 393                                      pat->elts[i1].values,
 394                                      fnt->elts[i2].values,
 395                                      0,
 396                                      value,
 397                                      result))
 398                 return FcFalse;
 399             i1++;
 400             i2++;
 401         }
 402     }
 403     return FcTrue;
 404 #if 0
 405     for (i1 = 0; i1 < pat->num; i1++)
 406     {
 407         for (i2 = 0; i2 < fnt->num; i2++)
 408         {
 409             if (!strcmp (pat->elts[i1].object, fnt->elts[i2].object))
 410             {
 411                 break;
 412             }
 413         }
 414     }
 415     return FcTrue;
 416 #endif
 417 }
 418
 419 FcPattern *
 420 FcFontRenderPrepare (FcConfig       *config,
 421                      FcPattern      *pat,
 422                      FcPattern      *font)
 423 {
 424     FcPattern       *new;
 425     int             i;
 426     FcPatternElt    *fe, *pe;
 427     FcValue         v;
 428     FcResult        result;
 429
 430     new = FcPatternCreate ();
 431     if (!new)
 432         return 0;
 433     for (i = 0; i < font->num; i++)
 434     {
 435         fe = &font->elts[i];
 436         pe = FcPatternFindElt (pat, fe->object);
 437         if (pe)
 438         {
 439             if (!FcCompareValueList (pe->object, pe->values,
 440                                      fe->values, &v, 0, &result))
 441             {
 442                 FcPatternDestroy (new);
 443                 return 0;
 444             }
 445         }
 446         else
 447             v = fe->values->value;
 448         FcPatternAdd (new, fe->object, v, FcFalse);
 449     }
 450     for (i = 0; i < pat->num; i++)
 451     {
 452         pe = &pat->elts[i];
 453         fe = FcPatternFindElt (font, pe->object);
 454         if (!fe)
 455             FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
 456     }
 457     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 458     return new;
 459 }
 460
 461 FcPattern *
 462 FcFontSetMatch (FcConfig    *config,
 463                 FcFontSet   **sets,
 464                 int         nsets,
 465                 FcPattern   *p,
 466                 FcResult    *result)
 467 {
 468     double          score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
 469     int             f;
 470     FcFontSet       *s;
 471     FcPattern       *best;
 472     int             i;
 473     int             set;
 474
 475     for (i = 0; i < NUM_MATCH_VALUES; i++)
 476         bestscore[i] = 0;
 477     best = 0;
 478     if (FcDebug () & FC_DBG_MATCH)
 479     {
 480         printf ("Match ");
 481         FcPatternPrint (p);
 482     }
 483     if (!config)
 484     {
 485         config = FcConfigGetCurrent ();
 486         if (!config)
 487             return 0;
 488     }
 489     for (set = 0; set < nsets; set++)
 490     {
 491         s = sets[set];
 492         if (!s)
 493             continue;
 494         for (f = 0; f < s->nfont; f++)
 495         {
 496             if (FcDebug () & FC_DBG_MATCHV)
 497             {
 498                 printf ("Font %d ", f);
 499                 FcPatternPrint (s->fonts[f]);
 500             }
 501             if (!FcCompare (p, s->fonts[f], score, result))
 502                 return 0;
 503             if (FcDebug () & FC_DBG_MATCHV)
 504             {
 505                 printf ("Score");
 506                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 507                 {
 508                     printf (" %g", score[i]);
 509                 }
 510                 printf ("\n");
 511             }
 512             for (i = 0; i < NUM_MATCH_VALUES; i++)
 513             {
 514                 if (best && bestscore[i] < score[i])
 515                     break;
 516                 if (!best || score[i] < bestscore[i])
 517                 {
 518                     for (i = 0; i < NUM_MATCH_VALUES; i++)
 519                         bestscore[i] = score[i];
 520                     best = s->fonts[f];
 521                     break;
 522                 }
 523             }
 524         }
 525     }
 526     if (FcDebug () & FC_DBG_MATCH)
 527     {
 528         printf ("Best score");
 529         for (i = 0; i < NUM_MATCH_VALUES; i++)
 530             printf (" %g", bestscore[i]);
 531         FcPatternPrint (best);
 532     }
 533     if (!best)
 534     {
 535         *result = FcResultNoMatch;
 536         return 0;
 537     }
 538     return FcFontRenderPrepare (config, p, best);
 539 }
 540
 541 FcPattern *
 542 FcFontMatch (FcConfig   *config,
 543              FcPattern  *p,
 544              FcResult   *result)
 545 {
 546     FcFontSet   *sets[2];
 547     int         nsets;
 548
 549     if (!config)
 550     {
 551         config = FcConfigGetCurrent ();
 552         if (!config)
 553             return 0;
 554     }
 555     nsets = 0;
 556     if (config->fonts[FcSetSystem])
 557         sets[nsets++] = config->fonts[FcSetSystem];
 558     if (config->fonts[FcSetApplication])
 559         sets[nsets++] = config->fonts[FcSetApplication];
 560     return FcFontSetMatch (config, sets, nsets, p, result);
 561 }
 562
 563 typedef struct _FcSortNode {
 564     FcPattern   *pattern;
 565     double      score[NUM_MATCH_VALUES];
 566 } FcSortNode;
 567
 568 static int
 569 FcSortCompare (const void *aa, const void *ab)
 570 {
 571     FcSortNode  *a = *(FcSortNode **) aa;
 572     FcSortNode  *b = *(FcSortNode **) ab;
 573     double      *as = &a->score[0];
 574     double      *bs = &b->score[0];
 575     double      ad = 0, bd = 0;
 576     int         i;
 577
 578     i = NUM_MATCH_VALUES;
 579     while (i-- && (ad = *as++) == (bd = *bs++))
 580         ;
 581     return ad < bd ? -1 : ad > bd ? 1 : 0;
 582 }
 583
 584 static FcBool
 585 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 586 {
 587     FcCharSet   *ncs;
 588     FcSortNode  *node;
 589
 590     while (nnode--)
 591     {
 592         node = *n++;
 593         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 594             FcResultMatch)
 595         {
 596             /*
 597              * If this font isn't a subset of the previous fonts,
 598              * add it to the list
 599              */
 600             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 601             {
 602                 if (*cs)
 603                 {
 604                     ncs = FcCharSetUnion (ncs, *cs);
 605                     if (!ncs)
 606                         return FcFalse;
 607                     FcCharSetDestroy (*cs);
 608                 }
 609                 else
 610                     ncs = FcCharSetCopy (ncs);
 611                 *cs = ncs;
 612                 FcPatternReference (node->pattern);
 613                 if (FcDebug () & FC_DBG_MATCH)
 614                 {
 615                     printf ("Add ");
 616                     FcPatternPrint (node->pattern);
 617                 }
 618                 if (!FcFontSetAdd (fs, node->pattern))
 619                 {
 620                     FcPatternDestroy (node->pattern);
 621                     return FcFalse;
 622                 }
 623             }
 624         }
 625     }
 626     return FcTrue;
 627 }
 628
 629 void
 630 FcFontSetSortDestroy (FcFontSet *fs)
 631 {
 632     FcFontSetDestroy (fs);
 633 }
 634
 635 FcFontSet *
 636 FcFontSetSort (FcConfig     *config,
 637                FcFontSet    **sets,
 638                int          nsets,
 639                FcPattern    *p,
 640                FcBool       trim,
 641                FcCharSet    **csp,
 642                FcResult     *result)
 643 {
 644     FcFontSet       *ret;
 645     FcFontSet       *s;
 646     FcSortNode      *nodes;
 647     FcSortNode      **nodeps, **nodep;
 648     int             nnodes;
 649     FcSortNode      *new;
 650     FcCharSet       *cs;
 651     int             set;
 652     int             f;
 653     int             i;
 654
 655     if (FcDebug () & FC_DBG_MATCH)
 656     {
 657         printf ("Sort ");
 658         FcPatternPrint (p);
 659     }
 660     nnodes = 0;
 661     for (set = 0; set < nsets; set++)
 662     {
 663         s = sets[set];
 664         if (!s)
 665             continue;
 666         nnodes += s->nfont;
 667     }
 668     if (!nnodes)
 669         goto bail0;
 670     /* freed below */
 671     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 672     if (!nodes)
 673         goto bail0;
 674     nodeps = (FcSortNode **) (nodes + nnodes);
 675
 676     new = nodes;
 677     nodep = nodeps;
 678     for (set = 0; set < nsets; set++)
 679     {
 680         s = sets[set];
 681         if (!s)
 682             continue;
 683         for (f = 0; f < s->nfont; f++)
 684         {
 685             if (FcDebug () & FC_DBG_MATCHV)
 686             {
 687                 printf ("Font %d ", f);
 688                 FcPatternPrint (s->fonts[f]);
 689             }
 690             new->pattern = s->fonts[f];
 691             if (!FcCompare (p, new->pattern, new->score, result))
 692                 goto bail1;
 693             if (FcDebug () & FC_DBG_MATCHV)
 694             {
 695                 printf ("Score");
 696                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 697                 {
 698                     printf (" %g", new->score[i]);
 699                 }
 700                 printf ("\n");
 701             }
 702             *nodep = new;
 703             new++;
 704             nodep++;
 705         }
 706     }
 707
 708     nnodes = new - nodes;
 709
 710     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 711            FcSortCompare);
 712
 713     ret = FcFontSetCreate ();
 714     if (!ret)
 715         goto bail1;
 716
 717     cs = 0;
 718
 719     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 720         goto bail2;
 721
 722     if (csp)
 723         *csp = cs;
 724     else
 725         FcCharSetDestroy (cs);
 726
 727     free (nodes);
 728
 729     return ret;
 730
 731 bail2:
 732     if (cs)
 733         FcCharSetDestroy (cs);
 734     FcFontSetDestroy (ret);
 735 bail1:
 736     free (nodes);
 737 bail0:
 738     return 0;
 739 }
 740
 741 FcFontSet *
 742 FcFontSort (FcConfig    *config,
 743             FcPattern   *p,
 744             FcBool      trim,
 745             FcCharSet   **csp,
 746             FcResult    *result)
 747 {
 748     FcFontSet   *sets[2];
 749     int         nsets;
 750
 751     if (!config)
 752     {
 753         config = FcConfigGetCurrent ();
 754         if (!config)
 755             return 0;
 756     }
 757     nsets = 0;
 758     if (config->fonts[FcSetSystem])
 759         sets[nsets++] = config->fonts[FcSetSystem];
 760     if (config->fonts[FcSetApplication])
 761         sets[nsets++] = config->fonts[FcSetApplication];
 762     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 763 }