src/fcmatch.c

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