If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

Elsa should use the STL more.

RESOLVED WONTFIX

Status

()

Core
Rewriting and Analysis
RESOLVED WONTFIX
8 years ago
6 years ago

People

(Reporter: jcranmer, Assigned: jcranmer)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(5 attachments)

(Assignee)

Description

8 years ago
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.
(Assignee)

Comment 1

8 years ago
Created attachment 396274 [details] [diff] [review]
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.
Attachment #396274 - Flags: review?(tglek)

Updated

8 years ago
Attachment #396274 - Flags: review?(tglek) → review-

Comment 2

8 years ago
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.
(Assignee)

Comment 3

8 years ago
(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.

Updated

8 years ago
Attachment #396274 - Flags: review- → review+

Comment 4

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

s/map/noterminals/ or something
(Assignee)

Comment 5

8 years ago
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.
Attachment #396274 - Attachment description: Remove bitarray.h, changing only usage to vector<bool> → Remove bitarray.h, changing only usage to vector<bool> [checked in]
(Assignee)

Comment 6

8 years ago
(with the name changed, of course)
(Assignee)

Comment 7

8 years ago
Created attachment 397099 [details] [diff] [review]
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.
Attachment #397099 - Flags: review?(tglek)

Comment 8

8 years ago
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!
Attachment #397099 - Flags: review?(tglek) → review+
(Assignee)

Comment 9

8 years ago
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.
Attachment #397099 - Attachment description: Remove StringSet in favor of std::set<string> → Remove StringSet in favor of std::set<string> [Checked in]
(Assignee)

Comment 10

8 years ago
Created attachment 397309 [details] [diff] [review]
Remove SObjStack in favor of std::stack [checked in]

This removes sobjstack, and also fixes a dependency rebuild problem in elkhound/c.
Attachment #397309 - Flags: review?(tglek)

Comment 11

8 years ago
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?
Attachment #397309 - Flags: review?(tglek) → review+
(Assignee)

Comment 12

8 years ago
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.
Attachment #397309 - Attachment description: Remove SObjStack in favor of std::stack → Remove SObjStack in favor of std::stack [checked in]
(Assignee)

Comment 13

8 years ago
Created attachment 398024 [details] [diff] [review]
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.
Attachment #398024 - Flags: review?(tglek)

Comment 14

8 years ago
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 []
Attachment #398024 - Flags: review?(tglek) → review+
(Assignee)

Comment 15

8 years ago
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.
Attachment #398024 - Attachment description: Remove StringDict (unused) and ObjMap in favor of std::map. → Remove StringDict (unused) and ObjMap in favor of std::map [checked-in]
(Assignee)

Comment 16

8 years ago
Created attachment 399934 [details] [diff] [review]
Remove PtrIntMap in favor of std::map [checked in]

This removes PtrIntMap, which is only used once and is a rather small header file...
Attachment #399934 - Flags: review?(tglek)

Comment 17

8 years ago
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
Attachment #399934 - Flags: review?(tglek) → review+
(Assignee)

Comment 18

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

Pushed as changeset 4215:ed6b8eb3cd20.
Attachment #399934 - Attachment description: Remove PtrIntMap in favor of std::map → Remove PtrIntMap in favor of std::map [checked in]
(Assignee)

Comment 19

6 years ago
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.
Status: ASSIGNED → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.