devatlas_priv.h

#ifndef devatlas_priv_h
#define devatlas_priv_h
#include <mtld/devatlas.h>
#include <mtld/common_priv.h>
#include <limits>

namespace Mobi { namespace Mtld { namespace Da {


struct LocalProperty {
    Property property;
    const Value *value;
};

static const size_t LOCAL_PROP_COUNT=16;
class LocalProperties {
    size_t count;
    LocalProperty properties[LOCAL_PROP_COUNT];
    LocalProperties *next;
public:
    LocalProperty *get(size_t);
    LocalProperty *get(const char *);
    LocalProperty *allocNew(DeliveryContext *ctx, const char *, PropertyType);
    LocalProperties()
        : count(0)
        , next(0)
    {
    }
    size_t size() const;
};

class NodeData;

/*
 * a set of properties
 * This is only used if the mask and/or conflicts processing is in use
 */
class propset {
    typedef unsigned int I;
    I *vals;
    static const int mask = sizeof (I) * 8 - 1;

    static unsigned idxOf(unsigned item) {
        return item / sizeof(I);
    }

public:
    propset(size_t maxcount = 200) {
        size_t count = idxOf(maxcount | mask) + 1;
        vals = new I[count];
        memset(vals, 0, sizeof (I) * count);
    }
    ~propset() {
        delete[] vals;
    }

    bool find(size_t v) const {
        return vals[idxOf(v)] & (1 << (v & mask));
    }

    bool end() const {
        return false;
    }

    void insert(unsigned v) {
        vals[idxOf(v)] |= 1 << (v & mask);
    }
};

/*
 * Node:
 * Each character in the tree is represented by a node. 
 *
 * Note that the empty nodes (those with null data fields) are represented in the JSON data by having
 * children with arbitrary length characters, where all but the last 
 * character represents an empty child. We unfold these, so the lookups
 * can be carried out more simply.
 * For Example, the JSON data might have a node at "M" with a child at
 * "ozilla". We represent this as a string of descendents
 * M, o, z, i, l, l, a.
 * The node objects are small enough that this makes the time/space
 * tradeoff well worth it.
 */

class Node {
    // The JSON parsers for this type are allowed at its internals.
    friend class NodeParse;
    friend struct ChildrenParse;

    // Children, indexed by the extra character at the end of their substring
public:
    typedef Util::CharacterIndex<Node *> childmap;
    childmap children;
    Node();
    ~Node();
    NodeData *data;

    /* recursive search operations on the node: see below for details. */
    template <typename T> void visitR(T &t, char key) const;

