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 FcObjectPtr objectPtr;
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, 0, FcCompareString, 0, 0 },
189 #define MATCH_FOUNDRY 0
190 #define MATCH_FOUNDRY_INDEX 0
192 { FC_CHARSET, 0, FcCompareCharSet, 1, 1 },
193 #define MATCH_CHARSET 1
194 #define MATCH_CHARSET_INDEX 1
196 { FC_FAMILY, 0, 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, 0, FcCompareLang, 3, 3 },
203 #define MATCH_LANG_INDEX 3
205 { FC_SPACING, 0, FcCompareNumber, 5, 5 },
206 #define MATCH_SPACING 4
207 #define MATCH_SPACING_INDEX 5
209 { FC_PIXEL_SIZE, 0, FcCompareSize, 6, 6 },
210 #define MATCH_PIXEL_SIZE 5
211 #define MATCH_PIXEL_SIZE_INDEX 6
213 { FC_STYLE, 0, FcCompareString, 7, 7 },
214 #define MATCH_STYLE 6
215 #define MATCH_STYLE_INDEX 7
217 { FC_SLANT, 0, FcCompareNumber, 8, 8 },
218 #define MATCH_SLANT 7
219 #define MATCH_SLANT_INDEX 8
221 { FC_WEIGHT, 0, FcCompareNumber, 9, 9 },
222 #define MATCH_WEIGHT 8
223 #define MATCH_WEIGHT_INDEX 9
225 { FC_WIDTH, 0, FcCompareNumber, 10, 10 },
226 #define MATCH_WIDTH 9
227 #define MATCH_WIDTH_INDEX 10
229 { FC_ANTIALIAS, 0, FcCompareBool, 11, 11 },
230 #define MATCH_ANTIALIAS 10
231 #define MATCH_ANTIALIAS_INDEX 11
233 { FC_RASTERIZER, 0, FcCompareString, 12, 12 },
234 #define MATCH_RASTERIZER 11
235 #define MATCH_RASTERIZER_INDEX 12
237 { FC_OUTLINE, 0, FcCompareBool, 13, 13 },
238 #define MATCH_OUTLINE 12
239 #define MATCH_OUTLINE_INDEX 13
241 { FC_FONTVERSION, 0, FcCompareNumber, 14, 14 },
242 #define MATCH_FONTVERSION 13
243 #define MATCH_FONTVERSION_INDEX 14
246 #define NUM_MATCH_VALUES 15
248 static FcBool matchObjectPtrsInit = FcFalse;
251 FcMatchObjectPtrsInit (void)
253 _FcMatchers[MATCH_FOUNDRY].objectPtr = FcObjectToPtr(FC_FOUNDRY);
254 _FcMatchers[MATCH_CHARSET].objectPtr = FcObjectToPtr(FC_CHARSET);
255 _FcMatchers[MATCH_FAMILY].objectPtr = FcObjectToPtr(FC_FAMILY);
256 _FcMatchers[MATCH_LANG].objectPtr = FcObjectToPtr(FC_LANG);
257 _FcMatchers[MATCH_SPACING].objectPtr = FcObjectToPtr(FC_SPACING);
258 _FcMatchers[MATCH_PIXEL_SIZE].objectPtr = FcObjectToPtr(FC_PIXEL_SIZE);
259 _FcMatchers[MATCH_STYLE].objectPtr = FcObjectToPtr(FC_STYLE);
260 _FcMatchers[MATCH_SLANT].objectPtr = FcObjectToPtr(FC_SLANT);
261 _FcMatchers[MATCH_WEIGHT].objectPtr = FcObjectToPtr(FC_WEIGHT);
262 _FcMatchers[MATCH_WIDTH].objectPtr = FcObjectToPtr(FC_WIDTH);
263 _FcMatchers[MATCH_ANTIALIAS].objectPtr = FcObjectToPtr(FC_ANTIALIAS);
264 _FcMatchers[MATCH_RASTERIZER].objectPtr = FcObjectToPtr(FC_RASTERIZER);
265 _FcMatchers[MATCH_OUTLINE].objectPtr = FcObjectToPtr(FC_OUTLINE);
266 _FcMatchers[MATCH_FONTVERSION].objectPtr = FcObjectToPtr(FC_FONTVERSION);
267 matchObjectPtrsInit = FcTrue;
271 FcObjectPtrToMatcher (FcObjectPtr o)
274 const char *object = FcObjectPtrU(o);
283 i = MATCH_FOUNDRY; break;
285 i = MATCH_FONTVERSION; break;
289 i = MATCH_FAMILY; break;
293 i = MATCH_CHARSET; break;
295 i = MATCH_ANTIALIAS; break;
297 i = MATCH_LANG; break;
301 i = MATCH_SPACING; break;
303 i = MATCH_STYLE; break;
305 i = MATCH_SLANT; break;
309 i = MATCH_PIXEL_SIZE; break;
313 i = MATCH_WIDTH; break;
315 i = MATCH_WEIGHT; break;
319 i = MATCH_RASTERIZER; break;
321 i = MATCH_OUTLINE; break;
327 if (!matchObjectPtrsInit)
328 FcMatchObjectPtrsInit();
330 if (o != _FcMatchers[i].objectPtr)
333 return _FcMatchers+i;
337 FcCompareValueList (FcObjectPtr o,
338 FcValueListPtr v1orig, /* pattern */
339 FcValueListPtr v2orig, /* target */
344 FcValueListPtr v1, v2;
345 FcValueList *v1_ptrU, *v2_ptrU;
346 double v, best, bestStrong, bestWeak;
348 const char *object = FcObjectPtrU(o);
349 FcMatcher *match = FcObjectPtrToMatcher(o);
354 *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
362 for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
363 v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1))
365 for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); v2_ptrU;
366 v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
368 v = (match->compare) (&v1_ptrU->value, &v2_ptrU->value);
371 *result = FcResultTypeMismatch;
378 *bestValue = FcValueCanonicalize(&v2_ptrU->value);
381 if (v1_ptrU->binding == FcValueBindingStrong)
394 if (FcDebug () & FC_DBG_MATCHV)
396 printf (" %s: %g ", object, best);
397 FcValueListPrint (v1orig);
399 FcValueListPrint (v2orig);
404 int weak = match->weak;
405 int strong = match->strong;
407 value[strong] += best;
410 value[weak] += bestWeak;
411 value[strong] += bestStrong;
418 * Return a value indicating the distance between the two lists of
423 FcCompare (FcPattern *pat,
430 for (i = 0; i < NUM_MATCH_VALUES; i++)
435 while (i1 < pat->num && i2 < fnt->num)
437 FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
438 FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
440 i = FcObjectPtrCompare(elt_i1->object, elt_i2->object);
447 if (!FcCompareValueList (elt_i1->object,
448 elt_i1->values, elt_i2->values,
459 FcFontRenderPrepare (FcConfig *config,
465 FcPatternElt *fe, *pe;
469 new = FcPatternCreate ();
472 for (i = 0; i < font->num; i++)
474 fe = FcPatternEltU(font->elts)+i;
475 pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
478 if (!FcCompareValueList (pe->object, pe->values,
479 fe->values, &v, 0, &result))
481 FcPatternDestroy (new);
486 v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
487 FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
489 for (i = 0; i < pat->num; i++)
491 pe = FcPatternEltU(pat->elts)+i;
492 fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
494 FcPatternAdd (new, FcObjectPtrU(pe->object),
495 FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
498 if (FcPatternFindElt (font, FC_FILE))
499 FcPatternTransferFullFname (new, font);
501 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
506 FcFontSetMatch (FcConfig *config,
523 FcMatcher *strong_matchers[NUM_MATCH_VALUES];
524 FcMatcher *weak_matchers[NUM_MATCH_VALUES];
525 FcPatternElt *pat_elts[NUM_MATCH_VALUES];
530 if (!nsets || !sets || !p)
532 *result = FcResultNoMatch;
536 if (FcDebug () & FC_DBG_MATCH)
543 config = FcConfigGetCurrent ();
546 *result = FcResultOutOfMemory;
551 sets_offset = (int *)calloc(nsets, sizeof (int));
554 for (set = 0; set < nsets; ++set)
556 sets_offset[set] = nfonts;
558 nfonts += sets[set]->nfont;
563 match_blocked = (int*)calloc(nfonts, sizeof(int));
565 /* Find out all necessary matchers first, so we don't need to find them
569 memset(strong_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
570 memset(weak_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
571 memset(pat_elts, 0, sizeof (FcPatternElt*) * NUM_MATCH_VALUES);
573 for (pat_elt = 0; pat_elt < p->num; ++pat_elt)
575 matcher = FcObjectPtrToMatcher
576 ((FcPatternEltU(p->elts)+pat_elt)->object);
579 strong_matchers[matcher->strong] = matcher;
580 weak_matchers[matcher->weak] = matcher;
581 pat_elts [matcher->strong] = pat_elts [matcher->weak] =
582 (FcPatternEltU(p->elts)+pat_elt);
586 /* The old algorithm checked if each font beat 'best',
587 * scanning all of the value lists for all of the pattern elts. */
588 /* This algorithm checks each font on a element-by-element basis
589 * and blocks fonts that have already lost on some element from
590 * further consideration from being best. Basically, we've
591 * swapped the order of loops and short-circuited fonts that
592 * are out of contention right away.
593 * This saves a lot of time! */
596 for (scoring_index = 0; scoring_index < NUM_MATCH_VALUES; ++scoring_index)
599 FcValueList *v1_ptrU;
602 if (!strong_matchers [scoring_index] && !weak_matchers [scoring_index])
605 for (v1 = pat_elts[scoring_index]->values, v1_ptrU = FcValueListPtrU(v1);
607 v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1), ++v1_offset)
609 matcher = (v1_ptrU->binding == FcValueBindingWeak) ?
610 weak_matchers[scoring_index] : strong_matchers[scoring_index];
612 if (!matcher) continue;
616 if (FcDebug () & FC_DBG_MATCHV)
618 printf("Scoring Index %d, Value %d: %d(%d) fonts left\n",
619 scoring_index, v1_offset, fonts_left, nfonts);
622 for (set = 0; set < nsets; ++set)
627 /* All fonts before block_start should have been knocked out. */
628 for (f = (block_start > sets_offset[set]) ? (block_start - sets_offset[set]) : 0;
632 FcPatternElt *cand_elts;
634 if (match_blocked[f + sets_offset[set]] == 1)
638 cand_elts = FcPatternEltU(s->fonts[f]->elts);
640 /* Look for the appropriate element in this candidate
641 * pattern 'f' and evaluate its score wrt 'p'. */
642 for (cand_elt = 0; cand_elt < s->fonts[f]->num; ++cand_elt)
644 if (cand_elts[cand_elt].object == pat_elts[scoring_index]->object)
647 FcValueList *v2_ptrU;
649 for (v2 = cand_elts[cand_elt].values, v2_ptrU = FcValueListPtrU(v2);
651 v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
653 double v = (matcher->compare)(&v1_ptrU->value, &v2_ptrU->value);
657 *result = FcResultTypeMismatch;
658 free (match_blocked);
663 /* I'm actually kind of surprised that
664 * this isn't v + 100 * v1_offset. -PL */
665 v = v * 100 + v1_offset;
666 /* The old patch said score += v, which
667 * seems to be wrong when you have
668 * multiple matchers. This takes the
669 * best score it can find for that font. */
676 /* We had no matching, just try the next one */
679 match_blocked[f + sets_offset[set]] = 2;
682 match_blocked[f + sets_offset[set]] = 0;
683 /* If there's a previous champion, and current score
684 * beats previous best score, on this element, then
685 * knock out the previous champion and anything
686 * else that we would have visited previous to f;
687 * clearly anything previous to f would have been
688 * less than f on this score. */
689 if (!best || score < bestscore)
694 for (b = block_start; b < f + sets_offset[set]; ++b)
695 if (!match_blocked[b])
697 match_blocked[b] = 1;
704 /* This kills too many fonts, unfortunately. */
705 /* block_start = f + sets_offset[set]; */
708 /* If f loses, then it's out too. */
709 if (best && score > bestscore)
711 match_blocked[f + sets_offset[set]] = 1;
715 /* If there is only 1 font left and the best is set,
716 * then just return this font
718 if (fonts_left == 1 && best)
721 /* Otherwise, f is equal to best on this element.
722 * Carry on to next pattern element. */
725 if ((FcDebug () & FC_DBG_MATCHV) && best)
727 printf ("Best match (scoring index %d) candidate %d ", scoring_index, block_start);
728 FcPatternPrint (best);
734 free (match_blocked);
737 if ((FcDebug () & FC_DBG_MATCH) && best)
739 printf ("Best match (scoring index %d) %d ", scoring_index, block_start);
740 FcPatternPrint (best);
744 *result = FcResultNoMatch;
747 return FcFontRenderPrepare (config, p, best);
751 FcFontMatch (FcConfig *config,
760 config = FcConfigGetCurrent ();
765 if (config->fonts[FcSetSystem])
766 sets[nsets++] = config->fonts[FcSetSystem];
767 if (config->fonts[FcSetApplication])
768 sets[nsets++] = config->fonts[FcSetApplication];
769 return FcFontSetMatch (config, sets, nsets, p, result);
772 typedef struct _FcSortNode {
774 double score[NUM_MATCH_VALUES];
778 FcSortCompare (const void *aa, const void *ab)
780 FcSortNode *a = *(FcSortNode **) aa;
781 FcSortNode *b = *(FcSortNode **) ab;
782 double *as = &a->score[0];
783 double *bs = &b->score[0];
784 double ad = 0, bd = 0;
787 i = NUM_MATCH_VALUES;
788 while (i-- && (ad = *as++) == (bd = *bs++))
790 return ad < bd ? -1 : ad > bd ? 1 : 0;
794 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
802 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
806 * If this font isn't a subset of the previous fonts,
809 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
811 if (trim || build_cs)
815 ncs = FcCharSetUnion (ncs, *cs);
818 FcCharSetDestroy (*cs);
821 ncs = FcCharSetCopy (ncs);
825 FcPatternReference (node->pattern);
826 if (FcDebug () & FC_DBG_MATCH)
829 FcPatternPrint (node->pattern);
831 if (!FcFontSetAdd (fs, node->pattern))
833 FcPatternDestroy (node->pattern);
843 FcFontSetSortDestroy (FcFontSet *fs)
845 FcFontSetDestroy (fs);
849 FcFontSetSort (FcConfig *config,
860 FcSortNode **nodeps, **nodep;
868 FcBool *patternLangSat;
871 if (FcDebug () & FC_DBG_MATCH)
877 for (set = 0; set < nsets; set++)
887 for (nPatternLang = 0;
888 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
893 nodes = malloc (nnodes * sizeof (FcSortNode) +
894 nnodes * sizeof (FcSortNode *) +
895 nPatternLang * sizeof (FcBool));
898 nodeps = (FcSortNode **) (nodes + nnodes);
899 patternLangSat = (FcBool *) (nodeps + nnodes);
903 for (set = 0; set < nsets; set++)
908 for (f = 0; f < s->nfont; f++)
910 if (FcDebug () & FC_DBG_MATCHV)
912 printf ("Font %d ", f);
913 FcPatternPrint (s->fonts[f]);
915 new->pattern = s->fonts[f];
916 if (!FcCompare (p, new->pattern, new->score, result))
918 if (FcDebug () & FC_DBG_MATCHV)
921 for (i = 0; i < NUM_MATCH_VALUES; i++)
923 printf (" %g", new->score[i]);
933 nnodes = new - nodes;
935 qsort (nodeps, nnodes, sizeof (FcSortNode *),
938 for (i = 0; i < nPatternLang; i++)
939 patternLangSat[i] = FcFalse;
941 for (f = 0; f < nnodes; f++)
943 FcBool satisfies = FcFalse;
945 * If this node matches any language, go check
946 * which ones and satisfy those entries
948 if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
950 for (i = 0; i < nPatternLang; i++)
954 if (!patternLangSat[i] &&
955 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
956 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
958 double compare = FcCompareLang (&patternLang, &nodeLang);
959 if (compare >= 0 && compare < 2)
961 if (FcDebug () & FC_DBG_MATCHV)
966 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
967 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
968 printf ("Font %s:%s matches language %d\n", family, style, i);
970 patternLangSat[i] = FcTrue;
978 nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
982 * Re-sort once the language issues have been settled
984 qsort (nodeps, nnodes, sizeof (FcSortNode *),
987 ret = FcFontSetCreate ();
993 if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
1001 FcCharSetDestroy (cs);
1010 FcCharSetDestroy (cs);
1011 FcFontSetDestroy (ret);
1019 FcFontSort (FcConfig *config,
1030 config = FcConfigGetCurrent ();
1035 if (config->fonts[FcSetSystem])
1036 sets[nsets++] = config->fonts[FcSetSystem];
1037 if (config->fonts[FcSetApplication])
1038 sets[nsets++] = config->fonts[FcSetApplication];
1039 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);