undertaker 1.6.1-1 / usr / bin / undertaker-checkpatch

#! /usr/bin/python

"""Check a specified patch for variability related defects in a Linux tree."""

# Copyright (C) 2014 Valentin Rothberg <valentinrothberg@gmail.com>
#
# 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/>.

import os
import sys

sys.path = [os.path.join(os.path.dirname(sys.path[0]), 'lib', 'python%d.%d' % \
               (sys.version_info[0], sys.version_info[1]), 'site-packages')] + sys.path

import vamos.tools as tools
import vamos.golem.kbuild as kbuild
import vamos.defect_analysis as defect_analysis
from vamos.block import Block
from vamos.model import RsfModel

import re
import glob
import logging
import whatthepatch
from optparse import OptionParser


# regex expressions
OPERATORS = r"&|\(|\)|\||\!"
FEATURE = r"\w*[A-Z0-9]{1}\w*"
CONFIG_DEF = r"^\s*(?:menu){,1}config\s+(" + FEATURE + r")\s*"
EXPR = r"(?:" + OPERATORS + r"|\s|" + FEATURE + r")+"
STMT = r"^\s*(?:if|select|depends\s+on)\s+" + EXPR
SOURCE_FEATURE = r"(?:\W|\b)+[D]{,1}CONFIG_(" + FEATURE + r")"

# regex objects
REGEX_FILE_KCONFIG = re.compile(r".*Kconfig[\.\w+\-]*$")
REGEX_FILE_SOURCE = re.compile(r".*\.[cSh]$")
REGEX_FEATURE = re.compile(r"(" + FEATURE + r")")
REGEX_KCONFIG_DEF = re.compile(CONFIG_DEF)
REGEX_KCONFIG_EXPR = re.compile(EXPR)
REGEX_KCONFIG_STMT = re.compile(STMT)
REGEX_FILTER_FEATURES = re.compile(r"[A-Za-z0-9]$")
REGEX_SOURCE_FEATURE = re.compile(SOURCE_FEATURE)


def parse_options():
    """The user interface of this module."""
    parser = OptionParser(usage="undertaker-check-patch file [options]\n\n"
            "This tool needs to run in a Linux tree. Specify a patch file\n"
            "to check if any defects are introduced, fixed, changed, or if\n"
            "they remained present (unchanged).")

    parser.add_option('-a', '--arch', dest='arch', action='store', default="",
            help="Generate models for only this architecture.")

    parser.add_option('-m', '--models', dest='models', action='store',
            default="", help="Consider only these models for analysis.")

    parser.add_option('-c', '--check', dest='check', action='store_true',
            default=False, help="Try to find defect causes and effects." +
            "If no architecture is specified, the model defaults" +
            " to the x86 architecture.")

    parser.add_option('-u', '--mus', dest='mus', action='store_true',
            default=False, help="Generate minimally unsatisfiable" +
            "subformulas (MUS) for dead Kconfig defects.")

    parser.add_option('-v', '--verbose', dest='verbose', action='count',
            help="Increase verbosity (specify multiple times for more)")

    (opts, args) = parser.parse_args()
    tools.setup_logging(opts.verbose)

    if not args or not os.path.exists(args[0]):
        sys.exit("Please specify a valid patch file.")

    if opts.models and not os.path.exists(opts.models):
        sys.exit("The specified models do not exist.")

    if not apply_patch(args[0]):
        sys.exit("The specified patch cannot be applied.")
    else:
        apply_patch(args[0], "-R")

    return (opts, args)


