Array as hash tables

[Lasse Reichstein Nielsen]

I don't see any way of acquiring a reference to an object with less
than one object on its prototype chain.

Object.prototype
But apart from that, no.
/L

 

[Richard Cornford]

Object.prototype
But apart from that, no.

Good point. That is one object with a null [[prototype]] property.
Unfortunately it will also feature the list of specified properties and
any implementation dependent properties from the outset so it doesn't
help in this context.

Richard.

 

[Thomas 'PointedEars' Lahn]

It works fine for that. The problem is that it doesn't start out empty,
but wnything you put in, you get out again fine.

With the exception of built-in properties, see below.

Richard did. He suggested a single space IIRC.


Ok, an associative array implementation that isn't fooled by standard ^^^^^^^^^^^^^^^^^^^^^^^^
or non-standard values:

^^^^^^^^^^^^^^^^^^^^^^
What is this supposed to mean?

---
function Map() {
this.map = {};
}
Map.Value = function Value(v) {
this.value = v;
}
Map.prototype.containsKey = function containsKey(k) {
return (this.map[k]) instanceof Map.Value;

It does not make sense to put the operand of `instanceof' in parantheses.
It would make more sense to put the entire return value in parantheses
although this would not be required as `instanceof' has precedence over
`return'.

}
Map.prototype.put = function put(k,v) {
this.map[k] = new Map.Value(v);
};
Map.prototype.get = function get(k) {
var v = this.map[k];
if (v instanceof Map.Value) {

^^^^^^^^^^^^^^^^^^^^^^
Would it not be wise to use this.contains(v) here?

return v.value;
}
};
Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!) and thus assignment to objectReference[k] (here:
this.map[k]) must not be allowed for those values of k. Encapsulating
the value in another (prototyped) object (twice) does not really help
here, and if the used object contains _only_ a value property this
approach is merely a waste of memory. Only a suitable transparent
modification of the passed property name (suffix, prefix, infix; while
one the former to should be used) will solve that problem. A single
space indeed seems to be viable as internal prefix, yet the prototype
could be implemented more flexible in the case the space is not enough:

function Map() {}

Map.prototype.prefix = " ";
Map.prototype.suffix = "";

Map.prototype.containsKey = function map_containsKey(k)
{
return !!(this[this.prefix + k + this.suffix]);
}

Map.prototype.put = function map_put(k, v)
{
this[this.prefix + k + this.suffix] = v;
};

Map.prototype.get = function map_get(k)
{
return this[this.prefix + k + this.suffix];
};

Map.prototype.remove = function map_remove(k)
{
delete this[this.prefix + k + this.suffix];
};


PointedEars

 

[Thomas 'PointedEars' Lahn]

Map.prototype.containsKey = function containsKey(k) {
return (this.map[k]) instanceof Map.Value; [...]
}
Map.prototype.put = function put(k,v) {
this.map[k] = new Map.Value(v);
};
Map.prototype.get = function get(k) {
var v = this.map[k];
if (v instanceof Map.Value) {

^^^^^^^^^^^^^^^^^^^^^^
Would it not be wise to use this.contains(v) here?

No, it would not, and this.containsKey(k) would result in another
unnessary lookup which is not reasonable. Forget about this.


PointedEars

 

[Lasse Reichstein Nielsen]

^^^^^^^^^^^^^^^^^^^^^^
What is this supposed to mean?

Hmm ... should be: fooled by existing standard or non-standard
properties.

Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!)

Absolutely. I'm depending on them being overwritable.

and thus assignment to objectReference[k] (here: this.map[k]) must
not be allowed for those values of k.

Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.

If the properties are "magic", like, e.g., innerHTML on DOM nodes, or
"length" on Arrays, then even overwriting is a problem.

However, that would be a violation of ECMA 262, since an object is
created using "new Constructor", where "Constructor" is a user defined
function, can not be a host object.

What you might be thinking of, is that deleting existing properties
should not be allowed, which is true (no "delete Object.prototype.toString").
So, "delete" should be:

Map.prototype.remove = function remove(k) {
if (this.containsKey(k)) {
delete this.map[k]
}
};

Encapsulating the value in another (prototyped) object (twice) does
not really help here, and if the used object contains _only_ a value
property this approach is merely a waste of memory.

No, the point of wrapping in an instance of Map.Value is that no
preexisting property is an instance of Map.Value. That allows us to
distinguish properties that we put in the map from those already
there, no matter what type they might be (including objects or
arrays).

The "containsKey" and "get" methods (and the correct "delete") test
that the property value is an instance of Map.Value, i.e., that it's
something put there using the "put" method.

(I'm not considering someone deliberatly messing with the "this.map"
property, only the problem of avoiding mistakin existing properties
for elements of the map)

Only a suitable transparent modification of the passed property name
(suffix, prefix, infix; while one the former to should be used) will
solve that problem.

This solves it for correct ECMA262 implementations.

Modifying the property name blindly will not be absolutely safe, since
you might hit another preexisting property name with the modified name
as well (who knows, maybe some day, an ECMAScript impelentation will
have a hidden method called " hiddenMethod " on Object prototype).

/L

 

[Grant Wagner]

This solves it for correct ECMA262 implementations.

Modifying the property name blindly will not be absolutely safe, since
you might hit another preexisting property name with the modified name
as well (who knows, maybe some day, an ECMAScript impelentation will
have a hidden method called " hiddenMethod " on Object prototype).

How about defining the prefix/suffix combination by some millisecond time stamp /
psuedo-random value at run time. This would reduce the chances of a conflict to
zero[1]:

<script type="text/javascript">
function Map() {}
Map.prototype.prefix = (new Date()).getTime();
Map.prototype.suffix = Math.floor(Map.prototype.prefix * Math.random()) + "_";
Map.prototype.prefix = "_" + prefix;
Map.prototype.uniqueId = prefix + suffix;
// or one of the endless variations on this concept
// ... etc ...
</script>

Doing it this way would also guarantee that you could uniquely[2] identify each
Map(), although I'm not sure there's any value in that.

[1] - almost zero. It's certainly possible, however unlikely, that a user agent
or future ECMAScript implementation might have an Object property called
"_1092061591623toString1026459394798_" or
"_1092061887384constructor527875481827_".
[2] - almost unique. Due to system clock synchronizing software, it would be
possible, however unlikely, for two Map()s to have the same prefix and randomly
generate the same suffix.

 

[Thomas 'PointedEars' Lahn]

Hmm ... should be: fooled by existing standard or non-standard
properties.

Well, it can still be fooled.

Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!)

Absolutely. I'm depending on them being overwritable.

But some properties are read-only.

and thus assignment to objectReference[k] (here: this.map[k]) must
not be allowed for those values of k.

Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.

If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

And if not, you would have saved nothing in your "hash table". That
does not sound like a (reasonable/viable) solution.

If the properties are "magic", like, e.g., innerHTML on DOM nodes, or
"length" on Arrays, then even overwriting is a problem.

However, that would be a violation of ECMA 262, since an object is
created using "new Constructor", where "Constructor" is a user defined
function, can not be a host object.

This is not about host objects, it is about core properties *every*
object has.

What you might be thinking of, is that deleting existing properties
should not be allowed,

No, although that would be useful.

which is true (no "delete Object.prototype.toString").

You would effectively overlay Object.prototype.toString if you would try
to add a "toString" hash table entry and cause to property cease to work
as supposed. Or consider a "valueOf" hash table entry. Or "constructor".
Or ...

No, the point of wrapping in an instance of Map.Value is that no
preexisting property is an instance of Map.Value.

Even your Map and Map.Value instances have preexisting properties
inherited from Object. They may not be enumerable but they still
exist. There is no, I repeat, *no* object that has no "preexisting
properties".

That allows us to distinguish properties that we put in the map from those
already there, no matter what type they might be (including objects or
arrays).

I won't debate that you can distinguish between added and built-in
properties and I did not. The point is that your implementation does
not prevent overlaying or overwriting built-in properties. You control
the read, but not the write process (yet).

This solves it for correct ECMA262 implementations.

No, it does not, because of

,-[ECMA 262 Edition 3, 2000-03-24]
|
| 2 Conformance
|
| [...]
| A conforming implementation of ECMAScript is permitted to provide
| additional types, values, objects, properties, and functions beyond
| those described in this specification. In particular, a conforming
| implementation of ECMAScript is permitted to provide properties not
| described in this specification, and values for those properties,
| for objects that are described in this specification.

And unfortunately(?), we are not living in a perfect standardized world.
Implementations make use of the opportunity described above, there is
escape(), unescape(), __proto__ and *much* more out there.

Exactly ECMA-262 and the prototype chain presents the reason why your
hash table implementation "as is" is flawed.


PointedEars

 

[Lasse Reichstein Nielsen]

But some properties are read-only.

But they exist on the prototype, not on the object itself. They can be
overwritten on the inheriting object.

Assume o is an object and o.ro is a read-only, don't delete,
etc. property. Then
---
function C(){};
C.prototype = o;
var c = new C();
c.ro = 42;
---
will work and set "c.ro" to 42. It isn't affected by the read-only
property of the prototype. The prototype's property is just what you
read if you haven't created that property on the object itself.

If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

No unexpected behavior will happen, as long as the object is only used
to look up properties in. No "core property" affects how [[Get]] and
[[Put]] works.

Unexpected behavior might happen if I overwrite the "toString"
property *and* tries to convert the object to a string, but I never do
that.

And if not, you would have saved nothing in your "hash table". That
does not sound like a (reasonable/viable) solution.

Not understood.

This is not about host objects, it is about core properties *every*
object has.

That every object's *prototype* has. The object itself has no
properties.

Doing
new Object()
creates a new native ECMAScript object. It has no visible properties
itself, only the ones inherited from its [[Prototype]], Object.prototype.

You would effectively overlay Object.prototype.toString if you would try
to add a "toString" hash table entry and cause to property cease to work
as supposed.

Deliberatly. That's why I don't use the map for anything except property
lookup.

Or consider a "valueOf" hash table entry. Or "constructor".
Or ...

It is not a problem.

Even your Map and Map.Value instances have preexisting properties
inherited from Object. They may not be enumerable but they still
exist. There is no, I repeat, *no* object that has no "preexisting
properties".

Absolutely. What I was saying is that no preexisting property of the
object used as a map would be an instance of "Map.Value". That means
that any property of the map object can be tested for being an
instance of "Map.Value", and if it is, it's something I put there,
otherwise it should be ignored.

I won't debate that you can distinguish between added and built-in
properties and I did not. The point is that your implementation does
not prevent overlaying or overwriting built-in properties.

Agree completely. It depends on doing just that.

You control the read, but not the write process (yet).

Sure I do, unless the implementation is pathologically flawed.

No, it does not, because of

,-[ECMA 262 Edition 3, 2000-03-24]
|
| 2 Conformance

And unfortunately(?), we are not living in a perfect standardized world.
Implementations make use of the opportunity described above, there is
escape(), unescape(), __proto__ and *much* more out there.

As long as a *new* object has no properties itself (not counting the ones
inherited from its prototype) that are read-only or don't-delete, then
it will work.

An implementation that makes a new object have a read-only or
don't-delete property that cannot be overwritten is asking for
trouble. Imagine

var x = new Object();
x.xyzzy = 42; // bang! "xyzzy" is read-only. Not a good idea!

Exactly ECMA-262 and the prototype chain presents the reason why your
hash table implementation "as is" is flawed.

No, the prototype chain guarantees that the read-only or don't-delete
properties of the prototype can be overwritten in the inheriting
object.

/L

 

[Thomas 'PointedEars' Lahn]

If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

No unexpected behavior will happen, as long as the object is only used
to look up properties in. No "core property" affects how [[Get]] and
[[Put]] works.

Unexpected behavior might happen if I overwrite the "toString"
property *and* tries to convert the object to a string, but I never do
that.

A toString() method, e.g., is really a nice-to-have for such hash tables
or collections, so I will try not to allow overlaying prototype properties
in my implementation (Collection in collection.js, available soon.)

Not understood.

Does not matter anymore.

This is not about host objects, it is about core properties *every*
object has.

That every object's *prototype* has. The object itself has no
properties.

Doing
new Object()
creates a new native ECMAScript object. It has no visible properties
itself, only the ones inherited from its [[Prototype]], Object.prototype.
ACK

You control the read, but not the write process (yet).

^^^^^
Sure I do, unless the implementation is pathologically flawed.

I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.

As long as a *new* object has no properties itself (not counting the ones
inherited from its prototype) that are read-only or don't-delete, then
it will work.

Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?

An implementation that makes a new object have a read-only or
don't-delete property that cannot be overwritten is asking for
trouble. Imagine

var x = new Object();
x.xyzzy = 42; // bang! "xyzzy" is read-only. Not a good idea!

Not a good idea for Object objects. Perfectly reasonable for others.

No, the prototype chain guarantees that the read-only or don't-delete
properties of the prototype can be overwritten in the inheriting
object.

ACK, but I would refrain from overlaying prototype properties anyway here.


PointedEars

 

[Lasse Reichstein Nielsen]

I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.

Correct. It shouldn't matter, though.

Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?

No. The "prototype" property is only relevant on function objects, and
the map object ("this.map") is just a normal object. It probably
doesn't have a property called "prototype", and if it does, it doesn't
do anything (not to be confuzed with the internal "[[Prototype]]"
property).

....
Not a good idea for Object objects. Perfectly reasonable for others.

Absolutely. Other types of Object, like those created by Array, will
have properties inherent to the specific object (e.g. "length"). Those
will be on the object itself, not its prototype, and can easily be
on-overwritable.

ACK, but I would refrain from overlaying prototype properties anyway here.

Out of curiosity: Why?

/L

 

[Thomas 'PointedEars' Lahn]

I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.

Correct. It shouldn't matter, though.
Hmmm.

Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?

No. The "prototype" property is only relevant on function objects, and
the map object ("this.map") is just a normal object. [...]

Of course (oh my, it is really *hot* weather here!!1 ).
I meant `constructor' (and the like). Can you think of
overlaying one of them to interfere with normal operation
(toString() aside, which is obvious)?

Out of curiosity: Why?

AFAIS it makes the implementation less flexible and thus restricts
the freedom of the users to apply it to their needs, effectively
making it less attractive to them.


PointedEars

 

[Lasse Reichstein Nielsen]

I meant `constructor' (and the like). Can you think of
overlaying one of them to interfere with normal operation
(toString() aside, which is obvious)?

No. There isn't really any "normal operation" for an instance of
Object. The "constructor" property is only a convenience, it is never
used for anything by the language. The functions like "hasOwnProperty"
are also only used by the programmer. The language sematics uses
[[hasProperty]] directly, so overwriting "hasOwnProperty" will not
affect anything except specific user-introduced calls to that.

AFAIS it makes the implementation less flexible and thus restricts
the freedom of the users to apply it to their needs, effectively
making it less attractive to them.

I don't see any restriction in this case, but if there were some,
it would be a reason.

/L