aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-14 14:10:59 +0100
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-14 14:10:59 +0100
commit0bb25e053b1ef2e7943340ff0bb684fae40ad13b (patch)
treefe4658cea6f116c3d2de565728f6f648e48879e2
parente0dc10d364802bee37e19a8468002d61e358cb43 (diff)
downloadpaludis-0bb25e053b1ef2e7943340ff0bb684fae40ad13b.tar.gz
paludis-0bb25e053b1ef2e7943340ff0bb684fae40ad13b.tar.xz
Track edge properties
-rw-r--r--paludis/resolver/lineariser.cc10
-rw-r--r--paludis/resolver/nag-fwd.hh1
-rw-r--r--paludis/resolver/nag.cc49
-rw-r--r--paludis/resolver/nag.hh22
4 files changed, 57 insertions, 25 deletions
diff --git a/paludis/resolver/lineariser.cc b/paludis/resolver/lineariser.cc
index 56c55d5..c41156c 100644
--- a/paludis/resolver/lineariser.cc
+++ b/paludis/resolver/lineariser.cc
@@ -31,6 +31,7 @@
#include <paludis/util/stringify.hh>
#include <paludis/util/hashes.hh>
#include <paludis/util/join.hh>
+#include <paludis/util/make_named_values.hh>
#include <paludis/environment.hh>
#include <paludis/notifier_callback.hh>
#include <tr1/unordered_set>
@@ -245,7 +246,10 @@ namespace
(*l)->accept(classifier);
if (classifier.build || classifier.run)
- nag->add_edge(r.from_resolvent(), resolvent);
+ nag->add_edge(r.from_resolvent(), resolvent, make_named_values<NAGEdgeProperties>(
+ n::build() = classifier.build,
+ n::run() = classifier.run
+ ));
else if (classifier.post)
{
/* we won't add a backwards edge, since most post deps dep upon
@@ -359,8 +363,8 @@ Lineariser::resolve()
* change or remove nodes */
for (NAG::EdgesFromConstIterator e(_imp->nag->begin_edges_from(*r)), e_end(_imp->nag->end_edges_from(*r)) ;
e != e_end ; ++e)
- if (changes_in_scc.end() != changes_in_scc.find(*e))
- scc_nag.add_edge(*r, *e);
+ if (changes_in_scc.end() != changes_in_scc.find(e->first))
+ scc_nag.add_edge(*r, e->first, e->second);
}
scc_nag.verify_edges();
diff --git a/paludis/resolver/nag-fwd.hh b/paludis/resolver/nag-fwd.hh
index 495cceb..3ebc41e 100644
--- a/paludis/resolver/nag-fwd.hh
+++ b/paludis/resolver/nag-fwd.hh
@@ -25,6 +25,7 @@ namespace paludis
namespace resolver
{
struct NAG;
+ struct NAGEdgeProperties;
}
}
diff --git a/paludis/resolver/nag.cc b/paludis/resolver/nag.cc
index c9d370f..50dd250 100644
--- a/paludis/resolver/nag.cc
+++ b/paludis/resolver/nag.cc
@@ -40,7 +40,9 @@ using namespace paludis;
using namespace paludis::resolver;
typedef std::tr1::unordered_set<Resolvent, Hash<Resolvent> > Nodes;
-typedef std::tr1::unordered_map<Resolvent, Nodes, Hash<Resolvent> > Edges;
+typedef std::tr1::unordered_map<Resolvent, NAGEdgeProperties, Hash<Resolvent> > NodesWithProperties;
+typedef std::tr1::unordered_map<Resolvent, NodesWithProperties, Hash<Resolvent> > Edges;
+typedef std::tr1::unordered_map<Resolvent, Nodes, Hash<Resolvent> > PlainEdges;
namespace paludis
{
@@ -55,12 +57,13 @@ namespace paludis
{
Nodes nodes;
Edges edges;
+ const NodesWithProperties empty_nodes_with_properties;
};
template <>
struct WrappedForwardIteratorTraits<NAG::EdgesFromConstIteratorTag>
{
- typedef Nodes::const_iterator UnderlyingIterator;
+ typedef NodesWithProperties::const_iterator UnderlyingIterator;
};
}
@@ -80,9 +83,9 @@ NAG::add_node(const Resolvent & r)
}
void
-NAG::add_edge(const Resolvent & a, const Resolvent & b)
+NAG::add_edge(const Resolvent & a, const Resolvent & b, const NAGEdgeProperties & p)
{
- _imp->edges.insert(std::make_pair(a, Nodes())).first->second.insert(b);
+ _imp->edges.insert(std::make_pair(a, NodesWithProperties())).first->second.insert(std::make_pair(b, p)).first->second |= p;
}
void
@@ -94,10 +97,10 @@ NAG::verify_edges() const
if (_imp->nodes.end() == _imp->nodes.find(e->first))
throw InternalError(PALUDIS_HERE, "Missing node for edge " + stringify(e->first));
- for (Nodes::const_iterator f(e->second.begin()), f_end(e->second.end()) ;
+ for (NodesWithProperties::const_iterator f(e->second.begin()), f_end(e->second.end()) ;
f != f_end ; ++f)
- if (_imp->nodes.end() == _imp->nodes.find(*f))
- throw InternalError(PALUDIS_HERE, "Missing node for edge " + stringify(e->first) + " -> " + stringify(*f));
+ if (_imp->nodes.end() == _imp->nodes.find(f->first))
+ throw InternalError(PALUDIS_HERE, "Missing node for edge " + stringify(e->first) + " -> " + stringify(f->first));
}
}
@@ -129,16 +132,16 @@ namespace
Edges::const_iterator e(edges.find(node));
if (e != edges.end())
{
- for (Nodes::const_iterator n(e->second.begin()), n_end(e->second.end()) ;
+ for (NodesWithProperties::const_iterator n(e->second.begin()), n_end(e->second.end()) ;
n != n_end ; ++n)
{
- TarjanDataMap::iterator n_data(data.find(*n));
+ TarjanDataMap::iterator n_data(data.find(n->first));
if (data.end() == n_data)
{
- n_data = tarjan(*n, edges, data, stack, index, result);
+ n_data = tarjan(n->first, edges, data, stack, index, result);
node_data->second.lowlink() = std::min(node_data->second.lowlink(), n_data->second.lowlink());
}
- else if (stack.end() != std::find(stack.begin(), stack.end(), *n))
+ else if (stack.end() != std::find(stack.begin(), stack.end(), n->first))
node_data->second.lowlink() = std::min(node_data->second.lowlink(), n_data->second.index());
}
}
@@ -164,14 +167,14 @@ namespace
void dfs(
const StronglyConnectedComponentsByRepresentative & sccs,
const Resolvent & node,
- const Edges & edges,
+ const PlainEdges & edges,
Nodes & done,
std::tr1::shared_ptr<SortedStronglyConnectedComponents> & result)
{
if (done.end() != done.find(node))
return;
- Edges::const_iterator e(edges.find(node));
+ PlainEdges::const_iterator e(edges.find(node));
std::set<Resolvent> consistently_ordered_edges;
if (e != edges.end())
std::copy(e->second.begin(), e->second.end(), std::inserter(consistently_ordered_edges, consistently_ordered_edges.begin()));
@@ -213,15 +216,15 @@ NAG::sorted_strongly_connected_components() const
throw InternalError(PALUDIS_HERE, "mismatch");
/* build edges between SCCs */
- Edges scc_edges;
+ PlainEdges scc_edges;
for (Edges::const_iterator e(_imp->edges.begin()), e_end(_imp->edges.end()) ;
e != e_end ; ++e)
{
RepresentativeNodes::const_iterator from(representative_nodes.find(e->first));
- for (Nodes::const_iterator n(e->second.begin()), n_end(e->second.end()) ;
+ for (NodesWithProperties::const_iterator n(e->second.begin()), n_end(e->second.end()) ;
n != n_end ; ++n)
{
- RepresentativeNodes::const_iterator to(representative_nodes.find(*n));
+ RepresentativeNodes::const_iterator to(representative_nodes.find(n->first));
if (! (to->second == from->second))
scc_edges.insert(std::make_pair(from->second, Nodes())).first->second.insert(to->second);
}
@@ -250,7 +253,7 @@ NAG::begin_edges_from(const Resolvent & r) const
{
Edges::const_iterator e(_imp->edges.find(r));
if (e == _imp->edges.end())
- return EdgesFromConstIterator(_imp->nodes.end());
+ return EdgesFromConstIterator(_imp->empty_nodes_with_properties.end());
else
return EdgesFromConstIterator(e->second.begin());
}
@@ -260,10 +263,18 @@ NAG::end_edges_from(const Resolvent & r) const
{
Edges::const_iterator e(_imp->edges.find(r));
if (e == _imp->edges.end())
- return EdgesFromConstIterator(_imp->nodes.end());
+ return EdgesFromConstIterator(_imp->empty_nodes_with_properties.end());
else
return EdgesFromConstIterator(e->second.end());
}
-template class WrappedForwardIterator<NAG::EdgesFromConstIteratorTag, const Resolvent>;
+NAGEdgeProperties &
+NAGEdgeProperties::operator|= (const NAGEdgeProperties & other)
+{
+ build() |= other.build();
+ run() |= other.run();
+ return *this;
+}
+
+template class WrappedForwardIterator<NAG::EdgesFromConstIteratorTag, const std::pair<const Resolvent, NAGEdgeProperties> >;
diff --git a/paludis/resolver/nag.hh b/paludis/resolver/nag.hh
index c5c7b2d..5b85e3f 100644
--- a/paludis/resolver/nag.hh
+++ b/paludis/resolver/nag.hh
@@ -25,12 +25,27 @@
#include <paludis/resolver/strongly_connected_component-fwd.hh>
#include <paludis/util/private_implementation_pattern.hh>
#include <paludis/util/wrapped_forward_iterator.hh>
+#include <paludis/util/named_value.hh>
#include <tr1/memory>
namespace paludis
{
+ namespace n
+ {
+ typedef Name<struct build_name> build;
+ typedef Name<struct run_name> run;
+ }
+
namespace resolver
{
+ struct NAGEdgeProperties
+ {
+ NamedValue<n::build, bool> build;
+ NamedValue<n::run, bool> run;
+
+ NAGEdgeProperties & operator|= (const NAGEdgeProperties &);
+ };
+
class NAG :
private PrivateImplementationPattern<NAG>
{
@@ -39,7 +54,7 @@ namespace paludis
~NAG();
void add_node(const Resolvent &);
- void add_edge(const Resolvent &, const Resolvent &);
+ void add_edge(const Resolvent &, const Resolvent &, const NAGEdgeProperties &);
void verify_edges() const;
@@ -47,13 +62,14 @@ namespace paludis
sorted_strongly_connected_components() const PALUDIS_ATTRIBUTE((warn_unused_result));
struct EdgesFromConstIteratorTag;
- typedef WrappedForwardIterator<EdgesFromConstIteratorTag, const Resolvent> EdgesFromConstIterator;
+ typedef WrappedForwardIterator<EdgesFromConstIteratorTag, const std::pair<const Resolvent, NAGEdgeProperties> > EdgesFromConstIterator;
EdgesFromConstIterator begin_edges_from(const Resolvent &) const PALUDIS_ATTRIBUTE((warn_unused_result));
EdgesFromConstIterator end_edges_from(const Resolvent &) const PALUDIS_ATTRIBUTE((warn_unused_result));
};
}
- extern template class WrappedForwardIterator<resolver::NAG::EdgesFromConstIteratorTag, const resolver::Resolvent>;
+ extern template class WrappedForwardIterator<resolver::NAG::EdgesFromConstIteratorTag,
+ const std::pair<const resolver::Resolvent, resolver::NAGEdgeProperties> >;
}
#endif