targets.rb

#!/usr/bin/ruby -w

# Ruby-based build system
# Author: ram (Munagala V. Ramanath)
#
# Classes for targets of various types
#

%w{ date find thread open3 set }.each { |f| require f }

# Classes associated with various targets

class Build    # main class and namespace

  # Bare minimal interface for a target: we assume that a target is embodied by a single
  # file. In the typical case this will be an object file generated by the assembler,
  # compiler or linker; in the atypical case (building firefox for example), this will be
  # a file generated by a Perl or Python script. The path to this file and its timestamp
  # are recorded here. Each target also needs the following methods:
  #   out_of_date?  -- return true iff target is out of date
  #   get_cmd       -- get the command to build the target
  #   make          -- run the command to build the target
  #
  module Target
    # path    -- absolute path of target file
    # mtime   -- modification time of target file
    # build   -- current build object (needed for compiler options, etc.)
    # ood     -- true iff target is known to be out-of-date
    #
    # deps    -- dependencies: array of target objects
    # visit -- transient variable that exists only for the duration of a Depth First
    #          Search; values: :start, :finish, nil
    # needed_by -- transient variable: set of targets that need this one to be up-to-date
    #              before they can be built
    # enqueued -- true iff target was enqueued for building
    # rebuilt -- true iff this target was rebuilt (undefined otherwise)
    #
    attr :path, :mtime, :build, :ood
    attr_accessor :deps, :visit, :needed_by, :enqueued, :rebuilt

    # p -- full path to target
    # b -- build object
    # d -- dependency list
    #
    def initialize p, b, d = []
      raise "build is nil" if !b
      @path = Util.strip p
      d = [] if !d    # user may pass nil
      @build, @deps = b, d
      # cannot initialize @mtime since file may not yet exist

      #Build.logger.debug "Initialized %s, deps.size = %d" % [p, d.size]
    end  # initialize

    # Performs these steps (invoked from a separate thread in the thread pool):
    # 1. Build this object file and save mtime
    # 2. Update statistics with build times.
    # 3. Set @rebuilt to true so we can identify targets that were actually built.
    # 4. Update t.needs sets for all targets t in @needed_by
    #
    def make
      log = Build.logger

      # if this target is being built, some other target should need it or this should be
      # a top-level target; in both cases @needed_by should be defined
      #
      raise "needed_by not defined for %s" % @path if !defined? @needed_by

      # assume all checks have been made earlier and build this target
      cmd = get_cmd
      t = Time.new
      Util.run_cmd cmd, Build.logger
      t = Time.new - t
      update_stats t
      @rebuilt = true    # for persistence

      File.check_er @path
      @mtime = File::stat( @path ).mtime
      @ood = false

      # update targets that depend on this one
      if :top == @needed_by    # this is a top-level target
        @build.lock.synchronize {
          status = @build.needs.delete? self
          raise "Failed to delete %s from build.needs" % @path if status.nil?
          # release main thread if no out-of-date top-level targets remain
          @build.done.signal if @build.needs.empty?
        }
        return
      end
      raise "Unexpected: @needed_by is empty for %s" % @path if @needed_by.empty?

      # this target is needed by one or more other targets
      @needed_by.each { |tgt|
        ready = false
        tgt.lock.synchronize {
          #log.debug "tgt.needs.size = %d before deleting %s from %s" %
          #  [tgt.needs.size, @path, tgt.path]
          status = tgt.needs.delete? self
          raise "Failed to delete %s from tgt.needs (%s)" [@path, tgt.path] if
            status.nil?
          ready = tgt.needs.empty?    # whether tgt is ready to be enqueued
        }
        # NOTE: doing this inside the synchronize block causes strange behavior
        next if !ready
        # enqueue tgt since all of its dependencies are current
        raise "Unexpected: %s already enqueued" % tgt.path if tgt.enqueued
        build.thr_pool.add Task.new( tgt, :make )
        log.debug "Added %s to task queue" % tgt.path
        tgt.enqueued = true
      }
    end  # make

    def read_mtime    # get mtime if file is present
      return nil if !File.exist? @path
      @mtime = File::stat( @path ).mtime if !defined? @mtime
      return @mtime
    end  # read_mtime

    def remove_visit    # remove transient instance variable (unused)
      remove_instance_variable :@visit
    end  # remove_visit

  end  # Target

  # .h, .c or other source file; note that this is a target representing the source file
  # itself, not the object file generated from that source file
  #
  class SourceFileTarget
    include Target

    # .hpp, tcc and ipp occur in boost:
    # /usr/include/c++/4.4/bits/basic_string.tcc
    # /usr/include/boost/date_time/gregorian_calendar.ipp
    #
    R_SRC_EXT = /\.(?:h|hpp|ipp|tcc|cc|cpp|c|C|S|s)$/o  # supported source file extensions

    # cmd
    #    if defined, this is a simple shell command or lambda to generate this target; not
    #    intended for heavy duty generators like lex/yacc which should use the same
    #    mechanism as C/C++.
    #
    attr :cmd

    # path : path to source
    # build : current build
    # cmd : generation command if any
    #
    def initialize a_path, a_build, a_cmd = nil
      p = Util.strip a_path
      ext = File.extname p
      # we allow empty extensions because we have system dependencies like this:
      #   /usr/include/c++/4.4/cstddef
      #
      Build.logger.warn "Unexpected extension in #{p}" if !ext.empty? && ext !~ R_SRC_EXT
      super p, a_build
      if a_cmd    # could be string (shell command) or lambda
        @cmd = a_cmd.is_a?( String ) ? Util.strip( a_cmd ) : a_cmd
        return
      end

      # no generation command, so check that the file exists and get mtime
      File.check_er @path
      @mtime = File::stat( @path ).mtime
    end  # initialize

    def make  # build this source target if we have a command
      # revise later when have a DB to store cmd as well; that way, we can rebuild if file
      # exists but cmd has changed.
      #
      if !File.exist? @path    # run generation command
        raise "No command to make %s" % path if !defined? @cmd
        if @cmd.is_a?( String )
          Util.run_cmd @cmd, Build.logger
          File.check_er @path
        else    # must be a lambda
          @cmd.call
        end
        @mtime = File::stat( @path ).mtime
      else
        @mtime = File::stat( @path ).mtime if !defined?( @mtime )
      end
    end  # make

    def bname    # return basename with extension stripped
      File.bname @path
    end  # bname

    def extname    # return extension name
      File.extname @path
    end  # extname

  end  # SourceFileTarget

  class CompileOrLinkTarget    # base class for Compilable and Linkable
    include Target

    # options -- custom compiler, assembler or linker options (if any) for this target
    # build_type
    #     :dbg, :opt, :rel (debug, optimized, release); we can further distinguish objects
    #     intended for dynamic or static linking (i.e. whether they were compiled with
    #     "-fPIC -DPIC" or not) if necessary later with a @dynamic boolean
    #
    attr :options, :build_type

    # get options of given type -- local set if it exists, global set otherwise. When the
    # global set is returned, a copy is made if the second argument is true.
    # When we need to make target-specific changes to options, we get a copy of the global
    # options, make changes to the copy and set it as the option list for this target.
    # When we need to construct the actual command to rebuild the target, we won't be
    # making a copy so copy = false in this case.
    #
    def get_options type, copy = true
      return @options if defined? @options
      opt = build.options.options[ type ]
      return copy ? opt.dup : opt
    end  # get_options

  end  # CompileOrLinkTarget

  # object file obtained by compiling or assembling a source (.{s|S|c|C}) file
  class Compilable < CompileOrLinkTarget

    # options_cpp -- custom pre-processor options (if any) for this target
    # no_hdr_deps
    #     true iff this object file has no header file dependencies (so deps will have
    #     only one item: the source file); this is a rare case but could happen if the
    #     source file has no pre-processor #include directives. If this variable is
    #     defined, the value must be true.
    #
    attr :options_cpp
    attr_accessor :no_hdr_deps

    # map file extension to object type
    EXT2TYPE = { '.o_dbg' => :dbg, '.o_opt' => :opt, '.o_rel' => :rel }

    # a_src   -- source file target (object)
    # a_path  -- path to object file
    # a_build -- current build object
    #
    def initialize a_src, a_path, a_build
      raise "SourceFileTarget != #{a_src.class.name}" if a_src.class != SourceFileTarget

      # sanity check: base names of source and object should be the same
      bname = File.bname a_path
      raise "Base names differ: #{bname} != #{a_src.bname}" if bname != a_src.bname

      super a_path, a_build

      # set the build_type
      ext = File.extname a_path
      @build_type = EXT2TYPE[ ext ]
      raise "Bad extension: '#{ext}'" if !@build_type
      raise "Build type mismatch: #{@build_type} != #{@build.build_type}" if
        @build_type != @build.build_type

      @deps = [a_src]    # first dependency should always be the source file target

      # object file may not yet exist, so cannot stat it
    end  # initialize

    # get cpp options for this target -- local set if present, otherwise global set. If
    # arg is true, a copy of the global set is returned; used when target-specific
    # modifications are made to the option set; arg is false when the options are used
    # for generating the compile command since making a copy is unnecessary then.
    #
    def get_cpp_options copy = true
      return @options_cpp if defined? @options_cpp
      opt = @build.options.options[ :cpp ]
      return copy ? opt.dup : opt
    end  # get_cpp_options

    # return true iff this target is out-of-date and needs to be made; since this is a
    # single object file generated by the compiler or assembler, neither self.needs nor
    # d.needed_by for dependencies d (which will be source or header files) is useful.
    #
    def out_of_date?
      return @ood if defined? @ood
      log = Build.logger

      # check if timestamp on source is more recent (first dependency is always source)
      src = @deps[ 0 ]
      src.make    # generate source file if necessary and possible
      raise "Source %s has no timestamp" % src.path if !src.mtime

      if !File.exist?( @path )    # easy case -- file missing
        log.info "%s out of date since file is absent" % @path
        @ood = true
        return @ood
      end

      # file exists
      @mtime = File::stat( @path ).mtime if ! defined? @mtime
      if 1 == @deps.size    # special case when source file is the only dependency
        raise "No header file deps for #{@path}; was discover_deps run ?" if
          !defined? @no_hdr_deps
        @ood = @mtime < src.mtime
        if @ood
          log.info "%s out of date since %s is newer (%s < %s)" %
            [@path, src.path, @mtime, src.mtime]
        else
          msg = ("%s is current since %s is the only dependency and is older" +
                 " (%s >= %s)") % [@path, src.path, @mtime, src.mtime]
          log.info msg
        end
        return @ood
      end

      # check mtime of all dependencies (first dependency is the source file; the rest
      # are header files)
      #
      @deps.each { |d|
        # We expect all source and header files to exist; if this is not the case (e.g.
        # some of them are generated, we'll need to revise this code
        #
        raise "Dependency %s of %s has no mtime" % [d.path, @path] if d.mtime.nil?
        next if @mtime >= d.mtime    # dependency is older
        log.info "%s out of date since dependency %s is newer (%s < %s)" %
          [@path, d.path, @mtime, d.mtime]
        @ood = true
        return @ood
      }

      # all dependencies are older
      log.info "%s is current since all dependencies are older" % @path
      @ood = false
      return @ood
    end  # out_of_date?

    # remove options from this target
    #
    # args is a hash with these keys:
    #   options -- array of options to delete [required]
    #   type    -- type of options (:cpp) [optional]; it is
    #              required when deleting pre-processor options from assembler, C and C++
    #              targets and should be :cpp in those cases; in other cases, it is
    #              deduced from target type and should be omitted.
    #   err     -- if false, no exception is raised if option is not found; default is
    #              true [optional]
    #
    # sample usage:
    #     delete_options( :options     => ['-Wl,-rpath', '-Wl,/opt/foo/lib'],
    #                     :option_type => :ld_cc_lib,
    #                     :err         => false )
    #
    def delete_options args
      opt = args[ :options ]
      raise "Missing options" if !opt
      raise "Empty options"   if opt.empty?
      type, err = args[ :option_type ], args[ :err ]
      err = true if err.nil?

      # make a local copy of global options if necessary and delete options from copy
      if type
        raise "Bad type: #{type}" if :cpp != type
        @options_cpp = get_cpp_options
        @options_cpp.delete opt, err
      else
        @options = get_options
        @options.delete opt, err
      end
      Build.logger.debug "Deleted %s from target %s (type = %s)" % [opt.to_s, @path, type]
    end  # delete_options

    # add options to this target
    #
    # args is a hash with these keys:
    #   options -- array of options to add [required]
    #   type    -- type of options (:cpp) [optional];
    #              required only when adding pre-processor options to assembler, C and C++
    #              targets and should be :cpp in those cases; in other cases, it is
    #              deduced from target type and should be omitted.
    #   replace -- if false, an exception is raised if an existing option conflicts with
    #              new options; if true, such conflicting options are removed; default is
    #              false [optional]
    #
    # sample usage:
    #     add_options( :options     => ['-Wtype-limits'],
    #                  :option_type => :cpp,
    #                  :replace     => true )
    #
    def add_options args
      opt = args[ :options ]
      raise "Missing options" if !opt
      raise "Empty options"   if opt.empty?
      type, err = args[ :option_type ], args[ :err ]
      err = true if err.nil?

      # make a local copy of global options if necessary and add options to copy
      if type
        raise "Bad type: #{type}" if :cpp != type
        @options_cpp = get_cpp_options
        @options_cpp.add opt, err
      else
        @options = get_options
        @options.add opt, err
      end
      Build.logger.debug "Added %s to target %s (type = %s)" % [opt.to_s, @path, type]
    end  # add_options

  end  # Compilable

  # object file from assembler source
  class ObjFileTargetAS < Compilable

    def initialize a_src, a_path, a_build
      ext = a_src.extname
      raise "Empty src extension" if ext.empty?
      raise "Bad source file extension in: #{ext}" if ext !~ /.[sS]/o
      super a_src, a_path, a_build
    end  # initialize

    # get options of appropriate type for this target (local set if it exists, a copy of
    # global set otherwise)
    #
    def get_options copy = true
      super :as, copy
    end  # get_options

    def get_cmd   # return command to rebuild this object
      # We currently do not support C pre-processor directives in assembler files; if
      # and when we do, we'll need to add CPP options like this:
      #   cpp_opt = get_cpp_options false
      # Then add before as_opt.to_s in the array: cpp_opt.to_s
      #
      as_opt = get_options false
      return [@build.cc, "-o %s -c %s" % [@path, @deps[ 0 ].path], as_opt.to_s].join ' '
    end  # get_cmd

    def update_stats time    # elapsed time
      @build.stats.update :@num_as_objs, time
      Util.print_status @build.thr_pool.tasks.size    # update status message on screen
    end  # update_stats

  end  # ObjFileTargetAS

  class ObjFileTargetCLike < Compilable    # object file from C-like source (C, C++, ...)
    
    R_C_EXT   = /\A\.(?:c)\Z/o           # C file extensions
    R_CXX_EXT = /\A\.(?:C|cc|cpp)\Z/o    # C++ file extensions

    # a_src   -- target object for source file
    # a_path  -- path to object file
    # a_build -- current build object
    # src_ext -- source file extension (used from ObjFileTargetCXX)
    #
    def initialize a_src, a_path, a_build, src_ext = /.c/o
      ext = a_src.extname
      raise "Unexpected: src_ext is nil" if !src_ext
      raise "Bad source file extension: #{ext}" if ext !~ src_ext

      super a_src, a_path, a_build

      # We might create all 3 targets (.o_dbg, .o_opt, .o_rel) for each source file found
      # because it allows us to perform more than one type of build during the course of a
      # single run; so skip this check:
      # raise "Build type mismatch: #{@build_type} != #{@build.build_type}" if
      #   @build_type != @build.build_type

    end  # initialize

    # Invoked _only_ for C and C++ object files.
    # return true if dependency list from persistence db is usable, false otherwise
    # if returning true, should set @hdrs to array of header file dependencies (or set
    # @no_hdr_deps if there no header files)
    #
    def set_deps_from_db compiler, cpp_opt
      db = @build.db
      return false if ! db    # persistence not enabled
      t = db.get_obj @path
      return false if !t             # no persisted data
      log = Build.logger

      if !File.exist?( @path )
        # it may still be the case that the dependency list from the DB is usable but
        # to verify that we need timestamps of all dependencies from the previous build
        # which, currently, are not saved to the database. If we had them and they are
        # unchanged we can return true (but still set @ood to true since the object
        # file needs to be generated)
        #
        log.info "%s out-of-date since file is absent" % @path
        @ood = true
        return false
      end

      # object file exists; get timestamp and compare to that of source
      @mtime = File::stat( @path ).mtime if !defined?( @mtime )
      sf = @deps.first    # first dependency is the source file
      if @mtime <= sf.mtime
        log.info "%s out-of-date since source file %s is newer" % [@path, sf.path]
        @ood = true
        return false
      end

      saved_compiler = db.get( '.c' =~ get_src_ext ? Build::KEY_CC_PATH
                                                   : Build::KEY_CXX_PATH )
      if compiler != saved_compiler
        # different compilers have different pre-defined pre-processor symbols so it is
        # possible that the set of header file dependencies is different
        #
        log.info "%s out-of-date since compiler is different: %s != %s" %
          [@path, compiler, saved_compiler]
        @ood = true
        return false
      end

      # needs fixing: compare CPP options, not compile options.
      # Get saved custom CPP options for this object, if any; otherwise, global CPP
      # options
      #
      saved_opt = t.options_cpp
      saved_opt = db.get_obj( Build::KEY_OPT_CPP ) if !saved_opt

      if cpp_opt != saved_opt    # options differ
        log.info "%s out-of-date since pre-processor options differ" % @path
        @ood = true
        return false
      end

      # compiler path and CPP options are the same and object file exists
      # compare time stamp of object with time stamp of all dependencies
      #
      h = []    # list of dependency header files
      t.deps.each{ |dname|
        if !File.exist? dname
          log.info "%s out-of-date since dependency file %s is absent" % [@path, dname]
          @ood = true
          return false
        end

        # dependency file exists, so get timestamp
        d_time = File::stat( dname ).mtime
        raise "Unable to get time stamp of #{dname}" if ! d_time
        h << dname
        next if @mtime > d_time    # dependency file is older

        # dependency file is newer
        log.info "%s out-of-date since dependency file %s is newer" % [@path, dname]
        h = nil
        @ood = true
        return false
      }

      # this target and all header file dependencies are current, so it does not need to
      # be remade; set @no_hdr_deps if there are no header file dependencies or set @hdrs
      # to the list of those dependencies
      #
      @ood = false
      if h.empty?
        @no_hdr_deps = true
      else
        @hdrs = h
      end
      return true

    end  # set_deps_from_db

    # Executed by a separate thread for each object so must be thread-safe (multiple
    # threads will, of course, never execute this method on the _same_ object!). Only
    # invoked on C and CXX objects (later on AS objects if necessary)
    #
    def discover_deps  # discover dependencies
      log = Build.logger

      # don't need compiler options, only need pre-processor options since we are
      # generating dependencies and not compiling
      #
      opt = get_cpp_options false
      compiler = get_compiler

      # if persistence database is unavailable, or if dependencies there are not usable
      # regenerate them
      #
      if !set_deps_from_db( compiler, opt )
        
        # sanity check the source file extension
        src_path = @deps[ 0 ].path
        src_ext = File.extname src_path    # actual source extension
        s_ext = get_src_ext                # expected source extension
        raise "Expected extension %s, got %s" % [s_ext, src_ext] if s_ext !~ src_ext

        # run pre-processor to generate file of dependency data; that file has same path
        # as object file but with .d extension
        # sub! returns nil if no substitution occurred
        #
        extname = File.extname @path
        dpath = @path.dup.sub!( /#{extname}\Z/o, '.d' )
        raise "Extension substitution of #{extname} failed on #{@path}" if !dpath

        # the -M yields all header files (use -MM to exclude system headers).
        # NOTE: We want all headers since we really should recompile if some system header
        #       changed due to a package upgrade.
        #
        cmd = [get_compiler, "#{src_path} -M -MF #{dpath}", opt.to_s].join ' '
        Util.run_cmd cmd, Build.logger
        files = parse_deps dpath    # list of file names (not objects)
        if files.nil? || files.empty?
          log.warn "No header deps for #{@path}"
          @no_hdr_deps = true    # indication that header deps have been computed
        else
          @hdrs = files
        end
      end  # db check

      cnt = defined?( @hdrs ) ? @hdrs.size : 0
      @build.stats.update_deps cnt    # update dependency histogram

      @build.lock.synchronize {    # awaken main thread if all tasks are done
        @build.deps_done_cnt += 1
        if @build.deps_enq_cnt == @build.deps_done_cnt
          @build.done.signal
          log.info "All dependency tasks complete; signalled main thread"
        end
      }
    end  # discover_deps

    # Convert list of header file names into list of objects and add to @deps. Invoked by
    # main thread after all worker threads have finished and dependent header file names
    # have been discovered and stored in @hdrs
    # 
    # Not thread safe since it accesses and modifies global target list
    #
    def hdrs_to_deps
      return if !defined?( @hdrs ) || @hdrs.empty?    # nothing to do

      # @hdrs guaranteed to be non-nil and non-empty here
      @hdrs.each { |f|
        target = @build.find_target f
        if target    # target object already exists
          raise "Multiple targets for #{f}" if target.size > 1
          @deps << target.first
          next
        end

        # get here for system headers (which will not be automatically discovered when
        # we scan the project source directory)
        #
        #log.debug "Adding header file target: %s" % f
        src = SourceFileTarget.new f, @build    # create object
        @build.add_targets [src]
        @deps << src
      }  # @hdrs iterator

      # no longer need @hdrs
      @hdrs = nil
    end  # hdrs_to_deps

    # expected prefixes for all header files
    R_HDR_PREFIX     = %r{^/(?:usr|opt|home)}o

    # OSX gets many headers from strange places:
    #  /System/Library/Frameworks/...
    #  /Applications/Xcode.app/Contents/...
    #  
    R_HDR_PREFIX_OSX = %r{^/(?:Developer|System|Users|Applications)}o

    def parse_deps dpath   # parse dependency file and return array of objects or nil
      log = Build.logger
      result = []
      # We might see output like this:
      # Stuff.o: \
      # /home/user/src/stuff/c++/Stuff.C \
      # /home/user/src/stuff/c++/Stuff.h \
      # ...
      #
      # or like this:
      #  baz.o: /home/user/c/baz.c /usr/include/stdio.h /usr/include/features.h \
      #   /usr/include/bits/predefs.h /usr/include/sys/cdefs.h \
      #   /usr/include/bits/wordsize.h /usr/include/gnu/stubs.h \
      #   /usr/include/gnu/stubs-64.h \
      #   /usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.5.2/include/stddef.h \
      #   /usr/include/bits/types.h /usr/include/bits/typesizes.h \
      #   /usr/include/libio.h /usr/include/_G_config.h /usr/include/wchar.h \
      #   /usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.5.2/include/stdarg.h \
      #   /usr/include/bits/stdio_lim.h /usr/include/bits/sys_errlist.h slow.h
      #
      state = :first
      s_ext = get_src_ext    # expected extension on source file
      IO.foreach( dpath ) { |line|
        line.strip!
        fields = line.split

        if :first == state
          raise "No dependency info: line = %s, dpath = %s" % [line, dpath] if
            fields.size < 2
          obj = fields.shift        # first field should be object file with ':' suffix
          raise "Expected #{obj} to end with ':'" if !obj.end_with? ':'
          src = fields.shift        # second field could be '\' or src file
          if '\\' == src
            state = :second    # we expect to find source file on next line
            next
          end
          raise "Expected %s to end with %s (dpath = %s)" % [src, s_ext, dpath] if
            s_ext !~ File.extname( src )
          state = :rest
        elsif :second == state
          src = fields.shift        # first field should be src file
          raise "Expected %s to end with %s (dpath = %s)" % [src, s_ext, dpath] if
            s_ext !~ File.extname( src )
          state = :rest
        end
        fields.pop if '\\' == fields[ -1 ]    # ignore continuation
        next if fields.empty?                 # nothing else on this line

        # have header files; here we have (:rest == state)
        fields.each_with_index { |f, i|
          raise "Unexpected backslash in #{line}, i = #{i}" if '\\' == f

          # we have a real header file name

          # since we exclusively use absolute paths with -I options, all dependencies
          # should be absolute paths; this is important since multiple directories
          # can have the same file name such as util.h or common.h or conf.h
          #
          raise "Dependency path #{f} not absolute" if !f.start_with? '/'

          # All header file paths must start with one of a handful of prefixes; warn if
          # they do not.
          #
          log.warn "Unusual header file location: #{f}" if
            !(f =~ R_HDR_PREFIX || (Build.system.darwin? && f =~ R_HDR_PREFIX_OSX))
          
          result << f
        }  # fields
      }  # IO.foreach

      if false && log.debug?    # dump all headers found (lots of output)
        if result.empty?
          # should never happen since we've eliminated this case above
          log.debug "No headers for #{@path}"
        else
          log.debug "Found #{result.size} headers for #{@path}:"
          result.each_with_index{ |p, i| log.debug "%6i: %s" % [i, p.path]}
        end
      end

      return result.empty? ? nil : result
    end  # parse_deps

  end  # ObjFileTargetCLike

  class ObjFileTargetC < ObjFileTargetCLike    # object file from C source
    def initialize a_src, a_path, a_build
      super
    end  # initialize

    # get options of appropriate type for this target (local set if it exists, a copy of
    # global set otherwise)
    #
    def get_options copy = true
      super :cc, copy
    end  # get_options

    def get_cmd   # return command to rebuild this object
      cpp_opt, cc_opt = get_cpp_options( false ), get_options( false )  # no need to copy
      return [@build.cc, "-o %s -c %s" % [@path, @deps[ 0 ].path],
              cpp_opt.to_s, cc_opt.to_s].join ' '
    end  # get_cmd

    def get_src_ext   # return expected extension of source file
      R_C_EXT
    end  # get_src_ext

    def get_compiler   # return compiler to compile source file
      @build.cc
    end  # get_compiler

    def update_stats time    # user time, system time
      @build.stats.update :@num_cc_objs, time
      Util.print_status @build.thr_pool.tasks.size    # update status message on screen
    end  # update_stats

  end  # ObjFileTargetC

  # may need to refactor later with a common base class for C and C++
  class ObjFileTargetCXX < ObjFileTargetCLike    # object file from C++ source
    def initialize a_src, a_path, a_build, src_ext = R_CXX_EXT
      super
    end  # initialize

    # get options of appropriate type for this target (local set if it exists, a copy of
    # global set otherwise)
    #
    def get_options copy = true
      super :cxx, copy
    end  # get_options

    def get_cmd   # return command to rebuild this object
      cpp_opt, cxx_opt = get_cpp_options( false ), get_options( false )  # no need to copy
      return [@build.cxx, "-o %s -c %s" % [@path, @deps[ 0 ].path],
              cpp_opt.to_s, cxx_opt.to_s].join ' '
    end  # get_cmd

    def get_src_ext   # return expected extension of source file
      R_CXX_EXT
    end  # get_src_ext

    def get_compiler   # return compiler to compile source file
      @build.cxx
    end  # get_compiler

    def update_stats time    # user time, system time
      @build.stats.update :@num_cxx_objs, time
      Util.print_status @build.thr_pool.tasks.size    # update status message on screen
    end  # update_stats

  end  # ObjFileTargetCXX

  # object file obtained by linking
  class Linkable < CompileOrLinkTarget   # common base class for libs and executables
  
    # link_type
    #   NOTE: Fully static linking is no longer possible on many modern systems, see:
    #         http://stackoverflow.com/questions/3430400/linux-static-linking-is-dead
    #
    #   :static - for a library, this means we build an archive of object files using 'ar';
    #             for an executable, this means that for any local libraries (i.e. those
    #             that are part of this project) we use the static versions. System
    #             libraries are specified as usual with "-l" flags and the linker may use
    #             dynamic versions for those.
    #   :dynamic - fully dynamically linked library (libfoo.{so,dylib}) or executable
    #   :hybrid - (not currently supported)
    #       library or executable where some components are statically linked and
    #       some dynamic (possible to do this with linker options like this:
    #           -Wl,-Bstatic -la -lb -Wl,-Bdynamic -lx -ly
    #       Here lib{a,b} will be statically linked, lib{x,y} dynamically linked.
    #       (see http://linux.die.net/man/1/ld for a detailed ld man page)
    #
    # libs   -- list of library dependencies
    # linker -- :ld_cc or :ld_cxx
    # opt_type -- type of options relevant to this target; one of:
    #               :ld_cc_lib, :ld_cc_exec, :ld_cxx_lib, :ld_cxx_exec
    #
    # needs -- transient variable: set of targets that need to be built before this one
    #          can be built
    # lock -- mutex to synchronize access to @needs since multiple threads may remove
    #         dependencies from this set as they are made
    #
    attr :link_type, :libs, :linker, :opt_type
    attr_accessor :needs, :lock

    EXT2TYPE = {    # map file extension to build type
      '.dbg_d'     => :dbg,   '.opt_d'     => :opt,   '.rel_d'     => :rel,  # executables
      '.dbg_s'     => :dbg,   '.opt_s'     => :opt,   '.rel_s'     => :rel,
      '.a_dbg'     => :dbg,   '.a_opt'     => :opt,   '.a_rel'     => :rel,
      '.so_dbg'    => :dbg,   '.so_opt'    => :opt,   '.so_rel'    => :rel,   # libs
      '.dylib_dbg' => :dbg,   '.dylib_opt' => :opt,   '.dylib_rel' => :rel }  # OSX libs

    # args is a hash with these keys:
    #
    # path   -- path to library or executable (required)
    # build  -- current build (required)
    # deps   -- object file dependencies (required)
    # libs   -- library dependencies (optional)
    # linker -- :ld_cc (C link) or :ld_cxx (C++ link) (required)
    # link_type -- :static or :dynamic; default is to use value in build (optional)
    #
    def initialize args
      super args[ :path ], args[ :build ], args[ :deps ]
      ldeps = args[ :libs ]
      @libs = ldeps if ldeps
      @linker = args[ :linker ]
      raise "Missing linker argument" if !@linker
      raise "Bad linker type: #{@linker}" if ![:ld_cc, :ld_cxx].include? @linker
      # executable or library file may not yet exist, so cannot stat it

      ltype = args[ :link_type ]
      if ltype
        raise "Bad link_type: #{ltype}" if ![:static, :dynamic].include?( ltype )
        @link_type = ltype
      else
        @link_type = build.link_type
      end

      # check that build type of file matches global build type
      @build_type = EXT2TYPE[ File.extname @path ]
      raise "Build type mismatch for #{@path}: #{@build_type} != #{build.build_type}" if
        @build_type != build.build_type

      # debug
      #log = Build.logger
      #log.debug "dependencies for #{@path} = "
      # @deps.each { |d| log.debug d.class.name + ": #{d.path.size}" }

      # check that the extension on dependencies matches type
      t = ".o_#{@build_type}"    # expected extension of dependency
      i = @deps.index{ |d| t != File.extname( d.path ) }
      raise "Unexpected extension (expected #{t}) in: #{@deps[ i ].path}" if i

      # check extension of all library dependencies
      if defined? @libs
        e = "_%s" % @build_type
        @libs.each { |lib|
          ext = File.extname lib.path
          raise "Unexpected extension (expected suffix #{e}) in #{lib.path}" if
            !ext.end_with? e
        }
      end
    end  # initialize

    # return true iff this target is out-of-date and needs to be made; since this is a
    # linker object, its dependencies could be object files or other libraries. Here we
    # set self.need to the set of out-of-date dependencies and add self to d.needed_by
    # to each of those dependencies d
    #
    def out_of_date?
      return @ood if defined? @ood
      log = Build.logger

      if false      # debug
        log.debug "Checking dependencies (%d libraries, %d files) of %s:" %
          [(defined?( @libs ) ? @libs.size : 0), @deps.size, @path]
        @libs.each_with_index{ |d, i|
          log.debug "%6d: %s" % [i, d.path]
        } if defined?( @libs )
        @deps.each_with_index{ |d, i|
          log.debug "%6d: %s" % [i, d.path]
        }
      end

      # check if we have out-of-date dependencies
      all_deps = @deps
      all_deps += @libs if defined? @libs
      need_to_make_deps = all_deps.select{ |d| d.out_of_date? }

      if !File.exist?( @path )
        log.info "%s out-of-date since file is absent" % @path
        @ood = true
        # cannot return yet since we need to process dependencies
      else
        @mtime = File::stat( @path ).mtime if !defined?( @mtime )
      end

      if need_to_make_deps.empty?
        log.info "All dependencies of %s are current" % @path

        # no need to set @needs; determine if this target needs regeneration
        if !defined? @ood    # file exists; compare mtimes
          o_deps = all_deps.select{ |d| @mtime < d.mtime }
          if o_deps.empty?   # this target is current and does not need to be remade
            @ood = false

            msg = ("%s is current and will not be remade since file and all " +
                   "dependencies exist, and file is newer than all deps.") % @path
            log.info msg
          else    # at least 1 dependency is newer
            @ood = true
            if log.debug?    # print list of out-of-date dependencies
              log.debug "%s out-of-date since %d dependencies are newer" %
                [@path, o_deps.size]
              o_deps.map( &:path ).sort.each_with_index{ |s, i|
                log.debug "    %d: %s" % [i, s]
              }
            end  # log.level check
          end    # o_deps.empty? check
        end      # defined? @ood check

      else    # have at least 1 dependency that is out-of-date; define @needs

        @ood = true
        @needs = Set[ *need_to_make_deps ]
        @lock = Mutex.new
        # no need to compare mtime to mtime of all dependencies since we already know
        # that this target is out-of-date and will be remade

        if log.debug?    # print list of out-of-date dependencies
          log.debug "%s has %d out-of-date dependencies:" % [@path, @needs.size]
          @needs.map( &:path ).sort.each_with_index{ |s, i|
            log.debug "    %d: %s" % [i, s]
          }
        end

        @needs.each { |d|    # for each dependency d, add self to d.needed_by 
          if !d.needed_by
            d.needed_by = Set[ self ]
          else
            raise "Top-level target %s is a dependency for %s" % [d.path, @path] if
              :top == d.needed_by
            d.needed_by << self
          end
        }
      end

      return @ood
    end  # out_of_date?

    # get options of appropriate type for this target (local set if it exists, a copy of
    # global set otherwise)
    #
    def get_options copy = true
      super @opt_type, copy
    end  # get_options

    # Recursive utility routine to add library file paths to list. Used when constructing
    # the link command: for example, if the executable is built from object files a.o and
    # b.o and libraries libA and libB where the latter depends on libC, we want this
    # function to return the list of paths to:
    #   a.o, b.o, libA.a,  libB.a,  libC.a     {static linking}
    #   a.o, b.o, libA.so, libB.so, libC.so    {dynamic linking}
    #
    # list -- list of paths to objects to link
    # libs -- list of library objects whose paths we want to add
    #
    def self.add_libs list, libs
      # add these libraries first and then the descendents since there may be references
      # in these libraries to symbols defined in the descendents but the reverse cannot
      # happen
      #
      list += libs.map( &:path )
      libs.each { |lib|
        clibs = lib.libs
        next if !clibs || clibs.empty?
        list = add_libs list, clibs
      }
      return list
    end  # add_libs

  end  # Linkable

  class LibFileTarget < Linkable    # library (static or dynamic)
    # These are for shared libraries and are undefined/nil for static libs; only one is
    # valid for a particular build.
    #
    # soname -- (non-OSX) soname
    # install_name -- (OSX) install_name
    #
    attr :soname, :install_name

    # args is a hash with all keys of Linkable plus: soname or install_name
    #
    def initialize args
      super
      @opt_type = :ld_cc == @linker ? :ld_cc_lib : :ld_cxx_lib

      if Build.system.darwin?
        name = args[ :install_name ]
        if :dynamic == @link_type
          raise "Need install_name for dynamic library #{@path}" if !name
          @install_name = name
        else    # static lib
          raise "Got install_name #{name} for static library #{@path}" if name
        end

      else    # not OSX

        name = args[ :soname ]
        if :dynamic == @link_type
          raise "Need soname for dynamic library #{@path}" if !name
          @soname = name
        else    # static lib
          raise "Got soname #{name} for static library #{@path}" if name
        end
      end

    end  # initialize

    # helper routine for make
    # create suitable link command to build this library
    #
    def get_cmd
      log = Build.logger

      # list of objects to link
      # for a library, we only need the subsidiary libraries in the case of dynamic
      # linking since the static library is built using "ar" and only needs the local
      # objects
      #
      objlist = @deps.map( &:path )
      if :dynamic == @link_type && defined? @libs    # add lib files if any
        log.debug "Adding %d library files for %s" % [@libs.size, @path]
        objlist = Linkable.add_libs objlist, @libs    # get all required libraries
      end
      raise "No objects for #{@path}" if objlist.empty?

      # static lib is easy
      if :static == @link_type
        cmd = "ar scru #{@path} " + objlist.join( ' ' )
        return cmd
      end

      # no need for cc, cxx, or cpp options; only need linker options
      opt = get_options false
      link = (:ld_cc == @linker) ? @build.cc : @build.cxx

      # error if -shared is not present for a dynamic library
      i = opt.get_opt '-shared'
      j = opt.get_post '-shared'
      raise "Library target %s missing -shared linker option" % @path if ( !i && !j )
      raise "Library target %s missing soname" % @path if !defined? @soname

      s_opt, s_post = opt.to_s, opt.post_to_s    # pre/post options as strings
      cmd = [link, "-o #{@path}", s_opt].join( ' ' ) 
      cmd += ' ' + objlist.join( ' ' )

      # @install_name/@soname will not be defined if we are linking an executable (this
      # is checked in the class initializer
      #
      if Build.system.darwin?
        cmd += ' -install_name ' + @install_name if defined? @install_name
      else
        cmd += ' -Wl,-soname -Wl,' + @soname if defined? @soname
      end

      cmd += ' ' + s_post if !s_post.empty?
      return cmd
    end  # get_cmd

    # build this library
    def make
      super

      # no symbolic links needed for static libraries
      return if :static == @link_type

      if Build.system.darwin?
        # create symbolic link install_name --> real name if the two differ
        # get basenames of actual file and install_name; basename includes extension
        base, ibase = File.basename( @path ), File.basename( @install_name )
        return if base == ibase     # no link needed

        link = File.join File.dirname( @path ), ibase
        return if File.exist? link    # link already exists

      else

        # create symbolic link soname --> real name if the two differ
        base = File.basename @path    # basename includes extension
        return if base == @soname     # no link needed

        link = File.join File.dirname( @path ), @soname
        return if File.exist? link    # link already exists

      end  # darwin check

      cmd = "ln -s %s %s" % [@path, link]
      Util.run_cmd cmd, Build.logger

    end  # make

    def update_stats time    # user time, system time
      @build.stats.update( :ld_cc == @linker ? :@num_cc_libs : :@num_cxx_libs, time )
      Util.print_status @build.thr_pool.tasks.size    # update status message on screen
    end  # update_stats

  end  # LibFileTarget

  class ExecFileTarget < Linkable    # executable
    # static/dynamic executable named foo: foo.dbg_s/foo.dbg_d, foo.opt_s/foo.opt_d etc.

    # args is a hash with all keys of Linkable
    def initialize args
      super
      @opt_type = :ld_cc == @linker ? :ld_cc_exec : :ld_cxx_exec

      if Build.system.darwin?
        name = args[ :install_name ]
        raise "Got install_name #{name} for executable #{@path}" if name
      else
        name = args[ :soname ]
        raise "Got soname #{name} for executable #{@path}" if name
      end
    end  # initialize

    # helper routine for make
    # create suitable link command to build this executable
    #
    def get_cmd
      log = Build.logger

      # list of objects to link: for an executable, we want all the libraries regardless
      # of whether we are linking statically or dynamically
      #
      objlist = @deps.map( &:path )
      if defined? @libs    # add lib files if any
        log.debug "Adding %d library files for %s" % [@libs.size, @path]
        objlist = Linkable.add_libs objlist, @libs    # get all required libraries
      end
      raise "No objects for #{@path}" if objlist.empty?

      # no need for cc, cxx, or cpp options; only need linker options
      opt = get_options false
      link = (:ld_cc == @linker) ? @build.cc : @build.cxx

      # error if -shared is present for an executable because that will create a shared
      # library, not an executable file!
      #
      if Build.system.darwin?
        i = opt.get_opt '-dynamiclib'
        j = opt.get_post '-dynamiclib'
        raise "Executable target %s has -dynamiclib linker option" % @path if ( i || j )
        raise "Executable target %s has install_name" % @path if defined? @install_name
      else
        i = opt.get_opt '-shared'
        j = opt.get_post '-shared'
        raise "Executable target %s has -shared linker option" % @path if ( i || j )
        raise "Executable target %s has soname" % @path if defined? @soname
      end

      s_opt, s_post = opt.to_s, opt.post_to_s    # pre/post options as strings
      cmd = [link, "-o #{@path}", s_opt].join( ' ' ) 
      cmd += ' ' + objlist.join( ' ' )

      cmd += ' ' + s_post if !s_post.empty?
      return cmd
    end  # get_cmd

    # add options to this target
    #
    # args is a hash with these keys:
    #   options -- array of options to add [required]
    #   type    -- type of options (:exe) [optional];
    #   replace -- if false, an exception is raised if an existing option conflicts with
    #              new options; if true, such conflicting options are removed; default is
    #              false [optional]
    #
    # sample usage:
    #     add_options( :options     => ['-Wtype-limits'],
    #                  :option_type => :cpp,
    #                  :replace     => true )
    #
    def add_options args
      opt = args[ :options ]
      raise "Missing options" if !opt
      raise "Empty options"   if opt.empty?
      type, err = args[ :option_type ], args[ :err ]
      err = true if err.nil?

      @options = get_options
      @options.add opt, err

      Build.logger.debug "Added %s to target %s (type = %s)" % [opt.to_s, @path, type]
    end  # add_options

    def update_stats time    # user time, system time
      @build.stats.update( :ld_cc == @linker ? :@num_cc_execs : :@num_cxx_execs, time )
      Util.print_status @build.thr_pool.tasks.size    # update status message on screen
    end  # update_stats

  end  # ExecFileTarget

  # add a list of targets to list of known targets (not to list of default targets)
  def add_targets args
    args.each { |t|
      raise "Bad object (expected Target): #{t.class.name}" if !t.is_a? Target
      raise "Duplicate target: #{t.path}" if @all_targets.key? t.path
      @all_targets[ t.path ] = t
      Build.logger.debug "Added target: %s" % t.path
    }
  end  # add_targets

  def chk_incl_excl incl, excl    # variety of checks on include/exclude lists
    raise "Entire source root excluded: #{excl}" if excl && excl.include?( '.' )
    raise "Include list empty" if incl && incl.empty?
    raise "Include list has duplicates" if incl && incl.uniq!
    raise "Exclude list has duplicates" if excl && excl.uniq!
    return if !(incl && excl)    # at most one is non-nil

    # an exclude path must not be a parent of any other item in either list
    excl.each { |e|
      e2 = e + '/'
      bad = incl.index{ |ip| ip == e || ip.start_with?( e2 ) }
      raise "Include path #{incl[bad]} descendent of exclude path #{e}" if bad
      bad = excl.index{ |ep| ep != e && ep.start_with?( e2 ) }
      raise "Exclude path #{excl[bad]} descendent of exclude path #{e}" if bad
    }
    # an include path must not be a parent of another include path
    incl.combination( 2 ) { |p1, p2|
      # need to check prefix with separator (otherwise c is detected as ancestor of c++)
      q1, q2 = p1 + '/', p2 + '/'
      bad = p1.start_with?( q2 ) || p2.start_with?( q1 )
      raise "Include paths #{p1} and #{p2} ancestor/descendent" if bad
    }
  end  # chk_incl_excl

  # compute all targets starting from @src_root
  # + if args[:include] is present, only those directories and files are searched
  #   and used (must be relative paths)
  # + if args[:exclude] is present, those files and directories are excluded
  #   (must be relative paths)
  # + if args[:all] is true, target objects for all 3 types are created (this could be
  #   useful if we want to build multiple types of builds in the same run); if false,
  #   only current build type target is created.
  #
  def discover_targets args = {}
    incl, excl, all = args[ :include ], args[ :exclude ], args[ :all ]
    raise "Bad build type: #{all}" if all and true != all

    # remove trailing slash if any
    incl.map!{ |v| '/' == v[ -1 ] ? v.chop : v } if incl
    excl.map!{ |v| '/' == v[ -1 ] ? v.chop : v } if excl

    log = Build.logger

    # sanity checks
    chk_incl_excl incl, excl

    log.debug( "Discovering targets, src_root = %s, include = %s, exclude = %s" %
               [@src_root, incl.to_s, excl.to_s] )

    # prepend src_root to incl and excl
    # if incl is nil we start at src_root; otherwise, at each element of incl
    #
    list = incl ? incl.map{ |p| File.join( @src_root, p ) } : [@src_root]
    excl.map!{ |p| File.join( @src_root, p ) } if excl

    list.each { |dir|
      Find.find( dir ) { |f|   # we don't see '.' and '..' here

        if excl && excl.include?( f )    # exclude list
          #log.debug "Skipping %s (in excl)" % f
          if File.directory? f
            Find.prune
          else
            next
          end
        end

        if File.directory?( f ) || !File.file?( f )
          #log.debug "Skipping %s (directory)" % f
          next
        end

        # we have a usable file
        if f !~ /\.(?:c|C|cc|cpp|S)\Z/o    # not a source file we can process
          #log.debug "Skipping non C/C++/assembler file: %s" % f
          next
        end

        # finally, add source and object targets
        if all    # build targets of all types
          add_object f, nil, true, true
        else   # build targets of current build type
          add_object f
        end
      }  # Find.find
    }    # list
    log.debug "Done discovering targets"
  end  # discover_targets

  # Add source file and associated object targets. This function can be called from
  # 2 contexts
  # (a) From discover_targets above for existing source files;
  # (b) From any of the subproject classes in <your-project>.rb for generated sources, if
  #     there are any.
  #
  # file -- full path to source file
  # cmd -- command to generate source file
  # sub -- if sub is true, we expect to find src_root as a prefix and replace it with
  #        obj_root; sub is false for generated source files
  # all -- if true, targets of all 3 types are added, otherwise only a single target of
  #        the current build type is added (currently, always false)
  #
  # sub will be false for generated files which should already be under obj_root; for
  # such files, a generation command must be provided in gen
  #
  def add_object file, cmd = nil, sub = true, all = false
    #raise "Need generation command for #{file}" if !cmd && !sub

    #log = Build.logger
    ext = File.extname file     # add source target based on extension
    case ext
    when /\.[sS]\Z/o                        # assembler source file
      src = SourceFileTarget.new file, self, cmd
      cls = ObjFileTargetAS
      
    when /\.c\Z/o                        # C source file
      src = SourceFileTarget.new file, self, cmd
      cls = ObjFileTargetC
      
    when /\.C\Z/o, /\.cc\Z/o, /\.cpp\Z/o     # C++ source file
      src = SourceFileTarget.new file, self, cmd
      cls = ObjFileTargetCXX
      
    else raise "Unsupported extension in file: #{file}"
    end  # case
    #log.debug "Adding source target: %s" % file
    add_targets [src]

    pre = /^#{@src_root}/o    # for stripping prefix

    # add object file targets
    bname = File.bname file     # file base name excluding extension
    path = File.dirname file
    # replace leading src_root prefix with obj_root
    raise "Failed to replace #{@src_root} in #{file}" if
      sub && ! path.sub!( pre, @obj_root )

    if all    # not yet supported
      objects = BUILD_TYPES.map { |v|
        p = File.join( path, bname + ".o_#{v}" )
        #log.debug "Adding object file target: %s" % p
        cls.new src, p, self
      }
    else
      p = if :dynamic == @link_type
            File.join( path, bname + ".o_#{@build_type}" )
          else
            File.join( path, 'static', bname + ".o_#{@build_type}" )
          end
      #log.debug "Adding object file target: %s" % p
      objects = [cls.new( src, p, self )]
    end
    add_targets objects
  end  # add_object

  # returns an array of target objects matching given path suffix (or nil if none exist).
  # Argument can be either an absolute path or some suffix thereof
  #
  def find_target tgt
    if '/' == tgt[ 0 ]    # absolute path
      result = @all_targets[ tgt ]
      return result.nil? ? nil : [result]
    end

    # tgt is a relative path (suffix)
    t = tgt.reverse + '/'

    # sorted list of reversed keys: rebuild list if new targets have been added
    @sort_all_targets = @all_targets.keys.map( &:reverse ).sort! if
      !defined?( @sort_all_targets ) || @sort_all_targets.size < @all_targets.size

    # binary search
    max = @sort_all_targets.size
    low, high = 0, max
    mid = (low + high) / 2
    loop {
      break if @sort_all_targets[ mid ].start_with? t
      (t > @sort_all_targets[ mid ]) ? low = mid + 1: high = mid
      return nil if low >= high
      mid = (low + high) / 2
    }

    # found a match at mid
    k = @sort_all_targets[ mid ].reverse
    result = [@all_targets[ k ]]
    (mid - 1).downto( 0 ).each { |i|    # backward search
      k = @sort_all_targets[ i ]
      break if !k.start_with? t
      result << @all_targets[ k.reverse ]
    }
    (mid + 1...max).each { |i|    # forward search
      k = @sort_all_targets[ i ]
      break if !k.start_with? t
      result << @all_targets[ k.reverse ]
    }
    return result
  end  # find_target

  # append appropriate extension to target name and, if we are linking statically,
  # prepend directory name 'static'.
  #
  # type -- one of :obj (compiler object), :lib (library file), or :exe (executable)
  # mm -- if true, only the 2-component version number (major.minor) is used,
  #       otherwise all 3 used
  #
  def add_ext name, type = :obj, mm = false
    bt = @build_type.to_s
    ext = case type
          when :obj then        # foo.o_dbg, foo.o_opt, ...
            'o_' + bt

          when :exe then        # foo.dbg_d, foo.dbg_s, ...
            bt + (:dynamic == @link_type ? '_d' : '_s')

          when :lib then        # libFoo.3.2.1.dylib_dbg, libFoo.3.2.1.so_opt, ...

            # e will be 'a', 'dylib', or 'so'
            e = :static == @link_type ? 'a' : (@@system.darwin? ? 'dylib' : 'so')

            # finally this yields: 3.2.1 or 3.2 (or the empty string if no version is
            # is available), a dot, and 'dylib_dbg', 'so_opt' etc.
            #
            defined?( @version ) ? "#{mm ? @v_lib : @version}.#{e}_#{bt}"
                                 : "#{e}_#{bt}"

          else raise "Bad object type: %s for %s" % [type, name]
          end  # case
    name + '.' + ext
  end  # add_ext

  def add_static name    # add 'static' subdirectory before file name
    dirname = File.dirname name
    return File.join( 'static', name ) if '.' == dirname
    File.join dirname, 'static', File.basename( name )
  end  # add_static

  # return list of target objects matching input list of names
  # type -- indicates the type of objects the names denote (with appropriate
  #         suffix _dbg, _rel, or _opt):
  #   :obj  --> compiler/assembler object file
  #   :lib  --> library file (static or dynamic depending on @link_type)
  #
  def names_to_objects names, type = :obj
    names.map{ |s|          # add version, extension then look it up
      name = add_ext s, type

      # static objects are in the 'static' subdirectory
      name = add_static name if :static == @link_type && :obj == type

      t = find_target name
      raise "No target for #{name}" if !t
      raise "Multiple targets for #{name}" if t.size > 1
      #Build.logger.debug "Found target %s for name %s" % [t[0].path, name]
      t.first
    }
  end  # names_to_objects

  # create and return target object for a single library
  #
  # Argument is a hash with these keys:
  # name   -- name of library excluding extension
  # files  -- dependencies: list of object file targets
  # libs   -- dependencies: list of library file targets (may be nil)
  #
  def lib_target args
    # We adjust args slightly and pass it on. Add one of these for dynamic libs:
    # soname -- soname of library (non-OSX only)
    # install_name -- install_name of library (OSX only)

    # If the version is defined, the file name will have all 3 components of the version
    # number but the soname will only have major.minor (executables compiled against this
    # library will have the soname embedded so this ensures that the library can be
    # upgraded without affecting those executables).
    #
    # If no version is available, obviously none of this applies.
    #
    # Append major.minor.patch version numbers and extension to library name
    # and prepend path
    #
    name = add_ext args[ :name ], :lib
    args[ :path ] = File.join( @obj_root, 'lib', name )

    if :dynamic == @link_type    # soname etc. only for dynamic libs
      if @@system.darwin?
        # special case --
        # 1. path and install_name are identical absolute paths
        # 2. We use all 3 version components in the actual path name but only the major
        #    and minor numbers in the install_name; finally, suitable symbolic links
        #    are created. For example, for debug build of library libFoo we will have:
        #    + path = /var/tmp/brubuild/foo/lib/libFoo.3.2.1.dylib_dbg
        #    + install_name = @rpath/../lib/libFoo.3.2.dylib
        #    + symbolic link in the lib directory:
        #        libFoo.3.2.dylib --> libFoo.3.2.1.dylib_dbg
        # 3. Applications that will be installed in the 'bin' directory next to 'lib' will
        #    need to link with "-Wl,-rpath,@loader_path/../lib"

        # add :install_name to args
        # add suitable extension including 2-component version
        lib_name = add_ext( args[ :name ], :lib, true )
        args[ :install_name ] = File.join( '@rpath', '..', 'lib', lib_name )

      else

        # add :soname to args
        # add suitable extension including 2-component version
        lib_name = add_ext( args[ :name ], :lib, true )
        args[ :soname ] = lib_name
      end
    end

    args[ :build ] = self

    # replace dependency lists with lists of corresponding objects

    # object files
    files = args[ :files ]
    raise "File list missing" if !files
    raise "Expected Array, got String" if files.is_a?( String )
    raise "File list empty" if files.empty?
    args[ :deps ] = names_to_objects files

    # libraries
    libs = args[ :libs ]
    if libs
      raise "Expected Array, got String" if libs.is_a?( String )
      args[ :libs ] = names_to_objects( libs, :lib ) if libs
    end

    Build.logger.debug "Creating library target %s" % args[ :path ]
    return LibFileTarget.new args
  end  # lib_target

  # create and return executable file target for a single executable
  #
  # Argument is a hash with these keys:
  # name   -- name of executable excluding extension
  # files  -- dependencies: list of object file targets
  # libs   -- dependencies: list of library file targets (may be nil)
  #
  def exe_target args
    # We adjust args slightly and pass it on

    # append appropriate extension to executable name and attach path:
    #   foo.dbg_d -- debug, dynamically linked
    #   foo.dbg_s -- debug, static linked
    # etc.
    #
    name = args[ :name ]
    raise "Missing :name key; files = %s" % args[ :files ] if !name
    name = add_ext name, :exe
    args[ :path ] = File.join( @obj_root, 'bin', name )
    args[ :build ] = self

    # replace dependency lists with lists of corresponding objects
    args[ :deps ] = names_to_objects( args[ :files ] )
    libs = args[ :libs ]
    args[ :libs ] = names_to_objects( libs, :lib ) if libs

    Build.logger.debug "Creating executable target %s" % args[ :path ]
    return ExecFileTarget.new args
  end  # exe_target

  # helper routine to return list of target objects for deleting or adding options after
  # checking arguments
  #
  def get_targets args
    tlist = args[ :targets ]
    raise "Missing target list"  if !tlist
    raise "Empty target list" if tlist.empty?
    t_type = args[ :target_type ]
    raise "Missing target_type" if !t_type
    raise "Bad target type: #{t_type}" if ![:obj, :lib, :exe].include? t_type
    opt = args[ :options ]
    raise "Missing options" if !opt
    raise "Empty options"   if opt.empty?
    result = []
    tlist.each{ |name|
      name.strip!
      raise "Target name empty" if name.empty?

      # add version and extension if necessary (user may supply the full name
      # such as libFoo.3.2.1.so_dbg or just the prefix 'libFoo')
      #
      ext = File.extname name
      raise "Please omit extension in name (it will be computed): #{name}" if !ext.empty?
      name = add_ext name, t_type

      target = find_target name
      raise "Target #{name} not found" if !target
      raise "Target #{name} not unique" if target.size > 1
      result << target.first
    }
    return result
  end  # get_targets

  # delete options of specified type from given target; args is a hash with these keys:
  #   targets  -- array of target names
  #   target_type  -- type of target (:obj, :lib, :exe) [required]
  #   options -- array of option strings to delete [required]
  #   option_type    -- type of options (:cpp) [optional]
  #              required only when adding pre-processor options to assembler, C and C++
  #              targets and should be :cpp in those cases; in other cases, it is
  #              deduced from target type.
  #   err     -- if false, no exception is raised if option is not found; default is
  #              true [optional]
  #
  def delete_target_options args
    get_targets( args ).each{ |t| t.delete_options args }
  end  # delete_target_options

  # add options of specified type to given target; args is a hash with these keys:
  #   targets  -- array of target names
  #   target_type  -- type of target (:obj, :lib, :exe) [required]
  #   options -- array of option strings to add [required]
  #   option_type    -- type of options (:cpp) [optional]
  #              required only when adding pre-processor options to assembler, C and C++
  #              targets and should be :cpp in those cases; in other cases, it is
  #              deduced from target type.
  #   replace -- if false, an exception is raised if an existing option conflicts with
  #              new options; if true, such conflicting options are removed; default is
  #              false [optional]
  #
  def add_target_options args
    get_targets( args ).each{ |t| t.add_options args }
  end  # add_target_options

  # recursive helper routine -- this should be removed and the relevant code fragments
  # moved into respective classes; do later
  #
  def target_deps tgt

    # add target to the redundant list for later removal if it is:
    #  + not the current search root; and
    #  + a top-level target
    #  + not already in redundant list
    #
    if (tgt != @top) && @targets.include?( tgt ) && !@redundant.include?( tgt )
      @redundant << tgt
      msg = ("Top-level target %s ignored since it will be built as a dependency of " +
             "another: %s") % [tgt.path, @top.path]
      @@logger.warn msg
    end

    if tgt.visit    # already processed
      # if we reach a target a second time before finishing it, we have a circular
      # dependency
      #
      raise "Circular dependency: #{tgt.path}" if :finish != tgt.visit
      return
    end

    @@logger.debug "Processing dependencies of target: %s, deps.size = %d ..." %
      [tgt.path, tgt.deps.size]
    case tgt.class.name
    when /SourceFileTarget$/o then
      # these have no dependencies, so just make sure mtime is defined
      tgt.make if tgt.cmd               # if generation command present, run it
      raise "No mtime for #{tgt.path}" if !tgt.mtime
      tgt.visit = :finish
      @t_groups[ :src ] << tgt

    when /ObjFileTargetAS$/o then
      tgt.visit = :start
      @t_groups[ :as ] << tgt
      src = tgt.deps[ 0 ]
      target_deps src if !src.visit      # recursive call on source file
      # currently we have no assembler files which include header files
      tgt.no_hdr_deps = true
      tgt.visit = :finish

    when /ObjFileTarget(C|CXX)$/ then
      which = $1
      tgt.visit = :start
      @t_groups[ ('C' == which) ? :cc : :cxx ] << tgt
      src = tgt.deps[ 0 ]
      target_deps src if !src.visit      # recursive call on source file

      # discover header file deps if not already done; we expect that the source file
      # will be the only dependency and @no_hdr_deps will not be set
      #
      raise "Anomaly: #{tgt.path}: deps.size = #{tgt.deps.size}" if
        1 != tgt.deps.size || tgt.no_hdr_deps

      # Add task for thread pool. No need to set @enqueued since we will never enqueue
      # the same target twice since tgt.visit is defined.
      #
      @thr_pool.add Task.new tgt, :discover_deps

      # We use negative counts here since worker threads will commence as soon as tasks
      # are enqueued so we want the comparison of the enqueued count and done count in
      # discover_deps to fail until the main thread finishes enqueuing all tasks.
      #
      # We may need to synchronize access to this variable, since worker threads are
      # reading it while we are writing it; do later if necessary
      #
      @deps_enq_cnt -= 1
      tgt.visit = :finish

    when /(Lib|Exec)FileTarget$/o then
      which = $1
      tgt.visit = :start
      @t_groups[ ('Lib' == which) ? :lib : :exe ] << tgt

      # recursive call on all dependencies
      tgt.deps.each { |d| target_deps d }
      tgt.libs.each { |d| target_deps d } if tgt.libs

      tgt.visit = :finish

    else raise "Bad target: %s (%s)" % [tgt.class.name, tgt.path]
    end  # case

    @@logger.debug "... finished dependencies of target: %s, deps.size = %d ..." %
      [tgt.path, tgt.deps.size]
  end  # target_deps

  # add header file dependencies to all object file targets reachable from a top-level
  # target
  #
  def discover_deps
    log = Build.logger

    # list of targets that may need building, separated by type (found by following
    # dependencies of top-level targets)
    #
    @t_groups = {
      :src => [], :as => [], :cc => [], :cxx => [], :lib => [], :exe => [],
    }
    log.debug "Discovering header file dependencies ..."

    # @redundant -- holds top-level targets that are redundant due to being dependencies
    #               of other top-level targets
    #
    @redundant = Set[]
    @targets.each { |tgt|
      next if @redundant.include? tgt
      raise "Top-level target %s already visited but not in @redundant" % tgt.path if
        tgt.visit

      # this allows us, when we discover a redundant top-level target T, to print the
      # name of the top-level target of which T is a dependency
      #
      @top = tgt

      target_deps tgt
    }
    if !@redundant.empty?    # remove redundant targets
      before = @targets.size
      @targets -= @redundant
      msg = ("Removed %d redundant targets from top-level list, @targets.size: " +
             "%d --> %d") % [@redundant.size, before, @targets.size]
      log.info msg
    end

    # wait for dependency discovery tasks to complete
    @lock.synchronize {
      # enqueued task count is negative, so negate it
      @deps_enq_cnt = -@deps_enq_cnt

      # in the unlikely but possible case that all enqueued tasks are done, no need to
      # wait
      #
      if @deps_enq_cnt == @deps_done_cnt
        log.info "All dependency discovery tasks already done, no need to wait"
      else
        # wait on condition variable until it is signalled by a thread indicating that
        # dependency tasks have completed
        # might need to add "... until @needs.empty?" here if we get spurious signals
        #
        @done.wait @lock
        raise "Spurious signal: enqueued count (%d) != completed count (%d)" %
          [@deps_enq_cnt, @deps_done_cnt] if @deps_enq_cnt != @deps_done_cnt
        log.info "Got signal: dependency dicovery tasks completed."
      end
    }  # synchronize

    # Convert list of header file names into objects and add to @deps;
    # this needs to be single threaded since it reads/modifies global target list
    # Add "@t_groups[ :as ] + " if necessary; currently, we assume assembler files do
    # not have included header files.
    #
    list = @t_groups[ :cc ] + @t_groups[ :cxx ]
    list.map( &:hdrs_to_deps )

    # remove the transient field @visit in each target; we'll get an exception if the
    # field does not exist
    #
    # This may be useful later so we no longer remove it
    # @t_groups.each_value{ |list| list.map( &:remove_visit ) }

    log.debug "... done discovering header file dependencies"
  end  # discover_deps

  def persist    # save data to DB if necessary
    log = @@logger
    if !defined? @db
      log.info "Persistence disabled, skipping"
      return
    end
    if @stats.histogram_time.item_count.zero?
      log.info "Persistence skipped since no objects were built"
      return
    end

    # persistence enabled, so persist globals and each target
    @db.persist_globals
    [:as, :cc, :cxx, :lib, :exe].each { |k|
      @t_groups[ k ].each{ |t| @db.persist_target t }
    }
  end  # persist

  # start of the parallel builder
  def go    # build targets that need it; call after discover_deps and pre_build_check
    log = Build.logger
    # t_groups should now be defined and all source files should exist

    @needs = Set[]    # top-level targets that are out-of-date

    # Do all this inside the mutex lock since threads will start processing jobs as soon
    # as they are enqueued and then may try to signal @done before the main thread is
    # actually waiting for it thus losing the signal (a remote contingency).
    #
    STDERR.sync = true    # flush output immediately
    @lock.synchronize {
      # find out-of-date targets and set @needs and @needed_by fields of each target
      @targets.each { |tgt|
        if !tgt.out_of_date?
          log.info "Skipping %s since it is already current" % tgt.path
          next
        end
        
        # tgt is out of date, so add it to build.needs and set tgt.needed_by to :top;
        #
        @needs << tgt
        raise "Target %s already has needed_by set" if tgt.needed_by
        tgt.needed_by = :top

        # if it has no out-of-date dependencies add this task to thread pool; if it does,
        # it will automatically be added when the dependencies are made
        #
        if !defined? tgt.needs
          # would not normally happen since top-level targets are usually libraries or
          # executables which need other object files; but could happen in some
          # circumstances, e.g.
          # -- user specifies object files explicitly as top-level targets
          # -- an executable or library file was deleted but nothing else changes; in
          #    this case, only the link step is needed since all dependencies are current
          #
          log.info "Adding top-level target %s to queue" % tgt.path
          @thr_pool.add Task.new( tgt, :make )    # enqueue task
          tgt.enqueued = true
        end
      }  # targets
      if @needs.empty?    # all top-level targets are current; nothing to do
        log.info "All %d top-level targets are current, exiting" % @targets.size
        exit
      end
      log.info "%d out of %d top-level targets are out-of-date" %
        [@needs.size, @targets.size]

      # add all out-of-date assembler and compiler targets to the queue
      list = @t_groups[ :as ] + @t_groups[ :cc ] + @t_groups[ :cxx ]
      cnt_objs = list.size    # no. of object files that might be out-of-date

      list.select!{ |tgt| tgt.out_of_date? }
      cnt_ood = list.size    # no. of object files that _are_ out-of-date

      if cnt_ood.zero?
        log.info "All %d object files are current" % cnt_objs
      else
        if cnt_ood == cnt_objs
          log.info "Building all %d objects" %  cnt_objs
        else    # cnt_ood < cnt_objs
          log.info "Building %d objects out of %d" % [cnt_ood, cnt_objs]
        end
        list.each_with_index { |tgt, i|
          log.debug "%d: Adding %s to task queue" % [i, tgt.path]
          @thr_pool.add Task.new( tgt, :make )    # enqueue task
          tgt.enqueued = true
        }
      end

      # There is a subtle point here:
      # Any out-of-date libraries and executable targets that have out-of-date object
      # file (_not_ libraries) dependencies will be enqueued when all those objects have
      # been built. But if they have no such dependencies, we need to enqueue them here
      # because they will never get added otherwise.
      #
      # Enqueue any out-of-date libraries and executable targets if they:
      # -- are out-of-date; and
      # -- have not already been enqueued; and
      # -- have no out-of-date dependencies;
      # need to do this because we could have scenarios like this:
      #
      # (a) Top-level target libA depends on libB
      # (b) libB is not a top-level target and has no out-of-date dependencies
      # (c) libB is itself out-of-date (e.g. the file was deleted).
      #
      # 1. In this case, libA will not be added to the queue in the top-level target loop
      #    above since its @needs field will contain libB;
      # 2. libB will never be enqueued because it is not a top-level target and none of
      #    its dependencies will be made (because they are all current).
      # 3. Because of 2, libA will never be enqueued
      #
      list = @t_groups[ :lib ] + @t_groups[ :exe ]
      cnt_objs = list.size    # no. of linker files that might be out-of-date

      list.select!{ |tgt| tgt.out_of_date? }
      cnt_ood = list.size    # no. of linker files that _are_ out-of-date

      list.select!{ |tgt|
        b1, b2 = tgt.enqueued, tgt.needs
        log.debug "%s not enqueued since it is already enqueued" % tgt.path if b1
        if b2
          log.debug "%s not enqueued since tgt.needs is defined:" % tgt.path
          tgt.needs.each_with_index{ |t, i| log.debug "%6d: %s" % [i, t.path] }
        end
        !b1 && !b2
      }
      cnt_enq = list.size    # no. of linker files that need to be enqueued

      # print meaningful messages
      if cnt_ood.zero?
        log.info "All %d linker objects are current" % cnt_objs
      elsif cnt_ood == cnt_objs
        log.info "All %d linker objects are out-of-date and will be built" %  cnt_objs
      else    # cnt_ood < cnt_objs
        log.info "%d linker objects out of %d are out-of-date and will be built" %
          [cnt_ood, cnt_objs]
      end

      if cnt_enq.zero?
        log.info "No linker objects need to be enqueued directly"
      else
        log.info "%d linker objects need to be enqueued directly" % cnt_enq
        list.each_with_index { |tgt, i|
          log.debug "%d: Adding %s to task queue" % [i, tgt.path]
          @thr_pool.add Task.new( tgt, :make )    # enqueue task
          tgt.enqueued = true
        }
      end

      # sanity checks -- threads can dequeue tasks as soon as they are enqueued so there
      # is a small probablility that all enqueued tasks have been dequeued by worker
      # threads and so the queue is empty by the time we get here.
      #
      cnt = @thr_pool.tasks.size
      log.warn "Task queue empty: Enqueued tasks completed very quickly!" if cnt.zero?
      raise "Unexpected: @needs is empty" if @needs.empty?
      Util.print_status cnt

      # wait on condition variable until it is signalled by a thread indicating that
      # all needed targets have been built, i.e. @needs is empty
      # might need to add "... until @needs.empty?" here if we get spurious signals
      #
      @done.wait @lock
      raise "Spurious signal: @needs not empty: [%s ...]" % @needs.first if
        !@needs.empty?

    }  # @lock.synchronize

    # shutdown thread pool
    STDERR.puts "\nShutting down thread pool ..."
    @thr_pool.close
    STDERR.puts 'Build finished'

    # save stuff to DB if necessary
    persist

    # let this be the last thing in the log file
    @stats.dump    # print statistics to log file
    log.info "Build finished"
  end  # go

end  # Build