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 FcConfigSubstituteWithPat (config
, new, pat
, FcMatchFont
);
503 FcFontSetMatch (FcConfig
*config
,
509 double score
[NUM_MATCH_VALUES
], bestscore
[NUM_MATCH_VALUES
];
516 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
519 if (FcDebug () & FC_DBG_MATCH
)
526 config
= FcConfigGetCurrent ();
530 for (set
= 0; set
< nsets
; set
++)
535 for (f
= 0; f
< s
->nfont
; f
++)
537 if (FcDebug () & FC_DBG_MATCHV
)
539 printf ("Font %d ", f
);
540 FcPatternPrint (s
->fonts
[f
]);
542 if (!FcCompare (p
, s
->fonts
[f
], score
, result
))
544 if (FcDebug () & FC_DBG_MATCHV
)
547 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
549 printf (" %g", score
[i
]);
553 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
555 if (best
&& bestscore
[i
] < score
[i
])
557 if (!best
|| score
[i
] < bestscore
[i
])
559 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
560 bestscore
[i
] = score
[i
];
567 if (FcDebug () & FC_DBG_MATCH
)
569 printf ("Best score");
570 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
571 printf (" %g", bestscore
[i
]);
572 FcPatternPrint (best
);
576 *result
= FcResultNoMatch
;
579 return FcFontRenderPrepare (config
, p
, best
);
583 FcFontMatch (FcConfig
*config
,
592 config
= FcConfigGetCurrent ();
597 if (config
->fonts
[FcSetSystem
])
598 sets
[nsets
++] = config
->fonts
[FcSetSystem
];
599 if (config
->fonts
[FcSetApplication
])
600 sets
[nsets
++] = config
->fonts
[FcSetApplication
];
601 return FcFontSetMatch (config
, sets
, nsets
, p
, result
);
604 typedef struct _FcSortNode
{
606 double score
[NUM_MATCH_VALUES
];
610 FcSortCompare (const void *aa
, const void *ab
)
612 FcSortNode
*a
= *(FcSortNode
**) aa
;
613 FcSortNode
*b
= *(FcSortNode
**) ab
;
614 double *as
= &a
->score
[0];
615 double *bs
= &b
->score
[0];
616 double ad
= 0, bd
= 0;
619 i
= NUM_MATCH_VALUES
;
620 while (i
-- && (ad
= *as
++) == (bd
= *bs
++))
622 return ad
< bd
? -1 : ad
> bd
? 1 : 0;
626 FcSortWalk (FcSortNode
**n
, int nnode
, FcFontSet
*fs
, FcCharSet
**cs
, FcBool trim
, FcBool build_cs
)
634 if (FcPatternGetCharSet (node
->pattern
, FC_CHARSET
, 0, &ncs
) ==
638 * If this font isn't a subset of the previous fonts,
641 if (!trim
|| !*cs
|| !FcCharSetIsSubset (ncs
, *cs
))
643 if (trim
|| build_cs
)
647 ncs
= FcCharSetUnion (ncs
, *cs
);
650 FcCharSetDestroy (*cs
);
653 ncs
= FcCharSetCopy (ncs
);
657 FcPatternReference (node
->pattern
);
658 if (FcDebug () & FC_DBG_MATCH
)
661 FcPatternPrint (node
->pattern
);
663 if (!FcFontSetAdd (fs
, node
->pattern
))
665 FcPatternDestroy (node
->pattern
);
675 FcFontSetSortDestroy (FcFontSet
*fs
)
677 FcFontSetDestroy (fs
);
681 FcFontSetSort (FcConfig
*config
,
692 FcSortNode
**nodeps
, **nodep
;
700 FcBool
*patternLangSat
;
703 if (FcDebug () & FC_DBG_MATCH
)
709 for (set
= 0; set
< nsets
; set
++)
719 for (nPatternLang
= 0;
720 FcPatternGet (p
, FC_LANG
, nPatternLang
, &patternLang
) == FcResultMatch
;
725 nodes
= malloc (nnodes
* sizeof (FcSortNode
) +
726 nnodes
* sizeof (FcSortNode
*) +
727 nPatternLang
* sizeof (FcBool
));
730 nodeps
= (FcSortNode
**) (nodes
+ nnodes
);
731 patternLangSat
= (FcBool
*) (nodeps
+ nnodes
);
735 for (set
= 0; set
< nsets
; set
++)
740 for (f
= 0; f
< s
->nfont
; f
++)
742 if (FcDebug () & FC_DBG_MATCHV
)
744 printf ("Font %d ", f
);
745 FcPatternPrint (s
->fonts
[f
]);
747 new->pattern
= s
->fonts
[f
];
748 if (!FcCompare (p
, new->pattern
, new->score
, result
))
750 if (FcDebug () & FC_DBG_MATCHV
)
753 for (i
= 0; i
< NUM_MATCH_VALUES
; i
++)
755 printf (" %g", new->score
[i
]);
765 nnodes
= new - nodes
;
767 qsort (nodeps
, nnodes
, sizeof (FcSortNode
*),
770 for (i
= 0; i
< nPatternLang
; i
++)
771 patternLangSat
[i
] = FcFalse
;
773 for (f
= 0; f
< nnodes
; f
++)
775 FcBool satisfies
= FcFalse
;
777 * If this node matches any language, go check
778 * which ones and satisfy those entries
780 if (nodeps
[f
]->score
[MATCH_LANG_INDEX
] < nPatternLang
)
782 for (i
= 0; i
< nPatternLang
; i
++)
786 if (!patternLangSat
[i
] &&
787 FcPatternGet (p
, FC_LANG
, i
, &patternLang
) == FcResultMatch
&&
788 FcPatternGet (nodeps
[f
]->pattern
, FC_LANG
, 0, &nodeLang
) == FcResultMatch
)
790 double compare
= FcCompareLang (&patternLang
, &nodeLang
);
791 if (compare
>= 0 && compare
< 2)
793 if (FcDebug () & FC_DBG_MATCHV
)
798 if (FcPatternGetString (nodeps
[f
]->pattern
, FC_FAMILY
, 0, &family
) == FcResultMatch
&&
799 FcPatternGetString (nodeps
[f
]->pattern
, FC_STYLE
, 0, &style
) == FcResultMatch
)
800 printf ("Font %s:%s matches language %d\n", family
, style
, i
);
802 patternLangSat
[i
] = FcTrue
;
810 nodeps
[f
]->score
[MATCH_LANG_INDEX
] = 1000.0;
814 * Re-sort once the language issues have been settled
816 qsort (nodeps
, nnodes
, sizeof (FcSortNode
*),
819 ret
= FcFontSetCreate ();
825 if (!FcSortWalk (nodeps
, nnodes
, ret
, &cs
, trim
, (csp
!=0)))
833 FcCharSetDestroy (cs
);
842 FcCharSetDestroy (cs
);
843 FcFontSetDestroy (ret
);
851 FcFontSort (FcConfig
*config
,
862 config
= FcConfigGetCurrent ();
867 if (config
->fonts
[FcSetSystem
])
868 sets
[nsets
++] = config
->fonts
[FcSetSystem
];
869 if (config
->fonts
[FcSetApplication
])
870 sets
[nsets
++] = config
->fonts
[FcSetApplication
];
871 return FcFontSetSort (config
, sets
, nsets
, p
, trim
, csp
, result
);