src/fcmatch.c

   1 /*
   2  * $XFree86: xc/lib/fontconfig/src/fcmatch.c,v 1.13 2002/06/19 20:08:22 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             int     j;
 333             double  score[NUM_MATCHER];
 334
 335             for (j = 0; j < NUM_MATCHER; j++)
 336                 score[j] = 0;
 337             if (!FcCompareValueList (pe->object, pe->values,
 338                                      fe->values, &v, score, &result))
 339             {
 340                 FcPatternDestroy (new);
 341                 return 0;
 342             }
 343             for (j = 0; j < NUM_MATCHER; j++)
 344                 if (score[j] >= 100.0)
 345                 {
 346                     FcValueList *pv;
 347
 348                     for (pv = pe->values; pv; pv = pv->next)
 349                         FcPatternAdd (new, fe->object, pv->value, FcTrue);
 350                     break;
 351                 }
 352         }
 353         else
 354             v = fe->values->value;
 355         FcPatternAdd (new, fe->object, v, FcFalse);
 356     }
 357     for (i = 0; i < pat->num; i++)
 358     {
 359         pe = &pat->elts[i];
 360         fe = FcPatternFindElt (font, pe->object);
 361         if (!fe)
 362             FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
 363     }
 364     FcConfigSubstitute (config, new, FcMatchFont);
 365     return new;
 366 }
 367
 368 FcPattern *
 369 FcFontSetMatch (FcConfig    *config,
 370                 FcFontSet   **sets,
 371                 int         nsets,
 372                 FcPattern   *p,
 373                 FcResult    *result)
 374 {
 375     double          score[NUM_MATCHER], bestscore[NUM_MATCHER];
 376     int             f;
 377     FcFontSet       *s;
 378     FcPattern       *best;
 379     int             i;
 380     int             set;
 381
 382     for (i = 0; i < NUM_MATCHER; i++)
 383         bestscore[i] = 0;
 384     best = 0;
 385     if (FcDebug () & FC_DBG_MATCH)
 386     {
 387         printf ("Match ");
 388         FcPatternPrint (p);
 389     }
 390     if (!config)
 391     {
 392         config = FcConfigGetCurrent ();
 393         if (!config)
 394             return 0;
 395     }
 396     for (set = 0; set < nsets; set++)
 397     {
 398         s = sets[set];
 399         if (!s)
 400             continue;
 401         for (f = 0; f < s->nfont; f++)
 402         {
 403             if (FcDebug () & FC_DBG_MATCHV)
 404             {
 405                 printf ("Font %d ", f);
 406                 FcPatternPrint (s->fonts[f]);
 407             }
 408             if (!FcCompare (p, s->fonts[f], score, result))
 409                 return 0;
 410             if (FcDebug () & FC_DBG_MATCHV)
 411             {
 412                 printf ("Score");
 413                 for (i = 0; i < NUM_MATCHER; i++)
 414                 {
 415                     printf (" %g", score[i]);
 416                 }
 417                 printf ("\n");
 418             }
 419             for (i = 0; i < NUM_MATCHER; i++)
 420             {
 421                 if (best && bestscore[i] < score[i])
 422                     break;
 423                 if (!best || score[i] < bestscore[i])
 424                 {
 425                     for (i = 0; i < NUM_MATCHER; i++)
 426                         bestscore[i] = score[i];
 427                     best = s->fonts[f];
 428                     break;
 429                 }
 430             }
 431         }
 432     }
 433     if (FcDebug () & FC_DBG_MATCH)
 434     {
 435         printf ("Best score");
 436         for (i = 0; i < NUM_MATCHER; i++)
 437             printf (" %g", bestscore[i]);
 438         FcPatternPrint (best);
 439     }
 440     if (!best)
 441     {
 442         *result = FcResultNoMatch;
 443         return 0;
 444     }
 445     return FcFontRenderPrepare (config, p, best);
 446 }
 447
 448 FcPattern *
 449 FcFontMatch (FcConfig   *config,
 450              FcPattern  *p,
 451              FcResult   *result)
 452 {
 453     FcFontSet   *sets[2];
 454     int         nsets;
 455
 456     if (!config)
 457     {
 458         config = FcConfigGetCurrent ();
 459         if (!config)
 460             return 0;
 461     }
 462     nsets = 0;
 463     if (config->fonts[FcSetSystem])
 464         sets[nsets++] = config->fonts[FcSetSystem];
 465     if (config->fonts[FcSetApplication])
 466         sets[nsets++] = config->fonts[FcSetApplication];
 467     return FcFontSetMatch (config, sets, nsets, p, result);
 468 }
 469
 470 typedef struct _FcSortNode {
 471     FcPattern   *pattern;
 472     double      score[NUM_MATCHER];
 473 } FcSortNode;
 474
 475 static int
 476 FcSortCompare (const void *aa, const void *ab)
 477 {
 478     FcSortNode  *a = *(FcSortNode **) aa;
 479     FcSortNode  *b = *(FcSortNode **) ab;
 480     double      *as = &a->score[0];
 481     double      *bs = &b->score[0];
 482     double      ad = 0, bd = 0;
 483     int         i;
 484
 485     i = NUM_MATCHER;
 486     while (i-- && (ad = *as++) == (bd = *bs++))
 487         ;
 488     return ad < bd ? -1 : ad > bd ? 1 : 0;
 489 }
 490
 491 static FcBool
 492 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 493 {
 494     FcCharSet   *ncs;
 495     FcSortNode  *node;
 496
 497     while (nnode--)
 498     {
 499         node = *n++;
 500         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 501             FcResultMatch)
 502         {
 503             /*
 504              * If this font isn't a subset of the previous fonts,
 505              * add it to the list
 506              */
 507             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 508             {
 509                 if (*cs)
 510                 {
 511                     ncs = FcCharSetUnion (ncs, *cs);
 512                     if (!ncs)
 513                         return FcFalse;
 514                     FcCharSetDestroy (*cs);
 515                 }
 516                 else
 517                     ncs = FcCharSetCopy (ncs);
 518                 *cs = ncs;
 519                 FcPatternReference (node->pattern);
 520                 if (!FcFontSetAdd (fs, node->pattern))
 521                 {
 522                     FcPatternDestroy (node->pattern);
 523                     return FcFalse;
 524                 }
 525             }
 526         }
 527     }
 528     return FcTrue;
 529 }
 530
 531 void
 532 FcFontSetSortDestroy (FcFontSet *fs)
 533 {
 534     FcFontSetDestroy (fs);
 535 }
 536
 537 FcFontSet *
 538 FcFontSetSort (FcConfig     *config,
 539                FcFontSet    **sets,
 540                int          nsets,
 541                FcPattern    *p,
 542                FcBool       trim,
 543                FcCharSet    **csp,
 544                FcResult     *result)
 545 {
 546     FcFontSet       *ret;
 547     FcFontSet       *s;
 548     FcSortNode      *nodes;
 549     FcSortNode      **nodeps, **nodep;
 550     int             nnodes;
 551     FcSortNode      *new;
 552     FcCharSet       *cs;
 553     int             set;
 554     int             f;
 555     int             i;
 556
 557     nnodes = 0;
 558     for (set = 0; set < nsets; set++)
 559     {
 560         s = sets[set];
 561         if (!s)
 562             continue;
 563         nnodes += s->nfont;
 564     }
 565     if (!nnodes)
 566         goto bail0;
 567     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 568     if (!nodes)
 569         goto bail0;
 570     nodeps = (FcSortNode **) (nodes + nnodes);
 571
 572     new = nodes;
 573     nodep = nodeps;
 574     for (set = 0; set < nsets; set++)
 575     {
 576         s = sets[set];
 577         if (!s)
 578             continue;
 579         for (f = 0; f < s->nfont; f++)
 580         {
 581             if (FcDebug () & FC_DBG_MATCHV)
 582             {
 583                 printf ("Font %d ", f);
 584                 FcPatternPrint (s->fonts[f]);
 585             }
 586             new->pattern = s->fonts[f];
 587             if (!FcCompare (p, new->pattern, new->score, result))
 588                 goto bail1;
 589             if (FcDebug () & FC_DBG_MATCHV)
 590             {
 591                 printf ("Score");
 592                 for (i = 0; i < NUM_MATCHER; i++)
 593                 {
 594                     printf (" %g", new->score[i]);
 595                 }
 596                 printf ("\n");
 597             }
 598             *nodep = new;
 599             new++;
 600             nodep++;
 601         }
 602     }
 603
 604     nnodes = new - nodes;
 605
 606     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 607            FcSortCompare);
 608
 609     ret = FcFontSetCreate ();
 610     if (!ret)
 611         goto bail1;
 612
 613     cs = 0;
 614
 615     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 616         goto bail2;
 617
 618     if (csp)
 619         *csp = cs;
 620     else
 621         FcCharSetDestroy (cs);
 622
 623     free (nodes);
 624
 625     return ret;
 626
 627 bail2:
 628     if (cs)
 629         FcCharSetDestroy (cs);
 630     FcFontSetDestroy (ret);
 631 bail1:
 632     free (nodes);
 633 bail0:
 634     return 0;
 635 }
 636
 637 FcFontSet *
 638 FcFontSort (FcConfig    *config,
 639             FcPattern   *p,
 640             FcBool      trim,
 641             FcCharSet   **csp,
 642             FcResult    *result)
 643 {
 644     FcFontSet   *sets[2];
 645     int         nsets;
 646
 647     if (!config)
 648     {
 649         config = FcConfigGetCurrent ();
 650         if (!config)
 651             return 0;
 652     }
 653     nsets = 0;
 654     if (config->fonts[FcSetSystem])
 655         sets[nsets++] = config->fonts[FcSetSystem];
 656     if (config->fonts[FcSetApplication])
 657         sets[nsets++] = config->fonts[FcSetApplication];
 658     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 659 }