diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | readme.md | 34 | ||||
| -rw-r--r-- | res/config | 51 | ||||
| -rw-r--r-- | res/default.css | 12 | ||||
| -rw-r--r-- | src/buffer.nim | 17 | ||||
| -rw-r--r-- | src/config.nim | 42 | ||||
| -rw-r--r-- | src/css/cssparser.nim (renamed from src/cssparser.nim) | 74 | ||||
| -rw-r--r-- | src/css/selector.nim | 151 | ||||
| -rw-r--r-- | src/css/style.nim | 321 | ||||
| -rw-r--r-- | src/html/dom.nim (renamed from src/dom.nim) | 290 | ||||
| -rw-r--r-- | src/html/entity.nim (renamed from src/entity.nim) | 17 | ||||
| -rw-r--r-- | src/html/htmlparser.nim (renamed from src/htmlparser.nim) | 135 | ||||
| -rw-r--r-- | src/io/display.nim (renamed from src/display.nim) | 38 | ||||
| -rw-r--r-- | src/io/twtio.nim | 323 | ||||
| -rw-r--r-- | src/main.nim | 28 | ||||
| -rw-r--r-- | src/radixtree.nim | 440 | ||||
| -rw-r--r-- | src/style.nim | 74 | ||||
| -rw-r--r-- | src/twtio.nim | 263 | ||||
| -rw-r--r-- | src/types/enums.nim (renamed from src/enums.nim) | 29 | ||||
| -rw-r--r-- | src/types/tagtypes.nim | 30 | ||||
| -rw-r--r-- | src/utils/radixtree.nim | 309 | ||||
| -rw-r--r-- | src/utils/termattrs.nim (renamed from src/termattrs.nim) | 0 | ||||
| -rw-r--r-- | src/utils/twtstr.nim (renamed from src/twtstr.nim) | 154 |
23 files changed, 1705 insertions, 1133 deletions
diff --git a/Makefile b/Makefile index 3d42c18d..a3baa746 100644 --- a/Makefile +++ b/Makefile @@ -6,11 +6,9 @@ debug: $(NIMC) $(FLAGS) -d:small $(FILES) release: $(NIMC) $(FLAGS) -d:release $(FILES) +small: + $(NIMC) $(FLAGS) -d:danger -d:small $(FILES) danger: $(NIMC) $(FLAGS) -d:danger $(FILES) -small: - $(NIMC) $(FLAGS) -d:release -d:small $(FILES) -lowmem: - $(NIMC) $(FLAGS) -d:release -d:lowmem $(FILES) clean: rm ./twt diff --git a/readme.md b/readme.md index 7c95e958..9a399b00 100644 --- a/readme.md +++ b/readme.md @@ -1,14 +1,32 @@ # twt - a web browser in your terminal ## What is this? + A terminal web browser. It displays websites in your terminal and allows you to navigate on them. +## How to compile? + +1. Install the nim compiler. +2. Use one of the following: + - `make release` - normal release build + - `make small` - small release build + - `make` - debug build + ## Why make another web browser? -I've found other terminal web browsers insufficient for my needs, so I thought it'd be a fun excercise to write one myself. -I don't really want a standard-compliant browser, or one that displays pages perfectly - the only way you could do that in a terminal is to work like browsh, which kinda defeats the point of a terminal web browser. I want one that is good enough for daily use, something like lynx or w3m. -So the aim is to implement HTML rendering, some degree of JS support, and a very limited subset of CSS. Plus some other things. + +I've found other terminal web browsers insufficient for my needs, so I thought +it'd be a fun excercise to write one myself. + +I don't really want a standard-compliant browser, or one that displays pages +perfectly - the only way you could do that in a terminal is to work like +browsh, which kinda defeats the point of a terminal web browser. I want one +that is good enough for daily use, something like lynx or w3m. + +So the aim is to implement HTML rendering, some degree of JS support, and a +very limited subset of CSS. Plus some other things. ## So what can this do? + Currently implemented features are: * basic html rendering (very much WIP) @@ -17,7 +35,8 @@ Currently implemented features are: Planned features (roughly in order of importance): * stylesheets -* improved html rendering (like, actually functioning) +* JavaScript +* improved html rendering (i.e. actually functioning) * form * table * cookie @@ -25,14 +44,15 @@ Planned features (roughly in order of importance): * HTTP proxy * image (sixel/kitty) * audio -* JavaScript * video (sixel/kitty) +* frame? * extension API? * non-unicode charsets? * async? * markdown? (with built-in parser) * gopher? -* gemini? +* gemini?? ## How do I configure stuff? -Currently only keybindings can be configured. See the keymap file for the default (built-in) configuration. + +Currently only keybindings can be configured. See the res/config file for the default (built-in) configuration. diff --git a/res/config b/res/config index 48ec0d32..a4f5ebd0 100644 --- a/res/config +++ b/res/config @@ -4,10 +4,10 @@ nmap h CURSOR_LEFT nmap j CURSOR_DOWN nmap k CURSOR_UP nmap l CURSOR_RIGHT -nmap \e[D CURSOR_LEFT -nmap \e[B CURSOR_DOWN -nmap \e[A CURSOR_UP -nmap \e[C CURSOR_RIGHT +nmap M-[D CURSOR_LEFT +nmap M-[B CURSOR_DOWN +nmap M-[A CURSOR_UP +nmap M-[C CURSOR_RIGHT nmap ^ CURSOR_LINEBEGIN nmap $ CURSOR_LINEEND nmap b CURSOR_PREV_WORD @@ -21,8 +21,8 @@ nmap C-d HALF_PAGE_DOWN nmap C-u HALF_PAGE_UP nmap C-f PAGE_DOWN nmap C-b PAGE_UP -nmap \e[6~ PAGE_DOWN -nmap \e[5~ PAGE_UP +nmap M-[6~ PAGE_DOWN +nmap M-[5~ PAGE_UP nmap C-e SCROLL_DOWN nmap C-y SCROLL_UP nmap J SCROLL_DOWN @@ -35,8 +35,8 @@ nmap r RESHAPE nmap R REDRAW nmap gg CURSOR_FIRST_LINE nmap G CURSOR_LAST_LINE -nmap \e[H CURSOR_FIRST_LINE -nmap \e[F CURSOR_LAST_LINE +nmap M-[H CURSOR_FIRST_LINE +nmap M-[F CURSOR_LAST_LINE nmap z CENTER_LINE nmap C-g LINE_INFO @@ -47,8 +47,8 @@ lemap C-h LINED_BACKSPACE lemap C-? LINED_BACKSPACE lemap C-d LINED_DELETE lemap C-c LINED_CANCEL -lemap \eb LINED_PREV_WORD -lemap \ef LINED_NEXT_WORD +lemap M-b LINED_PREV_WORD +lemap M-f LINED_NEXT_WORD lemap C-b LINED_BACK lemap C-f LINED_FORWARD lemap C-u LINED_CLEAR @@ -121,7 +121,7 @@ comp te て comp to と comp tta った -comp tchi っち +comp cchi っち comp ttsu っつ comp tte って comp tto っと @@ -160,8 +160,6 @@ comp re れ comp ro ろ comp wa わ -comp wi ゐ -comp we ゑ comp wo を comp ga が @@ -195,6 +193,7 @@ comp pe ぺ comp po ぽ comp n ん +comp n' ん comp kya きゃ comp kyu きゅ @@ -249,10 +248,22 @@ comp tti ってぃ comp di てぃ comp ddi ってぃ -comp she しぇ -comp sshe っしぇ +comp kkya っきゃ +comp kkyu っきゅ +comp kkyo っきょ + +comp ssha っしゃ +comp sshu っしゅ +comp ssho っしょ + +comp ccha っちゃ +comp cchu っちゅ +comp ccho っちょ +comp she しぇ comp je じぇ + +comp sshe っしぇ comp jje っじぇ #katakana @@ -299,7 +310,7 @@ comp TE テ comp TO ト comp TTA ッタ -comp TCHI ッチ +comp CCHI ッチ comp TTSU ッツ comp TTE ッテ comp TTO ッと @@ -338,8 +349,6 @@ comp RE レ comp RO ロ comp WA ワ -comp WI ヰ -comp WE ヱ comp WO ヲ comp GA ガ @@ -373,7 +382,8 @@ comp PE ペ comp PO ポ comp N ン -comp X ー +comp N' ン +comp - ー comp KYA キャ comp KYU キュ @@ -432,3 +442,6 @@ comp SSHE ッシェ comp JE ジェ comp JJE ッジェ + +comp WI ウィ +comp WE ウェ diff --git a/res/default.css b/res/default.css index d1d6801d..1e30253c 100644 --- a/res/default.css +++ b/res/default.css @@ -5,28 +5,28 @@ area, base, source, track, link, meta, param, wbr, head, style, script { address, blockquote, center, del, dir, div, dl, fieldset, form, h1, h2, h3, h4, h5, h6, hr, ins, menu, noframes, noscript, ol, p, pre, table, ul, center, dir, menu, noframes, body { - display: block + display: block; } br { display: block; - content: ' ' + content: ' '; } a, abbr, b, bdo, button, cite, code, del, dfn, em, font, i, img, ins, input, iframe, kbd, label, map, object, q, samp, select, small, span, strong, sub, sup, textarea, tt, var, font, iframe, u, s, strike, frame, img, input { - display: inline + display: inline; } col { - display: table-column + display: table-column; } img { - display: inline-block + display: inline-block; } li { - display: list-item + display: list-item; } diff --git a/src/buffer.nim b/src/buffer.nim index 5eaa4717..dc171137 100644 --- a/src/buffer.nim +++ b/src/buffer.nim @@ -4,11 +4,14 @@ import tables import strutils import unicode -import termattrs -import dom -import twtio -import enums -import twtstr +import types/enums + +import utils/termattrs +import utils/twtstr + +import html/dom + +import io/twtio type Buffer* = ref BufferObj @@ -115,7 +118,7 @@ proc addNode*(buffer: Buffer, node: Node) = buffer.clickables.add(node) else: discard elif node.isTextNode(): - if node.parentElement != nil and node.parentElement.style.islink: + if node.parentElement != nil and node.getStyle().islink: let anchor = node.ancestor(TAG_A) assert(anchor != nil) buffer.clickables.add(anchor) @@ -407,7 +410,6 @@ proc checkLinkSelection*(buffer: Buffer): bool = return false else: let anchor = buffer.selectedlink.ancestor(TAG_A) - anchor.style.selected = false buffer.selectedlink.fmttext = buffer.selectedlink.getFmtText() buffer.selectedlink = nil buffer.hovertext = "" @@ -423,7 +425,6 @@ proc checkLinkSelection*(buffer: Buffer): bool = buffer.selectedlink = node let anchor = node.ancestor(TAG_A) assert(anchor != nil) - anchor.style.selected = true buffer.hovertext = HtmlAnchorElement(anchor).href var stack: seq[Node] stack.add(anchor) diff --git a/src/config.nim b/src/config.nim index d4713123..73dff47d 100644 --- a/src/config.nim +++ b/src/config.nim @@ -1,8 +1,8 @@ import tables import strutils -import twtstr -import radixtree +import utils/twtstr +import utils/radixtree type TwtAction* = @@ -43,21 +43,30 @@ func getRealKey(key: string): string = var realk: string var currchar: char var control = 0 + var meta = 0 var skip = false for c in key: if c == '\\': skip = true elif skip: - if c == 'e': - realk &= '\e' - else: - realk &= c + realk &= c skip = false + elif c == 'M': + inc meta + currchar = c elif c == 'C': inc control currchar = c elif c == '-' and control == 1: inc control + elif c == '-' and meta == 1: + inc meta + elif meta == 1: + realk &= 'C' & c + meta = 0 + elif meta == 2: + realk &= '\e' + realk &= c elif control == 1: realk &= 'C' & c control = 0 @@ -115,18 +124,11 @@ proc staticReadKeymap(): (ActionMap, ActionMap, Table[string, string]) = lemap = constructActionTable(lemap) return (nmap, lemap, compose) -const (normalActionMap, linedActionMap, composeMap) = staticReadKeymap() - -normalActionRemap = normalActionMap -linedActionRemap = linedActionMap -composeRemap = composeMap.toRadixTree() -proc traverseRemap[T](m: RadixNode[T], s: string) = - echo s - for k in m.keys: - assert(m{k, m} != m, s & " " & k) - m{k, m}.traverseRemap(s & k) - -composeRemap.traverseRemap("") +when not defined(small): + const (normalActionMap, linedActionMap, composeMap) = staticReadKeymap() + normalActionRemap = normalActionMap + linedActionRemap = linedActionMap + composeRemap = composeMap.toRadixTree() proc readConfig*(filename: string): bool = var f: File @@ -139,8 +141,8 @@ proc readConfig*(filename: string): bool = while f.readLine(line): parseConfigLine(line, nmap, lemap, compose) - normalActionRemap = constructActionTable(normalActionMap) - linedActionRemap = constructActionTable(linedActionMap) + normalActionRemap = constructActionTable(nmap) + linedActionRemap = constructActionTable(lemap) composeRemap = compose.toRadixTree() return true else: diff --git a/src/cssparser.nim b/src/css/cssparser.nim index ce5b5037..5ecb470a 100644 --- a/src/cssparser.nim +++ b/src/css/cssparser.nim @@ -7,9 +7,11 @@ import streams import math import options -import twtstr -import twtio -import enums +import ../io/twtio + +import ../utils/twtstr + +import ../types/enums type CSSTokenizerState = object @@ -71,9 +73,7 @@ type SyntaxError = object of ValueError - CSSColor* = tuple[r: uint8, g: uint8, b: uint8, a: uint8] - -func `==`(a: CSSParsedItem, b: CSSTokenType): bool = +func `==`*(a: CSSParsedItem, b: CSSTokenType): bool = return a of CSSToken and CSSToken(a).tokenType == b func toNumber(s: seq[Rune]): float64 = @@ -119,31 +119,6 @@ func toNumber(s: seq[Rune]): float64 = return float64(sign) * (integer + f * pow(10, float64(-d))) * pow(10, (float64(t) * e)) -func toColor*(s: seq[Rune]): CSSColor = - if s.len == 3: - for r in s: - if hexValue(r) == -1: - return - let r = hexValue(s[0]) * 0x10 + hexValue(s[0]) - let g = hexValue(s[1]) * 0x10 + hexValue(s[1]) - let b = hexValue(s[2]) * 0x10 + hexValue(s[2]) - - result.r = uint8(r) - result.g = uint8(g) - result.b = uint8(b) - result.a = 0 - elif s.len == 6: - for r in s: - if hexValue(r) == -1: - return - let r = hexValue(s[0]) * 0x10 + hexValue(s[1]) - let g = hexValue(s[2]) * 0x10 + hexValue(s[3]) - let b = hexValue(s[4]) * 0x10 + hexValue(s[5]) - result.r = uint8(r) - result.g = uint8(g) - result.b = uint8(b) - result.a = 0 - func isNameStartCodePoint*(r: Rune): bool = return not isAscii(r) or r == Rune('_') or isAlphaAscii(r) @@ -470,7 +445,6 @@ proc tokenizeCSS*(inputStream: Stream): seq[CSSParsedItem] = state.buf = state.stream.readLine().toRunes() while state.has(): result.add(state.consumeToken()) - eprint "consume token", CSSToken(result[^1]).tokenType inputStream.close() @@ -512,10 +486,26 @@ proc consumeSimpleBlock(state: var CSSParseState): CSSSimpleBlock = result.value.add(CSSComponentValue(t)) return result +proc consumeComponentValue*(state: var CSSParseState): CSSComponentValue + +proc consumeFunction(state: var CSSParseState): CSSFunction = + let t = (CSSToken)state.consume() + result = CSSFunction(name: t.value) + while state.at < state.tokens.len: + let t = state.consume() + if t == CSS_RPAREN_TOKEN: + return result + else: + state.reconsume() + result.value.add(state.consumeComponentValue()) + proc consumeComponentValue(state: var CSSParseState): CSSComponentValue = let t = state.consume() if t == CSS_LBRACE_TOKEN or t == CSS_LBRACKET_TOKEN or t == CSS_LPAREN_TOKEN: return state.consumeSimpleBlock() + elif t == CSS_FUNCTION_TOKEN: + state.reconsume() + return state.consumeFunction() return CSSComponentValue(t) proc consumeQualifiedRule(state: var CSSParseState): Option[CSSQualifiedRule] = @@ -559,15 +549,11 @@ proc consumeDeclaration(state: var CSSParseState): Option[CSSDeclaration] = if not state.has() or state.curr() != CSS_COLON_TOKEN: return none(CSSDeclaration) discard state.consume() - eprint state.tokens.len while state.has() and state.curr() == CSS_WHITESPACE_TOKEN: - eprint "ok...", CSSToken(state.curr()).tokenType discard state.consume() while state.has(): - eprint "ok..." decl.value.add(state.consumeComponentValue()) - eprint "helloo?", decl.value.len var i = decl.value.len - 1 var j = 2 @@ -642,15 +628,6 @@ proc consumeListOfRules(state: var CSSParseState): seq[CSSRule] = if q.isSome: result.add(q.get) -proc consumeFunction(state: var CSSParseState): CSSFunction = - while state.at < state.tokens.len: - let t = state.consume() - if t == CSS_RPAREN_TOKEN: - return result - else: - state.reconsume() - result.value.add(state.consumeComponentValue()) - proc parseStylesheet(state: var CSSParseState): CSSStylesheet = state.top_level = true result.value.add(state.consumeListOfRules()) @@ -793,9 +770,10 @@ proc printc*(c: CSSComponentValue) = printc(s) stderr.write(";\n") elif c of CSSFunction: - eprint "FUNCTION", CSSFunction(c).name + stderr.write($CSSFunction(c).name & "(") for s in CSSFunction(c).value: printc(s) + stderr.write(")") elif c of CSSSimpleBlock: case CSSSimpleBlock(c).token.tokenType of CSS_LBRACE_TOKEN: eprint "{" @@ -810,8 +788,10 @@ proc printc*(c: CSSComponentValue) = of CSS_LBRACKET_TOKEN: stderr.write("]") else: discard +proc parseCSS*(inputStream: Stream): CSSStylesheet = + return inputstream.parseStylesheet() -proc parseCSS*(inputStream: Stream) = +proc debugparseCSS*(inputStream: Stream) = let ss = inputStream.parseStylesheet() for v in ss.value: if v of CSSAtRule: diff --git a/src/css/selector.nim b/src/css/selector.nim new file mode 100644 index 00000000..1ca417dd --- /dev/null +++ b/src/css/selector.nim @@ -0,0 +1,151 @@ +import unicode + +import ../types/enums +import ../types/tagtypes + +import cssparser + +type + SelectorType* = enum + TYPE_SELECTOR, ID_SELECTOR, ATTR_SELECTOR, CLASS_SELECTOR, + UNIVERSAL_SELECTOR, PSEUDO_SELECTOR, PSELEM_SELECTOR, FUNC_SELECTOR + + QueryMode* = enum + QUERY_TYPE, QUERY_CLASS, QUERY_ATTR, QUERY_DELIM, QUERY_VALUE, + QUERY_PSEUDO, QUERY_PSELEM + + SelectorParser = object + selectors: seq[SelectorList] + query: QueryMode + negate: bool + + #TODO combinators + Selector* = object + case t*: SelectorType + of TYPE_SELECTOR: + tag*: TagType + of ID_SELECTOR: + id*: string + of ATTR_SELECTOR: + attr*: string + value*: string + rel*: char + of CLASS_SELECTOR: + class*: string + of UNIVERSAL_SELECTOR: #TODO namespaces? + discard + of PSEUDO_SELECTOR: + pseudo*: string + of PSELEM_SELECTOR: + elem*: string + of FUNC_SELECTOR: + name*: string + selectors*: SelectorList + + SelectorList* = ref object + sels*: seq[Selector] + parent*: SelectorList + +proc add*(sellist: SelectorList, sel: Selector) = sellist.sels.add(sel) +proc add*(sellist: SelectorList, sels: SelectorList) = sellist.sels.add(sels.sels) +proc setLen*(sellist: SelectorList, i: int) = sellist.sels.setLen(i) +proc `[]`*(sellist: SelectorList, i: int): Selector = sellist.sels[i] +proc len*(sellist: SelectorList): int = sellist.sels.len + +proc parseSelectorToken(state: var SelectorParser, csstoken: CSSToken) = + case csstoken.tokenType + of CSS_IDENT_TOKEN: + var sel: Selector + case state.query + of QUERY_CLASS: + state.selectors[^1].add(Selector(t: CLASS_SELECTOR, class: $csstoken.value)) + of QUERY_TYPE: + state.selectors[^1].add(Selector(t: TYPE_SELECTOR, tag: tagType($csstoken.value))) + of QUERY_PSEUDO: + state.selectors[^1].add(Selector(t: PSEUDO_SELECTOR, pseudo: $csstoken.value)) + of QUERY_PSELEM: + state.selectors[^1].add(Selector(t: PSELEM_SELECTOR, elem: $csstoken.value)) + else: discard + state.query = QUERY_TYPE + of CSS_DELIM_TOKEN: + if csstoken.rvalue == Rune('.'): + state.query = QUERY_CLASS + of CSS_HASH_TOKEN: + state.selectors[^1].add(Selector(t: ID_SELECTOR, id: $csstoken.value)) + of CSS_COMMA_TOKEN: + if state.selectors[^1].len > 0: + state.selectors.add(SelectorList()) + of CSS_COLON_TOKEN: + if state.query == QUERY_PSEUDO: + state.query = QUERY_PSELEM + else: + state.query = QUERY_PSEUDO + else: discard + +proc parseSelectorSimpleBlock(state: var SelectorParser, cssblock: CSSSimpleBlock) = + case cssblock.token.tokenType + of CSS_LBRACKET_TOKEN: + state.query = QUERY_ATTR + for cval in cssblock.value: + if cval of CSSToken: + let csstoken = (CSSToken)cval + case csstoken.tokenType + of CSS_IDENT_TOKEN: + case state.query + of QUERY_ATTR: + state.query = QUERY_DELIM + state.selectors[^1].add(Selector(t: ATTR_SELECTOR, attr: $csstoken.value, rel: ' ')) + of QUERY_VALUE: + state.selectors[^1].sels[^1].value = $csstoken.value + break + else: discard + of CSS_STRING_TOKEN: + case state.query + of QUERY_VALUE: + state.selectors[^1].sels[^1].value = $csstoken.value + break + else: discard + of CSS_DELIM_TOKEN: + case csstoken.rvalue + of Rune('~'), Rune('|'), Rune('^'), Rune('$'), Rune('*'): + if state.query == QUERY_DELIM: + state.selectors[^1].sels[^1].rel = char(csstoken.rvalue) + of Rune('='): + if state.query == QUERY_DELIM: + state.query = QUERY_VALUE + else: discard + else: discard + state.query = QUERY_TYPE + else: discard + +proc parseSelectorFunction(state: var SelectorParser, cssfunction: CSSFunction) = + case $cssfunction.name + of "not": + if state.query != QUERY_PSEUDO: + return + state.query = QUERY_TYPE + else: return + var fun = Selector(t: FUNC_SELECTOR, name: $cssfunction.name) + fun.selectors = SelectorList(parent: state.selectors[^1]) + state.selectors[^1].add(fun) + state.selectors[^1] = fun.selectors + for cval in cssfunction.value: + if cval of CSSToken: + state.parseSelectorToken((CSSToken)cval) + elif cval of CSSSimpleBlock: + state.parseSelectorSimpleBlock((CSSSimpleBlock)cval) + elif cval of CSSFunction: + state.parseSelectorFunction((CSSFunction)cval) + state.selectors[^1] = fun.selectors.parent + +func parseSelectors*(cvals: seq[CSSComponentValue]): seq[SelectorList] = + var state = SelectorParser() + state.selectors.add(SelectorList()) + for cval in cvals: + if cval of CSSToken: + state.parseSelectorToken((CSSToken)cval) + elif cval of CSSSimpleBlock: + state.parseSelectorSimpleBlock((CSSSimpleBlock)cval) + elif cval of CSSFunction: + state.parseSelectorFunction((CSSFunction)cval) + return state.selectors diff --git a/src/css/style.nim b/src/css/style.nim new file mode 100644 index 00000000..56e6b00b --- /dev/null +++ b/src/css/style.nim @@ -0,0 +1,321 @@ +import streams +import unicode +import terminal +import tables + +import ../io/twtio + +import ../utils/twtstr + +import ../types/enums + +import cssparser + +type + CSSLength* = object + num*: float64 + unit*: CSSUnit + auto*: bool + + CSS2Properties* = ref object + rawtext*: string + fmttext*: seq[string] + x*: int + y*: int + ex*: int + ey*: int + width*: int + height*: int + hidden*: bool + before*: CSS2Properties + after*: CSS2Properties + margintop*: CSSLength + marginbottom*: CSSLength + marginleft*: CSSLength + marginright*: CSSLength + centered*: bool + display*: DisplayType + bold*: bool + italic*: bool + underscore*: bool + islink*: bool + selected*: bool + indent*: int + color*: CSSColor + position*: CSSPosition + + CSSCanvas* = object + rootBox*: CSSBox + width*: int + height*: int + + CSSRect* = object + x1*: int + y1*: int + x2*: int + y2*: int + + CSSBox* = ref object + display*: DisplayType + x*: int + y*: int + innerEdge*: CSSRect + paddingEdge*: CSSRect + borderEdge*: CSSRect + marginEdge*: CSSRect + color*: CSSColor + props*: CSS2Properties + content*: seq[Rune] + dispcontent*: string + children*: seq[CSSBox] + + CSSColor* = tuple[r: uint8, g: uint8, b: uint8, a: uint8] + +func `+`(a: CSSRect, b: CSSRect): CSSRect = + result.x1 = a.x1 + b.x1 + result.y1 = a.y1 + b.y1 + result.x2 = a.x2 + b.x2 + result.y2 = a.y2 + b.y2 + +proc `+=`(a: var CSSRect, b: CSSRect) = + a = a + b + +func cells(l: CSSLength): int = + case l.unit + of EM_UNIT: + return int(l.num) + else: + #TODO + return int(l.num / 8) + +const colors = { + "maroon": (0x80u8, 0x00u8, 0x00u8, 0x00u8), + "red": (0xffu8, 0x00u8, 0x00u8, 0x00u8), + "orange": (0xffu8, 0xa5u8, 0x00u8, 0x00u8), + "yellow": (0xffu8, 0xffu8, 0x00u8, 0x00u8), + "olive": (0x80u8, 0x80u8, 0x00u8, 0x00u8), + "purple": (0x80u8, 0x00u8, 0x80u8, 0x00u8), + "fuchsia": (0xffu8, 0x00u8, 0x00u8, 0x00u8), + "white": (0xffu8, 0xffu8, 0xffu8, 0x00u8), + "lime": (0x00u8, 0xffu8, 0x00u8, 0x00u8), + "green": (0x00u8, 0x80u8, 0x00u8, 0x00u8), + "navy": (0x00u8, 0x00u8, 0x80u8, 0x00u8), + "blue": (0x00u8, 0x00u8, 0xffu8, 0x00u8), + "aqua": (0x00u8, 0xffu8, 0xffu8, 0x00u8), + "teal": (0x00u8, 0x80u8, 0x80u8, 0x00u8), + "black": (0x00u8, 0x00u8, 0x00u8, 0x00u8), + "silver": (0xc0u8, 0xc0u8, 0xc0u8, 0x00u8), + "gray": (0x80u8, 0x80u8, 0x80u8, 0x00u8), +}.toTable() + +const defaultColor = (0xffu8, 0xffu8, 0xffu8, 0x00u8) + +func cssLength(val: float64, unit: string): CSSLength = + case unit + of "%": return CSSLength(num: val, unit: PERC_UNIT) + of "cm": return CSSLength(num: val, unit: CM_UNIT) + of "mm": return CSSLength(num: val, unit: MM_UNIT) + of "in": return CSSLength(num: val, unit: IN_UNIT) + of "px": return CSSLength(num: val, unit: PX_UNIT) + of "pt": return CSSLength(num: val, unit: PT_UNIT) + of "pc": return CSSLength(num: val, unit: PC_UNIT) + of "em": return CSSLength(num: val, unit: EM_UNIT) + of "ex": return CSSLength(num: val, unit: EX_UNIT) + of "ch": return CSSLength(num: val, unit: CH_UNIT) + of "rem": return CSSLength(num: val, unit: REM_UNIT) + of "vw": return CSSLength(num: val, unit: VW_UNIT) + of "vh": return CSSLength(num: val, unit: VH_UNIT) + of "vmin": return CSSLength(num: val, unit: VMIN_UNIT) + of "vmax": return CSSLength(num: val, unit: VMAX_UNIT) + else: return CSSLength(num: 0, unit: EM_UNIT) + +func cssColor*(d: CSSDeclaration): CSSColor = + if d.value.len > 0: + if d.value[0] of CSSToken: + let tok = CSSToken(d.value[0]) + case tok.tokenType + of CSS_HASH_TOKEN: + let s = tok.value + if s.len == 3: + for r in s: + if hexValue(r) == -1: + return + let r = hexValue(s[0]) * 0x10 + hexValue(s[0]) + let g = hexValue(s[1]) * 0x10 + hexValue(s[1]) + let b = hexValue(s[2]) * 0x10 + hexValue(s[2]) + + return (uint8(r), uint8(g), uint8(b), 0x00u8) + elif s.len == 6: + for r in s: + if hexValue(r) == -1: + return + let r = hexValue(s[0]) * 0x10 + hexValue(s[1]) + let g = hexValue(s[2]) * 0x10 + hexValue(s[3]) + let b = hexValue(s[4]) * 0x10 + hexValue(s[5]) + return (uint8(r), uint8(g), uint8(b), 0x00u8) + else: + return defaultColor + of CSS_IDENT_TOKEN: + let s = tok.value + eprint "ident", s + if $s in colors: + return colors[$s] + else: + return defaultColor + else: + eprint "else", tok.tokenType + return defaultColor + elif d of CSSFunction: + let f = CSSFunction(d.value[0]) + eprint "func", f.name + #todo calc etc (cssnumber function or something) + case $f.name + of "rgb": + if f.value.len != 3: + return defaultColor + for c in f.value: + if c != CSS_NUMBER_TOKEN: + return defaultColor + let r = CSSToken(f.value[0]).nvalue + let g = CSSToken(f.value[1]).nvalue + let b = CSSToken(f.value[2]).nvalue + return (uint8(r), uint8(g), uint8(b), 0x00u8) + of "rgba": + if f.value.len != 4: + eprint "too few args" + return defaultColor + for c in f.value: + if c != CSS_NUMBER_TOKEN: + eprint "not number" + return defaultColor + let r = CSSToken(f.value[0]).nvalue + let g = CSSToken(f.value[1]).nvalue + let b = CSSToken(f.value[2]).nvalue + let a = CSSToken(f.value[3]).nvalue + return (uint8(r), uint8(g), uint8(b), uint8(a)) + else: + eprint "not rgba" + return defaultColor + + return defaultColor + +func cssLength(d: CSSDeclaration): CSSLength = + if d.value.len > 0 and d.value[0] of CSSToken: + let tok = CSSToken(d.value[0]) + case tok.tokenType + of CSS_PERCENTAGE_TOKEN: + return cssLength(tok.nvalue, "%") + of CSS_DIMENSION_TOKEN: + return cssLength(tok.nvalue, $tok.unit) + of CSS_IDENT_TOKEN: + if $tok.value == "auto": + return CSSLength(num: 0, unit: EM_UNIT, auto: true) + else: + return CSSLength(num: 0, unit: EM_UNIT) + + return CSSLength(num: 0, unit: EM_UNIT) + +func hasColor*(style: CSS2Properties): bool = + return style.color.r != 0 or style.color.b != 0 or style.color.g != 0 or style.color.a != 0 + +func termColor*(style: CSS2Properties): ForegroundColor = + if style.color.r > 120: + return fgRed + elif style.color.b > 120: + return fgBlue + elif style.color.g > 120: + return fgGreen + else: + return fgWhite + +proc applyProperties*(box: CSSBox, s: string) = + let decls = parseCSSListOfDeclarations(newStringStream(s)) + if box.props == nil: + box.props = CSS2Properties() + let props = box.props + + for item in decls: + if item of CSSDeclaration: + let d = CSSDeclaration(item) + case $d.name + of "color": + props.color = cssColor(d) + eprint props.color #TODO + of "margin": + let l = cssLength(d) + props.margintop = l + props.marginbottom = l + props.marginleft = l + props.marginright = l + of "margin-top": + props.margintop = cssLength(d) + of "margin-left": + props.marginleft = cssLength(d) + of "margin-right": + props.marginright = cssLength(d) + of "margin-bottom": + props.marginbottom = cssLength(d) + else: + printc(d) #TODO + +func getLength(s: seq[Rune], start: int, wlimit: int): tuple[wrap: bool, len: int, width: int] = + var len = 0 + var width = 0 + var i = start + while i < s.len: + let r = s[i] + let cw = r.width() + if width + cw > wlimit: + return (wrap: true, len: len, width: width) + width += cw + len += 1 + + return (wrap: false, len: len, width: width) + +proc arrangeBoxes*(canvas: CSSCanvas) = + var stack: seq[CSSBox] + stack.add(canvas.rootBox) + var x = 0 + var y = 0 + + while stack.len > 0: + let box = stack.pop() + + #arrange box + box.marginEdge.x1 = x + box.marginEdge.y1 = y + x += box.props.marginleft.cells() + y += box.props.margintop.cells() + + if box.display == DISPLAY_BLOCK: + x = 0 + inc y + + if x > canvas.width: + x = 0 + inc y + + box.x = x + box.y = y + + var l = 0 + while l < box.content.len: + let (wrap, wraplen, wrapwidth) = box.content.getLength(l, canvas.width - x) + var wrapbox = new(CSSBox) + wrapbox.content = box.content.substr(l, l + wraplen) + box.children.add(wrapbox) + l += wraplen + x += wrapwidth + if wrap: + inc y + x = 0 + + x += box.props.marginright.cells() + y += box.props.marginbottom.cells() + box.marginEdge.x2 = x + box.marginEdge.y2 = y + + var i = box.children.len - 1 + while i >= 0: + stack.add(box.children[i]) + i -= 1 diff --git a/src/dom.nim b/src/html/dom.nim index c9dc367e..74ebe5ea 100644 --- a/src/dom.nim +++ b/src/html/dom.nim @@ -3,11 +3,23 @@ import uri import unicode import strutils import tables +import streams +import sequtils +import sugar -import twtstr -import twtio -import enums -import style +import ../css/style +import ../css/cssparser +import ../css/selector + +import ../types/enums +import ../types/tagtypes + +import ../utils/twtstr + +import ../io/twtio + +const css = staticRead"../../res/default.css" +let stylesheet = parseCSS(newStringStream(css)) type EventTarget* = ref EventTargetObj @@ -17,9 +29,8 @@ type NodeObj = object of EventTargetObj nodeType*: NodeType childNodes*: seq[Node] - firstChild*: Node + children*: seq[Element] isConnected*: bool - lastChild*: Node nextSibling*: Node previousSibling*: Node parentNode*: Node @@ -48,8 +59,12 @@ type Document* = ref DocumentObj DocumentObj = object of NodeObj location*: Uri - id_elements*: Table[string, Element] + type_elements*: array[low(TagType)..high(TagType), seq[Element]] + id_elements*: Table[string, seq[Element]] class_elements*: Table[string, seq[Element]] + all_elements*: seq[Element] + head*: HTMLElement + body*: HTMLElement CharacterData* = ref CharacterDataObj CharacterDataObj = object of NodeObj @@ -74,7 +89,7 @@ type id*: string classList*: seq[string] attributes*: Table[string, Attr] - style*: CSS2Properties + box*: CSSBox HTMLElement* = ref HTMLElementObj HTMLElementObj = object of ElementObj @@ -97,6 +112,9 @@ type value*: string valueSet*: bool + HTMLSpanElement* = ref HTMLSpanElementObj + HTMLSpanElementObj = object of HTMLElementObj + HTMLOptionElement* = ref HTMLOptionElementObj HTMLOptionElementObj = object of HTMLElementObj value*: string @@ -109,32 +127,28 @@ type HTMLBRElementObj = object of HTMLElementObj -func getTagTypeMap(): Table[string, TagType] = - for i in low(TagType) .. high(TagType): - let enumname = $TagType(i) - let tagname = enumname.split('_')[1..^1].join("_").tolower() - result[tagname] = TagType(i) +func firstChild(node: Node): Node = + if node.childNodes.len == 0: + return nil + return node.childNodes[0] -func getInputTypeMap(): Table[string, InputType] = - for i in low(InputType) .. high(InputType): - let enumname = $InputType(i) - let tagname = enumname.split('_')[1..^1].join("_").tolower() - result[tagname] = InputType(i) +func lastChild(node: Node): Node = + if node.childNodes.len == 0: + return nil + return node.childNodes[^1] -const tagTypeMap = getTagTypeMap() -const inputTypeMap = getInputTypeMap() +func firstElementChild(node: Node): Element = + if node.children.len == 0: + return nil + return node.children[0] -func tagType*(s: string): TagType = - if tagTypeMap.hasKey(s): - return tagTypeMap[s] - else: - return TAG_UNKNOWN +func lastElementChild(node: Node): Element = + if node.children.len == 0: + return nil + return node.children[^1] -func inputType*(s: string): InputType = - if inputTypeMap.hasKey(s): - return inputTypeMap[s] - else: - return INPUT_UNKNOWN +func `$`*(element: Element): string = + return "Element of " & $element.tagType #TODO func nodeAttr*(node: Node): HtmlElement = @@ -145,8 +159,8 @@ func nodeAttr*(node: Node): HtmlElement = func getStyle*(node: Node): CSS2Properties = case node.nodeType - of TEXT_NODE: return node.parentElement.style - of ELEMENT_NODE: return Element(node).style + of TEXT_NODE: return node.parentElement.box.props + of ELEMENT_NODE: return Element(node).box.props else: assert(false) func displayed*(node: Node): bool = @@ -243,6 +257,7 @@ proc getRawText*(htmlNode: Node): string = else: return "" elif htmlNode.isTextNode(): let chardata = CharacterData(htmlNode) + #eprint "char data", chardata.data if htmlNode.parentElement != nil and htmlNode.parentElement.tagType != TAG_PRE: result = chardata.data.remove("\n") if unicode.strip(result).runeLen() > 0: @@ -257,39 +272,33 @@ proc getRawText*(htmlNode: Node): string = else: assert(false) -func getFmtText*(htmlNode: Node): seq[string] = - if htmlNode.isElemNode(): - case HtmlElement(htmlNode).tagType - of TAG_INPUT: return HtmlInputElement(htmlNode).getFmtInput() +func getFmtText*(node: Node): seq[string] = + if node.isElemNode(): + case HtmlElement(node).tagType + of TAG_INPUT: return HtmlInputElement(node).getFmtInput() else: return @[] - elif htmlNode.isTextNode(): - let chardata = CharacterData(htmlNode) + elif node.isTextNode(): + let chardata = CharacterData(node) result &= chardata.data - if htmlNode.parentElement != nil: - if htmlNode.parentElement.style.islink: - result = result.ansiFgColor(fgBlue).ansiReset() - let anchor = htmlNode.ancestor(TAG_A) - if anchor != nil and anchor.style.selected: - result = result.ansiStyle(styleUnderscore).ansiReset() - - if htmlNode.parentElement.tagType == TAG_OPTION: + if node.parentElement != nil: + let style = node.getStyle() + if style.hasColor(): + result = result.ansiFgColor(style.termColor()) + + if node.parentElement.tagType == TAG_OPTION: result = result.ansiFgColor(fgRed).ansiReset() - if htmlNode.parentElement.style.bold: + if style.bold: result = result.ansiStyle(styleBright).ansiReset() - if htmlNode.parentElement.style.italic: + if style.italic: result = result.ansiStyle(styleItalic).ansiReset() - if htmlNode.parentElement.style.underscore: + if style.underscore: result = result.ansiStyle(styleUnderscore).ansiReset() else: - assert(false, "Uhhhh I'm pretty sure we should have parent elements for text nodes?" & htmlNode.rawtext) + assert(false, node.rawtext) else: assert(false) -func newDocument*(): Document = - new(result) - result.nodeType = DOCUMENT_NODE - func newText*(): Text = new(result) result.nodeType = TEXT_NODE @@ -298,6 +307,10 @@ func newComment*(): Comment = new(result) result.nodeType = COMMENT_NODE +func newBox*(element: HTMLElement): CSSBox = + new(result) + result.props = CSS2Properties() + func newHtmlElement*(tagType: TagType): HTMLElement = case tagType of TAG_INPUT: @@ -312,12 +325,20 @@ func newHtmlElement*(tagType: TagType): HTMLElement = result = new(HTMLHeadingElement) of TAG_BR: result = new(HTMLBRElement) + of TAG_SPAN: + result = new(HTMLSpanElement) else: new(result) result.nodeType = ELEMENT_NODE result.tagType = tagType - result.style = new(CSS2Properties) + result.box = result.newBox() + +func newDocument*(): Document = + new(result) + result.head = newHtmlElement(TAG_HEAD) + result.body = newHtmlElement(TAG_BODY) + result.nodeType = DOCUMENT_NODE func newAttr*(parent: Element, key: string, value: string): Attr = new(result) @@ -332,27 +353,140 @@ func getAttrValue*(element: Element, s: string): string = return attr.value return "" +#TODO case sensitivity +func attrSelectorMatches(elem: Element, sel: Selector): bool = + case sel.rel + of ' ': return sel.attr in elem.attributes + of '=': return elem.getAttrValue(sel.attr) == sel.value + of '~': return sel.value in unicode.split(elem.getAttrValue(sel.attr)) + of '|': + let val = elem.getAttrValue(sel.attr) + return val == sel.value or sel.value.startsWith(val & '-') + of '^': return elem.getAttrValue(sel.attr).startsWith(sel.value) + of '$': return elem.getAttrValue(sel.attr).endsWith(sel.value) + of '*': return elem.getAttrValue(sel.attr).contains(sel.value) + else: return false + +func pseudoSelectorMatches(elem: Element, sel: Selector): bool = + case sel.pseudo + of "first-child": return elem.parentNode.firstElementChild == elem + of "last-child": return elem.parentNode.lastElementChild == elem + else: return false + +func pseudoElemSelectorMatches(elem: Element, sel: Selector): bool = + case sel.elem + of "after": return false + of "before": return false + else: return false + +func selectorMatches(elem: Element, sel: Selector): bool = + case sel.t + of TYPE_SELECTOR: + return elem.tagType == sel.tag + of CLASS_SELECTOR: + return sel.class in elem.classList + of ID_SELECTOR: + return sel.id == elem.id + of ATTR_SELECTOR: + return elem.attrSelectorMatches(sel) + of PSEUDO_SELECTOR: + return pseudoSelectorMatches(elem, sel) + of PSELEM_SELECTOR: + return pseudoElemSelectorMatches(elem, sel) + of UNIVERSAL_SELECTOR: + return true + of FUNC_SELECTOR: + return false + +func selectorsMatch(elem: Element, selectors: SelectorList): bool = + for sel in selectors.sels: + if not selectorMatches(elem, sel): + return false + return true + +func selectElems(document: Document, sel: Selector): seq[Element] = + case sel.t + of TYPE_SELECTOR: + return document.type_elements[sel.tag] + of ID_SELECTOR: + return document.id_elements[sel.id] + of CLASS_SELECTOR: + return document.class_elements[sel.class] + of UNIVERSAL_SELECTOR: + return document.all_elements + #TODO: following selectors are rather inefficient + of ATTR_SELECTOR: + return document.all_elements.filter((elem) => attrSelectorMatches(elem, sel)) + of PSEUDO_SELECTOR: + return document.all_elements.filter((elem) => pseudoSelectorMatches(elem, sel)) + of PSELEM_SELECTOR: + return document.all_elements.filter((elem) => pseudoElemSelectorMatches(elem, sel)) + of FUNC_SELECTOR: + if sel.name == "not": + return document.all_elements.filter((elem) => not selectorsMatch(elem, sel.selectors)) + return newSeq[Element]() + +func optimizeSelectorList(selectors: SelectorList): SelectorList = + new(result) + #pass 1: check for invalid sequences + var i = 1 + while i < selectors.len: + let sel = selectors[i] + if sel.t == TYPE_SELECTOR or sel.t == UNIVERSAL_SELECTOR: + return SelectorList() + inc i + + #pass 2: move selectors in combination + if selectors.len > 1: + var i = 0 + var slow = SelectorList() + if selectors[0].t == UNIVERSAL_SELECTOR: + inc i + + while i < selectors.len: + if selectors[i].t in {ATTR_SELECTOR, PSEUDO_SELECTOR, PSELEM_SELECTOR}: + slow.add(selectors[i]) + else: + result.add(selectors[i]) + inc i -#type -# SelectorType = enum -# TYPE_SELECTOR, ID_SELECTOR, ATTR_SELECTOR, CLASS_SELECTOR, CHILD_SELECTOR, -# UNIVERSAL_SELECTOR -# -# Selector = object -# t: SelectorType -# s0: string -# s1: string -# -#proc querySelector*(document: Document, q: string): seq[Element] = -# #let ss = newStringStream(q) -# #let cvals = parseCSSListOfComponentValues(ss) -# #var selectors: seq[Selector] -# return -# -# #for cval in cvals: -# # if cval of CSSToken: -# # case CSSToken(cval).tokenType -# # of CSS_DELIM_TOKEN: -# # if cval.rvalue == Rune('*'): -# # selectors.add(Selector(t)) -# # printc(cval) + result.add(slow) + else: + result.add(selectors[0]) + +func selectElems(document: Document, selectors: SelectorList): seq[Element] = + assert(selectors.len > 0) + let sellist = optimizeSelectorList(selectors) + result = document.selectElems(selectors[0]) + var i = 1 + + while i < sellist.len: + if sellist[i].t == FUNC_SELECTOR: + if sellist[i].name == "not": + result = result.filter((elem) => not selectorsMatch(elem, sellist[i].selectors)) + else: + result = result.filter((elem) => selectorMatches(elem, sellist[i])) + inc i + +proc querySelector*(document: Document, q: string): seq[Element] = + let ss = newStringStream(q) + let cvals = parseCSSListOfComponentValues(ss) + let selectors = parseSelectors(cvals) + + for sel in selectors: + result.add(document.selectElems(sel)) + +proc applyRule(elem: Element, rule: CSSRule) = + let selectors = parseSelectors(rule.prelude) + for sel in selectors: + if elem.selectorsMatch(sel): + eprint "match!" + +proc applyRules(document: Document, rules: CSSStylesheet) = + var stack: seq[Element] + + stack.add(document.firstElementChild) + while stack.len > 0: + let elem = stack.pop() + for child in elem.children: + stack.add(child) diff --git a/src/entity.nim b/src/html/entity.nim index dcac258e..79c57ca0 100644 --- a/src/entity.nim +++ b/src/html/entity.nim @@ -1,24 +1,23 @@ -import radixtree import json +import ../utils/radixtree + +const entity = staticRead"../../res/entity.json" when defined(small): - proc genEntityMap(data: seq[tuple[a: string, b: string]]): StaticRadixTree[string] = - result = newStaticRadixTree[string]() + proc genEntityMap(data: seq[tuple[a: string, b: string]]): RadixNode[string] = + result = newRadixTree[string]() for pair in data: result[pair.a] = pair.b - proc genEntityHashMap(): seq[tuple[a: string, b: string]] = - let entity = staticRead"../res/entity.json" + proc genEntityTable(): seq[tuple[a: string, b: string]] = let entityJson = parseJson(entity) for k, v in entityJson: result.add((k.substr(1), v{"characters"}.getStr())) - const entityHashMap = genEntityHashMap() - let entityMap* = genEntityMap(entityHashMap) #TODO: use refs here + const entityTable = genEntityTable() + let entityMap* = genEntityMap(entityTable) else: - import tables proc genEntityMap(): StaticRadixTree[string] = - let entity = staticRead"../res/entity.json" let entityJson = parseJson(entity) var entityMap = newStaticRadixTree[string]() diff --git a/src/htmlparser.nim b/src/html/htmlparser.nim index 86065ef7..f43bcf40 100644 --- a/src/htmlparser.nim +++ b/src/html/htmlparser.nim @@ -4,11 +4,15 @@ import strutils import tables import json -import twtio -import enums -import twtstr +import ../types/enums +import ../types/tagtypes + +import ../utils/twtstr +import ../utils/radixtree + +import ../io/twtio + import dom -import radixtree import entity type @@ -23,6 +27,7 @@ type in_script: bool in_style: bool in_noscript: bool + in_body: bool parentNode: Node textNode: Text @@ -148,21 +153,39 @@ proc getescapecmd(buf: string, at: var int): string = elif not isAlphaAscii(buf[i]): return "" - var n = 0 - var s = "" - while true: - s &= buf[i] - if not entityMap.hasPrefix(s, n): - break - let pn = n - n = entityMap{s, n} - if n != pn: - s = "" - inc i + #TODO this could be way more efficient (and radixnode needs better interface) + when defined(small): + var n = entityMap + var s = "" + while true: + s &= buf[i] + if not entityMap.hasPrefix(s, n): + break + let pn = n + n = n{s} + if n != pn: + s = "" + inc i - if entityMap.nodes[n].leaf: - at = i - return entityMap.nodes[n].value + if n.leaf: + at = i + return n.value + else: + var n = 0 + var s = "" + while true: + s &= buf[i] + if not entityMap.hasPrefix(s, n): + break + let pn = n + n = entityMap{s, n} + if n != pn: + s = "" + inc i + + if entityMap.nodes[n].leaf: + at = i + return entityMap.nodes[n].value return "" @@ -232,11 +255,6 @@ proc parse_tag(buf: string, at: var int): DOMParsedTag = proc insertNode(parent: Node, node: Node) = parent.childNodes.add(node) - if parent.firstChild == nil: - parent.firstChild = node - - parent.lastChild = node - if parent.childNodes.len > 1: let prevSibling = parent.childNodes[^1] prevSibling.nextSibling = node @@ -244,14 +262,43 @@ proc insertNode(parent: Node, node: Node) = node.parentNode = parent if parent.nodeType == ELEMENT_NODE: - node.parentElement = Element(parent) + node.parentElement = (Element)parent if parent.ownerDocument != nil: node.ownerDocument = parent.ownerDocument elif parent.nodeType == DOCUMENT_NODE: - node.ownerDocument = Document(parent) + node.ownerDocument = (Document)parent + + if node.nodeType == ELEMENT_NODE: + parent.children.add((Element)node) + + let element = ((Element)node) + if element.ownerDocument != nil: + node.ownerDocument.all_elements.add((Element)node) + element.ownerDocument.type_elements[element.tagType].add(element) + if element.id != "": + if not (element.id in element.ownerDocument.id_elements): + element.ownerDocument.id_elements[element.id] = newSeq[Element]() + element.ownerDocument.id_elements[element.id].add(element) + + for c in element.classList: + if not (c in element.ownerDocument.class_elements): + element.ownerDocument.class_elements[c] = newSeq[Element]() + element.ownerDocument.class_elements[c].add(element) + +proc processDocumentBody(state: var HTMLParseState) = + if not state.in_body: + state.in_body = true + if state.parentNode.ownerDocument != nil: + state.parentNode = state.parentNode.ownerDocument.body proc processDocumentStartNode(state: var HTMLParseState, newNode: Node) = + if state.parentNode.nodeType == ELEMENT_NODE and ((Element)state.parentNode).tagType == TAG_HTML: + if state.in_body: + state.parentNode = state.parentNode.ownerDocument.body + else: + state.parentNode = state.parentNode.ownerDocument.head + insertNode(state.parentNode, newNode) state.parentNode = newNode @@ -261,6 +308,8 @@ proc processDocumentEndNode(state: var HTMLParseState) = state.parentNode = state.parentNode.parentNode proc processDocumentText(state: var HTMLParseState) = + if state.textNode != nil and state.textNode.data.len > 0: + processDocumentBody(state) if state.textNode == nil: state.textNode = newText() @@ -268,6 +317,8 @@ proc processDocumentText(state: var HTMLParseState) = processDocumentEndNode(state) proc processDocumentStartElement(state: var HTMLParseState, element: Element, tag: DOMParsedTag) = + var add = true + for k, v in tag.attrs: element.attributes[k] = element.newAttr(k, v) @@ -294,6 +345,13 @@ proc processDocumentStartElement(state: var HTMLParseState, element: Element, ta HTMLAnchorElement(element).href = element.getAttrValue("href") of TAG_OPTION: HTMLOptionElement(element).value = element.getAttrValue("href") + of TAG_HTML: + add = false + of TAG_HEAD: + add = false + of TAG_BODY: + add = false + processDocumentBody(state) else: discard if state.parentNode.nodeType == ELEMENT_NODE: @@ -315,13 +373,8 @@ proc processDocumentStartElement(state: var HTMLParseState, element: Element, ta HTMLHeadingElement(element).rank = 6 else: discard - processDocumentStartNode(state, element) - if element.ownerDocument != nil: - for c in element.classList: - element.ownerDocument.id_elements[c] = element - if not (c in element.ownerDocument.class_elements): - element.ownerDocument.class_elements[c] = newSeq[Element]() - element.ownerDocument.class_elements[c].add(element) + if add: + processDocumentStartNode(state, element) if element.tagType in VoidTagTypes: processDocumentEndNode(state) @@ -329,6 +382,11 @@ proc processDocumentStartElement(state: var HTMLParseState, element: Element, ta proc processDocumentEndElement(state: var HTMLParseState, tag: DOMParsedTag) = if tag.tagid in VoidTagTypes: return + if tag.tagid == TAG_HEAD: + state.in_body = true + return + if tag.tagid == TAG_BODY: + return if state.parentNode.nodeType == ELEMENT_NODE: if Element(state.parentNode).tagType in {TAG_LI, TAG_P}: processDocumentEndNode(state) @@ -395,6 +453,12 @@ proc processDocumentPart(state: var HTMLParseState, buf: string) = if state.textNode != nil: state.textNode.rawtext = state.textNode.getRawText() state.textNode = nil + else: + #TODO for doctype + while p < max and buf[p] != '>': + inc p + at = p + continue if not state.in_comment: if state.textNode != nil: @@ -439,9 +503,14 @@ proc processDocumentPart(state: var HTMLParseState, buf: string) = proc parseHtml*(inputStream: Stream): Document = let document = newDocument() + let html = newHtmlElement(TAG_HTML) + insertNode(document, html) + insertNode(html, document.head) + insertNode(html, document.body) + #eprint document.body.firstElementChild != nil var state = HTMLParseState() - state.parentNode = document + state.parentNode = html var till_when = false diff --git a/src/display.nim b/src/io/display.nim index d7d69c4a..e3ce6bac 100644 --- a/src/display.nim +++ b/src/io/display.nim @@ -4,13 +4,17 @@ import uri import strutils import unicode -import buffer -import termattrs -import dom -import twtstr +import ../types/enums + +import ../utils/termattrs +import ../utils/twtstr + +import ../html/dom + +import ../buffer +import ../config + import twtio -import config -import enums proc clearStatusMsg*(at: int) = setCursorPos(0, at) @@ -81,7 +85,7 @@ proc writeWrappedText(buffer: Buffer, state: var RenderState, node: Node) = for r in w.runes: if r == Rune(' '): - if rawword.len > 0 and rawword[0] == ' ' and prevl: #first byte can't fool comparison to ascii + if rawword.len > 0 and rawword[0] == ' ' and prevl: fmtword = fmtword.substr(1) rawword = rawword.substr(1) state.x -= 1 @@ -124,15 +128,15 @@ proc preAlignNode(buffer: Buffer, node: Node, state: var RenderState) = buffer.flushLine(state) if node.firstNode(): - while state.blanklines < max(style.margin, style.margintop): - buffer.flushLine(state) + #while state.blanklines < max(style.margin, style.margintop): + # buffer.flushLine(state) state.indent += style.indent if state.rawline.len > 0 and state.blanklines == 0 and node.displayed(): buffer.addSpaces(state, state.nextspaces) state.nextspaces = 0 - if state.blankspaces < max(style.margin, style.marginleft): - buffer.addSpaces(state, max(style.margin, style.marginleft) - state.blankspaces) + #if state.blankspaces < max(style.margin, style.marginleft): + # buffer.addSpaces(state, max(style.margin, style.marginleft) - state.blankspaces) if style.centered and state.rawline.len == 0 and node.displayed(): buffer.addSpaces(state, max(buffer.width div 2 - state.centerlen div 2, 0)) @@ -162,14 +166,14 @@ proc postAlignNode(buffer: Buffer, node: Node, state: var RenderState) = state.blanklines = 0 state.blankspaces = 0 - if state.rawline.len > 0 and state.blanklines == 0: - state.nextspaces += max(style.margin, style.marginright) - #if node.lastNode() and (node.isTextNode() or elem.childNodes.len == 0): - # buffer.flushLine(state) + #if state.rawline.len > 0 and state.blanklines == 0: + # state.nextspaces += max(style.margin, style.marginright) + # if node.lastNode() and (node.isTextNode() or elem.childNodes.len == 0): + # buffer.flushLine(state) if node.lastNode(): - while state.blanklines < max(style.margin, style.marginbottom): - buffer.flushLine(state) + #while state.blanklines < max(style.margin, style.marginbottom): + # buffer.flushLine(state) state.indent -= style.indent if style.display == DISPLAY_LIST_ITEM and node.lastNode(): diff --git a/src/io/twtio.nim b/src/io/twtio.nim new file mode 100644 index 00000000..34cf4ce6 --- /dev/null +++ b/src/io/twtio.nim @@ -0,0 +1,323 @@ +import terminal +import tables +import unicode +import strutils +import sequtils + +import ../utils/twtstr +import ../utils/radixtree + +import ../config + +template print*(s: varargs[string, `$`]) = + for x in s: + stdout.write(x) + +template printesc*(s: string) = + for r in s.runes: + if r.isControlChar(): + stdout.write(('^' & $($r)[0].getControlLetter()) + .ansiFgColor(fgBlue).ansiStyle(styleBright).ansiReset()) + else: + stdout.write($r) + +template printspc(i: int) = + print(' '.repeat(i)) + +template eprint*(s: varargs[string, `$`]) = {.cast(noSideEffect).}: + var a = false + for x in s: + if not a: + a = true + else: + stderr.write(' ') + stderr.write(x) + stderr.write('\n') + +proc termGoto*(x: int, y: int) = + setCursorPos(stdout, x, y) + +proc getNormalAction*(s: string): TwtAction = + if normalActionRemap.hasKey(s): + return normalActionRemap[s] + return NO_ACTION + +proc getLinedAction*(s: string): TwtAction = + if linedActionRemap.hasKey(s): + return linedActionRemap[s] + return NO_ACTION + +type LineState = object + news: seq[Rune] + s: string + feedNext: bool + escNext: bool + comp: bool + compn: RadixNode[string] + compa: int + comps: string + cursor: int + shift: int + minlen: int + maxlen: int + displen: int + spaces: seq[string] + +proc backward(state: LineState, i: int) = + if i == 1: + print('\b') + else: + cursorBackward(i) + +proc forward(state: LineState, i: int) = + cursorForward(i) + +proc begin(state: LineState) = + print('\r') + + state.forward(state.minlen) + +proc space(state: LineState, i: int) = + print(state.spaces[i]) + +proc kill(state: LineState) = + when defined(windows): + let w = min(state.news.width(state.cursor), state.displen) + state.space(w) + state.backward(w) + else: + print("\e[K") + +proc fullRedraw(state: var LineState) = + state.displen = state.maxlen - 1 + if state.cursor > state.shift: + var shiftw = state.news.width(state.shift, state.cursor) + while shiftw > state.maxlen - 1: + inc state.shift + shiftw -= state.news[state.shift].width() + else: + state.shift = max(state.cursor - 1, 0) + + var dispw = state.news.width(state.shift, state.shift + state.displen) + if state.shift + state.displen > state.news.len: + state.displen = state.news.len - state.shift + while dispw > state.maxlen - 1: + dispw -= state.news[state.shift + state.displen - 1].width() + dec state.displen + + state.begin() + let os = state.news.substr(state.shift, state.shift + state.displen) + printesc($os) + state.space(max(state.maxlen - os.width(), 0)) + + state.begin() + state.forward(state.news.width(state.shift, state.cursor)) + +proc zeroShiftRedraw(state: var LineState) = + state.shift = 0 + state.displen = state.maxlen - 1 + + var dispw = state.news.width(0, state.displen) + if state.displen > state.news.len: + state.displen = state.news.len + while dispw > state.maxlen - 1: + dispw -= state.news[state.displen - 1].width() + dec state.displen + + state.begin() + let os = state.news.substr(0, state.displen) + printesc($os) + state.space(max(state.maxlen - os.width(), 0)) + + state.begin() + state.forward(state.news.width(0, state.cursor)) + +proc insertCharseq(state: var LineState, cs: var seq[Rune]) = + let escNext = state.escNext + cs.keepIf(func(r: Rune): bool = escNext or not r.isControlChar()) + state.escNext = false + if cs.len == 0: + return + elif state.cursor >= state.news.len and state.news.width(state.shift, state.cursor) + cs.width() < state.displen: + state.news &= cs + state.cursor += cs.len + printesc($cs) + else: + state.news.insert(cs, state.cursor) + state.cursor += cs.len + state.fullRedraw() + +proc insertCompose(state: var LineState, c: char) = + state.comps &= c + let n = state.compn{state.comps} + if n != state.compn: + state.compn = n + state.compa += state.comps.len + state.comps = "" + if state.compn.hasPrefix(state.comps, state.compn) and n.children.len > 0: + state.feedNext = true + else: + var cs: seq[Rune] + if state.compn.leaf: + cs = state.compn.value.toRunes() + else: + cs = state.s.substr(0, state.compa - 1).toRunes() + state.comps = state.s.substr(state.compa) + if state.comps.len > 0 and composeRemap.hasPrefix(state.comps): + state.compa = state.comps.len + state.compn = composeRemap{state.comps} + state.s = state.comps + state.comps = "" + state.feedNext = true + else: + cs &= state.comps.toRunes() + state.compa = 0 + state.compn = composeRemap + state.comps = "" + + state.insertCharseq(cs) + +proc readLine*(current: var string, minlen: int, maxlen: int): bool = + var state: LineState + state.news = current.toRunes() + state.compn = composeRemap + state.cursor = state.news.len + state.minlen = minlen + state.maxlen = maxlen + state.displen = state.maxlen - 1 + #ugh + for i in 0..(maxlen - minlen): + state.spaces.add(' '.repeat(i)) + printesc(current) + while true: + if not state.feedNext: + state.s = "" + else: + state.feedNext = false + + let c = getch() + state.s &= c + + var action = getLinedAction(state.s) + if state.escNext: + action = NO_ACTION + case action + of ACTION_LINED_CANCEL: + return false + of ACTION_LINED_SUBMIT: + current = $state.news + return true + of ACTION_LINED_BACKSPACE: + if state.cursor > 0: + state.news.delete(state.cursor - 1, state.cursor - 1) + dec state.cursor + state.fullRedraw() + of ACTION_LINED_DELETE: + if state.cursor > 0 and state.cursor < state.news.len: + state.news.delete(state.cursor, state.cursor) + state.fullRedraw() + of ACTION_LINED_ESC: + state.escNext = true + of ACTION_LINED_CLEAR: + if state.cursor > 0: + state.news.delete(0, state.cursor - 1) + state.cursor = 0 + state.zeroShiftRedraw() + of ACTION_LINED_KILL: + if state.cursor < state.news.len: + state.kill() + state.news.setLen(state.cursor) + of ACTION_LINED_BACK: + if state.cursor > 0: + dec state.cursor + if state.cursor > state.shift or state.shift == 0: + state.backward(state.news[state.cursor].width()) + else: + state.fullRedraw() + of ACTION_LINED_FORWARD: + if state.cursor < state.news.len: + inc state.cursor + if state.news.width(state.shift, state.cursor) < state.displen: + var n = 1 + if state.news.len > state.cursor: + n = state.news[state.cursor].width() + state.forward(n) + else: + state.fullRedraw() + of ACTION_LINED_PREV_WORD: + let oc = state.cursor + while state.cursor > 0: + dec state.cursor + if state.news[state.cursor].breaksWord(): + break + if state.cursor != oc: + if state.cursor > state.shift or state.shift == 0: + state.backward(state.news.width(state.cursor, oc)) + else: + state.fullRedraw() + of ACTION_LINED_NEXT_WORD: + let oc = state.cursor + while state.cursor < state.news.len: + inc state.cursor + if state.cursor < state.news.len: + if state.news[state.cursor].breaksWord(): + break + + if state.cursor != oc: + let dw = state.news.width(oc, state.cursor) + if oc + dw - state.shift < state.displen: + state.forward(dw) + else: + state.fullRedraw() + of ACTION_LINED_KILL_WORD: + var chars = 0 + if state.cursor > chars: + inc chars + + while state.cursor > chars: + inc chars + if state.news[state.cursor - chars].breaksWord(): + dec chars + break + if chars > 0: + let w = state.news.width(state.cursor - chars, state.cursor) + state.news.delete(state.cursor - chars, state.cursor - 1) + state.cursor -= chars + if state.cursor > state.news.len and state.shift == 0: + state.backward(w) + state.space(w) + state.backward(w) + else: + state.fullRedraw() + of ACTION_LINED_BEGIN: + if state.cursor > 0: + if state.shift == 0: + state.backward(state.news.width(0, state.cursor)) + else: + state.fullRedraw() + state.cursor = 0 + of ACTION_LINED_END: + if state.cursor < state.news.len: + if state.news.width(state.shift, state.news.len) < maxlen: + state.forward(state.news.width(state.cursor, state.news.len)) + else: + state.fullRedraw() + state.cursor = state.news.len + of ACTION_LINED_COMPOSE_TOGGLE: + state.comp = not state.comp + state.compn = composeRemap + state.compa = 0 + state.comps = "" + of ACTION_FEED_NEXT: + state.feedNext = true + elif state.comp: + state.insertCompose(c) + elif validateUtf8(state.s) == -1: + var cs = state.s.toRunes() + state.insertCharseq(cs) + else: + state.feedNext = true + +proc readLine*(prompt: string, current: var string, termwidth: int): bool = + printesc(prompt) + readLine(current, prompt.width(), termwidth - prompt.len) diff --git a/src/main.nim b/src/main.nim index 95f1f3cd..539527f1 100644 --- a/src/main.nim +++ b/src/main.nim @@ -3,14 +3,18 @@ import uri import os import streams -import display -import termattrs +import css/style + +import utils/termattrs + +import html/dom +import html/htmlparser + +import io/display +import io/twtio + import buffer -import twtio import config -import htmlparser -import dom -import style let clientInstance = newHttpClient() proc loadRemotePage*(url: string): string = @@ -39,16 +43,17 @@ proc main*() = if paramCount() != 1: eprint "Invalid parameters. Usage:\ntwt <url>" quit(1) - if not readConfig("config"): - eprint "Failed to read keymap, falling back to default" + if not readConfig("res/config"): + eprint "Failed to read keymap, fallback to default" let attrs = getTermAttributes() let buffer = newBuffer(attrs) let uri = parseUri(paramStr(1)) buffers.add(buffer) buffer.document = parseHtml(getPageUri(uri)) - #discard buffer.document.querySelector("#hi.a[title=\"test\"]") - var box = CSSBox() - applyProperties(box, "color: #090; line-height: 1.2") + let s = buffer.document.querySelector(":not(:first-child)") + eprint s.len + for q in s: + eprint q buffer.setLocation(uri) buffer.renderHtml() var lastUri = uri @@ -65,6 +70,5 @@ proc main*() = buffer.document = parseHtml(getPageUri(buffer.document.location)) buffer.renderHtml() lastUri = newUri - main() #parseCSS(newFileStream("default.css", fmRead)) diff --git a/src/radixtree.nim b/src/radixtree.nim deleted file mode 100644 index 0d9db3ab..00000000 --- a/src/radixtree.nim +++ /dev/null @@ -1,440 +0,0 @@ -# Radix tree implementation, with some caveats: -# * insertion takes forever, so try to insert only during compile-time -# * it isn't that much faster than a hash table, even when used for e.g. parsing -# -# Update: now it also has a version using references. Should be somewhat faster -# at the cost of having to initialize it every time the program is started. - -import strutils -import json -import tables - -type - RadixPair[T] = tuple[k: string, v: RadixNode[T]] - - RadixNode*[T] = ref object - children*: seq[RadixPair[T]] - case leaf*: bool - of true: value*: T - of false: discard - - StaticRadixPair = tuple[k: string, v: int] - StaticRadixPairSeq = seq[StaticRadixPair] - - StaticRadixNode[T] = object - children*: StaticRadixPairSeq - case leaf*: bool - of true: value*: T - of false: discard - - StaticRadixTree*[T] = object - nodes*: seq[StaticRadixNode[T]] - -func newStaticRadixTree*[T](): StaticRadixTree[T] = - result.nodes.add(StaticRadixNode[T](leaf: false)) - -func newRadixTree*[T](): RadixNode[T] = - new(result) - -func toRadixTree*[T](table: Table[string, T]): RadixNode[T] = - result = newRadixTree[T]() - for k, v in table: - result[k] = v - -# PairSeq Insert: theoretically this should only be called when there's no -# conflicts... TODO: so we should be able to just compare the first char? -# probably a bad idea... -proc `[]=`(pairseq: var StaticRadixPairSeq, k: string, v: int) = - var i = 0 - while i < pairseq.len: - if pairseq[i].k == k: - pairseq[i].v = v - return - inc i - - pairseq.add((k: k, v: v)) - -proc `[]=`[T](node: RadixNode[T], k: string, n: RadixNode[T]) = - var i = 0 - assert(k.len > 0) - while i < node.children.len: - if node.children[i].k == k: - node.children[i].v = n - return - inc i - - node.children.add((k: k, v: n)) - -# PairSeq Lookup: since we're sure k is in pairseq, return the first match. -func `[]`(pairseq: StaticRadixPairSeq, k: string): int = - var i = 0 - while i < pairseq.len: - if pairseq[i].k[0] == k[0]: - return pairseq[i].v - inc i - - return -1 - -func `[]`[T](node: RadixNode[T], k: string): RadixNode[T] = - var i = 0 - while i < node.children.len: - if node.children[i].k[0] == k[0]: - return node.children[i].v - inc i - - return nil - -# getOrDefault: we have to compare the entire string but if it doesn't match -# exactly we can just return default. -func getOrDefault(pairseq: StaticRadixPairSeq, k: string, default: int): int = - var i = 0 - while i < pairseq.len: - if pairseq[i].k[0] == k[0]: - if k.len != pairseq[i].k.len: - return default - var j = 1 - while j < k.len: - if pairseq[i].k[j] != k[j]: - return default - inc j - return pairseq[i].v - inc i - return default - -func getOrDefault[T](node: RadixNode[T], k: string, default: RadixNode[T]): RadixNode[T] = - var i = 0 - while i < node.children.len: - if node.children[i].k[0] == k[0]: - if k.len != node.children[i].k.len: - debugecho "defa: ", k, " ", node.children[i].k - return default - var j = 1 - while j < k.len: - if node.children[i].k[j] != k[j]: - return default - inc j - return node.children[i].v - inc i - return default - -func getOrDefault[T](node: RadixNode[T], k: string, default: int): int = - var i = 0 - while i < node.children.len: - if node.children[i].k[0] == k[0]: - if k.len != node.children[i].k.len: - return default - var j = 1 - while j < k.len: - if node.children[i].k[j] != k[j]: - return default - inc j - return i - inc i - return default - -iterator keys(pairseq: StaticRadixPairSeq): string = - var i = 0 - while i < pairseq.len: - yield pairseq[i].k - inc i - -iterator keys*[T](node: RadixNode[T]): string = - var i = 0 - while i < node.children.len: - yield node.children[i].k - inc i - -# AKA `in`. -func contains(pairseq: StaticRadixPairSeq, k: string): bool = - var i = 0 - while i < pairseq.len: - if pairseq[i].k[0] == k[0]: - if k.len != pairseq[i].k.len: - return false - var j = 1 - while j < k.len: - if pairseq[i].k[j] != k[j]: - return false - inc j - return true - inc i - return false - -func contains[T](node: RadixNode[T], k: string): bool = - var i = 0 - while i < node.children.len: - if node.children[i].k[0] == k[0]: - if k.len != node.children[i].k.len: - return false - var j = 1 - while j < k.len: - if node.children[i].k[j] != k[j]: - return false - inc j - return true - inc i - return false - -# Delete proc: again we should be able to check for first char only... TODO? -proc del(pairseq: var StaticRadixPairSeq, k: string) = - var i = 0 - while i < pairseq.len: - if pairseq[i].k == k: - pairseq.del(i) - return - inc i - -proc add[T](node: RadixNode[T], k: string, v: T) = - node.children.add((k, RadixNode[T](leaf: true, value: v))) - -proc add[T](node: RadixNode[T], k: string) = - node.children.add((k, RadixNode[T](leaf: false))) - -# Insert: this is ugly and I'm not quite sure about what it does at all. Oh -# well. -proc `[]=`*[T](tree: var StaticRadixTree[T], key: string, value: T) = - var n = 0 - var p = 0 - var i = 0 - var j = 0 - var s = "" - var t = "" - var nodeKey = "" - # find last matching node - while i < key.len: - s &= key[i] - inc i - if s in tree.nodes[n].children: - p = n - n = tree.nodes[n].children[s] - t &= s - j = i - nodeKey = s - s = "" - - for k in tree.nodes[n].children.keys: - if s.len > 0 and k[0] == s[0]: - p = n - n = tree.nodes[n].children[k] - t &= k - nodeKey = k - break - - # if first node, just add normally - if n == 0: - tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) - tree.nodes[n].children[key] = int(tree.nodes.len - 1) - else: - i = 0 - var conflict = false - # compare new key with the one we found so far - while i < t.len and i < key.len: - if key[i] == t[i]: - inc i - else: - conflict = true - break - - if conflict: - # conflict somewhere, so: - # * add new non-leaf to parent - # * add old to non-leaf - # * add new to non-leaf - # * remove old from parent - assert(i != 0) - - tree.nodes[p].children[key.substr(j, i - 1)] = int(tree.nodes.len) - tree.nodes.add(StaticRadixNode[T](leaf: false)) - tree.nodes[^1].children[t.substr(i)] = n - tree.nodes[^1].children[key.substr(i)] = int(tree.nodes.len) - tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) - tree.nodes[p].children.del(nodeKey) - else: # new is either substr of old or old is substr of new - # new matches a node, so replace - if key.len == t.len: - let children = tree.nodes[n].children - tree.nodes[n] = StaticRadixNode[T](leaf: true, value: value) - tree.nodes[n].children = children - elif i == j: - # new is longer than the old, so add child to old - tree.nodes[n].children[key.substr(i)] = int(tree.nodes.len) - tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) - elif i > 0: - # new is shorter than old, so: - # * add new to parent - # * add old to new - # * remove old from parent - tree.nodes[p].children[key.substr(j, i - 1)] = int(tree.nodes.len) - tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) - tree.nodes[^1].children[t.substr(i)] = n - tree.nodes[p].children.del(nodeKey) - -# Non-static insert, for extra fun - and code duplication :( -proc `[]=`*[T](tree: RadixNode[T], key: string, value: T) = - var n = tree - var p: RadixNode[T] = nil - var i = 0 - var j = 0 - var k = 0 - var s = "" - var t = "" - var l = 0 - # find last matching node - while i < key.len: - s &= key[i] - inc i - let pk = n.getOrDefault(s, -1) - if pk != -1: - k = pk - p = n - n = n.children[k].v - t &= s - j = i - s = "" - - l = 0 - for ki in n.keys: - if s.len > 0 and ki[0] == s[0]: - p = n - n = n[ki] - t &= ki - k = l - break - inc l - - # TODO: this below could be a better algorithm for what we do above - # but I'm kinda scared of touching it - #n = tree - #i = 0 - #j = 0 - #k = 0 - #t = "" - #p = nil - - #var conflict = false - #while i < key.len: - # k = 0 - # for pk in n.keys: - # if pk[0] == key[i]: - # var l = 0 - # while l < pk.len and i + l < key.len: - # if pk[l] != key[i + l]: - # conflict = true - # break - # inc l - # if not conflict: - # p = n - # n = n.children[k].v - # t &= pk - # i += l - # j = i - # break - # inc k - # inc i - - - # if first node, just add normally - if n == tree: - tree.add(key, value) - else: - i = 0 - var conflict = false - # compare new key with the one we found so far - while i < t.len and i < key.len: - if key[i] == t[i]: - inc i - else: - conflict = true - break - - if conflict: - # conflict somewhere, so: - # * add new non-leaf to parent - # * add old to non-leaf - # * add new to non-leaf - # * remove old from parent - debugecho "conflict: ", i, " ", j, " ", t, " ", key, ": ", key.substr(j, i - 1) - p[key.substr(j, i - 1)] = RadixNode[T](leaf: false) - p.children[^1].v[t.substr(i)] = n - p.children[^1].v[key.substr(i)] = RadixNode[T](leaf: true, value: value) - p.children.del(k) - else: # new is either substr of old or old is substr of new - # new matches a node, so replace - if key.len == t.len: - p.children[k].v = RadixNode[T](leaf: true, value: value, children: n.children) - elif key.len > t.len: - # new is longer than the old, so add child to old - debugecho "longer: ", i, " ", j, " ", t, " ", key, ": ", key.substr(i) - n[key.substr(i)] = RadixNode[T](leaf: true, value: value) - else: - assert(i > 0) - # new is shorter than old, so: - # * add new to parent - # * add old to new - # * remove old from parent - debugecho "shorter: ", i, " ", j, " ", t, " ", key, ": ", key.substr(i) - p[key.substr(j, i - 1)] = RadixNode[T](leaf: true, value: value) - p.children[^1].v[t.substr(i)] = n - p.children.del(k) - -func `{}`*[T](tree: StaticRadixTree[T], key: string, at: int = 0): int = - return tree.nodes[at].children.getOrDefault(key, at) - -func `{}`*[T](tree: RadixNode[T], key: string, at: RadixNode[T] = tree): RadixNode[T] = - return tree.getOrDefault(key, at) - -func hasPrefix*[T](tree: StaticRadixTree[T], prefix: string, at: int = 0): bool = - var n = at - var i = 0 - var j = 0 - var s = "" - while i < prefix.len: - s &= prefix[i] - inc i - if s in tree.nodes[n].children: - n = tree.nodes[n].children[s] - j = i - - if j == prefix.len: - return true - - for k in tree.nodes[n].children.keys: - if prefix.len - j < k.len and k[0] == prefix[j]: - i = 1 - inc j - while j < prefix.len: - inc i - inc j - if k[i] != k[j]: - return false - return true - - return false - -func hasPrefix*[T](tree: RadixNode[T], prefix: string, at: RadixNode[T] = tree): bool = - var n = at - var i = 0 - var j = 0 - var s = "" - while i < prefix.len: - s &= prefix[i] - inc i - if s in n: - n = n[s] - j = i - - if j == prefix.len: - return true - - for k in n.keys: - if prefix.len - j < k.len and k[0] == prefix[j]: - i = 1 - inc j - while j < prefix.len: - inc i - inc j - if k[i] != k[j]: - return false - return true - - return false diff --git a/src/style.nim b/src/style.nim deleted file mode 100644 index e5bee647..00000000 --- a/src/style.nim +++ /dev/null @@ -1,74 +0,0 @@ -import streams -import unicode - -import enums -import cssparser -import twtio - -type - CSS2Properties* = ref object - rawtext*: string - fmttext*: seq[string] - x*: int - y*: int - ex*: int - ey*: int - width*: int - height*: int - hidden*: bool - before*: CSS2Properties - after*: CSS2Properties - margintop*: int - marginbottom*: int - marginleft*: int - marginright*: int - margin*: int - centered*: bool - display*: DisplayType - bold*: bool - italic*: bool - underscore*: bool - islink*: bool - selected*: bool - indent*: int - - CSSRect* = object - x1*: int - y1*: int - x2*: int - y2*: int - - CSSBox* = ref object - display*: DisplayType - x*: int - y*: int - innerEdge*: CSSRect - paddingEdge*: CSSRect - borderEdge*: CSSRect - marginEdge*: CSSRect - parent*: CSSBox - color*: CSSColor - margintop*: int - marginbottom*: int - marginleft*: int - marginright*: int - margin*: int - -proc applyProperties*(box: var CSSBox, props: string) = - var decls = parseCSSListOfDeclarations(newStringStream(props)) - - for item in decls: - if item of CSSDeclaration: - let d = CSSDeclaration(item) - case $d.name - of "color": - if d.value.len > 0 and d.value[0] of CSSToken and - CSSToken(d.value[0]).tokenType == CSS_HASH_TOKEN: - box.color = toColor(CSSToken(d.value[0]).value) - of "margin-top": - if d.value.len > 0 and d.value[0] of CSSToken: - if CSSToken(d.value[0]).tokenType == CSS_PERCENTAGE_TOKEN: - discard - #box.margintop = CSSToken(d.value[0]).nvalue #TODO represent percentages - else: - printc(d) diff --git a/src/twtio.nim b/src/twtio.nim deleted file mode 100644 index 20c8c527..00000000 --- a/src/twtio.nim +++ /dev/null @@ -1,263 +0,0 @@ -import terminal -import tables -import unicode -import strutils - -import twtstr -import config -import radixtree - -template print*(s: varargs[string, `$`]) = - for x in s: - stdout.write(x) - -template printesc*(s: string) = - for r in s.runes: - if r.isControlChar(): - stdout.write(('^' & $($r)[0].getControlLetter()) - .ansiFgColor(fgBlue).ansiStyle(styleBright).ansiReset()) - else: - stdout.write($r) - -template eprint*(s: varargs[string, `$`]) = {.cast(noSideEffect).}: - var a = false - for x in s: - if not a: - a = true - else: - stderr.write(' ') - stderr.write(x) - stderr.write('\n') - -proc termGoto*(x: int, y: int) = - setCursorPos(stdout, x, y) - -proc getNormalAction*(s: string): TwtAction = - if normalActionRemap.hasKey(s): - return normalActionRemap[s] - return NO_ACTION - -proc getLinedAction*(s: string): TwtAction = - if linedActionRemap.hasKey(s): - return linedActionRemap[s] - return NO_ACTION - -proc readLine*(prompt: string, current: var string, termwidth: int): bool = - let maxlen = termwidth - prompt.len - let promptwidth = prompt.width() - var news = current.toRunes() - var s = "" - var feedNext = false - var escNext = false - var comp = false - var compi = composeRemap - var compa = 0 - var comps = "" - var cursor = news.len - var shift = 0 - var redraw = true - printesc(prompt) - while true: - if redraw: - var displen = maxlen - 1 - if cursor >= shift: - while news.substr(shift, cursor).width() > maxlen - 1: - shift += 1 - while news.substr(shift, shift + displen).width() > maxlen - 1: - displen -= 1 - - shift = max(0, min(cursor - 1, shift)) - - print('\r') - cursorForward(promptwidth) - let os = $news.substr(shift, shift + displen) - printesc(os) - print(' '.repeat(max(displen - os.width(), 0))) - - print('\r') - cursorForward(promptwidth + news.substr(shift, cursor).width()) - else: - redraw = true - - if not feedNext: - s = "" - else: - feedNext = false - - let c = getch() - s &= c - - var action = getLinedAction(s) - if escNext: - action = NO_ACTION - case action - of ACTION_LINED_CANCEL: - return false - of ACTION_LINED_SUBMIT: - current = $news - return true - of ACTION_LINED_BACKSPACE: - if cursor > 0: - news = news.substr(0, cursor - 1) & news.substr(cursor) - dec cursor - else: - redraw = false - of ACTION_LINED_DELETE: - if cursor > 0 and cursor < news.len: - news = news.substr(0, cursor) & news.substr(cursor + 1) - else: - redraw = false - of ACTION_LINED_ESC: - escNext = true - of ACTION_LINED_CLEAR: - news = news.substr(cursor) - cursor = 0 - of ACTION_LINED_KILL: - if cursor > 0: - news = news.substr(0, cursor) - else: - redraw = false - of ACTION_LINED_BACK: - if cursor > 0: - dec cursor - if cursor > shift: - redraw = false - cursorBackward(news[cursor].width()) - else: - redraw = false - of ACTION_LINED_FORWARD: - if cursor < news.len: - inc cursor - if news.substr(shift, cursor).width() < maxlen: - redraw = false - var n = 1 - if news.len > cursor: - n = news[cursor].width() - cursorForward(n) - else: - redraw = false - of ACTION_LINED_PREV_WORD: - let oc = cursor - while cursor > 0: - dec cursor - if news[cursor].breaksWord(): - break - if cursor == oc: - redraw = false - elif cursor > shift: - cursorBackward(news.substr(cursor, oc).width()) - redraw = false - of ACTION_LINED_NEXT_WORD: - let oc = cursor - while cursor < news.len: - inc cursor - if cursor < news.len: - if news[cursor].breaksWord(): - break - if cursor == oc: - redraw = false - else: - let dw = news.substr(oc, cursor).width() - if oc + dw - shift < maxlen: - cursorForward(dw) - redraw = false - of ACTION_LINED_KILL_WORD: - var chars = 0 - - while cursor > chars: - inc chars - if news[cursor - chars].breaksWord(): - break - if chars > 0: - let w = news.substr(cursor - chars, cursor).width() - news = news.substr(0, cursor - chars) & news.substr(cursor) - cursor -= chars - if cursor > shift: - redraw = false - cursorBackward(w) - print(' '.repeat(w)) - cursorBackward(w) - else: - redraw = false - of ACTION_LINED_BEGIN: - if cursor > 0: - if shift == 0: - redraw = false - cursorBackward(news.substr(0, cursor).width()) - cursor = 0 - else: - redraw = false - of ACTION_LINED_END: - if cursor < news.len: - if news.substr(shift, news.len).width() < maxlen: - redraw = false - cursorForward(news.substr(shift, news.len).width()) - cursor = news.len - else: - redraw = false - of ACTION_LINED_COMPOSE_TOGGLE: - comp = not comp - compi = composeRemap - compa = 0 - comps = "" - redraw = false - of ACTION_FEED_NEXT: - feedNext = true - redraw = false - elif comp: - comps &= c - let n = composeRemap{comps, compi} - if n != compi: - compi = n - compa += comps.len - comps = "" - if composeRemap.hasPrefix(comps, compi) and n.children.len > 0: - feedNext = true - else: - var cs = "" - if compi.leaf: - cs = compi.value - else: - cs = s.substr(0, compa - 1) - comps = s.substr(compa) - if comps.len > 0 and composeRemap.hasPrefix(comps): - compa = comps.len - compi = composeRemap{comps} - s = comps - comps = "" - feedNext = true - else: - cs &= comps - compa = 0 - compi = composeRemap - comps = "" - - news = news.substr(0, cursor) & cs.toRunes() & news.substr(cursor) - cursor += cs.runeLen() - elif validateUtf8(s) == -1: - var cs = "" - for c in s: - if not c.isControlChar(): - cs &= c - elif escNext: - cs &= c - escNext = false - escNext = false - if cs.len == 0: - redraw = false - continue - - let csr = cs.toRunes() - - if cursor >= news.len and - news.substr(shift, cursor).width() + csr.width() < maxlen - 1: - cursor += csr.len - news &= csr - print(csr) - redraw = false - else: - news = news.substr(0, cursor) & csr & news.substr(cursor) - cursor += csr.len - else: - feedNext = true - redraw = false diff --git a/src/enums.nim b/src/types/enums.nim index 62e96e4c..21b27ab6 100644 --- a/src/enums.nim +++ b/src/types/enums.nim @@ -1,6 +1,7 @@ +import tables + type - NodeType* = - enum + NodeType* = enum UNKNOWN_NODE = 0, ELEMENT_NODE = 1, ATTRIBUTE_NODE = 2, @@ -15,27 +16,23 @@ type DOCUMENT_FRAGMENT_NODE = 11, NOTATION_NODE = 12 - DisplayType* = - enum + DisplayType* = enum DISPLAY_INLINE, DISPLAY_BLOCK, DISPLAY_LIST_ITEM, DISPLAY_TABLE_COLUMN, DISPLAY_INLINE_BLOCK, DISPLAY_NONE - InputType* = - enum + InputType* = enum INPUT_UNKNOWN, INPUT_BUTTON, INPUT_CHECKBOX, INPUT_COLOR, INPUT_DATE, INPUT_DATETIME_LOCAL, INPUT_EMAIL, INPUT_FILE, INPUT_HIDDEN, INPUT_IMAGE, INPUT_MONTH, INPUT_NUMBER, INPUT_PASSWORD, INPUT_RADIO, INPUT_RANGE, INPUT_RESET, INPUT_SEARCH, INPUT_SUBMIT, INPUT_TEL, INPUT_TEXT, INPUT_TIME, INPUT_URL, INPUT_WEEK - WhitespaceType* = - enum + WhitespaceType* = enum WHITESPACE_UNKNOWN, WHITESPACE_NORMAL, WHITESPACE_NOWRAP, WHITESPACE_PRE, WHITESPACE_PRE_LINE, WHITESPACE_PRE_WRAP, WHITESPACE_INITIAL, WHITESPACE_INHERIT - TagType* = - enum + TagType* = enum TAG_UNKNOWN, TAG_HTML, TAG_BASE, TAG_HEAD, TAG_LINK, TAG_META, TAG_STYLE, TAG_TITLE, TAG_BODY, TAG_ADDRESS, TAG_ARTICLE, TAG_ASIDE, TAG_FOOTER, TAG_HEADER, TAG_H1, TAG_H2, TAG_H3, TAG_H4, TAG_H5, TAG_H6, TAG_HGROUP, @@ -55,8 +52,7 @@ type TAG_DIALOG, TAG_MENU, TAG_SUMMARY, TAG_BLINK, TAG_CENTER, TAG_CONTENT, TAG_DIR, TAG_FONT, TAG_FRAME, TAG_NOFRAMES, TAG_FRAMESET, TAG_STRIKE, TAG_TT - CSSTokenType* = - enum + CSSTokenType* = enum CSS_NO_TOKEN, CSS_IDENT_TOKEN, CSS_FUNCTION_TOKEN, CSS_AT_KEYWORD_TOKEN, CSS_HASH_TOKEN, CSS_STRING_TOKEN, CSS_BAD_STRING_TOKEN, CSS_URL_TOKEN, CSS_BAD_URL_TOKEN, CSS_DELIM_TOKEN, CSS_NUMBER_TOKEN, CSS_PERCENTAGE_TOKEN, @@ -65,6 +61,15 @@ type CSS_LBRACKET_TOKEN, CSS_LPAREN_TOKEN, CSS_RPAREN_TOKEN, CSS_LBRACE_TOKEN, CSS_RBRACE_TOKEN + CSSUnit* = enum + CM_UNIT, MM_UNIT, IN_UNIT, PX_UNIT, PT_UNIT, PC_UNIT, + EM_UNIT, EX_UNIT, CH_UNIT, REM_UNIT, VW_UNIT, VH_UNIT, VMIN_UNIT, VMAX_UNIT, + PERC_UNIT + + CSSPosition* = enum + STATIC_POSITION, RELATIVE_POSITION, ABSOLUTE_POSITION, FIXED_POSITION, + INHERIT_POSITION + const DisplayInlineTags* = { TAG_A, TAG_ABBR, TAG_B, TAG_BDO, TAG_BR, TAG_BUTTON, TAG_CITE, TAG_CODE, TAG_DEL, TAG_DFN, TAG_EM, TAG_FONT, TAG_I, TAG_IMG, TAG_INS, TAG_INPUT, diff --git a/src/types/tagtypes.nim b/src/types/tagtypes.nim new file mode 100644 index 00000000..34111570 --- /dev/null +++ b/src/types/tagtypes.nim @@ -0,0 +1,30 @@ +import tables +import enums +import strutils + +func getTagTypeMap(): Table[string, TagType] = + for i in low(TagType) .. high(TagType): + let enumname = $TagType(i) + let tagname = enumname.split('_')[1..^1].join("_").tolower() + result[tagname] = TagType(i) + +func getInputTypeMap(): Table[string, InputType] = + for i in low(InputType) .. high(InputType): + let enumname = $InputType(i) + let tagname = enumname.split('_')[1..^1].join("_").tolower() + result[tagname] = InputType(i) + +const tagTypeMap = getTagTypeMap() +const inputTypeMap = getInputTypeMap() + +func tagType*(s: string): TagType = + if tagTypeMap.hasKey(s): + return tagTypeMap[s] + else: + return TAG_UNKNOWN + +func inputType*(s: string): InputType = + if inputTypeMap.hasKey(s): + return inputTypeMap[s] + else: + return INPUT_UNKNOWN diff --git a/src/utils/radixtree.nim b/src/utils/radixtree.nim new file mode 100644 index 00000000..0601eeba --- /dev/null +++ b/src/utils/radixtree.nim @@ -0,0 +1,309 @@ +# Radix tree implementation. It isn't that much faster than a hash table, +# however it *is* faster. Use StaticRadixTree for saving trees in the +# executable and RadixNode otherwise (which needs less bounds checking). + +import json +import tables + +type + RadixPair[T] = tuple[k: string, v: RadixNode[T]] + + RadixNode*[T] = ref object + children*: seq[RadixPair[T]] + case leaf*: bool + of true: value*: T + of false: discard + + StaticRadixPair = tuple[k: string, v: int] + + StaticRadixNode[T] = object + children*: seq[StaticRadixPair] + case leaf*: bool + of true: value*: T + of false: discard + + StaticRadixTree*[T] = object + nodes*: seq[StaticRadixNode[T]] + +func newStaticRadixTree*[T](): StaticRadixTree[T] = + result.nodes.add(StaticRadixNode[T](leaf: false)) + +func newRadixTree*[T](): RadixNode[T] = + new(result) + +func toRadixTree*[T](table: Table[string, T]): RadixNode[T] = + result = newRadixTree[T]() + for k, v in table: + result[k] = v + +# getOrDefault: we have to compare the entire string but if it doesn't match +# exactly we can just return default. +func getOrDefault(pairseq: seq[StaticRadixPair], k: string, default: int): int = + var i = 0 + while i < pairseq.len: + if pairseq[i].k[0] == k[0]: + if k.len != pairseq[i].k.len: + return default + var j = 1 + while j < k.len: + if pairseq[i].k[j] != k[j]: + return default + inc j + return pairseq[i].v + inc i + return default + +func getOrDefault[T](node: RadixNode[T], k: string, default: RadixNode[T]): RadixNode[T] = + var i = 0 + while i < node.children.len: + if node.children[i].k[0] == k[0]: + if k.len != node.children[i].k.len: + return default + var j = 1 + while j < k.len: + if node.children[i].k[j] != k[j]: + return default + inc j + return node.children[i].v + inc i + return default + +iterator keys(pairseq: seq[StaticRadixPair]): string = + var i = 0 + while i < pairseq.len: + yield pairseq[i].k + inc i + +iterator keys*[T](node: RadixNode[T]): string = + var i = 0 + while i < node.children.len: + yield node.children[i].k + inc i + +func contains(pairseq: seq[StaticRadixPair], k: string): bool = + var i = 0 + while i < pairseq.len: + if pairseq[i].k[0] == k[0]: + if k.len != pairseq[i].k.len: + return false + var j = 1 + while j < k.len: + if pairseq[i].k[j] != k[j]: + return false + inc j + return true + inc i + return false + +func contains[T](node: RadixNode[T], k: string): bool = + var i = 0 + while i < node.children.len: + if node.children[i].k[0] == k[0]: + if k.len != node.children[i].k.len: + return false + var j = 1 + while j < k.len: + if node.children[i].k[j] != k[j]: + return false + inc j + return true + inc i + return false + +# Static insert +proc `[]=`*[T](tree: var StaticRadixTree[T], key: string, value: T) = + var n = 0 + var p = 0 + var i = 0 + var j = 0 + var k = 0 + var t = "" + # find last matching node + var conflict = false + while i < key.len: + let m = i + var o = 0 + for pk in tree.nodes[n].children.keys: + if pk[0] == key[i]: + var l = 0 + while l < pk.len and i + l < key.len: + if pk[l] != key[i + l]: + conflict = true + break + inc l + p = n + k = o + n = tree.nodes[n].children[k].v + t &= pk + i += l + if not conflict and pk.len == l: + j = i + break + inc o + if i == m: + break + if conflict: + break + + # if first node, just add normally + if n == 0: + tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) + tree.nodes[n].children.add((k: key, v: int(tree.nodes.len - 1))) + elif conflict: + # conflict somewhere, so: + # * add new non-leaf to parent + # * add old to non-leaf + # * add new to non-leaf + # * remove old from parent + tree.nodes[p].children.add((k: key.substr(j, i - 1), v: int(tree.nodes.len))) + tree.nodes.add(StaticRadixNode[T](leaf: false)) + tree.nodes[^1].children.add((k: t.substr(i), v: n)) + tree.nodes[^1].children.add((k: key.substr(i), v: int(tree.nodes.len))) + tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) + tree.nodes[p].children.del(k) + elif key.len == t.len: + # new matches a node, so replace + tree.nodes[n] = StaticRadixNode[T](leaf: true, value: value, children: tree.nodes[n].children) + elif i == j: + # new is longer than the old, so add child to old + tree.nodes[n].children.add((k: key.substr(i), v: int(tree.nodes.len))) + tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) + else: + # new is shorter than old, so: + # * add new to parent + # * add old to new + # * remove old from parent + tree.nodes[p].children.add((k: key.substr(j, i - 1), v: int(tree.nodes.len))) + tree.nodes.add(StaticRadixNode[T](leaf: true, value: value)) + tree.nodes[^1].children.add((k: key.substr(i), v: n)) + tree.nodes[p].children.del(k) + +# O(1) add procedures for insert +proc add[T](node: RadixNode[T], k: string, v: T) = + node.children.add((k, RadixNode[T](leaf: true, value: v))) + +proc add[T](node: RadixNode[T], k: string) = + node.children.add((k, RadixNode[T](leaf: false))) + +proc add[T](node: RadixNode[T], k: string, v: RadixNode[T]) = + node.children.add((k, v)) + +# Non-static insert +proc `[]=`*[T](tree: RadixNode[T], key: string, value: T) = + var n = tree + var p: RadixNode[T] = nil + var i = 0 + var j = 0 + var k = 0 + var t = "" + + # find last matching node + var conflict = false + while i < key.len: + let m = i + var o = 0 + for pk in n.keys: + if pk[0] == key[i]: + var l = 0 + while l < pk.len and i + l < key.len: + if pk[l] != key[i + l]: + conflict = true + #t = key.substr(0, i + l - 1) & pk.substr(l) + break + inc l + p = n + k = o + n = n.children[k].v + t &= pk + i += l + if not conflict and pk.len == l: + j = i + # t = key.substr(0, i - 1) + #elif not conflict and pk.len > l: + # t = key & pk.substr(l) + break + inc o + if i == m: + break + if conflict: + break + + if n == tree: + # first node, just add normally + tree.add(key, value) + elif conflict: + # conflict somewhere, so: + # * add new non-leaf to parent + # * add old to non-leaf + # * add new to non-leaf + # * remove old from parent + p.add(key.substr(j, i - 1)) + p.children[^1].v.add(t.substr(i), n) + p.children[^1].v.add(key.substr(i), value) + p.children.del(k) + elif key.len == t.len: + # new matches a node, so replace + p.children[k].v = RadixNode[T](leaf: true, value: value, children: n.children) + elif key.len > t.len: + # new is longer than the old, so add child to old + n.add(key.substr(i), value) + else: + # new is shorter than old, so: + # * add new to parent + # * add old to new + # * remove old from parent + p.add(key.substr(j, i - 1), value) + p.children[^1].v.add(t.substr(i), n) + p.children.del(k) + +func `{}`*[T](tree: StaticRadixTree[T], key: string, at: int = 0): int = + return tree.nodes[at].children.getOrDefault(key, at) + +func `{}`*[T](node: RadixNode[T], key: string): RadixNode[T] = + return node.getOrDefault(key, node) + +func hasPrefix*[T](tree: StaticRadixTree[T], prefix: string, at: int = 0): bool = + var n = at + var i = 0 + + while i < prefix.len: + let m = i + var j = 0 + for pk in tree.nodes[n].children.keys: + if pk[0] == prefix[i]: + var l = 0 + while l < pk.len and i + l < prefix.len: + if pk[l] != prefix[i + l]: + return false + inc l + n = tree.nodes[n].children[j].v + i += l + break + inc j + if i == m: + return false + + return true + +func hasPrefix*[T](tree: RadixNode[T], prefix: string, at: RadixNode[T] = tree): bool = + var n = at + var i = 0 + + while i < prefix.len: + let m = i + var j = 0 + for pk in n.keys: + if pk[0] == prefix[i]: + var l = 0 + while l < pk.len and i + l < prefix.len: + if pk[l] != prefix[i + l]: + return false + inc l + n = n.children[j].v + i += l + break + inc j + if i == m: + return false + + return true diff --git a/src/termattrs.nim b/src/utils/termattrs.nim index d49800ae..d49800ae 100644 --- a/src/termattrs.nim +++ b/src/utils/termattrs.nim diff --git a/src/twtstr.nim b/src/utils/twtstr.nim index aa2cf2c7..d5de3eef 100644 --- a/src/twtstr.nim +++ b/src/utils/twtstr.nim @@ -183,29 +183,27 @@ func substr*(s: seq[Rune], i: int): seq[Rune] = return @[] return s[min(high(s), i)..high(s)] -#Measure length of rune. From https://www.cl.cam.ac.uk/~mgk25/ucs/wcwidth.c - -#auxiliary function for binary search in interval table -func bisearch(ucs: Rune, table: openarray[(int, int)]): bool = - var max = table.high - var min = 0 - var mid: int +func skipBlanks*(buf: string, at: int): int = + result = at + while result < buf.len and buf[result].isWhitespace(): + inc result - if int(ucs) < table[0][0] or int(ucs) > table[max][1]: - return false +iterator split*(s: seq[Rune], sep: Rune): seq[Rune] = + var i = 0 + var prev = 0 + while i < s.len: + if s[i] == sep: + yield s.substr(prev, i) + prev = i + inc i - while max >= min: - mid = (min + max) div 2 - if int(ucs) > table[mid][1]: - min = mid + 1 - elif int(ucs) < table[mid][0]: - max = mid - 1 - else: - return true - return false + if prev < i: + yield s.substr(prev, i) -#The following two functions define the column width of an ISO 10646 -#character as follows: +# Measure length of runes. From https://www.cl.cam.ac.uk/~mgk25/ucs/wcwidth.c +# +# The following two functions define the column width of an ISO 10646 +# character as follows: # # - The null character (U+0000) has a column width of 0. # @@ -230,12 +228,9 @@ func bisearch(ucs: Rune, table: openarray[(int, int)]): bool = # - All remaining characters (including all printable ISO 8859-1 and WGL4 # characters, Unicode control characters, etc.) have a column width of 1. # -#This implementation assumes that wchar_t characters are encoded -#in ISO 10646. -# -# sorted list of non-overlapping intervals of non-spacing characters -# generated by "uniset +cat=Me +cat=Mn +cat=Cf -00AD +1160-11FF +200B c" +# sorted list of non-overlapping intervals of non-spacing characters generated +# by "uniset +cat=Me +cat=Mn +cat=Cf -00AD +1160-11FF +200B c" const combining = [ ( 0x0300, 0x036F ), ( 0x0483, 0x0486 ), ( 0x0488, 0x0489 ), ( 0x0591, 0x05BD ), ( 0x05BF, 0x05BF ), ( 0x05C1, 0x05C2 ), @@ -326,39 +321,16 @@ func makewidthtable(): array[0..0x10FFFF, byte] = else: result[ucs] = 1 - for range in combining: - for r in range[0]..range[1]: - result[r] = 0 - - -# lowmem: use slow binary search etc method -when defined(lowmem): - func width*(r: Rune): int = - # binary search in table of non-spacing characters - if bisearch(r, combining): - return 0 - - if r.isControlChar(): - return 2 - - # if we arrive here, ucs is not a combining or C0/C1 control character - - if r.is_dwidth(): - return 2 - return 1 - - func width*(r: Rune): int = - return int(width_table[int(r)]) -# small: store lookup table in memory on startup -elif defined(small): +when defined(small): + # compute lookup table on startup let width_table = makewidthtable() - func width*(r: Rune): int = - {.cast(noSideEffect).}: - return int(width_table[int(r)]) -# release: store lookup table in executable else: + # store lookup table in executable const width_table = makewidthtable() - func width*(r: Rune): int = + +{.push boundChecks:off.} +func width*(r: Rune): int = + {.cast(noSideEffect).}: return int(width_table[int(r)]) func width*(s: string): int = @@ -369,8 +341,21 @@ func width*(s: seq[Rune]): int = for r in s: result += width(r) -# sorted list of non-overlapping intervals of East Asian Ambiguous -# characters, generated by "uniset +WIDTH-A -cat=Me -cat=Mn -cat=Cf c" +func width*(s: seq[Rune], min: int, max: int): int = + var i = min + var mi = min(max, s.len) + while i < mi: + result += width(s[i]) + inc i + +func width*(s: seq[Rune], min: int): int = + var i = min + while i < s.len: + result += width(s[i]) + inc i + +# sorted list of non-overlapping intervals of East Asian Ambiguous characters, +# generated by "uniset +WIDTH-A -cat=Me -cat=Mn -cat=Cf c" const ambiguous = [ ( 0x00A1, 0x00A1 ), ( 0x00A4, 0x00A4 ), ( 0x00A7, 0x00A8 ), @@ -428,16 +413,34 @@ const ambiguous = [ ] # -# The following functions are the same as mk_wcwidth() and -# mk_wcswidth(), except that spacing characters in the East Asian -# Ambiguous (A) category as defined in Unicode Technical Report #11 -# have a column width of 2. This variant might be useful for users of -# CJK legacy encodings who want to migrate to UCS without changing -# the traditional terminal character-width behaviour. It is not -# otherwise recommended for general use. -# -# note: seconded, this should only be used if some option was changed (TODO: -# make such an option available) +# The following functions are the same as mk_wcwidth() and mk_wcswidth(), +# except that spacing characters in the East Asian Ambiguous (A) category as +# defined in Unicode Technical Report #11 have a column width of 2. This +# variant might be useful for users of CJK legacy encodings who want to migrate +# to UCS without changing the traditional terminal character-width behaviour. +# It is not otherwise recommended for general use. +# +# TODO: currently these are unused, the user should be able to toggle them + +# auxiliary function for binary search in interval table +func bisearch(ucs: Rune, table: openarray[(int, int)]): bool = + var max = table.high + var min = 0 + var mid: int + + if int(ucs) < table[0][0] or int(ucs) > table[max][1]: + return false + + while max >= min: + mid = (min + max) div 2 + if int(ucs) > table[mid][1]: + min = mid + 1 + elif int(ucs) < table[mid][0]: + max = mid - 1 + else: + return true + return false + func mk_wcwidth_cjk(r: Rune): int = # binary search in table of non-spacing characters @@ -450,20 +453,3 @@ func mk_wcswidth_cjk(s: string): int = for r in s.runes: result += mk_wcwidth_cjk(r) return result - -func skipBlanks*(buf: string, at: int): int = - result = at - while result < buf.len and buf[result].isWhitespace(): - inc result - -iterator split*(s: seq[Rune], sep: Rune): seq[Rune] = - var i = 0 - var prev = 0 - while i < s.len: - if s[i] == sep: - yield s.substr(prev, i) - prev = i - inc i - - if prev < i: - yield s.substr(prev, i) |