    // has this node any children?
    bool isLeaf() const { return children.empty(); }
};

class NodeData {
    friend class NodeParse;
    friend class Node;
    attrvec attrs;
    propset conflicts;
    unsigned int nextTree;
    unsigned int matchedDevices;
    int resetWalkId;
public:
    std::vector<size_t> *replacementStrings;
    NodeData() : nextTree(0), matchedDevices(0), replacementStrings(0), resetWalkId(-1) {}
    ~NodeData() { delete replacementStrings; }
    const attrvec &getAttrs() const { return attrs; }
    attrvec &getAttrs() { return attrs; }
    const propset &getConflicts() const { return conflicts; }
    propset &getConflicts() { return conflicts; }
    unsigned getMatchedDeviceCount() const { return matchedDevices; }
    unsigned getNextTreeMatchCount() const { return nextTree; }
    const std::vector<size_t> *getReplacementStrings() const { return replacementStrings; }
    int getResetWalkId() const { return resetWalkId; }
};

/*
 * visit this node, and all its children recursively, calling "pre"
 * and "post" using a false return value to terminate the search.
 * pre and post are passed the current node, and the character which
 * identifies it in its parent.
 */
template <typename T> void
Node::visitR(T &t, char key) const
{
    if (!t.pre(key, this))
        return;
    for (childmap::const_iterator it = children.begin(); it != children.end(); ++it)
        if ((*it).second)
            (*it).second->visitR(t, (*it).first);
    t.post(key, this);
}

/*
 * Searches for the substring of str from offset in the subtree of the
 * current node.
 * The search continues as follows:
 * o call the supplied functor, and terminate the search if it returns false.
 * o if we have reached the end of the string, return false.
 * o find the child at the index specified for the character at str[offset]
 * o if it exists, cal findR on it recursively, advancing offset.
 */



/*
 * Utility to call find and visit on a specific tree in the atlas.
 * Eliminates the "offset" parameter for clarity.
 */
template <typename T, typename Allocator> size_t
dafind(const DeviceAtlas &atlas, T &t, TreeID tree, Allocator &a, const char *rostr, char **matched, char **unmatched)
{
    const Node *n = atlas.roots[tree];
    size_t len = strlen(rostr);
    char *str;
    a.allocate(str, len + 1);
    strlcpy(str, rostr, len + 1);

    if (matched)
        a.allocate(*matched, atlas.maxDepth + 1);

    Node::childmap::const_iterator it;
    size_t offset;
    size_t dataoff = 0;
    char *pathp = matched ? *matched : 0;

    for (offset = 0;;++offset) {
        NodeData *data = n->data;
        // Don't do any heavy lifting if the node has no associated data.
        if (data) {
            if (data->getResetWalkId() > -1) {
                char *pstr;
                const char *resetWalkString = atlas.getResetWalkString((size_t)data->getResetWalkId()).c_str();
                size_t resetWalkStringLen = strlen(resetWalkString);
                size_t ostrlen = strlen(str + offset);
                size_t pcount = atlas.getPropertyCount();
                a.allocate(pstr, resetWalkStringLen + ostrlen + 1);
                memcpy(pstr, resetWalkString, resetWalkStringLen);
                memcpy(pstr + resetWalkStringLen, str + offset, ostrlen + 1);               
                if (matched)
                    *matched = 0;
                if (unmatched)
                    *unmatched = 0;

                for (size_t i = 0; i < pcount; i ++)
                    t.setProperty(i, 0);

                return dafind(atlas, t, tree, a, pstr, matched, unmatched);
            }
            dataoff = offset;
            if (!t(*n, str, offset) || str[offset] == 0)
                break;
            if ((atlas.flags & DeviceAtlas::NoREFold) == 0) {
                const std::vector<size_t> *repls = data->replacementStrings;
                if (repls)
                    atlas.doReplacements(repls, str, offset);
            }
        }
        if (pathp)
            *pathp++ = str[offset];
        it = n->children.find(str[offset]);
        if (it == n->children.end())
            break;
        n = (*it).second;
        if (n == 0)
            break;
    }
    if (matched)
        (*matched)[dataoff] = 0;
    if (unmatched) 
        *unmatched = str + dataoff;

    return offset;
}

template <typename T> void
visit(const DeviceAtlas &atlas, T &t, TreeID tree)
{
    atlas.roots[tree]->visitR(t, '.');
}

// 3.1 extensions: "UAR"
class Rule {
public:
    int property;
    int regex;
    int matchpos;
    int value;
    Rule()
        : property(-1)
        , regex(-1)
        , matchpos(-1)
        , value(-1)
    {
    }
};

enum REType {
    RE_REFINE = 0,
    RE_SEARCH = 1,
    RE_TYPES = 2
};

class RuleSet {
public:
    int re[RE_TYPES];
    std::vector<Rule *> rules;
    RuleSet();
    ~RuleSet();
};

class RuleGroup {
// all these properties must be true for a UA to consider it for this RG
public:
    std::map<int, int> selectionCriteria; // maps from property to value
    std::vector<RuleSet *> ruleSets;
    RuleGroup();
    ~RuleGroup();
    const RuleSet *findSet(const UAR *, int, const char *text) const;
    bool matchProperties(const DeliveryContext *ctx) const;
};

class UAR {
public:
    TaggedRegexMap allRegexes;
    const std::vector<REInfo *> *langRegexes;
    const std::vector<REInfo *> *defaultRegexes;
    std::vector<int> skipProps; // if these properties are true, then don't apply UAR rules
    std::vector<RuleGroup *> groups;
    const REInfo *getRE(size_t re) const;
    UAR();
    ~UAR();
};

enum Operator {
    Equal,
    NotEqual
};

template <typename T> bool
testop(Operator op, const T &lhs, const T &rhs)
{
    switch (op) {
        case Equal: return lhs == rhs;
        case NotEqual: return lhs != rhs;
        default: { Exception err;  err << "\"unknown\""; throw err; }
    }
}


struct CPRule {
    size_t property;
    Value *value;

