On 16 Feb 2015, at 23:32, Nicolai Hess <nicolaihess@web.de> wrote:
2015-02-05 16:02 GMT+01:00 Sven Van Caekenberghe <sven@stfx.eu>:
On 05 Feb 2015, at 15:44, Nicolai Hess <nicolaihess@web.de> wrote:
2015-02-02 3:03 GMT+01:00 Eliot Miranda <eliot.miranda@gmail.com>:
On Sun, Feb 1, 2015 at 3:39 AM, Nicolai Hess <nicolaihess@web.de> wrote:
2015-02-01 10:52 GMT+01:00 Ben Coman <btc@openinworld.com>:
Looking into Image locking problems [1] caused by a recursive array such as this...
literalArray := #( 1 2 3 ). literalArray at: 3 put: literalArray.
I find that "literalArray printString" locks the image due to Array>>printOn: use of the recursive #shouldBePrintedAsLiteral method. Now its implementation is identical to #isLiteral and indeed "literalArray isLiteral" also locks the Image. So comparing implementors of #isLiteral...
Squeak uses a Set to store all visited elements for shouldBePrintedAsLiteral and this protects against the recursive loop.
shouldBePrintedAsLiteralVisiting: aSet self class == Array ifFalse: [^false]. (aSet includes: self) ifTrue: [^false]. aSet add: self. ^self allSatisfy: [:each | each shouldBePrintedAsLiteralVisiting: aSet]
isn't there a common pattern to handle this kind of potential endless recursion?
At Cadence we fixed it thus:
Object>>shouldBePrintedAsLiteral
^self isLiteral
Array>>shouldBePrintedAsLiteral
^self class == Array and: [self shouldBePrintedAsLiteralVisiting: (IdentitySet new: 8)]
Object>>shouldBePrintedAsLiteralVisiting: aSet
^self isLiteral
Array>>shouldBePrintedAsLiteralVisiting: aSet self class == Array ifFalse: [^false]. (aSet includes: self) ifTrue: [^false]. aSet add: self. ^self allSatisfy: [:each | each shouldBePrintedAsLiteralVisiting: aSet]
Is there something more "generic". Something we can use for any object tracing. Isn't there something the GC uses? The GC obviously does not fall into this loop. (It flags visited objects, but there is nothing exposed that can be used at the image level?) How do ImageSegment or Fuel work with recursive structures?
In Moose there is DeepTraverser which does something similar it seems.
FUEL & STON do this too.
How is it done in Fuel and STON ? Do they both use DeepTraverser, or is there another implementation in Fuel and another one in STON?
They both have their own implementation. The actual traversal is not that difficult, doing it efficiently is a bit harder. Getting all the edge cases of the total algorithm (the serialisation) right is a more work. I am not familiar with DeepTraverser, I just know it exists.
Nicolai
Object>>isLiteral ^false Boolean>>isLiteral ^true Character>>isLiteral ^true Integer>>isLiteral ^true String>>isLiteral ^true UndefinedObject>>isLiteral ^true
ByteArray>>isLiteral ^self class == ByteArray Float>>isLiteral ^self isFinite "^(self - self) = 0.0" ScaledDecimal>>isLiteral ^denominator = 1 or: [(10 raisedTo: scale)\\denominator = 0]
Array>>isLiteral ^self class == Array and: [self allSatisfy: [:each | each isLiteral]]
...I find most are very basic (might even say deterministic), with the recursion of Array>>isLiteral seeming an annomaly. Also, the big IF condition in Array>>printOn: smells like a design decision being made at runtime (Valloud AMCOS p12).
Array>>printOn: aStream self shouldBePrintedAsLiteral ifTrue: [self printAsLiteralFormOn: aStream. ^ self]. self isSelfEvaluating ifTrue: [self printAsSelfEvaluatingFormOn: aStream. ^ self]. super printOn: aStream
Flipping between two printString formats seems like selecting between two class types. Indeed, if we had a LiteralArray class, there would be no need for its printOn: to recursively search to determine its form, thus allowing #printStringLimitedTo: to do its thing to protect against infinite recursion.
Also, instead of a recursive Array>>isLiteral we'd have something like LiteralArray>>isLiteral ^true Array>>isLiteral ^false which seems to align much better with the pattern of the other #isLiteral implementors.
I notice there is both RBArrayNode and RBLiteralArrayNode.
So what are the wider concerns that might apply? (In particular, I'm not sure how the #isSelfEvaluating (which is also recursive) fits into the big picture)
cheers -ben
[1] https://www.mail-archive.com/pharo-dev@lists.pharo.org/msg25156.html
-- best, Eliot