Markdown Linter - Fun With Nested Containers

Summary¶

In my last article, I talked about my continuing efforts to clean up the scenario tests and the existing parser issues. In this article, I continue to talk about cleaning up existing parser issues.

Introduction¶

It is yet another week of me working on bugs, and I can easily tell that progress is being made to reduce the amount of outstanding work. As I look at the Issues List, the number of issues above the Priority 3 line is dwindling, and that is a good thing. Depending on how I look at the Issues List, I can just about see both headings for Priority 2 and Priority 3 at the same time! For me, that is progress!

And while it was not planned, almost all the work that I did this week was related to nested container blocks in some way, so that was interesting. As the only way that I make that progress is by buckling down and getting stuff done, here I go!

What Is the Audience for This Article?¶

While detailed more eloquently in this article, my goal for this technical article is to focus on the reasoning behind my solutions, rather than the solutions themselves. For a full record of the solutions presented in this article, please consult the commits that occurred between 20 Oct 2021 and 24 Oct 2021.

Issue 72 - Fun with Nested Blocks¶

Picking an issue somewhat at random, I ended up looking at the following issue:

md006 - how works within bq?
      - two lists in same top-level... same indent?
      - ordered with unordered sub, and unordered with ordered sub

As I delved into the issue, I must admit that I never determined the real purpose of this rule. First off, the original rule was disabled, but there was no documented reason for disabling the rule. If I had to guess, it was because there was another rule that did the job better than that one. Which rule replaced this rule? I am not sure. If I had to guess, perhaps it was Rule Md007, though I do not feel that Rule Md007 works as an improved version of Rule Md006. Secondly, the rule documentation for Rule Md006 seems… well… incomplete. It describes lists at the start of the line but does not take any time to exclude sublists. It is almost as if someone started to make a rule, gave up in the middle, and then published that rule.

Those feelings left me with an interesting problem. The primary goal of the PyMarkdown project is to provide parity with the Markdown Lint rules. So far, this is the only rule where I am not sure that I can provide that required parity. In this case, I strongly feel that parity alone is not good enough. While I realized that this rule is also disabled in PyMarkdown, I did not feel that it gave me any leeway in implementing something that I felt was half done. As always, I felt that I need to do what I thought was right for the PyMarkdown project. And in the end, that is what I focused on. For every other rule, parity was the best choice. But I made a firm decision that for this rule, leaving the rule as-is was the wrong decision. I needed my version of this rule to be something I could stand behind my work on.

Given that decision, I started to work on the small adjustments needed to change the rule to allow it to function with Unordered List elements inside of another container. First, I started by adding ten new scenario tests and verifying that each of the tests were failing. Then I went back to the rule module and started to make a couple of targeted changes. Instead of having a __list_stack, I replaced it with a __token_stack and placed both List elements and Block Quote elements on the stack. After a couple of adjustments to ensure that the Block Quotes were being added and removed from the stack properly, I moved the calculation of the expected indentation value into the new __calculate_expected_indent function.

From there, it was largely trial and error as I worked through the existing scenario tests, adjusting the calculations within the __calculate_expected_indent function as I went. One scenario test at a time, I moved closer to having them all passing until they were all passing. The big addition to the __calculate_expected_indent function was that I needed to take the Block Quote characters into account. Once I had that figured out, the rest of the stuff was easy.

Issue 74 - More Fun With Nested Blocks¶

As I had just finished work on nested container blocks, I thought that it might be useful to get some other nested block issues out of the way as well. I decided to tackle this one:

### if time 270, 271, 237, 238

- with list item
- start with blank
- list starts after bq starts
- varying spaces between bqs
- no space between bq and following list

It was a bit of a meaty issue to tackle, mostly because it is not very clearly defined. Specifically, when I started digging into this issue and breaking it apart, it resulted in seven new variations of the test_list_blocks_271 scenario test, three new variations of the test_list_blocks_270 scenario test, and two variations a piece of the test_list_blocks_237 and test_list_blocks_238 scenario tests. For the most part, everything worked well, and all the tests passed. In addition, there were two tests dealing with the alternating four levels of nesting scenario tests which I postponed until later.

Other than those two scenario tests, the only scenario test that I had a problem with involved the following Markdown:

1. > 1. Blockquote
> continued here.

When the parser first encountered this Markdown document, it incorrectly parsed the text and merged it all together. But looking at the reference HTML, the reference document and the tokens were not matching up. The reference HTML had two Block Quote elements, with one line of text in each element. The tokens had everything in one Block Quote element, with the text appended together. That difference is what I needed to figure out.

