src/fcmatch.c

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