src/fcmatch.c

   1 /*
   2  * $XFree86: xc/lib/fontconfig/src/fcmatch.c,v 1.16 2002/07/06 23:47:44 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     FcPatternAddPattern (new, FC_PATTERN, pat);
 406     FcConfigSubstitute (config, new, FcMatchFont);
 407     return new;
 408 }
 409
 410 FcPattern *
 411 FcFontSetMatch (FcConfig    *config,
 412                 FcFontSet   **sets,
 413                 int         nsets,
 414                 FcPattern   *p,
 415                 FcResult    *result)
 416 {
 417     double          score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
 418     int             f;
 419     FcFontSet       *s;
 420     FcPattern       *best;
 421     int             i;
 422     int             set;
 423
 424     for (i = 0; i < NUM_MATCH_VALUES; i++)
 425         bestscore[i] = 0;
 426     best = 0;
 427     if (FcDebug () & FC_DBG_MATCH)
 428     {
 429         printf ("Match ");
 430         FcPatternPrint (p);
 431     }
 432     if (!config)
 433     {
 434         config = FcConfigGetCurrent ();
 435         if (!config)
 436             return 0;
 437     }
 438     for (set = 0; set < nsets; set++)
 439     {
 440         s = sets[set];
 441         if (!s)
 442             continue;
 443         for (f = 0; f < s->nfont; f++)
 444         {
 445             if (FcDebug () & FC_DBG_MATCHV)
 446             {
 447                 printf ("Font %d ", f);
 448                 FcPatternPrint (s->fonts[f]);
 449             }
 450             if (!FcCompare (p, s->fonts[f], score, result))
 451                 return 0;
 452             if (FcDebug () & FC_DBG_MATCHV)
 453             {
 454                 printf ("Score");
 455                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 456                 {
 457                     printf (" %g", score[i]);
 458                 }
 459                 printf ("\n");
 460             }
 461             for (i = 0; i < NUM_MATCH_VALUES; i++)
 462             {
 463                 if (best && bestscore[i] < score[i])
 464                     break;
 465                 if (!best || score[i] < bestscore[i])
 466                 {
 467                     for (i = 0; i < NUM_MATCH_VALUES; i++)
 468                         bestscore[i] = score[i];
 469                     best = s->fonts[f];
 470                     break;
 471                 }
 472             }
 473         }
 474     }
 475     if (FcDebug () & FC_DBG_MATCH)
 476     {
 477         printf ("Best score");
 478         for (i = 0; i < NUM_MATCH_VALUES; i++)
 479             printf (" %g", bestscore[i]);
 480         FcPatternPrint (best);
 481     }
 482     if (!best)
 483     {
 484         *result = FcResultNoMatch;
 485         return 0;
 486     }
 487     return FcFontRenderPrepare (config, p, best);
 488 }
 489
 490 FcPattern *
 491 FcFontMatch (FcConfig   *config,
 492              FcPattern  *p,
 493              FcResult   *result)
 494 {
 495     FcFontSet   *sets[2];
 496     int         nsets;
 497
 498     if (!config)
 499     {
 500         config = FcConfigGetCurrent ();
 501         if (!config)
 502             return 0;
 503     }
 504     nsets = 0;
 505     if (config->fonts[FcSetSystem])
 506         sets[nsets++] = config->fonts[FcSetSystem];
 507     if (config->fonts[FcSetApplication])
 508         sets[nsets++] = config->fonts[FcSetApplication];
 509     return FcFontSetMatch (config, sets, nsets, p, result);
 510 }
 511
 512 typedef struct _FcSortNode {
 513     FcPattern   *pattern;
 514     double      score[NUM_MATCH_VALUES];
 515 } FcSortNode;
 516
 517 static int
 518 FcSortCompare (const void *aa, const void *ab)
 519 {
 520     FcSortNode  *a = *(FcSortNode **) aa;
 521     FcSortNode  *b = *(FcSortNode **) ab;
 522     double      *as = &a->score[0];
 523     double      *bs = &b->score[0];
 524     double      ad = 0, bd = 0;
 525     int         i;
 526
 527     i = NUM_MATCH_VALUES;
 528     while (i-- && (ad = *as++) == (bd = *bs++))
 529         ;
 530     return ad < bd ? -1 : ad > bd ? 1 : 0;
 531 }
 532
 533 static FcBool
 534 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 535 {
 536     FcCharSet   *ncs;
 537     FcSortNode  *node;
 538
 539     while (nnode--)
 540     {
 541         node = *n++;
 542         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 543             FcResultMatch)
 544         {
 545             /*
 546              * If this font isn't a subset of the previous fonts,
 547              * add it to the list
 548              */
 549             if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
 550             {
 551                 if (*cs)
 552                 {
 553                     ncs = FcCharSetUnion (ncs, *cs);
 554                     if (!ncs)
 555                         return FcFalse;
 556                     FcCharSetDestroy (*cs);
 557                 }
 558                 else
 559                     ncs = FcCharSetCopy (ncs);
 560                 *cs = ncs;
 561                 FcPatternReference (node->pattern);
 562                 if (FcDebug () & FC_DBG_MATCH)
 563                 {
 564                     printf ("Add ");
 565                     FcPatternPrint (node->pattern);
 566                 }
 567                 if (!FcFontSetAdd (fs, node->pattern))
 568                 {
 569                     FcPatternDestroy (node->pattern);
 570                     return FcFalse;
 571                 }
 572             }
 573         }
 574     }
 575     return FcTrue;
 576 }
 577
 578 void
 579 FcFontSetSortDestroy (FcFontSet *fs)
 580 {
 581     FcFontSetDestroy (fs);
 582 }
 583
 584 FcFontSet *
 585 FcFontSetSort (FcConfig     *config,
 586                FcFontSet    **sets,
 587                int          nsets,
 588                FcPattern    *p,
 589                FcBool       trim,
 590                FcCharSet    **csp,
 591                FcResult     *result)
 592 {
 593     FcFontSet       *ret;
 594     FcFontSet       *s;
 595     FcSortNode      *nodes;
 596     FcSortNode      **nodeps, **nodep;
 597     int             nnodes;
 598     FcSortNode      *new;
 599     FcCharSet       *cs;
 600     int             set;
 601     int             f;
 602     int             i;
 603
 604     if (FcDebug () & FC_DBG_MATCH)
 605     {
 606         printf ("Sort ");
 607         FcPatternPrint (p);
 608     }
 609     nnodes = 0;
 610     for (set = 0; set < nsets; set++)
 611     {
 612         s = sets[set];
 613         if (!s)
 614             continue;
 615         nnodes += s->nfont;
 616     }
 617     if (!nnodes)
 618         goto bail0;
 619     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 620     if (!nodes)
 621         goto bail0;
 622     nodeps = (FcSortNode **) (nodes + nnodes);
 623
 624     new = nodes;
 625     nodep = nodeps;
 626     for (set = 0; set < nsets; set++)
 627     {
 628         s = sets[set];
 629         if (!s)
 630             continue;
 631         for (f = 0; f < s->nfont; f++)
 632         {
 633             if (FcDebug () & FC_DBG_MATCHV)
 634             {
 635                 printf ("Font %d ", f);
 636                 FcPatternPrint (s->fonts[f]);
 637             }
 638             new->pattern = s->fonts[f];
 639             if (!FcCompare (p, new->pattern, new->score, result))
 640                 goto bail1;
 641             if (FcDebug () & FC_DBG_MATCHV)
 642             {
 643                 printf ("Score");
 644                 for (i = 0; i < NUM_MATCH_VALUES; i++)
 645                 {
 646                     printf (" %g", new->score[i]);
 647                 }
 648                 printf ("\n");
 649             }
 650             *nodep = new;
 651             new++;
 652             nodep++;
 653         }
 654     }
 655
 656     nnodes = new - nodes;
 657
 658     qsort (nodeps, nnodes, sizeof (FcSortNode *),
 659            FcSortCompare);
 660
 661     ret = FcFontSetCreate ();
 662     if (!ret)
 663         goto bail1;
 664
 665     cs = 0;
 666
 667     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 668         goto bail2;
 669
 670     if (csp)
 671         *csp = cs;
 672     else
 673         FcCharSetDestroy (cs);
 674
 675     free (nodes);
 676
 677     return ret;
 678
 679 bail2:
 680     if (cs)
 681         FcCharSetDestroy (cs);
 682     FcFontSetDestroy (ret);
 683 bail1:
 684     free (nodes);
 685 bail0:
 686     return 0;
 687 }
 688
 689 FcFontSet *
 690 FcFontSort (FcConfig    *config,
 691             FcPattern   *p,
 692             FcBool      trim,
 693             FcCharSet   **csp,
 694             FcResult    *result)
 695 {
 696     FcFontSet   *sets[2];
 697     int         nsets;
 698
 699     if (!config)
 700     {
 701         config = FcConfigGetCurrent ();
 702         if (!config)
 703             return 0;
 704     }
 705     nsets = 0;
 706     if (config->fonts[FcSetSystem])
 707         sets[nsets++] = config->fonts[FcSetSystem];
 708     if (config->fonts[FcSetApplication])
 709         sets[nsets++] = config->fonts[FcSetApplication];
 710     return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
 711 }