First of all, this bug is not a duplicate of 1032. After applying the patch provided in 1032, the 1032 test schema passes, but the schema attached to 1066 still fails.
There are 2 problems in Xerces' current implementation. The first one is, as Lucian correctly pointed out in 1032, that the order of sub-group-expansion is not specified (more a problem in the spec, as I mentioned in the first comment to this bug).
The second problem (what's really causing 1066) is that "pointless particle removal" happens before sub-group-expansion, as opposed to after, as specified in the spec.
To be more specific about point 2 (and to correct what I said in the first comment). For the schema attached above, after removal and expansion:
Base = ((X|X1|X2|X3)|Y)*
Restriction = (X1|X2|Y)*
Note that Base has nested choice groups and Restriction doesn't. Now when the "RecurseLax" rule is invoked, the 3 particles in Restriction need to map to 2 particles in the Base. Never possible, hence rejected.
So to me, the right fix needs to contain 2 parts:
1. expand sub-groups before pointless particle removal
2. disregard ordering for choices resulted from sub-group expansion.
[Patch analysis - 1032]
1032 patch sorts particles resulted from sub-group-expansion. This partially fixes the ordering problem, but not completely. It works when both base and restriction use sub-groups. After both are sorted, the "complete mapping" rule can be applied. But it doesn't work when one of the types uses sub-group and the other doesn't, because the type that doesn't use sub-group may have elements in arbitrary order.
Knowing the sorting strategy may help schema designers: when writing choices, try to sort them. This may or may not be appropriate for certain schema authors/designs, and may or may not work for different languages.
Overall, 1032 is a safe fix, it improves things, though doesn't fix the problem entirely. I'm willing to apply it unless a better/more complete solution is found.
[Patch analysis - 1066]
On the surface, Ignacio's patch works perfectly: both schemas from 1032 and 1066 are now accepted. But careful looking at the details reveals some rather serious problems.
For the 1032 schema, this patch works because both sub-groups are turned into this special MODELGROUP_SUBSTITUTIONGROUP and are handled specially (without worrying about the order).
For the 1066 schema, it works because it treats X1 (the element) as restricting the sub-group (X|X1|X2|X3) and X2 as restriction (X|X1|X2|X3) again. I would consider this as "works by luck".
The reason it's "luck" is because there are some schemas (valid and invalid) that this patch will give the wrong answer.
<xsd:element name="X1" substitutionGroup="X"/>
<xsd:element ref="X" minOccurs="0"/>
After expansion and removal,
Base = (X|X1|)?
Restriction = (X1|)?
(The last '|' is just to indicate it's a choice.)
The spec is clear that this is a valid restriction (RecurseLax). But 1066 patch would reject it, because now dType=choice and bType=subgroup, which is not handled by the big switch.
Similar to Case 1, but change the <choice> in "restriction" to <sequence>, it should still be valid (MapAndSum). But again, 1066 patch rejects it, for the same reason.
However valid this looks like (I just changed something from optional to mandatory), this is actually invalid in schema 1.0. (Note that schema 1.1  plans to replace the entire Particle Valid (Restriction) rule with a supposedly simple statement: it's a restriction as long as it accepts a subset.)
Base = ((X|Y|)?|Z)
Restriction = (X|Y|Z)
"X" and "Y" in restriction can not both map to (X|Y) in base, because RecurseLax requires an order-preserving mapping. So this should be invalid, but 1066 patch says it's valid. What causes this to fail to produce the correct result is actually the same as what was introduced to make the original 1066 test case happy. Namely the change in the method "checkRecurseLax" to reuse the base particle.
Though not working as a charm, this patch actually involves some creative thinking and is somewhat similar to some of my thoughts back in 2005 when 1066 was first opened (see below). Thanks for the effort and do keep trying. I sincerely hope that you beat me in finding the perfect solution.
My first attempt in 2005 was similar to your approaches in different aspects. I mark sub-group choices as special, and have a special method to handle the RecurseLax case when either choice came from a sub-group. This does a better job than the 1032 patch, because the special method discards order entirely, instead of using a specific order.
This attempt would have fixed 1032, but my focus was 1066 and it didn't work for 1066, because of the reason I mentioned earlier: expansion happened after removal.
My second attempt was to move the expansion to happen before removal, but encounter a big problem where expansion and removal don't seem to work together happily. Consider a choice
where B has X in its sub-group and D has Y in its sub-group. After expansion/removal, it becomes
Now we have to remember that the order between B and X doesn't matter, neither does that between D and Y. But the order does matter between A and B/X and so on.
This is where I stopped (it seemed too difficult to solve when no one was pressing ).
Ouch, it takes almost an entire day to analyze the problems (again), look at the patches, and re-gather my thoughts from last year, and of course, write this long comment. I'm glad that I'm writing things down this time so that I don't have to go through the same process again in the future. I will definitely give it some more thoughts. The least we can do is to commit Lucian's patch (or my attempt 1). Or to make expansion happen before removal + Lucian's patch. Though not complete, the latter should make both test cases from 1032 and 1066 happy.