from_xmpl.cpp

vxworks的系统故障诊断项目

/***
 *** See the file "mba/disclaimers-and-notices-L2.txt" for
 *** information on usage and redistribution of this file,
 *** and for a DISCLAIMER OF ALL WARRANTIES.
 ***/

/* $Id: from_xmpl.cpp,v 1.1.1.1 2006/10/09 06:58:18 shao Exp $ */

#include <errno.h>
#include <math.h>
#include <stdlib.h>

#include <livingstone/L2_fstream.h>
#include <readers/from_xmpl.h>
#include <readers/transition.h>

#include <sax/HandlerBase.hpp>
#include <sax/AttributeList.hpp>
#include <parsers/SAXParser.hpp>
#include <util/PlatformUtils.hpp>

// The do-while(0) is the only portable way to block.
#ifdef ENABLE_L2_VERBOSE
#define verbose(expr) do { if (isVerbose()) { expr; } } while(0)
#else
#define verbose(expr)
#endif

template <class T>
T *list_to_array(Slist<T>& list) {
    T* ret = L2_alloc_array(T,list.size());
    unsigned i;
    typename Slist<T>::iterator it;
    for(i=0, it=list.begin(); it!=list.end(); ++i, ++it)
        ret[i] = *it;
    return ret;
}



/***************************************************************************
        The class that handles the parsing callbacks.
 ***************************************************************************/
class from_xmpl::HandlerBase_subclass : public HandlerBase {
    private:
        from_xmpl& owner_;
        AttributeList *attr_;

    public:

        MBA_string filename;

        HandlerBase_subclass(from_xmpl& owner)
            : owner_(owner)
        {
        }

        MBA_string xcode(const XMLCh* xmlstr) {
            return XMLString::transcode(xmlstr);
        }
        MBA_string get_attribute(const char *str) {
            const XMLCh* attr = attr_->getValue(str);
            if(attr)
                return xcode(attr);
            else
                return "";
        }

        /// These are callbacks declared in HandlerBase
        virtual void startElement(const XMLCh* const tagname,
                AttributeList& attributes) {
            attr_ = &attributes;
            MBA_string localTag(xcode(tagname));

            if(localTag == "ci:attribute") {
                MBA_string name = get_attribute("name");
                MBA_string type = get_attribute("type");

                owner_.start_attribute(name, type);
            }
            else if(localTag == "cmd") {
                MBA_string varname = get_attribute("name");
                owner_.start_cmd(varname);
            }
            else if(localTag == "obs") {
                MBA_string varname = get_attribute("name");
                owner_.start_obs(varname);
            }
            else if(localTag == "assign") {
                MBA_string prop = get_attribute("eq");
                owner_.start_assign(prop);
            }
            else if(localTag == "ci:attributetype") {
                MBA_string name = get_attribute("name");
                MBA_string values(get_attribute("members"));
                owner_.start_attributetype(name, values);
            }
            else if(localTag == "ci:component") {
                MBA_string name = get_attribute("name");
                owner_.start_component(name);
            }
            else if(localTag == "ci:clause") {
                owner_.start_clause();
            }
            else if(localTag == "ci:term") {
                owner_.start_prop();
            }
            else if(localTag == "ci:statevector") {
                MBA_string name = get_attribute("vars");
                owner_.start_statevector(name);
            }
            else if(localTag == "ci:transition") {
                MBA_string from, to, name, prob;

                from = get_attribute("from");
                to   = get_attribute("to");
                prob = get_attribute("probability");

                const XMLCh *xname = attributes.getValue("name");

                if(xname)
                    name = xcode(xname);
                else
                    name = from + "->" + to;
                owner_.start_transition(from, to, name, prob);
            }
        }

        virtual void characters(const XMLCh* const chars, const unsigned int) {
            owner_.characters(xcode(chars));
        }

        virtual void endElement(const XMLCh* const tagname) {
            MBA_string localTag(xcode(tagname));
            if(localTag == "ci:component")
                owner_.end_component();
            else if(localTag == "ci:clause")
                owner_.end_clause();
            else if(localTag == "ci:term")
                owner_.end_prop();
            else if(localTag == "ci:transition")
                owner_.end_transition();
        }



