Rework Fontconfig fallback to use cached list from font_sort

Previous implementation was querying Fontconfig using `charset` in a pattern,
which was leading to unpredictable fallbacks in some cases, since Fontconfig
was picking the font with the most coverage for a given charset, regardless of
user configuration. Moreover all fallback was based on font_match which is
extremely slow for such performance sensitive task as a fallback, so alacritty
had a hard times on vtebench's unicode-random-write.

The new approach is to use some internal fallback list from font_sort
and iterate over it to get a proper fallback font, since it matches the
following example query from `fc-match`:

`fc-match -s "monospace:pixelsize=X:style=Y"

That being said it's more intuitive for users to setup their system Fontconfig
fallback, and also most applications are doing similar things. Moreover the new
implementation uses internal caches over Fontconfig API when possible and
performs font matches only once during load of requested font with font_sort,
which leads to dramatically improved performance on already mentioned
vtebench's unicode-random-write.

Fixes #3176.
Fixes #3134.
Fixes #2657.
Fixes #1560.
Fixes #965.
Fixes #511.

3 files changed, 66 insertions, 8 deletions

diff --git a/font/src/ft/fc/char_set.rs b/font/src/ft/fc/char_set.rs
index 89554458..4bba4818 100644
--- a/font/src/ft/fc/char_set.rs
+++ b/font/src/ft/fc/char_set.rs
@@ -13,15 +13,19 @@
 // limitations under the License.
 use std::ptr::NonNull;
 
-use foreign_types::{foreign_type, ForeignTypeRef};
+use foreign_types::{foreign_type, ForeignType, ForeignTypeRef};
 
 use super::ffi::FcCharSetCreate;
-use super::ffi::{FcCharSet, FcCharSetAddChar, FcCharSetDestroy};
+use super::ffi::{
+    FcBool, FcCharSet, FcCharSetAddChar, FcCharSetCopy, FcCharSetCount, FcCharSetDestroy,
+    FcCharSetHasChar, FcCharSetMerge, FcCharSetSubtract, FcCharSetUnion,
+};
 
 foreign_type! {
     pub unsafe type CharSet {
         type CType = FcCharSet;
         fn drop = FcCharSetDestroy;
+        fn clone = FcCharSetCopy;
     }
 }
 
@@ -41,4 +45,39 @@ impl CharSetRef {
     pub fn add(&mut self, glyph: char) -> bool {
         unsafe { FcCharSetAddChar(self.as_ptr(), glyph as _) == 1 }
     }
+
+    pub fn has_char(&self, glyph: char) -> bool {
+        unsafe { FcCharSetHasChar(self.as_ptr(), glyph as _) == 1 }
+    }
+
+    pub fn count(&self) -> u32 {
+        unsafe { FcCharSetCount(self.as_ptr()) as u32 }
+    }
+
+    pub fn union(&self, other: &CharSetRef) -> CharSet {
+        unsafe {
+            let ptr = FcCharSetUnion(self.as_ptr() as _, other.as_ptr() as _);
+            CharSet::from_ptr(ptr)
+        }
+    }
+
+    pub fn subtract(&self, other: &CharSetRef) -> CharSet {
+        unsafe {
+            let ptr = FcCharSetSubtract(self.as_ptr() as _, other.as_ptr() as _);
+            CharSet::from_ptr(ptr)
+        }
+    }
+
+    pub fn merge(&self, other: &CharSetRef) -> Result<bool, ()> {
+        unsafe {
+            // Value is just an indicator whether something was added or not
+            let mut value: FcBool = 0;
+            let res = FcCharSetMerge(self.as_ptr() as _, other.as_ptr() as _, &mut value);
+            if res == 0 {
+                Err(())
+            } else {
+                Ok(value != 0)
+            }
+        }
+    }
 }
diff --git a/font/src/ft/fc/mod.rs b/font/src/ft/fc/mod.rs
index 612f7c5a..7389614f 100644
--- a/font/src/ft/fc/mod.rs
+++ b/font/src/ft/fc/mod.rs
@@ -75,11 +75,10 @@ pub fn font_sort(config: &ConfigRef, pattern: &mut PatternRef) -> Option<FontSet
         let mut result = FcResultNoMatch;
 
         let mut charsets: *mut _ = ptr::null_mut();
-
         let ptr = FcFontSort(
             config.as_ptr(),
             pattern.as_ptr(),
-            0, // false
+            1, // Trim font list
             &mut charsets,
             &mut result,
         );
@@ -323,7 +322,7 @@ mod tests {
         let fonts = super::font_sort(config, &mut pattern).expect("sort font monospace");
 
         for font in fonts.into_iter().take(10) {
-            let font = font.render_prepare(&config, &pattern);
+            let font = pattern.render_prepare(&config, &font);
             print!("index={:?}; ", font.index());
             print!("family={:?}; ", font.family());
             print!("style={:?}; ", font.style());
@@ -345,7 +344,7 @@ mod tests {
         let fonts = super::font_sort(config, &mut pattern).expect("font_sort");
 
         for font in fonts.into_iter().take(10) {
-            let font = font.render_prepare(&config, &pattern);
+            let font = pattern.render_prepare(&config, &font);
             print!("index={:?}; ", font.index());
             print!("family={:?}; ", font.family());
             print!("style={:?}; ", font.style());
diff --git a/font/src/ft/fc/pattern.rs b/font/src/ft/fc/pattern.rs
index 4fcea7ae..f69f0926 100644
--- a/font/src/ft/fc/pattern.rs
+++ b/font/src/ft/fc/pattern.rs
@@ -24,7 +24,7 @@ use libc::{c_char, c_double, c_int};
 use super::ffi::FcResultMatch;
 use super::ffi::{FcBool, FcFontRenderPrepare, FcPatternGetBool, FcPatternGetDouble};
 use super::ffi::{FcChar8, FcConfigSubstitute, FcDefaultSubstitute, FcPattern};
-use super::ffi::{FcPatternAddCharSet, FcPatternDestroy};
+use super::ffi::{FcPatternAddCharSet, FcPatternDestroy, FcPatternDuplicate, FcPatternGetCharSet};
 use super::ffi::{FcPatternAddDouble, FcPatternAddString, FcPatternCreate, FcPatternGetString};
 use super::ffi::{FcPatternAddInteger, FcPatternGetInteger, FcPatternPrint};
 
@@ -329,6 +329,7 @@ foreign_type! {
     pub unsafe type Pattern {
         type CType = FcPattern;
         fn drop = FcPatternDestroy;
+        fn clone = FcPatternDuplicate;
     }
 }
 
@@ -531,7 +532,7 @@ impl PatternRef {
 
     pub fn render_prepare(&self, config: &ConfigRef, request: &PatternRef) -> Pattern {
         unsafe {
-            let ptr = FcFontRenderPrepare(config.as_ptr(), request.as_ptr(), self.as_ptr());
+            let ptr = FcFontRenderPrepare(config.as_ptr(), self.as_ptr(), request.as_ptr());
             Pattern::from_ptr(ptr)
         }
     }
@@ -552,6 +553,25 @@ impl PatternRef {
         }
     }
 
+    pub fn get_charset(&self) -> Option<&CharSetRef> {
+        unsafe {
+            let mut charset: *mut _ = ptr::null_mut();
+
+            let result = FcPatternGetCharSet(
+                self.as_ptr(),
+                b"charset\0".as_ptr() as *mut c_char,
+                0,
+                &mut charset,
+            );
+
+            if result == FcResultMatch {
+                Some(&*(charset as *const CharSetRef))
+            } else {
+                None
+            }
+        }
+    }
+
     pub fn file(&self, index: usize) -> Option<PathBuf> {
         unsafe { self.get_string(b"file\0").nth(index) }.map(From::from)
     }