543898 - Traits resolution dependent on abc parsing order, not Domain hierarchy

Status: VERIFIED FIXED

(Tamarin Graveyard :: Virtual Machine, defect, P2)

Description

[Rick Reitmaier]

The implicit assumption built into the look-up logic of Domain.getNamedTraits() is that a parent trait will 'shadow' a child one.

But If the trait is added to the child Domain first, then code begins execution using this trait we can end up in a situation where the parent Domain adds a different with the same name and suddenly, this trait 'appears' during named look-ups.

see http://watsonexp.corp.adobe.com/#bug=2513781 for one example.

Comment 1

[Rick Reitmaier]

Attachment: ver 1

First cut at one possible solution...looking for feedback.

The idea with this patch is to prevent adding a traits to the name table if one with the same name already exists in any child Domain.

Comment 2

[Steven Johnson]

I see no obvious flaw, but this is pretty hairy stuff. Performance impact?

Comment 3

[Rick Reitmaier]

Performance probably not that bad, but yes in the wild with a 'fan-out' of children it could get hairy.

Comment 4

[Rick Reitmaier]

In a separate thread, Edwin suggested following Java's approach to resolution.   Making that change fixed the bug.

Two modifications are needed:  the lookup code changes from :

Traits *traits = NULL;
if (recursive && m_base) {
   traits = m_base->getNamedTraits(name, ns, true);
}
if (!traits) {
   traits = (Traits*) m_namedTraits->get(name, ns);
}

to:

Traits *traits = (Traits*) m_namedTraits->get(name, ns);
if (recursive && !traits && m_base) {
   traits = m_base->getNamedTraits(name, ns, true);
}        

Notice that we obtain the trait of the current Domain first, prior to recursing.    

Secondly, the 'add' logic (in AbcParser) would also require a slight modification in that it would perform a 'recursive' search up the Domain tree looking for an existing name;  currently it does a 'non-recursive' search.

Comment 5

[Steven Johnson]

