Issue #1467, #3397 - Rewrite the map from threads to tabs

src/plugin/Instances.h

+/*

[sergei, 2016/02/01 15:50:42]

Header guard is missed.

[sergei, 2016/02/01 15:50:42]

It would be better to rename the file to SyncMap.h

[Eric, 2016/02/03 17:17:04]

Acknowledged.

FYI, it's already present in https://codereview.adblockplus.org/29333107/, where
the other class destined for this header is present.

[Eric, 2016/02/03 17:17:04]

See https://codereview.adblockplus.org/29333107/. There are two classes related
to BHO instances to be defined here.

[sergei, 2016/02/08 13:35:35]

In that case it would be better to have two files SyncMap.h and SyncSet.h
because they contain quite generic classes. It seems it would be also good to
move them into "shared".

[Eric, 2016/02/08 18:45:29]

We're not writing Java. One header for two related containers for BHO instances
is just fine.

We will never need these containers in the engine, because they're especially
written to be containers of BHO instances, and the engine does not have any BHO
classes. They can stay right here in the plugin project.

[sergei, 2016/05/23 13:14:48]

So far there is only one container which is named as a generic container. It's
just a good practice to name files according to  the content of files. Even if
there are some generic container like SyncMap and SyncSet the file should be
named SyncContainers. "Instances" and SyncMap have nothing common.
If they are written only to store pointers to BHO instances and use thread ID as
a key then they should not be generic.

[Eric, 2016/07/17 16:04:43]

Both points addressed elsewhere.

+ * This file is part of Adblock Plus <https://adblockplus.org/>,
+ * Copyright (C) 2006-2015 Eyeo GmbH

[sergei, 2016/02/01 15:50:42]

2016

[Eric, 2016/02/03 17:17:04]

Done.

+ *
+ * Adblock Plus is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
+ * published by the Free Software Foundation.
+ *
+ * Adblock Plus is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#include <map>
+#include <mutex>
+
+/**
+ * A base class for a synchronized map from threads to BHO instances.

[sergei, 2016/02/01 15:50:41]

Either the comment or class should not be so thread-pointer specific. Either
it's a template SyncMap or it's a concrete class without any templates.

[Eric, 2016/02/03 17:17:03]

It's a template class to be instantiated with some BHO class. We only have one
BHO class in shipped code. There's a substitute BHO class used in the unit
tests.

[sergei, 2016/05/23 13:14:48]

I think that we should not overcomplicate the code only to have an ability to
use `int` instead of a particular class or just any auxiliary class in unit
tests.

[Eric, 2016/07/17 16:04:44]

This "complication" is part of the environment. We can't have unit tests with
BHO instance because we don't run unit tests under IE. If we have units tests,
we have some sort of mock class regardless.

+ *
+ * The member functions here not simply forwarded versions of the container functions.
+ * Rather, they are specialized for tracking BHO calls to SetSite().
+ * Their semantics allow for verification that the call pattern is as expected.
+ *
+ * The key to the map (in the subclass) is the thread ID, thus operations are serialized on a per-key basis.
+ * Calls to SetSite() bracket all other calls, so on a per-key basis
+ *   the order of operations is always either (insert / find-success / erase) or (find-failure).
+ * The library guarantees for std::map seem to indicate that operations on different keys
+ *   do not interfer with each other, but there's some ambiguity there.
+ * This class is synchronized as a matter of defensive programming.
+ */
+template<class Key, class T, T nullValue>

[sergei, 2016/02/01 15:50:42]

We don't need `T nullValue`.

[Eric, 2016/02/03 17:17:04]

See the unit tests. This class is easier to test when the argument is "class T"
and not "class T*".

+class SyncMap

[Oleksandr, 2016/02/01 10:53:28]

Isn't this essentially the same as concurrent_unordered_map?
https://msdn.microsoft.com/en-us/library/hh750089.aspx
Wouldn't we be better of with just using that?