        virtual void warning(const SAXParseException& e) {
            _STD_ cerr<< filename << ":" << e.getLineNumber()
		     << " : " << xcode(e.getMessage()) << _STD_ endl;
        }

        virtual void error(const SAXParseException& e) {
            L2_throw( L2_reader_error,
                    ("Error at " + filename
                     + " line " + MBA_string(e.getLineNumber())
                     + " position " + MBA_string(e.getColumnNumber())
                     + ": " + xcode(e.getMessage())));
        }

        virtual void fatalError(const SAXParseException& e) {
            L2_throw( L2_reader_error,
                    ("Fatal Error at " + filename
                     + " line " + MBA_string(e.getLineNumber())
                     + " position " + MBA_string(e.getColumnNumber())
                     + ": " + xcode(e.getMessage())));
        }
};


/***************************************************************************
        Parsing probabilities into the ranks that Livingstone uses.
 ***************************************************************************/

// Take the negative log, base 10, of the probability to yield a rank.

static unsigned convert_to_rank(double prob) {
  L2_assert(prob >  0, L2_reader_error, ("probability <= 0"));
  L2_assert(prob <= 1, L2_reader_error, ("probability >  1"));
  int rank = (int)(0.5 - log10(prob));
  return rank;
}


// If the probability is one of { likely, lessLikely, unlikely, rare },
// map to a rank. Otherwise, try to interpret as a probability.

static unsigned convert_to_rank(const MBA_string& prob_string) {
  if      (prob_string == "likely")     { return 1; }
  else if (prob_string == "lessLikely") { return 2; }
  else if (prob_string == "unlikely")   { return 3; }
  else if (prob_string == "rare")       { return 4; }
  // Any Candidate containing an Assignment with this rank will have a rank
  // higher than any double-fault Candidate with only the previous four ranks
  // used. That way, unknown-fault Candidates can be segregated.
  else if (prob_string == "unknownFaultRank") { return 10; }
  else {
    double probability = atof(prob_string.c_str());
    L2_assert(probability != 0 || errno != EINVAL,
	      L2_reader_error,
	      ("probability unparseable"));
    return convert_to_rank(probability);
  }
}


/***************************************************************************
        Dictionary functions
 ***************************************************************************/
dbg_L2rEnumeration *from_xmpl::find_enum(const MBA_string& name) {
    Hash_table<MBA_string, dbg_L2rEnumeration*>::iterator it = enums_.find(name);
    L2_assert(it != enums_.end(), L2_not_found_error,
            ("enumeration `"+name+"' not found"));
    return *it;
}

static const char* noCommand = "noCommand";

dbg_L2rEnumeration *from_xmpl::create_enum(
        const MBA_string& name, Slist<MBA_string>& values) {

    // first, force noCommand to the start of the list
    Slist<MBA_string>::iterator it = values.begin();
    bool hasNoCommand = false;
    while(it != values.end()) {
        if(*it == noCommand) {
            hasNoCommand = true;
            values.erase(it);
        } else
            ++it;
    }
    if(hasNoCommand) values.push_front(noCommand);


    // create the new enumeration, give it its ID, add to the list
    unsigned nvalues = values.size();
    MBA_string *names = list_to_array(values);
    dbg_L2rEnumeration *newenum = new dbg_L2rEnumeration(nenums_++,
            nvalues, name, names);
    L2_free_array(names, nvalues);

#ifdef VXWORKS531
    const bool ok = enums_.insert(name, newenum);        // returns bool
#else
    const bool ok = enums_.insert(name, newenum).second; // returns pair
#endif
    L2_assert(ok, L2_reader_error, ("enumeration `"+name+"' already exists"));
    verbose(newenum->toOStream_long(_STD_ cout));
    return newenum;
}


