src/fcmatch.c

   1 /*
   2  * $XFree86: xc/lib/fontconfig/src/fcmatch.c,v 1.2 2002/02/15 06:01:28 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 FcCompareBool (char *object, FcValue value1, FcValue value2)
  53 {
  54     if (value2.type != FcTypeBool || value1.type != FcTypeBool)
  55         return -1.0;
  56     return (double) value2.u.b != value1.u.b;
  57 }
  58
  59 static double
  60 FcCompareCharSet (char *object, FcValue value1, FcValue value2)
  61 {
  62     if (value2.type != FcTypeCharSet || value1.type != FcTypeCharSet)
  63         return -1.0;
  64     return (double) FcCharSetSubtractCount (value1.u.c, value2.u.c);
  65 }
  66
  67 static double
  68 FcCompareSize (char *object, FcValue value1, FcValue value2)
  69 {
  70     double  v1, v2, v;
  71
  72     switch (value1.type) {
  73     case FcTypeInteger:
  74         v1 = value1.u.i;
  75         break;
  76     case FcTypeDouble:
  77         v1 = value1.u.d;
  78         break;
  79     default:
  80         return -1;
  81     }
  82     switch (value2.type) {
  83     case FcTypeInteger:
  84         v2 = value2.u.i;
  85         break;
  86     case FcTypeDouble:
  87         v2 = value2.u.d;
  88         break;
  89     default:
  90         return -1;
  91     }
  92     if (v2 == 0)
  93         return 0;
  94     v = v2 - v1;
  95     if (v < 0)
  96         v = -v;
  97     return v;
  98 }
  99
 100 /*
 101  * Order is significant, it defines the precedence of
 102  * each value, earlier values are more significant than
 103  * later values
 104  */
 105 static FcMatcher _FcMatchers [] = {
 106     { FC_FOUNDRY,       FcCompareString, },
 107     { FC_CHARSET,       FcCompareCharSet },
 108     { FC_ANTIALIAS,     FcCompareBool, },
 109     { FC_LANG,          FcCompareString },
 110     { FC_FAMILY,        FcCompareString, },
 111     { FC_SPACING,       FcCompareInteger, },
 112     { FC_PIXEL_SIZE,    FcCompareSize, },
 113     { FC_STYLE,         FcCompareString, },
 114     { FC_SLANT,         FcCompareInteger, },
 115     { FC_WEIGHT,        FcCompareInteger, },
 116     { FC_RASTERIZER,    FcCompareString, },
 117     { FC_OUTLINE,       FcCompareBool, },
 118 };
 119
 120 #define NUM_MATCHER (sizeof _FcMatchers / sizeof _FcMatchers[0])
 121
 122 static FcBool
 123 FcCompareValueList (const char  *object,
 124                     FcValueList *v1orig,        /* pattern */
 125                     FcValueList *v2orig,        /* target */
 126                     FcValue     *bestValue,
 127                     double      *value,
 128                     FcResult    *result)
 129 {
 130     FcValueList    *v1, *v2;
 131     double          v, best;
 132     int             j;
 133     int             i;
 134
 135     for (i = 0; i < NUM_MATCHER; i++)
 136     {
 137         if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
 138                                  (FcChar8 *) object))
 139             break;
 140     }
 141     if (i == NUM_MATCHER)
 142     {
 143         if (bestValue)
 144             *bestValue = v2orig->value;
 145         return FcTrue;
 146     }
 147
 148     best = 1e99;
 149     j = 0;
 150     for (v1 = v1orig; v1; v1 = v1->next)
 151     {
 152         for (v2 = v2orig; v2; v2 = v2->next)
 153         {
 154             v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
 155                                             v1->value,
 156                                             v2->value);
 157             if (v < 0)
 158             {
 159                 *result = FcResultTypeMismatch;
 160                 return FcFalse;
 161             }
 162             if (FcDebug () & FC_DBG_MATCHV)
 163                 printf (" v %g j %d ", v, j);
 164             v = v * 100 + j;
 165             if (v < best)
 166             {
 167                 if (bestValue)
 168                     *bestValue = v2->value;
 169                 best = v;
 170             }
 171         }
 172         j++;
 173     }
 174     if (FcDebug () & FC_DBG_MATCHV)
 175     {
 176         printf (" %s: %g ", object, best);
 177         FcValueListPrint (v1orig);
 178         printf (", ");
 179         FcValueListPrint (v2orig);
 180         printf ("\n");
 181     }
 182     value[i] += best;
 183     return FcTrue;
 184 }
 185
 186 /*
 187  * Return a value indicating the distance between the two lists of
 188  * values
 189  */
 190
 191 static FcBool
 192 FcCompare (FcPattern    *pat,
 193            FcPattern    *fnt,
 194            double       *value,
 195            FcResult     *result)
 196 {
 197     int             i, i1, i2;
 198
 199     for (i = 0; i < NUM_MATCHER; i++)
 200         value[i] = 0.0;
 201
 202     for (i1 = 0; i1 < pat->num; i1++)
 203     {
 204         for (i2 = 0; i2 < fnt->num; i2++)
 205         {
 206             if (!FcStrCmpIgnoreCase ((FcChar8 *) pat->elts[i1].object,
 207                                      (FcChar8 *) fnt->elts[i2].object))
 208             {
 209                 if (!FcCompareValueList (pat->elts[i1].object,
 210                                          pat->elts[i1].values,
 211                                          fnt->elts[i2].values,
 212                                          0,
 213                                          value,
 214                                          result))
 215                     return FcFalse;
 216                 break;
 217             }
 218         }
 219 #if 0
 220         /*
 221          * Overspecified patterns are slightly penalized in
 222          * case some other font includes the requested field
 223          */
 224         if (i2 == fnt->num)
 225         {
 226             for (i2 = 0; i2 < NUM_MATCHER; i2++)
 227             {
 228                 if (!FcStrCmpIgnoreCase (_FcMatchers[i2].object,
 229                                          pat->elts[i1].object))
 230                 {
 231                     value[i2] = 1.0;
 232                     break;
 233                 }
 234             }
 235         }
 236 #endif
 237     }
 238     return FcTrue;
 239 }
 240
 241 FcPattern *
 242 FcFontRenderPrepare (FcConfig       *config,
 243                      FcPattern      *pat,
 244                      FcPattern      *font)
 245 {
 246     FcPattern       *new;
 247     int             i;
 248     FcPatternElt    *fe, *pe;
 249     FcValue         v;
 250     double          score[NUM_MATCHER];
 251     FcResult        result;
 252
 253     new = FcPatternCreate ();
 254     if (!new)
 255         return 0;
 256     for (i = 0; i < font->num; i++)
 257     {
 258         fe = &font->elts[i];
 259         pe = FcPatternFind (pat, fe->object, FcFalse);
 260         if (pe)
 261         {
 262             if (!FcCompareValueList (pe->object, pe->values,
 263                                      fe->values, &v, score, &result))
 264             {
 265                 FcPatternDestroy (new);
 266                 return 0;
 267             }
 268         }
 269         else
 270             v = fe->values->value;
 271         FcPatternAdd (new, fe->object, v, FcTrue);
 272     }
 273     for (i = 0; i < pat->num; i++)
 274     {
 275         pe = &pat->elts[i];
 276         fe = FcPatternFind (font, pe->object, FcFalse);
 277         if (!fe)
 278             FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
 279     }
 280     FcConfigSubstitute (config, new, FcMatchFont);
 281     return new;
 282 }
 283
 284 FcPattern *
 285 FcFontSetMatch (FcConfig    *config,
 286                 FcFontSet   **sets,
 287                 int         nsets,
 288                 FcPattern   *p,
 289                 FcResult    *result)
 290 {
 291     double          score[NUM_MATCHER], bestscore[NUM_MATCHER];
 292     int             f;
 293     FcFontSet       *s;
 294     FcPattern       *best;
 295     int             i;
 296     int             set;
 297
 298     for (i = 0; i < NUM_MATCHER; i++)
 299         bestscore[i] = 0;
 300     best = 0;
 301     if (FcDebug () & FC_DBG_MATCH)
 302     {
 303         printf ("Match ");
 304         FcPatternPrint (p);
 305     }
 306     if (!config)
 307     {
 308         config = FcConfigGetCurrent ();
 309         if (!config)
 310             return 0;
 311     }
 312     for (set = 0; set < nsets; set++)
 313     {
 314         s = sets[set];
 315         if (!s)
 316             continue;
 317         for (f = 0; f < s->nfont; f++)
 318         {
 319             if (FcDebug () & FC_DBG_MATCHV)
 320             {
 321                 printf ("Font %d ", f);
 322                 FcPatternPrint (s->fonts[f]);
 323             }
 324             if (!FcCompare (p, s->fonts[f], score, result))
 325                 return 0;
 326             if (FcDebug () & FC_DBG_MATCHV)
 327             {
 328                 printf ("Score");
 329                 for (i = 0; i < NUM_MATCHER; i++)
 330                 {
 331                     printf (" %g", score[i]);
 332                 }
 333                 printf ("\n");
 334             }
 335             for (i = 0; i < NUM_MATCHER; i++)
 336             {
 337                 if (best && bestscore[i] < score[i])
 338                     break;
 339                 if (!best || score[i] < bestscore[i])
 340                 {
 341                     for (i = 0; i < NUM_MATCHER; i++)
 342                         bestscore[i] = score[i];
 343                     best = s->fonts[f];
 344                     break;
 345                 }
 346             }
 347         }
 348     }
 349     if (FcDebug () & FC_DBG_MATCH)
 350     {
 351         printf ("Best score");
 352         for (i = 0; i < NUM_MATCHER; i++)
 353             printf (" %g", bestscore[i]);
 354         FcPatternPrint (best);
 355     }
 356     if (!best)
 357     {
 358         *result = FcResultNoMatch;
 359         return 0;
 360     }
 361     return FcFontRenderPrepare (config, p, best);
 362 }
 363
 364 FcPattern *
 365 FcFontMatch (FcConfig   *config,
 366              FcPattern  *p,
 367              FcResult   *result)
 368 {
 369     FcFontSet   *sets[2];
 370     int         nsets;
 371
 372     if (!config)
 373     {
 374         config = FcConfigGetCurrent ();
 375         if (!config)
 376             return 0;
 377     }
 378     nsets = 0;
 379     if (config->fonts[FcSetSystem])
 380         sets[nsets++] = config->fonts[FcSetSystem];
 381     if (config->fonts[FcSetApplication])
 382         sets[nsets++] = config->fonts[FcSetApplication];
 383     return FcFontSetMatch (config, sets, nsets, p, result);
 384 }
 385
 386 #include "fcavl.h"
 387
 388 typedef struct _FcSortNode {
 389     FcAvlNode   avl;
 390     FcPattern   *pattern;
 391     double      score[NUM_MATCHER];
 392 } FcSortNode;
 393
 394 static FcBool
 395 FcSortMore (FcAvlNode *aa, FcAvlNode *ab)
 396 {
 397     FcSortNode  *a = (FcSortNode *) aa;
 398     FcSortNode  *b = (FcSortNode *) ab;
 399     int         i;
 400
 401     for (i = 0; i < NUM_MATCHER; i++)
 402     {
 403         if (a->score[i] > b->score[i])
 404             return FcTrue;
 405         if (a->score[i] < b->score[i])
 406             return FcFalse;
 407     }
 408     if (aa > ab)
 409         return FcTrue;
 410     return FcFalse;
 411 }
 412
 413 static FcBool
 414 FcSortWalk (FcSortNode *n, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 415 {
 416     FcCharSet   *ncs;
 417
 418     if (!n)
 419         return FcTrue;
 420     if (!FcSortWalk ((FcSortNode *) n->avl.left, fs, cs, trim))
 421         return FcFalse;
 422     if (FcPatternGetCharSet (n->pattern, FC_CHARSET, 0, &ncs) == FcResultMatch)
 423     {
 424         if (!trim || !*cs || FcCharSetSubtractCount (ncs, *cs) != 0)
 425         {
 426             if (*cs)
 427             {
 428                 ncs = FcCharSetUnion (ncs, *cs);
 429                 if (!ncs)
 430                     return FcFalse;
 431                 FcCharSetDestroy (*cs);
 432             }
 433             else
 434                 ncs = FcCharSetCopy (ncs);
 435             *cs = ncs;
 436             if (!FcFontSetAdd (fs, n->pattern))
 437                 return FcFalse;
 438         }
 439     }
 440     if (!FcSortWalk ((FcSortNode *) n->avl.right, fs, cs, trim))
 441         return FcFalse;
 442     return FcTrue;
 443 }
 444
 445 FcFontSet *
 446 FcFontSetSort (FcConfig     *config,
 447                FcFontSet    **sets,
 448                int          nsets,
 449                FcPattern    *p,
 450                FcBool       trim,
 451                FcCharSet    **csp,
 452                FcResult     *result)
 453 {
 454     FcFontSet       *ret;
 455     FcFontSet       *s;
 456     FcSortNode      *nodes;
 457     int             nnodes;
 458     FcSortNode      *root;
 459     FcSortNode      *new;
 460     FcCharSet       *cs;
 461     int             set;
 462     int             f;
 463     int             i;
 464
 465     nnodes = 0;
 466     for (set = 0; set < nsets; set++)
 467     {
 468         s = sets[set];
 469         if (!s)
 470             continue;
 471         nnodes += s->nfont;
 472     }
 473     if (!nnodes)
 474         goto bail0;
 475     nodes = malloc (nnodes * sizeof (FcSortNode));
 476     if (!nodes)
 477         goto bail0;
 478
 479     root = 0;
 480     new = nodes;
 481     for (set = 0; set < nsets; set++)
 482     {
 483         s = sets[set];
 484         if (!s)
 485             continue;
 486         for (f = 0; f < s->nfont; f++)
 487         {
 488             if (FcDebug () & FC_DBG_MATCHV)
 489             {
 490                 printf ("Font %d ", f);
 491                 FcPatternPrint (s->fonts[f]);
 492             }
 493             new->pattern = s->fonts[f];
 494             if (!FcCompare (p, new->pattern, new->score, result))
 495                 goto bail1;
 496             if (FcDebug () & FC_DBG_MATCHV)
 497             {
 498                 printf ("Score");
 499                 for (i = 0; i < NUM_MATCHER; i++)
 500                 {
 501                     printf (" %g", new->score[i]);
 502                 }
 503                 printf ("\n");
 504             }
 505             FcAvlInsert (FcSortMore, (FcAvlNode **) &root, &new->avl);
 506             new++;
 507         }
 508     }
 509
 510     ret = FcFontSetCreate ();
 511     if (!ret)
 512         goto bail1;
 513
 514     cs = 0;
 515
 516     if (!FcSortWalk (root, ret, &cs, trim))
 517         goto bail2;
 518
 519     *csp = cs;
 520
 521     return ret;
 522
 523 bail2:
 524     if (cs)
 525         FcCharSetDestroy (cs);
 526     FcFontSetDestroy (ret);
 527 bail1:
 528     free (nodes);
 529 bail0:
 530     return 0;
 531 }