netsurf: branch master updated. release/3.0-782-g5b4a9e9
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/netsurf.git/shortlog/5b4a9e9315d688765115f...
...commit http://git.netsurf-browser.org/netsurf.git/commit/5b4a9e9315d688765115f84...
...tree http://git.netsurf-browser.org/netsurf.git/tree/5b4a9e9315d688765115f846a...
The branch, master has been updated
via 5b4a9e9315d688765115f846a8cd1731dfffb5b3 (commit)
from 71a1a762d1f62399be6db0aaae579cb9bf5cf74e (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/netsurf.git/commit/?id=5b4a9e9315d68876511...
commit 5b4a9e9315d688765115f846a8cd1731dfffb5b3
Author: Ole Loots <ole(a)monochrom.net>
Commit: Ole Loots <ole(a)monochrom.net>
Use correct LD_LIBRARY_PATH for additional libraries
diff --git a/atari/Makefile.target b/atari/Makefile.target
index 4a416ba..789118b 100644
--- a/atari/Makefile.target
+++ b/atari/Makefile.target
@@ -70,7 +70,7 @@ LDFLAGS += -lcflib -lcurl
LDFLAGS += -lcss -lparserutils -ldom -lwapcaplet -lhubbub
LDFLAGS += -lssl -lcrypto
LDFLAGS += -lz -liconv -lcares -lHermes -lgem -lm
-LDFLAGS += -L$(GCCSDK_INSTALL_ENV)/lib
+LDFLAGS += -L$(GCCSDK_INSTALL_ENV)/env/lib
# S_ATARI are sources purely for the Atari FreeMiNT build
-----------------------------------------------------------------------
Summary of changes:
atari/Makefile.target | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/atari/Makefile.target b/atari/Makefile.target
index 4a416ba..789118b 100644
--- a/atari/Makefile.target
+++ b/atari/Makefile.target
@@ -70,7 +70,7 @@ LDFLAGS += -lcflib -lcurl
LDFLAGS += -lcss -lparserutils -ldom -lwapcaplet -lhubbub
LDFLAGS += -lssl -lcrypto
LDFLAGS += -lz -liconv -lcares -lHermes -lgem -lm
-LDFLAGS += -L$(GCCSDK_INSTALL_ENV)/lib
+LDFLAGS += -L$(GCCSDK_INSTALL_ENV)/env/lib
# S_ATARI are sources purely for the Atari FreeMiNT build
--
NetSurf Browser
9 years, 1 month
- 1
- 0
netsurf-website: branch master updated. 1a1c5c9c88acc673eedf5fe87175edbdf7c95843
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/netsurf-website.git/shortlog/1a1c5c9c88acc...
...commit http://git.netsurf-browser.org/netsurf-website.git/commit/1a1c5c9c88acc67...
...tree http://git.netsurf-browser.org/netsurf-website.git/tree/1a1c5c9c88acc673e...
The branch, master has been updated
via 1a1c5c9c88acc673eedf5fe87175edbdf7c95843 (commit)
from addf7d482a97c8264d9997fefc8e805ce7b74d65 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/netsurf-website.git/commit/?id=1a1c5c9c88a...
commit 1a1c5c9c88acc673eedf5fe87175edbdf7c95843
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Tweak some wording.
diff --git a/about/news.en b/about/news.en
index 0381f08..27d971e 100644
--- a/about/news.en
+++ b/about/news.en
@@ -57,8 +57,8 @@
<h1>News</h1>
<dl class="news">
-<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance optimisation</a> <span>02 Dec 2013</span></dt>
-<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance boost</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf include this improvement.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of the NetSurf codebase</a> <span>22 Nov 2013</span></dt>
<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
diff --git a/index.en b/index.en
index 6aac82a..47812da 100644
--- a/index.en
+++ b/index.en
@@ -147,7 +147,7 @@
<dl class="frontnews">
<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS performance boost</a> <span>02 Dec 2013</span></dt>
-<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf include this improvement.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of NetSurf's codebase</a> <span>22 Nov 2013</span></dt>
<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
-----------------------------------------------------------------------
Summary of changes:
about/news.en | 4 ++--
index.en | 2 +-
2 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/about/news.en b/about/news.en
index 0381f08..27d971e 100644
--- a/about/news.en
+++ b/about/news.en
@@ -57,8 +57,8 @@
<h1>News</h1>
<dl class="news">
-<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance optimisation</a> <span>02 Dec 2013</span></dt>
-<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance boost</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf include this improvement.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of the NetSurf codebase</a> <span>22 Nov 2013</span></dt>
<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
diff --git a/index.en b/index.en
index 6aac82a..47812da 100644
--- a/index.en
+++ b/index.en
@@ -147,7 +147,7 @@
<dl class="frontnews">
<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS performance boost</a> <span>02 Dec 2013</span></dt>
-<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf include this improvement.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of NetSurf's codebase</a> <span>22 Nov 2013</span></dt>
<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
--
NetSurf website source for *.netsurf-browser.org
9 years, 1 month
- 1
- 0
netsurf-website: branch master updated. addf7d482a97c8264d9997fefc8e805ce7b74d65
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/netsurf-website.git/shortlog/addf7d482a97c...
...commit http://git.netsurf-browser.org/netsurf-website.git/commit/addf7d482a97c82...
...tree http://git.netsurf-browser.org/netsurf-website.git/tree/addf7d482a97c8264...
The branch, master has been updated
via addf7d482a97c8264d9997fefc8e805ce7b74d65 (commit)
from 5e452bf7a5781fe87304d454fb636919ad88301c (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/netsurf-website.git/commit/?id=addf7d482a9...
commit addf7d482a97c8264d9997fefc8e805ce7b74d65
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Update news.
diff --git a/about/news.en b/about/news.en
index 6c73433..0381f08 100644
--- a/about/news.en
+++ b/about/news.en
@@ -57,12 +57,26 @@
<h1>News</h1>
<dl class="news">
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance optimisation</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of the NetSurf codebase</a> <span>22 Nov 2013</span></dt>
+<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
+<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
+<dd>Some of the recent changes made to NetSurf have included a rewritten core treeview widget. It fixes bugs, provides a nicer look & feel, and yields an improvement to startup time. The Global History, Hotlist (Bookmarks), Cookie Manager, and SSL Certificate inspection treeviews have all been rewritten with the new treeview. Another recent change is the addition of undo and redo support to NetSurf's textarea widget.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/09/strive-for-continuous-improv...">Continuous Integration experiences</a> <span>05 Sep 2013</span></dt>
+<dd>We've been running our Jenkins based <a href="http://ci.netsurf-browser.org/">Continuous Integration (CI)</a> system for a year now. It now builds NetSurf and our libraries for multiple architecture, operating systems and with different compilers. It runs static analysis, automated testing, produces test coverage reports, code documentation and more. Vince has written up <a href="http://vincentsanders.blogspot.co.uk/2013/09/strive-for-continuous-improv...">our experience</a> with the CI system.</dd>
<dt><a href="http://www.netsurf-browser.org/downloads/">NetSurf 3.0 released</a> <span>20 Apr 2013</span></dt>
<dd>NetSurf 3.0 contains many changes over the 2.x release series. The biggest difference is the use of our new Document Object Model library, <a href="http://www.netsurf-browser.org/projects/libdom/">LibDOM</a>. This new library is a foundation that paves the way for us to implement a fully dynamic layout engine in the future. Other improvements in NetSurf 3.0 include completely new textarea support, ability to fetch and parse CSS in parallel with HTML documents, extensive behind-the-scenes refactoring, and a host of smaller changes and fixes. A more complete listing is available in the <a href="http://download.netsurf-browser.org/netsurf/releases/ChangeLog.txt">Change Log</a>.</dd>
<dt><a href="http://www.wakefieldshow.org.uk/">NetSurf at the Wakefield Show</a> <span>23 Mar 2013</span></dt>
<dd>The NetSurf developers will be exhibiting at the Wakefield RISC OS trade show on Saturday 20th April. Please visit our stand to discuss issues, future plans, or just to meet the developers.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/03/man-cannot-discover-new-ocea...">Developer guide – 2: Working with the codebase and community</a> <span>07 Mar 2013</span></dt>
+<dd>The second part to Vince's development guide for newcomers to the project. This one examines the code, how its arranged, and how to interact with the existing developers.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/03/the-way-to-get-started-is-to...">Developer guide – 1: Getting & building the source</a> <span>07 Mar 2013</span></dt>
+<dd>Vince is producing a series of posts to help enable new contributers get involved with the project. This first post covers the mechanics of acquiring and building the source.</dd>
<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-users-netsurf-browser.org/...">New textarea handling</a> <span>11 Feb 2013</span></dt>
<dd>We've rewritten NetSurf's textarea support, so composing webmail, forum posting, and form filling should be more reliable now. Support for text selection and other behaviour is improved.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/01/gource.html">Project development visulisations</a> <span>01 Jan 2013</span></dt>
+<dd>Vince has produced <a href="http://code.google.com/p/gource/">Gource</a> animations that show the development of our project graphically. The videos habe been uploaded to <a href="http://www.youtube.com/playlist?list=PLDdL0LpD7UK69yb6iB6NyhxK1QJNnlzZJ">YouTube</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Early JavaScript builds available</a> <span>13 Dec 2012</span></dt>
<dd>While there is a very long way to go before NetSurf becomes a fully JavaScript-capable browser, brave users may like to try the JavaScript enabled test builds from our <a href="http://ci.netsurf-browser.org/builds/">autobuilder</a>.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2012/11/another-netsurf-developer-wo...">Development progress</a> <span>05 Nov 2012</span></dt>
diff --git a/index.en b/index.en
index 7b1c238..6aac82a 100644
--- a/index.en
+++ b/index.en
@@ -146,12 +146,12 @@
<h2 id="news">Latest news</h2>
<dl class="frontnews">
-<dt><a href="http://www.netsurf-browser.org/downloads/">NetSurf 3.0 released</a> <span>20 Apr 2013</span></dt>
-<dd>NetSurf 3.0 contains many changes over the 2.x release series. The biggest difference is the use of our new Document Object Model library, <a href="http://www.netsurf-browser.org/projects/libdom/">LibDOM</a>. This new library is a foundation that paves the way for us to implement a fully dynamic layout engine in the future. Other improvements in NetSurf 3.0 include completely new textarea support, ability to fetch and parse CSS in parallel with HTML documents, extensive behind-the-scenes refactoring, and a host of smaller changes and fixes. A more complete listing is available in the <a href="http://download.netsurf-browser.org/netsurf/releases/ChangeLog.txt">Change Log</a>.</dd>
-<dt><a href="http://www.wakefieldshow.org.uk/">NetSurf at the Wakefield Show</a> <span>23 Mar 2013</span></dt>
-<dd>The NetSurf developers will be exhibiting at the Wakefield RISC OS trade show on Saturday 20th April. Please visit our stand to discuss issues, future plans, or just to meet the developers.</dd>
-<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-users-netsurf-browser.org/...">New textarea handling</a> <span>11 Feb 2013</span></dt>
-<dd>We've rewritten NetSurf's textarea support, so composing webmail, forum posting, and form filling should be more reliable now. Support for text selection and other behaviour is improved.</dd>
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS performance boost</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of NetSurf's codebase</a> <span>22 Nov 2013</span></dt>
+<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
+<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
+<dd>Some of the recent changes made to NetSurf have included a rewritten core treeview widget. It fixes bugs, provides a nicer look & feel, and yields an improvement to startup time. The Global History, Hotlist (Bookmarks), Cookie Manager, and SSL Certificate inspection treeviews have all been rewritten with the new treeview. Another recent change is the addition of undo and redo support to NetSurf's textarea widget.</dd>
</dl>
<p class="more"><a href="/about/news" class="seemore">See more news</a></p>
-----------------------------------------------------------------------
Summary of changes:
about/news.en | 14 ++++++++++++++
index.en | 12 ++++++------
2 files changed, 20 insertions(+), 6 deletions(-)
diff --git a/about/news.en b/about/news.en
index 6c73433..0381f08 100644
--- a/about/news.en
+++ b/about/news.en
@@ -57,12 +57,26 @@
<h1>News</h1>
<dl class="news">
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS selection performance optimisation</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of the NetSurf codebase</a> <span>22 Nov 2013</span></dt>
+<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
+<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
+<dd>Some of the recent changes made to NetSurf have included a rewritten core treeview widget. It fixes bugs, provides a nicer look & feel, and yields an improvement to startup time. The Global History, Hotlist (Bookmarks), Cookie Manager, and SSL Certificate inspection treeviews have all been rewritten with the new treeview. Another recent change is the addition of undo and redo support to NetSurf's textarea widget.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/09/strive-for-continuous-improv...">Continuous Integration experiences</a> <span>05 Sep 2013</span></dt>
+<dd>We've been running our Jenkins based <a href="http://ci.netsurf-browser.org/">Continuous Integration (CI)</a> system for a year now. It now builds NetSurf and our libraries for multiple architecture, operating systems and with different compilers. It runs static analysis, automated testing, produces test coverage reports, code documentation and more. Vince has written up <a href="http://vincentsanders.blogspot.co.uk/2013/09/strive-for-continuous-improv...">our experience</a> with the CI system.</dd>
<dt><a href="http://www.netsurf-browser.org/downloads/">NetSurf 3.0 released</a> <span>20 Apr 2013</span></dt>
<dd>NetSurf 3.0 contains many changes over the 2.x release series. The biggest difference is the use of our new Document Object Model library, <a href="http://www.netsurf-browser.org/projects/libdom/">LibDOM</a>. This new library is a foundation that paves the way for us to implement a fully dynamic layout engine in the future. Other improvements in NetSurf 3.0 include completely new textarea support, ability to fetch and parse CSS in parallel with HTML documents, extensive behind-the-scenes refactoring, and a host of smaller changes and fixes. A more complete listing is available in the <a href="http://download.netsurf-browser.org/netsurf/releases/ChangeLog.txt">Change Log</a>.</dd>
<dt><a href="http://www.wakefieldshow.org.uk/">NetSurf at the Wakefield Show</a> <span>23 Mar 2013</span></dt>
<dd>The NetSurf developers will be exhibiting at the Wakefield RISC OS trade show on Saturday 20th April. Please visit our stand to discuss issues, future plans, or just to meet the developers.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/03/man-cannot-discover-new-ocea...">Developer guide – 2: Working with the codebase and community</a> <span>07 Mar 2013</span></dt>
+<dd>The second part to Vince's development guide for newcomers to the project. This one examines the code, how its arranged, and how to interact with the existing developers.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/03/the-way-to-get-started-is-to...">Developer guide – 1: Getting & building the source</a> <span>07 Mar 2013</span></dt>
+<dd>Vince is producing a series of posts to help enable new contributers get involved with the project. This first post covers the mechanics of acquiring and building the source.</dd>
<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-users-netsurf-browser.org/...">New textarea handling</a> <span>11 Feb 2013</span></dt>
<dd>We've rewritten NetSurf's textarea support, so composing webmail, forum posting, and form filling should be more reliable now. Support for text selection and other behaviour is improved.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/01/gource.html">Project development visulisations</a> <span>01 Jan 2013</span></dt>
+<dd>Vince has produced <a href="http://code.google.com/p/gource/">Gource</a> animations that show the development of our project graphically. The videos habe been uploaded to <a href="http://www.youtube.com/playlist?list=PLDdL0LpD7UK69yb6iB6NyhxK1QJNnlzZJ">YouTube</a>.</dd>
<dt><a href="http://ci.netsurf-browser.org/builds/">Early JavaScript builds available</a> <span>13 Dec 2012</span></dt>
<dd>While there is a very long way to go before NetSurf becomes a fully JavaScript-capable browser, brave users may like to try the JavaScript enabled test builds from our <a href="http://ci.netsurf-browser.org/builds/">autobuilder</a>.</dd>
<dt><a href="http://vincentsanders.blogspot.co.uk/2012/11/another-netsurf-developer-wo...">Development progress</a> <span>05 Nov 2012</span></dt>
diff --git a/index.en b/index.en
index 7b1c238..6aac82a 100644
--- a/index.en
+++ b/index.en
@@ -146,12 +146,12 @@
<h2 id="news">Latest news</h2>
<dl class="frontnews">
-<dt><a href="http://www.netsurf-browser.org/downloads/">NetSurf 3.0 released</a> <span>20 Apr 2013</span></dt>
-<dd>NetSurf 3.0 contains many changes over the 2.x release series. The biggest difference is the use of our new Document Object Model library, <a href="http://www.netsurf-browser.org/projects/libdom/">LibDOM</a>. This new library is a foundation that paves the way for us to implement a fully dynamic layout engine in the future. Other improvements in NetSurf 3.0 include completely new textarea support, ability to fetch and parse CSS in parallel with HTML documents, extensive behind-the-scenes refactoring, and a host of smaller changes and fixes. A more complete listing is available in the <a href="http://download.netsurf-browser.org/netsurf/releases/ChangeLog.txt">Change Log</a>.</dd>
-<dt><a href="http://www.wakefieldshow.org.uk/">NetSurf at the Wakefield Show</a> <span>23 Mar 2013</span></dt>
-<dd>The NetSurf developers will be exhibiting at the Wakefield RISC OS trade show on Saturday 20th April. Please visit our stand to discuss issues, future plans, or just to meet the developers.</dd>
-<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-users-netsurf-browser.org/...">New textarea handling</a> <span>11 Feb 2013</span></dt>
-<dd>We've rewritten NetSurf's textarea support, so composing webmail, forum posting, and form filling should be more reliable now. Support for text selection and other behaviour is improved.</dd>
+<dt><a href="http://vlists.pepperfish.net/pipermail/netsurf-dev-netsurf-browser.org/20...">LibCSS performance boost</a> <span>02 Dec 2013</span></dt>
+<dd>A significant optimisation has been made to LibCSS's selection engine performance. This is the code that works out which CSS rules apply to DOM elements, and calculates their computed styles. Recent <a href="http://ci.netsurf-browser.org/builds/">development builds</a> of NetSurf are using the updated LibCSS.</dd>
+<dt><a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">Static analysis of NetSurf's codebase</a> <span>22 Nov 2013</span></dt>
+<dd>NetSurf and several of our libraries have recently been added to the <a href="https://scan.coverity.com/">Coverity Scan</a> service for open-source projects. It has enabled us to identify and fix quite a few bugs over a very sort period. We also have the Clang static analyser set up as part of our <a href="http://ci.netsurf-browser.org/">CI system</a>. For more information on the utilisation of static analysis by the NetSurf project, take a look at <a href="http://vincentsanders.blogspot.co.uk/2013/11/error-analysis-is-sweet-spot...">this article</a>.</dd>
+<dt><a href="http://ci.netsurf-browser.org/builds/">Summary of recent development</a> <span>16 Oct 2013</span></dt>
+<dd>Some of the recent changes made to NetSurf have included a rewritten core treeview widget. It fixes bugs, provides a nicer look & feel, and yields an improvement to startup time. The Global History, Hotlist (Bookmarks), Cookie Manager, and SSL Certificate inspection treeviews have all been rewritten with the new treeview. Another recent change is the addition of undo and redo support to NetSurf's textarea widget.</dd>
</dl>
<p class="more"><a href="/about/news" class="seemore">See more news</a></p>
--
NetSurf website source for *.netsurf-browser.org
9 years, 1 month
- 1
- 0
netsurf: branch master updated. release/3.0-781-g71a1a76
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/netsurf.git/shortlog/71a1a762d1f62399be6db...
...commit http://git.netsurf-browser.org/netsurf.git/commit/71a1a762d1f62399be6db0a...
...tree http://git.netsurf-browser.org/netsurf.git/tree/71a1a762d1f62399be6db0aaa...
The branch, master has been updated
via 71a1a762d1f62399be6db0aaae579cb9bf5cf74e (commit)
from b0fc9bfcb9b4e01e0c77bb1e92861e3ab24a8b23 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/netsurf.git/commit/?id=71a1a762d1f62399be6...
commit 71a1a762d1f62399be6db0aaae579cb9bf5cf74e
Author: Ole Loots <ole(a)monochrom.net>
Commit: Ole Loots <ole(a)monochrom.net>
Use LOG(()) instead of printf
diff --git a/atari/deskmenu.c b/atari/deskmenu.c
index 79baf1b..206d7f7 100644
--- a/atari/deskmenu.c
+++ b/atari/deskmenu.c
@@ -544,15 +544,16 @@ static void register_menu_str( struct s_menu_item_evnt * mi )
i = l = strlen(str);
while (i > 2) {
-
if ((strncmp(" ", &str[i], 2) == 0) && (strlen(&str[i]) > 2)) {
// "Standard" Keyboard Shortcut Element found:
+ LOG(("Standard Keyboard Shortcut: \"%s\"\n", &str[i]));
x = i+2;
is_std_shortcut = true;
break;
}
if( str[i] == '['){
+ LOG(("Keyboard Shortcut: \"%s\"\n", &str[i]));
// "Custom" Keyboard Shortcut Element found (identified by [):
x = i;
break;
-----------------------------------------------------------------------
Summary of changes:
atari/deskmenu.c | 3 ++-
1 files changed, 2 insertions(+), 1 deletions(-)
diff --git a/atari/deskmenu.c b/atari/deskmenu.c
index 79baf1b..206d7f7 100644
--- a/atari/deskmenu.c
+++ b/atari/deskmenu.c
@@ -544,15 +544,16 @@ static void register_menu_str( struct s_menu_item_evnt * mi )
i = l = strlen(str);
while (i > 2) {
-
if ((strncmp(" ", &str[i], 2) == 0) && (strlen(&str[i]) > 2)) {
// "Standard" Keyboard Shortcut Element found:
+ LOG(("Standard Keyboard Shortcut: \"%s\"\n", &str[i]));
x = i+2;
is_std_shortcut = true;
break;
}
if( str[i] == '['){
+ LOG(("Keyboard Shortcut: \"%s\"\n", &str[i]));
// "Custom" Keyboard Shortcut Element found (identified by [):
x = i;
break;
--
NetSurf Browser
9 years, 1 month
- 1
- 0
libcss: branch master updated. release/0.2.0-22-g161a5b6
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/libcss.git/shortlog/161a5b63e5a1b63251acc7...
...commit http://git.netsurf-browser.org/libcss.git/commit/161a5b63e5a1b63251acc715...
...tree http://git.netsurf-browser.org/libcss.git/tree/161a5b63e5a1b63251acc715fb...
The branch, master has been updated
via 161a5b63e5a1b63251acc715fb81d9b71dabc9a0 (commit)
from 1a820d249aba97dbc36cdd88cc114918db2eb987 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=161a5b63e5a1b63251ac...
commit 161a5b63e5a1b63251acc715fb81d9b71dabc9a0
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Fixup for insensitive hash utilisation.
diff --git a/src/parse/language.c b/src/parse/language.c
index ed6d515..7003f0b 100644
--- a/src/parse/language.c
+++ b/src/parse/language.c
@@ -1001,7 +1001,8 @@ css_error parseClass(css_language *c, const parserutils_vector *vector,
qname.name = token->idata;
/* Ensure lwc insensitive string is available for class names */
- if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(qname.name) != lwc_error_ok)
return CSS_NOMEM;
return css__stylesheet_selector_detail_init(c->sheet,
@@ -1455,7 +1456,8 @@ css_error parsePseudo(css_language *c, const parserutils_vector *vector,
/* Ensure lwc insensitive string is available
* for element names */
- if (lwc__intern_caseless_string(
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
qname.name) != lwc_error_ok)
return CSS_NOMEM;
@@ -1514,7 +1516,9 @@ css_error parseSpecific(css_language *c,
qname.name = token->idata;
/* Ensure lwc insensitive string is available for id names */
- if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ qname.name) != lwc_error_ok)
return CSS_NOMEM;
error = css__stylesheet_selector_detail_init(c->sheet,
@@ -1634,7 +1638,9 @@ css_error parseTypeSelector(css_language *c, const parserutils_vector *vector,
}
/* Ensure lwc insensitive string is available for element names */
- if (lwc__intern_caseless_string(qname->name) != lwc_error_ok)
+ if (qname->name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ qname->name) != lwc_error_ok)
return CSS_NOMEM;
return CSS_OK;
diff --git a/src/select/hash.c b/src/select/hash.c
index 71b655b..6c0ab7c 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -383,6 +383,12 @@ css_error css__selector_hash_find(css_selector_hash *hash,
/* Find index */
mask = hash->elements.n_slots - 1;
+
+ if (req->qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->qname.name) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->qname.name) & mask;
head = &hash->elements.slots[index];
@@ -393,9 +399,9 @@ css_error css__selector_hash_find(css_selector_hash *hash,
lwc_error lerror;
bool match = false;
- lerror = lwc_string_caseless_isequal(
- req->qname.name,
- head->sel->data.qname.name,
+ lerror = lwc_string_isequal(
+ req->qname.name->insensitive,
+ head->sel->data.qname.name->insensitive,
&match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
@@ -449,6 +455,12 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
/* Find index */
mask = hash->classes.n_slots - 1;
+
+ if (req->class->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->class) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->class) & mask;
head = &hash->classes.slots[index];
@@ -462,8 +474,9 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
n = _class_name(head->sel);
if (n != NULL) {
- lerror = lwc_string_caseless_isequal(
- req->class, n, &match);
+ lerror = lwc_string_isequal(
+ req->class->insensitive,
+ n->insensitive, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
@@ -521,6 +534,12 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
/* Find index */
mask = hash->ids.n_slots - 1;
+
+ if (req->id->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->id) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->id) & mask;
head = &hash->ids.slots[index];
@@ -534,8 +553,9 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
n = _id_name(head->sel);
if (n != NULL) {
- lerror = lwc_string_caseless_isequal(
- req->id, n, &match);
+ lerror = lwc_string_isequal(
+ req->id->insensitive,
+ n->insensitive, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
-----------------------------------------------------------------------
Summary of changes:
src/parse/language.c | 14 ++++++++++----
src/select/hash.c | 34 +++++++++++++++++++++++++++-------
2 files changed, 37 insertions(+), 11 deletions(-)
diff --git a/src/parse/language.c b/src/parse/language.c
index ed6d515..7003f0b 100644
--- a/src/parse/language.c
+++ b/src/parse/language.c
@@ -1001,7 +1001,8 @@ css_error parseClass(css_language *c, const parserutils_vector *vector,
qname.name = token->idata;
/* Ensure lwc insensitive string is available for class names */
- if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(qname.name) != lwc_error_ok)
return CSS_NOMEM;
return css__stylesheet_selector_detail_init(c->sheet,
@@ -1455,7 +1456,8 @@ css_error parsePseudo(css_language *c, const parserutils_vector *vector,
/* Ensure lwc insensitive string is available
* for element names */
- if (lwc__intern_caseless_string(
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
qname.name) != lwc_error_ok)
return CSS_NOMEM;
@@ -1514,7 +1516,9 @@ css_error parseSpecific(css_language *c,
qname.name = token->idata;
/* Ensure lwc insensitive string is available for id names */
- if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ if (qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ qname.name) != lwc_error_ok)
return CSS_NOMEM;
error = css__stylesheet_selector_detail_init(c->sheet,
@@ -1634,7 +1638,9 @@ css_error parseTypeSelector(css_language *c, const parserutils_vector *vector,
}
/* Ensure lwc insensitive string is available for element names */
- if (lwc__intern_caseless_string(qname->name) != lwc_error_ok)
+ if (qname->name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ qname->name) != lwc_error_ok)
return CSS_NOMEM;
return CSS_OK;
diff --git a/src/select/hash.c b/src/select/hash.c
index 71b655b..6c0ab7c 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -383,6 +383,12 @@ css_error css__selector_hash_find(css_selector_hash *hash,
/* Find index */
mask = hash->elements.n_slots - 1;
+
+ if (req->qname.name->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->qname.name) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->qname.name) & mask;
head = &hash->elements.slots[index];
@@ -393,9 +399,9 @@ css_error css__selector_hash_find(css_selector_hash *hash,
lwc_error lerror;
bool match = false;
- lerror = lwc_string_caseless_isequal(
- req->qname.name,
- head->sel->data.qname.name,
+ lerror = lwc_string_isequal(
+ req->qname.name->insensitive,
+ head->sel->data.qname.name->insensitive,
&match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
@@ -449,6 +455,12 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
/* Find index */
mask = hash->classes.n_slots - 1;
+
+ if (req->class->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->class) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->class) & mask;
head = &hash->classes.slots[index];
@@ -462,8 +474,9 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
n = _class_name(head->sel);
if (n != NULL) {
- lerror = lwc_string_caseless_isequal(
- req->class, n, &match);
+ lerror = lwc_string_isequal(
+ req->class->insensitive,
+ n->insensitive, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
@@ -521,6 +534,12 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
/* Find index */
mask = hash->ids.n_slots - 1;
+
+ if (req->id->insensitive == NULL &&
+ lwc__intern_caseless_string(
+ req->id) != lwc_error_ok) {
+ return CSS_NOMEM;
+ }
index = _hash_name(req->id) & mask;
head = &hash->ids.slots[index];
@@ -534,8 +553,9 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
n = _id_name(head->sel);
if (n != NULL) {
- lerror = lwc_string_caseless_isequal(
- req->id, n, &match);
+ lerror = lwc_string_isequal(
+ req->id->insensitive,
+ n->insensitive, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
--
Cascading Style Sheets library
9 years, 1 month
- 1
- 0
libcss: branch master updated. release/0.2.0-21-g1a820d2
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/libcss.git/shortlog/1a820d249aba97dbc36cdd...
...commit http://git.netsurf-browser.org/libcss.git/commit/1a820d249aba97dbc36cdd88...
...tree http://git.netsurf-browser.org/libcss.git/tree/1a820d249aba97dbc36cdd88cc...
The branch, master has been updated
via 1a820d249aba97dbc36cdd88cc114918db2eb987 (commit)
via aad2ae03d349f7cee11efaf4643e6f7e4afa86a9 (commit)
via 8819e781762e81d5c1664dc65636845db91982b5 (commit)
from 3e36d994a1500d3b3d6ebba548ed4c47b641b7c9 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=1a820d249aba97dbc36c...
commit 1a820d249aba97dbc36cdd88cc114918db2eb987
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Since element/class/id names are known to have insensitive string set, just use that hash value for hash table, instead of calculating own hash.
diff --git a/src/select/hash.c b/src/select/hash.c
index 32034e0..71b655b 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -44,7 +44,6 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash_name(const lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
@@ -70,6 +69,14 @@ static css_error _iterate_universal(
const css_selector ***next);
+
+
+/* Get case insensitive hash value for a name.
+ * All element/class/id names are known to have their insensitive ptr set. */
+#define _hash_name(name) \
+ lwc_string_hash_value(name->insensitive)
+
+
/* No bytecode if rule body is empty or wholly invalid --
* Only interested in rules with bytecode */
#define RULE_HAS_BYTECODE(r) \
@@ -634,28 +641,6 @@ css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
******************************************************************************/
/**
- * Name hash function -- case-insensitive FNV.
- *
- * \param name Name to hash
- * \return hash value
- */
-uint32_t _hash_name(const lwc_string *name)
-{
- uint32_t z = 0x811c9dc5;
- const char *data = lwc_string_data(name);
- const char *end = data + lwc_string_length(name);
-
- while (data != end) {
- const char c = *data++;
-
- z *= 0x01000193;
- z ^= c & ~0x20;
- }
-
- return z;
-}
-
-/**
* Retrieve the first class name in a selector, or NULL if none
*
* \param selector Selector to consider
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=aad2ae03d349f7cee11e...
commit aad2ae03d349f7cee11efaf4643e6f7e4afa86a9
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
We know element/id/class names are available through the insensitive ptr now.
diff --git a/src/select/hash.c b/src/select/hash.c
index 5420d6d..32034e0 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -720,7 +720,7 @@ static inline void _chain_bloom_add_detail(
const css_selector_detail *d,
css_bloom bloom[CSS_BLOOM_SIZE])
{
- lwc_string *add = NULL; /* String to add to bloom */
+ lwc_string *add; /* String to add to bloom */
switch (d->type) {
case CSS_SELECTOR_ELEMENT:
@@ -729,33 +729,20 @@ static inline void _chain_bloom_add_detail(
lwc_string_data(d->qname.name)[0] == '*') {
return;
}
-
- /* TODO: Remain case sensitive for XML */
- if (d->qname.name->insensitive == NULL) {
- lwc__intern_caseless_string(d->qname.name);
- }
- add = d->qname.name->insensitive;
- break;
-
+ /* Fall through */
case CSS_SELECTOR_CLASS:
case CSS_SELECTOR_ID:
- /* TODO: Remain case sensitive in standards mode */
- if (d->qname.name->insensitive == NULL) {
- lwc__intern_caseless_string(d->qname.name);
- }
+ /* Element, Id and Class names always have the insensitive
+ * string set at css_selector_detail creation time. */
add = d->qname.name->insensitive;
+
+ if (add != NULL) {
+ css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ }
break;
default:
- return;
- }
-
- /* Don't really care if intern for caseless string failed, if we're
- * out of memory, something else will panic. Everything still works
- * if the string isn't added the the rule bloom. Just less optimally.
- */
- if (add != NULL) {
- css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ break;
}
return;
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=8819e781762e81d5c166...
commit 8819e781762e81d5c1664dc65636845db91982b5
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Ensure that element/class/id names in selector details always get their caseless string.
diff --git a/src/parse/language.c b/src/parse/language.c
index 522c763..ed6d515 100644
--- a/src/parse/language.c
+++ b/src/parse/language.c
@@ -1000,6 +1000,10 @@ css_error parseClass(css_language *c, const parserutils_vector *vector,
qname.ns = NULL;
qname.name = token->idata;
+ /* Ensure lwc insensitive string is available for class names */
+ if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
return css__stylesheet_selector_detail_init(c->sheet,
CSS_SELECTOR_CLASS, &qname, detail_value,
CSS_SELECTOR_DETAIL_VALUE_STRING, false, specific);
@@ -1449,6 +1453,12 @@ css_error parsePseudo(css_language *c, const parserutils_vector *vector,
type = CSS_SELECTOR_ELEMENT;
+ /* Ensure lwc insensitive string is available
+ * for element names */
+ if (lwc__intern_caseless_string(
+ qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
detail_value.string = NULL;
value_type = CSS_SELECTOR_DETAIL_VALUE_STRING;
} else {
@@ -1503,6 +1513,10 @@ css_error parseSpecific(css_language *c,
qname.ns = NULL;
qname.name = token->idata;
+ /* Ensure lwc insensitive string is available for id names */
+ if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
error = css__stylesheet_selector_detail_init(c->sheet,
CSS_SELECTOR_ID, &qname, detail_value,
CSS_SELECTOR_DETAIL_VALUE_STRING, false,
@@ -1619,6 +1633,10 @@ css_error parseTypeSelector(css_language *c, const parserutils_vector *vector,
qname->name = prefix;
}
+ /* Ensure lwc insensitive string is available for element names */
+ if (lwc__intern_caseless_string(qname->name) != lwc_error_ok)
+ return CSS_NOMEM;
+
return CSS_OK;
}
-----------------------------------------------------------------------
Summary of changes:
src/parse/language.c | 18 ++++++++++++++
src/select/hash.c | 62 +++++++++++++------------------------------------
2 files changed, 35 insertions(+), 45 deletions(-)
diff --git a/src/parse/language.c b/src/parse/language.c
index 522c763..ed6d515 100644
--- a/src/parse/language.c
+++ b/src/parse/language.c
@@ -1000,6 +1000,10 @@ css_error parseClass(css_language *c, const parserutils_vector *vector,
qname.ns = NULL;
qname.name = token->idata;
+ /* Ensure lwc insensitive string is available for class names */
+ if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
return css__stylesheet_selector_detail_init(c->sheet,
CSS_SELECTOR_CLASS, &qname, detail_value,
CSS_SELECTOR_DETAIL_VALUE_STRING, false, specific);
@@ -1449,6 +1453,12 @@ css_error parsePseudo(css_language *c, const parserutils_vector *vector,
type = CSS_SELECTOR_ELEMENT;
+ /* Ensure lwc insensitive string is available
+ * for element names */
+ if (lwc__intern_caseless_string(
+ qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
detail_value.string = NULL;
value_type = CSS_SELECTOR_DETAIL_VALUE_STRING;
} else {
@@ -1503,6 +1513,10 @@ css_error parseSpecific(css_language *c,
qname.ns = NULL;
qname.name = token->idata;
+ /* Ensure lwc insensitive string is available for id names */
+ if (lwc__intern_caseless_string(qname.name) != lwc_error_ok)
+ return CSS_NOMEM;
+
error = css__stylesheet_selector_detail_init(c->sheet,
CSS_SELECTOR_ID, &qname, detail_value,
CSS_SELECTOR_DETAIL_VALUE_STRING, false,
@@ -1619,6 +1633,10 @@ css_error parseTypeSelector(css_language *c, const parserutils_vector *vector,
qname->name = prefix;
}
+ /* Ensure lwc insensitive string is available for element names */
+ if (lwc__intern_caseless_string(qname->name) != lwc_error_ok)
+ return CSS_NOMEM;
+
return CSS_OK;
}
diff --git a/src/select/hash.c b/src/select/hash.c
index 5420d6d..71b655b 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -44,7 +44,6 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash_name(const lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
@@ -70,6 +69,14 @@ static css_error _iterate_universal(
const css_selector ***next);
+
+
+/* Get case insensitive hash value for a name.
+ * All element/class/id names are known to have their insensitive ptr set. */
+#define _hash_name(name) \
+ lwc_string_hash_value(name->insensitive)
+
+
/* No bytecode if rule body is empty or wholly invalid --
* Only interested in rules with bytecode */
#define RULE_HAS_BYTECODE(r) \
@@ -634,28 +641,6 @@ css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
******************************************************************************/
/**
- * Name hash function -- case-insensitive FNV.
- *
- * \param name Name to hash
- * \return hash value
- */
-uint32_t _hash_name(const lwc_string *name)
-{
- uint32_t z = 0x811c9dc5;
- const char *data = lwc_string_data(name);
- const char *end = data + lwc_string_length(name);
-
- while (data != end) {
- const char c = *data++;
-
- z *= 0x01000193;
- z ^= c & ~0x20;
- }
-
- return z;
-}
-
-/**
* Retrieve the first class name in a selector, or NULL if none
*
* \param selector Selector to consider
@@ -720,7 +705,7 @@ static inline void _chain_bloom_add_detail(
const css_selector_detail *d,
css_bloom bloom[CSS_BLOOM_SIZE])
{
- lwc_string *add = NULL; /* String to add to bloom */
+ lwc_string *add; /* String to add to bloom */
switch (d->type) {
case CSS_SELECTOR_ELEMENT:
@@ -729,33 +714,20 @@ static inline void _chain_bloom_add_detail(
lwc_string_data(d->qname.name)[0] == '*') {
return;
}
-
- /* TODO: Remain case sensitive for XML */
- if (d->qname.name->insensitive == NULL) {
- lwc__intern_caseless_string(d->qname.name);
- }
- add = d->qname.name->insensitive;
- break;
-
+ /* Fall through */
case CSS_SELECTOR_CLASS:
case CSS_SELECTOR_ID:
- /* TODO: Remain case sensitive in standards mode */
- if (d->qname.name->insensitive == NULL) {
- lwc__intern_caseless_string(d->qname.name);
- }
+ /* Element, Id and Class names always have the insensitive
+ * string set at css_selector_detail creation time. */
add = d->qname.name->insensitive;
+
+ if (add != NULL) {
+ css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ }
break;
default:
- return;
- }
-
- /* Don't really care if intern for caseless string failed, if we're
- * out of memory, something else will panic. Everything still works
- * if the string isn't added the the rule bloom. Just less optimally.
- */
- if (add != NULL) {
- css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ break;
}
return;
--
Cascading Style Sheets library
9 years, 1 month
- 1
- 0
netsurf: branch master updated. release/3.0-780-gb0fc9bf
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/netsurf.git/shortlog/b0fc9bfcb9b4e01e0c77b...
...commit http://git.netsurf-browser.org/netsurf.git/commit/b0fc9bfcb9b4e01e0c77bb1...
...tree http://git.netsurf-browser.org/netsurf.git/tree/b0fc9bfcb9b4e01e0c77bb1e9...
The branch, master has been updated
via b0fc9bfcb9b4e01e0c77bb1e92861e3ab24a8b23 (commit)
from 14387a53b7ab2e15790a733c3db5841f6705fc89 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/netsurf.git/commit/?id=b0fc9bfcb9b4e01e0c7...
commit b0fc9bfcb9b4e01e0c77bb1e92861e3ab24a8b23
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Optimise selection by generating node ancestor element/class/id name bloom filters for new libcss API.
diff --git a/css/select.c b/css/select.c
index 812bc06..40755cb 100644
--- a/css/select.c
+++ b/css/select.c
@@ -33,6 +33,8 @@
#include "utils/url.h"
#include "utils/utils.h"
+#undef PRINT_NODE_BLOOM_DETAILS
+
static css_error node_name(void *pw, void *node, css_qname *qname);
static css_error node_classes(void *pw, void *node,
lwc_string ***classes, uint32_t *n_classes);
@@ -211,6 +213,67 @@ css_stylesheet *nscss_create_inline_style(const uint8_t *data, size_t len,
return sheet;
}
+#ifdef PRINT_NODE_BLOOM_DETAILS
+/* Count bits set in uint32_t */
+static int bits_set(uint32_t n) {
+ n = n - ((n >> 1) & 0x55555555);
+ n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
+ n = (n + (n >> 4)) & 0x0f0f0f0f;
+ n = n + (n >> 8);
+ n = n + (n >> 16);
+ return n & 0x0000003f;
+}
+
+/* Node bloom instrumentation ouput display. */
+static void print_node_bloom_details(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ printf("Node bloom:\t");
+ int total = 0, i;
+ int set[CSS_BLOOM_SIZE];
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ set[i] = bits_set(bloom[i]);
+ total += set[i];
+ }
+ printf("bits set:");
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ printf(" %2i", set[i]);
+ }
+ printf(" (total:%4i of %i) saturation: %3i%%\n", total,
+ (32 * CSS_BLOOM_SIZE),
+ (100 * total) / (32 * CSS_BLOOM_SIZE));
+}
+#endif
+
+/* Handler for libdom node user data
+ * We store our libcss selection bloom filter on the DOM node. */
+static void nscss_dom_user_data_handler(dom_node_operation operation,
+ dom_string *key, void *data, struct dom_node *src,
+ struct dom_node *dst)
+{
+ bool match;
+
+ if (lwc_string_isequal(corestring_dom_key_css_bloom, key, &match) !=
+ lwc_error_ok || match == false || data == NULL) {
+ return;
+ }
+
+ switch (operation) {
+ case DOM_NODE_CLONED:
+ case DOM_NODE_IMPORTED:
+ case DOM_NODE_RENAMED:
+ case DOM_NODE_ADOPTED:
+ /* TODO: Do something about these.
+ * For now, just cautiously fall through to delete.
+ */
+ case DOM_NODE_DELETED:
+ free(data);
+ break;
+ default:
+ LOG(("User data operation not handled."));
+ assert(0);
+ }
+}
+
/**
* Get a style selection results (partial computed styles) for an element
*
@@ -228,14 +291,55 @@ css_select_results *nscss_get_style(nscss_select_ctx *ctx, dom_node *n,
css_allocator_fn alloc, void *pw)
{
css_select_results *styles;
+ css_bloom *bloom = NULL;
+ dom_exception err;
css_error error;
- error = css_select_style(ctx->ctx, n, media, inline_style,
+ /* Create the node's bloom */
+ ctx->bloom = calloc(sizeof(css_bloom), CSS_BLOOM_SIZE);
+ if (ctx->bloom == NULL) {
+ return NULL;
+ }
+
+ /* Get parent node */
+ ctx->parent = NULL;
+ dom_element_parent_node((struct dom_element *) n, &(ctx->parent));
+
+ /* Get parent node's bloom */
+ if (ctx->parent != NULL) {
+ err = dom_node_get_user_data(ctx->parent,
+ corestring_dom_key_css_bloom, (void *) &bloom);
+ if (err != DOM_NO_ERR) {
+ dom_node_unref(ctx->parent);
+ return NULL;
+ }
+ /* TODO: no bloom; walk up the tree to generate it. */
+ assert(bloom != NULL);
+ } else {
+ /* No parents means empty bloom. Just use node bloom. */
+ bloom = ctx->bloom;
+ }
+
+ /* Select style for node */
+ ctx->current = n;
+ error = css_select_style(ctx->ctx, n, bloom, media, inline_style,
&selection_handler, ctx, &styles);
if (error != CSS_OK) {
return NULL;
}
+ /* Merge parent bloom into node bloom */
+ css_bloom_merge(bloom, ctx->bloom);
+
+#ifdef PRINT_NODE_BLOOM_DETAILS
+ print_node_bloom_details(ctx->bloom);
+#endif
+
+ /* Set this node's bloom */
+ /* TODO: For now, this is LEAKED. Move it into libdom? */
+ dom_node_set_user_data(n, corestring_dom_key_css_bloom, ctx->bloom,
+ nscss_dom_user_data_handler, (void *) &bloom);
+
return styles;
}
@@ -329,8 +433,8 @@ css_error nscss_compute_font_size(void *pw, const css_hint *parent,
/* Grab parent size, defaulting to medium if none */
if (parent == NULL) {
parent_size.value = FDIV(FMUL(factors[CSS_FONT_SIZE_MEDIUM - 1],
- INTTOFIX(nsoption_int(font_size))),
- INTTOFIX(10));
+ INTTOFIX(nsoption_int(font_size))),
+ INTTOFIX(10));
parent_size.unit = CSS_UNIT_PT;
} else {
assert(parent->status == CSS_FONT_SIZE_DIMENSION);
@@ -346,8 +450,7 @@ css_error nscss_compute_font_size(void *pw, const css_hint *parent,
if (size->status < CSS_FONT_SIZE_LARGER) {
/* Keyword -- simple */
size->data.length.value = FDIV(FMUL(factors[size->status - 1],
- INTTOFIX(nsoption_int(font_size))),
- F_10);
+ INTTOFIX(nsoption_int(font_size))), F_10);
size->data.length.unit = CSS_UNIT_PT;
} else if (size->status == CSS_FONT_SIZE_LARGER) {
/** \todo Step within table, if appropriate */
@@ -455,6 +558,7 @@ bool nscss_parse_colour(const char *data, css_color *result)
*/
css_error node_name(void *pw, void *node, css_qname *qname)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_string *name;
dom_exception err;
@@ -471,6 +575,21 @@ css_error node_name(void *pw, void *node, css_qname *qname)
return CSS_NOMEM;
}
+ /* If 'n' is the element we are currently selecting for,
+ * add element name to the node's bloom. */
+ if (n == ctx->current) {
+ /* Element names are case insensitive in HTML */
+ if (qname->name->insensitive == NULL) {
+ if (lwc__intern_caseless_string(qname->name) !=
+ lwc_error_ok) {
+ dom_string_unref(name);
+ return CSS_NOMEM;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom, lwc_string_hash_value(
+ qname->name->insensitive));
+ }
+
dom_string_unref(name);
return CSS_OK;
@@ -493,8 +612,10 @@ css_error node_name(void *pw, void *node, css_qname *qname)
css_error node_classes(void *pw, void *node,
lwc_string ***classes, uint32_t *n_classes)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_exception err;
+ unsigned int i;
*classes = NULL;
*n_classes = 0;
@@ -503,7 +624,34 @@ css_error node_classes(void *pw, void *node,
if (err != DOM_NO_ERR)
return CSS_NOMEM;
+ /* If 'n' is the element we are currently selecting for,
+ * add class names to the node's bloom. */
+ if (n == ctx->current) {
+ lwc_string *s;
+ for (i = 0; i < (*n_classes); i++) {
+ s = (*classes)[i];
+ /* TODO: remain case sensitive in standards mode */
+ if (s->insensitive == NULL) {
+ if (lwc__intern_caseless_string(s) !=
+ lwc_error_ok) {
+ goto error;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom,
+ lwc_string_hash_value(s->insensitive));
+ }
+ }
+
return CSS_OK;
+
+error:
+
+ for (i = 0; i < (*n_classes); i++)
+ lwc_string_unref((*classes)[i]);
+
+ free(*classes);
+
+ return CSS_NOMEM;
}
/**
@@ -517,6 +665,7 @@ css_error node_classes(void *pw, void *node,
*/
css_error node_id(void *pw, void *node, lwc_string **id)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_string *attr;
dom_exception err;
@@ -534,6 +683,18 @@ css_error node_id(void *pw, void *node, lwc_string **id)
dom_string_unref(attr);
return CSS_NOMEM;
}
+ if (n == ctx->current) {
+ /* TODO: remain case sensitive in standards mode */
+ if ((*id)->insensitive == NULL) {
+ if (lwc__intern_caseless_string(*id) !=
+ lwc_error_ok) {
+ dom_string_unref(attr);
+ return CSS_NOMEM;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom, lwc_string_hash_value(
+ (*id)->insensitive));
+ }
dom_string_unref(attr);
}
diff --git a/css/select.h b/css/select.h
index b28a670..764c43f 100644
--- a/css/select.h
+++ b/css/select.h
@@ -37,6 +37,10 @@ typedef struct nscss_select_ctx
bool quirks;
nsurl *base_url;
lwc_string *universal;
+
+ dom_node *current;
+ dom_element *parent;
+ css_bloom *bloom;
} nscss_select_ctx;
css_stylesheet *nscss_create_inline_style(const uint8_t *data, size_t len,
diff --git a/utils/corestrings.c b/utils/corestrings.c
index cc1d615..9e992b8 100644
--- a/utils/corestrings.c
+++ b/utils/corestrings.c
@@ -174,6 +174,7 @@ dom_string *corestring_dom_invalid;
dom_string *corestring_dom_keydown;
dom_string *corestring_dom_keypress;
dom_string *corestring_dom_keyup;
+dom_string *corestring_dom_key_css_bloom;
dom_string *corestring_dom_link;
dom_string *corestring_dom_load;
dom_string *corestring_dom_loadeddata;
@@ -404,6 +405,7 @@ void corestrings_fini(void)
CSS_DOM_STRING_UNREF(keydown);
CSS_DOM_STRING_UNREF(keypress);
CSS_DOM_STRING_UNREF(keyup);
+ CSS_DOM_STRING_UNREF(key_css_bloom);
CSS_DOM_STRING_UNREF(link);
CSS_DOM_STRING_UNREF(load);
CSS_DOM_STRING_UNREF(loadeddata);
diff --git a/utils/corestrings.h b/utils/corestrings.h
index 8cfd239..c37242a 100644
--- a/utils/corestrings.h
+++ b/utils/corestrings.h
@@ -180,6 +180,7 @@ extern struct dom_string *corestring_dom_invalid;
extern struct dom_string *corestring_dom_keydown;
extern struct dom_string *corestring_dom_keypress;
extern struct dom_string *corestring_dom_keyup;
+extern struct dom_string *corestring_dom_key_css_bloom;
extern struct dom_string *corestring_dom_link;
extern struct dom_string *corestring_dom_load;
extern struct dom_string *corestring_dom_loadeddata;
-----------------------------------------------------------------------
Summary of changes:
css/select.c | 171 +++++++++++++++++++++++++++++++++++++++++++++++++--
css/select.h | 4 +
utils/corestrings.c | 2 +
utils/corestrings.h | 1 +
4 files changed, 173 insertions(+), 5 deletions(-)
diff --git a/css/select.c b/css/select.c
index 812bc06..40755cb 100644
--- a/css/select.c
+++ b/css/select.c
@@ -33,6 +33,8 @@
#include "utils/url.h"
#include "utils/utils.h"
+#undef PRINT_NODE_BLOOM_DETAILS
+
static css_error node_name(void *pw, void *node, css_qname *qname);
static css_error node_classes(void *pw, void *node,
lwc_string ***classes, uint32_t *n_classes);
@@ -211,6 +213,67 @@ css_stylesheet *nscss_create_inline_style(const uint8_t *data, size_t len,
return sheet;
}
+#ifdef PRINT_NODE_BLOOM_DETAILS
+/* Count bits set in uint32_t */
+static int bits_set(uint32_t n) {
+ n = n - ((n >> 1) & 0x55555555);
+ n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
+ n = (n + (n >> 4)) & 0x0f0f0f0f;
+ n = n + (n >> 8);
+ n = n + (n >> 16);
+ return n & 0x0000003f;
+}
+
+/* Node bloom instrumentation ouput display. */
+static void print_node_bloom_details(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ printf("Node bloom:\t");
+ int total = 0, i;
+ int set[CSS_BLOOM_SIZE];
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ set[i] = bits_set(bloom[i]);
+ total += set[i];
+ }
+ printf("bits set:");
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ printf(" %2i", set[i]);
+ }
+ printf(" (total:%4i of %i) saturation: %3i%%\n", total,
+ (32 * CSS_BLOOM_SIZE),
+ (100 * total) / (32 * CSS_BLOOM_SIZE));
+}
+#endif
+
+/* Handler for libdom node user data
+ * We store our libcss selection bloom filter on the DOM node. */
+static void nscss_dom_user_data_handler(dom_node_operation operation,
+ dom_string *key, void *data, struct dom_node *src,
+ struct dom_node *dst)
+{
+ bool match;
+
+ if (lwc_string_isequal(corestring_dom_key_css_bloom, key, &match) !=
+ lwc_error_ok || match == false || data == NULL) {
+ return;
+ }
+
+ switch (operation) {
+ case DOM_NODE_CLONED:
+ case DOM_NODE_IMPORTED:
+ case DOM_NODE_RENAMED:
+ case DOM_NODE_ADOPTED:
+ /* TODO: Do something about these.
+ * For now, just cautiously fall through to delete.
+ */
+ case DOM_NODE_DELETED:
+ free(data);
+ break;
+ default:
+ LOG(("User data operation not handled."));
+ assert(0);
+ }
+}
+
/**
* Get a style selection results (partial computed styles) for an element
*
@@ -228,14 +291,55 @@ css_select_results *nscss_get_style(nscss_select_ctx *ctx, dom_node *n,
css_allocator_fn alloc, void *pw)
{
css_select_results *styles;
+ css_bloom *bloom = NULL;
+ dom_exception err;
css_error error;
- error = css_select_style(ctx->ctx, n, media, inline_style,
+ /* Create the node's bloom */
+ ctx->bloom = calloc(sizeof(css_bloom), CSS_BLOOM_SIZE);
+ if (ctx->bloom == NULL) {
+ return NULL;
+ }
+
+ /* Get parent node */
+ ctx->parent = NULL;
+ dom_element_parent_node((struct dom_element *) n, &(ctx->parent));
+
+ /* Get parent node's bloom */
+ if (ctx->parent != NULL) {
+ err = dom_node_get_user_data(ctx->parent,
+ corestring_dom_key_css_bloom, (void *) &bloom);
+ if (err != DOM_NO_ERR) {
+ dom_node_unref(ctx->parent);
+ return NULL;
+ }
+ /* TODO: no bloom; walk up the tree to generate it. */
+ assert(bloom != NULL);
+ } else {
+ /* No parents means empty bloom. Just use node bloom. */
+ bloom = ctx->bloom;
+ }
+
+ /* Select style for node */
+ ctx->current = n;
+ error = css_select_style(ctx->ctx, n, bloom, media, inline_style,
&selection_handler, ctx, &styles);
if (error != CSS_OK) {
return NULL;
}
+ /* Merge parent bloom into node bloom */
+ css_bloom_merge(bloom, ctx->bloom);
+
+#ifdef PRINT_NODE_BLOOM_DETAILS
+ print_node_bloom_details(ctx->bloom);
+#endif
+
+ /* Set this node's bloom */
+ /* TODO: For now, this is LEAKED. Move it into libdom? */
+ dom_node_set_user_data(n, corestring_dom_key_css_bloom, ctx->bloom,
+ nscss_dom_user_data_handler, (void *) &bloom);
+
return styles;
}
@@ -329,8 +433,8 @@ css_error nscss_compute_font_size(void *pw, const css_hint *parent,
/* Grab parent size, defaulting to medium if none */
if (parent == NULL) {
parent_size.value = FDIV(FMUL(factors[CSS_FONT_SIZE_MEDIUM - 1],
- INTTOFIX(nsoption_int(font_size))),
- INTTOFIX(10));
+ INTTOFIX(nsoption_int(font_size))),
+ INTTOFIX(10));
parent_size.unit = CSS_UNIT_PT;
} else {
assert(parent->status == CSS_FONT_SIZE_DIMENSION);
@@ -346,8 +450,7 @@ css_error nscss_compute_font_size(void *pw, const css_hint *parent,
if (size->status < CSS_FONT_SIZE_LARGER) {
/* Keyword -- simple */
size->data.length.value = FDIV(FMUL(factors[size->status - 1],
- INTTOFIX(nsoption_int(font_size))),
- F_10);
+ INTTOFIX(nsoption_int(font_size))), F_10);
size->data.length.unit = CSS_UNIT_PT;
} else if (size->status == CSS_FONT_SIZE_LARGER) {
/** \todo Step within table, if appropriate */
@@ -455,6 +558,7 @@ bool nscss_parse_colour(const char *data, css_color *result)
*/
css_error node_name(void *pw, void *node, css_qname *qname)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_string *name;
dom_exception err;
@@ -471,6 +575,21 @@ css_error node_name(void *pw, void *node, css_qname *qname)
return CSS_NOMEM;
}
+ /* If 'n' is the element we are currently selecting for,
+ * add element name to the node's bloom. */
+ if (n == ctx->current) {
+ /* Element names are case insensitive in HTML */
+ if (qname->name->insensitive == NULL) {
+ if (lwc__intern_caseless_string(qname->name) !=
+ lwc_error_ok) {
+ dom_string_unref(name);
+ return CSS_NOMEM;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom, lwc_string_hash_value(
+ qname->name->insensitive));
+ }
+
dom_string_unref(name);
return CSS_OK;
@@ -493,8 +612,10 @@ css_error node_name(void *pw, void *node, css_qname *qname)
css_error node_classes(void *pw, void *node,
lwc_string ***classes, uint32_t *n_classes)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_exception err;
+ unsigned int i;
*classes = NULL;
*n_classes = 0;
@@ -503,7 +624,34 @@ css_error node_classes(void *pw, void *node,
if (err != DOM_NO_ERR)
return CSS_NOMEM;
+ /* If 'n' is the element we are currently selecting for,
+ * add class names to the node's bloom. */
+ if (n == ctx->current) {
+ lwc_string *s;
+ for (i = 0; i < (*n_classes); i++) {
+ s = (*classes)[i];
+ /* TODO: remain case sensitive in standards mode */
+ if (s->insensitive == NULL) {
+ if (lwc__intern_caseless_string(s) !=
+ lwc_error_ok) {
+ goto error;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom,
+ lwc_string_hash_value(s->insensitive));
+ }
+ }
+
return CSS_OK;
+
+error:
+
+ for (i = 0; i < (*n_classes); i++)
+ lwc_string_unref((*classes)[i]);
+
+ free(*classes);
+
+ return CSS_NOMEM;
}
/**
@@ -517,6 +665,7 @@ css_error node_classes(void *pw, void *node,
*/
css_error node_id(void *pw, void *node, lwc_string **id)
{
+ nscss_select_ctx *ctx = (nscss_select_ctx *) pw;
dom_node *n = node;
dom_string *attr;
dom_exception err;
@@ -534,6 +683,18 @@ css_error node_id(void *pw, void *node, lwc_string **id)
dom_string_unref(attr);
return CSS_NOMEM;
}
+ if (n == ctx->current) {
+ /* TODO: remain case sensitive in standards mode */
+ if ((*id)->insensitive == NULL) {
+ if (lwc__intern_caseless_string(*id) !=
+ lwc_error_ok) {
+ dom_string_unref(attr);
+ return CSS_NOMEM;
+ }
+ }
+ css_bloom_add_hash(ctx->bloom, lwc_string_hash_value(
+ (*id)->insensitive));
+ }
dom_string_unref(attr);
}
diff --git a/css/select.h b/css/select.h
index b28a670..764c43f 100644
--- a/css/select.h
+++ b/css/select.h
@@ -37,6 +37,10 @@ typedef struct nscss_select_ctx
bool quirks;
nsurl *base_url;
lwc_string *universal;
+
+ dom_node *current;
+ dom_element *parent;
+ css_bloom *bloom;
} nscss_select_ctx;
css_stylesheet *nscss_create_inline_style(const uint8_t *data, size_t len,
diff --git a/utils/corestrings.c b/utils/corestrings.c
index cc1d615..9e992b8 100644
--- a/utils/corestrings.c
+++ b/utils/corestrings.c
@@ -174,6 +174,7 @@ dom_string *corestring_dom_invalid;
dom_string *corestring_dom_keydown;
dom_string *corestring_dom_keypress;
dom_string *corestring_dom_keyup;
+dom_string *corestring_dom_key_css_bloom;
dom_string *corestring_dom_link;
dom_string *corestring_dom_load;
dom_string *corestring_dom_loadeddata;
@@ -404,6 +405,7 @@ void corestrings_fini(void)
CSS_DOM_STRING_UNREF(keydown);
CSS_DOM_STRING_UNREF(keypress);
CSS_DOM_STRING_UNREF(keyup);
+ CSS_DOM_STRING_UNREF(key_css_bloom);
CSS_DOM_STRING_UNREF(link);
CSS_DOM_STRING_UNREF(load);
CSS_DOM_STRING_UNREF(loadeddata);
diff --git a/utils/corestrings.h b/utils/corestrings.h
index 8cfd239..c37242a 100644
--- a/utils/corestrings.h
+++ b/utils/corestrings.h
@@ -180,6 +180,7 @@ extern struct dom_string *corestring_dom_invalid;
extern struct dom_string *corestring_dom_keydown;
extern struct dom_string *corestring_dom_keypress;
extern struct dom_string *corestring_dom_keyup;
+extern struct dom_string *corestring_dom_key_css_bloom;
extern struct dom_string *corestring_dom_link;
extern struct dom_string *corestring_dom_load;
extern struct dom_string *corestring_dom_loadeddata;
--
NetSurf Browser
9 years, 1 month
- 1
- 0
libcss: branch master updated. release/0.2.0-18-g3e36d99
by NetSurf Browser Project
Gitweb links:
...log http://git.netsurf-browser.org/libcss.git/shortlog/3e36d994a1500d3b3d6ebb...
...commit http://git.netsurf-browser.org/libcss.git/commit/3e36d994a1500d3b3d6ebba5...
...tree http://git.netsurf-browser.org/libcss.git/tree/3e36d994a1500d3b3d6ebba548...
The branch, master has been updated
via 3e36d994a1500d3b3d6ebba548ed4c47b641b7c9 (commit)
via d32e3c3c06d0f7cd0fb81545dd168364cefad68f (commit)
via cea0f412145c239a7583c10554c2d88964e94fd7 (commit)
via d2460b3a2f2690813abdf3b350be9dc5ebf2fe18 (commit)
from 024a89ef4d52d1cbfc9f5289a2f075b8f401b2ff (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=3e36d994a1500d3b3d6e...
commit 3e36d994a1500d3b3d6ebba548ed4c47b641b7c9
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Add selection test using bloom filter.
diff --git a/test/INDEX b/test/INDEX
index b519b1f..1c776c6 100644
--- a/test/INDEX
+++ b/test/INDEX
@@ -11,6 +11,7 @@ number Conversion of numbers to fixed point number
parse-auto Automated parser tests (bytecode) parse
parse2-auto Automated parser tests (om & invalid) parse2
select-auto Automated selection engine tests select
+sel-bloom-auto Automated selection tests with bloom select
# Regression tests
diff --git a/test/Makefile b/test/Makefile
index c4d7eee..23d4442 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -2,6 +2,6 @@
DIR_TEST_ITEMS := csdetect:csdetect.c css21:css21.c lex:lex.c \
lex-auto:lex-auto.c number:number.c \
parse:parse.c parse-auto:parse-auto.c parse2-auto:parse2-auto.c \
- select-auto:select-auto.c
+ select-auto:select-auto.c sel-bloom-auto:select-bloom-auto.c
include $(NSBUILD)/Makefile.subdir
diff --git a/test/select-bloom-auto.c b/test/select-bloom-auto.c
new file mode 100644
index 0000000..2d8628d
--- /dev/null
+++ b/test/select-bloom-auto.c
@@ -0,0 +1,1631 @@
+#include <ctype.h>
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <libcss/libcss.h>
+#include <libcss/computed.h>
+#include <libcss/select.h>
+#include <libcss/stylesheet.h>
+
+#include "utils/utils.h"
+
+#include "dump_computed.h"
+#include "testutils.h"
+
+typedef struct attribute {
+ lwc_string *name;
+ lwc_string *value;
+} attribute;
+
+typedef struct node {
+ lwc_string *name;
+
+ uint32_t n_attrs;
+ attribute *attrs;
+
+ struct node *parent;
+ struct node *next;
+ struct node *prev;
+ struct node *children;
+ struct node *last_child;
+} node;
+
+typedef struct sheet_ctx {
+ css_stylesheet *sheet;
+ css_origin origin;
+ uint64_t media;
+} sheet_ctx;
+
+typedef struct line_ctx {
+ size_t explen;
+ size_t expused;
+ char *exp;
+
+ bool intree;
+ bool insheet;
+ bool inerrors;
+ bool inexp;
+
+ node *tree;
+ node *current;
+ uint32_t depth;
+
+ uint32_t n_sheets;
+ sheet_ctx *sheets;
+
+ uint64_t media;
+ uint32_t pseudo_element;
+ node *target;
+
+ lwc_string *attr_class;
+ lwc_string *attr_id;
+} line_ctx;
+
+static bool handle_line(const char *data, size_t datalen, void *pw);
+static void css__parse_tree(line_ctx *ctx, const char *data, size_t len);
+static void css__parse_tree_data(line_ctx *ctx, const char *data, size_t len);
+static void css__parse_sheet(line_ctx *ctx, const char *data, size_t len);
+static void css__parse_media_list(const char **data, size_t *len, uint64_t *media);
+static void css__parse_pseudo_list(const char **data, size_t *len,
+ uint32_t *element);
+static void css__parse_expected(line_ctx *ctx, const char *data, size_t len);
+static void run_test(line_ctx *ctx, const char *exp, size_t explen);
+static void destroy_tree(node *root);
+
+static css_error node_name(void *pw, void *node,
+ css_qname *qname);
+static css_error node_classes(void *pw, void *node,
+ lwc_string ***classes, uint32_t *n_classes);
+static css_error node_id(void *pw, void *node,
+ lwc_string **id);
+static css_error named_ancestor_node(void *pw, void *node,
+ const css_qname *qname,
+ void **ancestor);
+static css_error named_parent_node(void *pw, void *node,
+ const css_qname *qname,
+ void **parent);
+static css_error named_sibling_node(void *pw, void *node,
+ const css_qname *qname,
+ void **sibling);
+static css_error named_generic_sibling_node(void *pw, void *node,
+ const css_qname *qname,
+ void **sibling);
+static css_error parent_node(void *pw, void *node, void **parent);
+static css_error sibling_node(void *pw, void *node, void **sibling);
+static css_error node_has_name(void *pw, void *node,
+ const css_qname *qname,
+ bool *match);
+static css_error node_has_class(void *pw, void *node,
+ lwc_string *name,
+ bool *match);
+static css_error node_has_id(void *pw, void *node,
+ lwc_string *name,
+ bool *match);
+static css_error node_has_attribute(void *pw, void *node,
+ const css_qname *qname,
+ bool *match);
+static css_error node_has_attribute_equal(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_has_attribute_dashmatch(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_has_attribute_includes(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_has_attribute_prefix(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_has_attribute_suffix(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_has_attribute_substring(void *pw, void *node,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match);
+static css_error node_is_root(void *pw, void *node, bool *match);
+static css_error node_count_siblings(void *pw, void *node,
+ bool same_name, bool after, int32_t *count);
+static css_error node_is_empty(void *pw, void *node, bool *match);
+static css_error node_is_link(void *pw, void *node, bool *match);
+static css_error node_is_visited(void *pw, void *node, bool *match);
+static css_error node_is_hover(void *pw, void *node, bool *match);
+static css_error node_is_active(void *pw, void *node, bool *match);
+static css_error node_is_focus(void *pw, void *node, bool *match);
+static css_error node_is_enabled(void *pw, void *node, bool *match);
+static css_error node_is_disabled(void *pw, void *node, bool *match);
+static css_error node_is_checked(void *pw, void *node, bool *match);
+static css_error node_is_target(void *pw, void *node, bool *match);
+static css_error node_is_lang(void *pw, void *node,
+ lwc_string *lang, bool *match);
+static css_error node_presentational_hint(void *pw, void *node,
+ uint32_t property, css_hint *hint);
+static css_error ua_default_for_property(void *pw, uint32_t property,
+ css_hint *hint);
+static css_error compute_font_size(void *pw, const css_hint *parent,
+ css_hint *size);
+
+static css_select_handler select_handler = {
+ CSS_SELECT_HANDLER_VERSION_1,
+
+ node_name,
+ node_classes,
+ node_id,
+ named_ancestor_node,
+ named_parent_node,
+ named_sibling_node,
+ named_generic_sibling_node,
+ parent_node,
+ sibling_node,
+ node_has_name,
+ node_has_class,
+ node_has_id,
+ node_has_attribute,
+ node_has_attribute_equal,
+ node_has_attribute_dashmatch,
+ node_has_attribute_includes,
+ node_has_attribute_prefix,
+ node_has_attribute_suffix,
+ node_has_attribute_substring,
+ node_is_root,
+ node_count_siblings,
+ node_is_empty,
+ node_is_link,
+ node_is_visited,
+ node_is_hover,
+ node_is_active,
+ node_is_focus,
+ node_is_enabled,
+ node_is_disabled,
+ node_is_checked,
+ node_is_target,
+ node_is_lang,
+ node_presentational_hint,
+ ua_default_for_property,
+ compute_font_size
+};
+
+static void *myrealloc(void *data, size_t len, void *pw)
+{
+ UNUSED(pw);
+
+ return realloc(data, len);
+}
+
+static css_error resolve_url(void *pw,
+ const char *base, lwc_string *rel, lwc_string **abs)
+{
+ UNUSED(pw);
+ UNUSED(base);
+
+ /* About as useless as possible */
+ *abs = lwc_string_ref(rel);
+
+ return CSS_OK;
+}
+
+static bool fail_because_lwc_leaked = false;
+
+static void
+printing_lwc_iterator(lwc_string *str, void *pw)
+{
+ UNUSED(pw);
+
+ printf(" DICT: %*s\n", (int)(lwc_string_length(str)), lwc_string_data(str));
+ fail_because_lwc_leaked = true;
+}
+
+int main(int argc, char **argv)
+{
+ line_ctx ctx;
+
+ if (argc != 2) {
+ printf("Usage: %s <filename>\n", argv[0]);
+ return 1;
+ }
+
+ memset(&ctx, 0, sizeof(ctx));
+
+
+ lwc_intern_string("class", SLEN("class"), &ctx.attr_class);
+ lwc_intern_string("id", SLEN("id"), &ctx.attr_id);
+
+ assert(css__parse_testfile(argv[1], handle_line, &ctx) == true);
+
+ /* and run final test */
+ if (ctx.tree != NULL)
+ run_test(&ctx, ctx.exp, ctx.expused);
+
+ free(ctx.exp);
+
+ lwc_string_unref(ctx.attr_class);
+ lwc_string_unref(ctx.attr_id);
+
+ lwc_iterate_strings(printing_lwc_iterator, NULL);
+
+ assert(fail_because_lwc_leaked == false);
+
+ printf("PASS\n");
+ return 0;
+}
+
+bool handle_line(const char *data, size_t datalen, void *pw)
+{
+ line_ctx *ctx = (line_ctx *) pw;
+ css_error error;
+
+ if (data[0] == '#') {
+ if (ctx->intree) {
+ if (strncasecmp(data+1, "errors", 6) == 0) {
+ ctx->intree = false;
+ ctx->insheet = false;
+ ctx->inerrors = true;
+ ctx->inexp = false;
+ } else {
+ /* Assume start of stylesheet */
+ css__parse_sheet(ctx, data + 1, datalen - 1);
+
+ ctx->intree = false;
+ ctx->insheet = true;
+ ctx->inerrors = false;
+ ctx->inexp = false;
+ }
+ } else if (ctx->insheet) {
+ if (strncasecmp(data+1, "errors", 6) == 0) {
+ assert(css_stylesheet_data_done(
+ ctx->sheets[ctx->n_sheets - 1].sheet)
+ == CSS_OK);
+
+ ctx->intree = false;
+ ctx->insheet = false;
+ ctx->inerrors = true;
+ ctx->inexp = false;
+ } else if (strncasecmp(data+1, "ua", 2) == 0 ||
+ strncasecmp(data+1, "user", 4) == 0 ||
+ strncasecmp(data+1, "author", 6) == 0) {
+ assert(css_stylesheet_data_done(
+ ctx->sheets[ctx->n_sheets - 1].sheet)
+ == CSS_OK);
+
+ css__parse_sheet(ctx, data + 1, datalen - 1);
+ } else {
+ error = css_stylesheet_append_data(
+ ctx->sheets[ctx->n_sheets - 1].sheet,
+ (const uint8_t *) data,
+ datalen);
+ assert(error == CSS_OK ||
+ error == CSS_NEEDDATA);
+ }
+ } else if (ctx->inerrors) {
+ ctx->intree = false;
+ ctx->insheet = false;
+ ctx->inerrors = false;
+ ctx->inexp = true;
+ } else if (ctx->inexp) {
+ /* This marks end of testcase, so run it */
+ run_test(ctx, ctx->exp, ctx->expused);
+
+ ctx->expused = 0;
+
+ ctx->intree = false;
+ ctx->insheet = false;
+ ctx->inerrors = false;
+ ctx->inexp = false;
+ } else {
+ /* Start state */
+ if (strncasecmp(data+1, "tree", 4) == 0) {
+ css__parse_tree(ctx, data + 5, datalen - 5);
+
+ ctx->intree = true;
+ ctx->insheet = false;
+ ctx->inerrors = false;
+ ctx->inexp = false;
+ }
+ }
+ } else {
+ if (ctx->intree) {
+ /* Not interested in the '|' */
+ css__parse_tree_data(ctx, data + 1, datalen - 1);
+ } else if (ctx->insheet) {
+ error = css_stylesheet_append_data(
+ ctx->sheets[ctx->n_sheets - 1].sheet,
+ (const uint8_t *) data, datalen);
+ assert(error == CSS_OK || error == CSS_NEEDDATA);
+ } else if (ctx->inexp) {
+ css__parse_expected(ctx, data, datalen);
+ }
+ }
+
+ return true;
+}
+
+void css__parse_tree(line_ctx *ctx, const char *data, size_t len)
+{
+ const char *p = data;
+ const char *end = data + len;
+ size_t left;
+
+ /* [ <media_list> <pseudo>? ] ? */
+
+ ctx->media = CSS_MEDIA_ALL;
+ ctx->pseudo_element = CSS_PSEUDO_ELEMENT_NONE;
+
+ /* Consume any leading whitespace */
+ while (p < end && isspace(*p))
+ p++;
+
+ if (p < end) {
+ left = end - p;
+
+ css__parse_media_list(&p, &left, &ctx->media);
+
+ end = p + left;
+ }
+
+ if (p < end) {
+ left = end - p;
+
+ css__parse_pseudo_list(&p, &left, &ctx->pseudo_element);
+ }
+}
+
+void css__parse_tree_data(line_ctx *ctx, const char *data, size_t len)
+{
+ const char *p = data;
+ const char *end = data + len;
+ const char *name = NULL;
+ const char *value = NULL;
+ size_t namelen = 0;
+ size_t valuelen = 0;
+ uint32_t depth = 0;
+ bool target = false;
+
+ /* ' '{depth+1} [ <element> '*'? | <attr> ]
+ *
+ * <element> ::= [^=*[:space:]]+
+ * <attr> ::= [^=*[:space:]]+ '=' [^[:space:]]*
+ */
+
+ while (p < end && isspace(*p)) {
+ depth++;
+ p++;
+ }
+ depth--;
+
+ /* Get element/attribute name */
+ name = p;
+ while (p < end && *p != '=' && *p != '*' && isspace(*p) == false) {
+ namelen++;
+ p++;
+ }
+
+ /* Skip whitespace */
+ while (p < end && isspace(*p))
+ p++;
+
+ if (p < end && *p == '=') {
+ /* Attribute value */
+ p++;
+
+ value = p;
+
+ while (p < end && isspace(*p) == false) {
+ valuelen++;
+ p++;
+ }
+ } else if (p < end && *p == '*') {
+ /* Element is target node */
+ target = true;
+ }
+
+ if (value == NULL) {
+ /* We have an element, so create it */
+ node *n = malloc(sizeof(node));
+ assert(n != NULL);
+
+ memset(n, 0, sizeof(node));
+
+ lwc_intern_string(name, namelen, &n->name);
+
+ /* Insert it into tree */
+ if (ctx->tree == NULL) {
+ ctx->tree = n;
+ } else {
+ assert(depth > 0);
+ assert(depth <= ctx->depth + 1);
+
+ /* Find node to insert into */
+ while (depth <= ctx->depth) {
+ ctx->depth--;
+ ctx->current = ctx->current->parent;
+ }
+
+ /* Insert into current node */
+ if (ctx->current->children == NULL) {
+ ctx->current->children = n;
+ ctx->current->last_child = n;
+ } else {
+ ctx->current->last_child->next = n;
+ n->prev = ctx->current->last_child;
+
+ ctx->current->last_child = n;
+ }
+ n->parent = ctx->current;
+ }
+
+ ctx->current = n;
+ ctx->depth = depth;
+
+ /* Mark the target, if it's us */
+ if (target)
+ ctx->target = n;
+ } else {
+ /* New attribute */
+ attribute *attr;
+
+ attribute *temp = realloc(ctx->current->attrs,
+ (ctx->current->n_attrs + 1) * sizeof(attribute));
+ assert(temp != NULL);
+
+ ctx->current->attrs = temp;
+
+ attr = &ctx->current->attrs[ctx->current->n_attrs];
+
+ lwc_intern_string(name, namelen, &attr->name);
+ lwc_intern_string(value, valuelen, &attr->value);
+
+ ctx->current->n_attrs++;
+ }
+}
+
+void css__parse_sheet(line_ctx *ctx, const char *data, size_t len)
+{
+ css_stylesheet_params params;
+ const char *p;
+ const char *end = data + len;
+ css_origin origin = CSS_ORIGIN_AUTHOR;
+ uint64_t media = CSS_MEDIA_ALL;
+ css_stylesheet *sheet;
+ sheet_ctx *temp;
+
+ /* <origin> <media_list>? */
+
+ /* Find end of origin */
+ for (p = data; p < end; p++) {
+ if (isspace(*p))
+ break;
+ }
+
+ if (p - data == 6 && strncasecmp(data, "author", 6) == 0)
+ origin = CSS_ORIGIN_AUTHOR;
+ else if (p - data == 4 && strncasecmp(data, "user", 4) == 0)
+ origin = CSS_ORIGIN_USER;
+ else if (p - data == 2 && strncasecmp(data, "ua", 2) == 0)
+ origin = CSS_ORIGIN_UA;
+ else
+ assert(0 && "Unknown stylesheet origin");
+
+ /* Skip any whitespace */
+ while (p < end && isspace(*p))
+ p++;
+
+ if (p < end) {
+ size_t ignored = end - p;
+
+ css__parse_media_list(&p, &ignored, &media);
+ }
+
+ params.params_version = CSS_STYLESHEET_PARAMS_VERSION_1;
+ params.level = CSS_LEVEL_21;
+ params.charset = "UTF-8";
+ params.url = "foo";
+ params.title = "foo";
+ params.allow_quirks = false;
+ params.inline_style = false;
+ params.resolve = resolve_url;
+ params.resolve_pw = NULL;
+ params.import = NULL;
+ params.import_pw = NULL;
+ params.color = NULL;
+ params.color_pw = NULL;
+ params.font = NULL;
+ params.font_pw = NULL;
+
+ /** \todo How are we going to handle @import? */
+ assert(css_stylesheet_create(¶ms, myrealloc, NULL,
+ &sheet) == CSS_OK);
+
+ /* Extend array of sheets and append new sheet to it */
+ temp = realloc(ctx->sheets,
+ (ctx->n_sheets + 1) * sizeof(sheet_ctx));
+ assert(temp != NULL);
+
+ ctx->sheets = temp;
+
+ ctx->sheets[ctx->n_sheets].sheet = sheet;
+ ctx->sheets[ctx->n_sheets].origin = origin;
+ ctx->sheets[ctx->n_sheets].media = media;
+
+ ctx->n_sheets++;
+}
+
+void css__parse_media_list(const char **data, size_t *len, uint64_t *media)
+{
+ const char *p = *data;
+ const char *end = p + *len;
+ uint64_t result = 0;
+
+ /* <medium> [ ',' <medium> ]* */
+
+ while (p < end) {
+ const char *start = p;
+
+ /* consume a medium */
+ while (isspace(*p) == false && *p != ',')
+ p++;
+
+ if (p - start == 10 &&
+ strncasecmp(start, "projection", 10) == 0)
+ result |= CSS_MEDIA_PROJECTION;
+ else if (p - start == 8 &&
+ strncasecmp(start, "handheld", 8) == 0)
+ result |= CSS_MEDIA_HANDHELD;
+ else if (p - start == 8 &&
+ strncasecmp(start, "embossed", 8) == 0)
+ result |= CSS_MEDIA_EMBOSSED;
+ else if (p - start == 7 &&
+ strncasecmp(start, "braille", 7) == 0)
+ result |= CSS_MEDIA_BRAILLE;
+ else if (p - start == 6 &&
+ strncasecmp(start, "speech", 6) == 0)
+ result |= CSS_MEDIA_SPEECH;
+ else if (p - start == 6 &&
+ strncasecmp(start, "screen", 6) == 0)
+ result |= CSS_MEDIA_SCREEN;
+ else if (p - start == 5 &&
+ strncasecmp(start, "print", 5) == 0)
+ result |= CSS_MEDIA_PRINT;
+ else if (p - start == 5 &&
+ strncasecmp(start, "aural", 5) == 0)
+ result |= CSS_MEDIA_AURAL;
+ else if (p - start == 3 &&
+ strncasecmp(start, "tty", 3) == 0)
+ result |= CSS_MEDIA_TTY;
+ else if (p - start == 3 &&
+ strncasecmp(start, "all", 3) == 0)
+ result |= CSS_MEDIA_ALL;
+ else if (p - start == 2 &&
+ strncasecmp(start, "tv", 2) == 0)
+ result |= CSS_MEDIA_TV;
+ else
+ assert(0 && "Unknown media type");
+
+ /* Consume whitespace */
+ while (p < end && isspace(*p))
+ p++;
+
+ /* Stop if we've reached the end */
+ if (p == end || *p != ',')
+ break;
+
+ /* Consume comma */
+ p++;
+
+ /* Consume whitespace */
+ while (p < end && isspace(*p))
+ p++;
+ }
+
+ *media = result;
+
+ *data = p;
+ *len = end - p;
+}
+
+void css__parse_pseudo_list(const char **data, size_t *len, uint32_t *element)
+{
+ const char *p = *data;
+ const char *end = p + *len;
+
+ /* <pseudo> [ ',' <pseudo> ]* */
+
+ *element = CSS_PSEUDO_ELEMENT_NONE;
+
+ while (p < end) {
+ const char *start = p;
+
+ /* consume a pseudo */
+ while (isspace(*p) == false && *p != ',')
+ p++;
+
+ /* Pseudo elements */
+ if (p - start == 12 &&
+ strncasecmp(start, "first-letter", 12) == 0)
+ *element = CSS_PSEUDO_ELEMENT_FIRST_LETTER;
+ else if (p - start == 10 &&
+ strncasecmp(start, "first-line", 10) == 0)
+ *element = CSS_PSEUDO_ELEMENT_FIRST_LINE;
+ else if (p - start == 6 &&
+ strncasecmp(start, "before", 6) == 0)
+ *element = CSS_PSEUDO_ELEMENT_BEFORE;
+ else if (p - start == 5 &&
+ strncasecmp(start, "after", 5) == 0)
+ *element = CSS_PSEUDO_ELEMENT_AFTER;
+ else
+ assert(0 && "Unknown pseudo");
+
+ /* Consume whitespace */
+ while (p < end && isspace(*p))
+ p++;
+
+ /* Stop if we've reached the end */
+ if (p == end || *p != ',')
+ break;
+
+ /* Consume comma */
+ p++;
+
+ /* Consume whitespace */
+ while (p < end && isspace(*p))
+ p++;
+ }
+
+ *data = p;
+ *len = end - p;
+}
+
+void css__parse_expected(line_ctx *ctx, const char *data, size_t len)
+{
+ while (ctx->expused + len >= ctx->explen) {
+ size_t required = ctx->explen == 0 ? 64 : ctx->explen * 2;
+ char *temp = realloc(ctx->exp, required);
+ if (temp == NULL) {
+ assert(0 && "No memory for expected output");
+ }
+
+ ctx->exp = temp;
+ ctx->explen = required;
+ }
+
+ memcpy(ctx->exp + ctx->expused, data, len);
+
+ ctx->expused += len;
+}
+
+static void get_bloom_for_target_node(line_ctx *ctx,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ node *n = ctx->target;
+ bool match;
+ uint32_t i;
+
+ css_bloom_init(bloom);
+
+ while (n->parent != NULL) {
+ n = n->parent;
+
+ /* Element name */
+ if (n->name->insensitive == NULL)
+ assert(lwc__intern_caseless_string(n->name) ==
+ lwc_error_ok);
+
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(n->name->insensitive));
+
+ /* Id */
+ for (i = 0; i < n->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ n->attrs[i].name, ctx->attr_id,
+ &match) == lwc_error_ok);
+ if (match == true) {
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(
+ n->attrs[i].value));
+ break;
+ }
+ }
+
+ /* Classes */
+ for (i = 0; i < n->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ n->attrs[i].name, ctx->attr_class,
+ &match) == lwc_error_ok);
+ if (match == true) {
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(
+ n->attrs[i].value));
+ break;
+ }
+ }
+ }
+}
+
+void run_test(line_ctx *ctx, const char *exp, size_t explen)
+{
+ css_select_ctx *select;
+ css_select_results *results;
+ uint32_t i;
+ char *buf;
+ size_t buflen;
+ static int testnum;
+ css_bloom node_bloom[CSS_BLOOM_SIZE];
+
+ UNUSED(exp);
+
+ buf = malloc(8192);
+ if (buf == NULL) {
+ assert(0 && "No memory for result data");
+ }
+ buflen = 8192;
+
+ assert(css_select_ctx_create(myrealloc, NULL, &select) == CSS_OK);
+
+ for (i = 0; i < ctx->n_sheets; i++) {
+ assert(css_select_ctx_append_sheet(select,
+ ctx->sheets[i].sheet, ctx->sheets[i].origin,
+ ctx->sheets[i].media) == CSS_OK);
+ }
+
+ testnum++;
+
+ get_bloom_for_target_node(ctx, node_bloom);
+
+ assert(css_select_style(select, ctx->target, node_bloom, ctx->media, NULL,
+ &select_handler, ctx, &results) == CSS_OK);
+
+ assert(results->styles[ctx->pseudo_element] != NULL);
+
+ dump_computed_style(results->styles[ctx->pseudo_element], buf, &buflen);
+
+ if (8192 - buflen != explen || memcmp(buf, exp, explen) != 0) {
+ printf("Expected (%u):\n%.*s\n",
+ (int) explen, (int) explen, exp);
+ printf("Result (%u):\n%.*s\n", (int) (8192 - buflen),
+ (int) (8192 - buflen), buf);
+ assert(0 && "Result doesn't match expected");
+ }
+
+ /* Clean up */
+ css_select_results_destroy(results);
+ css_select_ctx_destroy(select);
+
+ destroy_tree(ctx->tree);
+
+ for (i = 0; i < ctx->n_sheets; i++) {
+ css_stylesheet_destroy(ctx->sheets[i].sheet);
+ }
+
+ ctx->tree = NULL;
+ ctx->current = NULL;
+ ctx->depth = 0;
+ ctx->n_sheets = 0;
+ free(ctx->sheets);
+ ctx->sheets = NULL;
+ ctx->target = NULL;
+
+ free(buf);
+
+ printf("Test %d: PASS\n", testnum);
+}
+
+void destroy_tree(node *root)
+{
+ node *n, *p;
+ uint32_t i;
+
+ for (n = root->children; n != NULL; n = p) {
+ p = n->next;
+
+ destroy_tree(n);
+ }
+
+ for (i = 0; i < root->n_attrs; ++i) {
+ lwc_string_unref(root->attrs[i].name);
+ lwc_string_unref(root->attrs[i].value);
+ }
+
+ free(root->attrs);
+
+ lwc_string_unref(root->name);
+ free(root);
+}
+
+
+css_error node_name(void *pw, void *n, css_qname *qname)
+{
+ node *node = n;
+
+ UNUSED(pw);
+
+ qname->name = lwc_string_ref(node->name);
+
+ return CSS_OK;
+}
+
+css_error node_classes(void *pw, void *n,
+ lwc_string ***classes, uint32_t *n_classes)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *lc = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch = false;
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, lc->attr_class, &amatch) ==
+ lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ if (i != node->n_attrs) {
+ *classes = realloc(NULL, sizeof(lwc_string **));
+ if (*classes == NULL)
+ return CSS_NOMEM;
+
+ *(classes[0]) =
+ lwc_string_ref(node->attrs[i].value);
+ *n_classes = 1;
+ } else {
+ *classes = NULL;
+ *n_classes = 0;
+ }
+
+ return CSS_OK;
+
+}
+
+css_error node_id(void *pw, void *n,
+ lwc_string **id)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *lc = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch = false;
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, lc->attr_id, &amatch) ==
+ lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ if (i != node->n_attrs)
+ *id = lwc_string_ref(node->attrs[i].value);
+ else
+ *id = NULL;
+
+ return CSS_OK;
+}
+
+css_error named_ancestor_node(void *pw, void *n,
+ const css_qname *qname,
+ void **ancestor)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ for (node = node->parent; node != NULL; node = node->parent) {
+ bool match = false;
+ assert(lwc_string_caseless_isequal(
+ qname->name, node->name,
+ &match) == lwc_error_ok);
+ if (match == true)
+ break;
+ }
+
+ *ancestor = (void *) node;
+
+ return CSS_OK;
+}
+
+css_error named_parent_node(void *pw, void *n,
+ const css_qname *qname,
+ void **parent)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ *parent = NULL;
+ if (node->parent != NULL) {
+ bool match = false;
+ assert(lwc_string_caseless_isequal(
+ qname->name, node->parent->name, &match) ==
+ lwc_error_ok);
+ if (match == true)
+ *parent = (void *) node->parent;
+ }
+
+ return CSS_OK;
+}
+
+css_error named_sibling_node(void *pw, void *n,
+ const css_qname *qname,
+ void **sibling)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ *sibling = NULL;
+ if (node->prev != NULL) {
+ bool match = false;
+ assert(lwc_string_caseless_isequal(
+ qname->name, node->prev->name, &match) ==
+ lwc_error_ok);
+ if (match == true)
+ *sibling = (void *) node->prev;
+ }
+
+ return CSS_OK;
+}
+
+css_error named_generic_sibling_node(void *pw, void *n,
+ const css_qname *qname,
+ void **sibling)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ for (node = node->prev; node != NULL; node = node->prev) {
+ bool match = false;
+ assert(lwc_string_caseless_isequal(
+ qname->name, node->name,
+ &match) == lwc_error_ok);
+ if (match == true)
+ break;
+ }
+
+ *sibling = (void *) node;
+
+ return CSS_OK;
+}
+
+css_error parent_node(void *pw, void *n, void **parent)
+{
+ node *node = n;
+
+ UNUSED(pw);
+
+ *parent = (void *) node->parent;
+
+ return CSS_OK;
+}
+
+css_error sibling_node(void *pw, void *n, void **sibling)
+{
+ node *node = n;
+
+ UNUSED(pw);
+
+ *sibling = (void *) node->prev;
+
+ return CSS_OK;
+}
+
+css_error node_has_name(void *pw, void *n,
+ const css_qname *qname,
+ bool *match)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ if (lwc_string_length(qname->name) == 1 &&
+ lwc_string_data(qname->name)[0] == '*')
+ *match = true;
+ else
+ assert(lwc_string_caseless_isequal(node->name,
+ qname->name, match) == lwc_error_ok);
+
+ return CSS_OK;
+}
+
+css_error node_has_class(void *pw, void *n,
+ lwc_string *name,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *ctx = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch = false;
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, ctx->attr_class,
+ &amatch) == lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ /* Classes are case-sensitive in HTML */
+ if (i != node->n_attrs && name == node->attrs[i].value)
+ *match = true;
+ else
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_has_id(void *pw, void *n,
+ lwc_string *name,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ line_ctx *ctx = pw;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ bool amatch = false;
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, ctx->attr_id, &amatch) ==
+ lwc_error_ok);
+ if (amatch == true)
+ break;
+ }
+
+ /* IDs are case-sensitive in HTML */
+ if (i != node->n_attrs && name == node->attrs[i].value)
+ *match = true;
+ else
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute(void *pw, void *n,
+ const css_qname *qname,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ UNUSED(pw);
+
+ *match = false;
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_equal(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, value, match) ==
+ lwc_error_ok);
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_includes(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ size_t vlen = lwc_string_length(value);
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ const char *p;
+ const char *start = lwc_string_data(node->attrs[i].value);
+ const char *end = start +
+ lwc_string_length(node->attrs[i].value);
+
+ *match = false;
+
+ for (p = start; p < end; p++) {
+ if (*p == ' ') {
+ if ((size_t) (p - start) == vlen &&
+ strncasecmp(start,
+ lwc_string_data(value),
+ vlen) == 0) {
+ *match = true;
+ break;
+ }
+
+ start = p + 1;
+ }
+ }
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_dashmatch(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ size_t vlen = lwc_string_length(value);
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ const char *p;
+ const char *start = lwc_string_data(node->attrs[i].value);
+ const char *end = start +
+ lwc_string_length(node->attrs[i].value);
+
+ *match = false;
+
+ for (p = start; p < end; p++) {
+ if (*p == '-') {
+ if ((size_t) (p - start) == vlen &&
+ strncasecmp(start,
+ lwc_string_data(value),
+ vlen) == 0) {
+ *match = true;
+ break;
+ }
+
+ start = p + 1;
+ }
+ }
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_prefix(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ size_t len = lwc_string_length(node->attrs[i].value);
+ const char *data = lwc_string_data(node->attrs[i].value);
+
+ size_t vlen = lwc_string_length(value);
+ const char *vdata = lwc_string_data(value);
+
+ if (len < vlen)
+ *match = false;
+ else
+ *match = (strncasecmp(data, vdata, vlen) == 0);
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_suffix(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ size_t len = lwc_string_length(node->attrs[i].value);
+ const char *data = lwc_string_data(node->attrs[i].value);
+
+ size_t vlen = lwc_string_length(value);
+ const char *vdata = lwc_string_data(value);
+
+ size_t suffix_start = len - vlen;
+
+ if (len < vlen)
+ *match = false;
+ else {
+ *match = (strncasecmp(data + suffix_start,
+ vdata, vlen) == 0);
+ }
+ }
+
+ return CSS_OK;
+}
+
+css_error node_has_attribute_substring(void *pw, void *n,
+ const css_qname *qname,
+ lwc_string *value,
+ bool *match)
+{
+ node *node = n;
+ uint32_t i;
+ UNUSED(pw);
+
+ *match = false;
+
+ for (i = 0; i < node->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ node->attrs[i].name, qname->name, match) ==
+ lwc_error_ok);
+ if (*match == true)
+ break;
+ }
+
+ if (*match == true) {
+ size_t len = lwc_string_length(node->attrs[i].value);
+ const char *data = lwc_string_data(node->attrs[i].value);
+
+ size_t vlen = lwc_string_length(value);
+ const char *vdata = lwc_string_data(value);
+
+ const char *last_start = data + len - vlen;
+
+ if (len < vlen)
+ *match = false;
+ else {
+ while (data <= last_start) {
+ if (strncasecmp(data, vdata, vlen) == 0) {
+ *match = true;
+ break;
+ }
+
+ data++;
+ }
+
+ if (data > last_start)
+ *match = false;
+ }
+ }
+
+ return CSS_OK;
+}
+
+css_error node_is_root(void *pw, void *n, bool *match)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ *match = (node->parent == NULL);
+
+ return CSS_OK;
+}
+
+css_error node_count_siblings(void *pw, void *n,
+ bool same_name, bool after, int32_t *count)
+{
+ int32_t cnt = 0;
+ bool match = false;
+ node *node = n;
+ lwc_string *name = node->name;
+ UNUSED(pw);
+
+ if (after) {
+ while (node->next != NULL) {
+ if (same_name) {
+ assert(lwc_string_caseless_isequal(
+ name, node->next->name, &match) ==
+ lwc_error_ok);
+
+ if (match)
+ cnt++;
+ } else {
+ cnt++;
+ }
+
+ node = node->next;
+ }
+ } else {
+ while (node->prev != NULL) {
+ if (same_name) {
+ assert(lwc_string_caseless_isequal(
+ name, node->prev->name, &match) ==
+ lwc_error_ok);
+
+ if (match)
+ cnt++;
+ } else {
+ cnt++;
+ }
+
+ node = node->prev;
+ }
+ }
+
+ *count = cnt;
+
+ return CSS_OK;
+}
+
+css_error node_is_empty(void *pw, void *n, bool *match)
+{
+ node *node = n;
+ UNUSED(pw);
+
+ *match = (node->children == NULL);
+
+ return CSS_OK;
+}
+
+css_error node_is_link(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_visited(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_hover(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_active(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_focus(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_enabled(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_disabled(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_checked(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_target(void *pw, void *n, bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_is_lang(void *pw, void *n,
+ lwc_string *lang,
+ bool *match)
+{
+ node *node = n;
+
+ UNUSED(pw);
+ UNUSED(node);
+ UNUSED(lang);
+
+ *match = false;
+
+ return CSS_OK;
+}
+
+css_error node_presentational_hint(void *pw, void *node,
+ uint32_t property, css_hint *hint)
+{
+ UNUSED(pw);
+ UNUSED(node);
+ UNUSED(property);
+ UNUSED(hint);
+
+ return CSS_PROPERTY_NOT_SET;
+}
+
+css_error ua_default_for_property(void *pw, uint32_t property, css_hint *hint)
+{
+ UNUSED(pw);
+
+ if (property == CSS_PROP_COLOR) {
+ hint->data.color = 0xff000000;
+ hint->status = CSS_COLOR_COLOR;
+ } else if (property == CSS_PROP_FONT_FAMILY) {
+ hint->data.strings = NULL;
+ hint->status = CSS_FONT_FAMILY_SANS_SERIF;
+ } else if (property == CSS_PROP_QUOTES) {
+ /* Not exactly useful :) */
+ hint->data.strings = NULL;
+ hint->status = CSS_QUOTES_NONE;
+ } else if (property == CSS_PROP_VOICE_FAMILY) {
+ /** \todo Fix this when we have voice-family done */
+ hint->data.strings = NULL;
+ hint->status = 0;
+ } else {
+ return CSS_INVALID;
+ }
+
+ return CSS_OK;
+}
+
+css_error compute_font_size(void *pw, const css_hint *parent, css_hint *size)
+{
+ static css_hint_length sizes[] = {
+ { FLTTOFIX(6.75), CSS_UNIT_PT },
+ { FLTTOFIX(7.50), CSS_UNIT_PT },
+ { FLTTOFIX(9.75), CSS_UNIT_PT },
+ { FLTTOFIX(12.0), CSS_UNIT_PT },
+ { FLTTOFIX(13.5), CSS_UNIT_PT },
+ { FLTTOFIX(18.0), CSS_UNIT_PT },
+ { FLTTOFIX(24.0), CSS_UNIT_PT }
+ };
+ const css_hint_length *parent_size;
+
+ UNUSED(pw);
+
+ /* Grab parent size, defaulting to medium if none */
+ if (parent == NULL) {
+ parent_size = &sizes[CSS_FONT_SIZE_MEDIUM - 1];
+ } else {
+ assert(parent->status == CSS_FONT_SIZE_DIMENSION);
+ assert(parent->data.length.unit != CSS_UNIT_EM);
+ assert(parent->data.length.unit != CSS_UNIT_EX);
+ parent_size = &parent->data.length;
+ }
+
+ assert(size->status != CSS_FONT_SIZE_INHERIT);
+
+ if (size->status < CSS_FONT_SIZE_LARGER) {
+ /* Keyword -- simple */
+ size->data.length = sizes[size->status - 1];
+ } else if (size->status == CSS_FONT_SIZE_LARGER) {
+ /** \todo Step within table, if appropriate */
+ size->data.length.value =
+ FMUL(parent_size->value, FLTTOFIX(1.2));
+ size->data.length.unit = parent_size->unit;
+ } else if (size->status == CSS_FONT_SIZE_SMALLER) {
+ /** \todo Step within table, if appropriate */
+ size->data.length.value =
+ FMUL(parent_size->value, FLTTOFIX(1.2));
+ size->data.length.unit = parent_size->unit;
+ } else if (size->data.length.unit == CSS_UNIT_EM ||
+ size->data.length.unit == CSS_UNIT_EX) {
+ size->data.length.value =
+ FMUL(size->data.length.value, parent_size->value);
+
+ if (size->data.length.unit == CSS_UNIT_EX) {
+ size->data.length.value = FMUL(size->data.length.value,
+ FLTTOFIX(0.6));
+ }
+
+ size->data.length.unit = parent_size->unit;
+ } else if (size->data.length.unit == CSS_UNIT_PCT) {
+ size->data.length.value = FDIV(FMUL(size->data.length.value,
+ parent_size->value), FLTTOFIX(100));
+ size->data.length.unit = parent_size->unit;
+ }
+
+ size->status = CSS_FONT_SIZE_DIMENSION;
+
+ return CSS_OK;
+}
+
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=d32e3c3c06d0f7cd0fb8...
commit d32e3c3c06d0f7cd0fb81545dd168364cefad68f
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Update for new selection API.
diff --git a/test/select-auto.c b/test/select-auto.c
index 4b664ab..9c1a52b 100644
--- a/test/select-auto.c
+++ b/test/select-auto.c
@@ -708,6 +708,7 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
char *buf;
size_t buflen;
static int testnum;
+ css_bloom node_bloom[CSS_BLOOM_SIZE];
UNUSED(exp);
@@ -727,7 +728,12 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
testnum++;
- assert(css_select_style(select, ctx->target, ctx->media, NULL,
+ /* Not testing bloom functionality here, just set all bits */
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ node_bloom[i] = ~0;
+ }
+
+ assert(css_select_style(select, ctx->target, node_bloom, ctx->media, NULL,
&select_handler, ctx, &results) == CSS_OK);
assert(results->styles[ctx->pseudo_element] != NULL);
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=cea0f412145c239a7583...
commit cea0f412145c239a7583c10554c2d88964e94fd7
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Significantly optimise CSS selection performance.
Now we pass a node bloom filter to css_get_style. That node bloom
filter is filled with the node's ancestor element, class, and id
names. Internally, libcss also generates a bloom filter for each
selector chain. If the selector chain's bloom filter is not a
subset of the node bloom filter, we know that the selector chain's
rule does not apply to the node. This avoids the slow selector
chain matching process.
Other smaller optimisations to move the ruling out of selector
chains for inapplicable media types and other reasons to before
we start comparing rules from different sources to find the next
rule. All this is now done in hash.c so select.c never sees the
trivially ruled out rules.
diff --git a/Makefile b/Makefile
index 68ec9ba..d9a2b9b 100644
--- a/Makefile
+++ b/Makefile
@@ -46,6 +46,7 @@ include $(NSBUILD)/Makefile.top
# Extra installation rules
I := /include/libcss
+INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/bloom.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/computed.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/errors.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/font_face.h
diff --git a/include/libcss/libcss.h b/include/libcss/libcss.h
index 89e83b5..bde2707 100644
--- a/include/libcss/libcss.h
+++ b/include/libcss/libcss.h
@@ -15,6 +15,7 @@ extern "C"
#include <libwapcaplet/libwapcaplet.h>
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/types.h>
#include <libcss/functypes.h>
diff --git a/include/libcss/select.h b/include/libcss/select.h
index 4a95752..9ab2550 100644
--- a/include/libcss/select.h
+++ b/include/libcss/select.h
@@ -13,6 +13,7 @@ extern "C"
{
#endif
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/functypes.h>
#include <libcss/hint.h>
@@ -162,6 +163,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
const css_stylesheet **sheet);
css_error css_select_style(css_select_ctx *ctx, void *node,
+ const css_bloom bloom[CSS_BLOOM_SIZE],
uint64_t media, const css_stylesheet *inline_style,
css_select_handler *handler, void *pw,
css_select_results **result);
diff --git a/src/select/hash.c b/src/select/hash.c
index 37492c1..5420d6d 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -12,8 +12,11 @@
#include "select/hash.h"
#include "utils/utils.h"
+#undef PRINT_CHAIN_BLOOM_DETAILS
+
typedef struct hash_entry {
const css_selector *sel;
+ css_bloom sel_chain_bloom[CSS_BLOOM_SIZE];
struct hash_entry *next;
} hash_entry;
@@ -41,7 +44,7 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash_name(lwc_string *name);
+static inline uint32_t _hash_name(const lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
@@ -49,15 +52,88 @@ static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
static css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
const css_selector *selector);
-static css_error _iterate_elements(const css_selector **current,
+static css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_classes(const css_selector **current,
+static css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_ids(const css_selector **current,
+static css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_universal(const css_selector **current,
+static css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
+
+/* No bytecode if rule body is empty or wholly invalid --
+ * Only interested in rules with bytecode */
+#define RULE_HAS_BYTECODE(r) \
+ (((css_rule_selector *)(r->sel->rule))->style != NULL)
+
+
+/**
+ * Test first selector on selector chain for having matching element name.
+ *
+ * If source of rule is element or universal hash, we know the
+ * element name is a match. If it comes from the class or id hash,
+ * we have to test for a match.
+ *
+ * \param selector selector chain head to test
+ * \param qname element name to look for
+ * \return true iff chain head doesn't fail to match element name
+ */
+static inline bool _chain_good_for_element_name(const css_selector *selector,
+ const css_qname *qname)
+{
+ if (lwc_string_length(selector->data.qname.name) != 1 ||
+ lwc_string_data(selector->data.qname.name)[0] != '*') {
+ bool match;
+ if (lwc_string_caseless_isequal(
+ selector->data.qname.name, qname->name,
+ &match) == lwc_error_ok && match == false) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Test whether the rule applies for current media.
+ *
+ * \param rule Rule to test
+ * \meaid media Current media type(s)
+ * \return true iff chain's rule applies for media
+ */
+static inline bool _rule_good_for_media(const css_rule *rule, uint64_t media)
+{
+ bool applies = true;
+ const css_rule *ancestor = rule;
+
+ while (ancestor != NULL) {
+ const css_rule_media *m = (const css_rule_media *) ancestor;
+
+ if (ancestor->type == CSS_RULE_MEDIA &&
+ (m->media & media) == 0) {
+ applies = false;
+ break;
+ }
+
+ if (ancestor->ptype != CSS_RULE_PARENT_STYLESHEET)
+ ancestor = ancestor->parent;
+ else
+ ancestor = NULL;
+ }
+
+ return applies;
+}
+
+
/**
* Create a hash
*
@@ -288,19 +364,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || qname == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->elements.n_slots - 1;
- index = _hash_name(qname->name) & mask;
+ index = _hash_name(req->qname.name) & mask;
head = &hash->elements.slots[index];
@@ -311,13 +387,22 @@ css_error css__selector_hash_find(css_selector_hash *hash,
bool match = false;
lerror = lwc_string_caseless_isequal(
- qname->name, head->sel->data.qname.name,
+ req->qname.name,
+ head->sel->data.qname.name,
&match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
head = head->next;
}
@@ -344,19 +429,20 @@ css_error css__selector_hash_find(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->class == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->classes.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->class) & mask;
head = &hash->classes.slots[index];
@@ -370,12 +456,24 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
n = _class_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->class, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -403,19 +501,20 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->id == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->ids.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->id) & mask;
head = &hash->ids.slots[index];
@@ -429,12 +528,24 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
n = _id_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->id, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -461,14 +572,39 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
- if (hash == NULL || iterator == NULL || matched == NULL)
+ hash_entry *head;
+
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
+ head = &hash->universal;
+
+ if (head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+
+ head = head->next;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+ }
+
(*iterator) = _iterate_universal;
- (*matched) = (const css_selector **) &hash->universal;
+ (*matched) = (const css_selector **) head;
return CSS_OK;
}
@@ -503,7 +639,7 @@ css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
* \param name Name to hash
* \return hash value
*/
-uint32_t _hash_name(lwc_string *name)
+uint32_t _hash_name(const lwc_string *name)
{
uint32_t z = 0x811c9dc5;
const char *data = lwc_string_data(name);
@@ -573,6 +709,119 @@ lwc_string *_id_name(const css_selector *selector)
return name;
}
+
+/**
+ * Add a selector detail to the bloom filter, if the detail is relevant.
+ *
+ * \param d Selector detail to consider and add if relevant
+ * \param bloom Bloom filter to add to.
+ */
+static inline void _chain_bloom_add_detail(
+ const css_selector_detail *d,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ lwc_string *add = NULL; /* String to add to bloom */
+
+ switch (d->type) {
+ case CSS_SELECTOR_ELEMENT:
+ /* Don't add universal element selector to bloom */
+ if (lwc_string_length(d->qname.name) == 1 &&
+ lwc_string_data(d->qname.name)[0] == '*') {
+ return;
+ }
+
+ /* TODO: Remain case sensitive for XML */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ case CSS_SELECTOR_CLASS:
+ case CSS_SELECTOR_ID:
+ /* TODO: Remain case sensitive in standards mode */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ default:
+ return;
+ }
+
+ /* Don't really care if intern for caseless string failed, if we're
+ * out of memory, something else will panic. Everything still works
+ * if the string isn't added the the rule bloom. Just less optimally.
+ */
+ if (add != NULL) {
+ css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ }
+
+ return;
+}
+
+
+/**
+ * Generate a selector chain's bloom filter
+ *
+ * \param s Selector at head of selector chain
+ * \param bloom Bloom filter to generate.
+ */
+static void _chain_bloom_generate(const css_selector *s,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ css_bloom_init(bloom);
+
+ /* Work back through selector chain... */
+ do {
+ /* ...looking for Ancestor/Parent combinators */
+ if (s->data.comb == CSS_COMBINATOR_ANCESTOR ||
+ s->data.comb == CSS_COMBINATOR_PARENT) {
+ const css_selector_detail *d = &s->combinator->data;
+ while (d != NULL) {
+ if (d->negate == 0) {
+ _chain_bloom_add_detail(d, bloom);
+ }
+ d = (d->next != 0) ? d + 1 : NULL;
+ }
+ }
+
+ s = s->combinator;
+ } while (s != NULL);
+}
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+/* Count bits set in uint32_t */
+static int bits_set(uint32_t n) {
+ n = n - ((n >> 1) & 0x55555555);
+ n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
+ n = (n + (n >> 4)) & 0x0f0f0f0f;
+ n = n + (n >> 8);
+ n = n + (n >> 16);
+ return n & 0x0000003f;
+}
+
+/* Selector chain bloom instrumentation ouput display. */
+static void print_chain_bloom_details(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ printf("Chain bloom:\t");
+ int total = 0, i;
+ int set[4];
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ set[i] = bits_set(bloom[i]);
+ total += set[i];
+ }
+ printf("bits set:");
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ printf(" %2i", set[i]);
+ }
+ printf(" (total:%4i of %i) saturation: %3i%%\n", total,
+ (32 * CSS_BLOOM_SIZE),
+ (100 * total) / (32 * CSS_BLOOM_SIZE));
+}
+#endif
+
/**
* Insert a selector into a hash chain
*
@@ -588,6 +837,11 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
if (head->sel == NULL) {
head->sel = selector;
head->next = NULL;
+ _chain_bloom_generate(selector, head->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(head->sel_chain_bloom);
+#endif
} else {
hash_entry *search = head;
hash_entry *prev = NULL;
@@ -612,13 +866,19 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
search = search->next;
} while (search != NULL);
+ entry->sel = selector;
+ _chain_bloom_generate(selector, entry->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(entry->sel_chain_bloom);
+#endif
+
if (prev == NULL) {
- entry->sel = head->sel;
- entry->next = head->next;
- head->sel = selector;
- head->next = entry;
+ hash_entry temp = *entry;
+ *entry = *head;
+ temp.next = entry;
+ *head = temp;
} else {
- entry->sel = selector;
entry->next = prev->next;
prev->next = entry;
}
@@ -685,7 +945,9 @@ css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_elements(const css_selector **current,
+css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -693,14 +955,29 @@ css_error _iterate_elements(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name;
- name = head->sel->data.qname.name;
+ name = req->qname.name;
+ head = head->next;
+
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ lerror = lwc_string_caseless_isequal(name,
+ head->sel->data.qname.name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- lerror = lwc_string_caseless_isequal(
- name, head->sel->data.qname.name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -720,7 +997,9 @@ css_error _iterate_elements(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_classes(const css_selector **current,
+css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -728,18 +1007,37 @@ css_error _iterate_classes(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _class_name(head->sel);
+ ref = req->class;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _class_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _class_name(head->sel);
+
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -759,7 +1057,9 @@ css_error _iterate_classes(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_ids(const css_selector **current,
+css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -767,18 +1067,37 @@ css_error _iterate_ids(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _id_name(head->sel);
+ ref = req->id;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _id_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _id_name(head->sel);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -798,15 +1117,32 @@ css_error _iterate_ids(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_universal(const css_selector **current,
+css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
+ head = head->next;
- if (head->next == NULL)
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ head = head->next;
+ }
+ }
+
+ if (head == NULL)
head = &empty_slot;
- else
- head = head->next;
(*next) = (const css_selector **) head;
diff --git a/src/select/hash.h b/src/select/hash.h
index 06c27a9..2217cbd 100644
--- a/src/select/hash.h
+++ b/src/select/hash.h
@@ -10,6 +10,7 @@
#include <libwapcaplet/libwapcaplet.h>
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/functypes.h>
@@ -18,7 +19,16 @@ struct css_selector;
typedef struct css_selector_hash css_selector_hash;
+struct css_hash_selection_requirments {
+ css_qname qname; /* Element name, or universal '*' */
+ lwc_string *class; /* Name of class, or NULL */
+ lwc_string *id; /* Name of id, or NULL */
+ uint64_t media; /* Media type(s) we're selecting for */
+ const css_bloom *node_bloom; /* Node's bloom filter */
+};
+
typedef css_error (*css_selector_hash_iterator)(
+ const struct css_hash_selection_requirments *req,
const struct css_selector **current,
const struct css_selector ***next);
@@ -32,18 +42,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
const struct css_selector *selector);
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
diff --git a/src/select/select.c b/src/select/select.c
index 2a56dec..cfafe32 100644
--- a/src/select/select.c
+++ b/src/select/select.c
@@ -355,6 +355,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
*
* \param ctx Selection context to use
* \param node Node to select style for
+ * \param bloom Node's bloom filter filled with ancestor tag,id,class
* \param media Currently active media types
* \param inline_style Corresponding inline style for node, or NULL
* \param handler Dispatch table of handler functions
@@ -372,6 +373,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
* update the fully computed style for a node when layout changes.
*/
css_error css_select_style(css_select_ctx *ctx, void *node,
+ const css_bloom bloom[CSS_BLOOM_SIZE],
uint64_t media, const css_stylesheet *inline_style,
css_select_handler *handler, void *pw,
css_select_results **result)
@@ -394,6 +396,7 @@ css_error css_select_style(css_select_ctx *ctx, void *node,
state.pw = pw;
state.next_reject = state.reject_cache +
(N_ELEMENTS(state.reject_cache) - 1);
+ state.bloom = bloom;
/* Allocate the result set */
state.results = ctx->alloc(NULL, sizeof(css_select_results), ctx->pw);
@@ -1331,31 +1334,6 @@ static const css_selector *_selector_next(const css_selector **node,
return ret;
}
-static bool _rule_good_for_element_name(const css_selector *selector,
- css_select_rule_source *src, css_select_state *state)
-{
- /* If source of rule is element or universal hash, we know the
- * element name is a match. If it comes from the class or id hash,
- * we have to test for a match */
- if (src->source == CSS_SELECT_RULE_SRC_ID ||
- src->source == CSS_SELECT_RULE_SRC_CLASS) {
- if (lwc_string_length(selector->data.qname.name) != 1 ||
- lwc_string_data(
- selector->data.qname.name)[0] != '*') {
- bool match;
- if (lwc_string_caseless_isequal(
- selector->data.qname.name,
- state->element.name,
- &match) == lwc_error_ok &&
- match == false) {
- return false;
- }
- }
- }
-
- return true;
-}
-
css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_stylesheet *sheet, css_select_state *state)
{
@@ -1371,11 +1349,17 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_selector **univ_selectors = &empty_selector;
css_selector_hash_iterator univ_iterator;
css_select_rule_source src = { CSS_SELECT_RULE_SRC_ELEMENT, 0 };
+ struct css_hash_selection_requirments req;
css_error error;
+ /* Set up general selector chain requirments */
+ req.media = state->media;
+ req.node_bloom = state->bloom;
+
/* Find hash chain that applies to current node */
+ req.qname = state->element;
error = css__selector_hash_find(sheet->selectors,
- &state->element, &node_iterator,
+ &req, &node_iterator,
&node_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1391,8 +1375,9 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
}
for (i = 0; i < n_classes; i++) {
+ req.class = state->classes[i];
error = css__selector_hash_find_by_class(
- sheet->selectors, state->classes[i],
+ sheet->selectors, &req,
&class_iterator, &class_selectors[i]);
if (error != CSS_OK)
goto cleanup;
@@ -1401,14 +1386,15 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
if (state->id != NULL) {
/* Find hash chain for node ID */
+ req.id = state->id;
error = css__selector_hash_find_by_id(sheet->selectors,
- state->id, &id_iterator, &id_selectors);
+ &req, &id_iterator, &id_selectors);
if (error != CSS_OK)
goto cleanup;
}
/* Find hash chain for universal selector */
- error = css__selector_hash_find_universal(sheet->selectors,
+ error = css__selector_hash_find_universal(sheet->selectors, &req,
&univ_iterator, &univ_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1431,46 +1417,32 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
* selector here */
assert(selector != NULL);
- /* No bytecode if rule body is empty or wholly invalid --
- * Only interested in rules with bytecode */
- if (((css_rule_selector *) selector->rule)->style != NULL) {
- /* Ignore any selectors contained in rules which are a
- * child of an @media block that doesn't match the
- * current media requirements. */
- if (_rule_applies_to_media(selector->rule,
- state->media)) {
- if (_rule_good_for_element_name(selector, &src,
- state)) {
- error = match_selector_chain(
- ctx, selector,
- state);
- if (error != CSS_OK)
- goto cleanup;
- }
- }
- }
+ /* Match and handle the selector chain */
+ error = match_selector_chain(ctx, selector, state);
+ if (error != CSS_OK)
+ goto cleanup;
/* Advance to next selector in whichever chain we extracted
* the processed selector from. */
switch (src.source) {
case CSS_SELECT_RULE_SRC_ELEMENT:
- error = node_iterator(
- node_selectors, &node_selectors);
+ error = node_iterator(&req, node_selectors,
+ &node_selectors);
break;
case CSS_SELECT_RULE_SRC_ID:
- error = id_iterator(
- id_selectors, &id_selectors);
+ error = id_iterator(&req, id_selectors,
+ &id_selectors);
break;
case CSS_SELECT_RULE_SRC_UNIVERSAL:
- error = univ_iterator(
- univ_selectors, &univ_selectors);
+ error = univ_iterator(&req, univ_selectors,
+ &univ_selectors);
break;
case CSS_SELECT_RULE_SRC_CLASS:
- error = class_iterator(
- class_selectors[src.class],
+ req.class = state->classes[src.class];
+ error = class_iterator(&req, class_selectors[src.class],
&class_selectors[src.class]);
break;
}
diff --git a/src/select/select.h b/src/select/select.h
index ee8e42a..43c29d2 100644
--- a/src/select/select.h
+++ b/src/select/select.h
@@ -58,6 +58,8 @@ typedef struct css_select_state {
reject_item reject_cache[128]; /* Reject cache (filled from end) */
reject_item *next_reject; /* Next free slot in reject cache */
+ const css_bloom *bloom; /* Bloom filter */
+
prop_state props[CSS_N_PROPERTIES][CSS_PSEUDO_ELEMENT_COUNT];
} css_select_state;
commitdiff http://git.netsurf-browser.org/libcss.git/commit/?id=d2460b3a2f2690813abd...
commit d2460b3a2f2690813abdf3b350be9dc5ebf2fe18
Author: Michael Drake <tlsa(a)netsurf-browser.org>
Commit: Michael Drake <tlsa(a)netsurf-browser.org>
Bloom filter implementation for selection optimisation.
diff --git a/include/libcss/bloom.h b/include/libcss/bloom.h
new file mode 100644
index 0000000..8c1da3f
--- /dev/null
+++ b/include/libcss/bloom.h
@@ -0,0 +1,205 @@
+/*
+ * This file is part of LibCSS.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2013 Michael Drake <tlsa(a)netsurf-browser.org>
+ */
+
+/** \file
+ * Bloom filter for CSS style selection optimisation.
+ *
+ * Attempting to match CSS rules by querying the client about DOM nodes via
+ * the selection callbacks is slow. To avoid this, clients may pass a node
+ * bloom filter to css_get_style. This bloom filter has bits set according
+ * to the node's ancestor element names, class names and id names.
+ *
+ * Generate the bloom filter by adding calling css_bloom_add_hash() on each
+ * ancestor element name, class name and id name for the node.
+ *
+ * Use the insesnsitive lwc_string:
+ *
+ * lwc_string_hash_value(str->insensitive)
+ */
+
+#ifndef libcss_bloom_h_
+#define libcss_bloom_h_
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include <stdint.h>
+
+/* Size of bloom filter as multiple of 32 bits.
+ * Has to be 4, 8, or 16.
+ * Larger increases optimisation of style selection engine but uses more memory.
+ */
+#define CSS_BLOOM_SIZE 4
+
+
+
+/* Check valid bloom filter size */
+#if !(CSS_BLOOM_SIZE == 4 || CSS_BLOOM_SIZE == 8 || CSS_BLOOM_SIZE == 16)
+# error Unsupported bloom filter size. Size must be {4|8|16}.
+#endif
+
+/* Setup index bit mask */
+#define INDEX_BITS_N (CSS_BLOOM_SIZE - 1)
+
+
+
+/* type for bloom */
+typedef uint32_t css_bloom;
+
+
+/**
+ * Add a hash value to the bloom filter.
+ *
+ * \param bloom bloom filter to insert into
+ * \param hash libwapcaplet hash value to insert
+ */
+static inline void css_bloom_add_hash(css_bloom bloom[CSS_BLOOM_SIZE],
+ lwc_hash hash)
+{
+ unsigned int bit = hash & 0x1f; /* Top 5 bits */
+ unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
+
+ bloom[index] |= (1 << bit);
+}
+
+
+/**
+ * Test whether bloom filter contains given hash value.
+ *
+ * \param bloom bloom filter to check inside
+ * \param hash libwapcaplet hash value to look for
+ * \return true hash value is already set in bloom
+ */
+static inline bool css_bloom_has_hash(const css_bloom bloom[CSS_BLOOM_SIZE],
+ lwc_hash hash)
+{
+ unsigned int bit = hash & 0x1f; /* Top 5 bits */
+ unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
+
+ return (bloom[index] & (1 << bit));
+}
+
+
+/**
+ * Test whether bloom 'a' is a subset of bloom 'b'.
+ *
+ * \param a potential subset bloom to test
+ * \param b superset bloom
+ * \return true iff 'a' is subset of 'b'
+ */
+static inline bool css_bloom_in_bloom(const css_bloom a[CSS_BLOOM_SIZE],
+ const css_bloom b[CSS_BLOOM_SIZE])
+{
+ if ((a[0] & b[0]) != a[0])
+ return false;
+ if ((a[1] & b[1]) != a[1])
+ return false;
+ if ((a[2] & b[2]) != a[2])
+ return false;
+ if ((a[3] & b[3]) != a[3])
+ return false;
+#if (CSS_BLOOM_SIZE > 4)
+ if ((a[4] & b[4]) != a[4])
+ return false;
+ if ((a[5] & b[5]) != a[5])
+ return false;
+ if ((a[6] & b[6]) != a[6])
+ return false;
+ if ((a[7] & b[7]) != a[7])
+ return false;
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ if ((a[8] & b[8]) != a[8])
+ return false;
+ if ((a[9] & b[9]) != a[9])
+ return false;
+ if ((a[10] & b[10]) != a[10])
+ return false;
+ if ((a[11] & b[11]) != a[11])
+ return false;
+ if ((a[12] & b[12]) != a[12])
+ return false;
+ if ((a[13] & b[13]) != a[13])
+ return false;
+ if ((a[14] & b[14]) != a[14])
+ return false;
+ if ((a[15] & b[15]) != a[15])
+ return false;
+#endif
+ return true;
+}
+
+
+/**
+ * Merge bloom 'a' into bloom 'b'.
+ *
+ * \param a bloom to insert
+ * \param b target bloom
+ */
+static inline void css_bloom_merge(const css_bloom a[CSS_BLOOM_SIZE],
+ css_bloom b[CSS_BLOOM_SIZE])
+{
+ b[0] |= a[0];
+ b[1] |= a[1];
+ b[2] |= a[2];
+ b[3] |= a[3];
+#if (CSS_BLOOM_SIZE > 4)
+ b[4] |= a[4];
+ b[5] |= a[5];
+ b[6] |= a[6];
+ b[7] |= a[7];
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ b[8] |= a[8];
+ b[9] |= a[9];
+ b[10] |= a[10];
+ b[11] |= a[11];
+ b[12] |= a[12];
+ b[13] |= a[13];
+ b[14] |= a[14];
+ b[15] |= a[15];
+#endif
+}
+
+
+/**
+ * Initialise a bloom filter to 0
+ *
+ * \param bloom bloom filter to initialise
+ */
+static inline void css_bloom_init(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ bloom[0] = 0;
+ bloom[1] = 0;
+ bloom[2] = 0;
+ bloom[3] = 0;
+#if (CSS_BLOOM_SIZE > 4)
+ bloom[4] = 0;
+ bloom[5] = 0;
+ bloom[6] = 0;
+ bloom[7] = 0;
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ bloom[8] = 0;
+ bloom[9] = 0;
+ bloom[10] = 0;
+ bloom[11] = 0;
+ bloom[12] = 0;
+ bloom[13] = 0;
+ bloom[14] = 0;
+ bloom[15] = 0;
+#endif
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
-----------------------------------------------------------------------
Summary of changes:
Makefile | 1 +
include/libcss/bloom.h | 205 ++++++++++++
include/libcss/libcss.h | 1 +
include/libcss/select.h | 2 +
src/select/hash.c | 466 +++++++++++++++++++++++----
src/select/hash.h | 17 +-
src/select/select.c | 82 ++----
src/select/select.h | 2 +
test/INDEX | 1 +
test/Makefile | 2 +-
test/select-auto.c | 8 +-
test/{select-auto.c => select-bloom-auto.c} | 53 +++-
12 files changed, 714 insertions(+), 126 deletions(-)
create mode 100644 include/libcss/bloom.h
copy test/{select-auto.c => select-bloom-auto.c} (96%)
diff --git a/Makefile b/Makefile
index 68ec9ba..d9a2b9b 100644
--- a/Makefile
+++ b/Makefile
@@ -46,6 +46,7 @@ include $(NSBUILD)/Makefile.top
# Extra installation rules
I := /include/libcss
+INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/bloom.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/computed.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/errors.h
INSTALL_ITEMS := $(INSTALL_ITEMS) $(I):include/libcss/font_face.h
diff --git a/include/libcss/bloom.h b/include/libcss/bloom.h
new file mode 100644
index 0000000..8c1da3f
--- /dev/null
+++ b/include/libcss/bloom.h
@@ -0,0 +1,205 @@
+/*
+ * This file is part of LibCSS.
+ * Licensed under the MIT License,
+ * http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2013 Michael Drake <tlsa(a)netsurf-browser.org>
+ */
+
+/** \file
+ * Bloom filter for CSS style selection optimisation.
+ *
+ * Attempting to match CSS rules by querying the client about DOM nodes via
+ * the selection callbacks is slow. To avoid this, clients may pass a node
+ * bloom filter to css_get_style. This bloom filter has bits set according
+ * to the node's ancestor element names, class names and id names.
+ *
+ * Generate the bloom filter by adding calling css_bloom_add_hash() on each
+ * ancestor element name, class name and id name for the node.
+ *
+ * Use the insesnsitive lwc_string:
+ *
+ * lwc_string_hash_value(str->insensitive)
+ */
+
+#ifndef libcss_bloom_h_
+#define libcss_bloom_h_
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include <stdint.h>
+
+/* Size of bloom filter as multiple of 32 bits.
+ * Has to be 4, 8, or 16.
+ * Larger increases optimisation of style selection engine but uses more memory.
+ */
+#define CSS_BLOOM_SIZE 4
+
+
+
+/* Check valid bloom filter size */
+#if !(CSS_BLOOM_SIZE == 4 || CSS_BLOOM_SIZE == 8 || CSS_BLOOM_SIZE == 16)
+# error Unsupported bloom filter size. Size must be {4|8|16}.
+#endif
+
+/* Setup index bit mask */
+#define INDEX_BITS_N (CSS_BLOOM_SIZE - 1)
+
+
+
+/* type for bloom */
+typedef uint32_t css_bloom;
+
+
+/**
+ * Add a hash value to the bloom filter.
+ *
+ * \param bloom bloom filter to insert into
+ * \param hash libwapcaplet hash value to insert
+ */
+static inline void css_bloom_add_hash(css_bloom bloom[CSS_BLOOM_SIZE],
+ lwc_hash hash)
+{
+ unsigned int bit = hash & 0x1f; /* Top 5 bits */
+ unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
+
+ bloom[index] |= (1 << bit);
+}
+
+
+/**
+ * Test whether bloom filter contains given hash value.
+ *
+ * \param bloom bloom filter to check inside
+ * \param hash libwapcaplet hash value to look for
+ * \return true hash value is already set in bloom
+ */
+static inline bool css_bloom_has_hash(const css_bloom bloom[CSS_BLOOM_SIZE],
+ lwc_hash hash)
+{
+ unsigned int bit = hash & 0x1f; /* Top 5 bits */
+ unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
+
+ return (bloom[index] & (1 << bit));
+}
+
+
+/**
+ * Test whether bloom 'a' is a subset of bloom 'b'.
+ *
+ * \param a potential subset bloom to test
+ * \param b superset bloom
+ * \return true iff 'a' is subset of 'b'
+ */
+static inline bool css_bloom_in_bloom(const css_bloom a[CSS_BLOOM_SIZE],
+ const css_bloom b[CSS_BLOOM_SIZE])
+{
+ if ((a[0] & b[0]) != a[0])
+ return false;
+ if ((a[1] & b[1]) != a[1])
+ return false;
+ if ((a[2] & b[2]) != a[2])
+ return false;
+ if ((a[3] & b[3]) != a[3])
+ return false;
+#if (CSS_BLOOM_SIZE > 4)
+ if ((a[4] & b[4]) != a[4])
+ return false;
+ if ((a[5] & b[5]) != a[5])
+ return false;
+ if ((a[6] & b[6]) != a[6])
+ return false;
+ if ((a[7] & b[7]) != a[7])
+ return false;
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ if ((a[8] & b[8]) != a[8])
+ return false;
+ if ((a[9] & b[9]) != a[9])
+ return false;
+ if ((a[10] & b[10]) != a[10])
+ return false;
+ if ((a[11] & b[11]) != a[11])
+ return false;
+ if ((a[12] & b[12]) != a[12])
+ return false;
+ if ((a[13] & b[13]) != a[13])
+ return false;
+ if ((a[14] & b[14]) != a[14])
+ return false;
+ if ((a[15] & b[15]) != a[15])
+ return false;
+#endif
+ return true;
+}
+
+
+/**
+ * Merge bloom 'a' into bloom 'b'.
+ *
+ * \param a bloom to insert
+ * \param b target bloom
+ */
+static inline void css_bloom_merge(const css_bloom a[CSS_BLOOM_SIZE],
+ css_bloom b[CSS_BLOOM_SIZE])
+{
+ b[0] |= a[0];
+ b[1] |= a[1];
+ b[2] |= a[2];
+ b[3] |= a[3];
+#if (CSS_BLOOM_SIZE > 4)
+ b[4] |= a[4];
+ b[5] |= a[5];
+ b[6] |= a[6];
+ b[7] |= a[7];
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ b[8] |= a[8];
+ b[9] |= a[9];
+ b[10] |= a[10];
+ b[11] |= a[11];
+ b[12] |= a[12];
+ b[13] |= a[13];
+ b[14] |= a[14];
+ b[15] |= a[15];
+#endif
+}
+
+
+/**
+ * Initialise a bloom filter to 0
+ *
+ * \param bloom bloom filter to initialise
+ */
+static inline void css_bloom_init(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ bloom[0] = 0;
+ bloom[1] = 0;
+ bloom[2] = 0;
+ bloom[3] = 0;
+#if (CSS_BLOOM_SIZE > 4)
+ bloom[4] = 0;
+ bloom[5] = 0;
+ bloom[6] = 0;
+ bloom[7] = 0;
+#endif
+#if (CSS_BLOOM_SIZE > 8)
+ bloom[8] = 0;
+ bloom[9] = 0;
+ bloom[10] = 0;
+ bloom[11] = 0;
+ bloom[12] = 0;
+ bloom[13] = 0;
+ bloom[14] = 0;
+ bloom[15] = 0;
+#endif
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
diff --git a/include/libcss/libcss.h b/include/libcss/libcss.h
index 89e83b5..bde2707 100644
--- a/include/libcss/libcss.h
+++ b/include/libcss/libcss.h
@@ -15,6 +15,7 @@ extern "C"
#include <libwapcaplet/libwapcaplet.h>
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/types.h>
#include <libcss/functypes.h>
diff --git a/include/libcss/select.h b/include/libcss/select.h
index 4a95752..9ab2550 100644
--- a/include/libcss/select.h
+++ b/include/libcss/select.h
@@ -13,6 +13,7 @@ extern "C"
{
#endif
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/functypes.h>
#include <libcss/hint.h>
@@ -162,6 +163,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
const css_stylesheet **sheet);
css_error css_select_style(css_select_ctx *ctx, void *node,
+ const css_bloom bloom[CSS_BLOOM_SIZE],
uint64_t media, const css_stylesheet *inline_style,
css_select_handler *handler, void *pw,
css_select_results **result);
diff --git a/src/select/hash.c b/src/select/hash.c
index 37492c1..5420d6d 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -12,8 +12,11 @@
#include "select/hash.h"
#include "utils/utils.h"
+#undef PRINT_CHAIN_BLOOM_DETAILS
+
typedef struct hash_entry {
const css_selector *sel;
+ css_bloom sel_chain_bloom[CSS_BLOOM_SIZE];
struct hash_entry *next;
} hash_entry;
@@ -41,7 +44,7 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash_name(lwc_string *name);
+static inline uint32_t _hash_name(const lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
@@ -49,15 +52,88 @@ static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
static css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
const css_selector *selector);
-static css_error _iterate_elements(const css_selector **current,
+static css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_classes(const css_selector **current,
+static css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_ids(const css_selector **current,
+static css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_universal(const css_selector **current,
+static css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
+
+/* No bytecode if rule body is empty or wholly invalid --
+ * Only interested in rules with bytecode */
+#define RULE_HAS_BYTECODE(r) \
+ (((css_rule_selector *)(r->sel->rule))->style != NULL)
+
+
+/**
+ * Test first selector on selector chain for having matching element name.
+ *
+ * If source of rule is element or universal hash, we know the
+ * element name is a match. If it comes from the class or id hash,
+ * we have to test for a match.
+ *
+ * \param selector selector chain head to test
+ * \param qname element name to look for
+ * \return true iff chain head doesn't fail to match element name
+ */
+static inline bool _chain_good_for_element_name(const css_selector *selector,
+ const css_qname *qname)
+{
+ if (lwc_string_length(selector->data.qname.name) != 1 ||
+ lwc_string_data(selector->data.qname.name)[0] != '*') {
+ bool match;
+ if (lwc_string_caseless_isequal(
+ selector->data.qname.name, qname->name,
+ &match) == lwc_error_ok && match == false) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Test whether the rule applies for current media.
+ *
+ * \param rule Rule to test
+ * \meaid media Current media type(s)
+ * \return true iff chain's rule applies for media
+ */
+static inline bool _rule_good_for_media(const css_rule *rule, uint64_t media)
+{
+ bool applies = true;
+ const css_rule *ancestor = rule;
+
+ while (ancestor != NULL) {
+ const css_rule_media *m = (const css_rule_media *) ancestor;
+
+ if (ancestor->type == CSS_RULE_MEDIA &&
+ (m->media & media) == 0) {
+ applies = false;
+ break;
+ }
+
+ if (ancestor->ptype != CSS_RULE_PARENT_STYLESHEET)
+ ancestor = ancestor->parent;
+ else
+ ancestor = NULL;
+ }
+
+ return applies;
+}
+
+
/**
* Create a hash
*
@@ -288,19 +364,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || qname == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->elements.n_slots - 1;
- index = _hash_name(qname->name) & mask;
+ index = _hash_name(req->qname.name) & mask;
head = &hash->elements.slots[index];
@@ -311,13 +387,22 @@ css_error css__selector_hash_find(css_selector_hash *hash,
bool match = false;
lerror = lwc_string_caseless_isequal(
- qname->name, head->sel->data.qname.name,
+ req->qname.name,
+ head->sel->data.qname.name,
&match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
head = head->next;
}
@@ -344,19 +429,20 @@ css_error css__selector_hash_find(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->class == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->classes.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->class) & mask;
head = &hash->classes.slots[index];
@@ -370,12 +456,24 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
n = _class_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->class, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -403,19 +501,20 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->id == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->ids.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->id) & mask;
head = &hash->ids.slots[index];
@@ -429,12 +528,24 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
n = _id_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->id, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -461,14 +572,39 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
- if (hash == NULL || iterator == NULL || matched == NULL)
+ hash_entry *head;
+
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
+ head = &hash->universal;
+
+ if (head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+
+ head = head->next;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+ }
+
(*iterator) = _iterate_universal;
- (*matched) = (const css_selector **) &hash->universal;
+ (*matched) = (const css_selector **) head;
return CSS_OK;
}
@@ -503,7 +639,7 @@ css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
* \param name Name to hash
* \return hash value
*/
-uint32_t _hash_name(lwc_string *name)
+uint32_t _hash_name(const lwc_string *name)
{
uint32_t z = 0x811c9dc5;
const char *data = lwc_string_data(name);
@@ -573,6 +709,119 @@ lwc_string *_id_name(const css_selector *selector)
return name;
}
+
+/**
+ * Add a selector detail to the bloom filter, if the detail is relevant.
+ *
+ * \param d Selector detail to consider and add if relevant
+ * \param bloom Bloom filter to add to.
+ */
+static inline void _chain_bloom_add_detail(
+ const css_selector_detail *d,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ lwc_string *add = NULL; /* String to add to bloom */
+
+ switch (d->type) {
+ case CSS_SELECTOR_ELEMENT:
+ /* Don't add universal element selector to bloom */
+ if (lwc_string_length(d->qname.name) == 1 &&
+ lwc_string_data(d->qname.name)[0] == '*') {
+ return;
+ }
+
+ /* TODO: Remain case sensitive for XML */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ case CSS_SELECTOR_CLASS:
+ case CSS_SELECTOR_ID:
+ /* TODO: Remain case sensitive in standards mode */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ default:
+ return;
+ }
+
+ /* Don't really care if intern for caseless string failed, if we're
+ * out of memory, something else will panic. Everything still works
+ * if the string isn't added the the rule bloom. Just less optimally.
+ */
+ if (add != NULL) {
+ css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ }
+
+ return;
+}
+
+
+/**
+ * Generate a selector chain's bloom filter
+ *
+ * \param s Selector at head of selector chain
+ * \param bloom Bloom filter to generate.
+ */
+static void _chain_bloom_generate(const css_selector *s,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ css_bloom_init(bloom);
+
+ /* Work back through selector chain... */
+ do {
+ /* ...looking for Ancestor/Parent combinators */
+ if (s->data.comb == CSS_COMBINATOR_ANCESTOR ||
+ s->data.comb == CSS_COMBINATOR_PARENT) {
+ const css_selector_detail *d = &s->combinator->data;
+ while (d != NULL) {
+ if (d->negate == 0) {
+ _chain_bloom_add_detail(d, bloom);
+ }
+ d = (d->next != 0) ? d + 1 : NULL;
+ }
+ }
+
+ s = s->combinator;
+ } while (s != NULL);
+}
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+/* Count bits set in uint32_t */
+static int bits_set(uint32_t n) {
+ n = n - ((n >> 1) & 0x55555555);
+ n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
+ n = (n + (n >> 4)) & 0x0f0f0f0f;
+ n = n + (n >> 8);
+ n = n + (n >> 16);
+ return n & 0x0000003f;
+}
+
+/* Selector chain bloom instrumentation ouput display. */
+static void print_chain_bloom_details(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ printf("Chain bloom:\t");
+ int total = 0, i;
+ int set[4];
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ set[i] = bits_set(bloom[i]);
+ total += set[i];
+ }
+ printf("bits set:");
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ printf(" %2i", set[i]);
+ }
+ printf(" (total:%4i of %i) saturation: %3i%%\n", total,
+ (32 * CSS_BLOOM_SIZE),
+ (100 * total) / (32 * CSS_BLOOM_SIZE));
+}
+#endif
+
/**
* Insert a selector into a hash chain
*
@@ -588,6 +837,11 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
if (head->sel == NULL) {
head->sel = selector;
head->next = NULL;
+ _chain_bloom_generate(selector, head->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(head->sel_chain_bloom);
+#endif
} else {
hash_entry *search = head;
hash_entry *prev = NULL;
@@ -612,13 +866,19 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
search = search->next;
} while (search != NULL);
+ entry->sel = selector;
+ _chain_bloom_generate(selector, entry->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(entry->sel_chain_bloom);
+#endif
+
if (prev == NULL) {
- entry->sel = head->sel;
- entry->next = head->next;
- head->sel = selector;
- head->next = entry;
+ hash_entry temp = *entry;
+ *entry = *head;
+ temp.next = entry;
+ *head = temp;
} else {
- entry->sel = selector;
entry->next = prev->next;
prev->next = entry;
}
@@ -685,7 +945,9 @@ css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_elements(const css_selector **current,
+css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -693,14 +955,29 @@ css_error _iterate_elements(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name;
- name = head->sel->data.qname.name;
+ name = req->qname.name;
+ head = head->next;
+
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ lerror = lwc_string_caseless_isequal(name,
+ head->sel->data.qname.name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- lerror = lwc_string_caseless_isequal(
- name, head->sel->data.qname.name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -720,7 +997,9 @@ css_error _iterate_elements(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_classes(const css_selector **current,
+css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -728,18 +1007,37 @@ css_error _iterate_classes(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _class_name(head->sel);
+ ref = req->class;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _class_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _class_name(head->sel);
+
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -759,7 +1057,9 @@ css_error _iterate_classes(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_ids(const css_selector **current,
+css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -767,18 +1067,37 @@ css_error _iterate_ids(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _id_name(head->sel);
+ ref = req->id;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _id_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _id_name(head->sel);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -798,15 +1117,32 @@ css_error _iterate_ids(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_universal(const css_selector **current,
+css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
+ head = head->next;
- if (head->next == NULL)
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ head = head->next;
+ }
+ }
+
+ if (head == NULL)
head = &empty_slot;
- else
- head = head->next;
(*next) = (const css_selector **) head;
diff --git a/src/select/hash.h b/src/select/hash.h
index 06c27a9..2217cbd 100644
--- a/src/select/hash.h
+++ b/src/select/hash.h
@@ -10,6 +10,7 @@
#include <libwapcaplet/libwapcaplet.h>
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/functypes.h>
@@ -18,7 +19,16 @@ struct css_selector;
typedef struct css_selector_hash css_selector_hash;
+struct css_hash_selection_requirments {
+ css_qname qname; /* Element name, or universal '*' */
+ lwc_string *class; /* Name of class, or NULL */
+ lwc_string *id; /* Name of id, or NULL */
+ uint64_t media; /* Media type(s) we're selecting for */
+ const css_bloom *node_bloom; /* Node's bloom filter */
+};
+
typedef css_error (*css_selector_hash_iterator)(
+ const struct css_hash_selection_requirments *req,
const struct css_selector **current,
const struct css_selector ***next);
@@ -32,18 +42,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
const struct css_selector *selector);
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
diff --git a/src/select/select.c b/src/select/select.c
index 2a56dec..cfafe32 100644
--- a/src/select/select.c
+++ b/src/select/select.c
@@ -355,6 +355,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
*
* \param ctx Selection context to use
* \param node Node to select style for
+ * \param bloom Node's bloom filter filled with ancestor tag,id,class
* \param media Currently active media types
* \param inline_style Corresponding inline style for node, or NULL
* \param handler Dispatch table of handler functions
@@ -372,6 +373,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
* update the fully computed style for a node when layout changes.
*/
css_error css_select_style(css_select_ctx *ctx, void *node,
+ const css_bloom bloom[CSS_BLOOM_SIZE],
uint64_t media, const css_stylesheet *inline_style,
css_select_handler *handler, void *pw,
css_select_results **result)
@@ -394,6 +396,7 @@ css_error css_select_style(css_select_ctx *ctx, void *node,
state.pw = pw;
state.next_reject = state.reject_cache +
(N_ELEMENTS(state.reject_cache) - 1);
+ state.bloom = bloom;
/* Allocate the result set */
state.results = ctx->alloc(NULL, sizeof(css_select_results), ctx->pw);
@@ -1331,31 +1334,6 @@ static const css_selector *_selector_next(const css_selector **node,
return ret;
}
-static bool _rule_good_for_element_name(const css_selector *selector,
- css_select_rule_source *src, css_select_state *state)
-{
- /* If source of rule is element or universal hash, we know the
- * element name is a match. If it comes from the class or id hash,
- * we have to test for a match */
- if (src->source == CSS_SELECT_RULE_SRC_ID ||
- src->source == CSS_SELECT_RULE_SRC_CLASS) {
- if (lwc_string_length(selector->data.qname.name) != 1 ||
- lwc_string_data(
- selector->data.qname.name)[0] != '*') {
- bool match;
- if (lwc_string_caseless_isequal(
- selector->data.qname.name,
- state->element.name,
- &match) == lwc_error_ok &&
- match == false) {
- return false;
- }
- }
- }
-
- return true;
-}
-
css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_stylesheet *sheet, css_select_state *state)
{
@@ -1371,11 +1349,17 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_selector **univ_selectors = &empty_selector;
css_selector_hash_iterator univ_iterator;
css_select_rule_source src = { CSS_SELECT_RULE_SRC_ELEMENT, 0 };
+ struct css_hash_selection_requirments req;
css_error error;
+ /* Set up general selector chain requirments */
+ req.media = state->media;
+ req.node_bloom = state->bloom;
+
/* Find hash chain that applies to current node */
+ req.qname = state->element;
error = css__selector_hash_find(sheet->selectors,
- &state->element, &node_iterator,
+ &req, &node_iterator,
&node_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1391,8 +1375,9 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
}
for (i = 0; i < n_classes; i++) {
+ req.class = state->classes[i];
error = css__selector_hash_find_by_class(
- sheet->selectors, state->classes[i],
+ sheet->selectors, &req,
&class_iterator, &class_selectors[i]);
if (error != CSS_OK)
goto cleanup;
@@ -1401,14 +1386,15 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
if (state->id != NULL) {
/* Find hash chain for node ID */
+ req.id = state->id;
error = css__selector_hash_find_by_id(sheet->selectors,
- state->id, &id_iterator, &id_selectors);
+ &req, &id_iterator, &id_selectors);
if (error != CSS_OK)
goto cleanup;
}
/* Find hash chain for universal selector */
- error = css__selector_hash_find_universal(sheet->selectors,
+ error = css__selector_hash_find_universal(sheet->selectors, &req,
&univ_iterator, &univ_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1431,46 +1417,32 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
* selector here */
assert(selector != NULL);
- /* No bytecode if rule body is empty or wholly invalid --
- * Only interested in rules with bytecode */
- if (((css_rule_selector *) selector->rule)->style != NULL) {
- /* Ignore any selectors contained in rules which are a
- * child of an @media block that doesn't match the
- * current media requirements. */
- if (_rule_applies_to_media(selector->rule,
- state->media)) {
- if (_rule_good_for_element_name(selector, &src,
- state)) {
- error = match_selector_chain(
- ctx, selector,
- state);
- if (error != CSS_OK)
- goto cleanup;
- }
- }
- }
+ /* Match and handle the selector chain */
+ error = match_selector_chain(ctx, selector, state);
+ if (error != CSS_OK)
+ goto cleanup;
/* Advance to next selector in whichever chain we extracted
* the processed selector from. */
switch (src.source) {
case CSS_SELECT_RULE_SRC_ELEMENT:
- error = node_iterator(
- node_selectors, &node_selectors);
+ error = node_iterator(&req, node_selectors,
+ &node_selectors);
break;
case CSS_SELECT_RULE_SRC_ID:
- error = id_iterator(
- id_selectors, &id_selectors);
+ error = id_iterator(&req, id_selectors,
+ &id_selectors);
break;
case CSS_SELECT_RULE_SRC_UNIVERSAL:
- error = univ_iterator(
- univ_selectors, &univ_selectors);
+ error = univ_iterator(&req, univ_selectors,
+ &univ_selectors);
break;
case CSS_SELECT_RULE_SRC_CLASS:
- error = class_iterator(
- class_selectors[src.class],
+ req.class = state->classes[src.class];
+ error = class_iterator(&req, class_selectors[src.class],
&class_selectors[src.class]);
break;
}
diff --git a/src/select/select.h b/src/select/select.h
index ee8e42a..43c29d2 100644
--- a/src/select/select.h
+++ b/src/select/select.h
@@ -58,6 +58,8 @@ typedef struct css_select_state {
reject_item reject_cache[128]; /* Reject cache (filled from end) */
reject_item *next_reject; /* Next free slot in reject cache */
+ const css_bloom *bloom; /* Bloom filter */
+
prop_state props[CSS_N_PROPERTIES][CSS_PSEUDO_ELEMENT_COUNT];
} css_select_state;
diff --git a/test/INDEX b/test/INDEX
index b519b1f..1c776c6 100644
--- a/test/INDEX
+++ b/test/INDEX
@@ -11,6 +11,7 @@ number Conversion of numbers to fixed point number
parse-auto Automated parser tests (bytecode) parse
parse2-auto Automated parser tests (om & invalid) parse2
select-auto Automated selection engine tests select
+sel-bloom-auto Automated selection tests with bloom select
# Regression tests
diff --git a/test/Makefile b/test/Makefile
index c4d7eee..23d4442 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -2,6 +2,6 @@
DIR_TEST_ITEMS := csdetect:csdetect.c css21:css21.c lex:lex.c \
lex-auto:lex-auto.c number:number.c \
parse:parse.c parse-auto:parse-auto.c parse2-auto:parse2-auto.c \
- select-auto:select-auto.c
+ select-auto:select-auto.c sel-bloom-auto:select-bloom-auto.c
include $(NSBUILD)/Makefile.subdir
diff --git a/test/select-auto.c b/test/select-auto.c
index 4b664ab..9c1a52b 100644
--- a/test/select-auto.c
+++ b/test/select-auto.c
@@ -708,6 +708,7 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
char *buf;
size_t buflen;
static int testnum;
+ css_bloom node_bloom[CSS_BLOOM_SIZE];
UNUSED(exp);
@@ -727,7 +728,12 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
testnum++;
- assert(css_select_style(select, ctx->target, ctx->media, NULL,
+ /* Not testing bloom functionality here, just set all bits */
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ node_bloom[i] = ~0;
+ }
+
+ assert(css_select_style(select, ctx->target, node_bloom, ctx->media, NULL,
&select_handler, ctx, &results) == CSS_OK);
assert(results->styles[ctx->pseudo_element] != NULL);
diff --git a/test/select-auto.c b/test/select-bloom-auto.c
similarity index 96%
copy from test/select-auto.c
copy to test/select-bloom-auto.c
index 4b664ab..2d8628d 100644
--- a/test/select-auto.c
+++ b/test/select-bloom-auto.c
@@ -700,6 +700,54 @@ void css__parse_expected(line_ctx *ctx, const char *data, size_t len)
ctx->expused += len;
}
+static void get_bloom_for_target_node(line_ctx *ctx,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ node *n = ctx->target;
+ bool match;
+ uint32_t i;
+
+ css_bloom_init(bloom);
+
+ while (n->parent != NULL) {
+ n = n->parent;
+
+ /* Element name */
+ if (n->name->insensitive == NULL)
+ assert(lwc__intern_caseless_string(n->name) ==
+ lwc_error_ok);
+
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(n->name->insensitive));
+
+ /* Id */
+ for (i = 0; i < n->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ n->attrs[i].name, ctx->attr_id,
+ &match) == lwc_error_ok);
+ if (match == true) {
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(
+ n->attrs[i].value));
+ break;
+ }
+ }
+
+ /* Classes */
+ for (i = 0; i < n->n_attrs; i++) {
+ assert(lwc_string_caseless_isequal(
+ n->attrs[i].name, ctx->attr_class,
+ &match) == lwc_error_ok);
+ if (match == true) {
+ css_bloom_add_hash(bloom,
+ lwc_string_hash_value(
+ n->attrs[i].value));
+ break;
+ }
+ }
+ }
+}
+
void run_test(line_ctx *ctx, const char *exp, size_t explen)
{
css_select_ctx *select;
@@ -708,6 +756,7 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
char *buf;
size_t buflen;
static int testnum;
+ css_bloom node_bloom[CSS_BLOOM_SIZE];
UNUSED(exp);
@@ -727,7 +776,9 @@ void run_test(line_ctx *ctx, const char *exp, size_t explen)
testnum++;
- assert(css_select_style(select, ctx->target, ctx->media, NULL,
+ get_bloom_for_target_node(ctx, node_bloom);
+
+ assert(css_select_style(select, ctx->target, node_bloom, ctx->media, NULL,
&select_handler, ctx, &results) == CSS_OK);
assert(results->styles[ctx->pseudo_element] != NULL);
--
Cascading Style Sheets library
9 years, 1 month
- 1
- 0