# # # patch "rcs_import.cc" # from [234cf60d8d7d77a1d00eb1a7b29fe6d68f0793be] # to [93c0454b23e1c0e4cf43752da1ac6f3bc610e28d] # ============================================================ --- rcs_import.cc 234cf60d8d7d77a1d00eb1a7b29fe6d68f0793be +++ rcs_import.cc 93c0454b23e1c0e4cf43752da1ac6f3bc610e28d @@ -2601,229 +2601,6 @@ 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. @@ -2905,7 +2682,7 @@ public: write_graphviz_partial(cvs, "invalid_back_edge", blobs_to_show, 5); #endif - L(FL("streamliner: back edge from blob %d (%s) to blob %d (%s) - ABORTING!") + 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())); @@ -3696,17 +3473,6 @@ 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