null

2015-01-29

Desktop tweaks

This post is just a list of some of the desktop tweaks I did to help me set them up again if needed :)

Change Ctrl-U to kill-line instead of View Source in opera


First, edit ~/.gtkrc-2.0:

binding "gtk-clear-text-entry" {
    bind "<ctrl>u" { "delete-from-cursor" (paragraph-ends, -1) }
    bind "<ctrl>k" { "delete-from-cursor" (paragraph-ends, 1) };
}
class "GtkEntry" binding "gtk-clear-text-entry"
class "GtkTextView" binding "gtk-clear-text-entry"


For gtk3:

edit ~/.local/share/themes/CtrlU/gtk-3.0/gtk-keys.css:
/*
 * Bindings for GtkTextView and GtkEntry for Ctrl-U, Ctrl-K
 */
@binding-set gtk-ctrlu-text-entry {
  bind "<ctrl>u" { "delete-from-cursor" (paragraph-ends, -1) };
  bind "<ctrl>k" { "delete-from-cursor" (paragraph-ends, 1) };
}

entry {
  -gtk-key-bindings: gtk-ctrlu-text-entry;
}

textview {
  -gtk-key-bindings: gtk-ctrlu-text-entry;
}
edit ~/.config/gtk-3.0/settings.ini:
[Settings]
gtk-key-theme-name = CtrlU

This seems to be enough for Firefox-35 and Chromium-40 and Opera-27 to use Ctrl-U in input fields.

To disable the Ctrl-U - View Source binding completely in Opera,
edit ~/.config/opera/Preferences, add/modify the Keybindings section:

"Keybindings": {
      "Basic": {
         "ForceReload": [ "Shift+F5", "Ctrl+F5", "Ctrl+Shift+R" ],
         "ViewSource": [  ]
      },
      "Settings": {
         "AdvancedEnabled": true
      }
   },

See Ruarí’s blog for more customization options in Opera.

Fix the new snap-to-client behaviour of kwin


Kwin's window snapping algorithm was changed from snap-to-deco to snap-to-client which I personally find annoying (see Bug 325286). The current workaround is to use the Screen Snapping kwin-script by Thomas Lübking...
The KDE5 version: Screen Snapping 5.

Restoring top(1) sanity

The recent versions of top(1) on linux start up with some atrocious defaults bleeding my eyes out. To get back to a sane-looking top, add these to ~/.toprc:
top's Config File (Linux processes with windows)
Id:i, Mode_altscr=0, Mode_irixps=1, Delay_time=1.500, Curwin=0
Def fieldscur=¥&K¨³´»½@·º¹56ÄFÅ')*+,-./0128<>?ABCGHIJLMNOPQRSTUVWXYZ[\]^_`abcdefghij
    winflags=192564, sortindx=18, maxtasks=0, graph_cpus=0, graph_mems=0
    summclr=1, msgsclr=1, headclr=3, taskclr=1
Job fieldscur=¥¦¹·º(³´Ä»½@<§Å)*+,-./012568>?ABCFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij
    winflags=163124, sortindx=0, maxtasks=0, graph_cpus=2, graph_mems=0
    summclr=6, msgsclr=6, headclr=7, taskclr=6
Mem fieldscur=¥º»<½¾¿ÀÁMBNÃD34·Å&'()*+,-./0125689FGHIJKLOPQRSTUVWXYZ[\]^_`abcdefghij
    winflags=163124, sortindx=21, maxtasks=0, graph_cpus=2, graph_mems=0
    summclr=5, msgsclr=5, headclr=4, taskclr=5
Usr fieldscur=¥¦§¨ª°¹·ºÄÅ)+,-./1234568;<=>?@ABCFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij
    winflags=163124, sortindx=3, maxtasks=0, graph_cpus=2, graph_mems=0
    summclr=3, msgsclr=3, headclr=2, taskclr=3
Fixed_widest=0, Summ_mscale=2, Task_mscale=1, Zero_suppress=0

Nice, human readable config file, right? I'm not sure what special characters will be eaten by the grue during a copy-waste, so the file is available to download from here, too.

Fixing the broken line-editing in bash after a window resize


If you resize the window while you're running some program in bash (for example while editing a file in vi), bash (sometimes?) fails to update window sizes and line editing becomes completely messed up. The fix for this is the checkwinsize shell option. Just add this to your .bashrc:
shopt -s checkwinsize


Trying to get sane date formats with English locale in KDE


Ok, I don't get it why it has to be so hard...

So, KDE had a nice locale system, but they ditched it in favor of using QLocale, but QLocale is a bit lacking at the moment, so a lot of customization was lost. Now, at last they included the en_DK locale in the regional settings, but they somehow managed to botch it: the time separator in this locale is dot instead of colon, and the short date format is also some abomination, not the expected iso-date-format.

Apparently Qt supports en_SE though, which does work as I expect. Unfortunately this locale is not supported by my system (arch linux), so I had to cheat a bit: I created a symlink from the en_DK locale spec as en_SE (under /usr/share/i18n/locales), created a new entry for en_SE.UTF-8 in /etc/locale.gen and regenerated the locale database with locale-gen.

Now all is well (until the next update breaks it somehow again...)

2013-01-08

Quick and dirty hack to build OpenJDK6 with clang and libc++ on FreeBSD

FreeBSD is in the process of replacing the GNU toolchain with the LLVM based clang compiler suite. I wanted to check out how far they got in the latest release (9.1R), so I set out to build our internal test server running a jboss application server with clang and the new c++ standard library: libc++.

Unfortunately, an important patch hasn't made it into the 9.1 release (without this patch it's not possible to statically link programs with -stdlib=libc++), so I switched my sources to stable/9 and rebuilt the base system.

Instructions for using the new toolchain in FreeBSD can by found here, and for using libc++ instead of libstdc++ here, but in a nutshell, you just have to add the following lines to /etc/make.conf:

