src/fcmatch.c

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