def main():
    """Main function of this module."""
    #pylint: disable=R0912
    #pylint: disable=R0914
    #pylint: disable=R0915
    (opts, args) = parse_options()
    try:
        logging.info("Detected Linux version " + kbuild.get_linux_version())
    except kbuild.NotALinuxTree:
        sys.exit("Cannot detect Linux version.")

    patchfile = args[0]
    model_path = opts.models.rstrip('/')
    blocks_a = {}
    blocks_b = {}
    kconfig_change = False
    (worklist_a, worklist_b, removals, additions) = parse_patch(patchfile)

    for item in list(worklist_a):
        if REGEX_FILE_KCONFIG.match(item):
            kconfig_change = True
        if not REGEX_FILE_SOURCE.match(item) or not os.path.exists(item):
            worklist_a.remove(item)

    for item in list(worklist_b):
        if REGEX_FILE_KCONFIG.match(item):
            kconfig_change = True
        if not REGEX_FILE_SOURCE.match(item):
            worklist_b.remove(item)

    if not opts.models:
        # if no model is specified, we need to generate new ones
        model_path = generate_models(arch=opts.arch)
    elif opts.arch and ".model" not in opts.models:
        # if arch-specific model is not present, generate it
        if not os.path.exists("%s/%s.model" % (model_path, opts.arch)):
            logging.info("Model for specified architecture is not present")
            model_path = generate_models(arch=opts.arch)

    # detect defects before applying the patch
    blocks_a = defect_analysis.batch_analysis(worklist_a, model_path, "")

    # apply patch and update block ranges
    apply_patch(patchfile)
    Block.parse_patchfile(patchfile, blocks_a)

    # for any Kconfig change we need to generate new models
    if kconfig_change:
        model_path = generate_models(arch=opts.arch)

    # detect defects after applying the patch
    flags = ""
    if opts.mus:
        logging.info("Generating MUS reports")
        flags = "-u"
    blocks_b = defect_analysis.batch_analysis(worklist_b, model_path, flags)

    # compare blocks before and after applying the patch to detect if a defect
    # is a) introduced, b) fixed, c) changed or d) remained unchanged
    print "Reporting defects:"
    defects = {}
    is_defect = False
    for srcfile in set(worklist_a + worklist_b):
        list_a = blocks_a.get(srcfile, [])
        list_b = blocks_b.get(srcfile, [])
        defects[srcfile] = defect_analysis.compare_and_report(list_a, list_b)
        if defects[srcfile]:
            is_defect = True

    # load models for later checks
    models = []
    mainmodel = None
    if kconfig_change or opts.check:
        models, mainmodel = load_models(model_path, opts.arch)

    # check referential integrity of the patch
    is_defect = check_referential_integrity(removals, additions, models)

    # if no defect is detected, we can stop here
    if not is_defect:
        apply_patch(patchfile, "-R")
        sys.exit(0)

    if opts.check:
        print "Analyzing defects:"
        for srcfile in defects:
            for block in defects[srcfile]:
                if "missing" in block.defect:
                    defect_analysis.check_missing_defect(block, mainmodel)
                elif "kconfig" in block.defect:
                    defect_analysis.check_kconfig_defect(block, mainmodel)
                elif "code" in block.defect:
                    defect_analysis.check_code_defect(block)

    if opts.mus:
        print "MUS reports (only for dead blocks):"
        for srcfile in defects:
            for block in defects[srcfile]:
                if block.mus:
                    print block.mus

    # remove generated models and revert patch
    apply_patch(patchfile, "-R")


def apply_patch(patchfile, flags=""):
    """Apply @patchfile and return True if it could is applied successfully."""
    patch = "patch -p1 -i %s " % patchfile
    (_, err) = tools.execute(patch + flags)
    return err == 0


def generate_models(arch):
    """Generate models and return the absolute path to the model directory.
    In case the model generation fails, then exit with an error message."""
    try:
        return tools.generate_models(arch=arch)
    except (RuntimeError, OSError) as err:
        sys.exit("Cannot generate models:\n%s" % err)


def load_models(model_path, arch):
    """Load and return a list of models and a main model in the given
    models directory. In case an architecture is specified, only this model
    will be loaded. Otherwise, the main model tries to default to x86."""
    models = []
    mainmodel = None

    if model_path.endswith(".model"):
        # single file
        mainmodel = RsfModel(model_path, readrsf=False)
        return [mainmodel], mainmodel

    # model directory
    if not model_path.endswith("/"):
        model_path += "/"

    # get all models in directory
    model_files = glob.glob(model_path + "*.model")

    if arch:
        # load only the main model
        for model in model_files:
            if arch in model:
                mainmodel = RsfModel(model, readrsf=False)
                return [mainmodel], mainmodel

    # default to x86 if no arch is specified and load all models
    arch = "x86"
    for model in model_files:
        models.append(RsfModel(model, readrsf=False))
        if arch in model:
            mainmodel = models[-1]

    # if x86 model is absent, then take the first in the list
    if not mainmodel:
        mainmodel = models[0]
    return models, mainmodel