# use clang:
CPP=clang-cpp
CC=clang
CXX=clang++
# use libc++ instead of libstdc++:
CXXFLAGS+=-stdlib=libc++
# build libc++:
WITH_LIBCPLUSPLUS=yes
# skip building gcc:
WITHOUT_GCC=yes

Note: first you'll have to build and install the base system without setting -stdlib=libc++ in CXXFLAGS if you don't already have libc++ installed. Then rebuild everything with the above settings to let the base system link against libc++ instead of libstdc++.

Most of the ports I needed built fine, but some didn't use the CXXFLAGS from make.conf, so I had to trick them by adding the following lines to make.conf:

.if ${.CURDIR:M*/usr/ports/archivers/p7zip*}
CXX+=-stdlib=libc++
.endif
.if ${.CURDIR:M*/usr/ports/databases/db42*}
CXX+=-stdlib=libc++
.endif
.if ${.CURDIR:M*/usr/ports/java/openjdk6*}
CXX+=-stdlib=libc++
.endif

Now everything was building with libc++ but the openjdk6 build blew up, because they defined their own assert() macro in hotspot/src/share/vm/utilities/debug.hpp which got wiped when one of the libc++ headers included <assert.h> [Quote from the standard: "The assert macro is redefined according to the current state of NDEBUG each time that <assert.h> is included."]. I'm surprised this issue hasn't bitten them yet...

I changed the macro definition in debug.hpp to assert_vm (since this macro is used solely in the vm subsystem) and updated all references to it. This wasn't so easy, as the "real" assert() was also used in some files, and my sed script replaced some of those at first, too, but after some trial-and-error, I got it right (see patch-zzz-assert-vm). The patch also fixes a minor typo in debug.hpp that would cause a compilation failure if USE_REPEATED_ASSERTS were defined (a backlash was forgotten from the first line of the macro definition).

With this patch the java/openjdk6 port built successfully, but libmawt.so was still linking against libstdc++, so I had to dig deeper into the build scripts / Makefiles. It turned out that the Makefile under jdk/make/sun/headless wasn't requesting to use a c++ compiler to do the linking, even though it links with -lstdc++, so libmawt.so was linked with CC instead of CXX. I fixed this with patch-jdk-make-sun-headless.
[Note: apparently linking libmawt.so with -lstdc++ on FreeBSD is wrong, as libmawt.so isn't linked agains libstdc++ on linux, for example. I'll revise this section as soon as I find out why -libstdc++ is added to the link line here...]

After a short recompile (an hour or so on this old box ;), I got everything up and running built with clang and linked against libc++. My initial tests with jboss went well, nothing scary happened so far.

