RoxTerm Code

#  maitch.py - Simple but flexible build system tool
#  Copyright (C) 2012 Tony Houghton <h@realh.co.uk>
#
#  This program is free software; you can redistribute it and/or modify it
#  under the terms of the GNU Lesser General Public License as published by the
#  Free Software Foundation; either version 3 of the License, or (at your
#  option) any later version.
#
#  This program is distributed in the hope that it will be useful, but WITHOUT
#  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
#  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
#  for more details.
#
#  You should have received a copy of the GNU Lesser General Public License
#  along with this program; if not, write to the Free Software Foundation,
#  Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

import atexit
import fnmatch
import os
import re
import shutil
import subprocess
import sys
import threading
import traceback

try:
    basestring = basestring
except NameError:
    basestring = (str, bytes)
    def to_str(s):
        if isinstance(s, bytes):
            return str(s, "utf-8")
        elif isinstance(s, str):
            return s
        else:
            return str(s)
else:
    def to_str(s):
        if isinstance(s, str):
            return s
        else:
            return str(s)

if sys.version_info[0] < 3:
    def open_utf8(*args, **kwargs):
        return open(*args, **kwargs)
else:
    def open_utf8(*args, **kwargs):
        kwargs["encoding"] = "utf8"
        return open(*args, **kwargs)

mswin = sys.platform.startswith("win")

# curses is broken on Windows
if mswin:
    class ascii:
        @staticmethod
        def isdigit(c):
            return c >= '0' and c <= '9'

        @staticmethod
        def isspace(c):
            return c == ' ' or c == '\t' or c == '\n' or c == '\r' or c == '\l'

        @staticmethod
        def isalnum(c):
            return ascii.isdigit(c) or (c >= 'a' and c <= 'z') \
                   or (c >= 'A' and c <= 'Z')

else:
    from curses import ascii


_mprint_lock = threading.Lock()
_mprint_fp = None

def mprint(*args, **kwargs):
    """ Equivalent to python 3's print but also works in python < 2.6 """
    global _mprint_lock
    _mprint_lock.acquire()
    try:
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        file = kwargs.get('file', sys.stdout)
        s = sep.join(args) + end
        file.write(s)
        #file.write("Called from: " + "".join(traceback.format_stack()) + "\n")
        file.flush()
        if _mprint_fp and file != _mprint_fp:
            _mprint_fp.write(s)
    finally:
        _mprint_lock.release()


_debug = False
def dprint(*args, **kwargs):
    if _debug:
        mprint(*args, **kwargs)
    elif _mprint_fp:
        kwargs['file'] = _mprint_fp
        mprint(*args, **kwargs)


try:
    from lockfile import FileLock

    class FLock(FileLock):
        def __init__(self, *args, **kwargs):
            self.maitch_locked = False
            FileLock.__init__(self, *args, **kwargs)

        def acquire(self, timeout = None):
            FileLock.acquire(self, timeout)
            self.maitch_locked = True

        def release(self):
            if self.maitch_locked:
                try:
                    FileLock.release(self)
                except:
                    mprint("Lock was already released")
                self.maitch_locked = False

except:
    _nolock = True
else:
    _nolock = False



# Where to look for sources if a relative path is given and the file
# doesn't exist relative to cwd.
# May be combined with bitwise or.
NOWHERE = 0
SRC = 1
TOP = 2


class MaitchError(Exception):
    pass

class MaitchRuleError(MaitchError):
    pass

class MaitchArgError(MaitchError):
    pass

class MaitchChildError(MaitchError):
    pass

class MaitchDirError(MaitchError):
    pass

class MaitchNotFoundError(MaitchError):
    pass

class MaitchRecursionError(MaitchError):
    pass

class MaitchJobError(MaitchError):
    pass

class MaitchInstallError(MaitchError):
    pass

class MaitchPkgError(MaitchError):
    pass



# subst behaviour if a variable isn't found
NOVAR_FATAL = 0     # Raise exception
NOVAR_BLANK = 1     # Replace with empty string
NOVAR_SKIP = 2      # Leave ${} construct untouched



