baker

#!/usr/bin/python

# baker: Automatically compile C libraries and programs
# Copyright (C) 2015 Jim Belton
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU 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 General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

"""baker - build C libraries and programs without a makefile

Usage: baker [-cnstv]

Options:
    -c --clean     Remove all built artifacts
    -n --noaction  Tell what would be done without actually doing it
    -s --strict    Fail on warnings
    -t --test      Run any test programs found
    -v --verbose   Tell what is being done
"""

import errno
import os
import re
import resource
import shutil
import signal
import subprocess
import sys

bakerDir = os.path.dirname(os.path.abspath(os.path.realpath(__file__)))
sys.path.append(os.path.join(bakerDir, "lib"))
from properties import Properties
from directory  import Directory, findFileInDirectories
from docopt     import docopt
from options    import error, fatal, getOption, setOptions, takeAction, warn
from OrderedSet import OrderedSet

setOptions(docopt(__doc__, version='1.0'))
setOptions({"warning": True})

startDirPath   = os.path.abspath(".")
symbolToFiles  = {}

symbolPat      = re.compile(r'[\da-f]+\s+\w\s+(\w+)$')
testPat        = re.compile(r'test')
warningPat     = re.compile(r'\bwarning:')

defaultProperties = {
    "ccFlags": {"-g": True, "-O" : "3", "-W": True, "-Waggregate-return": True, "-Wall": True, "-Wcast-align": True,
                "-Wcast-qual": True, "-Wcomment": True, "-Wimplicit": True, "-Wmissing-declarations": True,
                "-Wmissing-prototypes": True, "-Wnested-externs": True, "-Wpointer-arith": True, "-Wredundant-decls": True,
                "-Wshadow": True, "-Wstrict-prototypes": True, "-Wunused": True, "-Wwrite-strings": True}
}

# NOTE: If compiling for covereage, need to remove {-O, -O1, -O2, -O3} and -Wunitialized and and -O0
# See http://gcc.gnu.org/onlinedocs/gcc-3.0/gcc_8.html#SEC135: "...but if you want to prove that every single line in your program
# was executed, you should not compile with optimization at the same time."

def removeTargets(dirPath, dirProperties, files):
    """
    Remove all target directoriess found in dirPath and any of its subdirectories
    """
    for entry in files:
        if entry.endswith(".c"):
            if os.path.isdir("target") and takeAction("rm -rf " + dirPath + "/target"):
                shutil.rmtree("target")

            break

genxfaceScript = os.path.join(bakerDir, "genxface.pl")
protoPat       = re.compile(r'(.+)-proto.h$')

def generateDirHeaders(prefix, dirPath, dirName):
    if prefix == dirName:
        if takeAction(genxfaceScript + " -d " + dirPath):
            subprocess.check_output([genxfaceScript, "-d", dirPath])

        return True

    if os.path.isfile(os.path.join(dirPath, prefix + ".c")):
        if takeAction("'" + genxfaceScript + " " + dirPath + "'"):
            subprocess.check_output([genxfaceScript, dirPath])

        return True

    warn("Failed to generate " + prefix + "-proto.h for path " + dirPath + " directory " + dirName)
    return False

def regenerateHeaders(dirPath, dirProperties, files):
    dirName = os.path.basename(dirPath)

    for file in files:
        match = protoPat.match(file)

        if not match:
            continue

        if generateDirHeaders(match.group(1), dirPath, dirName):
            break

def findFile(dirPath, fileName, exclude=None):
    """
    Look for the fileName in all directories under the dirPath, excluding the exclude subdirectory if set or parent if ".."
    @return A list of directory objects or None if not found
    """

    (files, subDirs) = Directory.fromPath(dirPath).getContents()
    #print "Looking for %s under %s (subDirs=%s, files=%s)" % (fileName, dirPath, str(subDirs), str(files))

    # Look in all subdirectories
    for subDir in subDirs:
        if subDir == exclude:
            continue

        findFile(os.path.join(dirPath, subDir), fileName, exclude="..")

    # Return if found
    directories = findFileInDirectories(fileName)

    if directories:
        return directories

    # If we came from the parent, return none
    if exclude == "..":
        return None

    parent = os.path.dirname(dirPath)

    # Don't leave the user's directory; may want to allow this to be overridden
    if parent == "/home":
        return None

    return findFile(parent, fileName, exclude=os.path.basename(dirPath))

