Hello community,
here is the log from the commit of package re2 for openSUSE:Factory checked in
at 2017-12-19 10:59:21
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/re2 (Old)
and /work/SRC/openSUSE:Factory/.re2.new (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "re2"
Tue Dec 19 10:59:21 2017 rev:12 rq:558181 version:MACRO
Changes:
--------
--- /work/SRC/openSUSE:Factory/re2/re2.changes 2017-11-04 19:29:43.820153929
+0100
+++ /work/SRC/openSUSE:Factory/.re2.new/re2.changes 2017-12-19
10:59:21.946806415 +0100
@@ -1,0 +2,6 @@
+Mon Dec 18 14:19:37 UTC 2017 - mplus...@suse.com
+
+- Update to version 2017-12-01
+ * No upstream changelog available
+
+-------------------------------------------------------------------
Old:
----
2017-11-01.tar.gz
New:
----
2017-12-01.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ re2.spec ++++++
--- /var/tmp/diff_new_pack.2NxJny/_old 2017-12-19 10:59:22.706769728 +0100
+++ /var/tmp/diff_new_pack.2NxJny/_new 2017-12-19 10:59:22.706769728 +0100
@@ -16,7 +16,7 @@
#
-%global longver 2017-11-01
+%global longver 2017-12-01
%global shortver %(echo %{longver}|sed 's|-||g')
%define libname libre2-0
Name: re2
@@ -25,7 +25,7 @@
Summary: C++ fast alternative to backtracking RE engines
License: BSD-3-Clause
Group: Development/Libraries/C and C++
-Url: https://github.com/google/re2/
+URL: https://github.com/google/re2/
Source0: https://github.com/google/re2/archive/%{longver}.tar.gz
BuildRequires: gcc-c++
BuildRequires: pkgconfig
++++++ 2017-11-01.tar.gz -> 2017-12-01.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/re2/prefilter_tree.cc
new/re2-2017-12-01/re2/prefilter_tree.cc
--- old/re2-2017-11-01/re2/prefilter_tree.cc 2017-10-28 04:16:51.000000000
+0200
+++ new/re2-2017-12-01/re2/prefilter_tree.cc 2017-11-16 22:52:42.000000000
+0100
@@ -15,6 +15,7 @@
#include "util/util.h"
#include "util/logging.h"
+#include "util/strutil.h"
#include "re2/prefilter.h"
#include "re2/re2.h"
@@ -67,7 +68,9 @@
compiled_ = true;
- AssignUniqueIds(atom_vec);
+ // TODO(junyer): Use std::unordered_set<Prefilter*> instead?
+ NodeMap nodes;
+ AssignUniqueIds(&nodes, atom_vec);
// Identify nodes that are too common among prefilters and are
// triggering too many parents. Then get rid of them if possible.
@@ -100,27 +103,27 @@
}
if (ExtraDebug)
- PrintDebugInfo();
+ PrintDebugInfo(&nodes);
}
-Prefilter* PrefilterTree::CanonicalNode(Prefilter* node) {
+Prefilter* PrefilterTree::CanonicalNode(NodeMap* nodes, Prefilter* node) {
string node_string = NodeString(node);
- std::map<string, Prefilter*>::iterator iter = node_map_.find(node_string);
- if (iter == node_map_.end())
+ std::map<string, Prefilter*>::iterator iter = nodes->find(node_string);
+ if (iter == nodes->end())
return NULL;
return (*iter).second;
}
string PrefilterTree::NodeString(Prefilter* node) const {
// Adding the operation disambiguates AND/OR/atom nodes.
- string s = std::to_string(node->op()) + ":";
+ string s = StringPrintf("%d", node->op()) + ":";
if (node->op() == Prefilter::ATOM) {
s += node->atom();
} else {
for (size_t i = 0; i < node->subs()->size(); i++) {
if (i > 0)
s += ',';
- s += std::to_string((*node->subs())[i]->unique_id());
+ s += StringPrintf("%d", (*node->subs())[i]->unique_id());
}
}
return s;
@@ -162,7 +165,8 @@
}
}
-void PrefilterTree::AssignUniqueIds(std::vector<string>* atom_vec) {
+void PrefilterTree::AssignUniqueIds(NodeMap* nodes,
+ std::vector<string>* atom_vec) {
atom_vec->clear();
// Build vector of all filter nodes, sorted topologically
@@ -199,11 +203,11 @@
if (node == NULL)
continue;
node->set_unique_id(-1);
- Prefilter* canonical = CanonicalNode(node);
+ Prefilter* canonical = CanonicalNode(nodes, node);
if (canonical == NULL) {
// Any further nodes that have the same node string
// will find this node as the canonical node.
- node_map_[NodeString(node)] = node;
+ nodes->emplace(NodeString(node), node);
if (node->op() == Prefilter::ATOM) {
atom_vec->push_back(node->atom());
atom_index_to_id_.push_back(unique_id);
@@ -213,7 +217,7 @@
node->set_unique_id(canonical->unique_id());
}
}
- entries_.resize(node_map_.size());
+ entries_.resize(nodes->size());
// Create parent StdIntMap for the entries.
for (int i = static_cast<int>(v.size()) - 1; i >= 0; i--) {
@@ -221,7 +225,7 @@
if (prefilter == NULL)
continue;
- if (CanonicalNode(prefilter) != prefilter)
+ if (CanonicalNode(nodes, prefilter) != prefilter)
continue;
Entry* entry = &entries_[prefilter->unique_id()];
@@ -234,7 +238,7 @@
if (prefilter == NULL)
continue;
- if (CanonicalNode(prefilter) != prefilter)
+ if (CanonicalNode(nodes, prefilter) != prefilter)
continue;
Entry* entry = &entries_[prefilter->unique_id()];
@@ -254,7 +258,7 @@
std::set<int> uniq_child;
for (size_t j = 0; j < prefilter->subs()->size(); j++) {
Prefilter* child = (*prefilter->subs())[j];
- Prefilter* canonical = CanonicalNode(child);
+ Prefilter* canonical = CanonicalNode(nodes, child);
if (canonical == NULL) {
LOG(DFATAL) << "Null canonical node";
return;
@@ -281,7 +285,7 @@
for (size_t i = 0; i < prefilter_vec_.size(); i++) {
if (prefilter_vec_[i] == NULL)
continue;
- int id = CanonicalNode(prefilter_vec_[i])->unique_id();
+ int id = CanonicalNode(nodes, prefilter_vec_[i])->unique_id();
DCHECK_LE(0, id);
Entry* entry = &entries_[id];
entry->regexps.push_back(static_cast<int>(i));
@@ -357,7 +361,7 @@
LOG(ERROR) << DebugNodeString(prefilter_vec_[regexpid]);
}
-void PrefilterTree::PrintDebugInfo() {
+void PrefilterTree::PrintDebugInfo(NodeMap* nodes) {
LOG(ERROR) << "#Unique Atoms: " << atom_index_to_id_.size();
LOG(ERROR) << "#Unique Nodes: " << entries_.size();
@@ -370,8 +374,8 @@
LOG(ERROR) << it->first;
}
LOG(ERROR) << "Map:";
- for (std::map<string, Prefilter*>::const_iterator iter = node_map_.begin();
- iter != node_map_.end(); ++iter)
+ for (std::map<string, Prefilter*>::const_iterator iter = nodes->begin();
+ iter != nodes->end(); ++iter)
LOG(ERROR) << "NodeId: " << (*iter).second->unique_id()
<< " Str: " << (*iter).first;
}
@@ -389,7 +393,7 @@
for (size_t i = 0; i < node->subs()->size(); i++) {
if (i > 0)
node_string += ',';
- node_string += std::to_string((*node->subs())[i]->unique_id());
+ node_string += StringPrintf("%d", (*node->subs())[i]->unique_id());
node_string += ":";
node_string += DebugNodeString((*node->subs())[i]);
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/re2/prefilter_tree.h
new/re2-2017-12-01/re2/prefilter_tree.h
--- old/re2-2017-11-01/re2/prefilter_tree.h 2017-10-28 04:16:51.000000000
+0200
+++ new/re2-2017-12-01/re2/prefilter_tree.h 2017-11-16 22:52:42.000000000
+0100
@@ -22,14 +22,10 @@
#include "util/util.h"
#include "util/sparse_array.h"
+#include "re2/prefilter.h"
namespace re2 {
-typedef SparseArray<int> IntMap;
-typedef std::map<int, int> StdIntMap;
-
-class Prefilter;
-
class PrefilterTree {
public:
PrefilterTree();
@@ -61,6 +57,10 @@
// nodes of the prefilter of the regexp.
void PrintPrefilter(int regexpid);
+ private:
+ typedef SparseArray<int> IntMap;
+ typedef std::map<int, int> StdIntMap;
+ typedef std::map<string, Prefilter*> NodeMap;
// Each unique node has a corresponding Entry that helps in
// passing the matching trigger information along the tree.
@@ -84,14 +84,13 @@
std::vector<int> regexps;
};
- private:
// Returns true if the prefilter node should be kept.
bool KeepNode(Prefilter* node) const;
// This function assigns unique ids to various parts of the
// prefilter, by looking at if these nodes are already in the
// PrefilterTree.
- void AssignUniqueIds(std::vector<string>* atom_vec);
+ void AssignUniqueIds(NodeMap* nodes, std::vector<string>* atom_vec);
// Given the matching atoms, find the regexps to be triggered.
void PropagateMatch(const std::vector<int>& atom_ids,
@@ -99,7 +98,7 @@
// Returns the prefilter node that has the same NodeString as this
// node. For the canonical node, returns node.
- Prefilter* CanonicalNode(Prefilter* node);
+ Prefilter* CanonicalNode(NodeMap* nodes, Prefilter* node);
// A string that uniquely identifies the node. Assumes that the
// children of node has already been assigned unique ids.
@@ -109,15 +108,12 @@
string DebugNodeString(Prefilter* node) const;
// Used for debugging.
- void PrintDebugInfo();
+ void PrintDebugInfo(NodeMap* nodes);
// These are all the nodes formed by Compile. Essentially, there is
// one node for each unique atom and each unique AND/OR node.
std::vector<Entry> entries_;
- // Map node string to canonical Prefilter node.
- std::map<string, Prefilter*> node_map_;
-
// indices of regexps that always pass through the filter (since we
// found no required literals in these regexps).
std::vector<int> unfiltered_;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/re2/set.cc
new/re2-2017-12-01/re2/set.cc
--- old/re2-2017-11-01/re2/set.cc 2017-10-28 04:16:51.000000000 +0200
+++ new/re2-2017-12-01/re2/set.cc 2017-11-16 22:52:42.000000000 +0100
@@ -104,8 +104,15 @@
}
bool RE2::Set::Match(const StringPiece& text, std::vector<int>* v) const {
+ return Match(text, v, NULL);
+}
+
+bool RE2::Set::Match(const StringPiece& text, std::vector<int>* v,
+ ErrorInfo* error_info) const {
if (!compiled_) {
LOG(DFATAL) << "RE2::Set::Match() called before compiling";
+ if (error_info != NULL)
+ error_info->kind = kNotCompiled;
return false;
}
bool dfa_failed = false;
@@ -121,17 +128,26 @@
LOG(ERROR) << "DFA out of memory: size " << prog_->size() << ", "
<< "bytemap range " << prog_->bytemap_range() << ", "
<< "list count " << prog_->list_count();
+ if (error_info != NULL)
+ error_info->kind = kOutOfMemory;
return false;
}
- if (ret == false)
+ if (ret == false) {
+ if (error_info != NULL)
+ error_info->kind = kNoError;
return false;
+ }
if (v != NULL) {
if (matches->empty()) {
- LOG(DFATAL) << "RE2::Set::Match() matched, but matches unknown";
+ LOG(DFATAL) << "RE2::Set::Match() matched, but no matches returned?!";
+ if (error_info != NULL)
+ error_info->kind = kInconsistent;
return false;
}
v->assign(matches->begin(), matches->end());
}
+ if (error_info != NULL)
+ error_info->kind = kNoError;
return true;
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/re2/set.h new/re2-2017-12-01/re2/set.h
--- old/re2-2017-11-01/re2/set.h 2017-10-28 04:16:51.000000000 +0200
+++ new/re2-2017-12-01/re2/set.h 2017-11-16 22:52:42.000000000 +0100
@@ -22,29 +22,45 @@
// be searched for simultaneously.
class RE2::Set {
public:
+ enum ErrorKind {
+ kNoError = 0,
+ kNotCompiled, // The set is not compiled.
+ kOutOfMemory, // The DFA ran out of memory.
+ kInconsistent, // The result is inconsistent. This should never happen.
+ };
+
+ struct ErrorInfo {
+ ErrorKind kind;
+ };
+
Set(const RE2::Options& options, RE2::Anchor anchor);
~Set();
- // Add adds regexp pattern to the set, interpreted using the RE2 options.
- // (The RE2 constructor's default options parameter is RE2::UTF8.)
- // Add returns the regexp index that will be used to identify
- // it in the result of Match, or -1 if the regexp cannot be parsed.
+ // Adds pattern to the set using the options passed to the constructor.
+ // Returns the index that will identify the regexp in the output of Match(),
+ // or -1 if the regexp cannot be parsed.
// Indices are assigned in sequential order starting from 0.
- // Error returns do not increment the index.
- // If an error occurs and error != NULL, *error will hold an error message.
+ // Errors do not increment the index; if error is not NULL, *error will hold
+ // the error message from the parser.
int Add(const StringPiece& pattern, string* error);
- // Compile prepares the Set for matching.
- // Add must not be called again after Compile.
- // Compile must be called before Match.
- // Compile may return false if it runs out of memory.
+ // Compiles the set in preparation for matching.
+ // Returns false if the compiler runs out of memory.
+ // Add() must not be called again after Compile().
+ // Compile() must be called before Match().
bool Compile();
- // Match returns true if text matches any of the regexps in the set.
- // If so, it fills v (if not NULL) with the indices of the matching regexps.
+ // Returns true if text matches at least one of the regexps in the set.
+ // Fills v (if not NULL) with the indices of the matching regexps.
// Callers must not expect v to be sorted.
bool Match(const StringPiece& text, std::vector<int>* v) const;
+ // As above, but populates error_info (if not NULL) when none of the regexps
+ // in the set matched. This can inform callers when DFA execution fails, for
+ // example, because they might wish to handle that case differently.
+ bool Match(const StringPiece& text, std::vector<int>* v,
+ ErrorInfo* error_info) const;
+
private:
typedef std::pair<string, re2::Regexp*> Elem;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/re2/testing/set_test.cc
new/re2-2017-12-01/re2/testing/set_test.cc
--- old/re2-2017-11-01/re2/testing/set_test.cc 2017-10-28 04:16:51.000000000
+0200
+++ new/re2-2017-12-01/re2/testing/set_test.cc 2017-11-16 22:52:42.000000000
+0100
@@ -3,6 +3,7 @@
// license that can be found in the LICENSE file.
#include <stddef.h>
+#include <string>
#include <vector>
#include "util/test.h"
@@ -200,4 +201,18 @@
CHECK_EQ(v[0], 0);
}
+TEST(Set, OutOfMemory) {
+ RE2::Set s(RE2::DefaultOptions, RE2::UNANCHORED);
+
+ string a(10000, 'a');
+ CHECK_EQ(s.Add(a, NULL), 0);
+ CHECK_EQ(s.Compile(), true);
+
+ std::vector<int> v;
+ RE2::Set::ErrorInfo ei;
+ CHECK_EQ(s.Match(a, &v, &ei), false);
+ CHECK_EQ(v.size(), 0);
+ CHECK_EQ(ei.kind, RE2::Set::kOutOfMemory);
+}
+
} // namespace re2
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/util/sparse_array.h
new/re2-2017-12-01/util/sparse_array.h
--- old/re2-2017-11-01/util/sparse_array.h 2017-10-28 04:16:51.000000000
+0200
+++ new/re2-2017-12-01/util/sparse_array.h 2017-11-16 22:52:42.000000000
+0100
@@ -55,36 +55,34 @@
// IMPLEMENTATION
//
-// SparseArray uses a vector dense_ and an array sparse_to_dense_, both of
-// size max_size_. At any point, the number of elements in the sparse array is
-// size_.
+// SparseArray is an array dense_ and an array sparse_, both of size max_size_.
+// At any point, the number of elements in the sparse array is size_.
//
-// The vector dense_ contains the size_ elements in the sparse array (with
+// The array dense_ contains the size_ elements in the sparse array (with
// their indices),
// in the order that the elements were first inserted. This array is dense:
// the size_ pairs are dense_[0] through dense_[size_-1].
//
-// The array sparse_to_dense_ maps from indices in [0,m) to indices in
-// [0,size_).
-// For indices present in the array, dense_[sparse_to_dense_[i]].index_ == i.
-// For indices not present in the array, sparse_to_dense_ can contain
-// any value at all, perhaps outside the range [0, size_) but perhaps not.
+// The array sparse_ maps from indices in [0,m) to indices in [0,size_).
+// For indices present in the array, dense_[sparse_[i]].index_ == i.
+// For indices not present in the array, sparse_ can contain any value at all,
+// perhaps outside the range [0, size_) but perhaps not.
//
-// The lax requirement on sparse_to_dense_ values makes clearing
-// the array very easy: set size_ to 0. Lookups are slightly more
-// complicated. An index i has a value in the array if and only if:
-// sparse_to_dense_[i] is in [0, size_) AND
-// dense_[sparse_to_dense_[i]].index_ == i.
+// The lax requirement on sparse_ values makes clearing the array very easy:
+// set size_ to 0. Lookups are slightly more complicated.
+// An index i has a value in the array if and only if:
+// sparse_[i] is in [0, size_) AND
+// dense_[sparse_[i]].index_ == i.
// If both these properties hold, only then it is safe to refer to
-// dense_[sparse_to_dense_[i]].value_
+// dense_[sparse_[i]].value_
// as the value associated with index i.
//
-// To insert a new entry, set sparse_to_dense_[i] to size_,
+// To insert a new entry, set sparse_[i] to size_,
// initialize dense_[size_], and then increment size_.
//
// Deletion of specific values from the array is implemented by
// swapping dense_[size_-1] and the dense_ being deleted and then
-// updating the appropriate sparse_to_dense_ entries.
+// updating the appropriate sparse_ entries.
//
// To make the sparse array as efficient as possible for non-primitive types,
// elements may or may not be destroyed when they are deleted from the sparse
@@ -94,9 +92,17 @@
//
// A moved-from SparseArray will be empty.
+// Doing this simplifies the logic below.
+#ifndef __has_feature
+#define __has_feature(x) 0
+#endif
+
#include <assert.h>
#include <stdint.h>
#include <string.h>
+#if __has_feature(memory_sanitizer)
+#include <sanitizer/msan_interface.h>
+#endif
#include <algorithm>
#include <memory>
#include <type_traits>
@@ -200,13 +206,13 @@
iterator find(int i) {
if (has_index(i))
- return dense_.get() + sparse_to_dense_[i];
+ return dense_.get() + sparse_[i];
return end();
}
const_iterator find(int i) const {
if (has_index(i))
- return dense_.get() + sparse_to_dense_[i];
+ return dense_.get() + sparse_[i];
return end();
}
@@ -263,7 +269,7 @@
DebugCheckInvariants();
std::pair<iterator, bool> p;
if (has_index(v.index_)) {
- p = {dense_.get() + sparse_to_dense_[v.index_], false};
+ p = {dense_.get() + sparse_[v.index_], false};
} else {
p = {set_new(std::forward<U>(v).index_, std::forward<U>(v).second),
true};
}
@@ -295,9 +301,9 @@
iterator SetExistingInternal(int i, U&& v) { // NOLINT
DebugCheckInvariants();
assert(has_index(i));
- dense_[sparse_to_dense_[i]].value() = std::forward<U>(v);
+ dense_[sparse_[i]].value() = std::forward<U>(v);
DebugCheckInvariants();
- return dense_.get() + sparse_to_dense_[i];
+ return dense_.get() + sparse_[i];
}
// Add the index i to the array.
@@ -312,23 +318,20 @@
// and at the beginning and end of all public non-const member functions.
void DebugCheckInvariants() const;
- static bool ShouldInitializeMemory() {
-#if defined(__has_feature)
+ // Initializes memory for elements [min, max).
+ void MaybeInitializeMemory(int min, int max) {
#if __has_feature(memory_sanitizer)
- return true;
-#else
- return false;
-#endif
+ __msan_unpoison(sparse_.get() + min, (max - min) * sizeof sparse_[0]);
#elif defined(RE2_ON_VALGRIND)
- return true;
-#else
- return false;
+ for (int i = min; i < max; i++) {
+ sparse_[i] = 0xababababU;
+ }
#endif
}
int size_ = 0;
int max_size_ = 0;
- std::unique_ptr<int[]> sparse_to_dense_;
+ std::unique_ptr<int[]> sparse_;
std::unique_ptr<IndexValue[]> dense_;
};
@@ -339,9 +342,9 @@
SparseArray<Value>::SparseArray(const SparseArray& src)
: size_(src.size_),
max_size_(src.max_size_),
- sparse_to_dense_(new int[max_size_]),
+ sparse_(new int[max_size_]),
dense_(new IndexValue[max_size_]) {
- std::copy_n(src.sparse_to_dense_.get(), max_size_, sparse_to_dense_.get());
+ std::copy_n(src.sparse_.get(), max_size_, sparse_.get());
std::copy_n(src.dense_.get(), max_size_, dense_.get());
}
@@ -349,7 +352,7 @@
SparseArray<Value>::SparseArray(SparseArray&& src) /*noexcept*/ // NOLINT
: size_(src.size_),
max_size_(src.max_size_),
- sparse_to_dense_(std::move(src.sparse_to_dense_)),
+ sparse_(std::move(src.sparse_)),
dense_(std::move(src.dense_)) {
src.size_ = 0;
src.max_size_ = 0;
@@ -360,8 +363,8 @@
size_ = src.size_;
max_size_ = src.max_size_;
std::unique_ptr<int[]> a(new int[max_size_]);
- std::copy_n(src.sparse_to_dense_.get(), src.max_size_, a.get());
- sparse_to_dense_ = std::move(a);
+ std::copy_n(src.sparse_.get(), src.max_size_, a.get());
+ sparse_ = std::move(a);
std::unique_ptr<IndexValue[]> b(new IndexValue[max_size_]);
std::copy_n(src.dense_.get(), src.max_size_, b.get());
dense_ = std::move(b);
@@ -373,7 +376,7 @@
SparseArray&& src) /*noexcept*/ { // NOLINT
size_ = src.size_;
max_size_ = src.max_size_;
- sparse_to_dense_ = std::move(src.sparse_to_dense_);
+ sparse_ = std::move(src.sparse_);
dense_ = std::move(src.dense_);
// clear out the source
src.size_ = 0;
@@ -425,10 +428,10 @@
DebugCheckInvariants();
if (max_size > max_size_) {
std::unique_ptr<int[]> a(new int[max_size]);
- if (sparse_to_dense_) {
- std::copy_n(sparse_to_dense_.get(), max_size_, a.get());
+ if (sparse_) {
+ std::copy_n(sparse_.get(), max_size_, a.get());
}
- sparse_to_dense_ = std::move(a);
+ sparse_ = std::move(a);
std::unique_ptr<IndexValue[]> b(new IndexValue[max_size]);
if (dense_) {
@@ -436,12 +439,7 @@
}
dense_ = std::move(b);
- if (ShouldInitializeMemory()) {
- for (int i = max_size_; i < max_size; i++) {
- sparse_to_dense_[i] = 0xababababU;
- dense_[i].index_ = 0xababababU;
- }
- }
+ MaybeInitializeMemory(max_size_, max_size);
}
max_size_ = max_size;
if (size_ > max_size_)
@@ -457,15 +455,15 @@
if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size_)) {
return false;
}
- // Unsigned comparison avoids checking sparse_to_dense_[i] < 0.
- return (uint32_t)sparse_to_dense_[i] < (uint32_t)size_ &&
- dense_[sparse_to_dense_[i]].index_ == i;
+ // Unsigned comparison avoids checking sparse_[i] < 0.
+ return (uint32_t)sparse_[i] < (uint32_t)size_ &&
+ dense_[sparse_[i]].index_ == i;
}
template<typename Value>
const Value& SparseArray<Value>::get_existing(int i) const {
assert(has_index(i));
- return dense_[sparse_to_dense_[i]].second;
+ return dense_[sparse_[i]].second;
}
template<typename Value>
@@ -480,10 +478,10 @@
void SparseArray<Value>::erase_existing(int i) {
DebugCheckInvariants();
assert(has_index(i));
- int di = sparse_to_dense_[i];
+ int di = sparse_[i];
if (di < size_ - 1) {
dense_[di] = std::move(dense_[size_ - 1]);
- sparse_to_dense_[dense_[di].index_] = di;
+ sparse_[dense_[di].index_] = di;
}
size_--;
DebugCheckInvariants();
@@ -493,24 +491,17 @@
void SparseArray<Value>::create_index(int i) {
assert(!has_index(i));
assert(size_ < max_size_);
- sparse_to_dense_[i] = size_;
+ sparse_[i] = size_;
dense_[size_].index_ = i;
size_++;
}
template<typename Value> SparseArray<Value>::SparseArray(int max_size) {
- max_size_ = max_size;
- sparse_to_dense_.reset(new int[max_size]);
+ sparse_.reset(new int[max_size]);
dense_.reset(new IndexValue[max_size]);
size_ = 0;
-
- if (ShouldInitializeMemory()) {
- for (int i = 0; i < max_size; i++) {
- sparse_to_dense_[i] = 0xababababU;
- dense_[i].index_ = 0xababababU;
- }
- }
-
+ MaybeInitializeMemory(size_, max_size);
+ max_size_ = max_size;
DebugCheckInvariants();
}
@@ -521,7 +512,7 @@
template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const
{
assert(0 <= size_);
assert(size_ <= max_size_);
- assert(size_ == 0 || sparse_to_dense_ != NULL);
+ assert(size_ == 0 || sparse_ != NULL);
}
// Comparison function for sorting.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2017-11-01/util/sparse_set.h
new/re2-2017-12-01/util/sparse_set.h
--- old/re2-2017-11-01/util/sparse_set.h 2017-10-28 04:16:51.000000000
+0200
+++ new/re2-2017-12-01/util/sparse_set.h 2017-11-16 22:52:42.000000000
+0100
@@ -47,9 +47,17 @@
//
// See sparse_array.h for implementation details.
+// Doing this simplifies the logic below.
+#ifndef __has_feature
+#define __has_feature(x) 0
+#endif
+
#include <assert.h>
#include <stdint.h>
#include <string.h>
+#if __has_feature(memory_sanitizer)
+#include <sanitizer/msan_interface.h>
+#endif
#include <algorithm>
#include <memory>
#include <utility>
@@ -145,7 +153,7 @@
create_index(i);
}
DebugCheckInvariants();
- return dense_.get() + sparse_to_dense_[i];
+ return dense_.get() + sparse_[i];
}
// Add the index i to the set.
@@ -159,23 +167,20 @@
// and at the beginning and end of all public non-const member functions.
void DebugCheckInvariants() const;
- static bool ShouldInitializeMemory() {
-#if defined(__has_feature)
+ // Initializes memory for elements [min, max).
+ void MaybeInitializeMemory(int min, int max) {
#if __has_feature(memory_sanitizer)
- return true;
-#else
- return false;
-#endif
+ __msan_unpoison(sparse_.get() + min, (max - min) * sizeof sparse_[0]);
#elif defined(RE2_ON_VALGRIND)
- return true;
-#else
- return false;
+ for (int i = min; i < max; i++) {
+ sparse_[i] = 0xababababU;
+ }
#endif
}
int size_ = 0;
int max_size_ = 0;
- std::unique_ptr<int[]> sparse_to_dense_;
+ std::unique_ptr<int[]> sparse_;
std::unique_ptr<int[]> dense_;
};
@@ -189,10 +194,10 @@
DebugCheckInvariants();
if (max_size > max_size_) {
std::unique_ptr<int[]> a(new int[max_size]);
- if (sparse_to_dense_) {
- std::copy_n(sparse_to_dense_.get(), max_size_, a.get());
+ if (sparse_) {
+ std::copy_n(sparse_.get(), max_size_, a.get());
}
- sparse_to_dense_ = std::move(a);
+ sparse_ = std::move(a);
std::unique_ptr<int[]> b(new int[max_size]);
if (dense_) {
@@ -200,12 +205,7 @@
}
dense_ = std::move(b);
- if (ShouldInitializeMemory()) {
- for (int i = max_size_; i < max_size; i++) {
- sparse_to_dense_[i] = 0xababababU;
- dense_[i] = 0xababababU;
- }
- }
+ MaybeInitializeMemory(max_size_, max_size);
}
max_size_ = max_size;
if (size_ > max_size_)
@@ -221,33 +221,26 @@
if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size_)) {
return false;
}
- // Unsigned comparison avoids checking sparse_to_dense_[i] < 0.
- return (uint32_t)sparse_to_dense_[i] < (uint32_t)size_ &&
- dense_[sparse_to_dense_[i]] == i;
+ // Unsigned comparison avoids checking sparse_[i] < 0.
+ return (uint32_t)sparse_[i] < (uint32_t)size_ &&
+ dense_[sparse_[i]] == i;
}
template<typename Value>
void SparseSetT<Value>::create_index(int i) {
assert(!contains(i));
assert(size_ < max_size_);
- sparse_to_dense_[i] = size_;
+ sparse_[i] = size_;
dense_[size_] = i;
size_++;
}
template<typename Value> SparseSetT<Value>::SparseSetT(int max_size) {
- max_size_ = max_size;
- sparse_to_dense_.reset(new int[max_size]);
+ sparse_.reset(new int[max_size]);
dense_.reset(new int[max_size]);
size_ = 0;
-
- if (ShouldInitializeMemory()) {
- for (int i = 0; i < max_size; i++) {
- sparse_to_dense_[i] = 0xababababU;
- dense_[i] = 0xababababU;
- }
- }
-
+ MaybeInitializeMemory(size_, max_size);
+ max_size_ = max_size;
DebugCheckInvariants();
}
@@ -258,7 +251,7 @@
template<typename Value> void SparseSetT<Value>::DebugCheckInvariants() const {
assert(0 <= size_);
assert(size_ <= max_size_);
- assert(size_ == 0 || sparse_to_dense_ != NULL);
+ assert(size_ == 0 || sparse_ != NULL);
}
// Comparison function for sorting.
