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             return 0;
 497     }
 498     for (set = 0; set < nsets; set++)
 499     {
 500         s = sets[set];
 501         if (!s)
 502             continue;
 503         for (f = 0; f < s->nfont; f++)
 504         {
 505             if (FcDebug () & FC_DBG_MATCHV)
 506             {
 507                 printf ("Font %d ", f);
 508                 FcPatternPrint (s->fonts[f]);
 509             }
 510             if (!FcCompare (p, s->fonts[f], score, result))
 511                 return 0;
 512             if (FcDebug () & FC_DBG_MATCHV)
 513             {
 514                 printf ("Score");
 515                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 516                 {
 517                     printf (" %g", score[i]);
 518                 }
 519                 printf ("\n");
 520             }
 521             for (i = 0; i < NUM_MATCH_VALUES; i++)
 522             {
 523                 if (best && bestscore[i] < score[i])
 524                     break;
 525                 if (!best || score[i] < bestscore[i])
 526                 {
 527                     for (i = 0; i < NUM_MATCH_VALUES; i++)
 528                         bestscore[i] = score[i];
 529                     best = s->fonts[f];
 530                     break;
 531                 }
 532             }
 533         }
 534     }
 535     if (FcDebug () & FC_DBG_MATCH)
 536     {
 537         printf ("Best score");
 538         for (i = 0; i < NUM_MATCH_VALUES; i++)
 539             printf (" %g", bestscore[i]);
 540         FcPatternPrint (best);
 541     }
 542     if (!best)
 543     {
 544         *result = FcResultNoMatch;
 545         return 0;
 546     }
 547     return FcFontRenderPrepare (config, p, best);
 548 }
 549
 550 FcPattern *
 551 FcFontMatch (FcConfig   *config,
 552              FcPattern  *p,
 553              FcResult   *result)
 554 {
 555     FcFontSet   *sets[2];
 556     int         nsets;
 557
 558     if (!config)
 559     {
 560         config = FcConfigGetCurrent ();
 561         if (!config)
 562             return 0;
 563     }
 564     nsets = 0;
 565     if (config->fonts[FcSetSystem])
 566         sets[nsets++] = config->fonts[FcSetSystem];
 567     if (config->fonts[FcSetApplication])
 568         sets[nsets++] = config->fonts[FcSetApplication];
 569     return FcFontSetMatch (config, sets, nsets, p, result);
 570 }
 571
 572 typedef struct _FcSortNode {
 573     FcPattern   *pattern;
 574     double      score[NUM_MATCH_VALUES];
 575 } FcSortNode;
 576
 577 static int
 578 FcSortCompare (const void *aa, const void *ab)
 579 {
 580     FcSortNode  *a = *(FcSortNode **) aa;
 581     FcSortNode  *b = *(FcSortNode **) ab;
 582     double      *as = &a->score[0];
 583     double      *bs = &b->score[0];
 584     double      ad = 0, bd = 0;
 585     int         i;
 586
 587     i = NUM_MATCH_VALUES;
 588     while (i-- && (ad = *as++) == (bd = *bs++))
 589         ;
 590     return ad < bd ? -1 : ad > bd ? 1 : 0;
 591 }
 592
 593 static FcBool
 594 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 595 {
 596     FcCharSet   *ncs;
 597     FcSortNode  *node;
 598
 599     while (nnode--)
 600     {
 601         node = *n++;
 602         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 603             FcResultMatch)
 604         {
 605             /*
 606              * If this font isn't a subset of the previous fonts,
 607              * add it to the list
 608              */
 609             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 610             {
 611                 if (*cs)
 612                 {
 613                     ncs = FcCharSetUnion (ncs, *cs);
 614                     if (!ncs)
 615                         return FcFalse;
 616                     FcCharSetDestroy (*cs);
 617                 }
 618                 else
 619                     ncs = FcCharSetCopy (ncs);
 620                 *cs = ncs;
 621                 FcPatternReference (node->pattern);
 622                 if (FcDebug () & FC_DBG_MATCH)
 623                 {
 624                     printf ("Add ");
 625                     FcPatternPrint (node->pattern);
 626                 }
 627                 if (!FcFontSetAdd (fs, node->pattern))
 628                 {
 629                     FcPatternDestroy (node->pattern);
 630                     return FcFalse;
 631                 }
 632             }
 633         }
 634     }
 635     return FcTrue;
 636 }
 637
 638 void
 639 FcFontSetSortDestroy (FcFontSet *fs)
 640 {
 641     FcFontSetDestroy (fs);
 642 }
 643
 644 FcFontSet *
 645 FcFontSetSort (FcConfig     *config,
 646                FcFontSet    **sets,
 647                int          nsets,
 648                FcPattern    *p,
 649                FcBool       trim,
 650                FcCharSet    **csp,
 651                FcResult     *result)
 652 {
 653     FcFontSet       *ret;
 654     FcFontSet       *s;
 655     FcSortNode      *nodes;
 656     FcSortNode      **nodeps, **nodep;
 657     int             nnodes;
 658     FcSortNode      *new;
 659     FcCharSet       *cs;
 660     int             set;
 661     int             f;
 662     int             i;
 663
 664     if (FcDebug () & FC_DBG_MATCH)
 665     {
 666         printf ("Sort ");
 667         FcPatternPrint (p);
 668     }
 669     nnodes = 0;
 670     for (set = 0; set < nsets; set++)
 671     {
 672         s = sets[set];
 673         if (!s)
 674             continue;
 675         nnodes += s->nfont;
 676     }
 677     if (!nnodes)
 678         goto bail0;
 679     /* freed below */
 680     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 681     if (!nodes)
 682         goto bail0;
 683     nodeps = (FcSortNode **) (nodes + nnodes);
 684
 685     new = nodes;
 686     nodep = nodeps;
 687     for (set = 0; set < nsets; set++)
 688     {
 689         s = sets[set];
 690         if (!s)
 691             continue;
 692         for (f = 0; f < s->nfont; f++)
 693         {
 694             if (FcDebug () & FC_DBG_MATCHV)
 695             {
 696                 printf ("Font %d ", f);
 697                 FcPatternPrint (s->fonts[f]);
 698             }
 699             new->pattern = s->fonts[f];
 700             if (!FcCompare (p, new->pattern, new->score, result))
 701                 goto bail1;
 702             if (FcDebug () & FC_DBG_MATCHV)
 703             {
 704                 printf ("Score");
 705                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 706                 {
 707                     printf (" %g", new->score[i]);
 708                 }
 709                 printf ("\n");
 710             }
 711             *nodep = new;
 712             new++;
 713             nodep++;
 714         }
 715     }
 716
 717     nnodes = new - nodes;
 718
 719     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 720            FcSortCompare);
 721
 722     ret = FcFontSetCreate ();
 723     if (!ret)
 724         goto bail1;
 725
 726     cs = 0;
 727
 728     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 729         goto bail2;
 730
 731     if (csp)
 732         *csp = cs;
 733     else
 734         FcCharSetDestroy (cs);
 735
 736     free (nodes);
 737
 738     return ret;
 739
 740 bail2:
 741     if (cs)
 742         FcCharSetDestroy (cs);
 743     FcFontSetDestroy (ret);
 744 bail1:
 745     free (nodes);
 746 bail0:
 747     return 0;
 748 }
 749
 750 FcFontSet *
 751 FcFontSort (FcConfig    *config,
 752             FcPattern   *p,
 753             FcBool      trim,
 754             FcCharSet   **csp,
 755             FcResult    *result)
 756 {
 757     FcFontSet   *sets[2];
 758     int         nsets;
 759
 760     if (!config)
 761     {
 762         config = FcConfigGetCurrent ();
 763         if (!config)
 764             return 0;
 765     }
 766     nsets = 0;
 767     if (config->fonts[FcSetSystem])
 768         sets[nsets++] = config->fonts[FcSetSystem];
 769     if (config->fonts[FcSetApplication])
 770         sets[nsets++] = config->fonts[FcSetApplication];
 771     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 772 }