class Context(object):
    " The fundamental build context. "

    # Commonly used variables
    def add_vars(self):
        self.var_repository = []
        self.prog_var_repository = {}

        self.add_var('PARALLEL', '0',
            "Number of build operations to run at once", True)
        self.add_var('PREFIX', '/usr/local',
            "Base directory for installation", True)
        self.add_var('BINDIR', '${PREFIX}/bin',
            "Installation directory for binaries", True)
        self.add_var('LIBDIR', '${PREFIX}/lib',
            "Installation directory for shared libraries "
            "(you should use multiarch where possible)", True)
        self.add_var('SYSCONFDIR', '/etc',
            "Installation directory for system config files", True)
        self.add_var('MANDIR', '${DATADIR}/man',
            "Installation directory for man pages", True)
        self.add_var('DATADIR', '${PREFIX}/share',
            "Installation directory for data files", True)
        self.add_var('LOCALEDIR', '${DATADIR}/locale',
            "Installation directory for locale data", True)
        self.add_var('PKGDATADIR', '${PREFIX}/share/${PACKAGE}',
            "Installation directory for this package's data files", True)
        self.add_var('DOCDIR', '${PREFIX}/share/doc/${PACKAGE}',
            "Installation directory for this package's documentation", True)
        self.add_var('HTMLDIR', '${DOCDIR}',
            "Installation directory for this package's HTML documentation",
            True)
        self.add_var('DESTDIR', '',
            "Prepended to prefix at installation (for packaging)", True)
        if mswin:
            self.add_var('MINGW_PATH', "C:\MinGW", "Where MinGW is installed")
        self.add_var('LOCK_TOP', False,
            "Lock ${TOP_DIR} instead of ${BUILD_DIR}")
        self.add_var('NO_LOCK', False, "Disable locking (not recommended)")
        self.add_var('ENABLE_DEBUG', False,
            "Enable the printing of maitch debug messages")
        self.add_var('CC', '${GCC}', "C compiler")
        self.add_var('CXX', self.find_cxx, "C++ compiler")
        self.add_var('GCC', self.find_prog_by_var, "GNU C compiler")
        self.add_var('CPP', self.find_prog_by_var, "C preprocessor")
        self.add_var('LIBTOOL', self.find_prog_by_var,
            "libtool compiler frontend for libraries")
        self.add_var('CDEP', '${CPP} -M',
                "C preprocessor with option to print deps")
        self.add_var('CFLAGS', '', "C compiler flags")
        self.add_var('CPPFLAGS', '', "C preprocessor flags")
        self.add_var('LIBS', '', "libraries and linker options")
        self.add_var('LDFLAGS', '', "Extra linker options")
        self.add_var('CXXFLAGS', '${CFLAGS}', "C++ compiler flags")
        self.add_var('LIBTOOL_MODE_ARG', '', "Default libtool mode argument(s)")
        self.add_var('LIBTOOL_FLAGS', '', "Additional libtool flags")
        self.add_var('PKG_CONFIG', self.find_prog_by_var, "pkg-config")
        self.add_var('INSTALL', self.find_prog_by_var, "install program")
        self.add_var('SIGN_DIST', False,
                "If True, dist archives will be signed (requires ${GPG}")


    def __init__(self, **kwargs):
        """
        All kwargs are added to context's env. They may include:

        PACKAGE = package name (compulsory).
        BUILD_DIR = where to output all generated files, defaults to
                "${MSCRIPT_REAL_DIR}/build". ${BUILD_DIR} is used as the cwd for
                all commands and other directories should be specified relative
                to it.
        TOP_DIR = top level of package directory, defaults to ".."
        SRC_DIR = top level of source directory, defaults to ${TOP_DIR}.
                Otherwise it should be specified relative to TOP_DIR to make
                sure dist stage works correctly.

        Special env variables. These are expanded in all modes, not just
        configure. They are not saved in the env file.

        MSCRIPT_DIR: The directory containing the executable script running
                the build (sys.argv[0]). Symlinks are not followed.
        MSCRIPT_REAL_DIR: MSCRIPT_DIR with symlinks followed.


        Useful attributes:

        env: context's variables
        mode: mode of build, one of "configure", "build", "install", "dist"
                or "zip"; taken from sys.argv[1]
        build_dir, src_dir, top_dir: Expanded versions of above variables. Bear
                in mind that these are expanded before you have a chance to add
                any vars to env after constructing the ctx:- they may refer to
                each other (non-recursively) but to no other variables.

        Notes:

        All "nodes" (sources, targets etc) are expressed as strings.
        See process_nodes() for how they are accepted as arguments.
        """
        self.lock = threading.RLock()
        self.tmpfile_index = 0

        # Make sure a package name was specified
        self.package_name = kwargs['PACKAGE']

        self.created_by_config = {}
        self.installed = []
        self.tar_contents = []

        self.add_vars()

        # Check mode
        if len(sys.argv) < 2:
            self.mode = 'help'
        else:
            self.mode = sys.argv[1]
            if not self.mode in \
                    "help configure reconfigure build dist install uninstall " \
                    "clean pristine zip".split():
                self.mode = 'help'
        if self.mode == 'help':
            ms = os.path.basename(sys.argv[0])
            mprint("Help for maitch:\nUSAGE:")
            for m in ["help", "configure", "reconfigure",
                    "build [TARGETS]", "install", "uninstall",
                    "clean", "pristine", "dist", "zip"]:
                mprint("  python %s %s" % (ms, m))
            mprint("""
Further variables may be set after the mode argument in the form VAR=value, or
VAR on its own for True. "--foo-bar" is equivalent to "FOO_BAR". Variables may
refer to each other eg FOO='${BAR}.baz'. Note that maitch does not read
variables directly from the environment. If you want to use, for example,
CFLAGS from the environment, add CFLAGS="$CFLAGS" to the configure command.

Variables can be set from the environment indirectly using MAITCHFLAGS. For
example:

export MAITCHFLAGS="CFLAGS=$CFLAGS;LDFLAGS=$LDFLAGS"

Note that multiple variables are separated by semicolons and you should not use
quoting within the MAITCHFLAGS string.

The most pivotal variable is BUILD_DIR which is the working directory and where
built files are saved. It will be created if necessary. If not specified it
defaults to a directory "build" in the same directory as %s
(symbolic links are followed).

TOP_DIR and SRC_DIR are the top level directory of the package, and the
subdirectory containing source files respectively. SRC_DIR is commonly
"${TOP_DIR}/src" or just "${TOP_DIR}". It is recommended that they are specified
as relative paths assuming a working directory of $BUILD_DIR. For example, when
the default BUILD_DIR is used, TOP_DIR='..'

Other predefined variables [default values shown in squarer brackets]:
""" % ms)
            for v in self.var_repository:
                if v[3]:
                    alt = "/%s" % var_to_arg(v[0])
                else:
                    alt = ""
                if callable(v[1]):
                    default = 'dynamic'
                else:
                    default = v[1]
                print_wrapped("  %s%s [%s]: %s" %
                        (v[0], alt, default, v[2]),
                        80, 8, 0)
            self.showed_var_header = False
            return

        elif self.mode == 'zip':
            self.mode = 'dist'
            self.dist_as_zip = True
        else:
            self.dist_as_zip = False

        self.env = {}

        # Process MAITCHFLAGS first because it's lowest priority and
        # subsequent processing will overwrite it
        mf = os.environ.get('MAITCHFLAGS')
        if mf:
            self.__process_args(mf.split(';'))

        # Get more env vars from kwargs
        for k, v in kwargs.items():
            self.env[k] = v

        self.explicit_rules = {}

        self.cli_targets = []

        # Process command-line args
        if len(sys.argv) > 2:
            cli_env = self.__process_args(sys.argv[2:])
        else:
            cli_env = {}

        # Everything hinges on BUILD_DIR
        self.get_build_dir()
        self.build_dir = opap(self.subst(self.env['BUILD_DIR']))
        self.ensure_out_dir(self.build_dir)
        log_file = opj(self.build_dir, ".maitch", "log")
        self.ensure_out_dir_for_file(log_file)
        global _mprint_fp
        _mprint_fp = open(log_file, 'w')
        if self.mode != "dist":
            # This message is to help text editors find the cwd in case errors
            # are reported relative to it
            mprint('make[0]: Entering directory "%s"' % \
                    self.build_dir)
        os.chdir(self.build_dir)

        # Get lock on BUILD_DIR
        if not self.env.get('NO_LOCK'):
            global _nolock
            if _nolock:
                mprint("Error: lockfile module unavailable. "
                        "Please install it or, as a last resort, "
                        "use the --no-lock option:\n"
                        "%s %s --no-lock ..." % (sys.argv[0], sys.argv[1]),
                        file = sys.stderr)
                sys.exit(1)
            f = self.get_lock_file_name()
            self.ensure_out_dir_for_file(f)
            self.lock_file = FLock(f)
            self.lock_file.acquire(0)
            atexit.register(lambda x: x.release(), self.lock_file)
        else:
            mprint("Warning: Locking disabled. This is not recommended.")

        # If not in configure mode load a previous saved env.
        if self.mode != 'configure':
            n = self.env_file_name()
            if os.path.exists(n):
                fp = open(n, 'r')
                for l in fp.readlines():
                    k, v = l.split('=', 1)
                    # Don't override command line or constructor
                    if not k in cli_env:
                        v = v.rstrip()
                        if v == 'True':
                            v = True
                        elif v == 'False':
                            v = False
                        elif len(v) \
                                and (ascii.isdigit(v[0]) \
                                    or (v[0] == '-' and len(v) > 1)) \
                                and all([ascii.isdigit(a) for a in v[1:]]):
                            v = int(v)
                        self.env[k] = v
                fp.close()

        # From now on reconfigure is the same as configure
        if self.mode == 'reconfigure':
            self.mode = 'configure'

        # Set defaults
        for v in self.var_repository:
            if not self.env.get(v[0]):
                if callable(v[1]):
                    d = v[1](v[0])
                else:
                    d = v[1]
                self.env[v[0]] = d

        # In dist mode everything is relative to TOP_DIR
        bd = self.subst("${BUILD_DIR}")
        td = self.subst("${TOP_DIR}")
        if self.mode == "dist":
            self.env['TOP_DIR'] = os.curdir
            self.env['BUILD_DIR'] = bd
            mprint('make[0]: Entering directory "%s"' % td)
            os.chdir(td)
        else:
            os.chdir(bd)

        self.top_dir = self.subst("${TOP_DIR}")
        self.abs_top_dir = opap(self.top_dir)
        self.env['ABS_TOP_DIR'] = self.abs_top_dir
        self.src_dir = self.subst("${SRC_DIR}")
        self.abs_src_dir = opap(self.src_dir)
        self.env['ABS_SRC_DIR'] = self.abs_src_dir
        self.check_build_dir()
        self.build_dir = self.subst("${BUILD_DIR}")
        self.abs_build_dir = opap(self.build_dir)
        self.env['ABS_BUILD_DIR'] = self.abs_build_dir
        self.dest_dir = self.subst(self.env['DESTDIR'])


        self.definitions = {}

        self.created_by_config[".maitch"] = True

        if self.env.get('ENABLE_DEBUG'):
            global _debug
            _debug = True


    def __process_args(self, args):
        cli_env = {}
        for a in args:
            if '=' in a:
                k, v = a.split('=', 1)
            elif self.mode != 'build' or a.startswith('--'):
                k = a
                v = True
            elif self.mode == 'build':
                self.cli_targets.append(a)
            if k.startswith('--'):
                k = arg_to_var(k)
            if self.var_is_special(k):
                raise MaitchDirError("%s is a reserved variable" % k)
            self.env[k] = v
            cli_env[k] = v
        return cli_env


    def define(self, key, value):
        """ Define a variable to be used in the build. At the moment the only
        supported method is to output a C header ${BUILD_DIR}/config.h at the
        end of the configure phase. Definitions are of the form:
        #define key value
        where double quotes are automatically added for string values unless
        already enclosed in single quotes. True and False are converted to 1 and
        0, while a value of None results in:
        #undef key
        being written instead. """
        self.definitions[key] = value


    def define_from_var(self, key, default = None):
        """ Calls self.define() with env variable's value. """
        self.define(key, self.env.get(key, default))


    def __arg(self, help_name, help_body, var, antivar, default):
        if self.mode == 'help':
            if not self.showed_var_header:
                mprint("\n%s supports these configure options:\n" %
                        self.package_name)
                self.showed_var_header = True
            print_formatted(help_body, 80, help_name, 20)
        else:
            if self.env.get(antivar):
                self.setenv(var, False)
            elif self.env.get(var) == None:
                if callable(default):
                    default = default(self, var)
                self.setenv(var, default)


    def arg_enable(self, name, help, var = None, default = False):
        """ Similar to autoconf's AC_ARG_ENABLE. Adds a variable which may
        be enabled/disabled on the configure command line with --enable-name
        or --disable-name. default may be a callable, in which case it will be
        called as default(context, var) if the argument isn't given on the
        command line, and var will be set to its return value. If var is not
        given, it's generated in the form ENABLE_NAME. Its value in the env will
        be 1 or 0. """
        if default == True:
            prefix = "disable"
        else:
            prefix = "enable"
        arg = "--%s-%s" % (prefix, name)
        if not var:
            var = 'ENABLE_' + s_to_var(name)
        self.__arg(arg, help, var, 'DISABLE' + var[6:], default)


    def arg_disable(self, name, help, var = None, default = True):
        """ Can be used as a shortcut for arg_enable with default = True or
        to force help string to be shown as --disable-name when default is
        callable. """
        if not var:
            var = 'ENABLE_' + s_to_var(name)
        self.__arg("--disable-%s" % name, help, var,
                'DISABLE' + var[6:], default)


    def arg_with(self, name, help, var = None, default = False):
        """ Like arg_enable but uses --with-name=... and --without-name=... """
        if not var:
            var = 'WITH_' + s_to_var(name)
        self.__arg("--with-%s=VALUE" % name, help, var,
                'WITHOUT' + var[4:], default)


    def save_if_different(self, filename, content):
        " Like global version but runs self.subst() on filename and content. "
        save_if_different(self.subst(filename), self.subst(content))


    def output_config_h(self):
        sentinel = "%s__CONFIG_H" % self.package_name.upper()
        keys = list(self.definitions.keys())
        keys.sort()
        s = "/* Auto-generated by maitch.py for %s */\n" \
                "#ifndef %s\n#define %s\n\n" % \
                (self.package_name, sentinel, sentinel)
        for k in keys:
            v = self.definitions[k]
            if v == None:
                s += "#undef %s\n\n" % k
                continue
            elif v == True:
                v = 1
            elif v == False:
                v = 0
            else:
                if isinstance(v, basestring):
                    if (v[0] != "'" or v[-1] != "'"):
                        v = '"' + v + '"'
                    v = self.subst(v)
            s += "#define %s %s\n\n" % (k, v)
        s += "#endif /* %s */\n" % sentinel
        filename = opj(self.build_dir, "config.h")
        self.save_if_different(filename, s)
        self.created_by_config["config.h"] = True


    @staticmethod
    def var_is_special(k):
        return k == "MSCRIPT_DIR" or k == "MSCRIPT_REAL_DIR"


    def check_build_dir(self):
        clash = None
        if self.top_dir == self.build_dir or self.top_dir == ".":
            clash = 'TOP_DIR'
        elif self.src_dir == self.build_dir or self.src_dir == ".":
            clash = 'SRC_DIR'
        if clash:
            mprint("WARNING: BUILD_DIR == %s, unable to clean" % clash,
                    file = sys.stderr)
            return False
        return True


    def tmpname(self):
        """ Returns the name of a temporary file in ${BUILD_DIR}/.maitch
        which is unique for this context. """
        self.lock.acquire()
        try:
            self.tmpfile_index += 1
            i = self.tmpfile_index
            result = opj(self.build_dir, ".maitch", "tmp%03d" % i)
        finally:
            self.lock.release()
        return result


    def get_build_dir(self, kwargs = None):
        """ Sets env's TOP_DIR and SRC_DIR, looking in kwargs or self.env,
        setting defaults if necessary. """
        if not kwargs:
            kwargs = self.env
        self.env['MSCRIPT_DIR'] = opap(os.path.dirname(sys.argv[0]))
        self.env['MSCRIPT_REAL_DIR'] = \
                opap(os.path.dirname(os.path.realpath(sys.argv[0])))
        bd = kwargs.get('BUILD_DIR')
        if bd:
            bd = opap(bd)
        else:
            bd = opj("${MSCRIPT_REAL_DIR}", "build")
        self.env['BUILD_DIR'] = bd
        td = kwargs.get('TOP_DIR')
        if not td:
            td = os.pardir
        self.env['TOP_DIR'] = td
        sd = kwargs.get('SRC_DIR')
        if not sd:
            sd = "${TOP_DIR}"
        self.env['SRC_DIR'] = sd


    def env_file_name(self):
        """ Returns the filename of where env is saved, ensuring its
        directory exists. """
        n = self.make_out_path(".maitch", "env")
        self.ensure_out_dir_for_file(n)
        return n


    def get_lock_file_name(self):
        if self.env.get("LOCK_TOP"):
            return opap(opj(self.subst("${TOP_DIR}"), ".maitchlock"))
        else:
            return opap(opj(self.subst("${BUILD_DIR}"),
                    ".maitch", "lock"))


    def release_lock(self, lock, lockname):
        try:
            lock.release()
        except:
            pass
        try:
            if os.path.isdir(lockname):
                os.unlink(lockname)
            else:
                recursively_remove(lockname, False, [])
        except:
            pass


    def add_rule(self, rule):
        " Adds an explicit rule. "
        for t in rule.targets:
            self.explicit_rules[self.subst(t)] = rule
        rule.ctx = self


    def glob(self, pattern, dir = None, subdir = None, expand = None):
        """ Returns a list of matching filenames relative to dir (default
        ${BUILD_DIR}). subdir, if given, is preserved at the start of each
        filename. expand is whether to use the substituted/expanded version
        of dir in the output. If not given/None it's True in all modes except
        dist and zip. """
        if expand == None:
            expand = self.mode != "dist"
        if dir:
            orig_dir = dir
            dir = self.subst(dir)
        else:
            orig_dir = os.curdir
            dir = opap(orig_dir)
        if subdir:
            dir = opj(dir, subdir)
        matches = fnmatch.filter(os.listdir(dir), pattern)
        if expand or subdir:
            if not expand:
                dir = subdir
            for i in range(len(matches)):
                matches[i] = opj(dir, matches[i])
        return matches


    def glob_src(self, pattern, subdir = None, expand = None):
        " Performs glob on src_dir. "
        return self.glob(pattern, self.src_dir, subdir, expand)


    def glob_all(self, pattern, subdir = None, expand = None):
        """ Performs glob on both build_dir/src_dir. No pathname component
        is added other than subdir. """
        matches = self.glob(pattern, self.build_dir, subdir, expand)
        for n in self.glob_src(pattern, subdir, expand):
            if not n in matches:
                matches.append(n)
        return matches


    def run(self):
        " Run whichever stage of the build was specified on CLI. "
        if self.mode == 'configure':
            fp = open(self.env_file_name(), 'w')
            for k, v in self.env.items():
                if not self.var_is_special(k):
                    fp.write("%s=%s\n" % (k, v))
            fp.close()
            if self.definitions:
                self.output_config_h()
            fp = open(opj(self.build_dir, ".maitch", "manifest"), 'w')
            for f in self.created_by_config.keys():
                fp.write("%s\n" % f)
            fp.close()
        elif self.mode == 'build':
            if len(self.cli_targets):
                tgts = self.cli_targets
            else:
                tgts = self.explicit_rules.keys()
            bg = BuildGroup(self, tgts)
            if bg.cancelled:
                sys.exit(1)
        elif self.mode == 'clean':
            filename = opj(self.build_dir, ".maitch", "manifest")
            if os.path.exists(filename):
                fp = open(filename, 'r')
                for f in fp.readlines():
                    self.created_by_config[f.strip()] = True
                fp.close()
            self.clean(False)
        elif self.mode == 'pristine':
            self.clean(False, True)
        elif self.mode == 'dist':
            self.make_tarball()
        elif self.mode == 'uninstall':
            self.uninstall()


    def make_tarball(self):
        if self.dist_as_zip:
            import zipfile
            suffix = "zip"
            zname = "zip archive"
        else:
            import tarfile
            suffix = "tar.xz"
            zname = "tarball"
        basedir = self.subst("${PACKAGE}-${VERSION}")

        def get_filename(d, s):
            return opap(self.subst("${BUILD_DIR}/%s.%s" % (d, s)))

        filename = get_filename(basedir, suffix)
        if self.dist_as_zip:
            tar = zipfile.ZipFile(filename, 'w', zipfile.ZIP_DEFLATED)
        else:
            try:
                tar = tarfile.open(filename, 'w:xz')
            except:
                filename = get_filename(basedir, "tar.bz2")
                tar = tarfile.open(filename, 'w:bz2')
        mprint("Creating %s '%s'" % (zname, filename))

        for f, kwargs in self.tar_contents:
            f = self.subst(f)
            kwargs = dict(kwargs)
            dest = kwargs.get('arcname')
            if dest:
                dest = os.path.normpath(opj(basedir, dest))
            else:
                dest = os.path.normpath(opj(basedir, f))
            kwargs['arcname'] = dest
            mprint("Adding '%s' to %s" % (dest, zname))
            if self.dist_as_zip:
                tar.write(f, **kwargs)
            else:
                tar.add(f, **kwargs)
        tar.close()
        if self.env.get("SIGN_DIST"):
            gpg = self.env.get("GPG")
            try:
                if gpg:
                        mprint("Signing " + filename)
                        result = call_subprocess([gpg, "--detach-sign",
                                "--armor", "-o", filename + ".sign", filename])
                        if result:
                            raise Exception()
                else:
                    raise Exception()
            except:
                mprint("Unable to sign " + filename, file = sys.stderr)


    def add_dist(self, objects, **kwargs):
        if isinstance(objects, basestring):
            objects = objects.split()
        for o in objects:
            self.tar_contents.append([o, kwargs])


    def clean(self, fatal, pristine = False):
        if pristine:
            # Release lock prematurely because we're about to delete it!
            self.lock_file.release()
            keep = []
        else:
            keep = {}
            for k in self.created_by_config.keys():
                k = self.subst(k)
                if not os.path.isabs(k):
                    k = opj(self.subst("${BUILD_DIR}"), k)
                keep[k] = True
        if not self.check_build_dir():
            return
        recursively_remove(self.build_dir, fatal, keep)
        recursively_remove(opj(self.build_dir, ".maitch", "deps"), fatal, [])
        recursively_remove(opj(self.top_dir, "__pycache__"), False, [])


    def ensure_out_dir(self, *args):
        """ Ensures the named directory exists. args is a single string or list
        of strings. Single string may be absolute in which case it isn't
        altered. Otherwise a path is made absolute using BUILD_DIR. """
        if isinstance(args, basestring) and os.path.isabs(args):
            path = args
        else:
            path = self.make_out_path(*args)
        self.lock.acquire()
        try:
            if not os.path.isdir(path):
                os.makedirs(path)
        finally:
            self.lock.release()


    def ensure_out_dir_for_file(self, path):
        """ As above but uses a single string only and acts on its
        parent directory. """
        self.ensure_out_dir(os.path.dirname(path))


    def make_out_path(self, *args):
        """ Creates an absolute filename from BUILD_DIR and args (single
        string or list). """
        if isinstance(args, basestring):
            args = (args)
        args = (self.build_dir,) + args
        return self.subst(opj(*args))


    def find_prog(self, prog, expand = False):
        " Finds a binary in context's PATH. prog not expanded by default. "
        mprint("Searching for program %s... " % prog, end = '')
        if expand:
            prog = self.subst(prog)
        try:
            p = self.__find_prog(prog, self.env)
            mprint("%s" % p)
        except MaitchNotFoundError:
            mprint("not found")
            raise
        return p


    def find_prog_env(self, prog, var = None, expand = False):
        """ Finds a program and sets an env var to its full path. If the var
        is not specified a capitalised (etc) transform of the program name
        is used. """
        if not var:
            var = s_to_var(prog)
        self.env[var] = self.find_prog(prog, expand)


    def prog_output(self, prog, use_shell = False):
        """ Runs a program and returns its [stdout, stderr]. prog should be a
        list or single string (former will not be split at spaces). Each
        component will be expanded. cwd is set to BUILD_DIR. """
        if isinstance(prog, basestring):
            prog = prog.split()
        for i in range(len(prog)):
            prog[i] = self.subst(prog[i])
        if not os.path.isabs(prog[0]):
            prog[0] = self.find_prog(prog[0], False)
        proc = subprocess.Popen(prog,
                stdout = subprocess.PIPE, stderr = subprocess.PIPE,
                shell = use_shell, cwd = self.build_dir)
        result = proc.communicate()
        if proc.returncode:
            raise MaitchChildError("%s failed:\n%d:\n%s" % \
                    (' '.join(prog), proc.returncode, result[1].strip()))
        return (to_str(result[0]), to_str(result[1]))


    def prog_to_var(self, prog, var, use_shell = False):
        " As prog_output(), storing stripped result into self.env[var]. "
        output = self.prog_output(prog, use_shell)[0].strip()
        dprint("prog_to_var: input: %s" % ' '.join(prog))
        dprint("prog_to_var: output: %s" % output)
        self.env[var] = output


    def pkg_config(self, pkgs, prefix = None, version = None,
            pkg_config = "${PKG_CONFIG}"):
        """ Runs pkg-config (or optionally a similar tool) and sets
        ${prefix}_CFLAGS to the output of --flags and ${prefix}_LIBS
        to the output of --libs. If prefix is None, derive it from pkg
        eg "gobject-2.0 sqlite3" becomes GOBJECT_2_0_SQLITE3.
        If version is given, also check that package's version is at least
        as new (only works on one package at a time). """
        mprint("Checking pkg-config %s..." % pkgs, end = '')
        pvs = ""
        try:
            if version:
                pvs = self.prog_output(
                        [pkg_config, '--modversion', pkgs])[0].strip()
                pkg_v = pvs.split('.')
                v = version.split('.')
                new_enough = True
                for n in range(len(v)):
                    if int(v[n]) > int(pkg_v[n]):
                        new_enough = False
                        break
                    elif int(v[n]) < int(pkg_v[n]):
                        new_enough = True
                        break
                if not new_enough:
                    mprint("too old")
                    raise MaitchPkgError("%s has version %s, "
                            "%s needs at least %s" %
                            (pkgs, pvs, self.package_name, version))
            if not prefix:
                prefix = make_var_name(pkgs, True)
            pkgs = pkgs.split()
            self.prog_to_var([pkg_config, '--cflags'] + pkgs,
                    prefix + '_CFLAGS')
            self.prog_to_var([pkg_config, '--libs'] + pkgs,
                    prefix + '_LIBS')
        except:
            mprint("error")
            raise
        else:
            if version:
                mprint("ok (%s)" % pvs)
            else:
                mprint("ok")


    def subst(self, s, novar = NOVAR_FATAL, recurse = True, at = False):
        " Runs global subst() using self.env. "
        return subst(self.env, s, novar, recurse, at)


    def deps_from_cpp(self, sources, cppflags = None):
        """ Runs "${CDEP} sources" and returns its dependencies
        (one file per line). filename should be absolute. If cppflags is
        None, self.env['CPPFLAGS'] is used. """
        if not cppflags:
            cppflags = self.env.get('CPPFLAGS', "")
        sources = process_nodes(sources)
        sources = [self.find_source(s) for s in sources]
        if not sources:
            sources = []
        prog = (self.subst("${CDEP} %s" % cppflags)).split() + sources
        deps = self.prog_output(prog)[0].replace(' \\', '')
        deps = deps.split(':', 1)[1].split()
        return deps


    def find_sys_header(self, header, cflags = None):
        """ Uses deps_from_cpp() to find the full path of a header in the
        include path. Returns None if not found. """
        mprint("Looking for header '%s'... " % header, end = '')
        tmp = self.tmpname() + ".c"
        fp = open(tmp, 'w')
        fp.write("#include <%s>\n" % header)
        fp.close()
        deps = self.deps_from_cpp(tmp, cflags)
        os.unlink(tmp)
        for d in deps:
            if d.endswith(os.sep + header):
                mprint("%s" % d)
                return d
        mprint("not found")
        return None


    def check_compile(self, code, msg = None, cflags = None, libs = None):
        """ Checks whether the program code can be compiled as C, returns
        True or False. If msg is given prints "Checking msg... ". """
        if msg:
            mprint("Checking %s... " % msg, end = '')
        if not cflags:
            cflags = self.env.get('CFLAGS', "")
        if not libs:
            libs = self.env.get('LIBS', "")
        tmp = self.tmpname()
        fp = open(tmp + ".c", 'w')
        fp.write(code)
        fp.close()
        prog = self.subst("${CC} -o %s %s %s %s" %
                (tmp, tmp + ".c", libs, cflags)).split()
        try:
            self.prog_output(prog)
        except MaitchChildError as e:
            if msg:
                mprint("no")
            dprint("check_compile failed:\n%s" % to_str(e))
            dprint("code was:\n%s" % code)
            result = False
        else:
            if msg:
                mprint("yes")
            try:
                os.unlink(tmp)
            except OSError:
                pass
            result = True
        os.unlink(tmp + ".c")
        return result


    def check_header(self, header, cflags = None, libs = None):
        """ Uses check_compile to test whether header is available, calling
        self.define('HAVE_HEADER_H', v) where v is 1 or None and HEADER_H is
        derived from header by make_var_name(). Also sets env var with the
        same name to True or False. """
        if self.check_compile("""#include "%s"
int main() { return 0; }
""" % header,
                "for header '%s'" % header, cflags, libs):
            present = 1
        else:
            present = None
        nm = make_var_name('HAVE_' + header, True)
        self.define(nm, present)
        self.setenv(nm, present == 1)
        return present == 1


    def check_func(self, func, cflags = None, libs = None, includes = None):
        """ Like check_header but for a function. includes is an optional
        list of header names. """
        code = ""
        if includes:
            for i in includes:
                code += '#include "%s"\n' % i
        code += """
int main() { %s(); return 0; }
""" % func
        if self.check_compile(code, "for function %s()" % func, cflags, libs):
            present = 1
        else:
            present = None
        nm = make_var_name('HAVE_' + func, True)
        self.define(nm, present)
        self.setenv(nm, present == 1)
        return present == 1


    def find_source(self, name, cwd = None, where = SRC, fatal = True):
        """ Finds a source file relative to BUILD_DIR (higher priority) or
        SRC_DIR or cwd, returning full path or raising exception if not found.
        Returns absolute paths unchanged. If fatal is False, unfound files are
        returned unchanged"""
        looked_for = []
        name = self.subst(name)
        if os.path.isabs(name):
            if os.path.exists(name):
                return name
            else:
                self.not_found(name, [name])
        elif cwd and os.path.exists(opj(cwd, name)):
            return name
        if where & SRC:
            p = opj(self.abs_src_dir, name)
            looked_for.append('SRC: ' + p)
            if os.path.exists(p):
                return p
        if where & TOP:
            p = opj(self.abs_top_dir, name)
            looked_for.append('TOP: ' + p)
            if os.path.exists(p):
                return p
        if cwd:
            p = opj(self.subst(cwd), name)
            looked_for.append('CWD:' + p)
            if os.path.exists(p):
                return p
        else:
            # If no cwd (Rule.dir) we should be in BUILD_DIR
            p = opj(self.abs_build_dir, name)
            looked_for.append(['BUILD: ' + p])
            if os.path.exists(p):
                return p
        if fatal:
            self.not_found(name, looked_for)
        else:
            dprint("find_source failed:", looked_for)
            return name


    @staticmethod
    def not_found(name, looked_for = None):
        if looked_for:
            s = " - looked for " + to_str(looked_for)
        else:
            s = ""
        raise MaitchNotFoundError(("Resource '%s' cannot be found" % name) + s)


    def setenv(self, k, v):
        " Sets an env var. "
        self.env[k] = v


    def getenv(self, k, default = None):
        " Returns an env var. "
        return self.env.get(k)


    def get_stamp(self, name, cwd = None, where = NOWHERE):
        """ Returns the mtime for named file. Uses find_source() and subst and
        therefore may raise MaitchNotFoundError or KeyError. """
        n = self.find_source(self.subst(name), cwd, where)
        return os.stat(name).st_mtime


    def get_extreme_stamp(self, nodes, comparator, cwd = None, where = NOWHERE,
            verbose = False):
        """ Like global version, but runs subst() and find_source() on each
        item. Items that don't exist are skipped because some suffix rules
        don't necessarily use all sources or targets (eg gob2 doesn't always
        output a private header) and because this is also used on files which
        may not have been built yet. If verbose isn't False it must be a string
        prefix """
        pnodes = []
        for n in nodes:
            try:
                pnodes.append(self.find_source(self.subst(n), cwd, where))
            except MaitchNotFoundError:
                pass
        if not cwd:
            cwd = self.abs_build_dir
        for n in range(len(pnodes)):
            f = pnodes[n]
            if not os.path.isabs(f):
                pnodes[n] = opj(cwd, f)
        return get_extreme_stamp(pnodes, comparator, verbose)


    def get_oldest(self, nodes, cwd = None, where = NOWHERE, verbose = False):
        """ Like global version, but runs subst() and find_source() on each
        item, so may raise MaitchNotFoundError or KeyError. """
        if verbose:
            verbose += "Oldest"
        return self.get_extreme_stamp(nodes, lambda a, b: a < b,
                cwd, where, verbose)


    def get_newest(self, nodes, cwd = None, where = NOWHERE, verbose = False):
        """ Like global version, but runs subst() and find_source() on each
        item, so may raise MaitchNotFoundError or KeyError. """
        if verbose:
            verbose += "Newest"
        return self.get_extreme_stamp(nodes, lambda a, b: a > b,
                cwd, where, verbose)


    def subst_file(self, source, target, at = False):
        """ As global version, using self.env. """
        subst_file(self.env, source, target, at)
        self.created_by_config[target] = True


    def install(self, directory, sources = None,
            mode = None, libtool = False, other_options = None):
        """ Uses the install program to install files. Default mode is install's
        default mode, which in turn defaults to rwxr-xr-x. sources may be string
        with multiple files separated by spaces, or a list, or None to create
        directory. other_options, which may also be a string or a list, are
        additional options for install.
        Automatically creates target directories.
        If other_options contains -T, directory is the target filename.
        In uninstall mode each installed file/directory is instead added to a
        list which will be deleted in reverse order when run() is called. """
        directory = process_nodes(directory)
        if self.dest_dir:
            directory = [self.dest_dir + os.sep + d for d in directory]
        directory = [opap(self.subst(d)) for d in directory]
        if not sources:
            sources = []
        else:
            sources = [self.subst(s) for s in process_nodes(sources)]
        if len(directory) > 1 and sources:
            raise MaitchInstallError("Can't install files to multiple " \
                    "directories")
        if len(sources) > 1 and other_options and "-T" in other_options:
            raise MaitchInstallError("Can only install one file where " \
                    "target is a filename instead of a directory")
        if self.mode == 'uninstall':
            if other_options and "-T" in other_options:
                f = [directory[0]]
            elif sources:
                f = [opj(directory[0], os.path.basename(f)) \
                        for f in sources]
            else:
                f = directory
            self.installed.append([f, libtool])
            return
        sources = [self.find_source(s, None, TOP | SRC, False) for s in sources]
        if libtool:
            cmd = ["${LIBTOOL}", "--mode=install", "${INSTALL}"]
        else:
            cmd = ["${INSTALL}"]
        if isinstance(other_options, basestring):
            cmd += other_options.split()
        elif other_options:
            cmd += list(other_options)
        if mode:
            cmd += ["-m", to_str(mode)]
        if not sources:
            cmd.append("-d")
        cmd += sources + directory
        if sources:
            if other_options and "-T" in other_options:
                dir = os.path.dirname(directory[0])
            else:
                dir = directory[0]
            if not os.path.isdir(dir):
                dd = self.dest_dir
                self.dest_dir = None
                try:
                    self.install(dir)
                except:
                    raise
                finally:
                    self.dest_dir = dd
        cmd = [self.subst(c) for c in cmd]
        mprint("%s" % ' '.join(cmd))
        if subprocess.call(cmd, cwd = self.build_dir) != 0:
            raise MaitchChildError("install failed")


    def install_bin(self, sources, directory = "${BINDIR}", mode = None,
            libtool = True, other_options = None):
        self.install(directory, sources, mode, libtool, other_options)


    def install_lib(self, sources, directory = "${LIBDIR}", mode = '0644',
            libtool = True, other_options = None):
        self.install(directory, sources, mode, libtool, other_options)


    def install_data(self, sources, directory = "${PKGDATADIR}", mode = '0644',
            libtool = False, other_options = None):
        self.install(directory, sources, mode, libtool, other_options)


    def install_doc(self, sources, directory = "${DOCDIR}", mode = '0644',
            libtool = False, other_options = None):
        self.install(directory, sources, mode, libtool, other_options)


    def install_man(self, sources, directory = None, mode = '0644',
            other_options = None):
        if not directory:
            directory = "${MANDIR}"
        sources = process_nodes(sources)
        dirs = {}
        for s in sources:
            if s.endswith('.gz'):
                f = s[:-3]
            else:
                f = s
            sec = f.rsplit('.', 1)[1]
            d = dirs.get(sec)
            if not d:
                d = []
                dirs[sec] = d
            d.append(s)
        for d, s in dirs.items():
            self.install(opj(directory, "man%d" % int(d)), s, '0644')


    def uninstall(self):
        if not self.installed:
            mprint("Nothing to uninstall")
            return
        self.installed.reverse()
        for fs, libtool in self.installed:
            if libtool:
                cmd = ["${LIBTOOL}", "--mode=uninstall", "rm", "-f"] + fs
                cmd = [self.subst(c) for c in cmd]
                mprint("%s" % ' '.join(cmd))
                subprocess.call(cmd, cwd = self.build_dir)
            else:
                fs = [self.subst(f) for f in fs]
                if os.path.isdir(fs[0]):
                    # If first is directory, then so are the rest
                    rm = os.rmdir
                else:
                    rm = os.unlink
                for f in fs:
                    self.delete(f, rm)


    def delete(self, f, rm = None):
        """ Delete a file, which is processed with self.subst(). The default
        for rm is os.unlink, use os.rmdir for directories. """
        if not rm:
            rm = os.unlink
        f = self.subst(f)
        try:
            rm(f)
        except OSError:
            mprint("Failed to delete '%s'" % f)
        else:
            mprint("Removed '%s'" % f)


    def recursively_remove(self, target, fatal = False, excep = []):
        recursively_remove(self.subst(target), fatal, excep)


    def prune_directory(self, root):
        """ Expands variables in root and prefixes ${DESTDIR} before
        calling global version. """
        # Note we can't use opj because root is (usually) absolute
        root = os.path.normpath(self.subst("${DESTDIR}" + os.sep + root))
        mprint("Removing empty directories from '%s'" % root)
        return prune_directory(root)


    def __find_prog(self, name, env = os.environ):
        if os.path.isabs(name):
            return name
        path = env.get('PATH')
        if not path:
            path = os.environ['PATH']
        if not path:
            if mswin:
                path = 'C:\Windows'
            else:
                path = '/bin:/usr/bin:/usr/local/bin'
        if mswin:
            if not "mingw" in path.lower():
                path = ctx.env['MINGW_PATH'] + os.pathsep + path
            if not name.lower().endswith('exe'):
                name += '.exe'
        for p in path.split(os.pathsep):
            n = opj(p, name)
            if os.path.exists(n):
                return n
        raise MaitchNotFoundError("%s program not found in PATH" % name)


    def add_var(self, name, default = "", desc = "", as_arg = False):
        """
        Registers a variable name with a default value which will be used if the
        variable isn't specified on the command-line. If as_arg is True it can
        be specified as a -- option ie --foo-bar=baz is equivalent to the usual
        form FOO_BAR=baz. default may be a function, called as function(name)
        to calculate the default value dynamically.
        """
        self.var_repository.append([name, default, desc, as_arg])


    def find_prog_by_var(self, var, prog = None):
        p = self.prog_var_repository.get(var)
        if not p:
            if prog:
                p = prog
            else:
                p = var_to_s(var)
            try:
                p = self.find_prog(p)
            except MaitchNotFoundError:
                mprint("Warning: Program '%s' not found" % p, file = sys.stderr)
            self.prog_var_repository[var] = p
        return p


    def find_cxx(self, var):
        return self.find_prog_by_var(var, "g++")



