Libraries: Add LibMarkdown

17 files changed, 711 insertions, 1 deletions

diff --git a/Kernel/makeall.sh b/Kernel/makeall.sh
index 29913554b3..d4713cf6ac 100755
--- a/Kernel/makeall.sh
+++ b/Kernel/makeall.sh
@@ -38,6 +38,7 @@ build_targets="$build_targets ../Libraries/LibHTML"
 build_targets="$build_targets ../Libraries/LibM"
 build_targets="$build_targets ../Libraries/LibPCIDB"
 build_targets="$build_targets ../Libraries/LibVT"
+build_targets="$build_targets ../Libraries/LibMarkdown"
 
 build_targets="$build_targets ../Applications/About"
 build_targets="$build_targets ../Applications/Calculator"
diff --git a/Libraries/LibMarkdown/MDBlock.h b/Libraries/LibMarkdown/MDBlock.h
new file mode 100644
index 0000000000..e1c1bfc7b1
--- /dev/null
+++ b/Libraries/LibMarkdown/MDBlock.h
@@ -0,0 +1,12 @@
+#pragma once
+
+#include <AK/String.h>
+
+class MDBlock {
+public:
+    virtual ~MDBlock() {}
+
+    virtual String render_to_html() const = 0;
+    virtual String render_for_terminal() const = 0;
+    virtual bool parse(Vector<StringView>::ConstIterator& lines) = 0;
+};
diff --git a/Libraries/LibMarkdown/MDCodeBlock.cpp b/Libraries/LibMarkdown/MDCodeBlock.cpp
new file mode 100644
index 0000000000..230324ccf9
--- /dev/null
+++ b/Libraries/LibMarkdown/MDCodeBlock.cpp
@@ -0,0 +1,137 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDCodeBlock.h>
+
+MDText::Style MDCodeBlock::style() const
+{
+    if (m_style_spec.spans().is_empty())
+        return {};
+    return m_style_spec.spans()[0].style;
+}
+
+String MDCodeBlock::style_language() const
+{
+    if (m_style_spec.spans().is_empty())
+        return {};
+    return m_style_spec.spans()[0].text;
+}
+
+String MDCodeBlock::render_to_html() const
+{
+    StringBuilder builder;
+
+    String style_language = this->style_language();
+    MDText::Style style = this->style();
+
+    if (style.strong)
+        builder.append("<b>");
+    if (style.emph)
+        builder.append("<i>");
+
+    builder.append("<pre>");
+
+    if (style_language.is_null())
+        builder.append("<code>");
+    else
+        builder.appendf("<code class=\"%s\">", style_language.characters());
+
+    // TODO: This should also be done in other places.
+    for (int i = 0; i < m_code.length(); i++)
+        if (m_code[i] == '<')
+            builder.append("&lt;");
+        else if (m_code[i] == '>')
+            builder.append("&gt;");
+        else if (m_code[i] == '&')
+            builder.append("&amp;");
+        else
+            builder.append(m_code[i]);
+
+    builder.append("</code></pre>");
+
+    if (style.emph)
+        builder.append("</i>");
+    if (style.strong)
+        builder.append("</b>");
+
+    builder.append('\n');
+
+    return builder.build();
+}
+
+String MDCodeBlock::render_for_terminal() const
+{
+    StringBuilder builder;
+
+    MDText::Style style = this->style();
+    bool needs_styling = style.strong || style.emph;
+    if (needs_styling) {
+        builder.append("\033[");
+        bool first = true;
+        if (style.strong) {
+            builder.append('1');
+            first = false;
+        }
+        if (style.emph) {
+            if (!first)
+                builder.append(';');
+            builder.append('4');
+        }
+        builder.append('m');
+    }
+
+    builder.append(m_code);
+
+    if (needs_styling)
+        builder.append("\033[0m");
+
+    builder.append("\n\n");
+
+    return builder.build();
+}
+
+bool MDCodeBlock::parse(Vector<StringView>::ConstIterator& lines)
+{
+    if (lines.is_end())
+        return false;
+
+    constexpr auto tick_tick_tick = "```";
+
+    StringView line = *lines;
+    if (!line.starts_with(tick_tick_tick))
+        return false;
+
+    // Our Markdown extension: we allow
+    // specifying a style and a language
+    // for a code block, like so:
+    //
+    // ```**sh**
+    // $ echo hello friends!
+    // ````
+    //
+    // The code block will be made bold,
+    // and if possible syntax-highlighted
+    // as appropriate for a shell script.
+    StringView style_spec = line.substring_view(3, line.length() - 3);
+    bool success = m_style_spec.parse(style_spec);
+    ASSERT(success);
+
+    ++lines;
+
+    bool first = true;
+    StringBuilder builder;
+
+    while (true) {
+        if (lines.is_end())
+            break;
+        line = *lines;
+        ++lines;
+        if (line == tick_tick_tick)
+            break;
+        if (!first)
+            builder.append('\n');
+        builder.append(line);
+        first = false;
+    }
+
+    m_code = builder.build();
+    return true;
+}
diff --git a/Libraries/LibMarkdown/MDCodeBlock.h b/Libraries/LibMarkdown/MDCodeBlock.h
new file mode 100644
index 0000000000..6e45d74d42
--- /dev/null
+++ b/Libraries/LibMarkdown/MDCodeBlock.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <LibMarkdown/MDBlock.h>
+#include <LibMarkdown/MDText.h>
+
+class MDCodeBlock final : public MDBlock {
+public:
+    virtual ~MDCodeBlock() override {}
+
+    virtual String render_to_html() const override;
+    virtual String render_for_terminal() const override;
+    virtual bool parse(Vector<StringView>::ConstIterator& lines) override;
+
+private:
+    String style_language() const;
+    MDText::Style style() const;
+
+    String m_code;
+    MDText m_style_spec;
+};
diff --git a/Libraries/LibMarkdown/MDDocument.cpp b/Libraries/LibMarkdown/MDDocument.cpp
new file mode 100644
index 0000000000..21b2f2a3e1
--- /dev/null
+++ b/Libraries/LibMarkdown/MDDocument.cpp
@@ -0,0 +1,62 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDCodeBlock.h>
+#include <LibMarkdown/MDDocument.h>
+#include <LibMarkdown/MDHeading.h>
+#include <LibMarkdown/MDList.h>
+#include <LibMarkdown/MDParagraph.h>
+
+String MDDocument::render_to_html() const
+{
+    StringBuilder builder;
+
+    for (auto& block : m_blocks) {
+        auto s = block.render_to_html();
+        builder.append(s);
+    }
+
+    return builder.build();
+}
+
+String MDDocument::render_for_terminal() const
+{
+    StringBuilder builder;
+
+    for (auto& block : m_blocks) {
+        auto s = block.render_for_terminal();
+        builder.append(s);
+    }
+
+    return builder.build();
+}
+
+template<typename Block>
+static bool helper(Vector<StringView>::ConstIterator& lines, NonnullOwnPtrVector<MDBlock>& blocks)
+{
+    NonnullOwnPtr<Block> block = make<Block>();
+    bool success = block->parse(lines);
+    if (!success)
+        return false;
+    blocks.append(move(block));
+    return true;
+}
+
+bool MDDocument::parse(const StringView& str)
+{
+    const Vector<StringView> lines_vec = str.split_view('\n', true);
+    auto lines = lines_vec.begin();
+
+    while (true) {
+        if (lines.is_end())
+            return true;
+
+        if ((*lines).is_empty()) {
+            ++lines;
+            continue;
+        }
+
+        bool any = helper<MDList>(lines, m_blocks) || helper<MDParagraph>(lines, m_blocks) || helper<MDCodeBlock>(lines, m_blocks) || helper<MDHeading>(lines, m_blocks);
+
+        if (!any)
+            return false;
+    }
+}
diff --git a/Libraries/LibMarkdown/MDDocument.h b/Libraries/LibMarkdown/MDDocument.h
new file mode 100644
index 0000000000..c3f04def07
--- /dev/null
+++ b/Libraries/LibMarkdown/MDDocument.h
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <AK/NonnullOwnPtrVector.h>
+#include <AK/String.h>
+#include <LibMarkdown/MDBlock.h>
+
+class MDDocument final {
+public:
+    String render_to_html() const;
+    String render_for_terminal() const;
+
+    bool parse(const StringView&);
+
+private:
+    NonnullOwnPtrVector<MDBlock> m_blocks;
+};
diff --git a/Libraries/LibMarkdown/MDHeading.cpp b/Libraries/LibMarkdown/MDHeading.cpp
new file mode 100644
index 0000000000..37c15db49b
--- /dev/null
+++ b/Libraries/LibMarkdown/MDHeading.cpp
@@ -0,0 +1,54 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDHeading.h>
+
+String MDHeading::render_to_html() const
+{
+    StringBuilder builder;
+    builder.appendf("<h%d>", m_level);
+    builder.append(m_text.render_to_html());
+    builder.appendf("</h%d>\n", m_level);
+    return builder.build();
+}
+
+String MDHeading::render_for_terminal() const
+{
+    StringBuilder builder;
+
+    switch (m_level) {
+    case 1:
+    case 2:
+        builder.append("\n\033[1m");
+        builder.append(m_text.render_for_terminal().to_uppercase());
+        builder.append("\033[0m\n");
+        break;
+    default:
+        builder.append("\n\033[1m");
+        builder.append(m_text.render_for_terminal());
+        builder.append("\033[0m\n");
+        break;
+    }
+
+    return builder.build();
+}
+
+bool MDHeading::parse(Vector<StringView>::ConstIterator& lines)
+{
+    if (lines.is_end())
+        return false;
+
+    const StringView& line = *lines;
+
+    for (m_level = 0; m_level < line.length(); m_level++)
+        if (line[m_level] != '#')
+            break;
+
+    if (m_level >= line.length() || line[m_level] != ' ')
+        return false;
+
+    StringView title_view = line.substring_view(m_level + 1, line.length() - m_level - 1);
+    bool success = m_text.parse(title_view);
+    ASSERT(success);
+
+    ++lines;
+    return true;
+}
diff --git a/Libraries/LibMarkdown/MDHeading.h b/Libraries/LibMarkdown/MDHeading.h
new file mode 100644
index 0000000000..67fff18689
--- /dev/null
+++ b/Libraries/LibMarkdown/MDHeading.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include <AK/StringView.h>
+#include <AK/Vector.h>
+#include <LibMarkdown/MDBlock.h>
+#include <LibMarkdown/MDText.h>
+
+class MDHeading final : public MDBlock {
+public:
+    virtual ~MDHeading() override {}
+
+    virtual String render_to_html() const override;
+    virtual String render_for_terminal() const override;
+    virtual bool parse(Vector<StringView>::ConstIterator& lines) override;
+
+private:
+    MDText m_text;
+    int m_level { -1 };
+};
diff --git a/Libraries/LibMarkdown/MDList.cpp b/Libraries/LibMarkdown/MDList.cpp
new file mode 100644
index 0000000000..c6072b98f6
--- /dev/null
+++ b/Libraries/LibMarkdown/MDList.cpp
@@ -0,0 +1,89 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDList.h>
+
+String MDList::render_to_html() const
+{
+    StringBuilder builder;
+
+    const char* tag = m_is_ordered ? "ol" : "ul";
+    builder.appendf("<%s>", tag);
+
+    for (auto& item : m_items) {
+        builder.append("<li>");
+        builder.append(item.render_to_html());
+        builder.append("</li>\n");
+    }
+
+    builder.appendf("</%s>\n", tag);
+
+    return builder.build();
+}
+
+String MDList::render_for_terminal() const
+{
+    StringBuilder builder;
+
+    int i = 0;
+    for (auto& item : m_items) {
+        builder.append("  ");
+        if (m_is_ordered)
+            builder.appendf("%d. ", ++i);
+        else
+            builder.append("* ");
+        builder.append(item.render_for_terminal());
+        builder.append("\n");
+    }
+    builder.append("\n");
+
+    return builder.build();
+}
+
+bool MDList::parse(Vector<StringView>::ConstIterator& lines)
+{
+    bool first = true;
+    while (true) {
+        if (lines.is_end())
+            break;
+        const StringView& line = *lines;
+        if (line.is_empty())
+            break;
+
+        bool appears_unordered = false;
+        int offset = 0;
+        if (line.length() > 2)
+            if (line[1] == ' ' && (line[0] == '*' || line[0] == '-')) {
+                appears_unordered = true;
+                offset = 2;
+            }
+
+        bool appears_ordered = false;
+        for (int i = 0; i < 10 && i < line.length(); i++) {
+            char ch = line[i];
+            if ('0' <= ch && ch <= '9')
+                continue;
+            if (ch == '.' || ch == ')')
+                if (i + 1 < line.length() && line[i + 1] == ' ') {
+                    appears_ordered = true;
+                    offset = i + 1;
+                }
+            break;
+        }
+
+        ASSERT(!(appears_unordered && appears_ordered));
+        if (!appears_unordered && !appears_ordered)
+            return false;
+        if (first)
+            m_is_ordered = appears_ordered;
+        else if (m_is_ordered != appears_ordered)
+            return false;
+
+        first = false;
+        MDText text;
+        bool success = text.parse(line.substring_view(offset, line.length() - offset));
+        ASSERT(success);
+        m_items.append(move(text));
+        ++lines;
+    }
+
+    return !first;
+}
diff --git a/Libraries/LibMarkdown/MDList.h b/Libraries/LibMarkdown/MDList.h
new file mode 100644
index 0000000000..c1e58dc9bb
--- /dev/null
+++ b/Libraries/LibMarkdown/MDList.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include <AK/Vector.h>
+#include <LibMarkdown/MDBlock.h>
+#include <LibMarkdown/MDText.h>
+
+class MDList final : public MDBlock {
+public:
+    virtual ~MDList() override {}
+
+    virtual String render_to_html() const override;
+    virtual String render_for_terminal() const override;
+    virtual bool parse(Vector<StringView>::ConstIterator& lines) override;
+
+private:
+    // TODO: List items should be considered blocks of their own kind.
+    Vector<MDText> m_items;
+    bool m_is_ordered { false };
+};
diff --git a/Libraries/LibMarkdown/MDParagraph.cpp b/Libraries/LibMarkdown/MDParagraph.cpp
new file mode 100644
index 0000000000..75874a57ae
--- /dev/null
+++ b/Libraries/LibMarkdown/MDParagraph.cpp
@@ -0,0 +1,66 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDParagraph.h>
+
+String MDParagraph::render_to_html() const
+{
+    StringBuilder builder;
+    builder.appendf("<p>");
+    builder.append(m_text.render_to_html());
+    builder.appendf("</p>\n");
+    return builder.build();
+}
+
+String MDParagraph::render_for_terminal() const
+{
+    StringBuilder builder;
+    builder.append(m_text.render_for_terminal());
+    builder.appendf("\n\n");
+    return builder.build();
+}
+
+bool MDParagraph::parse(Vector<StringView>::ConstIterator& lines)
+{
+    if (lines.is_end())
+        return false;
+
+    bool first = true;
+    StringBuilder builder;
+
+    while (true) {
+        if (lines.is_end())
+            break;
+        StringView line = *lines;
+        if (line.is_empty())
+            break;
+        char ch = line[0];
+        // See if it looks like a blockquote
+        // or like an indented block.
+        if (ch == '>' || ch == ' ')
+            break;
+        if (line.length() > 1) {
+            // See if it looks like a heading.
+            if (ch == '#' && (line[1] == '#' || line[1] == ' '))
+                break;
+            // See if it looks like a code block.
+            if (ch == '`' && line[1] == '`')
+                break;
+            // See if it looks like a list.
+            if (ch == '*' || ch == '-')
+                if (line[1] == ' ')
+                    break;
+        }
+
+        if (!first)
+            builder.append(' ');
+        builder.append(line);
+        first = false;
+        ++lines;
+    }
+
+    if (first)
+        return false;
+
+    bool success = m_text.parse(builder.build());
+    ASSERT(success);
+    return true;
+}
diff --git a/Libraries/LibMarkdown/MDParagraph.h b/Libraries/LibMarkdown/MDParagraph.h
new file mode 100644
index 0000000000..245ba4f75e
--- /dev/null
+++ b/Libraries/LibMarkdown/MDParagraph.h
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <LibMarkdown/MDBlock.h>
+#include <LibMarkdown/MDText.h>
+
+class MDParagraph final : public MDBlock {
+public:
+    virtual ~MDParagraph() override {}
+
+    virtual String render_to_html() const override;
+    virtual String render_for_terminal() const override;
+    virtual bool parse(Vector<StringView>::ConstIterator& lines) override;
+
+private:
+    MDText m_text;
+};
diff --git a/Libraries/LibMarkdown/MDText.cpp b/Libraries/LibMarkdown/MDText.cpp
new file mode 100644
index 0000000000..9be080df9b
--- /dev/null
+++ b/Libraries/LibMarkdown/MDText.cpp
@@ -0,0 +1,138 @@
+#include <AK/StringBuilder.h>
+#include <LibMarkdown/MDText.h>
+
+String MDText::render_to_html() const
+{
+    StringBuilder builder;
+
+    Vector<String> open_tags;
+    Style current_style;
+
+    for (auto& span : m_spans) {
+        struct TagAndFlag {
+            String tag;
+            bool Style::*flag;
+        };
+        TagAndFlag tags_and_flags[] = {
+            { "i", &Style::emph },
+            { "b", &Style::strong },
+            { "code", &Style::code }
+        };
+        auto it = open_tags.find([&](const String& open_tag) {
+            for (auto& tag_and_flag : tags_and_flags) {
+                if (open_tag == tag_and_flag.tag && !(span.style.*tag_and_flag.flag))
+                    return true;
+            }
+            return false;
+        });
+
+        if (!it.is_end()) {
+            // We found an open tag that should
+            // not be open for the new span. Close
+            // it and all the open tags that follow
+            // it.
+            for (auto it2 = --open_tags.end(); it2 >= it; --it2) {
+                const String& tag = *it2;
+                builder.appendf("</%s>", tag.characters());
+                for (auto& tag_and_flag : tags_and_flags)
+                    if (tag == tag_and_flag.tag)
+                        current_style.*tag_and_flag.flag = false;
+            }
+            open_tags.shrink(it.index());
+        }
+        for (auto& tag_and_flag : tags_and_flags) {
+            if (current_style.*tag_and_flag.flag != span.style.*tag_and_flag.flag) {
+                open_tags.append(tag_and_flag.tag);
+                builder.appendf("<%s>", tag_and_flag.tag.characters());
+            }
+        }
+
+        current_style = span.style;
+        builder.append(span.text);
+    }
+
+    for (auto it = --open_tags.end(); it >= open_tags.begin(); --it) {
+        const String& tag = *it;
+        builder.appendf("</%s>", tag.characters());
+    }
+
+    return builder.build();
+}
+
+String MDText::render_for_terminal() const
+{
+    StringBuilder builder;
+
+    for (auto& span : m_spans) {
+        bool needs_styling = span.style.strong || span.style.emph || span.style.code;
+        if (needs_styling) {
+            builder.append("\033[");
+            bool first = true;
+            if (span.style.strong || span.style.code) {
+                builder.append('1');
+                first = false;
+            }
+            if (span.style.emph) {
+                if (!first)
+                    builder.append(';');
+                builder.append('4');
+            }
+            builder.append('m');
+        }
+
+        builder.append(span.text.characters());
+
+        if (needs_styling)
+            builder.append("\033[0m");
+    }
+
+    return builder.build();
+}
+
+bool MDText::parse(const StringView& str)
+{
+    Style current_style;
+    int current_span_start = 0;
+
+    for (int offset = 0; offset < str.length(); offset++) {
+        char ch = str[offset];
+
+        bool is_special_character = false;
+        is_special_character |= ch == '`';
+        if (!current_style.code)
+            is_special_character |= ch == '*' || ch == '_';
+        if (!is_special_character)
+            continue;
+
+        if (current_span_start != offset) {
+            Span span {
+                str.substring_view(current_span_start, offset - current_span_start),
+                current_style
+            };
+            m_spans.append(move(span));
+        }
+
+        if (ch == '`') {
+            current_style.code = !current_style.code;
+        } else {
+            if (offset + 1 < str.length() && str[offset + 1] == ch) {
+                offset++;
+                current_style.strong = !current_style.strong;
+            } else {
+                current_style.emph = !current_style.emph;
+            }
+        }
+
+        current_span_start = offset + 1;
+    }
+
+    if (current_span_start < str.length()) {
+        Span span {
+            str.substring_view(current_span_start, str.length() - current_span_start),
+            current_style
+        };
+        m_spans.append(move(span));
+    }
+
+    return true;
+}
diff --git a/Libraries/LibMarkdown/MDText.h b/Libraries/LibMarkdown/MDText.h
new file mode 100644
index 0000000000..c1bda3cadf
--- /dev/null
+++ b/Libraries/LibMarkdown/MDText.h
@@ -0,0 +1,28 @@
+#pragma once
+
+#include <AK/String.h>
+#include <AK/Vector.h>
+
+class MDText final {
+public:
+    struct Style {
+        bool emph { false };
+        bool strong { false };
+        bool code { false };
+    };
+
+    struct Span {
+        String text;
+        Style style;
+    };
+
+    const Vector<Span>& spans() const { return m_spans; }
+
+    String render_to_html() const;
+    String render_for_terminal() const;
+
+    bool parse(const StringView&);
+
+private:
+    Vector<Span> m_spans;
+};
diff --git a/Libraries/LibMarkdown/Makefile b/Libraries/LibMarkdown/Makefile
new file mode 100644
index 0000000000..295fc19cdb
--- /dev/null
+++ b/Libraries/LibMarkdown/Makefile
@@ -0,0 +1,25 @@
+include ../../Makefile.common
+
+OBJS = \
+    MDDocument.o \
+		MDParagraph.o \
+		MDHeading.o \
+		MDCodeBlock.o \
+		MDList.o \
+		MDText.o
+
+LIBRARY = libmarkdown.a
+DEFINES += -DUSERLAND
+
+all: $(LIBRARY)
+
+$(LIBRARY): $(OBJS)
+	@echo "LIB $@"; $(AR) rcs $@ $(OBJS) $(LIBS)
+
+.cpp.o:
+	@echo "CXX $<"; $(CXX) $(CXXFLAGS) -o $@ -c $<
+
+-include $(OBJS:%.o=%.d)
+
+clean:
+	@echo "CLEAN"; rm -f $(LIBRARY) $(OBJS) *.d
diff --git a/Libraries/LibMarkdown/install.sh b/Libraries/LibMarkdown/install.sh
new file mode 100755
index 0000000000..0f40a59675
--- /dev/null
+++ b/Libraries/LibMarkdown/install.sh
@@ -0,0 +1,8 @@
+#!/bin/sh
+
+set -e
+SERENITY_ROOT=../../
+
+mkdir -p $SERENITY_ROOT/Root/usr/include/LibMarkdown/
+cp *.h $SERENITY_ROOT/Root/usr/include/LibMarkdown/
+cp libmarkdown.a $SERENITY_ROOT/Root/usr/lib/
diff --git a/Userland/Makefile b/Userland/Makefile
index ab46369c96..57993debfd 100644
--- a/Userland/Makefile
+++ b/Userland/Makefile
@@ -19,7 +19,7 @@ clean:
 
 $(APPS) : % : %.o $(OBJS)
 	@echo "LD $@"
-	@$(LD) -o $@ $(LDFLAGS) $< -lc -lgui -ldraw -laudio -lipc -lthread -lcore -lpcidb
+	@$(LD) -o $@ $(LDFLAGS) $< -lc -lgui -ldraw -laudio -lipc -lthread -lcore -lpcidb -lmarkdown
 
 %.o: %.cpp
 	@echo "CXX $<"