1 /*
2 * fontconfig/src/fcmatch.c
3 *
4 * Copyright © 2000 Keith Packard
5 *
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.
15 *
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.
23 */
24
25 #include "fcint.h"
26
27 static double
28 FcCompareNumber (const FcValue *value1, const FcValue *value2, FcValue *bestValue)
29 {
30 double v1, v2, v;
31
32 switch ((int) value1->type) {
33 case FcTypeInteger:
34 v1 = (double) value1->u.i;
35 break;
36 case FcTypeDouble:
37 v1 = value1->u.d;
38 break;
39 default:
40 return -1.0;
41 }
42 switch ((int) value2->type) {
43 case FcTypeInteger:
44 v2 = (double) value2->u.i;
45 break;
46 case FcTypeDouble:
47 v2 = value2->u.d;
48 break;
49 default:
50 return -1.0;
51 }
52 v = v2 - v1;
53 if (v < 0)
54 v = -v;
55 *bestValue = FcValueCanonicalize (value2);
56 return v;
57 }
58
59 static double
60 FcCompareString (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
61 {
62 *bestValue = FcValueCanonicalize (v2);
63 return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
64 }
65
66 static double
67 FcCompareFamily (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
68 {
69 /* rely on the guarantee in FcPatternObjectAddWithBinding that
70 * families are always FcTypeString. */
71 const FcChar8* v1_string = FcValueString(v1);
72 const FcChar8* v2_string = FcValueString(v2);
73
74 *bestValue = FcValueCanonicalize (v2);
75
76 if (FcToLower(*v1_string) != FcToLower(*v2_string) &&
77 *v1_string != ' ' && *v2_string != ' ')
78 return 1.0;
79
80 return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
81 }
82
83 static double
84 FcComparePostScript (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
85 {
86 const FcChar8 *v1_string = FcValueString (v1);
87 const FcChar8 *v2_string = FcValueString (v2);
88 int n;
89 size_t len1, len2, mlen;
90
91 *bestValue = FcValueCanonicalize (v2);
92
93 if (FcToLower (*v1_string) != FcToLower (*v2_string) &&
94 *v1_string != ' ' && *v2_string != ' ')
95 return 1.0;
96
97 n = FcStrMatchIgnoreCaseAndDelims (v1_string, v2_string, (const FcChar8 *)" -");
98 len1 = strlen ((const char *)v1_string);
99 len2 = strlen ((const char *)v2_string);
100 mlen = FC_MAX (len1, len2);
101
102 return (double)(mlen - n) / (double)mlen;
103 }
104
105 static double
106 FcCompareLang (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
107 {
108 FcLangResult result;
109
110 switch ((int) v1->type) {
111 case FcTypeLangSet:
112 switch ((int) v2->type) {
113 case FcTypeLangSet:
114 result = FcLangSetCompare (FcValueLangSet (v1), FcValueLangSet (v2));
115 break;
116 case FcTypeString:
117 result = FcLangSetHasLang (FcValueLangSet (v1), FcValueString (v2));
118 break;
119 default:
120 return -1.0;
121 }
122 break;
123 case FcTypeString:
124 switch ((int) v2->type) {
125 case FcTypeLangSet:
126 result = FcLangSetHasLang (FcValueLangSet (v2), FcValueString (v1));
127 break;
128 case FcTypeString:
129 result = FcLangCompare (FcValueString (v1), FcValueString (v2));
130 break;
131 default:
132 return -1.0;
133 }
134 break;
135 default:
136 return -1.0;
137 }
138 *bestValue = FcValueCanonicalize (v2);
139 switch (result) {
140 case FcLangEqual:
141 return 0;
142 case FcLangDifferentCountry:
143 return 1;
144 case FcLangDifferentLang:
145 default:
146 return 2;
147 }
148 }
149
150 static double
151 FcCompareBool (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
152 {
153 if (v2->type != FcTypeBool || v1->type != FcTypeBool)
154 return -1.0;
155
156 bestValue->type = FcTypeBool;
157 if (v2->u.b != FcDontCare)
158 bestValue->u.b = v2->u.b;
159 else
160 bestValue->u.b = v1->u.b;
161
162 return (double) ((v2->u.b ^ v1->u.b) == 1);
163 }
164
165 static double
166 FcCompareCharSet (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
167 {
168 *bestValue = FcValueCanonicalize (v2); /* TODO Improve. */
169 return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
170 }
171
172 static double
173 FcCompareRange (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
174 {
175 FcValue value1 = FcValueCanonicalize (v1);
176 FcValue value2 = FcValueCanonicalize (v2);
177 double b1, e1, b2, e2, d;
178
179 switch ((int) value1.type) {
180 case FcTypeInteger:
181 b1 = e1 = value1.u.i;
182 break;
183 case FcTypeDouble:
184 b1 = e1 = value1.u.d;
185 break;
186 case FcTypeRange:
187 b1 = value1.u.r->begin;
188 e1 = value1.u.r->end;
189 break;
190 default:
191 return -1;
192 }
193 switch ((int) value2.type) {
194 case FcTypeInteger:
195 b2 = e2 = value2.u.i;
196 break;
197 case FcTypeDouble:
198 b2 = e2 = value2.u.d;
199 break;
200 case FcTypeRange:
201 b2 = value2.u.r->begin;
202 e2 = value2.u.r->end;
203 break;
204 default:
205 return -1;
206 }
207
208 if (e1 < b2)
209 d = b2;
210 else if (e2 < b1)
211 d = e2;
212 else
213 d = (FC_MAX (b1, b2) + FC_MIN (e1, e2)) * .5;
214
215 bestValue->type = FcTypeDouble;
216 bestValue->u.d = d;
217
218 /* If the ranges overlap, it's a match, otherwise return closest distance. */
219 if (e1 < b2 || e2 < b1)
220 return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
221 else
222 return 0.0;
223 }
224
225 static double
226 FcCompareSize (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
227 {
228 FcValue value1 = FcValueCanonicalize (v1);
229 FcValue value2 = FcValueCanonicalize (v2);
230 double b1, e1, b2, e2;
231
232 switch ((int) value1.type) {
233 case FcTypeInteger:
234 b1 = e1 = value1.u.i;
235 break;
236 case FcTypeDouble:
237 b1 = e1 = value1.u.d;
238 break;
239 case FcTypeRange:
240 b1 = value1.u.r->begin;
241 e1 = value1.u.r->end;
242 break;
243 default:
244 return -1;
245 }
246 switch ((int) value2.type) {
247 case FcTypeInteger:
248 b2 = e2 = value2.u.i;
249 break;
250 case FcTypeDouble:
251 b2 = e2 = value2.u.d;
252 break;
253 case FcTypeRange:
254 b2 = value2.u.r->begin;
255 e2 = value2.u.r->end;
256 break;
257 default:
258 return -1;
259 }
260
261 bestValue->type = FcTypeDouble;
262 bestValue->u.d = (b1 + e1) * .5;
263
264 /* If the ranges overlap, it's a match, otherwise return closest distance. */
265 if (e1 < b2 || e2 < b1)
266 return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
267 if (b2 != e2 && b1 == e2) /* Semi-closed interval. */
268 return 1e-15;
269 else
270 return 0.0;
271 }
272
273 static double
274 FcCompareFilename (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
275 {
276 const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
277 *bestValue = FcValueCanonicalize (v2);
278 if (FcStrCmp (s1, s2) == 0)
279 return 0.0;
280 else if (FcStrCmpIgnoreCase (s1, s2) == 0)
281 return 1.0;
282 else if (FcStrGlobMatch (s1, s2))
283 return 2.0;
284 else
285 return 3.0;
286 }
287
288
289 /* Define priorities to -1 for objects that don't have a compare function. */
290
291 #define PRI_NULL(n) \
292 PRI_ ## n ## _STRONG = -1, \
293 PRI_ ## n ## _WEAK = -1,
294 #define PRI1(n)
295 #define PRI_FcCompareFamily(n) PRI1(n)
296 #define PRI_FcCompareString(n) PRI1(n)
297 #define PRI_FcCompareNumber(n) PRI1(n)
298 #define PRI_FcCompareBool(n) PRI1(n)
299 #define PRI_FcCompareFilename(n) PRI1(n)
300 #define PRI_FcCompareCharSet(n) PRI1(n)
301 #define PRI_FcCompareLang(n) PRI1(n)
302 #define PRI_FcComparePostScript(n) PRI1(n)
303 #define PRI_FcCompareRange(n) PRI1(n)
304 #define PRI_FcCompareSize(n) PRI1(n)
305
306 #define FC_OBJECT(NAME, Type, Cmp) PRI_##Cmp(NAME)
307
308 typedef enum _FcMatcherPriorityDummy {
309 #include "fcobjs.h"
310 } FcMatcherPriorityDummy;
311
312 #undef FC_OBJECT
313
314
315 /* Canonical match priority order. */
316
317 #undef PRI1
318 #define PRI1(n) \
319 PRI_ ## n, \
320 PRI_ ## n ## _STRONG = PRI_ ## n, \
321 PRI_ ## n ## _WEAK = PRI_ ## n
322
323 typedef enum _FcMatcherPriority {
324 PRI1(FILE),
325 PRI1(FONTFORMAT),
326 PRI1(VARIABLE),
327 PRI1(SCALABLE),
328 PRI1(COLOR),
329 PRI1(FOUNDRY),
330 PRI1(CHARSET),
331 PRI_FAMILY_STRONG,
332 PRI_POSTSCRIPT_NAME_STRONG,
333 PRI1(LANG),
334 PRI_FAMILY_WEAK,
335 PRI_POSTSCRIPT_NAME_WEAK,
336 PRI1(SYMBOL),
337 PRI1(SPACING),
338 PRI1(SIZE),
339 PRI1(PIXEL_SIZE),
340 PRI1(STYLE),
341 PRI1(SLANT),
342 PRI1(WEIGHT),
343 PRI1(WIDTH),
344 PRI1(FONT_HAS_HINT),
345 PRI1(DECORATIVE),
346 PRI1(ANTIALIAS),
347 PRI1(RASTERIZER),
348 PRI1(OUTLINE),
349 PRI1(ORDER),
350 PRI1(FONTVERSION),
351 PRI_END
352 } FcMatcherPriority;
353
354 #undef PRI1
355
356 typedef struct _FcMatcher {
357 FcObject object;
358 double (*compare) (const FcValue *v1, const FcValue *v2, FcValue *bestValue);
359 int strong, weak;
360 } FcMatcher;
361
362 /*
363 * Order is significant, it defines the precedence of
364 * each value, earlier values are more significant than
365 * later values
366 */
367 #define FC_OBJECT(NAME, Type, Cmp) { FC_##NAME##_OBJECT, Cmp, PRI_##NAME##_STRONG, PRI_##NAME##_WEAK },
368 static const FcMatcher _FcMatchers [] = {
369 { FC_INVALID_OBJECT, NULL, -1, -1 },
370 #include "fcobjs.h"
371 };
372 #undef FC_OBJECT
373
374 static const FcMatcher*
375 FcObjectToMatcher (FcObject object,
376 FcBool include_lang)
377 {
378 if (include_lang)
379 {
380 switch (object) {
381 case FC_FAMILYLANG_OBJECT:
382 case FC_STYLELANG_OBJECT:
383 case FC_FULLNAMELANG_OBJECT:
384 object = FC_LANG_OBJECT;
385 break;
386 }
387 }
388 if (object > FC_MAX_BASE_OBJECT ||
389 !_FcMatchers[object].compare ||
390 _FcMatchers[object].strong == -1 ||
391 _FcMatchers[object].weak == -1)
392 return NULL;
393
394 return _FcMatchers + object;
395 }
396
397 static FcBool
398 FcCompareValueList (FcObject object,
399 const FcMatcher *match,
400 FcValueListPtr v1orig, /* pattern */
401 FcValueListPtr v2orig, /* target */
402 FcValue *bestValue,
403 double *value,
404 int *n,
405 FcResult *result)
406 {
407 FcValueListPtr v1, v2;
408 double v, best, bestStrong, bestWeak;
409 int j, k, pos = 0;
410 int weak, strong;
411
412 if (!match)
413 {
414 if (bestValue)
415 *bestValue = FcValueCanonicalize(&v2orig->value);
416 if (n)
417 *n = 0;
418 return FcTrue;
419 }
420
421 weak = match->weak;
422 strong = match->strong;
423
424 best = 1e99;
425 bestStrong = 1e99;
426 bestWeak = 1e99;
427 for (v1 = v1orig, j = 0; v1; v1 = FcValueListNext(v1), j++)
428 {
429 for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
430 {
431 FcValue matchValue;
432 v = (match->compare) (&v1->value, &v2->value, &matchValue);
433 if (v < 0)
434 {
435 *result = FcResultTypeMismatch;
436 return FcFalse;
437 }
438 v = v * 1000 + j * 100 + k * (v2->value.type == FcTypeString ? 1 : 0);
439 if (v < best)
440 {
441 if (bestValue)
442 *bestValue = matchValue;
443 best = v;
444 pos = k;
445 }
446 if (weak == strong)
447 {
448 /* found the best possible match */
449 if (best < 1000)
450 goto done;
451 }
452 else if (v1->binding == FcValueBindingStrong)
453 {
454 if (v < bestStrong)
455 bestStrong = v;
456 }
457 else
458 {
459 if (v < bestWeak)
460 bestWeak = v;
461 }
462 }
463 }
464 done:
465 if (FcDebug () & FC_DBG_MATCHV)
466 {
467 printf (" %s: %g ", FcObjectName (object), best);
468 FcValueListPrint (v1orig);
469 printf (", ");
470 FcValueListPrint (v2orig);
471 printf ("\n");
472 }
473 if (value)
474 {
475 if (weak == strong)
476 value[strong] += best;
477 else
478 {
479 value[weak] += bestWeak;
480 value[strong] += bestStrong;
481 }
482 }
483 if (n)
484 *n = pos;
485
486 return FcTrue;
487 }
488
489 /* The bulk of the time in FcFontMatch and FcFontSort goes to
490 * walking long lists of family names. We speed this up with a
491 * hash table.
492 */
493 typedef struct
494 {
495 double strong_value;
496 double weak_value;
497 } FamilyEntry;
498
499 typedef struct
500 {
501 FcHashTable *family_hash;
502 } FcCompareData;
503
504 static void
505 FcCompareDataClear (FcCompareData *data)
506 {
507 FcHashTableDestroy (data->family_hash);
508 }
509
510 static void
511 FcCompareDataInit (FcPattern *pat,
512 FcCompareData *data)
513 {
514 FcHashTable *table;
515 FcPatternElt *elt;
516 FcValueListPtr l;
517 int i;
518 const void *key;
519 FamilyEntry *e;
520
521 table = FcHashTableCreate ((FcHashFunc)FcStrHashIgnoreBlanksAndCase,
522 (FcCompareFunc)FcStrCmpIgnoreBlanksAndCase,
523 NULL,
524 NULL,
525 NULL,
526 free);
527
528 elt = FcPatternObjectFindElt (pat, FC_FAMILY_OBJECT);
529 if (elt)
530 {
531 for (l = FcPatternEltValues(elt), i = 0; l; l = FcValueListNext(l), i++)
532 {
533 key = FcValueString (&l->value);
534 if (!FcHashTableFind (table, key, (void **)&e))
535 {
536 e = malloc (sizeof (FamilyEntry));
537 e->strong_value = 1e99;
538 e->weak_value = 1e99;
539 FcHashTableAdd (table, (void *)key, e);
540 }
541 if (l->binding == FcValueBindingWeak)
542 {
543 if (i < e->weak_value)
544 e->weak_value = i;
545 }
546 else
547 {
548 if (i < e->strong_value)
549 e->strong_value = i;
550 }
551 }
552 }
553
554 data->family_hash = table;
555 }
556
557 static FcBool
558 FcCompareFamilies (FcPattern *pat,
559 FcValueListPtr v1orig,
560 FcPattern *fnt,
561 FcValueListPtr v2orig,
562 double *value,
563 FcResult *result,
564 FcHashTable *table)
565 {
566 FcValueListPtr v2;
567 double strong_value;
568 double weak_value;
569 const void *key;
570 FamilyEntry *e;
571
572 assert (table != NULL);
573
574 strong_value = 1e99;
575 weak_value = 1e99;
576
577 for (v2 = v2orig; v2; v2 = FcValueListNext(v2))
578 {
579 key = FcValueString (&v2->value);
580 if (FcHashTableFind (table, key, (void **)&e))
581 {
582 if (e->strong_value < strong_value)
583 strong_value = e->strong_value;
584 if (e->weak_value < weak_value)
585 weak_value = e->weak_value;
586 }
587 }
588 if (FcDebug () & FC_DBG_MATCHV)
589 {
590 printf ("%s: %g ", FcObjectName (FC_FAMILY_OBJECT), strong_value);
591 FcValueListPrint (v1orig);
592 printf (", ");
593 FcValueListPrint (v2orig);
594 printf ("\n");
595 }
596
597 value[PRI_FAMILY_STRONG] = strong_value;
598 value[PRI_FAMILY_WEAK] = weak_value;
599
600 return FcTrue;
601 }
602
603 /*
604 * Return a value indicating the distance between the two lists of
605 * values
606 */
607
608 static FcBool
609 FcCompare (FcPattern *pat,
610 FcPattern *fnt,
611 double *value,
612 FcResult *result,
613 FcCompareData *data)
614 {
615 int i, i1, i2;
616
617 for (i = 0; i < PRI_END; i++)
618 value[i] = 0.0;
619
620 i1 = 0;
621 i2 = 0;
622 while (i1 < pat->num && i2 < fnt->num)
623 {
624 FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
625 FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
626
627 i = FcObjectCompare(elt_i1->object, elt_i2->object);
628 if (i > 0)
629 i2++;
630 else if (i < 0)
631 i1++;
632 else if (elt_i1->object == FC_FAMILY_OBJECT && data->family_hash)
633 {
634 if (!FcCompareFamilies (pat, FcPatternEltValues(elt_i1),
635 fnt, FcPatternEltValues(elt_i2),
636 value, result,
637 data->family_hash))
638 return FcFalse;
639 i1++;
640 i2++;
641 }
642 else
643 {
644 const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
645 if (!FcCompareValueList (elt_i1->object, match,
646 FcPatternEltValues(elt_i1),
647 FcPatternEltValues(elt_i2),
648 NULL, value, NULL, result))
649 return FcFalse;
650 i1++;
651 i2++;
652 }
653 }
654 return FcTrue;
655 }
656
657 FcPattern *
658 FcFontRenderPrepare (FcConfig *config,
659 FcPattern *pat,
660 FcPattern *font)
661 {
662 FcPattern *new;
663 int i;
664 FcPatternElt *fe, *pe;
665 FcValue v;
666 FcResult result;
667 FcBool variable = FcFalse;
668 FcStrBuf variations;
669
670 assert (pat != NULL);
671 assert (font != NULL);
672
673 FcPatternObjectGetBool (font, FC_VARIABLE_OBJECT, 0, &variable);
674 assert (variable != FcDontCare);
675 if (variable)
676 FcStrBufInit (&variations, NULL, 0);
677
678 new = FcPatternCreate ();
679 if (!new)
680 return NULL;
681 for (i = 0; i < font->num; i++)
682 {
683 fe = &FcPatternElts(font)[i];
684 if (fe->object == FC_FAMILYLANG_OBJECT ||
685 fe->object == FC_STYLELANG_OBJECT ||
686 fe->object == FC_FULLNAMELANG_OBJECT)
687 {
688 /* ignore those objects. we need to deal with them
689 * another way */
690 continue;
691 }
692 if (fe->object == FC_FAMILY_OBJECT ||
693 fe->object == FC_STYLE_OBJECT ||
694 fe->object == FC_FULLNAME_OBJECT)
695 {
696 FcPatternElt *fel, *pel;
697
698 FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
699 FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
700 FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
701
702 fel = FcPatternObjectFindElt (font, fe->object + 1);
703 pel = FcPatternObjectFindElt (pat, fe->object + 1);
704
705 if (fel && pel)
706 {
707 /* The font has name languages, and pattern asks for specific language(s).
708 * Match on language and and prefer that result.
709 * Note: Currently the code only give priority to first matching language.
710 */
711 int n = 1, j;
712 FcValueListPtr l1, l2, ln = NULL, ll = NULL;
713 const FcMatcher *match = FcObjectToMatcher (pel->object, FcTrue);
714
715 if (!FcCompareValueList (pel->object, match,
716 FcPatternEltValues (pel),
717 FcPatternEltValues (fel), NULL, NULL, &n, &result))
718 {
719 FcPatternDestroy (new);
720 return NULL;
721 }
722
723 for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
724 l1 != NULL || l2 != NULL;
725 j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
726 {
727 FcValueListPtr (* func) (FcValueListPtr, FcValue, FcValueBinding);
728 FcValueBinding binding = FcValueBindingEnd;
729
730 if (j == n)
731 {
732 binding = FcValueBindingStrong;
733 func = FcValueListPrepend;
734 }
735 else
736 func = FcValueListAppend;
737 if (l1)
738 {
739 ln = func (ln,
740 FcValueCanonicalize (&l1->value),
741 l1->binding);
742 }
743 if (l2)
744 {
745 if (binding == FcValueBindingEnd)
746 binding = l2->binding;
747 ll = func (ll,
748 FcValueCanonicalize (&l2->value),
749 binding);
750 }
751 }
752 FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
753 FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
754
755 continue;
756 }
757 else if (fel)
758 {
759 /* Pattern doesn't ask for specific language. Copy all for name and
760 * lang. */
761 FcValueListPtr l1, l2;
762
763 l1 = FcValueListDuplicate (FcPatternEltValues (fe));
764 l2 = FcValueListDuplicate (FcPatternEltValues (fel));
765 FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
766 FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
767
768 continue;
769 }
770 }
771
772 pe = FcPatternObjectFindElt (pat, fe->object);
773 if (pe)
774 {
775 const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
776 if (!FcCompareValueList (pe->object, match,
777 FcPatternEltValues(pe),
778 FcPatternEltValues(fe), &v, NULL, NULL, &result))
779 {
780 FcPatternDestroy (new);
781 return NULL;
782 }
783 FcPatternObjectAdd (new, fe->object, v, FcFalse);
784
785 /* Set font-variations settings for standard axes in variable fonts. */
786 if (variable &&
787 FcPatternEltValues(fe)->value.type == FcTypeRange &&
788 (fe->object == FC_WEIGHT_OBJECT ||
789 fe->object == FC_WIDTH_OBJECT ||
790 fe->object == FC_SIZE_OBJECT))
791 {
792 double num;
793 FcChar8 temp[128];
794 const char *tag = " ";
795 assert (v.type == FcTypeDouble);
796 num = v.u.d;
797 if (variations.len)
798 FcStrBufChar (&variations, ',');
799 switch (fe->object)
800 {
801 case FC_WEIGHT_OBJECT:
802 tag = "wght";
803 num = FcWeightToOpenType (num);
804 break;
805
806 case FC_WIDTH_OBJECT:
807 tag = "wdth";
808 break;
809
810 case FC_SIZE_OBJECT:
811 tag = "opsz";
812 break;
813 }
814 sprintf ((char *) temp, "%4s=%g", tag, num);
815 FcStrBufString (&variations, temp);
816 }
817 }
818 else
819 {
820 FcPatternObjectListAdd (new, fe->object,
821 FcValueListDuplicate (FcPatternEltValues (fe)),
822 FcTrue);
823 }
824 }
825 for (i = 0; i < pat->num; i++)
826 {
827 pe = &FcPatternElts(pat)[i];
828 fe = FcPatternObjectFindElt (font, pe->object);
829 if (!fe &&
830 pe->object != FC_FAMILYLANG_OBJECT &&
831 pe->object != FC_STYLELANG_OBJECT &&
832 pe->object != FC_FULLNAMELANG_OBJECT)
833 {
834 FcPatternObjectListAdd (new, pe->object,
835 FcValueListDuplicate (FcPatternEltValues(pe)),
836 FcFalse);
837 }
838 }
839
840 if (variable && variations.len)
841 {
842 FcChar8 *vars = NULL;
843 if (FcPatternObjectGetString (new, FC_FONT_VARIATIONS_OBJECT, 0, &vars) == FcResultMatch)
844 {
845 FcStrBufChar (&variations, ',');
846 FcStrBufString (&variations, vars);
847 FcPatternObjectDel (new, FC_FONT_VARIATIONS_OBJECT);
848 }
849
850 FcPatternObjectAddString (new, FC_FONT_VARIATIONS_OBJECT, FcStrBufDoneStatic (&variations));
851 FcStrBufDestroy (&variations);
852 }
853
854 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
855 return new;
856 }
857
858 static FcPattern *
859 FcFontSetMatchInternal (FcFontSet **sets,
860 int nsets,
861 FcPattern *p,
862 FcResult *result)
863 {
864 double score[PRI_END], bestscore[PRI_END];
865 int f;
866 FcFontSet *s;
867 FcPattern *best, *pat = NULL;
868 int i;
869 int set;
870 FcCompareData data;
871 const FcPatternElt *elt;
872
873 for (i = 0; i < PRI_END; i++)
874 bestscore[i] = 0;
875 best = 0;
876 if (FcDebug () & FC_DBG_MATCH)
877 {
878 printf ("Match ");
879 FcPatternPrint (p);
880 }
881
882 FcCompareDataInit (p, &data);
883
884 for (set = 0; set < nsets; set++)
885 {
886 s = sets[set];
887 if (!s)
888 continue;
889 for (f = 0; f < s->nfont; f++)
890 {
891 if (FcDebug () & FC_DBG_MATCHV)
892 {
893 printf ("Font %d ", f);
894 FcPatternPrint (s->fonts[f]);
895 }
896 if (!FcCompare (p, s->fonts[f], score, result, &data))
897 {
898 FcCompareDataClear (&data);
899 return 0;
900 }
901 if (FcDebug () & FC_DBG_MATCHV)
902 {
903 printf ("Score");
904 for (i = 0; i < PRI_END; i++)
905 {
906 printf (" %g", score[i]);
907 }
908 printf ("\n");
909 }
910 for (i = 0; i < PRI_END; i++)
911 {
912 if (best && bestscore[i] < score[i])
913 break;
914 if (!best || score[i] < bestscore[i])
915 {
916 for (i = 0; i < PRI_END; i++)
917 bestscore[i] = score[i];
918 best = s->fonts[f];
919 break;
920 }
921 }
922 }
923 }
924
925 FcCompareDataClear (&data);
926
927 /* Update the binding according to the score to indicate how exactly values matches on. */
928 if (best)
929 {
930 pat = FcPatternCreate ();
931 elt = FcPatternElts (best);
932 for (i = 0; i < FcPatternObjectCount (best); i++)
933 {
934 const FcMatcher *match = FcObjectToMatcher (elt[i].object, FcFalse);
935 FcValueListPtr l = FcPatternEltValues (&elt[i]);
936
937 if (!match)
938 FcPatternObjectListAdd(pat, elt[i].object,
939 FcValueListDuplicate(l), FcTrue);
940 else
941 {
942 FcValueBinding binding = FcValueBindingWeak;
943 FcValueListPtr new = NULL, ll, t = NULL;
944 FcValue v;
945
946 /* If the value was matched exactly, update the binding to Strong. */
947 if (bestscore[match->strong] < 1000)
948 binding = FcValueBindingStrong;
949
950 for (ll = l; ll != NULL; ll = FcValueListNext (ll))
951 {
952 if (!new)
953 {
954 t = new = FcValueListCreate ();
955 }
956 else
957 {
958 t->next = FcValueListCreate ();
959 t = FcValueListNext (t);
960 }
961 v = FcValueCanonicalize (&ll->value);
962 t->value = FcValueSave (v);
963 t->binding = binding;
964 t->next = NULL;
965 }
966 FcPatternObjectListAdd (pat, elt[i].object, new, FcTrue);
967 }
968 }
969 }
970 if (FcDebug () & FC_DBG_MATCH)
971 {
972 printf ("Best score");
973 for (i = 0; i < PRI_END; i++)
974 printf (" %g", bestscore[i]);
975 printf ("\n");
976 FcPatternPrint (pat);
977 }
978 if (FcDebug () & FC_DBG_MATCH2)
979 {
980 char *env = getenv ("FC_DBG_MATCH_FILTER");
981 FcObjectSet *os = NULL;
982
983 if (env)
984 {
985 char *ss, *s;
986 char *p;
987 FcBool f = FcTrue;
988
989 ss = s = strdup (env);
990 os = FcObjectSetCreate ();
991 while (f)
992 {
993 size_t len;
994 char *x;
995
996 if (!(p = strchr (s, ',')))
997 {
998 f = FcFalse;
999 len = strlen (s);
1000 }
1001 else
1002 {
1003 len = (p - s);
1004 }
1005 x = malloc (sizeof (char) * (len + 1));
1006 if (x)
1007 {
1008 strcpy (x, s);
1009 if (FcObjectFromName (x) > 0)
1010 FcObjectSetAdd (os, x);
1011 s = p + 1;
1012 free (x);
1013 }
1014 }
1015 free (ss);
1016 }
1017 FcPatternPrint2 (p, pat, os);
1018 if (os)
1019 FcObjectSetDestroy (os);
1020 }
1021 /* assuming that 'result' is initialized with FcResultNoMatch
1022 * outside this function */
1023 if (pat)
1024 *result = FcResultMatch;
1025
1026 return pat;
1027 }
1028
1029 FcPattern *
1030 FcFontSetMatch (FcConfig *config,
1031 FcFontSet **sets,
1032 int nsets,
1033 FcPattern *p,
1034 FcResult *result)
1035 {
1036 FcPattern *best, *ret = NULL;
1037
1038 assert (sets != NULL);
1039 assert (p != NULL);
1040 assert (result != NULL);
1041
1042 *result = FcResultNoMatch;
1043
1044 config = FcConfigReference (config);
1045 if (!config)
1046 return NULL;
1047 best = FcFontSetMatchInternal (sets, nsets, p, result);
1048 if (best)
1049 {
1050 ret = FcFontRenderPrepare (config, p, best);
1051 FcPatternDestroy (best);
1052 }
1053
1054 FcConfigDestroy (config);
1055
1056 return ret;
1057 }
1058
1059 FcPattern *
1060 FcFontMatch (FcConfig *config,
1061 FcPattern *p,
1062 FcResult *result)
1063 {
1064 FcFontSet *sets[2];
1065 int nsets;
1066 FcPattern *best, *ret = NULL;
1067
1068 assert (p != NULL);
1069 assert (result != NULL);
1070
1071 *result = FcResultNoMatch;
1072
1073 config = FcConfigReference (config);
1074 if (!config)
1075 return NULL;
1076 nsets = 0;
1077 if (config->fonts[FcSetSystem])
1078 sets[nsets++] = config->fonts[FcSetSystem];
1079 if (config->fonts[FcSetApplication])
1080 sets[nsets++] = config->fonts[FcSetApplication];
1081
1082 best = FcFontSetMatchInternal (sets, nsets, p, result);
1083 if (best)
1084 {
1085 ret = FcFontRenderPrepare (config, p, best);
1086 FcPatternDestroy (best);
1087 }
1088
1089 FcConfigDestroy (config);
1090
1091 return ret;
1092 }
1093
1094 typedef struct _FcSortNode {
1095 FcPattern *pattern;
1096 double score[PRI_END];
1097 } FcSortNode;
1098
1099 static int
1100 FcSortCompare (const void *aa, const void *ab)
1101 {
1102 FcSortNode *a = *(FcSortNode **) aa;
1103 FcSortNode *b = *(FcSortNode **) ab;
1104 double *as = &a->score[0];
1105 double *bs = &b->score[0];
1106 double ad = 0, bd = 0;
1107 int i;
1108
1109 i = PRI_END;
1110 while (i-- && (ad = *as++) == (bd = *bs++))
1111 ;
1112 return ad < bd ? -1 : ad > bd ? 1 : 0;
1113 }
1114
1115 static FcBool
1116 FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
1117 {
1118 FcBool ret = FcFalse;
1119 FcCharSet *cs;
1120 int i;
1121
1122 cs = 0;
1123 if (trim || csp)
1124 {
1125 cs = FcCharSetCreate ();
1126 if (cs == NULL)
1127 goto bail;
1128 }
1129
1130 for (i = 0; i < nnode; i++)
1131 {
1132 FcSortNode *node = *n++;
1133 FcBool adds_chars = FcFalse;
1134
1135 /*
1136 * Only fetch node charset if we'd need it
1137 */
1138 if (cs)
1139 {
1140 FcCharSet *ncs;
1141
1142 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
1143 FcResultMatch)
1144 continue;
1145
1146 if (!FcCharSetMerge (cs, ncs, &adds_chars))
1147 goto bail;
1148 }
1149
1150 /*
1151 * If this font isn't a subset of the previous fonts,
1152 * add it to the list
1153 */
1154 if (!i || !trim || adds_chars)
1155 {
1156 FcPatternReference (node->pattern);
1157 if (FcDebug () & FC_DBG_MATCHV)
1158 {
1159 printf ("Add ");
1160 FcPatternPrint (node->pattern);
1161 }
1162 if (!FcFontSetAdd (fs, node->pattern))
1163 {
1164 FcPatternDestroy (node->pattern);
1165 goto bail;
1166 }
1167 }
1168 }
1169 if (csp)
1170 {
1171 *csp = cs;
1172 cs = 0;
1173 }
1174
1175 ret = FcTrue;
1176
1177 bail:
1178 if (cs)
1179 FcCharSetDestroy (cs);
1180
1181 return ret;
1182 }
1183
1184 void
1185 FcFontSetSortDestroy (FcFontSet *fs)
1186 {
1187 FcFontSetDestroy (fs);
1188 }
1189
1190 FcFontSet *
1191 FcFontSetSort (FcConfig *config FC_UNUSED,
1192 FcFontSet **sets,
1193 int nsets,
1194 FcPattern *p,
1195 FcBool trim,
1196 FcCharSet **csp,
1197 FcResult *result)
1198 {
1199 FcFontSet *ret;
1200 FcFontSet *s;
1201 FcSortNode *nodes;
1202 FcSortNode **nodeps, **nodep;
1203 int nnodes;
1204 FcSortNode *new;
1205 int set;
1206 int f;
1207 int i;
1208 int nPatternLang;
1209 FcBool *patternLangSat;
1210 FcValue patternLang;
1211 FcCompareData data;
1212
1213 assert (sets != NULL);
1214 assert (p != NULL);
1215 assert (result != NULL);
1216
1217 /* There are some implementation that relying on the result of
1218 * "result" to check if the return value of FcFontSetSort
1219 * is valid or not.
1220 * So we should initialize it to the conservative way since
1221 * this function doesn't return NULL anymore.
1222 */
1223 if (result)
1224 *result = FcResultNoMatch;
1225
1226 if (FcDebug () & FC_DBG_MATCH)
1227 {
1228 printf ("Sort ");
1229 FcPatternPrint (p);
1230 }
1231 nnodes = 0;
1232 for (set = 0; set < nsets; set++)
1233 {
1234 s = sets[set];
1235 if (!s)
1236 continue;
1237 nnodes += s->nfont;
1238 }
1239 if (!nnodes)
1240 return FcFontSetCreate ();
1241
1242 for (nPatternLang = 0;
1243 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
1244 nPatternLang++)
1245 ;
1246
1247 /* freed below */
1248 nodes = malloc (nnodes * sizeof (FcSortNode) +
1249 nnodes * sizeof (FcSortNode *) +
1250 nPatternLang * sizeof (FcBool));
1251 if (!nodes)
1252 goto bail0;
1253 nodeps = (FcSortNode **) (nodes + nnodes);
1254 patternLangSat = (FcBool *) (nodeps + nnodes);
1255
1256 FcCompareDataInit (p, &data);
1257
1258 new = nodes;
1259 nodep = nodeps;
1260 for (set = 0; set < nsets; set++)
1261 {
1262 s = sets[set];
1263 if (!s)
1264 continue;
1265 for (f = 0; f < s->nfont; f++)
1266 {
1267 if (FcDebug () & FC_DBG_MATCHV)
1268 {
1269 printf ("Font %d ", f);
1270 FcPatternPrint (s->fonts[f]);
1271 }
1272 new->pattern = s->fonts[f];
1273 if (!FcCompare (p, new->pattern, new->score, result, &data))
1274 goto bail1;
1275 if (FcDebug () & FC_DBG_MATCHV)
1276 {
1277 printf ("Score");
1278 for (i = 0; i < PRI_END; i++)
1279 {
1280 printf (" %g", new->score[i]);
1281 }
1282 printf ("\n");
1283 }
1284 *nodep = new;
1285 new++;
1286 nodep++;
1287 }
1288 }
1289
1290 FcCompareDataClear (&data);
1291
1292 nnodes = new - nodes;
1293
1294 qsort (nodeps, nnodes, sizeof (FcSortNode *),
1295 FcSortCompare);
1296
1297 for (i = 0; i < nPatternLang; i++)
1298 patternLangSat[i] = FcFalse;
1299
1300 for (f = 0; f < nnodes; f++)
1301 {
1302 FcBool satisfies = FcFalse;
1303 /*
1304 * If this node matches any language, go check
1305 * which ones and satisfy those entries
1306 */
1307 if (nodeps[f]->score[PRI_LANG] < 2000)
1308 {
1309 for (i = 0; i < nPatternLang; i++)
1310 {
1311 FcValue nodeLang;
1312
1313 if (!patternLangSat[i] &&
1314 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
1315 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
1316 {
1317 FcValue matchValue;
1318 double compare = FcCompareLang (&patternLang, &nodeLang, &matchValue);
1319 if (compare >= 0 && compare < 2)
1320 {
1321 if (FcDebug () & FC_DBG_MATCHV)
1322 {
1323 FcChar8 *family;
1324 FcChar8 *style;
1325
1326 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
1327 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
1328 printf ("Font %s:%s matches language %d\n", family, style, i);
1329 }
1330 patternLangSat[i] = FcTrue;
1331 satisfies = FcTrue;
1332 break;
1333 }
1334 }
1335 }
1336 }
1337 if (!satisfies)
1338 {
1339 nodeps[f]->score[PRI_LANG] = 10000.0;
1340 }
1341 }
1342
1343 /*
1344 * Re-sort once the language issues have been settled
1345 */
1346 qsort (nodeps, nnodes, sizeof (FcSortNode *),
1347 FcSortCompare);
1348
1349 ret = FcFontSetCreate ();
1350 if (!ret)
1351 goto bail1;
1352
1353 if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
1354 goto bail2;
1355
1356 free (nodes);
1357
1358 if (FcDebug() & FC_DBG_MATCH)
1359 {
1360 printf ("First font ");
1361 FcPatternPrint (ret->fonts[0]);
1362 }
1363 if (ret->nfont > 0)
1364 *result = FcResultMatch;
1365
1366 return ret;
1367
1368 bail2:
1369 FcFontSetDestroy (ret);
1370 bail1:
1371 free (nodes);
1372 bail0:
1373 return 0;
1374 }
1375
1376 FcFontSet *
1377 FcFontSort (FcConfig *config,
1378 FcPattern *p,
1379 FcBool trim,
1380 FcCharSet **csp,
1381 FcResult *result)
1382 {
1383 FcFontSet *sets[2], *ret;
1384 int nsets;
1385
1386 assert (p != NULL);
1387 assert (result != NULL);
1388
1389 *result = FcResultNoMatch;
1390
1391 config = FcConfigReference (config);
1392 if (!config)
1393 return NULL;
1394 nsets = 0;
1395 if (config->fonts[FcSetSystem])
1396 sets[nsets++] = config->fonts[FcSetSystem];
1397 if (config->fonts[FcSetApplication])
1398 sets[nsets++] = config->fonts[FcSetApplication];
1399 ret = FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1400 FcConfigDestroy (config);
1401
1402 return ret;
1403 }
1404 #define __fcmatch__
1405 #include "fcaliastail.h"
1406 #undef __fcmatch__