class Rule(object):
    """
    Standard rule.
    """

    # Prevent race conditions when changing directory
    using_dir = False
    dir_lock = threading.Condition()
    cwd = None
    printed_cwd = None
    n_running = 0

    def __init__(self, **kwargs):
        """
        Possible arguments (all optional except targets):
        rule: A function or a string containing a command to be called.
                A string should contain "${TGT}" and/or "${SRC}" for
                targets and sources. This will not work if they contain spaces.
                A function is called as func(ctx, env, [targets], [sources])
                where ctx is the Context and targets and soures are expanded.
                Note env is not the same as ctx.env, it will have ${TGT} and
                ${SRC} added.
                An additional variable, ${TGT_DIR}, is set to the directory
                name of the first target. Note ${TGT_DIR} is absolute but
                ${TGT} is not.
                rule may be a heterogeneous list of functions or strings.
        sources: See process_nodes() func for what's valid.
        targets: As above, or a function which takes source(s) as input and
                returns target(s).
        deps:   Dependencies other than sources; deps are satisfied before
                sources.
        wdeps: "Weak dependencies":- the targets will not be built until after
                all wdeps are built, but the targets don't necessarily depend
                on the wdeps. This makes sure dynamic dependency tracking
                works properly when some headers are generated by other steps
                eg by making C compiler rules wdep on all files generated by
                gob2.
        dep_func: A function to calculate implicit deps; takes a ctx and rule
                as arguments and returns a list of filenames - absolute or
                relative to BUILD_DIR. This is used only to work out whether the
                target is out of date and needs to be rebuilt; it is not used
                when working out the dependency chain.
        use_shell: Whether to use shell if rule is a string (default False).
        dir:    Working directory for this rule. Use sparingly, it causes
                threads to block.
        env:    A dict containing env vars to override those from Context. Each
                var may refer to its own name in its value to derive values
                from the Context.
        quiet:  If True don't print the command about to be executed.
        where:  Where to look for sources: SRC, TOP or both (default SRC).
        lock:   Some jobs can't be run simultaneously so you can pass in a Lock
                object to prevent that.
        diffpat: If this is given (a string) it invokes special behaviour. For
                each target T, if T already exists it's backed up to T.old
                before running the rule. Then T is compared line-by-line with
                T.old. Lines containing a match for the regex in diffpat are
                skipped. If the files are equal T is replaced by T.old and
                touched. This is to prevent VCS etc conflicts when a build
                messes with headers in .pot and .po files but the main content
                is unchanged.
        verbose: Show dependency info if debug is enabled.
        """
        if not 'where' in kwargs:
            kwargs['where'] = SRC
        rule = kwargs.get('rule')
        if callable(rule) or isinstance(rule, basestring):
            self.rules = [rule]
        else:
            self.rules = rule
        self.sources = kwargs.get('sources')
        if self.sources and isinstance(self.sources, basestring):
            self.sources = process_nodes(self.sources)
        self.targets = kwargs['targets']
        if callable(self.targets):
            self.targets = self.targets(self.sources)
        elif isinstance(self.targets, basestring):
            self.targets = process_nodes(self.targets)
        self.deps = kwargs.get('deps')
        if self.deps and isinstance(self.deps, basestring):
            self.deps = process_nodes(self.deps)
        self.wdeps = kwargs.get('wdeps')
        if self.wdeps and isinstance(self.wdeps, basestring):
            self.wdeps = process_nodes(self.wdeps)
        self.dep_func = kwargs.get('dep_func')
        self.use_shell = kwargs.get('use_shell')
        self.dir = kwargs.get('dir')
        self.env = kwargs.get('env')
        self.quiet = kwargs.get('quiet')
        self.blocking = []
        self.blocked_by = []
        self.completed = False
        self.cached_env = None
        self.cached_targets = None
        self.cached_sources = None
        self.cached_deps = []
        self.where = kwargs['where']
        self.lock = kwargs.get('lock')
        if self.dir:
            Rule.using_dir = True
        diffpat = kwargs.get('diffpat')
        if diffpat:
            self.diffpat = re.compile(diffpat)
        else:
            self.diffpat = None
        self.verbose = kwargs.get('verbose', False)


    @staticmethod
    def init_var(kwargs, var):
        """ Call this from subclass' constructor if it uses var (specified in
        lower case). If kwargs includes a key 'var' (lower case) env[VAR_] is
        set to its value. Note the trailing _. This is because a variable
        overridden here would commonly want to refer to itself (as ${VAR}) but
        can't due to recursion. So accompanying variables should refer to one
        set here with the trailing _. If kw var is not present, env[VAR_] is set
        to ${VAR}. See CRule's use of libs and cflags for an example. """
        val = kwargs.get(var)
        if not val:
            val = "${%s}" % var.upper()
        env = kwargs.get('env')
        if not env:
            env = {}
            kwargs['env'] = env
        env[var.upper() + '_'] = val


    def init_cflags(self, kwargs):
        " For rules which use cflags. "
        self.init_var(kwargs, 'cflags')


    def init_libs(self, kwargs):
        " For rules which use libs. "
        self.init_var(kwargs, 'libs')


    def process_env(self):
        " Merges env with ctx's, with caching. Does not set TGT or SRC. "
        if self.cached_env == None:
            env = dict(self.ctx.env)
            if self.env:
                for k, v in self.env.items():
                    env[k] = v
            self.cached_env = env
        return self.cached_env


    def process_env_tgt_src(self):
        """ As process_env, but also returns expanded targets and sources
        [env, targets sources] and adds them to env. """
        env = self.process_env()
        if self.cached_targets == None:
            # Expand targets and sources, finding the sources, and prefixing
            # targets with build_dir.
            targets = [subst(env, t) for t in self.targets]
            if self.sources:
                sources = [self.ctx.find_source(subst(env, s),
                                self.dir, self.where) \
                        for s in self.sources]
            else:
                sources = None
            # Add them to env
            if sources:
                env['SRC'] = ' '.join(sources)
            else:
                env['SRC'] = ''
            if targets:
                env['TGT'] = ' '.join(targets)
                td = os.path.dirname(targets[0])
                if not os.path.isabs(td):
                    td = opj(self.ctx.build_dir, td)
                env['TGT_DIR'] = td
            else:
                env['TGT'] = ''
                env['TGT_DIR'] = ''
            self.cached_targets = targets
            self.cached_sources = sources
        return [env, self.cached_targets, self.cached_sources]


    def run(self):
        " Run a job with thread-safe directory management. "
        if not Rule.using_dir:
            self.__inner_run()
            return
        Rule.dir_lock.acquire()
        try:
            if self.dir:
                self.dir = self.ctx.subst(self.dir)
            if self.dir != Rule.cwd:
                # Wait for current rule to finish before changing cwd
                #dprint("%s wants to use dir '%s', waiting for '%s'" \
                #        % (to_str(self), self.dir, Rule.cwd))
                while Rule.n_running > 1:
                    Rule.dir_lock.wait()
                #dprint("%s woke up to use dir '%s'" % (to_str(self), self.dir))
                if self.dir:
                    dir_ = self.dir
                    self.ctx.ensure_out_dir(dir_)
                else:
                    dir_ = self.ctx.build_dir
                os.chdir(dir_)
                Rule.cwd = self.dir
        except:
            Rule.dir_lock.release()
            raise
        Rule.n_running += 1
        #dprint("%s increasing n_running to %d and releasing dir lock" \
        #        % (to_str(self), Rule.n_running))
        Rule.dir_lock.release()
        self.__inner_run()
        #dprint("%s reacquring dir lock" % to_str(self))
        Rule.dir_lock.acquire()
        try:
            Rule.n_running -= 1
            #dprint("%s decreasing n_running to %d" \
            #        % (to_str(self), Rule.n_running))
            Rule.dir_lock.notify()
        except:
            Rule.dir_lock.release()
            raise
        #dprint("%s done, releasing dir lock" % to_str(self))
        Rule.dir_lock.release()

    """
    def dump_uv(self, u, v):
        f = open("/home/tony/roxterm/build/u", "w")
        for l in u:
            f.write(l)
        f.close()
        f = open("/home/tony/roxterm/build/v", "w")
        for l in v:
            f.write(l)
        f.close()
        sys.exit(1)
    """

    def __inner_run(self):
        if self.is_uptodate():
            if self.verbose:
                dprint("%s is up-to-date" % self)
            return
        if self.dir != Rule.printed_cwd:
            d = Rule.printed_cwd
            if not d:
                d = self.ctx.abs_build_dir
            mprint('make[0]: Leaving directory "%s"' % d)
            d = self.dir
            if not d:
                d = self.ctx.abs_build_dir
            mprint('make[0]: Entering directory "%s"' % d)
            Rule.printed_cwd = self.dir
        env, targets, sources = self.process_env_tgt_src()
        if self.lock:
            self.lock.acquire()
        for t in targets:
            dprint("Creating directory for target '%s'" % t)
            self.ctx.ensure_out_dir_for_file(t)
        if self.diffpat:
            for t in self.targets:
                t = self.ctx.subst(t)
                if os.path.exists(t):
                    shutil.copy(t, t + '.old')
        try:
            for rule in self.rules:
                if callable(rule):
                    if self.quiet:
                        p = dprint
                    else:
                        p = mprint
                    p("Internal function: %s(%s, %s)" %
                            (rule.__name__, to_str(targets), to_str(sources)))
                    rule(self.ctx, env, targets, sources)
                else:
                    r = subst(env, rule)
                    if self.use_shell:
                        prog = r
                    else:
                        prog = r.split()
                    if self.dir:
                        dir_ = self.dir
                    else:
                        dir_ = self.ctx.build_dir
                    if call_subprocess(prog,
                            shell = self.use_shell, cwd = dir_,
                            quiet = self.quiet):
                        dprint("%s NZ error code" % r)
                        raise MaitchChildError("Rule '%s' failed" % r)
                    else:
                        dprint("%s executed successfully" % r)
        except:
            raise
        else:
            if self.diffpat:
                for t in self.targets:
                    same = False
                    t = self.ctx.subst(t)
                    s = t + '.old'
                    if os.path.exists(t) and os.path.exists(s):
                        f = open_utf8(s, 'r')
                        u = []
                        for l in f.readlines():
                            if not self.diffpat.search(l):
                                u.append(l)
                        f.close()
                        f = open_utf8(t, 'r')
                        v = []
                        for l in f.readlines():
                            if not self.diffpat.search(l):
                                v.append(l)
                        f.close()
                        if len(u) == len(v):
                            same = True
                            for n in range(len(u)):
                                if u[n] != v[n]:
                                    same = False
                                    break
                        if same:
                            os.rename(s, t)
                        else:
                            os.unlink(s)
        finally:
            if self.lock:
                self.lock.release()


    def __repr__(self):
        return "JT:%s" % to_str(self.targets)
        #return "T:%s S:%s" % (self.targets, self.sources)


    def list_static_deps(self):
        """ Works out a rule's static dependencies ie deps + sources, but not
        dep_func. Caches them and returns list. """
        if self.deps:
            deps = self.deps
        else:
            deps = []
        if self.sources:
            deps += self.sources
        self.cached_deps = deps
        return deps


    def is_uptodate(self):
        """ Returns False if any target is older than any source, dep, or result
        of dep_func (implicit/dynamic deps). """
        # If there are no dependencies target(s) must be rebuilt every time
        if self.verbose:
            dprint("Checking whether %s is up-to-date, cached_deps %s" % \
                    (self, self.cached_deps))
        if not self.cached_deps:
            if self.verbose:
                dprint("  %s has no deps, assuming not up-to-date" % self)
            return False
        # First find whether uptodate wrt static deps.
        # If result is True extra variable newest_dep is available
        uptodate = True
        verbose = self.verbose
        if verbose:
            verbose = "  "
        try:
            oldest_target = self.ctx.get_oldest(self.targets, self.dir,
                    NOWHERE, verbose)
        except (MaitchNotFoundError, KeyError):
            oldest_target = None
        if not oldest_target:
            uptodate = False
        if self.verbose:
            dprint("  %s oldest target is %s" % (self, oldest_target))
        if uptodate:
            # All sources and deps should be available at this point so
            # OK to let exception propagate
            newest_dep = self.ctx.get_newest(self.cached_deps, self.dir,
                    self.where, verbose)
            dprint("  %s newest dep is %s" % (self, newest_dep))
            if newest_dep and (newest_dep > oldest_target):
                if verbose:
                    dprint("  %s: %s > %s" % (self, newest_dep, oldest_target))
                uptodate = False
        else:
            if self.verbose:
                dprint("  %s had no target, not testing deps" % self)
            newest_dep = None

        if uptodate and self.dep_func:
            if verbose:
                dprint("  %s has dep_func" % self)
            # Work out whether cached dynamic deps need updating
            dyn_deps = None
            deps_name = self.ctx.make_out_path(self.ctx.subst(
                    opj(".maitch", "deps", self.targets[0])))
            if os.path.exists(deps_name):
                deps_stamp = os.stat(deps_name).st_mtime
                if not newest_dep:
                    newest_dep = self.ctx.get_newest(self.cached_deps,
                            self.dir, self.where)
                if newest_dep and newest_dep > deps_stamp:
                    # sources/static deps are newer than dynamics
                    rebuild_deps = True
                else:
                    # see whether cached deps are older than any file they list
                    dyn_deps = load_deps(deps_name)
                    try:
                        newest_impl_dep = self.ctx.get_newest(dyn_deps,
                                self.dir)
                    except MaitchNotFoundError:
                        # Some header must have moved, deps need rebuilding
                        rebuild_deps = True
                    else:
                        if newest_impl_dep > newest_dep:
                            newest_dep = newest_impl_dep
                        rebuild_deps = newest_impl_dep > deps_stamp
            else:
                rebuild_deps = True
            if rebuild_deps:
                dyn_deps = self.dep_func(self.ctx, self)
                self.ctx.ensure_out_dir_for_file(deps_name)
                fp = open(deps_name, 'w')
                for d in dyn_deps:
                    fp.write(d + '\n')
                fp.close()
            if not dyn_deps:
                dyn_deps = load_deps(deps_name)
            # Now we have up-to-date implicit dyn_deps, check whether targets
            # are older than them
            try:
                if self.ctx.get_newest(dyn_deps, self.dir) > oldest_target:
                    uptodate = False
            except:
                uptodate = False
        else:
            if verbose:
                if uptodate:
                    dprint("  %s has no dep_func" % self)
                else:
                    dprint(("  %s: skipping dep_func because out of date " + \
                            "wrt static deps") % self)

        if verbose:
            if uptodate:
                dprint("  %s is up to date" % self)
            else:
                dprint("  %s is not up to date" % self)
        return uptodate



