Edgewall Software

Changes between Version 5 and Version 6 of GSoC2008


Ignore:
Timestamp:
Jun 30, 2008, 3:48:35 AM (16 years ago)
Author:
mkurczych
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GSoC2008

    v5 v6  
    88
    99== What has been done ==
    10 Nothing, but the coding has just started. ;-)
     10=== XPath reimplementation ===
     11Current XPath implementation in Genshi is rather buggy (for example [http://genshi.edgewall.org/ticket/185]). I've rewritten it. Implemented algorithm works in O(qn) time, where q is length of XPath expression, n is number of stream events and O(qh) memory complexity, where h is height of document XML tree. It computes for every node which places of XPath expression does it match. O(qn) is pessimistic complexity, I think algorithm will work like O(n) in most cases (the worst case is when nearly every node matches to nearly every place of expression, which is quite rare).
     12
     13Still need to add some tests covering more situations.
    1114
    1215== Currently working at: ==
    13 === XPath reimplementation ===
    14 XPath implementation in Genshi is rather buggy (for example [http://genshi.edgewall.org/ticket/185]). I want to rewrite it. ~~I'm going to implement ideas from docs from the Internet like [http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Boettcher/Lehre/WS_07_08/dbis1/dbis1k8b-xpath_queries_on_xml_streams.pdf] and [http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Boettcher/Lehre/WS_07_08/dbis1/dbis1k8a-xml-streams.pdf].~~
    15 It appears algorithms described in these docs used buffering, which we don't want. It would allow to support more XPath expressions, but could make matching slow. Maybe later I will write code that chooses XPath algorithm according to expression complexity, but for now I'll focus on non-buffering one.
    16 Implemented algorithm will work in O(qn) time, where q is length of XPath expression, n is number of stream events and O(qh) memory complexity, where h is height of document XML tree. It will compute for every node which places of XPath expression does it match. O(qn) is pessimistic complexity, I think algorithm will work like O(n) in most cases (the worst case is when nearly every node matches to nearly every place of expression, which is quite rare).
     16=== Template pre-processing ===
     17There are many templates where much of code doesn't depend on context. It can be pre-rendered once and then only pasted as result.
     18Also common situation is when there are only few possible variable values - for example only True or False. We can pre-reder parts of code for each of values and use them later. We only have to check for given fragment of template which values does it use and find recurrences of this values.
     19There's also need of making filters compatible with this changes - probably somehow mark fragment of code they change.