О пользе префиксов
Я хочу рассказать о не совсем очевидной пользе префиксов в названиях имён и типов. Я считаю что у любых разработок у которых наличествует внешнее апи, должны быть префиксы, причём не с потолка взятые а тщательно выбранные.
Всё дело в удобстве поиска информации. Я уже почти год знаком с box2d, чуть больше с SDL и около двух месяцев как начал писать под ios (cocoa). И при работе с этими библиотеками я ощутил необыкновенную легкость и удобность. И совсем недавно, когда опять плотно занялся actionScript понял, чем те библиотеки отличаются от стандартного рантайма Adobe: префиксами. И дело не в коде, не в наличии пакетов или неймспейсов. Дело в гуглении. Это же просто шикарно, набрать в гугле SDL_MOUSEBUTTONDOWN, или NSArray или b2Shape и сразу получить то, что вы ищите. Это огромный плюс, возможность мгновенно находить то что вам нужно, очень важная часть хорошего апи. Чтобы найти документацию или сторонние обсуждения к Array от Adobe надо приписывать всякие штуки, типа as3 или Adobe, некоторые статьи теряются и не находятся таким образом. По запросу «array sort» гуглится и msdn и java и flash и php.
Я думаю что все апи с которыми будут взаимодействовать другие разработчики нужно снабжать префиксами. При этом нужно обязательно погуглить их, дабы не пересечься с уже занятыми. Это сделает разработчиков работающих с вашими апи счастливее.
Данный текст опубликован под лицензией CC-BY.
- префиксы
- префиксная нотация
Префиксы. Зачем и как правильно
Вадим Макеев: Добрый день! Я работаю в компании Opera Software, мы делаем разные браузеры. В своем докладе я буду не рекламировать какие-то крутые новинки, а расскажу о технологиях, которые мы используем повседневно. Поговорим о префиксах.
Префиксы используют все, но даже самые опытные специалисты порой не до конца понимают, как они работают. Для того, чтобы писать их правильно, нужно знать некоторые простые вещи, которые иногда оказываются совсем не простыми. Именно поэтому я расскажу вам о том, как это все работает.
Что может быть проще стула? Если в реальной жизни нам нужен стул, требуется одно простое действие – взять и поставить его. Но многие из вас пишут код, и вы периодически замечали, что некоторые свойства приходится повторять. Если у вас есть свойство «стул», вам нужно написать «-о-стул», чтобы все это нормально отобразилось в Opera. Потом вам понадобится «-ms-стул», «-moz-стул» и «-webkit-стул». Получается нагромождение, и совершенно непонятно, что с ним делать. И сесть на такой «стул» нельзя, и переносить неудобно.
Если вы каждый день сталкиваетесь с префиксами, то, честно говоря, они портят вам жизнь. 99 % людей мечтает, чтобы они исчезли и никогда не появлялись. Отчасти они правы, отчасти нет. Я объясню, почему.
Что собой представляют префиксы? Префикс, как правило, ставится перед значимым элементом и указывает на определенный браузер или производителя какой-либо техники. Префиксов существует очень много. Они могут начинаться как с дефиса, так и с нижнего подчеркивания. Префиксы – появились не в CSS 3, где они используются для таких вещей как градиент или “border-radius”, а еще в CSS 2.1. Это один из способов расширить CSS, добавляя туда собственные свойства, которые впоследствии можно стандартизировать.
На самом деле префиксы не «засоряют код». Изначально они были придуманы для того, чтобы помогать разработчикам браузеров адаптировать спецификацию под свои нужды и писать в них какие-то новые вещи. В итоги префиксы в большей степени стали использовать разработчики. Именно в этом кроется проблема.
Кстати, правильно называть префиксы именно «браузерными», а не «вендорными». В русском языке у слова «вендор» очень широкое значение. «Вендором», например, может быть и компания-поставщик холодильников. «Браузерный префикс» — это более удачный перевод.
Откуда вообще берутся префиксы? Давайте представим такую историю…
Где-то в Калифорнии, в Силиконовой долине утром просыпается разработчик webkit. Может быть, в офисе Google он заснул – бывает, трудоголики с работы не уходят. И во сне этому разработчику пришла идея свойства “lol-cat”. Он подумал, что классным значением для этого свойства будет вот такой милый смайлик.
«Надо бы внедрить это свойство», — решает разработчик. Но свойство нельзя внедрять в том виде, в котором оно ему приснилось. Сначала он должен спрятать его за пространством имен webkit.
Через некоторое время в Европе просыпаются разработчики из компании Mozilla. Они говорят: «Ага, ребята из Калифорнии придумали классное свойство “lol-cat”, давайте-ка мы тоже что-то придумаем. На самом деле, у нас в Европе принято другие смайлики рисовать. Поэтому нам нужно сделать другое значение!» И они вместо «домиков» делают «кругляшки». Кот у нас получается менее счастливым – может, он француз?
Но это неважно. Важно, что разработчики в Европе считают, что значение у свойства должно быть другим. Они очень вовремя добавляют префикс «-moz-», чтобы это свойство ни с чем не конфликтовало, чтобы только их браузер «понимал» это свойство и его значение. Браузер Mozilla префиксы «-moz-» «понимает».
Потом дело доходит до Норвегии, где нашего «кота» захотели сделать удивленным, и придумали свойству ещё одно значение.
Просто у каждого разработчика есть свое мнение относительно того, как все должно быть. Именно поэтому у нас был адский ад лет 10-15 назад – как раз из-за того, что разработчики не могли договориться друг с другом. Это нормальный процесс, это конкуренция. Есть масса людей, каждый из которых создает что-то, что, по его мнению, будет работать лучше. Для тех, кто живет в Калифорнии, лучше оказываются одни вещи, а для тех, кто живет в Европе, — другие.
Префиксы позволяют «прятать» все эти различия под браузерными пространствами имен и не мешать друг другу.
Но проходит полгода или год, проходит два года, три года, пять лет, и просыпаются разработчики из Консорциума всемирной паутины (W3C). Они говорят: «Никаких смайликов в значении не будет. У нас там будет стоять слово “smile”, потому что оно читаемо, понятно представителям всех культур и выглядит серьезно».
Эти разработчики пишут спецификацию, указывают типы смайликов, проверяют, чтобы совместимость этого свойства с другими была нормальной, все тестируют и выпускают спецификацию. Ее долго обсуждают, принимают версию «Кандидат в рекомендации». После этого W3C дает указание использовать беспрефиксную версию с тем значением, которое они утвердили. После прочтения новой спецификации владельцы всех браузеров должны избавиться от префиксов, убрать их из кода и использовать новое свойство. Но события развивались несколько по-другому. Об этом я еще расскажу.
Допустим, у нас есть свойство “box-shadow”. Когда совместимость была неполной, нам был нужен префикс. Мы писали вот так. Но это неправильно. Казалось бы, это естественно: пирамида должна стоять на самой широкой грани, чтобы быть устойчивой. Сначала идет “box-shadow”, потом “-moz- box-shadow”, затем “webkit-box-shadow”. Казалось бы, какая разница, в каком порядке свойства записывать, все равно каждое свойство адресуется каждому браузеру. Если ПО «понимает» свойство без префикса, оно «поймет» его без префикса, если оно «понимает» webkit, то оно «поймет» webkit. Но нет, все должно быть вот в таком порядке.
«Пирамида» должна «висеть» острием вниз. Необязательно, чтобы сначала шла часть с “webkit-…”, а потом часть с “-moz-”, их можно поменять местами. Главное, чтобы свойство “box-shadow” шло последним. Организация ровной «пирамиды» просто помогает визуально определить, все ли у вас в порядке с префиксами.
Зачем это вообще нужно? Представьте, что производители браузеров не успели отказаться от префиксов. Допустим, webkit-браузеры практически не отбрасывают префиксы, у них такая политика. То есть они сознательно не поступают так, как им рекомендует W3C. Думаю, они не делают этого потому, что есть старые версии iTunes, которые частично используют webkit, и надо, чтобы они справлялись с рендерингом страниц.
В итоге браузер, который сделал нормальную реализацию свойства, применит “smile”. А если это Mozilla Firefox, он дойдет до свойства с префиксом “-moz-”, то он может после правильного “smile” применить старое значение – возникнет ошибка. Если в браузере реализовано 2 типа свойств (с префиксом и без него), то будут применены те свойство и значение, которые расположены последними. Поэтому в конце должно стоять новое свойство без префикса.
Это главное правило, которое нужно знать при использовании префиксов. Многие этого не понимают. Свойство без префикса идет последним.
Кто-то может задать вопрос: иначе что? Я покажу, что произойдет в этом случае. Допустим, у элемента есть свойство “webkit-box-shadow”, размер тени 400 пикселей, отступ от центра 200 пикселей, тень черного цвета. Есть свойство “box-shadow” с теми же самыми значениями, они абсолютно одинаковы. Вот в таком порядке мы их записали – сначала с префиксом, потом без.
Текущий Chrome или Safari рендерят это вот так.
У нас есть блок нулевых размеров, к которому применена такая тень. Если мы поменяем порядок свойств (сначала свойство без префикса, а потом свойство с префиксом), то у нас получится вот что.
Рендеринг тени зависит от порядка свойств, потому что под версией без префикса «спрятана» более качественная и совместимая реализация. Возможно, она даже быстрее работает. Но главная ее ценность в том, что она совместима с другими браузерами.
То есть во всех браузерах будет вот такая хорошая тень.
А в браузере, для которого вы запишете префиксы в неправильном порядке, будет то нечто, которое я показывал.
Поэтому, чтобы применить самые новые и последние спецификации, пишите свойство без префиксов последним. Все свойства с префиксами нужны для поддержки старых браузеров на Android 2.1, например.
Что можно порекомендовать при работе с префиксами? У нас есть множество свойств для разных старых браузеров. Если вы делаете градиенты, применяете “transform”, “transition origin”, кода становится очень много. Есть варианты того, как этого можно избежать.
Самый интересный вариант из тех, что мне попадались за последнее время, это Prefix Free. Лия Веру, которая тоже выступала здесь на конференции РИТ++, написала JavaScript-библиотеку, которая находит свойства без префиксов и добавляет к ним префиксные свойства, притом не все, а только необходимые.
В самой библиотеке нет списка префиксов. JavaScript проверяет, какие префиксы «поймет» браузер, и добавляет только их. Это классное изобретение. Потому что в большинстве своем препроцессоры просто берут и добавляют все, что можно. А эта библиотека динамическая и добавляет только то, что нужно. Поэтому код у нас не «распухает». Количество правил в блоке, пусть даже невалидных правил, может влиять на производительность.
У этой библиотеки есть некоторые недостатки. Со сложным CSS вроде импорта она не работает, потому что внутрь не забирается. По-моему, это тоже можно решить, но это сильно усложнит код. Еще один недостаток состоит в том, что библиотека нагружает отрисовку.
Допустим, если вы делаете какой-то JS-fiddle, чтобы быстро посмотреть, как работает ваш код, такая библиотека будет идеальным вариантом. Лия Веру даже создала свой сервис для просмотра демонстраций – Tablet.Com. Там используется эта библиотека. Если вы напишите там градиент без префиксов, он заработает во всех браузерах, потому что библиотека автоматически его подставит.
Это быстрое JavaScript-решение. Для серьезных вещей оно не годится. Для них используются препроцессоры. Связка Sass и Compass работает на Ruby, они просто запускаются на локальной машине и обрабатывают ваши файлы. Less и Stylus могут работать как в качестве запущенных скриптов с чтением из файлов, так и при подключении в браузере. Это позволяет легко выполнять отладку без необходимости каждый раз переписывать файлы заново. Но у них есть некоторые особенности.
Препроцессоры популярны, потому что всем нам нравится, когда кода мало. Тем не менее, у них есть одна главная проблема – это их «глупость». Я сейчас расскажу о каждом из них.
Начнем с Compass. Compass позволяет писать свойства в двух нотациях. Через «собаку» — @include border-radius, также можно писать свойство через знак «плюс», что заодно поможет отказаться от фигурных скобок. В обоих случаях мы получим добавление префиксов для данного свойства. Это позволит получить и “-webkit-border-radius”, и “-moz-border-radius”, и так далее. Значение вы указываете тут же.
Какие провалы есть у Compass? Когда Compass добавляет префиксы, у нас появляются 2 свойства, которых не существует в природе. Их никогда не было и никогда не будет. Свойства “-o-border-radius” и “-ms-border-radius” не нужны в принципе. У нас есть избыточность в виде 2 лишних строк кода. Создатели не потратили лишних полчаса, чтобы изучить, какие свойства действительно нужно разворачивать. Modernizer, кстати, отказался от свойств khtml, потому что браузера под Linux, из идеи которого «родился» webkit, не существует. Разработчики khtml сами сказали, что будут использовать последний webkit для своего браузера Conqueror. Таким образом, три свойства с префиксами, которые предлагает Compass, лишние.
Какие еще провалы Compass стоит упомянуть? Забыт префикс “-ms-“ для свойств “transform” и “transition. У свойства “box-shadow” масса ненужных префиксов. Есть ненужный префикс “-o-“ для свойства “column”, которое делает несколько колонок. Для свойства “background-size” тоже есть ненужный префикс “-o-“, мы его поддерживаем без префикса. Если вы используете в коде “opacity”, Compass автоматически понапишет там “filter:progid:DXImage…”, причем он использует старую и невалидную версию, без “-ms-filter-…”, без кавычек и так далее. Ваш код будет испорчен.
Кстати, на поиск всех этих ошибок у меня ушло не более 15 минут. Не знаю, сколько времени нужно, чтобы их поправить. Минут 10, наверное. Несмотря на все ошибки, это по-прежнему одна из самых популярных библиотек для работы с префиксами.
Теперь поговорим о библиотеке Less. Она позволяет писать свойства через точку. И либо в коде, либо в каких-то отдельно подключаемых вещах у вас будет записываться, что происходит, какие значения он принимает. И вот он разворачивается в такие строки с префиксами. Казалось бы, все нормально. Но на сайте, в официальной документации использован неправильный порядок свойств. Те, кто делает библиотеку для работы с префиксами, не знают, как работает префикс.
Еще один пример с Less. Там все правильно, там нет лишних префиксов, насколько я понял, но порядок свойств они выводят неправильный по умолчанию. Вы можете написать собственные сниппеты, но правильный порядок не предполагается по умолчанию, у всех. А людей, которые пишут собственные сниппеты, единицы.
Stylus – это, на мой взгляд, самый гибкий из существующих препроцессоров. Это одна из самых адекватных библиотек для работы с префиксами, потому что она позволяет писать код очень гибко. Можно использовать массу нотаций, убирать фигурные скобки, точки с запятой, объявлять переменные без всяких префиксов. В моем примере “fonts” – это переменная, не нужно значка доллара, подчеркиваний или еще чего-то. Просто пишете «равно» и можете эту переменную дальше использовать.
Stylus – самый «молодой» препроцессор. В нем есть проблемы. Например, если вы поставите такие скобки, все поломается. Я «отбиваю» последнюю скобку, мне удобнее читать код, когда скобка «отбита». А здесь получается так: «отбил» скобку – сломал целый файл. Это несерьезно, хотя в остальном библиотека хорошая. Всем, кто делает такие библиотеки, советую писать пул запросов.
Префиксы можно использовать не только в CSS, но и в JavaScript. Если у вас есть какая-то анимация, например.
Как мы привыкли работать со свойствами в JavaScript? Если свойство состоит из двух слов, разделенных дефисом, мы берем и убираем дефис, а следующую букву делаем заглавной. Это называется «верблюдизацией» (Lower Camel Case), то есть первая буква строчная, а все остальные буквы заглавные. Это много где описано, мы привыкли работать с этим.
То же самое должно происходить с префиксами. Мы берем и заменяем префикс на букву. А поскольку это первая буква, то она будет строчной, а остальные заглавными. Получится примерно так.
По идее, все просто. Надо написать несколько строк кода, чтобы свойства заработали во всех браузерах. Допустим, нам нужно задать Transition Timing Function.
На первый взгляд, все нормально. Тестируем в браузере… Строки для префиксов “-moz-“ и “-o-“ не работают. Само свойство браузер поддерживает, но строки не работают.
Попробуем сделать первые буквы заглавными.
Тогда перестает работать строка, начинающаяся с “Ms” для IE.
Читаем спецификацию. Дословно там прописано, что с префиксами следует поступать так: дефис и буква превращаются в заглавную букву. Это должно применяться везде. По спецификации, первая буква должна быть заглавной.
А по факту в браузерах есть различия. Mozilla и Opera буквально следуют спецификации, Firefox и Opera «понимают» префиксы только тогда, когда первая буква прописная. Internet Explorer «понимаeт» их только тогда, когда первая буква строчная. Webkit «понимаeт» оба варианта.
Тем не менее, написанная только прописными буквами строка GETELEMENTBYID в JavaScript не сработает. Появляются какие-то двойные стандарты: в одном месте есть гибкость, в другом ее нет. Почему бы не сделать JavaScript независимым от регистра?
На самом деле, всем производителям браузерам стоит внимательнее читать спецификацию. Периодически к нам обращаются разработчики, которые жалуются, что у них что-то не работает. Мы им отвечаем, что все реализовано в строгом соответствии со спецификацией, а не с ориентацией на другие браузеры. Такое периодически случается. Разработчикам мои разъяснения не помогают, естественно. Я себя чувствую виноватым из-за того, что мы сделали что-то не так, как в других браузерах.
Грядет страшное!
А сейчас я вынужден предупредить вас о том, что скоро все будет очень плохо. Opera, Mozilla и Microsoft собираются поддерживать свойства с префиксом “-webkit-”. Компания Mozilla заявила об этом. Они в этом заинтересованы, потому что им кажется, что их игнорируют разработчики, пишущие для iPhone. Opera и Microsoft тоже заинтересовались поддержкой этого префикса. На мероприятии CSS Working Group это обсуждалось. Возможно, я сейчас выдаю инсайдерскую информацию, но этот вопрос уже решен. Это случится очень скоро.
Безусловно, когда мы начнем поддерживать свойства с префиксом “-webkit-”, мы выпустим тестовую сборку, чтобы все могли проверить, что «отвалится» у них на сайтах, что начнет работать лучше, и так далее.
На самом деле, это не просто какая-то вольность. Было проведено специальное исследование. Аналитики компании Alexa взяли Топ 100 сайтов по всему миру и посчитали, какие свойства там используются. Свойств “-webkit-box-shadow” оказалось почти 800 штук. Свойств “-moz-border-radius” чуть меньше, “- webkit-border-radius» практически столько же. Дальше уже разрыв гораздо больше. Тут нет ни свойств Opera, почти нет свойств Microsoft Internet Explorer.
На диаграмме в процентном содержании показано распределение свойств, которые в целом используют разработчики. То есть про “-moz-» помнят, про “-webkit-” помнят, а про “-o-» и “-ms-» практически никогда не помнят, даже если браузер поддерживает эти свойства.
Поэтому нужно что-то делать. У нас в компании есть целый отдел Open Relations, там идет работа над проектом “Open the Web», где люди занимаются тем, что пишут разработчикам: «Пожалуйста, не блокируйте Opera! Мы поддерживаем это свойство. Напишите строчку кода!» А разработчики нам отвечают: «Да? А мы думали, что Opera – это мобильный браузер… Окей!» Иногда они не соглашаются, ссылаясь на малую распространенность Opera. Да, наш браузер по-разному распространен в разных регионах мира, но это не повод не давать ему то, что он может «понять»!
Поэтому и мы, и компания Mozilla (которую упоминают часто), решили заняться этим сомнительным делом с поддержкой свойств “-webkit-”. Возможно, от этого многое поломается, но многое и исправится.
Мы уже делали так раньше. Посмотрите любой User Agent браузера – что там написано? Там написано “like Mozilla”, то есть все идентично. Это способ сделать User Agent совместимым с сайтами, которые его проверяют и так далее. Сейчас User Agent каждого браузера представляет собой «кашу». Там множество строк, которые отвечают только за то, чтобы старые сайты не сломались. Долгое время браузеры поддерживали “document.all”, некоторые до сих пор его поддерживают. Если вы протестируете поддержку “document.all”, мы скажем, что ее нет, а если мы ей воспользуемся, окажется, что она будет. Для обратной совместимости.
Будут поддерживаться не все свойства “-webkit-”, а только избранные и нужные. Если мы пока не поддерживаем 3D-трансформацию (над этим наши специалисты пока работают), мы не будем делать вид, что мы ее поддерживаем. Будут поддерживаться только те свойства, которые «понимает» наш браузер, те, которые улучшат совместимость.
Если сейчас через Opera Mobile зайти на сайт, сделанный для iPhone, окажется, что у нас белый текст на белом фоне.
Если автоматически добавить нужные префиксы каким-то простым скриптом, все будет работать хорошо, — будет черный текст на синем фоне, например.
Мы пытаемся улучшить то, что видит пользователь, мы не пытаемся испортить жизнь разработчикам. Я сам разработчик, я сам был не в восторге от этой идеи поначалу. Постепенно привыкаю к этой мысли.
Свойства “-webkit-” будут применяться только в случае отсутствия свойств для Opera. Если будут найдены свойства для Opera, они будут применяться прежде всего. Каскады будут сохраняться, сайты для iPhone заработают.
Я предчувствую, что что-нибудь обязательно сломается. Поэтому мы при начале поддержки свойств “-webkit-” постараемся сообщить об этом всем. Нужно, чтобы все успели протестировать свои сайты.
Может случиться еще кое-что другое. Недавно я говорил с человеком из CSS Working Group, который занимается в том числе и спецификациями, он мой коллега. Он рассказал, что в CSS Working Group есть и другая идея относительно работы с префиксами. Объясню на примере.
Браузер «икс» внедрил свойство “lol-cat:smile” без префикса, но в какой-то момент обнаружилась ошибка. Чтобы исправить эту ошибку, он внедрит исправленную версию этого свойства с префиксом. Тогда разработчики смогут исправить ошибку, использовав префикс.
Как видно из примера, порядок свойств здесь другой. Текущий подход предполагает использование «пирамиды» острием вниз, а подход, который, возможно, предложит CSS Working Group, предлагает другую «пирамиду» — острием вверх. Так что неизвестно, что будет считаться правильным в перспективе. Пока правильно то, о чем я говорил в начале доклада. Что будет через год, два или три, мы не знаем. Префиксы не дадут нам заскучать. Помните главное: свойство без префикса идет последним.
Приведу ссылки на статьи, в которых есть более подробная информация о работе с префиксами. Первая статья Эрика Мейера дана в переводе. В остальных ведется дискуссия о префиксах, которая длится уже полгода. Люди буквально сражаются за то, чтобы или убрать префиксы совсем, или, наконец, сделать их удобными.
Большое вам спасибо за внимание. Жду вопросов.
Вопросы и ответы
Реплика из зала: Привет. Хочу сделать комментарий. Начну с того, что “khtml” был давно убран из Compass , а “transform” был исправлен. Opacity с префиксами не работает уже, их не нужно добавлять.
Вадим Макеев: Там с opacity проблема в том, что добавляется невалидный CSS-код.
Реплика из зала: Этот невалидный CSS-код нужен, чтобы поддерживался старый IE.
Вадим Макеев: Все, понял.
Вопрос из зала: Вопрос про другое. Есть ли какие-нибудь идеи (может быть, ты их знаешь), почему-то их не внедряют… Почему бы не сделать общий префикс для всех браузеров, например, “-beta-“ и оставить префиксы для всех браузеров на случай, если какие-то браузеры реализуют это свойство неправильно?
Вадим Макеев: Тогда тебе в коде придется писать не 6, а 7 строк.
Реплика из зала: Но большинство свойств реализовано всеми браузерами одинаково.
Вадим Макеев: Понимаешь, если у тебя какой-то крупный проект, и тебе важна полная совместимость, ты будешь писать все свойства… То есть ты предлагаешь эту ситуацию еще больше ухудшить…
Реплика из зала: Но потом-то будет лучше, когда «умрут» старые браузеры, которые не поддерживали общий префикс…
Вадим Макеев: На самом деле, таких дискуссий очень много. Главная идея, с которой согласны все: префиксы в текущем состоянии всех «достали». С этим нужно что-то делать. Есть еще потрясающий аргумент: префиксы – это экспериментальные свойства. У вас стабильный проект, зачем ему экспериментальные свойства? Мы вежливо улыбаемся ребятам из W3C и говорим: «Конечно, вы молодцы, что пишете спецификации, но сайты вы хоть раз разрабатывали?» Дискуссий много. Я рассказал о том, что есть. О том, что будет, я не могу рассказать. Я не гадалка.
Реплика из зала: Я, например, стараюсь писать префиксы вручную и быть в курсе, что сейчас где используется…
Вадим Макеев: Таких, как ты, мало.
Вопрос из зала: Штука в том, что помнить об этом и следить за изменениями не всегда просто и не всегда нужно. На самом деле, нас еще в университете учили, что не нужно ничего запоминать. Нужно думать и искать информацию. Сейчас для того, чтобы найти список актуальных префиксов, нужно перебрать примерно пять статей, хорошенько «полазить» по сайтам производителей… Не было ли когда-нибудь мысли создать сводный проект по префиксам, где можно будет посмотреть, в каких версиях движков что работает или не работает? Просто хочется знать, что поддерживается…
Вадим Макеев: Нужно «перелопатить» огромное количество данных. В последнее время на Западе очень популярны проекты типа «Все свойства такого-то браузера», «Все префиксы такого-то браузера», поддержка CSS 3, HTML 5, и так далее. Сейчас много таких проектов. Не удивлюсь, если в какой-то момент появится и то, о чем вы говорите. Есть парочка страниц, на которых собираются все свойства с префиксами всех известных браузеров. Две из них я знаю. Ссылок на них я не давал, но их можно найти довольно легко. Сводного проекта нет, но я бы с удовольствием поучаствовал в его создании.
Реплика из зала: Я бы тоже хотел поучаствовать в его создании. Есть основной момент… Собирать эти свойства с каких-то посторонних страниц крайне неприятно. Скажи, насколько возможно общение непосредственно с производителями браузеров, привлечение их к участию в таком проекте? Или хотя бы «вытягивать» данные из конкретных мест, где они будут их размещать.
Вадим Макеев: Я так понимаю, что ты бы хотел, чтобы сами производители браузеров выкладывали какой-нибудь файл XML или JSON со всеми префиксами? Это будет слишком накладно, мы же все очень занятые люди. Но я знаю, кого дернуть за рукав, чтобы получить актуальные списки – в принципе, это реально. Но вот обновлять их все-таки придется вручную.
Вопрос из зала: Что ты имеешь в виду? Придется каждый раз запрашивать у специалиста список, или в каком-то виде на каком-то ресурсе этот список будет фигурировать?
Вадим Макеев: Допустим, у нас есть страница, на которой есть все свойства с префиксами.
Реплика из зала: Вы практически святые в этом плане. Не стоит обобщать.
Вадим Макеев: Документация хорошая, мне правда нравится. Да, иногда мы добавляем туда свойства с опозданием на неделю, на месяц. У нас сильно загружен человек, который занимается документацией.
Реплика из зала: Ок.
Реплика из зала: Кстати, насчет гордости за документацию: мои переводы вы так и не опубликовали!
Вадим Макеев: Мы с вами свяжемся!
Реплика из зала: По поводу единого сайта, где указаны все префиксы… На сайте Mozilla Developer Center всегда указаны префиксы и версии, в которых все это работает. Единственное исключение – там практически не показана информация для каких-то технологий, которые не работают в Mozilla, но их достаточно мало.
Вадим Макеев: На самом деле, самый простой способ найти префиксы прямо сейчас – это зайти на сайт webstandards.ru и ввести в строке поиска слово «префиксы». Примерно полгода или год назад мы писали новость со ссылками на страницы, где описаны все браузерные префиксы. Еще вопросы?
Вопрос из зала: Когда Opera начнет префиксы webkit, она будет поддерживать их так, как это у вас уже реализовано, или так, как это реализовано в webkit?
Вадим Макеев: Нет, мы просто будем «мапить» существующие свойства на свойства webkit. Есть еще один момент… Мы сейчас работаем над новой спецификацией Flexbox, она уже настолько финализирована, что ее можно внедрять. За последние полгода ее переписали практически с нуля. Там есть общие слова, но суть там очень сильно поменялась. Когда мы внедрим новую спецификацию Flexbox, мы посмотрим сайты и, возможно, сделаем совместимость со старой. Мы не просто будем реализовывать спецификацию, а «замапим» нужные свойства в виде ссылки.
Допустим, вы пишете какой-нибудь webkit Flexbox или просто Flexbox в старой нотации, а он раз – и начинает работать по спецификации. Мы не будем писать вторую реализацию, не будем «форкать».
Реплика из зала: У меня не вопрос, а небольшое предостережение. Вы компетентный специалист, и в вашем докладе прозвучали нотки антиагитации против использования Less и других подобных инструментов, правильно? Было такое, пусть и в неявном виде. А инструмент хороший, просто в нем есть некоторые нюансы, которые вы перечислили. Но сам инструмент очень облегчает жизнь. Я смотрел в исходники Less. На первых порах было много проблем с парсингом CSS, были какие-то ошибки, нельзя было вставить комментарии внутрь значения CSS-свойства. Все «валилось», да и сейчас так, по-моему. Вся проблема Less в том, что они разбирают CSS регулярными выражениями. Наверное, остальные препроцессоры работают сходным образом. А это, по-моему, абсолютно неправильно. У CSS слишком сложная структура для того, чтобы разбирать его на регулярные выражения.
Вадим Макеев: У молодого человека, который с микрофоном ходит, есть проект CSScomb, который разбирает CSS не регулярными выражениями, а построчно. Не просто пытается понять, как CSS работает, но разбирает его на какие-то простые структуры.
Реплика из зала: На простые структуры можно разбить CSS, описав CSS в виде БНФ, то есть формы Бэкуса-Наура. В Mozilla Developer Network все спецификации в виде псевдо-БНФ… Если так описать, то будет очень гибкий инструмент для анализа и трансформации CSS.
Вадим Макеев: Если там написано выражение (англ. expression), в которое вставляется таблица… Да?
Реплика из зала: Как раз SCSS под проекты SASS (оперативный синтаксис, совместимый с CSS) не использует регулярные выражения, он честно все парсит, и когда он вышел, было заявлено, что его парсер справится с любым валидным CSS-документом, включая невалидные расширения для IE.
Вадим Макеев: То есть если там «закавычена» таблица на 300 строк, он не сломается?
Реплика из зала: Если это нормально обрабатывается в браузерах, то проблем не будет.
Вопрос из зала: У меня вопрос: почему вы не перейдете на движок webkit?
Вадим Макеев: Тема слишком обширна. Попробую ответить кратко. Потому, что это не имеет смысла вообще. Нам придется уволить всех наших инженеров. Впрочем, есть более важный аспект. Я не с того пункта начал. Проект webkit контролируется компаниями Apple и Google. Чтобы получить право отправлять обновления (англ. commit) в основное ядро проекта, нужно иметь проверяющих (англ. reviewer) где-нибудь в Калифорнии, платить им как вице-президентам нефтяных компаний. Также стоит иметь в виду, что 90 % проверяющих ядра webkit связаны с Apple и Google. Все, что им не понравится, они будут отклонять. Чтобы начать разрабатывать движок, нельзя просто «форкнуть» Google и начать его писать. Это кажется классным и интересным. Но это повлечет за собой огромное количество проблем. Мы обсуждали эту возможность, это адекватно. Мы не хотим поддерживать что-то свое, но плохое. Мы хотим, чтобы пользователям было удобно. Но для того, чтобы им было удобно, мы должны иметь возможность гибко разрабатывать то, что мы хотим. Переход на webkit нам этой гибкости не даст. Мы просто разоримся.
Реплика из зала: У меня не вопрос, а замечание по поводу дискуссии о webkit и так далее. Я ещё помню времена, когда очень распространенным браузером был IE5. Монополия движка какого-то одного браузера ни к чему хорошему не приводит. Сейчас прекрасное время. Конкуренция дает массу преимуществ. Мы сейчас ими пользуемся, и будем пользоваться еще достаточно долго. Хорошо, что у нас есть разные браузеры. Здорово, что они продолжают появляться и что они делают друг друга лучше.
Префикс-функция
Здесь и далее считаем, что символы в строках нумеруются с [math]0[/math] .
Определим префикс-функцию от строки [math]s[/math] в позиции [math]i[/math] следующим образом: [math]\pi(s, i) = \max\limits_ \[/math] . Если мы не нашли такого [math]k[/math] , то [math]\pi(s, i)=0[/math] .
Наивный алгоритм
Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за [math]n[/math] . Будем считать, что префикс-функция хранится в массиве [math] p [/math] .
Псевдокод
int[] prefixFunction(string s): int[] p = int[s.length] fill(p, 0) for i = 0 to s.length - 1 for k = 0 to i - 1 if s[0..k] == s[i - k..i] p[i] = k return p
Пример
Рассмотрим строку [math]abcabcd[/math] , для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math] .
| Шаг | Строка | Значение функции |
|---|---|---|
| [math]1[/math] | a | 0 |
| [math]2[/math] | ab | 0 |
| [math]3[/math] | abc | 0 |
| [math]4[/math] | abca | 1 |
| [math]5[/math] | abcab | 2 |
| [math]6[/math] | abcabc | 3 |
| [math]7[/math] | abcabcd | 0 |
Время работы
Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math] , что дает в итоге [math]O(n^3)[/math] .
Эффективный алгоритм
Вносятся несколько важных замечаний:
- Заметим, что [math]p[i + 1] \leqslant p[i] + 1[/math] . Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции [math]i + 1[/math] и имеющий длину [math]p[i + 1][/math] , удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции [math]i[/math] и имеющий длину [math]p[i + 1] — 1[/math] , следовательно неравенство [math]p[i + 1] \gt p[i] + 1[/math] неверно.
- Избавимся от явных сравнений строк. Пусть мы вычислили [math]p[i][/math] , тогда, если [math]s[i + 1] = s[p[i]][/math] , то [math]p[i + 1] = p[i] + 1[/math] . Если окажется, что [math]s[i + 1] \ne s[p[i]][/math] , то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое [math]k[/math] , что [math]k = p[i] — 1[/math] . Делаем это следующим образом. За исходное [math]k[/math] необходимо взять [math]p[i — 1][/math] , что следует из первого пункта. В случае, когда символы [math]s[k][/math] и [math]s[i][/math] не совпадают, [math]p[k — 1][/math] — следующее потенциальное наибольшее значение [math]k[/math] , что видно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math] , что позволит всегда найти его следующее значение. Если [math]k=0[/math] , то [math]p[i]=1[/math] при [math]s[i] = s[1][/math] , иначе [math]p[i]=0[/math] .
Псевдокод
int[] prefixFunction(string s): p[0] = 0 for i = 1 to s.length - 1 k = p[i - 1] while k > 0 and s[i] != s[k] k = p[k - 1] if s[i] == s[k] k++ p[i] = k return p
Время работы
Время работы алгоритма составит [math]O(n)[/math] . Для доказательства этого нужно заметить, что итоговое количество итераций цикла [math]\mathrm[/math] определяет асимптотику алгоритма. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n — 1[/math] . Поскольку внутри цикла [math]\mathrm[/math] значение [math]k[/math] лишь уменьшается, получается, что [math]k[/math] не может суммарно уменьшиться больше, чем [math]n-1[/math] раз. Значит цикл [math]\mathrm[/math] в итоге выполнится не более [math]n[/math] раз, что дает итоговую оценку времени алгоритма [math]O(n)[/math] .
Построение префикс-функции по Z-функции
Постановка задачи
Дан массив с корректной Z-функцией для строки [math]s[/math] , получить за [math]O(n)[/math] массив с префикс-функцией для строки [math]s[/math] .
Описание алгоритма
Пусть Z-функция хранится в массиве [math]z[0 \ldots n-1][/math] . Префикс-функцию будем записывать в массив [math]p[0 \ldots n-1][/math] . Заметим, что если [math]z[i] \gt 0, [/math] то для всех элементов с индексом [math]i + j[/math] , где [math]0 \leqslant j \lt z[i] [/math] , значение [math]p[i + j] [/math] будет не меньше, чем длина подстроки с [math] i [/math] по [math] i + j[/math] , что равно [math]j + 1[/math] (как изображено на рисунке).
Также заметим, что если мы уже установили в какую-то позицию значение [math] j [/math] с позиции [math] i [/math] , а потом пытаемся установить значение [math] j’ [/math] c позиции [math] i’ [/math] , причём [math] i \lt i’ [/math] и [math] i + j = i’ + j’ [/math] , то изменение с позиции [math] i’ [/math] только уменьшит значение [math] p[i + j][/math] . Действительно, значение после первого присвоения [math]p[i + j] = j \gt j’ = p[i’ + j’][/math] . В итоге получаем алгоритм: идем слева направо по массиву [math]z[/math] и, находясь на позиции [math]i[/math] , пытаемся записать в [math]p[/math] от позиции [math]i + z[i] — 1 [/math] до [math]i[/math] значение [math] j + 1,[/math] где [math]j[/math] пробегает все значения [math] 0 \dots z[i] — 1[/math] , пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.
Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только [math]\mathrm[/math] . Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество [math]\mathrm[/math] . Количество установленных значений — [math] n[/math] . А число [math]\mathrm[/math] тоже будет не больше [math]n[/math] , так как каждый [math]\mathrm[/math] переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику [math]O(n)[/math] .
Псевдокод
int[] buildPrefixFunctionFromZFunction(int[] z): int[] p = int[z.length] fill(p, 0) for i = 1 to z.length - 1 for j = z[i] - 1 downto 0 if p[i + j] > 0 break else p[i + j] = j + 1 return p
Построение строки по префикс-функции
Постановка задачи
Восстановить строку по префикс-функции за [math]O(n)[/math] , считая алфавит неограниченным.
Описание алгоритма
Пусть в массиве [math]p[/math] хранятся значения префикс-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]p[/math] слева направо.
Пусть мы хотим узнать значение [math]s[i][/math] . Для этого посмотрим на значение [math]p[i][/math] : если [math]p[i] =0[/math] , тогда в [math]s[i][/math] запишем новый символ, иначе [math]s[i] = s[p[i] — 1][/math] . Обратим внимание, что [math]s[p[i] — 1][/math] нам уже известно, так как [math]p[i] — 1 \lt i[/math] .
Реализация
string buildFromPrefix(int[] p): s = "" for i = 0 to p.length - 1 if p[i] == 0 s += new character else s += s[p[i] - 1] return s
Доказательство корректности алгоритма
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Пусть [math]p[/math] — данная префикс-функция, строку [math]s[/math] построил наш алгоритм, [math] q [/math] — массив значений префикс-функции для [math]s[/math] .
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива [math] q [/math] прибавление нового символа не влияет, так как при подсчёте префикс-функции на [math] i [/math] -ой позиции рассматриваются символы на позициях не больше [math] i [/math] . Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
- База очевидна для строки длины [math]1[/math] .
- Переход: пусть до [math]n[/math] -ой позиции мы построили строку, что [math]p[0 \ldots n — 1] = q[0 \ldots n — 1][/math] . Возможны два случая:
- [math]p[n] = 0[/math] . Тогда мы добавляем новый символ, поэтому [math]q[n][/math] тоже будет равно [math]0[/math] .
- [math]p[n] \gt 0[/math] . Бордер строки [math] s[0 \ldots n — 1] [/math] имеет длину [math] p[n-1] = q[n-1] [/math] . Поэтому если дописать к строке [math] s [/math] символ [math] s[q[n] — 1] [/math] , то бордер нашей новой строки [math] s[0 \ldots n] [/math] станет равен [math] p[n] [/math] , как можно увидеть на рисунке.
Критерий корректности значений префикс-функции
Задача: Дан массив значений префикс-функции некоторой строки [math]s[/math] , необходимо проверить, корректен ли он за [math]O(|s|)[/math] . Так же узнать размер минимального алфавита, при котором он корректен. Решение
Если выполняется неравенство [math]0 \leqslant p[i + 1] \leqslant p[i] + 1[/math] , то мы можем построить строку из алгоритма выше, значит префикс-функция корректна.
Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву.
Доказательство корректности
Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом [math]\mathrm[/math] по подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей мощности, чем найденный алгоритмом выше.
Псевдокод
bool is_correct(int[] p): for i = 0 to p.length - 1 if i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0 return false return true
int minimal_alphabet(int[] p): c = 1 s[0] = 0 for i = 1 to p.length - 1 if p[i] == 0 fill(used, false) k = p[i - 1] while k > 0 used[s[k]] = true k = p[k - 1] s[i] = -1 for j = 1 to c if !used[j] s[i] = j; break if s[i] == -1 s[i] = c++ else s[i] = s[p[i] - 1] return c
См. также
- Z-функция
- Алгоритм Кнута-Морриса-Пратта
Источники информации
- Википедия — Префикс-функция
- MAXimal :: algo :: Префикс-функция
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296 ISBN 978-5-8459-0857-5
- Алгоритмы и структуры данных
- Поиск подстроки в строке
- Точный поиск
Префикс-функция
Определение. Префикс-функцией от строки $s$ называется массив $p$, где $p_i$ равно длине самого большого префикса строки $s_0 s_1 s_2 \ldots s_i$, который также является и суффиксом $i$-того префика (не считая весь $i$-й префикс).
Например, самый большой префикс, который равен суффиксу для строки «aataataa» — это «aataa»; префикс-функция для этой строки равна $[0, 1, 0, 1, 2, 3, 4, 5]$.
Этот алгоритм пока что работает за $O(n^3)$, но позже мы его ускорим.
#Как это поможет решить исходную задачу?
Давайте пока поверим, что мы умеем считать префикс-функцию за линейное от размера строки, и научимся с помощью нее искать подстроку в строке.
Соединим подстроки $s$ и $t$ каким-нибудь символом, который не встречается ни там, ни там — обозначим пусть этот символ # . Посмотрим на префикс-функцию получившейся строки s#t .
Видно, что все места, где значения равны 6 (длине $s$) — это концы вхождений $s$ в текст $t$.Такой алгоритм (посчитать префикс-функцию от s#t и посмотреть, в каких позициях она равна $|s|$) называется алгоритмом Кнута-Морриса-Пратта.
#Как её быстро считать
Рассмотрим ещё несколько примеров префикс-функций и попытаемся найти закономерности:
Можно заметить следующую особенность: $p_$ максимум на единицу превосходит $p_i$.
Доказательство. Если есть префикс, равный суффиксу строки $s_$, длины $p_$, то, отбросив последний символ, можно получить правильный суффикс для строки $s_$, длина которого будет ровно на единицу меньше.
Попытаемся решить задачу с помощью динамики: найдём формулу для $p_i$ через предыдущие значения.
Заметим, что $p_ = p_i + 1$ в том и только том случае, когда $s_ =s_$. В этом случае мы можем просто обновить $p_$ и пойти дальше.
Например, в строке $\underbracet\overbrace$ выделен максимальный префикс, равный суффиксу: $p_ = 5$. Если следующий символ равен будет равен $t$, то $p_ = p_ + 1 = 6$.
Но что происходит, когда $s_\neq s_$? Пусть следующий символ в этом же примере равен не $t$, а $b$.
- $\implies$ Длина префикса, равного суффиксу новой строки, будет точно меньше 5.
- $\implies$ Помимо того, что искомый новый супрефикс является суффиксом «aabaab», он ещё является префиксом подстроки «aabaa».
- $\implies$ Значит, следующий кандидат на проверку — это значение префикс-функции от «aabaa», то есть $p_4 = 2$, которое мы уже посчитали.
- $\implies$ Если $s_2 = s_$ (т. е. новый символ совпадает с идущим после префикса-кандидата), то $p_ = p_2 + 1 = 2 + 1 = 3$.
В данном случае это действительно так (нужный префикс — «aab»). Но что делать, если, в общем случае, $p_ \neq p_$? Тогда мы проводим такое же рассуждение и получаем нового кандидата, меньшей длины — $p_>$. Если и этот не подошел — аналогично проверяем меньшего, пока этот индекс не станет нулевым.
Асимптотика. В худшем случае этот while может работать $O(n)$ раз за одну итерацию, но в среднем каждый while работает за $O(1)$.
Префикс-функция каждый шаг возрастает максимум на единицу и после каждой итерации while уменьшается хотя бы на единицу. Значит, суммарно операций будет не более $O(n)$.