class SuffixRule(Rule):
    """ A rule where targets is a function that transforms sources by changing
    their suffix, and optionally prefix. """
    def __init__(self, **kwargs):
        """ args are similar to those for a standard Rule but targets should
        not be specified. deps are complete filenames as with explicit Rules.
        sources and rule are compulsory.

        suffix (compulsory): Suffix to be applied to targets. Source suffixes to
                be stripped are inferred by looking for last period. Do not
                include period, it's implied.
        prefix (optional): Added to the start of the targets' leafname(s) -
                after any directory components. Any separator between the prefix
                and leafname (eg '-') should be included at the end of the
                prefix. """
        self.suffix = kwargs['suffix']
        self.prefix = kwargs.get('prefix', '')
        set_default(kwargs, 'targets', self.transform)
        Rule.__init__(self, **kwargs)


    def transform(self, sources):
        targets = []
        for s in sources:
            s = s.rsplit('.', 1)[0]
            if len(self.prefix):
                p, l = os.path.split(s)
                l = self.prefix + l
                if p:
                    s = os.path.join(p, l)
                else:
                    s = l
            targets.append(s + '.' + self.suffix)
        return targets



class TouchRule(Rule):
    """ Use this as a dummy rule rather than use a Rule with no rule parameter.
    The target(s) will be "touched" to update their timestamp. """
    def __init__(self, **kwargs):
        set_default(kwargs, 'rule', self.touch)
        Rule.__init__(self, **kwargs)


    def touch(self, ctx, env, tgts, srcs):
        for t in tgts:
            os.utime(t, None)