def sourceToTargetFileName(sourceFileName):
    return "target/" + sourceFileName[:-2] + ".o"

hFilePat       = re.compile(r'(?:^(.*\.[ch]):\d+:\d+: fatal error:)\s(\S+\.h): No such file')

def compileSources(dirPath, dirProperties, files):
    """
    Compile all source files found in entries
    """

    preferredIncludeDirExps = dirProperties.getProperty("preferredIncludeDirExps")
    ignoreFilesSet          = set(dirProperties.getProperty("ignoreFiles")) if dirProperties.getProperty("ignoreFiles") else None

    for entry in files:
        if entry.endswith(".c"):
            if ignoreFilesSet and entry in ignoreFilesSet:
                warn("Ignoring {} in {}".format(entry, dirPath));
                continue

            if not os.path.isdir("target"):
                os.mkdir("target")

            entryIncludeDirsProp = entry + ".includeDirectories"
            extraIncludeDirs     = set(dirProperties.getProperty(entryIncludeDirsProp, default=[]))
            lenExtraIncludeDirs  = len(extraIncludeDirs)

            while True:
                try:
                    ccCommand = ["cc", "-c", os.path.join(dirPath, entry), "-o", sourceToTargetFileName(entry)]
                    ccFlags = defaultProperties["ccFlags"].copy()
                    ccFlags.update(dirProperties.getProperty("ccFlags", {}))

                    for flag in ccFlags:
                        if ccFlags[flag] == True:
                            ccCommand.append(flag)
                        elif ccFlags[flag]:
                            ccCommand.append(flag + ccFlags[flag])

                    if getOption("strict"):
                        ccCommand.append("-Werror")

                    for incDirPath in list(extraIncludeDirs):
                        ccCommand.extend(["-I", incDirPath])

                    if takeAction(" ".join(ccCommand)):
                        output = subprocess.check_output(ccCommand, stderr=subprocess.STDOUT)

                        if warningPat.search(output):
                            sys.stderr.write(output)

                    # If the include path has grown, update the properties
                    #
                    if len(extraIncludeDirs) > lenExtraIncludeDirs:
                        dirProperties.setProperty(entryIncludeDirsProp, list(extraIncludeDirs))

                    break # Done!

                except subprocess.CalledProcessError as exception:
                    numberOfIncludeDirs = len(extraIncludeDirs)
                    interfacesGenerated = False

                    for line in exception.output.split('\n'):
                        match = hFilePat.search(line)

                        if not match:
                            continue

                        includer = match.group(1)
                        hFile    = match.group(2)

                        # If the missing include file looks like a generated prototype file, try to generate it
                        #
                        if includer and hFile.endswith("-proto.h"):
                            includerDir = os.path.dirname(includer) or dirPath
                            includerDir = includerDir if includerDir[0] == '/' else os.path.join(dirPath, includerDir)

                            if generateDirHeaders(hFile[:-8], includerDir, os.path.basename(os.path.abspath(includerDir))):
                                interfacesGenerated = True
                                break

                        hDirList = findFileInDirectories(hFile, closestToPath=dirPath)    # May be in the cache

                        if not hDirList:
                            hDirList = findFile(os.path.dirname(dirPath), hFile, exclude=os.path.basename(dirPath))

                        # If the file was found in more than one equally preferable place, check for doh that selects a directory
                        if hDirList and len(hDirList) > 1:
                            if preferredIncludeDirExps:
                                for hDir in hDirList:
                                    for exp in preferredIncludeDirExps:
                                        if re.match(exp, hDir.path):
                                            hDirList = [hDir]
                                            break

                                    if len(hDirList) == 1:
                                        break

                        # Still not found or multiple choices? Look for a .h.in file and a configure script (autoconf special case)
                        if not hDirList or len(hDirList) > 1:
                            hSourceDirs = findFileInDirectories(hFile + ".in", closestToPath=dirPath)

                            if not hSourceDirs:
                                hDirSources = findFile(dirPath, hFile  + ".in")

                            if hSourceDirs:
                                if len(hSourceDirs) > 1:
                                    fatal("Found %s.in found for missing C header file included by %s/%s in multiple directories: %s"
                                          % (hFile, dirPath, entry, [hDir.path for hDir in hSourceDirs]))

                                if not hSourceDirs[0].containsFile("configure"):
                                    fatal("Found %s.in for missing C header file included by %s/%s, but no configure script in %s"
                                          % (hFile, dirPath, entry, hSourceDirs[0].path))

                                currentDir = os.getcwd()
                                os.chdir(hSourceDirs[0].path)

                                try:
                                    output = subprocess.check_output(["./configure"], stderr=subprocess.STDOUT)
                                except subprocess.CalledProcessError as exception:
                                    sys.stderr.write(exception.output)
                                    fatal("Failed to run './configure' in %s" % (hSourceDirs[0].path))

                                os.chdir(currentDir)

                                if not hSourceDirs[0].containsFile(hFile):
                                    fatal("Running './configure' in %s failed to generate missing C header file %s included by %s/%s"
                                          % (hSourceDirs[0].path, hFile, dirPath, entry))

                                hDirList = hSourceDirs

                        if not hDirList:
                            sys.stderr.write(exception.output)
                            fatal("Failed to find C header file %s included by %s/%s" % (hFile, dirPath, entry))

                        if len(hDirList) > 1:
                            sys.stderr.write(exception.output)
                            fatal("Found C header file %s included by %s/%s exists in multiple directories: %s"
                                  % (hFile, dirPath, entry, [hDir.path for hDir in hDirList]))

                        extraIncludeDirs.add(hDirList[0].getRelpath())

                    # If interface files were generated or at least on additional directory was added, try again
                    if interfacesGenerated or len(extraIncludeDirs) > numberOfIncludeDirs:
                        continue

                    sys.stderr.write(exception.output)
                    fatal("Failed to compile C file with: %s" % (" ".join(ccCommand)))

