How to use ReplaceAll and RuleDelayed with an Association?

This is more of an extended comment rather than an answer. Using this definition:

assoc = <|"a" -> "str1", "b" -> <|"a" -> "str2", "b" -> <||>|>|>
(* <|"a" -> "str1", "b" -> <|"a" -> "str2", "b" -> <||>|>|> *)

when applying this replacement the result was:

assoc /. <|"a" -> v_, "b" -> <||>|> :> v <> "0"
(* <|"a" -> "str1", "b" -> "str2" <> "0"|> *)

whereas the expected result was:

(* <|"a" -> "str1", "b" -> "str20"|> *)

JM suggested using Replace with KeyValuePattern

Using Replace with KeyValuePattern produces the desired result:

Replace[assoc, KeyValuePattern[{"a" -> v_, "b" -> <||>}] :> v <> "0", {1}]
(* <|"a" -> "str1", "b" -> "str20"|> *)

Result is not related to KeyValuePattern

I discovered that KeyValuePattern is not the cure, rather it was using Replace rather than ReplaceAll.

Observe the results below.

Replace[assoc, <|"a" -> v_, "b" -> <||>|> :> v <> "0", {1}]
(* <|"a" -> "str1", "b" -> "str20"|> *)

ReplaceAll[assoc, <|"a" -> v_, "b" -> <||>|> :> v <> "0"]
(* <|"a" -> "str1", "b" -> "str2" <> "0"|> *)

ReplaceAll[assoc,KeyValuePattern[{"a" -> v_, "b" -> <||>}] :> v <> "0"]
(* <|"a" -> "str1", "b" -> "str2" <> "0"|> *)

Independent of the whether we use KeyValuePattern or not, Replace appears to evaluate the result whereas ReplaceAll returns the result without evaluation.

Using List rather than Association

If rather than using an association we use a list, the problem disappears.

listOfRules = {{"a" -> "str1"}, {"b" -> {"a" -> "str2"}}}
(* {{"a" -> "str1"}, {"b" -> {"a" -> "str2"}}} *)

Replace[listOfRules, {"a" -> v_, "b" -> {}} :> v <> "0", Infinity]
(* {"a" -> "str1", "b" -> "str20"} *)

ReplaceAll[listOfRules, {"a" -> v_, "b" -> {}} :> v <> "0"]
(* {"a" -> "str1", "b" -> "str20"} *)

Particular solution

It is interesting than to see that for this particular problem one could convert the association to a list, make the replacement and then convert it back to an association.

assoc /. Association -> List /. {"a" -> v_, "b" -> {}} :> v <> "0" // Association
(* <|"a" -> "str1", "b" -> "str20"|> *)

I don't recommend this (I think J.M's suggestion is the way to go).

Conclusion

It appears that applying ReplaceAll to an association returns the result without evaluation whereas Relace evaluates the result.

This observation is unrelated to the use of KeyValuePattern.

Maybe J.M. doesn't need to write an answer anymore, but I think this answer based on Leonid Shifrin's earlier answer should be recorded.

assoc = <|"a" -> "str1", "b" -> <|"a" -> "str2", "b" -> <||>|>|>;
assoc /. <|"a" -> v_, "b" -> <||>|> :> RuleCondition[v <> "0"]

<|"a" -> "str1", "b" -> "str20"|>