class CRuleBase(SuffixRule):
    " Standard rule for compiling C to an object file. "
    def __init__(self, **kwargs):
        self.flagsname = kwargs['flagsname']
        set_default(kwargs, 'rule', "${%s} ${%s_} -c -o ${TGT} ${SRC}" %
                (kwargs['compiler'], self.flagsname))
        set_default(kwargs, 'suffix', "o")
        set_default(kwargs, 'dep_func', self.get_implicit_deps)
        SuffixRule.__init__(self, **kwargs)


    def get_implicit_deps(self, ctx, rule):
        # rule will be a static rule generated from self with a single source
        env = self.process_env()
        try:
            return ctx.deps_from_cpp(rule.sources, env[self.flagsname + '_'])
        except MaitchNotFoundError:
            return None



class CRule(CRuleBase):
    " Standard rule for compiling C to an object file. "
    def __init__(self, **kwargs):
        self.init_cflags(kwargs)
        set_default(kwargs, 'compiler', "CC");
        set_default(kwargs, 'flagsname', "CFLAGS");
        CRuleBase.__init__(self, **kwargs)



class CxxRule(CRuleBase):
    " Standard rule for compiling C++ to an object file. "
    def __init__(self, **kwargs):
        self.init_var(kwargs, 'cxxflags')
        set_default(kwargs, 'compiler', "CXX");
        set_default(kwargs, 'flagsname', "CXXFLAGS");
        CRuleBase.__init__(self, **kwargs)



