src/fcmatch.c

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