Walking through the Markdown in my head, it took a bit for me to get the Markdown parsing in the correct context. When the second line is reached, there are already three active containers in play: a List element, a Block Quote element, and another List element. When the parser then encountered the second line, it only saw the Block Quote starting on that line and ignored the List elements completely. That was the main problem. To parse the document correctly, the parser needed to close all three containers, as the main List container requires an indent of two spaces, and that indent is not provided. Only after those containers are closed can the line be properly parsed. With the slate being effectively cleared, a new Block Quote can then be opened to hold the second line of text, just as the reference HTML dictates.

But how to get there?

Doing The Hard Work¶

Most of the changes occurred in the is_block_quote_start function. During the initial parsing of the document, the parser believed that the text on the second line was a continuation of the first line due to paragraph continuation lines. As those lines apply to both Block Quote elements and List elements, removing the first two characters from the second line would enact exactly that scenario. So, care had to be taken not to destroy that existing functionality.

The first part of this solution was the easy part. I changed the is_block_quote_start function to look for any List elements near the start of the token_stack list. If the potential Block Quote start column had any List elements before it where the leading spaces were not present, then the algorithm closed all open elements back to and including that List element. Basically, if current line was not indented enough so that the encompassing List element was satisfied, everything back to that point needed to be closed. That code was a bit tricky in places, but relatively easy to figure out.

The tricky part was what to do at that point to get the parsing to continue. All the obvious options were messy. Most of them were variations of calling back into the Container Block Processor and reprocessing the line. A couple of the variations were simply trying to bend the processors to do something that I did not feel comfortable with. I tried about four different solutions before I decided that I needed to do something different. So, I finally tried to do something unexpected: I tried the non-obvious solution. Normally, I would report that it was the dead simple solution that worked the best, but in this case, that solution was more work than it was worth. In this case, I just had a hunch that something different was needed.

After taking a handful of deep breaths, I decided that the non-obvious but best option was to use the parser’s requeue ability. It took me a bit to flush the concept out, but it made sense in a non-obvious sort of way. Once I added any tokens that arose from the blocks that were closed from the close-blocks action, the only thing left to do was to properly parse the line. Putting extra code in that function to call back into the parser just was not working. On a whim, thinking that it probably would not work, I added the lines:

    parser_state.token_document.extend(container_level_tokens)
    lines_to_requeue = [position_marker.text_to_parse]
    requeue_line_info = RequeueLineInfo(lines_to_requeue, False)

and then returned that requeue_line_info variable after fourteen None keywords. And it worked! Well, it mostly worked, but it got me close enough to getting the document parsed properly that I was able to finish the work in about ten minutes with some smart debugging.

What saved me was that while I wanted to keep things simple, I was not afraid to try something unusual. Just because it had not worked before, did not mean it was not going to work this time. And the idea itself was a stretch. Up to that point, the requeue feature of the parser was only used with Link Reference Definitions. But if there was another case for using it to make the code cleaner, this was it. Once the effects of closing the blocks was completed, the cleanest way for the line to be processed properly was to requeue the line for further processing. The handling of the requeue_line_info return variable was already supported, so no other code was needed.

And except for Black placing each return value on its own line¹, the code was compact and localized to where the issue was. That made it easy to tidy things up and verify that all tests were passing properly before going on. I did go back and forth on whether to leave the container_depth variable debugging in, but as I have added it and removed it during debugging sessions three times now, I figured I might as well leave it in.

Issue 76 - Nested Unordered List Fun¶

The solution to this issue was so funny to me that it made me laugh. By looking at the project code, anyone can tell that I prefer descriptive names for my functions and variables. Instead of i and j, I am more likely to use inner_loop_index and outer_loop_index. It is something that has served me well over the years and is something I plan to keep on doing. But that does not mean I always use it flawlessly.

In looking over the scenario tests for Rule Md007, I decided that it needed at least one solid complex scenario test to ensure things were working properly. As such, I added this Markdown document:

This is a test

 * this is level 1
 * this is also level 1
   * this is level 2
   * this is also level 2
      * this is level 3
   * this is also level 2
    * this is also level 2
    * this is also level 2
* this is also level 1

This was a good complex test because the only List start or List Item that was in the right column was the last line. Every other line was off by at least one column, and in some cases, off by two columns.

But when I ran the document through PyMarkdown the first time, the errors that I got back were not the complete list I was expecting. Narrowing things down to the __process_eligible_list_start function, I debugged through the following code until I noticed something.