class LibtoolCRuleBase(CRuleBase):
    def __init__(self, **kwargs):
        """ Additional kwargs:
            libtool_flags.
            libtool_mode_arg: -shared, -static etc.
        """
        self.init_var(kwargs, 'libtool_flags')
        self.init_var(kwargs, 'libtool_mode_arg')
        set_default(kwargs, 'suffix', "lo")
        set_default(kwargs, 'rule',
                "${LIBTOOL} --mode=compile --tag=%s ${LIBTOOL_FLAGS_} "
                "${%s} ${LIBTOOL_MODE_ARG_} ${%s_} -c -o ${TGT} ${SRC}" %
                (kwargs['tag'], kwargs['compiler'], kwargs['flagsname']))
        CRuleBase.__init__(self, **kwargs)



class LibtoolCRule(LibtoolCRuleBase):
    " libtool version of CRule. "
    def __init__(self, **kwargs):
        """ Additional kwargs:
            libtool_flags.
            libtool_mode_arg: -shared, -static etc.
        """
        self.init_cflags(kwargs)
        set_default(kwargs, 'compiler', "CC");
        set_default(kwargs, 'flagsname', "CFLAGS");
        set_default(kwargs, 'tag', "CC");
        LibtoolCRuleBase.__init__(self, **kwargs)



class LibtoolCxxRule(LibtoolCRuleBase):
    " libtool version of CxxRule. "
    def __init__(self, **kwargs):
        """ Additional kwargs:
            libtool_flags.
            libtool_mode_arg: -shared, -static etc.
        """
        self.init_var(kwargs, 'cxxflags')
        set_default(kwargs, 'compiler', "CXX");
        set_default(kwargs, 'flagsname', "CXXFLAGS");
        set_default(kwargs, 'tag', "CXX");
        LibtoolCRuleBase.__init__(self, **kwargs)



class ShlibCRule(LibtoolCRule):
    " Compiles C into an object file suitable for a shared library. "
    def __init__(self, **kwargs):
        kwargs['libtool_mode_arg'] = "-shared %s" % \
                kwargs.get('libtool_mode_arg', '')
        LibtoolCRule.__init__(self, **kwargs)



class StaticLibCRule(LibtoolCRule):
    " Compiles C into an object file suitable for a static library. "
    def __init__(self, **kwargs):
        kwargs['libtool_mode_arg'] = "-static %s" % \
                kwargs.get('libtool_mode_arg', '')
        LibtoolCRule.__init__(self, **kwargs)



class ShlibCxxRule(LibtoolCxxRule):
    " Compiles C++ into an object file suitable for a shared library. "
    def __init__(self, **kwargs):
        kwargs['libtool_mode_arg'] = "-shared %s" % \
                kwargs.get('libtool_mode_arg', '')
        LibtoolCxxRule.__init__(self, **kwargs)



class StaticLibCxxRule(LibtoolCxxRule):
    " Compiles C++ into an object file suitable for a static library. "
    def __init__(self, **kwargs):
        kwargs['libtool_mode_arg'] = "-static %s" % \
                kwargs.get('libtool_mode_arg', '')
        LibtoolCxxRule.__init__(self, **kwargs)



class ProgramRuleBase(Rule):
    " Standard rule for linking mutiple object files and libs into a program. "
    def __init__(self, **kwargs):
        self.init_libs(kwargs)
        self.init_var(kwargs, 'ldflags')
        if mswin:
            targs = process_nodes(kwargs['targets'])
            for n in range(len(targs)):
                if not targs[n].lower().endswith('.exe'):
                    targs[n] += '.exe'
            kwargs['targets'] = targs
        set_default(kwargs, 'rule',
                "${%s} ${%s_} ${LDFLAGS_} -o ${TGT} ${SRC} ${LIBS_}" %
                (kwargs['linker'], kwargs['flagsname']))
        Rule.__init__(self, **kwargs)



class CProgramRule(ProgramRuleBase):
    "Standard rule for linking C object files and libs into a program."
    def __init__(self, **kwargs):
        self.init_cflags(kwargs)
        set_default(kwargs, 'linker', "CC");
        set_default(kwargs, 'flagsname', "CFLAGS");
        ProgramRuleBase.__init__(self, **kwargs)



class CxxProgramRule(ProgramRuleBase):
    "Standard rule for linking C++ object files and libs into a program."
    def __init__(self, **kwargs):
        self.init_var(kwargs, 'cxxflags')
        set_default(kwargs, 'linker', "CXX");
        set_default(kwargs, 'flagsname', "CXXFLAGS");
        ProgramRuleBase.__init__(self, **kwargs)



class LibtoolProgramRuleBase(ProgramRuleBase):
    " Use libtool during linking. "
    def __init__(self, **kwargs):
        self.init_var(kwargs, 'libtool_flags')
        self.init_var(kwargs, 'libtool_mode_arg')
        set_default(kwargs, 'rule',
                "${LIBTOOL} --mode=link --tag=%s ${LIBTOOL_FLAGS_} "
                "${%s} ${LIBTOOL_MODE_ARG_} "
                "${%s_} ${LIBS_} ${LDFLAGS_} -o ${TGT} ${SRC}" %
                (kwargs['tag'], kwargs['linker'], kwargs['flagsname']))
        ProgramRuleBase.__init__(self, **kwargs)



class LibtoolCProgramRule(LibtoolProgramRuleBase):
    " Use libtool to link C. "
    def __init__(self, **kwargs):
        self.init_cflags(kwargs)
        set_default(kwargs, 'linker', "CC");
        set_default(kwargs, 'flagsname', "CFLAGS");
        set_default(kwargs, 'tag', "CC");
        LibtoolProgramRuleBase.__init__(self, **kwargs)



class LibtoolCxxProgramRule(LibtoolProgramRuleBase):
    " Use libtool to link C. "
    def __init__(self, **kwargs):
        self.init_var(kwargs, 'cxxflags')
        set_default(kwargs, 'linker', "CXX");
        set_default(kwargs, 'flagsname', "CXXFLAGS");
        set_default(kwargs, 'tag', "CXX");
        LibtoolProgramRuleBase.__init__(self, **kwargs)



class CShlibRule(LibtoolCProgramRule):
    """ Standard rule to create a shared C library with libtool. See the
    libtool manual for an explanation of its interface version system.
    -release is not supported (yet). """
    def __init__(self, **kwargs):
        version = kwargs.get('libtool_version')
        if version:
            version = "-version-info %d:%d:%d" % tuple(version)
        else:
            version = ""
        kwargs['libtool_mode_arg'] = "-shared %s %s" % \
                (kwargs.get('libtool_mode_arg', ''), version)
        LibtoolCProgramRule.__init__(self, **kwargs)



class CxxShlibRule(LibtoolCxxProgramRule):
    """ Standard rule to create a shared C++ library with libtool. See the
    libtool manual for an explanation of its interface version system.
    -release is not supported (yet). """
    def __init__(self, **kwargs):
        version = kwargs.get('libtool_version')
        if version:
            version = "-version-info %d:%d:%d" % tuple(version)
        else:
            version = ""
        kwargs['libtool_mode_arg'] = "-shared %s %s" % \
                (kwargs.get('libtool_mode_arg', ''), version)
        LibtoolCxxProgramRule.__init__(self, **kwargs)



class CStaticLibRule(LibtoolCProgramRule):
    """ Standard rule to create a static C library with libtool. See the
    libtool manual for an explanation of its interface version system.
    -release is not supported (yet). """
    def __init__(self, **kwargs):
        version = kwargs.get('libtool_version')
        if version:
            version = "-version-info %d:%d:%d" % tuple(version)
        else:
            version = ""
        kwargs['libtool_mode_arg'] = "-static %s %s" % \
                (kwargs.get('libtool_mode_arg', ''), version)
        LibtoolCProgramRule.__init__(self, **kwargs)



class CxxStaticLibRule(LibtoolCxxProgramRule):
    """ Standard rule to create a static C++ library with libtool. See the
    libtool manual for an explanation of its interface version system.
    -release is not supported (yet). """
    def __init__(self, **kwargs):
        version = kwargs.get('libtool_version')
        if version:
            version = "-version-info %d:%d:%d" % tuple(version)
        else:
            version = ""
        kwargs['libtool_mode_arg'] = "-static %s %s" % \
                (kwargs.get('libtool_mode_arg', ''), version)
        LibtoolCxxProgramRule.__init__(self, **kwargs)



def mkdir_rule(ctx, env, targets, sources):
    """ A rule function to ensure targets' directories exist. """
    for t in targets:
        ctx.ensure_out_dir(t)


def mk_parent_dir_rule(ctx, env, targets, sources):
    """ A rule function to ensure targets' directories exist. """
    for t in targets:
        ctx.ensure_out_dir_for_file(t)


gettext_diffpat = '^"(#-#-#-#-#|POT-Creation-Date:|PO-Revision-Date:|' + \
        'Language:|MIME-Version:|Content-Type:|Content-Transfer-Encoding:|' + \
        'Project-Id-Version:)'


