charlock_holmes: Build fails to link `-licuuc -lz` on gentoo

gem install fails with these build errors (and warnings)

host ~ # gem install charlock_holmes
Building native extensions.  This could take a while...
ERROR:  Error installing charlock_holmes:
        ERROR: Failed to build gem native extension.

        /usr/bin/ruby19 extconf.rb
checking for main() in -licui18n... yes
checking for main() in -licui18n... yes
checking for unicode/ucnv.h... yes
  -- tar zxvf file-5.08.tar.gz
  -- ./configure --prefix=/usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4/ext/charlock_holmes/dst/ --disable-shared --enable-static --with-pic
  -- patch -p0 < ../file-soft-check.patch
  -- make -C src install
  -- make -C magic install
checking for main() in -lmagic_ext... yes
checking for magic.h... yes
creating Makefile

make
compiling encoding_detector.c
common.h:14:14: warning: 'charlock_new_enc_str' defined but not used [-Wunused-function]
compiling converter.c
common.h:23:14: warning: 'charlock_new_str' defined but not used [-Wunused-function]
common.h:32:14: warning: 'charlock_new_str2' defined but not used [-Wunused-function]
compiling ext.c
common.h:14:14: warning: 'charlock_new_enc_str' defined but not used [-Wunused-function]
common.h:23:14: warning: 'charlock_new_str' defined but not used [-Wunused-function]
common.h:32:14: warning: 'charlock_new_str2' defined but not used [-Wunused-function]
compiling transliterator.cpp
common.h:14:14: warning: 'VALUE charlock_new_enc_str(const char*, size_t, void*)' defined but not used [-Wunused-function]
common.h:32:14: warning: 'VALUE charlock_new_str2(const char*)' defined but not used [-Wunused-function]
linking shared-object charlock_holmes/charlock_holmes.so
encoding_detector.o: In function `rb_get_supported_encodings':
encoding_detector.c:(.text+0xa0): undefined reference to `uenum_count_49'
encoding_detector.c:(.text+0xc1): undefined reference to `uenum_next_49'
encoding_detector.c:(.text+0x12a): undefined reference to `uenum_next_49'
encoding_detector.c:(.text+0x16c): undefined reference to `uenum_next_49'
encoding_detector.c:(.text+0x1ad): undefined reference to `uenum_next_49'
encoding_detector.c:(.text+0x1f7): undefined reference to `uenum_next_49'
encoding_detector.o:encoding_detector.c:(.text+0x234): more undefined references to `uenum_next_49' follow
encoding_detector.o: In function `rb_encdec__alloc':
encoding_detector.c:(.text+0x75d): undefined reference to `u_errorName_49'
converter.o: In function `rb_converter_convert':
converter.c:(.text+0xb1): undefined reference to `ucnv_convert_49'
converter.c:(.text+0xf1): undefined reference to `ucnv_convert_49'
converter.c:(.text+0x18a): undefined reference to `u_errorName_49'
transliterator.o: In function `rb_transliterator_id_list':
transliterator.cpp:(.text+0x15a): undefined reference to `u_errorName_49'
transliterator.o: In function `rb_transliterator_transliterate':
transliterator.cpp:(.text+0x242): undefined reference to `icu_49::UnicodeString::UnicodeString(char const*, int)'
transliterator.cpp:(.text+0x26e): undefined reference to `icu_49::UnicodeString::~UnicodeString()'
transliterator.cpp:(.text+0x287): undefined reference to `icu_49::UMemory::operator new(unsigned long)'
transliterator.cpp:(.text+0x29d): undefined reference to `icu_49::UnicodeString::UnicodeString(char const*, int)'
transliterator.cpp:(.text+0x2e5): undefined reference to `icu_49::UnicodeString::toUTF8(icu_49::ByteSink&) const'
transliterator.cpp:(.text+0x339): undefined reference to `icu_49::ByteSink::~ByteSink()'
transliterator.cpp:(.text+0x396): undefined reference to `u_errorName_49'
transliterator.cpp:(.text+0x40b): undefined reference to `icu_49::UMemory::operator delete(void*)'
transliterator.cpp:(.text+0x442): undefined reference to `icu_49::UnicodeString::~UnicodeString()'
transliterator.o: In function `icu_49::StringByteSink<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >::~StringByteSink()':
transliterator.cpp:(.text._ZN6icu_4914StringByteSinkISsED2Ev[_ZN6icu_4914StringByteSinkISsED5Ev]+0xf): undefined reference to `icu_49::ByteSink::~ByteSink()'
transliterator.o: In function `icu_49::StringByteSink<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >::~StringByteSink()':
transliterator.cpp:(.text._ZN6icu_4914StringByteSinkISsED0Ev[_ZN6icu_4914StringByteSinkISsED5Ev]+0x13): undefined reference to `icu_49::ByteSink::~ByteSink()'
transliterator.cpp:(.text._ZN6icu_4914StringByteSinkISsED0Ev[_ZN6icu_4914StringByteSinkISsED5Ev]+0x1c): undefined reference to `icu_49::UMemory::operator delete(void*)'
transliterator.o:(.data.rel.ro._ZTVN6icu_4914StringByteSinkISsEE[vtable for icu_49::StringByteSink<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]+0x28): undefined reference to `icu_49::ByteSink::GetAppendBuffer(int, int, char*, int, int*)'
transliterator.o:(.data.rel.ro._ZTVN6icu_4914StringByteSinkISsEE[vtable for icu_49::StringByteSink<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]+0x30): undefined reference to `icu_49::ByteSink::Flush()'
transliterator.o:(.data.rel.ro._ZTIN6icu_4914StringByteSinkISsEE[typeinfo for icu_49::StringByteSink<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]+0x10): undefined reference to `typeinfo for icu_49::ByteSink'
./libmagic_ext.a(compress.o): In function `uncompressgzipped':
/usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4/ext/charlock_holmes/src/file-5.08/src/compress.c:357: undefined reference to `inflateInit2_'
/usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4/ext/charlock_holmes/src/file-5.08/src/compress.c:363: undefined reference to `inflate'
/usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4/ext/charlock_holmes/src/file-5.08/src/compress.c:370: undefined reference to `inflateEnd'
collect2: ld returned 1 exit status
make: *** [charlock_holmes.so] Error 1


Gem files will remain installed in /usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4 for inspection.
Results logged to /usr/local/lib64/ruby/gems/1.9.1/gems/charlock_holmes-0.6.9.4/ext/charlock_holmes/gem_make.out

I have also tried with --with-icu-dir to no avail.

Also see https://github.com/gitlabhq/gitlabhq/issues/1972