Структура данных для поиска подходящих CSS-правил

Question

[Виталий]

В качестве домашнего проекта начал потихоньку делать рендерер страниц на python.
Но вопрос не по языку.

Нужно организовать правильную структуру данных для удобного поиска подходящих правил.

Пример:

css:

a { display: block; font-size: 12pt; }
div p.links a { color: green; display: inline; }

Предположим, что я распарсил этот фрагмент и получил необходимую структуру.

Теперь должно быть возможно сделать такое:

cssTable.get_styles( 'html > div#content > h3 > a' );

Это возвратит: { display: block; font-size: 12pt; }

Если я запрашиваю такой путь:

cssTable.get_styles( 'html > div#content > p.links > a' );

Это должно возвратить совмещенное правило: {display: inline; color: green; font-size: 12pt;}

Есть идеи как правильно организовать такую структуру?

Comments

[Виталий]

Задал этот же вопрос на stackoverflow, но большой надежды что там ответят нету, ресурс сильно опопсел.

Answer 1

[Павел Тысляцкий]

Если учитывать что Вы не привязваетесь к DOM, то можно предположить что все возможныне css правила это бесконечное множество (конечно можно сделать его конечным с ограничениями на число элементов или длине строки правила). Теперь любой css или группу css или одно css правило можно представить как подмножество всех css правил. Как я понимаю Вы хотите сделать из подмножества группы css другое подмножество с меньшим или равным количесвом правил (иначе весь смысл теряется). Те Вы хотите для двух любых правил найти найти в лучшем случае одно, в худшем два правила. Тогда:

a {...} a {...} можно преобразовать в a {...}

a {...} div a {...} можно преобразовать в a {...} только в том случае если правила a имеют больший приоритет, например !important, в противном случае этого сделать нельзя тк данные правила определяют разные возможные подмножества.

Я склоняюсь к тому что уменьшить количество правил практически нереально, тк они описывают разные подмножества. Когда правила опиывают одно подмножество, или более общее подмножество имеет больший приоритет, то некоторые правила можно упразднить.

Теперь поиск. Для того чтобы определить элементы которому удовлетворяет правило, необходимо пройтись по всему дереву. Это достаточно интересный момент, тк некоторые css правила могут явно описывать элементы находящиеся внутри другого правила, например:

.base .child и .base .child .node заведомо извесно что все .base .child .node элементы будут находиться внутри .base .child.

Таким образом если предствать такие правила как дерево, можно уменьшить затраты на поиск элементов в уже найденом базовом элементе.

Вариации поиска. Я вижу два основных варианта:
1. берем правило, проходим по DOM, для каждого элемента вычисляя является ли правило DOM элемента подмножеством определенного правила и применяем его, переходим к сл правилу.
2. берем DOM и начинаем проходить по нему, для элемента вычисляя является ли правило DOM элемента подмножеством определенного каждого правила и если да, то применяем его, переходи к сл элементу.

На второй вариант очень хорошо ложится предложение с деревом подправил и вообще кажется более интересным ввиду того что требуется один обход DOM.

Comments

[Виталий]

По поводу склейки — это не проблема вовсе, там по длине правила определяется приоритет + если явно не заданы настройки текста, то они переходят от родительского элемента. Важнее найти подходящие правила.
Вот вы написали: .base .child и .base .child .node
А ведь может быть и: .base .child и .node
Т.е. .node может быть и внутри и снаружи.
Да, я по второму варианту и хотел делать, вопрос только в эффективном и правильном поиске правил для заданного пути.

[Павел Тысляцкий]

Вот вы написали: .base .child и .base .child .node
А ведь может быть и: .base .child и .node
Т.е. .node может быть и внутри и снаружи.

Да, может, но в этом случае нет гарантии что .node будет внутри .base .child для правила .node, те это разные правила. Если же правило будет описано как .base .child .node, то уверенно можно сказать что оно никаким образом не будет применено к элементам .node находящимся вне .base .child .node.

Да, я по второму варианту и хотел делать, вопрос только в эффективном и правильном поиске правил для заданного пути.

Если Вы хотите делать один прогон по дереву, то собсвенно собираетесь оптимизировать поиск подходящих правил и это как Вы описали Ваша основаня задача.
Собсвенно тут есть сл подходы:
1. уменьшить количество правил, но как я описал выше здесь есть проблемы с точным определением подмножеств.
2. исключить заведомо неверные проверки.
3. ускорить саму проверку правила, тут все свести к проверке одного не разделенного правила element#id.class в хорошем случае.

Вы вроде бы хотеле инвертировать правила, но это может быть не совем оптимально если заведомо не проверять правила вне скоупа.
Я вижу структуру как дерево. Например, для правил div {...} div .node1 .node2 {...} div .node1 .node2 {} div a.node4 {}:

div
    .node1
        .node2
        .node3
    a.node4