def getSymbolsFromObjectFile(objectFileName):
    symbols = set()

    try:
        for line in subprocess.check_output(["nm", "-gp", "--defined-only", objectFileName], stderr=subprocess.STDOUT).split('\n'):
            match = symbolPat.match(line)

            if match:
                symbols.add(match.group(1))

        return symbols

    except subprocess.CalledProcessError as exception:
        sys.stderr.write(exception.output)
        fatal("Unable to get symbol names from %s (in directory %s)" % (objectFileName, os.getcwd()))

def dictOfListsBulkAdd(intoDict, keySet, value):
    for key in keySet:
        if key in intoDict:
            intoDict[key].append(value)
        else:
            intoDict[key] = [value]

def dictOfListsExtend(intoDict, fromDict):
    for key in fromDict:
        if key in intoDict:
            intoDict[key].extend(fromDict[key])
        else:
            intoDict[key] = fromDict[key]

undefSymbolPat = re.compile(r': undefined reference to [\'`](\w+)\'')

def archiveObjects(dirPath, dirProperties, files):
    """
    Archive all object files in dirPath if it does not contain programs
    """
    directory        = Directory.fromPath(dirPath)
    objectFiles      = []
    programs         = []
    dirSymbolToFiles = {}

    for entry in files:
        if entry.endswith(".c"):
            objectFile = sourceToTargetFileName(entry)
            symbols    = getSymbolsFromObjectFile(objectFile)

            if "main" in symbols:
                programs.append(entry[:-2])
            else:
                objectFiles.append(objectFile)
                dictOfListsBulkAdd(dirSymbolToFiles, symbols, objectFile)

    # If any new programs were found, update the Properties
    if len(programs) > len(dirProperties.getProperty("programs", [])):
        dirProperties.setProperty("programs", programs)

    archive = dirProperties.getProperty("archive")

    # If any progam was found and no explicit Properties telling baker to make an archive, return
    if len(programs) > 0 and not archive:
        directory.symbolToFiles = dirSymbolToFiles
        return

    if len(dirSymbolToFiles) == 0:
        return

    if not archive:
        archive = "target/%s.a" % os.path.basename(dirPath)
        dirProperties.setProperty("archive", archive)

    if os.path.isfile(archive):
        os.remove(archive)

    try:
        arCommand = ["ar", "rc", archive]
        arCommand.extend(objectFiles)

        if takeAction(" ".join(arCommand)):
            subprocess.check_output(arCommand)
    except subprocess.CalledProcessError as exception:
        sys.stderr.write(exception.output)
        fatal("Unable to create library %s from %s" % (objectFileName))

    for symbol in dirSymbolToFiles:
        if len(dirSymbolToFiles[symbol]) == 1:
            dirSymbolToFiles[symbol] = [os.path.join(dirPath, archive)]

    dictOfListsExtend(symbolToFiles, dirSymbolToFiles)

