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