Собсвенно тем самым ислючая все проверки .node1, .node1 .node2, .node1 .node3 и a.node4 дня не div элементов и тд.
Далее опускаясь в div, поиск по элеметам внутри мы будем делать по корням (div плюс если нужно дефолтыне стили) плюс по правилам .node1 и a.node4.
Когда мы опустимя в .node1, то поиск будем делать по корнмя плюс предыдущий поиск .node1 и a.node4 плюс .node2 и .node3.
Когда мы выйдем из .node1, то поиск по .node2 и .node3 уже будет не нужен.
Но данный случай не учитывает более сложных правил div>p, div+p и div~p, но они не выглядят слишком сложными.

Answer 2

[m-haritonov]

Не совсем понял в чём вопрос. Если распарсить CSS, то в итоге у Вас будет объектная структура данных CSS таблиц, их правил и селекторов (с которой Вы сможете взаимодействовать программно). И в реализации функции cssTable.get_styles Вам необходимо будет написать код, выполняющий поиск соответствующих CSS правил таблицы стилей по переданному CSS селектору (например, методом сопоставления переданного CSS селектора каждому из CSS селекторов таблицы стилей).

Т.е. когда функция, подобная Вашей cssTable.get_styles, применяется для поиска HTML элементов, она (руководствуясь переданным её CSS селектором и правилами синтаксиса CSS селекторов), находит нужный HTML элемент из всего дерева (например, сопоставляя по очереди каждый HTML элемент переданному CSS селектору). В Вашем же случае, в качестве HTML документа будет выступать таблица CSS стилей и при поиске Вы будете сопоставлять переданный функции CSS селектор каждому из CSS селектором в Вашей таблицы стилей.

Comments

[Виталий]

(1ый абзац): Проверять каждое правило для каждого элемента — это неправильно (медленно).
(2ой абзац): Вопрос именно в эффективном поиске элемента (множества эелементов), и это специфично именно для css, так как мы последовательно обходим все дерево html и для каждого элемента применяем правило.

Я пока что пришел к выводу что мне нужна инверсированная хеш-таблица (или что-то типа) правил, в которой селекторы описаны справа налево. К примеру:

div p.links a

превратится в (упрощенно): table[ 'a' ]['p.links']['div']