last_stack_depth = parser_state.token_stack[-1].ws_before_marker
...
while current_start_index < last_stack_depth and allow_list_removal:
    ...
    last_stack_depth = parser_state.token_stack[-1].ws_before_marker

I did not really notice it clearly at first, but I noticed that something was weird about the code. It took me fifteen minutes before I noticed it clearly enough that I could explain it to myself: the while statement was comparing an index to a depth. As I walked through it again, the reasoning for the error crystalized before my eyes.

In counting terms, depths and positions are usually different than indices. The first group of items usually start counting at 1, where the indices always start counting at 0. And in this case, that made all the difference. Instead of comparing an index to a depth, I either needed to compare an index to an index or a position to a depth. After flipping a coin, I changed the above code to the following:

last_stack_depth = parser_state.token_stack[-1].ws_before_marker
...
last_stack_depth_index = last_stack_depth - 1
while (
    current_start_index < last_stack_depth_index and allow_list_removal
):
    ...
    last_stack_depth = parser_state.token_stack[-1].ws_before_marker
    last_stack_depth_index = last_stack_depth - 1

I could have gone either way, but once I altered the last_stack_depth variable, it just seemed like the right choice. More importantly, with those minor changes, the tests that were previously passing were still passing, as were the tests that were previously failing.

Yup, I had an off-by-one error, and I fixed it! Me, finding an off-by-one error in my own code. I laughed. Maybe you had to be there to get why that was funny. But trust me, it was.

Issue 79 - Fixing Rule Md005¶

Rule Md005. A simple rule, but one that I was never one hundred percent happy with. But that was about to change with this issue. This issue was basically my “stop complaining and start fixing” issue for this rule.

From the top, there was never anything wrong with this rule, at least nothing I could point to at the time. It just did not feel right. When I was implementing the rules and checking out their documentation, I was just left with a feeling that I had missed something in the rule or its scenario tests. Along the way, I added an issue about checking for left alignment and right alignment in the same list, but I knew that there was more to my feeling than that. I just had to figure out what that feeling was based on and deal with it.

I started the process by looking through the existing scenario tests for any holes that I perceived in the tests. Adding scenario tests to address those spots, I ended up with ten new scenario tests. As I started testing the Unordered List elements, I found out that the new tests for those elements were passing with only small adjustments to do with the reported expected and actual measurements. That was good. But when I got to the Ordered List elements, things were not in the same shape. While I had done a decent job on covering simple scenarios in the original tests, the more complicated scenario tests were largely ignored.

How Did This Happen?¶

Digging into the code, I was able to quickly determine what the issues were. Before I started addressing this issue, the code for detecting the failures for List elements was relatively simple:

if self.__list_stack[-1].is_unordered_list_start:
    if self.__list_stack[-1].indent_level != token.indent_level:
        self.__report_issue(context, token)
elif self.__list_stack[-1].column_number != token.column_number:
    original_text = self.__list_stack[-1].list_start_content
    if self.__list_stack[-1].extracted_whitespace:
        original_text += self.__list_stack[-1].extracted_whitespace
    original_text_length = len(original_text)
    current_prefix_length = len(
        token.list_start_content + token.extracted_whitespace
    )
    if original_text_length == current_prefix_length:
        assert token.indent_level == self.__list_stack[-1].indent_level
    else:
        self.__report_issue(context, token)

If a new List Item was detected, and that List Item element was part of an Unordered List element, then a simple check was made against the indent level of the parent List element. Anything other than that was a failure. For the Ordered List Items, there was a bit more to the calculation. If the two column_number fields were the same, then the List Item was left-aligned with the parent List element, and things were okay. Otherwise, a calculation was done to see if the new List Item was right aligned with that same parent List element.

There is nothing wrong with that logic… for simple cases. All the tests were passing properly, and it was detecting each problem properly and triggering the rule properly. But the scenario tests that I added were for more complex scenarios, and that is where that logic failed. The failures were not about the individual lines themselves, but how different lines and different lists interacted with each other.

What Next?¶

After starting to understand the scope of the issues, I took a bit of a break and did some stuff around the house before getting back to the problem. Looking at the issue with a fresh set of eyes, I figured out that there were three significant issues that I needed to take care of. The first is that there was no cohesion between lists within the same base list. The second is that the determination of alignment for an Ordered List was being made on a List Item by List Item basis. Finally, the third issue was that List Start tokens were being left completely out of the check.

Leaving a copy of the existing rule in the editor, I started working on a new rule from scratch. I started by copying the __report_issue function and everything above it over to the new rule, followed by adding a blank next_token function. I then started by adding the framework for the Unordered List elements back into the function. Except for a couple of small improvements, that handling was working fine, so there was no need to make drastic changes to it. But the Ordered List elements were another story.

