1 /* 2 * Copyright 2006 Sony Computer Entertainment Inc. 3 * 4 * Licensed under the MIT Open Source License, for details please see license.txt or the website 5 * http://www.opensource.org/licenses/mit-license.php 6 * 7 */ 8 9 #include <list> 10 #include <vector> 11 #include <sstream> 12 #include <algorithm> 13 #include <dae/daeSIDResolver.h> 14 #include <dae/daeIDRef.h> 15 #include <dae/daeAtomicType.h> 16 #include <dae/daeMetaAttribute.h> 17 #include <dae/daeMetaElement.h> 18 #include <dae/daeURI.h> 19 #include <dom/domTypes.h> 20 #include <dom/domConstants.h> 21 #include <dae/daeDocument.h> 22 #include <dae/daeDatabase.h> 23 #include <dae/daeUtils.h> 24 #include <dom/domSource.h> 25 26 using namespace std; 27 28 29 namespace { 30 template<typename T> 31 T nextIter(const T& iter) { 32 T next = iter; 33 return ++next; 34 } 35 36 template<typename T> 37 T moveIter(const T& iter, int n) { 38 T result = iter; 39 advance(result, n); 40 return result; 41 } 42 43 // Implements a breadth-first sid search by starting at the container element and 44 // traversing downward through the element tree. 45 daeElement* findSidTopDown(daeElement* container, const string& sid, const string& profile) { 46 if (!container) 47 return NULL; 48 49 vector<daeElement*> elts, matchingElts; 50 elts.push_back(container); 51 52 for (size_t i = 0; i < elts.size(); i++) { 53 daeElement* elt = elts[i]; 54 55 // Bail if we're looking for an element in a different profile 56 if (!profile.empty()) { 57 if (strcmp(elt->getElementName(), COLLADA_ELEMENT_TECHNIQUE_COMMON) == 0) 58 continue; 59 if (strcmp(elt->getElementName(), COLLADA_ELEMENT_TECHNIQUE) == 0 && 60 profile != elt->getAttribute("profile")) 61 continue; 62 } 63 64 // See if this is a matching element 65 if (elt->getAttribute("sid") == sid) 66 return elt; 67 else { 68 // Add the children to the list of elements to check 69 daeElementRefArray children; 70 elt->getChildren(children); 71 for (size_t j = 0; j < children.getCount(); j++) 72 elts.push_back(children[j]); 73 } 74 } 75 76 return NULL; 77 } 78 79 // Returns the distance between an element and an ancestor of the element. If 'container 80 // isn't an ancestor of 'elt', or if 'elt' is in a profile that doesn't match 'profile' 81 // UINT_MAX is returned. 82 unsigned int computeDistance(daeElement* container, daeElement* elt, const string& profile) { 83 if (!container || !elt) 84 return UINT_MAX; 85 86 unsigned int distance = 0; 87 do { 88 // Bail if we're looking for an element in a different profile 89 if (!profile.empty()) { 90 if (strcmp(elt->getElementName(), COLLADA_ELEMENT_TECHNIQUE_COMMON) == 0) 91 return UINT_MAX; 92 if (strcmp(elt->getElementName(), COLLADA_ELEMENT_TECHNIQUE) == 0 && 93 profile != elt->getAttribute("profile")) 94 return UINT_MAX; 95 } 96 97 if (elt == container) 98 return distance; 99 distance++; 100 } while ((elt = elt->getParentElement()) != NULL); 101 102 return UINT_MAX; 103 } 104 105 // Implements a breadth-first sid search by using the database to find all elements 106 // matching 'sid', then finding the element closest to 'container'. 107 daeElement* findSidBottomUp(daeElement* container, const string& sid, const string& profile) { 108 if (!container || !container->getDocument()) 109 return NULL; 110 111 // Get the elements with a matching sid 112 vector<daeElement*> elts; 113 container->getDocument()->getDAE()->getDatabase()->sidLookup(sid, elts, container->getDocument()); 114 115 // Compute the distance from each matching element to the container element 116 unsigned int minDistance = UINT_MAX; 117 daeElement* closestElt = NULL; 118 for (size_t i = 0; i < elts.size(); i++) { 119 unsigned int distance = computeDistance(container, elts[i], profile); 120 if (distance < minDistance) { 121 minDistance = distance; 122 closestElt = elts[i]; 123 } 124 } 125 126 return closestElt; 127 } 128 129 daeElement* findID(daeElement* elt, const string& id, const string& profile) { 130 return elt ? elt->getDAE()->getDatabase()->idLookup(id, elt->getDocument()) : NULL; 131 } 132 133 void buildString(const list<string>::iterator& begin, 134 const list<string>::iterator& end, 135 string& result) { 136 ostringstream stream; 137 for (list<string>::iterator iter = begin; iter != end; iter++) 138 stream << *iter; 139 result = stream.str(); 140 } 141 142 // Finds an element with a matching ID or sid (depending on the 'finder' function) 143 // passed in. First it tries to resolve the whole ID/sid, then it tries to resolve 144 // successively smaller parts. For example, consider this sid ref: "my.sid.ref". 145 // First this function will try to resolve "my.sid.ref" entirely, then if that 146 // fails it'll try to resolve "my.sid.", "my.sid", "my.", and "my", in that order. 147 // The part that wasn't matched is returned in the 'remainingPart' parameter. 148 daeElement* findWithDots(daeElement* container, 149 const string& s, 150 const string& profile, 151 daeElement* (*finder)(daeElement*, const string&, const string&), 152 list<string>& remainingPart) { 153 remainingPart.clear(); 154 155 // First see if the whole thing resolves correctly 156 if (daeElement* result = finder(container, s, profile)) 157 return result; 158 159 // It didn't resolve. Let's tokenize it by '.'s and see if we can resolve a 160 // portion of it. 161 cdom::tokenize(s, ".", remainingPart, true); 162 if (remainingPart.size() == 1) 163 return NULL; // There were no '.'s, so the result won't be any different 164 165 list<string>::iterator iter = moveIter(remainingPart.end(), -1); 166 for (int i = int(remainingPart.size())-1; i >= 1; i--, iter--) { 167 string substr; 168 buildString(remainingPart.begin(), iter, substr); 169 if (daeElement* result = finder(container, substr, profile)) { 170 // Remove the part we matched against from the list 171 remainingPart.erase(remainingPart.begin(), iter); 172 return result; 173 } 174 } 175 176 remainingPart.clear(); 177 return NULL; 178 } 179 180 daeSidRef::resolveData resolveImpl(const daeSidRef& sidRef) { 181 if (sidRef.sidRef.empty() || !sidRef.refElt) 182 return daeSidRef::resolveData(); 183 184 daeSidRef::resolveData result; 185 string separators = "/()"; 186 list<string> tokens; 187 cdom::tokenize(sidRef.sidRef, separators, /* out */ tokens, true); 188 189 list<string>::iterator tok = tokens.begin(); 190 191 // The first token should be either an ID or a '.' to indicate 192 // that we should start the search from the container element. 193 if (tok == tokens.end()) 194 return daeSidRef::resolveData(); 195 196 list<string> remainingPart; 197 if (*tok == ".") { 198 result.elt = sidRef.refElt; 199 tok++; 200 } else { 201 // Try to resolve it as an ID 202 result.elt = findWithDots(sidRef.refElt, *tok, sidRef.profile, findID, remainingPart); 203 if (result.elt) { 204 if (!remainingPart.empty()) { 205 // Insert the "remaining part" from the ID resolve into our list of tokens 206 tokens.erase(tokens.begin()); 207 tokens.splice(tokens.begin(), remainingPart); 208 tok = tokens.begin(); 209 } else 210 tok++; 211 } 212 } 213 214 if (!result.elt) 215 return daeSidRef::resolveData(); 216 217 // Next we have an optional list of SIDs, each one separated by "/". Once we hit one of "()", 218 // we know we're done with the SID section. 219 for (; tok != tokens.end() && *tok == "/"; tok++) { 220 tok++; // Read the '/' 221 if (tok == tokens.end()) 222 return daeSidRef::resolveData(); 223 224 // Find the element matching the SID 225 result.elt = findWithDots(result.elt, *tok, sidRef.profile, findSidTopDown, remainingPart); 226 if (!result.elt) 227 return daeSidRef::resolveData(); 228 229 if (!remainingPart.empty()) { 230 list<string>::iterator tmp = tok; 231 tok--; 232 tokens.splice(tmp, remainingPart); 233 tokens.erase(tmp); 234 } 235 } 236 237 // Now we want to parse the member selection tokens. It can either be 238 // (a) '.' followed by a string representing the member to access 239 // (b) '(x)' where x is a number, optionally followed by another '(x)' 240 // Anything else is an error. 241 string member; 242 bool haveArrayIndex1 = false, haveArrayIndex2 = false; 243 int arrayIndex1 = -1, arrayIndex2 = -1; 244 if (tok != tokens.end()) { 245 if (*tok == ".") { 246 tok++; 247 if (tok == tokens.end()) 248 return daeSidRef::resolveData(); 249 member = *tok; 250 tok++; 251 } 252 else if (*tok == "(") { 253 tok++; 254 if (tok == tokens.end()) 255 return daeSidRef::resolveData(); 256 257 istringstream stream(*tok); 258 stream >> arrayIndex1; 259 haveArrayIndex1 = true; 260 if (!stream.good() && !stream.eof()) 261 return daeSidRef::resolveData(); 262 tok++; 263 if (tok == tokens.end() || *tok != ")") 264 return daeSidRef::resolveData(); 265 tok++; 266 267 if (tok != tokens.end() && *tok == "(") { 268 tok++; 269 if (tok == tokens.end()) 270 return daeSidRef::resolveData(); 271 272 stream.clear(); 273 stream.str(*tok); 274 stream >> arrayIndex2; 275 haveArrayIndex2 = true; 276 if (!stream.good() && !stream.eof()) 277 return daeSidRef::resolveData(); 278 tok++; 279 if (tok == tokens.end() || *tok != ")") 280 return daeSidRef::resolveData(); 281 tok++; 282 } 283 } 284 } 285 286 // We shouldn't have any tokens left. If we do it's an error. 287 if (tok != tokens.end()) 288 return daeSidRef::resolveData(); 289 290 // At this point we've parsed a correctly formatted SID reference. The only thing left is to resolve 291 // the member selection portion of the SID ref. First, see if the resolved element has a float array we 292 // can use. 293 if (result.elt->typeID() == domSource::ID()) { 294 if (domFloat_array* floatArray = ((domSource*)result.elt)->getFloat_array()) 295 result.array = (daeDoubleArray*)floatArray->getCharDataObject()->get(floatArray); 296 } 297 else 298 { 299 daeMetaAttribute *ma = result.elt->getCharDataObject(); 300 if ( ma != NULL ) { 301 if ( ma->isArrayAttribute() && ma->getType()->getTypeEnum() == daeAtomicType::DoubleType ) { 302 result.array = (daeDoubleArray*)ma->get( result.elt ); 303 } 304 } 305 } 306 307 if( result.array ) { 308 // We have an array to use for indexing. Let's see if the SID ref uses member selection. 309 if (!member.empty()) { 310 // Do member lookup based on the constants defined in the COMMON profile 311 if (member == "ANGLE") { 312 result.scalar = &(result.array->get(3)); 313 } else if (member.length() == 1) { 314 switch(member[0]) { 315 case 'X': 316 case 'R': 317 case 'U': 318 case 'S': 319 result.scalar = &(result.array->get(0)); 320 break; 321 case 'Y': 322 case 'G': 323 case 'V': 324 case 'T': 325 result.scalar = &(result.array->get(1)); 326 break; 327 case 'Z': 328 case 'B': 329 case 'P': 330 result.scalar = &(result.array->get(2)); 331 break; 332 case 'W': 333 case 'A': 334 case 'Q': 335 result.scalar = &(result.array->get(3)); 336 break; 337 }; 338 } 339 } else if (haveArrayIndex1) { 340 // Use the indices to lookup a value in the array 341 if (haveArrayIndex2 && result.array->getCount() == 16) { 342 // We're doing a matrix lookup. Make sure the index is valid. 343 int i = arrayIndex1*4 + arrayIndex2; 344 if (i >= 0 && i < int(result.array->getCount())) 345 result.scalar = &(result.array->get(i)); 346 } else { 347 // Vector lookup. Make sure the index is valid. 348 if (arrayIndex1 >= 0 && arrayIndex1 < int(result.array->getCount())) 349 result.scalar = &(result.array->get(arrayIndex1)); 350 } 351 } 352 } 353 354 // If we tried to do member selection but we couldn't resolve it to a doublePtr, fail. 355 if ((!member.empty() || haveArrayIndex1) && result.scalar == NULL) 356 return daeSidRef::resolveData(); 357 358 // SID resolution was successful. 359 return result; 360 } 361 } // namespace { 362 363 364 daeSidRef::resolveData::resolveData() : elt(NULL), array(NULL), scalar(NULL) { } 365 366 daeSidRef::resolveData::resolveData(daeElement* elt, daeDoubleArray* array, daeDouble* scalar) 367 : elt(elt), 368 array(array), 369 scalar(scalar) { } 370 371 372 daeSidRef::daeSidRef() : refElt(NULL) { } 373 374 daeSidRef::daeSidRef(const string& sidRef, daeElement* referenceElt, const string& profile) 375 : sidRef(sidRef), 376 refElt(referenceElt), 377 profile(profile) { } 378 379 bool daeSidRef::operator<(const daeSidRef& other) const { 380 if (refElt != other.refElt) 381 return refElt < other.refElt; 382 if (sidRef != other.sidRef) 383 return sidRef < other.sidRef; 384 return profile < other.profile; 385 } 386 387 daeSidRef::resolveData daeSidRef::resolve() { 388 if (!refElt) 389 return daeSidRef::resolveData(); 390 391 // First check the cache 392 daeSidRef::resolveData result = refElt->getDAE()->getSidRefCache().lookup(*this); 393 if (result.elt) 394 return result; 395 396 // Try to resolve as an effect-style sid ref by prepending "./" to the sid ref. 397 // If that fails, try resolving as an animation-style sid ref, where the first part is an ID. 398 result = resolveImpl(daeSidRef(string("./") + sidRef, refElt, profile)); 399 if (!result.elt) 400 result = resolveImpl(*this); 401 402 if (result.elt) // Add the result to the cache 403 refElt->getDAE()->getSidRefCache().add(*this, result); 404 405 return result; 406 } 407 408 409 daeSIDResolver::daeSIDResolver( daeElement *container, daeString target, daeString profile ) 410 : container(NULL) 411 { 412 setContainer(container); 413 setTarget(target); 414 setProfile(profile); 415 } 416 417 daeString daeSIDResolver::getTarget() const { 418 return target.empty() ? NULL : target.c_str(); 419 } 420 421 void daeSIDResolver::setTarget( daeString t ) 422 { 423 target = t ? t : ""; 424 } 425 426 daeString daeSIDResolver::getProfile() const { 427 return profile.empty() ? NULL : profile.c_str(); 428 } 429 430 void daeSIDResolver::setProfile( daeString p ) 431 { 432 profile = p ? p : ""; 433 } 434 435 daeElement* daeSIDResolver::getContainer() const { 436 return container; 437 } 438 439 void daeSIDResolver::setContainer(daeElement* element) 440 { 441 container = element; 442 } 443 444 daeSIDResolver::ResolveState daeSIDResolver::getState() const { 445 if (target.empty()) 446 return target_empty; 447 448 daeSidRef::resolveData result = daeSidRef(target, container, profile).resolve(); 449 if (!result.elt) 450 return sid_failed_not_found; 451 if (result.scalar) 452 return sid_success_double; 453 if (result.array) 454 return sid_success_array; 455 456 return sid_success_element; 457 } 458 459 daeElement* daeSIDResolver::getElement() 460 { 461 return daeSidRef(target, container, profile).resolve().elt; 462 } 463 464 daeDoubleArray *daeSIDResolver::getDoubleArray() 465 { 466 return daeSidRef(target, container, profile).resolve().array; 467 } 468 469 daeDouble *daeSIDResolver::getDouble() 470 { 471 return daeSidRef(target, container, profile).resolve().scalar; 472 } 473 474 475 daeSidRefCache::daeSidRefCache() : hitCount(0), missCount(0) { } 476 477 daeSidRef::resolveData daeSidRefCache::lookup(const daeSidRef& sidRef) { 478 map<daeSidRef, daeSidRef::resolveData>::iterator iter = lookupTable.find(sidRef); 479 if (iter != lookupTable.end()) { 480 hitCount++; 481 return iter->second; 482 } 483 missCount++; 484 return daeSidRef::resolveData(); 485 } 486 487 void daeSidRefCache::add(const daeSidRef& sidRef, const daeSidRef::resolveData& result) { 488 lookupTable[sidRef] = result; 489 } 490 491 void daeSidRefCache::clear() { 492 lookupTable.clear(); 493 hitCount = missCount = 0; 494 } 495 496 bool daeSidRefCache::empty() { 497 return lookupTable.empty(); 498 } 499 500 int daeSidRefCache::misses() { 501 return missCount; 502 } 503 504 int daeSidRefCache::hits() { 505 return hitCount; 506 } 507