def manipulate_kwargs_for_pot_rule(ctx, kwargs, potfiles = False):
    """ Helper function. It processes the following args for certain rules:

    XGETTEXT is not set by default. *_XGETTEXT_OPTS is generated on the fly.

    Special args:
    copyright_holder
    package
    version
    bugs_addr
    opts_prefix: Goes on front of _XGETTEXT_OPTS added to env from above args
    xgettext_opts: Additional xgettext_opts

    diffpat is set to match certain headers that xgettext adds or removes
    at will.

    dir must be set to the directory in which you want the pot file to be
    output, for correct relative paths to files referenced in the pot file
    and/or potfiles.
    """

    def pot_deps(ctx, rule):
        deps = []
        for s in process_nodes(rule.sources):
            fp = open(ctx.subst(s), 'r')
            for f in fp.readlines():
                deps.append(f.strip())
        return deps

    opts_prefix = kwargs.get('opts_prefix', "")
    varname = "%s_XGETTEXT_OPTS" % opts_prefix
    if not 'where' in kwargs:
        kwargs['where'] = SRC | TOP
    targets = kwargs.get('targets')
    if not targets:
        targets = ["${TOP_DIR}/po/${PACKAGE}.pot"]
        kwargs['targets'] = targets
    elif isinstance(targets, basestring):
        targets = [targets]
    for n in range(len(targets)):
        t = ctx.subst(targets[n])
        if not os.path.isabs(t):
            targets[n] = opap(t)
    if potfiles:
        potfiles = " -f"
    else:
        potfiles = ""
    xgto = kwargs.get('xgettext_opts', None)
    if not xgto:
        xgto = ""
    else:
        xgto = " " + xgto
    if not 'rule' in kwargs:
        kwargs['rule'] = "${XGETTEXT} ${%s}%s%s ${SRC} -o ${TGT}" % \
                (varname, xgto, potfiles)
    if potfiles and not 'dep_func' in kwargs:
        kwargs['dep_func'] = pot_deps
    xgto = []
    copyrt = kwargs.get('copyright_holder')
    if copyrt:
        xgto.append('--copyright-holder=%s' % copyrt)
    pkg = kwargs.get('package')
    if not pkg:
        pkg = "${PACKAGE}"
    xgto.append('--package-name=${PACKAGE}')
    ver = kwargs.get('version')
    if ver:
        xgto.append('--package-version=%s' % ver)
    ba = kwargs.get('bugs_addr')
    if ba:
        xgto.append('--msgid-bugs-address=%s' % ba)
    for n in range(len(xgto)):
        s = ctx.subst(xgto[n])
        if any([ascii.isspace(c) for c in s]):
            if "'" in s:
                if '"' in s:
                    raise MaitchRuleError(
                            "Unable to quote xgettext option: %s" % s)
                xgto[n] = '"%s"' % s
            else:
                xgto[n] = "'%s'" % s
            kwargs['use_shell'] = True
    ctx.setenv(varname, ' '.join(xgto))
    kwargs['diffpat'] = gettext_diffpat


class PotRule(Rule):
    """ See manipulate_kwargs_for_pot_rule for special args.

    potfiles: If True, the source is a POTFILES, use xgettext's -f option
    """
    def __init__(self, ctx, **kwargs):
        potfiles = kwargs.get('potfiles', False)
        manipulate_kwargs_for_pot_rule(ctx, kwargs, potfiles)
        Rule.__init__(self, **kwargs)


def PotRules(ctx, **kwargs):
    """ Returns a pair (list) of rules for generating a .pot file from a list of
    source files eg POTFILES.in where filenames are relative to TOP_DIR.
    Default source is "${TOP_DIR}/po/POTFILES.in",
    default target is ${TOP_DIR}/po/${PACKAGE}.pot.

    See manipulate_kwargs_for_pot_rule for special args.

    """
    def generate_potfiles(ctx, env, targets, sources):
        potfiles = []
        relpath = ".."
        for s in sources:
            fp = open(subst(env, s), 'r')
            for f in fp.readlines():
                f = f.strip()
                if len(f) and f[0] != '#':
                    potfiles.append(opj(relpath, f))
            fp.close()
        t = subst(env, targets[0])
        ctx.ensure_out_dir_for_file(t)
        fp = open(t, 'w')
        for f in potfiles:
            fp.write("%s\n" % f)
        fp.close()

    podir = "${ABS_TOP_DIR}/po"
    kwargs['dir'] = podir
    manipulate_kwargs_for_pot_rule(ctx, kwargs, True)

    src1 = kwargs.get('sources', podir + "/POTFILES.in")
    rule1 = Rule(rule = generate_potfiles,
            sources = opap(ctx.subst(src1)),
            targets = ["${ABS_BUILD_DIR}/po/POTFILES"],
            dir = podir,
            where = kwargs['where'])

    kwargs['sources'] = ["${ABS_BUILD_DIR}/po/POTFILES"]
    rule2 = Rule(**kwargs)

    return [rule1, rule2]


class PoRule(TouchRule):
    """ Updates a po file from a pot (default src is
    ${ABS_TOP_DIR}/po/${PACKAGE}.pot). """
    def __init__(self, *args, **kwargs):
        if not 'sources' in kwargs:
            kwargs['sources'] = "${ABS_TOP_DIR}/po/${PACKAGE}.pot"
        if not 'rule' in kwargs:
            kwargs['rule'] = ["${MSGMERGE} -q -U ${TGT} ${SRC}", self.touch]
        kwargs['diffpat'] = gettext_diffpat
        Rule.__init__(self, *args, **kwargs)



def parse_linguas(ctx, podir = None, linguas = None):
    if not podir:
        podir = opj("${ABS_TOP_DIR}", "po")
    if not linguas:
        linguas = opj(podir, "LINGUAS")
    langs = []
    fp = open(ctx.subst(linguas), 'r')
    for l in fp.readlines():
        l = l.strip()
        if not l or l[0] == '#':
            continue
        langs.append(l)
    fp.close()
    return langs



def foreach_lingua(ctx, fn, podir = None, linguas = None, prefix = None):
    """ Runs fn(ctx, lang, f) for each lang found in linguas,
        where f is .po file.
        Default podir is '${ABS_TOP_DIR}/po'
        Default linguas is ${podir}/LINGUAS.
    """
    if not podir:
        podir = opj("${ABS_TOP_DIR}", "po")
    if not linguas:
        linguas = opj(podir, "LINGUAS")
    langs = parse_linguas(ctx, linguas = linguas)
    for l in langs:
        if prefix:
            l = prefix + l
        f = opj(podir, l + ".po")
        if not os.path.isfile(ctx.subst(f)):
            raise MaitchNotFoundError("Linguas file %s includes %s, "
                    "but no corresponding po file found" % (linguas, l))
        fn(ctx, l, f)


def PoRulesFromLinguas(ctx, *args, **kwargs):
    """ Generates a PoRule and .mo for each language listed in linguas. Default
        linguas is podir/LINGUAS. Default podir is ${ABS_TOP_DIR}/po. Default
        modir is ${ABS_BUILD_DIR}/po. Default pot file is po/${PACKAGE}.pot,
        otherwise specify in sources. Other args are passed to each PoRule. Also
        generates .mo rules unless nomo is True. If prefix arg is given this is
        added to po and mo filenames.
     """
    nomo = kwargs.get("nomo")
    prefix = kwargs.get("prefix")
    podir = kwargs.get("podir")
    if not podir:
        podir = opj("${ABS_TOP_DIR}", "po")
    modir = kwargs.get("modir")
    if not modir:
        modir = opj("${ABS_BUILD_DIR}", "po")
    rules = []

    def add_po_rule(ctx, l, f):
        kwargs['targets'] = f
        rules.append(PoRule(*args, **kwargs))
        if not nomo:
            rules.append(Rule(rule = "${MSGFMT} -c -o ${TGT} ${SRC}",
                    targets = opj(modir, l + ".mo"),
                    sources = f,
                    dir = podir))

    foreach_lingua(ctx, add_po_rule,
            kwargs.get('podir'), kwargs.get('linguas'), kwargs.get('prefix'))
    return rules



def call_subprocess(*args, **kwargs):
    """ Like subprocess.Call() with stdout and stderr logged.
    stdout and stderr in kwargs are overridden. """
    kwargs['stdout'] = subprocess.PIPE
    kwargs['stderr'] = subprocess.PIPE
    if isinstance(args[0], basestring):
        c = args[0]
    else:
        c = ' '.join(args[0])
    if not kwargs.get('quiet'):
        mprint(c)
    if 'quiet' in kwargs:
        del kwargs['quiet']
    sp = subprocess.Popen(*args, **kwargs)
    [out, err] = sp.communicate()
    out = to_str(out).strip()
    err = to_str(err).strip()
    if out:
        dprint(out)
    if err:
        mprint(err, file = sys.stderr)
    return sp.returncode


def report_exception():
    """ Reports the last raised exception. """
    mprint(traceback.format_exc(), file = sys.stderr)



def print_formatted(body, columns = 80, heading = None, h_columns = 20):
    """ Prints body, wrapped at the specified number of columns. If heading is
    given, h_columns are reserved on the left for it. """
    if heading and len(heading) >= h_columns:
        print_wrapped(heading, columns)
        print_wrapped(body, columns, h_columns)
    elif heading:
        print_wrapped(heading + ' ' * (h_columns - len(heading)) + body,
                columns, h_columns, 0)
    else:
        print_wrapped(body, columns, h_columns)


def print_wrapped(s, columns = 80, indent = 0, first_indent = None,
        file = sys.stdout):
    """ Prints s wrapped to fit in columns, optionally indented,
    with an optional alternative indent for the first line. """
    if first_indent == None:
        first_indent = indent
    i = ' ' * first_indent
    current_indent = first_indent
    while len(s) > columns - current_indent:
        l = s[:columns - current_indent]
        s = s[columns - current_indent:]
        if ascii.isspace(l[-1]):
            l = l[:-1]
            split = []
        else:
            split = l.rsplit(None, 1)
        if len(split) > 1:
            l = split[0]
            s = split[1] + s
        file.write("%s%s\n" % (i, l))
        i = ' ' * indent
        current_indent = indent
    if s:
        file.write("%s%s\n" % (i, s))
    file.flush()



def subst_file(env, source, target, at = False):
    """ Run during configure phase to create a copy of source as target
    with ${} constructs substituted. Uses save_if_different() to avoid
    unnecessary rebuilds. """
    fp = open_utf8(subst(env, source), 'r')
    s = fp.read()
    fp.close()
    save_if_different(subst(env, target), subst(env, s, at = at))


def save_if_different(filename, content):
    """ Saves content to filename, only if file doesn't already contain
    identical content. """
    if os.path.exists(filename):
        fp = open_utf8(filename, 'r')
        old = fp.read()
        fp.close()
    else:
        old = None
    if content != old:
        if old == None:
            mprint("Creating '%s'" % filename)
        else:
            mprint("Updating '%s'" % filename)
        fp = open_utf8(filename, 'w')
        fp.write(content)
        fp.close()
    else:
        mprint("'%s' is unchanged" % filename)



def set_default(d, k, v):
    " Sets d[k] = v only if d doesn't already contain k. "
    if not d.get(k):
        d[k] = v



def opj(*args):
    """ Like os.path.join and also calls os.path.normpath """
    return os.path.normpath(os.path.join(*args))



def opap(p):
    """ Like os.path.abspath and also calls os.path.normpath """
    return os.path.normpath(os.path.abspath(p))



def prune_directory(root):
    """ Recursively moves all empty directories at root. Returns False if
    remaining files meant one or more directories could not be deleted. """
    if not os.path.exists(root):
        return True
    success = True
    subs = os.listdir(root)
    for n in subs:
        n = opj(root, n)
        if os.path.isdir(n):
            success = prune_directory(n) and success
        elif os.path.exists(n):
            mprint("Unable to remove non-empty directory '%s'" % root,
                    file = sys.stderr)
            success = False
    if success:
        try:
            os.rmdir(root)
        except:
            mprint("Unable to remove directory '%s'" % root, file = sys.stderr)
            success = False
    return success



_subst_re = re.compile(r"(\$\{-?([a-zA-Z0-9_]+)\})")
_subst_re_at = re.compile(r"(@-?([a-zA-Z0-9_]+)@)")

def subst(env, s, novar = NOVAR_FATAL, recurse = True, at = False):
    """
    Processes string s, substituting ${var} with values from dict env
    with var as the key. To prevent substitution put a '-' after the
    opening brace. It will be removed. Most variables are expanded
    recursively immediately before use.
    See comment where NOVAR_ constants for description of novar.
    If at is True, substitute @VAR@ instead.
    """
    def ms(match):
        s = match.group(2)
        if s[0] == '-':
            if at:
                return "@%s@" % s[1:]
            else:
                return "${%s}" % s[1:]
        elif novar == NOVAR_FATAL:
            return env[s]
        else:
            if novar == NOVAR_BLANK:
                dr = ''
            else:
                dr = match.group(0)
            return env.get(s, dr)
    if at:
        rex = _subst_re_at
    else:
        rex = _subst_re
    result, n = rex.subn(ms, s)
    if recurse and n:
        return subst(env, result, novar, True, at)
    return result



