Upgrading to Boost 1.61 in MacPorts

The Boost version in MacPorts was still 1.59.0—a year old now. When I wrote about Boost.Coroutine2, I found I had to install the latest Boost version 1.61.0. So I had two sets of Boost libraries on my hard drive, which made things . . . er . . . a little bit complicated. After I built Microsoft’s cpprestsdk last night—I managed to make it find and use the MacPorts Boost libraries—I feel more urged to change the situation. So this morning I subscribed to the MacPorts mailing list and posted the question about the outdated version problem. With the help from Mr Michael Dickens and Google, I have a working port of Boost 1.61.0 now. This article will document the procedure how it works.

The first thing one needs to do is check out the port files from the MacPorts Subversion repository. In my case, The boost files are under devel/boost. So I checked out only the boost directory into ~/Programming/MacPorts/devel.

One then needs to tell MacPorts to look for ports in that directory. There are two steps involved:

  1. Add the URL of the local ports directory (e.g. ‘file:///Users/yongwei/Programming/MacPorts’ in my case) to /opt/local/etc/macports/sources.conf, above the default rsync URL.
  2. Run the portindex command under that directory. It needs to be rerun every time a Portfile is changed.

Now MacPorts should find ports first in my local ports directory and then the system default. And I could begin patching the files.

It turned out that people tried to update boost half a year ago for Boost 1.60, but they found there were failing ports and the ABI was incompatible with 1.59. The patch was still good to me, as I had now a good example. I simply applied the patch, ran portindex again, and went ahead to port upgrade boost.

The procedure turned out quite smooth, though mkvtoolnix, the only installed port that depended on boost on my laptop, failed to run after the upgrade. I had to port uninstall it and then port install it again (rebuilding it).

After I had some confidence, I began to change the port files. I changed first Portfile, which contained the version information and file checksums. Updating them was trivial. When I could see the new version 1.61.0 from port info boost, I kicked off the build with port upgrade boost again.

Then came the more painful process of fixing the patch files under devel/boost/files (the ‘patch’ I mentioned a moment ago actually contained patches for these patch files). Most of these MacPorts-specific patch files could be applied without any problems, but one of them failed. It was actually due to trivial code changes in Boost, but I still had to check all the rejections, manually apply the changes, and generate a new patch file. After that, everything went on smoothly.

Against all my hopes, I found that I had to rebuild mkvtoolnix yet again. So the ABI instability is really an issue, and I understand now why boost was stuck at the old version for such a long time. However, I consider my task completed, when I uploaded the updated patch to the MacPorts ticket. At least I have the new working port of boost for myself now. And you can have it too.

Python yield and C++ Coroutines

Back in 2008, an old friend challenged me with a programming puzzle, when we both attended a wedding. He later gave a solution in Python. Comparing with my C++ solution, the Python one has about half the code lines. I was not smart enough to begin learning Python then, but instead put an end to my little interest in Python with a presentation in C++ Conference China 2009. I compared the basic constructs, and concluded they were equivalent, not realizing that Python had more to offer than that trivial programming exercise showed.

Fast forwarding to today (2016), I am really writing some (small) programs in Python. I have begun to appreciate Python more and more. For many of the tasks, the performance loss in executing the code is ignorable, but the productivity boost is huge. I have also realized that there are constructs in Python that are not easily reproducible in other languages. Generator/yield is one of them.

The other day, I was writing a small program to sort hosts based on dot-reversed order so as to group the host names in a more reasonable order (regarding ‘www.wordpress.com’ as ‘com.wordpress.www’). I quickly came up with a solution in Python. The code is very short and I can show it right here:

def backsort(lines):
    result = {}
    for line in lines:
        result['.'.join(reversed(line.split('.')))] = line
    return map(lambda item: item[1],
               sorted(result.items()))

Of course, we can implement a similar function in C++11. We will immediately find that there are no standard implementations for split and join (see Appendix below for my implementation). Regardless, we can write some code like:

template <typename C>
vector<string> backsort(C&& lines)
{
    map<string, string> rmap;
    for (auto& line : lines) {
        auto split_line = split(line, '.');
        reverse(split_line.begin(), split_line.end());
        rmap[join(split_line, '.')] = line;
    }
    vector<string> result(rmap.size());
    transform(rmap.begin(), rmap.end(), result.begin(),
              [](const pair<string, string>& pr)
              {
                  return pr.second;
              });
    return result;
}

Even though it has twice the non-trivial lines of code and is a function template, there is immediately something Python can do readily but C++ cannot. I can give the Python file handle (like os.stdin) directly to backsort, and the for line will iterate through the file content.1 This is because the Python file object implements the iterator protocol over lines of text, but the C++ istream does not do anything similar.

Let us forget this C++ detail, and focus on the problem. My Python code accepts an iterator, and ‘backsorts’ all the input lines. Can we make it process multiple files (like the cat command line), without changing the backsort function?

Of course it can be done. There is a traditional way, and there is a smart way. The traditional way is write a class that implements the iterator protocol (which can be readily modelled by C++):

class cat:
    def __init__(self, files):
        self.files = files
        self.cur_file = None

    def __iter__(self):
        return self

    def next(self):
        while True:
            if self.cur_file:
                line = self.cur_file.readline()
                if line:
                    return line.rstrip('\n')
                self.cur_file.close()
            if self.files:
                self.cur_file = open(self.files[0])
                self.files = self.files[1:]
            else:
                raise StopIteration()

We can then cat files by the following lines:

if __name__ == '__main__':
    if sys.argv[1:]:
        for line in cat(sys.argv[1:]):
            print(line)

Using yield, we can reduce the 18 lines of code of cat to only 5:

def cat(files):
    for fn in files:
        with open(fn) as f:
            for line in f:
                yield line.rstrip('\n')

There is no more bookkeeping of the current file and the unprocessed files, and everything is wrapped in simple loops. Isn’t that amazing? I actually learnt about the concept before (in C#), but never used it in real code—perhaps because I was too much framed by existing code, using callbacks, observer pattern, and the like.—Those ‘patterns’ now look ugly, when compared to the simplicity of generators.

Here comes the real challenge for C++ developers: Can we do the same in C++? Can we do something better than inelegant callbacks? 2


My investigations so far indicate the following: No C++ standards (up to C++14) support such constructs, and there is no portable way to implement them as a library.

Are we doomed? No. Apart from standardization efforts regarding coroutines (which is the ancient name for a superset of generators, dated from 1958) in C++,3 there have been at least five cross-platform implementations for C++:

  • The unofficial Boost.Coroutine by Giovanni P. Deretta (2006), compatible with Windows, Linux, and maybe a few Unix variants (tested not working on OS X); apparently abandoned.4
  • The official Boost.Coroutine by Oliver Kowalke (2013), compatible with ARM, MIPS, PPC, SPARC, x86, and x86-64 architectures.
  • The official Boost.Coroutine2 by Oliver Kowalke (2015), compatible with the same hardware architectures but only C++ compilers/code conformant to the C++14 standard.
  • Mordor by Mozy (2010), compatible with Windows, Linux, and OS X, but seemingly no longer maintained.
  • CO2 by Jamboree (2015), supporting stackless coroutines only, using preprocessor tricks, and requiring C++14.

As Boost.Coroutine2 looks modern, is well-maintained, and is very much comparable to the Python constructs, I will use it in the rest of this article.5 It hides all the platform details with the help of Boost.Context. Now I can write code simply as follows for cat:

typedef boost::coroutines2::coroutine<const string&> coro_t;

void cat(coro_t::push_type& yield, int argc, char* argv[])
{
    for (int i = 1; i < argc; ++i) {
        ifstream ifs(argv[i]);
        for (;;) {
            string line;
            if (getline(ifs, line)) {
                yield(line);
            } else {
                break;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    using namespace std::placeholders;
    for (auto& line : coro_t::pull_type(
             boost::coroutines2::fixedsize_stack(),
             bind(cat, _1, argc, argv))) {
        cout << line << endl;
    }
}

Is this simple and straightforward? The only thing that is not quite intuitive is the detail that the constructor of pull_type expects the second argument to be a function object that takes a push_type& as the only argument. That is why we need to use bind to generate it—a lambda expression being the other alternative.

I definitely believe being able to write coroutines is a big step forward to make C++ more expressive. I can foresee many tasks simplified, like recursive parsing. I believe this will prove very helpful in the C++ weaponry. I only wish we could see it standardized soon.

Appendix

The complete backsort code in Python:

#!/usr/bin/env python
#coding: utf-8

import sys

def cat(files):
    for fn in files:
        with open(fn) as f:
            for line in f:
                yield line.rstrip('\n')

def backsort(lines):
    result = {}
    for line in lines:
        result['.'.join(reversed(line.split('.')))] = line
    return map(lambda item: item[1],
               sorted(result.items()))

def main():
    if sys.argv[1:]:
        result = backsort(cat(sys.argv[1:]))
    else:
        result = backsort(map(
                lambda line: line.rstrip('\n'), sys.stdin))
    for line in result:
        print(line)

if __name__ == '__main__':
    main()

The complete backsort code in C++:

#include <assert.h>         // assert
#include <algorithm>        // std::reverse/transform
#include <fstream>          // std::ifstream
#include <functional>       // std::bind
#include <iostream>         // std::cin/cout
#include <map>              // std::map
#include <string>           // std::string
#include <vector>           // std::vector
#include <boost/coroutine2/all.hpp>

using namespace std;

typedef boost::coroutines2::coroutine<const string&> coro_t;

void cat(coro_t::push_type& yield, int argc, char* argv[])
{
    for (int i = 1; i < argc; ++i) {
        ifstream ifs(argv[i]);
        for (;;) {
            string line;
            if (getline(ifs, line)) {
                yield(line);
            } else {
                break;
            }
        }
    }
}

vector<string> split(const string& str, char delim)
{
    vector<string> result;
    string::size_type last_pos = 0;
    string::size_type pos = str.find(delim);
    while (pos != string::npos) {
        result.push_back(
            str.substr(last_pos, pos - last_pos));
        last_pos = pos + 1;
        pos = str.find(delim, last_pos);
        if (pos == string::npos) {
            result.push_back(str.substr(last_pos));
        }
    }
    return result;
}

template <typename C>
string join(const C& str_list, char delim)
{
    string result;
    for (auto& item : str_list) {
        result += item;
        result += delim;
    }
    if (result.size() != 0) {
        result.resize(result.size() - 1);
    }
    return result;
}

template <typename C>
vector<string> backsort(C&& lines)
{
    map<string, string> rmap;
    for (auto& line : lines) {
        auto split_line = split(line, '.');
        reverse(split_line.begin(), split_line.end());
        rmap[join(split_line, '.')] = line;
    }
    vector<string> result(rmap.size());
    transform(rmap.begin(), rmap.end(), result.begin(),
              [](const pair<string, string>& pr)
              {
                  return pr.second;
              });
    return result;
}

class istream_line_reader {
public:
    class iterator { // implements InputIterator
    public:
        typedef const string& reference;
        typedef string value_type;

        iterator() : stream_(nullptr) {}
        explicit iterator(istream& is) : stream_(&is)
        {
            ++*this;
        }

        reference operator*()
        {
            assert(stream_ != nullptr);
            return line_;
        }
        value_type* operator->()
        {
            assert(stream_ != nullptr);
            return &line_;
        }
        iterator& operator++()
        {
            getline(*stream_, line_);
            if (!*stream_) {
                stream_ = nullptr;
            }
            return *this;
        }
        iterator operator++(int)
        {
            iterator temp(*this);
            ++*this;
            return temp;
        }

        bool operator==(const iterator& rhs) const
        {
            return stream_ == rhs.stream_;
        }
        bool operator!=(const iterator& rhs) const
        {
            return !operator==(rhs);
        }

    private:
        istream* stream_;
        string line_;
    };

    explicit istream_line_reader(istream& is)
        : stream_(is)
    {
    }
    iterator begin() const
    {
        return iterator(stream_);
    }
    iterator end() const
    {
        return iterator();
    }

private:
    istream& stream_;
};

int main(int argc, char* argv[])
{
    using namespace std::placeholders;
    vector<string> result;
    if (argc > 1) {
        result = backsort(coro_t::pull_type(
            boost::coroutines2::fixedsize_stack(),
            bind(cat, _1, argc, argv)));
    } else {
        result = backsort(istream_line_reader(cin));
    }
    for (auto& item : result) {
       cout << item << endl;
    }
}

The istream_line_reader class is not really necessary, and we can simplify it with coroutines. I am including it here only to show what we have to write ‘normally’ (if we cannot use coroutines). Even if we remove it entirely, the C++ version will still have about three times as many non-trivial lines of code as the Python equivalent. It is enough proof to me that I should move away from C++ a little bit. . . .


  1. There is one gotcha: the ‘\n’ character will be part of the string. It will be handled in my solution. 
  2. Generally speaking, callbacks or similar techniques are what C++ programmers tend to use in similar circumstances, if the ‘producer’ part is complicated (otherwise the iterator pattern may be more suitable). Unfortunately, we cannot then combine the use of two simple functions like cat and backsort simultaneously. If we used callbacks, backsort would need to be modified and fragmented. 
  3. P0057 is one such effort, which is experimentally implemented in Visual Studio 2015
  4. According to the acknowledgement pages of next two Boost projects, Giovanni Deretta contributed to them. So his work was not in vain. 
  5. This said, CO2 is also well-maintained, and is more efficient if only a stackless coroutine is needed. See Jamboree’s answer on StackOverflow. The difference looks small to me, and preprocessor tricks are not my favourites, so I will not spend more time on CO2 for now. 

A Small Experiment of System Scripting in Python

My main laptop is still on Mac OS X Lion (10.7). I know I am guilty of exposing my laptop to potential security risks,1 but some of my paid applications do not work on newer OS X versions without an upgrade. I am an austere person and do not want to pay the money yet. In addition, I am also a little bit nostalgic about the skeuomorphic design, though I know some day I will have to use a Mac that has the latest macOS version in order to use new applications. Anyway, I am just procrastinating now, until some sexy new laptop from Apple makes me take out my wallet, or my old laptop goes crazy.

Sorry for this verbose beginning. What I really want to whine about is that Homebrew has stopped supporting my obsolete version of OS X, and I am relying more and more on MacPorts.2 I even had to rebuild most of my ‘ports’ (the term for packages in MacPorts) because the ‘standard’ way of building ports on Lion does not use libc++, while it is necessary for some ports.3 Unlike Homebrew, MacPorts does not show whether a dependency of a port is already installed or not. Worse, MacPorts packages often have heavy dependencies. For example, the command-line tool mkvtoolnix currently has 20 (recursive) dependencies in Homebrew, but 60 dependencies in MacPorts. My default compiler is clang-3.7, which has 46 dependencies. That pretty much makes the ‘port rdeps’ command useless.

A Google search showed this port command could be helpful:

port echo rdepof:PORT_NAME and not installed

However, more investigation showed there were several problems:

  • One cannot specify variants (like ‘+openmp’).
  • An option (like ‘configure.compiler=macports-clang-3.7’) can affect dependencies, but options do not have the intended effect in the ‘port echo’ command.
  • The recursion is not ‘cut’ when a port is already installed, which can result in unnecessary ports.

This problem had fretted me for some time, before I finally decided to take some action. Naturally, the ultimate solution is write some code. I normally use Bash or Perl for such scripting tasks, but, as I have become more and more interested in Python recently, I decided also to give Python a try to see how it handles such tasks.

I first wrote a Bash version for comparison purposes. It was not recursive, though (too cumbersome for Bash):

#!/bin/bash
function escape {
  printf "%s" "$1" | sed 's/[.*\[]/\\&/g'
}

INSTALLED=`port installed \
         | sed -n 's/^  \([A-Za-z_][^ ]*\).*/-e ^\1$/p'`
INSTALLED_ESC=`escape "$INSTALLED"`
port deps "$@" | sed -n 's/.*Dependencies:[[:space:]]*//p' \
               | sed $'s/, /\\\n/g' \
               | sort \
               | uniq \
               | grep -v $INSTALLED_ESC

Let me explain the code quickly (assuming you are familiar with the basic use of Bash and common Unix tools). ‘port installed’ returns the installed ports, and every line beginning with two spaces are port names followed by other information (like version). I retrieve the port names, and wrap each of them with ‘-e ^…$’. Since they will be used for grep, special characters need to be escaped (practically only ‘.’). I then invoke ‘port deps’ with the command-line arguments, look for lines containing ‘Dependencies:’, get everything after it, split at the commas to get the depended ports, sort the ports, remove duplicates, and filter out all installed ports from the result.

It basically works, and the code is succinct. It is also far from elegant, and quite error-prone. A Bash function feels like a hack. The quotation rules are tricky (when invoking escape, $INSTALLED must be quoted; but when invoking grep, $INSTALLED_ESC must not be quoted). Escaping can easily get problematic when used inside quotation marks. And so on. . . . It is difficult to imagine people can write Bash scripts without some trial and error, even though only a few lines are written.

I knew some Python, but I am not very familiar with it. So I was basically writing while Googling. I got the first version, sort of an equivalent of the Bash script, in about two hours:

#!/usr/bin/env python
#coding: utf-8

import re
import sys
import subprocess

# Gets command output as a list of lines
def popen_readlines(cmd):
    p = subprocess.Popen(cmd, stdout=subprocess.PIPE)
    p.wait()
    if p.returncode != 0:
        raise subprocess.CalledProcessError(p.returncode, \
                                            cmd)
    else:
        return map(lambda line: line.rstrip('\n'), \
                   p.stdout.readlines())

# Gets the port name from a line like
# "  gcc6 @6.1.0_0 (active)"
def get_port_name(port_line):
    return re.sub(r'^  (\S+).*', r'\1', port_line)

# Gets installed ports as a set
def get_installed():
    installed_ports_lines = \
            popen_readlines(['port', 'installed'])[1:]
    installed_ports = \
            set(map(get_port_name, installed_ports_lines))
    return installed_ports

# Gets dependencies for the given port list (which may
# contain options etc.), as a list, excluding items in
# ignored_ports
def get_deps(ports, ignored_ports):
    deps_raw = popen_readlines(['port', 'deps'] + ports)
    uninstalled_ports = []
    for line in deps_raw:
        if re.search(r'Dependencies:', line):
            deps = re.sub(r'.*Dependencies:\s*', '', \
                          line).split(', ')
            uninstalled_ports += \
                [x for x in deps if x not in ignored_ports]
            ignored_ports |= set(deps)
    return uninstalled_ports

def main():
    if sys.argv[1:]:
        installed_ports = get_installed()
        uninstalled_ports = get_deps(sys.argv[1:], \
                                     installed_ports)
        for port in uninstalled_ports:
            print port

if __name__ == '__main__':
    main()

A few things immediately came to notice:

  • The code is apparently more verbose than Bash or Perl, but arguably also clearer and more readable.
  • Strings are ubiquitous in Bash, but lists are ubiquitous in Python. Python allowed backticks (`…`) for piping, but they are deprecated now in favour of the subprocess routines, which accept the command line as a list.
  • The set is a built-in type and is a breeze to use.
  • I/O is not as easy as in Perl (thinking of <> and chomp now), but can be easily simplified with helper functions, as composability is very good.
  • List comprehension and map are very helpful to keep the code concise.

It is not all. The real fun was that it was easy to convert the code to work recursively on all depended ports. I only needed to add/change seven lines of code, at the beginning and end of get_deps:

def get_deps(ports, ignored_ports):
    # New code to end the recursion
    if ports == []:
        return []

    # This part is not changed
    deps_raw = popen_readlines(['port', 'deps'] + ports)
    uninstalled_ports = []
    for line in deps_raw:
        if re.search(r'Dependencies:', line):
            deps = re.sub(r'.*Dependencies:\s*', '', \
                          line).split(', ')
            uninstalled_ports += \
                [x for x in deps if x not in ignored_ports]
            ignored_ports |= set(deps)

    # New code to call recursively and collect the result
    results = []
    for port in uninstalled_ports:
        results.append(port)
        results += get_deps([port], ignored_ports)
    return results

The output did not show any indentation yet, and I found another problem later. The improved final code looks as follows:

#!/usr/bin/env python
#coding: utf-8

import re
import sys
import subprocess

# Gets command output as a list of lines
def popen_readlines(cmd):
    p = subprocess.Popen(cmd, stdout=subprocess.PIPE)
    p.wait()
    if p.returncode != 0:
        raise subprocess.CalledProcessError(p.returncode, \
                                            cmd)
    else:
        return map(lambda line: line.rstrip('\n'), \
                   p.stdout.readlines())

# Gets the port name from a line like
# "  gcc6 @6.1.0_0 (active)"
def get_port_name(port_line):
    return re.sub(r'^  (\S+).*', r'\1', port_line)

# Gets installed ports as a set
def get_installed():
    installed_ports_lines = \
            popen_readlines(['port', 'installed'])[1:]
    installed_ports = \
            set(map(get_port_name, installed_ports_lines))
    return installed_ports

# Gets port names from items that may contain version
# specifications, variants, or options
def get_ports(ports_and_specs):
    requested_ports = set()
    for item in ports_and_specs:
        if not (re.search(r'^[-+@]', item) or \
                re.search(r'=', item)):
            requested_ports.add(item)
    return requested_ports

# Gets dependencies for the given port list (which may
# contain options etc.), as a list of tuples (combining
# with level), excluding items in ignored_ports
def get_deps(ports, ignored_ports, level):
    if ports == []:
        return []

    deps_raw = popen_readlines(['port', 'deps'] + ports)
    uninstalled_ports = []
    for line in deps_raw:
        if re.search(r'Dependencies:', line):
            deps = re.sub(r'.*Dependencies:\s*', '', \
                          line).split(', ')
            uninstalled_ports += \
                [x for x in deps if x not in ignored_ports]
            ignored_ports |= set(deps)

    port_level_pairs = []
    for port in uninstalled_ports:
        port_level_pairs += [(port, level)]
        port_level_pairs += get_deps([port], \
                                     ignored_ports, \
                                     level + 1)
    return port_level_pairs

def main():
    if sys.argv[1:]:
        ports_and_specs = sys.argv[1:]
        ignored_ports = get_installed() | \
                        get_ports(ports_and_specs)
        uninstalled_ports = get_deps(ports_and_specs, \
                                     ignored_ports, 0)
        for (port, level) in uninstalled_ports:
            print ' ' * (level * 2) + port

if __name__ == '__main__':
    main()

I would say I am very happy, even excited, with the experiment results. No wonder Python has been a great success, despite being verbose and having a slightly weird syntax🙂. I guess I would do more Python in the future.

By the way, the code in this article is in Python 2. Python 3 is stricter and even more verbose: I do not see the benefits of using it for system scripting (yet).


  1. Not really. My MacBook Pro has the firewall turned on, it is behind the home router nearly at all times, and I do not visit strange web sites—not with Safari at least. 
  2. Honestly, it is not the fault of Homebrew, or even Apple. However, I do miss the support lifecycle that Microsoft provided for Windows XP. 
  3. For more details, Using libc++ on older system explains the why and how. 

Choosing a Multi-Precision Library for C++—A Critique

The Problem

After reading From Mathematics to Generic Programming,1 I accumulated some template code related to the RSA algorithm,2 but I tested it only with native integer types. Some recent events required me to use it for calculations that involve data sizes slightly bigger than those of the built-in types. I had to find some big-number libraries to help the calculation.

This is what the code looks like:

template <Integer N>
inline bool odd(N n)
{
    return n % 2 == 1;
}

template <Integer N>
inline N half(N n)
{
    return n / 2;
}

…

template <EuclideanDomain E>
std::pair<E, E> extended_gcd(E a, E b)
{
    …
}

template <Regular A, Integer N, SemigroupOperation Op>
A power_accumulate_semigroup(A r, A a, N n, Op op)
{
    …
}

template <Regular A, Integer N, SemigroupOperation Op>
A power_semigroup(A a, N n, Op op)
{
    assert(n > 0);
    while (!odd(n)) {
        a = op(a, a);
        n = half(n);
    }
    if (n == 1) {
        return a;
    }
    return power_accumulate_semigroup(a, op(a, a),
                                      half(n - 1), op);
}

template <Integer N>
struct modulo_multiply {
    modulo_multiply(const N& i) : modulus(i) {}
    N operator()(const N& n, const N& m) const
    {
        return (n * m) % modulus;
    }
private:
    N modulus;
};

int main()
{
    typedef … int_type;

    int_type p1 = …;
    int_type p2 = …;
    int_type n = p1 * p2;
    int_type phi = (p1 - 1) * (p2 - 1);
    int_type pub = …;

    pair<int_type, int_type> p = extended_gcd(pub, phi);
    // Check that p.second == 1
    int_type prv = p.first;
    …

    int_type encrypt = …;

    cout << "Encryped message is " << encrypt << endl;
    cout << "Decrypted message is "
         << power_semigroup(encrypt, prv,
                            modulo_multiply<int_type>(n))
         << endl;
}

There are a few details omitted here, but the point is that I had already the code that worked when int_type was defined to int64_t, and I needed some types that could represent higher precisions and work with the existing code with minimal changes.

The Exploration

NTL

One of the first libraries I tried was NTL,3 which seemed to support the standard mathematical operators well. It did not take me long to make it work with my program, and I was able to get the result successfully. However, I saw several problems that made me think I probably wanted a more mature solution in the long run:

  • Its class name for big integers is ‘NTL::ZZ’. ‘ZZ’ looks ugly to me, not aesthetically comfortable as a type name.
  • It does not provide a make mechanism for Windows. Luckily, it does not require external libraries and it is easy enough to build it manually with GCC.
  • Code like ‘NTL::ZZ pub = 3’ does not compile, which is a minor annoyance (but ‘NTL::ZZ pub(3)’ is an easy workaround, anyway).
  • Code like ‘NTL::ZZ p1("3440890133")’ does not work. This is a problem for big integers that cannot be represented by a native integer type. The workaround is using std::istringstream, which would require more lines and clumsiness.
  • There is no support for getting the input or output in hexadecimal numbers.

CLN

Another library I tried at the same time was CLN.4 It is not friendly to Windows users either, so I simply installed it from Cygwin.5 It seems to be in stark contrast to NTL in some aspects:

  • The class name for big integers is more reasonably named ‘cln::cl_I’.
  • Code lines like ‘cln::cl_I pub = 3’ and ‘cln::cl_I p1("3440890133")’ work.
  • CLN provides support for hexadecimal input (using a special ‘#x’ prefix in the number string) and output (using the fprinthexadecimal function).

However, CLN is quite terrible in its handling of C++ operators:

  • % is not overriden, and I have to call the mod function instead.
  • Division is not implemented on cl_I. I have to, in the general case, use a function that returns the {quotient, remainder} pair, or use an exquo function when I can guarantee that the remainder is zero. Luckily, in my specific case, I can substitute ‘>> 1’ for ‘/ 2’. If shifts could not be used, I would have to replace ‘n / 2’ with something like ‘truncate2(n, 2).quotient’. Providing a series of division functions that return both the quotient and remainder is good; forcing people to use them is not.

Unlike the immaturity of NTL, it looks like that CLN deliberately made the design choices to be this way. Still, it looks bad enough to me. The API design of CLN shows the hauteur of the authors: Your time is not important to me; read the fucking manual, and do things the correct way we want it to be. This condescending attitude is completely against the trend.

Boost.Multiprecision

Finally, I found out that I should have looked no further than just the famous Boost libraries.6 A multi-precision template library is among Boost’s 100+ libraries, simply named ‘Boost.Multiprecision’.7 I wondered why I missed it in the beginning. But, anyway, it fulfilled all my needs wonderfully:

  • Using the basic cpp_int type does not require building any libraries. This makes it work on any platform that has a decent C++ compiler.
  • All needed operators (like +, -, *, /, and %) are implemented.
  • Initialization from native integer types and C strings works.
  • Hexadecimal input and output are implemented in a natural way: inputs can have the ‘0x’ prefix, and the hex manipulator can be used to make the big integer output to iostreams in the hexadecimal form.8
  • In addition, it supports the C++11 user-defined literals.9 So, instead of writing something like ‘cppint encrypt("0xB570BF8E4BDABA4C")’, you can have more efficient code by writing ‘cppint encrypt(0xB570BF8E4BDABA4C_cppi)’.

This said, one problem halted me when I first used its cpp_int type: very weird compilation errors occurred, spanning several screens. Actually, the solution is described in the introduction of the library, as well as in the first answer of its FAQ, so I figured it out the next day (I did not read carefully the documentation on the first night). I needed to either replace expressions like ‘half(n - 1)’ with explicit type-casts like ‘half(N(n - 1))’, or simply use an alternative typedef to turn off expression templates—which I did:

    typedef boost::multiprecision::number<
            boost::multiprecision::cpp_int_backend<>,
            boost::multiprecision::et_off> int_type;

You can read the Boost documentation for more details. It is related to performance. It is also worth noting that with C++11 move semantics, the expression-template-disabled form I use can still have performance close enough (no more than 10% slower) to the expression-template-enabled form. And the first template parameter probably has a bigger impact—GMP can be used as the backend and is considered faster.10

In my humble opinions, Boost.Precision should change the default cpp_int definition to have et_off. Developers who want the ultimate performance will always read the documentation, but it does not seem necessary to force other developers to have failures, read documentation, and change their code. In my case, it takes several seconds to compile the program, a small fraction of a second to run the program, but several hours to find the correct library and learn how to use it.

The Critique

I would argue that the following three criteria should be the foremost in choosing (and thus providing) a good library:

  • Correctness. I think this is self-evident. All three libraries described here satisfy this criterion.
  • Standard and intuitive interface. This is where NTL and CLN fail. CLN does the worst here by intentionally failing to provide operator/. Boost.Multiprecision satisfies my needs without requiring me to look up the documentation (mostly), but it is not perfect, in that the default types can cause horrendous error messages and that its iostream routines do not honour uppercase and nouppercase.11
  • Performance. Yes, performance comes the last among these three. It is still important, but I would argue we should put performance aside when it conflicts with the other two criteria (like treating ‘premature optimization’), and developers can read the documentation and turn performance options back on when they really need it. Boost.Multiprecision is nice to support different backends and the expression template option, but I am not persuaded that expression templates should be enabled by default.

Of course, there are many other criteria, like portability, (lack of) dependency, etc., but they tend to be more subjective and can vary from project to project. The three criteria listed above are the most important to me.

Correctness and developer productivity should be preferred to code performance. This should be true for both scripting languages and traditional compiled languages.

Appendix: Source Listing

The complete RSA sample code that builds with Boost.Precision is listed below for you to play with. We can optimize the code a little bit by substituting the Boost.Multiprecision divide_qr function for the handwritten quotient_remainder. That can be the small exercise for you, dear reader.🙂

#include <assert.h>             // assert
#include <iostream>             // std::cout/endl
#include <utility>              // std::pair/make_pair
#include <boost/multiprecision/cpp_int.hpp>

// Concepts
#define EuclideanDomain         typename
#define Integer                 typename
#define Regular                 typename
#define SemigroupOperation      typename

template <Integer N>
inline bool odd(N n)
{
    return n % 2 == 1;
}

template <Integer N>
inline N half(N n)
{
    return n / 2;
}

template <Integer N>
N largest_doubling(N a, N b)
{
    assert(b != 0);
    for (;;) {
        N c = b + b;
        if (a < c)
            break;
        b = c;
    }
    return b;
}

template <Integer N>
std::pair<N, N> quotient_remainder(N a, N b)
{
    assert(b > 0);
    if (a < b) {
        return std::make_pair(N(0), a);
    }
    N c = largest_doubling(a, b);
    N n(1);
    a = a - c;
    while (c != b) {
        c = half(c);
        n = n + n;
        if (c <= a) {
            a = a - c;
            n = n + 1;
        }
    }
    return std::make_pair(n, a);
}

template <EuclideanDomain E>
std::pair<E, E> extended_gcd(E a, E b)
{
    E x0(1);
    E x1(0);
    while (b != E(0)) {
        // compute new r and x
        std::pair<E, E> qr = quotient_remainder(a, b);
        E x2 = x0 - qr.first * x1;
        // shift r and x
        x0 = x1;
        x1 = x2;
        a = b;
        b = qr.second;
    }
    return std::make_pair(x0, a);
}

template <Regular A, Integer N, SemigroupOperation Op>
A power_accumulate_semigroup(A r, A a, N n, Op op)
{
    assert(n >= 0);
    if (n == 0) {
        return r;
    }
    for (;;) {
        if (odd(n)) {
            r = op(r, a);
            if (n == 1) {
                return r;
            }
        }
        n = half(n);
        a = op(a, a);
    }
}

template <Regular A, Integer N, SemigroupOperation Op>
A power_semigroup(A a, N n, Op op)
{
    assert(n > 0);
    while (!odd(n)) {
        a = op(a, a);
        n = half(n);
    }
    if (n == 1) {
        return a;
    }
    return power_accumulate_semigroup(a, op(a, a),
                                      half(n - 1), op);
}

template <Integer N>
struct modulo_multiply {
    modulo_multiply(const N& i) : modulus(i) {}
    N operator()(const N& n, const N& m) const
    {
        return (n * m) % modulus;
    }
private:
    N modulus;
};

int main()
{
    using namespace std;
    typedef boost::multiprecision::number<
            boost::multiprecision::cpp_int_backend<>,
            boost::multiprecision::et_off> int_type;

    int_type p1 = 3440890133;
    int_type p2 = 4006628849;
    int_type n = p1 * p2;
    int_type phi = (p1 - 1) * (p2 - 1);
    int_type pub = 65537;

    pair<int_type, int_type> p = extended_gcd(pub, phi);
    if (p.second != 1) {
        // pub is not coprime with phi
        cout << "Please choose another public key!" << endl;
        return 1;
    }

    int_type prv = p.first;
    if (prv < 0) {
        prv += phi;
    }

    cout << "Public key is (" << pub << ", " << n << ")\n";
    cout << "Private key is (" << prv << ", " << n << ")\n";

    int_type encrypt("0xB570BF8E4BDABA4C");
    cout << hex;
    cout << "Encryped message is " << encrypt << endl;
    cout << "Decrypted message is "
         << power_semigroup(encrypt, prv,
                            modulo_multiply<int_type>(n))
         << endl;
}

  1. Alexander A. Stepanov and Daniel E. Rose: From Mathematics to Generic Programming. Addison-Wesley Professional, 2014. 
  2. Wikipedia: RSA (cryptosystem)
  3. Victor Shoup: NTL: A Library for doing Number Theory
  4. Bruno Haible and Richard B. Kreckel: CLN — Class Library for Numbers 
  5. Cygwin
  6. Boost
  7. John Maddock and Christopher Kormanyos: Boost.Multiprecision
  8. Cppreference.com: std::hex
  9. Cppreference.com: User-defined literals
  10. Free Software Foundation: GMP — The GNU Multiple Precision Arithmetic Library
  11. Cppreference.com: std::uppercase

MSVCRT.DLL Console I/O Bug

I have been quite annoyed by a Windows bug that causes a huge number of open-source command-line tools to choke on multi-byte characters at the Windows Command Prompt. The MSVCRT.DLL shipped with Windows Vista or later has been having big troubles with such characters. While Microsoft tools and compilers after Visual Studio 6.0 do not use this DLL anymore, the GNU tools on Windows, usually built by MinGW or Mingw-w64, are dependent on this DLL and suffer from this problem. One cannot even use ls to display a Chinese file name, when the system locale is set to Chinese.

The following simple code snippet demonstrates the problem:

#include <locale.h>
#include <stdio.h>

char msg[] = "\xd7\xd6\xb7\xfb Char";
wchar_t wmsg[] = L"字符 char";

void Test1()
{
    char* ptr = msg;
    printf("Test 1: ");
    while (*ptr) {
        putchar(*ptr++);
    }
    putchar('\n');
}

void Test2()
{
    printf("Test 2: ");
    puts(msg);
}

void Test3()
{
    wchar_t* ptr = wmsg;
    printf("Test 3: ");
    while (*ptr) {
        putwchar(*ptr++);
    }
    putwchar(L'\n');
}

int main()
{
    char buffer[32];
    puts("Default C locale");
    Test1();
    Test2();
    Test3();
    putchar('\n');
    puts("Chinese locale");
    setlocale(LC_CTYPE, "Chinese_China.936");
    Test1();
    Test2();
    Test3();
    putchar('\n');
    puts("English locale");
    setlocale(LC_CTYPE, "English_United States.1252");
    Test1();
    Test2();
    Test3();
}

When built with a modern version of Visual Studio, it gives the expected output (console code page is 936):

Default C locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3:  char

Chinese locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3: 字符 char

English locale
Test 1: ×?·? Char
Test 2: ×?·? Char
Test 3:  char

I.e. when the locale is the default ‘C’, the ‘ANSI’ version of character output routines can successfully output single-byte and multi-byte characters, while putwchar, the ‘Unicode’ version of putchar, fails at the multi-byte characters (reasonably, as the C locale does not understand how to translate Chinese characters). When the locale is set correctly to code page 936 (Simplified Chinese), everything is correct. When the locale is set to code page 1252 (Latin), the corresponding characters at the same code points of the original Chinese characters (‘×Ö·û’ instead of ‘字符’) are shown with the ‘ANSI’ routines, though ‘Ö’ (\xd6) and ‘û’ (\xfb) are shown as ‘?’ because they do not exist in code page 936. The Chinese characters, of course, cannot be shown with putwchar in this locale, just like the C locale.

When built with GCC, the result is woeful:

Default C locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3:  char

Chinese locale
Test 1:  Char
Test 2: 字符 Char
Test 3:  char

English locale
Test 1: ×?·? Char
Test 2: ×?·? Char
Test 3:  char

Two things are worth noticing:

  • putchar stops working for Chinese when the locale is correctly set.
  • putwchar never works for Chinese.

Horrible and thoroughly broken! (Keep in mind that Microsoft is to blame here. You can compile the program with MSVC 6.0 using the /MD option, and the result will be the same—an executable that works in Windows XP but not in Windows Vista or later.)

I attacked this problem a few years ago, and tried some workarounds. The solution I came up with looked so fragile that I did not push it up to the MinGW library. It was a personal failure, as well as an indication that working around a buggy implementation without affecting the application code can be very difficult or just impossible.


The problem occurs only with the console, where the Microsoft runtime does some translation (broken in MSVCRT.DLL, but OK in newer MSVC runtimes). It vanishes when users redirect the output from the console. So one solution is not to use the Command Prompt at all. The Cygwin Terminal may be a good choice, especially for people familiar with Linux/Unix. I have Cygwin installed, but sometimes I still want to do things in the more Windows-y way. I figured I could make a small tool (like cat) to get the input from stdin, and forward everything to stdout. As long as this tool is compiled by a Microsoft compiler, things should be OK. Then I thought a script could be faster. Finally, I came up with putting the following line into an mbf.bat:

@perl -p -e ""

(Perl is still wonderful for text processing, even in this ‘empty’ program!)

Now the executables built by GCC and MSVC give the same result, if we append ‘|mbf’ on the command line:

Default C locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3:  char

Chinese locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3: 字符 char

English locale
Test 1: 字符 Char
Test 2: 字符 Char
Test 3:  char

If you know how to make Microsoft fix the DLL problem, do it. Otherwise you know at least a workaround now.🙂


The following code is my original partial solution to the problem, and it may be helpful to your GCC-based project. I don’t claim any copyright of it, nor will I take any responsibilities for its use.

/* mingw_mbcs_safe_io.c */

#include <mbctype.h>
#include <stdio.h>

/* Output functions that work with the Windows 7+ MSVCRT.DLL
 * for multi-byte characters on the console.  Please notice
 * that buffering must not be enabled for the console (e.g.
 * by calling setvbuf); otherwise weird things may occur. */

int __cdecl _mgw_flsbuf(int ch, FILE* fp)
{
  static char lead = '\0';
  int ret = 1;

  if (lead != '\0')
    {
      ret = fprintf(fp, "%c%c", lead, ch);
      lead = '\0';
      if (ret < 0)
        return EOF;
    }
  else if (_ismbblead(ch))
    lead = ch;
  else
    return _flsbuf(ch, fp);

  return ch;
}

int __cdecl putc(int ch, FILE* fp)
{
  static __thread char lead = '\0';
  int ret = 1;

  if (lead != '\0')
    {
      ret = fprintf(fp, "%c%c", lead, ch);
      lead = '\0';
    }
  else if (_ismbblead(ch))
    lead = ch;
  else
    ret = fprintf(fp, "%c", ch);

  if (ret < 0)
    return EOF;
  else
    return ch;
}

int __cdecl putchar(int ch)
{
  putc(ch, stdout);
}

int __cdecl _mgwrt_putchar(int ch)
{
  putc(ch, stdout);
}

Universal Force of LOVE

A purported letter of Albert Einstein to his daughter Lieserl has been circulating in the WeChat Moments recently. It can be summarized as: ‘The universal force is LOVE.’ I was sceptical immediately—as a physics major, I could hardly imagine that our grand master could utter such nonsense (sorry to folks who happen to like the letter). He made mistakes, he could be sentimental, but it was beyond my imagination to assume that he had generated this kind of ‘chicken soup for the soul’.

I am slightly comforted to see my search results indicate that the letter did not originate in China. It could be found here and here. People have already been discussing it, and it was quite obvious to me that the letter was a fake. A conclusive article appeared on The Huffington Post web site. Katharine Rose discussed the letter, and mentioned that she could not find anything in the online Albert Einstein archives. She also got a response from Diana Kormos-Buchwald, director and editor of the Einstein Papers Project, who clearly stated:

This document is not by Einstein. The family letters donated to the Hebrew University—referred to in this rumor—were not given by Lieserl. They were given by Margot Einstein, who was Albert Einstein’s stepdaughter. Many of those letters were published in Volume 10 of The Collected Papers of Albert Einstein in 2006 and in subsequent volumes, in chronological order.

Interestingly, Katharine Rose thought the letter was ‘seemingly written by Albert Einstein’, and thought it was ‘a beautiful read, offering a universal message that speaks to the essence of the human condition and our incessant yearning to believe in love’s conquering force’. I definitely could not agree. Fortunately, she was rational enough to investigate further. She said it was most important that ‘we always remember and strive to seek the truth in all things’, that ‘we not shy away from asking questions and challenging notions’, and that ‘we remain curious’.—I could not agree more.

The same cannot be said about some other bloggers and commentators. People have used the fake letter to strengthen their faith. Even when challenged about the truthfulness of the letter, one blogger said:

The message is powerful and I believe it to be true. Whether Einstein wrote it or not, some Genius did and I would think that Genius would have shown him/herself by now to claim this letter as theirs.

The faith is stronger than reason. They simply ignored the fact that the message could not have circulated that much, if no one claimed it had been written by Einstein. And I think it is naïve to suppose love can solve problem automatically (unlike Ms Rose, I could not concur with the sentiments). Hey, maybe I should agree that the author is a genius, not of writing, but of psychology. I even think the letter could be a bait, considering that the author used the name Lieserl, who never grew up …

Anyway, it is amazing to see so many people enjoy the chicken soup:

In awe of Mr. Einstein’s brilliance which is just as relative today as it was when he wrote the letter. No question that his words will have the same wonderful ‘light’ decades in the future as well. Thanks for sharing, Sue. Light and love to you.

How wonderful, “God is love and love is God”. The great scientist concluded this! Love is a powerful force that unites and i [sic] think Love alone will bring Peace upon the planet.

Amen. Men of science will come to know what men of faith have always known.

I do not see that anybody contest the value of this massage [sic], because it is uncontestable.

Some people may read into this sentimentality, but I think that Einstein was onto something much more profound. I’m thinking that this universal force, when focused on loving others, is what can eventually overcome all obstacles in one’s own mind (soul) and others. How do we develop pure love? Worth contemplating.

I do not think I stand a chance of persuading them the other way.

I cannot help thinking about one famous quote attributed to Einstein, which is probably false, but more like what he might have said:

Two things are infinite, the universe and human stupidity, and I am not yet completely sure about the universe.

Generic Lambdas and the compose Function

I am about two thirds through Scott Meyers’ Effective Modern C++, and I have discovered the power of generic lambdas. Actually I had read about generic lambdas before in the Wikipedia entry on C++14, but that was far from enough for me to get it—and I was not smart enough to investigate deeper. Anyway, Item 33 in Effective Modern C++ gives enough examples to show me the power, and it is exactly the tool I need to solve the problems in my compose function.

Let me start from my (poor) exclamation in my last blog:

Alas, a lambda is only a function, but not a type-deducing function template.

Wrong, wrong, wrong! The generic lambda is exactly what I claimed it was not.

Type deduction was the problem that caused my compose function template to fail. Recall its definition and the failure case:

template <typename Tp>
auto compose()
{
    return apply<Tp>;
}

template <typename Tp, typename Fn, typename... Fargs>
auto compose(Fn fn, Fargs... args)
{
    return [=](Tp&& x) -> decltype(auto)
    {
        return fn(compose<Tp>(args...)(forward<Tp>(x)));
    };
}

…
Obj obj(0);
auto const op_nr = compose<Obj>(clone);
test(op_nr(obj));

The error was that obj, as an lvalue, could not be bound to Obj&& (on line 10). Although I tried to use the perfect forwarding pattern, it did not work, as there was no type deduction—Tp was specified by the caller. Why so? Because I thought a lambda could not be a type-deducing function template.

I won’t go into details about generic lambdas per se, of which you can get a lot of information in Scott’s book or by Google. Instead, I only want to show you that generic lambdas help solve the type deduction problem and give a function template to suit my needs.

Without further ado, I am showing you the improved version of compose that uses generic lambdas:

auto compose()
{
    return [](auto&& x) -> decltype(auto)
    {
        return forward<decltype(x)>(x);
    };
}

template <typename Fn, typename... Fargs>
auto compose(Fn fn, Fargs... args)
{
    return [=](auto&& x) -> decltype(auto)
    {
        return fn(compose(args...)(forward<decltype(x)>(x)));
    };
}

You can immediately notice the following:

  • The original template type parameter Tp is gone.
  • Tp&& is now changed to auto&&, allowing type deduction to work.
  • In order to make perfect forwarding work when the type of x is unknown, forward<decltype(x)> is used.

With this definition, We no longer need to differentiate between op_klvr, op_rvr, etc. No way to do so, anyway. Things are beautifully unified, until the moment you need to put it in an std::function. Run the code at the final listing to see their differences.

Although it already looks perfect, we have a bonus since we no longer specify Tp. We are no longer constrained by only one argument. A small change will make multiple arguments work:

auto compose()
{
    return [](auto&& x) -> decltype(auto)
    {
        return forward<decltype(x)>(x);
    };
}

template <typename Fn>
auto compose(Fn fn)
{
    return [=](auto&&... x) -> decltype(auto)
    {
        return fn(forward<decltype(x)>(x)...);
    };
}

template <typename Fn, typename... Fargs>
auto compose(Fn fn, Fargs... args)
{
    return [=](auto&&... x) -> decltype(auto)
    {
        return fn(
            compose(args...)(forward<decltype(x)>(x)...));
    };
}

The first compose function is no longer useful when we have at least one function passed to compose, but I am keeping it for now. The parameter pack plus the generic lambda makes a perfect combination here.

Finally, a code listing for you to play with is provided below (also available as test_compose.cpp in the zip file download for my last blog):

#include <functional>
#include <iostream>

using namespace std;

#define PRINT_AND_TEST(x)           \
    cout << " " << #x << ":\n  ";   \
    test(x);                        \
    cout << endl;

auto compose()
{
    return [](auto&& x) -> decltype(auto)
    {
        return forward<decltype(x)>(x);
    };
}

template <typename Fn>
auto compose(Fn fn)
{
    return [=](auto&&... x) -> decltype(auto)
    {
        return fn(forward<decltype(x)>(x)...);
    };
}

template <typename Fn, typename... Fargs>
auto compose(Fn fn, Fargs... args)
{
    return [=](auto&&... x) -> decltype(auto)
    {
        return fn(
            compose(args...)(forward<decltype(x)>(x)...));
    };
}

struct Obj {
    int value;
    explicit Obj(int n) : value(n)
    {
        cout << "Obj(){" << value << "} ";
    }
    Obj(const Obj& rhs) : value(rhs.value)
    {
        cout << "Obj(const Obj&){" << value << "} ";
    }
    Obj(Obj&& rhs) : value(rhs.value)
    {
        rhs.value = -1;
        cout << "Obj(Obj&&){" << value << "} ";
    }
    ~Obj()
    {
        cout << "~Obj(){" << value << "} ";
    }
};

void test(Obj& x)
{
    cout << "=> Obj&:" << x.value << "\n  ";
}

void test(Obj&& x)
{
    cout << "=> Obj&&:" << x.value << "\n  ";
}

void test(const Obj& x)
{
    cout << "=> const Obj&:" << x.value << "\n  ";
}

Obj clone(Obj x)
{
    cout << "=> clone(Obj):" << x.value << "\n  ";
    return x;
}

void test()
{
    Obj obj(0);
    cout << endl;

    auto const op = compose(clone);
    std::function<Obj(const Obj&)> fn_klvr = op;
    std::function<Obj(Obj&&)> fn_rvr = op;
    std::function<Obj(Obj)> fn_nr = op;
    PRINT_AND_TEST(op(obj));
    PRINT_AND_TEST(fn_klvr(obj));
    PRINT_AND_TEST(fn_nr(obj));
    cout << endl;
    PRINT_AND_TEST(op(Obj(1)));
    PRINT_AND_TEST(fn_klvr(Obj(1)));
    PRINT_AND_TEST(fn_rvr(Obj(1)));
    PRINT_AND_TEST(fn_nr(Obj(1)));
}

template <typename T1, typename T2>
auto sum(T1 x, T2 y)
{
    return x + y;
}

template <typename T1, typename T2, typename... Targ>
auto sum(T1 x, T2 y, Targ... args)
{
    return sum(x + y, args...);
}

template <typename T>
auto sqr(T x)
{
    return x * x;
}

int main()
{
    test();
    cout << endl;
    auto const op = compose(sqr<int>,
                            sum<int, int, int, int, int>);
    cout << op(1, 2, 3, 4, 5) << endl;
}

Happy hacking!

Type Deduction and My Reference Mistakes

I had read Scott Meyers’ three previous books in the Effective series 1 2 3, before I began to read his new Effective Modern C++ 4 at Safari Books Online. I always expect to learn from Scott, but it surprised me how fast it could be. After reading only a few items about type deduction, I found that I implemented apply and compose (pipeline) incorrectly in my first WordPress blog 5. What a shame! But I thought I was fortunate to find the problem so soon, and I would like to record my mistakes and solutions here.

(A side note: As WordPress does not allow uploading C++ source files, I have put all the test code in a zip file. I will quote the relevant source code in the blog directly for an easy read, but you are welcome to download and try the test code yourself!)

First, my implementation of apply had the wrong return type, as shown in the following program (test1.cpp):

#include <iostream>

using namespace std;

#define PRINT_AND_TEST(x)    \
    cout << #x << ": ";      \
    test(x);                 \
    cout << endl;

template <typename Tp>
auto apply(Tp&& data)
{
    return forward<Tp>(data);
}

template <typename Tp, typename Fn, typename... Fargs>
auto apply(Tp&& data, Fn fn, Fargs... args)
{
    return apply(fn(forward<Tp>(data)), args...);
}

struct Obj {
    int value;
    explicit Obj(int n) : value(n)
    {
    }
    Obj(const Obj& rhs) : value(rhs.value)
    {
    }
    Obj(Obj&& rhs) : value(rhs.value)
    {
        rhs.value = -1;
    }
    ~Obj()
    {
    }
};

void test(Obj& x)
{
    cout << "Obj&:" << x.value;
}

void test(Obj&& x)
{
    cout << "Obj&&:" << x.value;
}

void test(const Obj& x)
{
    cout << "const Obj&:" << x.value;
}

int main()
{
    Obj obj(0);
    Obj& nref = obj;
    const Obj& cref = obj;

    PRINT_AND_TEST(obj);
    PRINT_AND_TEST(nref);
    PRINT_AND_TEST(cref);
    PRINT_AND_TEST(Obj(1));
    cout << endl;

    PRINT_AND_TEST(apply(obj));
    PRINT_AND_TEST(apply(nref));
    PRINT_AND_TEST(apply(cref));
    PRINT_AND_TEST(apply(Obj(1)));
    cout << endl;
}

It gives the following output:

obj: Obj&:0
nref: Obj&:0
cref: const Obj&:0
Obj(1): Obj&&:1

apply(obj): Obj&&:0
apply(nref): Obj&&:0
apply(cref): Obj&&:0
apply(Obj(1)): Obj&&:1

Apparently I did not make the types correct. The reason was my ignorant use of auto as the return type, without realizing that it always results in a non-reference type. C++14 provides a special decltype(auto) syntax, which keeps the reference-ness, and it seems to work here. The ‘fixed’ code is as follows (test2.cpp):

template <typename Tp>
decltype(auto) apply(Tp&& data)
{
    return forward<Tp>(data);
}

template <typename Tp, typename Fn, typename... Fargs>
decltype(auto) apply(Tp&& data, Fn fn, Fargs... args)
{
    return apply(fn(forward<Tp>(data)), args...);
}

After that, the program can output the correct result:

obj: Obj&:0
nref: Obj&:0
cref: const Obj&:0
Obj(1): Obj&&:1

apply(obj): Obj&:0
apply(nref): Obj&:0
apply(cref): const Obj&:0
apply(Obj(1)): Obj&&:1

Wait—is the code really correct?

Actually a little more testing reveals a bigger problem, which the original code did not exhibit. Here is the additional test code (test3.cpp):

…
Obj clone(Obj x)
{
    cout << "clone(Obj):" << x.value << " => ";
    return x;
}

int main()
{
    …
    PRINT_AND_TEST(clone(obj));
    PRINT_AND_TEST(clone(nref));
    PRINT_AND_TEST(clone(cref));
    PRINT_AND_TEST(clone(Obj(2)));
    cout << endl;

    PRINT_AND_TEST(apply(obj, clone));
    PRINT_AND_TEST(apply(nref, clone));
    PRINT_AND_TEST(apply(cref, clone));
    PRINT_AND_TEST(apply(Obj(2), clone));
    cout << endl;
}

And its horrendous output:

…
clone(obj): clone(Obj):0 => Obj&&:0
clone(nref): clone(Obj):0 => Obj&&:0
clone(cref): clone(Obj):0 => Obj&&:0
clone(Obj(2)): clone(Obj):2 => Obj&&:2

apply(obj, clone): clone(Obj):0 => Obj&&:1875662080
apply(nref, clone): clone(Obj):0 => Obj&&:1875662080
apply(cref, clone): clone(Obj):0 => Obj&&:1875662080
apply(Obj(2), clone): clone(Obj):2 => Obj&&:1875662080

Let us go back and analyse the case. Since all four functions have problems, we’ll just check the first one.

The call apply(obj, clone) makes the template parameter Tp be deduced to Obj&, as obj is an lvalue. This instantiation of apply(Obj&, Fn) contains the following function body, after all arguments are passed in:

    return apply(clone(forward<Obj&>(obj)));

Please notice that clone returns a temporary object, and its lifetime ends after return statement. As clone returns an rvalue, Tp for the next apply call is deduced to Obj. The function is instantiated as follows (check out the definition of std::forward if you are not familiar with it 6):

Obj&& apply(Obj&& data)
{
    return forward<Obj>(data);
}

Although the cloned object is destroyed after apply(Obj&, Fn) returns, its rvalue reference is still returned. Oops!

Seeing the reason, I only need to make sure an object type is returned when this apply is called. I experimented with the enable_if template 7, but it turns out that the fix is simpler than I expected (test4.cpp):

template <typename Tp>
Tp apply(Tp&& data)
{
    return forward<Tp>(data);
}

template <typename Tp, typename Fn, typename... Fargs>
decltype(auto) apply(Tp&& data, Fn fn, Fargs... args)
{
    return apply(fn(forward<Tp>(data)), args...);
}

I just have to change the first decltype(auto) to Tp to take advantage of the type deduction rules of ‘universal references’. While it is explained most clearly in Item 1 of Scott Meyers’ Effect Modern C++, his online article already has it clearly 8:

During type deduction for a template parameter that is a universal reference, lvalues and rvalues of the same type are deduced to have slightly different types. In particular, lvalues of type T are deduced to be of type T& (i.e., lvalue reference to T), while rvalues of type T are deduced to be simply of type T. (Note that while lvalues are deduced to be lvalue references, rvalues are not deduced to be rvalue references!)

Therefore:

  • If an lvalue is passed to apply, Tp (and the return type) is deduced to an lvalue reference (say, Obj&). This is what we expect to reduce copying.
  • If an rvalue is passed to apply, Tp (and the return type) is deduced to the object type (say, Obj). Now the returned object is move-constructed—what we would like to see.

I then also checked compose. At first, I tested with these lines added to the end of main (after adding the definition of compose, of course; see test5.cpp):

    auto const op1 = compose<Obj&&>(apply<Obj&&>);
    PRINT_AND_TEST(op1(Obj(3)));
    auto const op2 = compose<const Obj&>(apply<const Obj&>);
    PRINT_AND_TEST(op2(Obj(3)));

Both output lines contain ‘test(Obj&&):3’. The second line is obviously wrong, and it is exactly like the apply case, so the solution is similar too. I should not have relied on the wrong auto return type deduction—using decltype(auto) would fix it. The changed compose is like the following (test6.cpp):

template <typename Tp>
auto compose()
{
    return apply<Tp>;
}

template <typename Tp, typename Fn, typename... Fargs>
auto compose(Fn fn, Fargs... args)
{
    return [=](Tp&& x) -> decltype(auto)
    {
        return fn(compose<Tp>(args...)(forward<Tp>(x)));
    };
}

However, when I test code like below, it will not even compile (test7.cpp):

    auto const op_nr = compose<Obj>(clone);
    test(op_nr(obj));

Clang reports errors:

test7.cpp:106:10: error: no matching function for call to object of type 'const (lambda at test.cpp:26:12)'
    test(op_nr(obj));
         ^~~~~
test7.cpp:31:12: note: candidate function not viable: no known conversion from 'Obj' to 'Obj &&' for 1st argument
    return [=](Tp&& x) -> decltype(auto)
           ^
1 error generated.

!@#$%^…

Actually I can ‘fix’ the problem like this:

    auto const op_klvr = compose<const Obj&>(clone);
    test(op_klvr(obj));

Or this:

    auto const op_rvr  = compose<Obj&&>(clone);
    test(op_rvr(Obj()));

The two forms above would work actually quite well, if one knew the argument type and was careful. However, there would be a difference if one was careless, as could be shown by the revised test program with tracking information of the objects’ lifetime (test8.cpp). Only the relevant changes are shown below:

…
#define PRINT_AND_TEST(x)           \
    cout << " " << #x << ":\n  ";   \
    test(x);                        \
    cout << endl;
…
struct Obj {
    int value;
    explicit Obj(int n) : value(n)
    {
        cout << "Obj(){" << value << "} ";
    }
    Obj(const Obj& rhs) : value(rhs.value)
    {
        cout << "Obj(const Obj&){" << value << "} ";
    }
    Obj(Obj&& rhs) : value(rhs.value)
    {
        rhs.value = -1;
        cout << "Obj(Obj&&){" << value << "} ";
    }
    ~Obj()
    {
        cout << "~Obj(){" << value << "} ";
    }
};

void test(Obj& x)
{
    cout << "=> Obj&:" << x.value << "\n  ";
}

void test(Obj&& x)
{
    cout << "=> Obj&&:" << x.value << "\n  ";
}

void test(const Obj& x)
{
    cout << "=> const Obj&:" << x.value << "\n  ";
}

Obj clone(Obj x)
{
    cout << "=> clone(Obj):" << x.value << "\n  ";
    return x;
}

int main()
{
    Obj obj(0);
    Obj& nref = obj;
    const Obj& cref = obj;
    cout << endl;
    …
    auto const op_klvr = compose<const Obj&>(clone);
    auto const op_rvr  = compose<Obj&&>(clone);
    auto const op_nr   = compose<Obj>(clone);
    PRINT_AND_TEST(op_klvr(obj));
    PRINT_AND_TEST(op_klvr(Obj(3)));
    PRINT_AND_TEST(op_rvr(Obj(3)));
    PRINT_AND_TEST(op_nr(Obj(3)));
    //PRINT_AND_TEST(op_nr(obj));
}

The commented-out line cannot compile yet. The rest works fine, and the program will generate the following output (edited):

Obj(){0}
 obj:
  => Obj&:0
 …

 clone(obj):
  Obj(const Obj&){0} => clone(Obj):0
  Obj(Obj&&){0} => Obj&&:0
  ~Obj(){0} ~Obj(){-1}
 clone(nref):
  Obj(const Obj&){0} => clone(Obj):0
  Obj(Obj&&){0} => Obj&&:0
  ~Obj(){0} ~Obj(){-1}
 clone(cref):
  Obj(const Obj&){0} => clone(Obj):0
  Obj(Obj&&){0} => Obj&&:0
  ~Obj(){0} ~Obj(){-1}
 clone(Obj(2)):
  Obj(){2} => clone(Obj):2
  Obj(Obj&&){2} => Obj&&:2
  ~Obj(){2} ~Obj(){-1}

 apply(obj, clone):
  Obj(const Obj&){0} => clone(Obj):0
  Obj(Obj&&){0} Obj(Obj&&){0} ~Obj(){-1} ~Obj(){-1} => Obj&&:0
  ~Obj(){0}
 …
 apply(Obj(2), clone):
  Obj(){2} Obj(Obj&&){2} => clone(Obj):2
  Obj(Obj&&){2} Obj(Obj&&){2} ~Obj(){-1} ~Obj(){-1} => Obj&&:2
  ~Obj(){2} ~Obj(){-1}

 op_klvr(obj):
  Obj(const Obj&){0} => clone(Obj):0
  Obj(Obj&&){0} ~Obj(){-1} => Obj&&:0
  ~Obj(){0}
 op_klvr(Obj(3)):
  Obj(){3} Obj(const Obj&){3} => clone(Obj):3
  Obj(Obj&&){3} ~Obj(){-1} => Obj&&:3
  ~Obj(){3} ~Obj(){3}
 op_rvr(Obj(3)):
  Obj(){3} Obj(Obj&&){3} => clone(Obj):3
  Obj(Obj&&){3} ~Obj(){-1} => Obj&&:3
  ~Obj(){3} ~Obj(){-1}
 op_nr(Obj(3)):
  Obj(){3} Obj(Obj&&){3} => clone(Obj):3
  Obj(Obj&&){3} ~Obj(){-1} => Obj&&:3
  ~Obj(){3} ~Obj(){-1}
~Obj(){0}

We can see that apply(Obj(2), clone) generates one more move-construction than clone(Obj(2)), and this is expected from our implementation. We can also see the differences in the last group, where the use of op_klvr, op_rvr, or op_nr can affect whether copy-construction or move-construction is used. I would like to make op_nr work on an lvalue too (so the last code line can be uncommented).

I have finally implemented a version of compose with tag dispatching 9, treating reference types and non-reference types differently. The strategy is as follows:

  • If template argument is a reference type, the old logic still applies.
  • If template argument is not a reference type, a temporary object will be constructed in the pass-by-value parameter (with either the copy constructor or move constructor), and its rvalue reference will be used to invoke the reference-branch logic. An extra move operation may result, so it is still better to use ‘compose’ if it is known that the argument will be an value. (Alas, a lambda is only a function, but not a type-deducing function template. Damn, Scott hit me right on the face, again, with his nice introduction of the C++14 generic lambdas in Effective Modern C++. It provides for a far nicer solution. I won’t change the content here, but the part about compose is now largely obsoleted. Check out ‘Generic Lambdas and the compose Function’ for an update.—I hate love you, Scott!)

The extra move overhead makes this solution less attractive, but it only adds to the choices. Also, it would be a little awkward if one was forced to type ‘compose’. So my final compose is here (test9.cpp):

template <typename Tp>
auto compose_ref()
{
    return apply<Tp>;
}

template <typename Tp, typename Fn, typename... Fargs>
auto compose_ref(Fn fn, Fargs... args)
{
    return [=](Tp&& x) -> decltype(auto)
    {
        return fn(compose_ref<Tp>(args...)(forward<Tp>(x)));
    };
}

template <typename Tp, typename... Fargs>
auto compose_impl(false_type, Fargs... args)
{
    return [=](Tp x) -> decltype(auto)
    {
        return compose_ref<Tp&&>(args...)(move(x));
    };
}

template <typename Tp, typename... Fargs>
auto compose_impl(true_type, Fargs... args)
{
    return compose_ref<Tp>(args...);
}

template <typename Tp, typename... Fargs>
auto compose(Fargs... args)
{
    return compose_impl<Tp>(
        typename is_reference<Tp>::type(), args...);
}

Lessons learnt:

  • C++ programmers should always read Scott’s books (at least 99.99% should).
  • Although type deduction is very helpful, one needs to understand its rules and what auto actually means in each case; otherwise it is easy to make (terrible) mistakes.

  1. Scott Meyers: Effective C++. Addison-Wesley, 3rd edition, 2005. 
  2. Scott Meyers: More Effective C++. Addison-Wesley, 1996. 
  3. Scott Meyers: Effective STL. Addison-Wesley, 2001. 
  4. Scott Meyers: Effective Modern C++. O’Reilly Media, 2014. 
  5. Yongwei Wu: Study Notes: Functional Programming with C++
  6. Thomas Becker: Rvalue References Explained, p. 8
  7. Cppreference.com: std::enable_if
  8. Scott Meyers: Universal References in C++11
  9. David Abrahams and Douglas Gregor: Generic Programming in C++: Techniques, section ‘Tag Dispatching’

Installing Clang 3.5 for Windows

I had used LLVM 3.4 on Windows for quite some time. It had worked well, and had all the features I needed—mostly the beautiful C++11/C++14 compiler and the easy-to-use Clang-Format. However, the C++ compiler only works when some specific GCC versions are installed together, and the GCC version 4.6.3 I installed for Clang has a conflict with the GCC 4.9 I use. The major issue is the C++ run-time library libstdc++-6.dll, which actually has many variants due to the combination of different thread models and different exception handling methods. The result is that GCC 4.9 generated executables will crash when the libstdc++-6.dll from GCC 4.6.3 appears earlier in path, and Clang generated executables will crash when the libstdc++-6.dll from GCC 4.9 appears earlier in path. I do not like this situation. So recently I tried new combinations when I installed LLVM 3.5, and made sure everything work together. I would like to share the result.

Let me first list the binary files one needs to download:

I install Clang to the default location, C:\Program Files (x86)\LLVM. For the rest of this article, I assume GCC 4.9.2 is extracted to C:\ (so all files are under C:\mingw32), and GCC 4.8.2 is extracted to C:\Temp (all files are under C:\Temp\mingw32).

Although I need GCC 4.9 for the best and latest C++ features, Clang does not work with it. One can tell from the error output of Clang that it should work with the MinGW-w64 GCC 4.8.2:

ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.0"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.0/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.0/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.0/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.1"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.1/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.1/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.1/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.2"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.2/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.2/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.2/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.3"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.3/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.3/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.7.3/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.0"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.0/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.0/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.0/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.1"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.1/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.1/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.1/backward"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.2"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.2/x86_64-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.2/i686-w64-mingw32"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0/../../../include/c++/4.8.2/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.0/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.0/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.0/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.1/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.1/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.1/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.2/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.2/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.2/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.3/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.3/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.7.3/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.0/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.0/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.0/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.1/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.1/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.1/include/c++/backward"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.2/include/c++"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.2/include/c++/mingw32"
ignoring nonexistent directory "c:/MinGW/lib/gcc/mingw32/4.8.2/include/c++/backward"
ignoring nonexistent directory "/usr/include/c++/4.4"
ignoring nonexistent directory "/usr/local/include"
ignoring nonexistent directory "C:\Program Files (x86)\LLVM\bin\..\lib\clang\3.5.0\../../../x86_64-w64-mingw32/include"
ignoring nonexistent directory "/mingw/include"
ignoring nonexistent directory "c:/mingw/include"
ignoring nonexistent directory "/usr/include"

(As one may expect from the error messages, the official MinGW GCC, currently at version 4.8.1, also works with Clang. I personally prefer MinGW-w64, as its GCC is more usable—e.g., the MinGW version supports only Win32 threads, and therefore does not support std::thread. MinGW does not provide GCC 4.9 yet, and you can’t put C:\MinGW\bin in the path, if you want to use MinGW-w64 GCC 4.9 simultaneously. You do need to put either C:\MinGW\bin or C:\mingw32\bin—for MinGW-w64 GCC 4.9—in the path, as Clang cannot find a working GCC for linking otherwise. If you use only MinGW GCC 4.8.1, or only MinGW-w64 GCC 4.9, this configuration works.)

Now back to MinGW-w64 GCC 4.8.2. Depending on the size of your hard disk, you may want to tailor it. In my case, I removed all traces of Fortran, Ada, and Objective-C, as well as build-info.txt, etc, license, opt, and shared from C:\Temp\mingw32. After that, you need to do the following to make GCC 4.8.2 work for Clang:

  • Make directory c++ under C:\Temp\mingw32\include.
  • Make directory 4.8.2 under C:\Temp\mingw32\include\c++.
  • Copy all contents under C:\Temp\mingw32\i686-w64-mingw32\include\c++ to C:\Temp\mingw32\include\c++\4.8.2.
  • Move all contents under C:\Temp\mingw32 to C:\Program Files (x86)\LLVM, merging with existing directories there.
  • Remove the empty C:\Temp\mingw32.

You can now add both C:\mingw32\bin and C:\Program Files (x86)\LLVM to the path: both Clang and GCC are at your hand and won’t conflict with each other.

A Complaint of ODF’s Asian Language Support

I have recently read about news about better support for ODF from Google. The author then went on to complain that neither Google nor Microsoft makes ‘it easy to use ODF as part of a workflow’. This reminds me that maybe I should write down a long-time complaint I have for ODF.

I have always loved open standards. However, there are not only open and proprietary standards, there are also good and bad standards. ODF looks pretty bad regarding Asian language support. It can be powerfully demonstrated by this image:

ODF Issue

If you are interested in it, you can download the document yourself. It simply contains four lines:

  • The first line has a left quotation mark, the English word ‘Test’, and the corresponding Chinese word. It looks OK.
  • The second line is a duplication of the first line, with an additional colon added at the beginning. It immediately changes the font of the left quotation mark.
  • The third line is a duplication of the second line, with the Chinese word removed. Both quotation marks are now using the default Western font ‘Times New Roman’.
  • The fourth line is a duplication of the third line, with the leading colon removed. Weirdly enough, the left quotation mark now uses the Chinese font. (This may be related to my using the Chinese OpenOffice version or Chinese Windows OS.)

Is it ridiculous that adding or removing a character can change how other characters are rendered? Still, I would not blog about it, if it had only been a bug in OpenOffice (actually I filed three bug reports back in 2006—more ancient than I thought—and this bug remains unfixed ). It actually seems a problem in the ODF standard. After extracting the content from the .ODT file (as a zip file), I can shrink the content of the document to these XML lines (content.xml with irrelevant contents removed and the result reformatted):

<office:font-face-decls>
<style:font-face
    style:name="Times New Roman"
    style:font-family-generic="roman"
    style:font-pitch="variable"/>
<style:font-face
    style:name="宋体"
    style:font-family-generic="system"
    style:font-pitch="variable"/>
</office:font-face-decls>
<office:automatic-styles>
<style:style
    style:name="P1"
    style:family="paragraph"
    style:parent-style-name="Standard">
<style:text-properties
    fo:font-size="12pt" fo:language="en" fo:country="GB"
    style:language-asian="zh" style:country-asian="CN"/>
</style:style>
</office:automatic-styles>
<office:body>
<office:text>
<text:p text:style-name="P1">“Test测试”</text:p>
<text:p text:style-name="P1">:“Test测试”</text:p>
<text:p text:style-name="P1">:“Test”</text:p>
<text:p text:style-name="P1">“Test”</text:p>
</office:text>
</office:body>

The problem is that instead of specifying a single language on any text, it specifies both a ‘fo:language’ and a ‘style:language-asian’. The designer of this feature definitely did not think carefully about the fact that many symbols exist in both Asian and non-Asian contexts and can often be rendered differently!

When I repeated the same process in Microsoft Word (on Windows), all text appeared correctly—Microsoft applications recognize which keyboard I use and which language it represents. Pasting as plain text introduced one error (as no language information is present). Even in that case, fixing the problem is easier. In OpenOffice I have to change the font manually, but in Microsoft Word I only need to specify the correct language (‘Office, this is English, not Chinese’). It is much more intuitive and natural.

I also analysed the XML in the resulting .DOCX file. Its styles.xml contained this:

<w:lang w:val="en-US" w:eastAsia="zh-CN" w:bidi="ar-SA"/>

So these are default languages. I had to use UK English and Traditional Chinese to force Word to specify the languages in the document explicitly. The embedded document.xml now contains content like the following:

<w:p>
<w:r>
<w:rPr>
<w:rFonts w:eastAsia="PMingLiU" w:hint="eastAsia"/>
<w:lang w:eastAsia="zh-TW"/>
</w:rPr>
<w:t>“</w:t>
</w:r>
<w:r>
<w:rPr>
<w:rFonts w:eastAsia="PMingLiU"/>
<w:lang w:val="en-GB" w:eastAsia="zh-TW"/>
</w:rPr>
<w:t>Test</w:t>
</w:r>
<w:r>
<w:rPr>
<w:rFonts w:eastAsia="PMingLiU" w:hint="eastAsia"/>
<w:lang w:eastAsia="zh-TW"/>
</w:rPr>
<w:t>測試”</w:t>
</w:r>
</w:p>
...
<w:p>
<w:r>
<w:rPr>
<w:rFonts w:eastAsia="PMingLiU"/>
<w:lang w:val="en-GB" w:eastAsia="zh-TW"/>
</w:rPr>
<w:t>“Test”</w:t>
</w:r>
</w:p>

We can argue the structure is somewhat similar (compare ‘w:val’ in <w:lang> with ‘fo:language’ and ‘fo:country’, and ‘w:eastAsia’ with ‘style:language-asian’ and ‘style:country-asian’), but the semantics are obviously different, and text of different languages is not mixed together. The English text has the language attribute <w:lang w:val="en-GB" w:eastAsia="zh-TW"/>, and the Chinese text has only <w:lang w:eastAsia="zh-TW"/>. It looks to me a more robust approach to processing mixed text.

Although it might be true that Microsoft lobbied strongly to get OOXML approved as an international standard, I do not think ODF’s openness alone is enough to make people truly adopt it.