src/fcmatch.c

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