// depexpand.cxx

// David Adams
// January 20, 2005
//
// Expand a package dependency tree described by a collection of files.
// Each file lists its dependencies by naming other packages. The user
// supplies the base name for these files, a top level package name and
// a path to search for files. The location for a file is obtained by
// searching the path for the concatenation of the package name and
// basename.
//
// For example, if a user provided a basename of LIBDEPS, a package
// name mygroup/mypkg and a path with the single entry /home/dev, then
// file /home/dev/mygroup/mypkg/LIBDEPS would read, the package listed
// there to find more files, and so on recursively.

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <fstream>

using std::ostream;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::vector;
using std::list;
using std::ifstream;

namespace {

//**********************************************************************
// Local typedefs and classes.
//**********************************************************************

typedef vector<string> StringList;

//**********************************************************************

struct Pkg {
  string name;
  string fullpath;
  StringList pkgs;
  bool processed;
public:  // methods
  Pkg(string inname);
};

//**********************************************************************

typedef list<Pkg> PkgList;

//**********************************************************************

string findpkg(string pkg);

//**********************************************************************
// Local data.
//**********************************************************************

string pbasename;
StringList dirs;
bool debug_depexpand = false;

//**********************************************************************
// Local function declarations.
//**********************************************************************

// Find package pkg and return the full path to that package.
string findpkg(string pkg);

//**********************************************************************

// Print the package names from a package list.
// Those that are not processed are flagged.
// If the iterators are supplied, then those entries are marked.
ostream& print_names(const PkgList& pkgs, ostream& out);
ostream& print_names(const PkgList& pkgs, ostream& out,
                     PkgList::const_iterator ibad1);
ostream& print_names(const PkgList& pkgs, ostream& out,
                     PkgList::const_iterator ibad1,
                     PkgList::const_iterator ibad2);

//**********************************************************************
// Local method and function definitions.
//**********************************************************************

Pkg::Pkg(string inname) : name(inname), processed(false) {
  fullpath = findpkg(name);
  if ( fullpath.size() ) {
    string fname = fullpath + "/" + pbasename;
    ifstream fin(fname.c_str());
    while ( fin.good() ) {
      string pkg;
      fin >> pkg;
      if ( pkg.size() ) {
        pkgs.push_back(pkg);
      }
    }
  }
}

//**********************************************************************

string findpkg(string pkg) {
  for ( StringList::const_iterator idir=dirs.begin();
        idir!=dirs.end(); ++idir ) {
    string fname = *idir + "/" + pkg;
    ifstream fin(fname.c_str());
    if ( fin.good() ) return fname;
  }
  return "";
}

//**********************************************************************

ostream& print_names(const PkgList& pkgs, ostream& out) {
  return print_names(pkgs, out, pkgs.end(), pkgs.end());
}

ostream& print_names(const PkgList& pkgs, ostream& out,
                     PkgList::const_iterator ibad1) {
  return print_names(pkgs, out, ibad1, pkgs.end());
}

ostream& print_names(const PkgList& pkgs, ostream& out,
                     PkgList::const_iterator ibad1,
                     PkgList::const_iterator ibad2) {
  for ( PkgList::const_iterator ipkg=pkgs.begin();
        ipkg!=pkgs.end(); ++ipkg ) {
    string name = ipkg->name;
    bool proc = ipkg->processed;
    if ( name.size() ) {
      out << name;
    } else {
      out << "UNNAMED PACKAGE!!!";
    }
    if ( ! proc ) {
      out << " *";
    }
    if ( ipkg == ibad1 ) {
      out << " <---";
    }
    if ( ipkg == ibad2 ) {
      out << " <---";
    }
    out << endl;
  }
  return out;
}

}  // end unnamed namespace

//**********************************************************************
// Main program.
//**********************************************************************

int main(int argc, char* carg[]) {
  
  if ( argc < 4 ) {
    cout << "Usage: " << carg[0] << " DEPFILE PKGNAME DIR1 [DIR2 ...]"
         << endl;
    if ( argc == 2 && string(carg[1] ) == "-h" ) return 0;
    return 1;
  }

  pbasename = carg[1];
  string pkgname = carg[2];
  for ( int idir=3; idir<argc; ++idir ) {
    dirs.push_back(carg[idir]);
  }

  // Initialize package list with input package.
  Pkg toppkg(pkgname);
  if ( toppkg.fullpath.size() == 0 ) {
    cerr << "depexpand: Unable to find package " << pkgname
         << endl;
    return 2;
  }
  PkgList pkgs;
  pkgs.push_back(toppkg);

  // Expand package list.
  PkgList::iterator ipkg = pkgs.begin();
  while ( ipkg!=pkgs.end() ) {
    if ( debug_depexpand ) print_names(pkgs, cerr, ipkg) << endl;
    Pkg& pkg = *ipkg;
    // If already processed go to the next.
    if ( pkg.processed ) { ++ipkg; continue; }
    // Remove any duplicates later in the list.
    // If duplicate has been processed, assume circular dependency
    // and exit with error.
    PkgList::iterator kpkg=ipkg;
    ++kpkg;
    while ( kpkg!=pkgs.end() ) {
      PkgList::iterator oldkpkg = kpkg;
      ++kpkg;
      if ( oldkpkg->name == ipkg->name ) {
        if ( oldkpkg->processed ) {
          cerr << "depexpand: Circular dependency:" << endl;
          print_names(pkgs, cerr, ipkg, oldkpkg);
          cerr << "depexpand: Exiting with error" << endl;
          return 4;
        }
        pkgs.erase(oldkpkg);
      }
    }
    // Check the list of subpackages and insert here if not already
    // present earlier in the list. Processing continues with the
    // first insertion.
    StringList& names = pkg.pkgs;
    pkg.processed = true;
    for ( StringList::reverse_iterator inam=names.rbegin();
          inam!=names.rend(); ++inam ) {
      string sname = *inam;
      // Check if this is a duplicate.
      bool dup = false;
      for ( PkgList::const_iterator jpkg=pkgs.begin();
            jpkg!=ipkg; ++jpkg ) {
        if ( jpkg->name == sname ) { dup = true; break; }
      }
      // If not a duplicate, insert it.
      if ( ! dup ) {
        Pkg spkg(sname);
        if ( spkg.fullpath.size() == 0 ) {
          cerr << "depexpand: Unable to find subpackage " << sname
               << endl;
          return 3;
        }
        ipkg = pkgs.insert(ipkg, spkg);
        assert( ipkg != pkgs.end() );
      }
    }
  }

  // Remove the original entry.
  bool remove_original = false;
  if ( remove_original ) {
    ipkg = pkgs.end();
    --ipkg;
    assert( ipkg != pkgs.end() );
    assert( ipkg->name == toppkg.name );
    pkgs.erase(ipkg);
  }

  // Write out the package names.
  print_names(pkgs, cout);

  return 0;
}