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 typedef struct _FcSortNode {
 387     FcPattern   *pattern;
 388     double      score[NUM_MATCHER];
 389 } FcSortNode;
 390
 391 static int
 392 FcSortCompare (const void *aa, const void *ab)
 393 {
 394     FcSortNode  *a = *(FcSortNode **) aa;
 395     FcSortNode  *b = *(FcSortNode **) ab;
 396     int         i;
 397
 398     for (i = 0; i < NUM_MATCHER; i++)
 399     {
 400         if (a->score[i] > b->score[i])
 401             return -1;
 402         if (a->score[i] < b->score[i])
 403             return 1;
 404     }
 405     return 0;
 406 }
 407
 408 static FcBool
 409 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
 410 {
 411     FcCharSet   *ncs;
 412     FcSortNode  *node;
 413
 414     while (nnode--)
 415     {
 416         node = *n++;
 417         if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
 418             FcResultMatch)
 419         {
 420             if (!trim || !*cs || FcCharSetSubtractCount (ncs, *cs) != 0)
 421             {
 422                 if (*cs)
 423                 {
 424                     ncs = FcCharSetUnion (ncs, *cs);
 425                     if (!ncs)
 426                         return FcFalse;
 427                     FcCharSetDestroy (*cs);
 428                 }
 429                 else
 430                     ncs = FcCharSetCopy (ncs);
 431                 *cs = ncs;
 432                 if (!FcFontSetAdd (fs, node->pattern))
 433                     return FcFalse;
 434             }
 435         }
 436     }
 437     return FcTrue;
 438 }
 439
 440 FcFontSet *
 441 FcFontSetSort (FcConfig     *config,
 442                FcFontSet    **sets,
 443                int          nsets,
 444                FcPattern    *p,
 445                FcBool       trim,
 446                FcCharSet    **csp,
 447                FcResult     *result)
 448 {
 449     FcFontSet       *ret;
 450     FcFontSet       *s;
 451     FcSortNode      *nodes;
 452     FcSortNode      **nodeps, **nodep;
 453     int             nnodes;
 454     FcSortNode      *new;
 455     FcCharSet       *cs;
 456     int             set;
 457     int             f;
 458     int             i;
 459
 460     nnodes = 0;
 461     for (set = 0; set < nsets; set++)
 462     {
 463         s = sets[set];
 464         if (!s)
 465             continue;
 466         nnodes += s->nfont;
 467     }
 468     if (!nnodes)
 469         goto bail0;
 470     nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
 471     if (!nodes)
 472         goto bail0;
 473     nodeps = (FcSortNode **) nodes + nnodes;
 474
 475     new = nodes;
 476     nodep = nodeps;
 477     for (set = 0; set < nsets; set++)
 478     {
 479         s = sets[set];
 480         if (!s)
 481             continue;
 482         for (f = 0; f < s->nfont; f++)
 483         {
 484             if (FcDebug () & FC_DBG_MATCHV)
 485             {
 486                 printf ("Font %d ", f);
 487                 FcPatternPrint (s->fonts[f]);
 488             }
 489             new->pattern = s->fonts[f];
 490             if (!FcCompare (p, new->pattern, new->score, result))
 491                 goto bail1;
 492             if (FcDebug () & FC_DBG_MATCHV)
 493             {
 494                 printf ("Score");
 495                 for (i = 0; i < NUM_MATCHER; i++)
 496                 {
 497                     printf (" %g", new->score[i]);
 498                 }
 499                 printf ("\n");
 500             }
 501             *nodep = new;
 502             new++;
 503             nodep++;
 504         }
 505     }
 506
 507     nnodes = new - nodes;
 508
 509     qsort (nodeps, sizeof (FcSortNode *), nnodes,
 510            FcSortCompare);
 511
 512     ret = FcFontSetCreate ();
 513     if (!ret)
 514         goto bail1;
 515
 516     cs = 0;
 517
 518     if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
 519         goto bail2;
 520
 521     *csp = cs;
 522
 523     return ret;
 524
 525 bail2:
 526     if (cs)
 527         FcCharSetDestroy (cs);
 528     FcFontSetDestroy (ret);
 529 bail1:
 530     free (nodes);
 531 bail0:
 532     return 0;
 533 }