def findSymbol(dirPath, symbol, exclude=None):
    """
    Look for the symbols in all directories under the dirPath, excluding the exclude subdirectory if set or parent if ".."
    """

    directory = Directory.fromPath(dirPath)

    try:
        if directory.symbolsIndexed:
            return None
    except AttributeError:
        pass

    directory.symbolsIndexed = True    # Done early to prevent a recursion loop on /usr/lib

    try:
        (files, subDirs) = directory.getContents()
    except OSError as exception:
        if exception.errno == errno.EACCES:
            sys.stderr.write("warning: Skipped directory {}: permission denied\n".format(dirPath))
            return None

        raise exception

    #sys.stderr.write("Looking for %s under %s (subDirs=%s)\n" % (symbol, dirPath, str(subDirs)))

    # Look in all subdirectories

    for subDir in subDirs:
        if subDir == exclude:
            continue

        findSymbol(os.path.join(dirPath, subDir), symbol, exclude="..")

    # If there are any libraries in the current directory, map them

    for file in files:
        if file.endswith(".a"):
            filePath = os.path.join(dirPath, file)
            symbols  = getSymbolsFromObjectFile(filePath)
            dictOfListsBulkAdd(symbolToFiles, symbols, filePath)

    # Return if found

    foundFiles = symbolToFiles.get(symbol)

    if foundFiles:
        return foundFiles

    # If we didn't come from the parent directory
    if exclude != "..":
        parent = os.path.dirname(dirPath)

        # If we haven't reached the user's home directory, continue down to the root.
        if parent != "/home":
            return findSymbol(parent, symbol, exclude=os.path.basename(dirPath))

    # Last chance: look in "/usr/lib" if we haven't looked there yet
    return findSymbol("/usr/lib", symbol, exclude="..")

