package xsbt


 * Extracts simple names used in given compilation unit.
 * Extracts simple (unqualified) names mentioned in given in non-definition position by collecting
 * all symbols associated with non-definition trees and extracting names from all collected symbols.
 * Also extract the names of the types of non-definition trees (see source-dependencies/types-in-used-names
 * for an example where this is required).
 * If given symbol is mentioned both in definition and in non-definition position (e.g. in member
 * selection) then that symbol is collected. It means that names of symbols defined and used in the
 * same compilation unit are extracted. We've considered not extracting names of those symbols
 * as an optimization strategy. It turned out that this is not correct.  Check
 * for an example of scenario where it matters.
 * All extracted names are returned in _decoded_ form. This way we stay consistent with the rest
 * of incremental compiler which works with names in decoded form.
 * Names mentioned in Import nodes are handled properly but require some special logic for two
 * reasons:
 *   1. import node itself has a term symbol associated with it with a name `<import`>.
 *      I (gkossakowski) tried to track down what role this symbol serves but I couldn't.
 *      It doesn't look like there are many places in Scala compiler that refer to
 *      that kind of symbols explicitly.
 *   2. ImportSelector is not subtype of Tree therefore is not processed by `Tree.foreach`
 * Another type of tree nodes that requires special handling is TypeTree. TypeTree nodes
 * has a little bit odd representation:
 *   1. TypeTree.hasSymbol always returns false even when TypeTree.symbol
 *      returns a symbol
 *   2. The original tree from which given TypeTree was derived is stored
 *      in TypeTree.original but Tree.forech doesn't walk into original
 *      tree so we missed it
 * The tree walking algorithm walks into TypeTree.original explicitly.
class ExtractUsedNames[GlobalType <: CallbackGlobal](val global: GlobalType) extends Compat with GlobalHelpers {
  import global._

  @inline def debug(msg: => String) = if (settings.verbose.value) inform(msg)

  def extract(unit: CompilationUnit): Set[String] = {
    val tree = unit.body
    val extractedByTreeWalk = extractByTreeWalk(tree)

  private def extractByTreeWalk(tree: Tree): Set[String] = {
    val namesBuffer = collection.mutable.ListBuffer.empty[String]

     * Some macros appear to contain themselves as original tree.
     * We must check that we don't inspect the same tree over and over.
     * See
    val inspectedOriginalTrees = collection.mutable.Set.empty[Tree]

    def addSymbol(symbol: Symbol): Unit =
      if (eligibleAsUsedName(symbol)) {
        val symbolNameAsString =
        namesBuffer += symbolNameAsString

    def handleTreeNode(node: Tree): Unit = {
      def handleMacroExpansion(original: Tree): Unit = {

      def handleClassicTreeNode(node: Tree): Unit = node match {
        case _: DefTree | _: Template => ()
        // turns out that Import node has a TermSymbol associated with it
        // I (Grzegorz) tried to understand why it's there and what does it represent but
        // that logic was introduced in 2005 without any justification I'll just ignore the
        // import node altogether and just process the selectors in the import node
        case Import(_, selectors: List[ImportSelector]) =>
          def usedNameInImportSelector(name: Name): Unit =
            if ((name != null) && (name != nme.WILDCARD)) namesBuffer += name.toString
          selectors foreach { selector =>
        // TODO: figure out whether we should process the original tree or walk the type
        // the argument for processing the original tree: we process what user wrote
        // the argument for processing the type: we catch all transformations that typer applies
        // to types but that might be a bad thing because it might expand aliases eagerly which
        // not what we need
        case t: TypeTree if t.original != null =>
        case t if t.hasSymbol =>
          if (t.tpe != null)
        case _ => ()

      node match {
        case MacroExpansionOf(original) if inspectedOriginalTrees.add(original) =>
        case _ =>


   * Needed for compatibility with Scala 2.8 which doesn't define `tpnme`
  private object tpnme {
    val EMPTY = nme.EMPTY.toTypeName

  private def eligibleAsUsedName(symbol: Symbol): Boolean = {
    def emptyName(name: Name): Boolean = name match {
      case nme.EMPTY | nme.EMPTY_PACKAGE_NAME | tpnme.EMPTY | tpnme.EMPTY_PACKAGE_NAME => true
      case _ => false

    (symbol != NoSymbol) &&
      (callback.includeSynthToNameHashing || !symbol.isSynthetic) &&