1 /* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5 /* 6 * Copyright 2001-2004 The Apache Software Foundation. 7 * 8 * Licensed under the Apache License, Version 2.0 (the "License"); 9 * you may not use this file except in compliance with the License. 10 * You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 21 package com.sun.org.apache.xerces.internal.impl.xs.models; 22 23 import com.sun.org.apache.xerces.internal.impl.dtd.models.CMNode; 24 import com.sun.org.apache.xerces.internal.impl.xs.SchemaSymbols; 25 import com.sun.org.apache.xerces.internal.impl.xs.XSComplexTypeDecl; 26 import com.sun.org.apache.xerces.internal.impl.xs.XSDeclarationPool; 27 import com.sun.org.apache.xerces.internal.impl.xs.XSElementDecl; 28 import com.sun.org.apache.xerces.internal.impl.xs.XSModelGroupImpl; 29 import com.sun.org.apache.xerces.internal.impl.xs.XSParticleDecl; 30 31 /** 32 * This class constructs content models for a given grammar. 33 * 34 * @xerces.internal 35 * 36 * @author Elena Litani, IBM 37 * @author Sandy Gao, IBM 38 * 39 */ 40 public class CMBuilder { 41 42 // REVISIT: should update the decl pool to cache XSCM objects too 43 private XSDeclarationPool fDeclPool = null; 44 45 // It never changes, so a static member is good enough 46 private static XSEmptyCM fEmptyCM = new XSEmptyCM(); 47 48 // needed for DFA construction 49 private int fLeafCount; 50 // needed for UPA 51 private int fParticleCount; 52 //Factory to create Bin, Uni, Leaf nodes 53 private CMNodeFactory fNodeFactory ; 54 55 public CMBuilder(CMNodeFactory nodeFactory) { 56 fDeclPool = null; 57 fNodeFactory = nodeFactory ; 58 } 59 60 public void setDeclPool(XSDeclarationPool declPool) { 61 fDeclPool = declPool; 62 } 63 64 /** 65 * Get content model for the a given type 66 * 67 * @param typeDecl get content model for which complex type 68 * @return a content model validator 69 */ 70 public XSCMValidator getContentModel(XSComplexTypeDecl typeDecl) { 71 72 // for complex type with empty or simple content, 73 // there is no content model validator 74 short contentType = typeDecl.getContentType(); 75 if (contentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE || 76 contentType == XSComplexTypeDecl.CONTENTTYPE_EMPTY) { 77 return null; 78 } 79 80 XSParticleDecl particle = (XSParticleDecl)typeDecl.getParticle(); 81 82 // if the content is element only or mixed, but no particle 83 // is defined, return the empty content model 84 if (particle == null) 85 return fEmptyCM; 86 87 // if the content model contains "all" model group, 88 // we create an "all" content model, otherwise a DFA content model 89 XSCMValidator cmValidator = null; 90 if (particle.fType == XSParticleDecl.PARTICLE_MODELGROUP && 91 ((XSModelGroupImpl)particle.fValue).fCompositor == XSModelGroupImpl.MODELGROUP_ALL) { 92 cmValidator = createAllCM(particle); 93 } 94 else { 95 cmValidator = createDFACM(particle); 96 } 97 98 //now we are throught building content model and have passed sucessfully of the nodecount check 99 //if set by the application 100 fNodeFactory.resetNodeCount() ; 101 102 // if the validator returned is null, it means there is nothing in 103 // the content model, so we return the empty content model. 104 if (cmValidator == null) 105 cmValidator = fEmptyCM; 106 107 return cmValidator; 108 } 109 110 XSCMValidator createAllCM(XSParticleDecl particle) { 111 if (particle.fMaxOccurs == 0) 112 return null; 113 114 // get the model group, and add all children of it to the content model 115 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue; 116 // create an all content model. the parameter indicates whether 117 // the <all> itself is optional 118 XSAllCM allContent = new XSAllCM(particle.fMinOccurs == 0, group.fParticleCount); 119 for (int i = 0; i < group.fParticleCount; i++) { 120 // add the element decl to the all content model 121 allContent.addElement((XSElementDecl)group.fParticles[i].fValue, 122 group.fParticles[i].fMinOccurs == 0); 123 } 124 return allContent; 125 } 126 127 XSCMValidator createDFACM(XSParticleDecl particle) { 128 fLeafCount = 0; 129 fParticleCount = 0; 130 // convert particle tree to CM tree 131 CMNode node = useRepeatingLeafNodes(particle) ? buildCompactSyntaxTree(particle) : buildSyntaxTree(particle, true); 132 if (node == null) 133 return null; 134 // build DFA content model from the CM tree 135 return new XSDFACM(node, fLeafCount); 136 } 137 138 // 1. convert particle tree to CM tree: 139 // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+ 140 // a{n, m} -> a, a, ..., a?, a?, ... 141 // 3. convert model groups (a, b, c, ...) or (a | b | c | ...) to 142 // binary tree: (((a,b),c),...) or (((a|b)|c)|...) 143 // 4. make sure each leaf node (XSCMLeaf) has a distinct position 144 private CMNode buildSyntaxTree(XSParticleDecl particle, boolean optimize) { 145 146 int maxOccurs = particle.fMaxOccurs; 147 int minOccurs = particle.fMinOccurs; 148 short type = particle.fType; 149 CMNode nodeRet = null; 150 151 if ((type == XSParticleDecl.PARTICLE_WILDCARD) || 152 (type == XSParticleDecl.PARTICLE_ELEMENT)) { 153 // (task 1) element and wildcard particles should be converted to 154 // leaf nodes 155 // REVISIT: Make a clone of the leaf particle, so that if there 156 // are two references to the same group, we have two different 157 // leaf particles for the same element or wildcard decl. 158 // This is useful for checking UPA. 159 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++); 160 // (task 2) expand occurrence values 161 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs, optimize); 162 } 163 else if (type == XSParticleDecl.PARTICLE_MODELGROUP) { 164 // (task 1,3) convert model groups to binary trees 165 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue; 166 CMNode temp = null; 167 // when the model group is a choice of more than one particles, but 168 // only one of the particle is not empty, (for example 169 // <choice> 170 // <sequence/> 171 // <element name="e"/> 172 // </choice> 173 // ) we can't not return that one particle ("e"). instead, we should 174 // treat such particle as optional ("e?"). 175 // the following boolean variable is true when there are at least 176 // 2 non-empty children. 177 boolean twoChildren = false; 178 for (int i = 0; i < group.fParticleCount; i++) { 179 // first convert each child to a CM tree 180 temp = buildSyntaxTree(group.fParticles[i], 181 optimize && 182 minOccurs == 1 && maxOccurs == 1 && 183 (group.fCompositor == XSModelGroupImpl.MODELGROUP_SEQUENCE || 184 group.fParticleCount == 1)); 185 // then combine them using binary operation 186 if (temp != null) { 187 if (nodeRet == null) { 188 nodeRet = temp; 189 } 190 else { 191 nodeRet = fNodeFactory.getCMBinOpNode(group.fCompositor, nodeRet, temp); 192 // record the fact that there are at least 2 children 193 twoChildren = true; 194 } 195 } 196 } 197 // (task 2) expand occurrence values 198 if (nodeRet != null) { 199 // when the group is "choice", there is only one non-empty 200 // child, and the group had more than one children, we need 201 // to create a zero-or-one (optional) node for the non-empty 202 // particle. 203 if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE && 204 !twoChildren && group.fParticleCount > 1) { 205 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet); 206 } 207 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs, false); 208 } 209 } 210 211 return nodeRet; 212 } 213 214 // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+ 215 // a{n, m} -> a, a, ..., a?, a?, ... 216 // 4. make sure each leaf node (XSCMLeaf) has a distinct position 217 private CMNode expandContentModel(CMNode node, 218 int minOccurs, int maxOccurs, boolean optimize) { 219 220 CMNode nodeRet = null; 221 222 if (minOccurs==1 && maxOccurs==1) { 223 nodeRet = node; 224 } 225 else if (minOccurs==0 && maxOccurs==1) { 226 //zero or one 227 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node); 228 } 229 else if (minOccurs == 0 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) { 230 //zero or more 231 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, node); 232 } 233 else if (minOccurs == 1 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) { 234 //one or more 235 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node); 236 } 237 else if (optimize && node.type() == XSParticleDecl.PARTICLE_ELEMENT || 238 node.type() == XSParticleDecl.PARTICLE_WILDCARD) { 239 // Only for elements and wildcards, subsume e{n,m} and e{n,unbounded} to e* 240 // or e+ and, once the DFA reaches a final state, check if the actual number 241 // of elements is between minOccurs and maxOccurs. This new algorithm runs 242 // in constant space. 243 244 // TODO: What is the impact of this optimization on the PSVI? 245 nodeRet = fNodeFactory.getCMUniOpNode( 246 minOccurs == 0 ? XSParticleDecl.PARTICLE_ZERO_OR_MORE 247 : XSParticleDecl.PARTICLE_ONE_OR_MORE, node); 248 nodeRet.setUserData(new int[] { minOccurs, maxOccurs }); 249 } 250 else if (maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) { 251 // => a,a,..,a+ 252 // create a+ node first, then put minOccurs-1 a's in front of it 253 // for the first time "node" is used, we don't need to make a copy 254 // and for other references to node, we make copies 255 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node); 256 // (task 4) we need to call copyNode here, so that we append 257 // an entire new copy of the node (a subtree). this is to ensure 258 // all leaf nodes have distinct position 259 // we know that minOccurs > 1 260 nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE, 261 multiNodes(node, minOccurs-1, true), nodeRet); 262 } 263 else { 264 // {n,m} => a,a,a,...(a),(a),... 265 // first n a's, then m-n a?'s. 266 // copyNode is called, for the same reason as above 267 if (minOccurs > 0) { 268 nodeRet = multiNodes(node, minOccurs, false); 269 } 270 if (maxOccurs > minOccurs) { 271 node = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node); 272 if (nodeRet == null) { 273 nodeRet = multiNodes(node, maxOccurs-minOccurs, false); 274 } 275 else { 276 nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE, 277 nodeRet, multiNodes(node, maxOccurs-minOccurs, true)); 278 } 279 } 280 } 281 282 return nodeRet; 283 } 284 285 private CMNode multiNodes(CMNode node, int num, boolean copyFirst) { 286 if (num == 0) { 287 return null; 288 } 289 if (num == 1) { 290 return copyFirst ? copyNode(node) : node; 291 } 292 int num1 = num/2; 293 return fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE, 294 multiNodes(node, num1, copyFirst), 295 multiNodes(node, num-num1, true)); 296 } 297 298 // 4. make sure each leaf node (XSCMLeaf) has a distinct position 299 private CMNode copyNode(CMNode node) { 300 int type = node.type(); 301 // for choice or sequence, copy the two subtrees, and combine them 302 if (type == XSModelGroupImpl.MODELGROUP_CHOICE || 303 type == XSModelGroupImpl.MODELGROUP_SEQUENCE) { 304 XSCMBinOp bin = (XSCMBinOp)node; 305 node = fNodeFactory.getCMBinOpNode(type, copyNode(bin.getLeft()), 306 copyNode(bin.getRight())); 307 } 308 // for ?+*, copy the subtree, and put it in a new ?+* node 309 else if (type == XSParticleDecl.PARTICLE_ZERO_OR_MORE || 310 type == XSParticleDecl.PARTICLE_ONE_OR_MORE || 311 type == XSParticleDecl.PARTICLE_ZERO_OR_ONE) { 312 XSCMUniOp uni = (XSCMUniOp)node; 313 node = fNodeFactory.getCMUniOpNode(type, copyNode(uni.getChild())); 314 } 315 // for element/wildcard (leaf), make a new leaf node, 316 // with a distinct position 317 else if (type == XSParticleDecl.PARTICLE_ELEMENT || 318 type == XSParticleDecl.PARTICLE_WILDCARD) { 319 XSCMLeaf leaf = (XSCMLeaf)node; 320 node = fNodeFactory.getCMLeafNode(leaf.type(), leaf.getLeaf(), leaf.getParticleId(), fLeafCount++); 321 } 322 323 return node; 324 } 325 326 // A special version of buildSyntaxTree() which builds a compact syntax tree 327 // containing compound leaf nodes which carry occurence information. This method 328 // for building the syntax tree is chosen over buildSyntaxTree() when 329 // useRepeatingLeafNodes() returns true. 330 private CMNode buildCompactSyntaxTree(XSParticleDecl particle) { 331 int maxOccurs = particle.fMaxOccurs; 332 int minOccurs = particle.fMinOccurs; 333 short type = particle.fType; 334 CMNode nodeRet = null; 335 336 if ((type == XSParticleDecl.PARTICLE_WILDCARD) || 337 (type == XSParticleDecl.PARTICLE_ELEMENT)) { 338 return buildCompactSyntaxTree2(particle, minOccurs, maxOccurs); 339 } 340 else if (type == XSParticleDecl.PARTICLE_MODELGROUP) { 341 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue; 342 if (group.fParticleCount == 1 && (minOccurs != 1 || maxOccurs != 1)) { 343 return buildCompactSyntaxTree2(group.fParticles[0], minOccurs, maxOccurs); 344 } 345 else { 346 CMNode temp = null; 347 348 // when the model group is a choice of more than one particles, but 349 // only one of the particle is not empty, (for example 350 // <choice> 351 // <sequence/> 352 // <element name="e"/> 353 // </choice> 354 // ) we can't not return that one particle ("e"). instead, we should 355 // treat such particle as optional ("e?"). 356 // the following int variable keeps track of the number of non-empty children 357 int count = 0; 358 for (int i = 0; i < group.fParticleCount; i++) { 359 // first convert each child to a CM tree 360 temp = buildCompactSyntaxTree(group.fParticles[i]); 361 // then combine them using binary operation 362 if (temp != null) { 363 ++count; 364 if (nodeRet == null) { 365 nodeRet = temp; 366 } 367 else { 368 nodeRet = fNodeFactory.getCMBinOpNode(group.fCompositor, nodeRet, temp); 369 } 370 } 371 } 372 if (nodeRet != null) { 373 // when the group is "choice" and the group has one or more empty children, 374 // we need to create a zero-or-one (optional) node for the non-empty particles. 375 if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE && count < group.fParticleCount) { 376 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet); 377 } 378 } 379 } 380 } 381 return nodeRet; 382 } 383 384 private CMNode buildCompactSyntaxTree2(XSParticleDecl particle, int minOccurs, int maxOccurs) { 385 // Convert element and wildcard particles to leaf nodes. Wrap repeating particles in a CMUniOpNode. 386 CMNode nodeRet = null; 387 if (minOccurs == 1 && maxOccurs == 1) { 388 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++); 389 } 390 else if (minOccurs == 0 && maxOccurs == 1) { 391 // zero or one 392 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++); 393 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet); 394 } 395 else if (minOccurs == 0 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) { 396 // zero or more 397 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++); 398 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet); 399 } 400 else if (minOccurs == 1 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) { 401 // one or more 402 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++); 403 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet); 404 } 405 else { 406 // {n,m}: Instead of expanding this out, create a compound leaf node which carries the 407 // occurence information and wrap it in the appropriate CMUniOpNode. 408 nodeRet = fNodeFactory.getCMRepeatingLeafNode(particle.fType, particle.fValue, minOccurs, maxOccurs, fParticleCount++, fLeafCount++); 409 if (minOccurs == 0) { 410 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet); 411 } 412 else { 413 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet); 414 } 415 } 416 return nodeRet; 417 } 418 419 // This method checks if this particle can be transformed into a compact syntax 420 // tree containing compound leaf nodes which carry occurence information. Currently 421 // it returns true if each model group has minOccurs/maxOccurs == 1 or 422 // contains only one element/wildcard particle with minOccurs/maxOccurs == 1. 423 private boolean useRepeatingLeafNodes(XSParticleDecl particle) { 424 int maxOccurs = particle.fMaxOccurs; 425 int minOccurs = particle.fMinOccurs; 426 short type = particle.fType; 427 428 if (type == XSParticleDecl.PARTICLE_MODELGROUP) { 429 XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue; 430 if (minOccurs != 1 || maxOccurs != 1) { 431 if (group.fParticleCount == 1) { 432 XSParticleDecl particle2 = (XSParticleDecl) group.fParticles[0]; 433 short type2 = particle2.fType; 434 return ((type2 == XSParticleDecl.PARTICLE_ELEMENT || 435 type2 == XSParticleDecl.PARTICLE_WILDCARD) && 436 particle2.fMinOccurs == 1 && 437 particle2.fMaxOccurs == 1); 438 } 439 return (group.fParticleCount == 0); 440 } 441 for (int i = 0; i < group.fParticleCount; ++i) { 442 if (!useRepeatingLeafNodes(group.fParticles[i])) { 443 return false; 444 } 445 } 446 } 447 return true; 448 } 449 }