Instead of tackling each of the above issues individually, I took a step back and quickly designed a better rule. Addressing the third problem first, I needed code that could work with either a List Item or a List start to decide if it was properly indented. To that extent, I created the __handle_ordered_list_item function that accepted either token as its input and tested that thoroughly before moving on. As that function was the cornerstone of the design, it was critical that I got it right!

I then designed around the second issue by delaying the determination of the alignment of the list until the end of the list. Before the rule had been deciding that line by line, and it did not work well. Using this design, I could make a clean determination of the alignment once using every list element. Once I had that determination, I could call the __handle_ordered_list_item function at the end of the list without any loss of functionality. Instead, it allowed me to simplify the __handle_ordered_list_item code to look for one alignment or the other, not both. That cleared up that issue.

Finally, I looked at the first issue and came up with a quick and dirty solution. Whenever a new Ordered List was started, it stored an alignment of UNKNOWN at the level of the sublist. Then, when a positive determination of the alignment was made, it would update that value to LEFT or RIGHT. Within the __handle_ordered_list_item function the following code was added:

    list_level = len(self.__list_stack)
    list_alignment = self.__ordered_list_alignment[list_level]

    if list_alignment == OrderedListAlignment.RIGHT:
        ...
    else:
        ...

At that point, the calculation was as simple as determining the depth of the List element, grabbing the alignment from the __ordered_list_alignment field, and using that value to determine what alignment to check against. As part of the design, I verified that unless the alignment was determined to be RIGHT, the other two alignments were equivalent. That helped simplify things.

It was pedantic, but I walked through it all on paper before writing even one line of code. It took a bit of time, but it was worth it. By doing that, I was quickly able to spot a couple of design flaws and fix them right away. I do admit that I had a couple of small “black boxes” that were labelled calculate alignment and handle ordered list, but I was confident that I had a solid grip on the algorithms for those two components. It was the rest of the design I was worried about.

Once done, I found that with the design in hand, the code came naturally from the design. I started with everything in the next_token function before moving groups of functionalities into their own functions. The __compute_ordered_list_alignment function was used to calculate the alignment of a list, and __handle_ordered_list_item was used to evaluate both Ordered List start tokens and Ordered List Item tokens. The remaining handle_* were used to manage the delegation of calls to those functions, as well as ensuring that the various fields to collect the required information were maintained.

It was unexpected, but exception for a couple of small errors that were easily fixed, the updated version of the rule worked on the first try. I do not attribute that to any prowess in writing Python code. Rather it was because I took the time to design it on paper and walk through the scenarios in my head before going on. I do admit that sometimes I do some “cowboy coding”, but unless it is something really simple, I find that those sessions are more hit-or-miss than I prefer.

But what is important to me is that this entire development process has helped me hone my design skills. And it was cases like this where I got to use those skills to produce something that worked very cleanly and very solidly.

Issue 77 - Fun with Scripts¶

With time left before my noon² deadline, I wanted to look at a puzzling issue that was just reported within the last couple of days. In this issue, the reporter claimed that the pymarkdown script was not being assigned the right permissions upon installation. I double checked with them, and they confirmed the steps the included with the issue. It just was not working for them.

Not wasting any time, I switched over to my pymtest project and ran my usual release tests against the version of the project I have built in the dist directory. Two minutes later, I walked through the test script and the output one line at a time, and everything looked good. I then switched to the variation of that script that grabs the package from PyPi.org and performed the same verification with the same results. Everything looked good so far.

Switching over to my Ubuntu shell running on WSL2, I repeated the same tests, and everything looked fine. Nothing deviated from my pymtest project except the name of the script, the upymtest project it was in, and that it was running under Ubuntu instead of Windows 10. I had to be missing something. But what?

Starting From Scratch¶

I knew I had to do something different, but I did not have a clue of what to change. So, the only thing I could think of was to go back to the beginning and build my way back up to the level of the script in the upymtest project. I started by going into the upymtest project and doing a pipenv --rm to remove the virtual environment. To be sure, I also found out the location of the virtual environments on my machine and removed both directories associated with them. Then I tried to remove the Pipfile file and the Pipfile.lock file. While I did think this may be overkill, at the very least I knew I was thorough in my work!

Running through the Ubuntu version of my test, everything stayed the same. It was frustrating and rewarding at the same time. There was something in my process of local testing that masked the issue, and I still had to find it. But at the same time, I was mostly there, and just had to find the right thing to tweak. And just to confirm, with a thoroughly removed PyMarkdown package, installing it from PyPi resulted in incorrect permissions, installing it locally resulted in correct permissions.

