Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

301 lines (264 sloc) 14.202 kb
/* sbt -- Simple Build Tool
* Copyright 2010 Mark Harrah
*/
package sbt
package inc
import xsbt.api.{NameChanges, SameAPI, TopLevel}
import annotation.tailrec
import xsbti.api.{Compilation, Source}
import xsbti.compile.DependencyChanges
import java.io.File
object Incremental
{
// to be configurable
final val TransitiveStep = 2
final val RecompileAllFraction = 0.5
def compile(sources: Set[File], entry: String => Option[File], previous: Analysis, current: ReadStamps, forEntry: File => Option[Analysis], doCompile: (Set[File], DependencyChanges) => Analysis, log: Logger)(implicit equivS: Equiv[Stamp]): (Boolean, Analysis) =
{
val initialChanges = changedInitial(entry, sources, previous, current, forEntry)
val binaryChanges = new DependencyChanges {
val modifiedBinaries = initialChanges.binaryDeps.toArray
val modifiedClasses = initialChanges.external.modified.toArray
def isEmpty = modifiedBinaries.isEmpty && modifiedClasses.isEmpty
}
val initialInv = invalidateInitial(previous.relations, initialChanges, log)
log.debug("Initially invalidated: " + initialInv)
val analysis = cycle(initialInv, sources, binaryChanges, previous, doCompile, 1, log)
(!initialInv.isEmpty, analysis)
}
val incDebugProp = "xsbt.inc.debug"
// TODO: the Analysis for the last successful compilation should get returned + Boolean indicating success
// TODO: full external name changes, scopeInvalidations
def cycle(invalidatedRaw: Set[File], allSources: Set[File], binaryChanges: DependencyChanges, previous: Analysis, doCompile: (Set[File], DependencyChanges) => Analysis, cycleNum: Int, log: Logger): Analysis =
if(invalidatedRaw.isEmpty)
previous
else
{
def debug(s: => String) = if(java.lang.Boolean.getBoolean(incDebugProp)) log.debug(s) else ()
val invalidated = expand(invalidatedRaw, allSources, log)
val pruned = prune(invalidated, previous)
debug("********* Pruned: \n" + pruned.relations + "\n*********")
val fresh = doCompile(invalidated, binaryChanges)
debug("********* Fresh: \n" + fresh.relations + "\n*********")
val merged = pruned ++ fresh//.copy(relations = pruned.relations ++ fresh.relations, apis = pruned.apis ++ fresh.apis)
debug("********* Merged: \n" + merged.relations + "\n*********")
val incChanges = changedIncremental(invalidated, previous.apis.internalAPI _, merged.apis.internalAPI _)
debug("Changes:\n" + incChanges)
val incInv = invalidateIncremental(merged.relations, incChanges, invalidated, cycleNum >= TransitiveStep, log)
cycle(incInv, allSources, emptyChanges, merged, doCompile, cycleNum+1, log)
}
private[this] def emptyChanges: DependencyChanges = new DependencyChanges {
val modifiedBinaries = new Array[File](0)
val modifiedClasses = new Array[String](0)
def isEmpty = true
}
private[this] def expand(invalidated: Set[File], all: Set[File], log: Logger): Set[File] =
if(invalidated.size > all.size * RecompileAllFraction) {
log.debug("Recompiling all " + all.size + " sources: invalidated sources (" + invalidated.size + ") exceeded " + (RecompileAllFraction*100.0) + "% of all sources")
all ++ invalidated // need the union because all doesn't contain removed sources
}
else invalidated
/**
* Accepts the sources that were recompiled during the last step and functions
* providing the API before and after the last step. The functions should return
* an empty API if the file did not/does not exist.
*/
def changedIncremental[T](lastSources: collection.Set[T], oldAPI: T => Source, newAPI: T => Source): APIChanges[T] =
{
val oldApis = lastSources.toSeq map oldAPI
val newApis = lastSources.toSeq map newAPI
val changes = (lastSources, oldApis, newApis).zipped.filter { (src, oldApi, newApi) => !sameSource(oldApi, newApi) }
val changedNames = TopLevel.nameChanges(changes._3, changes._2 )
val modifiedAPIs = changes._1.toSet
new APIChanges(modifiedAPIs, changedNames)
}
def sameSource(a: Source, b: Source): Boolean = {
// Clients of a modified source file (ie, one that doesn't satisfy `shortcutSameSource`) containing macros must be recompiled.
val hasMacro = a.hasMacro || b.hasMacro
shortcutSameSource(a, b) || (!hasMacro && SameAPI(a,b))
}
def shortcutSameSource(a: Source, b: Source): Boolean = !a.hash.isEmpty && !b.hash.isEmpty && sameCompilation(a.compilation, b.compilation) && (a.hash.deep equals b.hash.deep)
def sameCompilation(a: Compilation, b: Compilation): Boolean = a.startTime == b.startTime && a.outputs.corresponds(b.outputs){
case (co1, co2) => co1.sourceDirectory == co2.sourceDirectory && co1.outputDirectory == co2.outputDirectory
}
def changedInitial(entry: String => Option[File], sources: Set[File], previousAnalysis: Analysis, current: ReadStamps, forEntry: File => Option[Analysis])(implicit equivS: Equiv[Stamp]): InitialChanges =
{
val previous = previousAnalysis.stamps
val previousAPIs = previousAnalysis.apis
val srcChanges = changes(previous.allInternalSources.toSet, sources, f => !equivS.equiv( previous.internalSource(f), current.internalSource(f) ) )
val removedProducts = previous.allProducts.filter( p => !equivS.equiv( previous.product(p), current.product(p) ) ).toSet
val binaryDepChanges = previous.allBinaries.filter( externalBinaryModified(entry, forEntry, previous, current)).toSet
val extChanges = changedIncremental(previousAPIs.allExternals, previousAPIs.externalAPI _, currentExternalAPI(entry, forEntry))
InitialChanges(srcChanges, removedProducts, binaryDepChanges, extChanges )
}
def changes(previous: Set[File], current: Set[File], existingModified: File => Boolean): Changes[File] =
new Changes[File]
{
private val inBoth = previous & current
val removed = previous -- inBoth
val added = current -- inBoth
val (changed, unmodified) = inBoth.partition(existingModified)
}
def invalidateIncremental(previous: Relations, changes: APIChanges[File], recompiledSources: Set[File], transitive: Boolean, log: Logger): Set[File] =
{
val dependsOnSrc = previous.usesInternalSrc _
val propagated =
if(transitive)
transitiveDependencies(dependsOnSrc, changes.modified, log)
else
invalidateStage2(dependsOnSrc, changes.modified, log)
val dups = invalidateDuplicates(previous)
if(dups.nonEmpty)
log.debug("Invalidated due to generated class file collision: " + dups)
val inv = propagated ++ dups // ++ scopeInvalidations(previous.extAPI _, changes.modified, changes.names)
val newlyInvalidated = inv -- recompiledSources
if(newlyInvalidated.isEmpty) Set.empty else inv
}
/** Invalidate all sources that claim to produce the same class file as another source file. */
def invalidateDuplicates(merged: Relations): Set[File] =
merged.srcProd.reverseMap.flatMap { case (classFile, sources) =>
if(sources.size > 1) sources else Nil
} toSet;
/** Only invalidates direct source dependencies. It excludes any sources that were recompiled during the previous run.
* Callers may want to augment the returned set with 'modified' or all sources recompiled up to this point. */
def invalidateDirect(dependsOnSrc: File => Set[File], modified: Set[File]): Set[File] =
(modified flatMap dependsOnSrc) -- modified
/** Invalidates transitive source dependencies including `modified`.*/
@tailrec def invalidateTransitive(dependsOnSrc: File => Set[File], modified: Set[File], log: Logger): Set[File] =
{
val newInv = invalidateDirect(dependsOnSrc, modified)
log.debug("\tInvalidated direct: " + newInv)
if(newInv.isEmpty) modified else invalidateTransitive(dependsOnSrc, modified ++ newInv, log)
}
/** Returns the transitive source dependencies of `initial`, excluding the files in `initial` in most cases.
* In three-stage incremental compilation, the `initial` files are the sources from step 2 that had API changes.
* Because strongly connected components (cycles) are included in step 2, the files with API changes shouldn't
* need to be compiled in step 3 if their dependencies haven't changed. If there are new cycles introduced after
* step 2, these can require step 2 sources to be included in step 3 recompilation.
*/
def transitiveDependencies(dependsOnSrc: File => Set[File], initial: Set[File], log: Logger): Set[File] =
{
// include any file that depends on included files
def recheck(included: Set[File], process: Set[File], excluded: Set[File]): Set[File] =
{
val newIncludes = (process flatMap dependsOnSrc) intersect excluded
if(newIncludes.isEmpty)
included
else
recheck(included ++ newIncludes, newIncludes, excluded -- newIncludes)
}
val transitiveOnly = transitiveDepsOnly(initial)(dependsOnSrc)
log.debug("Step 3 transitive dependencies:\n\t" + transitiveOnly)
val stage3 = recheck(transitiveOnly, transitiveOnly, initial)
log.debug("Step 3 sources from new step 2 source dependencies:\n\t" + (stage3 -- transitiveOnly))
stage3
}
def invalidateStage2(dependsOnSrc: File => Set[File], initial: Set[File], log: Logger): Set[File] =
{
val initAndImmediate = initial ++ initial.flatMap(dependsOnSrc)
log.debug("Step 2 changed sources and immdediate dependencies:\n\t" + initAndImmediate)
val components = sbt.inc.StronglyConnected(initAndImmediate)(dependsOnSrc)
log.debug("Non-trivial strongly connected components: " + components.filter(_.size > 1).mkString("\n\t", "\n\t", ""))
val inv = components.filter(initAndImmediate.exists).flatten
log.debug("Step 2 invalidated sources:\n\t" + inv)
inv
}
/** Invalidates sources based on initially detected 'changes' to the sources, products, and dependencies.*/
def invalidateInitial(previous: Relations, changes: InitialChanges, log: Logger): Set[File] =
{
val srcChanges = changes.internalSrc
val srcDirect = srcChanges.removed ++ srcChanges.removed.flatMap(previous.usesInternalSrc) ++ srcChanges.added ++ srcChanges.changed
val byProduct = changes.removedProducts.flatMap(previous.produced)
val byBinaryDep = changes.binaryDeps.flatMap(previous.usesBinary)
val byExtSrcDep = changes.external.modified.flatMap(previous.usesExternal) // ++ scopeInvalidations
log.debug(
"\nInitial source changes: \n\tremoved:" + srcChanges.removed + "\n\tadded: " + srcChanges.added + "\n\tmodified: " + srcChanges.changed +
"\nRemoved products: " + changes.removedProducts +
"\nModified external sources: " + changes.external.modified +
"\nModified binary dependencies: " + changes.binaryDeps +
"\nInitial directly invalidated sources: " + srcDirect +
"\n\nSources indirectly invalidated by:" +
"\n\tproduct: " + byProduct +
"\n\tbinary dep: " + byBinaryDep +
"\n\texternal source: " + byExtSrcDep
)
srcDirect ++ byProduct ++ byBinaryDep ++ byExtSrcDep
}
def prune(invalidatedSrcs: Set[File], previous: Analysis): Analysis =
{
IO.deleteFilesEmptyDirs( invalidatedSrcs.flatMap(previous.relations.products) )
previous -- invalidatedSrcs
}
def externalBinaryModified(entry: String => Option[File], analysis: File => Option[Analysis], previous: Stamps, current: ReadStamps)(implicit equivS: Equiv[Stamp]): File => Boolean =
dependsOn =>
analysis(dependsOn).isEmpty &&
orTrue(
for {
name <- previous.className(dependsOn)
e <- entry(name)
} yield {
val resolved = Locate.resolve(e, name)
(resolved.getCanonicalPath != dependsOn.getCanonicalPath) || !equivS.equiv(previous.binary(dependsOn), current.binary(resolved))
}
)
def currentExternalAPI(entry: String => Option[File], forEntry: File => Option[Analysis]): String => Source =
className =>
orEmpty(
for {
e <- entry(className)
analysis <- forEntry(e)
src <- analysis.relations.definesClass(className).headOption
} yield
analysis.apis.internalAPI(src)
)
def orEmpty(o: Option[Source]): Source = o getOrElse APIs.emptySource
def orTrue(o: Option[Boolean]): Boolean = o getOrElse true
private[this] def transitiveDepsOnly[T](nodes: Iterable[T])(dependencies: T => Iterable[T]): Set[T] =
{
val xs = new collection.mutable.HashSet[T]
def all(ns: Iterable[T]): Unit = ns.foreach(visit)
def visit(n: T): Unit =
if (!xs.contains(n)) {
xs += n
all(dependencies(n))
}
all(nodes)
xs --= nodes
xs.toSet
}
// unmodifiedSources should not contain any sources in the previous compilation run
// (this may unnecessarily invalidate them otherwise)
/*def scopeInvalidation(previous: Analysis, otherSources: Set[File], names: NameChanges): Set[File] =
{
val newNames = newTypes ++ names.newTerms
val newMap = pkgNameMap(newNames)
otherSources filter { src => scopeAffected(previous.extAPI(src), previous.srcDependencies(src), newNames, newMap) }
}
def scopeAffected(api: Source, srcDependencies: Iterable[Source], newNames: Set[String], newMap: Map[String, List[String]]): Boolean =
collisions_?(TopLevel.names(api.definitions), newNames) ||
pkgs(api) exists {p => shadowed_?(p, srcDependencies, newMap) }
def collisions_?(existing: Set[String], newNames: Map[String, List[String]]): Boolean =
!(existing ** newNames).isEmpty
// A proper implementation requires the actual symbol names used. This is a crude approximation in the meantime.
def shadowed_?(fromPkg: List[String], srcDependencies: Iterable[Source], newNames: Map[String, List[String]]): Boolean =
{
lazy val newPN = newNames.filter { pn => properSubPkg(fromPkg, pn._2) }
def isShadowed(usedName: String): Boolean =
{
val (usedPkg, name) = pkgAndName(usedName)
newPN.get(name).forall { nPkg => properSubPkg(usedPkg, nPkg) }
}
val usedNames = TopLevel.names(srcDependencies) // conservative approximation of referenced top-level names
usedNames exists isShadowed
}
def pkgNameMap(names: Iterable[String]): Map[String, List[String]] =
(names map pkgAndName).toMap
def pkgAndName(s: String) =
{
val period = s.lastIndexOf('.')
if(period < 0) (Nil, s) else (s.substring(0, period).split("\\."), s.substring(period+1))
}
def pkg(s: String) = pkgAndName(s)._1
def properSubPkg(testParent: Seq[String], testSub: Seq[String]) = testParent.length < testSub.length && testSub.startsWith(testParent)
def pkgs(api: Source) = names(api :: Nil).map(pkg)*/
}
Jump to Line
Something went wrong with that request. Please try again.