512293 - Elsa should use the STL more.

Status: RESOLVED WONTFIX

(Developer Infrastructure :: Source Code Analysis, defect)

Description

[Joshua Cranmer [:jcranmer]]

Elsa has a deficiency in that it uses the smbase instead of the STL libraries. These classes can easily be ported:
* BitArray (vector<bool>)
* StringSet (set<string>)
* sm::string (std::string)
* Many maps (std::map)
* lists (std::list)

The key issue that I see is that some claim to have ownership models which may not be compatible with the STL. Then again, I don't think there would be too many problems with simply letting elsa leak like a holey bucket given the average lifespan of a program using elsa.

Regex is definitely present in TR 1 and C++0x, and I believe g++ 4.3 has support for both (I see them in /usr/include/c++/4.3). I don't know when hashtable was introduced, but it looks like TR 1 and C++0x as well.

The classes which I don't see a C++ or C++0x standard library for:
* [B]Flatten
* Bit2D
* breaker (okay, it's a function...)
* DataBlok/GrowBuffer (a std::basic_string<void *> or probably even just std::string may be better here)
* BitwiseArray stuff (memcpy instead of copy-constructor for moving elements)
* gprintf
* srcloc

Patches to remove BitArray and StringSet will be coming shortly.

Comment 1

[Joshua Cranmer [:jcranmer]]

Attachment: Remove bitarray.h, changing only usage to vector<bool> [checked in]

This works (it passes all tests and if it didn't, I'm quite sure we'd know about it). I can't say anything about speed, but I'd be surprised if it wasn't faster.

Comment 2

[(dormant account)]

Comment on attachment 396274 [details] [diff] [review]
Remove bitarray.h, changing only usage to vector<bool> [checked in]

>-  BitArray map(numNonterms);
>+  std::vector<bool> map(numNonterms);

Please don't call it map. I know old code is doing that, but it's morally wrong.

>   bool anyWithSuper = false;
>   {
>     SFOREACH_PRODUCTION(reductions, iter) {
>       Production const *p = iter.data();
>       if (p->left->superset) {
>-        map.set(p->left->ntIndex);
>+        map.assign(p->left->ntIndex, true);

use [] to assign.


>         anyWithSuper = true;
>       }
>     }
>@@ -2998,7 +2997,7 @@ int GrammarAnalysis::subsetDirectiveReso
> 
>     SFOREACH_OBJLIST(Nonterminal, prod->left->subsets, iter) {
>       Nonterminal const *sub = iter.data();
>-      if (map.test(sub->ntIndex)) {
>+      if (map[sub->ntIndex]) {

dont do that, do .find != .end(). && *map.iterator() I think that's what the code means? Not sure what .test did

>         trace("prec")
>           << "in state " << state->id
>           << ", R/R conflict on token " << sym->name
>@@ -3366,7 +3365,7 @@ void GrammarAnalysis::computeParseTables
> 
>   // use the derivability relation to compute a total order
>   // on nonterminals
>-  BitArray seen(numNonterms);
>+  std::vector<bool> seen(numNonterms);
>   int nextOrdinal = numNonterms-1;
>   for (int nt=0; nt < numNonterms; nt++) {
>     // expand from 'nt' in case it's disconnected; this will be
>@@ -3401,15 +3400,15 @@ void GrammarAnalysis::topologicalSort(
>   NtIndex *order,    // table we're filling with ordinals
>   int &nextOrdinal,  // latest ordinal not yet used
>   NtIndex current,   // current nonterminal to expand
>-  BitArray &seen)    // set of nonterminals we've already seen
>-{
>-  if (seen.test(current)) {
>+  std::vector<bool> &seen)    // set of nonterminals we've already seen
>+{
>+  if (seen[current]) {

Same as above, this test is ok is "current" guaranteed to be in there.

Comment 3

[Joshua Cranmer [:jcranmer]]

(In reply to comment #2)
> >     SFOREACH_OBJLIST(Nonterminal, prod->left->subsets, iter) {
> >       Nonterminal const *sub = iter.data();
> >-      if (map.test(sub->ntIndex)) {
> >+      if (map[sub->ntIndex]) {
> 
> dont do that, do .find != .end(). && *map.iterator() I think that's what the
> code means? Not sure what .test did

This is a bit array: test checks if the nth bit (or sub->ntIndex'th bit, in this case) is set). vector<bool> is perhaps the most poorly named collection, I believe a better name would be dynamic_bitset_but_omitting_some_features.

Comment 4

[(dormant account)]

Comment on attachment 396274 [details] [diff] [review]
Remove bitarray.h, changing only usage to vector<bool> [checked in]

s/map/noterminals/ or something

Comment 5

[Joshua Cranmer [:jcranmer]]

Comment on attachment 396274 [details] [diff] [review]
Remove bitarray.h, changing only usage to vector<bool> [checked in]

Removal of BitArray pushed as changeset 4211:ff5b31f3d14f.

Comment 6

[Joshua Cranmer [:jcranmer]]

(with the name changed, of course)

Comment 7

[Joshua Cranmer [:jcranmer]]

Attachment: Remove StringSet in favor of std::set<string> [Checked in]

This removes StringSet, and incidentally removes a lot of set occurrences by changing a list to a set.

Comment 8

[(dormant account)]

Comment on attachment 397099 [details] [diff] [review]
Remove StringSet in favor of std::set<string> [Checked in]

> 
> using namespace sm;

seems like a good time to switch to std::string too.
>+  std::set<string> attributeNames;     // names of attributes of AST nodes

And then you'd get to not put std:: everywhere.


nice!

Comment 9

[Joshua Cranmer [:jcranmer]]

Comment on attachment 397099 [details] [diff] [review]
Remove StringSet in favor of std::set<string> [Checked in]

Checked in, with a minor change (got rid of the -> change in the comment, that was bad s///).

Changeset 4212:3b0234a757ac.

Comment 10

[Joshua Cranmer [:jcranmer]]

Attachment: Remove SObjStack in favor of std::stack [checked in]

This removes sobjstack, and also fixes a dependency rebuild problem in elkhound/c.

Comment 11

[(dormant account)]

Comment on attachment 397309 [details] [diff] [review]
Remove SObjStack in favor of std::stack [checked in]

>+    S_goto *g = gotos.top();
>+    gotos.pop();

frankly stl map sucks for not returning stuff in .pop. I think we should just make a <return same stuff as .top> pop_set(set) utility.
> 
>-  xassert(switches.count() == 0);
>-  xassert(loops.count() == 0);
>+  xassert(switches.size() == 0);
>+  xassert(loops.size() == 0);

>-  xassert(switches.count() == 0);
>-  xassert(loops.count() == 0);
>+  xassert(switches.size() == 0);
>+  xassert(loops.size() == 0);
> }

Use empty?

Comment 12

[Joshua Cranmer [:jcranmer]]

Comment on attachment 397309 [details] [diff] [review]
Remove SObjStack in favor of std::stack [checked in]

Pushed, with changes for nits, as changeset 4213:e7202930744f.

Comment 13

[Joshua Cranmer [:jcranmer]]

Attachment: Remove StringDict (unused) and ObjMap in favor of std::map [checked-in]

This patch removes the unknowningly unused StringDict (someone left the header included, which is why I missed it in my grand removal patch) and the ObjMap as well. It also removes some more stuff from the smbase build system that I've missed in previous patches.

Comment 14

[(dormant account)]

Comment on attachment 398024 [details] [diff] [review]
Remove StringDict (unused) and ObjMap in favor of std::map [checked-in]

> 
>-  bindings.add(name, value);
>+  bindings[name] = value;

that's not correct. bindings.insert(...::value_type(name,value)) is the stl equiv if my memory serves me right.
>-  bindings.addReplace(name, b);
>+  Binding *tmp = bindings[name];

use .find

stl's [] stuff is broken for stuff like this

>+  if (tmp)
>+    delete tmp;
>+  bindings[name] = b;
> }
> 


r+ with these fixed. I think in general stl's [] is dumb and causes weird issues when not used with utmost care. I'm almost tempted to forbid using stl's []

Comment 15

[Joshua Cranmer [:jcranmer]]

Comment on attachment 398024 [details] [diff] [review]
Remove StringDict (unused) and ObjMap in favor of std::map [checked-in]

Checked in with the [] removed as changeset:   4214:890fc0eac8c8.

Comment 16

[Joshua Cranmer [:jcranmer]]

Attachment: Remove PtrIntMap in favor of std::map [checked in]

This removes PtrIntMap, which is only used once and is a rather small header file...

Comment 17

[(dormant account)]

Comment on attachment 399934 [details] [diff] [review]
Remove PtrIntMap in favor of std::map [checked in]

>diff --git a/ast/xmlhelp.cc b/ast/xmlhelp.cc
>--- a/ast/xmlhelp.cc
>+++ b/ast/xmlhelp.cc
>@@ -7,7 +7,6 @@
> #include <stdio.h>              // sprintf
> // #include "strtokp.h"            // StrtokParse
> #include "exc.h"                // xformat
>-#include "ptrintmap.h"          // PtrIntMap
> 
> using namespace sm;
> 
>@@ -15,8 +14,11 @@ using namespace sm;
> #define CANONICAL_XML_IDS
> 
> #ifdef CANONICAL_XML_IDS
>+#include <map>
>+
>+typedef std::map<const void * const, xmlUniqueId_t> XmlIdMap;
> xmlUniqueId_t nextXmlUniqueId = 1;
>-PtrIntMap<void const, xmlUniqueId_t> addr2id;
>+XmlIdMap addr2id;
> #endif
> 
> xmlUniqueId_t mapAddrToUniqueId(void const * const addr) {
>@@ -24,12 +26,12 @@ xmlUniqueId_t mapAddrToUniqueId(void con
>   // special-case the NULL pointer
>   if (addr == NULL) return 0;
>   // otherwise, maintain a map to a canonical address
>-  xmlUniqueId_t id0 = addr2id.get(addr);
>-  if (!id0) {
>-    id0 = nextXmlUniqueId++;
>-    addr2id.add(addr, id0);
>+  XmlIdMap::iterator iter = addr2id.find(addr);
>+  if (iter == addr2id.end()) {
>+    addr2id[addr] = nextXmlUniqueId;
>+    return nextXmlUniqueId++;
>   }
>-  return id0;
>+  return iter->second;
> #else
>   // avoid using the map
>   return reinterpret_cast<xmlUniqueId_t>(addr);
>diff --git a/smbase/ptrintmap.h b/smbase/ptrintmap.h
>deleted file mode 100644
>--- a/smbase/ptrintmap.h
>+++ /dev/null
>@@ -1,68 +0,0 @@
>-// ptrintmap.h            see license.txt for copyright and terms of use
>-// map from KEY* to int for arbitrary type KEY
>-// (key is not owned by the table)
>-
>-// dsw: modified from ptrmap.h by replacing 'VALUE*' with 'DATAVALUE'.
>-// this is an abuse of VoidPtrMap as it only works with types
>-// DATAVALUE that are the same size as a 'void*', such as 'int'; I
>-// think VoidPtrMap should be generalized to allow this usage.
>-
>-// for const purposes, I regard the mapping itself as the only
>-// thing that cannot be modified in a "const" map
>-
>-#ifndef PTRINTMAP_H
>-#define PTRINTMAP_H
>-
>-#include "vptrmap.h"       // VoidPtrMap
>-#include "typ.h"           // NULL
>-
>-
>-template <class KEY, class DATAVALUE>
>-class PtrIntMap {
>-private:     // data
>-  // underlying map implementation, around which this class
>-  // is a type-safe wrapper
>-  VoidPtrMap map;
>-
>-public:      // funcs
>-  PtrIntMap()                         : map() {}
>-  ~PtrIntMap()                        {}
>-
>-  // query # of mapped entries
>-  int getNumEntries() const        { return map.getNumEntries(); }
>-  bool isEmpty() const             { return getNumEntries() == 0; }
>-  bool isNotEmpty() const          { return !isEmpty(); }
>-
>-  // if this key has a mapping, return it; otherwise, return NULL
>-  DATAVALUE get(KEY const *key) const { return reinterpret_cast<DATAVALUE>(map.get((void const*)key)); }
>-
>-  // add a mapping from 'key' to 'value'; replaces existing
>-  // mapping, if any
>-  void add(KEY *key, DATAVALUE value) { map.add((void*)key, (void*)value); }
>-
>-  // remove all mappings
>-  void empty()                     { map.empty(); }
>-
>-
>-public:      // iterators
>-  class Iter {
>-  private:     // data
>-    // underlying iterator state
>-    VoidPtrMap::Iter iter;
>-
>-  public:      // fucs
>-    Iter(PtrIntMap<KEY,DATAVALUE> const &map)   : iter(map.map) {}
>-    ~Iter()                              {}
>-
>-    bool isDone() const            { return iter.isDone(); }
>-    void adv()                     { return iter.adv(); }
>-
>-    // return information about the currently-referenced table entry
>-    KEY *key() const               { return (KEY*)iter.key(); }
>-    DATAVALUE value() const        { return reinterpret_cast<DATAVALUE>(iter.value()); }
>-  };
>-  friend class Iter;
>-};
>-
>-
>-#endif // PTRINTMAP_H

Comment 18

[Joshua Cranmer [:jcranmer]]

Comment on attachment 399934 [details] [diff] [review]
Remove PtrIntMap in favor of std::map [checked in]

Pushed as changeset 4215:ed6b8eb3cd20.

Comment 19

[Joshua Cranmer [:jcranmer]]

At this time, Mozilla is no longer pursuing the use of Elsa and Pork for static analysis and rewriting. Therefore, there are no longer any intentions to fix or support any outstanding bugs in these tools.