    Operator op;
    bool test(const DeviceAtlas &da, const Value *candidate) const {
        const Property &p = da.getPropertyDescr(property);
        switch (p.type) {
            case Bool: return testop<bool>(op, *value, *candidate);
            case Integer: return testop<long>(op, *value, *candidate);
            case String: return testop<std::string>(op, *value, *candidate);
            default: throw Exception("unhandled property type");
        }
    }
};

class CPRuleGroup {
public:
    const char *ua;
    typedef std::vector<CPRule> Rules;
    Rules rules;
    attrvec properties;
    attrvec extraproperties;
    CPRuleGroup() : ua(0) {}
    void setProperty(size_t, const Value *) {}
    bool match(const DeliveryContext &ctx) const;
    bool operator() (const Node &node, const char *, size_t);
};

std::ostream &operator<<(std::ostream &os, const CPRuleGroup &);
std::ostream &operator<<(std::ostream &os, const CPRule &);
std::ostream &operator<<(std::ostream &os, const Operator &);

class CPR;
struct ClientPropertiesReceiver {
    std::vector<const Value *> props;
    DeliveryContext &ctx;
    ClientPropertiesReceiver(DeliveryContext &ctx_) : ctx(ctx_) {}
    void operator () (PropertyType type, const char *, const char *);
};

/*
 * q's Accept Language preference handling
 * The first encountered is taken
 */

struct AcceptLanguagePreference {
    const char *code;
    size_t len;
    size_t minuspos;
    float q;
};

/*
 * language value sanity check
 */

inline size_t 
decodeLanguage(char *language, size_t *minuspos) {
    *minuspos = 0;
    if (*language == '*')
        return 1;
    char *p = language;
    char *m = NULL;
    size_t mlen;
    if ((m = strchr(language, '-')) == NULL)
        m = strchr(language, '_');

    if (m) {
        mlen = strlen(m);
        if (mlen == 1 || mlen > 3)
            return 0;
        *minuspos = m - p;
        char *wp = p;
        wp[*minuspos] = 0;
        if (strlen(wp) > 2)
            return 0;
        p[*minuspos] = '-';
    } else {
        if (strlen(language) > 2)
            return 0;
    }
    size_t mp = 0;
    for(; *p; p++, mp++) {
        if ((*p != '-' && !isalpha(*p) && !isspace(*p)))
            break; 
        if (*minuspos > 0 && mp > *minuspos)
            *p = toupper(*p);
    }

    return mp;
}

/*
 * language preference handling
 * the one chosen is related to q ordering (implicity or explicity)
 */
template <typename Allocator>
inline const char*
stripQlanguage(const char *language, size_t *minuspos, Allocator &a) {
    char *cp;
    size_t plen = strlen(language);
    a.allocate(cp, plen + 1);
    strlcpy(cp, language, plen + 1);

    char *token, *ptr;
    AcceptLanguagePreference apmax;
    apmax.len = 0;
    apmax.code = 0;
    apmax.q = 0.0f;
    apmax.minuspos = 0;

    while((token = strtok_r(cp, ",", &ptr)) != NULL) {
        if (cp)
            cp = 0;

        while (isspace(*token) && token ++);

        float q = 1.0f;
        char *qstr, *code;
        size_t codelen = 0;

        if ((qstr = strstr(token, ";")) != NULL) {
            codelen = (qstr - token);
            token[codelen] = 0;
            if (qstr ++) {
                while (isspace(*qstr) && qstr ++);
                if (strncmp(qstr, "q=", 2) == 0) {
                    qstr += 2;
                    while (isspace(*qstr) && qstr ++);
                    if (*qstr != '*') {
                        float qtmp = strtod(qstr, 0);

                        if (qtmp > 0.0f)
                            q = qtmp;
                    } else {
                        q = 0.0f;
                    }
                }
            }
        }

        size_t tminuspos = 0;

        if ((codelen = decodeLanguage(token, &tminuspos)) > 0) {
            a.allocate(code, codelen + 1);
            strlcpy(code, token, codelen + 1);

            if (q > apmax.q) {
                apmax.q = q;
                apmax.len = codelen;
                apmax.minuspos = tminuspos;
                apmax.code = code;
            } else if (q == apmax.q) {
                if (apmax.code && tminuspos > 0 && 
                        strncmp(apmax.code, code, tminuspos) == 0 &&
                        codelen > apmax.len) {
                    apmax.len = codelen;
                    apmax.minuspos = tminuspos;
                    apmax.code = code;
                }
            }
        }
    }

    const char *finallanguage = (apmax.code ? (*apmax.code == '*' ? 0 : apmax.code) : 0);
    *minuspos = (apmax.code ? apmax.minuspos : 0);

    return finallanguage;
}

template <typename T, typename Allocator>
void decodeHeuristic(const char *p, T &cprec, Allocator &a) // XXX: template on ClientPropertiesReceiver
{
    PropertyType type;
    char c;
    char *cp;
    size_t plen = strlen(p);
    a.allocate(cp, plen + 1);
    strlcpy(cp, p, plen + 1);

    using namespace Mobi::Mtld::Util;

    char *token, *ptr;

    while ((token = strtok_r(cp, "|", &ptr)) != NULL) {
        if (cp)
            cp = 0;
        char key[124], *kp = key;
        char escapedvalue[124], *ep = escapedvalue;
        switch ((c = nextchar((const char *&)token, Util::SKIPQUOTE | Util::NULLOK))) {
            case 'b': type = Bool; break;
            case 'i': type = Integer; break;
            case 's': type = String; break;
            case 0: return; // that's all folks.
            default: cprec.props.clear(); return;
        }

        char *sptr, *tmpkp, *tmpvp;
        tmpkp = strtok_r(token, ":", &sptr);
        tmpvp = strtok_r(NULL, ":", &sptr);
        if (!tmpvp)
            continue;

        size_t m = 0;
        char *k = kp; 
        for (char *p = tmpkp; m++ < (sizeof(key)) - 1 && *p; ++p)
            *k++ = *p;
        *k = 0;

        m = 0;
        for (const char *p = tmpvp; m++ < (sizeof(escapedvalue) - 1) && *p; ++p) {
            switch (*p) {
                case '\"': ep += snprintf(ep, sizeof("&quote;") + 1, "&quote;"); break;
                case '&': ep += snprintf(ep, sizeof("&amp;") + 1, "&amp;"); break;
                case '<': ep += snprintf(ep, sizeof("&lt;") + 1, "&lt;"); break;
                case '>': ep += snprintf(ep, sizeof("&gt;") + 1, "&gt;"); break;
                default: *ep++ = *p; break;
            }
        }
        *ep = 0; 

        const char * i;
        for (i = kp; *i && (isalnum(*i) || *i == '.'); ++i);

        if (*i == 0 && i != kp)
            cprec(type, kp, escapedvalue);
    }
}

class CPR {
public:
    typedef std::vector<CPRuleGroup> RuleGroups;
    RuleGroups ruleGroups;
    const CPRuleGroup *getMatchingCPRules(const DeliveryContext &ctx) const;
};


}}}
#endif // devatlas_priv_h