1/* libs/graphics/xml/SkDOM.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include "SkDOM.h"
19
20/////////////////////////////////////////////////////////////////////////
21
22#include "SkXMLParser.h"
23
24bool SkXMLParser::parse(const SkDOM& dom, const SkDOMNode* node)
25{
26    const char* elemName = dom.getName(node);
27
28    if (this->startElement(elemName))
29        return false;
30
31    SkDOM::AttrIter iter(dom, node);
32    const char*     name, *value;
33
34    while ((name = iter.next(&value)) != NULL)
35        if (this->addAttribute(name, value))
36            return false;
37
38    if ((node = dom.getFirstChild(node)) != NULL)
39        do {
40            if (!this->parse(dom, node))
41                return false;
42        } while ((node = dom.getNextSibling(node)) != NULL);
43
44    return !this->endElement(elemName);
45}
46
47/////////////////////////////////////////////////////////////////////////
48
49struct SkDOMAttr {
50    const char* fName;
51    const char* fValue;
52};
53
54struct SkDOMNode {
55    const char* fName;
56    SkDOMNode*  fFirstChild;
57    SkDOMNode*  fNextSibling;
58    uint16_t    fAttrCount;
59    uint8_t     fType;
60    uint8_t     fPad;
61
62    const SkDOMAttr* attrs() const
63    {
64        return (const SkDOMAttr*)(this + 1);
65    }
66    SkDOMAttr* attrs()
67    {
68        return (SkDOMAttr*)(this + 1);
69    }
70};
71
72/////////////////////////////////////////////////////////////////////////
73
74#define kMinChunkSize   512
75
76SkDOM::SkDOM() : fAlloc(kMinChunkSize), fRoot(NULL)
77{
78}
79
80SkDOM::~SkDOM()
81{
82}
83
84const SkDOM::Node* SkDOM::getRootNode() const
85{
86    return fRoot;
87}
88
89const SkDOM::Node* SkDOM::getFirstChild(const Node* node, const char name[]) const
90{
91    SkASSERT(node);
92    const Node* child = node->fFirstChild;
93
94    if (name)
95    {
96        for (; child != NULL; child = child->fNextSibling)
97            if (!strcmp(name, child->fName))
98                break;
99    }
100    return child;
101}
102
103const SkDOM::Node* SkDOM::getNextSibling(const Node* node, const char name[]) const
104{
105    SkASSERT(node);
106    const Node* sibling = node->fNextSibling;
107    if (name)
108    {
109        for (; sibling != NULL; sibling = sibling->fNextSibling)
110            if (!strcmp(name, sibling->fName))
111                break;
112    }
113    return sibling;
114}
115
116SkDOM::Type SkDOM::getType(const Node* node) const
117{
118    SkASSERT(node);
119    return (Type)node->fType;
120}
121
122const char* SkDOM::getName(const Node* node) const
123{
124    SkASSERT(node);
125    return node->fName;
126}
127
128const char* SkDOM::findAttr(const Node* node, const char name[]) const
129{
130    SkASSERT(node);
131    const Attr* attr = node->attrs();
132    const Attr* stop = attr + node->fAttrCount;
133
134    while (attr < stop)
135    {
136        if (!strcmp(attr->fName, name))
137            return attr->fValue;
138        attr += 1;
139    }
140    return NULL;
141}
142
143/////////////////////////////////////////////////////////////////////////////////////
144
145const SkDOM::Attr* SkDOM::getFirstAttr(const Node* node) const
146{
147    return node->fAttrCount ? node->attrs() : NULL;
148}
149
150const SkDOM::Attr* SkDOM::getNextAttr(const Node* node, const Attr* attr) const
151{
152    SkASSERT(node);
153    if (attr == NULL)
154        return NULL;
155    return (attr - node->attrs() + 1) < node->fAttrCount ? attr + 1 : NULL;
156}
157
158const char* SkDOM::getAttrName(const Node* node, const Attr* attr) const
159{
160    SkASSERT(node);
161    SkASSERT(attr);
162    return attr->fName;
163}
164
165const char* SkDOM::getAttrValue(const Node* node, const Attr* attr) const
166{
167    SkASSERT(node);
168    SkASSERT(attr);
169    return attr->fValue;
170}
171
172/////////////////////////////////////////////////////////////////////////////////////
173
174SkDOM::AttrIter::AttrIter(const SkDOM&, const SkDOM::Node* node)
175{
176    SkASSERT(node);
177    fAttr = node->attrs();
178    fStop = fAttr + node->fAttrCount;
179}
180
181const char* SkDOM::AttrIter::next(const char** value)
182{
183    const char* name = NULL;
184
185    if (fAttr < fStop)
186    {
187        name = fAttr->fName;
188        if (value)
189            *value = fAttr->fValue;
190        fAttr += 1;
191    }
192    return name;
193}
194
195//////////////////////////////////////////////////////////////////////////////
196
197#include "SkXMLParser.h"
198#include "SkTDArray.h"
199
200static char* dupstr(SkChunkAlloc* chunk, const char src[])
201{
202    SkASSERT(chunk && src);
203    size_t  len = strlen(src);
204    char*   dst = (char*)chunk->alloc(len + 1, SkChunkAlloc::kThrow_AllocFailType);
205    memcpy(dst, src, len + 1);
206    return dst;
207}
208
209class SkDOMParser : public SkXMLParser {
210    bool fNeedToFlush;
211public:
212    SkDOMParser(SkChunkAlloc* chunk) : SkXMLParser(&fParserError), fAlloc(chunk)
213    {
214        fRoot = NULL;
215        fLevel = 0;
216        fNeedToFlush = true;
217    }
218    SkDOM::Node* getRoot() const { return fRoot; }
219    SkXMLParserError fParserError;
220protected:
221    void flushAttributes()
222    {
223        int attrCount = fAttrs.count();
224
225        SkDOM::Node* node = (SkDOM::Node*)fAlloc->alloc(sizeof(SkDOM::Node) + attrCount * sizeof(SkDOM::Attr),
226                                                        SkChunkAlloc::kThrow_AllocFailType);
227
228        node->fName = fElemName;
229        node->fFirstChild = NULL;
230        node->fAttrCount = SkToU16(attrCount);
231        node->fType = SkDOM::kElement_Type;
232
233        if (fRoot == NULL)
234        {
235            node->fNextSibling = NULL;
236            fRoot = node;
237        }
238        else    // this adds siblings in reverse order. gets corrected in onEndElement()
239        {
240            SkDOM::Node* parent = fParentStack.top();
241            SkASSERT(fRoot && parent);
242            node->fNextSibling = parent->fFirstChild;
243            parent->fFirstChild = node;
244        }
245        *fParentStack.push() = node;
246
247        memcpy(node->attrs(), fAttrs.begin(), attrCount * sizeof(SkDOM::Attr));
248        fAttrs.reset();
249
250    }
251    virtual bool onStartElement(const char elem[])
252    {
253        if (fLevel > 0 && fNeedToFlush)
254            this->flushAttributes();
255        fNeedToFlush = true;
256        fElemName = dupstr(fAlloc, elem);
257        ++fLevel;
258        return false;
259    }
260    virtual bool onAddAttribute(const char name[], const char value[])
261    {
262        SkDOM::Attr* attr = fAttrs.append();
263        attr->fName = dupstr(fAlloc, name);
264        attr->fValue = dupstr(fAlloc, value);
265        return false;
266    }
267    virtual bool onEndElement(const char elem[])
268    {
269        --fLevel;
270        if (fNeedToFlush)
271            this->flushAttributes();
272        fNeedToFlush = false;
273
274        SkDOM::Node* parent;
275
276        fParentStack.pop(&parent);
277
278        SkDOM::Node* child = parent->fFirstChild;
279        SkDOM::Node* prev = NULL;
280        while (child)
281        {
282            SkDOM::Node* next = child->fNextSibling;
283            child->fNextSibling = prev;
284            prev = child;
285            child = next;
286        }
287        parent->fFirstChild = prev;
288        return false;
289    }
290private:
291    SkTDArray<SkDOM::Node*> fParentStack;
292    SkChunkAlloc*   fAlloc;
293    SkDOM::Node*    fRoot;
294
295    // state needed for flushAttributes()
296    SkTDArray<SkDOM::Attr>  fAttrs;
297    char*                   fElemName;
298    int                     fLevel;
299};
300
301const SkDOM::Node* SkDOM::build(const char doc[], size_t len)
302{
303    fAlloc.reset();
304    SkDOMParser parser(&fAlloc);
305    if (!parser.parse(doc, len))
306    {
307        SkDEBUGCODE(SkDebugf("xml parse error, line %d\n", parser.fParserError.getLineNumber());)
308        fRoot = NULL;
309        fAlloc.reset();
310        return NULL;
311    }
312    fRoot = parser.getRoot();
313    return fRoot;
314}
315
316///////////////////////////////////////////////////////////////////////////
317
318static void walk_dom(const SkDOM& dom, const SkDOM::Node* node, SkXMLParser* parser)
319{
320    const char* elem = dom.getName(node);
321
322    parser->startElement(elem);
323
324    SkDOM::AttrIter iter(dom, node);
325    const char*     name;
326    const char*     value;
327    while ((name = iter.next(&value)) != NULL)
328        parser->addAttribute(name, value);
329
330    node = dom.getFirstChild(node, NULL);
331    while (node)
332    {
333        walk_dom(dom, node, parser);
334        node = dom.getNextSibling(node, NULL);
335    }
336
337    parser->endElement(elem);
338}
339
340const SkDOM::Node* SkDOM::copy(const SkDOM& dom, const SkDOM::Node* node)
341{
342    fAlloc.reset();
343    SkDOMParser parser(&fAlloc);
344
345    walk_dom(dom, node, &parser);
346
347    fRoot = parser.getRoot();
348    return fRoot;
349}
350
351//////////////////////////////////////////////////////////////////////////
352
353int SkDOM::countChildren(const Node* node, const char elem[]) const
354{
355    int count = 0;
356
357    node = this->getFirstChild(node, elem);
358    while (node)
359    {
360        count += 1;
361        node = this->getNextSibling(node, elem);
362    }
363    return count;
364}
365
366//////////////////////////////////////////////////////////////////////////
367
368#include "SkParse.h"
369
370bool SkDOM::findS32(const Node* node, const char name[], int32_t* value) const
371{
372    const char* vstr = this->findAttr(node, name);
373    return vstr && SkParse::FindS32(vstr, value);
374}
375
376bool SkDOM::findScalars(const Node* node, const char name[], SkScalar value[], int count) const
377{
378    const char* vstr = this->findAttr(node, name);
379    return vstr && SkParse::FindScalars(vstr, value, count);
380}
381
382bool SkDOM::findHex(const Node* node, const char name[], uint32_t* value) const
383{
384    const char* vstr = this->findAttr(node, name);
385    return vstr && SkParse::FindHex(vstr, value);
386}
387
388bool SkDOM::findBool(const Node* node, const char name[], bool* value) const
389{
390    const char* vstr = this->findAttr(node, name);
391    return vstr && SkParse::FindBool(vstr, value);
392}
393
394int SkDOM::findList(const Node* node, const char name[], const char list[]) const
395{
396    const char* vstr = this->findAttr(node, name);
397    return vstr ? SkParse::FindList(vstr, list) : -1;
398}
399
400bool SkDOM::hasAttr(const Node* node, const char name[], const char value[]) const
401{
402    const char* vstr = this->findAttr(node, name);
403    return vstr && !strcmp(vstr, value);
404}
405
406bool SkDOM::hasS32(const Node* node, const char name[], int32_t target) const
407{
408    const char* vstr = this->findAttr(node, name);
409    int32_t     value;
410    return vstr && SkParse::FindS32(vstr, &value) && value == target;
411}
412
413bool SkDOM::hasScalar(const Node* node, const char name[], SkScalar target) const
414{
415    const char* vstr = this->findAttr(node, name);
416    SkScalar    value;
417    return vstr && SkParse::FindScalar(vstr, &value) && value == target;
418}
419
420bool SkDOM::hasHex(const Node* node, const char name[], uint32_t target) const
421{
422    const char* vstr = this->findAttr(node, name);
423    uint32_t    value;
424    return vstr && SkParse::FindHex(vstr, &value) && value == target;
425}
426
427bool SkDOM::hasBool(const Node* node, const char name[], bool target) const
428{
429    const char* vstr = this->findAttr(node, name);
430    bool        value;
431    return vstr && SkParse::FindBool(vstr, &value) && value == target;
432}
433
434//////////////////////////////////////////////////////////////////////////
435
436#ifdef SK_DEBUG
437
438static void tab(int level)
439{
440    while (--level >= 0)
441        SkDebugf("\t");
442}
443
444void SkDOM::dump(const Node* node, int level) const
445{
446    if (node == NULL)
447        node = this->getRootNode();
448    if (node)
449    {
450        tab(level);
451        SkDebugf("<%s", this->getName(node));
452
453        const Attr* attr = node->attrs();
454        const Attr* stop = attr + node->fAttrCount;
455        for (; attr < stop; attr++)
456            SkDebugf(" %s=\"%s\"", attr->fName, attr->fValue);
457
458        const Node* child = this->getFirstChild(node);
459        if (child)
460        {
461            SkDebugf(">\n");
462            while (child)
463            {
464                this->dump(child, level+1);
465                child = this->getNextSibling(child);
466            }
467            tab(level);
468            SkDebugf("</%s>\n", node->fName);
469        }
470        else
471            SkDebugf("/>\n");
472    }
473}
474
475void SkDOM::UnitTest()
476{
477#ifdef SK_SUPPORT_UNITTEST
478    static const char gDoc[] =
479        "<root a='1' b='2'>"
480            "<elem1 c='3' />"
481            "<elem2 d='4' />"
482            "<elem3 e='5'>"
483                "<subelem1/>"
484                "<subelem2 f='6' g='7'/>"
485            "</elem3>"
486            "<elem4 h='8'/>"
487        "</root>"
488        ;
489
490    SkDOM   dom;
491
492    SkASSERT(dom.getRootNode() == NULL);
493
494    const Node* root = dom.build(gDoc, sizeof(gDoc) - 1);
495    SkASSERT(root && dom.getRootNode() == root);
496
497    const char* v = dom.findAttr(root, "a");
498    SkASSERT(v && !strcmp(v, "1"));
499    v = dom.findAttr(root, "b");
500    SkASSERT(v && !strcmp(v, "2"));
501    v = dom.findAttr(root, "c");
502    SkASSERT(v == NULL);
503
504    SkASSERT(dom.getFirstChild(root, "elem1"));
505    SkASSERT(!dom.getFirstChild(root, "subelem1"));
506
507    dom.dump();
508#endif
509}
510
511#endif
512
513