Initial import.

[mirror_edk2.git] / Tools / Source / Cpptasks / net / sf / antcontrib / cpptasks / DependencyTable.java

/*\r
 * \r
 * Copyright 2002-2004 The Ant-Contrib project\r
 *\r
 *  Licensed under the Apache License, Version 2.0 (the "License");\r
 *  you may not use this file except in compliance with the License.\r
 *  You may obtain a copy of the License at\r
 *\r
 *      http://www.apache.org/licenses/LICENSE-2.0\r
 *\r
 *  Unless required by applicable law or agreed to in writing, software\r
 *  distributed under the License is distributed on an "AS IS" BASIS,\r
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
 *  See the License for the specific language governing permissions and\r
 *  limitations under the License.\r
 */\r
package net.sf.antcontrib.cpptasks;\r
import java.io.BufferedWriter;\r
import java.io.File;\r
import java.io.FileOutputStream;\r
import java.io.IOException;\r
import java.io.OutputStreamWriter;\r
import java.io.UnsupportedEncodingException;\r
import java.util.Enumeration;\r
import java.util.Hashtable;\r
import java.util.Vector;\r
import javax.xml.parsers.ParserConfigurationException;\r
import javax.xml.parsers.SAXParser;\r
import javax.xml.parsers.SAXParserFactory;\r
import net.sf.antcontrib.cpptasks.compiler.CompilerConfiguration;\r
import org.apache.tools.ant.BuildException;\r
import org.apache.tools.ant.Project;\r
import org.xml.sax.Attributes;\r
import org.xml.sax.SAXException;\r
import org.xml.sax.helpers.DefaultHandler;\r
/**\r
 * @author Curt Arnold\r
 */\r