[Eric, 2016/02/01 12:14:59]

It's similar in purpose, but that's about it.

You might consider replacing member 'idMap' with this class, but it looks like
that would be a step backwards. 'concurrent_unordered_map' does not have a
member analogous to 'find()'. Instead, you'd have call its 'at()' method and
catch the 'out_of_range' exception. Not exactly an improvement. Furthemore,
'concurrent_unordered_map' doesn't even have a concurrency-safe 'erase()'
method. Instead, it only has 'unsafe_erase', which is specifically marked as not
safe. So it doesn't work even as the underlying container.

+{
+  typedef std::lock_guard<std::mutex> SentryType;
+
+  /**
+   * Underlying map container
+   */
+  std::map<Key, T> idMap;

[sergei, 2016/02/01 15:50:43]

it would be better to call just "map".

[Eric, 2016/02/03 17:17:03]

Acknowledged.

+
+  /**
+   * Synchronization primitive
+   */
+  std::mutex mutex;

[sergei, 2016/02/01 15:50:42]

it should has `mutable`.

[Eric, 2016/02/03 17:17:03]

Done.

+
+public:
+  /**
+   * Returns true if (as expected) no key of value 'id' was present.
+   * Returns false otherwise.
+   */
+  bool AddIfAbsent(Key id, T p)

[sergei, 2016/02/01 15:50:41]

What about constant references or more concrete interface?

[sergei, 2016/02/01 15:50:43]

it would be better to call the arguments as "key" and "value".

[Eric, 2016/02/03 17:17:03]

I don't want it completely generic. If this were a generic-use class, I'd agree
with you.

[Eric, 2016/02/03 17:17:05]

No need for that. A plain 'class T' is just fine.

[sergei, 2016/02/08 13:35:35]

I disagree here. If it's written as generic and it can be used with almost any
type then it should have a proper interface. Otherwise it should not be generic.

[Eric, 2016/02/08 18:45:29]

Please tell that to 'std::basic_string', which ordinarily instantiates only with
one of two types. 'basic_string' can _not_ "be used with almost any type". Just
because you have a template doesn't mean you can stick anything at all in the
argument.

Perhaps the various iterations of "Concepts" that have been kicking around the
C++ standards committee for years (at least the last three rounds) will come to
fruition and there will be a decent way of specifying requirements on template
arguments. Until then, you just declare template arguments without such
specification.

You haven't said anything new on this point for a couple rounds of comments.
Just drop it.

[Oleksandr, 2016/02/10 10:58:47]

I think if we are not implementing a proper interface there isn't any reason
then to have both this and CurrentThreadMap later. We can just have one type
instead. But if we are treating this as a base class, hinting other types as
well, we can just implement it properly.

That being said, I don't feel this is very important and I would be fine
committing this as is too.

[Eric, 2016/05/19 17:23:57]

Good.
Unit testing is the reason to split them up.  You can't test all the basic cases
if you only use the current thread ID as a test parameter.

+  {
+    SentryType sentry(mutex);
+    auto it = idMap.find(id);
+    if (it != idMap.end())
+    {
+      return false;
+    }
+    idMap[id] = p;

[sergei, 2016/02/01 15:50:43]

`T` is not necessarily default constructible, it's better to use `emplace` or
`insert` here.

[Eric, 2016/02/03 17:17:04]

How is default construction an issue here? 'p' is an argument; we already have
an instance.

[sergei, 2016/02/08 13:35:35]

`map<K, T>::operator[]` firstly creates T() and then calls assign operator with
p as the argument.

[Eric, 2016/02/08 18:45:30]

No it doesn't. It constructs the value type in-place. Assignment is used nowhere
in any variant of this function. If it were to require assignment, the container
would only be available to types that were default-constructible.

http://en.cppreference.com/w/cpp/container/map/operator_at

[sergei, 2016/05/23 13:14:47]

So, it describes exactly what I had told. One can even try the code there, just
try it
#include <map>

class X {
public:
  X(int i){}
};

int main()
{
  std::map<int, X> m;
  m[10] = X(10);
  return 0;
}

[Eric, 2016/07/17 16:04:43]

I've rewritten the function to use insert(). The bigger problem with this
function was a performance detail, since 'operator[]' implicitly calls the
equivalent of 'find()'.

[sergei, 2016/07/19 07:56:09]

JIC, insert has the same complexity.

+    return true;
+  }
+
+  /**
+   * Returns true if (as expected) a key of value 'id' was already present.
+   * Returns false otherwise.
+   */
+  bool RemoveAndCheck(Key id)
+  {
+    SentryType sentry(mutex);
+    auto it = idMap.find(id);

[sergei, 2016/02/01 15:50:42]

Can we do instead `return 1 == idMap.erase(id);`?

[Eric, 2016/02/03 17:17:04]

Other than being written as a yoda condition, that would also be correct. I find
that far less clear, though.

The way it's written now, it's an obvious parallel with 'AddIfAbsent()'
immediately above.

If this were a performance-critical function, I'd consider the optimization. As
it is, clarity predominates.

+    if (it == idMap.end())
+    {
+      return false;
+    }
+    idMap.erase(it);
+    return true;
+  }
+
+  /**
+   * Returns a non-null pointer if a key of value 'id' is present.

[sergei, 2016/02/01 15:50:42]

This comment does not fit the template class. We don't know whether T is a
pointer or not.

[Eric, 2016/02/03 17:17:04]

Acknowledged.

I probably wrote this comment before I wrote the unit tests.

+   * Returns nullptr otherwise.
+   */
+  T Locate(Key id)

[sergei, 2016/02/01 15:50:42]

I would rather prefer to pass T by reference to use it as a destination for the
copy of stored object and return `bool` to indicate whether it's found or not.

[sergei, 2016/02/01 15:50:42]

This method should be constant method.

[Eric, 2016/02/03 17:17:03]

No need. Putting return values in references is never a great pattern, but
sometimes necessary. Here we don't need it.

[Eric, 2016/02/03 17:17:03]

Done.

[sergei, 2016/02/08 13:35:36]

IMO having default `nullValue` here is a bad design.
The main reason is that it's used here to infer that there is no entry with the
passed key, but one can easily put `nullptr` into that container (and it's a
normal case), so there is indeed an entry with that value but the caller will
think that there is no such entry.
Secondly, the caller should be able to obtain that nullValue from the container
(class or instance), otherwise it looks like a magic value in the code. We use
it merely in one place, so it seems that having `nullValue` requires too much
efforts.

As I said before we don't need it. I think it's not only an over-engineering
it's rather a bad design.

[Eric, 2016/02/08 18:45:30]

The alternative is a traits class, which would over-engineering for the present
usage, although not for a general library function, which this is not.

Some classes have a special value that means "nothing", other classes do not. It
would be useful if the C++ standard library provided such a traits class that
could be simply overloaded to specify such a property. No such standard property
query, though, exists in <type_traits>. Lacking that, it's easier just to put it
in a template argument.
You can't put 'nullptr' into a container that's not instantiated with pointer
class. Had I intended the container to only supported pointers I would have
declared the template argument "class T*" and not "class T".
We use it in the unit tests.

Are you arguing that we should eliminate the unit tests so that it actually is
only used in one place?

+  {
+    SentryType sentry(mutex);
+    auto it = idMap.find(id);
+    return (it != idMap.end()) ? it->second : nullValue;

[sergei, 2016/02/01 15:50:43]

As far as I remember () are not needed here.

[Eric, 2016/02/03 17:17:04]

Not necessary, but ternary expressions are always easier to read with
parentheses around the condition (unless it's a single variable).

[sergei, 2016/02/08 13:35:36]

That's very subjective.

[Eric, 2016/02/08 18:45:29]

It should be manifestly obvious by now that your personal preferences differs
from mine.

+  }
+};