2 * fontconfig/src/fcmatch.c
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 the author(s) not be used in
11 * advertising or publicity pertaining to distribution of the software without
12 * specific, written prior permission. The authors make no
13 * representations about the suitability of this software for any purpose. It
14 * is provided "as is" without express or implied warranty.
16 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18 * EVENT SHALL THE AUTHOR(S) 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.
28 FcCompareNumber (FcValue *value1, FcValue *value2)
32 switch ((int) value1->type) {
34 v1 = (double) value1->u.i;
42 switch ((int) value2->type) {
44 v2 = (double) value2->u.i;
59 FcCompareString (FcValue *v1, FcValue *v2)
61 return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
65 FcCompareFamily (FcValue *v1, FcValue *v2)
67 /* rely on the guarantee in FcPatternObjectAddWithBinding that
68 * families are always FcTypeString. */
69 const FcChar8* v1_string = FcValueString(v1);
70 const FcChar8* v2_string = FcValueString(v2);
72 if (FcToLower(*v1_string) != FcToLower(*v2_string) &&
73 *v1_string != ' ' && *v2_string != ' ')
76 return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
80 FcCompareLang (FcValue *v1, FcValue *v2)
83 FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
85 switch ((int) value1.type) {
87 switch ((int) value2.type) {
89 result = FcLangSetCompare (value1.u.l, value2.u.l);
92 result = FcLangSetHasLang (value1.u.l,
100 switch ((int) value2.type) {
102 result = FcLangSetHasLang (value2.u.l, value1.u.s);
105 result = FcLangCompare (value1.u.s,
118 case FcLangDifferentCountry:
120 case FcLangDifferentLang:
127 FcCompareBool (FcValue *v1, FcValue *v2)
129 if (v2->type != FcTypeBool || v1->type != FcTypeBool)
131 return (double) v2->u.b != v1->u.b;
135 FcCompareCharSet (FcValue *v1, FcValue *v2)
137 return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
141 FcCompareSize (FcValue *value1, FcValue *value2)
145 switch ((int) value1->type) {
155 switch ((int) value2->type) {
174 FcCompareFilename (FcValue *v1, FcValue *v2)
176 const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
177 if (FcStrCmp (s1, s2) == 0)
179 else if (FcStrCmpIgnoreCase (s1, s2) == 0)
181 else if (FcStrRegexCmp (s2, s1))
183 else if (FcStrRegexCmpIgnoreCase (s2, s1))
189 typedef struct _FcMatcher {
191 double (*compare) (FcValue *value1, FcValue *value2);
196 * Order is significant, it defines the precedence of
197 * each value, earlier values are more significant than
200 static const FcMatcher _FcMatchers [] = {
201 { FC_FILE_OBJECT, FcCompareFilename, 0, 0 },
203 { FC_FOUNDRY_OBJECT, FcCompareString, 1, 1 },
204 #define MATCH_FOUNDRY 1
205 { FC_CHARSET_OBJECT, FcCompareCharSet, 2, 2 },
206 #define MATCH_CHARSET 2
207 { FC_FAMILY_OBJECT, FcCompareFamily, 3, 5 },
208 #define MATCH_FAMILY 3
209 { FC_LANG_OBJECT, FcCompareLang, 4, 4 },
211 #define MATCH_LANG_INDEX 4
212 { FC_SPACING_OBJECT, FcCompareNumber, 6, 6 },
213 #define MATCH_SPACING 5
214 { FC_PIXEL_SIZE_OBJECT, FcCompareSize, 7, 7 },
215 #define MATCH_PIXEL_SIZE 6
216 { FC_STYLE_OBJECT, FcCompareString, 8, 8 },
217 #define MATCH_STYLE 7
218 { FC_SLANT_OBJECT, FcCompareNumber, 9, 9 },
219 #define MATCH_SLANT 8
220 { FC_WEIGHT_OBJECT, FcCompareNumber, 10, 10 },
221 #define MATCH_WEIGHT 9
222 { FC_WIDTH_OBJECT, FcCompareNumber, 11, 11 },
223 #define MATCH_WIDTH 10
224 { FC_DECORATIVE_OBJECT, FcCompareBool, 12, 12 },
225 #define MATCH_DECORATIVE 11
226 { FC_ANTIALIAS_OBJECT, FcCompareBool, 13, 13 },
227 #define MATCH_ANTIALIAS 12
228 { FC_RASTERIZER_OBJECT, FcCompareString, 14, 14 },
229 #define MATCH_RASTERIZER 13
230 { FC_OUTLINE_OBJECT, FcCompareBool, 15, 15 },
231 #define MATCH_OUTLINE 14
232 { FC_FONTVERSION_OBJECT, FcCompareNumber, 16, 16 },
233 #define MATCH_FONTVERSION 15
236 #define NUM_MATCH_VALUES 17
238 static const FcMatcher*
239 FcObjectToMatcher (FcObject object,
247 i = MATCH_FILE; break;
248 case FC_FOUNDRY_OBJECT:
249 i = MATCH_FOUNDRY; break;
250 case FC_FONTVERSION_OBJECT:
251 i = MATCH_FONTVERSION; break;
252 case FC_FAMILY_OBJECT:
253 i = MATCH_FAMILY; break;
254 case FC_CHARSET_OBJECT:
255 i = MATCH_CHARSET; break;
256 case FC_ANTIALIAS_OBJECT:
257 i = MATCH_ANTIALIAS; break;
259 i = MATCH_LANG; break;
260 case FC_SPACING_OBJECT:
261 i = MATCH_SPACING; break;
262 case FC_STYLE_OBJECT:
263 i = MATCH_STYLE; break;
264 case FC_SLANT_OBJECT:
265 i = MATCH_SLANT; break;
266 case FC_PIXEL_SIZE_OBJECT:
267 i = MATCH_PIXEL_SIZE; break;
268 case FC_WIDTH_OBJECT:
269 i = MATCH_WIDTH; break;
270 case FC_WEIGHT_OBJECT:
271 i = MATCH_WEIGHT; break;
272 case FC_RASTERIZER_OBJECT:
273 i = MATCH_RASTERIZER; break;
274 case FC_OUTLINE_OBJECT:
275 i = MATCH_OUTLINE; break;
276 case FC_DECORATIVE_OBJECT:
277 i = MATCH_DECORATIVE; break;
282 case FC_FAMILYLANG_OBJECT:
283 case FC_STYLELANG_OBJECT:
284 case FC_FULLNAMELANG_OBJECT:
285 i = MATCH_LANG; break;
293 return _FcMatchers+i;
297 FcCompareValueList (FcObject object,
298 const FcMatcher *match,
299 FcValueListPtr v1orig, /* pattern */
300 FcValueListPtr v2orig, /* target */
306 FcValueListPtr v1, v2;
307 double v, best, bestStrong, bestWeak;
313 *bestValue = FcValueCanonicalize(&v2orig->value);
323 for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
325 for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
327 v = (match->compare) (&v1->value, &v2->value);
330 *result = FcResultTypeMismatch;
337 *bestValue = FcValueCanonicalize(&v2->value);
341 if (v1->binding == FcValueBindingStrong)
354 if (FcDebug () & FC_DBG_MATCHV)
356 printf (" %s: %g ", FcObjectName (object), best);
357 FcValueListPrint (v1orig);
359 FcValueListPrint (v2orig);
364 int weak = match->weak;
365 int strong = match->strong;
367 value[strong] += best;
370 value[weak] += bestWeak;
371 value[strong] += bestStrong;
381 * Return a value indicating the distance between the two lists of
386 FcCompare (FcPattern *pat,
393 for (i = 0; i < NUM_MATCH_VALUES; i++)
398 while (i1 < pat->num && i2 < fnt->num)
400 FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
401 FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
403 i = FcObjectCompare(elt_i1->object, elt_i2->object);
410 const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
411 if (!FcCompareValueList (elt_i1->object, match,
412 FcPatternEltValues(elt_i1),
413 FcPatternEltValues(elt_i2),
414 NULL, value, NULL, result))
424 FcFontRenderPrepare (FcConfig *config,
430 FcPatternElt *fe, *pe, *fel, *pel;
434 assert (pat != NULL);
435 assert (font != NULL);
437 new = FcPatternCreate ();
440 for (i = 0; i < font->num; i++)
442 fe = &FcPatternElts(font)[i];
443 if (fe->object == FC_FAMILYLANG_OBJECT ||
444 fe->object == FC_STYLELANG_OBJECT ||
445 fe->object == FC_FULLNAMELANG_OBJECT)
447 /* ignore those objects. we need to deal with them
451 if (fe->object == FC_FAMILY_OBJECT ||
452 fe->object == FC_STYLE_OBJECT ||
453 fe->object == FC_FULLNAME_OBJECT)
455 FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
456 FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
457 FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
459 fel = FcPatternObjectFindElt (font, fe->object + 1);
460 pel = FcPatternObjectFindElt (pat, fe->object + 1);
467 pe = FcPatternObjectFindElt (pat, fe->object);
470 const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
472 if (!FcCompareValueList (pe->object, match,
473 FcPatternEltValues(pe),
474 FcPatternEltValues(fe), &v, NULL, NULL, &result))
476 FcPatternDestroy (new);
482 FcValueListPtr l1, l2, ln = NULL, ll = NULL;
484 match = FcObjectToMatcher (pel->object, FcTrue);
485 if (!FcCompareValueList (pel->object, match,
486 FcPatternEltValues (pel),
487 FcPatternEltValues (fel), NULL, NULL, &n, &result))
489 FcPatternDestroy (new);
493 for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
494 l1 != NULL || l2 != NULL;
495 j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
500 ln = FcValueListPrepend (ln,
501 FcValueCanonicalize (&l1->value),
502 FcValueBindingStrong);
504 ll = FcValueListPrepend (ll,
505 FcValueCanonicalize (&l2->value),
506 FcValueBindingStrong);
511 ln = FcValueListAppend (ln,
512 FcValueCanonicalize (&l1->value),
513 FcValueBindingStrong);
515 ll = FcValueListAppend (ll,
516 FcValueCanonicalize (&l2->value),
517 FcValueBindingStrong);
520 FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
521 FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
527 FcValueListPtr l1, l2;
530 l1 = FcValueListDuplicate (FcPatternEltValues (fe));
531 l2 = FcValueListDuplicate (FcPatternEltValues (fel));
532 FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
533 FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
542 v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
544 FcPatternObjectAdd (new, fe->object, v, FcFalse);
546 for (i = 0; i < pat->num; i++)
548 pe = &FcPatternElts(pat)[i];
549 fe = FcPatternObjectFindElt (font, pe->object);
552 v = FcValueCanonicalize(&FcPatternEltValues(pe)->value);
553 FcPatternObjectAdd (new, pe->object, v, FcTrue);
557 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
562 FcFontSetMatchInternal (FcFontSet **sets,
567 double score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
574 for (i = 0; i < NUM_MATCH_VALUES; i++)
577 if (FcDebug () & FC_DBG_MATCH)
582 for (set = 0; set < nsets; set++)
587 for (f = 0; f < s->nfont; f++)
589 if (FcDebug () & FC_DBG_MATCHV)
591 printf ("Font %d ", f);
592 FcPatternPrint (s->fonts[f]);
594 if (!FcCompare (p, s->fonts[f], score, result))
596 if (FcDebug () & FC_DBG_MATCHV)
599 for (i = 0; i < NUM_MATCH_VALUES; i++)
601 printf (" %g", score[i]);
605 for (i = 0; i < NUM_MATCH_VALUES; i++)
607 if (best && bestscore[i] < score[i])
609 if (!best || score[i] < bestscore[i])
611 for (i = 0; i < NUM_MATCH_VALUES; i++)
612 bestscore[i] = score[i];
619 if (FcDebug () & FC_DBG_MATCH)
621 printf ("Best score");
622 for (i = 0; i < NUM_MATCH_VALUES; i++)
623 printf (" %g", bestscore[i]);
625 FcPatternPrint (best);
627 /* assuming that 'result' is initialized with FcResultNoMatch
628 * outside this function */
630 *result = FcResultMatch;
636 FcFontSetMatch (FcConfig *config,
644 assert (sets != NULL);
646 assert (result != NULL);
648 *result = FcResultNoMatch;
652 config = FcConfigGetCurrent ();
656 best = FcFontSetMatchInternal (sets, nsets, p, result);
658 return FcFontRenderPrepare (config, p, best);
664 FcFontMatch (FcConfig *config,
673 assert (result != NULL);
675 *result = FcResultNoMatch;
679 config = FcConfigGetCurrent ();
684 if (config->fonts[FcSetSystem])
685 sets[nsets++] = config->fonts[FcSetSystem];
686 if (config->fonts[FcSetApplication])
687 sets[nsets++] = config->fonts[FcSetApplication];
689 best = FcFontSetMatchInternal (sets, nsets, p, result);
691 return FcFontRenderPrepare (config, p, best);
696 typedef struct _FcSortNode {
698 double score[NUM_MATCH_VALUES];
702 FcSortCompare (const void *aa, const void *ab)
704 FcSortNode *a = *(FcSortNode **) aa;
705 FcSortNode *b = *(FcSortNode **) ab;
706 double *as = &a->score[0];
707 double *bs = &b->score[0];
708 double ad = 0, bd = 0;
711 i = NUM_MATCH_VALUES;
712 while (i-- && (ad = *as++) == (bd = *bs++))
714 return ad < bd ? -1 : ad > bd ? 1 : 0;
718 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
720 FcBool ret = FcFalse;
726 cs = FcCharSetCreate ();
733 FcSortNode *node = *n++;
734 FcBool adds_chars = FcFalse;
737 * Only fetch node charset if we'd need it
743 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
747 if (!FcCharSetMerge (cs, ncs, &adds_chars))
752 * If this font isn't a subset of the previous fonts,
755 if (!trim || adds_chars)
757 FcPatternReference (node->pattern);
758 if (FcDebug () & FC_DBG_MATCHV)
761 FcPatternPrint (node->pattern);
763 if (!FcFontSetAdd (fs, node->pattern))
765 FcPatternDestroy (node->pattern);
780 FcCharSetDestroy (cs);
786 FcFontSetSortDestroy (FcFontSet *fs)
788 FcFontSetDestroy (fs);
792 FcFontSetSort (FcConfig *config FC_UNUSED,
803 FcSortNode **nodeps, **nodep;
810 FcBool *patternLangSat;
813 assert (sets != NULL);
815 assert (result != NULL);
817 /* There are some implementation that relying on the result of
818 * "result" to check if the return value of FcFontSetSort
820 * So we should initialize it to the conservative way since
821 * this function doesn't return NULL anymore.
824 *result = FcResultNoMatch;
826 if (FcDebug () & FC_DBG_MATCH)
832 for (set = 0; set < nsets; set++)
840 return FcFontSetCreate ();
842 for (nPatternLang = 0;
843 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
848 nodes = malloc (nnodes * sizeof (FcSortNode) +
849 nnodes * sizeof (FcSortNode *) +
850 nPatternLang * sizeof (FcBool));
853 nodeps = (FcSortNode **) (nodes + nnodes);
854 patternLangSat = (FcBool *) (nodeps + nnodes);
858 for (set = 0; set < nsets; set++)
863 for (f = 0; f < s->nfont; f++)
865 if (FcDebug () & FC_DBG_MATCHV)
867 printf ("Font %d ", f);
868 FcPatternPrint (s->fonts[f]);
870 new->pattern = s->fonts[f];
871 if (!FcCompare (p, new->pattern, new->score, result))
873 if (FcDebug () & FC_DBG_MATCHV)
876 for (i = 0; i < NUM_MATCH_VALUES; i++)
878 printf (" %g", new->score[i]);
888 nnodes = new - nodes;
890 qsort (nodeps, nnodes, sizeof (FcSortNode *),
893 for (i = 0; i < nPatternLang; i++)
894 patternLangSat[i] = FcFalse;
896 for (f = 0; f < nnodes; f++)
898 FcBool satisfies = FcFalse;
900 * If this node matches any language, go check
901 * which ones and satisfy those entries
903 if (nodeps[f]->score[MATCH_LANG_INDEX] < 2000)
905 for (i = 0; i < nPatternLang; i++)
909 if (!patternLangSat[i] &&
910 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
911 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
913 double compare = FcCompareLang (&patternLang, &nodeLang);
914 if (compare >= 0 && compare < 2)
916 if (FcDebug () & FC_DBG_MATCHV)
921 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
922 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
923 printf ("Font %s:%s matches language %d\n", family, style, i);
925 patternLangSat[i] = FcTrue;
933 nodeps[f]->score[MATCH_LANG_INDEX] = 10000.0;
937 * Re-sort once the language issues have been settled
939 qsort (nodeps, nnodes, sizeof (FcSortNode *),
942 ret = FcFontSetCreate ();
946 if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
951 if (FcDebug() & FC_DBG_MATCH)
953 printf ("First font ");
954 FcPatternPrint (ret->fonts[0]);
957 *result = FcResultMatch;
962 FcFontSetDestroy (ret);
970 FcFontSort (FcConfig *config,
980 assert (result != NULL);
982 *result = FcResultNoMatch;
986 config = FcConfigGetCurrent ();
991 if (config->fonts[FcSetSystem])
992 sets[nsets++] = config->fonts[FcSetSystem];
993 if (config->fonts[FcSetApplication])
994 sets[nsets++] = config->fonts[FcSetApplication];
995 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
998 #include "fcaliastail.h"