all repos — grayfriday @ 31f2685bfecabaa4fe77d7cc6a97c2e6510f0194

blackfriday fork with a few changes

inline.go (view raw)

   1//
   2// Blackfriday Markdown Processor
   3// Available at http://github.com/russross/blackfriday
   4//
   5// Copyright © 2011 Russ Ross <russ@russross.com>.
   6// Distributed under the Simplified BSD License.
   7// See README.md for details.
   8//
   9
  10//
  11// Functions to parse inline elements.
  12//
  13
  14package blackfriday
  15
  16import (
  17	"bytes"
  18	"regexp"
  19	"strconv"
  20)
  21
  22var (
  23	urlRe    = `((https?|ftp):\/\/|\/)[-A-Za-z0-9+&@#\/%?=~_|!:,.;\(\)]+`
  24	anchorRe = regexp.MustCompile(`^(<a\shref="` + urlRe + `"(\stitle="[^"<>]+")?\s?>` + urlRe + `<\/a>)`)
  25
  26	// TODO: improve this regexp to catch all possible entities:
  27	htmlEntityRe = regexp.MustCompile(`&[a-z]{2,5};`)
  28)
  29
  30// Functions to parse text within a block
  31// Each function returns the number of chars taken care of
  32// data is the complete block being rendered
  33// offset is the number of valid chars before the current cursor
  34
  35func (p *parser) inline(currBlock *Node, data []byte) {
  36	// this is called recursively: enforce a maximum depth
  37	if p.nesting >= p.maxNesting {
  38		return
  39	}
  40	p.nesting++
  41
  42	i, end := 0, 0
  43	for i < len(data) {
  44		// Stop at EOL
  45		if data[i] == '\n' && i+1 == len(data) {
  46			break
  47		}
  48
  49		for ; end < len(data); end++ {
  50			if p.inlineCallback[data[end]] != nil {
  51				break
  52			}
  53		}
  54
  55		if end >= len(data) {
  56			if data[end-1] == '\n' {
  57				currBlock.AppendChild(text(data[i : end-1]))
  58			} else {
  59				currBlock.AppendChild(text(data[i:end]))
  60			}
  61			break
  62		}
  63
  64		// call the trigger
  65		handler := p.inlineCallback[data[end]]
  66		if consumed, node := handler(p, data, end); consumed == 0 {
  67			// No action from the callback.
  68			end++
  69		} else {
  70			// Copy inactive chars into the output.
  71			currBlock.AppendChild(text(data[i:end]))
  72			if node != nil {
  73				currBlock.AppendChild(node)
  74			}
  75			// Skip past whatever the callback used.
  76			i = end + consumed
  77			end = i
  78		}
  79	}
  80
  81	p.nesting--
  82}
  83
  84// single and double emphasis parsing
  85func emphasis(p *parser, data []byte, offset int) (int, *Node) {
  86	data = data[offset:]
  87	c := data[0]
  88
  89	if len(data) > 2 && data[1] != c {
  90		// whitespace cannot follow an opening emphasis;
  91		// strikethrough only takes two characters '~~'
  92		if c == '~' || isspace(data[1]) {
  93			return 0, nil
  94		}
  95		ret, node := helperEmphasis(p, data[1:], c)
  96		if ret == 0 {
  97			return 0, nil
  98		}
  99
 100		return ret + 1, node
 101	}
 102
 103	if len(data) > 3 && data[1] == c && data[2] != c {
 104		if isspace(data[2]) {
 105			return 0, nil
 106		}
 107		ret, node := helperDoubleEmphasis(p, data[2:], c)
 108		if ret == 0 {
 109			return 0, nil
 110		}
 111
 112		return ret + 2, node
 113	}
 114
 115	if len(data) > 4 && data[1] == c && data[2] == c && data[3] != c {
 116		if c == '~' || isspace(data[3]) {
 117			return 0, nil
 118		}
 119		ret, node := helperTripleEmphasis(p, data, 3, c)
 120		if ret == 0 {
 121			return 0, nil
 122		}
 123
 124		return ret + 3, node
 125	}
 126
 127	return 0, nil
 128}
 129
 130func codeSpan(p *parser, data []byte, offset int) (int, *Node) {
 131	data = data[offset:]
 132
 133	nb := 0
 134
 135	// count the number of backticks in the delimiter
 136	for nb < len(data) && data[nb] == '`' {
 137		nb++
 138	}
 139
 140	// find the next delimiter
 141	i, end := 0, 0
 142	for end = nb; end < len(data) && i < nb; end++ {
 143		if data[end] == '`' {
 144			i++
 145		} else {
 146			i = 0
 147		}
 148	}
 149
 150	// no matching delimiter?
 151	if i < nb && end >= len(data) {
 152		return 0, nil
 153	}
 154
 155	// trim outside whitespace
 156	fBegin := nb
 157	for fBegin < end && data[fBegin] == ' ' {
 158		fBegin++
 159	}
 160
 161	fEnd := end - nb
 162	for fEnd > fBegin && data[fEnd-1] == ' ' {
 163		fEnd--
 164	}
 165
 166	// render the code span
 167	if fBegin != fEnd {
 168		code := NewNode(Code)
 169		code.Literal = data[fBegin:fEnd]
 170		return end, code
 171	}
 172
 173	return end, nil
 174}
 175
 176// newline preceded by two spaces becomes <br>
 177func maybeLineBreak(p *parser, data []byte, offset int) (int, *Node) {
 178	origOffset := offset
 179	for offset < len(data) && data[offset] == ' ' {
 180		offset++
 181	}
 182
 183	if offset < len(data) && data[offset] == '\n' {
 184		if offset-origOffset >= 2 {
 185			return offset - origOffset + 1, NewNode(Hardbreak)
 186		}
 187		return offset - origOffset, nil
 188	}
 189	return 0, nil
 190}
 191
 192// newline without two spaces works when HardLineBreak is enabled
 193func lineBreak(p *parser, data []byte, offset int) (int, *Node) {
 194	if p.flags&HardLineBreak != 0 {
 195		return 1, NewNode(Hardbreak)
 196	}
 197	return 0, nil
 198}
 199
 200type linkType int
 201
 202const (
 203	linkNormal linkType = iota
 204	linkImg
 205	linkDeferredFootnote
 206	linkInlineFootnote
 207)
 208
 209func isReferenceStyleLink(data []byte, pos int, t linkType) bool {
 210	if t == linkDeferredFootnote {
 211		return false
 212	}
 213	return pos < len(data)-1 && data[pos] == '[' && data[pos+1] != '^'
 214}
 215
 216func maybeImage(p *parser, data []byte, offset int) (int, *Node) {
 217	if offset < len(data)-1 && data[offset+1] == '[' {
 218		return link(p, data, offset)
 219	}
 220	return 0, nil
 221}
 222
 223func maybeInlineFootnote(p *parser, data []byte, offset int) (int, *Node) {
 224	if offset < len(data)-1 && data[offset+1] == '[' {
 225		return link(p, data, offset)
 226	}
 227	return 0, nil
 228}
 229
 230// '[': parse a link or an image or a footnote
 231func link(p *parser, data []byte, offset int) (int, *Node) {
 232	// no links allowed inside regular links, footnote, and deferred footnotes
 233	if p.insideLink && (offset > 0 && data[offset-1] == '[' || len(data)-1 > offset && data[offset+1] == '^') {
 234		return 0, nil
 235	}
 236
 237	var t linkType
 238	switch {
 239	// special case: ![^text] == deferred footnote (that follows something with
 240	// an exclamation point)
 241	case p.flags&Footnotes != 0 && len(data)-1 > offset && data[offset+1] == '^':
 242		t = linkDeferredFootnote
 243	// ![alt] == image
 244	case offset >= 0 && data[offset] == '!':
 245		t = linkImg
 246		offset++
 247	// ^[text] == inline footnote
 248	// [^refId] == deferred footnote
 249	case p.flags&Footnotes != 0:
 250		if offset >= 0 && data[offset] == '^' {
 251			t = linkInlineFootnote
 252			offset++
 253		} else if len(data)-1 > offset && data[offset+1] == '^' {
 254			t = linkDeferredFootnote
 255		}
 256	// [text] == regular link
 257	default:
 258		t = linkNormal
 259	}
 260
 261	data = data[offset:]
 262
 263	var (
 264		i                       = 1
 265		noteID                  int
 266		title, link, altContent []byte
 267		textHasNl               = false
 268	)
 269
 270	if t == linkDeferredFootnote {
 271		i++
 272	}
 273
 274	// look for the matching closing bracket
 275	for level := 1; level > 0 && i < len(data); i++ {
 276		switch {
 277		case data[i] == '\n':
 278			textHasNl = true
 279
 280		case data[i-1] == '\\':
 281			continue
 282
 283		case data[i] == '[':
 284			level++
 285
 286		case data[i] == ']':
 287			level--
 288			if level <= 0 {
 289				i-- // compensate for extra i++ in for loop
 290			}
 291		}
 292	}
 293
 294	if i >= len(data) {
 295		return 0, nil
 296	}
 297
 298	txtE := i
 299	i++
 300
 301	// skip any amount of whitespace or newline
 302	// (this is much more lax than original markdown syntax)
 303	for i < len(data) && isspace(data[i]) {
 304		i++
 305	}
 306
 307	// inline style link
 308	switch {
 309	case i < len(data) && data[i] == '(':
 310		// skip initial whitespace
 311		i++
 312
 313		for i < len(data) && isspace(data[i]) {
 314			i++
 315		}
 316
 317		linkB := i
 318
 319		// look for link end: ' " )
 320	findlinkend:
 321		for i < len(data) {
 322			switch {
 323			case data[i] == '\\':
 324				i += 2
 325
 326			case data[i] == ')' || data[i] == '\'' || data[i] == '"':
 327				break findlinkend
 328
 329			default:
 330				i++
 331			}
 332		}
 333
 334		if i >= len(data) {
 335			return 0, nil
 336		}
 337		linkE := i
 338
 339		// look for title end if present
 340		titleB, titleE := 0, 0
 341		if data[i] == '\'' || data[i] == '"' {
 342			i++
 343			titleB = i
 344
 345		findtitleend:
 346			for i < len(data) {
 347				switch {
 348				case data[i] == '\\':
 349					i += 2
 350
 351				case data[i] == ')':
 352					break findtitleend
 353
 354				default:
 355					i++
 356				}
 357			}
 358
 359			if i >= len(data) {
 360				return 0, nil
 361			}
 362
 363			// skip whitespace after title
 364			titleE = i - 1
 365			for titleE > titleB && isspace(data[titleE]) {
 366				titleE--
 367			}
 368
 369			// check for closing quote presence
 370			if data[titleE] != '\'' && data[titleE] != '"' {
 371				titleB, titleE = 0, 0
 372				linkE = i
 373			}
 374		}
 375
 376		// remove whitespace at the end of the link
 377		for linkE > linkB && isspace(data[linkE-1]) {
 378			linkE--
 379		}
 380
 381		// remove optional angle brackets around the link
 382		if data[linkB] == '<' {
 383			linkB++
 384		}
 385		if data[linkE-1] == '>' {
 386			linkE--
 387		}
 388
 389		// build escaped link and title
 390		if linkE > linkB {
 391			link = data[linkB:linkE]
 392		}
 393
 394		if titleE > titleB {
 395			title = data[titleB:titleE]
 396		}
 397
 398		i++
 399
 400	// reference style link
 401	case isReferenceStyleLink(data, i, t):
 402		var id []byte
 403		altContentConsidered := false
 404
 405		// look for the id
 406		i++
 407		linkB := i
 408		for i < len(data) && data[i] != ']' {
 409			i++
 410		}
 411		if i >= len(data) {
 412			return 0, nil
 413		}
 414		linkE := i
 415
 416		// find the reference
 417		if linkB == linkE {
 418			if textHasNl {
 419				var b bytes.Buffer
 420
 421				for j := 1; j < txtE; j++ {
 422					switch {
 423					case data[j] != '\n':
 424						b.WriteByte(data[j])
 425					case data[j-1] != ' ':
 426						b.WriteByte(' ')
 427					}
 428				}
 429
 430				id = b.Bytes()
 431			} else {
 432				id = data[1:txtE]
 433				altContentConsidered = true
 434			}
 435		} else {
 436			id = data[linkB:linkE]
 437		}
 438
 439		// find the reference with matching id
 440		lr, ok := p.getRef(string(id))
 441		if !ok {
 442			return 0, nil
 443		}
 444
 445		// keep link and title from reference
 446		link = lr.link
 447		title = lr.title
 448		if altContentConsidered {
 449			altContent = lr.text
 450		}
 451		i++
 452
 453	// shortcut reference style link or reference or inline footnote
 454	default:
 455		var id []byte
 456
 457		// craft the id
 458		if textHasNl {
 459			var b bytes.Buffer
 460
 461			for j := 1; j < txtE; j++ {
 462				switch {
 463				case data[j] != '\n':
 464					b.WriteByte(data[j])
 465				case data[j-1] != ' ':
 466					b.WriteByte(' ')
 467				}
 468			}
 469
 470			id = b.Bytes()
 471		} else {
 472			if t == linkDeferredFootnote {
 473				id = data[2:txtE] // get rid of the ^
 474			} else {
 475				id = data[1:txtE]
 476			}
 477		}
 478
 479		if t == linkInlineFootnote {
 480			// create a new reference
 481			noteID = len(p.notes) + 1
 482
 483			var fragment []byte
 484			if len(id) > 0 {
 485				if len(id) < 16 {
 486					fragment = make([]byte, len(id))
 487				} else {
 488					fragment = make([]byte, 16)
 489				}
 490				copy(fragment, slugify(id))
 491			} else {
 492				fragment = append([]byte("footnote-"), []byte(strconv.Itoa(noteID))...)
 493			}
 494
 495			ref := &reference{
 496				noteID:   noteID,
 497				hasBlock: false,
 498				link:     fragment,
 499				title:    id,
 500			}
 501
 502			p.notes = append(p.notes, ref)
 503
 504			link = ref.link
 505			title = ref.title
 506		} else {
 507			// find the reference with matching id
 508			lr, ok := p.getRef(string(id))
 509			if !ok {
 510				return 0, nil
 511			}
 512
 513			if t == linkDeferredFootnote {
 514				lr.noteID = len(p.notes) + 1
 515				p.notes = append(p.notes, lr)
 516			}
 517
 518			// keep link and title from reference
 519			link = lr.link
 520			// if inline footnote, title == footnote contents
 521			title = lr.title
 522			noteID = lr.noteID
 523		}
 524
 525		// rewind the whitespace
 526		i = txtE + 1
 527	}
 528
 529	var uLink []byte
 530	if t == linkNormal || t == linkImg {
 531		if len(link) > 0 {
 532			var uLinkBuf bytes.Buffer
 533			unescapeText(&uLinkBuf, link)
 534			uLink = uLinkBuf.Bytes()
 535		}
 536
 537		// links need something to click on and somewhere to go
 538		if len(uLink) == 0 || (t == linkNormal && txtE <= 1) {
 539			return 0, nil
 540		}
 541	}
 542
 543	// call the relevant rendering function
 544	var linkNode *Node
 545	switch t {
 546	case linkNormal:
 547		linkNode = NewNode(Link)
 548		linkNode.Destination = normalizeURI(uLink)
 549		linkNode.Title = title
 550		if len(altContent) > 0 {
 551			linkNode.AppendChild(text(altContent))
 552		} else {
 553			// links cannot contain other links, so turn off link parsing
 554			// temporarily and recurse
 555			insideLink := p.insideLink
 556			p.insideLink = true
 557			p.inline(linkNode, data[1:txtE])
 558			p.insideLink = insideLink
 559		}
 560
 561	case linkImg:
 562		linkNode = NewNode(Image)
 563		linkNode.Destination = uLink
 564		linkNode.Title = title
 565		linkNode.AppendChild(text(data[1:txtE]))
 566		i++
 567
 568	case linkInlineFootnote, linkDeferredFootnote:
 569		linkNode = NewNode(Link)
 570		linkNode.Destination = link
 571		linkNode.Title = title
 572		linkNode.NoteID = noteID
 573		if t == linkInlineFootnote {
 574			i++
 575		}
 576
 577	default:
 578		return 0, nil
 579	}
 580
 581	return i, linkNode
 582}
 583
 584func (p *parser) inlineHTMLComment(data []byte) int {
 585	if len(data) < 5 {
 586		return 0
 587	}
 588	if data[0] != '<' || data[1] != '!' || data[2] != '-' || data[3] != '-' {
 589		return 0
 590	}
 591	i := 5
 592	// scan for an end-of-comment marker, across lines if necessary
 593	for i < len(data) && !(data[i-2] == '-' && data[i-1] == '-' && data[i] == '>') {
 594		i++
 595	}
 596	// no end-of-comment marker
 597	if i >= len(data) {
 598		return 0
 599	}
 600	return i + 1
 601}
 602
 603func stripMailto(link []byte) []byte {
 604	if bytes.HasPrefix(link, []byte("mailto://")) {
 605		return link[9:]
 606	} else if bytes.HasPrefix(link, []byte("mailto:")) {
 607		return link[7:]
 608	} else {
 609		return link
 610	}
 611}
 612
 613// autolinkType specifies a kind of autolink that gets detected.
 614type autolinkType int
 615
 616// These are the possible flag values for the autolink renderer.
 617const (
 618	notAutolink autolinkType = iota
 619	normalAutolink
 620	emailAutolink
 621)
 622
 623// '<' when tags or autolinks are allowed
 624func leftAngle(p *parser, data []byte, offset int) (int, *Node) {
 625	data = data[offset:]
 626	altype, end := tagLength(data)
 627	if size := p.inlineHTMLComment(data); size > 0 {
 628		end = size
 629	}
 630	if end > 2 {
 631		if altype != notAutolink {
 632			var uLink bytes.Buffer
 633			unescapeText(&uLink, data[1:end+1-2])
 634			if uLink.Len() > 0 {
 635				link := uLink.Bytes()
 636				node := NewNode(Link)
 637				node.Destination = link
 638				if altype == emailAutolink {
 639					node.Destination = append([]byte("mailto:"), link...)
 640				}
 641				node.AppendChild(text(stripMailto(link)))
 642				return end, node
 643			}
 644		} else {
 645			htmlTag := NewNode(HTMLSpan)
 646			htmlTag.Literal = data[:end]
 647			return end, htmlTag
 648		}
 649	}
 650
 651	return end, nil
 652}
 653
 654// '\\' backslash escape
 655var escapeChars = []byte("\\`*_{}[]()#+-.!:|&<>~")
 656
 657func escape(p *parser, data []byte, offset int) (int, *Node) {
 658	data = data[offset:]
 659
 660	if len(data) > 1 {
 661		if p.flags&BackslashLineBreak != 0 && data[1] == '\n' {
 662			return 2, NewNode(Hardbreak)
 663		}
 664		if bytes.IndexByte(escapeChars, data[1]) < 0 {
 665			return 0, nil
 666		}
 667
 668		return 2, text(data[1:2])
 669	}
 670
 671	return 2, nil
 672}
 673
 674func unescapeText(ob *bytes.Buffer, src []byte) {
 675	i := 0
 676	for i < len(src) {
 677		org := i
 678		for i < len(src) && src[i] != '\\' {
 679			i++
 680		}
 681
 682		if i > org {
 683			ob.Write(src[org:i])
 684		}
 685
 686		if i+1 >= len(src) {
 687			break
 688		}
 689
 690		ob.WriteByte(src[i+1])
 691		i += 2
 692	}
 693}
 694
 695// '&' escaped when it doesn't belong to an entity
 696// valid entities are assumed to be anything matching &#?[A-Za-z0-9]+;
 697func entity(p *parser, data []byte, offset int) (int, *Node) {
 698	data = data[offset:]
 699
 700	end := 1
 701
 702	if end < len(data) && data[end] == '#' {
 703		end++
 704	}
 705
 706	for end < len(data) && isalnum(data[end]) {
 707		end++
 708	}
 709
 710	if end < len(data) && data[end] == ';' {
 711		end++ // real entity
 712	} else {
 713		return 0, nil // lone '&'
 714	}
 715
 716	ent := data[:end]
 717	// undo &amp; escaping or it will be converted to &amp;amp; by another
 718	// escaper in the renderer
 719	if bytes.Equal(ent, []byte("&amp;")) {
 720		ent = []byte{'&'}
 721	}
 722
 723	return end, text(ent)
 724}
 725
 726func linkEndsWithEntity(data []byte, linkEnd int) bool {
 727	entityRanges := htmlEntityRe.FindAllIndex(data[:linkEnd], -1)
 728	return entityRanges != nil && entityRanges[len(entityRanges)-1][1] == linkEnd
 729}
 730
 731var prefixes = [][]byte{
 732	[]byte("http://"),
 733	[]byte("https://"),
 734	[]byte("ftp://"),
 735	[]byte("file://"),
 736	[]byte("mailto:"),
 737}
 738
 739func hasPrefixCaseInsensitive(s, prefix []byte) bool {
 740	if len(s) < len(prefix) {
 741		return false
 742	}
 743	delta := byte('a' - 'A')
 744	for i, b := range prefix {
 745		if b != s[i] && b != s[i]+delta {
 746			return false
 747		}
 748	}
 749	return true
 750}
 751
 752func maybeAutoLink(p *parser, data []byte, offset int) (int, *Node) {
 753	// quick check to rule out most false hits
 754	if p.insideLink || len(data) < offset+6 { // 6 is the len() of the shortest of the prefixes
 755		return 0, nil
 756	}
 757	for _, prefix := range prefixes {
 758		endOfHead := offset + 8 // 8 is the len() of the longest prefix
 759		if endOfHead > len(data) {
 760			endOfHead = len(data)
 761		}
 762		if hasPrefixCaseInsensitive(data[offset:endOfHead], prefix) {
 763			return autoLink(p, data, offset)
 764		}
 765	}
 766	return 0, nil
 767}
 768
 769func autoLink(p *parser, data []byte, offset int) (int, *Node) {
 770	// Now a more expensive check to see if we're not inside an anchor element
 771	anchorStart := offset
 772	offsetFromAnchor := 0
 773	for anchorStart > 0 && data[anchorStart] != '<' {
 774		anchorStart--
 775		offsetFromAnchor++
 776	}
 777
 778	anchorStr := anchorRe.Find(data[anchorStart:])
 779	if anchorStr != nil {
 780		anchorClose := NewNode(HTMLSpan)
 781		anchorClose.Literal = anchorStr[offsetFromAnchor:]
 782		return len(anchorStr) - offsetFromAnchor, anchorClose
 783	}
 784
 785	// scan backward for a word boundary
 786	rewind := 0
 787	for offset-rewind > 0 && rewind <= 7 && isletter(data[offset-rewind-1]) {
 788		rewind++
 789	}
 790	if rewind > 6 { // longest supported protocol is "mailto" which has 6 letters
 791		return 0, nil
 792	}
 793
 794	origData := data
 795	data = data[offset-rewind:]
 796
 797	if !isSafeLink(data) {
 798		return 0, nil
 799	}
 800
 801	linkEnd := 0
 802	for linkEnd < len(data) && !isEndOfLink(data[linkEnd]) {
 803		linkEnd++
 804	}
 805
 806	// Skip punctuation at the end of the link
 807	if (data[linkEnd-1] == '.' || data[linkEnd-1] == ',') && data[linkEnd-2] != '\\' {
 808		linkEnd--
 809	}
 810
 811	// But don't skip semicolon if it's a part of escaped entity:
 812	if data[linkEnd-1] == ';' && data[linkEnd-2] != '\\' && !linkEndsWithEntity(data, linkEnd) {
 813		linkEnd--
 814	}
 815
 816	// See if the link finishes with a punctuation sign that can be closed.
 817	var copen byte
 818	switch data[linkEnd-1] {
 819	case '"':
 820		copen = '"'
 821	case '\'':
 822		copen = '\''
 823	case ')':
 824		copen = '('
 825	case ']':
 826		copen = '['
 827	case '}':
 828		copen = '{'
 829	default:
 830		copen = 0
 831	}
 832
 833	if copen != 0 {
 834		bufEnd := offset - rewind + linkEnd - 2
 835
 836		openDelim := 1
 837
 838		/* Try to close the final punctuation sign in this same line;
 839		 * if we managed to close it outside of the URL, that means that it's
 840		 * not part of the URL. If it closes inside the URL, that means it
 841		 * is part of the URL.
 842		 *
 843		 * Examples:
 844		 *
 845		 *      foo http://www.pokemon.com/Pikachu_(Electric) bar
 846		 *              => http://www.pokemon.com/Pikachu_(Electric)
 847		 *
 848		 *      foo (http://www.pokemon.com/Pikachu_(Electric)) bar
 849		 *              => http://www.pokemon.com/Pikachu_(Electric)
 850		 *
 851		 *      foo http://www.pokemon.com/Pikachu_(Electric)) bar
 852		 *              => http://www.pokemon.com/Pikachu_(Electric))
 853		 *
 854		 *      (foo http://www.pokemon.com/Pikachu_(Electric)) bar
 855		 *              => foo http://www.pokemon.com/Pikachu_(Electric)
 856		 */
 857
 858		for bufEnd >= 0 && origData[bufEnd] != '\n' && openDelim != 0 {
 859			if origData[bufEnd] == data[linkEnd-1] {
 860				openDelim++
 861			}
 862
 863			if origData[bufEnd] == copen {
 864				openDelim--
 865			}
 866
 867			bufEnd--
 868		}
 869
 870		if openDelim == 0 {
 871			linkEnd--
 872		}
 873	}
 874
 875	var uLink bytes.Buffer
 876	unescapeText(&uLink, data[:linkEnd])
 877
 878	if uLink.Len() > 0 {
 879		node := NewNode(Link)
 880		node.Destination = uLink.Bytes()
 881		node.AppendChild(text(uLink.Bytes()))
 882		return linkEnd, node
 883	}
 884
 885	return linkEnd, nil
 886}
 887
 888func isEndOfLink(char byte) bool {
 889	return isspace(char) || char == '<'
 890}
 891
 892var validUris = [][]byte{[]byte("http://"), []byte("https://"), []byte("ftp://"), []byte("mailto://")}
 893var validPaths = [][]byte{[]byte("/"), []byte("./"), []byte("../")}
 894
 895func isSafeLink(link []byte) bool {
 896	for _, path := range validPaths {
 897		if len(link) >= len(path) && bytes.Equal(link[:len(path)], path) {
 898			if len(link) == len(path) {
 899				return true
 900			} else if isalnum(link[len(path)]) {
 901				return true
 902			}
 903		}
 904	}
 905
 906	for _, prefix := range validUris {
 907		// TODO: handle unicode here
 908		// case-insensitive prefix test
 909		if len(link) > len(prefix) && bytes.Equal(bytes.ToLower(link[:len(prefix)]), prefix) && isalnum(link[len(prefix)]) {
 910			return true
 911		}
 912	}
 913
 914	return false
 915}
 916
 917// return the length of the given tag, or 0 is it's not valid
 918func tagLength(data []byte) (autolink autolinkType, end int) {
 919	var i, j int
 920
 921	// a valid tag can't be shorter than 3 chars
 922	if len(data) < 3 {
 923		return notAutolink, 0
 924	}
 925
 926	// begins with a '<' optionally followed by '/', followed by letter or number
 927	if data[0] != '<' {
 928		return notAutolink, 0
 929	}
 930	if data[1] == '/' {
 931		i = 2
 932	} else {
 933		i = 1
 934	}
 935
 936	if !isalnum(data[i]) {
 937		return notAutolink, 0
 938	}
 939
 940	// scheme test
 941	autolink = notAutolink
 942
 943	// try to find the beginning of an URI
 944	for i < len(data) && (isalnum(data[i]) || data[i] == '.' || data[i] == '+' || data[i] == '-') {
 945		i++
 946	}
 947
 948	if i > 1 && i < len(data) && data[i] == '@' {
 949		if j = isMailtoAutoLink(data[i:]); j != 0 {
 950			return emailAutolink, i + j
 951		}
 952	}
 953
 954	if i > 2 && i < len(data) && data[i] == ':' {
 955		autolink = normalAutolink
 956		i++
 957	}
 958
 959	// complete autolink test: no whitespace or ' or "
 960	switch {
 961	case i >= len(data):
 962		autolink = notAutolink
 963	case autolink != notAutolink:
 964		j = i
 965
 966		for i < len(data) {
 967			if data[i] == '\\' {
 968				i += 2
 969			} else if data[i] == '>' || data[i] == '\'' || data[i] == '"' || isspace(data[i]) {
 970				break
 971			} else {
 972				i++
 973			}
 974
 975		}
 976
 977		if i >= len(data) {
 978			return autolink, 0
 979		}
 980		if i > j && data[i] == '>' {
 981			return autolink, i + 1
 982		}
 983
 984		// one of the forbidden chars has been found
 985		autolink = notAutolink
 986	}
 987	i += bytes.IndexByte(data[i:], '>')
 988	if i < 0 {
 989		return autolink, 0
 990	}
 991	return autolink, i + 1
 992}
 993
 994// look for the address part of a mail autolink and '>'
 995// this is less strict than the original markdown e-mail address matching
 996func isMailtoAutoLink(data []byte) int {
 997	nb := 0
 998
 999	// address is assumed to be: [-@._a-zA-Z0-9]+ with exactly one '@'
1000	for i := 0; i < len(data); i++ {
1001		if isalnum(data[i]) {
1002			continue
1003		}
1004
1005		switch data[i] {
1006		case '@':
1007			nb++
1008
1009		case '-', '.', '_':
1010			break
1011
1012		case '>':
1013			if nb == 1 {
1014				return i + 1
1015			}
1016			return 0
1017		default:
1018			return 0
1019		}
1020	}
1021
1022	return 0
1023}
1024
1025// look for the next emph char, skipping other constructs
1026func helperFindEmphChar(data []byte, c byte) int {
1027	i := 0
1028
1029	for i < len(data) {
1030		for i < len(data) && data[i] != c && data[i] != '`' && data[i] != '[' {
1031			i++
1032		}
1033		if i >= len(data) {
1034			return 0
1035		}
1036		// do not count escaped chars
1037		if i != 0 && data[i-1] == '\\' {
1038			i++
1039			continue
1040		}
1041		if data[i] == c {
1042			return i
1043		}
1044
1045		if data[i] == '`' {
1046			// skip a code span
1047			tmpI := 0
1048			i++
1049			for i < len(data) && data[i] != '`' {
1050				if tmpI == 0 && data[i] == c {
1051					tmpI = i
1052				}
1053				i++
1054			}
1055			if i >= len(data) {
1056				return tmpI
1057			}
1058			i++
1059		} else if data[i] == '[' {
1060			// skip a link
1061			tmpI := 0
1062			i++
1063			for i < len(data) && data[i] != ']' {
1064				if tmpI == 0 && data[i] == c {
1065					tmpI = i
1066				}
1067				i++
1068			}
1069			i++
1070			for i < len(data) && (data[i] == ' ' || data[i] == '\n') {
1071				i++
1072			}
1073			if i >= len(data) {
1074				return tmpI
1075			}
1076			if data[i] != '[' && data[i] != '(' { // not a link
1077				if tmpI > 0 {
1078					return tmpI
1079				}
1080				continue
1081			}
1082			cc := data[i]
1083			i++
1084			for i < len(data) && data[i] != cc {
1085				if tmpI == 0 && data[i] == c {
1086					return i
1087				}
1088				i++
1089			}
1090			if i >= len(data) {
1091				return tmpI
1092			}
1093			i++
1094		}
1095	}
1096	return 0
1097}
1098
1099func helperEmphasis(p *parser, data []byte, c byte) (int, *Node) {
1100	i := 0
1101
1102	// skip one symbol if coming from emph3
1103	if len(data) > 1 && data[0] == c && data[1] == c {
1104		i = 1
1105	}
1106
1107	for i < len(data) {
1108		length := helperFindEmphChar(data[i:], c)
1109		if length == 0 {
1110			return 0, nil
1111		}
1112		i += length
1113		if i >= len(data) {
1114			return 0, nil
1115		}
1116
1117		if i+1 < len(data) && data[i+1] == c {
1118			i++
1119			continue
1120		}
1121
1122		if data[i] == c && !isspace(data[i-1]) {
1123
1124			if p.flags&NoIntraEmphasis != 0 {
1125				if !(i+1 == len(data) || isspace(data[i+1]) || ispunct(data[i+1])) {
1126					continue
1127				}
1128			}
1129
1130			emph := NewNode(Emph)
1131			p.inline(emph, data[:i])
1132			return i + 1, emph
1133		}
1134	}
1135
1136	return 0, nil
1137}
1138
1139func helperDoubleEmphasis(p *parser, data []byte, c byte) (int, *Node) {
1140	i := 0
1141
1142	for i < len(data) {
1143		length := helperFindEmphChar(data[i:], c)
1144		if length == 0 {
1145			return 0, nil
1146		}
1147		i += length
1148
1149		if i+1 < len(data) && data[i] == c && data[i+1] == c && i > 0 && !isspace(data[i-1]) {
1150			nodeType := Strong
1151			if c == '~' {
1152				nodeType = Del
1153			}
1154			node := NewNode(nodeType)
1155			p.inline(node, data[:i])
1156			return i + 2, node
1157		}
1158		i++
1159	}
1160	return 0, nil
1161}
1162
1163func helperTripleEmphasis(p *parser, data []byte, offset int, c byte) (int, *Node) {
1164	i := 0
1165	origData := data
1166	data = data[offset:]
1167
1168	for i < len(data) {
1169		length := helperFindEmphChar(data[i:], c)
1170		if length == 0 {
1171			return 0, nil
1172		}
1173		i += length
1174
1175		// skip whitespace preceded symbols
1176		if data[i] != c || isspace(data[i-1]) {
1177			continue
1178		}
1179
1180		switch {
1181		case i+2 < len(data) && data[i+1] == c && data[i+2] == c:
1182			// triple symbol found
1183			strong := NewNode(Strong)
1184			em := NewNode(Emph)
1185			strong.AppendChild(em)
1186			p.inline(em, data[:i])
1187			return i + 3, strong
1188		case (i+1 < len(data) && data[i+1] == c):
1189			// double symbol found, hand over to emph1
1190			length, node := helperEmphasis(p, origData[offset-2:], c)
1191			if length == 0 {
1192				return 0, nil
1193			}
1194			return length - 2, node
1195		default:
1196			// single symbol found, hand over to emph2
1197			length, node := helperDoubleEmphasis(p, origData[offset-1:], c)
1198			if length == 0 {
1199				return 0, nil
1200			}
1201			return length - 1, node
1202		}
1203	}
1204	return 0, nil
1205}
1206
1207func text(s []byte) *Node {
1208	node := NewNode(Text)
1209	node.Literal = s
1210	return node
1211}
1212
1213func normalizeURI(s []byte) []byte {
1214	return s // TODO: implement
1215}