2 * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
4 * Copyright © 2000 Keith Packard
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.
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.
31 FcCompareNumber (FcValue *value1, FcValue *value2)
35 switch (value1->type) {
37 v1 = (double) value1->u.i;
45 switch (value2->type) {
47 v2 = (double) value2->u.i;
62 FcCompareString (FcValue *v1, FcValue *v2)
64 return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
68 FcCompareFamily (FcValue *v1, FcValue *v2)
70 /* rely on the guarantee in FcPatternAddWithBinding that
71 * families are always FcTypeString. */
72 const FcChar8* v1_string = fc_value_string(v1);
73 const FcChar8* v2_string = fc_value_string(v2);
75 if (FcToLower(*v1_string) != FcToLower(*v2_string))
78 return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
82 FcCompareLang (FcValue *v1, FcValue *v2)
85 FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
87 switch (value1.type) {
89 switch (value2.type) {
91 result = FcLangSetCompare (value1.u.l, value2.u.l);
94 result = FcLangSetHasLang (value1.u.l,
102 switch (value2.type) {
104 result = FcLangSetHasLang (value2.u.l, value1.u.s);
107 result = FcLangCompare (value1.u.s,
120 case FcLangDifferentCountry:
122 case FcLangDifferentLang:
129 FcCompareBool (FcValue *v1, FcValue *v2)
131 if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
133 return (double) v2->u.b != v1->u.b;
137 FcCompareCharSet (FcValue *v1, FcValue *v2)
139 return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
143 FcCompareSize (FcValue *value1, FcValue *value2)
147 switch (value1->type) {
157 switch (value2->type) {
175 typedef struct _FcMatcher {
177 double (*compare) (FcValue *value1, FcValue *value2);
182 * Order is significant, it defines the precedence of
183 * each value, earlier values are more significant than
186 static FcMatcher _FcMatchers [] = {
187 { FC_FOUNDRY, FcCompareString, 0, 0 },
188 #define MATCH_FOUNDRY 0
189 #define MATCH_FOUNDRY_INDEX 0
191 { FC_CHARSET, FcCompareCharSet, 1, 1 },
192 #define MATCH_CHARSET 1
193 #define MATCH_CHARSET_INDEX 1
195 { FC_FAMILY, FcCompareFamily, 2, 4 },
196 #define MATCH_FAMILY 2
197 #define MATCH_FAMILY_STRONG_INDEX 2
198 #define MATCH_FAMILY_WEAK_INDEX 4
200 { FC_LANG, FcCompareLang, 3, 3 },
202 #define MATCH_LANG_INDEX 3
204 { FC_SPACING, FcCompareNumber, 5, 5 },
205 #define MATCH_SPACING 4
206 #define MATCH_SPACING_INDEX 5
208 { FC_PIXEL_SIZE, FcCompareSize, 6, 6 },
209 #define MATCH_PIXEL_SIZE 5
210 #define MATCH_PIXEL_SIZE_INDEX 6
212 { FC_STYLE, FcCompareString, 7, 7 },
213 #define MATCH_STYLE 6
214 #define MATCH_STYLE_INDEX 7
216 { FC_SLANT, FcCompareNumber, 8, 8 },
217 #define MATCH_SLANT 7
218 #define MATCH_SLANT_INDEX 8
220 { FC_WEIGHT, FcCompareNumber, 9, 9 },
221 #define MATCH_WEIGHT 8
222 #define MATCH_WEIGHT_INDEX 9
224 { FC_WIDTH, FcCompareNumber, 10, 10 },
225 #define MATCH_WIDTH 9
226 #define MATCH_WIDTH_INDEX 10
228 { FC_ANTIALIAS, FcCompareBool, 11, 11 },
229 #define MATCH_ANTIALIAS 10
230 #define MATCH_ANTIALIAS_INDEX 11
232 { FC_RASTERIZER, FcCompareString, 12, 12 },
233 #define MATCH_RASTERIZER 11
234 #define MATCH_RASTERIZER_INDEX 12
236 { FC_OUTLINE, FcCompareBool, 13, 13 },
237 #define MATCH_OUTLINE 12
238 #define MATCH_OUTLINE_INDEX 13
240 { FC_FONTVERSION, FcCompareNumber, 14, 14 },
241 #define MATCH_FONTVERSION 13
242 #define MATCH_FONTVERSION_INDEX 14
245 #define NUM_MATCH_VALUES 15
248 FcCompareValueList (const char *object,
249 FcValueListPtr v1orig, /* pattern */
250 FcValueListPtr v2orig, /* target */
255 FcValueListPtr v1, v2;
256 FcValueList *v1_ptrU, *v2_ptrU;
257 double v, best, bestStrong, bestWeak;
262 * Locate the possible matching entry by examining the
263 * first few characters in object
266 switch (FcToLower (object[0])) {
268 switch (FcToLower (object[1])) {
270 switch (FcToLower (object[2])) {
272 i = MATCH_FOUNDRY; break;
274 i = MATCH_FONTVERSION; break;
278 i = MATCH_FAMILY; break;
282 i = MATCH_CHARSET; break;
284 i = MATCH_ANTIALIAS; break;
286 i = MATCH_LANG; break;
288 switch (FcToLower (object[1])) {
290 i = MATCH_SPACING; break;
292 i = MATCH_STYLE; break;
294 i = MATCH_SLANT; break;
298 i = MATCH_PIXEL_SIZE; break;
300 switch (FcToLower (object[1])) {
302 i = MATCH_WIDTH; break;
304 i = MATCH_WEIGHT; break;
308 i = MATCH_RASTERIZER; break;
310 i = MATCH_OUTLINE; break;
313 FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
314 (FcChar8 *) object) != 0)
317 *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
321 for (i = 0; i < NUM_MATCHER; i++)
323 if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
327 if (i == NUM_MATCHER)
330 *bestValue = v2orig->value;
338 for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
339 v1 = FcValueListPtrU(v1)->next, v1_ptrU = FcValueListPtrU(v1))
341 for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); FcValueListPtrU(v2);
342 v2 = FcValueListPtrU(v2)->next)
344 v = (*_FcMatchers[i].compare) (&v1_ptrU->value,
348 *result = FcResultTypeMismatch;
351 if (FcDebug () & FC_DBG_MATCHV)
352 printf (" v %g j %d ", v, j);
357 *bestValue = FcValueCanonicalize(&v2_ptrU->value);
360 if (v1_ptrU->binding == FcValueBindingStrong)
373 if (FcDebug () & FC_DBG_MATCHV)
375 printf (" %s: %g ", object, best);
376 FcValueListPrint (v1orig);
378 FcValueListPrint (v2orig);
383 int weak = _FcMatchers[i].weak;
384 int strong = _FcMatchers[i].strong;
386 value[strong] += best;
389 value[weak] += bestWeak;
390 value[strong] += bestStrong;
397 * Return a value indicating the distance between the two lists of
402 FcCompare (FcPattern *pat,
409 for (i = 0; i < NUM_MATCH_VALUES; i++)
414 while (i1 < pat->num && i2 < fnt->num)
416 FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
417 FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
419 i = FcObjectPtrCompare(elt_i1->object, elt_i2->object);
426 if (!FcCompareValueList (FcObjectPtrU(elt_i1->object),
427 elt_i1->values, elt_i2->values,
438 FcFontRenderPrepare (FcConfig *config,
444 FcPatternElt *fe, *pe;
448 new = FcPatternCreate ();
451 for (i = 0; i < font->num; i++)
453 fe = FcPatternEltU(font->elts)+i;
454 pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
457 if (!FcCompareValueList (FcObjectPtrU(pe->object), pe->values,
458 fe->values, &v, 0, &result))
460 FcPatternDestroy (new);
465 v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
466 FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
468 for (i = 0; i < pat->num; i++)
470 pe = FcPatternEltU(pat->elts)+i;
471 fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
473 FcPatternAdd (new, FcObjectPtrU(pe->object),
474 FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
477 if (FcPatternFindElt (font, FC_FILE))
478 FcPatternTransferFullFname (new, font);
480 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
485 FcFontSetMatch (FcConfig *config,
491 double score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
498 for (i = 0; i < NUM_MATCH_VALUES; i++)
501 if (FcDebug () & FC_DBG_MATCH)
508 config = FcConfigGetCurrent ();
511 *result = FcResultOutOfMemory;
515 for (set = 0; set < nsets; set++)
520 for (f = 0; f < s->nfont; f++)
522 if (FcDebug () & FC_DBG_MATCHV)
524 printf ("Font %d ", f);
525 FcPatternPrint (s->fonts[f]);
527 if (!FcCompare (p, s->fonts[f], score, result))
529 if (FcDebug () & FC_DBG_MATCHV)
532 for (i = 0; i < NUM_MATCH_VALUES; i++)
534 printf (" %g", score[i]);
538 for (i = 0; i < NUM_MATCH_VALUES; i++)
540 if (best && bestscore[i] < score[i])
542 if (!best || score[i] < bestscore[i])
544 for (i = 0; i < NUM_MATCH_VALUES; i++)
545 bestscore[i] = score[i];
552 if (FcDebug () & FC_DBG_MATCH)
554 printf ("Best score");
555 for (i = 0; i < NUM_MATCH_VALUES; i++)
556 printf (" %g", bestscore[i]);
557 FcPatternPrint (best);
561 *result = FcResultNoMatch;
564 return FcFontRenderPrepare (config, p, best);
568 FcFontMatch (FcConfig *config,
577 config = FcConfigGetCurrent ();
582 if (config->fonts[FcSetSystem])
583 sets[nsets++] = config->fonts[FcSetSystem];
584 if (config->fonts[FcSetApplication])
585 sets[nsets++] = config->fonts[FcSetApplication];
586 return FcFontSetMatch (config, sets, nsets, p, result);
589 typedef struct _FcSortNode {
591 double score[NUM_MATCH_VALUES];
595 FcSortCompare (const void *aa, const void *ab)
597 FcSortNode *a = *(FcSortNode **) aa;
598 FcSortNode *b = *(FcSortNode **) ab;
599 double *as = &a->score[0];
600 double *bs = &b->score[0];
601 double ad = 0, bd = 0;
604 i = NUM_MATCH_VALUES;
605 while (i-- && (ad = *as++) == (bd = *bs++))
607 return ad < bd ? -1 : ad > bd ? 1 : 0;
611 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
619 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
623 * If this font isn't a subset of the previous fonts,
626 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
630 ncs = FcCharSetUnion (ncs, *cs);
633 FcCharSetDestroy (*cs);
636 ncs = FcCharSetCopy (ncs);
638 FcPatternReference (node->pattern);
639 if (FcDebug () & FC_DBG_MATCH)
642 FcPatternPrint (node->pattern);
644 if (!FcFontSetAdd (fs, node->pattern))
646 FcPatternDestroy (node->pattern);
656 FcFontSetSortDestroy (FcFontSet *fs)
658 FcFontSetDestroy (fs);
662 FcFontSetSort (FcConfig *config,
673 FcSortNode **nodeps, **nodep;
681 FcBool *patternLangSat;
684 if (FcDebug () & FC_DBG_MATCH)
690 for (set = 0; set < nsets; set++)
700 for (nPatternLang = 0;
701 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
706 nodes = malloc (nnodes * sizeof (FcSortNode) +
707 nnodes * sizeof (FcSortNode *) +
708 nPatternLang * sizeof (FcBool));
711 nodeps = (FcSortNode **) (nodes + nnodes);
712 patternLangSat = (FcBool *) (nodeps + nnodes);
716 for (set = 0; set < nsets; set++)
721 for (f = 0; f < s->nfont; f++)
723 if (FcDebug () & FC_DBG_MATCHV)
725 printf ("Font %d ", f);
726 FcPatternPrint (s->fonts[f]);
728 new->pattern = s->fonts[f];
729 if (!FcCompare (p, new->pattern, new->score, result))
731 if (FcDebug () & FC_DBG_MATCHV)
734 for (i = 0; i < NUM_MATCH_VALUES; i++)
736 printf (" %g", new->score[i]);
746 nnodes = new - nodes;
748 qsort (nodeps, nnodes, sizeof (FcSortNode *),
751 for (i = 0; i < nPatternLang; i++)
752 patternLangSat[i] = FcFalse;
754 for (f = 0; f < nnodes; f++)
756 FcBool satisfies = FcFalse;
758 * If this node matches any language, go check
759 * which ones and satisfy those entries
761 if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
763 for (i = 0; i < nPatternLang; i++)
767 if (!patternLangSat[i] &&
768 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
769 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
771 double compare = FcCompareLang (&patternLang, &nodeLang);
772 if (compare >= 0 && compare < 2)
774 if (FcDebug () & FC_DBG_MATCHV)
779 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
780 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
781 printf ("Font %s:%s matches language %d\n", family, style, i);
783 patternLangSat[i] = FcTrue;
791 nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
795 * Re-sort once the language issues have been settled
797 qsort (nodeps, nnodes, sizeof (FcSortNode *),
800 ret = FcFontSetCreate ();
806 if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
812 FcCharSetDestroy (cs);
820 FcCharSetDestroy (cs);
821 FcFontSetDestroy (ret);
829 FcFontSort (FcConfig *config,
840 config = FcConfigGetCurrent ();
845 if (config->fonts[FcSetSystem])
846 sets[nsets++] = config->fonts[FcSetSystem];
847 if (config->fonts[FcSetApplication])
848 sets[nsets++] = config->fonts[FcSetApplication];
849 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);