def enableCoreDumps():
    resource.setrlimit(resource.RLIMIT_CORE, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

def linkPrograms(dirPath, dirProperties, files):
    """
    Link all programs in dirPath and any of its subdirectories
    """

    preferredLibraries  = dirProperties.getProperty("preferredLibraries")
    preferredLibrarySet = set(preferredLibraries) if preferredLibraries else None
    programs            = dirProperties.getProperty("programs", [])
    systemLibraryFlags  = dirProperties.getProperty("systemLibraryFlags")
    directory           = Directory.fromPath(dirPath)
    #print "Linking programs in directory " + dirPath + " files " + str(files) + " subDirs " + str(subDirs)

    # Try to build any programs in the directory
    for program in programs:
        #print "Linking program: " + program
        programObjectFilesProp = program + ".objectFiles"
        extraObjectFiles       = OrderedSet(dirProperties.getProperty(programObjectFilesProp, []))
        lenExtraObjectFiles    = len(extraObjectFiles)
        movedObjectFiles       = set()

        while True:
            try:
                ldCommand = ["cc", sourceToTargetFileName(program + ".c"), "-o", "target/" + program]

                if systemLibraryFlags:
                    ldCommand.append(systemLibraryFlags)

                for objectFile in extraObjectFiles.toList():
                    ldCommand.append(objectFile)

                if takeAction(" ".join(ldCommand)):
                    subprocess.check_output(ldCommand, stderr=subprocess.STDOUT)

                # If the number of object files has grown or the order was changed, update the Properties
                #
                if len(extraObjectFiles) > lenExtraObjectFiles or len(movedObjectFiles) > 0:
                    dirProperties.setProperty(programObjectFilesProp, extraObjectFiles.toList())

                break # Done!

            except subprocess.CalledProcessError as exception:
                numberOfObjectFiles = len(extraObjectFiles)
                undefinedSymbols    = []
                newOrMovedFiles     = set()

                for line in exception.output.split('\n'):
                    match = undefSymbolPat.search(line)

                    if not match:
                        continue

                    undefinedSymbols.append(match.group(1))

                for symbol in undefinedSymbols:
                    # First, look in any object files in the same directory
                    oFileList = directory.symbolToFiles.get(symbol)

                    # May be in the cache
                    if not oFileList:
                        oFileList = symbolToFiles.get(symbol)

                    # Look in higher level directories for archives
                    if not oFileList:
                        oFileList = findSymbol(os.path.dirname(startDirPath), symbol, exclude=os.path.basename(startDirPath))

                    if not oFileList:
                        sys.stderr.write(exception.output)
                        fatal("Failed to find symbol %s needed by %s in %s" % (symbol, program, dirPath))

                    if len(oFileList) > 1:
                        if preferredLibrarySet:
                            for oFile in oFileList:
                                if os.path.basename(oFile) in preferredLibrarySet:
                                    oFileList = [oFile]
                                    break

                        if len(oFileList) > 1:
                            sys.stderr.write(exception.output)
                            fatal("Found symbol %s needed by %s in %s in multiple files: %s"
                                  % (symbol, program, dirPath, oFileList))

                    oFile = os.path.relpath(oFileList[0])

                    # If the symbol is in an object file thats already in the list, might need to move it later in the link order
                    #
                    if extraObjectFiles.has_key(oFile):
                        if oFile not in newOrMovedFiles:
                            if oFile in movedObjectFiles:
                                sys.stderr.write(" ".join(ldCommand) + "\n")
                                sys.stderr.write(exception.output)
                                fatal("Linker failed to find symbol %s needed by %s even after moving %s to end of list"
                                    % (symbol, program,  oFile))

                            newoOrMovedFiles.add(oFile)
                            extraObjectFiles.remove(oFile)
                            movedObjectFiles.add(oFile)

                    else:
                        newOrMovedFiles.add(oFile)
                        movedObjectFiles.clear()    # When a file is added, allow any others to be moved past it

                    extraObjectFiles.add(oFile)

                # If no additional object files and no object files were moved, fail
                if len(extraObjectFiles) <= numberOfObjectFiles and len(movedObjectFiles) == 0:
                    sys.stderr.write(exception.output)
                    fatal("Failed to link C program with: %s" % (" ".join(ldCommand)))

        if getOption("test") and testPat.match(program) and takeAction("run " + program):
            try:
                output = subprocess.check_output(["target/" + program], stderr=subprocess.STDOUT, preexec_fn=enableCoreDumps)

                if getOption("verbose"):
                    sys.stdout.write(output)
            except subprocess.CalledProcessError as exception:
                sys.stderr.write(exception.output)

                if exception.returncode == -signal.SIGSEGV:
                    fatal("Test program %s was killed with a segmentation fault" % program)

                error("Test failure in program " + program)

def visitDirTree(dirPath, visit):
    """
    Visits dirPath and all of its subdirectories in depth first postfix order (leaves first)
    @param visit Function to call on each directory, which is passed the directory path, the directory properties, and the files
    """
    dirProperties           = Properties.fromFilePath(os.path.join(dirPath, "baker.doh"))
    oldPath                 = os.getcwd()
    os.chdir(dirPath)
    (files, subDirs) = Directory.fromPath(dirPath).getContents()

    for subDir in subDirs:
        visitDirTree(os.path.join(dirPath, subDir), visit)

    visit(dirPath, dirProperties, files)
    dirProperties.flushIfDirty()
    os.chdir(oldPath)

if getOption("clean"):
    visitDirTree(startDirPath, removeTargets)
    sys.exit(0)

# Compile any source files found in and under the current directory, then link any programs and archive any directories with none

print "-" * 79
Directory.setIndexExp(r'.+\.h(?:\.in)?$')        # Index .h files, as well as .h.in (autoconf .h source files special case)
visitDirTree(startDirPath, regenerateHeaders)
visitDirTree(startDirPath, compileSources)
visitDirTree(startDirPath, archiveObjects)
visitDirTree(startDirPath, linkPrograms)