Update: I filed a bug report with a proposed patch to openjdk: Bug 100297 (probably moved to Bug 8007770 by the java devs while I wasn't paying attention), but I won't have time now to find a sponsor for this among the openjdk folks, so if you have any connections with openjdk devs, I'd be thankful if you could help me push this along.

I'd like here to thank dim and various other folks at irc://irc.oftc.net/#freebsd-clang for their help with this experiment, and the clang and FreeBSD developers for the wonderful software they created.

2012-11-28

Getting FreeBSD to recognize my Defy's SD card

When I connect my Motorola Defy phone to my FreeBSD desktop via USB, the usb subsystem checks if there's any mountable media available on the newly connected device. Unfortunately the phone only switches to "Memory card access" mode after it notices the connection, and by this time the media detection from the desktop fails with "NOT READY" error.

Apparently the device will only be rescanned ("retasted") when a write request is issued to the device, so a manual workaround is to issue the following command after the phone has switched to "Memory card access" mode:

dd count=0 if=/dev/null of=/dev/da0

To automate this, I created a small shell script that executes this "fake" write after a short delay, and added a devd rule to invoke this script when the usb device is detected:

/opt/DefySD.sh

#!/bin/sh

( /bin/sleep 3 && /bin/dd count=0 if=/dev/null of=/dev/$1 >/dev/null 2>/dev/null ) &


/usr/local/etc/devd/DefySD.conf

notify 200 { 
    match "cdev" "da[0-9]+$";
    match "system" "DEVFS";
    match "subsystem" "CDEV";
    match "type" "CREATE";
    action "/opt/DefySD.sh $cdev"; 
};

After restarting devd, I could auto-mount my SD card from KDE like any other "normal" USB stick.

2012-06-03

C++11 tuple implementation details (Part 1)

In his "Variadic Templates are Funadic" talk at GoingNative 2012 Andrei Alexandrescu outlines a "recursive" implementation of std::tuple. He also notes that most implementations arrange tuple members in memory in the "wrong" order, that is, std::tuple<int, double, std::string> will have a memory layout where the std::string comes first and the int comes last. The straightforward recursive implementation he presents also has this property.

I checked out the implementation of std::tuple in libc++, and their implementation has the "sane" memory layout, and it's also non-recursive, which — according to Howard Hinnant, the primary author of libc++'s tuple implementation — has other benefits, like faster compile times, too.

In this post I'll try to explain the implementation details of a flat (non-recursive) tuple. The implementation presented here is based on the libc++ version — in fact, it's mostly copy-waste, I just simplified some of the hairy bits and omitted some parts, like the allocator related constructors, exception specifications, tie and tuple_cat. I'll return to them in a follow-up post. Some parts (like our internal TupleSize and TupleElement) are a bit more complicated than the ones in the standard library, because we can't just assume/dictate implementation details in the std namespace and we need compatibility with the standard tuple-like classes.

Tuple synopsis

First, let's see what our Tuple should look like:

template <typename... T>
class Tuple {
public:
    Tuple();

    explicit Tuple(const T&...);

    template <typename... U>
    explicit Tuple(U&&...);

    Tuple(const Tuple&);

    Tuple(Tuple&&);

    template <typename... U>
    Tuple(const Tuple<U...>&);

    template <typename... U>
    Tuple(Tuple<U...>&&);

    Tuple& operator=(const Tuple&);

    Tuple& operator=(Tuple&&);

    template <typename... U>
    Tuple& operator=(const Tuple<U...>&);

    template <typename... U>
    Tuple& operator=(Tuple<U...>&&);

    void swap(Tuple&);
};
  
template <typename... T> typename tuple_size<Tuple<T...>>;

template <size_t I, typename... T> typename tuple_element<I, Tuple<T...>>;

// element access:

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type&
get(Tuple<T...>&);

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type const&
get(const Tuple<T...>&);

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type&&
get(Tuple<T...>&&);

// relational operators:

template<typename... T, typename... U>
bool operator==(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator<(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator!=(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator>(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator<=(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator>=(const Tuple<T...>&, const Tuple<U...>&);

template <typename... Types>
void swap(Tuple<Types...>& x, Tuple<Types...>& y);

Notes on namespaces

I'm planning to use this Tuple implementation in a project (a simple OpenGL game on android), thus the Tuple class is in namespace migl2, the namespace used in this project. All implementation details are in namespace migl2::detail, and some template specializations are in (or lifted into) namespace std. I'm using namespace std inside namespace migl2::detail, so std::forward, std::enable_if and others will be unqualified there. The overall layout is something like this:

namespace migl2 {
using std::size_t;

// forward declaration of our Tuple template
template <typename... Ts_>
class Tuple;

namespace detail {
using namespace std;
using std::swap; // needed for primitive types, as ADL won't kick in for them

/*** Tuple implementation details come here ***/

} // end namespace detail

/*** user-visible Tuple and related functions come here ***/

} // end namespace migl2

namespace std {

/*** specializations of tuple_size, tuple_element and get for our Tuple come here ***/

} // end namespace std

A slightly odd-looking thing here is the using std::swap; line right after using namespace std. At first glance it'd seem superfluous, but it's in fact necessary. We'll use unqualified calls to swap() to enable Argument Dependent Lookup. Unqualified calls to swap would work for user defined types if they also provide their swap override, but it won't work for primitive types (as they're not in namespace std) or user-defined types that don't provide their specialized swap(), since the generic std::swap() is not picked up with ADL in this case, as we'll have our own swap() defined for TupleLeaf in the detail namespace, and without that "extra" using std::swap the compiler would try to use that for all types that don't provide their own overload.

The non-recursive approach

The basic idea behind the non-recursive tuple implementation is that tuple elements are stored in TupleLeaf base classes, but whereas the recursive implementation uses a deep class hierarchy, we'll use multiple-inheritance. In pseudo-code:

template<typename T0, typename T1, ..., typename Tn>
class PseudoTuple : TupleLeaf<0, T0>, TupleLeaf<1, T1>, ..., TupleLeaf<n, Tn> {
   ...
};

Each leaf has an index, so that each base-class becomes unique even if the types they contain are identical, so we can access the nth element with a simple static_cast:

static_cast<TupleLeaf<0, T0>*>(this);
// ...
static_cast<TupleLeaf<n, Tn>*>(this);

TupleLeaf

Let's start with our basic building-block, the TupleLeaf template:

// TupleLeaf

template <size_t I_, typename ValueType_,
        bool IsEmpty_ = is_empty<ValueType_>::value
#if __has_feature(is_final)
            && !__is_final(ValueType_)
#endif
    >
class TupleLeaf;

template <size_t I, typename ValueType, bool IsEmpty>
inline void swap(TupleLeaf<I, ValueType, IsEmpty>& a,
                 TupleLeaf<I, ValueType, IsEmpty>& b) {
    swap(a.get(), b.get());
}

template <size_t I_, typename ValueType_, bool IsEmpty_>
class TupleLeaf {
    ValueType_ value_;
    
    TupleLeaf& operator=(const TupleLeaf&) = delete;
public:
    TupleLeaf()
            : value_() {
        static_assert(!is_reference<ValueType_>::value,
            "Attempt to default construct a reference element in a tuple");
    }

    TupleLeaf(const TupleLeaf& t)
            : value_(t.get()) {
        static_assert(!is_rvalue_reference<ValueType_>::value,
            "Can not copy a tuple with rvalue reference member");
    }

    template <typename T, typename = typename enable_if<
            is_constructible<ValueType_, T>::value>::type>
    explicit TupleLeaf(T&& t)
            : value_(forward<T>(t)) {
        static_assert(!is_reference<ValueType_>::value ||
                (is_lvalue_reference<ValueType_>::value &&
                 (is_lvalue_reference<T>::value ||
                  is_same<typename remove_reference<T>::type,
                    reference_wrapper<
                        typename remove_reference<ValueType_>::type
                    >
                 >::value)) ||
                (is_rvalue_reference<ValueType_>::value &&
                 !is_lvalue_reference<T>::value),
            "Attempted to construct a reference element in a tuple with an rvalue");
    }

    template <typename T>
    explicit TupleLeaf(const TupleLeaf<I_, T>& t) 
            : value_(t.get()) {
    }

    template <typename T>
    TupleLeaf& operator=(T&& t) {
        value_ = forward<T>(t);
        return *this;
    }

    int swap(TupleLeaf& t) {
        migl2::detail::swap(*this, t);
        return 0;
    }

    ValueType_& get() {
        return value_;
    }

    const ValueType_& get() const {
        return value_;
    }
};
Lines 3-9:
Here we declare our TupleLeaf template, and set the IsEmpty value to true when we can use Empty Base Class Optimization. A little bit of trickery is needed here: if the implementation supports final classes, then we must check if our ValueType_ is final or not. Since we can't subclass a final class, we cannot use EBCO in that case.
Lines 11-15:
Swap two TupleLeafs by swapping the contained elements. We'll use this from the swap member functions.
Lines 17-75:
The TupleLeaf implementation for the generic case (no Empty Base Class Optimization). We disable the normal copy-assignment (line 17), as we'll always use the forwarding copy-assignment (lines 53-57). The only interesting bit here is the return type of swap (lines 59-62). Normally, it should be void, but we'll later call this swap member from our TupleImpl::swap with template-pack expansion, and to do that we need a function with a return type. See the swallow function below.

Next, we specialize our TupleLeaf for the case when we can use the Empty Base Class Optimization, so as to not waste space for empty tuple members:

// TupleLeaf specialization in case we can use Empty Base Class Optimization:

template <size_t I_, typename ValueType_>
class TupleLeaf<I_, ValueType_, true>
        : private ValueType_ {

    TupleLeaf& operator=(const TupleLeaf&) = delete;
public:
    TupleLeaf() {
    }

    TupleLeaf(const TupleLeaf& t)
            : ValueType_(t.get()) {
        static_assert(!is_rvalue_reference<ValueType_>::value,
            "Can not copy a tuple with rvalue reference member");
    }

    template <typename T, typename = typename enable_if<
            is_constructible<ValueType_, T>::value>::type>
    explicit TupleLeaf(T&& t)
            : ValueType_(forward<T>(t)) {
    }

    template <typename T>
    explicit TupleLeaf(const TupleLeaf<I_, T>& t)
            : ValueType_(t.get()) {
    }

    template <typename T>
    TupleLeaf& operator=(T&& t) {
        ValueType_::operator=(forward<T>(t));
        return *this;
    }

    int swap(TupleLeaf& t) {
        migl2::detail::swap(*this, t);
        return 0;
    }

    ValueType_& get() {
        return static_cast<ValueType_&>(*this);
    }

    const ValueType_& get() const {
        return static_cast<const ValueType_&>(*this);
    }
};

Some glue: TupleIndexes, TupleSize and TupleElements

We'll need indexes and corresponding types for our TupleLeafs. To handle their coupling we'll create two helper classes for storing them and corresponding templates to create them when needed:

// TupleIndexes

template <size_t... Is_>
struct TupleIndexes {
};

template <size_t Start_, typename TupleIndexes_, size_t End_>
struct MakeTupleIndexesImpl;

template <size_t Start_, size_t... Indexes_, size_t End_>
struct MakeTupleIndexesImpl<Start_, TupleIndexes<Indexes_...>, End_> {
    typedef typename MakeTupleIndexesImpl<Start_ + 1,
            TupleIndexes<Indexes_..., Start_>, End_>::type type;
};

template <size_t End_, size_t... Indexes_>
struct MakeTupleIndexesImpl<End_, TupleIndexes<Indexes_...>, End_> {
    typedef TupleIndexes<Indexes_...> type;
};

template <size_t End_, size_t Start_ = 0>
struct MakeTupleIndexes {
    static_assert(Start_ <= End_, "MakeTupleIndexes: invalid parameters");
    typedef typename MakeTupleIndexesImpl<Start_, TupleIndexes<>, End_>::type type;
};

MakeTupleIndexes creates a type that encodes the indexes from Start_ to End_, for example: TupleTypes<0, 1, 2>. It could be a bit simpler, but we'll extend the standard tuple with a constructor that takes less parameters than the actual number of tuple elements (and default-constructs the rest), and for that we'll need to be able to create TupleIndexes starting from an arbitrary index instead of 0. The same applies to MakeTupleTypes below. Both templates use a helper template to build their values incrementally. The end result is a typedef for the complete indexes and types.


Note: Since the time of writing, c++14 introduced std::index_sequence, since the concept was found to be useful in many situations. The implementation of the sequence generation can also be optimized: instead of the above described linear recursion one can use a logarithmic implementation, or the sequence generation could even be a compiler intrinsic. The tuple implementation could be updated to use the new index_sequence here.

// TupleTypes

template <typename... Ts_>
struct TupleTypes {
};

// TupleSize

template <typename T_>
struct TupleSize
        : public tuple_size<T_> {
};

template <typename T_>
struct TupleSize<const T_>
        : public TupleSize<T_> {
};

template <typename T_>
struct TupleSize<volatile T_>
        : public TupleSize<T_> {
};

template <typename T_>
struct TupleSize<const volatile T_>
        : public TupleSize<T_> {
};

template <typename... Ts_>
struct TupleSize<TupleTypes<Ts_...>>
        : public integral_constant<size_t, sizeof...(Ts_)> {
};

// specialization for Tuple

template <typename... Ts_>
struct TupleSize<Tuple<Ts_...>>
        : public integral_constant<size_t, sizeof...(Ts_)> {
};

Here we declare our special type-holder, TupleTypes and then we can define TupleSize for that using the sizeof... operator. TupleSize for our own Tuple uses TupleTypes. For all other types, we fall back on the standard tuple_size template, thus our internal TupleSize will work for std::tuple, std::pair and std::array, too. The cv-qualified types are forwarded to the implementation for the unqualified TupleTypes.

Similarly our internal TupleElement is defined for TupleTypes and Tuple, but falls back on the standard tuple_element for other types:

// TupleElement

template <size_t I_, typename T_>
class TupleElement : public tuple_element<I_, T_> {
};

template <size_t I_>
class TupleElement<I_, TupleTypes<>> {
public:
    static_assert(I_ != I_, "tuple_element index out of range");
};

template <typename H_, typename... Ts_>
class TupleElement<0, TupleTypes<H_, Ts_...>> {
public:
    typedef H_ type;
};

template <size_t I_, typename H_, typename... Ts_>
class TupleElement<I_, TupleTypes<H_, Ts_...>> {
public:
    typedef typename TupleElement<I_ - 1, TupleTypes<Ts_...>>::type type;
};

// specialization for Tuple

template <size_t I_, typename... Ts_>
class TupleElement<I_, Tuple<Ts_...>> {
public:
    typedef typename TupleElement<I_, TupleTypes<Ts_...>>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, const Tuple<Ts_...>> {
public:
    typedef typename add_const<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, volatile Tuple<Ts_...>> {
public:
    typedef typename add_volatile<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, const volatile Tuple<Ts_...>> {
public:
    typedef typename add_cv<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

TupleElement is a classic recursive template. We chomp off the types from the beginning of our list as we decrement the index (I_ in the main template at lines 19-23). The stop condition is when we reach I_ == 0 (lines 13-17). If the remaining TupleTypes is empty before we reach our stop condition, we signal an error with a static_assert (lines 7-11). The end result — if all goes well — is a typedef (TupleElement::type) corresponding to the I_th element in our TupleTypes. The specialization for our final Tuple uses TupleTypes adjusted for const and volatile qualifiers.


Note: TupleElement could be implemented by letting overload resolution find the correct type for us instead of the above presented linear recursion. See this other nice blog post about tuples for details.

Now we can return to our helper template that creates TupleTypes for us:

// MakeTupleTypes

template <typename TupleTypes_, typename Tuple_, size_t Start_, size_t End_>
struct MakeTupleTypesImpl;

template <typename... Types_, typename Tuple_, size_t Start_, size_t End_>
struct MakeTupleTypesImpl<TupleTypes<Types_...>, Tuple_, Start_, End_> {
    typedef typename remove_reference<Tuple_>::type TupleType;
    typedef typename MakeTupleTypesImpl<TupleTypes<Types_...,
            typename conditional<is_lvalue_reference<Tuple_>::value,
                // append ref if Tuple_ is ref
                typename TupleElement<Start_, TupleType>::type&,
                // append non-ref otherwise 
                typename TupleElement<Start_, TupleType>::type>::type>,
            Tuple_, Start_ + 1, End_>::type  type;
};

template <typename... Types_, typename Tuple_, size_t End_>
struct MakeTupleTypesImpl<TupleTypes<Types_...>, Tuple_, End_, End_> {
    typedef TupleTypes<Types_...> type;
};

template <typename Tuple_,
         size_t End_ = TupleSize<typename remove_reference<Tuple_>::type>::value,
         size_t Start_ = 0>
struct MakeTupleTypes {
    static_assert(Start_ <= End_, "MakeTupleTypes: invalid parameters");
    typedef typename MakeTupleTypesImpl<TupleTypes<>, Tuple_, Start_, End_>::type type;
};

MakeTupleTypes extracts the types from Tuple_ in the range [Start_ .. End_] and stores them in our TupleTypes type. The element-types are determined with the above defined TupleElement, and appended to a temporary list. As std::tuple_element (and consequently our TupleElement) doesn't work on reference types, we use a typedef for the reference-stripped type of Tuple_ (TupleType at line 8), but we convert the result type from TupleElement to a reference if the original Tuple_ was an lvalue_reference (types that were already reference-types in the original tuple are not touched by this transformation).

TupleImpl and swallow()

We're ready to assemble these pieces into our internal TupleImpl class that will be the basis of the final Tuple.

// TupleImpl

template <typename... Ts>
void swallow(Ts&&...) {
}

template <typename TupleIndexes_, typename... Ts_>
struct TupleImpl;

template <size_t... Indexes_, typename... Ts_>
struct TupleImpl<TupleIndexes<Indexes_...>, Ts_...>
        : public TupleLeaf<Indexes_, Ts_>... {
    template <size_t... FirstIndexes, typename... FirstTypes,
              size_t... LastIndexes, typename... LastTypes,
              typename... ValueTypes>
    explicit TupleImpl(
                TupleIndexes<FirstIndexes...>, TupleTypes<FirstTypes...>,
                TupleIndexes<LastIndexes...>, TupleTypes<LastTypes...>,
                ValueTypes&&... values)
            : TupleLeaf<FirstIndexes,
                    FirstTypes>(forward<ValueTypes>(values))...,
                    TupleLeaf<LastIndexes, LastTypes>()... {
    }

    template <typename OtherTuple>
    TupleImpl(OtherTuple&& t)
            : TupleLeaf<Indexes_, Ts_>(forward<
                    typename TupleElement<Indexes_,
                    typename MakeTupleTypes<OtherTuple>::type>::type
                    >(get<Indexes_>(t)))... {
    }

    template <typename OtherTuple>
    TupleImpl& operator=(OtherTuple&& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::operator=(forward<
                    typename TupleElement<Indexes_,
                    typename MakeTupleTypes<OtherTuple>::type>::type
                    >(get<Indexes_>(t)))...);
        return *this;
    }

    TupleImpl& operator=(const TupleImpl& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::operator=(static_cast<
                const TupleLeaf<Indexes_, Ts_>&>(t).get())...);
        return *this;
    }

    void swap(TupleImpl& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::swap(
            static_cast<TupleLeaf<Indexes_, Ts_>&>(t))...);
    }
};
Lines 3-5:
The swallow() functions is just a little trick to allow us to use template-parameter-pack expansion at places where it wouldn't be possible otherwise: when we want to call foo() for each element of the template-parameter-pack, we call swallow() with the expansion like this:
template<typename... Ts>
void fooCaller(Ts... ts) {
    swallow(foo(ts)...);
}
The parameters of swallow() bind to anything except void, hence we'll need to make sure that our foo() does return something (is not void foo()). That's why we have the "strange" signature of our TupleLeaf::swap() function. Since the function itself doesn't do anything, the actuall call will be optimized away, and the only visible effect will be that foo() will be called for each element.
Lines 7-8:
The first template parameter of our TupleImpl template will be our TupleIndexes, and the rest are the actual types stored in the tuple. We'll immediately specialize this template declaration using actual indexes (as non-type template parameters) below.
Lines 10-12:
Here's our (only) specialization using actual indexes, and fixing the first type parameter to be TupleIndexes, and as we mentioned at the beginning, we're using multiple inheritance from TupleLeaf to build our class. The indexes and corresponding types are expanded in tandem, forming the base-classes.
Lines 13-23:
This is our "standard" constructor. As mentioned before, we'll allow construction of our final Tuple with less parameters than tuple elements. To allow this, this TupleImpl constructor splits the parameters in two, and expands them separately. The sum of the parameters of course must match the actual number of elements, but we'll take care of that in the final Tuple implementation.
Lines 25-31:
This is our "converting" constructor. We extract the elements from OtherTuple with get() expanded for each index our TupleImpl has, and forward them to the corresponding TupleLeafs. Since std::forward requires an explicit type specifier, we determine the correct type to use by building TupleTypes from OtherTuple and extracting the required type using TupleElement.
Lines 23-40:
This is our "converting" (or forwarding) assignment operator. It's pretty similar to our "converting" constructor above, we just use the swallow() function to call operator= of our TupleLeafs with corresponding elements from OtherTuple
Lines 42-46:
We need to define the "standard" assignment operator, too, because we explicitly disabled the standard operator= in our TupleLeaf (we only use the forwarding assignment operator), so the compiler cannot create the default assignment operator for us (as that would use TupleLeaf's default assignment operator, too).
Lines 48-51:
TupleImpl::swap() swaps each leaf piecewise using the swallow() trick.


Note: The swallow() implementation presented here processes the arguments in implementation-defined order. We could force left-to-right evaluation though by turning swallow into a struct with a variadic constructor and using brace-init like this: swallow{(foo(Args), 0)...}. Also note the use of the comma operator in this expansion: using this method to call swallow lets us use even void functions (no need for the trickery with the internal swap function above).

Some SFINAE helpers: TupleLike, TupleConvertible and TupleAssignable

The following templates will be used by our final Tuple class to disable some template instantiations (via SFINAE).

// TupleLike

template <typename T_>
struct TupleLike 
        : public false_type {
};

template <typename T_>
struct TupleLike<const T_>
        : public TupleLike<T_> {
};

template <typename T_>
struct TupleLike<volatile T_>
        : public TupleLike<T_> {
};

template <typename T_>
struct TupleLike<const volatile T_>
        : public TupleLike<T_> {
};

template <typename... Ts_>
struct TupleLike<Tuple<Ts_...>>
        : public true_type {
};

template <typename... Ts_>
struct TupleLike<TupleTypes<Ts_...>>
        : public true_type {
};

template <typename... Ts_>
struct TupleLike<std::tuple<Ts_...>>
        : public true_type {
};

template <typename First_, typename Second_>
struct TupleLike<std::pair<First_, Second_>>
        : public true_type {
};

template <typename T_, size_t N_>
struct TupleLike<std::array<T_, N_>>
        : public true_type {
};

TupleLike is a simple traits-template to check if the given type can be handled like a tuple, that is: tuple_size, tuple_element and get will work with it. The default implementation just inherits std::false_type, then we specialize it for our final Tuple, our internal TupleTypes and the standard tuple-like classes (std::tuple, std::pair and std::array).

// TupleConvertible

template <bool IsSameSize_, typename From_, typename To_>
struct TupleConvertibleImpl
        :  public false_type {
};

template <typename From0_, typename... FromRest_,
        typename To0_, typename... ToRest_>
struct TupleConvertibleImpl<true, TupleTypes<From0_, FromRest_...>,
            TupleTypes<To0_, ToRest_...>>
        : public integral_constant<bool,
            is_convertible<From0_, To0_>::value &&
            TupleConvertibleImpl<true, TupleTypes<FromRest_...>,
                TupleTypes<ToRest_...>>::value> {
};

template <>
struct TupleConvertibleImpl<true, TupleTypes<>, TupleTypes<>>
        : public true_type {
};

template <typename From_, typename To_,
         bool = TupleLike<typename remove_reference<From_>::type>::value,
         bool = TupleLike<typename remove_reference<To_>::type>::value>
struct TupleConvertible
        : public false_type {
};

template<typename From_, typename To_>
struct TupleConvertible<From_, To_, true, true>
        : public TupleConvertibleImpl<
            TupleSize<typename remove_reference<From_>::type>::value
                == TupleSize<typename remove_reference<To_>::type>::value,
            typename MakeTupleTypes<From_>::type,
            typename MakeTupleTypes<To_>::type> {
};

TupleConvertible is similar to std::is_convertible: it just checks that each tuple element of From_ is convertible to the corresponding element of To_. The default TupleConvertible template inherits std::false_type (lines 23-28). The two bool template parameters are defaulted to true if From_ and To_ are both TupleLike. We then specialize this template for the case when both are indeed tuple-like and defer the work to TupleConvertibleImpl (lines 30-37). We need this trick, because our TupleConvertibleImpl's first parameter is a bool indicating that From_ and To_ have the same number of elements. We check that with TupleSize, but it would blow up for non-tuple-like types, hence we can only use it when we're sure that both From_ and To_ are indeed tuple-like.

Once we get the size-match handled, TupleConvertibleImpl is pretty straightforward: we start with a default false_type (lines 3-6), then specialize for same-size tuples. This checks if the first elements are convertible then recursively checks the rest of the elements (lines 8-16).
The stop condition is when we reach empty TupleTypes<>, which are considered convertible (lines 18-21).

TupleAssignable is just like TupleConvertible, but we're using std::is_assignable in place of std::is_convertible:

// TupleAssignable

template <bool IsSameSize_, typename Target_, typename From_>
struct TupleAssignableImpl
        :  public false_type {
};

template <typename Target0_, typename... TargetRest_,
         typename From0_, typename... FromRest_>
struct TupleAssignableImpl<true, TupleTypes<Target0_, TargetRest_...>,
            TupleTypes<From0_, FromRest_...>>
        : public integral_constant<bool,
            is_assignable<Target0_, From0_>::value &&
            TupleAssignableImpl<true, TupleTypes<TargetRest_...>,
                TupleTypes<FromRest_...>>::value> {
};

template <>
struct TupleAssignableImpl<true, TupleTypes<>, TupleTypes<>>
        : public true_type {
};

template <typename Target_, typename From_,
         bool = TupleLike<typename remove_reference<Target_>::type>::value,
         bool = TupleLike<typename remove_reference<From_>::type>::value>
struct TupleAssignable
        : public false_type {
};

template<typename Target_, typename From_>
struct TupleAssignable<Target_, From_, true, true>
        : public TupleAssignableImpl<
            TupleSize<typename remove_reference<Target_>::type>::value
                == TupleSize<typename remove_reference<From_>::type>::value,
            typename MakeTupleTypes<Target_>::type,
            typename MakeTupleTypes<From_>::type> {
};

Helper templates for the relational operators: TupleEqual and TupleLess

The last detail (pun intended) we need are two helper templates to evaluate equals and less-than for tuples:

// TupleEqueal

template <size_t I_>
struct TupleEqual {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_& t1, const Tuple2_& t2) {
        return TupleEqual<I_ - 1>()(t1, t2) &&
            get<I_ - 1>(t1) == get<I_ - 1>(t2);
    }
};

template<>
struct TupleEqual<0> {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_&, const Tuple2_&) {
        return true;
    }
};

// TupleLess

template <size_t I_>
struct TupleLess {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_& t1, const Tuple2_& t2) {
        return TupleLess<I_ - 1>()(t1, t2) ||
            (!TupleLess<I_ - 1>()(t2, t1) && get<I_ - 1>(t1) < get<I_ - 1>(t2));
    }
};

template<>
struct TupleLess<0> {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_&, const Tuple2_&) {
        return false;
    }
};

These are the usual recursive templates parametrized on the number of tuple elements, that define an operator() to evaluate the relation for tuple elements up to the given index. The stop condition for both recursions is when I_ == 0, where TupleEqual return true and TupleLess returns false.

After the optimizer is done with the code, a call like

TupleEqual<2>()(tuple1, tuple2)
ends up as if we had hand-written
get<0>(tuple1) == get<0>(tuple2) && get<1>(tuple1) == get<1>(tuple2).

Tuple

Finally we can leave the detail namespace and put everything together in our final Tuple template:

// tuple_size

template <typename Tuple_>
class tuple_size : public detail::TupleSize<Tuple_> {
};

// tuple_element

template <size_t I_, typename Tuple_>
class tuple_element : public detail::TupleElement<I_, Tuple_> {
};

// Tuple

template <typename... Ts_>
class Tuple  {
    typedef detail::TupleImpl<typename detail::MakeTupleIndexes<sizeof...(Ts_)>::type, Ts_...> Impl;
    Impl impl_;

    template <size_t I, typename... Ts>
    friend
    typename tuple_element<I, Tuple<Ts...>>::type&
    get(Tuple<Ts...>& t);

    template <size_t I, typename... Ts>
    friend
    const typename tuple_element<I, Tuple<Ts...>>::type&
    get(const Tuple<Ts...>& t);

    template <size_t I, typename... Ts>
    friend
    typename tuple_element<I, Tuple<Ts...>>::type&&
    get(Tuple<Ts...>&& t);

public:
    explicit Tuple(const Ts_&... t)
            : impl_(typename detail::MakeTupleIndexes<sizeof...(Ts_)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Ts_)>::type(),
                   typename detail::MakeTupleIndexes<0>::type(),
                   typename detail::MakeTupleTypes<Tuple, 0>::type(),
                   t...) {
    }

    template <typename... Us, typename std::enable_if<
                    sizeof...(Us) <= sizeof...(Ts_) &&
                    detail::TupleConvertible<
                        typename detail::MakeTupleTypes<Tuple<Us...>>::type,
                        typename detail::MakeTupleTypes<Tuple,
                            sizeof...(Us) < sizeof...(Ts_)
                                ? sizeof...(Us)
                                : sizeof...(Ts_)>::type>::value,
                    bool>::type = false>
    explicit Tuple(Us&&... u)
            : impl_(typename detail::MakeTupleIndexes<sizeof...(Us)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Us)>::type(),
                   typename detail::MakeTupleIndexes<sizeof...(Ts_), sizeof...(Us)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Ts_), sizeof...(Us)>::type(),
                   std::forward<Us>(u)...) {
    }
                    
    
    template <typename OtherTuple, typename std::enable_if<
            detail::TupleConvertible<OtherTuple, Tuple>::value,
            bool>::type = false>
    Tuple(OtherTuple&& t)
            : impl_(std::forward<OtherTuple>(t)) {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleAssignable<Tuple, OtherTuple>::value,
            bool>::type = false>
    Tuple& operator=(OtherTuple&& t) {
        impl_.operator=(std::forward<OtherTuple>(t));
        return *this;
    }

    void swap(Tuple& t) {
        impl_.swap(t.impl_);
    }
};

// Empty Tuple

template <>
class Tuple<> {
public:
    Tuple() {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleConvertible<OtherTuple, Tuple>::value,
            bool>::type = false>
    Tuple(OtherTuple&&) {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleAssignable<Tuple, OtherTuple>::value,
            bool>::type = false>
    Tuple& operator=(OtherTuple&&) {
        return *this;
    }

    void swap(Tuple&) {
    }
};

// get

template <size_t I, typename... Ts>
inline
typename tuple_element<I, Tuple<Ts...>>::type&
get(Tuple<Ts...>& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<detail::TupleLeaf<I, Type>&>(t.impl_).get();
}

template <size_t I, typename... Ts>
inline
const typename tuple_element<I, Tuple<Ts...>>::type&
get(const Tuple<Ts...>& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<const detail::TupleLeaf<I, Type>&>(t.impl_).get();
}

template <size_t I, typename... Ts>
inline
typename tuple_element<I, Tuple<Ts...>>::type&&
get(Tuple<Ts...>&& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<Type&&>(static_cast<detail::TupleLeaf<I, Type>&&>(t.impl_).get());
}

// swap 

template <typename... Ts>
inline
void swap(Tuple<Ts...>& a, Tuple<Ts...>& b) {
    a.swap(b);
}

// relational operators

template <typename... T1s_, typename... T2s_>
inline bool operator==(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return detail::TupleEqual<sizeof...(T1s_)>()(t1, t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator!=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t1 == t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator<(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return detail::TupleLess<sizeof...(T1s_)>()(t1, t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator>(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return t2 < t1;
}

template <typename... T1s_, typename... T2s_>
inline bool operator<=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t2 < t1);
}

template <typename... T1s_, typename... T2s_>
inline bool operator>=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t1 < t2);
}
Lines 1-11:
The user-visible tuple_size and tuple_element templates just inherit from the corresponding "hidden" templates. Nothing fancy here.
Lines 13-18:
The generic Tuple template builds a detail::TupleImpl and holds that as its only data member.
Lines 20-33 and 107-131:
The get() functions are made friends so that they can access our private impl_ member. The three versions return reference, const-reference or rvalue-reference types depending on the type of the input parameter. We get the desired element by converting our impl_ member to the correct TupleLeaf type via a simple static_cast.
Lines 36-42:
This is the simplest of our constructors: it takes its parameters as const references, matching both the number and exact type of our tuple members. We pass these along to our TupleImpl's constructor, and since we fill out all parameters in the first set, the second set of parameters is empty (empty indexes and types).
Lines 44-59:
This constructor is responsible for constructing a Tuple from values convertible to our tuple-elements. We allow less parameters than the number of elements we hold, the rest of the elements will be default constructed. As a special case, if the number of supplied parameters is 0, then all of our tuple-elements will be default constructed, so this constructor acts as our default constructor, too. This constructor is enabled only if the supplied types are convertible to the corresponding types of our Tuple. This is checked via the above defined TupleConvertible template after creating suitable TupleTypes from the supplied parameter pack.
Lines 62-67:
Our last constructor takes a single tuple-like argument, and forwards it to the corresponding TupleImpl constructor, thus this constructor is both our copy and move constructor, depending on context. This constructor is enabled only if OtherTuple is convertible to our Tuple. This implicitly checks that OtherTuple is in fact tuple-like. Without this tuple-like check there would be an ambiguity (or other compile error) if we tried to instantiate our Tuple with a single (non-tuple) parameter.
Lines 69-75:
The forwarding move/copy assignment operator is analogous to the copy/move constructor above, the only difference is that instead of checking for TupleConvertible, we check for TupleAssignable to enable this operator.
Lines 77-79, 103-104 and 133-139:
The swap() member function just calls TupleImpl::swap() (the implementation for empty tuples is of course a no-op). We also define a standard swap() override, so that it could be picked up by ADL when needed.
Lines 82-105:
The empty Tuple<> doesn't need to hold any data at all, so we specialize our template for that case to avoid unnecessary memory waste. The constructors are of course simpler than in the general case. We also won't need get functions, and our swap is a no-op.
Lines 141-171:
The two basic relational operators (equals and less-than) are implemented via the corresponding helper templates, the rest are just built using these two, as usual.

Finishing touches: integration with the std namespace

In the last section we make our Tuple drop-in compatible with std::tuple by specializing the std::tuple_size and std::tuple_element templates for it, and providing overloads for std::get by lifting the migl2::get functions into the std namespace:
namespace std {

// tuple_size

template <typename... Ts_>
class tuple_size<migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<const migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<const migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<volatile migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<const volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<const volatile migl2::Tuple<Ts_...>> {
};

// tuple_element

template <size_t I_, typename... Ts_>
class tuple_element<I_, migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, const migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, const migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, volatile migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, const volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, const volatile migl2::Tuple<Ts_...>> {
};

using migl2::get;

} // namespace std

Disclaimer

I'm returning to C++ after 9 years of Java development, so take everything presented here with a grain of salt, and please point out any mistakes in the comments section below, so that I can fix them and not confuse others. As mentioned in the preamble, this code is based on the tuple implementation in libc++, which was created by Howard Hinnant, so hereby I thank him (and all other developers of libc++) for the inspiration.

The complete source for the above Tuple implementation can be found on bitbucket.

2009-04-28

Dump java stack traces

This is a small utility function to programmatically dump all stack traces of a java process similar to the output of kill -QUIT on unix platforms. Use at your own peril, no warranties, no royalties :)
public static void dumpStackTraces(PrintStream out) {
    synchronized (out) {
        Map<Thread, StackTraceElement[]> sts = Thread.getAllStackTraces();
        for (Thread t : sts.keySet()) {
            StackTraceElement[] st = sts.get(t);
            out.println(t.getName() + "[" + t.getId() + "]" + "(" + t.getState() + (t.isDaemon() ? ")(DAEMON):" : "):"));
            for (int i = 0; i < st.length; ++i) {
                out.println("\t" + st[i]);
            }
        }
    }
}

2008-09-25

XML indenting with sed(1)

Some years ago I stumbled upon SedSokoban, the sokoban game implemented as a sed script. I found it pretty amusing, so I got interested in the more arcane uses of sed. As an exercise, I set out to write an XML indenter sed script.

Now I found that script (again), and I thought it would be a nice starting post here.

xmlindent.sed looks like this:

:a
/>/!N;s/\n/ /;ta
s/	/ /g;s/^ *//;s/  */ /g
/^<!--/{
:e
/-->/!N;s/\n//;te
s/-->/\n/;D;
}
/^<[?!][^>]*>/{
H;x;s/\n//;s/>.*$/>/;p;bb
}
/^<\/[^>]*>/{
H;x;s/\n//;s/>.*$/>/;s/^	//;p;bb
}
/^<[^>]*\/>/{
H;x;s/\n//;s/>.*$/>/;p;bb
}
/^<[^>]*[^\/]>/{
H;x;s/\n//;s/>.*$/>/;p;s/^/	/;bb
}
/</!ba
{
H;x;s/\n//;s/ *<.*$//;p;s/[^	].*$//;x;s/^[^<]*//;ba
}
:b
{
s/[^	].*$//;x;s/^<[^>]*>//;ba
}

Unfortunately it chokes on some xml inputs, but I could use it to pretty-format most of the common xml files I came across (configuration files, xml-based network protocol messages, etc).