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>
nextIter(const T & iter)31 T nextIter(const T& iter) {
32 T next = iter;
33 return ++next;
34 }
35
36 template<typename T>
moveIter(const T & iter,int n)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.
findSidTopDown(daeElement * container,const string & sid,const string & profile)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.
computeDistance(daeElement * container,daeElement * elt,const string & profile)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'.
findSidBottomUp(daeElement * container,const string & sid,const string & profile)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
findID(daeElement * elt,const string & id,const string & profile)129 daeElement* findID(daeElement* elt, const string& id, const string& profile) {
130 return elt ? elt->getDAE()->getDatabase()->idLookup(id, elt->getDocument()) : NULL;
131 }
132
buildString(const list<string>::iterator & begin,const list<string>::iterator & end,string & result)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.
findWithDots(daeElement * container,const string & s,const string & profile,daeElement * (* finder)(daeElement *,const string &,const string &),list<string> & remainingPart)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
resolveImpl(const daeSidRef & sidRef)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
resolveData()364 daeSidRef::resolveData::resolveData() : elt(NULL), array(NULL), scalar(NULL) { }
365
resolveData(daeElement * elt,daeDoubleArray * array,daeDouble * scalar)366 daeSidRef::resolveData::resolveData(daeElement* elt, daeDoubleArray* array, daeDouble* scalar)
367 : elt(elt),
368 array(array),
369 scalar(scalar) { }
370
371
daeSidRef()372 daeSidRef::daeSidRef() : refElt(NULL) { }
373
daeSidRef(const string & sidRef,daeElement * referenceElt,const string & profile)374 daeSidRef::daeSidRef(const string& sidRef, daeElement* referenceElt, const string& profile)
375 : sidRef(sidRef),
376 refElt(referenceElt),
377 profile(profile) { }
378
operator <(const daeSidRef & other) const379 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
resolve()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
daeSIDResolver(daeElement * container,daeString target,daeString profile)409 daeSIDResolver::daeSIDResolver( daeElement *container, daeString target, daeString profile )
410 : container(NULL)
411 {
412 setContainer(container);
413 setTarget(target);
414 setProfile(profile);
415 }
416
getTarget() const417 daeString daeSIDResolver::getTarget() const {
418 return target.empty() ? NULL : target.c_str();
419 }
420
setTarget(daeString t)421 void daeSIDResolver::setTarget( daeString t )
422 {
423 target = t ? t : "";
424 }
425
getProfile() const426 daeString daeSIDResolver::getProfile() const {
427 return profile.empty() ? NULL : profile.c_str();
428 }
429
setProfile(daeString p)430 void daeSIDResolver::setProfile( daeString p )
431 {
432 profile = p ? p : "";
433 }
434
getContainer() const435 daeElement* daeSIDResolver::getContainer() const {
436 return container;
437 }
438
setContainer(daeElement * element)439 void daeSIDResolver::setContainer(daeElement* element)
440 {
441 container = element;
442 }
443
getState() const444 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
getElement()459 daeElement* daeSIDResolver::getElement()
460 {
461 return daeSidRef(target, container, profile).resolve().elt;
462 }
463
getDoubleArray()464 daeDoubleArray *daeSIDResolver::getDoubleArray()
465 {
466 return daeSidRef(target, container, profile).resolve().array;
467 }
468
getDouble()469 daeDouble *daeSIDResolver::getDouble()
470 {
471 return daeSidRef(target, container, profile).resolve().scalar;
472 }
473
474
daeSidRefCache()475 daeSidRefCache::daeSidRefCache() : hitCount(0), missCount(0) { }
476
lookup(const daeSidRef & sidRef)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
add(const daeSidRef & sidRef,const daeSidRef::resolveData & result)487 void daeSidRefCache::add(const daeSidRef& sidRef, const daeSidRef::resolveData& result) {
488 lookupTable[sidRef] = result;
489 }
490
clear()491 void daeSidRefCache::clear() {
492 lookupTable.clear();
493 hitCount = missCount = 0;
494 }
495
empty()496 bool daeSidRefCache::empty() {
497 return lookupTable.empty();
498 }
499
misses()500 int daeSidRefCache::misses() {
501 return missCount;
502 }
503
hits()504 int daeSidRefCache::hits() {
505 return hitCount;
506 }
507