source/dependency.cc

   1 #include "tag-parser.hh"
   2 #include "utility/File.cc"
   3 #include <map>
   4 #include <sstream>
   5 #include <algorithm>
   6
   7 // todo: const correctness
   8
   9 class PkgNode
  10 {
  11 public:
  12   typedef std::vector <std::string> DependencyVector;
  13   typedef DependencyVector::iterator iterator;
  14
  15   PkgNode (std::string i_name)
  16   {
  17     name = i_name;
  18     priority = -1;
  19   }
  20
  21   iterator Begin () {return depend.begin();}
  22   iterator End () {return depend.end();}
  23
  24   void AddDependency (const std::string& dep) {depend.push_back(std::string(dep));}
  25
  26   const std::string& Name () {return name;}
  27
  28   int Priority () {return priority;}
  29
  30 private:
  31   friend class PkgGraph;
  32
  33   std::string name;
  34   DependencyVector depend;
  35   int priority; // -1 = not evaluated yet; -2 = in evaluation;
  36 };
  37
  38 class PkgGraph : public std::map <std::string, PkgNode*>
  39 {
  40 public: // TODO: duplication checking !!
  41   void AddPkg (PkgNode* pkg) { (*this)[pkg-> Name()] = pkg; }
  42
  43   typedef std::map <std::string, PkgNode*>::iterator iterator;
  44
  45   int GetPriority (const std::string& pkgname)
  46   {
  47     iterator pi = find(pkgname);
  48     if (pi == end()) {
  49       std::cerr << "Warning: could not find package '" << pkgname << "'" << std::endl;
  50       return 0;
  51     }
  52
  53     PkgNode& node = *(pi -> second);
  54     if (node.priority == -2) {
  55       std::cerr << "Warning: circular dependency detected involving package '"
  56                 << pkgname << "'" << std::endl;
  57        node.priority = 0;
  58     } else if (node.priority == -1) {
  59       int new_priority = 0;
  60       node.priority = -2;
  61       for (PkgNode::iterator i = node.Begin(); i != node.End(); i++)
  62         new_priority = std::max (new_priority, GetPriority(*i));
  63       node.priority = new_priority + 1;
  64     }
  65     return node.priority;
  66   }
  67
  68 } pkg_graph;
  69
  70
  71 class CacheFile : public TagParser
  72 {
  73 public:
  74
  75   CacheFile ()
  76     : copyright("COPY","",""),
  77
  78       timestamp("TIMESTAMP","",""),
  79       config_id("CONFIG-ID","",""),
  80       version("ROCKVER","",""),
  81
  82       logs("LOGS","",""),
  83
  84       buildtime("BUILDTIME","",""),
  85       size("SIZE","",""),
  86
  87       dep("DEP","",""),
  88
  89       error0("0-ERROR","",""),
  90       error1("1-ERROR","",""),
  91       error2("2-ERROR","",""),
  92       error3("3-ERROR","",""),
  93       error4("4-ERROR","",""),
  94       error5("5-ERROR","",""),
  95       error6("6-ERROR","",""),
  96       error7("7-ERROR","",""),
  97       error8("8-ERROR","",""),
  98       error9("9-ERROR","","")
  99   {
 100     tags.push_back(&copyright);
 101     tags.push_back(&timestamp);
 102     tags.push_back(&config_id);
 103     tags.push_back(&version);
 104     tags.push_back(&logs);
 105     tags.push_back(&buildtime);
 106     tags.push_back(&size);
 107     tags.push_back(&dep);
 108
 109     tags.push_back(&error0);
 110     tags.push_back(&error1);
 111     tags.push_back(&error2);
 112     tags.push_back(&error3);
 113     tags.push_back(&error4);
 114     tags.push_back(&error5);
 115     tags.push_back(&error6);
 116     tags.push_back(&error7);
 117     tags.push_back(&error8);
 118     tags.push_back(&error9);
 119   }
 120
 121   PkgNode* DepsFromFile(const std::string& pkgname, const std::string& file)
 122   {
 123     Clear ();
 124     if (!Parse (file))
 125       std::cerr << "warning: there were errors in the cache file of package '"
 126                 << pkgname << "'" << std::endl;
 127
 128     PkgNode* ret = new PkgNode (pkgname);
 129
 130     // split dep tag value into single tokens and add into PkgNode's Dependency vector.
 131     std::stringstream stream(dep.value);
 132     while (stream) {
 133       std::string s = "";
 134       stream >> s;
 135       if (s != "")
 136         ret -> AddDependency(s);
 137     }
 138
 139     return ret;
 140   }
 141
 142   Tag copyright;
 143
 144   Tag timestamp;
 145   Tag config_id;
 146   Tag version;
 147
 148   Tag logs;
 149
 150   Tag buildtime;
 151   Tag size;
 152
 153   Tag dep;
 154
 155   // Todo: replace those
 156   Tag error0;
 157   Tag error1;
 158   Tag error2;
 159   Tag error3;
 160   Tag error4;
 161   Tag error5;
 162   Tag error6;
 163   Tag error7;
 164   Tag error8;
 165   Tag error9;
 166
 167 } cache_file;
 168
 169
 170
 171 std::string PkgName (const std::string& file)
 172 {
 173   return Utility::File(file).BasenameWOExtension();
 174 }
 175
 176 class PriorityCmp
 177 {
 178 public:
 179   bool operator() (PkgNode* a, PkgNode* b)
 180   {
 181     return a->Priority() < b->Priority();
 182   }
 183 };
 184
 185 class DownArrow
 186 {
 187 public:
 188   DownArrow (unsigned int pkg_priority)
 189   {
 190     start = pkg_priority;
 191     end = pkg_priority;
 192   }
 193
 194   void SetNeed (unsigned int by_priority)
 195   {
 196     end = std::max(end, by_priority);
 197   }
 198
 199   // returns true iff a and this arrow can be drawn in the same column
 200   bool Compatible (const DownArrow& a)
 201   {
 202     return (a.start > end || a.end < start);
 203   }
 204
 205   unsigned int start;
 206   unsigned int end;
 207   unsigned int h_pos;
 208 };
 209
 210 std::map <std::string, DownArrow*> down_arrows;
 211 typedef std::map <std::string, DownArrow*>::iterator arrow_iterator;
 212
 213 void InsertAt(std::string& s, unsigned int char_pos, char c)
 214 {
 215   while (s.length() <= char_pos)
 216     s += " ";
 217   s[char_pos] = c;
 218 }
 219
 220 std::string Template (unsigned int v_pos)
 221 {
 222   arrow_iterator arr_end = down_arrows.end ();
 223   std::string ret = "";
 224
 225   for (arrow_iterator i = down_arrows.begin(); i != arr_end; i++) {
 226     if (i -> second -> start <= v_pos && i -> second -> end > v_pos)
 227       InsertAt(ret, 2*(i -> second -> h_pos), '|');
 228   }
 229
 230   return ret;
 231 }
 232
 233 std::string HRef (PkgNode& node, unsigned int v_pos)
 234 {
 235   std::string tmpl = Template(v_pos);
 236   arrow_iterator arr_end = down_arrows.end ();
 237
 238   unsigned int h_min = ((unsigned int) ((int) -1));
 239
 240   // comparism (1) is a workaround for those cross references
 241
 242   for (PkgNode::iterator dep_on = node.Begin(); dep_on != node.End(); dep_on++) {
 243     arrow_iterator arrow = down_arrows.find(*dep_on);
 244     if (arrow != arr_end && arrow -> second -> start < v_pos /* (1) */) {
 245       h_min = std::min (h_min, arrow -> second -> h_pos);
 246       InsertAt(tmpl, 2*(arrow -> second -> h_pos), '+');
 247     }
 248   }
 249
 250   arrow_iterator arrow = down_arrows.find(node.Name());
 251   if (arrow != arr_end) {
 252     h_min = std::min (h_min, arrow -> second -> h_pos);
 253     InsertAt(tmpl, 2*(arrow -> second -> h_pos), 'v');
 254   }
 255
 256   for (unsigned int i = 2*h_min; i < tmpl.length(); i++)
 257     if (tmpl[i] != 'v' && tmpl[i] != '+')
 258       tmpl[i]='-';
 259
 260   return tmpl;
 261 }
 262
 263
 264 void PrintGraph ()
 265 {
 266   std::vector <PkgNode*> needed;
 267
 268   for (PkgGraph::iterator i = pkg_graph.begin(); i != pkg_graph.end(); i++) {
 269     if (i -> second -> Priority () >= 0)
 270       needed.push_back (i -> second);
 271   }
 272
 273   // sort after priority
 274   std::sort (needed.begin(), needed.end(), PriorityCmp ());
 275
 276   arrow_iterator arr_end = down_arrows.end ();
 277
 278
 279
 280   // compute DownArrow lengh
 281   for (unsigned int i = 0; i < needed.size(); i++) {
 282     PkgNode& current = *(needed[i]);
 283     down_arrows[current.Name()] = new DownArrow (i);
 284     for (PkgNode::iterator dep_on = current.Begin(); dep_on != current.End(); dep_on++) {
 285       arrow_iterator arrow = down_arrows.find(*dep_on);
 286       if (arrow != arr_end)
 287         arrow -> second -> SetNeed(i);
 288     }
 289   }
 290
 291   // greedyly arrange DownArrows horizontaly
 292   for (unsigned int i = 0; i < needed.size(); i++) {
 293     arrow_iterator cur_assign = down_arrows.find(needed[i] -> Name());
 294
 295     unsigned int h_pos = 0;
 296     bool pos_found;
 297
 298     do {
 299       pos_found = true;
 300
 301       for (unsigned int j = 0; j < i ; j++) {
 302         arrow_iterator assigned = down_arrows.find(needed[j] -> Name());
 303         if (assigned -> second -> h_pos == h_pos)
 304           if (!(assigned -> second -> Compatible(*(cur_assign -> second))))
 305             pos_found = false;
 306       }
 307
 308       if (pos_found)
 309         cur_assign -> second -> h_pos = h_pos;
 310       else
 311         h_pos++;
 312     } while (!pos_found);
 313
 314   }
 315
 316   // Print the graph
 317   for (unsigned int i = 0; i < needed.size(); i++) {
 318     std::cout << HRef (*(needed[i]),i) << "---" << needed[i] -> Name() << std::endl
 319               << Template(i) << std::endl;
 320   }
 321 }
 322
 323
 324
 325 int main (int argc, char** argv)
 326 {
 327   if (argc < 3) {
 328     std::cerr << argv[0] << " <pkgs> <cachefile>+" << std::endl;
 329     exit (-1);
 330   }
 331
 332   std::string package(argv[1]);
 333   argv += 2;
 334   while (*argv) {
 335     pkg_graph.AddPkg(
 336           cache_file.DepsFromFile(
 337                  PkgName(*argv), std::string(*argv)));
 338     argv ++;
 339   }
 340
 341   pkg_graph.GetPriority (package);
 342
 343   PrintGraph();
 344 }