Путь я тоже буду инверсировать. Например 'html > div#content > p.links > a' превратится в 'a < p.links < div#content < html'.
Он будет выступать в качестве фильтра.
Т.е. читаю 'a' — беру из таблицы правила table['a'].
Читаю p.links — если есть правило, неподходящее под p.links (например table['a']['< .other'] — отфильтровываю его.
И т.д. до конца.
Если в таблице остались элементы с непройденными путями — отфильтровываю их.
Оставшиеся правила объединяю и возвращаю результат.

Пока что такой алгоритм. Может надумаю что-то получше.

[m-haritonov]

(1ый абзац): Проверять каждое правило для каждого элемента — это неправильно (медленно).

Чтобы избежать этого существуют индексы (тогда скорость поиска увеличится за счёт дополнительных расходов на оперативную память).

Я пока что пришел к выводу что мне нужна инверсированная хеш-таблица (или что-то типа) правил, в которой селекторы описаны справа налево.

И почему Вы решили, что поиск снизу вверх будет быстрее, чем сверху вниз? Вы рассматриваете какие-то частные случае таблиц стилей?

[Виталий]

>> И почему Вы решили, что поиск снизу вверх будет быстрее
Тут не в «быстрее» даже дело, а в том что конечный элемент находится справа. Зачем нам проходить через span, p, div и т.д. если нам нужно множество 'a' элементов? По такой же логики и работа с предыдущими элементами. Тут полюбому инверсия эффективнее прямой структуры.

Грубый пример прямой таблицы:

div <rule> p span <rule> div p span <rule> div h3 span a <rule> a <rule>

Обратная таблица:

div <rule> span p <rule> span p div <rule> a span h3 div <rule> a <rule>

Тогда при запросе table.get_rules('html > body > div > h3 > span > a') я уже первым прогоном сужаю область правил до 2х, а вторым прогоном получаю более конкретное (приоритет при слиянии).
Прямой поиск тут однозначно проигрывает. Я даже не могу придумать нормального алгоритма для поиска по прямой таблице.

[m-haritonov]

Если я правильно понял, то эталонный условный алгоритм у Вашей задаче следующий:
Запрос cssTable.get_styles( 'html > div#content > h3 > a' ) создаёт HTML код <html><div id="content"><h3><a></a></h3></div></html> к которому применяется каждый из селекторов таблицы стилей. Те селекторы, которые применились к тегу «a» и считаются искомыми. Их правила берутся для дальнейшего объединения и формирования возвращаемого значения.

В таком случае, Ваш алгоритм, видимо, действительно будет эффективнее, чем поиск слева направо, т.к. наличие конечного элемента из селектора запроса (т.е. самого глубокого элемента из условного HTML дерева) в конце искомых селекторов из таблицы стилей требуется всегда.

Я даже не могу придумать нормального алгоритма для поиска по прямой таблице.

По идее, реализация будет примерно такая же, как и в Вашей реализации алгоритма с конца. Селектор запроса разбивается на части (части «html» и «body» добавляются в начало селектора запроса всегда). Затем для каждой части слева направо ищутся все селекторы из таблицы стилей, начинающиеся на соответствующую часть (притом, ищутся для каждой части каждый раз во всей таблице стилей, включая повторное сравнения ранее отобранных селекторов, т.к. начало одного и того же селектора из таблицы стилей может соответствовать разным частям селектора запроса).

Отобранные селекторы из таблицы стилей, у которых следующая часть не совпадает со следующей частью селектора запроса — отбрасываются (за исключением селекторов потомков («div div») из таблицы стилей, следующий элемент которых надо применять к каждой из последующих частей селектора запроса, даже если совпадение уже нашлось). Также отбрасываются те из отобранных селекторов, у которых по завершению частей селектора запроса, справа ещё остались части.

Это всё лишь набросок, который может быть и ошибочным. Плюс, всё это усложнится, если добавлять в селектор запроса поддержку селектора потомков («div div») — это будет означать, что у нас будет бесконечное множество HTML деревьев (условно формируемых для селектора запроса).

Сестринские селекторы («div+div», «div~div»), а так же некоторые псевдоклассы (":first-child", ":last-child" и т.п.) учитывать, видимо, не понадобится, т.к. в HTML дереве (условно формируемому для селектора запроса) не будет сестринских элементов (только дочерние).

[m-haritonov]

Сестринские селекторы («div+div», «div~div»), а так же некоторые псевдоклассы (":first-child", ":last-child" и т.п.) учитывать, видимо, не понадобится, т.к. в HTML дереве (условно формируемому для селектора запроса) не будет сестринских элементов (только дочерние).

С этим я поторопился, т.к. нично не мешает написать селектор запроса вида html>div+p>a для которого будет формироваться условный HTML код <html><div></div><p><a></a></p></html>.

Answer 3

[Daedmen]

Посмотри как браузеры DOM хранят

Comments

[Виталий]

Если ссылку дашь, то посмотрю обязательно. Я даже css парсера никак найти в исходниках (chrome) не мог.

[m-haritonov]

Пробовали искать в коде JavaScript функций «document.querySelector» и «document.querySelectorAll»?

[Виталий]

https://github.com/chromium/chromium/search?q=querySelector&ref=cmdform нет результатов, но еще раз повторюсь: это не то совсем. Мне для заданного пути нужно найти множество селекторов.

[m-haritonov]

Смотрите здесь: https://code.google.com/p/chromium/codesearch#search/&q=querySelector&sq=package:chromium&type=cs

но еще раз повторюсь: это не то совсем. Мне для заданного пути нужно найти множество селекторов.

Тогда зачем Вы искали CSS парсер в Chrome (сами же писали)?!

[Виталий]

>> Тогда зачем Вы искали CSS парсер в Chrome (сами же писали)
Как зачем? Прежде чем писать свой, хотел гугловский портировать на python, он же наверняка там учитывает много особенностей css и поддерживает css3. Велосипед еще не значит что мне не интересны другие реализации.
За ссылку спасибо.

Answer 4

[Сергей]

Писать собственный рендерер, да ещё на питоне это хардкорно конечно. Я бы не решился.
Мне кажется, для хранения правил CSS все же нужно непосредственно накладывать последовательно правила на DOM дерево без использования промежуточных хранилищ. Т.е. строим DOM дерево. Считываем последовательно правила из вашего CSS:

a { display: block; font-size: 12pt; }
div p.links a { color: green; display: inline; }

и последовательно накладываем правила по селектору (перезаписывая конфликтующие правила, учитывая !important и пр). Получается, что при модификации дерева придется все правила прогонять заново.

Код браузера можно попытаться тут: github.com/WebKit/webkit/tree/master/Source/WebCore/css поковырять, но там комментариев в коде нет, вряд-ли удастся что то понять =)

Comments

[Сергей]

Ну и вот для Blink chromium.googlesource.com/chromium/blink/+/master/Source/core/css/

[Виталий]

Хм… накладывать на уже готовый DOM список селекторов это идея. Тут надо подумать что быстрее: искать css селекторы в DOM, или искать список правил для заданного пути DOM.
С css-селекторами в dom наверное проще будет в реализации, т.к. есть готовые билиотеки поддерживающие xpath, но чего-то скорость беспокоит. Типичный сайт имеет от 3-5 тысяч css селекторов… для каждого вызывать прогон по DOM накладно… будем эксперементировать.