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 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) &&
76 *v1_string != ' ' && *v2_string != ' ')
79 return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
83 FcCompareLang (FcValue *v1, FcValue *v2)
86 FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
88 switch (value1.type) {
90 switch (value2.type) {
92 result = FcLangSetCompare (value1.u.l, value2.u.l);
95 result = FcLangSetHasLang (value1.u.l,
103 switch (value2.type) {
105 result = FcLangSetHasLang (value2.u.l, value1.u.s);
108 result = FcLangCompare (value1.u.s,
121 case FcLangDifferentCountry:
123 case FcLangDifferentLang:
130 FcCompareBool (FcValue *v1, FcValue *v2)
132 if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
134 return (double) v2->u.b != v1->u.b;
138 FcCompareCharSet (FcValue *v1, FcValue *v2)
140 return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
144 FcCompareSize (FcValue *value1, FcValue *value2)
148 switch (value1->type) {
158 switch (value2->type) {
176 typedef struct _FcMatcher {
178 double (*compare) (FcValue *value1, FcValue *value2);
183 * Order is significant, it defines the precedence of
184 * each value, earlier values are more significant than
187 static FcMatcher _FcMatchers [] = {
188 { FC_FOUNDRY_OBJECT, FcCompareString, 0, 0 },
189 #define MATCH_FOUNDRY 0
190 #define MATCH_FOUNDRY_INDEX 0
192 { FC_CHARSET_OBJECT, FcCompareCharSet, 1, 1 },
193 #define MATCH_CHARSET 1
194 #define MATCH_CHARSET_INDEX 1
196 { FC_FAMILY_OBJECT, FcCompareFamily, 2, 4 },
197 #define MATCH_FAMILY 2
198 #define MATCH_FAMILY_STRONG_INDEX 2
199 #define MATCH_FAMILY_WEAK_INDEX 4
201 { FC_LANG_OBJECT, FcCompareLang, 3, 3 },
203 #define MATCH_LANG_INDEX 3
205 { FC_SPACING_OBJECT, FcCompareNumber, 5, 5 },
206 #define MATCH_SPACING 4
207 #define MATCH_SPACING_INDEX 5
209 { FC_PIXEL_SIZE_OBJECT, FcCompareSize, 6, 6 },
210 #define MATCH_PIXEL_SIZE 5
211 #define MATCH_PIXEL_SIZE_INDEX 6
213 { FC_STYLE_OBJECT, FcCompareString, 7, 7 },
214 #define MATCH_STYLE 6
215 #define MATCH_STYLE_INDEX 7
217 { FC_SLANT_OBJECT, FcCompareNumber, 8, 8 },
218 #define MATCH_SLANT 7
219 #define MATCH_SLANT_INDEX 8
221 { FC_WEIGHT_OBJECT, FcCompareNumber, 9, 9 },
222 #define MATCH_WEIGHT 8
223 #define MATCH_WEIGHT_INDEX 9
225 { FC_WIDTH_OBJECT, FcCompareNumber, 10, 10 },
226 #define MATCH_WIDTH 9
227 #define MATCH_WIDTH_INDEX 10
229 { FC_DECORATIVE_OBJECT, FcCompareBool, 11, 11 },
230 #define MATCH_DECORATIVE 10
231 #define MATCH_DECORATIVE_INDEX 11
233 { FC_ANTIALIAS_OBJECT, FcCompareBool, 12, 12 },
234 #define MATCH_ANTIALIAS 11
235 #define MATCH_ANTIALIAS_INDEX 12
237 { FC_RASTERIZER_OBJECT, FcCompareString, 13, 13 },
238 #define MATCH_RASTERIZER 12
239 #define MATCH_RASTERIZER_INDEX 13
241 { FC_OUTLINE_OBJECT, FcCompareBool, 14, 14 },
242 #define MATCH_OUTLINE 13
243 #define MATCH_OUTLINE_INDEX 14
245 { FC_FONTVERSION_OBJECT, FcCompareNumber, 15, 15 },
246 #define MATCH_FONTVERSION 14
247 #define MATCH_FONTVERSION_INDEX 15
250 #define NUM_MATCH_VALUES 16
253 FcObjectToMatcher (FcObject object)
259 case FC_FOUNDRY_OBJECT:
260 i = MATCH_FOUNDRY; break;
261 case FC_FONTVERSION_OBJECT:
262 i = MATCH_FONTVERSION; break;
263 case FC_FAMILY_OBJECT:
264 i = MATCH_FAMILY; break;
265 case FC_CHARSET_OBJECT:
266 i = MATCH_CHARSET; break;
267 case FC_ANTIALIAS_OBJECT:
268 i = MATCH_ANTIALIAS; break;
270 i = MATCH_LANG; break;
271 case FC_SPACING_OBJECT:
272 i = MATCH_SPACING; break;
273 case FC_STYLE_OBJECT:
274 i = MATCH_STYLE; break;
275 case FC_SLANT_OBJECT:
276 i = MATCH_SLANT; break;
277 case FC_PIXEL_SIZE_OBJECT:
278 i = MATCH_PIXEL_SIZE; break;
279 case FC_WIDTH_OBJECT:
280 i = MATCH_WIDTH; break;
281 case FC_WEIGHT_OBJECT:
282 i = MATCH_WEIGHT; break;
283 case FC_RASTERIZER_OBJECT:
284 i = MATCH_RASTERIZER; break;
285 case FC_OUTLINE_OBJECT:
286 i = MATCH_OUTLINE; break;
287 case FC_DECORATIVE_OBJECT:
288 i = MATCH_DECORATIVE; break;
294 return _FcMatchers+i;
298 FcCompareValueList (FcObject object,
299 FcValueListPtr v1orig, /* pattern */
300 FcValueListPtr v2orig, /* target */
305 FcValueListPtr v1, v2;
306 double v, best, bestStrong, bestWeak;
308 FcMatcher *match = FcObjectToMatcher(object);
313 *bestValue = FcValueCanonicalize(&v2orig->value);
321 for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
323 for (v2 = v2orig; v2; v2 = FcValueListNext(v2))
325 v = (match->compare) (&v1->value, &v2->value);
328 *result = FcResultTypeMismatch;
335 *bestValue = FcValueCanonicalize(&v2->value);
338 if (v1->binding == FcValueBindingStrong)
351 if (FcDebug () & FC_DBG_MATCHV)
353 printf (" %s: %g ", FcObjectName (object), best);
354 FcValueListPrint (v1orig);
356 FcValueListPrint (v2orig);
361 int weak = match->weak;
362 int strong = match->strong;
364 value[strong] += best;
367 value[weak] += bestWeak;
368 value[strong] += bestStrong;
375 * Return a value indicating the distance between the two lists of
380 FcCompare (FcPattern *pat,
387 for (i = 0; i < NUM_MATCH_VALUES; i++)
392 while (i1 < pat->num && i2 < fnt->num)
394 FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
395 FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
397 i = FcObjectCompare(elt_i1->object, elt_i2->object);
404 if (!FcCompareValueList (elt_i1->object,
405 FcPatternEltValues(elt_i1),
406 FcPatternEltValues(elt_i2),
417 FcFontRenderPrepare (FcConfig *config,
423 FcPatternElt *fe, *pe;
427 new = FcPatternCreate ();
430 for (i = 0; i < font->num; i++)
432 fe = &FcPatternElts(font)[i];
433 pe = FcPatternObjectFindElt (pat, fe->object);
436 if (!FcCompareValueList (pe->object, FcPatternEltValues(pe),
437 FcPatternEltValues(fe), &v, 0, &result))
439 FcPatternDestroy (new);
444 v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
445 FcPatternObjectAdd (new, fe->object, v, FcFalse);
447 for (i = 0; i < pat->num; i++)
449 pe = &FcPatternElts(pat)[i];
450 fe = FcPatternObjectFindElt (font, pe->object);
453 v = FcValueCanonicalize(&FcPatternEltValues(pe)->value);
454 FcPatternObjectAdd (new, pe->object, v, FcTrue);
458 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
463 FcFontSetMatchInternal (FcConfig *config,
469 double score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
476 for (i = 0; i < NUM_MATCH_VALUES; i++)
479 if (FcDebug () & FC_DBG_MATCH)
484 for (set = 0; set < nsets; set++)
489 for (f = 0; f < s->nfont; f++)
491 if (FcDebug () & FC_DBG_MATCHV)
493 printf ("Font %d ", f);
494 FcPatternPrint (s->fonts[f]);
496 if (!FcCompare (p, s->fonts[f], score, result))
498 if (FcDebug () & FC_DBG_MATCHV)
501 for (i = 0; i < NUM_MATCH_VALUES; i++)
503 printf (" %g", score[i]);
507 for (i = 0; i < NUM_MATCH_VALUES; i++)
509 if (best && bestscore[i] < score[i])
511 if (!best || score[i] < bestscore[i])
513 for (i = 0; i < NUM_MATCH_VALUES; i++)
514 bestscore[i] = score[i];
521 if (FcDebug () & FC_DBG_MATCH)
523 printf ("Best score");
524 for (i = 0; i < NUM_MATCH_VALUES; i++)
525 printf (" %g", bestscore[i]);
527 FcPatternPrint (best);
531 *result = FcResultNoMatch;
538 FcFontSetMatch (FcConfig *config,
548 config = FcConfigGetCurrent ();
552 best = FcFontSetMatchInternal (config, sets, nsets, p, result);
554 return FcFontRenderPrepare (config, p, best);
560 FcFontMatch (FcConfig *config,
570 config = FcConfigGetCurrent ();
575 if (config->fonts[FcSetSystem])
576 sets[nsets++] = config->fonts[FcSetSystem];
577 if (config->fonts[FcSetApplication])
578 sets[nsets++] = config->fonts[FcSetApplication];
580 best = FcFontSetMatchInternal (config, sets, nsets, p, result);
582 return FcFontRenderPrepare (config, p, best);
587 typedef struct _FcSortNode {
589 double score[NUM_MATCH_VALUES];
593 FcSortCompare (const void *aa, const void *ab)
595 FcSortNode *a = *(FcSortNode **) aa;
596 FcSortNode *b = *(FcSortNode **) ab;
597 double *as = &a->score[0];
598 double *bs = &b->score[0];
599 double ad = 0, bd = 0;
602 i = NUM_MATCH_VALUES;
603 while (i-- && (ad = *as++) == (bd = *bs++))
605 return ad < bd ? -1 : ad > bd ? 1 : 0;
609 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
619 * Only fetch node charset if we'd need it
621 if (trim || build_cs)
623 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
629 * If this font isn't a subset of the previous fonts,
632 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
634 if (trim || build_cs)
636 *cs = FcCharSetMerge (*cs, ncs);
641 FcPatternReference (node->pattern);
642 if (FcDebug () & FC_DBG_MATCHV)
645 FcPatternPrint (node->pattern);
647 if (!FcFontSetAdd (fs, node->pattern))
649 FcPatternDestroy (node->pattern);
658 FcFontSetSortDestroy (FcFontSet *fs)
660 FcFontSetDestroy (fs);
664 FcFontSetSort (FcConfig *config,
675 FcSortNode **nodeps, **nodep;
683 FcBool *patternLangSat;
686 if (FcDebug () & FC_DBG_MATCH)
692 for (set = 0; set < nsets; set++)
702 for (nPatternLang = 0;
703 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
708 nodes = malloc (nnodes * sizeof (FcSortNode) +
709 nnodes * sizeof (FcSortNode *) +
710 nPatternLang * sizeof (FcBool));
713 nodeps = (FcSortNode **) (nodes + nnodes);
714 patternLangSat = (FcBool *) (nodeps + nnodes);
718 for (set = 0; set < nsets; set++)
723 for (f = 0; f < s->nfont; f++)
725 if (FcDebug () & FC_DBG_MATCHV)
727 printf ("Font %d ", f);
728 FcPatternPrint (s->fonts[f]);
730 new->pattern = s->fonts[f];
731 if (!FcCompare (p, new->pattern, new->score, result))
733 if (FcDebug () & FC_DBG_MATCHV)
736 for (i = 0; i < NUM_MATCH_VALUES; i++)
738 printf (" %g", new->score[i]);
748 nnodes = new - nodes;
750 qsort (nodeps, nnodes, sizeof (FcSortNode *),
753 for (i = 0; i < nPatternLang; i++)
754 patternLangSat[i] = FcFalse;
756 for (f = 0; f < nnodes; f++)
758 FcBool satisfies = FcFalse;
760 * If this node matches any language, go check
761 * which ones and satisfy those entries
763 if (nodeps[f]->score[MATCH_LANG_INDEX] < 200)
765 for (i = 0; i < nPatternLang; i++)
769 if (!patternLangSat[i] &&
770 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
771 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
773 double compare = FcCompareLang (&patternLang, &nodeLang);
774 if (compare >= 0 && compare < 2)
776 if (FcDebug () & FC_DBG_MATCHV)
781 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
782 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
783 printf ("Font %s:%s matches language %d\n", family, style, i);
785 patternLangSat[i] = FcTrue;
793 nodeps[f]->score[MATCH_LANG_INDEX] = 10000.0;
797 * Re-sort once the language issues have been settled
799 qsort (nodeps, nnodes, sizeof (FcSortNode *),
802 ret = FcFontSetCreate ();
808 if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
816 FcCharSetDestroy (cs);
821 if (FcDebug() & FC_DBG_MATCH)
823 printf ("First font ");
824 FcPatternPrint (ret->fonts[0]);
830 FcCharSetDestroy (cs);
831 FcFontSetDestroy (ret);
839 FcFontSort (FcConfig *config,
850 config = FcConfigGetCurrent ();
855 if (config->fonts[FcSetSystem])
856 sets[nsets++] = config->fonts[FcSetSystem];
857 if (config->fonts[FcSetApplication])
858 sets[nsets++] = config->fonts[FcSetApplication];
859 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
862 #include "fcaliastail.h"