Think I've found a bug causing stack overflow in HashCodeUtil (hirondelle.web4j.model.ModelUtil might also be affected) in certain circumstances.

[Jared Tomaszewski]

Greetings,

I already did send this message to webm...@javapractices.com, but since this e-mail is somewhat anonymous, I thought I post it on this mailing list as well to make sure that persons concerned get the message.

It might be that the issue in question is not directly related to web4j, though I have all reasons to believe that the implementation of ModelUtil.hash(int aSeed, Object aObject) is the same as the HashCodeUtil.( int aSeed , Object aObject ) from http://www.javapractices.com/topic/TopicAction.do?Id=28. So, without further ado:

This refers to the HashCodeUtil listed on

http://www.javapractices.com/topic/TopicAction.do?Id=28

If an object has a field which is an array (or List as in my case) which contains the object itself as an element, then using HashCodeUtil.( int aSeed , Object aObject ) to hash the field will cause stack overflow.

The following two marked lines might be a solution to the problem, though I have not tested it:

  public static int hash( int aSeed , Object aObject ) {

      ...

      for ( int idx = 0; idx < length; ++idx ) {

        Object item = Array.get(aObject, idx);

>       if(item.equals(aObject)) result = hash(result, aObject.hashCode());

>       else

                //recursive call!

        result = hash(result, item);

      }

      ...

  }

Please confirm if the problem is real and if my solution is right.

While currently I am in no need to use web4j, I do like the idea of simplicity and minimalism, as well convention over configuration. If I even need to build a web app I will surely seriously consider web4j for the job.

Best regards

Jared

