src/fcmatch.c

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