Hi, DeepTraverser is small (427 lines of code including comments and tests) and robust in that it deals with cycles, but it does not have support for limiting the depth of the search. Efficiency is not its strength, and it would be great if someone would review it.
I think something like this should be integrated in Pharo because it is so convenient for quick prototyping. The original post that describes it is here: http://www.humane-assessment.com/blog/traversal-enabled-pharo-objects/ Cheers, Doru On Mon, Feb 16, 2015 at 11:48 PM, Sven Van Caekenberghe <[email protected]> wrote: > > > On 16 Feb 2015, at 23:32, Nicolai Hess <[email protected]> wrote: > > > > 2015-02-05 16:02 GMT+01:00 Sven Van Caekenberghe <[email protected]>: > > > > > On 05 Feb 2015, at 15:44, Nicolai Hess <[email protected]> wrote: > > > > > > 2015-02-02 3:03 GMT+01:00 Eliot Miranda <[email protected]>: > > > > > > > > > On Sun, Feb 1, 2015 at 3:39 AM, Nicolai Hess <[email protected]> > wrote: > > > > > > > > > 2015-02-01 10:52 GMT+01:00 Ben Coman <[email protected]>: > > > > > > 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/[email protected]/msg25156.html > > > > > > > > > > > > > > > -- > > > best, > > > Eliot > > > -- www.tudorgirba.com "Every thing has its own flow"
