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 (char *object, 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 (char *object, FcValue value1, FcValue value2)
64 if (value2.type != FcTypeString || value1.type != FcTypeString)
66 return (double) FcStrCmpIgnoreCase (value1.u.s, value2.u.s) != 0;
70 FcCompareFamily (char *object, FcValue value1, FcValue value2)
72 if (value2.type != FcTypeString || value1.type != FcTypeString)
74 return (double) FcStrCmpIgnoreBlanksAndCase (value1.u.s, value2.u.s) != 0;
78 FcCompareLang (char *object, FcValue value1, FcValue value2)
82 switch (value1.type) {
84 switch (value2.type) {
86 result = FcLangSetCompare (value1.u.l, value2.u.l);
89 result = FcLangSetHasLang (value1.u.l, value2.u.s);
96 switch (value2.type) {
98 result = FcLangSetHasLang (value2.u.l, value1.u.s);
101 result = FcLangCompare (value1.u.s, value2.u.s);
113 case FcLangDifferentCountry:
115 case FcLangDifferentLang:
122 FcCompareBool (char *object, FcValue value1, FcValue value2)
124 if (value2.type != FcTypeBool || value1.type != FcTypeBool)
126 return (double) value2.u.b != value1.u.b;
130 FcCompareCharSet (char *object, FcValue value1, FcValue value2)
132 if (value2.type != FcTypeCharSet || value1.type != FcTypeCharSet)
134 return (double) FcCharSetSubtractCount (value1.u.c, value2.u.c);
138 FcCompareSize (char *object, FcValue value1, FcValue value2)
142 switch (value1.type) {
152 switch (value2.type) {
170 typedef struct _FcMatcher {
172 double (*compare) (char *object, FcValue value1, FcValue value2);
177 * Order is significant, it defines the precedence of
178 * each value, earlier values are more significant than
181 static FcMatcher _FcMatchers [] = {
182 { FC_FOUNDRY, FcCompareString, 0, 0 },
183 #define MATCH_FOUNDRY 0
184 #define MATCH_FOUNDRY_INDEX 0
186 { FC_CHARSET, FcCompareCharSet, 1, 1 },
187 #define MATCH_CHARSET 1
188 #define MATCH_CHARSET_INDEX 1
190 { FC_FAMILY, FcCompareFamily, 2, 4 },
191 #define MATCH_FAMILY 2
192 #define MATCH_FAMILY_STRONG_INDEX 2
193 #define MATCH_FAMILY_WEAK_INDEX 4
195 { FC_LANG, FcCompareLang, 3, 3 },
197 #define MATCH_LANG_INDEX 3
199 { FC_SPACING, FcCompareNumber, 5, 5 },
200 #define MATCH_SPACING 4
201 #define MATCH_SPACING_INDEX 5
203 { FC_PIXEL_SIZE, FcCompareSize, 6, 6 },
204 #define MATCH_PIXEL_SIZE 5
205 #define MATCH_PIXEL_SIZE_INDEX 6
207 { FC_STYLE, FcCompareString, 7, 7 },
208 #define MATCH_STYLE 6
209 #define MATCH_STYLE_INDEX 7
211 { FC_SLANT, FcCompareNumber, 8, 8 },
212 #define MATCH_SLANT 7
213 #define MATCH_SLANT_INDEX 8
215 { FC_WEIGHT, FcCompareNumber, 9, 9 },
216 #define MATCH_WEIGHT 8
217 #define MATCH_WEIGHT_INDEX 9
219 { FC_WIDTH, FcCompareNumber, 10, 10 },
220 #define MATCH_WIDTH 9
221 #define MATCH_WIDTH_INDEX 10
223 { FC_ANTIALIAS, FcCompareBool, 11, 11 },
224 #define MATCH_ANTIALIAS 10
225 #define MATCH_ANTIALIAS_INDEX 11
227 { FC_RASTERIZER, FcCompareString, 12, 12 },
228 #define MATCH_RASTERIZER 11
229 #define MATCH_RASTERIZER_INDEX 12
231 { FC_OUTLINE, FcCompareBool, 13, 13 },
232 #define MATCH_OUTLINE 12
233 #define MATCH_OUTLINE_INDEX 13
235 { FC_FONTVERSION, FcCompareNumber, 14, 14 },
236 #define MATCH_FONTVERSION 13
237 #define MATCH_FONTVERSION_INDEX 14
240 #define NUM_MATCH_VALUES 15
243 FcCompareValueList (const char *object,
244 FcValueList *v1orig, /* pattern */
245 FcValueList *v2orig, /* target */
250 FcValueList *v1, *v2;
251 double v, best, bestStrong, bestWeak;
256 * Locate the possible matching entry by examining the
257 * first few characters in object
260 switch (FcToLower (object[0])) {
262 switch (FcToLower (object[1])) {
264 switch (FcToLower (object[2])) {
266 i = MATCH_FOUNDRY; break;
268 i = MATCH_FONTVERSION; break;
272 i = MATCH_FAMILY; break;
276 i = MATCH_CHARSET; break;
278 i = MATCH_ANTIALIAS; break;
280 i = MATCH_LANG; break;
282 switch (FcToLower (object[1])) {
284 i = MATCH_SPACING; break;
286 i = MATCH_STYLE; break;
288 i = MATCH_SLANT; break;
292 i = MATCH_PIXEL_SIZE; break;
294 switch (FcToLower (object[1])) {
296 i = MATCH_WIDTH; break;
298 i = MATCH_WEIGHT; break;
302 i = MATCH_RASTERIZER; break;
304 i = MATCH_OUTLINE; break;
307 FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
308 (FcChar8 *) object) != 0)
311 *bestValue = v2orig->value;
315 for (i = 0; i < NUM_MATCHER; i++)
317 if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
321 if (i == NUM_MATCHER)
324 *bestValue = v2orig->value;
332 for (v1 = v1orig; v1; v1 = v1->next)
334 for (v2 = v2orig; v2; v2 = v2->next)
336 v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
341 *result = FcResultTypeMismatch;
344 if (FcDebug () & FC_DBG_MATCHV)
345 printf (" v %g j %d ", v, j);
350 *bestValue = v2->value;
353 if (v1->binding == FcValueBindingStrong)
366 if (FcDebug () & FC_DBG_MATCHV)
368 printf (" %s: %g ", object, best);
369 FcValueListPrint (v1orig);
371 FcValueListPrint (v2orig);
376 int weak = _FcMatchers[i].weak;
377 int strong = _FcMatchers[i].strong;
379 value[strong] += best;
382 value[weak] += bestWeak;
383 value[strong] += bestStrong;
390 * Return a value indicating the distance between the two lists of
395 FcCompare (FcPattern *pat,
402 for (i = 0; i < NUM_MATCH_VALUES; i++)
407 while (i1 < pat->num && i2 < fnt->num)
409 i = strcmp (pat->elts[i1].object, fnt->elts[i2].object);
416 if (!FcCompareValueList (pat->elts[i1].object,
417 pat->elts[i1].values,
418 fnt->elts[i2].values,
429 for (i1 = 0; i1 < pat->num; i1++)
431 for (i2 = 0; i2 < fnt->num; i2++)
433 if (!strcmp (pat->elts[i1].object, fnt->elts[i2].object))
444 FcFontRenderPrepare (FcConfig *config,
450 FcPatternElt *fe, *pe;
454 new = FcPatternCreate ();
457 for (i = 0; i < font->num; i++)
460 pe = FcPatternFindElt (pat, fe->object);
463 if (!FcCompareValueList (pe->object, pe->values,
464 fe->values, &v, 0, &result))
466 FcPatternDestroy (new);
471 v = fe->values->value;
472 FcPatternAdd (new, fe->object, v, FcFalse);
474 for (i = 0; i < pat->num; i++)
477 fe = FcPatternFindElt (font, pe->object);
479 FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
481 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
486 FcFontSetMatch (FcConfig *config,
492 double score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
499 for (i = 0; i < NUM_MATCH_VALUES; i++)
502 if (FcDebug () & FC_DBG_MATCH)
509 config = FcConfigGetCurrent ();
512 *result = FcResultOutOfMemory;
516 for (set = 0; set < nsets; set++)
521 for (f = 0; f < s->nfont; f++)
523 if (FcDebug () & FC_DBG_MATCHV)
525 printf ("Font %d ", f);
526 FcPatternPrint (s->fonts[f]);
528 if (!FcCompare (p, s->fonts[f], score, result))
530 if (FcDebug () & FC_DBG_MATCHV)
533 for (i = 0; i < NUM_MATCH_VALUES; i++)
535 printf (" %g", score[i]);
539 for (i = 0; i < NUM_MATCH_VALUES; i++)
541 if (best && bestscore[i] < score[i])
543 if (!best || score[i] < bestscore[i])
545 for (i = 0; i < NUM_MATCH_VALUES; i++)
546 bestscore[i] = score[i];
553 if (FcDebug () & FC_DBG_MATCH)
555 printf ("Best score");
556 for (i = 0; i < NUM_MATCH_VALUES; i++)
557 printf (" %g", bestscore[i]);
558 FcPatternPrint (best);
562 *result = FcResultNoMatch;
565 return FcFontRenderPrepare (config, p, best);
569 FcFontMatch (FcConfig *config,
578 config = FcConfigGetCurrent ();
583 if (config->fonts[FcSetSystem])
584 sets[nsets++] = config->fonts[FcSetSystem];
585 if (config->fonts[FcSetApplication])
586 sets[nsets++] = config->fonts[FcSetApplication];
587 return FcFontSetMatch (config, sets, nsets, p, result);
590 typedef struct _FcSortNode {
592 double score[NUM_MATCH_VALUES];
596 FcSortCompare (const void *aa, const void *ab)
598 FcSortNode *a = *(FcSortNode **) aa;
599 FcSortNode *b = *(FcSortNode **) ab;
600 double *as = &a->score[0];
601 double *bs = &b->score[0];
602 double ad = 0, bd = 0;
605 i = NUM_MATCH_VALUES;
606 while (i-- && (ad = *as++) == (bd = *bs++))
608 return ad < bd ? -1 : ad > bd ? 1 : 0;
612 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
620 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
624 * If this font isn't a subset of the previous fonts,
627 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
631 ncs = FcCharSetUnion (ncs, *cs);
634 FcCharSetDestroy (*cs);
637 ncs = FcCharSetCopy (ncs);
639 FcPatternReference (node->pattern);
640 if (FcDebug () & FC_DBG_MATCH)
643 FcPatternPrint (node->pattern);
645 if (!FcFontSetAdd (fs, node->pattern))
647 FcPatternDestroy (node->pattern);
657 FcFontSetSortDestroy (FcFontSet *fs)
659 FcFontSetDestroy (fs);
663 FcFontSetSort (FcConfig *config,
674 FcSortNode **nodeps, **nodep;
682 FcBool *patternLangSat;
685 if (FcDebug () & FC_DBG_MATCH)
691 for (set = 0; set < nsets; set++)
701 for (nPatternLang = 0;
702 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
707 nodes = malloc (nnodes * sizeof (FcSortNode) +
708 nnodes * sizeof (FcSortNode *) +
709 nPatternLang * sizeof (FcBool));
712 nodeps = (FcSortNode **) (nodes + nnodes);
713 patternLangSat = (FcBool *) (nodeps + nnodes);
717 for (set = 0; set < nsets; set++)
722 for (f = 0; f < s->nfont; f++)
724 if (FcDebug () & FC_DBG_MATCHV)
726 printf ("Font %d ", f);
727 FcPatternPrint (s->fonts[f]);
729 new->pattern = s->fonts[f];
730 if (!FcCompare (p, new->pattern, new->score, result))
732 if (FcDebug () & FC_DBG_MATCHV)
735 for (i = 0; i < NUM_MATCH_VALUES; i++)
737 printf (" %g", new->score[i]);
747 nnodes = new - nodes;
749 qsort (nodeps, nnodes, sizeof (FcSortNode *),
752 for (i = 0; i < nPatternLang; i++)
753 patternLangSat[i] = FcFalse;
755 for (f = 0; f < nnodes; f++)
757 FcBool satisfies = FcFalse;
759 * If this node matches any language, go check
760 * which ones and satisfy those entries
762 if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
764 for (i = 0; i < nPatternLang; i++)
768 if (!patternLangSat[i] &&
769 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
770 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
772 double compare = FcCompareLang (FC_LANG, patternLang,
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] = 1000.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))
814 FcCharSetDestroy (cs);
822 FcCharSetDestroy (cs);
823 FcFontSetDestroy (ret);
831 FcFontSort (FcConfig *config,
842 config = FcConfigGetCurrent ();
847 if (config->fonts[FcSetSystem])
848 sets[nsets++] = config->fonts[FcSetSystem];
849 if (config->fonts[FcSetApplication])
850 sets[nsets++] = config->fonts[FcSetApplication];
851 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);