(In reply to comment #4)
> In a separate thread, Edwin suggested following Java's approach to resolution. 

Assuming it doesn't introduce any subtle backwards incompatibilities, I like it.

Comment 6

[Rick Reitmaier]

Attachment: ver 1 - java lookup rules

Patch with Java lookup rules to compare with current

Comment 7

[Rick Reitmaier]

Lars proposed serializing the initialization of the swfs.   This approach would not work in this scenario since the swf in question only executes the 2nd doAbcTag after a UI component is clicked.  That is;
 (1) main swf loaded and first doAbcTag parsed
 (2) main swf draws to screen and playhead remains at frame 1 
 (3) first doAbcTag contains code that starts loading child swfs
 (4) child swfs define class(es) that are possibly available in the main swf (but not available until post-frame 1).
 (5) user clicks button
 (6) main swf advances to frame 2 and encounters 2nd doAbcTag .
 (7) main swf defines a class with the same name as found in a child swf during step (4) 

So, as much as I hate to say it, in order to preserve first-seen-first-used behaviour we probably need to resort to the first proposed patch.

Comment 8

[Rick Reitmaier]

Well I've convinced myself that the correct solution is to follow 
the Java class-loader lookup rules [hat-tip to Ed for suggestion],
and I'm looking for help to prove/disprove that this is the right decision.

The current code is already following these rules (at least from the 
view of the lookup logic) for all cases, except one.

The only exception is when we have an entry in a child and we then 
want to add an entry with the same name to the parent.

Under the current rules, the item is added, and we then start returning 
this parent item, for all queries.

The bug manifests because prior to this add, we would have returned 
the child item if queried from the child.

Under Java's rules, we would add the parent item *BUT* we'd continue to 
return the child item when requested from the child.  Requests from 
the parent would return the parent item.

I'm proposing 2 code changes; one to the lookup logic and one to the 
table addition logic.  

These two changes combined should net in one outwardly visible change 
to lookups; i.e the above mentioned scenario.

A couple of questions/comments:
(1) I would appreciate someone to review my logic / patch to ensure
    that my assertions are correct and no other outward effects 
    would be visible with this change.
(2) The change affects the xxxNamedTraits() methods should we also 
    change the xxxNamedScript() methods.

Comment 9

[Jeff Mott]

It seems like the right thing to do, but as Steven said - what's the compatibility story.  I've kind of lost the big picture here.  Is the bug being fixed an injection from the new Tamarin work, or did we ship it in 10.0?  The player's behavior in 10.1 should match that of 10.0.

Comment 10

[Rick Reitmaier]

Attachment: java lookup rules + cleanup

(1) Patch implementing lookup rules matching Java's.
(2) Choose to leave xxxNamedScript() methods as is.
(3) Took opportunity to clean up the proliferation of unused 'recursive' flags

Comment 11

[Rick Reitmaier]

(In reply to comment #9)
> It seems like the right thing to do, but as Steven said - what's the
> compatibility story.  

After analyzing all the cases, we should retain compatibility in all cases, except for the one that exhibits the failure mode.  

In this case, the current code produces a result that is timing dependent.  This patch locks down the behaviour to be deterministic.

> fixed an injection from the new Tamarin work

This bug has been in existence since Argo.  Interesting point though, I'll see what the rules looked like pre-Argo and report back.

Comment 12

[Rick Reitmaier]

Comment on attachment 427811 [details] [diff] [review]
java lookup rules + cleanup

Added a couple more to review.

Comment 13

[Steven Johnson]

Comment on attachment 427811 [details] [diff] [review]
java lookup rules + cleanup

r+ on the condition that we add a nice lengthy comment explicitly defining what the lookup rules are.

we should ideally also follow up with an acceptance test to exercise this somehow...

Comment 14

[Rick Reitmaier]

(In reply to comment #11)
> (In reply to comment #9)
> > It seems like the right thing to do, but as Steven said - what's the
> > compatibility story.  
> 
> This bug has been in existence since Argo.  Interesting point though, I'll see
> what the rules looked like pre-Argo and report back.

The rules are the same in Marlin, so it's been a latent bug that we're only now just tickling.

Comment 15

[Edwin Smith]

Comment on attachment 427811 [details] [diff] [review]
java lookup rules + cleanup

<caveat> this may very well be correct but the issues below prevent me from being able to tell by inspection that the code is correct.

AbcParser.cpp:1533 - should this be a plain addNamedTraits or should it be one that explicitly recurses before adding or explicitly doesn't recurse before adding?  (i'm not sure but the policy should be clear either way)

From a cursory overview, it is not clear that we're using the same policy for name insertion at all call sites of AbcParser::addNamedTraits.  I shudder to think about if (say) scripts use one lookup rule, and class instance types use a different lookup rule.

AbcParser.cpp:1887 - this is the only call site to PoolObject::getTraitsNoRecurse(), so the method should return bool and be called something more descriptive, perhaps traitsNotFound() or something.

Does the above call site implement the new policy correctly?  If a parent domain already has the type, then the child domain should not insert the new type but instead should preserve and return the parent's type, right?  seems like here we will insert the new type in the child domain's table whether the parent has it or not.

overall: this patch needs a comment that clearly describes the new name resolution policy.

Comment 16

[Jeff Mott]

Given that:

"we should retain compatibility in all cases, except for the one that exhibits the failure mode" 

and: 

"The rules are the same in Marlin, so it's been a latent bug that we're only now just tickling." 

I'm review+ from the player side. I'll leave the internal details to y'all to sort out.

Comment 17

[Rick Reitmaier]

(In reply to comment #15)

> AbcParser.cpp:1533 - should this be a plain addNamedTraits or should it be one
> that explicitly recurses before adding or explicitly doesn't recurse before
> adding? 

see below

> 
> AbcParser.cpp:1887 - this is the only call site to
> PoolObject::getTraitsNoRecurse(), so the method should return bool and be
> called something more descriptive, perhaps traitsNotFound() or something.
> 

The above two comments are related, as they apply to the same piece of code
which is:

 if (pool->getTraitsNoRecurse(name, ns) == NULL)
 {
    pool->addNamedTraits(name, ns, itraits);
 }

In this case we call into the pool object directly.  All other cases
of adding the trait use AbcParser.addNamedTraits() which contains
some non-trivial versioning logic.

For this reason, I believe the above calls which directly add a pool
entry are intentional.

Maybe others on this list can comment on this code, but I'm hesitant 
to change it to follow the new rules, without more data.

I can certainly rename the method, in fact I'd roll up the query and
add into a single call, say  'addUniqueNamedTrait()'

> 
> overall: this patch needs a comment that clearly describes the new name
> resolution policy.

Yes, Steven also mentioned this and I added the following comment 
to Domain.cpp ...

    // Domain lookup rules should always look for a name in their
    // table first prior to checking the parent.  Additionally,
    // a name is added to the table only if it is not found 
    // in the parent (recursively).
    //
    // If the rule was to return the trait found in a parent's 
    // table first, then we could end up in a situation where
    // one query would return the child's version and the next
    // query would return the parent's; assuming the parent's
    // version was added inbetween the queries.
    //

Comment 18

[Jeff Dyer]

(In reply to comment #16)
> Given that:
> 
> "we should retain compatibility in all cases, except for the one that exhibits
> the failure mode" 

How about this case:

SWFA loads SWFB; SWFB loads SWFC; SWFA and SWFB define class Foo; SWFC uses class Foo

The proposed patch appears to change the meaning of SWFC. In Marlin (and probably back to FP9) Foo would resolve to SWFA's Foo; with this fix it would resolve to SWFB's Foo.

I don't know how common this configuration is, but I wouldn't be surprised if it occurs in aggregation sites

Comment 19

[Rick Reitmaier]

(In reply to comment #18)

> How about this case:
> 
> SWFA loads SWFB; SWFB loads SWFC; SWFA and SWFB define class Foo; SWFC uses
> class Foo
> 
> The proposed patch appears to change the meaning of SWFC. In Marlin (and
> probably back to FP9) Foo would resolve to SWFA's Foo; with this fix it would
> resolve to SWFB's Foo.
>

Once SWFA's version of Foo is seen all other will use that version.  When SWFB tries to define Foo the trait will not be added to the table.

At least that is the intent, if there is a specific bug in the code, please point it out.

Comment 20

[Rick Reitmaier]

Attachment: Rewrite of code without changing any logic

This patch represents the 'clean-up' portion of the bug without any change to the look-up or addition rules.

It now becomes clear that there are 3 paths to adding a trait to a domain.

(1) PoolObject:667 the trait is added directly to the domain when it is not found in either the domain (incl. parent's) or pool's _namedTraits table.
 
(2) AbcParser:1887 the trait is added to the pool's _namedTraits when it is not found in the domain (not checking parent's) nor the pool's table.

(3) AbcParser:1553 trait is added to the domain if it is not found in the domain (incl. parent's).  This also contains versioning logic and appears to be the 'main' focal point for the majority of traits additions.

Summary
=======
- Fix (2) to follow rules identical to (1) and (3) 
- Combine the query/add call sequence for adding a trait into a atomic addUniqueTrait() call 
- modify lookup and addUniqueTrait() logic to follow rules outlined above. 


Details
======

(1) and (3) follow similar logic and will be affected in the same fashion by any rule change.

A further note on (1); it is called from resolvedParameterizedType() which creates a new name/vector-trait type and adds it to the domain wide table.   

On the other hand (2), which is within the function, parseInstanceInfos() , only affects the pool's _namedTraits.   Which makes sense since the parser only promotes (i.e. exposes to domain-wide) a subset of traits encountered, at a later point in parsing.

So as expected the search checks the pool's table, but oddly, it limits the domain search to the immediate domain, not searching the parent's ?!?.   The latter appears to be a bug.   

Looking at where _namedTraits is used; getBuiltinTraits() and getTraits(), the former being only used by builtins macros.  Interestingly, getBuiltinTraits() only works because our builtin pool exists with a domain whose base is null.    I'll add an assert with the above comment to a subsequent patch.

For the latter, the current rules imply that a given trait would be visible unless one was later added to the domain (or the parent's domain) at which point the query would return the domain's version.  This is a similar problem to the issue being addressed in the bug.

A couple of options off the top of my head; 

(a) we could always add the trait to the _namedTraits table (avoiding duplicates of course) without ever checking the Domain.   Subsequent queries will always look into the domain tables first anyway, so the only loss is the expense of memory.   But this might prove fragile, as we might have names in the table that should *never* be used.   I.e. a duplicate trait exists in the _namedTraits table, but when we do a getTraits() look-up we get the domain visible one.

(b) only add the trait to the table if the getTraits() query returns null.  This would be consistent with (1) and (3) and avoids the memory issue.  Performance may be impacted somewhat, since we are now adding a linear search up the Domain tree for each class.  But, frankly we are already doing such calls for both the base class and each interface, so it seems reasonable to assume the overhead is negligible.

Also, In the final patch I think its a good idea to remove Domain.addNamedTrait() and combine the query and the addition into a single atomic call, this will ensure that the rules for adding a new trait are consistent and contained.



more visible

Comment 21

[Rick Reitmaier]

Attachment: Remove recursion flag from PoolObject getTraits() calls

Breaking the work into smaller bite-sized chunks that transform the logic making the 'final' fix patch easier.

This patch removes the 'recursive' flag from PoolObject and moves implementation from Domain.h

Comment 22

[Rick Reitmaier]

Attachment: Remove recursion flag from Domain

Cleans up Domain (the 2nd patch in the series).

Comment 23

[Rick Reitmaier]

Attachment: Remove addNamedTrait replaced with check and add.

3rd patch in the sequence.  Consolidates the non-recursive lookup and addition of a trait into a single Domain call.

The PoolObject call-site substitutes addNamedTrait which is safe, since the prior pool->getTraits() call has already confirmed that the trait does not reside in the domain.

Comment 24

[Rick Reitmaier]

Attachment: Move parameterized vector code

Moving parameterized vector code for clean-up.  

We should probably also modify this code, as it appears that it is not 'verion-ized'.  But that would be done in a separate bug, for now let's just cordon it off.

Comment 25

[Rick Reitmaier]

Attachment: Final patch containing rules changes

Final patch, in the sequence of 5.

Here we apply the final rule changes,  I'll be adding comments to the top of the file, but for now I wanted to get the code change out there so others can review and comment on the change.

Comment 26

[Edwin Smith]

(In reply to comment #20)


> A couple of options off the top of my head; 
> 
> (a) we could always add the trait to the _namedTraits table (avoiding
> duplicates of course) without ever checking the Domain.
> 
> (b) only add the trait to the table if the getTraits() query returns null. 
> This would be consistent with (1) and (3) and avoids the memory issue.

(b) sounds right to me.  is that what these final patches implement?

Comment 27

[Edwin Smith]

Comment on attachment 429192 [details] [diff] [review]
Remove addNamedTrait replaced with check and add.

addUniqueTrait() should be named addUniqueTraitNoRecurse(), but it might be moot if the function goes away after the remaining patches are applied().

with the new policy, it still seems sketchy that we'd have any add operation that doesn't check the parent domains first.

Comment 28

[Rick Reitmaier]

(In reply to comment #26)
> (In reply to comment #20)
> 
> (b) only add the trait to the table if the getTraits() query returns null. 
> > This would be consistent with (1) and (3) and avoids the memory issue.
> 
> (b) sounds right to me.  is that what these final patches implement?

Yes, (b) is implemented in attachment 429434 [details] [diff] [review], all the other patches are just code re-writing and moving in preparation for this patch.

Comment 29

[Rick Reitmaier]

(In reply to comment #27)
> (From update of attachment 429192 [details] [diff] [review])
> addUniqueTrait() should be named addUniqueTraitNoRecurse(), but it might be
> moot if the function goes away after the remaining patches are applied().
> 
> with the new policy, it still seems sketchy that we'd have any add operation
> that doesn't check the parent domains first.

Right, the final patch does away with the non-recursive version(s), leaving only a single addUniqueTrait() function.

Comment 30

[Rick Reitmaier]

pushed patches 1-4 :
http://hg.mozilla.org/tamarin-redux/rev/a9cef6653d4e
http://hg.mozilla.org/tamarin-redux/rev/6714dde2fe9f
http://hg.mozilla.org/tamarin-redux/rev/ff9324bf39dd
http://hg.mozilla.org/tamarin-redux/rev/8276eb2e068d

Comment 31

[Jeff Dyer]

Comment on attachment 429434 [details] [diff] [review]
Final patch containing rules changes

nit: the contract on getUniqueTraits has changed. I think I like the old contract (return NULL if added) rather than the new one (returning the original traits) because it seems a little less subtle

Comment 32

[Edwin Smith]

Comment on attachment 429434 [details] [diff] [review]
Final patch containing rules changes

I'm marking the patch R+ because it does seem to fix the type lookup policy between child/parent domains.  

However, this bug is still broken, because:

Problem #1: PoolObject._namedTraits is a type table that shadows the one in Domain.  One would expect this pool-owned table to have the same policy that a subdomain table would have:  ADD checks parent first (i.e. resolves top-down), and GET checks child first (resolves bottom-up).  However, PoolObject::getTraits() checks parent [domain] first, before checking child [this->_namedTraits].

Sketch of the bug:
1. add T1 (named "T") to PoolObject.namedTraits
2. pool->getTrait("T") => T1
3. add T2 (named "T") to pool->domain
4. P1->getTrait("T") => T2

After some searching, it appears that step 3 might not be possible, because in AbcParser::parseTraits, we also add ("T", T1) to pool->domain, which would prevent #3 from inserting T2.  however, we have a subtle cooperation between AbcParser, PoolObject, and Domain, to make this work, which is fragile as heck.

Problem #2:  Domain.getNamedScript() checks parent first, unlike getNamedTraits().  It is very important that name resolution works the same way for both tables.  Also, addNamedScript() doesn't check any table first, it relies on the caller to do so.  Too fragile!  There should be obvious symmetry between the namedScripts tables and namedTraits tables.

Problem #3:  we have unchecked, unbounded recursion in Domain.getNamedTraits() and getNamedScript().

Problem #4: get/add ParameterizedType() also don't appear to follow the same name resolution policy.  If there is a good reason, it needs to be written down.  If not, these methods also need to be fixed.  At minimum, it appears that we can end up with a differently defined Vector<T> in each domain that can resolve T, for each unique T (one would expect a 1-1 relationship between Vector<T> and T, but we apparently have a many-to-1 relationship).

Comment 33

[Edwin Smith]

(In reply to comment #32)
> Problem #3:  we have unchecked, unbounded recursion in Domain.getNamedTraits()
> and getNamedScript().

added bug 551004

Comment 34

[Rick Reitmaier]

These patches fix a very specific problem dealing with the interaction between Traits and Domain.  

There are remaining issues with Scripts and with the PoolObject that need to be resolved.

However, I would suggest that we clean them up each as separate independent fixes.

The script issue is addressed in newly opened bug 551112 (#2), the parameterized vector issue is described in 549651 (#4).

#1.  Yes the policy remains the same for PoolObject.  In regards to this not being an issue, I've opened bug 551116 since we should at least consolidate the rules.

Re: problem #3 , agreed, this is worthwhile cleanup.

Comment 35

[Rick Reitmaier]

pushed http://hg.mozilla.org/tamarin-redux/rev/9fc7425863e9

Comment 36

[Chris Peyer]

verified in argo.  Also verified that watson issue is fixed.