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

По поводу склейки — это не проблема вовсе, там по длине правила определяется приоритет + если явно не заданы настройки текста, то они переходят от родительского элемента. Важнее найти подходящие правила.
Вот вы написали: .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, но они не выглядят слишком сложными.

(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'] — отфильтровываю его.
И т.д. до конца.
Если в таблице остались элементы с непройденными путями — отфильтровываю их.
Оставшиеся правила объединяю и возвращаю результат.

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

(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х, а вторым прогоном получаю более конкретное (приоритет при слиянии).
Прямой поиск тут однозначно проигрывает. Я даже не могу придумать нормального алгоритма для поиска по прямой таблице.

Если я правильно понял, то эталонный условный алгоритм у Вашей задаче следующий:
Запрос 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 дереве (условно формируемому для селектора запроса) не будет сестринских элементов (только дочерние).

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

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

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

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

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

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

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

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

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

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

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