Digging Deeper¶

So, I pulled up some online resources and started to read them. I was about 45 minutes into that research when I came across this article at Real Python. In it, there was one line that caught my attention:

If you’ve installed a Python package using pip, then chances are that a wheel has made the installation faster and more efficient.

Huh? I had always thought it was the tarball, the *.tar.gz file, which was used with PyPi.org and the pip family of commands. Could I have been wrong?

With nothing to lose, I read the rest of that article, and I was convinced that I had made a mistake. Changing my test process to operation off the wheel file instead of the tarball, everything worked the same on the Windows shell. But in the Ubuntu shell, I was finally able to reproduce the behavior. Installing from the wheel, the script to start PyMarkdown did not have the correct permissions. I had reproduced the reported issue, now to fix it.

Scripts and Permissions¶

Now that I had a good handle on the problem, I started looking for a solution. It took a while to find one because looking for python wheel permission script or any variation of those words usually results in pages that deal with the proper permissions needed to install Python packages, not on how to specify the correct permissions for the scripts. But it was during one of those searches that I found information referring to specifying entry-points to allow for post-install fixes. That article was about providing an extra feature to set that package up for use with one of three editors, but it was still a useful find. It explained that there was a console_scripts setting for entry-points that creates platform specific scripts for each entry point at install time.

That just clicked with me as the right thing to do. Prior to reading that article, I had hard-wired the pymarkdown and pymarkdown.bat scripts into the scripts directory. Since they have been there for months, I can only assume that there were one or more examples of projects that used scripts and that method of launching projects. And to be honest, if you are building on a Linux system and have all the permissions set right, that might be a practical alternative. For my setup, it just was not cutting it.

So, I went to my setup.py file and removed this line:

    scripts=PACKAGE_SCRIPTS,

and replaced it with these lines:

    entry_points={
        "console_scripts": [
            "pymarkdown=pymarkdown.__main__:main",
        ],
    },

According to the article, that code should inform the setup tools to create a new script called pymarkdown specifically for the operating system it is installed on. In that script, it looks in the __main__ module of the pymarkdown package and invokes the main function. After a small alteration to the __main__.py file to include an extra function, I created a new package.

Holding my breath, I walked through the Windows installation tests, and everything worked fine. Switching over to my Ubuntu shell, I repeated the installation tests and… everything worked! It was a relief! It had taken me three hours at that point to figure out the problem and devise a solution, but it was worth it.

Just to be sure, I cleaned up the __main__.py file and the setup.py file before repackaging the project and running through the steps two more times. Once again, it might have been overkill, but I wanted to make sure.

Release 0.9.2¶

Having completed all the changes I was going to make for this week, I decided that I had enough changes and fixes queued up to make a release. After quick double checking to make sure that everything looked right, I created a package using my package.cmd script. Then, using both my Ubuntu shell and my Windows shell, I tested against the wheel file produced by the package.cmd script to make sure it installed properly in both environments.

This was only a slight change from earlier releases, but an important one. In earlier releases, I was testing against the *.tar.gz file produced by the script, not the *.whl or wheel file. As the wheel file is the file that is uploaded to the PyPi.org site, it is important to test against that file. As I thought it was the *.tar.gz file that was uploaded, I was testing locally against that file. As such, Issue 77 slipped through the cracks.

But with my slightly adjusted process in place, everything looked good, so I published the release, tagged the repository, and published the release notes for the release. It was a good feeling.

What Was My Experience So Far?¶

Things are rolling, and I am starting to feel that they are taking longer than I want them to. And I know that this is my personal danger zone. For me, getting that last five to ten percent of a project done has always been my weak spot. It happens not because I grow tired of the project, but because I do not find any fun in the work. And yes, solving issues is fun for me, while double checking everything is more of a chore.

Regardless, I need to make sure I keep my focus on completing this section of the work and getting on to more of the interesting problems in the next section: code quality improvements and performance improvements. For now, I am reminding myself of those tasks coming up as a “carrot” to dangle in front of myself to get this “boring” work done.

Hope it helps… but I am close enough I think I can manage.

What is Next?¶

Looking ahead in the Issues List, I see a lot of validation and a lot of added scenario tests. I am not sure which one I will decide to do, but either way, with those items out the way, the list will almost be down to Priority 3 items. Gotta like that! Stay tuned!

Like this post? Share on: Twitter ❄ Facebook ❄ Email