def process_nodes(nodes):
    """
    nodes may be a string with a single node filename, several names
    separated by spaces, or a list of strings - one per node, each may
    contain spaces. Returns a list of nodes.
    """
    if isinstance(nodes, basestring):
        return nodes.split()
    else:
        return list(nodes)


def recursively_remove(path, fatal, excep):
    """ Deletes path and all its contents, leaving behind exceptions.
    Returns False if path could not be deleted because it contains an
    exception. If something can not be deleted only propagate exception
    if fatal is True. """
    if fatal:
        contents = os.listdir(path)
    else:
        try:
            contents = os.listdir(path)
        except:
            return True
    removable = True
    if contents:
        for f in contents:
            f = opj(path, f)
            if f in excep:
                removable = False
            elif os.path.isdir(f):
                if not recursively_remove(f, fatal, excep):
                    removable = False
            elif fatal:
                os.unlink(f)
            else:
                try:
                    os.unlink(f)
                except OSError:
                    removable = False
    if removable:
        if fatal:
            os.rmdir(path)
        else:
            try:
                os.rmdir(path)
            except OSError:
                removable = False
    return removable



def s_to_var(s):
    return s.upper().replace('-', '_').replace('.', '_').replace(' ', '_')

def var_to_s(s):
    return s.lower().replace('_', '-')

def arg_to_var(s):
    return s_to_var(s[2:])

def var_to_arg(s):
    return '--' + var_to_s(s)



def make_var_name(template, upper = False):
    """ Makes an eligible variable name from template by replacing special
    characters with '_' and also prepending a '_' if template has a leading
    digit. ALso optionally converts to upper case. """
    if ascii.isdigit(template[0]):
        s = "_"
    else:
        s = ""
    for c in template:
        if c != '_' and not ascii.isalnum(c):
            s += "_"
        else:
            s += c
    if upper:
        s = s.upper()
    return s



def change_suffix(files, old, new):
    """ Returns a new list of files with old suffix replaced with new
    (include the '.' in the parameters). files may be a space-separated string
    or a list/tuple of strings. Non-matching suffixes are left unchanged. """
    changed = []
    if isinstance(files, basestring):
        files = files.split()
    l = len(old)
    for f in files:
        if f.endswith(old):
            f = f[:-l] + new
        changed.append(f)
    return changed


def add_prefix(files, prefix):
    """ Returns a new list of files with prefix added to leafname.
    files may be a space-separated string or a list/tuple of strings. """
    changed = []
    if isinstance(files, basestring):
        files = files.split()
    changed = []
    for f in files:
        head, tail = os.path.split(f)
        changed.append(opj(head, prefix + tail))
    return changed


def change_suffix_with_prefix(files, old, new, prefix):
    return add_prefix(change_suffix(files, old, new), prefix)



def get_extreme_stamp(nodes, comparator, verbose = None):
    """ Gets stamp for each item in nodes and returns the highest
    according to comparator. Returns None for an empty list or raises
    MaitchNotFoundError if any member is not found. """
    stamp = None
    nodest = None
    for n in nodes:
        if not os.path.exists(n):
            raise MaitchNotFoundError("Can't find '%s' to get timestamp" % n)
        s = os.stat(n).st_mtime
        if stamp == None:
            nodest = n
            stamp = s
        else:
            r = comparator(s, stamp)
            if r == True or r > 0:
                nodest = n
                stamp = s
    if verbose:
        dprint("%s of %s is %s: %s" % (verbose, nodes, nodest, to_str(stamp)))
    return stamp


def get_oldest(nodes):
    """ See get_extreme_stamp(). """
    return get_extreme_stamp(nodes, lambda a, b: a < b)


def get_newest(nodes):
    """ See get_extreme_stamp(). """
    return get_extreme_stamp(nodes, lambda a, b: a > b)


def load_deps(f):
    """ Loads a list of filenames from file with absolute name f. """
    fp = open(f, 'r')
    deps = []
    while 1:
        l = fp.readline()
        if l:
            deps.append(l.strip())
        else:
            break
    fp.close()
    return deps



class BuildGroup(object):
    " Class to organise the build, arranging tasks in order of dependency. "
    def __init__(self, ctx, targets):
        """ ctx is the context containing info for the build. targets is a
        list of targets. """
        self.ctx = ctx

        # cond is used to allow builders to wait until a new task is ready
        # and to access the queue in a thread-safe way
        self.cond = threading.Condition(ctx.lock)

        # ready_queue isn't really ordered, jobs are just appended as they
        # become unblocked. This is nice and simple.
        # Additionally all jobs are added to ready_queue before checking
        # up-to-dateness; this is checked just before they would run and
        # up-to-date jobs are skipped and handled as if they were just run.
        self.ready_queue = []

        # quick way to find whether a target is due to be, or has been, built
        self.queued = {}

        # Jobs are added here until unblocked, then moved to ready_queue
        self.pending_jobs = []

        self.verbose = 0

        # Add jobs
        for tgt in targets:
            self.add_target(tgt)

        # Start builders
        self.cancelled = False
        self.threads = []
        n = int(self.ctx.env.get('PARALLEL', 1))
        if n < 1:
            n = 1
        mprint("Starting %d build thread(s)" % n)
        for n in range(n):
            t = Builder(self)
            self.threads.append(t)
            t.start()

        # Wait for threads; doesn't matter what order they finish in
        for t in self.threads:
            #dprint("Main loop waiting for %s to finish" % t.describe())
            t.join()


    def add_target(self, target):
        if not target in self.queued:
            self.add_job(self.ctx.explicit_rules[target])


    def add_job(self, job):
        if job in self.pending_jobs:
            return
        job.calculating = True
        if job.verbose:
            self.verbose += 1
        self.cond.acquire()
        try:
            self.pending_jobs.append(job)
        finally:
            self.cond.release()
        for t in job.targets:
            self.queued[self.ctx.subst(t)] = job
        self.satisfy_deps(job)
        if job.verbose:
            dprint("  " * self.verbose + \
                    "%s is blocked by %s" % (job, job.blocked_by))
            self.verbose -= 1
        job.calculating = False
        if not len(job.blocked_by):
            self.do_while_locked(self.make_job_ready, job)


    def do_while_locked(self, func, *args, **kwargs):
        """ Lock cond and run func(*args, **kwargs), handling errors in a
        thread-safe way. Returns result of func. """
        self.cond.acquire()
        try:
            result = func(*args, **kwargs)
        except:
            self.cancel_all_jobs()
            self.cond.release()
            raise
        self.cond.release()
        return result


    def cancel_all_jobs(self):
        dprint("Cancelling all jobs")
        # Cond.notify_all() sometimes freezes all threads instead of
        # awakening them, so only choice is to exit
        self.cond.acquire()
        try:
            if not self.cancelled:
                self.cancelled = True
                self.ready_queue = []
                self.pending_jobs = []
                self.cond.notify_all()
        finally:
            self.cond.release()
        dprint("Leaving cancel_all_jobs")


    def make_job_ready(self, job):
        " Moves a job from pending_jobs to ready_queue. "
        self.cond.acquire()
        try:
            # We may still get here after all jobs have been cancelled due
            # to an error
            try:
                self.pending_jobs.remove(job)
            except ValueError:
                pass
            else:
                self.ready_queue.append(job)
            self.cond.notify()
        finally:
            self.cond.release()


    def satisfy_deps(self, job):
        if job.wdeps:
            deps = job.wdeps
        else:
            deps = []
        sdeps = job.list_static_deps()
        if sdeps:
            deps += sdeps
        if self.verbose:
            vdp = "  " * (self.verbose - 1)
            dprint(vdp + "%s depends on %s" % (job, deps))
        if not len(deps):
            return
        for dep in deps:
            dep = self.ctx.subst(dep)
            if job.dir and not os.path.isabs(dep):
                absdep = self.ctx.subst(opj(job.dir, dep))
            else:
                absdep = None
            try:
                # Has a rule to build this dep already been queued?
                rule = self.queued.get(dep)
                if not rule and absdep:
                    rule = self.queued.get(absdep)
                if rule:
                    if rule.calculating:
                        raise MaitchRecursionError("%s and %s have circular "
                                "dependencies" % (rule, dep))
                    self.mark_blocking(job, rule)
                    if self.verbose:
                        dprint(vdp + "  Making already queued %s block %s" % \
                                (rule, job))
                    continue

                # Is there an explicit rule for it?
                rule = self.ctx.explicit_rules.get(dep)
                if not rule and absdep:
                    rule = self.ctx.explicit_rules.get(absdep)
                if rule:
                    self.mark_blocking(job, rule)
                    if self.verbose:
                        dprint(vdp + \
                                "  Making unqueued %s block %s and adding" % \
                                (rule, job))
                    self.add_job(rule)
                    continue

                # Does file already exist?
                self.ctx.find_source(dep, job.dir, job.where)
                if self.verbose:
                    dprint(vdp +  "  %s already exists" % dep)
            except:
                mprint("Error trying to satisfy dep '%s' of '%s'" % (dep, job),
                        file = sys.stderr)
                raise


    def mark_blocking(self, blocked, blocker):
        self.cond.acquire()
        try:
            if blocked.verbose:
                blocker.verbose = True
            if not blocked in blocker.blocking:
                blocker.blocking.append(blocked)
            if not blocker in blocked.blocked_by:
                blocked.blocked_by.append(blocker)
        finally:
            self.cond.release()


    def job_done(self, job):
        if job.verbose:
            dprint("%s complete, unblocking %s" % (job, job.blocking))
        for j in job.blocking:
            self.do_while_locked(self.unblock_job, j, job)
        if not len(self.ready_queue) and not len(self.pending_jobs):
            self.cond.acquire()
            try:
                self.cond.notify_all()
            finally:
                self.cond.release()


    def unblock_job(self, blocked, blocker):
        """ 'blocked' is no longer blocked by 'blocker'. Call while locked.
        blocker is not altered, but if blocked has no remaining blockers it's
        moved to ready_queue. """
        try:
            blocked.blocked_by.remove(blocker)
        except ValueError:
            raise MaitchError(
                    "%s was supposed to be blocked by %s but wasn't" %
                    (blocked, blocker))
        if not len(blocked.blocked_by):
            self.make_job_ready(blocked)



_thread_index = 0

class Builder(threading.Thread):
    """ A Builder starts a new thread which waits for jobs to be added to
    BuildGroup's ready_queue, pops one at a time and runs it. """

    def __init__(self, build_group):
        global builder_index
        build_group.cond.acquire()
        try:
            global _thread_index
            self.index = _thread_index
            _thread_index += 1
        finally:
            build_group.cond.release()
        self.bg = build_group
        threading.Thread.__init__(self)


    def describe(self):
        return "Builder Thread %d" % self.index


    def run(self):
        finished = False
        dprint("Starting %s" % self.describe())
        try:
            while not finished:
                job = None
                #dprint("%s acquiring cond" % self.describe())
                self.bg.cond.acquire()
                try:
                    if not len(self.bg.ready_queue):
                        if len(self.bg.pending_jobs):
                            dprint("%s waiting for jobs" % self.describe())
                            self.bg.cond.wait()
                            dprint("%s awoken" % self.describe())
                    # Check both queues again, because they could have both
                    # changed while we were waiting
                    if not len(self.bg.ready_queue) and \
                            not len(self.bg.pending_jobs):
                        # No jobs left, we're done
                        dprint("%s finished" % self.describe())
                        finished = True
                    elif len(self.bg.ready_queue):
                        job = self.bg.ready_queue.pop()
                finally:
                    self.bg.cond.release()
                    #dprint("%s released cond" % self.describe())
                if job:
                    dprint("%s running job %s" % (self.describe(), to_str(job)))
                    job.run()
                    dprint("%s completed job %s" % (self.describe(),
                        to_str(job)))
                    self.bg.job_done(job)
                    dprint("%s marked job %s done" % \
                            (self.describe(), to_str(job)))
        except:
            dprint("Exception in %s" % self.describe())
            report_exception()
            self.bg.cancel_all_jobs()
        dprint("%s finished" % self.describe())