cmark - My own fork of cmark for commonmark conversion

Age	Commit message (Collapse)	Author
2020-02-16	Fix #220 (hash collisions for references).	John MacFarlane
	This commit ports Vicent Marti's fix in cmark-gfm. (384cc9db4cd7a90f59c0751e58eb7b3023d38b85) His commit message follows: As explained on the previous commit, it is trivial to DoS the CMark parser by generating a document where all the link reference names hash to the same bucket in the hash table. This will cause the lookup process for each reference to take linear time on the amount of references in the document, and with enough link references to lookup, the end result is a pathological O(N^2) that causes medium-sized documents to finish parsing in 5+ minutes. To avoid this issue, we propose the present commit. Based on the fact that all reference lookup/resolution in a Markdown document is always performed as a last step during the parse process, we've reimplemented reference storage as follows: 1. New references are always inserted at the end of a linked list. This is an O(1) operation, and does not check whether an existing (duplicate) reference with the same label already exists in the document. 2. Upon the first call to `cmark_reference_lookup` (when it is expected that no further references will be added to the reference map), the linked list of references is written into a fixed-size array. 3. The fixed size array can then be efficiently sorted in-place in O(n log n). This operation only happens once. We perform this sort in a _stable_ manner to ensure that the earliest link reference in the document always has preference, as the spec dictates. To accomplish this, every reference is tagged with a generation number when initially inserted in the linked list. 4. The sorted array is then compacted in O(n). Since it was sorted in a stable way, the first reference for each label is preserved and the duplicates are removed, matching the spec. 5. We can now simply perform a binary search for the current `cmark_reference_lookup` query in O(log n). Any further lookup calls will also be O(log n), since the sorted references table only needs to be generated once. The resulting implementation is notably simple (as it uses standard library builtins `qsort` and `bsearch`), whilst performing better than the fixed size hash table in documents that have a high number of references and never becoming pathological regardless of the input.
2020-01-23	Use C string instead of chunk for link URL and title	Nick Wellnhofer
	Use zero-terminated C strings instead of cmark_chunks without storing the length. This introduces a few additional strlen computations, but overhead should be low. Allows to reduce size of struct cmark_node later.
2016-09-26	Use cmark_mem to free where used to alloc	Yuki Izumi

2016-06-24	Reformatted.	John MacFarlane

2016-06-22	cmark_reference_lookup: Return NULL if reference is null string.	John MacFarlane

2016-06-06	msvc: Fix warnings and errors	Vicent Marti

2016-06-06	cmark: Implement support for custom allocators	Vicent Marti

2016-06-06	cmake: Global handler for OOM situations	Vicent Marti

2015-08-06	Prefix utf8proc functions to avoid conflict with existing library	Kevin Wojniak

2015-07-27	Use clang-format, llvm style, for formatting.	John MacFarlane
	* Reformatted all source files. * Added 'format' target to Makefile. * Removed 'astyle' target. * Updated .editorconfig.
2015-05-14	Store link URL and title as cmark_chunk	Nick Wellnhofer

2015-01-05	Reformatted code consistently with astyle.	John MacFarlane

2014-12-15	Re-added cmark_ prefix to strbuf and chunk.	John MacFarlane
	Reverts 225d720.
2014-11-28	Use prefixed names for symbols from references.h	Nick Wellnhofer

2014-11-28	Use prefixed names for symbols from inlines.h	Nick Wellnhofer

2014-11-17	Rename ast.h to parser.h	Nick Wellnhofer

2014-11-16	Cast void pointers explicitly	Nick Wellnhofer
	Needed for C++ compatibility.
2014-11-16	Moved AST details from public header cmark.h to private ast.h.	John MacFarlane

2014-11-13	Removed ast modules, moved these defs back to cmark.h.	John MacFarlane

2014-11-09	Added MAX_LINK_LABEL_LENGTH to cmark.h.	John MacFarlane
	Use in link label parsing and reference lookup.
2014-11-06	Reformatted code consistently.	John MacFarlane

2014-10-24	Renamed c program and library stmd -> cmark.	John MacFarlane
	Also renamed internal library functions accordingly.
2014-10-24	Merge branch 'master' of https://github.com/tchetch/stmd into tchetch-master	John MacFarlane
	Conflicts: src/inlines.c
2014-10-24	Use unsigned char, not char, throughout.	John MacFarlane
	Closes #43.
2014-10-18	Reindented c sources.	John MacFarlane

2014-10-06	- Use of calloc instead of malloc	tchetch
	- Test for NULL after allocation
2014-09-15	Cleanup external APIs	Vicent Marti

2014-09-10	Do not create references with empty names	Vicent Marti

2014-09-10	Fix misc bugs	Vicent Marti

2014-09-10	Cleanup reference implementation	Vicent Marti