int from_xmpl::find_enum_member(const L2rEnumeration *t,
				const MBA_string& member) {
    assert(t->hasDebug());
    const dbg_L2rEnumeration *type = (dbg_L2rEnumeration*)t;

    if(member == "*") // required for transitions
        return L2rTransition::ANY_MODE;
    for(unsigned i=0; i<type->nmembers(); i++) {
        if(member==type->name(i))
            return i;
    }
    return NOT_FOUND;
}



L2rVariable *from_xmpl::find_variable(const MBA_string& name, bool fatal) {
    varsIT it = vars_.find(name);
    if(it == vars_.end()) {
        if(fatal) {
            L2_assert(it != vars_.end(), L2_not_found_error,
                    ("variable `"+name+"' not found"));
        } else
            return 0;
    }
    return *it;
}

L2rVariable *from_xmpl::create_variable(
        const dbg_L2rEnumeration *type, const MBA_string& name) {

    dbg_L2rVariable *v = new dbg_L2rVariable(nvars_++, type, name);
#ifdef VXWORKS531
    const bool ok = vars_.insert(name, v);        // returns bool
#else
    const bool ok = vars_.insert(name, v).second; // returns pair
#endif
    L2_assert(ok, L2_reader_error, ("variable `"+name+"' already exists"));
    verbose(v->toOStream_long(_STD_ cout));
    return v;
}



L2rProposition *from_xmpl::find_or_create_prop(
        const L2rVariable *var, bool isPositive, const MBA_string& equalTo) {
    // first, find out what `equalTo' refers to -- a variable or a value
    // Search for a value; if not found, search for a variable.

    // For ease-of-implementation, we create the prop and then use
    // operator == ; this is inefficient but I don't really care since
    // this is only used on the ground.
    int value = find_enum_member(var->type(), equalTo);
    L2rProposition *prop;
    if(value>=0) {
        // found a value of the given name, so use it
        prop = new L2rPropVarValue(nprops_, var, isPositive, value);
    } else {
        // no such value; look for a variable.
        MBA_string varname = component_name + "." + equalTo;
        L2rVariable *var2 = find_variable(varname, false);
        L2_assert(var2, L2_not_found_error,
                ("no value or variable `"+equalTo+"' found"));
        prop = new L2rPropVarVar(nprops_, var, isPositive, var2);
    }

    // linear search; surely I could do better!
    for(propsIT it = props_.begin() ; it != props_.end() ; ++it ) {
        if(*prop == **it) {
            // found a previous identical prop; delete the new one and
            // use the old.
            delete prop;
            return *it;
        }
    }

    // not found; add the new prop we just created to the list.
    props_.push_front(prop);
    nprops_++;
    verbose(prop->toOStream_long(_STD_ cout));
    return prop;
}

/***************************************************************************
  Building up a clause.
  We store the props in sorted order, which takes O(n^2) where n is the
  number of props.
  This allows us to check clause==list in O(n) time.
  We build c lists ; we check each against c clauses.  So we spend
  O(c*n^2) building, and O(c^2*n) searching.

  If we built the list in O(n) time, we'd spend O(n^2) time searching each,
  for a total of O(cn) building and O(c^2*n^2) searching, so it's faster this
  way.

  If we used a hash table, hash function is sum the pointers, then search
  would be O(n+T(eq)) per lookup, c lookups.  So we'd spend

  Note: n << c
                sorted                unsorted
  building      O(c*n^2)              O(cn)

  list          O(c^2*n)              O(c^2*n^2)
  total(list)   O(c^2*n)              O(c^2*n^2)

  hash          O(cn)                 O(cn^2)
  total(hash)   O(cn^2)               O(cn^2)

  In other words, we have a speedup of O(c) possible if we use a hash table.
 ***************************************************************************/

void from_xmpl::add_clause_prop(L2rProposition *prop) {
    // Insert in sorted order.  Insertion-sort is expensive but the
    // clauses are small.
    Slist<L2rProposition*>::iterator it = clause_props.begin();
    Slist<L2rProposition*>::iterator pit= it; // prev iterator
    while(it != clause_props.end()) {
        if(prop == *it) {
            return; // duplicate; skip this one
        }
        if(prop < *it) {