HTML parsing algorithm for extracting <a> tags

Question

My intention is to create a complete HTML parser, so far I made a basic algorithm that iterates trough text and extracts everything in an "a" tag.

It works on everything I tried, but I want a review of what I could do better or what I did right.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <fstream>
#include <streambuf>
#include <sstream>


std::vector<std::string> performCheck(std::string check, std::string text)
{       
        int iterator = 0;
        int second_iterator = 0;

        bool is_flag = false;

        std::string returnString = "";
        std::vector<std::string> returnVector;

        for(iterator = 0;iterator < text.size();iterator++)
        {
            if(text[iterator] == '<')
            {

                is_flag = true;

                for(second_iterator = 0;second_iterator < check.size();second_iterator++)
                {
                    if(text[iterator + second_iterator] == check[second_iterator])
                    {   
                        returnString = returnString + text[iterator + second_iterator];
                    }
                    else
                    {
                        is_flag = false;
                        returnString = "";
                        break;
                    }
                }

                if(is_flag == true)
                {
                    for(second_iterator = iterator + second_iterator;second_iterator < text.size();second_iterator++)
                    {   
                        returnString = returnString +  text[second_iterator];

                        if(text[second_iterator - 2] == '/' && text[second_iterator - 1] == 'a')
                        {   
                            returnVector.push_back(returnString);
                            break;
                        }
                    }   
                }

            }

        }

    return returnVector;    
}


int main(int argc, char** argv) {

    std::string check = "<a href=\"";
    std::vector<std::string> urlmap;

    std::ifstream t("your_file.ext");
    std::stringstream buffer;
    buffer << t.rdbuf();

    std::string textBig = buffer.str();


    urlmap = performCheck(check, textBig);

    for(int iterator = 0;iterator < urlmap.size();iterator++)
    {
        std::cout<<urlmap[iterator]<<std::endl;
    } 

    system("PAUSE");

    return 0;
}

Answer 1

First of all, as Loki mentioned in the comments, it is incredibly cumbersome to parse any text that made by human. We tend to abuse things, so I'd refrain from parsing it myself. There are good libraries that does parsing. If you want performance, I'd go with boost.spirit that is based on expression templates. I've also made a topic request about expression templates on so.docs, but it still has low upvote count, so don't rely on it to come in near future. I strongly encourage you to read about both, because it is the greatest power to have in parsing input files.

About the code:

Good try, but probably you will need a lot more. Some people would think that I need to put suggestion about regex over hand rolled search, but I will just put link to an article on very famous blog.

Use <cstdio> instead of <stdio.h>. All C headers have C++ equivalents and are preferred over C ones.

Don't mix <cstdio> and <iostream>. The I/O may become unordered.

Overflow:

int can and will overflow. For example here:

iterator + second_iterator

The C standard guarantees only 16 bit for it as I remember. It is not mandated by the standard that return type of the std::string::size() is int. In fact it will probably never be int, because it is signed type, but size can not be negative. I recommend you to use std::string::size_type. It is guaranteed by the standard that this type will have enough capacity to store the maximum possible index that std::string can have.

Readability comments:

second_iterator - 2
second_iterator - 1

Those 2 expressions rise alerts in my head, because type of second_iterator is int, which is signed. I know that it will never be less than 2 by design, but I think that there is at least one better solution, one of which is mentioned above.

I'd wait bool(s) from any function that has check word in it's name. I think the function now performs what sequence of std::string::find()s does. This suggests using standard one. It will be much more clear.

Performance comments:

Usually standard containers are implemented in terms of 3 pointers, not a pointer and 2 indices. This suggests that iterator based algorithms will outperform index based ones. Further reading.

I found it impractical using push_back() without preceding reserve() call where performance matters. On top of that, every push will have control flow manipulators, which will greatly decrease the throughput on the function.

I'd use std::string::compare to compare check string and the substring. The implementations are allowed to deploy more intelligent comparison functions, so it might have zero development cost optimization.

Redesign:

I'd redesign the function to accept Input Iterators. It will make it more customizable with zero runtime overhead (well it depends on the iterator, but it is possible and easy to do). It will also keep strings from being copied.

Notes about example code:

You can use range for loop to traverse whole container/range.

Declaring urlmap right on assignment would trigger copy elision (the output will start constructing right in urlmap).

Don't use system(). It is the source of many security issues.

Answer 2

OverView

Issue 1

What about:

<a style="a:link{color: red;}" href="#">

That's a perfectly valid <a> tag. Your code is not going find this tag.

Issue 2

Web pages can be big. If we just look at amazon.com

curl -A 'Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-US; rv:1.8.1.13) Gecko/20080313 Firefox' https://www.amazon.com | wc

lines   words   characters
3408    8386    203846

So this page is 200K bytes long. I don't think its a good idea to load the whole page into memory then parse the page.

std::ifstream t("your_file.ext");
std::stringstream buffer;
buffer << t.rdbuf();
std::string textBig = buffer.str();

Personally I would just work with the stream. You can get iterators that work on streams just like they work on a text string so your algorithm would not have to change.

std:::istreambuf_iterator<char> loop(t);
if (*loop == '<') {
   ++loop;

   ...etc

Code Review

C++ Headers

This is a C header.

#include <stdio.h>

The C++ version of this header is:

#include <cstdio>    // drop the ".h" at the end add "c" at the beginning.

Most standard C libraries have a C++ version. The main difference is that the code is guaranteed to be placed in the standard namespace rather than the global namespace.

Prefer to pass by const reference

If you are not mutating your parameters (check and text) then pass by const reference this will prevent you objects from being copied. Currently you will be making a copy of text which if it is 200K in size is a serious performance issue.

std::vector<std::string> performCheck(std::string check, std::string text)

// I would use:

std::vector<std::string> performCheck(std::string const& check, std::string const& text)

Iteratos

Yes. Iterators are the best thing. But these are not iterators (apart from the name).

        int iterator = 0;
        int second_iterator = 0;

An iterator has a couple of properties. It can be incremented/decremented (you have that covered). But an iterator can be dereferenced with operator* to get the value. It looks very much like a pointer. This is an index (nothing wrong with that. indexing into text is just fine just use the correct terminology please).

Declare variables close to the point of usage.

        int iterator = 0;
        int second_iterator = 0;

You declare second_iterator way up the to tof the function. But it is only used deep inside a nested loop. Just declare variables before you use them. Then it is easy to see the type information close to the point where they are being used.

Return value

One of these two things is not returned.

        std::string returnString = "";
        std::vector<std::string> returnVector;