def search_item_tree(item):
    """Return a list of files referencing @item."""
    item += "[^_a-zA-Z0-9]"  # avoid substring matches (e.g., for CONFIG_X86*)
    (files, _) = tools.execute("git grep -n '%s'" % item)
    # if there is no reference we get [""]
    if files[0] == "":
        return []
    return files


def get_kconfig_definition(line):
    """Return defined Kconfig item in @line or None."""
    definition = REGEX_KCONFIG_DEF.findall(line)
    if definition:
        return definition[0]
    else:
        return None


def in_models(feature, models, arch=""):
    """Check if the feature is defined in at least one of the models or
    in the model of the specified architecture."""
    if arch:
        for model in models:
            if re.search(r"\/%s\.model$" % arch, model.path):
                return model.is_defined(feature)
    for model in models:
        if model.is_defined(feature):
            return True
    return False


def check_referential_integrity(removals, additions, models):
    """Check removed Kconfig features and all added lines for violations of the
    referential integrity."""
    if not removals and not additions:
        return False

    defect = False
    # removed features in Kconfig files
    for filepath in removals:
        for feature in removals[filepath]:
            if not in_models(feature, models):
                references = search_item_tree(feature)
                references.extend(search_item_tree(feature + '_MODULE'))
                if not references:
                    continue
                defect = True
                print "Feature %s is removed but still referenced in:" % \
                        feature
                for reference in set(references):
                    print reference

    # added references on Kconfig features in any file type
    for filepath in additions:
        arch = tools.get_architecture(filepath)
        for feature in additions[filepath]:
            if not in_models(feature, models, arch):
                defect = True
                print "%s: patch adds undefined reference on %s" % \
                        (filepath, feature)
    return defect


def parse_patch(patchfile):
    """Parse @patchfile and return related data."""
    #pylint: disable=R0912
    diffs = []
    worklist_a = []
    worklist_b = []
    removals = {}
    additions = {}

    # https://pypi.python.org/pypi/whatthepatch/0.0.2
    with open(patchfile) as stream:
        diffs = whatthepatch.parse_patch(stream.read())

    for diff in diffs:
        path = ""

        # extend the worklists
        if diff.header.old_path == diff.header.new_path:
            path = diff.header.old_path
            worklist_a.append(diff.header.old_path)
            worklist_b.append(diff.header.old_path)
        else:
            path = diff.header.new_path[2:]
            worklist_a.append(diff.header.old_path[2:])
            worklist_b.append(diff.header.new_path[2:])

        # parse Kconfig file
        if REGEX_FILE_KCONFIG.match(path):
            # change = [line# before, line# after, text]
            for change in diff.changes:
                # Removed features ({menu}config FOO)
                if change[0] and not change[1] and \
                        REGEX_KCONFIG_DEF.match(change[2]):
                    feature = get_kconfig_definition(change[2])
                    if feature:
                        removed = removals.get(path, set())
                        removed.add("CONFIG_" + feature)
                        removals[path] = removed

                # added statements (if, select, depends on)
                elif not change[0] and change[1] and \
                        REGEX_KCONFIG_STMT.match(change[2]):
                    stmts = additions.get(path, set())
                    for feature in REGEX_FEATURE.findall(change[2]):
                        stmts.add("CONFIG_" + feature)
                    additions[path] = stmts

        # parse any file that is no Kconfig, source or log file
        elif not REGEX_FILE_SOURCE.match(path) and \
                not "ChangeLog" in path and \
                not ".log" in path:
            # change = [line# before, line# after, text]
            for change in diff.changes:
                # any added line is interesting
                if not change[0] and change[1] and \
                        "CONFIG_" in change[2]:
                    refs = additions.get(path, set())
                    for feature in REGEX_SOURCE_FEATURE.findall(change[2]):
                        refs.add("CONFIG_" + feature)
                    additions[path] = refs

    return (worklist_a, worklist_b, removals, additions)


if __name__ == "__main__":
    main()