public final class DependencyTable {\r
    /**\r
     * This class handles populates the TargetHistory hashtable in response to\r
     * SAX parse events\r
     */\r
    private class DependencyTableHandler extends DefaultHandler {\r
        private File baseDir;\r
        private final DependencyTable dependencyTable;\r
        private String includePath;\r
        private Vector includes;\r
        private String source;\r
        private long sourceLastModified;\r
        private Vector sysIncludes;\r
        /**\r
         * Constructor\r
         * \r
         * @param history\r
         *            hashtable of TargetHistory keyed by output name\r
         * @param outputFiles\r
         *            existing files in output directory\r
         */\r
        private DependencyTableHandler(DependencyTable dependencyTable,\r
                File baseDir) {\r
            this.dependencyTable = dependencyTable;\r
            this.baseDir = baseDir;\r
            includes = new Vector();\r
            sysIncludes = new Vector();\r
            source = null;\r
        }\r
        public void endElement(String namespaceURI, String localName,\r
                String qName) throws SAXException {\r
            //\r
            //   if </source> then\r
            //       create Dependency object and add to hashtable\r
            //           if corresponding source file exists and\r
            //           has the same timestamp\r
            //\r
            if (qName.equals("source")) {\r
                if (source != null && includePath != null) {\r
                    File existingFile = new File(baseDir, source);\r
                    //\r
                    //   if the file exists and the time stamp is right\r
                    //       preserve the dependency info\r
                    if (existingFile.exists()) {\r
                        //\r
                        //   would have expected exact matches\r
                        //       but was seeing some unexpected difference by\r
                        //       a few tens of milliseconds, as long\r
                        //       as the times are within a second\r
                        long existingLastModified = existingFile.lastModified();\r
                        long diff = existingLastModified - sourceLastModified;\r
                        if (diff >= -500 && diff <= 500) {\r
                            DependencyInfo dependInfo = new DependencyInfo(\r
                                    includePath, source, sourceLastModified,\r
                                    includes, sysIncludes);\r
                            dependencyTable.putDependencyInfo(source,\r
                                    dependInfo);\r
                        }\r
                    }\r
                    source = null;\r
                    includes.setSize(0);\r
                }\r
            } else {\r
                //\r
                //    this causes any <source> elements outside the\r
                //       scope of an <includePath> to be discarded\r
                //\r
                if (qName.equals("includePath")) {\r
                    includePath = null;\r
                }\r
            }\r
        }\r
        /**\r
         * startElement handler\r
         */\r
        public void startElement(String namespaceURI, String localName,\r
                String qName, Attributes atts) throws SAXException {\r
            //\r
            //   if includes, then add relative file name to vector\r
            //\r
            if (qName.equals("include")) {\r
                includes.addElement(atts.getValue("file"));\r
            } else {\r
                if (qName.equals("sysinclude")) {\r
                    sysIncludes.addElement(atts.getValue("file"));\r
                } else {\r
                    //\r
                    //    if source then\r
                    //        capture source file name,\r
                    //        modification time and reset includes vector\r
                    //\r
                    if (qName.equals("source")) {\r
                        source = atts.getValue("file");\r
                        sourceLastModified = Long.parseLong(atts\r
                                .getValue("lastModified"), 16);\r
                        includes.setSize(0);\r
                        sysIncludes.setSize(0);\r
                    } else {\r
                        if (qName.equals("includePath")) {\r
                            includePath = atts.getValue("signature");\r
                        }\r
                    }\r
                }\r
            }\r
        }\r
    }\r
    public abstract class DependencyVisitor {\r
        /**\r
         * Previews all the children of this source file.\r
         * \r
         * May be called multiple times as DependencyInfo's for children are\r
         * filled in.\r
         * \r
         * @return true to continue towards recursion into included files\r
         */\r
        public abstract boolean preview(DependencyInfo parent,\r
                DependencyInfo[] children);\r
        /**\r
         * Called if the dependency depth exhausted the stack.\r
         */\r
        public abstract void stackExhausted();\r
        /**\r
         * Visits the dependency info.\r
         * \r
         * @returns true to continue towards recursion into included files\r
         */\r
        public abstract boolean visit(DependencyInfo dependInfo);\r
    }\r
    public class TimestampChecker extends DependencyVisitor {\r
        private boolean noNeedToRebuild;\r
        private long outputLastModified;\r
        private boolean rebuildOnStackExhaustion;\r
        public TimestampChecker(final long outputLastModified,\r
                boolean rebuildOnStackExhaustion) {\r
            this.outputLastModified = outputLastModified;\r
            noNeedToRebuild = true;\r
            this.rebuildOnStackExhaustion = rebuildOnStackExhaustion;\r
        }\r
        public boolean getMustRebuild() {\r
            return !noNeedToRebuild;\r
        }\r
        public boolean preview(DependencyInfo parent, DependencyInfo[] children) {\r
            int withCompositeTimes = 0;\r
            long parentCompositeLastModified = parent.getSourceLastModified();\r
            for (int i = 0; i < children.length; i++) {\r
                if (children[i] != null) {\r
                    //\r
                    //  expedient way to determine if a child forces us to\r
                    // rebuild\r
                    //\r
                    visit(children[i]);\r
                    long childCompositeLastModified = children[i]\r
                            .getCompositeLastModified();\r
                    if (childCompositeLastModified != Long.MIN_VALUE) {\r
                        withCompositeTimes++;\r
                        if (childCompositeLastModified > parentCompositeLastModified) {\r
                            parentCompositeLastModified = childCompositeLastModified;\r
                        }\r
                    }\r
                }\r
            }\r
            if (withCompositeTimes == children.length) {\r
                parent.setCompositeLastModified(parentCompositeLastModified);\r
            }\r
            //\r
            //  may have been changed by an earlier call to visit()\r
            //\r
            return noNeedToRebuild;\r
        }\r
        public void stackExhausted() {\r
            if (rebuildOnStackExhaustion) {\r
                noNeedToRebuild = false;\r
            }\r
        }\r
        public boolean visit(DependencyInfo dependInfo) {\r
            if (noNeedToRebuild) {\r
                if (dependInfo.getSourceLastModified() > outputLastModified\r
                        || dependInfo.getCompositeLastModified() > outputLastModified) {\r
                    noNeedToRebuild = false;\r
                }\r
            }\r
            //\r
            //   only need to process the children if\r
            //      it has not yet been determined whether\r
            //      we need to rebuild and the composite modified time\r
            //         has not been determined for this file\r
            return noNeedToRebuild\r
                    && dependInfo.getCompositeLastModified() == Long.MIN_VALUE;\r
        }\r
    }\r
    private/* final */File baseDir;\r
    private String baseDirPath;\r
    /**\r
     * a hashtable of DependencyInfo[] keyed by output file name\r
     */\r
    private final Hashtable dependencies = new Hashtable();\r
    /** The file the cache was loaded from. */\r
    private/* final */File dependenciesFile;\r
    /** Flag indicating whether the cache should be written back to file. */\r
    private boolean dirty;\r
    /**\r
     * Creates a target history table from dependencies.xml in the prject\r
     * directory, if it exists. Otherwise, initializes the dependencies empty.\r
     * \r
     * @param task\r
     *            task used for logging history load errors\r
     * @param baseDir\r
     *            output directory for task\r
     */\r
    public DependencyTable(File baseDir) {\r
        if (baseDir == null) {\r
            throw new NullPointerException("baseDir");\r
        }\r
        this.baseDir = baseDir;\r
        try {\r
            baseDirPath = baseDir.getCanonicalPath();\r
        } catch (IOException ex) {\r
            baseDirPath = baseDir.toString();\r
        }\r
        dirty = false;\r
        //\r
        //   load any existing dependencies from file\r
        dependenciesFile = new File(baseDir, "dependencies.xml");\r
    }\r
    public void commit(CCTask task) {\r
        //\r
        //   if not dirty, no need to update file\r
        //\r
        if (dirty) {\r
            //\r
            //   walk through dependencies to get vector of include paths\r
            // identifiers\r
            //\r
            Vector includePaths = getIncludePaths();\r
            //\r
            //\r
            //   write dependency file\r
            //\r
            try {\r
                FileOutputStream outStream = new FileOutputStream(\r
                        dependenciesFile);\r
                OutputStreamWriter streamWriter;\r
                //\r
                //    Early VM's may not have UTF-8 support\r
                //       fallback to default code page which\r
                //           "should" be okay unless there are\r
                //            non ASCII file names\r
                String encodingName = "UTF-8";\r
                try {\r
                    streamWriter = new OutputStreamWriter(outStream, "UTF-8");\r
                } catch (UnsupportedEncodingException ex) {\r
                    streamWriter = new OutputStreamWriter(outStream);\r
                    encodingName = streamWriter.getEncoding();\r
                }\r
                BufferedWriter writer = new BufferedWriter(streamWriter);\r
                writer.write("<?xml version='1.0' encoding='");\r
                writer.write(encodingName);\r
                writer.write("'?>\n");\r
                writer.write("<dependencies>\n");\r
                StringBuffer buf = new StringBuffer();\r
                Enumeration includePathEnum = includePaths.elements();\r
                while (includePathEnum.hasMoreElements()) {\r
                    writeIncludePathDependencies((String) includePathEnum\r
                            .nextElement(), writer, buf);\r
                }\r
                writer.write("</dependencies>\n");\r
                writer.close();\r
                dirty = false;\r
            } catch (IOException ex) {\r
                task.log("Error writing " + dependenciesFile.toString() + ":"\r
                        + ex.toString());\r
            }\r
        }\r
    }\r
    /**\r
     * Returns an enumerator of DependencyInfo's\r
     */\r
    public Enumeration elements() {\r
        return dependencies.elements();\r
    }\r
    /**\r
     * This method returns a DependencyInfo for the specific source file and\r
     * include path identifier\r
     *  \r
     */\r
    public DependencyInfo getDependencyInfo(String sourceRelativeName,\r
            String includePathIdentifier) {\r
        DependencyInfo dependInfo = null;\r
        DependencyInfo[] dependInfos = (DependencyInfo[]) dependencies\r
                .get(sourceRelativeName);\r
        if (dependInfos != null) {\r
            for (int i = 0; i < dependInfos.length; i++) {\r
                dependInfo = dependInfos[i];\r
                if (dependInfo.getIncludePathIdentifier().equals(\r
                        includePathIdentifier)) {\r
                    return dependInfo;\r
                }\r
            }\r
        }\r
        return null;\r
    }\r
    private Vector getIncludePaths() {\r
        Vector includePaths = new Vector();\r
        DependencyInfo[] dependInfos;\r
        Enumeration dependenciesEnum = dependencies.elements();\r
        while (dependenciesEnum.hasMoreElements()) {\r
            dependInfos = (DependencyInfo[]) dependenciesEnum.nextElement();\r
            for (int i = 0; i < dependInfos.length; i++) {\r
                DependencyInfo dependInfo = dependInfos[i];\r
                boolean matchesExisting = false;\r
                final String dependIncludePath = dependInfo\r
                        .getIncludePathIdentifier();\r
                Enumeration includePathEnum = includePaths.elements();\r
                while (includePathEnum.hasMoreElements()) {\r
                    if (dependIncludePath.equals(includePathEnum.nextElement())) {\r
                        matchesExisting = true;\r
                        break;\r
                    }\r
                }\r
                if (!matchesExisting) {\r
                    includePaths.addElement(dependIncludePath);\r
                }\r
            }\r
        }\r
        return includePaths;\r
    }\r
    public void load() throws IOException, ParserConfigurationException,\r
            SAXException {\r
        dependencies.clear();\r
        if (dependenciesFile.exists()) {\r
            SAXParserFactory factory = SAXParserFactory.newInstance();\r
            factory.setValidating(false);\r
            SAXParser parser = factory.newSAXParser();\r
            parser.parse(dependenciesFile, new DependencyTableHandler(this,\r
                    baseDir));\r
            dirty = false;\r
        }\r
    }\r
    /**\r
     * Determines if the specified target needs to be rebuilt.\r
     * \r
     * This task may result in substantial IO as files are parsed to determine\r
     * their dependencies\r
     */\r
    public boolean needsRebuild(CCTask task, TargetInfo target,\r
            int dependencyDepth) {\r
        //    look at any files where the compositeLastModified\r
        //    is not known, but the includes are known\r
        //\r
        boolean mustRebuild = false;\r
        CompilerConfiguration compiler = (CompilerConfiguration) target\r
                .getConfiguration();\r
        String includePathIdentifier = compiler.getIncludePathIdentifier();\r
        File[] sources = target.getSources();\r
        DependencyInfo[] dependInfos = new DependencyInfo[sources.length];\r
        long outputLastModified = target.getOutput().lastModified();\r
        //\r
        //   try to solve problem using existing dependency info\r
        //      (not parsing any new files)\r
        //\r
        DependencyInfo[] stack = new DependencyInfo[50];\r
        boolean rebuildOnStackExhaustion = true;\r
        if (dependencyDepth >= 0) {\r
            if (dependencyDepth < 50) {\r
                stack = new DependencyInfo[dependencyDepth];\r
            }\r
            rebuildOnStackExhaustion = false;\r
        }\r
        TimestampChecker checker = new TimestampChecker(outputLastModified,\r
                rebuildOnStackExhaustion);\r
        for (int i = 0; i < sources.length && !mustRebuild; i++) {\r
            File source = sources[i];\r
            String relative = CUtil.getRelativePath(baseDirPath, source);\r
            DependencyInfo dependInfo = getDependencyInfo(relative,\r
                    includePathIdentifier);\r
            if (dependInfo == null) {\r
                task.log("Parsing " + relative, Project.MSG_VERBOSE);\r
                dependInfo = parseIncludes(task, compiler, source);\r
            }\r
            walkDependencies(task, dependInfo, compiler, stack, checker);\r
            mustRebuild = checker.getMustRebuild();\r
        }\r
        return mustRebuild;\r
    }\r
    public DependencyInfo parseIncludes(CCTask task,\r
            CompilerConfiguration compiler, File source) {\r
        DependencyInfo dependInfo = compiler.parseIncludes(task, baseDir,\r
                source);\r
        String relativeSource = CUtil.getRelativePath(baseDirPath, source);\r
        putDependencyInfo(relativeSource, dependInfo);\r
        return dependInfo;\r
    }\r
    private void putDependencyInfo(String key, DependencyInfo dependInfo) {\r
        //\r
        //   optimistic, add new value\r
        //\r
        DependencyInfo[] old = (DependencyInfo[]) dependencies.put(key,\r
                new DependencyInfo[]{dependInfo});\r
        dirty = true;\r
        //\r
        //   something was already there\r
        //\r
        if (old != null) {\r
            //\r
            //   see if the include path matches a previous entry\r
            //       if so replace it\r
            String includePathIdentifier = dependInfo\r
                    .getIncludePathIdentifier();\r
            for (int i = 0; i < old.length; i++) {\r
                DependencyInfo oldDepend = old[i];\r
                if (oldDepend.getIncludePathIdentifier().equals(\r
                        includePathIdentifier)) {\r
                    old[i] = dependInfo;\r
                    dependencies.put(key, old);\r
                    return;\r
                }\r
            }\r
            //\r
            //   no match prepend the new entry to the array\r
            //      of dependencies for the file\r
            DependencyInfo[] combined = new DependencyInfo[old.length + 1];\r
            combined[0] = dependInfo;\r
            for (int i = 0; i < old.length; i++) {\r
                combined[i + 1] = old[i];\r
            }\r
            dependencies.put(key, combined);\r
        }\r
        return;\r
    }\r
    public void walkDependencies(CCTask task, DependencyInfo dependInfo,\r
            CompilerConfiguration compiler, DependencyInfo[] stack,\r
            DependencyVisitor visitor) throws BuildException {\r
        //\r
        //   visit this node\r
        //       if visit returns true then\r
        //          visit the referenced include and sysInclude dependencies\r
        //\r
        if (visitor.visit(dependInfo)) {\r
            //\r
            //   find first null entry on stack\r
            //\r
            int stackPosition = -1;\r
            for (int i = 0; i < stack.length; i++) {\r
                if (stack[i] == null) {\r
                    stackPosition = i;\r
                    stack[i] = dependInfo;\r
                    break;\r
                } else {\r
                    //\r
                    //   if we have appeared early in the calling history\r
                    //      then we didn't exceed the criteria\r
                    if (stack[i] == dependInfo) {\r
                        return;\r
                    }\r
                }\r
            }\r
            if (stackPosition == -1) {\r
                visitor.stackExhausted();\r
                return;\r
            }\r
            //\r
            //   locate dependency infos\r
            //\r
            String[] includes = dependInfo.getIncludes();\r
            String includePathIdentifier = compiler.getIncludePathIdentifier();\r
            DependencyInfo[] includeInfos = new DependencyInfo[includes.length];\r
            for (int i = 0; i < includes.length; i++) {\r
                DependencyInfo includeInfo = getDependencyInfo(includes[i],\r
                        includePathIdentifier);\r
                includeInfos[i] = includeInfo;\r
            }\r
            //\r
            //   preview with only the already available dependency infos\r
            //\r
            if (visitor.preview(dependInfo, includeInfos)) {\r
                //\r
                //   now need to fill in the missing DependencyInfos\r
                //\r
                int missingCount = 0;\r
                for (int i = 0; i < includes.length; i++) {\r
                    if (includeInfos[i] == null) {\r
                        missingCount++;\r
                        task.log("Parsing " + includes[i], Project.MSG_VERBOSE);\r
                        // If the include is part of a UNC don't go building a\r
                        // relative file name.\r
                        File src = includes[i].startsWith("\\\\") ? new File(\r
                                includes[i]) : new File(baseDir, includes[i]);\r
                        DependencyInfo includeInfo = parseIncludes(task,\r
                                compiler, src);\r
                        includeInfos[i] = includeInfo;\r
                    }\r
                }\r
                //\r
                //   if it passes a review the second time\r
                //      then recurse into all the children\r
                if (missingCount == 0\r
                        || visitor.preview(dependInfo, includeInfos)) {\r
                    //\r
                    //   recurse into\r
                    //\r
                    for (int i = 0; i < includeInfos.length; i++) {\r
                        DependencyInfo includeInfo = includeInfos[i];\r
                        walkDependencies(task, includeInfo, compiler, stack,\r
                                visitor);\r
                    }\r
                }\r
            }\r
            stack[stackPosition] = null;\r
        }\r
    }\r
    private void writeDependencyInfo(BufferedWriter writer, StringBuffer buf,\r
            DependencyInfo dependInfo) throws IOException {\r
        String[] includes = dependInfo.getIncludes();\r
        String[] sysIncludes = dependInfo.getSysIncludes();\r
        //\r
        //   if the includes have not been evaluted then\r
        //       it is not worth our time saving it\r
        //       and trying to distiguish between files with\r
        //       no dependencies and those with undetermined dependencies\r
        buf.setLength(0);\r
        buf.append("      <source file=\"");\r
        buf.append(CUtil.xmlAttribEncode(dependInfo.getSource()));\r
        buf.append("\" lastModified=\"");\r
        buf.append(Long.toHexString(dependInfo.getSourceLastModified()));\r
        buf.append("\">\n");\r
        writer.write(buf.toString());\r
        for (int i = 0; i < includes.length; i++) {\r
            buf.setLength(0);\r
            buf.append("         <include file=\"");\r
            buf.append(CUtil.xmlAttribEncode(includes[i]));\r
            buf.append("\"/>\n");\r
            writer.write(buf.toString());\r
        }\r
        for (int i = 0; i < sysIncludes.length; i++) {\r
            buf.setLength(0);\r
            buf.append("         <sysinclude file=\"");\r
            buf.append(CUtil.xmlAttribEncode(sysIncludes[i]));\r
            buf.append("\"/>\n");\r
            writer.write(buf.toString());\r
        }\r
        writer.write("      </source>\n");\r
        return;\r
    }\r
    private void writeIncludePathDependencies(String includePathIdentifier,\r
            BufferedWriter writer, StringBuffer buf) throws IOException {\r
        //\r
        //  include path element\r
        //\r
        buf.setLength(0);\r
        buf.append("   <includePath signature=\"");\r
        buf.append(CUtil.xmlAttribEncode(includePathIdentifier));\r
        buf.append("\">\n");\r
        writer.write(buf.toString());\r
        Enumeration dependenciesEnum = dependencies.elements();\r
        while (dependenciesEnum.hasMoreElements()) {\r
            DependencyInfo[] dependInfos = (DependencyInfo[]) dependenciesEnum\r
                    .nextElement();\r
            for (int i = 0; i < dependInfos.length; i++) {\r
                DependencyInfo dependInfo = dependInfos[i];\r
                //\r
                //   if this is for the same include path\r
                //      then output the info\r
                if (dependInfo.getIncludePathIdentifier().equals(\r
                        includePathIdentifier)) {\r
                    writeDependencyInfo(writer, buf, dependInfo);\r
                }\r
            }\r
        }\r
        writer.write("   </includePath>\n");\r
    }\r
}\r