# # # patch "rcs_import.cc" # from [9e30084b479eb1def40928b3e79142850a64a147] # to [972da75872c33e6f9b52df88f7ad0df665e9a4db] # ============================================================ --- rcs_import.cc 9e30084b479eb1def40928b3e79142850a64a147 +++ rcs_import.cc 972da75872c33e6f9b52df88f7ad0df665e9a4db @@ -2512,6 +2512,229 @@ public: I(!a_has_branch); I(!b_has_branch); + // the streamliner will handle this case later on. + } + } + + void back_edge(Edge e) + { +#ifdef DEBUG_GRAPHVIZ + set blobs_to_show; + + blobs_to_show.insert(e.first); + blobs_to_show.insert(e.second); + + write_graphviz_partial(cvs, "invalid_back_edge", blobs_to_show, 5); +#endif + + L(FL("branch_sanitizer: back edge from blob %d (%s) to blob %d (%s) - ABORTING!") + % e.first % get_event_repr(cvs, *cvs.blobs[e.first].begin()) + % e.second % get_event_repr(cvs, *cvs.blobs[e.second].begin())); + + I(false); + } +}; + + +struct streamliner +{ +protected: + cvs_history & cvs; + int & edges_removed; + +public: + streamliner(cvs_history & c, int & edges_removed) + : cvs(c), + edges_removed(edges_removed) + { } + + bool abort() + { + return edges_removed > 0; + } + + void tree_edge(Edge e) + { +#ifdef DEBUG_BLOB_SPLITTER + L(FL("streamliner: tree edge: %d -> %d") % e.first % e.second); +#endif + } + + void forward_or_cross_edge(Edge e) + { +#ifdef DEBUG_BLOB_SPLITTER + L(FL("streamliner: cross edge: %d -> %d") % e.first % e.second); +#endif + + // a short circuit for branch start and tag blobs, which may very + // well have multiple ancestors (i.e. cross or forward edges) + if (cvs.blobs[e.second].get_digest().is_branch_start() || + cvs.blobs[e.second].get_digest().is_tag()) + return; + + // On a forward or cross edge, we first have to find the common + // ancestor of both blobs involved. For that we go upwards from + // the target (e.second) blob, until we reach the first grey + // blob. That must be a common ancestor (but not necessarily the + // lowest one). + vector< cvs_blob_index > path_a, path_b; + insert_iterator< vector< cvs_blob_index > > + ity_a(path_a, path_a.end()), + ity_b(path_b, path_b.end()); + + I(cvs.blobs[e.second].colors[0] == black); + dijkstra_shortest_path(cvs, e.second, cvs.root_blob, ity_a, + false, // upwards direction, + false, true, true, // follow grey and black, but + true, // break on first grey + make_pair(e.second, e.first)); // ignore direct path + I(!path_a.empty()); + L(FL(" forked at blob: %d") % path_a[0]); + + // From that common ancestor, we now follow the grey blobs downwards, + // until we find the source (e.first) blob of the cross edge. + I(cvs.blobs[e.first].colors[0] == grey); + I(cvs.blobs[path_a[0]].colors[0] == grey); + dijkstra_shortest_path(cvs, path_a[0], e.first, ity_b, + true, // downwards + false, true, false, // follow only grey + false, + make_pair(invalid_blob, invalid_blob)); + I(!path_b.empty()); + + { + vector< cvs_blob_index > tmp(path_b.size()); + reverse_copy(path_b.begin(), path_b.end(), tmp.begin()); + swap(tmp, path_b); + } + path_b.push_back(e.second); + + // At this point we have two different paths, both going from the + // (grey) common ancestor we've found. + I(path_a[0] == path_b[0]); + // to the target of the cross edge (e.second). + I(*path_a.rbegin() == e.second); + I(*path_b.rbegin() == e.second); + + for (vector::iterator ii = path_a.begin(); ii != path_a.end(); ++ii) + L(FL(" path a: %d") % *ii); + + for (vector::iterator ii = path_b.begin(); ii != path_b.end(); ++ii) + L(FL(" path b: %d") % *ii); + + // Unfortunately, that common ancestor isn't necessarily the lowest + // common ancestor. Because the (grey) path b might contain other + // forward edges to blobs in path a. An example (from the test + // importing_cvs_branches2): + // + // 2 + // p / \ p + // a 10 <-. 12 a + // t | | | t + // h 9 | 11 h + // | | | + // a 5 '- 3 b + // \ / + // 8 + // + // Here, the cross edge discovered was 3 -> 8. Here, path_a is: + // (2, 10, 9, 5, 8), while path_b is (2, 12, 11, 3, 8). The edge + // 3 -> 10 is another cross edge and will be discovered next, but + // hasn't been discovered so far. + // + // Thus to make sure we find the lowest common ancestor, we check + // if any blob in path_b depends on another blob in path_a. In + // such a case, that blob in path_a is the least common ancestor. + + set common_ancestors; + set done; + stack stack; + + for (vector::iterator ib = ++path_b.begin(); + ib != path_b.end(); ++ib) + { + if (*ib == e.second) + break; + + vector cross_path; + insert_iterator< vector< cvs_blob_index > > + ity_c(cross_path, cross_path.end()); + + // From the lowest common ancestor, we again try to find the + // shortest path to e.first to get a better path_b. + L(FL("checking for cross path from %d to %d") % *ib % *(++path_a.rbegin())); + dijkstra_shortest_path(cvs, *ib, *(++path_a.rbegin()), ity_c, + true, // downwards + true, false, true, // follow black and white + false, + make_pair(invalid_blob, invalid_blob)); + + if (!cross_path.empty()) + { + vector< cvs_blob_index > tmp(cross_path.size()); + reverse_copy(cross_path.begin(), cross_path.end(), tmp.begin()); + swap(tmp, path_a); + path_a.push_back(e.second); + + for (vector::iterator ii = path_a.begin(); ii != path_a.end(); ++ii) + L(FL(" new path a: %d") % *ii); + + I(path_a[0] == *ib); + + ib = path_b.erase(path_b.begin(), ib); + for (vector::iterator ii = path_b.begin(); ii != path_b.end(); ++ii) + L(FL(" new path b: %d") % *ii); + + I(path_a[0] == path_b[0]); + I(*path_a.rbegin() == e.second); + I(*path_b.rbegin() == e.second); + } + } + + + // Check if any one of the two paths contains a branch start. + bool a_has_branch = false; + vector::iterator first_branch_start_in_path_a; + bool b_has_branch = false; + vector::iterator first_branch_start_in_path_b; + for (vector::iterator i = ++path_a.begin(); + i != path_a.end(); ++i) + if (cvs.blobs[*i].get_digest().is_branch_start()) + { + L(FL("path b contains a branch blob: %d (%s)") % *i % get_event_repr(cvs, *cvs.blobs[*i].begin())); + a_has_branch = true; + first_branch_start_in_path_a = i; + break; + } + +#ifdef DEBUG_GRAPHVIZ + { + set blobs_to_show; + + for (vector::iterator i = path_a.begin(); i != path_a.end(); ++i) + blobs_to_show.insert(*i); + + for (vector::iterator i = path_b.begin(); i != path_b.end(); ++i) + blobs_to_show.insert(*i); + + write_graphviz_partial(cvs, "splitter", blobs_to_show, 5); + } +#endif + + for (vector::iterator i = ++path_b.begin(); + i != path_b.end(); ++i) + if (cvs.blobs[*i].get_digest().is_branch_start()) + { + L(FL("path b contains a branch blob: %d (%s)") % *i % get_event_repr(cvs, *cvs.blobs[*i].begin())); + b_has_branch = true; + first_branch_start_in_path_b = i; + break; + } + + { + I(!a_has_branch); + I(!b_has_branch); + // If none of the two paths has a branch start, we can simply // join them into one path, which satisfies all of the // dependencies and is correct with regard to timestamps. @@ -2593,7 +2816,7 @@ public: write_graphviz_partial(cvs, "invalid_back_edge", blobs_to_show, 5); #endif - L(FL("back edge from blob %d (%s) to blob %d (%s) - ABORTING!") + L(FL("streamliner: back edge from blob %d (%s) to blob %d (%s) - ABORTING!") % e.first % get_event_repr(cvs, *cvs.blobs[e.first].begin()) % e.second % get_event_repr(cvs, *cvs.blobs[e.second].begin())); @@ -3354,6 +3577,17 @@ resolve_blob_dependencies(cvs_history & break; } + while (1) + { + int edges_removed = 0; + cvs.import_order.clear(); + streamliner vis(cvs, edges_removed); + cvs.depth_first_search(vis, back_inserter(cvs.import_order)); + + if (edges_removed == 0) + break; + } + #ifdef DEBUG_GRAPHVIZ write_graphviz_complete(cvs, "all"); #endif