code:
## 1.1.3 (March 31, 2021)

- Fixed matching on CSS wide keywords for at-rule's prelude and descriptors
- Added `fit-content` to `width` property patch as browsers are supported it as a keyword (nonstandard), but spec defines it as a function
- Fixed parsing a value contains parentheses or brackets and `parseValue` option is set to `false`, in that case `!important` was included into a value but must not (#155)

## 1.1.2 (November 26, 2020)

- Rolled back to use spread syntax in object literals since it not supported by nodejs < 8.3 (#145)

## 1.1.1 (November 18, 2020)

- Fixed edge cases in mismatch location computation for `SyntaxMatchError`

## 1.1.0 (November 17, 2020)

- Bumped `mdn-data` to 2.0.14
- Extended `fork()` method to allow append syntax instead of overriding for `types`, `properties` and `atrules`, e.g. `csstree.fork({ types: { color: '| foo | bar' } })`
- Extended lexer API for validation
    - Added `Lexer#checkAtruleName(atruleName)`, `Lexer#checkAtrulePrelude(atruleName, prelude)`, `Lexer#checkAtruleDescriptorName(atruleName, descriptorName)` and `Lexer#checkPropertyName(propertyName)`
    - Added `Lexer#getAtrule(atruleName, fallbackBasename)` method
    - Extended `Lexer#getAtrulePrelude()` and `Lexer#getProperty()` methods to take `fallbackBasename` parameter
    - Improved `SyntaxMatchError` location details
    - Changed error messages

## 1.0.1 (November 11, 2020)

- Fixed edge cases for parsing of custom property value with a single whitespace when `parseCustomProperty:true`

## 1.0.0 (October 27, 2020)

- Added `onComment` option to parser config
- Added support for `break` and `skip` values in `walk()` to control traversal
- Added `List#reduce()` and `List#reduceRight()` methods
- Bumped `mdn-data` to 2.0.12
- Exposed version of the lib (i.e. `import { version } from 'css-tree'`)
- Fixed `Lexer#dump()` to dump atrules syntaxes as well
- Fixed matching comma separated `<urange>` list (#135)
- Renamed `HexColor` node type into `Hash`
- Removed `element()` specific parsing rules
- Removed `dist/default-syntax.json` from package

## 1.0.0-alpha.39 (December 5, 2019)

- Fixed walker with `visit: "Declaration"` to iterate `DeclarationList` (#114)

## 1.0.0-alpha.38 (November 25, 2019)

- Bumped `mdn-data` to `2.0.6`
- Added initial implmentation for at-rule matching via `Lexer#matchAtrulePrelude()` and `Lexer#matchAtruleDescriptor()` methods
- Added `-moz-control-character-visibility`, `-ms-grid-columns`, `-ms-grid-rows` and `-ms-hyphenate-limit-last` properties to patch (#111)
- Added `flow`, `flow-root` and `table-caption` values to patched `display` (#112)

## 1.0.0-alpha.37 (October 22, 2019)

- Bumped `source-map` version to `^0.6.1` to fix source map generation inconsistency across node.js versions due to mappings sorting bug and v8 moving to [a stable Array#sort](https://v8.dev/blog/array-sort) ([fix commit](https://github.com/mozilla/source-map/commit/f35a2e4212dd025cb5e1fc219e7ac8a4b96c2cc9) in `source-map`)

## 1.0.0-alpha.36 (October 13, 2019)

- Dropped support for Node < 8
- Updated dev deps (fixed `npm audit` issues)
- Reworked build pipeline
    - Package provides `dist/csstree.js` and `dist/csstree.min.js` now (instead of single `dist/csstree.js` that was a min version)
    - Bundle size (min version) reduced from 191Kb to 158Kb due to some optimisations
- Definition syntax
    - Renamed `grammar` into `definitionSyntax` (named per spec)
    - Added `compact` option to `generate()` method to avoid formatting (spaces) when possible
- Lexer
    - Changed `dump()` method to produce syntaxes in compact form by default

## 1.0.0-alpha.35 (October 7, 2019)

- Walker
    - Changed implementation to avoid runtime compilation due to CSP issues (see #91, #109)
    - Added `find()`, `findLast()` and `findAll()` methods (e.g. `csstree.find(ast, node => node.type === 'ClassSelector')`)

## 1.0.0-alpha.34 (July 27, 2019)

- Tokenizer
    - Added `isBOM()` function
    - Added `charCodeCategory()` function
    - Removed `firstCharOffset()` function (use `isBOM()` instead)
    - Removed `CHARCODE` dictionary
    - Removed `INPUT_STREAM_CODE*` dictionaries
- Lexer
    - Allowed comments in matching value (just ignore them like whitespaces)
    - Increased iteration count in value matching from 10k up to 15k
    - Fixed missed `debugger` (#104)

## 1.0.0-alpha.33 (July 11, 2019)

- Lexer
    - Fixed low priority productions matching by changing an approach for robust one (#103)

## 1.0.0-alpha.32 (July 11, 2019)

- Lexer
    - Fixed low priority productions matching in long `||-` and `&&-` groups (#103)

## 1.0.0-alpha.31 (July 11, 2019)

- Bumped `mdn/data` to `2.0.4` (#99)
- Lexer
    - Added [bracketed range notation](https://drafts.csswg.org/css-values-4/#numeric-ranges) support and related refactoring
    - Removed `<number-zero-one>`, `<number-one-or-greater>` and `<positive-integer>` from generic types. In fact, types moved to patch, because those types can be expressed in a regular grammar due to bracketed range notation implemented
    - Added support for multiple token string matching
    - Improved `<custom-ident>` production matching to claim the keyword only if no other unfulfilled production can claim it (#101)
    - Improved `<length>` production matching to claim "unitless zero" only if no other unfulfilled production can claim it
    - Changed lexer's constructor to prevent generic types override when used
    - Fixed large `||`- and `&&`-group matching, matching continues from the beginning on term match (#85)
    - Fixed checking that value has `var()` occurrences when value is a string (such values can't be matched on syntax currently and fail with specific error that can be used for ignorance in validation tools)
    - Fixed `<declaration-value>` and `<any-value>` matching when a value contains a function, parentheses or braces

## 1.0.0-alpha.30 (July 3, 2019)

- Bumped `mdn/data` to `~2.0.3`
    - Removed type removals from `mdn/data` due to lack of some generic types and specific lexer restictions (since lexer was reworked, see below)
    - Reduced and updated patches
- Tokenizer
    - Reworked tokenizer itself to compliment [CSS Syntax Module Level 3](https://drafts.csswg.org/css-syntax/#tokenization)
    - `Tokenizer` class splitted into several abstractions:
        - Added `TokenStream` class
        - Added `OffsetToLocation` class
        - Added `tokenize()` function that creates `TokenStream` instance for given string or updates a `TokenStream` instance passed as second parameter
        - Removed `Tokenizer` class
    - Removed `Raw` token type
    - Renamed `Identifier` token type to `Ident`
    - Added token types: `Hash`, `BadString`, `BadUrl`, `Delim`, `Percentage`, `Dimension`, `Colon`, `Semicolon`, `Comma`, `LeftSquareBracket`, `RightSquareBracket`, `LeftParenthesis`, `RightParenthesis`, `LeftCurlyBracket`, `RightCurlyBracket`
    - Replaced `Punctuator` with `Delim` token type, that excludes specific characters with its own token type like `Colon`, `Semicolon` etc
    - Removed `findCommentEnd`, `findStringEnd`, `findDecimalNumberEnd`, `findNumberEnd`, `findEscapeEnd`, `findIdentifierEnd` and `findUrlRawEnd` helper function
    - Removed `SYMBOL_TYPE`, `PUNCTUATION` and `STOP_URL_RAW` dictionaries
    - Added `isDigit`, `isHexDigit`, `isUppercaseLetter`, `isLowercaseLetter`, `isLetter`, `isNonAscii`, `isNameStart`, `isName`, `isNonPrintable`, `isNewline`, `isWhiteSpace`, `isValidEscape`, `isIdentifierStart`, `isNumberStart`, `consumeEscaped`, `consumeName`, `consumeNumber` and `consumeBadUrlRemnants` helper functions
- Parser
    - Changed parsing algorithms to work with new token type set
    - Changed `HexColor` consumption in way to relax checking a value, i.e. now `value` is a sequence of one or more name chars
    - Added `&` as a property hack
    - Relaxed `var()` parsing to only check that a first arguments is an identifier (not a custom property name as before)
- Lexer
    - Reworked syntax matching to relay on token set only (having AST is optional now)
    - Extended `Lexer#match()`, `Lexer#matchType()` and `Lexer#matchProperty()` methods to take a string as value, beside AST as a value
    - Extended `Lexer#match()` method to take a string as a syntax, beside of syntax descriptor
    - Reworked generic types:
        - Removed `<attr()>`, `<url>` (moved to patch) and `<progid>` types
        - Added types:
            - Related to token types: `<ident-token>`, `<function-token>`, `<at-keyword-token>`, `<hash-token>`, `<string-token>`, `<bad-string-token>`, `<url-token>`, `<bad-url-token>`, `<delim-token>`, `<number-token>`, `<percentage-token>`, `<dimension-token>`, `<whitespace-token>`, `<CDO-token>`, `<CDC-token>`, `<colon-token>`, `<semicolon-token>`, `<comma-token>`, `<[-token>`, `<]-token>`, `<(-token>`, `<)-token>`, `<{-token>` and `<}-token>`
            - Complex types: `<an-plus-b>`, `<urange>`, `<custom-property-name>`, `<declaration-value>`, `<any-value>` and `<zero>`
        - Renamed `<unicode-range>` to `<urange>` as per spec
        - Renamed `<expression>` (IE legacy extension) to `<-ms-legacy-expression>` and may to be removed in next releases

## 1.0.0-alpha.29 (May 30, 2018)

- Lexer
    - Syntax matching was completely reworked. Now it's token-based and uses state machine. Public API has not changed. However, some internal data structures have changed. Most significal change in syntax match result tree structure, it's became token-based instead of node-based.
    - Grammar
        - Changed grammar tree format:
            - Added `Token` node type to represent a single code point (`<delim-token>`)
            - Added `Multiplier` that wraps a single node (`term` property)
            - Added `AtKeyword` to represent `<at-keyword-token>`
            - Removed `Slash` and `Percent` node types, they are replaced for a node with `Token` type
            - Changed `Function` to represent `<function-token>` with no children
            - Removed `multiplier` property from `Group`
        - Changed `generate()` method:
            - Method takes an `options` as second argument now (`generate(node, forceBraces, decorator)` -> `generate(node, options)`). Two options are supported: `forceBraces` and `decorator`
            - When a second parameter is a function it treats as `decorate` option value, i.e. `generate(node, fn)` -> `generate(node, { decorate: fn })`
            - Decorate function invokes with additional parameter – a reference to a node
- Tokenizer
    - Renamed `Atrule` const to `AtKeyword`

## 1.0.0-alpha.28 (February 19, 2018)

- Renamed `lexer.grammar.translate()` method into `generate()`
- Fixed `<'-webkit-font-smoothing'>` and `<'-moz-osx-font-smoothing'>` syntaxes (#75)
- Added vendor keywords for `<'overflow'>` property syntax (#76)
- Pinned `mdn-data` to `~1.1.0` and fixed issues with some updated property syntaxes

## 1.0.0-alpha.27 (January 14, 2018)

- Generator
    - Changed node's `generate()` methods invocation, methods now take a node as a single argument and context (i.e. `this`) that have methods: `chunk()`, `node()` and `children()`
    - Renamed `translate()` to `generate()` and changed to take `options` argument
    - Removed `translateMarkup(ast, enter, leave)` method, use `generate(ast, { decorator: (handlers) => { ... }})` instead
    - Removed `translateWithSourceMap(ast)`, use `generate(ast, { sourceMap: true })` instead
    - Changed to support for children as an array
- Walker
    - Changed `walk()` to take an `options` argument instead of handler, with `enter`, `leave`, `visit` and `reverse` options (`walk(ast, fn)` is still works and equivalent to `walk(ast, { enter: fn })`)
    - Removed `walkUp(ast, fn)`, use `walk(ast, { leave: fn })`
    - Removed `walkRules(ast, fn)`, use `walk(ast, { visit: 'Rule', enter: fn })` instead
    - Removed `walkRulesRight(ast, fn)`, use `walk(ast, { visit: 'Rule', reverse: true, enter: fn })` instead
    - Removed `walkDeclarations(ast, fn)`, use `walk(ast, { visit: 'Declaration', enter: fn })` instead
    - Changed to support for children as array in most cases (`reverse: true` will fail on arrays since they have no `forEachRight()` method)
- Misc
    - List
        - Added `List#forEach()` method
        - Added `List#forEachRight()` method
        - Added `List#filter()` method
        - Changed `List#map()` method to return a `List` instance instead of `Array`
        - Added `List#push()` method, similar to `List#appendData()` but returns nothing
        - Added `List#pop()` method
        - Added `List#unshift()` method, similar to `List#prependData()` but returns nothing
        - Added `List#shift()` method
        - Added `List#prependList()` method
        - Changed `List#insert()`, `List#insertData()`, `List#appendList()` and `List#insertList()` methods to return a list that performed an operation
    - Changed `keyword()` method
        - Changed `name` field to include a vendor prefix
        - Added `basename` field to contain a name without a vendor prefix
        - Added `custom` field that contain a `true` when keyword is a custom property reference
    - Changed `property()` method
        - Changed `name` field to include a vendor prefix
        - Added `basename` field to contain a name without any prefixes, i.e. a hack and a vendor prefix
    - Added `vendorPrefix()` method
    - Added `isCustomProperty()` method

## 1.0.0-alpha.26 (November 9, 2017)

- Tokenizer
    - Added `Tokenizer#isBalanceEdge()` method
    - Removed `Tokenizer.endsWith()` method
- Parser
    - Made the parser tolerant to errors by default
    - Removed `tolerant` parser option (no parsing modes anymore)
    - Removed `property` parser option (a value parsing does not depend on property name anymore)
    - Canceled error for a handing semicolon in a block
    - Canceled error for unclosed `Brackets`, `Function` and `Parentheses` when EOF is reached
    - Fixed error when prelude ends with a comment for at-rules with custom prelude consumer
    - Relaxed at-rule parsing:
        - Canceled error when EOF is reached after a prelude
        - Canceled error for an at-rule with custom block consumer when at-rule has no block (just don't apply consumer in that case)
        - Canceled error on at-rule parsing when it occurs outside prelude or block (at-rule is converting to `Raw` node)
        - Allowed for any at-rule to have a prelude and a block, even if it's invalid per at-rule syntax (the responsibility for this check is moved to lexer, since it's possible to construct a AST with such errors)
    - Made a declaration value a safe parsing point (i.e. error on value parsing lead to a value is turning into `Raw` node, not a declaration as before)
    - Excluded surrounding white spaces and comments from a `Raw` node that represents a declaration value
    - Changed `Value` parse handler to return a node only with type `Value` (previously it returned a `Raw` node in some cases)
    - Fixed issue with `onParseError()` is not invoked for errors occured on selector or declaration value parsing in some cases
    - Changed using of `onParseError()` to stop parsing if handler throws an exception
- Lexer
    - Changed `grammar.walk()` to invoke passed handler on entering to node rather than on leaving the node
    - Improved `grammar.walk()` to take a walk handler pair as an object, i.e. `walk(node, { enter: fn, leave: fn })`
    - Changed `Lexer#match*()` methods to take a node of any type, but with a `children` field
    - Added `Lexer#match(syntax, node)` method
    - Fixed `Lexer#matchType()` method to stop return a positive result for the CSS wide keywords

## 1.0.0-alpha25 (October 9, 2017)

- Parser
    - Added fallback node as argument to `onParseError()` handler
    - Fixed raw consuming in tolerant mode when selector is invalid (greedy consuming and redundant warnings)
    - Fixed exception in tolerant mode caused by unknown at-rule with unclosed block
    - Changed handling of semicolons:
        - Hanging semicolon inside declaration blocks raise an error or turns into a `Raw` node in tolerant mode instead of being ignored
        - Semicolon outside of declaration blocks opens a `Rule` node as part of selector instead of being ignored
    - Aligned `parseAtrulePrelude` behaviour to `parseRulePrelude`
        - Removed `Raw` node wraping into `AtrulePrelude` when `parseAtrulePrelude` is disabled
        - Removed error emitting when at-rule has a custom prelude customer but no prelude is found (it should be validated by a lexer later)
- Generator
    - Fixed performance issue with `translateWithSourceMap()`, flattening the string (because of mixing building string and indexing into it) turned it into a quadratic algorithm (approximate numbers can be found in [the quiz created by this case](https://gist.github.com/lahmatiy/ea25d0e623d88ca9848384b5707d52d9))
- Added support for a single solidus hack for `property()`
- Minor fixes for custom errors

## 1.0.0-alpha24 (September 14, 2017)

- Improved CSSTree to be stable for standart build-in objects extension (#58)
- Parser
    - Renamed rule's `selector` to `prelude`. The reasons: [spec names this part so](https://www.w3.org/TR/css-syntax-3/#qualified-rule), and this branch can contain not only a selector (`SelectorList`) but also a raw payload (`Raw`). What's changed:
        - Renamed `Rule.selector` to `Rule.prelude`
        - Renamed `parseSelector` parser option to `parseRulePrelude`
        - Removed option for selector parse in `SelectorList`
- Lexer
    - Fixed undefined positions in a error when match a syntax to empty or white space only value
    - Improved `Lexer#checkStructure()`
        - Return a warning as an object with node reference and message
        - No exception on unknown node type, return a warning instead

## 1.0.0-alpha23 (September 10, 2017)

- Fixed `Tokenizer#getRawLength()`'s false positive balance match to the end of input in some cases (#56)
- Rename walker's entry point methods to be the same as CSSTree exposed methods (i.e. `walk()`, `walkUp()` etc)
- Rename at-rule's `expression` to `prelude` (since [spec names it so](https://www.w3.org/TR/css-syntax-3/#at-rule))
    - `AtruleExpression` node type → `AtrulePrelude`
    - `Atrule.expression` field → `Atrule.prelude`
    - `parseAtruleExpression` parser's option → `parseAtrulePrelude`
    - `atruleExpression` parse context → `atrulePrelude`
    - `atruleExpression` walk context reference → `atrulePrelude`

## 1.0.0-alpha22 (September 8, 2017)

- Parser
    - Fixed exception on parsing of unclosed `{}-block` in tolerant mode
    - Added tolerant mode support for `DeclarationList`
    - Added standalone entry point, i.e. default parser can be used via `require('css-tree/lib/parser')` (#47)
- Generator
    - Changed generator to produce `+n` when `AnPlusB.a` is `+1` to be "round-trip" with parser
    - Added standalone entry point, i.e. default generators can be used via `require('css-tree/lib/generator')`
- Walker
    - Added standalone entry point, i.e. default walkers can be used via `require('css-tree/lib/walker')` (#47)
- Lexer
    - Added `default` keyword to the list of invalid values for `<custom-ident>` (since it reversed per [spec](https://www.w3.org/TR/css-values/#custom-idents))
- Convertors (`toPlainObject()` and `fromPlainObject()`) moved to `lib/convertor` (entry point is `require('css-tree/lib/convertor')`)

## 1.0.0-alpha21 (September 5, 2017)

- Tokenizer
    - Added `Raw` token type
    - Improved tokenization of `url()` with raw as url to be more spec complient
    - Added `Tokenizer#balance` array computation on token layout
    - Added `Tokenizer#getRawLength()` to compute a raw length with respect of block balance
    - Added `Tokenizer#getTokenStart(offset)` method to get token start offset by token index
    - Added `idx` and `balance` fields to each token of `Tokenizer#dump()` method result
- Parser
    - Added `onParseError` option
    - Reworked node parsers that consume a `Raw` node to use a new approach. Since now a `Raw` node builds in `parser#Raw()` function only
    - Changed semantic of `parser#Raw()`, it takes 5 parameters now (it might to be changed in future)
    - Changed `parser#tolerantParse()` to pass a start token index to fallback function instead of source offset
    - Fixed `AtruleExpression` consuming in tolerant mode
    - Atrule handler to convert an empty `AtruleExpression` node into `null`
    - Changed `AtruleExpression` handler to always return a node (before it could return a `null` in some cases)
- Lexer
    - Fixed comma match node for `#` multiplier
    - Added reference name to `SyntaxReferenceError`
- Additional fixes on custom errors
- Reduced possible corruption of base config by `syntax.fork()`

## 1.0.0-alpha20 (August 28, 2017)

- Tokenizer
    - Added `Atrule` token type (`<at-rule-token>` per spec)
    - Added `Function` token type (`<function-token>` per spec)
    - Added `Url` token type
    - Replaced `Tokenizer#getTypes()` method with `Tokenizer#dump()` to get all tokens as an array
    - Renamed `Tokenizer.TYPE.Whitespace` to `Tokenizer.TYPE.WhiteSpace`
    - Renamed `Tokenizer.findWhitespaceEnd()` to `Tokenizer.findWhiteSpaceEnd()`
- Parser
    - Added initial implementation of tollerant mode (turn on by passing `tolerant: true` option). In this mode parse errors are never occour and any invalid part of CSS turns into a `Raw` node. Current safe points: `Atrule`, `AtruleExpression`, `Rule`, `Selector` and `Declaration`. Feature is experimental and further improvements are planned.
    - Changed `Atrule.expression` to contain a `AtruleExpression` node or `null` only (other node types is wrapping into a `AtruleExpression` node)
    - Renamed `AttributeSelector.operator` to `AttributeSelector.matcher`
- Generator
    - `translate()` method is now can take a function as second argument, that recieves every generated chunk. When no function is passed, default handler is used, it concats all the chunks and method returns a string.
- Lexer
    - Used [mdn/data](https://github.com/mdn/data) package as source of lexer's grammar instead of local dictionaries
    - Added `x` unit to `<resolution>` generic type
    - Improved match tree:
        - Omited Group (sequences) match nodes
        - Omited empty match nodes (for terms with `zero or more` multipliers)
        - Added `ASTNode` node type to contain a reference to AST node
        - Fixed node duplication (uncompleted match were added to tree)
        - Added AST node reference in match nodes
        - Added comma match node by `#` multiplier
    - Grammar
        - Changed `translate()` function to get a handler as third argument (optional). That handler recieves result of node traslation and can be used for decoration purposes. See [example](https://github.com/csstree/docs/blob/04c65af44477b5ea05feb373482898122b2a4528/docs/syntax.html#L619-L627)
        - Added `SyntaxParseError` to grammar export
        - Reworked group and multipliers representation in syntax tree:
            - Replaced `Sequence` for `Group` node type (`Sequence` node type removed)
            - Added `explicit` boolean property for `Group`
            - Only groups can have a multiplier now (other node types is wrapping into a single term implicit group when multiplier is applied)
            - Renamed `nonEmpty` Group's property to `disallowEmpty`
            - Added optimisation for syntax tree by dropping redundant root `Group` when it contains a single `Group` term (return this `Group` as a result)
    - Changed lexer's match functionality
        - Changed `Lexer#matchProperty()` and `Lexer#matchType()` to return an object instead of match tree. A match tree stores in `matched` field when AST is matched to grammar successfully, otherwise an error in `error` field. The result object also has some methods to test AST node against a match tree: `getTrace()`, `isType()`, `isProperty()` and `isKeyword()`
        - Added `Lexer#matchDeclaration()` method
        - Removed `Lexer#lastMatchError` (error stores in match result object in `error` field)
    - Added initial implementation of search for AST segments (new lexer methods: `Lexer#findValueSegments()`, `Lexer#findDeclarationValueSegments()` and `Lexer#findAllSegments`)
    - Implemented `SyntaxReferenceError` for unknown property and type references
- Renamed field in resulting object of `property()` function: `variable` → `custom`
- Fixed issue with readonly properties (e.g. `line` and `column`) of `Error` and exception on attempt to write in iOS Safari

## 1.0.0-alpha19 (April 24, 2017)

- Extended `List` class with new methods:
    - `List#prepend(item)`
    - `List#prependData(data)`
    - `List#insertData(data)`
    - `List#insertList(list)`
    - `List#replace(item, itemOrList)`

## 1.0.0-alpha18 (April 3, 2017)

- Added `atrule` walk context (#39)
- Changed a result of generate method for `AnPlusB`, `AttributeSelector`, `Function`, `MediaFeature` and `Ratio` ([1e95877](https://github.com/csstree/csstree/commit/1e9587710efa8e9338bcf0bc794b4b45f286231d))
- Fixed typo in `List` exception messages (@strarsis, #42)
- Improved tokenizer to convert an input to a string

## 1.0.0-alpha17 (March 13, 2017)

- Implemented new concept of `syntax`
    - Changed main `exports` to expose a default syntax
    - Defined initial [CSS syntax](lib/syntax/default.js)
    - Implemented `createSyntax()` method to create a new syntax from scratch
    - Implemented `fork()` method to create a new syntax based on given via extension
- Parser
    - Implemented `mediaQueryList` and `mediaQuery` parsing contexts
    - Implemented `CDO` and `CDC` node types
    - Implemented additional declaration property prefix hacks (`#` and `+`)
    - Added support for UTF-16LE BOM
    - Added support for `@font-face` at-rule
    - Added `chroma()` to legacy IE filter functions
    - Improved `HexColor` to consume hex only
    - Improved support for `\0` and `\9` hacks (#2)
    - Relaxed number check for `Ratio` terms
        - Allowed fractal values as a `Ratio` term
        - Disallowed zero number as a `Ratio` term
    - Changed important clause parsing
        - Allowed any identifier for important (to support hacks like `!ie`)
        - Store `true` for `important` field in case identifier equals to `important` and string otherwise
    - Fixed parse error formatted message rendering to take into account tabs
    - Removed exposing of `Parser` class
    - Removed `readSelectorSequence()`, `readSequenceFallback()` and `readSelectorSequenceFallback` methods
    - Used single universal sequence consumer for `AtruleExpression`, `Selector` and `Value`
- Generator
    - Reworked generator to use auto-generated functions based on syntax definition (additional work to be done in next releases)
    - Implemented `translateMarkup(ast, before, after)` method for complex cases
    - Reworked `translateWithSourceMap` to be more flexible (based on `translateMarkup`, additional work to be done in next releases)
- Walker
    - Reworked walker to use auto-generated function based on syntax definition (additional work to be done in next releases)
- Lexer
    - Prepared for better extensibility (additional work to be done in next releases)
    - Implemented `checkStructure(ast)` method to check AST structure based on syntax definition
    - Update syntax dictionaries to latest `mdn/data`
        - Add missing `<'offset-position'>` syntax
        - Extended `<position>` property with `-webkit-sticky` (@sergejmueller, #37)
    - Improved mismatch error position
- Implemented script (`gen:syntax`) to generate AST format reference page (`docs/ast.md`) using syntax definition

## 1.0.0-alpha16 (February 12, 2017)

- Exposed `Parser` class
- Added `startOffset` option to `Tokenizer` (constructor and `setSource()` method)
- Added fallback functions for default (`readSequenceFallback`) and selector (`readSelectorSequenceFallback`) sequence readers
- Fixed edge cases for `AnPlusB`
- Fixed wrong whitespace ignoring in `Selector` consumer

## 1.0.0-alpha15 (February 8, 2017)

- Fixed broken `atruleExpression` context
- Fixed vendor prefix detection in `keyword()` and `property()`
- Fixed `property()` to not lowercase custom property names
- Added `variable` boolean flag in `property()` result
- Renamed `scanner` into `tokenizer`
- Ranamed `syntax` into `lexer`
- Moved `docs/*.html` files to [csstree/docs](https://github.com/csstree/docs) repo
- Added `element()` function for `Value` context (`-moz-element()` supported as well)
- Merged `Universal` node type into `Type`
- Renamed node types:
    - `Id` -> `IdSelector`
    - `Class` -> `ClassSelector`
    - `Type` -> `TypeSelector`
    - `Attribute` -> `AttributeSelector`
    - `PseudoClass` -> `PseudoClassSelector`
    - `PseudoElement` -> `PseudoElementSelector`
    - `Hash` -> `HexColor`
    - `Space` -> `WhiteSpace`
    - `An+B` -> `AnPlusB`
- Removed `Progid` node type
- Relaxed `MediaQuery` consumer to not validate syntax on parse and to include whitespaces in children sequence as is
- Added `WhiteSpace.value` property to store whitespace sequence
- Implemented parser options to specify what should be parsed in details (when option is `false` some part of CSS represents as balanced `Raw`):
    - `parseAtruleExpression` – to parse at-rule expressions (`true` by default)
    - `parseSelector` – to parse rule's selector (`true` by default)
    - `parseValue` - to parse declaration's value (`true` by default)
    - `parseCustomProperty` – to parse value and fallback of custom property (`false` by default)
- Changed tokenization to stick leading hyphen minus to identifier token
- Changed selector parsing:
    - Don't convert spaces into descendant combinator
    - Don't validate selector structure on parsing (selectors may be checked by lexer later)
- Initial refactoring of [docs](https://github.com/csstree/csstree/blob/master/docs)
- Various improvements and fixes

## 1.0.0-alpha14 (February 3, 2017)

- Implemented `DeclarationList`, `MediaQueryList`, `MediaQuery`, `MediaFeature` and `Ratio` node types
- Implemented `declarationList` context (useful to parse HTML `style` attribute content)
- Implemented custom consumers for `@import`, `@media`, `@page` and `@supports` at-rules
- Implemented `atrule` option for `parse()` config, is used for `atruleExpession` context to specify custom consumer for at-rule if any
- Added `Scanner#skipWS()`, `Scanner#eatNonWS()`, `Scanner#consume()` and `Scanner#consumeNonWS()` helper methods
- Added custom consumers for known functional-pseudos, consume unknown functional-pseudo content as balanced `Raw`
- Allowed any `PseudoElement` to be a functional-pseudo (#33)
- Improved walker implementations to reduce GC thrashing by reusing cursors
- Changed `Atrule.block` to contain a `Block` node type only if any
- Changed `Block.loc` positions to include curly brackets
- Changed `Atrule.expression` to store a `null` if no expression
- Changed parser to use `StyleSheet` node type only for top level node (when context is `stylesheet`, that's by default)
- Changed `Parentheses`, `Brackets` and `Function` consumers to use passed sequence reader instead of its own
- Changed `Value` and `AtruleExpression` consumers to use common sequence reader (that reader was used by `Value` consumer before)
- Changed default sequence reader to exclude storage of spaces around `Comma`
- Changed processing of custom properties:
    - Consume declaration value as balanced `Raw`
    - Consume `var()` fallback value as balanced `Raw`
    - Validate first argument of `var()` starts with double dash
    - Custom property's value and fallback includes spaces around
- Fixed `Nth` to have a `loc` property
- Fixed `SelectorList.loc` and `Selector.loc` positions to exclude spaces
- Fixed issue Browserify build fail with `default-syntax.json` is not found error (#32, @philschatz)
- Disallowed `Type` selector starting with dash (parser throws an error in this case now)
- Disallowed empty selectors for `Rule` (not sure if it's correct but looks reasonable)
- Removed `>>` combinator support until any browser support (no signals about that yet)
- Removed `PseudoElement.legacy` property
- Removed special case for `:before`, `:after`, `:first-letter` and `:first-line` to represent them as `PseudoElement`, now those pseudos are represented as `PseudoClass` nodes
- Removed deprecated `Syntax#match()` method
- Parser was splitted into modules and related changes, one step closer to an extensible parser
- Various fixes and improvements, all changes have negligible impact on performance

## 1.0.0-alpha13 (January 19, 2017)

- Changed location storing in `SyntaxMatchError`
    - Changed property to store mismatch offset to `mismatchOffset`
    - Changed `offset` property to store bad node offset in source CSS if any
    - Added `loc` property that stores bad node `loc` if any

## 1.0.0-alpha12 (January 19, 2017)

- Fixed `Syntax#matchProperty()` method to always return a positive result for custom properties since syntax is never defined for them (#31)
- Implemented `fromPlainObject()` and `toPlainObject()` to convert plain object to AST or AST to plain object (currently converts `List` <-> `Array`)

## 1.0.0-alpha11 (January 18, 2017)

- Added support for `:matches(<selector-list>)` (#28)
- Added support for `:has(<relative-selector-list>)`
- Added support for `::slotted(<compound-selector>)`
- Implemented `Brackets` node type
- Implemented basic support for at-rule inside rule block (#24)
- Renamed `Selector` node type to `SelectorList`
- Renamed `SimpleSelector` node type to `Selector`
- Renamed `UnicodeRange.name` property to `UnicodeRange.value`
- Replaced `Negation` node type for regular `PseudoClass`
- Unified name of node property to store nested nodes, it always `children` now:
    - `StyleSheet.rules` -> `StyleSheet.children`
    - `SelectorList.selectors` -> `SelectorList.children`
    - `Block.declarations` -> `Block.children`
    - `*.sequence` -> `*.children`
- Fixed edge cases in parsing `Hex` and `UnicodeRange` when number not an integer
- Changed `nth-` pseudos parsing
    - Implemented `An+B` node type to represent expressions like `2n + 1` or `-3n`
    - Fixed edge cases when `a` or `b` is not an integer
    - Changed `odd` and `even` keywords processing, keywords are storing as `Identifier` node type now
    - Changed `Nth` node type format to store a `nth`-query and an optional `selector`
    - Implemented `of` clause for `nth-` pseudos (a.e. `:nth-child(2n + 1 of li, img)`)
    - Limited `Nth` parsing rules to `:nth-child()`, `:nth-last-child()`, `:nth-of-type()` and `:nth-last-of-type()` pseudos
- Changed the way to store locations
    - Renamed `info` node property to `loc`
    - Changed format of `loc` to store `start` and `end` positions

## 1.0.0-alpha10 (January 11, 2017)

- Reworked `Scanner` to be a single point to its functionality
- Exposed `Scanner` class to be useful for external projects
- Changed `walk()` function behaviour to traverse AST nodes in natural order
- Implemented `walkUp()` function to traverse AST nodes from deepest to parent (behaves as `walk()` before)

## 1.0.0-alpha9 (December 21, 2016)

- Fixed `<angle>` generic according to specs that allow a `<number>` equals to zero to be used as valid value (#30)

## 1.0.0-alpha8 (November 11, 2016)

- Fixed `Scanner#skip()` issue method when cursor is moving to the end of source
- Simplified `Progid` node
- Changed behaviour for bad selector processing, now parsing fails instead of selector ignoring
- Fixed `<id-selector>` generic syntax
- Added `q` unit for `<length>` generic syntax
- Refactored syntax parser (performance)
- Reduced startup time by implementing lazy syntax parsing (default syntax doesn't parse on module load)
- Updated syntax dictionaries and used [`mdn/data`](https://github.com/mdn/data) instead of `Template:CSSData`
- Renamed `syntax.stringify()` method to `syntax.translate()`
- Simplified generic syntax functions, those functions receive a single AST node for checking and should return `true` or `false`
- Added exception for values that contains `var()`, those values are always valid for now
- Added more tests and increase code coverage to `98.5%`

## 1.0.0-alpha7 (October 7, 2016)

- Added support for explicit descendant combinator (`>>`)
- Implemented `Type` and `Universal` type nodes
- Improved `Number` parsing by including sign and exponent (#26)
- Parse `before`, `after`, `first-letter` and `first-line` pseudos with single colon as `PseudoElement`
- Changed `FunctionalPseudo` node type to `PseudoClass`
- Fixed attribute selector name parsing (namespace edge cases)
- Fixed location calculation for specified offset when `eof` is reached
- Added more non-standard colors (#25)
- Removed obsolete `Syntax#getAll()` method
- Fixed various edge cases, code clean up and performance improvements

## 1.0.0-alpha6 (September 23, 2016)

- More accurate positions for syntax mismatch errors
- Added [`apple`](https://webkit.org/blog/3709/using-the-system-font-in-web-content/) specific font keywords (#20)
- Changed `Property` node stucture from object to string
- Renamed `Ruleset` node type to `Rule`
- Removed `Argument` node type
- Fixed `Dimension` and `Percentage` position computation
- Fixed bad selector parsing (temporary solution)
- Fixed location computation for CSS with very long lines that may lead to really long parsing with `positions:true` (even freeze)
- Fixed `line` and `column` computation for `SyntaxMatch` error
- Improved performance of parsing and translation. Now CSSTree is under 10ms in [PostCSS benchmark](https://github.com/postcss/benchmark).


code:
<img align="right" width="111" height="111"
     alt="CSSTree logo"
     src="https://cloud.githubusercontent.com/assets/270491/19243723/6f9136c6-8f21-11e6-82ac-eeeee4c6c452.png"/>

# CSSTree

[![NPM version](https://img.shields.io/npm/v/css-tree.svg)](https://www.npmjs.com/package/css-tree)
[![Build Status](https://travis-ci.org/csstree/csstree.svg?branch=master)](https://travis-ci.org/csstree/csstree)
[![Coverage Status](https://coveralls.io/repos/github/csstree/csstree/badge.svg?branch=master)](https://coveralls.io/github/csstree/csstree?branch=master)
[![NPM Downloads](https://img.shields.io/npm/dm/css-tree.svg)](https://www.npmjs.com/package/css-tree)
[![Twitter](https://img.shields.io/badge/Twitter-@csstree-blue.svg)](https://twitter.com/csstree)

CSSTree is a tool set for CSS: [fast](https://github.com/postcss/benchmark) detailed parser (CSS → AST), walker (AST traversal), generator (AST → CSS) and lexer (validation and matching) based on specs and browser implementations. The main goal is to be efficient and W3C specs compliant, with focus on CSS analyzing and source-to-source transforming tasks.

> NOTE: The library isn't in final shape and needs further improvements (e.g. AST format and API are subjects to change in next major versions). However it's stable enough and used by projects like [CSSO](https://github.com/css/csso) (CSS minifier) and [SVGO](https://github.com/svg/svgo) (SVG optimizer) in production.

## Features

- **Detailed parsing with an adjustable level of detail**

  By default CSSTree parses CSS as detailed as possible, i.e. each single logical part is representing with its own AST node (see [AST format](docs/ast.md) for all possible node types). The parsing detail level can be changed through [parser options](docs/parsing.md#parsesource-options), for example, you can disable parsing of selectors or declaration values for component parts.

- **Tolerant to errors by design**

  Parser behaves as [spec says](https://www.w3.org/TR/css-syntax-3/#error-handling): "When errors occur in CSS, the parser attempts to recover gracefully, throwing away only the minimum amount of content before returning to parsing as normal". The only thing the parser departs from the specification is that it doesn't throw away bad content, but wraps it in a special node type (`Raw`) that allows processing it later.

- **Fast and efficient**

  CSSTree is created with focus on performance and effective memory consumption. Therefore it's [one of the fastest CSS parsers](https://github.com/postcss/benchmark) at the moment.

- **Syntax validation**

  The build-in lexer can test CSS against syntaxes defined by W3C. CSSTree uses [mdn/data](https://github.com/mdn/data/) as a basis for lexer's dictionaries and extends it with vendor specific and legacy syntaxes. Lexer can only check the declaration values currently, but this feature will be extended to other parts of the CSS in the future.

## Documentation

- [AST format](docs/ast.md)
- [Parsing CSS → AST](docs/parsing.md)
  - [parse(source[, options])](docs/parsing.md#parsesource-options)
- [Serialization AST → CSS](docs/generate.md)
  - [generate(ast[, options])](docs/generate.md#generateast-options)
- [AST traversal](docs/traversal.md)
  - [walk(ast, options)](docs/traversal.md#walkast-options)
  - [find(ast, fn)](docs/traversal.md#findast-fn)
  - [findLast(ast, fn)](docs/traversal.md#findlastast-fn)
  - [findAll(ast, fn)](docs/traversal.md#findallast-fn)
- [Utils for AST](docs/utils.md)
  - [property(name)](docs/utils.md#propertyname)
  - [keyword(name)](docs/utils.md#keywordname)
  - [clone(ast)](docs/utils.md#cloneast)
  - [fromPlainObject(object)](docs/utils.md#fromplainobjectobject)
  - [toPlainObject(ast)](docs/utils.md#toplainobjectast)
- [Value Definition Syntax](docs/definition-syntax.md)
  - [parse(source)](docs/definition-syntax.md#parsesource)
  - [walk(node, options, context)](docs/definition-syntax.md#walknode-options-context)
  - [generate(node, options)](docs/definition-syntax.md#generatenode-options)
  - [AST format](docs/definition-syntax.md#ast-format)

## Tools

* [AST Explorer](https://astexplorer.net/#/gist/244e2fb4da940df52bf0f4b94277db44/e79aff44611020b22cfd9708f3a99ce09b7d67a8) – explore CSSTree AST format with zero setup
* [CSS syntax reference](https://csstree.github.io/docs/syntax.html)
* [CSS syntax validator](https://csstree.github.io/docs/validator.html)

## Related projects

* [csstree-validator](https://github.com/csstree/validator) – NPM package to validate CSS
* [stylelint-csstree-validator](https://github.com/csstree/stylelint-validator) – plugin for stylelint to validate CSS
* [Grunt plugin](https://github.com/sergejmueller/grunt-csstree-validator)
* [Gulp plugin](https://github.com/csstree/gulp-csstree)
* [Sublime plugin](https://github.com/csstree/SublimeLinter-contrib-csstree)
* [VS Code plugin](https://github.com/csstree/vscode-plugin)
* [Atom plugin](https://github.com/csstree/atom-plugin)

## Usage

Install with npm:

```
> npm install css-tree
```

Basic usage:

```js
var csstree = require('css-tree');

// parse CSS to AST
var ast = csstree.parse('.example { world: "!" }');

// traverse AST and modify it
csstree.walk(ast, function(node) {
    if (node.type === 'ClassSelector' && node.name === 'example') {
        node.name = 'hello';
    }
});

// generate CSS from AST
console.log(csstree.generate(ast));
// .hello{world:"!"}
```

Syntax matching:

```js
// parse CSS to AST as a declaration value
var ast = csstree.parse('red 1px solid', { context: 'value' });

// match to syntax of `border` property
var matchResult = csstree.lexer.matchProperty('border', ast);

// check first value node is a <color>
console.log(matchResult.isType(ast.children.first(), 'color'));
// true

// get a type list matched to a node
console.log(matchResult.getTrace(ast.children.first()));
// [ { type: 'Property', name: 'border' },
//   { type: 'Type', name: 'color' },
//   { type: 'Type', name: 'named-color' },
//   { type: 'Keyword', name: 'red' } ]
```

## Top level API

![API map](https://cdn.rawgit.com/csstree/csstree/1.0/docs/api-map.svg)

## License

MIT

license: mit


code:
const mdnAtrules = require('mdn-data/css/at-rules.json');
const mdnProperties = require('mdn-data/css/properties.json');
const mdnSyntaxes = require('mdn-data/css/syntaxes.json');
const patch = require('./patch.json');
const extendSyntax = /^\s*\|\s*/;

function preprocessAtrules(dict) {
    const result = Object.create(null);

    for (const atruleName in dict) {
        const atrule = dict[atruleName];
        let descriptors = null;

        if (atrule.descriptors) {
            descriptors = Object.create(null);

            for (const descriptor in atrule.descriptors) {
                descriptors[descriptor] = atrule.descriptors[descriptor].syntax;
            }
        }

        result[atruleName.substr(1)] = {
            prelude: atrule.syntax.trim().match(/^@\S+\s+([^;\{]*)/)[1].trim() || null,
            descriptors
        };
    }

    return result;
}

function patchDictionary(dict, patchDict) {
    const result = {};

    // copy all syntaxes for an original dict
    for (const key in dict) {
        result[key] = dict[key].syntax || dict[key];
    }

    // apply a patch
    for (const key in patchDict) {
        if (key in dict) {
            if (patchDict[key].syntax) {
                result[key] = extendSyntax.test(patchDict[key].syntax)
                    ? result[key] + ' ' + patchDict[key].syntax.trim()
                    : patchDict[key].syntax;
            } else {
                delete result[key];
            }
        } else {
            if (patchDict[key].syntax) {
                result[key] = patchDict[key].syntax.replace(extendSyntax, '');
            }
        }
    }

    return result;
}

function unpackSyntaxes(dict) {
    const result = {};

    for (const key in dict) {
        result[key] = dict[key].syntax;
    }

    return result;
}

function patchAtrules(dict, patchDict) {
    const result = {};

    // copy all syntaxes for an original dict
    for (const key in dict) {
        const patchDescriptors = (patchDict[key] && patchDict[key].descriptors) || null;

        result[key] = {
            prelude: key in patchDict && 'prelude' in patchDict[key]
                ? patchDict[key].prelude
                : dict[key].prelude || null,
            descriptors: dict[key].descriptors
                ? patchDictionary(dict[key].descriptors, patchDescriptors || {})
                : patchDescriptors && unpackSyntaxes(patchDescriptors)
        };
    }

    // apply a patch
    for (const key in patchDict) {
        if (!hasOwnProperty.call(dict, key)) {
            result[key] = {
                prelude: patchDict[key].prelude || null,
                descriptors: patchDict[key].descriptors && unpackSyntaxes(patchDict[key].descriptors)
            };
        }
    }

    return result;
}

module.exports = {
    types: patchDictionary(mdnSyntaxes, patch.syntaxes),
    atrules: patchAtrules(preprocessAtrules(mdnAtrules), patch.atrules),
    properties: patchDictionary(mdnProperties, patch.properties)
};


code:
//
//                              list
//                            ┌──────┐
//             ┌──────────────┼─head │
//             │              │ tail─┼──────────────┐
//             │              └──────┘              │
//             ▼                                    ▼
//            item        item        item        item
//          ┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
//  null ◀──┼─prev │◀───┼─prev │◀───┼─prev │◀───┼─prev │
//          │ next─┼───▶│ next─┼───▶│ next─┼───▶│ next─┼──▶ null
//          ├──────┤    ├──────┤    ├──────┤    ├──────┤
//          │ data │    │ data │    │ data │    │ data │
//          └──────┘    └──────┘    └──────┘    └──────┘
//

function createItem(data) {
    return {
        prev: null,
        next: null,
        data: data
    };
}

function allocateCursor(node, prev, next) {
    var cursor;

    if (cursors !== null) {
        cursor = cursors;
        cursors = cursors.cursor;
        cursor.prev = prev;
        cursor.next = next;
        cursor.cursor = node.cursor;
    } else {
        cursor = {
            prev: prev,
            next: next,
            cursor: node.cursor
        };
    }

    node.cursor = cursor;

    return cursor;
}

function releaseCursor(node) {
    var cursor = node.cursor;

    node.cursor = cursor.cursor;
    cursor.prev = null;
    cursor.next = null;
    cursor.cursor = cursors;
    cursors = cursor;
}

var cursors = null;
var List = function() {
    this.cursor = null;
    this.head = null;
    this.tail = null;
};

List.createItem = createItem;
List.prototype.createItem = createItem;

List.prototype.updateCursors = function(prevOld, prevNew, nextOld, nextNew) {
    var cursor = this.cursor;

    while (cursor !== null) {
        if (cursor.prev === prevOld) {
            cursor.prev = prevNew;
        }

        if (cursor.next === nextOld) {
            cursor.next = nextNew;
        }

        cursor = cursor.cursor;
    }
};

List.prototype.getSize = function() {
    var size = 0;
    var cursor = this.head;

    while (cursor) {
        size++;
        cursor = cursor.next;
    }

    return size;
};

List.prototype.fromArray = function(array) {
    var cursor = null;

    this.head = null;

    for (var i = 0; i < array.length; i++) {
        var item = createItem(array[i]);

        if (cursor !== null) {
            cursor.next = item;
        } else {
            this.head = item;
        }

        item.prev = cursor;
        cursor = item;
    }

    this.tail = cursor;

    return this;
};

List.prototype.toArray = function() {
    var cursor = this.head;
    var result = [];

    while (cursor) {
        result.push(cursor.data);
        cursor = cursor.next;
    }

    return result;
};

List.prototype.toJSON = List.prototype.toArray;

List.prototype.isEmpty = function() {
    return this.head === null;
};

List.prototype.first = function() {
    return this.head && this.head.data;
};

List.prototype.last = function() {
    return this.tail && this.tail.data;
};

List.prototype.each = function(fn, context) {
    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, null, this.head);

    while (cursor.next !== null) {
        item = cursor.next;
        cursor.next = item.next;

        fn.call(context, item.data, item, this);
    }

    // pop cursor
    releaseCursor(this);
};

List.prototype.forEach = List.prototype.each;

List.prototype.eachRight = function(fn, context) {
    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, this.tail, null);

    while (cursor.prev !== null) {
        item = cursor.prev;
        cursor.prev = item.prev;

        fn.call(context, item.data, item, this);
    }

    // pop cursor
    releaseCursor(this);
};

List.prototype.forEachRight = List.prototype.eachRight;

List.prototype.reduce = function(fn, initialValue, context) {
    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, null, this.head);
    var acc = initialValue;

    while (cursor.next !== null) {
        item = cursor.next;
        cursor.next = item.next;

        acc = fn.call(context, acc, item.data, item, this);
    }

    // pop cursor
    releaseCursor(this);

    return acc;
};

List.prototype.reduceRight = function(fn, initialValue, context) {
    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, this.tail, null);
    var acc = initialValue;

    while (cursor.prev !== null) {
        item = cursor.prev;
        cursor.prev = item.prev;

        acc = fn.call(context, acc, item.data, item, this);
    }

    // pop cursor
    releaseCursor(this);

    return acc;
};

List.prototype.nextUntil = function(start, fn, context) {
    if (start === null) {
        return;
    }

    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, null, start);

    while (cursor.next !== null) {
        item = cursor.next;
        cursor.next = item.next;

        if (fn.call(context, item.data, item, this)) {
            break;
        }
    }

    // pop cursor
    releaseCursor(this);
};

List.prototype.prevUntil = function(start, fn, context) {
    if (start === null) {
        return;
    }

    var item;

    if (context === undefined) {
        context = this;
    }

    // push cursor
    var cursor = allocateCursor(this, start, null);

    while (cursor.prev !== null) {
        item = cursor.prev;
        cursor.prev = item.prev;

        if (fn.call(context, item.data, item, this)) {
            break;
        }
    }

    // pop cursor
    releaseCursor(this);
};

List.prototype.some = function(fn, context) {
    var cursor = this.head;

    if (context === undefined) {
        context = this;
    }

    while (cursor !== null) {
        if (fn.call(context, cursor.data, cursor, this)) {
            return true;
        }

        cursor = cursor.next;
    }

    return false;
};

List.prototype.map = function(fn, context) {
    var result = new List();
    var cursor = this.head;

    if (context === undefined) {
        context = this;
    }

    while (cursor !== null) {
        result.appendData(fn.call(context, cursor.data, cursor, this));
        cursor = cursor.next;
    }

    return result;
};

List.prototype.filter = function(fn, context) {
    var result = new List();
    var cursor = this.head;

    if (context === undefined) {
        context = this;
    }

    while (cursor !== null) {
        if (fn.call(context, cursor.data, cursor, this)) {
            result.appendData(cursor.data);
        }
        cursor = cursor.next;
    }

    return result;
};

List.prototype.clear = function() {
    this.head = null;
    this.tail = null;
};

List.prototype.copy = function() {
    var result = new List();
    var cursor = this.head;

    while (cursor !== null) {
        result.insert(createItem(cursor.data));
        cursor = cursor.next;
    }

    return result;
};

List.prototype.prepend = function(item) {
    //      head
    //    ^
    // item
    this.updateCursors(null, item, this.head, item);

    // insert to the beginning of the list
    if (this.head !== null) {
        // new item <- first item
        this.head.prev = item;

        // new item -> first item
        item.next = this.head;
    } else {
        // if list has no head, then it also has no tail
        // in this case tail points to the new item
        this.tail = item;
    }

    // head always points to new item
    this.head = item;

    return this;
};

List.prototype.prependData = function(data) {
    return this.prepend(createItem(data));
};

List.prototype.append = function(item) {
    return this.insert(item);
};

List.prototype.appendData = function(data) {
    return this.insert(createItem(data));
};

List.prototype.insert = function(item, before) {
    if (before !== undefined && before !== null) {
        // prev   before
        //      ^
        //     item
        this.updateCursors(before.prev, item, before, item);

        if (before.prev === null) {
            // insert to the beginning of list
            if (this.head !== before) {
                throw new Error('before doesn\'t belong to list');
            }

            // since head points to before therefore list doesn't empty
            // no need to check tail
            this.head = item;
            before.prev = item;
            item.next = before;

            this.updateCursors(null, item);
        } else {

            // insert between two items
            before.prev.next = item;
            item.prev = before.prev;

            before.prev = item;
            item.next = before;
        }
    } else {
        // tail
        //      ^
        //      item
        this.updateCursors(this.tail, item, null, item);

        // insert to the ending of the list
        if (this.tail !== null) {
            // last item -> new item
            this.tail.next = item;

            // last item <- new item
            item.prev = this.tail;
        } else {
            // if list has no tail, then it also has no head
            // in this case head points to new item
            this.head = item;
        }

        // tail always points to new item
        this.tail = item;
    }

    return this;
};

List.prototype.insertData = function(data, before) {
    return this.insert(createItem(data), before);
};

List.prototype.remove = function(item) {
    //      item
    //       ^
    // prev     next
    this.updateCursors(item, item.prev, item, item.next);

    if (item.prev !== null) {
        item.prev.next = item.next;
    } else {
        if (this.head !== item) {
            throw new Error('item doesn\'t belong to list');
        }

        this.head = item.next;
    }

    if (item.next !== null) {
        item.next.prev = item.prev;
    } else {
        if (this.tail !== item) {
            throw new Error('item doesn\'t belong to list');
        }

        this.tail = item.prev;
    }

    item.prev = null;
    item.next = null;

    return item;
};

List.prototype.push = function(data) {
    this.insert(createItem(data));
};

List.prototype.pop = function() {
    if (this.tail !== null) {
        return this.remove(this.tail);
    }
};

List.prototype.unshift = function(data) {
    this.prepend(createItem(data));
};

List.prototype.shift = function() {
    if (this.head !== null) {
        return this.remove(this.head);
    }
};

List.prototype.prependList = function(list) {
    return this.insertList(list, this.head);
};

List.prototype.appendList = function(list) {
    return this.insertList(list);
};

List.prototype.insertList = function(list, before) {
    // ignore empty lists
    if (list.head === null) {
        return this;
    }

    if (before !== undefined && before !== null) {
        this.updateCursors(before.prev, list.tail, before, list.head);

        // insert in the middle of dist list
        if (before.prev !== null) {
            // before.prev <-> list.head
            before.prev.next = list.head;
            list.head.prev = before.prev;
        } else {
            this.head = list.head;
        }

        before.prev = list.tail;
        list.tail.next = before;
    } else {
        this.updateCursors(this.tail, list.tail, null, list.head);

        // insert to end of the list
        if (this.tail !== null) {
            // if destination list has a tail, then it also has a head,
            // but head doesn't change

            // dest tail -> source head
            this.tail.next = list.head;

            // dest tail <- source head
            list.head.prev = this.tail;
        } else {
            // if list has no a tail, then it also has no a head
            // in this case points head to new item
            this.head = list.head;
        }

        // tail always start point to new item
        this.tail = list.tail;
    }

    list.head = null;
    list.tail = null;

    return this;
};

List.prototype.replace = function(oldItem, newItemOrList) {
    if ('head' in newItemOrList) {
        this.insertList(newItemOrList, oldItem);
    } else {
        this.insert(newItemOrList, oldItem);
    }

    this.remove(oldItem);
};

module.exports = List;


code:
var adoptBuffer = require('./adopt-buffer');
var isBOM = require('../tokenizer').isBOM;

var N = 10;
var F = 12;
var R = 13;

function computeLinesAndColumns(host, source) {
    var sourceLength = source.length;
    var lines = adoptBuffer(host.lines, sourceLength); // +1
    var line = host.startLine;
    var columns = adoptBuffer(host.columns, sourceLength);
    var column = host.startColumn;
    var startOffset = source.length > 0 ? isBOM(source.charCodeAt(0)) : 0;

    for (var i = startOffset; i < sourceLength; i++) { // -1
        var code = source.charCodeAt(i);

        lines[i] = line;
        columns[i] = column++;

        if (code === N || code === R || code === F) {
            if (code === R && i + 1 < sourceLength && source.charCodeAt(i + 1) === N) {
                i++;
                lines[i] = line;
                columns[i] = column;
            }

            line++;
            column = 1;
        }
    }

    lines[i] = line;
    columns[i] = column;

    host.lines = lines;
    host.columns = columns;
}

var OffsetToLocation = function() {
    this.lines = null;
    this.columns = null;
    this.linesAndColumnsComputed = false;
};

OffsetToLocation.prototype = {
    setSource: function(source, startOffset, startLine, startColumn) {
        this.source = source;
        this.startOffset = typeof startOffset === 'undefined' ? 0 : startOffset;
        this.startLine = typeof startLine === 'undefined' ? 1 : startLine;
        this.startColumn = typeof startColumn === 'undefined' ? 1 : startColumn;
        this.linesAndColumnsComputed = false;
    },

    ensureLinesAndColumnsComputed: function() {
        if (!this.linesAndColumnsComputed) {
            computeLinesAndColumns(this, this.source);
            this.linesAndColumnsComputed = true;
        }
    },
    getLocation: function(offset, filename) {
        this.ensureLinesAndColumnsComputed();

        return {
            source: filename,
            offset: this.startOffset + offset,
            line: this.lines[offset],
            column: this.columns[offset]
        };
    },
    getLocationRange: function(start, end, filename) {
        this.ensureLinesAndColumnsComputed();

        return {
            source: filename,
            start: {
                offset: this.startOffset + start,
                line: this.lines[start],
                column: this.columns[start]
            },
            end: {
                offset: this.startOffset + end,
                line: this.lines[end],
                column: this.columns[end]
            }
        };
    }
};

module.exports = OffsetToLocation;


code:
var createCustomError = require('../utils/createCustomError');
var MAX_LINE_LENGTH = 100;
var OFFSET_CORRECTION = 60;
var TAB_REPLACEMENT = '    ';

function sourceFragment(error, extraLines) {
    function processLines(start, end) {
        return lines.slice(start, end).map(function(line, idx) {
            var num = String(start + idx + 1);

            while (num.length < maxNumLength) {
                num = ' ' + num;
            }

            return num + ' |' + line;
        }).join('\n');
    }

    var lines = error.source.split(/\r\n?|\n|\f/);
    var line = error.line;
    var column = error.column;
    var startLine = Math.max(1, line - extraLines) - 1;
    var endLine = Math.min(line + extraLines, lines.length + 1);
    var maxNumLength = Math.max(4, String(endLine).length) + 1;
    var cutLeft = 0;

    // column correction according to replaced tab before column
    column += (TAB_REPLACEMENT.length - 1) * (lines[line - 1].substr(0, column - 1).match(/\t/g) || []).length;

    if (column > MAX_LINE_LENGTH) {
        cutLeft = column - OFFSET_CORRECTION + 3;
        column = OFFSET_CORRECTION - 2;
    }

    for (var i = startLine; i <= endLine; i++) {
        if (i >= 0 && i < lines.length) {
            lines[i] = lines[i].replace(/\t/g, TAB_REPLACEMENT);
            lines[i] =
                (cutLeft > 0 && lines[i].length > cutLeft ? '\u2026' : '') +
                lines[i].substr(cutLeft, MAX_LINE_LENGTH - 2) +
                (lines[i].length > cutLeft + MAX_LINE_LENGTH - 1 ? '\u2026' : '');
        }
    }

    return [
        processLines(startLine, line),
        new Array(column + maxNumLength + 2).join('-') + '^',
        processLines(line, endLine)
    ].filter(Boolean).join('\n');
}

var SyntaxError = function(message, source, offset, line, column) {
    var error = createCustomError('SyntaxError', message);

    error.source = source;
    error.offset = offset;
    error.line = line;
    error.column = column;

    error.sourceFragment = function(extraLines) {
        return sourceFragment(error, isNaN(extraLines) ? 0 : extraLines);
    };
    Object.defineProperty(error, 'formattedMessage', {
        get: function() {
            return (
                'Parse error: ' + error.message + '\n' +
                sourceFragment(error, 2)
            );
        }
    });

    // for backward capability
    error.parseError = {
        offset: offset,
        line: line,
        column: column
    };

    return error;
};

module.exports = SyntaxError;


code:
var constants = require('../tokenizer/const');
var TYPE = constants.TYPE;
var NAME = constants.NAME;

var utils = require('../tokenizer/utils');
var cmpStr = utils.cmpStr;

var EOF = TYPE.EOF;
var WHITESPACE = TYPE.WhiteSpace;
var COMMENT = TYPE.Comment;

var OFFSET_MASK = 0x00FFFFFF;
var TYPE_SHIFT = 24;

var TokenStream = function() {
    this.offsetAndType = null;
    this.balance = null;

    this.reset();
};

TokenStream.prototype = {
    reset: function() {
        this.eof = false;
        this.tokenIndex = -1;
        this.tokenType = 0;
        this.tokenStart = this.firstCharOffset;
        this.tokenEnd = this.firstCharOffset;
    },

    lookupType: function(offset) {
        offset += this.tokenIndex;

        if (offset < this.tokenCount) {
            return this.offsetAndType[offset] >> TYPE_SHIFT;
        }

        return EOF;
    },
    lookupOffset: function(offset) {
        offset += this.tokenIndex;

        if (offset < this.tokenCount) {
            return this.offsetAndType[offset - 1] & OFFSET_MASK;
        }

        return this.source.length;
    },
    lookupValue: function(offset, referenceStr) {
        offset += this.tokenIndex;

        if (offset < this.tokenCount) {
            return cmpStr(
                this.source,
                this.offsetAndType[offset - 1] & OFFSET_MASK,
                this.offsetAndType[offset] & OFFSET_MASK,
                referenceStr
            );
        }

        return false;
    },
    getTokenStart: function(tokenIndex) {
        if (tokenIndex === this.tokenIndex) {
            return this.tokenStart;
        }

        if (tokenIndex > 0) {
            return tokenIndex < this.tokenCount
                ? this.offsetAndType[tokenIndex - 1] & OFFSET_MASK
                : this.offsetAndType[this.tokenCount] & OFFSET_MASK;
        }

        return this.firstCharOffset;
    },

    // TODO: -> skipUntilBalanced
    getRawLength: function(startToken, mode) {
        var cursor = startToken;
        var balanceEnd;
        var offset = this.offsetAndType[Math.max(cursor - 1, 0)] & OFFSET_MASK;
        var type;

        loop:
        for (; cursor < this.tokenCount; cursor++) {
            balanceEnd = this.balance[cursor];

            // stop scanning on balance edge that points to offset before start token
            if (balanceEnd < startToken) {
                break loop;
            }

            type = this.offsetAndType[cursor] >> TYPE_SHIFT;

            // check token is stop type
            switch (mode(type, this.source, offset)) {
                case 1:
                    break loop;

                case 2:
                    cursor++;
                    break loop;

                default:
                    // fast forward to the end of balanced block
                    if (this.balance[balanceEnd] === cursor) {
                        cursor = balanceEnd;
                    }

                    offset = this.offsetAndType[cursor] & OFFSET_MASK;
            }
        }

        return cursor - this.tokenIndex;
    },
    isBalanceEdge: function(pos) {
        return this.balance[this.tokenIndex] < pos;
    },
    isDelim: function(code, offset) {
        if (offset) {
            return (
                this.lookupType(offset) === TYPE.Delim &&
                this.source.charCodeAt(this.lookupOffset(offset)) === code
            );
        }

        return (
            this.tokenType === TYPE.Delim &&
            this.source.charCodeAt(this.tokenStart) === code
        );
    },

    getTokenValue: function() {
        return this.source.substring(this.tokenStart, this.tokenEnd);
    },
    getTokenLength: function() {
        return this.tokenEnd - this.tokenStart;
    },
    substrToCursor: function(start) {
        return this.source.substring(start, this.tokenStart);
    },

    skipWS: function() {
        for (var i = this.tokenIndex, skipTokenCount = 0; i < this.tokenCount; i++, skipTokenCount++) {
            if ((this.offsetAndType[i] >> TYPE_SHIFT) !== WHITESPACE) {
                break;
            }
        }

        if (skipTokenCount > 0) {
            this.skip(skipTokenCount);
        }
    },
    skipSC: function() {
        while (this.tokenType === WHITESPACE || this.tokenType === COMMENT) {
            this.next();
        }
    },
    skip: function(tokenCount) {
        var next = this.tokenIndex + tokenCount;

        if (next < this.tokenCount) {
            this.tokenIndex = next;
            this.tokenStart = this.offsetAndType[next - 1] & OFFSET_MASK;
            next = this.offsetAndType[next];
            this.tokenType = next >> TYPE_SHIFT;
            this.tokenEnd = next & OFFSET_MASK;
        } else {
            this.tokenIndex = this.tokenCount;
            this.next();
        }
    },
    next: function() {
        var next = this.tokenIndex + 1;

        if (next < this.tokenCount) {
            this.tokenIndex = next;
            this.tokenStart = this.tokenEnd;
            next = this.offsetAndType[next];
            this.tokenType = next >> TYPE_SHIFT;
            this.tokenEnd = next & OFFSET_MASK;
        } else {
            this.tokenIndex = this.tokenCount;
            this.eof = true;
            this.tokenType = EOF;
            this.tokenStart = this.tokenEnd = this.source.length;
        }
    },

    forEachToken(fn) {
        for (var i = 0, offset = this.firstCharOffset; i < this.tokenCount; i++) {
            var start = offset;
            var item = this.offsetAndType[i];
            var end = item & OFFSET_MASK;
            var type = item >> TYPE_SHIFT;

            offset = end;

            fn(type, start, end, i);
        }
    },

    dump() {
        var tokens = new Array(this.tokenCount);

        this.forEachToken((type, start, end, index) => {
            tokens[index] = {
                idx: index,
                type: NAME[type],
                chunk: this.source.substring(start, end),
                balance: this.balance[index]
            };
        });

        return tokens;
    }
};

module.exports = TokenStream;


code:
var MIN_SIZE = 16 * 1024;
var SafeUint32Array = typeof Uint32Array !== 'undefined' ? Uint32Array : Array; // fallback on Array when TypedArray is not supported

module.exports = function adoptBuffer(buffer, size) {
    if (buffer === null || buffer.length < size) {
        return new SafeUint32Array(Math.max(size + 1024, MIN_SIZE));
    }

    return buffer;
};


code:
var List = require('../common/List');

module.exports = function createConvertors(walk) {
    return {
        fromPlainObject: function(ast) {
            walk(ast, {
                enter: function(node) {
                    if (node.children && node.children instanceof List === false) {
                        node.children = new List().fromArray(node.children);
                    }
                }
            });

            return ast;
        },
        toPlainObject: function(ast) {
            walk(ast, {
                leave: function(node) {
                    if (node.children && node.children instanceof List) {
                        node.children = node.children.toArray();
                    }
                }
            });

            return ast;
        }
    };
};


code:
var createConvertor = require('./create');

module.exports = createConvertor(require('../walker'));


code:
var createCustomError = require('../utils/createCustomError');

module.exports = function SyntaxError(message, input, offset) {
    var error = createCustomError('SyntaxError', message);

    error.input = input;
    error.offset = offset;
    error.rawMessage = message;
    error.message = error.rawMessage + '\n' +
        '  ' + error.input + '\n' +
        '--' + new Array((error.offset || error.input.length) + 1).join('-') + '^';

    return error;
};


code:
function noop(value) {
    return value;
}

function generateMultiplier(multiplier) {
    if (multiplier.min === 0 && multiplier.max === 0) {
        return '*';
    }

    if (multiplier.min === 0 && multiplier.max === 1) {
        return '?';
    }

    if (multiplier.min === 1 && multiplier.max === 0) {
        return multiplier.comma ? '#' : '+';
    }

    if (multiplier.min === 1 && multiplier.max === 1) {
        return '';
    }

    return (
        (multiplier.comma ? '#' : '') +
        (multiplier.min === multiplier.max
            ? '{' + multiplier.min + '}'
            : '{' + multiplier.min + ',' + (multiplier.max !== 0 ? multiplier.max : '') + '}'
        )
    );
}

function generateTypeOpts(node) {
    switch (node.type) {
        case 'Range':
            return (
                ' [' +
                (node.min === null ? '-∞' : node.min) +
                ',' +
                (node.max === null ? '∞' : node.max) +
                ']'
            );

        default:
            throw new Error('Unknown node type `' + node.type + '`');
    }
}

function generateSequence(node, decorate, forceBraces, compact) {
    var combinator = node.combinator === ' ' || compact ? node.combinator : ' ' + node.combinator + ' ';
    var result = node.terms.map(function(term) {
        return generate(term, decorate, forceBraces, compact);
    }).join(combinator);

    if (node.explicit || forceBraces) {
        result = (compact || result[0] === ',' ? '[' : '[ ') + result + (compact ? ']' : ' ]');
    }

    return result;
}

function generate(node, decorate, forceBraces, compact) {
    var result;

    switch (node.type) {
        case 'Group':
            result =
                generateSequence(node, decorate, forceBraces, compact) +
                (node.disallowEmpty ? '!' : '');
            break;

        case 'Multiplier':
            // return since node is a composition
            return (
                generate(node.term, decorate, forceBraces, compact) +
                decorate(generateMultiplier(node), node)
            );

        case 'Type':
            result = '<' + node.name + (node.opts ? decorate(generateTypeOpts(node.opts), node.opts) : '') + '>';
            break;

        case 'Property':
            result = '<\'' + node.name + '\'>';
            break;

        case 'Keyword':
            result = node.name;
            break;

        case 'AtKeyword':
            result = '@' + node.name;
            break;

        case 'Function':
            result = node.name + '(';
            break;

        case 'String':
        case 'Token':
            result = node.value;
            break;

        case 'Comma':
            result = ',';
            break;

        default:
            throw new Error('Unknown node type `' + node.type + '`');
    }

    return decorate(result, node);
}

module.exports = function(node, options) {
    var decorate = noop;
    var forceBraces = false;
    var compact = false;

    if (typeof options === 'function') {
        decorate = options;
    } else if (options) {
        forceBraces = Boolean(options.forceBraces);
        compact = Boolean(options.compact);
        if (typeof options.decorate === 'function') {
            decorate = options.decorate;
        }
    }

    return generate(node, decorate, forceBraces, compact);
};


code:
module.exports = {
    SyntaxError: require('./SyntaxError'),
    parse: require('./parse'),
    generate: require('./generate'),
    walk: require('./walk')
};


code:
var Tokenizer = require('./tokenizer');
var TAB = 9;
var N = 10;
var F = 12;
var R = 13;
var SPACE = 32;
var EXCLAMATIONMARK = 33;    // !
var NUMBERSIGN = 35;         // #
var AMPERSAND = 38;          // &
var APOSTROPHE = 39;         // '
var LEFTPARENTHESIS = 40;    // (
var RIGHTPARENTHESIS = 41;   // )
var ASTERISK = 42;           // *
var PLUSSIGN = 43;           // +
var COMMA = 44;              // ,
var HYPERMINUS = 45;         // -
var LESSTHANSIGN = 60;       // <
var GREATERTHANSIGN = 62;    // >
var QUESTIONMARK = 63;       // ?
var COMMERCIALAT = 64;       // @
var LEFTSQUAREBRACKET = 91;  // [
var RIGHTSQUAREBRACKET = 93; // ]
var LEFTCURLYBRACKET = 123;  // {
var VERTICALLINE = 124;      // |
var RIGHTCURLYBRACKET = 125; // }
var INFINITY = 8734;         // ∞
var NAME_CHAR = createCharMap(function(ch) {
    return /[a-zA-Z0-9\-]/.test(ch);
});
var COMBINATOR_PRECEDENCE = {
    ' ': 1,
    '&&': 2,
    '||': 3,
    '|': 4
};

function createCharMap(fn) {
    var array = typeof Uint32Array === 'function' ? new Uint32Array(128) : new Array(128);
    for (var i = 0; i < 128; i++) {
        array[i] = fn(String.fromCharCode(i)) ? 1 : 0;
    }
    return array;
}

function scanSpaces(tokenizer) {
    return tokenizer.substringToPos(
        tokenizer.findWsEnd(tokenizer.pos)
    );
}

function scanWord(tokenizer) {
    var end = tokenizer.pos;

    for (; end < tokenizer.str.length; end++) {
        var code = tokenizer.str.charCodeAt(end);
        if (code >= 128 || NAME_CHAR[code] === 0) {
            break;
        }
    }

    if (tokenizer.pos === end) {
        tokenizer.error('Expect a keyword');
    }

    return tokenizer.substringToPos(end);
}

function scanNumber(tokenizer) {
    var end = tokenizer.pos;

    for (; end < tokenizer.str.length; end++) {
        var code = tokenizer.str.charCodeAt(end);
        if (code < 48 || code > 57) {
            break;
        }
    }

    if (tokenizer.pos === end) {
        tokenizer.error('Expect a number');
    }

    return tokenizer.substringToPos(end);
}

function scanString(tokenizer) {
    var end = tokenizer.str.indexOf('\'', tokenizer.pos + 1);

    if (end === -1) {
        tokenizer.pos = tokenizer.str.length;
        tokenizer.error('Expect an apostrophe');
    }

    return tokenizer.substringToPos(end + 1);
}

function readMultiplierRange(tokenizer) {
    var min = null;
    var max = null;

    tokenizer.eat(LEFTCURLYBRACKET);

    min = scanNumber(tokenizer);

    if (tokenizer.charCode() === COMMA) {
        tokenizer.pos++;
        if (tokenizer.charCode() !== RIGHTCURLYBRACKET) {
            max = scanNumber(tokenizer);
        }
    } else {
        max = min;
    }

    tokenizer.eat(RIGHTCURLYBRACKET);

    return {
        min: Number(min),
        max: max ? Number(max) : 0
    };
}

function readMultiplier(tokenizer) {
    var range = null;
    var comma = false;

    switch (tokenizer.charCode()) {
        case ASTERISK:
            tokenizer.pos++;

            range = {
                min: 0,
                max: 0
            };

            break;

        case PLUSSIGN:
            tokenizer.pos++;

            range = {
                min: 1,
                max: 0
            };

            break;

        case QUESTIONMARK:
            tokenizer.pos++;

            range = {
                min: 0,
                max: 1
            };

            break;

        case NUMBERSIGN:
            tokenizer.pos++;

            comma = true;

            if (tokenizer.charCode() === LEFTCURLYBRACKET) {
                range = readMultiplierRange(tokenizer);
            } else {
                range = {
                    min: 1,
                    max: 0
                };
            }

            break;

        case LEFTCURLYBRACKET:
            range = readMultiplierRange(tokenizer);
            break;

        default:
            return null;
    }

    return {
        type: 'Multiplier',
        comma: comma,
        min: range.min,
        max: range.max,
        term: null
    };
}

function maybeMultiplied(tokenizer, node) {
    var multiplier = readMultiplier(tokenizer);

    if (multiplier !== null) {
        multiplier.term = node;
        return multiplier;
    }

    return node;
}

function maybeToken(tokenizer) {
    var ch = tokenizer.peek();

    if (ch === '') {
        return null;
    }

    return {
        type: 'Token',
        value: ch
    };
}

function readProperty(tokenizer) {
    var name;

    tokenizer.eat(LESSTHANSIGN);
    tokenizer.eat(APOSTROPHE);

    name = scanWord(tokenizer);

    tokenizer.eat(APOSTROPHE);
    tokenizer.eat(GREATERTHANSIGN);

    return maybeMultiplied(tokenizer, {
        type: 'Property',
        name: name
    });
}

// https://drafts.csswg.org/css-values-3/#numeric-ranges
// 4.1. Range Restrictions and Range Definition Notation
//
// Range restrictions can be annotated in the numeric type notation using CSS bracketed
// range notation—[min,max]—within the angle brackets, after the identifying keyword,
// indicating a closed range between (and including) min and max.
// For example, <integer [0, 10]> indicates an integer between 0 and 10, inclusive.
function readTypeRange(tokenizer) {
    // use null for Infinity to make AST format JSON serializable/deserializable
    var min = null; // -Infinity
    var max = null; // Infinity
    var sign = 1;

    tokenizer.eat(LEFTSQUAREBRACKET);

    if (tokenizer.charCode() === HYPERMINUS) {
        tokenizer.peek();
        sign = -1;
    }

    if (sign == -1 && tokenizer.charCode() === INFINITY) {
        tokenizer.peek();
    } else {
        min = sign * Number(scanNumber(tokenizer));
    }

    scanSpaces(tokenizer);
    tokenizer.eat(COMMA);
    scanSpaces(tokenizer);

    if (tokenizer.charCode() === INFINITY) {
        tokenizer.peek();
    } else {
        sign = 1;

        if (tokenizer.charCode() === HYPERMINUS) {
            tokenizer.peek();
            sign = -1;
        }

        max = sign * Number(scanNumber(tokenizer));
    }

    tokenizer.eat(RIGHTSQUAREBRACKET);

    // If no range is indicated, either by using the bracketed range notation
    // or in the property description, then [−∞,∞] is assumed.
    if (min === null && max === null) {
        return null;
    }

    return {
        type: 'Range',
        min: min,
        max: max
    };
}

function readType(tokenizer) {
    var name;
    var opts = null;

    tokenizer.eat(LESSTHANSIGN);
    name = scanWord(tokenizer);

    if (tokenizer.charCode() === LEFTPARENTHESIS &&
        tokenizer.nextCharCode() === RIGHTPARENTHESIS) {
        tokenizer.pos += 2;
        name += '()';
    }

    if (tokenizer.charCodeAt(tokenizer.findWsEnd(tokenizer.pos)) === LEFTSQUAREBRACKET) {
        scanSpaces(tokenizer);
        opts = readTypeRange(tokenizer);
    }

    tokenizer.eat(GREATERTHANSIGN);

    return maybeMultiplied(tokenizer, {
        type: 'Type',
        name: name,
        opts: opts
    });
}

function readKeywordOrFunction(tokenizer) {
    var name;

    name = scanWord(tokenizer);

    if (tokenizer.charCode() === LEFTPARENTHESIS) {
        tokenizer.pos++;

        return {
            type: 'Function',
            name: name
        };
    }

    return maybeMultiplied(tokenizer, {
        type: 'Keyword',
        name: name
    });
}

function regroupTerms(terms, combinators) {
    function createGroup(terms, combinator) {
        return {
            type: 'Group',
            terms: terms,
            combinator: combinator,
            disallowEmpty: false,
            explicit: false
        };
    }

    combinators = Object.keys(combinators).sort(function(a, b) {
        return COMBINATOR_PRECEDENCE[a] - COMBINATOR_PRECEDENCE[b];
    });

    while (combinators.length > 0) {
        var combinator = combinators.shift();
        for (var i = 0, subgroupStart = 0; i < terms.length; i++) {
            var term = terms[i];
            if (term.type === 'Combinator') {
                if (term.value === combinator) {
                    if (subgroupStart === -1) {
                        subgroupStart = i - 1;
                    }
                    terms.splice(i, 1);
                    i--;
                } else {
                    if (subgroupStart !== -1 && i - subgroupStart > 1) {
                        terms.splice(
                            subgroupStart,
                            i - subgroupStart,
                            createGroup(terms.slice(subgroupStart, i), combinator)
                        );
                        i = subgroupStart + 1;
                    }
                    subgroupStart = -1;
                }
            }
        }

        if (subgroupStart !== -1 && combinators.length) {
            terms.splice(
                subgroupStart,
                i - subgroupStart,
                createGroup(terms.slice(subgroupStart, i), combinator)
            );
        }
    }

    return combinator;
}

function readImplicitGroup(tokenizer) {
    var terms = [];
    var combinators = {};
    var token;
    var prevToken = null;
    var prevTokenPos = tokenizer.pos;

    while (token = peek(tokenizer)) {
        if (token.type !== 'Spaces') {
            if (token.type === 'Combinator') {
                // check for combinator in group beginning and double combinator sequence
                if (prevToken === null || prevToken.type === 'Combinator') {
                    tokenizer.pos = prevTokenPos;
                    tokenizer.error('Unexpected combinator');
                }

                combinators[token.value] = true;
            } else if (prevToken !== null && prevToken.type !== 'Combinator') {
                combinators[' '] = true;  // a b
                terms.push({
                    type: 'Combinator',
                    value: ' '
                });
            }

            terms.push(token);
            prevToken = token;
            prevTokenPos = tokenizer.pos;
        }
    }

    // check for combinator in group ending
    if (prevToken !== null && prevToken.type === 'Combinator') {
        tokenizer.pos -= prevTokenPos;
        tokenizer.error('Unexpected combinator');
    }

    return {
        type: 'Group',
        terms: terms,
        combinator: regroupTerms(terms, combinators) || ' ',
        disallowEmpty: false,
        explicit: false
    };
}

function readGroup(tokenizer) {
    var result;

    tokenizer.eat(LEFTSQUAREBRACKET);
    result = readImplicitGroup(tokenizer);
    tokenizer.eat(RIGHTSQUAREBRACKET);

    result.explicit = true;

    if (tokenizer.charCode() === EXCLAMATIONMARK) {
        tokenizer.pos++;
        result.disallowEmpty = true;
    }

    return result;
}

function peek(tokenizer) {
    var code = tokenizer.charCode();

    if (code < 128 && NAME_CHAR[code] === 1) {
        return readKeywordOrFunction(tokenizer);
    }

    switch (code) {
        case RIGHTSQUAREBRACKET:
            // don't eat, stop scan a group
            break;

        case LEFTSQUAREBRACKET:
            return maybeMultiplied(tokenizer, readGroup(tokenizer));

        case LESSTHANSIGN:
            return tokenizer.nextCharCode() === APOSTROPHE
                ? readProperty(tokenizer)
                : readType(tokenizer);

        case VERTICALLINE:
            return {
                type: 'Combinator',
                value: tokenizer.substringToPos(
                    tokenizer.nextCharCode() === VERTICALLINE
                        ? tokenizer.pos + 2
                        : tokenizer.pos + 1
                )
            };

        case AMPERSAND:
            tokenizer.pos++;
            tokenizer.eat(AMPERSAND);

            return {
                type: 'Combinator',
                value: '&&'
            };

        case COMMA:
            tokenizer.pos++;
            return {
                type: 'Comma'
            };

        case APOSTROPHE:
            return maybeMultiplied(tokenizer, {
                type: 'String',
                value: scanString(tokenizer)
            });

        case SPACE:
        case TAB:
        case N:
        case R:
        case F:
            return {
                type: 'Spaces',
                value: scanSpaces(tokenizer)
            };

        case COMMERCIALAT:
            code = tokenizer.nextCharCode();

            if (code < 128 && NAME_CHAR[code] === 1) {
                tokenizer.pos++;
                return {
                    type: 'AtKeyword',
                    name: scanWord(tokenizer)
                };
            }

            return maybeToken(tokenizer);

        case ASTERISK:
        case PLUSSIGN:
        case QUESTIONMARK:
        case NUMBERSIGN:
        case EXCLAMATIONMARK:
            // prohibited tokens (used as a multiplier start)
            break;

        case LEFTCURLYBRACKET:
            // LEFTCURLYBRACKET is allowed since mdn/data uses it w/o quoting
            // check next char isn't a number, because it's likely a disjoined multiplier
            code = tokenizer.nextCharCode();

            if (code < 48 || code > 57) {
                return maybeToken(tokenizer);
            }

            break;

        default:
            return maybeToken(tokenizer);
    }
}

function parse(source) {
    var tokenizer = new Tokenizer(source);
    var result = readImplicitGroup(tokenizer);

    if (tokenizer.pos !== source.length) {
        tokenizer.error('Unexpected input');
    }

    // reduce redundant groups with single group term
    if (result.terms.length === 1 && result.terms[0].type === 'Group') {
        result = result.terms[0];
    }

    return result;
}

// warm up parse to elimitate code branches that never execute
// fix soft deoptimizations (insufficient type feedback)
parse('[a&&<b>#|<\'c\'>*||e() f{2} /,(% g#{1,2} h{2,})]!');

module.exports = parse;


code:
var SyntaxError = require('./SyntaxError');

var TAB = 9;
var N = 10;
var F = 12;
var R = 13;
var SPACE = 32;

var Tokenizer = function(str) {
    this.str = str;
    this.pos = 0;
};

Tokenizer.prototype = {
    charCodeAt: function(pos) {
        return pos < this.str.length ? this.str.charCodeAt(pos) : 0;
    },
    charCode: function() {
        return this.charCodeAt(this.pos);
    },
    nextCharCode: function() {
        return this.charCodeAt(this.pos + 1);
    },
    nextNonWsCode: function(pos) {
        return this.charCodeAt(this.findWsEnd(pos));
    },
    findWsEnd: function(pos) {
        for (; pos < this.str.length; pos++) {
            var code = this.str.charCodeAt(pos);
            if (code !== R && code !== N && code !== F && code !== SPACE && code !== TAB) {
                break;
            }
        }

        return pos;
    },
    substringToPos: function(end) {
        return this.str.substring(this.pos, this.pos = end);
    },
    eat: function(code) {
        if (this.charCode() !== code) {
            this.error('Expect `' + String.fromCharCode(code) + '`');
        }

        this.pos++;
    },
    peek: function() {
        return this.pos < this.str.length ? this.str.charAt(this.pos++) : '';
    },
    error: function(message) {
        throw new SyntaxError(message, this.str, this.pos);
    }
};

module.exports = Tokenizer;


code:
var noop = function() {};

function ensureFunction(value) {
    return typeof value === 'function' ? value : noop;
}

module.exports = function(node, options, context) {
    function walk(node) {
        enter.call(context, node);

        switch (node.type) {
            case 'Group':
                node.terms.forEach(walk);
                break;

            case 'Multiplier':
                walk(node.term);
                break;

            case 'Type':
            case 'Property':
            case 'Keyword':
            case 'AtKeyword':
            case 'Function':
            case 'String':
            case 'Token':
            case 'Comma':
                break;

            default:
                throw new Error('Unknown type: ' + node.type);
        }

        leave.call(context, node);
    }

    var enter = noop;
    var leave = noop;

    if (typeof options === 'function') {
        enter = options;
    } else if (options) {
        enter = ensureFunction(options.enter);
        leave = ensureFunction(options.leave);
    }

    if (enter === noop && leave === noop) {
        throw new Error('Neither `enter` nor `leave` walker handler is set or both aren\'t a function');
    }

    walk(node, context);
};


code:
var sourceMap = require('./sourceMap');
var hasOwnProperty = Object.prototype.hasOwnProperty;

function processChildren(node, delimeter) {
    var list = node.children;
    var prev = null;

    if (typeof delimeter !== 'function') {
        list.forEach(this.node, this);
    } else {
        list.forEach(function(node) {
            if (prev !== null) {
                delimeter.call(this, prev);
            }

            this.node(node);
            prev = node;
        }, this);
    }
}

module.exports = function createGenerator(config) {
    function processNode(node) {
        if (hasOwnProperty.call(types, node.type)) {
            types[node.type].call(this, node);
        } else {
            throw new Error('Unknown node type: ' + node.type);
        }
    }

    var types = {};

    if (config.node) {
        for (var name in config.node) {
            types[name] = config.node[name].generate;
        }
    }

    return function(node, options) {
        var buffer = '';
        var handlers = {
            children: processChildren,
            node: processNode,
            chunk: function(chunk) {
                buffer += chunk;
            },
            result: function() {
                return buffer;
            }
        };

        if (options) {
            if (typeof options.decorator === 'function') {
                handlers = options.decorator(handlers);
            }

            if (options.sourceMap) {
                handlers = sourceMap(handlers);
            }
        }

        handlers.node(node);

        return handlers.result();
    };
};


code:
var createGenerator = require('./create');
var config = require('../syntax/config/parser');

module.exports = createGenerator(config);


code:
var SourceMapGenerator = require('source-map/lib/source-map-generator').SourceMapGenerator;
var trackNodes = {
    Atrule: true,
    Selector: true,
    Declaration: true
};

module.exports = function generateSourceMap(handlers) {
    var map = new SourceMapGenerator();
    var line = 1;
    var column = 0;
    var generated = {
        line: 1,
        column: 0
    };
    var original = {
        line: 0, // should be zero to add first mapping
        column: 0
    };
    var sourceMappingActive = false;
    var activatedGenerated = {
        line: 1,
        column: 0
    };
    var activatedMapping = {
        generated: activatedGenerated
    };

    var handlersNode = handlers.node;
    handlers.node = function(node) {
        if (node.loc && node.loc.start && trackNodes.hasOwnProperty(node.type)) {
            var nodeLine = node.loc.start.line;
            var nodeColumn = node.loc.start.column - 1;

            if (original.line !== nodeLine ||
                original.column !== nodeColumn) {
                original.line = nodeLine;
                original.column = nodeColumn;

                generated.line = line;
                generated.column = column;

                if (sourceMappingActive) {
                    sourceMappingActive = false;
                    if (generated.line !== activatedGenerated.line ||
                        generated.column !== activatedGenerated.column) {
                        map.addMapping(activatedMapping);
                    }
                }

                sourceMappingActive = true;
                map.addMapping({
                    source: node.loc.source,
                    original: original,
                    generated: generated
                });
            }
        }

        handlersNode.call(this, node);

        if (sourceMappingActive && trackNodes.hasOwnProperty(node.type)) {
            activatedGenerated.line = line;
            activatedGenerated.column = column;
        }
    };

    var handlersChunk = handlers.chunk;
    handlers.chunk = function(chunk) {
        for (var i = 0; i < chunk.length; i++) {
            if (chunk.charCodeAt(i) === 10) { // \n
                line++;
                column = 0;
            } else {
                column++;
            }
        }

        handlersChunk(chunk);
    };

    var handlersResult = handlers.result;
    handlers.result = function() {
        if (sourceMappingActive) {
            map.addMapping(activatedMapping);
        }

        return {
            css: handlersResult(),
            map: map
        };
    };

    return handlers;
};


code: module.exports = require('./syntax');