[John O'Hanley]

The issue rests on the fact that an object references another-object-of-the-same-class as a field.

Is that correct? Would an example of that be a linked-list implementation, in which a Node can reference another Node? Would you have any other examples of this kind of self-referential behaviour?

 - John

[John O'Hanley]

Or does the object X actually wind up referring to itself? (Instead of another object of the same class.)

- John

[Jared Tomaszewski]

Yes, it refers to itself. In my application I am indeed using LinkedList which holds a list of objects of its own type. The object itself is immutable with the exception for the list, which is supposed to change at different points throughout the application's lifetime, therefore for the object to appear unchanged within Collections at all times, the list is omitted in implementations of equals(), hashCode() and compareTo() functions. Note that other objects added to the list within current object hold references to exactly the same instance of LinkedList as the current one. Also all object instances are at some point stored in various Collection instances.

[Jared Tomaszewski]

Now that I think of it, this stack overflow I've encountered pointed out an error in my implementation, where I initially included the changing list into the hashCode() /equals() of my immutable Object thus violating its immutability, so in a way this behaviour was helpful. In my case this list serves as a mean of grouping objects related to the one instantiating the list with itself as the first member of the group. Other members can be added to the group arbitrarily. However it is possible that one would want to include this list in the hashCode() and equals() computation if an object's identity was expected to established once its list has been established, where by default the object itself would be the first element on the list/collection (i.e. the first member of the group).

[John O'Hanley]

Hi,

The case of an object referring to itself is really unusual. It's not usually found in the kind of applications which are the primary target of the web4j framework - HTML front ends to a relational database.

The JDK's Collections framework already has many classes written by intelligent experts. Outside of an academic context, I can't see much need to write a custom LinkedList class, or similar.

For these reasons, I don't think it's appropriate to change the ModelUtil class for cases where an object refers to itself.

 - John

[Jared Tomaszewski]

I see and I understand your viewpoint. In this case it might indeed be unnecessary to amend ModelUtil. However, maybe it could be useful to change the HashCodeUtil for faithful readers of http://www.javapractices.com, such as myself, who might run into the problem. Nevertheless, below I post the whole method with a fix that I think will actually work:

public static int hash( int aSeed , Object aObject ) {

int result = aSeed;

if ( aObject == null)

result = hash(result, 0);

else if ( ! isArray(aObject) )

result = hash(result, aObject.hashCode());

else {

int length = Array.getLength(aObject);

for ( int idx = 0; idx < length; ++idx ) {

Object item = Array.get(aObject, idx);

if(!item.equals(aObject))  // In case the aObject equals to an item, the item will not be hashed to prevent stack overflow.

//recursive call!

result = hash(result, item);

}

}

return result;

}

Maybe someone will find this useful on those rare occasions.

Best regards

Jared

[John O'Hanley]

Hi Jared

I'm reconsidering. If it doesn't cost anything, it's probably worth doing.

But instead of :
  if(!item.equals(aObject))

shouldn't the check be simply on the object's identity? :
  if(! item == aObject) 

- John

[Jared Thomas]

Yup, 'if(! item == aObject)' is definitely a cheaper way to go about this. The only point in going after .equals() is that it would offer greater flexibility. Shall anyone go for similar use and behaviour, but their objects weren't immutable, there's a good chance the '==' wouldn't work as expected, particularly if they were going for a particular way of comparing those objects. But then, it is a fair trade-off I guess, as long as it is documented.

regards

Jared

--
You received this message because you are subscribed to a topic in the Google Groups "web4j-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/web4j-users/_t3SFwA4-Zk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to web4j-users...@googlegroups.com.

To post to this group, send email to web4j...@googlegroups.com.

Visit this group at http://groups.google.com/group/web4j-users.
For more options, visit https://groups.google.com/groups/opt_out.

[Jared Thomas]

Ok, now that I think of it how about:

if ( !item == aObject || !item.equals(aObject) )

The best of both worlds?

[Thomas Hallgren]

Given that most implementations of the method equals starts by comparing identity and given that a JVM nowadays will perform very clever optimistic method call inlining, I think that you might be discussing a non-issue.

I would be very surprised if you could prove a measurable performance gain in a real world scenario by replacing the call to equals with an identity comparison in this case.

If you are interested in learning more about optimistic method inlining, then you can find good info here:  http://www.stanford.edu/class/cs343/resources/java-hotspot.pdf

Also, unless item is a boolean, the following expression is a syntax error:

 if (!item == object)

it should be written:

 if (item != object)

Just my 2c,

- thomas

You received this message because you are subscribed to the Google Groups "web4j-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to web4j-users...@googlegroups.com.

[John O'Hanley]

Hi,

Not sure we are speaking about the same issues on this one.

The reasoning behind using == instead of equals had no relation to a performance optimization. The reasoning was based on the semantics of what was going on.

To review:
Object x has an array field y.
The scenario being addressed here (as I understand it) is that y may have a reference back to object x. That is, there is 'eventual self-reference'.

That's the only scenario that I was trying to address. Hence the == (identity comparison) instead of equals (state comparison).

Using 'equals' would capture additional cases, in which x has an array y that references an x2 (a different object than x) that coincidentally has the same state as the original x. That's not a case of self-reference.

That's all.

 - John

[Thomas Hallgren]

While I'm sure that's your view on it, I'm not sure Jared shares it. At least not when he uses words like "cheaper" in the discussion. Hence my remark.

Another thing worries me is that the suggested improvement will still not detect self references that are more than one level deep. An object containing an array, which in turn contains an array, which in turn references the top level object will still go undetected and cause an endless recursion. The only way to prevent such recursion is to pass a list of parent objects down and then compare to that list. Just using the immediate parent doesn't fix the problem.

- thomas

[John O'Hanley]

Hi,

Yes, that's an excellent criticism. It only goes one level deep, and it doesn't cover the general case. But that's all I was trying to do - the first level, as you might find in a linked list.

I have updated the topic on hashCode on javapractices.com with a new version:
http://www.javapractices.com/topic/TopicAction.do?Id=28

If you can come up with a better version, that covers the general case of an object eventually referencing itself somewhere in an arbitrary object graph, then send it along, and I will take a look at it.

- John

[Jared Thomas]

Thomas,

thank you for your insight regarding the performance issue. My statement and the word "cheaper" was caused by not being aware of the "optimistic method call inlining" - something I'll definitely have a look into. 

As for the way it has been implemented in the HashCodeUtil by John, I reckon it better for it to be there, even in its current, one level deep form, than not to be there at all, although I too am interested in seeing a general case solution. I would've worked on it if it weren't for my current 'business', which is now shifted towards javascript.

More than anything though, I am extremely happy that I could make my first contribution in my life to an open source software. Thank you for this opportunity :-)

cheers

Jared