LCOV - code coverage report
Current view: top level - lib - optimizer_matches.cpp (source / functions) Hit Total Coverage
Test: coverage.info Lines: 73 106 68.9 %
Date: 2014-11-22 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* optimizer_compare.cpp -- written by Alexis WILKE for Made to Order Software Corp. (c) 2005-2014 */
       2             : 
       3             : /*
       4             : 
       5             : Copyright (c) 2005-2014 Made to Order Software Corp.
       6             : 
       7             : http://snapwebsites.org/project/as2js
       8             : 
       9             : Permission is hereby granted, free of charge, to any
      10             : person obtaining a copy of this software and
      11             : associated documentation files (the "Software"), to
      12             : deal in the Software without restriction, including
      13             : without limitation the rights to use, copy, modify,
      14             : merge, publish, distribute, sublicense, and/or sell
      15             : copies of the Software, and to permit persons to whom
      16             : the Software is furnished to do so, subject to the
      17             : following conditions:
      18             : 
      19             : The above copyright notice and this permission notice
      20             : shall be included in all copies or substantial
      21             : portions of the Software.
      22             : 
      23             : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
      24             : ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
      25             : LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
      26             : FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO
      27             : EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
      28             : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
      29             : WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
      30             : ARISING FROM, OUT OF OR IN CONNECTION WITH THE
      31             : SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
      32             : SOFTWARE.
      33             : 
      34             : */
      35             : 
      36             : #include    "optimizer_tables.h"
      37             : 
      38             : #include    "as2js/exceptions.h"
      39             : 
      40             : 
      41             : namespace as2js
      42             : {
      43             : namespace optimizer_details
      44             : {
      45             : 
      46             : 
      47             : /** \brief Hide all optimizer compare implementation details.
      48             :  *
      49             :  * This unnamed namespace is used to further hide all the optimizer
      50             :  * details.
      51             :  */
      52             : namespace
      53             : {
      54             : 
      55             : 
      56             : /** \brief Compare a node against a specific match.
      57             :  *
      58             :  * This function checks the data of one node against the data defined
      59             :  * by the match parameter.
      60             :  *
      61             :  * The matching processes uses the parameters defined in the optimization
      62             :  * match structure. This includes:
      63             :  *
      64             :  * \li Node Type -- whether one of the node types defined in the match
      65             :  *                  structure is equal to the type of \p node.
      66             :  * \li Attributes -- whether one set of the attributes defined in the
      67             :  *                   match structure is equal to the attributes defined
      68             :  *                   in \p node
      69             :  * \li Flags -- whether one set of the flags defined in the match structure
      70             :  *              is equal to the attributes defined in \p node
      71             :  * \li Links -- whether each set of links has at least one tree that
      72             :  *              matches the links of \p node
      73             :  *
      74             :  * Any one of those match lists can be empty (its size is zero) in which
      75             :  * case it it ignored and the node can as well have any value there. It
      76             :  * is very likely that testing attributes, flags, or links on a node of
      77             :  * which the type was not tested will not be a good match.
      78             :  *
      79             :  * \internal
      80             :  *
      81             :  * \param[in] node  The node to compare against.
      82             :  * \param[in] match  The optimization match to use against this node.
      83             :  *
      84             :  * \return true if the node is a perfect match.
      85             :  */
      86      206540 : bool match_node(node_pointer_vector_t& node_array, Node::pointer_t node, optimization_match_t const *match)
      87             : {
      88             :     // match node types
      89      206540 :     if(match->f_node_types_count > 0)
      90             :     {
      91      206416 :         Node::node_t const node_type(node->get_type());
      92      448988 :         for(size_t idx(0);; ++idx)
      93             :         {
      94      448988 :             if(idx >= match->f_node_types_count)
      95             :             {
      96      204166 :                 return false;
      97             :             }
      98      244822 :             if(match->f_node_types[idx] == node_type)
      99             :             {
     100        2250 :                 break;
     101             :             }
     102      242572 :         }
     103             :     }
     104             : 
     105        2374 :     if(match->f_with_value != nullptr)
     106             :     {
     107          97 :         optimization_match_t::optimization_literal_t const *value(match->f_with_value);
     108             : 
     109             :         // note: we only need to check STRING, INT64, and FLOAT64 literals
     110          97 :         switch(value->f_operator)
     111             :         {
     112             :         case Node::node_t::NODE_ASSIGNMENT:
     113          17 :             if(node->has_side_effects())
     114             :             {
     115           3 :                 return false;
     116             :             }
     117          14 :             break;
     118             : 
     119             :         case Node::node_t::NODE_IDENTIFIER:
     120           2 :             if(value->f_int64 != 0)
     121             :             {
     122           2 :                 if(static_cast<size_t>(value->f_int64) >= node_array.size())
     123             :                 {
     124             :                     throw exception_internal_error("INTERNAL ERROR: identifier check using an index larger than the existing nodes"); // LCOV_EXCL_LINE
     125             :                 }
     126           2 :                 if(node_array[value->f_int64]->get_string() != node->get_string())
     127             :                 {
     128           1 :                     return false;
     129             :                 }
     130             :             }
     131             :             else
     132             :             {
     133           0 :                 if(node->get_string() != value->f_string)
     134             :                 {
     135           0 :                     return false;
     136             :                 }
     137             :             }
     138           1 :             break;
     139             : 
     140             :         case Node::node_t::NODE_BITWISE_AND:
     141          10 :             switch(node->get_type())
     142             :             {
     143             :             case Node::node_t::NODE_INT64:
     144             :                 {
     145           7 :                     uint32_t mask(static_cast<uint32_t>(value->f_float64));
     146           7 :                     if((node->get_int64().get() & mask) != value->f_int64)
     147             :                     {
     148           1 :                         return false;
     149             :                     }
     150             :                 }
     151           6 :                 break;
     152             : 
     153             :             case Node::node_t::NODE_FLOAT64:
     154             :                 {
     155           3 :                     uint32_t mask(static_cast<uint32_t>(value->f_float64));
     156           3 :                     if((static_cast<uint32_t>(node->get_float64().get()) & mask) != value->f_int64)
     157             :                     {
     158           1 :                         return false;
     159             :                     }
     160             :                 }
     161           2 :                 break;
     162             : 
     163             :             default:
     164             :                 throw exception_internal_error("INTERNAL ERROR: optimizer optimization_literal_t table used against an unsupported node type."); // LCOV_EXCL_LINE
     165             : 
     166             :             }
     167           8 :             break;
     168             : 
     169             :         case Node::node_t::NODE_EQUAL:
     170             :         case Node::node_t::NODE_STRICTLY_EQUAL:
     171          29 :             switch(node->get_type())
     172             :             {
     173             :             // This is not yet accessible (as in, nothing makes use of it
     174             :             // and I'm not totally sure it will come up, re-add later if
     175             :             // useful.)
     176             :             //case Node::node_t::NODE_STRING:
     177             :             //    if(node->get_string() != value->f_string)
     178             :             //    {
     179             :             //        return false;
     180             :             //    }
     181             :             //    break;
     182             : 
     183             :             case Node::node_t::NODE_INT64:
     184           2 :                 if(node->get_int64().get() != value->f_int64)
     185             :                 {
     186           1 :                     return false;
     187             :                 }
     188           1 :                 break;
     189             : 
     190             :             case Node::node_t::NODE_FLOAT64:
     191             : #pragma GCC diagnostic push
     192             : #pragma GCC diagnostic ignored "-Wfloat-equal"
     193             :                 // if we expect a NaN make sure both are NaN
     194             :                 // remember that == and != always return false
     195             :                 // when checked with one or two NaN
     196          27 :                 if(std::isnan(value->f_float64))
     197             :                 {
     198          25 :                     if(!node->get_float64().is_NaN())
     199             :                     {
     200           1 :                         return false;
     201             :                     }
     202             :                 }
     203           2 :                 else if(node->get_float64().get() != value->f_float64)
     204             :                 {
     205           1 :                     return false;
     206             :                 }
     207             : #pragma GCC diagnostic pop
     208          25 :                 break;
     209             : 
     210             :             default:
     211             :                 throw exception_internal_error("INTERNAL ERROR: optimizer optimization_literal_t table used against an unsupported node type."); // LCOV_EXCL_LINE
     212             : 
     213             :             }
     214          26 :             break;
     215             : 
     216             :         case Node::node_t::NODE_TRUE:
     217          20 :             if(node->to_boolean_type_only() != Node::node_t::NODE_TRUE)
     218             :             {
     219           6 :                 return false;
     220             :             }
     221          14 :             break;
     222             : 
     223             :         case Node::node_t::NODE_FALSE:
     224          19 :             if(node->to_boolean_type_only() != Node::node_t::NODE_FALSE)
     225             :             {
     226           0 :                 return false;
     227             :             }
     228          19 :             break;
     229             : 
     230             :         default:
     231             :             throw exception_internal_error("INTERNAL ERROR: optimizer optimization_literal_t table using an unsupported comparison operator."); // LCOV_EXCL_LINE
     232             : 
     233             :         }
     234             :     }
     235             : 
     236             :     // match node attributes
     237        2359 :     if(match->f_attributes_count > 0)
     238             :     {
     239           0 :         Node::attribute_set_t attrs;
     240             :         // note: if the list of attributes is just one entry and that
     241             :         //       one entry is NODE_ATTR_max, we compare the same thing
     242             :         //       twice (i.e. that all attributes are false)
     243           0 :         for(size_t idx(0); idx < match->f_attributes_count; ++idx)
     244             :         {
     245           0 :             if(match->f_attributes[idx] == Node::attribute_t::NODE_ATTR_max)
     246             :             {
     247           0 :                 if(!node->compare_all_attributes(attrs))
     248             :                 {
     249           0 :                     return false;
     250             :                 }
     251           0 :                 attrs.reset();
     252             :             }
     253             :             else
     254             :             {
     255           0 :                 attrs[static_cast<size_t>(match->f_attributes[idx])] = true;
     256             :             }
     257             :         }
     258           0 :         if(!node->compare_all_attributes(attrs))
     259             :         {
     260           0 :             return false;
     261             :         }
     262             :     }
     263             : 
     264             :     // match node flags
     265        2359 :     if(match->f_flags_count > 0)
     266             :     {
     267           0 :         Node::flag_set_t flags;
     268             :         // note: if the list of flags is just one entry and that
     269             :         //       one entry is NODE_FALG_max, we compare the same thing
     270             :         //       twice (i.e. that all flags are false)
     271           0 :         for(size_t idx(0); idx < match->f_flags_count; ++idx)
     272             :         {
     273           0 :             if(match->f_flags[idx] == Node::flag_t::NODE_FLAG_max)
     274             :             {
     275           0 :                 if(!node->compare_all_flags(flags))
     276             :                 {
     277           0 :                     return false;
     278             :                 }
     279           0 :                 flags.reset();
     280             :             }
     281             :             else
     282             :             {
     283           0 :                 flags[static_cast<size_t>(match->f_flags[idx])] = true;
     284             :             }
     285             :         }
     286           0 :         if(!node->compare_all_flags(flags))
     287             :         {
     288           0 :             return false;
     289             :         }
     290             :     }
     291             : 
     292             :     // match node links
     293        2359 :     if(match->f_links_count > 0)
     294             :     {
     295           0 :         for(size_t idx(0); idx < match->f_links_count; ++idx)
     296             :         {
     297           0 :             optimization_match_t::optimization_link_t const *lk(match->f_links + idx);
     298           0 :             Node::pointer_t link(node->get_link(lk->f_link));
     299           0 :             for(size_t j(0);; ++j)
     300             :             {
     301           0 :                 if(j >= lk->f_links_count)
     302             :                 {
     303           0 :                     return false;
     304             :                 }
     305             :                 // when matching links, we do not optimize those thus
     306             :                 // we put their nodes in a temporary array
     307           0 :                 node_pointer_vector_t temp_node_array;
     308           0 :                 if(match_tree(temp_node_array, link, lk->f_links[j].f_match, lk->f_links[j].f_match_count, 0))
     309             :                 {
     310           0 :                     break;
     311             :                 }
     312           0 :             }
     313           0 :         }
     314             :     }
     315             : 
     316             :     // everything matched
     317        2359 :     return true;
     318             : }
     319             : 
     320             : 
     321             : }
     322             : // noname namespace
     323             : 
     324             : 
     325             : /** \brief Compare a node against an optimization tree.
     326             :  *
     327             :  * This function goes through a node tree and and optimization tree.
     328             :  * If they both match, then the function returns true.
     329             :  *
     330             :  * The function is generally called using the node to be checked and
     331             :  * the match / match_count parameters as found in an optimization
     332             :  * structure.
     333             :  *
     334             :  * The depth is expected to start at zero.
     335             :  *
     336             :  * The function is recursive in order to handle the whole tree (i.e.
     337             :  * when the function determines that the node is a match with the
     338             :  * current match level, it then checks all the children of the current
     339             :  * node if required.)
     340             :  *
     341             :  * \internal
     342             :  *
     343             :  * \param[in] node_array  The final array of nodes matched
     344             :  * \param[in] node  The node to be checked against this match.
     345             :  * \param[in] match  An array of match definitions.
     346             :  * \param[in] match_count  The size of the match array.
     347             :  * \param[in] depth  The current depth (match->f_depth == depth).
     348             :  *
     349             :  * \return true if the node matches that optimization match tree.
     350             :  */
     351      206540 : bool match_tree(node_pointer_vector_t& node_array, Node::pointer_t node, optimization_match_t const *match, size_t match_count, uint8_t depth)
     352             : {
     353             :     // attempt a match only if proper depth
     354      619620 :     if(match->f_depth == depth
     355      826160 :     && match_node(node_array, node, match))
     356             :     {
     357        2359 :         node_array.push_back(node);
     358             : //std::cerr << "Matched " << node->get_type_name()
     359             : //                        << ", depth=" << static_cast<int>(depth)
     360             : //                        << ", count=" << match_count
     361             : //                        << ", children? " << ((match->f_match_flags & OPTIMIZATION_MATCH_FLAG_CHILDREN) != 0 ? "YES" : "no")
     362             : //                        << ", size=" << node_array.size()
     363             : //                        << "\n";
     364             : 
     365        2359 :         size_t const max_child(node->get_children_size());
     366        2359 :         size_t c(max_child);
     367             : 
     368             :         // it matched, do we have more to check in the tree?
     369        2359 :         --match_count;
     370        2359 :         if(match_count != 0 && (match->f_match_flags & OPTIMIZATION_MATCH_FLAG_CHILDREN) != 0)
     371             :         {
     372             : 
     373             : #if defined(_DEBUG) || defined(DEBUG)
     374        1730 :             if(depth >= 255)
     375             :             {
     376             :                 throw exception_internal_error("INTERNAL ERROR: optimizer is using a depth of more than 255."); // LCOV_EXCL_LINE
     377             :             }
     378             : #endif
     379             : 
     380             :             // check that the children are a match
     381        1730 :             uint8_t const next_level(depth + 1);
     382             : 
     383        1730 :             c = 0;
     384        2808 :             for(; match_count > 0; --match_count)
     385             :             {
     386        2216 :                 ++match;
     387        2216 :                 if(match->f_depth == next_level)
     388             :                 {
     389        1771 :                     if(c >= max_child)
     390             :                     {
     391             :                         // another match is required, but no more children are
     392             :                         // available in this node...
     393           0 :                         return false;
     394             :                     }
     395        1771 :                     if(!match_tree(node_array, node->get_child(c), match, match_count, next_level))
     396             :                     {
     397             :                         // not a match
     398         714 :                         return false;
     399             :                     }
     400        1057 :                     ++c;
     401             :                 }
     402         445 :                 else if(match->f_depth < next_level)
     403             :                 {
     404             :                     // we arrived at the end of this list of children
     405         424 :                     break;
     406             :                 }
     407             :             }
     408             :         }
     409             : 
     410             :         // return true if all children were taken in account
     411        1645 :         return c >= max_child;
     412             :     }
     413             : 
     414             :     // no matches
     415      204181 :     return false;
     416             : }
     417             : 
     418             : 
     419             : }
     420             : // namespace optimizer_details
     421          63 : }
     422             : // namespace as2js
     423             : 
     424             : // vim: ts=4 sw=4 et

Generated by: LCOV version 1.10