src/fcmatch.c

   1 /*
   2  * $XFree86: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 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     { FC_FONTVERSION,   FcCompareInteger,       13, 13 },
 201 #define MATCH_FONTVERSION   12
 202 };
 203
 204 #define NUM_MATCH_VALUES    14
 205
 206 static FcBool
 207 FcCompareValueList (const char  *object,
 208                     FcValueList *v1orig,        /* pattern */
 209                     FcValueList *v2orig,        /* target */
 210                     FcValue     *bestValue,
 211                     double      *value,
 212                     FcResult    *result)
 213 {
 214     FcValueList    *v1, *v2;
 215     double          v, best, bestStrong, bestWeak;
 216     int             i;
 217     int             j;
 218
 219     /*
 220      * Locate the possible matching entry by examining the
 221      * first few characters in object
 222      */
 223     i = -1;
 224     switch (FcToLower (object[0])) {
 225     case 'f':
 226         switch (FcToLower (object[1])) {
 227         case 'o':
 228             switch (FcToLower (object[2])) {
 229             case 'u':
 230                 i = MATCH_FOUNDRY; break;
 231             case 'n':
 232                 i = MATCH_FONTVERSION; break;
 233             }
 234             break;
 235         case 'a':
 236             i = MATCH_FAMILY; break;
 237         }
 238         break;
 239     case 'c':
 240         i = MATCH_CHARSET; break;
 241     case 'a':
 242         i = MATCH_ANTIALIAS; break;
 243     case 'l':
 244         i = MATCH_LANG; break;
 245     case 's':
 246         switch (FcToLower (object[1])) {
 247         case 'p':
 248             i = MATCH_SPACING; break;
 249         case 't':
 250             i = MATCH_STYLE; break;
 251         case 'l':
 252             i = MATCH_SLANT; break;
 253         }
 254         break;
 255     case 'p':
 256         i = MATCH_PIXEL_SIZE; break;
 257     case 'w':
 258         i = MATCH_WEIGHT; break;
 259     case 'r':
 260         i = MATCH_RASTERIZER; break;
 261     case 'o':
 262         i = MATCH_OUTLINE; break;
 263     }
 264     if (i == -1 ||
 265         FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
 266                             (FcChar8 *) object) != 0)
 267     {
 268         if (bestValue)
 269             *bestValue = v2orig->value;
 270         return FcTrue;
 271     }
 272 #if 0
 273     for (i = 0; i < NUM_MATCHER; i++)
 274     {
 275         if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
 276                                  (FcChar8 *) object))
 277             break;
 278     }
 279     if (i == NUM_MATCHER)
 280     {
 281         if (bestValue)
 282             *bestValue = v2orig->value;
 283         return FcTrue;
 284     }
 285 #endif
 286     best = 1e99;
 287     bestStrong = 1e99;
 288     bestWeak = 1e99;
 289     j = 0;
 290     for (v1 = v1orig; v1; v1 = v1->next)
 291     {
 292         for (v2 = v2orig; v2; v2 = v2->next)
 293         {
 294             v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
 295                                             v1->value,
 296                                             v2->value);
 297             if (v < 0)
 298             {
 299                 *result = FcResultTypeMismatch;
 300                 return FcFalse;
 301             }
 302             if (FcDebug () & FC_DBG_MATCHV)
 303                 printf (" v %g j %d ", v, j);
 304             v = v * 100 + j;
 305             if (v < best)
 306             {
 307                 if (bestValue)
 308                     *bestValue = v2->value;
 309                 best = v;
 310             }
 311             if (v1->binding == FcValueBindingStrong)
 312             {
 313                 if (v < bestStrong)
 314                     bestStrong = v;
 315             }
 316             else
 317             {
 318                 if (v < bestWeak)
 319                     bestWeak = v;
 320             }
 321         }
 322         j++;
 323     }
 324     if (FcDebug () & FC_DBG_MATCHV)
 325     {
 326         printf (" %s: %g ", object, best);
 327         FcValueListPrint (v1orig);
 328         printf (", ");
 329         FcValueListPrint (v2orig);
 330         printf ("\n");
 331     }
 332     if (value)
 333     {
 334         int weak    = _FcMatchers[i].weak;
 335         int strong  = _FcMatchers[i].strong;
 336         if (weak == strong)
 337             value[strong] += best;
 338         else
 339         {
 340             value[weak] += bestWeak;
 341             value[strong] += bestStrong;
 342         }
 343     }
 344     return FcTrue;
 345 }
 346
 347 /*
 348  * Return a value indicating the distance between the two lists of
 349  * values
 350  */
 351
 352 static FcBool
 353 FcCompare (FcPattern    *pat,
 354            FcPattern    *fnt,
 355            double       *value,
 356            FcResult     *result)
 357 {
 358     int             i, i1, i2;
 359
 360     for (i = 0; i < NUM_MATCH_VALUES; i++)
 361         value[i] = 0.0;
 362
 363     i1 = 0;
 364     i2 = 0;
 365     while (i1 < pat->num && i2 < fnt->num)
 366     {
 367         i = strcmp (pat->elts[i1].object, fnt->elts[i2].object);
 368         if (i > 0)
 369             i2++;
 370         else if (i < 0)
 371             i1++;
 372         else
 373         {
 374             if (!FcCompareValueList (pat->elts[i1].object,
 375                                      pat->elts[i1].values,
 376                                      fnt->elts[i2].values,
 377                                      0,
 378                                      value,
 379                                      result))
 380                 return FcFalse;
 381             i1++;
 382             i2++;
 383         }
 384     }
 385     return FcTrue;
 386 #if 0
 387     for (i1 = 0; i1 < pat->num; i1++)
 388     {
 389         for (i2 = 0; i2 < fnt->num; i2++)
 390         {
 391             if (!strcmp (pat->elts[i1].object, fnt->elts[i2].object))
 392             {
 393                 break;
 394             }
 395         }
 396     }
 397     return FcTrue;
 398 #endif
 399 }
 400
 401 FcPattern *
 402 FcFontRenderPrepare (FcConfig       *config,
 403                      FcPattern      *pat,
 404                      FcPattern      *font)
 405 {
 406     FcPattern       *new;
 407     int             i;
 408     FcPatternElt    *fe, *pe;
 409     FcValue         v;
 410     FcResult        result;
 411
 412     new = FcPatternCreate ();
 413     if (!new)
 414         return 0;
 415     for (i = 0; i < font->num; i++)
 416     {
 417         fe = &font->elts[i];
 418         pe = FcPatternFindElt (pat, fe->object);
 419         if (pe)
 420         {
 421             if (!FcCompareValueList (pe->object, pe->values,
 422                                      fe->values, &v, 0, &result))
 423             {
 424                 FcPatternDestroy (new);
 425                 return 0;
 426             }
 427         }
 428         else
 429             v = fe->values->value;
 430         FcPatternAdd (new, fe->object, v, FcFalse);
 431     }
 432     for (i = 0; i < pat->num; i++)
 433     {
 434         pe = &pat->elts[i];
 435         fe = FcPatternFindElt (font, pe->object);
 436         if (!fe)
 437             FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
 438     }
 439     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
 440     return new;
 441 }
 442
 443 FcPattern *
 444 FcFontSetMatch (FcConfig    *config,
 445                 FcFontSet   **sets,
 446                 int         nsets,
 447                 FcPattern   *p,
 448                 FcResult    *result)
 449 {
 450     double          score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
 451     int             f;
 452     FcFontSet       *s;
 453     FcPattern       *best;
 454     int             i;
 455     int             set;
 456
 457     for (i = 0; i < NUM_MATCH_VALUES; i++)
 458         bestscore[i] = 0;
 459     best = 0;
 460     if (FcDebug () & FC_DBG_MATCH)
 461     {
 462         printf ("Match ");
 463         FcPatternPrint (p);
 464     }
 465     if (!config)
 466     {
 467         config = FcConfigGetCurrent ();
 468         if (!config)
 469             return 0;
 470     }
 471     for (set = 0; set < nsets; set++)
 472     {
 473         s = sets[set];
 474         if (!s)
 475             continue;
 476         for (f = 0; f < s->nfont; f++)
 477         {
 478             if (FcDebug () & FC_DBG_MATCHV)
 479             {
 480                 printf ("Font %d ", f);
 481                 FcPatternPrint (s->fonts[f]);
 482             }
 483             if (!FcCompare (p, s->fonts[f], score, result))
 484                 return 0;
 485             if (FcDebug () & FC_DBG_MATCHV)
 486             {
 487                 printf ("Score");
 488                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 489                 {
 490                     printf (" %g", score[i]);
 491                 }
 492                 printf ("\n");
 493             }
 494             for (i = 0; i < NUM_MATCH_VALUES; i++)
 495             {
 496                 if (best && bestscore[i] < score[i])
 497                     break;
 498                 if (!best || score[i] < bestscore[i])
 499                 {
 500                     for (i = 0; i < NUM_MATCH_VALUES; i++)
 501                         bestscore[i] = score[i];
 502                     best = s->fonts[f];
 503                     break;
 504                 }
 505             }
 506         }
 507     }
 508     if (FcDebug () & FC_DBG_MATCH)
 509     {
 510         printf ("Best score");
 511         for (i = 0; i < NUM_MATCH_VALUES; i++)
 512             printf (" %g", bestscore[i]);
 513         FcPatternPrint (best);
 514     }
 515     if (!best)
 516     {
 517         *result = FcResultNoMatch;
 518         return 0;
 519     }
 520     return FcFontRenderPrepare (config, p, best);
 521 }
 522
 523 FcPattern *
 524 FcFontMatch (FcConfig   *config,
 525              FcPattern  *p,
 526              FcResult   *result)
 527 {
 528     FcFontSet   *sets[2];
 529     int         nsets;
 530
 531     if (!config)
 532     {
 533         config = FcConfigGetCurrent ();
 534         if (!config)
 535             return 0;
 536     }
 537     nsets = 0;
 538     if (config->fonts[FcSetSystem])
 539         sets[nsets++] = config->fonts[FcSetSystem];
 540     if (config->fonts[FcSetApplication])
 541         sets[nsets++] = config->fonts[FcSetApplication];
 542     return FcFontSetMatch (config, sets, nsets, p, result);
 543 }
 544
 545 typedef struct _FcSortNode {
 546     FcPattern   *pattern;
 547     double      score[NUM_MATCH_VALUES];
 548 } FcSortNode;
 549
 550 static int
 551 FcSortCompare (const void *aa, const void *ab)
 552 {
 553     FcSortNode  *a = *(FcSortNode **) aa;
 554     FcSortNode  *b = *(FcSortNode **) ab;
 555     double      *as = &a->score[0];
 556     double      *bs = &b->score[0];
 557     double      ad = 0, bd = 0;
 558     int         i;
 559
 560     i = NUM_MATCH_VALUES;
 561     while (i-- && (ad = *as++) == (bd = *bs++))
 562         ;
 563     return ad < bd ? -1 : ad > bd ? 1 : 0;
 564 }
 565
 566 static FcBool
 567 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 568 {
 569     FcCharSet   *ncs;
 570     FcSortNode  *node;
 571
 572     while (nnode--)
 573     {
 574         node = *n++;
 575         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 576             FcResultMatch)
 577         {
 578             /*
 579              * If this font isn't a subset of the previous fonts,
 580              * add it to the list
 581              */
 582             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 583             {
 584                 if (*cs)
 585                 {
 586                     ncs = FcCharSetUnion (ncs, *cs);
 587                     if (!ncs)
 588                         return FcFalse;
 589                     FcCharSetDestroy (*cs);
 590                 }
 591                 else
 592                     ncs = FcCharSetCopy (ncs);
 593                 *cs = ncs;
 594                 FcPatternReference (node->pattern);
 595                 if (FcDebug () & FC_DBG_MATCH)
 596                 {
 597                     printf ("Add ");
 598                     FcPatternPrint (node->pattern);
 599                 }
 600                 if (!FcFontSetAdd (fs, node->pattern))
 601                 {
 602                     FcPatternDestroy (node->pattern);
 603                     return FcFalse;
 604                 }
 605             }
 606         }
 607     }
 608     return FcTrue;
 609 }
 610
 611 void
 612 FcFontSetSortDestroy (FcFontSet *fs)
 613 {
 614     FcFontSetDestroy (fs);
 615 }
 616
 617 FcFontSet *
 618 FcFontSetSort (FcConfig     *config,
 619                FcFontSet    **sets,
 620                int          nsets,
 621                FcPattern    *p,
 622                FcBool       trim,
 623                FcCharSet    **csp,
 624                FcResult     *result)
 625 {
 626     FcFontSet       *ret;
 627     FcFontSet       *s;
 628     FcSortNode      *nodes;
 629     FcSortNode      **nodeps, **nodep;
 630     int             nnodes;
 631     FcSortNode      *new;
 632     FcCharSet       *cs;
 633     int             set;
 634     int             f;
 635     int             i;
 636
 637     if (FcDebug () & FC_DBG_MATCH)
 638     {
 639         printf ("Sort ");
 640         FcPatternPrint (p);
 641     }
 642     nnodes = 0;
 643     for (set = 0; set < nsets; set++)
 644     {
 645         s = sets[set];
 646         if (!s)
 647             continue;
 648         nnodes += s->nfont;
 649     }
 650     if (!nnodes)
 651         goto bail0;
 652     /* freed below */
 653     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 654     if (!nodes)
 655         goto bail0;
 656     nodeps = (FcSortNode **) (nodes + nnodes);
 657
 658     new = nodes;
 659     nodep = nodeps;
 660     for (set = 0; set < nsets; set++)
 661     {
 662         s = sets[set];
 663         if (!s)
 664             continue;
 665         for (f = 0; f < s->nfont; f++)
 666         {
 667             if (FcDebug () & FC_DBG_MATCHV)
 668             {
 669                 printf ("Font %d ", f);
 670                 FcPatternPrint (s->fonts[f]);
 671             }
 672             new->pattern = s->fonts[f];
 673             if (!FcCompare (p, new->pattern, new->score, result))
 674                 goto bail1;
 675             if (FcDebug () & FC_DBG_MATCHV)
 676             {
 677                 printf ("Score");
 678                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 679                 {
 680                     printf (" %g", new->score[i]);
 681                 }
 682                 printf ("\n");
 683             }
 684             *nodep = new;
 685             new++;
 686             nodep++;
 687         }
 688     }
 689
 690     nnodes = new - nodes;
 691
 692     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 693            FcSortCompare);
 694
 695     ret = FcFontSetCreate ();
 696     if (!ret)
 697         goto bail1;
 698
 699     cs = 0;
 700
 701     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 702         goto bail2;
 703
 704     if (csp)
 705         *csp = cs;
 706     else
 707         FcCharSetDestroy (cs);
 708
 709     free (nodes);
 710
 711     return ret;
 712
 713 bail2:
 714     if (cs)
 715         FcCharSetDestroy (cs);
 716     FcFontSetDestroy (ret);
 717 bail1:
 718     free (nodes);
 719 bail0:
 720     return 0;
 721 }
 722
 723 FcFontSet *
 724 FcFontSort (FcConfig    *config,
 725             FcPattern   *p,
 726             FcBool      trim,
 727             FcCharSet   **csp,
 728             FcResult    *result)
 729 {
 730     FcFontSet   *sets[2];
 731     int         nsets;
 732
 733     if (!config)
 734     {
 735         config = FcConfigGetCurrent ();
 736         if (!config)
 737             return 0;
 738     }
 739     nsets = 0;
 740     if (config->fonts[FcSetSystem])
 741         sets[nsets++] = config->fonts[FcSetSystem];
 742     if (config->fonts[FcSetApplication])
 743         sets[nsets++] = config->fonts[FcSetApplication];
 744     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 745 }